Элементы теории двойственности. Чернышова Г.Д - 8 стр.

                                                                 �     �
    Из свойства 2 следует, что �x � � можно записать cT x � bT y � cT x . сле-
            �
довательно, x – решение исходной задачи.

    5. Возможна ситуация: � � � и Q � � .
    Рассмотрим пример. Исходная задача задана в виде
                              3 x1 � 2 x 2 � max
                              � x1 � x 2 � 4       .
                              �
                              � x1 � x 2 � 2
Допустимое множество � � � .
Двойственная к исходной запишется следующим образом
                              4 y1 � 2 y 2 � min
                              � y1 � y 2 � 3       .
                              �
                              � y1 � y 2 � 2
Допустимое множество Q � � .

    6. Пусть � � � и Q � � , тогда исходная задача не имеет решения из-
за неограниченности целевой функции на допустимом множестве.
     7. Если � � � и Q � � , то обе задачи имеют решение.

    8. Первая теорема двойственности.
    Если одна из задач (исходная или двойственная) имеет решение, то и
вторая имеет решение, причём оптимальные значения целевых функций
совпадают.
    Доказательство.
    Пусть задана задача в каноническом виде

                                  с T x � max
                                      Ax � b
                                      x �0.
    И пусть она имеет решение x 0 , полученное, например, симплекс-
методом.
    Двойственная задача записывается в виде

                                 b T y � min
                                 AT y � c.
                                       8