线性优化-2_对偶问题.pdf

1 第七章 线性优化 (2) 清华大学清华大学MBA课程课程 Data, Models and Decisions 数据, 模型与决策 第七章 线 性 优 化 (2) §§5 5 线性规划的对偶问题线性规划的对偶问题 §§6 6 对偶解的经济解释对偶解的经济解释 §§7 7 敏感性分析敏感性分析 §§8 8 对偶问题的博弈内涵对偶问题的博弈内涵 3 §5 线性规划的对偶问题 对偶理论是线性规划中最重要的理论之一，对偶理论是线性规划中最重要的理论之一，  充分显示线性规划理论的严谨性和结构的对称性；充分显示线性规划理论的严谨性和结构的对称性；  对偶解（影子价格）有重要的经济意义，是进行经对偶解（影子价格）有重要的经济意义，是进行经 济分析的重要工具；济分析的重要工具；  对偶问题为资源定价，并建立整个系统的价值平衡对偶问题为资源定价，并建立整个系统的价值平衡 关系，为分析经营活动价值链提供了科学手段；关系，为分析经营活动价值链提供了科学手段； 4 对偶问题的提出对偶问题的提出  家具厂模型：站在家具厂角度追求销售利润最大：家具厂模型：站在家具厂角度追求销售利润最大： max z = 50x1 + 30x2 s.t. 4x1 + 3x2   120 2x1 + x2   50 x1, x2   0  考虑决策问题：一个企业家有一批待加工的订单，考虑决策问题：一个企业家有一批待加工的订单， 有意利用家具厂的资源来加工他的产品，该企业家有意利用家具厂的资源来加工他的产品，该企业家 试图劝说家具厂的管理者将资源租给他。

他将面对试图劝说家具厂的管理者将资源租给他他将面对 一个什么样的经营问题：决策变量是什么？追求的一个什么样的经营问题：决策变量是什么？追求的 目标是什么？目标是什么？ 5 租赁者的决策模型租赁者的决策模型  变量变量: y1 为单位木工工时所支付的租金；为单位木工工时所支付的租金； y2 为单位油漆工工时所支付的租金；为单位油漆工工时所支付的租金；  目标函数目标函数：总租金最小：总租金最小 min 120y1 + 50y2  约束约束：： s.t.  桌子等价资源约束桌子等价资源约束：： 4y1 + 2y2   50  椅子等价资源约束：椅子等价资源约束： 3y1 + y2   30  租金非负约束租金非负约束：： y1   0, y2   0  约束经济意义约束经济意义：租赁者所付：租赁者所付租金应不低于家具厂利租金应不低于家具厂利 用这些资源可能获得的利益；用这些资源可能获得的利益； 6 用图解法求解租赁问题用图解法求解租赁问题 y2 y1 20 25 15 4y1+ 2y2   50 10 5 5 10 15 3y1+y2   30 w = 120y1+50y2= 1350 (5, 15) 最优解恰好最优解恰好 也是也是1350；； 是巧合，还是巧合，还 是必然？是必然？ 如何解释这如何解释这 种巧合？种巧合？ 2 7 线性规划的原问题与对偶问题线性规划的原问题与对偶问题 min: w = 120y1 + 50y2 s.t. 4y1 + 2y2   50 3y1 + y2   30 y1   0, y2   0 资 源 定 价 问 题资 源 定 价 问 题租 赁 者 模 型租 赁 者 模 型max: z = 50x1 + 30x2 s.t. 4x1 + 3x2   120 2x1 + x2   50 x1   0, x2   0 资 源 优 化 问 题资 源 优 化 问 题管 理 者 模 型管 理 者 模 型原原 始始 问问 题题 对对 偶偶 问问 题题 8 配餐问题的对偶问题配餐问题的对偶问题  原问题原问题：：满足营养前提下使食品成本最小；满足营养前提下使食品成本最小；  对偶问题：某生产减肥食品公司生产三种可替代食对偶问题：某生产减肥食品公司生产三种可替代食 品中热量、蛋白质和钙的营养素，希望产品既有市品中热量、蛋白质和钙的营养素，希望产品既有市 场竞争力，又能带来丰厚利润，需构造模型研究营场竞争力，又能带来丰厚利润，需构造模型研究营 养素的定价问题。

