运筹学 运 筹 帷 幄 之 中 决 胜 千 里 之 外 Operations Research 讲课教师：王传伟

Presentation on theme: "运筹学 运 筹 帷 幄 之 中 决 胜 千 里 之 外 Operations Research 讲课教师：王传伟"— Presentation transcript:

1 运筹学 运 筹 帷 幄 之 中 决 胜 千 里 之 外 Operations Research 讲课教师：王传伟
运 筹 帷 幄 之 中 决 胜 千 里 之 外 运筹学 讲课教师：王传伟 Tel：( 824 ) 2504

2 教学理念 战略上 快乐运筹 整体最优 助你决策 伴你追求 战术上 不急不躁 追根寻由 建模寻优 创新应用 学习精神 勤于思考 勇于实践

3 课程简介 本课程是工科管理类的专业技术基础课。
开设本课程的主要目的是使学生了解和掌握运筹学对一些类型的优化决策问题进行定量研究的思想、技术和方法，培养学生的实际问题定量分析能力、一定的建模能力和创新能力。 世界各国的大学，管理类、理工类专业一般都开设运筹学这一课程。 现实中许多问题通过一定的变化都可以归纳为某类运筹学的问题，运筹学为解决实际问题和科学研究提供了较好的技术和工具。

4 初识运筹学--几个例子 初中习题 例1 现有甲、乙两种货物需用火车运输。已知甲有2000t，乙有1700t。
车站有A、B两种车厢供选择，A种车厢最多可装35t的甲和15t的乙； B种车厢最多可装25t的甲和35t的乙。 （1）有多少种装运方案？ （2）若甲种货物运费为600元/t，乙种货物运费为800元/t，哪种方案最省？

5 初识运筹学--几个例子 高考题 例2 某公司计划2008年在甲、乙两个电视台做总时间不超过300分钟的广告，广告总费用不超过9万元。
例2 某公司计划2008年在甲、乙两个电视台做总时间不超过300分钟的广告，广告总费用不超过9万元。 甲、乙两电视台的广告收费标准为500元/分钟和200元/分钟。 假定甲、乙两电视台为该公司所做的每分钟广告能给公司带来的收益分别为3000元和2000元。 问该公司如何分配在甲、乙两个电视台的广告时间，才能使公司的收益最大，最大收益为多少元?

6 初识运筹学--几个例子 例3 (生产计划问题—线性规划) 某厂生产A、B、C三种产品，其所需劳动力、材料等有关数据见下表。求：
（1）确定获利最大的产品生产计划； （2）若产品B、C的单件利润不变，则产品A的单件利润在什么 范围内变动时,上述最优计划不变？ （3）若材料供应量不变，则劳动力供应量在什么范围内变动时,上述最优基不变？ （4）如果设计一种新产品D，单件劳动力消耗为2单位，材料消耗为3单位，每件可获利5元，问该种产品是否值得生产？并求新的最优计划。

7 初识运筹学--几个例子 例3(续) 产 品 资 源 A B C 可用量 劳动力 材 料 1 1 1 1 4 7 3 9 产品利润（元）
材 料 3 9 产品利润（元）

8 初识运筹学--几个例子 例4 (运输问题) 某饮料在国内有三个生产厂，分布在城市A1、A2、A3,其一级承销商有4个，分布在城市B1、B2、B3、B4，已知各厂的产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为Cij，为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。 销地 产地 B1 B2 B3 B4 产量 A1 6 3 2 5 A2 7 8 4 A3 9 销量 1

9 例5 (指派问题) 已知分配A1、A2、A3、A4、A5五人分别完成五项任务, 他们分别完成各任务的时间如表
初识运筹学--几个例子 例5 (指派问题) 已知分配A1、A2、A3、A4、A5五人分别完成五项任务, 他们分别完成各任务的时间如表 问应如何分配,使这五人分别完成这五项任务的总时间最小?

10 初识运筹学--几个例子 B1 B2 B3 B4 B5 B6 A1 √ A2 A3 A4 A5 A6 例6 (图的应用问题)
例6 (图的应用问题) 有A1,A2,A3,A4,A5,A6六名运动员报名参加B1,B2,B3,B4,B5,B6六个项目的比赛. 下表是各运动员报名参加的比赛项目. 问六个项目的比赛顺序如何安排, 做到每名运动员都不连续地参加两项比赛? B1 B2 B3 B4 B5 B6 A1 √ A2 A3 A4 A5 A6

