Составители:
Рубрика:
78
∑ ∑
= =
=
m
i
m
i
iii
yXAyb
i
1 1
.)(
(2.2.58)
Из первого равенства получаем
∑
=
=−
n
j
jjj
cYAx
1
.0)(
Все слагаемые этой суммы неотрицательны, поскольку x
j
≥0 и A
j
Y – c
j
≥0. Но сумма
всех неотрицательных чисел может равняться нулю только в том случае, когда каждое
слагаемое равно нулю, т. е. для каждого j имеем
x
j
(A
j
Y-c
j
)=0 (2.2.59)
откуда следует, что если x
j
>0, то должно быть A
j
Y= с
j
и, наоборот, если АY>с
j
, то должно
быть х
j
=0, а это и есть условия (2.2.53) и (2.2.54) теоремы.
Аналогичные рассуждения с использованием равенства (2.2.58) доказывают
справедливость условий (2.2.51) и (2.2.52).
Примечание.
Равенство (2.2.59) выполняется при A
j
Y - c
j
=0 и x
j
=0. Поэтому при
оптимальных решениях X и Y взаимосопряженных задач могут существовать некоторые
пары двойственных условий (2.2.40) и (2.2.41), в которых каждое условие является
равенством, так как теорема утверждает, что если в какой-либо паре двойственных
условий одно условие является строгим неравенством, то второе — обязано быть равенст-
вом. Обратное же утверждение теоремой не предусматривается.
Теорема равновесия часто может быть использована для проверки оптимальности
предложенного решения задачи линейного программирования. Если задано решение
прямой задачи, то, с использованием теоремы равновесия, часто удается найти
допустимое решение двойственной задачи. Если допустимый вектор X (предложенное
решение прямой задачи) и допустимый вектор Y двойственной задачи будут удовлет-
ворять условиям теоремы равновесия, то оба вектора X и Y — оптимальны. Рассмотрим
численный пример.
Найти неотрицательные числа х
1
x
2
, х
3
, х
4
, максимизирующие целевую функцию
z=2x
1
+3x
2
+x
3
+x
4
(2.2.60)
при условиях:
≤++
≤++
≤++
.8523
;52
;94
432
321
421
xxx
xxx
xxx
(2.2.61)
Предположим, что вычислено оптимальное решение этой задачи:
x
1
= l, x
2
= 2, x
3
= l, x
4
= 0. (2.2.62)
Подставляя эти числа в уравнение (2.2.60), получаем
z
мax
=2⋅1 +3⋅2+ 1+0 = 9.
Как проверить, что никакой другой набор чисел х
j
, также удовлетворяющий
системе ограничений (2.2.61), не даст нам большего значения целевой функции (2.2.60)?
Это можно проверить следующим образом. Составим условие двойственной задачи.
Двойственной к задаче (2.2.60) — (2.2.61) будет задача нахождения
неотрицательных чисел у
1
, у
2
, y
3
, для которых целевая .функция
w = 9y
1
+ 5y
2
+ 8y
3
(2.2.63)
минимальна и которые подчинены условиям:
Страницы
- « первая
- ‹ предыдущая
- …
- 76
- 77
- 78
- 79
- 80
- …
- следующая ›
- последняя »
