Составители:
Рубрика:
77
∑ ∑ ∑ ∑
= = = =
===
n
j
n
j
m
i
m
i
iiijjjj
ybyXAxYAxc
i
1 1 1 1
.)()( (2.2.50)
Имеет место следующая интересная теорема.
Теорема 3
(теорема равновесия). Допустимые векторы X и Y прямой и
двойственной задач являются оптимальными в том и только в том случае, если в парах
их двойственных условий (2.2.40) и (2.2.41) одно условие является равенством, как только
второе — строгим неравенством.
П о я с н е н и е. Строгое неравенство имеет знак > вместо ≥ или < вместо ≤..
Д о к а з а т е л ь с т в о. Прежде докажем достаточность условий теоремы.
Предположим, что условия теоремы выполнены, т. е. что в некоторых парах
двойственных условий (2.2.40)
y
i
=0, A
i
X<b
i
(2.2.51)
и
y
i
>0, А
i
Х = b
i
(2.2.52)
в остальных парах.
Точно так же в некоторых парах двойственных условий (2.2.41)
x
j
= 0, A
j
Y>c
j
(2.2.53)
и в остальных парах
x
j
> 0, A
j
Y=c
j
(2.2.54)
Умножая i-е ограничение-неравенство прямой задачи A
i
X≤b
i
на y
i
и
используя условия (2.2.51), получим
.)(
iiii
yXAyb =
Суммируя это равенство по индексу i от 1 до т, находим
∑ ∑ ∑
= =
==
m
i
m
i ji
ijijiii
yxayXAyb
i
1 1 ,
.)( (2.2.55)
Аналогично, умножая j-е ограничение-неравенство двойственной задачи A
j
Y ≥с
j
на
х
j
и используя условие (2.2.53), получим
.)(
jjjj
xYAxс =
Суммируя это равенство по индексу j от 1 до п, находим
∑ ∑ ∑
= =
==
n
j
n
j ji
ijijjjjj
yxaxYAxc
1 1 ,
.)( (2.2.56)
Из равенств (2.2.55) и (2.2.56) имеем
∑ ∑
= =
=
n
j
m
i
iijj
ybxc
1 1
.
или
CX=BY,
поэтому, в силу теоремы 2, векторы X и Y являются оптимальными решениями
взаимосопряженных задач.
Теперь докажем необходимость условий теоремы. Предположим, что векторы X и
Y являются оптимальными; тогда должны иметь место равенства (2.2.50). Из равенств
(2.2.50) следует:
∑ ∑
= =
=
n
j
n
j
jjjj
xYAxc
1 1
;)( (2.2.57)
Страницы
- « первая
- ‹ предыдущая
- …
- 75
- 76
- 77
- 78
- 79
- …
- следующая ›
- последняя »
