第2章 线性规划的对偶理论与灵敏度分析2011,9(上课)

1、1、线性规划的对偶问题、线性规划的对偶问题2、图解法的灵敏度分析、图解法的灵敏度分析对偶是一种普遍现象对偶是一种普遍现象两个黄鹂鸣翠柳两个黄鹂鸣翠柳, , 一行白露上青天。一行白露上青天。门泊东吴万里船。门泊东吴万里船。窗含西岭千秋雪窗含西岭千秋雪, , 第一节 线性规划的对偶问题 一、问题的提出一、问题的提出我们先来看一个例题我们先来看一个例题: 例例1 某工厂在计划期内安排甲、乙两种产品，已某工厂在计划期内安排甲、乙两种产品，已知生产单位产品所需设备知生产单位产品所需设备A、B、C台时和所获利润如台时和所获利润如下表所示：下表所示： 甲乙资源限量设备A11300台时设备B 21400台时设

2、备C01250台时利润（元） 50100 问：工厂应分别生产甲、乙产品各多少，才能使工厂问：工厂应分别生产甲、乙产品各多少，才能使工厂获获利最多？利最多？设：甲设：甲 x1， 乙乙 x2该线性规划的模型为：该线性规划的模型为： 现在我们从另一个角度来考虑这个问题现在我们从另一个角度来考虑这个问题。 假如有另外一个工厂要求租用该厂的设备假如有另外一个工厂要求租用该厂的设备A、B、C，那么，那么该厂的厂长应该如何来确定合理的租金呢？该厂的厂长应该如何来确定合理的租金呢？(LP1)0 x0,x250 x400 x2x300 x x100 x50 xmax Z212212121设：设：y1 - A 每

3、台时的租金每台时的租金_ y2 - B 每台时的租金每台时的租金 y3 - C 每台时的租金每台时的租金则则 建立该线性规划的数学模型为：建立该线性规划的数学模型为：Min z = 300y1+400y2+250y3 y1+2y2 50 y1+y2+y3 100 (LP2) y1,y2,y3 0LP1 与与LP2 是一对是一对对偶问题对偶问题cj50 100 0 0 0 x1 x2 x3 x4 x511 0 -1 0 0 -2 1 1cBixBi50 x10 x4bi50biaikyj=cj-zj100 x2050250 0 1 0 0 1 0 0 -50 0 -50 - 27500cj-30

4、0 -400 -250 0 0 -M cBixBi-300 y1-250 y3bi50biaikyj=cj-zj50y1 y2 y3 y4 y5 y6 1 2 0 -1 0 10 -1 1 1 -1 -1 0 - 50 0 -50 -250 -m+50 27500LP1最终单纯型表最终单纯型表LP2最终单纯型表最终单纯型表求解问题求解问题 LP1得：得：X* = （x1,x2,x3,x4,x5)T = (50,250,0,50,0)T Max z = 27500求解问题求解问题 LP2得：得：Y* = （y1,y2,y3,y4,y5, y6,)T = (50,0,50,0,0,0)TMin z

5、 = 275000,. .max21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZ对称形式下线性规划原问题的一般形式为：对称形式下线性规划原问题的一般形式为： 用用yi（i=1，2，.，m）代表第）代表第i种资源的种资源的估价，则其对偶问题的一般形式为：估价，则其对偶问题的一般形式为：0,. .2122112211112121112211mnmmnnn2mm222mmmmyyycyyycyyycyyyybybybminZaaaaaaaaats用矩阵形式表示，对称形式的线性规划用矩阵形式表示，对称形式的

6、线性规划问题的原问题为：问题的原问题为： YCYYmin wZ0A. .X0XbAX. .CXmaxtsts其对偶问题为：0 x0,x182x3x 122x4 x5x3xmax Z221212121例0y0,y0,y52y2y33yy 18y12y4ymin w3213231321其对偶问题：原问题和对偶问题的关系可用下面表格的形式来表示：原问题和对偶问题的关系可用下面表格的形式来表示：原问题（求极大）c1 c2 cn x1 x2 xn右边对偶问题（求极小）b1 y1b2 y2bm ym a11 a12 a1n a21 a22 . . a2n. am1 am2 . amnb1b2bm右边 c1

