运筹与优化+10

《运筹与优化+10》由会员分享，可在线阅读，更多相关《运筹与优化+10（180页珍藏版）》请在金锄头文库上搜索。

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

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

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

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

5、于线性规划问 题，因此，不论是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 const

6、raints 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.000

7、0 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 0.000000 X22 0.000000 9.000000 X23 0.000000 1.000000,X24 12.000000 0.000000 X31 0.000000 7.000000 X32 0.000000 11.000000 X33 21.000000 0.000000 X34 0.000000 5.000000 R

8、OW SLACK OR SURPLUS DUAL PRICES 2) 10.000000 0.000000 3) 0.000000 2.000000 4) 0.000000 5.000000 5) 0.000000 -6.000000 6) 0.000000 -2.000000 7) 0.000000 -6.000000 8) 0.000000 -5.000000 NO. ITERATIONS= 6,事实上，我们关心更多的是那些非零变量，因此, 可选择LINDO中的命令（具体方法见第二章的2.3节), 只列出非零变量.,OBJECTIVE FUNCTION VALUE 1) 161.0000

9、VARIABLE VALUE REDUCED COST X11 2.000000 0.000000 X12 17.000000 0.000000,X13 1.000000 0.000000 X21 13.000000 0.000000 X24 12.000000 0.000000 X33 21.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 3) 0.000000 2.000000 4) 0.000000 5.000000 5) 0.000000 -6.000000 6) 0.000000 -2.000000 7) 0.000000 -6.00

10、0000 8) 0.000000 -5.000000 NO. ITERATIONS= 6,LINDO软件虽然给出最优解，但上述模型还存在 着缺点，例如，上述方法不便于推广的一般情况，特 别是当产地和销地的个数较多时，情况更为突出. 下面写出求解该问题的LINGO程序，并在程序中 用到在第三章介绍的集与数据段，以及相关的循环函 数. 写出相应的LINGO程序，程序名： exam0702.lg4,MODEL: 1! 3 Warehouse, 4 Customer Transportation Problem; 2sets: 3 Warehouse /13/: a; 4 Customer /14/:

11、 b;,5 Routes( Warehouse, Customer) : c, x; 6endsets 7! Here are the parameters; 8data: 9 a = 30, 25, 21 10 b = 15, 17, 22, 12; 11 c = 6, 2, 6, 7, 12 4, 9, 5, 3, 13 8, 8, 1, 5; 14enddata 15! The objective; 16OBJ min = sum( Routes: c * x);,17! The supply constraints; 18for( Warehouse(i): SUP 19 sum( C

12、ustomer(j): x(i,j) = a(i); 20! The demand constraints; 21for( Customer(j): DEM 22 sum( Warehouse(i): x(i,j) = b(j); END,在上述程序中，第16表示运输问题中目标函数 (7.1). 第18 19行表示约束条件(7.2), 第21 22行 表示约束条件(7.3).,下面列出LINGO软件的求解结果（仅保留非零变量）,Global optimal solution found at iteration: 6 Objective value: 161.0000 Variable Val

13、ue Reduced Cost X( 1, 1) 2.000000 0.000000 X( 1, 2) 17.00000 0.000000 X( 1, 3) 1.000000 0.000000 X( 2, 1) 13.00000 0.000000 X( 2, 4) 12.00000 0.000000 X( 3, 3) 21.00000 0.000000 Row Slack or Surplus Dual Price OBJ 161.0000 -1.000000 SUP( 1) 10.00000 0.000000,从上述求解过程来看，两种软件的计算结果 是相同的，但由于LINGO软件中采用集、数

14、据段 和循环函数的编写方式，因此更便于程序推广到 一般形式使用.例如，只需修改运输问题中产地 和销地的个数，以及参数a,b,c的值，就可以求解 任何运输问题.所以，从程序通用性的角度来看, 推荐大家采用LINGO软件来求解运输问题.,7.1.2 指派问题,例7.3（指派问题）设有n个人, 计划作n项工作, 其 中 表示第i个人做第j项工作的收益, 现求一种指派方 式，使得每个人完成一项工作，使总收益最大. 例7.3就是指派问题(Assignment Problem).指派 问题也是图论中的重要问题，有相应的求解方法，如 匈牙利算法.从问题的形式来看，指派问题是运输问 题的特例，也可以看成0-1

15、规划问题.,返 回 导 航,1. 指派问题的数学表达式,设变量为 ,当第 个人作第 项工作时， , 否则 . 因此，相应的线性规划问题为,2. 指派问题的求解过程 分别用LINDO软件和LINGO软件求解指派问 题，并对两种软件的求解方法与各自的优缺点进 行比较.,例7.4（继例7.3） 考虑例7.3中 的情况,即 6个人做6项工作的最优指派问题，其收益矩阵如 表7-2所示.,! Assignment model ! Maximize valve of assignments max 20x11 + 15x12 + 16x13 + 5x14 + 4x15 + 7x16 + 17x21 + 15x22 + 33x23 + 12x24 + 8x25 + 6