第七讲+网络模型.ppt

《第七讲+网络模型.ppt》由会员分享，可在线阅读，更多相关《第七讲+网络模型.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七讲 网络模型物流管理系 薛伟霞AT&T公司的最优恢复能力公司的最优恢复能力nAT&TAT&T公司是一个提供远距离声讯数据、图象、无公司是一个提供远距离声讯数据、图象、无线、卫星和网络服务的全球性电讯公司。该公司线、卫星和网络服务的全球性电讯公司。该公司运用高级的转换和传输设备向运用高级的转换和传输设备向80008000万以上的客户万以上的客户提供服务。在美国本土的大陆上，提供服务。在美国本土的大陆上，AT&TAT&T公司的传公司的传输网络由输网络由4000040000英里以上的钎维光缆组成。在高英里以上的钎维光缆组成。在高峰时候，峰时候，AT&TAT&T公司要处理大约公司要处理大约2.92

2、.9亿各种各样的亿各种各样的呼叫。呼叫。AT&T公司的最优恢复能力公司的最优恢复能力n能源损耗、自然灾害、光缆断裂或其他的一些事件能源损耗、自然灾害、光缆断裂或其他的一些事件会使部分传输网络瘫痪。当这样的事件发生时，包会使部分传输网络瘫痪。当这样的事件发生时，包含恢复性网络的备用能力必须立即起用以便服务不含恢复性网络的备用能力必须立即起用以便服务不被干扰。关于恢复性网络的重要问题包括：多少的被干扰。关于恢复性网络的重要问题包括：多少的备用能力才够？应位于何处？在备用能力才够？应位于何处？在19971997年，年，AT&TAT&T公司公司组织了一个组织了一个“其他网络其他网络”工作组从事这些问题

3、的研工作组从事这些问题的研究。究。AT&T公司的最优恢复能力公司的最优恢复能力n为了最优恢复能力，该工作组发展了一个大型的为了最优恢复能力，该工作组发展了一个大型的直线型规划模型。模型中的一个分支问题涉及无直线型规划模型。模型中的一个分支问题涉及无论何时传输网络范围内出现错误连接，原线路与论何时传输网络范围内出现错误连接，原线路与目的地之间最短路线的决定问题。另外一个问题目的地之间最短路线的决定问题。另外一个问题是解答最大流量问题，即找到从每一个转换器到是解答最大流量问题，即找到从每一个转换器到灾难恢复转换器的最佳恢复路线。灾难恢复转换器的最佳恢复路线。主要内容n最短路径问题n最小支撑树问题n

4、最大流问题最短路径问题 Gorman建筑公司n目标：确定一个网络内两个节点间的最短路径或路线。目标：确定一个网络内两个节点间的最短路径或路线。nGorman公司有一些建筑遍布在公司有一些建筑遍布在3个县区内。由于从个县区内。由于从Gorman的办事处运送人力、设备和供应物资到这些的办事处运送人力、设备和供应物资到这些建筑地点需要好几天的行程，所以与运输活动相关的成建筑地点需要好几天的行程，所以与运输活动相关的成本是巨大的。本是巨大的。Gorman的办事处和每一个建筑地点之的办事处和每一个建筑地点之间的行程选择可以用公路网络来描述，如图。间的行程选择可以用公路网络来描述，如图。nGorman想要

5、确定一条能够最小化想要确定一条能够最小化Gorman的办事处的办事处（坐落在节点（坐落在节点1）和坐落在节点）和坐落在节点6的建筑地点间的总行的建筑地点间的总行程距离的路径。程距离的路径。123456252031456447办事处办事处Gorman最短路径问题的转运网络最短路径问题的转运网络123456252031456447起始起始节点节点目标目标节点节点定义决策变量定义决策变量模型模型nMIN 25x12+20 x13+3x23+3x32+5x24+5x42+14x26+6x35+6x53+4x45+4x54+4x46+7x56n S.T.n 1)1x12+1x13=1n 2)-1x12+

6、1x23-1x32+1x24-1x42+1x26=0n 3)-1x13-1x23+1x32+1x35-1x53=0n 4)-1x24+1x42+1x45-1x54+1x46=0n 5)-1x35+1x53-1x45+1x54+1x56=0n 6)1x26+1x46+1x56=1软件求解n线性规划模型n最短路径求解结果求解结果Gorman最短路径最短路径123456252031456447起始起始节点节点目标目标节点节点戈曼建筑公司面临的情况n戈曼总部拥有的几个建筑工程项目遍布于一个三戈曼总部拥有的几个建筑工程项目遍布于一个三个县区大的区域内。建筑工地有时位于戈曼总部个县区大的区域内。建筑工地有