11 初识运筹学--几个例子 B C E D 例7 (图的应用问题)
某河流中有4个岛屿, 从两岸至各岛屿及各岛屿之间的桥梁编号如图所示. 在一次敌对的军事行动中, 问至少应炸断几座及哪几座桥梁, 才能完全切断两岸的交通联系? B C D E 1 2 4 5 6 10 11 12 13 7 3 9 8

12 初识运筹学--几个例子 10 20 30 40 50 收 益 （万元） A 15 25 28 B 45 70 C 例8 (资源分配问题)
投放资金（万元） 10 20 30 40 50 收 益 （万元） A 15 25 28 B 45 70 C

13 初识运筹学--几个例子 例9 (生产存贮问题)

14 初识运筹学--几个例子 例10 (决策分析问题) 某公司有资金500万元，
例10 (决策分析问题) 某公司有资金500万元， (1) 如用于某项开发事业，估计成功率为96%，一年可获利润12％；若失败则丧失全部资金； (2) 若把资金全存在银行，可获得年利率6%; (3) 为辅助决策可求助于咨询公司，费用为5万元. 根据咨询过去公司类似200例咨询工作，有下表 ：

15 实施结果 投资 投资 合计 咨询意见 成功 失败 可以投资 154 2 156次 不宜投资 38 6 44次 合计 192 8 200次
投资 投资 合计 咨询意见 成功 失败 可以投资 次 不宜投资 次 合计 次 该公司是否应该咨询？资金该如何使用？

16 初识运筹学--几个例子 例11 (层次分析问题) 甲 乙 丙 价格 35 28 22 上下班 不太方便 较方便 方便 中小学 名校 较好
例11 (层次分析问题) 张老师需要购买一套住房, 他考虑的主要因素有: 价格适中, 上下班比较方便, 小区对应的中小学校较好, 居住环境相对较好. 经比较, 他初步选择了甲, 乙, 丙三套住房, 情况如下表所示. 他应该选哪套房子? 甲 乙 丙 价格 35 28 22 上下班 不太方便 较方便 方便 中小学 名校 较好 一般 居住环境 好 稍差

17 初识运筹学--几个例子 例12 (囚徒困境问题) 设有甲, 乙两名嫌疑犯因同一桩罪行被捕, 由于希望他们坦白并提供对方犯罪证据. 规定
例12 (囚徒困境问题) 设有甲, 乙两名嫌疑犯因同一桩罪行被捕, 由于希望他们坦白并提供对方犯罪证据. 规定 (1) 如两人均坦白各判刑3年; (2) 如一方坦白另一方不坦白, 坦白一方从轻释放, 不坦白一方判刑8年; (3) 如两人均不坦白, 由于犯罪事实证据中很多不能成立, 只能每人各判1年. 试分析甲, 乙两名犯罪嫌疑人怎样选择最好?

18 运筹学课件 运筹学概论 运筹学的由来与发展 运筹学的性质与特点 运筹学的主要内容 运筹学的发展趋势 运筹学的学科地位 △返回

19 (一)、运筹学的由来与发展 1. 名称的由来 2. 运筹学 (Operational Research) 日本译作“运用学”;
运筹学课件 (一)、运筹学的由来与发展 1. 名称的由来 英文： Operations Research 缩写 O.R. (Operational Research) 日本译作“运用学”; 香港、台湾译为“作业研究”. 2. 运筹学 我国学者从古语“运筹帷幄之中，决胜千里之外”取“运筹”二字，充分体现了这门学科运心筹谋、策略取胜的精髓。

20 运筹学的由来与发展 3. 运筹学一般定义 4.其它描述 运筹学是一门新兴的应用学科. 由于它所研究的对象极其广泛有着许多不同的定义.
运筹学是应用分析、试验、量化的方法,对系统(经济管理)中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。 4.其它描述 运筹学是一门新兴的应用学科. 由于它所研究的对象极其广泛有着许多不同的定义.

21 运筹学的由来与发展 1976年美国运筹学会定义: “运筹学是研究用科学方法来决定在资源不充分的情况下如何最好地设计人 一 机系统, 并使之最好地运行的一门学科”. 1978年联邦德国的科学词典上定义: “运筹学是从事决策模型的数学解法的一门学科”. 前者着重于处理实际问题, 而对于“科学方法”则未加说明, 后者强调数字解, 而注重数学方法.

