原问题对偶问题一对对偶问题

第三章线性规划的对偶理论•线性规划问题具有对偶性，即任何一个求极大值的线性规划问题，都有一个求极小值的线性规划问题与之对应，反之亦然．•原问题、对偶问题、一对对偶问题•对偶理论（DualityTheory）–[dju(:)’æliti]–研究对偶问题之间的关系及其解的性质•根据对偶理论，在解原问题的同时，也可以得到对偶问题的解，并且还可以提供影子价格等有价值的信息，在经济管理中有着广泛的应用．为什么研究对偶理论？–对偶问题可能比原问题容易求解–对偶问题还有很多理论和实际应用的意义§1对偶问题的一般概念§2对偶问题的基本性质§3对偶问题的解§4对偶问题的经济解释——影子价格§5对偶单纯形法§6原始——对偶单纯形法§1对偶问题的一般概念1.对偶问题的提出2.对偶问题的形式1.1对偶问题的提出•资源的合理利用问题，即充分利用资源生产两种产品•大规模定制生产时代，充分利用资源生成所需的产品•对外提供加工服务，收取加工费•存在一个矛盾–自己要赚钱，定价越高越好–定价太高，别人不找你•折中——保证不亏的前提下，对方的支出最少例1甲乙限额材料2332工时4523利润（元/件）1020235432322010max212121xxxxxxZ问题•假设不是安排生产，而是出售材料，出租工时，问如何定价，可使工厂获利不低于安排生产所获得的利益，且又能使这些定价具有竞争力解决•设出售材料的定价为每单位y1元•出租工时的定价为每工时y2元205310422332min212121yyyyyyW235432322010max212121xxxxxxZ205310422332min212121yyyyyyW1.2对偶问题的形式1.对称型对偶问题2.非对称型对偶问题3.混合型对偶问题1.对称型对偶问题•定义1矩阵形式•原问题•对偶问题增加内容对偶规则1.给每个原始约束条件定义一个非负对偶变量yi(i=1,2,…,m);2.使原问题的目标函数系数cj变为其对偶问题约束条件的右端常数；3.使原问题约束条件的右端常数bi变为其对偶问题目标函数的系数；4.将原问题约束条件的系数矩阵转置，得到其对偶问题约束条件的系数矩阵；5.改变约束条件不等号的方向，即将“=”改为“=”；6.原问题“max”型，对偶问题为“min”型．例32.非对称型对偶问题例4对偶规则原问题第k个约束为等式，对偶问题第k个变量是自由变量。原问题第k个变量是自由变量，则对偶问题第k个约束为等式约束。3.混合型对偶问题对偶约束•另外，我们把约束条件分为行约束（变量的线性组合的等式或不等式约束）和变量的符号约束两部分，而以原问题的行约束与对偶问题的变量一一对应，原问题的变量与对偶问题的行约束一一对应，并且将对应的一对约束称为一对对偶约束．例5例3用矩阵理论讨论对偶问题设原问题：01maxXbAXCXZ可用另一形式：0SSX,XbIXAXCXZmax00NBCCbINBXBXNXSbBCBCNBCCbBBNBIBBBN1111110XBXNXS4003020111BCNBCCBBCCBSBNNBBB表示线性规划问题已得到最优解.令,BCYB1则由(4)有0Y由(2)和(3),有,ABCCB01故有CYA因为,1YbbBCZB而Y的上限无限大,所以只存在最小值.由上讨论,可得另一个线性规划问题:05minYCYAYbW称为原线性规划问题的对偶规划问题。0X,bAXCXZmax原问题PrimeProblem对偶问题DualProblem原问题与对偶问题的对应关系原问题求极小------ZMAXZmin原问题约束方程有“≥”------两边同乘（-1），“≤”原问题约束方程有“=”------对偶问题？§2对偶问题的基本性质•对称性•弱对偶性•无界性•最优性•强对偶性•互补松弛性•解的对应性产品A，B产量X1，X2，Z为利润例1、3X1+X2+X3=483X1+4X2+X4=120X1…X40maxZ=5X1+6X23X1+X2483X1+4X2120X1,X20机器台时劳动工时X=(8,24)TZ=1845600X1X2X3X4XB056000X34831100X41203(4)011801/200-3/20X318(9/4)01-1/46X2303/4101/418400-2/9-13/95X18104/9-1/96X22401-1/31/33y1+3y25y1+4y26minW=48y1+120y23y1+3y2-y3+y5=5y1+4y2-y4+y6=6minW=48y1+120y2+My5+My64812000MMy1y2y3y4y5y6yB11M48-4M120-7MMM00My5533-1010My66140-101yB180+1/2M18-9/4M0M30-3/4M0-30+7/4MMy51/29/40-13/41-3/4120y23/21/410-1/401/4yB18400824M-8M-2448y12/910-4/91/34/9-1/3120y213/9011/9-1/3-1/91/3y=(2/9,13/9),Z=184观察结论:①一对对偶问题都有最优解，且目标函数值相等。②最优表中有两个问题的最优解。对称性•定理1（对称性定理）•对偶问题的对偶是原问题。弱对偶性•定理2（弱对偶性）bYXCDP则存在的可行解，是的可行解，是若YX证明推论1•最大化问题的任一个可行解的目标函数值都是其对偶最小化问题目标函数的下界；•最小化问题的任一个可行解的目标函数值都是其对偶最大化问题目标函数的上界。无界性•推论2•若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。•逆命题不成立。•在一对对偶问题P和D中，当其中一个问题无可行解时，则另一个问题或者目标函数无界，或者无可行解。推论3•在一对对偶问题P和D中，若一个可行，而另一个不可行，则该可行的问题无界。例140104010maxminZWbYXCbYWXCZ例2例3最优性•定理3（最优性判别定理）是最优解时，当的可行解，是的可行解，是设YXbYCXDYPX,证明•定理1——对称性定理•定理2——弱对偶性定理•定理3——最优性判别定理•定理4——主对偶定理•定理5——互补松弛定理强对偶性•定理4（主对偶理论）•若一对对偶问题都有可行解，则它们都有最优解，且目标函数的最优值必相等。证明DPDYDX设根据弱对偶性定理，有bYXC又有上界为,maxCXP所以，P有最优解又有下界为,minYbD所以，D有最优解为最优基的最优解，为设B*PX0)3(Z)2()1(1**1*bBCCXbBXB最优值得引入,SX***0,maxSSSSXXXXXbIXAXOXCXZ111111BCNBCCObBCZBNBIbBXCXXXbXCOCCCBBNBBBSNBBBNB00011BCNBCCBBN0011BCABCCBB1*BCYB令0YCYADDY***1*CXZbBCbYB＝根据最优性判别定理，Y*也是最优解推论4•原问题有最优解，那末对偶问题也有最优解，且目标函数值相等。一对对偶问题的关系•两个问题都有可行解，从而都有最优解•一个问题为无界解，另一个问题必无可行解•两个问题都无可行解互补松弛性•定理5（互补松弛定理）•设X*和Y*分别是P和D的可行解，则它们分别是最优解的充要条件是0)(0)(****XCAYAXbY为最优解**YX0)(0)(****XCAYAXbYCAYAXb**和关键在于凑出PDX*0,**XbAX**,0AXbXXbXAXSSS且DDY*0,**YCAYCAYYYCYAYSSS**,0且bYXYAXYS********CXXYAXYSbYCXYX****,根据主对偶定理为最优解0**XYXYSS0**XYXYSS00**XYXYSS0)(0)(****XCAYAXbY*AXbXSCAYYS*互补松弛条件0)(0)(****XCAYAXbY互补松弛条件互补松弛关系（松紧关系）•若原问题最优解第i个约束方程为严格的不等式，则对偶问题最优解中第i个对偶变量取值必为0松约束与紧约束•把某一可行点处的严格不等式约束（包括对变量的非负约束）称为松约束–不起作用约束•把严格等式约束称为紧约束–起作用约束结论•即对于最优解X*和Y*而言，松约束的对偶约束是紧约束．•注意：是先松后紧！推论5•设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定是其对偶问题最优解的紧约束．松紧关系的实际意义•在计算上，若已知一个问题的最优解，则可利用互补松弛条件求另一个问题的最优解．w1wiwmwm+1wm+jwn+mx1xjxnxn+1xn+ixn+m对偶问题的变量对偶问题的松弛变量原始问题的变量原始问题的松弛变量xjwm+j=0wixn+i=0(i=1,2,…,m;j=1,2,…,n)在一对变量中，其中一个大于0，另一个一定等于0maxz=3x1+4x2-x3s.t.4x1+2x2+5x3≤38-x1+3x2-x3≥182x1-x2+3x3≤263x1+x2-2x3≥10x1,x2,x3≥0miny=38w1+18w2+26w3+10w4s.t.4w1-w2+2w3+3w4≥32w1+3w2-w3+w4≥45w1-w2+3w3-2w4≥-1w1≥0,w2≤0,w3≥0,w4≤0|－变量－|－松弛变量－|(x1,x2,x3,x4,x5,x6,x7)(0,19,0,0,39,45,9)(2,0,0,0,5,0,11)(w1,w2,w3,w4,w5,w6,w7)|－变量－|－松弛变量－|互补松弛关系+x4=38-x5=18+x6=26-x7=10x4,x5,x6,x7≥0-w5=3-w6=4-w7=-1,w5,w6,w7≥0原始问题对偶问题原始问题的每一个变量和对偶问题相应的松弛变量组成互补松弛对，每一对变量中至少有一个等于0。对偶问题的每一个变量和原始问题相应的松弛变量组成互补松弛对，每一对变量中至少有一个等于0。例4先松后紧！！！非对称对偶问题的互补松弛条件•设X*和Y*分别是一对非对称对偶问题的可行解，则它们分别是最优解的充要条件是下式成立0)(**XCAYWhy?对于非对称形式的对偶问题，因为此时Y*无正负限制，所以只有一个成立0)(0)(****XCAYAXbY混合型对偶问题•定理1－5成立例5结论•如果D易求，可以通过求D来讨论P•若D无界，则P无解•若求得D的最优解Y*，最优值为W*，则利用互补松弛条件可求得P的最优解X*，并且P的最优值为Z*=Y*b解的对应性0,maxSSXXbXAXCXZ0,minSSYYCYYAYbW推论•对于对称形式的原问题，若有最优解，则在其最优单纯形表中，松弛变量的检验数的负值即为对偶问题的一个最优解mnnnxxx,,,21),,,(21mnnn0,maxSSSXXbIXAXOXCXZ非基变量基变量XBXNXSCBXBB-1bBNIσjCBCNO基变量非基变量XBXNXSCBXBB-1bIB-1NB-1σjOCN-CBB-1N-CBB-1非基变量基变量XBXNXSCBXBB-1bBNIσjCBCNO0000011111YCYABCYBCABCCBCNBCCBBBBBN