线性规划4—对偶单纯形.ppt

1.6 线性规划的对偶理论 （Duality Theory）,窗含西岭千秋雪，门泊东吴万里船 对偶是一种普遍现象,本节主要内容：,线性规划的对偶模型 对偶性质 对偶单纯形法,学习要点： 1. 理解线性规划的对偶性质 2. 掌握对偶单纯形法的解题思路及求解步骤,一、线性规划的对偶模型,设某工厂生产两种产品甲和乙，生产中需4种设备按A，B，C，D顺序加工，每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表 ：,表1. 产品数据表,问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得最大利润？,1. 对偶问题的现实来源,线性规划的对偶模型,解：设甲、乙型产品各生产x1及x2件，则数学模型为：,反过来问：若厂长决定不生产甲和乙型产品，决定出租机器用于接受外加工，只收加工费，那么种机器的机时如何定价才是最佳决策？,线性规划的对偶模型,在市场竞争的时代，厂长的最佳决策显然应符合两条： （1）不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型产品所获利润。由此原则，便构成了新规划的不等式约束条件。 （2）竞争性原则。即在上述不吃亏原则下，尽量降低机时总收费，以便争取更多用户。,设A、B、C、D设备的机时价分别为y1、y2、y3、y4，则新的线性规划数学模型为：,线性规划的对偶模型,把同种问题的两种提法所获得的数学模型用表2表示，将会发现一个有趣的现象。,表2. 原问题与新问题对比表,线性规划的对偶模型,2. 原问题与对偶问题的对应关系,原问题 （对偶问题）,对偶问题 （原问题）,线性规划的对偶模型,特点：目标函数求极大值时，所有约束条件为号，变量非负;目标函数求极小值时，所有约束条件为号，变量非负.,对称形式的对偶线性规划问题,对合性,定理6.1 对偶线性规划的对偶问题是原始线性规划问题。,对偶定义,对偶定义,线性规划的对偶模型,例1 写出线性规划问题的对偶问题,解：首先将原问题变形为,线性规划的对偶模型,若给出的线性规划不是对称形式，可以先化成对称形式再写对偶问题。,线性规划的对偶模型,线性规划的对偶变换规则,对偶问题的形成,min z= 2x1+4x2-x3 s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15,max w=6y1+12y2+8y3+15y4 s.t. 3y1- y2+2y3+ y4 2 -y1+2y2+ y3+3y4 4 2y1- 3y2+2y3- y4 -1 y1 0,y2 ,y3 0,y4 0,=,unr,=,x10,x20,x3: unr,例3 写出下列线性规划问题的对偶问题.,解：原问题的对偶问题为,非对称形式的对偶线性规划问题,练习,写出下面线性规划的对偶规划模型,解： 先将约束条件变形为“”形式,再根据非对称形式的对应关系，直接写出对偶规划,为了便于讨论，下面不妨总是以非对称形式的线性规划问题作证明.,二、对偶性质,若x 0 ,y 0分别是(LP)与(DP)的可行解,则,定理6.2 弱对偶原理(弱对偶性)：设 和 分别是问题(LP)和(DP)的可行解，则必有,证明：,于是，,推论1: 原问题任一可行解的目标函数值是其对偶问题目标函数值的上界；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的下界。,二、对偶性质,推论2: 在一对对偶问题（LP）和（DP）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；这也是对偶问题的无界性。,推论3：在一对对偶问题（LP）和（DP）中，若一个有可行解，而另一个无可行解，则该可行的问题目标函数值无界。,定理6.3 最优性定理：如果 是原问题的可行解， 是其对偶问题的可行解，并且:,则 是原问题的最优解， 是其对偶问题的最优解。,设x 是(LP) 问题的任一可行解,则,证明：,二、对偶性质,考虑如下的线性规划,考虑基解 (0,1,0,-2)T (不可行),对应的规范式为,其判别数向量 (7/2,0,3/2,0)是非负的.,二、对偶性质,判别数向量用(LP)中的符号可以记为,则判别数向量为,上述的判别数向量非负，因此有,即,这说明y是对偶规划的可行解.,这一可行解对应的目标函数值为,即为在原始线性规划中基解对应的目标函数值.,二、对偶性质,判别数非负,对偶解可行,对偶的线性规划问题的解,定理6.4 设B是问题,的一个基矩阵,对应的 基解满足最优性条件,则对偶线性规划问题有可行解,在上述条件下,(LP)的基解的目标 函数值等于(DP)的解的目标函数值.,定理6.5 若原始线性规划问题与对偶线性规划问题之一有最优解,则另一个也有最优解,并且它们目标函数的最优值相等.,证明: 考虑到对合性,只需选取两个规划中的任一个证明.,设,有最优解x0,且其为基可行解,再设基矩阵为B,x0为最优解,判别数非负,有,y0可行,且,y0是对偶规划最优解.,对偶的线性规划问题的解,定理6.6 强对偶性：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。,推论4：（LP）与（DP）要么两者都有最优解，要么都无最优解。,二、对偶性质,两个互为对偶的线性规划的解的情况,(3) 一个有可行解,无最优解(目标函数无界),则 另一个无可行解.,两个都有可行解, 两个都有最优解,且最 优值相等.,(2) 两个都无最优解.,(4) 一个有可行解，另一个无可行解，则可 行的一个目标函数无界.,判断下列结论是否正确？,3）互为对偶问题，或者同时都有最优解，或者 同时都无最优解.,1）任何线性规划都存在一个对应的对偶线性规划.,2）原问题第i个约束是“”约束，则对偶变量yi0.,4）对偶问题有可行解，则原问题也有可行解.,5）原问题有多重解，对偶问题也有多重解.,6）对偶问题有可行解，原问题无可行解，则 对偶问题具有无界解.,7）原问题无最优解，则对偶问题无可行解.,8）对偶问题不可行，原问题可能有无界解.,9）原问题与对偶问题都可行，则都有最优解.,10）原问题具有无界解，则对偶问题不可行.,11）对偶问题具有无界解，则原问题无最优解.,12）若X*、Y*是原问题与对偶问题的最优解， 则X*=Y*.,二、对偶性质,分别求解下列2个互为对偶关系的线性规划问题,分别用单纯形法求解上述2个规划问题，得到最终单纯形表如下表：,对偶性质,原问题最优表,对偶问题最优表,对偶性质,原问题与其对偶问题的变量与解的对应关系： 在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量。,对偶定理,定理6.7 互补松弛性：设X0和Y0分别是(LP) 问题和 (DP) 问题的可行解，则它们分别是最优解的充要条件是：,其中：Xs为松弛变量、Ys为剩余变量.,互补松弛条件,证：由定理所设，可知有,分别以Y0T左乘(1)式，以X0右乘(2)式后，两式相减，即得,由可行性及最优性条件，可知有,反之亦然。 证毕。,定理6.7* 互补松弛性：设X0和Y0分别是(LP) 问题和 (DP) 问题的可行解，则它们分别是最优解的充要条件是：,互补松弛条件,可写为：,对偶性质,定理6.7的应用： 该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知Y*求X*或已知X*求Y*,由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系： 若Y*0，则Xs必为0；若X*0，则Ys必为0 利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。,对偶性质,例2.4 已知线性规划,的最优解是X*=(6,2,0)T,求其对偶问题的最优解Y*。,解：写出原问题的对偶问题，即,标准化,对偶性质,设对偶问题最优解为Y*(y1，y2),由互补松弛性定理可知，X*和 Y*满足：,即：,因为x10，x20，所以对偶问题的第一、二个约束的松弛变量等于零，即y30，y40，带入方程中：,解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为： Y*=(1,1)，最优值w=26。,对偶性质,例2.5 已知线性规划,的对偶问题的最优解为Y*=(0,-2)，求原问题的最优解。,解: 对偶问题是,标准化,对偶性质,设对偶问题最优解为X*(x1，x2 ，x3)T ,由互补松弛性定理可知，X*和 Y*满足：,将Y*带入由方程可知，y3y50，y41。,y2=-20 x50 又y4=10 x20,将x2，x5分别带入原问题约束方程中，得：,解方程组得：x1=-5,x3=-1, 所以原问题的最优解为,X*=(-5,0,-1)，最优值 z=-12,三、单纯形方法对偶单纯形法,用单纯形方法求解线性规划时, x的可行性是满足的,但是最优性条件不满足，即w不可行. 迭代是使最优性条件逐步得到满足,（检验数非负），即使w逐步可行的过程。,构造另一种方法,最优性条件始终满足,即y可行,而x不可行. 逐步迭代使x最终可行,从而是最优解.,对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。而不是求解对偶问题的单纯形法。,判别数向量非负,为对偶规划的可行解,单纯形方法,保证解可行,最优性条件不满足 (有负判别数),对偶规划解不可行,最优性条件满足 (判别数非负),对偶规划解可行,形方法 对偶单纯,划解可行 保证对偶规,解不可行,解可行,两种方法都始终保证,对偶单纯形法原理,对偶单纯形法,对偶单纯形法基本思路：,找出一个对偶问题的可行基，保持对偶问题为可行解的条件下，判断XB是否可行（XB为非负），若否，通过变换基解，直到找到原问题基可行解（即XB为非负），这时原问题与对偶问题同时达到可行解，由定理6.4可得最优解。,对偶单纯形法,找出一个DP的可行基,LP是否可行 （XB 0）,保持DP为可行解情况下转移到LP的另一个基本解,最优解,是,否,循 环,结束,对偶单纯形法,1. 最优解的判别,已知线性规划问题的基矩阵B及它对应的基解,则所得的基解为最优解.,并且此基解的所有判别数非负.,2. 确定出(离)基变量,则以xl为离基变量,若xl所在行的所有系数alj0 (j=1,2,n),则线性规划问题无可行解.,(此时若有可行解,3.确定进基变量,对偶单纯形法,设目标函数的形式为,已确定离基变量为xl,设进基变量为xk.在目标函数中,用xk替换xl ，,得,3.确定进基变量,由(1)式，,则xk为进基变量,为保持判别数非负，有,例 2.6. 用对偶单纯形法求解：,引入松弛变量得到标准型线性规划,解：,构造对偶单纯形表 选取离基变量,选取进基变量,基解已可行,最优解为 x*= (0,3/2, 1/8,0) T,最优值为 z*=14,对偶单纯形法,例2.7 用对偶单纯形法求解：,解: 将模型化为标准型。,对偶单纯形法,对偶单纯形法,对偶单纯形法,原问题的最优解为：X*=（2 , 2 , 2 , 0 , 0 , 0），Z* =72 其对偶问题的最优解为：Y*= （1/3 , 3 , 7/3），W*= 72,对偶单纯形法,对偶单纯形法应注意的问题：,用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解.,初始表中一定要满足对偶问题可行，也就是说检验数满足最优判别准则.,对偶单纯形法与普通单纯形法的换基顺序不一样，普通单纯形法是先确定进基变量后确定出基变量，对偶单纯形法是先确