《第五节软件的最优化求解课件.ppt》由会员分享，可在线阅读，更多相关《第五节软件的最优化求解课件.ppt（60页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五节软件的最优化求解第1页，此课件共60页哦简要提纲简要提纲 优化模型简介优化模型简介LINGO软件的使用简介软件的使用简介 建模与求解实例（结合软件使用）建模与求解实例（结合软件使用）第2页，此课件共60页哦优化模型优化模型实际问题中实际问题中的优化模型的优化模型x决策变量决策变量f(x)目标函数目标函数gi(x)0约束条件约束条件数学规划数学规划线性规划线性规划(LP)二次规划二次规划(QP)非线性规划非线性规划(NLP)纯整数规划纯整数规划(PIP)混合整数规划混合整数规划(MIP)整数规划整数规划(IP)0-1整数规划整数规划一般整数规划一般整数规划连续规划连续规划第3页，此课件共6
2、0页哦LINDO和和LINGO软件能求解的优化模型软件能求解的优化模型LINGOLINDO优化模型优化模型线性规划线性规划(LP)非线性规划非线性规划(NLP)二次规划二次规划(QP)连续优化连续优化整数规划整数规划(IP)第4页，此课件共60页哦LPQPNLPIP全局优化全局优化(选选)ILPIQPINLPLINDO/LINGO软件的求解过程 LINDO/LINGO预处理程序预处理程序线性优化求解程序线性优化求解程序非线性优化求解程序非线性优化求解程序分枝定界管理程序分枝定界管理程序1.确定常数确定常数2.识别类型识别类型1.单纯形算法单纯形算法2.内点算法内点算法(选选)1、顺序线性规划法
3、、顺序线性规划法(SLP)2、广义既约梯度法、广义既约梯度法(GRG)(选选)3、多点搜索、多点搜索(Multistart)(选选)第5页，此课件共60页哦建模时需要注意的几个基本问题建模时需要注意的几个基本问题1、尽量使用实数优化，减少整数约束和整数变量尽量使用实数优化，减少整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数尽量使用光滑优化，减少非光滑约束的个数如：尽量少使用绝对值、符号函数、多个变量求最大如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量的个数尽量使用线性模型，减
4、少非线性约束和非线性变量的个数（如（如x/y5改为改为x5y）4、合理设定变量上下界，尽可能给出变量初始值合理设定变量上下界，尽可能给出变量初始值5、模型中使用的参数数量级要适当模型中使用的参数数量级要适当(如小于如小于103)第6页，此课件共60页哦Lingo需要掌握的几个重要方面需要掌握的几个重要方面掌握集合掌握集合(SETS)的应用；的应用；正确阅读求解报告；正确阅读求解报告；正确理解求解状态窗口；正确理解求解状态窗口；学会设置基本的求解选项学会设置基本的求解选项(OPTIONS)；掌握与外部文件的基本接口方法掌握与外部文件的基本接口方法第7页，此课件共60页哦例例1加工奶制品的生产计划
5、加工奶制品的生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶时间时间480小时小时至多加工至多加工100公斤公斤A1制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获利增加到30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？每天：每天：第8页，此课件共60页哦1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利2
6、4元/公斤 获利16元/公斤 x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2获利获利243x1获利获利164 x2原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变量目标函数目标函数每天获利每天获利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480小时小时至多加工至多加工100公斤公斤A150桶牛奶桶牛奶每天每天第9页，此课件共60页哦模型求解模型求解Globaloptimalsolutionfound.Objectivevalue:3360.000Infeasibilities:0.000000Totalsolveriteration
7、s:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.00000020桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元。元。model:max=72*x1+64*x2;milkx1+x250;time12*x1+8*x2480;cpct3*x1100;end第10页，此课件共60页哦模型求解模型求解reduced
8、cost值值表表示示当当该该非非基基变变量量增增加加一一个个单单位位时时（其其他他非非基基变变量量保保持持不不变变）目目标标函函数数减减少少的的量量(对对max型问题型问题)Globaloptimalsolutionfound.Objectivevalue:3360.000Infeasibilities:0.000000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.0000004
9、8.00000TIME0.0000002.000000CPCT40.000000.000000也可理解为：也可理解为：为为了了使使该该非非基基变变量量变变成成基基变变量量，目目标标函函数数中中对对应应系系数数应应增增加加的的量量第11页，此课件共60页哦Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPric13360.0001.0000
10、00MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40model:max=72*x1+64*x2;milkx1+x250;time12*x1+8*x2480;cpct3*x1100;end三三种种资资源源“资源资源”剩余为零的约束为紧约束（有效约束）剩余为零的约束为紧约束（有效约束）结果解释结果解释第12页，此课件共60页哦Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterati
11、ons:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPric13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000结果解释结果解释最优解下最优解下“资源资源”增加增加1单位时单位时“效益效益”的增的增量量原料增原料增1单位单位,利润增利润增48时间加时间加1单位单位,利润增利润增2能力增减不影响利润能力增减不影响利润影子价格影子价格35元可买到元可买到1桶牛奶，要买吗？桶牛奶，
12、要买吗？3548,应该买！应该买！聘用临时工人付出的工资最多每小时几元？聘用临时工人付出的工资最多每小时几元？2元！元！第13页，此课件共60页哦Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncrea
13、seDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000最优解不变时目标系最优解不变时目标系数允许变化范围数允许变化范围DORANGE(SENSITIVITY)ANALYSISx1系数范围系数范围(64,96)x2系数范围系数范围(48,72)A1获利增加到获利增加到30元元/千克，应否改变生产计划千克，应否改变生产计划x1系数由系数由24 3=72增加增加为为30 3=90，在，在允许范围允许范围内内不变！不变！(约束条件不变约束条件不变)结果解释结果解释第14
14、页，此课件共60页哦结果解释结果解释Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.33
15、33380.00000CPCT100.0000INFINITY40.00000影子价格有意义影子价格有意义时约束右端的允时约束右端的允许变化范围许变化范围原料最多增加原料最多增加10时间最多增加时间最多增加5335元可买到元可买到1桶牛奶，每天最多买多少？桶牛奶，每天最多买多少？最多买最多买10桶？桶？(目标函数不变目标函数不变)注意注意:充分但充分但可能不必要可能不必要第15页，此课件共60页哦LINGO软件简介软件简介目标与约束段目标与约束段集合段（集合段（SETSENDSETS）数据段（数据段（DATAENDDATA）初始段（初始段（INITENDINIT）计算段（计算段（CALCEND
16、CALC）LINGO9.0模型的构成：模型的构成：5个段个段LINGO模型的优点模型的优点提供了灵活的编程语言（矩阵生成器）提供了灵活的编程语言（矩阵生成器）第16页，此课件共60页哦LINGO模型模型 例：选址问题例：选址问题某公司有某公司有6个建筑工地，位置坐标为个建筑工地，位置坐标为(ai,bi)(单位：公里单位：公里),水泥水泥日用量日用量di(单位：吨）单位：吨）假设：假设：料场和料场和工地之间有直工地之间有直线道路线道路第17页，此课件共60页哦用例中数据计算，最优解为总吨公里数为总吨公里数为总吨公里数为总吨公里数为136.2线性规划模型线性规划模型决策变量：决策变量：ci j(料
17、料场场j到到工地工地i的运的运量）量）12维维第18页，此课件共60页哦选址问题：选址问题：NLP2）改建两个新料场，需要确定新料场位置）改建两个新料场，需要确定新料场位置(xj,yj)和运量和运量cij，在其它条件不变下使总吨公里数最小。，在其它条件不变下使总吨公里数最小。决策变量：决策变量：ci j，(xj,yj)16维维非线性规划模型非线性规划模型第19页，此课件共60页哦LINGO模型的构成：模型的构成：4个段个段集合段（集合段（SETSENDSETS）数据段（数据段（DATAENDDATA）初始段（初始段（INITENDINIT）目标与目标与约束段约束段局部最优：局部最优：89.88
18、35(吨公里吨公里)LP：移到数据段：移到数据段第20页，此课件共60页哦边界第21页，此课件共60页哦集合的类型集合的类型集合集合派生集合派生集合基本集合基本集合稀疏集合稀疏集合稠密集合稠密集合元素列表法元素列表法元素过滤法元素过滤法直接列举法直接列举法隐式列举法隐式列举法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/
19、:D;ENDSETSSETS:STUDENTS/S1.S8/;PAIRS(STUDENTS,STUDENTS)|&2#GT#&1:BENEFIT,MATCH;ENDSETS第22页，此课件共60页哦最短路问题求求S到到T最短路长最短路长模型模型第23页，此课件共60页哦匹配问题某班级8名同学准备分成4个调查队（每队2人）前往4个地区进行社会调查，假设8名同学两两组队效率如表所示，问如何组队可以使总效率最高？第24页，此课件共60页哦模型表示两同学组队，等于零表示不组队表示两同学组队，等于零表示不组队第25页，此课件共60页哦集合元素的集合元素的隐式列举隐式列举类型隐式列举格式示例示例集合的元素
20、数字型1.n1.51,2,3,4,5字符-数字型stringM.stringNCar101.car208 Car101,car102,car208星期型dayM.dayNMON.FRIMON,TUE,WED,THU,FRI月份型monthM.monthNOCT.JANOCT,NOV,DEC,JAN年份-月份型monthYearM.monthYearNOCT2001.JAN2002OCT2001,NOV2001,DEC2001,JAN2002第26页，此课件共60页哦运算符的优先级运算符的优先级 优先级运算符最高#NOT#（负号）*/+（减法）#EQ#NE#GT#GE#LT#LE#AND#OR#
21、最低(=)三类运算符：三类运算符：算术运算符算术运算符逻辑运算符逻辑运算符关系运算符关系运算符第27页，此课件共60页哦集合循环函数集合循环函数四个集合循环函数：四个集合循环函数：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(PAI
22、RS(I,J):BIN(MATCH(I,J);MAXB=MAX(PAIRS(I,J):BENEFIT(I,J);MINB=MIN(PAIRS(I,J):BENEFIT(I,J);Example:第28页，此课件共60页哦状态窗口状态窗口Solver Type:B-and-BGlobal MultistartModel Class:LP，QP，ILP，IQP，PILP,PIQP，NLP，INLP，PINLP State:Global OptimumLocal OptimumFeasibleInfeasibleUnboundedInterruptedUndetermined第29页，此课件共60页
23、哦7个选项卡个选项卡(可设置可设置80-90个控制参数个控制参数)第30页，此课件共60页哦 程序与数据分离程序与数据分离文文本本文文件件使用外部数据文件使用外部数据文件Cut(orCopy)Paste方法方法FILE输入数据、输入数据、TEXT输出数据（文本文件）输出数据（文本文件）OLE函数与电子表格软件（如函数与电子表格软件（如EXCEL）连接）连接ODBC函数与数据库连接函数与数据库连接LINGO命令脚本文件命令脚本文件LG4（LONGO模型文件）模型文件）LNG（LONGO模型文件）模型文件）LTF（LONGO脚本文件）脚本文件）LDT（LONGO数据文件）数据文件）LRP（LONG
24、O报告文件）报告文件）常用文件后缀常用文件后缀第31页，此课件共60页哦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:JXIEBJ2004MCMmydata.xls,CITIES);COST,NEED,SU
25、PPLY=OLE(mydata.xls);OLE(mydata.xls,SOLUTION)=SHIP;ENDDATAEND mydata.xls文件中必须有下列名称(及数据)：CITIES，COST，NEED，SUPPLY，SOLUTION在在EXCEL中还可以通过中还可以通过“宏宏”自动调用自动调用LINGO(略略)也可以将也可以将EXCEL表格嵌入到表格嵌入到LINGO模型中模型中(略略)演示演示MydataExample.lg4第33页，此课件共60页哦ODBC ODBC：与数据库连接：与数据库连接输入基本集合元素：输入基本集合元素：setname/ODBC(datasource,tab
26、lename,columnname)/输入派生集合元素：输入派生集合元素：setname/ODBC(source,table,column1,column2)/目前支持下列目前支持下列DBMS:(如为其他数据库，则需自行安装驱动如为其他数据库，则需自行安装驱动)ACCESS，DBASE，EXCEL，FOXPRO，ORACLE，PARADOX，SQLSERVER，TEXEFILES使用数据库之前，数据源需要在使用数据库之前，数据源需要在ODBC管理器注册管理器注册输入数据：输入数据：Attr_list=ODBC(source,table,column1,column2)输出数据：输出数据：ODB
27、C(source,table,column1,column2)=Attr_list具体例子略具体例子略第34页，此课件共60页哦建模实例与求解建模实例与求解最短路问题最短路问题下料问题下料问题露天矿的运输问题露天矿的运输问题钢管运输问题钢管运输问题第35页，此课件共60页哦最短路问题最短路问题求各点到求各点到T的最短路的最短路56774968658336C1B1C2B2A1A2A3TS6shortestPath.lg4第36页，此课件共60页哦问题问题1.如何下料最节省如何下料最节省?例例 钢管下料钢管下料 问题问题2.客户增加需求：客户增加需求：原料钢管原料钢管:每根每根19米米 4米米50
28、根根 6米米20根根 8米米15根根 客户需求客户需求节省的标准是什么？节省的标准是什么？由于采用不同切割模式太多，会增加生产和管理成本，规定切由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过割模式不能超过3种。如何下料最节省？种。如何下料最节省？5米米10根根 第37页，此课件共60页哦按照客户需要在一根原料钢管上安排切割的一种组合。按照客户需要在一根原料钢管上安排切割的一种组合。切割模式切割模式余料余料1 1米米 4米米1根根 6米米1根根 8米米1根根余料余料3米米4米米1根根6米米1根根6米米1根根合理切割模式合理切割模式的余料应小于客户需要钢管的最小尺寸的余料应小
29、于客户需要钢管的最小尺寸余料余料3米米8米米1根根8米米1根根钢管下料钢管下料 第38页，此课件共60页哦为满足客户需要，按照哪些种合理模式，每种模式切割为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？多少根原料钢管，最为节省？合理切割模式合理切割模式2.所用原料钢管总根数最少所用原料钢管总根数最少模式模式4米钢管根数米钢管根数6米钢管根数米钢管根数8米钢管根数米钢管根数余料余料(米米)14003231013201341203511116030170023钢管下料问题钢管下料问题1 两种两种标准标准1.原料钢管剩余总余量最小原料钢管剩余总余量最小第39页，此课件共60
30、页哦xi 按第按第i 种模式切割的原料钢管根数种模式切割的原料钢管根数(i=1,2,7)约束约束满足需求满足需求 决策变量决策变量 目标目标1（总余量）（总余量）按模式按模式2切割切割12根根,按模式按模式5切割切割15根，余料根，余料27米米模模式式4米米根数根数6米米根数根数8米米根数根数余余料料14003231013201341203511116030170023需需求求502015最优解：最优解：x2=12,x5=15,其余为其余为0；最优值：最优值：27整数约束：整数约束：xi 为整数为整数第40页，此课件共60页哦当余料没有用处时，当余料没有用处时，通常以总根数最少为目标通常以总根
31、数最少为目标 目标目标2（总根数）（总根数）钢管下料问题钢管下料问题1 约束条约束条件不变件不变 最优解：最优解：x2=15,x5=5,x7=5,其余为其余为0；最优值：最优值：25。xi 为整数按模式按模式2切割切割15根，根，按模式按模式5切割切割5根，按根，按模式模式7切割切割5根，共根，共25根，余料根，余料35米米虽余料增加虽余料增加8米，但减少了米，但减少了2根根与与目标目标1的结果的结果“共切割共切割27根，余料根，余料27米米”相比相比第41页，此课件共60页哦钢管下料问题钢管下料问题2对大规模问题，用模型的约束条件界定合理模式对大规模问题，用模型的约束条件界定合理模式增加一种
32、需求：增加一种需求：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米长的钢管的数量米长的钢管的数量第42页，此课件共60页哦满足需求满足需求模式合理：每根余模式合理：每根余料不超过料不超
33、过3米米整数非线性规划模型整数非线性规划模型钢管下料问题钢管下料问题2目标函数（目标函数（总根数）总根数）约束约束条件条件整数约束：整数约束：xi,r1i,r2i,r3i,r4i(i=1,2,3)为整数为整数第43页，此课件共60页哦增加约束，缩小可行域，便于求解增加约束，缩小可行域，便于求解原料钢管总根数下界：原料钢管总根数下界：特殊生产计划：对每根原料钢管特殊生产计划：对每根原料钢管模式模式1：切割成：切割成4根根4米钢管，需米钢管，需13根；根；模式模式2：切割成：切割成1根根5米和米和2根根6米钢管，需米钢管，需10根；根；模式模式3：切割成：切割成2根根8米钢管，需米钢管，需8根。根
34、。原料钢管总根数上界：原料钢管总根数上界：31模式排列顺序可任定模式排列顺序可任定钢管下料问题钢管下料问题2需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根根每根原料钢管长每根原料钢管长19米米第44页，此课件共60页哦LINGO求解整数非线性规划模型求解整数非线性规划模型Localoptimalsolutionfoundatiteration:12211Objectivevalue:28.00000VariableValueReducedCostX110.000000.000000X210.000002.000000X38.0000001.000000R113.
35、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：每根原料钢管切割成：每根原料钢管切割
36、成2根根4米、米、1根根5米和米和1根根6米钢管，共米钢管，共10根；根；模式模式3：每根原料钢管切割成：每根原料钢管切割成2根根8米钢管，共米钢管，共8根。根。原料钢管总根数为原料钢管总根数为28根。根。演示演示cut02a.lg4；cut02b.lg4第45页，此课件共60页哦露天矿里铲位已分成矿石和岩石露天矿里铲位已分成矿石和岩石:平均铁含量不低于平均铁含量不低于25%的为的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多安置的平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电
37、铲，电铲平均装车时间一台电铲，电铲平均装车时间5分钟分钟卡车在等待时所耗费的能量也是相当可观的，原则上在安排卡车在等待时所耗费的能量也是相当可观的，原则上在安排时时不应发生卡车等待不应发生卡车等待的情况。的情况。露天矿生产的车辆安排露天矿生产的车辆安排(CUMCM-2003B)矿石卸点需要的铁含量要求都为矿石卸点需要的铁含量要求都为29.5%1%(品位限制），品位限制），搭配量在一个班次（搭配量在一个班次（8小时）内满足品位限制即可。卸点在小时）内满足品位限制即可。卸点在一个班次内不变。卡车载重量为一个班次内不变。卡车载重量为154吨，平均时速吨，平均时速28km,平均平均卸车时间为卸车时间为
38、3分钟。分钟。问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次分别在哪些路线上各运输多少次?第46页，此课件共60页哦平面示意图第47页，此课件共60页哦问题数据问题数据 距离铲位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
39、.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%第48页，此课件共60页哦问题分析问题分析 与典型的运输问题明显有以下不同：与典型的运输问题明显有以下不同：1.这是运输矿石与岩石两种物资的问题；这是运输矿石与岩石两种物资的问题；2.属于产量大
40、于销量的不平衡运输问题；属于产量大于销量的不平衡运输问题；3.为了完成品位约束，矿石要搭配运输；为了完成品位约束，矿石要搭配运输；4.产地、销地均有单位时间的流量限制；产地、销地均有单位时间的流量限制；5.运输车辆只有一种，每次满载运输，运输车辆只有一种，每次满载运输，154吨吨/车次；车次；6.铲位数多于铲车数意味着要最优的选择不多于铲位数多于铲车数意味着要最优的选择不多于7个产个产地作为最后结果中的产地；地作为最后结果中的产地；7.最后求出各条路线上的派出车辆数及安排。最后求出各条路线上的派出车辆数及安排。近似处理：近似处理：先求出产位、卸点每条线路上的运输量先求出产位、卸点每条线路上的运
41、输量(MIP模型模型)然后求出各条路线上的派出车辆数及安排然后求出各条路线上的派出车辆数及安排第49页，此课件共60页哦模型假设模型假设卡车在一个班次中不应发生等待或熄火后再启动的情卡车在一个班次中不应发生等待或熄火后再启动的情况；况；在铲位或卸点处由两条路线以上造成的冲突问题面在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认为不前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论；冲突。我们不排时地进行讨论；空载与重载的速度都是空载与重载的速度都是28km/h，耗油相差很大；，耗油相差很大；卡车可提前退出系统，等等。卡车可提前退出系统，等
42、等。如理解为严格不等待，难以用数学规划模型来解如理解为严格不等待，难以用数学规划模型来解个别参数队找到了可行解个别参数队找到了可行解（略）（略）第50页，此课件共60页哦符号符号xij：从：从i铲位到铲位到j号卸点的石料运量号卸点的石料运量（车）（车）单位：单位：吨；吨；cij：从：从i号铲位到号铲位到j号卸点的距离号卸点的距离公里；公里；Tij:从从i号铲位到号号铲位到号j卸点路线上运行一个周期平均时间卸点路线上运行一个周期平均时间分；分；Aij：从号铲位到号卸点最多能同时运行的卡车数：从号铲位到号卸点最多能同时运行的卡车数辆；辆；Bij：从号铲位到号卸点路线上一辆车最多可运行的次数：从号铲
43、位到号卸点路线上一辆车最多可运行的次数次；次；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为关闭。为关闭。(近似近似)第51页，此课件共60页哦优化模型（1）道路能力道路能力(卡车数卡车数)约束约束（2）电铲能力约束（3）卸点能力约
44、束（4）铲位储量约束（5）产量任务约束（6）铁含量约束（7）电铲数量约束（8）整数约束.xij为非负整数fi 为0-1整数第52页，此课件共60页哦计算结果（计算结果（LINGO软件）软件）铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿漏135411倒4243岩场7015岩漏8143倒13270铲位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.489cumcm2003b1.lg4第53页，此课件共60页哦计算结果（派车）计算结果（派
45、车）铲位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、9、10处各放置一台电铲。处各放置一台电铲。一共使用了一共使用了13辆卡车；总运量为辆卡车；总运量为85628.62吨公里；吨公里；岩石产量为岩石产量为32186吨；矿石产量为吨；矿石产量为38192吨。吨。此外：此外：6辆联合派车（方案略）辆联合派车（方案略）第54页，此课件共60页哦最大化产量最大化产量结论：结论：（略）（略）目标函数变化目标函数变化此外：车辆数量（此外：车辆数量（20辆）限制
46、（其实上面的模型也应该辆）限制（其实上面的模型也应该有）有）第55页，此课件共60页哦A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7铁路运价表里程300301350351400401450451500运价2023262932钢管运输问题钢管运输问题（CUMCM-
47、2000B)第56页，此课件共60页哦常用解法常用解法:二次规划二次规划先计算最小运费矩阵先计算最小运费矩阵两种运输方式（铁路公路）混合最短路问题两种运输方式（铁路公路）混合最短路问题是普通最短路问题的变种，需要自己设计算法是普通最短路问题的变种，需要自己设计算法钢管运输问题钢管运输问题（CUMCM-2000B)第57页，此课件共60页哦fi表示钢厂表示钢厂i是否使用；是否使用；xij是从钢厂是从钢厂i运到节点运到节点j的钢管量的钢管量yj是从节点是从节点j向左铺设的钢管量；向左铺设的钢管量；zj是向右铺设的钢管量是向右铺设的钢管量 钢管运输问题钢管运输问题（CUMCM-2000B)LINDO/LINGO得得到的结果比到的结果比matlab得到的好得到的好cumcm2000b.lg4第58页，此课件共60页哦其他优化赛题其他优化赛题飞行管理问题飞行管理问题空洞探测问题空洞探测问题钻井布局问题钻井布局问题抢渡长江问题抢渡长江问题等等等等第59页，此课件共60页哦Thats all.Any Questions?谢谢大家！第60页，此课件共60页哦