优化模型与优化软件简介课件.pptx
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《优化模型与优化软件简介课件.pptx》由用户(ziliao2023)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 优化 模型 软件 简介 课件
- 资源描述:
-
1、简要提纲简要提纲 1.优化模型与优化软件简介优化模型与优化软件简介2.LINDO公司的主要软件产品及功能简介公司的主要软件产品及功能简介3.LINDO/LINGO软件的使用简介软件的使用简介4.建模与求解实例(结合软件使用)建模与求解实例(结合软件使用)1.优化模型与优化软件简介优化模型与优化软件简介 最优化是工程技术、经济管理、科学研究、最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题社会生活中经常遇到的问题,如如:优化模型和优化软件的重要意义优化模型和优化软件的重要意义结构设计结构设计资源分配资源分配生产计划生产计划运输方案运输方案解决优化问题的手段解决优化问题的手段 经验积
2、累,主观判断经验积累,主观判断 作试验,比优劣作试验,比优劣 建立数学模型建立数学模型(优化模型优化模型),求最优策略,求最优策略(决策决策)(最最)优化优化:在一定条件下在一定条件下,寻求使目标最大寻求使目标最大(小小)的决策的决策 CUMCMCUMCM赛题:约赛题:约70%70%以上与优化有关,需用软件求解以上与优化有关,需用软件求解运筹学运筹学(OR:Operations/Operational Research)管理科学管理科学(MS:Management Science)决策科学决策科学(DS:Decision Science)(最最)优化理论是运筹学的基本内容优化理论是运筹学的基本
3、内容无无约约束束优优化化OR/MS/DS优化优化(Optimization),规划规划(Programming)线线性性规规划划非非线线性性规规划划网网络络优优化化组组合合优优化化整整数数规规划划不不确确定定规规划划多多目目标标规规划划目目标标规规划划动动态态规规划划优化问题三要素:优化问题三要素:决策变量决策变量;目标函数目标函数;约束条件约束条件约约束束条条件件决策变量决策变量优化问题的一般形式优化问题的一般形式njiDxljxgmixhtsxf,.,1,0)(,.,1,0)(.)(min可行解(满足约束)与可行域(可行解的集合)可行解(满足约束)与可行域(可行解的集合)最优解(取到最小大
4、值的可行解)最优解(取到最小大值的可行解)目标函数目标函数无约束优化无约束优化:最优解的分类和条件最优解的分类和条件)(xfMinx给定一个函数给定一个函数 f(x),),寻找寻找 x*使得使得 f(x*)最小,即最小,即nTnxxxx),(21其中其中局部最优解局部最优解全局最优解全局最优解必要条件必要条件0),()(1*Txxnffxfx*f(x)xlxgo充分条件充分条件0)(,0)(*2*xfxfHessian阵阵nnjixxff22最优解在可行域边界上取得时不能用无约束优化方法求解最优解在可行域边界上取得时不能用无约束优化方法求解约束优化的约束优化的简单分类简单分类 线性规划线性规划
5、(LP)目标和约束均为线性函数目标和约束均为线性函数 非线性规划非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函数 二次规划二次规划(QP)目标为二次函数、约束为线性目标为二次函数、约束为线性 整数规划整数规划(IP)决策变量决策变量(全部或部分全部或部分)为整数为整数 整数整数线性线性规划规划(ILP),整数,整数非线性非线性规划规划(INLP)纯整数规划纯整数规划(PIP),混合整数规划混合整数规划(MIP)一般整数规划,一般整数规划,0-1(整数)规划(整数)规划njiDxljxgmixhtsxf,.,1,0)(,.,1,0)(.)(min连连续续优优化化离离散散优
6、优化化数学规划数学规划常用优化软件常用优化软件 1.LINDO/LINGO软件软件2.MATLAB优化工具箱优化工具箱3.EXCEL软件的优化功能软件的优化功能4.SAS(统计分析统计分析)软件的优化功能软件的优化功能5.其他其他MATLABMATLAB优化工具箱优化工具箱能求解的优化模型能求解的优化模型优化工具箱优化工具箱3.0(MATLAB 7.0 R14)连续优化连续优化离散优化离散优化无约束优化无约束优化非线性非线性极小极小fminunc非光滑非光滑(不可不可微微)优化优化fminsearch非线性非线性方程方程(组组)fzerofsolve全局全局优化优化暂缺暂缺非线性非线性最小二乘
7、最小二乘lsqnonlinlsqcurvefit线性规划线性规划linprog纯纯0-1规划规划 bintprog一般一般IP(暂缺暂缺)非线性规划非线性规划fminconfminimaxfgoalattainfseminf上下界约束上下界约束fminbndfminconlsqnonlinlsqcurvefit约束线性约束线性最小二乘最小二乘lsqnonneglsqlin约束优化约束优化二次规划二次规划quadprog2.LINDO公司的主要软件产品及功能简介公司的主要软件产品及功能简介LINDO LINDO 公司软件产品简要介绍公司软件产品简要介绍 美国芝加哥美国芝加哥(Chicago)大学
8、的大学的Linus Schrage教授于教授于1980年前后开发年前后开发,后来成立后来成立 LINDO系统公司(系统公司(LINDO Systems Inc.),),网址:网址:http:/ LINDO:Linear INteractive and Discrete Optimizer (V6.1)LINGO:Linear INteractive General Optimizer (V9.0)LINDO API:LINDO Application Programming Interface(V3.0)Whats Best!:(SpreadSheet e.g.EXCEL)(V8.0)演演示示
9、(试用试用)版、学生版、高级版、超级版、工业版、版、学生版、高级版、超级版、工业版、扩展版扩展版(求解(求解问题规模问题规模和和选件选件不同)不同)LINDOLINDO和和LINGOLINGO软件能求解的优化模型软件能求解的优化模型 LINGO LINDO优化模型优化模型线性规划线性规划(LP)非线性规划非线性规划(NLP)二次规划二次规划(QP)连续优化连续优化整数规划整数规划(IP)LP QP NLP IP 全局优化全局优化(选选)ILP IQP INLP LINDO/LINGO软件的求解过程 LINDO/LINGO预处理程序预处理程序线性优化求解程序线性优化求解程序非线性优化求解程序非线
10、性优化求解程序分枝定界管理程序分枝定界管理程序1.确定常数确定常数2.识别类型识别类型1.单纯形算法单纯形算法2.内点算法内点算法(选选)1、顺序线性规划法、顺序线性规划法(SLP)2、广义既约梯度法、广义既约梯度法(GRG)(选选)3、多点搜索、多点搜索(Multistart)(选选)建模时需要注意的几个基本问题建模时需要注意的几个基本问题 1、尽量使用实数优化,减少整数约束和整数变量尽量使用实数优化,减少整数约束和整数变量2、尽量使用光滑优化,减少非光滑约束的个数尽量使用光滑优化,减少非光滑约束的个数 如:尽量少使用绝对值、符号函数、多个变量求如:尽量少使用绝对值、符号函数、多个变量求最大
11、最大/最小值、四舍五入、取整函数等最小值、四舍五入、取整函数等3、尽量使用线性模型,减少非线性约束和非线性变尽量使用线性模型,减少非线性约束和非线性变量的个数量的个数 (如(如x/y 5 改为改为x5y)4、合理设定变量上下界,尽可能给出变量初始值合理设定变量上下界,尽可能给出变量初始值 5、模型中使用的参数数量级要适当模型中使用的参数数量级要适当 (如小于如小于103)3.LINDO/LINGO软件的使用简介软件的使用简介需要掌握的几个重要方面需要掌握的几个重要方面1、LINDO:正确阅读求解报告(尤其要掌握敏感性分析)正确阅读求解报告(尤其要掌握敏感性分析)2、LINGO:掌握集合掌握集合
12、(SETS)的应用;的应用;正确阅读求解报告;正确阅读求解报告;正确理解求解状态窗口;正确理解求解状态窗口;学会设置基本的求解选项学会设置基本的求解选项(OPTIONS);掌握与外部文件的基本接口方法掌握与外部文件的基本接口方法例例1 加工奶制品的生产计划加工奶制品的生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶 时间时间480小时小时 至多加工至多加工100公斤公斤A1 制订生产计划,使每天获利最大制订生产计划,使每天获利最大 35元可买到元可买到1桶牛奶,买吗?若买,每天最多买多少桶牛奶,买吗?若买,每天最多买多少?可聘用
13、临时工人,付出的工资最多是每小时几元可聘用临时工人,付出的工资最多是每小时几元?A1的获利增加到的获利增加到 30元元/公斤,应否改变生产计划?公斤,应否改变生产计划?每天:每天:1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产桶牛奶生产A1 x2桶牛奶生产桶牛奶生产A2 获利获利 243x1 获利获利 164 x2 原料供应原料供应 5021 xx劳动时间劳动时间 48081221 xx加工能力加工能力 10031x决策变量决策变量 目标函数目标函数 216472xxzMax每天获利每天获利约束条件约束条件非负约束非负约束 0,21xx
14、线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天模型求解模型求解 max 72x1+64x2st2)x1+x2503)12x1+8x24804)3x1100end 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
15、)40.000000 0.000000 NO.ITERATIONS=2DO RANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2,利润,利润3360元。元。模型求解模型求解 reduced cost值表值表示当该非基变量示当该非基变量增加一个单位时增加一个单位时(其他非基变量(其他非基变量保持不变)目标保持不变)目标函数减少的量函数减少的量(对对max型问题型问题)OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2
16、 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也可理解为:也可理解为:为了使该非基变为了使该非基变量变成基变量,量变成基变量,目标函数中对应目标函数中对应系数应增加的量系数应增加的量 OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.
17、000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40max 72x1+64x2st2)x1+x2503)12x1+8x24804)3x1100end三三种种资资源源“资源资源”剩余为零的约束为紧约束(有效约束)剩余为零的约束为紧约束(有效约束)结果解释结果解释 OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED C
18、OST 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”(或(或“=”(或(或“=
19、”)功能相同)功能相同2.变量与系数间可有空格变量与系数间可有空格(甚至回车甚至回车),但无运算符但无运算符3.变量名以字母开头,不能超过变量名以字母开头,不能超过8个字符个字符4.变量名不区分大小写(包括变量名不区分大小写(包括LINDO中的关键字)中的关键字)5.目标函数所在行是第一行,第二行起为约束条件目标函数所在行是第一行,第二行起为约束条件6.行号行号(行名行名)自动产生或人为定义。行名以自动产生或人为定义。行名以“)”结结束束7.行中注有行中注有“!”符号的后面部分为注释。如符号的后面部分为注释。如:!Its Comment.8.在模型的任何地方都可以用在模型的任何地方都可以用“T
20、ITLE”对模型命名对模型命名(最多(最多72个字符),如:个字符),如:TITLE This Model is only an Example9.变量不能出现在一个约束条件的右端变量不能出现在一个约束条件的右端10.表达式中不接受括号表达式中不接受括号“()”和逗号和逗号“,”等任何符号等任何符号,例例:400(X1+X2)需写为需写为400X1+400X211.表达式应化简,如表达式应化简,如2X1+3X2-4X1应写成应写成-2X1+3X212.缺省假定所有变量非负;可在模型的缺省假定所有变量非负;可在模型的“END”语句语句后用后用“FREE name”将变量将变量name的非负假定取
21、消的非负假定取消13.可在可在“END”后用后用“SUB”或或“SLB”设定变量上设定变量上下界下界 例如:例如:“sub x1 10”的作用等价于的作用等价于“x1=10”但用但用“SUB”和和“SLB”表示的上下界约束不计入模表示的上下界约束不计入模型的约束,也不能给出其松紧判断和敏感性分析。型的约束,也不能给出其松紧判断和敏感性分析。14.“END”后对后对0-1变量说明:变量说明:INT n 或或 INT name15.“END”后对整数变量说明:后对整数变量说明:GIN n 或或 GIN name使用使用LINDOLINDO的一些注意事项的一些注意事项二次规划规划(QP)问题 LIN
22、DO可求解二次规划可求解二次规划(QP)问题,但输入方式较问题,但输入方式较复杂,因为在复杂,因为在LINDO中不许出现非线性表达式中不许出现非线性表达式 需要为每一个实际约束增加一个对偶变量需要为每一个实际约束增加一个对偶变量(LAGRANGE乘子),在实际约束前增加有关乘子),在实际约束前增加有关变量的一阶最优条件,转化为互补问题变量的一阶最优条件,转化为互补问题“END”后面使用后面使用QCP命令指明实际约束开始的命令指明实际约束开始的行号,然后才能求解行号,然后才能求解 建议总是用建议总是用LINGO解解QP注意注意对对QP和和IP:敏感性分析意义不大敏感性分析意义不大状态窗口状态窗口
23、(LINDO Solver Status)当前状态:已达最优解当前状态:已达最优解 迭代次数:迭代次数:18次次 约束不满足的约束不满足的“量量”(不不是是“约束个数约束个数”):0 当前的目标值:当前的目标值:94 最好的整数解:最好的整数解:94 整数规划的界:整数规划的界:93.5 分枝数:分枝数:1 所用时间:所用时间:0.00秒(太快秒(太快了,还不到了,还不到0.005秒)秒)刷新本界面的间隔刷新本界面的间隔:1(秒秒)选项设置选项设置 Preprocess:预处理:预处理(生成割平面生成割平面);Preferred Branch:优先的分枝方式:优先的分枝方式:“Default”
24、(缺省方式)、(缺省方式)、“Up”(向上取整优先)、(向上取整优先)、“Down”(向下取整优先);(向下取整优先);IP Optimality Tol:IP最优值允许的误最优值允许的误差上限(一个百分数,如差上限(一个百分数,如5%即即0.05););IP Objective Hurdle:IP目标函数的篱目标函数的篱笆值,即只寻找比这个值更优最优解笆值,即只寻找比这个值更优最优解(如当知道当前模型的某个整数可行解(如当知道当前模型的某个整数可行解时,就可以设置这个值);时,就可以设置这个值);IP Var Fixing Tol:固定一个整数变量:固定一个整数变量取值所依据的一个上限(如果
25、一个整数取值所依据的一个上限(如果一个整数变量的判别数(变量的判别数(REDUCED COST)的)的值很大,超过该上限,则以后求解中把值很大,超过该上限,则以后求解中把该整数变量固定下来)。该整数变量固定下来)。Nonzero Limit:非零系数的个数上限;非零系数的个数上限;Iteration Limit:最大迭代步数;最大迭代步数;Initial Contraint Tol:约束的初始误差上限;约束的初始误差上限;Final Contraint Tol:约束的最后误差上限;约束的最后误差上限;Entering Var Tol:进基变量的进基变量的REDUCED COST的误差限;的误差
展开阅读全文