《运 筹 学 基 础》

rainbow

《运 筹 学 基 础》

何坚勇编著
清华大学出版社
http://www.tup.tsinghua.edu.cn
(京)新登字158号
内容简介
    本书是一本着重实际应用又兼顾理论要求的运筹学教材．主要内容包括线性规划、整数规划、目标规划、非线性规划、动态规划及决策分析．各章附有习题，书末有习题解答和提示．并介绍了专门用于求解数学规划的LINDO软件包．
    本书起点低、跨度大；基本概念与基本理论阐述清晰透彻，密切联系实际，各种算法推导详细，配有丰富实用的例题．本书可作为工程硕士研究生以及经济管理等非数学专业大学生、研究生的教材，也可供科技人员和管理人员参考．
书  名：运筹学基础
作  者：何坚勇
出版者：清华大学出版社
        (北京清华大学学研楼，邮编 100084)
        http://www.tup.tsinghua.edu.cn
印刷者：北京清华园胶印厂
发行者：新华书店总店北京发行所
开  本：787×960 1/16 印张：31
字  数：652千字
版  次：2000年7月第1版2000年7月第1次印刷
书  号：ISBN 7-302-03922-4/F·276
印  数：0001～5000
定  价：31.00元
编委会
主  编：蔡大用
编  委(以姓氏笔划为序)：
邢文训 陆璇 姜启源 康飞宇 潘真微

编者的话
    电子计算机已经成为工程技术界、管理科学领域须臾离不开的工具．因此，学习用计算机解决工作中的各种实际问题已经成为各行业知识更新的必要环节，更是工程硕士学位的必修课程．为了适应这种形势，在几年教学经验的基础上我们编撰了这套《工程硕士应用数学》系列教程．
    全套书由三本组成：《科学和工程计算基础》，《应用概率统计》和《运筹学基础》．
    编书的指导思想是：低起点，大跨度．前者是指避免某些抽象的数学推理和繁琐的公式演绎．为了顾及有些读者复习基础知识的需要，书中专门设置了有关微积分、线性代数的章节．大跨度是指力图覆盖各领域中常常涉及到的数学问题．当然，全面覆盖是不可能的，仅仅是尽我们所能而已．另一个指导思想是：着重内容的实用性，兼顾理论体系．对于知识更新和进修工程硕士的需要来说，学习内容的实用性显得更加重要．因此，在题材选择和叙述重点上我们都把实用性放在首位．
    除了介绍算法和相关的理论之外，《科学和工程计算基础》及《应用概率统计》两本书还介绍了目前流行的两个数学软件——Matlab和SAS．《运筹学基础》介绍了LINDO软件包．学员利用这些工具可以很容易地实现各种算法，从而避免了枯燥的程序设计工作．
    还要提到的是，这套丛书虽然是针对工程硕士课程撰写的，但对于一般理工科大学生和研究生，也是一本可以使用的教科书．
    最后，我们对清华大学研究生院和清华大学出版社的领导表示衷心的感谢，没有他们的指导和帮助这套丛书是不可能成功的．
