数学模型第七章457.doc

第七章 图论模型 7.4 网 络 最 大 流7.4.1引例v1v6v2v3v4v51048535631117图7.4.1如图有一连接某产品的产地v1与销地v6的交通网.每条弧表示运输线路.弧旁的数字表示该运输线的最大通过能力.要求制定一个运输计划使从v1到v6的产品输送量最大.这就是一个网络最大流问题.7.4.2基本概念设有一有向图D=(V,A), 发点是指定的起始点 vsV; 收点是指定的终止点 vtV. 对每一弧(vi,vj)A , 规定一个非负数Cij表示流量的上限称为容量; 指定了发点、收点和各弧容量的有向图D称为网络; 所谓网络上的一个流是指定义在弧集A上的一个实函f = f(vi,vj). fij =f(vi,vj) 称为从vi到vj的流量.若f满足以下2个条件者，则称f为可行流. (1) 容量限制 对每一条弧(vi,vj)A, 0fijCij(2) 平衡条件 (i)对每个中间点viA，流入量等于流出量. （流出vi） (流入vi)(ii) 发点净流出量等于收点净流入量 (称为总流量)最大流问题就是求一个可行流f，使达到最大.网络最大流问题的线性规划模型：对可行流f，若fij=Cij，则称(vi,vj)为饱和弧;对可行流f，若fij=0，则称(vi,vj)为零弧; 根据原网络的每条弧变作一条顺向弧和一条逆向弧，且把顺向弧的容量定义为，逆向弧的容量定义为，这样得到的网络称为原网络D=(V,A,C)关于流f的增量网络，记为.例7.4.1图7.4.2(b) 就是图7.4.2(a) 的一个增量网络.3, 05,14, 14,32, 2st240111333st0图7.4.2(a)(b)7.4.3求网络最大流的方法（1） 增量网络与原网络的关系N(f)的顺向弧的数表示原网络对应弧上最大可增加的流量.N(f)的逆向弧的数表示原网络对应弧上最大可减少的流量.若在N(f)中能找到从s到t的一条路P，且每条弧容量为正数，则称P为f的增广路.令：，则，称为增广量.对原网络的流f作如下调整：, (7.4.1)则是新的可行流且，若N(f)中不存在增广路，则对应的流f已是最大流.（2） 步骤以零流f=0作初始可行流作增量网络N(f)寻找增广路P.若无，则结束.令按（7.4.1）式调整流量，得新流f.转v1v2v3v43,04,05,02,04,0 (a)34 0504 0v1v2v3v4020图7.4.3(b)例 求图7.4.3(a)的网络的最大流, 初始可行流零流=0, 对应的增量网络N(f)如图7.4.3(b)所示. 得增广路P:. v1v2v3v4,求得=4. v1v2v3v43,04,45,42,04,4(a)(b)v1v2v3v430 4140 4002图7.4.4按(7.4.1)式调整流量，得新可行流f ,如图7.4.4(a) 所示, 总流量V(f)=4,对应的增量网络N(f)如图7.4.4(b)所示. 找得增广路P:. v1v3v2v4,求得=2.v1v2v3v43,24,45,22,24,4(a)(b)v1v2v3v410 4320 4202图7.4.5再按（7.4.1）式调整流量，得新可行流f” ,如图7.4.5(a) 所示, 对应的增量网络N(f”如图7.4.5(b)所示.没有增广路, f”已经是最大流, V(f”)=6.7.4.4应用实例-房产商的推销策略某房产商现有6套房（用Xi表示）要出售，现来了7个买主（用Yj表示），分别看中了其中若干套房（如图），假设每个买主至多只买1套房，求房产商使销量最大的推销策略。Y1Y2Y3Y4Y5Y6Y7X1X2X3X4X5X6补充发点S和收点T，定义所有弧的容量都是1，得下图，需要求S到T的最大流。Y1Y2Y3Y4Y5Y6Y7X1X2X3X4X5X6ST可用运筹学求解网络最大流的软件求解，就得房产商使销量最大的推销策略，下图蓝色粗弧都是饱和弧，其他弧是零弧。Y1Y2Y3Y4Y5Y6Y7X1X2X3X4X5X6ST即得房产商最佳的推销策略是：即极力说服买主Y1去买X1, Y2去买X3, Y3去买X4, Y4去买X2, Y5去买X6. 这样能卖出5套房。（当然，此题最优解是不唯一的）注：此题也可以转化为指派问题，方法是先虚拟一套房X7，然后定义Cij，若Yi看中了Xj，则Cij=1，否则Cij=0，当然Ci7=0，目标最大化。应用案例-BMZ公司的最大流问题1.背景 BMZ 公司是欧洲一家生产豪华汽车的制造商。它因为提供优质的服务而获得很好的声誉，保持这个声誉一个很重要的秘诀就是它有着充裕的汽车配件供应，从而能够随时供货给公司众多的经销商和授权维修店。 这些供应件主要存放在公司的配送中心里，这样一有需求就可以立即送货。卡尔(BMZ公司的供应链的经理)优先考虑的是改进这些配送中心的不足之处。 该公司在美国有几个配送中心。但是，离洛杉机中心最近的一个配送中心却坐落离洛杉机 1000 多英里的西雅图。保证洛杉机中心良好的供应是尤为重要的。因此，现在那里的供应不断减少的现状成为了公司高层管理真正关心的问题。 大部分的汽车配件以及新车是在该公司坐落于德国的斯图加特的总厂和新车一起生产的。也就是这家工厂向洛杉机中心供应汽车配件。每月有超过 300000 立方英尺的配件需要运到。现在，下个月需要多得多的数量以补充正在减少的库存。 2.问题 卡尔需要尽快制定一个方案，使得下个月从总厂运送到洛杉机配送中心的供应件尽可能多。他认识到了这是个最大流的问题 一个使得从总厂运送到洛杉机配送中心的配件流最大的问题。因为总厂生产的配件量远远要大于能够运送到配送中心的量，所以，可以运送多少配件的限制条件就是公司配送网络的容量。 这个配送网络如下图。在图中，标有 (ST) 和(LA)的节点分别代表斯图加特的工厂和洛杉机的配送中心。由于工厂所在地有一个铁路运转点，所以首先通过铁路把配件运输到欧洲的三个港口：鹿特丹（RO）波尔图（BO）和里斯本 (LI) ；然后通过船运到美国的港口纽约（NY）或新奥尔良（NO）；最后用卡车送到洛杉机的配送中心。 3.模型描述 STLIBOORONYNOLA507040604050308070（弧旁的方括号里的数字代表该弧的容量：万立方英尺）4.最优方案从 到 运输量 容量 斯图加特（ST）鹿特丹（RO）50 50 斯图加特（ST）波尔图（BO）70 70 斯图加特（ST）里斯本(LI)30 40 鹿特丹（RO）纽约（NY）50 60 波尔图（BO）纽约（NY）30 40 波尔图（BO）新奥尔良(NO)40 50 里斯本(LI)新奥尔良(NO)30 30 纽约（NY）洛杉矶(LA)80 80 新奥尔良(NO)洛杉矶(LA)70 70 总运输量 150 7.5统筹方法统筹方法是一种研究如何对工程计划进行合理组织、统筹安排使其发挥最大效益的方法.常用工序流线图对各工序的关系进行描述.7.5.1. 工序流线图工序流线图是用于描述各工序的逻辑关系与工程进度的一种有向网路图.绘图规则如下：（1）用箭号表示工序，箭号旁可用数字表示该工序所需时间;（2）用小圆表示事项（工序开工或完工的时刻）, 箭尾处为开工事项, 箭头处为完工事项;（3）全部事项从小到大进行编号，不得重复;（4）任一工序的开工事项编号小于完工事项编号，如 ;（5）不同的工序不得使用两个相同的相关事项，如图7.5.1是不允许的;从而可用（i,j）表示开工事项编号为i, 完工事项编号为j的工序;（6）必要时可使用虚工序（无须实际执行的工序，工时为0），用虚箭号 表示，如图7.5.2所示;AB46图7.5.1BA465图7.5.2（7）一个工程只有一个始点与一个终点.例7.5.1 某工厂改建工程由下列6道工序构成:A:拆旧厂房;B:工程设计;C:采购设备,紧前工序(紧接本工序之前的工序)是B;D:厂房土建, 紧前工序是A与B;E:设备安装, 紧前工序是C与D;F:设备调试, 紧前工序是E.123456ABCDEF图7.5.3本工程可用图7.5.3的工序流线图来描述作工序流线图时我们要小心虚箭号的合理使用,否则容易出错.例7.5.2 现有一工程：代号ABCDEFGH紧前工序ABBBC，DC，EF，G工序时间13162424作出图7.5.4.图7.5.4 请注意, 图7.5.5的作法是错的.图7.5.5 这样画的话,工序D也变为工序G的紧前工序了,与原题意不符.提醒:使用虚工序时尽量避免多个同向相连7.5.2工序流线图的时间参数设工序流线图中始点编号为1，终点编号为n.以下引进几个记号.TE总工期，等于图中终点的最早完工时间，也等于终点的最迟完工时间;工序（i,j）的耗用工时;tE(k)事项k的最早时间，即以事项k为开工事项的工序的最早可以开工时间，也即它前面全部工序都已完工的时间.递推公式为 (7.5.1)如图7.5.6所示.若已算得tE(2)=3, tE(3)=2又知w24=2,w34=4从而按(7.5.1)式算得tE(4)=max3+2,2+4=6.tE(1)=0tE(2)=3tE(3)=2tE(4)=6图7.5.6 tL(k)事项k的最迟时间，即以事项k为完工事项的工序的最迟必须完工时间（以不耽误总工期而言）,递推公式为 (7.5.2)如图7.5.7所示.若已算得tL(8)=5, tL(9)=6又知w78=3,w79=2从而按(7.5.2)式算得tL(7)=min5-3,6-2=2.7tL(7)=2tL(8)=5tL(9)=6图7.5.7R(i,j)-工序（i,j）的总时差（指不误总工期条件下的最大机动时间）.定义 , (7.5.3) 如果，w45=3, 则R(i,j)=8-2-3=3ktEtL图7.5.8 若图不太复杂,则时间参数tE与tL可直接在图上计算, 称为图算法. 把每个事项分为3部分，分别表示编号、最早时间和最迟时间,如图7.5.8.先按编号从小到大计算tE(k)，再按编号从大到小算tL(k); 如图7.5.9所示.图7.5.97.5.3 关键路工序流线图中按箭头方向从始点到终点的一条顺向通道称为路;图7.5.9中有四条路.路上各工序时间之和称为路长;图中最长的路称为关键路; 关键路上的工序称为关键工序.注意,每个工序流线图都一定有关键路，关键路的长就是全工程的完工 的总工时; 关键路可能不是唯一的;要想工程提前完工，只有缩短关键工序的工时.故寻找工序流线图的关键路,在工程项目的管理中,有十分重要的作用.我们可以用以下方法确定关键路. 由于关键路上的各工序都是不停留地一道紧接一道进行.才能保证不误总工期.从而关键路上各事项必满足tL(k)=tE(k).故只须把图中全部满足此关系的事项连接起来就得关键路.在图7.5.9中, 关键路为，总工期为41天.注：一道工序是关键工序的充要条件是总时差为0.再看一例：根据下列资料绘制网络图，计算各项时间参数，并确定关键路线. 工 序紧前工序工 时工 序紧前工序工 时AG , M3GB , C4BH4H-7C-7IA , L3DL3KF , I5EC5LB , C6FA , E5MC41023231128289182081720718186181851515411113711277100H , 7C , 7B , 4M , 4G , 4L , 6A , 3E , 5I , 3F , 5D , 3K , 5解：图与参数为关键路线如图中粗线所示。总工期为28.7.7 匹配问题 设有X、Y、Z三家公司，各有一个职位空缺。三个求职者Alice, Bob, Charles希望得到一个职位。假设X公司雇佣Charles，Y公司雇佣Alice，Z公司雇佣Bob。我们可用图7.7.1表示这一结果。图 7.7.1XYZAliceBobChales二部图(bipartite graph)：若一个图G=(V, E)的顶点集V可分为两个互不相交的子集V1和V2，且G中任何一条边e的一个顶点属于V1另一个顶点属于V2，则称G是一个二部图(bipartite graph)。匹配：设，若M中任两条边都没有公共顶点，则称M是G的一个匹配。最大匹配：G中边数最多的匹配。ABab婚姻介绍所需要为顾客（n位男士和n位女士）推荐合适的配偶。推荐是基于每个人的偏好，每个顾客都要给出他们对异性的优先顺序。障碍对：假设给男士a指定配偶女士A, 而给男士b指定配偶女士B, 但在a的心目中，B比A更好，而在B的心目中，a比b更好. 就是说，a和B更愿意配成一对，那么a和B称为该匹配中的一个障碍对。（注意，在该匹配中，a和B并没有配成一对）稳定匹配(婚姻)：如果一个匹配中没有障碍对，则称该匹配是稳定的。GS算法：（用于求稳定匹配）(1962年，美国数学家戈尔（Gale）和夏普利（Shapley）就解决了)首先要给出男士对女士的偏好矩阵和女士对男士的偏好矩阵（用排序或评分）.在第一轮循环中, 每位男士向他最喜欢的女士求婚. 而每位女士则选择向她求婚的男士中, 她最喜欢的一个男士作为暂时的配偶. 没有人求婚的女士等待下一轮.在下一轮循环中, 已经有暂时配偶的男士什么也不做. 每一个没有配偶的男士再向他的偏好顺序表里排在最前面而没有拒绝过他的女士求婚. 而每位女士则选择向她求婚的男士(包括原来的暂时配偶)中,她最喜欢的一位男士作为暂时的配偶. 如此循环，直到所有的男士都有配偶时, 算法结束.例 设男士a，b，c与女士A，B，C的偏好矩阵为顺序abcABC一BAAbcb二ACBaac三CBCcba以下用 表示男士向女士求婚或女士暂时接纳男士第1轮aBbA cAAb拒cBaC空第2轮a停b停cBAbBc拒aC空第3轮aAb停c停Ab拒aBcC空第4轮aCb停c停AbBcCa这就得到稳定匹配ABCabc稳定匹配是不是最满意的匹配？把偏好排序换成评分，分值越大表示越偏好男士对女士评分女士对男士评分ABCABCa231a221b312b313c321c132ABCabc上面的稳定匹配的总分S1=(3