第五节 对偶单纯形法.ppt

第五节 对偶单纯形法 一、对偶单纯形法基本思想：基本思想是保持对偶问题为可行解(此时一般原问题为非可行解)的基础上，通过迭代，减小目标函数，当原问题也达到可行解时，即得到了目标函数的最优值。 ◆说明：对偶单纯形法应用前提: ① 单纯形表的检验数行全部非正（对偶可行）； ② 变量取值可有负数（非可行解）。 * 2010年3月 管理工程学院 《运筹学》 * * ◆对偶单纯型法 … a1,m+1 ? ar,m+1 ? am,m+1 xm+1 … … … … … … 0 ? 1 ? 0 xr … … … … 0 … 0 σj=cj-zj a1n ? a2n ? amn … … … a1s ? a2s ? ams … … … 0 ? 0 ? 1 ? ? 1 ? 0 ? 0 b1 ? br ? bm x1 ? xr ? xm c1 ? cr ? cm xn … xs … xm … x1 b 基 cB 表2-5 二、对偶单纯形法的算法步骤。 ◆表2-5中必须有cj-zj≤0(j=1, …,n)但 (i=1, …,m) 的值不一定为正。当对i=1, …,m 均有 表中原问题和对偶问题均为最优解。 ≥0， ◆对偶单纯形法的算法步骤如下： 1.确定换出基变量。存在 时，令 其对应变量xr为换出基的变量。 2.确定换入基变量。 (2.14) 称ars为主元素， xs为换入基的变量。 3.用换入替换换出变量，得到一个新的基。 再检查是否所有的 (i=1, …,m) 如果是，找到了问题的最优解； 否则，回到第1步再重复计算。 ◆说明： 当 ，且所有j=1, …,n，有arj≥0时， 原问题无可行解，对偶问题的目标函数值无界。 例5：用对偶单纯形法求解线性规划问题： 解：先将问题改写为： * 2010年3月 管理工程学院 《运筹学》 *