最优化

1数学建模•Name:李学文•Office：中心教学楼0814•E-mail:[e-mail]2A零件的参数设计1997B最优截断切割问题A投资的收益和风险1998B灾情巡视路线A自动化车床管理1999B钻井布局ADNA序列分类2000B钢管订购和运输近年全国大学生数学建模竞赛题3A血管的三维重建2001B公交车调度A车灯线光源的优化设计2002B彩票中的数学ASARS的传播2003B露天矿生产的车辆安排A奥运会临时超市网点设计2004B电力市场的输电阻塞管理4A长江水质的评价和预测2005BDVD在线租赁A出版社的资源配置2006B艾滋病疗法的评价及疗效的预测A中国人口增长预测2007B乘公交，看奥运51）建模的基本概念和方法（数学建模课程的主要内容）2）建模过程中常用的数学方法(微积分、代数、概率外)，主要有：计算方法(如数值微分和积分、微分方程数值解、代数方程组解法)，优化方法(如线性、非线性规划)，数理统计(如假设检验、回归分析)，图论(如最短路)等。3)只要求知道实际问题与这些数学知识之间的对应关系（如哪些问题可用线性规划求解，或线性规划可解决哪些问题），以及用它们建立模型的方法，基本上不必涉及模型的求解。4）合适的数学软件的用法。基本上能完成上述方法的软件，如MATLAB,MATHEMATICA,LINDO等。6数学规划(最优化方法）7建立数学模型时要尽可能简单，而且要能完整地描述所研究的系统，具体建立怎样的数学模型需要丰富的经验和熟练的技巧。即使在建立了问题的数学模型之后，通常也必须对模型进行必要的数学简化以便于分析、计算。一般的模型简化工作包括以下几类：（1）将离散变量转化为连续变量。（2）将非线性函数线性化。（3）删除一些非主要约束条件。最优化问题的数学模型8建立最优化问题数学模型的三要素：（1）决策变量和参数。决策变量是由数学模型的解确定的未知数。参数表示系统的控制变量，有确定性的也有随机性的。（2）约束或限制条件。由于现实系统的客观物质条件限制，模型必须包括把决策变量限制在它们可行值之内的约束条件，而这通常是用约束的数学函数形式来表示的。（3）目标函数。这是作为系统决策变量的一个数学函数来衡量系统的效率，即系统追求的目标。9解：决定圆柱体表面积大小有两个决策变量：圆柱体底面半径r、高h。问题的约束条件是所铸圆柱体重量与球重相等。即3234Rhr1.0.R为金属比重例1.把半径为1的实心金属球熔化后，铸成一个实心圆柱体，问圆柱体取什么尺寸才能使它的表面积最小？10则得数学模型：s.t.Subjectto.034..22min22hrtsrrh222rrh问题目标是圆柱体表面积最小。即min0342hr即即342hr11rhhrLrrhLrhrhrL203402024222.323r3322h32326此时圆柱体的表面积为分别对r.h.λ求偏导数,并令其等于零.有:3422..22hrrrhhrL利用在高等数学中所学的Lagrange乘子法可求解本问题12例2、生产计划问题某厂利用a、b、c三种原料生产A、B、C三种产品，已知生产每种产品在消耗原料方面的各项技术条件和单位产品的利润，以及可利用的各种原料的量（具体数据如下表），试制订适当的生产规划使得该厂的总的利润最大。生产每单位产品所消耗的原料产品原料ABC现有原料的量a34260b21240c13280单位产品利润24313利润最大化）目标函数(约束条件一般数学模型0,,8023402260243..342max321321321321321xxxxxxxxxxxxtsxxxz以1x、2x、3x分别表示生产A、B、C三种产品的量，称之为决策变量14例3、运输问题假设某种产品有m个生产地，用)...2,1(miAi表示，其产量分别为(1,2...)isim；有n个消费地点，用)...2,1(njBj表示，需要该种物资，其需求量分别为(1,2...)jdjn。已知由第i个产地到第j个销地的单位物资运输成本为ijc。试构造一个运输方案，使总的运输成本最小。15运输问题数据表销地产地B1B2…Bn产量A1A2┇Amc11c12…c1nc21c22…c2n┇┇┇┇cm1cm2…cmns1s2┇sm销量d1d2…dn16销地产地B1B2…Bn产量A1A2┇Amx11x12…x1nx21x22…x2n┇┇┇┇xm1xm2…xmns1s2┇sm销量d1d2…dn设xij为从产地Ai运往销地Bj的运输量，根据这个运输问题的要求，可以建立运输变量表。17mnMinf=cijxiji=1j=1ns.t.xijsii=1,2,…,mj=1mxij(=,)djj=1,2,…,ni=1xij0(i=1,2,…,m;j=1,2,…,n)于是得到下列一般运输问题的模型：18mnMinf=cijxiji=1j=1ns.t.xij=sii=1,2,…,mj=1mxij=djj=1,2,…,ni=1xij≥0(i=1,2,…,m;j=1,2,…,n)对于产销平衡问题，可得到下列运输问题的模型：19在实际问题建模时，还会出现如下一些变化：（1）有时目标函数求最大，如求利润最大或营业额最大等；（2）当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束；产销不平衡的情况。当销量大于产量时可加入一个虚设的产地去生产不足的物资，当产量大于销量时可加入一个虚设的销地去消化多余的物资。20例4.多参数曲线拟合问题已知两个物理量x和y之间的依赖关系为:其中和待定参数,为确定这些参数,54321exp1ln1aaxaaay4321aaaa5a对x.y测得m个实验点:试将确定参数的问题表示成最优化问题..,,,2,21,1mmyxyxyx21解:很显然对参数和任意给定的一组数值,就由上式确定了y关于x的一个函数关系式,在几何上它对应一条曲线,这条曲线不一定通过那m个测量点,而要产生“偏差”.将测量点沿垂线方向到曲线的距离的平方和作为这种“偏差”的度量.即显然偏差S越小,曲线就拟合得越好,说明参数值就选择得越好，从而我们的问题就转化为5维无约束最优化问题。即：4321aaaa5amiiiaaxaaayS1254321exp1ln1xy22miiiaxxaaay1254321exp1ln1min23例5：两杆桁架的最优设计问题。由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2L，圆杆的壁厚为B，杆的比重为ρ，弹性模量为E，屈曲强度为δ。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均直径d。1p1p2pp2hhhL2受力分析图圆杆截面图Bp2hL2桁杆示意图d24解：桁杆的截面积为：桁杆的总重量为：负载2p在每个杆上的分力为：于是杆截面的应力为：此应力要求小于材料的屈曲极限，即圆杆中应力小于等于压杆稳定的临界应力。由材料力学知：压杆稳定的临界应力为由此得稳定约束：SdBS222hLdBWhhLppp221cosdhBhLsp2211dhBhLp22222228hLBdE082222222dhBhLphLBdE25另外还要考虑到设计变量d和h有界。从而得到两杆桁架最优设计问题的数学模型：minmaxminmax22222222222080..2minhhhddddhBhLphLBdEdhBhLptshLdB26例6(系统可靠性问题)在设计某些大型的系统工程时,常常要考虑它们的可靠性。设一个系统是由n个部件串联而成。为提高系统的可靠性,每个部件都装有备用件,一但原部件出现故障,备用件就自动进入系统。显然,备用件越多系统可靠性越大,但费用也越高，重量也越大,这在实际上是不行的。假定当部件k配置uk个备用件时,这个部件正常工作的概率为pk(uk),而每个备用件k的费用为ck,重量为ak。试在总费用不超过C,总重量不超过A的条件下决定各部件的备用件的数量,使得系统正常工作的概率最大。解因为系统正常工作的概率是各部件正常工作的概率的乘积,所以问题归纳为uk是正整数。nkkkup1)(maxnkkkCucts1.nkkkAua127min..01,2,,()()01,2,ijfxsthximPgxjp最优化问题的一般数学模型最优化问题的一般算法28整体（全局）最优解：若，对于一切，恒有则称是最优化问题的整体最优解。局部最优解：若，存在某邻域，使得对于一切，恒有则称是最优化问题的局部最优解。其中严格最优解：当，有则称为问题的严格最优解。*xDxD*fxfx*x*xD*()Nx*()xNxD*fxfx*x**(){|,0}Nxxxx*xx*fxfx*x29f(X)局部最优解整体最优解303使得或者某个kx恰好是问题的一个最优解，或者该点列kx收敛到问题的一个最优解*x。2产生可行点1x，2x，…，kx，…，记为kx；1给定一个初始可行点0xD；求解P的基本方法（迭代算法）：312以kx为出发点，作射线kkxp，其中0，在此射线上求一点1kx，1kx=kkkxp，使得1()()kkfxfx，其中k称为步长。1在可行域内kx点处求一个方向kp，称这个方向为下降方向或搜索方向；点列kx的产生，通常采取两步完成：下降算法：在迭代算法中，若1()()kkfxfx322、掌握用数学软件包求解数学规划问题。1、了解数学规划的基本内容。线性规划，无约束非线性规划，约束非线性规划33线性规划的模型的一般形式:目标函数满足约束条件通常称为决策变量，为价值系数，为消耗系数,为资源限制系数。1122nnmax(min)Z=cx+cx++cx1111221nn12112222nn2m11m22mnnm12naxaxax(,)baxaxax(,)baxaxax(,)bx,x,x012nx,x,,x12nc,c,,c1112mna,a,,a12mb,b,,b线性规划34minf=cxs.t.Ax=b（1）x0这里A=(ija)m,n,x=T21nxxxb=T21nbbb,c=nccc21用单纯法求解时，常将标准形式化为：线性规划的基本算法——单纯形法35用MATLAB优化工具箱解线性规划minz=cXbAXts..1、模型：命令：x=linprog（c，A，b）2、模型：minz=cXbAXts..beqXAeq命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式：存在，则令A=[]，b=[].bAX363、模型：minz=cXbAXts..beqXAeq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表示初始点beqXAeq4、命令：[x,fval]=linprog(…)返回最优解ｘ及ｘ处的目标函数值fval.37问题：任务分配问