运筹学第二章线性规划的对偶理论.ppt

第二章 线性规划,解：设生产x1的产品I，x2的产品II，则,目标函数 max z 2x1+3x2约束条件 x1+2x2 8 4 x1 16 4x2 12 x1 x2 0,线性规划的对偶理论,例1 某厂可生产产品和，生产I需1台设备，4单位原料A，生产II需2台设备，4单位原料B。该厂每生产一件产品获利2元每生产一件产品获利3元。现有8台设备，16单位原料A，12单位原料B，问如何安排计划使获利最多?,第二章 线性规划,对偶问题的提出 原问题与对偶问题的关系 对偶问题的基本性质 对偶单纯形法 灵敏度分析,4.1 对偶问题的提出,我们从另一个角度来讨论这个问题：假设不生产产品，而将所有资源出租或外售。问题：考虑每种资源如何定价。,4.1 对偶问题的提出,例1 产品：1台设备，4单位原料A，获利2元；产品：2台设备，4单位原料B，获利3元。现有：8台设备，16单位原料A，12单位原料B,设y1，y2，y3分别表示出售单位设备台时的租金和出让原材料A，B的附加额。根据题意可得：,y1+4y22，2 y1+4y33，,=8 y1+16y2+12y3,要实现出租的愿望，只能在满足所有产品的利润条件下，必须使尽可能的小。,4.1 对偶问题的提出,为此需解决如下的线性规划问题：,与,关系？,对原模型设：,C=(2，3),b=(8,16,12)T,X=（x1，x2）T,Y=（y1，y2，y3）,则可得:,4.1 对偶问题的提出,和,我们把（5.2）式的问题称为（5.1）式问题的对偶线性规划问题。,第二章 线性规划,对偶问题的提出 原问题与对偶问题的关系 对偶问题的基本性质 对偶单纯形法 灵敏度分析,4.2 原问题与对偶问题的关系,1对称式的对偶,“”不等式约束条件的原问题与“”不等式约束条件的对偶问题，称为对称式的一对对偶问题。,原问题：,对偶问题：,n个变量，m个约束条件,m个变量，n个约束条件,2约束条件全部为“=”的对偶,原问题：,其中 Y1=(y1,y2,ym)，Y2=(ym+1,ym+2,y2m),对偶问题,4.2 原问题与对偶问题的关系,3约束条件为“”的对偶,原问题：,对偶问题,4变量0的对偶,原问题：,令X=X1,对偶问题,5变量无约束的对偶,原问题：,对偶问题,6原问题与对偶问题的关系表,例：求下列线性规划问题的对偶问题,C=(5,4,6),b=(2,3,-5,1)T,解：,因原问题有3个变量，4个约束条件，所以对偶问题4个变量，3个约束条件。设变量Y=(y1,y2,y3,y4),min=2y1+3y25y3+y4,于是,y1+y23y3+y45,2y1+2y3y44,y2+y3+y46,y10,y2,y3 0,y4无约束,第二章 线性规划,对偶问题的提出 原问题与对偶问题的关系 对偶问题的基本性质 对偶单纯形法 灵敏度分析,4.3 对偶问题的基本性质,1对称性：对偶问题的对偶问题是原问题。,证：,设原问题为：max z=CX；AXb；X0,则,对偶问题为：min=Yb；YAC；Y 0,因min=max(),max()=Yb；YAC；Y 0,min(1)=CX；AX b；X 0,对偶问题,又因min(1)=max(1),max(1)=CX；AX b；X 0,这就是原问题。,4.3 对偶问题的基本性质,2弱对偶性：若X(0)是原问题的可行解，Y(0)是对偶问题的可行解，则存在CX(0)Y(0)b。,证：,设原问题为：max z=CX；AXb；X0,则,因X(0)是原问题的可行解，所以AX(0)b,又因Y(0)是对偶问题的可行解，所以Y(0)AC,Y(0)A X(0)Y(0)b,因此，CX(0)Y(0)A X(0)Y(0)b,结论成立。,对偶问题为：min=Yb；YAC；Y 0,Y(0)A X(0)CX(0),4.3 对偶问题的基本性质,3无界性：若原问题无界解，则其对偶问题无可行解。,证：由弱对偶性可知结论成立。(CX(0)Y(0)b),4最优性：若X(0)是原问题的可行解，Y(0)是对偶问题的可行解，且CX(0)=Y(0)b，则X(0)，Y(0)是最优解。,证：,设Y(1)是对偶问题的任意可行解，由性质2可得,Y(1)b CX(0)=Y(0)b，则,Y(0)是对偶问题的最优解。,设X(1)是原问题的任意可行解，由性质2可得,CX(0)=Y(0)b CX(1)，则,X(0)是原问题的最优解。,4.3 对偶问题的基本性质,5对偶定理：若原问题有最优解，那么对偶问题也有优解；且目标函数值相等。,证：,设X(0)是原问题的最优解，它对应的基B，必有CCBB-1A0，且 z=CX(0)=CBB-1b。,令Y(0)=CBB-1,显然，Y(0)AC。,所以 Y(0)是对偶问题的可行解。,又因Y(0)b=CBB-1b=CX(0),由性质4可知Y(0)是对偶问题的最优解。,因此，结论成立。,6互补松弛性：若X(0)是原问题的可行解，Y(0)是对偶问题的可行解，则YX(0)=0和Y(0)X=0 当且仅当X(0)，Y(0)是最优解。,证：,设原问题和对偶问题的标准型是,将原问题目标函数中的系数向量C用C=YAY代替：,z=(YAY)X=YA X YX(5.3),对偶问题目标函数中的系数向量，用b=AX+X代替：,=Y(AX+X)=YA X+YX(5.4),Y X(0)=0和Y(0)X=0,则Y(0)b=Y(0)A X(0)=CX(0),X(0),Y(0)最优解,则Y(0)b=Y(0)AX(0)=CX(0)(性质3),所以Y X(0)=0和Y(0)X=0。,X(0)，Y(0)是最优解,7设原问题：max z=CX；AX+X=b；X,X 0 对偶问题：min=Yb；YA Y=C；Y,Y 0。则原问题单纯形表的检验数行对应其对偶问题的一个基解。其关系如表：,这里Y1对应原问题的基变量XB的剩余变量，Y2对应原问题的非基变量XN的剩余变量。,证：,设B是一可行基，于是A=(B,N),4.3 对偶问题的基本性质,其中Y=(Y1,Y2),当原问题的解为：XB=B-1b 时，其检验参数为 CNCBB-1N 与CBB-1。,令Y=CBB-1，将它代入(5.5)和(5.6)得,Y1=0，Y2=CNCBB-1N,因此，结论成立。,4.3 对偶问题的基本性质,8单纯形乘子Y的定理：若B是原问题的一最优可行基，则单纯形乘子Y=CBB-1是对偶问题的一个最优解。,证：设X(0)是对应基B的原问题的最优解，则,显然，Y AC。,所以 Y 是对偶问题的可行解。,又因Yb=CBB-1 b=CX(0),由性质4可知Y 是对偶问题的最优解。,因此，结论成立。,CCBB-1A0，且 z=C X(0)CBB-1b。,根据本性质，可以从原问题最优解的单纯形表中直接得到对偶问题的最优解。,9最优对偶变量(影子价格)的经济解释,从对偶定理可知，当达到最优解时，原问题和对偶问题的目标函数值相等，即z=CX(0)=Y(0)b=CBB-1b.,也即z=CX(0)=Y(0)b=CBB-1b=y1(0)b1+y2(0)b2+ym(0)bm 其中 X(0),Y(0)分别是原问题和对偶问题的最优解。,现在考虑在最优解处，常数项bi的微小变动对目标函数值的影响(不改变原来的最优基).求z对bi的偏导数，可得：,这说明，若原问题的某一约束条件的右端常数项 bi 增加一个单位，则由此引起的最优目标函值的增加量，就等于该约束条件相对应的对偶变量的最优值。,最优变量yi(0的值，就相当于对单位第I种资源在实现最大利润时的一种估价。这种估价是针对具体企业具体产品而存在的一种特殊价格，称它为“影子价格”。,“影子价格”对市场有调节作用。,例 已知线性规划问题,其对偶问题的最优解为y1*=4/5,y2*=3/5；z=5。试用对偶理论找出原问题的最优解。,解：,对偶问题,max z4y1+3y2,y1+2y2 2,y1 y2 3,2y1+3y2 5,y1y20,y1+y2 2,3y1+y2 3,C=(2,3,5,2,3),b=(4,3)T,Y=(y1,y2),设X=(x1,x2)T，,Y=(y1,y2,y3,y4,y5),把y1*=4/5,y2*=3/5 代入约束条件中可得,Y=(0,14/5,8/5,2/5,0),据互补松弛性：YX*=0,YX*=14/5x2*+8/5x3*+2/5x4*=0,所以x2*=x3*=x4*=0,又因Y*X=4/5x1+3/5x2=0,所以x1=x2=0,4.3 对偶问题的基本性质,因为,所以,x1*=1，x5*=1,因此，原问题最优解为 X*=(1，0，0，0，1)T,，*=5。,第二章 线性规划,对偶问题的提出 原问题与对偶问题的关系 对偶问题的基本性质 对偶单纯形法 灵敏度分析,4.4 对偶单纯形法,1对偶单纯形法与单纯形法的区别,1.1 对偶单纯形法的思路,原理：由性质7可知：在单纯形表中进行迭代时，在b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。通过逐步迭代，当在检验数行得到对偶问题的解也是基可行解时，根据性质4，5可知，已得到最优解。即原问题与对偶问题都是最优解。,思路：在进行迭代时，保持对偶问题的解是基可行解，即cjCBB-1pj0，而原问题通过逐步迭代，达到基可行解，这样就得到最优解。,4.4 对偶单纯形法,对偶单纯形法：在逐步迭代中，保持检验数行 cjCBB-1pj 0，即保持对偶问题的解是基可行解。通过迭代得到原问题的基可行解。,说明：对偶单纯法是运用对偶原理求解原问题的一种方法，而不是求解对偶问题的单纯法。,2对偶单纯形法求解步骤,2.1 对偶可行的基解：,设X(0)是原问题的基解，其对应的基为B，记Y=CBB-1，若Y是对偶问题的基可行解。即C CBB-1A 0，则称X(0)是原问题的对偶可行的基解。,2.2 对偶单纯形法的计算步骤,列出初始单纯形表,最优性检验,根据线性规划问题，确定一个对偶可行的基解，列出初始单纯形表。,检查b列的数，若都为非负，则已得到最优解。停止计算。若b列的数中，还有分量为负数，则进行下一步计算。,确定换出变量,按min(B-1b)i|(B-1b)i0=(B-1b)l 确定xl为换出变量。,确定换入变量,如果xl所在行各系数alj(j=1,2,n).都有alj 0，则无可行解，停止计算。,如果 有alj 0(j=1,2,n),则计算,确定xk为换入 变量，且保持得到的对偶问题的解是基可行解。,迭代运算,以alk为主元素，对单纯形表进行迭代运算，得到新单纯表。,重复,“按规则确定换入变量，确保变换后，对偶问题的解仍然是可行解。”的证明：,因经过初等变换后,所以变换后，对偶问题的解是基可行解。,（j是非基变量下角标。）,2.3 两个说明,初始对偶可行的基解的确定,运用对偶单纯法，需要先给定一个对偶可行的基解，而这个解有时不易直接得到。我们可先构造一个扩充,问题，通过求解扩充问题的解给出原问题的解。,原问题如下，是一基，是非基向量构成的矩阵。,增加一个变量xn+1，和一个约束条件,M是大正数。于是扩充问题,可以得基解,由此易求一对偶可行的基解。,4.4 对偶单纯形法,若(0)不是对偶可行的，即检验数中有正的。并设正检验数中最大的一个为k，则以k相应的变量xk为换入变量，以xn+1为换出变量，即以am+1,k为主元素进行初等变换，可得到全部检验数，即得到一个对偶可行的基解。理由如下：,初等变换前后检验数之间的关系:,其中j是变换后新基下的检验数。,当jNn+1时，am+1,j=1，所以j=j k0,因此，变换后，有j 0，得到的基解是对偶可行的。,扩充问题的解与原问题解的关系：若扩充问题无可行解，则原问题无可行解。若扩充问题的目标函数最优值与M无关，则得到原问题的最优解。,用对偶单纯形法求扩充问题的最优解，依此得到原问题最优解。,2.4 举例,例 用对偶单纯形法求解,解：,其中x4,x5为松弛变量,原最优 X*=(11/5,2/5,0,0,0)T，对偶最优 Y*=(8/5,1/5),第二章 线性规划,对偶问题的提出 原问题与对偶问题的关系 对偶问题的基本性质 对偶单纯形法 灵敏度分析,4.5 灵敏度分析,在前面讨论线性规划问题时，假定aij,bi,cj都是常数.但实际上这些参数往往是估计值和预测值.所谓灵敏度分析,就是要研究初始单纯形表上的系数变化对最优解的影响,研究这些系数在什么范围内变化时,原最优基仍是最优；若原最优基不再是最优的，如何用最简便的方法找到新的最优解。,设资源br发生变化，即br=br+br。并假定其它系数不变。则解变化为 XB=B-1(b+b)，其中b=(0,br，,0）T。由于br变化不影响检验数，所以只要XB0，最优基不变,XB是最优解。,要使XB0，只有bi+air br 0,i=1,2,m 所以,air br bi,i=1,2,m,当 air 0时，br bi/air,当 air 0时，br bi/air,于是得到,max bi/air|air 0 br,min bi/air|air 0,当 br（r=1,2,m)取上述范围之内的值，XB为最优。,如果 br取值在上述范围之外时，由于检验数不变，所以此时基解是对偶可行的基解。就可以用对偶单纯形法求最优解。,2.目标函数中价值系数cj的变化分析,设价值系数cj的改变 cj。分非基变量和基变量讨论。,设cj是非基变量xj系数，则其检验数j=cjCBB-1pj,当cj改变 cj后，j=cj+cj CBB-1pj 要使原最优解，只有j0，所以有 cj CBB-1pj cj。,设cr是基变量xr系数。因cr CB，所以当cr变化 cr时，就引起CB变化，,(CB+CB)B-1A=CB B-1A+(0,cr,0)B-1A,=CB B-1A+cr(ar1,ar2,arn)。当cr变化 cr 后，检验数为：,j=cj CBB-1A cr arj j=1,2,n,若要使原最优解不变，必须j0。于是得到,当 arj 0时，cr j/arj,当 arj 0时，cr j/arj j=1,2,n,max j/arj|arj 0 cr,min j/arj|arj 0,3.技术系数aij的变化,非基向量Pj变为Pj。这一改变直接影响第j数据和第j个检验数j=cj CBB-1 Pj。,4.5 灵敏度分析,若j0，则原最优解仍是新问题的最优解。,若j0，则原最优基不再是最优基，此时在原问题的最终表的基础上，换上改变后的第j列数据B-1 Pj和j，把 xj作为换入变量，用单纯形法继续迭代。,基向量Pj变为Pj。此时原最优解的可行性和最优性都遭到破坏，一般不修改原来的最终表，而是重新计算。,