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

1、运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外 线性规划对偶理论线性规划对偶理论运筹学君子曰：学不可以已。君子曰：学不可以已。青，取之于蓝而青于蓝；冰，水为之而寒于水。青，取之于蓝而青于蓝；冰，水为之而寒于水。故不登高山，不知天之高也；故不登高山，不知天之高也；不临深溪，不知地之厚也；不临深溪，不知地之厚也； 荀子荀子劝学劝学掌握掌握线性规划对偶理论及其基本经济学意义；教学要求：教学要求：了解了解运用对偶理论对线性规划最优解进行分析的基本方法；会会运用对偶理论对一些基本的管理问题进行经济学分析。第三章线性规划对偶理论第三章线性规划对偶理论p线性规划的对偶问题线性规划的对偶

2、问题p对偶规划的基本性质对偶规划的基本性质p对偶单纯形法对偶单纯形法p影子价格和灵敏度分析影子价格和灵敏度分析重点：对偶转换、对偶单纯形法重点：对偶转换、对偶单纯形法难点：对偶性质、灵敏度分析难点：对偶性质、灵敏度分析第三章线性规划对偶理论第三章线性规划对偶理论某家具厂木器车间生产木门和木窗两种产品，加工木门收入为某家具厂木器车间生产木门和木窗两种产品，加工木门收入为56元元/扇、加工木窗收入为扇、加工木窗收入为30元元/扇，生产扇，生产 一扇木门需要木工一扇木门需要木工4小时，油漆工小时，油漆工2小时；生产一扇木窗需要木工小时；生产一扇木窗需要木工3小时，油漆工小时，油漆工1小小时，该车间可

3、用本工总工时为时，该车间可用本工总工时为120小时，油漆工总工时为小时，油漆工总工时为50小小时问该车间应如何安排生产才能使每日收入最大？时问该车间应如何安排生产才能使每日收入最大？令该车间每日安排生产木门令该车间每日安排生产木门x1,木窗木窗x2扇，则其数学模型为：扇，则其数学模型为：max z=56x1+30 x2s.t 4x1+3x2120 2x1+x2 50 x1,x20即每日安排生产木门即每日安排生产木门15扇，木窗扇，木窗20扇时，收入最大为扇时，收入最大为1440元元一、一、对偶问题的提出最优解为：最优解为：x=(15,20)，最优值为最优值为1440元元第一节线性规划的对偶问题

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

5、生产木门和木窗所得到的收入，否则该车间觉得无利可图就不会替他加工这批订单，因此，图就不会替他加工这批订单，因此，w1,w2 应满足应满足 4w1+2w2 56上式可理解：生产一扇木门的木工工时上式可理解：生产一扇木门的木工工时*木工工时价木工工时价+生产生产一扇木门的油漆工时一扇木门的油漆工时*油漆工工时价油漆工工时价生产一扇木门的收入生产一扇木门的收入 3w1+w2 30上式可理解：生产一扇木窗的木工工时上式可理解：生产一扇木窗的木工工时*木工工时价木工工时价+生产生产一扇木窗的油漆工时一扇木窗的油漆工时*油漆工工时价油漆工工时价生产一扇木窗的收入生产一扇木窗的收入第一节线性规划的对偶问题第

6、一节线性规划的对偶问题该个体经营者的数学模型为min f=120w1+50w24w1+2w2 563w1+w2 30w1,w2 0解得解得w1=2,w2=24,f=1440第一节线性规划的对偶问题第一节线性规划的对偶问题第一节线性规划的对偶问题第一节线性规划的对偶问题一、一、对偶问题的提出原问题原问题某工厂甲生产a、b、c三种产品。这三种产品的单位利润分别是60、30、20。生产这三种单位产品所占用m、n、p三种机器的时间如表所示，机器m、n、p每天可供使用的时间分别是48、20、8小时。这三种产品每天生产多少才能使工厂获得最大效益。产品机器abc资源限制m86148n421.520p210.

7、58利润603020该问题的数学模型为：该问题的数学模型为：0,85 . 02205 . 1244868203060max321321321321321xxxxxxxxxxxxxxxzm机器机器n机器机器p机器机器 现在甲厂拟出租机器给乙厂，即甲厂出租机器现在甲厂拟出租机器给乙厂，即甲厂出租机器m、n和和p给乙厂，请问甲厂应如何给这三种机器定价？给乙厂，请问甲厂应如何给这三种机器定价？考虑：1、定价不能太低太低？2、定价不能太高太高？既要保证甲厂利润又必须使乙厂的租金越少越好咋办？第一节线性规划的对偶问题第一节线性规划的对偶问题产品机器abc资源限制m86148y1n421.520y2p210