22 运筹学的由来与发展 英国运筹学杂志认为: “运筹学是运用科学方法(特别是数学方法)来解决那些在工业、商业、政府部门、国防部门中有关人力、机器、物资、金钱等的大型系统的指挥和管理方面所出现的问题,其目的是帮助管理者科学地决定其策略和行动”.

23 运筹学的由来与发展 运筹学是近代应用数学的一个分支.
运筹学主要是将生产管理中出现的一些带普遍性的运筹问题加以提炼, 然后利用数学方法去解决. 前者提供模型, 后者提供理论和方法,前者是后者发展的基础, 后者是前者进行工作的科学依据. 运筹学(O.R.)是两者有机结合而成的.

24 运筹学的由来与发展 5. 运筹学的发展历史 20世纪40年代诞生于英美
1940年，英国为对付德国空军的空袭，使用了雷达，但没有科学布局，效果不好，为解决这个问题，成立了运筹学小组, 称为Operational Research，意为作战研究. 美国和加拿大也在军队设立了运筹学小组，称之为Operations Research，协助指挥官研究战略及战术问题. 战后许多从事运筹学研究的科学家转向了民用问题的研究，使运筹学在企业管理方面的应用得到了长足进展.

25 运筹学的由来与发展 50~60年代快速发展走向成熟 计算机的崛起使OR进入飞速发展期 新领域新方法不断萌发 应用范围更加广泛
标志： 队伍壮大，成立学会，创办刊物，高校开课 军事运筹学面向未来要求 大量理论成果问世，系统专著出版 各个分支得到充实、完善 计算机的崛起使OR进入飞速发展期 LP算法的研究带动各个分支理论与方法的更大发展 新领域新方法不断萌发 应用范围更加广泛

26 运筹学的由来与发展 第一本运筹学杂志和英国的运筹学会分别于1950年和1953年出现.
世界上第一个运筹学会“美国运筹学会”于1952年成立. 1959年成立了国际运筹学会(IFORS), 到1986年已有35个会员国和6个兄弟学会, 会员3万多人, 大多数会员国都办有自己的杂志. “中国运筹学联合会”于1980年成立, 于1982年加入国际运筹学会联盟并创刊《运筹学杂志》, 后改名为《运筹学学报》.

27 运筹学的由来与发展 1947年Dantzig提出单纯形法 50-56年LP对偶理论诞生
1951年Kuhn-Tucker定理奠定非线性规划理论基础 1954年网络流理论建立 1955年创立随机规划 1958年创立整数规划及割平面解法 1958年求解动态规划的Bellman原理发表 1960年Dantzig-Wolfe建立大LP分解算法 哈奇扬的椭球算法 T.Lsaaty创立层次分析(AHP)

28 (二)、运筹学的性质与特点 引入数学方法解决实际问题 --定性与定量方法结合 系统与整体性 --从全局考察问题 应用性
运筹学课件 (二)、运筹学的性质与特点 引入数学方法解决实际问题 --定性与定量方法结合 系统与整体性 --从全局考察问题 应用性 --源于实践、为了实践、服务于实践 交叉学科 --涉及经济、管理、数学、工程和系统等 多学科 开放性 --不断产生新的问题和学科分支 多分支 --问题的复杂和多样性

29 运筹学课件 （三）运 筹 学 的 主 要 内 容

30 主 要 学 习 内 容 课程主要由几个比较独立的部分构成 第1章 线性规划及单纯形 第2章 线性规划的对偶 第3章 运输问题
运筹学课件 课程主要由几个比较独立的部分构成 第1章 线性规划及单纯形 第2章 线性规划的对偶 第3章 运输问题 第4章 整数规划与分配问题 第6章 图与网络分析 第8章 动态规划 第9章 存贮论 第10章 排队论 第11章 决策分析 第12章 对策论(博弈论) 主 要 学 习 内 容

31 主要学习内容简介 线性规划是将追求的目标和受到的约束条件都用线性方程表示出来； 整数规划与线性规划的模型相似，但变量取值必须为整数；
动态规划分析问题的时候将问题考虑成多阶段决策问题，分阶段求出最优决策； 图与网络，将事物及事物之间关系用图的方法表示出来，通过图来解决一些问题； 排队论则研究日常中最常见的排队现象。 这些内容都是运筹学中最基本的分支领域； 课程重点是各领域问题的优化原理、常用的模型和算法及实际问题的应用。

32 （四）运筹学的发展趋势 成熟的学科分支向纵深发展 新的研究领域产生 与新的技术结合 与其他学科的结合加强 传统优化观念不断变化 运筹学课件
△返回

