运筹学第17讲最小费用最大流-绍兴文理学院.pptVIP

教案要点 文 件 名：051OR17.PPT；第十章.XLS 授课时间：第十七讲 授课内容：第十章图与网络模型，习题 预备知识：最大流. 复习:最大流算法. 难 点：最小费用最大流问题. 重 点：最小费用最大流问题及其它组合优化的应用实例。 预习：教材第十一章排序与统筹方法。 运筹学 绍兴文理学院 工学院计算机系 第十章图与网络模型Graph and Network Optimal 图与网络基本概念 最小生成树问题 最大流问题 最小费用最大流问题 最大流问题 作为LP问题用Excel的规划求解; 网络图论算法 最小费用最大流问题 问题的提法：(P.225)； 问题的LP解法：(P.225); 问题的网络图论解法：费用当路长找最短路，路中找最大流，删边，…，反复寻找。(P.226)。 最小费用最大流问题 作为LP问题用Excel的规划求解; 网络图论算法:分费用、流量两张图。 最小费用最大流问题 费用看作边长的图中找V1?V7的最短路。 最小费用最大流问题 V1?V7最短路:V1?V4? V6?V7; 最小费用最大流问题 删边V4?V6,路程图中找V1?V7最短路。 最小费用最大流问题 V1?V7最短路:V1?V4?V7; 最小费用最大流问题 删边V4?V7,路程图中找V1?V7最短路。 最小费用最大流问题 V1?V7最短路:V1?V4?V3?V6?V7; 最小费用最大流问题 删边V3?V6,路程图中找V1?V7最短路。 最小费用最大流问题 V1?V7最短路:V1?V4?V3?V5?V7; 最小费用最大流问题 删边V1?V4?V3,路程图中找V1?V7最短路。 最小费用最大流问题 V1?V7最短路:V1?V2?V5?V7; 最小费用最大流问题 删边V2?V5,路程图中找V1?V7最短路。 最小费用最大流问题 V1?V7最短路:V1?V2?V3?V5?V7; 最小费用最大流问题 教材中的做法存在问题：如 排序与统筹优先策略 (Greedy method 贪心算法) 安排问题(收衣服)： 文件的存储； 任务的安排。 安排问题 满足某种要求的安排有没有？有的话,有多少？如有某个定量指标时,最优安排是否存在？是否唯一？如存在,怎么找？这类问题是优化关心的主题。如：著名 的八皇后问题。 存在性问题：设计 一个参观如右3X3的 展览馆的路线,使每 间展馆都到而且不重 复每东西或南北两间 之间都有门可穿过。 (出入口如图示)。　 安排问题一：文件存储 4段乐曲存在一条磁带上,查到并听完每首乐曲的时间：设依次存的乐曲的长度为：a,b,c,d。 找到并听完第一首需时间a; 找到并听完第二首需时间a+b; 找到并听完第三首需时间a+b+c; 找到并听完第四首需时间a+b+c+d; 四共需时间：4a+3b+2c+d,平均找到并听完一首乐曲所需的时间为f(a,b,c,d)=(4a+3b+2c+d)/4。 四首乐曲有4！=24种存放顺序,哪一种次序使f最少？短的存在前：abcd的f(a,b,c,d)=min 否则如ab,则顺序b,a,c,d将使f变大。理由是: f(b,a,c,d)-f(a,b,c,d)=[4b+3a-(4a+3b)]/4=(b-a)/40 安排问题一：文件存储 一般地说：n段乐曲存在一条磁带上,要使平均找到并听完一首乐曲所需的时间最短,就应该尽量先存短的乐曲。 但这没考虑听这些乐曲的概率,最短的存在最前面,但若人们听这首乐曲的概率很小,那按乐曲长短安排存放次序就不一定可取了。 等长的n段乐曲存在一条磁带上,要使平均找到并听完一首乐曲所需的时间最短,要尽量先存收听概率高的乐曲。 安排问题一：文件存储 n段乐曲存在一条磁带上,查到并听完每首乐曲的时间：设要存的乐曲的长度排序后从短到长依次为：t1,t2,…,tn。 找到并听第k首需时间t1+t2+…+ tk;(k=1,2,…,n) 安排问题一：文件存储 n段等长的乐曲存在一条磁带上,查到并听完每首乐曲的时间为t，设所存的乐曲被查听的概率从大到小依次为：p1,p2,…,pn[Σpk =1] 。 找到并听第k首需时间kt;(k=1,2,…,n) 安排问题一：文件存储 n段乐曲存在一条磁带上,记第k首乐曲的长度和收听的概率分别为tk,pk,(k=1..n), 如收听每首乐曲是等可能的,即pk=1/n,就应按tk升序存放；如每首乐曲是等长的,即tk=t,就应按pk降序存放。一般地则应按fk=tk/pk之比升序存放。可使平均找到并听完一首乐曲所需的时间最短。 不妨设这些乐曲是按乐曲的收听概率与长比升序排列的： f1= t1/p1≤f2=t2/p2≤…≤fn=tn/pn。 定理的证明 证明：只须证明交换相邻的两个如fi与fi+1,新的T’与T相比：不会减少。 定理的证明 证