最优化计算方法

最优化计算方法数学建模系列讲座最优化问题的解就是从所有可能的方案中选出最合理的,以达到最优目标的方案--最优方案.搜寻最优方案的方法就是最优化方法.

最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题.如：结构设计资源分配生产计划运输方案最优化:在一定条件下,寻求使目标最大（小）的决策CUMCM赛题：约一半以上与最优化问题有关.2012年B题太阳能小屋的设计，2011年B题交巡警服务平台的设置与调度，2010年A题储油罐的变位识别与罐容表标定，2009年B题眼科病床的合理安排等非线性规划：96A最优捕鱼策略

96B节水洗衣机97A零件参数设计

98A投资收益与风险01B公交车调度混合整数规划:99B钻井布局最短路，二次规划：00B管道订购组合优化最短路：97B截断切割，

04A奥运会临时超市(MS)网点设计旅行商问题:98B灾情巡视优化：02A车灯光源优化设计

02B彩票中的数学最优化理论是运筹学的基本内容运筹学OR：OperationalResearch管理科学MS:ManagementScience决策科学DS:DecisionScience优化Optimization规划Programming动态规划整数规划不确定规划非线性规划目标规划组合优化网络优化线性规划无约束优化多目标规划智能优化优化问题的一般形式优化问题三要素：决策变量；目标函数；约束条件

可行解（满足约束）与可行域（可行解的集合）最优解（取到最小或最大值的可行解）约束条件目标函数决策变量最优化模型与方法的步骤1.分析问题.发现、提出并形成问题,进行抽象、简化、归纳和综合.明确问题的目标、各种约束、问题的可控变量以及有关参数,搜集有关资料2.建立模型.经过合理的假设,确定变量、参数和目标与约束之间的关系,使用有效的模型来表示3.求解.使用和创立各种数学方法和数学技术,对模型求解(如最优解、次优解、近似解).借助于计算机软件进行求解复杂的模型,并进行各种数据分析4.解的检验和控制.检查求解步骤和程序无误后,检验解是否反映现实问题并进行灵敏度分析

建模时需要注意的几个基本问题1.尽量使用实数优化,减少整数约束和整数变量2.尽量使用光滑优化,减少非光滑约束的个数

如:尽量少使用绝对值函数、符号函数、多个变量求最大(最小)值、四舍五入、取整函数等3.尽量使用线性模型,减少非线性约束和非线性变量的个数

如:x/y<5应改为x<5y4.合理设定变量上下界,尽可能给定变量初始值5.模型中使用的参数数量级要适当

如:小于

无约束优化最优解都是局部最优解,全局最优解只能从局部最优解的比较中得到.

多局部极小

唯一极小(全局极小)在迭代的每一步,确定一个搜索方向和一个步长,使沿此方向和此步长走一步到达下一点时,函数f(X)的值下降.步长的选择:搜索方向

确定后,求步长实际上是一个一维优化问题

成功-失败法黄金分割法(0.618法)Fibonacci法抛物线插值法三次插值法求解方法:搜索算法(数值迭代)

