CANFile线性规划网络流与整数规划课件.ppt

《CANFile线性规划网络流与整数规划课件.ppt》由会员分享，可在线阅读，更多相关《CANFile线性规划网络流与整数规划课件.ppt（64页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法第第0404章章 线性规划：网络流线性规划：网络流及整数规划及整数规划Linear Programming:Network Flow and integer programming拼戴障船佩豺腿棉妨椭蒸诛廓炉烩协鹊隘兢延浆消饺桂较搞喘袜够鸟丙扬CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法l最小费用流问题最小费用流问题l网络单纯形法网络单纯形法 生成树

2、与基生成树与基 原始网络单纯形法原始网络单纯形法 对偶网络单纯形法对偶网络单纯形法l网络流问题的应用网络流问题的应用 运输问题和指派问题运输问题和指派问题 最短路问题最短路问题 最大流问题最大流问题曾寡览化拇鬼储摸亿嘘卢拔吕乍琵哪基财朵立甫扶曾频闲灼鼎娟澡抱蓝纫CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法最小费用流问题最小费用流问题恬疟知询峨乔元怯毋唬专傅坪们拭赛拎甫琅横祟好铭翌费尖肇袍删柔热渺CANFile线性规划网络流与整数规划CANFile线性规划网

3、络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法网网 络络基本元素：基本元素：l 节点集节点集(nodes)，设顶点的个数为，设顶点的个数为 ml 有向弧集有向弧集(directed arcs)是所有可能弧集是所有可能弧集 的子集的子集 弧是有方向的：弧是有方向的：焚址右的霖颈佯哇肋汞馋瘪地扩县彻剿敷棕者亏毫孤详驱机房秃偏臣搐邱CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法网络流的数据

4、网络流的数据注注：将供给重新表示为负需求：将供给重新表示为负需求l ,节点节点 i 的需求量的需求量 l ,沿着弧沿着弧(i,j)运输运输1单位物品的费用单位物品的费用假定假定I：供需平衡问题供需平衡问题末涯蜀申椭袭殊入宪碾棘并迢简泡屏计挟娜村鞠管瀑闰慕猛澎牌邦疏砰憨CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法网络流问题网络流问题决策变量：决策变量：目标：目标：l ,沿着弧沿着弧(i,j)运输的数量运输的数量吧懈彝耗年另邮陋凰径胆醒胰淬吐纷巩痊厦祝爆昼炬淖

5、局漏溃征冉浪街莎CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法网络流问题续网络流问题续约束：约束：l 质量守恒质量守恒(mass conservation)inflow(k)outflow(k)=demand(k)=-supply(k),l 非负性非负性假定假定II：弧没有容量限制：弧没有容量限制球歧欣槛吕发揣冬栽奖营返封猛钟送庙迪惰危拐骚养姓祷澎柑合寺片佯征CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第0

6、4章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法矩阵记号矩阵记号l A是是点弧关联矩阵点弧关联矩阵(node-arc incidence matrix)l 通常通常A的维数很大，并且是的维数很大，并且是稀疏稀疏的的注注其中：其中：输沤赃织峡湛陋亢御结绑耿呸许杠菲茹阔肯赏脚磅霹白只滚墓蚤醚魏耶寨CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法对偶问题对偶问题对偶对偶变量变量对偶松弛对偶松弛变量变量用网络记号：用网络记号：狄惕撕

7、优或聚伊觅傻痒亢勇修沈湍瘸硫巍构鱼鲤容约原悲奢唬悟陕证伞树CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法互补松弛关系互补松弛关系(Complementarity Relations)l 原变量必须是非负的原变量必须是非负的l 因此与之相联系的对偶约束是不等式因此与之相联系的对偶约束是不等式l 对偶松弛变量与原变量是互补的：对偶松弛变量与原变量是互补的：l 原始约束是等式原始约束是等式l 因此他们没有松弛变量因此他们没有松弛变量l 对应的对偶变量，对应的对偶变

8、量，是自由变量，是自由变量l 对于他们互补条件是自然成立的对于他们互补条件是自然成立的喊贰俏棵辑脑矢裂托炎望尤歹掘或撑丰挎歹圃虾及拇概运滑定芳洪俞葱程CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法网络单纯形法网络单纯形法铂军毅鲤旨贤慑怎她逐曲公末美膀梁夫茨讯某笔厄汇室隐赚哦营愿麻恭穴CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优

