数学建模-最优化模型

最优化模型 一 最优化方法概述 二 无约束最优化问题 三 无约束最优化问题的MATLAB求解 四 有约束最优化问题 最优化方法概述 1 最优化理论和方法是近二十多年来发展十分迅速的一个数学分支 2 在数学上 最优化是一种求极值的方法 3 最优化已经广泛的渗透到工程 经济 电子技术等领域 在实际生活当中 人们做任何事情 不管是分析问题 还是进行决策 都要用一种标准衡量一下是否达到了最优 比如基金人投资 在各种科学问题 工程问题 生产管理 社会经济问题中 人们总是希望在有限的资源条件下 用尽可能小的代价 获得最大的收获 比如保险 数学家对最优化问题的研究已经有很多年的历史 以前解决最优化问题的数学方法只限于古典求导方法和变分法 求无约束极值问题 拉格朗日 Lagrange 乘数法解决等式约束下的条件极值问题 计算机技术的出现 使得数学家研究出了许多最优化方法和算法用以解决以前难以解决的问题 最优化 在一定的条件下 寻求使得目标最大 最小 的策略 约一半以上的问题与最优化问题有关 如 飞行管理问题 95A 最优捕鱼策略 96A 节水洗衣机 96B 零件的参数设计 97A 投资收益和风险 98A 钢管订购和运输 2000B 电力市场的堵塞管理 2004B 几个概念 最优化是从所有可能方案中选择最合理的一种以达到最优目标的学科 最优方案是达到最优目标的方案 最优化方法是搜寻最优方案的方法 最优化理论就是最优化方法的理论 经典极值问题 包括 无约束极值问题 约束条件下的极值问题 1 无约束极值问题的数学模型 2 约束条件下极值问题的数学模型 其中 极大值问题可以转化为极小值问题来进行求解 如求 可以转化为 1 无约束极值问题的求解 例1 求函数y 2x3 3x2 12x 14在区间 3 4 上的最大值与最小值 解 令f x y 2x3 3x2 12x 14f x 6x2 6x 12 6 x 2 x 1 解方程f x 0 得到x1 2 x2 1 又由于f 3 23 f 2 34 f 1 7 f 4 142 综上得 函数f x 在x 4取得在 3 4 上得最大值f 4 142 在x 1处取得在 3 4 上取得最小值f 1 7 用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 MATLAB 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有边长为3m的正方形铁板 在四个角剪去相等的正方形以制成方形无盖水槽 问如何剪法使水槽的容积最大 解 先编写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 5m时水槽的容积最大 最大容积为2m3 MATLAB 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 多元函数无约束优化问题 标准型为 min 例用fminsearch函数求解 输入命令 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 202algorthm Nelder Meadsimplexdirectsearch 建立数学模型时要尽可能简单 而且要能完整地描述所研究的系统 具体建立怎样的数学模型需要丰富的经验和熟练的技巧 即使在建立了问题的数学模型之后 通常也必须对模型进行必要的数学简化以便于分析 计算 一般的模型简化工作包括以下几类 1 将离散变量转化为连续变量 2 将非线性函数线性化 3 删除一些非主要约束条件 最优化问题的数学模型 建立最优化问题数学模型的三要素 1 决策变量和参数 决策变量是由数学模型的解确定的未知数 参数表示系统的控制变量 有确定性的也有随机性的 2 约束或限制条件 由于现实系统的客观物质条件限制 模型必须包括把决策变量限制在它们可行值之内的约束条件 而这通常是用约束的数学函数形式来表示的 3 目标函数 这是作为系统决策变量的一个数学函数来衡量系统的效率 即系统追求的目标 解 决定圆柱体表面积大小有两个决策变量 圆柱体底面半径r 高h 问题的约束条件是所铸圆柱体重量与球重相等 即 例1 把半径为1的实心金属球熔化后 铸成一个实心圆柱体 问圆柱体取什么尺寸才能使它的表面积最小 则得数学模型 s t Subjectto 问题目标是圆柱体表面积最小 即min 即即 此时圆柱体的表面积为 分别对r h 求偏导数 并令其等于零 有 利用在高等数学中所学的Lagrange乘子法可求解本问题 例4 多参数曲线拟合问题已知两个物理量x和y之间的依赖关系为 其中和待定参数 为确定这些参数 对x y测得m个实验点 试将确定参数的问题表示成最优化问题 解 很显然对参数和任意给定的一组数值 就由上式确定了y关于x的一个函数关系式 在几何上它对应一条曲线 这条曲线不一定通过那m个测量点 而要产生 偏差 将测量点沿垂线方向到曲线的距离的平方和作为这种 偏差 的度量 即显然偏差S越小 曲线就拟合得越好 说明参数值就选择得越好 从而我们的问题就转化为5维无约束最优化问题 即 有约束最优化最优化方法分类 一 线性最优化 目标函数和约束条件都是线性的则称为线性最优化 非线性最优化 目标函数和约束条件如果含有非线性的 则称为非线性最优化 二 静态最优化 如果可能的方案与时间无关 则是静态最优化问题 动态最优化 如果可能的方案与时间有关 则是动态最优化问题 有约束最优化问题的数学建模 有约束最优化模型一般具有以下形式 或 其中f x 为目标函数 省略号表示约束式子 可以是等式约束 也可以是不等式约束 根据目标函数 约束条件的特点将最优化方法包含的主要内容大致如下划分 线性规划整数规划非线性规划动态规划多目标规划对策论 最优化方法主要内容 最优化问题的一般数学模型 最优化问题的一般算法 整体 全局 最优解 若 对于一切 恒有则称是最优化问题的整体最优解 局部最优解 若 存在某邻域 使得对于一切 恒有则称是最优化问题的局部最优解 其中严格最优解 当 有则称为问题的严格最优解 f X 局部最优解 整体最优解 运用最优化方法解决最优化问题的一般方法步骤如下 前期分析 分析问题 找出要解决的目标 约束条件 并确立最优化的目标 定义变量 建立最优化问题的数学模型 列出目标函数和约束条件 针对建立的模型 选择合适的求解方法或数学软件 编写程序 利用计算机求解 对结果进行分析 讨论诸如 结果的合理性 正确性 算法的收敛性 模型的适用性和通用性 算法效率与误差等 线性规划的模型的一般形式 目标函数满足约束条件通常称为决策变量 为价值系数 为消耗系数 为资源限制系数 线性规划 用单纯法求解时 常将标准形式化为 线性规划的基本算法 单纯形法 用MATLAB优化工具箱解线性规划 命令 x linprog c A b 2 模型 minz cX 命令 x linprog c A b Aeq beq 注意 若没有不等式 存在 则令A b 命令 1 x linprog c A b Aeq beq VLB VUB 2 x linprog c A b Aeq beq VLB VUB X0 注意 1 若没有等式约束 则令Aeq beq 2 其中X0表示初始点 4 命令 x fval linprog 返回最优解 及 处的目标函数值fval 问题 任务分配问题 某车间有甲 乙两台机床 可用于加工三种工件 假定这两台车床的可用台时数分别为800和900 三种工件的数量分别为400 600和500 且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表 问怎样分配车床的加工任务 才能既满足加工工件的要求 又使加工费用最低 引例 解设在甲车床上加工工件1 2 3的数量分别为x1 x2 x3 在乙车床上加工工件1 2 3的数量分别为x4 x5 x6 可建立以下线性规划模型 问题的解答 编写M文件xxgh3 m如下 f 1391011128 A 0 41 110000000 51 21 3 b 800 900 Aeq 100100010010001001 beq 400600500 vlb zeros 6 1 vub x fval linprog f A b Aeq beq vlb vub 结果 x 0 0000600 00000 0000400 00000 0000500 0000fval 1 3800e 004即在甲机床上加工600个工件2 在乙机床上加工400个工件1 500个工件3 可在满足条件的情况下使总加工费最小为13800 例1 某铁器加工厂要制作100套钢架 每套要用长为2 9米 2 1米和1 5米的圆钢各一根 已知原料长为7 4米 问应如何下料 可使材料最省 分析 在长度确定的原料上截取三种不同规格的圆钢 可以归纳出8种不同的下料方案 问题归纳为如何混合使用这8种不同的下料方案 来制造100套钢架 且要使剩余的料头总长为最短 线性规划的一些应用 设xj表示用第j种下料方案下料的原料根数 j 1 2 8 数学模型s t 这是一个下料问题 是在生产任务确定的条件下 合理的组织生产 使所消耗的资源数最少的数学规划问题 满足一组约束条件的同时 寻求变量x1至x8的值 使目标函数取得最小值 且为整数 数学模型s t 且为整数 设xj表示用第j种下料方案下料的原料根数 j 1 2 8 例2 人力资源分配问题红旗商场是个中型的百货商场 它对售货人员的需求经过统计分析如表所示 为了保证售货人员充分休息 售货人员每周工作五天 休息两天 并要求休息的两天是连续的 问应该如何安排售货人员的作息 既满足了工作需要又使配备的售货人员的人数最少 表 解 设x1为星期一开始上班的人数 x2为星期二开始上班的人数 x7星期日开始上班的人数 我们就可得到如下的数学模型 minx1 x2 x3 x4 x5 x6 x7x3 x4 x5 x6 x7 28x4 x5 x6 x7 x1 15x5 x6 x7 x1 x2 24x6 x7 x1 x2 x3 25x7 x1 x2 x3 x4 19x1 x2 x3 x4 x5 31x2 x3 x4 x5 x6 28x1 x2 x3 x4 x5 x6 x7 0该问题的最优解为 x1 8 x2 0 x3 12 x4 0 x5 11 x6 5 x7 0 目标函数的最小值为36 例3 某公司现有68名员工申请提前退休 公司必须在此后的8年内对这些员工分期支付一定数量的现金 如下表所示 注意 三种政府债券的票面价值均为1000元 债券到期时按票面价值进行支付 利率的计算也以票面的价值为基准 银行储蓄年利率为4 如何安排投资计划 使公司以最小的投资额完成对退休员工的现金支付任务 为了完成这项现金支付任务 公司的财务人员必须现在就为此制定一个投资计划 投资计划有政府债券投资和银行储蓄两种方式组成 政府债券投资有三种债券类型可供选择 如下表所示 解 1 确定决策变量设F为完成投资计划所需要的总资金额 x1 x2 x3分别表示债券1 2 3的购买量 yi i 1 8 表示第i年初银行储蓄的投资额 2 确定约束条件这类问题的一个典型特征就是每年现金支付的一般表达式为 年初可用资金额 当年用于债券和储蓄的资金额 当年现金支付于是有F 1 15x1 1x2 1 35x3 y1 430 第1年 对于第二年 用于三种债券投资的第一年利息加上第一年储蓄利息为年初可用资金 第二年用于储蓄的资金为y2 因此有0 08875x1 0 055x2 0 1175x3 1 04y1 y2 210 第2年 同理对于其它年份有0 08875x1 0 055x2 0 1175x3 1 04y2 y3 222 第3年 0 08875x1 0 055x2 0 1175x3 1 04y3 y4 231 第4年 0 08875x1 0 055x2 0 1175x3 1 04y4 y5 240 第5年 1 08875x1 0 055x2 0 1175x3 1 04y5 y6 195 第6年 1 055x2 0 1175x3 1 04y6 y7 225 第7年 1 1175x3 1 04y7 y8 255 第8年 因此事实上 y8的值应为0 若大于0 那么对应的投资计划必定不是最优的 3 确定目标函数目标就是使满足要求的投资额最小 即Minz F综合有如下数学模型Minz FF 1 15x1 1x2 1 35x3 y1 4300 08875x1 0 055x2 0 1175x3 1 04y1 y2 2100 08875x1 0 055x2 0 1175x3 1 04y2 y3 2220 08875x1 0 055x2 0 1175x3 1 04y3 y4 2310 08875x1 0 055x2 0 1175x3 1 04y4 y5 2401 08875x1 0 055x2 0 1175x3 1 04y5 y6 1951 055x2 0 1175x3 1 04y6 y7 2251 1175x3 1 04y7 y8 255x1 x2 x3 0 yi 0 i 1 8 该线性规划模型的求解结果为目标函数最优值为 1728 794变量最优解检验数F1728 7940 x1144 9880 x2187 8560 x3228 1880y1636 1480y2501 6060y3349 6820y4182 6810y500 064y600 0126y700 0213y800 671 即得到最佳投资计划如下表所示 约束松弛 剩余变量对偶价格10 1 00020 0 96230 0 92540 0 88950 0 85560 0 76070 0 71980 0 671结果分析 前4年的储蓄额均大于0 可见从第6年起债券的利息和债券到期收入才能够完全满足当前现金支付需要 每一个约束条件的对偶价格均为负值 说明减少任何一年的现金支付都将有利于公司总投资额的降低 对偶价格的逐年降低也说明了 在前面年份减少现金支付将对总投资额的减少更为有效 从而暗示了公司可以适当减少前面年份的现金支付量 而在后面年份进行补足 Minz FF 1 15x1 1x2 1 35x3 y1 4300 08875x1 0 055x2 0 1175x3 1 04y1 y2 2100 08875x1 0 055x2 0 1175x3 1 04y2 y3 2220 08875x1 0 055x2 0 1175x3 1 04y3 y4 2310 08875x1 0 055x2 0 1175x3 1 04y4 y5 2401 08875x1 0 055x2 0 1175x3 1 04y5 y6 1951 055x2 0 1175x3 1 04y6 y7 2251 1175x3 1 04y7 y8 255x1 x2 x3 0 yi 0 i 1 8 线性规划应用小结 线性规划有着广泛的应用 线性规划的应用非常灵活 所讲案例只是真实情况的缩微 投资的收益和风险 98A 二 基本假设和符号规定 三 模型的建立与分析 1 总体风险用所投资的Si中最大的一个风险来衡量 即max qixi i 1 2 n 4 模型简化 四 模型1的求解 由于a是任意给定的风险度 到底怎样给定没有一个准则 不同的投资者有不同的风险度 我们从a 0开始 以步长 a 0 001进行循环搜索 编制程序如下 a 0 while 1 1 a 1c 0 05 0 27 0 19 0 185 0 185 Aeq 11 011 021 0451 065 beq 1 A 00 025000 000 01500 0000 0550 00000 026 b a a a a vlb 0 0 0 0 0 vub x val linprog c A b Aeq beq vlb vub ax x Q valplot a Q axis 00 100 5 holdona a 0 001 endxlabel a ylabel Q 计算结果 五 结果分析 3 曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险 对于不同风险的承受能力 选择该风险水平下的最优投资组合 2 当投资越分散时 投资者承担的风险越小 这与题意一致 即 冒险的投资者会出现集中投资的情况 保守的投资者则尽量分散投资 1 风险大 收益也大 4 在a 0 006附近有一个转折点 在这一点左边 风险增加很少时 利润增长很快 在这一点右边 风险增加很大时 利润增长很缓慢 所以对于风险和收益没有特殊偏好的投资者来说 应该选择曲线的拐点作为最优投资组合 大约是a 0 6 Q 20 所对应投资方案为 风险度收益x0 x1x2x3x40 00600 201900 24000 40000 10910 2212 无约束最优化问题 标准形式 求解无约束最优化问题的基本思想 求解的基本思想 以二元函数为例 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矩阵要可逆 要计算二阶导数和逆矩阵 就加大了计算机计算量和存储量 3 拟牛顿法 其他多种直接算法 单纯形调优法 H J法 Powell方向加速法等 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 主程序为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立方米 命令格式为 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 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 3 用fminsearch函数求解 输入命令 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函数 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 约束非线性规划 定义如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题 约束非现性规划的基本概念 一般形式 1 其中 是定义在En上的实值函数 简记 其它情况 求目标函数的最大值或约束条件为小于等于零的情况 都可通过取其相反数化为上述一般形式 非线性规划的基本解法 SUTM外点法 SUTM内点法 障碍罚函数法 1 罚函数法 2 近似规划法 罚函数法 罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题 进而用无约束最优化方法去求解 这类方法称为序列无约束最小化方法 简称为SUMT法 其一为SUMT外点法 其二为SUMT内点法 其中T X M 称为罚函数 M称为罚因子 带M的项称为罚项 这里的罚函数只对不满足约束条件的点实行惩罚 当时 满足各 故罚项 0 不受惩罚 当时 必有的约束条件 故罚项 0 要受惩罚 SUTM外点法 罚函数法的缺点是 每个近似最优解Xk往往不是容许解 而只能近似满足约束 在实际问题中这种结果可能不能使用 在解一系列无约束问题中 计算量太大 特别是随着Mk的增大 可能导致错误 1 任意给定初始点X0 取M1 1 给定允许误差 令k 1 2 求无约束极值问题的最优解 设为Xk X Mk 即 3 若存在 使 则取Mk M 令k k 1返回 2 否则 停止迭代 得最优解 计算时也可将收敛性判别准则改为 SUTM外点法 罚函数法 的迭代步骤 SUTM内点法 障碍函数法 内点法的迭代步骤 近似规划法的基本思想 将问题 3 中的目标函数和约束条件近似为线性函数 并对变量的取值范围加以限制 从而得到一个近似线性规划问题 再用单纯形法求解之 把其符合原始条件的最优解作为 3 的解的近似 近似规划法 每得到一个近似解后 都从这点出发 重复以上步骤 这样 通过求解一系列线性规划问题 产生一个由线性规划最优解组成的序列 经验表明 这样的序列往往收敛于非线性规划问题的解 近似规划法的算法步骤如下 用MATLAB软件求解 其输入格式如下 1 x quadprog H C A b 2 x quadprog H C A b Aeq beq 3 x quadprog H C A b Aeq beq VLB VUB 4 x quadprog H C A b Aeq beq VLB VUB X0 5 x quadprog H C A b Aeq beq VLB VUB X0 options 6 x fval quaprog 7 x fval exitflag quaprog 8 x fval exitflag output quaprog 1 二次规划 例1minf x1 x2 2x1 6x2 x12 2x1x2 2x22s t x1 x2 2 x1 2x2 2x1 0 x2 0 1 写成标准形式 2 输入命令 H 1 1 12 c 2 6 A 11 12 b 2 2 Aeq beq VLB 0 0 VUB x z quadprog H c A b Aeq beq VLB VUB 3 运算结果为 x 0 66671 3333z 8 2222 s t 1 首先建立M文件fun m 定义目标函数F X functionf fun X f F X 2 一般约束非线性规划 其中X为n维变元向量 G X 与Ceq X 均为非线性函数组成的向量 其它变量的含义与线性规划 二次规划中相同 用Matlab求解上述问题 基本步骤分三步 3 建立主程序 非线性规划求解的函数是fmincon 命令的基本格式如下 1 x fmincon fun X0 A b 2 x fmincon fun X0 A b Aeq beq 3 x fmincon fun X0 A b Aeq beq VLB VUB 4 x fmincon fun X0 A b Aeq beq VLB VUB nonlcon 5 x fmincon fun X0 A b Aeq beq VLB VUB nonlcon options 6 x fval fmincon 7 x fval exitflag fmincon 8 x fval exitflag output fmincon 输出极值点 M文件 迭代的初值 参数说明 变量上下限 注意 1 fmincon函数提供了大型优化算法和中型优化算法 默认时 若在fun函数中提供了梯度 options参数的GradObj设置为 on 并且只有上下界存在或只有等式约束 fmincon函数将选择大型算法 当既有等式约束又有梯度约束时 使用中型算法 2 fmincon函数的中型算法使用的是序列二次规划法 在每一步迭代中求解二次规划子问题 并用BFGS法更新拉格朗日Hessian矩阵 3 fmincon函数可能会给出局部最优解 这与初值X0的选取有关 1 写成标准形式 s t 2x1 3x26s tx1 4x25x1 x20 例2 2 先建立M 文件fun3 m functionf fun3 x f x 1 2 x 2 1 2 x 1 2 1 2 x 2 2 3 再建立主程序youh2 m x0 1 1 A 23 14 b 6 5 Aeq beq VLB 0 0 VUB x fval fmincon fun3 x0 A b Aeq beq VLB VUB 4 运算结果为 x 0 76471 0588fval 2 0294 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 3 主程序youh3 m为 x0 1 1 A b Aeq 11 beq 0 vlb vub x fval fmincon fun4 x0 A b Aeq beq vlb vub mycon 3 运算结果为 x 1 22501 2250fval 1 8951 例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 3 主程序fxx m为 x0 3 2 5 VLB 00 VUB 510 x fval exitflag output fmincon fun x0 VLB VUB mycon2 4 运算结果为 x 4 00003 0000fval 11 0000exitflag 1output iterations 4funcCount 17stepsize 1algorithm 1x44char firstorderopt cgiterations 应用实例 供应与选址 某公司有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 计算结果为 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定义目标函数 2 取初值为线性规划的计算结果及临时料场的坐标 x0 35070100406105127 编写主程序gying2 m 3 计算结果为 x 3 00005 00000 07077 000000 9293003 929306 000010 07076 38754 39435 75117 1867 fval 105 4626exitflag 1 4 若修改主程序gying2 m 取初值为上面的计算结果 x0 3 00005 00000 07077 000000 9293003 929306 000010 07076 38754 39435 75117 1867 得结果为 x 3 00005 0