运筹学导论第八版3单纯形法与敏感性分析

1第3章单纯形方法&灵敏度分析23.1等式形式的线性规划模型为了方便单纯形法的计算，对模型的约束有如下两个要求：(1)所有的约束都是等式(变量的非负限制除外)，并且具有非负的右端项；(2)所有变量是非负的。这两项要求目的在于使得单纯形方法标准化和简单化。这也就是现在的所有商业软件都直接运行不等式约束、非负的右端项和无限制变量。在进行单纯形法求解前，模型的任何必要处理都在软件内部完成。33.1.1将不等式转化为带有非负右端项的等式约束在(≤)约束中，右端项可被视为资源可利用性限制的描述，在这种情况下，左端项表示模型的活动(变量)对这些有限资源的用量。因此，(≤)约束的右端项与左端项之间的差构成未用的或松弛的资源量。为了把(≤)不等式约束转为等式约束，在约束左端增加非负的松弛变量(SlackVariable).例如在ReddyMikks模型中，相当于原料M1的约束给出如下：6x1+4x2≤24定义s1作为M1的松弛的或未用的量，约束可以转化为如下等式约束：6x1+4x2+s1=24,s1≥04在(≥)约束设置了模型的活动(变量)对的下限。因此，可以将(≥)约束的左端项超出最下限制的量表示为剩余。为了把(≤)不等式约束转为等式约束，在约束左端减去非负的剩余变量(SurplusVariable).例如在营养配方模型（例2.2-2）中，表示最小饲料需求的约束是：x1+x2≥800定义S1作为剩余变量，约束可以转化为如下等式约束：x1+x2-S1≥800,S1≥05对于让等式约束的右端项是非负的，这个条件总是可以满足的，必要时可以在得到的方程两端乘以(-1).例如，约束-x1+x2≤-3则等价方程为-x1+x2+s1=-3，s1≥0对上式两边乘以(-1),转化为非负的右端项，便得到我们需要的约束等式，即x1-x2-s1=-363.1.2无限制变量处理方法在单纯形方法中，要求所有的决策变量是非负的。然而很多现实问题中往往很多的决策变量恰恰是不要求非负的。例如例2.3-6中介绍的多周期生产平滑模型，其中要求每个周期在开始时要根据周期需求上下调整。如果xi是周期i的劳动力数量，则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来实现。2y2y2250yy和2204yy和那么和能否同时取正值？这种情况是不会发生的，否则这意味着相同的时间内既雇佣工人又解雇工人。通过数学的证明也发现，在任意的单纯形中，这两个值同时取正值是不可能的。2y2y83.2从图形解到代数解的转换在2.2节介绍的二元决策变量的线性规划模型的图形求解思想奠定了代数单纯形法发展的基础。在图解方法中，解空间由表示约束的半空间描述，而在单纯形法中，解空间由m个同时成立的线性方程和n个非负变量表示。画出所有约束，包括非负限制解空间由无穷个可行点组成识别解空间的可行角点最优解的候选点为有限个角点用目标函数从所有的候选点确定最优角点解空间由n个变量的每个方程表示，所有变量均为非负方程组有无穷个可行解确定方程的基本可行解最优解由有限个基本可行解给出在所有候选解中，用目标函数确定最优的基本可行解图解法代数法9根据图形，容易解空间有无穷个解点的原因，那么如何能从解空间的代数表示中得出类似的结论？在代数表示上，方程的个数m小于决策变量个数n。如果m=n，方程是相容的，则方程组只有唯一解；如果mn，假定方程组是相容的，则方程组有无穷多的解。在代数中如何定义角点：在m×n(mn)阶方程组中，如果令(n-m)个变量等于0，然后求解其余的含m个变量的m个方程，如果有唯一解，则称相应的解为基本解，它一定对应解空间的一个(可行或不可行)角点，这意味着角点的最大数目为!!()!mnnCmnm1012121212max232425,0zxxstxxxxxx方程组有m=2个方程和n=4个变量。因此最大数目的角点为4!/(2!2!)6mnC到底令哪些点为零才能对应一个特定的角点？21122121212425,,,0xxsxxsxxss解空间(x1，x2，s1，s2)最优点(1,2,0,0)2x1xABCDEF10s20s(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，必须求解184756个10×10阶的方程。而在很多实际的问题中，很多是有成百上千的变量和约束的问题。2x1xABCDEF10s最优点（x1=1，x2=2）20s2x1xABCDEF10s最优点（x1=1，x2=2）20s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，他是最优点。因此单纯形方法的路径是沿着A→B→C。沿着路径的每个角点与一步迭代是对应的，单纯形方法是沿着解空间的边缘移动，不能抄近路，直接A→C132x1xABCDEF10s最优点(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）可以看到，在基变量和非基变量中的变化模式随着解沿着路径A→B→C的移动而改变。A→B，在A处的非基变量x2变成B处的基变量，并且在A处的基变量s2变成在A处的非基变量，称X2为进基变量，s2为离基变量，类似地，在点B，x1进基，s1离基，因此到了C点15ReddyMikks模型是MaxZ=5x1+4x2St6x1+4x2≤24（原料M1）x1+2x2≤6（原料M1）-x1+x2≤1（市场限制）x2≤2（需求限制）x1,x2≥012123412112212324121234max54000064242612,,,,,0zxxssssstxxsxxsxxsxsxxssss12540zxx163.3.2单纯形算法的计算细节基Zx1x2s1s2s3s4解Z1-5-400000Z行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解比值（或截距）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,,,,,0zxxaxxsbxxscxxsdxsxxssssabcd-1461234561235s4=01/-1=-124/6=46/1=6ABC在点B处的非基（零）变量：（s1,x2）在点B处的基变量：（x1,s2,s3,s4）19进基变量和离基变量如何“交换”？进基↓基Zx1x2s1s2s3s4解Z1-5-400000离基←s1064100024枢轴行s201201006s30-1100101s400100012枢轴行一些概念20基于高斯-乔丹行操作来计算新的基本解1.枢轴行a.在基列中，以进基变量替换离基变量b.新的枢轴行=当前枢轴行÷枢轴元素2.其他所有行，包括Z行新的行=当前行-当前枢轴列的系数×新的枢轴列将该方法应用到上表1.在基列中，以x1替换s1新的x1行=当前s1行÷6=(064100024)/6=(012/31/60004)2.新的Z行=当前Z行-(-5)×新的x1行=(1-5-400000)-(-5)×(012/31/60004)=(10-2/35/600020)3.新的s2行=当前s2行-(1)×新的x1行=(01201006)-(1)×(012/31/60004)=(004/3-1/61002)4.新的s3行=当前s3行-(-1)×新的x1行=(0-1100101)-(-1)×(012/31/60004)=(005/31/60105)5.新的s4行=当前s4行-(0)×新的x1行=(00100012)-(0)×(012/31/60004)=(00100012)21新的基本解是（x1,s2,s3,s4），因此新的单纯形表为进基↓基Zx1x2s1s2s3s4解Z10-2/35/600020s1012/31/60104离基←s2004/3-1/61002s3005/31/60105s400100012新的基本解是（x1,s2,s3,s4）=(4252)，而Z=20与下面的公式计算结果一致新的Z=原来的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/3×1.5=1,它产生新的Z=20+1=21在基列中，用进基变量x2替换s2，应用高斯-乔丹行运算，有：1.新的枢轴行x2行=当前s2行÷4/3；2.新的Z行=当前Z行-(-2/3)×新的x2行；3.新的x1行=当前x1行-(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/