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

对偶单纯形法是求解对偶规划的一种方法 对偶单纯形法 利用对偶理论得到的一个求解线性规划问题的方法 2 3对偶单纯形法 1 单纯形法 原始单纯形法 的两个条件 1 问题为标准型 2 有初始基本可行解 用单纯形法求解 2 对偶单纯形法的优点 1 不需要人工变量 2 当变量多于约束时 用对偶单纯形法可减少迭代次数 3 在灵敏度分析中 有时需要用对偶单纯形法处理简化 3 B可逆 原始单纯形法的基本思路 4 关于可行基B的典则形式 检验数 5 初始单纯形表 原始单纯形法的迭代过程 6 对偶单纯形法的基本思路 作对偶单纯形表 7 基B的典则形式 不可行 检验行 0 分析 若X3或X4所在的行的aij均非负 则问题一定无可行解 否则 做换基迭代 8 1 确定出基变量 设br min bi bi 0 则取br所在行的基变量为出基变量 即取X4为出基变量 2 确定入基变量 原则 保持检验行系数 0 2 300 1 30Z 2 5 301 1 30 1 4 310 1 302 5 3002 31 1 000 3 5 2 5Z 12 5 001 1 10 0101 54 56 5 100 2 5 3 53 5 9 10 对偶单纯形法步骤 1 找出一个初始对偶可行解 把原问题写成该基的典则形式时 目标函数的系数均 0 2 判断 1 若B 1b 0 则得到最优解 结束 则问题无可行解 3 换基迭代 1 确定出基变量 2 确定入基变量 即找出一个基B 否则转下一步 11 不是典则形式 12 注意 对偶单纯形法仅限于初始基B对应的典则形式中目标函数的系数 检验数 均 0的情形 可用对偶单纯形法 B的典则形式 13 为什么叫对偶单纯形法 14 设B为可行基 原始单纯形法的基本思路 15 设B为可行基 原始单纯形法的迭代过程 16 对偶单纯形法的基本思路 17 如何用 18 求解线性规划问题的方法与步骤 1 把原问题化为标准型 2 找初始基 转第3步 转第4步 3 把问题写成关于基B的典则形式 用单纯形法 对偶单纯形法 转第4步 4 增加人工变量 用大M法或两阶段法求解 19 对应B1的基本解 可用对偶单纯形法求解 检验数全部 0 不可行 对应B2的基本解 用单纯形法求解 可行 20 对应B的基本解 存在检验数 0 不可行 单纯形法 对偶单纯形法 21 大M法 两阶段法 单纯形法 单纯形法 22 作业 23