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

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 运筹学的发展运筹学的发展运筹学的发展大概分三个阶段运筹学的发展大概分三个阶段第一个阶段第一个阶段蓬勃生长期蓬勃生长期3939年英国成立了世界上第一个运筹学工作小组，年英国成立了世界上第一个运筹学工作小

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

5、学专著“运筹运筹学的方法学的方法”战后，运筹学的应用领域从军事扩展到其它各领域战后，运筹学的应用领域从军事扩展到其它各领域19481948年英国成立运筹学学会年英国成立运筹学学会19521952年美国成立运筹学学会年美国成立运筹学学会19561956年法国成立运筹学学会年法国成立运筹学学会19591959年英、美、法成立运筹学联合会年英、美、法成立运筹学联合会 第二阶段第二阶段危机期危机期六、七十年代六、七十年代第三阶段第三阶段运筹学发展的正确之路运筹学发展的正确之路理念更新、实践为本、学科交融理念更新、实践为本、学科交融我国运筹学的发展我国运筹学的发展2 2 运筹学的释义运筹学的释义运筹学具

6、有如下的性质特点（1）运筹学是一门应用科学）运筹学是一门应用科学(2) 运筹学的目的是寻找最佳解决问题的方案，运筹学的目的是寻找最佳解决问题的方案， 为决策者的最优决策提供依据为决策者的最优决策提供依据(3) 以数学为基础提供定量分析以数学为基础提供定量分析（4）以计算机为手段）以计算机为手段 （5） 以软科学研究软系统以软科学研究软系统（6） 多学科专家集体协作研究多学科专家集体协作研究 由一支综合性的队伍，采用科学的方法，为一些涉及到有机系统（人-机）的控制系统问题提供解答，为该系统的总目标服务的学科。钱学森 运用科学方法来解决工业、商业、政府、国防等部门里有关人力、机器、物资、金钱等大型

7、系统的指挥或管理中所出现的复杂问题的一门学科。其目的是“帮助管理者以科学方法确定其方针和行动”英国运筹学会 运筹学是应用系统的、科学的、数学分析的方法，通过建模、检验和求解数学模型而获得最优决策的科学。近代运筹学工作者运筹学的定义运筹学的定义 执行部门对所控制的业务作出决策提供数量上的科学或利用所应用科学，执行部门对其所属业务作出决策提供数量上依据的一门科学。Morse 规划论规划论线性规划线性规划、目标规划、非线、目标规划、非线性规划、性规划、整数规划整数规划、动态规划动态规划、组合规划等、组合规划等 图与网络图与网络 存储论存储论 排队论排队论 对策论对策论 决策论决策论 仿真仿真 马尔科

8、夫过程马尔科夫过程 可靠性可靠性 多目标规划多目标规划 3 3 运筹学的分支运筹学的分支3 3 运筹学的工作步骤运筹学的工作步骤(1) 提出和形成问题。提出和形成问题。即要弄清问题的目标，可能的约束，问题的可控变量以及有关参数；(2) 建立模型。建立模型。即把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示出来； (3) 求解。求解。用各种手段( 主要是数学方法，也可用其他方法 )将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机，解的精度要求可由决策者提出；(4) 解的检验。解的检验。首先检查求解步骤和程序有无错误，然后检查解是否反应现实问题；(5) 解的控制。解

9、的控制。通过控制解的变化过程决定对解是否要作一定的改变； (6) 解的实施。解的实施。是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清楚用法、在实施中可能产生的问题和修改。4 4 本课程的要求本课程的要求本课程的授课对象是管理科学与工程类及交通运输类专业本课程的授课对象是管理科学与工程类及交通运输类专业本科生，属管理类专业技术基础必修课。本科生，属管理类专业技术基础必修课。 学生通过学习该课程，应了解管理运筹学对优化决策问题进学生通过学习该课程，应了解管理运筹学对优化决策问题进行定量研究的特点，行定量研究的特点， 理解理解 线性规划、整数规划、动态规划、图与线性规划、整数规划、动态规划

10、、图与网络、排队论和库存论网络、排队论和库存论 等分支的基本优化等分支的基本优化原理，掌握原理，掌握 其中常用的其中常用的模型和算法模型和算法，具有一定的建模能力。具有一定的建模能力。 先修课程主要为先修课程主要为线性代数和概率统计线性代数和概率统计，学生对它们的掌握程，学生对它们的掌握程度直接影响本课程的学习，所以要求学生课前要做必要的复习。度直接影响本课程的学习，所以要求学生课前要做必要的复习。 学习方法：理解、掌握基本理论和方法的基础上，适当作些学习方法：理解、掌握基本理论和方法的基础上，适当作些习题。习题。 二二. 线性规划线性规划 (LP )( Linear Programming)

11、第一章第一章 线性规划与单纯形法线性规划与单纯形法1947年由美国空军G.B.Dantzig提出。本部分是课程的最重要部分本节重点：本节重点：线性规划模型的特点线性规划模型的特点线性规划解的存在情况线性规划解的存在情况线性规划标准型线性规划标准型线性规划解的基本概念线性规划解的基本概念（特别是基解和基可行解）（特别是基解和基可行解）1 线性规划问题及其数学模型线性规划问题及其数学模型11 问题的提出问题的提出 例例 1 1某工厂计划期内要安排生产、两种产品，某工厂计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时和已知生产单位产品所需的设备台时和A A、B B两种原材料的两种原材料的

