《数学建模～最优化模型(课件).ppt》由会员分享，可在线阅读，更多相关《数学建模～最优化模型(课件).ppt（64页珍藏版）》请在三一办公上搜索。
1、最优化方法,2014数学建模培训,许丽艳 20140120,最优化模型,一、最优化方法概述,二、无约束最优化问题,三、无约束最优化问题的MATLAB求解,四、有约束最优化问题,最优化方法概述,1、最优化理论和方法是近二十多年来发展十分迅速的一个数学分支。2、在数学上，最优化是一种求极值的方法。3、最优化已经广泛的渗透到工程、经济、电子技术等领域。,在实际生活当中，人们做任何事情，不管是分析问题，还是进行决策，都要用一种标准衡量一下是否达到了最优。（比如基金人投资）在各种科学问题、工程问题、生产管理、社会经济问题中，人们总是希望在有限的资源条件下，用尽可能小的代价，获得最大的收获。（比如保险）,
2、数学家对最优化问题的研究已经有很多年的历史。以前解决最优化问题的数学方法只限于古典求导方法和变分法（求无约束极值问题），拉格朗日（Lagrange）乘数法解决等式约束下的条件极值问题。计算机技术的出现，使得数学家研究出了许多最优化方法和算法用以解决以前难以解决的问题。,几个概念,最优化是从所有可能方案中选择最合理的一种以达到最优目标的学科。最优方案是达到最优目标的方案。最优化方法是搜寻最优方案的方法。最优化理论就是最优化方法的理论。,经典极值问题,包括：无约束极值问题约束条件下的极值问题,1、无约束极值问题的数学模型,2、约束条件下极值问题的数学模型,其中，极大值问题可以转化为极小值问题来进行
3、求解。如求：,可以转化为：,1、无约束极值问题的求解,例1：求函数y=2x3+3x2-12x+14在区间-3,4上的最大值与最小值。解：令f(x)=y=2x3+3x2-12x+14 f(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解无约束优化问题,其中等式（3）、（4）、（5）的右边可选用（1）或（2）的等式右边.它要求目标函数必须是连续函
4、数，并可能只给出局部最优解.,常用格式如下：（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（）,MATLAB(wliti1),主程序为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
5、 有边长为3m的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？,解,先编写M文件fun0.m如下:function f=fun0(x)f=-(3-2*x).2*x;,主程序为wliti2.m:x,fval=fminbnd(fun0,0,1.5);xmax=x fmax=-fval,运算结果为:xmax=0.5000,fmax=2.0000.即剪掉的正方形的边长为0.5m时水槽的容积最大,最大容积为2m3.,MATLAB(wliti2),命令格式为:（1）x=fminunc（fun,X0）；或x=fminsearch（fun,X0）（2）x=fminunc（
6、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,例 用fminsearch函数求解,输入命令:f=100*(x(2)-x(1)2)2+(1-x(1)2;x,fval
7、,exitflag,output=fminsearch(f,-1.2 2),运行结果:x=1.0000 1.0000fval=1.9151e-010exitflag=1output=iterations:108 funcCount:202 algorthm:Nelder-Mead simplex direct search,有约束最优化最优化方法分类（一）线性最优化：目标函数和约束条件都是线性的则称为线性最优化。非线性最优化：目标函数和约束条件如果含有非线性的，则称为非线性最优化。（二）静态最优化：如果可能的方案与时间无关，则是静态最优化问题。动态最优化：如果可能的方案与时间有关，则是动态最优
8、化问题,有约束最优化问题的数学建模,有约束最优化模型一般具有以下形式：,或,其中f(x)为目标函数，省略号表示约束式子，可以是等式约束，也可以是不等式约束。,根据目标函数，约束条件的特点将最优化方法包含的主要内容大致如下划分：线性规划整数规划非线性规划动态规划多目标规划 对策论,最优化方法主要内容,两个引例,问题一：某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示,该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元。问应如何安排计划使该工厂获利最多？,解：该工厂生产产品I x1件，生产产品II x2件，我们可建立如下数学
9、模型：,s.t.,问题二：某厂每日8小时的产量不低于1800件.为了进行质量控制，计划聘请两种不同水平的检验员.一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15件/小时，正确率95%，计时工资3元/小时.检验员每错检一次，工厂要损失2元.为使总检验费用最省，该工厂应聘一级、二级检验员各几名？,解 设需要一级和二级检验员的人数分别为x1、x2人,则应付检验员的工资为：,因检验员错检而造成的损失为：,故目标函数为：,约束条件为：,运用最优化方法解决最优化问题的一般方法步骤如下：前期分析：分析问题，找出要解决的目标，约束条件，并确立最优化的目标。定
10、义变量，建立最优化问题的数学模型，列出目标函数和约束条件。针对建立的模型，选择合适的求解方法或数学软件。编写程序，利用计算机求解。对结果进行分析，讨论诸如：结果的合理性、正确性，算法的收敛性，模型的适用性和通用性，算法效率与误差等。,线 性 规 划,某豆腐店用黄豆制作两种不同口感的豆腐出售。制作口感较鲜嫩的豆腐每千克需要0.3千克一级黄豆及0.5千克二级黄豆，售价10元；制作口感较厚实的豆腐每千克需要0.4千克一级黄豆及0.2千克二级黄豆，售价5元。现小店购入9千克一级黄豆和8千克二级黄豆。问：应如何安排制作计划才能获得最大收益。,一、问题前期分析该问题是在不超出制作两种不同口感豆腐所需黄豆总
11、量条件下合理安排制作计划，使得售出各种豆腐能获得最大收益。二、模型假设1假设制作的豆腐能全部售出。2假设豆腐售价无波动。,变量假设：设计划制作口感鲜嫩和厚实的豆腐各x1千克和 x2千克，可获得收益R元。,目标函数：获得的总收益最大。,总收益可表示为：,受一级黄豆数量限制：,受二级黄豆数量限制：,综上分析，得到该问题的线性规划模型,s.t.,用Matlab编程求解程序如下：X,FVAL,EXITFLAG,OUTPUT=LINPROG(f,A,b)f=-10 5;A=0.3 0.4;0.5 0.2;B=9;8;X,FVAL,EXITFLAG,OUTPUT=LINPROG(f,A,b),X=10.0
12、000 15.0000FVAL=-175.0000,用YALMIP编程求解程序如下：x=sdpvar(1,2);C=10 5;a=0.3 0.4;0.5 0.2;b=9 8;f=C*x;F=set(0=x=inf);F=F+set(a*x=b);solvesdp(F,-f)double(f)double(x),ans=175ans=10 15,线 性 规 划,设某工厂有甲、乙、丙、丁四个车间，生产A、B、C、D、E、F六种产品。根据机床性能和以前的生产情况，得知每单位产品所需车间的工作小时数、每个车间在一个季度工作小时的上限以及单位产品的利润，如下表所示(例如，生产一个单位的A产品，需要甲、乙
13、、丙三个车间分别工作1小时、2小时和4小时)问：每种产品各应该每季度生产多少，才能使这个工厂每季度生产利润达到最大。,这是一个典型的最优化问题，属线性规划。假设：产品合格且能及时销售出去；工作无等待情况等 变量说明：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种产品所花时间总数；,于是，我们可建立如下数学模型：,s.t.,计算结果：,运 输 问 题,要从甲城调出蔬菜2000吨，从乙城调出蔬
14、菜2500吨，从丙地调出3000吨，分别供应A地2000吨，B地2300吨、C地1800吨、D地1400吨，已知每吨运费如下表：,问：如何调拨才能使运费最省？,假设：假设题目中所给运费已考虑各地间公里数；只考虑运量和运费，不考虑车辆调拨等其它相关因素不考虑车辆返空的费用（或：所给运费已包含车辆返空的费用）变量说明：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地所需蔬菜总量,可以建立如下模型：,s.t.,整 数 规 划,最优化问题中的所有变量均为整数时，
15、这类问题称为整数规划问题。如果线性规划中的所有变量均为整数时，称这类问题为线性整数规划问题。整数规划可分为线性整数规划和非线性整数规划，以及混合整数规划等。如果决策变量的取值要么为0，要么为1，则这样的规划问题称为01规划。,例1 某钢厂两个炼钢炉同时各用一种方法炼钢。第一种炼法每炉用a小时，第二种用b小时（包括清炉时间）。假定这两种炼法，每炉出钢都是k公斤，而炼1公斤钢的平均燃料费第一法为m元，第二法为n元。若要求在c小时内炼钢公斤数不少于d，试列出燃料费最省的两种方法的分配方案的数学模型。,设用第一种炼法炼钢x1炉，第二种炼钢x2炉,s.t.,引例2.资源分配问题：某个中型的百货商场要求售
16、货人员每周工作5天，连续休息2天，工资200元/周，已知对售货人员的需求经过统计分析如下表，问如何安排可使配备销售人员的总费用最少？,非线性规划,非线性规划问题的一般数学模型：其中，为目标函数，为约束函数，这些函数中至少有一个是非线性函数。,应用实例：供应与选址,某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：km）及水泥日用量d(t)由下表给出目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20t假设从料场到工地之间均有直线道路相连（1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少水泥，可使总的吨千米数最小（2）为了进一步减少吨千米数，
17、打算舍弃两个临时料场，改建两个新的，日储量各为20t，问应建在何处，节省的吨千米数有多大？,（一）建立模型,记工地的位置为(ai，bi)，水泥日用量为di，i=1,6;料场位置为(xj，yj)，日储量为ej，j=1,2；料场j向工地i的运送量为Xij,当用临时料场时决策变量为：Xij，当不用临时料场时决策变量为：Xij，xj，yj,多目标规划,引例1.投资问题 某公司在一段时间内有a(亿元)的资金可用于建厂投资。若可供选择的项目记为1,2,m。而且一旦对第i个项目投资就用去ai亿元；而这段时间内可得收益ci亿元。问如何确定最佳的投资方案？,最佳投资方案：投资最少，收益最大！,投资最少：,约束条
18、件为：,收益最大：,引例2：生产问题 某工厂生产两种产品，产品A每单位利润为10元，而产品B每单位利润为8元；产品A每单位需3小时装配时间而B为2小时，每周总装配有效时间为120小时。工厂允许加班，但加班生产出来的产品利润要减去1元。根据最近的合同，厂商每周最少的向用户提供两种产品各30单位。要求：必须遵守合同；尽可能少加班；利润最大。问应怎样安排生产？,x1：每周正常时间生产得A产品的数量；x2：每周加班时间生产得A产品的数量；x3：每周正常时间生产得B产品的数量；x4：每周加班时间生产得B产品的数量；,目标函数（有两个）：,Nonlinear minimization of functio
19、ns.fminbnd-Scalar bounded nonlinear function minimization.fmincon-Multidimensional constrained nonlinear minimization.fminsearch-Multidimensional unconstrained nonlinear minimization,by Nelder-Mead direct search method.fminunc-Multidimensional unconstrained nonlinear minimization.fseminf-Multidimens
20、ional constrained minimization,semi-infinite constraints.ktrlink-Multidimensional constrained nonlinear minimization using KNITRO(R)third-party libraries.Nonlinear minimization of multi-objective functions.fgoalattain-Multidimensional goal attainment optimization fminimax-Multidimensional minimax op
21、timization.,linprog,f=-10 5;A=0.3 0.4;0.5 0.2;B=9;8;X,FVAL,EXITFLAG,OUTPUT=LINPROG(f,A,b),quadprog,fminbnd,Examples FUN can be specified using:X=fminbnd(cos,3,4)computes pi to a few decimal places and gives a message upon termination.X,FVAL,EXITFLAG=fminbnd(cos,3,4,optimset(TolX,1e-12,Display,off)co
22、mputes pi to about 12 decimal places,suppresses output,returns the function value at x,and returns an EXITFLAG of 1.FUN can be an anonymous function:X=fminbnd(x)sin(x)+3,2,5)FUN can be a parameterized function.Use an anonymous function to capture the problem-dependent parameters:f=(x,c)(x-c).2;%The
23、parameterized function.c=1.5;%The parameter.X=fminbnd(x)f(x,c),0,1),fminsearch,Examples FUN can be specified using:X=fminsearch(sin,3)finds a minimum of the SIN function near 3.In this case,SIN is a function that returns a scalar function value SIN evaluated at X.FUN can be an anonymous function:X=f
24、minsearch(x)norm(x),1;2;3)returns a point near the minimizer 0;0;0.FUN can be a parameterized function.Use an anonymous function to capture the problem-dependent parameters:f=(x,c)x(1).2+c.*x(2).2;%The parameterized function.c=1.5;%The parameter.X=fminsearch(x)f(x,c),0.3;1),fminunc,fminunc finds a l
25、ocal minimum of a function of several variables.X=fminunc(FUN,X0)starts at X0 and attempts to find a local minimizer X of the function FUN.FUN accepts input X and returns a scalar function value F evaluated at X.X0 can be a scalar,vector or matrix.,x=fminunc(x)5*x(1)2+x(2)2,5;1),fminsearch,help fmin
26、search fminsearch Multidimensional unconstrained nonlinear minimization(Nelder-Mead).X=fminsearch(FUN,X0)starts at X0 and attempts to find a local minimizer X of the function FUN.FUN is a function handle.FUN accepts input X and returns a scalar function value F evaluated at X.X0 can be a scalar,vect
27、or or matrix.,例子,X=fminsearch(x)norm(x),1;2;3)f=(x,c)x(1).2+c.*x(2).2;%The parameterized function.c=1.5;%The parameter.X=fminsearch(x)f(x,c),0.3;1),fmincon,%optimset,bintprog Binary integer programming.bintprog solves the binary integer programming problem min f*X subject to:A*X=b,Aeq*X=beq,where th
28、e elements of X are binary integers,i.e.,0s or 1s.X=bintprog(f)solves the problem min f*X,where the elements of X are binary integers.,X=bintprog(f,A,b)solves the problem min f*X subject to the linear inequalities A*X=b,where the elements of X are binary integers.X=bintprog(f,A,b,Aeq,beq)solves the
29、problem min f*X subject to the linear equalities Aeq*X=beq,the linear inequalities A*X=b,where the elements of X are binary integers.X=bintprog(f,A,b,Aeq,beq,X0)sets the starting point to X0.The starting point X0 must be binary integer and feasible,or it will be ignored.,Example f=-9;-5;-6;-4;A=6 3 5 2;0 0 1 1;-1 0 1 0;0-1 0 1;b=9;1;0;0;X=bintprog(f,A,b),
