Применение теории двойственности в экономике. Определение двойственной задачи

1.

Глава 2. Применение теории
двойственности в экономике.
2.1. Определение двойственной задачи
Каждой ЗЛП может быть поставлена в соответствие по
определенным правилам другая ЗЛП, которая называется
двойственной задачей. В этом случае исходная ЗЛП
называется прямой задачей.

2.

(1)
х = (x1, x2, …, xn);
b1
b ;
b
m
с = (с1, с2, …, сn);
матрица
a11 , , a1n
A
a , , a
mn
m1
n
Целевая функция
(c, x) c j x j
j 1
Введем вектор двойственных переменных
y = (y1, y2, …, ym)

3.

Построим ЗЛП (2)
(2)
Задача (2) есть двойственная задача к ЗЛП (1).
m
B( y ) (b, y ) bi y i
i 1
Матрица AT – транспонированная матрица A.
D1 область допустимых планов задачи (1), т.е. допустимый
план x D1, а D2 – область допустимых планов задачи (2), т.е.
допустимый план y D2.

4.

Замечание. Так как AT y = y A, то непрямые (структурные)
ограничения в двойственной задаче могут быть записаны
в виде yA c.
Правила построения двойственной задачи для исходной
задачи вида (1):
• Количество переменных в двойственной задаче (2)
равно количеству непрямых (структурных)
ограничений прямой задачи (1).
• Целевая функция исходной задачи задается на
максимум, а целевая функция двойственной задачи –
на минимум.

5.

Матрица коэффициентов системы ограничений А в
двойственной задаче транспонируется.
Вектор коэффициентов целевой функции задачи (1)
становится вектором системы ограничений в двойственной
задаче (2), а вектор правых частей ограничений задачи (1)
становится вектором коэффициентов целевой функции
двойственной задачи (2).
Знаки отношений “ ” в системе ограничений задачи (1)
заменяются на знаки отношений “ ” в ограничениях
задачи (2).

6.

П р и м е р 1.
Количество ограничений прямой и двойственной
задач
Ограничения
Прямая задача
Двойственная
задача
N
M
Прямые
M
N
Непрямые
(структурные)
n+m
m+n
Всего

7.

Утверждение. Задача двойственная к двойственной есть
прямая задача.
Умножим цел. функцию и систему ограничений (2) на (- 1).
(- b, y) max
- ATy - с
(2 )
y 0
z = (z1, z2, …, zn) - вектор, компонентами которого являются
неизвестные в двойственной задаче к задаче (2 ).
Двойственная задача:
(- c, z) min
(-AT)T z - b
z 0.
(2 )

8.

Умножим целевую функцию и ограничения на (-1) и учтем,
что (АT)T = А, тогда:
(с, z) max
Az b
z 0
Задачи (3) и (1) отличаются только обозначениями
переменных, следовательно, утверждение доказано.
(3)

9.

Рассмотрим задачу, двойственную к исходной задаче,
содержащей строгое равенство.
C(х) = с1x1 + с2 x2 + … + сnxn max
a11x1 + a12x1 +…+ a1nxn = b1
a21x1 + a22x2 +…+ a2nxn b2
……………………………
am1x1 + am2x2 +…+ amnxn bm
xj 0,
j 1, n
Первое ограничение задачи:
n
a
j 1
1j
x j b1
n
и
a
j 1
1j
x j b1
(4)

10.

Умножим второе неравенство на (- 1), тогда:
n
C ( x) c j x j max
j 1
n
a1 j x j b1
j 1
n
a1 j x j b1
j 1
n
aij x j bi , i 2, m
j 1
x j 0, j 1, n.
y1
y1
yi
(5)

11.

Двойственная задача (6).
m
B( y ) b1 y1 b1 y1 bi y i min
(6)
i 2
m
a1 j y1 a1 j y1 aij y i c j ,
j 1, n
i 2
y1 , y1 ,
y i 0, i 2, m.
Вынесем b1 в целевой функции и a1j в ограничениях за
скобки.
m
B( y ) b1 ( y1 y1 ) bi y i min
i 2
m
a1 j ( y1 y1 ) aij y i c j ,
i 2
y1 , y1 ,
y i 0, i 2, m.
j 1, n

12.

Введем новую переменную y1 = y 1– y 1, тогда получим ЗЛП:
m
B( y ) bi y i min
i 1
m
a
i 1
ij
yi c j ,
j 1, n
(7)
y i 0, i 2, m.
При этом в (7) y1 может быть как отрицательным, так и
положительным числом, тогда как y 1, y 1 0. (т.к. первое
ограничение содержало знак « = »).

13.

ЗЛП в канонической форме:
(c, x) max
Ax = b
(8)
x 0,
то двойственной задачей к (8) будет (9):
(b, y) min
ATy c
(9)
Задача, двойственная к ЗЛП (10), будет иметь вид (11).
(10)
(11)

14.

П р и м е р.
C ( x) (c, x) min
Ax b
Сначала упорядочим запись прямой задачи.
C ( x) (c, x) min
Ax b
Двойственная задача будет иметь вид:
B( y ) ( b, y ) max
T
A y c
y 0
В структурных ограничениях двойственной задачи стоит
знак “ = ”, поскольку в исходной задаче отсутствуют прямые
ограничения на переменные.

15.

2.2. Экономическая интерпретация двойственной задачи
Рассмотрим ЗЛП:
n
C ( x ) c j x j max
j 1
n
a ij x j bi , i 1, m
j 1
x 0, j 1, n
j
(1)
где х = (x1,…, xn) – вектор выпуска товаров;
сj– прибыль от реализации единицы товара j-го вида;
aij – количество i-го ресурса, идущего на изготовление
единицы товара j-го вида;
bI – запас (наличие) i-го ресурса.

16.

Двойственная задача к задаче (1) :
m
B ( y ) bi y i min
i 1
m
aij y i c j , j 1, n
i 1
y 0, i 1, m
i
Рассмотрим k-е ограничение задачи (2):
(2)
m
a
i 1
ik
y i c k (3)
В правой части неравенства ck - прибыль от реализации
единицы товара k-го вида, которая носит стоимостной
характер, в левой части неравенства тоже стоимостная
характеристика.

17.

a ik
yi
– расход ресурса;
– стоимостная величина.
Вектор y = (y1, y2,…, ym ) – вектор цен на ресурсы.
yi 0, i 1, m.
Естественное требование к ценам со стороны продавца
состоит в следующем: выручка от продажи ресурсов,
расходуемых на изготовление единицы товара k-го вида,
должна быть не меньше, чем прибыль, которую могло бы
получить предприятие от реализации единицы товара k-го
вида, если бы оно отказалось от продажи ресурсов и
направило их на изготовление товаров.

18.

Это требование математически записывается в виде
неравенств (3). Всего таких неравенств n, так как
k 1, n
Кроме того, продавая ресурсы, предприятие
заинтересовано в том, чтобы цены на них были как можно
выше. Однако рыночные цены могут существенно
отличаться от желаемых цен.
Поэтому для установления нижних границ, ниже которых не
имеет смысла продавать ресурсы, предприятию
целесообразно определить минимально возможную
стоимость продаваемых ресурсов.

19.

То есть определить минимум функции B ( y )
m
b y
i 1
при выполнении ограничений (3) и yi 0,
i 1, m
Следовательно, для рациональной продажи ресурсов
необходимо решить двойственную задачу (2).
Заметим, что переменные yi , «внутренние цены»
предприятия («теневые» цены, стоимостные оценки),
которые дают возможность предприятию эффективно
использовать имеющиеся ресурсы.
i
i