2.1. определение и экономический смысл двойственной злп.
2.1. определение и экономический смысл двойственной злп.
Пусть прямая задача записана в каноническом виде:
n
max (min) f (x) = £ cjxI (2.1)
і=1
n
£ aijxj = b , i=1..m (2.2)
j=1
x, > 0 , j=1..n (2.3)
min (max) g(у) = Y у1Ь1
i=i
m
Y yia4(")Cj , j = 1"n
i=1
yi не ограничены в знаке, i=1..m
(2.4)
(2.5) (2.6)
Из приведенного определения следует, что двойственная ЗЛП строится по следующим правилам:
Каждому ограничению прямой задачи соответствует переменная двойственной задачи, т.е. число переменных двойственной задачи (у 1,..., ym) равно числу ограничений прямой задачи.
Каждой переменной прямой задачи соответствует ограничение двойственной задачи, т.е. число ограничений двойственной задачи равно числу переменных прямой задачи.
. Матрица функциональных ограничений двойственной задачи получается путем транспонирования матрицы функциональных ограничений прямой задачи.
Вектор C целевой функции прямой задачи становится вектором правой части ограничений двойственной задачи, а вектор b правой части прямой задачи вектором целевой функции двойственной задачи.
5) Если целевая функция прямой задачи максимизируется, то
целевая функция двойственной задачи минимизируется, а ограничения
имеют вид -, и наоборот.
Прямая задача
Двойственная задача
max f (x) = (C, x) Г Ax = b
P= Imin f (x) = (C, x) Ax = b
min g (y) =(y,b)
~yA C
(2.7)
у не ограничен в знаке
max g (у) = (у, b) yA < C
(2.8)
x 0
у не ограничен в знаке
Пример 2.1 Пусть прямая задача записана в виде основной ЗЛП:
Max ( c, x), Ax <b (2.9) x < 0
Приведем задачу (2.9) к канонической форме:
max[( C, X) + (0,S)]
Ax + S = b (2.10)
x > 0 , S > 0
Тогда двойственная задача (ДЗ) будет иметь вид: min(y,b)
(2.11)
Уа > C
y > 0.
Пример 2.2.
Прямая задача
max(5x1 +12 x2 + 4 x3)
x1 + 2 x2 + x3 < 10 2X1 X2 + = 8
X1,2,3 > 0.
Прямая задача в каноническом виде
max 5x1 +12 x2 + 4 x3 + 0S1)
x1 + 2 x2 + x3 + S1 = 10 2 X1 X2 + 3 8
X1,2,3 > 0.
S1 > 0
Двойственная задача
min(10y1 + 8 У2)
У1 + 2 У2 > 5 2 У1 У2 > 12 У1 + ^У2 > 4 У1 + 0У2 > 0 У12 не ограничены в знаке.
Ограничение y1 + 0y2 > 0, т.е. y1 > 0является более жестким, чем условие неограниченности у1 в знаке, поэтому двойственная задача может быть записана в следующем виде:
min(10y1 + 8^2)
У1 + 2 У2 > 5 2 У1 У2 > 12 У1 + ЗУ2 > 4 У1 > 0
у2 не ограничена в знаке.
Пример 2.3 Прямая задача
min( 5X1 2X2 ) X1 + X2 > -3 2 X1 + 3X2 < 5
X1,2 > 0
Прямая задача в канонической форме min( 5X1 2X2 + 0 S1 + 0 S2)
X1 + X2 S1 = -3
2 X1 + 3X2 + S2 = 5 Xj > 0, j = 1,2, Sj > 0, j =1,2.
Двойственная задача max( 3 У1 +5 У2 )
У1 + 2 У2 < 5
У1 + 3 У2 < -2
У1 + 0 У2 < 0 0 У1 + У2 < 0
У1,2 не ограничены в знаке. Отбрасывая избыточные ограничения, получаем:
max( 3 У1 +5 У2 )
У1 + 2 У2 < 5
У1 + 3 У2 < -2 У1 > 0 , У2 < 0
Пример 2.4. Прямая задача
max( 5X1 + 6X2 ) X1 + 2X2 < 5
X1 + 5X2 > 3
4X1 + 7X2 < 8
X1 не ограничена в знаке, X2 > 0
Прямая задача в канонической форме max( 5 X1 -5 Xl'+ 6X2 + 0 S1 + 0 S2)
X[X"1 + 2X2 = 5
x1+ x; + 5X2 s1 =3
4 Xl4 x;+ 7X2 + S2 =8
xi,x; > 0, X2 > 0, Sj > 0, j =Гд
Двойственная задача min( 5 УГ +3 У2 + 8 У3)
Уі 2 У2 + 4 У3 > 5
У1 + У2 4 У3 > -5
2 У1 + 5 У2 +7 У3 > 6 0 У1 У2 +0 У3 > 0 0 У1 + 0У2 + У3 > 0
У1,2,3 не ограничены в знаке
Заметим, что первое и второе ограничения двойственной задачи можно заменить одним ограничением в виде равенства, избыточные ограничения на У2 и У3 можно отбросить. Окончательно получаем:
min( 5 У1 +3 У2 + 8 У3) У1 2 У2 + 4 У3 = 5 2 У1 + 5 У2 +7 У3 > 6
У1 не ограничена в знаке У2 < 0 , У3 > 0
Очевидно, что задача, двойственная к двойственной, совпадает с прямой.
Обсуждение Исследование операций в экономике
Комментарии, рецензии и отзывы