优化模型与LINDOLINGO优化软件教程来自清华大学数学科学系市公开课一等奖百校联赛特等奖课件.pptx

数学建模讲座（7月8月江西）优化模型与LINDO/LINGO优化软件谢金星谢金星清华大学数学科学系清华大学数学科学系Tel:010-62787812Email:http:/ 优化模型介绍优化模型介绍LINDO企业主要软件产品及功效介绍企业主要软件产品及功效介绍LINDO软件使用介绍软件使用介绍LINGO软件使用介绍软件使用介绍 建模与求解实例（结合软件使用）建模与求解实例（结合软件使用）第2页优化模型优化模型 实际问题中实际问题中优化模型优化模型x决议变量决议变量f(x)目标函数目标函数gi(x)0约束条约束条件件数学规划数学规划线性规划线性规划(LP)二次规划二次规划(QP)非线性规划非线性规划(NLP)纯整数规划纯整数规划(PIP)混合整数规划混合整数规划(MIP)整数规划整数规划(IP)0-1整数规划整数规划普通整数规划普通整数规划连续规划连续规划第3页LINDO LINDO 企业软件产品简明介绍企业软件产品简明介绍美国芝加哥美国芝加哥(Chicago)大学大学LinusSchrage教授于教授于1980年年前后开发前后开发,以后成立以后成立LINDO系统企业（系统企业（LINDOSystemsInc.），），网址：网址：http:/LINDO:LinearINteractiveandDiscreteOptimizer(V6.1)LINGO:LinearINteractiveGeneralOptimizer(V8.0)LINDOAPI:LINDOApplicationProgrammingInterface(V2.0)WhatsBest!:(SpreadSheete.g.EXCEL)(V7.0)演演示示(试用试用)版、学生版、高级版、超级版、工业版、版、学生版、高级版、超级版、工业版、扩展版扩展版（求解（求解问题规模问题规模和和选件选件不一样）不一样）第4页LINDOLINDO和和LINGOLINGO软件能求解优化模型软件能求解优化模型LINGOLINDO优化模型优化模型线性规划线性规划(LP)非线性规划非线性规划(NLP)二次规划二次规划(QP)连续优化连续优化整数规划整数规划(IP)第5页LPQPNLPIP全局优化全局优化(选选)ILPIQPINLPLINDO/LINGO软件求解过程 LINDO/LINGO预处理程序预处理程序线性优化求解程序线性优化求解程序非线性优化求解程序非线性优化求解程序分枝定界管理程序分枝定界管理程序1.确定常数确定常数2.识别类型识别类型1.单纯形算法单纯形算法2.内点算法内点算法(选选)1、次序线性规划法、次序线性规划法(SLP)2、广义既约梯度法、广义既约梯度法(GRG)(选选)3、多点搜索、多点搜索(Multistart)(选选)第6页建模时需要注意几个基本问题建模时需要注意几个基本问题1、尽可能使用实数优化，降低整数约束和整数变量尽可能使用实数优化，降低整数约束和整数变量2、尽可能使用光滑优化，降低非光滑约束个数尽可能使用光滑优化，降低非光滑约束个数如：尽可能少使用绝对值、符号函数、多个变量求如：尽可能少使用绝对值、符号函数、多个变量求最大最大/最小值、四舍五入、取整函数等最小值、四舍五入、取整函数等3、尽可能使用线性模型，降低非线性约束和非线性变尽可能使用线性模型，降低非线性约束和非线性变量个数量个数（如（如x/y5改为改为x5y）4、合理设定变量上下界，尽可能给出变量初始值合理设定变量上下界，尽可能给出变量初始值5、模型中使用参数数量级要适当模型中使用参数数量级要适当(如小于如小于103)第7页需要掌握几个主要方面需要掌握几个主要方面1、LINDO:正确阅读求解汇报（尤其要掌握敏感性分析）正确阅读求解汇报（尤其要掌握敏感性分析）2、LINGO：掌握集合掌握集合(SETS)应用；应用；正确阅读求解汇报；正确阅读求解汇报；正确了解求解状态窗口；正确了解求解状态窗口；学会设置基本求解选项学会设置基本求解选项(OPTIONS)；掌握与外部文件基本接口方法掌握与外部文件基本接口方法第8页例例1加工奶制品生产计划加工奶制品生产计划1桶牛奶 3千克A1 12小时 8小时 4千克A2 或赢利24元/千克 赢利16元/千克 50桶牛奶桶牛奶时间时间480小时小时 至多加工至多加工100千克千克A1制订生产计划，使天天赢利最大制订生产计划，使天天赢利最大 35元可买到元可买到1桶牛奶，买吗？若买，天天最多买多少桶牛奶，买吗？若买，天天最多买多少?可聘用暂时工人，付出工资最多是每小时几元可聘用暂时工人，付出工资最多是每小时几元?A1赢利增加到赢利增加到30元元/千克，应否改变生产计划？千克，应否改变生产计划？天天：天天：第9页1桶牛奶 3千克A1 12小时 8小时 4千克A2 或赢利24元/千克 赢利16元/千克 x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2赢利赢利243x1赢利赢利164 x2原料供给原料供给 劳动时间劳动时间 加工能力加工能力 决议变量决议变量 目标函数目标函数 天天赢利天天赢利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100千克千克A150桶牛奶桶牛奶天天天天第10页模型求解模型求解 max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100endOBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元。元。第11页模型求解模型求解 reduced cost值值表表示示当当该该非非基基变变量量增增加加一一个个单单位位时时（其其它它非非基基变变量量保保持持不不变变）目目标标函函 数数 降降 低低 量量(对对max型问题型问题)OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2也可了解为：也可了解为：为为了了使使该该非非基基变变量量变变成成基基变变量量，目目标标函函数数中中对对应应系数应增加量系数应增加量第12页OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000原料无剩下原料无剩下时间无剩下时间无剩下加工能力剩下加工能力剩下40max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三种种资资源源“资源资源”剩下为零约束为紧约束（有效约束）剩下为零约束为紧约束（有效约束）结果解释结果解释 第13页OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000结果解释结果解释 最优解下最优解下“资源资源”增增加加1单位时单位时“效益效益”增增量量原料增原料增1单位单位,利润增利润增48时间加时间加1单位单位,利润增利润增2能力增减不影响利润能力增减不影响利润影子价格影子价格35元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？35”（或（或“=”（或（或“=”）功效相）功效相同同2.变量与系数间可有空格变量与系数间可有空格(甚至回车甚至回车),但无运算符但无运算符3.变量名以字母开头，不能超出变量名以字母开头，不能超出8个字符个字符4.变量名不区分大小写（包含变量名不区分大小写（包含LINDO中关键字）中关键字）5.目标函数所在行是第一行，第二行起为约束条件目标函数所在行是第一行，第二行起为约束条件6.行号行号(行名行名)自动产生或人为定义。行名以自动产生或人为定义。行名以“）”结结束束7.行中注有行中注有“!”符号后面部分为注释。如符号后面部分为注释。如:!ItsComment.8.在模型任何地方都能够用在模型任何地方都能够用“TITLE”对模型命名对模型命名（最多（最多72个字符），如：个字符），如：TITLEThisModelisonlyanExample第17页9.变量不能出现在一个约束条件右端变量不能出现在一个约束条件右端10.表示式中不接收括号表示式中不接收括号“()”和逗号和逗号“,”等任何符等任何符号号,例例:400(X1+X2)需写为需写为400X1+400X211.表示式应化简，如表示式应化简，如2X1+3X2-4X1应写成应写成-2X1+3X212.缺省假定全部变量非负；可在模型缺省假定全部变量非负；可在模型“END”语句后语句后用用“FREEname”将变量将变量name非负假定取消非负假定取消13.可在可在“END”后用后用“SUB”或或“SLB”设定变量上设定变量上下界下界比如：比如：“subx110”作用等价于作用等价于“x1=10”但用但用“SUB”和和“SLB”表示上下界约束不计入模型表示上下界约束不计入模型约束，也不能给出其松紧判断和敏感性分析。约束，也不能给出其松紧判断和敏感性分析。14.“END”后对后对0-1变量说明：变量说明：INTn或或INTname15.“END”后对整数变量说明：后对整数变量说明：GINn或或GINname使用使用LINDOLINDO一些注意事项一些注意事项第18页二次规划规划(QP)问题LINDO可求解二次规划可求解二次规划(QP)问题，但输入方式较问题，但输入方式较复杂，因为在复杂，因为在LINDO中不许出现非线性表示式中不许出现非线性表示式需要为每一个实际约束增加一个对偶变量需要为每一个实际约束增加一个对偶变量（LAGRANGE乘子），在实际约束前增加相关乘子），在实际约束前增加相关变量一阶最优条件，转化为互补问题变量一阶最优条件，转化为互补问题“END”后面使用后面使用QCP命令指明实际约束开始行号，命令指明实际约束开始行号，然后才能求解然后才能求解提议总是用提议总是用LINGO解解QP注意注意对对QP和和IP:敏感性分析意义不大敏感性分析意义不大第19页状态窗口状态窗口（LINDO Solver Status）当前状态：已达最优解当前状态：已达最优解迭代次数：迭代次数：18次次约束不满足约束不满足“量量”(不是不是“约束个数约束个数”)：0当前目标值：当前目标值：94最好整数解：最好整数解：94整数规划界：整数规划界：93.5分枝数：分枝数：1所用时间：所用时间：0.00秒（太快秒（太快了，还不到了，还不到0.005秒）秒）刷新本界面间隔刷新本界面间隔:1(秒秒)第20页选项设置选项设置Preprocess：预处理：预处理(生成割平面生成割平面)；PreferredBranch：优先分枝方式：优先分枝方式：“Default”（缺省方式）、（缺省方式）、“Up”（向上取整优先）、（向上取整优先）、“Down”（向下取整优先）；（向下取整优先）；IPOptimalityTol：IP最优值允许误差最优值允许误差上限（一个百分数，如上限（一个百分数，如5%即即0.05）；）；IPObjectiveHurdle：IP目标函数篱笆目标函数篱笆值，即只寻找比这个值更优最优解（如值，即只寻找比这个值更优最优解（如当知道当前模型某个整数可行解时，就当知道当前模型某个整数可行解时，就能够设置这个值）；能够设置这个值）；IPVarFixingTol：固定一个整数变量：固定一个整数变量取值所依据一个上限（假如一个整数变取值所依据一个上限（假如一个整数变量判别数（量判别数（REDUCEDCOST）值很大，）值很大，超出该上限，则以后求解中把该整数变超出该上限，则以后求解中把该整数变量固定下来）。量固定下来）。NonzeroLimit：非零系数个数上限；非零系数个数上限；IterationLimit：最大迭代步数；最大迭代步数；InitialContraintTol：约束初始误差上限；约束初始误差上限；FinalContraintTol：约束最终误差上限；约束最终误差上限；EnteringVarTol：进基变量进基变量REDUCEDCOST误差限；误差限；PivotSizeTol：旋转元误差限旋转元误差限第21页Report/Statistics第一行：模型有第一行：模型有5行（约束行（约束4行），行），4个变量，两个整数变量（没有个变量，两个整数变量（没有0-1变量），从第变量），从第4行开始是二次规划实际约束。行开始是二次规划实际约束。第二行：非零系数第二行：非零系数19个，约束中非零系数个，约束中非零系数12个个(其中其中6个为个为1或或-1)，模型密度为模型密度为0.760(密度密度=非零系数非零系数/行数行数(变量数变量数)。第三行意思：按绝对值看，系数最小、最大分别为第三行意思：按绝对值看，系数最小、最大分别为0.3和和277。第四行意思：模型目标为极小化；小于等于、等于、大于等于约束第四行意思：模型目标为极小化；小于等于、等于、大于等于约束分别有、个；广义上界约束（分别有、个；广义上界约束（GUBS）不超出个；变）不超出个；变量上界约束（量上界约束（VUBS）不少于个。所谓）不少于个。所谓GUBS，是指一组不含，是指一组不含有相同变量约束；所谓有相同变量约束；所谓VUBS，是指一个蕴涵变量上界约束，如，是指一个蕴涵变量上界约束，如从约束从约束X1+X2-X3=0能够看出，若能够看出，若X3=0，则，则X1=0，X2=0（因为（因为有非负限制），所以有非负限制），所以X1+X2-X3=0是一个是一个VUBS约束。约束。第五行意思：只含个变量约束个数第五行意思：只含个变量约束个数=个；冗余列数个；冗余列数=个个ROWS=5 VARS=4 INTEGER VARS=2(0=0/1)QCP=4NONZEROS=19 CONSTRAINT NONZ=12(6=+-1)DENSITY=0.760SMALLEST AND LARGEST ELEMENTS IN ABSOLUTE VALUE=0.300000 277.000OBJ=MIN,NO.:2 0 2,GUBS=0SINGLE COLS=0 REDUNDANT COLS=0第22页LINDOLINDO行命令、命令脚本文件行命令、命令脚本文件批处理：能够采取命令脚本（行命令序列）批处理：能够采取命令脚本（行命令序列）WINDOWS环境下行命令意义不大环境下行命令意义不大Example演示演示用用FILE/TAKECOMMANDS(F11)命令调入命令调入必须是以必须是以LINDOPACKED形式形式（压缩）保留文件（压缩）保留文件FILE/SAVE命令命令SAVE行命令行命令第23页LINGO软件介绍软件介绍目标与约束段目标与约束段集合段（集合段（SETSENDSETS）数据段（数据段（DATAENDDATA）初始段（初始段（INITENDINIT）LINGO模型组成：模型组成：4个段个段LINGO模型优点模型优点包含了包含了LINDO全部功效全部功效提供了灵活编程语言（矩阵生成器）提供了灵活编程语言（矩阵生成器）第24页LINGOLINGO模型模型 例：选址问题例：选址问题某企业有某企业有6个建筑工地，位置坐标为个建筑工地，位置坐标为(ai,bi)(单位：公单位：公里里),水泥日用量水泥日用量di(单位：吨）单位：吨）假设：假设：料场料场和工地之间和工地之间有直线道路有直线道路第25页用例中数据计算，最优解为总吨公里数为总吨公里数为总吨公里数为总吨公里数为136.2136.2线性规划模型线性规划模型决议变量：决议变量：ci j(料场料场j到到工地工地i运量）运量）12维维第26页选址问题：选址问题：NLPNLP2）改建两个新料场，需要确定新料场位置）改建两个新料场，需要确定新料场位置(xj,yj)和运量和运量cij，在其它条件不变下使总吨公里数最小。，在其它条件不变下使总吨公里数最小。决议变量：决议变量：ci j，(xj,yj)16维维非线性规划模型非线性规划模型第27页LINGO模型组成：模型组成：4个段个段集合段（集合段（SETSENDSETS）数据段（数据段（DATAENDDATA）初始段（初始段（INITENDINIT）目标与目标与约束段约束段局部最优：局部最优：89.8835(吨公里吨公里)LP：移到数据段：移到数据段第28页边界第29页集合类型集合类型集合集合派生集合派生集合基本集合基本集合稀疏集合稀疏集合稠密集合稠密集合元素列表法元素列表法元素过滤法元素过滤法直接列举法直接列举法隐式列举法隐式列举法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;ENDSETSSETS:STUDENTS/S1.S8/;PAIRS(STUDENTS,STUDENTS)|&2#GT#&1:BENEFIT,MATCH;ENDSETS第30页集合元素集合元素隐式列举隐式列举类类型型隐隐式列式列举举格式格式示例示例示例集合元素数字型数字型 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.monthYearNOCT.JANOCT,NOV,DEC,JAN第31页运算符优先级运算符优先级 优优先先级级运算符运算符最高最高#NOT#（负负号）号）*/+（减法）（减法）#EQ#NE#GT#GE#LT#LE#AND#OR#最低最低(=)三类运算符：三类运算符：算术运算符算术运算符逻辑运算符逻辑运算符关系运算符关系运算符第32页集合循环函数集合循环函数四个集合循环函数：四个集合循环函数：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(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:第33页状态窗口状态窗口Solver Type:B-and-BGlobal MultistartModel Class:LP，QP，ILP，IQP，PILP,PIQP，NLP，INLP，PINLP State:Global OptimumLocal OptimumFeasibleInfeasibleUnboundedInterruptedUndetermined第34页7 7个选项卡个选项卡(可设置可设置80-9080-90个控制参数个控制参数)第35页 程序与数据分离程序与数据分离文文本本文文件件使用外部数据文件使用外部数据文件Cut(orCopy)Paste方法方法FILE输入数据、输入数据、TEXT输出数据（文本文件）输出数据（文本文件）OLE函数与电子表格软件（如函数与电子表格软件（如EXCEL）连接）连接ODBC函数与数据库连接函数与数据库连接LINGO命令脚本文件命令脚本文件LG4（LONGO模型文件）模型文件）LNG（LONGO模型文件）模型文件）LTF（LONGO脚本文件）脚本文件）LDT（LONGO数据文件）数据文件）LRP（LONGO汇报文件）汇报文件）惯用文件后缀惯用文件后缀第36页FILEFILE和和TEXTTEXT：文本文件输入输出：文本文件输入输出MODEL:SETS:MYSET/FILE(myfile.txt)/:FILE(myfile.txt);ENDSETSMIN=SUM(MYSET(I):SHIP(I)*COST(I);FOR(MYSET(I):CON1 SHIP(I)NEED(I);CON2 SHIP(I)NEED(I);CON2 SHIP(I)SUPPLY(I);DATA:MYSET=OLE(D:JXIEBJMCMmydata.xls,CITIES);COST,NEED,SUPPLY=OLE(mydata.xls);OLE(mydata.xls,SOLUTION)=SHIP;ENDDATAEND mydata.xls文件中必须有以下名称(及数据)：CITIES，COST，NEED，SUPPLY，SOLUTION在在EXCEL中还能够经过中还能够经过“宏宏”自动调用自动调用LINGO(略略)也能够将也能够将EXCEL表格嵌入到表格嵌入到LINGO模型中模型中(略略)演示演示MydataExample.lg4第38页ODBC ODBC：与数据库连接：与数据库连接输入基本集合元素：输入基本集合元素：setname/ODBC(datasource,tablename,columnname)/输入派生集合元素：输入派生集合元素：setname/ODBC(source,table,column1,column2)/当前支持以下当前支持以下DBMS:(如为其它数据库，则需自行安装驱动如为其它数据库，则需自行安装驱动)ACCESS，DBASE，EXCEL，FOXPRO，ORACLE，PARADOX，SQLSERVER，TEXEFILES使用数据库之前，数据源需要在使用数据库之前，数据源需要在ODBC管理器注册管理器注册输入数据：输入数据：Attr_list=ODBC(source,table,column1,column2)输出数据：输出数据：ODBC(source,table,column1,column2)=Attr_list详细例子略详细例子略第39页建模实例与求解建模实例与求解最短路问题最短路问题下料问题下料问题露天矿运输问题露天矿运输问题钢管运输问题钢管运输问题第40页最短路问题最短路问题求各点到求各点到T最短路最短路56774968658336C1B1C2B2A1A2A3TS6shortestPath.lg4第41页问题问题1.怎样下料最节约怎样下料最节约?例例 钢管下料钢管下料 问题问题2.客户增加需求：客户增加需求：原料钢管原料钢管:每根每根19米米 4米米50根根 6米米20根根 8米米15根根 客户需求客户需求节约标准是什么？节约标准是什么？因为采取不一样切割模式太多，会增加生产和管理成因为采取不一样切割模式太多，会增加生产和管理成本，要求切割模式不能超出本，要求切割模式不能超出3种。怎样下料最节约？种。怎样下料最节约？5米米10根根 第42页按照客户需要在一根原料钢管上安排切割一个组合。按照客户需要在一根原料钢管上安排切割一个组合。切割模式切割模式余料余料1 1米米 4米米1根根 6米米1根根 8米米1根根余料余料3米米4米米1根根6米米1根根6米米1根根合理切割模式合理切割模式余料应小于客户需要钢管最小尺寸余料应小于客户需要钢管最小尺寸余料余料3米米8米米1根根8米米1根根钢管下料钢管下料 第43页为满足客户需要，按照哪些种合理模式，每种模式为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节约？切割多少根原料钢管，最为节约？合理切割模式合理切割模式2.所用原料钢管总根数最少所用原料钢管总根数最少模式模式4米钢管根数米钢管根数6米钢管根数米钢管根数8米钢管根数米钢管根数余料余料(米米)14003231013201341203511116030170023钢管下料问题钢管下料问题1 1 两种两种标准标准1.原料钢管剩下总余量最小原料钢管剩下总余量最小第44页xi 按第按第i 种模式切割原料钢管根数种模式切割原料钢管根数(i=1,2,7)约束约束满足需求满足需求 决议变量决议变量 目标目标1（总余量）（总余量）按模式按模式2切割切割12根根,按模式按模式5切割切割15根，余料根，余料27米米模模式式4米米根数根数6米米根数根数8米米根数根数余余料料14003231013201341203511116030170023需需求求502015最优解：最优解：x2=12,x5=15,其余为其余为0；最优值：最优值：27整数约束：整数约束：xi 为整数为整数第45页当余料没有用处时，当余料没有用处时，通常以总根数最少为目标通常以总根数最少为目标 目标目标2（总根数）（总根数）钢管下料问题钢管下料问题1 1 约束条约束条件不变件不变 最优解：最优解：x2=15,x5=5,x7=5,其余为其余为0；最优值：最优值：25。xi 为整数按模式按模式2切割切割15根，根，按模式按模式5切割切割5根，根，按模式按模式7切割切割5根，根，共共25根，余料根，余料35米米虽余料增加虽余料增加8米，但降低了米，但降低了2根根与与目标目标1结果结果“共切割共切割27根，余料根，余料27米米”相比相比第46页钢管下料问题钢管下料问题2 2对大规模问题，用模型约束条件界定合理模式对大规模问题，用模型约束条件界定合理模式增加一个需求：增加一个需求：5米米10根；切割根；切割模式不超出模式不超出3种。种。现有现有4种种需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根，用枚举法确定合理切割模式，过于复杂。根，用枚举法确定合理切割模式，过于复杂。决议变量决议变量 xi 按第按第i 种模式切割原料钢管根数种模式切割原料钢管根数(i=1,2,3)r1i,r2i,r3i,r4i 第第i 种切割模式下，每根原料钢种切割模式下，每根原料钢管生产管生产4米、米、5米、米、6米和米和8米长钢管数量米长钢管数量第47页满足需求满足需求模式合理：每根模式合理：每根余料不超出余料不超出3米米整数非线性规划模型整数非线性规划模型钢管下料问题钢管下料问题2 2目标函数（目标函数（总根数）总根数）约束约束条件条件整数约束：整数约束：xi,r1i,r2i,r3i,r4i(i=1,2,3)为整数为整数第48页增加约束，缩小可行域，便于求解增加约束，缩小可行域，便于求解原料钢管总根数下界：原料钢管总根数下界：特殊生产计划：对每根原料钢管特殊生产计划：对每根原料钢管模式模式1：切割成：切割成4根根4米钢管，需米钢管，需13根；根；模式模式2：切割成：切割成1根根5米和米和2根根6米钢管，需米钢管，需10根；根；模式模式3：切割成：切割成2根根8米钢管，需米钢管，需8根。根。原料钢管总根数上界：原料钢管总根数上界：31模式排列次序可任定模式排列次序可任定钢管下料问题钢管下料问题2 2需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根根每根原料钢管长每根原料钢管长19米米第49页LINGOLINGO求解整数非线性规划模型求解整数非线性规划模型Localoptimalsolutionfoundatiteration:12211Objectivevalue:28.00000VariableValueReducedCostX110.000000.000000X210.000002.000000X38.0000001.000000R113.0000000.000000R122.0000000.000000R130.0000000.000000R210.0000000.000000R221.0000000.000000R230.0000000.000000R311.0000000.000000R321.0000000.000000R330.0000000.000000R410.0000000.000000R420.0000000.000000R432.0000000.000000模式模式1：每根原料钢管切割成：每根原料钢管切割成3根根4米和米和1根根6米钢管，共米钢管，共10根；根；模式模式2：每根原料钢管切割成：每根原料钢管切割成2根根4米、米、1根根5米和米和1根根6米钢管，米钢管，共共10根；根；模式模式3：每根原料钢管切割成：每根原料钢管切割成2根根8米钢管，共米钢管，共8根。根。原料钢管总根数为原料钢管总根数为28根。根。演示演示cut02a.lg4；cut02b.lg4第50页露天矿里铲位已分成矿石和岩石露天矿里铲位已分成矿石和岩石:平均铁含量不低于平均铁含量不低于25%为矿石，不然为岩石。每个铲位矿石、岩石数量，为矿石，不然为岩石。每个铲位矿石、岩石数量，以及矿石平均铁含量（称为品位）都是已知。每个铲位以及矿石平均铁含量（称为品位）都是已知。每个铲位至多安置一台电铲，电铲平均装车时间至多安置一台电铲，电铲平均装车时间5分钟分钟卡车在等候时所花费能量也是相当可观，标准上在安排卡车在等候时所花费能量也是相当可观，标准上在安排时时不应发生卡车等候不应发生卡车等候情况。情况。露天矿生产车辆安排露天矿生产车辆安排(CUMCM-B)矿石卸点需要铁含量要求都为矿石卸点需要铁含量要求都为29.5%1%(品位限制），品位限制），搭配量在一个班次（搭配量在一个班次（8小时）内满足品位限制即可。卸小时）内满足品位限制即可。卸点在一个班次内不变。卡车载重量为点在一个班次内不变。卡车载重量为154吨，平均时速吨，平均时速28km,平均卸车时间为平均卸车时间为3分钟。分钟。问题：出动几台电铲，分别在哪些铲位上；出动几辆问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次卡车，分别在哪些路线上各运输多少次?第51页平面示意图第52页问题数据问题数据 距离铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏5.265.194.214.002.952.742.461.900.641.27倒装1.900.991.901.131.272.251.482.043.093.51岩场5.895.615.614.563.513.652.462.461.060.57岩石漏0.641.761.271.832.742.604.213.725.056.10倒装4.423.863.723.162.252.810.781.621.270.50铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石量095105100105110125105130135125岩石量125110135105115135105115135125铁含量30%28%29%32%31%33%32%31%33%31%第53页问题分析问题分析 与经典运输问题显著有以下不一样：与经典运输问题显著有以下不一样：1.这是运输矿石与岩石两种物资问题；这是运输矿石与岩石两种物资问题；2.属于产量大于销量不平衡运输问题；属于产量大于销量不平衡运输问题；3.为了完成品位约束，矿石要搭配运输；为了完成品位约束，矿石要搭配运输；4.产地、销地都有单位时间流量限制；产地、销地都有单位时间流量限制；5.运输车辆只有一个，每次满载运输，运输车辆只有一个，每次满载运输，154吨吨/车次；车次；6.铲位数多于铲车数意味着要最优选择不多于铲位数多于铲车数意味着要最优选择不多于7个产个产地作为最终结果中产地；地作为最终结果中产地；7.最终求出各条路线上派出车辆数及安排。最终求出各条路线上派出车辆数及安排。近似处理：近似处理：先求出产位、卸点每条线路上运输量先求出产位、卸点每条线路上运输量(MIP模型模型)然后求出各条路线上派出车辆数及安排然后求出各条路线上派出车辆数及安排第54页模型假设模型假设卡车在一个班次中不应发生等候或熄火后再开启卡车在一个班次中不应发生等候或熄火后再开启情况；情况；在铲位或卸点处由两条路线以上造成冲突问题面在铲位或卸点处由两条路线以上造成冲突问题面前，我们认为只要平均时间能完成任务，就认为前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论；不冲突。我们不排时地进行讨论；空载与重载速度都是空载与重载速度都是28km/h，耗油相差很大；，耗油相差很大；卡车可提前退出系统，等等。卡车可提前退出系统，等等。如了解为严格不等候，难以用数学规划模型来解如了解为严格不等候，难以用数学规划模型来解个别参数队找到了可行解个别参数队找到了可行解（略）（略）第55页符号符号xij：从：从i铲位到铲位到j号卸点石料运量号卸点石料运量（车）（车）单位：单位：吨；吨；cij：从：从i号铲位到号铲位到j号卸点距离号卸点距离公里；公里；Tij:从从i号铲位到号号铲位到号j卸点路线上运行一个周期平均时间卸点路线上运行一个周期平均时间分；分；Aij：从号铲位到号卸点最多能同时运行卡车数：从号铲位到号卸点最多能同时运行卡车数辆；辆；Bij：从号铲位到号卸点路线上一辆车最多可运行次数：从号铲位到号卸点路线上一辆车最多可运行次数次；次；pi：i号铲位矿石铁含量号铲位矿石铁含量p=(30,28,29,32,31,33,32,31,33,31)%qj:j号卸点任务需求，号卸点任务需求，q=(1.2,1.3,1.3,1.9,1.3)*10000吨吨cki：i号铲位铁矿石储量号铲位铁矿石储量万吨万吨cyi：i号铲位岩石储量号铲位岩石储量万吨万吨fi:描述第描述第i号铲位是否使用号铲位是否使用0-1变量，取变量，取1为使用；为使用；0为关闭。为关闭。(近似近似)第56页优化模型（1）道路能力道路能力(卡车数卡车数)约束约束（2）电铲能力约束（3）卸点能力约束（4）铲位储量约束（5）产量任务约束（6）铁含量约束（7）电铲数量约束（8）整数约束.xij为非负整数fi 为0-1整数第57页计算结果（计算结果（LINGOLINGO软件）软件）铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿漏131354541111倒42424343岩场70701515岩漏81814343倒13132 27070铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏0.8671.8620.314倒场1.0771.162岩场1.8920.326岩石漏1.8411.229倒场0.6840.11.489cumcmb1.lg4第58页计算结果（派车）计算结果（派车）铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏1(29)倒场1(39)1(37)岩场1(37)岩石漏1(44)1(35)倒场1(47)结论：结论：铲位铲位1、2、3、4、8、