《运筹学绪论.ppt》由会员分享,可在线阅读,更多相关《运筹学绪论.ppt(127页珍藏版)》请在金锄头文库上搜索。
1、1,运筹学,北京理工大学 管理与经济学院 吴祈宗教授,2,1、绪 论 2、线 性 规 划 3、运 输 问 题 4、动 态 规 划 5、图与网络分析 6、排 队 论 7、教学日历,运 筹 学 目录,说 明 本教学课件是与教材紧密配合使用的,教材为: 运筹学 杨民助编著 西安交通大学出版社,2000年6月 参考书: 运筹学 清华大学出版社 或其他的运筹学方面本科教材的相关内容 下面所标注的页号,均为本课程教材的页号。例如: p123 表示第123页 p31-34 表示从第31页到第34页,3,绪 论,运筹学(Operational Research) 直译为“运作研究” 运筹学是运用科学的方法(如
2、分析、试验、量化等)来决定如何最佳地运营和设计各种系统的一门学科。运筹学对经济管理系统中的人力、物力、财力等资源进行统筹安排,为决策者提供有依据的最优方案,以实现最有效的管理。 运筹学有广泛应用(可以自己找一些参考书看) 运筹学的产生和发展(可以自己找一些参考书看),4,运筹学解决问题的过程,1)提出问题:认清问题 2)寻求可行方案:建模、求解 3)确定评估目标及方案的标准或方法、途径 4)评估各个方案:解的检验、灵敏性分析等 5)选择最优方案:决策 6)方案实施:回到实践中 7)后评估:考察问题是否得到完满解决 1)2)3):形成问题;4)5)分析问题:定性分析与定量分析。构成决策。,5,运
3、筹学的分支,线性规划 非线性规划 整数规划 动态规划 多目标规划 随机规划 模糊规划等,图与网络理论 存储论 排队论 决策论 对策论 排序与统筹方法 可靠性理论等,6,运筹学在工商管理中的应用,生产计划:生产作业的计划、日程表的编排、合理下 料、配料问题、物料管理等 库存管理:多种物资库存量的管理,库存方式、库存 量等 运输问题:确定最小成本的运输线路、物资的调拨、 运输工具的调度以及建厂地址的选择等 人事管理:对人员的需求和使用的预测,确定人员编 制、人员合理分配,建立人才评价体系等 市场营销:广告预算、媒介选择、定价、产品开发与 销售计划制定等 财务和会计:预测、贷款、成本分析、定价、证券
4、管 理、现金管理等 * 设备维修、更新,项目选择、评价,工程优化设计与管理等,7,运筹学方法使用情况(美1983)(%),8,运筹学方法在中国使用情况(随机抽样)(%),9,运筹学的推广应用前景,据美劳工局1992年统计预测: 运筹学应用分析人员需求从1990年到2005年的增长百分比预测为73%,增长速度排到各项职业的前三位. 结论: 运筹学在国内或国外的推广前景是非常广阔的 工商企业对运筹学应用和需求是很大的 在工商企业推广运筹学方面有大量的工作要做,10,学习运筹学要把重点放在分析、理解有关的概念、思路上。在自学过程中,应该多向自己提问,如一个方法的实质是什么,为什么这样做,怎么做等。
5、自学时要掌握三个重要环节: 1、认真阅读教材和参考资料,以指定教材为主,同时参考其他有关书籍。一般每一本运筹学教材都有自己的特点,但是基本原理、概念都是一致的。注意主从,参考资料会帮助你开阔思路,使学习深入。但是,把时间过多放在参考资料上,会导致思路分散,不利于学好。 2、要在理解了基本概念和理论的基础上研究例题,注意例题是为了帮助你理解概念、理论的。作业练习的主要作用也是这样,它同时还有让你自己检查自己学习的作用。因此,做题要有信心,要独立完成,不要怕出错。因为,整个课程是一个整体,各节内容有内在联系,只要学到一定程度,知识融会贯通起来,你做题的正确性自己就有判断。 3、要学会做学习小结。每
6、一节或一章学完后,必须学会用精炼的语言来该书所学内容。这样,你才能够从较高的角度来看问题,更深刻的理解有关知识和内容。这就称作“把书读薄”,若能够结合自己参考大量文献后的深入理解,把相关知识从更深入、广泛的角度进行论述,则称之为“把书读厚” 在建数学模型时要结合实际应用,要学会用计算机软件解决问题。,如何学习运筹学课程,返回目录,11,各章节的重点、难点 及注意事项,12,1、 线 性 规 划,线性规划模型: 目标函数:Max z = 50 x1 + 100 x2 约束条件:s.t. x1 + x2 300 2 x1 + x2 400 x2 250 x1 , x2 0 *看 p 7-9 例1-
7、1,1-2,例1. 某工厂在计划期内要安排甲、乙两种产品的生产,已知生产单位产品所需的设备台时及A、B两种原材料的消耗以及资源的限制,如下表: 问题:工厂应分别生产多少单位甲、乙产品才能使工厂获利最多?,13,1、 线 性 规 划 (续1.1),1. 1 线性规划的概念 线性规划的组成: 目标函数 Max f 或 Min f 约束条件 s.t. (subject to) 满足于 决策变量 用符号来表示可控制的因素,一般形式 ( p10- p 11) 目标函数: Max (Min) z = c1 x1 + c2 x2 + + cn xn 约束条件: s.t. a11 x1 + a12 x2 +
8、+ a1n xn ( =, )b1 a21 x1 + a22 x2 + + a2n xn ( =, )b2 am1 x1 + am2 x2 + + amn xn ( =, )bm x1 ,x2 , ,xn 0,标准形式 ( p11- p 15 ,例1-3) 目标函数: Max z = c1 x1 + c2 x2 + + cn xn 约束条件: s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ,x2 , ,xn 0 *练习:p 68-70
9、 习题1 1-1,1-2,14,1、 线 性 规 划 (续1.2),1. 2 线性规划问题解的概念及性质 熟悉下列一些解的概念(p15-16) 可行解、可行解集(可行域),最优解、最优值,基、基变量、非基变量,基本解、基本可行解,可行基、最优基。,图解方法及各有关概念的意义(p16-20) 看:图解法步骤,例1-4,1-5,1-6,1-7,1-8,1-9 下一页是一个图解法解题的一个例子,右图中的阴影部分为可行域。,单纯形法的理论基础(p20-30) 1.2.3段要求看懂,了解如何直接通过对约束矩阵的分析求出基本可行解 1.2.4, 1.2.5两段应注重结论的了解,如单纯形法思想和关于线性规划
10、解的四个 定理,而对证明过程则可根据自己的数学基础来掌握: 基础很好,可要求掌握;否则,也可略去不看。 *习题:p70 习题1 1-3,1-4,15,1、 线 性 规 划 (续1.2),例1. 目标函数: Max z = 50 x1 + 100 x2 约束条件: s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E) 得到最优解: x1 = 50, x2 = 250 最优目标值 z = 27500,16,1、 线 性 规 划 (续1.3),1. 3 单纯形法 利用单纯形表的方法求解线性规划重点 (p30-45 1.
11、3.1, 1.3.2, 1.3.3) 此项内容是本章的重点,学习中应注意掌握表格单纯形法求解线性规划问题的基本过程。要通过读懂教材内容以及大量练习来掌握。,17,1、 线 性 规 划 (续1.3),表格单纯形法 ( p40- p 45) 考虑: bi 0 i = 1 , , m Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn b1 a21 x1 + a22 x2 + + a2n xn b2 am1 x1 + am2 x2 + + amn xn bm x1 ,x2 , ,xn 0 加入松弛变量: Max z = c1
12、 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn+ xn+m = bm x1 ,x2 , ,xn ,xn+1 , ,xn+m 0,18,显然,xj = 0 j = 1, , n ; xn+i = bi i = 1 , , m 是基本可行解 对应的基是单位矩阵。 以下是初始单纯形表: m m 其中:f = - cn+i bi j = cj - cn+i aij 为检验数 cn+i =
13、0 i= 1,m i = 1 i = 1 an+i,i = 1 , an+i,j = 0 ( ji ) i , j = 1, , m,1、 线 性 规 划 (续1.3),19,1、 线 性 规 划 (续1.3单纯形法解题例),例1。化标准形式: Max z = 50 x1 + 100 x2 s.t. x1 + x2 + x3 = 300 2 x1 + x2 + x4 = 400 x2 + x5 = 250 x1 , x2 , x3 , x4 , x5 0 最优解 x1 = 50 x2 = 250 x4 = 50(松弛标量,表示原料A有50个单位的剩余),20,注意:单纯形法中, 1、每一步运算
14、只能用矩阵初等行变换; 2、表中第3列的数总应保持非负( 0); 3、当所有检验数均非正( 0)时,得到最优单纯形表。,1、 线 性 规 划 (续1.3),21,1、 线 性 规 划 (续1.3),一般情况的处理及注意事项的强调(p45-55) 1.3.4段主要是讨论初始基本可行解不明显时,常用的方法。要弄清它的原理,并通过例1-14 例1-17掌握这些方法,同时进一步熟悉用单纯形法解题。 考虑一般问题: bi 0 i = 1 , , m Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 +
15、a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ,x2 , ,xn 0,22,1、 线 性 规 划 (续1.3),大M法: 引入人工变量 xn+i 0 i = 1 , , m ; 充分大正数 M 。 得到, Max z = c1 x1 + c2 x2 + + cn xn + M xn+1 + + M xn+m s.t. a11 x1 + a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn + xn+m = bm x1 ,x2 , ,xn ,xn+1 , ,xn+m 0 显然,