第01讲+绪论+线性规划模型+

1、Operational Research 运筹学王坤 讲师/博交通运输与物流学院Operational Research 课程背景介绍p 教材 运筹学，第三版，清华大学出版社p 参考教材 数据、模型与决策，弗雷德里克 S 希利尔等著，任建标译，中国财政经济出版社.Operational Research Operational Research 课程背景介绍p 课程教学共68学时，授课60学时，习题课4学时，机动学习4学时。周次周次内容内容周次周次内容内容1绪论、线性规划问题10动态规划2单纯形法11动态规划应用举例3单线形法的矩阵描述及改进12排队论4对偶问题及灵敏

2、度分析13排队论5运输问题14存储论6整数规划15对策论7图与网络优化16复习+习题 8图与网络优化17机动+答疑9习题+期中考试18考试 （考勤/作业，10%；期中，20%；期末，70%）Operational Research 一、绪论IntroductionOperational Research 1.为什么学习运筹学？经经 营营设计设计 管理管理 规划规划 组织、管理组织、管理 系统、优化系统、优化 技术、经济技术、经济 法律、法规法律、法规 市场、流通市场、流通信信息息技技术术交交通通运运输输仓仓 储储包包 装装流流通通加加工工装装卸卸p运筹学是物流工程专业的必修课Operation

3、al Research p运筹学能够解决典型物流问题。 (1)存储问题1.为什么学习运筹学？Operational Research (2)厂内物料优化问题1.为什么学习运筹学？Operational Research SF11098543276(3)最短路问题1.为什么学习运筹学？Operational Research (4)物流中心选址问题1.为什么学习运筹学？Operational Research 2.什么是运筹学？ 为决策机构决策机构在对其控制下业务活动进行决策决策时，提供以数量化数量化为基础的科学方法方法。Morse，Kimball 运筹学是一门应用科学，它广泛应用现有的科学技术

4、知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。制定决策管理者管理者运用定量分析来改善决策的制定管理科学管理科学Operational Research 2.什么是运筹学？p 运筹学已被应用于工商企业、军事部门、民政事业等研究组织内的统筹协调问题，故其应用不受行业、部门的限制应用不受行业、部门的限制；p 运筹学既对各种经营进行创造性的科学研究，又涉及到组织的实际管理问题，它具有很强的实践性很强的实践性，最终应能向决策者提供建设性意见，并应收到实效；p 运筹学以整体最优为目标，从系统的观点出发，力图以整个系统最佳的方式来解决该系统各部门之间的利益冲突。对所研究的问题求

5、出最优解，寻求最佳的行动方案，所以它也可以看成是一门优化技术优化技术，提供的是解决各类问题的优化方法。Operational Research 3.运筹学的发展p1917年，爱尔朗的排队论公式；年，爱尔朗的排队论公式；p1939年，英国成立第一个运筹学工作小组，从事防空预警系统研年，英国成立第一个运筹学工作小组，从事防空预警系统研制（如何合理运用雷达），使原先平均击落一架敌机要发制（如何合理运用雷达），使原先平均击落一架敌机要发2万发炮万发炮弹改善为只要发弹改善为只要发4千发炮弹；千发炮弹；p1939年，前苏联的康托洛维奇提出类似线性规划模型；年，前苏联的康托洛维奇提出类似线性规划模型；p19

6、60年，年，康托洛维康托洛维奇出版奇出版最佳资源利用的经济计算最佳资源利用的经济计算一书，因一书，因此获诺贝尔奖；此获诺贝尔奖；p1942年，美国成立运筹学工作小组，研究战斗行动效能、行动方年，美国成立运筹学工作小组，研究战斗行动效能、行动方式；式；p1947年，美国数学家丹捷格提出线性规划模型和单纯形算法；年，美国数学家丹捷格提出线性规划模型和单纯形算法；p二战后，二战后，Morse和和Kimball合著第一部专著合著第一部专著运筹学方法运筹学方法；p运筹学的应用领域从军事扩展到其它各领域。运筹学的应用领域从军事扩展到其它各领域。Operational Research 3.运筹学的发展p1

