运筹学对偶单纯形法ppt课件.ppt

第六节对偶单纯形法 1 本节内容安排 对偶单纯形法的求解思路对偶单纯形法的求解步骤 2 对偶单纯形法是根据对偶原理和单纯形法的原理而设计出来求解原LP的一种方法 采用的技术是在原问题的单纯形表格上进行对偶处理 注意 对偶单纯形法不是求解对偶问题的单纯形法 一对偶单纯形法的求解思路 一 什么是对偶单纯形法 3 1单纯形法中原问题 max 的最优解满足的条件 1 是基本解 2 可行解 XB B 1b 0 3 检验数C CBB 1A 0 CBB 1 0即YA C Y 0即对偶解可行 二 普通单纯形法 4 2普通单纯形法的求解思路 从满足 1 2 的一个初始基本可行解出发 此时原LP问题中 b列保持 0 对偶的解一般为非可行基解 通过逐步迭代 增大原目标函数值 每一步迭代 都得到一个基本可行解 并且逐步迭代实现检验数行 0 对偶解可行 迭代到 3 得到满足 即所有检验数 0 此时 原问题的基可行解达到最优时 对偶的基解由不可行达到可行 得到的这个基可行解也是对偶问题的最优解 5 3普通单纯型法的求解过程 对原问题的一个基可行解 判别是否所有检验数非正cj zj 0 j 1 n 若是 又基变量中无非零人工变量 即找到问题最优解 基变量中含有非零人工变量 则无最优解 若否 再迭代 找出相邻的目标函数值更大的基可行解 并继续判别 只要最优解存在 就一直迭代下去 直到找出最优解为止 6 1对偶单纯形法求解思路 换个角度考虑LP求解过程从满足 1 3 的一个非可行基解 检验数行保持 0 出发 此时对偶问题的解一般为可行解 通过逐步迭代直至 2 得到满足 即直到实现到b列所有的值 0 原问题的解在迭代过程中从非可行解变成可行解 最终达到最优解 此时 对偶问题也达到最优解 单纯形法中原问题的最优解满足的条件 1 是基本解 2 可行解 XB B 1b 0 3 检验数C CBB 1A 0 CBB 1 0即YA C Y 0即对偶解可行 三 对偶单纯形法 7 普通单纯形法 对偶单纯形法 前提是原问题可行 优化条件 两种方法都从原问题的基解出发 前提是对偶可行 优化条件 2两种方法的联系 YA C Y 0 8 原问题基可行解最优解判断 对偶问题的可行解 对偶问题最优解判断 对偶单纯形法基本思路 普通单纯形法基本思路 9 3对偶单纯形法的使用条件 原问题的初始基解的检验数全部 0 b列至少一个元素 0 4实施对偶单纯形法的基本原则 在保持对偶可行的前提下进行基变换 每一次迭代过程中取出基变量中的一个负分量作为换出变量去替换某个非基变量 作为换入变量 使原始问题的非可行解向可行解靠近 10 第一步 构造初始单位阵 确定原问题 max 的初始基B 使所有检验数Cj Zj j Cj CBB 1Pj 0 即Y CBB 1 b列的值 是对偶可行解 建立初始单纯形表 第二步 可行性检验 检验b列和 j行 即检查基变量的取值 若bi 0 XB B 1b 0 j 0 则原问题得到最优解 计算停 若bi 0 j 0 则用对偶单纯形法进行换基迭代 二对偶单纯形法的步骤 11 第三步先确定换出变量解答列 b列 中的负元素对应的基变量出基 相应的行为主元行 一般选最小的负元素出基 即若min B 1b i B 1b I 0 B 1b l则选取xl为换出变量 检验第l行中非基变量xj的系数 lj 若所有的 lj 0 则LP问题无可行解 下面进行说明 此时计算结束 否则转下步 12 当bl 0 而对所有j 1 n 有alj 0 则原问题无可行解 证明 xl al m 1xm 1 al nxn bl因alj 0 j m 1 n 又bl 0 故有xl 0 即不可能存在xj 0 j 1 n 的解 故原问题无可行解 此时对偶问题的目标函数值无界 13 若有 Min cj zj lj lj 0 xj为非基变量 ck zk lk则确定xk为换入变量 相应的列为主元列 标出主元素 lk 应用矩阵的初等行变换得到新的单纯形表 第四步 若对于bl 0 且有alj 0 则确定换入变量 应用最小比值原则目的 是在保持下一个对偶问题的基解可行的前提下 减少原始问题的不可行性 下面进行说明 根据最小比值原则 14 alk为主元素xk为进基变量 设下一个表中的检验数为 cj zj 则 15 1 对alj 0 因cj zj 0 故 又因主元素alk 0 故有 所以 cj zj 0 2 对alj 0 因 故有 cj zj 0 所以 cj zj 0 j 1 n 则有 16 第五步 用换入变量替换换出变量 得到一个新的基 对新的基再检查是否所有如果是 得原问题的最优解 如果否 回到第一步再重复计算 直到检验数行非正 基列非负 得到最终表 17 例6应用对偶单纯型法求解下面的线性规划问题 18 cj zj min j lj lj 0 x5换出变量 x1换入变量 min j lj lj 0 x2换入变量 8 5 2 x4换出变量 19 bi 0 j 0得到最优解为 X 11 5 2 5 0 0 0 T 对偶问题最优解为 20 例 用对偶单纯形法求解下面线性规划 解 构造对偶单纯形表进行迭代 21 从最后的表可以看到 B 1b列元素中有 2 0 并且 2所在行各元素皆非负 因此 原问题没有可行解 22 原问题可以从非可行解开始 即初始解可以是非可行解 在构造初始单位阵时 不需要加人工变量 简化计算 对偶单纯形法的特点 灵敏度分析和整数规划常借助于对偶单纯形法分析 使问题处理简单 变量多 约束条件少的问题 在迭代过程中计算工作量小 因此 可以把变量少 约束条件多的LP问题转化成变量多 约束条件少的对偶问题 再用对偶单纯形法求解 23 对偶单纯形法的局限性 很难找到初始可行基 很少单独使用 初始单纯形表的检验数行很难满足小于或等于零的要求 即满足检验数行对应的对偶问题的解是可行解 24 对于原问题为最小化时 选取换出变量的原则不变 选取换入变量时作相应改变 j 0min j lj lj 0 xj为非基变量 k lk 注意 若xl为换出变量 所有 lj 0 则原问题无可行解 25 初始可行基 例 用对偶单纯形法求解线性规划问题 对偶问题的初始可行基 26 min j lj lj 0 4 5 y2换入变量 27 28 最优解 29 对偶单纯形法与原始单纯形法内在的对应关系 30 单纯形法和对偶单纯形法步骤 31 例用对偶单纯形法求解 minz 2x1 4x2 6x3s t 2x1 x2 x3 10 x1 2x2 2x3 122x2 x3 4x1 x2 x3 0 解 将问题化为 maxz 2x1 4x2 6x3s t 2x1 x2 x3 x4 10 x1 2x2 2x3 x5 12 2x2 x3 x6 4xj 0 j 1 2 6 2 1 1 2 1 2 1 2 0 0 5 0 x1 2 5 2 3 2 1 2 1 0 7 0 5 1 5 0 0 10