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

 

На основании материала, рассмотренного выше, можно сделать следующий вывод.

Существует такая угловая точка многогранника решений, в которой линейная функция достигает своего наименьшего (наибольшего) значения. Каждой угловой точке многогранника решений соответствует опорный план. Каждый опорный план определяется системой m линейно независимых векторов, содержащихся в данной системе из n векторов, А1, А2,…, Аn. Для отыскания оптимального плана необходимо исследовать только опорные планы. Верхняя граница количества опорных планов, содержащихся в данной задаче, определяется числом сочетаний Сnm.  При больших m и n найти оптимальный план, перебирая все опорные планы задачи, очень трудно. Поэтому необходимо иметь схему, позволяющую осуществлять упорядоченный переход от одного опорного плана к другому. Такой схемой является симплексный метод, который позволяет, исходя из известного опорного плана задачи, за конечное число шагов получить ее оптимальный план. Каждый из шагов (или итераций) состоит в нахождении нового плана, которому соответствует меньшее значение линейной функции, в чем значение этой же функции в предыдущем плане. Процесс продолжают до получения оптималь-ного плана. Если задача не обладает планами или ее линейная функция не ограничена на многограннике решений, то симплексный метод позволяет установить это в процессе решения.

 

 Построение опорных планов

 

Пусть поставлена задача линейного программирования. Найти минимальное значение функции   Z = C1x1 + C2x2 + ... + Cnxn

при ограничениях

 

                      а11х1 + а12х2 +…+ a1nхn = b1,

                      а21х1 + а22х2 +…+ a2nхn = b2,

                      ..........................................                         xj ≥ 0

                     am1х1 + am2х2 +...+  amnхn= bm ,                         (j=1, 2,..., n),

 

где bi ≥ 0   (i = 1, 2,..., n).

Предположим сначала, что система ограничений задачи содержит m единичных векторов, причем без ограничения общности можно положить, что единичными являются первые m векторов. Тогда необходимо минимизировать линейную функцию

                                    Z = C1x1 + C2x2 +...+ Cnxn                                                       (2.4.1)

при ограничениях

 

                       x1 + a1,m+1 xm+1 +...+ a1nxn = b1,

                       x2 + a2,m+1  xm+1 +...+ a2nxn = b2,                                         (2.4.2)

                          ...........................................

                       xm + a,m,m+1  xm+1 +...+ amnxn = bm,

 

                     xj ≥ 0   (j=1, 2,..., n).                                                          (2.4.3)

        Запишем систему (2.4.2) в векторной форме:

 

x1A1 + x2A2 +...+ xmAm  + xm+1Am+1  +...+ xnAn = A0,                             (2.4.4)

 

где

               1                                             0                                    0

               0                                             1                                    0

 А1=        .         ,                     А2=         .      , … ,        Аm=        .       ,

                .                                            .                                  .      

0                                                  0                                    1

                                                                 

 

 


                     a1,m+1                                              a1n                                                          b1

                     a2,m+1                                             a2n                                                          b2

     Am+1 =               .        , ... ,       An=      .         ,                 A0 =            .             .     

                        .                                    .                                         .

                     am,m+1                                             amn                                                         bm

 

            Векторы А1, А2, …, Аm – линейно независимые единичные векторы m- мерного пространства. Они и образуют базис этого пространства. Поэтому в разложении (2.4.4) за базисные неизвестные выбираем х1, х2, …, хm, свободные неизвестные  хm+1, …, хn приравниваем нулю и, учитывая, что bi ≥ 0 (i=1, 2,...,m), а векторы А1, А2, …, Аm - единичные, получаем первоначальный план:

         X0 = (x1 = b1; x2 = b2; ...; xm = bm; xm+1 = 0; ...; xm = 0)                 (2.4.5)

Плану (2.4.5)  соответствует разложение

                x1A1 + x2A2 +...+ xmAm = A0,                                                (2.4.6)

 где  А1, А2, …, Аm линейно независимы, следовательно, построенный первоначальный план является и опорным.

         Рассмотрим, как исходя из первоначального опорного плана (2.4.5), можно построить второй опорный план. Векторы А1, А2, …, Аm образуют базис в m-мерном пространстве, поэтому каждый из данных n векторов соотношения (2.4.4) можно разложить по векторам базиса, причем единственным образом:

                         m

                 Aj = ∑ xij Ai,           j =1, 2, ..., n.

                                       i=1

         Предположим, что для некоторого вектора, не входящего в базис, например, для вектора Аm+1 , положителен хотя бы один из коэффициентов хi,m+1 в разложении

              x1,m+1A1 + x2,m+1A2 +...+ xm,m+1Am = Am+1.                             (2.4.7)

         Зададимся некоторой величиной θ > 0 (пока неизвестной ), умножим на нее обе части равенства (2.4.7) и вычтем результат почленно из равенства (2.4.6).

