优化方法.ppt
《优化方法.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种物品 件,则,非线性规划 目标函
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 优化 方法
链接地址:https://www.31doc.com/p-2654853.html