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

原始问题 Max z=CTX s.t. AX ≤ b X ≥0 当原问题为求极小值时，对偶问题为求极大值。 原始问题中目标函数的系数变成对偶问题中约束条件的右端；原始问题中约束条件的右端变成对偶问题中目标函数的系数。 原始问题约束条件系数矩阵的转置对应对偶问题中约束条件的系数矩阵。 原始问题的约束条件个数决定对偶问题变量的个数；原始问题变量个数，决定对偶问题的约束个数。 原始问题的约束方程的匹配形式决定对偶问题变量的符号；原始问题决策变量的符号决定所对应对偶问题的约束方程的匹配形式。 －2/11 0 －32/11 0 0 －45/11 0 λj 14/11 －7/11 0 －2/11 1 0 13/11 0 x4 1 0 1 －1 0 0 －2 0 x6 13/11 －1/11 0 6/11 0 0 5/11 1 x1 20/11 1/11 0 5/11 0 1 6/11 0 x3 0 0 －20/7 －2/7 0 －31/7 0 λj －2 1 0 2/7 [－11/7] 0 －13/7 0 x7 1 0 1 －1 0 0 －2 0 x6 1 0 0 4/7 －1/7 0 2/7 1 x1 2 0 0 3/7 1/7 1 5/7 0 x3 b x7 x6 x5 x4 x3 x2 x1 XB 表2－14 最优解 2.4 灵敏度分析 Sensitivity Analysis （7）将原最优解代入约束 的左边有 5×1－2×2=110，满足新约束，故最优解不变。 上述cj及bi的最大允许变化范围是假定其它参数不变的前提下，单个参数的变化范围，当几个参数同时在各自范围内变化时，最优解或最优基有可能改变。 2.4 灵敏度分析 Sensitivity Analysis 灵敏度分析的关键在于线性规划某些参数或条件发生变化时，需要判断最优表中哪些数据发生了变化，如何求这些数据，如果不是最优解再用什么方法计算等问题．前两个问题可以直接用§1.5的矩阵公式判断和计算．将这些问题简要综合在表2-15中． 表2-15 若原问题与对偶问题都不可行，用人工变量法 用§1.5介绍的5个计算公式判断变化情况 综合变化，参数、增减变量与约束等 若非最优，用普通单纯形法 可行 非基变量系数及xj的检验 非基变量系数aij 视检验数和基本解来确定 基、基变量、检验数等 基变量系数aij 若不可行，用对偶单纯形法 对偶问题可行 XB bi 若非最优，用普通单纯形法 可行 只有xj的检验数变化 非基变量系数cj 若非最优，用普通单纯形法 可行 所有非基变量的检验数 基变量系数ci 单纯形法 可行与最优 最优表可能发生变化 参数或条件变化 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）的波动对最优解的影响程度，主要研究