Получаем:

 (x1 –θх1,m+1)A1 + (x2-θх2,m+1)A2 +...+ (xm-θхm,m+1)Am + θAm+1 = A0.  (2.4.8)

    

         Таким образом, вектор

                            Х1 = (x1 –θх1,m+1; x2-θх2,m+1; ...; xm-θхm,m+1; θ; 0, …; 0)

является планом, если его компоненты неотрицательны.

         Так как θ > 0, то все компоненты вектора Х1, в которые входят неположительные xi,m+1, неотрицательны. Поэтому надо рассмотреть только компоненты, включающие положительные xi,m+1 (i=1, 2, ..., m), т.е необходимо определить такое θ > 0, при котором для всех  xi,m+1>0

                     xi - θxi,m+1 ≥ 0.                                                                (2.4.9)

          Из (2.4.9) получаем  θ ≤ xi/xi,m+1 , следовательно вектор х1- план задачи для любого θ,  удовлетворяющего условию

                  0 < θ  ≤ min xi/ xi,m+1 ,                                                      (2.4.10) 

где минимум берется по i, для которых xi,m+1 > 0.

         Опорный план не может содержать m+1 положительных компонентов, поэтому в плане Х1 необходимо обратить в нуль по крайней мере одну из компонент. Положим в (2.4.10), что

           θ = θ0= min xi/ xi,m+1 ,                                                              (2.4.11)          

тогда компонента плана Х1, для которой достигается минимум, обращается в нуль. Пусть эта компонента стоит на первом месте, т.е.

                         

                      θ0 = min xi/ xi,m+1 = min x1/ x1,m+1.

                                      

         Подставляя значение θ0  в (2.4.8), имеем

 ,

откуда получаем разложение

                      х¢2A2 + x¢3A3 + ... + x¢mAm + x¢m+1Am+1 = A0,

 

которому соответствует новый опорный план :

                       Х1 = (0; х¢2; x¢3; ...; x¢m; x¢m+1; 0; ...; 0), 

где x¢i = xi - θ0xi,m+1  (i = 2, 3, ..., m),   x¢m+1 = θ0.

          Исключение одного вектора из базиса и включение вместо него другого с помощью θ0 соответствуют переходу от одного базиса к другому с помощью метода  Жордана – Гаусса,  поэтому система векторов  А1, А2,…,Аm, Аm+1        линейно независима и является новым базисом.

         Для  определения следующего опорного плана необходимо любой вектор, не входящий в базис А2, А3, …, Аm, Аm+1, разложить по векторам этого базиса, а затем определить такое θ0 > 0, при котором исключался бы один из векторов этого базиса.

         Таким образом, процесс получения новых опорных планов заключается в выборе вектора, который подлежит включению в базис, и определении вектора, подлежащего исключению из базиса. Критерий, используемый для определения вектора, который включается в базис, является одним из основных элементов симплексного метода. Заметим, что если вектор Аm+1 подлежит включению в базис, а в его разложении (2.4.7) все  xi,m+1 ≤ 0, то, очевидно, нельзя выбрать такое  θ > 0, которое исключало бы один из векторов разложения (2.4.8). В этом случае план Х1 содержит m+1 положительных компонент, а система векторов А1, А2, …, Аm, Аm+1  линейно зависимая и определяет не угловую, а внутреннюю точку многогранника решений, в которой линейная функция не может достигать минимального значения. Это указывает на то, что гиперплоскость соответствующая линейной функции, не может стать опорной к многограннику решений, как бы далеко ни перемещать ее в направлении, обратном вектору N, т.е. линейная функция не ограничена на многограннике решений.

          Таким образом, если система ограничений задачи линейного программирования при неотрицательных свободных членах содержит единичный базис, то без дополнительных вычислений можно получить первоначальный опорный план, а также коэффициенты разложения векторов по векторам базиса.

 

Отыскание оптимального плана. Условия оптимальности

 

           Предположим, что задача линейного программирования (2.4.1) - (2.4.3) обладает планами и каждый ее опорный план невырожден. В этом случае для опорного плана (2.4.5) имеем:  

                x1A1 + x2A2 +...+ xmAm  = A0,                                             (2.4.12)

                x1С1 + x2С2 +...+ xmСm  = Z(Х0),                                         (2.4.13)

где все xi > 0, а Z(Х0) - значение линейной функции, соответствующее этому плану.

            Разложение любого вектора Aj по векторам данного базиса А1, А2,…, Аm единственное:

                 x1jA1 + x2jA2 + ... + xmjAmj  = Aj       (j=1, 2,…, n),             (2.4.14)

