《【运筹学】教程_课件》由会员分享，可在线阅读，更多相关《【运筹学】教程_课件（217页珍藏版）》请在金锄头文库上搜索。
1、运筹学 Operational Research,天津大学管理学院,教师简介,张小涛，博士，副教授研究方向：计算实验金融，中小企业融资Email：,运筹学简介,什么是运筹学? 运筹学的简史 运筹学的分支有哪些? 运筹学研究的一般程序 课程要求,2018/10/18,古籍中的运筹问题,田忌赛马：田忌与齐王多次赛马，屡战屡败，田忌的一位谋士比较了六种对策后建议十万个为什么.数学分册P.312 最早记载的对策论范例。,2018/10/18,古籍中的运筹问题,祥符中,禁火。时丁晋公主营复宫室,患取土远,公乃令凿通衢取土,不日皆成巨堑。乃决汴水入堑中,引诸道竹木排筏及船运杂材,尽自堑中入至宫门。事毕,却
2、以斥弃瓦砾灰壤实于堑中,复为街衢。一举而三役济,计省费以亿万计。沈括梦溪笔谈.补笔谈卷二.权智,2018/10/18,“运筹”的出典,据史记记载：汉高祖刘邦称赞张良：运筹策帷帐中，决胜千里外，子房功也。司马迁史记留侯世家 “筹”是古代比算盘还早的计算工具之一。“运筹”是计划、安排、比较、决策优化的一个过程。 英文名：Operational Research,港台地区译为：作业研究、运作研究。五十年代末华罗庚等人介绍国外这一门新兴学科时就建议定名为：运筹学。近几十年来随着计算机的普及它的应用越来越广泛。其作用越来越被人们所认识。 大学里为什么要开设运筹学呢?请自己考虑。,2018/10/18,我
3、国当代数学家在运筹学中的贡献,1957年起中科院一批数学家作了许多令国际同行称道的工作：如物资调运问题。 20世纪70年代华罗庚先生在中国大力创导推广“统筹学”当时就获得第一代领导人的首肯，在国际数学界被称为是全世界最大而有成果的一次普及数学的创举。 凡是讲图论的优化的教科书，多半有专门的一章名：Chinese Postman Problems,其中无一例外的要提到管梅谷先生的杰出工作：中国邮递员问题(CPP)。,2018/10/18,运筹学（Operational Research),运筹学是运用科学的方法（如分析、试验、量化等）来决定如何最佳地运营和设计各种系统的一门学科。运筹学对经济管理
4、系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。,2018/10/18,运筹学的应用,经济、工商管理； 计算机算法的设计； 数学理论； 军事； 工业；农、林、牧、渔业; 医学、生物、理化、遗传； 工程计划、安排等“优化”; 学习、日常生活、旅游等。,2018/10/18,运筹学的发展：三个来源,军 事管 理经 济,军事：运筹学的主要发源地,古代军事运筹学思想 中国古代的“孙子兵法”在质的论断中渗透着量的分析（1981年美国军事运筹学会出版了一本书，书中第一句话就是说孙武子是世界上第一个军事运筹学的实践家），中国古代运筹学思想的例子还有：田忌赛马、围
5、魏救赵、行军运粮，等等。 国外历史上的阿基米德、伽利略研究过作战问题；第一次世界大战时，英国的兰彻斯特（Lanchester）提出了战斗方程，指出了数量优势、火力和胜负的动态关系；美国的爱迪生为美国海军咨询委员会研究了潜艇攻击和潜艇回避攻击的问题。,运筹学的正式产生：第二次世界大战 鲍德西（Bawdsey）雷达站的研究1939年，以Blackett为首的一个研究小组（代号“Blackett 马戏团”），研究如何改进英国的空防系统，提高英国本土防空能力。 Blackett备忘录1941年12月， Blackett应盟国政府的要求，写了五份题为“Scientists at the Operatio
6、nal Level”的简短备忘录，建议在各大指挥部建立运筹学小组，此建议被迅速采纳。据不完全统计，二战期间，仅在英、美和加拿大，参加运筹学工作的科学家超过700名。 大西洋反潜战：研究如何打破德国对英吉利海峡的海上封锁 英国战斗机中队援法的决策,管理,泰勒的时间动作研究、甘特的用于生产计划与控制的“甘特图”、吉尔布雷思夫妇的动作研究等 爱尔朗（Erlong）的排队论公式19091920年间，丹麦哥本哈根电话公司工程师爱尔朗陆续发表了关于电话通路数量等方面的分析与计算公式。尤其是1909年的论文“概率与电话通话理论”，开创了运筹学的重要分支排队论。,经济（数理经济学）,Von Neumann 与
7、对策论 1932年，Von Neumann提出一个广义经济平衡模型；1939年，提出了一个属于宏观经济优化的控制论模型；1944年，与Morgenstern共著的对策论与经济行为开创了对策论分支。 康托洛维奇与“生产组织与计划中的数学方法” 30年代，苏联数理经济学家康托洛维奇从事生产组织与管理中的定量化方法研究，取得了很多重要成果。1939年，出版了堪称运筹学的先驱著作生产组织与计划中的数学方法，其思想和模型被归入线性规划范畴。,运筹学的性质和特点,应用科学“应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据”。 运筹学的特点 定量化分析 多学科交叉
8、，如综合利用了心理学、经济学、物理等方法 最优决策,管理运筹学的工作程序,明确问题,问题分类,建立数学模型,求解数学模型,结果分析,实施,运筹学的分支,规划论(分线性、非线性、整数、目标、动态及随机规划等) 图论与网络优化； 排队论、存储论、搜索论； 对策论(博弈论)、； 可靠性理论; 全面质量管理(TQC); 计划评审、维修更新理论等。,课程教材：,胡运权，运筹学教程，北京：清华大学出版社，2007；,主要参考书：1 丁以中主编，管理科学-运用Spreadsheet建模和求解，北京：清华大学出版社，2003； 2 美弗雷德里克S希利尔（Frederick S Hillier）,任建标译,数据
9、、模型与决策（原书名 Introduction to Management Science），北京：中国财政经济出版社，2004； 3谢金星， 优化建模LINDO/LINGO软件，清华大学出版社 4 钱颂迪等，运筹学，北京：清华大学出版社，1990； 5吴育华,杜纲. 管理科学基础，天津大学出版社。,主要授课内容：,线性规划:模型与图解法，单纯形法，对偶与灵敏度分析，运输问题，线性整数规划图论与网络分析网络计划 动态规划风险型决策排队论 随机模拟,课程基本要求,掌握好基本概念、主要模型形式及其特点、适当的建模能力，必要的算法原理及简单的计算 具备计算机解题的基本能力 认真听课，勤于思考，多看书
10、 每周四交作业，独立完成 闭卷考试 有问题请Email联系,第一章 线性规划 （Linear Programming，简称LP）,1 线性规划的模型与图解法,一、LP问题及其数学模型,例1 某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源，有关单耗数据如表，试拟定使总收入最大的生产计划。,产品,资源,线性规划模型三要素： （1）决策变量设甲产品生产x1，乙产品生产x2 （2）目标函数Max Z=7 x1 +12x2 （3）约束条件,9 x1 +4x2360 4x1 +5x2 200 3 x1 +10x2 300 x1 , x20,s.t.,返回,Subject To， 意为“使其满足”,L
11、P模型的一般形式,其中: X= (x1,x2, , xn) T 为决策变量 C=(c1,c2, , cn) 称为价格系数 A=(aij)mn 称为技术系数 b= (b1,b2, , bm) T 称为资源系数,线性规划问题隐含的假定： 比例性假定 可加性假定 连续性假定 确定性假定,线性规划问题隐含的假定： 比例性假定：决策变量变化引起的目标函数的改变量和决策变量的改变量成比例，同样，每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例。 可加性假定：每个决策变量对目标函数和约束方程的影响是独立于其他变量的，目标函数值是每个决策变量对目标函数贡献的总和。,连续性假定：线性规划问题中
12、的决策变量应取连续值。 确定性假定：线性规划问题中的所有参数都是确定的参数。线性规划问题不包含随机因素。,例2 某市今年要兴建大量住宅,已知有三种住宅体系可以 大量兴建，各体系资源用量及今年供应量见下表：要求在充分利用各种资源条件下使建造住宅的总面积为最 大(即求安排各住宅多少m2)，求建造方案。,解: 设今年计划修建砖混、壁板、大模住宅各为 x1,x2,x3 m2, z为总面积,则本问题的数学模型为:,前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了12个变量，10个约束条件。,课堂练习,某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料
13、可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）,养分,饲料,课堂练习,某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）,养分,饲料,答案：设购买M饲料x1，N饲料x2,0.5 x1 +0.1x210 0.2x1 +0.3x2 5 0.3x1 +0.4x2 80.2x2 7 x1 , x20,s.t.,Min Z=300 x1 +200x2,思考题,表1-2,表1-3,单位：100m2,单位；元/100m2,解：设 表示捷运公司在第i (i=
14、1,2,3,4)月初签订的租期为j (j=1,2,3,4)个月的仓库面积的合同（单位为100m2)。,表1-2,表1-3,单位：100m2,单位；元/100m2,15,10,20,12,经过上面的讨论，得到下面的LP模型：,目标函数,约束条件,二、线性规划的图解法,1. 步骤,（1）作约束的图形可行域,可行解的集合,先作非负约束 再作资源约束,9x1+4x2=360,4x1+5x2=200,3x1+10x2=300,（2）作目标函数的等值线,给z不同的值，作相应直线，判断出z增大时，直线的移动方向,将直线向增大方向移动，直至可行域边界，交点X*即为最优解。,7x1+12x2=84,7x1+12
15、x2=168,如：令7 x1 +12x2=847 x1 +12x2=168,X*=（20，24）， Z*=428,最优解： x1 = 0， x2 = 1 最优目标值 z = 3,课堂练习 图解法求解线性规划,2. LP 解的几种情况,注：出现（3）、（4）情况时，建模有问题,补充知识：凸集,凸集：在点集中任取两点，则其连线仍在其中。,即没有凹入的部分；没有空洞。,在凸集中，点A，B，C，D称为极点（或顶点）。,A,B,C,D,从图解法中我们了解到以下事实： 若LP问题的可行域存在，则可行域一定是凸集。 若LP问题的最优解存在，则最优解或最优解之一（如果有 无穷多最优解的话）一定是可行域凸集的某
16、个极点（顶 点）。,思路：最优解先在可行域中找。（可行域为空集，则无可 行解，故无最优解。） 最优解在可行域的极点中找。 极点是有限个，若两个极点都是最优解，则两个极点所连 线段上的所有点均是最优解）,定义：LP问题的可行域的极点（顶点）称为基本可行解。,三、 线性规划应用举例与软件求解,例1 （下料问题） 某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？,例1 （下料问题） 某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？,
