7 Решение  задач  симплексным  методом  с  искусственным  базисом

 

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

         Минимизировать линейную форму

                               Z = c1x1 + c2x2 + … + c n x n

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

                                                              (2.5.1)

                              x j  0 (j=1, 2,…, n, n+1, n+2, …, n+ m ).

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

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

минимизировать линейную форму

            Z = c1x1 + c2x2 + … + cnxn + Mxn+1 + Mxn+2 +…+ M x n+ m       (2.5.2)

при следующих ограничениях:

                                                         (2.5.3)

             x j  0 (j = 1, 2, …, n, n+1, n+2, …, n+ m).

           Система уравнений (2.5.3) получена из системы (2.5.1) введением неотрицательных искусственных переменных.

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

          Между М-задачей и исходной задачей  существует  определенная зависимость. В случае неразрешимости М-задачи исходная задача или неразрешима, или линейная форма ее не ограничена. Если в оптимальном решении М-задачи все искусственные переменные равны нулю, то вектор

= (x1, x2, …, x n)  является оптимальным решением исходной задачи. Если же хотя бы одна из искусственных переменных отлична от нуля, исходная задача не имеет решения.

            Нужно заметить, что в случае, когда в базисе будут содержаться искусственные векторы, разности   Zj - cj      будут линейными функциями от М. Причем каждая из разностей Zj - cj  состоит из двух независимых друг от друга частей, одна из которых зависит от М. Результаты  вычислений сводятся в таблицу.

            Здесь введены обозначения bi = x n+ i, aij = xij, i=1, 2,…, m. Предполагается задача с полным искусственным базисом n+1, n+2, …, n+ m,  которому соответствует исходный план = (0, 0,…,0, xn+1, xn+2, …, x n+ m).

             Обработка таблицы производится аналогично первой итерации симплексного   процесса  с той  лишь разницей , что критерий оптимальности плана проверяется по (m+2)-й строке.

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

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

 

    i

Базис

сi

   1

  C1

  C2

…

C k

…

   C n

  1

  2

…

k

…

   n

   1

n+1

  M

Xn+1

X11

X12

…

X1k

…

X1n

   2

n+2

M

Xn+2

X21

X22

…

X2k

…

X2n

…

…

…

…

…

…

…

…

…

…

    L

n+l

M

X n+

Xl1

Xl2

…

X l k

…

X l n

…

…

…

…

…

…

…

…

…

…

  M

n +m

M

X n+ m

Xm1

Xm2

….

X  m k

…

X m n

  M+1

Z j-c j

 

0

-c1

-c2

…

- c k

…

-c n

 m+2

 

x n+ i

xi1

xi2

…

x i k

…

x i n

          

Проиллюстрируем  метод искусственного  базиса примерами.

         Пример 1. Минимизировать линейную форму z = -x1+2x2 + x3+3x4-x5 при следующих ограничениях:

                                            

                                                    x j  0 (j=1, 2, 3, 4, 5).

         Решение. Поскольку условие задачи  содержит единичны вектор 1, необходимо ввести два дополнительных вектора     6   и     7. Тогда задача   будет поставлена так. Минимизировать линейную форму Z = -x1 +2x2 + x3 +3x4-

-x5+Mx6+Mx7  при следующих ограничениях:

                                           

                                         x j 0 (j=1, 2, 3, 4, 5, 6, 7).

             Исходным  планом  является =(x 1,x 2,x 3, x4,x5,x6,x7)=(6, 0, 0, 0, 0, 6, 5).

                           

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

i

Базис

Сi

 

-1

2

1

3

-1

1

2

3

4

5

1

1

-1

6

1

2

3

2

-1

2

6

M

6

0

2

4

-4

2

3

7

M

5

0

1

1

1

1

4

Z1j-cj

 

-6

0

-4

-4

-5

2

5

 

11

0

3

5

-3

3

               Значение линейной формы, соответствующее  плану

  =(x 1,x 2,x 3, x4,x5,x6,x7) = (6, 0, 0, 0, 0, 6, 5), равно  –6+11М.

               В 5-й строке максимальным элементом является элемент (5; 3), равный5; таким образом, вектор 3   необходимо ввести в базис.

              Определяем  == min(, , )=;   следовательно, вектор   нужно исключить из базиса.

            Получаем план  = (x 1, x 2, x 3, x4, x5, x6, x7)=( , 0, , 0, 0, 0, ).

 

План  

 

I

Базис

Сi

 

-1

2

1

3

-1

1

2

3

4

5

1

1

-1

1

0

5

-

2

3

1

0

1

-1

3

7

M

0

0

2

4

-cj

 

0

0

-2

0

-9

4

5

 

0

0

2

         

         В 5-й строке максимальным элементом является элемент (5;4), равный 2; следовательно, вектор 4 необходимо ввести в базис. Так как  = min(, )= =; вектор    нужно исключить из базиса.

         Получаем новый план  = (x 1,x 2,x 3, x4,x5,x6,x7) = (0, 0, ,,0, 0, )  со значением линейной формы, равной   +М.

        В 5-й строке максимальное значение, равное ,  соответствует вектору ; следовательно,  вектор   нужно ввести в базис. Так как ==, вектор  следует  исключить из базиса.

        Преобразовав приведенный план, получим план  =(x 1,x 2,x 3, x4,x5,x6,x7)=

  =(0, 0, , ,, 0, 0). Значение линейной формы при плане  равно .

                               План 

i

Базис

С i

 

-1

2

1

3

-1

1

2

3

4

5

1

4

3

0

1

-

2

3

1

1

0

0

3

7

M

-

0

0

4

-с j

 

-

0

0

-

5

 

-

0

0

                                                 

                                                                        План            

 

i

Базис

С i

 

-1

2

1

3

-1

1

2

3

4

5

1

4

3

0

1

0

2

3

1

1

0

0

3

5

-1

-

0

0

1

4

Z44-cj

Z0=

-1

0

0

0

Вектор 1  следует  ввести  в базис,  так как   (Zj - cj) = Z1 - c1 = .

   = min(, ) =  = 9; следовательно, вектор  3   нужно исключить из базиса.

          Получаем новый план  = (x 1, x 2, x 3, x4, x5, x6, x7) = (9, 0, 0, ,, 0, 0).  Значение линейной формы при плане  равно  -.

План   

 

i

Базис

С i

 

-1

2

1

3

-1

1

2

3

4

5

1

4

3

0

0

1

0

2

1

-1

9

1

3

5

0

0

3

5

-1

0

1

4

0

1

4

Z4V-cj

 =-

0

-6

-9

0

0

 

             В индексной строке 4 все разности  ZVj - cj     0,  т.е. критерий оптимальности для плана выполняется.

           Получили значение линейной формы   zmin== -  при плане

= (x 1, x 2, x 3, x4, x5, x6, x7) = (9, 0, 0, ,, 0, 0).