7、时位于戈曼总部远达远达5050英里的地方。在总部与工地之间需要每天英里的地方。在总部与工地之间需要每天几次运送员工、设备和补给，其与运输活动有关几次运送员工、设备和补给，其与运输活动有关的成本相当高。对于任一个指定的建筑工地，在的成本相当高。对于任一个指定的建筑工地，在工地与总部的运输路线可被看成一个由小路、街工地与总部的运输路线可被看成一个由小路、街道和公路组成的网络。在图道和公路组成的网络。在图9-19-1中展示的网络描中展示的网络描述了来往与戈曼总部述了来往与戈曼总部6 6个最新建筑工地的运输路个最新建筑工地的运输路线。线。路程单位：英里21103652461547653417戈曼总部节

8、点20.4从节点1到此节点的距离为20从节点1到该节点路线上前一个节点为节点4节点标识图9-2 节点标识示例211036524615476534170，S图9-4 戈曼网络节点2和3的暂时网络标识211036524615476534170，S10，115，1图9-5 戈曼网络节点3的永久标识211036524615476534170，S10，115，1211036524615476534170，S10，115，113，314，3图9-6 戈曼网络节点2和5的新暂时标识211036524615476534170，S10，113，314，319，230，2图9-7 戈曼网络节点2的永久标识以及节点

9、4和7的新暂时标识211036524615476534170，S10，113，314，319，230，218，516，5图9-8 戈曼网络节点5的永久标识以及节点4和6的新暂时标识211036524615476534170，S10，113，314，330，218，516，522，6图9-9 戈曼网络节点6的永久标识以及节点7的新暂时标识211036524615476534170，S10，113，314，318，516，522，6图9-10 戈曼网络节点4的永久标识211036524615476534170，S10，113，314，318，516，522，6图9-11 戈曼网络所有节点被永久标识

10、节点从节点1的最短路线距离（英里）2345671-31-3-21-3-5-41-3-51-3-5-61-3-5-6-7131018161422标识法n 第一步：给节点第一步：给节点1 1永久标识永久标识00，SS。“0 0”指从节点指从节点1 1到其自到其自己的距离为零。己的距离为零。“S S”指节点指节点1 1为起始点。为起始点。n 第二步：计算可从节点第二步：计算可从节点1 1直接到达的暂时标识节点数。直接到达的暂时标识节点数。n 第三步：确定具有最小距离值的暂时标识节点并且宣布该节第三步：确定具有最小距离值的暂时标识节点并且宣布该节点被永久标识。如果所有节点都被永久标识，跳到第五步。点被

11、永久标识。如果所有节点都被永久标识，跳到第五步。n第四步：考虑所有在第三步中已确认的节点所能直接到达的第四步：考虑所有在第三步中已确认的节点所能直接到达的未被永久标识的节点。未被永久标识的节点。n第五步：永久标识既认定了从节点第五步：永久标识既认定了从节点1 1到每个节点的最短路线也到每个节点的最短路线也认定了最短路线上前一个节点值。认定了最短路线上前一个节点值。案例：救护车行程安排案例：救护车行程安排 宾厄姆顿市两大主要医院：西部医疗和宾厄姆顿大众，西部医疗坐落于城市的西南部，而宾厄姆顿大众位于东北部。鲍勃仲斯，西部医疗的医院主管，一直在和宾厄姆顿大众的主管玛格丽特约翰逊讨论救护车的时间和行

12、程安排。两个主观都感到某些类型需要改进，以便更好地协调两个医院间的救护服务，以便他们能提供尽可能快速的紧急服务。通过一中心集散系统处理所有救护服务的提议正在考虑之中。此集散系统会自动地把呼叫转到能够提供最快服务的医院。在研究此提议的过程中，一个由两个医院员工组成的工作组决定其最好方法是把城市分为20个服务区。在此提到的结构中，西部医疗将会位于1区而宾厄姆顿大众位于20区。展示此20区域的布置图以及相关区域间的往返时间如图9-20所示。245368791011191617181514131212061079878784555635796577655466658476454图9-20 救护的服务网

