第七讲网络模型ppt课件

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

2、p;T AT&T公司要处置大约公司要处置大约2.92.9亿各种各样的亿各种各样的呼叫。呼叫。AT&T公司的最优恢复才干公司的最优恢复才干n能源损耗、自然灾祸、光缆断裂或其他的一些事件能源损耗、自然灾祸、光缆断裂或其他的一些事件会使部分传输网络瘫痪。当这样的事件发生时，包会使部分传输网络瘫痪。当这样的事件发生时，包含恢复性网络的备用才干必需立刻起用以便效力不含恢复性网络的备用才干必需立刻起用以便效力不被干扰。关于恢复性网络的重要问题包括：多少的被干扰。关于恢复性网络的重要问题包括：多少的备用才干才够？应位于何处？在备用才干才够？应位于何处？在20192019年，年，AT&

3、TAT&T公司公司组织了一个组织了一个“其他网络任务组从事这些问题的研讨其他网络任务组从事这些问题的研讨。AT&T公司的最优恢复才干公司的最优恢复才干n为了最优恢复才干，该任务组开展了一个大型的为了最优恢复才干，该任务组开展了一个大型的直线型规划模型。模型中的一个分支问题涉及无直线型规划模型。模型中的一个分支问题涉及无论何时传输网络范围内出现错误衔接，原线路与论何时传输网络范围内出现错误衔接，原线路与目的地之间最短道路的决议问题。另外一个问题目的地之间最短道路的决议问题。另外一个问题是解答最大流量问题，即找到从每一个转换器到是解答最大流量问题，即找到从每一个转换器到灾难恢复转换

4、器的最正确恢复道路。灾难恢复转换器的最正确恢复道路。主要内容n最短途径问题n最小支撑树问题n最大流问题最短途径问题 Gorman建筑公司n目的：确定一个网络内两个节点间的最短途径或道路。目的：确定一个网络内两个节点间的最短途径或道路。nGorman公司有一些建筑遍及在公司有一些建筑遍及在3个县区内。由于从个县区内。由于从Gorman的办事处运送人力、设备和供应物资到这些的办事处运送人力、设备和供应物资到这些建筑地点需求好几天的行程，所以与运输活动相关的本建筑地点需求好几天的行程，所以与运输活动相关的本钱是宏大的。钱是宏大的。 Gorman的办事处和每一个建筑地点之的办事处和每一个建筑地点之间的

5、行程选择可以用公路网络来描画，如图。间的行程选择可以用公路网络来描画，如图。nGorman想要确定一条可以最小化想要确定一条可以最小化Gorman的办事处的办事处坐落在节点坐落在节点1和坐落在节点和坐落在节点6的建筑地点间的总行的建筑地点间的总行程间隔的途径。程间隔的途径。123456252031456447办事处办事处Gorman最短途径问题的转运网络最短途径问题的转运网络123456252031456447起始起始节点节点目的目的节点节点定义决策变量定义决策变量上的弧线不在该最短路径至节点从节点的最短路径上到节点的弧线在从节点至节点从节点jijixij0611模型模型nMIN 25x12+

6、20 x13+3x23+3x32+5x24+5x42+14x26+6x35+6x53+4x45+4x54+4x46+7x56n S.T.n 1) 1x12+1x13=1n 2) -1x12+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起始起始节点

7、节点目的目的节点节点戈曼建筑公司面临的情况n戈曼总部拥有的几个建筑工程工程遍及于一个三戈曼总部拥有的几个建筑工程工程遍及于一个三个县区大的区域内。建筑工地有时位于戈曼总部个县区大的区域内。建筑工地有时位于戈曼总部远达远达5050英里的地方。在总部与工地之间需求每天英里的地方。在总部与工地之间需求每天几次运送员工、设备和补给，其与运输活动有关几次运送员工、设备和补给，其与运输活动有关的本钱相当高。对于任一个指定的建筑工地，在的本钱相当高。对于任一个指定的建筑工地，在工地与总部的运输道路可被看成一个由小路、街工地与总部的运输道路可被看成一个由小路、街道和公路组成的网络。在图道和公路组成的网络。在图

8、9-19-1中展现的网络描中展现的网络描画了来往与戈曼总部画了来往与戈曼总部6 6个最新建筑工地的运输道个最新建筑工地的运输道路。路。路程单位：英里21103652461547653417戈曼总部节点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，S1

