运筹学(绝密) 绪论与图解法

1、管理管理运筹学运筹学 (OR) ( (美美Operations Research)Operations Research) ( (英英 Operational Research)Operational Research) 学时数：64学时 教材： 运筹学教材编写组编运筹学，清华大学出版社 参考书： 其它版本的管理运筹学； 胡运权主编运筹学教程清华大学出版社； 牛映武主编运筹学 西安交通大学出版社； 成绩评定： 作业：15分； 考勤：15分； 期中考试：10分 期末考试：60分 1 1 运筹学的产生和发展运筹学的产生和发展 运筹学是运用筹划的科学，运筹学是运用筹划的科学， 原意原意“作战研究作战

2、研究”或或“运用研究运用研究”。 一、一、 绪论绪论 1.1 运筹学产生运筹学产生 运筹学的三个来源是军事、管理和经济运筹学的三个来源是军事、管理和经济 军事 特点是：定量化、系统化方法迅速发展；采集真实的实 际数据；多学科密切协作；解决方法渗透物理学的思想。 （1）波得塞（Bawdsey)雷达站的研究 1939年 任务：如何最好地运用空军及新发明的雷达保卫国家 （2）Morse小组领导的运筹学小组 目标：打破德军对英吉利海峡的封锁 建议：用飞机代替舰艇投掷水雷，起爆深度由100米改为25米， 当敌舰刚下潜时攻击； 运送物资的船队及护卫舰的编队由小规模、多批次改为大规模 、少批次。丘吉尔采纳了

3、建议 （3）英国战斗机援法 德军突破马奇诺防线，法军节节败退，英军参与抗德。英军的 战机均在法国上空与德军作战，指挥维护在法国。法国请求增 援10中队，邱吉尔同意。 但运筹学小组认为：按现在的方式，英军的援法战机两周内会 全军覆灭；不增加战机，而应以英国本土为基地与德军战斗， 使局面大为改观。 经济 冯诺意曼（Von.neumann)对策论与经济行为 管理 康托洛维齐（Kantorovich) 生产配置问题、原材料的合理利用、运输问题等 生产组织与计划中的数学方法 1.1 运筹学的发展运筹学的发展 运筹学的发展大概分三个阶段运筹学的发展大概分三个阶段 第一个阶段第一个阶段蓬勃生长期蓬勃生长期

4、3939年英国成立了世界上第一个运筹学工作小组，年英国成立了世界上第一个运筹学工作小组， 从事防空预警系统的研制（研究如何合理运用雷达）从事防空预警系统的研制（研究如何合理运用雷达） 19391939年前苏联的康托洛维奇提出类似线性规划模型年前苏联的康托洛维奇提出类似线性规划模型 19601960年年最佳资源利用的经济计算最佳资源利用的经济计算，获诺贝尔奖，获诺贝尔奖 19471947年美国数学家，提出线性规划模型及单纯形算法年美国数学家，提出线性规划模型及单纯形算法 4242年美国成立运筹学工作小组，研究战斗行动效能，年美国成立运筹学工作小组，研究战斗行动效能， 行动方式行动方式 战争结束，

5、战争结束，MoresMores和和KimballKimball合著第一部运筹学专著合著第一部运筹学专著“运筹运筹 学的方法学的方法” 战后，运筹学的应用领域从军事扩展到其它各领域战后，运筹学的应用领域从军事扩展到其它各领域 19481948年英国成立运筹学学会年英国成立运筹学学会 19521952年美国成立运筹学学会年美国成立运筹学学会 19561956年法国成立运筹学学会年法国成立运筹学学会 19591959年英、美、法成立运筹学联合会年英、美、法成立运筹学联合会 第二阶段第二阶段危机期危机期 六、七十年代六、七十年代 第三阶段第三阶段运筹学发展的正确之路运筹学发展的正确之路 理念更新、实践

