数学建模最优化模型课件ppt市公开课金奖市赛课一等奖课件.pptx

最优化模型最优化模型一、最优化办法概述一、最优化办法概述二、无约束最优化问题二、无约束最优化问题三、无约束最优化问题三、无约束最优化问题MATLABMATLAB求解求解四、有约束最优化问题四、有约束最优化问题第1页第1页最优化办法概述最优化办法概述 1 1、最最优优化化理理论论和和办办法法是是近近二二十十多多年年来来发发展展十十分分快快速一个数学分支。速一个数学分支。2 2、在数学上，最优化是一个求极值办法。、在数学上，最优化是一个求极值办法。3 3、最优化已经广泛渗入到工程、经济、电子技术、最优化已经广泛渗入到工程、经济、电子技术等领域。等领域。第2页第2页在实际生活当中，人们做任何事情，不论是分析问题，还是进行决议，都要用一个标准衡量一下是否达到了最优。（比如基金人投资）在各种科学问题、工程问题、生产管理、社会经济问题中，人们总是希望在有限资源条件下，用尽也许小代价，取得最大收获。（比如保险）第3页第3页 数学家对最优化问题研究已有诸多年历史。数学家对最优化问题研究已有诸多年历史。以前处理最优化问题数学办法只限于古典求以前处理最优化问题数学办法只限于古典求导办法和变分法（求导办法和变分法（求无约束极值无约束极值问题），拉格朗问题），拉格朗日（日（LagrangeLagrange）乘数法处理等式约束下条件极值）乘数法处理等式约束下条件极值问题。问题。计算机技术出现，使得数学家研究出了许多计算机技术出现，使得数学家研究出了许多最优化办法和算法用以处理以前难以处理问题。最优化办法和算法用以处理以前难以处理问题。第4页第4页几种概念几种概念最优化最优化是从所有也许方案中选择最合理一个以达是从所有也许方案中选择最合理一个以达到最优目的学科。到最优目的学科。最优方案最优方案是达到最优目的方案。是达到最优目的方案。最优化办法最优化办法是搜寻最优方案办法。是搜寻最优方案办法。最优化理论最优化理论就是最优化办法理论。就是最优化办法理论。第5页第5页典型极值问题典型极值问题包括：包括：无约束极值问题无约束极值问题约束条件下极值问题约束条件下极值问题第6页第6页1 1、无约束极值问题数学模型、无约束极值问题数学模型 2 2、约束条件下极值问题数学模型、约束条件下极值问题数学模型 其中，极大值问题能够转化为极小值问题来其中，极大值问题能够转化为极小值问题来进行求解。如求：进行求解。如求：能够转化为：能够转化为：第7页第7页1 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 第8页第8页第9页第9页用用MATLAB解无约束优化问题解无约束优化问题 其中档式（其中档式（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（）第10页第10页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)第11页第11页例例2 有边长为有边长为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)第12页第12页 命令格式为命令格式为:（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第13页第13页例例 用用fminsearch函数求解函数求解输入命令输入命令:f=100*(x(2)-x(1)2)2+(1-x(1)2;x,fval,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 第14页第14页有约束最优化有约束最优化最优化办法分类最优化办法分类（一一）线线性性最最优优化化：目目的的函函数数和和约约束束条条件件都都是是线线性则称为线性最优化。性则称为线性最优化。非非线线性性最最优优化化：目目的的函函数数和和约约束束条条件件假假如如含含有非线性，则称为非线性最优化。有非线性，则称为非线性最优化。（二二）静静态态最最优优化化：假假如如也也许许方方案案与与时时间间无无关关，则是静态最优化问题。则是静态最优化问题。动态最优化动态最优化：假如也许方案与时间相关，则假如也许方案与时间相关，则是动态最优化问题是动态最优化问题第15页第15页有约束最优化问题数学建模有约束最优化问题数学建模 有约束最优化模型普通含有下列形式：有约束最优化模型普通含有下列形式：或或 其中其中f(x)为目的函数，省略号表示约束式子，能够是为目的函数，省略号表示约束式子，能够是等式约束，也能够是不等式约束。等式约束，也能够是不等式约束。第16页第16页 依依据据目目的的函函数数，约约束束条条件件特特点点将将最最优优化化办法包括主要内容大体下列划分：办法包括主要内容大体下列划分：线性规划线性规划整数规划整数规划非线性规划非线性规划动态规划动态规划多目的规划多目的规划 对策论对策论最优化办法主要内容最优化办法主要内容第17页第17页两个引例两个引例问题一问题一：某工厂在计划期内要安排生产：某工厂在计划期内要安排生产I、II两种产品，两种产品，已知生产单位产品所需设备台时及已知生产单位产品所需设备台时及A、B两种原材料消耗，两种原材料消耗，下列表所表示下列表所表示 12kg40原材料原材料B16kg04原材料原材料A8台时台时21设备设备III该工厂每生产一件产品该工厂每生产一件产品I可赢利可赢利2元，每生产一件产品元，每生产一件产品II可赢利可赢利3元。问应如何安排计划使该工厂赢利最多？元。问应如何安排计划使该工厂赢利最多？第18页第18页解解：该工厂生产产品：该工厂生产产品I x1件，生产产品件，生产产品II x2件，件，我们可建立下列数学模型：我们可建立下列数学模型：s.t.第19页第19页问题二：某厂每日8小时产量不低于1800件.为了进行质量控制，计划聘请两种不同水平检验员.一级检验员标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员标准为：速度15件/小时，正确率95%，计时工资3元/小时.检验员每错检一次，工厂要损失2元.为使总检验费用最省，该工厂应聘一级、二级检验员各几名？解解 设需要一级和二级检查员人数分别为设需要一级和二级检查员人数分别为x1、x2人人,则应付检查员工资为：则应付检查员工资为：因检查员错检而造成损失为：因检查员错检而造成损失为：第20页第20页故目的函数为：故目的函数为：约束条件为：约束条件为：第21页第21页 利用最优化办法处理最优化问题普通办利用最优化办法处理最优化问题普通办法环节下列：法环节下列：前期分析：分析问题，找出要处理目的，约束条件，前期分析：分析问题，找出要处理目的，约束条件，并确立最优化目的。并确立最优化目的。定义变量，建立最优化问题数学模型，列出目的函数定义变量，建立最优化问题数学模型，列出目的函数和约束条件。和约束条件。针对建立模型，选择适当求解办法或数学软件。针对建立模型，选择适当求解办法或数学软件。编写程序，利用计算机求解。编写程序，利用计算机求解。对结果进行分析，讨论诸如：结果合理性、正确性，对结果进行分析，讨论诸如：结果合理性、正确性，算法收敛性，模型合用性和通用性，算法效率与误差算法收敛性，模型合用性和通用性，算法效率与误差等。等。第22页第22页线线 性性 规规 划划某豆腐店用黄豆制作两种不同口感豆腐发售。制作口感较鲜嫩豆腐每千克需要0.3千克一级黄豆及0.5千克二级黄豆，售价10元；制作口感较厚实豆腐每千克需要0.4千克一级黄豆及0.2千克二级黄豆，售价5元。现小店购入9千克一级黄豆和8千克二级黄豆。问：应怎样安排制作计划才干取得最大收益。第23页第23页一、问题前期分析该问题是在不超出制作两种不同口感豆腐所需黄豆总量条件下合理安排制作计划，使得售出各种豆腐能取得最大收益。二、模型假设1假设制作豆腐能全部售出。2假设豆腐售价无波动。第24页第24页变量假设：变量假设：设计划制作口感鲜嫩和厚实豆腐各设计划制作口感鲜嫩和厚实豆腐各x1公斤和公斤和 x2公斤，可取得收益公斤，可取得收益R元。元。目的函数：取得总收益最大。目的函数：取得总收益最大。总收益可表示为：总收益可表示为：受一级黄豆数量限制：受一级黄豆数量限制：受二级黄豆数量限制：受二级黄豆数量限制：第25页第25页综上分析，得到该问题线性规划模型综上分析，得到该问题线性规划模型 s.t.第26页第26页用用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.0000 15.0000FVAL=-175.0000第27页第27页用用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第28页第28页线线 性性 规规 划划 设某工厂有甲、乙、丙、丁四个车间，生产设某工厂有甲、乙、丙、丁四个车间，生产A、B、C、D、E、F六种产品。依据机床性能和六种产品。依据机床性能和以前生产情况，得知每单位产品所需车间工作小以前生产情况，得知每单位产品所需车间工作小时数、每个车间在一个季度工作小时上限以及单时数、每个车间在一个季度工作小时上限以及单位产品利润，下列表所表示位产品利润，下列表所表示(比如，生产一个单位比如，生产一个单位A产品，需要甲、乙、丙三个车间分别工作产品，需要甲、乙、丙三个车间分别工作1小时、小时、2小时小时和和4小时小时)问：每种产品各应当每季度生产多少，才干使这问：每种产品各应当每季度生产多少，才干使这个工厂每季度生产利润达到最大。个工厂每季度生产利润达到最大。第29页第29页生产单位产品所需车间工作小时数 ABCDEF每个车间一个季度工作小时上限甲甲111323500乙乙255500丙丙425500丁丁138500利润利润(百元百元)4.02.45.55.04.58.5第30页第30页这是一个典型最优化问题，属线性规划。这是一个典型最优化问题，属线性规划。假设：产品合格且能及时销售出去；工作无等待情况等假设：产品合格且能及时销售出去；工作无等待情况等 变量阐明：变量阐明：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种产品所花时间总数；种产品所花时间总数；第31页第31页于是，我们可建立下列数学模型：于是，我们可建立下列数学模型：s.t.计算结果：计算结果：Z(百元百元)x1x2x3x4x5x6132000604010040第32页第32页运运 输输 问问 题题 要从甲城调出蔬菜吨，从乙城调出蔬菜要从甲城调出蔬菜吨，从乙城调出蔬菜2500吨，从吨，从丙地调出丙地调出3000吨，分别供应吨，分别供应A地吨，地吨，B地地2300吨、吨、C地地1800吨、吨、D地地1400吨，已知每吨运费下列表：吨，已知每吨运费下列表：供应单位调出单位ABCD甲甲21271340乙乙45513720丙丙32352030问：如何调拨才干使运费最省？问：如何调拨才干使运费最省？第33页第33页假设：假设：假设题目中所给运费已考虑各地间公里数；假设题目中所给运费已考虑各地间公里数；只考虑运量和运费，不考虑车辆调拨等其它相关原因只考虑运量和运费，不考虑车辆调拨等其它相关原因不考虑车辆返空费用（或：所给运费已包括车辆返空不考虑车辆返空费用（或：所给运费已包括车辆返空费用）费用）变量阐明：变量阐明：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地所需蔬菜总量地所需蔬菜总量 第34页第34页能够建立下列模型：能够建立下列模型：s.t.第35页第35页整整 数数 规规 划划 最优化问题中所有变量均为整数时，这类问最优化问题中所有变量均为整数时，这类问题称为整数规划问题。题称为整数规划问题。假如线性规划中所有变量均为整数时，称这假如线性规划中所有变量均为整数时，称这类问题为线性整数规划问题。类问题为线性整数规划问题。整数规划可分为线性整数规划和非线性整数整数规划可分为线性整数规划和非线性整数规划规划 ，以及混合整数规划等。，以及混合整数规划等。假如决议变量取值要么为假如决议变量取值要么为0 0，要么为，要么为1 1，则这，则这样规划问题称为样规划问题称为0 01 1规划。规划。第36页第36页例例1 某钢厂两个炼钢炉同时各用一个办法炼钢。某钢厂两个炼钢炉同时各用一个办法炼钢。第一个炼法每炉用第一个炼法每炉用a小时，第二种用小时，第二种用b小时（包括小时（包括清炉时间）。假定这两种炼法，每炉出钢都是清炉时间）。假定这两种炼法，每炉出钢都是k公斤，而炼公斤，而炼1公斤钢平均燃料费第一法为公斤钢平均燃料费第一法为m元，元，第二法为第二法为n元。若要求在元。若要求在c小时内炼钢公斤数不少小时内炼钢公斤数不少于于d，试列出燃料费最省两种办法分派方案数学，试列出燃料费最省两种办法分派方案数学模型。模型。第37页第37页设用第一个炼法炼钢设用第一个炼法炼钢x1炉，第二种炼钢炉，第二种炼钢x2炉炉 s.t.第38页第38页引例引例2.资源分派问题：资源分派问题：某个中型百货商场要求售货人员每七天工作某个中型百货商场要求售货人员每七天工作5天，连续休息天，连续休息2天，工资天，工资200元元/周，已知对售货人周，已知对售货人员需求通过统计分析下列表，问如何安排可使配员需求通过统计分析下列表，问如何安排可使配备销售人员总费用至少？备销售人员总费用至少？星期星期一一二二三三四四五五六六日日所需售货员人数所需售货员人数18151216191412开始休息人数开始休息人数 x1 x2 x3 x4 x5 x6 x7 设决议变量如上，可建立下列模型：设决议变量如上，可建立下列模型：第39页第39页第40页第40页非线性规划非线性规划非线性规划问题普通数学模型：非线性规划问题普通数学模型：其中，其中，为目的函数，为目的函数，为约束函数，这些函数中至少有为约束函数，这些函数中至少有一个是非线性函数。一个是非线性函数。第41页第41页应用实例：应用实例：供应与选址供应与选址 某公司有某公司有6个建筑工地要动工，每个工地位置（用平面坐标系个建筑工地要动工，每个工地位置（用平面坐标系a，b表示，距离单位：表示，距离单位：km）及水泥日用量）及水泥日用量d(t)由下表给出当前有由下表给出当前有两个暂时料场位于两个暂时料场位于A(5,1)，B(2,7)，日储量各有，日储量各有20t假设从料场到假设从料场到工地之间都有直线道路相连工地之间都有直线道路相连 （1）试制定天天供应计划，即从）试制定天天供应计划，即从A，B两料场分别向各工地运送两料场分别向各工地运送多少水泥，可使总吨千米数最小多少水泥，可使总吨千米数最小（2）为了进一步减少吨千米数，打算舍弃两个暂时料场，改建两）为了进一步减少吨千米数，打算舍弃两个暂时料场，改建两个新，日储量各为个新，日储量各为20t，问应建在何处，节约吨千米数有多大？，问应建在何处，节约吨千米数有多大？第42页第42页（一）建立模型（一）建立模型 记工地位置为记工地位置为(ai，bi)，水泥日用量为，水泥日用量为di，i=1,6;料场位置为料场位置为(xj，yj)，日储量为，日储量为ej，j=1,2；料场；料场j向工地向工地i运送量为运送量为Xij当用暂时料场时决议变量为：当用暂时料场时决议变量为：Xij，当不用暂时料场时决议变量为：当不用暂时料场时决议变量为：Xij，xj，yj第43页第43页多目的规划多目的规划引例引例1.投资问题投资问题 某公司在一段时间内有某公司在一段时间内有a(亿元亿元)资金可用于建厂投资。资金可用于建厂投资。若可供选择项目记为若可供选择项目记为1,2,m。并且一旦对第。并且一旦对第i个项目投资个项目投资就用去就用去ai亿元；而这段时间内可得收益亿元；而这段时间内可得收益ci亿元。问如何拟定亿元。问如何拟定最佳投资方案？最佳投资方案？最佳投资方案：投资至少，收益最大！最佳投资方案：投资至少，收益最大！第44页第44页投资至少：投资至少：约束条件为：约束条件为：收益最大：收益最大：第45页第45页引例2：生产问题 某工厂生产两种产品，产品A每单位利润为10元，而产品B每单位利润为8元；产品A每单位需3小时装配时间而B为2小时，每七天总装配有效时间为120小时。工厂允许加班，但加班生产出来产品利润要减去1元。依据最近协议，厂商每七天最少向用户提供两种产品各30单位。要求：必须恪守协议；尽也许少加班；利润最大。问应怎样安排生产？x1：每七天正常时间生产得：每七天正常时间生产得A产品数量；产品数量；x2：每七天加班时间生产得：每七天加班时间生产得A产品数量；产品数量；x3：每七天正常时间生产得：每七天正常时间生产得B产品数量；产品数量；x4：每七天加班时间生产得：每七天加班时间生产得B产品数量；产品数量；第46页第46页目的函数（有两个）：目的函数（有两个）：第47页第47页