поэтому разложению вектора Аj  в базисе соответствует и единственное значение линейной функции

                 x1jС1 + x2jС2 +...+ xmjСmj = Zj      (j=1, 2, …, n),                (2.4.15)    

где Zj   - значение линейной функции, если в нее вместо неизвестных подставить соответствующие коэффициенты разложения j-го вектора по векторам

базиса.

          Обозначим через Сj  коэффициент линейной функции, соответствующий  вектору  Aj . Тогда справедлива следующая теорема.

         Теорема 1.  Если для некоторого вектора  Aj  выполняется условие

 Zj  – Сj > 0, то план X0  не является оптимальным, и можно построить такой план X , для которого выполняется неравенство Z(X) < Z(X0).

         Следствие.  Если для некоторого плана X0   разложения всех векторов Aj   (j = 1, 2, …, n) в данном базисе удовлетворяют условию

                                Zj  – Сj  ≤  0,                                                        (2.4.16)

то план X0  является оптимальным.

          Неравенства   (2.4.16)  являются условием оптимальности плана задачи, решаемой на отыскание минимального значения линейной  функции, а значения Zj  – Сj называются оценками плана.

          Таким образом, для того чтобы план задачи на отыскание минимального значения линейной функции был оптимальным, необходимо и достаточно, чтобы его оценки были неположительными.

           Для задачи линейного программирования (2.4.1) – (2.4.3), заключающейся в отыскании максимального значения линейной функции, справедлива следующая теорема.

           Теорема 2.   Если для некоторого вектора  Aj выполняется условие

Zj  – Сj <0, то план X0 не является оптимальным  и можно построить такой план X , для которого выполняется условие  Z(X) > Z(X0).

          Следствие.   Если для некоторого плана Х0  разложения всех векторов Aj    (j =  1, 2,…, n) в данном базисе удовлетворяют условию

                                  Zj  – Сj  ≥ 0,                                                        (2.4.17)

 то план Х0 является оптимальным

          Неравенство (2.4.17) - условие оптимальности плана задачи на отыскание максимального значения линейной функции.

         Таким образом., для того  чтобы план задачи на отыскание максимального значения линейной функции был оптимальным, необходимо и достаточно, чтобы его оценки были неотрицательными.

 Алгоритм симплексного  метода

Пусть имеем задачу линейного программирования. Минимизировать линейную формулу         при следующих ограничениях:

               (2.4.18)

В более компактной  форме систему ограничений (2.4.18) можно представить в виде  где -й вектор-столбец, координатами которого являются коэффициенты при неизвестном   - вектор-столбец свободных членов системы ограничений.

         Определим  некоторые свойства решений задачи, с которыми очень часто придется встречаться. Будем называть решением (планом) задачи линейного программирования вектор, удовлетворяющий системе ограничений задачи и условию План задачи, для которого линейная форма достигает минимума (или максимума), является оптимальным.

         Предполагается, что рассматриваемая задача обладает планами и содержит m векторов, из которых составляется единичная матрица порядка m. Исходным планом задачи в базисе системы единичных векторов     будет план вида   . Если для плана   все, такой план будет невырожденным; если же один или несколько коэффициентов xi = 0 , план будет вырожденным.

         Решение задачи начинаем с составления первой итерации симплексного процесса, предварительно обозначив

В (m+1)-й строке  значения Z0 и  Zj  можно определить по формулам:

 

Первая итерация

 

i

Базис

ci

C1

C2

…

cm

Cm+1

…

Ck

…

cn

…

…

…

1

C1

X1

1

0

…

0

…

…

2

C2

X2

0

1

 

0

…

…

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

…

.

.

.

.

.

.

…

.

.

.

…

.

.

.

L

cl

Xl

0

0

…

0

…

…

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

…

.

.

.

.

.

.

…

.

.

.

…

.

.

.

M

cm

Xm

0

0

…

1

…

…

M+1

…

…

…

 

         Критерием оптимальности плана задачи является выполнение условия . Если же условие не выполняется , т.е. для некоторого номера

 j (Zj-cj)>0, тогда следует отыскать новый план, который лучше (по крайней мере, не хуже) предшествующего. Базис нового плана будет содержать (m-1) векторов первоначального базиса и новый вектор, вводимый в базис. Чтобы определить, какой вектор следует ввести в базис, просматривают (m+1)-ю строку. Вектор, соответствующий максимальному значению разности, , вводится в базис, причём максимальное значение разности берётся по всем индексам  j (j=1,2,…,n).

         Предположим, что . Вектор  следует ввести в новый базис. Столбец, соответствующий вектору , является разрешающим.

         Невырожденный план задачи должен содержать ровно m положительных компонент, поэтому необходимо определить, какой вектор нужно вывести из базиса. Для этого вычисляют минимальное отношение координат xi исходного плана соответственно к положительным элементам xik  разрешающего столбца, т.е.

