《运筹学》 安徽水利水电职业技术学院 刘舒 教材 Operation(al) Research(简写OR) 直译为:作战研究,运用研究 日本:运用学 中国:运筹学(意译) 教材 《运筹学》,清华大学出版社《运筹学》,2000年 教学目的与方法 教学目的:介绍运筹学各分支体系的基本模型,求解方法;引导并锻练学生用运筹学知识定量分析与解决实际问题的能力. 教学方法 以各种实际问题为背景,引出各分支基本概念,基本模型和基本方法,侧重各种方法及应用,回避繁复的数学理论推导. 运用软件教学,并让学生掌握这类软件. 分组进行案例分析与讨论 教学内容 运筹学ABC 线性规划问题 整数规划 目标规划 动态规划 网络规划 排队论 存贮论 对策论 决策论 第一章 运筹学ABC 运筹学 的发展:三个来源 运筹学的性质和特点 运筹学研究的问题与解决方法 运筹学的工作步骤 运筹学的发展:三个来源 军 事 管 理 经 济 军事:运筹学的主要发源地 古代军事运筹学思想 中国古代的"孙子兵法"在质的论断中渗透着量的分析(1981年美国军事运筹学会出版了一本书,书中第一句话就是说孙武子是世界上第一个军事运筹学的实践家),中国古代运筹学思想的例子还有:田忌赛马,围魏救赵,行军运粮,等等. 国外历史上的阿基米德,伽利略研究过作战问题;第一次世界大战时,英国的兰彻斯特(Lanchester)提出了战斗方程,指出了数量优势,火力和胜负的动态关系;美国的爱迪生为美国海军咨询委员会研究了潜艇攻击和潜艇回避攻击的问题. 运筹学的正式产生:第二次世界大战 鲍德西(Bawdsey)雷达站的研究 1939年,以Blackett为首的一个研究小组(代号"Blackett 马戏团"),研究如何改进英国的空防系统,提高英国本土防空能力. Blackett备忘录 1941年12月, Blackett应盟国政府的要求,写了五份题为"Scientists at the Operational Level"的简短备忘录,建议在各大指挥部建立运筹学小组,此建议被迅速采纳.据不完全统计,二战期间,仅在英,美和加拿大,参加运筹学工作的科学家超过700名. 大西洋反潜战:研究如何打破德国对英吉利海峡的海上封锁 英国战斗机中队援法的决策 管理 泰勒的时间动作研究,甘特的用于生产计划与控制的"甘特图",吉尔布雷思夫妇的动作研究等 爱尔朗(Erlong)的排队论公式 1909-1920年间,丹麦哥本哈根电话公司工程师爱尔朗陆续发表了关于电话通路数量等方面的分析与计算公式.尤其是1909年的论文"概率与电话通话理论",开创了运筹学的重要分支--排队论. 经济(数理经济学) Von Neumann 与对策论 1932年,Von Neumann提出一个广义经济平衡模型;1939年,提出了一个属于宏观经济优化的控制论模型;1944年,与Morgenstern共着的《对策论与经济行为》开创了对策论分支. 康托洛维奇与"生产组织与计划中的数学方法" 30年代,苏联数理经济学家康托洛维奇从事生产组织与管理中的定量化方法研究,取得了很多重要成果.1939年,出版了堪称运筹学的先驱着作--《生产组织与计划中的数学方法》,其思想和模型被归入线性规划范畴. 运筹学的性质和特点 应用科学-"应用现有的科学技术知识和数学方法,解决实际中提出的专门问题,为决策者选择最优决策提供定量依据". 运筹学的特点 定量化分析 多学科交叉,如综合利用了心理学,经济学,物理,化学等方法 最优决策 运筹学的研究对象 1)机器,工具,设备,人员等如何最佳利用问题 方法有:线性规划,整数规划,网络图,动态规划,目标规划等 2)竞争现象如战争,投资,商品竞争 方法是对策论 3)拥挤现象如公共汽车排队,打电话,买东西,飞机着陆,船舶进港等 方法是排队论 运筹学的工作步骤 1)提出和形成问题, 2)建立模型, 3)求解, 4)解的检验, 5)解的控制, 6)解的实施. 第二章 线性规划 线性规划问题 线性规划模型 线性规划的求解------单纯形方法 线性规划问题 例1(广告方式的选择)中华家电公司推销一种新型洗衣机,有关数据见下表.销售部第一月的广告预算为20000元,要求至少有8电视商业节目,15家报纸广告/电视广告费不得超过12000元,电台广播至少隔日有一次.现问该公司销售部应当采用怎样的广告宣传计划,才能取得最好的效果? 表1-1 表1-2  求解--单纯形法 将所给问题化为标准形 找出一个初始可行基,建立初始单纯形表 检查所有检验数(若全为非负,则已得到最优解,计算停止.否则继续下一步) 考察是否无解(若是,计算停止,否则继续下一步) 确定入基变量,出基变量 对初始单纯形表进行单纯形变换 第三章 对偶问题和灵敏度分析 原问题 对偶问题 对偶性质 原问题与对偶问题互为对偶 原问题与对偶问题或都有最优解(最优值相同),两最优解之间存在一定的关系,或都 没有最优解 可知:研究对偶问题可以简化计算(当原问题很复杂时,可先求解对偶问题,再根据一定的关系得出原问题的最优解 提出了新的求解方法:对偶单纯形法 对偶变量的经济解释 对偶变量yi在经济上表示原问题第i种资源的边际贡献,即当第i种资源增加一个单位时,相应的目标值z的增量 对偶问题的最优解yi*是原问题第i种资源的影子价格 应用:1.出租资源或设备时,租金价格的设定(至少高于该资源在企业内的影子价格) 2.企业内资源I的存量设定(当资源I的影子价格>=市场价格时,可买进该资源;否则卖出) 3.调整资源的分配量以增加利润 灵敏度分析 基本任务:确定参数的影响范围,即保持某LP问题的最优基不变的条件下该参数单独变化的最大范围 一个参数的影响范围越小,最优基对这一参数的变化就越敏感,最优基对该参数而言就越不稳定 另一个任务:当最优解随参数变化时如何简便地求得新最优解 平衡运输问题的求解---表上作业法 找一个初始基可行解; 方法:最小元素法/Vogel近似法(VAM) 检验,若所有的检验数都小于零,最优解已得,否则继续下一步; 方法:位势检验法 调整,得到一个新的基可行解,重复第二步. 方法:闭回路法 第五章 指派问题 设有n 个人A1, A2, …An,要分派去做n件事B1, B2… Bn,要求每一件事都 必须有一个人去做,而且不同的事由不同的人去做.已知每个人Ai做每件事Bj的效率(如劳动工时或成本,或创造的价值等)为Cij,问应如何进行指派(哪个人做哪件事),才能使 工作效益最好(如工时最少,或成本最低,或创造的价值最大)? 指派问题既可以说是运输问题的特殊情形,也可以说是整数规划的特殊情形. 指派问题的数学模型 Min z= S.t. 第六章 目标规划 多目标 的线性规划问题(多目标 决策),而非单目标. 其模型是在线性模型的基础上,利用正负偏差变量(d+,d-) ,优先因子(pk,pk>>pk+1) ,权系数,对同等级或不同等级的目标进行设置. 因其模型结构与线性规划的数学模型结构没有本质的区别,所以可用单纯形法求解. 举例 某商店有五位工作人员:经理1人,主任1人,售货员3人.有关情况见下表.设广告费对销售额的贡献为其投入的15倍,各工作人员的收入相当于其完成销售额的5.5%.问如何安排才能达到以下的目标:P1保证全体人员正常工作时间;P2 至少完成销售额70000元;P3主任的月收入不少于1200元,售货员A和B的月收入不少于600元和400元;P4 全体人员加班时间不超过规定; P5广告费不超过3000元,力争销售额增加10000元,前者的重要性为后者的两倍. 第七章 整数规划 最优解不是分数或小数,而是整数的情形. 整数规划的一种特殊情形是0-1规划,如指派问题. 整数规划的解法有割平面法,分枝定界法.0-1规划的解法有0-1隐枚举法. 运用0-1规划的实际问题 关于固定费用的问题 相互排斥的约束条件 投资场所的选定------相互排斥的计划 例:某公司拟在市东,西,南三区建立门市部,拟议中有7个位置Ai(i=1,2, …7)可供选择,规定:在东区,由A1,A2,A3三个点中至多选两个;在西区,由A4,A5两个点中至少选一个;在南区,由A6,A7两个点中至少选一个.如选用Ai点设备投资估计为bi元,每年可获利润估计为ci元,但投资总额不能超过B元,问如何选择使年利润最大? 第八章 图与网络分析 着名哥尼斯堡七桥问题:欧拉(1736). 中国邮递员问题:中国管梅谷(1962) 网络规划问题 最小支撑树问题 网络最大流问题 最短路问题 最小费用流问题 将庞大复杂的工程系统和管理问题用图描述,可以解决工程设计和管理决策的最优化.问题.如,完成任务的时间最少,距离最短,费用最省等等. 第九章 网络计划(PERT技术) 特别适用于生产技术复杂,工作项目繁多且联系紧密的一些跨部门的工作计划,如新产品开发,大型的工程项目.还可以应用在人力,物力,财力等资源的安排. 编制网络计划包括绘制网络图,计算时间参数,确定关键路线,网络优化等环节. 第十章 动态规划 解决多阶段决策过程最优化. 只是求解某类问题的一种方法,是考察问题的一种途径,而不是一种特殊算法(如线性规划是一种算法),因而没有一个标准的数学表达式和明确定义的一组规则,必须对具体问题进行具体分析处理. 动态规划方法的基本思想 动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件(即基本方程).所以,必须先将问题的过程分成几个相互联系的阶段,恰当地选取状态变量和决策变量及定义最优值函数,从而把一个大问题化成一族同类型的子问题,然后逐个求解. 动态规划的应用------定价问题 例 :某厂要确定一种新产品在今后五年内的价格,并已拟定只在5,6,7,8元这四种单价中进行选择.据预测,今后五年不同价格下每年盈利(万元)如下表所示,但是各相邻年度价格不得超过1元.问今后五年内每年定价各为多少,可预期五年总利润最大? 上表 第十二章 决策论 决策过程 不确定型的决策 悲观主义决策准则,乐观主义决策准则,等可能性准则,最小机会损失准则,折衷主义准则 风险决策 最大期望值决策准则,最小机会损失决策准则 第十一章 对策论(博弈论) 二人或多人竞争或对抗活动 基本概念:局中人,策略集,支付函数 矩阵对策记为:G={I,II;S1,S2;A}或 G={ S1,S2;A},其中A为某局中人的支付矩阵. 矩阵对策的解法 运输问题的实例 东风电机公司接到上海一家商场(B1),青岛一家商场(B2),西安一家商场(B3)各一份订单,要求下月供应电机.B1的需求量为100台,B2的需求量为80台,而B3要求供应120台.该公司在北京和武汉设有两个仓库(A1,A2),预计A1,A2下月的库存量分别为200台和150台.已知每个仓库到每家商场运送1 台电机的费用如表所示.问该公司应如何调运电机,才能既满足用户的需要又使总的运费最少? 16 25 20 A2 18 21 15 A1 B3 B2 B1 举例 有4 个工人,要指派他们分别完成4 项工作,每人做各项工作所消耗的时间如下表:问如何指派使总的消耗时间最小? 17 19 18 24 D 23 16 22 21 C 21 17 23 18 B 19 26 19 15 A 丁 丙 乙 甲 人 工作 32 100 9 售货员C 32 160 30 售货员B 52 172 54 售货员A 24 200 96 主任 24 200 144 经理 每月加班限量(工时) 每月总工时 每小时对销售额的贡献(元) 整数规划 纯整数规划 混合整数规划 建模 解:先引入0-1变量,令 于是:max z= Xi= 1,当Ai点被选用 0,当Ai点没被选用 C D A A C B D B 1 3 5 2 4 6 4 6 6 7 8 8 3 7 9 5 6 7 4 6 8 5 7 6 8 5 4 2 9 5 5 4 3 2 1 年 价格 * * 15 25 80 广播电台/(1分钟) 40 4 300 星期日报/(半版) 30 24 100 每日晨报/(半版) 80 10 1000 电视台b(晚上,30钞) 50 16 500 电视台a(白天,1 分钟) 期望的宣传效果/单位 可用最高次数/月 广告费用(元/次) 广告方式 例2 长成家电公司准备将一种新型电视机在三家商场进行销售,每一个商场的批发价和推销费及产品的利润如表所示.由于该电视机的性能良好,各商场都纷纷争购,但公司每月的生产能力有限,只能生产1000台,故公司规定:铁路商场至少经销300台,水上商场至少经销200台,航空商场至少经销100台,至多200台.公司计划在一个月内的广告预算费为8000元,推销人员最高可用工时数为1500.同时,公司只根据经销数进行生产,试问公司下个月的市场对策? 4 8 70 水上商场 3 7 80 铁路商场 2 12 50 航空商场 推销工时 (小时/台) 广告费 (元/台) 销售利润 (元/台) 经销商场  第四章 运输问题 发点 am a1 发量 bn Cmn xmn C1nx1n Bn … b2 Cm2xm2 C12x12 B2 b1 Cm1xm1 C11 x 11 B1 收量 Am … A1 收点 平衡运输问题的模型 Min z= S.t.