Линейное программирование. Элементы теории, алгоритмы и примеры. Азарнова Т.В - 31 стр.

                                                      Линейное программирование


        Ax ≤b                A T y ≥c
        x ≥0                  y ≥0
      Свойство 1. Задача двойственная к двойственной является исходной.
      Свойство 2. Для любых x допустимых в исходной задаче и y допус-
тимых в двойственной справедливо неравенство
                                 c T x ≤b T y
      Свойство 3. Если исходная задача не имеет решения из-за неограни-
ченности целевой функции на допустимом множестве, то допустимое мно-
жество двойственной задачи пусто.
      Свойство 4. Возможен вариант, когда допустимые множества исход-
ной и двойственной задач одновременно пусты.
      В качестве примера рассмотрим следующую двойственную пару
      x1 +2 x 2 → max                      −4 y1 + y 2 → min
       −3x1 −x 2 ≤−4                       −3 y1 +3 y 2 =1
         3 x1 +x 2 ≤1                      − y1 + y 2 =2
                                            y1 ≥0, y 2 ≥0
     Свойство 5. Если существует точка x 0 , допустимая в исходной задаче
и точка y 0 , допустимая в двойственной задаче, такие, что c T x 0 =b T y 0 , то
 x 0 - решение исходной, а y 0 - решение двойственной задачи.
         Теорема 1. (Первая теорема двойственности). Если одна из задач
(двойственная или исходная) имеет решение, то и двойственная к ней имеет
решение, причем оптимальные значения целевых функций совпадают.
         Теорема 2. (Вторая теорема двойственности) Для того, чтобы допус-
тимая в исходной задаче точка x 0 и допустимая в двойственной задаче
точка y 0 являлись соответственно решениями исходной и двойственной за-
дач, необходимо и достаточно, чтобы выполнялись равенства (условия до-
полняющей нежесткости):
               �                       �
                                                ( )(              )
                        m                                 T
         x 0j � c j −∑ a ij y i0 � =0, j =1, n или  x 0 c −AT y 0 =0
                 �     i =1              �
                   �               �
                                                ( )(          )
                        n                                 T
         y i0 �� bi −∑ a ij x 0j �� =0, i =1, m или y 0 b −Ax 0 =0 .
                     � j =1          �
         Замечание 1.В симплекс - процедуре осуществляется перебор базисов
B (невырожденных) подматриц исходной матрицы A таким образом, что
                                                       � x�
         1. На каждой итерации метода вектор x B =� � , где x =B −1b является
                                                        � 0�
                                                         � �
допустимым в исходной задаче, т.е. Ax B =b, x B ≥0 ;



                                     33