运筹学导论之单纯形法与敏感性分析(共106页).ppt

1、1第3章 单纯形方法&灵敏度分析23.1 等式形式的线性规划模型为了方便单纯形法的计算，对模型的约束有如下两个要求：(1) 所有的约束都是等式(变量的非负限制除外)，并且具有非负的右端项；(2) 所有变量是非负的。 这两项要求目的在于使得单纯形方法标准化和简单化。这也就是现在的所有商业软件都直接运行不等式约束、非负的右端项和无限制变量。在进行单纯形法求解前，模型的任何必要处理都在软件内部完成。33.1.1 将不等式转化为带有非负右端项的等式约束在()约束中，右端项可被视为资源可利用性限制的描述，在这种情况下，左端项表示模型的活动(变量)对这些有限资源的用量。因此， ()约束的右端项与左

2、端项之间的差构成未用的或松弛的资源量。为了把()不等式约束转为等式约束，在约束左端增加非负的松弛变量(Slack Variable). 例如在Reddy Mikks模型中，相当于原料M1的约束给出如下：6x1+4x224定义s1作为M1的松弛的或未用的量，约束可以转化为如下等式约束：6x1+4x2+s1=24, s104在()约束设置了模型的活动(变量)对的下限。因此， 可以将()约束的左端项超出最下限制的量表示为剩余。为了把()不等式约束转为等式约束，在约束左端减去非负的剩余变量(Surplus Variable). 例如在营养配方模型（例2.2-2）中，表示最小饲料需求的约束是：x1+x2

3、800定义S1作为剩余变量，约束可以转化为如下等式约束：x1+x2-S1800, S105对于让等式约束的右端项是非负的，这个条件总是可以满足的，必要时可以在得到的方程两端乘以(-1). 例如，约束-x1+x2-3则等价方程为-x1+x2+s1=-3，s10对上式两边乘以(-1), 转化为非负的右端项，便得到我们需要的约束等式，即x1-x2-s1=-363.1.2 无限制变量处理方法在单纯形方法中，要求所有的决策变量是非负的。然而很多现实问题中往往很多的决策变量恰恰是不要求非负的。例如例2.3-6中介绍的多周期生产平滑模型，其中要求每个周期在开始时要根据周期需求上下调整。如果xi是周期 i 的

4、劳动力数量，则xi+1是周期 i+1的劳动力数量，可以表示为xi+1= xi+ yi+1变量yi+1必须无符号限制，它运行xi+1相对于xi增加或减少，即雇佣或解雇工人。可以采用如下替换方法来满足这个要求11111,00iiiiiyyyyy其中，这样的替换原理是什么？7假定在周期1中，劳动力是x1=20名工人，在周期2中，劳动力将增加5名，达到25名。依据变量 和变量 ，这等价于 ，或者y2=5-0=5. 类似地，如果在周期2中劳动力减少到16名，则我们有 或者y2=0-4=-4. 替换还运行劳动力不作改变的可能性，此时两个变量均为0来实现。2y2y2250yy和2204yy和那么 和 能否同

5、时取正值？这种情况是不会发生的，否则这意味着相同的时间内既雇佣工人又解雇工人。通过数学的证明也发现，在任意的单纯形中，这两个值同时取正值是不可能的。2y2y83.2 从图形解到代数解的转换在2.2节介绍的二元决策变量的线性规划模型的图形求解思想奠定了代数单纯形法发展的基础。在图解方法中，解空间由表示约束的半空间描述，而在单纯形法中，解空间由m个同时成立的线性方程和n个非负变量表示。9根据图形，容易解空间有无穷个解点的原因，那么如何能从解空间的代数表示中得出类似的结论？在代数表示上，方程的个数m小于决策变量个数n 。如果m=n，方程是相容的，则方程组只有唯一解；如果mn，假定方程组是相容的，则方

6、程组有无穷多的解。在代数中如何定义角点：在mn (mn)阶方程组中，如果令(n-m)个变量等于0，然后求解其余的含m个变量的m个方程，如果有唯一解，则称相应的解为基本解，它一定对应解空间的一个(可行或不可行)角点，这意味着角点的最大数目为!()!mnnCm nm1012121212max232425,0zxxstxxxxxx方程组有m=2个方程和n=4个变量。因此最大数目的角点为4!/(2!2!)6mnC到底令哪些点为零才能对应一个特定的角点？21122121212425,0 xxsxxsx x s s解空间(x1，x2，s1，s2)最优点(1,2,0,0)2x1xABCDEF10s 20s

7、(0，0，4，5)(0，2.5，1.5，0)(2，0，0，3)(5，0，-6，0)(0，4，0，-3)11非基（零）变量基变量基本解相应的角点可行否？目标值Z（x1, x2）（s1, s2）(4, 5)A是0（x1, s1）（x2, s2）(4, -3)F否-（x1, s2）（x2, s1）(2.5, 1.5)B是7.5（x2, s1）（x1, s2）(2, 3)D是4（x2, s2）（x1, s1）(5, -6)E否-（s1, s2）（x1, x2）(1, 2)C是8（最优点）可以看到，当问题的大小增加后（即m与n变大），枚举所有角点的过程包含巨量的计算，如m=10和n=20，必须求解184

