优化模型与LINDO LINGO 软件

优化模型与LINDO LINGO 软件 优化模型与LINDO / LINGO 软件谢金星清华大学数学科学系 提要??LINDO公司的主要软件产品及功能简介??LINDO软件的使用简介??LINGO软件的使用简介??建模与求解实例 优化模型T实际问题中Min(或Max)z=f(x),x=(x,Lx)1n的优化模型s.t.g(x)?0,i=1,2,Lmig(x)?0~约束条件x~决策变量f(x)~目标函数i数学规划线性规划(LP)0-1整数规划纯整数规划(PIP)二次规划(QP)混合整数规划(MIP)一般整数规划非线性规划(NLP)整数规划(IP)连续规划 LINDO 公司软件产品简要介绍美国芝加哥(Chicago)大学的LinusSchrage教授于1980年前后开发, 后来成立LINDO系统公司(LINDO Systems Inc.)，网址://.lindo.comLINDO: Linear INteractiveand Discrete Optimizer (V6.1)LINGO: Linear INteractiveGeneral Optimizer (V8.0)LINDO API: LINDO Application Programming Interface (V2.0)What’s Best!: (SpreadSheete.g. EXCEL) (V7.0)演示(试用)版、学生版、高级版、超级版、工业版、扩展版„(求解问题规模和选件不同) LINDO和LINGO软件能求解的优化模型优化模型连续优化整数规划(IP)线性规划二次规划非线性规划(LP)(QP)(NLP)LINDOLINGO LINDO/LINGO软件的求解过程1、确定常数LINDO/LINGO预处理程序2、识 别类型LP QP NLP IP 全局优化(选)分枝定界管理程序ILP INLPIQP线性优化求解程序非线性优化求解程序1、顺序线性规划法(Sequential Linear Programming, SLP)2、广义既约梯度法(Generalized 1、单纯形算法Reduced Gradient, GRG)(选)2、内点算法(选)3、多点搜索(Multistart)(选) 建模时需要注意的几个基本问题1、尽量使用实数优化模型，减少整数约束和整数变量的个数2、尽量使用光滑优化模型，减少非光滑约束的个数如:尽量少地使用绝对值函数(|x|)、符号函数(当变量x为正数时取1，为0时取0，为-1时取-1)、多个变量求最大(或最小)值、四舍五入函数、取整函数等3、尽量使用线性优化模型，减少非线性约束和非线性变量的个数(如x/y<5 改为x<5y)4、合理设定变量的上下界，尽可能给出变量的初始值35、模型中使用的单位的数量级要适当(如小于10) 需要掌握的几个重要方面1、LINDO:正确阅读求解报告(尤其要掌握敏感性 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 )2、LINGO:掌握集合(SETS)的应用;正确阅读求解报告;正确理解求解状态窗口;学会设置基本的求解选项(OPTIONS) ;掌握与外部文件的基本接口 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 例1 加工奶制品的生产计划3公斤A获利24元/公斤11桶12小时或牛奶获利16元/公斤4公斤A28小时50桶牛奶时间480小时至多加工100公斤A每天:1制订生产计划，使每天获利最大??35元可买到1桶牛奶，买吗,若买，每天最多买多少???可聘用临时工人，付出的工资最多是每小时几元? ??A的获利增加到30元/公斤，应否改变生产计划,1 3公斤A获利24元/公斤11桶12小时或牛奶获利16元/公斤4公斤A28小 时50桶牛奶时间480小时至多加工100公斤A每天1x桶牛奶生产Ax桶牛奶生 产A决策变量1122获利24×3x获利16×4x目标函数12Maxz=72x+64x每天获利 12线性x+x?50原料供应12规划12x+8x?480劳动时间12模型约束条件3x? 100(LP)加工能力1x,x?012非负约束 LINDO 6.1模型求解Milk01.ltx软件实现OBJECTIVE FUNCTION VALUEmax 72x1+64x21) 3360.000stVARIABLE VALUEREDUCED COST2) x1+x2<50X1 20.0000000.0000003)12x1+8x2<480X2 30.0000000.0000004)3x1<100ROW SLACK OR SURPLUS DUAL PRICESend2) 0.000000 48.0000003) 0.000000 2.000000DO RANGE 4) 40.000000 0.000000(SENSITIVITY) NoNO. ITERATIONS= 2ANALYSIS? 20桶牛奶生产 A, 30桶生产A，利润3360元。12 模型求解reduced cost值 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 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 PRICESmax型问题)2) 0.000000 48.000000也可理解为:3) 0.000000 2.0000004) 40.000000 0.000000为了使该非基 变NO. ITERATIONS= 2量变成基变量，目标函数中对应系数应增加的量 结果解释OBJECTIVE FUNCTION VALUEmax 72x1+64x21) 3360.000stVARIABLE VALUE REDUCED COST2)x1+x2<50X1 20.000000 0.0000003)12x1+8x2<480X2 30.000000 0.0000004)3x1<100ROWSLACK OR SURPLUSDUAL PRICESend2) 0.00000048.000000原料无剩余三3) 0.0000002.000000种时间无剩余4) 40.0000000.000000资加工能力 剩余40NO. ITERATIONS= 2源“资源”剩余为零的约束为紧约束(有效约 束) OBJECTIVE FUNCTION VALUE结果解释1) 3360.000最优解下“资源” 增加1VARIABLE VALUE REDUCED COST单位时“效益”的增量 X1 20.000000 0.000000X2 30.000000 0.000000影子价格ROW SLACK OR SURPLUS DUAL PRICES2)0.000000 48.000000原料增加1单位, 利润增长48 3)0.000000 2.000000时间增加1单位, 利润增长2 4)40.000000 0.000000加工能力增长不影响利润NO. ITERATIONS= 235 <48, 应该 买～??35元可买到1桶牛奶，要买吗,??聘用临时工人付出的工资最多每小时 几元,2元～ DO RANGE(SENSITIVITY) ANALYSIS?Yes最优解不变时目标函RANGES IN WHICH THE BASIS IS UNCHANGED:数系数允许变化范围OBJ COEFFICIENT RANGES(约束条件不变)VARIABLE CURRENT ALLOWABLE ALLOWABLECOEF INCREASE DECREASEx系数范围(64,96)X1 72.000000 24.000000 8.0000001X2 64.000000 8.000000 16.000000x系数范围(48,72) 2RIGHTHAND SIDE RANGESROW CURRENT ALLOWABLE ALLOWABLERHS INCREASE DECREASEx系数由24 ×3=7212 50.000000 10.000000 6.666667增加为30×3=90，3 480.000000 53.333332 80.000000在允许范围内4 100.000000 INFINITY 40.000000不变～??A获利增加到30元/千克，应否改变生产计划1 结果解释影子价格有意义时约束右端的允许变化范围RANGES IN WHICH THE BASIS IS UNCHANGED:(目标函数不变)OBJ COEFFICIENT RANGESVARIABLE CURRENT ALLOWABLE ALLOWABLECOEF INCREASE DECREASEX1 72.000000 24.000000 8.000000X2 64.000000 8.000000 16.000000RIGHTHAND SIDE RANGESROW CURRENT ALLOWABLE ALLOWABLERHS INCREASE DECREASE原料 最多增加10 2 50.000000 10.000000 6.6666673 480.000000 53.333332 80.000000时间最多增加53 4 100.000000 INFINITY 40.000000最多买10桶,??35元可买到1桶牛奶，每天最多买多少, LINDO的一些注意事项(1)1.“>”(或“<”)号与“>=”(或“<=”) 功能相同2.变量与系数间可有空格(甚至回车), 但无运算符3.变量名以字母开 头，不能超过8个字符4.变量名不区分大小写(包括LINDO中的关键字)5.目 标函数所在行是第一行，第二行起为约束条件6.行号(行名)自动产生或人为定 义。行名以“)”结束7.行中注有“!”符号的后面部分为注释。如: ! It’s Comment.8.在模型的任何地方都可以用“TITLE”对模型命名(最多72个字符)， 如:TITLE This Model is only an Example LINDO的一些注意事项(2)9.变量不能出现在一个约束条件的右端10.表达 式中不接受括号“( )”和逗号“,”等任何符号, 例: 400(X1+X2)需写为 400X1+400X211.表达式应化简，如2X1+3X2-4X1应写成-2X1+3X212.缺省假定所有变量非负;可在模型的“END”语句后用“FREE name”将变量name的非负假定取消13.可在“END”后用“SUB”或“SLB”设定变量上下界例如:“sub x1 10”的作用等价于“x1<=10”但用“SUB”和“SLB”表示的上下界约束不计入模型的约束，也不能给出其松紧判断和敏感性分析。14.“END”后对0-1变量说明:INT n或INT name15.“END”后对整数变量说明:GIN n或GIN name 二次规划(QP)问题??LINDO可求解二次规划(QP)问题，但输入方式较复杂，因为在LINDO中不许出现非线性表达式??需要为每一个实际约束增加一个对偶变量(LAGRANGE乘子)，在实际约束前增加有关变量的一阶最优条件，转化为互补问题??“END”后面使用QCP命令指明实际约束开始的行号，然后才能求解??建议总是用LINGO解QP[注意]对QP和IP: 敏感性分析意义不大 ??当前状态:已经达到最优解??迭代次状态窗口(LINDO Solver Status) 数:18次??约束不满足的量(不是“个数”):0??当前的目标值:94??最好的整数解:94??整数规划的界:93.5??分枝数:1??所用时间:0.00秒(太快了，还不到0.005秒)??刷新本界面的时间间隔:1(秒) 选项设置??Preprocess:预处理(生成割平面);??Preferred Branch:优先的分枝方式:Nonzero Limit:“Default”(缺省方式)、非零系数的个数上限;“Up”(向上取整优先)、“Down”(向下取整优先);Iteration Limit:??IP Optimality Tol:IP最优值允许的误差最大迭代步数;上限(一个百分数，如5%即0.05);Initial ContraintTol:??IP Objective Hurdle:IP目标函数的篱笆约束的初始误差上限;Final ContraintTol:值，即只寻找比这个值更优最优解(如当知道当前模型的某个整数可行解时，约束的最后误差上限;Entering VarTol:就可以设置这个值);??IP VarFixing Tol:固定一个整数变量取进基 变量的REDUCED COST的误差限;值所依据的一个上限(如果一个整数变量的判 别数(REDUCED COST)的值很Pivot Size Tol:大，超过该上限，则以后求解 中把该整旋转元的误差限数变量固定下来)。 Report/StatisticsROWS= 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 VALUE= 0.300000 277.000OBJ=MIN, NO. <,=,>: 2 0 2, GUBS <= 1 VUBS >= 0SINGLE COLS= 0 REDUNDANT COLS= 0第一行:模型有5行(约束4行)，4个变量，两个整数变量(没有0-1变量)， 从第4行开始是二次规划的实际约束。第二行:非零系数19个，约束中非零系 数12个(其中6个为1或-1)，模型密度为0.760(密度=非零系数/[行数,(变量 数，,)])。第三行的意思:按绝对值看，系数最小、最大分别为0.3和277。 第四行的意思:模型目标为极小化;小于等于、等于、大于等于约束分别有,、 ,、,个;广义上界约束(GUBS)不超过,个;变量上界约束(VUBS)不少于, 个。所谓GUBS，是指一组不含有相同变量的约束;所谓VUBS，是指一个蕴涵变 量上界的约束，如从约束X1+X2-X3=0可以看出，若X3=0，则X1=0，X2=0(因为 有非负限制)，因此X1+X2-X3=0是一个VUBS约束。第五行的意思:只含,个变 量的约束个数=,个;冗余的列数=,个 LINDO行命令、命令脚本文件WINDOWS环境下行命令的意义不大批处理:可 以采用命令脚本(行命令序列)Example 演示Bat01.txtModel01.ltx LINGO模型—例:选址问题某公司有6个建筑工地，位置坐标为(a, b) (单 位:公里),ii水泥日用量d(单位:吨)ii,,,,,,假设:料场a1.258.750.55.7537.25和工地之间b1.250.754.7556.57.75d371有直线道路1)现有2料场，位于A (5, 1), B (2, 7),记(x,y),j=1,2, 日储量e各有20吨。jjj目标:制定每天的供应计划，即从A, B两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。 26决策变量:cij221/2minc[(x??a)+(y??b)]ijjiji??(料场j到工地i的j=1i=1运量)~12维2s.t.c=d,i=1,...,6iji?线性规划模型j=16c?e,j=1,2ijj?i=1123456i用例中数350701Ac(料场)i1据计算，0040610Bc(料场)最优解为i2总吨公里数为136.2 选址问题:NLP2)改建两个新料场，需要确定新料场位置(x,y)和jj运量c，在其它条件不变下使总吨公里数最小。ij26221/2minc[(x??a)+(y??b)]ijjiji j=1非线决策变量:??j=1i=1c(x,y)~16维ij，jj2s.t.c=d,i=1,...,6iji?性规划模型6c?e,j=1,2ijj?i=1 LINGO模型的构成:4个段集合段(SETS ENDSETS)数据段(DATA ENDDATA)LP:移到数据段初始段(INIT ENDINIT)目标与约束段局部最优:89.8835(吨公里) 边界 集合的类型setname(parent_set_list) setname[/member_list/] [/member_list/] [: attribute_list];集合[: attribute_list];派生集合基本集合稀疏集合稠密集合元素列表法元素过滤法直接列举法隐式列举法 SETS:SETS:CITIES /A1,A2,A3,B1,B2/;STUDENTS /S1..S8/;ROADS(CITIES, CITIES)/PAIRS( STUDENTS, STUDENTS) | A1,B1 A1,B2 A2,B1 A3,B2/:D; &2 #GT# &1: BENEFIT, MATCH;ENDSETSENDSETS 集合元素的隐式列举类型隐式列举格式示例示例集合的元素1..n1..51, 2, 3, 4, 5数字型字符-stringM..stringNCar101..car208Car101, car102, „, car208数字型dayM..dayNMON..FRIMON, TUE, WED, 星期型THU, FRImonthM..monthNOCT..JANOCT, NOV, DEC, 月份型JAN年份 -monthYearM..moOCT2001..JANOCT2001, nthYearN2002NOV2001, 月份型 DEC2001, JAN2002 运算符的优先级三类运算符:算术运算符逻辑运算符关系运算符优先级运算 符最高#NOT# —(负号)^* /+ —(减法)#EQ# #NE# #GT# #GE# #LT# #LE# #AND# #OR#最低<(=) = >(=) 集合循环函数四个集合循环函数:FOR、SUM 、MAX、 MIN@function( setname[ ( set_index_list)[ | condition]] : expression_list);Example:[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)); Model Class:状态窗口LP，QP，ILP，IQP，PILP, PIQP，NLP，INLP，PINLP State:??Global Optimum??Local Optimum??Feasible??Infeasible??Unbounded??Interrupted??UndeterminedSolver Type:??B-and-B??Global ??Multistart 7个选项卡(可设置80-90个控制参数) 使用外部数据文件??Cut (or Copy) –Paste 方法??@FILE函数输入数据、 @TEXT函数输出数据(文本文件)??@OLE函数与电子表格软件(如EXCEL)连 接??@ODBC函数与数据库连接程序与数据分离??LINGO命令脚本文件常用文件后 缀??LG4 (LONGO模型文件)文??LNG (LONGO模型文件)本??LTF (LONGO脚 本文件)文??LDT (LONGO数据文件)件??LRP (LONGO报告文件) @FILE和@TEXT:文本文件输入输出MODEL:SETS:myfile.txt文件的 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 、 格式:MYSET / @FILE(‘myfile.txt’) / : @FILE(‘myfile.txt’);Seattle,Detroit,Chicago,Denver~ENDSETSCOST,NEED,SUPPLY,SHIP~MIN = @SUM( MYSET( I):SHIP( I) * COST( I));12,28,15,20~@FOR( MYSET( I): 1600,1800,1200,1000~[CON1] SHIP( I) > NEED( I);1700,1900,1300,1100[CON2] SHIP( I) < SUPPLY( I));DATA:COST = @FILE(‘myfile.txt’);NEED = @FILE(‘myfile.txt’);SUPPLY = @FILE(‘myfile.txt’);@TEXT(‘result.txt’)=SHIP, @DUAL(SHIP), @DUAL(CON1);ENDDATAEND @OLE :与EXCEL连接MODEL:SETS:MYSET / @OLE(‘mydata.xls’,’CITIES’) / : @OLE(‘mydata.xls’, ‘ATTR’);ENDSETSMIN = @SUM( MYSET( I): SHIP( I) * COST( I));@FOR( MYSET( I): mydata.xls文件中必须有[CON1] SHIP( I) > NEED( I);下列名称(及数据):[CON2] SHIP( I) < SUPPLY( I));CITIES，ATTR，DATA:COST，NEED，COST,NEED,SUPPLY = @OLE(‘mydata.xls’);@(‘mydata.xls’,’SOLUTION’)=SHIP; SUPPLY，SOLUTIONENDDATAEND??在EXCEL中还可以通过“宏”自动调用LINGO??也可以将EXCEL表格嵌入到LINGO模型中 @ODBC :与数据库连接使用数据库之前，数据源需要在ODBC管理器注册目前支持下列DBMS: (如为其他数据库，则需自行安装驱动)ACCESS，DBASE，EXCEL，FOXPRO，ORACLE，PARADOX，SQL SERVER，TEXE FILES输入基本集合元素:setname/@ODBC([‘datasource’[, ‘tablename’[, ‘columnname’]]])/输入派生集合元素:setname/@ODBC([‘source’[,‘table’[, ‘column1’[, ‘column2’„]]]])/输入数据:Attr_list=@ODBC([‘source’[,‘table’[, ‘column1’[, ‘column2’„]]]])输出数据:@ODBC([‘source’[,‘table’[, ‘column1’[, ‘column2’„]]]])= Attr_list 建模例子露天矿生产的车辆安排(CUMCM-2003B)露天矿里铲位已分成矿石和岩石: 平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量(称为品位)都是已知的。每个铲位至多安置一台电铲，电铲平均装车时间5分钟矿石卸点需要的铁含量要求都为29.5%!1%(品位限制)，搭配量在一个班次(8小时)内满足品位限制即可。卸点在一个班次内不变。卡车载重量为154吨，平均时速28km,平均卸车时间为3分钟。卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。问题:出动几台电铲，分别在哪些铲位上;出动几辆卡车，分别在哪些路线上各运输多少次? 平面示意图 问题数据距离铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位105.265.194.214.002.952.742.461.900.641.27矿石漏1.900.991.901.131.272.251.482.07><43.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铲位100(951(051(001(051(101(251(051(301(351(25矿石量1(251(101(351(051(151(351(051(151(351(25岩石量30%28%29%32%31%33%32%31%33%31%铁含量 问题分析与典型的运输问题明显有以下不同:1.这是运输矿石与岩石两种物资的问题;2.属于产量大于销量的不平衡运输问题;3.为了完成品位约束，矿石要搭配运输;4.产地、销地均有单位时间的流量限制;5.运输车辆只有一种，每次满载运输，154吨/车次;6.铲位数多于铲车数意味着要最优的选择不多于7个产地作为最后结果中的产地;7.最后求出各条路线上的派出车辆数及安排。近似处理:??先求出产位、卸点每条线路上的运输量(MIP模型)??然后求出各条路线上的派出车辆数及安排 模型假设??卡车在一个班次中不应发生等待或熄火后再启动的情况;??在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论;??空载与重载的速度都是28km/h，耗油相差很大;??卡车可提前退出系统，等等。如理解为严格不等待，难以用数学规划模型来解个别参数队找到了可行解(略) 符号??x:从i铲位到j号卸点的石料运量(车)单位:吨;ij??c:从i号铲位到j号卸点的距离公里;ij??T:从i号铲位到号j卸点路线上运行一个周期平均时间分;ij??A:从号铲位到号卸点最多能同时运行的卡车数辆;ij??B:从号铲位到号卸点路线上一辆车最多可运行的次数次;ij??p:i号铲位的矿石铁含量p=(30,28,29,32,31,33,32,31,33,31) %i??q: j号卸点任务需求，q=(1.2,1.3,1.3,1.9,1.3)*10000 吨j??ck:i号铲位的铁矿石储量万吨i??cy:i号铲位的岩石储量万吨i??f:描述第i号铲位是否使用的0-1变量，取1为使用;0为关闭。iT????ij????8×60,(A??1)×5i到j距离×2ijA=T=，3，5B=ij????????ijij(近似)平均速度5T????????ij???? 105优化模型min×??xcijiji=1j=1(1)道路能力(卡车数)约束?×,i=1,L,10,j=1,L,5xABijijij5(2)电铲能力约束?×8×60/5,i=1,L,10f?xijij=110?(3)卸点能力约束8×20,j=1,L,5?xiji=1++?×10000/154xxxcki1i2i5i(4)铲位储量约束,i=1,L,10+?×10000/154cyxxi3i4i10(5)产量任务约束?/154,j=1,L,5q?xijji=110(6)铁含量约束??×(??30.5)?0p?x??iji.??i=1,j=1,2,5??10??(7)电铲数量约束×(??28.5)?0p?xiji??i=1??10x为非负整数(8)整数约束?7ijf?ii=1f为0-1整数i 计算结果(LINGO软件)铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿漏135411倒?42<43岩场7015岩漏81<43倒?13270铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位100.8671.8620.314矿石漏1.0771.162倒场?1.8920.326岩场1.8411.229岩石漏0.6840.11.489倒场? 计算结果(派车)铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位101 (29)矿石漏1 (39)1 (37)倒场?1 (37)岩场1(44)1 (35)岩石漏1 (47)倒场?此外:6辆联合派车( 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 略)结论:铲位1、2、3、4、8、9、10处各放置一台电铲。一共使用了13辆卡车;总运量为85628.62吨公里;岩石产量为32186吨;矿石产量为38192吨。 最大化产量目标函数变化此外:车辆数量(20辆)限制(其实上面的模型也应该有)结论:(略) 其他优化赛题飞行管理问题西气东送问题等等 Thank you for your attendance!最后，祝大家在数学建模活动中不断提高综合素质，在数学建模竞赛中取得更好的成绩～That’s all. Any Questions?