6、为本、学科交融理念更新、实践为本、学科交融 我国运筹学的发展我国运筹学的发展 2 2 运筹学的释义运筹学的释义 运筹学具有如下的性质特点 （1）运筹学是一门应用科学）运筹学是一门应用科学 (2) 运筹学的目的是寻找最佳解决问题的方案，运筹学的目的是寻找最佳解决问题的方案， 为决策者的最优决策提供依据为决策者的最优决策提供依据 (3) 以数学为基础提供定量分析以数学为基础提供定量分析 （4）以计算机为手段）以计算机为手段 （5） 以软科学研究软系统以软科学研究软系统 （6） 多学科专家集体协作研究多学科专家集体协作研究 由一支综合性的队伍，采用科学的方法，为一些涉及到有机 系统（人-机）的控制系

7、统问题提供解答，为该系统的总目标服务 的学科。钱学森 运用科学方法来解决工业、商业、政府、国防等部门里有关 人力、机器、物资、金钱等大型系统的指挥或管理中所出现的 复杂问题的一门学科。其目的是“帮助管理者以科学方法确定 其方针和行动”英国运筹学会 运筹学是应用系统的、科学的、数学分析的方法，通过建模、 检验和求解数学模型而获得最优决策的科学。近代运筹学工 作者 运筹学的定义运筹学的定义 执行部门对所控制的业务作出决策提供数量上的科学或利用 所应用科学，执行部门对其所属业务作出决策提供数量上依据的 一门科学。Morse 规划论规划论线性规划线性规划、目标规划、非线、目标规划、非线 性规划、性规划

8、、整数规划整数规划、动态规划动态规划、组合规划等、组合规划等 图与网络图与网络 存储论存储论 排队论排队论 对策论对策论 决策论决策论 仿真仿真 马尔科夫过程马尔科夫过程 可靠性可靠性 多目标规划多目标规划 3 3 运筹学的分支运筹学的分支 3 3 运筹学的工作步骤运筹学的工作步骤 (1) 提出和形成问题。提出和形成问题。即要弄清问题的目标，可能的约束，问 题的可控变量以及有关参数； (2) 建立模型。建立模型。即把问题中可控变量、参数和目标与约束之间 的关系用一定的模型表示出来； (3) 求解。求解。用各种手段( 主要是数学方法，也可用其他方法 )将 模型求解。解可以是最优解、次优解、满意解

9、。复杂模型的求 解需用计算机，解的精度要求可由决策者提出； (4) 解的检验。解的检验。首先检查求解步骤和程序有无错误，然后检查 解是否反应现实问题； (5) 解的控制。解的控制。通过控制解的变化过程决定对解是否要作一定 的改变； (6) 解的实施。解的实施。是指将解用到实际中必须考虑到实施的问题， 如向实际部门讲清楚用法、在实施中可能产生的问题和修改。 4 4 本课程的要求本课程的要求 本课程的授课对象是管理科学与工程类及交通运输类专业本课程的授课对象是管理科学与工程类及交通运输类专业 本科生，属管理类专业技术基础必修课。本科生，属管理类专业技术基础必修课。 学生通过学习该课程，应了解管理运

10、筹学对优化决策问题进学生通过学习该课程，应了解管理运筹学对优化决策问题进 行定量研究的特点，行定量研究的特点， 理解理解 线性规划、整数规划、动态规划、图与线性规划、整数规划、动态规划、图与 网络、排队论和库存论网络、排队论和库存论 等分支的基本优化等分支的基本优化原理，掌握原理，掌握 其中常用的其中常用的 模型和算法模型和算法，具有一定的建模能力。具有一定的建模能力。 先修课程主要为先修课程主要为线性代数和概率统计线性代数和概率统计，学生对它们的掌握程，学生对它们的掌握程 度直接影响本课程的学习，所以要求学生课前要做必要的复习。度直接影响本课程的学习，所以要求学生课前要做必要的复习。 学习方

