优化建模与LINGO第07章.ppt

《优化建模与LINGO第07章.ppt》由会员分享，可在线阅读，更多相关《优化建模与LINGO第07章.ppt（180页珍藏版）》请在三一办公上搜索。

1、欢迎各位同学学习第七章,内容导航 概述7.1运输问题与转运问题7.2最短路问题和最大流问题7.3最优连线问题与旅行商问题7.4计划评审方法和关键路线法 习题 七,第 7 章 图论与网络模型,本章内容概述 本章介绍图论与网络(Graph Theory and Network)的有关优化问题模型。在这里，我们并不打算全面系统介绍图论与网络的知识，而着重介绍与LINDO、LINGO软件有关的组合优化模型和相应的求解过程。如果读者打算深入地了解图论与网络的更全面的知识，请参阅图论或运筹学中的有关书籍.LINDO软件和LINGO软件可以求解一些著名的组合优化问题，这包括最短路问题、最大流问题、运输和转运

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

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

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

5、别求解该运输问题.首先写出LINDO软件的模型（程序），程序名：exam0702.ltx.!3 Warehouse,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)x11+x21+x31=15

6、6)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 2.000000 X21 13.000000 0.000000 X22 0.000000 9.000000 X23 0.00

7、0000 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.000000-6.000000 6)0.000000-2.000000 7)0.000000-6.000000 8)0.000000-5.000000

8、 NO.ITERATIONS=6,事实上，我们关心更多的是那些非零变量，因此,可选择LINDO中的命令（具体方法见第二章的2.3节),只列出非零变量.,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 X21 13.000000 0.000000 X24 12.000000 0.000000 X33 21.000000 0.000000 ROW SLACK OR SURPLUS DUA

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

10、 Warehouse,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 objective;16OBJ min=sum(Routes:c*x);,17!The supply cons

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

12、61.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(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软件中采用集、数据段

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

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

15、+30 x35+13x36+12x41+8x42+11x43+27x44+19x45+14x46-99x51+7x52+10 x53+21x54+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+x35+x36=1 x

16、41+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+x44+x54+x64=1 x15+x25+x35+x45+x55+x65=1 x16+x26+x36+x46+x56+x66=1end,在上述程序中，x51,x61,x62,x63前的系数均为

17、-99,这是因为某人无法做某项工作可以某人做该项工作的收益是,在计算中通常取一个较大的负数就可以.上述程序也没有说明决策变量 是0-1型变量,这是因为对于此类问题线性规划理论已保证了变量 的取值只可能是0或1.,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.

18、000000 X65 1.000000 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,即第1个人做第1项

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

20、 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);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行中的

21、-99意义与LINDO程序中的意义相同，当某人无法做某项工作时，取一个数值较大的负值.LINGO软件计算结果如下（只列出非零变量）:,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

22、0.000000,从上述两个例子，可以看出LINGO软件在处理问题方面要大优于LINDO软件，而且便于推广，只是在编程方面，LINGO程序的编写稍复杂一些.在后面的问题求解中，绝大多数的求解方法是采用LINGO软件计算.对于指派问题，也可以考虑人数不工作数不相等的情况，和考虑支付最小的情况.第一章的例1.5“混合泳接力队员选拔问题”就是属于这一类情况.,例7.5（继例1.5）用LINGO软件求解例1.5.解：在第二章的例2.7给出了该问题的LINDO软件求解方法，这里给出LINGO软件的求解方法，读者可根据问题的求解过程来考查两种软件求解问题的方法，以及每种软件各自的特点.为了便于编写程序，将

