7.Реш.Злп методом искусств.Базиса

Метод искусственного базиса используется для нахождения допустимого базисного решения задачи линейного программирования, когда в условии присутствуют ограничения типа равенств. Рассмотрим задачу:

max{F(x)=∑c_ix_i|∑a_jix_i=b_j, j=1,m; x_i≥0}.

В ограничения и в функцию цели вводят так называемые «искусственные переменные» R_j следующим образом:

∑a_jix+R_j=b_j, j=1,m;F(x)=∑c_ix_i-M∑R_j

При введении искусственных переменных в методе искусственного базиса в функцию цели им приписывается достаточно большой коэффициент M, который имеет смысл штрафа за введение искусственных переменных. В случае минимизации искусственные переменные прибавляются к функции цели с коэффициентом M. Введение искусственных переменных допустимо в том случае, если в процессе решения задачи они последовательно обращаются в нуль.

Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна – для составляющей F = ∑c_ix_i, , а другая – для составляющей M ∑R_j Рассмотрим процедуру решения задачи на конкретном примере.

Пример 1. Найти максимум функции F(x) = -x₁ + 2x₂ - x₃ при ограничениях:

2x₁+3x₂+x₃=3,

x₁+3x₃=2,

x₁≥0, x₂≥0, x₃≥0 .

Применим метод искусственного базиса. Введем искусственные переменные в ограничения задачи

2x₁ + 3x₂ + x₃ + R₁ = 3;

x₁ + 3x₃ + R₂ = 2 ;

Функция цели F(x)-M ∑R_j= -x₁ + 2x₂ - x₃ - M(R₁+R₂).

Выразим сумму R₁ + R₂ из системы ограничений: R₁ + R₂ = 5 - 3x₁ - 3x₂ - 4x₃, тогда F(x) = -x₁ + 2x₂ - x₃ - M(5 - 3x₁ - 3x₂ - 4x₃) .

При составлении первой симплекс-таблицы (табл. 1) будем полагать, что исходные переменные x₁, x₂ , x₃ являются небазисными, а введенные искусственные переменные – базисными. В задачах максимизации знак коэффициентов при небазисных переменных в F- и M-строках изменяется на противоположный. Знак постоянной величины в M-строке не изменяется. Оптимизация проводится сначала по M-строке. Выбор ведущих столбца и строки, все симплексные преобразования при испльзовании метода искусственного базиса осуществляются как в обычном симплекс-методе.

Максимальный по абсолютному значению отрицательный коэффициент (-4) определяет ведущий столбец и переменную x₃, которая перейдет в базис. Минимальное симплексное отношение (2/3) соответствует второй строке таблицы, следовательно, переменная R₂ должна быть из базиса исключена. Ведущий элемент обведен контуром.

В методе искусственного базиса искусственные переменные, исключенные из базиса, в него больше не возвращаются, поэтому столбцы элементов таких переменных опускаются. Табл. 2. сократилась на 1 столбец. Осуществляя пересчет этой таблицы, переходим к табл. 3., в которой строка M обнулилась, ее можно убрать. После исключения из базиса всех искусственных переменных получаем допустимое базисное решение исходной задачи, которое в рассматриваемом примере является оптимальным:

x₁=0; x₂=7/9; F_max=8/9.

Если при устранении M-строки решение не является оптимальным, то процедура оптимизации продолжается и выполняется обычным симплекс-методом