数学建模～最优化模型(课件ppt).

最优化模型一、最优化方法概述二、无约束最优化问题三、无约束最优化问题的MATLAB求解四、有约束最优化问题最优化方法概述1、最优化理论和方法是近二十多年来发展十分迅速的一个数学分支。2、在数学上，最优化是一种求极值的方法。3、最优化已经广泛的渗透到工程、经济、电子技术等领域。•在实际生活当中，人们做任何事情，不管是分析问题，还是进行决策，都要用一种标准衡量一下是否达到了最优。（比如基金人投资）•在各种科学问题、工程问题、生产管理、社会经济问题中，人们总是希望在有限的资源条件下，用尽可能小的代价，获得最大的收获。（比如保险）数学家对最优化问题的研究已经有很多年的历史。以前解决最优化问题的数学方法只限于古典求导方法和变分法（求无约束极值问题），拉格朗日（Lagrange）乘数法解决等式约束下的条件极值问题。计算机技术的出现，使得数学家研究出了许多最优化方法和算法用以解决以前难以解决的问题。几个概念•最优化是从所有可能方案中选择最合理的一种以达到最优目标的学科。•最优方案是达到最优目标的方案。•最优化方法是搜寻最优方案的方法。•最优化理论就是最优化方法的理论。经典极值问题包括：①无约束极值问题②约束条件下的极值问题1、无约束极值问题的数学模型min()xfx2、约束条件下极值问题的数学模型min()xfx..()0,1,2,...,()0,1,2,...,iistgximhxin其中，极大值问题可以转化为极小值问题来进行求解。如求：max()xfx可以转化为：min()xfx1、无约束极值问题的求解例1：求函数y=2x3+3x2-12x+14在区间[-3,4]上的最大值与最小值。解：令f(x)=y=2x3+3x2-12x+14f’(x)=6x2+6x-12=6(x+2)(x-1)解方程f’(x)=0，得到x1=-2，x2=1，又由于f(-3)=23，f(-2)=34，f(1)=7，f(4)=142，综上得，函数f(x)在x=4取得在[-3,4]上得最大值f(4)=142，在x=1处取得在[-3,4]上取得最小值f(1)=7用MATLAB解无约束优化问题1.一元函数无约束优化问题:min()fx21xxx其中等式（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（…）运行结果：xmin=3.9270ymin=-0.0279xmax=0.7854ymax=0.6448MATLAB(wliti1)例1求x=2esinxx在0x8中的最小值与最大值.主程序为wliti1.m:f='2*exp(-x).*sin(x)';fplot(f,[0,8]);%作图语句[xmin,ymin]=fminbnd(f,0,8)f1='-2*exp(-x).*sin(x)';[xmax,ymax]=fminbnd(f1,0,8)例2有边长为3m的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？设剪去的正方形的边长为x，则水槽的容积为：xx2)23(建立无约束优化模型为：miny=-xx2)23(，0x1.5解先编写M文件fun0.m如下:functionf=fun0(x)f=-(3-2*x).^2*x;主程序为wliti2.m:[x,fval]=fminbnd('fun0',0,1.5);xmax=xfmax=-fval运算结果为:xmax=0.5000,fmax=2.0000.即剪掉的正方形的边长为0.5m时水槽的容积最大,最大容积为2m3.MATLAB(wliti2)命令格式为:（1）x=fminunc（fun,X0）；或x=fminsearch（fun,X0）（2）x=fminunc（fun,X0，options）；或x=fminsearch（fun,X0，options）（3）[x，fval]=fminunc（...）；或[x，fval]=fminsearch（...）（4）[x，fval，exitflag]=fminunc（...）；或[x，fval，exitflag]=fminsearch（5）[x，fval，exitflag，output]=fminunc（...）；或[x，fval，exitflag，output]=fminsearch（...）2.多元函数无约束优化问题标准型为：min()FX例用fminsearch函数求解输入命令:f='100*(x(2)-x(1)^2)^2+(1-x(1))^2';[x,fval,exitflag,output]=fminsearch(f,[-1.22])运行结果:x=1.00001.0000fval=1.9151e-010exitflag=1output=iterations:108funcCount:202algorthm:'Nelder-Meadsimplexdirectsearch'有约束最优化最优化方法分类（一）线性最优化：目标函数和约束条件都是线性的则称为线性最优化。非线性最优化：目标函数和约束条件如果含有非线性的，则称为非线性最优化。（二）静态最优化：如果可能的方案与时间无关，则是静态最优化问题。动态最优化：如果可能的方案与时间有关，则是动态最优化问题有约束最优化问题的数学建模有约束最优化模型一般具有以下形式：min()........xfxst或max()........xfxst其中f(x)为目标函数，省略号表示约束式子，可以是等式约束，也可以是不等式约束。根据目标函数，约束条件的特点将最优化方法包含的主要内容大致如下划分：线性规划整数规划非线性规划动态规划多目标规划对策论最优化方法主要内容两个引例问题一：某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示12kg40原材料B16kg04原材料A8台时21设备III该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元。问应如何安排计划使该工厂获利最多？解：该工厂生产产品Ix1件，生产产品IIx2件，我们可建立如下数学模型：2132maxxxz0,12416482212121xxxxxxs.t.问题二：某厂每日8小时的产量不低于1800件.为了进行质量控制，计划聘请两种不同水平的检验员.一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15件/小时，正确率95%，计时工资3元/小时.检验员每错检一次，工厂要损失2元.为使总检验费用最省，该工厂应聘一级、二级检验员各几名？解设需要一级和二级检验员的人数分别为x1、x2人,则应付检验员的工资为：212124323848xxxx因检验员错检而造成的损失为：21211282)%5158%2258(xxxx故目标函数为：2121213640)128()2432(minxxxxxxz约束条件为：0,18001582582121xxxx运用最优化方法解决最优化问题的一般方法步骤如下：①前期分析：分析问题，找出要解决的目标，约束条件，并确立最优化的目标。②定义变量，建立最优化问题的数学模型，列出目标函数和约束条件。③针对建立的模型，选择合适的求解方法或数学软件。④编写程序，利用计算机求解。⑤对结果进行分析，讨论诸如：结果的合理性、正确性，算法的收敛性，模型的适用性和通用性，算法效率与误差等。线性规划某豆腐店用黄豆制作两种不同口感的豆腐出售。制作口感较鲜嫩的豆腐每千克需要0.3千克一级黄豆及0.5千克二级黄豆，售价10元；制作口感较厚实的豆腐每千克需要0.4千克一级黄豆及0.2千克二级黄豆，售价5元。现小店购入9千克一级黄豆和8千克二级黄豆。问：应如何安排制作计划才能获得最大收益。一、问题前期分析该问题是在不超出制作两种不同口感豆腐所需黄豆总量条件下合理安排制作计划，使得售出各种豆腐能获得最大收益。二、模型假设1．假设制作的豆腐能全部售出。2．假设豆腐售价无波动。变量假设：设计划制作口感鲜嫩和厚实的豆腐各x1千克和x2千克，可获得收益R元。目标函数：获得的总收益最大。总收益可表示为：21510xxR受一级黄豆数量限制：受二级黄豆数量限制：94.03.021xx82.05.021xx综上分析，得到该问题的线性规划模型21510maxxxR94.03.021xx82.05.021xx0,21xxs.t.用Matlab编程求解程序如下：[X,FVAL,EXITFLAG,OUTPUT]=LINPROG(f,A,b)f=-[105];A=[0.30.4;0.50.2];B=[9;8];[X,FVAL,EXITFLAG,OUTPUT]=LINPROG(f,A,b)X=10.000015.0000FVAL=-175.0000用YALMIP编程求解程序如下：x=sdpvar(1,2);C=[105];a=[0.30.4;0.50.2];b=[98];f=C*x';F=set(0=x=inf);F=F+set(a*x'=b');solvesdp(F,-f)double(f)double(x)ans=175ans=1015线性规划设某工厂有甲、乙、丙、丁四个车间，生产A、B、C、D、E、F六种产品。根据机床性能和以前的生产情况，得知每单位产品所需车间的工作小时数、每个车间在一个季度工作小时的上限以及单位产品的利润，如下表所示(例如，生产一个单位的A产品，需要甲、乙、丙三个车间分别工作1小时、2小时和4小时)问：每种产品各应该每季度生产多少，才能使这个工厂每季度生产利润达到最大。生产单位产品所需车间的工作小时数ABCDEF每个车间一个季度工作小时的上限甲111323500乙255500丙425500丁138500利润(百元)4.02.45.55.04.58.5这是一个典型的最优化问题，属线性规划。假设：产品合格且能及时销售出去；工作无等待情况等变量说明：xj：第j种产品的生产量（j=1,2,……,6）aij：第i车间生产单位第j种产品所需工作小时数（i=1,2,3,4;j=1,2,……,6）bi：第i车间的最大工作上限cj：第j种产品的单位利润则：cjxj为第j种产品的利润总额；aijxj表示第i车间生产第j种产品所花时间总数；于是，我们可建立如下数学模型：61maxjjjxcz6,5,4,3,2,1,}{max04,3,2,14161jabxibxaijiijjijij且为整数s.t.计算结果：Z(百元)x1x2x3x4x5x6132000604010040运输问题要从甲城调出蔬菜2000吨，从乙城调出蔬菜2500吨，从丙地调出3000吨，分别供应A地2000吨，B地2300吨、C地1800吨、D地1400吨，已知每吨运费如下表：供应单位调出单位ABCD甲21271340乙45513720丙32352030问：如何调拨才能使运费最省？假设：①假设题目中所给运费已考虑各地间公里数；②只考虑运量和运费，不考虑车辆调拨等其它相关因素③不考虑车辆返空的费用（或：所给运费已包含车辆返空的费用）变量说明：xij:从第i城运往第j地的蔬菜数量（i=1,2,3;j=1,2,3,4）aij:从第i城运往第j地的单位运费（i=1,2,3;j=1,2,3,4）bi:从第i城调出的蔬菜总量cj:第j地所需蔬菜总量可以建立如下模型：3141minijijijxaz4131(1,2,3