物流运筹学(第10节-对偶单纯形法).ppt

《物流运筹学(第10节-对偶单纯形法).ppt》由会员分享，可在线阅读，更多相关《物流运筹学(第10节-对偶单纯形法).ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Page 1对偶单纯形法对偶单纯形法 对偶单纯形法是求解线性规划的另一个基本方法。它对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。对偶单纯形法。不是求解对偶问题的单纯形法，而是在原始问题的单不是求解对偶问题的单纯形法，而是在原始问题的单纯形表中进行对偶处理。纯形表中进行对偶处理。对偶单纯形法原理对偶单纯形法原理对偶单纯形法原理对偶单纯形法原理Page 2证明过程省略Page 3对偶单纯形法对偶单纯形法找出一个找出一个DP的可行基的可行基LP是否可行是否可行（XB 0）保持保持DP为

2、可行解情况下转移到为可行解情况下转移到LP的另一个基本解的另一个基本解最优解最优解是是否否循循环环结束结束不是求解对偶问题的单纯形法，而是在原始不是求解对偶问题的单纯形法，而是在原始问题的单纯形表中进行对偶处理。问题的单纯形表中进行对偶处理。即检验数即检验数0是否是否b0用对偶单纯形表求解条件：用对偶单纯形表求解条件：（1）找到检验数）找到检验数0的对偶单纯形表为初的对偶单纯形表为初始单纯形表。始单纯形表。（2）存在）存在bj0Page 4对偶单纯形法对偶单纯形法例例2.9 用对偶单纯形法求解：用对偶单纯形法求解：解解:（1）转化为标准式）转化为标准式。（2）满足对偶单纯形法求解的基本条件）满

3、足对偶单纯形法求解的基本条件即检验数即检验数0存在至少一个存在至少一个Bj0Ci 0Page 5对偶单纯形法对偶单纯形法cj-9-12-15000bcBxBx1x2x3x4x5x60 x4-2-2-1100-100 x5-2-3-1010-120 x6-1-1-5001-14(-9/-1.-12/-1.-15/-5)j-9-12-1500001.确定出基变量：确定出基变量：找出最小的检验数，找出最小的检验数，设为设为bl，它对应的原，它对应的原问题的基变量即为问题的基变量即为换出变量。换出变量。2.确定入基变量，确定入基变量，检验数行Page 6对偶单纯形法对偶单纯形法cj-9-12-1500

4、0bcBxBx1x2x3x4x5x60 x4-9/5-9/5010-1/5-36/50 x5-9/5-14/5001-1/5-46/5-15x31/51/5100-1/514/5(-30/-9,-45/-14,-15/-1)-6-9000-342cj-9-12-15000bcBxBx1x2x3x4x5x60 x4-9/14001-9/14-1/14-9/7-12x29/14100-5/141/1423/7(-3/-9,-45/-9,-33/-1)-15x31/140101/14-3/1415/7-3/14000-45/14-33/14Page 7对偶单纯形法对偶单纯形法cj-9-12-1500

5、0cBxBx1x2x3x4x5x6b-9x1100-14/911/92-12x20101-102-15x30011/90-2/92000-1/3-3-7/3原问题的最优解为：原问题的最优解为：X*=（2,2,2,0,0,0），），Z*=72 其对偶问题的最优解为：其对偶问题的最优解为：Y*=（1/3,3,7/3），），W*=72Page 8对偶单纯形法对偶单纯形法找出一个找出一个DP的可行基的可行基LP是否可行是否可行（XB 0）保持保持DP为可行解情况下转移到为可行解情况下转移到LP的另一个基本解的另一个基本解最优解最优解是是否否循循环环结束结束不是求解对偶问题的单纯形不是求解对偶问题的单纯

