《运筹学的线性规划与动态规划》由会员分享，可在线阅读，更多相关《运筹学的线性规划与动态规划（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 显然，
