单纯形法的解题步骤0001

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

2、数所在列，用常数项 -!.：. 与进基变量所对应的列向h量中正分量的比值最小者；（3） 换基：用进基变量“替换出基变量从而得到新的基变量也就是主元所在列的非基变量进基，所在行的基变量出基；（4） 利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到 新的单纯形表；（5）回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得 到解决为止例 3 求-J.1-亠：；=.xl5TJ+221000 = L2,W)（2）作单纯形表：在约束方程组系数矩阵中:的系数构成单位矩阵，故取心二.匚为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表 6.8）表 6.8X

3、1X2X3XX5常数X31 0 1 0 05X41 2 0 1 010X50 (1) 0 0 14S130000X31 0 1 0 05X4(1) 0 0 1 -22X20 1 0 0 14S1000 -3-12X30 0 1 -1 23X11 0 0 1 -22=10心-*4X20 1 0 0 14S000 -1 -1-14（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为JT=2 4 3 0 Of目标函数取得最优值一了 .原线性规划问题的最优解为：6 二*.匚二 4 .目标函数的最优值为 14,即.? = ；-?丄=1 .例 4 用单纯形方法解线性规划问题经整理后，目标

4、函数非基化了作单纯形表，并进行换基迭代（见表6.9）最大检验数 _-，由最小比值法知：-为主兀，对主兀所在列施以行初等变换，基变量 三出基，非基变量进基兀花十兀二2一坯+心+心-4 OU = 134）解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（ 列构成），取为基变量，而目标函数没有非基化.从约束方程找出1、2 行，3、4, 一一 - ,18-:1,X1X2X3X4常数X31-1102X4-3 (1)014S23000X3-20116X2-31014S110 0-312目前最大检验数T 二.1,其所在列没有正分量，所以该线性规划问题没有最优解例 5 用单纯形方法解线性规划问题求

5、II : + -4解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵，取匸亠为基变量，而目标函数没有非基化.从约束方程找出6.9-:1,代入目标函数，经整理得目标函数已非基化作单纯形表，并进行换基迭代（见表 6.10）.最大检验数，由最小比值法知： 亠打 二为主元，对主元所在列施以行初等变换，基变量门出基，非基变量X2进基，先将主元= /化为 1,然后再将主元所在列的其他元素化为零表 6.10X1XX3X4常数X3-2（2）104X431 016S-2 20010X2-1 1+02X440 -吉 14S0 0-106至此，检验数均为非正数，故得基础可行解 - _ I1-.原问题的最优解为：，）. .最优值为 6，即;i_JL - J J 1-匚.如果我们再迭代一次，将基变量门出基，非基变量讥进基（见表 6.11）表 6.11X1X2X3X4常数X2-111202X4（4）01a14S00 -10吉6X20138143X110111S00-E06可得到另一个基础可行解丁-1-|. J I.?,原问题的最优解为,最优值仍为 6,说明该线性规划问题有无穷多最优解，其最优解均为6.如何知道线性规划问题有无穷多最