7、 c2cm 例3、写出下述线性规划问题的对偶问题无约束333333333333300Zxxxbxaxaxabxaxaxabxaxaxaxcxcxc,max21221122222121112121112211 0, 0, 0, 0yyyyxcZmax0 x, 0 x, 0 x,xxx,xx33213333333322311322323332222121223233322221211131333121211133332211 33233322xxxxbxaxaxaxabxaxaxaxabxaxaxaxabxaxaxaxaxcxcxc对偶变量则上式可写为：其中令 0y, 0y, 0y, 0ycyyy

8、ycyyyycyyyycyyyyybybybybmin w3221333322322311333332322321132332222222121133121221211133222211aaaaaaaaaaaaaaaa其对偶问题为： 0y,y0ycyyycyyycyyyy-y,y-yy333333133321132233222无约束由此得令2122122221211111332211,min:,aaaaaaaaaybybybw原问题（对偶问题）原问题（对偶问题）对偶问题（原问题）对偶问题（原问题）无约束），（量变jjjxxxnj00. .1xjjiijjiijjiijcyacyacyaj），个

9、（件条束约n. .1nijijijijijijbxabxabxai），个（件条束约m. .1m变量无约束iiyyy00m)1,.,(iyiijjxczmaxiiybzmin例例4 4、写对偶规划、写对偶规划minZ= 4x1 +2x2 -3x3 -x1+2x2 62x1 +3x3 9 x1 +5x2 -2x3 = = 4x2 , x3 0maxW= 6y1 +9y2 +4y3 -y1+2y2 + y3 = = 42y1 +5y3 2 3y2 -2y3 -3y1 0 , y2 0 , y3自由自由minZ= 4x1 +2x2 -3x3 x1 -2x2 - 62x1 +3x3 9 x1 +5x2

10、-2x3 = = 4x2 , x3 0或将原问题变形为或将原问题变形为maxW= -6y1 +9y2 +4y3 y1+2y2 + y3 = = 4-2y1 +5y3 2 3y2 -2y3 -3y1 , y2 0 , y3自由自由对偶规划对偶规划例例5 写出下面线性规划的对偶规划写出下面线性规划的对偶规划 min z = 3x1+9x2 + 4x3 x1+ 2x2 +3x3 = 180 2x1- 3x2 + x3 60 5x1 + 3x2 240 x1 0, x2 0)n,.,2 , 1j (0 x)m,.,2 , 1i (bxa)P(xczmax jn1jijijn1jjj原问题：)m,.,2

11、 , 1i (0y)n,.,2 , 1j (cya)D(ybmin wim1ijiijm1iji其对偶问题为：1、弱对偶性、弱对偶性n1jm1iiijjijybxcDPy,x）的可行解，则有：），（分别为（如果n1jm1iiijjm1im1im1iijn1jijijn1jijiin1jn1jm1iijn1jijjim1iijjjybxcyxay)xaybyxax)yaxc所以（因为证l原问题任一可行解的目标函数值是其对偶问题原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任一可行目标函数值的下界；反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。解的目标函

12、数值是其原问题目标函数值的上界。l如原问题有可行解且其目标函数值无界（具有如原问题有可行解且其目标函数值无界（具有无界解），则其对偶问题无可行解；反之，对无界解），则其对偶问题无可行解；反之，对偶问题有可行解且其目标函数值无界，则其原偶问题有可行解且其目标函数值无界，则其原问题无可行解（注意，本点性质的逆不成立）。问题无可行解（注意，本点性质的逆不成立）。l若原问题有可行解而其对偶问题无可行解，则若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之，对偶问题有可原问题目标函数值无界；反之，对偶问题有可行解而其原问题无可行解，则对偶问题的目行解而其原问题无可行解，则对偶问题的目标函

