运筹学研究的基本步骤.ppt

《运筹学研究的基本步骤.ppt》由会员分享，可在线阅读，更多相关《运筹学研究的基本步骤.ppt（33页珍藏版）》请在三一办公上搜索。

1、,济南大学管理学院,运 筹 学,运筹学教程胡运权主编,绪 论,运筹学释义运筹学的来源运筹学的发展运筹学研究的基本特征运筹学研究的基本步骤运筹学主要分支简介,大英百科全书 中国大百科全书 辞海(1979年版)中国企业管理百科全书,一、运筹学释义,绪 论,大英百科全书,“运筹学是一门应用于管理有组织系统的科学”，“运筹学为掌管这类系统的人提供决策目标和数量分析的工具”,一、运筹学释义,绪 论,中国大百科全书,“用数学方法研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学。它可以用来预测发展趋势、制定行动规划或优选可行方案”,一、运筹学释义,

2、绪 论,辞 海,“主要研究经济活动与军事活动中能用数量来表达的有关运用、筹划与管理方面的问题它根据问题的要求，通过数学的分析与运算，作出综合性的合理安排以达到较经济较有效地使用人力物力。”,一、运筹学释义,绪 论,中国企业管理百科全书,“应用分析、试验、量化的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。”,一、运筹学释义,绪 论,名称来源运筹学一词在英国称为Operationa1 research，在美国称为operations research(缩写为OR)，可直译为“运用研究”或“作业研究”。1957年我国从“夫运筹帷幄之中，决

3、胜千里之外”（见史记高祖本纪)这句古语中抽取“运筹”二字，将OR正式译作运筹学，包含运用筹划以策略取胜等意义，比较恰当地反映了这门学科的性质和内涵。“夫运筹帷幄之中，决胜千里之外，吾不如子房；镇国家，抚百姓，给馈饷，不绝粮道，吾不如萧何；连百万之军，战必胜，攻必取，吾不如韩信。”,二、运筹学的来源,绪 论,思想体现 齐王赛马,绪 论,二、运筹学的来源,丁渭修皇宫,宋代真宗年间，一场大火烧掉皇宫。真宗皇帝命令大臣丁渭修复皇宫，他面临烧砖无土、大型建筑材料无法运输，清墟无处排放等重重困难。丁渭第一件事是将皇宫周围的大街小巷挖成河道，与河流相通。挖出来的土烧砖制瓦，解决了取土问题，这是短期目标，为修

4、皇宫服务。全国各地建筑材料水运到京城，由开挖的河道直接运到工地，省去二次运输，节约了一大笔资金，解决了运输问题。几年以后，皇宫修复了，建筑垃圾成山，他又叫人将垃圾填到挖的河道中去，恢复了原来的大街小巷，结果，皇宫修成了，街道恢复了，资金节省了，可谓“一石三鸟”。这是一个典型的长短联系的好决策，这种综合解决问题的思想便是出色的系统工程思想。,绪 论,丁渭修皇宫,正式使用：二十世纪三十年代后期的二战期间 英美-“运作研究”(operational Reserch)小组。通过科学方法的运用成功地解决了许多非常复杂的战略和战术问题。例如如何合理运用雷达有效地对付德国空袭；对商船队如何进行编队护航，在船

5、队遭受德国潜艇攻击时使船队损失最少；反潜深水炸弹在各种情况下 如何调整其爆炸深度，才能增加对德国潜潜艇的杀伤力等。,绪 论,二、运筹学的来源,英国第一个运筹小组：领导人，著名的物理学家MsBlackett（后来因在宇宙射线方面的研究成果而获得诺贝尔物理学奖）。组员：2位数学家，2位普通物理学家，1位理论物理学家，1位天体物理学家，l位测量员，3位生理学家，1位军官）。-“Blackett杂技团”。美国也成立一个运筹小组：领导人，物理学家Philip WMorse（美国运筹学会第一届主席）。组员与英国相仿，大多为自然科学家，包括数学家、物理学家，其中还有一位象棋大师。,绪 论,二、运筹学的来源,

