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

                                                            m
                                 � ( y 1 ) � � ( x) � � y i1 f i ( x), �x � S ,
                                                           i �1
                                                            m
                                � ( y 2 ) � � ( x) � � y i21 f i ( x), �x � S .
                                                           i �1

    Умножив первое неравенство на � , а второе – на ( 1 � � ) и сложив их,
мы получим:
                                                             m
            �� ( y 1 ) � (1 � � )� ( y 2 ) � � ( x ) � � (��y 1 � (1 � � ) y 2 ) f i ( x), �x � S .
                                                            i �1

    Полученное выражение верно для любого x � S , следовательно, оно
будет верно, если мы возьмем от обеих частей минимум по x � S . Значит,
верно неравенство (**).
    Что и требовалось доказать.

    Скачок двойственности
    Рассмотрим следующую задачу оптимизации:
                                             � ( x) � max
                                          f i ( x) � bi , i � 1, m
                                             x � 0 (x � S) ,
где � , f i , i � 1, m - заданные функции, S - некоторое множество.
    Функция Лагранжа для данной задачи имеет вид:
                 � ( x, y ) � � ( x) � y T (b � f ( x)), x � 0, y � 0.
                                                                     �
                                                                     �
                                                                     �
                                                                         x � S ���
    При этом исходная задача записывается с помощью � ( x, y ) следую-
щим образом:
                                            max min � ( x, y ),
                                             x�0        y �0
                                             ( x�s )

двойственная задача по определению имеет вид:
                                            min max � ( x, y ).
                                              y �0     x�0
                                                       ( x�s )

     Свойства двойственности, справедливые для линейного программиро-
вания, вообще говоря, неверны в нелинейном случае. Проиллюстрируем
это на примере:
     Пример.
    10 � 3x1 � 2 x 2 � x3 � min
     2 x1 � 3x 2 � 4 x3 � 4,

                                                       24