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

                                                                                                         (8)

 

……………

 

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

                                                                      (9) 

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

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

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

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

                                                              (10) 

           Здесь свободный член β_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. Тогда имеет смысл разрешить систему уравнений (8) относительно других базисных переменных, исключаяиз числа свободных переменных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.

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

 
                                                                           (11) 
                                                 

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

                                        Z=5x₁ - 2x₃             

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

 
                                                                                         (11)       

              Число переменных (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₃. Из выражений (11) видно, что в y₁ и y₂ переменная x₃ входит с отрицательным коэффициентом, значит, при увеличении x₃ соответствующие переменные могут стать отрицательными. 
          Определим, какая из этих переменных (y₁ или y₂) раньше обратится в нуль при увеличении x₃ Очевидно, что это y₁ она станет равной нулю при x₃=1, а величина y₂ только при x₃= 5.                                              

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

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

 

                                                                     (12) 
 

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

           Положим теперь свободные переменные равными нулю. Функция приобретает значение Z=-2, что меньше (лучше), чем прежнее значение Z= 0. 
          Это решение все еще не оптимально, так как коэффициент при x₂ в выражении (13) отрицателен, и переменная x₂ может быть увеличена. Это увеличение, как это видно из системы (12), может сделать отрицательной y₂ (в первое уравнение x₂ входит с положительным коэффициентом, а в третьем отсутствует).                                                             

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

 

                                                                       (13)

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

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

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

                                    (15)

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

                                                                                                          (16)                      

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

        

      

       2.4 Двойственный симплекс-метод                     

         Двойственный симплекс-метод, как и симплекс-метод, используется при нахождении решения задачи линейного программирования, записанной в форме основной задачи, для которой среди векторов , составленных из коэффициентов при неизвестных в системе уравнений, имеется m единичных. Вместе с тем двойственный симплекс–метод можно применять при решении задачи линейного программирования, свободные члены системы уравнений которой могут быть любыми числами (при решении задачи симплексным методом эти числа предполагались неотрицательными). Такую задачу и рассмотрим теперь, предварительно предположив, что единичными являются векторы P₁, P₂,…, P_m, т. е. рассмотрим задачу, состоящую в определении максимального значения функции.

                                                                              (17)                    

                                                     при условиях

                                  (18)

                                                                                                   (19)

Где

и среди чисел  имеются отрицательные.

           В  данном случае  есть решение системы линейных уравнений (18). Однако это решение не является планом задачи (17) – (19), так как среди его компонент имеются отрицательные числа.   

          Поскольку векторы  P₁,P₂,…,P_m,– единичные, каждый из векторов  можно представить в виде линейной комбинации данных векторов, причем коэффициентами разложения векторов P_j по векторам P₁,P₂,…,P_m служат числа  .Таким образом, можно найти

 

Определение

Решение  системы линейных уравнений (18), определяемое базисом P₁,P₂,…,P_m, называется п севдопланом задачи (17) – (19), если  для любого  .

Теорема 1

            Если в псевдоплане                     , определяемом базисом  P₁,P₂,…,P_m, есть хотя бы одно отрицательное число b_i<0 такое, что все , то задача (17) – (19)) вообще не имеет планов.

Теорема 2

         Если в псевдоплане  X=(b₁;b₂;…;b_m;0;…;0), определяемом                  базисом P₁,P₂,P₃, имеются отрицательные числа  b_i такие, что для любого из них существуют числа a_ij<0, то можно перейти к новому псевдоплану, при котором значение целевой функции задачи (17) – (19) не уменьшится.        

         Сформулированные  теоремы дают основание для  построения алгоритма двойственного  симплекс-метода.

          Итак, продолжим  рассмотрение задачи (17) – (19). Пусть  – псевдоплан этой задачи. На основе исходных данных составляют симплекс-таблицу (табл. 1), в которой некоторые элементы столбца вектора  P₀ являются отрицательными числами. Если таких чисел нет, то в симплекс-таблице записан оптимальный план задачи (17) – (19), поскольку, по предположению, все . Поэтому для определения оптимального плана задачи при условии, что онo существует, следует произвести упорядоченный переход от одной симплекс–таблицы к другой до тех пор, пока из столбца вектора P₀ не будут исключены отрицательные элементы. При этом все время должны оставаться неотрицательными все элементы (т +1)–й строки, т.е.  для любого .

Таким образом, после составления  симплекс-таблицы проверяют, имеются  ли в столбце вектора P₀ отрицательные числа. Если их нет, то найден оптимальный план исходной задачи. Если же они имеются (что мы и предполагаем), то выбирают наибольшее по абсолютной величине отрицательное число. В том случае, когда таких чисел несколько, берут какое–нибудь одно из них: пусть это число b_l . Выбор этого числа определяет вектор, исключаемый из базиса, т. е. в данном случае из базиса выводится вектор P_l. Чтобы определить, какой вектор следует ввести в базис, находим , где .