Составители:
Рубрика:
80
Найти неотрицательный вектор Х =[х
1
,х
2
, . . .,х
п
], максимизирующий целевую
функцию
z=CX (2.2.69)
при условиях:
A
i
X
≤
b
i
, i=1, 2,..., т; (2.2.70)
-А
i
Х ≤ - b
i
i = 1,2,. . ., m. (2.2.71)
Двойственной к задаче (2.2.69) — (2.2.71) будет следующая задача.
Найти неотрицательные векторы ],...,,[
''
2
'
1
'
m
yyyY = и ],...,,[
''''
2
''
1
''
m
yyyY = ,
минимизирующие целевую функцию
w = B(Y'-Y") (2.2.72)
при условиях:
A
j
(Y'-Y")≥c
j
, j=1, 2,..., п, (2.2.73)
где B=[b
1
,b
2
,...,b
m
] — вектор ограничений задачи (2.2.67) — (2.2.68); A
j
=[a
1j
a
2j
,...,a
mj
] —
векторы условий той же задачи.
Если обозначить разность векторов Y' - Y" через Y = [y
1
, y
2
,…, y
т
] то координаты
этого вектора y
i
=y
i
' - у
i
" могут иметь любой знак. Поэтому двойственная задача (2.2.72) —
(2.2.73) эквивалентна следующей задаче.
Найти вектор Y=[y
1
, y
2
,…,y
m
] без ограничения его координат у
i
по знаку,
который обращает в минимум целевую функцию
w = BY (2.2.74)
при условиях:
A
j
Y ≥ c
j
, j=1,2,..., n. (2.2.75)
Задача (2.2.74) - (2.2.75) называется двойственной канонической задаче линейного
программирования (2.2.67) — (2.2.68).
Таким образом, мы видим, что задача, двойственная канонической задаче
линейного программирования, является задачей с ограничениями-неравенствами (2.2.75),
без ограничений переменных y
i
по знаку. Поэтому прямую каноническую задачу
линейного программирования и двойственную ей нельзя назвать взаимосопряженными.
Аналогично можно доказать, что для канонической задачи, также как и для
стандартной задачи, имеет место следующий критерий оптимальности.
Для оптимальности допустимых решений X = [x
1
, х
2
, . . ., х
п
] и Y = [y
1
, y
2
, . . ., у
т
]
задач (2.2.67) — (2.2.68) и (2.2.74) — (2.2.75) необходимо и достаточно равенство их
целевых функций СХ и BY для этих решений.
Справедливо также следующее утверждение, аналогичное теореме равновесия для
взаимосопряженных стандартных задач.
Для оптимальности допустимых решений X и Y задач (2.2.67) — (2.2.68) и (2.2.74)
— (2.2.76) соответственно необходимо и достаточно, чтобы в столбцовых парах
двойственных условий x
j
≥ 0, A
j
Y ≥ c
j
одно условие было равенством, как только другое —
строгим неравенством.
Теорема равновесия для канонической задачи линейного программирования и для задачи двойственной
ей также может быть использована для проверки оптимальности предложенных решений.
Пример. Пусть дана задача — найти неотрицательные числа x
j
, j = l,2,...,5,
максимизирующие целевую функцию
z= -x
i
– 5x
2
+ 6x
3
- х
4
– 4x
5
(2.2.76)
при условиях:
Страницы
- « первая
- ‹ предыдущая
- …
- 78
- 79
- 80
- 81
- 82
- …
- следующая ›
- последняя »
