Симплексный метод решения ЗЛП

     Предположим, что все свободные переменныеx₁, x₂,…,x_kравны нулю.

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

      x_k+1=β_k+1;

     x_k+2=β_k+2;

           …….. (2.2)

     X_n=β_n

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

           Z=γ₀+γ₁x₁+γ₂x₂+…+γ_kx_k (2.3) 

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

     Пусть, например, коэффициентγ₁в (2.3) отрицателен. Значит, есть смысл увеличитьx₁, т. е. перейти от данного опорного решения к другому, где переменнаяx₁не равна нулю, а вместо нее равна нулю какая-то другая. Однако увеличиватьx₁следует с осторожностью, так чтобы не стали отрицательными другие переменныеx_k+1, x_k+2,…,x_nвыраженные через свободные переменные, в частности черезx₁формулами (2.2).

     Например, если коэффициент приx₁в соответствующемx_jуравнении (2.2) отрицателен, то увеличениеx₁может сделатьx_jотрицательным. Наоборот, если среди уравнений (2.2) нет уравнения с отрицательным коэффициентом приx₁то величинуx₁можно увеличивать беспредельно, а, значит, линейная функция Z не ограничена снизу и оптимального решения ОЗ не существует.

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

     Возьмем одну из таких переменныхx_lи посмотрим, до какой степени можно увеличитьx₁, пока переменнаяx_lне станет отрицательной. Выпишемl-eуравнение из системы (2.2): 

           x_l=α_l1x₁+α_l2x₂+…+α_lkx_k+β_l (2.4) 

     Здесь свободный членβ_l≥0, а коэффициентα_l1отрицателен.

     Легко понять, что если мы оставимx₂=x₃=…=x_k=0, тоx_kможно увеличивать только до значения, равного–β_l/α_l1,а при дальнейшем увеличенииx₁переменнаяx₁станет отрицательной.

     Выберем ту из переменныхx_k+1,x_k+2,…,x_n, которая раньше всех обратится в нуль при увеличении x₁, т. е. ту, для которой величина–β_l/α_l1 наименьшая. Пусть это будетx_r. Тогда имеет смысл разрешить систему уравнений (2.2) относительно других базисных переменных, исключаяиз числа свободных переменныхx₁и переводя вместо нее в группу свободных переменныхx_r. Действительно, мы хотим перейти от опорного решения, задаваемого равенствамиx₁=x₂=…=x_n=0 к опорному решению, в котором ужеx₁≠0, аx₂=…=x_k=x_r=0. Первое опорное решение мы получили, положив равными нулю все прежние свободные переменныеx₁,x₂,…,x_kвторое мы получим, если обратим в нуль все новые свободные переменныеx₂,x₃,…,x_k,x_r.

     Базисными переменными при этом будутx_l,x_k+1,x_k+2,…,x_r-1, x_r-1,…,x_r.

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

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

     

     -5x₁-x₂+2x₃≤2;

           -x₁+x₃+x₄≤5; (2.5)

     -3x₁+5x₄≤7. 

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

     Z=5x₁-2x₃

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

     

     y₁=5x₁+x₂-2x₃+2

           y₂=x₁-x₃-x₄+5 (2.5)

     y₃=3x₁-5x₄+7 

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

     Пусть в качестве свободных переменных выступаютx₁,x₂,x₃,x₄. Положим их равными нулю и получим опорное решение: 

     x₁=x₂=x₃=x₄=0;

     y₁=2, y₂=5, y₃=7. 

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

     Это решение не оптимально, поскольку  в линейной функции Z коэффициент  приx₃отрицателен. Значит, увеличиваяx₃можно уменьшить Z.

     Попробуем увеличиватьx₃.Из выражений (2.5) видно, что вy₁и y₂переменнаяx₃входит с отрицательным коэффициентом, значит, при увеличенииx₃соответствующие переменные могут стать отрицательными.

     Определим, какая из этих переменных (y₁илиy₂)раньше обратится в нуль при увеличенииx₃Очевидно, что этоy₁она станет равной нулю приx₃=1, а величинаy₂— только приx₃= 5.

     Выбирается  переменная у, и вводится в число  свободных вместоx₃Чтобы разрешить систему (2.5) относительноx₃, y₂, y₃поступим следующим образом. Разрешим первое уравнение (2.5) относительно новой базисной переменнойx₃: 

     x₃=5/2*x₁+1/2*x₂-1/2*y₁+1

     Это выражение подставляется вместоx₃во второе уравнение: 

      x₃=5/2*x₁+1/2*x₂-1/2y₁+1;

           y₂=-3/2*x₁-1/2*x₂+1/2*y₁-x₄+4; (2.6)

     y₃=3x₁-5x₄+7. 

     Что касается третьего уравнения, то оно, как  не содержащееx₃не изменится. Система (2.2) приведена к виду со свободными переменнымиx₁, x₂, y₁, x₄и базиснымиx₃, y₂, y₃.

     Положим теперь свободные переменные равными  нулю. Функция приобретает значение Z=-2, что меньше (лучше), чем прежнее  значение Z= 0.

     Это решение все еще не оптимально, так как коэффициент приx₂в выражении (2.7) отрицателен, и переменнаяx₂может быть увеличена. Это увеличение, как это видно из системы (2.6), может сделать отрицательнойy₂(в первое уравнениеx₂входит с положительным коэффициентом, а в третьем — отсутствует).

     Поменяем  местами переменныеx₂ и y₂— первую исключим

     из  числа свободных, а вторую — включим. Для этого разрешим второе уравнение (2.6) относительноx₂и подставимx₂в первое уравнение. Получим следующий вид системы (2.5): 

      x₃=x₁-y₂-x₄+5

           y₂=-3x₁-2y₂+y₁-2x₄+8  (2.7)

     y₃=3x₁-5x₄+7 

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

           Z=3x₁+2y₂-y₁+2x₄-8+y₁-2=3x₁+2y₂+2x₄-10 (2.8)

     Полагаяx₁=y₁=y₂=x₄=0 , получим Z = -10.

     Это решение является оптимальным, так  как коэффициенты при всех свободных переменных в выражении (2.8) неотрицательны. Итак, оптимальное решение ОЗ найдено (2.9):

           x₁^*=0, x₂^*=8, x₃^*=5, x₄^*=0, y₁^*=0, y₂^*=0, y₃^*=7. (2.9)

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

           Z_min=-10 (2.10) 

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

     2.4 Двойственная задача 

     Использование идей двойственности в сочетании с общей идеей симплекс-метода позволило разработать еще один метод решения задач ЛП - двойственный симплекс-метод. Впервые этот метод был предложен Лемке в 1954г. Решение задачи ЛП двойственным симплекс-методом сводится к отысканию оптимального плана прямой задачи последовательным переходом от одного базиса к другому.

     Задача ЛП в канонической форме имеет вид:  