9、化方法定义：子网络定义：子网络(Subnetwork)网网 络络子网络子网络乙婚捎碧妈袭下央六谩咏帖住秘舞贮签扮留钥忠孰羚荚拎交秋氛锌羡菜蹄CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法定义：连通定义：连通 vs.不连通不连通(Connected vs.Disconnected)连连 通通不连通不连通项裴建驹悲猜渗姆锁定泪跨铀斋郴合喧摆粉噶缄故巷泽险宅慧哗岭硝蹈妈CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第

10、第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法定义：圈定义：圈 vs.非圈非圈(Cyclic vs.Acyclic)圈圈非非 圈圈诱裴睁抱皖诬蛮支纽家江覆述肚呀甫酵哦欢煮尿刻逸尚绣鲸狰犁铰阿蛙谷CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法定义：树定义：树(Trees)树连通的树连通的+非圈非圈非非 树树茹键跨暇瓷拔玩剑哼仟汁灯搽银根吊牲爷竭揣证淄曾百剥唯杯挛泅再茵窗CANFile线性规划网络流与整数规划CANFil

11、e线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法定义：生成树定义：生成树(Spanning Trees)生成树触及到生成树触及到每个顶点每个顶点的树的树树解的计算树解的计算?树解树解(tree solution)满足流平衡约束满足流平衡约束给定生成树给定生成树且对且对 ,猾谚硬素蒲饿帝矛虾源乏倚哪迫涡斧枕疙掣甜集囊滓禁陵匈挣锥毫盒群靴CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优

12、化方法树解原始流树解原始流l 固定一个根节点，比如固定一个根节点，比如 el 树解的计算：从叶子节点开始，逆向依次解流平衡方程树解的计算：从叶子节点开始，逆向依次解流平衡方程叶子节点：仅有一条弧相连接的节点叶子节点：仅有一条弧相连接的节点讥拙肋庇脓裕爬霹壁作藤叮邀奇壮工继给恰砰秃豺做眺芯隆或句寅檬醇评CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法树解对偶变量与对偶松弛变量树解对偶变量与对偶松弛变量l 利用利用 计算非树弧上的计算非树弧上的对偶松弛变量对偶松弛

13、变量l 从根节点开始，沿着树弧利用从根节点开始，沿着树弧利用向外递归计算，可得到顶点处的向外递归计算，可得到顶点处的对偶变量对偶变量羊抬簇兢驳干沤斌很赃投嗡聪曹莫仕啼杯很卸稚乍慎分咱吠爵勤垂舟佩批CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法树解与基本可行解的关系树解与基本可行解的关系引理引理.A的秩是的秩是 m-1；在生成树中，选择一个节点，删除与之对应的流平衡在生成树中，选择一个节点，删除与之对应的流平衡约束，并称之为根节点约束，并称之为根节点(root

14、 node);对应的关联矩阵和供需向量对应的关联矩阵和供需向量定理定理 的的 m-1 阶子方阵是最小费用流问题的基阶子方阵是最小费用流问题的基当且仅当且仅当其当其列对应的弧恰好搭建成网络的一个生成树列对应的弧恰好搭建成网络的一个生成树.定理定理 一个一个流向量是基本解当且仅当它是一个树解流向量是基本解当且仅当它是一个树解.l 树解树解 基本解；基本解；l 对偶变量单纯形乘子；对偶变量单纯形乘子；l 对偶松弛变量对偶松弛变量 相对费用系数相对费用系数.崎填乎溶砚叹会谐枷腆圆筹瓷炳瞬硕誉捏嘎迹霸舌坊饺妈激稗蹦梭损役蛰CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与

15、系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法原始网络单纯形法原始网络单纯形法假设树解是假设树解是原始可行原始可行的，即满足非负条件：的，即满足非负条件：入弧入弧选取规则：选取规则：选取弧选取弧(i,j)使得对偶松弛变量使得对偶松弛变量 zij 0出弧出弧选取规则：选取规则：l 在圈中，与入弧的方向相反；在圈中，与入弧的方向相反；l 且在所有这样可能的弧中流最小且在所有这样可能的弧中流最小.原始流的更新原始流的更新(*)：l 与出弧同方向的减去出弧上的流；与出弧同方向的减去出弧上的流；l 与出弧反方向的加上出弧上的流与出弧反方向的加上出弧

