运筹学 对偶与灵敏度分析幻灯片.ppt

运筹学 对偶与灵敏度分析第1页，共20页，编辑于2022年，星期三对偶模型的一般式以例1.7为例，原问题为（P）（D）这是最常见的对偶模型形式，称为对称式对偶模型。二者间具有十分对称的对应关系：原问题（P）对偶问题（D）目标max型 目标min型 有n个变量（非负）有n个约束（大于等于）有m个约束（小于等于）有m个变量（非负）价格系数 资源向量 资源向量 价格系数 技术系数矩阵 技术系数矩阵的转置第2页，共20页，编辑于2022年，星期三此外，还有一种情形 原问题（P）对偶问题（D）第j个变量为自由变量 第j个约束为等式约束 第i个约束为等式约束 第i个变量为自由变量例1.8：写出下面线性规划的对偶规划模型：第3页，共20页，编辑于2022年，星期三例1.8：写出下面线性规划的对偶规划模型：第4页，共20页，编辑于2022年，星期三二、对偶的性质（P）（D）考虑1.对称性 （P）与（D）互为对偶。证：由（P）、（D）的约束可得几何意义：CXYb第5页，共20页，编辑于2022年，星期三4.对偶定理 若（P）有最优解，则（D）也有最优解，且最优值相同。证：对（P）增加松弛变量Xs，化为设其最优基为B，终表为其检验数为第6页，共20页，编辑于2022年，星期三问题：(1)由性质4可知，对偶问题最优解的表达式 Y*=？(2)求Y*是否有必要重新求解（D）？CBB-1 不必。可以从原问题（P）的单纯形终表获得。例如，在前面的练习中已知的终表为请指出其对偶问题的最优解和最优值。第7页，共20页，编辑于2022年，星期三5.互补松弛定理第8页，共20页，编辑于2022年，星期三6.对偶问题的经济解释（1）对偶最优解的经济解释资源的影子价格（Shadow Price）CBB-1 对偶问题的最优解 买主的最低出价；原问题资源的影子价格 当该资源增加1单 位时引起的总收入的增量卖主的内控价格。例1.10：例1.1（煤电油例）的单纯形终表如下：（1）请指出资源煤电油的影子价格，并解释其经济意义。（2）由单纯形终表还可得到哪些有用的信息？第9页，共20页，编辑于2022年，星期三例1.10：例1.1（煤电油例）的单纯形终表如下：（1）请指出资源煤、电、油的影子价格，并解释其经济意义。（2）由单纯形终表还可得到哪些有用的信息？解：（1）煤、电、油的影子价格分别是0、1.36、0.52；其经济意义是当煤、电、油分别增加1单位时可使总 收入分别增加0、1.36、0.52。（2）由单纯形终表还可得到：原问题的最优生产计划、最大收入、资源剩余，对偶问题的最低购买价格、最少的购买费用等。第10页，共20页，编辑于2022年，星期三 在利润最大化的生产计划中（1）影子价格大于0的资源没有剩余；（2）有剩余的资源影子价格等于0；（3）安排生产的产品机会成本等于利润；（4）机会成本大于利润的产品不安排生产。（2）互补松弛关系的经济解释第11页，共20页，编辑于2022年，星期三三、灵敏度分析 讨论模型的系数或变量发生小的变化时对解的影响（如它们在何范围内变化时可使原最优解或最优基不变？）我们主要讨论C、b和变量结构变化时对解的影响。对解怎样影响？影响解的-最优性 -可行性第12页，共20页，编辑于2022年，星期三1.b变化时的分析第13页，共20页，编辑于2022年，星期三2.C变化时的分析第14页，共20页，编辑于2022年，星期三3.增加新变量时的分析 主要讨论增加新变量xn+1是否有利。经济意义是第n+1种新产品是否应当投产，数学意义是xn+1是否应进基。经济意义：市场价影子价第15页，共20页，编辑于2022年，星期三例1.11：在例1.1（煤电油例）中，其单纯形终表如下：（1）电的影子价格是多少？使最优基仍适用的电的变 化范围为何？（2）若有人愿以每度1元的价格向该厂供应25度电，是 否值得接受？（3）甲产品的价格在何范围内变化时，现最优解不变？（4）若现又考虑一新产品丙，其资源单耗为10，2，5，售价为6.5，问该产品是否可投产？第16页，共20页，编辑于2022年，星期三例1.11：在例1.1（煤电油例）中，其单纯形终表如下：（1）电的影子价格是多少？使最优基仍适用的电的变 化范围为何？解：（1）电的影子价格是1.36。第17页，共20页，编辑于2022年，星期三例1.11：在例1.1（煤电油例）中，其单纯形终表如下：（2）若有人愿以每度1元的价格向该厂供应25度电，是 否值得接受？解：（2）值得。因25在B的适用范围内（即影子价格适用），且 1.36-1.000。第18页，共20页，编辑于2022年，星期三例1.11：在例1.1（煤电油例）中，其单纯形终表如下：（3）甲产品的价格在何范围内变化时，现最优解不变？解：甲产品的价格c1是基变量的价格系数。第19页，共20页，编辑于2022年，星期三例1.11：在例1.1（煤电油例）中，其单纯形终表如下：（4）若现又考虑一新产品丙，其资源单耗为10，2，5，售价为6.5，问该产品是否可投产？故丙产品可以投产。第20页，共20页，编辑于2022年，星期三