Составители:
Рубрика:
74
Найти неотрицательный m-мерный вектор
Y=[y
1
,y
2
,…,y
m
], (2.2.37)
который минимизирует скалярное произведение
w = BY (2.2.38)
при условии
А
т
У
≥
С, (2.2.39)
где А
т
. — транспонированная матрица А.
Задача (2.2.37) — (2.2.39) называется двойственной, или сопряженной, задаче
(2.2.34) — (2.2.36). Задача (2.2.34) — (2.2.36) называется прямой. Если считать задачу
(2.2.37) —(2.2.39) прямой, то двойственная ей будет задача (2.2.34) — (2.2.36). Таким
образом, стандартной задаче максимизации соответствует двойственная стандартная
задача минимизации и, наоборот, стандартной задаче минимизации соответствует
двойственная стандартная задача максимизации. Поэтому прямую и двойственную
стандартные задачи называют двойственной, или взаимосопряженной, парой стандартных
задач линейного программирования.
Можно доказать, но на этом мы останавливаться не будем, что или обе
взаимосопряженные задачи имеют решения, или ни одна из них не имеет решения. Таким
образом, из существования решения прямой задачи всегда вытекает существование
решения двойственной задачи и наоборот.
Двойственная задача может быть составлена очень просто, если только помнить,
что во взаимосопряженных задачах вектор коэффициентов целевой функции и вектор
ограничений меняются ролями, а матрица условий одной задачи является
транспонированной матрицей условий другой задачи, и, наконец, знаки неравенств в
системе ограничений той и другой задач имеют противоположный смысл.
Взаимосвязь между двумя задачами можно представить с помощью следующей
таблицы:
Табл.2.2.1
X
Y
x
1
x
2
……………………. x
n
≤
y
1
a
11
a
12
…………………… a
1
n
b
1
y
2
a
21
a
22
…………………… a
2
n
b
2
. . .
. .
. . .
. .
. . .
. .
y
m
a
m
1
a
m
2
……………………. a
mn
b
m
≥
c
1
c
2
……………………. c
n
B
C
Параллельная подробная запись условий обеих задач легко осуществляется с
помощью этой таблицы и выглядит так:
Прямая задача Двойственная задача
Найти неотрицательные числа
х
1
,х
2
,…,х
n
,
максимизирующие целевую функцию
z=c
1
x
1
+ c
2
x
2
+…+ c
n
x
n
при условиях:
a
11
x
1
+ a
12
x
2
+… a
1
n
x
n
≤
b
1
;
Найти неотрицательные числа
y
1
,y
2
,…,y
m
,
минимизирующие целевую функцию
w=b
1
y
1
+ b
2
y
2
+…+ b
m
y
m
при условиях:
a
11
y
1
+ a
21
y
2
+… a
m
1
y
m
≥
c
1
;
Страницы
- « первая
- ‹ предыдущая
- …
- 72
- 73
- 74
- 75
- 76
- …
- следующая ›
- последняя »
