《优化方法.ppt》由会员分享，可在线阅读，更多相关《优化方法.ppt（61页珍藏版）》请在三一文库上搜索。
1、,最优化方法,数学建模系列讲座,最优化问题的解就是从所有可能的方案中选出最合理的, 以达到最优目标的方案-最优方案. 搜寻最优方案的方法就是最优化方法.,最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题. 如： 结构设计 资源分配 生产计划 运输方案,最优化:在一定条件下,寻求使目标最大（小）的决策,CUMCM赛题：约一半以上与最优化问题有关.如： 飞行管理问题(95A) 最优捕鱼策略(96A) 节水洗衣机(96B) 零件参数设计(97A) 投资的收益和风险(98A) 钢管订购和运输(2000B) 电力市场的堵塞管理(2004B),非线性规划： 96A 最优捕鱼策略 96B 节水
2、洗衣机 97A 零件参数设计 98A 投资收益与风险01B 公交车调度 混合整数规划: 99B 钻井布局 最短路，二次规划： 00B 管道订购 组合优化最短路： 97B 截断切割， 04A 奥运会临时超市(MS)网点设计 旅行商问题: 98B 灾情巡视 优化： 02A 车灯光源优化设计 02B 彩票中的数学,最优化理论是运筹学的基本内容,运筹学OR： Operational Research 管理科学MS: Management Science 决策科学DS: Decision Science,优化Optimization 规划Programming,动态规划,整数规划,不确定规划,非线性规划
3、,目标规划,组合优化,网络优化,线性规划,无约束优化,多目标规划,优化问题的一般形式,优化问题三要素：决策变量；目标函数；约束条件,可行解（满足约束）与可行域（可行解的集合） 最优解（取到最小或最大值的可行解）,约 束 条 件,目标函数,决策变量,最优化模型与方法的步骤,1.分析问题.发现、提出并形成问题,进行抽象、 简化、归纳和综合.明确问题的目标、各种约束、 问题的可控变量以及有关参数,搜集有关资料 2.建立模型.经过合理的假设,确定变量、参数和 目标与约束之间的关系,使用有效的模型来表示 3.求解.使用和创立各种数学方法和数学技术,对 模型求解(如最优解、次优解、近似解).借助于计 算机
4、软件进行求解复杂的模型,并进行各种数据分 析 4.解的检验和控制.检查求解步骤和程序无误后, 检验解是否反映现实问题并进行灵敏度分析,建模时需要注意的几个基本问题,1.尽量使用实数优化,减少整数约束和整数变量 2.尽量使用光滑优化,减少非光滑约束的个数 如:尽量少使用绝对值函数、符号函数、多个变量求最大(最 小)值、四舍五入、取整函数等 3.尽量使用线性模型,减少非线性约束和非线性 变量的个数 如: x/y5应改为x5y 4.合理设定变量上下界,尽可能给定变量初始值 5.模型中使用的参数数量级要适当 如:小于,无约束优化,最优解都是局部最优解,全局最优解只能从局部最优解的比较中得到.,多局部极
5、小,唯一极小 (全局极小),在迭代的每一步,确定一个搜索方向和一个步长,使沿此方向和此步长走一步到达下一点时,函数f(X)的值下降.,步长的选择:搜索方向,确定后,求步长实际上是一个一维,优化问题,成功-失败法 黄金分割法(0.618法) Fibonacci法 抛物线插值法 三次插值法,求解方法:搜索算法(数值迭代),方向的选择:最速下降法(梯度法),牛顿法,拟牛顿法,由BFGS迭代公式或DEP公式迭代得出,称为一维搜索,搜索过程,最优点 (1 1) 初始点 (-1 1),-1,1,4.00,-0.79,0.58,3.39,-0.53,0.23,2.60,-0.18,0.00,1.50,0.0
6、9,-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的二次函数，则用牛顿
7、法经过一次迭代就可达到最优点,如不是二次函数，则牛顿法不能一步达到极值点，但由于这种函数在极值点附近和二次函数很近似,因此牛顿法的收敛速度还是很快的.,牛顿法的收敛速度虽然较快，但要求Hessian矩阵要可逆,要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量.,3拟牛顿法,选址问题:某市燃气公司计划要建一个煤气供应站, 该站向城市中有固定位置的m个用户供货. 对于选定的坐标系, 已知第i个用户的位置为 如果只考虑直线距离, 如何确定煤气站的位置,才能使总的运输距离最短?,设煤气站的位置为,则问题的数学模型为,容积问题:对边长为3米的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问
8、如何剪法使水槽的容积最大？,产销量的最佳安排 某厂生产一种产品有甲、乙两个牌号，讨论在产销平衡的情况下如何确定各自的产量，使总利润最大. 所谓产销平衡指工厂的产量等于市场上的销量.,总利润为： z(x1,x2)=(p1-q1)x1+(p2-q2)x2,基本假设 1价格与销量成线性关系,2成本与产量成负指数关系,模型建立 总利润函数 z(x1,x2)=(p1-q1)x1+(p2-q2)x2,若根据大量的统计数据,求出系数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, 则问题转
9、化为无约束优化问题：求甲,乙两个牌号的产量x1，x2，使总利润z最大.,为简化模型,先忽略成本,并令a12=0,a21=0,问题转化为求: z1 = ( b1 - a11x1 ) x1 + ( b2 - a22x2 ) x2 的极值. 显然其解为x1 = b1/2a11 = 50, x2 = b2/2a22 = 70, 可以把它作为原问题的初始值.,约束优化,连续优化,离散规划,线性规划LP 目标和约束均为线性函数 非线性规划NLP 目标和约束均为非线性函数 二次规划QP 目标为二次函数,约束为线性函数,整数规划IP 决策变量(全部或部分)为整数 整数线性规划ILP 整数非线性规划INLP 纯
10、整数规PIP 混合整数规划MIP 一般整数规划 0-1整数规划,线性规划 目标函数和约束条件都是线性函数,线性规划的其他形式可通过形式变换和添加松弛变量而化为标准型. 常用求解方法:单纯形法,线性规划模型的标准型:,其中,运输问题: 设有m个生产地点 可供应物资,其供应量(产量)分别为 .有n个销售地点 ,其需求量分别为 ,假设供需平衡,即,.,用 表示由 运 输单位物资的运价,如何 确定一种调运方案才能 使总运输费用 最小. 用 表示由调运物资的 数量,则运输问题的数学 模型为:,任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工
11、件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？,设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：,人员问题:某厂每日8小时的产量不低于1800件。为了进行质量控制，计划聘请两种不同水平的检验员。一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15小时/件，正确率95%，计时工资3元/小时。检验员每错检一次，工厂要损失2元。为
12、使总检验费用最省，该工厂应聘一级、二级检验员各几名？,设需要一级和二级检验员的人数分别为x1、x2人, 则应付检验员的工资为：,因检验员错检而造成的损失为：,故目标函数为：,约束条件为：,线性规划模型：,整数规划 决策变量只能取整数的数学规划问题,模型的一般形式为,求解方法:割平面法用于求解纯整数规划 分枝定界法用于求解混合整数规划. 穷举法用于规模不大的整数规划.,背包问题: 有一只背包(泛指仓库、船舱、卫星仓等)，最大装载重量为w单位。现有k种物品，每种的数量无限。第i种物品每件重量为 ,价值 .每种物品各取多少装入背包，使其中的物品总价值最高。 设取第i种物品 件,则,非线性规划 目标函
13、数与约束条件中至少有一个是非线性函数,SUTM外点法,SUTM内点法（障碍罚函数法）,罚函数法,近似规划法,常用方法,基本思想：将非线性规划问题中的目标函数 和约束条件 近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似线性规划问题，再用单纯形法求解之，把其符合原始条件的最优解作为原问题的近似解每得到一个近似解后，都从这点出发，重复以上步骤 这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序列，经验表明，这样的序列往往收敛于非线性规划问题的解。,近似规划法,SUTM外点法,将求解将非线性规划问题转化为无约束问题,构造罚函数,罚函数法基本思想是通过构造罚函数把约束问题转
14、化为一系列无约束最优化问题. 称为序列无约束最小化方法, 简称SUMT.,其中T(x,M)称为罚函数，M称为罚因子，带M的项称为罚项,这里的罚函数只对不满足约束条件的点实行惩罚： 当 时,满足各 ,故罚项=0,不受惩罚. 当 时,必有 的约束条件,故罚项0, 要受惩罚,SUTM内点法(障碍函数法),设集合 是可行域中所有 严格内点的集合.构造障碍函数,考虑问题,将问题转化为无约束问题 其中 则 是问题的解.,其中称 或 为障碍项, 为障碍因子,资金使用问题:设有400万元资金, 要求4年内使用完, 若在一年内使用资金x万元, 则可得效益 万元(效益不能再使用),当年不用的资金可存入银行, 年利
15、率为10%. 试制定出资金的使用计划, 以使4年效益之和为最大. 设变量 表示第i年所使用的资金数,则有,其中H为n阶对称半正定矩阵.,二次规划问题 标准形为,动态规划 解决多阶段决策过程最优化的数学方法 特点: 具有明确的阶段性,各阶段次序递推且相互依赖和影响. 各个阶段所作的决策形成确定整个系统的决策序列,称这样的决策序列为系统的一个策略.多阶段决策过程就是在所有允许的策略集合中确定一个达到最优指标的最优策略.,多阶段决策过程是一种多维优化问题的方法. 动态规划是基于最优性原理,将一个复杂的多元问题分解成为若干个相互依赖,相互联系的易于求解优化的少阶段低维问题.,构造动态规划模型的步骤 1
16、）将实际问题恰当地划分为若干阶段; 2）正确选择状态变量 ; 3）确定决策变量 及每段的允许决策集合 4）正确选择状态转移方程 ； 5）正确列出指标函数 并要求满足递推性。 根据Bellman的最优化原理，利用逆推（初始状态给定）和顺推方法(终止状态给定)，可求出最优决策和最优值。,把资源分配过程分为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个生产项目能获得的最大利润(称为最优值函数).,投资问题 设有某种资源(
17、或资金)M个单位(M为正整数), 欲分配用于N个生产项目. 已知第k个生产项目获得u(k)个单位(u(k)为非负整数, 称为决策变量)这种资源后可创利润L(u(k),k). L(u(k),K)是u(k)的不减函数.如何分配这些资源可使所获利润 最大.,根据动态规划方法, 利用动态规划基本方程,和状态转移方程,逆向递推可求得最优决策序列,和总利润的最大值,其中,多目标规划 目标函数由两个或两个以上函数构成,其中,为(vp)的绝对最优解.,为(vp)的(弱)有效解或pareto最优解.,求解求解多目标函数的评价函数方法 求多目标规划有效解的最基本方法. 基本思想:借助于几何和应用中的直观背景, 构
18、造所谓的评价函数, 从而将多目标规划问题转化为单目标优化问题. 然后利用单目标优化问题的求解方法求出最优解, 并把这种最优解当作多目标规划问题的最优解. 所谓的评价函数是利用(vp)的目标函数f(x), 构造一个复合函数 ,然后在(vp)的约束集上极小化 .的构造必须保证在一定条件下, 的最优解是(vp)的(弱)有效解.,理想点法,线性加权和法,极大极小法,理想点法,先求解p个单目标问题 .设其最优值为 ,称 为一个理想值点, 一般很难达到, 寻求距 最近的f 作为近似值. 构造评价函数,线性加权和法,构造评价函数,极大极小法,在决策时, 采取保守策略是稳妥的.即在最坏的情况下, 寻求最好的结
19、果.构造评价函数,材料问题用直径为1的圆木制作截面为矩形的梁, 为使重量最轻而强度最大, 问截面的长与宽应取何尺寸?,设矩形截面的长与宽分别 为 ,这时梁的面积为 ,它决定重量.而梁的 强度取决于截面矩 故得到模型为,组合最优化 可行解集合为有限点集,求解方法: 枚举法 有限个点,逐一判别.以时间为代价 启发式算法 不一定能保证所得解的可行性和最优性. 现代优化算法 包括禁忌搜索,模拟退火,遗传算法,人 工神经网络.,D表示由有限点 组成的集合,背包问题:设有一个容积为b的背包,n个体积分别为 ,价值分别为 的物品,如何以最大的价值装包?,设,则建模为,旅行商问题:一个商人欲到n个城市推销商品
20、, 每两个城市i和j之间的距离为 ,如何选择一条道路使得商人每个城市走一遍后回到起点且所走路径最短.,决策变量 和 分别表示行走的路线不包含和包含从城市i到城市j路径, 则数学模型为,投资的收益和风险,任何人都希望最大化自己的效用而非最小，在保持生活水平不变的条件下最小化自己的支出而非最大，这是经济学的先验命题，从重商主义、重农主义、古典经济学、新古典经济学到当代主流经济学(新古典主义和新凯恩斯主义)，无不接受、继承和发展这一命题，效用最大化,支出最小化问题得到了越来越深入的研究。 偏好的无满足性决定了消费者根本不可能在整个消费集合中选择出最为满意的消费方案，因此，无限制的效用最大化是无法实现
21、的。也就是说，消费者的欲望是无止境的，永远没有一个满足的时候，当消费者面临一种消费方案时，常常会作出这样的考虑：只要效用水平不降低，支出越少就越好。正常人都会有想占便宜的正常心理，谁不想以较少的效用换得较多的效用呢？ 任何人都处在一定的客观环境中，客观环境必然对人们的选择行为带来一定的限制。人们受到的种种限制影响了人们的选择和享受，但这些限制却使得效用最大化问题有了解决途径服从约束条件的效用最大化。理性消费者正是在服从种种条件限制的情况下，选择自己最满意的方案。在保证不降低生活水平的前提下谋求消费支出达到最少。,二、问题的分析与假设 这是一个多目标优化问题，目标有二，净收益最大和整体风险最小.
22、 一般来说，这两个目标是矛盾的，收益大，风险必然大，所以不可能给出这两个目标同时达到最优的所谓最优决策，我们追求的只能是，在一定的风险下收益最大的决策，或在一定收益下风险最小的决策，或收益和风险按一定比例组合最优的决策。 这就是说应该给出的不是一个解，而是一组Pareto解，比如在一系列风险值下收益最大的决策，冒险者会从中选择高风险下收益最大的决策，保守者会从低风险下的决策中选择。,三、模型的建立与分析,1.总体风险用所投资的Si中最大的一个风险来衡量,即max qixi | i=1，2,n,对 投资 时,交易费,净收益,风险,所需资金,用 表示投资方案,则投资方案的,总收益,整体风险,所需资
23、金,将多目标规划问题化为单目标规划问题,双目标优化模型,a. 在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限a，使最大的一个风险 ，可找到相应的投资方案。这样把多目标规划变成一个目标的线性规划。,模型M1:确定风险水平 ,优化收益.记 .求解,模型M2:确定盈利水平 ,极小化风险.记 .求解,模型M3:确定投资者对风险-收益的相对偏好参数 ,求解,b若投资者希望总盈利至少达到水平k以上，在风险最小的情况下寻找相应的投资组合。,c投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资组合。因此对风险、收益赋予权重s（0s1)，s称为投资偏好系数.,4. 模型简化：,交
24、易费的简化: 由于交易费 中固定费用 的存在, 使得模型中的目标函数或约束条件是非光滑的, 求解非常困难. 考虑到总资金M相当大, 而交易费中的 又相当小, 故可使对每个 的投资 都超过 ,于是交易费可简化为线性函数,从而资金约束简化为 进而在具体计算时可设M=1, 这时,将 视作投资 的比例.,M1化为如下的线性规划LP1:,极小极大规划M2引进人工 变量 化为如下的线 性规划LP2:,M3化为如下的线性规划LP3:,四、模型1的求解,由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从a=0开始，以步长a=0.001进行循环搜索，编制程序如下：,计算结果：
25、,五、 结果分析,4.在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合大约是a*=0.6%，Q*=20% ，所对应投资方案为: 风险度 收益 x0 x1 x2 x3 x4 0.0060 0.2019 0 0.2400 0.4000 0.1091 0.2212,3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。,2.当投资越分散时，投资者承担的风险越小，这与题意一致。即: 冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。,1.风险大，收益也大。,