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

《物流运筹学(第10节-对偶单纯形法).ppt》由会员分享，可在线阅读，更多相关《物流运筹学(第10节-对偶单纯形法).ppt（32页珍藏版）》请在三一办公上搜索。

1、对偶单纯形法,对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。不是求解对偶问题的单纯形法，而是在原始问题的单纯形表中进行对偶处理。,对偶单纯形法原理,证明过程省略,对偶单纯形法,找出一个DP的可行基,LP是否可行（XB 0）,保持DP为可行解情况下转移到LP的另一个基本解,最优解,是,否,循环,结束,不是求解对偶问题的单纯形法，而是在原始问题的单纯形表中进行对偶处理。,即检验数0,是否b0,用对偶单纯形表求解条件：（1）找到检验数0的对偶单纯形表为初始单纯形表。（2）存在bj0,对偶单纯形法,例2.9 用对偶单纯形法求解：,解:（1

2、）转化为标准式。（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的另一个基本解,最优解,是,否,循环,结束,不是求解对偶问题的单纯形法，而是在原始问题的单纯形表中进行对偶处理。,即检验数0,

3、是否b0,用对偶单纯形表求解条件：（1）找到检验数0的对偶单纯形表为初始单纯形表。（2）存在bj0,1.确定出基变量：找出最小的检验数，设为bl，它对应的原问题的基变量即为换出变量。,2.确定入基变量，,3.基变换,作业,2.11,线性规划的对偶问题与灵敏度分析,线性规划的对偶问题对偶问题的基本性质影子价格对偶单纯形法灵敏度分析参数线性规划,灵敏度分析,在生产计划问题的一般形式中，A代表企业的技术状况，b代表企业的资源状况，而C代表企业产品的市场状况，在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。在实际生产过程中，上述三类因素均是在不断变化的，如果按照初始的

4、状况制订了最佳的生产计划，而在计划实施前或实施中上述状况发生了改变，则决策者所关心的是目前所执行的计划还是不是最优，如果不是应该如何修订原来的最优计划。更进一步，为了防止在各类状况发生时，来不及随时对其变化作出反应，即所谓“计划不如变化快”，企业应当预先了解，当各项因素变化时，应当作出什么样的反应。,灵敏度分析的步骤,灵敏度分析的步骤可归纳如下：1.将参数的改变通过计算反映到最终单纯形表上来。2.检查原问题是否仍为可行解。3.检查对偶问题是否仍为可行解。4.按下表所列情况得出结论或决定继续计算的步骤。,灵敏度分析,若B是最优基，则最优表形式如下,灵敏度分析总是在最优表上进行,灵敏度分析,当系数

5、A，b，C发生改变时，目前最优基是否还最优？为保持目前最优基还是最优，系数A，b，C的允许变化范围是什么？假设每次只有一种系数变化目标系数C变化 基变量系数发生变化；非基变量系数发生变化；右端常数b变化增加一个变量增加一个约束技术系数A发生变化,灵敏度分析举例,分析cj的变化例2-7 在第一章例1的美佳公司例子中：（1）若家电的利润降至1.5元/件，而家电的利润增至2元/件时，美佳公司最优生产计划有何变化?,即美佳公司随家电，的利润变化应调整为生产2件，生产3件。,（2）若家电的利润不变，则家电的利润在什么范围内变化时，该公司的最优生产计划将不发生变化？设家电的利润为（1+）元，如下,为保证最

6、优解，-1/4+1/40，-1/2-3/2 0解得-1/3 1即家电的利润c2的变化范围应满足2/3 c2 2,灵敏度分析举例,分析bi的变化例2-8 在美佳公司的例子中：（1）若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32h，分析公司最优计划的变化；,灵敏度分析举例,灵敏度分析举例,例2-8（2）设设备A和设备B每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变。设调试工序每天可用能力为（5+）h，因有,最终单纯形表中b列数字为,因b0时最优基不变，故-11。调试工序的能力应在4h6h之间。,增加一个变量xj的分析 若企业在计划期内，有新的产品可以生产，则在

7、知道新产品的单位利润，单件资源消耗量时，可以在最优表中补充一列，其中的前m行可以由基矩阵的逆矩阵得到，而检验数行也可以由与其它列相同的方法计算得到。若检验数非正，则原最优解仍为最优，原生产计划不变，不生产这种新产品；否则，当检验数为正时，则应以该变量进基，作单纯形迭代，从而找出新的最优解。,例2-9 设美佳公司又计划推出新型号的家电，生产一件所需设备A、B及调试工序的时间分别为3h、4h、2h，该产品的预期盈利为3元/件，试分析该产品是否值得投产；如投产，对该公司的最优生产计划有何影响。设生产x6件家电，有c6=3，P6=（3，4，2）T,灵敏度分析举例,增加一个变量xj的分析,灵敏度分析举例

8、,最优生产计划应为每天生产7/2件家电，51/4件家电。,灵敏度分析举例,分析参数aij的变化,例2-10 在美佳公司的例子中，若家电每件需设备A,B和调试工时变为8h、4h、1h，该产品的利润变为3元/件，试重新确定该公司最优生产计划。设生产工时变化后的新家电的生产量为x2，其中：,灵敏度分析举例,原问题和对偶问题均为非可行解,上表中第二阶段第一行的约束为：x3+4x4-24x5=-9-x3-4x4+24x5+x6=9替换后重新得表：,灵敏度分析举例,最优生产计划为每天生产11/4台家电，15/8台家电,灵敏度分析举例,增加一个约束条件在企业的生产过程中，经常有一些突发事件产生，造成原本不紧

9、缺的某种资源变成为紧缺资源，对生产计划造成影响。若把目前的最优解代入新增加的约束，能满足约束条件，则说明该增加的约束对最优解不构成影响，即不影响最优生产计划的实施。若当前最优解不满足新增加的约束，则应把新的约束添到原问题的最优表内新的一行中去，用对偶单纯形方法来进行迭代，求出新的最优解。,增加一个约束条件,灵敏度分析举例,例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,