8、.58y3利润60 3020设m、n、p机器的单位出售价格分别为 y1 、 y2和y3，针对乙厂，建立其相应的数学模型：目标：目标：min w=48y1+20y2+8y3对于a产品而言，甲厂生产一件产品可获利60元，如果8y1+4y2+2y30 0 ，则有，则有y y0 0p pj j=c=cj j2. 2. 如果如果y y0 0p pj jccj j, ,则有则有x x0 0=0=03. 3. 如果如果y y0 0i i00，则有，则有a ai ix xi i0 0 =b=bi i4.4.如果如果a ai ix xi i0 0 b,0，由松驰性质得到原问题约束条件应取等号即，由松驰性质得到原

9、问题约束条件应取等号即w10 2x3+3x4=20w2 0 3x3+2x4=20， 解方程组，得解方程组，得x3=x4=4故原问题的最优解为故原问题的最优解为(0,0,4,4)第二节对偶规划的基本性质第二节对偶规划的基本性质 w1+2w212w1+w222w1+3w2=33w1+2w2=4x1=0 x2=0例例3.3已知线性规划问题已知线性规划问题max z=2x1+x2+5x3+6x4s.t 2x1 + x3+ x4 8 2x1+2x2+x3+2x412 x1 ,x2 ,x3 , x4 , 0其对偶问题的最优解为其对偶问题的最优解为w=(4,1)t，试根据对偶理论求出原问题的最优解，试根据对

10、偶理论求出原问题的最优解解，该原问题的对偶问题为：解，该原问题的对偶问题为：min y=8w1+12w2s.t 2w1+2w2 2 (1) 2w1+2w22 x1=0 2w2 1 (2) 2w21 x2=0 w1+ w2 5 (3) w1+w2=5 w1+2w2 6 (4) w1+2w2=6 w1,w2 0将对偶问题的最优解代入，得到将对偶问题的最优解代入，得到(1),(2)为严格不等式，故由互补松驰性质得到为严格不等式，故由互补松驰性质得到x1=x2=0又又w1,w20，由松驰性质得到原问题约束条件应取等号即，由松驰性质得到原问题约束条件应取等号即w10 x3+x4=8w20 x3+2x4=

11、12，解方程组，得，解方程组，得x3=x4=4故问题的最优解为（故问题的最优解为（0,0，4,4）第二节对偶规划的基本性质第二节对偶规划的基本性质 第三节对偶单纯形法第三节对偶单纯形法 一、对偶单纯形法原理一、对偶单纯形法原理 对偶单纯形法是利用对偶原理求解原问题的一对偶单纯形法是利用对偶原理求解原问题的一种方法（而不是求解对偶问题的方法）种方法（而不是求解对偶问题的方法） 对偶单纯形法基本思想是：首先从原问题的一对偶单纯形法基本思想是：首先从原问题的一个对偶可行的基本解个对偶可行的基本解(它不是原线性规划问题的可它不是原线性规划问题的可行解行解)出发，求改进的对偶可行的基本解，向原问出发，求

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

13、n如何保证初始基础解满足最优条件b=b1b0考虑对偶线性规划问题 min z=cxs.t ax=b x0其中a=(p1,p2,pn)b=(b1,b2,.bn)bi可以是任意数第三节对偶单纯形法第三节对偶单纯形法 二、对偶单纯形法的计算步骤：二、对偶单纯形法的计算步骤：1、给定一个初始对偶可行的基本解，设相应的基为b；2若 ，则停止计算，现行对偶可行的基本解为最优解。否则令 ，则该行所对应的变量xr 为换出基的变量； 3若对所有j， ，则停止计算，原问题无可行解。否则，令则 为换入基的变量；4以 为主元进行主元消去，返回2。01bbb0miniirbb0ija0|maxrjrjjjjrkrkkk

14、aazcaazc检验数kxrka第三节对偶单纯形法第三节对偶单纯形法 标准化乘以(-1)icbcbxjjzc3100bx1x2x3x40 x3-1-1-1100 x4-2-2-3013100初始对偶单纯形表：初始对偶单纯形表：出基出基进基进基主元主元 直到直到b0，停止，停止第三节对偶单纯形法第三节对偶单纯形法 为了得了初始基本解，为了得了初始基本解，可用大可用大m法和两阶段法法和两阶段法例例3100cbxbbx1x2x3x40 x3-1/3-1/301-1/30 x22/32/310-1/37/3001/3 3100cbxbbx1x2x3x40 x4110-311x2111-102010因为

