运筹学ppt课件.ppt
《运筹学ppt课件.ppt》由会员分享,可在线阅读,更多相关《运筹学ppt课件.ppt(66页珍藏版)》请在三一文库上搜索。
1、1,运筹学,1 运筹学的释义和发展简史 2 运筹学的特征和方法 3 运筹学的分支 4 运筹学应用与管理科学,2,名称的由来 Operation Research 运筹帷幄 “史记” 运作研究 发展历程,运筹学的由来与发展,3,引入数学方法解决实际问题 -定性与定量方法结合 系统与整体性 -从全局考察问题 应用性 -源于实践、为了实践、服务于实践 交叉学科 -涉及经济、管理、数学、工程和系统等 多学科 开放性 -不断产生新的问题和学科分支 多分支 -问题的复杂和多样性,运筹学的性质与特点,4,线性规划,数 学 规 划,非线性规划,整数规划,动态规划,学 科 内 容,多目标规划,双层规划,组 合
2、优 化,最优计数问题,网络优化,排序问题,统筹图,随 机 优 化,对策论,排队论,库存论,决策分析,可靠性分析,运筹学的主要内容,5,成熟的学科分支向纵深发展 新的研究领域产生 与新的技术结合 与其他学科的结合加强 传统优化观念不断变化,运筹学的发展趋势,6,运筹数学,系统工程,管理与运筹学,问题与方法,方法与应用,核心算法与工具,基础理论,应用理论,应用技术,运筹学,运筹学的学科地位,7,模型要素 变量可控因素 目标优化的动力和依据 约束内部条件和外部约束 研究内容,建模,概念,最优性条件,算法,灵敏度分析,最优化模型,实例,8,运筹学(Operations Research)释义 运筹学是
3、应用数学方法对经济、民政、国防等部门在内外环境的约束条件下合理分配安排人力、物力、财力等资源,使实际系统有效运行的技术科学。它可以用来预测发展趋势,制定行动规划或优选可行方案。 运筹学的产生和发展 运筹学产生于第二次世界大战,主要用于解决如何在与德军的对抗中最大限度地杀伤敌人,减少损失。 二战以后,运筹学得到了快速的发展,成立了国际运筹学联合会(IFORS),形成了许多分支. 运筹学有广泛应用 运筹学在军事,生产、决策、运输、存储、排队等经济管理领域有着广泛的应用。,9,运筹学的特征 (1)系统的整体观念, (2)多学科交叉, (3)模型方法应用 决策步骤: 1)分析、表述问题; 2)建立模型
4、; 3)求解和优化方案; 4)测试模型,修正模型; 5)解的检验、灵敏性分析等; 6)实施方案;,2 运筹学的特征和步骤,10,线性规划 非线性规划 动态规划 整数线性规划 图与网络分析 存储论 排队论 对策论 决策分析,3 运筹学的分支,11,合伙 原则 催化原则 渗透原则 独立原则 宽容原则 平衡原则,12,生产计划:生产作业的计划、日程表的编排、合理下料、 配料问题、物料管理等,追求利润最大化和成 本最小化 库存管理:多种物资库存量的管理,库存方式、库存量等 运输问题:确定最小成本的运输线路、物资的调拨、运输 工具的调度以及建厂地址的选择等 人事管理:对人员的需求和使用的预测,确定人员编
5、制、 人员合理分配,建立人才评价体系等 市场营销:广告预算、媒介选择、定价、产品开发与销售 计划制定等 财务和会计:预测、贷款、成本分析、定价、证券管理、 现金管理等,4 运筹学的应用和管理科学,13,由国际运筹与管理科学协会(INFORMS)和它的管理科学实践学会(College for the Practice of the Management Sciences)主持评奖的负有盛名的弗兰茨厄德曼(Frany Edlman)奖,就是为奖励优秀的运筹学在管理中的应用的成就设立的,该奖每年举行一次,在对大量富有竞争力的入闱者进行艰苦的评审后,一般有六位优胜者获奖。关于这些获奖项目的文章都在第二
6、年发表在著名刊物Interface的第一期上,下面列表就是发表在Interface期刊的一些获奖项目。,14,15,16,17,第二章 线性规划基本概念,1 线性规划问题及模型 2 图解法 3 单纯形方法 4 线性规划应用举例分析,18,1 问题的提出,例1. 某工厂在计划期内要安排、两种产品的生产,已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制,如下表: 问题:工厂应分别生产多少单位、产品才能使工厂获利最多? 线性规划模型: 目标函数:Max z = 50 x1 + 100 x2 约束条件:s.t. x1 + x2 300 2 x1 + x2 400 x2 250 x1
7、, x2 0,19,线性规划的组成要素: 目标函数 Max F 或 Min F 约束条件 s.t. (subject to) 满足于 决策变量 用符号来表示可控制的因素 建模步骤 1.理解要解决的问题,了解解题的目标和条件; 2.定义决策变量( x1 ,x2 , ,xn ),每一组值表示一个方案; 3.用决策变量的线性函数形式写出目标函数,确定最大化或最小化目标; 4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件,20,一般形式 目标函数: 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,21,对于只有两个决策变量的线性规划问题,可以在平面直角坐标系上作图表示线性规划问题的有关概念,并求解。下面通过例1详细讲解其方法。 例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),2 图 解 法,22,(1)画出线性规划问题
9、的可行域,如图所示。,23,(2)目标函数z=50x1+100x2,当z取某一固定值时得到一条直线,直线上的每一点都具有相同的目标函数值,称之为“等值线”。平行移动等值线,当移动到B点时,z在可行域内实现了最大化。得到最优解: x1 = 50, x2 = 250, 最优目标值 z = 27500,24,重要结论: 如果线性规划有最优解,则一定有一个可行域的顶点对应一个最优解; 无穷多个最优解。若将例1中的目标函数变为max z=50x1+50x2,则线段BC上的所有点都代表了最优解; 无界解。即可行域的范围延伸到无穷远,目标函数值可以无穷大或无穷小。一般来说,这说明模型有错,忽略了一些必要的约
10、束条件; 无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x21200,则可行域为空域,不存在满足约束条件的解,当然也就不存在最优解了。,25,线性规划的标准化引入松驰变量(含义是资源的剩余量) 例1 中引入 s1, s2, s3 模型化为 目标函数:Max z = 50 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3 约束条件:s.t. x1 + x2 + s1 = 300 2 x1 + x2 + s2 = 400 x2 + s3 = 250 x1 , x2 , s1 , s2 , s3 0 对于最优解 x1 =50 x2 = 250 , s1 = 0 s2 =5
11、0 s3 = 0 说明:生产50单位产品和250单位产品将消耗完所有 可能的设备台时数及原料B,但对原料A则还剩余50千克。,26,线性规划的标准化 线性规划标准形式 目标函数: 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,bi 0,27,可以看出,线性规划的标准形式有如下四个特 点: 目标最大化; 约束为等式; 决策变量均非负; 右
12、端项非负。 对于各种非标准形式的线性规划问题,我们总可 以通过以下变换,将其转化为标准形式:,28,1.极小化目标函数的问题: 设目标函数为 Min f = c1x1 + c2x2 + + cnxn (可以)令 z -f , 则该极小化问题与下面的极大化问题有相同的最优解, 即 Max z = - c1x1 - c2x2 - - cnxn 但必须注意,尽管以上两个问题的最优解相同,但它们 最优解的目标函数值却相差一个符号,即 Min f - Max z,29,2、约束条件不是等式的问题: 设约束条件为 ai1 x1+ai2 x2+ +ain xn bi 可以引进一个新的变量s ,使它等于约束右
13、边与左 边之差 s=bi(ai1 x1 + ai2 x2 + + ain xn ) 显然,s 也具有非负约束,即s0, 这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn+s = bi,30,当约束条件为 ai1 x1+ai2 x2+ +ain xn bi 时, 类似地令 s=(ai1 x1+ai2 x2+ +ain xn)- bi 显然,s 也具有非负约束,即s0,这时新的约 束条件成为 ai1 x1+ai2 x2+ +ain xn-s = bi,31,为了使约束由不等式成为等式而引进的变量s,当 不等式为“小于等于”时称为“松弛变量”;当不等式 为“大于等于”时称为“剩余变
14、量”。如果原问题中有 若干个非等式约束,则将其转化为标准形式时,必须 对各个约束引进不同的松弛变量。,3.右端项有负值的问题: 在标准形式中,要求右端项必须每一个分量非负。当某一个右端项系数为负时,如 bi0,则把该等式约束两端同时乘以-1,得到:-ai1 x1-ai2 x2- -ain xn = -bi。,32,例:将以下线性规划问题转化为标准形式 Min f = 2 x1 -3x2 + 4 x3 s.t. 3 x1 + 4x2 - 5 x3 6 2 x1 + x3 8 x1 + x2 + x3 = -9 x1 , x2 , x3 0 解:首先,将目标函数转换成极大化: 令 z= -f =
15、-2x1+3x2-4x3 其次考虑约束,有2个不等式约束,引进松弛变量 x4,x5 0。 第三个约束条件的右端值为负,在等式两边同时乘-1。,33,通过以上变换,可以得到以下标准形式的线性规划问题: Max z = - 2x1 + 3 x2 - 4x3 s.t. 3x1+4x2-5x3 +x4 = 6 2x1 +x3 -x5= 8 -x1 -x2 -x3 = 9 x1 ,x2 ,x3 ,x4 ,x5 0 在标准形式中,必须每一个变量均有非负约束。当某一个变量xj没 有非负约束时,可以令 xj = xj- xj” 其中 xj0,xj”0 即用两个非负变量之差来表示一个无符号限制的变量,当然xj的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 ppt 课件
链接地址:https://www.31doc.com/p-2709421.html