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

《物流运筹学(第10节-对偶单纯形法)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、化为标准式。（2）满足对偶单纯形法求解的基本条件即检验数≤0存在至少一个Bj≤0Ci≤0对偶单纯形法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.确定入基变量，检验数行对偶单纯形法cj-9-12-15000bcBxBx1x2x3x4x5x60x4-9/5-9/5010-1/5-36/50x5-9/5-14/50

3、01-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对偶单纯形法cj-9-12-15000cBxBx1x2x3x4x5x6b-9x1100-14/911/92-12x20101-102-15x300

4、11/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对偶单纯形法找出一个DP的可行基LP是否可行（XB≥0）保持DP为可行解情况下转移到LP的另一个基本解最优解是否循环结束不是求解对偶问题的单纯形法，而是在原始问题的单纯形表中进行对偶处理。即检验数≤0是否b≥0用对偶单纯形表求解条件：（1）找到检验数≤0的对偶单纯形表为初始单纯形表。（2）存在bj<01.确定出基变量：找出最小的检验数，设为bl，它对应的原问题的基变量即为换出变量。2.确定入基变量，

5、3.基变换作业2.11线性规划的对偶问题与灵敏度分析线性规划的对偶问题对偶问题的基本性质影子价格对偶单纯形法灵敏度分析参数线性规划灵敏度分析在生产计划问题的一般形式中，A代表企业的技术状况，b代表企业的资源状况，而C代表企业产品的市场状况，在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。在实际生产过程中，上述三类因素均是在不断变化的，如果按照初始的状况制订了最佳的生产计划，而在计划实施前或实施中上述状况发生了改变，则决策者所关心的是目前所执行的计划还是不是最优，如果不是应该如何修订原来的最优计划。更进一步，为了防止在各类状况发生时，

6、来不及随时对其变化作出反应，即所谓“计划不如变化快”，企业应当预先了解，当各项因素变化时，应当作出什么样的反应。灵敏度分析的步骤灵敏度分析的步骤可归纳如下：1.将参数的改变通过计算反映到最终单纯形表上来。2.检查原问题是否仍为可行解。3.检查对偶问题是否仍为可行解。4.按下表所列情况得出结论或决定继续计算的步骤。原问题对偶问题结论或继续计算的步骤可行解可行解问题的最优解或最优基不变可行解非可行解用单纯形法继续迭代求最优解非可行解可行解用对偶单纯形法继续迭代求最优解非可行解非可行解引进人工变量，编制新的单纯形表重新计算灵敏度分析CBXBCBCNxjbXBTXNTCB

7、TXBB-1bB-1BB-1N－Ｚ-CBB-1bCB-CBB-1BCN-CBB-1N若B是最优基，则最优表形式如下灵敏度分析总是在最优表上进行灵敏度分析当系数A，b，C发生改变时，目前最优基是否还最优？为保持目前最优基还是最优，系数A，b，C的允许变化范围是什么？假设每次只有一种系数变化①目标系数C变化基变量系数发生变化；非基变量系数发生变化；②右端常数b变化③增加一个变量④增加一个约束⑤技术系数A发生变化灵敏度分析举例分析cj的变化例2-7在第一章例1的美佳公司例子中：（1）若家电Ⅰ的利润降至1.5元/件，而家电Ⅱ的利润增至2元/件时，美佳公司最优生产计划有何