数学建模讲座优化模型与LINDOLINGO优化软件市公开课获奖课件省名师优质课赛课一等奖课件.ppt

本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考!,数学建模讲座,优化模型与,LINDO/LINGO,优化软件,谢金星,清华大学数学科学系,Tel:[phone],Email:jxie,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 Programming Interface(V2.0),Whats Best!:(SpreadSheet e.g.EXCEL)(V7.0),演,示,(,试用,),版、学生版、高级版、超级版、工业版、扩展版,（求解,问题规模,和,选件,不一样）,4/65,LINDO,和,LINGO,软件能求解优化模型,LINGO,LINDO,优化模型,线性规划,(LP),非线性规划,(NLP),二次规划,(QP),连续优化,整数规划,(IP),5/65,LP QP NLP IP,全局优化,(,选,),ILP IQP INLP,LINDO/LINGO,软件求解过程,LINDO/LINGO,预处理程序,线性优化求解程序,非线性优化求解程序,分枝定界管理程序,1.,确定常数,2.,识别类型,1.,单纯形算法,2.,内点算法,(,选,),1,、次序线性规划法,(SLP),2,、广义既约梯度法,(GRG),(,选,),3,、多点搜索,(Multistart),(,选,),6/65,建模时需要注意几个基本问题,1,、,尽可能使用实数优化，降低整数约束和整数变量,2,、,尽可能使用光滑优化，降低非光滑约束个数,如：尽可能少使用绝对值、符号函数、多个变量求最大,/,最小值、四舍五入、取整函数等,3,、,尽可能使用线性模型，降低非线性约束和非线性变量个数 （如,x/y,5,改为,x,5,y,）,4,、,合理设定变量上下界，尽可能给出变量初始值,5,、,模型中使用参数数量级要适当,(,如小于,10,3,),7/65,需要掌握几个主要方面,1,、,LINDO:,正确阅读求解汇报（尤其要掌握敏感性分析）,2,、,LINGO,：,掌握集合,(SETS),应用；,正确阅读求解汇报；,正确了解求解状态窗口；,学会设置基本求解选项,(OPTIONS),；,掌握与外部文件基本接口方法,8/65,例,1,加工奶制品生产计划,1,桶牛奶,3,千克,A,1,12,小时,8,小时,4,千克,A,2,或,赢利,24,元,/,千克,赢利,16,元,/,千克,50,桶牛奶,时间,480,小时,至多加工,100,千克,A,1,制订生产计划，使天天赢利最大,35,元可买到,1,桶牛奶，买吗？若买，天天最多买多少,?,可聘用暂时工人，付出工资最多是每小时几元,?,A,1,赢利增加到,30,元,/,千克，应否改变生产计划？,天天：,9/65,1,桶牛奶,3,千克,A,1,12,小时,8,小时,4,千克,A,2,或,赢利,24,元,/,千克,赢利,16,元,/,千克,x,1,桶牛奶生产,A,1,x,2,桶牛奶生产,A,2,赢利,243,x,1,赢利,164,x,2,原料供给,劳动时间,加工能力,决议变量,目标函数,天天赢利,约束条件,非负约束,线性规划模型,(LP),时间,480,小时,至多加工,100,千克,A,1,50,桶牛奶,天天,10/65,模型求解,max 72x1+64x2,st,2,）,x1+x250,3,）,12x1+8x2480,4,）,3x1100,end,OBJECTIVE FUNCTION VALUE,1)3360.000,VARIABLE VALUE,REDUCED COST,X1 20.000000,0.000000,X2 30.000000,0.000000,ROW SLACK OR SURPLUS DUAL PRICES,2)0.000000 48.000000,3)0.000000 2.000000,4)40.000000 0.000000,NO.ITERATIONS=2,DO RANGE(SENSITIVITY)ANALYSIS?,No,20,桶牛奶生产,A,1,30,桶生产,A,2,，利润,3360,元。,11/65,模型求解,reduced cost,值表示当该非基变量增加一个单位时（其它非基变量保持不变）目标函数降低量,(,对,max,型问题,),OBJECTIVE FUNCTION VALUE,1)3360.000,VARIABLE VALUE,REDUCED COST,X1 20.000000,0.000000,X2 30.000000,0.000000,ROW SLACK OR SURPLUS DUAL PRICES,2)0.000000 48.000000,3)0.000000 2.000000,4)40.000000 0.000000,NO.ITERATIONS=2,也可了解为：,为了使该非基变量变成基变量，目标函数中对应系数应增加量,12/65,OBJECTIVE FUNCTION VALUE,1)3360.000,VARIABLE VALUE REDUCED COST,X1 20.000000 0.000000,X2 30.000000 0.000000,ROW,SLACK OR SURPLUS,DUAL PRICES,2)0.000000,48.000000,3)0.000000,2.000000,4)40.000000,0.000000,原料无剩下,时间无剩下,加工能力剩下,40,max 72x1+64x2,st,2,）,x1+x250,3,）,12x1+8x2480,4,）,3x1100,end,三种资源,“,资源”剩下为零约束为紧约束（有效约束）,结果解释,13/65,OBJECTIVE FUNCTION VALUE,1)3360.000,VARIABLE VALUE REDUCED COST,X1 20.000000 0.000000,X2 30.000000 0.000000,ROW SLACK OR SURPLUS,DUAL PRICES,2),0.000000,48.000000,3),0.000000,2.000000,4),40.000000,0.000000,结果解释,最优解下“资源”增加,1,单位时“效益”增量,原料增,1,单位,利润增,48,时间加,1,单位,利润增,2,能力增减不影响利润,影子价格,35,元可买到,1,桶牛奶，要买吗？,35”,（或“,=”,（或“,=”,）功效相同,变量与系数间可有空格,(,甚至回车,),但无运算符,变量名以字母开头，不能超出,8,个字符,变量名不区分大小写（包含,LINDO,中关键字）,目标函数所在行是第一行，第二行起为约束条件,行号,(,行名,),自动产生或人为定义。行名以“）”结束,行中注有“,!”,符号后面部分为注释。如,:,!Its Comment.,在模型任何地方都能够用“,TITLE”,对模型命名（最多,72,个字符），如：,TITLE This Model is only an Example,17/65,变量不能出现在一个约束条件右端,表示式中不接收括号“,()”,和逗号“,”,等任何符号,例,:,400(X1+X2),需写为,400X1+400X2,表示式应化简，如,2X1+3X2-4X1,应写成,-2X1+3X2,缺省假定全部变量非负；可在模型“,END”,语句后用“,FREE name,”,将变量,name,非负假定取消,可在“,END”,后用“,SUB”,或“,SLB”,设定变量上下界,比如：“,sub x1 10,”,作用等价于“,x1 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;,ENDDATA,END,mydata.xls,文件中必须有以下名称,(,及数据,),：,CITIES,，,COST,，,NEED,，,SUPPLY,，,SOLUTION,在,EXCEL,中还能够经过“宏”自动调用,LINGO(,略,),也能够将,EXCEL,表格嵌入到,LINGO,模型中,(,略,),演示,MydataExample.lg4,38/65,ODBC,：与数据库连接,输入基本集合元素：,setname/ODBC(datasource,tablename,columnname)/,输入派生集合元素：,setname/ODBC(source,table,column1,column2)/,当前支持以下,DBMS:(,如为其它数据库，则需自行安装驱动,),ACCESS,，,DBASE,，,EXCEL,，,FOXPRO,，,ORACLE,，,PARADOX,，,SQL SERVER,，,TEXE FILES,使用数据库之前，数据源需要在,ODBC,管理器注册,输入数据：,Attr_list=ODBC(source,table,column1,column2),输出数据：,ODBC(source,table,column1,column2)=Attr_list,详细例子略,39/65,建模实例与求解,最短路问题,下料问题,露天矿运输问题,钢管运输问题,40/65,最短路问题,求各点到,T,最短路,5,6,7,7,4,9,6,8,6,5,8,3,3,6,C,1,B,1,C,2,B,2,A,1,A,2,A,3,T,S,6,shortestPath.lg4,41/65,问题,1.,怎样下料最节约,?,例 钢管下料,问题,2.,客户增加需求：,原料钢管,:,每根,19,米,4,米,50,根,6,米,20,根,8,米,15,根,客户需求,节约标准是什么？,因为采取不一样切割模式太多，会增加生产和管理成本，要求切割模式不能超出,3,种。怎样下料最节约？,5,米,10,根,42/65,按照客户需要在一根原料钢管上安排切割一个组合。,切割模式,余料,1,米,4,米,1,根,6,米,1,根,8,米,1,根,余料,3,米,4,米,1,根,6,米,1,根,6,米,1,根,合理切割模式,余料应小于客户需要钢管最小尺寸,余料,3,米,8,米,1,根,8,米,1,根,钢管下料,43/65,为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节约？,合理切割模式,2.,所用原料钢管总根数最少,模式,4,米钢管根数,6,米钢管根数,8,米钢管根数,余料,(,米,),1,4,0,0,3,2,3,1,0,1,3,2,0,1,3,4,1,2,0,3,5,1,1,1,1,6,0,3,0,1,7,0,0,2,3,钢管下料问题,1,两种标准,1.,原料钢管剩下总余量最小,44/65,x,i,按第,i,种模式切割原料钢管根数,(,i,=,1,2,7,),约束,满足需求,决议变量,目标,1,（总余量）,按模式,2,切割,12,根,按模式,5,切割,15,根，余料,27,米,模,式,4,米,根数,6,米,根数,8,米,根数,余,料,1,4,0,0,3,2,3,1,0,1,3,2,0,1,3,4,1,2,0,3,5,1,1,1,1,6,0,3,0,1,7,0,0,2,3,需,求,50,20,15,最优解：,x,2,=12,x,5,=15,其余为,0,；,最优值：,27,整数约束：,x,i,为整数,45/65,当余料没有用处时，,通常以总根数最少为目标,目标,2,（总根数）,钢管下料问题,1,约束条件不变,最优解：,x,2,=15,x,5,=5,x,7,=5,其余为,0,；,最优值：,25,。,x,i,为整数,按模式,2,切割,15,根，按模式,5,切割,5,根，按模式,7,切割,5,根，共,25,根，余料,35,米,虽余料增加,8,米，但降低了,2,根,与,目标,1,结果“共切割,27,根，余料,27,米”相比,46/65,钢管下料问题,2,对大规模问题，用模型约束条件界定合理模式,增加一个需求：,5,米,10,根；切割,模式不超出,3,种。,现有,4,种,需求：,4,米,50,根，,5,米,10,根，,6,米,20,根，,8,米,15,根，用枚举法确定合理切割模式，过于复杂。,决议变量,x,i,按第,i,种模式切割原料钢管根数,(,i,=,1,2,3,),r,1,i,r,2,i,r,3,i,r,4,i,第,i,种切割模式下，每根原料钢管生产,4,米、,5,米、,6,米和,8,米长钢管数量,47/65,满足需求,模式合理：每根余料不超出,3,米,整数非线性规划模型,钢管下料问题,2,目标函数（,总根数）,约束条件,整数约束：,x,i,r,1,i,r,2,i,r,3,i,r,4,i,(,i,=,1,2,3,),为整数,48/65,增加约束，缩小可行域，便于求解,原料钢管总根数下界：,特殊生产计划：对每根原料钢管,模式,1,：切割成,4,根,4,米钢管，需,13,根；,模式,2,：切割成,1,根,5,米和,2,根,6,米钢管，需,10,根；,模式,3,：切割成,2,根,8,米钢管，需,8,根。,原料钢管总根数上界：,31,模式排列次序可任定,钢管下料问题,2,需求：,4,米,50,根，,5,米,10,根，,6,米,20,根，,8,米,15,根,每根原料钢管长,19,米,49/65,LINGO,求解整数非线性规划模型,Local optimal solution found at iteration:12211,Objective value:28.00000,Variable Value Reduced Cost,X1,10.00000,0.000000,X2,10.00000,2.000000,X3 8.000000 1.000000,R11,3.000000,0.000000,R12,2.000000,0.000000,R13 0.000000 0.000000,R21,0.000000,0.000000,R22,1.000000,0.000000 R23 0.000000 0.000000 R31,1.000000,0.000000 R32,1.000000,0.000000 R33 0.000000 0.000000 R41,0.000000,0.000000 R42,0.000000,0.000000 R43 2.000000 0.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/65,露天矿里铲位已分成矿石和岩石,:,平均铁含量不低于,25%,为矿石，不然为岩石。每个铲位矿石、岩石数量，以及矿石平均铁含量（称为品位）都是已知。每个铲位至多安置一台电铲，电铲平均装车时间,5,分钟,卡车在等候时所花费能量也是相当可观，标准上在安排时,不应发生卡车等候,情况。,露天矿生产车辆安排,(CUMCM-B),矿石卸点需要铁含量要求都为,29.5%,1%(,品位限制），搭配量在一个班次（,8,小时）内满足品位限制即可。卸点在一个班次内不变。卡车载重量为,154,吨，平均时速,28km,平均卸车时间为,3,分钟。,问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次,?,51/65,平面示意图,52/65,问题数据,距离,铲位,1,铲位,2,铲位,3,铲位,4,铲位,5,铲位,6,铲位,7,铲位,8,铲位,9,铲位,10,矿石漏,5.26,5.19,4.21,4.00,2.95,2.74,2.46,1.90,0.64,1.27,倒装,1.90,0.99,1.90,1.13,1.27,2.25,1.48,2.04,3.09,3.51,岩场,5.89,5.61,5.61,4.56,3.51,3.65,2.46,2.46,1.06,0.57,岩石漏,0.64,1.76,1.27,1.83,2.74,2.60,4.21,3.72,5.05,6.10,倒装,4.42,3.86,3.72,3.16,2.25,2.81,0.78,1.62,1.27,0.50,铲位,1,铲位,2,铲位,3,铲位,4,铲位,5,铲位,6,铲位,7,铲位,8,铲位,9,铲位,10,矿石量,0,95,1,05,1,00,1,05,1,10,1,25,1,05,1,30,1,35,1,25,岩石量,1,25,1,10,1,35,1,05,1,15,1,35,1,05,1,15,1,35,1,25,铁含量,30%,28%,29%,32%,31%,33%,32%,31%,33%,31%,53/65,问题分析,与经典运输问题显著有以下不一样：,这是运输矿石与岩石两种物资问题；,属于产量大于销量不平衡运输问题；,为了完成品位约束，矿石要搭配运输；,产地、销地都有单位时间流量限制；,运输车辆只有一个，每次满载运输，,154,吨,/,车次；,铲位数多于铲车数意味着要最优选择不多于,7,个产地作为最终结果中产地；,最终求出各条路线上派出车辆数及安排。,近似处理：,先求出产位、卸点每条线路上运输量,(MIP,模型,),然后求出各条路线上派出车辆数及安排,54/65,模型假设,卡车在一个班次中不应发生等候或熄火后再开启情况；,在铲位或卸点处由两条路线以上造成冲突问题面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论；,空载与重载速度都是,28km/h,，耗油相差很大；,卡车可提前退出系统，等等。,如了解为严格不等候，难以用数学规划模型来解,个别参数队找到了可行解（略）,55/65,符号,x,ij,：从,i,铲位到,j,号卸点石料运量（车）单位：吨；,c,ij,：从,i,号铲位到,j,号卸点距离 公里；,T,ij,:,从,i,号铲位到号,j,卸点路线上运行一个周期平均时间 分；,A,ij,：从号铲位到号卸点最多能同时运行卡车数 辆；,B,ij,：从号铲位到号卸点路线上一辆车最多可运行次数 次；,p,i,：,i,号铲位矿石铁含量,p=(30,28,29,32,31,33,32,31,33,31)%,q,j,:j,号卸点任务需求，,q=(1.2,1.3,1.3,1.9,1.3)*10000,吨,ck,i,：,i,号铲位铁矿石储量 万吨,cy,i,：,i,号铲位岩石储量 万吨,f,i,:,描述第,i,号铲位是否使用,0-1,变量，取,1,为使用；,0,为关闭。,(,近似,),56/65,优化模型,（,1,）,道路能力,(,卡车数,),约束,（,2,）电铲能力约束,（,3,）卸点能力约束,（,4,）铲位储量约束,（,5,）产量任务约束,（,6,）铁含量约束,（,7,）电铲数量约束,（,8,）整数约束,.,x,ij,为非负整数,f,i,为,0-1,整数,57/65,计算结果（,LINGO,软件）,铲位,1,铲位,2,铲位,3,铲位,4,铲位,5,铲位,6,铲位,7,铲位,8,铲位,9,铲位,10,矿漏,13,54,11,倒,42,43,岩场,70,15,岩漏,81,43,倒,13,2,70,铲位,1,铲位,2,铲位,3,铲位,4,铲位,5,铲位,6,铲位,7,铲位,8,铲位,9,铲位,10,矿石漏,0.867,1.862,0.314,倒场,1.077,1.162,岩场,1.892,0.326,岩石漏,1.841,1.229,倒场,0.684,0.1,1.489,cumcmb1.lg4,58/65,计算结果（派车）,铲位,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,辆联合派车（方案略）,59/65,最大化产量,结论：,（略）,目标函数改变,另外：车辆数量（,20,辆）限制（其实上面模型也应该有）,60/65,A,1,3,2,5,80,10,10,31,20,12,42,70,10,88,10,70,62,70,30,20,20,30,450,104,301,750,606,194,205,201,680,480,300,220,210,420,500,600,3060,195,202,720,690,520,170,690,462,160,320,160,110,290,1150,1100,1200,A,2,A,3,A,4,A,5,A,6,A,7,A,8,A,9,A,10,A,11,A,12,A,13,A,14,A,15,S,1,S,2,S,3,S,4,S,5,S,6,S,7,铁路运价表,里程,300,301,350,351,400,401,450,451,500,运价,20,23,26,29,32,钢管运输问题,（,CUMCM-B),61/65,惯用解法,:,二次规划,先计算最小运费矩阵,两种运输方式（铁路公路）混合最短路问题,是普通最短路问题变种，需要自己设计算法,钢管运输问题,（,CUMCM-B),62/65,f,i,表示钢厂,i,是否使用；,x,ij,是从钢厂,i,运到节点,j,钢管量,y,j,是从节点,j,向左铺设钢管量；,z,j,是向右铺设钢管量,钢管运输问题,（,CUMCM-B),LINDO/LINGO,得到结果比,matlab,得到好,cumcmb.lg4,63/65,其它优化赛题,飞行管理问题,空洞探测问题,钻井布局问题,抢渡长江问题,等等,64/65,Thats all.Any Questions?,谢谢大家！,65/65,