运筹学绪论ppt课件

第一讲 绪 论,一、运筹学的形成与发展,二、运筹学模型及分析步骤,三、运筹学的定义及学科体系,学习目的 学习本章要了解运筹学的形成和发展历史、典型案例，以及运筹学研究的主要内容等。,第一节 运筹学的形成和发展,运筹学（Operations Research）是系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学(Management Science)。 运筹学所研究的问题，可简单地归结为一句话：“依照给定条件和目标，从众多方案中选择最佳方案”，故有人称之为最优化技术。 1938年英国最早出现了军事运筹学，命名为“Operational Research”,1942年，美国从事这方面工作的科学家命其名为“Operations Research”，这个名字一直延用至今。,一、中国古代的运筹学思想 中国史记中的“运筹帷幄之中，决胜千里之外”表达了中国古代运筹学思想，在古代中国有许多运筹学思想的应用案例，如丁谓修宫、田忌赛马等，都蕴藏着神奇的运筹学思想，这些案例至今仍有很高的参考和借鉴价值。,1丁谓修宫 宋朝梦溪笔谈中记载了这样一个故事：北宋真宗年间，皇宫失火，皇帝召各大臣商议如何在很短的时间内修复好皇宫，而修复皇宫包括取土烧砖，运输建筑材料，清理废墟三大工程，但在当时的条件下，这是相当繁重的工程，大家都无以言答。当时有个叫丁谓的大臣，他提出了一个一举三得的方案,丁谓修宫工程问题示意图,取土问题,木材和石料运输问题,建筑垃圾处理问题,2田忌赛马,战国时期齐王和田忌赛马,各从自己上等马 、中等马 、下等马中选送一匹进行比赛，每输一局，输银千两，齐王的马都比田忌的好，但田忌的下等马与齐王的上等马赛，用上等马对中等马，用中等马对下等马，这样田忌非但没有输，反而嬴了一千两银子，这便是系统中从整体出发，选最优方案，到最后实施的对策策略。,二、运筹学学科的形成,现在普遍认为，运筹学的研究是从第二次世界大战初期的军事任务开始的，以英国为代表的科学家做了奠基性的工作。当时迫切需要把各项稀少的资源以有效的方式分配给各种不同的军事经营及在每一经营内的各项活动，所以美国及随后美国的军事管理当局都号召大批科学家运用科学手段来处理战略与战术问题，实际上这便是要求他们对种种（军事）经营进行研究，这些科学家小组正是最早的运筹小组（O.R.小组）。 第二次世界大战期间，运筹学（OR）成功地解决了许多重要作战问题，显示了科学的巨大物质威力，为“OR”后来的发展铺平了道路。,1935年，英国科学家R.Watson-Wart发明了雷达。丘吉尔命令在英国东海岸的Bawdsey建立了一个秘密雷达站。 1939年由P.M.S.Blackett（著名物理学家）为首，组织了一个小组，代号“Blackett马戏团”。研究的问题是：设计将雷达信息传送到指挥系统和武器系统的最佳方式；雷达与武器的最佳配置；对探测、信息传递、作战指挥、战斗机与武器的协调，作了系统的研究，并获得成功。 “Blackett马戏团”在秘密报告中使用了“Operational Research”，即“运筹学”。,1模型 运筹学模型是用一些数学关系（数学方程、逻辑关系等）来描述被研究对象的实际关系（技术关系、物理定律、外部环境等）。 运筹学模型的一个显著特点是它们大部分为最优化模型。一般来说，运筹学模型都有一个目标函数和一系列的约束条件，模型的目标是在满足约束条件的前提下使目标函数最大化或最小化。,第二节、运筹学模型及分析步骤,Max（Min） z7 x1+5 x2 3 x1+2 x2 90 4 x1+6 x2 200 7 x2 210 x10，x20,数学模型举例：,2研究方法 从现实生活场合抽出本质的要素来构造数学模 型； 探索求解的结构并导出系统的求解过程； 从可行方案中寻求系统的最优解法。,01,02,03,3 运筹学解决问题的方法步骤,明确问题 建立模型 设计算法 整理数据 求解模型 评价结果,明确问题,建立模型,设计算法,整理数据,求解模型,评价结果,简化？,满意？,Yes,No,No,Operations Research含义 Operations 汉语翻译 工作、操作、行动、手术、运算 Operations Research 日本运用学 港台作业研究 中国大陆运筹学,第三节 运筹学的定义及学科体系,运筹学的定义 Morse&Kimball（运筹学界元老） 运筹学是为决策机构在对其控制的业务活动进行决策时，提供的数量化为基础的科学方法。 英国人运筹学会（世界上最早的运筹学会） 运筹学是运用科学方法（特别是数学方法）来解决工业、商业、政府、国防等部门里有关人力、机器、物资、金钱等大型系统的指挥和管理中出现的复杂问题的一门学科。 由一支综合性的队伍 ，采用科学的方法，为一些涉及到有机系统（人-机）的控制系统问题提供解答，为该系统的总目标服务的学科。 钱学森等,学科体系 运筹学已经形成了一个庞大的学科体系，其具体内容主要包括：规划论（包括线性规划、非线性规划、整数规划和动态规划）、决策论、对策论、排队论、存储论、网络分析等。,线性规划 对偶理论 运输问题 整数规划 动态规划,图与网络方法 网络计划技术 矩阵决策 决策分析,14,绪论-思考题,1什么是运筹学？列举我国古代运筹学思想的应用案例。 2在第二次世界大战中，有哪些运用运筹学的战例？ 3我国的运筹学研究和应用情况如何？ 4主要分支有哪些？ 5简述运筹学分析的步骤。,15,第 一 章 线 形 规 划 本章学习重点,线性规划是运筹学中比较成熟的一个分支，它具有成熟而有效的求解方法，可以借助于计算机进行求解，在军事、经济等领域中具有广泛的应用。学习本章，要掌握线性规划的数学模型（建模以及把不同形式的线性规划问题化为标准形式的方法）、求解方法。,线性规划问题的提出 线性规划的数学模型 线性规划的基本概念 线性规划问题的标准形式,第一节 线性规划问题 及其数学模型,问题的提出,引例: 生产计划问题,线性规划研究的内容,在现有的资源条件下，如何充分利用资源，使任务或目标完成得最好（求极大化问题）。 在给定目标下，如何以最少的资源消耗，实现这个目标（求极小化问题）。,是问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。,第1步 -确定决策变量,设 甲的产量 乙的产量,Max Z = x1 + x2,第2步 -定义目标函数 利润,Max Z = 2 x1 + 3 x2,第2步 -定义目标函数,第3步 -表示约束条件,x1 + 2 x2 8 4 x1 16 4 x2 12 x1、 x2 0,该计划的数学模型,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,x1,x2,决策变量（Decision variables） 目标函数（Objective function） 约束条件（Constraint conditions） 可行域（Feasible region) 最优解（Optimal solution),基本概念,问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。,它是决策变量的函数,指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。,满足约束条件的决策变量的取值范围,可行域中使目标函数达到最优的决策变量的值,线性规划问题的共同特征,一组决策变量X表示一个方案,一般X大于等于零。 约束条件是线性等式或不等式。 目标函数是线性的。 求目标函数最大化或最小化,例2(书) 某厂生产甲乙两种产品，已知制成一吨产品甲需用资源A 3吨，资源B 4m3；制成一吨产品乙需用资源A 2吨，资源B 6m3，资源c 7个单位。若一吨产品甲和乙的经济价值分别为7万元和5万元，三种资源的限制量分别为90吨、200m3和210个单位，试决定应生产这两种产品各多少吨才能使创造的总经济价值最高?,建模步骤：,第一步：确定决策变量 x1：生产产品甲的数量（吨） x2：生产产品乙的数量（吨） 上述变量为由决策者决定的未知量，称为决策变量。,第二步：确定目标函数 以 Z 表示生产甲和乙两种产品各为x1和x2（吨）时产生的经济价值，总经济价值最高的目标可表示为： max z7 x1十5 x2 这就是该问题的目标函数。,第三步：确定约束条件 本例的约束条件为三种资源的限制用量。对各个限制条件逐一加以分析，写出反映其限制关系的表达式（等式或不等式），从而得到约束条件。 资源A限制：3 x1十2 x2 90 资源B限制；4 x1十6 x2 200 资源C限制： 7 x2 210 此外，产量x1和x2不能为负，只能取正值 非负条件： x1 0， x2 0,经上述分析，可将该问题表示为： max z7 x1十5 x2 3 x1十2 x2 90 4 x1十6 x2 200 7 x2 210 x1 0，x2 0 这种数学表达方式，称为该问题的一种数学模型。,线性规划三要素,线性规划(Linear Programming，LP)有： 一组有待决策的变量 （指模型中要求解的未知量） 一个线性的目标函数 （指模型中要达到的目标的数学表达式） 一组线性的约束条件 （指模型中的变量取值所需要满足的一切限制条件）,线性规划模型的一般形式,线性规划问题的标准形式,标准形式为:,目标函数最大 约束条件等式 决策变量非负 右端常数项非负,用矩阵表示,A系数矩阵 C价值向量 b资源向量 X决策变量向量,一般线性规划问题的标准形化,线型规划问题的数学模型有各种不同的形式，为了便于讨论和求解，需要将线型规划问题的数学模型写成一个统一的格式，称为线型规划问题的标准型。 统一格式规定如下 ： 1、目标函数取最大化 2、所有约束条件用等式来表示 3、所有决策变量取非负值 4、每一约束条件的右端常数（资源限量）为非负值,min Z=CX 等价于 max Z = -CX “” 约束：加入非负松驰变量,一般线性规划问题的标准形化,例：,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,min Z=CX 等价于 max Z = -CX “” 约束：加入非负松驰变量,一般线性规划问题的标准形化,例：,“” 约束： 减去非负剩余变量；,Max,例 ：,可正可负（即无约束）；,解 ：标准形为,复习思考题,1.什么是模型结构的三要素？ 2.什么是线性规划模型？ 3.LP模型中目标函数系数、约束条件系数、约束右端项的含义指的是什么？通常以什么符号表示？ 4.LP模型的一般表示方法有几种形式？能否写出这些形式？,作业：将数学模型转化为标准形,什么是线性规划？ 在工业、农业、国防、建筑、交通运输、科研、商业等各种活动中，常常要求对资源进行统一分配、全面规划和合理调度，以便从各种可能安排方案中找出最优的计划或设计，用以指导生产。在这类问题中，一方面有期望达到最优要求的目标（例如希望产值最高或消耗最少），另一方面又要受到一定条件的限制（例如人力、物力、财力的限制），如何安排才能使成效最高，消耗既定资源取得的收益最大，或达到既定收益所消耗的资源最少。这可以借助线性规划（Linear Programming，LP）来解决。,线性规划的地位与研究进程,作为一门科学的线性规划，最早可以追溯到20世纪30年代末，前苏联数学家康德洛维奇等人关于生产组织和运输问题研究所作的开拓性工作。1947年，美国数学家G.B.Dantzig以及美国空军的SCOOP研究小组提出了线性规划问题的一般性解法即单纯形法,奠定了线性规划的理论基础。50年代后，随着电子计算机的介入，线性规划的应用越来越普遍，在生产、管理、军事等方面发挥着重要的作用。 线性规划目前仍然还在发展，主要是：大型线性规划问题，线性规划解法研究等。,结束,线性规划模型,