13、络 根据所提出的操作程序，新的紧急呼叫将会以区号划分。也就是说最靠近该区的医院会派出救护车来完成服务。然而，如果最近医疗所有救护车都在使用之中，此服务将由另一个医院完成。无论哪一个医院负责服务，要求紧急服务的个人将会被带到最近的医院。为了使此协调性服务尽可能高效，救护车司机必须预 先知道到达每一区的最短路线。需要知道救护者应被带到哪个医院以及最快到达该院的路线。管理报告管理报告 为两个医院主管准备一个描述你自己对此问题的分析报告。在你的报告陈述中，包括以下几点。1.一张给调度员的划分城市医院救护服务区的地图。2.一张给西部医疗救护车司机提供从西部医疗到城市中每一个区域需要最少时间路线的图，包含

14、宾厄姆顿。还包括一张可以告诉西部医疗司机此人应被带到哪个医院以及应走的路线。3.一张给宾厄姆顿救护车司机提供从宾厄姆顿到城市中每一个区域的最少时间路线，包含西部医疗。还包括一张告诉宾厄姆顿救护车司机此人应被带到哪个医院以及应走的路线。4.包括一些关于此系统如何通过改动而把一天中出现的交通情况以及由于暂时性道路建设而要改变交通路线考虑进去的建议。扩展应用n下面网络图中的下面网络图中的5 5个节点表示一个个节点表示一个4 4年期的时间段年期的时间段内各年的时间点。每个节点表示的是做出保持或内各年的时间点。每个节点表示的是做出保持或替代公司电脑决定的时间。如果决定替换电脑设替代公司电脑决定的时间。如

15、果决定替换电脑设备，那么同时也要决定新设备要用多久，从节点备，那么同时也要决定新设备要用多久，从节点0 0到节点到节点1 1的弧代表持有现有设备的弧代表持有现有设备1 1年并且到年底年并且到年底替换，从节点替换，从节点0 0到节点到节点2 2的弧表示保持现有设备的弧表示保持现有设备2 2年并且到第年并且到第2 2年末替换。弧上的数字表示与替换年末替换。弧上的数字表示与替换设备有关的总成本。这些成本包括打折后的购买设备有关的总成本。这些成本包括打折后的购买价、旧设备换新的折价、运营成本和维修成本。价、旧设备换新的折价、运营成本和维修成本。请确定请确定4 4年内的最小设备替换成本。年内的最小设备替

16、换成本。最小支撑树问题最小支撑树问题n以用弧总长最小化的方式通过网络线路到达所有以用弧总长最小化的方式通过网络线路到达所有网络中的节点。网络中的节点。区域性电脑中心碰到的通信系统设计问题n西南部区域电脑中心装配了专用电脑通讯线以此西南部区域电脑中心装配了专用电脑通讯线以此通过一个新的中心电脑来和通过一个新的中心电脑来和5 5个通信卫星使用商个通信卫星使用商联系。电话公司也会装配这个新的通信网络。然联系。电话公司也会装配这个新的通信网络。然而，装配的花费很大。为了减少成本，中心的管而，装配的花费很大。为了减少成本，中心的管理集团想让这个新的通信线路尽可能的短。尽管理集团想让这个新的通信线路尽可能

17、的短。尽管中心电脑可以与每个使用商直接联系，但如果给中心电脑可以与每个使用商直接联系，但如果给一些使用者装一根直达线同时让一些其他使用者一些使用者装一根直达线同时让一些其他使用者通过与那些已与此系统相连的用户连接而进入，通过与那些已与此系统相连的用户连接而进入，那就会更加经济实惠。有关此问题的网络以及可那就会更加经济实惠。有关此问题的网络以及可能的可选连接和距离等数据如下图。能的可选连接和距离等数据如下图。区域电脑中心1526342040403030504030402010两地之间通信线路的英里数最小支撑树法n一个具有一个具有N N个节点的支撑树是一套由个节点的支撑树是一套由N-1N-1条连接

18、每一节条连接每一节点与其他节点的弧组成的。点与其他节点的弧组成的。n此方法的步骤如下所示：此方法的步骤如下所示：n第一步：以任一节点开始，把它与所用标准下的（例第一步：以任一节点开始，把它与所用标准下的（例如时间、成本或距离等）最近一点相连。两个点被看如时间、成本或距离等）最近一点相连。两个点被看成是两相连节点，剩下的为未相连节点。成是两相连节点，剩下的为未相连节点。n第二步：确认离某一相连节点最近的未相连节点。如第二步：确认离某一相连节点最近的未相连节点。如果有两个或两个以上的节点符合条件，那么任意选择果有两个或两个以上的节点符合条件，那么任意选择一点。然后，把此新节点加入到整套相连节点中。

