优化建模与lingo第07章

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

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

3、LINGO软件求解运输问题.但为便于后面的叙述，先给出图论中有关图的部分定义.图7-1:m个产地,n 个销售地运输问题的图形 优化建模1. 图的基本定义从直观上看, 所谓图是由点和边组成的图形, 如图7-1所示.下面我们给出图的定义. 优化建模注：通常有向图的边称为弧，由弧构成的集记为A, 因此，有向图记为, 而无向图记为. 为G(V , A)G(V , E)方便起见，在后面的论述中，有时也用向图.表示有G(V , E)在无向图中, 每条至多有一条边的图称为简单图(Simple Graph). 若每一对不同的顶点都有一条边相连的简单图称为完全图(Complete Graph). 若一个图, 使

4、得任何一中的顶点集可以分解为两个子集V1 和V2中, 另一个端点在 V2中, 这种图条边都有一个端点在V1称为二部图或偶图(BipartVi1te Graph). 运输问题所构成的图7-1是偶图. 优化建模2. 运输问题的数学表达式mn cij xij .i =1j =1第 i 个产地的运出量应小于或等于该地的生产量，即：n xij ai .j =1第j 个销地的运入量应等于该地的需求量，即：m xij i =1= b j . 优化建模因此，运输问题的数学表达式为:称具有形如式 (1) (4) 的线性规划问题为运输问题. 优化建模3. 运输问题的求解过程为了便于讨论，以一个运输问题实例的求解过

5、程来介绍如何用LINDO或LINGO软件求解运输问题模型.例7.2(继例7.1)即为有3个产地和设m = 3, n = 44个销地的运输问题，其产量、销量及单位运费如表7-1所示.试求总运费最少的运输方案，以及总 运费. 优化建模解：从前面的分析来看，运输问题属于线性规划问题，因此，不论是LINDO软件或LINGO软件都可以对该问题求解.为了便于比较两种软件的优缺点，以及各自的特点，我们用两种软件分别求解该运输问题.首先写出LINDO软件的模型（程序），程序名：exam0702.ltx.! 3 Warehouse, 4 Customer Transportation Problem! The

6、objectivemin6x11 + 2x12 + 6x13 + 7x14+ 4x21 + 9x22 + 5x23 + 3x24+ 8x31 + 8x32 +x33 + 5x34subject to 优化建模! The supply constraints2)3)4)x11 + x12 + x13 + x14 = 30 x21 + x22 + x23 + x24 = 25x31 + x32 + x33 + x34 = 21! The demand constraints5)6)7)8)x11 + x21 + x31 = 15 x12 + x22 + x32 = 17 x13 + x23 + x

7、33 = 22x14 + x24 + x34 = 12end 优化建模LINDO软件的计算结果如下：LP OPTIMUM FOUND AT STEP6OBJECTIVE FUNCTION VALUE1)161.0000VARIABLEX11VALUEREDUCED COST 0.0000000.0000000.0000002.0000000.0000009.0000001.0000002.000000X12 X13 X14 X21 X22X2317.0000001.0000000.00000013.0000000.0000000.000000 优化建模X2412.0000000.0000000

8、.00000021.0000000.0000000.0000007.00000011.0000000.0000005.000000X31 X32 X33X34ROW 2)3)4)5)6)7)8)SLACK OR SURPLUSDUAL PRICES10.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000002.0000005.000000-6.000000-2.000000-6.000000-5.0000006NO. ITERATIONS= 优化建模事实上，我们关心更多的是那些非零变量，因此,可选择LINDO中的命令（具体方

9、法见第二章的2.3节), 只列出非零变量.OBJECTIVE FUNCTION VALUE1)161.0000VARIABLEX11VALUEREDUCED COST 0.0000000.0000002.000000X1217.000000 优化建模X13X21 X24 X33 ROW 3)4)5)6)7)8)1.00000013.00000012.00000021.0000000.0000000.0000000.0000000.000000SLACK OR SURPLUSDUAL PRICES0.0000000.0000000.0000000.0000000.0000000.0000002.

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