6、运筹学在军事领域中的应用取得了显著效果。例如，在第二次世界大战中，德国潜艇严重威胁盟军运输船队。反潜战的一个重要问题是：当侦察飞机发现潜艇后，飞机投掷深水炸弹的最佳时间以及炸弹引爆的最佳深度应是多少?运筹工作者对大量统计数字进行认真分析后，提出：(1)应在潜艇浮出水面或刚下沉时，投掷深水炸弹；(2)炸弹起爆的最佳深度为离水面25英尺(当时深水炸弹所容许的最低起爆点)。空军采用上述建议后，使德国潜艇被摧毁数增加到400%。船只受敌机攻击时中弹数由47%降到29%。,绪 论,二、运筹学的来源,值得注意的是：当时许多实际问题的解决，仅应用了初等概率和统计。第二次世界大战以后，运筹学得到了很大的发展。

7、一方面，运筹学得到了广泛应用。它几乎涉及经济管理的所有领域；另一方面，在理论方面发展了一些数学分支，例如数学规划、应用概率、应用组合论、博弈论、数理经济学、系统科学等。大体可分为以下三个阶段：,绪 论,三、运筹学的发展,一、从l945年到50年代初，被称为创建时期。第一本运筹学杂志运筹学季刊(ORQuarterly)1950年于英国创刊。第一个运筹学会英国运筹学会于1948年成立。主要研究伦敦周围高炮的布置问题。当然高炮越多打掉敌机越多，漏掉越少，但高炮多到一定程度以后，打掉的敌机数增加甚微。所以选择多少高炮数为最优和怎样布置是他们要解决的问题。,绪 论,三、运筹学的发展,三、运筹学的发展,二

8、、50年代初期到50年代末期，运筹学的成长时期 最早建立运筹学会的国家是英国（1948），接着是美国（1952），法国（1956），日本和印度（1957）。我国的运筹学会建立在1980年。,绪 论,三、自60年代以来，运筹学迅速发展和普及时期 运筹学进一步细分为各个分支，专业学术团体迅速增多，更多期刊创办，运筹学书籍大量出版，更多学校将运筹学课程纳入教学计划。目前国际上著名的运筹学刊物有：Management Science（管理科学），Operations Research(运筹学)，Interfaces（相互关系），Journal of Operational Reseach Societ

9、y（英国运筹学研究学会期刊），European Journal of Operations Research（欧洲运筹学杂志）。国内比较著名的运筹学刊物：运筹学学报、管理科学学报、中国管理科学、运筹与管理、系统工程等。,绪 论,三、运筹学的发展,运筹学在中国的发展引入：中国第一个运筹学小组在钱学森、许国志先生的推动下在1956年于中国科学院力学研究所成立。1959年，第二个运筹学部门在中国科学院数学研究所成立。力学所小组与数学所的小组于1960年合并成为数学研究所的一个研究室，当时的主要研究方向为排队论、非线性规划和图论。五十年代后期，运筹学在中国的应用集中在运输问题上。“打麦场选址问题”；“

10、中国邮路问题”（管梅谷）。中国运筹学早期应用的亮点由华罗庚教授点燃的。,绪 论,三、运筹学的发展,中国运筹学会于1980年成立，作为中国数学会的一个分会。1982年成为国际运筹学联合会（IFORS）的成员。1992年中国运筹学会从中国数学会独立出来成为国家一级学会是学会发展史上的一个重要事件。近二十年来，中国运筹学工作者在信息科学、生命科学等现代高科技都作出了突出的贡献。例如，将全局最优化、图论、神经网络等运筹学理论及方法应用于分子生物信息学中的DNA与蛋白质序列比较、芯片测试、生物进化分析、蛋白质结构预测等问题的研究；在金融管理方面，将优化及决策分析方法，应用于金融风险控制与管理、资产评估与

11、定价分析模型等；在网络管理上，利用随机过程方法，研究排队网络的数量指标分析；在供应链管理问题中，利用随机动态规划模型，研究多重决策最优策略的计算方法。,绪 论,三、运筹学的发展,四、运筹学研究的基本特征,系统的整体观念多学科的综合模型方法的应用-制定决策是运筹学应用的核心，而建立模型则是运筹学方法的精髓。,绪 论,五、运筹学研究的基本步骤,一、分析和表述问题二、建立模型三、求解模型和优化方案四、对模型和由模型导出的解进行检验五、建立起对解的有效控制六、方案的实施,绪 论,六、运筹学主要分支简介,一、线性规划(Linear programming)二、非线性规划(nonlinear progra

12、mming)三、动态规划(dynamic programming)四、图与网络分析(graph theory and network analysis)五、存贮论(inventory theory)六、排队论(queueing theory,or waiting line)七、对策论(game theory)八、决策论(decision theory),绪 论,线性规划问题,某医院护士值班班次、每班工作时间及各班所需护士数如表所示。每班护士值班开始时向病房报到，并连续工作8小时。试决定该医院最少需多少名护士，以满足轮班需要？,动态规划问题,某公司打算在3个不同地区设置4个销售点，根据市场预测部