8、756个1010阶的方程。而在很多实际的问题中，很多是有成百上千的变量和约束的问题。123.2 单纯形方法3.3.1 单纯形方法的迭代本质2x1xABCDEF10s 最优点（x1=1，x2=2）20s 12max23zxx正常情况下，单纯形从原点（A点）开始，此时Z=0，能否在当前零值的基础上，通过增加非基变量x1和x2来增加Z值？图形显示，增加x1和x2将增加Z。单纯形方法每次要求增加一个变量，且选择使得Z有最大改善率的那个变量。因此选择增加x2具有最大改善率，因此增加x2直到角点B，在点B，再增加x1的值，达到改进的角点C，他是最优点。因此单纯形方法的路径是沿着ABC。沿着路径的每个角点与

9、一步迭代是对应的，单纯形方法是沿着解空间的边缘移动，不能抄近路，直接AC132x1xABCDEF10s 最优点(1,2,0,0)20s (0，2.5，1.5，0)(2，0，0，3)x1x2s1s2A0045B02.51.50C1200D2003(0，0，4，5)单纯形方法的本质就是换基！角点基变量零变量As1 ，s2x1， x2Bs1 ，x2x1 ，s2Cx1 ，x2s1 ，s214相应的角点基变量非基（零）变量A（s1, s2）（x1, x2）B（x2, s1）（x1, s2）C（x1, x2）（s1, s2）可以看到，在基变量和非基变量中的变化模式随着解沿着路径ABC的移动而改变。AB，在

10、A处的非基变量x2变成B处的基变量，并且在A处的基变量s2变成在A处的非基变量，称X2为进基变量，s2为离基变量，类似地，在点B，x1进基，s1离基，因此到了C点15Reddy Mikks模型是Max Z=5x1+4x2St 6x1+4x224 （原料M1） x1+2x26 （原料M1） -x1+x21 （市场限制） x2 2 （需求限制） x1, x2012123412112212324121234max54000064242612,0zxxssssstxxsxxsxxsxsx x s s s s12540zxx163.3.2 单纯形算法的计算细节基Zx1x2s1s2s3s4解Z1-5-40

11、0000Z 行s1064100024s1 行s201201006s2 行s30-1100101s3 行s400100012s4 行初始解是最优解吗？目标函数表明可以增加x1或x2来改进这个解，选择具有最正的系数的变量选择具有最正的系数的变量x1为进基变量为进基变量，这个等价于将目标函数中最负系数的变量作为进基变量。最优性条件最优性条件，该条件确定进基变量单纯形迭代开始于原点（x2, x2）=(0, 0)，因此, 在初始点处的非基（零）变量：（x1, x2），在初始点处的基变量： （s1, s2, s3, s4）即 Z=0， s1=24, s2=6, s3=1, s4=217基进基x1解比值（或

12、截距）s1624x1=24/6=4 最小值s216x1=6/1=6s3-11x1=1/-1=-1 （不考虑）s402x1=2/0= （不考虑）结论：x1进基，s1离基 从单纯形表中确定离基变量的方法是，计算方程的右端项（解列）与相应的在进基变量x1下方的约束系数的非负比可行性规则可行性规则最小非负比自动识别当前基变量s1作为离基变量，并指定进基变量x1的新值为4181212112212324121234max54:6424:26:1:2,0zxxaxxsbxxscxxsdxsx x s s s sabcd-1461234561235s1=0s2=0s3=0s4=01/-1=-124/6=46/

13、1=6ABC在点B处的非基（零）变量： （s1, x2）在点B处的基变量： （x1, s2, s3, s4）19进基变量和离基变量如何进基变量和离基变量如何“交换交换”？进基基Zx1x2s1s2s3s4解Z1-5-400000离基s1064100024枢轴行s201201006s30-1100101s400100012枢轴行一些概念一些概念20基于高斯基于高斯-乔丹行操作来计算新的基本解乔丹行操作来计算新的基本解1. 枢轴行 a. 在基列中，以进基变量替换离基变量 b. 新的枢轴行=当前枢轴行枢轴元素2. 其他所有行，包括Z行 新的行=当前行-当前枢轴列的系数新的枢轴列将该方法应用到上表将该方

14、法应用到上表在基列中，以x1替换s1 新的x1行=当前s1行6=(0 6 4 1 0 0 0 24)/6=(0 1 2/3 1/6 0 0 0 4)新的Z行=当前Z行-(-5)新的x1行=(1 -5 -4 0 0 0 0 0)-(-5) (0 1 2/3 1/6 0 0 0 4)=(1 0 -2/3 5/6 0 0 0 20)新的s2行=当前s2行-(1)新的x1行=(0 1 2 0 1 0 0 6)-(1) (0 1 2/3 1/6 0 0 0 4)=(0 0 4/3 -1/6 1 0 0 2)新的s3行=当前s3行-(-1)新的x1行=(0 -1 1 0 0 1 0 1)-(-1) (0

15、1 2/3 1/6 0 0 0 4)=(0 0 5/3 1/6 0 1 0 5)新的s4行=当前s4行-(0)新的x1行=(0 0 1 0 0 0 1 2)-(0) (0 1 2/3 1/6 0 0 0 4)=(0 0 1 0 0 0 1 2)21新的基本解是（x1, s2, s3, s4），因此新的单纯形表为进基基Zx1x2s1s2s3s4解Z10-2/35/600020s1012/31/60104离基s2004/3-1/61002s3005/31/60105s400100012新的基本解是（x1, s2, s3, s4）=(4 2 5 2)，而Z=20与下面的公式计算结果一致新的Z=原来的

