Методы оптимизации. Азарнова Т.В - 61 стр.

                                          63
              x1 +x 2 ≤2
                                         −x1 +2 x 2 ≤2
                                         x1 ≥0, x 2 ≥0 .
     Решение. Целевая функция данной задачи является квадратичной с
               � 1 −1�
матрицей A =��           �� . Так как определители главных миноров данной
                � −1 2 �
матрицы ∆1 =1, ∆ 2 =1 положительны, то данная матрица является
положительно определенной, а целевая функция выпуклой. Следовательно,
данная задача является задачей выпуклого программирования и для ее
решения можно применить описанный выше метод решения. Система
равенств (1) запишется для рассматриваемой задачи в виде
                             2 x1 −2 x 2 +λ1 −λ 2 −µ1 =2
                       −2 x1 +4 x 2 +λ1 +2λ 2 −µ 2 =6
                                       x1 +x 2 +x 3 =2
                                    −x1 +2 x 2 +x 4 =2
                           x1 , x 2 , x 3 , x 4 , λ1 , λ 2 , µ1 , µ 2 ≥0
                           µ1 x1 =µ 2 x 2 =λ1 x3 =λ 2 x 4 =0 .
Найдем допустимое базисное решение этой системы, путем решения
вспомогательной задачи линейного программирования с искусственными
переменными
                                      −x 5 −x 6 → max
                      2 x1 −2 x 2 +λ1 −λ 2 −µ1 +x 5 =2
                     −2 x1 +4 x 2 +λ1 +2λ 2 −µ 2 +x 6 =6

                                 x1 +x 2 +x3 =2
                               −x1 +2 x 2 +x 4 =2
                     x1 , x 2 , x3 , x 4 , λ1 , λ 2 , µ1 , µ 2 ≥0 ,
взяв в качестве первоначального базисного множества                    J ={5,6,3,4}.
Приведем последовательность симплексных таблиц.

 cB     J      xB      x1     x2     x3         x4    λ1     λ2       µ1     µ2

 -1     5      2        2     -2      0          0    1      -1       -1     0
 -1     6      6       -2      4      0          0    1      2         0     -1
 0      3      2        1      1      1          0     0      0        0      0
 0      4      2       -1      2      0          1     0      0        0      0
               -8       0     -2      0          0    -2     -1        1      1
 -1     5      4        1      0      0          1     1     -1       -1     0
 -1     6      2        0      0      0         -2    1      2         0     1
 0      3      1      3/2      0      1        -1/2    0      0        0      0
 0      2      1      -1/2     1      0         1/2    0      0        0     0