运筹学25-27-课件.ppt

1、第5节 对偶问题的经济解释影子价格 在单纯形法的每步迭代中，目标函数取值z=CBB-1b，和检验数CN-CBB-1N中都有乘子Y=CBB-1，那么Y的经济意义是什么?设B是max z=CXAXb，X0的最优基，由-Yb=-CB B-1b可知 z*=CBB-1b=Y*b。对z求偏导数，得 *B*YBCbz1 由上式可知，变量yi*的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函的最优值的变化。eg.7 max z=2x1+3x2 x1+2x2 8 4x1 16 4x2 12 x1,x2 0cj23000 CBXBbx1x2x3x4x52x141001/400 x5400-21/21

2、3x22011/2-1/80-z-1400-3/2-1/80y1*=1.5，y2*=0.125，y3*=0。b1：8 9 Q2(4，2.5)z*=15.5 z*=z*-z*=3/2=y1*b2：16 17 Q2”(4.25，1.875)z*”=14.125 z*=z*”-z*=1/8=y2*b3：12 13 z*=0=y3*这说明是其他条件不变的情况下，若设备增加一台时，该厂按最优计划安排生产可多获利1.5元；原材料A增加1kg，可多获利0.125元；原材料B增加1kg，对获利无影响。yi*的值代表对第i种资源的估价-影子价格。这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子

3、价格”。在该厂现有资源和现有生产方案的条件下，设备的每小时租费为1.5元，1kg原材料A的出让费为除成本外再附加0.125元，1kg原材料B可按原成本出让，这时该厂的收入与自己组织生产时获利相等。影子价格随具体情况而异，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价高于企业影子价格时，则企业的决策者应把已有资源卖掉。可见影子价格对市场有调节作用。第6节 偶单纯形法 前节讲到原问题与对偶问题的解之间的对应关系时指出：在单纯形表中进行迭代时，在b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。通过逐步迭代，当在检验数行

4、得到对偶问题的解也是基可行解时，根据性质(2)、(3)可知，已得到最优解。即原问题与对偶问题都是最优解。根据对偶问题的对称性 可以这样考虑：若保持对偶问题的解是基可行解，即cj-CBB-1Pj0，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最优解。其优点是原问题的初始解不一定是基可行解，可从非基可行解开始迭代。设原问题max z=CXAX=bX0 又设B是一个基。不失一般性，令B=(P1，P2，Pm)，它对应的变量为 XB=(x1，x2，,xm)当非基变量都为零时，可以得到XB=B-1b。若在B-1b中至少有一个负分量，设(B-1b)i0，并且在单纯形表的检验数行中的检验

5、数都为非正，即对偶问题保持可行解，它的各分量是(1)对应基变量x1，x2，,xm的检验数是i=ci-zi=ci-CBB-1Pj=0，i=1,2,m(2)对应非基变量xm+1，xn的检验数是j=cj-zj=cj-CBB-1Pj0，j=m+1,n 每次迭代是将基变量中的负分量xl取出，去替换非基变量中的xk，经基变换，所有检验数仍保持非正。从原问题来看，经过每次迭代，原问题由非可行解往可行解靠近。当原问题得到可行解时，便得到了最优解。对偶单纯形法的计算步骤如下：(1)根据线性规划问题，列出初始单纯形表。检查b列的数字，若都为非负，检验数都为非正，则已得到最优解。停止计算。若检查b列的数字时，至少还

6、有一个负分量，检验数保持非正，那么进行以下计算。(2)确定换出变量 按min(B-1b)i(B-1b)i0(B-1b)l对应的基变量xl为换出变量(3)确定换入变量 在单纯形表中检查xl所在行的各系数lj(j=1,2,，n)。若所有lj0，则无可行解，停止 计算。若存在lj0 (j=1,2,，n),计算 按规则所对应的列的非基变量xk为换入变量，这样才能保持得到的对偶问题解仍为可行解。lkkkljljjjjazcaazc0min(4)以lk为主元素，按原单纯形法在表中进行迭代运算，得到新的计算表。重复步骤(1)(4)。例6 用对偶单纯形法求解 min=2x1+3x2+4x3x1+2x2+x33

7、2x1-x2+3x34x1，x2，x30解解 先将此问题化成下列形式，以便得到对偶问题的初始可行基 max z=-2x1-3x2-4x3-x1-2x2-x3+x4 =-3-2x1+x2-3x3 +x5=-4xj0，j=1,2,5初始单纯形表，见表2-6。表 2-8表2-8中，b列数字全为非负，检验数全为非正，故问题的最优解为X*=(11/5，2/5，0，0，0)T若对应两个约束条件的对偶变量分别为y1和y2，则对偶问题的最优解为Y*=(y1*,y2*)=(8/5,1/5)eg.8 用对偶单纯形法求解 min w=2x1+3x2+4x3 x1+2x2+x3 1 2x1-x2+3x3 4 x1,x

