最优化方法第二章单纯形法.pptVIP

第二讲 单纯形法 单纯形法的一般原理 表格单纯形法 借助人工变量求初始的基本可行解 单纯形表与线性规划问题的讨论 改进单纯形法 2.1 单纯形法的一般原理 1 确定初始的基本可行解 2 判断现行的基本可行解是否最优 3 基本可行解的改进 ——基变换 4 用初等变换求改进了的基本可行解——旋转变换 其步骤如下： 1 确定初始的基本可行解 线性规划问题基变换的矩阵表示 Linear Programming in MATLAB （2）检验　　　　　　　　　　 是否最优。 检验向量 　　　因为所有检验数均大于零， 　所以　　　　　　　　　　　　　是最优解， 2.2 表格单纯形法 　通过例１我们发现，在单纯形法的求解过程中，有下列重要指标： 每一个基本可行解的检验向量 根据检验向量可以确定所求得的基本可行解是否为最优解。如果不是最优又可以通过检验向量确定合适的换入变量。 每一个基本可行解所对应的目标函数值 通过目标函数值可以观察单纯形法的每次迭代是否能使目标函数值有效地减小，直至求得最优目标函数为止。 在单纯形法求解过程中，每一个基本可行解Ｘ都以某个经过初等行变换的约束方程组中的单位矩阵Ι为可行基。 当Ｂ=Ｉ时，Ｂ-1=Ｉ，易知： 可将这些重要结论的计算设计成如下一个简单的表格， 即单纯形表来完成： CB CN- CBN 0 CBb Z θ1 θ2 . . θm N I b1 b2 . . bm x1 x2 ? . xm c1 c2 . . cm x m+1 xm+2 ··· xn x1 x2 ··· xm b XB CB θ CN C 　例2、试利用单纯形表求例1中的最优解解： 　　 　　得初始的单纯形表： 　初始基本可行解　　　　　　　　　　，Z= 1， 1 2 2 1 0 8 x4 1 －3 0 － 4 0 0 1 Z 3 4 1 0 1 7 x5 －1 x1 x2 x3 x4 x5 b XB CB θ －5 － 2 － 3 1 －1 C x3换入变量，x4换出变量，２为主元进行旋转变换 基本可行解　　　　　　　　　 1/2 　 1 　 1 　 1/2 　 0 4 x3 －3 －1 4 0 2 0 －15 Z 5/2 3 0 -1/2 1 3 x5 －1 　 x1 　 x2 　 x3 　 x4 　 x5 b XB CB θ C 1 2 2 1 0 8 x4 1 －3 0 －4 0 0 1 Z 3 4 1 0 1 7 x5 －1 x1 x2 x3 x4 x5 b XB CB θ C 8/2 7/1 －5 － 2 － 3 1 －1 －5 － 2 － 3 1 －1 　　　　　　　　最优解 　　　　　　　　　最优值 x1换入变量，x5换出变量，５/２为主元进行旋转变换 4/1/2 1/2 　 1 　 1 　 1/2 　 0 4 x3 3 －1 4 0 2 0 －15 Z 3/5/2 5/2 3 0 -1/2 1 3 x5 －1 　　x1 　 x2 　 x3 　 x4 　 x5 b XB CB θ C 0 2/5 1 3/5 -1/5 17/5 x3 －3 0 26/5 0