运筹学讲义-单纯形方法1

《运筹学讲义-单纯形方法1》由会员分享，可在线阅读，更多相关《运筹学讲义-单纯形方法1（78页珍藏版）》请在金锄头文库上搜索。

1、2019/8/18,1,运筹学,耿修林,2019/8/18,2,五 、 单纯形方法,（一）单纯形方法的初步讨论 1、单纯形方法的基本思想 从可行域中的一个基本可行解出发，判断它是否已是最优解，若不是，寻找下一个基本可行解，并使目标函数得到改进，如此迭代下去，直到找出最优解或判定问题无界为止。 从另一个角度说，就是从可行域的某一个极点出发，迭代到另一个极点，并使目标函数的值有所改善，直到找出有无最优解时为止。,2019/8/18,3,五 、 单纯形方法,（一）单纯形方法的初步讨论 2、单纯形方法：消去法 例求解线性规划模型 解：第一步，将线性规划模型标准化： Max Z=50x1+30x2+0x

2、3+0x4 st 4x1+3x2+x3 =120 2x1+x2+ +x4 =50 x1 , x2 , x3 , ,x40,2019/8/18,4,2、单纯形方法：消去法 第二步，寻找初始可行解。变量x3 、,x4对应的列 向量A3、A4 可作为初始可行基，那么X3、X4为基 变量，X1、X2为非基变量，用非基量表示基变量， 则有： Max Z=50x1+30x2+0x3+0x4 st x3 =120- 4x1-3x2 x4 =50 -2x1-x2 x1 , x2 , x3 , ,x40 令x1 、 x2 =0，得到基本可行解 X=（0，0，120，50）。,文本,文本,文本,文本,文本,文本,

3、文本,文本,2019/8/18,5,五、 单纯形方法,2、单纯形方法：消去法 第三步，判断目标函数是否达到了最优。 第四步，选取入基变量。确定x1 为 基变量， x2仍为非基变量。 第五步，选取出基变量。 x3 =120- 4x1-3x20 x4 =50 -2x1-x20 解不等式得：x125 ，只有当x1=25时， x4恰好等于0，所以x4确定为出基变量。于是新的典则方程为： x1 =25 - 0.5x2 - 0.5 x4 x3 =20 - x2 + 2 x4,2019/8/18,6,（一）单纯形方法的初步讨论,第六步，产生新的基本可行解及目标函数值。令x2 、 x4等于0，得到x1 =25

4、， x3 =20，于是新的基本可行解为X=（25，0，20，0），目标函数值为Z=1250。 第七步，判定目标函数值是否得到了最优。根据分析目前的方案还不是最优的。重复第四、五、六步， x2入基， x3 出基，建立新的典则方程： x1 =15+ 0.5 x3 -1.5 x4 x2 =20 - 2 x3 + 2 x4 令非基变量x3 、 x4等于0，得到新的基本可行解X=（15，20，0，0），目标函数值为1350。 问题求解完成。,2019/8/18,7,五、 单纯形方法,（二）单纯形方法的矩阵描述 1、线性规划的典则形式： Max Z=CBB-1b+(CN-CBB-1N)XN St XB=B

5、-1b-B-1NXN XB , XN 0 2、判别向量与判别数： （a）=CN- CBB-1A为对应基B的所有X的判别向量，其中任一分量j=cj-CBB-1Aj 为变量xj关于基B的判别数，j=1,2, -, n。,2019/8/18,8,五、 单纯形方法,2、判别向量与判别数： （b）N=CN-CBB-1N为对应基B的所有非基变量XN的判别向量，其中任一分量j=cj-CBB-1Aj 为非基变量xj关于基B的判别数，j=m+1,m+2, -, n。 （c）所有基变量的判别向量是零向量，所有基变量的判别数是0（为什么？）。 3、最优解的判定： （a）如果所有的检验数都小于0，则当前解为最优解。,

6、2019/8/18,9,五、 单纯形方法,3、最优解的判定： （b）如果至少存在一个检验数大于0，且该检验数对应的列向量中至少有一个正分量，则需要继续进行迭代寻找最优解。 （c）如果至少存在一个检验数大于0，且该检验数对应的列向量的所有分量都小于0，则线性规划问题不存在有界最优解。,2019/8/18,10,五、 单纯形方法,（三）单纯形方法：表上作业法 1、单纯形表的构造 方法1：C-CBB-1A=(CB,CN)-CBB-1(B,N) =(0,CN-CBB-1N) 两边同乘上X得： （C-CBB-1A）X= (0,CN-CBB-1N)X，化简得： Z=CBB-1b+(CN-CBB-1N) X

7、N 构造联立方程： Z+(CBB-1A- C) X =CBB-1b B-1AX =B-1b,2019/8/18,11,五、 单纯形方法,1、单纯形表的构造 这样得到单纯形表：,2019/8/18,12,五、 单纯形方法,1、单纯形表的构造 方法2： XB=B-1b-B-1NXN，则有： XB+B-1N XN =B-1b 又 Z=CBB-1b+(CN-CBB-1N)XN，于是： Z+（CBB-1N-CN）XN=CBB-1b，这样得： Z+（CBB-1N-CN）XN=CBB-1b XB +B-1N XN=B-1b 构造单纯形表：,2019/8/18,13,五、 单纯形方法,（三）单纯形方法：表上作

