Основы теории систем и системного анализа. Матвеев Ю.Н. - 95 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

95
mib
i
,1, = единиц, максимизировать выпуск продукции в стоимостном
выражении.
Двойственная задача
Какова должна быть цена единицы каждого из m ресурсов, чтобы
при заданных количествах ресурсов
mib
i
,1, = и величинах стоимости
единицы продукции j-го вида
njC
j
,1, = минимизировать общую
стоимость затрат?
Переменные
miz
i
,1,0 =≥ двойственной задачи называются
оценками, или учётными, неявными, теневыми ценами.
Многие задачи ЛП первоначально ставятся в виде исходных или
двойственных задач, поэтому говорят о паре двойственных задач ЛП.
2.11.2. Виды математических моделей двойственных задач ЛП
Математические модели пары двойственных задач могут иметь один
из видов:
Тип
задачи
Исходная задача
Двойственная задача
W
min
=
x
С
T
A
B
x
=
x
≥ 0
F
max
= z
B
T
A
T
Cz ≤
z не ограничен по знаку
Несимметричные
задачи
W
max
=
x
С
T
A
B
x
=
x
≥ 0
F
min
= z
B
T
A
T
Cz ≥
z
не ограничен по знаку
W
min
=
x
С
T
A
B
x
≥
x
≥ 0
F
max
= z
B
T
A
T
Cz ≤
0≥z
Симметричные
задачи
W
max
=
x
С
T
A
B
x
≤
x
≥ 0
F
min
= z
B
T
A
T
Cz ≥
0≥z
Приведем без доказательства теоремы двойственности.
Теорема 1
Если исходная и двойственная задачи ЛП имеют опорные решения, то:
1)
существует оптимальное решение njx
j
,1,
0
= исходной задачи;
2)
оптимальное решение miz
i
,1,
0
= двойственной задачи;
3)
имеет место соотношение
∑∑
==
=
m
i
ii
n
j
jj
zbxC
1
0
1
0
, (2.57)
т.е. max W = min F.

Страницы