33 运筹学课件 (五)运 筹 学 的 学 科 地 位 △返回

34 运筹学课件 （六）最优化模型 模型要素 变量—可控因素 目标—优化的动力和依据 约束—内部条件和外部约束 一般步骤 实例 △返回

35 运筹学课件 线性规划模型 问 题

36 运筹学课件 线性规划模型 建模分析

37 运筹学课件 线性规划模型 模型 △返回

38 （七）学习要求 学习要求 教学方法 基本要求 运筹学课件
本课程强调定量分析、实际问题的数学抽象、建立优化模型和算法设计与实现。理解概念、原理、定理，结合例题讲解和较大量的课外练习理解和掌握重点模型和算法 教学方法 以授课为主，案例分析与上机实习相结合。而讲课中主要培养用最优化方法解决实际问题的能力。 基本要求 不能旷课、迟到、早退，有事要请假； 上课认真听讲； 认真完成并按时交作业。 △返回

39 参 考 资 料 运筹学课件 中国运筹学会网址: http://www.orsc.org.cn
韩伯棠, 管理运筹学, 高等教育出版社, 北京, 2000年 刁在筠等, 运筹学(第二版), 高等教育出版社, 2002 胡运权, 运筹学习题集, 清华大学出版社, 北京, 2002年 《运筹学》教材编写组编, 运筹学, 清华大学出版社, 2005 徐渝主编, 运筹学, 陕西人民出版社出版, 2007 李宗元, 运筹学ABC成就、信念与能力, 经济管理出版社,  2000 △返回

40 Thank You !

41 附录--中国运筹学发展史 现代运筹学被引入中国是在五十年代后期。中国第一个运筹学小组在钱学森、许国志先生的推动下在1956年于中国科学院力学研究所成立。可见，运筹学一开始就被理解为同工程有密切联系的学科。 钱学森先生在MIT取得硕士学位，在加州理工大学（California Institute of Technology）取得博士学位后成为该校的第一位Goddard讲座教授。许国志先生在堪萨斯大学取得博士学位后，在马里兰大学流体力学和应用数学研究所当研究员。他们两人于1955年回到祖国致力于新中国的科技事业。

42 中国运筹学发展史 1959年，第二个运筹学部门在中国科学院数学研究所成立(华罗庚)，这是大跃进中数学家们投身于国家建设的一个产物。
力学所小组与数学所的小组于1960年合并成为数学研究所的一个研究室，当时的主要研究方向为排队论、非线性规划和图论，还有人专门研究运输理论、动态规划和经济分析（例如投入产出方法）。 在当时这些先遣者中，目前还健在的有越民义先生、刘源张院士、朱永津教授、桂湘云教授、陈锡康教授、徐光煇教授、韩继业教授、李秉全教授、郭绍僖教授等。

43 中国运筹学发展史 1963年是中国运筹学教育史上值得一提的一年，数学研究所的运筹学研究室为中国科技大学应用数学系的第一届毕业生（58届）开设了较为系统的运筹学专业课，这是第一次在中国的大学里开设运筹学专业和授课。 今天，运筹学的课程已变成所有大学的商学院、工学院乃至数学系和计算机系的基本课程了。

44 中国运筹学发展史 五十年代后期，运筹学在中国的应用集中在运输问题上，其中一个广为流传容易明白的例子就是“打麦场的选址问题”，目的在于解决当时手工收割为主的情况下如何节省人力和实践. 国际上大家都知道的“中国邮路问题”模型也是在那个时期由管梅谷教授提出的。所以，现在非常热门的“物流学”，在当时就有一些雏形的研究. 但可惜中国的大工业落后，又不是市场环境，使我们在相当长的时期中远离了当代“物流学”的发展主流.

45 中国运筹学发展史 中国运筹学会于文化大革命后的1980年成立, 当时作为中国数学会的一个分会。
第一届全国大会在山东省济南召开，华罗庚教授当然地被选为第一届理事长，副理事长有许国志先生、越民义先生。 中国运筹学会在1982年成为国际运筹学联合会（IFORS）的成员。 第二届全国代表大会和学术会议于1984年在上海召开，越民义先生被选为该届理事长，余潜修、刘源张、桂湘云为副理事长。 第三次全国会议于1988年在安徽省九华山召开,徐光煇先生任理事长，副理事长为管梅谷、常本英、吴沧浦。

