《lingo软件求解选址、调拨、路线优化问题.ppt》由会员分享，可在线阅读，更多相关《lingo软件求解选址、调拨、路线优化问题.ppt（46页珍藏版）》请在三一办公上搜索。
1、西南林业大学 汽车与交通学院 马志磊2019,Lingo在建模中的运用,目录,概况（基本操作、基本函数）,01,实例（单设施选址、多设置选址、物资调拨规划、旅行商模型）,02,03,定义集合,某工厂有两条生产线，分别用来生产M和P两种产品，利润分别为200元/个和300元/个，生产线的最大生产能力分别为每日100和120，生产一个M产品需要1个劳动日，生产P产品需要2个劳动日，工厂每天可以提供160劳动日，如何计划生产，可以使利润最大。max=200*X1+300*X2;X1100;X2120;X1+2*X2160;,01 概况（基本操作、基本函数）,扩展的求解器(求解程序)状态框,使用的特殊
2、求解程序:B-and-B(分枝定界算法)Global(全局最优求解程序)Multistart(用多个初始点求解的程序),目前为止找到的可行解的最佳目标函数值,目标函数值的界,特殊求解程序当前运行步数：分枝数(对B-and-B程序)；子问题数(对Global程序)；初始点数(对Multistart程序),有效步数,最优整数解X=(35，65),最大利润=11077.5,目标函数用 MAX=或 MIN=来表示每条语句用；结束，！后可加注释，以；结束变量名用字母开头，由数字下划线组成，不区分大小写默认所有决策变量非负,算术运算符,加、减、乘、除、乘方等数学运算(即数与数之间的运算，运算结果也是数)。
3、LINGO中的算术运算符有以下5种：+（加法），（减法或负号），*（乘法），/（除法），(求幂)。,逻辑运算符,运算结果只有“真”(TRUE)和“假”(FALSE)两个值(称为“逻辑值”)，LINGO中用数字1代表TRUE，其他值(典型的值是0)都是FALSE。在LINGO中，逻辑运算(表达式)通常作为过滤条件使用,逻辑运算符有9种，可以分成两类：#AND#(与),#OR#(或),#NOT#(非)：逻辑值之间的运算，它们操作的对象本身已经是逻辑值或逻辑表达式，计算结果也是逻辑值。#EQ#(等于),#NE#(不等于),#GT#(大于),#GE#(大于等于),#LT#(小于),#LE#(小于等于)
4、：是“数与数之间”的比较,也就是它们操作的对象本身必须是两个数,计算得到的结果是逻辑值。,关系运算符,表示是“数与数之间”的大小关系，在LINGO中用来表示优化模型的约束条件。LINGO中关系运算符有3种：(即=，大于等于)(在优化模型中约束一般没有严格小于、严格大于关系),运算符的优先级,基本的数学函数,LINGO中内部函数以”打头。ABS(X)：绝对值函数，返回X的绝对值。SIN(X)：正弦函数，返回X的正弦值（X的单位是弧度）。COS(X)：余弦函数，返回X的余弦值TAN(X)：正切函数，返回X的正切值（X的单位是弧度）。POW(X,Y)：指数函数，返回XY的值。SMAX(list)：最
5、大值函数，返回一列数(list)的最大值。SMIN(list)：最小值函数，返回一列数(list)的最小值。SQR(X)：平方函数，返回X的平方（即X*X）的值。SQRT(X)：开平方函数，返回X的正的平方根的值。,集合循环函数,集合上的元素(下标)进行循环操作的函数,一般用法如下:function(setname(set_index_list)|condition:expression_list);其中：function 集合函数名,FOR、MAX、MIN、PROD、SUM之一；Setname 集合名；set_index_list 集合索引列表(不需使用索引时可以省略)；Condition
6、用逻辑表达式描述的过滤条件(无条件时可以省略)；expression_list 一个表达式(对FOR函数，可以是一组表达式。,FOR(集合元素的循环函数)：对集合setname的每个元素独立地生成表达式，表达式由expression_list描述（通常是优化问题的约束）。MAX（集合属性的最大值函数）：返回集合setname上的表达式的最大值。MIN（集合属性的最小值函数）：返回集合setname上的表达式的最小值。PROD（集合属性的乘积函数）：返回集合setname上的表达式的积。SUM(集合属性的求和函数):返回集合setname上的表达式的和。,集合操作函数,INDEX(set_nam
7、e,primitive_set_element)给出元素primitive_set_element在集合set_name中的索引值。省略set_name，LINGO按模型中定义的集合顺序找到第一个含有该元素的集合，并返回索引值。如果没有找到该元素，则出错。SETS:GIRLS/DEBBIE,SUE,ALICE/;BOYS/BOB,JOE,SUE,FRED/;ENDSETSGIRLS在BOYS前定义,调用INDEX(SUE)将返2，相当于INDEX(GIRLS,SUE)。要找男孩中名为SUE的小孩的索引，应该使用INDEX(BOYS,SUE)，返3。SIZE(set_name)返回数据集set_
8、name中包含元素的个数。,变量定界函数,BND(L,X,U)：限制L=X=U。注意LINGO中没有与LINDO命令SLB、SUB类似的函数SLB和SUBBIN(X)：限制X为0或1。注意LINDO中的命令是INT，但LINGO中这个函数的名字却不是INT(X)FREE(X)：取消对X的符号限制（即可取负数、0或正数）GIN(X)：限制X为整数,02,重心法,02 实例（单设施选址、多设置选址、物资调拨规划、旅行商模型）,min=A*0.4*sqrt(sqr(x-3)+sqr(y-8)+B*0.4*sqrt(sqr(x-8)+sqr(y-2)+C*0.6*sqrt(sqr(x-2)+sqr(y
9、-5)+D*0.6*sqrt(sqr(x-6)+sqr(y-4)+E*0.6*sqrt(sqr(x-8)+sqr(y-8);A=2000;B=3000;C=2500;D=1000;E=1500;,02,混合整数线性规划法,min=g1*c1*(110000*24+110000*16+110000*0+390000)+g1*c2*(110000*24+110000*8+110000*5+300000)+g2*c1*(110000*16+110000*16+110000*4+390000)+g2*c2*(110000*16+110000*8+110000*2+300000)+c1*800000+c
10、2*4000000;bin(g1);bin(g2);bin(c1);bin(c2);g1+g2=1;c1+c2=1;,02,物资调拨规划,min=3*A1+2*A2+3*A3+5*B1+4*B2+1*B3+4*C1+2*C2+2*C3;A1+A2+A3=1500;B1+B2+B3=3000;C1+C2+C3=2000;A1+B1+C1=2000;A2+B2+C2=2000;A3+B3+C3=2500;,02,原点O（0,0）1栋（13.2，4.5）2栋（14.2，5.6）3栋（12，6.5）5栋（13.5，7）7栋（1.2，11）8栋（0，11.7）9栋（-2.2，9）10栋（-1.8，10.
11、5）11栋（-1.8，6.6）12栋（-3.7，6）,旅行商问题,MIN=X11*0+X12*139+X13*394+X14*304+X15*533+X16*700+X21*139+X22*0+X23*348+X24*216+X25*541+X26*680+X31*394+X32*348+X33*0+X34*155+X35*243+X36*335+X41*304+X42*216+X43*115+X44*0+X45*390+X46*488+X51*533+X52*541+X53*243+X54*390+X55*0+X56*199+X61*700+X62*680+X63*335+X64*488+X
12、65*199+X66*0;,X11+X12+X13+X14+X15+X16=1;X21+X22+X23+X24+X25+X26=1;X31+X32+X33+X34+X35+X36=1;X41+X42+X43+X44+X45+X46=1;X51+X52+X53+X54+X55+X56=1;X61+X62+X63+X64+X65+X66=1;,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
13、;X16+X26+X36+X46+X56+X66=1;,bin(X11);bin(X12);bin(X13);bin(X14);bin(X15);bin(X16);,bin(X21);bin(X22);bin(X23);bin(X24);bin(X25);bin(X26);,bin(X31);bin(X32);bin(X33);bin(X34);bin(X35);bin(X36);,bin(X41);bin(X42);bin(X43);bin(X44);bin(X45);bin(X46);,bin(X51);bin(X52);bin(X53);bin(X54);bin(X55);bin(X56
14、);,bin(X61);bin(X62);bin(X63);bin(X64);bin(X65);bin(X66);,改1,MIN=X12*139+X13*394+X14*304+X15*533+X16*700+X21*139+X23*348+X24*216+X25*541+X26*680+X31*394+X32*348+X34*155+X35*243+X36*335+X41*304+X42*216+X43*115+X45*390+X46*488+X51*533+X52*541+X53*243+X54*390+X56*199+X61*700+X62*680+X63*335+X64*488+X65
15、*199;X12+X13+X14+X15+X16=1;X21+X23+X24+X25+X26=1;X31+X32+X34+X35+X36=1;X41+X42+X43+X45+X46=1;X51+X52+X53+X54+X56=1;X61+X62+X63+X64+X65=1;X21+X31+X41+X51+X61=1;X12+X32+X42+X52+X62=1;X13+X23+X43+X53+X63=1;X14+X24+X34+X54+X64=1;X15+X25+X35+X45+X65=1;X16+X26+X36+X46+X56=1;,bin(X12);bin(X13);bin(X14);bin
16、(X15);bin(X16);bin(X21);bin(X23);bin(X24);bin(X25);bin(X26);bin(X31);bin(X32);bin(X34);bin(X35);bin(X36);,bin(X41);bin(X42);bin(X43);bin(X45);bin(X46);bin(X51);bin(X52);bin(X53);bin(X54);bin(X56);bin(X61);bin(X62);bin(X63);bin(X64);bin(X65);,改2,真的最优吗？,X12+X21=1;X34+X43=1;X56+X65=1;,X12+X211.5;X34+X4
17、31.5;X56+X651.5;改为这样可以限制（1,2）、（3,4）、（5,6）不重复，但只能限制没有2个节点的子回路，不能避免可能产生的3个、4个节点的子回路。,需要限制没有子回路,03,定义集合的方法,某公司有6个仓库，库存货物总数分别为：60、55、51、43、41、52。现有8个客户需要一批货，数量分别为：35、37、22、32、41、32、43、38。各仓库到客户的运价如下表：,03,model:sets:store/W1.W6/:kucun;customer/v1.v8/:xuqiu;links(store,customer):C,X;endsetsdata:kucun=60,5
18、5,51,43,41,52;xuqiu=35,37,22,32,41,32,43,38;c=6,2,6,7,4,2,5,9 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;enddatamin=sum(links(i,j):C(i,j)*X(i,j);for(store(i):sum(customer(j):X(i,j)=xuqiu(j);end,03,集合定义部分：定义集合时，要明确3个内容：1、集合的名称；2、集合内的成员（组成集合的个体，也称为元素）；3、集合的属性（与该集合有
19、关的参数）sets:store/W1.W6/:kucun;customer/v1.v8/:xuqiu;links(store,customer):C,X;EndsetsStore是集合名称，W1.W2是集合内的成员，kucun是集合在存储能力上的属性，可看做是一个一维数组，有6个分量。,03,sets:store/W1.W6/:kucun;customer/v1.v8/:xuqiu;links(store,customer):C,X;Endsetscustomer是集合名称，V1.V8是集合内的成员，xuqiu是集合在需求量上的属性，可看做是一个一维数组，有8个分量。Links是以store与
20、customer为基础，衍生出来的集合，C、X分别是集合links在运输费用、运输量上的属性。可看做是一个6*8的矩阵，具有48个元素，C、X都相当于二维数组。集合定义部分以语句SETS：开始，以语句endsets结束。,03,数据初始化（数据段）以上定义中，X是决策变量（6*8），不需要数据初始化，其他定义的变量是已知数，需要赋初值。data:kucun=60,55,51,43,41,52;xuqiu=35,37,22,32,41,32,43,38;c=6,2,6,7,4,2,5,9 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,
21、5,7,2,6,5 5,5,2,2,8,1,4,3;enddata数据初始化以data：开始，以enddata结束。,目标函数与约束条件min=sum(links(i,j):C(i,j)*X(i,j);函数名（集合名|条件：表达式）sum函数中有2个参数：1、集合名称；2、表达式，表示求和运算对该表达式进行。此处sum的第一个参数是links(i,j)，表示求和运算对links进行，该集合有48个元素，运算过程是：先对48个成员分别求表达式C(i,j)*X(i,j)的值，然后求和。,for(store(i):sum(customer(j):X(i,j)=kucun(i);函数名（集合名|条件：
22、表达式）for的作用是对某个集合的所有成员分别生产约束表达式，有2个表达式：1、集合名，表示生成对该集合所有成员对应的约束表达式；2、约束表达式的具体内容，此处嵌套调用了sum函数，表示约束表达式的左边求和，是分别对集合customer的8个成员的属性X(i,j)上第二维j求和。表达式的右边是store的属性kucun，其有6个分量，与六个表达式一一对应。产生6条约束条件，各仓库的运出量小于库存量。,for(customer(j):sum(store(i):X(i,j)=xuqiu(j);函数名（集合名|条件：表达式）for的作用是对某个集合的所有成员分别生产约束表达式，有2个表达式：1、集合
23、名，表示生成对该集合所有成员对应的约束表达式；2、约束表达式的具体内容，此处嵌套调用了sum函数，表示约束表达式的左边求和，是分别对集合store的6个成员的属性X(i,j)上第一维i求和。表达式的右边是customer的属性xuqiu，其有8个分量，与八个表达式一一对应。产生8条约束条件，各仓库对某客户的运入量大于需求量。,03,model:sets:store/W1.W6/:kucun;customer/v1.v8/:xuqiu;links(store,customer):C,X;endsetsdata:kucun=60,55,51,43,41,52;xuqiu=35,37,22,32,4
24、1,32,43,38;c=6,2,6,7,4,2,5,9 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;enddatamin=sum(links(i,j):C(i,j)*X(i,j);for(store(i):sum(customer(j):X(i,j)=xuqiu(j);end,03,某公司有6个建筑工地要开工，工地位置（x，y）/km和混泥土日用量d/t已知，目前公司有两个临时混泥土搅拌楼，分别位于A（5,1）与B（2,7），日供应量各20t，解决以下问题：1、假设从料场到工地
25、之间直线连接，制定每日运输计划，即从A、B两个料场分别向各工地送多少水泥，使总吨千米数最小。2、为了进一步减少吨千米数，打算舍弃目前的两个临时料场，改建两个新料场，日供应量仍各为20t，求新料场坐标。,03,model:sets:gd/1.6/:x,y,d;lch/A,B/:px,py,e;links(gd,lch):c;endsetsdata:x=1.25,8.75,0.5,5.75,3,7.25;y=1.25,0.75,4.75,5,6.5,7.75;d=3,5,4,7,6,11;e=20,20;px=5,2;py=1,7;enddatamin=sum(links(i,j):c(i,j)*
26、(px(j)-x(i)2+(py(j)-y(i)2)(1/2);for(gd(i):sum(lch(j):c(i,j)=d(i);for(lch(i):sum(gd(j):c(j,i)=e(i);end,03,重选料场,PX(A)3.254883 PX(B)7.250000PY(A)5.652332 PY(B)7.750000,model:sets:gd/1.6/:x,y,d;lch/A,B/:px,py,e;links(gd,lch):c;endsetsdata:x=1.25,8.75,0.5,5.75,3,7.25;y=1.25,0.75,4.75,5,6.5,7.75;d=3,5,4,7
27、,6,11;e=20,20;enddatamin=sum(links(i,j):c(i,j)*(px(j)-x(i)2+(py(j)-y(i)2)(1/2);for(gd(i):sum(lch(j):c(i,j)=d(i);for(lch(i):sum(gd(j):c(j,i)=e(i);for(lch(i):free(px(i);for(lch(i):free(py(i);end,03,重选料场（赋初值）,PX(A)3.254883 PX(B)7.250000PY(A)5.652332 PY(B)7.750000,model:sets:gd/1.6/:x,y,d;lch/A,B/:px,py
28、,e;links(gd,lch):c;endsetsdata:x=1.25,8.75,0.5,5.75,3,7.25;y=1.25,0.75,4.75,5,6.5,7.75;d=3,5,4,7,6,11;e=20,20;enddatainit:px=3,7;py=5,7;endinitmin=sum(links(i,j):c(i,j)*(px(j)-x(i)2+(py(j)-y(i)2)(1/2);for(gd(i):sum(lch(j):c(i,j)=d(i);for(lch(i):sum(gd(j):c(j,i)=e(i);for(lch(i):free(px(i);for(lch(i):
29、free(py(i);end,03,重心法（使用集合）,sets:guke/1.5/:x,y,v,r;endsetsdata:x=3,8,2,6,8;y=8,2,5,4,8;v=2000,3000,2500,1000,1500;r=0.4,0.4,0.6,0.6,0.6;enddatamin=sum(guke(i):r(i)*v(i)*(px-x(i)2+(py-y(i)2)(1/2);,03,旅行商问题,model:sets:jiedian/1.6/:u;links(jiedian,jiedian):distance,X;endsetsdata:distance=0,139,394,304,
30、533,700 139,0,348,216,541,680 394,348,0,155,243,335 304,216,155,0,390,488 533,541,243,390,0,199 700,680,335,488,199,0;enddatamin=sum(links(i,j)|i#NE#j:distance(i,j)*X(i,j);for(jiedian(i):sum(jiedian(j)|j#NE#i:X(i,j)=1);for(jiedian(j):sum(jiedian(i)|i#NE#j:X(i,j)=1);for(links(i,j):(X(i,j)+X(j,i)1.5);
31、for(links(i,j):bin(X(i,j);end,目标函数（除去i=j的点）。约束条件（除去i=j的点），每个节点仅有一个输出，仅有一个输入。,min=sum(links(i,j)|i#NE#j:distance(i,j)*X(i,j);for(jiedian(i):sum(jiedian(j)|j#NE#i:X(i,j)=1);for(jiedian(j):sum(jiedian(i)|i#NE#j:X(i,j)=1);,for(links(i,j):(X(i,j)+X(j,i)1.5);for(links(i,j):bin(X(i,j);,约束条件，不产生2点间的子回路。设置0-
32、1变量。,改,model:sets:jiedian/1.6/:u;links(jiedian,jiedian):distance,X;endsetsdata:distance=0,139,394,304,533,700 139,0,348,216,541,680 394,348,0,155,243,335 304,216,155,0,390,488 533,541,243,390,0,199 700,680,335,488,199,0;enddatamin=sum(links(i,j)|i#NE#j:distance(i,j)*X(i,j);for(jiedian(i):sum(jiedian
33、(j)|j#NE#i:X(i,j)=1);for(jiedian(j):sum(jiedian(i)|i#NE#j:X(i,j)=1);!for(links(i,j):(X(i,j)+X(j,i)1.5);for(links(i,j):bin(X(i,j);n=size(jiedian);for(links(i,j)|i#ne#j#and#j#gt#1:u(i)-u(j)+n*X(i,j)=(n-1);end,将（不产生2点间的子回路的约束条件）改为：不产生任何子回路，使用变量u：设置ij，因为i=j时0n-1，必然满足（也可选择不写i#ne#j，对结果没有影响）。设置j#gt#1（严格大于）
34、，若产生了子回路，必然有一个子回路不包含节点1，则该子回路中各节点计算的u(i)-u(j)+n*X(i,j)=(n-1)累加，会产生n=(n-1)的矛盾。仅当产生无子回路的路线时，各节点u(i)-u(j)+n*X(i,j)=(n-1)累加：必然为u(1)-u(x)+n=(n-1),可以决策出满足该条件的u(1)与u(x)的实际值（x为1前的节点，下一步将要去1）。可将j#gt#1 改为 j#ne#1 或者 j#gt#n，含义为若产生了子回路，必然有一个子回路不包含节点1或者节点n，会产生n=(n-1)的矛盾。,n=size(jiedian);for(links(i,j)|i#ne#j#and#j#gt#1:u(i)-u(j)+n*X(i,j)=(n-1);,谢谢！,