16、Z + 新的x1的值 它的目标系数=0+4 5=2022基进基x2解比值x12/34X2=4/(2/3)=6s24/32X2=2/(4/3)=1.5 最小值s35/35X2=5/(5/3)=3s412X2=2/1=2在前表中，最优性条件最优性条件表明，x2是进基变量，由可行性条件可行性条件可得下表因此，s2离开基本解，并且x2的新值是1.5，相应增加的Z值是2/3x2=2/31.5=1,它产生新的Z=20+1=21在基列中，用进基变量x2替换s2，应用高斯-乔丹行运算，有：1. 新的枢轴行x2行=当前s2行4/3；2. 新的Z行=当前Z行-(-2/3)新的x2行；3. 新的x1行=当前x1行-

17、(2/3)新的x2行；4. 新的s3行=当前s3行-(5/3)新的x2行；5. 新的s4行=当前s4行-(1)新的x2行；23这些计算产生新的单纯形表为基Zx1x2s1s2s3s4解Z1003/41/20021x10101/4-1/2003x2001-1/83/4003/2s30003/8-5/4105/2s40001/8-3/4011/2基于最优性条件，Z行中相应于非基变量s1和s2的系数没有一个是负的，因此最后的单纯形表是最优的决策变量最优值建议x13日生产 3 吨外墙涂料x23/2日生产 1.5 吨内墙涂料Z21利润2.1万美元24资源松弛变量的值状况原料M1s1=0匮乏原料M2s2=0

18、匮乏市场限制s3=5/2充裕需求限制s4=1/2充裕单纯形的计算结果还给出了资源的使用情况：如果松弛变量为零，表明资源全部用完，该资源是匮乏的如果松弛变量为正，表明资源尚有余存，该资源是充裕的25练习Max z=2x1+x2St 5x215 6x1+2x224 x1+ x25 x1，x2 0 结果：x1=7/2x2=3/2s1=15/2s2=0s3=0z=17/2263.3.3 单纯形方法的总结最优性条件最优性条件 在极大化（极小化）问题中，进基变量是Z行中具有最负（最正）系数的非基变量。如有多个可任选其一。当非基变量的所有Z行系数是非负的（非正的）时，迭代达到最优可行性条件可行性条件 对于极

19、大化（极小化）问题，离基变量都是具有最小非负比（带有严格的正分母）的基变量，如有多个可任选其一高斯高斯-乔丹行运算乔丹行运算 （1）枢轴行 a. 在基列中，用进基变量替换离基变量 b. 新的枢轴行=当前枢轴行枢轴元素 （2）包括 Z 的所有其他行 新行=当前行枢轴列系数新的枢轴行决定进基变量！决定离基变量！27单纯形方法总结第1步 确定初始基本可行解第2步 用最优性条件选择一个进基变量，如果没有进基变量，停止计算；上一个解就是最优的，否则转第3步。第3步 用可行性条件选择离基变量。第4步 用适当的高斯-乔丹行运算确定新的基本解。转到第2步283.4 人工初始解所有约束是（）并且有非负右端的线性

20、规划方便地提供了全部为松弛变量的初始基本可行解。Max & Min Z=5x1+4x2St 6x1+4x224 x1+2x26 -x1+x21 x2 2 x1, x2029Min z=4x1+x2s.t. 3x1+x2=3 4x1+3x26 x1+2x24 x1，x20Min z=4x1+x2s.t. 3x1+x2 =3 4x1+3x2-x3 =6 x1+2x2 + x4 =4 x1, x2 , x3, x4 0松弛变量剩余变量u 需要增加人工变量以扮演松弛变量的角色，然后在迭代中加以适当处理。带有（=）和（）的约束的线性规划求解该如何求解？303.4.1 大M方法 大M方法以等式形式

21、的线性规划开始。如果第 i 个约束没有松弛变量，则将人工变量 Ri 加入到初始解中，类似于所有松弛变量为基本解的情况。然后在目标函数中对他们指定非常大的惩罚，强迫人工变量在最优解中等于零。如果问题有可行解，该种情况总会发生。惩罚规则惩罚规则已知M为一个充分大的数，人工变量的目标系数表示为适当的惩罚，如果MM在极大化问题中人工变量的目标系数在极小化问题中31Min z=4x1+x2s.t. 3x1+x2=3 4x1+3x26 x1+2x24 x1，x20Min z=4x1+x2s.t. 3x1+x2 =3 4x1+3x2-x3 =6 x1+2x2 + x4 =4 x1, x2 , x3, x4

22、0松弛变量剩余变量Min z=4x1+x2+MR1+MR2s.t. 3x1+x2 +R1 =3 4x1+3x2-x3 + R2 =6 x1+2x2 + x4 =4 x1, x2 , x3, x4， R1， R2 0初始解(R1, R2, x4)=(3,6,4)32M可以不采用代数运算的传统，并用数值代替，以简化表达.M值应该多大？依赖于初始线性规划的数据：u M相对于初始目标系数必须充分大，使得M能起到惩罚作用，迫使人工变量在最优值为零。u 也不希望M太大，否则在计算机求解中，非常大的数与非常小的数值在一起运算时，可能产生严重的四舍五入。本例似乎取M=10033基x1x2x3R1R2x4解z-