8、业法 1、表上作业的步骤： 第一步，将线性规划问题进行标准化处理。 第二步，确定初始基本可行解与初始可行基。 第三步，编制单纯形计算表。 第四步，计算检验数，判断线性规划问题是否有最优解。 第五步，确定入基变量。一是最大检验数准则，二是最 小下标准则。 第六步，确定出基变量。最小检验数对应的基变量出基。 第七步，编制新的单纯形表。重复以上的第四七步， 直到能够确定线性规划问题是否有最优解为止。,2019/8/18,14,五、 单纯形方法,2、单纯形方法：表上作业法 应用举例 求解下列线性规划问题： Min Z=X1-3X2 S.t. 2X1+4X2 6 -X1+3X25 X1 , X20 解：

9、 第一步，将上述问题进行标准化处理：,2019/8/18,15,五、 单纯形方法,应用举例 Max Z=-X1+3X2 S.t. 2X1+4X2+X3 =6 -X1+3X2 + X4 =5 X1,X2,X3,X4 0 第二步，确定初始基本可行解与初始基本可行基。 初始可行基： B=（A3,A4） 初始可行解： X=（0，0，6，5）,2019/8/18,16,五、 单纯形方法,应用举例 第三步，构造单纯形表：,2019/8/18,17,五、 单纯形方法,应用举例 第四步，计算检验数并判断是否是最优解。检验数列在初始单纯形表中的最后一行。 第五步，确定入基变量。 对应的检验数最大，所以确定X2为

10、入基变量。 第六步，确定出基变量。计算的检验数列在初始单纯形表中的最后一列。根据出基变量的判别准则，应确定X3出基。,2019/8/18,18,五、 单纯形方法,第七步，构造新的单纯形表：,2019/8/18,19,五、 单纯形方法,应用举例 第八步，判定迭代到这一步是否应该停止。 因为所有的非基变量的检验数都为负数，因此可以判断迭代到此步的基是最优基，目标函数值为Z=4.5，最优解为X=（0，1.5，0，0）。原问题的最优解为X=（0，1.5，0，0），目标函数值为Z=-4.5。,2019/8/18,20,五、 单纯形方法,（四）确定初始基本可行解的方法 1、对于约束方程中都是小于等于0，并

11、且约束方程右边项皆大于0的情况，只要引进松弛变量即可得到单位阵的初始可行基。 2、如果约束方程都是等于某些值的情况，此时需要引进人工变量才能构造出单位阵的初始可行基和初始可行解。 3、如果约束方程中有大于某些值的情况，则需要引进剩余变量并同时引进人工变量，才能构造出单位阵的初始可行基和初始可行解。,2019/8/18,21,六、 线性规划的其他解法,（一）人工变量消除法M法 1、M法的含义： 通过引进人工变量，构造一个辅助的线性规划问题，然后由辅助的线性规划问题找出原问题的第一个初始可行基，在此基础上，利用单纯形方法求出原问题的最优解。,2019/8/18,22,六、 线性规划的其他解法,（一

12、）人工变量消除法M法 2、M法的辅助线性规划问题： 原问题： Max z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn=b1 a21 x1+ a22x2+ +a2nxn =b2 am1x1+am2x2+amnxn=bm x1,x2, ,xn 0,2019/8/18,23,六、线性规划的其他解法,（一）人工变量消除法M法 2、M法的辅助线性规划问题： Max z=c1x1+c2x2+cnxn-MXn+1-MXn+2-MXn+m s.t. a11x1+a12x2+a1nxn+Xn+1 =b1 a21x1+a22x2+ +a2nxn + Xn+2 =b2 am1x1+a

13、m2x2+ +amnxn +Xn+m=bm x1,x2, ,xn 0,2019/8/18,24,六、线性规划的其他解法,3、M法的解题步骤 （1）把原线性规划问题进行标准化处理。 （2）引进人工变量，构造辅助线性规划问题。 （3）运用单纯形方法，把人工变量全部剔除出基变量。 （4）在得到的原问题的初始可行基的基础上，运用单纯形方法进行迭代。 （5）直到能够判断原问题有无最优解时为止。,2019/8/18,25,六、线性规划的其他解法,4、M法解的判定 （1）经过若干次迭代后，基变量中无人工变量，则说明原问题有基本可行解。 （2）经过若干次迭代后，基变量中仍有人工变量，并且全部检验数皆小于0，则

14、表明原问题无可行解。,2019/8/18,26,六、线性规划的其他解法,（二）人工变量消除法两阶段法 1、含义：在原来问题引入人工变量后分两个阶段求解线性规划问题的方法。其中，第一阶段在原来问题中引入人工变量，设法构造一个单位阵的初始可行基，另外在目标函数中令非人工变量的系数全部为0，人工变量的系数为1，构造一个新的辅助目标函数。在此基础上，建立辅助线性规划问题。然后运用单纯形方法求解，直到辅助目标函数为0时为止。第二阶段重新回到原来的问题，以第一阶段得到的可行基为初始可行基，运用单纯形方法以求出原来问题的解。,2019/8/18,27,六、 线性规划的其他解法,（二）人工变量消除法两阶段法 2、两阶段法的辅助问题： 原问题： Max z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn =b1 a21 x1+ a22x2+ +a2nxn =b2 am1x1+am2x2+amnxn =bm x1,x2, ,xn 0,2019/8/18,28,六、线性规划的其他解法,（二）人工变量消除法两阶段法 2、两阶段法的辅助问题： 辅助问题： Min Z/=Xn+1+Xn+2+Xn+m s.t. a11x1+a12x2+a1nxn+Xn+1 = b1 a21 x1+ a22x2+