运筹学7_对偶理论II.pdf

对偶理论对偶理论对偶理论对偶理论 （（（（二二二二）））） 李田 华东理工大学商学院 2014年春季学期年春季学期 回顾对偶问题的相互对应回顾对偶问题的相互对应 原问题（对偶问题）原问题（对偶问题）原问题（对偶问题）原问题（对偶问题） 对偶问题（原问题）对偶问题（原问题）对偶问题（原问题）对偶问题（原问题） 目标函数目标函数 maxmax 目标函数目标函数 minmin 目标函数的系数目标函数的系数目标函数的系数目标函数的系数 约束条件右端常数约束条件右端常数约束条件右端常数约束条件右端常数 约束条件右端常数约束条件右端常数 目标函数的系数目标函数的系数 约 约 约 约 mm个个 mm个个 件 件 条 条 束 束 ≤≤ ≥≥00 变 变 量 量 ≥≥ ≤≤00 == 无符号限制无符号限制无符号限制无符号限制 约 约 nn个个 nn个个 变 变 变 变 ≥≥≥≥0000 ≥≥≥≥ 束 束 束 束 量 量 ≤≤00 ≤≤ 件 件 条 条 无符号限制无符号限制无符号限制无符号限制 == 总结如何写出对偶总结如何写出对偶 • 对称型的线性规划仍然是对称型 • 一个问题的约束数和变量数分别是另一个问题的变量 数和约束数数和约束数 • 一个问题的价值系数和资源限量与另一问题的资源限 量和价值系数相对应 • 一个问题等式约束与另个问题等式约束与另一个问题变量无约束相对应个问题变量无约束相对应 • 如果如果一个问题约束个问题约束 （（变量变量））的不等式符号与它的对称的不等式符号与它的对称 形式的符号相反，那么另一个问题变量（约束）的不 等式符号与它的对称形式符号相反等式符号与它的对称形式符号相反 提纲提纲 • 对偶问题的基本性质 • 对偶问题的经济含义 – 影子价格 • 对偶单纯形法 提纲提纲 • 对偶问题的基本性质 • 对偶问题的经济含义 – 影子价格 • 对偶单纯形法 对称形式的单纯形解对称形式的单纯形解 max z CX max z C X + C X + 0X B B N N S AXAX ≤≤ bb