《优化建模与LindoLingo优化软件》由会员分享,可在线阅读,更多相关《优化建模与LindoLingo优化软件(80页珍藏版)》请在金锄头文库上搜索。
1、数学建模讲座(数学建模讲座(2005年年8月月2日日 北戴河)北戴河)优化建模与优化建模与LINDO/LINGO优化软件优化软件谢金星谢金星清华大学数学科学系清华大学数学科学系Tel:010-62787812Email:http:/ 1.优化模型与优化软件简介优化模型与优化软件简介2.LINDO公司的主要软件产品及功能简介公司的主要软件产品及功能简介3.LINDO/LINGO软件的使用简介软件的使用简介4.建模与求解实例(结合软件使用)建模与求解实例(结合软件使用)骏驰厌攫宜弄烃邵孩箱荧凡扣谍苗谤人蹋岿怪朵蔬垣诽叶锤消录姻勾拍粳优化建模与Lindo,Lingo优化软件优化建模与Lindo,Li
2、ngo优化软件1.优化模型与优化软件简介优化模型与优化软件简介埔渔至拆泡衰惩就缆双度图愁苯绸配挂奥绞糊筒派角辫反稠裸伯献十绘吾优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件最优化是工程技术、经济管理、科学研究、最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题社会生活中经常遇到的问题,如如:优化模型和优化软件的重要意义优化模型和优化软件的重要意义结构设计结构设计资源分配资源分配生产计划生产计划运输方案运输方案解决优化问题的手段解决优化问题的手段经验积累,主观判断经验积累,主观判断作试验,比优劣作试验,比优劣建立数学模型建立数学模型(优化模型优化模型
3、),求最优策略,求最优策略(决策决策)( (最最) )优化优化: :在一定条件下在一定条件下, ,寻求使目标最大寻求使目标最大( (小小) )的决策的决策 CUMCMCUMCM赛题:约一半以上与优化有关,需用软件求解赛题:约一半以上与优化有关,需用软件求解磨莱期萧庭督淖进仔支俺诅渔窍氖急背姥豆预惮石洱织掇值真捉糙柬凹烤优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件运筹学运筹学(OR:Operations/OperationalResearch)管理科学管理科学(MS:ManagementScience)决策科学决策科学(DS:DecisionScience)(
4、最最)优化理论是运筹学的基本内容优化理论是运筹学的基本内容无无约约束束优优化化OR/MS/DS优化优化(Optimization),规划规划(Programming)线线性性规规划划非非线线性性规规划划网网络络优优化化组组合合优优化化整整数数规规划划不不确确定定规规划划多多目目标标规规划划目目标标规规划划动动态态规规划划妄航讽五洒贼棚肾仙今漏咕俯琳肢榜土辣娃桌臃取蝎戏啄柏钟演往畅敬闲优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件优化问题三要素:优化问题三要素:决策变量决策变量;目标函数目标函数;约束条件约束条件约约束束条条件件决策变量决策变量优化问题的一般形式
5、优化问题的一般形式可行解(满足约束)与可行域(可行解的集合)可行解(满足约束)与可行域(可行解的集合)最优解(取到最小大值的可行解)最优解(取到最小大值的可行解)目标函数目标函数鸳恫浪翻慢侄枚茅嫉钦橙猿拈陵启纵陋崇重醒隔蝶期堆痢袭啥牢耳溯捌浦优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件无约束优化无约束优化: :最优解的分类和条件最优解的分类和条件给定一个函数给定一个函数 f( (x),),寻找寻找 x* 使得使得 f( (x*)最小,即最小,即其中其中局部最优解局部最优解全局最优解全局最优解必要条件必要条件x*f(x)xlxgo充分条件充分条件Hessian
6、阵阵最优解在可行域边界上取得时不能用无约束优化方法求解最优解在可行域边界上取得时不能用无约束优化方法求解袋兄漫迭斥军铱粥霞刁武河麦氰犀恕榴济韧疾铂烷姜核赛尽润张毯醋滥符优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件约束优化的约束优化的简单分类简单分类线性规划线性规划(LP)目标和约束均为线性函数目标和约束均为线性函数非线性规划非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函数二次规划二次规划(QP)目标为二次函数、约束为线性目标为二次函数、约束为线性整数规划整数规划(IP)决策变量决策变量(全部或部分全部或部分)为整数为整数整数整数线性线
7、性规划规划(ILP),整数,整数非线性非线性规划规划(INLP)纯整数规划纯整数规划(PIP),混合整数规划混合整数规划(MIP)一般整数规划,一般整数规划,0-1(整数)规划(整数)规划连连续续优优化化离离散散优优化化数学规划数学规划缀文电典喀匠圾婶萨皆答狈粟渠员捻颊只验库姚椭拥范茧癌玻庐褂艘懂械优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件常用优化软件常用优化软件 1.LINDO/LINGO软件软件2.MATLAB优化工具箱优化工具箱3.EXCEL软件的优化功能软件的优化功能4.SAS(统计分析统计分析)软件的优化功能软件的优化功能5.其他其他帆痰投忻爽遭
8、抒蜜娜痕翁抡迫子得伯佃铭遣酿召痊孪撕奈埔木你十式狗妇优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件MATLABMATLAB优化工具箱优化工具箱能求解的优化模型能求解的优化模型优化工具箱优化工具箱3.0(MATLAB7.0R14)连续优化连续优化离散优化离散优化无约束优化无约束优化非线性非线性极小极小fminunc非光滑非光滑(不可不可微微)优化优化fminsearch非线性非线性方方程程(组组)fzerofsolve全局全局优化优化暂缺暂缺非线性非线性最小二乘最小二乘lsqnonlinlsqcurvefit线性规划线性规划linprog纯纯0-1规划规划bin
9、tprog一般一般IP(暂缺暂缺)非线性规划非线性规划fminconfminimaxfgoalattainfseminf上下界约束上下界约束fminbndfminconlsqnonlinlsqcurvefit约束线性约束线性最小二乘最小二乘lsqnonneglsqlin约束优化约束优化二次规划二次规划quadprog查启敢崩郧睡牙厂豌策杏深宏凰懦氢拷测贞颤碌醛闪依弊朴墩难存墒棺袖优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件2.LINDO公司的主要软件产品及功能简介公司的主要软件产品及功能简介旋显呵碟湿缸哉拂喳窥搔彭显撇囤万栗惠凭草临缨谨侵配幕否茶聋弯漾啸优化
10、建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件LINDO LINDO 公司软件产品简要介绍公司软件产品简要介绍美国芝加哥美国芝加哥(Chicago)大学的大学的LinusSchrage教授于教授于1980年前后开发年前后开发,后来成立后来成立LINDO系统公司(系统公司(LINDOSystemsInc.),),网址:网址:http:/LINDO:LinearINteractiveandDiscreteOptimizer(V6.1)LINGO:LinearINteractiveGeneralOptimizer(V9.0)LINDOAPI:LINDOApplicati
11、onProgrammingInterface(V3.0)WhatsBest!:(SpreadSheete.g.EXCEL)(V8.0)演演示示(试用试用)版、学生版、高级版、超级版、工业版、版、学生版、高级版、超级版、工业版、扩展版扩展版(求解(求解问题规模问题规模和和选件选件不同)不同)故旅脖英渴粗痊爪监继酱狠囱帛须奏蘸跋万跳样聋焙攘诚捕证唬讽河存纲优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件LINDOLINDO和和LINGOLINGO软件能求解的优化模型软件能求解的优化模型LINGOLINDO优化模型优化模型线性规划线性规划(LP)非线性规划非线性规划(
12、NLP)二次规划二次规划(QP)连续优化连续优化整数规划整数规划(IP)埔树晓汾锰丢虏毛糖瘫徘榴株嘱斋羚舷尊嘎创工沾烷雇狗篱诉拱稠铡被嗣优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件LPQPNLPIP全局优化全局优化(选选)ILPIQPINLPLINDO/LINGO软件的求解过程 LINDO/LINGO预处理程序预处理程序线性优化求解程序线性优化求解程序非线性优化求解程序非线性优化求解程序分枝定界管理程序分枝定界管理程序1.确定常数确定常数2.识别类型识别类型1.单纯形算法单纯形算法2.内点算法内点算法(选选)1、顺序线性规划法、顺序线性规划法(SLP)2、广
13、义既约梯度法、广义既约梯度法(GRG)(选选)3、多点搜索、多点搜索(Multistart)(选选)虑闪次绞峙惹渭蕊鱼簿顽熙坐槛缺歇宛嫩苫冠钝褐荔乎干汕属忆叔粳肚殃优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件建模时需要注意的几个基本问题建模时需要注意的几个基本问题1、尽量使用实数优化,减少整数约束和整数变量尽量使用实数优化,减少整数约束和整数变量2、尽量使用光滑优化,减少非光滑约束的个数尽量使用光滑优化,减少非光滑约束的个数如:尽量少使用绝对值、符号函数、多个变量求最如:尽量少使用绝对值、符号函数、多个变量求最大大/最小值、四舍五入、取整函数等最小值、四舍五
14、入、取整函数等3、尽量使用线性模型,减少非线性约束和非线性变量尽量使用线性模型,减少非线性约束和非线性变量的个数的个数(如(如x/y5改为改为x5y)4、合理设定变量上下界,尽可能给出变量初始值合理设定变量上下界,尽可能给出变量初始值5、模型中使用的参数数量级要适当模型中使用的参数数量级要适当(如小于如小于103)鼻箭坟悦谎障枚闯畔梳踢铂癸衅阔尔局房潞惠渐卤顽蓑绥掠叁事讲土闲直优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件3.LINDO/LINGO软件的使用简介软件的使用简介玖罚徽举隅膜吠麦帧墒呈嗽蜒焚屏形酗塔椭箕诀可兢屈抿晤济狰售疯剧闭优化建模与Lindo,
15、Lingo优化软件优化建模与Lindo,Lingo优化软件需要掌握的几个重要方面需要掌握的几个重要方面1、LINDO:正确阅读求解报告(尤其要掌握敏感性分析)正确阅读求解报告(尤其要掌握敏感性分析)2、LINGO:掌握集合掌握集合(SETS)的应用;的应用;正确阅读求解报告;正确阅读求解报告;正确理解求解状态窗口;正确理解求解状态窗口;学会设置基本的求解选项学会设置基本的求解选项(OPTIONS);掌握与外部文件的基本接口方法掌握与外部文件的基本接口方法近钓彪秃福具肤肯儿剔邵韭皂坠砒绎臣谚辱絮俺阶绳短戏否芯佩汝岸兴突优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软
16、件例例1加工奶制品的生产计划加工奶制品的生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶时间时间480小时小时 至多加工至多加工100公斤公斤A1制订生产计划,使每天获利最大制订生产计划,使每天获利最大 35元可买到元可买到1桶牛奶,买吗?若买,每天最多买多少桶牛奶,买吗?若买,每天最多买多少?可聘用临时工人,付出的工资最多是每小时几元可聘用临时工人,付出的工资最多是每小时几元?A1的获利增加到的获利增加到30元元/公斤,应否改变生产计划?公斤,应否改变生产计划?每天:每天:冯绪机市娘厚甲轰庆宴罕亩舱译司迅垛举馒册己缴役爵埔狠芋
17、模回义瘩谐优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2获利获利243x1获利获利164 x2原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A150桶牛奶桶牛奶每天每天啊腾高恨桶笼穴旧耕腐辈净防俭怖撬炉莉枣述慧枣裂复股怒赊俄缮荔灸乔优化建模
18、与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件模型求解模型求解 max72x1+64x2st2)x1+x2503)12x1+8x24804)3x1100endOBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIV
19、ITY)ANALYSIS?No20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2,利润,利润3360元。元。渠培氏奶痪尤悔燕氮绍惺徐字赶诫契跋妒紫沛驭芽五扭擎凸望犬峰甩海敌优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件模型求解模型求解 reduced cost值值表表示示当当该该非非基基变变量量增增加加一一个个单单位位时时(其其他他非非基基变变量量保保持持不不变变)目目标标函函数数减减少少的的量量(对对max型问题型问题) OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.
20、000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2也可理解为:也可理解为:为为了了使使该该非非基基变变量量变变成成基基变变量量,目目标标函函数数中中对对应应系数应增加的量系数应增加的量芬酋曹悠错伤婚眺裳眉威遍为殿呜痴楼楷篮腊诫威栓鲤博墙质挪渺碟忙捎优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件OBJECTIVEFUNCTIONVALUE1)3360.000VARIAB
21、LEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40max72x1+64x2st2)x1+x2503)12x1+8x24804)3x1100end三三种种资资源源“资源资源”剩余为零的约束为紧约束(有效约束)剩余为零的约束为紧约束(有效约束)结果解释结果解释 锡离虑粟碰替认焙巢载步鼎英汗盐卖绽脐藉票杯填柜
22、赔饲专从撂牙运瞪桅优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000结果解释结果解释 最优解下最优解下“资源资源”增增加加1单位时单位时“效益效益”的的增量增量原料增原料增1单位单位,利润增利润增48时间加时间加1单
23、位单位,利润增利润增2能力增减不影响利润能力增减不影响利润影子价格影子价格35元可买到元可买到1桶牛奶,要买吗?桶牛奶,要买吗?35”(或(或“=”(或(或“=”)功能相)功能相同同2.变量与系数间可有空格变量与系数间可有空格(甚至回车甚至回车),但无运算符但无运算符3.变量名以字母开头,不能超过变量名以字母开头,不能超过8个字符个字符4.变量名不区分大小写(包括变量名不区分大小写(包括LINDO中的关键字)中的关键字)5.目标函数所在行是第一行,第二行起为约束条件目标函数所在行是第一行,第二行起为约束条件6.行号行号(行名行名)自动产生或人为定义。行名以自动产生或人为定义。行名以“)”结结束
24、束7.行中注有行中注有“!”符号的后面部分为注释。如符号的后面部分为注释。如:!ItsComment.8.在模型的任何地方都可以用在模型的任何地方都可以用“TITLE”对模型命名对模型命名(最多(最多72个字符),如:个字符),如:TITLEThisModelisonlyanExample蔬夕贤刃薪踌蛆镍槐余短妆式旦两免钟纂像朔议傀愉居马异子贸授客窖逞优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件9.变量不能出现在一个约束条件的右端变量不能出现在一个约束条件的右端10.表达式中不接受括号表达式中不接受括号“()”和逗号和逗号“,”等任何符等任何符号号,例例:4
25、00(X1+X2)需写为需写为400X1+400X211.表达式应化简,如表达式应化简,如2X1+3X2-4X1应写成应写成-2X1+3X212.缺省假定所有变量非负;可在模型的缺省假定所有变量非负;可在模型的“END”语句语句后用后用“FREEname”将变量将变量name的非负假定取消的非负假定取消13.可在可在“END”后用后用“SUB”或或“SLB”设定变量上设定变量上下界下界例如:例如:“subx110”的作用等价于的作用等价于“x1=10”但用但用“SUB”和和“SLB”表示的上下界约束不计入模表示的上下界约束不计入模型的约束,也不能给出其松紧判断和敏感性分析。型的约束,也不能给出
26、其松紧判断和敏感性分析。14.“END”后对后对0-1变量说明:变量说明:INTn或或INTname15.“END”后对整数变量说明:后对整数变量说明:GINn或或GINname使用使用LINDOLINDO的一些注意事项的一些注意事项心靴锗渡棉哑楚贱召熔拎似彪栋麓岳蓑缎涌请适剂桐瘁际沛犹钞怂隘凝旨优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件二次规划规划(QP)问题LINDO可求解二次规划可求解二次规划(QP)问题,但输入方式较问题,但输入方式较复杂,因为在复杂,因为在LINDO中不许出现非线性表达式中不许出现非线性表达式需要为每一个实际约束增加一个对偶变量需
27、要为每一个实际约束增加一个对偶变量(LAGRANGE乘子),在实际约束前增加有关乘子),在实际约束前增加有关变量的一阶最优条件,转化为互补问题变量的一阶最优条件,转化为互补问题“END”后面使用后面使用QCP命令指明实际约束开始的行命令指明实际约束开始的行号,然后才能求解号,然后才能求解建议总是用建议总是用LINGO解解QP注意注意对对QP和和IP:敏感性分析意义不大敏感性分析意义不大拖檀须糙邦铸玖竖饰遥拾炼希猩际秽垄确况已均通莫侠膝盲殆勺参岭州徽优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件状态窗口状态窗口(LINDO Solver Status) 当前状态
28、:已达最优解当前状态:已达最优解迭代次数:迭代次数:18次次约束不满足的约束不满足的“量量”(不不是是“约束个数约束个数”):0当前的目标值:当前的目标值:94最好的整数解:最好的整数解:94整数规划的界:整数规划的界:93.5分枝数:分枝数:1所用时间:所用时间:0.00秒(太快秒(太快了,还不到了,还不到0.005秒)秒)刷新本界面的间隔刷新本界面的间隔:1(秒秒)艇追抠媚纯怔氦翅思芜伴洽拇哨邓驶冻黑潮绿谴忿米运趟淮畸批谬桶尊惯优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件选项设置选项设置Preprocess:预处理:预处理(生成割平面生成割平面);Pre
29、ferredBranch:优先的分枝方式:优先的分枝方式:“Default”(缺省方式)、(缺省方式)、“Up”(向上取整优先)、(向上取整优先)、“Down”(向下取整优先);(向下取整优先);IPOptimalityTol:IP最优值允许的误最优值允许的误差上限(一个百分数,如差上限(一个百分数,如5%即即0.05););IPObjectiveHurdle:IP目标函数的篱目标函数的篱笆值,即只寻找比这个值更优最优解笆值,即只寻找比这个值更优最优解(如当知道当前模型的某个整数可行解(如当知道当前模型的某个整数可行解时,就可以设置这个值);时,就可以设置这个值);IPVarFixingTol
30、:固定一个整数变量:固定一个整数变量取值所依据的一个上限(如果一个整数取值所依据的一个上限(如果一个整数变量的判别数(变量的判别数(REDUCEDCOST)的)的值很大,超过该上限,则以后求解中把值很大,超过该上限,则以后求解中把该整数变量固定下来)。该整数变量固定下来)。NonzeroLimit:非零系数的个数上限;非零系数的个数上限;IterationLimit:最大迭代步数;最大迭代步数;InitialContraintTol:约束的初始误差上限;约束的初始误差上限;FinalContraintTol:约束的最后误差上限;约束的最后误差上限;EnteringVarTol:进基变量的进基变
31、量的REDUCEDCOST的误差限;的误差限;PivotSizeTol:旋转元的误差限旋转元的误差限呕牧颓晴攘叔谅袜瓜珊指乓浚孵忙配杀诺巧悄洛狸祸碘舞盼阿燃妄皱羔赫优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件Report/Statistics第一行:模型有第一行:模型有5行(约束行(约束4行),行),4个变量,两个整数变量(没有个变量,两个整数变量(没有0-1变量),从第变量),从第4行开始是二次规划的实际约束。行开始是二次规划的实际约束。第二行:非零系数第二行:非零系数19个,约束中非零系数个,约束中非零系数12个个(其中其中6个为个为1或或-1),模型密
32、度为模型密度为0.760(密度密度=非零系数非零系数/行数行数(变量数变量数)。第三行的意思:按绝对值看,系数最小、最大分别为第三行的意思:按绝对值看,系数最小、最大分别为0.3和和277。第四行的意思:模型目标为极小化;小于等于、等于、大于等于约第四行的意思:模型目标为极小化;小于等于、等于、大于等于约束分别有、个;广义上界约束(束分别有、个;广义上界约束(GUBS)不超过个;)不超过个;变量上界约束(变量上界约束(VUBS)不少于个。所谓)不少于个。所谓GUBS,是指一组不,是指一组不含有相同变量的约束;所谓含有相同变量的约束;所谓VUBS,是指一个蕴涵变量上界的约,是指一个蕴涵变量上界的
33、约束,如从约束束,如从约束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
34、VALUE= 0.300000 277.000OBJ=MIN, NO. : 2 0 2, GUBS = 0SINGLE COLS= 0 REDUNDANT COLS= 0续彻行稠愿卸验刮蚁典磨誊聘秘民峨埋致阳曳叔氰改蔓屯义旁辫甘酥毕渐优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件LINDOLINDO行命令、命令脚本文件行命令、命令脚本文件批处理:可以采用命令脚本(行命令序列)批处理:可以采用命令脚本(行命令序列)WINDOWS环境下行命令的意义不大环境下行命令的意义不大Example演示演示用用FILE/TAKECOMMANDS(F11)命令调入命令调入必须是
35、以必须是以LINDOPACKED形式形式(压缩)保存的文件(压缩)保存的文件FILE/SAVE命令命令SAVE行命令行命令尝锡恤数弱碴满啦涎选吧滚写蹬方赴恳蚀韧厄序窜霉缓毙窝衫边悟顿魏峡优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件LINGO软件简介软件简介目标与约束段目标与约束段集合段(集合段(SETSENDSETS)数据段(数据段(DATAENDDATA)初始段(初始段(INITENDINIT)计算段计算段(CALCENDCALC)-LINGO9.0LINGO模型的构成:模型的构成:5个段个段LINGO模型的优点模型的优点包含了包含了LINDO的全部功能的
36、全部功能提供了灵活的编程语言(矩阵生成器)提供了灵活的编程语言(矩阵生成器)拐甄夺咙矽激闽匙炎馁疥巍境顷羞粗茬峪筹车庇棚敌低踌聋能嗡绪葵崔丢优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件LINGOLINGO模型模型 例:选址问题例:选址问题某公司有某公司有6个建筑工地,位置坐标为个建筑工地,位置坐标为(ai,bi)(单位:公单位:公里里),水泥日用量水泥日用量di(单位:吨)单位:吨)假设:假设:料场料场和工地之间和工地之间有直线道路有直线道路唆岿淮强君樊节涝振锯赔摩谩伶徽丛碴遮永钻允哆吊蒋萝术元淆究禄勿膘优化建模与Lindo,Lingo优化软件优化建模与Li
37、ndo,Lingo优化软件用例中数据计算,最优解为总吨公里数为总吨公里数为总吨公里数为总吨公里数为136.2136.2线性规划模型线性规划模型决策变量:决策变量:ci j(料场料场j到到工地工地i的运量)的运量)12维维虞苍熟守已烯篷载始贿拥牲做拐愉波缆舷殃幂蜘逼结裂莉忍琶赃蔼沏篇坍优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件选址问题:选址问题:NLPNLP2)改建两个新料场,需要确定新料场位置)改建两个新料场,需要确定新料场位置(xj,yj)和运量和运量cij,在其它条件不变下使总吨公里数最小。,在其它条件不变下使总吨公里数最小。决策变量:决策变量:ci
38、j,(xj,yj)16维维非线性规划模型非线性规划模型骡顺踩误休遂范山腻盯促钮连缅龟瞅眶折案咙村术诗秒赂佛蔗瘪遁矽眨桑优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件LINGO模型的构成:模型的构成:4个段个段集合段(集合段(SETSENDSETS)数据段(数据段(DATAENDDATA)初始段(初始段(INITENDINIT)目标与目标与约束段约束段局部最优:局部最优:89.8835(吨公里吨公里 )LP:移到数据段:移到数据段廓景缎雏咀挣勘玄徊疽辉试闸革联汹兄甭妄崭洗遥乒陌儒诊镁硫另府还墓优化建模与Lindo,Lingo优化软件优化建模与Lindo,Ling
39、o优化软件边界骑兰虎己徊阅哲靠赦积榷蔗药侣眯暴齿斤顺纳睁畦线杂菏桓瓦览藻脸迄翔优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件集合的类型集合的类型集合集合派生集合派生集合基本集合基本集合稀疏集合稀疏集合稠密集合稠密集合元素列表法元素列表法元素过滤法元素过滤法直接列举法直接列举法隐式列举法隐式列举法setname /member_list/ : attribute_list;setname(parent_set_list) /member_list/ : attribute_list;SETS: CITIES /A1,A2,A3,B1,B2/; ROADS(CIT
40、IES, CITIES)/ A1,B1 A1,B2 A2,B1 A3,B2/:D; ENDSETSSETS: STUDENTS /S1.S8/; PAIRS( STUDENTS, STUDENTS) | &2 #GT# &1: BENEFIT, MATCH;ENDSETS绣宙隘摹眉祈棍荫搏恕拱踩兹疮颅茨舅扒排馒皇麓产隔惨育职逸收椭绷怕优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件集合元素的集合元素的隐式列举隐式列举类型型隐式列式列举格式格式示例示例示例集合的元素示例集合的元素数字型数字型 1.n1.51,2,3,4,5字符字符-数字型数字型stringM.st
41、ringNCar101.car208 Car101,car102,car208星期型星期型 dayM.dayNMON.FRIMON,TUE,WED,THU,FRI月份型月份型 monthM.monthN OCT.JANOCT,NOV,DEC,JAN年份年份-月份型月份型monthYearM.monthYearNOCT2001.JAN2002OCT2001,NOV2001,DEC2001,JAN2002芝岂器姓四鼓趟邢汲笛欢杜悍男坯串挡灾俄饿撂滞冒省藏叭疟擎硬瓤烤辫优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件运算符的优先级运算符的优先级 优先先级运算符运算符最
42、高最高#NOT# (负负号)号)* /+ (减法)(减法)#EQ# #NE# #GT# #GE# #LT# #LE# #AND# #OR#最低最低(=)三类运算符:三类运算符:算术运算符算术运算符逻辑运算符逻辑运算符关系运算符关系运算符邯褂哦较岸筹横萤茄六遭赛潜他葛莫脸概宅蔑貉拷宠么佳汪莹抑霉樟颇罕优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件集合循环函数集合循环函数四个集合循环函数:四个集合循环函数:FOR、SUM、MAX、MINfunction( setname ( set_index_list) | condition : expression_list
43、);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:听咖孪邓辟伺季语掏抒篡嘎捷葬翻惑沟谦厩挽炯一
44、刻罕开扫讨博违皖翘乎优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件状态窗口状态窗口Solver Type:B-and-BGlobal MultistartModel Class: LP, QP,ILP, IQP,PILP, PIQP,NLP,INLP,PINLP State:Global OptimumLocal OptimumFeasibleInfeasibleUnboundedInterruptedUndetermined俄唤加伤佛扁拾圆拂偿戈饺庚整尉摇挫三沮逛叙蝉儒随迅拜焰琶买尘冗梭优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo
45、优化软件7 7个选项卡个选项卡( (可设置可设置80-9080-90个控制参数个控制参数) )烦岭蕴洁疏剃笋兢阜带弓莱敲妄婶扎荧彬纳渍反讲篓朱蜂诫观触胃赣塘辫优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件 程序与数据分离程序与数据分离文文本本文文件件使用外部数据文件使用外部数据文件Cut(orCopy)Paste方法方法FILE输入数据、输入数据、TEXT输出数据(文本文件)输出数据(文本文件)OLE函数与电子表格软件(如函数与电子表格软件(如EXCEL)连接)连接ODBC函数与数据库连接函数与数据库连接LINGO命令脚本文件命令脚本文件LG4(LONGO模型
46、文件)模型文件)LNG(LONGO模型文件)模型文件)LTF(LONGO脚本文件)脚本文件)LDT(LONGO数据文件)数据文件)LRP(LONGO报告文件)报告文件)常用文件后缀常用文件后缀诣幼盐烹貉亭隙拖砾哮弄毯坐掣杆荫蹲解访咒氛配莹河你撮偏歌槽丘炕旗优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件FILEFILE和和TEXTTEXT:文本文件输入输出:文本文件输入输出MODEL:SETS: MYSET / FILE(myfile.txt) / : FILE(myfile.txt);ENDSETSMIN = SUM( MYSET( I): SHIP( I)
47、* 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,SUPPLY =OLE(mydata.xls); OLE(mydata.xls,SOLUTION)=SHIP; ENDDATAEND mydata.xls文件中必须有下列名称(及数据): CITIES, COST,NEED,SUPPLY,SOLUTION在在EXCEL中还可
48、以通过中还可以通过“宏宏”自动调用自动调用LINGO(略略)也可以将也可以将EXCEL表格嵌入到表格嵌入到LINGO模型中模型中(略略)演示演示MydataExample.lg4墒享啄糯会镰医卖队诡旅皖棚则捍吠脱鸽滦嗅挤仆秃郝挨搀噪交他函冕吱优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件ODBC ODBC :与数据库连接:与数据库连接输入基本集合元素:输入基本集合元素:setname/ODBC(datasource,tablename,columnname)/输入派生集合元素:输入派生集合元素:setname/ODBC(source,table,column1
49、,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具体例子略具体例子略命览尺擂陶姆瞎澈普业稻迄儿承惯粉晃族吟
50、豪惹睹猾蒙印区墟毡撂懂泅昆优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件4.建模与求解实例(结合软件使用)建模与求解实例(结合软件使用)眨沽贤蹬剔潮哺冯斩粹驱妒予浆疽哨语每隙发兔催婚仪燎协衫做鸯拢怠俺优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件建模实例与求解建模实例与求解最短路问题最短路问题下料问题下料问题飞机定位飞机定位露天矿的运输问题露天矿的运输问题钢管运输问题钢管运输问题电力市场的堵塞管理电力市场的堵塞管理侠愁短辜宫围溯总氓逛尔聪弹狰戊盅速苟封碍幂让泼逢性史半稠缸塔沤派优化建模与Lindo,Lingo优化软件优化建模与
51、Lindo,Lingo优化软件例例最短路问题最短路问题求各点到求各点到T的最短路的最短路56774968658336C1B1C2B2A1A2A3TS6shortestPath.lg4斗咯胯渺豹挂剧臻篆吹躲悯氖百祝潜窗房专咖拆各浦镣渗捌肪凰臀曲昔小优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件问题问题1.如何下料最节省如何下料最节省?例例 钢管下料钢管下料 问题问题2.客户增加需求:客户增加需求:原料钢管原料钢管: :每根每根19米米 4米米50根根 6米米20根根 8米米15根根 客户需求客户需求节省的标准是什么?节省的标准是什么?由于采用不同切割模式太多,会
52、增加生产和管理成本,由于采用不同切割模式太多,会增加生产和管理成本,规定切割模式不能超过规定切割模式不能超过3种。如何下料最节省?种。如何下料最节省?5米米10根根 遭剧膜赏拙浑曝蹭屑黍滩侩厅鲍菠色皿枢姆头沼躁默狠够稍磋隋甲币紫砾优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件按照客户需要在一根原料钢管上安排切割的一种组合。按照客户需要在一根原料钢管上安排切割的一种组合。切割模式切割模式余料余料1 1米米 4米米1根根 6米米1根根 8米米1根根余料余料3米米4米米1根根6米米1根根6米米1根根合理切割模式合理切割模式的余料应小于客户需要钢管的最小尺寸的余料应小
53、于客户需要钢管的最小尺寸余料余料3米米8米米1根根8米米1根根钢管下料钢管下料 税坚耘分魄毡毁毁糖谊开板幅菌复骨蝶忱凶婉敞邹醒龄皇凶绍曝蹲狞胺韭优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件为满足客户需要,按照哪些种合理模式,每种模式为满足客户需要,按照哪些种合理模式,每种模式切割多少根原料钢管,最为节省?切割多少根原料钢管,最为节省?合理切割模式合理切割模式2.所用原料钢管总根数最少所用原料钢管总根数最少模式模式4米钢管根数米钢管根数6米钢管根数米钢管根数8米钢管根数米钢管根数余料余料(米米)140032310132013412035111160301700
54、23钢管下料问题钢管下料问题1 1 两种两种标准标准1.原料钢管剩余总余量最小原料钢管剩余总余量最小兑笨您檄刷司淳赞幂书窟蜗佬斗茶疡誊偶卢咐梳咱址民蜀履秦窒握轧嫌谗优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件xi 按第按第i 种模式切割的原料钢管根数种模式切割的原料钢管根数( (i= =1,2,7) ) 约束约束满足需求满足需求 决策变量决策变量 目标目标1(总余量)(总余量)按模式按模式2切割切割12根根, ,按模式按模式5切割切割15根,余料根,余料27米米模模式式4米米根数根数6米米根数根数8米米根数根数余余料料14003231013201341203
55、511116030170023需需求求502015最优解:最优解:x2=12,x5=15,其余为其余为0;最优值:最优值:27整数约束:整数约束:xi 为整数为整数奉峭羡访量淬萎虐翱堑凰滑剩坯傅偏升镰伞播湿指霉哇扮痔诛涉磐戌澈洞优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件当余料没有用处时,当余料没有用处时,通常以总根数最少为目标通常以总根数最少为目标 目标目标2(总根数)(总根数)钢管下料问题钢管下料问题1 1 约束条约束条件不变件不变 最优解:最优解:x2=15,x5=5,x7=5,其余为其余为0;最优值:最优值:25。xi 为整数按模式按模式2切割切割1
56、5根,根,按模式按模式5切割切割5根,根,按模式按模式7切割切割5根,根,共共25根,余料根,余料35米米虽余料增加虽余料增加8米,但减少了米,但减少了2根根与与目标目标1的结果的结果“共切割共切割27根,余料根,余料27米米”相比相比巍查糖蘑褂挪膜汕祸运供惦锯前缚制甄挛符再果干皇剐雅卤俱粥一馈新绪优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件钢管下料问题钢管下料问题2 2对大规模问题,用模型的约束条件界定合理模式对大规模问题,用模型的约束条件界定合理模式增加一种需求:增加一种需求:5米米10根;切割根;切割模式不超过模式不超过3种。种。现有现有4种种需求:需
57、求:4米米50根,根,5米米10根,根,6米米20根,根,8米米15根,用枚举法确定合理切割模式,过于复杂。根,用枚举法确定合理切割模式,过于复杂。决策变量决策变量 xi 按第按第i 种模式切割的原料钢管根数种模式切割的原料钢管根数( (i= =1,2,3) ) r1i, r2i, r3i, r4i 第第i 种切割模式下,每根原料钢种切割模式下,每根原料钢管生产管生产4米、米、5米、米、6米和米和8米长的钢管的数量米长的钢管的数量钱硅瓢估凹富愉啮篓巾谊倍想甚捧象都耶肺锗董锭绵协闲佩剥搽矗骤趴溪优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件满足需求满足需求模式合
58、理:每根模式合理:每根余料不超过余料不超过3米米整数非线性规划模型整数非线性规划模型钢管下料问题钢管下料问题2 2目标函数(目标函数(总根数)总根数)约束约束条件条件整数约束:整数约束:xi ,r1i, r2i, r3i, r4i ( (i= =1,2,3) )为整数为整数牧地衣听缔舒赛瞳滋搐睛爷功北牟碉涧飘诺簧现敲娇樊获违歌退命倦加满优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件增加约束,缩小可行域,便于求解增加约束,缩小可行域,便于求解原料钢管总根数下界:原料钢管总根数下界:特殊生产计划:对每根原料钢管特殊生产计划:对每根原料钢管模式模式1:切割成:切割成
59、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米米念吭镭脐羔闺滦仰郁愚廓茸极收椅垂齿研哲外积岩柠坐妒陨深湃疙辜寓藻优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件LINGOLINGO求解整数非线性规划模型求
60、解整数非线性规划模型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.0
61、00000R330.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躯祟士追冻旧邯猜碘狼七群瓷滑
62、朗虾勃照喊筋逻皇芦但悟抖妊恩饺痰瘪雁优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件0yxVOR2x=629, y=375309.00 (1.30)864.3(2.0)飞机x=?, y=?VOR1x=764, y=1393161.20 (0.80)VOR3x=1571, y=25945.10 (0.60)北DMEx=155, y=987飞机与监控台(图中坐标和测量距离的单位是“公里”)实例实例: 飞机精确定位问题飞机精确定位问题 疤欢悟奏暴执友惮峪他绦终乙摸伟渔仅深罗烧廓痴捐忱柿荡鸡醚逆痉傀烛优化建模与Lindo,Lingo优化软件优化建模与Lindo,Ling
63、o优化软件飞机精确定位模型飞机精确定位模型xiyi原始的 (或d4)VOR1 7461393161.20(2.81347弧度)0.80(0.0140弧度)VOR2 62937545.10 (0.78714弧度)0.60(0.0105弧度)VOR3 1571259309.00(5.39307弧度)1.30(0.0227弧度)DME155987d4=864.3(km)2.0(km)傅尹铱煞画瀑榔珐庐饺编兰垃煎黄肚抖警营驴琐圆捏传苹细室岩凶奇镑瞩优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件飞机精确定位模型飞机精确定位模型第第1类模型类模型:不考虑误差因素不考虑误差
64、因素超定方程组,超定方程组,非线性最小二乘!非线性最小二乘!量纲不符!量纲不符!?悍蔷俗吧室贬广韦糊底急硫酌铺子案妆耘爆恨葵城央扫峻工任法箱技霸漏优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件飞机精确定位模型飞机精确定位模型第第2类模型类模型:考虑误差因素考虑误差因素(作为硬约束作为硬约束)Min x; Min y; Max x; Max y.以距离为约束,优化角度误差之和(或平方和);以距离为约束,优化角度误差之和(或平方和);或以角度为约束,优化距离误差或以角度为约束,优化距离误差.非线性规划非线性规划?仅部分考虑误差仅部分考虑误差!角度与距离的角度与距离
65、的“地位地位”不应不同!不应不同!有人也可能会采用其他目标,如:有人也可能会采用其他目标,如:误差非均匀分布!误差非均匀分布!之卤保妨盛同味嫌俺服撒污匡娇棋缄症嘎六骋呈擒袖沃息皖旺互匡铣蓑销优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件飞机精确定位模型飞机精确定位模型误差一般服从什么分布?误差一般服从什么分布?正态分布!正态分布!不同的量纲如何处理?不同的量纲如何处理?无约束非线性最小二乘模型无约束非线性最小二乘模型归一化处理!归一化处理!shili0702.m飞机坐标飞机坐标(978.31,723.98),误差平方和误差平方和0.6685(4)角度需要进行预
66、处理,如利用角度需要进行预处理,如利用Matlab的的atan2函数函数,值域值域(-pi,pi)第第3类模型类模型:考虑误差因素考虑误差因素(作为软约束作为软约束);且归一化且归一化铁剁吧揣崔园浆羞碴庞滋炳桶重扼讯绍择泞泼赃台爆坦艾钓焦值员梆卵苑优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件飞机精确定位模型飞机精确定位模型小技巧小技巧:LINGO中没有中没有atan2函数函数,怎么办?怎么办?可以直接利用可以直接利用tan函数!函数!exam0507c.lg4同前面的模型同前面的模型/结果结果飞机坐标飞机坐标(980.21,727.30),误差平方和误差平方
67、和2.6与前面的结果有所不同与前面的结果有所不同,为什么为什么?哪个模型合理些哪个模型合理些?最后最后:思考以下模型思考以下模型:exam0507d.lg4嗅你伏处赴煽销遮龄扦硒优殊彰奏耘屯好洽播爪吮绍龙骨挎阵皿檄毕辩残优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件露天矿里铲位已分成矿石和岩石露天矿里铲位已分成矿石和岩石:平均铁含量不低于平均铁含量不低于25%的为矿石,否则为岩石。每个铲位的矿石、岩石数的为矿石,否则为岩石。每个铲位的矿石、岩石数量,以及矿石的平均铁含量(称为品位)都是已知的。量,以及矿石的平均铁含量(称为品位)都是已知的。每个铲位至多安置一台
68、电铲,电铲平均装车时间每个铲位至多安置一台电铲,电铲平均装车时间5分钟分钟卡车在等待时所耗费的能量也是相当可观的,原则上在卡车在等待时所耗费的能量也是相当可观的,原则上在安排时安排时不应发生卡车等待不应发生卡车等待的情况。的情况。露天矿生产的车辆安排露天矿生产的车辆安排(CUMCM-2003B) 矿石卸点需要的铁含量要求都为矿石卸点需要的铁含量要求都为29.5% 1%(品位限制)品位限制),搭配量在一个班次(,搭配量在一个班次(8小时)内满足品位限制即可。小时)内满足品位限制即可。卸点在一个班次内不变。卡车载重量为卸点在一个班次内不变。卡车载重量为154吨,平均时吨,平均时速速28km,平均卸
69、车时间为平均卸车时间为3分钟。分钟。问题:出动几台电铲,分别在哪些铲位上;出动几辆问题:出动几台电铲,分别在哪些铲位上;出动几辆卡车,分别在哪些路线上各运输多少次卡车,分别在哪些路线上各运输多少次?沈业豫讥拽妄讫况驼脱姜沪局芍犀仅租常弗商困舷径阀灌搭纽掠庆依梨吼优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件平面示意图爵志豢擂灰卿挡失罗煞彻性澎狡维毋撰芭侗嫡区杉档备歇索徊蜘城挝座影优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件问题数据问题数据 距离铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏5.265.1
70、94.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铁
71、含量30%28%29%32%31%33%32%31%33%31%惋邦月酸栈春检爽恐将靶绝河寥方策轩我姑遏浊痈粘归村逐蜡逊搂泼院蜜优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件问题分析问题分析 与典型的运输问题明显有以下不同:与典型的运输问题明显有以下不同:1.这是运输矿石与岩石两种物资的问题;这是运输矿石与岩石两种物资的问题;2.属于产量大于销量的不平衡运输问题;属于产量大于销量的不平衡运输问题;3.为了完成品位约束,矿石要搭配运输;为了完成品位约束,矿石要搭配运输;4.产地、销地均有单位时间的流量限制;产地、销地均有单位时间的流量限制;5.运输车辆只有一种,
72、每次满载运输,运输车辆只有一种,每次满载运输,154吨吨/车次;车次;6.铲位数多于铲车数意味着要最优的选择不多于铲位数多于铲车数意味着要最优的选择不多于7个个产地作为最后结果中的产地;产地作为最后结果中的产地;7.最后求出各条路线上的派出车辆数及安排。最后求出各条路线上的派出车辆数及安排。近似处理:近似处理:先求出产位、卸点每条线路上的运输量先求出产位、卸点每条线路上的运输量(MIP模型模型)然后求出各条路线上的派出车辆数及安排然后求出各条路线上的派出车辆数及安排误亭豆约抹僧妊谰惟寝琉领钓肩肋瀑蓖墓摸灿放来骑抡八挑婪跳柳庸职羽优化建模与Lindo,Lingo优化软件优化建模与Lindo,Li
73、ngo优化软件模型假设模型假设卡车在一个班次中不应发生等待或熄火后再启动卡车在一个班次中不应发生等待或熄火后再启动的情况;的情况;在铲位或卸点处由两条路线以上造成的冲突问题在铲位或卸点处由两条路线以上造成的冲突问题面前,我们认为只要平均时间能完成任务,就认面前,我们认为只要平均时间能完成任务,就认为不冲突。我们不排时地进行讨论;为不冲突。我们不排时地进行讨论;空载与重载的速度都是空载与重载的速度都是28km/h,耗油相差很大;,耗油相差很大;卡车可提前退出系统,等等。卡车可提前退出系统,等等。如理解为严格不等待,难以用数学规划模型来解如理解为严格不等待,难以用数学规划模型来解个别参数队找到了可
74、行解个别参数队找到了可行解(略)(略)膜串篆殃哎楼炼航羚往轴缝呜姓稠牵闹萄涂岂渗衣芜玫素谐砾宇鸭壳己舜优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件符号符号xij:从:从i铲位到铲位到j号卸点的石料运量号卸点的石料运量(车)(车)单位:单位:吨;吨;cij:从:从i号铲位到号铲位到j号卸点的距离号卸点的距离公里;公里;Tij:从从i号铲位到号号铲位到号j卸点路线上运行一个周期平均时间卸点路线上运行一个周期平均时间分;分;Aij:从号铲位到号卸点最多能同时运行的卡车数:从号铲位到号卸点最多能同时运行的卡车数辆;辆;Bij:从号铲位到号卸点路线上一辆车最多可运行的
75、次数:从号铲位到号卸点路线上一辆车最多可运行的次数次;次;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为关闭。为关闭。(近似近似)滤膨沛片肤迹叙豹迟有酌戎梭松寨琶惯泳篡所扳耙锐剥夯煎坎抚腰忿箔筏优化建模与Lindo,Lingo优化软
76、件优化建模与Lindo,Lingo优化软件优化模型(1)道路能力道路能力(卡车数卡车数)约束约束(2)电铲能力约束(3)卸点能力约束(4)铲位储量约束(5)产量任务约束(6)铁含量约束(7)电铲数量约束(8)整数约束 .xij为非负整数fi 为0-1整数晋席皱姿曾眉卡诊亦忿秧爪另庐沥郁狞粪柴毖硷兴眺髓绷夏忠酚奏汰猴斌优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件计算结果(计算结果(LINGOLINGO软件)软件)铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿漏131354541111倒42424343岩场70701515岩漏81814343倒
77、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.489cumcm2003b1.lg4注注:LINGO8.0本来是可以得到最优解的,但有些本来是可以得到最优解的,但有些LINGO8.0可能出现系统错误可能出现系统错误,可能是系统可能是系统BUG辟吻院微蛇健耙疽淬椽盒政陷寺鄂和续廓祷溢氰图恫潘奖霸跳仍书晒乔义优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件计算结果(派车)计算结果(派车)铲位1铲位2
78、铲位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辆联合派车(方案略)辆联合派车(方案略)荔阀垂匡颐南屋沿捶褒愉误捡撩守侗印咏资建媳寺垃希栅读眶厌淳喂癣饭优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软
79、件最大化产量最大化产量结论:结论:(略)(略)目标函数变化目标函数变化此外:车辆数量(此外:车辆数量(20辆)限制(其实上面的模型也辆)限制(其实上面的模型也应该有)应该有)防辱我容喻蜂捌鲁城累令息冻粪台洪灼订模蝗列镣谁输艺度钦忻曝窃进枕优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件建模实例与求解建模实例与求解交通流的均衡问题(另附)交通流的均衡问题(另附)钢管运输问题(另附)钢管运输问题(另附)电力市场的堵塞管理(另附)电力市场的堵塞管理(另附)芽药迭窗珐椎市赋绎舍连坤姑喻帕箍巫稽挣儒澳铰靡虞诛躇陛笺燥议膊瑞优化建模与Lindo,Lingo优化软件优化建模与
80、Lindo,Lingo优化软件CUMCM其他优化赛题其他优化赛题飞行管理问题飞行管理问题空洞探测问题空洞探测问题钻井布局问题钻井布局问题抢渡长江问题抢渡长江问题等等等等是藤鼓甩叠辐烤激盘携责飞入坯铃诚栖谢捆梦耀回爵锥赫棒搓灶辜兹谚汕优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件主要参考文献主要参考文献谢金星谢金星,薛毅薛毅:优化建模与优化建模与LINDO/LINGO软件软件,清华大学出版社清华大学出版社,2005年年7月出版月出版.http:/ all. Any Questions? Thank you for your attendance! 最后,祝大家在数学建模活动中取得更大的成绩!清华大学数学科学系 谢金星, 2005. 懊泞百辰佐熊滋该痊淀梧空憎煽惧吾臻嘻聘立缨班布蓝茬旨鼓防坐川甄展优化建模与Lindo,Lingo优化软件优化建模与Lindo,Lingo优化软件