11、 a;4 Customer/1.4/: b; 优化建模5Routes( Warehouse, Customer) : c, x; 6endsets7! Here are the parameters;8data:910111213a = 30, 25, 21b = 15, 17, 22, 12;c =6,2,6,7,4,9,5,3,8,8,1,5;14enddata15! The objective;16OBJ min = sum( Routes: c * x); 优化建模17 ! The supply constraints;18 for( Warehouse(i): SUP19sum( C

12、ustomer(j): x(i,j) = a(i);20! The demand constraints; 21for( Customer(j): DEM22sum( 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:6Objective value:Variable X( 1, 1)X( 1, 2)X(

13、1, 3)X( 2, 1)X( 2, 4)X( 3, 3)161.0000Reduced Cost 0.0000000.0000000.0000000.0000000.0000000.000000Value 2.00000017.000001.00000013.0000012.0000021.00000Row OBJSUP( 1)Slack or Surplus 161.000010.00000Dual Price-1.0000000.000000 优化建模从上述求解过程来看，两种软件的计算结果是相同的，但由于LINGO软件中采用集、数据段 和循环函数的编写方式，因此更便于程序推广到一般形式使

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

15、j ,当第 ij 项工作时，xij = 1,个人作第. 因此，相应的线性规划问题为否则= 0xijmncij xij； (5)i=1 j =1minn xijj =1= 1,i =1, 2,s.t., n，(每个人做一项工作) (6)n xij= 1,j = 1, 2,j = 1, 2, n,(每项工作有一个人去做)(7)i=1xij= 0或1, n. (8) 优化建模2. 指派问题的求解过程分别用LINDO软件和LINGO软件求解指派问题，并对两种软件的求解方法与各自的优缺点进行比较.例7.4（继例7.3）考虑例7.3中 n = 6 的情况,即6个人做6项工作的最优指派问题，其收益矩阵如表7

16、-2所示. 优化建模解：与运输问题一样，先用LINDO软件求解.给出LINGO程序，程序名exam0704.ltx! Assignment model! Maximize valve of assignmentsmax20x11 + 15x12 + 16x13 +5x14 +4x15 +7x16+ 17x21 + 15x22 + 33x23 + 12x24 +8x25 +6x26+9x31 + 12x32 + 18x33 + 16x34 + 30x35 + 13x36+ 12x41 +8x42 + 11x43 + 27x44 + 19x45 + 14x46- 99x51 +7x52 + 10x

17、53 + 21x54 + 10x55 + 32x56- 99x61 - 99x62 - 99x63 +6x64 + 11x65 + 13x66subject to 优化建模! Each person must be assigned to some jobx11 + x12 + x13 + x14 + x15 + x16 x21 + x22 + x23 + x24 + x25 + x26 x31 + x32 + x33 + x34 + x35 + x36 x41 + x42 + x43 + x44 + x45 + x46 x51 + x52 + x53 + x54 + x55 + x56x61

18、 + x62 + x63 + x64 + x65 + x66= 1= 1= 1= 1= 1= 1! Each job must receive an assignmentx11 + x21 + x31 + x41 + x51 + x61 x12 + x22 + x32 + x42 + x52 + x62 x13 + x23 + x33 + x43 + x53 + x63 x14 + x24 + x34 + x44 + x54 + x64 x15 + x25 + x35 + x45 + x55 + x65 x16 + x26 + x36 + x46 + x56 + x66end= 1= 1= 1

19、= 1= 1= 1 优化建模在上述程序中， x51, x61, x62, x63前的系数均为-99, 这是因为某人无法做某项工作可以某人做该项工作的收益是 - , 在计算中通常取一个较大的负数就可以.x是0-1型变量,上述程序也没有说明决策变量这是因为对于此类问题线性规划理论已保证了变量x的取值只可能是0或1.LINDO软件给出的计算结果如下（只列出非零变量）: 优化建模OBJECTIVE FUNCTION VALUE1)135.0000VARIABLE X11X23 X32 X44 X56X65VALUEREDUCED COST 0.0000000.0000000.0000000.00000

20、00.0000000.0000001.0000001.0000001.0000001.0000001.0000001.000000ROWSLACK OR SURPLUSDUAL PRICES 优化建模2)3)5)7)8)9)10)11)12)13)0.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000003.00000015.000000-4.000000-19.00000017.00000012.00000018.00000031.00000030.00000032.00000020NO.

