图论与网络模型课件.ppt

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

1、欢迎各位同学学习第七章内容导航概述7.1运输问题与转运问题7.2最短路问题和最大流问题7.3最优连线问题与旅行商问题7.4计划评审方法和关键路线法习题七第7章　图论与网络模型本章内容概述本章介绍图论与网络(GraphTheoryandNetwork)的有关优化问题模型。在这里，我们并不打算全面系统介绍图论与网络的知识，而着重介绍与LINDO、LINGO软件有关的组合优化模型和相应的求解过程。如果读者打算深入地了解图论与网络的更全面的知识，请参阅图论或运筹学中的有关书籍.LINDO软件和LINGO软件可以求解一些著名的组合优化问题，这包括最短路问题、最大流问题、运输和转运问题、最优匹配和最

2、优指派问题、最优连线或最小生成树问题、旅行商问题、关键路线法与计划评审方法等。7.1运输问题与转运问题本节内容导航7.1.1运输问题7.1.2指派问题7.1.3转运问题§7.1.1　运输问题运输问题(TransportationProblem)是图论与网络中的一个重要问题，也是一个典型的线性规划问题.例7.1（运输问题）返回导航例7.1就是典型的运输问题，图7-1给出了个产地，个销地运输问题的图形.关于它的求解方法有两类，一类是按照图论的方法求解，另一类是化成线性规划问题.这里介绍第二类方法，即用LINDO或LINGO软件求解运输问题.但为便于后面的叙述，先给出图论中有关图的部分定义.图

3、7-1:个产地,个销售地运输问题的图形1.图的基本定义从直观上看,所谓图是由点和边组成的图形,如图7-1所示.下面我们给出图的定义.注：通常有向图的边称为弧，由弧构成的集记为因此，有向图记为　　　,而无向图记为　　　.为方便起见，在后面的论述中，有时也用　　　表示有向图.在无向图中,每条至多有一条边的图称为简单图(SimpleGraph).若每一对不同的顶点都有一条边相连的简单图称为完全图(CompleteGraph).若一个图中的顶点集可以分解为两个子集　和　,使得任何一条边都有一个端点在　中,另一个端点在　中,这种图称为二部图或偶图(BipartiteGraph).运输问题所构成的图

4、7-1是偶图.2.运输问题的数学表达式第　个产地的运出量应小于或等于该地的生产量，即：第　个销地的运入量应等于该地的需求量，即：因此，运输问题的数学表达式为:称具有形如式　　　的线性规划问题为运输问题.3.运输问题的求解过程为了便于讨论，以一个运输问题实例的求解过程来介绍如何用LINDO或LINGO软件求解运输问题模型.例7.2(继例7.1)设即为有3个产地和4个销地的运输问题，其产量、销量及单位运费如表7-1所示.试求总运费最少的运输方案，以及总运费.解：从前面的分析来看，运输问题属于线性规划问题，因此，不论是LINDO软件或LINGO软件都可以对该问题求解.为了便于比较两种软件的优缺

5、点，以及各自的特点，我们用两种软件分别求解该运输问题.首先写出LINDO软件的模型（程序），程序名：exam0702.ltx.!3Warehouse,4CustomerTransportationProblem!Theobjectivemin6x11+2x12+6x13+7x14+4x21+9x22+5x23+3x24+8x31+8x32+x33+5x34subjectto!Thesupplyconstraints2)x11+x12+x13+x14<=303)x21+x22+x23+x24<=254)x31+x32+x33+x34<=21!Thedemandconstraints5)x1

6、1+x21+x31=156)x12+x22+x32=177)x13+x23+x33=228)x14+x24+x34=12endLINDO软件的计算结果如下：LPOPTIMUMFOUNDATSTEP6OBJECTIVEFUNCTIONVALUE1)161.0000VARIABLEVALUEREDUCEDCOSTX112.0000000.000000X1217.0000000.000000X131.0000000.000000X140.0000002.000000X2113.0000000.000000X220.0000009.000000X230.0000001.000000X2412.0

7、000000.000000X310.0000007.000000X320.00000011.000000X3321.0000000.000000X340.0000005.000000ROWSLACKORSURPLUSDUALPRICES2)10.0000000.0000003)0.0000002.0000004)0.0000005.0000005)0.000000-6.0000006)0.000000-2.0000007)0.000