CANFile线性规划对偶.pptx

北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法l对偶理论对偶理论 对偶问题对偶问题 对偶定理对偶定理 与单纯形法的关系与单纯形法的关系l互补松弛互补松弛KKT条件条件l基于对偶的方法基于对偶的方法 对偶单纯形法对偶单纯形法(概念、步骤、收敛性概念、步骤、收敛性)北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法对偶理论对偶理论北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法 食谱问题食谱问题：确定食品数量，满足营养需求，花费最小？：确定食品数量，满足营养需求，花费最小？对偶问题：举例对偶问题：举例n种食品，种食品，m种营养成份；第种营养成份；第 j 种食品的单价种食品的单价每单位第每单位第 j 种食品所含第种食品所含第 i 种营养的数量种营养的数量 变量变量：食用第食用第 j 种食品的数量种食品的数量为了健康，每天必须食用第为了健康，每天必须食用第i 种营养的数量种营养的数量 模型：模型：北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法对偶问题：经济解释对偶问题：经济解释 保健品公司：保健品公司：药剂师、营养丸、药剂师、营养丸、定价问题定价问题 对偶问题对偶问题北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法对偶问题：对称形式的对偶对对偶问题：对称形式的对偶对注：对偶是相互的，即注：对偶是相互的，即对偶问题的对偶是原问题对偶问题的对偶是原问题 原始问题原始问题(primal)：给定数据给定数据原问题的变量原问题的变量 对偶问题对偶问题(dual)：对偶问题的变量对偶问题的变量北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法对偶问题：非对称形式的对偶对对偶问题：非对称形式的对偶对注：为了确定任一线性规划问题的对偶，可以利用注：为了确定任一线性规划问题的对偶，可以利用 对称形式或非对称形式的对偶对！对称形式或非对称形式的对偶对！原始问题原始问题(primal)：给定数据给定数据原问题的变量原问题的变量 对偶问题对偶问题(dual)：对偶问题的变量对偶问题的变量北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法对偶问题：一般问题的对偶对偶问题：一般问题的对偶给定数据给定数据c,A,b；记；记 A 的第的第 j 行为行为 aj，A 的第的第 i 列为列为 ai 原问题原问题(primal)：对偶问题对偶问题(dual)：北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法对偶问题：例子对偶问题：例子北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法对偶定理：弱对偶定理对偶定理：弱对偶定理弱对偶定理弱对偶定理.设设 和和 分别是原始问题和对偶问题的分别是原始问题和对偶问题的可行可行解，则解，则推论推论2.2.如果原始问题与对偶问题之一无界，则另一个问题如果原始问题与对偶问题之一无界，则另一个问题 没有可行解没有可行解.推论推论1.1.设设 和和 分别是原始问题和对偶问题的可行解分别是原始问题和对偶问题的可行解,若若 则则 和和 分别是原始问题和对偶问题最优解分别是原始问题和对偶问题最优解.北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法对偶定理：强对偶定理对偶定理：强对偶定理对于一般形式的线性规划利用对于一般形式的线性规划利用凸集分离凸集分离定理定理证明！证明！强对偶定理强对偶定理.如果原始问题和对偶问题之一有解，则另如果原始问题和对偶问题之一有解，则另一个问题也有解，且最优值相等一个问题也有解，且最优值相等.有解有解无下界无下界不可行不可行有解有解无上界无上界不可行不可行 对偶问题对偶问题 原始问题原始问题北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法与单纯形法的关系：定理与单纯形法的关系：定理如何由原始问题的解得到对偶问题的解？如何由原始问题的解得到对偶问题的解？定理定理.设标准形线性规划问题有最优解，设标准形线性规划问题有最优解，B是最优基本可是最优基本可行解对应的基，则行解对应的基，则是其对偶问题的最优解是其对偶问题的最优解.北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法与单纯形法的关系：例子与单纯形法的关系：例子考虑问题考虑问题引入松弛变量引入松弛变量标准形标准形利用单纯形法求解利用单纯形法求解对偶问题对偶问题北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法与单纯形法的关系：例子与单纯形法的关系：例子(续续)原原问题问题最优解最优解对偶对偶问题问题最优解最优解北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法与单纯形法的关系：单纯形乘子与单纯形法的关系：单纯形乘子 与基与基 B 对应的单纯形乘子对应的单纯形乘子(simplex multiplier)经济解释经济解释 记记 A 的列向量为的列向量为 aj，对应费用为，对应费用为 cj，j=1,n解释为单位向量解释为单位向量 ei 的的合成合成价格！价格！解释为解释为aj 的的相对相对费用系数费用系数 最优性最优性：对所有的对所有的 i 有有 北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法与单纯形法的关系：单纯形乘子与单纯形法的关系：单纯形乘子(续续)灵敏度灵敏度(sensitivity，工程上，工程上)假设该问题的最优基是假设该问题的最优基是 B.则则假设假设非退化！非退化！问题：当向量问题：当向量 b 变化时，最优值如何变化？变化时，最优值如何变化？北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法与单纯形法的关系：单纯形乘子与单纯形法的关系：单纯形乘子(续续)影子价格影子价格(shadow price，经济上，经济上)称称 为分量为分量 所对应资源的所对应资源的边际边际价格价格(marginal price)或者或者影子影子价格价格(shadow price)北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法互补松弛互补松弛Complementary Slackness北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法互补松弛定理互补松弛定理其中其中 ai 表示表示A 的第的第 i 列，列，aj 表示表示A 的第的第 j 行行 定理定理.设设 和和 分别是分别是非对非对称称形式原始问题和对偶问题形式原始问题和对偶问题的的可行解可行解.则它们是各自最优则它们是各自最优解的解的充要充要条件是：对所有条件是：对所有 i 有有定理定理.设设 和和 分别是分别是对称对称形式原始问题和对偶问题的形式原始问题和对偶问题的可行解可行解.则它们是各自最优则它们是各自最优解的解的充要充要条件是：对所有的条件是：对所有的 i 和和 j 有有北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法对偶单纯形法对偶单纯形法Dual Simplex Method北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法对偶单纯形法：概述对偶单纯形法：概述 适用问题：标准形问题有一个适用问题：标准形问题有一个不可行不可行的基本解，的基本解，但但 对应单纯形乘子是对偶问题的可行解对应单纯形乘子是对偶问题的可行解 单纯形表中的表现：单纯形表中的表现：第一张单纯形表第一张单纯形表:相对费用系数非负，但有基变量取负值！相对费用系数非负，但有基变量取负值！转轴过程中：保持相对费用系数非负，直到基变量全部转轴过程中：保持相对费用系数非负，直到基变量全部 取非负值！取非负值！北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法则称则称 x 是标准形问题的是标准形问题的对偶可行对偶可行基本解基本解.定义定义.假设是假设是 Ax=b 的基本解的基本解.如果如果基本解可行对偶可行最优解基本解可行对偶可行最优解初始对偶可行基本解初始对偶可行基本解新的对偶可行基本解新的对偶可行基本解“原始可行对偶可行原始可行对偶可行”的基本解！的基本解！迭代迭代对偶单纯形法：对偶可行基本解对偶单纯形法：对偶可行基本解 是对偶问题的可行解，即是对偶问题的可行解，即 北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法设对偶可行基本解设对偶可行基本解 x 对应的基对应的基 B=此外还假设此外还假设 非退化，即非退化，即目的：目的：找新的找新的 使前使前m个等式中的某个与后个等式中的某个与后n-m个不等式个不等式中的某个角色互换，同时使中的某个角色互换，同时使对偶对偶问题的目标函数值问题的目标函数值增大增大！对偶单纯形法：推导对偶单纯形法：推导I I北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法对偶单纯形法：推导对偶单纯形法：推导IIII令令 ，其中，其中 ui 是是 B-1 的第的第 i 行，则行，则出基变量：取出基变量：取负值负值的基变量的基变量(*)(*)进基变量：取到进基变量：取到最小正最小正比值的非基变量比值的非基变量(*)(*)北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法步步0 给定对偶可行基本解对应的单纯形表给定对偶可行基本解对应的单纯形表.步步1 若对若对每个每个 i 都有都有 ，停；当前，停；当前DFBS是最优的是最优的.步步2 选取选取 i 满足满足 yi00，这时，第，这时，第 i 个基变量出基个基变量出基.步步4 以以 yiq 为转轴元进行为转轴元进行转轴转轴，更新单纯形表，返步，更新单纯形表，返步1.对偶单纯形法：计算步骤对偶单纯形法：计算步骤步步3 若若 ，停，问题，停，问题无可行解无可行解；否则，；否则，选选 q 满足满足北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法引入盈余变量；并给等式两边同乘引入盈余变量；并给等式两边同乘-1；得初始表格；得初始表格对偶单纯形法：例子对偶单纯形法：例子北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法对偶单纯形法：例子对偶单纯形法：例子(续续)最优解：最优解：北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法结论结论：由对偶可行基本解确定的单纯形乘子集合与对偶：由对偶可行基本解确定的单纯形乘子集合与对偶问题可行集的极点是完全相同的。问题可行集的极点是完全相同的。DFBS对偶问题对偶问题可行集的极点！可行集的极点！对偶单纯形法：进一步的理解对偶单纯形法：进一步的理解北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法原 问 题北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法对偶单纯形法：收敛性对偶单纯形法：收敛性定理定理.如果标准形线性规划问题的任一对偶可行基本如果标准形线性规划问题的任一对偶可行基本解所对应的非基变量的相对费用系数解所对应的非基变量的相对费用系数大于零大于零，则对偶，则对偶单纯形法在单纯形法在有限步有限步内终止内终止.如果线性规划问题可以用对偶单纯形法求解，则必有界！如果线性规划问题可以用对偶单纯形法求解，则必有界！其计算结果只能是不可行或者有解！其计算结果只能是不可行或者有解！如果线性规划问题可以用单纯形法求解，则其无界或有解！如果线性规划问题可以用单纯形法求解，则其无界或有解！两阶段法可以求解任一线性规划问题；两阶段法可以求解任一线性规划问题；第第I阶段的结果分有可行解或者无可行解两种；阶段的结果分有可行解或者无可行解两种；对有可行解的，在第对有可行解的，在第II阶段可得问题无界或有解！阶段可得问题无界或有解！北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法 典型情况典型情况(有显然的对偶可行基本解有显然的对偶可行基本解)一般情况一般情况 已有一个标准形问题的最优解和最优基已有一个标准形问题的最优解和最优基 添加一个添加一个“不等式约束不等式约束”后的新问题后的新问题灵敏度分析灵敏度分析对偶单纯形法：启动对偶单纯形法：启动“不等式约束不等式约束”后的新问题后的新问题北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法线性规划的应用：线性规划的应用：博弈论博弈论(Game Theory)北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法石头布剪刀石头布剪刀(Rock-Paper-Scissors)二人博弈二人博弈规则：规则：l 在石头、布和剪刀中选择一个，同时宣布选择在石头、布和剪刀中选择一个，同时宣布选择l 相同的选择无效相同的选择无效.否则：否则：石头赢剪刀石头赢剪刀 布赢石头布赢石头 剪刀赢布剪刀赢布支付矩阵支付矩阵：行：行palyer给列给列player的支付的支付(payoff)注注：某个：某个player利用任一利用任一确定性确定性(纯纯)策略，均可被另一策略，均可被另一个个player击败击败.北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法二人零和博弈二人零和博弈(Two-Person Zero-sum Games)给定给定 mn 矩阵矩阵 A注注：A的行代表的行代表rowboy的确定性策略，而的确定性策略，而A的列代表的列代表colgirl的确定性策略的确定性策略.l 行行player(rowboy)选择策略选择策略l 列列player(colgirl)选择策略选择策略l rowboy支付给支付给colgirl aij 美元美元确定性策略可能会很差！确定性策略可能会很差！北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法随机化策略随机化策略(Randomized Strategies)l 假设假设 rowboy 选择策略选择策略 i 的概率是的概率是 yil 假设假设colgirl选择策略选择策略 j 的概率是的概率是 xj如果使用随机如果使用随机(混合混合)策略策略 y，colgirl使用随机策略使用随机策略 x，则，则rowboy向向colgirl的期望支付是的期望支付是北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法Colgirl的分析的分析假设假设colgirl准备采取策略准备采取策略 x则则rowboy最好的防卫是利用最好的防卫是利用 y,其求解问题其求解问题因此因此colgirl应该选取应该选取 x,其极大化这种可能性其极大化这种可能性北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法求解求解Max-Min问题问题(转化成线性规划问题转化成线性规划问题)内层优化很容易：内层优化很容易：引入标量变量引入标量变量 v 表示内层极小化的值：表示内层极小化的值：因此因此colgirl的问题是的问题是北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法Rowboy的问题的问题类似地，类似地，rowboy选择选择 y该问题等价于：该问题等价于：注：注：colgirl的问题是的问题是rowboy的问题的对偶的问题的对偶北京航空航天大学数学与系统科学学院第第03章章 线性规划：对偶线性规划：对偶实用优化方法实用优化方法MinMax定理定理设设 x*表示表示colgirl的的max-min问题的解；设问题的解；设 y*是是rowboy的的min-max问题的解问题的解.则则证明证明.由强对偶定理，我们有由强对偶定理，我们有且且