Двойственность линейного программирования

1. Двойственность линейного программирования

2.

Правила построения двойственных задач:
1. Если в исходной задаче целевая функция
исследуется на min, то в двойственной задаче она будет
исследоваться на max и наоборот.
2. Если в исходной задаче n переменных и m
уравнений, то в двойственной задаче будет m переменных и
n уравнений.
3. Коэффициенты целевой функции исходной задачи
становятся правыми частями ограничений двойственной
задачи, а правые части системы ограничений исходной
задачи становятся коэффициентами целевой функции
исходной задачи.

3.

4. Матрица
ограничений
двойственной задачи
получается из матрицы ограничений исходной задачи
транспонированием.
5. Если в исходной задаче xk 0, то в двойственной
задаче k-ое ограничение будет неравенством, если же в
исходной задаче xk не имело ограничений на знак, то k-ое
ограничение в двойственной задаче будет равенством.
6. Если в исходной задаче l-ое ограничение неравенство, то в двойственной задаче yl 0 ; если же в
исходной задаче l-ое ограничение - равенство, то в
двойственной задаче нет ограничений на знак yi.

4.

Пример построения двойственной задачи.
Исходная задача
Двойственная задача
3x 2 x 3x 5x min
1
2
3
4
2 x 4 x 5
1
4
3x 2 x 10
3
2
4 x 5 x 3x 7
2
4
1
x , x , x 0
1 2 3
A=
2
0
4
A
T
2
0
0
4
2 y
4 y 3
1
3
3 y 5 y 2
2
3
2 y 3
2
3 y 5
4 y
1
3
0
0
4
3
2
0
5
0
0
3
5
0
3
4
3
2
0
5 y 10 y 7 y max
1
2
3
y 0
1
y знака
2
y 0
3

5.

Лемма 1
Если исходная задача (X) исследуется на max, а двойственная
(Y) на min, то Z ( x) Z ( y )
Лемма 2
*
*
Если Z ( x * ) Z ( y * ) , то x , y – оптимальные планы.
Теорема 1 (1 –ая теорема двойственности)
Если одна из пары двойственных задач имеет оптимальные
планы, то и другая имеет оптимальный план, причем : Z*max = Z*min
Если же в одной из задач целевая функция не ограничена на
ОДЗ, то у другой задачи вообще нет допустимых планов.
Теорема 2
Планы
x* и y* пары двойственной задачи являются
оптимальными тогда и только тогда, когда выполняется:
m
a
ij
i 1
y* c
i
j
*
x
j
0
j 1,...n

6.

Пара симметричных двойственных задач.
Z C X ... C X max
1 1
n n
a x a x ... a x b
11 1
12 2
1n n 1
...
a
x a x ... a x b
m1 1
m2 2
mn n m
x 0( j 1,n)
j
Z b y b y ... b y min
11 2 2
m m
a y a
y ... a y C
11 1
21 2
m1 m 1
...
a y a
y ... a y C
1n 1
2n 2
mn m n
y 0(i 1,m)
i
Пары сопряженных переменных.
Основные
Дополнительные
x1 , x2 ,..., xn ,
xn 1 , xn 2 ,..., xn m
y m 1 , y m 2 ,..., y m n ,
Дополнительные
y1 , y 2 ,..., y m
Основные

7.

Экономический смысл двойственных задач об
использовании ресурсов
Задача I (исходная)
F c1 x1 c2 x2 ... cn xn max
при
ограничениях :
a11 x1 a12 x2 ... a1n xn b1 ,
a x a x ... a x b ,
21 1 22 2
2n n
2
...............................................
am1 x1 am 2 x2 ... amn xn bm
и
условии
неотрицательности
x1 0,
x2 0,
...,
x n 0.
Составить такой план выпуска продукции X x1 , x2 ,..., xn , при
котором прибыль (выручка) от реализации продукции будет
максимальной при условии, что потребление ресурсов по
каждому виду продукции не превзойдет имеющихся запасов.

8.

Задача II (двойственная)
Z b1 y1 b2 y 2 ... bn y n min
при
ограничениях :
a11 y1 a12 y 2 ... a1n y n c1 ,
a y a y ... a y c ,
21 1
22 2
2n n
2
...............................................
a m1 y1 a m 2 y 2 ... a mn y n c m
и
условии
неотрицательности
y1 0,
y 2 0,
...,
y n 0.
Найти такой набор цен (оценок) ресурсов Y y1 , y 2 ,..., y m ,
при котором общие затраты на ресурсы будут минимальными
при условии, что затраты на ресурсы при производстве
каждого вида продукции будут не менее прибыли (выручки) от
реализации этой продукции

9.

Экономический смысл основной теоремы двойственности
План производства X * x1*, x*2,..., x*n и набор цен ресурсов Y * y1*, y*2 ,...., y*m
оказываются оптимальными тогда и только тогда, когда
прибыль
(выручка)
от
продукции,
найденная
при
“внешних”(известных заранее) ценах c1,c2 ,...,cn ,равна затратам
на ресурсы при “внутренних” (определяемым только из
решения задачи) ценах y1, y2,..., ym.
Для всех других планов X и Y обеих задач прибыль (выручка) от
продукции всегда меньше (или равна) затратам на ресурсы.

10.

F 2 x1 3 x2 max
Z 18 y1 16 y2
x1 3 x2 18
2 x x 16
1 2
x2 5
3 x1 21
x1 , x2 0
5 y3 21 y4 min
F
*
y1 2 y2 3 y4 2
3 y1 y2 y3 3
y1 , y2 , y3 , y4 0
max
Z
*
min
24

11.

Число единиц
продукции
x*1 = 6 x*2 = 4
y*5 = 0 y*6 = 0
Превышение
затрат на
ресурсы над
ценой
реализации
Задача 1
Остатки ресурсов (ед.)
x*3 = 0
x*4 = 0
x*5 = 1 x*6 = 3
y*1 = 4/5 y*2 = 3/5 y*3 = 0 y*4 = 0
Условные цены ресурсов
Задача 2
Компоненты оптимального решения двойственной задачи
называются оптимальными двойственными оценками исходной
задачи (скрытые доходы).
Они определяют степень дефицитности ресурса.

12.

Исследование на устойчивость
Исследование на устойчивость –
исследование
диапазона изменения правых частей системы ограничений,
при котором найденное оптимальное решение не
изменяется.
Исследование на чувствительность
При исследовании на чувствительность исследуется
зависимость решения ЗЛП от небольших изменений
коэффициентов в условии задачи. При этом предыдущее
решение
может
стать
либо
недопустимым,
либо
неоптимальным.
• К недопустимости пред. решения могут привести
изменения запасов ресурсов и/или добавление новых
ограничений.
• К неоптимальности пред. решения могут привести
изменение
целевой
функции
и/или
изменение
технологических коэффициентов и/или включение в модель
нового вида производственной деятельности.