§4. Решение задачи лп двухфазным симплекс-методом

Двухфазный симплекс-метод (или. метод искусственного базиса) применяется в тех случаях, когда и задаче ЛП в канонической форме затруднительно определить н.д.б.р. с помощью эквивалентных преобразований (привести систему ограничений к диагональному виду).

Пример 7.Следующую задачу ЛП решить двухфазным симплекс-методом:

minf(x)=x1-x2+1 (13)

при ограничениях

(14)

x₁, x₂, x₃≥0 (15)

Первая фаза (цель: при- помощи искусственного базиса и симплекс-метода определить базисные переменные из числа исходных переменных).

В систему (14)вводим искусственные переменныеx₃≥0,x₅≥0,x₆≥0 (предварительно умножив обе части второго неравенства на -1),новую целевую функцию как сумму всех искусственных переменных, а старую присоединяем к ограничениям:

minz(x) =x₄ +x₅ +x₆ (16)

при ограничениях

(17)

Искусственные переменные x₄,x₅,x₆выбираем в качестве базисных, а все остальныеx₁,x₂,x₃ -небазисных. По правилу симплекс-метода исключаем базисные переменные из целевой функции (16)(при помощи уравнений системы (17), содержащих эти переменные):

z(x)= -2x₁- 15x₂- 5x₃+ 15

или, что все равно

z(x)+2x₁+15 x₂+5 x₃=15 (19)

Начальное д.б.р.

x⁰=(x₁⁰,x₂⁰,x₃⁰,x₄⁰,x₅⁰,x₆⁰)=(0, 0, 0, 1, 3,11)

называется искусственным базисом. При помощи этого базиса, и выражений (19), (17)строим начальную симплекс-таблицуI-ой фазы.

		x1	x2	x3	x4	x5	x6
z	15	2	15	5	0	0	0
f	1	-1	1	0	0	0	0
x4	1	2	(1)	3	1	0	0
x5	3	-1	3	-1	0	1	0
x3	11	1	11	3	0	0	1

До конца Iфазы роль нулевой строки играет строка для z,все остальное как в симплекс-методе (см. примеры 5,6).Следует только заметить, что строка для fне участвует в выборе ведущей строки.

Из (16)видно, чтоminz(x) = 0и достигается приx₄=x₅ =x₆=0,те, задача (16)-(18) будет решена, если все искусственные переменные будут вытеснены из базиса, а z=0.Это и будет означать конец первой фазы и переход ко второй фазе.

Обратите внимание, что в первой таблице ведущей может быть любая из последних трех строк (предвестник зацикливания). В таких случаях можно выбрать любой из них -выберем первую строку. Так как искусственная переменнаяx₄выходит из базиса, то соответствующий столбик в дальнейшем можно исключить. В результате соответствующих преобразований получим вторую симплекс-таблицу.

		x1	x2	x3	x4	x5
z	0	-28	0	-40	0	0
f	0	-3	0	-3	0	0
x2	1	2	1	3	1	0
x5	0	-7	0	-10	0	1
x6	0	-21	0	-30	0	0

Из таблицы следует, что minzдостигнут, однако искусственные переменныеx₅иx₆еще не выведены из базиса. В такой ситуации правила симплекс-метода "не работают" (т.к. ввиду отсутствия в нулевой строке положительных оценок нельзя выбрать ведущий столбик). Задача здесь одна - вывести оставшиеся искусственные переменные из базиса. Выведем сначалаx₅. Умножим все элементы этой строки на -1(что допустимо, т.к. в нулевом столбике стоит 0).Введем в базис вместоx₅переменнуюx₁. С этой целью строку для x₅ поделим на 7и с "ведущим элементом" 1выполним элементарные преобразования (как в симплекс-методе). В результате получим таблицу:

		x1	x2	x3	x6
z	0	0	0	0	0
f	0	0	0	9/7	0
x2	1	0	1	1/7	0
x1	0	1	0	10/7	0
x6	0	0	0	0	1

Остается в базисе еще x₆. Ее из числа базисных вывести нельзя, так как все элементы таблицы равны нулю, кроме 1в столбике дляx₆. Это говорит о том, что в системе (14)третье уравнение было "лишним" и потому последнюю строку таблицы можно вычеркнуть. Действительно, третье уравнение в (14)является линейной комбинацией первых двух (оно получается вычитанием второго уравнения, умноженного на 3,из первого уравнения, умноженного на 2),

Вычеркивая столбик для x₆ и строку дляzприходим к таблице,

		x1	x2	x3
f	0	0	0	9/7
x2	1	0	1	1/7
x1	0	1	0	10/7

содержащей только элементы исходной задачи (13)-(15)и с базисными переменными из числа исходных переменных.

Таким образом, задача Iфазы выполнена.

Вторая фаза (цель: применяя обычный симплекс-метод к полученной в результате Iфазы таблице, получить оптимальное решение исходной задачи).

Д.б.р. для последней таблицы есть

x⁰=(0, 1, 0)

Заметим, что это вырожденное д.б.р., так как в нем базисная переменная x₁ - 0.То есть здесь мы можем получить зацикливание.

В качестве упражнения IIфазу предлагается сделать самостоятельно.

Теперь можно привести алгоритм двухфазного симплекс-метода:

1)привести задачу ЛП к канонической форме;

2)ввести в ограничения искусственные переменные и составить новую целевую функциюz;

3)исключить из новой целевой функции все искусственные переменные;

4)используя искусственные переменные в качестве базисных, построить начальную симплекс-таблицу;

5)использовать симплекс-метод, исключая из таблиц столбики для искусственных переменных по мере их выхода из базиса до тех пор, покаminz=0 и все искусственные переменные не будут выведены из базиса;

6)вычеркнуть строчку для zи перейти ко второй фазе;

7)во второй фазе, к таблице, полученной в результате первой фазы, применить симплекс-метод до тех пор, пока не найдется оптимальное решение исходной задачи или не выявится его отсутствие.

П р и м е ч а н и як двухфазному симплекс-методу

1.Если в результате первой фазы окажется, чтоminz > 0,то система ограничений исходной задачи (в канонической форме) несовместна. Во всех остальных случаях первая фаза разрешима.

2.Еслиminz= 0и в таблице остались искусственные переменные, то, используя элементарные преобразования, эти переменные следует вывести из числа базисных, а вместо них ввести исходные переменные (см. пример 7).

3.Пусть каноническая форма задачи ЛП получена с помощью слабых переменных. Применение двухфазного симплекс-метода упростится, если искусственные переменные ввести только в те ограничения, ж которых слабая переменная либо отсутствует (исходное ограничение-равенство), либо не может войти в базис (введена в ограничение со знаком минус).