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

证明过程省略第一页，共31页。对偶单纯形法找出一个DP的可行基LP是否可行（XB≥0）保持DP为可行解情况下转移到LP的另一个基本解最优解是否循环结束不是求解对偶问题的单纯形法，而是在原始问题的单纯形表中进行对偶处理。即检验数≤0是否b≥0用对偶单纯形表求解条件：（1）找到检验数≤0的对偶单纯形表为初始单纯形表。（2）存在bj<0第二页，共31页。对偶单纯形法例2.9用对偶单纯形法求解：解:（1）转化为标准式。

（2）满足对偶单纯形法求解的基本条件即检验数≤0存在至少一个Bj≤0Ci

≤0第三页，共31页。对偶单纯形法cj-9-12-15000bcBxBx1x2x3x4x5x60x4-2-2-1100-100x5-2-3-1010-120x6-1-1-5001-14(-9/-1.-12/-1.

-15/-5)λj-9-12-1500001.确定出基变量：找出最小的检验数，设为bl，它对应的原问题的基变量即为换出变量。2.确定入基变量，检验数行第四页，共31页。对偶单纯形法cj-9-12-15000bcBxBx1x2x3x4x5x60x4-9/5-9/5010-1/5-36/50x5-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-15000bcBxBx1x2x3x4x5x60x4-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/14第五页，共31页。对偶单纯形法cj-9-12-15000cBxBx1x2x3x4x5x6b-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*=72第六页，共31页。对偶单纯形法找出一个DP的可行基LP是否可行（XB≥0）保持DP为可行解情况下转移到LP的另一个基本解最优解是否循环结束不是求解对偶问题的单纯形法，而是在原始问题的单纯形表中进行对偶处理。即检验数≤0是否b≥0用对偶单纯形表求解条件：（1）找到检验数≤0的对偶单纯形表为初始单纯形表。（2）存在bj<01.确定出基变量：找出最小的检验数，设为bl，它对应的原问题的基变量即为换出变量。2.确定入基变量，3.基变换第七页，共31页。第八页，共31页。第九页，共31页。第十页，共31页。第十一页，共31页。作业2.11第十二页，共31页。线性规划的对偶问题与灵敏度分析线性规划的对偶问题对偶问题的基本性质影子价格对偶单纯形法灵敏度分析参数线性规划第十三页，共31页。灵敏度分析

在生产计划问题的一般形式中，A代表企业的技术状况，b代表企业的资源状况，而C代表企业产品的市场状况，在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。在实际生产过程中，上述三类因素均是在不断变化的，如果按照初始的状况制订了最佳的生产计划，而在计划实施前或实施中上述状况发生了改变，则决策者所关心的是目前所执行的计划还是不是最优，如果不是应该如何修订原来的最优计划。更进一步，为了防止在各类状况发生时，来不及随时对其变化作出反应，即所谓“计划不如变化快”，企业应当预先了解，当各项因素变化时，应当作出什么样的反应。第十四页，共31页。灵敏度分析的步骤灵敏度分析的步骤可归纳如下：1.将参数的改变通过计算反映到最终单纯形表上来。2.检查原问题是否仍为可行解。3.检查对偶问题是否仍为可行解。4.按下表所列情况得出结论或决定继续计算的步骤。原问题对偶问题结论或继续计算的步骤可行解可行解问题的最优解或最优基不变可行解非可行解用单纯形法继续迭代求最优解非可行解可行解用对偶单纯形法继续迭代求最优解非可行解非可行解引进人工变量，编制新的单纯形表重新计算第十五页，共31页。灵敏度分析

CB

XB

CBCN

xj

bXBTXNTCBTXBB-1bB-1BB-1N－Ｚ-CBB-1bCB-CBB-1BCN-CBB-1N若B是最优基，则最优表形式如下灵敏度分析总是在最优表上进行第十六页，共31页。灵敏度分析当系数A，b，C发生改变时，目前最优基是否还最优？为保持目前最优基还是最优，系数A，b，C的允许变化范围是什么？假设每次只有一种系数变化①目标系数C变化基变量系数发生变化；

非基变量系数发生变化；②右端常数b变化③增加一个变量④增加一个约束⑤技术系数A发生变化第十七页，共31页。灵敏度分析举例分析cj的变化例2-7

