《运筹学周四课件》由会员分享，可在线阅读，更多相关《运筹学周四课件（21页珍藏版）》请在金锄头文库上搜索。
1、求解如下线性规划问题,cj,最优解是,目标函数为-2。,第一阶段：求解辅助规划问题,2、两阶段法,cj,x6，x7是人工变量，第一阶段求解的最优结果是=0，因此得最优解为：,第二阶段：取消人工变量，添入原问题目标函数的系数，求解相应的线性规划。,最优解为：,最优值为： z= -2,（无可行解）求解下列线性规划问题 解： 首先将问题化为标准型 令，则,故引入人工变量， 并利用大M法求解,C,-3 -2 -1 0 0 0 -M -M,CB,XB,b,x1 x2 x3 x4 x5 x6 x7 x8,0 -M -M,x4 x7 x8,6 4 3,1 1 1 1 0 0 0 0 1 0 -1 0 -1
2、0 1 0 0 1 -1 0 0 -1 0 1,6/1 - 3/1,Z,-7M,-6-4M,-15-M,-3+M -2+M -1-2M 0 -M -M 0 0,0 -M -2,x4 x7 x2,3 4 3,1 0 2 1 0 1 0 -1 1 0 -1 0 -1 0 1 0 0 1 -1 0 0 -1 0 1,3/1 4/1 -,Z,Z,-3+M 0 -3-M 0 -M -2 0 2-M,-3 -M -2,x1 x7 x2,3 1 3,1 0 2 1 0 1 0 -1 0 0 -3 -1 -1 -1 1 1 0 1 -1 0 0 -1 0 1,0 0 3-3M 3-M -M 1-M 0 -1,
3、在以上最优单纯形表中，所有非基变量检验数都小于零，但在该表中人工变量x7=1为基变量，所以原线性规划不存在可行解。,（无界解）试用单纯形法求解下列线性规划问题： 解：引入松弛变量x3,x4化为标准型,因 但 所以原问题 无最优解,（退化）求解下述线性规划问题： 解：引入松弛变量 化标准型,0,0,0,-24,2,-80,3,0,Z,-5,-6,0,-42,0,-8,0,5,Z,1,0,0,0,1,0,0,1,x3,2,1,2,0,6,0,-24,1,1,x1,3,3,2,1,30,0,-8,0,3,x5,0,0,-3,0,-42,5,-8,0,0,Z,1,1,0,0,1,0,0,1,x7,0,
4、0,1,0,6,-1,-24,1,0,x1,3,0,-1,1,30,-3,-8,0,0,x5,0,-,1,1,0,0,1,0,0,1,x7,0,0,0,1,0,6,-1,-24,1,0,x6,0,0,0,0,1,36,-4,-32,1,0,x5,0,x7,x6,x5,x4,x3,x2,x1,b,XB,CB,0,0,0,-24,2,-80,3,C,第一次迭代中使用了摄动法原理，选择下标为6的基变量x6离基。,可得最优解 ，目标函数值maxZ=，,0,0,0,-24,2,-80,3,0,Z,0,0,-3,-132,14,16,0,0,Z,1,1,0,0,1,0,0,1,x7,0,0,1,-1,-3
5、0,3,8,0,0,0,0,-1,1,36,-4,-32,1,0,x5,3,-,1,1,0,0,1,0,0,1,x7,0,0,0,1,0,6,-1,-24,1,0,x6,0,0,0,0,1,36,-4,-32,1,0,x5,0,x7,x6,x5,x4,x3,x2,x1,b,XB,CB,x1,勃兰特法则,无穷多最优解：,用大M法或者二阶段法求解,标准型：,其中M是一个任意大的正数,CB,XB,b,x6,x7,x1,x2,x3,x4,x5,x6,x7,CB,XB,b,x7,x1,x2,x3,x4,x5,x6,x7,x2,CB,XB,b,x1,x2,x3,x4,x5,x6,x7,x2,x1,可得最优
6、解（4/5,5/8,0,0,0,0,0）,如下表，是某求极大化线性规划问题计算得到的单纯形表。表中无人工变量，a1，a2，a3，d，c1，c2为待定常数。试说明这些常数分别取何值时，以下结论成立。 （1）表中解为唯一最优解 （2）表中解为最优解，但存在无穷多最优解 （3）该线性规划问题具有无界解 （4）表中解非最优解，为对解改进，换入变量为x1，换出变量为x6 基 B X1 X2 X3 X4X5X6 X3 d4 a1 10a20 X4 2-1 -3 0 1-10 X6 3 a3-5 00-41 Cj-Zj c1c200-30,（1）当解为最优解时，必有d0，c10，c20。 （2）当解为最优解
7、，但存在无穷多最优解时，必有d0，c10，c2=0或d0，c1=0，c20 （3）当该问题为无界解时，必有d0，c10， c20且a10。 （4）当解为非最优，为对解进行改进，当换入变量为x1，换出变量为x6，必有d0，c10且 c1c2，a30，,无穷多最优解,无穷多最优解判别原理： 若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零，但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。 例：最优表： 非基变量检验 数，所以有无穷多 最优解。 最优解集为可行域两个顶点的凸组合：,退化解,当线性规划问题的基本可行解中有一个或多个基变量取零值时，称此基本可行解为退化解。 产生
8、的原因：在单纯形法计算中用最小比值原则确定换出变量时，有时存在两个或两个以上相同的最小比值，那么在下次迭代中就会出现一个甚至多个基变量等于零。 遇到的问题：当某个基变量为零，且下次迭代以该基变量作为换出变量时，目标函数并不能因此得到任何改变（由旋转变换性质可知，任何一个换入变量只能仍取零值，其它基变量的取值保持不变）。通过基变换以后的前后两个退化的基本可行解的坐标形式完全相同。从几何角度来解释，这两个退化的基本可行解对应线性规划可行域的同一个顶点， 解决的办法：最小比值原则计算时存在两个及其以上相同的最小比值时，选取下标最大的基变量为换出变量，按此方法进行迭代一定能避免循环现象的产生（摄动法原理）。,
