单纯形法(人工变量法）.ppt

《单纯形法(人工变量法）.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性规划——单纯形法单纯形是在n维空间里由n+1个点组成的最简单图形7/25/20211一、单纯形法的基本原理单纯形法是一种迭代的算法，它的思是在可行域的顶点----基本可行解中寻优。由于顶点是有限个,因此，算法经有限步可终止。基本思路：从可行域的一个顶点到另一个顶点迭代求最优解。（注：转移的条件和目的是使MaxZ增加）7/25/20212①目标求极大值②变量非负③右端项非负④全部等式约束单纯形法要求线性规划模型（P-56）标准形式规范形式⑤系数矩阵中包含一个单位子矩阵每个约束方程中要有一个变量的系数１，而这个

2、变量在其余方程中不出现。7/25/20213一、单纯形法的基本原理（一）基本变量：如果变量xj在某一方程中系数为1，而在其它一切方程中的系数为零，则称xj为该方程中的基本变量。否则为非基本变量。（二）基本解：在典型方程中，设非基本变量为零，求解基本变量得到的解，称为基本解。（三）基本可行解：基本变量为非负的一组基本解称为基本可行解。7/25/20214规范形式—典型方程组(p-59)S.t.7/25/20215最优性的检验与解的判别7/25/20216则:7/25/20217检验数对线性规划问题的实际意义是：表示当

3、变量xj增加1个单位时，目标函数的增加量；其经济意义表示相对利润．当>0时，说明非基本变量增加1个单位，目标函数可以增加，即现在的函数值不是最优，还能增加．这时要将某个非基本变量换到基本变量中去（称为进基变量）．为了使目标函数值增长最快，所以应选择检验数最大的一项所对应的非基本变量进基,7/25/20218得到最优解或证明最优解不存在标准型从可行域某个顶点开始检查该点是否最优解不是取一个“相邻”、“更好”的顶点单纯形法的基本原理规范型7/25/20219单纯形法原理：第一步：引入非负的松弛变量，将LP化为标准形式第二

4、步：寻求初始可行基，确定基变量第三步：写出初始基本可行解和相应的目标函数值两个关键的基本表达式：1、用非基变量表示基变量的表达式2、用非基变量表示目标函数的表达式7/25/2021101、分析用非基变量表示目标函数的表达式通常把非基变量前面的系数叫做“检验数”（非基变量前面的系数均为正数时，任何一个非基变量进基都能使Z值增加）2、选哪一个非基变量进基任何一个正检验数对应的非基变量？最大正检验数对应的非基变量？排在最前面的正检验数对应的非基变量？3、确定出基变量（最小比值原则）4、基变换，写出新的用非基变量表示基变量的

5、表达式5、写出新的用非基变量表示目标函数的表达式检验数仍有正的，返回（1）进行讨论，当用非基变量表示目标函数的表达式中，检验数全部非正时，当前基本可行解就是最优解。第四步：分析两个基本表达式，看看目标函数是否还可以改善7/25/202111例8某制药厂生产甲、乙两种药品，它们均须在A、B、C三种设备上加工，每种设备的使用时间，每吨药品的加工时间以及所获利润见下表，甲、乙药品各生产多少吨，可使该厂所获利润最大？表1－5药品生产有关数据ABC利润（百元/吨）甲35970乙95330设备使用时间（小时）540450720二

6、、单纯形解法7/25/202112解：设甲、乙分别生产x1、x2吨，该厂所获利润为Z百元。建立数学模型如下：第二步：建立初始单纯形表并进行表的迭代（见表1－6）第一步：化线性规划模型为标准规范型（见上面右边）7/25/202113表1－6单纯形法表格计算过程C基变量B7030000θX1X2X3X4X5000X3X4X554045072035[9]9531000100011809080Cj-ZjO70300000070X3X4X130050800018[10/3]1/3100010-1/3-5/91/937.5152

7、40Cj-Zj5600020/300-70/903070X3X2X11801575001010100-12/53/10-1/101-1/61/6Cj-Zj5700000-2-20/37/25/202114由表得最优解相应的最优值Z＝5700例8的最优解是最优值是Z＝57007/25/202115单纯形法的基本步骤:1．建立初始单纯形表----确定初始基本可行解确定基变量、非基变量以及初始基本可行解和目标函数的值。（１）求出相应的检验数在用非基变量表达的目标函数表达式中，我们称非基变量xj的系数为检验数．2．最优性检验

8、7/25/202116（２）最优解判别如果任何一个非基变量的值增加都不能使目标函数值增加，即所有检验数非正，则当前的基本可行解就是最优解，计算结束。（３）无有限最优解判别如果有一个检验数大于０，且其所在的列的所有aij非正，则表示可行域是不封闭的，且目标函数值随进基变量的增加可以无限增加，此时，不存在有限最优解（或称有无界解或无最优解），计算结