[IT认证]优化模型讲义.ppt

第一讲 规划理论及模型 一、引言 二、线性规划模型 线性规划模型的三种形式 ②．为了把一般形式的LP问题变换为标准形式，必须消除其不等式约束和符号无限制变量. 运输问题 例2. 设要从甲地调出物资2000吨，从乙地调出物 数学模型： 背包问题 例4. 有 n 个物品，编号为1, 2, …, n，第 i 件物品 指派问题 例5. 有n 项任务，由 n 个人来完成，每个人只能 DVD在线租赁第二个问题的求解 问题二的分析 问题二的模型及求解 5.非线性规划模型 事实上，客观世界中的问题许多是非线性的，给予线性大多是近似的，是在作了科学的假设和简化后得到的. 为了利用线性的知识，许多非线性问题常进行线性化处理. 但在实际问题中，有一些是不能进行线性化处理的，否则将严重影响模型对实际问题近似的可依赖型. 非线性规划问题的标准形式为： 表4 各种符号表示意义表 即: 解这个线性方程组得： 6、多目标规划模型  在许多实际问题中，衡量一个方案的好坏标准往往不止一个，例如设计一个导弹，既要射程最远，又要燃料最省，还要精度最高. 这一类问题统称为多目标最优化问题或多目标规划问题. 我们先来看一个生产计划的例子. 我们希望购买DVD的总数量最小，即 : 表6 当 时最小购买量的 值 续上表 我们利用规划模型求得每种DVD的购买量后，需要对其进行可行性校验，测试此结果是否可以满足一个月内比例为95%的会员得到他想看的DVD，且具有尽可能大的总体满意度. 校验方法： （一）根据订单和求得的DVD购买数量，利用问题二的规划模型进行第一次分配，对分配情况：租赁的会员，DVD的分配情况，剩余的各种DVD数量作记录；同时将已租赁的会员在满意指数矩阵的指数全变为0，即不考虑对其进行第二次分配. （三）统计出经过两次分配后，得到DVD的会员的比例，若大于95%，则此次分配成功.利用这种算法进行多次随机模拟，若大多数情况下可以使得到DVD的会员大于95%，则认为模型三是合理的. 校验结果： 因为每次检验需时约1小时，我们只对问题三求得的结果进行了7次模拟，其中6次符合要求（观看比例大于95%）.下面给出7次模拟得到的观看比例（表7）： 5.非线性规划模型 事实上，客观世界中的问题许多是非线性的，给予线性大多是近似的，是在作了科学的假设和简化后得到的. 为了利用线性的知识，许多非线性问题常进行线性化处理. 但在实际问题中，有一些是不能进行线性化处理的，否则将严重影响模型对实际问题近似的可依赖型. 非线性规划问题的标准形式为： 表4 各种符号表示意义表 即: 解这个线性方程组得： 6、多目标规划模型  在许多实际问题中，衡量一个方案的好坏标准往往不止一个，例如设计一个导弹，既要射程最远，又要燃料最省，还要精度最高. 这一类问题统称为多目标最优化问题或多目标规划问题. 我们先来看一个生产计划的例子. 我们希望购买DVD的总数量最小，即 : 表6 当 时最小购买量的 值 续上表 我们利用规划模型求得每种DVD的购买量后，需要对其进行可行性校验，测试此结果是否可以满足一个月内比例为95%的会员得到他想看的DVD，且具有尽可能大的总体满意度. 校验方法： （一）根据订单和求得的DVD购买数量，利用问题二的规划模型进行第一次分配，对分配情况：租赁的会员，DVD的分配情况，剩余的各种DVD数量作记录；同时将已租赁的会员在满意指数矩阵的指数全变为0，即不考虑对其进行第二次分配. （三）统计出经过两次分配后，得到DVD的会员的比例，若大于95%，则此次分配成功.利用这种算法进行多次随机模拟，若大多数情况下可以使得到DVD的会员大于95%，则认为模型三是合理的. 校验结果： 因为每次检验需时约1小时，我们只对问题三求得的结果进行了7次模拟，其中6次符合要求（观看比例大于95%）.下面给出7次模拟得到的观看比例（表7）： 20 20 15 20 16 22 21 16 20 32 最少购买量 D50 D49 D48 D47 D46 D45 D44 D43 D42 D41 DVD编号 17 17 17 13 22 22 19 20 22 19 最少购买量 D40 D39 D38 D37 D36 D35 D34 D33 D32 D31 DVD编号 24 16 12 15 17 18 14 22 18 20 最少购买量 D30 D29 D28