优化建模与LINGO第07章.ppt

优化建模与LINGO第07章.ppt

ID:50338905

大小:3.11 MB

页数:180页

时间:2020-03-12

优化建模与LINGO第07章.ppt_第1页
优化建模与LINGO第07章.ppt_第2页
优化建模与LINGO第07章.ppt_第3页
优化建模与LINGO第07章.ppt_第4页
优化建模与LINGO第07章.ppt_第5页
资源描述:

《优化建模与LINGO第07章.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给出了个产地,个销地运输问题的图形.关于它的求解方法有两类,一类是按照图论的方法求解,另一类是

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

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

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

6、14+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软件的计算结果如下:LPOPTIMUMFOUNDATSTEP6OBJEC

7、TIVEFUNCTIONVALUE1)161.0000VARIABLEVALUEREDUCEDCOSTX112.0000000.000000X1217.0000000.000000X131.0000000.000000X140.0000002.000000X2113.0000000.000000X220.0000009.000000X230.0000001.000000X2412.0000000.000000X310.0000007.000000X320.00000011.000000X3321.0000000.0000

8、00X340.0000005.000000ROWSLACKORSURPLUSDUALPRICES2)10.0000000.0000003)0.0000002.0000004)0.0000005.0000005)0.000000-6.0000006)0.000000-2.0000007)0.000000-6.00000

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。