《运筹学第2章对偶理论ppt课件》由会员分享，可在线阅读，更多相关《运筹学第2章对偶理论ppt课件（121页珍藏版）》请在金锄头文库上搜索。
1、-1-China University of Mining and Technology运筹学 Chapter2 对偶理论对偶理论 ( Duality Theory )单纯形法的矩阵描述单纯形法的矩阵描述对偶问题的提出对偶问题的提出线性规划的对偶理论线性规划的对偶理论对偶问题的经济解释影子价格对偶问题的经济解释影子价格对偶单纯形法对偶单纯形法灵敏度分析灵敏度分析(选讲选讲)掌握掌握WinQSB软件求解对偶规划软件求解对偶规划本章主要内容：本章主要内容：本章主要内容：本章主要内容：-2-China University of Mining and Technology运筹学 学习要点：学习要点：
2、1. 理解对偶理论，掌握描述一个线性规划问题理解对偶理论，掌握描述一个线性规划问题 的对偶问题。的对偶问题。 2. 能够运用对偶单纯形法来求解线性规划问题。能够运用对偶单纯形法来求解线性规划问题。 3. 会用互补松弛条件来考虑一对对偶问题的界。会用互补松弛条件来考虑一对对偶问题的界。 4. 了解影子价格、灵敏度分析以及用了解影子价格、灵敏度分析以及用WinQSB求求 解对偶规划问题。解对偶规划问题。-29-China University of Mining and Technology运筹学 Max Z=40x1+ 50x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x
3、2 0s.ty1y2y3Min W = 30y1+ 60y2 + 24y3 y1+3y2 + 0y3 402y1+2y2 + 2y3 50 y1 , y2 , y3 0s.tMax W= -30y1- 60y2 - 24y3 y1+3y2 + 0y3 y4 = 402y1+2y2 + 2y3 y5 = 50 y1 , y2 , y3 , y4 , y5 0s.t例例4二、二、二、二、 对偶问题的解对偶问题的解对偶问题的解对偶问题的解线性规划的对偶理论线性规划的对偶理论-30-China University of Mining and Technology运筹学 Max W= -30y1- 6
4、0y2 - 24y3 +0(y4 + y5 )-M (y6 + y7 ) y1+3y2 + 0y3 y4 + y6 = 402y1+2y2 + 2y3 y5 + y7 = 50 y1 , y2 , y3 , y4 , y5 0s.tcj-30-60-2400-M-MB-1bcByBy1y2y3y4y5y6y7-My6130-10104040/3-My72220-1015050/2j3M-305M-602M-24-M-M00-90M线性规划的对偶理论线性规划的对偶理论-31-China University of Mining and Technology运筹学 cj-30-60-2400-M-
5、MB-1bcByBy1y2y3y4y5y6y7-60y21/310-1/301/3040/3-My74/3022/3-1-2/3170/335/3j4M/3-1002M-242M/3+20-M-5M/3+200800-70M/3-60y21/310-1/301/3040/340-24y32/3011/3-1/2-1/31/235/335/2j600-12-12-M+12-M+12-1080-60y201-1/2-1/21/41/2-1/415/2-30y1103/21/2-3/4-1/23/435/2j00-9-15-15/2-M+30-M-15/2-975线性规划的对偶理论线性规划的对偶理论
6、-32-China University of Mining and Technology运筹学 cj4050000 B-1bcBxBx1x2x3x4x540x1101/2-1/20150x5003/2-1/21950x201-3/41/4015/2j00-35/2-15/20975 Max Z=40x1+ 50x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 0s.t x1+2x2 +x3 = 303x1+2x2 +x4 =60 2x2 +x5 = 24 x1 x5 0s.t线性规划的对偶理论线性规划的对偶理论-33-China University of Mini
7、ng and Technology运筹学 线性规划的对偶理论线性规划的对偶理论-34-China University of Mining and Technology运筹学 原问题与其对偶问题的变量与解的对应关系： 在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量。线性规划的对偶理论线性规划的对偶理论-35-China University of Mining and Technology运筹学 XBb原问题的变量原问题的变量原问题的松弛变量原问题的松弛变量x1x2x3x4x5x115101/2-1/20x59003/2-1/21x215/2013/4-1
8、/4000-35/2-15/20YBb对偶问题对偶问题的变量的变量对偶问题的对偶问题的剩余变量剩余变量y1y2y3y4y5y215/201-1/2-1/21/4y135/2103/21/2-3/400-9-15-15/2原问原问题最题最优表优表对偶对偶问题问题最优最优表表 Max Z=40x1+ 50x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 0s.tMin W = 30y1+ 60y2 + 24y3 y1+3y2 + 0y3 402y1+2y2 + 2y3 50 y1 , y2 , y3 0s.t线性规划的对偶理论线性规划的对偶理论-36-China Univ
9、ersity of Mining and Technology运筹学 性质性质1 对称性定理：对偶问题的对偶是原问题对称性定理：对偶问题的对偶是原问题 min W= Y bs.t. YA C Y 0max Z=C Xs.t. AXb X 0三、三、三、三、 对偶原理对偶原理对偶原理对偶原理线性规划的对偶理论线性规划的对偶理论-37-China University of Mining and Technology运筹学 min z= - CXs.t. -AX-bX 0maxw= -Ybs.t. -YA-C Y 0min w=Ybs.t. YAC Y 0max z=CXs.t. AXb X 0对
10、偶的对偶的定义定义对偶的对偶的定义定义简要证明：简要证明：线性规划的对偶理论线性规划的对偶理论-38-China University of Mining and Technology运筹学 性质性质2 弱对偶原理弱对偶原理(弱对偶性弱对偶性)：设：设 和和 分别是问题分别是问题(P)和和(D)的可行解，则必有的可行解，则必有推论推论1: 原问题任一可行解的目标函数值是其对偶问题目标函数值原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任意可行解的目标函数值是其原问题目的下界；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。标函数值的上界。证明：证明：(
11、1) 当当X和和Y为原问题和对偶问题的一个可行解为原问题和对偶问题的一个可行解有有原问题目标函数值原问题目标函数值对偶问题目标函数值对偶问题目标函数值线性规划的对偶理论线性规划的对偶理论-39-China University of Mining and Technology运筹学 推论推论2: 在一对对偶问题在一对对偶问题P和和D中，若其中一个问题可行但中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；反之不成立。这也是对目标函数无界，则另一个问题无可行解；反之不成立。这也是对偶问题的无界性。偶问题的无界性。假设假设P为无界解，那么为无界解，那么D无可行无可行解；解；假设假设D为无
12、界解，那么为无界解，那么P无可行无可行解。解。线性规划的对偶理论线性规划的对偶理论推论推论3：在一对对偶问题：在一对对偶问题P和和D中，若一个可行如中，若一个可行如P），），而另一个不可行如而另一个不可行如D），则该可行的问题目标函数值无界。），则该可行的问题目标函数值无界。-40-China University of Mining and Technology运筹学 已知原问题已知原问题(LP)，试估计它的目标函数值的界试估计它的目标函数值的界,并验证弱对偶定理并验证弱对偶定理.例例5线性规划的对偶理论线性规划的对偶理论-41-China University of Mining and
13、Technology运筹学 解：解：解：解：问题问题(LP)的对偶问题的对偶问题(DP)为为 (DP)线性规划的对偶理论线性规划的对偶理论-42-China University of Mining and Technology运筹学 由观察可知由观察可知 分别是原问题和对偶问题的可行解。分别是原问题和对偶问题的可行解。 ，弱对偶定理成立。，弱对偶定理成立。且由推论且由推论1知，对偶问题目标函数知，对偶问题目标函数W的下界为的下界为10，原问题目，原问题目标函数标函数Z的上界为的上界为40。且原问题的目标函数值为且原问题的目标函数值为对偶问题的目标函数值为对偶问题的目标函数值为故故线性规划的对
14、偶理论线性规划的对偶理论-43-China University of Mining and Technology运筹学 例：利用对偶性质判断下面问题有无最优解例：利用对偶性质判断下面问题有无最优解例例6解：此问题的对偶问题为解：此问题的对偶问题为不能成立，因此对偶问题不不能成立，因此对偶问题不可行。故由推论可行。故由推论3知原问题知原问题无界。无界。为可行解为可行解线性规划的对偶理论线性规划的对偶理论-44-China University of Mining and Technology运筹学 性质性质3 最优性定理：假设最优性定理：假设 是原问题的可行解，是原问题的可行解， 是其对偶是其
15、对偶问题的可行解，并且问题的可行解，并且:那么那么 是原问题的最优解，是原问题的最优解， 是其对偶问题的最优解。是其对偶问题的最优解。线性规划的对偶理论线性规划的对偶理论-45-China University of Mining and Technology运筹学 性质性质4 强强(主主)对偶性：若原问题及其对偶问题均具有可行解，对偶性：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。则两者均具有最优解，且它们最优解的目标函数值相等。还可推出另一结论：若一对对偶问题中的任意一个有最优解，还可推出另一结论：若一对对偶问题中的任意一个有最优解，则另一个也有最优
16、解，且目标函数最优值相等；若一个问题则另一个也有最优解，且目标函数最优值相等；若一个问题无最优解，则另一问题也无最优解。无最优解，则另一问题也无最优解。一对对偶问题的关系，有且仅有下列三种：一对对偶问题的关系，有且仅有下列三种：都有最优解，且目标函数最优值相等；都有最优解，且目标函数最优值相等；两个都无可行解；两个都无可行解；一个问题无界，则另一问题无可行解。一个问题无界，则另一问题无可行解。线性规划的对偶理论线性规划的对偶理论-46-China University of Mining and Technology运筹学 证明：当证明：当X*为原问题的一个最优解，为原问题的一个最优解，B为相
17、应的最优基，通过引为相应的最优基，通过引入松弛变量入松弛变量Xs，将问题，将问题(P)转化为标准型转化为标准型令令CCBCN0解解基系数基系数基变量基变量XBXNXsCBXBIB-1NB-1B-1b0CN -CBB-1N -CBB-1CBB-1bCXAC-CBB-1A说明说明Y*可行可行线性规划的对偶理论线性规划的对偶理论-47-China University of Mining and Technology运筹学 问题问题:（1由性质由性质4可知，对偶问题最优解的表达式可知，对偶问题最优解的表达式 Y*=?（2求求 Y*是否有必要重新求解是否有必要重新求解(D)?不用。可以从原问题不用。可
18、以从原问题P的单纯形终表获得。的单纯形终表获得。CCBCN0解解基系数基系数基变量基变量XBXNXsCBXBIB-1NB-1B-1b0CN -CBB-1N -CBB-1CBB-1b线性规划的对偶理论线性规划的对偶理论-48-China University of Mining and Technology运筹学 性质性质5 互补松弛性：设互补松弛性：设X0和和Y0分别是分别是P问题问题 和和 D问题问题 的可的可行解，则它们分别是最优解的充要条件是：行解，则它们分别是最优解的充要条件是：其中：其中：Xs、Ys为松弛变量。为松弛变量。在线性规划问题的最优解中，若对应某一约束条件的对偶变量值为非零
19、，则在线性规划问题的最优解中，若对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；另一方面，如果约束条件取严格不等式，则其对应该约束条件取严格等式；另一方面，如果约束条件取严格不等式，则其对应的变量一定为零。的变量一定为零。紧约束与紧约束与紧约束与紧约束与松约束松约束松约束松约束线性规划的对偶理论线性规划的对偶理论-50-China University of Mining and Technology运筹学 证证: (: (必要性）必要性）原问题原问题 对偶问题对偶问题线性规划的对偶理论线性规划的对偶理论-51-China University of Mining and Tech
20、nology运筹学 Max Z=CXs.t.AX+XS=bX, XS 0X, XS 0Min W=Ybs.t. YA-YS=CW, WS 0XTYS=0YTXS=0mn=YYSAT-ICn=AXSIbnmmX原始问题和对偶问题变量、松弛变量的维数原始问题和对偶问题变量、松弛变量的维数线性规划的对偶理论线性规划的对偶理论-52-China University of Mining and Technology运筹学 y1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1 xn+i xn+m 对偶问题的变量对偶问题的变量 对偶问题的松弛变量对偶问题的松弛变量 原始问题的变量原始
21、问题的变量 原始问题的松弛变量原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m; j=1,2,n)在一对变量中，其中一个大于在一对变量中，其中一个大于0，另一个一定等于，另一个一定等于0线性规划的对偶理论线性规划的对偶理论-53-China University of Mining and Technology运筹学 性质性质5的应用：的应用：该性质给出了已知一个问题最优解求另一个问题最优解该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知的方法，即已知Y求求X或已知或已知X求求Y互补松弛条件互补松弛条件由于变量都非负，要使求和式等于零，则必定每一分量为零，由于变
22、量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：因而有下列关系： 若若Y0，则，则Xs必为必为0；若；若X0，则，则Ys必为必为0利用上述关系，建立对偶问题或原问题的约束线性方程组，利用上述关系，建立对偶问题或原问题的约束线性方程组，方程组的解即为最优解。方程组的解即为最优解。线性规划的对偶理论线性规划的对偶理论-54-China University of Mining and Technology运筹学 已知线性规划已知线性规划的最优解是的最优解是X=(6,2,0)T,求其对偶问题的最优解求其对偶问题的最优解Y。解：写出原问题的对偶问题，即解：写出原问题的对偶问题，即标准化
23、标准化例例7线性规划的对偶理论线性规划的对偶理论-55-China University of Mining and Technology运筹学 设对偶问题最优解为设对偶问题最优解为Y(y1，y2),由互补松弛性定理可知，由互补松弛性定理可知，X和和 Y满足：满足：即：即：因为因为x10，x20，所以对偶问题的第一、二个约束的松弛，所以对偶问题的第一、二个约束的松弛变量等于零，即变量等于零，即y30，y40，带入方程中：，带入方程中：解此线性方程组得解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为：从而对偶问题的最优解为：Y=(1,1)，最优值，最优值w=26。线性规划的对偶理论线性
24、规划的对偶理论-56-China University of Mining and Technology运筹学 已知线性规划已知线性规划 的对偶问题的最优解为的对偶问题的最优解为Y=(0,-2)，求原问题的最优解。，求原问题的最优解。解解: 对偶问题是对偶问题是标准化标准化例例8线性规划的对偶理论线性规划的对偶理论-57-China University of Mining and Technology运筹学 设原问题最优解为设原问题最优解为X(x1，x2 ，x3)T ,由互补松弛性定理知，由互补松弛性定理知，X和和 Y满足：满足：将将Y带入由方程可知，带入由方程可知，y3y50，y41。y2
25、=-20 x50又又y4=10 x20将将x2，x5分别带入原问题约束方程中，得：分别带入原问题约束方程中，得：解方程组得：解方程组得：x1=-5,x3=-1, 所以原问题的最优解为所以原问题的最优解为X=(-5,0,-1)，最优值，最优值z=-12线性规划的对偶理论线性规划的对偶理论-58-China University of Mining and Technology运筹学 试用对偶原理求解线性规划问题试用对偶原理求解线性规划问题已知其对偶规划的最优解为已知其对偶规划的最优解为练习练习线性规划的对偶理论线性规划的对偶理论-62-China University of Mining and
26、 Technology运筹学 对偶规划可以用线性规划的单纯形法求解。对偶规划可以用线性规划的单纯形法求解。由对偶原理可见，原问题与对偶问题之间有紧密联系，因由对偶原理可见，原问题与对偶问题之间有紧密联系，因此我们能够通过求解原问题来找出对偶问题的解，反之依然。此我们能够通过求解原问题来找出对偶问题的解，反之依然。互补松弛条件就可以解决由原问题的最优解直接求出对偶互补松弛条件就可以解决由原问题的最优解直接求出对偶问题的最优解。问题的最优解。对偶问题解的求法对偶问题解的求法线性规划的对偶理论线性规划的对偶理论-63-China University of Mining and Technology
27、运筹学 原问题与对偶问题解的对应关系小结原问题与对偶问题解的对应关系小结对应关系对应关系原问题原问题最优解最优解无界解无界解无可行解无可行解对偶问题对偶问题最优解最优解(Y,Y)(N,N)无界解无界解(Y,Y)无可行解无可行解(Y,Y)无法判断无法判断线性规划的对偶理论线性规划的对偶理论-65-China University of Mining and Technology运筹学 2.5 影子价格-66-China University of Mining and Technology运筹学 单位产品消耗的资源单位产品消耗的资源( (吨吨/ /件件)原始问题是利润最大化的生产计划问题原始问题
28、是利润最大化的生产计划问题总利润总利润( (元元) )产品产量产品产量( (件件) )单位产品的利润单位产品的利润( (元元/ /件件) )消耗的资源消耗的资源( (吨吨) )剩余的资源剩余的资源( (吨吨) )资源限量资源限量( (吨吨) )影影 子子 价价 格格-67-China University of Mining and Technology运筹学 对偶问题对偶问题资源定价问题资源定价问题对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为称为m种资源的影子价格种资源的影子价格Shadow Price）原始和对偶问题都取得最优解时
29、，最大利润原始和对偶问题都取得最优解时，最大利润 Max z=Min w总利润总利润(元元)资源限量资源限量(吨吨)资源价格资源价格(元元/吨吨)影影 子子 价价 格格-68-China University of Mining and Technology运筹学 在在一一对对 P 和和 D 中中，假假设设 P 的的某某个个约约束束条条件件的的右右端端项项常常数数 bi （ 第第 i 种种资资源源的的拥拥有有量量增增加加一一个个单单位位时时，所所引引起起目目标标函函数数最最优优值值 z* 的的改改变变量量称称为为第第 i 种种资资源源的的影影子子价价格格，其其值值等等于于 D问问题题中中对对偶
30、偶变变量量 yi*。由对偶问题得基本性质可得：由对偶问题得基本性质可得：1. 影子价格的数学分析：影子价格的数学分析：影影 子子 价价 格格-69-China University of Mining and Technology运筹学 2. 影子价格的经济意义影子价格的经济意义1影子价格是一种边际价格影子价格是一种边际价格在其它条件不变的情况下，单位资源数量的变化所引起的在其它条件不变的情况下，单位资源数量的变化所引起的目标函数最优值的变化。即对偶变量目标函数最优值的变化。即对偶变量yi 就是第就是第 i 种资源的影子种资源的影子价格。即：价格。即： 影影 子子 价价 格格影影子子价价格格是
31、是针针对对某某一一具具体体约约束束条条件件而而 言言 ,因因此此影影子子价价格格可可理理解解为为目目标标函函数数最最优优值值对对资资源源的的一一阶阶偏偏导导数数-70-China University of Mining and Technology运筹学 资源影子价格的性质资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于价格一定等于0 0影影 子子 价价 格格-72-C
32、hina University of Mining and Technology运筹学 0X2X1X= (15,7.5) Z=975Max Z=40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t-73-China University of Mining and Technology运筹学 0X2X1X= (15,7.5) Z=975X= (14.5,8.25) Z=992.5Max Z=40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t-74-China University of Minin
33、g and Technology运筹学 0X2X1X= (15,7.5) Z=975X= (15.5,7.25) Z=982.5Max Z=40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t-75-China University of Mining and Technology运筹学 0X2X1X= (15,7.5) Z=975Max Z=40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t-76-China University of Mining and Technology运筹学 0X2X
34、1X= (15,7.5) Z=975X= (15.5,7.25) Z=982.5X= (14.5,8.25) Z=992.5Max Z=40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t-77-China University of Mining and Technology运筹学 2影子价格是一种机会成本影子价格是一种机会成本影子价格是在资源最优利用条件下对单位资源的估价，这影子价格是在资源最优利用条件下对单位资源的估价，这种估价不是资源实际的市场价格。因此，从另一个角度说，它种估价不是资源实际的市场价格。因此，从另一个角度说，它是一种机会成
35、本。是一种机会成本。若第若第i 种资源的单位市场价格为种资源的单位市场价格为mi ，则有，则有当当yi* mi 时，企业愿意购进这种资源，单位纯利为时，企业愿意购进这种资源，单位纯利为yi*mi ，则有利可图；，则有利可图；当当yi* mi 则购进资源则购进资源 i，可获单位纯利，可获单位纯利yi*mi ； 若若yi* 0，则，则xn+i =0如果如果xn+i 0，则，则yi =0影子价格大于0的资源，在最优生产计划条件下没有剩余ym+jxj=0如果如果ym+j 0，则，则xj =0如果如果xj 0，则，则ym+j =0最优生产计划条件下有剩余的资源，其影子价格等于0差额成本大于0机会成本大于
36、利润的产品，不安排生产安排生产的产品，差额成本等于0机会成本等于利润）互补松弛关系经济解释互补松弛关系经济解释影影 子子 价价 格格-82-China University of Mining and Technology运筹学 4影子价格对单纯形表计算的解释影子价格对单纯形表计算的解释单纯形表中的检验数单纯形表中的检验数其中其中cj表示第表示第j种产品的价格种产品的价格; 表示生产该种产品所消表示生产该种产品所消耗的各项资源的影子价格的总和，即产品的隐含成本。耗的各项资源的影子价格的总和，即产品的隐含成本。当产值大于隐含成本时，即当产值大于隐含成本时，即 ，表明生产该项产品有利，表明生产该项
37、产品有利，可在计划中安排；可在计划中安排；否则否则 ，用这些资源生产别的产品更有利，不在生产中，用这些资源生产别的产品更有利，不在生产中安排该产品。安排该产品。影影 子子 价价 格格-83-China University of Mining and Technology运筹学 2.6 对偶单纯形法-84-China University of Mining and Technology运筹学 对偶单纯形法是求解线性规划的另一个基本方法。它是根对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯据对偶原理和单纯形法原理而设计出来的，因此称为对
38、偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。形法。不要简单理解为是求解对偶问题的单纯形法。对偶单纯形法原理对偶单纯形法原理对偶单纯形法基本思路：对偶单纯形法基本思路： 找出一个对偶问题的可行基，保持对偶问题为可行解的条找出一个对偶问题的可行基，保持对偶问题为可行解的条件下，判断件下，判断XB是否可行是否可行XB为非负），若否，通过变换基解，为非负），若否，通过变换基解，直到找到原问题基可行解即直到找到原问题基可行解即XB为非负），这时原问题与对为非负），这时原问题与对偶问题同时达到可行解，由定理偶问题同时达到可行解，由定理4可得最优解。可得最优解。对对 偶偶 单单 纯纯 形形 法法-8
39、5-China University of Mining and Technology运筹学 找出一个找出一个DP的可行基的可行基LP是否可行是否可行（XB 0）保持保持DP为可行解情况下转移到为可行解情况下转移到LP的另一个基本解的另一个基本解最优解最优解是是否否循循环环终了终了对对 偶偶 单单 纯纯 形形 法法-86-China University of Mining and Technology运筹学 先回顾一下单纯形算法：先回顾一下单纯形算法：它是从线性规划的一个基可行解迭代到另一个基可行解的过它是从线性规划的一个基可行解迭代到另一个基可行解的过程，在迭代过程中，保持基解的可行性，逐
40、步消除基解的检程，在迭代过程中，保持基解的可行性，逐步消除基解的检验数的非负性，即验数的非负性，即为了求解线性规划，我们也可以从线性规划的一个基解迭代为了求解线性规划，我们也可以从线性规划的一个基解迭代到另一个基解，在迭代过程中，保持基解的检验数的非正性，到另一个基解，在迭代过程中，保持基解的检验数的非正性，逐步消除基解的不可行性，即逐步消除基解的不可行性，即对对 偶偶 单单 纯纯 形形 法法-87-China University of Mining and Technology运筹学 如果原问题如果原问题(P)的一个基本解的一个基本解X与对偶问题与对偶问题(D)的基可的基可 行解行解Y对应
41、的检验数向量满足条件对应的检验数向量满足条件 则称则称X为原问题为原问题(P)的一个正则解。的一个正则解。求解原问题求解原问题(P)时，可以从时，可以从(P)的一个正则解开始，迭代到另的一个正则解开始，迭代到另一个正则解，使目标函数值增加，当迭代到正则解满足原始一个正则解，使目标函数值增加，当迭代到正则解满足原始可行性条件可行性条件(即即xi0)时，就找到了原问题时，就找到了原问题(P)的最优解。的最优解。 这一方法称为对偶单纯形法这一方法称为对偶单纯形法对对 偶偶 单单 纯纯 形形 法法定义定义-88-China University of Mining and Technology运筹学
42、原始单纯形法原始单纯形法对偶单纯形法对偶单纯形法前前提提条条件件所有所有bi 0所有所有检验数检验数0最最 优优 性性 检检 验验所有所有检验数检验数0？所有所有bi 0？换换 入入 、 出出 基基变变 量量 的的 确确 定定先确定换入基变量先确定换入基变量后确定换出基变量后确定换出基变量先确定换出基变量先确定换出基变量后确定换入基变量后确定换入基变量原原始始基基本本解解的的进进化化可行可行最优最优（对偶问题的解从（对偶问题的解从不可行到可行）不可行到可行）非可行非可行可行（最优）可行（最优）（原问题的解从不可行（原问题的解从不可行到可行）到可行）对对 偶偶 单单 纯纯 形形 法法-89-Ch
43、ina University of Mining and Technology运筹学 原问题解空间原问题解空间对偶问题解空间对偶问题解空间可行解可行解可行解可行解基本解基本解基本解基本解正则解正则解正则解正则解基可行解基可行解基可行解基可行解最优解最优解对对 偶偶 单单 纯纯 形形 法法-90-China University of Mining and Technology运筹学 对偶单纯法的迭代步骤：对偶单纯法的迭代步骤：对偶单纯法的迭代步骤：对偶单纯法的迭代步骤：（1找一个正则基找一个正则基B和初始正则解和初始正则解X(0)，将问题，将问题P化为化为关于基关于基B的典式，列初始对偶单纯形
44、表的典式，列初始对偶单纯形表.设正则解设正则解的典式为：的典式为：对对 偶偶 单单 纯纯 形形 法法-91-China University of Mining and Technology运筹学 将上面的典式转换成前面所学习过的单纯形表：将上面的典式转换成前面所学习过的单纯形表：（2假假设设, 则迭代停止，已求得原问题则迭代停止，已求得原问题P的最优的最优解解;否则转下一步。否则转下一步。对对 偶偶 单单 纯纯 形形 法法-92-China University of Mining and Technology运筹学 则迭代停止，原问题无解；否则转下一步。则迭代停止，原问题无解；否则转下一步
45、。为换出变量。假设为换出变量。假设（3确定换出变量：假设确定换出变量：假设则取相应的变量则取相应的变量对对 偶偶 单单 纯纯 形形 法法-93-China University of Mining and Technology运筹学 （4确定换入变量：假设确定换入变量：假设则取则取x l 为换入变量。为换入变量。以以正则解，前往正则解，前往2）。）。为主元进行换基运算得到新的为主元进行换基运算得到新的对对 偶偶 单单 纯纯 形形 法法-94-China University of Mining and Technology运筹学 用对偶单纯形法计算用对偶单纯形法计算解：为了便于解：为了便于寻找
46、初始正则寻找初始正则解，将问题变解，将问题变形为：形为：取取x4,x5为初始正则为初始正则解，列单纯形表如下：解，列单纯形表如下：例例9对对 偶偶 单单 纯纯 形形 法法-95-China University of Mining and Technology运筹学 -2-3-400XBbx1x2x3x4x5x4-3-1-2-110x5-4-21-3010-2-3-4由于初始正则解有负分量，于是取由于初始正则解有负分量，于是取min-3,-4=-4x5为换出变量，取为换出变量，取x1为换入变量，得新基为换入变量，得新基x4,x1 ，51= -2为主元为主元对对 偶偶 单单 纯纯 形形 法法-9
47、6-China University of Mining and Technology运筹学 基变换的过程：基变换的过程：1.主元变为主元变为1，即用，即用-2去除单纯形表中基变量去除单纯形表中基变量x5所在的行；所在的行；2.主元所在列的其它元变为主元所在列的其它元变为0，消去非基变量，消去非基变量x1所在的列的所在的列的其余元其余元-1，-2；3.得新基得新基x4,x1的单纯形表的单纯形表-2-3-400XBbx1x2x3x4x5x4-3-1-2-110x5-4-21-3010-2-3-4对对 偶偶 单单 纯纯 形形 法法-97-China University of Mining and
48、 Technology运筹学 基变换的过程：基变换的过程：-2-3-4XBbx1x2x3x4x5x4x1-2-3-400XBbx1x2x3x4x5x4-3-1-2-110x5-4-21-3010-2-3-421-1/23/20-1/2-10-5/21/21-1/240-4-10-1对对 偶偶 单单 纯纯 形形 法法-98-China University of Mining and Technology运筹学 -2-3-4XBbx1x2x3x4x5x4x121-1/23/20-1/2-10-5/21/21-1/240-4-10-1可见正则解的有负分量，由于可见正则解的有负分量，由于x4=1 ,
49、 所以取所以取x4为换出变量，为换出变量，取取x2为换入变量，得新基为换入变量，得新基x2,x1 ，42=-5/2为主元为主元对对 偶偶 单单 纯纯 形形 法法-99-China University of Mining and Technology运筹学 -2-3-4XBbx1x2x3x4x5x22/501-1/5-2/51/5x111/5107/5-1/5-2/528/500-3/5-8/5-1/5此时正则解是可行解，也是最优解。此时正则解是可行解，也是最优解。 X*=(11/5，2/5，0，0，0)；z*=-28/5进行基变换，得新正则解的单纯形表：进行基变换，得新正则解的单纯形表：对对
50、 偶偶 单单 纯纯 形形 法法-100-China University of Mining and Technology运筹学 例例10-101-China University of Mining and Technology运筹学 cjB-1b-120-5000cByBy1y2y3y40y3-50-4-2100y4-30-3-101j0-120-5000-120/-4-50/-2-50y22521-1/200y4-5-10-1/21j-1250-200-2502050-50y21501-3/22-120y15101/2-1j-135000-15-20-102-China Universi
51、ty of Mining and Technology运筹学 例例11-103-China University of Mining and Technology运筹学 cjB-1b23-5-M0cBxBx1x2x3x4x5-Mx471111070x5-10-25-101j-7MM+2M+3M-5003x27111100x5-45-70-6-51j21-10-7-M-301/77/6(M+3)/53x24/7011/72/71/72x145/7106/75/7-1/7j102/700-50/7-(M+16)/7-1/7-104-China University of Mining and Te
52、chnology运筹学 例例12-105-China University of Mining and Technology运筹学 cj3-1-100-MB-1bcBxBx1x2x3x4x5x60x41-2110011110x54-1-2010-3-Mx6-20100111j-6M+3-1M-1000-Mcj3-1-100-MB-1bcBxBx1x2x3x4x5x60x43-2010-1100x50-10012-1-1x3-2010011j1-1000-M+1-1-106-China University of Mining and Technology运筹学 cj3-1-100-MB-1bc
53、BxBx1x2x3x4x5x63x11001/3-2/3-5/34-1x20100-1-21-1x30012/3-4/3-7/39j000-1/3-1/3-M+2/32cj3-1-100-MB-1bcBxBx1x2x3x4x5x60x43001-2-512-1x20100-1-21-1x3-2010011j1000-1-M-1-2-107-China University of Mining and Technology运筹学 对偶单纯形法的迭代步骤中对偶单纯形法的迭代步骤中, ,如何找一个初始正则解？如何找一个初始正则解？初始正则解的确定初始正则解的确定初始正则解的确定初始正则解的确定标准形
54、线性规划问题标准形线性规划问题选定的基选定的基B B，不妨设，不妨设对对 偶偶 单单 纯纯 形形 法法可行基可行基B的典式为的典式为右端常数中有负数，而检验数全非正，则基右端常数中有负数，而检验数全非正，则基B为正则为正则基，相应的基，相应的 解为初解为初始正则解，就可用对偶单纯形法求解。始正则解，就可用对偶单纯形法求解。否则，若出现正检否则，若出现正检验数，验数，X(0)就不是就不是正则解。正则解。-108-China University of Mining and Technology运筹学 为此，求初始正则基和初始正则解，可增加一个约束条件：为此，求初始正则基和初始正则解，可增加一个约
55、束条件：原问题原问题(P)的典式扩充为下列问题的典式扩充为下列问题:扩充问题：扩充问题：对对 偶偶 单单 纯纯 形形 法法非基变量非基变量充分大数充分大数-109-China University of Mining and Technology运筹学 u扩充问题的一个正则基和正则解是不难得到的。扩充问题的一个正则基和正则解是不难得到的。对对 偶偶 单单 纯纯 形形 法法u扩充问题的两种可能结果：扩充问题的两种可能结果：（1若扩充问题无可行解，则原问题若扩充问题无可行解，则原问题(P)也无可行解。也无可行解。（2若扩充问题有最优解若扩充问题有最优解且目标函数最优值与且目标函数最优值与 M 无关
56、无关,则有则有必为原问题必为原问题(P)的最优解。的最优解。-113-China University of Mining and Technology运筹学 对偶单纯形法的理论解释对偶单纯形法的理论解释对偶单纯形法的理论解释对偶单纯形法的理论解释对偶单纯形法所使用的表格与原单纯形法一样，可将典式对偶单纯形法所使用的表格与原单纯形法一样，可将典式中的数据放在原单纯形表上，即得到对偶单纯形表，所不中的数据放在原单纯形表上，即得到对偶单纯形表，所不同的是这里保证在整个过程中同的是这里保证在整个过程中不保证不保证,即右端常数中可以出现负数。即右端常数中可以出现负数。对对 偶偶 单单 纯纯 形形 法法
57、先定换出变量，再定换入变量。先定换出变量，再定换入变量。从本章起，不从本章起，不强调右端常数强调右端常数非负这个条件。非负这个条件。-121-China University of Mining and Technology运筹学 (1)用对偶单纯形法求解线性规划问题时，当约束条件为用对偶单纯形法求解线性规划问题时，当约束条件为“”时，不必引进人工变量，使计算简化。时，不必引进人工变量，使计算简化。(2)当线性规划问题中变量多于约束条件时，用对偶单纯形法当线性规划问题中变量多于约束条件时，用对偶单纯形法计算可以减少工作量。计算可以减少工作量。(3)对偶单纯形法应用于主要应用于灵敏度分析及整数规划等对偶单纯形法应用于主要应用于灵敏度分析及整数规划等有关章节中。有关章节中。(4)对偶单纯形法的局限性主要是：对大多数线性规划问题，对偶单纯形法的局限性主要是：对大多数线性规划问题，很难找到一个初始正则解。因此对偶单纯形法一般不单独很难找到一个初始正则解。因此对偶单纯形法一般不单独使用。使用。对偶单纯形法的优缺点：对偶单纯形法的优缺点：对偶单纯形法的优缺点：对偶单纯形法的优缺点：对对 偶偶 单单 纯纯 形形 法法
