运筹学模型与软件实践 Models and Software Practice of the Operations Research

Presentation on theme: "运筹学模型与软件实践 Models and Software Practice of the Operations Research"— Presentation transcript:

1 中国科学院研究生院 数学科学学院 赵 彤 zhaotong@gucas.ac.cn
运筹学模型与软件实践 Models and Software Practice of the Operations Research 中国科学院研究生院 数学科学学院 赵 彤

2 教学目的和要求： 1:公共选修课程。(40学时/2学分) 2:主要内容 (1)初步掌握将实际科研中的问题转化成为运筹学模型的方法与技巧 (2)掌握若干运筹学的重要方法及技术，知道在科研工作中使用运筹学模型和数量分析方法的对于解决科研中的问题和提高效益所起的作用。 (3)初步掌握运用软件求解基本运筹学模型的能力，会使用所学软件解决较简单的实际问题

3 星际争霸中的运筹学应用 运筹学的思想无处不在 运用好需要心领神会

4 某游戏开发商的招聘启事： [数值平衡分析]1人 职位要求： -学历本科 (数学类相关专业优先) -擅长逻辑学、统计学和经济学，数学知识丰富 -半年以上游戏从业经验，能很好地与程序员进行交流 -丰富的游戏经验 职责： 　-根据游戏系统和规则设计数学模型和计算公式 　-调整游戏的平衡性 　-跟进并修正错误。

5

6

7

8

9

10 数学建模和最优化的案例就在咱们周围 不去了解和利用数学技术解决身边的问题，实在可惜！

11 本课程侧重从经济学、管理学和工程系统的角度介绍运筹学的基本知识，试图以实际问题为背景，引出运筹学模型各分枝的基本概念、基本模型和方法。
尽管计算过程仍然作为教学的一个基本而重要的内容，但从实际应用角度出发，将运用在教育、科研、经济、管理与工业界得到广泛应用的软件包――Lindo\Lingo等软件包进行模型的求解分析，并在相应章节着重地穿插了如何使用该软件包编制的程序求解各类运筹学的模型。 通过本课程的学习，可以熟练地掌握如何使用Lindo\Lingo软件编制相应的程序，求解大部分运筹学模型，为解决实际问题提供思路。此外本课程还将简单介绍MATLAB、WinQSB甚至Excel等软件在运筹学方面的应用情况。

12 课程形式： 本课程以课堂讲授及上机实践为主，提供大量的例题分析以及上机动手实践的机会。 例题分析包含：背景、所选方案、模型变量、约束及参数的描述；优化模型求解，结果说明。 上机实践包含：上机建模及求解，解读数值报告， 课程成绩： 平时作业成绩＋期末大开卷考试成绩

13 参考的书籍 1：教材： 朱德通 《最优化模型与实验》 同济大学出版社，上海 2003 2：主要参考书：
徐玖平等. 运筹学(第二版). 北京：科学出版社, 1994 熊伟. 运筹学.　北京：机械工业出版社,2005 洪文, 吴本忠. Lingo4.0 for Windows 最优化软件及其应用. 北京：北京大学出版社, 2001

14 课程需要具备的知识及能力 1：具有简单的运筹学思想，愿意运用运筹学的思想解决实际问题。
2：具备一定的计算机操作能力，愿意通过上机培养自己的动手能力。 3：无任何编程能力的要求。

15 准备好了么？我们出发了！

16 运筹学名称的由来 Operation Research 运筹帷幄　　 “史记” （运筹帷幄，决胜千里 史记《张良传》） 操作研究

17 运筹学的起源与发展 起源于二次大战的一门新兴交叉学科 与作战问题相关
如雷达的设置、运输船队的护航、反潜作战中深水炸弹的深度、飞行员的编组、军事物资的存储等 英国称为 Operational Research 美国称为 Operations Research

18 军事物资调度与存储 二战中一个倒霉的家伙： 号称沙漠之狐的隆美尔。 在没有汽油、柴油的日子里很绝望！

19 军事保障内容繁多，不仅包括各式各样的武器装备、燃料、油料、服装、食品，还包括对信息系统、指挥系统、运输系统本身的保障。每一项内容又包括众多的具体保障对象，保障物资种类繁多，数量庞大，任务繁重。为了完成了各项保障任务，盟军动用了各式各样的运输机、运输船等物流装备，配备了大量的专业物资保障人员，实现了运输、装备和参战人员的跨国大转移。由此可见，军事保障在现代战争中的地位和作用日益突出，在某种意义上说，军事保障活动的成败直接关系到战争的胜负。

