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

运筹学基础运筹学基础1 1第二章第二章 线性规划线性规划q 对偶问题的提出对偶问题的提出q 原问题与对偶问题的关系原问题与对偶问题的关系q 对偶问题的基本性质对偶问题的基本性质q 对偶单纯形法对偶单纯形法q 灵敏度分析灵敏度分析2 2运筹学基础运筹学基础解：解：设生产设生产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，问如何安排计划使获利最多，问如何安排计划使获利最多?运筹学基础运筹学基础3 3第二章第二章 线性规划线性规划q 对偶问题的提出对偶问题的提出q 原问题与对偶问题的关系原问题与对偶问题的关系q 对偶问题的基本性质对偶问题的基本性质q 对偶单纯形法对偶单纯形法q 灵敏度分析灵敏度分析4 44.1 4.1 对偶问题的提出对偶问题的提出运筹学基础运筹学基础我我们们从从另另一一个个角角度度来来讨讨论论这这个个问问题题：假假设设不不生生产产品产产品，而将所有资源出租或外售。，而将所有资源出租或外售。问题：考虑每种资源如何定价。问题：考虑每种资源如何定价。5 54.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要实现出租的愿望，只能在满足要实现出租的愿望，只能在满足所有产品的利润所有产品的利润条件下，必须使条件下，必须使尽可能的小。尽可能的小。6 64.1 4.1 对偶问题的提出对偶问题的提出运筹学基础运筹学基础为此需解决如下的线性规划问题：为此需解决如下的线性规划问题：y1+4y2 2 2 y1 +4y33 min=8 y1+16y2+12y2 y1，y2，y30 max z2x1+3x2x1 2x2 84x1 16 4x2 12x1x2 0与与关系？关系？对原模型设：对原模型设：1 2 4 0 0 4 A=C=(2，3)b=(8,16,12)TX=（x1，x2）TY=（y1，y2，y3）则可得则可得:7 74.1 4.1 对偶问题的提出对偶问题的提出运筹学基础运筹学基础max z=CXAXb （5.1）X0 y1+4y2 2 2 y1 +4y33 min=8 y1+16y2+12y3 y1，y2，y30 max z2x1+3x2x1 2x2 84x1 16 4x2 12x1x2 0与与有何关有何关系？系？对愿模型设：对愿模型设：1 2 4 0 0 4 A=C=(2，3)b=(8,16,12)TX=（x1，x2）TY=（y1，y2，y3）则可得则可得:min =YbYA C （5.2）Y0和和我们把（我们把（5.2）式的问题称为（）式的问题称为（5.1）式问题的）式问题的对偶线对偶线性规划问题性规划问题。运筹学基础运筹学基础8 8第二章第二章 线性规划线性规划q 对偶问题的提出对偶问题的提出q 原问题与对偶问题的关系原问题与对偶问题的关系q 对偶问题的基本性质对偶问题的基本性质q 对偶单纯形法对偶单纯形法q 灵敏度分析灵敏度分析9 94.2 4.2 原问题与对偶问题的关系原问题与对偶问题的关系运筹学基础运筹学基础1对称式的对偶对称式的对偶“”不等式约束条件的原问题与不等式约束条件的原问题与“”不等式约束条件的对不等式约束条件的对偶问题，称为偶问题，称为对称式对称式的一对对偶问题。的一对对偶问题。原问题：原问题：max z=c1x1+c2x2+cnxn a11 a12 a1n am1 am2 amnx1xnb1bm x1，x2，xn0对偶问题：对偶问题：min =b1y1+b2y2+bmym a11 a12 a1n am1 am2 amn y1，y2，ym 0(y1,y2,ym)(c1,c2,cn)n个变量，m个约束条件 m个变量，n个约束条件1010运筹学基础运筹学基础2约束条件全部为约束条件全部为“=”的对偶的对偶max z=CXAXbX0原问题：原问题：max z=CXAXbX0AXb等价max z=CXAXbX0AXbmax z=CXX0AAXbbmin =(Y1,Y2)Y1,Y20AACbb(Y1,Y2)其中其中 Y1=(y1,y2,ym)，Y2=(ym+1,ym+2,y2m)等价等价min =YbY为无约束为无约束YA Cmin =(Y1Y2)bY1,Y20(Y1 Y2)A C令令Y=(Y1 Y2)对偶问题对偶对偶问题问题11114.2 4.2 原问题与对偶问题的关系原问题与对偶问题的关系运筹学基础运筹学基础3约束条件为约束条件为“”的对偶的对偶max z=CXAXbX0原问题：原问题：max z=CXAX bX0min =Y1(b)Y1(A)CY10min =YbYA CY0等价等价对对偶偶问问题题令令Y=Y1对偶对偶问题问题1212运筹学基础运筹学基础4变量变量0的对偶的对偶max z=CXAXbX0原问题：原问题：令令X=X1max z=C(X1)A(X1)bX10max z=(C)X1(A)X1 bX10min =Y bY(A)CY0min =Y bY A CY0对对偶偶问问题题对偶对偶问题问题等等价价1313运筹学基础运筹学基础5变量无约束的对偶变量无约束的对偶max z=CXAXbX无约束无约束原问题：原问题：令令X=X1 X2 X1，X20max z=CX1CX2X1,X20AX1 AX2 bmax z=(C,C)X1,X20bX1X2(A,A)X1X2等等价价min =YbY0Y(A,A)(C,C)对对偶偶min=YbYACY0 YA Cmin=YbYA CY0min=YbYACY0YA C等价等价等等价价等等价价对偶对偶问题问题1414运筹学基础运筹学基础6原问题与对偶问题的关系表原问题与对偶问题的关系表原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 max zn个变量个变量变量变量0变量变量0变量无约束变量无约束目标函数目标函数 min n个约束条件个约束条件约束约束约束约束约束约束=m个约束条件个约束条件约束约束约束约束约束约束=约束条件右端项约束条件右端项目标函数变量系数目标函数变量系数m个变量个变量变量变量0变量变量 0变量无约束变量无约束 目标函数变量系数目标函数变量系数约束条件右端项约束条件右端项1515运筹学基础运筹学基础例：求下列线性规划问题的对偶问题例：求下列线性规划问题的对偶问题 max z5x1+4x2+6x3x1+2x2 2x1 +x3 33x1+2x2+x3 5x1 0 x20,x3 无约束无约束 x1x2 +x3=1C=(5,4,6)b=(2,3,-5,1)T1 2 01 0 1 -3 2 1A=1-1 1解：解：因原问题有因原问题有3个变个变量，量，4个约束条件，个约束条件，所以对偶问题所以对偶问题4个个变量，变量，3个约束条个约束条件。设变量件。设变量Y=(y1,y2,y3,y4)min=2y1+3y25y3+y4于是于是 y1+y23y3+y45 2y1 +2y3y44 y2 +y3+y46y10,y2,y3 0,y4无约束无约束Y AC确定约束条件确定约束条件运筹学基础运筹学基础1616第二章第二章 线性规划线性规划q 对偶问题的提出对偶问题的提出q 原问题与对偶问题的关系原问题与对偶问题的关系q 对偶问题的基本性质对偶问题的基本性质q 对偶单纯形法对偶单纯形法q 灵敏度分析灵敏度分析17174.3 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这就是原问题。这就是原问题。18184.3 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 0Y(0)A X(0)CX(0)19194.3 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)是原问题的最优解。是原问题的最优解。20204.3 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)是对偶问题的最优解。是对偶问题的最优解。因此，结论成立。因此，结论成立。2121运筹学基础运筹学基础6互补松弛性：互补松弛性：若若X(0)是原问题的可行解，是原问题的可行解，Y(0)是对偶是对偶问题的可行解，则问题的可行解，则YX(0)=0和和Y(0)X=0 当且仅当当且仅当X(0)，Y(0)是最优解。是最优解。证：证：max z=CXAX+x=bX0，X 0设原问题和对偶问题的标准型是设原问题和对偶问题的标准型是min =YbYAY=CY0，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)是最优解是最优解2222运筹学基础运筹学基础7设原问题：设原问题：max z=CX；AX+X=b；X,X 0 对偶问题：对偶问题：min=Yb；YA Y =C；Y,Y 0 。则原问题单纯形表的检验。则原问题单纯形表的检验数行对应其对偶问题的一个基解。其关系如表：数行对应其对偶问题的一个基解。其关系如表：0Y1CN1 CB B-1N1Y2 CB B-1Y这里这里Y1对应原问题的基变量对应原问题的基变量XB的剩余变量，的剩余变量，Y2对应原问题的对应原问题的非基变量非基变量XN的剩余变量。的剩余变量。证：证：max z=CBXB+CNXNBXB+BXN+X=bXN,XB,X 0设设B是一可行基，于是是一可行基，于是A=(B,N)min =YbYBY1=CB (5.5)Y,Y1 Y2 0YNY2=CN (5.6)23234.3 4.3 对偶问题的基本性质对偶问题的基本性质运筹学基础运筹学基础证：证：max z=CBXB+CNXNBXB+BXN+X=bX,XB,X 0设设B是一可行基，于是是一可行基，于是A=(B,N)min =YbYBY1=CB (5.5)Y,Y1 Y2 0YNY2=CN (5.6)其中其中Y=(Y1,Y2)当原问题的解为：当原问题的解为：XB=B-1b 时，其检验参数为时，其检验参数为 CNCBB-1N 与与CBB-1。令令Y=CBB-1，将它代入，将它代入(5.5)和和(5.6)得得Y1=0，Y2=CNCBB-1N 因此，结论成立。因此，结论成立。24244.3 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 。根据本性质，根据本性质，可以从原问可以从原问题最优解的题最优解的单纯形表中单纯形表中直接得到对直接得到对偶问题的最偶问题的最优解。优解。2525运筹学基础运筹学基础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的偏导数，可得：的偏导数，可得：y1(0)zb1,y2(0)zb2,ym(0)zbm,这说明这说明，若原问题的某一约束条件的右端常数项，若原问题的某一约束条件的右端常数项 bi 增加一个单增加一个单位，则由此引起的最优目标函值的增加量，就等于该约束条件位，则由此引起的最优目标函值的增加量，就等于该约束条件相对应的对偶变量的最优值。相对应的对偶变量的最优值。最优变量最优变量yi(0的值的值，就相当于对单位第，就相当于对单位第I种资源在实现最大利润时种资源在实现最大利润时的一种估价。这种估价是针对具体企业具体产品而存在的一种的一种估价。这种估价是针对具体企业具体产品而存在的一种特殊价格，称它为特殊价格，称它为“影子价格影子价格”。“影子价格影子价格”对市场有调节作用。对市场有调节作用。2626运筹学基础运筹学基础例例 已知线性规划问题已知线性规划问题 x1+x2+2x3+x4+3x5 4 2x1x2+3x3+x4+x5 3 min=2x1+3x2+5x3+2x4+3x5 x1,x2,x3,x4,x50其对偶问题的最优其对偶问题的最优解为解为y1*=4/5,y2*=3/5；z=5。试。试用对偶理论找出原用对偶理论找出原问题的最优解。问题的最优解。解：解：对偶问题对偶问题 max z4y1+3y2y1+2y2 2 y1 y2 3 2y1+3y2 5 y1y20y1+y2 2 3y1 +y2 3 C=(2,3,5,2,3)b=(4,3)T1 1 2 1 3 A=2-1 3 1 1Y AC确定约确定约束条件束条件 Y=(y1,y2)原原对对min变变00无无max约约约约变变00无无关系表关系表形形成成2727运筹学基础运筹学基础原原对对min变变00无无max约约约约变变00无无解：解：对偶问题对偶问题 max z4y1+3y2y1+2y2 2 y1y2 3 2y1+3y2 5 y1y20y1+y2 2 3y1 +y2 3 C=(2,3,5,2,3)b=(4,3)T1 1 2 1 3 A=2-1 3 1 1Y AC确定约确定约束条件束条件 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*=0YX*=14/5x2*+8/5x3*+2/5x4*=0所以所以x2*=x3*=x4*=0又因又因Y*X=4/5x1+3/5x2=0所以所以x1=x2=028284.3 4.3 对偶问题的基本性质对偶问题的基本性质运筹学基础运筹学基础设设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*=0YX*=14/5x2*+8/5x3*+2/5x4*=0所以所以x2*=x3*=x4*=0又因又因Y*X=4/5x1+3/5x2=0所以所以x1=x2=0因为因为所以所以 x1*+x2*+2x3*+x4*+3x5*+x1=4 2x1*x2*+3x3*+x4*+x5*+x2=3 x1*+3x5*=4 2x1*+x5*=3x1*=1，x5*=1因此，原问题最优解为因此，原问题最优解为 X*=(1，0，0，0，1)T，*=5 。运筹学基础运筹学基础2929第二章第二章 线性规划线性规划q 对偶问题的提出对偶问题的提出q 原问题与对偶问题的关系原问题与对偶问题的关系q 对偶问题的基本性质对偶问题的基本性质q 对偶单纯形法对偶单纯形法q 灵敏度分析灵敏度分析30304.4 4.4 对偶单纯形法对偶单纯形法运筹学基础运筹学基础1 对偶单纯形法与单纯形法的区别对偶单纯形法与单纯形法的区别1.1 对偶单纯形法的思路对偶单纯形法的思路原理：原理：由性质由性质7可知：在单纯形表中进行迭代时，在可知：在单纯形表中进行迭代时，在b列中得到列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。通过逐步迭代，当在检验数行得到对偶问题的解也是基可解。通过逐步迭代，当在检验数行得到对偶问题的解也是基可行解时，根据性质行解时，根据性质4，5可知，已得到最优解。即原问题与对偶可知，已得到最优解。即原问题与对偶问题都是最优解。问题都是最优解。思路：思路：在进行迭代时，保持对偶问题的解是基可行解，即在进行迭代时，保持对偶问题的解是基可行解，即cjCBB-1pj0，而原问题通过逐步迭代，达到基可行解，这样就得，而原问题通过逐步迭代，达到基可行解，这样就得到最优解。到最优解。31314.4 4.4 对偶单纯形法对偶单纯形法运筹学基础运筹学基础1.2 对偶单纯形法与单纯形法的区别对偶单纯形法与单纯形法的区别单纯形法：单纯形法：在迭代中，保持在迭代中，保持b列中得到的是原问题的基可行解，列中得到的是原问题的基可行解，逐步得到对偶问题的基可行解。逐步得到对偶问题的基可行解。对偶单纯形法：对偶单纯形法：在逐步迭代中在逐步迭代中，保持检验数行，保持检验数行 cjCBB-1pj 0，即保持对偶问题的解是基可行解。通过迭代得到原问题的基，即保持对偶问题的解是基可行解。通过迭代得到原问题的基可行解。可行解。说明：说明：对偶单纯法是运用对偶原理求解原问题的一种方法，而对偶单纯法是运用对偶原理求解原问题的一种方法，而不是求解对偶问题的单纯法。不是求解对偶问题的单纯法。2 对偶单纯形法求解步骤对偶单纯形法求解步骤2.1 对偶可行的基解：对偶可行的基解：设设X(0)是原问题的基解，其对应的基为是原问题的基解，其对应的基为B，记，记Y=CBB-1，若，若Y是对偶问题的基可行解。即是对偶问题的基可行解。即C CBB-1A 0，则称，则称X(0)是原问题的对偶可行的基解。是原问题的对偶可行的基解。3232运筹学基础运筹学基础2.2 对偶单纯形法的计算步骤对偶单纯形法的计算步骤列出初始单纯形表列出初始单纯形表最优性检验最优性检验 根据线性规划问题，确定一个对偶可行根据线性规划问题，确定一个对偶可行的基解，列出初始单纯形表。的基解，列出初始单纯形表。检查检查b列的数，若都为非负，则已得到最优解。列的数，若都为非负，则已得到最优解。停止计算。若停止计算。若b列的数中，还有分量为负数，则进行下一步计列的数中，还有分量为负数，则进行下一步计算。算。确定换出变量确定换出变量 按按min(B-1b)i|(B-1b)i0，则无可行解，停止计算。，则无可行解，停止计算。如果如果 有有alj 0(j=1,2,n),则计算则计算 ck zkmincj zj alj|alj 0时，时，br bi/air 当当 air 0 br min bi/air|air 0时，时，cr j /arj 当当 arj 0 cr min j /arj|arj 0，则原最优基不再是最优基，此时在原问题的最，则原最优基不再是最优基，此时在原问题的最终表的基础上，换上改变后的第终表的基础上，换上改变后的第j列数据列数据B-1 Pj和和j，把，把 xj作为换入变量，用单纯形法继续迭代。作为换入变量，用单纯形法继续迭代。基基向向量量Pj变变为为Pj。此此时时原原最最优优解解的的可可行行性性和和最最优优性性都都遭遭到到破坏，一般不修改原来的最终表，而是重新计算。破坏，一般不修改原来的最终表，而是重新计算。