单纯形法解题步骤.doc

三、单纯形法的解题步骤第一步：作单纯形表•） （1）把原线性规划问题化为标准形式；） （2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵；） （3）目标函数非基化；） （4）作初始单纯形表.第二步：最优解的判定.（1） 若所有检验数都是非正数，即 ，则此时线性规划问题已取得最优解.（2） 若存在某个检验数是正数，即：二小，而所对应的列向量无正分量，则线性规划 问题无最优解.如果以上两条都不满足，则进行下一步 .第三步：换基迭代.（1） 找到最大正检验数，设为 山，并确定，1|所在列的非基变量 ■■:为进基变量.（2） 对最大正检验数 所在列实施最小比值法，确定出主元，并把主元加上小括号主元是最大正检验数 .：所在列，用常数项 与进基变量 、所对应的列向量中正分量的比值 匸最小者；%（3） 换基：用进基变量 ;替换出基变量 从而得到新的基变量.也就是主元所在列的非基变量进基，所在行的基变量出基；（4） 利用矩阵的行初等变换，将主元变为 1，其所在列其他元素都变为零，从此得到 新的单纯形表；（5） 回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得 到解决为止.例 3 求二匚：；二 1 .# / 6xx<5解（1）化标准型：令］二_「；，引进松弛变量.■. 2.,.-^ 2 ...'.. i .，其标准型为心王00二12巩5）（2）作单纯形表：在约束方程组系数矩阵中 ； .:；的系数构成单位矩阵，故取，；=仁：1为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代” （见表6.8）表6.8xiX2X3X4X5常数x 3101005x 41201010x 50(1)0014S'130000x 3101005X 4(1)001-22X2010014S'1000-3-12x 3001-123x 11001-22x 2010014S'000-1-1-14目X1X2X3X4常数原线X31-1102目标X4-3(1)014S23000题.X3-20116X2-31014S1100-312(3) 最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为标函数取得最优值 J ］_ •性规划问题的最优解为：^ ^ ，］.函数的最优值为 14 '， 即例4用单纯形方法解线性规划问.nunS = -x1-^x2+^x3--x41 5 2 5 3 5可一乃+心=2 一 3心十兀2 +才4二4 勺 > 0(/ = 1.234)1、2 行，3、4解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵(列构成)，取】.二.为基变量，而目标函数没有非基化 •从约束方程找出—二，「二」丨 “ ,代入目标函数〔82 1经整理后，目标函数非基化了作单纯形表，并进行换基迭代(见表 6.9)最大检验数二-■■:，由最小比值法知: 换，基变量 爲出基，非基变量 .［进基•-为主元，对主元所在列施以行初等变表6.9目前最大检验数 f 其所在列没有正分量，所以该线性规划问题没有最优解例5用单纯形方法解线性规划问题求[—一二+.. + …,-2巧+ 2乜+為 =4st< 坯+也 +必二6可刃（八1234）解此数学模型已是标准型了， 其中约束方程含有一个二阶单位矩阵， 取二y为基变量，而目标函数没有非基化•从约束方程找出— ；］二,代入目标函数，经整理得IT . ' - . 1111,目标函数已非基化.作单纯形表，并进行换基迭代 （见表6.10）.最大检验数 J ,由最小比值法知：二为主元，对主元所在列施以行初等变换，基变量 I出基，非基变量X2进基，先将主元 二］化为1,然后再将主元所在列的其他元素化为零-. 八表 6.10X 1X2X3X4常数X 3-2（2）104X 431016S-220010X 2-11]202x 440]— 14S'00-106至此，检验数均为非正数，故得基础可行解 X 二［0 2 0 4f.原问题的最优解为： ,—-】：，—- 4 .最优值为6，即 二 一一 一 ._ ■ II ■ -如果我们再迭代一次，将基变量 〔出基，非基变量 爲进基（见表6.11）表 6.11X1X2X3X4常数X2-11102X4（4）01—= 14S'00-106X201了s143X1101二 H1J1S'00-106可得到另一个基础可行解—:::f,原问题的最优解为： ；. - .■ ■-，最优值仍为6,说明该线性规划问题有无穷多最优解，其最优解均为亠6. 一如何知道线性规划问题有无穷多最优解呢?这主要反映在单纯形表中.如果非基变量所对应的检验数为 0,我们可对此列继续进行换基迭代，就可以得到另一个基础可行解 .以此作下去，可得到许多基础可行解，即相对应的最优解有无穷多个.# / 6。