实验2Lingo求解运输问题与整数规划

1、数学规划数学规划 实验实验2 Lingo2 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

2、lingo程序程序:优化模型 实际问题中的优化模型mixgtsxxxxfzMaxMiniTn, 2 , 1, 0)(. .),(),()(1或x决策变量f(x)目标函数gi(x)0约束条件数学规划线性规划(LP)二次规划(QP)非线性规划(NLP)纯整数规划(PIP)混合整数规划(MIP)整数规划(IP)0-1整数规划一般整数规划连续规划LINDO LINDO 公司软件产品简要介绍公司软件产品简要介绍 美国芝加哥(Chicago)大学的Linus Schrage教授于1980年前后开发, 后来成立 LINDO系统公司（LINDO Systems Inc.）， 网址：http:/ LINDO:

3、Linear INteractive and Discrete Optimizer (V6.1)LINGO: Linear INteractive General Optimizer (V8.0)LINDO API: LINDO Application Programming Interface (V2.0)Whats Best!: (SpreadSheet e.g. EXCEL) (V7.0)演示(试用)版、学生版、高级版、超级版、工业版、扩展版 （求解问题规模和选件不同）LINDOLINDO和和LINGOLINGO软件能求解的优化模型软件能求解的优化模型 LINGO LINDO优化模型线性

4、规划(LP)非线性规划(NLP)二次规划(QP)连续优化整数规划(IP)Lingo LP QP NLP IP 全局优化(选) ILP IQP INLP LINDO/LINGO软件的求解过程 LINDO/LINGO预处理程序线性优化求解程序非线性优化求解程序分枝定界管理程序1. 确定常数2. 识别类型1. 单纯形算法2. 内点算法(选)1、顺序线性规划法(SLP) 2、广义既约梯度法(GRG) (选) 3、多点搜索(Multistart) (选) 单位 销地运价产地B1B2B3B4B5B6B7B8产量 A16267425960 A24953858255 A35219743351A47673927

5、143A52395726541A65522814352销量3537223241324338 二、实验例题例2.1 使用LINGO软件计算6个发点8个收点的最小费用运输问题。产销单位运价如下表。302524143515560iia2803843324132223735iib 解:设第I个产地运到第j个销地的单位运价为cij ,第I个产地运到第j个销地的运量为 xij ,第I个产地的产量为ai (I=1,2,6),第j个销地的销量为 bj(j=1,2,8),运费为z,则此问题的数学模型为如下的数学规划问题: 8.,1, 6,.,2 , 1, 0)8,.,2 , 1()6,.,2 , 1(.min6

6、1816181jixjdxiaxtsxcijiiijijijijijij302524143515560iia2803843324132223735iib使用LINGO软件，编制程序如下：使用使用LINGO软件，编制程序如下：软件，编制程序如下：model:!6发点发点8收点运输问题收点运输问题;sets: warehouses/wh1.wh6/: capacity; vendors/v1.v8/: demand; links(warehouses,vendors): cost, volume;endsets!目标函数目标函数; min=sum(links: cost*volume);!需求约束

7、需求约束; 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;

8、enddataend 8.,1, 6,.,2 , 1, 0)8,.,2 , 1()6,.,2 , 1(.min61816181jixjdxicxtsxcijiiijijijijijij产销不平衡问题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(chandi

9、(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;enddataendLINGO模型的构成：模型的构成：4个段个段集合段（集合段（SETS ENDSETS）数据段（数据段（DATA ENDDATA）目标与目标与约束段约束段 初始段（初始段（INIT ENDINIT）(

10、此题无初始数据此题无初始数据) 例例2.22.2 选址问题选址问题某公司有6个建筑工地，位置坐标为(ai, bi) (单位：公里),水泥日用量di (单位：吨）ia1.258.750.55.7537.25b1.250.754.7556.57.75d35476111)现有 2 料场，位于 A (5, 1), B (2, 7),记(xj,yj),j=1,2, 日储量 ej各有 20 吨。假设：料场和工地之间有直线道路目标：制定每天的供应计划，即从 A, B 两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。用例中数据计算，最优解为i 1 2 3 4 5 6 1ic（料料场场 A） 3 5 0

11、7 0 1 2ic（料料场场 B） 0 0 4 0 6 10 2 , 1,6,.,1,. .)()(min612121612/122jecidctsbyaxcjijiiijjjiijijij线性规划模型决策变量：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

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

13、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); );ENDLocation(Linear)选址问题：选址问题：NLPNLP2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij ，在其它条件不变下使总吨公里数

14、最小。2 , 1,6,.,1,. .)()(min612121612/122jecidctsbyaxcjijiiijjjiijijij决策变量：ci j，(xj,yj)16维非线性规划模型Location(Non Linear)LINGO模型的构成：4个段集合段（SETS ENDSETS）数据段（DATA ENDDATA）初始段（INIT ENDINIT） 目标与约束段 局部最优：89.8835(吨公里 ) LP：移到数据段边界集合的类型集合的类型 集合 派生集合 基本集合 稀疏集合 稠密集合 元素列表法 元素过滤法 直接列举法 隐式列举法setname /member_list/ : att

15、ribute_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; ENDSETSSETS: STUDENTS /S1.S8/; PAIRS( STUDENTS, STUDENTS) | &2 #GT# &1: BENEFIT, MATCH;ENDSETS集合元素的集合元素的隐式列举隐式列举类型类型隐式列举格式隐式列举格式示例示例示例集合的元素示例集

16、合的元素数字型数字型 1.n1.51, 2, 3, 4, 5字符字符-数字型数字型stringM.stringNCar101.car208 Car101, car102, , car208星期型星期型 dayM.dayNMON.FRIMON, TUE, WED, THU, FRI月份型月份型 monthM.monthN OCT.JANOCT, NOV, DEC, JAN年份年份-月份型月份型monthYearM.monthYearNOCT2001.JAN2002OCT2001, NOV2001, DEC2001, JAN2002运算符的优先级运算符的优先级 优先级优先级运算符运算符最高最高#N

17、OT# （负号）负号）* /+ （减法）（减法）#EQ# #NE# #GT# #GE# #LT# #LE# #AND# #OR#最低最低(=)三类运算符： 算术运算符 逻辑运算符 关系运算符集合循环函数集合循环函数四个集合循环函数：FOR、SUM 、 MAX、MINfunction( setname ( set_index_list) | condition : expression_list);objective MAX = SUM( PAIRS( I, J): BENEFIT( I, J) * MATCH( I, J);FOR(STUDENTS( I): constraints SUM(

18、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:PAIRSJIJIMATCHJIBENEFIT),(),(*),(1),(),(IKorIJPAIRSKJKJMATCH状态窗口状态窗口Solver Type:B-and-BGlobal MultistartModel Class: LP， QP，

19、ILP， IQP，PILP, PIQP，NLP，INLP，PINLP State:Global OptimumLocal OptimumFeasibleInfeasibleUnboundedInterruptedUndetermined7个选项卡(可设置80-90个控制参数) 程序与数据分离文本文件使用外部数据文件 Cut (or Copy) Paste 方法 FILE 输入数据、TEXT输出数据（文本文件） OLE函数与电子表格软件（如EXCEL）连接 ODBC函数与数据库连接 LINGO命令脚本文件 LG4 （LONGO模型文件） LNG （LONGO模型文件） LTF （LONGO脚本文

20、件） LDT （LONGO数据文件） LRP （LONGO报告文件）常用文件后缀2022-5-626例题例题2.3 合理下料问题合理下料问题 现有一批长度一定的钢管，由于生产的需要，要求截出现有一批长度一定的钢管，由于生产的需要，要求截出若干不同规格的钢管若干不同规格的钢管. .试问：要如何截取原材料，既能满试问：要如何截取原材料，既能满足生产的需要，又使得使用的原材料钢管数量最少？足生产的需要，又使得使用的原材料钢管数量最少？ 具体数据：原材料钢管长具体数据：原材料钢管长7.4m7.4m。 要截成要截成2.9m, 2.1m, 1.5m2.9m, 2.1m, 1.5m各为各为10001000根

21、，根，20002000根，根，10001000根根. . 解解 把所有可能的下料方式、按照各种下料方式从把所有可能的下料方式、按照各种下料方式从长长7.4m7.4m的原料上得到的不同规格钢管的根数、残料的原料上得到的不同规格钢管的根数、残料长度，以及需要量列于表长度，以及需要量列于表2.82.8中中. .例如，按照下料方例如，按照下料方式式 ，可以得到，可以得到2.9m2.9m钢管钢管2 2根根, 1.5m, 1.5m钢管钢管1 1根根. . 问问题转化为确定每种下料方式各用多少根题转化为确定每种下料方式各用多少根7.4m7.4m的原料，的原料，可使被使用的原料根数最少可使被使用的原料根数最少

22、. .1B2022-5-627设设 分别为按照分别为按照 方式下料的原料根方式下料的原料根数，则得到问题的数学模型为数，则得到问题的数学模型为128,xxx128,B BB具体数据：原材料钢管长原材料钢管长7.4m7.4m。要截成。要截成2.9m, 2.1m, 2.9m, 2.1m, 1.5m1.5m各为各为10001000根，根，20002000根，根，10001000根根. . 2022-5-628128123457346512468m ins.t. 21000,2232000,32341000,0(1 ,2, ,8),jfjx xxx x x xx xx xxxxxxxxx 且 为 整

23、数 .其解为其解为 即最佳下料方案为：方式即最佳下料方案为：方式 ：200根；方式根；方式 ：800根；根；方式方式 ：200根；其他方式为根；其他方式为0根根.TT128( ,)(0 200 800 0 200 0 0 0) ,min1200，xx xxf3B2B5Bmodel: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)

