线性规划对偶理论及其应用

1、运 筹 帷 幄 之 中,决 胜 千 里 之 外,运筹学,君子曰：学不可以已。 青，取之于蓝而青于蓝；冰，水为之而寒于水。 故不登高山，不知天之高也； 不临深溪，不知地之厚也； 荀子劝学,掌握线性规划对偶理论及其基本经济学意义,教学要求,了解运用对偶理论对线性规划最优解进行 分析的基本方法,会运用对偶理论对一些基本的管理问题进行 经济学分析,第三章线性规划对偶理论,线性规划的对偶问题 对偶规划的基本性质 对偶单纯形法 影子价格和灵敏度分析,重点：对偶转换、对偶单纯形法 难点：对偶性质、灵敏度分析,第三章线性规划对偶理论,某家具厂木器车间生产木门和木窗两种产品，加工木门收入为56元/扇、加工木窗收

2、入为30元/扇，生产 一扇木门需要木工4小时，油漆工2小时；生产一扇木窗需要木工3小时，油漆工1小时，该车间可用本工总工时为120小时，油漆工总工时为50小时问该车间应如何安排生产才能使每日收入最大？ 令该车间每日安排生产木门x1,木窗x2扇，则其数学模型为： max z=56x1+30 x2 s.t 4x1+3x2120 2x1+x2 50 x1,x20 即每日安排生产木门15扇，木窗20扇时，收入最大为1440元,一、对偶问题的提出,最优解为：X=(15,20)， 最优值为1440元,第一节线性规划的对偶问题,假若有一个个体经营者，手中有一批木器家具生产订单，但无人手加工，因此想利用该木器

3、车间的木工与油漆工来加工完成他的订单，它需要考虑付给该车间每个工时的价格 那他应如何定价才能使木器车间觉得有利可图从而愿意替他加工这批订单，同时又使自己所付的工时费用总数最少？ 设w1,w2分别为付给木工、油漆工每个工时的价格，则该个体经营者的目标函数为： min f=120w1+50w2,第一节线性规划的对偶问题,另外，该个体经营者所付的价格不能太低，至少不能低于该车间生产木门和木窗所得到的收入，否则该车间觉得无利可图就不会替他加工这批订单，因此，w1,w2 应满足 4w1+2w2 56 上式可理解：生产一扇木门的木工工时*木工工时价+生产一扇木门的油漆工时*油漆工工时价生产一扇木门的收入

4、3w1+w2 30 上式可理解：生产一扇木窗的木工工时*木工工时价+生产一扇木窗的油漆工时*油漆工工时价生产一扇木窗的收入,第一节线性规划的对偶问题,该个体经营者的数学模型为 min f=120w1+50w2 4w1+2w2 56 3w1+w2 30 W1,w2 0 解得w1=2,w2=24,f=1440,第一节线性规划的对偶问题,第一节线性规划的对偶问题,一、对偶问题的提出,原问题,某工厂甲生产A、B、C三种产品。这三种产品的单位利润分别是60、30、20。生产这三种单位产品所占用M、N、P三种机器的时间如表所示，机器M、N、P每天可供使用的时间分别是48、20、8小时。这三种产品每天生产多

5、少才能使工厂获得最大效益,现在甲厂拟出租机器给乙厂，即甲厂出租机器M、N和P给乙厂，请问甲厂应如何给这三种机器定价,考虑： 1、定价不能太低？ 2、定价不能太高？ 既要保证甲厂利润又必须使乙厂的租金越少越好,第一节线性规划的对偶问题,设M、N、P机器的单位出售价格 分别为 y1 、 y2和y3，针对乙厂， 建立其相应的数学模型,目标：min w=48y1+20y2+8y3,对于A产品而言，甲厂生产一件产品可获利60元， 如果8y1+4y2+2y360，则甲厂宁可自己生产A产品也不可能出售机器的，所以应有约束条件 8y1+4y2+2y360， 同理，从经济利益角度，还有另两个约束条件： 6y1+

6、2y2+y3 30 y1+1.5y2+0.5y3 20,第一节线性规划的对偶问题,当 时，工厂的决策者都能接受，并认为是最优方案,当WZ ，即乙厂所出的租金大于等于甲厂自己生产所带来的利润时，甲厂乐意出租，而乙厂希望W最小，同时又希望得到设备,即针对乙厂的数学模型为,现实意义：如果原问题是在资金有限的情况下产量最大，则相应的对偶问题是在产量有限的情况下使成本最小,第一节线性规划的对偶问题,原问题： max Z=60 x1+30 x2 +20 x3 s.t. 8x1+6x2+ x3 48 M机器 4x1+ 2x2 +1.5x3 20 N机器 2x1+ x2 + 0.5x3 8 P机器 x1,x2

