1、第四章 对偶原理,窗含西岭千秋雪，门泊东吴万里船对偶是一种普遍现象,2,x1x2x3,y1 y2 y3 y4,假设工厂考虑不进行生产而把全部可利用的资源都让给其他企业，工厂希望给这些资源定出一个合理的价格，即使别的单位愿意购买，又使本工厂能得到生产这些产品所能获得的最大收益。,3,二、对偶问题的表达,（1）对称LP问题的定义,（2）对称LP问题的对偶问题,第一类对称形式,第二类对称形式,(L),(D),4,例1：写出下列LP问题的对偶问题,对偶,5,（3）对偶问题的对偶,推导过程,变形,(D),6,对偶,变形,结论：对偶问题的对偶为原问题。,(DD),7,写出下列LP问题的对偶问题：,例2：,
2、8,写出对称形式的对偶规划的要点： (1) min变成max (2) 价值系数与右端向量互换 (3) 系数矩阵转置 (4) 变 原问题中约束条件的个数=对偶问题中变量的个数 原问题中变量的个数=对偶问题中约束条件的个数,9,非对称形式的对偶,写成对称形式,对偶问题为：,10,例 min 5x1+4x2+3x3s.t. x1+x2+x3=43x1+2x2+x3 =5x1 0, x2 0, x3 0 对偶问题为max 4w1+5w2s.t. w1+3w25w1+2w2 4w1+w2 3,11,一般情形LP问题的对偶问题,min cx s.t. A1x b1 A1 为m1n , b1为m11A2x
3、=b2 A2 为m2n , b2为m21A3x b3 A3 为m3n , b3为m31x 0 引入松弛变量min cxs.t. A1x xs =b1 xs为m11A2x =b2 A3x +xt = b3 xt为m31x, xs , xt 0,12,min cx s.t. A1x xs =b1 xs为m11A2x =b2 A3x +xt = b3 xt为m31x, xs , xt 0 对偶问题为 max w1b1+ w2b2 + w3b3 s.t. w1A1+ w2A2 + w3A3 c w1Is 0w3It 0max w1b1+ w2b2 + w3b3s.t. w1A1+ w2A2 + w3A
4、3 cw1 0, w3 0,13,min max 变 0 约 量 0 束无限制 = 方程 约 0 束 0 变 方 = 无限制 量 程,14,15,直接写出LP问题的对偶问题,例3,16,17,第二节 对偶问题的基本性质,原问题(L) 对偶问题(D) min cx max wbs.t. Ax b s.t. wA cx 0 w 0,18,定理1：弱对偶定理,19,例：,1）原问题任一可行解 x=(1, 1)T,（LP）,目标值 =40,40是DLP问题最优目标值的上界.,2）对偶问题任一可行解 w=（1 1 1 1）目标值 =1010是LP问题最优目标值的下界.,20,推论1：,若LP(或DLP)
5、问题有无界解，则其对偶问题(或原问题)无可行解； 若LP (或DLP)问题无可行解，则对偶问题(或原问题)或者无可行解,或者目标函数值趋于无穷。,推论2：,极大化问题的任何一个可行解所对应的目标 函数值都是其对偶问题的目标函数值的下界。,极小化问题的任何一个可行解所对应的目标 函数值都是其对偶问题的目标函数值的上界。,推论3：,21,定理2：最优性准则,证明：,22,例5,23,定理3：强对偶定理,若(L),(D)均有可行解,则(L),(D)均有最 优解,且(L),(D)的最优目标函数值相等.,证明：,24,(L),引入剩余变量，把(L)化为标准形,25,26,推论：,在用单纯形法求解LP问题
6、（L）的最优单纯 形表中松弛变量的检验数的相反数(单纯形 乘子w=cBB-1)就是其对偶问题（D）的最优解,27,方法,由于(L) 化成标准形式时,松弛变量xn+j对应的列为-ej，它在目标函数中的价格系数，所以， 判别数cBB-1(-ej)-0=-wj 则松弛变量对应的判别数均乘以(-1)，变得到单纯形乘子w=(w1,wm). 当原问题达最优时,单纯形乘子即为对偶问题的最优解.,28,解：化为标准型,例5 求下列问题对偶问题的最优解,29,4,1,30,2,此时达到最优解。x*=(4,2), MaxZ=14。,31,(L),(DL),32,小结,原问题(min) 对应关系 对偶问题(max)
7、,有最优解,有最优解,无界解,不可行,不可行,无界解,33,（无可行解）,（无可行解）,34,（无界解）,（无可行解）,35,定理4：互补松驰定理,36,证明：（必要性）,37,证明：（充分性）,38,定理4：互补松驰定理(非对称形式）,39,例6 考虑下面问题,40,解:,则，,41,1、定义,对偶问题的经济学解释：影子价格,2、含义,考虑在最优解处,右端项bi的微小变动对目标函数值的影响.,42,若把原问题的约束条件看成是广义的资源约束,则右端项的值表示每种资源的可用量. 对偶解的经济含义:资源的单位改变量引起目标函数值的增加量. 通常称对偶解为影子价格. 影子价格的大小客观地反映了资源在
8、系统内的稀缺程度.资源的影子价格越高,说明资源在系统内越稀缺,而增加该资源的供应量对系统目标函数值贡献越大.,43,木门 木窗 木工 4小时 3小时 120小时/日 油漆工 2小时 1小时 50小时/日 收入 56 30 解：设该车间每日安排 x1 x2 x3 x4 生产木门x1扇，木窗x2。 x3 4 3 1 0 120 max z=56 x1 +30 x2 x4 2 1 0 1 50s.t. 4 x1 +3 x2120 -56 -30 0 0 02 x1 + x2 50 x3 0 1 1 -2 20x1 x2 0 x1 1 1/2 0 1/2 250 -2 0 28 1400x2 0 1
9、1 -2 20x1 0 0 -1/2 -1/2 150 0 2 24 1440,对偶问题的解为: w*=(2, 24),44,（2）告诉管理者花多大代价购买进资源或卖出资源是合适的,3、影子价格的作用,（1）告诉管理者增加何种资源对企业更有利,（3）为新产品定价提供依据,45,对偶单纯形法,定义：设x(0)是(L)的一个基本解（不一定是可行解），它对应的矩阵为B，记w=cBB-1，若w是(L)的对偶问题的可行解，即对任意的j, wPj-cj 0，则称x(0)为原问题的对偶可行的基本解。 结论：当对偶可行的基本解是原问题的可行解时，由于判别数0，因此，它就是原问题的最优解。,46,基本思想： 从
10、原问题的一个对偶可行的基本解出发； 求改进的对偶可行的基本解：每个对偶可行的基本解x=(xBT,0)T对应一个对偶问题的可行解w=cBB-1，相应的对偶问题的目标函数值为wb=cBB-1b，所谓改进的对偶可行的基本解，是指对于原问题的这个基本解，相应的对偶问题的目标函数值wb有改进（选择离基变量和进基变量，进行主元消去）； 当得到的对偶可行的基本解是原问题的可行解时，就达到最优解。,47,与原单纯形法的区别： 原单纯形法保持原问题的可行性，对偶单纯形法保持所有检验数wPj-cj 0，即保持对偶问题的可行性。 特点：先选择出基变量，再选择进基变 量。,48,3、换基迭代,1. 化标准型,建立初始
11、单纯形表,4、回到第2步,(若所有yrj0,则该LP无可行解）,步骤：,49,50,51,-4,-13/4,52,用对偶单纯形法求解下列LP问题,解：原问题变形为,53,-1,-1,54,关于初始对偶可行的基本解,min cx s.t. Ax=bx 0 若初始对偶可行的基本解不易直接得到，则解一个扩充问题，通过这个问题的求解，给出原问题的解答。,55,方法,附加人工约束,56,57,58,显然， （2，3，-2，0，0） 不是对偶可行解， 所以加一个约束,59,60,方法一,x1 x2 x3 x4 x5 x6,1,-1,最优解为 (0,9,0,2,0) 最优值=-4,61,x1 x2 x3 x
12、4 x5 x6,x1 x2 x3 x6,1 0 0 1 -2 0,0 1 0 -3 1 0,0 0 1 -1 -1 0,0 0 0 1 1 1,0 0 0 2 -4 0,1 0 0 0 -3 -1,0 1 0 0 4 3,0 0 1 0 0 1,0 0 0 1 1 1,0 0 0 0 -6 -2,-1/3 0 0 0 1 1/3,-4/3 1 0 0 0 5/3,0 0 1 0 0 1,1/3 0 0 1 6 2/3,-2 0 0 0 0 0,x1 x2 x3 x4,x5 x2 x3 x4,2 3 -2 M,2-M 3+3M M-2 M,(M-2)/3 17/3+5M/3 M-2 2/3+2M
13、/3,0,-2M,-4,1,-3,方法二,62,扩充问题有最优解,最优值=-4,原问题最优值=-4,原问题最优解为,最优值=-4,63,用对偶单纯形法解下列问题,64,最优表为:,扩充问题的最优解是:,65,原始-对偶算法,基本思想： 从对偶问题的一个可行解开始，同时计算原问题和对偶问题，试图求出原问题的满足互补松弛条件的可行解。,66,原问题：,对偶问题：,67,限定原始问题 Restricted primal problem,人工变量,68,限定原始问题的对偶问题,69,70,71,由于对偶问题无上界，所以原问题无可行解。,72,计算步骤,73,74,限定原始问题目标函数值,对偶问题可行解为w时所有的wpj-cj,对偶问题函数值f=wb,75,用原始-对偶算法解下列问题,解：对偶问题为,76,限定原始问题为：,77,78,1,79,80,
