《运筹学复习指导wf》PPT课件.ppt

运筹学复习指导 经管类48课时2012年 考试内容及分值 1 第一章线性规划与单纯形法 25分 了解线性规划问题及其数学模型 解的基本性质掌握单纯形法的基本原理及其步骤 p32 T12熟练掌握图解法 线性规划的Excel规划求解以及线性规划问题的建模第二章对偶理论与灵敏度分析 15分 了解LP问题的对偶问题 对偶性质 对偶单纯形法的基本原理掌握灵敏度分析 p46 ex8熟练掌握影子价格的经济解释 考试内容及分值 2 第三章运输问题 10分 了解运输问题的数学模型掌握产销不平衡运输问题及有转运的运输问题的解决方法熟练掌握表上作业法 包括闭回路法与位势法 p88 T3第四章线性规划的应用 10分 熟练掌握线性规划问题的建模 p70 ex1 p83 ex4 p98 ex9 p92 ex3 考试内容及分值 3 第五章整数规划 10分 了解整数规划的数学模型及特点 理解整数规划的分支定界方法的基本思想 掌握整数规划与其对应的线性规划问题之间的关系熟练掌握求解指派问题的匈牙利法以及实际问题的建模第六章动态规划 10分 了解动态规划的基本概念和基本原理掌握动态规划的基本方程和递推方法 最优化原理熟练掌握多阶段实际问题的求解 p141 ex4 p169 T10 考试内容及分值 4 第七章图与网络分析 10分 了解图与网络的基本知识掌握树的概念熟练掌握求解最小树问题 最短路问题 最大流问题及最小费用最大流问题 p227 T17 T18第八章存贮论 10分 了解存储问题的有关概念掌握解决各类型存储问题的基本原理熟练掌握确定型存贮问题和单周期随机存贮模型 p313 T4 p314 T5 试题类型 选择题或者填空题15分判断题15分分析解答题60分实际问题建模题10分 考点详解 1 简单线性规划模型及其图解法 page10 ex 1 page17 ex 2 例 某工厂在计划期内要安排生产 两种产品 这些产品分别需要在A B C D四种不同的设备上加工 有关数据见表2 1 问应如何安排生产计划 才能得到利润最多 考点详解 2 线性规划的基本概念线性规划的三要素 决策变量 目标函数和约束条件 线性规划与非线性规划 page11 line 5标准形 page19 line 11 对偶形式 page114 page118可行域 可行解 page11 line 1 page12 line 1最优解 最优目标函数值 page12 line1可行域都是凸集 page14 line1 考点详解 3 松驰变量 page15 line6剩余变量 page17 line 4人工变量 page82图解法的灵敏度分析 page19 22对偶价格 page22 line6影子价格 page33 line 10 考点详解 4 线性规划模型 人力资源分配 page39 ex 1 page40 ex 2 生产计划 page42 ex 3 page44 ex 4 下料问题 page46 ex 5 配料问题 page47 ex 6 page49 ex 7 投资问题 page51 ex 8 page172 ex 8 运输问题 page126 ex 1 page134 ex 6 page138 ex 8 选址问题 page165 ex 4 固定成本问题 page168 ex 5 指派问题 page169 ex 6 分布系统设计问题 page171 ex 7 目标规划问题 page194 ex 7 最短路问题 page201 ex 1 背包问题 page214 line3 生产与存储问题 page214 ex 4 例8 某部门现有资金200万元 今后五年内考虑给以下的项目投资 已知 项目A 从第一年到第五年每年年初都可投资 当年末能收回本利110 项目B 从第一年到第四年每年年初都可投资 次年末能收回本利125 但规定每年最大投资额不能超过30万元 项目C 需在第三年年初投资 第五年末能收回本利140 但规定最大投资额不能超过80万元 项目D 需在第二年年初投资 第五年末能收回本利155 但规定最大投资额不能超过100万元 据测定每万元每次投资的风险指数如下表 问 a 应如何确定这些项目的每年投资额 使得第五年年末拥有资金的本利金额为最大 b 应如何确定这些项目的每年投资额 使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小 解 1 确定决策变量 连续投资问题设xij i 1 5 j 1 4 表示第i年初投资于A j 1 B j 2 C j 3 D j 4 项目的金额 这样我们建立如下的决策变量 Ax11x21x31x41x51Bx12x22x32x42Cx33Dx242 目标函数及模型 a Maxz 1 1x51 1 25x42 1 4x33 1 55x24s t x11 x12 200 x21 x22 x24 1 1x11 x31 x32 x33 1 1x21 1 25x12 x41 x42 1 1x31 1 25x22 x51 1 1x41 1 25x32 2 约束条件 第一年 A当年末可收回投资 故第一年年初应把全部资金投出去 于是x11 x12 200 第二年 B次年末才可收回投资 故第二年年初有资金1 1x11 于是x21 x22 x24 1 1x11 第三年 年初有资金1 1x21 1 25x12 于是x31 x32 x33 1 1x21 1 25x12 第四年 年初有资金1 1x31 1 25x22 于是x41 x42 1 1x31 1 25x22 第五年 年初有资金1 1x41 1 25x32 于是x51 1 1x41 1 25x32 B C D的投资限制 xi2 30 i 1 2 3 4 x33 80 x24 100 xi2 30 i 1 2 3 4 x33 80 x24 100 xij 0 i 1 5 j 1 4 b 所设变量与问题a相同 目标函数为风险最小 有Minf x11 x21 x31 x41 x51 3 x12 x22 x32 x42 4x33 5 5x24在问题a的约束条件中加上 第五年末拥有资金本利在330万元 的条件 于是模型如下 Minf x11 x21 x31 x41 x51 3 x12 x22 x32 x42 4x33 5 5x24s t x11 x12 200 x21 x22 x24 1 1x11 x31 x32 x33 1 1x21 1 25x12 x41 x42 1 1x31 1 25x22 x51 1 1x41 1 25x32 xi2 30 i 1 2 3 4 x33 80 x24 1001 1x51 1 25x42 1 4x33 1 55x24 330 xij 0 i 1 2 3 4 5 j 1 2 3 4 1 某厂按照合同规定每个季度分别提供10 16 26 20台柴油机 该厂各季度的生产能力及生产每台柴油机的成本如下表所示 生产出来的柴油机当季不交货的 每台每积压一季度存储 维护费用为0 1万元 要求在完成合同的情况下 作出使该厂全年生产费用 包括存储 维护费 最小的决策 建立数学模型 2 某公司在今后四个月内需租用仓库堆放物资 每个月所需的仓库面积数字如下表所示当租借合同期限越长时 仓库的租借费用享受的折扣优惠也越大 具体数字如下表所示 租借仓库的合同每月初都可办理 每份合同具体规定租用面积数和期限 因此该厂可根据需要在任何一个月初办理租借合同 且每次办理 可签一份 也可同时签若干份租用面积和租借期限不同的合同 求一个所付出租借费为最小的租借方案 建立该问题的模型 3 一个合资食品企业面临某种食品1至4月的生产计划问题 4个月的需求分别为 4600t 3800t 6500t 4200t 目前 1月初 该企业有120个熟练工人 正常工作时每人每月可以完成40t 成本为200元 t 由于市场需求浮动较大 该企业可通过下列方法调节生产 1 利用加班增加生产 但加班生产产品每人每月不能超过10t 加班时成本为300元 t 2 利用库存来调节生产 库存费用为60元 t 月 最大库存能力为1000t 请为该企业构造一个线性规划模型 在满足需求的前提下使四个月的总费用最小 假定该企业在1月初的库存为零 要求4月底的库存为500t 4 现要将一些不同类型的货物装到一条货船上 这些货物的单位重量 单位体积 冷藏要求 可燃性指数都不相同 它们由下表给出 该船可以装载的总重量为420000kg 总体积为45000 可以冷藏的总体积为10000 容许的可燃性指数的总和不能超过750 目标是希望装载的货物取得最大的价值 5 某投资者有50000元可供为期四年的投资 现有下列五个投资机会可供选择 A 在四年内 投资者可在每年年初投资 每年每元投资可获得0 2元利润 每年获利后可将本利重新投资 B 在四年内 投资者应在第一年年初或第三年年初投资 每两年每元投资可获利0 5元 两年后获利 然后可将本利再重新投资 C 在四年内 投资者应在第一年年初投资三年后每元投资可获利0 8元 获利后可将本利重新投资 这项投资最多不超过25000元 D 在四年内 投资者应在第二年年初投资 两年后每元投资可获利0 6元 获利后可将本利重新投资 这项投资最多不超过10000元 E 在四年内 投资者应在第一年年初投资 四年后每元获利1 7元 这项投资最多不超过20000元 投资者在四年内应如何投资 四年内所获利润最大 写出问题的线性规划模型 不求解 考点详解 5 单纯形法的基本概念和方法步骤 基 基向量 非基向量 基变量 非基变量 page68 基本可行解 page69 line 1 初始基本可行解 page71 line7 最优性检验的依据 检验数 page71 最优解判别定理 page71 line 9 入基变量的确定 page72 出基变量的确定 page73 13 单纯形表格形式 page79 考试题型 page96 exe 3 考点详解 6 线性规划解的四种情况及其判别无可行解 page86 ex 1 page88 line2 无界解 page88 ex 2 page89 line 15 无穷多最优解 page89 ex 3 page92 li