CAN-File-10-10-08-13-线性规划对偶.ppt

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