单纯形法的解题步骤.docx

《单纯形法的解题步骤.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、所在列的非基变量■■:为进基变量.（2）对最大正检验数所在列

3、实施最小比值法，确定出主元，并把主元加上小括号主元是最大正检验数.：所在列，用常数项与进基变量、所对应的列向量中正分量的比值匸最小者；%（3）换基：用进基变量;替换出基变量从而得到新的基变量.也就是主元所在列的非基变量进基，所在行的基变量出基；（4）利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到新的单纯形表；（5）回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得到解决为止.例3求二匚：；二1.4/5xx<54/54/54/54/5解（1）化标准型：令］二_「；，引进松弛变量.

4、■.2.,.-^2...'..i.，其标准型为4/5心王00二12巩5）（2）作单纯形表：在约束方程组系数矩阵中；.:；的系数构成单位矩阵，故取，；=仁：1为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）表6.8xiX2X3X4X5常数x3101005x41201010x50(1)0014S'130000x3101005X4(1)001-22X2010014S'1000-3-12x3001-123x11001-22x2010014S'000-1-1-144/5目X1X2X3X4常数原线X31-11

5、02目标X4-3(1)014S23000题.X3-20116X2-31014S1100-312(3)最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为标函数取得最优值J］_•性规划问题的最优解为：^^，］.函数的最优值为14'，即例4用单纯形方法解线性规划问.nunS=-x1-^x2+^x3--x4152535可一乃+心=2一3心十兀2+才4二4勺>0(/=1.234)1、2行，3、4解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵(列构成)，取】.二.为基变量，而目标函数没有非基化•从约束方程找

6、出—二，「二」丨“,代入目标函数〔821经整理后，目标函数非基化了作单纯形表，并进行换基迭代(见表6.9)最大检验数二-■■:，由最小比值法知:换，基变量爲出基，非基变量.［进基•-为主元，对主元所在列施以行初等变表6.9目前最大检验数f其所在列没有正分量，所以该线性规划问题没有最优解例5用单纯形方法解线性规划问题4/5求[—一二+..+…,-2巧+2乜+為=4st<坯+也+必二6可刃（八1234）解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵，取二y为基变量，而目标函数没有非基化•从约束方程找出—；］二,代

7、入目标函数，经整理得IT.'-.1111,目标函数已非基化.作单纯形表，并进行换基迭代（见表6.10）.最大检验数J,由最小比值法知：二为主元，对主元所在列施以行初等变换，基变量I出基，非基变量X2进基，先将主元二］化为1,然后再将主元所在列的其他元素化为零-.八表6.10X1X2X3X4常数X3-2（2）104X431016S-220010X2-11]202x440]—14S'00-1064/5至此，检验数均为非正数，故得基础可行解X二［0204f.原问题的最优解为：,—-】：，—-4.最优值为6，即二一一一._■II

8、■-如果我们再迭代一次，将基变量〔出基，非基变量爲进基（见表6.11）5/5至此，检验数均为非正数，故得基础可行解X二［0204f.表6.11X1X2X3X4常数X2-11102X4（4）0_114S'00-106X201了s143X1101——1*1S'00-106可得到另一个基础可行解—:::f,原问题的最优解为：；.-.■■-，最优值仍为6,说明该线性规划问题有无穷多最优解，其最优解均为亠6.一如何知道线性规划问题有无穷多最优解呢?这主要反映在单纯形表中.如果非基变量所对应的检验数为0,我们可对此列继续进行换基迭代

9、，就可以得到另一个基础可行解.以此作下去，可得到许多基础可行解，即相对应的最优解有无穷多个.5/5