Составители:
Рубрика:
139
Таким образом, двойственной по отношению к канонической задаче является
следующая задача.
Требуется найти числа
у
1
,
y
2
,...,
у
т
,
обращающие в минимум целевую
функцию
G = b
1
y
1
+ b
2
y
2
+
. . .
+b
i
y
i
+ ... +b
m
y
m
(3.52)
при условиях:
≥+++++
≥+++++
≥+++++
.......
................................................................
,......
................................................................
,......
2211
2211
111221111
nmmniinnn
jmmjiijjj
mmii
cyayayaya
cyayayaya
cyayayaya
(3.53)
Для задач (3.50), (3.51) и (3.52), (3.53) приемлема первая теорема двойственности, а
также вторая теорема двойственности, в которой рассматриваются только пары
двойственных условий (3.40).
Аналогично составляется задача двойственная к канонической задаче
минимизации, с той лишь разницей, что в ограничениях-неравенствах двойственной
задачи должны быть знаки неравенств
≤
.
∑ ∑
∑ ∑
= =
=
=≤==
====
n
j
m
i
jiijijij
m
i
iijjj
njcyamibxa
ybGxcxF
1 1
1
,1,,1,
maxmin)(
Кроме симплексного метода решения задачи линейного программирования,
существуют и другие методы, основанные на идее двойственности. При решении задачи
симплексным методом одновременно получается оптимальное решение двойственной
задачи. Это оптимальное решение представляется в последней симплексной таблице
двойственными оценками
∆j
,
соответствующими базисным неизвестным в исходной
симплексной таблице.
Если задача решается методом искусственного базиса
, то
оптимальными переменными двойственной задачи являются двойственные оценки
∆
j
в
последней симплексной таблице, соответствующие искусственным переменным,
взятые с
их знаками в задачах минимизации и с обратными знаками в задачах максимизации.
Используя теоремы двойственности, можно проверить правильность решения
задачи линейного программирования и в некоторых случаях применить более простые
приемы решения задач.
Применяя изложенные выше положения теории двойственности, проверим
правильность решения задач, приведенных в § 1 и 2 данной главы.
Так, табл. 3.5 в 3.1 является последней симплексной таблицей, в которой
содержится результат решения задачи: найти максимум целевой функции
F
= 3
x
1
+ 4
x
2
+ 6
x
3
(3.54)
при условиях:
x
1
≥
0,
x
2
≥
0
x
3
≥
0
Страницы
- « первая
- ‹ предыдущая
- …
- 137
- 138
- 139
- 140
- 141
- …
- следующая ›
- последняя »