11、法：理解、掌握基本理论和方法的基础上，适当作些学习方法：理解、掌握基本理论和方法的基础上，适当作些 习题。习题。 二二. 线性规划线性规划 (LP ) ( Linear Programming) 第一章第一章 线性规划与单纯形法线性规划与单纯形法 1947年由美国空军G.B.Dantzig提出。 本部分是课程的最重要部分 本节重点：本节重点： 线性规划模型的特点线性规划模型的特点 线性规划解的存在情况线性规划解的存在情况 线性规划标准型线性规划标准型 线性规划解的基本概念线性规划解的基本概念（特别是基解和基可行解）（特别是基解和基可行解） 1 线性规划问题及其数学模型线性规划问题及其数学模型

12、11 问题的提出问题的提出 例例 1 1某工厂计划期内要安排生产、两种产品，某工厂计划期内要安排生产、两种产品， 已知生产单位产品所需的设备台时和已知生产单位产品所需的设备台时和A A、B B两种原材料的两种原材料的 消耗、以及可获利润如表所示，问应如何安排计划使该消耗、以及可获利润如表所示，问应如何安排计划使该 工厂获利最多？工厂获利最多？ 可利用资源 设备 原材料 A 原材料 B 1 4 0 2 0 4 8 台时 16kg 12kg 利润23 ？元 设设 x1、x2分别表示计划期内产品分别表示计划期内产品、的产量，、的产量， 建立数学模型：建立数学模型： 设备台时设备台时 约束条件约束条件

13、 s.t. x1 + 2x2 8 原材料原材料 A (Subject to) 4 x1 16 原材料原材料 B 4 x2 12 产品产量产品产量 x1，x2 0 可利用资源 设备 原材料 A 原材料 B 1 4 0 2 0 4 8 台时 16kg 12kg 利润23 ？元 利润最大利润最大 目标函数目标函数 max max z z = 2 = 2x1+ 3x2 例2 某工厂用钢与橡胶生产3种产品A、B、C，有关资料如下表 40 45 24 3 3 2 2 3 1 A B C 单位产品利润单位产品橡胶量单位产品钢消耗量产品 已知每天可获得100单位的钢和120单位橡胶，问每天生产A、B、 C各多

14、少使总利润最大？ 解解：设x1，x2， x3分别为A、B、C日产量，则有 约束条件 2 x1 + 3x2 + x3 100 3x1 + 3x2 + 2x3 120 x10，x20， x30称x1，x2 ，x30为决策变量 目标函数： max z=40 x1+45x2 +24x3 例例 3靠近某河流有两个化工厂（见图） ，流经第一化工厂靠近某河流有两个化工厂（见图） ，流经第一化工厂 的河流流量为每天的河流流量为每天 500 万万 m3， 在两个工厂之间有一条流量为， 在两个工厂之间有一条流量为 每天每天 200 万万 m3的支流。的支流。 第一化工厂每天排放含有某种有害物第一化工厂每天排放含有

15、某种有害物 质的工业污水质的工业污水 2 万万 m3，第二化工厂每天排放这种工业污水，第二化工厂每天排放这种工业污水 1. .4 万万 m3。从第一化工厂排出的工业污水流到第二化工厂以从第一化工厂排出的工业污水流到第二化工厂以 前，有前，有 20% %可以自然净化。可以自然净化。根据环保要求，河流中工业污水根据环保要求，河流中工业污水 的含量不应大于的含量不应大于 0. .2 2% %。 这两个工厂都需各自处理一部分工业这两个工厂都需各自处理一部分工业 污水。污水。第一化工厂处理工业污水的成本是第一化工厂处理工业污水的成本是 10001000 元元/ /万万 m m 3 3，第 ，第 二化工厂

