《线性规划对偶理论(含影子价格)-21136.》由会员分享，可在线阅读，更多相关《线性规划对偶理论(含影子价格)-21136.（46页珍藏版）》请在金锄头文库上搜索。
1、线性规划的对偶理论线性规划的对偶理论 对偶的定义 对偶问题的性质 对偶的经济解释 SUES 本章重点本章重点 1、掌握写出对偶问题的方法，原问题与其对偶 问题的对应关系 2、掌握对偶问题的基本理论和性质 3、理解影子价格的定义和意义 4、理解并掌握对偶单纯形方法的思想和步骤 5、掌握线性规划灵敏度分析 (1) 资源数量 bi 发生变化的分析 (2) 目标函数中价值系数 cj 发生变化的分析 难点难点 难点难点 对偶原理对偶原理 对偶问题概念： 任何一个线性规划问题都有一个与之相对应 的线性规划问题，如果前者称为原始问题，后者 就称为“对偶”问题。 对偶问题是对原问题从另一角度进行的描述 其最优
2、解与原问题的最优解有着密切的联系，在 求得一个线性规划最优解的同时也就得到对偶线 性规划的最优解，反之亦然。 对偶理论就是研究线性规划及其对偶问题的 理论，是线性规划理论的重要内容之一。 问题的导出问题的导出 ABC拥有量 工 时 1113 材 料 1479 单件利润 233 ABC拥有量 工 时 1113 材 料 1479 单件利润 233 假设有客户提出要求，购买工厂所拥有的 工时和材料，为客户加工别的产品，由客 户支付工时费和材料费。那么工厂给工时 和材料制订的最低价格应是多少，才值得 出卖工时和材料 ? ABC拥有量 工 时 1113 材 料 1479 单件利润 233 出卖资源获利应
3、不少于生产产品的获利; 约束 价格应该尽量低，这样，才能有竞争力; 目标 价格应该是非负的 ABC拥有量 工 时 1113 材 料 1479 单件利润 233 用y1和y2分别表示工时和材料的出售价格 总利润最小 min W=3y1+9y2 保证A产品利润 y1+y22 保证B产品利润 y1+4y23 保证C产品利润 y1+7y23 售价非负 y10 y20 ABC拥有量 工 时 1113 材 料 1479 单件利润 233 对对 偶偶 问问 题题 的的 定定 义义 对 称 形 式 的 对 偶 问 题 对偶的定义对偶的定义 原始问题 min f(x)=CTX s.t.AXb X 0 对偶问题
4、max z(y)=bTy s.t. ATyC y 0 min bA CT CAT bT max m n m n 对偶问题的特点 l（1）目标函数在一个问题中是求最大值在 另一问题中则为求最小值 l（2）一个问题中目标函数的系数是另一个 问题中约束条件的右端项 l（3）一个问题中的约束条件个数等于另一 个问题中的变量数 l（4）原问题的约束系数矩阵与对偶问题的 约束系数矩阵互为转置矩阵 一般 线性规 划问题 的对偶 问题 对偶问题对应表 原问题（对偶问题）对偶问题（原问题） 目标函数min目标函数max 约束条件： m个 第i个约束类型为“” 第i个约束类型为“” 第i个约束类型为“” 变量数：
5、 m个 第i个变量0 第i个变量0 第i个变量是自由变量 变量数：n个 第j个变量 0 第j个变量 0 第j个变量是自由变量 约束条件：n个 第j个约束类型为“” 第j个约束类型为“” 第j个约束类型为“” 例 写出如下LP问题的对偶问题 对偶问题 对偶问题的性质 1、对偶的对偶就是原始问题 max z=-CTX s.t. -AX-b X 0 min y=-bTW s.t. -ATW-C W 0 max y=bTW s.t. ATWC W 0 min z=CTX s.t. AXb X 0 对偶的定义 对偶的定义 2、对偶问题的性质 （1）弱对偶性（可行解的目标函数值之间的关系） 设X、Y分别是
6、原始问题和对偶问题的可行解 cjxjbiyi （3）最优性 （2）无界性 如果原问题（对偶问题）具有无界解， 则其对偶问题（原问题）无可行解。 无界性 在一对对偶问 题，若其中一个问题可行 但目标函数无界，则另一 个问题不可行；反之不成 立。这也是对偶问题的无 界性。 关于无界性有如下结论： 问题无界 无可 行解 无可行解 无可行解 问题无界 对偶问题原问题 无界 如： （原） 无可 行解 （对） 已知 试用对偶理论证明原问题无界。 解： =（0.0.0）是 原问题的一个可行解，而 对偶 问题 的第一个约束条件不能成立（因为y1 , y2 0)。因 此，对偶问题不可行，可知，原问题无界。 （4
7、）强对偶性（最优解的目标函数之间的关系） 如果原问题有最优解，则其对偶问题也一定有 最优解，且两者的目标函数值相等 在线性规划问题的最优解中， 如果对应某一约束条件的对偶变量值为非零， 则该约束条件取严格等式； 反之如果约束条件取严格不等式， 3 3、互补松弛性互补松弛性 则其对应的对偶变量一定为零。 即 解：先写出它的对偶问题 l练习 已知线性规划问题 影子价格对偶的经济解释 1、原始问题是利润最大化的生产计划问题 单位产品的利润 产品产量 总利润 资源限量 单位产品消耗的资源 剩余的资源 消耗的资源 2、对偶问题 资源限量 资源价格 总利润 对偶问题是资源定价问题，对偶问题的最优解w1、w
8、2、 .、wm称为m种资源的影子价格（Shadow Price） 原始和对偶问题都取得最优解时，最大利润 max z=min y 3、资源影子价格的性质 影子价格越大，说明这种资源越是相对紧缺 影子价格越小，说明这种资源相对不紧缺 如果最优生产计划下某种资源有剩余，这种资源 的影子价格一定等于0 w1 w2 wm 4、产品的机会成本 机会成本 表示减少一件产品所节省的资源可以增加的利润 增加单位资源可以增加的利润 减少一件产品可以节省的资源 THE ENDTHE END 对偶单纯形法对偶单纯形法 l对偶单纯形法的原理 l对偶单纯形法的应用步骤 l对偶单纯形法举例 l对偶单纯形法的应用条件 l对
9、偶单纯形法的优点和缺点 对偶单纯形法原理对偶单纯形法原理 l对偶单纯形法并不是求解对偶问题解的方法 ，而是利用对偶理论求解原问题的解的方法 。 l单纯形法是在原问题可行的基础上，通过迭 代使对偶问题达到可行，从而得到最优解。 根据对偶问题的对称性，若原问题不可行而 对偶问题可行，那么在保持对偶问题可行的 基础上，逐步迭代使原问题达到可行，也可 得到最优解。 对于标准线性规划问题： 可行基B 若B对应的基本解是可行解 最优基B 若B对应的基本解是最优解 对偶可行基B 若CBB-1是对偶问题可行解 即 C-CBB-1A0 或 检验数0 最优基B 可行基B 对偶可行基B 单纯形法 可行基B 保持可行
10、性 对偶可行基B 对偶单纯形法 可行基B 保持对偶可行性 对偶可行基B 对偶单纯形法应用条件对偶单纯形法应用条件 应用前提： 有一个基，其对应的基满足: 单纯形表的检验数行全部非正（对偶 可行）； 变量取值可有负数（非可行解）。 对偶单纯形法步骤对偶单纯形法步骤 l找一个基（可以不是可行的），建立初始对偶 单纯形表，检验数全部非负； l若b列元素非负，则已经是最优基。反之，则 取相应行的基变量为出基变量； l为保证能对基的可行性有所改进，则将来的主 元应该为负数；为保证下一个基还能是对偶可 行基，应使检验数仍为非负的。 l主元变换 例题:用对偶单纯形法求解 解:将上述模型转化为 cj-9-12
11、-15000 cBxBbx1x2x3x4x5x6 0x4-10-2-2-1100 0x5-12-2-3-1010 0x6-14-1-1-5001(-9/-1.-12/-1. -15/-5) cj -Z 0-9-12-15000 列初始单纯形表，取b中比较小的行对应的变量为 换出基变量。 cj-9-12-15000 cBxBbx1x2x3x4x5x6 0x4-36/5-9/5-9/5010-1/5 0x5-46/5-9/5-14/5001-1/5 -15x314/51/51/5100-1/5 (-30/-9.-45/-14 .-15/-1) -Z 42-6-9000-3 cj-9-12 -150
12、00 cBxBbx1x2x3x4x5x6 0x4-9/7- 9/14 001-9/14-1/14 -12x223/79/14100-5/141/14 (-3/-9.-45/-9. -33/- 1) -15x315/71/140101/14-3/14 -Z 501/7- 3/14 000- 45/14 - 33/14 cj-9-12-15000 cBxBbx1x2x3x4x5x6 -9x12100-14/911/9 -12 x220101-10 -15 x320011/90- 2/9 -Z 72000-1/3-3- 7/3 所以， X*=（2 . 2 . 2 . 0 . 0 . 0） Z* =7
13、2， 原问题 Z* =72 其对偶问题的最优解为： Y*= (1/3 . 3 . 7/3)，W*= 72 对偶单纯形法的优点和缺点对偶单纯形法的优点和缺点 优点： l 初始解可以是非可行解，当检验数都为负数时，就 可以进行基的变换，不需要加入人工变量。 l 当变量多于约束条件，用对偶单纯形法计算可以减 少计算工作量，因此对于变量较少，而约束条件很多 的线性规划问题，可以首先将它变换成为对偶问题， 然后用对偶单纯形法来求解。 l 在灵敏度分析中，有时需要使用对偶单纯形法，这 样可以使问题处理简化。 l缺点：对于大多数的线性规划问题，很 难找到一个初始可行基，因而这个方法 在求解线性规划问题时很少单独应用。 l单纯形法是在基本可行解中寻找满足最优性 条件（简约价值系数非负）的最优解 l对偶单纯形法则是在所有满足最优性条件（ 简约价值系数非负）的最优解中寻找满足可 行的最优解 单纯形法与对偶单纯形法 对偶单纯形法与单纯形法的区别 补充 是 是 是是 否否 否否 所有所有 得到 最优解 计算计算 典式对应原规划的 基本解是可行的 典式对应原规划的基 本解的检验数 所有所有 计算计算 以为中心元素进行迭代以为中心元素进行迭代 停 没 有 最 优 解 没 有 最 优 解 单纯形法对偶单纯形法