12、消耗、以及可获利润如表所示，问应如何安排计划使该消耗、以及可获利润如表所示，问应如何安排计划使该工厂获利最多？工厂获利最多？可利用资源 设备 原材料 A 原材料 B140204 8 台时 16kg 12kg 利润23 ？元设设 x1、x2分别表示计划期内产品分别表示计划期内产品、的产量，、的产量， 建立数学模型：建立数学模型： 设备台时设备台时 约束条件约束条件 s.t. x1 + 2x2 8 原材料原材料 A (Subject to) 4 x1 16 原材料原材料 B 4 x2 12 产品产量产品产量 x1，x2 0 可利用资源 设备 原材料 A 原材料 B140204 8 台时 16kg

13、12kg 利润23 ？元利润最大利润最大 目标函数目标函数 max max z z = 2 = 2x1+ 3x2例2 某工厂用钢与橡胶生产3种产品A、B、C，有关资料如下表404524332231 A B C单位产品利润单位产品橡胶量单位产品钢消耗量产品已知每天可获得100单位的钢和120单位橡胶，问每天生产A、B、C各多少使总利润最大？解解：设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

14、 例例 3靠近某河流有两个化工厂（见图） ，流经第一化工厂靠近某河流有两个化工厂（见图） ，流经第一化工厂的河流流量为每天的河流流量为每天 500 万万 m3， 在两个工厂之间有一条流量为， 在两个工厂之间有一条流量为每天每天 200 万万 m3的支流。的支流。 第一化工厂每天排放含有某种有害物第一化工厂每天排放含有某种有害物质的工业污水质的工业污水 2 万万 m3，第二化工厂每天排放这种工业污水，第二化工厂每天排放这种工业污水1. .4 万万 m3。从第一化工厂排出的工业污水流到第二化工厂以从第一化工厂排出的工业污水流到第二化工厂以前，有前，有 20% %可以自然净化。可以自然净化。根据环保

15、要求，河流中工业污水根据环保要求，河流中工业污水的含量不应大于的含量不应大于 0. .2 2% %。 这两个工厂都需各自处理一部分工业这两个工厂都需各自处理一部分工业污水。污水。第一化工厂处理工业污水的成本是第一化工厂处理工业污水的成本是 10001000 元元/ /万万 m m3 3，第，第二化工厂处理工业污水的成本是二化工厂处理工业污水的成本是 800800 元元/ /万万 m m3 3。 现在要问在满现在要问在满足环保要求的足环保要求的条件下，每厂各应处理多少工业污水，使这两条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。个工厂总的处理工业污水费用最小。 2万m3

16、1.4万m3 设设 x1、x2 分别为第一、第二化工厂每天处理的工业污水量。分别为第一、第二化工厂每天处理的工业污水量。约束条件：约束条件： 第一化工厂到第二化工厂之间的污水含量要不大于第一化工厂到第二化工厂之间的污水含量要不大于 0. .2 2% % (2 -(2 - x1) / 500 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

17、0目标函数：目标函数： 要求两厂用于处理工业污水的费用最小要求两厂用于处理工业污水的费用最小 min z = 1000 x1+800 x22万m31.4万m3整理得数学模型：整理得数学模型：目标函数目标函数 min min z z = 1000 = 1000 x1+ 800 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)表表示示某某一一方方案案； 这这组

18、组决决策策变变量量的的值值就就代代表表一一个个具具体体方方案案。一一般般这这些些变变量量取取值值都都是是非非负负的的。 存存在在一一定定的的约约束束条条件件， 这这些些约约束束条条件件可可以以用用一一组组线线性性等等式式或或线线性性不不等等式式来来表表示示。 都都有有一一个个要要求求达达到到的的目目标标， 它它可可用用决决策策变变量量的的线线性性函函数数（称称为为目目标标函函数数）来来表表示示。按按问问题题的的不不同同，要要求求目目标标函函数数实实现现最最大大化化或或最最小小化化。 线性规划模型的一般形式为：线性规划模型的一般形式为： max(min) z =c1x1 + c2x2 + cnx

19、n (1.1) s.t. a11x1 + a12x2 + a1nxn ( = , ) b1 a21x1 + a22x2 + a2nxn ( = , ) b2 (1 (1.2)2) am1x1 + am2x2 + amnxn ( = , ) bm x1，x2，xn 0 (1.3) 求解线性规划问题的任务是求解线性规划问题的任务是：在满足在满足(1.2)、(1.3) 的所有的所有(x1，x2，xn)（可行解可行解）中求出使）中求出使(1.1)达到最大达到最大(小小)z 值的决策变量值值的决策变量值(x1*，x2*，xn*)（最优解最优解） 。） 。12 图图解解法法 只只有有两两个个决决策策变变量

20、量的的问问题题可可用用图图解解法法。图图解解法法有有助助于于理理解解线线性性规规划划问问题题的的求求解解原原理理。 例例 1 max max z z = 2 = 2x1 + 3x2 s.t. x1 + 2 x2 8 4 x1 16 4 x2 12 x1，x2 0 解解 法法 ：1 1o o. .建立平面直角坐标系；建立平面直角坐标系； 2 2o o. .找找出出表表示示每每个个约约束束的的半半平平面面， 所所有有半半平平面面的的交交集集是是可可行行域域 （全全体体可可行行解解的的集集合合） ； 3 3o o. .画画出出目目标标函函数数的的等等值值线线 ； max max z z = 2 = 2x1+ 3x2s.t. x1 + 2 x2 8 4 x1 16 4 x2 12 x1，x2 0 x1x204Q2(4,2)Q1Q3Q44x1=164x2=12 x1+2x2=82x1+3x2=03Q24o.向着目标函数的优化方向平移等值线，直至得到等值线与向着目标函数的优化方向平移等值线，直至得到等值线与可行域的最后交点，这种点就对应最优解。可行域的最后交点，这种点就对应最优解。 线性规划问题解的存在情况：线性规划