Симплекс-метод решения задачи линейного программирования

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

Идея симплекс-метода относительно проста. Пусть в задаче линейного программирования имеется в переменных и независимых линейных ограничений, заданных в форме уравнений. Мы знаем, что оптимальное решение (если оно существует) достигается в одной из опорных точек (вершин ОДР), где по крайней мере из переменных равны нулю. Выберем какие-то k переменных в качестве свободных и выразим через них остальные базисных переменных. Пусть, например, в качестве свободных выбраны первые переменных а остальные выражены через них:

Попробуем, что будет, если положить все свободные переменные равными нулю:

При этом мы получим:

Это решение может быть допустимым или недопустимым. Оно допустимо, если все свободные члены неотрицательны. Предположим, что это условие выполнено. Тогда мы получили опорное решение. Но является ли оно оптимальным? Может быть да, а может быть и нет. Чтобы проверить это, выразим минимизируемую линейную функцию L через свободные переменные

Очевидно, что при Посмотрим, не можем ли мы улучшить решение, т. е. уменьшить функцию увеличивая какие-нибудь из переменных (уменьшать их мы не можем, так как все они равны нулю, а отрицательные значения переменных недопустимы). Если все коэффициенты в формуле (5.2) положительны, то, увеличивая какие-то из переменных сверх нуля, мы не можем уменьшить L; следовательно, найденное нами опорное решение является оптимальным. Если же среди коэффициентов формуле (5.2) есть отрицательные, то, увеличивая некоторые из переменных, а именно — те, коэффициенты при которых отрицательны, мы можем улучшить решение, т. е. уменьшить

Пусть, например, коэффициент в формуле (5.2) отрицателен. Значит, есть смысл увеличить т. е. перейти от данного опорного решения к другому, где переменная не равна нулю, а вместо нее равна нулю какая-то другая. Увеличение «полезно» для линейной функции L, делает ее меньше. Однако увеличивать надо осторожно, так чтобы не стали отрицательными другие переменные выраженные через свободные переменные, в частности, через формулами (5.1).

Посмотрим, опасно ли для переменных увеличение т. е. может ли оно сделать их отрицательными? Да, опасно, если коэффициент при в соответствующем уравнении отрицателен. Если среди уравнений (5.1) нет уравнения с отрицательным коэффициентом при то величину можно увеличивать беспредельно, а, значит, линейная функция L не ограничена снизу и оптимального решения ОЗЛП не существует.

Допустим, что это не так и что среди уравнений (5.1) есть такие, в которых коэффициент при отрицателен. Для переменных, стоящих в левых частях этих уравнений, увеличение опасно — оно может сделать их отрицательными.

Возьмем одну из таких переменных и посмотрим, до какой степени можно все же увеличить пока переменная не станет отрицательной? Выпишем уравнение из системы (5.1):

Здесь свободный член а коэффициент отрицателен. Легко понять, что если мы оставим, то мы можем увеличивать только до значения, равного —, а при дальнейшем увеличении переменная станет отрицательной.

Выберем ту из переменных которая раньше всех обратится в нуль при увеличении т. е. ту, для которой величина — меньше всего. Пусть такая «наиболее угрожаемая» переменная будет Тогда имеет смысл «переразрешить» систему уравнений (5.1) относительно других базисных переменных, выведя из числа свободных переменных и переведя вместо нее в группу свободных переменных. Действительно, мы хотим перейти от опорного решения, задаваемого равенствами к опорному решению, в котором уже Первое опорное решение мы получили, положив равными нулю все прежние свободные переменные второе мы получим, если обратим в нуль все новые свободные переменные. Базисными переменными при этом будут

Предположим, что уравнения типа (5.1) для нового набора базисных и свободных переменных составлены. Тогда можно выразить через новые свободные переменные и линейную функцию L. Если все коэффициенты при переменных в этой формуле положительны, то мы нашли оптимальное решение: оно получится, если все свободные переменные положить равными нулю. Если среди коэффициентов при переменных есть отрицательные, то процедура улучшения решения продолжается: система вновь переразрешается относительно других базисных переменных, и так далее, пока не будет найдено оптимальное решение, обращающее функцию L в минимум.

Проследим описанную процедуру постепенного улучшения решения ОЗЛП на конкретном примере.

Пример Имеется задача линейного программирования с ограничениями-неравенствами:

Требуется минимизировать линейную функцию

Решение. Приводя неравенства к стандартному виду и вводя добавочные переменные переходим к условиям-равенствам:

Число пёременны на 4 превышает число уравнений Значит, четыре переменных могут быть выбраны в качестве свободных

Попробуем выбрать в качестве свободных переменных и положить их равными нулю. При этом мы сразу получим опорное решение:

При этих значениях переменных

Посмотрим, является ли это решение оптимальным? Нет! Потому что в выражении линейной функции L коэффициент при отрицателен. Значит, увеличивая 3, можно уменьшить

Попробуем увеличивать 3. Проследим по уравнениям (5.4), опасно ли это для других переменных? Да, опасно для — в оба эти уравнения переменная 8 входит с отрицательным коэффициентом, значит, при увеличении 3 соответствующие переменные могут стать отрицательными.

Посмотрим, какая из этих переменных или является наиболее «угрожаемой», какая раньше обратится в нуль при увеличениих. Очевидно, что она станет равной нулю при а величина -только при

Поэтому выбираем переменную и вводим ее в число свободных вместо 3. Чтобы «переразрешить» систему (5.4) относительно поступим следующим образом. Разрешим первое уравнение (5.4) относительно новой базисной переменной

Это выражение подставим вместо во второе уравнение; получим

Что касается третьего уравнения, то оно, как не содержащее не изменится. Итак, мы привели систему (5.4) к виду:

со свободными переменными и базисными

Выразим линейную функцию L через новые свободные переменные:

или

Положим теперь свободные переменные равными нулю. Линейная функция L станет равной —2. Это уже лучше, чем прежнее значение Но является ли это решение оптимальным? Все еще нет, так как коэффициент при 2 в выражении (5.6) отрицателен. Итак, будем увеличивать 2. Посмотрим, для какой из переменных, стоящих в левых частях системы (5.5), это может быть «опасно». Только для (в первое уравнение входит с положительным коэффициентом, а в третье совсем не входит).

Итак, обменяем местами переменные 2 и — первую выведем из числа свободных, а вторую — введем. Для этого разрешим второе уравнение (5.5) относительно 2 и подставим это 2 в первое уравнение. Получим еще один вид системы (5.4):

Выразим L через новые свободные переменные:

или

Полагая, получим

Является ли это решение оптимальным? На этот раз — да, так как коэффициенты при всех свободных переменных в выражении (5.8) неотрицательны.

Итак, оптимальное решение ОЗЛП найдено:

При таких значениях переменных линейная функция L принимает минимальное значение:

Заметим, что в рассмотренном примере нам не пришлось искать опорного решения: оно сразу же получилось, когда мы положили свободные переменные равными нулю. Это объясняется тем, что в уравнениях (5.4) все свободные члены были неотрицательны и, значит, первое же попавшееся решение оказалось опорным. Если это окажется не так, можно будет прийти к опорному решению с помощью такой же процедуры обмена местами некоторых базисных и свободных переменных, переразрешая уравнения до тех пор, пока свободные члены не станут неотрицательными. Как это делается, мы увидим в дальнейшем (см. § 7).