23、5名队员的4种泳姿的百米平均成绩重新列在表7-3中.,按第1章所列的规划问题（第章中的式(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 78,67.8,84.6,59.4,12

24、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该程序同样没有限制是01型变量.,下面列出LINGO软件计算结果（仅保留非零变量）:,Global optimal solutio

25、n 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 or Surplus Dual Price OB J 253.2000-1.000000 SUP(5)1.000000 0.000000,即甲游自由泳，乙游蝶泳，丙游仰泳，丁游蛙泳,没有被选拔上.平均成绩为.4132.,7.1.3 转运问题,

26、所谓转运问题(Transshipment Problem)实质上是运输问题的一种，其区别就在于不是将工厂生产出的产品直接送的顾客手中，而是要经过某些中间环节，如仓库、配送中心等.图7-2表示的是3水平分配（即有一个中间环节）的转运问题.,返回导航,1.转运问题的数学表达式,1.转运问题的求解方法,以一个例子为例，给出求解转运问题的两种求解方法.,例7.6（转运问题）设有两个工厂A,B,产量分别为9,8个单位.四个顾客1,2,3,4,需求量分别为3,5,4,5.和三个仓库x,y,z.其中工厂到仓库、仓库到顾客的运费单价分别由表7-4所示.试求总运费最少的运输方案，以及总运费.,表7-4 工厂到仓

27、库、仓库到顾客的运费单价,说明：其中-表示两地无道路通行.,解：写出相应的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,Warhouse):cI,xI;8 LinkII(Warhouse,Customer):cII,xII;9endsets 10!Here are the parame

28、ters;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:cI*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

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

