实验2Lingo求解运输问题和整数规划.ppt

《实验2Lingo求解运输问题和整数规划.ppt》由会员分享，可在线阅读，更多相关《实验2Lingo求解运输问题和整数规划.ppt（55页珍藏版）》请在三一办公上搜索。

1、数学规划,实验2 Lingo求解运输问题和整数规划,LINGO软件简介,目标与约束段 集合段（SETS ENDSETS）数据段（DATA ENDDATA）初始段（INIT ENDINIT）,LINGO模型的构成：4个段,LINGO模型的优点,包含了LINDO的全部功能提供了灵活的编程语言（矩阵生成器）,简单Lingo程序,Model:min=7*x1+3*x2;x1+x2=345.5;x1=98;2*x1+x2=600;end,lingo程序:,优化模型,实际问题中的优化模型,x决策变量,f(x)目标函数,gi(x)0约束条件,数学规划,线性规划(LP)二次规划(QP)非线性规划(NLP),纯

2、整数规划(PIP)混合整数规划(MIP),整数规划(IP),0-1整数规划一般整数规划,连续规划,LINDO 公司软件产品简要介绍,美国芝加哥(Chicago)大学的Linus Schrage教授于1980年前后开发,后来成立 LINDO系统公司（LINDO Systems Inc.），网址：,LINDO:Linear INteractive and Discrete Optimizer(V6.1)LINGO:Linear INteractive General Optimizer(V8.0)LINDO API:LINDO Application Programming Interface(V

3、2.0)Whats Best!:(SpreadSheet e.g.EXCEL)(V7.0),演示(试用)版、学生版、高级版、超级版、工业版、扩展版（求解问题规模和选件不同）,LINDO和LINGO软件能求解的优化模型,LINGO,LINDO,优化模型,线性规划(LP),非线性规划(NLP),二次规划(QP),连续优化,整数规划(IP),Lingo,LP QP NLP IP 全局优化(选)ILP IQP INLP,LINDO/LINGO软件的求解过程,LINDO/LINGO预处理程序,线性优化求解程序,非线性优化求解程序,分枝定界管理程序,1.确定常数2.识别类型,1.单纯形算法2.内点算法(选

4、),1、顺序线性规划法(SLP)2、广义既约梯度法(GRG)(选)3、多点搜索(Multistart)(选),二、实验例题例2.1 使用LINGO软件计算6个发点8个收点的最小费用运输问题。产销单位运价如下表。,解:设第I个产地运到第j个销地的单位运价为cij,第I个产地运到第j个销地的运量为 xij,第I个产地的产量为ai(I=1,2,6),第j个销地的销量为 bj(j=1,2,8),运费为z,则此问题的数学模型为如下的数学规划问题:,使用LINGO软件，编制程序如下：,使用LINGO软件，编制程序如下：model:!6发点8收点运输问题;sets:warehouses/wh1.wh6/:c