15、因为b0，且所有检验数，且所有检验数 cj-zj0,运算结束，得到最优解为运算结束，得到最优解为x1=0,x2=1 最优目标值为最优目标值为 fmin=1表二表二表三表三第三节对偶单纯形法第三节对偶单纯形法 例例3.4用对偶单纯形法求解线性规划用对偶单纯形法求解线性规划0,2 33843623min321321321321xxxxxxxxxxxxz解：在第解：在第2 2个约束方程的两边同乘以个约束方程的两边同乘以-1 -1，然后引入变量，然后引入变量x x4 4,x ,x5 5得：得：0,2 338 436 23min5432153214321321xxxxxxxxxxxxxxxxz 第三节对

16、偶单纯形法第三节对偶单纯形法 13200cbxbbx1x2x3x4x50 x4863-4100 x5-2-3-1301cj-zj01320013200cbxbbx1x2x3x4x50 x44012121x12/311/3-10-1/3cj-zj-2/308/3301/3 表一表一表二表二用对偶单纯形法求解得最优解用对偶单纯形法求解得最优解 ：, 4, 3/241xx0532xxx最优目标函数值最优目标函数值 ：fmin=2/3第三节对偶单纯形法第三节对偶单纯形法 例3.5 某工厂有生产a、b两种化工产品 的能力，生产一千克a产品需要2小时，花费成本为2元，而生产一千克b产品则需要1小时，成本为

17、3元，下个月的总生产时间是600小时，公司决定a，b的总产量至少为350千克，此外公司的一个主要客户订购了125千克a产品的要求必须满足，在满足客户要求的前提下，公司应怎样安排生产计划，才能尽量降低成本？解 设a产品的产量为x1千克，b产品的产量为x2千克，则建立相应模型min z=2x1+3x2s.t x1 125 x1+x2 350 2x1+x2600 x1,x2 0第三节对偶单纯形法第三节对偶单纯形法 在第一、二两个约束条件两边同乘以-1，然后引入变量x3,x4,x5，化为如下形式minz=2x1+3x2s.t -x1 +x3 =-125 -x1-x2 +x4 =-135 2x1+x2

18、+x5=600 x1,x2,x3,x4,x50表一23000cbxbbx1x2x3x4x50 x3-125-101000 x4-350-1-10100 x56002100123000 第三节对偶单纯形法第三节对偶单纯形法 表二23000cbxbbx1x2x3x4x50 x3225011-102x1350110-100 x5-1000-102101020表三23000cbxbbx1x2x3x4x50 x3125001112x1250100113x2100010-2-100041此时所有此时所有b且所有检验数大于等于且所有检验数大于等于0，所得得到最优解为，所得得到最优解为x1=250,x2=10

19、0,x3=125 最优值为最优值为800 第三节对偶单纯形法第三节对偶单纯形法 三、单纯形算法和对偶单纯形算法之差别三、单纯形算法和对偶单纯形算法之差别 第三节对偶单纯形法第三节对偶单纯形法 四、原问题检验数与对偶问题的解的总结四、原问题检验数与对偶问题的解的总结在主对偶定理的证明中我们有：对偶在主对偶定理的证明中我们有：对偶(min型型)变量的最变量的最优解等于原问题松弛变量的机会成本，或者说原问题松弛变优解等于原问题松弛变量的机会成本，或者说原问题松弛变量检验数的绝对值量检验数的绝对值不管原问题是否标准，在最优解的单纯型表中，都有原不管原问题是否标准，在最优解的单纯型表中，都有原问题问题虚

20、变量虚变量(松弛或剩余松弛或剩余) 的检验数对应其对偶问题的检验数对应其对偶问题实变量实变量 (对偶变量对偶变量)的最优解，原问题的最优解，原问题实变量实变量(决策变量决策变量) 的检验数对的检验数对应其对偶问题应其对偶问题虚变量虚变量 (松弛或剩余变量松弛或剩余变量)的最优解。的最优解。第三节对偶单纯形法第三节对偶单纯形法 第三节对偶单纯形法第三节对偶单纯形法 max z=4x1+3x2+7x3s.t x1+2x2+2x3 100 3x1+x2+3x3 100 x1.x2.x30解：其对偶问题为：解：其对偶问题为：min w=100y1+100y2s.t. y1+3y2 4 2y1+y2 3

21、 2y1+3y2 7 y1,y2 0例例3.6单纯形法(max, )对偶单纯形法(min, )化为标准形max z=4x1+3x2+7x3s.t x1+2x2+2x3 +x4=100 3x1+x2+3x3 +x5=100 x1.x2.x3.x4.x50min =100y1+100y2s.t. -y1-3y2+y3=-4 -2y1-y2 +y4=-3 -2y1-3y2 +y5=-7 y1,y2 ,y3,y4,y50最优性检验所有检验数是否0 所有b是否0进基出基变量的确定检验数大的max4,3,7,0,0对应的变量进基比值最小的min100/3,100/2 为出基b最小的min-4,-3,-7对