46 中国运筹学发展史 1992年第四次全国代表大会在四川省成都市召开，中国运筹学会成为全国一级学会，徐光煇先生继任理事长。
第五次全国代表大会和第六次全国代表大会分别于1996年和2000年在西安市和湖南长沙举行，章祥荪教授出任理事长，副理事长分别为吴仓浦、常本英、俞文此、赵玮、程侃、袁亚湘、邓乃扬、刘光中、冯英俊等。

47 中国运筹学发展史 1992年中国运筹学会从中国数学会独立出来成为国家一级学会是学会发展史上的一个重要事件。它的寓意是很深刻的，说明了运筹学以数学为基础，但同数学学科有本质的不同。运筹学家除了推动运筹学基本理论的发展，还要对社会负起同数学家不同的责任。 1994年美国运筹学会和管理科学学会的合并是国际运筹学界的一件大事，成立了INFORMS.目前，运筹学和管理科学的结合也引起中国运筹学界的极大关注。

48 中国运筹学发展史 运筹学的理论固然重要，但应用是它的灵魂。运筹学在国际上除了设理论奖，还设有应用奖。由INFOERMS 所设,被称为运筹学奥林匹克的Franz Edelman奖就是最好的说明。而IFORS 则只设面向发展中国家的运筹学应用奖。 中国的运筹学，在理论和应用上同国际水平均有很大差距，在应用方面的差距则更大，这是由社会、经济制度等多方面的原因。我们只可以说, 我们的运筹学工作在发展中国家这一层面上还是先进的。

49 中国运筹学发展史 作为例证，我们在这里提一下IFORS为发展中国家设的运筹学奖：IFORS Prize for Operational Research in Development (译为“运筹学进展奖”)，该奖三年一次在IFORS学术大会上颁发。 1996年，章祥荪、崔晋川研究员在加拿大温哥华举行的第十四届IFORS学术大会上获得该奖的一等奖。 1999年陈锡康研究员等在北京召开的第十五届IFORS大会上获得一等奖。另外还有中国运筹工作者获得二等奖

50 中国运筹学发展史 近年来，中国运筹学工作者继续坚持运筹学研究与经济建设等重大问题紧密结合。例如，山东省与大连市经济发展计划的制定， 兰州铁路局铁路运输的优化安排， 中外合资经营项目经济评价， 若干国家重大工程中的综合风险分析等方面， 我国运筹学者都发挥了积极作用。 近二十年来，信息科学、生命科学等现代高科技对人类社会产生了巨大影响，中国运筹学工作者还关注到其中一些运筹学起作用的新的工作方向。 例如，我们的运筹学工作者，将全局最优化、图论、神经网络等运筹学理论及方法应用于分子生物信息学中的DNA与蛋白质序列比较、芯片测试、生物进化分析、蛋白质结构预测等问题的研究；在金融管理方面，将优化及决策分析方法，应用于金融风险控制与管理、资产评估与定价分析模型等；在网络管理上，利用随机过程方法，研究排队网络的数量指标分析；在供应链管理问题中，利用随机动态规划模型，研究多重决策最优策略的计算方法。在这些重要的新方向上，我国运筹学工作者都取得了可喜的进展及成绩，有一些已进入国际先进水平的行列，被有关同行所认可。

51 中国运筹学发展史 中国运筹学会下属有多个专业分会：如决策科学分会；数学规划分会；排序分会；图论组合分会；排队轮分会；青年分会；可靠性分会；金融工程及金融风险管理分会；智能计算分会；企业管理运筹分会；经济数学分会等， 各分会定期或不定期进行学术交流。北京、陕西、山东、大庆等一些省市还有地区性运筹学会，部队系统有军事运筹学学会, 仅大庆油田运筹学会就有会员二百多名，他们在许多领域应用运筹学理论与方法，取得了很好的经济效益与社会效益。

52 全国运筹学硕士/博士学位授权表 二级学科代码 二级学科名称 一级学科代码 一级学科名称 门类代码 门类名称 所在大学 70105 运筹学与
数学 7 理学 复旦大学 控制论 山东大学

53 120100 管理科学 与工程 1201 管理科学与工程 12 管理学 清华大学 北京航空航天大学 天津大学 大连理工大学 哈尔滨工业大学 上海交通大学 西安交通大学

54 81103 系统工程 811 控制科学工程 8 工学 华中科技大学 西安交通大学 82303 交通运输 规划与 管理 823 交通运输工程 北京交通大学 同济大学 东南大学