2.1. определение и экономический смысл двойственной злп.

2.1. определение и экономический смысл двойственной злп.: Исследование операций в экономике, И.Н. Мастяева, 2003 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Рекомендовано Учебно-методическим объединением по образованию в области статистики в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности 061700 «Статистика» и другим экономическим специальностям.

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

Очевидно, что задача, двойственная к двойственной, совпадает с прямой.

Исследование операций в экономике

Исследование операций в экономике

Обсуждение Исследование операций в экономике

Комментарии, рецензии и отзывы

2.1. определение и экономический смысл двойственной злп.: Исследование операций в экономике, И.Н. Мастяева, 2003 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Рекомендовано Учебно-методическим объединением по образованию в области статистики в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности 061700 «Статистика» и другим экономическим специальностям.