运筹学Chap线性规划对偶理论及其应用PPT学习教案

1、会计学1 运筹学运筹学Chap线性规划对偶理论及其应用线性规划对偶理论及其应用 第1页/共51页 原问题对偶问题 0, 85.02 25.124 4868 203060max 321 321 321 321 321 xxx xxx xxx xxx xxxz 0, 205.05.1 30126 60248 82048min 321 321 321 321 321 uuu uuu uuu uuu uuuw 当 时，工厂的决策者认为这两种考虑有相同结果 ，都是最优方案！ wzminmax 产品产品 机器机器 ABC M861 N421.5 P210.5 令每天生产A、B、C的产量分别为x1、x2、x

2、3 令M、N、P的单位时间租金分别为u1、u2、u3 如果原问题是在资金有限的情况下使产量最大，则相应的对 偶问题就是在产量有限的情况下使成本最小。 第2页/共51页 原线性规划问题（LP） 原问题（LP）的对偶问题（LD ） 0 . z min x bAx ts cx 0 . max u cuA ts ubw 对偶问题的变量表示 单位资源的价值。 在实际问题中，对偶问题 的目标函数的系数表示可 利用资源的数量。 第3页/共51页 例： 求下面问题的对偶 5 , 1, 0 12 26 . 215min 5321 4321 31 jx xxxx xxxx ts xxz j 解: 10211 01

