资源描述：
《网络优化在交通中的应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、网络优化在交通中的应用内容最短路问题最大流问题最小费用流问题1、最短路问题1.1最短路问题的LP模型例：求1-8的最短路237184566131052759346248起点111223445566777终点246358273847258边权21365610294547381、最短路问题1.2最短路的求解算法（1）狄克斯拉（Dijkstra）方法：适用于满足所有权系数大于等于0（lij≥0）的网络最短路问题，能求出起点到所有其它点的最短距离；（2）Bellman-Ford算法:适用于求单一起点或终点的最短路（3）Floyd-Warshal
2、l算法：适用于求所有点对的最短距离。1、最短路问题1.3软件实现EXCEL求解Step1插入名称，定义起点、终点、边权以及决策变量Step2建立模型，输入公式Step3规划求解（2）LINGO求解(3)TransCAD1、最短路问题1.4算例设备更新问题例：某人打算购买一辆新轿车，轿车的售价是12万人民币，轿车购买后，每年的各种保险费、养护费等费用如表1所示，如果5年之内，此人将轿车售出，并再购买新车，5年之内的二手车销售价如表2所示，请帮助此人设计一种购车计划，使5年之内用车的费用最少。表1车辆的维护费车龄/年01234费用/万元24
3、5912表2二手车售价车龄/年12345售价/万元76210解：构造网络：用6个点表示各年的开始，各点之间的边表示从左端点开始至右端点开始年的费用，构造如下网络：Cij------第i年开始至j年初的总费用C12=2+12-7=7C13=2+4+12-6=12C14=2+4+5+12-2=21C15=2+4+5+9+12-1=31C16=2+4+5+9+12+12-1=44C23=2+12-7=7C24=2+4+12-6=12C25=2+4+5+12-2=21C26=2+4+5+9+12-1=31C34=2+12-7=7C35=2+4+
4、12-6=12C36=2+4+5+12-2=21C45=2+12-7=7;C46=2+4+12-6=12C56=2+12-7=71、最短路问题1.4算例例2求所有点对之间最短路的Floyd算法见floyd.xls思考：如何用floyd算法进行AON分配2、最大流问题2.1最大流问题的LP模型例：下图中边上的数字表示容量，现要求O至F的最大流。2、最大流问题2.2EXCEL求解Step1插入名称，定义起点、终点、容量以及决策变量Step2建立模型，输入公式公式1＝I4；公式2＝SUMIF(起点,H4,流量)-SUMIF(终点,H4,流量)
5、；公式3＝SUMIF(起点,H5,流量)-SUMIF(终点,H5,流量)；公式4＝SUMIF(起点,H6,流量)-SUMIF(终点,H6,流量)；公式5＝SUMIF(起点,H7,流量)-SUMIF(终点,H7,流量)；公式6＝SUMIF(起点,H8,流量)-SUMIF(终点,H8,流量)；公式7＝SUMIF(起点,H9,流量)-SUMIF(终点,H9,流量)；公式8＝SUMIF(起点,H10,流量)-SUMIF(终点,H10,流)Step3规划求解2、最大流问题2.3思考题例Fly-by-night航空公司必须确定每天可以在阿拉斯加的朱
6、诺和得克萨斯州的达拉斯之间安排多少转接班机。转接班机必须在西雅图停留，然后在洛杉矶或丹佛停留。由于着陆时间有限，所以该公司每天在一对城市之间安排的航班数量将受到限制，如下所示。该公司应该如何使每天从朱诺到达拉斯的航班数量最多？3、最小费用流问题3.1最小费用流问题的LP模型当vf为网络最大流时，上式为最小费用最大流问题例：继续以上例题，增加边的费用，求最小费用最大流。3、最小费用流问题3.2最小费用流的EXCEL求解Step1插入名称，定义起点、终点、流量、容量、费用、网络流、进出和等变量Step2建立模型，输入公式公式1＝SUMPRO
7、DUCT(流量,费用)；公式2＝SUMIF(起点,I4,流量)-SUMIF(终点,I4,流量)；公式3＝SUMIF(起点,I5,流量)-SUMIF(终点,I5,流量)；公式4＝SUMIF(起点,I6,流量)-SUMIF(终点,I6,流量)；公式5＝SUMIF(起点,I7,流量)-SUMIF(终点,I7,流量)；公式6＝SUMIF(起点,I8,流量)-SUMIF(终点,I8,流量)；公式7＝SUMIF(起点,I9,流量)-SUMIF(终点,I9,流量)；公式8＝SUMIF(起点,I10,流量)-SUMIF(终点,I10,流量)；Step3
8、规划求解3、最小费用流问题3.3思考题例：从1至6的高峰小时交通量为900PCU，每个路段的时间和通行能力如图所示，请问如何组织交通使得从1至6的总时间最少？
