2015最优化方法线性规划.ppt

min Ζ=CBXB+CNXN s.t. BXB+NXN=b XB,XN≥0 将基变量用非基变量表示 XB=B-1b-B-1NXN代入目标函数，得 Ζ=CB(B-1b-B-1NXN)+CNXN =CBB-1b+(CN-CBB-1N)XN XB=B-1b,XN=0为一基本可行解。 1.最优解判别定理： 若 X(0)=(B-1b,0)T为对应于基B的基本可行解，且CN-CBB-1N ≥ 0,则X(0)为最优解。 [证]对一切可行解X CX=CB B-1b+（CN-CBB-1N）XN ≥ CB B-1b 所以，X(0)=(B-1b,0)T为最优解。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 若把上面的矩阵形式表示为方程组，则 则上面的判别定理表示为：若X(0)=(b1?,b2 ?,…,bm ?,0,…0)T 为对应于基B的基本可行解，且对于一切j=m+1,2,…,n,?j?0，则X(0)为最优解。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2.无穷多最优解判别定理： 若X(0)=(b1’,b2’,…,bm’,0,…0)T为一基本可行解，对于一切j=m+1, …,n,有?j≤0, 又存在某个非基变量xm+k的检验数?m+k=0,则线性规划问题有无穷多最优解。 [证]只需将非基变量xm+k换入基变量中，找到一个新的基本可行解X（1），因?m+k=0，知z=z0，故X（1）也是最优解，由2.2定理3可知， X(0)、X（1）连线上所有点都是最优解。 3.无界解判别定理： 若X(0)=(b1’,b2’,…,bm’,0,…0)T为一基可行解，且有一个?m+k 0,并且对i=1,2,…,m,有ai’,m+k≤0, 那么该线性 规划问题没有有限最优解。 [证]取xm+k为进基变量，令xm+k增加，并取其余非基变量为零，则得 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 令xm+k=??0，显然，这时目标函数值为 z=z0+??m+k→+? （?→+? ） 故没有有限最优解。 4 基变换 1.换入变量的确定 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 一般取?j0中的最大者 max(?j0)=?k 对应的xk为换入变量。 2.换出变量的确定 5 迭代（旋转运算） Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. §4.单纯形法的计算步骤 基变量 b x1 x2… xm xm+1 … xn x1 b1 1 0 … 0 a1m+1 …a1n x2 b2 0 1 … 0 a2m+1 …a2n ┆ ┆ ┆┆ ┆ ┆ ┆ xm bm 0 0 … 1 amm+1 …amn c1 c2… cm cm+1 …cn 基变量 b x1 x2 … xm xm+1 … xn x1 b1 1 0 … 0 a1m+1 … a1n x2 b2 0 1 … 0 a2m+1 … a2n ┆ ┆ ┆┆ ┆ ┆ ┆ xm bm 0 0 … 1 amm+1 …amn 0 0… 0 ?m+1 …?n 初始