22、应的变量为出基变量比值最大的max-100/2,-100/3为进基表一表一43700cbxbbx1x2x3x4x50 x4100122100 x51003130143700表一表一100 100000cbybby1y2y3y4y50y3-4-1-31000y4-3-2-10100y5-7-2-3001100 100000表一43700cbxbbx1x2x3x4x50 x4100122100 x51003130143700表二43700cbxbbx1x2x3x4x50 x4100/3-14/301-2/37x3100/311/3101/3-32/300-7/3表三43700cbxbbx1x2x3

23、x4x53x225-3/4103/4-1/27x3255/401-1/41/2-5/200-1/2-2原问题求解（单纯形法）：原问题求解（单纯形法）：第三节对偶单纯形法第三节对偶单纯形法 得到最优解为得到最优解为x=(0,25,25),松驰变量的检验数为（松驰变量的检验数为（1/2，2)max z=4x1+3x2+7x3s.t x1+2x2+2x3 100 3x1+x2+3x3 100 x1.x2.x30表一表一100100000cbybby1y2y3y4y50y3-4-1-31000y4-3-2-10100y5-7-2-3001100100000表二表二100100000cbybby1y2y

24、3y4y50y331010-10y4-2/3-4/3001-1/3100y27/32/3100-1/3100/3000100/3表三表三100100000cbybby1y2y3y4y50y35/20013/4-5/4100y11/2100-3/41/4100y220101/2-1/20002525对偶问题求解对偶问题求解(对偶单纯形法对偶单纯形法)：第三节对偶单纯形法第三节对偶单纯形法 得到最优解得到最优解y=(1/2,2)t,松驰变量对应的检验数为松驰变量对应的检验数为(0,25,25)min w=100y1+100y2s.t. y1+3y2 4 2y1+y2 3 2y1+3y2 7 y1,

25、y2 0表三43700cbxbbx1x2x3x4x53x225-3/4103/4-1/27x3255/401-1/41/2-5/200-1/2-2表三表三100100000cbxbbx1x2x3x4x50 x35/20013/4-5/4100 x11/2100-3/41/4100 x220101/2-1/20002525最优解为：最优解为：x=(0,25,25)t，松驰变量的检验数为（，松驰变量的检验数为（1/2，2)原问题原问题(max型型)最优表：最优表：对偶问题对偶问题(min型型)最优表：最优表：最优解为：最优解为：x=(1/2,2)t,剩余变量对应的检验数为剩余变量对应的检验数为(0

26、,25,25)第三节对偶单纯形法第三节对偶单纯形法 结论：结论：若是若是max型型(单纯形法单纯形法)在最优表中，基变量对应的解为原问题在最优表中，基变量对应的解为原问题(max)的最优的最优解，松驰变量的解，松驰变量的检验数的相反数检验数的相反数对应为对偶问题对应为对偶问题(min)的最的最优解优解若是若是min型型 (对偶单纯形法对偶单纯形法)基变量对应的解为本身问题的基变量对应的解为本身问题的(min)的最优解，剩余变的最优解，剩余变量的量的检验数检验数对应为对偶问题对应为对偶问题(max)的最优解的最优解因此，针对线性规划问题，只要解原问题或对偶问题其因此，针对线性规划问题，只要解原问

27、题或对偶问题其中之一就可以中之一就可以第三节对偶单纯形法第三节对偶单纯形法 思考题：思考题：1、如有原问题为、如有原问题为max z=2x1+5x2s.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)第三节对偶单纯形法第三节对偶单纯形法 最优表最优表25000cbxbbx1x2x3x4x50 x320011/3-1/35x260101/200 x12100-1/31/

28、3000-11/6-2/32、某问题为、某问题为min w=4u1+12u2+18u3s.t u1+3u32 2u2+2u35 u1,u2,u30利用对偶单纯形法求得最优，利用对偶单纯形法求得最优，如右表所示，问对偶问题的如右表所示，问对偶问题的最优解为：（）最优解为：（）a, (2,6)b, (-11/6,-2/3)c, (11/6,2/3)d, (2,5)最优表最优表4121800cbubbu1u2u3u4u50u32/31/301-1/3012u211/6 -1/310-1-1/220026第三节对偶单纯形法第三节对偶单纯形法 第四节影子价格第四节影子价格二、影子价格和对偶价格二、影子价

29、格和对偶价格 约束条件右侧（即资源）每增加1个单位，由由此引起最优目标函数值的增加量，就等于与该约束条件相对应的对偶变量的最优解值。对偶解的经济含义对偶解的经济含义：资源的单位改变量引起目标函数值的增加量，经济学上称为影子价格影子价格。它度量了约束条件对应的那种资源的价值。第四节影子价格第四节影子价格在对偶问题的互补松弛性质中有 如果某种资源 bi未得到充分利用时，该种资源的影子价格为零；如果某种资源bi已完全耗尽，则该种资源的影子价格不为零资源的影子价格越高，表明该种资源的贡献越大 0y 0时，11injinjijijijijbxa;ybxa时，当当第四节影子价格第四节影子价格3020101