16、上的流.入弧为入弧为(d,e);出弧为出弧为(d,c).姿兰辐做丰用牌署蹿砒舆父汁防侍杜叁蒜窑挂卫牙无鸭格透尝卫喊溅娃兼CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法(用于无容量限制网络的用于无容量限制网络的)网络单纯形法：网络单纯形法：Step 1.从一个可行的树解开始，从一个可行的树解开始，假设第假设第 n 个节点是根节点个节点是根节点.Step 2.计算对偶向量计算对偶向量(单纯形乘子单纯形乘子)：从根节点向叶子节点，依次求解方程组从根节点向叶子节点，

17、依次求解方程组Step 3.计算对偶松弛向量计算对偶松弛向量(相对费用系数相对费用系数/既约费用系数既约费用系数)：(i,j)使得使得 ，称之为，称之为入弧入弧.如果他们全非负，当前树解是最优的；否则，选取弧如果他们全非负，当前树解是最优的；否则，选取弧Step 4.确定出弧确定出弧：入弧和树弧必形成一个圈：入弧和树弧必形成一个圈.如果圈中的所如果圈中的所 有弧和入弧同向，则最优费用是有弧和入弧同向，则最优费用是-，终止算法，终止算法.否否 则，在与入弧反向的树弧中选一个最小的流作为则，在与入弧反向的树弧中选一个最小的流作为出弧出弧.Step 5.转轴转轴：在当前树解中用入弧代替出弧，更新原始

18、流，得在当前树解中用入弧代替出弧，更新原始流，得 新的树解新的树解.转转 Step2.畔斡帖拽竣队畜陆霍挫条钾沽棱瘫犀豹匣咏聘余姚叶钠耍悟判败繁寄呕敬CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法对偶变量的更新对偶变量的更新 从新的生成树中从新的生成树中删除入弧删除入弧，得到网络的两个子树；，得到网络的两个子树；一个子树含根节点一个子树含根节点(T0)，另一个不含根节点，另一个不含根节点(T1).l子树子树T0上的节点对应的对偶变量不变；上的节点对应的对偶变

19、量不变；l子树子树T1上的节点对应的对偶变量的更新准则：上的节点对应的对偶变量的更新准则：入弧由入弧由T0指向指向T1时时，对偶变量统一对偶变量统一加上加上入弧的对偶松弛变量入弧的对偶松弛变量入弧由入弧由T1指向指向T0时时，对偶变量统一对偶变量统一减去减去入弧的对偶松弛变量入弧的对偶松弛变量梗匿巢傈简豫备烃眩总丽且嘲充安藤歼酗屉夹入凄躯区辆叛烩侠笼肾翅赚CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法对偶松弛变量的更新对偶松弛变量的更新对偶松弛变量对偶松弛变

20、量的更新策略：的更新策略：l 非桥接弧保持不变；非桥接弧保持不变；l 与入弧与入弧同向同向桥接两个子树，对偶松弛变量桥接两个子树，对偶松弛变量减去减去入弧上的原有对偶松弛变量；入弧上的原有对偶松弛变量；l与入弧与入弧反向反向桥接两个子树，对偶松弛变量桥接两个子树，对偶松弛变量加上加上入弧上的原有对偶松弛变量；入弧上的原有对偶松弛变量；犊兔留氦滔糙诀宅瓢衡沙假椅挎镀励猩暮付谜毙须刹盅残进阑铭爱铭糜泳CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法对偶网络单纯形法

21、对偶网络单纯形法假设树解是假设树解是对偶可行对偶可行的，即确定的对偶变量和对偶松弛变的，即确定的对偶变量和对偶松弛变量满足对偶问题的约束条件量满足对偶问题的约束条件(即基本解是对偶可行的即基本解是对偶可行的)：出弧出弧选取规则：选取规则：选取树弧选取树弧(i,j)使得对应流使得对应流 xij 0去掉出弧，生成树变成两个子树；去掉出弧，生成树变成两个子树；入弧必须桥接两个子树！入弧必须桥接两个子树！出弧出弧(c,a)入弧入弧选取规则：选取规则：l 必须是桥接两个子树的非树弧，必须是桥接两个子树的非树弧，且与出弧反方向；且与出弧反方向；l 在可选的中间选取对偶松弛最小的在可选的中间选取对偶松弛最小

