单纯形法的解题步骤

1、三、单纯形法的解题步骤第一步：作单纯形表)(1)把原线性规划问题化为标准形式；)(2)找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵；)(3)目标函数非基化；)(4 )作初始单纯形表.第二步：最优解的判定.若所有检验数都是非正数，即.: ：，贝毗时线性规划问题已取得最优解.若存在某个检验数是正数，即a ,而所对应的列向量无正分量，则线性规划问题无最优解.如果以上两条都不满足，则进行下一步.第三步：换基迭代.(1) 找到最大正检验数，设为 订，并确定丄，所在列的非基变量"为进基变量.(2) 对最大正检验数.；、所在列实施最小比值法，确定出主元，并把主元加上小括号 主元是最大正检验

2、数、所在列，用常数项 I - . 与进基变量口所对应的列向量b中正分量的比值 最小者；%(3) 换基：用进基变量“替换出基变量亠，从而得到新的基变量.也就是主元所在列 的非基变量进基，所在行的基变量出基；(4) 利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到 新的单纯形表；(5) 回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得 到解决为止.例 3 求 I'.- "_ + ： » .解(1)化标准型：令，引进松弛变量.-'.1.-',其标准型为（2）作单纯形表：在约束方程组系数矩阵中的系数构成单位矩阵，故

3、取心.二.心为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表）.X1X2X3X4X5常数X3101005X41201010X50 (1) 0014S'130000X3101005X4(1) 001-22X2010014S'1000-3-12X3001-123xi1001-22X2010014S'000-1-1-14（3）最终结果： 数，线性规划问题取得目标函数取得最优值原线性规划问题的最优解 函数的最优值为14,即此时检验数均为非正最优解，最优解为为：二丄厂二二目标max j? = 2-l-3x4 = n4 .例4用单纯形方法解线性规划问题18 2 11

4、、2 行，3、4 列解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（ 构成），取为基变量，而目标函数没有非基化 从约束方程找出.二一-，飞 + -，1 -,代入目标函数g 22 +-(2-x1 + x3)-(4 + 3-x2) = -2x1 -3经整理后，目标函数非基化了 作单纯形表，并进行换基迭代（见表）最大检验数 _，由最小比值法知：， 1为主元，对主元所在列施以行初等变换,基变量 仏出基，非基变量门 进基.X1X2X3X4常数X3X41-110-3(1)0124划S23000题X3-20116X2-31014S1100-312表目前最大检验数：.，其所在列没有正分量，所以该线

5、性规问题没有最优解例5用单纯形方法解线性规划问求 I I . :'-.+.，一.=解此数学模型已是标准型了， 其中约束方程含有一个二阶单位矩阵，取为基变量,而目标函数没有非基化从约束方程找出代入目标函数，经整理得目标函数已非基化作单纯形表，并进行换基迭代（见表.最大检验数：亠：，由最小比值法知：一i二为主元，对主元所在列施以行初等变换， 基变量出基，非基变量X2进基，先将主元；二化为1，然后再将主元所在列的其他元 素化为零至此，检验数均为非 解X1X2X3X4常数X3-2 (2) 104X431016S-220010X2也。2X440弓14S'00-106正数，故得基础可行原问题的最优解为：.|1 'I .最优值为6，即匚二m + :如果我们再迭代一次，将基变量出基，非基变量.匚进基（见表）可得到另一个基础可X1X2X3X4常数X2-11L 022X4(4) 0 14S'00-10 亠6X2cC 1018 43X110-111S'& 4 00- 1 06表行解原冋题的最优解为： 亠.，最优值仍为6，说明该线性规划冋题有无穷多最优解，其最优解均为6.如何知道线性规划问题有无穷