максимизировать L(x) = сумма от j=1 до n (сjчj) 
при условиях: 
сумма от j=1 до n (аjXj)=bv, (v=1,2,....m) 
или 
сумма от j=1 до n (АjXj)=b, xj>=0,  j=1,2,...n

     Составим двойственную задачу по условиям прямой задачи и определим области допустимых решений ДП:  
Прямая задача Двойственная задача

      
maxZ=x₁-3x₃-3x₄-MR₁-MR₂

     y₁: x₁+2x₃-2x₄+x₅=4

     y₂: 3x₁-4x₃+4x₄+R₁=11

     y₃: x₁+x₃-x₄-x₆+R₂=0

     minW=4y₁+12y₂

     x₁: y₁+3y₂+y₃≥1

     x₃: 2y₁-4y₂+y₃≥-3

     -2y₁+4y₂-y₃≤3(1)

     X₄: -2y₁+4y₂-y₃≥3  (2)

     X₅: y₁≥0

     X₆: -y₃≥0 => y₃≤0

     R₁: y₂≥-M

     R₂: y₃≥-M 
Итак, получено: y₁≥0,y₂≤≥0 ,y₃≤0. 

      
2. Приведём запись двойственной задачи к канонической форме. На основании полученных ОДР двойственных переменных введём необходимые подстановки:y₂=y₄-y₅; y₃=-ỹ_3; ỹ₃,y₄,y₅≥0 
Для удобства решения свернём ограничения (1) и (2) в одно со знаком равенства, а также введем в ограничения и целевую функцию избыточные, остаточные и искусственные переменные.  

     minW=4y₁+12y₄-12y₅+MR₁+MR₂

     y₁+3y₄-3y₅-ỹ₃-y₆+R₁=1  (3)

     -2y₁+4y₄-4y₅+ỹ₃+R₂=3  (4)

      
3. Решим ДЗ симплекс методом:  
Из (3) выразим: R₁=1-y₁-3y₄+3y₅+ỹ₃+y₆ 
Из (4) выразим:R₂=3+2y₁-4y₄+4y₅-ỹ₃

     W+y₁(-4-M)+y₄(-12+7M)+y₅(12-7M)-My₆=4M 

     Создаём симплекс-таблицы: 

      Таблица 2.2 – симплекс-таблица №1