Составители:
Рубрика:
136
Теорема 1 (первая теорема двойственности).
Если для допустимых решений x
1
,
x
2
,
...,
х
п
и
y
1
,
y
2
,...,
y
m
взаимосопряженных стандартных задач
∑ ∑
= =
=
n
j
m
i
iijj
ybxc
1 1
(3.38)
то эти допустимые решения являются оптимальными решениями соответствующих задач.
Иными словами, если значения целевых функций взаимосопряженных задач
совпадают при некоторых их допустимых решениях, то оба эти решения являются
оптимальными.
Доказательство. Пусть
''
2
'
1
,...,,
m
xxx —
какое-нибудь другое решение задачи на
максимум. Тогда по лемме
.
11
'
∑∑
==
≤
m
i
ii
n
j
jj
ybxc
Заменяя сумму в правой части этого неравенства равной суммой, на основании
соотношения (3.38) получаем:
.
11
'
∑∑
==
≤
n
j
jj
n
j
jj
xcxc
Это неравенство показывает, что значение целевой функции па любом допустимом
решении
''
2
'
1
,...,,
m
xxx
получается меньше, чем на допустимом решении
x
1
,
x
2
,
...,
х
п
,
удовлетворяющем условию теоремы. Это значит, что последнее допустимое решение задачи
на максимум оптимальное. Аналогично можно доказать оптимальность допустимого
решения
y
1
,
y
2
,. . . ,
y
m
двойственной задачи на минимум.
В теории линейного программирования не так просто доказывается, что условие
равенства целевых функций (3.38) является не только достаточным, но и необходимым
условием оптимальности допустимых решений; взаимосопряженных стандартных задач, т. е.
если
x
1
,
x
2
,
...,
х
п
,
и
y
1
,
y
2
,...,
y
m
оптимальные решения взаимосопряженных задач, то
значения целевых функций для этих оптимальных решений одинаковы.
Имеет место еще одно
соотношение между взаимосопряженными задачами, которое также является признаком
оптимальности допустимых решений этих задач.
Теорема 2 (вторая теорема двойственности).
Допустимые решения х
1
,
х
2
,…,
х
n
и
y
1
,
y
2
,...,
y
m
взаимосопряженных стандартных задач являются оптимальными решениями
этих задач тогда и только тогда, если в парах их двойственных условий
.,0
1
i
n
j
jiji
bxay ≤≥
∑
=
(3.39)
и
.,0
1
j
m
i
iijj
cyax ≥≥
∑
=
(3.40)
первое условие является равенством, как только второе строгим неравенством.
Разъяснение. Строгие неравенства имеют знак
>
или
<.
Доказательство. Допустим, что условия теоремы выполнены, т. е. что
.при0
1
i
n
j
jiji
bxay <=
∑
=
(3.41)
и
.при0
1
j
m
i
iijj
cyax >=
∑
=
(3.42)
Страницы
- « первая
- ‹ предыдущая
- …
- 134
- 135
- 136
- 137
- 138
- …
- следующая ›
- последняя »
