9. Двойственные задачи

Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной или сопряженной по отношению к исходной или прямой задаче.

Дадим определение двойственной задачи по отношению к общей задаче линейного программирования, состоящей, как мы уже знаем, в нахождении максимального значения функции

(1)

при условиях

(2)

(3)

Определение

Задача, состоящая в нахождении минимального значения функции

(4)

при условиях

(5)

(6)

называется двойственной по отношению к задаче (1) – (3). Задачи (1) – (3) и (4) – (6) образуют пару задач, называемую в линейном программировании двойственной парой.

Пара взаимо-двойственных задач может быть экономически интерпретировано сл. Образом: Прямая задача – сколько и какой продукции x_j надо произвести, чтобы при заданных стоимостях единицы продукции c_j объемах имеющихся ресурсов bi и нормах расходов a_ijмаксимизировать выпуск продукции в стоимостном выражении.Двойственная задача какова должна быть оценка единицы каждого из ресурсов yi чтобы при заданных bic_ja_ij минимизировать общую оценку затрат на все ресурсы.

 

Правила построения двойственных задач

Упорядочивается запись исходной задачи (если целевая функция максимизируется, то ограничения неравенства должны быть вида <= если минимизируется то >=), выполнение этих условий достигается умножением соответствующих ограничений на -1.

Если прямая задача решается на максимум то двойственная на минимум, и на оборот.

К каждому ограничению прямой задачи соответствует переменная двойственной задачи и наоборот.

Матрица системы ограничений двойственной задачи получается из матрицы системы ограничений прямой задачи транспонированием .

Свободные члены системы ограничений прямой задачи являются коэффициентами при соответствующих переменных целевой функции двойственной и наоборот

Если на переменную прямой задачи наложено условие не отрицательности то соответствующее ограничение  двойственной задачи записывается как ограничение неравенства, если же нет то как ограничение равенства.

Если какое либо ограничение прямой задачи записано как равенство, то на соответствующую переменную двойственной задачи условие не отрицательности не налагается.

 

Пример

 

MaxZ = -12x1 + 10x2 – 15x3 -11x4

2x1 – 4x2 + x4 >= 3;                             y1

3x1 + x2 + 2x3 + 2x4 = 4;     y2           

4x1 – 5x2 + 2x3>= -1 ;                         y3

-x1 +3x2 + 2x4 >=2;                             y4

-2x1 + x2 – 3x4 = -5;                            y5

X1,x4>= 0; x2,x3 (для любого знака)

Minf  = -3y1 -4y2 + y3 -2y4 + 5y5

 

 

-2y1 -3y2 – 4y3 – y4- 2y5 >= -12

4y1 – y2 +5y3 – 3y4 – y5  =10

2y2 - =-15

 = -15

***>=-11

Y1y3y4 >= 0; y2y5 (любогознака)

MinZ = x1 +2x2 – x3 + x4

Max Z = 4y1 + 6y2 – 8y3

 

 

32	2	0	4	0	3	0
	X1	X2	X3	X4	X5	X6
	Y4	Y5	Y6	Y1	Y2	Y3

Min f = 32

Y* = (0,3,0,2,0,4)

Y2*=3>0 ресурс используется полностью

Y1* =0 ресурс в избытке

Y3* = 0 избыток