Алгоритм поиска опорного и оптимального решения

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

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

(5.1)

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

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

Это решение может быть допустимым или недопустимым. Оно допустимо, если все свободные члены β_k+1, β_k+2,…, β_n неотрицательны. Предположим, что это условие выполнено. Тогда мы получили опорное решение. Но является ли оно оптимальным? Может быть да, а может быть и нет. Чтобы проверить это, выразим максимизируемую линейную функцию L через свободные переменные х₁,х₂,…,х _k:

(5.2)

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

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

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

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

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

Здесь свободный член β_i ≥ 0, а коэффициент α_i1 отрицателен. Легко понять, что если мы оставим х₂=…=х_k=0, то х₁ мы можем увеличивать только до значения, равного - β_i/ α_i1 , а при дальнейшем увеличении х₁ переменная х_i станет отрицательной.

Выберем ту из перемeнных х_k+1,х_k+2,…,х_n, которая раньше всех обратится в нуль при увеличении х₁, т.е. ту, для которой величина - β_i/ α_i1 меньше всего. Пусть такая «наиболее угрожаемая» переменная будет х_r. Тогда имеет смысл «переразрешить» систему уравнений (5.1) относительно других базисных переменных, выведя из числа свободных переменных х₁ и переводя вместо нее в группу свободных переменных х_r. Действительно, мы хотим перейти от опорного решения, задаваемого равенством х₁=х₂=….=х_k=0, к опорному решению, в котором уже х₁ ≠0, х₂=….=х_k=х_r=0. Первое опорное решение мы получили, положив равными нулю все прежние свободные переменные х₁,х₂,х_k; второе мы получим, если обратим в нуль все новые свободные переменные х₂,…,х_k,х_r. Базисными переменными при этом будут х_1, х_k+1,…, х_r-1, x_r+1, …, x_n.

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

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

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

(5.3)

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

Решение. Приводя неравенства к стандартному виду (≥0) и вводя добавочные переменные у₁,у₂,у₃, переходим к условиям-равенствам:

(5.4)

Число переменных n=7 на 4 превышает число уравнений m=3. Значит, четыре переменных могут быть выбраны в качестве свободных.

Попробуем выбрать в качестве свободных переменных х₁,х₂,х₃,х₄ и положить их равными нулю. При этом мы сразу получим опорное решение: х₁=х₂=х₃=х₄ = 0; у₁=2;у₂=5;у₃=7.

При этих значениях переменных L=0.

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

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

Посмотрим, какая из этих переменных у₁ или у₂ является наиболее «угрожаемой», какая раньше обратится в нуль при увеличении х₃. Очевидно, у₁: она станет равной нулю при х₃=1, а величина у₂ – только при х₃=5.

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

.

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

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

(5.5)

со свободными переменными х₁,х₂,у₁,х₄ и базисными х₃,у₂,у₃.

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

L= -5х₁+5х₁+х₂-у₁+2

или

L= х₂-у₁+2 (5.6)

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

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

(5.7)

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

L= -3х₁-2у₂+у₁+2х₄+8-у₁+2

или

L= -3х₁- 2у₂-2х₄+ 10. (5.8)

Полагая х₁=у₁=у₂=х₄ =0, получим L=10.

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

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

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

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