2.3. Симплексный метод решение злп

Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит:

1. умение находить начальный опорный план;

2. наличие признака оптимальности опорного плана;

     Пусть ЗЛП представлена системой ограничений в каноническом виде:     ,    .      Говорят, что ограничение ЗЛП имеет предпочтительный вид, если при неотрицательной правой части   левая часть ограничений содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения равенства - с коэффициентом, равным нулю.      Пусть система ограничений имеет вид    ,              Сведем задачу к каноническому виду. Для этого прибавим к левым частям неравенств дополнительные переменные  (  . Получим систему, эквивалентную исходной:

  ,

Которая имеет предпочтительный вид 

  ).

     В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю .      Пусть далее система ограничений имеет вид

       

     Сведём её к эквивалентной вычитанием дополнительных переменных  (    из левых частей неравенств системы. Получим систему 

  .      Однако теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные   входят в левую часть (при  ) с коэффициентами, равными –1. Поэтому, вообще говоря, базисный план    ) не является допустимым. В этом случае вводится так называемый искусственный базис. К левым частям ограничений-равенств, не имеющих предпочтительного вида, добавляют искусственные переменные  . В целевую функцию переменные   , вводят с коэффициентом М в случае решения задачи на минимум и с коэффициентом - М для задачи на максимум, где М - большое положительное число. Полученная задача называется М-задачей, соответствующей исходной. Она всегда имеет предпочтительный вид.     Пусть исходная ЗЛП имеет вид

    ) ,                      (2.17)               (2.18)        ,                     (2.19)

причём ни одно из ограничений не имеет предпочтительной переменной. М-задача запишется так:

    )                  (2.20)           (                  (2.21)       ,                  (2.22)

     Задача (2.20) - (2.22) имеет предпочтительный план. Её начальный опорный план имеет вид:

  ).

     Если некоторые из уравнений (2.18) имеют предпочтительный вид, то в них не следует вводить искусственные переменные.

     Теорема. Если в оптимальном плане 

     )                  (2.23) 

       М-задачи (2.20) - (2.22) все искусственные переменные    , то план   является оптимальным планом исходной задачи(2.17)-(2.19).      Для того чтобы решить задачу с ограничениями, не имеющими предпочтительного вида, вводят искусственный базис и решают расширенную М - задачу, которая имеет начальный опорный план      ).      Решение исходной задачи симплексным методом путем введения искусственных переменных   называется симплексным методом с искусственным базисом.      Если в результате применения симплексного метода к расширенной задаче получен оптимальный план, в котором все искусственные переменные , то его первые n-компоненты дают оптимальный план исходной задачи.