3、611 ,)1 , 2(,)0 , 0 ,21, 0 , 5(Abc TT 第4页/共51页 0 0 21 0 5 10 01 26 11 11 . . 12max 2 1 2 1 u u ts u u 其对偶问题为 0 0 2126 0 5 . . 2max 2 1 21 21 21 21 u u uu uu uu ts uu 写成分量形式，即 第5页/共51页 0, 1505 ( 10032 17025 1810max 21 21 21 21 21 xx xx xx xx xxZ 原原问问题题） 0, 18532 1025 150100170min 321 321 321 321 yyy

4、yyy yyy yyyW （对对偶偶问问题题） 第6页/共51页 个约束条件对应的是原问题中的 x2变量，依此类推。 当原问题有m个约束条件，则对 偶问题有m个决策变量。对偶问 题的u1变量对应的是原问题中的 第一约束条件，对偶问题的u2变 量对应的是原问题中的第二约束 条件，依此类推。 第7页/共51页 i 量取任意值； 如原问题的第i个决策变量无符 号限制，则对偶问题中第i个约 束条件为等式约束。 第8页/共51页 写出下列线性规划 问题的对偶问题： 0, 3 22 252 max 21 321 321 321 321 xx xxx xxx xxx xxxz 0, 3 22 252 min

5、 21 321 321 321 321 xx xxx xxx xxx xxxz 0, 12 12 1 3225max 21 321 321 321 321 uu uuu uuu uuu uuuw 0, 12 12 1 3225min 21 321 321 321 321 uu uuu uuu uuu uuuw 先化为最小化问题： 最小化问题的对偶问题：也可把对偶问题化为 最小化问题： 变成目标函数的系数 系数变成约束条件右侧值 变成第一个约束条件的系数 第9页/共51页 第10页/共51页 原问 题 目标函数 max目标函数 min m个 = n个 = n个 0 0 无符号限制 m个 0 0

6、无符号限制 目标函数的系数 约束条件右端常数 系数矩阵 A 约束条件右端常数 目标函数的系数 系数矩阵 AT 约束条件 约束条件 变 量 变 量 对偶问题 e.g. 1 写出(LP)问题 的(LD)问题 max z=2x1+3x2-5x3+x4 s.t. 4x1+x2-3x3+2x4 5 3x1-2x2 +7x4 4 -2x1+3x2+4x3+x4=6 x1 0, x2,x3 0 , x4 无符号限制 min w=5u1+4u2+6u3 s.t. 4u1+3u2-2u3 2 u1-2u2+3u3 3 -3u1 +4u3 -5 2u1+7u2+u3 = 1 u1 0, u20 , u3无符号限制

7、 第11页/共51页 123 min23fxxx 123 123 123 123 , 326 4235 39 0, xxx xxx xxx xxx 符号不限0, 123 max659zyyy 123 123 123 123 ,y0,y0 341 2232 353 yyy yyy yyy y 符号不限 对偶问题 e.g. 2 写出(LP)问题的(LD)问题 第12页/共51页 e.g. 3原问题 无约束、 4321 432 431 4321 4321 0 0 6 442 2 5 3 532min ,xxx,x xxx xxx xxxx xxxxZ 无约束 321 321 321 31 21 32

8、1 , 0, 0 1 4 523 3 2 2 645max yyy yyy yyy yy yy yyyW 对偶问题 第13页/共51页 e.g. 4原问题 0, 564 37 3 2532 432max 321 321 321 321 321 xxx xxx xxx xxx xxxZ 无约束 , 4675 34 3 2 32 532min 321 321 321 321 321 yyy yyy yyy yyy yyyW 解：对偶问题 第14页/共51页 第15页/共51页 p对偶规划的基本性质 1、对偶的对偶就是原始问题 max z=-CTX s.t. -AX-b X 0 min y=-bTu

9、 s.t. -ATu-C u 0 max y=bTu s.t. ATuC u 0 min z=CTX s.t. AXb X 0 对偶的定 义 对偶的定 义 第16页/共51页 2、对偶定理 （1）弱对偶性（可行解的目标函数值之间的关系） 设X、Y分别是原始问题和对偶问题的可行解 f=CTX YTAX YTb=z min T fC X . . 0 T A YC st Y max T zb Y TTTTT C XA YXY AXY bb Y . . 0 AXb st X 第17页/共51页 11 ( 1,2, ) ( 1,2,) ( 1,2, ) ( 1,2,) j i nm jjii ji j

10、i xjn y im c xb y xjn y im 如果是原问题的可行解 是其对偶问题的可行解 且有 则是原问题的最优解 是其对偶问题的最优解 （3）最优性 （2）无界性 如果原问题（对偶问题）具有无界解， 则其对偶问题（原问题）无可行解。 第18页/共51页 无界性在一对对偶问 题，若其中一个问题可行 但目标函数无界，则另一 个问题不可行；反之不成 立。这也是对偶问题的无 界性。 关于无界性有如下结论： 问题无界 无可 行解 无可行解 无可行解 问题无界 对偶问题原问题 0,0 2 4 2max 21 21 21 21 xx xx xx xxZ 无界 如 ： （原） 0,0 1 2 24m

11、in 21 21 21 21 yy yy yy yyW 无可 行解 （对） 第19页/共51页 已知 12 123 123 123 : max2 2 21 ,0 Zxx xxx xxx x x x 原 12 12 12 12 12 : min2 21 2 0 ,0 Wyy yy yy yy y y 对 试用对偶理论证明原问题无界。 解： =（0,0,0）是 P 的一个可行解，而 D 的第一 个约束条件不能成立（因为y1 , y2 0)。因此，对偶问题 不可行，可知，原问题无界。 _ X 第20页/共51页 （4）强对偶性（最优解的目标函数之间的关系） 如果原问题有最优解，则其对偶问题也一定有

12、最优解，且两者的目标函数值相等 设X*、Y*分别是原始问题和对偶问题的最优解 f=CTX*=Y*TAX*=Y*Tb=z 第21页/共51页 * 11 0. B TT B X cc B Ac B Ac 证明设是原问题的一个最优解，它对应的基矩阵 必存在即得到 * , TT B YBcA Yc 令则有 * *1TTTT BB Y b Yb Bcc B b 这时是对偶问题的可行解，它使 * *1TT B X c Xc B b 又由于是原问题的最优解，故 * * TT c Xb Y Y 由此得到 可见是对偶问题的最优解。 第22页/共51页 在线性规划问题的最优解中， 如果对应某一约束条件的对偶变量值

13、为非零， 则该约束条件取严格等式； 反之如果约束条件取严格不等式， 则其对应的对偶变量一定为零。 即 1 1 0 0 n iijji j n ijjii j ya xb a xby 如果，则 如果，则 第23页/共51页 123 123 123 123 min 23 . .331 22 ,0 xxx stxxx xxx x x x 例2给定线性规划问题 12 1 11 (,), 7 7 T yy y 已知对偶问题的最优解为 试用互补松弛性质求原问题的最优解. 第24页/共51页 12 12 12 12 12 max2 . .32 23 31 ,0 yy s tyy yy yy yy 12 31

14、2 , 0, y y xy y 将最优解的值代入约束条件，得第3个约束为严格 不等式，由互补松弛性得又由于的值均大于 零，因此原问题的两个约束条件应取等式，故有 123 123 31 232 xxx xxx 解：先写出它的对偶问题 12 123min 4,5/7, ( ,)(4/7,5/7,0)23/7 TT xx xx x xf 求解后得到/7故原问题的最优解为 第25页/共51页 12345 12345 12345 min23523 . .234 233 0,1,2,5 j xxxxx stxxxxx xxxxx xj (1,0,0,0,1)Tx 已知原问题的最优解为 试用互补松弛性质找出

15、对偶问题的最优解. 第26页/共51页 第27页/共51页 设 x0是（3.1）的基本解，它对应的基矩阵为B， 令u0=cBB-1，如u0是（3.1）的对偶问题的可行解，即 对所有j，zj-cj=u0pj-cj0，则称x0是原问题的对偶可行 的基本解。 * * * s x x x 0 . z min x bAx ts cx 3.1 对偶可行的基本解不一定是原问题的可行解，当对偶 可行的基本解也是原问题的可行解时，则它是原问题 的最优解。 第28页/共51页 第29页/共51页 0 1 bBb 0min i i r bb r x 0 ij a 0|max rj rj jj j rk kk a a

16、 zc a zc k x rk a 第30页/共51页 标准化 乘以(-1) i c B c B x jj zc 3100 Bx1x2x3x4 0 x3-1-1-110 0 x4-2-2-301 3100 初始对偶单纯形表： 出基 进基 主元 直到B0，停止。 第31页/共51页 第32页/共51页 0, 2 33 8436 23min 321 321 321 321 xxx xxx xxx xxxz 解：在第2个约束方程的两边同乘以-1，然后引入变量x4,x5得： 0, 2 33 8 436 23min 54321 5321 4321 321 xxxxx xxxx xxxx xxxz 用对偶

17、单纯形法求解得最优解 ： , 4, 3/2 41 xx0 532 xxx 最优目标函数值 ：3/2 min f 第33页/共51页 第34页/共51页 第35页/共51页 约束条件右侧（即资源）改变1个单位时，目标函数（即 利润）的变化量，它度量了约束条件对应的那种资源的价值 ，经济学上称为影子价格。 对偶价格：约束条件的右侧值每增加一个单位导致最优解的 增加量。对偶价格只适用于约束条件右侧值变化比较小的情况 。当资源越来越多时，约束条件右侧的值也越来越大，其它的 约束条件就有可能成为紧约束，限制目标函数值的变大。 第36页/共51页 第37页/共51页 例3.7：求下列原问题的最优解及影子价

18、格和对偶问题的最优解 及影子价格。 min z=4x1+7x2 +8x3 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； 第38页/共51页 例3.8：A工厂计划

19、生产甲、乙两种产品。每千克产品的销售价 格和能源消耗量、以及能源资源见表3-26，怎样安排生产计划 才能使A工厂获益最大？ 解：x1：产品甲的计划生产量；x2：产品乙的计划生产量，则有如下线 性规划问题： max z=7x1 + 12x2 (总销售收入) s.t. 9x1 + 4x2 360 (煤资源限制) 4x1 + 5x2 200 (电资源限制) 3x1 + 10 x2 300 (油资源限制) x1 0，x2 0 (非负条件) 用单纯形法求解得：x1=20，x2=24。 第39页/共51页 其对偶问题是： min w = 360y1+200y2 +300y3 s.t. 9y1 + 4y2

20、+ 3y3 7 4y1 + 5y2 + 10y3 12 y1 0，y2 0，y3 0 用单纯形法求解得：y1=0，y2 =1.36，y3=0.52。 所以，煤、电、石油的影子价格分别为：0、1.36、0.52。 直观上，如果在一个生产计划下，每一种资源都有所剩余， 必然还可进一步通过剩余资源的组合增加生产收入(例如， 将x2增加到24)。这表明该生产计划必定不是最优的生产计划 。 换言之，如果一个生产计划是最优的，则该计划必然会耗尽 某些资源。 第40页/共51页 在一个最优生产计划下，被耗尽的资源对于A工厂来说就是 所谓的稀缺资源。 如果追加这些稀缺资源的量，则可进一步提高产量以增加生 产收入。 于是，提出了这样一个实际问题：如果在一个最优生产计划 下，出现多种稀缺资源，那么，哪些稀缺资源最值得追加？ 或者说，如果A工厂始终按照最优化的计划组织生产，哪些 资源对其最为紧缺？ 另外，根据稀缺资源对提高整个生产收入的贡献，A工厂甚 至可考虑以高于市场价格的采购策略追加这些资源。 这类实际问题，可通过影子价格得以解答。 第41页/共51页 第二，是否将投资用于购 买设备，以扩大生产能力，若 市价低于某设备的影子价格， 可考虑买进该设备，否则不宜 买进。 第42页/共51页 根据影子价格确定某种资源的追加价值。 例如：煤、电、石油的影子价格分别为