5、apacity;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、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;enddataend,产销不平衡问题,model:!6发点8收点运输问题;sets:chandi/A1.A6/:a;xiaodi/B1.B8/:d;links(chandi,xiaodi):c,x;endsets!目标函数;min=sum(links(i,j):c(i,j)*x(i,j);!需求约束;for(xiaodi(J):sum(chandi(I):x(I,J)=d(J);!产量约束;for(cha

7、ndi(I):sum(xiaodi(J):x(I,J)=a(I);!这里是数据;data:a=60 55 51 43 41 52;d=35 37 22 32 41 32 43 38;c=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;enddataend,LINGO模型的构成：4个段,集合段（SETS ENDSETS）,数据段（DATA ENDDATA）,目标与约束段,初始段（INIT ENDINIT）(此题无初始数据),例2.2 选址问题,某公司有6

8、个建筑工地，位置坐标为(ai,bi)(单位：公里),水泥日用量di(单位：吨）,假设：料场和工地之间有直线道路,用例中数据计算，最优解为,总吨公里数为136.2,线性规划模型,决策变量：ci j(料场j到工地i的运量）12维,Location(Linear),MODEL:Title Location Problem;sets:demand/1.6/:a,b,d;supply/1.2/:x,y,e;link(demand,supply):c;endsetsdata:!locations for the demand(需求点的位置);a=1.25,8.75,0.5,5.75,3,7.25;b=1.

9、25,0.75,4.75,5,6.5,7.75;!quantities of the demand and supply（供需量）;d=3,5,4,7,6,11;e=20,20;x,y=5,1,2,7;enddatainit:!initial locations for the supply（初始点）;!x,y=5,1,2,7;endinit!Objective function（目标）;OBJ min=sum(link(i,j):c(i,j)*(x(j)-a(i)2+(y(j)-b(i)2)(1/2);!demand constraints（需求约束）;for(demand(i):DEMAN

10、D_CON sum(supply(j):c(i,j)=d(i););!supply constraints（供应约束）;for(supply(i):SUPPLY_CON sum(demand(j):c(j,i)=e(i););for(supply:free(X);free(Y););!for(supply:bnd(0.5,X,8.75);bnd(0.75,Y,7.75););END,Location(Linear),选址问题：NLP,2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij，在其它条件不变下使总吨公里数最小。,决策变量：ci j，(xj,yj)16维,非线性规划模型,L

11、ocation(Non Linear),LINGO模型的构成：4个段,集合段（SETS ENDSETS）,数据段（DATA ENDDATA）,初始段（INIT ENDINIT）,目标与约束段,局部最优：89.8835(吨公里),LP：移到数据段,边界,集合的类型,集合 派生集合 基本集合 稀疏集合 稠密集合 元素列表法 元素过滤法 直接列举法 隐式列举法,setname/member_list/:attribute_list;,setname(parent_set_list)/member_list/:attribute_list;,SETS:CITIES/A1,A2,A3,B1,B2/;RO

12、ADS(CITIES,CITIES)/A1,B1 A1,B2 A2,B1 A3,B2/:D;ENDSETS,SETS:STUDENTS/S1.S8/;PAIRS(STUDENTS,STUDENTS)|ENDSETS,集合元素的隐式列举,运算符的优先级,三类运算符：算术运算符 逻辑运算符 关系运算符,集合循环函数,四个集合循环函数：FOR、SUM、MAX、MINfunction(setname(set_index_list)|condition:expression_list);,objective MAX=SUM(PAIRS(I,J):BENEFIT(I,J)*MATCH(I,J);FOR(S

13、TUDENTS(I):constraints SUM(PAIRS(J,K)|J#EQ#I#OR#K#EQ#I:MATCH(J,K)=1);FOR(PAIRS(I,J):BIN(MATCH(I,J);MAXB=MAX(PAIRS(I,J):BENEFIT(I,J);MINB=MIN(PAIRS(I,J):BENEFIT(I,J);,Example:,状态窗口,Solver Type:B-and-BGlobal Multistart,Model Class:LP，QP，ILP，IQP，PILP,PIQP，NLP，INLP，PINLP,State:Global OptimumLocal Optimu

14、mFeasibleInfeasibleUnboundedInterruptedUndetermined,7个选项卡(可设置80-90个控制参数),程序与数据分离,文本文件,使用外部数据文件,Cut(or Copy)Paste 方法FILE 输入数据、TEXT输出数据（文本文件）OLE函数与电子表格软件（如EXCEL）连接ODBC函数与数据库连接LINGO命令脚本文件,LG4（LONGO模型文件）LNG（LONGO模型文件）LTF（LONGO脚本文件）LDT（LONGO数据文件）LRP（LONGO报告文件）,常用文件后缀,2023/10/12,26,例题2.3 合理下料问题 现有一批长度一定的钢

15、管，由于生产的需要，要求截出若干不同规格的钢管.试问：要如何截取原材料，既能满足生产的需要，又使得使用的原材料钢管数量最少？具体数据：原材料钢管长7.4m。要截成2.9m,2.1m,1.5m各为1000根，2000根，1000根.,解 把所有可能的下料方式、按照各种下料方式从长7.4m的原料上得到的不同规格钢管的根数、残料长度，以及需要量列于表2.8中.例如，按照下料方式，可以得到2.9m钢管2根,1.5m钢管1根.问题转化为确定每种下料方式各用多少根7.4m的原料，可使被使用的原料根数最少.,2023/10/12,27,设 分别为按照 方式下料的原料根数，则得到问题的数学模型为,具体数据：原

16、材料钢管长7.4m。要截成2.9m,2.1m,1.5m各为1000根，2000根，1000根.,2023/10/12,28,其解为 即最佳下料方案为：方式：200根；方式：800根；方式：200根；其他方式为0根.,model:min=x1+x2+x3+x4+x5+x6+x7+x8;2*x1+x2+x3+x4=1000;2*x3+x4+2*x5+x6+3*x7=2000;x1+3*x2+x4+2*x5+3*x6+4*x8=1000;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);gin(x8);end,Global optimal

17、 solution found.Objective value:1200.000 Extended solver steps:0 Total solver iterations:5 Variable Value Reduced Cost X1 0.000000 1.000000 X2 200.0000 1.000000 X3 800.0000 1.000000 X4 0.000000 1.000000 X5 200.0000 1.000000 X6 0.000000 1.000000 X7 0.000000 1.000000 X8 0.000000 1.000000,最优解为X1=0;x2=2

18、00;x3=800;x4=0;x5=200;x6=x7=x8=0最优值f=1200（根）,其中 gin(x1)-表变量x1为整数,2023/10/12,30,例2.4 某医院护士24小时值班，每次值班8小时.不同时段需要的护士人数不等.据统计，各时段所需护士的最少人数如表2.9所示.如何安排才能做到安排最少的护士就能满足工作的需要？,2023/10/12,31,解 设 为时段 开始上班的人数，.目标是要求护士的总数最少.因为每个护士都工作8小时，即连续工作2个时段后休息，所以问题的线性规划模型为：,2023/10/12,32,计算最优解为：故该医院需雇用150名护士，最佳安排见表2.10所示.

19、,model:min=x1+x2+x3+x4+x5+x6;x1+x270;x2+x360;x3+x450;x4+x520;x5+x630;x1+x660;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);end,Global optimal solution found.Objective value:150.0000 Extended solver steps:0 Total solver iterations:6 Variable Value Reduced Cost X1 60.00000 1.000000 X2 10.00000 1.000

20、000 X3 50.00000 1.000000 X4 0.000000 1.000000 X5 30.00000 1.000000 X6 0.000000 1.000000,与书中给出的最优解不同，但最优值相同，故本题有对个最优解。,例4（布线问题）,解决某市消防站的布线 问题。该城市共有6个区，每个区都可以建立消防站，市政府希望设置的消防站最少，但必须满足在城市任何地方发生火警时，消防车要在15分钟之内赶到现场，根据实地考察，各区之间消防车行驶的时间见下表,请帮助该市制定一个最节省的计划。,各区之间消防车行驶的时间表,解：每个地区是否设消防站可用一个0-1变量来表示。令,i=1,2,6,本

21、题要求消防站的个数最少，故目标函数为：,约束条件为：,各区之间消防车行驶的时间表,约束条件为：,OBJECTIVE FUNCTION VALUE 1)2.000000 VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X2 1.000000 1.000000 X3 0.000000 1.000000 X4 1.000000 1.000000 X5 0.000000 1.000000 X6 0.000000 1.000000,min=x1+x2+x3+x4+x5+x6;x1+x21;x1+x2+x61;x3+x41;x3+x4+x51;x4+x5+

22、x61;x2+x5+x61;bin(x1);bin(x2);bin(x3);bin(x4);bin(x5);bin(x6);end,计算程序为,求解报告为,最优方案为x2=x4=1,即在第2区和第4区设置消防站即可。,例2.5（最优装载问题）,（美国 1988 年大学生建摸竞赛B题),要把七种规格的包装箱装到两辆平板车上去，箱子的宽、高、相同，而厚度和重量不同。下表给出了他们的厚度和重量及数量。,每辆平板车有10.2米的地方用于装箱，载重40吨。由于货物的限制，对于第5、6、7三种包装箱的装载有如下约束：它们所占的空间（厚度）不得超过302.7厘米，试把这些包装箱装到平板车上去，使浪费的空间最

23、小。,解：容易计算出所有的包装箱的厚度为27.495米，而两俩平板车共有20.4米长的地方，所以不可能都装上。记表中所给出的第i种箱子的厚度、重量和数量分别为ti、wi 和 ni（i=1,2,.,7),又记第i种箱子装到第1、2辆平板车上的数量分别为 xi1,xi2（i=1,2,.,7),问题要求浪费的空间最小，即装载所占的空间最大，故目标函数为：,约束条件为：,厚度约束：,重量约束：,每辆平板车有10.2米的地方用于装箱，载重40吨,记第i种箱子装到第1、2辆平板车上的数量分别为（i=1,2,.,7),数量约束：,特殊约束：,或,第5、6、7三种包装箱的装载有如下约束：它们所占的空间（厚度）

24、不得超过302.7厘米，,(每辆平板车不超过302.7cm),故得到两个整数规划模型为：,(IP1),(IP2),现解第一个问题：,(IP1),Liti3.ltx,Liti3.txt,利用lindo 求解得到最优解为：,MAX 48.7x11+48.7x12+52.0 x21+52.0 x22+61.3x31+61.3x32+72.0 x41+72.0 x42+48.7x51+48.7x52+52.0 x61+52.0 x62+64x71+64x72st 48.7x11+52x21+61.3x31+72x41+48.7x51+52x61+64x711020 48.7x12+52x22+61.3

25、x32+72x42+48.7x52+52x62+64x721024 2x11+3x21+x31+0.5x41+4x51+2x61+x7140 2x12+3x22+x32+0.5x42+4x52+2x62+x7240 x11+x128 x21+x227 x31+x329x11+x128 x21+x227 x31+x329 x41+x426 x51+x526 x61+x624 x71+x728 48.7x51+48.7x52+52.0 x61+52.0 x62+64.0 x71+64.0 x72302.7 END GIN 14,objective function value 1)2039.400

26、variable value reduced cost x11 5.000000-48.700001 x12 3.000000-48.700001 x21 1.000000-52.000000 x22 6.000000-52.000000 x31 9.000000-61.299999 x32 0.000000-61.299999,X41 1.000000-72.000000 X42 5.000000-72.000000 X51 2.000000-48.700001 X52 1.000000-48.700001 X61 0.000000-52.000000 X62 3.000000-52.000

27、000 X71 0.000000-64.000000 X72 0.000000-64.000000,MAX=48.7*x11+48.7*x12+52.0*x21+52.0*x22+61.3*x31+61.3*x32+72.0*x41+72.0*x42+48.7*x51+48.7*x52+52.0*x61+52.0*x62+64*x71+64*x72;48.7*x11+52*x21+61.3*x31+72*x41+48.7*x51+52*x61+64*x711020;48.7*x12+52*x22+61.3*x32+72*x42+48.7*x52+52*x62+64*x721024;2*x11+

28、3*x21+x31+0.5*x41+4*x51+2*x61+x7140;2*x12+3*x22+x32+0.5*x42+4*x52+2*x62+x7240;x11+x128;x21+x227;x31+x329;x41+x426;x51+x526;x61+x624;x71+x728;48.7*x51+48.7*x52+52.0*x61+52.0*x62+64.0*x71+64.0*x72302.7;gin(x11);gin(x12);gin(x21);gin(x22);gin(x31);gin(x32);gin(x41);gin(x42);gin(x51);gin(x52);gin(x61);g

29、in(x62);gin(x71);gin(x72);END,Lingo程序1,model:!平板车装载问题;sets:box/1.7/:t,w,n;car/1,2/;links(box,car):x;endsets!目标函数;max=sum(links(i,j):t(i)*x(i,j);!厚度约束;for(car(j):sum(box(i):t(i)*x(i,j)=1020;);!重量约束;for(car(j):sum(box(i):w(i)*x(i,j)=40;);!数量约束;for(box(i):x(i,1)+x(i,2)=n(i););!特殊约束;sum(box(i)|i#ge#5:t(i)*x(i,1)+t(i)*x(i,2)=302.7;for(links:gin(x);!这里是数据;data:t=48.7 52.0 61.3 72 48.7 52.0 64.0;w=2 3 1 0.5 4 2 1;n=8 7 9 6 6 4 8;enddataend,Lingo程序2,实验题：运筹学实验指导书中第10页问题2-2，问题2.4。,