Составители:
Рубрика:
75
…………………………
a
m
1
x
1
+ a
m
2
x
2
+… a
mn
x
n
≤
b
m
………………………….
a
1
n
y
1
+ a
2
n
y
2
+… a
mn
y
m
≥
c
n
Ограничения-неравенства прямой задачи называют также строчечными
ограничениями, а ограничения-неравенства двойственной задачи — столбцовыми.
Всякому строчечному ограничению А
i
Х
≤
b
i
соответствует условие y
i
≥
0, а столбцовому
ограничению A
j
У
≥
с
j
—условие х
j
≥
0.
Условия
А
i
Х
≤
b
i
, у
i
≥
0 (2.2.40)
при фиксированном значении индекса i и условий
AjY
≥
с
j
, x
j
≥
0, (2.2.41)
при фиксированном значении индекса j называются парами двойственных условий
взаимосопряженных задач.
Двойственная пара (2.2.40) называется строчечной, а пара (2.2.41) — столбцовой.
Пример. Дана задача: найти неотрицательные числа х
1
, x
2
, x
3
, х
4
, максимизирующие
целевую функцию
z=x
1
+3x
2
+x
4
при условиях:
≤−++
≤++
.124
;22
4321
431
xxxx
xxx
Составить задачу, двойственную данной задаче. Взаимосвязь между обеими задачами представляется
следующей таблицей (см. табл.2.2.1)
Табл.2.2.2
X
Y
x
1
x
2
x
3
x
4
≤
y
1
1
0 1 2 2
y
2
1
1 4 -2 1
≥
1 3 0 1
B
C
Пользуясь этой таблицей, получаем формулировку двойственной задачи. Требуется
найти неотрицательные числа y
1
, y
2
, обращающие в минимум целевую функцию
z=2y
1
+y
2
при условиях:
≥−
≥+
≥
≥+
122
;04
;3
;1
21
21
2
21
yy
yy
y
yy
Страницы
- « первая
- ‹ предыдущая
- …
- 73
- 74
- 75
- 76
- 77
- …
- следующая ›
- последняя »
