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