数学规划模型实验ppt课件.ppt

数学规划模型实验 数学教研组卢鹏2015 7 23 优化问题及其一般模型 引言 优化问题是人们在工程技术 经济管理和科学研究等领域中最常遇到的问题之一 例如 设计师要在满足强度要求等条件下选择材料的尺寸 使结构总重量最轻 公司经理要根据生产成本和市场需求确定产品价格 使所获利润最高 调度人员要在满足物质需求和装载条件下安排从各供应点到需求点的运量和路线 使运输总费用最低 投资者要选择一些股票 债券下注 使收益最大 而风险最小 一般地 优化模型可以表述下 这是一个多元函数的条件极值问题 其中 许多实际问题归结出的这种优化模型 若决策变量个数较少可用微分法求解 但是其决策变量个数n和约束条件个数m较大 并且最优解往往在可行域的边界上取得 数学规划就是解决这类问题的有效方法 数学规划模型分类 数学规划是运筹学和管理科学中应用及其广泛的分支 数学规划包括线性规划 非线性规划 整数规划 几何规划 多目标规划等 用数学规划方法解决实际问题 就要将实际问题经过抽象 简化 假设 确定变量与参数 建立适当层次上的数学模型 并求解 建立数学规划模型的步骤 Step1 寻求决策 即回答什么 必须清楚 无歧义 阅读完题目的第一步不是寻找答案或者解法 而是 Step2 确定决策变量第一来源 Step1的结果 用变量固定需要回答的决策第二来源 由决策导出的变量 具有派生结构 其它来源 辅助变量 联合完成更清楚的回答 Step3 确定优化目标用决策变量表示的利润 成本等 Step4 寻找约束条件决策变量之间 决策变量与常量之间的联系 第一来源 需求 第二来源 供给 其它来源 辅助以及常识 Step5 构成数学模型将目标以及约束放在一起 写成数学表达式 目录 线性规划非线性规划二次规划整数规划 例1 加工奶制品的生产计划 一奶制品加工厂用牛奶生产A1 A2两种奶制品 一桶牛奶可以在设备甲上用12小时加工成3公斤A1 或者在设备乙上用8小时加工成4公斤A2 根据市场需求 生产的A1 A2全部能够售出 且每公斤A1获利24元 每公斤A2获利16元 现在加工厂每天能够得到50桶牛奶的供应 每天正式工人总的劳动时间为480小时 并且设备甲每天至多能加工100公斤A1 设备乙的加工能力没有限制 试为该厂制定一个生产计划 使每天获利最大 每天 50桶牛奶 时间480小时 至多加工100公斤A1 制订生产计划 使每天获利最大 问题分析 引入决策变量x1桶牛奶生产A1 x2桶牛奶生产A2 每天 目标函数 每天获利 生产A1获利 24 3x1生产A2获利 16 4x2每天获利总额 z 72x1 64x2约束条件原料供应 x1 x2 50劳动时间 12x1 8x2 480加工能力 3x1 100非负约束 x1 x2 0 模型构成 线性规划数学模型 线性规划求解 标准形式 其中 均为列向量 为矩阵 调用格式 x fval linprog c A b Aeq beq lb ub options 其中 x给出极小点 fval给出目标函数极小值 options是控制参数 可用help查询 Matlab程序如下 c 72 64 A 1 1 12 8 3 0 b 50 480 100 Ib 0 0 ub 1e 10 1 1 x fval linprog c A b lb ub 结果如下 x 20 30 fval 3360 例2 求解线性规划问题 Matlab程序如下 c 2 3 5 A 2 5 1 b 10 Aeq 1 1 1 beq 7 lb 0 0 0 x fval linprog c A b Aeq beq lb 例3 求解非线性规划问题 非线性规划求解 标准形式 其中 调用格式 x fval h fmincon f x0 A b Aeq beq lb ub nonlcon 其中 nonlcon是非线性约束函数 x0是迭代初始点 和 是非线性约束 Matlab程序如下 建立非线性约束函数的m文件lpnon mfunction c ceq lpcon x c x 1 1 2 x 2 Ceq 建立目标函数的m文件fun mfunctionf fun x f x 1 2 x 2 2 x 1 x 2 2 x 1 5 x 2 在命令窗口中输入x0 0 1 A 23 b 6 Aeq beq lb ub x fval h fmincon fun x0 A b Aeq beq lb ub lpcon 结果 x 3 4 fval 13 h 1 例4 求解二次规划问题 二次规划求解 标准形式 其中 H是实对称矩阵 调用格式 x fval quadprog H c A b Aeq beq lb ub x0 Matlab程序如下 H 1 1 1 2 c 2 6 A 1 1 1 2 2 1 b 2 2 3 Aeq beq lb zeros 2 1 ub x fval quadprog H c A b Aeq beq lb ub 结果 x 0 6667 1 3333 fval 8 2222 例5 求解整数规划问题 整数规划求解 随机投点法 编写目标函数和约束条件的m文件 function f g mengte x f x 1 2 x 2 2 3 x 3 2 4 x 4 2 2 x 5 2 8 x 1 2 x 2 3 x 3 x 4 2 x 5 g 1 sum x 400 g 2 x 1 2 x 2 2 x 3 x 4 6 x 5 800 g 3 2 x 1 x 2 6 x 3 200 g 4 x 3 x 4 5 x 5 200 Matlab程序如下 p0 0 x0 zeros 5 1 ticfori 1 100000 x1 99 rand