运筹学-武汉大学商学院

《运筹学》武汉大学商学院刘明霞1可编辑ppt教材Operation(al)Research（简写OR）直译为：作战研究、运用研究日本：运用学中国：运筹学（意译）教材《运筹学》，韩伯堂，高等教育出版社，2000年参考书《运筹学》，清华大学出版社《管理运筹学》韩大卫编，大连理工大学出版社其它同类书2可编辑ppt教学目的与方法教学目的：介绍运筹学各分支体系的基本模型、求解方法；引导并锻练MBA学员用运筹学知识定量分析与解决实际问题的能力。教学方法以各种实际问题为背景，引出各分支基本概念、基本模型和基本方法，侧重各种方法及应用，回避繁复的数学理论推导。运用软件教学，并让学生掌握这类软件。分组进行案例分析与讨论3可编辑ppt教学内容运筹学ABC线性规划问题整数规划目标规划动态规划网络规划排队论存贮论对策论决策论4可编辑ppt第一章运筹学ABC运筹学的发展：三个来源运筹学的性质和特点运筹学研究的问题与解决方法运筹学的工作步骤

5可编辑ppt运筹学的发展：三个来源

军事管理经济

6可编辑ppt军事：运筹学的主要发源地古代军事运筹学思想中国古代的“孙子兵法”在质的论断中渗透着量的分析（1981年美国军事运筹学会出版了一本书，书中第一句话就是说孙武子是世界上第一个军事运筹学的实践家），中国古代运筹学思想的例子还有：田忌赛马、围魏救赵、行军运粮，等等。国外历史上的阿基米德、伽利略研究过作战问题；第一次世界大战时，英国的兰彻斯特（Lanchester）提出了战斗方程，指出了数量优势、火力和胜负的动态关系；美国的爱迪生为美国海军咨询委员会研究了潜艇攻击和潜艇回避攻击的问题。7可编辑ppt运筹学的正式产生：第二次世界大战鲍德西（Bawdsey）雷达站的研究1939年，以Blackett为首的一个研究小组（代号“Blackett马戏团”），研究如何改进英国的空防系统，提高英国本土防空能力。Blackett备忘录1941年12月，Blackett应盟国政府的要求，写了五份题为“ScientistsattheOperationalLevel”的简短备忘录，建议在各大指挥部建立运筹学小组，此建议被迅速采纳。据不完全统计，二战期间，仅在英、美和加拿大，参加运筹学工作的科学家超过700名。大西洋反潜战：研究如何打破德国对英吉利海峡的海上封锁英国战斗机中队援法的决策8可编辑ppt管理泰勒的时间动作研究、甘特的用于生产计划与控制的“甘特图”、吉尔布雷思夫妇的动作研究等爱尔朗（Erlong）的排队论公式

1909－1920年间，丹麦哥本哈根电话公司工程师爱尔朗陆续发表了关于电话通路数量等方面的分析与计算公式。尤其是1909年的论文“概率与电话通话理论”，开创了运筹学的重要分支－－排队论。9可编辑ppt经济（数理经济学）VonNeumann与对策论1932年，VonNeumann提出一个广义经济平衡模型；1939年，提出了一个属于宏观经济优化的控制论模型；1944年，与Morgenstern共著的《对策论与经济行为》开创了对策论分支。康托洛维奇与“生产组织与计划中的数学方法”30年代，苏联数理经济学家康托洛维奇从事生产组织与管理中的定量化方法研究，取得了很多重要成果。1939年，出版了堪称运筹学的先驱著作－－《生产组织与计划中的数学方法》，其思想和模型被归入线性规划范畴。10可编辑ppt运筹学的性质和特点应用科学－“应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据”。运筹学的特点定量化分析多学科交叉，如综合利用了心理学、经济学、物理、化学等方法最优决策11可编辑ppt运筹学的研究对象

