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

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) 非线性

2、规划(NLP),纯整数规划(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 Pro

3、gramming 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预处理程序,线性优化求解程序,非线性优化求解程序,分枝定界管理程

4、序,1. 确定常数 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软件，编制程序如下：

5、 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); d

6、ata: 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,产销不平衡问题,model: !6发点8收点运输问题; sets: chandi/A1.A6/: a; xiaodi/B1.B8/: d; links(chandi,xiaodi): c, x; endsets !目标函数; min=sum(

7、links(i,j): c(i,j)*x(i,j); !需求约束; 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; enddata end,

8、LINGO模型的构成：4个段,集合段（SETS ENDSETS）,数据段（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.

9、2/:x,y,e; link(demand,supply):c; endsets data: !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; enddata init: !initial locations for the supply（初始点）; !x,y=5,1,2,7; endinit !Ob

10、jective 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):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(

11、0.5,X,8.75); bnd(0.75,Y,7.75); ); END,Location(Linear),选址问题：NLP,2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij ，在其它条件不变下使总吨公里数最小。,决策变量： ci j，(xj,yj)16维,非线性规划模型,Location(Non Linear),LINGO模型的构成：4个段,集合段（SETS ENDSETS）,数据段（DATA ENDDATA）,初始段（INIT ENDINIT）,目标与 约束段,局部最优：89.8835(吨公里 ),LP：移到数据段,边界,集合的类型,集合 派生集合 基本集合 稀疏集合 稠

12、密集合 元素列表法 元素过滤法 直接列举法 隐式列举法,setname /member_list/ : attribute_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,集合元素的隐式列举,运算符的优先级,三类运算符：

13、 算术运算符 逻辑运算符 关系运算符,集合循环函数,四个集合循环函数：FOR、SUM 、 MAX、MIN function( 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

14、( MATCH( I, J); MAXB=MAX(PAIRS( I, J): BENEFIT( I, J); MINB=MIN(PAIRS( I, J): BENEFIT( I, J);,Example:,状态窗口,Solver Type: B-and-B Global Multistart,Model Class: LP， QP，ILP， IQP，PILP, PIQP，NLP，INLP，PINLP,State: Global Optimum Local Optimum Feasible Infeasible Unbounded Interrupted Undetermined,7个选项卡(可

15、设置80-90个控制参数),程序与数据分离,文 本 文 件,使用外部数据文件,Cut (or Copy) Paste 方法 FILE 输入数据、TEXT输出数据（文本文件） OLE函数与电子表格软件（如EXCEL）连接 ODBC函数与数据库连接 LINGO命令脚本文件,LG4 （LONGO模型文件） LNG （LONGO模型文件） LTF （LONGO脚本文件） LDT （LONGO数据文件） LRP （LONGO报告文件）,常用文件后缀,2020/8/17,26,例题2.3 合理下料问题 现有一批长度一定的钢管，由于生产的需要，要求截出若干不同规格的钢管.试问：要如何截取原材料，既能满足生产

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

17、，2000根，1000根.,2020/8/17,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 solution found. Objecti

18、ve 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=200;x3=800;x4=0; x5=

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

20、2+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.0000

21、00 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,

22、6,本题要求消防站的个数最少，故目标函数为：,约束条件为：,各区之间消防车行驶的时间表,约束条件为：,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+x

23、51; x4+x5+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厘米，试把这些包装箱装到

24、平板车上去，使浪费的空间最小。,解：容易计算出所有的包装箱的厚度为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三种包装箱的

25、装载有如下约束：它们所占的空间（厚度）不得超过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+64x72 st 48.7x11+52x21+61.3x31+72x41+48.7x51+52x61+64x7110

26、20 48.7x12+52x22+61.3x32+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+x329 x11+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 fun

27、ction value 1) 2039.400 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.000000 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+