运筹学 by 党耀国.pdf

运摇筹摇学党耀国摇 朱建军摇 徐海燕关叶青摇 张风林摇 张骥骧摇 等编著内 容 简 介本书系统地介绍了运筹学中的主要内容,重点讲解了应用广泛的线性规划、运输问题、整数规划、图论与网络计划、存储论、决策分析等定量分析和优化的理论、方法与 Excel 求解。本书强调学以致用,以大量实际问题为背景引出运筹学各分支的基本概念、模型和方法,具有很强的实用性;在基本原理和方法的介绍方面,本书尽量避免复杂的理论证明,通过大量通俗易懂的例子进行理论方法的讲解,具有较强的趣味性,又不失理论性,理论难度由浅入深,适合不同层次的读者。本书可作为高等院校经济管理类、工程类各专业的本科生、专业硕士研究生教材,也可供各类管理人员及相关人员参考。未经许可,不得以任何方式复制或抄袭本书之部分或全部内容。版权所有,侵权必究。图书在版编目(CIP)数据运筹学/党耀国等编著.北京:电子工业出版社,2015.4ISBN 978鄄7鄄121鄄25739鄄1玉.淤运摇 域.淤党摇 芋.淤运筹学 高等学校 教材摇 郁.淤O22中国版本图书馆 CIP 数据核字(2015)第 057583 号策划编辑:王赫男责任编辑:郝黎明摇 摇 摇 摇印摇 摇 刷:装摇 摇 订:出版发行:电子工业出版社北京市海淀区万寿路 173 信箱摇 摇 邮编:100036开摇 摇 本:787 伊1092摇 1/16摇 印张:14摇字数:364 千字摇 摇 插页:1版摇 摇 次:2015 年 4 月第 1 版印摇 摇 次:2015 年 4 月第 1 次印刷定摇 摇 价:36郾 00 元凡所购买电子工业出版社图书有缺损问题,请向购买书店调换。若书店售缺,请与本社发行部联系,联系及邮购电话:(010)88254888。质量投诉请发邮件至 ,盗版侵权举报请发邮件至 。服务热线:(010)88258888。前摇 摇 言I运筹学是从实际问题中抽象而来的模型化手段,是一种解决实际问题的系统化思想,它帮助人们学会如何从实践中发现、提出和分析问题,基于定性和定量相结合的方法,对实际问题进行数学建模、模型求解以寻求最优的解决方案。运筹学的核心思想是当我们面临各种决策问题时,如何做事以及如何做事才能有较高的效率。运筹学已经广泛应用于工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各个部门领域,涉及生产管理实践中的最优生产计划、最优分配、最佳设计、最优决策、最佳管理等实际问题。掌握运筹学的基本理论与方法,是高等院校管理科学与工程、经济管理类专业学生和各级各类管理人员必须具备的基本素质。对以解决实际问题为目标的经济管理类专业的学生而言,最重要的是通过本门课程的学习,培养系统的解决问题的能力,促成其建立运用模型解决问题的习惯,储备一定的数学建模、求解与利用 Excel 求解的能力。对此,在教材编写过程中,本书以生产管理实践中的实际问题为基本素材,强调实践中的理念和悟性,书中编写了大量的实际案例的分析和案例讨论,可以加深读者对实际问题的认识,增强其学习兴趣;深入浅出地讲解各种模型的基本概念和求解思路,尽力避开纯粹数学上的复杂推导,易于学生理解和自学;教材体系结构清晰,涵盖了运筹学的经典理论模型和方法,内容选择安排合理,简单实用。本书适用于高等院校经济管理类专业的本科生和研究生,MBA,面向实际应用的工程类、管理类和各类管理干部进修班的学员。本书是在作者多年教学的基础上,根据教学过程中有关专家、学者的意见,重点对 Ex鄄cel 求解过程进行介绍。把 Excel 求解过程贯穿整个教材之中,对于学生自学、解决实际问题会有较大的帮助。全书共分 6 章,其中第 1 章由党耀国执笔,第 2 章由张凤林执笔,第 3 章由张骥骧执笔,第 4 章由徐海燕执笔,第5 章由关叶青执笔,第6 章由朱建军执笔,全书由党耀国教授统稿。由于作者水平有限,本书难免存在错漏与不足之处,敬请专家、学者及读者不吝指正。党耀国2015 年 1 月于南京目摇 摇 录III第 1 章摇 线性规划11.1摇 线性规划问题及其数学模型/11.1.1摇 线性规划问题的数学模型/11.1.2摇 线性规划问题的标准型/71.2摇 线性规划问题的图解法及几何意义/91.2.1摇 线性规划问题解的概念/91.2.2摇 线性规划问题的图解法/111.2.3摇 线性规划的基本定理/131.3摇 线性规划问题的单纯形算法/141.3.1摇 确定初始基可行解/151.3.2摇 最优性检验/151.3.3摇 基变换/161.4摇 线性规划问题的 Excel 求解/181.5摇 规划求解的极限值报告和敏感性报告/251.5.1摇 极限值报告/261.5.2摇 敏感性报告/261.6摇 线性规划问题的灵敏度分析/281.6.1摇 目标函数价值系数 Cj的灵敏度分析/301.6.2摇 资源约束量 b 的灵敏度分析与影子价格/311.6.3摇 添加新变量的灵敏度分析/331.6.4摇 添加新约束的灵敏度分析/351.6.5摇 技术系数 aij的改变(计划生产的产品工艺结构发生改变)/351.7摇 案例分析/361.8摇 案例讨论/41习题 1/46第 2 章摇 运输问题502.1摇 运输问题的数学模型/502.2摇 运输问题的基本可行解/522.3摇 运输问题的表上作业法/542.3.1摇 确定初始基可行解/542.3.2摇 最优解的判别/572.3.3摇基可行解改进的方法 闭回路调整法/592.4摇 运输问题的 Excel 求解方法/602.4.1摇 产销平衡运输问题/602.4.2摇 产销不平衡运输问题/642.5摇 案例分析/65习题 2/83第 3 章摇 整数规划863.1摇 整数规划的求解/863.1.1摇 装箱问题/863.1.2摇 分支定界算法/873.1.3摇 一般整数规划的 Excel 求解/893.2摇 0-1 规划/913.2.1摇 工厂选址问题/913.2.2摇 背包问题/913.2.3摇 隐枚举法/923.2.4摇 0-1 规划的 Excel 求解/933.3摇 指派问题/95IV运筹学3.3.1摇 指派问题模型/953.3.2摇 匈牙利法/963.3.3摇 指派问题的 Excel 求解/1003.4摇 案例分析/101习题 3/107第 4 章摇 图论与网络计划1104.1摇 图与网络/1104.1.1摇 图的基本概念/1104.1.2摇 网络的基本概念/1124.2摇 最小生成树问题/1144.2.1摇 最小生成树/1144.2.2摇 最小生成树算法/1154.2.3摇 最小生成树 Excel 软件求解/1164.3摇 最短路与最大流问题/1184.3.1摇 最短路算法/1184.3.2摇 最短路问题 Excel 软件求解/1214.3.3摇 最大流算法/1244.3.4摇 最大流算法的 Excel 软件求解/1294.4摇 网络计划技术/1324.4.1摇 网络图的绘制/1334.4.2摇 网络图的编制/1364.4.3摇 路线与关键路线/1374.4.4摇 网络时间参数的计算/1394.5摇 网络优化/1434.5.1摇 工期优化问题/1434.5.2摇 时间费用优化问题/1454.6摇 案例分析/1484.7摇 案例讨论/163习题 4/166第 5 章摇 存储论1725.1摇 存储概述/1725.2摇 确定性存储模型/1765.2.1摇 基本经济订购批量模型/1765.2.2摇 允许缺货的 EOQ 模型/1795.2.3摇 有数量折扣的 EOQ 模型/1815.3摇 单周期的随机性存储模型/1835.3.1摇 离散需求的随机存储模型/1835.3.2摇 连续需求的随机存储模型/1845.4摇 案例分析/1865.5摇 案例讨论/187习题 5/190第 6 章摇 决策分析1926.1摇 基本概念及分类/1926.2摇 不确定型决策方法/1936.2.1摇 乐观准则/1936.2.2摇 悲观准则/1946.2.3摇 折衷准则/1946.2.4摇 等可能性准则/1956.2.5摇 后悔值准则/1956.3摇 风险型决策分析方法/1966.3.1摇 最大收益期望值决策准则/1966.3.2摇 最小机会损失期望值决策准则/1966.3.3摇 渴望水平决策方法/1976.3.4摇 决策树分析方法/1976.4摇 多属性决策方法/2036.4.1摇 决策指标的标准化/2036.4.2摇 线性加权方法/2056.4.3摇 理想解方法/2066.4.4摇 层次分析法/2076.5摇 案例分析/2126.6摇 案例讨论/217习题 6/218第 1 章摇 线性规划001摇 摇 摇 摇第 1 章线 性 规 划线性规划是运筹学的一个重要分支,它也是现代科学管理的重要手段之一,它可以帮助管理者做出科学决策的一个有效的方法,在许多领域都有成功的应用案例。如生产计划安排问题,对于在计划期内安排生产多种产品,生产不同单位产品所需原材料及设备工时不同,同时不同产品的单位产品利润也不同,管理者如何安排各种产品的产量,使得在资源有限的情况下公司获得最大利润?再如投资问题,如何从不同的投资项目中选出一个投资方案使得投资的回报为最大?以上问题都可以利用线性规划方法进行解决。1.1摇 线性规划问题及其数学模型线性规划是研究在给定的约束条件下,求所考查的目标函数在某种意义下的极值问题。自 1947 年美国数学家丹捷格(G.B.Dantzig)提出了求解线性规划问题的方法 单纯形法之后,线性规划在理论上趋于成熟,在实际中的应用日益广泛与深入。特别是在能用计算机来处理成千上万个约束条件和变量的大规模线性规划问题之后,它的适用领域更加广泛。从解决技术问题中的最优化设计到工业、农业、商业、交通运输业、军事、经济计划与管理、决策等各个领域均可发挥重要作用;从范围来看,小到一个小组的日常工作和计划安排,大至整个部门以致国民经济计划的最优方案的提出,都有用武之地。它具有适应性强、应用广泛、计算技术比较简单的特点,是现代管理科学的重要基础和手段之一。摇 摇 1.1.1摇 线性规划问题的数学模型在生产管理和经济活动中,经常会遇到线性规划问题,如何利用线性规划的方法来进行分析,下面举例来加以说明。揖例 1.1铱摇(生产计划问题)某公司在计划期内安排生产甲、乙两种产品,已知生产产品甲需原材料 B,生产产品乙需原材料 A,生产单位产品甲、乙所需原材料及设备工时和002摇 摇 摇 摇运筹学甲、乙两种产品的单位产品利润等数据如表 1.1 所示;由于两种产品生产都在一个设备上生产,且设备工时有限,公司管理者如何安排这两种产品的生产量,使得在资源有限的情况下公司获得最大利润。表 1.1摇 生产单位产品消耗原材料及占用设备工时甲乙资 源 限 制原材料 A(吨)0315原材料 B(吨)4012设备(单位设备工时)2214单位产品利润(万元)23现在需要确定这两种产品的产量,使公司获得最大利润。因此需要引入变量如下:设生产产品 A 和生产产品 B 的产量用变量 x1、x2来表示,则称 x1、x2为决策变量。若用 Z 表示该公司的利润,则该公司的利润值为Z=2x1+3x2(万元)因为在计划期内原材料 A 有 15 吨可利用,所以在确定产品甲、乙的产量时,可用不等式表示为3x2臆 15摇 摇 同理,因在计划期内原材料 B 的限制,有不等式4x1臆 12摇 摇 设备工时的限制,有不等式:摇 摇 摇 摇2x1+2x2臆 14摇 摇 此外甲、乙两种产品的产量不可能为负值,因此有对变量的非负约束x1,x2逸 0综上所述,该公司的生产计划安排问题可用如下数学模型表示为目标函数摇 摇 摇 摇 摇maxZ=2x1+3x2约束条件3x2臆 154x1臆 122x1+2x2臆 14x1,x2逸0揖例 1.2铱摇(成本问题)某炼油厂每季度需供应给合同单位汽油 15 万吨、煤油 12 万吨、重油 12 万吨。该厂计划从 A、B 两处运回原油提炼,已知两处的原油成分含量如表 1.2 所示;又已知从 A 处采购的原油价格为每吨(包括运费)200 元,B