8、2,x3 0解：max z=-2x1-3x2-4x3+0 x4+0 x5 -x1-2x2-x3+x4 =-1 -2x1+x2-3x3 +x5=-4 x1,x2,x3,x4,x5 0CB00XBx4x5b-1-4-2x1-3x2-4x30 x40X5出出出x4,x5 0 最优最优解：最优解：x1*=2，x2*=0，x3*=0，x4*=1，x5*=0目标值：目标值：w*=-z*=4从以上求解过程可以看到对偶单纯形法有以下优点：(1)初始解可以是非可行解，当检验数都为负数时就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。(2)当变量多于约束条件，对这样的线性规划问题用对偶单纯形法计算可

9、以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解。(3)在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法，这样可使问题的处理简化。对偶单纯形法的局限性主要是，对大多数线性规划问题，很难找到一个初始可行基，因而这种方法在求解线性规划问题时很少单独应用。0,40025005.2516002200034max515142132154321xxxxxxxxxxxxxxxz练习1 求解0,2 82 4 32min 32132321321321xxxxxxxxxxx s.txxxz例：0,2 -82 4 -32max6543216

10、3253214321321xxxxxxxxxxxxxxxxx s.txxxz cj-1 -2 -3 0 0 0bcBxB x1 x2 x3 x4 x5 x6 0 0 0 x4 x5 x6-1 1 -1 1 0 0 1 1 2 0 1 0 0 -1 1 0 0 1 -4 8 -2 j-1 -2 -3 0 0 0 j 1 3x1x5x6-1001 -1 1 -1 0 0 40 2 1 1 1 0 4 0 -1 1 0 0 1 -2j0 -3 -2 -1 0 0 j cj-1 -2 -3 0 0 0bcBxB x1 x2 x3 x4 x5 x6-1 0 0 x1 x5 x6 1 -1 1 -1 0

11、0 0 2 1 1 1 0 0 -1 1 0 0 1 4 4 -2 j 0 -3 -2 -1 0 0 j 3 x1 x5 x2-10-21 0 0 -1 0 -1 60 0 3 1 1 2 0 0 1 -1 0 0 -1 2j0 0 -5 -1 0 -3 10 0 0 0 2 6*zXT练习练习2 用用对偶单纯型求解0,44262.35)(min432143214321421xxxxxxxxxxxxtsxxxxf解：化原问题为适合对偶解法的标准型解：化原问题为适合对偶解法的标准型0,44262.35)(max6543216432154321421xxxxxxxxxxxxxxxxtsxxxxf对

12、偶单纯型法的单纯型表(min)答：最优解为答：最优解为x1=14,x3=8,x2=x4=0,OBJ=142.7 灵敏度分析“心有灵犀一点通”灵敏度分析又称为后优化分析Post-optimization Analysis以前讨论线性规划问题时，假定ij，bi,cj都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变，cj值就会变化；ij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。因此提出这样两个问题：(1)当这些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；(2)或者这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变

13、。后一个问题将在第8节参数线性规划中讨论。在单纯形法迭代时，每次运算都和基变量的系数矩阵B有关，因此可以把发生变化的个别系数，经过一定计算后直接填入最终计算表中，并进行检查和分析，可按表2-9中的几种情况 进行处理。原原问问题题 对对偶偶问问题题 结结论论或或继继续续计计算算的的步步骤骤 可行解 可行解 表中的解仍为最优解 可行解 非可行解 用单纯形法继续迭代求最优解 非可行解 可行解用 对偶单纯形法继续迭代求最优解 非可行解 非可行解 引进人工变量，编制新的单纯形表，求最优解 下面就各种情况分别按节进行讨论。njpBCcABCCNBCCjBjjBBNN,2,1,0 0 0 :111 或或最优

14、性条件分析 变化对最优解的影响。j ,ijiacb0 :1bBXB可行性条件的变化资源ib 1.7TiTmiiiibbbbbbbbbbbb)0b 0 0()(21 bBbBbbBbBXB1111)(.,0 11这里用到可行性条件保持问题的最优性不变的变化范围求出由ibbBbB 设 XB=B1b 是最优解，则有XB=B1b0 b 的变化不会影响检验数 b 的变化量 b 可能导致原最优解变为非可行解例1 已知下述问题的最优解及最优单纯形表,0,124 164 82 00032max54321524132154321xxxxxxxxxxxxxxxxxz.,)12使最优基不变的变化范围求 b.4 )2

