数学建模最优化市公开课一等奖百校联赛特等奖课件.pptx

12几类经典优化问题及其软件解法几类经典优化问题及其软件解法3举例举例4最优化概论最优化概论MATLAB优化工具箱介绍优化工具箱介绍第1页最优化概论最优化概论v当今，当今，“优化优化”无疑是一个热门词。做宏观经济无疑是一个热门词。做宏观经济规划要优化资源配置，搞企业经营管理要优化生规划要优化资源配置，搞企业经营管理要优化生产计划，作新产品设计要优化性能成本比。就是产计划，作新产品设计要优化性能成本比。就是在人们日常生活中，优化要求也比比皆是，消费在人们日常生活中，优化要求也比比皆是，消费时，怎样花尽可能少钱办尽可能多事，出行时，时，怎样花尽可能少钱办尽可能多事，出行时，怎样走最短旅程抵达目标地，等等。总而言之，怎样走最短旅程抵达目标地，等等。总而言之，在经济如此发展，竞争如此猛烈，资源日渐担心在经济如此发展，竞争如此猛烈，资源日渐担心今天，人们做任何事，无不望求事半功倍之术，今天，人们做任何事，无不望求事半功倍之术，以求或提效、或增收、或节约等等之目标。以求或提效、或增收、或节约等等之目标。第2页一、最优化概念一、最优化概念v全部类似这种课题统称为最优化问题，研究处理全部类似这种课题统称为最优化问题，研究处理这些问题科学普通就总称之为这些问题科学普通就总称之为最优化理论和方法最优化理论和方法v另外也可用学术味更浓名称：另外也可用学术味更浓名称：“运筹学运筹学”。因为。因为最优化问题背景十分广泛，包括知识不尽相同，最优化问题背景十分广泛，包括知识不尽相同，学科分枝很多，所以这个学科名下到底包含哪些学科分枝很多，所以这个学科名下到底包含哪些分枝，其说法也不一致。分枝，其说法也不一致。v比较公认是：比较公认是：“规划论规划论”（包含线性和非线性规（包含线性和非线性规划、整数规划、动态规划、多目标规划和随机规划、整数规划、动态规划、多目标规划和随机规划等），划等），“组合最优化组合最优化”，“对策论对策论”及及“最优最优控制控制”等等。等等。第3页数学建模竞赛中优化问题数学建模竞赛中优化问题vB钢管订购和运输问题钢管订购和运输问题二次规划二次规划vB公交车优化调度公交车优化调度vC基金使用最优策略基金使用最优策略-线性规划线性规划vB彩票中数学彩票中数学vB露天矿生产车辆安排问题露天矿生产车辆安排问题 vA奥运会暂时超市网点设计问题奥运会暂时超市网点设计问题 vD公务员招聘工作中录用方案公务员招聘工作中录用方案多目标规划多目标规划vBDVD在线租赁在线租赁vA出版社资源配置问题出版社资源配置问题 vA乘公交，看奥运乘公交，看奥运 vB高等教育学费探讨高等教育学费探讨vB眼科病床合理安排眼科病床合理安排 第4页数学建模竞赛中优化问题数学建模竞赛中优化问题vB，彩票中数学彩票中数学约束非线性规划约束非线性规划第5页v从数学上来看，所谓最优化问题能够概括为这么从数学上来看，所谓最优化问题能够概括为这么一个数学模型：给定一个一个数学模型：给定一个“函数函数”，F(X)F(X)，以及，以及“自变量自变量”X X应满足一定条件，求应满足一定条件，求X X为怎样值时，为怎样值时，F(X)F(X)取得其最大值或最小值。通常，称取得其最大值或最小值。通常，称F(X)F(X)为为“目标函数目标函数”，X X应满足条件为应满足条件为“约束条件约束条件”。约束。约束条件普通用一个集合条件普通用一个集合D D表示为：表示为：XDXD。v求目标函数求目标函数F(X)F(X)在约束条件在约束条件XDXD下最小值或最大下最小值或最大值问题，就是普通最优问题数学模型值问题，就是普通最优问题数学模型第6页无约束最优化问题无约束最优化问题目标函数目标函数 二、最优化问题普通形式二、最优化问题普通形式约束最优化问题约束最优化问题约束函数约束函数 最优解；最优值最优解；最优值第7页三、最优化问题分类三、最优化问题分类分类分类1 1：无约束最优化无约束最优化 约束最优化约束最优化 非线性规划：非线性规划：目标函数与约束函数中最少有一个目标函数与约束函数中最少有一个是变量是变量x x非线性函数；非线性函数；线性规划：线性规划：目标函数与约束函数均为线性函数；目标函数与约束函数均为线性函数；分类分类2 2：线性规划线性规划 非线性规划非线性规划第8页三、最优化问题分类三、最优化问题分类(续）续）分类分类3 3（依据决议变量、（依据决议变量、目标函数和要求目标函数和要求不一样）不一样）整数规划整数规划动态规划动态规划网络规划网络规划随机规划随机规划几何规划几何规划多目标规划多目标规划第9页三、最优化问题分类三、最优化问题分类(续）续）函数最优化函数最优化组合最优化组合最优化分类分类函数最优化：函数最优化：决议变量是一定区间内连续变量决议变量是一定区间内连续变量 组合最优化：组合最优化：决议变量是离散状态，同时可行域是决议变量是离散状态，同时可行域是由有限个点组成集合由有限个点组成集合 经典组合优化问题：经典组合优化问题：旅行商问题；加工调度问题；旅行商问题；加工调度问题；0-10-1背包问题；图着色问题背包问题；图着色问题第10页四、求解最优化问题方法四、求解最优化问题方法（1 1）传统优化方法）传统优化方法-基于导数优化方法基于导数优化方法 无约束规划：无约束规划：梯度法、共轭梯度法、拟牛顿法梯度法、共轭梯度法、拟牛顿法 约束规划：约束规划：序列二次规划法，罚函数法序列二次规划法，罚函数法 线性规划：线性规划：单纯形方法等单纯形方法等（2 2）当代优化方法）当代优化方法-智能优化方法智能优化方法 遗传算法，模拟退火法，蚁群算法，粒子群算法遗传算法，模拟退火法，蚁群算法，粒子群算法 神经网络算法，禁忌搜索算法等神经网络算法，禁忌搜索算法等 为了使系统到达最优目标所提出各种求解方法为了使系统到达最优目标所提出各种求解方法称为称为最优化方法最优化方法。第11页最优化方法通常采取迭代法求最优解，过程是最优化方法通常采取迭代法求最优解，过程是：五、结构数值优化算法普通过程五、结构数值优化算法普通过程或或迭代公式迭代公式第12页六、最优化方法基本结构六、最优化方法基本结构第13页七、搜索算法结构框图七、搜索算法结构框图线性搜索求线性搜索求 ，使使x(k+1)S初始初始x(1)S,k=1对对x(k)点选择下降点选择下降可行方向可行方向d(k)是否满足停机条件？是否满足停机条件？停停k=k+1YesNo第14页八、最优化方法处理问题步骤八、最优化方法处理问题步骤（1）确定变量，写出目标函数和相关约束条件，建）确定变量，写出目标函数和相关约束条件，建立数学模型。立数学模型。（2）分析模型，）分析模型，搞清它属于运筹学哪一分枝搞清它属于运筹学哪一分枝，选择选择适当最优化方法；适当最优化方法；（3）编程求解；）编程求解；尽可能利用现有数学软件或最优化尽可能利用现有数学软件或最优化软件，比如软件，比如 MatlabMatlab，MathematicaMathematica，LindoLindo，LingoLingo等，来计算。等，来计算。（4）最优解验证和实施。）最优解验证和实施。第15页九、九、MATLABMATLAB优化工具箱介绍优化工具箱介绍v1.功效功效v（1）求解无约束条件非线性极小值；）求解无约束条件非线性极小值；v（2）求解约束条件下非线性极小值，包含目标迫）求解约束条件下非线性极小值，包含目标迫近问题、极大近问题、极大-极小值问题和半无限极小值问题；极小值问题和半无限极小值问题；v（3）求解二次规划和线性规划问题；）求解二次规划和线性规划问题；v（4）非线性最小二乘迫近和曲线拟合；）非线性最小二乘迫近和曲线拟合；v（5）非线性系统方程求解；）非线性系统方程求解；v（6）约束条件下线性最小二乘优化；）约束条件下线性最小二乘优化；v（7）求解复杂结构大规模优化问题。）求解复杂结构大规模优化问题。第16页2.惯用函数：惯用函数：一元函数极小值一元函数极小值 X=fminbnd(F,x1,x2,options)无约束极小值无约束极小值 X=fminunc(F,X0,options)X=fminsearch(F,X0,options)线性规划线性规划 X=linprog(c,A,b,options)0-1整数规划整数规划 X=bintprog(F,options)二次规划二次规划X=quadprog(H,c,A,b,options)约束非线性规划极小值约束非线性规划极小值X=fmincon(FG,X0,options)非线性最小二乘非线性最小二乘 X=lsqnonlin(F,X0,options)v目标抵达问题X=fgoalattain(F,x,goal,w)极小极大问题极小极大问题X=fminimax(FG,x0)第17页3.Options选项说明选项说明v输入参数中能够用输入参数中能够用options，用于全部函数，其中包含有，用于全部函数，其中包含有一下参数。一下参数。v（1）Display：结果显示方式，：结果显示方式，off不显示，不显示，iter显示每显示每次迭代信息，次迭代信息，final为最终止果，为最终止果，notify只有当求解不收只有当求解不收敛时候才显示结果。敛时候才显示结果。v（2）MaxFunEvals：允许函数计算最大次数，取值为：允许函数计算最大次数，取值为正整数。正整数。v（3）MaxIter：允许迭代最大次数，正整数。：允许迭代最大次数，正整数。v（4）TolFun：函数值（计算结果）精度，正整数。：函数值（计算结果）精度，正整数。v（5）TolX：自变量精度，正整数。：自变量精度，正整数。v而且能够用函数而且能够用函数optimset创建和修改。创建和修改。第18页4.输出变量说明输出变量说明变量变量描描 述述调用函数调用函数xv由优化函数求得值.若exitflag0,则x为解;不然,x不是最终解,它只是迭代阻止时优化过程值v全部优化函数fvalv解x处目标函数值linprog,quadprog,fgoalattain,fmincon,fminimax,lsqcurvefit,lsqnonlin,fminbndexitflagv描述退出条件:vexitflag0,表目标函数收敛于解x处vexitflag=0,表已抵达函数评价或迭代最大次数vexitflag0,表目标函数不收敛outputv包含优化结果信息输出结构.vIterations:迭代次数vAlgorithm:所采取算法vFuncCount:函数评价次数v全部优化函数第19页数模竞赛培训几类经典最优化问题几类经典最优化问题及软件解法及软件解法第20页线性规划问题及其线性规划问题及其MATLABMATLAB解法解法1.线性规划普通形式线性规划普通形式或或第21页线性规划问题及其线性规划问题及其MATLABMATLAB解法解法2.线性规划线性规划matlab解法解法问题形式问题形式1：minz=CTxS.t.A xb指令：（指令：（x，z）=linprog(f,A,b)问题形式问题形式2：minz=CTxS.t.A xbAeq x=beq指令：（指令：（x，z）=linprog(f,A,b,Aeq,beq)第22页线性规划问题及其线性规划问题及其MATLABMATLAB解法解法问题形式问题形式3：minz=CTxS.t.A xbAeq x=beqlbxub指令：（指令：（x，z）=linprog(f,A,b,Aeq,beq,lb,ub)注：注：若没有不等式约束若没有不等式约束,可用可用 替换替换A和和b,若没有等式约束若没有等式约束,可用可用 替换替换Aeq和和beq,若某个若某个xi下无界或上无界下无界或上无界,可设定可设定-inf或或 inf；第23页x1+x2 5,-6 x1 10,-1 x2 4;4;例例:min Z=4x1+3x2s.t.解：程序以下解：程序以下c=4,3;a=1,1;b=5;c=4,3;a=1,1;b=5;vlb=-6;-1;vlb=-6;-1;%lower bound of vector x%vub=10;4;vub=10;4;%upper bound of vector x%X,z=linprog(c,a,b,vlb,vub)X,z=linprog(c,a,b,vlb,vub)第24页1.整数线性规划普通形式整数线性规划普通形式依依照照决决议议变变量量取取整整要要求求不不一一样样，整整数数规规划划可可分分为为纯纯整整数数规规划划、混混合合整整数数规规划划、0 01 1整整数数规划。规划。整数线性规划整数线性规划(ILP)及其及其lindo解法解法部分或者全部为整数部分或者全部为整数第25页2、整数规划计算机求解方法整数规划计算机求解方法 当前，求解整数规划模型现成数学软件有：当前，求解整数规划模型现成数学软件有：Lindo,LingoLindo,Lingo和和MatlabMatlab,其中其中LindoLindo和和LingoLingo是专业是专业优化软件优化软件.LINDO LINDO 企业软件产品是企业软件产品是美国芝加哥美国芝加哥(Chicago)(Chicago)大大学学Linus SchrageLinus Schrage教授于教授于19801980年前后开发年前后开发,以后成立以后成立 LINDOLINDO系统企业（系统企业（LINDO Systems Inc.LINDO Systems Inc.）。）。网址网址：http:/ 第26页LP问题问题Lindo输入范例输入范例MAX3x1+2x2ST2)X143)X234)2x1+3x212END注：注：Lindo中已要求全部决议变量均非负，故非负约束不用中已要求全部决议变量均非负，故非负约束不用输入；乘号省略，式中不能有括号，右边不能有数学符号；输入；乘号省略，式中不能有括号，右边不能有数学符号；=与与等效；等效；2），），3），），4）是为了便于从结果中）是为了便于从结果中查找信息和进行灵敏性分析；程序以查找信息和进行灵敏性分析；程序以end结束。结束。第27页ILP问题问题Lindo输入范例之一输入范例之一MAX3x1+2x2ST2)X143)X234)2x1+3x212ENDGIN2(!表示前两个变量为普通整数表示前两个变量为普通整数)第28页ILP问题问题Lindo输入范例之二输入范例之二MAX3x1+2x2ST2)X143)X234)2x1+3x212ENDINT2(!表示前两个变量为表示前两个变量为0-1整数整数)第29页ILP问题问题Lingo输入范例一输入范例一MAX=3*x1+2*x2;STX14;X23;2*x1+3*x212;GIN(X1);GIN(X2);第30页ILP问题问题Lingo输入范例之二输入范例之二max3x1+2x2s.t.X14X232x1+3x2”（或（或“=”（或（或“=”）功效相同）功效相同2.变量与系数间可有空格变量与系数间可有空格(甚至回车甚至回车),但无运算符但无运算符3.变量名以字母开头，不能超出变量名以字母开头，不能超出8个字符个字符4.变量名不区分大小写（包含变量名不区分大小写（包含LINDO中关键字）中关键字）5.目标函数所在行是第一行，第二行起为约束条件目标函数所在行是第一行，第二行起为约束条件6.行号行号(行名行名)自动产生或人为定义。行名以自动产生或人为定义。行名以“）”结束结束7.行中注有行中注有“!”符号后面部分为注释。如符号后面部分为注释。如:!ItsComment.8.在模型任何地方都能够用在模型任何地方都能够用“TITLE”对模型命名（最多对模型命名（最多72个字符），如：个字符），如：TITLEThisModelisonlyanExample第32页9.变量不能出现在一个约束条件右端变量不能出现在一个约束条件右端10.表示式中不接收括号表示式中不接收括号“()”和逗号和逗号“,”等任何符号等任何符号,例例:400(X1+X2)需需写为写为400X1+400X211.表示式应化简，如表示式应化简，如2X1+3X2-4X1应写成应写成-2X1+3X212.缺省假定全部变量非负；可在模型缺省假定全部变量非负；可在模型“END”语句后用语句后用“FREEname”将变将变量量name非负假定取消非负假定取消13.可在可在“END”后用后用“SUB”或或“SLB”设定变量上下界设定变量上下界比如：比如：“subx110”作用等价于作用等价于“x1uiv交易费交易费=vpiuixiuiv而题目所给定定值而题目所给定定值ui(单位单位:元元)相对总投资相对总投资M很小很小,piui更小更小,能够忽略不计能够忽略不计,这么购置这么购置Si净收益为净收益为(ri-pi)xi第48页净收益尽可能大净收益尽可能大建立模型建立模型总体风险尽可能小总体风险尽可能小多目标规划问题多目标规划问题第49页采取主要目标法化为单目标规划采取主要目标法化为单目标规划方法一方法一.固定风险水平，优化收益固定风险水平，优化收益 在实际投资中，投资者承受风险程度不一样，若在实际投资中，投资者承受风险程度不一样，若给定风险一个界限给定风险一个界限a，使最大一个风险，使最大一个风险qixi/Ma，可找到对应投资方案。可找到对应投资方案。模型一模型一线性规划模型线性规划模型第50页若投资者希望总盈利最少到达水平若投资者希望总盈利最少到达水平k以上，在风险以上，在风险最小情况下寻找对应投资组合。最小情况下寻找对应投资组合。模型二模型二线性规划模型线性规划模型方法二：方法二：固定盈利水平，极小化风险固定盈利水平，极小化风险第51页采取线性加权法化为单目标规划采取线性加权法化为单目标规划 投资者在权衡资产风险和预期收益两方面时，希望选投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意投资组合。所以对风险、收益赋予择一个令自己满意投资组合。所以对风险、收益赋予权重权重s（0s1)，s称为投资偏好系数称为投资偏好系数.模型三模型三线性规划模型线性规划模型第52页模型一求解模型一求解将详细数据代入将详细数据代入,模型一以下模型一以下:因为因为a是任意给定风险度，到底怎样给定没有一个是任意给定风险度，到底怎样给定没有一个准则，不一样投资者有不一样风险度。我们从准则，不一样投资者有不一样风险度。我们从a=0开始，开始，以步长以步长a=0.001进行循环搜索，编制程序以下：进行循环搜索，编制程序以下：第53页a=0;while(1.1-a)1 c=-0.05-0.27-0.19-0.185-0.185;Aeq=1 1.01 1.02 1.045 1.065;beq=1;A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0 0 0 0.026;b=a;a;a;a;vlb=0,0,0,0,0;vub=;x,val=linprog(c,A,b,Aeq,beq,vlb,vub);a x=x Q=-val plot(a,Q,.)，axis(0 0.1 0 0.5)，hold on a=a+0.001;end xlabel(a),ylabel(Q)第54页计算结果：计算结果：v风险大，收益也大。风险大，收益也大。v曲线上任一点表示该风曲线上任一点表示该风险水平最大可能收益。险水平最大可能收益。v对于不一样风险承受能对于不一样风险承受能力，选择该风险水平下力，选择该风险水平下最优投资组合。最优投资组合。第55页 在在a=0.006a=0.006附近有一个转折点，在这一点左边，附近有一个转折点，在这一点左边，风险增加极少时，利润增加很快。在这一点右边，风险增加极少时，利润增加很快。在这一点右边，风险增加很大时，利润增加很迟缓，所以对于风险风险增加很大时，利润增加很迟缓，所以对于风险和收益没有特殊偏好投资者来说，应该选择曲线拐和收益没有特殊偏好投资者来说，应该选择曲线拐点作为最优投资组合，大约是：点作为最优投资组合，大约是：a a*=0.6%=0.6%，Q Q*=20%=20%。此时所对应投资方案为此时所对应投资方案为:风险度风险度=0.0060；收益；收益=0.；x0=0，x1=0.2400，x2=0.4000，x3=0.1091，x4=0.2212第56页约束非线性规划约束非线性规划普通形式：普通形式：其其中中，f(x)为为多多元元实实值值函函数数;g(x)，ceq(x)为为向向量量函函数数,而而且且f(x),g(x),ceq(x)中中最最少少有有一一个个函函数数是是非非线线性性函函数数（不然成为线性规划问题）。（不然成为线性规划问题）。第57页x=fmincon(fun,x0,A,b)x=fmincon(fun,x0,A,b)x=fmincon(fun,x0,A,b,Aeq,beq)x=fmincon(fun,x0,A,b,Aeq,beq)x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub)x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub)x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcox=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)n)x=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,x=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)OPTIONS)在在Matlab优化工具箱中，优化工具箱中，fmincon函数是用函数是用SQP算算法来处理普通约束非线性规划函数，它命令格式为：法来处理普通约束非线性规划函数，它命令格式为：上式中上式中x为最优点；若将左端为最优点；若将左端x换为换为x,f,则返回最则返回最优点优点x和最优值和最优值f。第58页【例例1】求解约束非线性规划：求解约束非线性规划：(初值为初值为1;1)解解:首先建立一个首先建立一个m文件文件fun1.mfunction y=fun1(x)y=-exp(x(1)*x(2)2*(3-exp(x(1)-x(2)2);存放为存放为fun1.m首先将问题转化为首先将问题转化为matlab要求格式要求格式;即求出即求出fun,A,b,Aeq,Beq,X0,Lb,Ub第59页function g,cep=fun2(x)g=;%g为非线性不等式为非线性不等式,且为且为g=0ceq=exp(x(1)+x(2)2-3;%ceq为非线性等式为非线性等式然后存放为然后存放为fun2.m建立主程序：建立主程序：A=;b=;Aeq=;Beq=;Lb=;Ub=;x,f=fmincon(fun1,1;1,fun2)-f建立非线性约束建立非线性约束m-文件文件fun2.m运行结果为运行结果为:x=0.8852 0.7592f=6.2043e-016最优点最优点最优值最优值第60页【例例2】求解约束非线性规划：求解约束非线性规划：解：首先建立一个解：首先建立一个m文件文件 fun5.mfunction y=fun5(x)y=(x(1)-1)2+(x(2)-2)2+(x(3)-3)2+(x(4)-4)2;存放为存放为fun5.m文件文件.第61页x0=1;1;1;1;A=1 1 1 1;3 3 2 1;B=5;10;Aeq=;Beq=;Lb=0;0;0;0;x,g=fmincon(fun5,x0,A,B,Aeq,Beq,Lb)运行结果为运行结果为:x=0.0000 0.6667 1.6665 2.6668g=6.3333建立主程序建立主程序第62页小结：小结：用用Matlab求解非线性规划问题，基本步骤：求解非线性规划问题，基本步骤：1.首先建立首先建立M文件文件fun.m,定义目标函数定义目标函数f（x）:function f=fun(x);f=f（x）;2.若若约约束条件中有非束条件中有非线线性性约约束束:g(x)或或Ceq(x)=0,则则建立建立M文件文件nonlcon.m定定义义函函数数g(x)与与Ceq(x):function g,Ceq=nonlcon(X)g=.Ceq=.3.建立主程序建立主程序.并运行。并运行。第63页s.t.比如：比如：在对策论中：在最不利条件下，寻求最有利在对策论中：在最不利条件下，寻求最有利策略；策略；在投资规划中要确定最大风险最低程度；在投资规划中要确定最大风险最低程度；在城市规划中，要确定抢救中心位置，使其到全在城市规划中，要确定抢救中心位置，使其到全部地点最大距离为最小。部地点最大距离为最小。最大最小化问题最大最小化问题第64页求解最大最小化问题求解最大最小化问题Matlab函数为函数为fminimax.其调用其调用格式以下：格式以下：x=fminimax(F,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)或或x,fval,maxfval,exitflag,output=fminimax()其中：其中：x返回最优解；返回最优解；fval返回解返回解x处目标函数值；处目标函数值；maxfval返回解返回解x处最大函数值；处最大函数值；exitflag描述计算描述计算退出条件；退出条件；output返回包含优化信息输出参数。返回包含优化信息输出参数。第65页例：例：求解以下最大最小化问题：求解以下最大最小化问题：首先编写一个首先编写一个M文件文件ff2.m，计算，计算4个函数值。个函数值。function f=ff2(x)f(1)=3*x(1)2+2*x(2)2-12*x(1)+35;f(2)=5*x(1)*x(2)-4*x(2)+7;f(3)=x(1)2+6*x(2);f(4)=4*x(1)2+9*x(2)2-12*x(1)*x(2)+20;第66页然后，输入初值然后，输入初值x0=(1,1)，并调用优化函数进行计算，并调用优化函数进行计算x0=0 0;x,fval=fminimax(ff2,x0)运行结果以下：运行结果以下：x=1.7637 0.5317fval=23.7331 9.5622 6.3010 23.7331第67页练习题：练习题：设某城市有某种物品设某城市有某种物品10个需求点，第个需求点，第i个需个需求点求点Pi坐标为坐标为(ai,bi),道路网与坐标轴平行，彼此正交。道路网与坐标轴平行，彼此正交。现打算建一个该物品供给中心，且因为受到城市一现打算建一个该物品供给中心，且因为受到城市一些条件限制，该供给中心只能设在些条件限制，该供给中心只能设在x界于界于5,8，y界界于于5,8范围之内。问该中心应建在何处为好范围之内。问该中心应建在何处为好?（即（即供供给中心位置到最远需求点距离最小给中心位置到最远需求点距离最小）Pi点坐标为：点坐标为：ai1435912620178bi2108181451089第68页无约束最优化问题无约束最优化问题v求一元函数求一元函数fun在区间在区间(x1,x2)上最小值上最小值vX=fminbnd(fun,x1,x2)v或或x,fval=fminbnd(fun,x1,x2)v求多元无约束函数求多元无约束函数fun最小值最小值vx,fval=fminunc(fun,x0)x0为初值为初值vx,fval=fminsearch(fun,x0)注意：注意：fminunc不是处理平方相加函数优化问不是处理平方相加函数优化问题最好方法题最好方法第69页函数函数lsqnonlin专门处理非线性最小二乘问题：专门处理非线性最小二乘问题：调调用格式：用格式：x=lsqnonlin(fun,x0)x=lsqnonlin(fun,x0,lb,ub)x=lsqnonlin(fun,x0,lb,ub,options)第70页线性最小二乘问题线性最小二乘问题lsqlin函数函数：用于：用于处处理理线线性最小二乘性最小二乘问题问题：调调用格式：用格式：x=lsqlin(C,d,A,b)x=lsqlin(C,d,A,b,Aeq,beq)x=lsqlin(C,d,A,b,Aeq,beq,lb,ub)x=lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0)x=lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0,options)第71页例例.求解下面非线性最小二乘问题求解下面非线性最小二乘问题初始解向量为初始解向量为解：解：(1)建立函数文件建立函数文件example5.mfunction F=example5(x)k=1:10;F=2+2*k-exp(k*x(1)-exp(k*x(2);x0=0.30.4;x,resnorm,residual=lsqnonlin(example5,x0)(2)调用优化程序：调用优化程序：第72页(3)运行结果为运行结果为x=0.25780.2578resnorm=124.3622residual=Columns1through71.41182.65053.66544.39064.74084.60573.8428Columns8through102.2672-0.3600-4.3482residual为为解解x处处向量向量f(x)值值最优解最优解最优值最优值第73页无约束优化问题无约束优化问题1、一元函数极小问题、一元函数极小问题MinF（x）s.t.x1xx2x,fval=fminbnd(F,x1,x2)算法基于黄金分割法和二次插值法，它要算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给求目标函数必须是连续函数，并可能只给出局部最优解。出局部最优解。第74页2、无约束多元极小化问题、无约束多元极小化问题MinF(X)x,fval,exitflag,output=fminunc(F,X0,options)x,fval,exitflag,output=minsearch(F,X0,options)fminunc为无约束优化提供了大型优化和中型优化为无约束优化提供了大型优化和中型优化算法。算法。由由options中参数中参数LargeScale控制：控制：LargeScale=on,使用大型算法使用大型算法LargeScale=off,使用中型算法使用中型算法第75页fminunc为中型优化算法搜索方向提供了为中型优化算法搜索方向提供了4种算种算法，法，由由options中参数中参数HessUpdate控制：控制：HessUpdate=bfgs（默认值），拟牛顿法（默认值），拟牛顿法BFGS公式；公式；HessUpdate=dfp，拟牛顿法，拟牛顿法DFP公式；公式；HessUpdate=steepdesc，最速下降法，最速下降法fminunc为中型优化算法步长一维搜索提供了两种为中型优化算法步长一维搜索提供了两种算法算法，由，由options中参数中参数LineSearchType控制：控制：LineSearchType=quadcubic(缺省值缺省值)，混合二，混合二次和三次多项式插值；次和三次多项式插值；LineSearchType=cubicpoly，三次多项式插值，三次多项式插值第76页三、控制参数三、控制参数options设置设置(3)MaxIter:允许进行迭代最大次数允许进行迭代最大次数,取值为正取值为正整数整数Options中惯用几个参数名称、含义、取值中惯用几个参数名称、含义、取值以下以下:（1）Display:显示水平显示水平.取值为取值为off时时,不显示输出不显示输出;取值为取值为iter时时,显示每次迭代信息显示每次迭代信息;取值为取值为final时时,显示最终止果显示最终止果.默认值为默认值为final.（2）MaxFunEvals:允许进行函数评价最大允许进行函数评价最大次数次数,取值为正整数取值为正整数.第77页(3)options=optimset(oldops,param1,value1,param2,value2,.)创建名称为创建名称为oldops参数拷贝参数拷贝,用指定参数值修改用指定参数值修改oldops中对应参数中对应参数.控制参数控制参数options能够经过函数能够经过函数optimset创建或创建或修改。命令格式以下：修改。命令格式以下：(1)options=optimset(optimfun)创建一个含有全部参数名创建一个含有全部参数名,并与优化函数并与优化函数optimfun相关相关默认值选项结构默认值选项结构options.（2）options=optimset(param1,value1,param2,value2,.)创建一个名称为创建一个名称为options优化选项参数优化选项参数,其中指定参其中指定参数含有指定值数含有指定值,全部未指定参数取默认值全部未指定参数取默认值.第78页数模竞赛培训优化问题建模举例优化问题建模举例第79页v例例1某校篮球队准备从以下队员中选拔某校篮球队准备从以下队员中选拔3 3名为正式名为正式队员，并使平均身高尽可能高，这队员，并使平均身高尽可能高，这6 6名预备队员情名预备队员情况以下表所表示况以下表所表示。预备队员预备队员号码号码身高身高位置位置大张大张1193中锋中锋大李大李2191中锋中锋小王小王3187前卫前卫小赵小赵4186前卫前卫小田小田5180后卫后卫小周小周6185后卫后卫v队员挑选要满足以下条件：队员挑选要满足以下条件：(1)最少补充一名后卫队员；最少补充一名后卫队员；(2)大李或小田中间只能入选一名；大李或小田中间只能入选一名；(3)最多补充一名中锋；最多补充一名中锋；(4)假如大李或小赵入选，小周就不能入选假如大李或小赵入选，小周就不能入选.v试建立此问题数学模型。试建立此问题数学模型。第80页解解:则该问题数学模型为则该问题数学模型为:(0-1)规划规划第81页例例2 2 经典指派问题经典指派问题n n个员工分配做个员工分配做n n项工作，已知第项工作，已知第i i个员工做第个员工做第j j项工作成项工作成本为本为c cijij，i=1,n;j=1,ni=1,n;j=1,n。求最正确分配方案。求最正确分配方案。s.t.解解第82页例例3 3 工厂工厂-销售点配置问题销售点配置问题生产厂生产厂客户需求客户需求销售点销售点45DCBA7IIIII213I第83页工厂工厂-销售点配置问题销售点配置问题-问题描述问题描述问题问题:为使经营成本最低为使经营成本最低,应开设那些工厂及销售点应开设那些工厂及销售点?第84页工厂工厂-销售点配置问题销售点配置问题-模型参数第85页工厂工厂-销售点配置问题销售点配置问题-模型第86页第87页