21、ITERATIONS= 优化建模即第1个人做第1项工作，第2个人做第3项工作,第3个人做第2项工作，第4个人做第4项工作，第5 个人做第6项工作，第6个人做第5项工作. 总效益值为135.下面用LINGO程序再求解此问题，程序中仍然 用到集、数据段和循环函数.写出相应的LINGO程序，程序名exam0704.lg4.MODEL:1! Assignment Problem Model; 2sets:3Flight/1.6/;4Assign(Flight, Flight): c, x; 优化建模5endsets6! Here is income matrix; 7data:8910111213c

22、= 2017912-99-99151512816331811512162748301910117613143213;71021-99-99614enddata15 优化建模16! Maximize valve of assignments; 17max = sum(Assign: c*x);18for(Flight(i):19!2021!2223); ENDEach i must be assigned to some j; sum(Flight(j): x(i,j) = 1;Each I must receive an assignment;sum(Flight(j): x(j,i) = 1

23、; 优化建模程序中第12 13行中的-99意义与LINDO程序中的意义相同，当某人无法做某项工作时，取一个 数值较大的负值.LINGO软件计算结果如下（只列出非零变量）:Global optimal solution found at iteration: 0Objective value:Variable X( 1, 1)X( 2, 3)X( 3, 2)X( 4, 4)X( 5, 6)X( 6, 5)135.0000Reduced Cost 0.0000000.0000000.0000000.0000000.0000000.000000Value 1.0000001.0000001.0000

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

25、题的 方法，以及每种软件各自的特点.为了便于编写程序，将5名队员的4种泳姿的百米平均成绩重新列在表7-3中. 优化建模按第1章所列的规划问题（第章中的式(1.25) 式(1.28)）写出相应的LINGO程序， 程序名：exam0705.lg4.MODEL:1! 5 persons and 4 jobs Assignment Problem; 2sets:345Person /1.5/;Job/1.4/;Assign( Person, Job) : c, x;6endsets7! Here are the parameters; 8data: 优化建模9 c =1011121366.8, 75.

26、6, 87,58.6,57.2, 66,66.4, 53,78,70,67.8, 84.6, 59.4,74.2, 69.6, 57.2,67.4, 71,83.8, 62.4;14 enddata15 ! The objective;16OBJ min = sum( Assign: c * x); 17! The supply constraints;18for( Person(i): SUP19sum( Job(j): x(i,j) = 1);20! The demand constraints; 21for( Job(j): DEM22sum( Person(i): x(i,j) = 1

27、); END该程序同样没有限制 xij是01型变量. 优化建模下面列出LINGO软件计算结果（仅保留非零变 量）:Global optimal solution found at iteration:9Objective value:253.2000Reduced Cost0.0000000.0000000.0000000.000000Variable X( 1, 4)X( 2, 1)X( 3, 2)X( 4, 3)Value 1.0000001.0000001.0000001.000000RowSlack or SurplusDual Price-1.000000OB J 1.0000002

28、53.20000.000000SUP( 5)即甲游自由泳，乙游蝶泳，丙游仰泳，丁游蛙泳,没有被选拔上.平均成绩为. 4132. 优化建模返回导航7.1.3转运问题所谓转运问题(Transshipment Problem)实质上是运输问题的一种，其区别就在于不是将工厂生产出的产品直接送的顾客手中，而是要经过某些中间环节，如仓库、配送中心等.图7-2表示的是3水平分配（即有一个中间环节）的转运问题. 优化建模1.转运问题的数学表达式 优化建模ln+x12 x2minc;(9)ijjkjkj =1 k =1lij1 a ,i = 1, 2,s.t.xm,(运出量应不大于生产量)(10)ij =1mn

29、i=1j =1x1=j = 1, 2,12xx, l, (运入量应等于运出量)(11)ijjkk =1lx= b ,k = 1, 2,2n,(运入量应等于需求量)(12)jkk 0, x2 0. 优化建模1.转运问题的求解方法以一个例子为例，给出求解转运问题的两种求解方法.例7.6（转运问题）设有两个工厂A, B, 产量分别为9, 8个单位. 四个顾客1, 2, 3, 4, 需求量分别为3, 5,4, 5. 和三个仓库x, y, z. 其中工厂到仓库、仓库到顾客的运费单价分别由表7-4所示.试求总运费最少的运输方案，以及总运费. 优化建模表7-4工厂到仓库 、仓库到顾客的运费单价说明：其中-表

30、示两地无道路通行.解：写出相应的LINGO程序，程序名：exam0706a.lg4.AB1234xy z152 优化建模MODEL:1! 2 plants, 3 warehouses and 4 customers2Transshipment Problem;3sets:45678Plant/A, B/ : produce;Warhouse /x, y, z/;Customer /1.4/ : require;LinkI( Plant, Warhouse) : cI, xI;LinkII ( Warhouse, Customer) : cII, xII;9endsets10! Here are

31、 the parameters; 11data:12produce = 9, 8; 优化建模131415161718require = 3, 5, 4, 5;cI= 1, 2, 100,3, 1,2;cII = 5, 7, 100, 100,9, 6,7, 100,100, 8,7,4;19enddata20! The objective;21OBJ min = sum(LinkI: cI * xI)+sum(LinkII: cII * xII);22! The supply constraints; 23for( Plant(i): SUP24sum( Warhouse(j): xI(i,j

32、) = produce(i); 优化建模25 ! The warhouse constraints;26 for( Warhouse(j): MID27sum( Plant(i): xI(i,j)=sum( Customer(k): xII(j,k);28! The demand constraints; 29for( Customer(k): DEM30sum( Warhouse(j): xII(j,k) = require(k); END在上述程序中，由14至15行定义的cI是工厂到仓库的运费，由16至18行定义的cII是仓库到顾客的运费.我们的目标是求最小运费，因此当两点无 道路时，认为

33、是运费无穷大.为了便于计算，只要取 较大的数值就可以了，这里的取值为100. 优化建模程序的第21行表示目标函数（7，9）, 第23, 24行表示约束条件(7.10),第26, 27行表示约束条件(11)第29, 30行表示约束条件(7.12).LINGO软件的计算结果（仅保留非零变量）如下:Global optimal solution found at iteration:9,Objective value:Variable XI( A, X)XI( A, Y)XI( B, Y)121.0000Reduced Cost0.0000000.0000000.000000Value 3.0000

34、006.0000003.000000 优化建模XI( B, Z)XII( X, 1)XII( Y, 2)XII( Y, 3)XII( Z, 4)5.0000003.0000005.0000004.0000005.0000000.0000000.0000000.0000000.0000000.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个单位. 优化建模如果将转运问题看成运输问题，可以得到另一种程序的

35、编写方法，程序名： exam0706b.lg4.MODEL:1! 2 plants, 3 warehouses and 4 customers2Transshipment Problem;3sets:4567Plant/A,B/ : produce;Warhouse /x,y,z/;Customer /1.4/ : require;Link( Plant, Warhouse, Customer) : poss, cost, x;8endsets9! Here are the parameters; 优化建模10data:111213141516171819202122produce = 9,

36、8;require = 3, 5, 4, 5;poss = 1, 1, 0, 0,1, 1, 1, 0,0, 0, 0, 0,1, 1, 0, 0,1, 1, 1, 0,0, 1, 1, 1;cost = 6, 8, 0, 0,11, 8, 9, 0,0, 0, 0, 0,8,10, 0, 0, 优化建模232410, 7, 8, 0,0,10, 9, 6;25 enddata26 ! The objective;27OBJ min = sum( Link: poss * cost * x); 28! The supply constraints; 29for(Plant(i): SUP303

37、1sum(Warhouse(j):sum(Customer(k): poss(i,j,k)*x(i,j,k)=produce(i);32 ! The demand constraints;33 for(Customer(k): DEM 34sum(Plant(i):35ENDsum(Warhouse(j): poss(i,j,k)*x(i,j,k)=require(k); 优化建模A x 1 A y 1 A z 1 B x 1 B y 1B z 1A x 2 A y 2 A z 2 B x 2 B y 2B z 2A x 3 A y 3 A z 3 B x 3 B y 3B z 3A x 4

38、A y 4 A z 4 B x 4 B y 4B z 4排列的.由于引入了参数poss, 当两点间无路时，可以定义其长度为0（实际上可以定义成任何数，因为此时poss 对应的位置为0，因此，0乘任何数均为0）.程序中采用的其他方法基本上与运输问题是相同的. 优化建模LINGO软件的计算结果（仅保留非零变量）如下Global optimal solution found at iteration:11Objective value:Variable X( A, X, 1)X( A, Y, 2)X( A, Y, 3)X( B, Y, 3)X( B, Z, 4)121.0000Reduced Cos

39、t0.0000000.0000000.0000000.0000000.000000Value 3.0000005.0000001.0000003.0000005.000000 优化建模从上述求解过程可以看出，转运问题仍属于线性规划问题，因此也可以用LINDO软件求解，读者可将此问题作为LINDO软件的训练，用LINDO软件 求解例7.6, 并与LINGO软件的结果相比较. 优化建模本节内容导航本节概述7.2.1 最短路问题7.2.2 最大流问题7.2.3 最小费与最大流问题7.2最短路问题和最大流问题 优化建模本节内容概述返回导航最短路问题(Shortest Path Problems)和最大

40、流问题(Maxiumum Flow Problems)是图论另一类与优化有关的问题，对于这两在问题，实际上，图论中已 有解决的方法，如最短路问题的求解方法有Dijkstra 算法，最大流问题的求解方法有标号算法.这里主要讨论的是如何用LINGO软件来求解最短路和最大流问题，对于LINDO软件的求解方法，作者可以根据模型自己设计相应的程序，作为LINDO软件的训练和问题的练习. 优化建模返回导航7.2.1最短路问题例7.7 （最短路问题） 在图 7-3中，用点表示城共7个城市.点与点之间的连线市，现有A, B1, B2 ,C1,C2 ,C3 , D表示城市间有道路相连.连线旁的数字表示道路的长度

41、.现计划从城市到城A 市铺D设一条天然气管道，请设计出最小价格管道铺设方案.例7.7的本质是求从城市A到城市D 的一条最短路.为便于讨论，下面给出有关概念的明确定义. 优化建模1. 图的基本概念定义7.2(子图与赋权图)定义7.3(迹和路以及圈) 优化建模定义7.4（邻接矩阵和赋权矩阵）如果 (ui , vj ) E ,则称 v j 与vi邻接, 具有 n个顶点的图的邻接矩阵(Adjacency Matrix)是一个 n n阶矩阵分量为A = (aij )nn, 其= 1, (v i , v j ) Ea0, 其他.ij 优化建模nWn n个顶点的赋权图的赋权矩阵是一个阶矩阵= (wij )n

42、n ,其分量为= w(v i , v j ), (v i , v j ) Ea, 其他.ij定理7.1如果存在 u 到v 的途径, 则一定存在 u 到 v 的路. 如果图 G的顶点个数为 n, 则这个路的长度小于等于 n -1. 优化建模2. 最短路问题的数学表达式个顶点，现需要求从顶点1到顶点 n假设图有的最短路.设决策变量为x,ij当位(i, j)=,1说明弧xij的n于顶点1至顶点达式为路上；否则. 其数学规划表wij xij ;(i, j )Emin(14)1, i = 1,x= -1, i = n, ;nnx-s.t.(15)ijji0, i 1, n.j =j =11E(i, j

43、)xijE( j ,i ) 0, (i, j) E.(16) 优化建模3. 最短路问题的求解过程在第三章中（例3.5）我们接触到了最短路问题的求解，当时的求解方法是按照Dijkstra算法设计的，(14)设 (1计5)的.下面介绍的方法是按照规划问题例7.8 (继例7.7)最短路.求例7.7中，从城市A到城市D的解：写出相应的LINGO程序，程序名: exam0708.lg4.MODEL:1 ! We have a network of 7 cities. We want to find2 the length of the shortest route from city 1 to city

44、 7; 3 优化建模4sets:56789101112! Here is our primitive set of seven cities;cities/A, B1, B2, C1, C2, C3, D/;! The Derived set roads lists the roads that exist between the cities;roads(cities, cities)/A,B1A,B2B1,C1B1,C2B1,C3B2,C1B2,C2B2,C3C1,DC2,DC3,D/: w, x;13endsets 1415data:16! Here are the distances

45、that correspond 优化建模17to above links;18w = 24331231134;19enddata 2021n=size(cities); ! The number of cities; 22min=sum(roads: w*x);23for(cities(i) | i #ne# 1 #and# i #ne# n:24sum(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)是计算集c

46、ities的个数，这里的计算结果是 n = 7, 这样编写方法目的在于提高程序的通用性.22句表示目标函数(14), 即求道路的最小权值.23, 24句表示约束i 1,i n(15) 中的情况，即最短路中中间点的约束条件.25句表示约束中起点的约束.约束(15)中 i = n的情况，也就是最短路中终点的情况，没有列在程序中，因为终点的约束方程与前个方程相关.当然，如果你将此方程列入到LINGO程序中，计算时也不会出现任何问题，因为LINGOi = 1的情况，即最短路中 优化建模软件可以自动删除描述线性规划可行解中的多余方程.LINGO软件计算结果（仅保留非零变量）如下Global optima

47、l solution found at iteration:0Objective value:Variable X( A, B1)X( B1, C1)X( C1, D)6.000000Reduced Cost0.000000Value1.0000001.0000001.0000000.0000000.000000 D , 最短路长为6个单位.即最短路是A B1 C1 优化建模例7.9(设备更新问题)张先生打算购买一辆新轿车，轿车的售价是12万元人民币.轿车购买后， 每年的各种保险费养护费等费用由表7-5所示.如果在5年之内，张先生将轿车售出，并再购买新年.5 年之内的二手车销售价由表7-6所示

48、.请你帮助张先生设计一种购买轿车的方案，使5年内用车的总费用最少.表7-5 轿车的维护费车龄/年01234费用/万元245912 优化建模表7-6 二手车的售价分析： 设备更新问题是动态规划 的一 类 问题（事实上，最短路问题也是动态规划的一类问 题）,这里借助于最短路方法解决设备更新问题.解： 用6个点（1，2，3，4，5，6）表示各年的开始，各点之间的边从边表示左端点开始年至 表示右端点结束所花的费用，这样构成购车消费 的网络图，如图图7.4所示.车龄/年12345售价/万元76210 优化建模记 cij表示第 i 年开始到总销费, 即年结束购车的j -1= 在第i年到第j -1年结束轿车的维护费用cij +在i年开始新车的购买费用 -在第j年开始二手的销售人 优化建模由此得到= 2 + 12 - 7 = 7,= 2 + 4 + 12 - 6 = 12,= 2 + 4 + 5 + 12 -1 = 21,= 2 + 4 + 9 + 5 + 12 -1 = 31,= 2 + 4 + 9 + 5 + 12 + 1 - 0 = 44,= 2 + 12 - 7 = 7,= 2 + 4 + 12 - 6 = 12,= 2 + 4 + 5 + 12 -1 = 21,= 2 + 4 + 9 + 5 + 12 -1 = 31,= 2 + 12 - 7 = 7,= 2 + 4 +