7、948年，英国成立运筹学会；年，英国成立运筹学会；p1952年，美国成立运筹学会；年，美国成立运筹学会；p1956年，法国成立运筹学会；年，法国成立运筹学会；p1959年，英、美、法成立运筹学联合会；年，英、美、法成立运筹学联合会；p我国在我国在20世纪世纪50年代引入运筹学，年代引入运筹学，1956年时曾使用年时曾使用“运用运用学学”、1957年定名为年定名为“运筹学运筹学”，1982年加入世界运筹学联年加入世界运筹学联合会。合会。Operational Research 3.运筹学的发展p规划论：线性规划、目标规划、非线性规划、整数规划、动规划论：线性规划、目标规划、非线性规划、整数规划、

8、动态规划、组合规划等。态规划、组合规划等。p图与网络图与网络 存储论存储论 排队论排队论p对策论对策论 决策论决策论 启发式方法启发式方法 Operational Research 4.运筹学的工作步骤p弄清问题的目标，可能的约束，问题的可控变量以及有弄清问题的目标，可能的约束，问题的可控变量以及有关参数，搜集有关关参数，搜集有关资料。资料。p把问题中可控把问题中可控变量、参数变量、参数和目标与约束之间的关系用一和目标与约束之间的关系用一定的模型表示出来。定的模型表示出来。p用各种手段（主要是数学方法，也可用其他方法）将模用各种手段（主要是数学方法，也可用其他方法）将模型求解。解可以是最优解、

9、次优解、满意解。复杂模型型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机，解的精度要可的求解需用计算机，解的精度要可由决策者由决策者提出。提出。Operational Research 4.运筹学的工作步骤p首先检查求解步骤和程序有无错误，然后检查解是否反首先检查求解步骤和程序有无错误，然后检查解是否反映现实映现实问题。问题。p通过控制解的变化过程决定是否要作一定的通过控制解的变化过程决定是否要作一定的改变。改变。p将解用到实际中必须考虑到实施的问题，如向实际部门将解用到实际中必须考虑到实施的问题，如向实际部门讲清解的用法，在实施中可能产生的问题和修改讲清解的用法，在实施中可能

10、产生的问题和修改Operational Research 4.运筹学的工作步骤问题的确定分析问题建立模型软件求解结果分析确定解决方案实施方案控制Operational Research 5.运筹学的模型p研究者对研究者对经过思维经过思维后用后用描述所认识到的客观对象描述所认识到的客观对象。p利用模型可以进行一定的预测、灵敏度分析等。利用模型可以进行一定的预测、灵敏度分析等。模型是一件实际事物或情况的代表或抽象模型是一件实际事物或情况的代表或抽象。实际实际事物是事物是A A，若，若B B能够真实地描述能够真实地描述A A，则称，则称B B为为A A的的模型。模型。形象模型模拟模型符号或数学模型

11、把实际事物的尺寸加以改变（放大或缩小），看起来和实际的东西基本相似的模型。 如地图的等高线、地图的颜色、飞机风洞试验、模拟驾驶等。 用数学符号建立起来的通过等式和不等式以及图表、框图等来描述实际事物的特征或内在关系的模型。Operational Research 5.运筹学的模型p直接分析法直接分析法：按研究者对问题内在机理的认识直接构造出模型。如，：按研究者对问题内在机理的认识直接构造出模型。如，线性规划模型、投入产出模型、排队模型、存储模型、决策和对策线性规划模型、投入产出模型、排队模型、存储模型、决策和对策模型等。模型等。p类比法类比法：针对某一问题，应用不同方法构造结构性质类同的模型进

12、：针对某一问题，应用不同方法构造结构性质类同的模型进行类比。如，物理学中的机械系统、气体运力学系统、水力学系统、行类比。如，物理学中的机械系统、气体运力学系统、水力学系统、热力学系统及电路系统之间类比。热力学系统及电路系统之间类比。p数据分析法数据分析法：通过数据的搜集，应用统计分析方法，了解问题机理：通过数据的搜集，应用统计分析方法，了解问题机理的建模过程。如，回归分析模型、概率统计模型等。的建模过程。如，回归分析模型、概率统计模型等。p试验分析法试验分析法：通过对局部试验的数据加以分析来构造模型的方法。：通过对局部试验的数据加以分析来构造模型的方法。p想定（构想）法想定（构想）法：在已有的

