数学建模-最优化模型.ppt

最优化模型,一、最优化方法概述,二、无约束最优化问题,三、无约束最优化问题的MATLAB求解,四、有约束最优化问题,最优化方法概述,1、最优化理论和方法是近二十多年来发展十分迅速的一个数学分支。2、在数学上，最优化是一种求极值的方法。3、最优化已经广泛的渗透到工程、经济、电子技术等领域。,在实际生活当中，人们做任何事情，不管是分析问题，还是进行决策，都要用一种标准衡量一下是否达到了最优。（比如基金人投资）在各种科学问题、工程问题、生产管理、社会经济问题中，人们总是希望在有限的资源条件下，用尽可能小的代价，获得最大的收获。（比如保险）,数学家对最优化问题的研究已经有很多年的历史。以前解决最优化问题的数学方法只限于古典求导方法和变分法（求无约束极值问题），拉格朗日（Lagrange）乘数法解决等式约束下的条件极值问题。计算机技术的出现，使得数学家研究出了许多最优化方法和算法用以解决以前难以解决的问题。,最优化：在一定的条件下，寻求使得目标最大（最小）的策略,约一半以上的问题与最优化问题有关。如：飞行管理问题（95A）最优捕鱼策略（96A）节水洗衣机（96B）零件的参数设计(97A)投资收益和风险(98A)钢管订购和运输(2000B)电力市场的堵塞管理(2004B),几个概念,最优化是从所有可能方案中选择最合理的一种以达到最优目标的学科。最优方案是达到最优目标的方案。最优化方法是搜寻最优方案的方法。最优化理论就是最优化方法的理论。,经典极值问题,包括：无约束极值问题约束条件下的极值问题,1、无约束极值问题的数学模型,2、约束条件下极值问题的数学模型,其中，极大值问题可以转化为极小值问题来进行求解。如求：,可以转化为：,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解无约束优化问题,其中等式（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如下: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,例用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,建立数学模型时要尽可能简单，而且要能完整地描述所研究的系统，具体建立怎样的数学模型需要丰富的经验和熟练的技巧。即使在建立了问题的数学模型之后，通常也必须对模型进行必要的数学简化以便于分析、计算。,一般的模型简化工作包括以下几类：（1）将离散变量转化为连续变量。（2）将非线性函数线性化。（3）删除一些非主要约束条件。,最优化问题的数学模型,建立最优化问题数学模型的三要素：,（1）决策变量和参数。决策变量是由数学模型的解确定的未知数。参数表示系统的控制变量，有确定性的也有随机性的。,（2）约束或限制条件。由于现实系统的客观物质条件限制，模型必须包括把决策变量限制在它们可行值之内的约束条件，而这通常是用约束的数学函数形式来表示的。,（3）目标函数。这是作为系统决策变量的一个数学函数来衡量系统的效率，即系统追求的目标。,解：决定圆柱体表面积大小有两个决策变量：圆柱体底面半径r、高h。问题的约束条件是所铸圆柱体重量与球重相等。即,例1.把半径为1的实心金属球熔化后，铸成一个实心圆柱体，问圆柱体取什么尺寸才能使它的表面积最小？,则得数学模型：s.t.Subjectto.,问题目标是圆柱体表面积最小。即min,即即,此时圆柱体的表面积为,分别对r.h.求偏导数,并令其等于零.有:,利用在高等数学中所学的Lagrange乘子法可求解本问题,例4.多参数曲线拟合问题已知两个物理量x和y之间的依赖关系为:其中和待定参数,为确定这些参数,对x.y测得m个实验点:试将确定参数的问题表示成最优化问题.,解:很显然对参数和任意给定的一组数值,就由上式确定了y关于x的一个函数关系式,在几何上它对应一条曲线,这条曲线不一定通过那m个测量点,而要产生“偏差”.将测量点沿垂线方向到曲线的距离的平方和作为这种“偏差”的度量.即显然偏差S越小,曲线就拟合得越好,说明参数值就选择得越好，从而我们的问题就转化为5维无约束最优化问题。即：,有约束最优化最优化方法分类（一）线性最优化：目标函数和约束条件都是线性的则称为线性最优化。非线性最优化：目标函数和约束条件如果含有非线性的，则称为非线性最优化。（二）静态最优化：如果可能的方案与时间无关，则是静态最优化问题。动态最优化：如果可能的方案与时间有关，则是动态最优化问题,有约束最优化问题的数学建模,有约束最优化模型一般具有以下形式：,或,其中f(x)为目标函数，省略号表示约束式子，可以是等式约束，也可以是不等式约束。,根据目标函数，约束条件的特点将最优化方法包含的主要内容大致如下划分：线性规划整数规划非线性规划动态规划多目标规划对策论,最优化方法主要内容,最优化问题的一般数学模型,最优化问题的一般算法,整体（全局）最优解：若，对于一切，恒有则称是最优化问题的整体最优解。局部最优解：若，存在某邻域，使得对于一切，恒有则称是最优化问题的局部最优解。其中严格最优解：当，有则称为问题的严格最优解。,f(X),局部最优解,整体最优解,运用最优化方法解决最优化问题的一般方法步骤如下：前期分析：分析问题，找出要解决的目标，约束条件，并确立最优化的目标。定义变量，建立最优化问题的数学模型，列出目标函数和约束条件。针对建立的模型，选择合适的求解方法或数学软件。编写程序，利用计算机求解。对结果进行分析，讨论诸如：结果的合理性、正确性，算法的收敛性，模型的适用性和通用性，算法效率与误差等。,线性规划的模型的一般形式:目标函数满足约束条件通常称为决策变量，为价值系数，为消耗系数,为资源限制系数。,线性规划,用单纯法求解时，常将标准形式化为：,线性规划的基本算法单纯形法,用MATLAB优化工具箱解线性规划,命令：x=linprog（c，A，b）,2、模型：minz=cX,命令：x=linprog（c，A，b，Aeq,beq）,注意：若没有不等式：存在，则令A=，b=.,命令：1x=linprog（c，A，b，Aeq,beq,VLB，VUB）2x=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。可建立以下线性规划模型：,问题的解答,编写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，某铁器加工厂要制作100套钢架，每套要用长为2.9米，2.1米和1.5米的圆钢各一根。已知原料长为7.4米，问应如何下料，可使材料最省？分析：在长度确定的原料上截取三种不同规格的圆钢，可以归纳出8种不同的下料方案：,问题归纳为如何混合使用这8种不同的下料方案，来制造100套钢架，且要使剩余的料头总长为最短。,线性规划的一些应用,设xj表示用第j种下料方案下料的原料根数，j=1,28,数学模型s.t.这是一个下料问题，是在生产任务确定的条件下，合理的组织生产，使所消耗的资源数最少的数学规划问题。满足一组约束条件的同时，寻求变量x1至x8的值,使目标函数取得最小值。,且为整数,数学模型s.t.,且为整数,设xj表示用第j种下料方案下料的原料根数，j=1,28,例2:人力资源分配问题红旗商场是个中型的百货商场，它对售货人员的需求经过统计分析如表所示。为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作需要又使配备的售货人员的人数最少？表,解：设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%。如何安排投资计划，使公司以最小的投资额完成对退休员工的现金支付任务？,为了完成这项现金支付任务，公司的财务人员必须现在就为此制定一个投资计划。投资计划有政府债券投资和银行储蓄两种方式组成。政府债券投资有三种债券类型可供选择，如下表所示。,解：1确定决策变量设F为完成投资计划所需要的总资金额。x1、x2、x3分别表示债券1、2、3的购买量；yi(i=1,，8)表示第i年初银行储蓄的投资额。2确定约束条件这类问题的一个典型特征就是每年现金支付的一般表达式为：年初可用资金额当年用于债券和储蓄的资金额=当年现金支付于是有F1.15x11x21.35x3y1=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,即得到最佳投资计划如下表所示。,约束松弛/剩余变量对偶价格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中最大的一个风险来衡量,即maxqixi|i=1，2,n,4.模型简化：,四、模型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.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。,2.当投资越分散时，投资者承担的风险越小，这与题意一致。即:冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。,1.风险大，收益也大。,4.在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是a*=0.6%，Q*=20%，所对应投资方案为:风险度收益x0 x1x2x3x40.00600.201900.24000.40000.10910.2212,无约束最优化问题,标准形式：,求解无约束最优化问题的基本思想,求解的基本思想(以二元函数为例),5,3,1,连续可微,多局部极小,唯一极小(全局极小),搜索过程,最优点(11)初始点(-11),-1,1,4.00,-0.79,0.58,3.39,-0.53,0.23,2.60,-0.18,0.00,1.50,0.09,-0.03,0.98,0.37,0.11,0.47,0.59,0.33,0.20,0.80,0.63,0.05,0.95,0.90,0.003,0.99,0.99,1E-4,0.999,0.998,1E-5,0.9997,0.9998,1E-8,无约束优化问题的基本算法,最速下降法是一种最基本的算法，它在最优化方法中占有重要地位.最速下降法的优点是工作量小，存储变量较少,初始点要求不高；缺点是收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值点时，宜选用别种收敛快的算法.,1最速下降法（共轭梯度法）算法步骤：,2牛顿法算法步骤：,如果f是对称正定矩阵A的二次函数，则用牛顿法经过一次迭代就可达到最优点,如不是二次函数，则牛顿法不能一步达到极值点，但由于这种函数在极值点附近和二次函数很近似,因此牛顿法的收敛速度还是很快的.,牛顿法的收敛速度虽然较快，但要求Hessian矩阵要可逆，要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量.,3拟牛顿法,其他多种直接算法(单纯形调优法,H_J法,Powell方向加速法等),Matlab优化工具箱简介,1.MATLAB求解优化问题的主要函数,2.优化函数的输入变量,使用优化函数或优化工具箱中其它优化函数时,输入变量见下表:,3.优化函数的输出变量下表:,用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（.）,主程序为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对边长为3米的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？,解,先编写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.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),3fminunc为中型优化算法的步长一维搜索提供了两种算法，由options中参数LineSearchType控制：LineSearchType=quadcubic(缺省值)，混合的二次和三次多项式插值；LineSearchType=cubicpoly，三次多项式插,使用fminunc和fminsearch可能会得到局部最优解.,说明:,fminsearch是用单纯形法寻优.fminunc的算法见以下几点说明：,1fminunc为无约束优化提供了大型优化和中型优化算法。由options中的参数LargeScale控制：LargeScale=on(默认值),使用大型算法LargeScale=off,使用中型算法,2fminunc为中型优化算法的搜索方向提供了4种算法，由options中的参数HessUpdate控制：HessUpdate=bfgs（默认值），拟牛顿法的BFGS公式；HessUpdate=dfp，拟牛顿法的DFP公式；HessUpdate=steepdesc，最速下降法,例3minf(x)=(4x12+2x22+4x1x2+2x2+1)*exp(x1),1、编写M-文件fun1.m:functionf=fun1(x)f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);2、输入M文件wliti3.m如下:x0=-1,1;x=fminunc(fun1,x0);y=fun1(x),3、运行结果:x=0.5000-1.0000y=1.3029e-10,3.用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:202algorithm:Nelder-Meadsimplexdirectsearch,4.用fminunc函数,(1)建立M-文件fun2.mfunctionf=fun2(x)f=100*(x(2)-x(1)2)2+(1-x(1)2,(2)主程序wliti44.m,Rosenbrock函数不同算法的计算结果,可以看出，最速下降法的结果最差.因为最速下降法特别不适合于从一狭长通道到达最优解的情况.,例5产销量的最佳安排某厂生产一种产品有甲、乙两个牌号，讨论在产销平衡的情况下如何确定各自的产量，使总利润最大.所谓产销平衡指工厂的产量等于市场上的销量.,基本假设,1价格与销量成线性关系,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(x1,x2)=(p1-q1)x1+(p2-q2)x2,模型求解,1.建立M-文件fun.m:functionf=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、近似规划法,罚函数法,罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解这类方法称为序列无约束最小化方法简称为SUMT法其一为SUMT外点法，其二为SUMT内点法,其中T(X,M)称为罚函数，M称为罚因子，带M的项称为罚项，这里的罚函数只对不满足约束条件的点实行惩罚：当时，满足各，故罚项=0，不受惩罚当时，必有的约束条件，故罚项0，要受惩罚,SUTM外点法,罚函数法的缺点是：每个近似最优解Xk往往不是容许解，而只能近似满足约束，在实际问题中这种结果可能不能使用；在解一系列无约束问题中，计算量太大，特别是随着Mk的增大，可能导致错误,1、任意给定初始点X0，取M11，给定允许误差，令k=1；2、求无约束极值问题的最优解，设为Xk=X(Mk)，即；3、若存在，使，则取MkM()令k=k+1返回（2），否则，停止迭代得最优解.计算时也可将收敛性判别准则改为.,SUTM外点法(罚函数法)的迭代步骤,SUTM内点法（障碍函数法）,内点法的迭代步骤,近似规划法的基本思想：将问题(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、二次规划,例1minf(x1,x2)=-2x1-6x2+x12-2x1x2+2x22s.t.x1+x22-x1+2x22x10,x20,1、写成标准形式：,2、输入命令：H=1-1;-12;c=-2;-6;A=11;-12;b=2;2;Aeq=;beq=;VLB=0;0;VUB=;x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB),3、运算结果为：x=0.66671.3333z=-8.2222,s.t.,1.首先建立M文件fun.m,定义目标函数F（X）:functionf=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文件,迭代的初值,参数说明,变量上下限,注意：1fmincon函数提供了大型优化算法和中型优化算法。默认时，若在fun函数中提供了梯度（options参数的GradObj设置为on），并且只有上下界存在或只有等式约束，fmincon函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。2fmincon函数的中型算法使用的是序列二次规划法。在每一步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日Hessian矩阵。3fmincon函数可能会给出局部最优解，这与初值X0的选取有关。,1、写成标准形式：s.t.,2x1+3x26s.tx1+4x25x1,x20,例2,2、先建立M-文件fun3.m:functionf=fun3(x);f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)2,3、再建立主程序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.0294,1先建立M文件fun4.m,定义目标函数:functionf=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,例3,2再建立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.22501.2250fval=1.8951,例4,1先建立M-文件fun.m定义目标函数:functionf=fun(x);f=-2*x(1)-x(2);,2再建立M文件mycon2.m定义非线性约束：functiong,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=00;VUB=510;x,fval,exitflag,output=fmincon(fun,x0,VLB,VUB,mycon2),4.运算结果为:x=4.00003.0000fval=-11.0000exitflag=1output=iterations:4funcCount:17stepsize:1algorithm:1x44charfirstorderopt: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,X22=X8,X32=X9,X42=X10,X52=X11,X62=X12x1=X13,y1=X14,x2=X15,y2=X16,（1）先编写M文件liaoch.m定义目标函数。,(2)取初值为线性规划的计算结果及临时料场的坐标:x0=35070100406105127;编写主程序gying2.m.,(3)计算结果为：,x=3.00005.00000.07077.000000.9293003.929306.000010.07076.38754.39435.75117.1867fval=105.4626exitflag=1,(4)若修改主程序gying2.m,取初值为上面的计算结果:x0=3.00005.00000.07077.000000.9293003.929306.000010.07076.38754.39435.75117.1867,得结果为:x=3.00