23、4-10-100 -10000R13101003R243-10106x41200014在进行单纯形方法之前，需要将z 行与表的其余部分保持一致！在表中，x1=x2=x3=0，初始基本解(R1, R2, x4)=(3,6,4)，z=100*3+100*6=900（而不是z行右端当前显示的0！），这种不一致是由于R1, R2在目标函数中有非零系数（-100, -100）造成的！（在所有松弛变量为初始解中，Z行的松弛变量系数为0）34为此，在z行选用适当的约束方程替换出R1和R2，注意到橙色部分，用100乘以R1和R2行的每一行，求和之后加到z行，替换出R1和R2, 即基x1x2x3R1R2x4解z

24、-4-10-100-10000R13101003R243-10106x41200014基x1x2x3R1R2x4解z696399-100000900R13101003R243-10106x41200014X1为进基！最正系数！新的Z行=旧的z行+(100R1+100R2行)35基x1x2x3R1R2x4解z696399-100000900R13101003R243-10106x41200014基x1解最小比R1333/3=1（最小值）R2466/4=1.5x4144/1=4可行性条件，选择R1为离基变量！36基x1x2x3R1R2x4解z0167-100-23200204x111/301/30

25、01R205/3-1-4/3102x405/30-1/3013采用高斯-乔丹运算可以计算出如下最后的单纯形显示x2和R2分别是进基变量与离基变量。连续采用单纯形计算，再经过两步的迭代即可达到最优最优解为 x1=2/5 ，x2=9/5，z=17/5； R1=0，R2=0，x3=1，x4=0如果线性规划没有可行解，在最终的单纯形迭代中，使用惩罚项将不能迫使人工变量取值为零，此时至少有一个人工变量取正值。373.4.2 两阶段法大M方法中惩罚值的使用，可能会导致大的求解误差。两阶段法分两个阶段来求解线性规划：阶段一试图求一个初始基本可行解，找到一个解以后，调用阶段二求解原问题。38阶段 I 将问题变

26、成等式约束形式，并在约束中增加必要的人工变量（如大M方法一样），以保证找到一个初始基本解。接下来，求相应方程的基本解，无论线性规划是求极大化还是极小化，总是使得人工变量之和达到最小。如果其和的最小值为正，则线性规划问题无可行解（正的人工变量约束不满足）。否则进行阶段II。阶段II 使用阶段I得到的可行解作为原始问题的初始基本可行解。两阶段法的概况39Min z=4x1+x2s.t. 3x1+x2=3 4x1+3x26 x1+2x24 x1，x20Min r =R1+R2s.t. 3x1+x2+ R1 =3 4x1+3x2-x3 +R2 =6 x1+2x2 + x4 =4 x1, x2 , x3

27、, x4,R1,R2 0基x1x2x3R1R2x4解r000-1-100R13101003R243-10106x41200014阶段I40基x1x2x3R1R2x4解r74-10009R13101003R243-10106x41200014类似于大M方法中一样，在r行中的R1和R2用以下计算来替换： 新的 r 行=旧的r行+（1R1行+ 1R2行）利用上面的单纯形表格为基础，利用标准的单纯形方法，计算第一阶段的最优解。41基x1x2x3R1R2x4解r000-1-100 x1101/53/5-1/503/5x201-3/5-4/53/506/5x40011-111采用单纯形法迭代得到如下表格因

28、为最小值 r =0，阶段 I 产生了基本可行解x1=3/5，x2=6/5，x4=1。此时人工变量以完成了它的使命，从而我们能够从表中连同他们所在的列一起去掉，转入阶段 II42阶段IIMin z=4x1+x2s.t. x1+x3/5=3/5 x2-3x3/5=6/5 x3+x4=1 x1，x20基x1x2x3x4解r00000 x1101/503/5x201-3/506/5x400111基x1x2x3x4解z-4-1000 x1101/503/5x201-3/506/5x40011143基x1x2x3x4解z001/5018/5x1101/503/5x201-3/506/5x400111基变量

29、x1和x2在z行有非零的系数，使用下列计算将非零系数替换出去： 新的z行=旧的z行+（4 x1行+ 1x2行）最优解为 x1=2/5 ，x2=9/5，z=17/5； R1=0，R2=0，x3=1，x4=044基x1x2x3x4解z000-1/517/5x1100-1/52/5x20103/59/5x300111最优解为 x1=2/5 ，x2=9/5，z=17/5； x3=1，x4=0采用单纯形方法得到：45实际上几乎所有的商业软件包都采用两阶段法来求解线性规划。实际中，大M方法由于潜在的不利的舍入误差而可能从来不用的。介绍大M方法纯粹处于历史原因，其发展早于两阶段法。在最后一张表中人工变量及其

30、所在列被去掉，这只有在他们全部是非基变量时才会发生。如果在阶段I的最后一张表中有一个或者多个人工变量是基变量（取零值），则必须采取如下附加步，才能在阶段II开始前去掉人工变量。46第一步 选择一个零人工变量离开基本解，并指定它所在的行为枢轴行。进基变量可以是枢轴行具有系数非零的任意非基变量，完成相应的单纯法迭代。第二步 从表中去掉刚刚离基的人工变量的列。如果所有的人工变量已经被去掉转入阶段II，否则转回第一步。第一步的目的是保持基变量的可行性将不受影响，不论其枢轴元素是正还是负的总能使得零人工变量变为非基变量。47课后作业： P94，12题； P98，5（a）题、（d）题；1. P102，5题

