下载文档原格式
Lingo介绍Lingo是美国LINDO系统公司（Lindo Symtem Inc）开发的求解数学规划系列软件中的一个（其他软件为LINGDO,GINO,What’s Best 等），它的主要功能是求解大型线性、非线性和整数规划问题，目前的版本是lingo11.0。
lingo分为Demo、solve suite、hyper、industrial、extended等六类不同版本，只有Demo版本是免费的，其他版本需要向LINDO系统公司（在中国的代理商）购买，Lingo的不同版本对模型的变量总数、非线性变量个数、整型变量个数和约束条件的数量做出不同的限制（其中extended版本无限制）。
Lingo的主要功能特色为：（1）既能求解线性规划，也有较强的求解非线性规划的能力；（2）输入模型简练直观；（3）运行速度快、计算能力强；（4）内置建模语言，提供几十种内部函数，从而能以较少语句，较直观的方式描述较大规模的优化模型；（5）将集合的概念引入编程语言，很容易将实际问题转换为Lingo 语言；（6）能方便地与excel、数据库等其他软件交换数据。
学校图书馆40本《lingo和excel在数学建模中的应用》，袁新生、邵大宏、郁时炼主编，科学出版社Lingo 程序设计简要说明在数学建模中会遇到如规划类的题型，在这种模型中总存在着一个目标，并希望这个目标的取值尽可能的大或小，同时与这个目标有关的一系列变量之间存在一些约束。
在构造出目标函数和约束条件的表达式后，我们需要对求出这个最值和各变量的取值。
一般我们用LINGO 来对模型进行求解，本文将通过举一个简单的例子，围绕这个例子逐步学习LINGO 的使用。
LINGO 只是一个求解工具，我们主要的任务还是模型的建立！当你在windows 下开始运行LINGO 系统时，会得到类似下面的一个窗口：外层是主框架窗口，包含了所有菜单命令和工具条，其它所有的窗口将被包含在主窗口之下。
全国第四届研究生数学建模竞赛题 目 邮政运输网络中的邮路规划和邮车调度优化研究摘 要本文借助于图论典型算法（如Flody算法），以及运筹学图上作业法等典型手法，深入研究了一类曲面上的带附加条件的多路巡回问题。
分别回答了县区、市区邮政网络的邮路规划调度问题及其关于县区部分边界变动、和县区邮政中心变化引起的灵敏度分析。
并且针对每一问建立了相应的优化模型。
针对第一问、先回答了车辆个数的下确界，并用试探算法明确了三个子巡回可行，并针对三个子巡回设计了新颖的算法，先将问题松弛，将约束条件转化为准则库，找寻到经过县局的满足荷载限制的子巡回，然后定义每个子巡回的标示码、校验码、在程序中成功定义了映射，实现了三个子巡回的邮政网络划分，找到了问题的可行解域，然后以空载费用为目标函数，找到了空载费用为55.67的最优方案。
且该方案通过了检验。
针对第二问，针对市、县两级邮政网络图的特点，寻求局优解，借助于市区的最小生成树、以及市局、县局的最短路径，从中心向四周辐射，安排各子巡回，以区级车辆往返时间特点为约束，以子巡回的空余时间为罚函数，以环形回路为主兼顾辐射型回路，优先安排快车巡回，设计了相应的算法，并且给出了初始方案，且利用我们的方法调整方案，得到满意解，需要用13辆邮车完成全区的邮件任务，全区的总邮路路程为2453公里。
针对第三问，我们以减少邮路车辆为目标，研究了县区边界需要调整的点的特点，利用邻接区域的罚函数较大的回路破圈，重新构造子巡回。
既满足时间约束，又达到了降低费用和减少邮路车辆的目的。
通过我们的工作，可以减少两个邮车，总路程变比第二问减少了258公里针对第四问，我们定义了区域中心即为到达所有各点的距离之和为最小的点，但是邮政网络中的中心不仅取决于距离，同时由它的度数以及周围区域点的度数综合决定，我们利用Mthematica和Lingo中的tsp模板，借鉴第二问的表上作业法，和第三问灵敏度分析的经验，减少了两辆邮车，减少了284公里的邮路。
TSP 问题及LINGO 求解技巧巡回旅行商问题(Traveling Salesman Problem ，TSP)，也称为货郎担问题。
最早可以追溯到1759年Euler 提出的骑士旅行问题。
1948年，由美国兰德公司推动，TSP 成为近代组合优化领域的一个典型难题。
它已经被证明属于NP 难题。
用图论描述TSP ，给出一个图(,)G V E =，每边e E ∈上有非负权值()w e ,寻找G 的Hamilton 圈C ，使得C 的总权()()()W C w e e E C =∑∈最小. 几十年来，出现了很多近似优化算法。
如近邻法、贪心算法、最近插入法、最远插入法、模拟退火算法以及遗传算法。
这里我们介绍利用LINGO 软件进行求解的方法。
问题1设有一个售货员从10个城市中的某一个城市出发，去其它9个城市推销产品。
10个城市相互距离如下表。
要求每个城市到达一次仅一次后，回到原出发城市。
问他应如何选择旅行路线，使总路程最短。
我们采用线性规划的方法求解设城市之间距离用矩阵d 来表示，ij d 表示城市i 与城市j 之间的距离。
设0--1矩阵X 用来表示经过的各城市之间的路线。
设01,ij i j x i j i j ⎧=⎨⎩若城市不到城市若城市到城市且在前考虑每个城市后只有一个城市，则：11,nij j j ix =≠=∑1,,i n =… 考虑每个城市前只有一个城市，则：11,nij i i jx =≠=∑1,,j n =…； 但仅以上约束条件不能避免在一次遍历中产生多于一个互不连通回路。
为此我们引入额外变量i u (1,,i n =…），附加以下充分约束条件：1,i j ij u u nx n -+≤-1i j n <≠≤；该约束的解释：如i 与j 不会构成回路，若构成回路，有：1ij x =，1ji x =，则：1i j u u -≤-，1j i u u -≤-，从而有：02≤-，导致矛盾。
LINGO 使用教程LINGO 是用来求解线性和非线性优化问题的简易工具。
LINGO 内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO 高效的求解器可快速求解并分析结果。
一般来说LINGO 多用于解决大规模数学规划。
用时要注意以下几点：（1）每条语句后必须使用分号“；”结束。
问题模型必须由MODEL 命令开始，END结束。
（2）用MODEL 命令来作为输入问题模型的开始，格式为MODEL ：statement （语句）。
（3）目标函数必须由“min =”或“max =”开头。
§1 LINGO 快速入门当你在windows 下开始运行LINGO 系统时，会得到类似下面的一个窗口：外层是主框架窗口，包含了所有菜单命令和工具条，其它所有的窗口将被包含在主窗口之下。
在主窗口内的标题为LINGO Model – LINGO1的窗口是LINGO 的默认模型窗口，建立的模型都都要在该窗口内编码实现。
下面举两个例子。
例1.1 如何在LINGO 中求解如下的LP 问题：,6002100350..32min 212112121≥≤+≥≥++x x x x x x x t s x x在模型窗口中输入如下代码： min =2*x1+3*x2; x1+x2>=350; x1>=100;2*x1+x2<=600;然后点击工具条上的按钮 即可。
例1.2 使用LINGO 软件计算6个发点8个收点的最小费用运输问题。
产销单位运价如model :!6发点8收点运输问题; sets :warehouses/wh1..wh6/: capacity; vendors/v1..v8/: demand;links(warehouses,vendors): cost, volume; endsets !目标函数;min =@sum (links: cost*volume); !需求约束;@for (vendors(J):@sum (warehouses(I): volume(I,J))=demand(J)); !产量约束;@for (warehouses(I):@sum (vendors(J): volume(I,J))<=capacity(I));!这里是数据; data :capacity=60 55 51 43 41 52;demand=35 37 22 32 41 32 43 38; cost=6 2 6 7 4 2 9 5 4 9 5 3 8 5 8 2 5 2 1 9 7 4 3 3 7 6 7 3 9 2 7 1 2 3 9 5 7 2 6 5 5 5 2 2 8 1 4 3; enddata end然后点击工具条上的按钮 即可。
图论与网络流问题的LINGO 求解技巧我们介绍使用LINGO 求解图论与网络问题中的一些典型问题。
如最短路问题、最大流问题、关键路径问题、最优树问题，以及TSP 问题。
这里主要介绍使用LINGO 求解的方法，重在应用和解决问题。
1 最短路问题的Lingo 求解设图共有个节点，其赋权图的邻接矩阵为n n n w ×.ij w p =表示节点i 到j 的权值为.当为有向图时，p ji w w ij =；当为无向图时，和ij w ji w 分别由图得到，通常不一样。
当，表示节点i 与节点0ij w =j 不连通。
令0ii w =。
假设图的所有权值 0ij w ≥现求节点a 到节点b 的最短路，其线性规划模型为：模型一、决策变量：设1ij i j x i j ⎧=⎨⎩节点与节点连通节点与节点不连通目标函数为寻找一条节点到节点的通路，使其上权值和最小，故目标函数为：a b 11min .nnij ij i j Z w x ===∑∑1. 对节点恰有一条路出去，却不能有路回来，故有：a 11najj j ax=≠=∑ 且10nkak k a x=≠=∑2. 对节点恰有一条路到达，却不能有路出去，故有：b 11nkbk k bx=≠=∑ 且10nbjj j bx=≠=∑3. 对除起始点a 和目标点之外，其它点进入和出去的路是一样多（可都为0），则：b 11,nnkiijk j xx i a ===≠∑∑b4. 对不通的路不取，约束为：,1,2,ij ijx w i j ≤=L n总的线性规划模型为：11111111min .,10..10,1,2,,01n nij iji j nnki ijk j naj j j a n ka k k a n kb k k a nbj j j a ij ijijZ w x x x i a b x x s t x x x w i j x =====≠=≠=≠=≠=⎧=≠⎪⎪⎪=⎪⎪⎪⎪=⎪⎪⎪⎪=⎨⎪⎪⎪=⎪⎪⎪≤=⎪⎪=⎪⎪⎪⎩∑∑∑∑∑∑∑∑L 或n示例演示。
例1 现有11个点的无向图见图14.1，求点1到点11的最短路。
图14.1 无向图最短路示意图其Lingo 实现程序为：!最短路程序; model: sets:point/1..11/;road(point,point):W,X; endsets data:W=0,2,8,1,0,0,0,0,0,0,0, 2,0,6,0,1,0,0,0,0,0,0, 8,6,0,7,5,1,2,0,0,0,0,1,0,7,0,0,0,9,0,0,0,0, 0,1,5,0,0,3,0,2,9,0,0, 0,0,1,0,3,0,4,0,6,0,0, 0,0,2,9,0,4,0,0,3,1,0, 0,0,0,0,2,0,0,0,7,0,9, 0,0,0,0,9,6,3,7,0,1,2, 0,0,0,0,0,0,1,0,1,0,4, 0,0,0,0,0,0,0,9,2,4,0; enddatamin=@sum(road(i,j):w(i,j)*x(i,j)); !最短路;@for(point(i)|i#ne#1#and#i#ne#11:@sum(point(k):x(k,i))=@sum(point(j):x(i,j)));@sum(point(j)|j#ne#1:x(1,j))=1; !起始点要出去; @sum(point(k)|k#ne#1:x(k,1))=0; !不能回到起始点; @sum(point(k)|k#ne#11:x(k,11))=1; !要到达目标点; @sum(point(j)|j#ne#11:x(11,j))=0; !目标点不能出去;@for(road(i,j):x(i,j)<=W(i,j)); !不能到达的路不考虑; @for(road(i,j):@bin(x(i,j))); end结果为minZ=13x(1,2)=1 x(2,5)=1; x(5,6)=1 x(6,3)=1 x(3,7)=1 x(7,10)=1 x(10,9)=1 x(9,11)=1 故路径为1Æ2Æ5Æ6Æ3Æ7Æ10Æ9Æ11模型二:不必考虑起始点不回去，结束点不出去，统一考虑所有中间点不出现圈，添加约束为：.1i j ij u u n x n −+≤−总模型为：111111min.,1..1.1,1,2,,1,2,,01n nij iji jn nki ijk jnajjj ankbkk ai j ijij ijijZ w xx x i a bxs t xu u n x n i j nx w i j nx=====≠=≠=⎧=≠⎪⎪⎪=⎪⎪⎪⎪⎨=⎪⎪⎪−+≤−=⎪⎪≤=⎪=⎪⎩∑∑∑∑∑∑LL或,上面程序为：!最短路程序;model:sets:point/1..11/:u;road(point,point):W,X;endsetsdata:W=0,2,8,1,0,0,0,0,0,0,0,2,0,6,0,1,0,0,0,0,0,0,8,6,0,7,5,1,2,0,0,0,0,1,0,7,0,0,0,9,0,0,0,0,0,1,5,0,0,3,0,2,9,0,0,0,0,1,0,3,0,4,0,6,0,0,0,0,2,9,0,4,0,0,3,1,0,0,0,0,0,2,0,0,0,7,0,9,0,0,0,0,9,6,3,7,0,1,2,0,0,0,0,0,0,1,0,1,0,4,0,0,0,0,0,0,0,9,2,4,0;enddatamin=@sum(road(i,j):w(i,j)*x(i,j)); !最短路;n=@size(point);@for(point(i)|i#ne#1#and#i#ne#11:@sum(point(k):x(k,i))=@sum(point(j): x(i,j)));@sum(point(j)|j#ne#1:x(1,j))=1; !起始点要出去;@sum(point(k)|k#ne#11:x(k,11))=1; !要到达目标点;@for(road(i,j):u(i)-u(j)+n*x(i,j)<=n-1); !不出现圈;@for(road(i,j):x(i,j)<=W(i,j)); !不能到达的路不考虑;@for(road(i,j):@bin(x(i,j)));end2最大流问题的Lingo 求解设有向图共有个节点，其赋权图的容量矩阵为n n n C ×.表示节点i 到ij c j 的允许的最大容量。
现求根节点1到节点n 的最大流量。
其线性规划模型为：决策变量：设ij f 表示节点i 到节点j 的实际流量。
目标函数为：max Z flow =1. 从节点1流出的就是流量，故有：12nj j flow f ==∑2. 对终点流入的也是流量，故有：11n in i flow f −==∑3．中间所有点满足流入与流出相等，约束为：112,3,,1nnkiijk j ff i n ====∑∑L −4．每个节点上的流量不超过容量 ,,1,2,,ij ijf c i j ≤=L n总的线性规划模型为：121111max ..2,3,,1,,1,2,,njj n ini nn ki ij k j ijij Z flowflow f flow f s t f f i n f c i j n =−====⎧=⎪⎪⎪=⎪⎨⎪⎪==⎪⎪≤=⎩∑∑∑∑L L − 示例演示。
例2 有6个点的有向图见图14.2，求起始点1到终点6的最大流量。
图14.2 有向图初始网络其Lingo实现程序为：!最大流问题;model:sets:point/1..6/;link(point,point):C,f;endsetsdata:C=0,8,7,0,0,0,0,0,5,9,0,0,0,0,0,0,9,0,0,0,2,0,0,5,0,0,0,6,0,10,0,0,0,0,0,0;enddatamax=flow;n=@size(point);flow=@sum(point(j):f(1,j)); !流量为从起始点流出的量;gui=@sum(point(i):f(i,n)); !流入终点的量;gui=flow;!中间各点流入与流出的量相等;@for(point(i)|i#ne#1#and#i#ne#n:@sum(point(j):f(i,j))=@sum(point(k):f (k,i)));@for(link(i,j):f(i,j)<=c(i,j));end结果为maxZ=14F(1,2)=7 F(1,3)=7 F(2,3)=2 F(2,4)=5 F(3,5)=9F( 4,6）=5 F(5,6）=9结果见图14.3。
图14.3 计算结果图3 关键路线(CPM)问题的Lingo 求解计划评审方法(PERT)和关键路线法(CPM)是网络分析的重要部分，在中国又称为统筹方法(schedule methof)。
这里采用最短路的思想利用Lingo 求解关键路线。
以获得最少完成时间。
设有项作业等待完成。
作业号分别为1,。
每项作业需要完成的时间为。
第i 项作业的紧前作业有。
设虚拟的开始作业为，结束作业为。
号作业完成时间为0。
无紧前作业的作业号的紧前作业为，结束作业的紧前作业为其后无作业的作业号。
n 2,,n L (1,2,,i t i n =L )12,,,i k k k L 1n +2n +1n +1n +2n +该图共有个节点，其赋权图的邻接矩阵为2n +(2)(2)n n w +×+.ij i w t =表示作业i 完成的时间为。
当，表示作业i 与作业i t 0ij w =j 无依赖关系。
求完成作业的最少时间，就是求从起始点到结束点的最长路，其线性规划模型为： 1n +2n +决策变量：设10ij i j x i j ⎧=⎨⎩作业与作业紧连作业与作业不紧连目标函数为寻找一条从起始点到结束点1n +2n +的最长路，使其上权值和最大，故目标函数为：2211max .n n ij ij i j Z w x ++===∑∑1. 对起始点恰有一条路出去，故有：1n +21,111n n jj j n x++=≠+=∑2. 对终点恰有一条路到达，故有：2n +2,2121n k n k k n x ++=≠+=∑3. 对除起始点1n +和终点之外，其它点进入和出去的路是一样多（可都为0），则：2n +22111,2n n kiijk j xx i n n ++===≠+∑∑+4. 所有中间点不出现圈，添加约束为： .1i j ij u u n x n −+≤−总模型为：2211221121,112,212min .1,21..1.1,1,2,,,1,201n n ij iji j n n ki ijk j n n j j j n n k n kk n i j ij ij Z w x x x i n n x s t x u u n x n i j n n n x ++==++==++=≠+++=≠+=⎧=≠++⎪⎪⎪=⎪⎪⎪⎪=⎨⎪⎪−+≤−=++⎪⎪=⎪⎪⎪⎩∑∑∑∑∑∑L 或例3 1991年上海市大学生数学建模竞赛B 题第一问：现有14件工件等待在一台机床上加工，某些工件的加工顺序必须安排在另外一些工件完工以后才能开始，第j 号工件的加工时间j t 及先期必须完工的工件号i 由表1给出： 表14.4 工件加工时间与次序表 工件号1 2 3 4 5 6 7 8 9 1011 12 13 14 j t20 28 25 16 42 12 32 10 24 2040 24 36 16前期工件号3,4 5,7,85,9 -- 10,113,8,94 3,5,74 --4,76,7,14 5,12 1,2,6(1)给出一个加工顺序，则确定了每个工件的完工时间（包括等待与加工两个阶段）。
