三、单纯形法的解题步骤

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

2、丸只所在列，用常数项m =与进基变量从所对应的列向虬量中正分量的比值工最小者；（3）换基：用进基变量工兄替换出基变量 孔，从而得到新的基变量.也就是主元所在 列的非基变量进基，所在行的基变量出基；（4）利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到 新的单纯形表；（5）回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得 到解决为止.例3求m疆二知+ S.x1 5布+2沔10山，号4、沔，砺乏口解（1）化标准型：令菖二-s，引进松弛变量 吟乏S曲占0,心占0，其标准型为求 mm =知 S电+ 冷=5电十2心十 a+ = 10弋十L二4七0（j =技3牝

3、）（2）作单纯形表：在约束方程组系数矩阵中沔双的系数构成单位矩阵，故取 W4*为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）.表6.8x 1X2X3x4X5常数x 3101005X 41201010 x 50(1)0014S130000 x 3101005X 4(1)001-22x 2010014S1000-3-12X 3001-123X 11001-22010014S000-1-1-14（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为=2430 Of目标函数取得最优值S=T4.原线性规划问题的最优解为：电二2码二4.目标函数的最优值为14,即m

4、密抖二2 + 3 x 4 = 14.例4用单纯形方法解线性规划问题. TOC o 1-5 h z .1821求皿S二_互_亏七5,- x2 x3 = 2M - 3电+电+曲=4勺 OU 二技34）JJ解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4 列构成），取心孔为基变量，而目标函数没有非基化.从约束方程找出x冬二 2 沔 + 工卫， x* = 4 +3工,代入目标函数N = _诳_忑屯 +2 橱 + 勺）一（4+3 每一kJ = _2&i - 3心，经整理后，目标函数非基化了.作单纯形表，并进行换基迭代（见表6.9）.最大检验数 为二3，由最小比值法知：忘策二1

5、为主兀，对主兀所在列施以行初等变 换，基变量 冲出基，非基变量勺进基.表6.9目前最大检验数A=n，其所在列没有正分量，所以该线性规划问题没有最优 解.例5用单纯形方法解线性规划问题.求min 女+奶+心+孔一 2 工+2 +形=4鼠脖 3兀+ 工卫+4 = 6妇司。二12强）解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵，取“4为基变 量，而目标函数没有非基化.从约束方程找出号二 4 + 2兀一 2x2，互=6 ;k 一码,代入目标函数，经整理得打二 一2、一 2沔 +1。，目标函数已非基化.作单纯形表，并进行换基迭代（见表6.10）.最大检验数丸卫二2，由最小比值法知：队听2为

6、主x1X2X3X4常数兀，对主兀所在列施以行初等变换，基变量沔出基，非基变量2进基，先将主兀%31-1102吒=2化为1，然后再将主兀所在列的其他兀素化为零.X4-3(1)014S23000表 6.10X3-20116X2-31014S1100-312x 1X2x3x4常数x 3-2（2）104x 431016S-220010 x 2-111I02X 4401-214S00-106至此，检验数均为非正数，故得基础可行解=0 2 0 4f.原问题的最优解为：电二卫二4沔二a而=4.最优值为6，即 血3= 30 +2 + 0 + 4=6.如果我们再迭代一次，将基变量工1出基，非基变量 诳进基（见表6.11）.表 6.11_X1X2X3_4常数X2-111202X4（4）0_ 1 l14S00-106X201J8143X110111S00*14 06可得到另一个基础可行解JT=1 3 0 Of,原问题的最优解为：兀I二L听二4吟二5 二0，最优值仍为6,说明该线性规划问题有 无穷多最优解，其最优解均为6.如何知道线性