31、.483.5 单纯形法的特殊情况本节考虑单纯形法中的4种情况：n 退化；n 可选择最优解；n 无界解；n 不存在（或者可行解）（1）介绍这些情况的理论解释（2）提供相应的实际解释493.5.1 退化在单纯形方法可行性条件中，最小比值可能循环出现，可以随意打破这种循环。当这样的情况发生时，至少有一个基变量在下一次迭代中为零，并称新的解退化。Max z=3x1+9x2St x1+9x28 x1+2x24 x1，x2050迭代基x1x2x3x4解0z-3-9000 x2进基x314108x3进基x4120141z-3/409/4018x2进基x21/411/402x3进基x41/20-1/2102z

32、003/23/218(最优值)x2011/2-1/22x110-120在迭代中，x3和x4均可以是离基变量，在迭代1构成退化，在基变量x4出现零值，再一次迭代后，达到最优值。51x1+9x28（多余约束）x1+2x24超定的到3条直线通过最优点，使得某些约束是多余的。目前尚没有有效的计算方法能直接从表中识别多余的约束。退化的含义1，注意迭代1和2，你将注意到目标值没有改进（Z=18）。单纯形方法有可能进入一个重复迭代的序列，永远不改进目标值，也永远不满足最优性条件。退化的含义2，两个迭代尽管对基变量和非基变量分类不一致，但对于所有的变量和目标值都产生同样的值。在迭代中（遇到退化的时候）是否可以

33、停止计算，答案否定，因为可能出现暂时退化。523.5.2 可选择最优解当目标函数平行于非冗余的紧约束目标函数平行于非冗余的紧约束（binding constraint）（即在最优解处作为方程而被满足的约束）解，目标函数可以在多于一个解点处相同的最优解，因此产生可选择最优解。Max z=2x1+4x2St x1+2x25 x1+x24 x1，x20 x1+x24x1+2x25z=2x1+4x2最优基本可行解BCBC上任意一点都表示了具有相同目标值Z=10的可选最优解53迭代基x1x2x3x4解0z-2-4000X2进基x312105X3离基x4110141(最优值)z002010X1进基x21/

34、211/205/2X4离基x41/20-1/213/22(可选最优解)z002010 x2011-11x110-123迭代1给出了最优解x1=0，x2=5/2和z=10，它与点B相一致。如何从这个表格中知道可选择最优解存在呢？看看迭代看看迭代1行方程非基变量的系数行方程非基变量的系数。非基变量x1的系数为零，表明x1可以进入基本解而不会改变Z值，但会引起变量值的改变。迭代2正是这个情况：x1进基，x4离基，新的解点x1=3,x2=1,z=1054单纯形方法仅能确定B点和C点，从数学角度来说，BC上的点(x1,x2)作为点B和C的非负的加权平均，因此B：x1=0，x2=5/2C：x1=3，x2=

35、1则线段BC上的所有的点如下12(0)(1)(3)33,0153( )(1)(1)122xx 当=0，为C点；当=0，为B点；否则为B到C之间55在实践中，可选择最优解是有用的，因为我们可以从许多解中选择而不会损害目标。例如在前例中，在B处显示只有第二项活动是正值；而在C处，两项活动都为正值。如果例子描述的是一种混合产品情形，生产两种产品比生产一种产品对于满足市场或许更加有优势，在这样的情况下C处解可能更加吸引人，也就是不要把所有的鸡蛋放在一个篮子里面。563.5.3 无界解在一些线性规划中，可以无限地增加变量的值但不破坏任何一个约束，这个就意味这解空间中至少又一个变量是无界的。其结果是，目标

36、值可以无限制的增加（max情形）或减少（min情形），此时解空间和最优目标都是无界的。出现无界点可能是由于模型构造不合理。此类模型中最大可能的缺陷是一个或多个非多余约束没有考虑在内，一些约束参数估计错误57Max z=2x1+x2St x1-2x210 2x1 40 x1，x20通过单纯形法迭代会发现，x2可以无限制的增加而不破坏任何约束，因为x2每增加一个单位，z将增加1；x2将增加至无穷，使得z无穷大，因此问题无有界解。无界解空间无界目标值z=2x1+x2x1-2x210无界变量的下方的系数将会产生（也就系数将会产生（也就是可行性条件比的分母）是零或者负的是可行性条件比的分母）是零或者负的

37、基x1x2x3x4解z-2-1000 x31-11010 x4200140583.5.4 不可行解n 具有不相容约束的线性规划模型没有可行解。假如所有的约束类型都是类型并具有非负的右端项，则这种情况将永远不会出行，因为松弛变量提供了一个可行解。n 对于混合类型的约束，仅当模型有可行空间时，人工变量在最优解处可以取零，否则至少有一个人工变量在最优迭代中取正。n 不可行解空间表明模型的构建有可能是不正确的。59Max z=3x1+2x2St 2x1+x22 3x1+ 4x212 x1，x20z=3x1+2x22x1+x223x1+ 4x212伪最优解迭代基x1x2x3x4R解0z-303-4021

