Геометрическая интерпретация, которой мы пользовались при решении задач линейного программирования, перестает быть пригодной для этой цели при числе свободных переменных n-m , а затруднительна уже при n-m=3. Для нахождения решения задачи линейного программирования в общем случае (при произвольном числе свободных переменных) применяются не геометрические, а вычислительные методы. Из них наиболее универсальным является так называемый симплекс-метод.
Идея симплекс-метода относительно проста. Пусть в задаче линейного программирования иметься n переменных и m независимых линейных ограничений, заданных в форме уравнений. Мы знаем, что оптимальное решение (если оно существует) достигается в одной из опорных точек (вершин ОДР), где, по крайней мере, k=n-m из переменных равны нулю. Выберем какие-то переменных в качестве свободных и выразим через них остальные m базисных переменных. Пусть, например, в качестве свободных выбраны первые k=n-m переменных х1,х2,…,хk, а остальные m выражены через них:
(5.1)
Попробуем, что будет, если положить все свободные переменные х1,х2,…,хk равными нулю:
При этом мы получим:
Это решение может быть допустимым или недопустимым. Оно допустимо, если все свободные члены βk+1, βk+2,…, βn неотрицательны. Предположим, что это условие выполнено. Тогда мы получили опорное решение. Но является ли оно оптимальным? Может быть да, а может быть и нет. Чтобы проверить это, выразим максимизируемую линейную функцию L через свободные переменные х1,х2,…,х k:
(5.2)
Очевидно, что при х1=х2=….=хk=0, L=γ0. Посмотрим, не можем ли мы улучшить решение, т.е. увеличить функцию L, увеличивая какие-нибудь из переменных х1,х2,…,х k (уменьшить мы их не можем, так как все они равны нулю, а отрицательные значения переменных недопустимы). Если все коэффициенты γ1, γ2, …, γk в формуле (5.2) отрицательны, то, увеличивая какие-то из переменных х1,х2,…,х k сверх нуля, мы не можем увеличить L; следовательно, найденное нами опорное решение является оптимальным. Если же среди коэффициентов γ1, γ2, …, γk в формуле (5.2) есть положительные, то, увеличивая некоторые из переменных х1,х2,…,х k, а именно – те, коэффициенты при которых положительны, мы можем улучшить решение, т.е. увеличить L.
Пусть, например, коэффициент γ1 в формуле (5.2) положителен Значит, есть смысл увеличить х1, т.е. перейти от данного опорного решения к другому, где переменная х1 не равна нулю, а вместо нее равна нулю какая-то другая. Увеличение х1 «полезно» для линейной функции L, делает ее больше. Однако увеличивать х1 надо осторожно, так чтобы не стали отрицательными другие переменные хk+1,хk+2,…,хn, выраженные через свободные переменные, в частности, через х1 формулами (5.1).
Посмотрим, опасно ли для переменных хk+1,хk+2,…,хn увеличение х1, т.е. может ли оно сделать их отрицательными? Да, опасно, если коэффициент при х1 в соответствующем уравнении отрицателен. Если среди уравнений (5.1) нет уравнения с отрицательным коэффициентом при х1, то величину х1 можно увеличивать беспредельно, а, значит, линейная функция L не ограничена сверху и оптимального решения ОЗЛП не существует.
Допустим, что это не так и среди уравнений (5.1) есть такие, в которых коэффициент при х1 отрицателен. Для переменных, стоящих в левых частях этих уравнений, увеличение х1 опасно – оно может сделать их отрицательными.
Возьмем одну из таких переменных хi и посмотрим, до какой степени можно все же увеличить х1 пока переменная хi не станет отрицательной? Выпишем -е уравнение из системы (5.1):
Здесь свободный член βi ≥ 0, а коэффициент αi1 отрицателен. Легко понять, что если мы оставим х2=…=хk=0, то х1 мы можем увеличивать только до значения, равного - βi/ αi1 , а при дальнейшем увеличении х1 переменная хi станет отрицательной.
Выберем ту из перемeнных хk+1,хk+2,…,хn , которая раньше всех обратится в нуль при увеличении х1, т.е. ту, для которой величина - βi/ αi1 меньше всего. Пусть такая «наиболее угрожаемая» переменная будет хr . Тогда имеет смысл «переразрешить» систему уравнений (5.1) относительно других базисных переменных, выведя из числа свободных переменных х1 и переводя вместо нее в группу свободных переменных хr . Действительно, мы хотим перейти от опорного решения, задаваемого равенством х1=х2=….=хk=0 , к опорному решению, в котором уже х1≠0, х2=….=хk=хr=0. Первое опорное решение мы получили, положив равными нулю все прежние свободные переменные х1,х2,хk; второе мы получим, если обратим в нуль все новые свободные переменные х2,…,хk,хr. Базисными переменными при этом будут х1, хk+1,…, хr-1, xr+1, …, xn.
Предположим, что уравнения типа (5.1) для нового набора базисных и свободных переменных составлены. Тогда можно выразить через новые свободные переменные и линейную функцию L. Если все коэффициенты при переменных в этой формуле отрицательные, то мы нашли оптимальное решение: оно получится, если все свободные переменные положить равными нулю. Если среди коэффициентов при переменных есть положительные, то процедура улучшения решения продолжается: система вновь переразрешается относительно других базисных переменных, и так далее, пока не будет найдено оптимальное решение, обращающее функцию L в максимум.
Проследим описанную процедуру постепенного улучшая решения ОЗЛП на конкретном примере.
Пример. Имеется задача линейного программирования с ограничениями-неравенствами:
(5.3)
Требуется максимизировать линейную функцию
Решение.Приводя неравенства к стандартному виду (≥0) и вводя добавочные переменные у1,у2,у3, переходим к условиям-равенствам:
(5.4)
Число переменных n=7 на 4 превышает число уравнений m=3. Значит, четыре переменных могут быть выбраны в качестве свободных.
Попробуем выбрать в качестве свободных переменных х1,х2,х3,х4 и положить их равными нулю. При этом мы сразу получим опорное решение: х1=х2=х3=х4 = 0; у1=2;у2=5;у3=7.
При этих значениях переменных L=0.
Посмотрим, является ли это решение оптимальным? Нет! Потому что в выражении линейной функции L коэффициент при х3 положителен. Значит, увеличивая х3 , можно увеличить L.
Попробуем увеличить х3 . Проследим по уравнению (5.4), опасно ли это для других переменных? Да, опасно для у1 и у2 – в оба эти уравнения переменная х3 входит с отрицательным коэффициентом, значит, при увеличении х3 соответствующие переменные у1 и у2 могут стать отрицательными.
Посмотрим, какая из этих переменных у1 или у2 является наиболее «угрожаемой», какая раньше обратится в нуль при увеличении х3. Очевидно, у1: она станет равной нулю при х3=1, а величина у2 – только при х3=5.
Поэтому выбираем переменную у1 и вводим ее в число свободных вместо х3. Чтобы «переразрешить» систему (5.4) относительно новой базисной переменной х3:
.
Это выражение подставим вместо х3 во второе уравнение, получим
Что касается третьего уравнения, то оно, как не содержащее х3 не изменится. Итак, мы привели систему (5.4) к виду:
(5.5)
со свободными переменными х1,х2,у1,х4 и базисными х3,у2,у3.
Выразим линейную функцию L через новые свободные переменные:
L= -5х1+5х1+х2-у1+2
или
L= х2-у1+2 (5.6)
Положим теперь свободные переменные равными нулю. Линейная функция L станет равной 2. Это уже лучше, чем прежнее значение L=0. Но является ли это решение оптимальным? Все еще нет, так как коэффициент при х2 в выражении (5.6) положительный. Итак, будем увеличивать х2. Посмотрим, для какой из переменных, стоящих в левых частях системы (5.5) это может быть «опасно». Только для у2 (в первом уравнении х2 входит с положительным коэффициентом, а в третьем совсем не входит).
Итак, обменяем местами переменные х2 и у2 – первую из числа свободных, а вторую – введем. Для этого разрешим второе уравнение (5.5) относительно х2 и подставим это х2 в первое уравнение. Получим еще один вид системы (5.4):
(5.7)
Выразим L через новые свободные переменные:
L= -3х1-2у2+у1+2х4+8-у1+2
или
L= -3х1- 2у2-2х4+ 10. (5.8)
Полагая х1=у1=у2=х4 =0, получим L=10.
Является ли это решение оптимальным? На этот раз – да, так как коэффициенты при всех свободных переменных в выражении (5.8) отрицательны.
Итак, оптимально решение ОЗЛП найдено:
При таких значениях переменных линейная функция L принимает максимальное значение:
Заметим, что в рассмотренном примере нам не пришлось искать опорного решения: оно сразу же получилось, когда мы положили свободные переменные равными нулю. Это объясняется тем, что в уравнениях (5.4) все свободные члены были неотрицательны и, значит, первое же попавшееся решение оказалось опорным. Если же окажется не так, можно будет прийти к опорному решению с помощью такой же процедуры обмена местами некоторых базисных и свободных переменных, переразрешая уравнения до тех пор, пока свободные члены не станут неотрицательными. Как это делается, мы увидим в дальнейшем (смотри параграф 6).
, а затруднительна уже при n-m=3. Для нахождения решения задачи линейного программирования в общем случае (при произвольном числе свободных переменных) применяются не геометрические, а вычислительные методы. Из них наиболее универсальным является так называемый симплекс-метод.
(5.1)
(5.2)
-е уравнение из системы (5.1):
(5.3)
(5.4)
.
(5.5)
(5.7)
