最优化计算方法(工程优化)第5章详解.ppt

(ii) 如果存在 ，则取 对偶单纯形法 确定进基变量 则 的检验数是0，所以 是进基变量。 是主元。 (i) 如果所有的 ，则原问题没有可行解； 对偶单纯形法 找出 P 的一个对偶可行的基本解 基本解是否可行 （x ≥0） 保持对偶可行性的条件下，转移到 P 的另一个基本解 最优解 是 否 循 环 结束 确定离基变量和进基变量，从而确定主元，用主元消去法实现转移 应用前提：有一个基对应的基本解的检验数非正 例. 利用单纯形算法求解如下的线性规划问题 解： 先化成标准形式，引进松弛变量 得到原问题的一个基本解 两端同时乘以-1， 取x5, x6是基变量 它是对偶可行的。 是为了出现单位矩阵，可以从表格中直接计算检验数 xB x1 x2 x3 x4 x5 x6 x5 x6 -2 -3 -12 -8 -16 -12 0 0 x5 x4 -2 3/4 cB 0 0 0 12 -2 -1 -4 0 1 0 -2 -2 0 -4 0 1 -2 -1 -4 0 1 0 1/2 1/2 0 1 0 -1/4 -6 -2 -16 0 0 -3 c 12 8 16 12 0 0 6 4 -- 3 -- -- 3 2 4 -- -- -- x2 x4 -2 0 -8 0 -2 -3 8 12 2 1 4 0 -1 0 -1/2 0 -2 1 1/2 -1/4 4 -- 4 -- -- 12 2 -1/4 所有 ，因此达到最优解 xB x1 x2 x3 x4 x5 x6 cB c 12 8 16 12 0 0 2 1 4 0 -1 0 -1/2 0 -2 1 1/2 -1/4 x2 x4 8 12 2 -1/4 -2 0 -8 0 -2 -3 4 -- 4 -- -- 12 x2 x1 1 1/2 8 12 0 1 -4 4 1 -1 1 0 4 -2 -1 1/2 0 0 0 -4 -4 -2 最优值是12*(1/2)+8*1=14 对偶单纯形法 对偶单纯形法应注意的问题： 对偶单纯形