1、第二章 对偶线性规划p对偶的定义p对偶问题的性质p原始对偶关系p对偶单纯形法p对偶的经济解释p灵敏度分析DUAL第一节第一节 线性规划的对偶问题线性规划的对偶问题一、对偶理论的提出一、对偶理论的提出 例：现用甲乙两种原材料例：现用甲乙两种原材料生产生产A1，A2两种产品，所两种产品，所需的原料，甲乙两种原料需的原料，甲乙两种原料的可供量，以及生产的可供量，以及生产A1,A2两种产品可得的单位利润两种产品可得的单位利润见表。问如何安排生产资见表。问如何安排生产资源使得总利润为最大？源使得总利润为最大？A1A2可供量可供量甲甲3224乙乙4540利润利润4.55解：设生产解：设生产A1为为x1件，
2、生产件，生产A2为为x2件，则线性规划问题为：件，则线性规划问题为：maxZ=4.5x1+5x2 s.t.3x1+2x224 4x1+5x240 x1,x20假设现在不考虑生产产品，而是把甲乙两种原材料卖掉，则假设现在不考虑生产产品，而是把甲乙两种原材料卖掉，则问题变成对于甲乙两种原材料企业以多少最低价愿意出让？问题变成对于甲乙两种原材料企业以多少最低价愿意出让？解：设甲资源的出让价格为解：设甲资源的出让价格为y1,乙资源的出让价格为乙资源的出让价格为y2minw=24y1+40y2 s.t.3y1+4y24.5 2y1+5y25 y1,y203 24 53 42 5A1A2可供量可供量甲甲3
3、224乙乙4540利润利润4.55二、对称形式的线性规划问题的对偶问题二、对称形式的线性规划问题的对偶问题 一般认为变量均为非负约束的情况下，约束条件在目标函一般认为变量均为非负约束的情况下，约束条件在目标函数取极大值时均取数取极大值时均取“”号；当目标函数求极小值时均取号；当目标函数求极小值时均取“号。则称这些线性规划问题具有对称性。号。则称这些线性规划问题具有对称性。max z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1,x2,xn 0min w=b1y1+b2y2+
4、bmyms.t.a11y1+a21y2+am1ym c1 a12y1+a22y2+am2ym c2 a1ny1+a2ny2+amnym cn y1,y2,ym 0Max Z=CX s.t.AXb X0Minw=Yb s.t.ATYCT Y0原始问题原始问题max z=CXs.t.AXb X 0对偶问题对偶问题min w=Ybs.t.ATYCTY 0maxbACCATbminmnmn举例：举例：例例1:maxZ=3x1+2x2 s.t.-x1+2x24 3x1+2x214 x1-x2 3 x1,x20minw=4y1+14y2+3y3 s.t.-y1+3y2+y33 2y1+2x2-y32 y1
5、,y2,y30y1y2y3第一种资源第一种资源第二种资源第二种资源第三种资源第三种资源第一种产品第一种产品 第二种产品第二种产品x1x2例例2:原始问题为原始问题为min z=2x1+3x2-x3s.t.x1+2x2+x36 2x1-3x2+2x39 x1,x2,x30根据定义，对偶问题为根据定义，对偶问题为max w=6y1+9y2s.t.y1+2y22 2y1-3y23 y1+2y2-1 y1,y20原始问题是极小化问题原始问题是极小化问题原始问题的约束全为原始问题的约束全为原始问题有原始问题有3个变量，个变量，2个约束个约束原始问题的变量全部为非负原始问题的变量全部为非负对偶问题是极大化
6、问题对偶问题是极大化问题对偶问题的约束全为对偶问题的约束全为对偶问题有对偶问题有2个变量，个变量，3个约束个约束原始问题的变量全部为非负原始问题的变量全部为非负原始问题变量的个数原始问题变量的个数(3)等于对偶问题约束条件的个数等于对偶问题约束条件的个数(3)原始问题约束条件的个数原始问题约束条件的个数(2)等于对偶问题变量的个数等于对偶问题变量的个数(2)三、非对称形式的原问题三、非对称形式的原问题对偶问题对偶问题 如目标函数如目标函数maxz,就应把约束全部改为就应把约束全部改为“”型型方法：原为方法：原为“”型，两边同乘型，两边同乘“-1”原为原为“=”型，可用一个型，可用一个“”型和一
7、个型和一个“”型的两个不等式型的两个不等式代替，然后将代替，然后将“”型变为型变为“”型型原为原为xk 0，xk”0如果是如果是minw型，就应将约束全部改为型，就应将约束全部改为“”型型minz=2x1+3x2-5x3+x4 s.t.x1+x2-3x3+x45 2x1 +2x3-x44 x2+x3+x4=6 x10,x2,x30,X4自由自由x2+x3+x46x2+x3+x46-x1=x1,则则x10;x4-x4”=x4,其中其中x4 0,x4”0minz=-2x1+3x2-5x3+(x4-x4”)s.t.-x1+x2-3x3+(x4-x4”)5 2x1 -2x3+(x4-x4”)-4 x2
8、+x3+(x4-x4”)6 -x2-x3-(x4-x4”)-6 x1,x2,x3,x4,x4”0变为对称形式变为对称形式y1y2y3y3”maxw=5y1-4y2+6(y3-y3”)s.t -y1+2y2 -2 y1 +(y3-y3”)3 -3y1-2y2+(y3-y3”)-5 y1+y2+(y3-y3”)1 -y1-y2-(y3-y3”)-1 y1,y2,y3,y3”0写出对偶问题写出对偶问题maxw=5y1-4y2+6(y3-y3”)s.t.-y1+2y2 -2 y1 +(y3-y3”)3 -3y1-2y2+(y3-y3”)-5 y1+y2+(y3-y3”)1 -y1-y2-(y3-y3”
9、)-1 y1,y2,y3,y3”0设设y2=-y2,y3=y3-y3”,则则y20,y3无约束无约束此时对偶问题变为此时对偶问题变为maxw=5y1+4y2+6y3 s.t.y1+2y2 2 y1 +y3 3 -3y1+2y2+y3 -5 y1 -y2 +y3 =1 y10,y20,y3无约束无约束minz=2x1+3x2-5x3+x4 s.t.x1+x2-3x3+x45 2x1 +2x3-x4 4 x2+x3+x4 =6 x10,x2,x30,X4自由自由比较原问题比较原问题和对偶问题和对偶问题原始问题原始问题与其对偶与其对偶问题的对问题的对应规则应规则P问题（问题（D）D问题（问题（P）目
10、标函数目标函数 max目标函数目标函数 min变量变量n个个n个个约束约束条件条件free约束约束条件条件m个个m个个变量变量freeb价值系数价值系数 c右端常数右端常数min z=2x1+4x2-x3s.t.3x1-x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15max w=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y4 2 -y1+2y2+y3+3y4 4 2y1-3y2+2y3-y4 -1 y1 0,y2 ,y3 0,y4 0=Free=x10 x20 x3Freep原始问题变量的个数原始问题变量的个数(3)等于对
11、偶问题约束条件的个数等于对偶问题约束条件的个数(3)；p原始问题约束条件的个数原始问题约束条件的个数(4)等于对偶问题变量的个数等于对偶问题变量的个数(4)。p原始问题变量的性质影响对偶问题约束条件的性质。原始问题变量的性质影响对偶问题约束条件的性质。p原始问题约束条件的性质影响对偶问题变量的性质。原始问题约束条件的性质影响对偶问题变量的性质。练习练习1maxZ=x1-2x2+3x3 s.t.2x1+4x2+3x3100 3x1-2x2+6x3200 5x1+3x2+4x3=150 x1,x30，x2free练习练习2minw=100y1+200y2+150y3 s.t.2y1+3y2+5y3
12、1 4y1-2y2+3y3=-2 3y1+6y2+4y33 y10,y20,y3freeminZ=2x1+2x2+4x3 s.t.x1+3x2+4x32 2x1+x2+3x33 x1+4x2+3x3=5 x1 0,x2,x30,maxw=2y1+3y2+5y3 s.t.y1+2y2+y32 3y1+y2+4y3 2 4y1+3y2+3y34 y10,y20,y3free练习练习3第二节第二节 对偶问题的基本性质对偶问题的基本性质一、单纯形法计算的矩阵描述一、单纯形法计算的矩阵描述Max Z=CX AXb X0其中其中X(x1,x2xn)TMax Z=CX+0Xs AX+IXs=b X,Xs0其
13、中其中Xs(xn+1,xn+2xn+m)TI 为为mm的单位矩阵的单位矩阵非基变量非基变量基变量基变量XB(未来基变量未来基变量)XNXs0XsbBNIjCBCN0基变量基变量非基变量非基变量XBXNXsCBXBB-1bIB-1NB-1j0CN-CBB-1N-CBB-1对应初始单纯形表中的单位矩阵对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为，迭代后的单纯形表中为B-1；初始单纯形表中基变量初始单纯形表中基变量Xs=b，迭代后的表中为，迭代后的表中为XB=B-1b；约束矩阵（约束矩阵（A）（）（B，N，I），迭代后为），迭代后为（B-1B，B-1N，B-1）（）（I，B-1N，B-1)；
14、初始单纯形表中初始单纯形表中xj的系数向量为的系数向量为Pj，迭代后为，迭代后为Pj，且，且Pj=B-1Pj。CBB-1称为单纯形乘子称为单纯形乘子,是一个是一个m 个分量的个分量的“行向量行向量”设设CBB-1=（y1,ym）二、对偶问题的基本性质二、对偶问题的基本性质原始问题原始问题max z=CXs.t.AXb X 0对偶问题对偶问题min w=YTbs.t.ATYCTY01、对称性：对偶的对偶就是原始问题、对称性：对偶的对偶就是原始问题对偶问题的对偶对偶问题的对偶max z=6x1+9x2s.t.x1+2x22 2x1-3x23 x1+2x2-1 x1,x20minw=2y1+3y2-
15、y3s.t.y1+2y2+y36 2y1-3y2+2y39 y1,y2,y30对偶问题的对偶就是原始对偶问题的对偶就是原始问题。两个问题中的任一问题。两个问题中的任一个都可以作为原始问题。个都可以作为原始问题。另一个就是它的对偶问题。另一个就是它的对偶问题。根据定义写根据定义写出对偶问题出对偶问题根据定义写出对偶问题根据定义写出对偶问题max u=6w1+9w2s.t.w1+2w22 2w1-3w23 w1+2w2-1 w1,w20推论：推论：原问题任一可行解的目标函数是其对偶问题目标函数值的原问题任一可行解的目标函数是其对偶问题目标函数值的下界，反之对偶问题任一可行解的目标函数是其原问题目下
16、界，反之对偶问题任一可行解的目标函数是其原问题目标函数的上界。标函数的上界。无界性定理：如原问题有可行解且目标函数值无界，则其无界性定理：如原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之对偶问题有可行解且目标函数无对偶问题无可行解；反之对偶问题有可行解且目标函数无界，则原问题无可行解。（对偶问题无可行解时，其原问界，则原问题无可行解。（对偶问题无可行解时，其原问题无界解或无可行解）题无界解或无可行解）若原问题有可行解而其对偶问题无可行解时，原问题目标若原问题有可行解而其对偶问题无可行解时，原问题目标函数无界；反之若对偶问题有可行解而其原问题无可行解函数无界；反之若对偶问题有可行解而
17、其原问题无可行解时，对偶问题目标函数无界。时，对偶问题目标函数无界。2、弱对偶性、弱对偶性若若X为原问题的可行解，为原问题的可行解，Y为对偶问题的可行解，则恒有为对偶问题的可行解，则恒有CXYb利用弱对偶性和无界性定理可以做一些证明题，如利用弱对偶性和无界性定理可以做一些证明题，如P75：2.5和和2.63.最优性最优性 若若X为原问题的可行解，为原问题的可行解，Y为对偶问题的可行解，且为对偶问题的可行解，且CXYb,则则X，Y分别为原问题和对偶问题的最优解。分别为原问题和对偶问题的最优解。4.强对偶性强对偶性 若原问题和对偶问题均具有可行解，则两者均具有最优解，若原问题和对偶问题均具有可行解
18、，则两者均具有最优解，且他们的最优解的目标值相等。且他们的最优解的目标值相等。原始和对偶问题可行解目标函数值比较原始和对偶问题可行解目标函数值比较min z=2x1+3x2s.t.x1+3x23 2x1+x2 4 x1,x2 0max w=3y1+4y2s.t.y1+2y22 3y1+y2 3 y1,y2 00 1 2 34321A(3,0)B(1.8,0.4)C(0,4)D(2,2)可行可行解解z最优解最优解A6B4.8是是C12D103210 1 2A(1,0)B(0.8,0.6)C(0,1)O(0,0)可行解可行解w最优解最优解O0A3B4.8是是C4maxZ=4.5x1+5x2 s.t
19、.3x1+2x224 4x1+5x240 x1,x20minw=24y1+40y2 s.t.3y1+4y24.5 2y1+5x25 y1,y20y1y2x1x2maxZ=4.5x1+5x2 s.t.3x1+2x2+x3=24 4x1+5x2+x4=40 x1,x2,x3,x4,0minw=24y1+40y2 s.t.3y1+4y2-y3=4.5 2y1+5y2-y4=5 y1,y2,y3,y40y1y2x1x2cj4.5500CBXBB-1bx1x2x3x44.5x140/7105/7-2/75x224/701-4/73/7j00-5/14-6/7解原问题求得最终单纯形表：解原问题求得最终单纯
20、形表：Z*=4.540/7524/7=300/7解对偶问题求得最终单纯形表：解对偶问题求得最终单纯形表：w=245/14406/7=300/7cj244000CBYBB-1by1y2y3y424y15/1410-5/74/740y26/7012/7-3/7j0040/724/7cj4.5500CBXBB-1bx1x2x3x44.5x140/7105/7-2/75x224/701-4/73/7j00-5/14-6/7cj244000CBYBB-1by1y2y3y424y15/1410-5/74/740y26/7012/7-3/7j0040/724/7(x3,x4)=(0,0)(y3,y4)=(0
21、,0)-y1-y2-y4-y3x1x2x4x34.互补松弛定理互补松弛定理在线性规划问题的最优解中，如果对应某一约束条件的对偶在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非变量值为非0，则该约束条件取严格等式，即松弛变量或剩余变，则该约束条件取严格等式，即松弛变量或剩余变量为量为0；反之如果对应某一约束条件的对偶变量值为；反之如果对应某一约束条件的对偶变量值为0，则，则该约束条件取严格不等式，即松弛变量或剩余变量不为该约束条件取严格不等式，即松弛变量或剩余变量不为0.设设X*=（x1*,x2*,xn*）和）和 Y*=（y1*,y2*,ym*）分别是）分别是P和和D的最优解的最优
22、解若若yi*0,则则aijxj*=bi，即，即xsi*=0若若yi*0,则则aijxj*bi，即，即xsi*0即即xsi*yi*=0同理同理若若xj*0,则则aijyi*=cj，即，即ysj*=0若若xj*0,则则aijyi*cj，即，即ysj*0即即ysj*xj*=0maxZ=4.5x1+5x2 s.t.3x1+2x2+x3=24 4x1+5x2+x4=40 x1,x2,x3,x4,0y1y2minw=24y1+40y2 s.t.3y1+4y2-y3=4.5 2y1+5x2-y4=5 y1,y2,y3,y40 x1x2X3=0,3x1+2x2=24,y1=14/5X4=0,4x1+5x2=4
23、0,y2=6/7y3=0,3y1+4y2=4.5,x1=40/7y4=0,2y1+5y2=5,x2=24/7y1.yi.ym ym+1 .ym+j .ym+n x1 .xj .xn xn+1 xn+i xn+m 对偶问题的变量对偶问题的变量 对偶问题的松弛变量对偶问题的松弛变量 原始问题的变量原始问题的变量 原始问题的松弛变量原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于在一对变量中，其中一个大于0，另一个一定等于，另一个一定等于0互补松弛关系的分量表示互补松弛关系的分量表示min z=6x1+8x2+3x3s.t.x1+x2 1
24、 x1+2x2+x3-1 x1,x2,x3 0max w=y1-y2s.t.y1+y2 6 y1+2y2 8 y2 3 y1,y20max w=y1-y2s.t.y1+y2+y3 =6 y1+2y2 +y4 =8 y2 +y5=3 y1,y2,y3,y4,y50(y1,y2)=(6,0)(y1,y2,y3,y4,y5)=(6,0,0,2,3)min z=6x1+8x2+3x3s.t.x1+x2 -x4 =1 x1+2x2+x3 -x5 =-1 x1,x2,x3,x4,x50(x1,x2,x3|x4,x5)(y1,y2|y3,y4,y5)x2=x3=x4=0 x1=1,x5=2引进剩余变量引进剩
25、余变量 求对偶求对偶引进松弛变量引进松弛变量图解法求解图解法求解代入约束代入约束求出松弛变量求出松弛变量互补松弛关系互补松弛关系代入约束代入约束求解求解(x1,x2,x3,x4,x5)=(1,0,0,0,2)例2:min z=2x1+3x2+5x3+2x4+3x5s.t.x1+x2+2x3+x4+3x54 2x1-x2+3x3+x4+x5 3 x1,x2,x3,x4,x5 0且且Y*=(4/5,3/5),求原问题最优解求原问题最优解.第三节第三节 影子价格影子价格(Shadow Price)一、影子价格的含义一、影子价格的含义Z*=w*，w*=Y*b 即：即：Z*=Y*b=y1*b1+y2*b
26、2+ym*bmpyi*可理解为：在其他条件不变的情况下，只增加单位第可理解为：在其他条件不变的情况下，只增加单位第i种种资源所引起的目标函数最优值的变化。资源所引起的目标函数最优值的变化。pyi*0，增加这种资源，增加这种资源，Z*会增加会增加 yi*=0，增加这种资源，增加这种资源，Z*不增加不增加),.,2,1(*miybzii例：例：maxZ=7x1+12x2 s.t.9x1+4x2 360 4x1+5x2200 3x1+10 x2300 x1,x20cj71200CBXBB-1bx1x2x3x4x50 x384001-78/2529/257x1201002/5-1/512x224010
27、-3/254/25j000-34/25-13/25p用单纯形法求得最终表如下，分析每增加单位资源给目标用单纯形法求得最终表如下，分析每增加单位资源给目标 函数值带来的影响？函数值带来的影响？AB总量总量煤煤94360水水45200电电310300利润利润712 资源的影子价格是一种机会成本资源的影子价格是一种机会成本 根据互补松弛定理根据互补松弛定理若若yi*0,则则aijxj*=bi，若若yi*0,则则aijxj*bi，某种资源某种资源bi未得到充分利用时，该种资源的影子价格未得到充分利用时，该种资源的影子价格为为0；当资源的影子价格不为当资源的影子价格不为0，表示该种资源在生产中已，表示该
28、种资源在生产中已消耗完毕。消耗完毕。j=c=cj j-C-CB BB B-1-1P Pj j=c=cj j-YP-YPj jc cj j表示第表示第j j种产品的产值，种产品的产值，YPYPj j表示生产该种产品所消表示生产该种产品所消耗各项资源的影子价格的总和，即产品的隐含成本。耗各项资源的影子价格的总和，即产品的隐含成本。如上例中，用煤、水、电生产第三种产品如上例中，用煤、水、电生产第三种产品C1个个C要消耗三种资源的数量为要消耗三种资源的数量为1、2、3，则隐含成本为：，则隐含成本为：10+2 1.36+3 0.52=4.28y1y2ym产品的机会成本产品的机会成本(Opportunit
29、y Cost)产品产品j的机会成本的机会成本：表示减少一件产品所节省的所有资源可以增加的利润表示减少一件产品所节省的所有资源可以增加的利润增加单位资源可以增加的利润增加单位资源可以增加的利润减少一件产品的产量可以节省的资源减少一件产品的产量可以节省的资源0 xxxxbxaxaxaxabxaxaxaxabxaxaxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj2211a1jy1+a2jy2+amjym0 xxxxxxbxxaxaxabxxaxaxabxxaxaxa.t.sxcxcxczmaxmn2n1nn21m
30、mnnmn22m11m22nnn222212111nnn1212111nn22110.min212122112222221121112211112211nmmmmnnmmmnnnmmmmmmmmyyyyyycyyayayacyyayayacyyayayatsybybybw原始问题和对偶问题的经济解释总结原始问题和对偶问题的经济解释总结资源占用（吨）资源占用（吨）资源剩余（吨）资源剩余（吨）资源总量（吨）资源总量（吨）产品的机会成本产品的机会成本（元（元/件）件）产品的差额成本产品的差额成本（元（元/件）件）产品的利润产品的利润（元（元/件）件）产品的产量（件）产品的产量（件）资源的影子价格（元
31、资源的影子价格（元/吨）吨）互补松弛关系的经济解释互补松弛关系的经济解释yixn+i=0如果如果yi0，则，则xn+i=0如果如果xn+i0，则，则yi=0边际利润大于边际利润大于0的资源，在最优生产计划条件下没有剩余的资源，在最优生产计划条件下没有剩余ym+jxj=0如果如果ym+j0，则，则xj=0如果如果xj0，则，则ym+j=0最优生产计划条件下有剩余的资源，其边际利润等于最优生产计划条件下有剩余的资源，其边际利润等于0差额成本大于差额成本大于0（机会成本大于利润）的产品，不安排生产（机会成本大于利润）的产品，不安排生产安排生产的产品，差额成本等于安排生产的产品，差额成本等于0（机会成
32、本等于利润）（机会成本等于利润）和资源有关的量和资源有关的量n资源限量（吨）资源限量（吨）n资源占用（吨）资源占用（吨）n资源剩余（吨）资源剩余（吨）n资源的影子价格（元资源的影子价格（元/吨）吨）和产品有关的量和产品有关的量n产品利润（元产品利润（元/件）件）n产品产量（件）产品产量（件）n产品的机会成本（元产品的机会成本（元/件）件）n产品的差额成本（元产品的差额成本（元/件）件）互补松弛关系，其互补松弛关系，其中一个大于中一个大于0，另，另一个一定一个一定 互补松弛关系，其互补松弛关系，其中一个大于中一个大于0，另，另一个一定等于一个一定等于0Maxz=4x1+10 x2 s.t.3x1
33、+6x25 x1+3x22 2x1+5x24 x1,x20已知原问题为：已知原问题为：y1y2y3则对偶问题为：则对偶问题为：Minw=5y1+2y2+4y3 s.t.3y1+y2+2y34 6y1+3y2+5y310 y1,y2,y30Maxz=4x1+10 x2 s.t.3x1+6x2+x3=5 x1+3x2 +x4=2 2x1+5x2 +x5=4 xj0(j=1,2,5)Minw=5y1+2y2+4y3 s.t.3y1+y2+2y3-y4=4 6y1+3y2+5y3-y5=10 yi0(i=1,2,5)第四节第四节 对偶单纯形法对偶单纯形法一、基本思路一、基本思路cj410000CBXB
34、B-1bx1x2x3x4x50 x35361000 x42130100 x5425001j410000初始单纯形表为：初始单纯形表为：此时对偶问题的解为此时对偶问题的解为Minw=5y1+2y2+4y3 s.t.3y1+y2+2y3-y4=4 6y1+3y2+5y3-y5=10 yi0(i=1,2,5)不是对偶问题的可行解不是对偶问题的可行解Y（0，0，0，4，10）代入）代入5/62/34/5对原问题进行迭代得：对原问题进行迭代得：cj410000CBXBB-1bx1x2x3x4x50 x31101-2010 x22/31/3101/300 x52/31/300-5/31j2/300-10/
35、30此时对偶问题的解为此时对偶问题的解为Minw=5y1+2y2+4y3 s.t.3y1+y2+2y3-y4=4 6y1+3y2+5y3-y5=10 yi0(i=1,2,5)不是对偶问题的可行解不是对偶问题的可行解122Y（0，10/3，0，-2/3，0）代入）代入对原问题进行迭代得：对原问题进行迭代得：cj410000CBXBB-1bx1x2x3x4x54x11101-2010 x21/301-1/3100 x51/300-1/3-11j00-2/3-20此时对偶问题的解为此时对偶问题的解为Y（2/3，2，0，0，0）代入）代入Minw=5y1+2y2+4y3 s.t.3y1+y2+2y3-
36、y4=4 6y1+3y2+5y3-y5=10 yi0(i=1,2,5)是对偶问题的可行解是对偶问题的可行解 由此可以看出：单纯形法求解的过程，从对偶的观点由此可以看出：单纯形法求解的过程，从对偶的观点来看，是在始终保持原始可行解的条件下，不断改进对偶来看，是在始终保持原始可行解的条件下，不断改进对偶可行性的过程。一个从对偶不可行的解，经过几次叠代，可行性的过程。一个从对偶不可行的解，经过几次叠代，逐步向对偶可行解靠拢，一旦得到的解既是原始可行的，逐步向对偶可行解靠拢，一旦得到的解既是原始可行的，又是对偶可行的，这个解就分别是原始问题和对偶问题的又是对偶可行的，这个解就分别是原始问题和对偶问题的
37、最优解。最优解。对偶单纯形法刚好和单纯形法的思路相反，就是在始对偶单纯形法刚好和单纯形法的思路相反，就是在始终保持对偶问题可行的条件下，不断改进原问题可行性的终保持对偶问题可行的条件下，不断改进原问题可行性的过程。一个从原问题不可行的解，经过几次叠代，逐步向过程。一个从原问题不可行的解，经过几次叠代，逐步向原问题可行解靠拢，一旦得到的解既是原始可行的，又是原问题可行解靠拢，一旦得到的解既是原始可行的，又是对偶可行的，这个解就分别是原始问题和对偶问题的最优对偶可行的，这个解就分别是原始问题和对偶问题的最优解。解。步骤：步骤：1.确定初始解确定初始解一般设松弛变量为初时基可行解一般设松弛变量为初时
38、基可行解2.判断判断 若所有的基变量值均若所有的基变量值均0，则此解为线性规划问题，则此解为线性规划问题的最优解，若存在基变量的值的最优解，若存在基变量的值0，则问题还没有，则问题还没有达到最优解，需要进行改进。达到最优解，需要进行改进。3.改进改进选择换出变量选择换出变量min bi/bi0假设选取假设选取xr为换出变量为换出变量选择换入变量选择换入变量min(j/arj,arj0则假设选取则假设选取xl为换入变量为换入变量4.迭代。使得迭代。使得alk1，其余，其余aik为为0Minw=5y1+2y2+4y3 s.t.3y1+y2+2y34 6y1+3y2+5y310 y1,y2,y30举
39、例：举例：Maxw=-5y1-2y2-4y3 s.t.-3y1-y2-2y3-4 -6y1-3y2-5y3-10 y1,y2,y30Maxw=-5y1-2y2-4y3 s.t.-3y1-y2-2y3+y4=-4 -6y1-3y2-5y3+y5=-10 yi0(i=1,2,5)cj-5-2-400CB基基B-1by1y2y3y4y50y4-4-3-1-2100y5-10-6-3-501jjj此时对偶问题和原问题都达到可行，所以均达到了最优解此时对偶问题和原问题都达到可行，所以均达到了最优解Y（2/3.2,0,0,0)W=-22/3W=22/3-5-2-45/62/34/5y4y20-210/32
40、15/30-1/3-2/3-10-1/31-1/3-1-2/3-2/3122y1y2-5-22/3101/3-11/320112-1-1/3-1-1/3Minw=2x1+3x2+4x3 s.t.x1+2x2+x33 2x1-x2+3x34 x1,x2,x30练习练习:用对偶单纯形法求解并求出对偶变量的最优解用对偶单纯形法求解并求出对偶变量的最优解Maxw=-2x1-3x2-4x3 s.t.-x1-2x2-x3-3 -2x1 +x2-3x3-4 x1,x2,x30Maxw=-2x1-3x2-4x3 s.t.-x1-2x2-x3+x4=-3 -2x1 +x2-3x3 +x5=-4 xi0(i=1,
41、2,5)Maxz=3y1+4y2 s.t.y1+2y22 2y1 -y23 y1+3y24 y1,y20对偶问题为对偶问题为cj-2-3-400CBXBB-1bx1x2x3x4x50 x4-3-1-2-1100 x5-4-21-301j-2-3-4001-4/30 x4-10-5/21/21-1/2-2x121-1/23/20-1/2j0-4-10-18/5-2-3x22/510-1/5-2/51/5-2x111/5017/5-1/5-2/5j00-9/5-8/5-1/5此时对偶问题和原问题都达到可行，所以均达到了最优解此时对偶问题和原问题都达到可行，所以均达到了最优解X*（11/5.2/5,
42、0,0,0),Y*（8/5,1/5,0,0,9/5)W=-28/5，W=28/5对偶单纯形法的特点：对偶单纯形法的特点：优点：优点：当约束条件为当约束条件为“”时，不需要引入人工变量，从时，不需要引入人工变量，从而使计算更为简便。而使计算更为简便。在灵敏度分析时、求解整数规划时用到。在灵敏度分析时、求解整数规划时用到。缺点：不能保证所有的缺点：不能保证所有的LP问题的初始单纯形表中的问题的初始单纯形表中的j0思考思考:设在进行基变换时设在进行基变换时,确定了确定了xr出基出基,若若arj0,则如则如何判断原问题和对偶问题的解的情况何判断原问题和对偶问题的解的情况单纯形法与对偶单纯形法对照单纯形
43、法与对偶单纯形法对照单纯形法单纯形法对偶单纯形法对偶单纯形法检验数检验数j=cj-CBB-1pj0B-1b0进进出出基基原原则则大小原则大小原则先进基：先进基：maxj/j 0后出基：后出基：minbi/aik，aik0列除列除两小原则两小原则先出基：先出基：min bi/bi0后进基：后进基：min(j/arj,arj0 行除行除最优性最优性j 0B-1b0前提前提B-1b0，原问题的可行性，原问题的可行性j 0，对偶问题的可行性，对偶问题的可行性第五节第五节 灵敏度分析灵敏度分析前提条件前提条件:原线性规划问题已取得了最优解；原线性规划问题已取得了最优解；每次只讨论一种参数的变化，而参数之
44、间的变化互每次只讨论一种参数的变化，而参数之间的变化互不关联。不关联。非基变量非基变量基变量基变量XB(未来基变量未来基变量)XNXs0XsbBNIjCBCN0基变量基变量非基变量非基变量XBXNXsCBXBB-1bIB-1NB-1j0CN-CBB-1N-CBB-1 某厂准备用甲乙两种原料生产某厂准备用甲乙两种原料生产A，B，C三种产品，相关三种产品，相关参数见表。问如何安排生产总利润为最大。参数见表。问如何安排生产总利润为最大。ABC可供量可供量甲甲12110乙乙22116利润利润341Maxz=3x1+4x2+x3 s.t.x1+2x2+x310 2x1+2x2+x3 16 xj0(j=1
45、,2,3,)Maxz=3x1+4x2+x3 s.t.x1+2x2+x3+x4=10 2x1+2x2+x3+x5=16 xj0(j=1,2,3,)用单纯形法对该线性规划进行求解，得初始单纯行表用单纯形法对该线性规划进行求解，得初始单纯行表和最优单纯形表和最优单纯形表cj34100CBXBB-1bx1x2x3x4x50 x410121100 x51622101j34100.4x22011-1/23x16100-11j00-1-1-1Z*=26B=(P2,P1)=2 1 2 2B-1-y1-y2-y3-y4-y5一、目标函数中一、目标函数中cj发生变化发生变化1.非基变量的非基变量的cj发生变化发生
46、变化x3的利润值由的利润值由1变为变为1+c3则：则：3=1+c3-41/2=-1+c3如果如果3=-1+c30，最优解不发生变化；，最优解不发生变化；所以当所以当c3 1时，最优解不发生变化。时，最优解不发生变化。cj341+c300CBXBB-1bx1x2x3x4x54x22011-1/23x16100-11j00-1+c3-1-12.基变量的基变量的cj发生变化发生变化假设假设x2的利润由的利润由4变为变为4+c2cj34+c2100CBXBB-1bx1x2x3x4x54+c2x22011-1/23x16100-11j00-1-1-1非基变量的检验数都要发生变化非基变量的检验数都要发生变
47、化-1-c2-1+1/2c2当且仅当所有的非基变量的检验数都仍然小于等于当且仅当所有的非基变量的检验数都仍然小于等于0则最优解不变。则最优解不变。-1-1/2c2 总结总结:当目标函数中当目标函数中cj发生变化，将影响最终发生变化，将影响最终单纯形表非基变量的检验数。如果是非基单纯形表非基变量的检验数。如果是非基变量的价值系数发生变化，只影响该非基变量的价值系数发生变化，只影响该非基变量的检验数，如果变化后的检验数仍然变量的检验数，如果变化后的检验数仍然小于等于小于等于0，则最优解不变；如果是基变量，则最优解不变；如果是基变量的价值系数发生变化，将影响所有非基变的价值系数发生变化，将影响所有非
48、基变量的检验数，只有当所有的非基变量检验量的检验数，只有当所有的非基变量检验数都仍然小于等于数都仍然小于等于0，最优解才不变。，最优解才不变。二、右端常数项二、右端常数项bi发生变化发生变化X=(XB,0)T其中其中XB=B-1bZ=CBB-1b当当bi 发生变化时：发生变化时：bi=b+(0,bi,0)T=b+b则则:XB=B-1b=B-1(b+b)=B-1b+B-1bXB+B-1b如果如果XB=XB+B-1b0，则原最终单纯形表中的基变量不变，则原最终单纯形表中的基变量不变，基变量的值将发生变化基变量的值将发生变化如果如果XB=XB+B-1b0，则需采用对偶单纯形表进行重新，则需采用对偶单
49、纯形表进行重新求解。求解。在上例中假设：在最优基保持不变的情况下在上例中假设：在最优基保持不变的情况下,b1的变动范围的变动范围看出甲资源的供给量的变化范围为看出甲资源的供给量的变化范围为:-2 b16cj34100CBXBB-1bx1x2x3x4x54x22011-1/23x16100-11j00-1-1-10621610112/11111,1bbbbBXB在上例中若需要将右端项由在上例中若需要将右端项由(10,16)T,改变为改变为(12,10)T,试求新试求新问题的解问题的解.271012112/11,1bBXB-20,则需采用对偶单纯形表进行重新求解。则需采用对偶单纯形表进行重新求解。
50、cj34100CBXBB-1bx1x2x3x4x54x27011-1/23x1-2100-11j00-1-1-1j2-1001-15111/201/2-10-10-2x2x440Z*=20,X*=(0,5,0,2,0)T 当右端常数项发生变化时，主要考虑在最当右端常数项发生变化时，主要考虑在最优单纯行表中基变量的值是否仍然大于等优单纯行表中基变量的值是否仍然大于等于于0，如果仍然大于等于，如果仍然大于等于0，则线性规划问，则线性规划问题的基变量不变，但是基变量的值将发生题的基变量不变，但是基变量的值将发生变化；如果右端常数项发生变化时，最优变化；如果右端常数项发生变化时，最优单纯行表中基变量的
