matlab非线性规划.ppt

1 数学建模与数学实验 后勤工程学院数学教研室 非线性规划 2 实验目的 实验内容 2 掌握用数学软件求解优化问题 1 直观了解非线性规划的基本内容 1 非线性规划的基本理论 4 实验作业 2 用数学软件求解非线性规划 3 钢管订购及运输优化模型 3 非线性规划的基本解法 非线性规划的基本概念 非线性规划 返回 4 定义如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题 非现性规划的基本概念 一般形式 1 其中 是定义在En上的实值函数 简记 其它情况 求目标函数的最大值或约束条件为小于等于零的情况 都可通过取其相反数化为上述一般形式 5 定义1把满足问题 1 中条件的解称为可行解 或可行点 所有可行点的集合称为可行集 或可行域 记为D 即问题 1 可简记为 定义2对于问题 1 设 若存在 使得对一切 且 都有 则称X 是f X 在D上的局部极小值点 局部最优解 特别地当时 若 则称X 是f X 在D上的严格局部极小值点 严格局部最优解 定义3对于问题 1 设 对任意的 都有则称X 是f X 在D上的全局极小值点 全局最优解 特别地当时 若 则称X 是f X 在D上的严格全局极小值点 严格全局最优解 返回 6 非线性规划的基本解法 SUTM外点法 SUTM内点法 障碍罚函数法 1 罚函数法 2 近似规划法 返回 7 罚函数法 罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题 进而用无约束最优化方法去求解 这类方法称为序列无约束最小化方法 简称为SUMT法 其一为SUMT外点法 其二为SUMT内点法 8 其中T X M 称为罚函数 M称为罚因子 带M的项称为罚项 这里的罚函数只对不满足约束条件的点实行惩罚 当时 满足各 故罚项 0 不受惩罚 当时 必有的约束条件 故罚项 0 要受惩罚 SUTM外点法 9 罚函数法的缺点是 每个近似最优解Xk往往不是容许解 而只能近似满足约束 在实际问题中这种结果可能不能使用 在解一系列无约束问题中 计算量太大 特别是随着Mk的增大 可能导致错误 1 任意给定初始点X0 取M1 1 给定允许误差 令k 1 2 求无约束极值问题的最优解 设为Xk X Mk 即 3 若存在 使 则取Mk M 令k k 1返回 2 否则 停止迭代 得最优解 计算时也可将收敛性判别准则改为 SUTM外点法 罚函数法 的迭代步骤 10 SUTM内点法 障碍函数法 11 内点法的迭代步骤 12 近似规划法的基本思想 将问题 3 中的目标函数和约束条件近似为线性函数 并对变量的取值范围加以限制 从而得到一个近似线性规划问题 再用单纯形法求解之 把其符合原始条件的最优解作为 3 的解的近似 近似规划法 每得到一个近似解后 都从这点出发 重复以上步骤 这样 通过求解一系列线性规划问题 产生一个由线性规划最优解组成的序列 经验表明 这样的序列往往收敛于非线性规划问题的解 13 近似规划法的算法步骤如下 14 返回 15 用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 二次规划 16 例1minf x1 x2 2x1 6x2 x12 2x1x2 2x22s t x1 x2 2 x1 2x2 2x1 0 x2 0 MATLAB youh1 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 17 1 首先建立M文件fun m 定义目标函数F X functionf fun X f F X 2 一般非线性规划 其中X为n维变元向量 G X 与Ceq X 均为非线性函数组成的向量 其它变量的含义与线性规划 二次规划中相同 用Matlab求解上述问题 基本步骤分三步 18 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文件 迭代的初值 参数说明 变量上下限 19 注意 1 fmincon函数提供了大型优化算法和中型优化算法 默认时 若在fun函数中提供了梯度 options参数的GradObj设置为 on 并且只有上下界存在或只有等式约束 fmincon函数将选择大型算法 当既有等式约束又有梯度约束时 使用中型算法 2 fmincon函数的中型算法使用的是序列二次规划法 在每一步迭代中求解二次规划子问题 并用BFGS法更新拉格朗日Hessian矩阵 3 fmincon函数可能会给出局部最优解 这与初值X0的选取有关 20 1 写成标准形式 s t 2x1 3x26s tx1 4x25x1 x20 例2 21 2 先建立M 文件fun3 m functionf fun3 x f x 1 2 x 2 1 2 x 1 2 1 2 x 2 2 MATLAB youh2 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 22 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 23 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 MATLAB youh3 3 运算结果为 x 1 22501 2250fval 1 8951 24 例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 25 3 主程序fxx m为 x0 3 2 5 VLB 00 VUB 510 x fval exitflag output fmincon fun x0 VLB VUB mycon2 MATLAB fxx fun 26 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 MATLAB gying1 30 计算结果为 x 3 00005 00000 00007 00000 00001 00000 00000 00004 00000 00006 000010 0000 fval 136 2275 31 三 改建两个新料场的情形 改建两个新料场 要同时确定料场的位置 xj yj 和运送量Xij 在同样条件下使总吨千米数最小 这是非线性规划问题 非线性规划模型为 32 设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 编写主程序gying2 m MATLAB gying2 33 3 计算结果为 x 3 00005 00000 07077 000000 9293003 929306 000010 07076 38754 39435 75117 1867 fval 105 4626exitflag 1 34 4 若修改主程序gying2 m 取初值为上面的计算结果 x0 3 00005 00000 07077 000000 9293003 929306 000010 07076 38754 39435 75117 1867 得结果为 x 3 00005 00000 30947 00000 01080 6798003 690605 989210 32025 53694 91945 82917 2852 fval 103 4760exitflag 1 总的吨千米数比上面结果略优 5 若再取刚得出的结果为初值 却计算不出最优解 MATLAB gying2 MATLAB gying2 35 6 若取初值为 x0 35471000005115 63484 86877 24797 7499 则计算结果为 x 3 00005 00004 00007 00001 0000000005 000011 00005 69594 92857 25007 7500 fval 89 8835exitflag 1总的吨千米数89 8835比上面结果更好 通过此例可看出fmincon函数在选取初值上的重要性 MATLAB gying2 返回 36 钢管订购及运输优化模型 2000年 网易杯 全国大学生数学建模竞赛B题 37 符号说明 38 1 铺设总费用 2 成本及运输总费用 总费用 铺设总费用 成本及运输总费用 C W 模型的分析与建立 39 建立模型 40 模型求解 利用MATLAB软件包求解得 41 订购和运输方案表 返回 42 某厂向用户提供发动机 合同规定 第一 二 三季度末分别交货40台 60台 80台 每季度的生产费用为 元 其中x是该季生产的台数 若交货后有剩余 可用于下季度交货 但需支付存储费 每台每季度c元 已知工厂每季度最大生产能力为100台 第一季度开始时无存货 设a 50 b 0 2 c 4 问工厂应如何安排生产计划 才能既满足合同又使总费用最低 讨论a b c变化对计划的影响 并作出合理的解释 练习1 43 练习2 返回 44 谢谢