运筹与优化10.ppt

《运筹与优化10.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十讲图论与网络模型凯里学院文化素质选修课教案欢迎各位参加运筹与优化的学习凯里学院理学院潘东云2010年3月1日本章内容概述本章介绍图论与网络(GraphTheoryandNetwork)的有关优化问题模型。在这里，我们并不打算全面系统介绍图论与网络的知识，而着重介绍与LINDO、LINGO软件有关的组合优化模型和相应的求解过程。如果读者打算深入地了解图论与网络的更全面的知识，请参阅图论或运筹学中的有关书籍.LINDO软件和LINGO软件可以求解一些著名的组合优化问题，这包括最短路问题、最大流问题、运输

2、和转运问题、最优匹配和最优指派问题、最优连线或最小生成树问题、旅行商问题、关键路线法与计划评审方法等。10.1运输问题与转运问题本节内容导航10.1.1运输问题10.1.2指派问题10.1.3转运问题§10.1.1运输问题运输问题(TransportationProblem)是图论与网络中的一个重要问题，也是一个典型的线性规划问题.例10.1（运输问题）返回导航例10.1就是典型的运输问题，图7-1给出了个产地，个销地运输问题的图形.关于它的求解方法有两类，一类是按照图论的方法求解，另一类是化成线性规划

3、问题.这里介绍第二类方法，即用LINDO或LINGO软件求解运输问题.但为便于后面的叙述，先给出图论中有关图的部分定义.图10-1:个产地,个销售地运输问题的图形1.图的基本定义从直观上看,所谓图是由点和边组成的图形,如图10-1所示.下面我们给出图的定义.注：通常有向图的边称为弧，由弧构成的集记为因此，有向图记为,而无向图记为.为方便起见，在后面的论述中，有时也用　　　表示有向图.在无向图中,每条至多有一条边的图称为简单图(SimpleGraph).若每一对不同的顶点都有一条边相连的简单图称为完全图(

4、CompleteGraph).若一个图中的顶点集可以分解为两个子集　和,使得任何一条边都有一个端点在　中,另一个端点在　中,这种图称为二部图或偶图(BipartiteGraph).运输问题所构成的图7-1是偶图.2.运输问题的数学表达式第　个产地的运出量应小于或等于该地的生产量，即：第　个销地的运入量应等于该地的需求量，即：因此，运输问题的数学表达式为:称具有形如式的线性规划问题为运输问题.3.运输问题的求解过程为了便于讨论，以一个运输问题实例的求解过程来介绍如何用LINDO或LINGO软件求解运输问题

5、模型.例7.2(继例7.1)设即为有3个产地和4个销地的运输问题，其产量、销量及单位运费如表7-1所示.试求总运费最少的运输方案，以及总运费.解：从前面的分析来看，运输问题属于线性规划问题，因此，不论是LINDO软件或LINGO软件都可以对该问题求解.为了便于比较两种软件的优缺点，以及各自的特点，我们用两种软件分别求解该运输问题.首先写出LINDO软件的模型（程序），程序名：exam0702.ltx.!3Warehouse,4CustomerTransportationProblem!Theobject

6、ivemin6x11+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)x11+x21+x31=156)x12+x22+x32=177)x13+x23+x33=228)x14+x24+x34=12endLINDO软件的计

7、算结果如下：LPOPTIMUMFOUNDATSTEP6OBJECTIVEFUNCTIONVALUE1)161.0000VARIABLEVALUEREDUCEDCOSTX112.0000000.000000X1217.0000000.000000X131.0000000.000000X140.0000002.000000X2113.0000000.000000X220.0000009.000000X230.0000001.000000X2412.0000000.000000X310.0000007.000

8、000X320.00000011.000000X3321.0000000.000000X340.0000005.000000ROWSLACKORSURPLUSDUALPRICES2)10.0000000.0000003)0.0000002.0000004)0.0000005.0000005)0.000000-6.0000006)0.000000-2.0000007)0.000000-6.0000008)0.000000-5.000000NO