Оптимальное управление в экономике. Матвейкин В.Г - 13 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

2.4. ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
С любой задачей ЛП тесно связана другая линейная задача, называемая двойственной. Первоначальная за-
дача называется прямой (или исходной). Пара симметричных двойственных задач имеет вид
Прямая задача Двойственная задача
max
1
→=
∑
=
n
j
jj
xcz
min
1
→=
∑
=
m
i
ii
ybF
mibxa
i
n
j
jij
,1,
1
=≤
∑
=
njcya
j
n
j
iij
,1,
1
=≥
∑
=
njx
j
,1,0 =≥
miy
i
,1,0 =≥
Экономически пара взаимно двойственных задач может быть интерпретирована, например, так.
Прямая задача, сколько и какой продукции n=jx
j
1,0,≥ надо произвести, чтобы при заданных стоимо-
стях единицы продукции n=jc
j
1,0,≥ объёмах имеющихся ресурсов m=jb
j
1,0,≥
и нормах расходов
n=jm=ia
ij
1,,1,0,≥
максимизировать выпуск продукции в стоимостном выражении?
Двойственная задача, какова должна быть оценка единицы каждого из ресурсов m=iy
i
1,0,≥ чтобы при
заданных количествах ресурсов m=ib
i
1,0,≥ величинах стоимости единицы продукции n=jc
j
1,0,≥ и нор-
мах расходов n=jm=ia
ij
1,,1,0,≥ минимизировать общую оценку затрат на все ресурсы?
2.5. ПРАВИЛА ПОСТРОЕНИЯ ДВОЙСТВЕННОЙ ЗАДАЧИ К ИСХОДНОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРО-
ГРАММИРОВАНИЯ В ОБЩЕМ ВИДЕ
Прямая задача Двойственная задача
max
1
→=
∑
=
n
j
jj
xcz
min
1
→=
∑
=
m
i
ii
ybF
1
1
,1, mibxa
i
n
j
jij
=≤
∑
=
1
,1,0 miy
i
=≥
mmibxa
i
n
j
jij
,1,
1
1
+==
∑
=
i
y – произвольные,
mmi ,1
1
+=
1
,1,0 njx
j
=≥
1
1
,1, njcya
j
m
i
iij
=≥
∑
=
j
x
– произвольные,
nnj ,1
1
+=
nnjcya
j
m
i
iij
,1,
1
1
+=≥
∑
=
1. Упорядочивается запись исходной задачи: если целевая функция задачи исследуется на max, то огра-
ничения должны иметь знак ≤ или =, а если на min, то ограничения должны иметь знак ≥ или =.
2. Каждому ограничению исходной задачи ставится в соответствие двойственная переменная m=iy
i
1,,
и наоборот, т.е. число переменных двойственной задачи равно числу ограничений прямой задачи, а число огра-
ничений двойственной задачи равно числу переменных исходной задачи.
3. Если целевая функция прямой задачи исследуется на max, то целевая функция двойственной задачи ис-
следуется на min, и наоборот.
4. Коэффициенты целевой функции прямой задачи становятся свободными членами системы ограниче-
ний двойственной задачи.
5. Свободные члены системы ограничений прямой задачи становятся коэффициентами целевой функции
двойственной.
6. Матрицы коэффициентов систем ограничений прямой и двойственной задач являются транспониро-
ванными друг к другу.

Страницы