6、形法，而是在原始问题的单纯法，而是在原始问题的单纯形表中进行对偶处理。形表中进行对偶处理。即检验数即检验数0是否是否b0用对偶单纯形表求解条件：用对偶单纯形表求解条件：（1）找到检验数）找到检验数0的对偶单纯形表为初始单纯形表。的对偶单纯形表为初始单纯形表。（2）存在）存在bj0时最优基不变，故-11。调试工序的能力应在4h6h之间。|增加一个变量xj的分析 若企业在计划期内，有新的产品可以生产，则在知道新产品的单位利润，单件资源消耗量时，可以在最优表中补充一列，其中的前m行可以由基矩阵的逆矩阵得到，而检验数行也可以由与其它列相同的方法计算得到。若检验数非正，则原最优解仍为最优，原生产计划不变

7、，不生产这种新产品；否则，当检验数为正时，则应以该变量进基，作单纯形迭代，从而找出新的最优解。例2-9 设美佳公司又计划推出新型号的家电，生产一件所需设备A、B及调试工序的时间分别为3h、4h、2h，该产品的预期盈利为3元/件，试分析该产品是否值得投产；如投产，对该公司的最优生产计划有何影响。设生产x6件家电，有c6=3，P6=（3，4，2）T灵敏度分析举例|增加一个变量xj的分析灵敏度分析举例cj210003CB基bx1x2x3x4x5x60 x315/20015/4-15/2-72x17/21001/4-1/201x23/2010-1/43/22cj-zj000-1/4-1/210 x35

8、1/407/213/8-9/402x17/21001/4-1/203x63/401/20-1/83/41cj-zj0-1/20-1/8-5/40最优生产计划应为每天生产7/2件家电，51/4件家电。灵敏度分析举例|分析参数aij的变化例2-10 在美佳公司的例子中，若家电每件需设备A,B和调试工时变为8h、4h、1h，该产品的利润变为3元/件，试重新确定该公司最优生产计划。设生产工时变化后的新家电的生产量为x2，其中：灵敏度分析举例cj23000CB基bx1x2x3x4x50 x315/2011/215/4-15/22x17/211/201/4-1/21x23/201/20-1/43/2cj-

9、zj03/20-1/4-1/20 x3-90014-242x121001/2-23x23010-1/23cj-zj0001/2-5原问题和对偶问题均为非可行解上表中第二阶段第一行的约束为：x3+4x4-24x5=-9 -x3-4x4+24x5+x6=9替换后重新得表：灵敏度分析举例cj23000-MCB基bx1x2x3x4x5x6-Mx6900-1-42412x121001/2-203x23010-1/230cj-zj00-M1/2-4M-5+24M00 x53/800-1/24-1/611/242x111/410-1/121/601/123x215/8011/800-1/8cj-zj00-5

10、/24-1/30-M+5/24最优生产计划为每天生产11/4台家电，15/8台家电灵敏度分析举例|增加一个约束条件在企业的生产过程中，经常有一些突发事件产生，造成原本不紧缺的某种资源变成为紧缺资源，对生产计划造成影响。若把目前的最优解代入新增加的约束，能满足约束条件，则说明该增加的约束对最优解不构成影响，即不影响最优生产计划的实施。若当前最优解不满足新增加的约束，则应把新的约束添到原问题的最优表内新的一行中去，用对偶单纯形方法来进行迭代，求出新的最优解。|增加一个约束条件灵敏度分析举例例2-11 设家电，经调试后，还需经过一道环境试验工序。家电每件需环境试验3h，家电每件需2h，又环境试验工序

11、每天生产能力为12h。试分析增加该工序后的美佳公司最优生产计划。（1）检验原问题的最优解是否仍适用。将x1=7/2，x2=3/2代入3x1+2x212，27/212，所以不适用。（2）加入松弛变量x6，得3x1+2x2+x6=12（3）单纯形表求解。灵敏度分析举例cj210000CB基bx1x2x3x4x5x60 x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200 x612320001cj-zj000-1/4-1/200 x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200 x6-3/2000-1/4-3/21cj-zj000-1/4-1/200 x3150015/20-52x141001/30-1/31x20010-1/2010 x510001/61-2/3cj-zj000-1/60-1/3注：表中同，=-3-2。作业2.13