19、重一点。然后，把此新节点加入到整套相连节点中。重复此过程直到所有节点被连接为止复此过程直到所有节点被连接为止152634204040303050403040201015263420404030305040304020101526342040403030504030402010软件求解课堂练习n中西部中心大学正在安装一个电子邮件系统。下中西部中心大学正在安装一个电子邮件系统。下面的网络图展示了办公室之间可以实现的可能的面的网络图展示了办公室之间可以实现的可能的电子链接情况。办公室之间的距离以电子链接情况。办公室之间的距离以1 0001 000英尺英尺为单位。设计一个办公室联络系统，使所有办公为单

20、位。设计一个办公室联络系统，使所有办公室都能使用电子邮件服务，要求你的设计能使连室都能使用电子邮件服务，要求你的设计能使连接接8 8个办公室的线路最短。个办公室的线路最短。最大流问题最大流问题n目标目标确定最大数量的流量（交通工具、信息、确定最大数量的流量（交通工具、信息、液体等），它们能够在一个给定时期内进入和退液体等），它们能够在一个给定时期内进入和退出一个网络系统。出一个网络系统。n通过网络的所有弧线尽可能有效地传送流量。通过网络的所有弧线尽可能有效地传送流量。n流通能力流通能力弧线上流量的最大或最高限制。弧线上流量的最大或最高限制。案例案例辛辛那提和俄亥俄的南北向洲际高速公路系统。辛辛

21、那提和俄亥俄的南北向洲际高速公路系统。n南北向的交通流量在高峰时期会达到南北向的交通流量在高峰时期会达到1500015000辆车辆车的水平。由于夏季高速公路的维护计划需要暂时的水平。由于夏季高速公路的维护计划需要暂时封锁道路并限制最低的时速，交通规划委员会已封锁道路并限制最低的时速，交通规划委员会已经提出了穿过辛辛那提的可替代路径的网络图。经提出了穿过辛辛那提的可替代路径的网络图。这些可替代的路径既包括其他的高速公路，也包这些可替代的路径既包括其他的高速公路，也包括城市街道。由于时速限制以及交通模式的不同，括城市街道。由于时速限制以及交通模式的不同，所以在应用的特定街道和公路上的流通能力是不所

22、以在应用的特定街道和公路上的流通能力是不一样的。标有弧流通能力的提议网络如下图。一样的。标有弧流通能力的提议网络如下图。进入辛辛那提(北)离开辛辛那提(南)314326575375351187226修改后的网络修改后的网络143265753753511872263决策变量n xij=从节点i到节点j的车流量模型Max x71S.T.x12+x13+x14-x71=0 节点1 x23+x25-x12-x32=0 节点2 x32+x34+x35+x36-x13-x23=0 节点3 x46-x14-x34=0 节点4 x56+x57-x25-x35-x65=0 节点5 x65+x67-x36-x46

23、-x56=0 节点6 x71-x57-x67=0 节点7流通能力x12=5 x13=6 x14=5x23=2 x25=3x32=2 x34=3 x35=3 x36=7x46=5 x56=1 x57=8x65=1 x67=7Management Scientist求解结果521763453233536177最大流量1小时14000辆进入辛辛那提(北)离开辛辛那提(南)31432657537535118722652633353177练习n高价油公司拥有一个从采集地到几个储存点之间传送石高价油公司拥有一个从采集地到几个储存点之间传送石油的管道网络系统。其部分网络系统如下图所示：不同油的管道网络系统。

24、其部分网络系统如下图所示：不同的管道型号，其流量也不同。通过有选择地开关部分的的管道型号，其流量也不同。通过有选择地开关部分的管道网络，公司可以提供任何储藏地。管道网络，公司可以提供任何储藏地。nA.如果该公司想要充分利用此系统能力，以供给仓储地如果该公司想要充分利用此系统能力，以供给仓储地7，那么将需要多长时间以满足地点，那么将需要多长时间以满足地点7的的100 000加仑加仑的需要。此管道系统的最大流量是多少？的需要。此管道系统的最大流量是多少？nB.如果管道如果管道2与管道与管道3之间出现断裂并被关闭，那么此系之间出现断裂并被关闭，那么此系统的最大流量是多少？传送统的最大流量是多少？传送100 000加仑到地点加仑到地点7需要需要多长时间？多长时间？12356476源头源头6223333222211255流量：每小时5000加仑