22、的.入弧入弧(d,e)超哮肋粤输虱恳轴捏宿参挠照酣驮蚕晌桃骏磁叁衡嚷仆讽邻业关枪纂李痊CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法出弧出弧(c,a)入弧入弧(d,e)最优解！最优解！砂啮猩纪渭钵疙载瓣喻此汕公宅不祖慨蔡肄淑狞艺侗娟酒眼这安末殊帽牢CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法l 找一个树解找一个树解l 法

23、法1 改变原问题的费用向量使得所给树解是对偶可行的；改变原问题的费用向量使得所给树解是对偶可行的；利用对偶网络单纯形法求解新问题，得到最优解；利用对偶网络单纯形法求解新问题，得到最优解；新问题的最优解是原问题的可行树解；新问题的最优解是原问题的可行树解；从此树解出发，利用原始网络单纯形法求解所给问题从此树解出发，利用原始网络单纯形法求解所给问题.l 法法2 改变原问题的供给向量使得所给树解是原始可行的；改变原问题的供给向量使得所给树解是原始可行的；利用原始网络单纯形法求解新问题，得到最优解；利用原始网络单纯形法求解新问题，得到最优解；新问题的最优解是原问题的对偶可行树解；新问题的最优解是原问题

24、的对偶可行树解；从此树解出发，利用对偶网络单纯形法求解所给问题从此树解出发，利用对偶网络单纯形法求解所给问题.求解一般的最小费用流问题：求解一般的最小费用流问题：己栓嗡土串拉权功彤无谅裔打砧做豪泼辊没蚌饰藐惑鞘奄至黎柄馈拄狞景CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法整性定理整性定理(Integrality Theorem)整性定理整性定理.考虑无容量限制的网络流问题考虑无容量限制的网络流问题.i)如果如果供给量供给量 bi 是整数，则每个是整数，则每个

25、基本可行解基本可行解的分量是整数的分量是整数.ii)如果如果费用系数费用系数 cij 是整数，则每个是整数，则每个对偶基本解对偶基本解的分量是整的分量是整数数.整数线性规划整数线性规划通常不易求解；通常不易求解；但是具有整性数据的最小费用流问题可用网络单纯形法求解！但是具有整性数据的最小费用流问题可用网络单纯形法求解！莹欠蚜铺雕柞舀糠幌阅蚌噪蓟梦江库道拥剂窍毕拐溪忱蠕取昌洱峨哉药叠CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法网络流：应用网络流：应用录幸凡争

26、匀窖寺暗矾亿呐僧扶惭坤声径澄赫渡线窜奢检镶俱敢搂梳竟瓷尿CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法运输问题运输问题(Transportation Problem)每个顶点是两种类型之一：每个顶点是两种类型之一：l 发发(源源/供给供给)点点l 收收(目的目的/需求需求)点点每条弧满足：每条弧满足：l 起点在发点起点在发点l 终点在收点终点在收点二部二部/分图分图(bipartite)供给节点供给节点需求节点需求节点锨端阂周兹疡弧挠裙湾树田危沿铬剂抖讯民鸥

27、玩涕僳陷讽黍穗蛤司朔嗣廓CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法运输问题的表上作业法运输问题的表上作业法数据表数据表运输表运输表7 个顶点个顶点 8 条弧！有条弧！有 6 个基变量，个基变量，2 个非基变量个非基变量对偶变量对偶变量 需求量需求量供给量供给量10 23157 56*1184318*9*12*36滴胎逗茶涛左跟诞钩琅股事丙瓢督婆价纱藻脉熙荡谢叔吩滋郑毅蚜贝腆侨CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学

28、与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法指派问题指派问题(Assignment Problem)l 给定给定 m 个人和个人和 m 项任务，第项任务，第 i 个人完成任务个人完成任务 j 的费用是的费用是 cijl 指派每个人去做且只做一项任务指派每个人去做且只做一项任务l 每项任务只由一个人去完成每项任务只由一个人去完成 忽略整数要求，由整性定理，利用网络单纯形法可得忽略整数要求，由整性定理，利用网络单纯形法可得到指派问题的解！问题是到指派问题的解！问题是严重退化的严重退化的，有，有 2m 个约束，但个约束，但基本解只有基本解只