24、;gin(x8);end128123457346512468mins.t. 21000,2232000,32341000,0(1,2, ,8),jfjx xxx xxxxxxxxxxxxxxx 且 为 整 数 . Global optimal 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.

25、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-5-630 例例2.4 2.4 某医院护士某医院护士2424小时值班，每次值班小时值班，每次值班8 8小时小时. .不同时段需要的护士人数不等不同时段需要的护士人数不等. .据统计，各时

26、段所据统计，各时段所需护士的最少人数如表需护士的最少人数如表2.92.9所示所示. . 如何安排才能做如何安排才能做到安排最少的护士就能满足工作的需要？到安排最少的护士就能满足工作的需要？2022-5-631解 设 为时段 开始上班的人数， .目标是要求护士的总数最少.因为每个护士都工作8小时，即连续工作2个时段后休息，所以问题的线性规划模型为：jxj1,2,6j 123456122334455616mins.t.70,60,50,20,30,60,0 (1,2,6),且为整数.jfxxxxxxxxxxxxxxxxxxxj2022-5-632 计算最优解为： 故该医院需雇用150名护士，最佳安

27、排见表2.10所示. T126( ,)(30,40,30,20,0,30) ,min150.Txx xxfmodel: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 V

28、alue 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与书中给出的最优解不同，但最优值相同，故本题有对个最优解。例4（布线问题）解决某市消防站的布线解决某市消防站的布线 问题。该城市共有问题。该城市共有6个区，每个区个区，每个区都可以建立消防站，市政府希望设置的消防站最少，但都可以建立消防站，市政府希望设置的消防站最少，但必须满足在城市任何地方发生火警时，消防车要在

