第三章对偶问题与灵敏度分析 要求: 了解LP对偶问题的实际背景 了解对偶问题的建立规则与基本性质 掌握对偶最优解的计算及其经济解释 掌握LP的灵敏度分析 理解计算机输出的影子价格与灵敏度分 析的内容 ORI
OR1 1 第三章 对偶问题与灵敏度分析 要求： 了解LP对偶问题的实际背景 了解对偶问题的建立规则与基本性质 掌握对偶最优解的计算及其经济解释 掌握LP的灵敏度分析 理解计算机输出的影子价格与灵敏度分 析的内容
3.1对偶问题 ◆3.1.1对偶问题的提出 回顾例题1:现在A、B两产品销路不畅,可以 将所有资源出租或外卖,现在要谈判,我们的价 格底线是什么? 产品A产品B资源限制 劳动力 360 设备 943 200 原材料 10 300 单位利润70 120 ORI
OR1 2 3.1 对偶问题 3.1.1 对偶问题的提出 回顾例题1： 现在A、B两产品销路不畅，可以 将所有资源出租或外卖，现在要谈判，我们的价 格底线是什么？ 产品A 产品B 资源限制 劳动力 设备 原材料 9 4 3 4 5 10 360 200 300 单位利润 70 120
对偶模型 ◆设每个工时收费Y1元,设备台时费用Y2 元,原材料附加费Y3元 出租收入不低于生产收入: 9y1+4y2+3y3>70 4y1+5y2+10y3>120 目标:=360y+200y2+300 出租收入越多越好?至少不低于某数 ORI 3
OR1 3 对偶模型 设每个工时收费Y1元，设备台时费用Y2 元，原材料附加费Y3元。 出租收入不低于生产收入： 9y1+4y2+3y3 ≥70 4y1+5y2+10y3 ≥120 目标：ω=360y1+200y2+300y3 出租收入越多越好？至少不低于某数
原问题与对偶问题之比较 原问题 对偶问题: maxZ=70X1+120X2minO=360y1+200V2+3003 9X1+4X270 4x1+5X2≤200(3.1)4y1+5y2+10y3>120(3.2) 3X1+10X20 X1>0X2>0 ORI
OR1 4 原问题与对偶问题之比较 原问题： 对偶问题： maxZ=70X1+120X2 minω=360y1+200y2+300y3 9X1+4X2≤360 9y1+4y2+3y3 ≥70 4X1+5X2 ≤200 (3.1) 4y1+5y2+10y3 ≥120 (3.2) 3X1+10X2 ≤300 y1 ≥0, y2 ≥0, y3 ≥0 X1≥0 X2≥0
3.1.2对偶规则 原问题一般模型:对偶问题一般模型: maxZ=CX min o=yb aX C X>0 Y>0 ORI 5
OR1 5 3.1.2对偶规则 原问题一般模型： 对偶问题一般模型： maxZ=CX min ω=Yb AX ≤b YA ≥C X ≥0 Y ≥0
对偶规则 ◆原问题有m个约束条件,对偶问题有m个变量 ◆原问题有n个变量,对偶问题有n个约束条件 ◆原问题的价值系数对应对偶问题的右端项 ◆原问题的右端项对应对偶问题的价值系数 原问题的技术系数矩阵转置后为对偶问题系数 矩阵 ◆原问题的约束条件与对偶问题方向相反 原问题与对偶问题优化方向相反 ORI
OR1 6 对偶规则 原问题有m个约束条件，对偶问题有m个变量 原问题有n个变量，对偶问题有n个约束条件 原问题的价值系数对应对偶问题的右端项 原问题的右端项对应对偶问题的价值系数 原问题的技术系数矩阵转置后为对偶问题系数 矩阵 原问题的约束条件与对偶问题方向相反 原问题与对偶问题优化方向相反
对偶规则 原问题 对偶问题 目标函数 maxmin目标函数 约束条件≤≥ 变量 无约束 变量符号≤≤ 束条件 无约束 ORI
OR1 7 对偶规则 . 原问题 对偶问题 目标函数 max min 目标函数 约束条件 ≤ ≥ = ≥ 变量 ≤ 无约束 ≥ 变量符号 ≤ 无约束 ≥ ≤ 约束条件 =
对偶规则简捷记法 ◆原问题标准则对偶问题标准 ◆原问题不标准则对偶问题不标准 ◆例题2 max0=7y1+4y2-2y3 minz=3x1+2X2-6X3+X5 2V1+y2-V37 +3y3≤2 X1+2x3-X444y1+2y20 x4<0;x5无限制 y≥0y2≤0y3无约束 ORI
OR1 8 对偶规则简捷记法 原问题标准则对偶问题标准 原问题不标准则对偶问题不标准 例题2 max ω=7y1+4y2-2y3 minZ=3x1+2x2-6x3+x5 2y1+ y2- y3 ≤3 2x1+x2-4x3+x4+3x5 ≥7 y1 +3y3 ≤2 x1+ 2x3 -x4 ≤ 4 -4y1+ 2y2 ≤-6 -x1+3x2 -x4+ x5 =-2 y1 -y2 -y3 ≥ 0 x1，x2，x3 ≥0; 3y1 +y3=1 x4 ≤ 0;x5无限制 y1 ≥ 0y2 ≤ 0y3 无约束
3.1.3对偶问题的基本性质 ◆对称性:对偶问题的对偶问题是原问题 ◆弱对偶性:极大化原问题的任一可行解的目标 函数值,不大于其对偶问题任意可行解的目标 函数值(鞍型图) 无界性:原问题无界,对偶问题无可行解 ◆对偶定理:若一个问题有最优解,则另一问题 也有最优解,且目标函数值相等。若原问题最 优基为B,则其对偶问题最优解Y*=CB ORI
OR1 9 3.1.3对偶问题的基本性质 对称性：对偶问题的对偶问题是原问题 弱对偶性：极大化原问题的任一可行解的目标 函数值，不大于其对偶问题任意可行解的目标 函数值 (鞍型图) 无界性：原问题无界，对偶问题无可行解 对偶定理：若一个问题有最优解，则另一问题 也有最优解，且目标函数值相等。若原问题最 优基为B，则其对偶问题最优解Y*=CBB-1
3.1.4对偶最优解的经济解 释—影子价格 Z-Q=CX-Yb aZ/ab=(Yb=Y Z-Yb=∑yb的意义:Y是检验数的反数。在Y确定的前 提下,莓增加一个单位的种资源,对目标函数的贡献 ◆结合例题1讲解影子价格:y1=0:第一种资源过剩 y2=136:设备台时最紧张,每增加一个台时,利润增加 13.6元。y3=5.2 ◆影子价格所含有的信息:1、资源紧缺状况 2、确定资源转让基价 参见:P40 3、取得紧缺资源的代价 ORI
OR1 10 3.1.4对偶最优解的经济解 释—影子价格 Z= ω=CX=Yb Z/ b=(Yb)’=Y Z=Yb= ∑yibi的意义：Y是检验数的反数。在Y确定的前 提下，每增加一个单位的i种资源，对目标函数的贡献。 结合例题1讲解影子价格：y1=0:第一种资源过剩 y2=13.6：设备台时最紧张，每增加一个台时， 利润增加 13.6元。y3=5.2… 影子价格所含有的信息： 1、资源紧缺状况 2、确定资源转让基价 参见：P40 3、取得紧缺资源的代价