编者 1999年5月
前言
    运筹学，即最优化理论，或在有的领域中称为管理科学．它广泛应用于工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各个部门、各个领域．它主要解决最优生产计划、最优分配、最佳设计、最优决策、最佳管理等最优化问题．掌握优化思想并善于对遇到的问题进行优化处理，是企业领导或各级各类管理人员必须具备的基本素质．运筹学就是帮助读者学会如何根据实际问题的特点、抽象出不同类型的数学模型，然后选择不同的方法进行计算．
    随着经济建设与科教事业的不断发展，近年来在学生队伍中出现了新的群体——工程硕士研究生．这部分学员的特点是有丰富的实践经验、大多在各级领导岗位上或负责一定的技术业务工作，又受过良好的大学教育．只是离开学校时间较长，多达十来年，少则三五年．因此数学基础知识忘得较多、对理论推导有一定的惧怕心理．但又有在理论上进行深造与提高的强烈愿望．针对工程硕士研究生的上述特点，编写一本起点低、跨度大、着重实际应用又兼顾理论要求的运筹学教材，是作者这几年来的一个心愿．
    本书首先设置了预备知识这一章，着重复习与本书有关的微积分和线性代数的基础知识．如向量、矩阵、二次型的正定性；多元函数的梯度、极值、泰勒公式等．也补充了一般大学课程中没有但本书需要用到的知识，如多元函数的黑塞矩阵概念．
    本书的主体介绍了线性规划、运输问题、整数规划、目标规划、非线性规划、动态规划及决策分析．这些都是运筹学中最基本且应用最广泛的内容，涵盖了运筹学中的大部分．全部讲授约需64课时．书中部分打*内容可选讲．
    本书在阐述基本概念与基本理论时，力求清晰、透彻．在适当的地方配置了一些思考题，以促使读者深入思考、加深对内容的理解．对于基本的理论、主要的定理都给予了证明．因此本书在理论上有一定的深度．使读者不仅知其然，并且知其所以然，为其举一反三、扩大应用面打好基础．在证明定理时，尽量考虑到学员的现有基础．如在证明线性规划最优性准则定理(本书定理3.1 .1 )时，若按通常证法，书写简单明了．但几次教学实践结果，不少学员都感到有疑问．分析原因，主要是对线性方程组有无穷多个解时的解集、当取不同的基础解系时，其解集是等同的这一点理解不深．因此本书在证明该定理时，多费了一些笔墨，从线性方程组的解集角度入手，证明满足最优性准则的可行解必是全部可行解中的最优解．实践效果较好．本书对一些理论上过深或推导过于繁琐的内容，采取以讲清概念、用几何图形加以辅证的方法，避免过繁的推导或引入过多的数学概念(这些推导与概念对于数学专业也许是必须的)．
    本书注重联系实际．在介绍每一种规划模型前都以实际问题引入．在讲清概念和理论后，对各种算法都有详细的推导过程，且配有例题、参照例题的解法，学员可以比较容易理解算法的原理和掌握算法的基本步骤，并学会如何应用这些算法．书中还配有几十个各行各业的应用实例，学员参照这些实例可以学习到如何根据实际问题建立相应数学模型的方法与技巧．
    建立数学模型是为了解决实际问题，得到计算结果．书末附录中介绍了在教育、科研与工业界得到广泛应用且专门用于求解数学规划的软件包——LINDO软件包．书中相应部分穿插了用该软件包求解各类规划的例题．学员学习后可基本掌握如何使用LINDO软件包求解规划问题．运筹学基础书中每章都配有习题，书末给出了答案．
    作者相信广大学员学习本书后，能较快地掌握运筹学的基本知识，并应用到工作实际中去，定会对工作有所帮助．也为进一步学习运筹学理论打下良好的基础．
    本书主要对象是工程硕士研究生，同时也可作为经济管理等非数学专业的大学生、研究生的“运筹学”教材．对科技工作者与管理人员也有一定的参考价值．
    在编写本书过程中，得到清华大学研究生院与清华大学出版社的大力支持．清华大学应用数学系的领导及运筹学教研组的同事也给予了充分的支持和合作．附录中“LINDO软件包介绍”是谢金星、姜启源老师的工作成果．用LINDO软件计算的部分例题是由郑小峰同学完成的．在多年的教学实践及编写本书过程中，作者从许多国内外专家、学者的著作中汲取了营养，获益匪浅，本书直接或间接地引用了他们的部分成果(见书末参考文献)，在此一并表示感谢与敬意．
    由于成书时间仓促、作者水平有限，本书缺点甚至错误在所难免，敬请专家、学者及读者不吝指教．