30、008060402020406080 x1100b第四节影子价格第四节影子价格20101008060402020406080 x1100b第四节影子价格第四节影子价格3020101008060402020406080 x1100b第四节影子价格第四节影子价格2010 1008060402020406080 x1100b第四节影子价格第四节影子价格第四节影子价格第四节影子价格在最优表中，松驰变量的检验数与对偶决策变量是一一对应的在最优表中，松驰变量的检验数与对偶决策变量是一一对应的max()松驰变量的松驰变量的检验数的相反数检验数的相反数为对偶问题的最优解为对偶问题的最优解min() 检验变量的

31、检验变量的检验数检验数就为对偶问题的最优解就为对偶问题的最优解因此，可知因此，可知max()松驰变量的松驰变量的检验数的相反数检验数的相反数就为相应资源的影子价格就为相应资源的影子价格min() 检验变量的检验变量的检验数检验数相应资源的影子价格相应资源的影子价格由上述关系可知，影子价格其实就是对偶问题的最优解由上述关系可知，影子价格其实就是对偶问题的最优解决策变量、影子价格之间的对应关系决策变量、影子价格之间的对应关系 例例3.83.8：求下列原问题的最优解及影子价格和对偶问题的最优解：求下列原问题的最优解及影子价格和对偶问题的最优解及影子价格。及影子价格。 min z=4x1+7x2 +8

32、x3 s.t. x1+ x2 3 x2 +2x3 1 （lp） x1+ x2 + x3 8 x10,x20,x30其对偶问题为：其对偶问题为： 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； 第四

33、节影子价格第四节影子价格四、影子价格的经济含义1、是否将设备用于外加工或出租若租金高于某设备的影子价格，则可以出租，否则不宜出租。2、是否将投资用于购买设备，以扩大生产能力若市场价低于某设备的影子价格，可考虑买进设备，若高于，则不宜买进p市场价格是由市场决定的，一般较稳定的，而影子价格是有赖于资源的利用情况，是未知数。第四节影子价格第四节影子价格解：解：x1：产品甲的计划生产量；：产品甲的计划生产量；x2：产品乙的计划生产量，则有如下线：产品乙的计划生产量，则有如下线性规划问题：性规划问题： max z=7x1 + 12x2 (总销售收入总销售收入) s.t. 9x1 + 4x2 360 (煤

34、资源限制煤资源限制) 4x1 + 5x2 200 (电资源限制电资源限制) 3x1 + 10 x2 300 (油资源限制油资源限制) x1 0，x2 0 (非负条件非负条件)第四节影子价格第四节影子价格例例3.93.9：a a工厂计划生产甲、乙两种产品。每千克产品的销售工厂计划生产甲、乙两种产品。每千克产品的销售价格和能源消耗量、以及能源资源见表价格和能源消耗量、以及能源资源见表3-263-26，怎样安排生产计，怎样安排生产计划才能使划才能使a a工厂获益最大？工厂获益最大？ 712000cbxbbx1x2x3x4x50 x3360941000 x4200450100 x5300310001c

35、j-zj0712000表一表一表表二二xbbx1x2x3x4x50 x32407.8010-0.40 x4502.5001-0.512x2300.31000.1cj-zj-3603.4000-1.2 xbbx1x2x3x4x50 x3224.4001-3.121.160 x1201000.4-0.212x224010-0.120.04cj-zj-428000-1.36-0.52第四节影子价格第四节影子价格表表三三原问题的最优解为原问题的最优解为x(20,24)t,对应的对偶价格，也就是影子价格为对应的对偶价格，也就是影子价格为(0,1.36,0.52)所以，煤、电、石油的影子价格分别为：所以，

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

37、、电、石油分别是5、10、3单位，则新产品的价格必须大于5*0+10*1.3+3*0.52=15.16 如果售价低于15.16，生产该产品就是不划算的。 根据影子价格还可以分析生产工艺的改变对资源节约所带来的收益。 例如，如果a工厂经过工艺改造后使石油节约了2%，则带来的经济收益为 3002%0.52=3.12第四节影子价格第四节影子价格相当于生产成本相当于生产成本 五、利用excel求影子价格在报告列表框中选择“敏感性报告”microsoft excel 9.0 敏感性报告microsoft excel 9.0 敏感性报告工作表 solve.xlssheet2工作表 solve.xlsshe

