优化建模与lingo第07章.pptxVIP

本章内容概述 本章介绍图论与网络(Graph Theory and Network)的 有关优化问题模型。在这里，我们并不打算全面系统介绍 图论与网络的知识，而着重介绍与LINDO、LINGO软件有 关的组合优化模型和相应的求解过程。如果读者打算深入 地了解图论与网络的更全面的知识，请参阅图论或运筹学 中的有关书籍. LINDO软件和LINGO软件可以求解一些著名的组合优 化问题，这包括最短路问题、最大流问题、运输和转运问 题、最优匹配和最优指派问题、最优连线或最小生成树问 题、旅行商问题、关键路线法与计划评审方法等。;7.1　运输问题与转运问题;§7.1.1　运输问题 　　　运输问题(Transportation Problem)是图论与网络中的一个重要问题，也是一个典型的线性规划问题. 　 例7.1 （运输问题）　　　; 例7.1 就是典型的运输问题，图7-1给出了 个产地， 个销地运输问题的图形.关于它的求解方法有两类，一类是按照图论的方法求解，另一类是化成线性规划问题.这里介绍第二类方法，即用LINDO或LINGO软件求解运输问题.但为便于后面的叙述，先给出图论中有关图的部分定义. ; 　1. 图的基本定义 　从直观上看, 所谓图是由点和边组成的图形, 如 图7-1所示.下面我们给出图的定义.;　　注：通常有向图的边称为弧，由弧构成的集记为 　因此，有向图记为　　　, 而无向图记为　　　. 为 方便起见，在后面的论述中，有时也用　　　表示有 向图. 　　在无向图中, 每条至多有一条边的图称为简单图 (Simple Graph). 若每一对不同的顶点都有一条边相 连的简单图称为完全图(Complete Graph). 若一个图 中的顶点集可以分解为两个子集　和　, 使得任何一 条边都有一个端点在　中, 另一个端点在　中, 这种图 称为二部图或偶图(Bipartite Graph). 运输问题所构成 的图7-1是偶图.;2. 运输问题的数学表达式;因此，运输问题的数学表达式为:; 　3. 运输问题的求解过程 　　为了便于讨论，以一个运输问题实例的求解过 程来介绍如何用LINDO或LINGO软件求解运输问 题模型. 　例7.2(继例7.1) 设 　　　　即为有3个产地和 4个销地的运输问题，其产量、销量及单位运费如 表7-1所示.试求总???费最少的运输方案，以及总 运费.;　　解：从前面的分析来看，运输问题属于线性规划问 题，因此，不论是LINDO软件或LINGO软件都可以对 该问题求解.为了便于比较两种软件的优缺点，以及各 自的特点，我们用两种软件分别求解该运输问题. 　　首先写出LINDO软件的模型（程序），程序名： exam0702.ltx. ! 3 Warehouse, 4 Customer Transportation Problem 　　! The objective 　　min 6x11 + 2x12 + 6x13 + 7x14 　 + 4x21 + 9x22 + 5x23 + 3x24 　 + 8x31 + 8x32 + x33 + 5x34 　　subject to;! The supply constraints 2) x11 + x12 + x13 + x14 = 30 3) x21 + x22 + x23 + x24 = 25 4) x31 + x32 + x33 + x34 = 21 ! The demand constraints 5) x11 + x21 + x31 = 15 6) x12 + x22 + x32 = 17 7) x13 + x23 + x33 = 22 8) x14 + x24 + x34 = 12 end;LINDO软件的计算结果如下： LP OPTIMUM FOUND AT STEP 6 OBJECTIVE FUNCTION VALUE 1) 161.0000 VARIABLE VALUE REDUCED COST X11 2.000000 0.000000 X12 17.000000 0.000000 X13 1.000000 0.000000 X14 0.000000 2.000000 X21 13.000000