第-7-章--图论与网络模型ppt课件.ppt

《第-7-章--图论与网络模型ppt课件.ppt》由会员分享，可在线阅读，更多相关《第-7-章--图论与网络模型ppt课件.ppt（180页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、优优 化化 建建 模模欢迎各位同学学习第七章欢迎各位同学学习第七章内容导航内容导航 概述概述7.1运输问题与转运问题运输问题与转运问题7.2最短路问题和最大流问题最短路问题和最大流问题7.3最优连线问题与旅行商问题最优连线问题与旅行商问题7.4计划评审方法和关键路线法计划评审方法和关键路线法 习题习题 七七第第 7 7 章章 图论与网络模型图论与网络模型优优 化化 建建 模模 本章内容概述本章内容概述 本章介绍图论与网络本章介绍图论与网络(Graph Theory and Network)的的有关优化问题模型。在这里，我们并不打算全面系统介绍有关优化问题模型。在这里，我们并不打算全面系统介绍图

2、论与网络的知识，而着重介绍与图论与网络的知识，而着重介绍与LINDO、LINGO软件有软件有关的组合优化模型和相应的求解过程。如果读者打算深入关的组合优化模型和相应的求解过程。如果读者打算深入地了解图论与网络的更全面的知识，请参阅图论或运筹学地了解图论与网络的更全面的知识，请参阅图论或运筹学中的有关书籍中的有关书籍. LINDO软件和软件和LINGO软件可以求解一些著名的组合优软件可以求解一些著名的组合优化问题，这包括最短路问题、最大流问题、运输和转运问化问题，这包括最短路问题、最大流问题、运输和转运问题、最优匹配和最优指派问题、最优连线或最小生成树问题、最优匹配和最优指派问题、最优连线或最小

3、生成树问题、旅行商问题、关键路线法与计划评审方法等。题、旅行商问题、关键路线法与计划评审方法等。优优 化化 建建 模模7.17.1运输问题与转运问题运输问题与转运问题本节内容导航本节内容导航7.1.1运输问题运输问题7.1.2指派问题指派问题7.1.3转运问题转运问题优优 化化 建建 模模7.1.1运输问题运输问题运输问题运输问题(Transportation Problem)是图论与是图论与网络中的一个重要问题，也是一个典型的线性网络中的一个重要问题，也是一个典型的线性规划问题规划问题. 例例7.1 （运输问题）（运输问题）返回导航优优 化化 建建 模模 例例7.1 就是典型的运输问题，图就

4、是典型的运输问题，图7-1给出了给出了 个产地，个产地， 个销地运输问题的图形个销地运输问题的图形.关于它的求关于它的求解方法有两类，一类是按照图论的方法求解，解方法有两类，一类是按照图论的方法求解，另一类是化成线性规划问题另一类是化成线性规划问题.这里介绍第二类方这里介绍第二类方法，即用法，即用LINDO或或LINGO软件求解运输问题软件求解运输问题.但为便于后面的叙述，先给出图论中有关图的但为便于后面的叙述，先给出图论中有关图的部分定义部分定义.mn图7-1: 个产地, 个销售地运输问题的图形mn优优 化化 建建 模模1. 图的基本定义图的基本定义从直观上看, 所谓图是由点和边组成的图形,

5、 如图7-1所示.下面我们给出图的定义.优优 化化 建建 模模注：注：通常有向图的边称为弧，由弧构成的集记为通常有向图的边称为弧，由弧构成的集记为因此，有向图记为因此，有向图记为, 而无向图记为而无向图记为. 为为方便起见，在后面的论述中，有时也用表示有方便起见，在后面的论述中，有时也用表示有向图向图.在无向图中在无向图中, 每条至多有一条边的图称为简单图每条至多有一条边的图称为简单图(Simple Graph). 若每一对不同的顶点都有一条边相若每一对不同的顶点都有一条边相连的简单图称为完全图连的简单图称为完全图(Complete Graph). 若一个图若一个图中的顶点集可以分解为两个子集