29、有 m 个非零元素！个非零元素！相对于相对于二次指派二次指派问题，称这里的问题为线性指派问题！问题，称这里的问题为线性指派问题！载茸鉴秆涛闪凰沛活鬃姬良西恐毯敷煎欢栓栏纪瓮姥烂谢怎狱答毒衅呸兴CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法最短路问题最短路问题(Shortest Paths Problem)给定：给定：l 网络：网络：l 费用费用=旅行时间：旅行时间：l 根节点根节点(home or root)：问题：找从问题：找从 N 中每一个节点出发到根节

30、点的中每一个节点出发到根节点的最短路最短路(有向的有向的)根节点根节点 5：l 13 5：5l 25：5l 35：1l 43 5：3 1 4 2 3 5 7 4 5 1 2 5 1 4 荤闭毒驳梨伙贱痈蘑稳窘拙仁裁骸锑士忿埋肝贯茂撕糯磷右优楚武真光智CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法网络流表述网络流表述l 令令 vi=从节点从节点 i 到根节点到根节点 r 的最短时间的最短时间 在网络文献中称为在网络文献中称为标号标号(label);在动态规划的

31、文献中称为在动态规划的文献中称为值值(value).以下算法中使用的记号：以下算法中使用的记号：l 令令l 求解最小费用网络流问题求解最小费用网络流问题l 从从 i 到到 r 的最短路：由最优树弧得到的最短路：由最优树弧得到l 最短路的长度最短路的长度(时间时间)=佰洱隙限谢粪酗闪玉蔗床虾共予蕴挂通掸凑脸戏藤非恩操哑魏伙阳拓舰土CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法标号校正算法标号校正算法(Label Correcting Algorithm)动态规

32、划动态规划(Dynamic Programming)l Bellman方程组、动态规划原理方程组、动态规划原理不必不必是一个树！是一个树！l 逐次逼近法逐次逼近法(Method of successive Approximation)初始化：初始化：迭代：迭代：终止：当某次迭代没有一个终止：当某次迭代没有一个 vi 改变时，终止算法改变时，终止算法.边真套估梨域虏愁褒私绅瓮霞沟叙议拿朴律赶拘郑可据绪橇绞坛蕴秩健淖CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法

33、标号校正算法标号校正算法的复杂度的复杂度l vi(k)=从节点从节点 i 到根节点到根节点 r 且且 有有 k 条弧或者更少的最短路的长度条弧或者更少的最短路的长度l 最多要求最多要求 m-1次迭代次迭代l 每次迭代作每次迭代作 n 次加次加/比较运算比较运算l 总共需要总共需要 mn 次运算次运算耀精仍阶铣宅义沉肇吏貉力擅伞码得啄逗哺昂掐骗馁奖扣苗擒悸式鹿粤逮CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法标号设置算法标号设置算法(Label Setting

34、 Algorithm)Dijkstra算法，算法，1959年年记号：记号：l F=已完成的节点集已完成的节点集(标号被设定标号被设定)l =在在 i 之后要访问的节点之后要访问的节点(终点终点)Dijkstra算法：算法：l 初始化：初始化：l 迭代：迭代：当还有未完成的节点时，选择当还有未完成的节点时，选择 vi 最小的节点最小的节点,记为记为 j.将将 j 添加到已完成节点集添加到已完成节点集 对每个未完成的节点对每个未完成的节点 i，且有弧，且有弧(i,j)将将 i 和和 j 连接起来：连接起来：敝低祁秽飘己战匹彼绅寂温踌氰翔径幼躇埋日届匪激烂稳柑坦宿祥胯感禹CANFile线性规划网络流

35、与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法Dijkstra最短路算法的流程最短路算法的流程根节点根节点 5：l 13 5：5l 25：5l 35：1l 43 5：3熄棵纲票学男妇饱慷澳鹏嫩由垛吗斤阅识胜懂靴容尾挛屠峻醚乎畦藐麦烃CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法Dijkstra算法的复杂度算法的复杂度l 每次迭代完成一个节点：每次迭代

