本科毕业论文---运筹学在实际生活中的应用研究本科.doc

新疆师范大学2015本科毕业论文（设计） 2015届本科毕业论文(设计) 论文题目：运筹学在实际生活中的应用研究 学 院：数学科学学院 专业班级：信息与计算科学11-5班 学生姓名：王瑞琦 指导老师：张新东 答辩日期：2015年5月5日新疆师范大学教务处新疆师范大学2015本科毕业论文（设计）目 录引言.11 运筹学思想的产生和学科发展概述.2 2 运筹学的主要研究内容.4 2.1 确定型模型.4 2.1.1线性规划.4 2.1.2非线性规划.5 2.1.3图与网络.6 2.1.4动态规划2.2 概率型模型.7 2.2.1存贮论.7 2.2.2排队论.8 2.2.3决策分析.10 2.2.4博弈论.113 运筹学解决现实问题举例与研究.133.1 机械产品生产计划问题. .133.2存贮过程中的费用最小问题.164 运筹学在应用情况分析.205 总结.22参考文献.23致谢 .24 i运筹学在实际生活中的应用研究摘要：本文主要对运筹学在实际生活中的应用进行研究，使大家对运筹学在生活中的应用方法与产生的效果有大致认识。首先讲解运筹学的抽象模型，然后列举了军事指挥、运输等方面的实例，最后分析了运筹学应用于各个领域中的效果，对比了目前中外各领域运筹学应用的实际情况。关键词：运筹学，概率型模型，确定型模型，最优化问题，资源分配问题 Study on Application of operational Research in real life.Abstract: This paper mainly studied the application of operations research in real life, we roughly understanding of research methods in life and the effects of. First of all on the abstract model of operations research and management science, and then gives examples of mechanical production, logistics, storage and so on, finally analyses the application of operational research in various fields effect, compared to the actual situation at home and abroad in various fields of the application of operational research.Key words: Operational Research, Probability model, Deterministic model, Decision-making problem,Resource allocation problem.iii引言运筹学作为一门新兴的应用科学是近代数学应用的一个重要发展分支，不同的研究对象和角度，赋予了它不同的定义，不同国家都曾给出过定义，但本质上，这门学科都被看作是解决生产、管理领域出现的一些实际问题进行提炼，然后应用数学方法给出决策。运筹学作为一种科学的方法和工具，已经在诸如服务、人口、对抗、资源分配、教育、医疗等诸多社会领域扮演越来越重要的角色。从实践方面看，运筹学应社会需求逐渐发展，从教育方面看，运筹学将成为多专业的学科基础是历史和逻辑的辩证统一。本文首先介绍了运筹学思想的产生和学科的发展，使大家对运筹学有一个大体的了解，继而介绍了运筹学的研究内容，给出运筹学研究的两大类模型，在这些模型的基础上，列举出几个运筹学应用的实际案例，从案例中了解运筹学在决策中的一些重要作用。最后，分析了当下全社会对于运筹学的应用情况、应用效果的分析，对于学科前景有一个整体把握。 1 运筹学思想的产生和学科发展概述1) 运筹学思想的产生最初的运筹学思想在中国古代的历史中源远流长。早在公元前6世纪春秋时期，著名的军事家孙武的作品孙子兵法就是当时的军事运用运筹思想的集中体现，公元前4世纪的战国时期，军事家孙膑的“斗马术”就是中国古代运筹思想运用的另一个著名的例子，其思想体现为不争一局得失，而为求得全盘的胜利，是全局最优化的一个经典案例。公元前3世纪楚汉相争，刘邦曾赞誉张良“运筹帷幄之中，决胜千里之外”，就是对他运筹思想的高度评价。北宋时期的沈括关于军事中后勤问题的分析和计算则是更具现代示范意义的运筹学范例1。随着历史的发展，运筹学除了在军事领域的成功运用之外，在中国古代的农业、工程技术、运输等方面也有大量的运筹学运用的典范。北魏时期的齐民要术曾记载古代劳动人民根据天气、地理条件合理的规划农事的经验就体现了运筹学的要义，例如在作物连种和播种时机中的“谷田不可连作，必须岁易”可以视为近代运筹学中决策问题的最初解决方案。西汉时期首都长安是的选址、水陆枢纽的设计，宫殿、市井、街道的统筹布局等方面都体现了运筹的思想。中国历史上应对黄河决口的封堵提出过分阶段作业的方案，这个方案把经济、人力和实际工作效果等方面综合考虑，相比一次作业效果更优。这些都是最初的运筹学思想的源头2）运筹学的学科发展概述运筹学作为一个独立的学科，是从20世纪30年代出现并逐渐发展形成的。其实从20世纪出期，就有了为现代运筹学奠定基础和雏形的早期工作。运筹学研究的其他模型诸如库存论模型、决策论、博弈论等方面的奠基工作都是在20世纪开始出现的。而运筹学真正开始发展则在1935年，英国空军为了应对德国飞机的空袭研究了新的雷达系统，但是这个系统经常送来矛盾的信息，需要对这些信息加以协调和关联，达到改进作战效能的目的。为此，英国皇家空军由一批科学家为核心，成立了运筹学小组，目的是对新战术实验和战术效率进行评价，结果令人满意。受到这种成功效果的激励，美国也在自己的军队中建立了运筹学相关的小组，并命名为“Operations Research”.二战结束后，军方从事运筹学工作的已经超过了700人，他们中的大部分继续在军事部门继续效力，这也推动了运筹学的房展，运筹学的队伍被扩大了。另一部的工作人员则在民间成立了许多运筹学的小组。20世纪40年代后期，运筹学开始进入民用工业，并取得了可喜的成绩；大规模的新兴行业开始出现，迫切的需要对新的管理结构和复杂的生产结构进行分析，运筹学再次站到了历史的舞台中间，动态规划等问题被一一提出，在这样的推动下，运筹学得到了迅速发展。2 运筹学的主要研究内容2.1 确定型模型 2.1.1线性规划线性规划是数学规划中应用最为广泛的问题，通常用来研究设备最佳运行、资源最优利用的问题。下面列举一个简单的线性规划模型的例子，是大家对线性规划有初步了解。例1：成年人每天需要从食物中摄取的营养以及四种食品所含营养和价格见下表。问如何选择食品才能在满足营养的前提下使购买食品的费用最小？表1：食物的营养价值及价格食品名称热量(kcal)蛋白质(g)钙（mg）价格（元）牛肉10005040014鸡蛋800602006大米900203003青菜200105002营养需求量300055800解：min z=14s.t .这是一个典型的线性规划模型，问题的目的是达到费用最低，即达到目标的最优规划，求解线性规划问题的一般步骤是：找出实际问题的约束条件确定目标函数化为标准型求数值解实际问题中验证。求线性规划问题数值解的方法有很多，常见的有图解放、单纯形法、人工变量法等。2.1.2非线性规划非线性规格问题的形势是多种多样的，在一些问题中，可能含有边际收益递增或递减的活动，或者约束函数是非线性的，又或者利润曲线是不连续的几段曲线。例2：股票投资组合中的风险与回报有如下表的关系，为了达到成本和收益的平衡，改如何选择投资组合？表2：3支股票的回报与风险股票价格/千元预期回报/千元风险投资组合交叉风险1602541与222402091与3-1350912与3-1.5解：设相应的决策变量是(i=1,2,3)分别表示股票的购买量，则投资组合的非线性规划模型为min z = 4s.t.非线性规划的手工计算一般比较复杂，本文推荐读者使用数学软件来求解此类问题，常见的解决非线性规划问题的软件有WinSQB、LINGO等，这里采用LINGO，这款软件对于模型的维护相对方便，对于更加复杂的非线性规划问题也能求解。这里给出一个包括预期回报、风险以及最优解的求解结果，见下表：表3：收益与对应风险结果收益股票1股票2股票3风险收益股票1股票2股票3风险000003006.4162.25710.495246.76501.0030.3541.9826.753509.1023.1846.531432.591002.0070.7083.96527.0140011.7884.1102.566765.291503.0101.0615.94760.774501010015002004.0131.4157.929108.0350002505624.882504.0171.7699.912168.82.1.3图与网络在日常生活中，我们经常碰到各种各样的图：公路或铁路图，管线布置网图等等。运筹学中研究的图则是上述这些图的抽象概括，它表明一些研究对象和这些对象之间的联系。通常我们用点表示研究对象，用点之间的连线表示这些对象之间的联系，则我们给出一个图的定义：图G是一些点和这些点之间的边的集合记，作G=式中V是点的集合，E是边的集合，运筹学中的图只关心图中有多少个点，哪些点之间存在连线，是区别于几何学中的图的概念的2。网络图中从一点到其他点的最短距离是由Dijkstra算法求解的。但实际问题中如果采用该方法对求网络中任意两点之间的最短距离就很麻烦，这里介绍一种矩阵计算法求最短距离。例3：假设有7个村子，决定联合办一所小学，各村小学生人数为30,40,25,20,50,60,60，那么小学应该建在那个村子，小学生上学走的路程最短。表4：学生到学校的路程小学建于下列村子时小学生上学所走的路程01506021021018030020002808020016032050175015012510020014040120060401203502502501500501503602402401206002406004804803601802400总路程1700 1335 143010708357701330分析表格可知，小学建于为最优方案。2.1.4动态规划动态规划是一种研究多阶段决策问题的理论和方法。动态规划的几个要素是：指标函数，策略，决策，状态，阶段状态转移规律。这类问题分为两大类，确定性动态规划模型和随机性动态规划模型。顺序解法和逆序解法是求解动态规划问题的两种基本方法，实际问题中采用较多的是逆序解法3。2.2 概率型模型2.2.1存贮论存贮问题研究中的基本概念：订货-到货间隔，订货费用，存贮费用，缺货损失，独立需求，依赖需求。存贮问题是一个社会生产和服务中广泛存在的一个问题。目的主要是为了使生产平稳进行。例4 如某卫生服务单位需要某货品每年20000件，厂家给出每次不同购货件数的不同单价，如下表5。已经知道每次订货费用约50元因为货品损坏、变质失效的经济损失在存贮费用中占较大比例，存贮费用与货品价格有关，此卫生服务单位存贮此货品的费用是货品价值的20%。问一次订货多少使期望损失为最小？表5：订货数量与单价购买数量范围（件）单价（元）1-199915.002000-499913.505000-799912.508000-1999912.0020000以上11.50解： 首先求出在不同单价下，即不同存贮成本下的最优订货量。从最小单价开始，直到计算的订货量落在该单价对应的订货量范围内。= 从计算结果看，前4个单价下计算的最优订货量并不在应享受的单价内，只有第五个计算结果落在单价覆盖的购买数量范围内。此订货量也是此单价下保证存贮总费用最低的最大订货量，一般用表示。 下一步是计算订货量为的总存贮费用，并与大于 的其他单价下最小订购量总存贮费用对比，他们中的最小值即此模型的最优订货量。根据公式 C(817)=0.215817/2 + 5020000/817 +2000015 =302449（元）C(2000)=0.213.52000/2 + 5020000/2000 +2000013.5 =273200（元）C(5000)=0.212.55000/2 + 5020000/5000 +2000012.5 =256450（元）C(8000)=0.2128000/2 + 5020000/8000 +2000012 =249725（元）C(20000)=0.211.520000/2 + 5020000/20000 +2000011.5=253050（元） 最小值是249725，因此=8000（件）。2.2.2排队论一个排队系统或称服务系统（service system），有三个基本组成部分：即输入过程（arrival process ）、排队规则（queue discipline）和服务规则（service discipline）4。1 输入过程：顾客到达排队系统的规律，通常用到达时间间隔或单位时间内顾客到达数的概率分布描述；按到达的时间间隔分有确定的时间间隔和随机的时间间隔；按顾客到达的方式有单个到达和成批到达；从顾客源总体看，分有限源总体和无限源总体。2排队规则：排队系统一般分为等待制、损失制和混合制5。(1) 等待制：顾客到达系统时，如果服务台没有空闲，则顾客排队等候服务(2) 损失制：顾客到达系统时，如果服务台没有空闲，则顾客离去，另求服务如没有足够医生或医疗器械救治急诊患者，医院药物、卫生材料暂缺等。(3) 混合制：它是介于等待制和损失制之间的形式方式有：3服务机构：指排队系统中服务台的个数、排列及服务方式。例5 某医院欲购一台X光机，现有四种可供选择的机型已知就诊者按泊松分布到达，到达率每小时4人。四种机型的服务时间均服从指数分布，其不同机型的固定费用，操作费，服务率见表6。若每位就诊者在系统中逗留所造成的损失费为每小时15元，试确定选购哪一类机型可使综合费（固定费+操作费+逗留损失费）最低。表6：四种机型的使用费用和服务率机型固定费用元/小时操作费用元/小时服务率人/小时86051075618847201208解 该问题属/ 1 / / 系统，单列，FCFS规则。依题意只需计算各种机型在单位时间内的综合费。已知：设综合费为： 表7：四种机型在1小时内的综合费用机型固定费用操作费逗留损失费综合费80.84846011610502309018482086206011595可见选用C型X光机其综合费最小2.2.3决策分析决策的基本概念：为决策者分析具有不确定性的复杂问题并辅助决策的一套概念和系统分析方法。需要进行决策分析的问题通常具有如下的一些特性：不确定性，动态性，多目标性，模糊性，群体性。例6 某个商人以每个0.35元购进糖果，每个0.50元卖出，否则会因为溶化而损失，盈亏情况如下，这个商人每天至少想赚30元，那么最优的分配方案是？表8：不同购买量下的盈亏 买进卖出010020030040050000.010-35-70-105-140-1751000.05015-20-55-90-1252000.1001530-5-40-753000.30015304510-254000.30015304560255000.2401530456075计算不同购买量盈利大于30元的概率设B为购进量a而卖出量这一事件，通过计算可得相应的概率如下表9表9：盈利大于30的概率表aP000.940.840.540.24可见行动最好，实现盈利达30元的概率最大。E(A1)=200.3+120.5+(-12)0.2=9.6E(A2)=160.3+100.5+(-10)0.2=7.8E(A3)=120.3+60.5+(-8)0.2=5 最优方案是：A12.2.4博弈论博弈论及博弈现象的要素：博弈论是研究博弈现象的规律的数学理论和方法。博弈现象的要素：局中人（参与人）：二人或多人；行动与策略有限或无限；信息:完全或不完全；支付函数：可正可负。图2：对策的分类例7：以齐王赛马为例说明：齐王赛马：二人非合作零和对策;局中人齐王和田忌。策略：上 、中、下三种等级的马的组合，比三次，有六组策略：( 上，中，下) 、 ( 中，上，下) 、 ( 上，下，中) 、 ( 中，下，上) 、 ( 下，上，中) 、 ( 下，中，上) .对齐王，这六组策略用表示,对田忌用表示。支付函数:赢了得一千金，输了付一千金。结果见下表10。表10：赛马胜负情况31111-11311-111-13111-11131111-1131111-1133 运筹学解决现实问题举例与研究3.1 机械产品生产计划问题案例：机械加工厂生产7种产品。该厂有以下设备：四台磨床、两台立式钻床、三台水平钻床、一台镗床和一台刨床6。每种产品的利润（单位：元/件，在这里，利润定义为销售价格与原料成本之差）一级生产单位产品需要的各种设备的工时（小时/件）如表11所示，其中短划线表示这种产品不需要相应的设备加工。表11：不同产品利润率产品1234567单位产品利润10634193磨床0.50.7-0.30.20.5立钻0.12-0.3-0.6-水平钻0.260.8-0.6镗钻0.050.03-0.070.10-0.08刨床-0.01-0.05-0.05从一月份到六月份，每个月中需要检修设备见下表（在检修月份，检修设备完全不能用于生产）。每个月各种产品的市场销售量上限如4表所示。每种产品的最大库存量为一百件，库存费用每件每月0.5元，在一月初，所有产品都没有库存，而要求在六月底，每种产品都有50件库存。工厂每天开两班，每班8小时，为简单起见，假定每月都工作24天。表12：上半年计划检修设备数月份计划检修设备及台数月份计划检修设备及台数一月一台磨床四月一台立式钻床二月三台立式钻床五月一台磨床、一台立式钻床三月一台镗床六月一台刨床、一台水平钻床表13：上半年生产计划产品 1 234567一月500 1000300300800200100二月600 5002000400300150三月300 60000500400100四月200 3004005002000100五月0 10050010010003000六月500 500100300110050060生产过程中，各种工序没有先后次序要求；（1） 制定六个月的生产、库存、销售计划 使得六个月的总利润最大；（2） 最优设备检修设备计划问题，构造一个最优设备检修计划模型，使在这半年中设备的检修台数满足案例中的要求而使利润最大。分析：要使产品利润最高，也就是说每个月的各种产品的加工，销售，库存三个方面的费用的一个混合约束使得总利润最大。假设这三个变量分别是xij ,yij ,zij;(i=1,2,3,4,5,6;j=1,2,3,4,5,6,7)。现在找一下第三个变量之间的关系， 即第i-1月的库存量+第i月的生产量=第i月的销售量+第i月的库存量。一月份之前是没有库存的，但是题目要求在六月份各种产品的库存是50，即对第j种产品，有x1j-y1j-z1j=0;z1j+x2j-y2j-z2j=0;z5j+x6j-y6j=50.(j=1,2,3,4,5,6,7)这是库存量的约束条件。总共42个约束。再看工时的约束：先看一月份的，以后月份类推；0.5x1j+0.7x2j+0.3x5j+0.2x6j+0.5x7j1152;0.1x1j+0.2x2j+0.3x4j+0.6x6j768;0.2x1j+0.8x3j+0.6x71152;0.05x1j+0.03x2j+0.07x4j+0.1x5j+0.08x7j384;0.01x1j+0.05x5j+0.05x7j384;xij0;(i=1,2,3,4,5,6;j=1,2,3,4,5,6,7)这是生产量的约束 总共有67=42个约束。再看销售量的约束：由表4得到：y11500；y121000； y21600; y61500;.yij某值，此值由表4相应得到。这是销售的限制，总共42个约束。建立利润函数线性规划模型：x1j-y1j-z1j=0;z1j+x2j-y2j-z2j=0;.z5j+x6j-y6j=50.(j=1,2,3,4,5,6,7)将这些数据代入Lingo求解。关于设备检修计划的优化问题；我们先将机器编号，1:磨床2:立钻3：水平钻4:镗床5:刨床；于是引入变量mti 。t是类型数（t=1,2,3,4,5）；i是月份。mit即表示第i份第t类型的机床进行停车维修的台数。1.当t为1,2时，mit最大值是2.；2.当t为4,5时，mit最大值是1；3. 当为3时，mit最大值是3；这样有56=30个变量；于是以前的模型就会变化：假如把机械加工能力以小时计的话,第i月份的研磨能力536-384mit ；于是得到新的模型：;将数据代入Lingo求解。3.2 存贮过程中的费用最小问题防疫站使用某疫苗收费120元，缺货则每份疫苗损失25元，存贮每份疫苗的年费用是其价值的20%，订货一次的费用是25元7。每次订货少于25份单价每份100元，订货25至49份每份95元，50至99份每份90元，订货100元以上每份80元每天对此疫苗的需求量是不确定的，过去200天的统计见表14每次订货后到货时间也长短不等，过去50次的订货到货间隔如表15，现在的问题仍是在什么时间订货，每次订货多少才使总的存贮费用最小。表14：某防疫站每天对某疫苗使用量分布每天使用量（份）出现频次构成比0190.0951270.1352420.2103490.2454340.1705170.085690.045720.010810.005 2001.000表15：某疫苗订货到货间隔分布订货-到货间隔出现次数构成比4110.22570.14630.067210.42850.10920.041010.02合计501.00解 为模拟现实情况，首先建立两个随机数系列代表随机的需求量和订货到货间隔，根据表14 和表15两变量在各值上的出现频率构成，可以列出相应的随机数字范围见表16。表16：疫苗不同需求量和不同订货-到货间隔对应的随机数范围随机数范围每天需求量随机数范围订货-到货间隔0.000-0.09400.00-0.2140.095-0.22910.22-0.3550.230-0.43920.36-0.4160.440-0.68430.42-0.8370.685-0.85440.84-0.9380.855-0.93950.94-0.9790.940-0.98460.98-0.99100.985-0.99470.995-0.9998有了表16即可进行模拟。首先选取两个存贮策略，如选在库存量为10份时和15份时订货进行比较，订货量都是25份。查随机数字表或者用计算机自动产生随机数，根据随机数在表16中对应的需求量而确定需求量，如产生的第一个随机数是0.134，对应的需求是1份。假设第一天库存为15份，则用去1份，还剩14份需要送回冷库存贮。模拟结果见表17 和表18。表17 :模拟：库存量为10份时订货，订货量25份日期随机数需求订货量随机数订-到货间隔到货量库存量存贮费用（元）缺货损失（元）疫苗价值（元）订货费（元）总费用1.1341141.061.062.909525.34459.682375252400.683.20418.61.614.90653.23.235.38721.08.086.04501.08.087.89450.00100100.008.172125241.821.829.3802221.671.6710.3902201.521.5211.5133171.291.2912.5633141.061.0613.670311.84.8414.428225.63379.682375252400.6815.58936.46.4616.04006.46.4617.73842.15.1518.460300.002525.0019.007000.000.0020.775400.00100100.0021.421200.005050.0022.072025231.751.75合计14.342754750505089.34注：每月按22个工作日模拟，存贮费用按每年250工作日计算。表18:模拟：库存量为15份时订货，订货量25份日期随机数需求订货量随机数订-到货间隔到货量库存量存贮费用（元）缺货损失（元）疫苗价值（元）订货费（元）总费用1.134125.3445141.062375252401.062.9095.9.68.683.20418.61.614.90653.23.235.38721.08.086.04501.08.087.894525211.601.528.1721201.521.449.3802171.291