在第一章例1的美佳公司例子中：（1）若家电Ⅰ的利润降至1.5元/件，而家电Ⅱ的利润增至2元/件时，美佳公司最优生产计划有何变化?cj→1.52000CB基bx1x2x3x4x50x315/2001[5/4]-15/21.5x17/21001/4-1/22x23/2010-1/43/2cj-zj0001/8-9/40x46004/51-61.5x1210-1/5012x23011/500cj-zj00-1/100-3/2即美佳公司随家电Ⅰ，Ⅱ的利润变化应调整为生产2件Ⅰ，生产3件Ⅱ。第十八页，共31页。项目21+λ000CB基bx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21+λx23/2010-1/43/2cj-zj000-1/4+1/4λ-1/2-3/2λ（2）若家电Ⅰ的利润不变，则家电Ⅱ的利润在什么范围内变化时，该公司的最优生产计划将不发生变化？设家电Ⅱ的利润为（1+λ）元，如下为保证最优解，-1/4+1/4λ≤0，-1/2-3/2λ

≤0解得-1/3≤λ≤1即家电Ⅱ的利润c2的变化范围应满足2/3≤c2≤2灵敏度分析举例第十九页，共31页。分析bi的变化例2-8

在美佳公司的例子中：（1）若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32h，分析公司最优计划的变化；灵敏度分析举例cj→21000CB基bx1x2x3x4x50x335/20015/4-15/22x111/21001/4-1/21x2-1/2010[-1/4]3/2cj-zj000-1/4-1/20x315051002x15110010x420-401-6cj-zj0-100-2第二十页，共31页。灵敏度分析举例例2-8

（2）设设备A和设备B每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变。设调试工序每天可用能力为（5+λ）h，因有最终单纯形表中b列数字为因b>0时最优基不变，故-1≤λ≤1。调试工序的能力应在4h~6h之间。第二十一页，共31页。增加一个变量xj的分析若企业在计划期内，有新的产品可以生产，则在知道新产品的单位利润，单件资源消耗量时，可以在最优表中补充一列，其中的前m行可以由基矩阵的逆矩阵得到，而检验数行也可以由与其它列相同的方法计算得到。若检验数非正，则原最优解仍为最优，原生产计划不变，不生产这种新产品；否则，当检验数为正时，则应以该变量进基，作单纯形迭代，从而找出新的最优解。第二十二页，共31页。例2-9

设美佳公司又计划推出新型号的家电Ⅲ，生产一件所需设备A、B及调试工序的时间分别为3h、4h、2h，该产品的预期盈利为3元/件，试分析该产品是否值得投产；如投产，对该公司的最优生产计划有何影响。设生产x6件家电Ⅲ，有c6=3，P6=（3，4，2）T灵敏度分析举例增加一个变量xj的分析第二十三页，共31页。灵敏度分析举例cj→210003CB基bx1x2x3x4x5x60x315/20015/4-15/2-72x17/21001/4-1/201x23/2010-1/43/2[2]cj-zj000-1/4-1/210x351/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件家电Ⅲ。第二十四页，共31页。灵敏度分析举例分析参数aij的变化例2-10在美佳公司的例子中，若家电Ⅱ每件需设备A,B和调试工时变为8h、4h、1h，该产品的利润变为3元/件，试重新确定该公司最优生产计划。设生产工时变化后的新家电Ⅱ的生产量为x2′，其中：第二十五页，共31页。灵敏度分析举例cj→23000CB基bx1x2′x3x4x50x315/2011/215/4-15/22x17/211/201/4-1/21x23/20[1/2]0-1/43/2cj-zj03/20-1/4-1/20x3-90014-242x121001/2-23x2′3010-1/23cj-zj0001/2-5原问题和对偶问题均为非可行解第二十六页，共31页。上表中第二阶段第一行的约束为：x3+4x4-24x5=-9-x3-4x4+24x5+x6=9替换后重新得表：灵敏度分析举例cj→23000-MCB基bx1x2′x3x4x5x6-Mx6900-1-4[24]12x121001/2-203x2′3010-1/230cj-zj00-M1/2-4M-5+24M00x53/800-1/24-1/611/242x111/410-1/121/601/123x2′15/8011/800-1/8cj-zj00-5/24-1/30-M+5/24最优生产计划为每天生产11/4台家电Ⅰ，15/8台家电Ⅱ第二十七页，共31页。灵敏度分析举例增加一个约束条件在企业的生产过程中，经常有一些突发事件产生，造成原本不紧缺的某种资源变成为紧缺资源，对生产计划造成影响。若把目前的最优解代入新增加的约束，能满足约束条件，则说明该增加的约束对最优解不构成影响，即不影响最优生产计划的实施。若当前最优解不满足新增加的约束，则应把新的约束添到原问题的最优表内新的一行中去，用对偶单纯形方法来进行迭代，求出新的最优解。第二十八页，共31页。增加一个约束条件灵敏度分析举例例2-11

设家电Ⅰ，Ⅱ经调试后，还需经过一道环境试验工序。家电Ⅰ每件需环境试验3h，家电Ⅱ每件需2h，又环境试验工序每天生产能力为12h。试分析增加该工序后的美佳公司最优生产计划。（1）检验原问题的最优解是否仍适用。将x1=7/2，