第3讲对偶理论和灵敏度分析

1、第第1章章 线性规划线性规划线性规划模型及单纯形法线性规划模型及单纯形法 （2 2学时）学时）单纯形法续（单纯形法续（2 2学时）学时）对偶理论对偶理论 （2 2学时）学时）灵敏度分析及整数规划（灵敏度分析及整数规划（2 2学时）学时）第第3讲讲 对偶理论对偶理论对偶问题的提出对偶问题的提出对偶问题的经济解释对偶问题的经济解释-影子价格影子价格重重 点：对偶理论，对偶单纯形法点：对偶理论，对偶单纯形法 难难 点：对偶理论点：对偶理论基本要求：掌握对偶关系，理解对偶性质，掌握对基本要求：掌握对偶关系，理解对偶性质，掌握对偶单纯形法，偶单纯形法， 会求影子价格，会求影子价格，n引例：经营策略问题。

2、甲工厂有设备和原料引例：经营策略问题。甲工厂有设备和原料A A、B B 这些这些设备和原料可用于设备和原料可用于、两种产品的加工，每件产品加两种产品的加工，每件产品加工所需机时数，原料工所需机时数，原料A A、B B消耗量，每件产品的利润值及消耗量，每件产品的利润值及每种设备的可利用的机时数如下表。现在乙厂和甲厂协每种设备的可利用的机时数如下表。现在乙厂和甲厂协商，打算租用甲厂的设备商，打算租用甲厂的设备购买资源购买资源A和和B 。问甲厂采取。问甲厂采取哪种经营策略，是自己生产产品还是出租设备、出让原哪种经营策略，是自己生产产品还是出租设备、出让原材料？如果出租设备、出让原材料，在和乙厂协商时

3、出材料？如果出租设备、出让原材料，在和乙厂协商时出租设备和出让原材料租设备和出让原材料A,BA,B的底价应是多少？的底价应是多少？对偶问题的提出对偶问题的提出 设设 备备原料原料A A原料原料B B 1 4 0 2 0 4 80台时 160kg 120kg23盈利盈利自己生产：自己生产：0, 120 41604 802. .32zmax21212121xxxxxxt sxx原问题原问题引例分析：l设设y y1 1 , ,y y2 2和和y y3 3分别表示出租单位设备台时分别表示出租单位设备台时的租金和出让单位原材料的租金和出让单位原材料A,BA,B的附加额的附加额2421 yy=80y1+1

