《物流运筹学(第10节-对偶单纯形法)》由会员分享，可在线阅读，更多相关《物流运筹学(第10节-对偶单纯形法)（32页珍藏版）》请在金锄头文库上搜索。
1、对偶单纯形法,对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。不是求解对偶问题的单纯形法，而是在原始问题的单纯形表中进行对偶处理。,对偶单纯形法原理,证明过程省略,对偶单纯形法,找出一个DP的可行基,LP是否可行 （XB 0）,保持DP为可行解情况下转移到LP的另一个基本解,最优解,是,否,循 环,结束,不是求解对偶问题的单纯形法，而是在原始问题的单纯形表中进行对偶处理。,即检验数0,是否b0,用对偶单纯形表求解条件： （1）找到检验数0的对偶单纯形表为初始单纯形表。 （2）存在bj0,对偶单纯形法,例2.9 用对偶单纯形法求解：,
2、解:（1）转化为标准式。（2）满足对偶单纯形法求解的基本条件,即检验数0,存在至少一个Bj0,Ci 0,对偶单纯形法,1. 确定出基变量：找出最小的检验数，设为bl，它对应的原问题的基变量即为换出变量。,2. 确定入基变量，,检验数行,对偶单纯形法,对偶单纯形法,原问题的最优解为：X*=（2 , 2 , 2 , 0 , 0 , 0），Z* =72 其对偶问题的最优解为：Y*= （1/3 , 3 , 7/3），W*= 72,对偶单纯形法,找出一个DP的可行基,LP是否可行 （XB 0）,保持DP为可行解情况下转移到LP的另一个基本解,最优解,是,否,循 环,结束,不是求解对偶问题的单纯形法，而是
3、在原始问题的单纯形表中进行对偶处理。,即检验数0,是否b0,用对偶单纯形表求解条件： （1）找到检验数0的对偶单纯形表为初始单纯形表。 （2）存在bj0时最优基不变，故-11。 调试工序的能力应在4h6h之间。,增加一个变量xj的分析若企业在计划期内，有新的产品可以生产，则在知道新产品的单位利润，单件资源消耗量时，可以在最优表中补充一列，其中的前m行可以由基矩阵的逆矩阵得到，而检验数行也可以由与其它列相同的方法计算得到。若检验数非正，则原最优解仍为最优，原生产计划不变，不生产这种新产品；否则，当检验数为正时，则应以该变量进基，作单纯形迭代，从而找出新的最优解。,例2-9 设美佳公司又计划推出新
4、型号的家电，生产一件所需设备A、B及调试工序的时间分别为3h、4h、2h，该产品的预期盈利为3元/件，试分析该产品是否值得投产；如投产，对该公司的最优生产计划有何影响。设生产x6件家电，有c6=3，P6=（3，4，2）T,灵敏度分析举例,增加一个变量xj的分析,灵敏度分析举例,最优生产计划应为每天生产7/2件家电，51/4件家电。,灵敏度分析举例,分析参数aij的变化,例2-10 在美佳公司的例子中，若家电每件需设备A,B和调试工时变为8h、4h、1h，该产品的利润变为3元/件，试重新确定该公司最优生产计划。设生产工时变化后的新家电的生产量为x2，其中：,灵敏度分析举例,原问题和对偶问题均为非
5、可行解,上表中第二阶段第一行的约束为： x3+4x4-24x5=-9 -x3-4x4+24x5+x6=9 替换后重新得表：,灵敏度分析举例,最优生产计划为每天生产11/4台家电，15/8台家电,灵敏度分析举例,增加一个约束条件在企业的生产过程中，经常有一些突发事件产生，造成原本不紧缺的某种资源变成为紧缺资源，对生产计划造成影响。 若把目前的最优解代入新增加的约束，能满足约束条件，则说明该增加的约束对最优解不构成影响，即不影响最优生产计划的实施。 若当前最优解不满足新增加的约束，则应把新的约束添到原问题的最优表内新的一行中去，用对偶单纯形方法来进行迭代，求出新的最优解。,增加一个约束条件,灵敏度分析举例,例2-11 设家电，经调试后，还需经过一道环境试验工序。家电每件需环境试验3h，家电每件需2h，又环境试验工序每天生产能力为12h。试分析增加该工序后的美佳公司最优生产计划。,（1）检验原问题的最优解是否仍适用。 将x1=7/2，x2=3/2代入3x1+2x212，27/212，所以不适用。 （2）加入松弛变量x6，得3x1+2x2+x6=12 （3）单纯形表求解。,灵敏度分析举例,注：表中同，=-3-2。,作业,2.13,