编者 1999年
目录
编者的话Ⅲ
前言 Ⅴ
第1部分预 备 知 识
第1章预备知识2
1.1 向量2
1.1.1 向量定义及线性运算2
1.1.2 向量的线性相关性3
1.1.3 向量组的秩5
1.2 矩阵5
1.2.1 矩阵的概念与运算5
1.2.2 矩阵的求逆运算8
1.2.3 矩阵的初等变换9
1.2.4 矩阵的分块11
1.2.5 矩阵的秩14
1.3 二次型及其正定性17
1.3.1 二次型及其矩阵表达式17
1.3.2 二次型的正定性19
1.4 多元函数的导数与极值21
1.4.1 一元函数的导数、极值与泰勒公式21
1.4.2 多元函数的梯度、黑塞矩阵与泰勒公式24
1.4.3 多元函数的极值32
习题135
第2部分线 性 规 划
第2章线性规划的基本概念40
2.1 线性规划问题及其数学模型40
2.1.1 问题的提出40
2.1.2 线性规划问题的数学模型41
2.2 两个变量问题的图解法42
2.3 线性规划数学模型的标准形式及解的概念46
2.3.1 标准形式46
2.3.2 将非标准形式化为标准形式47
2.3.3 有关解的概念49
2.4 线性规划的基本理论51
2.4.1 凸集与凸组合51
2.4.2 线性规划基本定理53
习题258
第3章单纯形法60
3.1 单纯形法原理60
3.1.1 单纯形法的基本思路60
3.1.2 确定初始基本可行解64
3.1.3 最优性检验65
3.1.4 基变换67
3.1.5 无穷多个最优解及无界解的判定70
3.2 单纯形表72
3.3 人工变量及其处理方法77
3.3.1 大?M?法78
3.3.2 两阶段法80
3.3.3 关于退化与循环的问题83
3.4 改进单纯形法84
3.4.1 单纯形法的矩阵描述84
*3.4.2 改进单纯形法87
*3.5 用LINDO软件解线性规划93
3.5.1 初试LINDO93
3.5.2 用LINDO软件求解线性规划问题的一般步骤96
习题397
第4章线性规划的对偶理论101
4.1 线性规划的对偶问题101
4.1.1 对偶问题的实例101
4.1.2 三种形式的对偶关系102
4.2 对偶理论108
4.3 对偶解(影子价格)的经济解释115
4.4 对偶单纯形法116
4.5 灵敏度分析121
*4.6 用LINDO软件求对偶变量及进行灵敏度分析132
习题4135
第5章运输问题139
5.1 运输问题的数学模型及其特点139
5.1.1 产销平衡运输问题的数学模型139
5.1.2 运输问题数学模型的特点140
5.2 表上作业法142
5.2.1 确定初始基本可行解142
5.2.2 位势法求检验数146
5.2.3 用闭回路法调整当前基本可行解150
5.2.4 表上作业法计算中的两个问题155
*5.3 表上作业法的理论解释158
5.3.1 用西北角规则求得的解是基本可行解158
5.3.2 对于非基格存在唯一闭回路162
5.3.3 检验数 σ ij 与v n=a的取值无关162
习题5166
第6章线性规划应用实例168
6.1 套裁下料问题168
6.2 配料问题169
6.3 生产工艺优化问题171
6.4 有配套约束的资源优化问题172
6.5 多周期动态生产计划问题174
6.6 投资问题175
6.6.1 投资项目组合选择175
6.6.2 连续投资问题176
6.7 运输问题的扩展177
6.7.1 产销不平衡的运输问题178
*6.7.2 可以化成运输模型的其它线性规划问题182
*6.8 用LINDO软件求解题例187
习题6194
第3部分整 数 规 划
第7章整数规划198
7.1 分枝定界法200
7.2 割平面法207
7.3.0 1 型整数规划212
7.3.1 特殊约束的处理212
7.3.2 0 1 型整数规划的典型应用问题213
7.3.3 求解小规模0 1 规划问题的隐枚举法216
7.4 指派问题与匈牙利解法217
7.4.1 指派问题的数学模型217
7.4.2 匈牙利法的基本原理218
7.4.3 匈牙利法求解步骤220
*7.5 用LINDO软件求解整数规划228
习题7233
第4部分目 标 规 划
第8章目标规划236
8.1 线性目标规划的基本概念与数学模型236
8.2 线性目标规划的图解法240
8.3 线性目标规划的序贯式算法244
8.4 线性目标规划的单纯形算法250
习题8253
第5部分非线性规划
第9章非线性规划的基本概念与基本原理258
9.1 非线性规划的数学模型258
9.1.1 非线性规划问题举例258
9.1.2 非线性规划问题的一般数学模型260
9.1.3 局部最优解与全局最优解262
9.2 无约束问题的最优性条件262
9.3 凸函数与凸规划267
9.3.1 凸函数定义与性质268
9.3.2 凸函数的判别准则272
9.3.3 凸规划276
9.4 解非线性规划的基本思路277
习题9282
第10章一维搜索284
10.1 黄金分割法285
10.1 .1 单谷函数及其性质285
10.1 .2 0.618法基本原理与步骤286
10.2 加步探索法291
10.2 .1 基本原理和步骤291
10.2 .2 算计举例292
10.3 牛顿法293
*10.4 抛物线法295
习题10297
第11章无约束问题的最优化方法298
11.1 变量轮换法298
11.2 最速下降法301
11.2.1 基本原理301
11.2.2 最速下降法的算法步骤303
11.3 牛顿法306
11.3.1 牛顿方向和牛顿法306
11.3.2 计算举例307
11.3.3 修正牛顿法309
11.4 共轭梯度法311
11.4.1 共轭方向与共轭方向法311
11.4.2 正定二次函数的共轭梯度法314
11.4.3 非二次函数的共轭梯度法321
习题11322
第12章约束问题的最优化方法323
12.1 约束极值问题的最优性条件323
12.1 .1 起作用约束与可行下降方向323
12.1 .2 库恩?塔克条件326
12.2 可行方向法331
12.2 .1 基本原理与算法步骤331
12.2.2 计算举例333
12.3 近似规划法337
12.3.1 线性近似规划的构成337
12.3.2 近似规划法的算法步骤338
12.3.3 计算举例338
12.4 制约函数法342
12.4.1 外点法342
12.4.2 内点法347
*12.5 用GINO软件解非线性规划350
12.5.1 GINO的命令350
12.5.2 GINO的使用350
习题12353
第6部分动 态 规 划
第13章动态规划355
13.1 动态规划问题实例355
13.2 动态规划的基本概念357
13.2.1 多阶段决策过程357
13.2.2 动态规划的基本概念359
13.3 最优性定理与基本方程362
13.3.1 最优性原理362
13.3.2 最优性定理363
13.3.3 动态规划的基本方程364
13.4 动态规划应用举例370
13.4.1 资源分配问题371
13.4.2 生产与库存计划问题376
*13.4.3设备更新问题383
习题13387
*第7部分决 策 分 析
*第14章决策分析389
14.1 决策的基本概念389
14.1.1 决策问题实例389
14.1.2 决策问题中的主要概念390
14.1.3 决策问题的分类391
14.2 确定型决策392
14.3 风险型决策393
14.3.1 最优期望益损值决策准则393
14.3.2 决策表法393
14.3.3 决策树法395
14.4 效用理论400
14.4.1 效用的概念与效用曲线401
14.4.2 效用曲线的类型405
14.4.3 最大效用期望值决策准则及其应用406
14.5 不确定型决策408
习题14412
附录LINDO软件包介绍414
f.1 简介与安装414
f.1.1 LINDO软件包简介414
f.1.2 LINDO软件包的安装415
f.2 用LINDO软件求解线性规划、整数规划和二次规划416
f.2.1 初试LINDO416
f.2.2 求解LP问题的一般步骤416
f.2.3 计算结果显示及敏感性分析416
f.2.4 注意事项416
f.2.5 整数规划(IP)418
f.2.6 二次规划(QP)418
f.2.7 LINDO命令的详细解释419
f.2.8 熟练掌握LINDO427
f.3 用GINO求解非线性规划428
f.3.1 GINO命令428
f.3.2 GINO的使用429
f.4 用LINGO求解大规模数学规划429
f.4.1 LINGO、LINGO2命令429
f.4.2 LINGO的使用429
f.4.3 内部函数详细注释432
习题答案及提示436
参考文献472
索引473
其它相关内容
工程硕士研究生英语教程教师用书
工程硕士研究生英语教程学生用书
工程硕士研究生英语教程测试习题集
全国工程硕士专业学位研究生英语教学大纲
全国工程硕士研究生入学考试英语考试大纲

科学和工程计算
应用概率统计
运筹学基础