38、et2报告的建立: 2004-10-7 13:40:18报告的建立: 2004-10-7 13:40:18可变单元格终终递减递减目标式目标式允许的允许的允许的允许的单元格单元格名字名字值值成本成本系数系数增量增量减量减量$b$2x120072.63.4$c$2x22401211.333333333.25约束终终阴影阴影约束约束允许的允许的允许的允许的单元格单元格名字名字值值价格价格限制值限制值增量增量减量减量$b$8lhs27603601e+3084$b$9lhs2001.3620026.9230769250$b$10lhs3000.5230010072.4137931第四节影子价格第四节影子

39、价格max z = 7x1 + 12x2 s.t. 9x1 + 4x2 360 4x1 + 5x2 200 3x1 + 10 x2 300 x1 0，x2 0min g = 360y1 + 200y2 + 300y3 s.t. 9y1 + 4y2 + 3y3 7 4y1 + 5y2 + 10y3 12 y1 0，y2 0，y3 0第四节影子价格第四节影子价格在线性规划中，我们假定模型的系数都是已知常数。而在实际中，这些系数往往是通过估计、预测或人为决策得到的，不可能很准确，更不可一成不变，灵敏度分析就是研究当线性规划问题中的系数发生变化时，对函数最优解的影响程度灵敏度分析主要研究以下两个问题：

40、（1）这些系数中的一个或多个发生变化时对已求得的线性规划问题最优解的影响。（2）若原最优基不再是最优时，如何用最简便的方法找到新最优解和最优值一、灵敏度分析概念一、灵敏度分析概念第五节灵敏度分析第五节灵敏度分析)24.3(,2, 1,0)23.3(.max1nixbaxtscxxcziniii设最优解为设最优解为xb=b-1b，xn=0，其中，其中b是最优可行基是最优可行基考虑模型：考虑模型：第五节灵敏度分析第五节灵敏度分析单纯形法max型 最大检验数 最小比 检验数小于等于0对偶单纯形法max型 最小b 最小比 所有b大于等于0ccncbcbxbbxnxbcbxbb-1bb-1ni检验数向量

41、cb b-1bcn-cbb-1n0第五节灵敏度分析第五节灵敏度分析最优表：最优表：（1）如果）如果非基变量非基变量xk 的系数的系数ck变为变为ck时，此时时，此时zj=cbb-1pj不变不变,这种情况只引起一个检验数的变化。这种情况只引起一个检验数的变化。如果检验数（如果检验数（ck zk）0则原来问题的最优解也是新问题的最优解则原来问题的最优解也是新问题的最优解 如果检验数（如果检验数（ck -zk ）0则改变后则改变后xk为进基变量，把原来最优单纯形表中的为进基变量，把原来最优单纯形表中的ck-zk换成换成ck-zk，然后用单纯形表求新问题的最优解，然后用单纯形表求新问题的最优解1、目标

42、函数系数（、目标函数系数（c）的变化）的变化第五节灵敏度分析第五节灵敏度分析例例3.10已知线性规划问题已知线性规划问题max z=-5x1+5x2+13x3s.t -x1+ x2+ 3x3 20 12x1+4x2+10 x390 x1 ,x2 ,x3 0先用单纯形法求出最优解，然后分析在下列各种条件下，最优先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化解分别有什么变化.（1）目标函数）目标函数x3的系数由的系数由13变为变为8解，将原问题引入松驰变量化为标准，通过两步迭代得到最优解，将原问题引入松驰变量化为标准，通过两步迭代得到最优单纯形表：单纯形表：表三-55130

43、0cbxbbx1x2x3x4x55x220-113100 x510160-2-4100-2-50第五节灵敏度分析第五节灵敏度分析x3为非基变量，其变化后的检验数为3 ck zk85*3+0*(-2)=-70，则用3代替原最优解x3的检验数，并以x3为进基变量，继续迭代表三-55800cbxbbx1x2x3x4x55x220-113100 x510160-2-4100-2-503第五节灵敏度分析第五节灵敏度分析例例3.11， 考虑例考虑例2.1，即其线性规划为：，即其线性规划为：0,0 135 708 600 630 .910 max21241110123212651212110721xxxxx

44、xxxxxtsxx问中档球袋的利润即问中档球袋的利润即x1的系数在什么范围内变化时，公司的的系数在什么范围内变化时，公司的最优生产计划不变？最优生产计划不变？第五节灵敏度分析第五节灵敏度分析目标函数系数在什么范围变化时，目标函数的最优解不会目标函数系数在什么范围变化时，目标函数的最优解不会发生变化，称这样的范围为可行最优范围。发生变化，称这样的范围为可行最优范围。解：原问题引入松驰变量化为标准形经过迭代得最优单纯形表为：解：原问题引入松驰变量化为标准形经过迭代得最优单纯形表为：1090000cbxbbx1x2x3x4x5x69x2252011.8740-1.31200 x412000-0.93

45、710.156010 x154010-1.24901.87500 x61800-0.34400.141cj-zj766800-4.3750-6.9380设中档球袋的利润变化设中档球袋的利润变化c时，令时，令1090000cbxbbx1x2x3x4x5x69x2252011.8740-1.31200 x412000-0.93710.156010 x154010-1.24901.87500 x61800-0.34400.141cj-zj7668540 c 001.249 c -4.3750-1.875 c -6.9380c第五节灵敏度分析第五节灵敏度分析 要使原问题最优生产计划不变，也就是最优解不

46、变，要使原问题最优生产计划不变，也就是最优解不变，则必须所有检验数则必须所有检验数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) x19x27668540 c可行最优范围可行最优范围第五节灵敏度分析第五节灵敏度分析x240403020 x1 最优解变化max z = 40 x + 50y利润s.t.1x + 2y 40时间约束4x

