单纯形法思想原理wxp.ppt

《单纯形法思想原理wxp.ppt》由会员分享，可在线阅读，更多相关《单纯形法思想原理wxp.ppt（82页珍藏版）》请在三一文库上搜索。

1、1-3 单纯形法,方便、有效、通用,图解法的局限性？ 1947年G.B.Dantzig(丹捷格)提出的单纯形法提供了方便、有效的通用算法求解线性规划。,一、单纯形法的基本思想 1、顶点的逐步转移,转移条件：使目标函数值得到改善 停止准则：目标函数达到最优值,基本可行解,根据线性规划问题的可行域是凸集（凸多边形或凸多面体），若LP有最优解，就一定可以在可行域的顶点上找到。 于是，若LP只有唯一最优解，这个最优解所对应的点一定是可行域的一个顶点；若LP有多个最优解，那么肯定在可行域的顶点中可以找到至少一个最优解。,顶点转移的依据？,转移条件？ 转移结果？ 使目标函数值得到改善 得到LP最优解，目标

2、函数达到最优值 2需要解决的问题： (1)为了使目标函数逐步变优，怎么转移？ (2)目标函数何时达到最优 判断标准是什么？,二、单纯形法原理（用代数方法求解 LP） 例,第一步：引入非负的松弛变量X3,x4,x5,将该 LP化为标准型,x3, x4, x5 三个松弛变量的经济含义表示什么？,第二步：寻求初始可行基，确定基变量,对应的基变量是 x3，x4，x5；,第三步：写出初始基本可行解和相应的 目标函数值,两个关键的基本表达式： 用非基变量表示基变量的表达式,用非基变量表示目标函数的表达式,请解释结果的经济含义 不生产任何产品，资源都没有被利用（ x3=8,x4=16,x5=12），两种产品

3、的总利润为0！,第四步：分析两个基本表达式，看看 目标函数是否可以改善？, 分析用非基变量表示目标函数的表达式,非基变量前面的系数均为正数，所以任何一个非基变量进基都可能使Z值增加 通常, 把非基变量前面的系数叫“检验数”, 选哪一个非基变量进基？ 选x2为进基变量（换入变量） 问题讨论：能否选其他的非基变量进基？, 任意一个 任意一个正检验数对应的非基变量 最大正检验数对应的非基变量 排在最前面的正检验数对应的非基变量, 确定出基变量： 问题讨论, x2进基意味着其取值从0变成一个正数（经济意义生产乙产品），能否无限增大？ 当x2增加时，x3、x4、x5 如何变化？ 现在的非基变量是哪些？

4、具体如何确定换出变量？,根据非基变量表示基变量的表达式,当x2增加时， x3， x5会减小，但有限度必须0，以保持解的可行性！于是,当x2的值从0增加到3时, x5首先变为0, 此时x3=20， 因此选x5为出基变量（换出变量）。 这种用来确定出基变量的规则称为 “最小比值原则”（或原则）。,P1 P2 P3 P4 P5 x1 x2 x3 x4 x5,向量: 变量:,非基变量 x2 进基:,基变量 x5 出基:, 基变换 新的基变量x2 , x3, x4；新的非基变量x1, x5； 写出用非基变量表示基变量的表达式：,得新的基本可行解 X(1)=(0，3，2，16，0)T,由, 写出用非基变量

5、表示目标函数的表达式:,可得相应的目标函数值为Z(1)=9,检验数仍有正的, 返回进行讨论。,第五步：上述过程何时停止？,分析用非基变量表示目标函数的表达式，如果让负检验数所对应的变量进基，目标函数值将下降！Z=14-1.5x3-0.125x4,当用非基变量表示目标函数的表达式中，非基变量的系数（检验数）全部非正时，当前的基本可行解就是最优解! 为什么？,例,第一步：引入非负的松弛变量x4,x5, 将该 LP化为标准型,第二步：寻求初始可行基，确定基变量,对应的基变量是 x4，x5；,第三步：写出初始基本可行解和相应的 目标函数值,两个关键的基本表达式： 用非基变量表示基变量的表达式,用非基变

6、量表示目标函数的表达式,请解释结果的经济含义 不生产任何产品，资源全部节余（x4=3，x5=9），三种产品的总利润为0！,第四步：分析两个基本表达式，看看 目标函数是否可以改善？, 分析用非基变量表示目标函数的表达式,非基变量前面的系数均为正数，所以任何一个非基变量进基都能使Z值增加 通常, 把非基变量前面的系数叫“检验数”, 确定出基变量：用非基变量表示基变量的表达式,当x1增加时，x4, x5会减小，但有限度必须0，以保持解的可行性！于是,当x1的值从0增加到3时, x4首先变为0, 此时x5=60 因此选x4为出基变量“最小比值原则” 。,P1 P2 P3 P4 P5 x1 x2 x3