15、1时的最优解求b最优单纯形表如下:0-1/8-3/2000-1/81/2102311/2-2004001/40014200032bBXBC5x4x3x2x1x1x5x2x14 Z)4 0 0 2 4(,*TX此时22216 1):bbb解08/12/112/1204/101B2441216808/12/112/1204/101*bBXB由最优单纯形表得:)(012bbBb221118/12/14/12440008/12/112/1204/10244)(bbbBbBbbB0008/22/44/4222bbb08/202/404/4222bbb.1682最优基不变bTTbb)0 0 4()0 0

16、()214 44 28024400408/12/112/1204/10244)(111bBbBbbB不可行!用对偶单纯形法计算-3/4-1/20001/400103x23-1/2-1/41002x3001/40014x120-1/8-3/2000-1/81/2102+2311/2-2004-8x5001/40014+0 x12ix5x4x3x2x1bXBCB00032x23/4-2)(17 :.0,0,2,3,4 :*5*4*3*2*1元目标值最优解zxxxxx 7.2 价值系数 cj 的灵敏度分析 cj 变动可能由于市场价格的波动，或生产成本的变动cj 的灵敏度分析是在保证最优解的基变量不变

17、的情况下，分析cj 允许的变动范围cj cj 的变化会引起检验数的变化，有两种情况非基变量对应的价值系数变化，不影响其它检验数基变量对应的价值系数变化，影响所有非基变量检验数.01分两种情况讨论进行分析根据最优性条件NBCCBNN的变化非基变量价值系数kc.1kBkkpBCc1:原检验数/:kkkkkccccc变化kkkBkkkcpBCcc1/.,0 :/此时最优解不变令kkkkkcc例2 求例1 c4的变化范围,使最优解不变.0-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x204c8/1)8/1(8/14

18、44c由解:.8/1 4时最优解不变即c的变化基变量价值系数rc.2NBCCBNN1 原BBBCCC 若NBCNBCNBCCNBCCCBNBBNBBNN1111/)(则分析:)0 0 0()(:21 rBmrBcCccccC其中.变化影响所有可见jrc方法:.0 1/的变化范围求出令rBNNcNBC例3 求例1 c2的变化范围,使最优解不变.0-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x2解:0-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1

19、bXBCB00032x2)0 0(),3 0 2(2cCCBB 1/8)-(-3/2)(43N)(/4/3/n44414/433313/3pcpBcpcpBcBBBB02232/120)c 0 0(232233/3cpcB08818/12/14/1)c 0 0(812244/4cpcB1322cc.13 2时最优解不变即c7.3 技术系数 aij 的灵敏度分析 技术系数aij变化的影响比较复杂 对应基变量的 aij，且资源bi已全部用完 对应基变量的 aij，但资源bi未用完 对应非基变量的 aij，且资源bi全用完或未用完1、对应基变量的 aij，且资源bi已全部用完 aij=02、对应基变

20、量的 aij，但资源bi未用完 aij xn+i/xj 上述两个公式不是充分必要的，为什么？B1发生变化，从而引起非基变量检验数 cj zj 的变化3、对应非基变量的 aij 只影响对应非基变量xj的检验数 cj zj 若 aij 0，不会破坏最优解 若 aij=12;x3+x4+x5+x6+x7=15;x1+x4+x5+x6+x7=12;x1+x2+x5+x6+x7=14;x1+x2+x3+x6+x7=16;x1+x2+x3+x4+x7=18;x1+x2+x3+x4+x5=19;endGlobal optimal solution found at iteration:9 Objective

21、 value:4400.000 Variable Value Reduced Cost X1 5.000000 0.000000 X2 2.000000 0.000000 X3 8.000000 0.000000 X4 0.000000 0.000000 X5 4.000000 0.000000 X6 0.000000 66.66667 X7 3.000000 0.0000003,2,1,3,2,1,060100100003030.10401030152515max33231332221231211123222123222113121113121133312221131211jixxxxxxx

22、xxxxxxxxxxxxxxxtsxxxxxxxijmodel:max=-15*x11+25*x12+15*x13-30*x21+10*x22-40*x31-10*x33;-x11+x12+x13=0;-x11+3*x12-x13=0;-3*x21+x22+x23=0;-x21+x22-x23=0;x11+x21+x31=100;x12+x22+x32=100;x13+x23+x33=60;endGlobal optimal solution found at iteration:5 Objective value:500.0000Variable Value Reduced CostX11 100.0000 0.000000X12 50.00000 0.000000X13 50.00000 0.000000X21 0.000000 15.00000X22 0.000000 0.000000X31 0.000000 45.00000X33 0.000000 10.00000X23 0.000000 0.000000X32 0.000000 0.000000