关 键 词：

人大 经典 讲义 运筹学 ppt 非常好 一份

资源描述：

运 筹 学 1.绪论 2.线性规划建模及单纯形法 3.线性规划问题的对偶与灵敏度分析 4.运输问题 5.动态规划 6.排队论 7.决策分析 8.图与网络分析 2 运 筹 学 中国人民大学 2010.10 第一章 绪 论 运筹学概况简述 运筹学 (Operations Research) 直译为“运作研究”。 运筹学是运用科学的方法 (如 分析、试验、量化等 )来决定如何 最佳地运营和设计各种系统的一 门学科 。 运筹学概况简述 运筹学能够对经济管理系统中 的人力、物力、财力等资源进行统 筹安排，为决策者提供有依据的最 优方案，以实现最有效的管理。 通常以最优、最佳等作为决策 目标，避开最劣的方案。 运筹学在工商管理中的应用 生产计划 ： 生产作业的计划、 日程表的编排、合理下料、配料问 题、物料管理等。 库存管理 ： 多种物资库存量 的管理，库存方式、库存量等。 运输问题 ： 确定最小成本的 运输线路、物资的调拨、运输工具 的调度以及建厂地址的选择等 。 运筹学在工商管理中的应用 人事管理 ：对人员的需求和使 用的预测，确定人员编制、人员合 理分配，建立人才评价体系等。 市场营销 ：广告预算、媒介选择、 定价、产品开发与销售计划制定等。 运筹学在工商管理中的应用 财务和会计 ：包括预测、贷款、 成本分析、定价、证券管理、现金 管理等。 其他 ： 设备维修、更新，项 目选择、评价，工程优化设计与管 理等。 运筹学的产生和发展 运筹学思想的出现可以追溯到很 早 —―田忌齐王赛马 ” （对策论）、 孙 子兵法 等都体现了优化的思想。 “ Operational Research‖这一名 词最早出现在第二次世界大战期间 — — 美、英等国家的作战研究小组为了 解决作战中所遇到的许多错综复杂的 战略、战术问题而提出的。 运筹学的产生和发展 战后这些研究成果被应用到生产、 经济领域，并得到迅速发展 ——有关理 论和方法的研究、实践不断深入。 1947年美国数学家丹捷格 (G.B.Dantzig） 提出了求解线性规划的有效方法 ——单 纯形法 。 运筹学的产生和发展 数学对运筹学的作用 ——是有 关理论和方法的研究基础，是建立 运筹学模型的工具。 计算机的发展，促进运筹学的 进一步发展 ——高速、可靠的计算 是运筹学解决问题的基本保障。 运筹学的分支 线性规划 非线性规划 整数规划 动态规划 多目标规划 随机规划 模糊规划等 运筹学的分支 图与网络理 论 存储论 排队论 决策论 对策论 排序与统筹 方法 可靠性理论 等 运筹学方法使用情况 (美 1983) 运筹学方法在中国使用情况 (随机抽样 ) 运筹学的推广应用前景 据美劳工局 1992年统计预测 :社会 对运筹学应用分析人员的需求从 1990 年到 2005年，其增长百分比预测为 73%, 增长速度排到各项职业的前三位 。 运筹学的推广应用前景 结论 : --运筹学在国内或国外的推广应 用前景是非常广阔的。 --工商企业对运筹学应用的需求 是很大的。 --在工商企业推广运筹学方面有 大量的工作要做。 运筹学解决问题的过程 1） 提出问题：认清问题。 2） 寻求可行方案：建模、求解。 3） 确定评估目标及方案的标准或方 法、途径。 4） 评估各个方案：解的检验、灵敏 性分析等。 运筹学解决问题的过程 5） 选择最优方案：决策。 6） 方案实施：回到实践中。 7） 后评估：考察问题是否得到完 满解决。 1） 2） 3）形成问题； 4） 5）分析 问题：定性分析与定量分析相结合，构 成决策。 如何学习运筹学课程 学习运筹学要把 重点 放在分 析、理解有关的概念、思路上。 在自学过程中，应该多向自己提 问，例如一个方法的实质是什么， 为什么这样进行，怎么进行等。 自学时要掌握三个 重要环节 ： 如何学习运筹学课程 1.认真阅读教材和参考资料， 以指定教材为主，同时参考其他有 关书籍。一般每一本运筹学教材都 有自己的特点，但是基本原理、概 念都是一致的。注意主从，参考资 料会帮助你开阔思路，使学习深入。 但是，把时间过多放在参考资料上， 会导致思路分散，不利于学好。 2.要在理解了基本概念和理论的基础上 研究例题，注意例题是为了帮助理解概念、 理论的。作业练习的主要作用也是这样，它 同时还有让你自己检查自己学习的作用。因 此，做题要有信心，要独立完成，不要怕出 错。因为，整个课程是一个整体，各节内容 有内在联系，只要学到一定程度，知识融会 贯通起来，你自己就能够对所做题目的正确 性作出判断。 如何学习运筹学课程 3、 要学会做学习小结。每一节 或一章学完后，必须学会用精炼的语 言来概述该书所讲内容。这样，你才 能够从较高的角度来看问题，更深刻 地理解有关知识和内容。这就称作 “把书读薄”，若能够结合相关参考 文献并深入理解，把相关知识从更深 入、广泛的角度进行论述，则称为 “把书读厚”。 如何学习运筹学课程 24 第二章 线性规划建模及单纯形法 本章内容重点 线性规划模型与解的主要概念 线性规划的单纯形法，线性规 划多解分析 线性规划应用 ——建模 25 1.线性规划的概念 例 2.1:某工厂拥有 A、 B、 C 三种类型 的设备 ， 生产甲 、 乙两种产品 。 每件产品 在生产中需要占用的设备机时数 ， 每件产 品可以获得的利润以及三种设备可利用的 时数如下表所示： 产品甲 产品乙 设备能力 （ h） 设备 A 3 2 65 设备 B 2 1 40 设备 C 0 3 75 利润（元 /件） 1500 2500 26 问题：工厂应如何安排生产可获得最 大的总利润 ？ 解：设变量 xi 为第 i 种 （ 甲 、 乙 ） 产品的生产件数 （ i＝ 1， 2） 。 根据题意 ， 我们知道两种产品的生产受到设备能力 （ 机时数 ） 的限制 。 对设备 A：两种产品 生产所占用的机时数不能超过 65， 于是我 们可以得到不等式： 3 x1 + 2 x2 ≤ 65； 对设备 B：两种产品生产所占用的机 时数不能超过 40， 于是我们可以得到不等 式： 2 x1 + x2 ≤ 40； 1.线性规划的概念 27 对设备 C ：两种产品生产所占用的 机时数不能超过 75， 于是我们可以得到 不等式： 3x2 ≤ 75 ；另外 ， 产品数不可 能为负 ， 即 x1 ,x2 ≥ 0。 同时 ， 我们有一个追求目标 ， 即获 取最大利润 。 于是可写出目标函数 z为相 应的生产计划可以获得的总利润： z = 1500x1 + 2500x2 综合上述讨论 ， 在加工时间以及利 润与产品产量成线性关系的假设下 ， 把 目标函数和约束条件放在一起 ， 可以建 立如下的线性规划模型： 1.线性规划的概念 28 目标函数 Max z =1500x1+2500x2 约束条件 s.t. 3x1 + 2x2 ≤ 65 2x1 + x2 ≤ 40 3x2 ≤ 75 x1 ,x2 ≥ 0 1.线性规划的概念 29 这是一个典型的利润最大化的生 产计划问题 。 其中 ， “ Max‖是英文单 词 “ Maximize‖的缩写 ， 含义为 “ 最 大化 ” ； “ s.t.‖是 “ subject to‖的 缩写 ， 表示 “ 满足于 … ‖。 因此 ， 上 述模型的含义是：在给定条件限制下 ， 求使目标函数 z 达到最大的 x1 ,x2 的取值 。 1.线性规划的概念 30 •一般形式 •目标函数： Max(Min)z = c1x1 + c2x2 + … + cnxn •约束条件： a11x1+a12x2+…+a1nxn≤( =, ≥ ) b1 a21x1+a22x2+…+ a2nxn≤( =, ≥ ) b2 . . . am1x1+am2x2 +…+ amnxn≤( =, ≥ ) bm x1 ， x2 ， … ， xn ≥ 0 1.线性规划的概念 31 •标准形式 •目标函数： Max z = c1x1 + c2x2 + … + cnxn •约束条件： A11x1 + a12x2 + … + a1nxn = b1 a21x1 + a22x2 + … + a2nxn = b2 . . . am1x1 + am2x2 + … + amnxn = bm x 1 ， x2 ， … ， xn ≥ 0 1.线性规划的概念 32 可以看出 ， 线性规划的标准 形式有如下四个特点： 目标最大 化 、 约束为等式 、 决策变量均非 负 、 右端项非负 。 对于各种非标准形式的线性 规划问题 ， 我们总可以通过以下 变换 ， 将其转化为标准形式 : 1.线性规划的概念 33 1.极小化目标函数的问题： 设目标函数为 Min f = c1x1 + c2x2 + … + cnxn 则可以令 z ＝ -f ， 该极小化问 题与下面的极大化问题有相同的最优 解 ， 即 Max z = -c1x1 - c2x2 - … - cnxn 但必须注意 ， 尽管以上两个问题 的最优解相同 ， 但他们最优解的目标 函数值却相差一个符号 ， 即 Min f ＝ - Max z 1.线性规划的概念 34 2、 约束条件不是等式的问题： 设约束条件为 ai1 x1+ai2 x2+ … +ain xn ≤ bi 可以引进一个新的变量 s ， 使它等 于约束右边与左边之差 s =bi–(ai1 x1 + ai2 x2 + … + ain xn ) 显然 ， s 也具有非负约束 ， 即 s≥ 0， 这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn+s = bi 1.线性规划的概念 35 当约束条件为 ai1 x1+ai2 x2+ … +ain xn ≥ bi 时 ， 类似地令 s =(ai1 x1+ai2 x2+ … +ain xn)- bi 显然 ， s 也具有非负约束 ， 即 s≥ 0， 这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn-s = bi 1.线性规划的概念 36 为了使约束由不等式成为等式 而引进的变量 s 称为 “ 松弛变量 ” 。 如果原问题中有若干个非等式约束 ， 则将其转化为标准形式时 ， 必须对 各个约束引进不同的松弛变量 。 1.线性规划的概念 37 例 2.2：将以下线性规划问题转化为标 准形式 Min f = 3.6 x1 - 5.2 x2 + 1.8 x3 s. t. 2.3 x1 + 5.2 x2 - 6.1 x3 ≤ 15.7 4.1 x1 + 3.3 x3 ≥ 8.9 x1 + x2 + x3 = 38 x1 , x2 , x3 ≥ 0 1.线性规划的概念 解：首先 ,将目标函数转换成极大化 ： 令 z= -f = -3.6x1+5.2x2-1.8x3 38 其次考虑约束 ， 有 2个不等式约束 ， 引进 松弛变量 x4， x5 ≥ 0。 于是 ， 我们可以得到以下标准形式的线性 规划问题： Max z = - 3.6 x1 + 5.2 x2 - 1.8 x3 s.t. 2.3x1+5.2x2-6.1x3+x4= 15.7 4.1x1+3.3x3-x5= 8.9 x1+x2+x3= 38 x1 ,x2 ,x3 ,x4 ,x5 ≥ 0 1.线性规划的概念 39 3. 变量无符号限制的问题： 在标准形式中 ， 必须每一个变量均有 非负约束 。 当某一个变量 xj没有非负 约束时 ， 可以令 xj = xj’- xj” 其中 xj’≥0， xj”≥0 即用两个非负变量之差来表示一个无 符号限制的变量 ， 当然 xj的符号取决 于 xj’和 xj”的大小 。 1.线性规划的概念 40 4.右端项有负值的问题： 在标准形式中 ， 要求右端项必须每一 个分量非负 。 当某一个右端项系数为 负时 ， 如 bi<0， 则把该等式约束两 端同时乘以 -1， 得到： -ai1 x1-ai2 x2- … -ain xn = -bi 1.线性规划的概念 41 例 2.3：将以下线性规划问题转化为 标准形式 Min f= -3 x1 + 5 x2 + 8 x3 - 7 x4 s.t. 2 x1 - 3 x2 + 5 x3 + 6 x4 ≤ 28 4 x1 + 2 x2 + 3 x3 - 9 x4 ≥ 39 6 x2 + 2 x3 + 3 x4 ≤ - 58 x1 , x3 , x4 ≥ 0 1.线性规划的概念 42 解：首先 ， 将目标函数转换成极大化： 令 z = -f = 3x1–5x2–8x3+7x4 ； 其次考虑约束 ， 有 3个不等式约 束 ， 引进松弛变量 x5 ,x6 ,x7 ≥0 ； 由于 x2无非负限制 ， 可令 x2=x2’-x2”, 其中 x2’≥0， x2”≥0 ； 由于第 3个约束右端项系数为 -58， 于是把该式两端乘以 -1 。 于是 ， 我们可以得到以下标准形 式的线性规划问题： 1.线性规划的概念 43 Max z = 3x1–5x2’+5x2”–8x3 +7x4 s.t. 2x1–3x2’+3x2”+5x3+6x4+x5= 28 4x1+2x2’-2x2”+3x3-9x4-x6= 39 -6x2’+6x2”-2x3-3x4-x7 = 58 x1 ,x2’,x2”,x3 ,x4 ,x5 ,x6 ,x7 ≥ 0 1.线性规划的概念 44 2.线性规划的图解法 线性规划的图解法 (解的几 何表示 )： 对于只有两个决策变量的 线性规划问题 ， 可以二维直角 坐标平面上作图表示线性规划 问题的有关概念 ， 并求解 。 图解法求解线性规划问题 的步骤如下： 45 2.线性规划的图解法 (1)建立直角坐标系： 分别取决策变量 x1 ,x2 为坐标向量 。 46 2.线性规划的图解法 （ 2） 绘制可行域： 对每个约束 （ 包括非负约束 ） 条 件 ， 作出其约束半平面 （ 不等式 ） 或 约束直线 （ 等式 ） 。 各半平面与直线交出来的区域若 存在 ， 其中的点为此线性规划的可行 解 。 称这个区域为可行集或可行域 。 然后进行下步 。 否则若交为空 ， 那么 该线性规划问题无可行解 。 47 2.线性规划的图解法 （ 3） 绘制目标函数等值线 ， 并移动求解： 目标函数随着取值不同 ， 为一 族相互平行的直线 。 首先 ， 任意给定目标函数一个 值 ， 可作出一条目标函数的等值线 （ 直线 ） ； 然后 ， 确定该直线平移使函数 值增加的方向； 最后 ， 依照目标的要求平移此 直线 。 48 2.线性规划的图解法 结果 若目标函数等值线能够移动 到既与可行域有交点又达到最 优的位置 ， 此目标函数等值线 与可行域的交点即最优解 （ 一 个或多个 ） ， 此目标函数的值 即最优值 。 否则，目标函数等值线与可 行域将交于无穷远处，此时称 无有限最优解。 49 2.线性规划的图解法 例 2.4:某工厂拥有 A、 B、 C 三种 类型的设备 ， 生产甲 、 乙两种产品 。 每件产品在生产中需要占用的设备机 时数 ， 每件产品可以获得的利润以及 三种设备可利用的时数如下表所示： 产品甲 产品乙 设备能力 （ h） 设备 A 3 2 65 设备 B 2 1 40 设备 C 0 3 75 利润（元 /件） 1500 2500 50 2.线性规划的图解法 问题：工厂应如何安排生产可获得 最大的总利润 ？ 用图解法求解 。 解：设变量 xi为第 i种 （ 甲 、 乙 ） 产 品的生产件数 （ i＝ 1， 2） 。 根据前面分 析 ， 可以建立如下的线性规划模型： Max z = 1500 x1 + 2500 x2 s.t. 3x1+ 2x2 ≤ 65 (A) 2x1+ x2 ≤ 40 (B) 3x2 ≤ 75 (C) x1 , x2 ≥ 0 (D, E) 51 2.线性规划的图解法 例题作图（ 1） 按照图解法的步骤： （ 1） 以决策变量 x1 ， x2 为坐标向量 作平面直角坐标系；

内容简介：

-