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

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

26
Из графика видно, что решением является пересечение прямых
yy 27)(
-
=
w
и 5)(
+
=
yy
w
. Отсюда
3
2
* =y
, а
.
3
2
5*)( =y
w
Обе задачи, и исходная, и двойственная, имеют решение, но значения
целевых функций не совпадают. Это явление называется скачком двойст-
венности.
Замечание. Как мы убедились, верная для линейных задач первая тео-
рема двойственности в нелинейной оптимизации не выполняется.
Слабая теорема двойственности
Пусть *x – решение исходной задачи, а *y – решение двойственной.
Тогда справедливо следующее неравенство:
.0,)(*)(*)()(
³
Î
"
£
£
£
ySxxxyy
j
j
w
w
Доказательство.
Покажем, что ).(*)(*)()( xxyy
j
j
w
w
£
£
£
Неравенства
*)()( yy
w
w
£
и
)(*)( xx
j
j
£
справедливы, т. к. *x – реше-
ние исходной задачи, а *y – решение двойственной.
По определению двойственной функции верно следующее неравенство:
.)(*)(*)( Sxxfyxy
T
Î"+£
jw
При *xx
=
получим:
)(**)(*)( xfyxy
T
+£
jw
.
Здесь .0*)(,0* £³ xfy
T
Следовательно, *).(*)( xy
j
w
£
Что и требовалось доказать.
Теорема двойственности
I. Если *)*,( yx – седловая точка исходной задачи, то *)(*)( yx
w
j
=
.
II. Если *x – решение исходной задачи, 0*
³
y и справедливо равенст-
во *)(*)( yx
w
j
=
, то исходная задача имеет седловую точку *)*,( yx .
Доказательство.
I. Требуется доказать равенство *)(*)( yx
w
j
=
.
По определению седловой точки имеют место следующие неравенства:
.0,*),(*)*,()*,(
³
Î
"
F
£
F
£
F
ySxyxyxyx
1) Перепишем неравенство 0*)*,()*,(
³
"
F
£
F
yyxyx в виде:
.0*)(**)(*)(*)( ³"+£+ yxfyxxfyx
TT
jj
     Из графика видно, что решением является пересечение прямых
                                                     2                2
� ( y ) � 7 � 2 y и � ( y ) � y � 5 . Отсюда y* �      , а � ( y*) � 5 .
                                                     3                3
    Обе задачи, и исходная, и двойственная, имеют решение, но значения
целевых функций не совпадают. Это явление называется скачком двойст-
венности.
    Замечание. Как мы убедились, верная для линейных задач первая тео-
рема двойственности в нелинейной оптимизации не выполняется.
     Слабая теорема двойственности
     Пусть x * – решение исходной задачи, а y * – решение двойственной.
Тогда справедливо следующее неравенство:
                   � ( y ) � � ( y*) � � ( x*) � � ( x) �x � S , y � 0.
     Доказательство.
     Покажем, что � ( y ) � � ( y*) � � ( x*) � � ( x).
     Неравенства � ( y ) � � ( y*) и � ( x*) � � ( x) справедливы, т. к. x * – реше-
ние исходной задачи, а y * – решение двойственной.
     По определению двойственной функции верно следующее неравенство:
                       � ( y*) � � ( x) � y *T f ( x) �x � S .
     При x � x * получим:
                                    � ( y*) � � ( x*) � y *T f ( x) .
     Здесь y *T � 0, f ( x*) � 0.
     Следовательно, � ( y*) � � ( x*).
     Что и требовалось доказать.
     Теорема двойственности
     I. Если ( x*, y*) – седловая точка исходной задачи, то � ( x*) � � ( y*) .
     II. Если x * – решение исходной задачи, y* � 0 и справедливо равенст-
во � ( x*) � � ( y*) , то исходная задача имеет седловую точку ( x*, y*) .
     Доказательство.
     I. Требуется доказать равенство � ( x*) � � ( y*) .
     По определению седловой точки имеют место следующие неравенства:
     � ( x*, y ) � � ( x*, y*) � � ( x, y*) �x � S , y � 0.
     1) Перепишем неравенство � ( x*, y ) � � ( x*, y*) � y � 0 в виде:
                    � ( x*) � y T f ( x*) � � ( x*) � y *T f ( x*) � y � 0.
                                               26

Страницы