4、60y2+120y3出售资源对偶问题l显然商人希望总的收购价越小越好显然商人希望总的收购价越小越好l工厂希望出售资源后所得不应比生产产品所得少工厂希望出售资源后所得不应比生产产品所得少 34231 yy3,2,1,0 iyi .ts目标函数目标函数 min0, 120 41604 802. .32zmax21212121xxxxxxt sxx0, 120 41604 802. .32zmax21212121xxxxxxt sxx例例1400421A)3,2( C12016080b它的对偶问题是：它的对偶问题是：YAYA Cmin = YbYbY Y0 012016080Y)3,2(400421

5、 YY Y=（y1，y2，y3）3 , 2 , 1, 034224. .3121iyyyyytsi32112016080minyyy1 1.5.1 .5.1 原问题与对偶问题的关系原问题与对偶问题的关系( (对称形式对称形式) )线性规划的对偶理论线性规划的对偶理论0XbAXCX. .max :t sz原问题0YCYAYb. .min :ts对偶问题TmnmTnbbbbcccCyyyYxxxX),(),(),(),(21212121上两式中上两式中mnmmnnaaaaaaaaaA212222111211 0,. .min21221122222112112211112211mnmmnnnmmmm

6、mmyyycyayayacyayayacyayayatsybybyb 把把对对偶偶问问题题展展开开0,max 2112121112112211 nmnmnmmnnnxxxbbxxxaaaaaaxcxcxcz0,),(),(min21112111211212211 mnmnmmnmmmyyycccaaaaaayyyybybyb 0,. .max :21221122222112112211112211nmnmnnnnmnmnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz原问题展开 原关系minwnxxx21mnmmnnaaaaaaaaa212222111211对偶关系myyy

7、21 mbbb21 nccc21wzminmax maxzxy原问题与对偶问题的对称形式原问题与对偶问题的对称形式 标准标准( (max,max, ) )型的对偶变换型的对偶变换n目标函数由目标函数由 max max 型变为型变为 min min 型型n对应原问题每个约束行有一个对偶变量对应原问题每个约束行有一个对偶变量 yi，i=1,2,1,2, ,m mn对偶问题约束为对偶问题约束为 型，有型，有 n n 行行n原问题的价值系数原问题的价值系数 C C 变换为对偶问题的右端项变换为对偶问题的右端项n原问题的右端项原问题的右端项 b b 变换为对偶问题的价值系数变换为对偶问题的价值系数n原问

8、题的技术系数矩阵原问题的技术系数矩阵 A A 转置后成为对偶问题的技术转置后成为对偶问题的技术系数矩阵系数矩阵n原问题与对偶问题互为对偶原问题与对偶问题互为对偶l对偶问题可能比原问题容易求解对偶问题可能比原问题容易求解l对偶问题还有很多理论和实际应用的意义对偶问题还有很多理论和实际应用的意义原问题与对偶问题的结构关系原问题与对偶问题的结构关系n原问题与对偶问题中的目标函数的优化方向相反（前原问题与对偶问题中的目标函数的优化方向相反（前者为极大，后者为极小）者为极大，后者为极小）n原问题的每个约束条件对应于对偶问题的一个决策变原问题的每个约束条件对应于对偶问题的一个决策变量，且约束条件的资源系数

9、（右端的常数项）为相应量，且约束条件的资源系数（右端的常数项）为相应决策变量的价值系数决策变量的价值系数n原问题的每个决策变量对应于对偶问题的一个约束条原问题的每个决策变量对应于对偶问题的一个约束条件，且决策变量的价值系数为相应约束条件的右端常件，且决策变量的价值系数为相应约束条件的右端常数项数项n对偶问题中的系数矩阵为原问题中的系数矩阵的转置对偶问题中的系数矩阵为原问题中的系数矩阵的转置n原问题约束条件中的小于等于符号对应于对偶问题中原问题约束条件中的小于等于符号对应于对偶问题中的对偶变量取非负约束，原问题中决策的对偶问题非的对偶变量取非负约束，原问题中决策的对偶问题非负约束在对偶问题中体现

10、为相应的约束条件取大于等负约束在对偶问题中体现为相应的约束条件取大于等于符号于符号 非非标准标准型的对偶变换型的对偶变换0,510342023. .54max 21221212121xxxxxxxxtsxxz不限原线性规划问题例 0, 551033420223.554max)(max, 221221221221221221xxxxxxxxxxxxxxxtsxxxz型标准问题化为0,532532443. .551020min 43214321432143214321wwwwwwwwwwwwwwwwtswwww则应用标准型对偶变换规不限经整理得令3213213213214332211, 0, 05

11、32443. .51020min:, yyyyyyyyytsyyywwywywy 对偶变换的规则对偶变换的规则max=5y1+4y2+6y3y1 +2y2y1 + y3-3y1+2y2+y3y1- y2+ y3=23-5 1y1 0，y2 0,y3无约束无约束对偶问题例例3 3 写出线性规划问题的对偶问题写出线性规划问题的对偶问题minz=2x1+3x2-5x3+x4原问题原问题 x1+x2- 3x3 +x4 5 2x1+ 2x3 -x44 x2 + x3 +x4=6 x1 0 ,x2, x3 0, x4无约束（1）对称性：对偶的对偶就是原始问题min =-CXs.t. -AX -bX 0ma

12、x z=-Ybs.t. -YA -CY 0min =Ybs.t. YA C Y 0max z=CXs.t. AX bX 0对偶的定义对偶的定义对偶的定义对偶的定义1.5.2 对偶问题的基本性质对偶问题的基本性质 为了便于讨论，下面不妨总是假设为了便于讨论，下面不妨总是假设 0XbAX.CXmax :tsz原原问问题题 0YCYA.Ybmin :ts 对对偶偶问问题题 0YCAY0XbXA,Y,X :故有故有题的可行解题的可行解分别为原问题和对偶问分别为原问题和对偶问由于由于证证XYbYXC (2) 弱对偶性: :若若 是原问题的可行解，是对偶是原问题的可行解，是对偶问题的可行解。则存在问题的可

13、行解。则存在 XAbYY XAXCY bYYXC XA对偶问题对偶问题( (min)min)的任何可行解的任何可行解Y Y，其目标函数值总是其目标函数值总是不小于原问题不小于原问题( (max)max)任何可行解任何可行解X X的目标函数值的目标函数值 弱弱对偶定理推论对偶定理推论原问题的任何可行解目标函数值是其对偶问题目标函原问题的任何可行解目标函数值是其对偶问题目标函数值的下限；对偶问题的任何可行解目标函数值是数值的下限；对偶问题的任何可行解目标函数值是原问题目标函数值的上限原问题目标函数值的上限n如果原如果原( (对偶对偶) )问题为无界解，则其对偶问题为无界解，则其对偶( (原原) )

14、问题无问题无可行解可行解n如果原如果原( (对偶对偶) )问题有可行解，其对偶问题有可行解，其对偶( (原原) )问题无可问题无可行解，则原问题为无界解行解，则原问题为无界解n当原问题当原问题( (对偶问题对偶问题) )为无可行解为无可行解, ,其对偶问题其对偶问题( (原问原问题题) )或具有无界解或无可行解或具有无界解或无可行解bYYXC XA (3)强对偶性证：由弱对偶定理推论证：由弱对偶定理推论1 1，结论是显然的。，结论是显然的。 XYbYXC XY若是原问题的可行解，是对偶问题可行解，当若是原问题的可行解，是对偶问题可行解，当 , , , , 分别是相应问题的最优解分别是相应问题的

15、最优解XCbY bYXC 若若bYbY 是使目标函数取最小值的解，因此是最优解是使目标函数取最小值的解，因此是最优解 Y可行解是最优解的性质可行解是最优解的性质(最优性准则定理最优性准则定理) (4) (4) 对偶对偶定理定理 若原问题和对偶问题两者皆可行若原问题和对偶问题两者皆可行,则两者均则两者均有最优解有最优解,且此时目标函数值相等且此时目标函数值相等.第第1部分部分:证明两者均有最优解证明两者均有最优解证明分两部分证明分两部分由于原问题和对偶问题均可行由于原问题和对偶问题均可行,根据弱根据弱对偶性对偶性,可知两者均有界可知两者均有界,于是均有最于是均有最优解优解.bYXC 第第2部分部

16、分:证明有相同的目标函数值证明有相同的目标函数值 设设 为原问题的最优解为原问题的最优解X它所对应的基矩阵是它所对应的基矩阵是B B，则其检验数满足则其检验数满足 C C C CB BB B 1 1A A 0 0 bBX1 因此有对偶问题目标函数值因此有对偶问题目标函数值而原问题最优解的目标函数值而原问题最优解的目标函数值为为01 YCAYBCYB，则则有有令令显然显然 为对偶问题的可行解。为对偶问题的可行解。YbBCbYB1 bBCXCzB1 证毕故由最优解准则定理可知故由最优解准则定理可知 为对偶问题的最优解为对偶问题的最优解. .Y对偶定理推论对偶定理推论n根据对偶定理第根据对偶定理第2

17、 2部分的证明部分的证明, ,可以得出可以得出: :若互为若互为对偶的线性规划问题中的任一个有最优解对偶的线性规划问题中的任一个有最优解, ,则另则另一个也有最优解一个也有最优解, ,且目标函数值相等且目标函数值相等. . 综上所述综上所述, ,一对对偶问题的解必然是下列三种一对对偶问题的解必然是下列三种情况之一情况之一: :n原问题和对偶问题都有最优解原问题和对偶问题都有最优解n一个问题具有无界解一个问题具有无界解, ,另一个问题无可行解另一个问题无可行解n原问题和对偶问题都无可行解原问题和对偶问题都无可行解 (5)互补松弛互补松弛定理定理证：由定理所设，可知有 YXSXSYYX设设 , ,

18、 分别是原问题和对偶问题的可行解，分别是原问题和对偶问题的可行解， 为为原问题的松弛变量的值，为对偶问题剩余变量的原问题的松弛变量的值，为对偶问题剩余变量的值。值。 , , 分别是原问题和对偶问题最优解的充分分别是原问题和对偶问题最优解的充分必要条件是必要条件是0 SSYXXY0, SSXXbXXA0, SSYYCYAY分别以分别以 左乘左乘(1)(1)式，以式，以 右乘右乘(2)(2)式后，两式相减，得式后，两式相减，得 YXXCbYXYXYSS 0 XYXYSS若若根据最优解判别定理，根据最优解判别定理， 分别是原问题和对偶问题最优分别是原问题和对偶问题最优解。反之亦然。解。反之亦然。YX

19、,证毕。（1）（2）0 SSYXXY即即0 XCbYXCbY max z=CXs.t.AX+XS=bX, XS 0min w=Ybs.t. AY-YS=CY, YS 0XYS=0YXS=0mn=YYSA-ICn=AXSIbnmmX原始问题和对偶问题变量、松弛变量的维数原始问题和对偶问题变量、松弛变量的维数原始问题和对偶问题最优解之间的互补松弛关系原始问题和对偶问题最优解之间的互补松弛关系maxz=CX s.t. AX+XS=b X, XS0min w=bYs.t. AY-YS=C Y, YS0maxz=CXs.t. AXb X 0min w=bYs.t. AYC Y0对偶引进松弛变量引进松弛变

20、量XYS=0 YXS=0X，XsY，Ysy1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1 xn+i xn+m 对偶问题的变量对偶问题的变量原始问题的松弛变量原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m; j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于0原始问题的变量原始问题的变量对偶问题的松弛变量对偶问题的松弛变量(6)原问题单纯形表检验数行与对偶问题解的关系原问题单纯形表检验数行与对偶问题解的关系n原问题单纯形表检验数的相反数对应对偶原问题单纯形表检验数的相反数对应对偶问题的一个基解问题的一个基解. .显然显然, ,原问题最终单纯

21、形原问题最终单纯形表检验数的相反数对应对偶问题的一个基表检验数的相反数对应对偶问题的一个基可行解可行解BXNXSX1SYNBCCBN1 1 BCB02SY Y 证：标准化后的原问题和对偶问题的表达式为证：标准化后的原问题和对偶问题的表达式为：0,CXmax : SSXXbXAXz原原问问题题0,min :SSYYCYYAYb对偶问题若若B B是是A A中的一个基，中的一个基，A=A=（B B，N N） 0,XCmax :SNBSNBNNBBXXXbXNXBXXCz原原问问题题改改写写为为),(0,Ybmin :212121SSSSSNSBSYYYYYYCYYNCYYB 对对偶偶问问题题为为原问

22、题解为原问题解为XB=B-1b ，BSCYYB 1N= CN-CBB-1N，Z=CBB-1b对偶问题的约束条件：对偶问题的约束条件：1 BCYB令令011 BBCCYBBS01 SYNSCYYN 2NBCCYBNS12 BXNXSX1SYNBCCBN1 1 BCB02SY Y 检验数：检验数：B= CB-CBB-1B=0，N= CN-CBB-1N，S=CBB-1原问题单纯形表检验数行与对偶问题解的关系原问题单纯形表检验数行与对偶问题解的关系结论：结论：v单纯形表中的检验数行和对偶问题的解单纯形表中的检验数行和对偶问题的解仅差一个符号vyi等于原问题的第等于原问题的第i个方程中的松弛变量所对应的

23、检验个方程中的松弛变量所对应的检验 数的负数数的负数v单纯形法迭代时，原问题解为基可行解，相应的单纯形法迭代时，原问题解为基可行解，相应的检验数对应对偶问题的一个解，在原问题没有得到检验数对应对偶问题的一个解，在原问题没有得到最优解之前，对偶问题的解为非可行解最优解之前，对偶问题的解为非可行解基可行解基可行解非可行解基可行解目标函数对偶问题原问题YbCX YbCX 无可行解无界解原问题为可行解时原问题为可行解时，对偶问题不一定，对偶问题不一定有可行解，当原问有可行解，当原问题为最优解，对偶题为最优解，对偶问题一定有最优解问题一定有最优解例例4 0,12 2.zmax32132132121xxx

24、xxxxxxstxx试用对偶理论证明该线试用对偶理论证明该线性规划问题无最优解。性规划问题无最优解。证：证：该问题存在可行解，该问题存在可行解，X=（0，0，0）；）；对偶问题为：对偶问题为：212inyym 12.21yyst121 yy021 yy0,21 yy由第一个约束条件可知由第一个约束条件可知对偶问题无可行解，因对偶问题无可行解，因此，原问题有可行解，此，原问题有可行解，无最优解。无最优解。例例5： 0,332 432.32532min54321543215432154321xxxxxxxxxxxxxxxstxxxxx 试用对偶理论找出原问题的最优解。试用对偶理论找出原问题的最优解。解：解：原问题的对偶问题为：原问题的