资源描述：
《运筹学讲义-单纯形方法.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、运筹学耿修林8/24/20211五、单纯形方法（一）单纯形方法的初步讨论1、单纯形方法的基本思想从可行域中的一个基本可行解出发，判断它是否已是最优解，若不是，寻找下一个基本可行解，并使目标函数得到改进，如此迭代下去，直到找出最优解或判定问题无界为止。从另一个角度说，就是从可行域的某一个极点出发，迭代到另一个极点，并使目标函数的值有所改善，直到找出有无最优解时为止。8/24/20212五、单纯形方法（一）单纯形方法的初步讨论2、单纯形方法：消去法[例]求解线性规划模型解：第一步，将线性规划模型标准化：MaxZ=50x1+30x2+0x3+0x4s·t·4x
2、1+3x2+x3=1202x1+x2++x4=50x1,x2,x3,,x4≥08/24/202132、单纯形方法：消去法第二步，寻找初始可行解。变量x3、,x4对应的列向量A3、A4可作为初始可行基，那么X3、X4为基变量，X1、X2为非基变量，用非基量表示基变量，则有：MaxZ=50x1+30x2+0x3+0x4s·t·x3=120-4x1-3x2x4=50-2x1-x2x1,x2,x3,,x4≥0令x1、x2=0，得到基本可行解X=（0，0，120，50）。文本文本文本文本文本文本文本文本8/24/20214五、单纯形方法2、单纯形方法：消去法第三步
3、，判断目标函数是否达到了最优。第四步，选取入基变量。确定x1为基变量，x2仍为非基变量。第五步，选取出基变量。x3=120-4x1-3x2≥0x4=50-2x1-x2≥0解不等式得：x1≤25，只有当x1=25时，x4恰好等于0，所以x4确定为出基变量。于是新的典则方程为：x1=25-0.5x2-0.5x4x3=20-x2+2x48/24/20215（一）单纯形方法的初步讨论第六步，产生新的基本可行解及目标函数值。令x2、x4等于0，得到x1=25，x3=20，于是新的基本可行解为X=（25，0，20，0），目标函数值为Z=1250。第七步，判定目标函数
4、值是否得到了最优。根据分析目前的方案还不是最优的。重复第四、五、六步，x2入基，x3出基，建立新的典则方程：x1=15+0.5x3-1.5x4x2=20-2x3+2x4令非基变量x3、x4等于0，得到新的基本可行解X=（15，20，0，0），目标函数值为1350。问题求解完成。8/24/20216五、单纯形方法（二）单纯形方法的矩阵描述1、线性规划的典则形式：MaxZ=CBB-1b+(CN-CBB-1N)XNS·t·XB=B-1b-B-1NXNXB,XN≥02、判别向量与判别数：（a）λ=CN-CBB-1A为对应基B的所有X的判别向量，其中任一分量λj=
5、cj-CBB-1Aj为变量xj关于基B的判别数，j=1,2,-------,n。8/24/20217五、单纯形方法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，则当前解为最优解。8/24/20218五、单纯形方法3、最优解的判定：（b）如果至少存在一个检验数大于0，且该检验数
6、对应的列向量中至少有一个正分量，则需要继续进行迭代寻找最优解。（c）如果至少存在一个检验数大于0，且该检验数对应的列向量的所有分量都小于0，则线性规划问题不存在有界最优解。8/24/20219五、单纯形方法（三）单纯形方法：表上作业法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)XN构造联立方程：Z+(CBB-1A-C)X=CBB-1bB-1AX=B-1b8/24/202110
7、五、单纯形方法1、单纯形表的构造这样得到单纯形表：8/24/202111五、单纯形方法1、单纯形表的构造方法2：XB=B-1b-B-1NXN，则有：XB+B-1NXN=B-1b又Z=CBB-1b+(CN-CBB-1N)XN，于是：Z+（CBB-1N-CN）XN=CBB-1b，这样得：Z+（CBB-1N-CN）XN=CBB-1bXB+B-1NXN=B-1b构造单纯形表：8/24/202112五、单纯形方法（三）单纯形方法：表上作业法1、表上作业的步骤：第一步，将线性规划问题进行标准化处理。第二步，确定初始基本可行解与初始可行基。第三步，编制单纯形计算表。第
8、四步，计算检验数，判断线性规划问题是否有最优解。第五步，确定入基变量。一是最大检