方向的选择:最速下降法(梯度法)牛顿法拟牛顿法由BFGS迭代公式或DEP公式迭代得出称为一维搜索搜索过程最优点(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.900.0030.990.991E-40.9990.9981E-50.99970.99981E-8

最速下降法是一种最基本的算法，它在最优化方法中占有重要地位.最速下降法的优点是工作量小，存储变量较少,初始点要求不高；缺点是收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值点时，宜选用别种收敛快的算法.

1．最速下降法（共轭梯度法）算法步骤：无约束优化问题的基本算法2．牛顿法算法步骤：

如果f是对称正定矩阵A的二次函数，则用牛顿法经过一次迭代就可达到最优点,如不是二次函数，则牛顿法不能一步达到极值点，但由于这种函数在极值点附近和二次函数很近似,因此牛顿法的收敛速度还是很快的.

牛顿法的收敛速度虽然较快，但要求Hessian矩阵要可逆,要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量.3．拟牛顿法选址问题:某市燃气公司计划要建一个煤气供应站,该站向城市中有固定位置的m个用户供货.对于选定的坐标系,已知第i个用户的位置为如果只考虑直线距离,如何确定煤气站的位置,才能使总的运输距离最短?设煤气站的位置为

,则问题的数学模型为容积问题:对边长为3米的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？产销量的最佳安排

某厂生产一种产品有甲、乙两个牌号，讨论在产销平衡的情况下如何确定各自的产量，使总利润最大.所谓产销平衡指工厂的产量等于市场上的销量.总利润为：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,则问题转化为无约束优化问题：求甲,乙两个牌号的产量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

纯整数规PIP

混合整数规划MIP

一般整数规划0--1整数规划线性规划目标函数和约束条件都是线性函数线性规划的其他形式可通过形式变换和添加松弛变量而化为标准型.常用求解方法:单纯形法线性规划模型的标准型:其中运输问题:

设有m个生产地点可供应物资,其供应量(产量)分别为.有n个销售地点,其需求量分别为,假设供需平衡,即

.用表示由运

输单位物资的运价,如何

确定一种调运方案才能

使总运输费用最小.

用表示由调运物资的

数量,则运输问题的数学

模型为:任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：人员问题:某厂每日8小时的产量不低于1800件。为了进行质量控制，计划聘请两种不同水平的检验员。一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15小时/件，正确率95%，计时工资3元/小时。检验员每错检一次，工厂要损失2元。为使总检验费用最省，该工厂应聘一级、二级检验员各几名？

设需要一级和二级检验员的人数分别为x1、x2人,则应付检验员的工资为：因检验员错检而造成的损失为：故目标函数为：约束条件为：线性规划模型：整数规划决策变量只能取整数的数学规划问题模型的一般形式为

求解方法:割平面法—用于求解纯整数规划分枝定界法—用于求解混合整数规划.

穷举法—用于规模不大的整数规划.背包问题:

有一只背包(泛指仓库、船舱、卫星仓等)，最大装载重量为w单位。现有k种物品，每种的数量无限。第i种物品每件重量为,价值.每种物品各取多少装入背包，使其中的物品总价值最高。设取第i种物品件,则非线性规划目标函数与约束条件中至少有一个是非线性函数SUTM外点法SUTM内点法（障碍罚函数法）罚函数法近似规划法常用方法基本思想：将非线性规划问题中的目标函数和约束条件

近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似线性规划问题，再用单纯形法求解之，把其符合原始条件的最优解作为原问题的近似解．每得到一个近似解后，都从这点出发，重复以上步骤．这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序列，经验表明，这样的序列往往收敛于非线性规划问题的解。近似规划法

SUTM外点法将求解将非线性规划问题转化为无约束问题

构造罚函数

罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题.称为序列无约束最小化方法,简称SUMT.其中T(x,M)称为罚函数，M称为罚因子，带M的项称为罚项这里的罚函数只对不满足约束条件的点实行惩罚：当时,满足各,故罚项=0,不受惩罚.当时,必有的约束条件,故罚项>0,要受惩罚．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路径,则数学模型为投资的收益和风险任何人都希望最大化自己的效用而非最小，在保持生活水平不变的条件下最小化自己的支出而非最大，这是经济学的先验命题，从重商主义、重农主义、古典经济学、新古典经济学到当代主流经济学(新古典主义和新凯恩斯主义)，无不接受、继承和发展这一命题，效用最大化,支出最小化问题得到了越来越深入的研究。偏好的无满足性决定了消费者根本不可能在整个消费集合中选择出最为满意的消费方案，因此，无限制的效用最大化是无法实现的。也就是说，消费者的欲望是无止境的，永远没有一个满足的时候，当消费者面临一种消费方案时，常常会作出这样的考虑：只要效用水平不降低，支出越少就越好。正常人都会有想占便宜的正常心理，谁不想以较少的效用换得较多的效用呢？任何人都处在一定的客观环境中，客观环境必然对人们的选择行为带来一定的限制。人们受到的种种限制影响了人们的选择和享受，但这些限制却使得效用最大化问题有了解决途径——服从约束条件的效用最大化。理性消费者正是在服从种种条件限制的情况下，选择自己最满意的方案。在保证不降低生活水平的前提下谋求消费支出达到最少。二、问题的分析与假设这是一个多目标优化问题，目标有二，净收益最大和整体风险最小.一般来说，这两个目标是矛盾的，收益大，风险必然大，所以不可能给出这两个目标同时达到最优的所谓最优决策，我们追求的只能是，在一定的风险下收益最大的决策，或在一定收益下风险最小的决策，或收益和风险按一定比例组合最优的决策。这就是说应该给出的不是一个解，而是一组Pareto解，比如在一系列风险值下收益最大的决策，冒险者会从中选择高风险下收益最大的决策，保守者会从低风险下的决策中选择。三、模型的建立与分析1.总体风险用所投资的Si中最大的一个风险来衡量,即max{qixi|i=1，2,…n}对投资时交易费净收益风险所需资金

用表示投资方案,则投资方案的

总收益整体风险所需资金将多目标规划问题化为单目标规划问题双目标优化模型a.在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限a，使最大的一个风险，可找到相应的投资方案。这样把多目标规划变成一个目标的线性规划。模型M1:确定风险水平,优化收益.记.求解

模型M2:确定盈利水平,极小化风险.记.求解模型M3:确定投资者对风险-收益的相对偏好参数,求解b．若投资者希望总盈利至少达到水平k以上，在风险最小的情况下寻找相应的投资组合。c．投资者在权衡资产风险和预期收益两方面时，希望选择一个令自