《(完整word版)单纯形法的解题步骤.docx》由会员分享，可在线阅读，更多相关《(完整word版)单纯形法的解题步骤.docx（6页珍藏版）》请在三一文库上搜索。
1、三、单纯形法的解题步骤第一步：作单纯形表.)(1)把原线性规划问题化为标准形式；)(2)找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵；)(3)目标函数非基化；)(4)作初始单纯形表.第二步：最优解的判定.(1)若所有检验数都是非正数，即 儿纵人12 ,则此时线性规划问题已取 得最优解.(2)若存在某个检验数是正数，即 上 Q，而所对应的列向量无正分量，则线性规划 问题无最优解.如果以上两条都不满足，则进行下一步.第三步：换基迭代.(1)找到最大正检验数，设为 人,并确定所在列的非基变量 加为进基变量.(2)对最大正检验数 4t所在列实施最小比值法，确定出主元，并把主元加上小括号主元是最
2、大正检验数 人 所在列，用常数项 4Q = 12阅 与进基变量 力所对应的列向 be量中正分量的比值 最小者；口或(3)换基：用进基变量先替换出基变量 白,从而得到新的基变量.也就是主元所在列的非基变量进基，所在行的基变量出基；(4)利用矩阵的行初等变换，将主元变为1,其所在列其他元素都变为零，从此得到新的单纯形表；(5)回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得 到解决为止.例 3 求 max S = a + 3x解（1）化标准型：令 s二y ,引进松弛变量 为 Q网 。,公之0,其标准型为金+工三=5Xj + 2 盯 +1*-10Xq +x = 4打之 0。二
3、123,4。）（2）作单纯形表：在约束方程组系数矩阵中句, &的系数构成单位矩阵，故取匹力向为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）表6.8xix2x3x4x5常数x 3101005x 41201010x 50(1)0014S130000x 3101005X 4(1)001-22x2010014S1000-3-12x 3001-123x 11001-22x 2010014S000-1-1-14（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为X = 2 4 3 0 Of目标函数取得最优值二 1-.原线性规划问题的最优解为：用二2,5=4 .目
4、标函数的最优值为14,即 一 二：例4用单纯形方法解线性规划问题 .仃 1821求 _ -_ -.1、2 行，3、4解 此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（列构成），取 工j可为基变量，而目标函数没有非基化 .从约束方程找出窗=2一 a +阳，a =4+Mf,代入目标函数02,经整理后，目标函数非基化了作单纯形表，并进行换基迭代（见表6.9）.最大检验数 = 3,由最小比值法知：的?二1为主元，对主元所在列施以行初等变换，基变量 工出基，非基变量 内进基.表6.9X1X2X3X4常数X31-1102X4-3(1)014S23000X3-20116X2-31014S1100
5、-312目前最大检验数 1=11 ,其所在列没有正分量，所以该线TIe规划问题没有最优解例5用单纯形方法解线性规划问题 .求二.I. +. +-24 + 2勺 + x3= 4s.L 3/ + x2 + a4 = 6勺之 0(J = 123,4)kJ解 此数学模型已是标准型了， 其中约束方程含有一个二阶单位矩阵， 取 网J %为基变 量，而目标函数没有非基化.从约束方程找出网=4 + 2可- 2% , a=6- 3瓦-马,代入目标函数，经整理得T-： 11,目标函数已非基化作单纯形表，并进行换基迭代（见表6.10）.最大检验数= 2,由最小比值法知：= 2为主元，对主元所在列施以行初等变换，基变
6、量 也出基,非基变量X2进基，先将主元 口心二2化为1,然后再将主元所在列的 其他元素化为零一.一表 6.10X 1X2X3X4常数X 3-2(2)104X 431016S-220010X 2-11 202X 4401-另14S00-106至此，检验数均为非正数，故得基础可行解/ = 0 2 0 4.原问题的最优解为：. .最优值为 6,即 mmS=3xO+2+0+4=6.如果我们再迭代一次，将基变量工出基，非基变量进基（见表6.11）表 6.11X1X2X3X4常数X2-111022X4(4)01=14S00-106X201J1384X110111一,S00106可得到另一个基础可行解二，原问题的最优解为：否二1再= 3j3 = 0j4 = 0,最优值仍为6,说明该线性规划问题有无穷多最优解，其最优解均为 .一如何知道线性规划问题有无穷多最优解呢？这主要反映在单纯形表中.如果非基变量所对应的检验数为 0,我们可对此列继续进行换基迭代，就可以得到另一个基础可行解.以此作下去，可得到许多基础可行解，即相对应的最优解有无穷多个.