13、数值无界。标函数值无界。212minxxz0, 02221212121xxxxxx无可行解 St例：例：2122maxyyw002211212121yyyyyy解有可行解，则必有无界而对偶问题：2、最优性、最优性的最优解则它们是）的可行解，且有：），（分别为（如果(D)(P),ybxcDPyxn1jm1iiijjij ,3、强对偶性、强对偶性 若原问题及其对偶问题均具有可行解，则若原问题及其对偶问题均具有可行解，则两者均有最优解，且它们最优解的目标函数两者均有最优解，且它们最优解的目标函数值相等。值相等。4 互补松弛性互补松弛性 在线性规划的最优解中，如果对应某一在线性规划的最优解中，如果对应

14、某一约束条件的对偶变量值为非零，则该约束约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严条件取严格等式；反之如果约束条件取严格不等式，则对应的对偶变量一定为零。格不等式，则对应的对偶变量一定为零。0y 0b-x a0b-x a0y 0y b-x am.1i2.220b-x a0y 2.220y b-x a2.212.21y bx c2.21y by x ax ciijn1jijijn1jijiiijn1jijijn1jijim1iiijn1jijn1jm1iiijjn1jm1iiim1iijn1jijjj 时，必有当时，必有由此当有，）式成立必须对所有，故（，因）（）式

15、右端等式得应全为等式。由（）式中，故（又根据最优性）（由弱对偶性知证证明同上，则如果有时，则如果有对偶问题同样有：0 x cy acy a0 x jjim1iijjim1iijj求对偶问题的最优解。），（的最优解为例、已知线性规划,Tj321321321026X*1,2,3j0,x16x2x2x10 x2x xx4x3xmax Z26w11Y1y1y42y2y32yy0 x0 x0y0y1yy42y2y32yy1610212212），最优值，（，解得：变量等于零，即、二个约束的松弛，所以对偶问题的第一，因为解、对偶问题是*,min211212121121yyw例：例： min = 2x1+3x

16、2+5x3+2x4+3x5 其对偶解其对偶解 y1 =4/5 y2 =3/5 Z =5 用对偶理论求用对偶理论求(P)的最优解的最优解x1+x2+2x3+x4+3x5 42x1 -x2+3x3+x4+x5 3 xi 0 ( i =1 5 )(P)解：解：(D)为为maxZ =4y1+3y2y1+2y2 2 y1 - y2 3 2y1+3y2 5 y1+y2 2 3y1+y2 3 y1 , y2 0将将y1 ，y2 代入，知代入，知, , 为严格不等式为严格不等式 x2 = x3 = x4 = 0 x = (1, 0, 0, 0, 1)T Z=5由由y1 ，y20知原约束为等式知原约束为等式 x

17、1+3x5 =42x1+x5 =3l 综合以上对偶定理，互为对偶的两个线性综合以上对偶定理，互为对偶的两个线性规划问题的解之间的关系，只可能有三种情况：规划问题的解之间的关系，只可能有三种情况：（1)两个问题都存在最优解，且目标函数最优值两个问题都存在最优解，且目标函数最优值相等；相等；（2）两个问题都不存在可行解；）两个问题都不存在可行解；（3）一个问题无界，而另一个问题不存在可行）一个问题无界，而另一个问题不存在可行解。解。*m1iiin1jjj*wybxcz*Z*=yb=(y1 ym )b1bm= b1 y1 + b2 y2 + + bm ymZ=bi yi对对求求bi的偏导：的偏导：

18、z* bi=yi*yi* 影子价格（影子价格（shadow price）。）。 yi*的意义代表在资源最优利用条件的意义代表在资源最优利用条件下对单位第下对单位第i种资源的估价种资源的估价;bi 的单位改变的单位改变量所引起的目标函数值的改变量。量所引起的目标函数值的改变量。yi ：反映：反映bi 的边际效益的边际效益( (边际成本边际成本) )例例1中中y1 =50, 当机器台时数增加当机器台时数增加1个单位时，个单位时，工厂可增加利润工厂可增加利润50个单位。个单位。求解问题求解问题 LP1得：得：X* = （x1,x2,x3,x4,x5)T = (50,250,0,50,0)T Max

19、z = 27500求解问题求解问题 LP2得：得：Y* = （y1,y2,y3,y4,y5, y6,)T = (50,0,50,0,0,0)TMin z = 27500l根据对偶问题的互补松驰性质中有根据对偶问题的互补松驰性质中有 生产过程中如果某种资源生产过程中如果某种资源bi未得到充分利用未得到充分利用时，该种资源的影子价格为零；又当资源时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种在生产中的影子价格不为零时，表明该种在生产中已消耗完毕。已消耗完毕。，时，有当时，in1jjijiiin1jjijbxa0y0ybxa;例例.某企业生产甲、乙两种产品，消耗的资源某企业生产甲、

