资源描述：
《最新最优化计算方法幻灯片.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、最优化计算方法最优化问题的解就是从所有可能的方案中选出最合理的,以达到最优目标的方案--最优方案.搜寻最优方案的方法就是最优化方法.最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题.如：结构设计资源分配生产计划运输方案最优化:在一定条件下,寻求使目标最大（小）的决策CUMCM赛题：约一半以上与最优化问题有关.2012年B题太阳能小屋的设计，2011年B题交巡警服务平台的设置与调度，2010年A题储油罐的变位识别与罐容表标定，2009年B题眼科病床的合理安排等非线性规划：96A最优捕鱼策略96B
2、节水洗衣机97A零件参数设计98A投资收益与风险01B公交车调度混合整数规划:99B钻井布局最短路，二次规划：00B管道订购组合优化最短路：97B截断切割，04A奥运会临时超市(MS)网点设计旅行商问题:98B灾情巡视优化：02A车灯光源优化设计02B彩票中的数学建模时需要注意的几个基本问题1.尽量使用实数优化,减少整数约束和整数变量2.尽量使用光滑优化,减少非光滑约束的个数如:尽量少使用绝对值函数、符号函数、多个变量求最大(最小)值、四舍五入、取整函数等3.尽量使用线性模型,减少非线性约束和非线性变量的个
3、数如:x/y<5应改为x<5y4.合理设定变量上下界,尽可能给定变量初始值5.模型中使用的参数数量级要适当如:小于无约束优化最优解都是局部最优解,全局最优解只能从局部最优解的比较中得到.多局部极小唯一极小(全局极小)在迭代的每一步,确定一个搜索方向和一个步长,使沿此方向和此步长走一步到达下一点时,函数f(X)的值下降.步长的选择:搜索方向确定后,求步长实际上是一个一维优化问题成功-失败法黄金分割法(0.618法)Fibonacci法抛物线插值法三次插值法求解方法:搜索算法(数值迭代)方向的选择:最速下降法(
4、梯度法)牛顿法拟牛顿法由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最速下降法是一种最基本的算法，它在最优化方法中占有重要地位.最速下降法的优点是工作量小，存储变量较少,
5、初始点要求不高；缺点是收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值点时，宜选用别种收敛快的算法.1．最速下降法（共轭梯度法）算法步骤：无约束优化问题的基本算法2．牛顿法算法步骤：如果f是对称正定矩阵A的二次函数，则用牛顿法经过一次迭代就可达到最优点,如不是二次函数，则牛顿法不能一步达到极值点，但由于这种函数在极值点附近和二次函数很近似,因此牛顿法的收敛速度还是很快的.牛顿法的收敛速度虽然较快，但要求Hessian矩阵要可逆,要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量.3．拟
6、牛顿法选址问题:某市燃气公司计划要建一个煤气供应站,该站向城市中有固定位置的m个用户供货.对于选定的坐标系,已知第i个用户的位置为如果只考虑直线距离,如何确定煤气站的位置,才能使总的运输距离最短?设煤气站的位置为,则问题的数学模型为容积问题:对边长为3米的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？产销量的最佳安排某厂生产一种产品有甲、乙两个牌号，讨论在产销平衡的情况下如何确定各自的产量，使总利润最大.所谓产销平衡指工厂的产量等于市场上的销量.总利润为：z(x1,x2
7、)=(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,问题转化为
8、求:z1=(b1-a11x1)x1+(b2-a22x2)x2的极值.显然其解为x1=b1/2a11=50,x2=b2/2a22=70,可以把它作为原问题的初始值.约束优化连续优化离散规划线性规划LP目标和约束均为线性函数非线性规划NLP目标和约束均为非线性函数二次规划QP目标为二次函数,约束为线性函数整数规划IP决策变量(全部或部分)为整数整数线性规划ILP整数非线性规划INLP纯整数规PIP混合整数规划MIP一
