最优化方法讲稿.doc

第五章 最优化方法第五章 最优化方法在国民经济各部门和科学技术的各个领域中普遍存在着最优化问题(如工业设计中的参数选择,资源合理分配等等).最优化问题的解就是从所有可能的方案中选出最合理的, 以达到最优目标的方案-最优方案. 搜寻最优方案的方法就是最优化方法. 随着计算机科学的发展和广泛应用, 应用最优化方法解决问题的领域不断扩大, 解决问题的深度不断深化, 最优化的理论和方法也不断得到普及和发展. 近几年的大学生数学建模竞赛题目很多都与最优化问题有关(如飞行管理问题(95A),最优捕鱼策略(96A),节水洗衣机(96B),零件参数设计(97A),投资的收益和风险(98A),钢管订购和运输(2000B). 这里, 我们主要介绍最典型的优化模型及应用背景、相关的优化理论和最常用的优化算法.建立最优化问题的数学模型, 首先要确定问题的决策变量, 用n维向量表示, 然后构造模型的目标函数f(X)和决策变量的允许取值范围,称可行域,常用一组不等式来界定, 称为约束条件. 一般地,这类模型可表述成如下形式: (0.1)s.t. (0.2)只满足(0.2)的解x称可行解, 同时满足(0.1)、（0.2）的解称为最优解.1 线性规划如果(0.1)(0.2)中的目标函数f(x)和约束条件都是线性函数, 该模型称为线性规划.模型为 （LP）11 线性规划模型的标准型: (1)s.t. (2)其中线性规划的其他形式可通过形式变换和添加松弛变量而化为标准型.12 求解方法:单纯形方法是通过迭代来求问题（LP）的最优解，在一个基本可行解非最优时，确定一个更优的基本可行解，形成一个使目标函数单调减的基本可行解序列，经有限步即可求得最优解13 模型示例:例1.1 运输问题:设有m个生产地点可供应物资,其供应量(产量)分别为.有n个销售地点,其需求量分别为, 假设供需平衡既.用表示由运输单位物资的运价, 如何确定一种调运方案才能使总运输费用最小. 用表示由调运物资的数量, 则运输问题的数学模型为: s.t.14 利用MATLAB优化工具箱解线性规划 Matlab求解线性规划的命令为1) x=linprog(c,A,b,Aeq,beq)2) x=linprog(c,A,b, Aeq,beq ,vlb,vub)3) x=linprog(c,A,b, Aeq,beq ,vlb,vub,x0);x0表示初始点4) x=lp(c,A,b, Aeq,beq ,vlb,vub,x0,options);x0表示初始点其中1)用于求解模型 s.t. 2)、3)、4)用于求解 s.t. 例1 求解线性规划问题 s.t. 其中c=-0.4,-0.28,-0.32,-0.72,-0.64,-0.6A=0.01 0.01 0.01 0.03 0.03 0.03 0.02 0 0 0.05 0 0 0 0.02 0 0 0.05 0 0 0 0.03 0 0 0.08b=850;700;100;900vlb=0;0;0;0;0;0vub=解 用命令2）l11.mc=-0.4,-0.28,-0.32,-0.72,-0.64,-0.6;A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0; 0 0.02 0 0 0.05 0; 0 0 0.03 0 0 0.08;b=850;700;100;900;vlb=0;0;0;0;0;0;vub=;x=linprog(c,A,b,vlb,vub)f=c*x例2 求解线性规划问题 解 用命令3)l12.mc=6,3,4;A=1,1,1;0,1,0;b=120;50;vlb=30,0,20;vub=;x0=0;0;0;Aeq=1,1,1;Beq=120;x=lp(c,A,b,Aeq,beq,vlb,vub,x0)z=c*x2 整数线性规划在某些线性规划问题中,决策变量只能取整数（如人数、机器的数量）,这时约束条件中还需添加变量取整的限制,这就是整数线性规划,模型的一般形式为 （ILP）如果其中只有部分变量取整数,称为混合整数规划. 决策变量只能取整数0或1的称为0-1规划21 整数线性规划的求解方法21.1割平面法用于求解纯整数规划21.2 分枝定界法用于求解混合整数规划.213 穷举法-用于规模不大的整数问题的求解22 建模示例 例2.1 背包问题：有一只背包(泛指仓库、船舱、卫星仓等)，最大装载重量为w单位。现有k种物品，每种的数量无限。第i种物品每件重量为，价值。每种物品各取多少装入背包，使其中的物品总价值最高。 设取第i种物品 件,则 s.t. 3 无约束优化无约束优化的模型为 它的最优解都是局部最优解,全局最优解只能从局部最优解的比较中得到.31 最优解条件 必要条件: 若为的极小点，则=0充分条件:若 =0, 正定，则是极小点32 求解方法:搜索算法(数值迭代) 数值迭代的基本思路是在迭代的每一步,确定一个搜索方向和一个步长,使沿此方向和此步长走一步到达下一点时,函数f(X)的值下降.基本步骤为1)选初始点 2)对于第k次迭代解,确定搜索方向并在此方向确定搜索步长,令 s.t. 3)若 符合给定的迭代终止原则,停止迭代, 否则转2).不同的算法在于方向和步长的选择,目的是使f下降更快.321 步长的选择:搜索方向 确定后,求步长实际上是一个一维优化问题: 称为一维搜索,有很多方法,如成功-失败法、黄金分割法(0.618法)、Fibonacci法、抛物线插值法和三次插值法等等.32.2 方向的选择 3 2.2.1最速下降法(梯度法):取 3 2.2.2 牛顿法:取 3 2.2.3 拟牛顿法:选满足 其中由BFGS迭代公式或DEP公式迭代得出 33 用MATLAB优化工具箱解无约束最优化问题 3 3.1 命令fminunc 1)x=fminunc(fun,x0) 2)x=fminunc(fun,x0,options) 其中1)、2)用于求解多元函数的无约束极小化问题,x0为迭代的初值,fun 为函数形式的M-文件(fun.m)的文件名, fminunc的求解方法由options(6)(方向)和options(7)(步长)指定(options(6)=0 拟牛顿法(BFGS公式) options(6)=1拟牛顿法(DFP公式) options(6)=2 最速下降法; options(7)=0 混合的二次和三次多项式插值options(7)=1 三次多项式插值)例1 求在(0,8)上的最大值和最小值. L21.mf=2*exp(-x)*sin(x);fplot(f,0,8);xmin=fminbnd(f,0,8);x=xmin;ymin=eval(f);f1=-2*exp(-x)*sin(x);xmax=fminbnd(f1,0,8);x=xmax;ymax=eval(f)例2 求 1) 编写函数M-文件FUN32.Mfunction f=fun32(x)f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);2)键入命令l22.mx0=-1,1;x=fminunc(fun32,x0);y=fun32(x)例3 Rosenbrock函数它的极小值点为=(1,1),极小值f()=0. 试用不同的算法求数值最优解,初始点选为=(-1.2,2).建立函数M-文件fun33.mfunction f=fun33(x)f=100*(x(2)-x(1)2)2+(1-x(1)2;用fminunc命令1)l232.m options(6)=1;options(7)=0;x,options=fminu(fun33,-1.2,2,options)y=options(8)n=options(10)2) options(6)=1;options(7)=1;x,options=fminu(fun33,-1.2,2,options)y=options(8)n=options(10)3) options(6)=2;options(7)=1;x,options=fminu(fun33,-1.2,2,options)y=options(8)n=options(10)4) options(6)=0;options(7)=1;x,options=fminu(fun33,-1.2,2,options)y=options(8)n=options(10)画图x,y=meshgrid(-2:0.1:2,-1:0.1:3);z=100*(y-x.2).2+(1-x).2;mesh(x,y,z)contour(x,y,z,20)drawnowhold onplot(-1.2,2,o)text(-1.2,2,start point)plot(1,1,o)text(1,1,solution)34 模型示例 例 3.4.1 选址问题:某市燃气公司计划要建一个煤气供应站, 该站向城市中有固定位置的m个用户供货. 对于选定的坐标系, 已知第i个用户的位置为, 如果只考虑直线距离, 如何确定煤气站的位置, 才能使总的运输距离最短? 设煤气站的位置为 则问题的数学模型为 4 非线性规划(0.1)(0.2)中至少有一个是非线性函数的最优化问题称为非线性规划问题, 其数学模型为 (4.1) s.t. (4.2)其中求目标函数的最大值或约束条件小于等于零的情形,可通过取其相反数, 而化为上述形式. 41 非线性规划问题的求解方法 411 罚函数法 基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题. 这种方法称为序列无约束最小化方法, 简称SUMT. 4111SUMT外点法 构造罚函数T(x,M)如下: (4.3)将求解非线性规划问题(4.1)(4.2)转化为求解无约束问题 (4.4)若对某个确定的M, (4.4)的解,则是(4.1)(4.2)的解 4112SUMT内点法 对具有不等式约束的非线性规划问题 (4.5)构造障碍函数 如下: 将(4.5)转化为求解 (4.6)其中若是(4.6)的解, 则是(4.5)的解.42 用MATLAB优化工具箱解约束最优化(非线性规划)问题 42.1求解二次规划问题 其中H为n阶对称半正定矩阵. MATLAB命令为1)x=qp(H,c,A,b);2)x=qp(H,c,A,b,vlb,vub);2) x=qp(H,c,A,b,vlb,vub,x0);3) x=qp(H,c,A,b,vlb,vub,x0)4) x=qp(H,c,A,b,vlb,vub,x0,N) 例4.1 求二次规划 写成标准形式 键入命令l41H=2,-2;-2,4;c=-2;-6;A=1,1;-1,2;b=2;2,vlb=0;0;vub= ;x=qp(H,c,A,b,vlb,vub)z=0.5*x*H*x+c*x422 求解非线性规划问题的MATLAB命令为 1)x=constr(fun,x0) 2)x=constr(fun,x0,options) 3)x=constr(fun,x0,options,vlb,vub)例4.2 求解建立函数M-文件FUN42function f,g=fun42(x)f=-x(1)-2*x(2)+1/2*x(1)2+1/2*x(2)2;g=2*x(1)+3*x(2)-6;x(1)+4*x(2)-5;键入命令x0=1;1;vlb=0;0;vub=;options=;x=constr(fun42,x0,options,vlb,vub)fun42(x)例4.3 求解 建立函数文件FUN43.Mfunction f,g=fun43(x)f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);g=x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;键入命令x0=-1;1;options(13)=1;x,options=constr(fun43,x0,options);options(8)43.建模示例 例43.1 资金使用问题设有400万元资金, 要求4年内使用完, 若在一年内使用资金x万元, 则可得效益万元(效益不能再使用),当年不用的资金可存入银行, 年利率为10%. 试制定出资金的使用计划, 以使4年效益之和为最大.设变量表示第i年所使用的资金数,则有 建立函数文件FUN44.Mfunction f,g=fun44(x)f=-(sqrt(x(1)+sqrt(x(2)+sqrt(x(3)+sqrt(x(4);g(1)=x(1)-400;g(2)=1.1*x(1)+x(2)-440;g(3)=1.21*x(1)+1.1*x(2)+x(3)-484;g(4)=1.331*x(1)+1.21*x(2)+1.1*x(3)+x(4)-532.4;键入命令x0=1;1;1;1;vlb=0;0;0;0;vub=;options=;x=constr(fun44,x0,options,vlb,vub)fun44(x)得到 5 动态规划动态规划是解决多阶段决策过程最优化问题的一种数学方法. 它在工程技术、管理、经济、工业生产、军事及现代控制工程等方面都有广泛的应用。构造动态规划模型的步骤为1）将实际问题恰当地划分为若干阶段;2）正确选择状态变量;3)确定决策变量及每段的允许决策集合；4）正确选择状态转移方程；5）正确列出指标函数并要求满足递推性。根据Bellman的最优化原理（对最优策略来说，无论过去状态和决策如何，由前面诸决策所形成的状态出发，相应的剩余决策序列构成最优子策略），利用逆推（初始状态给定）和顺推方法(终止状态给定)可求出最优决策和最优值。下面我们将就几个典型的多阶段决策过程最优化问题，利用动态规划方法给出他们的求解算法。5.1 投资问题:设有某种资源(或资金)M个单位(M为正整数), 欲分配用于N个生产项目. 已知第k个生产项目获得u(k)个单位(u(k)为非负整数, 称为决策变量)这种资源后可创利润L(u(k),k). L(u(k),K)是u(k)的不减函数.如何分配这些资源可使所获利润最大.把资源分配过程分为N个阶段. 第k阶段是向第k个生产项目分配资源. 用x(k+1)表示分配完1,2,k个生产项目后剩余的资源数量(称为状态变量,x(1)=M). 用v(x(k+1),k+1)表示把剩余的资源x(k+1)分配给第k+1,k+2,N个生产项目能获得的最大利润(称为最优值函数). 根据动态规划方法, 利用动态规划基本方程和状态转移方程 逆向递推可求得最优决策序列和总利润的最大值其中求解程序TZ.Mfunction u,I=tz(M,N,L)for i=1:M+1 V(i,N)=L(i,N); W(i,N)=i-1;endfor k=N-1:-1:2 for i=1:M+1 V(i,k)=0; W(i,k)=i-1; for j=1:i if V(i,k)L(j,k)+V(i+1-j,k+1) V(i,k)=L(j,k)+V(i+1-j,k+1); W(i,k)=j-1; end end endendV(M+1,1)=0;W(M+1,1)=M;for j=1:M+1 if V(M+1,1)L(j,1)+V(M+2-j,2) V(M+1,1)=L(j,1)+V(M+2-j,2); W(M+1,1)=j-1; end end I=V(M+1,1); u(1)=W(M+1,1); s=M-u(1); for i=2:N u(i)=W(s+1,i); s=s-u(i); end 应用实例:某公司新购置了某种设备6台, 欲分配给下属的4个企业. 已知各企业获得这种设备后年创利润如表, 问如何分配这些设备能使年创总利润最大, 最大利润为多少?甲乙丙丁000001423426455376764788657986671086键入命令M=6;N=4;L=0,0,0,0;4,2,3,4;6,4,5,5;7,6,7,6;7,8,8,6;7,9,8,6;7,10,8,6;u,I=tz(M,N,L) 6 多目标规划在日常生产、管理、经营等活动中, 经常会遇到多目标决策问题,如在一个生产过程中, 人们总是期望高产出、少用料、省工时等等, 在风险投资中, 希望收益大、风险小.多目标规划的一般模型为 (vp)其中 6.1有效解和弱有效解6.1.16.1.2 设如果对则称为(vp)的绝对最优解.6.1.3设如果不存在则称为(vp)的(弱)有效解或pareto最优解.6.2 求解多目标函数的评价函数方法 评价函数法是求对目标规划有效解的最基本方法. 它的基本思想是:借助于几何和应用中的直观背景, 构造所谓的评价函数, 从而将多目标规划问题转化为单目标优化问题. 然后利用单目标优化问题的求解方法求出最优解, 并把这种最优解当作多目标规划问题的最优解.所谓的评价函数是利用(vp)的目标函数f(x), 构造一个复合函数,然后在(vp)的约束集上极小化.的构造必须保证在一定条件下, 的最优解是(vp)的(弱)有效解.6.2.1理想点法 在(vp)中, 先求解p个单目标问题, 设其最优值为,称为一个理想值点, 一般很难达到它, 我们期望在某种度量下, 寻求距最近的f作为近似值. 一种直接的想法是构造评价函数 然后极小化 并将它的最优解作为(vp)在这种意义下的最优解.6.2.2线性加权和法 构造评价函数 求解=, 将它的最优解最为(vp)在该意义下的最优解.为权.一般相对重要的指标给予较大的权系数.6.2.3 极大极小法在决策时, 采取保守策略是稳妥的. 既在最坏的情况下, 寻求最好的结果. 按照这种想法, 可以构造评价函数 然后求解=, 并将它的最优解作为(vp)在这种意义下的最优解.还有很多其他形式的评价函数. 不一一列举.6.3 建模示例 用直径为1的圆木制作截面为矩形的梁, 为使重量最轻而强度最大, 问截面的长与宽应取何尺寸?设矩形截面的长与宽分别为, 这时梁的面积为 ,它决定重量, 而梁的强度取决于截面矩,故得到模型为 7 组合最优化问题 组合最优化(combinatorial optimization)是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等, 是运筹学中的一个经典且重要的分支, 所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通讯网络等诸多领域。该问题可用数学模型描述为 其中，f（x）为目标函数， g（x）为约束条件， x为决策变量，D表示有限个点组成的集合。一个组合优化问题可用三参数（D，F, f）表示, 其中D 表示决策变量的定义域, F 表示可行解区域,F中的任何一个元素称为该问题的可行解, f表示目标函数.满足的可行解称为该问题的最优解.组合最优化问题的特点是可行解集合为有限点集. 由直观可知, 只要将D中有限个点逐一判别是否满足g(x)的约束和比较目标值的大小, 该问题的最优解一定存在和可以得到.因此, 每一个组合最优化问题都可以通过枚举法求得最优解. 但枚举是以时间为代价的,有的枚举可以接受, 有的则不可能接受.6.1 计算复杂性:针对一