数学建模最优化模型课件

最优化模型最优化模型一、最优化方法概述一、最优化方法概述二、无约束最优化问题二、无约束最优化问题三、无约束最优化问题的三、无约束最优化问题的MATLABMATLAB 求解求解四、有约束最优化问题四、有约束最优化问题最优化方法概述最优化方法概述 1 1、最最优优化化理理论论和和方方法法是是近近二二十十多多年年来来发发展展十十分分迅迅速的一个数学分支。速的一个数学分支。2 2、在数学上，最优化是一种求极值的方法。、在数学上，最优化是一种求极值的方法。3 3、最优化已经广泛的渗透到工程、经济、电子技、最优化已经广泛的渗透到工程、经济、电子技术等领域。术等领域。在实际生活当中，人们做任何事情，不管是分在实际生活当中，人们做任何事情，不管是分析问题，还是进行决策，都要用一种标准衡量析问题，还是进行决策，都要用一种标准衡量一下是否达到了最优。一下是否达到了最优。（比如基金人投资）（比如基金人投资）在各种科学问题、工程问题、生产管理、社会在各种科学问题、工程问题、生产管理、社会经济问题中，人们总是希望在有限的资源条件经济问题中，人们总是希望在有限的资源条件下，用尽可能小的代价，获得最大的收获。下，用尽可能小的代价，获得最大的收获。（比如保险）（比如保险）数学家对最优化问题的研究已经有很多年的数学家对最优化问题的研究已经有很多年的历史。历史。以前解决最优化问题的数学方法只限于古典以前解决最优化问题的数学方法只限于古典求导方法和变分法（求求导方法和变分法（求无约束极值无约束极值问题），拉格问题），拉格朗日（朗日（LagrangeLagrange）乘数法解决等式约束下的条件）乘数法解决等式约束下的条件极值问题。极值问题。计算机技术的出现，使得数学家研究出了许计算机技术的出现，使得数学家研究出了许多最优化方法和算法用以解决以前难以解决的问多最优化方法和算法用以解决以前难以解决的问题。题。最优化：最优化：在一定的条件下，寻求在一定的条件下，寻求使得目标最大（最小）的策略使得目标最大（最小）的策略约一半以上的问题与最优化问题有关。如：飞行管理问题（飞行管理问题（95A）最优捕鱼策略（最优捕鱼策略（96A）节水洗衣机（节水洗衣机（96B）零件的参数设计零件的参数设计(97A)投资收益和风险投资收益和风险(98A)钢管订购和运输钢管订购和运输(2000B)电力市场的堵塞管理电力市场的堵塞管理(2004B)几个概念几个概念最优化最优化是从所有可能方案中选择最合理的一种以是从所有可能方案中选择最合理的一种以达到最优目标的学科。达到最优目标的学科。最优方案最优方案是达到最优目标的方案。是达到最优目标的方案。最优化方法最优化方法是搜寻最优方案的方法。是搜寻最优方案的方法。最优化理论最优化理论就是最优化方法的理论。就是最优化方法的理论。经典极值问题经典极值问题包括：包括：无约束极值问题无约束极值问题约束条件下的极值问题约束条件下的极值问题1 1、无约束极值问题的数学模型、无约束极值问题的数学模型 2 2、约束条件下极值问题的数学模型、约束条件下极值问题的数学模型 其中，极大值问题可以转化为极小值问题来其中，极大值问题可以转化为极小值问题来进行求解。如求：进行求解。如求：可以转化为：可以转化为：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 用用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（）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 有边长为有边长为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（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,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 建立数学模型时要尽可能建立数学模型时要尽可能简单简单，而且要能完整地描述所，而且要能完整地描述所研究的系统，具体建立怎样的数学模型需要丰富的经验和熟练研究的系统，具体建立怎样的数学模型需要丰富的经验和熟练的技巧。即使在建立了问题的数学模型之后，通常也必须对模的技巧。即使在建立了问题的数学模型之后，通常也必须对模型进行必要的型进行必要的数学简化数学简化以便于分析、计算。以便于分析、计算。一般的模型简化工作包括以下几类：一般的模型简化工作包括以下几类：（1）将离散变量转化为连续变量。）将离散变量转化为连续变量。（2）将非线性函数线性化。）将非线性函数线性化。（3）删除一些非主要约束条件。）删除一些非主要约束条件。最优化问题的数学模型最优化问题的数学模型建立最优化问题数学模型的三要素：建立最优化问题数学模型的三要素：（1）决策变量和参数。决策变量和参数。决策变量是由数学模型的解确定的未知数。参数表示决策变量是由数学模型的解确定的未知数。参数表示系统的控制变量，有确定性的也有随机性的。系统的控制变量，有确定性的也有随机性的。（2）约束或限制条件。约束或限制条件。由于现实系统的客观物质条件限制，模型必须包括由于现实系统的客观物质条件限制，模型必须包括把决策变量限制在它们可行值之内的约束条件，而这把决策变量限制在它们可行值之内的约束条件，而这通常是用约束的数学函数形式来表示的。通常是用约束的数学函数形式来表示的。（3）目标函数。目标函数。这是作为系统决策变量的一个数学函数来衡量系统这是作为系统决策变量的一个数学函数来衡量系统的效率，即系统追求的目标。的效率，即系统追求的目标。解：决定圆柱体表面积大小有两个决策变量：解：决定圆柱体表面积大小有两个决策变量：圆柱体底面半径圆柱体底面半径r、高、高h。问题的约束条件是所铸圆柱体重量与球重相等。问题的约束条件是所铸圆柱体重量与球重相等。即即例例1.把半径为把半径为1的实心金属球熔化后，铸成一个实的实心金属球熔化后，铸成一个实心圆柱体，问圆柱体取什么尺寸才能使它的表面心圆柱体，问圆柱体取什么尺寸才能使它的表面积最小？积最小？则得数学模型：则得数学模型：s.t.Subject to.问题目标是圆柱体表面积最小。即问题目标是圆柱体表面积最小。即 min 即即 即即 此时圆柱体的表面积为此时圆柱体的表面积为 分别对分别对r.h.求偏导数求偏导数,并令其等于零并令其等于零.有有:利用在高等数学中所学的利用在高等数学中所学的Lagrange乘子法可求解本问题乘子法可求解本问题 例例4.多参数曲线拟合问题多参数曲线拟合问题 已知两个物理量已知两个物理量x和和y之间的依赖关系为之间的依赖关系为:其中其中 和和 待定参数待定参数,为确定这些参数为确定这些参数,对对x.y测得测得m个实验点个实验点:试将确定参数的问题表示成最优化问题试将确定参数的问题表示成最优化问题.解解:很显然对参数很显然对参数 和和 任意给定的一组数值任意给定的一组数值,就由上就由上式确定了式确定了 y关于关于x的一个函数关系式的一个函数关系式,在几何上它对应一条曲线在几何上它对应一条曲线,这条这条曲线不一定通过那曲线不一定通过那m个测量点个测量点,而要产生而要产生“偏差偏差”.将测量点沿垂线方向到曲线的距离的将测量点沿垂线方向到曲线的距离的平方和作为这种平方和作为这种“偏差偏差”的度量的度量.即即显然偏差显然偏差S越小越小,曲线就拟合得越好曲线就拟合得越好,说明参数值就选择得越好，从而说明参数值就选择得越好，从而我们的问题就转化为我们的问题就转化为5维无约束最优化问题。即：维无约束最优化问题。即：有约束最优化有约束最优化最优化方法分类最优化方法分类（一一）线线性性最最优优化化：目目标标函函数数和和约约束束条条件件都都是是线线性的则称为线性最优化。性的则称为线性最优化。非非线线性性最最优优化化：目目标标函函数数和和约约束束条条件件如如果果含含有非线性的，则称为非线性最优化。有非线性的，则称为非线性最优化。（二二）静静态态最最优优化化：如如果果可可能能的的方方案案与与时时间间无无关关，则是静态最优化问题。则是静态最优化问题。动态最优化动态最优化：如果可能的方案与时间有关，如果可能的方案与时间有关，则是动态最优化问题则是动态最优化问题有约束最优化问题的数学建模有约束最优化问题的数学建模 有约束最优化模型一般具有以下形式：有约束最优化模型一般具有以下形式：或或 其中其中f(x)为目标函数，省略号表示约束式子，可以是为目标函数，省略号表示约束式子，可以是等式约束，也可以是不等式约束。等式约束，也可以是不等式约束。根根据据目目标标函函数数，约约束束条条件件的的特特点点将将最最优优化方法包含的主要内容大致如下划分：化方法包含的主要内容大致如下划分：线性规划线性规划整数规划整数规划非线性规划非线性规划动态规划动态规划多目标规划多目标规划 对策论对策论最优化方法主要内容最优化方法主要内容最优化问题的一般数学模型最优化问题的一般数学模型最优化问题的一般算法最优化问题的一般算法整体（全局）最优解：整体（全局）最优解：若若 ，对于一切，对于一切 ，恒有，恒有 则称则称 是最优化问题的整体最优解。是最优化问题的整体最优解。局部最优解：局部最优解：若若 ，存在某邻域，存在某邻域 ，使得对于一切，使得对于一切 ，恒有，恒有 则称则称 是最优化问题的局部是最优化问题的局部最优解。其中最优解。其中严格最优解：严格最优解：当当 ，有，有 则称则称 为问题的严为问题的严格最优解。格最优解。f(X)f(X)局部最优解局部最优解局部最优解局部最优解整体最优解整体最优解整体最优解整体最优解 运用最优化方法解决最优化问题的一般运用最优化方法解决最优化问题的一般方法步骤如下：方法步骤如下：前期分析：分析问题，找出要解决的目标，约束条件，前期分析：分析问题，找出要解决的目标，约束条件，并确立最优化的目标。并确立最优化的目标。定义变量，建立最优化问题的数学模型，列出目标函定义变量，建立最优化问题的数学模型，列出目标函数和约束条件。数和约束条件。针对建立的模型，选择合适的求解方法或数学软件。针对建立的模型，选择合适的求解方法或数学软件。编写程序，利用计算机求解。编写程序，利用计算机求解。对结果进行分析，讨论诸如：结果的合理性、正确性，对结果进行分析，讨论诸如：结果的合理性、正确性，算法的收敛性，模型的适用性和通用性，算法效率与算法的收敛性，模型的适用性和通用性，算法效率与误差等。误差等。线性规划的模型的一般形式线性规划的模型的一般形式:目标函数目标函数 满足约束条件满足约束条件 通常称通常称 为决策变量，为决策变量，为价值系数，为价值系数，为消耗系数为消耗系数,为资源限制系数。为资源限制系数。线性规划线性规划用单纯法求解时，常将标准形式化为：线性规划的基本算法线性规划的基本算法单纯形法单纯形法用用MATLAB优化工具箱解线性规划优化工具箱解线性规划minz=cX1、模型：命令：x=linprog（c，A，b）2、模型：minz=cX命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式：存在，则令A=，b=.3、模型：minz=cXVLBXVUB命令：1x=linprog（c，A，b，Aeq,beq,VLB，VUB）2 x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）注意：1若没有等式约束:,则令Aeq=,beq=.2其中X0表示初始点4、命令：x,fval=linprog()返回最优解及处的目标函数值fval.问题问题：任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？引例引例解解 设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：S.t.改写为：问题的解答编写编写M文件文件xxgh3.m如下如下:f=1391011128;A=0.41.110000000.51.21.3;b=800;900;Aeq=100100010010001001;beq=400600500;vlb=zeros(6,1);vub=;x,fval=linprog(f,A,b,Aeq,beq,vlb,vub)结果结果:x=0.0000600.00000.0000400.00000.0000500.0000fval=1.3800e+004即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件的情况下使总加工费最小为13800。例例1 1，某某铁铁器器加加工工厂厂要要制制作作100100套套钢钢架架，每每套套要要用用长长为为2.92.9米米，2.12.1米米和和1.51.5米米的的圆圆钢钢各各一一根根。已已知知原原料料长长为为7.47.4米米，问问应应如如何何下下料料，可可使使材材料料最省？最省？分分析析：在在长长度度确确定定的的原原料料上上截截取取三三种种不不同同规规格格的的圆圆钢钢，可可以以归归纳纳出出8 8种不同的下料方案：种不同的下料方案：圆钢（米）圆钢（米）2 29 91 12 20 01 10 01 10 00 02 21 10 00 02 22 21 11 13 30 01 15 53 31 12 20 03 31 10 04 4料头（米）料头（米）0 00.10.10.20.20.30.30.80.80.90.91.1.1.41.4 问题归纳为如何混合使用这问题归纳为如何混合使用这8 8种不同的下料方案，来制造种不同的下料方案，来制造100100套套钢架，且要使剩余的料头总长为最短。钢架，且要使剩余的料头总长为最短。线性规划的一些应用线性规划的一些应用设设x xj j表示用第表示用第j j种下料方案下料的原料根数，种下料方案下料的原料根数，j=1,28,j=1,28,数学模型数学模型 s.t.s.t.这是一个下料问题，是在生产任务确定的条件下，合理的组织生产，这是一个下料问题，是在生产任务确定的条件下，合理的组织生产，使所消耗的资源数最少的数学规划问题。使所消耗的资源数最少的数学规划问题。满足一组约束条件的同时，寻求变量满足一组约束条件的同时，寻求变量x x1 1至至x x8 8的值的值,使目标函数取得最使目标函数取得最 小值。小值。圆钢（米）圆钢（米）2 29 91 12 20 01 10 01 10 00 02 21 10 00 02 22 21 11 13 30 01 15 53 31 12 20 03 31 10 04 4料头（米）料头（米）0 00.10.10.20.20.30.30.80.80.90.91.11.11.41.4且为整数且为整数 数学模型数学模型 s.t.s.t.且为整数且为整数 设设x xj j表示用第表示用第j j种下料方案下料的原料根数，种下料方案下料的原料根数，j=1,28,j=1,28,例例2:人力资源分配问题人力资源分配问题 红旗商场是个中型的百货商场，它对售货人员的需求经过统计红旗商场是个中型的百货商场，它对售货人员的需求经过统计分析如表所示。为了保证售货人员充分休息，售货人员每周分析如表所示。为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作需要又使配备的售如何安排售货人员的作息，既满足了工作需要又使配备的售货人员的人数最少？货人员的人数最少？表表时时 间间所需售货员人数所需售货员人数星期日星期日28人人星期一星期一15人人星期二星期二24人人星期三星期三25人人星期四星期四19人人星期五星期五31人人星期六星期六28人人解：解：设设x1为星期一开始上班的人数，为星期一开始上班的人数，x2为星期二开始上班的人为星期二开始上班的人数，数，x7星期日开始上班的人数。我们就可得到如下的数星期日开始上班的人数。我们就可得到如下的数学模型：学模型：minx1+x2+x3+x4+x5+x6+x7x3+x4+x5+x6+x728x4+x5+x6+x7+x115x5+x6+x7+x1+x224x6+x7+x1+x2+x325x7+x1+x2+x3+x419x1+x2+x3+x4+x531x2+x3+x4+x5+x628x1、x2、x3、x4、x5、x6、x70该问题的最优解为：x1=8，x2=0，x3=12，x4=0，x5=11，x6=5，x7=0；目标函数的最小值为36。例例3:某公司现有某公司现有68名员工申请提前退休。公司必须在此名员工申请提前退休。公司必须在此后的后的8年内对这些员工分期支付一定数量的现金，如年内对这些员工分期支付一定数量的现金，如下表所示。下表所示。注意，三种政府债券的票面价值均为注意，三种政府债券的票面价值均为1000元，债券到期时按票面价元，债券到期时按票面价值进行支付，利率的计算也以票面的价值为基准。银行储蓄年利率值进行支付，利率的计算也以票面的价值为基准。银行储蓄年利率为为4%。如何安排投资计划，使公司以最小的投资额完成对退休员工。如何安排投资计划，使公司以最小的投资额完成对退休员工的现金支付任务？的现金支付任务？为了完成这项现金支付任务，公司的财务人员必须现在就为此制为了完成这项现金支付任务，公司的财务人员必须现在就为此制定一个投资计划。投资计划有政府债券投资和银行储蓄两种方式定一个投资计划。投资计划有政府债券投资和银行储蓄两种方式组成。政府债券投资有三种债券类型可供选择，如下表所示。组成。政府债券投资有三种债券类型可供选择，如下表所示。年份（年）年份（年）12345678现现金金支支付付（千千元）元）430210222231240195225225债券债券价格（元）价格（元）利率（利率（%）到期年限到期年限111508.8755210005.50063135011.7507解：1确定决策变量确定决策变量 设设F为完成投资计划所需要的总资金额。为完成投资计划所需要的总资金额。x1、x2、x3分别表示债券分别表示债券1、2、3的购买量；的购买量；yi(i=1,，8)表示第表示第 i年初银行储蓄的投资额。年初银行储蓄的投资额。2确定约束条件确定约束条件这类问题的一个典型特征就是每年现金支付的一般表达式为：这类问题的一个典型特征就是每年现金支付的一般表达式为：年初可用资金额年初可用资金额 当年用于债券和储蓄的资金额当年用于债券和储蓄的资金额=当年现金支付当年现金支付于是有于是有 F 1.15x1 1x2 1.35x3 y1=430 （第（第1年）年）对于第二年，用于三种债券投资的第一年利息加上第一年储蓄利对于第二年，用于三种债券投资的第一年利息加上第一年储蓄利息为年初可用资金，第二年用于储蓄的资金为息为年初可用资金，第二年用于储蓄的资金为y2，因此有，因此有0.08875x1+0.055x2+0.1175x3+1.04y1y2=210（第2年）同理对于其它年份有同理对于其它年份有0.08875x1+0.055x2+0.1175x3+1.04y2y3=222（第3年）0.08875x1+0.055x2+0.1175x3+1.04y3y4=231（第4年）0.08875x1+0.055x2+0.1175x3+1.04y4y5=240（第5年）1.08875x1+0.055x2+0.1175x3+1.04y5y6=195（第6年）1.055x2+0.1175x3+1.04y6y7=225（第7年）1.1175x3+1.04y7y8=255（第8年）因此事实上，y8的值应为0，若大于0，那么对应的投资计划必定不是最优的。3.确定目标函数确定目标函数目标就是使满足要求的投资额最小，即目标就是使满足要求的投资额最小，即Minz=F综合有如下数学模型综合有如下数学模型 Minz=FF1.15x11x21.35x3y1=4300.08875x1+0.055x2+0.1175x3+1.04y1y2=2100.08875x1+0.055x2+0.1175x3+1.04y2y3=2220.08875x1+0.055x2+0.1175x3+1.04y3y4=2310.08875x1+0.055x2+0.1175x3+1.04y4y5=2401.08875x1+0.055x2+0.1175x3+1.04y5y6=1951.055x2+0.1175x3+1.04y6y7=2251.1175x3+1.04y7y8=255x1，x2，x30，yi0，i=1，8该线性规划模型的求解结果为目标函数最优值为：1728.794变量最优解检验数F1728.7940 x1144.9880 x2187.8560 x3228.1880y1636.1480y2501.6060y3349.6820y4182.6810y500.064y600.0126y700.0213y800.671债券债券购买量购买量投资额（千元）投资额（千元）年份年份储蓄额储蓄额（千元）（千元）1144.9881.150144.988=166.7361636.1482187.8561.000187.856=187.8562501.6063228.1881.350228.188=308.0543349.682总投资额总投资额 F=1728794 元元4182.681580即得到最佳投资计划如下表所示。约束松弛/剩余变量对偶价格101.000200.962300.925400.889500.855600.760700.719800.671结果分析：结果分析：前前4年的储蓄额均大于年的储蓄额均大于0，可见从第，可见从第6年起债券的利息和债券到年起债券的利息和债券到期收入才能够完全满足当前现金支付需要。期收入才能够完全满足当前现金支付需要。每一个约束条件的对偶价格均为负值，说明减少任何一年的每一个约束条件的对偶价格均为负值，说明减少任何一年的现金支付都将有利于公司总投资额的降低。现金支付都将有利于公司总投资额的降低。对偶价格的逐年降低也说明了，在前面年份减少现金支付将对偶价格的逐年降低也说明了，在前面年份减少现金支付将对总投资额的减少更为有效。从而暗示了公司可以适当减少对总投资额的减少更为有效。从而暗示了公司可以适当减少前面年份的现金支付量，而在后面年份进行补足。前面年份的现金支付量，而在后面年份进行补足。Minz=FF1.15x11x21.35x3y1=4300.08875x1+0.055x2+0.1175x3+1.04y1y2=2100.08875x1+0.055x2+0.1175x3+1.04y2y3=2220.08875x1+0.055x2+0.1175x3+1.04y3y4=2310.08875x1+0.055x2+0.1175x3+1.04y4y5=2401.08875x1+0.055x2+0.1175x3+1.04y5y6=1951.055x2+0.1175x3+1.04y6y7=2251.1175x3+1.04y7y8=255x1，x2，x30，yi0，i=1，8线性规划应用小结线性规划应用小结线性规划有着广泛的应用；线性规划的应用非常灵活；所讲案例只是真实情况的缩微；投资的收益和风险投资的收益和风险(98A)二、基本假设和符号规定二、基本假设和符号规定三、模型的建立与分析三、模型的建立与分析1.总体风险用所投资的Si中最大的一个风险来衡量,即max qixi|i=1，2,n4.模型简化：四、模型四、模型1 1的求解的求解 由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从a=0开始，以步长a=0.001进行循环搜索，编制程序如下：a=0;while(1.1-a)1c=-0.05-0.27-0.19-0.185-0.185;Aeq=11.011.021.0451.065;beq=1;A=00.025000;000.01500;0000.0550;00000.026;b=a;a;a;a;vlb=0,0,0,0,0;vub=;x,val=linprog(c,A,b,Aeq,beq,vlb,vub);ax=xQ=-valplot(a,Q,.)，axis(00.100.5)，holdona=a+0.001;endxlabel(a),ylabel(Q)计算结果：计算结果：五、五、结果分析结果分析3.3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。2 2.当投资越分散时，投资者承担的风险越小，这与题意一致。即:冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。1.1.风险大，收益也大。4 4.在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是a*=0.6%，Q*=20%，所对应投资方案为:风险度收益x0 x1x2x3x4 0.0060 0.2019 0 0.2400 0.4000 0.1091 0.2212 无约束最优化问题无约束最优化问题标准形式：标准形式：求解无约束最优化问题的基本思想求解无约束最优化问题的基本思想求解的基本思想求解的基本思想(以二元函数为例)531连续可微多局部极小唯一极小(全局极小)搜索过程搜索过程最优点(11)初始点(-11)-114.00-0.790.583.39-0.530.232.60-0.180.001.500.09-0.030.980.370.110.470.590.330.200.800.630.050.950.90 0.0030.990.991E-40.9990.9981E-50.9997 0.9998 1E-8无约束优化问题的基本算法无约束优化问题的基本算法 最速下降法是一种最基本的算法，它在最优化方法中占有重要地位.最速下降法的优点是工作量小，存储变量较少,初始点要求不高；缺点是收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值点时，宜选用别种收敛快的算法.1 1最速下降法（共轭梯度法）算法步骤：最速下降法（共轭梯度法）算法步骤：2 2牛顿法算法步骤：牛顿法算法步骤：如果f是对称正定矩阵A的二次函数，则用牛顿法经过一次迭代一次迭代就可达到最优点,如不是二次函数，则牛顿法不能一步达到极值点，但由于这种函数在极值点附近和二次函数很近似,因此牛顿法的收敛速度还是很快的.牛顿法的收敛速度虽然较快，但要求Hessian矩阵要可逆，要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量.3 3拟牛顿法拟牛顿法其他多种直接算法(单纯形调优法,H_J法,Powell方向加速法等)MatlabMatlab优化工具箱简介优化工具箱简介1.MATLAB1.MATLAB求解优化问题的主要函数求解优化问题的主要函数2.2.优化函数的输入变量优化函数的输入变量 使用优化函数或优化工具箱中其它优化函数时,输入变量见下表:3.3.优化函数的输出变量下表优化函数的输出变量下表:用用MatlabMatlab解无约束优化问题解无约束优化问题 其中（3）、（4）、（5）的等式右边可选用（1）或（2）的等式右边。函数fminbnd的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解。常用格式如下：常用格式如下：（1）x=fminbnd(x=fminbnd(fun,xfun,x1 1,x,x2 2)（2）x=fminbnd(x=fminbnd(fun,xfun,x1 1,x,x2 2 ，options)options)（3）xx，fval=fminbndfval=fminbnd（.）（4）xx，fvalfval，exitflag=fminbndexitflag=fminbnd（.）（5）xx，fvalfval，exitflagexitflag，output=fminbndoutput=fminbnd（.）主程序为主程序为wliti1.m: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 2 对边长为3米的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？解解先编写先编写M M文件文件fun0.mfun0.m如下如下:function f=fun0(x)f=-(3-2*x).2*x;主程序为主程序为wliti2.m:wliti2.m:x,fval=fminbnd(fun0,0,1.5);xmax=x fmax=-fval运算结果为运算结果为:xmax=0.5000,fmax=2.0000.即剪掉的正方形的边长为0.5米时水槽的容积最大,最大容积为2立方米.命令格式为命令格式为:（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、多元函数无约束优化问题、多元函数无约束优化问题标准型为标准型为：minF(X)3 fminunc为中型优化算法的步长一维搜索提供了两种算法，由options中参数LineSearchType控制：LineSearchType=quadcubic(缺省值)，混合的二次和三 次多项式插值；LineSearchType=cubicpoly，三次多项式插使用使用fminuncfminunc和和 fminsearchfminsearch可能会得到局部最优解可能会得到局部最优解.说明说明:fminsearchfminsearch是用单纯形法寻优是用单纯形法寻优.fminuncfminunc的算法见以下的算法见以下几点说明：几点说明：1 fminunc为无约束优化提供了大型优化和中型优化算法。由options中的参数LargeScale控制：LargeScale=on(默认值),使用大型算法LargeScale=off,使用中型算法2 fminunc为中型优化算法的搜索方向提供了4种算法，由 options中的参数HessUpdate控制：HessUpdate=bfgs（默认值），拟牛顿法的BFGS公式；HessUpdate=dfp，拟牛顿法的DFP公式；HessUpdate=steepdesc，最速下降法例例3 3 min f(x)=(4x12+2x22+4x1x2+2x2+1)*exp(x1)1 1、编写、编写M-M-文件文件 fun1.m:fun1.m:function f=fun1(x)f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);2 2、输入、输入M M文件文件wliti3.mwliti3.m如下如下:x0=-1,1;x=fminunc(fun1,x0);y=fun1(x)3 3、运行结果、运行结果:x=0.5000 -1.0000 y=1.3029e-103.3.用用fminsearchfminsearch函数求解函数求解输入命令: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:202algorithm:Nelder-Meadsimplexdirectsearch4.4.用用fminunc fminunc 函数函数(1)建立M-文件fun2.mfunctionf=fun2(x)f=100*(x(2)-x(1)2)2+(1-x(1)2(2)主程序wliti44.m RosenbrockRosenbrock函数不同算法的计算结果函数不同算法的计算结果可以看出，最速下降法的结果最差.因为最速下降法特别不适合于从一狭长通道到达最优解的情况.例例5 5 产销量的最佳安排产销量的最佳安排 某厂生产一种产品有甲、乙两个牌号，讨论在产销平衡的情况下如何确定各自的产量，使总利润最大.所谓产销平衡指工厂的产量等于市场上的销量.基本假设基本假设1 1价格与销量成线性关系价格与销量成线性关系2 2成本与产量成负指数关系成本与产量成负指数关系 模型建立模型建立 若根据大量的统计数据,求出系数b1=100,a11=1,a12=0.1,b2=280,a21=0.2,a22=2,r1=30,1=0.015,c1=20,r2=100,2=0.02,c2=30,则问题转化为无约束优化问题：求甲,乙两个牌号的产量x1，x2，使总利润z最大.为简化模型,先忽略成本,并令a12=0,a21=0,问题转化为求:z1=(b1-a11x1)x1+(b2-a22x2)x2 的极值.显然其解为x1=b1/2a11=50,x2=b2/2a22=70,我们把它作为原问题的初始值.总总利润利润为：为：z z(x x1 1,x,x2 2)=()=(p p1 1-q-q1 1)x x1 1+(+(p p2 2-q-q2 2)x x2 2 模型求解模型求解 1.建立M-文件fun.m:function f=fun(x)y1=(100-x(1)-0.1*x(2)-(30*exp(-0.015*x(1)+20)*x(1);y2=(280-0.2*x(1)-2*x(2)-(100*exp(-0.02*x(2)+30)*x(2);f=-y1-y2;2.输入命令:x0=50,70;x=fminunc(fun,x0),z=fun(x)3.计算结果:x=23.9025,62.4977,z=6.4135e+003 即甲的产量为23.9025,乙的产量为62.4977,最大利润为6413.5.约束非线性规划约束非线性规划 定义定义如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题非线性规划问题约束非现性规划的基本概念约束非现性规划的基本概念 一般形式一般形式:（1）其中 ，是定义在 En 上的实值函数，简记:其它情况其它情况:求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式非线性规划的基本解法非线性规划的基本解法SUTM外点法外点法SUTM内点法（障碍罚函数法）内点法（障碍罚函数法）1、罚函数法、罚函数法2、近似规划法近似规划法 罚函数法罚函数法 罚函数法罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解这类方法称为序列无约束最小化方法序列无约束最小化方法简称为SUMTSUMT法法 其一为SUMTSUMT外点法外点法，其二为SUMTSUMT内点法内点法 其中T(X,M)称为罚函数罚函数，M称为罚因子罚因子，带M的项称为罚项罚项，这里的罚函数只对不满足约束条件的点实行惩罚：当 时，满足各 ，故罚项=0，不受惩罚当 时，必有 的约束条件，故罚项0，要受惩罚SUTMSUTM外点法外点法 罚函数法的缺点缺点是：每个近似最优解Xk往往不是容许解，而只能近似满足约束，在实际问题中这种结果可能不能使用；在解一系列无约束问题中，计算量太大，特别是随着Mk的增大，可能导致错误1、任意给定初始点X0，取M11，给定允许误差 ，令k=1；2、求无约束极值问题 的最优解，设为Xk=X(Mk)，即 ；3、若存在 ，使 ，则取MkM()令k=k+1返回（2），否则，停止迭代得最优解 .计算时也可将收敛性判别准则 改为 .SUTMSUTM外点法外点法(罚函数法)的迭代步骤迭代步骤SUTMSUTM内点法（内点法（障碍函数法）内点法的迭代步骤内点法的迭代步骤 近似规划法的基本思想近似规划法的基本思想：将问题(3)中的目标函数 和约束条件 近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似线性规划问题，再用单纯形法求解之，把其符合原始条件的最优解作为(3)的解的近似近似规划法近似规划法每得到一个近似解后，都从这点出发，重复以上步骤 这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序列，经验表明，这样的序列往往收敛于非线性规划问题的解。近似规划法的算法步骤如下算法步骤如下用MATLAB软件求解,其输入格式输入格式如下:1.x=quadprog(H,C,A,b);2.x=quadprog(H,C,A,b,Aeq,beq);3.x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB);4.x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0);5.x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0,options);6.x,fval=quaprog(.);7.x,fval,exitflag=quaprog(.);8.x,fval,exitflag,output=quaprog(.);1、二次规划、二次规划例例1 1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t.x1+x22 -x1+2x22 x10,x20 1、写成标准形式写成标准形式：2、输入命令输入命令：H=1-1;-1 2;c=-2;-6;A=1 1;-1 2;b=2;2;Aeq=;beq=;VLB=0;0;VUB=;x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB)3、运算结果运算结果为：x=0.6667 1.3333 z=-8.2222s.t.1.首先建立M文件fun.m,定义目标函数F（X）:function f=fun(X);f=F(X);2、一般约束非线性规划、一般约束非线性规划 其中X为n维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同.用Matlab求解上述问题，基本步骤分三步：3.建立主程序.非线性规划求解的函数是fmincon,命令的基本格式如下：(1)x=fmincon(fun,X0,A,b)(2)x=fmincon(fun,X0,A,b,Aeq,beq)(3)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB)(4)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon)(5)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon,options)(6)x,fval=fmincon(.)(7)x,fval,exitflag=fmincon(.)(8)x,fval,exitflag,output=fmincon(.)输出极值点M文件迭代的初值参数说明变量上下限注意：注意：1 fmincon函数提供了大型优化算法和中型优化算法。默认时，若在fun函数中提供了梯度（options参数的GradObj设置为on），并且只有上下界存在或只有等式约束，fmincon函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。2 fmincon函数的中型算法使用的是序列二次规划法。在每一步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日Hessian矩阵。3 fmincon函数可能会给出局部最优解，这与初值X0的选取有关。1、写成标准形式写成标准形式：s.t.2x1+3x2 6 s.t x1+4x2 5 x1,x2 0例例22、先建立先建立M-文件文件 fun3.m:function f=fun3(x);f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)23、再建立主程序youh2.m：x0=1;1;A=23;14;b=6;5;Aeq=;beq=;VLB=0;0;VUB=;x,fval=fmincon(fun3,x0,A,b,Aeq,beq,VLB,VUB)4、运算结果为：运算结果为：x=0.76471.0588fval=-2.02941先建立先建立M文件文件 fun4.m,定义目标函数定义目标函数:function f=fun4(x);f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);x1+x2=0s.t.1.5+x1x2-x1-x20-x1x2100例例32再建立再建立M文件文件mycon.m定义非线性约束：定义非线性约束：functiong,ceq=mycon(x)g=x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;3主程序主程序youh3.m为为:x0=-1;1;A=;b=;Aeq=11;beq=0;vlb=;vub=;x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb,vub,mycon)3.运算结果为运算结果为：x=-1.2250 1.2250 fval=1.8951 例4 1先建立先建立M-文件文件fun.m定义目标函数定义目标函数:function f=fun(x);f=-2*x(1)-x(2);2再建立再建立M文件文件mycon2.m定义非线性约束：定义非线性约束：function g,ceq=mycon2(x)g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;3.主程序主程序fxx.m为为:x0=3;2.5;VLB=0 0;VUB=5 10;x,fval,exitflag,output =fmincon(fun,x0,VLB,VUB,mycon2)4.运算结果为运算结果为:x=4.0000 3.0000fval=-11.0000exitflag=1output=iterations:4 funcCount:17 stepsize:1 algorithm:1x44 char firstorderopt:cgiterations:应用实例：应用实例：供应与选址供应与选址某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：千米）及水泥日用量d(吨)由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连。（1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？（一）、建立模型（一）、建立模型记工地的位置为记工地的位置为(ai，bi)，水泥日用量为，水泥日用量为di，i=1,6;料场位置为料场位置为(xj，yj)，日储量为，日储量为ej，j=1,2；从料场；从料场j向工地向工地i的运送量为的运送量为Xij。当用临时料场时决策变量为：Xij，当不用临时料场时决策变量为：Xij，xj，yj。（二）使用临时料场的情形（二）使用临时料场的情形使用两个临时料场A(5,1)，B(2,7).求从料场j向工地i的运送量为Xij，在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题.线性规划模型为：设X11=X1,X21=X2,X31=X3,X41=X4,X51=X5,X61=X6X12=X7,X22=X8,X32=X9,X42=X10,X52=X11,X62=X12编写程序gying1.m计算结果为：计算结果为：x=3.00005.00000.00007.00000.00001.00000.00000.00004.00000.00006.000010.0000fval=136.2275（三）改建两个新料场的情形（三）改建两个新料场的情形 改建两个新料场，要同时确定料场的位置(xj,yj)和运送量Xij，在同样条件下使总吨千米数最小。这是非线性规划问题。非线性规划模型为：设X11=X1,X21=X2,X31=X3,X41=X4,X51=X5,X61=X6X12=X7,X