运筹学导论之单纯形法与敏感性分析.ppt

《运筹学导论之单纯形法与敏感性分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

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

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

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

4、+1的劳动力数量，可以表示为xi+1=xi+yi+1变量yi+1必须无符号限制，它运行xi+1相对于xi增加或减少，即雇佣或解雇工人。可以采用如下替换方法来满足这个要求这样的替换原理是什么？6假定在周期1中，劳动力是x1=20名工人，在周期2中，劳动力将增加5名，达到25名。依据变量和变量，这等价于，或者y2=5-0=5.类似地，如果在周期2中劳动力减少到16名，则我们有或者y2=0-4=-4.替换还运行劳动力不作改变的可能性，此时两个变量均为0来实现。那么和能否同时取正值？这种情况是不会发生的，否则这意味着相同的时间内既雇佣工人又解雇工人。通过数学的证明也发现，在任意的单纯形中，这两个值同时

5、取正值是不可能的。73.2从图形解到代数解的转换在2.2节介绍的二元决策变量的线性规划模型的图形求解思想奠定了代数单纯形法发展的基础。在图解方法中，解空间由表示约束的半空间描述，而在单纯形法中，解空间由m个同时成立的线性方程和n个非负变量表示。8根据图形，容易解空间有无穷个解点的原因，那么如何能从解空间的代数表示中得出类似的结论？在代数表示上，方程的个数m小于决策变量个数n。如果m=n，方程是相容的，则方程组只有唯一解；如果m

6、有唯一解，则称相应的解为基本解，它一定对应解空间的一个(可行或不可行)角点，这意味着角点的最大数目为9方程组有m=2个方程和n=4个变量。因此最大数目的角点为到底令哪些点为零才能对应一个特定的角点？解空间(x1，x2，s1，s2)最优点(1,2,0,0)ABCDEF(0，0，4，5)(0，2.5，1.5，0)(2，0，0，3)(5，0，-6，0)(0，4，0，-3)10非基（零）变量基变量基本解相应的角点可行否？目标值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）(

7、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阶的方程。而在很多实际的问题中，很多是有成百上千的变量和约束的问题。113.2单纯形方法3.3.1单纯形方法的迭代本质ABCDEF最优点（x1=1，x2