13、知识、经验和研究基础上，对于将来可：在已有的知识、经验和研究基础上，对于将来可能发生的情况给出逻辑上合理的设想和描述，然后用已有的方法构能发生的情况给出逻辑上合理的设想和描述，然后用已有的方法构造模型并不断修正完善的方法。如，社会、经济、军事问题等。造模型并不断修正完善的方法。如，社会、经济、军事问题等。Operational Research 5.运筹学的模型(,)ijkUf x y(,)0ijkg x yixjykOperational Research 6.运筹学的应用n生产管理n交通网络n物流配送n市场营销n项目评价n等等Operational Research 运筹学Operatio

14、nal Research交通运输与物流学院Operational Research 第一章 线性规划与单纯形法p线性规划问题及其数学模型p图解法及线性规划的几何意义p单纯形法与单纯形表p单纯形法的进一步讨论p应用举例Operational Research 1.线性规划问题及其数学模型（p8）产品产品资源限制设 备原材料 A原材料 B1 台时/件4 kg/件0 kg/件2 台时/件0 kg/件4 kg/件8台时16kg12kg利润2元3元问：如何组织生产才能使利润最大？ 问题描述Operational Research 1.线性规划问题及其数学模型（p8）产品产品资源限制设 备原材料 A原材料

15、 B1 台时4 kg0 kg2 台时0 kg4 kg8台时16kg12kg利润2元3元 第1步 确定决策变量 问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。1x2x产品的产量产品的产量 第2步 确定目标函数12max23zxxOperational Research 1.线性规划问题及其数学模型（p8）产品产品资源限制设 备原材料 A原材料 B1 台时4 kg0 kg2 台时0 kg4 kg8台时16kg12kg利润2元3元 第3步 确定约束条件Operational Research 1.线性规划问题及其数学模型产品车间A车间B单位产品利润市场限制甲乙211

16、164车间可用工时108问：如何组织生产才能使利润最大？ 问题描述Operational Research 1.线性规划问题及其数学模型 第1步 确定决策变量 问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。1x2x产品甲的产量产品乙的产量 第2步 确定目标函数12max64zxx产品车间A车间B单位产品利润市场限制甲乙211164车间可用工时108Operational Research 1.线性规划问题及其数学模型 第3步 确定约束条件产品车间A车间B单位产品利润市场限制甲乙211164车间可用工时108Operational Research 1.线性规划

17、问题及其数学模型12max23zxx121228416412xxxx120 xx、12max64zxx1212221087xxxxx120 xx、p 每一个问题都用一组表示某一方案，这组决策变量的值就代表一个具体方案。一般这些变量取值是的。p 存在有关的数据，同决策变量构成，这些约束条件可以用来表示。p 都有一个，它可用决策变量及其有关的价值系数构成的（称为目标函数）来表示。按问题的不同，要求目标函数实现。Operational Research 1.线性规划问题及其数学模型1 122max(min)nnzc xc xc x11 11221121 1222221 12212( , )( , )

18、( , ),0nnnnmmmnnmna xa xa xba xa xa xba xaxaxbxxx 目标函数约束条件 满足以上三个条件（决策变量、约束条件、目标函数决策变量、约束条件、目标函数）的数学模型称为线性规划的数学模型，其一般形式为：Operational Research 1.线性规划问题及其数学模型Operational Research 1.线性规划问题及其数学模型1 122maxnnzc xc xc x11 11221121 1222221 12212,0nnnnmmmnnmna xa xa xba xa xa xba xaxaxbxxx目标函数约束条件Operational

19、Research 1.线性规划问题及其数学模型1 122maxnnzc xc xc x11 11221121 1222221 12212,0nnnnmmmnnmna xa xa xba xa xa xba xaxaxbxxx11max 1,2,.0 1,2,.,njjinijjijjzc xa xbimxjn简写Operational Research 1.线性规划问题及其数学模型11max 1,2,.0 1,2,.,njjinijjijjzc xa xbimxjn112111222max0 1,2,. () njjjjnjjjnmmjzCXP xbxjnC = c ,c ,.caxbaxbX P b .xba其中：1111231 m ax 00 .0. (,.,) 0.0 C- nmm nzCXAXbXaaAPPPaab X - 111121 max 00 .0. ( ,.,) 0.0nnmmnZCXAXbXaaAP PPaa用向量表示用矩阵表示A：约束条件系数矩阵b：资源向量 C：价值向量X：决策变量向量Operat