20、乙两种产品，消耗的资源等情况见下表所示，问应如何组织生产，使利等情况见下表所示，问应如何组织生产，使利润最大？润最大？甲 乙每天可用量资源单位成本AB2 31 225单位15小时5元/单位10元/小时产品售价（元）23 40第一种模型第一种模型:),(*,*,max21212111116Y40z152555X015250203210 x54023ZTj434343对偶变量：，），（最优解：xxxxxxxxxxxx),(*,*,max21212111Y40z55X015225323ZTj对偶变量：，），（最优解：xxxxxxx第二种模型第二种模型:l一般说对线性规划的求解是确定资源的一般说对线性

21、规划的求解是确定资源的最优分配方案，而对于对偶问题的求解最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价则是确定对资源的恰当估价，这种估价直接涉及资源的最有效利用。直接涉及资源的最有效利用。第二节 图解法的灵敏度分析 灵敏度分析（灵敏度分析（Sensitivity Analysis) 是指对系统或是指对系统或事物因周围条件变化显示出来的敏感程度。即，在建立数事物因周围条件变化显示出来的敏感程度。即，在建立数学模型和求得最优解之后学模型和求得最优解之后,研究线性规划的系数研究线性规划的系数ci,aij,bj等变等变化时化时,对最优解产生什么影响对最优解产生什么影响?一一 目标

22、函数中的系数目标函数中的系数cj,的灵敏度分析的灵敏度分析 l 我们以下面的例题来看一下我们以下面的例题来看一下cj的变化的变化是如何来影响最优解的是如何来影响最优解的:l l 例例1、 某工厂在计划期内安排甲、乙某工厂在计划期内安排甲、乙两种产品，已知生产单位产品所需设备两种产品，已知生产单位产品所需设备和和A 、B原材料消耗和所获利润如下表所原材料消耗和所获利润如下表所示示 甲乙资源限量设备11300台时原料A 21400千克原料B01250千克利润（元） 50100 问：工厂应分别生产甲、乙产品各多少，才能使工厂问：工厂应分别生产甲、乙产品各多少，才能使工厂获利最多？获利最多？设：甲设：

23、甲 x1， 乙乙 x2该线性规划的模型为：该线性规划的模型为： max z = 50 x1+100 x2 x1+x2 300 2x1+x2 400 (LP1) x2 250 x1 0, x2 0求解问题求解问题 LP1得：得：X* = （x1,x2,x3,x4,x5)T = (50,250,0,50,0)T Max z = 27500用图解的方法定出利润变化的范围用图解的方法定出利润变化的范围z直线直线E 的方程为的方程为:E: x1+x2 = 300 x2 = -x1+ 300F: x2= 0 x1+250G: x2 = -2x1+ 400目标函数目标函数: z = c1x1+ c2x2 也

24、可表示为也可表示为: x2 = x1+c2-c1c2z100200300100200300 x1x2直线直线G（原料（原料A的约束）的约束）直线直线E （设备约束）（设备约束）50 x1+100 x2=27500直线直线F点仍然是最优解。之间变化时，元到的利润在不变时，单位产品即当解得：不变，则有假设当B1000100c100c00100c1100c0cc1211221点仍然是最优解。元时，利润只要大于等于的不变时，而单位产品即当解得：不变，则有假设的变化范围：计算B5050cc500c50150cc12212l假定前例中的假定前例中的A设备台时数增加了设备台时数增加了10个个台时台时,共有共

25、有310个台时，此时约束条件就个台时，此时约束条件就变为变为 310 xx21100200300100200300 x1x2*50 x1+100 x2=27500BC*B/ (60,250)为最优解为最优解MAX Z=28000元元其影子价格为其影子价格为: 500/10=50 如果原材料如果原材料A增加增加10千克千克,将会对最优解和最优值产将会对最优解和最优值产生影响什么生影响什么?100200300100200300 x1x250 x1+100 x2=27500最优解仍最优解仍然为然为B点点 当约束条件的右边常数增加一个单位时当约束条件的右边常数增加一个单位时: 1 如果影子价格大于零如