38、0000-1200X2进基x3210105X3离基R1101141(伪最优)z50101004020-396x2210102R-50-1-414最优迭代1显示人工变量R取值为正，表明问题不可行，上图也展示了不可行解空间。由于允许人工变量为正，单纯形方法实际上已经将不等式的方向颠倒，从3x1+ 4x212变为3x1+ 4x212，这个结果为伪伪最优最优。M=100课后作业： P28，第5题； P33，第1题； P36，第2题； P45，第4题； P61，第10题；1. 以上作业请给出最终的计算结果。613.6 灵敏度分析在线性规划模型中，参数通常是不精确的，借助于灵敏度分析，我们能够探索这种不确

39、定性对最优解质量的影响。例如1. 某种产品估计的单位利润/成本发生变动，我们是否还能维持原先的产品组合构成及产量，以实现最优目标？2. 公司准备添置机器/雇员/原材料，应该以什么依据来决定优先顺序？n 线性规划中，模型参数（输入数据）能够在一定的限度内变化而不引起最优解的改变。这些内容涉及灵敏度的分析n 如果输入的数据中做特定的变化后如何得到新的最优解。623.6.1 图形灵敏度分析考虑两种情况： 最优解对于资源的可利用性（约束的右端项）变化的灵敏度分析；最优解对于单位利润或单位费用（目标函数系数）变化的灵敏度分析；maxmin0 z=stCXAX = bX或63例3.6-1 （右端项变化）J

40、OBCO公司在两台机器上生产两种产品。1个单位的产品1需要2小时机器1和1小时机器2；对于产品2，一个单位产品需要1小时机器1和3小时机器2.每个单位产品1和产品2的收益分别是30美元和20美元。每台机器的日加工时间是8小时。令x1和x2分别表示产品1和产品2的日产量，则线性规划模型给出如下：Max z=30 x1+20 x2St 2x1+ x28（机器1） x1 +3x2 8（机器2） x1，x20maxmin0 z=stCXAX = bX或64如果日工作能力从8小时增加到9小时，则生产能力增加的收益率是多少？2x1+ x292x1+ x28x1 +3x2 8X1=3.2，x2=1.6，z=

41、128X1=3.8，x2=1.4，z=142Gc11ZZ142 12814.0(/)98CG机器 增加 小时工作能力产生美元 小时工作能力收益的变化率的改变（ 点变化到 ）CD计算出的变化率提供了模型的输入（资源）和它的输入（总收益）的直接联系，表示成为资源的单位价值：即可用资源的单位变化引起目标函数的变化。这意味着机器1的能力增加（或者减少）1个单位，将增加（或减少）收益14美元。65尽管目标函数变化率的恰当说法是资源的单位价值，然而在技术上的名称是对偶价格（dual price）或者影子价格（shadow price）。2x1+ x292x1+ x28x1 +3x2 8X1=3.2，x2=

42、1.6，z=128X1=3.8，x2=1.4，z=142CGBF当机器1工作能力变化（增加或者减少），即其约束平移到线段BF的任意一点，每小时14美元的对偶价格仍然有效。给定对偶价格的适用范围：机器1工作能力最小值B点=（0，2.67）=20+12.67=2.67小时机器1工作能力最大值F点=（8，0）=28+10=16小时在2.67机器1的工作能力16小时时，对偶价格14美元/小时将保持不变DE66类似方法可以验证，机器2工作能力的对偶价格是每小时2美元，它在如下区域内变化时保持不变，即约束平行移动到线段DE的任意一点时，将产生下面的限制区域：机器2工作能力最小值D点=(0，4)=14+30

43、=4小时机器2工作能力最大值E点=(0，8)=28+38=24小时对于机器2，在如下区域对偶价格2美元/小时将保持不变4机器 2 的工作能力24小时机器1和机器2计算出的限制称为可行性区域（feasibility range）67关于线性规划问题, 对偶价格能够作出相应的经济决策, 比如：问题1 如果JOBCO能够增加两种机器的能力，哪种机器应该有更高的优先权？机器1和机器2的对偶价格分别为14和2美元/小时，这时优先权应该是机器1问题2 一项建议提出，要以10美元/小时的额外费用增加机器1和机器2的能力，这项建议可取吗？对于机器1，每小时附加净收入为14-10=4美元；而对于机器2净收入为2

44、-10=-8美元，因此只应该增加机器1.68问题3 如果机器1的工作能力从现在的8小时增加到13小时，这个增加将如何影响最优收益？对于机器1的对偶价格是14美元，在2.67，16小时的区域内使用，所提出的增加到13小时落在可行域内，因此收入增加量是14(13-8)=70美元，这意味着总收入将增加到（当前收益+收益变化）=128+70=198美元。问题4 假定机器1的工作能力可以增加到20小时，这个增加将如何影响最优收益？所提出的改变超出2.67，16小时这个保持14美元的对偶价格区域，因此我们只能增加到16小时，超出部分需要进一步计算才能得到答案。落在可行域之外不意味着问题无解，只是我们没有充

45、分信息立刻作出决策。69问题5 只要资源的改变在可行域内，最优目标值的改变就等于（对偶价格资源的改变），相应变量的最优值是多少？变量的最优值一定发生改变，然而从图解得到的信息水平并不能充分确定新值。703.6.2 代数灵敏度分析右端项的变化TOYCO通过3种操作装配3种玩具玩具火车、卡车和汽车。这个3种操作可用时间限制分别为430、460和420分钟。这3个产品的单位收入分别为3、2和5美元。每辆火车在3种操作中的装配时间分别是1、3和1分钟，玩具卡车和汽车的时间分别是(2,0,4)和(1,2,0).令x1，x2，x3分别为每天装配玩具火车、卡车和汽车的单位数量，则规划模型如下：Max z=3

