《运筹学导论之单纯形法与敏感性分析》由会员分享，可在线阅读，更多相关《运筹学导论之单纯形法与敏感性分析（106页珍藏版）》请在金锄头文库上搜索。
1、1,第3章 单纯形方法&灵敏度分析,2,3.1 等式形式的线性规划模型,为了方便单纯形法的计算，对模型的约束有如下两个要求： (1) 所有的约束都是等式(变量的非负限制除外)，并且具有非负的右端项； 所有变量是非负的。,这两项要求目的在于使得单纯形方法标准化和简单化。这也就是现在的所有商业软件都直接运行不等式约束、非负的右端项和无限制变量。在进行单纯形法求解前，模型的任何必要处理都在软件内部完成。,3,3.1.1 将不等式转化为带有非负右端项的等式约束,在()约束中，右端项可被视为资源可利用性限制的描述，在这种情况下，左端项表示模型的活动(变量)对这些有限资源的用量。因此， ()约束的右端项与
2、左端项之间的差构成未用的或松弛的资源量。 为了把()不等式约束转为等式约束，在约束左端增加非负的松弛变量(Slack Variable). 例如在Reddy Mikks模型中，相当于原料M1的约束给出如下： 6x1+4x224 定义s1作为M1的松弛的或未用的量，约束可以转化为如下等式约束： 6x1+4x2+s1=24, s10,4,在()约束设置了模型的活动(变量)对的下限。因此， 可以将()约束的左端项超出最下限制的量表示为剩余。 为了把()不等式约束转为等式约束，在约束左端减去非负的剩余变量(Surplus Variable). 例如在营养配方模型（例2.2-2）中，表示最小饲料需求的约
3、束是： x1+x2800 定义S1作为剩余变量，约束可以转化为如下等式约束： x1+x2-S1800, S10,5,对于让等式约束的右端项是非负的，这个条件总是可以满足的，必要时可以在得到的方程两端乘以(-1). 例如，约束 -x1+x2-3 则等价方程为 -x1+x2+s1=-3，s10 对上式两边乘以(-1), 转化为非负的右端项，便得到我们需要的约束等式，即 x1-x2-s1=-3,6,3.1.2 无限制变量处理方法,在单纯形方法中，要求所有的决策变量是非负的。然而很多现实问题中往往很多的决策变量恰恰是不要求非负的。例如例2.3-6中介绍的多周期生产平滑模型，其中要求每个周期在开始时要根
4、据周期需求上下调整。如果xi是周期 i 的劳动力数量，则xi+1是周期 i+1的劳动力数量，可以表示为 xi+1= xi+ yi+1 变量yi+1必须无符号限制，它运行xi+1相对于xi增加或减少，即雇佣或解雇工人。 可以采用如下替换方法来满足这个要求,这样的替换原理是什么？,7,假定在周期1中，劳动力是x1=20名工人，在周期2中，劳动力将增加5名，达到25名。依据变量 和变量 ，这等价于 ，或者y2=5-0=5. 类似地，如果在周期2中劳动力减少到16名，则我们有 或者y2=0-4=-4. 替换还运行劳动力不作改变的可能性，此时两个变量均为0来实现。,那么 和 能否同时取正值？ 这种情况是
5、不会发生的，否则这意味着相同的时间内既雇佣工人又解雇工人。通过数学的证明也发现，在任意的单纯形中，这两个值同时取正值是不可能的。,8,3.2 从图形解到代数解的转换,在2.2节介绍的二元决策变量的线性规划模型的图形求解思想奠定了代数单纯形法发展的基础。 在图解方法中，解空间由表示约束的半空间描述，而在单纯形法中，解空间由m个同时成立的线性方程和n个非负变量表示。,9,根据图形，容易解空间有无穷个解点的原因，那么如何能从解空间的代数表示中得出类似的结论？ 在代数表示上，方程的个数m小于决策变量个数n 。如果m=n，方程是相容的，则方程组只有唯一解；如果mn，假定方程组是相容的，则方程组有无穷多的
6、解。 在代数中如何定义角点： 在mn (mn)阶方程组中，如果令(n-m)个变量等于0，然后求解其余的含m个变量的m个方程，如果有唯一解，则称相应的解为基本解，它一定对应解空间的一个(可行或不可行)角点，这意味着角点的最大数目为,10,方程组有m=2个方程和n=4个变量。因此最大数目的角点为,到底令哪些点为零才能对应一个特定的角点？,最优点(1,2,0,0),11,可以看到，当问题的大小增加后（即m与n变大），枚举所有角点的过程包含巨量的计算，如m=10和n=20，必须求解184756个1010阶的方程。而在很多实际的问题中，很多是有成百上千的变量和约束的问题。,12,3.2 单纯形方法,3.
7、3.1 单纯形方法的迭代本质,A,B,C,D,E,F,最优点（x1=1，x2=2）,正常情况下，单纯形从原点（A点）开始，此时Z=0，能否在当前零值的基础上，通过增加非基变量x1和x2来增加Z值？,图形显示，增加x1和x2将增加Z。单纯形方法每次要求增加一个变量，且选择使得Z有最大改善率的那个变量。因此选择增加x2具有最大改善率，因此增加x2直到角点B，在点B，再增加x1的值，达到改进的角点C，他是最优点。因此单纯形方法的路径是沿着ABC。,沿着路径的每个角点与一步迭代是对应的，单纯形方法是沿着解空间的边缘移动，不能抄近路，直接AC,13,A,B,C,D,E,F,最优点(1,2,0,0),(0
8、，2.5，1.5，0),(2，0，0，3),(0，0，4，5),单纯形方法的本质就是换基！,14,可以看到，在基变量和非基变量中的变化模式随着解沿着路径ABC的移动而改变。 AB，在A处的非基变量x2变成B处的基变量，并且在A处的基变量s2变成在A处的非基变量，称X2为进基变量，s2为离基变量，类似地，在点B，x1进基，s1离基，因此到了C点,15,Reddy Mikks模型是 Max Z=5x1+4x2 St 6x1+4x224 （原料M1） x1+2x26 （原料M1） -x1+x21 （市场限制） x2 2 （需求限制） x1, x20,16,3.3.2 单纯形算法的计算细节,初始解是最
9、优解吗？,目标函数表明可以增加x1或x2来改进这个解，选择具有最正的系数的变量x1为进基变量，这个等价于将目标函数中最负系数的变量作为进基变量。最优性条件，该条件确定进基变量,单纯形迭代开始于原点（x2, x2）=(0, 0)，因此, 在初始点处的非基（零）变量：（x1, x2），在初始点处的基变量： （s1, s2, s3, s4） 即 Z=0， s1=24, s2=6, s3=1, s4=2,17,从单纯形表中确定离基变量的方法是，计算方程的右端项（解列）与相应的在进基变量x1下方的约束系数的非负比可行性规则,最小非负比自动识别当前基变量s1作为离基变量，并指定进基变量x1的新值为4,18
10、,在点B处的非基（零）变量： （s1, x2） 在点B处的基变量： （x1, s2, s3, s4）,19,进基变量和离基变量如何“交换”？,一些概念,20,基于高斯-乔丹行操作来计算新的基本解,1. 枢轴行 a. 在基列中，以进基变量替换离基变量 b. 新的枢轴行=当前枢轴行枢轴元素 2. 其他所有行，包括Z行 新的行=当前行-当前枢轴列的系数新的枢轴列,将该方法应用到上表,在基列中，以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)-(
11、-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 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
12、0 0 0 1 2),21,新的基本解是（x1, s2, s3, s4），因此新的单纯形表为,新的基本解是（x1, s2, s3, s4）=(4 2 5 2)，而Z=20与下面的公式计算结果一致,新的Z=原来的Z + 新的x1的值 它的目标系数=0+4 5=20,22,在前表中，最优性条件表明，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)
13、新的x2行； 3. 新的x1行=当前x1行-(2/3)新的x2行； 4. 新的s3行=当前s3行-(5/3)新的x2行； 5. 新的s4行=当前s4行-(1)新的x2行；,23,这些计算产生新的单纯形表为,基于最优性条件，Z行中相应于非基变量s1和s2的系数没有一个是负的，因此最后的单纯形表是最优的,24,单纯形的计算结果还给出了资源的使用情况： 如果松弛变量为零，表明资源全部用完，该资源是匮乏的 如果松弛变量为正，表明资源尚有余存，该资源是充裕的,25,练习 Max z=2x1+x2 St 5x215 6x1+2x224 x1+ x25 x1，x2 0,结果： x1=7/2 x2=3/2 s
14、1=15/2 s2=0 s3=0 z=17/2,26,3.3.3 单纯形方法的总结,最优性条件 在极大化（极小化）问题中，进基变量是Z行中具有最负（最正）系数的非基变量。如有多个可任选其一。当非基变量的所有Z行系数是非负的（非正的）时，迭代达到最优,可行性条件 对于极大化（极小化）问题，离基变量都是具有最小非负比（带有严格的正分母）的基变量，如有多个可任选其一,高斯-乔丹行运算 （1）枢轴行 a. 在基列中，用进基变量替换离基变量 b. 新的枢轴行=当前枢轴行枢轴元素 （2）包括 Z 的所有其他行 新行=当前行枢轴列系数新的枢轴行,决定进基变量！,决定离基变量！,27,单纯形方法总结,第1步
15、确定初始基本可行解 第2步 用最优性条件选择一个进基变量，如果没有进基变量，停止计算；上一个解就是最优的，否则转第3步。 第3步 用可行性条件选择离基变量。 第4步 用适当的高斯-乔丹行运算确定新的基本解。转到第2步,28,3.4 人工初始解,所有约束是（）并且有非负右端的线性规划方便地提供了全部为松弛变量的初始基本可行解。,Max & Min Z=5x1+4x2 St 6x1+4x224 x1+2x26 -x1+x21 x2 2 x1, x20,29,Min z=4x1+x2 s.t. 3x1+x2=3 4x1+3x26 x1+2x24 x1，x20,Min z=4x1+x2 s.t. 3x
16、1+x2 =3 4x1+3x2-x3 =6 x1+2x2 + x4 =4 x1, x2 , x3, x4 0,需要增加人工变量以扮演松弛变量的角色，然后在迭代中加以适当处理。,带有（=）和（）的约束的线性规划求解该如何求解？,30,3.4.1 大M方法,大M方法以等式形式的线性规划开始。如果第 i 个约束没有松弛变量，则将人工变量 Ri 加入到初始解中，类似于所有松弛变量为基本解的情况。然后在目标函数中对他们指定非常大的惩罚，强迫人工变量在最优解中等于零。如果问题有可行解，该种情况总会发生。,惩罚规则,已知M为一个充分大的数，人工变量的目标系数表示为适当的惩罚，如果,31,Min z=4x1+x2 s.t. 3x1+