7、x4 x5,向量: 变量:,非基变量 x1 进基:,基变量 x4 出基:, 基变换 新的基变量x1, x5；新的非基变量x2, x3, x4； 写出用非基变量表示基变量的表达式：,得新的基本可行解 X(1)=(3，0，0，0，6)T,由, 写出用非基变量表示目标函数的表达式:,可得相应的目标函数值为Z(1)=6,检验数仍有正的, 返回进行讨论。,三、单纯形法的一般描述： 1、初始可行解的确定 (1)初始可行基的确定 观察法观察系数矩阵中是否含有现成的单位阵？ LP限制条件中全部是“”类型的约束 将新增的松弛变量作为初始基变量，对应的系数列向量构成单位阵；,（2）写出初始基本可行解 根据“用非基

8、变量表示基变量的表达式”，非基变量取0，算出基变量，搭配在一起构成初始基本可行解。,2、建立判别准则： （1）两个基本表达式的一般形式 就LP限制条件中全部是“”类型约束，新增的松弛变量作为初始基变量的情况来描述：,此时LP的标准型为,初始可行基 ：,初始基本可行解：,一般（经过若干次迭代），对于基B， 用非基变量表出基变量的表达式 为：,用非基变量表示目标函数的表达式：,若 是对应于基B的基本可行解， 是非基变量 的检验数，若对于一切非基变量的角指标j，均有 0，则X(0)为最优解。,（2）最优性判别定理,（3）无“有限最优解”的判别定理,若 为一基本可行解，有一非基变量xk,其检验数 ,

9、而对于i=1,2,，m，均有 ，则该线性规划问题没有“有限最优解”。,证明思路构造性证明： 依据用非基变量表示基变量的表达式构造一组可行解，其对应的目标函数值趋于无穷大。 可以看出： 将随着 的增大而增加，可行性自然满足；最小比值原则失效，LP问题无“有限最优解” 。,举例：用非基变量表示基变量的表达式,代表两个约束条件：,x2对应的系数列向量P2=(1，3)T， 当前的换入变量是 x2，按最小比值原则确定换出变量：,要求：,于是：,如果x2的系数列变成P2=(-1，0)T, 则,可行性自然满足,最小比值原则失效, 意即x2的值可以任意增大原LP无“有限最优解”。,3、进行基变换 （1）选择进

10、基变量原则：正检验数（或最大正检验数）所对应的变量进基，目的是使目标函数得到改善（较快增大）； 进基变量对应的系数列称为主元列。 （2）出基变量的确定按最小比值原则确定出基变量，为的是保持解的可行性； 出基变量所在的行称为主元行。 主元行和主元列的交叉元素称为主元素。,4、主元变换（旋转运算或枢运算） 按照主元素进行系数增广矩阵的初等行变换把主元素变成1，主元列的其他元素变成0（即主元列变为单位向量）,用非基变量表示基变量的表达式，用非基变量表示目标函数的表达式。,思考：这是在干什么呢？,写出新的基本可行解，返回最优性检验。,单纯形法小结,求解思想 顶点的逐步转移， 条件是 使目标函数值不断得

11、到改善。,四、表格单纯形法： 1、 初始单纯形表的建立 (1)表格结构：,（2）表格设计依据： 将-Z看作不参与基变换的基变量，把目标函数表达式改写成方程的形式，和原有的m个约束方程组成一个具有n+1个变量、m+1个方程的方程组：,取出系数写成增广矩阵的形式：,-Z x1 x2 xm xm+1 xm+2 xn b,-Z，x1，xm所对应的系数 列向量构成一个基,用矩阵的初等行变换将该基变成单位阵,这时 变成0，相应的增广矩阵变成如下形式：,（3）检验数的两种计算方法： 利用矩阵的行变换，把目标函数表达式中 基变量前面的系数变为0； 使用计算公式,增广矩阵的最后一行就是用非基变量表示目标函数的表

12、达式, (j=1,2,n)就是非基变量的检验数。,根据增广矩阵设计单纯形表,表格单纯形法求解步骤,第一步：将LP化为标准型，并加以整理。 引入适当的松驰变量、剩余变量和人工变量，使约束条件化为等式，并且约束方程组的系数阵中有一个单位阵。 确定初始可行基，写出初始基本可行解,第二步：最优性检验,计算检验数，检查： 所有检验数是否 0？ 是结束，写出最优解和目标函数最优值； 还有正检验数检查相应系数列 0？ 是结束，该LP无“有限最优解”！ 不属于上述两种情况，转入下一步基变换。 确定是停止迭代还是转入基变换？,选择（最大）正检验数对应的系数列为主元列，主元列对应的非基变量为换入变量； 最小比值对