9、0，115，113，314，3图9-6 戈曼网络节点2和5的新暂时标识211036524615476534170，S10，113，314，319，230，2图9-7 戈曼网络节点2的永久标识以及节点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，31

10、4，318，516，522，6图9-10 戈曼网络节点4的永久标识211036524615476534170，S10，113，314，318，516，522，6图9-11 戈曼网络一切节点被永久标识节点从节点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直接到达的暂时标识节点数。

11、直接到达的暂时标识节点数。n 第三步：确定具有最小间隔值的暂时标识节点并且宣布该节第三步：确定具有最小间隔值的暂时标识节点并且宣布该节点被永久标识。假设一切节点都被永久标识，跳到第五步。点被永久标识。假设一切节点都被永久标识，跳到第五步。n第四步：思索一切在第三步中已确认的节点所能直接到达的第四步：思索一切在第三步中已确认的节点所能直接到达的未被永久标识的节点。未被永久标识的节点。n第五步：永久标识既认定了从节点第五步：永久标识既认定了从节点1 1到每个节点的最短道路也到每个节点的最短道路也认定了最短道路上前一个节点值。认定了最短道路上前一个节点值。案例：救护车行程安排案例：救护车行程安排 宾

12、厄姆顿市两大主要医院：西部医疗和宾厄姆顿群众，西部医疗坐落于城市的西南部，而宾厄姆顿群众位于东北部。 鲍勃仲斯，西部医疗的医院主管，不断在和宾厄姆顿群众的主管玛格丽特约翰逊讨论救护车的时间和行程安排。两个客观都感到某些类型需求改良，以便更好地协调两个医院间的救护效力，以便他们能提供尽能够快速的紧急效力。 经过一中心集散系统处置一切救护效力的提议正在思索之中。此集散系统会自动地把呼叫转到可以提供最快效力的医院。在研讨此提议的过程中，一个由两个医院员工组成的任务组决议其最好方法是把城市分为20个效力区。在此提到的构造中，西部医疗将会位于1区而宾厄姆顿大众位于20区。展现此20区域的布置图以及相关区

13、域间的往返时间如图9-20所示。245368791011191617181514131212061079878784555635796577655466658476454图9-20 救护的效力网络 根据所提出的操作程序，新的紧急呼叫将会以区号划分。也就是说最接近该区的医院会派出救护车来完效果劳。然而，假设最近医疗一切救护车都在运用之中，此效力将由另一个医院完成。无论哪一个医院担任效力，要求紧急效力的个人将会被带到最近的医院。 为了使此协调性效力尽能够高效，救护车司机必需预 先知道到达每一区的最短道路。需求知道救护者应被带到哪个医院以及最快到达该院的道路。管理报告 为两个医院主管预备一个描画他本

14、人对此问题的分析报告。在他的报告陈说中，包括以下几点。 1.一张给调度员的划分城市医院救护效力区的地图。 2.一张给西部医疗救护车司机提供从西部医疗到城市中每一个区域需求最少时间道路的图，包含宾厄姆顿。还包括一张可以通知西部医疗司机此人应被带到哪个医院以及应走的道路。3.一张给宾厄姆顿救护车司机提供从宾厄姆顿到城市中每一个区域的最少时间道路，包含西部医疗。还包括一张通知宾厄姆顿救护车司机此人应被带到哪个医院以及应走的道路。4.包括一些关于此系统如何经过改动而把一天中出现的交通情况以及由于暂时性道路建立而要改动交通道路思索进去的建议。扩展运用n下面网络图中的下面网络图中的5 5个节点表示一个个节

15、点表示一个4 4年期的时间段年期的时间段内各年的时间点。每个节点表示的是做出坚持或内各年的时间点。每个节点表示的是做出坚持或替代公司电脑决议的时间。假设断定交换电脑设替代公司电脑决议的时间。假设断定交换电脑设备，那么同时也要决议新设备要用多久，从节点备，那么同时也要决议新设备要用多久，从节点0 0到节点到节点1 1的弧代表持有现有设备的弧代表持有现有设备1 1年并且到年底年并且到年底交换，从节点交换，从节点0 0到节点到节点2 2的弧表示坚持现有设备的弧表示坚持现有设备2 2年并且到第年并且到第2 2年末交换。弧上的数字表示与交换年末交换。弧上的数字表示与交换设备有关的总本钱。这些本钱包括打折

