运筹学(绝密)-绪论与图解法概要ppt课件

单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,管理,运筹学,(OR),(美Operations Research),(英 Operational Research),管理运筹学 (OR)(美Operations Resear,1,学时数：64学时,教材：,运筹学教材编写组编运筹学，清华大学出版社,参考书：,其它版本的管理运筹学；,胡运权主编运筹学教程清华大学出版社；,牛映武主编运筹学 西安交通大学出版社；,成绩评定：,作业：15分；,考勤：15分；,期中考试：10分,期末考试：60分,学时数：64学时教材：参考书：成绩评定：,2,1 运筹学的产生和发展,运筹学是运用筹划的科学，,原意“作战研究”或“运用研究”。,一、 绪论,1 运筹学的产生和发展运筹学是运用筹划的科学，一,3,1.1,运筹学产生,运筹学的三个来源是军事、管理和经济,军事,特点是：定量化、系统化方法迅速发展；采集真实的实际数据；多学科密切协作；解决方法渗透物理学的思想。,（1）波得塞（Bawdsey)雷达站的研究,1939年,任务：如何最好地运用空军及新发明的雷达保卫国家,1.1 运筹学产生军事（1）波得塞（Bawdsey)雷达站,4,（2）Morse小组领导的运筹学小组,目标：打破德军对英吉利海峡的封锁,建议：用飞机代替舰艇投掷水雷，起爆深度由100米改为25米，当敌舰刚下潜时攻击；,运送物资的船队及护卫舰的编队由小规模、多批次改为大规模、少批次。丘吉尔采纳了建议,（3）英国战斗机援法,德军突破马奇诺防线，法军节节败退，英军参与抗德。英军的战机均在法国上空与德军作战，指挥维护在法国。法国请求增援10中队，邱吉尔同意。,但运筹学小组认为：按现在的方式，英军的援法战机两周内会全军覆灭；不增加战机，而应以英国本土为基地与德军战斗，使局面大为改观。,（2）Morse小组领导的运筹学小组（3）英国战斗机援法,5,经济,冯,诺意曼（Von.neumann)对策论与经济行为,管理,康托洛维齐（Kantorovich),生产配置问题、原材料的合理利用、运输问题等,生产组织与计划中的数学方法,经济管理,6,1.1,运筹学的发展,运筹学的发展大概分三个阶段,第一个阶段蓬勃生长期,39年英国成立了世界上第一个运筹学工作小组，,从事防空预警系统的研制（研究如何合理运用雷达）,1939年前苏联的康托洛维奇提出类似线性规划模型1960年最佳资源利用的经济计算，获诺贝尔奖,1.1 运筹学的发展运筹学的发展大概分三个阶段第一个阶段,7,1947年美国数学家，提出线性规划模型及单纯形算法 42年美国成立运筹学工作小组，研究战斗行动效能，行动方式战争结束，Mores和Kimball合著第一部运筹学专著“运筹学的方法”战后，运筹学的应用领域从军事扩展到其它各领域,1947年美国数学家，提出线性规划模型及单纯形算法,8,1948年英国成立运筹学学会1952年美国成立运筹学学会1956年法国成立运筹学学会1959年英、美、法成立运筹学联合会,第二阶段危机期,六、七十年代,第三阶段运筹学发展的正确之路,理念更新、实践为本、学科交融,我国运筹学的发展,1948年英国成立运筹学学会1952年美国成立运筹学学,9,2 运筹学的释义,运筹学具有如下的性质特点,（1）运筹学是一门应用科学,(2) 运筹学的目的是寻找最佳解决问题的方案，,为决策者的最优决策提供依据,(3) 以数学为基础提供定量分析,（4）以计算机为手段,（5） 以软科学研究软系统,（6） 多学科专家集体协作研究,2 运筹学的释义运筹学具有如下的性质特点（1）运筹学是一,10,由一支综合性的队伍，采用科学的方法，为一些涉及到有机系统（人-机）的控制系统问题提供解答，为该系统的总目标服务的学科。钱学森,运用科学方法来解决工业、商业、政府、国防等部门里有关人力、机器、物资、金钱等大型系统的指挥或管理中所出现的复杂问题的一门学科。其目的是“帮助管理者以科学方法确定其方针和行动”英国运筹学会,运筹学是应用系统的、科学的、数学分析的方法，通过建模、检验和求解数学模型而获得最优决策的科学。近代运筹学工作者,运筹学的定义,执行部门对所控制的业务作出决策提供数量上的科学或利用所应用科学，执行部门对其所属业务作出决策提供数量上依据的一门科学。Morse,由一支综合性的队伍，采用科学的方法，为一些涉,11,规划论,线性规划,、目标规划、非线性规划、,整数规划,、,动态规划,、组合规划等,图与网络,存储论,排队论,对策论 决策论 仿真 马尔科夫过程 可靠性 多目标规划 ,3 运筹学的分支,规划论线性规划、目标规划、非线性规划、整数,12,3 运筹学的工作步骤,(1) 提出和形成问题。,即要弄清问题的目标，可能的约束，问题的可控变量以及有关参数；,(2) 建立模型。,即把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示出来；,(3) 求解。,用各种手段( 主要是数学方法，也可用其他方法 )将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机，解的精度要求可由决策者提出；,(4) 解的检验。,首先检查求解步骤和程序有无错误，然后检查解是否反应现实问题；,(5) 解的控制。,通过控制解的变化过程决定对解是否要作一定的改变；,(6) 解的实施。,是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清楚用法、在实施中可能产生的问题和修改。,3 运筹学的工作步骤(1) 提出和形成问题。即要弄清问,13,4 本课程的要求,本课程的授课对象是管理科学与工程类及交通运输类专业,本科生，属管理类专业技术基础必修课。,学生通过学习该课程，应了解管理运筹学对优化决策问题进,行定量研究的特点，,理解,线性规划、整数规划、动态规划、图与,网络、排队论和库存论,等分支的基本优化,原理，掌握,其中常用的,模型和算法,，,具有一定的建模能力。,先修课程主要为,线性代数和概率统计,，学生对它们的掌握程,度直接影响本课程的学习，所以要求学生课前要做必要的复习。,学习方法：理解、掌握基本理论和方法的基础上，适当作些,习题。,4 本课程的要求本课程的授课对象是管理科学与工程类及,14,二. 线性规划 (LP )( Linear Programming),第一章,线性规划与单纯形法,1947年由美国空军G.B.Dantzig提出。,本部分是课程的最重要部分,二. 线性规划 (LP )( Linear Progra,15,1 线性规划问题及其数学模型,1 线性规划问题及其数学模型,16,11 问题的提出,11 问题的提出,17,利润最大 目标函数 max,z,= 2,x,1,+ 3,x,2,利润最大 目标函数 max z = 2x1+ 3x2,18,例2 某工厂用钢与橡胶生产3种产品A、B、C，有关资料如下表,40,45,24,3,3,2,2,3,1,A,B,C,单位产品利润,单位产品橡胶量,单位产品钢消耗量,产品,已知每天可获得100单位的钢和120单位橡胶，问每天生产A、B、C各多少使总利润最大？,解,：设x,1,，x,2，,x,3,分别为A、B、C日产量，则有,约束条件,2 x,1,+ 3x,2,+ x,3,100,3x,1,+ 3x,2,+ 2x,3,120,x,1,0，x,2,0， x,3,0称x,1,，x,2 ，,x,3,0为决策变量,目标函数： max z=40x,1,+45x,2,+24x,3,例2 某工厂用钢与橡胶生产3种产品A、B、C，有关资料如下表,19,2万m,3,1.4万m,3,2万m31.4万m3,20,2万m,3,1.4万m,3,2万m31.4万m3,21,运筹学(绝密)-绪论与图解法概要ppt课件,22,运筹学(绝密)-绪论与图解法概要ppt课件,23,运筹学(绝密)-绪论与图解法概要ppt课件,24,运筹学(绝密)-绪论与图解法概要ppt课件,25,x,1,x,2,0,4,Q,2,(4,2),Q,1,Q,3,Q,4,4,x,1,=16,4,x,2,=,12,x,1,+2,x,2,=8,2x,1,+3x,2,=0,3,Q,2,4,o,.向着目标函数的优化方向平移等值线，直至得到等值线与可行域的最后交点，这种点就对应最优解。,x1x204Q2(4,2)Q1Q3Q44x1=164x2=1,26,线性规划问题解的存在情况：,(1)存在唯一最优解,x,1,x,2,0,4,Q,2,(4,2),Q,1,Q,3,Q,4,4,x,1,=16,4,x,2,=,12,x,1,+2,x,2,=8,2x,1,+3x,2,=0,3,Q,2,如例1,线性规划问题解的存在情况：(1)存在唯一最优解x1x204Q,27,（2）有无穷多最优解,若将例1目标函数变为 max,z,= 2,x,1,+ 4,x,2,，则问题变得存在无穷多最优解。如图,x,1,x,2,0,4,Q,2,(4,2),Q,1,Q,3,Q,4,4,x,1,=16,4,x,2,=,12,x,1,+2,x,2,=8,2x,1,+,4,x,2,=0,3,Q,2,（2）有无穷多最优解 若将例1目标函数变为 max,28,（3）有无界解( 无有限最优解或无最优解 ),z,（4）无可行解（可行域为空集）,思考：,1。线性规划问题可以存在有限多个最优解,2。可行域有界时必有最优解,3。可行域无界时没有最优界,（3）有无界解( 无有限最优解或无最优解 ) z（4）无可行,29,用图解法求下面问题的解,1,无界,2,不可行,用图解法求下面问题的解1无界2不可行,30,