[第四讲线性规划对偶理论与方法.pptVIP

湖州师范学院 规范形式原问题与对偶问题变换规则 对偶问题的经济解释---影子价格 对偶问题的经济解释---影子价格 对偶问题的经济解释---影子价格 第四讲 线性规划对偶理论与方法 【例】 已知线性规划 的最优解是： 求对偶问题的最优解。 【解】对偶问题是 因为X1≠0，X2≠0，所以对偶问题的第一、二个约束的松弛变量等于零，即 解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为Y=（1，1），最优值w=26。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 第四讲 线性规划对偶理论与方法 三、对偶问题的性质 练习题1 例： 已知线性规划问题 min w=2x1+3x2+5x3+2x4+3x5 x1+x2+2x3+x4+3x5≥4 2x1-x2+3x3+x4+x5≥3 xj≥0，j=1，2，…，5 已知其对偶问题的最优解为y1*=4/5，y2*=3/5；z=5。试用对偶理论找出原问题的最优解 。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 第四讲 线性规划对偶理论与方法 三、对偶问题的性质 练习题 2 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 第四讲 线性规划对偶理论与方法 三、对偶问题的性质 【性质7】互补对偶性　　LP(max)的检验数的相反数对应于DP(min)的一组基本解. 其中第j个决策变量xj的检验数的相反数对应于（DP）中第j个松弛变量 的解，第i个松弛变量 的检验数的相反数对应于第i个对偶变量yi的解。反之，（DP）的检验数（注意：不乘负号）对应于（LP）的一组基本解。 互补的两个基解所对应的目标值相等。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 第四讲 线性规划对偶理论与方法 三、对偶问题的性质 【性质7】互补对偶性　　 设原问题是 max z=CX; AX+XS=b; X,XS≥0 它的对偶问题是 min w=Yb; YA ? YS=C; Y,YS≥0 则原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系如表。 YS1是对应原问题中基变量XB的剩余变量， YS2是对应原问题中非基变量XN的剩余变量。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 第四讲 线性规划对偶理论与方法 证: 设B是原问题的一个可行基，于是A=(B,N)；原问题可改写为： max z=CBXB+CNXN BXB+NXN+XS=b XB，XN，XS≥0 相应地对偶问题可表示为： min w=Yb YB ? YS1=CB YN? YS2=CN Y，YS1,YS2≥0 这里YS=(YS1，YS2)。 当求得原问题的一个解：XB=B-1b,其相应的检验数为 CN ?CBB-1N 与 ?CBB-1 现分析这些检验数与对偶问题的解之间的关系：令Y=CBB-1,将它代入得： YS1=0, ?YS2=CN? CBB-1N。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 第四讲 线性规划对偶理论与方法 【练习题】 线性规划 （1）用单纯形法求最优解； （2）写出每步迭代对应对