20 运筹学的起源与发展 战后在经济、管理和机关学校及科研单位继续研究 1952年，Morse 和 Kimball出版《运筹学方法》
1948年英国首先成立运筹学会 1952年美国成立运筹学会 1959年成立国际运筹学联合会(IFORS) 我国于1982年加入IFORS，并于1999年8月组织了第15届大会

21 运筹学的起源与发展

22 运筹学在中国的发展 20世纪50年代后期,钱学森、华罗庚、许国志等把运筹学引入中国。“打麦场选址问题”和“中国邮递员问题”在此期间提出。
华罗庚院士在1965年起的10年中与他的学生一道在全国推广“优选法”和“统筹法” 1980年中国数学会运筹学会正式成立，1991年中国运筹学会作为中国运筹学会作为国家一级学会正式成立

23 运筹学的定义 为决策机构对所控制的业务活动作决策时，提供以数量为基础的科学方法——Morse 和 Kimball
运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题，其方法是发展一个科学的系统模式，并运用这种模式预测，比较各种决策及其产生的后果，以帮助主管人员科学地决定工作方针和政策——英国运筹学会 运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理——中国百科全书 现代运筹学涵盖了一切领域的管理与优化问题，称为 Management Science

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

25 运筹学的分枝 数学规划：线性规划、非线性规划、整数规划、动态规划、目标规划等 图论与网路理论 随机服务理论：排队论 存储理论 决策理论
对策论 系统仿真：随机模拟技术、系统动力学 可靠性理论 金融工程

26 运筹学研究的基本步骤

27 运筹学的发展趋势 运筹学的危机 IT对运筹学的影响 运筹学与行为科学结合 服务行业中的应用 脱离实际应用，陷入数学陷阱
MIS, DSS, MRP-II, CIMS, ERP OR Dept. --> Dept. Of OR & IS 运筹学与行为科学结合 群决策和谈判 对策理论 多层规划 合理性分析 服务行业中的应用 金融服务业 信息、电信服务业 医院管理

28 运筹学的发展趋势 后勤(Logistics) 全球供应链管理 电子商务：集成特性 随机和模糊 OR 问题本身的不确定性 人类知识的局限性

29 运筹学的学科地位

30 需要事先说明的问题 （丑话说在前面）： (1)运筹学是一种给出问题不坏的答案的艺术，否则问题的结果会更坏 (2)定性分析是定量分析的基础 (3)定量分析是定性分析的支持 (4)从数学模型中求解出来的最终答案，仅仅是为实际问题的系统处理提供了有用的可以作为决策基础的信息。

31 需要事先说明的问题 （丑话说在前面）： 数学模型不是万能的, 没有数学模型也许是万万不能的!

32 Lingo系列优化软件包就给我们提供了理想的选择！
工欲善其事，必先利其器 运用各种数学优化模型来解决不同领域中实际问题正逐渐得到广泛应用 。 构造一个优化模型容易（相关领域的知识，基本的数学修养），如何构造求解算法（数学专家？计算机编程?） 我们遇到的实际问题一般规模都较大，即使建立了模型，找到了求解的方法，对于庞大的计算量也是望而却步（数据在Excel里，怎么导出/入来？）。 Lingo系列优化软件包就给我们提供了理想的选择！

33 Lingo是解决优化模型的利器 Lingo是什么工具？ Lingo的特点
程序执行速度很快，易于输入、修改、求解和分析一个数学规划问题 有关Lingo软件的详细情况可上网访问网站：

34

35 Lingo的历史 美国芝加哥（Chicago）大学的Linus Schrage教授于1980年前后开发，后来成立LINDO系统公司（Lindo Systems Inc.） 主要产品 LINDO: Linear INteractive and Discrete Optimizer (V6.1) LINGO: Linear INteractive General Optimizer (V10.0) LINDO API: LINDO Application Programming Interface(4.1) 演示（试用）版、学生版、高级版、超级版、工业版、扩展版…（求解问题规模和选件不同）

36 一般的优化模型及其求解方式 实际问题中的优化模型 决策变量 目标函数 约束条件 数学规划 线性规划（LP） 0-1整数规划
纯整数规划（PIP） 二次规划（QP） 一般整数规划 混合整数规划（MIP） 非线性规划（NLP） 连续规划 整数规划（IP）

37 Lingo能做什么？

38 Lingo怎么做到的？

39 课程规划 线性规划模型及实验 对偶规划和灵敏度分析 运输问题类模型与实验 分配问题和实验 网络流量问题与实验 整数规划模型与实验
计划排序和统筹方法与实现 对策模型与实验 存储模型与实验

40 课程规划 你希望在这门课程中 学到什么？ 具备什么能力？