.

         Пусть таким положительным числом является

.

         Значит, вектор  следует исключить из базиса. Строка, соответствующая вектору , является разрешающей. Элемент xlk , стоящий на пересечении разрешающей строки и разрешающего столбца, называется  ключевым, или разрешающим. (В первой итерации разрешающий столбец и строка взяты в рамку.)

         Таким образом, новый базис содержит (m-1) векторов старого базиса и вектор .

         В этом базисе вычисляют новый план  и разлагают на векторы, не входящие в базис, причём единственным образом, по векторам базиса.

Вторая итерация

 

i

Базис

ci

C1

C2

…

Cm

Cm+1

…

ck

…

cn

…

…

…

1

C1

X1/

1

0

…

0

…

0

…

2

C2

X2/

0

1

 

0

…

0

…

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

…

.

.

.

.

.

.

…

.

.

.

…

.

.

.

L

Ck

Xk/

0

0

…

0

…

1

…

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

…

.

.

.

.

.

.

…

.

.

.

…

.

.

.

M

cm

Xm/

0

0

…

1

…

0

…

M+1

…

…

…

 

         Составляющие x/i нового плана определяются из соотношений

                             (2.4.19)

элементы  - из соотношений

                         (2.4.20)

         Если в (m+1)-й строке второй итерации все разности , получен оптимальный план; если же хотя бы одна из разностей , вторую итерацию необходимо провести  аналогично первой итерации. Процесс продолжается до тех пор, пока не будет получен оптимальный план, т.е. все разности .

         Может встретиться  случай, что одна или несколько разностей ,  а столбцы, соответствующие этим разностям, не содержат положительных элементов ( для какого-то k и всех i). Тогда линейная форма задачи не ограничена.

         Если первоначальная задача связана с максимизацией, можно использовать следующий критерий оптимальности плана: подсчитываются разности Zj –cj и выбирается новый вектор, соответствующий min(Zj-cj); оптимальный план в этом случае будет достигнут, когда все разности .

Пример 1. Найти максимум линейной формы Z=4x1+2x2  при следующих ограничениях:

Решение. Приведём задачу к каноническому виду:

Систему ограничений в векторной форме можно записать так:  или , где

         Поскольку отыскивается максимум задачи, оптимальный план будет достигнут, когда все разности

         Составляем исходный план задачи.

 

Исходный план

i

     Базис

         

 

4

2

0

0

0

0

1

  

  0

   5

   1

    0

    1

   0

   0

   0

2

  

  0

  14

   2

    1

    0

   1

   0

   0

3

  

  0

  10

   1

    1

    0

   0

   1

   0

4

  

  0

   8

   0

    1

    0

   0

   0

   1

5

  -4

   -2

    0

   0

   0

   0

        

Исходный базис состоит из векторов ,,,; ему соответствует план . Поскольку  равны нулю, значение линейной формы .

         В базис вводится вектор, который соответствует  Такой разностью является ; ей соответствует вектор , следовательно, вектор  нужно ввести в базис. Чтобы определить, какой вектор необходимо вывести из базиса, вычислим:

         Вектор  нужно вывести из базиса. Получаем разрешающую строку и разрешающий столбец (в таблице выделено рамкой).

         Преобразовав план  по формулам (2.4.19), получим новый план:

 

План

i

Базис

  

 

4

2

0

0

0

0

1

  

    4

    5

    1

    0

    1

    0

    0

    0

2

  

    0

    4

    0

    1

   -2

    1

    0

    0

3

  

    0

    5

    0

    1

   -1

    0

    1

    0

4

  

    0

    8

    0

    1

    0

    0

    0

    1

5

    0

   -2

    4

    0

    0

    0

 

         В этом случае значение линейной формы  Для плана  критерий оптимальности не выполняется. Среди разностей  имеются разности меньше нуля. Такой разностью является , следовательно, вектор нужно ввести в базис. Определяем, какой вектор следует исключить из базиса.

значит, вектор  подлежит исключению из базиса. Получили вторую разрешающую строку и новый разрешающий столбец.

          Преобразовав план  получим новый план

 

План

i

Базис

  

 

4

2

0

0

0

0

1

  

    4

    5

    1

    0

    1

    0

    0

    0

2

  

    2

    4

    0

    1

   -2

    1

    0

    0

3

  

    0

    1

    0

    0

    1

   -1

    1

    0

4

  

    0

    4

    0

    0

    2

   -1

    0

    1

5

    0

    0

    0

    2

    0

    0

 

         Очевидно, для плана  критерий  оптимальности выполняется, все  Следовательно, не существует нового допустимого решения системы линейных уравнений, при котором линейная форма принимала бы большее значение, чем , т.е. максимум линейной формы  достигается при плане