30、24行表示约束条件(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.000000,XI(B,Z)5.000000 0.000000 XII(X,1)3.000000 0.000

31、000 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个单位，仓库z向顾客4运输5个单位.总运费为121个单位.,如果将转运问题看成运输问题，可以得到另一种程序的编写方法，程序名：exam0706b.lg4.,MODEL:1!2 plants,3 warehouses and 4 customers 2 Transshipment

32、 Problem;3sets:4 Plant/A,B/:produce;5 Warhouse/x,y,z/;6 Customer/1.4/:require;7 Link(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

33、 0,0,0,0,22 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)=produce(i);32!The demand constraints;33for(Customer(k):DEM 34 sum(Plant(i):35 sum(Warhouse(j

34、):poss(i,j,k)*x(i,j,k)=require(k);END,排列的.由于引入了参数poss,当两点间无路时，可以定义其长度为0（实际上可以定义成任何数，因为此时poss对应的位置为0，因此，0乘任何数均为0）.程序中采用的其他方法基本上与运输问题是相同的.,LINGO软件的计算结果（仅保留非零变量）如下,Global optimal solution found at iteration:11 Objective value:121.0000 Variable Value Reduced Cost X(A,X,1)3.000000 0.000000 X(A,Y,2)5.0000

35、00 0.000000 X(A,Y,3)1.000000 0.000000 X(B,Y,3)3.000000 0.000000 X(B,Z,4)5.000000 0.000000,从上述求解过程可以看出，转运问题仍属于线性规划问题，因此也可以用LINDO软件求解，读者可将此问题作为LINDO软件的训练，用LINDO软件求解例7.6,并与LINGO软件的结果相比较.,7.2 最短路问题和最大流问题,本节内容导航 本节概述 7.2.1 最短路问题 7.2.2 最大流问题最小费与最大流问题,本节内容概述 最短路问题(Shortest Path Problems)和最大流问题(Maxiumum Flo

36、w Problems)是图论另一类与优化有关的问题，对于这两在问题，实际上，图论中已有解决的方法，如最短路问题的求解方法有Dijkstra算法，最大流问题的求解方法有标号算法.这里主要讨论的是如何用LINGO软件来求解最短路和最大流问题，对于LINDO软件的求解方法，作者可以根据模型自己设计相应的程序，作为LINDO软件的训练和问题的练习.,返回导航,7.2.1 最短路问题,例7.7（最短路问题）在图 7-3中，用点表示城市，现有 共7个城市.点与点之间的连线表示城市间有道路相连.连线旁的数字表示道路的长度.现计划从城市 到城市 铺设一条天然气管道，请设计出最小价格管道铺设方案.,例7.7的本

37、质是求从城市 到城市 的一条最短路.为便于讨论，下面给出有关概念的明确定义.,返回导航,1.图的基本概念,定义7.2(子图与赋权图),定义7.3(迹和路以及圈),定义7.4（邻接矩阵和赋权矩阵）如果,则称 与 邻接,具有 个顶点的图的邻接矩阵(Adjacency Matrix)是一个 阶矩阵,其分量为,个顶点的赋权图的赋权矩阵是一个阶 矩阵,其分量为,定理7.1 如果存在 到 的途径,则一定存在 到 的路.如果图 的顶点个数为,则这个路的长度小于等于.,2.最短路问题的数学表达式,假设图有 个顶点，现需要求从顶点1到顶点 的最短路.设决策变量为,当,说明弧 位于顶点1至顶点 的路上；否则.其数

38、学规划表达式为,3.最短路问题的求解过程,在第三章中（例3.5）我们接触到了最短路问题的求解，当时的求解方法是按照Dijkstra算法设计的，下面介绍的方法是按照规划问题 设计的.,例7.8(继例7.7)求例7.7中，从城市A到城市D的 最短路.,解：写出相应的LINGO程序，程序名:exam0708.lg4.,MODEL:1!We have a network of 7 cities.We want to find 2 the length of the shortest route from city 1 to city 7;3,4sets:5!Here is our primitive

39、set of seven cities;6 cities/A,B1,B2,C1,C2,C3,D/;7 8!The Derived set roads lists the roads that 9 exist between the cities;10 roads(cities,cities)/11 A,B1 A,B2 B1,C1 B1,C2 B1,C3 B2,C1 B2,C2 B2,C3 12 C1,D C2,D C3,D/:w,x;13endsets 14 15data:16!Here are the distances that correspond,17 to above links;1

40、8 w=2 4 3 3 1 2 3 1 1 3 4;19enddata 20 21n=size(cities);!The number of cities;22min=sum(roads:w*x);23for(cities(i)|i#ne#1#and#i#ne#n:24 sum(roads(i,j):x(i,j)=sum(roads(j,i):x(j,i);25sum(roads(i,j)|i#eq#1:x(i,j)=1;END,在上述程序中，21句中的n=size(cities)是计算集cities的个数，这里的计算结果是,这样编写方法目的在于提高程序的通用性.22句表示目标函数(14),即

41、求道路的最小权值.23,24句表示约束(15)中 的情况，即最短路中中间点的约束条件.25句表示约束中 的情况，即最短路中起点的约束.,约束(15)中 的情况，也就是最短路中终点的情况，没有列在程序中，因为终点的约束方程与前个方程相关.当然，如果你将此方程列入到LINGO程序中，计算时也不会出现任何问题，因为LINGO,软件可以自动删除描述线性规划可行解中的多余方程.,LINGO软件计算结果（仅保留非零变量）如下,Global optimal solution found at iteration:0 Objective value:6.000000 Variable Value Reduce

42、d Cost X(A,B1)1.000000 0.000000 X(B1,C1)1.000000 0.000000 X(C1,D)1.000000 0.000000,即最短路是,最短路长为6个单位.,例7.9(设备更新问题)张先生打算购买一辆新轿车，轿车的售价是12万元人民币.轿车购买后，每年的各种保险费养护费等费用由表7-5所示.如果在5年之内，张先生将轿车售出，并再购买新年.5年之内的二手车销售价由表7-6所示.请你帮助张先生设计一种购买轿车的方案，使5年内用车的总费用最少.,表7-5 轿车的维护费,表7-6 二手车的售价,分析：设备更新问题是动态规划 的一 类 问题（事实上，最短路问题也

43、是动态规划的一类问题）,这里借助于最短路方法解决设备更新问题.,解：用6个点（1，2，3，4，5，6）表示各年的开始，各点之间的边从边表示左端点开始年至表示右端点结束所花的费用，这样构成购车消费的网络图，如图图7.4所示.,记 表示第 年开始到 年结束购车的总销费,即,由此得到,写出相应的LINGO程序，程序名：exam0709.lg4,MODEL:1sets:2 nodes/1.6/;3 arcs(nodes,nodes)|,11enddata 12n=size(nodes);13min=sum(arcs:c*x);14for(nodes(i)|i#ne#1#and#i#ne#n:15 su

44、m(arcs(i,j):x(i,j)=sum(arcs(j,i):x(j,i);16sum(arcs(i,j)|i#eq#1:x(i,j)=1;END,程序中的第3句中&1#1t#&2是逻辑运算语句，表示所说明的变量只有行小于列的部分，因此所说明的矩阵是上三角阵.,LINGO软件的计算结果（仅保留非零变量）如下 Global optimal solution found at iteration:0 Objective value:31.00000 Variable Value Reduced Cost X(1,2)1.000000 0.000000 X(2,4)1.000000 0.0000

45、00 X(4,6)1.000000 0.000000,即第1年初购买轿车，第2年初卖掉，再购买新车，到第4年初卖掉，再购买新车使用到第5年末，总费用31万元.,当然，上述方案不是唯一的，例如还有 和,但无论何种方案，总费用均是31万.,例7.10（无向图的最短路问题）求图7-5中 到的最短路.,分析：不论是例7.7、例7.9还是第三章的例3.5处理的问题均属于有向图的最短路问题，本例是处理无向图的最短路问题，在处理方式上与有向图的最短路有一些差别.,解：对于无向图的最短路问题，可以这样理解，从点 到点 和点 到点 的边看成有向弧，其他各条边均看成有不同方向的双弧，因此，可以按照前面介绍有向图的

46、最短路问题来编程序，但按照这种方法编写LINGO程序相当边（弧）增加了一倍.这里选择邻接矩阵和赋权矩阵的方法编写LINGO程序.,写出相应的LINGO程序，程序名：exam0710.lg4,MODEL:1sets:2 cities/1.11/;3 roads(cities,cities):p,w,x;4endsets 5data:6 p=0 1 1 1 0 0 0 0 0 0 0 7 0 0 1 0 1 0 0 0 0 0 0 8 0 1 0 1 1 1 1 0 0 0 0 9 0 0 1 0 0 0 1 0 0 0 0 10 0 1 1 0 0 1 0 1 1 0 0,11 0 0 1 0

47、1 0 1 0 1 0 0 12 0 0 1 1 0 1 0 0 1 1 0 13 0 0 0 0 1 0 0 0 1 0 1 14 0 0 0 0 1 1 1 1 0 1 1 15 0 0 0 0 0 0 1 0 1 0 1 16 0 0 0 0 0 0 0 0 0 0 0;17 w=0 2 8 1 0 0 0 0 0 0 0 18 2 0 6 0 1 0 0 0 0 0 0 19 8 6 0 7 5 1 2 0 0 0 0 20 1 0 7 0 0 0 9 0 0 0 0 21 0 1 5 0 0 3 0 2 9 0 0 22 0 0 1 0 3 0 4 0 6 0 0,23 0 0 2

48、9 0 4 0 0 3 1 0 24 0 0 0 0 2 0 0 0 7 0 9 25 0 0 0 0 9 6 3 7 0 1 2 26 0 0 0 0 0 0 1 0 1 0 4 27 0 0 0 0 0 0 0 9 2 4 0;28enddata 29n=size(cities);30min=sum(roads:w*x);31for(cities(i)|i#ne#1#and#i#ne#n:32 sum(cities(j):p(i,j)*x(i,j)33=sum(cities(j):p(j,i)*x(j,i);34sum(cities(j):p(1,j)*x(1,j)=1;END,在上述程序

49、中，第6行到第16行给出了图的邻接矩阵，到 和 到 的边按单向计算，其余边双向计算.第17行到第27行给出了图的赋权矩阵,注意：由于有了邻接矩阵，两点无道路连接时，权值可以定义为0.其它的处理方法基本上与有向图相同.,用LINGO软件求解，得到（仅保留非零变量）Global optimal solution found at iteration:2 0 Objective value:13.00000 Variable Value Reduced Cost,X(1,2)1.000000 0.000000 X(2,5)1.000000 0.000000 X(3,7)1.000000 0.0000

50、00 X(5,6)1.000000 0.000000 X(6,3)1.000000 0.000000 X(7,10)1.000000 0.000000 X(9,11)1.000000 0.000000 X(10,9)1.000000 0.000000,即最短路径为,最短路长度.,为13,7.2.2 最大流问题,例7.11（最大流问题）现需要将城市s的石油通过管道运送到城市t，中间有4个中转站 和,城市与中转站的连接以及管道的容量如图7-6所示，求从城市s到城市t的最大流.,返回导航,图7-6给出的有一个源和一个汇的网络.网络 中每一条边 有一个容量,除此之外,对边 还有一个通过边的流(Flow