运 筹 学,Operational Research ( OR ),,主讲人：赵秀娟 单位：北京邮电大学经济管理学院信息系统中心 电子邮箱：xjzhao@ ：18618195600 研究方向：优化决策、经济评价方法、金融分析与决策,2011年12月出版,目 录,绪 论 第一章 线性规划 第二章 对偶理论与灵敏度分析 第三章 运输问题 第四章 整数规划 第五章 动态规划 第六章 图与网路分析 第七章 随机服务理论概述 第八章 生灭服务系统 第九章 一般服务系统 第十章 存储理论 第十一章 网络计划方法,绪 论,一、运筹学的起源与发展 二、运筹学的定义和主要研究分支 三、运筹学的特点及研究对象 四、运筹学解决问题的方法步骤 五、运筹学与其他学科的关系,夫运筹帷幄之中， 决胜千里之外运筹学简史,中国古代的运筹学思想 田忌赛马 丁渭修皇宫 候叔献治水,,一、运筹学的起源与发展,起源于二次大战的一门新兴交叉学科 与作战问题相关 如雷达的设置、运输船队的护航、反潜作战中深水炸弹的深度、飞行员的编组、军事物资的存储等 英国称为 Operational Research 美国称为 Operations Research 战后在经济、管理和机关学校及科研单位继续研究 1952年，Morse 和 Kimball出版《运筹学方法》 1948年英国首先成立运筹学会 1952年美国成立运筹学会 1959年成立国际运筹学联合会(IFORS) 我国于1982年加入IFORS，并于1999年8月组织了第15届大会,一、运筹学的起源与发展,1、中国运筹学会简介 50年代中期，我国著名科学家钱学森、许国志等教授将运筹学从西方引入国内。
1980年4月，中国数学会运筹学分会成立1991年，中国运筹学会成立历届学会理事长有，华罗庚、越民义，徐光辉，章祥荪，袁亚湘（现任） 2、中国系统工程学会简介 1、1979年由钱学森、宋健、关肇直、许国志等21名专家、学者共同倡议并筹备1980年11月18日在北京正式成立 第一届理事会理事长关肇直，第二、三届理事长许国志第四、五届理事长顾基发、第六届理事长陈光亚、第七届理事长汪寿阳（现任） 3、运筹学、系 统工程 主要研究人员构成 1）数学：如华罗庚、越民义，徐光辉，章祥荪，袁亚湘，许国志，顾基发等； 2）控制论：张仲俊，刘豹，陈珽，郑维敏，赵纯均，陈剑等 3）管理等专业相关教学、科研技术人员,一、运筹学的起源与发展,4、相关研究机构和高校 1）中国科学院数学与系统科学研究院应用数学研究所 2）中国科学院数学与系统科学研究院应用数学研究所 3）哈工大：胡运权，黄梯云，钱国明等 4）天津大学：刘豹，顾培亮，张维，杜 纲等 5）西安交大：汪应洛，席酉民等 6）上海交大：张仲俊，王浣尘等 7）清华大学：郑维敏，赵纯均，陈剑等； 8）大连理工：王众托，胡祥培等 9）北航：顾昌耀，黄海军等 10）北理工 ：吴沧浦，吴祈宗，张强等,12,二、运筹学的定义和主要研究分支,运筹学的定义 为决策机构对所控制的业务活动作决策时，提供以数量为基础的科学方法——Morse 和 Kimball 运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题，其方法是发展一个科学的系统模式，并运用这种模式预测，比较各种决策及其产生的后果，以帮助主管人员科学地决定工作方针和政策——英国运筹学会 运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理——中国百科全书 现代运筹学涵盖了一切领域的管理与优化问题，称为 Management Science,13,二、运筹学的定义和主要研究分支,运筹学的分支 数学规划：线性规划、非线性规划、整数规划、动态规划、目标规划等 图论与网路理论 随机服务理论：排队论 存储理论 网络计划方法 决策理论 对策论 系统仿真：随机模拟技术、系统动力学 可靠性理论 金融工程,引例,,例1： 某工厂在生产过程中需要使用浓度为80%的硫酸100吨，而市面上只有浓度为30%，45%，73%，85%，92%的硫酸出售，每吨的价格分别为400、700、1400、1900和2500元。
问：采用怎样的购买方案，才能使所需费用最小？,王经理花费12000元购买了一台微型车，年度维护费用取决于年初时汽车的役龄，如表示为避免使用旧车会带来较高的维护费用，王经理可选择卖掉旧车而购买新车使用的策略，旧车的售价如表示为简化计算，假定任何时刻购买新车都需花费12000元，王经理的目标是使净费用最小净费用=购置费+维护费-卖旧车收入）,,费用单位：元,引例,若你在俱乐部玩掷骰子的游戏，两枚骰子同时掷，胜负取决于出现的点数之和两枚骰子之和可能212若点数为2，你就损失10元，若点数为7或11，你就赢W元；若出现其它点数，你就损失1元问：W为多大时，这个游戏才能对你有吸引力？,引例,17,三、运筹学的特点及研究对象,运筹学的特点： 1)优化 以整体最优为目标，从系统的观点出发，力图以整个系统最佳的方式来协调各部门之间的利害冲突，从而求出问题的最优解所以运筹学可看成是一门优化技术，为解决各类问题提供优化方法 2定量 为所研究的问题提供定量的解决方案如采用运筹学研究资源分配问题时，其求解结果是一个定量的最优资源分配方案 运筹学的研究对象： 来自生产管理过程中的具体问题，如资源分配、物资调度，生产计划与控制等。
运筹学模型,特点： 系统的整体观念 多学科的综合 以及模型方法的应用 优点： 1 事前分析、减少失误 2 符号语言、便于交流 3 抽象反映实际、突出共性,例：,,,,,2a,,,,,,,,x,用一块边长为2a的正方形铁皮，四角剪去相等小正方形后将四边折起做一个铁盒，问：如何剪能使做成的盒子体积最大？,,,,,底,,,,,,,图像模型, 模型的概念：按一定规则完成的对现实的抽象 模型的形式： （1）实物模型：以实体描述对象 （2）图像模型：以图示描述对象 （3）数学模型：以数学符号和表达式完成的对现实的抽象 模型的建立：实际问题抽象为数学表达式的过程称为建模运筹学模型,数 学 模 型,设 剪掉的小正方形的边长为x，则该问题等同于,求 max V=(2a-2x)2 x 在满足 2x2a x0,,V所做成的盒子的体积运筹学模型的分类,（1）按表达事物的数学特点：线性规划、整数规划、非线性规划等；,（2）按特定专题用途：运输模型、分配模型、存储模型、投入产出模型、排队模型等；,（3）按研究对象：能源模型、教育模型、人口模型、投资模型、宏观经济模型运筹学 Operations ResearchO.R 管理科学 Management Science M.S,管理内容核心问题：正确决策 管理方法核心问题：科学性；艺术性 定性决策：方向性、战略性 定量决策：数量上、战术上,24,四、运筹学解决问题的方法步骤,1、理清问题、明确目标 2、建立模型 讨论：什么叫模型 3、求解模型。
建立模型之后，需要设计相应算法进行求解，实际问题运算量一般都很大，通常需要用计算机求解 4、结果分析 讨论：模型计算结果与已有的经验或知识进行比较 1）模型计算结果和已有的经验或知识比较一致 2）模型计算结果和已有的经验或知识差异较大 你喜欢那一种情况？,确定目标，明确约束 抓主要矛盾、舍次要矛盾 选择模型、设定变量 描述约束和目标、确定参数 选择求解方法、求解问题 灵敏度分析、评价 汇总、解释结果、报告,运筹学方法论,26,五、运筹学与其他学科的关系,运筹学目标分析、建模、求解和结果分析需要用到很多相关学科的知识，它与如下学科的知识关系比较密切 1、数学：学习、应用运筹学应该具备较广的数学知识，许多运筹学者来自数学专业就是这个原因，有人甚至认为运筹学是一门应用数学； 2、管理学：运筹学研究对象是生产管理过程的具体问题，在利用运筹学理论和方法解决具体问题时，需要的涉及管理科学的有关理论； 3、计算机：运筹学所研究的实际问题通常都是比较复杂，而且规模比较大，在求解这些问题时，必须借助计算机来完成教 学 要 求,认真听课，出勤，预习与复习；,及时完成作业：课堂作业；,(3)考核办法： 平时成绩 分 期中考试 分 期末考试 分,28,第一章 线性规划,1.1 线性规划模型 1.1.1问题的提出 一、例1、多产品生产问题（Max, ）,另,问该工厂应如何安排生产才能使工厂的总收入最大？,一、例1、多产品生产问题（Max, ）,设x1, x2 分别代表甲、乙两种电缆的生产量，f(x)为工厂的总收入，则上述问题可用如下数学模型来表示,,其中，OBJ（Objective）表示目标，S.t.（Subject to）表示满足于。
表示在满足铜、铅资源和需求等约束条件下，使工厂的总收入这一目标达到最大最优解为,,二、例2、配料问题（min, ),某混合饲料加工厂计划从市场上购买甲、乙两种原料生产一种混合饲料混合饲料对VA、VB1、VB2和VD的最低含量有一定的要求已知单位甲、乙两种原料VA、VB1、VB2和VD的含量，单位混合饲料对VA、VB1、VB2和VD的最低含量以及甲、乙两种原料的单位价格如下表所示问该该加工厂应如何搭配使用甲乙两种原料，才能使混合饲料在满足VA、VB1、VB2和VD的最低含量要求条件下，总成本最小？,二、例2、配料问题（MIN, ),设 x1, x2分别代表混合单位饲料对甲、乙两种原料的用量，f(x)表示单位混合饲料所需要的成本，则上述问题的线性规划数学模型如下：,该数学模型的最优解为该问题的最优解为 x1=3.69，x2=0.77，minf(x)=1.49,,三、线性规划数学模型的特征和定义,1、线性规划数学模型的特征： 1）有一组决策变量（x1，x2，…，xn）表示某一方案这一组决策变量的具体值就代表一个具体方案； 2）有一个目标函数，该目标函数根据其的具体性质取最大值或最小值当目标为成本型时取最小，而当目标为效益型时取最大。
3）有一组约束方程，包括决策变量的非负约束； 4）目标函数和约束方程都是线性的 2、线性规划数学模型的定义 定义1.1 有一个目标函数和一组约束方程，且目标函数和约束方程都是线性的数学模型称为线性规划数学模型四、线性规划数学模型的背景模型和思考,1、线性规划数学模型的背景模型： 例1.1的多产品生产计划问题的数学模型称为线性规划的背景模型把该背景模型的条件一般化后可叙述如下：用有限量的几种资源生产若干种产品，如何安排生产，才能使工厂的总收入或利润达到最大 2、背景模型的思考 1）讨论：什么叫背景模型 能够帮助我们理解和记住一些相对抽象和复杂问题的简单问题模型 2）背景模型的思考 利用一些相对比较简单的问题来阐述一些相对复杂和抽象的运筹学中的一些基础概念和原理是本课程力求在教学中体现的第一个特点，希望大家用心体会1.1.2 线性规划数学模型的一般表示方式,,35,1、和式,36,2、向量式,37,3、矩阵式,38,1.1.3 线性规划的图解法,,,,,,,,,,,f(x)=36,线性规划问题的几个特点：,1、线性规划的可行域为凸集； 讨论：什么叫凸集？ 集合中任意两点连线上的一切点仍然在该集合中，在平面上为凸多边形，在空间上为凸几何体； 讨论：最优解在那里取得？ 2、线性规划的最优解一定可在其凸集的某一顶点上达到； 讨论：什么情况有最优解？最优解的存在性条件？ 3、线性规划若有可行域且其可行域有界，则一定有最优解。
上述3个结论是线性规划的3个基础定理，可以用严格的数学方法进行证明我们以简单、直观的图解法方式给出，相信大家是可以接受的1.3 线性规划求解的基础原理和单纯形法,1.3.1 线性规划问题的标准形 一、线性规划模型一般形式,二、求解思路 1、规定一标准型线性的规划问题数学模型； 2、如何把非标准形的线性规划问题数。