养素的定价问题  决策变量：单位营养素的销售价格；决策变量：单位营养素的销售价格；  目标函数：销售收入最大；目标函数：销售收入最大；  约束条件：反映市场竞争条件，购买与食品营养约束条件：反映市场竞争条件，购买与食品营养 价值相同的营养素的成本应小于食品价格价值相同的营养素的成本应小于食品价格 9 配餐问题的对偶问题配餐问题的对偶问题  变量设置变量设置 y1: 单位单位热量营养素价格热量营养素价格; y2: 单位单位蛋白质营养素价格蛋白质营养素价格; y3: 单位单位钙营养素价格钙营养素价格;  目标函数：满足人一天需要的营养素产品的销售收目标函数：满足人一天需要的营养素产品的销售收 入最大：入最大： max ：： 3000y1 + 55y2 + 800y3 热量需求量热量需求量   热量营养素价格热量营养素价格+ 蛋白质蛋白质需求量需求量   蛋蛋 白质价格白质价格 + 钙需求量钙需求量   钙营养素价格钙营养素价格 10 配餐问题的对偶问题配餐问题的对偶问题  约束：购买与猪肉、鸡旦、大米和白菜营养价值等约束：购买与猪肉、鸡旦、大米和白菜营养价值等 价的营养素成本应不高于它们的价格；价的营养素成本应不高于它们的价格； 1000y1 + 50y2 + 400y3   14 800y1 + 60y2 + 200y3   6 900y1 + 20y2 + 300y3   3 200y1 + 10y2 + 500y3   2  营养素的价格不能为负值：营养素的价格不能为负值： y1 0, y2 0, y3 0 11 配餐问题配餐问题与与对偶问题对偶问题 max 3000y1 + 55y2 + 800y3 s.t. 1000y1 + 50y2 + 400y3   14 800y1 + 60y2 + 200y3   6 900y1 + 20y2 + 300y3   3 200y1 + 10y2 + 500y3   2 y1, y2, y3   0 min 14x1 + 6x2 + 3x3 + 2x4 s.t. 1000x1+800x2+900x3+200x4  3000 50x1+ 60x2+ 20x3+ 10x4   55 400x1+200x2+300x3+500x4   800 x1，，x2，，x3，，x4   0 原问题：原问题： 对偶问题：对偶问题： 12 原原(对偶对偶)问题问题 对偶对偶 (原原)问题问题 目标函数类型目标函数类型 max min 目标函数与右边项目标函数与右边项 的对应关系的对应关系 目标函数系数目标函数系数 右边项系数右边项系数 右边项系数右边项系数 目标函数系数目标函数系数 变量数与约束数的变量数与约束数的 对应关系对应关系 变量数变量数 n 约束数约束数 m 约束数约束数 n 变量数变量数 m 变量类型与变量类型与 约束类型的约束类型的 对应关系对应关系   0 变量变量   0 无限制无限制   约束约束     约束类型与约束类型与 变量类型的变量类型的 对应关系对应关系   约束约束       0 变量变量   0 无限制无限制 原问题－对偶问题的对应关系原问题－对偶问题的对应关系 3  原问题：原问题： 资源优化问题资源优化问题 max：：c1 x1 + ... + cn xn s.t. a11x1 + ... + a1nxn   b1 . . . . . . am1x1 + ...+ amn xn   bm x1, x2, ..., xn   0  对偶问题：资源定价问题对偶问题：资源定价问题 min：：b1 y1 + ... + bm ym s.t. a11y1 + ... + am1 ym   c1 . . . . . . a1ny1 + ... + amnym   c y1, y2, ..., ym   0 原问题与对偶问题的对应关系原问题与对偶问题的对应关系 原问题原问题 研究为企业带来研究为企业带来市场市场 价值价值 c 的的经营活动经营活动 x 在满足资源平衡条件在满足资源平衡条件 下竞争下竞争使用使用有限有限资源资源 b 的的资源优化资源优化问题问题。

对偶问题对偶问题 研究在满足研究在满足经营活动经营活动 价值平衡条件下，将价值平衡条件下，将 市场价值市场价值 c 分配给分配给资资 源源 b 带来带来价值贡献价值贡献 y 的的资源定价问题资源定价问题 线性规划同时完成线性规划同时完成资源优化资源优化与与资源定价资源定价 14 原问题的经济意义原问题的经济意义 max: c1x1+c2 x2+…+ cnxn s.t. a11x1+a12x2+…+ a1nxn   b1 · · · · · · ai1x1 + ai2x2+…+ ainxn   bi · · · · · · x1, x2, … , xn   0 经营收经营收 益最大益最大 经营活动消经营活动消 耗资源数量耗资源数量 可用资可用资 源数量源数量 目标：经营活动创造的目标：经营活动创造的经济效益最大化；经济效益最大化； 约束：经营活动使用资源约束：经营活动使用资源数量不大于可用数量不大于可用资源资源数量；数量； 经济意义：资源（物流经济意义：资源（物流）平衡约束）平衡约束下的下的资源优化问题资源优化问题 原始变量原始变量 表示经济表示经济 活动水平活动水平 资源消资源消 耗系数耗系数 15 对偶问题的经济意义对偶问题的经济意义 min：：b1 y1 + b2 y2 + ... + bm ym s.t. a11y1 + a21y2 + ... + am1 ym   c1 . . . . . . a1i y1 + a2i y2 + ... + ami ym   ci . . . . . . y1, y2, ... , ym   0 经营活动经营活动 市场贡献市场贡献 资源消资源消 耗系数耗系数 经营活动消经营活动消 耗资源价值耗资源价值 资源消耗资源消耗 价值最小价值最小 目标：经营活动消耗的资源价值最小目标：经营活动消耗的资源价值最小化；化； 约束：经营活动使用的资源约束：经营活动使用的资源价值不小于其价值不小于其市场市场价值；价值； 经济意义：价值（资金流经济意义：价值（资金流）平衡约束）平衡约束下下的的资源定价问题资源定价问题 对偶变量表对偶变量表 示资源价值示资源价值 16 对偶定理对偶定理 弱对偶定理：弱对偶定理：设设 x, y 分别是线性规划原问题分别是线性规划原问题 P 和对和对 偶问题偶问题 D 的可行解，则有的可行解，则有: max: cx   min: yb 对偶定理：对偶定理：P 和和 D 存在以下对应关系：存在以下对应关系： (1) P 有最优解的充要条件是有最优解的充要条件是 D 有最优解；有最优解； (2) P 无界则无界则 D 不可行，不可行，D 无界则无界则 P。