29、必须满足在城市任何地方发生火警时，消防车要在15分分钟之内赶到现场，根据实地考察，各区之间消防车行驶钟之内赶到现场，根据实地考察，各区之间消防车行驶的时间见下表的时间见下表请帮助该市制定一个最节省的计划。请帮助该市制定一个最节省的计划。地区地区1 地区地区2地区地区3地区地区4地区地区 5地区地区6地区地区101016282720地区地区210024321710地区地区316240122721地区地区428321201525地区地区527172715014地区地区620102125140各区之间消防车行驶的时间表各区之间消防车行驶的时间表解：每个地区是否设消防站可用一个解：每个地区是否设消防站

30、可用一个0-1变量来表示。变量来表示。令令不设消防站，地区设消防站地区iixi0, 1i=1,2,6本题要求消防站的个数最少，故目标函数为：本题要求消防站的个数最少，故目标函数为：654321minxxxxxxz约束条件为：约束条件为：1612 xxx143 xx1534xxx1645xxx1526xxx6,.,110ixi，或 时间时间1234 56地区地区101016282720地区地区210024321710地区地区316240122721地区地区428321201525地区地区527172715014地区地区620102125140各区之间消防车行驶的时间表各区之间消防车行驶的时间表约

31、束条件为：约束条件为：) 1( 121确保地区 xx 111111.5266455344362121xxxxxxxxxxxxxxxxts6,.,110ixi，或654321minxxxxxxz 时间时间1234 56地区地区101016282720地区地区210024321710地区地区316240122721地区地区428321201525地区地区527172715014地区地区620102125140OBJECTIVE FUNCTION VALUE 1) 2.000000 VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X2 1.00000

32、0 1.000000 X3 0.000000 1.000000 X4 1.000000 1.000000 X5 0.000000 1.000000 X6 0.000000 1.000000min =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区设置消防站即可。区设置消防站即可。例2.5（最优装