47、+ 3y 120人力约束x, y 0非负约束利用图解法求最优可行范围，考虑如下模型：利用图解法求最优可行范围，考虑如下模型：第五节灵敏度分析第五节灵敏度分析x240403020 x1 最优解变化第五节灵敏度分析第五节灵敏度分析 即当目标函数的斜率满足- 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/215 c80/3 当c1在上述范围内变化时，最优解不变第五节灵敏度分析第五节灵敏度分析如果检验数（如果检验数（ck z

48、k）0则原来问题的最优解也是新问题的最优解则原来问题的最优解也是新问题的最优解,但最优值发生变化但最优值发生变化如果检验数（如果检验数（ck -zk ）0则以最终单纯形表为基础，换上变化后的价值系数和检验数，则以最终单纯形表为基础，换上变化后的价值系数和检验数，继续迭代可以求出新的最优解。继续迭代可以求出新的最优解。第五节灵敏度分析第五节灵敏度分析（2）如果基变量的系数）如果基变量的系数ck变为变为ck时，此时，影响时，此时，影响检验数和目标函数值。检验数和目标函数值。例例3.12已知线性规划问题已知线性规划问题max z=2x1-x2+x3s.t x1+x2+x3 6 -x1+2x2 4 x

49、1 ,x2 ,x3 0先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化变化.（1）目标函数变为）目标函数变为max z=4x1-x2+x3解，将原问题引入松驰变量化为标准，通过两步迭代得到最优单纯形表：解，将原问题引入松驰变量化为标准，通过两步迭代得到最优单纯形表：表三2-1100cbxbbx1x2x3x4x52x16111100 x510031110-3-1-20故原问题的最优解为故原问题的最优解为x=(6,0,0,0,10)t，最优值为最优值为max z=12相当于相当于x1的系数变化了的系数变化了c2

50、方法一：直接将方法一：直接将c加到加到x1的检的检验数上得到新的检验数，并继验数上得到新的检验数，并继续迭代续迭代方法二：求变化后的方法二：求变化后的x1检验数检验数2 然后继续迭代然后继续迭代第五节灵敏度分析第五节灵敏度分析表四4-1100cbxbbx1x2x3x4x54x16111100 x510031112-3-1-20表五4-1100cbxbbx1x2x3x4x54x16111100 x510031110-5-3-4-2表三2-1100cbxbbx1x2x3x4x52x16111100 x510031110-3-1-20故原问题的最优解为故原问题的最优解为x=(6,0,0,0,10)t

51、，最优值为最优值为max z=24例例3.13已知线性规划问题已知线性规划问题max z=2x1-x2+x3s.t x1+x2+x3 6 -x1+2x2 4 x1 ,x2 ,x3 0先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化变化.（1）目标函数变为）目标函数变为max z=2x1+3x2+x3解，将原问题引入松驰变量化为标准，通过两步迭代得到最优单纯形表：解，将原问题引入松驰变量化为标准，通过两步迭代得到最优单纯形表：表三2-1100cbxbbx1x2x3x4x52x16111100 x5100311

52、10-3-1-20故原问题的最优解为故原问题的最优解为x=(6,0,0,0,10)t，最优值为最优值为max z=12求变化后的求变化后的x2检验数检验数2然后继续迭代然后继续迭代第五节灵敏度分析第五节灵敏度分析表四23100cbxbbx1x2x3x4x52x16111100 x5100311101-1-20表五23100cbxbbx1x2x3x4x52x18/3102/32/3-1/33x210/3011/31/31/300-4/3 -7/3-1/3即目标函数改变后，最优解变为：即目标函数改变后，最优解变为：x=(8/3,10/3,0,0,0)t,最优值为最优值为max z=46/3第五节灵