1）机器、工具、设备、人员等如何最佳利用问题方法有：线性规划、整数规划、网络图、动态规划、目标规划等2）竞争现象如战争、投资、商品竞争方法是对策论3）拥挤现象如公共汽车排队、打电话、买东西、飞机着陆、船舶进港等方法是排队论12可编辑ppt运筹学的工作步骤1）提出和形成问题，2）建立模型，3）求解，4）解的检验，5）解的控制，6）解的实施。13可编辑ppt第二章线性规划线性规划问题线性规划模型线性规划的求解------单纯形方法14可编辑ppt线性规划问题例1(广告方式的选择)中华家电公司推销一种新型洗衣机,有关数据见下表.销售部第一月的广告预算为20000元,要求至少有8电视商业节目,15家报纸广告/电视广告费不得超过12000元,电台广播至少隔日有一次.现问该公司销售部应当采用怎样的广告宣传计划,才能取得最好的效果?15可编辑ppt表1-1广告方式广告费用(元/次)可用最高次数/月期望的宣传效果/单位电视台a(白天,1分钟)5001650电视台b(晚上,30钞)10001080每日晨报/(半版)1002430星期日报/(半版)300440广播电台/(1分钟)80251516可编辑ppt17可编辑ppt例2长成家电公司准备将一种新型电视机在三家商场进行销售，每一个商场的批发价和推销费及产品的利润如表所示。由于该电视机的性能良好，各商场都纷纷争购，但公司每月的生产能力有限，只能生产1000台，故公司规定：铁路商场至少经销300台，水上商场至少经销200台，航空商场至少经销100台，至多200台。公司计划在一个月内的广告预算费为8000元,推销人员最高可用工时数为1500。同时，公司只根据经销数进行生产，试问公司下个月的市场对策？18可编辑ppt表1-2经销商场销售利润(元/台)广告费(元/台)推销工时(小时/台)航空商场50122铁路商场8073水上商场708419可编辑ppt20可编辑ppt

21可编辑ppt