16、后的购买设备有关的总本钱。这些本钱包括打折后的购买价、旧设备换新的折价、运营本钱和维修本钱。价、旧设备换新的折价、运营本钱和维修本钱。请确定请确定4 4年内的最小设备交换本钱。年内的最小设备交换本钱。最小支撑树问题最小支撑树问题n以用弧总长最小化的方式经过网络线路到达一切以用弧总长最小化的方式经过网络线路到达一切网络中的节点。网络中的节点。区域性电脑中心碰到的通讯系统设计问题n西南部区域电脑中心装配了公用电脑通讯线以此西南部区域电脑中心装配了公用电脑通讯线以此经过一个新的中心电脑来和经过一个新的中心电脑来和5 5个通讯卫星运用商个通讯卫星运用商联络。公司也会装配这个新的通讯网络。然而，联络。公

17、司也会装配这个新的通讯网络。然而，装配的破费很大。为了减少本钱，中心的管理集装配的破费很大。为了减少本钱，中心的管理集团想让这个新的通讯线路尽能够的短。虽然中心团想让这个新的通讯线路尽能够的短。虽然中心电脑可以与每个运用商直接联络，但假设给一些电脑可以与每个运用商直接联络，但假设给一些运用者装一根直达线同时让一些其他运用者经过运用者装一根直达线同时让一些其他运用者经过与那些已与此系统相连的用户衔接而进入，那就与那些已与此系统相连的用户衔接而进入，那就会更加经济实惠。有关此问题的网络以及能够的会更加经济实惠。有关此问题的网络以及能够的可选衔接和间隔等数据如以下图。可选衔接和间隔等数据如以下图。区

18、域电脑中心1526342040403030504030402010两地之间通讯线路的英里数最小支撑树法n一个具有一个具有N N个节点的支撑树是一套由个节点的支撑树是一套由N-1N-1条衔接每一节条衔接每一节点与其他节点的弧组成的。点与其他节点的弧组成的。n此方法的步骤如下所示：此方法的步骤如下所示：n第一步：以任一节点开场，把它与所用规范下的例第一步：以任一节点开场，把它与所用规范下的例如时间、本钱或间隔等最近一点相连。两个点被看如时间、本钱或间隔等最近一点相连。两个点被看成是两相连节点，剩下的为未相连节点。成是两相连节点，剩下的为未相连节点。n第二步：确认离某一相连节点最近的未相连节点。假第

19、二步：确认离某一相连节点最近的未相连节点。假设有两个或两个以上的节点符合条件，那么恣意选择设有两个或两个以上的节点符合条件，那么恣意选择一点。然后，把此新节点参与到整套相连节点中。反一点。然后，把此新节点参与到整套相连节点中。反复此过程直到一切节点被衔接为止复此过程直到一切节点被衔接为止152634204040303050403040201015263420404030305040304020101526342040403030504030402010软件求解课堂练习n中西部中心大学正在安装一个电子邮件系统。下中西部中心大学正在安装一个电子邮件系统。下面的网络图展现了办公室之间可以实现的能够的

20、面的网络图展现了办公室之间可以实现的能够的电子链接情况。办公室之间的间隔以电子链接情况。办公室之间的间隔以1 0001 000英尺英尺为单位。设计一个办公室联络系统，使一切办公为单位。设计一个办公室联络系统，使一切办公室都能运用电子邮件效力，要求他的设计能使衔室都能运用电子邮件效力，要求他的设计能使衔接接8 8个办公室的线路最短。个办公室的线路最短。最大流问题最大流问题n目的目的确定最大数量的流量交通工具、信息、确定最大数量的流量交通工具、信息、液体等，它们可以在一个给定时期内进入和退液体等，它们可以在一个给定时期内进入和退出一个网络系统。出一个网络系统。n经过网络的一切弧线尽能够有效地传送流

21、量。经过网络的一切弧线尽能够有效地传送流量。n流通才干流通才干弧线上流量的最大或最高限制。弧线上流量的最大或最高限制。案例案例辛辛那提和俄亥俄的南北向洲际高辛辛那提和俄亥俄的南北向洲际高速公路系统。速公路系统。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-