LINGO在数学建模中的应用.doc

-作者xxxx-日期xxxxLINGO在数学建模中的应用【精品文档】一、LINGO简介LINGO是美国LINDO系统公司开发的求解数学规划系列软件中你的一个,它的主要功能是求解大型线性、非线性和整数规划问题,LINGO的不同版本对模型的变量总数、非线性变量数目、整型变量数目和约束条件的数量做出不同的限制.LINGO的主要功能特色为:(1)既能求解线性规划问题,也有较强的求解非线性规划问题的能力;(2)输入模型简练直观;(3)运行速度快、计算能力强. (4)内置建模语言,提供几十个内部函数,从而能以较少语句,较直观的方式描述较大规模的优化模型;(5)将集合的概念引入编程语言,很容易将实际问题转换为LINGO模型;(6)能方便地与EXCEL、数据库等其他软件交换数据.LINGO像其他软件一样,对他的语法有规定,LINGO的语法规定如下:（1） 求目标函数的最大值或最小值分别用MAX=或MIN=来表示;(2) 每个语句必须以字母开头,由字母、数字和下划线所组成,昌都不超过32个字符,不区分大小写;(3)每个语句必须以分号“;”结束,每行可以有多个语句,语句可以跨行;(4)如果对变量的取值范围没有特殊说明,则默认所有决策变量都非负;(5)LINGO模型以语句“MODEL”开头,以语句“END”结束,对于比较简单的模型,这这两个语句可以省略.LINGO提供了五十几个内部函数,使用这些函数可以大大减少编程工作量,这些函数都是以字符开头,下面简单介绍其中的集合操作函数和变量定界函数及用法.集合是LINGO建模语言中最重要的概念,使用集合操作函数能够实现强大的功能,LINGO提供的常用集合操作函数有FOR(s:e)、SUM(s:e)、MAX(s:e)、MIN(s:e)等.FOR(s:e)常用在约束条件中,表示对集合s中的每个成员都生成一个约束条件表达式,表达式的具体形式由参数e描述;SUM(s:e) 表示对集合s中的每个成员,分别得到表达式e的值,然后返回所有这些值的和;MAX(s:e) 表示对集合s中的每个成员,分别得到表达式e的值,然后返回所有这些值中的最大值;MIN(s:e) 表示对集合s中的每个成员,分别得到表达式e的值,然后返回所有这些值中的最小值.LINGO默认变量的取值可以从零到正无穷大,变量定界函数可以改变默认状态,如对整数规划,限定变量取整数,对0-1规划,:BIN(X)、BND(L,X,U)、GIN(X)、FREE(X).BIN(X)限定X为0或1,在0-1规划中特别有用;GIN(X)限定X为整数,在整数规划中特别有用;BND(L,X,U)限定LXU,可用作约束条件;FREE(X)取消对X的限定,即X可以取任意实数.二、LINGO在线性规划中的应用 具有下列三个特征的问题称为线性规划问题(Linear program)简称LP问题,其数学模型称为线性规划(LP)模型.线性规划问题数学模型的一般形式为:求一组变量的值,使其满足式中“*”代表“”、“ ”或“=”.上述模型可简写为 其中,变量称为决策变量,函数称为目标函数,条件称为约束条件, 称为非负约束.在经济问题中,又称为价值系数,为资源限量. 线性规划在科学决策与经营管理中实效明显,但是对于规模较大的线性模型,其求解过程非常繁琐,不易得出结果.而 LINGO中的内部集合函数有FOR(s:e)、SUM(s:e)、MAX(s:e)、MIN(s:e)等,可以用这些集合函数使程序编程简单可行,下面举例说明.例1 某工厂有两条生产线,分别用来生产M和P两种型号的产品,利润分别为200元每个和300元每个,生产线的最大生产能力分别为每日100和120,生产线没生产一个M产品需要1个劳动日(1个工人工作8小时称为1个劳动日)进行调试、检测等工作,而每个P产品需要2个劳动日,该工厂每天共计能提供160个劳动日,假如原材料等其他条件不受限制,问应如何安排生产计划,才能使获得的利润最大？解 设两种产品的生产量分别为和,则该问题的数学模型为: 目标函数 约束条件 编写LINGO程序如下:MODEL:SETS:SHC/1,2 /:A,B,C,X; YF/1,2,3 /:J;ENDSETSDATA:A=1,2 ; B=100,120; C=200,300; ENDDATAMAX=SUM(SHC:C*X);FOR(SHC(I):X(I)<B(I); SUM(SHC(I):A(I)*X(I)<=160;END 程序运行结果如下Global optimal solution found. Total solver iterations: 0Variable Value Reduced CostA( 1) 1.000000 Row Slack or Surplus Dual Price 1 29000.00 最优解为最优值为.即每天生产100个M产品30个P产品,可获得29000元利润.三、LINGO在整数规划和0-1规划中的应用1 求解整数规划整数规划分为整数规划和混合整数规划,要求全部变量都为非负整数的数学规划称为纯整数规划,只要求部分变量为非负整数的数学规划称为混合整数规划.下面只讨论约束条件和目标函数均为线性的整数规划问题,即整数线性规划问题(以下简称整数规划,记为ILP),其数学模型的一般形式是, 且称线性规划问题 为整数规划问题的松弛问题. 显然,整数规划的可行域是其松弛问题的可行域的一个子集.如果线性规划的最优解为,相应的规划规划的最优解为,则必然有.LINGO的内部函数GIN(X)是限定X为整数,因此,LINGO对整数规划的求解是可行的.下面举例说明:例2 某疗养院营养师要为某类病人拟订本周蔬菜类菜单,当前可供选择的蔬菜品种、价格和营养成分含量,以及病人所需养分的最低数量见表1,病人1周需14份蔬菜,为了口味的原因,规定每周内的卷心菜不多于2份,胡萝卜不多于3份,其他蔬菜不多于4份且至少1份.在满足要求的前提下,制定费用最少的一周菜单方案. 表1 可供蔬菜养分含量和价格养分蔬菜 每份蔬菜所含养分数量每份价格(元) 铁 磷维生素A维生素C烟酸 锌A1青豆 20 415 22A2萝卜 28 4065 5A3花菜 40 850 43A4卷心菜0.4 25 75 27A5芹菜 26 76 48A6土 豆 75 235 8A7红柿 45 240 20 每周最低需求 8 180 19800 450 7 4解 用表示7种蔬菜的份数,表示蔬菜单价,表示每周最低营养需求,表示第种蔬菜的第种养分含量,建立如下整数规划模型 LINGO程序如下:MODEL:SETS:SHC/1 2 3 4 5 6 7/:AI,X; YF/1 2 3 4 5 6/:BJ;JIAGE(SHC,YF):C;ENDSETSDATA:AI=2 1 1.8 1.2 2.0 1.2 1.5; BJ=7 140 14800 400 7 4; 0.45 28 4065 0.6 45 240 20 0.2 0.25;ENDDATAMIN=SUM(SHC:AI*X);FOR(SHC(I):GIN(X(I); FOR(SHC(I):X(I)>=1); SUM(SHC(I):X(I)=21;X(2)<=3; X(3)<=2;FOR(SHC(I)|I #NE# 2 #AND# I #NE# 4:X(I)<=4);FOR(YF(J):SUM(SHC(I):X(I)*C(I,J)>=BJ(J);ENDGlobal optimal solution found. Extended solver steps: 0 Total solver iterations: 6Variable Value Reduced CostX( X( X( X( X( X( X( 当时,目标函数最小,.2求解0-1规划 在整数规划中,当对变量的限定为变量的值只能取整数值时,我们把整数规划称为0-1规划,0-1规划化为以下标准形式:,任意0-1规划模型如何化为标准形式: (1)如果目标函数是求最小值,则对目标函数两边乘以-1,变为求最大值;(2)如果目标函数中某变量的系数,则令替换为0-1变量,于是变量在目标函数中的系数变成小于0;(3)如果约束条件是“”形式,则可两边乘以-1,变为“”形式;(4)如果约束条件中含有等式,则可将每个等式化为两个“”形式的不等式.LINGO内部函数BIN(X)的作用是限定X为0或1,因此,LINGO对整数规划的求解是可行的.下面举例说明:例3 分配六个人去完成6项任务,每人完成一项,每项任务只能由一人去完成,六个人分别完成各项任务的效益如下表所示,试做出任务分配使效益最大. 各人完成各项任务的效益 任务人员A B C D E F 1 2 3 4 5 6 20 15 16 5 4 7 17 15 33 12 8 6 9 12 18 16 30 13 12 8 11 27 19 14 - 7 10 21 10 32 - - - 6 11 13解 用表示第个人是否完成第项任务,当表示第个人完成第项任务,第个人不完成第项任务,用表示第个人完成第项任务的效率模型建立如下:编写程序如下:MODEL:SETS: RENWU/1,2,3,4,5,6/; MEN/1,2,3,4,5,6/;WCHRW(MEN,RENWU):C,x;ENDSETSDATA:C=20,15,16,5,4,7 17,15,33,12,8,6 9,12,18,16,30,13 12,8,11,27,19,14 0,7,10,21,10,32 0,0,0,6,11,13;ENDDATAMAX=SUM(WCHRW(I,J):C*X);FOR(WCHRW(I,J):BIN(X(I,J);FOR(MEN(I):SUM(RENWU(J):X(I,J)=1); FOR(RENWU(J):SUM(MEN(I):X(I,J)=1);ENDGlobal optimal solution found. Extended solver steps: 0 Total solver iterations: 0当,时,142.即第一个人完成第一项任务,第二个人完成第二项任务,第三个人完成第三项任务,第四个人完成第四项任务,第五个人完成第五项任务,第六个人完成第六项任务时,效率最高.四 LINGO在多目标规划中的应用多目标规划的解法通常是根据问题的实际背景和特征,设法将多目标规划转化为单目标规划,从而获得满意解.常用的解法有:,把次要目标作为约束条件并设定适当界限值. ,且,然后把作为新的目标函数(其中,是原来的个目标).是原来的个目标,令,其中为指数加权,把Z作为新的目标函数.(4)理想点法.先分别求出个单目标规划的最优解,令,然后把它作为新的目标函数.(5)分层序列法.将所有个目标按其重要程度排序,先找出第一个最重要的目标的最优解,然后在保证前一个目标最优解的前提下,依次求下一个目标的最优解,一直求到最后一个目标为止.这些方法各有其优点和适用的场合,但并非总是有效,有些方法存在一些不足之处,例如,线性加权求和法确定权重系数时有一定主观性,权重系数取值不同,结果也就不一样;线性加权求和法,指数加权乘积法和理想点法通常只能用在两个目标的单位(量纲)相同的情况,如投资时希望收益要大、风险要小,这是双目标规划,若收益和风险的物理单位(元或百分比)相同,可以考虑用线性加权求和法、指数加权乘积法或理想点法把它们组合起来,化双目标规划为点目标规划.如果两个目标是不同的物理量,它们的量纲不相同,数量级相差很大,将它们相加或比较是不合适的,如火箭弹射程的单位是米或千米,且数量级比较大,而射击精度通常用样本方差来表示,其量纲是平方米,且数量级小,将两者比较、相加或者求理想点是没有有意义的.下面介绍一个双目标规划的例子.例 4 某工厂有工人300名,生产A,B,C,D四种产品,要求每人每周工作时间在20-48小时内,C的产量每周至少150件,而每周至多20吨煤,其他数据见下表:产品 最大产量 销售量 成本 售价 能耗 生产时间 (件/周) (件/周) (元/件) (元/件) (吨煤/百件) (时/件)A 270 300 190 200 1.5 13B 240 300 210 230 2 C 460 600 148 160 1.8 14D 130 200 100 114 1.1 问应如何安排每周生产,才能使利润最高,而能耗最少？解 用表示四种产品的产量,表示每件产品的利润,表示每100件产品的能耗,表示生产每件产品的时间,表示种产品的最大产量.建立双目标规划模型如下: LINGO程序如下:MODEL:SETS: YF/B1 B2 B3 B4 /:B,A,C,D,X;ENDSETSDATA:A=10 20 12 14; B=1.5 2 1.8 1.1;C=13 13.5 14 11.5; D=270 240 460 130;ENDDATAMAX=SUM(YF(I):A*X);FOR(YF(I):GIN(X(I); SUM(YF(I):B(I)*X(I)<=2000; X(3)>=150; FOR(YF(I):X(I)<=D(I);SUM(YF(I):C(I)*X(I)<=14400;SUM(YF(I):C(I)*X(I)>=12000;END具体求解结果为: Extended solver steps: 0 Total solver iterations: 3Variable Value Reduced Cost 即A、B、C、D四种产品各生产248件、240件、460件、130件时,能使利润最高,最高利润为14620元.题目还要求能耗最少,因此用分层序列法,把利润最高的计算结果作为约束条件,即增加约束条件:,把作为目标函数,建立单目标规划模型求解.LINGO程序如下:MODEL:SETS: YF/B1 B2 B3 B4 /:B,A,C,D,X;ENDSETSDATA:A=10 20 12 14; B=1.5 2 1.8 1.1;C=13 13.5 14 11.5; D=270 240 460 130;ENDDATAMIN=SUM(YF(I):B(I)*X(I)/100);SUM(YF(I):A*X)<=14620;FOR(YF(I):GIN(X(I); SUM(YF(I):B(I)*X(I)<=2000; X(3)>=150; FOR(YF(I):X(I)<=D(I);SUM(YF(I):C(I)*X(I)<=14400;SUM(YF(I):C(I)*X(I)>=12000;END具体求解结果为: Extended solver steps: 0 Total solver iterations: 5Variable Value Reduced Cost 即每周生产A、B、C、D四种产品各270件、42件、460件、129件,能使利润最高,能耗最少.五 用LINGO求非线性曲线拟合的最小二乘解设观测数据为,希望用一条相对光滑的曲线来近似表示变量y与x的关系,不要求它通过每个数据点(节点),但要求曲线与数据点之间的距离尽可能小,称为拟合函数或经验公式.设拟合函数的表达式中含有若干待定常数,称为回归系数,用向量符号记为,则曲线方程记为,其具体形式可由散点图或通过建立数学模型来确定.设拟合函数形式已知为,其中是待定常数(回归系数),求待定常数A的方法通常用最小二乘法,其算法原理是求出使均方误差取最小值的A,其结果称为最小二乘解,于是问题转化为多元函数的最小值: .上式可以看成是目标函数为非线性函数,没有约束条件的规划问题,适合用LINGO求解,举例如下:例5 2004年全国大学生数学建模竞赛C题中给出体重约70kg的某人在短时间内喝下2瓶啤酒后,隔一定时间测量他的学业者酒精含量,得到数据见下表,请建立饮酒后血液中酒精含量的数学模型.血液中酒精含量数据时间t(小时)酒精含量y0.25 0.5 0.75 1 1.5 2 2.5 3 3.5 4 4.5 530 68 75 82 82 77 68 68 58 51 50 41时间t(小时)酒精含量y6 7 8 9 10 11 12 13 14 15 1638 35 28 25 18 15 12 10 7 7 4 解 把人体内酒精的吸收、代谢、排除过程分成两个室,胃为第一室,血液为第二室,酒精先进入胃,然后被吸收进入血液,由循环到达体液内,在通过代谢、分解剂排泄、出汗、呼气等方式排泄.假设胃里的酒精被吸收进入血液的速度与胃里的酒精成正比,比例常数为,血液中的酒精被排出的速度与血液内的酒量成正比, 比例系数为. 短短时间内喝入胃里的酒精总量为. 则可以建立如下微分方程模型:这是线性常系数微分方程组,求解得到如果统一用 表示待定常数,则上式可以写成由已知数据求出使最小的待定系数,程序如下:MODEL:SETS: SJD/1.23/:T,Y; ENDSETSDATA:T=0.25,0.5,0.75,1,1.5,2,2.5,3,3.5,4,4.5,5,6,7,8,9,10,11,12,13,14,15,16;Y=30,68,75,82,82,77,68,68,58,51,50,41,38,35,28,25,18,15,12,10,7,7,4;ENDDATAMIN=SUM(SJD(I):(A1*(EXP(-A2*T)-EXP(-A3*T)-Y)2);END运行结果如下:Local optimal solution found. Extended solver steps: 5 Total solver iterations: 138Variable Value Reduced Cost 程序中定义SJD是含有23个成员的集合,T和Y是SJD的两个属性,分别表示时间t和血液中酒精浓度y,它们都是包含23个成员的以为数组(向量).点击运行按钮,很快得到计算结果: =,=,=,目标函数值(即最优解)为. 总结 LINGO软件作为一种解决许多规划问题的软件包,可以用LINGO软件模型解决许多规划问题,方法简单易行,操作灵活,比较适用于规划理论的求解.通过用LINGO对上面各个模型的求解,可以看出,由于LINGO的内部函数:FOR(s:e)、SUM(s:e)、MAX(s:e)、MIN(s:e)BIN(X)、BND(L,X,U)、GIN(X)、FREE(X).BIN(X)等,使得在编写程序时,可以避免使用for,if等循环语句,相对于用C语言求解,LINGO求解规划问题是十分方便的.参考文献:1袁新生,邵大宏,郁时炼.LINGO和Excel在数学建模中的应用M.北京:科学出版社,2007.2贾贞等.运筹学原理与实验教程M.武汉:华中师范大学出版社,2008.3Matlab与Lindo求解线性规划J.德宏师范高等专科学校学报,2006,8(1):106-111.4刁在筠,郑汉鼎,刘家壮,刘桂真.运筹学M.北京:高等教育出版社,2001.5徐玖平,胡知能.运筹学:数据·模型·决策M.北京:科学出版社,2009.6邓成梁等.运筹学的原理和方法M.武汉:华中理工大学出版社,1998,3.7许数柏.数学生态学模型与研究方法J.安康师专报,2002,12(2):4-8.8李磊.露天矿生产的车辆安排的模型和评述J.工程数学学报,2003,12(7):91-100.致 谢 本课题在选题及研究过程中得到数学科学学院吴庆丰老师的悉心指导,并为我提供相关资料,在此表示衷心的感谢!尤其是吴老师严谨的治学态度深深影响了我,使我获益良多.同时数学科学学院机房的硬件设施和学校图书馆电子资源,为本课题的研究工作提供了良好的条件.另外,本课题的部分工作还得益于同窗挚友的共同研讨,在此,对他们一并表示感谢!【精品文档】