26、果影子价格大于零,则其最优目标函数值得则其最优目标函数值得到改进到改进,即求最大值时即求最大值时,变得更大变得更大;求最小值时求最小值时,变得更小变得更小. 2如果如果影子影子价格小于零价格小于零,则其最优目标函数值变坏则其最优目标函数值变坏,即求最大值时即求最大值时,变得小了变得小了;求最小值时求最小值时,变得大了变得大了. 3如果如果影子影子价格等于零价格等于零,则其最优目标函数值不便则其最优目标函数值不便. 例例8：某部门现有资金：某部门现有资金200万元，今后五年内考虑给以下的万元，今后五年内考虑给以下的l项目投资，已知项目项目投资，已知项目A：从第一年到第五年每年年初都可投资，：从第

27、一年到第五年每年年初都可投资，l当年末能收回本利当年末能收回本利110%。l 项目项目B：从第一年到第四年每年年初都可以投资，次年末：从第一年到第四年每年年初都可以投资，次年末l回收本利回收本利125%，但规定每年最大投资额不能超过，但规定每年最大投资额不能超过30万元。万元。l 项目项目C：第三年初需要投资，到第五年末能回收本利：第三年初需要投资，到第五年末能回收本利140%，l但规定最大投资额不能超过但规定最大投资额不能超过80万元。万元。l 项目项目D：第二年初需要投资，到第五年末能回收本利：第二年初需要投资，到第五年末能回收本利155%，l但规定最大投资额不能超过但规定最大投资额不能超

28、过100万元。万元。l 据测定每万元每次投资的风险指数如下所示：据测定每万元每次投资的风险指数如下所示：项目项目风险指数（每万元每次）风险指数（每万元每次）A1B3C4D5.5问：问：1）应如何确定这些项目的每年投资额，使得第五年）应如何确定这些项目的每年投资额，使得第五年 末拥有资金的本利金额为最大？末拥有资金的本利金额为最大？ 2）应如何确定这些项目的每年投资额，使得第五年）应如何确定这些项目的每年投资额，使得第五年 末拥有资金的本利在末拥有资金的本利在330万的基础上使得其投资总万的基础上使得其投资总 的风险系数为最小？的风险系数为最小？解：解：（1）确定变量）确定变量1）我们设）我们设

29、xij=第第i年初投资于年初投资于j 项目的金额项目的金额(单位万元）根据单位万元）根据给定条件，将变量列于下表：给定条件，将变量列于下表： 年份年份项目项目12345Ax1Ax2Ax3Ax4Ax5ABx1Bx2Bx3Bx4BCx3CDx2D 801.11.251.4301001.55(10)(11)(2)约束条件约束条件 第一年：第一年： x1A+ x1B=200 第二年：第二年： x2A + x2B +x2D = 1.1 x1A 第三年：第三年： x3A + x3B + x3C =1.1x2A+1.25 x1B 第四年：第四年： x4A + x4B =1.1 x3A+1.25 x2B 第五

30、年：第五年： x5A = 1.1x4A + 1.25 x3B 此外：对项目此外：对项目B，C，D的投资额的限制有：的投资额的限制有： xiB 30 (i=1,2,3,4) x3C 80 x2D 100(3）目标函数）目标函数Max z=1.1 x5A +1.25 x4B +1.40 x3C +1.55 x2D 数学模型为：数学模型为：目标函数目标函数 MAX 1.1X5+1.25X9+1.40X10+1.55X11S.T. 约束约束 1) : X1+X6=200 约束约束 2) : -1.1X1+X2+X7+X11=0 约束约束 3) : -1.1X2+X3-1.25X6+X8+X10=0 约

