can-fi前le-10-10-08-13-线性规划对偶.ppt

第03章 线性规划：对偶Linear Programming: duality 对偶理论 －对偶问题 －对偶定理 －与单纯形法的关系 互补松弛－KKT条件 基于对偶的方法 －对偶单纯形法(概念、步骤、收敛性) 弱对偶定理. 设 和 分别是原始问题和对偶问题的可行 解，则 如何由原始问题的解得到对偶问题的解？ 原 问 题 * 北京航空航天大学 数学与系统科学学院 第03章 线性规划：对偶 实用优化方法 对偶理论 ◎ 食谱问题：确定食品数量，满足营养需求，花费最小？ 对偶问题：举例 n种食品，m种营养成份；　　－第 j 种食品的单价 －每单位第 j 种食品所含第 i 种营养的数量 ◎ 变量： 　　－食用第 j 种食品的数量 －为了健康，每天必须食用第i 种营养的数量 ◎ 模型： 对偶问题：经济解释 ◎ 保健品公司：药剂师、营养丸、定价问题 ◎ 对偶问题 对偶问题：对称形式的对偶对 注：对偶是相互的，即对偶问题的对偶是原问题 ◎ 原始问题(primal)： 给定数据 －原问题的变量 ◎ 对偶问题(dual)： －对偶问题的变量 对偶问题：非对称形式的对偶对 注：为了确定任一线性规划问题的对偶，可以利用 对称形式或非对称形式的对偶对！ ◎ 原始问题(primal)： 给定数据 －原问题的变量 ◎ 对偶问题(dual)： －对偶问题的变量 对偶问题：一般问题的对偶 给定数据c, A, b；记 A 的第 j 行为 aj，A 的第 i 列为 ai ◎ 原问题(primal)： ◎ 对偶问题(dual)： 对偶问题：例子 对偶定理：弱对偶定理 推论2. 如果原始问题与对偶问题之一无界，则另一个问题 没有可行解. 推论1. 设　 和 分别是原始问题和对偶问题的可行解,若 则　 和 分别是原始问题和对偶问题最优解. 对偶定理：强对偶定理 对于一般形式的线性规划－－利用凸集分离定理证明！ 强对偶定理. 如果原始问题和对偶问题之一有解，则另一个问题也有解，且最优值相等. √ × × 有解 × × √ 无下界 × √ √ 不可行 有解 无上界 不可行 对偶问题 原始问题 与单纯形法的关系：定理 定理. 设标准形线性规划问题有最优解，B是最优基本可行解对应的基，则 是其对偶问题的最优解. 与单纯形法的关系：例子 考虑问题 引入松弛变量→标准形→利用单纯形法求解 对偶问题 与单纯形法的关系：例子(续) 原问题最优解 对偶问题 最优解 与单纯形法的关系：单纯形乘子 ◎ 与基 B 对应的单纯形乘子(simplex multiplier) ◎ 经济解释 记 A 的列向量为 aj，对应费用为 cj，j=1 , … , n －－－－－－－－解释为单位向量 ei 的合成价格！ －－解释为aj 的相对费用系数 ◎ 最优性：对所有的 i 有 与单纯形法的关系：单纯形乘子(续) 灵敏度(sensitivity，工程上) 假设该问题的最优基是 B. 则 假设非退化！ 问题：当向量 b 变化时，最优值如何变化？ 与单纯形法的关系：单纯形乘子(续) 影子价格(shadow price，经济上) 称 为分量 所对应资源的边际价格(marginal price) 或者影子价格(shadow price) 互补松弛 Complementary Slackness 互补松弛定理 其中 ai 表示A 的第 i 列，aj 表示A 的第 j 行 定理. 设 和 分别是非对称形式原始问题和对偶问题的可行解.则它们是各自最优解的充要条件是：对所有 i 有 定理. 设 和　 分别是对称形式原始问题和对偶问题的可行解. 则它们是各自最优解的充要条件是：对所有的 i 和 j 有 对偶单纯形法 Dual Simplex Method 对偶单纯形法：概述 ◎ 适用问题：标准形问题有一个不可行的基本解，但 对应单纯形乘子是对偶问题的可行解 ◎ 单纯形表中的表现： ⊙ 第一张单纯形表: 相对费用系数非负，但有基变量取负值！ ⊙ 转轴过程中：保持相对费用系数非负，直到基变量全部 取非负值！ 则称 x 是标准形问题的对偶可行基本解. 定义. 假设　　　　　　　是 Ax=b 的基本解. 如果 基本解＋可行＋对偶可行＝最优解 初始对偶可行基本解 新的对偶可行基本解 “原始可行＋对偶可行”的基本解！ ……迭代…… 对偶单纯形法：对偶可行基本解 是对偶问