运筹学课件——2 线性规划对偶理论

运筹学课件,管理类教辅

运筹学3讲课教师： XXX

运筹学课件,管理类教辅

第二章 线性规划的对偶理论2.1对偶问题 2.2 灵敏度分析

运筹学课件,管理类教辅

2.1 对偶问题1.对偶问题的提出 2.对称的对偶线性规划 3.对偶问题的基本性质 4.对偶单纯形法 5.对偶问题的经济解释

运筹学课件,管理类教辅

一. 对偶问题的提出例：产品 A 原材料 工时定额 单位边际收益

2

2

10

B现有资源

3300

1.5180

12

问1:如何安排生产使总收益最大？

max z 10 x1 12 x2 s.t 2 x1 3 x2 300 2 x1 1.5 x2 180 x1 , x2 0

运筹学课件,管理类教辅

产品 A B 现有资源

原材料 工时定额 单位产品收益

23 300

21.5 180

1012

问2:若企业把资源出租，应如何确定合理的价格？ 出租可获得的收益不得低于自行生产的收益 在满足上述要求的前提下，所定的价格对方愿意接受 目标函数： 约束条件：min w 300 y1 180 y2

2 y1 2 y2 103 y1 1.5 y2 12y1 0, y2 0

非负条件：

运筹学课件,管理类教辅

max z 10 x1 12 x2 s.t 2 x1 3 x2 300 2 x1 1.5 x2 180 x1 , x2 0LP

min w 300 y1 180 y2

s.t

2 y1 2 y2 103 y1 1.5 y2 12y1 0, y2 0DLP

2 3 1、系数矩阵A 2 1.5 2、价值系数 3、资源系数(右项) 4、约束方程 <= 5、目标函数 max

2 2 A 3 1.5 T

资源系数(右项) 价值系数 约束方程 >= 目标函数 min

运筹学课件,管理类教辅

原始问题 max z=CX s.t. AX≤b X ≥0

对偶问题 min w=Yb s.t. YA≥C Y ≥0

max (LP) m

C A ≤

min

b

b

(DLP)

n

AT

≥ CT

nm

运筹学课件,管理类教辅

LP与DLP的对偶关系

标准形式的对偶关系max z CX AX b ( LP ) X 0

min w Yb YA C ( DLP ) Y 0

运筹学课件,管理类教辅

二、对称型对偶线性规划 线性规划具有对称形式的两个条件

所有变量非负 约束条件都是不等式，且目标函数极大化时， 不等式方向为≤,极小化时，为≥

原—对偶线性规划的对应关系 (p43 表2.1 ; 表2.2 ) 三、非对称的线性规划的对偶问题

等式约束的对偶关系 其它非对称约束的对偶关系

运筹学课件,管理类教辅

例：

min z= 2x1+4x2-x3 s.t. 3x1- x2+2x3 ≥ 6 -x1+2x2-3x3 = 12 2x1+x2+2x3 ≤ 8 x1+3x2-x3 ≥ 15 x1≥0, x2≤0, x3 无非负要求(unr)

运筹学课件,管理类教辅

对偶线性规划min z= 2x1+4x2-x3 s.t. 3x1- x2+2x3 ≥ 6 -x1+2x2-3x3 = 12 2x1+x2+2x3 ≤ 8 x1+3x2-x3 ≥ 15 maxw=6y1+12y2+8y3+15y4 s.t. 3y1- y2+2y3+ y4 ≤ 2 -y1+2y2+ y3+3y4 ≥ 4 2y1-3y2+2y3- y4 = -1 y1 ≥ 0,y2 unr ,y3 ≤ 0,y4 ≥ 0

x1≥0

x2≤0

x3: unr(无非负 约束)

原始问题变量的个数(3)等于对偶问题约束条件的个数(3); 原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。 原始问题变量的性质影响对偶问题约束条件的性质，用 表示 原始问题约束条件的性质影响对偶问题变量的性质，用 表示

运筹学课件,管理类教辅

三、 对偶问题的基本性质 1、对称性——对偶问题的对偶问题是原问题

max z CX AX

b ( LP ) X 0代数变换

对偶变换

min w Yb YA C ( DLP )代数变换

Y 0

min z CX'

- AX b ( DLP ) X 0

对偶变换

max w Yb'

- YA C ( LP ) Y 0

运筹学课件,管理类教辅

2、弱对偶性——揭示目标函数值的关系 若X为LP原问题的任一可行解，Y 为任一对偶

可行解，则有Y b CX。

AX b, Y 0, YAX Yb

YA C,X 0, YAX CX

w Yb CX z推论： 1)极大化问题任一可行解的目标函数值是其对偶问题最优值的下界。 2)极小化问题任一可行解的目标函数值是其对偶问题 最优值的上界。

运筹学课件,管理类教辅

例：max z x1 2 x2 3x3 4 x4

min w 20 y1 20 y2 s.t y1 2 y2 1 2 y1 y2 2

s.t (LP)

x1 2 x2 2 x3 3x4 20 2 x1 x2 3x3 2 x4 20 x j 0, j 1,2,3,4

2 y1 3 y2 3(DLP) 3 y1 2 y2 4 y1 , y2 0

1)原问题任一可行解 X=(1 1 1 1) 目标值 z=10 T 10是DLP问题最优目标值的下界 X * 0 0 4 4 z* 28 2)对偶问题任一可行解 Y=(1 1) Y* 1 6 w* 28 5 5 目标值 w=40

40是LP问题最优目标值的上界

运筹学课件,管理类教辅

弱对偶性的推论

3、最优性 — 若X和Y 分别为LP的可行解和对偶可行解 且CX Y b,则X为LP最优解，Y 为DLP最优解。证明：对任意可行解X ' ,由弱对偶性 CX ' Y b CX

则有CX ' CX X为最优解同理，对任意对偶可行解Y ' , Y 'b CX Y b Y 'b Y b Y 为对偶最优解若LP有最优解，则DLP也有最优解，且它们的目标值相等。

运筹学课件,管理类教辅

原始-对偶 问题目标函数值之间的关系1、可行解的目标函数值之间的关系设X、Y分别是原始问题和对偶问题的可行解

z=CX ≤YAX≤ Yb=w2、最优解的目标函数值之间的关系设X*、Y*分别是原始问题和对偶问题的最优解

z=CX*=Y*AX*=Y*b=w