《三、单纯形法的解题步骤》由会员分享，可在线阅读，更多相关《三、单纯形法的解题步骤（6页珍藏版）》请在装配图网上搜索。
1、三、单纯形法的解题步骤第一步：作单纯形表.）（1）把原线性规划问题化为标准形式；）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵）（3）目标函数非基化；）（4）作初始单纯形表.第二步：最优解的判定.若所有检验数都是非正数，即仏兰03=12屈，则此时线性规划问题已取得最优解.（2）若存在某个检验数是正数，即A0，而所对应的列向量无正分量，则线性规划问题无最优解.如果以上两条都不满足，则进行下一步.第三步：换基迭代.（1）找到最大正检验数，设为A，并确定几丘所在列的非基变量忑为进基变量.（2）对最大正检验数兄k所在列实施最小比值法，确定出主元，并把主元加上小括号主元是最大正检验数几丘所
2、在列，用常数项込Q=12衍）与进基变量耳所对应的列向量中正分量的比值乞最小者；（3）换基：用进基变量耳替换出基变量兀，从而得到新的基变量也就是主元所在列的非基变量进基，所在行的基变量出基；（4）利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到新的单纯形表；（5）回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得到解决为止.例3求max+3x2.5xt+2x20解（1）化标准型：令空二-S，引进松弛变量心王0,心王0,心王0，其标准型为（2）作单纯形表：在约束方程组系数矩阵中也,险卫5的系数构成单位矩阵，故取，和冷为基变量，目标函数已非基化了，作初始单纯
3、形表并“换基迭代”（见表6.8）.表6.8x1x2X3X4X5常数X3101005X41201010X50(1)0014S130000x3101005X4(1)001-22x2010014S1000-3-12x3001-123X11001-22x2010014S000-1-1-14（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为X=24300r目标函数取得最优值用=-14.原线性规划问题的最优解为：眄=厶也=4.目标函数的最优值为14,即max；?=2+3x4=14.例4用单纯形方法解线性规划问题.解此数学模型已是标准型了,其中约束方程含有一个二阶单位矩阵（1、2行,3、
4、4列构成），取“4为基变量，而目标函数没有非基化从约束方程找出代入目标函数经整理后，目标函数非基化了.作单纯形表，并进行换基迭代（见表6.9）.最大检验数久2=3，由最小比值法知：也2=1为主兀，对主兀所在列施以行初等变换，基变量可出基，非基变量也进基.表6.9目前最大检验数A=n，其所在列没有正分量，所以该线性规划问题没有最优解.例5用单纯形方法解线性规划问题.求mmS=3x1+疋？+花+疋4解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵，取也卫4为基变量，而目标函数没有非基化从约束方程找出=4+2-2x2，X4=_3疋1-x2,代入目标函数，经整理得目标函数已非基化.作单纯形表
5、，并进行换基迭代（见表6.10）.最大检验数法知：总12=2为主以行初等变换，基变x2进基，先将主元再将主元所在列的其表6.10x1X2X3x4常数X31-1102X4-3(1)014S23000X3-20116x-31014S1100-312為二2，由最小比值元，对主元所在列施量也出基，非基变量圧12=2化为1,然后他元素化为零.x1xx3x4常数X3-2（2）04x431016S-220010x2-1102x440-214S400-106至此，检验数均为非正数，故得基础可行解=020原问题的最优解为：巧=0,也=2,心=0,忑4=4.最优值为6,即minS=3x0+2+0+4=6.如果我们再迭代一次，将基变量可出基，非基变量心进基（见表6.11）.表6.11x1xX3X4常数X2-1102X4（4）0414S00-106X201I3X110i11S00-106可得到另一个基础可行解=130Of,原问题的最优解为：X=1,也=3,花=0,百=0,最优值仍为6,说明该线性规划问题有无穷多最优解，其最优解均为6.如何知道线性规划问题有无穷多最优解呢？这主要反映在单纯形表中.如果非基变量所对应的检验数为0，我们可对此列继续进行换基迭代，就可以得到另一个基础可行解.以此作下去，可得到许多基础可行解，即相对应的最优解有无穷多个.
三、单纯形法的解题步骤
