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

                                                                 62
              �
              n                �
 λi g i =λi �� ∑ αij x j −βi �� =0, i =1, m
                � j =1           �
                                    −µ j x j =0,                        j =1, n
                      λi ≥0, i =1, m, µ j ≥0, j =1, n .
     По теореме Куна - Таккера решение этой системы является искомой
точкой минимума функции f (x) на множестве Ω . Введя дополнительные
переменные xn +i , i =1, m , полученную систему перепишем в виде системы
равенств
                             n                     n
                             ∑ q ij x j +∑ λ i α ij −µ j =−b j ,                   j =1, n
                             i =1                 i =1
                                       n
                                       ∑ αij x j +xn +i =βi , i =1, m
                                       j =1
                                                       x j ≥0,        j =1, n +m               (1)
                                                  λi xn +i =0 i =1, m,
                                                   µ j x j =0, j =1, n
                                                       λi ≥0, i =1, m ,
                                           µ j ≥0, j =1, n
Решение ( x1 , x2 ,..., xn +m , λ1 ,..., λ m , µ1 ,..., µn ) данной системы n +m линейных
уравнений содержит, по крайней мере n +m нулевых координат. Задачу
нахождения решения системы                            без условий λi xn +i =0 i =1, m, и
µ j x j =0, j =1, n можно свести к нахождению допустимой базисной точки
методом искусственного базиса в специально построенной задаче линейного
программирования
                      z 1 +z 2 +... +z n +z n +1 +... +z n +m → min
                      n                       n
                      ∑ q ij x j +∑ λ i α ij −µ j +z j =−b j ,                       j =1, n
                      i =1                 i =1
                                 n
                               ∑ α ij x j +x n +i +z n +i =βi , i =1, m
                                 j=1

                                        x j ≥0, z j ≥0                j =1, n +m
                    λi ≥0, i =1, m, µ j ≥0, j =1, n .
При реализации метода искусственного базиса следует учитывать условия
                          λi xn +i =0 i =1, m,
                           µ j x j =0, j =1, n ,
т.е. не включать в базисные переменные одновременно λi и xn +i с одним и
тем же номером i и переменные µ j и x j с одинаковым номером j .
       Пример 1. Решить задачу квадратичного программирования:
                     x12 −2 x1 x 2 +2 x 22 −2 x1 −6 x 2 → min