6、和中的顶点集可以分解为两个子集和, 使得任何一使得任何一条边都有一个端点在中条边都有一个端点在中, 另一个端点在中另一个端点在中, 这种图这种图称为二部图或偶图称为二部图或偶图(Bipartite Graph). 运输问题所构成运输问题所构成的图的图7-1是偶图是偶图., A),(EVG),(AVG),(EVG1V2V1V2V1V优优 化化 建建 模模2. 运输问题的数学表达式运输问题的数学表达式.11minjijijxc第个产地的运出量应小于或等于该地的生产量，即：第个产地的运出量应小于或等于该地的生产量，即：i.1njiijax第个销地的运入量应等于该地的需求量，即：第个销地的运入量应等于

7、该地的需求量，即：j.1mijijbx优优 化化 建建 模模因此，运输问题的数学表达式为因此，运输问题的数学表达式为:称具有形如式称具有形如式的线性规划问题为运输问题的线性规划问题为运输问题.)4()1(优优 化化 建建 模模3. 运输问题的求解过程运输问题的求解过程为了便于讨论，以一个运输问题实例的求解过为了便于讨论，以一个运输问题实例的求解过程来介绍如何用程来介绍如何用LINDO或或LINGO软件求解运输问软件求解运输问题模型题模型.例例7.2(继例继例7.1) 设设 即为有即为有3个产地和个产地和4个销地的运输问题，其产量、销量及单位运费如个销地的运输问题，其产量、销量及单位运费如表表7

8、-1所示所示.试求总运费最少的运输方案，以及总试求总运费最少的运输方案，以及总运费运费.4, 3nm优优 化化 建建 模模解：解：从前面的分析来看，运输问题属于线性规划问从前面的分析来看，运输问题属于线性规划问题，因此，不论是题，因此，不论是LINDO软件或软件或LINGO软件都可以对软件都可以对该问题求解该问题求解.为了便于比较两种软件的优缺点，以及各为了便于比较两种软件的优缺点，以及各自的特点，我们用两种软件分别求解该运输问题自的特点，我们用两种软件分别求解该运输问题.首先写出首先写出LINDO软件的模型（程序），程序名：软件的模型（程序），程序名：exam0702.ltx. ! 3 Wa

9、rehouse, 4 Customer Transportation Problem! The objectivemin 6x11 + 2x12 + 6x13 + 7x14 + 4x21 + 9x22 + 5x23 + 3x24 + 8x31 + 8x32 + x33 + 5x34subject to优优 化化 建建 模模! The supply constraints2) x11 + x12 + x13 + x14 = 303) x21 + x22 + x23 + x24 = 254) x31 + x32 + x33 + x34 = 21! The demand constraints5)

10、x11 + x21 + x31 = 156) x12 + x22 + x32 = 177) x13 + x23 + x33 = 228) x14 + x24 + x34 = 12end优优 化化 建建 模模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

11、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 ROW SLACK OR SURPLUS DUAL PRICES 2) 10.000000 0.000000 3) 0.000000 2.000000 4) 0.000000 5.000000 5) 0

12、.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 VARIABLE VALUE REDUCED COST X11 2.000000 0.000

13、000 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.000000 8) 0.000000 -5.000000 NO. ITER

14、ATIONS= 6优优 化化 建建 模模 LINDO软件虽然给出最优解，但上述模型还存在软件虽然给出最优解，但上述模型还存在着缺点，例如，上述方法不便于推广的一般情况，特着缺点，例如，上述方法不便于推广的一般情况，特别是当产地和销地的个数较多时，情况更为突出别是当产地和销地的个数较多时，情况更为突出. 下面写出求解该问题的下面写出求解该问题的LINGO程序，并在程序中程序，并在程序中用到在第三章介绍的集与数据段，以及相关的循环函用到在第三章介绍的集与数据段，以及相关的循环函数数. 写出相应的写出相应的LINGO程序，程序名：程序，程序名： exam0702.lg4MODEL: 1! 3 War

