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

《实验2Lingo求解运输问题和整数规划ppt课件.ppt》由会员分享，可在线阅读，更多相关《实验2Lingo求解运输问题和整数规划ppt课件.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)非线性规划(NL

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

3、mming Interface (V2.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. 确定

4、常数2. 识别类型,1. 单纯形算法2. 内点算法(选),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发点

5、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 5

6、5 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;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

7、);!需求约束; for(xiaodi(J): sum(chandi(I): x(I,J)=d(J);!产量约束; for(chandi(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 ENDSET

8、S）,数据段（DATA ENDDATA）,目标与约束段,初始段（INIT ENDINIT）(此题无初始数据),例2.2 选址问题,某公司有6个建筑工地，位置坐标为(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;e

9、ndsetsdata:!locations for the demand(需求点的位置);a=1.25,8.75,0.5,5.75,3,7.25;b=1.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

10、,j)*(x(j)-a(i)2+(y(j)-b(i)2)(1/2) );!demand constraints（需求约束）;for(demand(i):DEMAND_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),

11、选址问题：NLP,2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij ，在其它条件不变下使总吨公里数最小。,决策变量：ci j，(xj,yj)16维,非线性规划模型,Location(Non Linear),LINGO模型的构成：4个段,集合段（SETS ENDSETS）,数据段（DATA ENDDATA）,初始段（INIT ENDINIT）,目标与约束段,局部最优：89.8835(吨公里 ),LP：移到数据段,边界,集合的类型,集合 派生集合 基本集合 稀疏集合 稠密集合 元素列表法 元素过滤法 直接列举法 隐式列举法,setname /member_list/ : attri

12、bute_list;,setname(parent_set_list) /member_list/ : attribute_list;,SETS: CITIES /A1,A2,A3,B1,B2/; ROADS(CITIES, CITIES)/ A1,B1 A1,B2 A2,B1 A3,B2/:D; ENDSETS,SETS: STUDENTS /S1.S8/; PAIRS( STUDENTS, STUDENTS) | ENDSETS,集合元素的隐式列举,运算符的优先级,三类运算符： 算术运算符 逻辑运算符 关系运算符,集合循环函数,四个集合循环函数：FOR、SUM 、 MAX、MINfunct

13、ion( setname ( set_index_list) | condition : expression_list);,objective MAX = SUM( PAIRS( I, J): BENEFIT( I, J) * MATCH( I, J);FOR(STUDENTS( 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=MI

14、N(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 OptimumFeasibleInfeasibleUnboundedInterruptedUndetermined,7个选项卡(可设置80-90个控制参数),程序与数据分离,文本文件,使用外部数据文件,Cut (or Copy) Paste 方法FILE 输入数据、TEX

15、T输出数据（文本文件）OLE函数与电子表格软件（如EXCEL）连接ODBC函数与数据库连接LINGO命令脚本文件,LG4 （LONGO模型文件）LNG （LONGO模型文件）LTF （LONGO脚本文件）LDT （LONGO数据文件）LRP （LONGO报告文件）,常用文件后缀,2022/11/21,26,例题2.3 合理下料问题 现有一批长度一定的钢管，由于生产的需要，要求截出若干不同规格的钢管.试问：要如何截取原材料，既能满足生产的需要，又使得使用的原材料钢管数量最少？ 具体数据：原材料钢管长7.4m。要截成2.9m, 2.1m, 1.5m各为1000根，2000根，1000根.,解 把所

16、有可能的下料方式、按照各种下料方式从长7.4m的原料上得到的不同规格钢管的根数、残料长度，以及需要量列于表2.8中.例如，按照下料方式 ，可以得到2.9m钢管2根, 1.5m钢管1根. 问题转化为确定每种下料方式各用多少根7.4m的原料，可使被使用的原料根数最少.,2022/11/21,27,设 分别为按照 方式下料的原料根数，则得到问题的数学模型为,具体数据：原材料钢管长7.4m。要截成2.9m, 2.1m, 1.5m各为1000根，2000根，1000根.,2022/11/21,28,其解为 即最佳下料方案为：方式 ：200根；方式 ：800根；方式 ：200根；其他方式为0根.,mode

17、l: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 solution found. Objective value: 1200.000 Extended solver steps: 0 Total solver iterations: 5 Variable Value Re

18、duced 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=200;x3=800;x4=0;x5=200;x6=x7=x8=0最优值f=1200（根）,其中 gin(x1)-表变量x1为整数,2022/11/21,30,例2.4 某医院护士24小时值班，每次值班8小时.不同时段

19、需要的护士人数不等.据统计，各时段所需护士的最少人数如表2.9所示. 如何安排才能做到安排最少的护士就能满足工作的需要？,2022/11/21,31,解 设 为时段 开始上班的人数， .目标是要求护士的总数最少.因为每个护士都工作8小时，即连续工作2个时段后休息，所以问题的线性规划模型为：,2022/11/21,32,计算最优解为： 故该医院需雇用150名护士，最佳安排见表2.10所示.,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(

20、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.000000 X3 50.00000 1.000000 X4 0.000000 1.000000 X5 30.00000 1.000000 X6 0.000000 1.000000,与书中给出的最优解不同，但

21、最优值相同，故本题有对个最优解。,例4（布线问题）,解决某市消防站的布线 问题。该城市共有6个区，每个区都可以建立消防站，市政府希望设置的消防站最少，但必须满足在城市任何地方发生火警时，消防车要在15分钟之内赶到现场，根据实地考察，各区之间消防车行驶的时间见下表,请帮助该市制定一个最节省的计划。,各区之间消防车行驶的时间表,解：每个地区是否设消防站可用一个0-1变量来表示。令,i=1,2,6,本题要求消防站的个数最少，故目标函数为：,约束条件为：,各区之间消防车行驶的时间表,约束条件为：,OBJECTIVE FUNCTION VALUE 1) 2.000000 VARIABLE VALUE R

22、EDUCED 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+x61;x2+x5+x61;bin(x1);bin(x2);bin(x3);bin(x4);bin(x5);bin(x6);end,计算程序为,求解报告为,最优方案为x2=x4=1,即在第2区和第4

23、区设置消防站即可。,例2.5（最优装载问题）,（美国 1988 年大学生建摸竞赛B题),要把七种规格的包装箱装到两辆平板车上去，箱子的宽、高、相同，而厚度和重量不同。下表给出了他们的厚度和重量及数量。,每辆平板车有10.2米的地方用于装箱，载重40吨。由于货物的限制，对于第5、6、7三种包装箱的装载有如下约束：它们所占的空间（厚度）不得超过302.7厘米，试把这些包装箱装到平板车上去，使浪费的空间最小。,解：容易计算出所有的包装箱的厚度为27.495米，而两俩平板车共有20.4米长的地方，所以不可能都装上。 记表中所给出的第i种箱子的厚度、重量和数量分别为ti 、 wi 和 ni （i=1,2

24、,.,7),又记第i种箱子装到第1、2辆平板车上的数量分别为 xi1 ,xi2（i=1,2,.,7),问题要求浪费的空间最小，即装载所占的空间最大，故目标函数为：,约束条件为：,厚度约束：,重量约束：,每辆平板车有10.2米的地方用于装箱，载重40吨,记第i种箱子装到第1、2辆平板车上的数量分别为 （i=1,2,.,7),数量约束：,特殊约束：,或,第5、6、7三种包装箱的装载有如下约束：它们所占的空间（厚度）不得超过302.7厘米，,(每辆平板车不超过302.7cm),故得到两个整数规划模型为：,(IP1),(IP2),现解第一个问题：,(IP1),Liti3.ltx,Liti3.txt,利

25、用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.3x32+72x42+48.7x52+52x62+64x721024 2x11+3x21+x31+0.5x41+4x51+2x61+x7140 2x12+3x22+x32+0.5x42+

26、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.400variable value reduced cost x11 5.000000 -48.700001 x12 3.000000 -48.700001 x21 1.000000 -5

27、2.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.000000 X71 0.000000 -64.000000 X72 0.000000 -64.000000,MAX= 48.7*x11+48.7*x12+52.0

28、*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+3*x21+x31+0.5*x41+4*x51+2*x61+x7140;2*x12+3*x22+x32+0.5*x42+4*x52+2*x62+x724

29、0; 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);gin(x62);gin(x71);gin(x72); END,Lingo程序1,model:!平板车装载问题;sets: box/1.7

30、/: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。,