运筹学：第2章 对偶理论与灵敏度分析

1、第二章 对偶理论与灵敏度分析2.1 对偶问题 凡是一个线性规划都对应一个对偶线性规划凡是一个线性规划都对应一个对偶线性规划2.2 对偶理论2.3 对偶单纯形法 新的算法（大新的算法（大M，二阶段），二阶段）2.4 对偶问题的最优解2.5 灵敏度分析 对线性规划参数动态分析对线性规划参数动态分析2.6 影子价格2.1对偶问题 思路：（1）从应用出发引入对偶问题（2）介绍任意线性规划对偶问题 【例】 某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗和各种资源的限制量，如表所示。该工厂每生产一件产品可获利2元，每生产一件产品可获利3元，问应如何安排计划使该

2、工厂获利最多？资源限量设 备128台时原材料A4016kg原材料B0412kg 对上例，假设该工厂的决策者决定不生产产品、，而将其所有资源出租或外售。这时工厂的决策者如何给每种资源定价？ 对比 例例2-12-1（营养问题）某养鸡场所用的混合饲料由（营养问题）某养鸡场所用的混合饲料由n n种天然饲料种天然饲料配合而成。要求在这批配合饲料中必须含有配合而成。要求在这批配合饲料中必须含有m m种不同的营养成种不同的营养成分，且第分，且第i i种营养成分的含量不低于种营养成分的含量不低于b bi i已知第已知第i i种营养成分种营养成分在每单位第在每单位第j j种天然饲料中的含量为种天然饲料中的含量为

3、a aijij. . 每单位第每单位第j j种天然饲种天然饲料的价格为料的价格为c cj j试问试问: :应如何对这应如何对这n n种饲料配方，使这批饲料种饲料配方，使这批饲料的费用最小的费用最小? ?（P）中第）中第i个约束条件，对应（个约束条件，对应（D）中第）中第i个变量；个变量；（P）中第）中第j个变量，对应（个变量，对应（D）中第）中第j个约束条件个约束条件记住矩阵表示对偶问题（对偶问题（D）的对偶问题即为原有问题（）的对偶问题即为原有问题（P），定理），定理2-1。思路：一般线性规划均整理成（思路：一般线性规划均整理成（P）或（）或（D）的形式，）的形式，然后求对偶规划。然后求对偶

4、规划。在对偶问题（在对偶问题（D）中，原有问题（）中，原有问题（P）中的等式约束对应）中的等式约束对应的变量的变量u1为自由变量；为自由变量；（P）中的自由变量）中的自由变量x2对应的约束条件为等式约束。对应的约束条件为等式约束。总结：任意一般线性规划（总结：任意一般线性规划（P）的对偶问题（）的对偶问题（D）定义）定义 书上书上59页页2-5，2-6（P）（D）以后不需要再将（以后不需要再将（P）中等式约束一拆为二，）中等式约束一拆为二，直接进行转换！直接进行转换！回顾书上本节内容。2.2 对偶理论 对标准型线性规划及其对偶问题之间关系对标准型线性规划及其对偶问题之间关系进行讨论，结论对一般

5、形式的线型规划进行讨论，结论对一般形式的线型规划（P）及其对偶问题及其对偶问题（D）同样适用同样适用。极大化问题可行解的目标函数极大化问题可行解的目标函数 不超过不超过极小化问题可行解的目标函数极小化问题可行解的目标函数 极大化问题可行解的目标函数极大化问题可行解的目标函数不超过不超过极小化问题可行解的目标函数极小化问题可行解的目标函数 （1）（3）书上书上64页页 作业： 92页1，2，3（P）在可行域内无上界，则对偶问题不可行。其他教材中有交待，本教材这样介绍的目的是为了给影子价格的讲解作铺垫。其他教材中有交待，本教材这样介绍的目的是为了给影子价格的讲解作铺垫。 总结原有问题（P）和对偶问

6、题（D）之间的对应关系。 64页表2-1。 Kp， KD ，f, z2.3对偶单纯形法2.3对偶单纯形法P67 对偶单纯形法原理单纯形法特点1.确定进基变量t (r0)2.确定出基变量k（最小比原则）3.f0不断下降1.确定出基变量k ( 0)2.确定进基变量t（最大比原则）3.f0不断上升（此时X不是可行解）(单纯形因子是对偶问题可行解。)对偶单纯形法特点B为原有可行基B为对偶可行基min0,1kiitktitbbyimyy max0,jtkjDktkjrryjIyyb 书上第67页（2-13） 书上第68页定理2-5 书上第68页单纯形法算法第一张表必须检验数非负第一张表必须检验数非负,

7、可正可负。可正可负。目标函数系数非负，为灵敏度分析和整数规划问题子程序目标函数系数非负，为灵敏度分析和整数规划问题子程序br=0 情况2.3对偶单纯形法 对偶单纯形法和大对偶单纯形法和大M M法一样都是求解极小化法一样都是求解极小化LPLP的算法。与其算法名称无关。的算法。与其算法名称无关。 第一张表必须检验数非负。第一张表必须检验数非负。 用对偶单纯形法求解的模型里用对偶单纯形法求解的模型里没有人工变没有人工变量量，只有剩余变量和松弛变量。，只有剩余变量和松弛变量。2.4对偶问题的最优解 本节目的：在求本节目的：在求P的同时，的同时，给出给出D的最优解的最优解看书73页，情况三 作业：93页

8、7，82.5 灵敏度分析 目的：对线性规划某些参数进行动态分析，为什么进行分析，怎么分析呢？目的：对线性规划某些参数进行动态分析，为什么进行分析，怎么分析呢？jjcc 属于72页情况二（P）类型是个静态问题是个静态问题最优值的变化？最优值的变化？2.5.1参数Cs的灵敏度分析 无影响X1为非基本变量为非基本变量X2为基本变量为基本变量改变量变化范围改变量变化范围目标函数最优值有何变化？目标函数最优值有何变化？受到影响的是？受到影响的是？X2为基本变量为基本变量目标函数最优值有何变化？目标函数最优值有何变化？“灵敏度分析的一般公式灵敏度分析的一般公式 仅影响仅影响rs基本变量在第基本变量在第 i

9、 行行f0 和和 非基本变量的检验数非基本变量的检验数 均受到影响均受到影响如果三个均为正如果三个均为负2.5.2参数bs的灵敏度分析2.5.2参数bs的灵敏度分析 sssbbb 令 s sbbbe 在哪里？73页2-18 B ：（A.2, A.3, A.6 ） B-1： （y4, y5, y6）请回答：最优解？最优值？请回答：最优解？最优值？ x2x3x6-4-30请回答：最优解？请回答：最优解？最优值？最优值？ -1000，用什么方法求解？，用什么方法求解？可见：对偶单纯形法是灵敏度分析的子程序。可见：对偶单纯形法是灵敏度分析的子程序。 作业：94页9 （1）要求用公式法和推导法两种办法解题 （2）用第一种方法b1求b1请同学直接回答？请同学直接回答？最优值的变化？最优值的变化？Cs摄动bs摄动11sissi