33、载问题） （美国（美国 1988 年大学生建摸竞赛年大学生建摸竞赛B题题) 要把七种规格的包装箱装到两辆平板车上去，箱子的要把七种规格的包装箱装到两辆平板车上去，箱子的宽、高、相同，而厚度和重量不同。下表给出了他们的厚宽、高、相同，而厚度和重量不同。下表给出了他们的厚度和重量及数量。度和重量及数量。第i种箱子1234567 厚度t（厘米）48.752.061.372.048.752.064.0 重量w（千克）200030001000 5004000 2000 1000数量n8796648每辆平板车有每辆平板车有10.2米的地方用于装箱，载重米的地方用于装箱，载重40吨。由吨。由于货物的限制，对

34、于第于货物的限制，对于第5、6、7三种包装箱的装载有三种包装箱的装载有如下约束：它们所占的空间（厚度）不得超过如下约束：它们所占的空间（厚度）不得超过302.7厘米，试把这些包装箱装到平板车上去，使浪费的厘米，试把这些包装箱装到平板车上去，使浪费的空间最小。空间最小。 解：容易计算出所有的包装箱的厚度为解：容易计算出所有的包装箱的厚度为27.495米，而米，而两俩平板车共有两俩平板车共有20.4米长的地方，所以不可能都装上。米长的地方，所以不可能都装上。 记表中所给出的第记表中所给出的第i种箱子的厚度、重量和数量分别为种箱子的厚度、重量和数量分别为ti 、 wi 和和 ni （i=1,2,.,

35、7),又记第又记第i种箱子装到第种箱子装到第1、2辆平板辆平板车上的数量分别为车上的数量分别为 xi1 ,xi2（i=1,2,.,7)第i种箱子1234567 厚度ti（厘米）48.752.061.3 72.0 48.7 52.0 64.0 重量wi(吨）2310.5421数量ni8796648 问题要求浪费的空问题要求浪费的空间最小，即装载所间最小，即装载所占的空间最大，故占的空间最大，故目标函数为：目标函数为： 7121maxijijixtz约束条件为：约束条件为：厚度约束：厚度约束：2 , 1,102071jxtiiji重量约束：重量约束：712 , 1,40iijijxw第i种箱子12

36、34567厚度ticm48.752.061.372.048.752.064.0 重量wi(t）2310.5421数量ni8796648每辆平板车有每辆平板车有10.2米的地方用于米的地方用于装箱，载重装箱，载重40吨吨记第记第i种箱子装到第种箱子装到第1、2辆平板车上的辆平板车上的数量分别为数量分别为 （i=1,2,.,7)21,iixx数量约束：数量约束：217,.,2 , 1,jiijinx特殊约束：特殊约束：7521, 7 .302)(iiiixxt2 , 1, 7 .30275jxtiiji或或第i种箱子1234567厚度ticm48.752.061.372.048.752.064.0

37、 重量wi(t）2310.5421数量ni8796648第第5、6、7三种包装箱的装载有三种包装箱的装载有如下约束：它们所占的空间如下约束：它们所占的空间（厚度）不得超过（厚度）不得超过302.7厘米，厘米，(每辆平板车不每辆平板车不超过超过302.7cm) 7121maxijijixtz71752121712, 1,10207 .302)(7,.,2, 1,2, 1,40.iijiiiiijiijiijijxtxxtinxjxwts为为整整数数, 2 , 1, 7,.,1i , 0 jxij故得到两个整数规划模型为：故得到两个整数规划模型为：(IP1)(IP2) 7121maxijijixt

38、z717521712, 1,10202, 1,7 .3027,.,2, 1,2, 1,40.iijijijijiijiijijxtjxtinxjxwts为为整整数数, 2 , 1, 7,.,1i , 0 jxij现解第一个问题：现解第一个问题：(IP1)71752121712, 1,10207 .302)(7,.,2, 1,2, 1,40.712maxiijijiiijiijiijijxtxxtinxjxwtsijijixtz为为整整数数, 2 , 1, 7,.,1i , 0 jxijLiti3.ltxLiti3.txt利用利用lindo 求解得到最优解为：求解得到最优解为：平板 车 1平 板

39、 车 2箱子类型c1c2c3c4c5c6c7c1c2c3c4c5c6c7最优值解10 5 6 0 0 0 08 2 7 0 2 0 0 2039.4解28 5 6 0 0 0 00 2 3 6 3 3 0 2039.4解30 6 9 0 0 3 08 1 0 6 3 0 0 2039.4解45 1 9 1 2 0 03 6 0 5 1 3 0 2039.4MAX 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

40、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+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 -52.000000 x22 6.000000 -52.000000 x31 9.000000 -61.299999