搜索

第2章26 对偶原理

gecimao 发表于 2019-07-03 23:30 | 查看: | 回复:

  第2章2.6 对偶原理_理学_高等教育_教育专区。物流运筹学中的对偶原理

  2.6 对偶原理 换个角度审视生产计划问题 要求制定一个生产计划方案, 例2-1要求制定一个生产计划方案,在劳动 要求制定一个生产计划方案 力和原材料可能供应的范围内, 力和原材料可能供应的范围内,使得产品 的总利润最大 。 max Z = 2 x1 + 3 x2 ? x1 + 2 x2 ≤ 8 ? 4 x1 ≤ 16 ? ? 4 x2 ≤ 12 ? ? x1 , x2 ≥ 0 ? 它的对偶问题就是一个价格系统 对偶问题就是一个价格系统, 它的对偶问题就是一个价格系统,使 在平衡了设备资源和原材料的直接成本 所确定的价格系统最具有竞争力 价格系统最具有竞争力: 后,所确定的价格系统最具有竞争力: MinW = 8 y1 + 16 y 2 + 12 y 3 ( 用于生产第 i 种产品 ? y1 + 4 y 2 ≥ 2 的资源转让收益不小于 ? 2 y1 + 4 y 3 ≥ 3 ? s.t .? 生产该种产品时获得的 ? y1 , y 2 , y 3 ≥ 0 利润) 利润) ? ? 对偶变量的经济意义可以解释为 对工时及原材料的单位定价 ; 若工厂自己不生产产品Ⅰ 若工厂自己不生产产品Ⅰ、Ⅱ,将现有 的设备及原材料转而接受外来加工时, 的设备及原材料转而接受外来加工时,那 么上述的价格系统能保证不亏本又最富有 竞争力(包工及原材料的总价格最低) 竞争力(包工及原材料的总价格最低) 当原问题和对偶问题都取得最优解时, 当原问题和对偶问题都取得最优解时,这 一对线性规划对应的目标函数值是相等的: 一对线性规划对应的目标函数值是相等的: Zmax=Wmin=14 考察原问题和对偶问题的解, 考察原问题和对偶问题的解,给作决 策的管理者另一个自由度; 策的管理者另一个自由度; 怎样通过增加更多的资源来增加利润? 怎样通过增加更多的资源来增加利润? 怎样使用不同类型的资源来增加利润? 怎样使用不同类型的资源来增加利润? 3、饮食与营养问题 例2-2 采购甲、乙、丙、丁4种食品量分别 采购甲、 为x1,x2,x3,x4,在保证人体所需维生素 A、B、C前提下,使总的花费最小。 前提下,使总的花费最小。 构建的线性规划模型: 构建的线性规划模型: 线性规划模型 MinZ = 0.8 x1 + 0.5 x 2 + 0.9 x 3 + 1.5 x 4 (国际单位维生素 A) ?1000 x1 + 1500 x 2 + 1750 x 3 + 3250 x 4 ≥ 4000 ?0.6 x + 0.27 x + 0.68 x + 0.3 x ≥ 1 (毫克维生素 B) ? 1 2 3 4 s.t .? (毫克维生素 C ) ?17 .5 x1 + 7.5 x 2 + 30 x 4 ≥ 30 ? x1 , x 2 , x 3 , x 4 ≥ 0 ? 换一个角度, 换一个角度,生产营养药丸的制药公司力 图使营养师相信, 图使营养师相信,各种营养药丸勿须通过多种 食品的转换就能供营养师调剂。 食品的转换就能供营养师调剂。 制药公司面对的问题是为营养药 制药公司面对的问题是为营养药 丸确定单价,以获得最大的收益, 丸确定单价,以获得最大的收益,同 时与真正的食品竞争。 时与真正的食品竞争。 于是,营养药丸的单位成本不能 于是,营养药丸的单位成本不能 超过相应食品的市场平均价 相应食品的市场平均价。 超过相应食品的市场平均价。 由此得到下面的对偶问题: 由此得到下面的对偶问题: MaxW= 4000y1 + y2 + 30y3 I ) ?1000y1 + 0.6 y2 +17.5y3 ≤ 0.8 (合成药丸的成本≤甲食品市价 ?1500y1 + 0.27y2 + 7.5y3 ≤ 0.5 (合成药丸 的成本≤ 乙食品市价 II ) ? ? s.t.?1750y1 + 0.68y2 + 0 y3 ≤ 0.9 (合成药丸 的成本≤ 丙食品市价 III ) ?3250y + 0.3y + 30y ≤ 1.5 (合成药丸 的成本≤ 丁食品市价 IV ) 1 2 3 ? ?y1 , y2 , y3 ≥ 0 ? 二、原问题和对偶问题的关系 1、对称形式的对偶关系 (1)若原问题是 ) MaxZ = c1 x1 + c 2 x 2 + L + c n x n ?a11 x1 + a12 x 2 + L + a1n x n ≤ b1 ?a x + a x + L + a x ≤ b 22 2 2n n 2 ? 21 1 ? s.t.? L L L ?a x + a x + L + a x ≤ b m2 2 mn n m ? m1 1 ? x1 , x 2 , L , x n ≥ 0 ? (2) 其对偶问题为 MinW = b1 y1 + b 2 y 2 + L + b m y m ? a11 y1 + a 21 y 2 + L + a m 1 y m ≥ c1 ?a y + a y + L + a y ≥ c 22 2 m2 n 2 ? 12 1 ? s .t .? L L L ?a y + a y + L + a y ≥ c 2n 2 mn n n ? 1n 1 ? y1 , y 2 , L , y m ≥ 0 ? 这两个式子的变换关系称为“对称形式的对偶关系” 这两个式子的变换关系称为“对称形式的对偶关系”。 (2)对称形式的对偶关系的矩阵描述 ) MaxZ = CX AX ≤ b (L) s .t .? ? ? X ≥0 (D) MinW = bY ? YA ≥ C s .t .? ? Y ≥ 0 例2-3 写出下面线性规划的对偶问题: 写出下面线性规划的对偶问题: MaxZ = 2 x1 + x2 ?3x1 + 4 x2 ≤ 15 ? s.t.?5 x1 + 2 x2 ≤ 10 ?x , x ≥ 0 ? 1 2 MinW = 15y1 + 10y2 ?3 y1 + 5 y2 ≥ 2 ? s.t.?4 y1 + 2 y2 ≥ 1 ? y ,y ≥0 ? 1 2 2、非对称形式的对偶关系: 非对称形式的对偶关系: (1) 原问题 MaxZ= ∑c j x j j=1 n 对偶问题 MinW= ∑bi xi i =1 m ?n ?∑aij x j = bi i =1,2,L, m s.t.? j=1 ?x j ≥ 0 j =1,2,L, n ? ?m ?∑aij yi ≥ cj j =1,2,L, n s.t.?i=1 ?yi符号不限, =1,2,L, m i ? 特点: ( 特点 : 对偶变量符 号不限, 系数阵转置) 号不限 , 系数阵转置 ) (特点:等式约束) 特点:等式约束 特点 (2)怎样写出非对称形式的对偶问题? )怎样写出非对称形式的对偶问题? ?把一个等式约束写成一个不等式约束, 把一个等式约束写成一个不等式约束, 再根据对称形式的对偶关系定义写出; 再根据对称形式的对偶关系定义写出; 按照原始?按照原始-对偶表直接写出 ; (3)原始 对偶表 )原始-对偶表 原问题(或对偶问题) 原问题(或对偶问题) 目标函数 MaxZ 约束条件数: 个 约束条件数:m个 个约束条件类型为“ ” 第i个约束条件类型为“≤” 个约束条件类型为 个约束条件类型为“ ” 第i个约束条件类型为“≥” 个约束条件类型为 个约束条件类型为“ ” 第i个约束条件类型为“=” 个约束条件类型为 决策变量数: 个 决策变量数:n个 个变量≥0 第j个变量 个变量 个变量≤0 第j个变量 个变量 第j个变量是自由变量 个变量是自由变量 对偶问题(或原问题) 对偶问题(或原问题) 目标函数 MinW 对偶变量数: 个 对偶变量数:m个 个变量≥0 第i个变量 个变量 个变量≤0 第i个变量 个变量 第i个变量是自由变量 个变量是自由变量 约束条件数: 约束条件数:n 个约束条件类型为“ ” 第i个约束条件类型为“≥” 个约束条件类型为 个约束条件类型为“ ” 第i个约束条件类型为“≤” 个约束条件类型为 个约束条件类型为“ ” 第i个约束条件类型为“=” 个约束条件类型为 例2-4 写出下面线性规划的对偶问题: 写出下面线性规划的对偶问题: MinZ = 3x1 + 2 x2 ? x3 ?2 x1 + x2 + 3x3 ≥ 2 ?3x1 ? 5 x2 ≤ 5 ? s.t.? ? x1 + x2 + x3 = 1 ? x1 ≤ 0, x3 ≥ 0 ? MaxW = 2 y1 + 5 y2 + y3 ?2 y1 + 3 y2 + y3 ≥ 3 ? y1 ? 5 y2 + y3 = 2 ? s.t.? ? 3y1 + y3 ≤ ?1 ? y1 ≥ 0, y2 ≤ 0 ? 三、对偶定理 对偶定理是揭示 原始问题的解与对偶问题的解之间重 一系列定理。 要关系的 一系列定理。 定理2 对称性定理—— 定理2-1 对称性定理—— 对偶问题的对偶是原问题。 定理2 弱对偶定理——若一对对称形 定理2-2 弱对偶定理——若一对对称形 式的对偶线性规划 MaxZ = CX L) ) MinW = bY ? AX ≤ b 和 D) ) s.t .?YA ≥ C s.t.? ? ? X ≥0 ?Y ≥0 ~ ~ ~ ~ 均有可行解, 均有可行解,分别为 X 和 Y ,则C X ≤ Yb。 。 ? 关于“界”的结果; 关于“ 的结果; 极小化问题有下界—— 极小化问题有下界 推论1 推论1 极大化问题的任意一个可行解所对应的目标函 数值是其对偶问题最优目标函数值的一个下界。 数值是其对偶问题最优目标函数值的一个下界。 ? 极大化问题有上界 极大化问题有上界—— 推论2 推论2 极小化问题的任意一个可行解所对 应的目标函数值是其对偶问题最优目标函 数值的一个上界。 数值的一个上界。 ?关于最优解无界情况与对偶问题的关系; 关于最优解无界情况与对偶问题的关系; 原始问题可行, 原始问题可行,且目标函数值上无界 对偶问题不可行 定理2 定理2-3 最优性准则定理 ~、~ 分别为对 最优性准则定理—— 最优性准则定理—— 若 X Y 称形式对偶线性规划的可行解, 称形式对偶线性规划的可行解,且两者目标 ~ ~,则 ~ ,~ 函数的相应值相等, 函数的相应值相等,即C X=b Y X Y 分别为原始问题和对偶问题的最优解。 分别为原始问题和对偶问题的最优解。 定理2 定理2-4 主对偶定理 若原始问题和对偶问 题两者均可行,则两者均有最优解, 题两者均可行,则两者均有最优解,且此时 目标函数值相同。 目标函数值相同。 四、对偶最优解(影子价格)的经济含义 影子价格) 1、 对偶最优解的经济解释 讨论例1-1的图解法时 , 提出了它的对 的图解法时, 讨论例 的图解法时 偶规划, 并用图解法求出了最优解。 偶规划 , 并用图解法求出了最优解 。 同时 提到“影子价格” 确切的定义是: 提到“影子价格” ,确切的定义是:一个 线性规划对偶问题的最优解( 简称为“ 线性规划对偶问题的最优解 ( 简称为 “ 对 偶最优解” 在经济上可以解释为 偶最优解 ” ) 。 在经济上可以解释 为 约束 条件所付出的代价。 条件所付出的代价。 原问题和对偶问题都取得最优解时, 当原问题和对偶问题都取得最优解时,这 一对线性规划对应的目标函数值相等, 一对线性规划对应的目标函数值相等,即 有 Zmax=CX*=2x*1+3x*2 Wmin=Y*b=8y*1+16y*2+12y*3=14 其中X 是原问题的最优解, 其中X*是原问题的最优解,Y*是对偶问 题最优解。 题最优解。 说明目标函数值增加一个单位 目标函数值增加一个单位, 说明目标函数值增加一个单位, 这就是放宽一个约束条件所产生的 这就是放宽一个约束条件所产生的 附加贡献。 附加贡献。 就是说,影子价格确定了 确定了为得到 就是说,影子价格确定了为得到 一个附加单位的约束因素所应花费 的成本上限。 的成本上限。 当前最敏感的资源是什麽? 当前最敏感的资源是什麽? 劳动工时! 劳动工时! 因为它的变化对产品总利润的影响最 因此劳动力 最关键的生产环节, 劳动力是 大 , 因此 劳动力 是 最关键的生产环节 , 若能采取有力措施增加劳动总工时, 若能采取有力措施增加劳动总工时 , 则 产品总利润将得到较大的提高。 产品总利润将得到较大的提高。 在计算机求解结果中将约束条件的影 子价格和变量的机会成本统称为机会成 子价格和变量的机会成本统称为机会成 本(opportunity cost)。 求解结果总表 Solution Opportun ity Cost 1 2 3 x1 x2 s1 4.0000 2.0000 0.0000 0.0000 0.0000 1.5000 4 5 s2 s3 0.0000 4.0000 0.1250 0.0000 Maximum Value of the OBJ = 14 Iters.=3 综上, 影子价格是灵敏度分析 综上 , 影子价格 是灵敏度分析 的一种形式, 的一种形式 , 它 通过获取一个单位 的追加的产品因素, 的追加的产品因素 , 去 测量放宽一 个约束条件的价值, 个约束条件的价值 , 比较追加资源 的价值和资源的实际成本, 的价值和资源的实际成本 , 就能比 较有把握地作出各种可行的决策。

本文链接:http://baumseelen.com/duiouyuanli/611.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部