6.8. Симплекс-метод

Рассмотрим конкретную задачу линейного программирования, заданную в канонической форме: минимизировать (найти наименьшее значение) линейную форму

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

Признак совместности (теорема Кронекера - Капелли) для системы (42) выполнен. Ее ранг равен трем, число базисных переменных также равно трем, число свободных переменных равно двум. Поэтому предложенную задачу можно решить геометрическим методом, рассматривая плоскость, определяемую двумя свободными переменными. В качестве свободных переменных можно выбрать, например, x₄ и x₅. Мы, однако, откажемся от геометрического решения (читателю рекомендуем поступить иначе!) и найдем решение другим способом. С этой целью выразим в (42) базисные переменные x₁, x₂, x₃ через свободные переменные x₄ и x₅:

Форма F (X) как видно из (41), уже выражена через свободные переменные (в ином случае следовало бы это сделать, т. е. подставить в F (X) вместо базисных неизвестных их выражения через свободные).

В силу ограничений (43) наименьшие допустимые значения свободных неизвестных - это значения, равные нулю: x₄ = 0, x₅ = 0. При этом x₁ = 2, x₂ = 7, x₃ = 2. Тем самым получаем допустимое базисное решение системы (44): X₀ = (2, 7, 2, 0, 0). Из (41) имеем соответствующее значение формы F(X₀) = 3.

Выбор именно нулевых значений свободных переменных, вообще говоря, ничем не оправдан. Проверим, нельзя ли добиться уменьшения значения формы F (X) за счет увеличения значений x₄ и x₅. Из выражения (41) видно, что поскольку неизвестная x₅ входит с положительным коэффициентом, то ее увеличение вызовет лишь увеличение формы. В то же время неизвестная x₄ входит в (41) с отрицательным коэффициентом, и потому ее увеличение сопровождается уменьшением формы F(X). Однако для неограниченного возрастания x₄ может быть препятствие. Ведь при этом меняются значения базисных переменных x₁, x₂, x₃. Может случиться так, что базисные переменные станут отрицательными, т. е. возникнут недопустимые решения. И действительно, из первого уравнения (44) следует, что переменная x₁ станет отрицательной при x₄, большем двух (за свободной переменной x₅ по-прежнему сохраняем значение, равное нулю). Одновременно с этим из второго и третьего уравнений (44) получаем, что при изменении x₄ от нуля до двух неизвестная x₂ хотя и убывает, но остается положительной, а неизвестная x₃ возрастает. Следовательно, более целесообразно придать x₄ значение x₄ = 2 (вместо x₄ = 0). При этом окажется, что x₁ = 0, x₂ = 3, x₃ = 4, x₄ = 2, x₅ = 0. Тем самым возникло новое допустимое базисное решение X₁ = (0, 3, 4, 2, 0), в котором роль свободных неизвестных играют x₁ и x₅. Непосредственно подсчитываем, что F(X₁) = 1. Это, как и ожидалось, меньше, чем F (X₀) = 3.

Все же мы на этом не остановимся, а подсчитаем выражения новых базисных переменных x₂, x₃, x₄ и формы F (X) через новый набор x₁, x₅ свободных неизвестных. С этой целью выразим из первого уравнения (44) x₄ через x₁ и x₅; получим: x₄ = 2 - x₁ - x₅. Подставляя это выражение в остальные два Уравнения (44), найдем

Проведем теперь рассуждения, аналогичные предыдущим, в отношении формы (46). Очевидно, что всякое увеличение свободных неизвестных x₁, x₅ по сравнению с нулевыми значениями вызовет лишь увеличение формы (46). Следовательно, решение X₁ уже является оптимальным и доставляет наименьшее значение форме F(X₁) = 1 = minF(X).

Рассмотрим еще одну задачу и найдем ее решение симплекс-методом.