53、敏度分析第五节灵敏度分析表三2-1100cbxbbx1x2x3x4x52x16111100 x510031110-3-1-203-2*1-0*32、约束条件右边值的变化、约束条件右边值的变化设设bb+b ,由最优表可知，改变的只是表中第三列，右端列由最优表可知，改变的只是表中第三列，右端列基变量的取值由基变量的取值由xb=b-1b b-1(b+ b)目标函数值由目标函数值由-z=-cbb-1b -cbb-1(b+ b)（1）如果如果xb=b-1(b+ b) 0则原来的最优基不变，但基变量的取值和目标函数将发生则原来的最优基不变，但基变量的取值和目标函数将发生变化此时变化此时xb为新问题的最优解

54、，为新问题的最优解，z为新问题的最优值为新问题的最优值第五节灵敏度分析第五节灵敏度分析例例3.12， 考虑例考虑例2.1，即其线性规划为：，即其线性规划为：0,0 135 708 600 630 .910 max21241110123212651212110721xxxxxxxxxxtsxx 当剪裁部门的时间再增加当剪裁部门的时间再增加20小时，同时定型部门小时，同时定型部门增加增加100小时，考虑对公司利润的有如何影响？小时，考虑对公司利润的有如何影响？第五节灵敏度分析第五节灵敏度分析解：用单纯形法求解新问题得初始表与最终单纯形表为：解：用单纯形法求解新问题得初始表与最终单纯形表为：最优表1

55、090000cbxbbx1x2x3x4x5x69x2252011.8740-1.31200 x412000-0.93710.156010 x154010-1.24901.87500 x61800-0.34400.141cj-zj766800-4.3750-6.9380初始表1090000cbxbbx1x2x3x4x5x60 x36307/10910000 x46001/25/601000 x570812/300100 x61351/101/40001cj-zj01090000b-1第五节灵敏度分析第五节灵敏度分析x=b-1b1.875 0 -1.312 0-0.937 1 0.156 0-1.

56、2 0 1.875 0-0.344 0 0.14 1b-1=约束条件的右端值约束条件的右端值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 1650600808135=158.25116.875702.525.1870第五节灵敏度分析第五节灵敏度分析630600708135b=650600808135b=原最优表1090000cbxbbx1x2x3x4x5x69x2011.8740-1.31200 x400-0.93710.156010 x110-1.24901.87500 x600-0.34400.141cj-

57、zj766800-4.3750-6.9380所以最优基不变，仍为所以最优基不变，仍为(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.3158.25116.875702.525.18725212054018第五节灵敏度分析第五节灵敏度分析p（2）如果）如果b-1b 0p则原来的最优基不再是新问题的可行基，但所

58、有则原来的最优基不再是新问题的可行基，但所有检验数检验数0，所以现行基本解是对偶可行的基本解，所以现行基本解是对偶可行的基本解，p此时，将最优表中的右端列修改为：此时，将最优表中的右端列修改为：b-1b，然，然后用对偶单纯形法求解新问题后用对偶单纯形法求解新问题第五节灵敏度分析第五节灵敏度分析例例3.13已知线性规划问题已知线性规划问题max z=-5x1+5x2+13x3s.t -x1+x2+3x3 20 12x1+4x2+10 x390 x1 ,x2 ,x3 0分析在下列各种条件下，最优解分别有什么变化分析在下列各种条件下，最优解分别有什么变化.（1）约束条件）约束条件的右端值由的右端值由

59、20变为变为30（2）约束条件）约束条件对应的对应的b1的在什么范围内变化时，最优基不变的在什么范围内变化时，最优基不变解，（解，（1）引入松驰变量）引入松驰变量,利用单纯形法得到最优单纯形表：利用单纯形法得到最优单纯形表：表三表三551300cbxbbx1x2x3x4x55x220-113100 x510160-2-4100-2-50最优解为最优解为x=(0,20,0,0,10)t,最优值为最优值为max z=100第五节灵敏度分析第五节灵敏度分析表三551300cbxbbx1x2x3x4x55x220-113100 x510160-2-4100-2-50由上表可知由上表可知b1=1 0-4

60、 1b-1b=1 0-4 130 9030 -30=表四551300cbxbbx1x2x3x4x55x230-113100 x5-30160-2-4100-2-50利用对偶单纯形利用对偶单纯形法（法（max)型求型求解解minbi出基出基最小比进基最小比进基存在值小于存在值小于0，即用对偶单纯形法继即用对偶单纯形法继续求解续求解第五节灵敏度分析第五节灵敏度分析表五-551300cbxbbx1x2x3x4x55x2-152310-53/213x315-8012-1/2-1600-1-1表六-551300cbxbbx1x2x3x4x50 x43-23/5-1/501-3/1013x396/52/5