数学建模-优化问题.ppt

约束优化constrainedoptimization的简单分类 数学规划mathematicalprogramming或连续优化continuousoptmization 线性规划 LP 目标和约束均为线性函数Linearprogramming非线性规划 NLP 目标或约束中存在非线性函数Nonlinearprogramming二次规划 QP 目标为二次函数 约束为线性Quadraticprogramming 一般优化问题概述 整数规划 IP 决策变量 全部或部分 为整数Integerprogramming整数线性规划 ILP 整数非线性规划 INLP 纯整数规划 PIP 混合整数规划 MIP Pure mixed Integerprogramming一般整数规划 0 1 整数 规划Zero oneprogramming 离散优化discreteoptimization或组合优化combinatorialoptimization 一般优化问题概述 无约束最优化问题 求解无约束最优化问题的的基本思想 无约束最优化问题的基本算法 返回 标准形式 求解无约束最优化问题的基本思想 求解的基本思想 以二元函数为例 5 3 1 连续可微 多局部极小 唯一极小 全局极小 搜索过程 最优点 11 初始点 11 1 1 4 00 0 79 0 58 3 39 0 53 0 23 2 60 0 18 0 00 1 50 0 09 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的二次函数 则用牛顿法经过一次迭代就可达到最优点 如不是二次函数 则牛顿法不能一步达到极值点 但由于这种函数在极值点附近和二次函数很近似 因此牛顿法的收敛速度还是很快的 牛顿法的收敛速度虽然较快 但要求Hessian矩阵要可逆 要计算二阶导数和逆矩阵 就加大了计算机计算量和存储量 Matlab优化工具箱简介 1 MATLAB求解优化问题的主要函数 2 优化函数的输入变量 使用优化函数或优化工具箱中其它优化函数时 输入变量见下表 3 优化函数的输出变量下表 用Matlab解无约束优化问题 其中 3 4 5 的等式右边可选用 1 或 2 的等式右边 函数fminbnd的算法基于黄金分割法和二次插值法 它要求目标函数必须是连续函数 并可能只给出局部最优解 常用格式如下 1 x fminbnd fun x1 x2 2 x fminbnd fun x1 x2 options 3 x fval fminbnd 4 x fval exitflag fminbnd 5 x fval exitflag output fminbnd ToMatlab wliti1 主程序为wliti1 m f 2 exp x sin x fplot f 0 8 作图语句 xmin ymin fminbnd f 0 8 f1 2 exp x sin x xmax ymax fminbnd f1 0 8 例2对边长为3米的正方形铁板 在四个角剪去相等的正方形以制成方形无盖水槽 问如何剪法使水槽的容积最大 解 先编写M文件fun0 m如下 functionf fun0 x f 3 2 x 2 x 主程序为wliti2 m x fval fminbnd fun0 0 1 5 xmax xfmax fval 运算结果为 xmax 0 5000 fmax 2 0000 即剪掉的正方形的边长为0 5米时水槽的容积最大 最大容积为2立方米 ToMatlab wliti2 命令格式为 1 x fminunc fun X0 或x fminsearch fun X0 2 x fminunc fun X0 options 或x fminsearch fun X0 options 3 x fval fminunc 或 x fval fminsearch 4 x fval exitflag fminunc 或 x fval exitflag fminsearch 5 x fval exitflag output fminunc 或 x fval exitflag output fminsearch 2 多元函数无约束优化问题 标准型为 minF X 3 fminunc为中型优化算法的步长一维搜索提供了两种算法 由options中参数LineSearchType控制 LineSearchType quadcubic 缺省值 混合的二次和三次多项式插值 LineSearchType cubicpoly 三次多项式插 使用fminunc和fminsearch可能会得到局部最优解 说明 fminsearch是用单纯形法寻优 fminunc的算法见以下几点说明 1 fminunc为无约束优化提供了大型优化和中型优化算法 由options中的参数LargeScale控制 LargeScale on 默认值 使用大型算法LargeScale off 默认值 使用中型算法 2 fminunc为中型优化算法的搜索方向提供了4种算法 由options中的参数HessUpdate控制 HessUpdate bfgs 默认值 拟牛顿法的BFGS公式 HessUpdate dfp 拟牛顿法的DFP公式 HessUpdate steepdesc 最速下降法 例3minf x 4x12 2x22 4x1x2 2x2 1 exp x1 ToMatlab wliti3 1 编写M 文件fun1 m functionf fun1 x f exp x 1 4 x 1 2 2 x 2 2 4 x 1 x 2 2 x 2 1 2 输入M文件wliti3 m如下 x0 1 1 x fminunc fun1 x0 y fun1 x 3 运行结果 x 0 5000 1 0000y 1 3029e 10 ToMatlab wliti31 ToMatlab wliti32 3 用fminsearch函数求解 ToMatlab wliti41 输入命令 f 100 x 2 x 1 2 2 1 x 1 2 x fval exitflag output fminsearch f 1 22 运行结果 x 1 00001 0000fval 1 9151e 010exitflag 1output iterations 108funcCount 202algorithm Nelder Meadsimplexdirectsearch 4 用fminunc函数 ToMatlab wliti44 1 建立M 文件fun2 mfunctionf fun2 x f 100 x 2 x 1 2 2 1 x 1 2 2 主程序wliti44 m Rosenbrock函数不同算法的计算结果 可以看出 最速下降法的结果最差 因为最速下降法特别不适合于从一狭长通道到达最优解的情况 例5产销量的最佳安排某厂生产一种产品有甲 乙两个牌号 讨论在产销平衡的情况下如何确定各自的产量 使总利润最大 所谓产销平衡指工厂的产量等于市场上的销量 基本假设 1 价格与销量成线性关系 2 成本与产量成负指数关系 模型建立 若根据大量的统计数据 求出系数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 我们把它作为原问题的初始值 总利润为 z x1 x2 p1 q1 x1 p2 q2 x2 模型求解 1 建立M 文件fun m functionf fun x y1 100 x 1 0 1 x 2 30 exp 0 015 x 1 20 x 1 y2 280 0 2 x 1 2 x 2 100 exp 0 02 x 2 30 x 2 f y1 y2 2 输入命令 x0 50 70 x fminunc fun x0 z fun x 3 计算结果 x 23 9025 62 4977 z 6 4135e 003即甲的产量为23 9025 乙的产量为62 4977 最大利润为6413 5 ToMatlab wliti5 返回 练习 1 线性逼近法 基本思想 将目标函数和约束函数近似为线性函数 转化为线性规划问题求解 重复这个过程 步骤 给定控制误差 0 初始可行点xk 初始步长 k 0 在xk线性化得线性规划问题 非线性规划 有约束问题 求出此线性规划问题得最优解xk 1 检验是否为原问题的的可行解 若是转 否则缩短步长转 判断精度 则取最优解x xk 1 停 否则令k k 1转 非线性规划 有约束问题 2 罚函数法 转化为无约束最优化问题 M为足够大的正数 称为罚因子 算法分析 设可行域为S 构造函数 非线性规划 有约束问题 求无约束问题得最优解为X M 直观看出 只有当X M S才可能真正取得极小值 若 就加大罚因子M 使X M 向S逼近 当M 时 点列 非线性规划 有约束问题 计算步骤 第k次迭代 非线性规划 有约束问题 有约束问题matlab解法 x fval fmincon myfun x0 A b x fval fmincon myfun x0 A b Aeq beq x fval fmincon myfun x0 A b Aeq beq lb ub x fval fmincon myfun x0 A b Aeq beq lb ub comfun 缺省的用 代替 myfun与confun是M 函数的地址具体如 目标函数 Functionf myfun x 非线性约束 function c ceq confun x Nonlinearinequalityconstraintsc c1 x c2 x Nonlinearequalityconstraintsceq ceq1 x ceq2 x M 函数 1 先建立M文件fun4 m 定义目标函数 functionf fun4 x f exp x 1 4 x 1 2 2 x 2 2 4 x 1 x 2 2 x 2 1 x1 x2 0s t 1 5 x1x2 x1 x20 x1x2 100 例3 2 再建立M文件mycon m定义非线性约束 function g ceq mycon x g x 1 x 2 1 5 x 1 x 2 x 1 x 2 x 1 x 2 10 例4 1 先建立M 文件fun m定义目标函数 functionf fun x f 2 x 1 x 2 2 再建立M文件mycon2 m定义非线性约束 function g ceq mycon2 x g x 1 2 x 2 2 25 x 1 2 x 2 2 7 应用实例 供应与选址 某公司有6个建筑工地要开工 每个工地的位置 用平面坐标系a b表示 距离单位 千米 及水泥日用量d 吨 由下表给出 目前有两个临时料场位于A 5 1 B 2 7 日储量各有20吨 假设从料场到工地之间均有直线道路相连 1 试制定每天的供应计划 即从A B两料场分别向各工地运送多少吨水泥 使总的吨千米数最小 2 为了进一步减少吨千米数 打算舍弃两个临时料场 改建两个新的 日储量各为20吨 问应建在何处 节省的吨千米数有多大 一 建立模型 记工地的位置为 ai bi 水泥日用量为di i 1 6 料场位置为 xj yj 日储量为ej j 1 2 从料场j向工地i的运送量为Xij 当用临时料场时决策变量为 Xij 当不用临时料场时决策变量为 Xij xj yj 二 使用临时料场的情形 使用两个临时料场A 5 1 B 2 7 求从料场j向工地i的运送量为Xij 在各工地用量必须满足和各料场运送量不超过日储量的条件下 使总的吨千米数最小 这是线性规划问题 线性规划模型为 设X11 X1 X21 X2 X31 X3 X41 X4 X51 X5 X61 X6X12 X7 X22 X8 X32 X9 X42 X10 X52 X11 X62 X12编写程序gying1 m MATLAB gying1 计算结果为 x 3 00005 00000 00007 00000 00001 00000 00000 00004 00000 00006 000010 0000 fval 136 2275 三 改建两个新料场的情形 改建两个新料场 要同时确定料场的位置 xj yj 和运送量Xij 在同样条件下使总吨千米数最小 这是非线性规划问题 非线性规划模型为 设X11 X1 X21 X2 X31 X3 X41 X4 X51 X5 X61 X6X12 X7 X22 X8 X32 X9 X42 X10 X52 X11 X62 X12x1 X13 y1 X14 x2 X15 y2 X16 1 先编写M文件liaoch m定义目标函数 MATLAB liaoch 2 取初值为线性规划的计算结果及临时料场的坐标 x0 35070100406105127 编写主程序gyin