Двойственный симплекс-метод (р-метод)

Пример 3.5. Рассмотрим следующую ЗЛП:

min(2Х₁ + 4Х₂)

3 Х₁ + Х₂ 3

4 Х₁ + 3 Х₂ 6 (3.36)

Х₁ + 2 Х₂ 3

Х_1,2 0

Приведем рассматриваемую ЗЛП к каноническому виду

max (-2 Х₁ -4 Х₂)

3 Х₁ + Х₂ - S₁ = 3

4 Х₁ + 3 Х₂ - S₂ = 6

Х₁ + 2 Х₂ - S₃ = 3

или

max (-2 Х₁ -4 Х₂)

- 3 Х₁ - Х₂ + S₁ = - 3

- 4 Х₁ - 3 Х₂ + S₂ = - 6 (3.37)

Х₁ + 2 Х₂+ S₃ = 3

Рассмотрим расширенную матрицу системы линейных уравнений (3.37):

Матрица содержит единичную подматрицу порядка 3 и, следовательно, определяет базисное решение

= (-3; -6; 3); = (3; 4; 5)

системы уравнений, причем =(0,0,0). Так как элементы (n + 1 = 6)-го столбца матрицы системы не являются неотрицательными, то она не является К-матрицей ЗЛП. Вычислим симплекс-разности матрицы :

,

Так как все симплекс-разности матрицы являются неотрицательными, то базисное решение = (-3; -6; 3) не являющееся допустимым решением ЗЛП, является «лучшим», чем оптимальное решение.

При решении задачи симплекс-методом текущее базисное решение является допустимым, но неоптимальным. Эти соображения позволяют построить метод решения определенного класса ЗЛП. В этом методе, называемом двойственным симплекс-методом, на каждой итерации обеспечивается выполнение условия оптимальности текущего базисного решения, не являющегося допустимым. Критерием окончания процесса итераций является получение допустимого решения.