22可编辑ppt求解--单纯形法将所给问题化为标准形找出一个初始可行基,建立初始单纯形表检查所有检验数(若全为非负,则已得到最优解,计算停止.否则继续下一步)考察是否无解(若是,计算停止,否则继续下一步)确定入基变量,出基变量对初始单纯形表进行单纯形变换23可编辑ppt第三章对偶问题和灵敏度分析原问题对偶问题24可编辑ppt对偶性质原问题与对偶问题互为对偶原问题与对偶问题或都有最优解(最优值相同),两最优解之间存在一定的关系,或都没有最优解可知:研究对偶问题可以简化计算(当原问题很复杂时,可先求解对偶问题,再根据一定的关系得出原问题的最优解提出了新的求解方法:对偶单纯形法25可编辑ppt对偶变量的经济解释对偶变量yi在经济上表示原问题第i种资源的边际贡献,即当第i种资源增加一个单位时,相应的目标值z的增量对偶问题的最优解yi*是原问题第i种资源的影子价格应用:1.出租资源或设备时,租金价格的设定(至少高于该资源在企业内的影子价格)2.企业内资源I的存量设定(当资源I的影子价格>=市场价格时,可买进该资源;否则卖出)3.调整资源的分配量以增加利润26可编辑ppt灵敏度分析基本任务:确定参数的影响范围,即保持某LP问题的最优基不变的条件下该参数单独变化的最大范围一个参数的影响范围越小,最优基对这一参数的变化就越敏感,最优基对该参数而言就越不稳定另一个任务:当最优解随参数变化时如何简便地求得新最优解27可编辑ppt第四章运输问题收点B1B2Bn发量发点A1C11x11C12x12

…C1nx1na1…AmCm1xm1Cm2xm2Cmnxmnam收量b1b2bn28可编辑ppt平衡运输问题的模型Minz=S.t.29可编辑ppt平衡运输问题的求解---表上作业法找一个初始基可行解;方法:最小元素法/Vogel近似法(VAM)检验,若所有的检验数都小于零,最优解已得,否则继续下一步;方法:位势检验法调整,得到一个新的基可行解,重复第二步.方法:闭回路法30可编辑ppt运输问题的实例东风电机公司接到上海一家商场(B1),青岛一家商场(B2),西安一家商场(B3)各一份订单,要求下月供应电机.B1的需求量为100台,B2的需求量为80台,而B3要求供应120台.该公司在北京和武汉设有两个仓库(A1,A2),预计A1,A2下月的库存量分别为200台和150台.已知每个仓库到每家商场运送1台电机的费用如表所示.问该公司应如何调运电机,才能既满足用户的需要又使总的运费最少?31可编辑pptB1B2B3A1152118A220251632可编辑ppt第五章指派问题设有n个人A1,A2,…An,要分派去做n件事B1,B2…Bn,要求每一件事都必须有一个人去做,而且不同的事由不同的人去做.已知每个人Ai做每件事Bj的效率(如劳动工时或成本,或创造的价值等)为Cij,问应如何进行指派(哪个人做哪件事),才能使工作效益最好(如工时最少,或成本最低,或创造的价值最大)?指派问题既可以说是运输问题的特殊情形,也可以说是整数规划的特殊情形.33可编辑ppt指派问题的数学模型Minz=S.t.34可编辑ppt举例有4个工人,要指派他们分别完成4项工作,每人做各项工作所消耗的时间如下表:问如何指派使总的消耗时间最小?人工作ABCD甲15182124乙19232218丙26171619丁1921231735可编辑ppt第六章目标规划多目标的线性规划问题(多目标决策),而非单目标.其模型是在线性模型的基础上,利用正负偏差变量(d+,d-)、优先因子(pk,pk>>pk+1)、权系数,对同等级或不同等级的目标进行设置.因其模型结构与线性规划的数学模型结构没有本质的区别,所以可用单纯形法求解.36可编辑ppt举例某商店有五位工作人员:经理1人,主任1人,售货员3人.有关情况见下表.设广告费对销售额的贡献为其投入的15倍,各工作人员的收入相当于其完成销售额的5.5%.问如何安排才能达到以下的目标:P1保证全体人员正常工作时间;P2至少完成销售额70000元;P3主任的月收入不少于1200元,售货员A和B的月收入不少于600元和400元;P4全体人员加班时间不超过规定;P5广告费不超过3000元,力争销售额增加10000元,前者的重要性为后者的两倍.37可编辑ppt每小时对销售额的贡献(元)每月总工时每月加班限量(工时)经理14420024主任9620024售货员A5417252售货员B3016032售货员C91003238可编辑ppt第七章整数规划最优解不是分数或小数,而是整数的情形.整数规划的一种特殊情形是0-1规划,如指派问题.整数规划的解法有割平面法、分枝定界法。0-1规划的解法有0-1隐枚举法.整数规划纯整数规划混合整数规划39可编辑ppt运用0-1规划的实际问题关于固定费用的问题相互排斥的约束条件投资场所的选定------相互排斥的计划例:某公司拟在市东、西、南三区建立门市部,拟议中有7个位置Ai（i=1,2,…7）可供选择,规定:在东区,由A1,A2,A3三个点中至多选两个;在西区,由A4,A5两个点中至少选一个;在南区,由A6,A7两个点中至少选一个.如选用Ai点设备投资估计为bi元,每年可获利润估计为ci元,但投资总额不能超过B元,问如何选择使年利润最大?40可编辑ppt建模解:先引入0-1变量,令于是:maxz=

Xi=1,当Ai点被选用0,当Ai点没被选用41可编辑ppt第八章图与网络分析著名哥尼斯堡七桥问题:欧拉(1736).中国邮递员问题：中国管梅谷（1962）CDAA

CBDB13524642可编辑ppt网络规划问题最小支撑树问题网络最大流问题最短路问题最小费用流问题将庞大复杂的工程系统和管理问题用图描述,可以解决工程设计和管理决策的最优化.问题.如,完成任务的时间最少,距离最短,费用最省等等.43可编辑ppt第九章网络计划(PERT技术)特别适用于生产技术复杂,工作项目繁多且联系紧密的一些跨部门的工作计划,如新产品开发、大型的工程项目.还可以应用在人力、物力、财力等资源的安排.编制网络计划包括绘制网络图、计算时间参数、确定关键路线、网络优化等环节.44可编辑ppt第十章动态规划解决多阶段决策过程最优化.只是求解某类问题的一种方法,是考察问题的一种途径,而不是一种特殊算法(如线性规划是一种算法),因而没有一个标准的数学表达式和明确定义的一组规则,必须对具体问题进行具体分析处理.45可编辑ppt动态规划方法的基本思想动态规划方法的关键在于正确地写出基本