《运筹学课件单纯形法的计算步骤资料》由会员分享，可在线阅读，更多相关《运筹学课件单纯形法的计算步骤资料（25页珍藏版）》请在金锄头文库上搜索。
1、本节重点： 单纯形表（特别是检验数行） 单纯形法的计算步骤 大M法 两阶段法 解的存在情况判别,41 单纯形表 用表格法求解LP，规范的表格单纯形表如下：,计算步骤,(1).找出初始可行基，确定初始基可行解，建立初始单纯形表。,(2).检验各非基变量xj的检验数，若j 0，j=m+1，n；则 已得到最优解，可停止计算，否则转入下一步。,(3).在j 0，j=m+1，n中，若有某个k对应xk的系数列向量Pk 0，则此问题是无界解，停止计算。否则，转入下一步。,(4).根据max(j 0) =k，确定xk为换入变量，按 规则计算, =minbi/aikaik0,可确定第l行的基变量为换出变量。转入
2、下一步。,2 3 0 0 0,1 2 1 0 0 4 0 0 1 0 0 4 0 0 1,0 2 3 0 0 0,0 0 0,8 16 12,x3 x4 x5,4 - 3,2 3 0 0 0,2 1 0 1 0 -1/2,- 9 2 0 0 0 -3/4,0 0 3,x3 x4 x2,2 4 -,( ),3 0 1 0 0 1/4,16 4 0 0 1 0,X(0)=(0，0，8，16，12)T， z0 =0,2 3 0 0 0,2 1 0 1 0 -1/2,-13 0 0 -2 0 1/4,2 0 3,x1 x4 x2,- 4 12,3 0 1 0 0 1/4,8 0 0 -4 1 2,X(
3、1)=(0，3，2，16，0)T， z1 =9,2 3 0 0 0,4 1 0 0 1/4 0,-14 0 0 -1.5 -1/8 0,2 0 3,x1 x5 x2,2 0 1 1/2 -1/8 0,4 0 0 -2 1/2 1,X(2)=(2，3，0，8，0)T， z2 =13,X(3)=(4，2，0，4，0)T， z3 =14,5 单纯形法的进一步讨论,51 人工变量法,解决初始基可行解的问题。当某个约束方程中没有明 显的基变量时，在该方程中加上人工变量。,其中第2、3个约束方程中无明显基变量，分别加上人工变x6, x7,这时，初始基和初始基可行解很明显。X(0)=(0，0，0，11，0，
4、3，1)T不满足原来的约束条件。如何使得可从X(0)开始，经迭代逐步得到x6=0，x7=0 的基可行解，从而求得问题的最优解，有两种方法：,反之，若加了人工变量的问题解后最优解中仍含人工变量为基变量，便说明原问题无可行解。例3的单纯形表格为：,只要原问题有可行解，随着目标函数向最大化方向的改善，人工变量一定会逐步换出基，从而得到原问题的基可行解，进而得到基最优解。,3.大M法,在目标函数中加上惩罚项,max =3x1-x2-x3-Mx6-Mx7 其中M为充分大的正数。,3-6M M-1 3M-1 0 -M 0 0,0 x4 10 3 -2 0 1 0 0 -1 -M x6 1 0 1 0 0
5、-1 1 -2 1 -1 x3 1 -2 0 1 0 0 0 1,1 -1+M 0 0 -M 0 -3M+1,2.两阶段法,第一阶段：以人工变量之和最小化为目标函数 min = x6+x7,第二阶段：以第一阶段的最优解(不含人工变量)为初始解，以原目标函数为目标函数。,5. 2 线性规划问题解的讨论,一、无可行解 max z=2x1+4x2 x1 +x2 10 2x1 +x2 40 x1 ,x2 0,人工变量不能从基底换出，此时原线性规划无可行解,x2,例: max z=3x1+4x2 x1 +x2 40 2x1+x260 x1-x2 =0 x1 ,x2 0,此题初始解是退化的。最优解也是退化
6、解。 退化解迭代中，当换入变量取零值时目标函数值没有改进，,例 max z=3x1+5x2 3x1 +5x2 15 2x1 + x2 5 2x1+2x2 11 x1 ,x2 0,如果将x1换入基底，得另一解，由可行域凸性易知，有两个最优解必有无穷多组最优解 当非基底变量的检验数中有取零值，或检验数中零的个数大于基变量个数时，有无穷多解。,四、无（有）界解 max z=x1+x2 -2x1+x2 4 x1- x2 2 -3x1+x23 x1 ,x2 0,若检验数有大于0，而对应系数列中元素全部小于，等于零（无换出变量）则原问题有无界解。,练习：写出单纯形表,分析检验数 与系数关系并画图验证。,线性规划解除有唯一最优解的情况外，还有如下几种情况,无可行解 退化 无穷多解 无界解,人工变量不能从基底中换出,基可行解中非零元素个数小于基变量数,检验数中零的个数多于基变量的个数,检验数大于零，但对应列元素小于等于零，无换出变量,对目标函数求标准型线性规划问题，用单纯形法计算步骤的框图如下：,
