Lingo and lindo解决运筹学问题

用LINDO、LINGO 和WHATS BEST!解运筹学问题优化模型介绍 实际问题中的优化模型Min/Max z=f(x), x=(x1,.,xn)T s.t. g i(x)0,i=1,2,.,mx1,.,xn0其中 x决策变量， f(x)目标函数， gi(x) 0约束条件数学规划分类：线性规划(LP)二次规划(QP)非线性规划(NLP)连续规划整数规划(IP)：0-1整数规划、一般整数规划、 纯整数规划(PIP)、混合整数规划(MIP)LINDO 公司软件产品简要介绍 美国芝加哥(Chicago)大学的Linus 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)演示(试用)版、学生版、高级版、超级版、工业版、扩展版 （求解问题规模和选件不同）LINDO和LINGO软件能求解的优化模型LINDO：线性规划(LP)、二次规划(QP)LINGO：线性规划(LP)、二次规划(QP)、非线性规划(NLP)建模时需要注意的几个问题 1、尽量使用实数优化，减少整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量的个数 （如x/y 5 改为x5y）4、合理设定变量上下界，尽可能给出变量初始值 5、模型中使用的参数数量级要适当 (如小于103)LINDO使用简介例 加工奶制品的生产计划1桶牛奶（ 经过12小时） 产生3公斤奶制品A ，可获利24元/公斤 或1桶牛奶（ 经过8小时） 产生4公斤奶制品B ， 可获利16元/公斤某天约束：50桶牛奶 、时间480小时 、至多加工100公斤A 如何制定生产计划，使这一天获利最大？一些小问题如下：问1、35元可买到1桶牛奶，买吗？若买，这一天最多买多少?问2、可聘用临时工人，付出的工资最多是每小时几元? 问3、奶制品A的获利增加到 30元/公斤，是否应改变生产计划？ 解：决策变量 用x桶牛奶生产A 用y桶牛奶生产B目标函数 Max z=72 x + 64 y约束条件 x + y 50 (原料供应 ) 12 x+ 8 y 480 (劳动时间 ) 3 x 100 (加工能力,产量约束 ) x, y0 (非负约束 )在LINDO输入窗中输入如下代码：max 72 x+64 yst2) x+y503) 12x+8y4804) 3x72x+8y64end影子价格 :最优解下“资源”增加1单位时“效益”的增量 原料增1单位(桶), 利润增48 (3360=3408,20,30=18,33)时间加1单位, 利润增2 能力增减不影响利润35元可买到1桶牛奶，要买吗？35 48, 应该买！聘用临时工人付出的工资最多每小时几元？2元！DO RANGE(SENSITIVITY) ANALYSIS? Yes RANGES IN WHICH THE BASIS IS UNCHANGED:基不变时目标系数允许变化范围 (约束条件不变)（意味着生产计划不变或变化不大，而最优目标值要改变？） OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X 72.000000 24.000000 8.000000 x系数范围64,96 Y 64.000000 8.000000 16.000000y系数范围48,72 A获利增加到 30元/千克（90元/桶），应否改变生产计划？不变！ RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 原料最多增加10 3 480.000000 53.333332 80.000000 时间最多增加53 4 100.000000 INFINITY 40.00000035元可买到1桶牛奶，每天最多买多少？最多买10桶？（多于10桶意味着基要发生改变，亦即生产计划要发生较大变化！）若在代码行“end”后定义整型变量或0/1型变量，则可求解整数规划问题了。定义形式为： int int 0/1型gin gin 整型使用LINDO的一些注意事项1.“”（或“=”（或“=”）功能相同2.变量与系数间可有空格(甚至回车), 但无运算符3.变量名以字母开头，不能超过8个字符4.变量名不区分大小写（包括LINDO中的关键字）5.目标函数所在行是第一行，第二行起为约束条件6.行号(行名)自动产生或人为定义。行名以“）”结束7.行中注有“!”符号的后面部分为注释。如: ! Its Comment.8.在模型的任何地方都可以用“TITLE” 对模型命名（最多72个字符），如： TITLE This Model is my first Example9.变量不能出现在一个约束条件的右端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 nameLINGO软件简介LINGO模型的优点包含了LINDO的全部功能提供了灵活的编程语言（矩阵生成器）LINGO模型的构成：4个段目标与约束段集合段（SETS ENDSETS）数据段（DATA ENDDATA）初始段（INIT ENDINIT）阅读如下代码：代码1：model:!可省略;max=2*x1+3*x2;4*x1+3*x2=10;3*x1+5*x2=12;end !可省略;代码2：model : sets: xx/1.1/:x,y; !集合名称为xx; endsets max=sum(xx:2*x+3*y); for(xx(i):4*x(i)+3*y(i)=10); for(xx(i):3*x(i)+5*y(i)=12);end代码3：model : sets: xx/1.2/ :x,c,d,e ; endsets max=sum(xx:c*x);sum(xx:d*x)=10;sum(xx:e*x)=12; data: c=2 3; d=4 3; e=3 5; enddataend代码4：model: sets: xx/1.2/:x; endsets max=2*x(1)+3*x(2);4*x(1)+3*x(2)=10;3*x(1)+5*x(2)=20; !周1雇员数;s1+s2+s5+s6+s7=16; !周2雇员数;s1+s2+s3+s6+s7=13; !周3雇员数;s1+s2+s3+s4+s7=16; !周4雇员数;s1+s2+s3+s4+s5=19; !周5雇员数;s2+s3+s4+s5+s6=14; !周6雇员数;s3+s4+s5+s6+s7=12; !周7雇员数;ENDSETSDATA: REQUIRED = 20 16 13 16 19 14 12;ENDDATAMIN = SUM( DAYS( I): START( I);FOR( DAYS( J): SUM( DAYS( I) | I #LE# 5: START( WRAP( J - I + 1, 7) = REQUIRED( J);END优化问题是：邮局一周中每天需要不同数目的雇员，设周一至少20人，周二至少16人，.，周日至少12人，又规定应聘者需连续工作5天，问邮局每天聘多少雇员才能既满足需求，又使聘用总人数最少。五个基本的组成部分：1变量定义；2数据输入；3目标函数；4约束；5变量取值范围。常见内部函数：集合定义：setname/member list(or 1.n)/:attribute,attribute,etc. setname(set1,set2,etc.): attribute,attribute,etc.集合基本集合直接列举法 隐式列举法派生集合 稠密集合稀疏集合 元素列表法 元素过滤法 e.gSETS: CITIES /A1,A2,A3,B1,B2/; ROADS(CITIES, CITIES)/ A1,B1 A1,B2 A2,B1 A3,B2/:D; ENDSETSSETS: STUDENTS /S1.S8/; PAIRS( STUDENTS, STUDENTS) | &2 #GT# &1: BENEFIT, MATCH;ENDSETS集合元素的隐式列举OCT2001, NOV2001, DEC2001, JAN2002OCT2001.JAN2002monthYearM.monthYearN年份-月份型OCT, NOV, DEC, JANOCT.JANmonthM.monthN月份型MON, TUE, WED, THU, FRIMON.FRIdayM.dayN星期型Car101, car102, , car208Car101.car208stringM.stringN字符-数字型1, 2, 3, 4, 51.51.n数字型示例集合的元素示例隐式列举格式类型集合函数：set_operator(set_name|condition:expression) set_operator:集合函数名 set_name:数据集合名 expression:表达式 |condition:条件 #AND#(与),#OR#(或),#NOT#(非) #EQ#(等于),#NE#(不等于),#GT#(大于),#GE#(大于等于), #LT#(小于),#LE#(小于等于)Max(set_name:expression) 返回集合上的表达式的最大值Min(set_name:expression) 返回集合上的表达式的最小值Sum(set_name:expression) 返回集合上的表达式的和For(set_name:constraint_expression) 对集合（set_name）的每个元素独立地生成约束，约束由约束表达式（constraint_expression）描述。变量界定函数：BND(L,X,U) 限制 L=X1.1x+y=1y1.1;x+y=1;y0.7;end例：用LINGO解决非线性问题model : max=sin(x);x3.14;init x=2;endinitend值得注意的是：LINGO 8.0 提供了LINGO.DLL文件可在VB 或VC+等集成开发环境中调用。且有示例参考，为同一模型不同数据而得出的不同结果进行比较这一类问题提供了解决方案。WhatsBest!介绍首先安装WhatsBest!，再打开MS Excel 可看见多了菜单栏 “WB!”和模型求解工具栏上述例子在Whats