资源描述：
《《纯形法思想原理》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1-3单纯形法方便、有效、通用图解法的局限性？1947年G.B.Dantzig(丹捷格)提出的单纯形法提供了方便、有效的通用算法求解线性规划。一、单纯形法的基本思想1、顶点的逐步转移转移条件：使目标函数值得到改善停止准则：目标函数达到最优值LP可行域基本可行解根据线性规划问题的可行域是凸集（凸多边形或凸多面体），若LP有最优解，就一定可以在可行域的顶点上找到。于是，若LP只有唯一最优解，这个最优解所对应的点一定是可行域的一个顶点；若LP有多个最优解，那么肯定在可行域的顶点中可以找到至少一个最优解。顶点转移的依据
2、？转移条件？转移结果？使目标函数值得到改善得到LP最优解，目标函数达到最优值2．需要解决的问题：(1)为了使目标函数逐步变优，怎么转移？(2)目标函数何时达到最优——判断标准是什么？二、单纯形法原理（用代数方法求解LP）例第一步：引入非负的松弛变量X3,x4,x5,将该LP化为标准型x3,x4,x5三个松弛变量的经济含义表示什么？第二步：寻求初始可行基，确定基变量对应的基变量是x3，x4，x5；第三步：写出初始基本可行解和相应的目标函数值两个关键的基本表达式：①用非基变量表示基变量的表达式②用非基变量表示目标函
3、数的表达式请解释结果的经济含义——不生产任何产品，资源都没有被利用（x3=8,x4=16,x5=12），两种产品的总利润为0！第四步：分析两个基本表达式，看看目标函数是否可以改善？①分析用非基变量表示目标函数的表达式非基变量前面的系数均为正数，所以任何一个非基变量进基都可能使Z值增加通常,把非基变量前面的系数叫“检验数”②选哪一个非基变量进基？选x2为进基变量（换入变量）问题讨论：能否选其他的非基变量进基？任意一个任意一个正检验数对应的非基变量最大正检验数对应的非基变量排在最前面的正检验数对应的非基变量
4、×③确定出基变量：问题讨论x2进基意味着其取值从0变成一个正数（经济意义——生产乙产品），能否无限增大？当x2增加时，x3、x4、x5如何变化？现在的非基变量是哪些？具体如何确定换出变量？根据非基变量表示基变量的表达式当x2增加时，x3，x5会减小，但有限度——必须≥0，以保持解的可行性！于是当x2的值从0增加到3时,x5首先变为0,此时x3=2>0，因此选x5为出基变量（换出变量）。这种用来确定出基变量的规则称为“最小比值原则”（或θ原则）。P1P2P3P4P5x1x2x3x4x5B=(P3，P
5、4,P5)B=(P2,P3，P4)向量:变量:非基变量x2进基:基变量x5出基:基变换新的基变量——x2,x3,x4；新的非基变量x1,x5；写出用非基变量表示基变量的表达式：得新的基本可行解X(1)=(0，3，2，16，0)T由→⑤写出用非基变量表示目标函数的表达式:可得相应的目标函数值为Z(1)=9检验数仍有正的,返回①进行讨论。第五步：上述过程何时停止？——分析用非基变量表示目标函数的表达式，如果让负检验数所对应的变量进基，目标函数值将下降！Z=14-1.5x3-0.125x4当用非基变量表示目标函数的
6、表达式中，非基变量的系数（检验数）全部非正时，当前的基本可行解就是最优解!为什么？例第一步：引入非负的松弛变量x4,x5,将该LP化为标准型第二步：寻求初始可行基，确定基变量对应的基变量是x4，x5；第三步：写出初始基本可行解和相应的目标函数值两个关键的基本表达式：①用非基变量表示基变量的表达式②用非基变量表示目标函数的表达式请解释结果的经济含义——不生产任何产品，资源全部节余（x4=3，x5=9），三种产品的总利润为0！第四步：分析两个基本表达式，看看目标函数是否可以改善？①分析用非基变量表示目标函数的表达式
7、非基变量前面的系数均为正数，所以任何一个非基变量进基都能使Z值增加通常,把非基变量前面的系数叫“检验数”②确定出基变量：用非基变量表示基变量的表达式当x1增加时，x4,x5会减小，但有限度——必须≥0，以保持解的可行性！于是当x1的值从0增加到3时,x4首先变为0,此时x5=6>0因此选x4为出基变量“最小比值原则”。P1P2P3P4P5x1x2x3x4x5B=(P4,P5)B=(P1,P5)向量:变量:非基变量x1进基:基变量x4出基:基变换新的基变量——x1,x5；新的非基变量x2,x3,x4；写出用非基
8、变量表示基变量的表达式：得新的基本可行解X(1)=(3，0，0，0，6)T由→⑤写出用非基变量表示目标函数的表达式:可得相应的目标函数值为Z(1)=6检验数仍有正的,返回①进行讨论。三、单纯形法的一般描述：1、初始可行解的确定(1)初始可行基的确定观察法——观察系数矩阵中是否含有现成的单位阵？LP限制条件中全部是“≤”类型的约束——将新增的松弛变量作为初始基变量，对应的系数列向量构成
