清华大学lingo.ppt
《清华大学lingo.ppt》由会员分享,可在线阅读,更多相关《清华大学lingo.ppt(65页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、数学建模讲座(数学建模讲座(2004年年7月月8月月 江西)江西)优化模型与优化模型与LINDO/LINGO优化软件优化软件谢金星谢金星清华大学数学科学系清华大学数学科学系Tel:010-62787812Email:http:/ 优化模型简介优化模型简介LINDO公司的主要软件产品及功能简介公司的主要软件产品及功能简介LINDO软件的使用简介软件的使用简介LINGO软件的使用简介软件的使用简介 建模与求解实例(结合软件使用)建模与求解实例(结合软件使用)优化模型优化模型 实际问题中实际问题中的优化模型的优化模型x决策变量决策变量f(x)目标函数目标函数gi(x)0约束条约束条件件数学规划数学规
2、划线性规划线性规划(LP)二次规划二次规划(QP)非线性规划非线性规划(NLP)纯整数规划纯整数规划(PIP)混合整数规划混合整数规划(MIP)整数规划整数规划(IP)0-1整数规划整数规划一般整数规划一般整数规划连续规划连续规划LINDO LINDO 公司软件产品简要介绍公司软件产品简要介绍美国芝加哥美国芝加哥(Chicago)大学的大学的LinusSchrage教授于教授于1980年前后开发年前后开发,后来成立后来成立LINDO系统公司(系统公司(LINDOSystemsInc.),),网址:网址:http:/LINDO:LinearINteractiveandDiscreteOptimi
3、zer(V6.1)LINGO:LinearINteractiveGeneralOptimizer(V8.0)LINDOAPI:LINDOApplicationProgrammingInterface(V2.0)WhatsBest!:(SpreadSheete.g.EXCEL)(V7.0)演演示示(试用试用)版、学生版、高级版、超级版、工业版、版、学生版、高级版、超级版、工业版、扩展版扩展版(求解(求解问题规模问题规模和和选件选件不同)不同)LINDOLINDO和和LINGOLINGO软件能求解的优化模型软件能求解的优化模型LINGOLINDO优化模型优化模型线性规划线性规划(LP)非线性规划非
4、线性规划(NLP)二次规划二次规划(QP)连续优化连续优化整数规划整数规划(IP)LPQPNLPIP全局优化全局优化(选选)ILPIQPINLPLINDO/LINGO软件的求解过程 LINDO/LINGO预处理程序预处理程序线性优化求解程序线性优化求解程序非线性优化求解程序非线性优化求解程序分枝定界管理程序分枝定界管理程序1.确定常数确定常数2.识别类型识别类型1.单纯形算法单纯形算法2.内点算法内点算法(选选)1、顺序线性规划法、顺序线性规划法(SLP)2、广义既约梯度法、广义既约梯度法(GRG)(选选)3、多点搜索、多点搜索(Multistart)(选选)建模时需要注意的几个基本问题建模时
5、需要注意的几个基本问题1、尽量使用实数优化,减少整数约束和整数变量尽量使用实数优化,减少整数约束和整数变量2、尽量使用光滑优化,减少非光滑约束的个数尽量使用光滑优化,减少非光滑约束的个数如:尽量少使用绝对值、符号函数、多个变量求最如:尽量少使用绝对值、符号函数、多个变量求最大大/最小值、四舍五入、取整函数等最小值、四舍五入、取整函数等3、尽量使用线性模型,减少非线性约束和非线性变量尽量使用线性模型,减少非线性约束和非线性变量的个数的个数(如(如x/y5改为改为x5y)4、合理设定变量上下界,尽可能给出变量初始值合理设定变量上下界,尽可能给出变量初始值5、模型中使用的参数数量级要适当模型中使用的
6、参数数量级要适当(如小于如小于103)需要掌握的几个重要方面需要掌握的几个重要方面1、LINDO:正确阅读求解报告(尤其要掌握敏感性分析)正确阅读求解报告(尤其要掌握敏感性分析)2、LINGO:掌握集合掌握集合(SETS)的应用;的应用;正确阅读求解报告;正确阅读求解报告;正确理解求解状态窗口;正确理解求解状态窗口;学会设置基本的求解选项学会设置基本的求解选项(OPTIONS);掌握与外部文件的基本接口方法掌握与外部文件的基本接口方法例例1加工奶制品的生产计划加工奶制品的生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶时间时间4
7、80小时小时 至多加工至多加工100公斤公斤A1制订生产计划,使每天获利最大制订生产计划,使每天获利最大 35元可买到元可买到1桶牛奶,买吗?若买,每天最多买多少桶牛奶,买吗?若买,每天最多买多少?可聘用临时工人,付出的工资最多是每小时几元可聘用临时工人,付出的工资最多是每小时几元?A1的获利增加到的获利增加到30元元/公斤,应否改变生产计划?公斤,应否改变生产计划?每天:每天:1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2获利获利243x1获利获利164 x2原料供应原料供应 劳动时间劳动时间
8、 加工能力加工能力 决策变量决策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A150桶牛奶桶牛奶每天每天模型求解模型求解 max72x1+64x2st2)x1+x2503)12x1+8x24804)3x1100endOBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.
9、0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2,利润利润3360元。元。模型求解模型求解 reduced cost值值表表示示当当该该非非基基变变量量增增加加一一个个单单位位时时(其其他他非非基基变变量量保保持持不不变变)目目标标函函数数减减少少的的量量(对对max型问题型问题)OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.
10、000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2也可理解为:也可理解为:为为了了使使该该非非基基变变量量变变成成基基变变量量,目目标标函函数数中中对对应应系数应增加的量系数应增加的量OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLU
11、SDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40max72x1+64x2st2)x1+x2503)12x1+8x24804)3x1100end三三种种资资源源“资源资源”剩余为零的约束为紧约束(有效约束)剩余为零的约束为紧约束(有效约束)结果解释结果解释 OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000R
12、OWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000结果解释结果解释 最优解下最优解下“资源资源”增增加加1单位时单位时“效益效益”的的增量增量原料增原料增1单位单位,利润增利润增48时间加时间加1单位单位,利润增利润增2能力增减不影响利润能力增减不影响利润影子价格影子价格35元可买到元可买到1桶牛奶,要买吗?桶牛奶,要买吗?35”(或(或“=”(或(或“=”)功能相)功能相同同2.变量与系数间可有空格变量与系数间可有空格(甚至回车甚至回车),但无运算符但无运算符3.变量名以字母开头
13、,不能超过变量名以字母开头,不能超过8个字符个字符4.变量名不区分大小写(包括变量名不区分大小写(包括LINDO中的关键字)中的关键字)5.目标函数所在行是第一行,第二行起为约束条件目标函数所在行是第一行,第二行起为约束条件6.行号行号(行名行名)自动产生或人为定义。行名以自动产生或人为定义。行名以“)”结结束束7.行中注有行中注有“!”符号的后面部分为注释。如符号的后面部分为注释。如:!ItsComment.8.在模型的任何地方都可以用在模型的任何地方都可以用“TITLE”对模型命名对模型命名(最多(最多72个字符),如:个字符),如:TITLEThisModelisonlyanExampl
14、e9.变量不能出现在一个约束条件的右端变量不能出现在一个约束条件的右端10.表达式中不接受括号表达式中不接受括号“()”和逗号和逗号“,”等任何符等任何符号号,例例:400(X1+X2)需写为需写为400X1+400X211.表达式应化简,如表达式应化简,如2X1+3X2-4X1应写成应写成-2X1+3X212.缺省假定所有变量非负;可在模型的缺省假定所有变量非负;可在模型的“END”语句语句后用后用“FREEname”将变量将变量name的非负假定取消的非负假定取消13.可在可在“END”后用后用“SUB”或或“SLB”设定变量上设定变量上下界下界例如:例如:“subx110”的作用等价于的
15、作用等价于“x1=10”但用但用“SUB”和和“SLB”表示的上下界约束不计入模表示的上下界约束不计入模型的约束,也不能给出其松紧判断和敏感性分析。型的约束,也不能给出其松紧判断和敏感性分析。14.“END”后对后对0-1变量说明:变量说明:INTn或或INTname15.“END”后对整数变量说明:后对整数变量说明:GINn或或GINname使用使用LINDOLINDO的一些注意事项的一些注意事项二次规划规划(QP)问题LINDO可求解二次规划可求解二次规划(QP)问题,但输入方式较问题,但输入方式较复杂,因为在复杂,因为在LINDO中不许出现非线性表达式中不许出现非线性表达式需要为每一个实
16、际约束增加一个对偶变量需要为每一个实际约束增加一个对偶变量(LAGRANGE乘子),在实际约束前增加有关乘子),在实际约束前增加有关变量的一阶最优条件,转化为互补问题变量的一阶最优条件,转化为互补问题“END”后面使用后面使用QCP命令指明实际约束开始的行命令指明实际约束开始的行号,然后才能求解号,然后才能求解建议总是用建议总是用LINGO解解QP注意注意对对QP和和IP:敏感性分析意义不大敏感性分析意义不大状态窗口状态窗口(LINDO Solver Status)当前状态:已达最优解当前状态:已达最优解迭代次数:迭代次数:18次次约束不满足的约束不满足的“量量”(不不是是“约束个数约束个数”
17、):0当前的目标值:当前的目标值:94最好的整数解:最好的整数解:94整数规划的界:整数规划的界:93.5分枝数:分枝数:1所用时间:所用时间:0.00秒(太快秒(太快了,还不到了,还不到0.005秒)秒)刷新本界面的间隔刷新本界面的间隔:1(秒秒)选项设置选项设置Preprocess:预处理:预处理(生成割平面生成割平面);PreferredBranch:优先的分枝方式:优先的分枝方式:“Default”(缺省方式)、(缺省方式)、“Up”(向上取整优先)、(向上取整优先)、“Down”(向下取整优先);(向下取整优先);IPOptimalityTol:IP最优值允许的误最优值允许的误差上限
18、(一个百分数,如差上限(一个百分数,如5%即即0.05););IPObjectiveHurdle:IP目标函数的篱目标函数的篱笆值,即只寻找比这个值更优最优解笆值,即只寻找比这个值更优最优解(如当知道当前模型的某个整数可行解(如当知道当前模型的某个整数可行解时,就可以设置这个值);时,就可以设置这个值);IPVarFixingTol:固定一个整数变量:固定一个整数变量取值所依据的一个上限(如果一个整数取值所依据的一个上限(如果一个整数变量的判别数(变量的判别数(REDUCEDCOST)的)的值很大,超过该上限,则以后求解中把值很大,超过该上限,则以后求解中把该整数变量固定下来)。该整数变量固定
19、下来)。NonzeroLimit:非零系数的个数上限;非零系数的个数上限;IterationLimit:最大迭代步数;最大迭代步数;InitialContraintTol:约束的初始误差上限;约束的初始误差上限;FinalContraintTol:约束的最后误差上限;约束的最后误差上限;EnteringVarTol:进基变量的进基变量的REDUCEDCOST的误差限;的误差限;PivotSizeTol:旋转元的误差限旋转元的误差限Report/Statistics第一行:模型有第一行:模型有5行(约束行(约束4行),行),4个变量,两个整数变量(没有个变量,两个整数变量(没有0-1变量),从第
20、变量),从第4行开始是二次规划的实际约束。行开始是二次规划的实际约束。第二行:非零系数第二行:非零系数19个,约束中非零系数个,约束中非零系数12个个(其中其中6个为个为1或或-1),模型密度为模型密度为0.760(密度密度=非零系数非零系数/行数行数(变量数变量数)。第三行的意思:按绝对值看,系数最小、最大分别为第三行的意思:按绝对值看,系数最小、最大分别为0.3和和277。第四行的意思:模型目标为极小化;小于等于、等于、大于等于约第四行的意思:模型目标为极小化;小于等于、等于、大于等于约束分别有、个;广义上界约束(束分别有、个;广义上界约束(GUBS)不超过个;)不超过个;变量上界约束(变
21、量上界约束(VUBS)不少于个。所谓)不少于个。所谓GUBS,是指一组不,是指一组不含有相同变量的约束;所谓含有相同变量的约束;所谓VUBS,是指一个蕴涵变量上界的约,是指一个蕴涵变量上界的约束,如从约束束,如从约束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
22、 CONSTRAINT NONZ=12(6=+-1)DENSITY=0.760SMALLEST AND LARGEST ELEMENTS IN ABSOLUTE VALUE=0.300000 277.000OBJ=MIN,NO.:2 0 2,GUBS=0SINGLE COLS=0 REDUNDANT COLS=0LINDOLINDO行命令、命令脚本文件行命令、命令脚本文件批处理:可以采用命令脚本(行命令序列)批处理:可以采用命令脚本(行命令序列)WINDOWS环境下行命令的意义不大环境下行命令的意义不大Example演示演示用用FILE/TAKECOMMANDS(F11)命令调入命令调入必须是
23、以必须是以LINDOPACKED形式形式(压缩)保存的文件(压缩)保存的文件FILE/SAVE命令命令SAVE行命令行命令LINGO软件简介软件简介目标与约束段目标与约束段集合段(集合段(SETSENDSETS)数据段(数据段(DATAENDDATA)初始段(初始段(INITENDINIT)LINGO模型的构成:模型的构成:4个段个段LINGO模型的优点模型的优点包含了包含了LINDO的全部功能的全部功能提供了灵活的编程语言(矩阵生成器)提供了灵活的编程语言(矩阵生成器)LINGOLINGO模型模型 例:选址问题例:选址问题某公司有某公司有6个建筑工地,位置坐标为个建筑工地,位置坐标为(ai,
24、bi)(单位:公单位:公里里),水泥日用量水泥日用量di(单位:吨)单位:吨)假设:假设:料场料场和工地之间和工地之间有直线道路有直线道路用例中数据计算,最优解为总吨公里数为总吨公里数为总吨公里数为总吨公里数为136.2136.2线性规划模型线性规划模型决策变量:决策变量:ci j(料场料场j到到工地工地i的运量)的运量)12维维选址问题:选址问题:NLPNLP2)改建两个新料场,需要确定新料场位置)改建两个新料场,需要确定新料场位置(xj,yj)和运量和运量cij,在其它条件不变下使总吨公里数最小。在其它条件不变下使总吨公里数最小。决策变量:决策变量:ci j,(xj,yj)16维维非线性规
25、划模型非线性规划模型LINGO模型的构成:模型的构成:4个段个段集合段(集合段(SETSENDSETS)数据段(数据段(DATAENDDATA)初始段(初始段(INITENDINIT)目标与目标与约束段约束段局部最优:局部最优:89.8835(吨公里吨公里)LP:移到数据段:移到数据段边界集合的类型集合的类型集合集合派生集合派生集合基本集合基本集合稀疏集合稀疏集合稠密集合稠密集合元素列表法元素列表法元素过滤法元素过滤法直接列举法直接列举法隐式列举法隐式列举法setname/member_list/:attribute_list;setname(parent_set_list)/member_l
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 清华大学 lingo
限制150内