16、处理工业污水的成本是二化工厂处理工业污水的成本是 800800 元元/ /万万 m m 3 3。 。 现在要问在满现在要问在满 足环保要求的足环保要求的条件下，每厂各应处理多少工业污水，使这两条件下，每厂各应处理多少工业污水，使这两 个工厂总的处理工业污水费用最小。个工厂总的处理工业污水费用最小。 2万m3 1.4万m3 设设 x1、x2 分别为第一、第二化工厂每天处理的工业污水量。分别为第一、第二化工厂每天处理的工业污水量。 约束条件：约束条件： 第一化工厂到第二化工厂之间的污水含量要不大于第一化工厂到第二化工厂之间的污水含量要不大于 0. .2 2% % (2 -(2 - x1) / 50

17、0 2 / 1000 流经第二化工厂后，河流中的污水含量仍不大于流经第二化工厂后，河流中的污水含量仍不大于 0. .2 2% % 0.0. 8(2 -8(2 - x1) + ( (1. .4-4- x2) / 700 2 / 1000 污水处理量限制污水处理量限制 x1 2，x2 1. .4 4，x1 0，x2 0 目标函数：目标函数： 要求两厂用于处理工业污水的费用最小要求两厂用于处理工业污水的费用最小 min z = 1000 x1+800 x2 2万m3 1.4万m3 整理得数学模型：整理得数学模型： 目标函数目标函数 min min z z = 1000 = 1000 x1+ 800

18、x2 约束条件约束条件 s.t. x1 1 0. .8 8 x1 + x2 1. .6 6 x1 2 x2 1. .4 4 x1 0，x2 0 线线性性规规划划问问题题的的共共同同特特征征 （模模型型的的三三要要素素） 每每一一个个问问题题都都用用一一组组决决策策变变量量(x1，x2，xn) 表表示示某某一一方方案案； 这这组组决决策策变变量量的的值值就就代代表表一一个个具具体体方方案案。 一一般般这这些些变变量量取取值值都都是是非非负负的的。 存存在在一一定定的的约约束束条条件件， 这这些些约约束束条条件件可可以以用用一一组组 线线性性等等式式或或线线性性不不等等式式来来表表示示。 都都有有

19、一一个个要要求求达达到到的的目目标标， 它它可可用用决决策策变变量量的的线线 性性函函数数（称称为为目目标标函函数数）来来表表示示。按按问问题题的的不不同同，要要求求 目目标标函函数数实实现现最最大大化化或或最最小小化化。 线性规划模型的一般形式为：线性规划模型的一般形式为： max(min) z =c1x1 + c2x2 + cnxn (1.1) s.t. a11x1 + a12x2 + a1nxn ( = , ) b1 a21x1 + a22x2 + a2nxn ( = , ) b2 (1 (1.2)2) am1x1 + am2x2 + amnxn ( = , ) bm x1，x2，xn

20、0 (1.3) 求解线性规划问题的任务是求解线性规划问题的任务是：在满足在满足(1.2)、(1.3) 的所有的所有(x1， x2，xn)（可行解可行解）中求出使）中求出使(1.1)达到最大达到最大(小小)z 值的决策变量值值的决策变量值 (x1*，x2*，xn*)（最优解最优解） 。） 。 12 图图解解法法 只只有有两两个个决决策策变变量量的的问问题题可可用用图图解解 法法。图图解解法法有有助助于于理理解解线线性性规规划划问问题题的的求求 解解原原理理。 例例 1 max max z z = 2 = 2x1 + 3x2 s.t. x1 + 2 x2 8 4 x1 16 4 x2 12 x1，

21、x2 0 解解 法法 ： 1 1 o o. .建立平面直角坐标系； 建立平面直角坐标系； 2 2 o o. .找 找出出表表示示每每个个约约束束的的半半平平面面， 所所有有半半平平面面的的交交集集是是可可行行域域 （全全 体体可可行行解解的的集集合合） ； 3 3 o o. .画 画出出目目标标函函数数的的等等值值线线 ； max max z z = 2 = 2x1+ 3x2 s.t. x1 + 2 x2 8 4 x1 16 4 x2 12 x1，x2 0 x1 x2 0 4 Q2(4,2) Q1 Q3 Q4 4x1=16 4x2=12 x1+2x2=8 2x1+3x2=0 3 Q2 4o.向着目标函数的优化方向平移等值线，直至得到等值线与向着目标函数的优化方向平移等值线，直至得到等值线与 可行域的最后交点，这种点就对应最优解。可行域的最后交点，这种点就对应最优解。 线性规划问题解的存在情况：线性规划问题解的存在情况： (1)(1)存在唯一