最优化计算方法数学建模系列讲座课件

最优化计算方法数学建模系列讲座最优化问题的解就是从所有可能的方案中选出最合理的,以达到最优目标的方案-最优方案.搜寻最优方案的方法就是最优化方法.最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题.如：结构设计 资源分配 生产计划 运输方案最优化:在一定条件下,寻求使目标最大（小）的决策CUMCM赛题：约一半以上与最优化问题有关.2012年B题 太阳能小屋的设计，2011年B题 交巡警服务平台的设置与调度，2010年A题 储油罐的变位识别与罐容表标定，2009年B题 眼科病床的合理安排等非非线性性规划：划：96A 最最优捕捕鱼策略策略 96B 节水洗衣机水洗衣机 97A 零件参数零件参数设计 98A 投投资收益与收益与风险01B 公交公交车调度度混合整数混合整数规划划:99B 钻井布局井布局最短路，二次最短路，二次规划：划：00B 管道管道订购组合合优化最短路：化最短路：97B 截断切割截断切割，04A 奥运会奥运会临时超市超市(MS)网点网点设计旅行商旅行商问题:98B 灾情巡灾情巡视优化：化：02A 车灯光源灯光源优化化设计 02B 彩票中的数学彩票中的数学最优化理论是运筹学的基本内容运筹学OR：Operational Research管理科学MS:Management Science决策科学DS:Decision Science优化Optimization 规划Programming动态规划整数规划不确定规划非线性规划目标规划组合优化网络优化线性规划无约束优化多目标规划智能优化优化问题的一般形式优化问题三要素：决策变量；目标函数；约束条件 可行解（满足约束）与可行域（可行解的集合）最优解（取到最小或最大值的可行解）约束条件目标函数决策变量最优化模型与方法的步骤1.分析问题.发现、提出并形成问题,进行抽象、简化、归纳和综合.明确问题的目标、各种约束、问题的可控变量以及有关参数,搜集有关资料2.建立模型.经过合理的假设,确定变量、参数和目标与约束之间的关系,使用有效的模型来表示3.求解.使用和创立各种数学方法和数学技术,对模型求解(如最优解、次优解、近似解).借助于计算机软件进行求解复杂的模型,并进行各种数据分析4.解的检验和控制.检查求解步骤和程序无误后,检验解是否反映现实问题并进行灵敏度分析 建模时需要注意的几个基本问题1.尽量使用实数优化,减少整数约束和整数变量2.尽量使用光滑优化,减少非光滑约束的个数 如:尽量少使用绝对值函数、符号函数、多个变量求最大(最 小)值、四舍五入、取整函数等3.尽量使用线性模型,减少非线性约束和非线性 变量的个数 如:x/y5应改为x0,要受惩罚SUTM内点法内点法(障碍函数法障碍函数法)设集合 是可行域中所有严格内点的集合.构造障碍函数 考虑问题将问题转化为无约束问题其中 则 是问题的解.其中称 或 为障碍项,为障碍因子资金使用问题:设有400万元资金,要求4年内使用完,若在一年内使用资金x万元,则可得效益 万元(效益不能再使用),当年不用的资金可存入银行,年利率为10%.试制定出资金的使用计划,以使4年效益之和为最大.设变量 表示第i年所使用的资金数,则有其中H为n阶对称半正定矩阵.二次规划问题标准形为动态规划解决多阶段决策过程最优化的数学方法特点:具有明确的阶段性,各阶段次序递推且相互依赖和影响.各个阶段所作的决策形成确定整个系统的决策序列,称这样的决策序列为系统的一个策略.多阶段决策过程就是在所有允许的策略集合中确定一个达到最优指标的最优策略.多阶段决策过程是一种多维优化问题的方法.动态规划是基于最优性原理,将一个复杂的多元问题分解成为若干个相互依赖,相互联系的易于求解优化的少阶段低维问题.构造动态规划模型的步骤1）将实际问题恰当地划分为若干阶段;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个生产项目能获得的最大利润(称为最优值函数).投资问题 设有某种资源(或资金)M个单位(M为正整数),欲分配用于N个生产项目.已知第k个生产项目获得u(k)个单位(u(k)为非负整数,称为决策变量)这种资源后可创利润L(u(k),k).L(u(k),K)是u(k)的不减函数.如何分配这些资源可使所获利润 最大.根据动态规划方法,利用动态规划基本方程和状态转移方程 逆向递推可求得最优决策序列和总利润的最大值其中多目标规划多目标规划目标函数由两个或两个以上函数构成其中 为(vp)的绝对最优解绝对最优解.为(vp)的(弱弱)有效解有效解或pareto最优解.求解求解多目标函数的评价函数方法求多目标规划有效解的最基本方法.基本思想:借助于几何和应用中的直观背景,构造所谓的评价函数,从而将多目标规划问题转化为单目标优化问题.然后利用单目标优化问题的求解方法求出最优解,并把这种最优解当作多目标规划问题的最优解.所谓的评价函数是利用(vp)的目标函数f(x),构造一个复合函数 ,然后在(vp)的约束集上极小化 .的构造必须保证在一定条件下,的最优解是(vp)的(弱)有效解.理想点法线性加权和法极大极小法理想点法 先求解p个单目标问题 .设其最优值为 ,称 为一个理想值点,一般很难达到,寻求距 最近的f 作为近似值.构造评价函数线性加权和法 构造评价函数极大极小法在决策时,采取保守策略是稳妥的.即在最坏的情况下,寻求最好的结果.构造评价函数材料问题用直径为1的圆木制作截面为矩形的梁,为使重量最轻而强度最大,问截面的长与宽应取何尺寸?设矩形截面的长与宽分别为 ,这时梁的面积为 ,它决定重量.而梁的强度取决于截面矩故得到模型为组合最优化组合最优化可行解集合为有限点集求解方法:枚举法 有限个点,逐一判别.以时间为代价 启发式算法 不一定能保证所得解的可行性和最优性.现代优化算法 包括禁忌搜索,模拟退火,遗传算法,人 工神经网络.D表示由有限点组成的集合背包问题:设有一个容积为b的背包,n个体积分别为 ,价值分别为 的物品,如何以最大的价值装包?设则建模为旅行商问题:一个商人欲到n个城市推销商品,每两个城市i和j之间的距离为 ,如何选择一条道路使得商人每个城市走一遍后回到起点且所走路径最短.决策变量和 分别表示行走的路线不包含和包含从城市i到城市j路径,则数学模型为投资的收益和风险任何人都希望最大化自己的效用而非最小，在保持生活水平不变的条件下最小化自己的支出而非最大，这是经济学的先验命题，从重商主义、重农主义、古典经济学、新古典经济学到当代主流经济学(新古典主义和新凯恩斯主义)，无不接受、继承和发展这一命题，效用最大化,支出最小化问题得到了越来越深入的研究。偏好的无满足性决定了消费者根本不可能在整个消费集合中选择出最为满意的消费方案，因此，无限制的效用最大化是无法实现的。也就是说，消费者的欲望是无止境的，永远没有一个满足的时候，当消费者面临一种消费方案时，常常会作出这样的考虑：只要效用水平不降低，支出越少就越好。正常人都会有想占便宜的正常心理，谁不想以较少的效用换得较多的效用呢？任何人都处在一定的客观环境中，客观环境必然对人们的选择行为带来一定的限制。人们受到的种种限制影响了人们的选择和享受，但这些限制却使得效用最大化问题有了解决途径服从约束条件的效用最大化。理性消费者正是在服从种种条件限制的情况下，选择自己最满意的方案。在保证不降低生活水平的前提下谋求消费支出达到最少。二、问题的分析与假设二、问题的分析与假设这是一个多目标优化问题，目标有二，净收益最大和整体风这是一个多目标优化问题，目标有二，净收益最大和整体风险最小险最小.一般来说，这两个目标是矛盾的，收益大，风险必然大，所一般来说，这两个目标是矛盾的，收益大，风险必然大，所以不可能给出这两个目标同时达到最优的所谓最优决策，我以不可能给出这两个目标同时达到最优的所谓最优决策，我们追求的只能是，在一定的风险下收益最大的决策，或在一们追求的只能是，在一定的风险下收益最大的决策，或在一定收益下风险最小的决策，或收益和风险按一定比例组合最定收益下风险最小的决策，或收益和风险按一定比例组合最优的决策。优的决策。这就是说应该给出的不是一个解，而是一组这就是说应该给出的不是一个解，而是一组ParetoPareto解，比如解，比如在一系列风险值下收益最大的决策，冒险者会从中选择高风在一系列风险值下收益最大的决策，冒险者会从中选择高风险下收益最大的决策，保守者会从低风险下的决策中选择。险下收益最大的决策，保守者会从低风险下的决策中选择。三、模型的建立与分析三、模型的建立与分析1.总体风险用所投资的Si中最大的一个风险来衡量,即max qixi|i=1，2,n对 投资 时交易费净收益风险所需资金 用 表示投资方案,则投资方案的 总收益整体风险所需资金将多目标规划问题化为单目标规划问题双目标优化模型a.在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限a，使最大的一个风险 ，可找到相应的投资方案。这样把多目标规划变成一个目标的线性规划。模型M1:确定风险水平 ,优化收益.记 .求解 模型M2:确定盈利水平 ,极小化风险.记 .求解模型M3:确定投资者对风险-收益的相对偏好参数 ,求解b若投资者希望总盈利至少达到水平k以上，在风险最小的情况下寻找相应的投资组合。c投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资组合。因此对风险、收益赋予权重s（0s1)，s称为投资偏好系数.4.模型简化：交易费的简化:由于交易费 中固定费用 的存在,使得模型中的目标函数或约束条件是非光滑的,求解非常困难.考虑到总资金M相当大,而交易费中的 又相当小,故可使对每个 的投资 都超过 ,于是交易费可简化为线性函数 从而资金约束简化为 进而在具体计算时可设M=1,这时 将 视作投资 的比例.M1化为如下的线性规划LP1:极小极大规划M2引进人工变量 化为如下的线性规划LP2:M3化为如下的线性规划LP3:四、模型四、模型1 1的求解的求解 由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从a=0开始，以步长a=0.001进行循环搜索，编制程序如下：计算结果：计算结果：五、五、结果分析结果分析4 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.3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。2 2.当投资越分散时，投资者承担的风险越小，这与题意一致。即:冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。1.1.风险大，收益也大。