《对偶及灵敏度分析》由会员分享，可在线阅读，更多相关《对偶及灵敏度分析（83页珍藏版）》请在金锄头文库上搜索。
1、第二章线性规划的对偶理论 及灵敏分析2.1 线性规划的对偶理论2.1.1 线性规划原问题与对偶问题的表达形式 任何线性规划问题都有其对偶问题 对偶问题有其明显的经济含义假设有商人要向厂方购买资源A和B，问他们谈判原料 价格的模型是怎样的？四种产品例2.1.1设A、B资源的出售价格分别为 y1 和 y2显然商人希望总的收购价越小越好 工厂希望出售资源后所得不应比生产产品所得少目标函数 min g(y)=25y1+15y2 (商人的目标)2.1.1 线性规划原问题与对偶问题的表达形式2.1.1 线性规划原问题与对偶问题的表达形式2.1.1 线性规划原问题与对偶问题的表达形式2.1.2 (max,)
2、标准型的对偶变换 目标函数由 max 型变为 min 型 对应原问题每个约束行有一个对偶变量 yi，i=1,2,m 对偶问题约束为 型，有 n 行 原问题的价值系数 C 变换为对偶问题的右端项(资源向 量) 原问题的右端项(资源向量) b 变换为对偶问题的价值系 数 原问题的技术系数矩阵 A 转置后成为对偶问题的技术 系数矩阵矩阵 原问题与对偶问题互为对偶 对偶问题可能比原问题容易求解 对偶问题还有很多理论和实际应用的意义表2.1.1 对偶变换的规则 约束条件的类型与非负条件对偶 非标准的约束条件类型对应非正常的非负条件 对偶变换是一一对应的2.1.3 非标准型的对偶变换2.2 线性规划的对偶
3、定理2.2.1 弱对偶定理 定理 对偶问题(min)的任何可行解Y0，其目标函数值总是 不小于原问题(max)任何可行解X0的目标函数值z，即CX0 Y0 A 为了便于讨论，下面不妨总是假设弱对偶定理几何意义 当CX时（无界解），则对偶问题无解 当Yb 时（无界解），则原问题无解 当CX、 Yb有最优解时， CX0= Y0 b弱对偶定理推论CXYb2.2.2 最优解判别定理定理 若原问题的某个可行解X0的目标函数值与对偶问题 某个可行解Y0的目标函数值相等，则X0, Y0分别是相应问 题的最优解 证：由弱对偶定理推论3，结论是显然的。即CX0 = Y0b CX, Y0b = CX0 Yb 。
4、证毕。2.2.3 主对偶定理(强对偶性、对偶定理） 定理 如果原问题和对偶问题都有可行解，则它们都有最 优解，且它们的最优解的目标函数值相等。 证：由弱对偶定理推论3可知，原问题和对偶问题的目标 函数有界，故一定存在最优解。现证明定理的后一句话。 主对偶定理的证明证：现证明定理的后一句话。设 X0 为原问题的最优解，它所对应的基矩阵是 B， X0= B1 b，则其检验数满足 C CBB1A 0令 Y0= CBB1，则有 Y0 A C ；而对原问题松弛变量 的检验数有 0 CBB1I 0，即 Y0 0 。显然Y0为对偶问题的可行解。因此有对偶问题目标函 数值， = g(Y0) = Y0b = C
5、BB1 b而原问题最优解的目标函数值为z = f(X0) = CX0 = CBB1 b 故由最优解判别定理可知Y0 为对偶问题的最优解。证毕。 该定理的证明告诉我们一个非常重要的概念：对偶 变量的最优解等于原问题松弛变量的机会成本。 即对偶变量的最优解是原问题资源的影子价格主对偶定理的证明 问题： 由此定理的可知，对偶问题的最优解的表达式Y*=？ Y* = CBB1 求Y*是否有必要重新的求解对问题？不必，可能从原问题的单纯表中获得 在线性规划问题的最优解中，如果对应某一约束条件 的对偶变量值为非零，则该约束条件取严格等式；反之 如果约束条件取严格不等式，则其对应的对偶变量一定 为零。即：2.
6、2.5 互补松驰性定理证明：1）证明：2）例：min = 5y1+y2 3y1+ y2 9y1+ y2 5y1+8y2 8 y1 , y2 0(P)maxZ=9x1+5x2 +8x3 3x1+x2+ x3 5x1+x2+8x3 1 x1 , x2 , x3 0(D)x1 x2 x3 x4 x5CB xB 9 5 8 0 00 x4 5 3 1 1 1 00 x5 1 1 1 8 0 19 5 8 0 00 x4 2 0 -2 -23 1 -39 x1 1 1 1 8 0 10 -4 -64 0 -9(P)最优解(0, 9, 0, 4, 64), = 9n = 3 m = 2xn+i yi =0
7、 ( i =1m ) ( i =1 ,2 )xj ym+j =0 ( j =1n ) xj y2+j( j =13 )x3+i yix1 y3x2 y4x3 y5x4 y1x5 y2例： min = 2x1+3x2+5x3+2x4+3x5 其对偶解 y1 =4/5 y2 =3/5 Z =5 用对偶理论求(P)的最优解x1+x2+2x3+x4+3x5 42x1 -x2+3x3+x4+x5 3 xi 0 ( i =1 5 )(P)解：(D)为maxZ =4y1+3y2y1+2y2 2 y1 - y2 3 2y1+3y2 5 y1+y2 2 3y1+y2 3 y1 , y2 0将y1 ，y2 代入，
8、知, , 为严格不等式 x2 = x3 = x4 = 0 x = (1, 0, 0, 0, 1)TZ=5由y1 ，y2 0知原约束为等式 x1+3x5 =42x1+x5 =32.3 影子价格1、Z= CBB-1b + (CN - CBB-1 N)XN (*)Z= Z(b) b为资源对(*)求偏导： Z b= CBB-1= y对偶解y：b 的单位改变量所引起的目标函数改变量。2、对偶的经济解释1)原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨 ）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）2)对偶问题资源限量（吨）资源价格（元/吨
9、）总利润（元）对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为m种资源的影子价格（ Shadow Price）原始和对偶问题都取得最优解时，最大利润 max z=min y3、资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺 影子价格越小，说明这种资源相对不紧缺 如果最优生产计划下某种资源有剩余，这种资源的影子 价格一定等于0y1y2ym4、产品的机会成本机会成本表示减少一件产品所节省的资源可以增加的利润当资源的市场价低于影子价格时，可以买进这种资源。增加单位资源可以增加的利润减少一件产品可以节省的资源机会成本利润差额成本5、产品的差额成本（Reduced Cost）差
10、额成本=机会成本 利润6、互补松弛关系的经济解释在利润最大化的生产计划中（1）边际利润大于0的资源没有剩余（2）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产以例1.1为例，求 原问题与对偶问题的最优解原问题：原问题的标准形：对偶问题：以例1.1为例，求 原问题与对偶问题的最优解用单纯形法解原问题的最优解：以例1.1为例，求 原问题与对偶问题的最优解原问题最优解： x1=2 ; x2=6;max z= 6x1 +4x2 =36铜资源的影子价格：1； 铅资源的影子价格：2经济意义：当铜、铅分别增加工厂单位时，可使总收入 分别是增加1、2对偶问
11、题最优解： y1=1 ; y2=2; y3=0; min = 10x1 +8y2 +7y3 =362.4 对偶单纯形法思路：(max型)单纯形法：找基B，满足B-1b0，但 C - CBB-1 A不全 0，（即检 验数）。迭代保持B-1b0，使C -CBB-1 A 0，即CBB-1 A C对偶单纯形法：找基B，满足C - CBB-1 A 0，但B-1b不全0迭代 保持C -CBB-1 A 0，使B-1b0例1： Max Z =2X1 +X2X1+ X2 + X3 = 52X2 + X3 54X2 +6X3 9X1 , X2 , X3 0maxZ=2X1 +X2X1+ X2 + X3 = 52X
12、2 + X3 +X4 = 5-4X2 -6X3 +X5 =-9X1 X5 02 1 0 0 0X1 X2 X3 X4 X5CB XB 10 0 -1 -2 0 02 X1 5 1 1 1 0 00 X4 5 0 2 1 1 00 X5 -9 0 (-4) -6 0 1XB 31/4 0 0 -1/2 0 -1/4X1 11/4 1 0 -1/2 0 1/4X4 1/2 0 0 -2 1 1/2X2 9/4 0 1 3/2 0 -1/4 37对偶单纯形法基本步骤 max型(min型)(1)、作初始表，要求全部j 0 (0)(2)、判定： B-1 b全0，停。否则，取max B-1 b =(B-1 b)l B-1 b0某xj 从0 ，xil不能变0为保持j 0 ，即对偶解可行性例2minZ=2X1 +3X2 +4X3X1+2X2 + X3 32X1 - X2 +3X3 4X1 , X2 , X3 0maxZ=-2X1 -3X2 -4X3-X1 -2X2 - X3 +X4 =- 3-2X1+ X2 -3X3