13、门估计，在不同地区设备不同数量的销售站，每月可得利润如表所示，试问应如何在各地区设置销售站，可使每月总利润最大？,图与图络分析,求解如图855所示的中国邮路问题，A点是邮局。,A,哥尼斯堡（Konigsberg）七桥问题。,图与图络分析,存贮论,对某种电子元件每月需求量为4000件，每件成本为150元，每年的存贮费为成本的10，每次订购费为500元。求：(1)不允许缺货条件下的最优存贮策略；(2)允许缺货(缺货费为每件每年100元)条件下的最优存贮策略。,排队论,某店仅有一个修理工人，顾客到达过程为Poisson流，平均每小时3人，修理时间服从负指数分布，平均需10分钟。求：(1)店内空闲的概

14、率；(2)有4个顾客的概率；(3)至少有1个顾客的概率；(4)店内顾客的平均数；(5)等待服务的顾客的平均数(6)平均等待修理时间；,对策论,“二指莫拉问题”，甲、乙二人游戏，每人出一个或两个手指，同时又把猜测对方所出的指数叫出来。如果只有一个人猜测正确，则他的赢得分数为二人所出指数之和、否则重新开始。试写出该对策中各局中人的策略集及甲的赢得矩阵，并说明是否存在某一种策略比其它策略更有利。再如“囚徒困境”,决策论,根据以往的资料，一家面包店每天所需面包数(当天市场需求量)可能是下列当中的某一个，100，150，200，250，300，但其概率分布不知道。如果一个面包当天没有卖掉，则可在当天结束

15、时每个0.15元处理掉。新鲜面包每个售价为o49元，成本为025元，假设进货量限制在需求量中的某一个，要求：(1)做出面包进货问题的决策矩阵；(2)用处理不确定性决策问题的方法确定最优进货量。,运筹学在科技体系中的地位,绪 论,一门科学只有成功地应用数学时，才算达到了完善的地步。-马克思,钱学森,钱学森（今）。中国著名物理学家，世界著名火箭专家。被誉为“中国导弹之父”。1934年毕业于交通大学（西安交），1934年在美国麻省理工学院和加利福尼亚理工大学学习。1938年获博士学位，后留任美国并从事火箭研究。1950年开始争取回归祖国，当时一位美国海军的一位高级将领金布尔说：“钱学森无论走到哪里，

16、都抵得上5个师的兵力，我宁可把他击毙在美国也不能让他离开。”因此钱学森受到美国政府迫害，失去自由，历经5年于1955年才回到祖国。1991年10月，国务院、中央军委授予钱学森“国家杰出贡献科学家”荣誉称号和一级英雄模范奖章。2007年感动中国组委会授予钱学森的颁奖词：在他心里，国为重，家为轻，科学最重，名利最轻。5年归国路，10年两弹成。他是知识的宝藏，是科学的旗帜，是中华民族知识分子的典范。,华罗庚-“烧水泡茶”的算法,1964年写统筹方法平话，“烧水泡茶”有五道工序：1、烧开水；2、洗茶壶；3、洗茶杯；4、拿茶叶5、泡茶。烧开水、洗茶壶、茶杯，拿茶叶是泡茶的前提。各道工序用时表：烧开水 15分，洗茶壶 2分，洗茶杯 1分，拿茶叶1分，泡茶1分方法比较：工序安排不同 甲：烧开水 同时，洗茶壶，洗茶杯，拿茶叶 乙：烧开水 之前，洗茶壶，洗茶杯，拿茶叶 丙：烧开水 之后，洗茶壶，洗茶杯，拿茶叶 花的时间不同，甲：16 分钟 乙：20 分钟 丙：20 分钟,