15、ehouse, 4 Customer Transportation Problem; 2sets: 3 Warehouse /1.3/: a; 4 Customer /1.4/: 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 object

16、ive; 16OBJ min = sum( Routes: c * x);优优 化化 建建 模模 17! The supply constraints; 18for( Warehouse(i): SUP 19 sum( Customer(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行表示约束条件行表示约束条件(

17、7.2), 第第21 22行行表示约束条件表示约束条件(7.3).优优 化化 建建 模模 下面列出下面列出LINGO软件的求解结果（仅保留非零变量）软件的求解结果（仅保留非零变量）Global optimal solution found at iteration: 6 Objective value: 161.0000 Variable Value 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(

18、 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软件中采用集、数据段软件中采用集、数据段和循环函数的编写方式，因此更便于程序推广到和循环函数的编写方式，因此更便于程序推广到一般形式使用一般形式使用.例如，只需修改运输问题中产地例如，只需修改运

19、输问题中产地和销地的个数，以及参数和销地的个数，以及参数a,b,c的值，就可以求解的值，就可以求解任何运输问题任何运输问题.所以，从程序通用性的角度来看所以，从程序通用性的角度来看,推荐大家采用推荐大家采用LINGO软件来求解运输问题软件来求解运输问题.优优 化化 建建 模模7.1.2 指派问题指派问题 例例7.3（指派问题）设有（指派问题）设有n个人个人, 计划作计划作n项工作项工作, 其其中中 表示第表示第i个人做第个人做第j项工作的收益项工作的收益, 现求一种指派方现求一种指派方式，使得每个人完成一项工作，使总收益最大式，使得每个人完成一项工作，使总收益最大. 例例7.3就是指派问题就是

20、指派问题(Assignment Problem).指派指派问题也是图论中的重要问题，有相应的求解方法，如问题也是图论中的重要问题，有相应的求解方法，如匈牙利算法匈牙利算法.从问题的形式来看，指派问题是运输问从问题的形式来看，指派问题是运输问题的特例，也可以看成题的特例，也可以看成0-1规划问题规划问题.ijc返回导航优优 化化 建建 模模 1. 指派问题的数学表达式指派问题的数学表达式 设变量为设变量为 ,当第当第 个人作第个人作第 项工作时，项工作时， , 否则否则 . 因此，相应的线性规划问题为因此，相应的线性规划问题为 1111min1,1, 2,(1,1, 2,()01,1, 2, .

21、mnijijijnijjnijiijc xxinxjnxjn ； (5)s.t. ，每 个 人 做 一 项 工 作 ) (6) 每 项 工 作 有 一 个 人 去 做 (7) 或 ( 8)ijxij1ijx 0ijx 优优 化化 建建 模模 2. 指派问题的求解过程指派问题的求解过程 分别用分别用LINDO软件和软件和LINGO软件求解指派问软件求解指派问题，并对两种软件的求解方法与各自的优缺点进题，并对两种软件的求解方法与各自的优缺点进行比较行比较. 例例7.4（继例（继例7.3） 考虑例考虑例7.3中中 的情况的情况,即即6个人做个人做6项工作的最优指派问题，其收益矩阵如项工作的最优指派问

22、题，其收益矩阵如表表7-2所示所示. 6n优优 化化 建建 模模! Assignment model! Maximize valve of assignmentsmax 20 x11 + 15x12 + 16x13 + 5x14 + 4x15 + 7x16 + 17x21 + 15x22 + 33x23 + 12x24 + 8x25 + 6x26 + 9x31 + 12x32 + 18x33 + 16x34 + 30 x35 + 13x36 + 12x41 + 8x42 + 11x43 + 27x44 + 19x45 + 14x46 - 99x51 + 7x52 + 10 x53 + 21x5

23、4 + 10 x55 + 32x56 - 99x61 - 99x62 - 99x63 + 6x64 + 11x65 + 13x66subject to 解：解：与运输问题一样，先用与运输问题一样，先用LINDO软件求解软件求解. 给出给出LINGO程序，程序名程序，程序名exam0704.ltx优优 化化 建建 模模! Each person must be assigned to some job x11 + x12 + x13 + x14 + x15 + x16 = 1 x21 + x22 + x23 + x24 + x25 + x26 = 1 x31 + x32 + x33 + x34

24、+ x35 + x36 = 1 x41 + x42 + x43 + x44 + x45 + x46 = 1 x51 + x52 + x53 + x54 + x55 + x56 = 1 x61 + x62 + x63 + x64 + x65 + x66 = 1! Each job must receive an assignment x11 + x21 + x31 + x41 + x51 + x61 = 1 x12 + x22 + x32 + x42 + x52 + x62 = 1 x13 + x23 + x33 + x43 + x53 + x63 = 1 x14 + x24 + x34 + x

25、44 + x54 + x64 = 1 x15 + x25 + x35 + x45 + x55 + x65 = 1 x16 + x26 + x36 + x46 + x56 + x66 = 1end优优 化化 建建 模模 在上述程序中，在上述程序中， x51, x61, x62, x63前的系数均前的系数均为为-99, 这是因为某人无法做某项工作可以某人做该这是因为某人无法做某项工作可以某人做该项工作的收益是项工作的收益是 , 在计算中通常取一个较大的负在计算中通常取一个较大的负数就可以数就可以. 上述程序也没有说明决策变量上述程序也没有说明决策变量 是是0-1型变量型变量,这是因为对于此类问题线

26、性规划理论已保证了变量这是因为对于此类问题线性规划理论已保证了变量 的取值只可能是的取值只可能是0或或1.xx LINDO软件给出的计算结果如下（只列出非软件给出的计算结果如下（只列出非零变量）零变量）:优优 化化 建建 模模OBJECTIVE FUNCTION VALUE 1) 135.0000 VARIABLE VALUE REDUCED COST X11 1.000000 0.000000 X23 1.000000 0.000000 X32 1.000000 0.000000 X44 1.000000 0.000000 X56 1.000000 0.000000 X65 1.000000

27、 0.000000 ROW SLACK OR SURPLUS DUAL PRICES优优 化化 建建 模模 2) 0.000000 3.000000 3) 0.000000 15.000000 5) 0.000000 -4.000000 7) 0.000000 -19.000000 8) 0.000000 17.000000 9) 0.000000 12.000000 10) 0.000000 18.000000 11) 0.000000 31.000000 12) 0.000000 30.000000 13) 0.000000 32.000000 NO. ITERATIONS= 20优优 化