31、束约束 4) : -1.1X3+X4-1.25X7+X9=0 约束约束 5) : -1.1X4+X5-1.25X8=0 约束约束 6) : X630 约束约束 7) : X730 约束约束 8) : X830 约束约束 9) : X930 约束约束 10) : X1080 约束约束 11) : X11100 xij 0 *最优解如下最优解如下* 目标函数最优值为目标函数最优值为 : 341.35 变量变量 最优解最优解 相差值相差值 - - - x 1 170 0 x 2 63 0 x 3 0 .044 x 4 0 0 x 5 33.5 0 x 6 30 0 x 7 24 0 x 8 26.8

32、 0 x 9 30 0 x 10 80 0 x 11 100 0 约束约束 松弛松弛/剩余变量剩余变量 对偶价格对偶价格 - - - 1 0 1.664 2 0 1.513 3 0 1.375 4 0 1.21 5 0 1.1 6 0 .055 7 6 0 8 3 0 9 0 .04 10 0 .025 11 0 .037目标函数系数范围目标函数系数范围: 变量变量 下限下限 当前值当前值 上限上限 - - - - X 1 无下限无下限 0 .055 X 2 0 0 .037 X 3 无下限无下限 0 .044 X 4 无下限无下限 0 0 X 5 0 1.1 1.12 X 6 -.055 0

33、 无上限无上限 X 7 -.05 0 0 X 8 0 0 .025 X 9 1.21 1.25 无上限无上限 X 10 1.375 1.4 无上限无上限 X 11 1.513 1.55 无上限无上限 常数项范围常数项范围: 约束约束 下限下限 当前值当前值 上限上限 - - - - 1 177.851 200 202.645 2 -24.364 0 2.909 3 -26.8 0 3.2 4 -7.5 0 3.636 5 -33.5 0 无上限无上限 6 0 30 87.273 7 24 30 无上限无上限 8 26.8 30 无上限无上限 9 26.364 30 37.5 10 76.8 8

34、0 106.8 11 97.091 100 124.3642) 所设变量与所设变量与1）相同，有：）相同，有：Min z =x1A+x2A +x3A+x4A+x5A+3(x1B+x2B+x3B+x4B)+ 4 x3C +5.5 x2Ds.t, x1A+ x1B=200 x2A + x2B +x2D - 1.1 x1A= 0 x3A + x3B + x3C -1.1x2A-1.25 x1B = 0 x4A + x4B -1.1 x3A-1.25 x2B = 0 x5A -1.1x4A -1.25 x3B = 0 xiB 30 (i=1,2,3,4) x3C 80 x2D 100 1.1 x5A

35、+1.25 x4B +1.40 x3C +1.55 x2D 33 0 xij 0 目标函数目标函数 MIN X1+X2+X3+X4+X5+3X6+3X7+3X8+3X9+4X10+5.5X1.T. 约束约束 1) : X1+X6=200 约束约束 2) : -1.1X1+X2+X7+X11=0 约束约束 3) : -1.1X2+X3-1.25X6+X8+X10=0 约束约束 4) : -1.1X3+X4-1.25X7+X9=0 约束约束 5) : -1.1X4+X5-1.25X8=0 约束约束 6) : X630 约束约束 7) : X730 约束约束 8) : X830 约束约束 9) :

36、X930 约束约束 10) : X1080 约束约束 11) : X11330*最优解如下最优解如下* 目标函数最优值为目标函数最优值为 : 1300 变量变量 最优解最优解 相差值相差值 - - - x 1 200 0 x 2 192.317 0 x 3 131.549 0 x 4 144.704 0 x 5 159.174 0 x 6 0 .5 x 7 0 .5 x 8 0 .5 x 9 0 .5 x 10 80 0 x 11 27.683 0 约束约束 松弛松弛/剩余变量剩余变量 对偶价格对偶价格- - - 1 0 10 2 0 10 3 0 10 4 0 10 5 0 10 6 30 0 7 30 0 8 30 0 9 30 0 10 0 0 11 72 0 12 0 -10目标函数系数范围目标函数系数范围: 变量变量 下限下限 当前值当前值 上限上限 - - - - X 1 无下限无下限 1 1.5 X 2 .024 1 1 X 3 1 1 1.781 X 4 1 1 1.71 X 5 1 1 1.645 X 6 2.5 3 无上限无上限 X 7 2.5 3 无上限无上限 X 8 2.5 3 无上限无上限 X 9 2.5 3