运筹学第三章线性规划的对偶原理.ppt

1,第三章线性规划的对偶原理,单纯形法的矩阵描述A为mn阶矩阵 RankA=m,取B为可行基,N为非基，,2,求解步骤：,3,4,现在不再生产，将设备材料出租出让，确定租费及转让费？设y1为设备单位台时的租金，y2,y3为材料A、B转让附加费(kg-1)目标函数，约束条件？,则M2为M1的对偶问题，反之亦然。,5,一般的，原问题：max z=CX AX b X 0,对偶问题：min w=Yb YA C Y 0,比较：max z min w 决策变量为n个 约束条件为n个 约束条件为m个 决策变量为m个“”“”约束条件的限定向量 目标函数的价值向量 目标函数的价值向量 约束条件的限定向量,6,二、对偶问题的化法 1、典型情况（对称形式）例2max z=x1+2x2+x3 2x1+x2 6 2x2+x3 8 x1,x2,x3 0,7,2、含等式的情况 例3max z=x1+2x2+4x3 2x1+x2+3x3=3 x1+2x2+5x3 4 x1,x2,x3 0,一般，原问题第i个约束取等式，对偶问题第i个变量自由变量。,8,3、含“”的max问题 例4max z=x1+2x2+4x3 2x1+x2+3x3 3 x1+2x2+5x3 4 x1,x2,x3 0,9,一般:max问题第i个约束取“”，则min问题第i个变量 0；,min问题第i个约束取“”，则max问题第i个变量 0；,原问题第i个约束取等式，对偶问题第i个变量 自由变量；,max问题第j个变量 0,则min问题第j个约束取“”；,min问题第j个变量 0，则max问题第j个约束取“”；,原问题第j个变量自由变量，对偶问题第j个约束取等式。,10,例5 min z=2x1+3x2-5x3+x4 x1+x2-3x3+x4 5 2x1+2x3-x4 4 x2+x3+x4=6 x1 0,x2,x3 0,x4自由变量,11,2 对偶问题的基本性质和基本定理,1、对称性定理 对偶问题的对偶为原问题.,原问题：max z=CX AX b X 0(1),对偶问题：min w=Yb YA C Y 0(2),证：,(2)作变换：,(2)等价于：,对偶,令z=w,即为(1),(2)的对偶问题为(1)。,12,证：,推论：(1)max问题任一可行解的目标值为min问题目标值的一个下界；(2)min问题任一可行解的目标值为max问题目标值的一个上界。,13,3、无界性（性质2的推论）若原问题(对偶问题)为无界解，则对偶问题(原问题)为无可行解。,注：该性质的逆不存在。若原(对偶)问题为无可行解，对偶(原问题)问题或为无界解，或为无可行解。,14,4、最优性 设X*，Y*分别为原问题和对偶问题可行解，当CX*=Y*b时，X*，Y*分别为最优解。,证：,X*为最优解,Y*为最优解,15,5、对偶定理 若原问题有最优解，那么对偶问题也有最优解，且目标值相等。,证：,16,5、对偶定理 若原问题有最优解，那么对偶问题也有最优解，且目标值相等。,推论（单纯形乘子Y的定理）：原问题有一个对应于基B的最优解，则此时的Y是对偶问题的一个最优解。,例：书P25,17,对偶问题中，解的情况有：1.都有有限最优解2.都无可行解3.一个有无界解，另一个无可行解,18,6、松弛性若X*，Y*分别为原问题及对偶问题的可行解，那么Ys*X*=0，Y*Xs*=0，当且仅当X*，Y*分别为最优解。,证：,将b，C代入目标函数，,19,7、检验数与解的关系 原问题附加变量最优检验数的值为对偶问题的最优解。,检验数：=(C 0)-CBB-1(A-I)=(C-CBB-1A CBB-1)=(c s)c=C-CBB-1A X对应的检验数 s=CBB-1 Xs对应的检验数,例：书P25,4=2，5=3,20,求对偶问题的最优解:1.单纯形乘子Y的定理2.松弛性3.检验数与解的关系,21,例6已知：min w=20y1+20y2 的最优解为y1*=1.2,y2*=0.2-ys1 y1+2y2 1 试用松弛性求对偶-ys2 2y1+y2 2 问题的最优解。-ys3 2y1+3y2 3-ys4 3y1+2y2 4 y1,y2 0,y1*xs1*=0 y2*xs2*=0 ys1*x1*=0 ys2*x2*=0 ys3*x3*=0 ys4*x4*=0,22,y1*=1.2,y2*0.2 0 xs1*=xs2*=0 由 y1*+2y2*=1.6 1 ys1*0 x1*=0 由 2y1*+y2*=2.6 2 ys2*0 x2*=0 由 2y1*+3y2*=3=右边 ys3*=0 x3*待定 由 3y1*+2y2*=4=右边 ys4*=0 x4*待定,最优解：x1*=0 x2*=0 x3*=4 x4*=4 xs1*=0 xs2*=0 最大值：z*=28=w*,y1*=1.2,y2*=0.2 ys1*x1*=0 ys2*x2*=0 ys3*x3*=0 ys4*x4*=0 y1*xs1*=0 y2*xs2*=0,y1+2y2-ys1*=1 2y1+y2-ys2*=2 2y1+3y2-ys3*=3 3y1+2y2-ys4*=4 x1+2x2+2x3+3x4+xs1=202x1+x2+3x3+2x4+xs2=20,23,8、对偶问题的经济含义影子价格 最优情况：z*=w*=b1y1*+biyi*+bmym*,b1：8 9 Q2(4，2.5)z*=15.5 z*=z*-z*=3/2=y1*b2：16 17 Q2”(4.25，1.875)z*”=14.125 z*=z*”-z*=1/8=y2*b3：12 13 z*=0=y3*,Q2,Q2”,Q2（4，2）z=14,条件3未满足，再增加b，不会带来z的增加，故该资源价值为0.,24,3 对偶单纯形法 单纯形法：由 XB=B-1b 0，使j 0，j=1,m 对偶单纯形法：由j 0(j=1,n)，使XB=B-1b 0 相同点：都用于求解原问题 对偶单纯形法：从一个原始不可行而对偶可行的基出发，进行基变换，每次基变换时都保持基的对偶可行性，一旦获得一个原始可行基，则该基必定是最优基。,步骤：(1)保持j 0，j=1,n，确定XB，建立计算表格；,(2)判别XB=B-1b 0是否成立？若成立，XB为最优基变量；若不成立，转(3)；,25,(4)取主变换，得到新的XB。,(3)基变换 换出变量，,换入变量（最大负比值规则），,重复（2）-（4）步，求出结果。,26,例8用对偶单纯形法求解 min w=2x1+3x2+4x3 x1+2x2+x3 1 2x1-x2+3x3 4 x1,x2,x3 0,min w=2x1+3x2+4x3+0 x4+0 x5 x1+2x2+x3-x4 1 2x1-x2+3x3 x5 4 x1,x2,x3,x4,x5 0,27,min w=2x1+3x2+4x3+0 x4+0 x5-x1-2x2-x3+x4-1-2x1+x2-3x3+x5-4 x1,x2,x3,x4,x5 0,28,*,-4,-2.5,2,-0.5,0.5,0,1,0,1,1.5,4,-0.5,x1,-0.5,1,x4,0,2,0,0,1,1,29,初始检验数中有负数？对偶不可行,1、构造扩充问题 增加一个变量和一个约束条件2、求基本解（初始对偶可行）检验数中最小的负数 换入变量 新增变量为换出变量 取主变换后全部检验数非负 3、用对偶单纯形法求解扩充问题扩充问题无可行解，则原问题无可行解扩充问题有最优解，则原问题有可行解，且如扩充问题的目标函数值与M无关，则为原问题最优解。,30,例：,标准型：,扩充问题：,31,*,2M,-3,6-M,1,0,0,0,0,1,1,4,1,x1,0,M-8,x4,0,-2,0,0,2,2,0,x5,1 1 1 0 0 1 M,0,1,-1,32,作业P81 1.12(1),33,4 灵敏度分析,分析 变化对最优解的影响。,1、保持原最优基的变化范围；2、原最优基不再最优时，求新的最优解的最简便方法,34,35,例1 已知下述问题的最优解及最优单纯形表,36,最优单纯形表如下:,37,由最优单纯形表得:,38,39,不可行!,用对偶单纯形法计算,40,4,20,4,41,42,43,例2 求例1 c4的变化范围,使最优解不变.,解:,44,分析:,45,方法:,例3 求例1 c2的变化范围,使最优解不变.,46,解:,0,1/8,3/2,0,0,0,-1/8,1/2,1,0,2,-3,1,1/2,-2,0,0,4,x5,0,0,1/4,0,0,1,4,x1,-2,x5,x4,x3,x2,x1,b,XB,CB,0,0,0,-3,-2,x2,47,48,改变C，求新的最优解?只需修改最终表上的C及检验数，得到新的迭代表，继续求解。,例3 c2=1,求新的最优解.,-2,-2,1,1/4,c2=-3，若c2=4？,最优解不变.,0 0-1/2 5/8 0,1,1,继续用单纯形法求解.,49,分析:,50,51,例4 求例1 a24的变化范围,使最优解不变.,解:,x4为非基变量，故只影响x4的检验数。,52,基变量约束系数的变化会导致问题变得相当复杂，所以重新计算。,53,四、增加一个新变量 例5 在例1的基础上，企业要增加一个新产品,每件产品需2个台时，原材料A 6kg，原材料B 3kg，利润 5元/件，问如何安排各产品的产量，使利润最大？解：,54,表明生产新品有利。,55,56,-5/4,0,1/8,3/2,0,0,1/4,0,-1/8,1/2,1,0,2,-3,2,1,1/2,-2,0,0,4,x5,0,3/2,0,1/4,0,0,1,4,x1,-2,x5,x4,x3,x2,x1,b,XB,CB,-5,0,0,0,-3,-2,x2,8/3,4/2,8,i,x3,2,14,57,五、增加一个新的约束条件1、原最优解满足新约束，则最优解不变。2、若不满足，则需求新的最优解。例:原问题：加条件：,58,需求新解，新条件变为,原最优表：,（0，1，2）不满足新条件,0,0,0,0,0,0,0,0,0,0,3,1,2,0,59,60,61,作业P81 1.13,62,小结,1、对偶问题及其化法,原问题决策变量决定对偶问题约束条件关系,原问题约束条件决定对偶问题决策变量取值方向。,63,2、检验数的计算方法,64,3、对偶问题的性质,4、对偶单纯形法,弱对偶性,无界性,最优性,松弛性,检验数与对偶问题的解,65,5、灵敏度分析,66,(4)增加一个新变量,(5)增加一个约束,