7、，x3 0,对偶问题： Min w= 48 y1 + 20 y2 +8 y3 s.t. 8y1 + 4 y2 +2 y3 60 6y1 + 2y2 +y3 30 y1 + 1.5y2 +0.5y3 20 y1, y2 , y3 0,max,min,第一节线性规划的对偶问题,对偶问题 Min y=bTY s.t. ATYC Y 0,二、对偶问题的一般形式,原问题 Max z=cTX s.t. AXb X 0,第一节线性规划的对偶问题,1)对称(max,)型的对偶变换,目标函数由 max 型变为 min 型 当原问题有n个决策变量，则对偶问题有n个约束条件。对偶问题的第一约束条件对应的是原问题中的

8、x1变量，对偶问题的第二个约束条件对应的是原问题中的x2变量，依此类推。 当原问题有m个约束条件，则对偶问题有m个决策变量。对偶问题的y1变量对应的是原问题中的第一约束条件，对偶问题的y2变量对应的是原问题中的第二约束条件，依此类推。 原问题的目标函数第i个变量的价值系数变换为对偶问题中第i个约束条件的右端项,第一节线性规划的对偶问题,原问题的右端项 b 变换为对偶问题的目标函数价值系数 原问题的技术系数矩阵 A 转置后成为对偶问题的技术系数矩阵 原问题与对偶问题互为对偶 对偶问题可能比原问题容易求解,1)对称(max,)型的对偶变换,第一节线性规划的对偶问题,2)非对称型对偶问题,约束条件的

9、类型(规范与否)与非负条件相互对应 非标准的约束条件类型对应非正常的非负条件 对偶变换是一一对应的,第一节线性规划的对偶问题,例3.1,怎么样， 没问题吧,第一节线性规划的对偶问题,求该问题的对偶问题,求该问题的对偶问题,令u1=y1,u2=-y2,u3=-y3则得,第一节线性规划的对偶问题,定理3.1 （对称性定理） 对偶问题的对偶问题是原问题,根据对称性定理，在任一对偶问题中，可以把其中的 任何一个称为原问题，而把另一个称为其对偶问题,第二节对偶规划的基本性质,一、对称性,证:由于X0,Y0分别为原问题和对偶问题的可行解,故有,定理3.2 （弱对偶定理） 对偶问题(min)的任何可行解Y0

10、，其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值,第二节对偶规划的基本性质,定理3.3 （主对偶定理） 如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解所对应的目标函数值相等,第二节对偶规划的基本性质,设X0，Y0分别为原问题和对偶问题的一个可行解， 则对于原问题的任一个可行解都有 CXY0b 对偶问题的任一个可行解Y，均有 YbCX0 故原问题与对偶问题都有最优解,max,min,min,若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0, Y0分别是相应问题的最优解 证：由弱对偶定理可知,定理3.4 （最优解判别定理,第二

11、节对偶规划的基本性质,CX0,Y0b,CX,CX0,CX,Y0b,CX0,Yb,Y0b,Yb,所以，X0,Y0分别是相应问题的最优解 证毕,定理3.5松驰性定理 设x0,y0分别是原问题和对偶问题的可行解， 则x0,y0是最优解的充要条件是对所有的i,j，下列关系成立： 如果xj00 ，则有y0pj=cj 2. 如果y0pjcj,则有x0=0 3. 如果y0i0，则有Aixi0 =bi 4.如果Aixi0 b,则有yi0 =0 其中，pj是A的第j 列，Ai是A的第i行,第二节对偶规划的基本性质,例3.2已知线性规划问题 Max z=x1+2x2+3x3+4x4 s.T x1+2x2+2x3+

12、3x4 20 2x1+x2+3x3+2x420 x1 ,x2 ,x3 , x4 , 0 其对偶问题的最优解为W=(1.2,0.2)T，试根据对偶理论求出原问题的最优解 解，该原问题的对偶问题为： min Y=20w1+20w2 s.T w1+2w2 1 (1) 2w1+w2 2 (2) 2w1+3w2 3 (3) 3w1+2w2 4 (4) w1,w2 0 将对偶问题的最优解代入，得到(1),(2)为严格不等式，故由互补松驰性质得到 X1=x2=0 又w1,w20，由松驰性质得到原问题约束条件应取等号即 w10 2x3+3x4=20 w2 0 3x3+2x4=20， 解方程组，得x3=x4=4