46、x1+2x2+5x3St x1+2x2+x3430（操作1） 3x1 +2x3 460（操作2） x1+4x2 420（操作3） x1，x2 ，x3 071基x1x2x3x4x5x6解z4001201350 x2-1/4101/2-1/40100 x33/20101/20230 x6200-21120这个结果表明生产玩具卡车100，汽车230，但不生产玩具火车，收入为1350美元。72对偶价格的确定在增加松弛变量x4，x5，x6后，模型的约束可以写为：x1+2x2+x3+x4=430(操作1)3x1 +2x3+x5 =460 (操作2)x1+4x2 +x6=420 (操作3)x1+2x2+x3

47、=430-x4 (操作1)3x1 +2x3 =460 -x5 (操作2)x1+4x2 = 420-x6 (操作3)或者借助于上式，我们可以是说，松弛变量上减少1分钟就等价于操作时间上增加1分钟。73可以用上述信息从最优表的Z的方程中确定对偶价格：Z+4x1+x4+2x5+0 x6=1350可以写成Z=1350-4x1+x4+2x5+0 x6 =1350-4x1+1(-x4) +2(-x5)+0(-x6)已知松弛变量值的减少等价于在它的操作时间上的增加，因此Z=1350-4x1+1增加操作1的时间 + 2增加操作2的时间 + 0增加操作3的时间74这个方程显示了：（1）在操作1上时间增加1分钟z

48、将增加1美元；（2）在操作2上时间增加1分钟z将增加2美元；（3）在操作2上时间增加1分钟z将保持不变；概括最优表的z行如下：基x1x2x3x4x5x6解z4001201350Z行直接产生的对偶价格如下表：资源松弛变量松弛变量的最优z方程系数对偶价格（美元/分钟）操作1x411操作2x522操作3x60075操作3的零对偶价格意味着，分配给这个操作更多的生产时间没有经济效益。这个结果有意义，因为资源已经参与了，证据就是，在最优解中与操作3相对应的松弛变量是正值(=20)（即资源过多）. 至于操作1和2每一个松弛变量，增加1分钟将分别提高1美元和2美元。对偶价格还表明，当分配额外资源时，操作2将

49、得到更高的优先权，因为它的对偶价格是操作1的2倍。上述计算说明对偶价格是如何从最优表的约束中确定的。对于约束，该方法仍然适用。但是对偶价格将于对应的约束符号相反。等式约束则还需要“相关的”计算。76可行性区域的确定令D1, D2, D3分别是分配给操作1、2和3的每天生产时间的该变量（正的或者负的），模型可写为Max z=3x1+2x2+5x3St x1+2x2+x3430+ D1 （操作1） 3x1 +2x3 460 + D2 （操作2） x1+4x2 420 + D3 （操作3） x1，x2 ，x3 0我们将考虑同时发生改变的一般情况，每次只改变一个变量的特殊情况将从这些结果中得到。77具

50、体方法是：用所修正的右端项从新计算最优单纯形表，然后获得保持解可行的条件，即最优表的右端项保持非负。为了说明右端项如何重新保持计算，我们以修正解列开始，即在初始单纯形表中使用新的右端项：430+D1、460+D2、420+D3，因此基x1x2x3x4x5x6解右端项D1D2D3z-3-2-50000000 x2121100430100 x3302010460010 x614000142000178基x1x2x3x4x5x6解右端项D1D2D3z4001201350120 x2-1/4101/2-1/401001/2-1/40 x33/20101/2023001/20 x6200-21120-2

51、11在D1，D2，D3下的列与初始基本列x4，x5，x6下的那些列是相同的。这意味着当我们像在初始模型那样完成相同的单纯形迭代是，两组中的列也一定是完全相同。实际上新的最优解变成79新的最优表提供了如下的最优解：1221232612313502111002412302202zDDxDDxDxDDD只要所有变量非负，则当前解保持可行，这就导出可行性条件可行性条件212326123111000241230022020 xDDxDxDDD任意同步改变D1、D2、D3，只要满足这些不等式，都将保持解可行。如果所有的条件满足，则可在上述等式约束中直接替换D1、D2、D3，来找到新的最优解。80假设对于操

52、作1、2、3的可利用生产时间分别是480、440和410分钟，则D1=480-430=50，D2=440-460=-20，D3=410-420=-10，在可行性条件中替换，得到23611100(50)( 20)1300241230( 20)22002202(50)( 20)( 10)1100 xxx （可行）（可行）（不可行）81计算表明x60，因此当前解并没有保持可行。需要额外的计算才能得到新的解（本课不介绍）。如果资源的变化使得D1=-30，D2=-12，D3=10，则23611100( 30)( 12)880241230( 12)22402202( 30)( 12)(10)780 xxx

