熊伟编运筹学Ch2对偶理论.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * XB x1 x2 x3 x4 x5 x6 x7 b x3 0 5/7 1 1/7 3/7 0 0 2 x1 1 2/7 0 －1/7 4/7 0 0 1 x6 0 －2 0 0 －1 1 0 1 x7 0 －13/7 0 [－11/7] 2/7 0 1 －2 λj 0 －31/7 0 －2/7 －20/7 0 0 x3 0 6/11 1 0 5/11 0 1/11 20/11 x1 1 5/11 0 0 6/11 0 －1/11 13/11 x6 0 －2 0 0 －1 1 0 1 x4 0 13/11 0 1 －2/11 0 －7/11 14/11 λj 0 －45/11 0 0 －32/11 0 －2/11 表2－14 最优解 2.4 灵敏度分析 Sensitivity Analysis * （7）将原最优解代入约束 的左边有 5×1－2×2=110，满足新约束，故最优解不变。 上述cj及bi的最大允许变化范围是假定其它参数不变的前提下，单个参数的变化范围，当几个参数同时在各自范围内变化时，最优解或最优基有可能改变。 2.4 灵敏度分析 Sensitivity Analysis 灵敏度分析的关键在于线性规划某些参数或条件发生变化时，需要判断最优表中哪些数据发生了变化，如何求这些数据，如果不是最优解再用什么方法计算等问题．前两个问题可以直接用§1.5的矩阵公式判断和计算．将这些问题简要综合在表2-15中． * 表2-15 参数或条件变化 最优表可能发生变化 可行与最优 单纯形法 基变量系数ci 所有非基变量的检验数 可行 若非最优，用普通单纯形法 非基变量系数cj 只有xj的检验数变化 可行 若非最优，用普通单纯形法 bi XB 对偶问题可行 若不可行，用对偶单纯形法 基变量系数aij 基、基变量、检验数等 视检验数和基本解来确定 非基变量系数aij 非基变量系数及xj的检验 可行 若非最优，用普通单纯形法 综合变化，参数、增减变量与约束等 用§1.5介绍的5个计算公式判断变化情况 若原问题与对偶问题都不可行，用人工变量法 2.4 灵敏度分析 Sensitivity Analysis * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 【例2.10】用对偶单纯形法求解 【解】取x3、x4为初始基变量，用对偶单纯形法迭代如表2-8所示。 表2－8 XB x1 x2 x 3 x 4 b 表 （1） x 3 x 4 2 －1 [－1] 2 1 0 0 1 －2→ －2 λj －7 －3↑ 0 0 ? 表 （2） x 2 x 4 －2 3 1 0 －1 2 0 1 2 －6 λj －13 0 －3 0 ? 第二张表中x 4=－60且第二行的系数全部大于等于零，说明 原问题无可行解。 2.3 对偶单纯形法 Dual Simplex Method * 例2.10可用性质2.6及性质2.2来说明，表（2）的第2行对应于对偶问题的第2列（相差一个负号），检验数行对应于对偶问题的常数项（相差一个负号），比值 对应于对偶问题的比值 失效，也说明 即对偶问题具有无界解，由性质2.2知原问题无可行解． 2.3 对偶单纯形法 Dual Simplex Method * 本节利用对偶性质6：原问题的检验数与对偶问题的基本解的对应关系，介绍了一种特殊线性规划的求解方法—对偶单纯形法。 1.对偶单纯形法的应用条件； 2.出基与进基的顺序； 3.如何求最小比值； 4.最优解、无可行解的判断。 作业：教材P62 T6 2.3 对偶单纯形法 Dual Simplex Method 下一节：灵敏度分析与参数分析 2.4 灵敏度与参数分析 Sensitivity and Parametric Analysis * 线性规划的灵敏度分析也称为敏感性分析，它是研究和分析参数（cj，bi，aij）的波动对最优解的影响程度，主要研究下面两个方面： （1）参数在什么范围内变化时，原最优解或最优基不变； （2）当参数已经变化时，最优解或最优基有