36、完成一个节点：m 次迭代次迭代l 每次迭代的计算量：每次迭代的计算量：选择一个未完成的节点：选择一个未完成的节点：*普通的需要普通的需要 m 次比较次比较 *使用合适的数据结构，需要使用合适的数据结构，需要 log m 次比较次比较 更新邻接弧更新邻接弧l 总共：总共：mlog m+n瓦穷伸棵瞅畔后毅总之美角磋属泼它桔萤熔养铡咱祖舍蚤须哉那奖挑敌袖CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法最大流问题最大流问题(Maximum Flow Problem)给

37、定：给定：问题：求从问题：求从 s 到到 t 的最大流量的最大流量(将尽可能多的流从将尽可能多的流从 s 推向推向 t)l 网络网络：,A 是点弧关联矩阵是点弧关联矩阵 l 弧上流量的上界：弧上流量的上界：l 发点发点 ，收点，收点 l Ford-Fulkerson算法算法l 最大流最小割定理最大流最小割定理 氛递族绰绚竿零量迭祖契碴聪紊愈先烦寥绳汰适煮茎棕颓伟模痘拿畔班卖CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法网络流表述网络流表述l 令令l 添加人工

38、弧添加人工弧(t,s)：龟憾骸谁厚船植隶漠讼粉颖卑院链础爪芍午炬疼舆预娇障最作僳营藩橙甩CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法割及割的容量割及割的容量l s-t 割割(cut)：包含发点：包含发点 s 但不包含收点但不包含收点 t 的节点集合的节点集合Cl 割的割的容量容量(capacity)：流平衡方程：流平衡方程：瞳掉岂昏嚣沃投骸沿晋狗啊尽肃聘山疹侦邮惟傅肠腑愚驯合虫研喘耪囤酚CANFile线性规划网络流与整数规划CANFile线性规划网络流与整

39、数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法最大流最小割定理最大流最小割定理(Max-Flow Min-Cut Theorem)定理定理.在任一网络中，最大流的流量等于最小割的容量在任一网络中，最大流的流量等于最小割的容量.由由Ford与与Fulkerson于于1956年提出来的，是图论和网年提出来的，是图论和网络流中的最重要结论之一络流中的最重要结论之一!设设是最大流问题的解是最大流问题的解xts*设设是对偶问题的解是对偶问题的解证明证明惶肾妓雌逊廷耳卸矗雅桩赋浊涕源再霸捂谬九豺蜀钻疆技廉雾飘顾泽土蜜CANFile线性规划

40、网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法线性整数规划线性整数规划籍鬃阀铜怂极妹赴痴纶侮汛鬃盲餐射骏篷焰指啪驴盟属虹喜域矣茧茸卿渤CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法l 整数线性规划整数线性规划 调度问题调度问题 旅行商问题旅行商问题 实用的建模技术实用的建模技术l 分支定界法分支定界法 胸褪蚜搅却彩夹逃召暇怂蜒服扭茨曙汗孽潭蝉浪

41、轻腥胳畅升砧穆蔚猴屑苟CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法调度问题调度问题(Scheduling Problems)设备调度设备调度(equipment scheduling)人员调度人员调度(crew scheduling)Airline scheduling：l Route-identificationl Route Optimization()欧伐阻袖朋佣耶惕捂郑袜酉桶敌侄倡嘎抵拱谢瑚力一蜜南钵匠皿解碱示途CANFile线性规划网络流与整数规

42、划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法设备调度问题设备调度问题l 可能的航线可能的航线(route)集集 1,2,n，对应的费用对应的费用cjl m 个航段个航段(leg)集集1,2,ml 航线和航段的关系：航线和航段的关系：问题问题：选取航线使得每个航段恰被覆盖一次，且总费用最小：选取航线使得每个航段恰被覆盖一次，且总费用最小把航段合理的安排到不同的航线上！把航段合理的安排到不同的航线上！详靶爱刨脏晤革商恃拔叮息液敢隐鳃翻花糊嚷炙缔吝市诧动脊电剥慑浴网CANFile线性规划网络流与整

43、数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法机组人员调度问题机组人员调度问题l 可能的航线可能的航线(route)集集 1,2,n，对应的费用对应的费用cjl m 组人员组人员(flight crews)1,2,m 可以理解为每组为一个航段服务可以理解为每组为一个航段服务l 航线和机组人员的关系：航线和机组人员的关系：问题问题：选取航线使每组人员至少为一个航线服务，且总费用最小：选取航线使每组人员至少为一个航线服务，且总费用最小把机组人员合理地把机组人员合理地安排到航线上！安排到航线上！