28、化 建建 模模 即第即第1个人做第个人做第1项工作，第项工作，第2个人做第个人做第3项工作项工作,第第3个人做第个人做第2项工作，第项工作，第4个人做第个人做第4项工作，第项工作，第5个人做第个人做第6项工作，第项工作，第6个人做第个人做第5项工作项工作. 总效益值总效益值为为135. 下面用下面用LINGO程序再求解此问题，程序中仍然程序再求解此问题，程序中仍然用到集、数据段和循环函数用到集、数据段和循环函数. 写出相应的写出相应的LINGO程序，程序名程序，程序名exam0704.lg4.MODEL: 1! Assignment Problem Model; 2sets: 3 Flight

29、/1.6/; 4 Assign(Flight, Flight): c, x;优优 化化 建建 模模 5endsets 6! Here is income matrix; 7data: 8 c = 20 15 16 5 4 7 9 17 15 33 12 8 6 10 9 12 18 16 30 13 11 12 8 11 27 19 14 12 -99 7 10 21 10 32 13 -99 -99 -99 6 11 13; 14enddata 15优优 化化 建建 模模 16! Maximize valve of assignments; 17max = sum(Assign: c*x);

30、 18for(Flight(i): 19! Each i must be assigned to some j; 20 sum(Flight(j): x(i,j) = 1; 21! Each I must receive an assignment; 22 sum(Flight(j): x(j,i) = 1; 23); END优优 化化 建建 模模 程序中第程序中第12 13行中的行中的-99意义与意义与LINDO程序程序中的意义相同，当某人无法做某项工作时，取一个中的意义相同，当某人无法做某项工作时，取一个数值较大的负值数值较大的负值. LINGO软件计算结果如下（只列出非零变量）软件计算结

31、果如下（只列出非零变量）:Global optimal solution found at iteration: 0 Objective value: 135.0000 Variable Value Reduced Cost X( 1, 1) 1.000000 0.000000 X( 2, 3) 1.000000 0.000000 X( 3, 2) 1.000000 0.000000 X( 4, 4) 1.000000 0.000000 X( 5, 6) 1.000000 0.000000 X( 6, 5) 1.000000 0.000000优优 化化 建建 模模 从上述两个例子，可以看出从上

32、述两个例子，可以看出LINGO软件在处软件在处理问题方面要大优于理问题方面要大优于LINDO软件，而且便于推软件，而且便于推广，只是在编程方面，广，只是在编程方面，LINGO程序的编写稍复杂程序的编写稍复杂一些一些.在后面的问题求解中，绝大多数的求解方法在后面的问题求解中，绝大多数的求解方法是采用是采用LINGO软件计算软件计算. 对于指派问题，也可以考虑人数不工作数不对于指派问题，也可以考虑人数不工作数不相等的情况，和考虑支付最小的情况相等的情况，和考虑支付最小的情况.第一章的例第一章的例1.5“混合泳接力队员选拔问题混合泳接力队员选拔问题”就是属于这一类就是属于这一类情情况况. 优优 化化

33、 建建 模模 例例7.5（继例（继例1.5）用）用LINGO软件求解例软件求解例1.5. 解：解：在第二章的例在第二章的例2.7给出了该问题的给出了该问题的LINDO软软件求解方法，这里给出件求解方法，这里给出LINGO软件的求解方法，读软件的求解方法，读者可根据问题的求解过程来考查两种软件求解问题的者可根据问题的求解过程来考查两种软件求解问题的方法，以及每种软件各自的特点方法，以及每种软件各自的特点. 为了便于编写程序，将为了便于编写程序，将5名队员的名队员的4种泳姿的百米种泳姿的百米平均成绩重新列在表平均成绩重新列在表7-3中中. 优优 化化 建建 模模按第按第1章所列的规划问题（第章中的

34、式章所列的规划问题（第章中的式(1.25) 式式(1.28)）写出相应的）写出相应的LINGO程序，程序，程序名：程序名：exam0705.lg4.MODEL: 1! 5 persons and 4 jobs Assignment Problem; 2sets: 3 Person /1.5/; 4 Job /1.4/; 5 Assign( Person, Job) : c, x; 6endsets 7! Here are the parameters; 8data:优优 化化 建建 模模 9 c = 66.8, 75.6, 87, 58.6, 10 57.2, 66, 66.4, 53, 11

35、 78, 67.8, 84.6, 59.4, 12 70, 74.2, 69.6, 57.2, 13 67.4, 71, 83.8, 62.4; 14enddata 15! The objective; 16OBJ min = sum( Assign: c * x); 17! The supply constraints; 18for( Person(i): SUP 19 sum( Job(j): x(i,j) = 1); 20! The demand constraints; 21for( Job(j): DEM 22 sum( Person(i): x(i,j) = 1); END该程序同

36、样没有限制是该程序同样没有限制是01型变量型变量.ijx优优 化化 建建 模模 下面列出下面列出LINGO软件计算结果（仅保留非零变软件计算结果（仅保留非零变量）量）: Global optimal solution found at iteration: 9Objective value: 253.2000Variable Value Reduced Cost X( 1, 4) 1.000000 0.000000 X( 2, 1) 1.000000 0.000000 X( 3, 2) 1.000000 0.000000 X( 4, 3) 1.000000 0.000000Row Slack

37、or Surplus Dual Price OB J 253.2000 -1.000000 SUP( 5) 1.000000 0.000000 即甲游自由泳，乙游蝶泳，丙游仰泳，丁游蛙泳即甲游自由泳，乙游蝶泳，丙游仰泳，丁游蛙泳,没有被选拔没有被选拔上上.平均成绩为平均成绩为. 4132.优优 化化 建建 模模7.1.3 转运问题转运问题 所谓转运问题所谓转运问题(Transshipment Problem)实质上实质上是运输问题的一种，其区别就在于不是将工厂生产是运输问题的一种，其区别就在于不是将工厂生产出的产品直接送的顾客手中，而是要经过某些中间出的产品直接送的顾客手中，而是要经过某些中间

38、环节，如仓库、配送中心等环节，如仓库、配送中心等.图图7-2表示的是表示的是3水平分水平分配（即有一个中间环节）的转运问题配（即有一个中间环节）的转运问题. 返回导航优优 化化 建建 模模1.转运问题的数学表达式转运问题的数学表达式优优 化化 建建 模模1221111min ; (9)s.t. , 1,2,() (10) lnijjkjkjklijijixc xxaimx运出量应不大于生产量12112112, 1,2, ,() (11) , 1,2,() (12) 0,0.mnjjkikljkkjxjlxbknxx运入量应等于运出量运入量应等于需求量优优 化化 建建 模模 1.转运问题的求解方

39、法转运问题的求解方法 以一个例子为例，给出求解转运问题的两种以一个例子为例，给出求解转运问题的两种求解方法求解方法. 例例7.6（转运问题）设有两个工厂（转运问题）设有两个工厂A, B, 产量分别产量分别为为9, 8个单位个单位. 四个顾客四个顾客1, 2, 3, 4, 需求量分别为需求量分别为3, 5, 4, 5. 和三个仓库和三个仓库x, y, z. 其中工厂到仓库、仓库到顾其中工厂到仓库、仓库到顾客的运费单价分别由表客的运费单价分别由表7-4所示所示.试求总运费最少的试求总运费最少的运输方案，以及总运费运输方案，以及总运费.优优 化化 建建 模模AB1234x15y2z表表7-4 工厂到

40、仓库工厂到仓库 、仓库到顾客的运费单价、仓库到顾客的运费单价说明：其中说明：其中-表示两地无道路通行表示两地无道路通行.解：解：写出相应的写出相应的LINGO程序，程序名：程序，程序名： exam0706a.lg4.优优 化化 建建 模模MODEL: 1! 2 plants, 3 warehouses and 4 customers 2 Transshipment Problem; 3sets: 4 Plant /A, B/ : produce; 5 Warhouse /x, y, z/; 6 Customer /1.4/ : require; 7 LinkI ( Plant, Warhous

41、e) : cI, xI; 8 LinkII ( Warhouse, Customer) : cII, xII; 9endsets 10! Here are the parameters; 11data: 12 produce = 9, 8;优优 化化 建建 模模 13 require = 3, 5, 4, 5; 14 cI = 1, 2, 100, 15 3, 1, 2; 16 cII = 5, 7, 100, 100, 17 9, 6, 7, 100, 18 100, 8, 7, 4; 19enddata 20! The objective; 21OBJ min = sum(LinkI: c

42、I * xI)+sum(LinkII: cII * xII); 22! The supply constraints; 23for( Plant(i): SUP 24 sum( Warhouse(j): xI(i,j) = produce(i);优优 化化 建建 模模 25! The warhouse constraints; 26for( Warhouse(j): MID 27 sum( Plant(i): xI(i,j)=sum( Customer(k): xII(j,k); 28! The demand constraints; 29for( Customer(k): DEM 30 su

43、m( Warhouse(j): xII(j,k) = require(k); END在上述程序中，由在上述程序中，由14至至15行定义的行定义的cI是工厂是工厂到仓库的运费，由到仓库的运费，由16至至18行定义的行定义的cII是仓库到顾是仓库到顾客的运费客的运费.我们的目标是求最小运费，因此当两点无我们的目标是求最小运费，因此当两点无道路时，认为是运费无穷大道路时，认为是运费无穷大.为了便于计算，只要取为了便于计算，只要取较大的数值就可以了，这里的取值为较大的数值就可以了，这里的取值为100.优优 化化 建建 模模程序的第程序的第21行表示目标函数（行表示目标函数（7，9）, 第第23, 24

44、行表示约束条件行表示约束条件(7.10),第第26, 27行表示约束条件行表示约束条件(11) , 第第29, 30行表示约束条件行表示约束条件(7.12). LINGO软件的计算结果（仅保留非零变量）如软件的计算结果（仅保留非零变量）如下下:Global optimal solution found at iteration: 9 Objective value: 121.0000 Variable Value Reduced Cost XI( A, X) 3.000000 0.000000 XI( A, Y) 6.000000 0.000000 XI( B, Y) 3.000000 0.0

45、00000优优 化化 建建 模模 XI( B, Z) 5.000000 0.000000 XII( X, 1) 3.000000 0.000000 XII( Y, 2) 5.000000 0.000000 XII( Y, 3) 4.000000 0.000000 XII( Z, 4) 5.000000 0.000000 即工厂即工厂A向仓库向仓库x, y, z分别运输分别运输3, 6, 0个单个单位，工厂位，工厂B向仓库向仓库x, y, z分别运输分别运输0, 3, 5个单位，个单位，仓库仓库x向顾客向顾客1运输运输3个单位，仓库个单位，仓库y向顾客向顾客2, 3分分别运输别运输5, 4个单位

46、，仓库个单位，仓库z向顾客向顾客4运输运输5个单位个单位.总运费为总运费为121个单位个单位.优优 化化 建建 模模 如果将转运问题看成运输问题，可以得到另一如果将转运问题看成运输问题，可以得到另一种程序的编写方法，程序名：种程序的编写方法，程序名： exam0706b.lg4.MODEL: 1! 2 plants, 3 warehouses and 4 customers 2 Transshipment Problem; 3sets: 4 Plant /A,B/ : produce; 5 Warhouse /x,y,z/; 6 Customer /1.4/ : require; 7 Link

47、 ( Plant, Warhouse, Customer) : poss, cost, x; 8endsets 9! Here are the parameters;优优 化化 建建 模模 10data: 11 produce = 9, 8; 12 require = 3, 5, 4, 5; 13 poss = 1, 1, 0, 0, 14 1, 1, 1, 0, 15 0, 0, 0, 0, 16 1, 1, 0, 0, 17 1, 1, 1, 0, 18 0, 1, 1, 1; 19 cost = 6, 8, 0, 0, 20 11, 8, 9, 0, 21 0, 0, 0, 0, 22

48、8,10, 0, 0,优优 化化 建建 模模 23 10, 7, 8, 0, 24 0,10, 9, 6; 25enddata 26! The objective; 27OBJ min = sum( Link: poss * cost * x); 28! The supply constraints; 29for(Plant(i): SUP 30 sum(Warhouse(j): 31 sum(Customer(k): poss(i,j,k)*x(i,j,k)=1; 24!For city i, except the base (city 1); 25for(cities(i) | i #gt

49、# 1 :优优 化化 建建 模模 26! It must be entered; 27 sum(cities(j)| j #ne# i: x(j,i)=1; 28! level(j)=levle(i)+1, if we link j and i; 29 for(cities(j)| j #gt# 1 #and# j #ne# i : 30 level(j) = level(i) + x(i,j) 31 - (n-2)*(1-x(i,j) + (n-3)*x(j,i); 32 ); 33! The level of city is at least 1 but no more n-1, 34 a

50、nd is 1 if it links to base (city 1); 35 bnd(1,level(i),999999); 36 level(i)= level(i) + x(i,j) 31 - (n-2)*(1-x(i,j) + (n-3)*x(j,i); 32 ); 33);优优 化化 建建 模模 34! Make the xs 0/1; 35for(link : bin(x); 36! For the first and last stop; 37for(cities(i) | i #gt# 1 : 38 level(i)=1+(n-2)*x(i,1); 40); END水平变量水