图与网络优化问题课件.ppt

《图与网络优化问题课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7讲图与网络优化问题1第7讲图与网络优化问题1.引例：奔驰公司的配送网络2.图论基础3.最小费用流问题4.最短路问题5.网络最大流问题6.最小费用最大流问题21.引例：奔驰公司的配送网络斯图加特鹿特丹波尔多里斯本纽约新奥尔良洛杉矶3（1）在各运输线路的单位运输成本不同的情况下，为了以最低成本将汽车配件运送到洛杉矶配送中心，应该如何分配各运输线路上的运输量？（2）在各运输线路距离不同的情况下，为了以最短距离将汽车配件运送到洛杉矶配送中心，应该如何分配各运输线路上的运输量？（3）在各运输线路的运输量有限制的情况下，为了使运输到洛杉矶配送中心的汽

2、车配件量最大，应该如何分配各运输线路上的运输量？斯图加特鹿特丹波尔多里斯本纽约新奥尔良洛杉矶42.图论基础2.1图论的起源2.2图的典型实例52.1图论的起源62.1图论的起源瑞士数学家列昂纳德•欧拉（LeonhardEuler，1707－1783）于1736年发表的一篇论文，被认为是图论方面的第一篇科学论文。7哥尼斯堡七桥问题（TheKoenigsbergBridgesProblem）8瑞士数学家列昂纳德•欧拉（LeonhardEuler，1707－1783）于1736年发表的一篇论文，被认为是图论方面的第一篇科学论文。至今已有两百多年的历

3、史。在此期间，图论大致经历了三个发展阶段：第一阶段，从18世纪上半叶至19世纪中叶，此时图论问题多数围绕游戏而产生，以哥尼斯堡七桥问题为典型；第二阶段，从19世纪中叶到20世纪中叶，此时图论问题大量出现，并在部分领域取得成功应用；第三阶段，从20世纪中叶至今，图论已广泛应用于生产管理、军事、交通、计算机网络等领域，同时由于计算机技术的发展，使得大规模问题的求解成为可能，进一步促进了图论在实际中的应用。92.2图的典型实例图论是运筹学的重要分支之一。图论以图为研究对象，这类图由若干给定的点和连接两点的线构成，可描述某些事物之间的关系，用点代表事

4、物，用连接两点的线表示两个事物之间具有特定关系。在自然界和人类社会中，许多事物以及事物之间的关系，都是可以用这种由点和线连接起来的图描述。10例：第十七届世界足球锦标赛C组对阵情况中国巴西土耳其哥斯达黎加11例：石油运输管线分布12一个图是由一些点以及点之间的连线组成的，图可以用来反映实际生活中某些对象之间的某种特定关系。通常用点代表研究对象（如城市、球队等），用点与点之间的连线表示这两个对象之间的特定关系（如，两城市之间有高速公路、两个球队之间有赛事关系等）。点与点之间的连线可能是带箭头的，也可能是不带箭头的。为了区别起见，把两点之间不带箭

5、头的连线称为边，带箭头的连线称为弧。133.最小费用流问题3.1引例：鹏程物流配送公司的最低配送成本问题3.2基本概念3.3最小费用流问题的数学模型与Excel求解143.1引例：鹏程物流配送公司的最低配送成本问题现代化物流配送是社会化大生产和国民经济发展的客观要求，它的发展状况对经济发展、商品流通和大众消费起着重要的促进或制约作用。物流配送通常有两个主要目标，即：低成本和高效率。而最小费用流问题正是以低成本为目标，寻找最佳网络流量分配方案，所以它对解决物流配送问题具有较好的适用性。151617现在，鹏程物流配送公司的管理者需要为上述运输网络

6、确定一个最佳运输方案，即：每条线路运送多少单位的产品时，总运输成本最小。该问题就是一个典型的最小费用流问题。18除了物流配送问题外，实际中存在着许多网络流量问题。例如，公路网络中的车辆流、控制系统中的信息流、供水系统中的水流以及金融系统中的现金流等等。193.2基本概念在介绍最小费用流的求解方法之前，有必要先了解一些相关的基本概念。20定义(发点，收点，中间点，弧的容量，网络)2122定义(网络上的流，弧的流量，顶点的流量)23鹏程物流配送公司的运输网络可以看出，网络上的流有两个要求：一是每条弧上的流量不能超过该弧的最大通过能力（即弧的容量）

7、；二是中间点的流量为零。由于中间点只起中转作用，所以其流量必为零。此外，发点的净流出量和收点的净流入量相等，两者均等于运输方案的总输送量。24定义(网络上的可行流，可行流的流量)2526在讨论网络流量问题时，我们应考虑的一个因素是：流量与成本有关。273.3最小费用流问题的数学模型与Excel求解28(1).既定流量要求，求使总费用最低的网络流量分配方案2930第一个约束条件表示容量限制条件；第二个约束条件表示发点的净输出量；第三个约束条件表示中间点的流出量等于输入量；第四个约束条件表示收点的净输入量。3132(2).既定预算费用，求使网络流

8、量最大的流量分配方案334最短路问题最短路问题（theshortestpathproblem）是图论中最重要的优化问题之一，可广泛应用于线路安排、工厂布局、设备更新