optimizatiolindo北戴河概要.pptx
《optimizatiolindo北戴河概要.pptx》由会员分享,可在线阅读,更多相关《optimizatiolindo北戴河概要.pptx(80页珍藏版)》请在咨信网上搜索。
1、数学建模讲座数学建模讲座优化建模与优化建模与LINDO/LINGO优化软件优化软件简要提纲简要提纲 1.优化模型与优化软件简介优化模型与优化软件简介2.LINDO公司的主要软件产品及功能简介公司的主要软件产品及功能简介3.LINDO/LINGO软件的使用简介软件的使用简介4.建模与求解实例(结合软件使用)建模与求解实例(结合软件使用)1.优化模型与优化软件简介优化模型与优化软件简介最优化是工程技术、经济管理、科学研究、最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题社会生活中经常遇到的问题,如如:优化模型和优化软件的重要意义优化模型和优化软件的重要意义结构设计结构设计资源分配资源
2、分配生产计划生产计划运输方案运输方案解决优化问题的手段解决优化问题的手段经验积累,主观判断经验积累,主观判断作试验,比优劣作试验,比优劣建立数学模型建立数学模型(优化模型优化模型),求最优策略,求最优策略(决策决策)(最最)优化优化:在一定条件下在一定条件下,寻求使目标最大寻求使目标最大(小小)的决策的决策 CUMCMCUMCM赛题:约赛题:约70%70%以上与优化有关,需用软件求解以上与优化有关,需用软件求解运筹学运筹学(OR:Operations/OperationalResearch)管理科学管理科学(MS:ManagementScience)决策科学决策科学(DS:DecisionSc
3、ience)(最最)优化理论是运筹学的基本内容优化理论是运筹学的基本内容无无约约束束优优化化OR/MS/DS优化优化(Optimization),规划规划(Programming)线线性性规规划划非非线线性性规规划划网网络络优优化化组组合合优优化化整整数数规规划划不不确确定定规规划划多多目目标标规规划划目目标标规规划划动动态态规规划划优化问题三要素:优化问题三要素:决策变量决策变量;目标函数目标函数;约束条件约束条件约约束束条条件件决策变量决策变量优化问题的一般形式优化问题的一般形式可行解(满足约束)与可行域(可行解的集合)可行解(满足约束)与可行域(可行解的集合)最优解(取到最小大值的可行解
4、)最优解(取到最小大值的可行解)目标函数目标函数无约束优化无约束优化:最优解的分类和条件最优解的分类和条件给定一个函数给定一个函数 f(x),),寻找寻找 x*使得使得 f(x*)最小,即最小,即其中其中局部最优解局部最优解全局最优解全局最优解必要条件必要条件x*f(x)xlxgo充分条件充分条件Hessian阵阵最优解在可行域边界上取得时不能用无约束优化方法求解最优解在可行域边界上取得时不能用无约束优化方法求解约束优化的约束优化的简单分类简单分类线性规划线性规划(LP)目标和约束均为线性函数目标和约束均为线性函数非线性规划非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函
5、数二次规划二次规划(QP)目标为二次函数、约束为线性目标为二次函数、约束为线性整数规划整数规划(IP)决策变量决策变量(全部或部分全部或部分)为整数为整数整数整数线性线性规划规划(ILP),整数,整数非线性非线性规划规划(INLP)纯整数规划纯整数规划(PIP),混合整数规划混合整数规划(MIP)一般整数规划,一般整数规划,0-1(整数)规划(整数)规划连连续续优优化化离离散散优优化化数学规划数学规划常用优化软件常用优化软件 1.LINDO/LINGO软件软件2.MATLAB优化工具箱优化工具箱3.EXCEL软件的优化功能软件的优化功能4.SAS(统计分析统计分析)软件的优化功能软件的优化功能
6、5.其他其他MATLABMATLAB优化工具箱优化工具箱能求解的优化模型能求解的优化模型优化工具箱优化工具箱3.0(MATLAB7.0R14)连续优化连续优化离散优化离散优化无约束优化无约束优化非线性非线性极小极小fminunc非光滑非光滑(不可不可微微)优化优化fminsearch非线性非线性方方程程(组组)fzerofsolve全局全局优化优化暂缺暂缺非线性非线性最小二乘最小二乘lsqnonlinlsqcurvefit线性规划线性规划linprog纯纯0-1规划规划bintprog一般一般IP(暂缺暂缺)非线性规划非线性规划fminconfminimaxfgoalattainfseminf
7、上下界约束上下界约束fminbndfminconlsqnonlinlsqcurvefit约束线性约束线性最小二乘最小二乘lsqnonneglsqlin约束优化约束优化二次规划二次规划quadprog2.LINDO公司的主要软件产品及功能简介公司的主要软件产品及功能简介LINDO LINDO 公司软件产品简要介绍公司软件产品简要介绍美国芝加哥美国芝加哥(Chicago)大学的大学的LinusSchrage教授于教授于1980年前后开发年前后开发,后来成立后来成立LINDO系统公司(系统公司(LINDOSystemsInc.),),网址:网址:http:/LINDO:LinearINteracti
8、veandDiscreteOptimizer(V6.1)LINGO:LinearINteractiveGeneralOptimizer(V9.0)LINDOAPI:LINDOApplicationProgrammingInterface(V3.0)WhatsBest!:(SpreadSheete.g.EXCEL)(V8.0)演演示示(试用试用)版、学生版、高级版、超级版、工业版、版、学生版、高级版、超级版、工业版、扩展版扩展版(求解(求解问题规模问题规模和和选件选件不同)不同)LINDOLINDO和和LINGOLINGO软件能求解的优化模型软件能求解的优化模型LINGOLINDO优化模型优化模
9、型线性规划线性规划(LP)非线性规划非线性规划(NLP)二次规划二次规划(QP)连续优化连续优化整数规划整数规划(IP)LPQPNLPIP全局优化全局优化(选选)ILPIQPINLPLINDO/LINGO软件的求解过程 LINDO/LINGO预处理程序预处理程序线性优化求解程序线性优化求解程序非线性优化求解程序非线性优化求解程序分枝定界管理程序分枝定界管理程序1.确定常数确定常数2.识别类型识别类型1.单纯形算法单纯形算法2.内点算法内点算法(选选)1、顺序线性规划法、顺序线性规划法(SLP)2、广义既约梯度法、广义既约梯度法(GRG)(选选)3、多点搜索、多点搜索(Multistart)(选
10、选)建模时需要注意的几个基本问题建模时需要注意的几个基本问题1、尽量使用实数优化,减少整数约束和整数变量尽量使用实数优化,减少整数约束和整数变量2、尽量使用光滑优化,减少非光滑约束的个数尽量使用光滑优化,减少非光滑约束的个数如:尽量少使用绝对值、符号函数、多个变量求最如:尽量少使用绝对值、符号函数、多个变量求最大大/最小值、四舍五入、取整函数等最小值、四舍五入、取整函数等3、尽量使用线性模型,减少非线性约束和非线性变量尽量使用线性模型,减少非线性约束和非线性变量的个数的个数(如(如x/y5改为改为x5y)4、合理设定变量上下界,尽可能给出变量初始值合理设定变量上下界,尽可能给出变量初始值5、模
11、型中使用的参数数量级要适当模型中使用的参数数量级要适当(如小于如小于103)3.LINDO/LINGO软件的使用简介软件的使用简介需要掌握的几个重要方面需要掌握的几个重要方面1、LINDO:正确阅读求解报告(尤其要掌握敏感性分析)正确阅读求解报告(尤其要掌握敏感性分析)2、LINGO:掌握集合掌握集合(SETS)的应用;的应用;正确阅读求解报告;正确阅读求解报告;正确理解求解状态窗口;正确理解求解状态窗口;学会设置基本的求解选项学会设置基本的求解选项(OPTIONS);掌握与外部文件的基本接口方法掌握与外部文件的基本接口方法例例1加工奶制品的生产计划加工奶制品的生产计划1桶牛奶 3公斤A1 1
12、2小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶时间时间480小时小时 至多加工至多加工100公斤公斤A1制订生产计划,使每天获利最大制订生产计划,使每天获利最大 35元可买到元可买到1桶牛奶,买吗?若买,每天最多买多少桶牛奶,买吗?若买,每天最多买多少?可聘用临时工人,付出的工资最多是每小时几元可聘用临时工人,付出的工资最多是每小时几元?A1的获利增加到的获利增加到30元元/公斤,应否改变生产计划?公斤,应否改变生产计划?每天:每天:1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产桶牛奶生产A1x2桶牛
13、奶生产桶牛奶生产A2获利获利243x1获利获利164 x2原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A150桶牛奶桶牛奶每天每天模型求解模型求解 max72x1+64x2st2)x1+x2503)12x1+8x24804)3x1100endOBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.
14、000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2,利润,利润3360元。元。模型求解模型求解 reduced cost值值表表示示当当该该非非基基变变量量增增加加一一个个单单位位时时(其其他他非非基基变变量量保保持持不不变变)目目标标函函数数减减少少的的量量(对对max型问题型问题)OBJECTIVEFUNCTIONVALUE
15、1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2也可理解为:也可理解为:为为了了使使该该非非基基变变量量变变成成基基变变量量,目目标标函函数数中中对对应应系数应增加的量系数应增加的量OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.00
16、00000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40max72x1+64x2st2)x1+x2503)12x1+8x24804)3x1100end三三种种资资源源“资源资源”剩余为零的约束为紧约束(有效约束)剩余为零的约束为紧约束(有效约束)结果解释结果解释 OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUERED
17、UCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000结果解释结果解释 最优解下最优解下“资源资源”增增加加1单位时单位时“效益效益”的的增量增量原料增原料增1单位单位,利润增利润增48时间加时间加1单位单位,利润增利润增2能力增减不影响利润能力增减不影响利润影子价格影子价格35元可买到元可买到1桶牛奶,要买吗?桶牛奶,要买吗?35”(或(或“=”(或(或“=”)功能相同)功能相同2.变量与系
18、数间可有空格变量与系数间可有空格(甚至回车甚至回车),但无运算符但无运算符3.变量名以字母开头,不能超过变量名以字母开头,不能超过8个字符个字符4.变量名不区分大小写(包括变量名不区分大小写(包括LINDO中的关键字)中的关键字)5.目标函数所在行是第一行,第二行起为约束条件目标函数所在行是第一行,第二行起为约束条件6.行号行号(行名行名)自动产生或人为定义。行名以自动产生或人为定义。行名以“)”结结束束7.行中注有行中注有“!”符号的后面部分为注释。如符号的后面部分为注释。如:!ItsComment.8.在模型的任何地方都可以用在模型的任何地方都可以用“TITLE”对模型命名对模型命名(最多
19、(最多72个字符),如:个字符),如:TITLEThisModelisonlyanExample9.变量不能出现在一个约束条件的右端变量不能出现在一个约束条件的右端10.表达式中不接受括号表达式中不接受括号“()”和逗号和逗号“,”等任何符号等任何符号,例例:400(X1+X2)需写为需写为400X1+400X211.表达式应化简,如表达式应化简,如2X1+3X2-4X1应写成应写成-2X1+3X212.缺省假定所有变量非负;可在模型的缺省假定所有变量非负;可在模型的“END”语句语句后用后用“FREEname”将变量将变量name的非负假定取消的非负假定取消13.可在可在“END”后用后用“
20、SUB”或或“SLB”设定变量上设定变量上下界下界例如:例如:“subx110”的作用等价于的作用等价于“x1=10”但用但用“SUB”和和“SLB”表示的上下界约束不计入模表示的上下界约束不计入模型的约束,也不能给出其松紧判断和敏感性分析。型的约束,也不能给出其松紧判断和敏感性分析。14.“END”后对后对0-1变量说明:变量说明:INTn或或INTname15.“END”后对整数变量说明:后对整数变量说明:GINn或或GINname使用使用LINDOLINDO的一些注意事项的一些注意事项二次规划规划(QP)问题LINDO可求解二次规划可求解二次规划(QP)问题,但输入方式较问题,但输入方式
21、较复杂,因为在复杂,因为在LINDO中不许出现非线性表达式中不许出现非线性表达式需要为每一个实际约束增加一个对偶变量需要为每一个实际约束增加一个对偶变量(LAGRANGE乘子),在实际约束前增加有关乘子),在实际约束前增加有关变量的一阶最优条件,转化为互补问题变量的一阶最优条件,转化为互补问题“END”后面使用后面使用QCP命令指明实际约束开始的行命令指明实际约束开始的行号,然后才能求解号,然后才能求解建议总是用建议总是用LINGO解解QP注意注意对对QP和和IP:敏感性分析意义不大敏感性分析意义不大状态窗口状态窗口(LINDO Solver Status)当前状态:已达最优解当前状态:已达最
22、优解迭代次数:迭代次数:18次次约束不满足的约束不满足的“量量”(不不是是“约束个数约束个数”):0当前的目标值:当前的目标值:94最好的整数解:最好的整数解:94整数规划的界:整数规划的界:93.5分枝数:分枝数:1所用时间:所用时间:0.00秒(太快秒(太快了,还不到了,还不到0.005秒)秒)刷新本界面的间隔刷新本界面的间隔:1(秒秒)选项设置选项设置Preprocess:预处理:预处理(生成割平面生成割平面);PreferredBranch:优先的分枝方式:优先的分枝方式:“Default”(缺省方式)、(缺省方式)、“Up”(向上取整优先)、(向上取整优先)、“Down”(向下取整优
23、先);(向下取整优先);IPOptimalityTol:IP最优值允许的误最优值允许的误差上限(一个百分数,如差上限(一个百分数,如5%即即0.05););IPObjectiveHurdle:IP目标函数的篱目标函数的篱笆值,即只寻找比这个值更优最优解笆值,即只寻找比这个值更优最优解(如当知道当前模型的某个整数可行解(如当知道当前模型的某个整数可行解时,就可以设置这个值);时,就可以设置这个值);IPVarFixingTol:固定一个整数变量:固定一个整数变量取值所依据的一个上限(如果一个整数取值所依据的一个上限(如果一个整数变量的判别数(变量的判别数(REDUCEDCOST)的)的值很大,超
24、过该上限,则以后求解中把值很大,超过该上限,则以后求解中把该整数变量固定下来)。该整数变量固定下来)。NonzeroLimit:非零系数的个数上限;非零系数的个数上限;IterationLimit:最大迭代步数;最大迭代步数;InitialContraintTol:约束的初始误差上限;约束的初始误差上限;FinalContraintTol:约束的最后误差上限;约束的最后误差上限;EnteringVarTol:进基变量的进基变量的REDUCEDCOST的误差限;的误差限;PivotSizeTol:旋转元的误差限旋转元的误差限Report/Statistics第一行:模型有第一行:模型有5行(约束
25、行(约束4行),行),4个变量,两个整数变量(没有个变量,两个整数变量(没有0-1变量),从第变量),从第4行开始是二次规划的实际约束。行开始是二次规划的实际约束。第二行:非零系数第二行:非零系数19个,约束中非零系数个,约束中非零系数12个个(其中其中6个为个为1或或-1),模型密度为模型密度为0.760(密度密度=非零系数非零系数/行数行数(变量数变量数)。第三行的意思:按绝对值看,系数最小、最大分别为第三行的意思:按绝对值看,系数最小、最大分别为0.3和和277。第四行的意思:模型目标为极小化;小于等于、等于、大于等于约第四行的意思:模型目标为极小化;小于等于、等于、大于等于约束分别有、
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- optimizatiolindo 北戴河 概要
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。