13、应的行为主元行，主元行对应的基变量为换出变量。,第三步：基变换,确定进基变量、出基变量。,利用矩阵初等行变换把主元列变成单位向量,主元素变为1，进基变量对应的检验数变成0,从而得到一张新的单纯形表，返回第二步。,第四步 换基迭代（旋转运算、枢运算),完成一次迭代，得到新的基本可行解和相应的目标函数值,该迭代过程直至下列情况之一发生时停止 检验数行全部变为非正值； （得到最优解）或 主元列 0 （最优解无界）,停止迭代的标志,依据：最优性检验的两个定理 最优性判别定理；无“有限最优解”判断定理,例,从最优表可知: 该LP的 最优解是X*=(4, 2, 0, 0, 4)T 相应的目标函数最优值是Z

14、max=14,例、表格单纯形法计算过程：,例、表格单纯形法计算过程：,从最优表可知: 该LP的 最优解是X*=(1, 2, 0, 0, 0)T 相应的目标函数最优值是Zmax=8,五、各种类型线性规划的处理 1、分类及处理原则： （1）类型一：目标要求是“Max”，约束条件是“”类型左边加上非负松弛变量变成等式约束（约束条件标准化），将引入的松弛变量作为初始基变量，则初始可行基是一个单位阵，用原始单纯形法求解。,（2）类型二：目标要求是“Max”，约束条件是“=”类型左边引入非负的人工变量，并将引入的人工变量作为初始基变量，则初始可行基是一个单位阵，然后用大M法或两阶段法求解。 （3）类型三：

15、目标要求是“Max”，约束条件是“”类型约束条件标准化，左边减去非负的剩余变量，变成等式约束，化为类型二。,（4）类型四：目标要求是“Min” 方法1化为极大化问题 方法2按照极小化问题直接在单纯形表格上计算处理，但是 相应的原则要作改动。,2、处理人工变量的方法： （1）大M法(惩罚法)在约束条件中人为地加入非负的人工变量，以便使它们对应的系数列向量构成单位阵。 问题：加入的人工变量如何处理？ 在目标函数中，给人工变量前面添上一个绝对值很大的负系数-M（M0），迭代过程中，只要基变量中还存在人工变量，这表示无可行解！,大M法 举例,加入人工 变量,大M法 举例,最优值Zmin=-Zmax=2

16、,最优解X*=(0,1,0,3,0), 最优表中，基变量不包含人工变量，则最优解就是原线性规划的最优解，不影响目标函数的取值； 最优表中，基变量中仍含有人工变量，表明原线性规划的约束条件(可行域)被破坏，线性规划没有可行解，也就没有最优解！,结 果,问题,结果中求得的最优解是哪个线性规划的最优解？,（2） 两阶段法 第一阶段：建立辅助线性规划并求解，以判断原线性规划是否存在基本可行解。 辅助线性规划的结构：目标函数W为所有人工变量之和，目标要求是使目标函数极小化，约束条件与原线性规划相同。,两阶段法 举例,第一阶段,两阶段法第一阶段,最优值Wmin=-Wmax=0,最优解X*=(0,1,0,3

17、,0),两阶段法 第二阶段,第二阶段： 将第一阶段的最优解作为初始可行解，目标函数换成原问题的目标函数，进行单纯形迭代，求出最优解。 问题讨论： 如何实施？需要重新建立初始 单纯形表吗？,第二阶段,实施中，在第一阶段最优表格中划去人工变量列，将表头部分和CB列的价值系数换成原问题的价值系数(把目标函数换成原线性规划的目标函数)，继续迭代，直至求出最优解。,最优值Zmin=-Zmax=2,最优解X*=(0,1,0,3,0),3、用表格单纯形法直接计算极小化线性规划 时要修改哪些原则？ （初始表？最优解判别？换入变量？换出变量？旋转运算？引入人工变量？） 最优性判别：所有检验数非负 换入变量选择原

18、则：（最小）负检验数所对应的变量进基，以保证目标函数值（较快）减小； 用大M法求解时，在目标函数中人工变量的前面添上一个很大的正系数M；,六、迭代过程中可能出现的问题及处理方法,1、为确定出基变量要计算比值，该比值=解答列元素/主元列元素。对于主元列的0元素或负元素是否也要计算比值？ （此时解的可行性自然满足，不必计算；如果主元列元素全部为0元素或负元素，则最小比值失效，线性规划无“有限最优解”）,2、出现若干个相同的最小比值怎么办？ （说明出现了退化的基本可行解，即非0分量的个数小于约束方程的个数。按照“摄动原理”所得的规则，从相同比值对应的基变量中选下标最大的基变量作为换出变量可以避免出现“死循环”现象） 3、选择进基变量时，同时有若干个正检验 数，怎么选？,（最大正检验数或从左至右第1个出现的正检验数所对应的非基变量进基） 课堂练习1-5：直接按极小化问题求解如下LP：,由最优表得： 最优解为X*=(0，1，0，3，0)T, 相应的目标函数最优值为 Zmin=2,第三次作业 P49 10）: (2)、(3) 分别用大M法与两阶段法求解！ 下周一交,