利用LINGO建立最优化模型.doc

利用LINGO建立最优化模型洪文1，朱云鹃1，金震1，王其文2 1（安徽大学商学院 合肥 230039）2（北京大学光华管理学院 北京 100871）摘 要：本文借助于最优化软件LINGO建立了最小树、最短路、最大流、最小费用流和货郎担问题的LINGO模型，并对模型中的难点给出了注释。利用本文提供的模型，可以很容易地求出上述5个最优化问题的最优解。关键词：最小树、最短路、最大流、最小费用流、货郎担问题、LINGO中图分类号：0211.6 文献标识码：A 文章编号：0 引 言求解最小树、最短路、最大流、最小费用流和货郎担问题的方法虽然很多，但是利用最优化求解软件LINGO建立相应的模型来求解上述5个问题是一种新的尝试。本文建立的模型有两个突出的特点。第一个特点是模型的数据与公式完全分离，这样使得问题的求解变得特别方便（对于不同的问题只要更换数据即可）。第二个特点是这五个模型都是利用最优化求解软件LINGO编写而成，可进行快速求解。1 LINGO简介LINGO是一个简单而实用的最优化软件。利用线性和非线性最优化的方法，LINGO可以用公式简明地表示复杂的规划问题，并可以快速地求出问题的最优解。LINGO是由美国芝加哥LINDO系统公司研制。该公司根据用户信息、线性和非线性规划的理论和方法及计算机发展的需要不断推出新的版本。目前LINGO已成为世界上最为流行的最优化软件之一。LINGO在我国已经有了相当多的用户。它的主要特点是：1）LINGO含有一系列的接口函数。这些接口函数可用在文本文件、电子表格和数据库中，可与外部的输入/输出源进行连接。2）LINGO可以直接嵌入到Excel中，也可以将Excel嵌入到LINGO模型中。这样就可以将数据与模型分离，使得模型的维护和调试变得非常容易。3）LINGO使用Windows的窗口展开优化分析功能，使用对话框展示各种功能。清晰、直观、易学易用。4）LINGO具有强大的计算功能。众所周知，建模难，求解模型更难。利用LINGO就可以摆脱复杂繁琐的计算烦恼。2 LINGO与LINDO的关系LINGO与LINDO都是美国LINDO系统公司的产品。利用它们都可以求解线性规划，这是它们的共同点。但是两者还是有区别的。1）如果要输入5x+4y70这样一个约束，在LINDO模型中可以直接输入，不需要变动。而在LINGO模型中一定要改成：5*x+4*y70。后者比前者复杂，但这也正是后者的特点：LINGO可以求解非线性规划，而LINDO只能求解线性规划。2）LINGO的集合函数功能非常强大，它可以使我们很容易地处理数据。例如可以利用集合语言将电子表格中数据调入模型，计算后将结果输出到电子表格中。这样，数据和模型就完全分离了，LINGO模型可以不因数据的变动而改动。3）利用LINGO的集合函数可以使我们摆脱处理复杂冗长表达式的烦恼。例如，假设a表示一个单位的职工集合，x表示职工的工资，工资总和就可以用sum(a:x)来表示。不管这个单位是10个人，100个人人还是1000个人，表达式不变，4）如果要在LINGO模型中输入已经建立的LINDO模型，只要使用import lindo file命令即可；如果要将已经建立的LINGO模型变成LINDO模型，只要使用generate命令即可。也就是说LINDO与LINGO线性模型可以相互转换。鉴于LINGO集合函数的强大功能，下面5个最优化问题实例都是LINGO模型。3 最小树问题和模型3.1 最小生成树问题在图论中，称无圈的连通图为树。现实中树的例子很多。例如通讯网、电网、自来水管网和暖气供应网都可以看成是树。这些网络的特点一是连通，二是不会形成圈。在一个连通图G中，如果保留全部顶点，并选择适当的边构成一个子图，并且使这个子图是一棵树，则称这个子图为图G的生成树（或支撑树）。连通图G生成树上各边的权数之和称为该生成树的权。连通图G的权数最小的生成树为图G的最小生成树或称最小树。许多实际问题都可以归结为求最小生成树。例如，如何修筑一些公路把若干个城镇连接起来；如何架设通讯网络将若干个地区连接起来；如何修筑水渠将水源和若干块待灌溉的土地连接起来等等。为了说明问题，请看下面的范例1。范例1：假设某电话公司计划在六个村庄架设电话线，各村庄之间的距离如图1所示。试求出使电话线总长度最小的架线方案。图1 六个村庄电话线路图3.2 最小树模型规定：节点V1表示树根；当两个节点之间没有线路时，规定两个节点之间的距离为M（利用计算机进行求解时换成一个大数，在本例中所有权重之和小于100，可以设M=100）。最小树整数规划模型如下（加重黑线部分根据问题大小做相应调整）：MODEL1 SETS:2CITY/1.6/: ; !定义了图1的点集CITY;3LINK(CITY, CITY): DIST, X,Y;! 定义了图1的边集LINK和属性DIST, X,Y;4ENDSETS5DATA:6DIST=!输入属性DIST的数值（距离）;7! 从 V1 V2 V3 V4 V5 V6;8!从V1; 0 3 1 51001009!从V2; 3 0100 2100 310!从V3; 1100 0 2 310011!从V4; 5 2 2 0 4 112!从V5;100100 3 4 0 213!从V6;100 3100 1 2 0;14ENDDATA15N=SIZE(CITY);!N表示CITY中点的个数;16 SUM(CITY(J)|J#GT#1:X(1,J) =N-1;!从树根V1发出流量N-1; 17FOR(CITY(K)|K#GT#1:!对于根以外的点，流进流量减流出流量等于1;SUM(CITY(I)|I#NE#K:X(I,K)-SUM(CITY(I)|I#NE#K:X(K,I)=1); 18FOR(LINK:X100*Y);!限制流量X大于0时Y等于1;19MIN=SUM(LINK: DIST*Y);!目标函数，使得生成树的权数达到最小;20FOR(LINK:BIN(Y); );!限制Y是0-1变量;END运行模型可以得到： Variable Value Reduced Cost X( 1, 3) 1.000000 1.000000 X( 3, 4) 1.000000 2.000000 X( 4, 2) 1.000000 2.000000 X( 4, 6) 1.000000 1.000000 X( 6, 5) 1.000000 2.000000相应的最小生成树在图1中的用加重黑线部分，最小生成树的权数为8。3.3 LINGO集合模型简介LINGO标量模型是指完全展开的模型。例如，100个约束就要写100个表达式，100个变量就要写100个符号。这种模型与LINDO模型并无实质上的差别。然而，当我们建立成百上千个变量和约束构成的模型时，LINGO标量模型就会显得很冗长。而且这种形式的模型也不利于模型的维护和调试。正是为了克服这一缺点，LINGO集合模型应运而生。LINGO集合模型主要有三部分构成。第一部分用SETS开始，用ENDSETS结束（最小生成树模型中的14）。它是模型的集合域，主要是根据问题来定义集合和属性。例如某工厂计划生产若干个产品，我们就可以定义一个产品集合。考虑到产品有产量、价格、成本等数量特征，故可将它们定义为产品集合的属性。第二部分用DATA开始，用ENDDATA结束（最小生成树模型中的514）。它是模型的数据域，主要是用于输入数据和输出结果。例如，一般来说，产品的价格和成本是数据需要输入，而产品的产量是变量，是想知道的结果，需要输出。LINGO集合模型的第三部分就是除去集合域和数据域以外的其他部分（最小生成树模型中的1520）。这一部分全部由集合函数编写的约束构成（目标函数也看成约束）。而用集合函数编写的约束就能很好地克服LINGO标量模型的缺点。例如，最小生成树模型中的18就表示了36个约束。而最小生成树模型中的19就表示了36个变量与对应距离相乘相加的结果。如果要详细了解LINGO集合模型可参阅参考文献1。另外，模型中所有形如“!“中文”;”的语句是模型的解释语句，可放在模型的任何地方，对模型运行没有影响。4 最短路问题和模型4.1 最短距离问题最短路问题就是在一个网络图中，要求出从某一起点到另一终点的权数最小的通路。它是网络分析中的最基本的最优化问题之一。最短路问题在实际问题中有广泛的应用。例如管道的铺设、线路安排、运输路线的选择、工厂布局等等都会涉及最短距离问题。为了说明问题，请看下面的范例2。范例2：设有一批货物要从v1运到v7边上的数字表示该段路的距离（网络图见图2），求出最短距离的运输路线。图2 货物运输线路图4.2 最短路模型规定当两个节点之间没有线路时，规定两个节点之间的距离为M（利用计算机进行求解时换成一个大数）。最短距离整数规划模型如下（加重黑线部分根据问题大小做相应调整）：MODEL1 SETS:2CITY/1.7/: ; !定义了图2的点集CITY;3LINK(CITY, CITY): DIST, X; 定义了图2的边集LINK和属性DIST, X;4ENDSETS5DATA:6DIST=!输入属性DIST的数值（距离）;7! 从 V1 V2 V3 V4 V5 V6V7;8!从V1; 0 1 41001001001009!从V2; 1 0 2 4 2 510010!从V3; 4 2 0100100 110011!从V4;100 4100 0 210010012!从V5;100 2 1 2 0 3 213!从V6;100 5 1100 3 0 614!从V7;100100100100 2 6 0;15S=?;!S表示要选择的始点;16T=?;!T表示要选择的终点;17ENDDATA18FOR(CITY(I):X(I,S)=0);!限制流入始点;19FOR(CITY(I):X(T,I)=0);!限制流出终点;20FOR(CITY(I)|I#ne#T#and#I#ne#S:!对于中间点满足：流进量=流出量;SUM (CITY(J):X(I,J)= SUM (CITY(K):X(K,I) );21min=SUM(LINK: DIST*X);!目标函数;22SUM(CITY(I):X(S,I)=1;!流出1;END运行模型可以得到：Variable Value Reduced Cost X( 1, 2) 1.000000 1.000000 X( 2, 5) 1.000000 2.000000 X( 5, 7) 1.000000 2.000000相应的的最短线路为：V1V2V5V7，最短距离为5。5最大流问题和模型5.1 最大流问题给定一个有向图D(V，A)，如果对于每一条弧a(vi，vj)A，均有一个非负实数c(a)或记为c(vi，vj)，cij与之对应，V中给定一个顶点x为源(发点)，一个顶点y为汇(收点)，其余顶点为中间顶点，则称这个有向图为容量网络，记为N(V，A，C，x，y)，称c(a)为弧a的容量。当每条边上的实际流量小于等于其容量时，流动才可以顺利进行，否则就会产生拥堵。对于给定的容量网络，如何求出从发点到收点的最大可行流量就是最大流问题。许多实际问题都可以归结为求最大流问题。例如城市的交通问题、自来水管网的设计问题、互联网的建设问题等等都会涉及最大流问题的计算。为了说明问题，请看下面的范例3。范例3：假设某山区有六个村庄。村庄与村庄之间虽有公路，但是通行的能力有很大差异，边上的数字小则表示通行能力差，反之则表示通行能力强（见图3）。试求出村庄1到村庄6之间的最大流。 5.2 最大流模型规定当两个节点之间没有线路时，两个节点之间的通行能力为0（容量为0）。最大流模型如下（加重黑线部分根据问题大小做相应调整）： 图3 六个村庄通行能力线路图MODEL1 SETS:2CITY/1.6/: ; ! 定义了图3的点集CITY;3LINK(CITY, CITY): C,X;! 定义了图3的边集LINK和属性C, X 。C表示容量,X表示实际流量;4ENDSETS5DATA:6C=!输入容量数据;7! 从V1V2V3V4V5V6;8!从V1;0400609!从V2;00441010!从V3;00022011!从V4;00000912!从V5;00060713!从V6;000000;14S=?;!S表示要选择的发点;15T=?;!T表示要选择的汇点;16ENDDATA17FOR(CITY(I):X(I,S)=0);!限制流入始点;18FOR(CITY(I):X(T,I)=0);!限制流出终点;19FOR(CITY(I)|I#ne#T#and#I#ne#S:!对于中间点满足：流进量=流出量; SUM (CITY(J):X(I,J)= SUM (CITY(K):X(K,I) ); 20FOR(LINK:XC);!线段流量限制;21max=W;!目标函数;22W=SUM (CITY (I):X(S,I);!W为发点发出去的流量;END运行模型可以得到： Variable Value Reduced Cost X( 1, 2) 4.000000 0.0000000 X( 1, 5) 6.000000 0.0000000 X( 2, 3) 3.000000 0.0000000 X( 2, 5) 1.000000 0.0000000 X( 3, 4) 2.000000 0.0000000 X( 3, 5) 1.000000 0.0000000 X( 4, 6) 8.000000 0.0000000 X( 5, 4) 6.000000 0.0000000 X( 5, 6) 2.000000 0.0000000从发点V1发出10个流量，汇点V6收到10个流量，最大流为10。6 最小费用流问题和模型6.1 最小费用流问题前面讨论的寻求网络最大流问题只考虑了流的数量，没有考虑流的费用。事实上很多情况下流量是确定的，需要求解费用最小的运输方案。这就是最小费用流问题。如果流量等于最大流量，就是最小费用最大流问题。最小费用流问题的一般提法：已知容量网络G=(V,E,C)，每条边（vi,vj）除了已给出容量cij外，还给出了单位流量的费用dij(大于等于零)，记G=(V,E,C,D)。求一个可行流f=fij，使得流量w(f)=v（v小于等于最大流），且总费用最小。为了说明问题，请看下面的范例4。范例4：假设从仓库V4到商店V5要运送8个流量的货物，边上左边数字表示线段最大通过能力，右边数字表示通过单位流量的费用（见图4）。 图4 运输线路图试求出费用最小的运输方案。 6.2 最小费用流模型规定当两个节点之间没有线路时，两个节点之间的通行能力为0（容量为0）。最小费用流模型如下（加重黑线部分根据问题大小做相应调整）：MODEL1 SETS:2CITY/1.5/: ; ! 定义了图4的点集CITY;3LINK(CITY, CITY): C,D, X;! 定义了图4的边集LINK。C表示容量,D表示费用,X表示实际流量;4ENDSETS5DATA:6C=!输入容量数据;7! 从V1V2V3V4V5;8!从V1;002079!从V2;50100010!从V3;0000411!从V4;10800012!从V5;00000;13D=!输入费用数据;14! 从V1V2V3V4V5;15!从V1;0060116!从V2;2030018!从V3;0000219!从V4;4100020!从V5;00000;21S=?;!T表示要选择的发点;22T=?;!T表示要选择的汇点;23W=?;!W表示设定流量;24ENDDATA25FOR(CITY(I):X(I,S)=0);!限制流入始点;26FOR(CITY(I):X(T,I)=0);!限制流出终点;27FOR(CITY(I)|I#ne#T#and#I#ne#S:!对于中间点满足：流进量=流出量;SUM (CITY(J):X(I,J)= SUM (CITY(K):X(K,I) ); 28FOR(LINK:XC);!线段流量限制;29W=SUM (CITY (I):X(S,I);!W为发点发出去的流量;30min=SUM(LINK:X*D);!目标函数;END运行模型可以得到： Variable Value Reduced Cost X( 1, 5) 7.000000 0.0000000 X( 2, 1) 5.000000 0.0000000 X( 2, 3) 1.000000 0.0000000 X( 3, 5) 1.000000 0.0000000 X( 4, 1) 2.000000 0.0000000 X( 4, 2) 6.000000 0.0000000从仓库V4运出8个流量，其中向V1运出2个流量，向V2运出6个流量，商店V5从V1收到7个流量，从V3收到1个流量，共收到8个流量，最小费用为15。7货郎担模型7.1 货郎担问题货郎担问题一般提法为：一个货郎从某村镇出发，经过若干个村镇一次，且仅一次，最后仍回到原出发的村镇，问应如何选择行走路线可使总行程最短？这是运筹学的一个著名问题，现实中有很多问题可以归结为这类问题。例如快递、检查等。设v1，v2，vn是已知的n个村镇，村镇vi到村镇vj的距离为dij，现求从vl出发，经各村镇一次且仅一次返回v1的最短路程行走线路。为了说明问题，请看下面的范例5。范例5 假设某个推销员从北京（V1）出发，跑遍6个城市一次且仅一次，城市之间的距离如表1所示。问按怎样的线路行走，才能使总的行程最短？表1 各城市之间的距离（dij）距离矩阵（公里）北京上海天津石家庄太原呼和浩特V1V2V3V4V5V6北京V1 01078119263 398 401上海V21078 096398910961381天津V3 119 963 0262 426 504石家庄V4 263 989262 0 171 394太原V5 3981096426171 0 341呼和浩特V6 4011381504394 341 07.2 货郎担模型 货郎担问题整数规划模型如下（加重黑线部分根据问题大小做相应调整）：MODEL1 SETS:2CITY/1.6/:U ; ! 定义了表1的点集CITY和属性U;3LINK(CITY, CITY): DISK, X;! 定义了表1的边集LINK和属性DIST, X;4ENDSETS5DATA:6DIST=!输入属性DIST的数值（距离）; ! 从 V1 V2 V3 V4 V5 V6;7!从V1; 01078119263398 4018!从V2; 1078 0963989109613819!从V3; 119 963 0262426 50410!从V4; 263 989262 0171 39411!从V5; 3981096426171 0 34112!从V6; 4011381504394341 0;13ENDDATA14FOR(CITY(K):!确保一个点过一次仅一次;SUM(CITY(I)|I#ne#k:X(I,K)=1;SUM(CITY(J)|J#ne#k:X(K,J)=1;);15MIN=SUM(LINK: DIST*X);!目标函数;16FOR(LINK:BIN(X); );!限制X仅取0或1;15N=SIZE(CITY);!N表示CITY中点的个数;17 FOR( LINK(I,J) | I #gt# 1#and#J #gt# 1#and#I #ne# J :!确定节点访问顺序;U(i)-U(j)+N*X(i,j)N-1 ); END运行模型可以得到： Variable Value Reduced Cost X( 1, 7) 1.000000 0.000000 X( 2, 3) 1.000000 963.0000 X( 3, 1) 1.000000 119.0000 X( 4, 2) 1.000000 989.0000 X( 5, 4) 1.000000 171.0000 X( 6, 5) 1.000000 341.0000 X( 7, 6) 1.000000 401.0000相应的最佳线路是：V1V6V5V4V2V3V1（北京呼和浩特太原石家庄上海天津北京），总线路的长度为2984公里。下面进行一次测试，假设必走V3V4（天津石家庄）线路，在模型中增加语句：“x(3,4)=1;”。相应的最佳线路为：V1V3V4V2V5V6V1（北京天津石家庄上海太原呼和浩特北京），总线路的长度为3208公里。8 结束语虽然上述5个问题都是古老的最优化问题，相应的解法也很多，但是本文提出的利用计算机，利用LINGO语言，通过建立LINGO模型求解问题是一种新的尝试。利用这种方法求解最优化问题需要注意以下几点：1、本文提出的最短路、最大流、最小费用流模型都是线性规划模型。而最小树和货郎担模型受制于模型使用的整数变量的数量。从这个角度来看，这些模型应该属于整数规划模型。LINGO是美国LINDO系统公司生产的最优化软件之一，其费用随着整数变量的增加而增加。如果限制整数变量在50个以内，则只能求解7个城市的货郎担问题；如果限制整数变量在1000个以内，则只能求解31个城市的货郎担问题。2、北京大学和清华大学出版的涉及上述5个问题的所有习题应用此模型都得到了正确答案。从教学的角