53、 （可行）（可行）（可行）新的可行解是x2=88，x3=224，x6=78，且 z=3(0)+2(88)+5(224)=1296美元，或z=1350+1(-30)+2(-12)=1296美元。82给出的条件可以专门用于产生各自的可行性区域，这就是一次只改变一种资源的变化结果。情况1 把操作1的时间从460分钟改变到(460+D1)分钟，这一变化等价于在同步条件中置D2=D3=0，得到21131611110002002230020010202010 xDDxDxDD 以上考虑的是同时发生改变的一般情况，而每次只改变一个变量的特殊情况将从一般结果中得到。83情况2 把操作2的时间从430分钟改变到

54、(430+D2)分钟，这一变化等价于在同步条件中置D1=D3=0，得到22232226121100040041230040020400220020 xDDxDDDxDD 情况3 把操作3的时间从430分钟改变到(430+D3)分钟，这一变化等价于在同步条件中置D1=D2=0，得到232631000230020200 xxDxD 84对TOYCO模型，总结对偶价格和可行性区域如下资源对偶价格可行性区域资源数量（分钟）最小值当前值最大值操作11-200D110230430440操作22-20D2400440440860操作30-20D3400420注意：对偶价格有效的同步可行性条件，不一定要求满足

55、所有单个可行性区域。2361000.5( 30)0.25( 12)11802300.5( 12)2240202(30)( 12)(100)480 xxx （可行）（可行）（可行）例如D1=30，D2=-12，D3=100，则85这意味着对偶价格仍然可适用，因此能够从对偶价格中计算出新的最优目标值z=1350+1(30)+2(-12)+0(100)=1356美元（1）如果约束右端项的该变量Di，i=1,2,3,m，在同步改变时满足所有可行性条件，或相应的Di在单个发生改变时仍然落在可行性区域内，则对偶价格有效。（2）如果同步的可行性条件不满足，或因为单个的可行性区域被破坏，对偶价格就不再有效。此

56、时，可以用新的Di 值重新解该问题，或者用后续方法来解决。86课后作业P123，第6题P125，第11题87例（目标系数的变化）2x1+ x28x1 +3x2 8X1=3.2，x2=1.6，z=128CGBFDE z=30 x1+20 x2C点为最优解点。收入单位数的变化（目标函数系数）将改变z的斜率。然而从右图可以看到，只要目标函数位于直线BF和DE之间，最优点将保持在C，这2个约束确定了最优点，这意味着存在一个关于目标函数系数的区域，在这个区域内最优解在C点将保持不变。maxmin0 z=stCXAX = bX或3.6.3 图形灵敏度分析目标函数88可以写出目标函数的一般形式：Max z=

57、c1x1+c2x2可以想象，直线z在C处转动，并且它能够沿着顺时针和逆时针转动，最优解始终保持在点C，只要z=c1x1+c2x2介于直线2x1+ x2=8，x1 +3x2 =8之间。这意味着比值c1/c2可以在1/3与2/1之间变化，这产生如下条件：121231cc这个信息能够直接提供有关最优解的答案。例如89问题1 假设产品1和产品2的单位收入分别改变到35美元和25美元，当前的最优解保持不变吗？新的目标函数为 Max z=35x1+25x2。解在C处保持最优，因为c1/c2=35/25=1.4，保持在最优区域1/3, 2之间。尽管变量在最优点C的保持不变，z的最优值变到35(3.2)+25

58、 (1.6)=152美元。当比值落在这个区域之外，需要增加额外的计算来求出新的最优解。90问题2 假设产品2的单位收入固定在当前值c2=20美元上，相应于c1，即产品1的单位收入保持最优值不变的区域是什么？在条件 中替换c2=20，得到121231cc1/320c1220，即6.67c140这个区域称为c1的最优区域，并隐含的假设c2固定在20美元。尽管这一节仅处理了二维变量问题，但是这些结果奠定了对一般线性规划进行灵敏度分析的基础！913.6.3 代数灵敏度分析目标函数本节从之前的图形法处理的保持线性规划最优解的条件，拓展到多维的代数方法。简约费用简约费用在TOYCO模型中，在最优表中目标Z

59、行系数是基x1x2x3x4x5x6解z4001201350因此z行方程是 z+4x1+x4+2x5=1350即 z=1350-4x1-x4-2x5 最优解建议不生产玩具火车（X1=0）。该建议由z行方程的信息得到证实，因为x1在当前零值情况下，每增加一个单位将降低4美元，即Z=1350-4(1)-1(0)-2(0)=1346美元。92可以把Z行方程中x1的系数(=4)作为费用的单位，因为它引起z的减少。但是这个“费用”来自哪里？在原来的模型中，x1的单位收入是3美元。我们还知道，每个玩具火车消耗资源（操作时间），它本身也导致费用。因此，从优化的观点来看，x1的”吸引力”依赖于单位收入与一个单位

60、资源消耗的费用的相对值。这个关系在线性规划文献中被公式化，定义简约费用如下： 应该尽量降低单位简约费用，即提高利润率，以提高运营系统的效益！单位利润=单位收入-单位消耗资源费用（成本）单位简约费用=单位消耗资源费用（成本）-单位收入93如何理解这个定义的含义？在TOYCO模型中，玩具卡车的单位收入(=2美元)少于玩具火车的单位收入(=3美元). 然而，最优解选择生产玩具卡车却不生产玩具火车(x1=0).原因在于用于玩具卡车资源（即操作时间）的单位成本小于售单位成本小于售价价。 而对于玩具火车，成本大于它的售价成本大于它的售价。 借助于简约费用的定义，现在可以看到无利益的变量（如x1）用下面两种方法使它成为有