Составители:
Рубрика:
134
3.3. Двойственные задачи линейного программирования
и применение теории двойственности
В гл. I было указано, что стандартной задачей максимизации является задача
нахождения неотрицательных чисел
x
1
,
x
2
, . . . ,
x
n
, обращающих в максимум целевую
функцию
F
=
c
1
x
1
+
c
2
x
2
+…+
c
j
x
j
.+…+
c
n
x
n
(3.31)
при условиях:
≤+++++
≤+++++
≤+++++
.......
................................................................
,......
................................................................
,......
2211
2211
111212111
mnmnjmjmm
ininjijii
nnjj
bxaxaxaxa
bxaxaxaxa
bxaxaxaxa
(3.32)
Или в краткой записи
∑
=
==
n
j
jjj
xcxF
1
max)( (3.31')
при условии
∑
=
=≤
n
j
ijij
mibxa
1
,1; (3.32')
.,1;0
njx
j
=≥
Аналогично формулируется стандартная задача минимизации, которая отличается в
записи от стандартной задачи максимизации только знаками неравенств в системе
ограничений (3.32). В стандартной задаче минимизации все ограничения-неравенства
выражаются со знаками неравенств
≥
.
Стандартной задаче максимизации соответствует стандартная задача минимизации,
которая составляется по заданным числовым характеристикам
а
ij
,
b
i
,
c
j
исходной задачи
следующим образом.
Будем называть исходную задачу (3.31), (3.32)
прямой
задачей. Каждому
ограничению-неравенству (3.32) прямой задачи ставится в соответствие неотрицательная
переменная двойственной задачи. Таким образом, число переменных
y
1
,
y
2
,…,
y
т
в двойственной
задаче равно числу ограничений в прямой задаче. Коэффициентами целевой функции
двойственной задачи являются свободные члены
b
1
,
b
2
, ...,
b
т
в ограничениях-неравенствах
прямой задачи. Число ограничений-неравенств в двойственной задаче равно числу
переменных в прямой задаче, так что каждой переменной
x
j
ставится в соответствие
j
-е
ограничение двойственной задачи. Коэффициентами этого
j
-го ограничения являются
коэффициенты
a
1j
,
a
2j
,...,
a
mj
при переменной
x
j
в системе ограничений (3.32) прямой
задачи, т. е.
j
-и столбец
A
j
матрицы системы ограничений, а свободным членом —
коэффициент
c
j
при переменной
x
j
в целевой функции (3.31) прямой задачи. Таким
образом, двойственная задача по отношению к прямой задаче (3.31), (3.32) будет следующая
задача.
Найти неотрицательные числа
y
1
,
y
2
,...,
y
т
,
обращающие в минимум целевую
функцию
G = b
1
y
1
+ b
2
y
2
+
. . .
+b
i
y
i
+ . .. +b
m
y
m
(3.33)
при условиях:
Страницы
- « первая
- ‹ предыдущая
- …
- 132
- 133
- 134
- 135
- 136
- …
- следующая ›
- последняя »
