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

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

min(2Х₁ + 4Х₂)

3 Х₁ + Х₂ 3

4 Х₁ + 3 Х₂ 6 (2.77)

Х₁ + 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 (2.78)

Х₁ + 2 Х₂+ S₃ = 3

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

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

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

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

,

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

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