版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
数学建模竞赛培训第一部分数学建模概况
唐代大诗人王之涣有一首著名诗篇:白日依山尽
黄河入海流
欲穷千里目
更上一层楼
按诗人的想象,要看到千里之外的景物,要站在多高的“一层楼”上呢?
以地球中心为原点,向上方向为纵轴建立直角坐标系.从地球表面算起,设应站高度为x,那么根据题设,该点到地球表面的切线长应为500km.
则依据题意,并利用勾股定理有解得解决问题的思路、方法、步骤:做出了合理的简化:1.人眼能看很远;2.楼房可以修的很高;3.地球近似为球体。进行了抽象:用数学符号表示相关变量应用数学物理知识、方法建立了方程(模型):利用数学工具求解(方程)回答现实世界数学世界数学模型(MathematicalModel)一般地说,数学模型可以描述为,对于现实世界的一个特定对象,为了一个特定目的,根据特有的内在规律,做出一些必要的简化假设,运用一些适当的数学工具,得到的一个数学结构。
数学建模(MathematicalModeling)
应用知识从实际问题中抽象、提炼出数学模型的过程。1.
数学模型与数学建模强调运用数学的思维方法、数学的语言去近似地刻画实际问题,并加以解决。树上有十只鸟,开枪打死一只,还剩几只,这样的问题就是一道数学应用题。正确答案应该是9只,是吧?这样的题照样是数学建模题,不过答案就不重要了,重要的是过程。真正的数学建模高手应该这样回答这道题。体现数学思维的案例:“树上有十只鸟,开枪打死一只,还剩几只?”“是无声手枪或别的无声的枪吗?”“不是。”“枪声有多大?”“80-100分贝。”“那就是说会震的耳朵疼?”“是。”“在这个城市里打鸟犯不犯法?”“不犯。”“您确定那只鸟真的被打死啦?”“确定。”“OK,树上的鸟里有没有聋子?”“没有。”“有没有关在笼子里的?”“没有。”“边上还有没有其他的树,树上还有没有其他鸟?”“没有。”“有没有残疾的或饿的飞不动的鸟?”“没有。”“打鸟的人眼有没有花?保证是十只?”“没有花,就十只。”“有没有傻的不怕死的?”“都怕死。”“会不会一枪打死两只?”“不会。”“所有的鸟都可以自由活动吗?”“完全可以。”“如果您的回答没有骗人,打死的鸟要是挂在树上没掉下来,那么就剩一只,如果掉下来,就一只不剩。”不是开玩笑,这就是数学建模。从不同的角度思考一个问题,想尽所有的可能,正所谓智者千虑,绝无一失!
建立数学模型的方法和步骤并没有一定的模式,但一个理想的模型应能反映系统的全部重要特征:
可靠性和使用性
建模的一般方法:◆机理分析◆测试分析方法
机理分析:根据对现实对象特性的认识,分析其因果关系,找出反映内部机理的规律,所建立的模型常有明确的物理或现实意义。
2.
数学建模的一般方法和步骤
测试分析方法:
将研究对象视为一个“黑箱”系统,内部机理无法直接寻求,通过测量系统的输入输出数据,并以此为基础运用统计分析方法,按照事先确定的准则在某一类模型中选出一个数据拟合得最好的模型。测试分析方法也叫做系统辩识。将这两种方法结合起来使用,即用机理分析方法建立模型的结构,用系统测试方法来确定模型的参数,也是常用的建模方法。
在实际过程中用那一种方法建模主要是根据我们对研究对象的了解程度和建模目的来决定。机理分析法建模的具体步骤大致可见右图。符合实际不符合实际交付使用,从而可产生经济、社会效益实际问题抽象、简化、假设确定变量、参数建立数学模型并用数学方法、计算机求解用实际问题的实测数据等来检验该数学模型建模过程示意图2.
数学建模步骤3.
数学模型及其分类模型
数学模型是模型的一种形式,属理想模型(又称为抽象模型),是将现实事物设定在一种理想状态,依据对事物所关心的目标,找出相关的主要因素,分析其内在联系,将目标及全部相关因素符号化、数量化;用数学的方法把这种关系表述出来(图形、图像、数表、解析式),这种数学表述形式就是数学模型。数学模型的分类:
◆按研究方法和对象的数学特征分:初等模型、几何模型、优化模型、微分方程模型、图论模型、逻辑模型、概率模型、稳定性模型、扩散模型等。◆按研究对象的实际领域(或所属学科)分:人口模型、交通模型、环境模型、生态模型、生理模型、城镇规划模型、水资源模型、污染模型、经济模型、社会模型等。3.
数学模型及其分类
竞赛的规模越来越大数量逐年增大覆盖面越来越大竞赛的水平不断地提高赛题水平的提高学生参赛水平的提高
越来越受到各个高校和学生的重视
一次参赛,终身受益衡量一个大学培养质量的重要指标
赛题越来越复杂(综合性、实用性、即时性)海量数据处理全国高校规模最大的学生课外科技活动!4.
CUMCM概况与趋势历年全国数学建模赛题及常用方法剖析赛题
解法93A非线性交调的频率设计拟合、规划93B足球队排名
矩阵论、图论、层次分析、整数规划94A逢山开路
图论、插值、动态规划94B锁具装箱问题
图论、组合数学95A飞行管理问题非线性规划、线性规划95B天车与冶炼炉的作业调度非线性规划、动态规划、层次分析法、PETRI方法、图论方法、排队论方法
96A最优捕鱼策略
微分方程、优化96B节水洗衣机非线性规划97A零件的参数设计田口方法、非线性规划97B截断切割的最优排列动态规划、图论模型、随机模拟98A一类投资组合问题多目标优化、非线性规划、模糊线性规划
98B灾情巡视的最佳路线图论、组合优化、线性规划99A自动化车床管理
随机优化、计算机模拟99B钻井布局0-1规划、图论、非线性规划
00ADNA序列分类
模式识别、欧氏距离、马氏距离分类法、Fischer判别模型、神经网络方法00B钢管订购和运输
组合优化、运输问题01A血管三维重建曲线拟合、曲面重建01B工交车调度问题多目标规划02A车灯线光源的优化
非线性规划02B彩票问题单目标决策03ASARS的传播
微分方程、差分方程03B露天矿生产的车辆安排整数规划、运输问题04A奥运会临时超市网点设计统计分析、数据处理、优化04B电力市场的输电阻塞管理数据拟合、优化05A长江水质整体评价模糊数学、神经网络方法,曲线拟合05BDVD在线租赁整数规划06A出版社资源优化配置统计分析(海量数据统计、筛选)、数据处理、优化06B艾滋病治疗效果评价与预测聚类分析,模糊数学评价,数据处理(1).从问题的实际意义分析
从问题的实际意义方面分析,大体上可以分为工业、农业、工程设计、交通运输、经济管理、生物医学和社会事业等七个大类。
工业类:电子通信、机械加工与制造、机械设计与控制等行业,共有8个题,约占31%。农业类:1个题,占4%。工程设计类:
3个题,占11%。交通运输类:3个题,占11%经济管理类:3个题,占11%生物医学类:4个题,占15%社会事业类:4个题,占15%(2).从所用方法上分析最优化方法:一般函数优化—用微积分的方法解决;规划问题—线性规划,非线性规划,多目标规划,动态规划,整数规划,组合优化(离散优化))等(使用软件求解);数据处理方法:曲线拟合,数据回归分析,插值,基于数据库(Acess,Excel)的海量数据的筛选等;概率统计方法:期望分析,排队论,回归分析,模式识别,判别分析;图论方法:最短路问题,最大流问题,最小生成树;微分方程方法:稳定性分析,预测;模糊数学:模糊聚类分析,模糊层次分析,模糊规划计算机技术:图像处理,随机模拟,各种算法实现,神经网络方法。离散方法:层次分析法,决策分析,对策论;
从各年赛题所用方法看,以下几种方法出现频率最高:最优化方法约占总数的80%大部分题目都可以用两种以上的方法来解决。数据处理方法概率统计方法约占总数的50%(3).从问题的题型上分析1)“即时性”较强的问题约占35%:1993B:足球队排名问题;1998B:灾情巡视路线问题;2000A:DNA序列分类问题;2000B:钢管订购与运输问题;2001B:公交车的调度问题;2002B:彩票中的数学问题;2003A:SARS的传播问题;2004A:奥运会临时超市网点设计问题2004B:电力市场的输电阻塞管理问题2005A:长江水质评价2)理论性较强的问题约占46%:94A,94B,95A,96A,97A,98B,99A,00B,01A,02A,03A,04B;3)实用性较强的问题约占46%:93A,94B,95B,96B,98B,99B,00B,01A,01B,02B,03A,04B;06A,06B4)算法要求强的约占19%:95A,97B,99B,00A,00B;5)数据量较大的问题约占31%:00A,00B,01A,01B,02B,03A,04A,04B,05B,06A,06B.
从近几年的竞赛题目来看,题目的水平在不断提高、难度在增加、实用性在增强;特别是综合性和开放性也在增强,这是一大潮流,从发展趋势上来看,有逐步走向国际化的趋势,同国际接轨是必然的;随着计算机技术和工具软件(Matlab,SAS,Lingo等)功能的增强,数据信息量(海量)也在逐步地增大,这也是现代应用的特点之一。第二部分专题+案例专题1:优化模型与优化工具无约束优化问题线性规划问题整数规划问题非线性规划问题
Lingo9Matlab6.5一、优化模型的一般形式
实际问题中的优化模型x~决策变量f(x)~目标函数gi(x)0~约束条件多元函数条件极值决策变量个数n和约束条件个数m较大最优解在可行域的边界上取得数学规划线性规划非线性规划整数规划重点在模型的建立和结果的分析有约束问题和无约束问题。静态问题和动态问题。线性规划,非线性规划,二次规划,多目标规划等。二、优化模型的分类
线性规划(LP)特点:
目标函数和所有的约束条件都是决策变量的线性函数。5.根据变量具有确定值还是随机值
确定规划和随机规划。4.根据决策变量的允许值整数规划(0-1规划)和实数规划。1.确定决策变量和目标变量;2.确定目标函数的表达式;3.寻找约束条件。三、建立优化模型的一般步骤四、若干优化模型案例
其中(3)、(4)、(5)的等式右边可选用(1)或(2)的等式右边。函数fminbnd的算法基于黄金分割法和二次插值法,它要求目标函数必须是连续函数,并可能只给出局部最优解。常用格式如下:(1)x=fminbnd(fun,x1,x2)(2)x=fminbnd(fun,x1,x2,options)(3)[x,fval]=fminbnd(...)(4)[x,fval,exitflag]=fminbnd(...)(5)[x,fval,exitflag,output]=fminbnd(...)1无约束优化问题及Matlab求解描述退出条件:exitflag>0,表目标函数收敛于解x处exitflag=0,表已达到函数评价或迭代的最大次数exitflag<0,表目标函数不收敛
包含优化结果信息的输出结构.Iterations:迭代次数Algorithm:所采用的算法FuncCount:函数评价次数
由优化函数求得的值.若exitflag>0,则x为解;否则,x不是最终解,它只是迭代制止时优化过程的值。优化函数的输出变量的含义:xexitflagoptions案例1对边长为3米的正方形铁板,在四个角剪去相等的正方形以制成方形无盖水槽,问如何剪法使水槽的容积最大?解:先编写M文件box.m如下:
functionf=box(x)f=-(3-2*x).^2*x;主程序为box_main.m:
[x,fval]=fminbnd(‘box',0,1.5);xmax=xfmax=-fval运算结果为:xmax=0.5000,fmax=2.0000.即剪掉的正方形的边长为0.5米时水槽的容积最大,最大容积为2立方米。案例2
有甲、乙两个工厂,甲厂位于一直线河岸的岸边A处,乙厂在河的另一侧的B处,B处距甲所在河岸的垂直距离为35公里,乙厂到河岸的垂足D与A相距50公里,两厂要在此岸边合建一个供水站C,从供水站到甲厂和乙厂的水管费用分别为30元和50元每公里,问供水站C建在何处才能使水管费用最省?xDCBA先建立该问题的数学模型。据题意和平面几何知识知,只有点C在线段AD上某一适当位置,才能能使费用最省。设C点距D点x公里,如右图所示,则BD=35,AC=50-x,于是
又设总的水管费用为f元,由题意得管道总费用模型如下:解答:xDCBA求该函数的最小值。
先定义目标函数plant.m:functionf=plant(x)f=30*(50-x)+50*sqrt(x^2+35^2);主程序为plant_main.m:fplot('plant',[0,50])[x,fval]=fminbnd('plant',0,50)输出图形见右图,最优解和最优值为:fval=2900注:fplot表示绘制字符串fun指定的函数在[xmin,xmax]的图形.2线性规划模型
线性规划(LP)研究的实际问题多种多样的,它在工农业生产、经济管理、优化设计与控制等领域都有广泛应用。如资源分配问题、生产计划问题、物资运输问题、合理下料问题、库存问题、劳动力安排问题、最优设计问题等等。线性规划模型的求解方法目前仍以单纯形法为主要方法,该方法于1947年由美国数学家丹茨格(G.B.Dantzig)提出,经过60多年的发展完善,已经形成比较成熟的算法,同时配合计算机技术的广泛应用使得该方法得到空前的普及应用。目前,大多数数学软件都可以求解一般线性规划模型,这一节主要采用Matlab和Lindo软件。
每种蔬菜含有的营养素成份是不同的,从医学上知道每人每周对每种营养成分的最低需求量以及各种蔬菜所含各种营养成分的数据。某医院营养室在制定下一周菜单时,需要确定表1中所列8种蔬菜的供应量,以便使费用最小而又能满足营养素等其它方面的要求。规定小白菜、豆芽的供应一周内不多于20千克,胡萝卜供应一周内不低于10千克,不高于35千克,其它蔬菜的供应在一周内不多于30千克,每周共需供应150千克蔬菜,为了使费用最小又满足营养成分等其它方面的要求,问在下一周内应当如何合理的安排食谱?案例3食谱问题表1各种蔬菜的营养成分表成份蔬菜热量(卡)水分(克)维生素A(IU)维生素C(毫克)钾(毫克)纤维(克)市场单价(元/千克)小白菜1395.778140.02401.82菠菜2293.021069.04602.44胡萝卜3889.751004.02902.65小黄瓜1795.2934.0900.93豆芽3390.60183.61901.76玉米11174.286.02404.67香菇4088.500.22803.912蕃茄2692.927821.02101.26人体最低需求量/周12000(卡)17500(克)24500(IU)420(毫克)2100(毫克)175(克)备注:此表为100克蔬菜所含的营养成分,IU表示国际单位
。决策变量:设xi(i=1,…,8)分别表示在下一周内应当供应的小白菜、菠菜、胡萝卜、小黄瓜、豆芽、玉米、香菇及蕃茄的量(千克)。费用的目标函数为:根据人体每周对各种营养成分的需求量,可以得到如下需求约束:模型建立需要注意的是,表中数据是每100克食物中所含营养成分的的量,而变量是以千克为单位,所以数据要作适当的转化处理,这里很明显就是各式两边除以10即可。另外对食物需求的上限和下限有如下约束:食物总供应量限制:小白菜、豆芽的供应一周内不多于20千克,胡萝卜不低于10千克,不高于35千克,其它蔬菜的不多于30千克,每周共需供应150千克蔬菜模型建立食谱搭配问题的线性规划模型模型建立min2x1+4x2+5x3+3x4+6x5+7x6+12x7+6x8st13x1+22x2+38x3+17x4+33x5+111x6+40x7+26x8>120095.7x1+93x2+89.7x3+95.2x4+90.6x5+74.2x6+88.5x7+92.9x8>1750781x1+2106x2+5100x3+93x4+8x6+278x8>245040x1+9x2+4x3+4x4+183.6x5+6x6+0.2x7+21x8>42240x1+460x2+290x3+90x4+190x5+240x6+280x7+210x8>210x1+x2+x3+x4+x5+x6+x7+x8=150x1<20x5<20x3>10x3<35x2<30x4<30x6<30x7<30x8<30end模型求解
LPOPTIMUMFOUNDATSTEP22OBJECTIVEFUNCTIONVALUEVARIABLEVALUEREDUCEDCOST运行后得到如下结果:可见最佳的食物搭配方案为一周安排20千克小白菜,30千克菠菜,35千克胡萝卜,30千克小黄瓜,5千克豆芽和30千克蕃茄,方案最小费用为635元。小白菜菠菜胡萝卜小黄瓜豆芽玉米香菇蕃茄结果分析ROWSLACKORSURPLUSDUALRICESNO.ITERATIONS=22结果分析x1<20x5<20x3>10x3<35x2<30x4<30x6<30x7<30x8<30小白菜豆芽胡萝卜胡萝卜小黄瓜菠菜玉米香菇蕃茄可见最佳的食物搭配方案为一周安排20千克小白菜,30千克菠菜,35千克胡萝卜,30千克小黄瓜,5千克豆芽和30千克蕃茄,方案最小费用为635元。minz=cX
1、模型:命令:x=linprog(c,A,b)
2、模型:minz=cX
命令:x=linprog(c,A,b,Aeq,beq)注意:若没有不等式:存在,则令A=[],b=[].MATLAB优化工具箱解数学规划(一)线性规划3、模型:minz=cX
VLB≤X≤VUB命令:[1]x=linprog(c,A,b,Aeq,beq,VLB,VUB)
[2]x=linprog(c,A,b,Aeq,beq,VLB,VUB,X0)
注意:[1]若没有等式约束:,则令Aeq=[],beq=[].[2]其中X0表示初始点4、命令:[x,fval]=linprog(…)返回最优解x及x处的目标函数值fval。clearf=[245367126];A=-[13223817331114026;95.79389.795.290.674.288.592.9;7812106510093080278;40944183.660.221;24046029090190240280210;1.82.42.60.91.74.63.91.2];b=-[1200175024504221017.5]';aeq=[11111111];beq=[150];vlb=[001000000]';vub=[2030353020303030]';[x,fval,exitflag,output]=linprog(f,A,b,aeq,beq,vlb,vub)Matlab求解Optimizationterminatedsuccessfully.x=fval=exitflag=1output=iterations:19cgiterations:0algorithm:'lipsol'X120.000000X230.000000X335.000000X430.000000X55.000000X60.000000X70.000000X830.000000Lindo6.1求解结果豆芽番茄对比用Matlab和Lindo求解的结果发现两个最优解不一样,主要是豆芽和蕃茄的量不一样,但最优值是一致的。导致这种结果的原因是不同软件使用算法的细节上有差异(初值,基变量选择),这从两个软件求解过程迭代的次数不同可见,同时由于线性规划问题可能存在多个最优解,而一般情况下软件只能给出一个解,这就使得不同软件求出的最优解可能具有算法上或精度上的差异。两种软件对比两种软件求解线性规划问题在格式上也有很大差别,Lindo语句在形式上和模型具有较大的相似性,使得输入比较直观,但如果约束条件多,变量多,可能程序会很罗嗦冗长,而Matlab所有数据需用矩阵形式输入,形式比较简单紧凑,也易于修改,但开始需要对模型进行变形整理,化成标准形式。灵敏度分析、整数规划求解等等。3整数规划模型实际问题中经常遇到货物是不可分割的,如人,动物,整体装配的设备等,这时候除了题目本身的约束外,还要加上决策变量的整数约束,这就是这节要介绍的整数规划问题(IntegerPrograming)。整数规划又可分为线性整数规划和非线性整数规划,这一节只介绍整线性规划。整数线性规划中如果所有决策变量都是整数,则称为纯整数规划;若只有部分变量为整数,则称为混合整数规划;若决策变量只能取0或1,则称为0-1规划。求解整数规划的算法主要是分枝定界法和割平面法,这两种方法都是以求解线性规划的方法为基础。而0-1规划的求解使用隐枚举法,它不需要用单纯形法先求解线性规划,而是依次检查变量等于0或1的某种组合,以便使目前最好的可行解不断加以改进,最终获得最优解。
整数规划的求解主要使用Lindo和Lingo软件。案例4铁路平板车装货问题有七种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和高是一样的,但厚度(t,以厘米计)及重量(w,以公斤计)是不同的。下表给出了每种包装箱的厚度、重量以及数量。下图中每辆平板车有10.2米长的地方可用来装包装箱(象面包片那样),载重为40吨。由于当地货运的限制,对C5,C6,C7类的包装箱的总数有一定的限制:这类箱子所占的空间(厚度)不能超过302.7厘米。试把包装箱装到平板车上去使得浪费的空间最小。问题描述C1C2C3C4C5C6C7t厘米48.752.061.372.048.752.064.0W公斤200030001000500400020001000件数8796648七种规格的包装箱参数所有包装箱的总重量为89吨,大于两辆平板车的总载重量80,所以只能选择性的装载货物.
浪费空间是指平板车可装车长度与每辆车所有包装箱厚度总和的差值,可以等效的把浪费空间最小转化成两辆车装车总量最大.包装箱的重量和厚度受到平板车装载条件的限制以及货物总量的限制.
问题分析货物是不可拆分的,所以这是一个典型的整数线性规划问题.两辆平板车之间存在相互的制约关系,在考虑一辆平板车时,必须同时考虑第二辆平板车.问题分析对题目中“由于当地货运的限制,对C5,C6,C7类的包装箱的总数有一定的限制:这类箱子所占的空间(厚度)不能超过厘米。”可以理解成每辆车这三类货物的装车总数不超过厘米,也可以是两辆车装载三类货物的总量不超过厘米.
模型假设1.各个货物之间排列时靠在一起,包装箱之间的空隙不计;2.装载的过程中不考虑货物在车上的排列次序及各个货物的重量分布,排除因局部过重而造成平板车失衡的情况;3.铁路平板车只能放置一列包装箱;4.两辆平板车装载C5,C6,C7三类包装箱的总厚度不超过302.7厘米。
模型建立决策变量设xij表示第i辆平板车装载Cj包装箱的件数,i=1,2;j=1,2,…,7.
分别表示包装箱的厚度、单个重量和可供装车的件数.参数变量装车总厚度记为T,则目标函数可表示为:
目标函数约束条件各种包装箱可供装车数量的限制:平板车载重限制:厚度限制:模型建立约束条件两辆车对包装箱C5,C6,C7的特殊限制:所有决策变量都是整数变量:
模型求解该整数规划模型可以利用Lindo和Lingo求解。求解之前注意到20.4-3.027=17.373m,而前4类货物的总长度恰为17.373m。因此在满足约束条件的情况下,应尽量将C1~C4四类箱子装完,以保证两辆车浪费的空间最小。所以在求解时将前四类箱子的数量约束改成等式。stx11+x21=8x12+x22=7x13+x23=9x14+x24=6x15+x25<6x16+x26<4x17+x27<82x11+3x12+x13+0.5x14+4x15+2x16+x17<402x21+3x22+x23+0.5x24+4x25+2x26+x27<400.487x11+0.52x12+0.613x13+0.72x14+0.487x15+0.52x16+0.64x17<10.2endgin14在Lindo6.1中输入程序代码:包装箱可供装车数量的限制平板车载重限制厚度限制特殊限制整数即最优的装车方案为:x11=0,x12=7,x13=9,x14=0,x15=0,x16=2,x17=0;x21=8,x22=0,x23=0,x24=6,x25=3,x26=1,x27=0。最优值为20.394,浪费的空间仅有0.6cm。此时两辆车装车总长度均为10.197m,装车总重分别为34t和33t,装载C5,C6,C7三类货物总长度分别为1.04m和1.981m。OBJECTIVEFUNCTIONVALUEVARIABLEVALUEREDUCEDCOSTX110.000000X12X13X140.000000X150.000000X162.000000X170.000000计算结果:ROWSLACKORSURPLUSDUALPRICESNO.ITERATIONS=155747计算结果:结果分析注意:题目中C1与C5,C2与C6厚度相同,导致可能存在多个解。通过不断求解这种实验方式来体验多个解的存在性!OBJECTIVEFUNCTIONVALUEVARIABLEVALUEREDUCEDCOSTNO.ITERATIONS=300985继续求解会得到不同的最优解,而且呈现一定的周期性重复,但最优值都是20.394。其原因就在于模型有多个解,但Lindo一次只能给出一个最优解。虽然每次求解可能有不同解,但并不是说一直进行下去就会求出所有解。可以利用最优解已知(20.394),通过计算机编程枚举得出如下所有可能解:第一辆第二辆x11x12x13x14x15x16x17x21x22x23x24x25x26x27079002080063100564020823231006900308106300076400080323300664010813232014433307353000154332072530101643310715302024432306353100250533062910002543220625311026432106153120274320060531303091320570501031913105605020329130055050303443130535320035052305291100354312052532103605220519111036431105153220370521050911203743100505323040533304743000409122047051104191210460512041533204643010425331045430204291200450513043533004443030该模型的计算量较大,每次迭代次数达到数十万次,寻找改进的、简化的计算方法和技巧是值得我们进一步思考的。如果将两辆车装载后三类货物总厚度不超过改成每辆车装载不超过此值,则情况如何?结果分析这30组解中,所有的装车方案都是值得推荐的吗?现实中还应考虑两辆平板车的载重量、占用空间差别均不应太大。需要进行结果筛选。该问题和自来水输送以及飞机装货问题一样属于运输问题,只不过是运输问题的一种变形,运筹学中通常将这类问题称为背包问题,由于有长度、重量两项约束,所以称为二维背包问题,可以利用数学规划或动态规划求解。小结每组解中第7种货物都没有选!这是88年一道MCM竞赛题,在当时软件还不发达时是有较大难度的!生产、生活物资从若干供应点运送到一些需求点,怎样安排输送方案使运费最小,或利润最大;小结:运输问题(TransportationProblem)各种类型的货物装箱,由于受体积、重量等限制,如何搭配装载,使获利最高,或装箱数量最少。案例5:人力资源配置问题
某城市有一昼夜服务的公交线路,经过长期观察统计,每天各时间区段内需司机和乘务人员总数如下表。班次时间区段所需人数16:00~10:0050210:00~14:0060314:00~18:0050418:00~22:0040522:00~2:002062:00~6:0030问题描述设司机和乘务人员分别在各时间区段一开始时上班,并连续工作八小时,问该公交线路至少配备多少名司机和乘务人员才能满足实际需要?模型建立设xi为第i时段所需的人数,由于从第i时段开始上班的人在第i+1时段会继续上班(注意如果i取6,则i+1应取1)目标函数约束条件班次时间区段16:00~10:00210:00~14:00314:00~18:00418:00~22:00522:00~2:0062:00~6:00模型求解直接输入方式:
model:min=x1+x2+x3+x4+x5+x6;x1+x6>50;x1+x2>60;x2+x3>50;x3+x4>40;x4+x5>20;x5+x6>30;@gin(x1);@gin(x2);@gin(x3);@gin(x4);@gin(x5);@gin(x6);endGlobaloptimalsolutionfound.Objectivevalue:130.0000Extendedsolversteps:0Totalsolveriterations:7VariableValueReducedCostX150.000001.000000X210.000001.000000X340.000001.000000X40.0000001.000000X530.000001.000000X60.0000001.000000计算结果:注意与Lindo的相似性和区别Lingo程序(方式一):
模型求解Lingo程序(方式二):model:sets:time/1..6/:required,driver;endsetsdata:required=605040203050;enddatamin=@sum(time:driver);!各时段需求约束;@for(time(i):driver(i)+driver(@wrap(i+1,6))>=required(i));!各变量整数约束;@for(time:@gin(driver));end注:在集合循环函数中,当达到集合的最后(或第一个)成员后,可以用@wrap函数把索引转到集合的第一个(或最后一个)成员。@wrap(i,N)的返回值当i位于区间[1,N]内时返回i,否则返回j=i-k*N,k为整数,且j位于区间[1,N]内。如@wrap(2,5)返回值为2,@wrap(16,5)返回值为1。在这里的作用是让@wrap(7,6)返回到1。编程方式定义原始集time,6个成员,两个属性数据部分Globaloptimalsolutionfound.Extendedsolversteps:0Totalsolveriterations:6VariableValueReducedCost求解结果即6个班次依次需要的司乘人员数量分别为:x1=50;x2=10;x3=40;x4=0;x5=30;x6=0。共计至少需要130名司乘人员。生产中通过切割、剪裁、冲压等手段,将原材料加工成所需大小原料下料问题按照工艺要求,确定下料方案,使所用材料最省,或利润最大案例6:下料问题(一维)问题.如何下料最节省?原料钢管:每根19米4米50根6米20根8米15根工地需求节省的标准是什么?问题描述某建筑工地需要一批不同型号的钢管,其中4m的50根,6m的20根,8m的15根。现在从钢管厂进货的原料都是19m的,需要对这些原料进行合理的切割。问怎样切割使得既满足工地需求,又使浪费材料最小?按照客户需要在一根原料钢管上安排切割的一种组合。
切割模式余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根合理切割模式的余料应小于客户需要钢管的最小尺寸余料3米8米1根8米1根钢管下料为满足客户需要,按照哪些种合理模式,每种模式切割多少根原料钢管,最为节省?合理切割模式2.所用原料钢管总根数最少模式
4米钢管根数6米钢管根数8米钢管根数余料(米)14003231013201341203511116030170023钢管下料问题1两种标准1.原料钢管剩余总余量最小xi~按第i种模式切割的原料钢管根数(i=1,2,…7)约束满足需求决策变量
目标1(总余量)按模式2切割12根,按模式5切割15根,余料27米
模式4米根数6米根数8米根数余料14003231013201341203511116030170023需求502015最优解:x2=12,x5=15,其余为0;最优值:27。整数约束:xi为整数model:sets:pattern/1..7/:residu,number;type/1..3/:required;link(pattern,type):aa;endsetsdata:residu=3133113;required=502015;aa=400310201120111030002;enddata!目标函数(总余量最小)min=@sum(pattern:residu*number);!工地需求;@for(type(i):@sum(pattern(j):aa(j,i)*number(j))>required(i));!各变量整数约束;@for(pattern:@gin(number));end钢管切割问题的Lingo程序当余料没有用处时,通常以总根数最少为目标目标2(总根数)钢管下料问题1约束条件不变最优解:x2=15,x5=5,x7=5,其余为0;最优值:25。xi为整数按模式2切割15根,按模式5切割5根,按模式7切割5根,共25根,余料35米虽余料增加8米,但减少了2根与目标1的结果“共切割27根,余料27米”相比小结:下料问题的建模确定下料模式构造优化模型规格不太多,可枚举下料模式,建立整数线性规划模型,否则要构造整数非线性规划模型,求解困难,可用缩小可行域的方法进行化简,但要保证最优解的存在。一维问题(如钢管下料)二维问题(如易拉罐下料)具体问题具体分析(比较复杂)
1.首先建立M文件fun.m,定义目标函数F(X):functionf=fun(X);f=F(X);
其中X为n维变元向量,G(X)与Ceq(X)均为非线性函数组成的向量,其它变量的含义与线性规划、二次规划中相同.用Matlab求解上述问题,基本步骤分三步:4非线性规划问题的matlab求解3.建立主程序.非线性规划求解的函数是fmincon,命令的基本格式如下:
(1)x=fmincon(‘fun’,X0,A,b)
(2)x=fmincon(‘fun’,X0,A,b,Aeq,beq)
(3)x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB)
(4)x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’)(5)x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’,options)
(6)[x,fval]=fmincon(...)
(7)[x,fval,exitflag]=fmincon(...)(8)[x,fval,exitflag,output]=fmincon(...)输出极值点M文件迭代的初值参数说明变量上下限
fmincon函数提供了大型优化算法和中型优化算法。默认时,若在fun函数中提供了梯度(options参数的GradObj设置为’on’),并且只有上下界存在或只有等式约束,fmincon函数将选择大型算法。当既有等式约束又有梯度约束时,使用中型算法。
fmincon函数的中型算法使用的是序列二次规划法。在每一步迭代中求解二次规划子问题,并用BFGS法更新拉格朗日Hessian矩阵。
fmincon函数可能会给出局部最优解,这与初值X0的选取有关。注意:案例71.先建立M-文件fun1.m定义目标函数:functionf=fun1(x);f=-2*x(1)-x(2);2.再建立M文件mycon1.m定义非线性约束:function[g,ceq]=mycon1(x)g=[x(1)^2+x(2)^2-25;x(1)^2-x(2)^2-7];ceq=[];3.主程序main.m为:x0=[3;2.5];VLB=[00];VUB=[510];[x,fval,exitflag,output]=fmincon('fun1',x0,[],[],[],[],VLB,VUB,'mycon4')4.运算结果为:x=exitflag=1output=iterations:4funcCount:17stepsize:1algorithm:[1x44char]firstorderopt:[]cgiterations:[]
某公司有6个建筑工地要开工,每个工地的位置(用平面坐标系a,b表示,距离单位:千米)及水泥日用量d(吨)由下表给出。目前有两个临时料场位于A(5,1),B(2,7),日储量各有20吨。假设从料场到工地之间均有直线道路相连。(1)试制定每天的供应计划,即从A,B两料场分别向各工地运送多少吨水泥,使总的吨千米数最小。(2)为了进一步减少吨千米数,打算舍弃两个临时料场,改建两个新的,日储量各为20吨,问应建在何处,节省的吨千米数有多大?案例8:供应与选址一建立模型
记工地的位置为(ai,bi),水泥日用量为di,i=1,…,6;料场位置为(xj,yj),日储量为ej,j=1,2;从料场j向工地i的运送量为Xij。当用临时料场时决策变量为:Xij,当不用临时料场时决策变量为:Xij,xj,yj。二使用临时料场的情形
使用两个临时料场A(5,1),B(2,7).求从料场j向工地i的运送量为Xij,在各工地用量必须满足和各料场运送量不超过日储量的条件下,使总的吨千米数最小,这是线性规划问题.线性规划模型为:设X11=X1,X21=X2,,X31=X3,X41=X4,X51=X5,,X61=X6X12=X7,X22=X8,,X32=X9,X42=X10,X52=X11,,X62=X12计算结果为:x=[3.00005.00000.00007.00000.00001.00000.00000.00004.00000.00006.000010.0000]’三改建两个新料场的情形
改建两个新料场,要同时确定料场的位置(xj,yj)和运送量Xij,在同样条件下使总吨千米数最小。这是非线性规划问题。非线性规划模型为:设X11=X1,X21=X2,,X31=X3,X41=X4,X51=X5,,X61=X6X12=X7,X22=X8,,X32=X9,X42=X10,X52=X11,,X62=X12
x1=X13,y1=X14,x2=X15,y2=X16
(1)先编写M文件liaoch.m定义目标函数。functionf=liaoch(x)a=[1.258.750.55.7537.25];b=[1.250.754.7556.57.75];d=[3547611];e=[2020];f1=0;fori=1:6s(i)=sqrt((x(13)-a(i))^2+(x(14)-b(i))^2);%计算料场A到各个工地距离f1=s(i)*x(i)+f1;%计算料场A到各个工地的吨千米总量Endf2=0;fori=7:12s(i)=sqrt((x(15)-a(i-6))^2+(x(16)-b(i-6))^2);%计算料场B到各工地距离f2=s(i)*x(i)+f2;%计算料场B到各个工地的吨千米总量endf=f1+f2;(2)取初值为线性规划的计算结果及临时料场的坐标:x0=[35070100406105127]';编写主程序gying2.m.x0=[35471000005115.63484.86877.24797.7499]';A=[11111100000000000000001111110000];B=[20;20];Aeq=[100000100000000001000001000000000010000010000000000100000100000000001000001000000000010000010000];beq=[3547611]';vlb=[zeros(12,1);-inf;-inf;-inf;-inf];vub=[];[x,fval,exitflag]=fmincon('liaoch',x0,A,B,Aeq,beq,vlb,vub)(3)计算结果为:10.07076.38754.39435.75117.1867]’exitflag=1(4)若修改主程序gying2.m,取初值为上面的计算结果:x0=[3.00005.00000.07077.000000.9293003.929306.000010.07076.38754.39435.75117.1867]’得结果为:x=[3.00005.00000.30947.00000.01080.6798003.690605.989210.32025.53694.91945.82917.2852]’exitflag=1总的吨千米数比上面结果略优.(5)若再取刚得出的结果为初值,却计算不出最优解.(6)若取初值为:x0=[35471000005115.63484.86877.24797.7499]',则计算结果为:x=[3.00005.00004.00007.00001.0000000005.000011.00005.69594.92857.25007.7500]’exitflag=1总的吨千米数89.8835比上面结果更好.通过此例可看出fmincon函数在选取初值上的重要性。
在我们的生活中每天都面对各种各样的大量的数据,比如科学研究,工程建设,股票信息,彩票数据,考试成绩,经济开销,时间,身高体重、三围参数等等。怎样从纷繁复杂的数据当中挖掘出有用的信息,是我们面临的一大问题。数据处理是数学建模一项重要的内容。问题的提出专题2:数据处理(拟合、插值、回归)问题1.已知一室模型快速静脉注射下的血药浓度数据(t=0注射300mg)求血药浓度随时间的变化规律c(t).
t(h)0.250.511.523468c(g/ml)19.2118.1515.3614.1012.899.327.455.243.01
这个问题要从一组实验观测数据(xi
,yi
)(i=1,2,…,n)出发揭示出自变量x与因变量y之间的关系,一般可以用一个近似的函数关系式y=f(x)来表示。函数f(x)的产生办法因观测数据与要求的不同而异,通常可采用两种方法:插值与数据拟合。1数据拟合2数据插值3回归分析4聚类分析数据处理的常用方法简介
已知一组(二维)数据,即平面上n个点(xi,yi)i=1,…,n,寻求一个函数(曲线)y=f(x),使f(x)在某种准则下与所有数据点最为接近,即曲线拟合得最好。
1.数据拟合(曲线拟合)+++++++++xyy=f(x)(xi,yi)ii为点(xi,yi)与曲线y=f(x)的距离某种准则下与所有数据点最为接近曲线拟合问题的提法拟合基函数第一步:确定拟合的函数类型其中为待定系数。第二步:确定的最小二乘准则:要求n个已知点(xi
,yi)与曲线的距离(偏差)di的平方和最小。满足上述要求的参数取值称为该问题的最小二乘解。曲线拟合问题最常用的解法—最小二乘法的基本思路2.如果无现成的规则,则可以通过散点图,结合曲线的形状进行分析,即建立经验模型。1.通过机理分析建立数学模型来确定f(x);+++++++++++++++f=ae-bxf=a1+a2xf=a1+a2x+a3x2拟合函数类型的确定1、线性最小二乘拟合2、非线性最小二乘拟合用MATLAB求解拟合问题1.作多项式f(x)=a1xm+…+amx+am+1拟合,可利用已有程序:a=polyfit(x,y,m)输出拟合多项式系数a=[a1,…,am,
am+1](数组)输入同长度的数组X,Y拟合多项式次数2.多项式在x处的值y可用以下命令计算:
y=polyval(a,x)用MATLAB作线性最小二乘拟合问题1药物浓度问题
2拟合结果:2次拟合效果对比图药物浓度与时间关系32拟合结果:药物浓度与时间关系3次拟合效果对比图
Matlab的提供了两个求非线性最小二乘拟合的函数:lsqcurvefit和lsqnonlin。两个命令都要先建立M-文件fun.m,在其中定义函数f(x),但两者定义f(x
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
评论
0/150
提交评论