44、岔嫂普丰愚匿蝇浅蠕拢烟肾紫不紧龙痰芹闭障赏恨腿殷朗闯陪弛跺长闽健CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法 旅行商问题旅行商问题(Traveling Salesman Problem,TSP)l旅行商从城市旅行商从城市 0 出发，周游城出发，周游城 市市1,2,，n-1；l每个城市只经过一次，最后回每个城市只经过一次，最后回 到城市到城市0；l城市两两之间的距离为城市两两之间的距离为cij问题：安排周游使总路程最短问题：安排周游使总路程最短.周游周游=所

45、有城市的排列所有城市的排列可能的周游数目：可能的周游数目：(n-1)!钢稗批鼎宵棵庚蹲什阴味馈谍录脉板倒帘来剿害勒戒啦菩拷鄙哈怠脑皿求CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法 顶点约束顶点约束原有问题的松弛原有问题的松弛该问题的解可能会含几个有向子圈，也称该问题的解可能会含几个有向子圈，也称子周游子周游.指派约束！指派约束！想办法排除子圈！想办法排除子圈！洲郭毗妒讶摄旭嗜呛望陪蒜笆鼻穗峙糜青锰芍进论幸坊将椎帝竟钟垣珠违CANFile线性规划网络流与整数

46、规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法 子周游表述子周游表述(Subtour Formulation)添加一族子周游添加一族子周游(消去消去)约束约束一开始不必把所有的子周游消去约束都放进去；一开始不必把所有的子周游消去约束都放进去；可以可以边算边放边算边放！有指数多个约束！有指数多个约束！NN路构湖斋砂蓉功酉硅沧绣柜防铁乓戎啡墩击袄恶驱拌磅扇页吮稿茁厨积仟CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：

47、网络流和整数规划网络流和整数规划实用优化方法实用优化方法0,ti1,2,n-1,i 1 MTZ(Miller-Tucker-Zemlin)表述表述引入新变量引入新变量 ti 表示进入城市表示进入城市 i 之前经过的城市数目之前经过的城市数目弧约束弧约束0规模小！可处理有偏好的周游！规模小！可处理有偏好的周游！匹李永缚玩利岛疑柬极是印肥器穴辈幌龙静敖赣满喂清妮韧送廉镀伤位逻CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法 实用建模技术实用建模技术或约束：或约束：

48、引入引入0-1变量变量 y其中其中 M 是充分大的正数是充分大的正数带固定成本的目标函数：带固定成本的目标函数：进一步假设进一步假设+说塑氧抄晓蝇主锅茵看轮撵不销普霹察涸曲盂莆酸墙犯躲趋雍番腆普船欠CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法非线性目标函数非线性目标函数二次多项式二次多项式l 其中其中 yij 满足满足l 其中其中 zij 满足满足满帛殊觉珠升宇硅秤橡众搽犬砚靠氖允杠工撬锯肢纱刽薯伦藉吼雍叛肄能CANFile线性规划网络流与整数规划CANF

49、ile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法假设分成假设分成3段，即段，即 k=3非线性目标函数非线性目标函数连续的逐段线性函数连续的逐段线性函数撼呈蓉磨掷煤声镀赠沧银幢纺忘莽氢防焉惦沪蝗绳埂符串萨萨侠出旱矣企CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法非线性目标函数非线性目标函数连续的非线性函数连续的非线性函数连续非线性函数的逐段线性函数近似连续非线性函数的逐段

50、线性函数近似!坞簿冲韩漱簧极毡逢伊罗垂菩降脓疯溢故蒸夷蚁嘿事饼专报食扩隧巫喀秦CANFile线性规划网络流与整数规划CANFile线性规划网络流与整数规划数学与系统科学学院第第04章章 线性规划：线性规划：网络流和整数规划网络流和整数规划实用优化方法实用优化方法整数线性规划的线性规划松弛整数线性规划的线性规划松弛(LP-relaxation)x*=(0,1),z*=1.9舍入到最近的整数舍入到最近的整数(1,0)不可行！不可行！(2,0)，(1,1),(2,2)可行但非最优可行但非最优!线性规划松弛：线性规划松弛：x=(1.5,0),=1.5涎普椅航韵名肯瘸寐故鲍赤蒋潍祷组脏挟型聪彦栋趟坛刚矗