运筹学课件op1.ppt

OperationResearch 运筹学 什么是运筹学 运用科学的方法研究管理和工程中各种决策的问题 为决策者提供科学的决策依据的学科 包括线性规划 非线性规划 整数规划 目标规划 动态规划 图和网络规划 存储论 排队论 对策论和决策论等等 运筹学的工作步骤提出和形成问题 弄清问题的目标 可能的约束 问题的可控变量以及有关参数 搜集有关资料 建立模型 把问题中可控变量 参数和目标及约束之间的关系用一定的模型表示出来 求解 用各种手段将模型求解 所得解可以是最优解 次优解 满意解 解的检验 检查求解步骤和程序有无错误 检查解是否反映现实问题 向决策者提供建议 辅助解的实施 运筹学的学习要求 运用所学知识 能够建立相应的数学模型 掌握各种模型的基本的解题方法 正确理解和应用数学运算中各种参数的经济管理意义 第一章线性规划 线性规划问题及其数学模型线性规划图解法及其几何意义用Excal求解线性规划问题线性规划问题求解的几种可能结果 在生产管理和经营活动中经常提出一类问题 即如何合理地利用有限的人 财 物等资源 得到最好的经济效果 线性规划以数学为工具 研究在一定的人 财 物等资源条件下 用最少的资源耗费 取得最大的经济效果 1 线性规划问题及其数学模型 1 1资源合理利用问题 例1 某工厂要生产门 窗两种产品 生产一扇门需要1车间加工1小时 3车间加工3小时 生产一扇窗需要2车间 3车间各加工2小时 而1车间每周用于这两种产品的的时间为4小时 另两车间为12 18小时 已知每扇门的利润为300元 每扇窗为500元 据市场调查得到 其销路不成问题 问管理者如何安排两种产品的产量 获得利润最大 这个问题的决策目标是利润的最大化 线性规划问题的三个因素 决策变量 待确定的未知因素目标函数 问题所追求的目标的数学描述约束条件 实现目标的限制因素 分析 1 决策变量 产品的产量 设x1和x2 单位 扇 分别表示产品门 窗的产量 2 目标函数 设Z表示企业利润 则有 Z 300 x1 500 x2 元 3 约束条件 可建立资源限制的约束条件 x1 4 2x2 12 3x1 2x2 18x1 0 x2 0 归纳上述条件 可得该问题的线性规划数学模型如下 线性规划模型 一组决策变量 一个线性目标函数 一组线性约束方程 线性规划问题的三要素 满足这三要素的问题称为线性规划问题 2最小投资风险问题 例2 某公司有100万元的资金可供投资 该公司有六个可选的投资项目 公司希望 投资风险最小 每年至少6 5万元红利 最低平均增长率为12 最低平均信用度为7 请用线性规划求解该问题 1 确定决策变量 设xi 项目i的投资额 万元 i 1 6 2 目标函数 总投资风险最低 即 3 约束条件 各项目投资总和为100万元每年红利至少6 5万元最低平均增长率12 最低平均信用度7非负约束 线性规划模型为 1 3运输问题的数学模型 例3 某地有3个有色金属矿A1 A2 A3 生产同一种金属矿石 A1矿的年产量为100万吨 A2矿为80万吨 A3矿为50万吨 矿石全部供应4个冶炼厂 B1厂的全部需求量为50万吨 B2厂为70万吨 B3厂为80万吨 B4厂为30万吨 总产量恰好等于总需求量 矿石由各矿山运到冶炼厂的单位运价已知 如下表 问如何安排运输 使各矿山的矿石运到各冶炼厂 满足各厂的需要 且运输费用最小 1 确定变量 设xij表示第i个矿山运到第j个冶炼厂的矿石量 可列表如下 2 目标函数 设Z表示总费用 目标函数为 3 约束条件 各矿山的运输量与产量的平衡条件 各冶炼厂的输入量与需求量的平衡条件 运输问题的一般数学模型 设某产品有m个生产地 其产量分别为ai i 1 2 m 有n个消费地 需要量分别为bj j 1 2 n 并且产销平衡 即 Cij表示第i产地到第j消费地的单位产品运价 则 线性规划的建模步骤 确定一组决策变量 确定一组线性约束条件和一个线性目标函数 最大或最小 一般 设有n个决策变量 m个约束方程 则线性规划问题的一般表达形式如下 线性规划问题一般表达式 目标函数 约束条件 cj价值系数 费用系数 bi右端常数 资源常数 aij约束方程系数 技术系数 工艺系数 可行解 满足 式的解 可行解域 所有可行解的集合 最优解 的可行解 线性规划数学模型的简写形式或矩阵形式 2线性规划图解法及其几何意义 线性规划求解法目前最常用的方法有 图解法 利用模型中方程几何图形寻找最优解 单纯形法 求解线性规划的一般方法 2 1图解法只适合于两个变量 但是利用它的直观图形看问题 有助于了解和剖析线性规划的原理及过程 图解法的重点是说明线性规划的几何意义 举例说明图解法的求解过程 maxZ 4x1 3x2x1 62x2 82x1 3x2 18x1 x2 0 s t 在以x1 x2为坐标轴的直角坐标系中 非负条件是指第一象限 每一个约束条件都代表一个半平面 同时满足x1 x2 0 x1 62x2 82x1 3x2 18 必落在由这三个半平面交成的第一象限区域内 x1 x2 可行解 满足约束条件的解 绿色区域中的每一个点 包括边界点 都是可行解 此区域是线性规划问题的解的集合 可行解域 位于同一直线上的点 具有相同的目标函数 称为 等值线 当Z值由小变大时 直线x2 4x1 3 Z 3沿其法线方向 4 3 向右上方移动 当移动到Q2时 Z值在可行域的边界上实现最大化 最优解Q2 6 2 Z 32 图解法的计算步骤 1 绘出每个约束方程的约束半平面设约束方程为 画出直线 若约束方程为 则半平面在其直线的 a1 a2 方向 若约束方程为 则半平面在其直线的 a1 a2 方向 若约束方程为 则半平面即为该直线 2 绘出可行解域各个约束半平面相交的区域 3 设目标函数为作与方向相垂直的目标函数等值线在可行解域中移动 若目标为求 max 则目标函数等值线沿方向同方向移动 若目标为求 min 则目标函数等值线沿相反方向移动移动确定使目标函数达到最优可行解 即最优解 4 求出最优解 3 用EXCEL求解线性规划问题 一个优化模型有目标函数 决策变量 约束条件三部分组成 回忆前面的例1 在Excel窗口输入这个模型 打开Excal系统 输入原始数据 数据单元格 输出单元格 目标单元格 可变单元格 E8 C8 C12 D8 D12 E9 C9 C12 D9 D12 E10 C10 C12 D10 D12 G12 C5 C12 D5 D12 输入计算公式 模型求解 单击 工具 规划求解 模型求解 求解选项 线性模型 非负变量 求解结果 公式拷贝 单元格的绝对地址 C 5单元格的相对地址 C5 C5 C 5 例如 可用F4将绝对地址转换成相对地址 运用函数功能 在输出单元格中键入计算公式时 常常用到两个函数 sumproduct 对相等行数和相等列数的两个单元格区域中的对应单元格分别相乘后再求和 sum 对单元格区域中所有单元格求和 单元格命名 单位利润 可用公式 每周产量 实际使用 总利润 定义名称 查看 更改或删除已定义的名称 应用名称 将公式中的单元格引用更改为名称 黏贴名称 将单元格名称黏贴到电子表格中 黏贴列表 例2某公司有100万元的资金可供投资 该公司有六个可选的投资项目 公司希望 投资风险最小 每年至少6 5万元红利 最低平均增长率为12 最低平均信用度为7 请用线性规划求解该问题 4 线性规划问题求解的几种可能结果 线性规划问题具有唯一解指该规划问题有且仅有一个既在可行域内 又使目标值达到最优的解 如 线性规划问题求解可能情况 除唯一解外有无穷多最优解 多重解 将上例中的目标函数变为求 当移动到Q2Q3线段时 Z值在线段Q2Q3上实现最大化 线段Q2Q3上的任意一点都使Z取得相同的最大值 这个线性规划问题有无穷多最优解 2 无界解考虑下述线性规划问题 该问题可行域无界 目标函数可以增大到无穷大 可行域无界是否一定没有最优解 L1 L2 无可行解在例1中增加一个约束条件 可行域为空集 无可行解 当然也无最优解 唯一解无穷组解 无可行解 无界解 线性规划的几何意义 当线性规划问题的可行解域非空时 它是有界或无界凸多边形 若LP问题存在最优解 它一定在可行域某个顶点得到 若在两个顶点同时得到最优解 则它们连线上的任意一点都是最优解 即有无穷多最优解 线性规划的这些性质并不因变量的个数增加而改变 可以从两个变量的图解法几何意义理解任意多个变量单纯形法原理 练习题一 1 某家具制造厂生产五种不同规格的家具 每件家具都要经过机械成型 打磨 上漆等几个主要生产工序 已知生产数据如下 问工厂应如何安排生产 才能使总利润最大 2 某公司受人委托 准备用120万元投资A和B两种基金 其中A基金的单位投资额为50元 年回报率为10 B基金的单位投资额为100元 年回报率为4 委托人要求在每年的年回报金额至少达到6万元的基础上要求投资风险最小 据测定每单位A基金的投资风险指数为8 每单位B基金的投资风险