对偶单纯形法(经典运筹学)解析.ppt

对偶单纯形法是求解对偶规划的一种方法 原始单纯形法的基本思路： 对偶单纯形法步骤： 注意：对偶单纯形法仅限于初始基B对应 的典则形式中目标函数的系数（检 验数）均≤0的情形。 * × 对偶单纯形法：利用对偶理论得到的一个 求解线性规划问题的方法 单纯形法（原始单纯形法）的两个条件： 1、问题为标准型 2、有初始基本可行解 用单纯形法求解 对偶单纯形法的优点： 1、不需要人工变量； 2、当变量多于约束时，用对偶单纯形法可减少迭代次数； 3、在灵敏度分析中，有时需要用对偶单纯形法处理简化。 B 可逆 关于可行基B的典则形式 检验数 B-1b E B-1N XB Z- CBB-1b 0 CN- CBB-1N 检验行 常数项 XB XN 初始单纯形表： 原始单纯形法的迭代过程： 对偶单纯形法的基本思路： B-1b E B-1N XB Z- CBB-1b 0 CN- CBB-1N 检验行 常数项 XB XN 作对偶单纯形表： 基B的典则形式 3 1 0 0 2 1 X5 -6 0 1 0 -3 -4 X4 -3 0 0 1 -1 -3 X3 Z 0 0 0 -1 -2 检 X5 X4 X3 X2 X1 不可行 检验行≤0 分析： 若X3或X4所在的行的aij均非负， 则问题一定无可行解 否则，做换基迭代 3 1 0 0 2 1 X5 -6 0 1 0 -3 -4 X4 -3 0 0 1 -1 -3 X3 Z 0 0 0 -1 -2 检 X5 X4 X3 X2 X1 1、确定出基变量： 设br =min{bi | bi 0} 则取br所在行的基变量 为出基变量 即取X4为出基变量 2、确定入基变量： 原则： 保持检验行系数≤0 X5 X2 X3 检 X5 X4 X3 X2 X1 X1 X2 X3 检 X5 X4 X3 X2 X1 -2/3 0 0 -1/3 0 Z+2 -5/3 0 1 -1/3 0 -1 4/3 1 0 -1/3 0 2 -5/3 0 0 2/3 1 -1 0 0 0 -3/5 -2/5 Z+12/5 0 0 1 -1 -1 0 0 1 0 1/5 4/5 6/5 1 0 0 -2/5 -3/5 3/5 1、找出一个初始对偶可行解。 把原问题写成该基的典则形式时，目标函数的系数均≤0 2、判断： （1）若B-1b≥0，则得到最优解 结束 （2）若B-1b≥0， 则问题无可行解。 3、换基迭代： （1）确定出基变量： （2）确定入基变量 即找出一个基B， 否则转下一步 不是典则形式 -9 1 0 -6 -4 0 X5 5 0 1 1 2 0 X4 5 0 0 1 1 1 X1 Z 0 0 0 1 2 检 X5 X4 X3 X2 X1 Z-10 0 0 -2 -1 0 X2 X4 X1 检 X5 X4 X3 X2 X1 9/4 -1/4 0 3/2 1 0 1/2 1/2 1 -2 0 0 11/4 1/4 0 -1/2 0 1 Z-31/4 -1/4 0 -1/2 0 0 可用对偶单纯形法 B的典则形式 B-1b XB Z- CBB-1b 检验行 解 X 设B为可行基 B-1b E B-1N XB Z- CBB-1b 0 CN- CBB-1N 检验行 解 XB XN 原始单纯形法的基本思路： B-1b XB Z- CBB-1b 检验行 解 X 设B为可行基 原始单纯形法的迭代过程： 对偶单纯形法的基本思路： 如何用？ 求解线性规划问题的方法与步骤： 1、 把原问题化为标准型 2、找初始基 ，转第3步 ，转第4步 3、把问题写成关于基B的典则形式 ，用单纯形法 ，对偶单纯形法 ，转第4步 4、增加人工变量，用大M法或两阶段法求解 对应B1的基本解： 可用对偶单纯形法求解 检验数全部≤0 不可行 对应B2的基本解 用单纯形法求解 可行 对应B的基本解： 存在检验数0 不可行 单纯形法× 对偶单纯形法？ × * * * 对偶规划本身是一个线性规划，用单纯形法可以求得他的解