13、 故原问题的最优解为(0,0,4,4,第二节对偶规划的基本性质,w1+2w21 2w1+w22 2w1+3w2=3 3w1+2w2=4,x1=0 x2=0,例3.3已知线性规划问题 Max z=2x1+x2+5x3+6x4 s.T 2x1 + x3+ x4 8 2x1+2x2+x3+2x412 x1 ,x2 ,x3 , x4 , 0 其对偶问题的最优解为w=(4,1)T，试根据对偶理论求出原问题的最优解 解，该原问题的对偶问题为： min Y=8w1+12w2 s.t 2w1+2w2 2 (1) 2w1+2w22 x1=0 2w2 1 (2) 2w21 x2=0 w1+ w2 5 (3) w1

14、+w2=5 w1+2w2 6 (4) w1+2w2=6 w1,w2 0 将对偶问题的最优解代入，得到(1),(2)为严格不等式，故由互补松驰性质得到 X1=x2=0 又w1,w20，由松驰性质得到原问题约束条件应取等号即 W10 x3+x4=8 W20 x3+2x4=12，解方程组，得x3=x4=4 故问题的最优解为（0,0，4,4,第二节对偶规划的基本性质,第三节对偶单纯形法,一、对偶单纯形法原理 对偶单纯形法是利用对偶原理求解原问题的一种方法（而不是求解对偶问题的方法） 对偶单纯形法基本思想是：首先从原问题的一个对偶可行的基本解(它不是原线性规划问题的可行解)出发，求改进的对偶可行的基本解

15、，向原问题的 可行域逼近，当求到对偶可行的基本解是原问题的可行解时，就得到了最优解,原单纯型迭代要求每步都是基础可行解 达到最优解时，检验数 cjzj 0 (max) 或 cjzj 0 (min) 但对于(min, )型所加的剩余变量无法构成初始基础可行解，因此通过加人工变量来解决 大M法和二阶段法较繁 能否从剩余变量构成的初始基础非可行解出发迭代，但保证检验数满足最优条件， cjzj 0 (max) 或 cjzj 0 (min) 每步迭代保持检验数满足最优条件，但减少非可行度 如何判断达到最优解 如何保证初始基础解满足最优条件,考虑对偶线性规划问题 min z=cx s.t Ax=b x0

16、其中A=(p1,p2,pn) B=(b1,b2,.bn) Bi可以是任意数,第三节对偶单纯形法,二、对偶单纯形法的计算步骤： 1、给定一个初始对偶可行的基本解，设相应的基为B； 2若 ，则停止计算，现行对偶可行的基本解为最优解。否则令 ，则该行所对应的变量xr 为换出基的变量； 3若对所有j， ，则停止计算，原问题无可行解。否则，令 则 为换入基的变量； 4以 为主元进行主元消去，返回2,第三节对偶单纯形法,标准化,乘以(-1,初始对偶单纯形表,出基,进基,主元,直到B0，停止,第三节对偶单纯形法,为了得了初始基本解，可用大M法和两阶段法,例,因为B0，且所有检验数 cj-zj0,运算结束，得

17、到最优解为x1=0,x2=1 最优目标值为 fmin=1,表二,表三,第三节对偶单纯形法,例3.4用对偶单纯形法求解线性规划,解：在第2个约束方程的两边同乘以-1，然后引入变量x4,x5得,第三节对偶单纯形法,表一,表二,用对偶单纯形法求解得最优解,最优目标函数值 ：fmin=2/3,第三节对偶单纯形法,例3.5 某工厂有生产A、B两种化工产品 的能力，生产一千克A产品需要2小时，花费成本为2元，而生产一千克B产品则需要1小时，成本为3元，下个月的总生产时间是600小时，公司决定A，B的总产量至少为350千克，此外公司的一个主要客户订购了125千克A产品的要求必须满足，在满足客户要求的前提下，

18、公司应怎样安排生产计划，才能尽量降低成本,解 设A产品的产量为x1千克，B产品的产量为x2千克， 则建立相应模型,Min z=2x1+3x2 s.t x1 125 x1+x2 350 2x1+x2600 x1,x2 0,第三节对偶单纯形法,在第一、二两个约束条件两边同乘以-1，然后引入变量x3,x4,x5，化为如下形式,Minz=2x1+3x2 s.T -x1 +x3 =-125 -x1-x2 +x4 =-135 2x1+x2 +x5=600 x1,x2,x3,x4,x50,第三节对偶单纯形法,此时所有b且所有检验数大于等于0，所得得到最优解为 x1=250,x2=100,x3=125 最优值

19、为800,第三节对偶单纯形法,三、单纯形算法和对偶单纯形算法之差别,第三节对偶单纯形法,四、原问题检验数与对偶问题的解的总结 在主对偶定理的证明中我们有：对偶(min型)变量的最优解等于原问题松弛变量的机会成本，或者说原问题松弛变量检验数的绝对值 不管原问题是否标准，在最优解的单纯型表中，都有原问题虚变量(松弛或剩余) 的检验数对应其对偶问题实变量 (对偶变量)的最优解，原问题实变量(决策变量) 的检验数对应其对偶问题虚变量 (松弛或剩余变量)的最优解,第三节对偶单纯形法,第三节对偶单纯形法,Max z=4x1+3x2+7x3 s.T x1+2x2+2x3 100 3x1+x2+3x3 100

20、 x1.x2.x30,解：其对偶问题为： Min w=100y1+100y2 s.t. y1+3y2 4 2y1+y2 3 2y1+3y2 7 y1,y2 0,例3.6,原问题求解（单纯形法,第三节对偶单纯形法,得到最优解为x=(0,25,25), 松驰变量的检验数为（1/2，2,Max z=4x1+3x2+7x3 s.T x1+2x2+2x3 100 3x1+x2+3x3 100 x1.x2.x30,对偶问题求解(对偶单纯形法,第三节对偶单纯形法,得到最优解Y=(1/2,2)T, 松驰变量对应的检验数为(0,25,25,Min w=100y1+100y2 s.t. y1+3y2 4 2y1+

21、y2 3 2y1+3y2 7 y1,y2 0,最优解为：x=(0,25,25)T，松驰变量的检验数为（1/2，2,原问题(max型)最优表,对偶问题(min型)最优表,最优解为：X=(1/2,2)T,剩余变量对应的检验数为(0,25,25,第三节对偶单纯形法,结论： 若是max型(单纯形法) 在最优表中，基变量对应的解为原问题(max)的最优解，松驰变量的检验数的相反数对应为对偶问题(min)的最优解 若是min型 (对偶单纯形法) 基变量对应的解为本身问题的(min)的最优解，剩余变量的检验数对应为对偶问题(max)的最优解 因此，针对线性规划问题，只要解原问题或对偶问题其中之一就可以,第三

22、节对偶单纯形法,思考题： 1、如有原问题为 Max z=2x1+5x2 s.t x1 4 2x2 12 3x1+2x2 18 x1.x20 利用单纯形法求得最优表如右表， 问其对偶问题最优解为（ ） A, (2,6,2) B, (0,-11/6,-2/3) C, (0,11/6,2/3) D, (4,12,18,第三节对偶单纯形法,2、某问题为 Min w=4u1+12u2+18u3 s.T u1+3U32 2u2+2u35 u1,u2,u30 利用对偶单纯形法求得最优，如右表所示，问对偶问题的最优解为：（） A, (2,6) B, (-11/6,-2/3) C, (11/6,2/3) D,

23、(2,5,第三节对偶单纯形法,第四节影子价格,二、影子价格和对偶价格,约束条件右侧（即资源）每增加1个单位，由由此引起最优目标函数值的增加量，就等于与该约束条件相对应的对偶变量的最优解值。 对偶解的经济含义：资源的单位改变量引起目标函数值的增加量，经济学上称为影子价格。它度量了约束条件对应的那种资源的价值,第四节影子价格,在对偶问题的互补松弛性质中有 如果某种资源 bi未得到充分利用时，该种资源的影子价格为零； 如果某种资源bi已完全耗尽，则该种资源的影子价格不为零 资源的影子价格越高，表明该种资源的贡献越大,第四节影子价格,30,20,10,例3.7 max Z=5x1+4x2 s.t. x

24、1+3x2 90 2x1+ x2 80 x1+ x2 45 x1,x2 0 由图示可知最优点为 B(35，10） 最优值为215,100,80,60,40,20,20,40,60,80,x1,100,B,三、影子价格的图解法,第四节影子价格,20,10,第1种资源增加1单位时 max Z=5x1+4x2 s.t. x1+3x2 91 2x1+ x2 80 x1+ x2 45 x1,x2 0 由图示可知最优点为 B(35,10) ,最优值为215 故资源1的影子价格为0,100,80,60,40,20,20,40,60,80,x1,100,B,第四节影子价格,30,20,10,第2种资源增加1单

25、位时 max Z=5x1+4x2 s.t. x1+3x2 90 2x1+ x2 81 x1+ x2 45 x1,x2 0 由图示可知最优点为B （36，9），最优值为216 故资源2的影子价格为1,100,80,60,40,20,20,40,60,80,x1,100,B,第四节影子价格,20,10,第3种资源增加1单位时 max Z=5x1+4x2 s.t. x1+3x2 90 2x1+ x2 80 x1+ x2 46 x1,x2 0 由图示可知最优点为 B(34，12），最优值为218,故C的影子价格为3,100,80,60,40,20,20,40,60,80,x1,100,B,第四节影子价

26、格,第四节影子价格,在最优表中，松驰变量的检验数与对偶决策变量是一一对应的 Max()松驰变量的检验数的相反数为对偶问题的最优解 Min() 检验变量的检验数就为对偶问题的最优解 因此，可知 Max()松驰变量的检验数的相反数就为相应资源的影子价格 Min() 检验变量的检验数相应资源的影子价格,由上述关系可知，影子价格其实就是对偶问题的最优解,决策变量、影子价格之间的对应关系,例3.8：求下列原问题的最优解及影子价格和对偶问题的最优解及影子价格。 min z=4x1+7x2 +8x3 s.t. x1+ x2 3 x2 +2x3 1 （LP） x1+ x2 + x3 8 x10,x20,x30

27、,其对偶问题为： max w=3u1+u2 +8x3 s.t. U1 + u3 4 u1+u2 + u3 7 （LD） 2u2 + u3 8 u10,u20 ,u30,求解（LP）得最优解为x*=7.5, 0, 0.5；最优值为34,求解（LD）得最优解为u*=0，2，4；最优值为34,所以（LP）的影子价格是：0，2，4 ；（LD）的影子价格为7.5, 0, 0.5,第四节影子价格,四、影子价格的经济含义 1、是否将设备用于外加工或出租 若租金高于某设备的影子价格，则可以出租，否则不宜出租。 2、是否将投资用于购买设备，以扩大生产能力 若市场价低于某设备的影子价格，可考虑买进设备，若高于，则

28、不宜买进 市场价格是由市场决定的，一般较稳定的，而影子价格是有赖于资源的利用情况，是未知数,第四节影子价格,解：x1：产品甲的计划生产量；x2：产品乙的计划生产量，则有如下线性规划问题： max z=7x1 + 12x2 (总销售收入) s.t. 9x1 + 4x2 360 (煤资源限制) 4x1 + 5x2 200 (电资源限制) 3x1 + 10 x2 300 (油资源限制) x1 0，x2 0 (非负条件,第四节影子价格,例3.9：A工厂计划生产甲、乙两种产品。每千克产品的销售价格和能源消耗量、以及能源资源见表3-26，怎样安排生产计划才能使A工厂获益最大,表一,表二,第四节影子价格,表

29、三,原问题的最优解为X(20,24)T, 对应的对偶价格，也就是影子价格为 (0,1.36,0.52,所以，煤、电、石油的影子价格分别为：0、1.36、0.52,理论上，如果一个生产计划是最优的，则该计划必然会耗尽某些资源。 通过比较可知，应首先增加电资源，因为它能导致更多的生产收入，即每增加1度电能使生产收入增加1.36。而如果1度电的价格高于1.36，对企业来讲就不划算，反之如果低于1.36，则应购买电资源进行生产,第四节影子价格,原问题的最优解为X(20,24)T, 对应的对偶价格，也就是影子价格为(0,1.36,0.52,根据影子价格还可制定新产品的价格，如上例的A工厂要生产一种新产品

30、，如果每单位新产品需耗用煤、电、石油分别是5、10、3单位，则新产品的价格必须大于5*0+10*1.3+3*0.52=15.16 如果售价低于15.16，生产该产品就是不划算的。 根据影子价格还可以分析生产工艺的改变对资源节约所带来的收益。 例如，如果A工厂经过工艺改造后使石油节约了2%，则带来的经济收益为 3002%0.52=3.12,第四节影子价格,相当于生产成本,五、利用excel求影子价格 在报告列表框中选择“敏感性报告,影子价格,第四节影子价格,Max z = 7x1 + 12x2 s.t. 9x1 + 4x2 360 4x1 + 5x2 200 3x1 + 10 x2 300 x1

31、 0，x2 0,Min g = 360y1 + 200y2 + 300y3 s.t. 9y1 + 4y2 + 3y3 7 4y1 + 5y2 + 10y3 12 y1 0，y2 0，y3 0,第四节影子价格,在线性规划中，我们假定模型的系数都是已知常数。 而在实际中，这些系数往往是通过估计、预测或人为决策得到的，不可能很准确，更不可一成不变，灵敏度分析就是研究当线性规划问题中的系数发生变化时，对函数最优解的影响程度 灵敏度分析主要研究以下两个问题： （1）这些系数中的一个或多个发生变化时对已求得的线性规划问题最优解的影响。 （2）若原最优基不再是最优时，如何用最简便的方法找到新最优解和最优值,

32、一、灵敏度分析概念,第五节灵敏度分析,设最优解为XB=B-1b，XN=0，其中B是最优可行基,考虑模型,第五节灵敏度分析,单纯形法 max型 最大检验数 最小比 检验数小于等于0 对偶单纯形法 max型 最小b 最小比 所有b大于等于0,第五节灵敏度分析,最优表,1）如果非基变量Xk 的系数Ck变为CK时，此时zj=CBB-1Pj不变,这种情况只引起一个检验数的变化。 如果检验数（CK zk）0 则原来问题的最优解也是新问题的最优解 如果检验数（CK -zk ）0 则改变后Xk为进基变量，把原来最优单纯形表中的Ck-Zk换成Ck-Zk，然后用单纯形表求新问题的最优解,1、目标函数系数（C）的变

33、化,第五节灵敏度分析,例3.10已知线性规划问题 Max z=-5x1+5x2+13x3 s.T -x1+ x2+ 3x3 20 12x1+4x2+10 x390 x1 ,x2 ,x3 0 先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化.（1）目标函数x3的系数由13变为8 解，将原问题引入松驰变量化为标准，通过两步迭代得到最优单纯形表,第五节灵敏度分析,X3为非基变量，其变化后的检验数为 3 CK zk85*3+0*(-2)=-70，则用3代替原最优解x3的检验数，并以x3为进基变量，继续迭代,3,第五节灵敏度分析,例3.11， 考虑例2.1，即其线性规划为,问中档球

34、袋的利润即X1的系数在什么范围内变化时，公司的最优生产计划不变,第五节灵敏度分析,目标函数系数在什么范围变化时，目标函数的最优解不会 发生变化，称这样的范围为可行最优范围,解：原问题引入松驰变量化为标准形经过迭代得最优单纯形表为,设中档球袋的利润变化C时，令,C,第五节灵敏度分析,要使原问题最优生产计划不变，也就是最优解不变， 则必须所有检验数0，所以令,1.249 C -4.3750,1.875 C -6.9380,故得X1系数的最优可行范围： -3.7 C 3.5,即当X1在6.3,13.5此范围内变化， 最优解不变，为X=（540,252） 目标函数值变为：z=(10+ C) x19x2

35、7668540 C,可行最优范围,第五节灵敏度分析,最优解变化,Max Z = 40 x + 50y利润 s.t. 1x + 2y 40时间约束 4x + 3y 120人力约束 x, y 0非负约束,利用图解法求最优可行范围，考虑如下模型,第五节灵敏度分析,最优解变化,第五节灵敏度分析,即当目标函数的斜率满足- 4/3 k目标- 1/2时，Q仍为最优解 也就是- 4/3 c1/c2- 1/2时，Q仍为最优解 假设c1变化C ,则解不等式 - 4/3 （c1 C） /c2- 1/2 即得C 。 解上述不等式 - 4/3 （40 C） /50- 1/2 15 C80/3 当c1在上述范围内变化时，

36、最优解不变,第五节灵敏度分析,如果检验数（CK zk）0 则原来问题的最优解也是新问题的最优解,但最优值发生变化 如果检验数（CK -zk ）0 则以最终单纯形表为基础，换上变化后的价值系数和检验数，继续迭代可以求出新的最优解,第五节灵敏度分析,2）如果基变量的系数ck变为ck时，此时，影响检验数和目标函数值,例3.12已知线性规划问题 Max z=2x1-x2+x3 s.T x1+x2+x3 6 -x1+2x2 4 x1 ,x2 ,x3 0 先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化.（1）目标函数变为max z=4x1-x2+x3 解，将原问题引入松驰变量化为标

37、准，通过两步迭代得到最优单纯形表,故原问题的最优解为X=(6,0,0,0,10)T，最优值为max z=12,相当于x1的系数变化了C2 方法一：直接将C加到x1的检验数上得到新的检验数，并继续迭代 方法二：求变化后的x1检验数2 然后继续迭代,第五节灵敏度分析,故原问题的最优解为X=(6,0,0,0,10)T，最优值为max z=24,例3.13已知线性规划问题 Max z=2x1-x2+x3 s.T x1+x2+x3 6 -x1+2x2 4 x1 ,x2 ,x3 0 先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化.（1）目标函数变为max z=2x1+3x2+x3

38、解，将原问题引入松驰变量化为标准，通过两步迭代得到最优单纯形表,故原问题的最优解为X=(6,0,0,0,10)T，最优值为max z=12,求变化后的x2检验数2 然后继续迭代,第五节灵敏度分析,即目标函数改变后，最优解变为： X=(8/3,10/3,0,0,0)T,最优值为max z=46/3,第五节灵敏度分析,3-2*1-0*3,2、约束条件右边值的变化,设bb+b ,由最优表可知，改变的只是表中第三列，右端列 基变量的取值由XB=B-1b B-1(b+ b) 目标函数值由-Z=-CBB-1b -CBB-1(b+ b,1）如果XB=B-1(b+ b) 0 则原来的最优基不变，但基变量的取值

39、和目标函数将发生变化此时XB为新问题的最优解，Z为新问题的最优值,第五节灵敏度分析,例3.12， 考虑例2.1，即其线性规划为,当剪裁部门的时间再增加20小时，同时定型部门增加100小时，考虑对公司利润的有如何影响,第五节灵敏度分析,解：用单纯形法求解新问题得初始表与最终单纯形表为,B-1,第五节灵敏度分析,X=B-1b,约束条件的右端值,B-1b,1.875 0 -1.312 0 -0.937 1 0.156 0 -1.2 0 1.875 0 -0.344 0 0.14 1,650 600 808 135,158.25 116.875 702.5 25.187,0,第五节灵敏度分析,630

40、600 708 135,b,650 600 808 135,b,所以最优基不变，仍为(x2,x4,x1,x6)，即最优解为 x2=158.25，x4=116.875,x1=702.5,x6=25.187, X3=x5=0 此时，目标函数z=10 x1+9x2=8449.25 增加利润为8449.25-7668=781.3 也等于影子价格20*4.375+100*6.938=781.3,158.25 116.875 702.5 25.187,252 120 540 18,第五节灵敏度分析,2）如果B-1b 0 则原来的最优基不再是新问题的可行基，但所有检验数0，所以现行基本解是对偶可行的基本解，

41、 此时，将最优表中的右端列修改为：B-1b，然后用对偶单纯形法求解新问题,第五节灵敏度分析,例3.13已知线性规划问题 Max z=-5x1+5x2+13x3 s.T -x1+x2+3x3 20 12x1+4x2+10 x390 x1 ,x2 ,x3 0 分析在下列各种条件下，最优解分别有什么变化. （1）约束条件的右端值由20变为30 （2）约束条件对应的b1的在什么范围内变化时，最优基不变 解，（1）引入松驰变量,利用单纯形法得到最优单纯形表,最优解为X=(0,20,0,0,10)T,最优值为max z=100,第五节灵敏度分析,利用对偶单纯形法（max)型求解 Minbi出基 最小比进基

42、,存在值小于0， 即用对偶单纯形法继续求解,第五节灵敏度分析,此时线性规划问题的最优解发生了变化，其最优解为 X（0，0,9,3,0)T 目标函数值为z=117,第五节灵敏度分析,2）约束条件对应的b1的在什么范围内变化时，最优基不变 解：假设b1的变化范围为b,则依题意得,由最优表可知B1,0 -4 1,要使原问题的最优基不变，必须满足B-1b 0,0,解不等式 20 b0 10-4 b 0 得 -20 b 10/4 即b1的最优可行范围为-20,10/4,第五节灵敏度分析,3、变量个数的变化,增加一个新变量在实际问题中就是增加一种新产品，设增加的变量为Xi， B-1是原问题的最优基,如果判

43、别数=Ci-Zi=Ci-CBB-1Pi 0 则新问题最优解与原问题相同，只需将 P=B-1Pi和直接写入单纯形表中即可 如果Ci-Zi0 则将Pi=B-1Pi和加入单纯形表后，继续用单纯形法计算,第五节灵敏度分析,例3.14 考虑例2.1，即其线性规划为,公司领导决定增加一种新款产品，经市场调研，该新款产品的利润可达12.85元，每件新产品需要0.8小时剪裁，1小时缝合，1小时定型，0.25小时检验和包装，其最优生产计划有什么变化,第五节灵敏度分析,解：设X7为生产新款产品的数量，则例2.1的数学模型改变为,第五节灵敏度分析,CB=(c2,c4,c1,c6)=(9,0,10,0), b=(63

44、0,600,708,135)T 对于新问题，因为c7=12.85, P7=(0.8,1,1,0.25)T, 所以,2.41250,因为原问题的最优解变量为x2,x4,x1,x6，相应的,由于70，则继续计算,第五节灵敏度分析,在原问题最优单纯形表中的右端加入P7列得,因为c7-z70，原问题的最优解发生变化，继续用单纯形法求解,最优解为 (280, 0, 91.6, 32, 0, 0, 428) ，最优值为z=8299.8,单纯形法,第五节灵敏度分析,4、约束条件个数的变化,当增加一个约束条件时： （1）如果原问题的最优解满足增加的约束条件，则它也是新问题的最优解， （2）如果原问题的最优解不

45、满足新增加的约束条件，则需要把新约束条件增加到原来单纯形表中重新求解,第五节灵敏度分析,例3.15已知线性规划问题 Max z=-5x1+5x2+13x3 s.T -x1+x2+3x3 20 12x1+4x2+10 x390 x1 ,x2 ,x3 0 分析在下变为列各种条件下，最优解分别有什么变化. （1）增加一个约束条件2x1+3x2+5x3 50 解，将原问题引入松驰变量，利用单纯形法得到最优单纯形,最优解为x=(0,20,0,0,20)T ,最优值为max z=100,咋办,第五节灵敏度分析,将新的约束条件引入松驰变量x6，得： 2x1+3x2+5x3 +x6= 50 并加入到单纯形表中

46、最后一行得表四,最优解变为 x=(0,25/2,5/2,0,15,0)T 最优值为： Max z=90,在每一张表中，基变量对应于单位矩阵,第五节灵敏度分析,5、约束条件系数矩阵的变化,当系数矩阵A=(P1，P2， ，P n)，B是最优解基矩阵,1)当非基列Pj改变为 Pj时，判别数变为,Cj-Zj=Cj-CBB-1Pj yj=B-1Pj,如果检验数Cj-Zj 0，则原来的最优解也是新问题的解,如果检验数Cj-Zj 0，此时，将yj列改成yj，判别数cj-zj改 为cj-zj，把Xj作为进基变量，继续迭代,2)当基列Pj改变为Pj 时，基矩阵将发生很大的变化，此时，需要用单纯形法从新计算,第五

47、节灵敏度分析,解：原问题引入松驰变量化为标准形，通过两步迭代得到最优表,第五节灵敏度分析,故线性规划问题的最优解不变,第五节灵敏度分析,例3.17已知线性规划问题 Max z=2x1+3x2 s.T 2x1+2x2 12 x1+2x2 8 4x1 16 4x2 12 x1 ,x2 0 问在下列条件下，最优解有什么变化？ （1）原问题增加一个变量x7,其系数列向量为 在目标函数中的系数为5， (其实际意义相当于增加一个新产品) (2)x1的系数列向量由 变为 x1的目标函数系数由2 变为4(相当于产品的工艺条件和价格发生变化,3 2 6 3,2 1 4 0,3 2 5 2,第五节灵敏度分析,3)

48、增加一个约束条件2x1+2.4x212 解，对原问题引入松驰变量化为标准形，通过迭代得到最优表,最优解为：X=(4,2,0,0,0,4)T 最优值max z=14,第五节灵敏度分析,1)由条件可知p7,3 2 6 3,由于7=c7-CBB-1P7,因此，增加变量x7后，最优解发生变化，为了修改最优表， 还须计算出B-1p7,第五节灵敏度分析,将B-1p7和7放入最优表中的最后一列得,单纯形法，继续迭代,第五节灵敏度分析,新的最优解为：X=(1,3/2,1,0,0,0,2)T 最优值为：max z=16.5,2)记条件改变后的变量为x1 ，则有,因此原最优解发生变化，计算B-1p1,第五节灵敏度

49、分析,B-1p1是变化后的x1的列向量，1是x1变化的检验数， 将新的数据代入原表得,X1是基变量,因为x1处在基变量的位置，应将x1的系数和列向量化为单位向量， 得表七,第五节灵敏度分析,所以，条件改变后，新的最优解为：X=(16/5,4/5) Max z=15.2,第五节灵敏度分析,3)在新增加的约束条件中，引入松驰变量x7，得： 2x1+2.4x2+x7=12 加入最优表中的最后一行，得表八,X1,x2是基变量,第五节灵敏度分析,利用max型的对偶单纯形法,添加约束条件后，最优解为x1=3,x2=5/2 max z=27/2,第五节灵敏度分析,当Excel已经找出了线形规划问题的最优解时

50、，屏幕上就会出现一个“规划求解结果”的对话框（图3-3）。如果这个解就是你所要的，在“报告”一栏里选择“敏感性报告”，单击“确定”，有关灵敏度分析的报告就会保存在同一个Excel工作簿的另外一张工作表上。对于球袋公司，我们得到最优解所在的工作表如图2-7和敏感性分析所在的工作表如图3-4,图 3-3,图 2-7,利用计算机管理软件进行灵敏度分析,第五节灵敏度分析,图 3-4,第五节灵敏度分析,此报告中将包含缩减成本、影子价格、目标系数(允许有小量增幅)以及右侧约束区域,注：必须选择 “假定线性模型” 才能提供完整的敏感性报告,接受求解结果，并将其输入可变单元格中,用Excel对例3.8的敏感性

51、报告,第五节灵敏度分析,在不改变最优解结构的前提下，单个目标系数的可变上下限,如果其中有0出现，表明存在多个最优解,仅当资源增幅在允许的范围内，才能利用影子价格进行分析,即产品的边际收入与按影子价格折算的边际成本之差。当递减成本小于零时，表示不应该安排该产品的生产,第五节灵敏度分析,列出目标单元格和可变单元格以及它们的初始值、最终结果、有关约束条件的信息,运算结果报告,列出目标单元格和可变单元及其数值、在满足约束条件和保持其它可变单元格数值不变情况下的上下限和目标值,极限值报告,第五节灵敏度分析,原问题： max Z=60 x1+30 x2 +20 x3 s.t. 8x1+6x2+ x3 48 M机器 4x1+ 2x2 +1.5x3 20 N机器 2x1+ x2 + 0.5x3 8 P机器 x1,x2，x3 0,对偶问题： Min w= 48 y1 + 20 y2 +8 y3 s.t. 8y1 + 4 y2 +2 y3 60 6y1 + 2y2 +y3 30 y1 + 1.5y2 +0.5y3 20 y1, y2 , y3 0,max,min,一、对偶问题与原问题的对应关系,本章小结,二、对偶变换,约束条件的类型(规