《对偶理论DualityTheory.ppt》由会员分享,可在线阅读,更多相关《对偶理论DualityTheory.ppt(86页珍藏版)》请在三一文库上搜索。
1、对 偶 理 论 (Duality Theory) 对偶问题的提出 线性规划的对偶理论 对偶问题的经济解释-影子价格 对 偶 单 纯 形 法 灵 敏 度 分 析 对偶性是线性规划问题的最重要的内容之一。每 一个线性规划( LP )必然有与之相伴而生的另一个 线性规划问题,即任何一个求 maxZ 的LP都有一个求 minZ 的LP。其中的一个问题叫“原问题”,记为 “P”,另一个称为“对偶问题”,记为“D”。 例一、资源的合理利用 问题 已知资料如表所示,问 应如何安排生产计划使得 既能充分利用现有资源有 使总利润最大? 1810单件利润 150(设备)51C 100(煤炭)32B 170(钢材)
2、25A 资源限制乙甲 单件 产 消耗 品 资源 一、问 题 的 提 出 下面从另一个角度来讨论这个问题: 假定:该厂的决策者不是考虑自己生产甲、乙两种 产品,而是将厂里的现有资源用于接受外来加工任务 ,只收取加工费。试问该决策者应制定怎样的收费标 准(合理的)? 分析问题: 1、每种资源收回的费用不能低于自己生产时的可获 利润; 2、定价又不能太高,要使对方能够接受。 一般而言,W 越大越好,但因需双方满意,故 为最好。 该问题的数学模型为: 模型对比: 例二、合理配料问题,其数学模型为: 假设工厂想把这m 种营养成分分别制成一种营养丸 销售,问如何定价(以保证总收入为最多)? 原问题对偶问题
3、 目标函数maxmin 约束条件 变量数量约束条件个数 约束条件个数变量数量 例三、 23 x1 x2 原问题 12y1 2212 8y2 128 16y34016 12y40412 对偶问题23 1、对称型对偶问题:已知 P,写出 D。 二、线性规划的对偶理论 (一)、对偶问题的形式 例一、写出线性规划问题的对偶问题 解:首先将原式变形 注意:以后不强调等式右段项 b0,原因在对偶 单纯型表中只保证 而不保证 ,故 b 可以是负数。 2、非对称型对偶问题 例二、原问题 2、混合型对偶问题 例三、 原问题 对偶问题 综上所述,其变换形式归纳如下: 原问题(或对偶问题)对偶问题(或原问题) 目标
4、函数 max目标函数 min 约 束 条 件 m个m个 变 量 0 0 =无约束 变 量 n个n个约 束 条 件 0 0 无约束= 约束条件右端项目标函数变量的系数 目标函数变量的系数约束条件右端项 例四、线性规划问题如下: 练习: min Z= - CX s.t. - AX- b X 0 1、对称性定理:对偶问题的对偶是原问题。 min W= Y b s.t. YA C Y 0 max Z=C X s.t. AXb X 0 对偶的定义 对偶的定义 max W = -Yb s.t. YA C Y 0 (二)、对偶问题的性质 2、弱对偶原理(弱对偶性):设 和 分别是问题 (P)和(D)的可行解
5、,则必有 推论.若 和 分别是问题(P)和(D)的可行解 ,则 是(D)的目标函数最小值的一个下界; 是 (P)的目标函数最大值的一个上界。 推论.在一对对偶问题 (P)和(D)中,若其中 一个问题可行但目标函数 无界,则另一个问题不可 行;反之不成立。这也是 对偶问题的无界性。 无可行解 关于无界性有如下结论: 问题无界 无可行解问题无界 对偶问题原问题 无界 如: (原) 无可 行解 (对) 推论.在一对对偶问题(P)和(D)中,若一个可 行(如P),而另一个不可行,(如D),则该可行的 问题无界。 例一、 试估计它们目标函数的界,并验证弱对偶性原理。 (P) 解: (D) 由观察可知:
6、=(1.1.1.1)T, =(1.1),分别 是(P)和(D)的可行解。Z=10 ,W=40,故有 ,弱对偶定理成立。由推论可知,W 的最 小值不能小于10,Z 的最大值不能超过40。 例二、已知 试用对偶理论证明原问题无界。 解: =(0.0.0)T是 P 的一个可行解,而 D 的第一 个约束条件不能成立(因为y1 , y2 0)。因此,对偶问题 不可行,由推论可知,原问题无界。 例3、已知 显然,这两个问题都无可行解。 3、最优性判别定理: 若 X* 和 Y* 分别是 P 和 D 的可行解且 CX* = Y* b, 则X*. Y*分别是问题 P和D 的最优解。 例如,在例1中,可找到 X*
7、=(0.0.4.4)T, Y*=(1.2,0.2),则Z* =28,W* =28.故X* .Y*分别是 P和D 的最优解。 4、对偶定理(强对偶性): 若一对对偶问题 P 和 D 都有可行解,则它们都有 最优解,且目标函数的最优值必相等。 推论.若 P 和 D 的任意一个有最优解,则另一个 也有最优解,且目标函数的最优值相等。 综上所述,一对对偶问题的关系,只能有下面三种情 况之一出现: .都有最优解,分别设为X* 和 Y*,则必有CX* =Y*b; . 一个问题无界,则另一个问题无可行解; .两个都无可行解。 5、互补松弛定理: 设X*和Y*分别是问题 P 和 D 的可行解,则它们分别 是最
8、优解的充要条件是 同时成立 一般而言,我们把某一可行点(如X*和Y* )处的严 格不等式约束(包括对变量的非负约束)称为松约束 ,而把严格等式约束称为紧约束。所以有如下推论: 设一对对偶问题都有可行解,若原问题的某一约束 是某个最优解的松约束,则它的对偶约束一定是其对 偶问题最优解的紧约束。 例4、已知 试通过求对偶问题的最优解来求解原问题的最优解。 解:对偶问题为 用图解法求出: Y*=(1 . 3), W=11。 将y*1=1, y*2=3 代入对偶约束条件, (1)(2)(5)式为紧约束,(3)(4)为松约束。 令原问题的最优解为X* = (x1.x2.x3.x4.x5)T,则根据 互补
9、松弛条件,必有x3 = x4 =0 (1 . 3)(1) (2) (3) (4) (5) 又由于y*10, y*2 0,原问题的约束必为等式,即 化简为 此方程组为无穷多解 令x5 =0,得到x1=1,x2=2 即X*1 =(1.2.0.0.0)T为原问题的 一个最优解,Z=11。 再令 x5 =2/3,得到x1=5/3,x2=0 即X*2 (5/3.0.0.0.2/3)T 也是原问题的一个最优解,Z* =11。 例5、已知原问题的最 优解为X* =(0.0.4)T ,Z=12 试求对偶问题 的最优解。 解: (1) (2) (3) 将X* =(0 . 0 . 4)代入原问题中,有下式: 所以
10、,根据互补松弛条件,必有y*1= y*2=0,代入对偶 问题 (3)式, y3 =3。因此,对偶问题的最优解为 Y*=(0 . 0 . 3),W=12。 6、对偶问题的解 利用原问题的最优单纯 形表和改进单纯形表求 解对偶问题的最优解。 .设原问题为: maxZ=CX AX b X0 引入xs ,构建初始基变量,然后,用单纯形法求解。当 检验数满足j0 ,则求得最优解。此时, xs对应的js 为 - Y* ,故求对偶Y* ,只要将最优单纯形表上xs 对应的检验数反号即可。 CCBCN0 CBXBbXBXNXS CBXBB-1bIB-1NB-1 ZCB B-1b0CNCB B-1NCB B-1
11、例一、 cj1018000 cBxBbx1x2x3x4x5 0x317052100170/2 0x410023010100/3 0x515015001150/5 -Z01018000 cj1018000 cBxBbx1x2x3x4x5 0x3540/7001-23/711/7 10x150/71005/7-3/7 18x2200/7010-1/72/7 -Z-4100/7000-32/7-6/7 初 始 表 最终表 由上表可知: X*=(50/7 . 200/7)T,Z* =4100/7 对偶问题的最优解: Y*=(0 . 32/7 . 6/7),W* =4100/7 也就是外加工时的收费标准
12、。 .设原问题: maxZ=CX AX=b X0 此时,矩阵A中没有现成的矩阵I,必须通过加入人工 变量来凑一个单位矩阵,再用大M法或两阶段法求解 。 如何求Y* ,经分析得出如下结论: B =0 最优基变量检验数向量 I =CI CB B-1 初始基变量检验数向量 D = CD CB B-1D 非基变量检验数向量 所以, Y* = CI I 例二、 cj3-1-100-M-M cBxBbx1x2x3x4x5x6x7 3x141001/3-2/32/3-5/3 -1x210100-11-2 -1x390012/3-4/34/3-7/3 -Z-2000-1/3-1/31/3-M 2/3- M c
13、j3- 1- 100- M- M cBxBbx1x2x3x4x5x6x7 0x4111-21100011 - Mx63-4120-1103/2 - Mx71-20100011 -Z 3-6M-1+M-1+3M 0-M00 所以, X*=(4 . 1 . 9),Z* = 2 y*1= (0 4 )=1/3 y*2=(M 6 )= M(1/3M)=1/3 y*3 =(M 7 )= M(2/3 M)=2/3 Y*=(1/3 . 1/3 . 2/3) W* = 2 初始基变量的检验数4 =1/3,6 =1/3M, 7 =2/3M 定义:在一对 P 和 D 中,若 P 的某个约束条件的 右端项常数bi
14、增加一个单位时,所引起的目标函数最优 值Z* 的改变量y*i 称为第 i 个约束条件的影子价格,又 称为边际价格。 三、对偶问题的经济解释影子价格 设:B是问题 P的最优基,由前式可知, Z*=CB B-1b = Y*b =y*1b1+ y*2b2+y*Ibi+y*mbm 当bi 变为bi+1 时(其余右端项不变,也不影响B) , CCBCN0 CBXBbXBXNXS CBXBB-1bIB-1NB-1 ZCB B-1b0CNCB B-1NCB B-1 目标函数最优值变为: Z*= y*1b1+ y*2b2+y*I ( bi+1 )+y*mbm Z*= Z* Z* = y*i 也可以写成: 即y
15、*i 表示Z*对 bi的变化率。 其经济意义是:在其它条件不变的情况下,单位资源 变化所引起的目标函数的最优值的变化。即对偶变量yi 就是第 i 个约束条件的影子价格。 也可以理解为目标函数最优值对资源的一阶偏导数 (但问题中所有其它数据都保持不变)。 若第i 种资源的单位市场价格为mi ,当yi mi 时, 企业愿意购进这种资源,单位纯利为yimi ,则有利 可图;如果yi 0, 则以 x j 为入基变量,用单纯 形法继续迭代,即可求出最优解。 (二)基变量的价值系数 Cj 发生改变, Cj Cj=Cj+Cj (Cj可正可负),所 有非基变量的检验数都改变,计算新的检验 数。 若新的检验数:
16、 (1)j0, 原最优解保持不变。 ( 2 ) j0, 则以大于0的检验数中最大的变 量为入基变量,用单纯形法继续迭代,即可 求出最优解。 例:某企业利用三种资源生产两种产品的最优计划 问题归结为下列线性规划 已知最优表如下。 (1)确定x2的系数c2的 变化范围,使原最优解 保持最优; (2)若c2=6,求新的最 优计划。 一、 价值系数cj的变化分析 cj54000 CBXBbx1x2x3x4x5 0x3250012-5 5x1351001-1 4 x2 10 010-12 000-1-3 4 = c25 0 5 = 52c2 0 5/2 c2 5 cj5c2 000 CBXBbx1x2x
17、3x4x5 0x3250012-5 5x1351001-1 c2 x2 10 010-12 000c2 - 55 - 2c2 最优解X*=(35,10,25,0,0)T保持不变。 (1) Cj56000 CBXBbx1x2x3x4x5 0x3250012-5 5x1351001-1 6 x2 10 010-12 j 0001-7 0x425/2001/21-5/2 5x145/210-1/203/2 6 x2 45/2 011/20-1/2 j00-1/20-9/2 x1*=45/2,x2*=45/2,x4*=25/2,x3*= x5*=0,z*=495/2 (2) 二、右端常数bi的变化分析
18、 1. 若B-1b0 , 则原最优解还是最优解, 即最优基B不变,但解的数值发生改变。 (XB=B-1b,其它 x为0) 2. 若B-1b 0, 则用对偶单纯形法继续求解。 3确定使最优基不变的资源限量范围。 用B-1b0计算。 XB= B1b 例:对于上例中的线性规划作下列分析: (1)b3在什么范围内变化,原最优基不变? (2)若b3=55,求出新的最优解。 二、右端常数bi的变化分析 cj54000 CBXBbx1x2x3x4x5 0x3250012-5 5x1351001-1 4 x2 10 010-12 000-1-3 最优基: B=(P3,P1,P2) B1= (1) B1 = =
19、0 解得40b350,即当b340,50 时,最优基B 不变 z*=5(80b3)+4(80+2b3) =80+3b3 = (2)当 b3= 55 时 = x2 x1 x5 0-11/5-3/500j 0-1/52/51020 4 03/5-1/501305 1-2/5-1/50050 -3 2 -1 -5 x5 0 -1000j -101030 x2 4 100125x15 2100-25x30 x4x3x2x1bXBCB 0045Cj 三、 增加一个新变量的分析 例2.10 (续例2.8)设企业研制了一种新产 品,对三种资源的消耗系数列向量以P6表示 P6= 。问它的价值系数c6符合什么条
20、件 才必须安排它的生产?设c6=3,新的最优 生产计划是什么? 6=c6CBB1P6 =c6(0,5,4) = c65/2 =B1P6 = Cj540003 CBXBbx1x2x3x4x5x6 0x3250012-51 5x1351001-11/2 6 x2 10 010-120 j 000-1-31/2 3x6250012-51 5x145/210-1/203/20 4 x2 10 010-120 j00-1/2-2-1/20 四、 增加新的约束条件的分析 例2.11 假设在例2.8中,还要考虑一个新的资源 约束:4x1+2x2150 4x1+2x2+x6=150 X*=(35,10,25,
21、0,0)T 4x1+2x2+x6=150 cj540000 CBXBbx1x2x3x4x5x6 0x3250012-50 5x1351001-10 4 x2 10 010-120 0x6150420001 000-1-30 Cj540000 CBXBbx1x2x3x4x5x6 0x3250012-50 5x1351001-10 4x210010-120 0 x6 150 420001 j 000-1-30 0x3250012-50 5x1351001-10 4x210010-120 0 x6 -10 000-201 j000-1-30 0x3150010-51 5x1301000-11/2 4
22、x21501002-1/2 0 x4 5 00010-1/2 j0000-3-1/2 五、 其它变化情况的分析 1. cj和bi同时变化的情况 例2.12 在例2.8中,假定c2由4上升为6,b3增加到 55,试问最优解将会发生什么变化? B1= B = = 代替最优表的b列,并把c2改为6 cj56000 CBXBbx1x2x3x4x5 0x3-250012-5 5x1251001-1 6 x2 30 010-12 j0001-7 原问题与对偶问题均非可行解,表中第一方程是 x3+2x45x5=25, 两边乘以(-1),得: x32x4+5x5=25, 再引入人工变量x6: x32x4+5x
23、5+x6=25 以x6为基变量,增添第6列,应用大M法继续求解。 Cj56000-M CBXBbx1x2x3x4x5x6 -Mx62500-1-251 5x1251001-10 6 x2 30 010-120 j 00-M-2M+15M-70 0x5500-1/5-2/510 5x13010-1/53/501/5 6 x2 20 012/5-1/50-2/5 j00-7/5-9/50-M+7/5 新的最优计划产量为x1*=30,x2*=20,z*=270。 x32x4+5x5+x6=25 2. 技术系数aij的变化 例2.13 在例2.8中,第一种产品的消耗系数改 变为 ,价值系数不变,求新的最优解。 B1= Cj54000 CBXBbx1x2x3x4x5 0x3252012-5 5x1351001-1 4 x2 10 -1/210-12 j 000-1-3 Cj54000 CBXBbx1x2x3x4x5 0x3252012-5 5x1351001-1 4 x2 10 -1/210-12 j 000-1-3 0x3-450010-3 5x1351001-1 4 x2 27.5 010-1/23/2 j000-3-1 0x51500-1/301 5x15010-1/310 4 x2 5 011/2-1/20 j 00-1/3-30
链接地址:https://www.31doc.com/p-3113444.html