本书是一本着重实际应用又有一定理论深度的最优化方法教材,内容包括线性规划、运输问题、整数规划、目标规划、非线性规划(无约束最优化与约束最优化)、动态规划等最基本、应用最广又最有代表性的最优化方法.各章都由实例引入,对主要定理进行证明,引入相应的数学模型与算法,配有算法例题与详细步骤.章末附有习题,书末有习题解答与提示.本书还专辟一章,列举了用新版本的MATLAB软件包及LINDO/LINGO优化软件包来计算的实例.
本教材在阐述基本概念与基本理论时,力求清晰、透彻,在适当地方配置了一些思考题,以促使读者深入思考,加深对内容的理解.在文字叙述方面力求语言浅显、简易明了、深入浅出,以便于学生学习.
序言
数学科学不仅是自然科学的基础,也是一切重要技术发展的基础.电子计算机的发明及计算技术的发展都以数学为其理论基础.计算机技术的发展使得数学的应用更加直接和广泛,同时也正在改变人们对数学的传统认识.数学素质已成为今天培养高层次创新人才的重要基础.
计算数学是一门随着计算机发展而形成的学科,研究如何应用计算机有效地求解各类计算问题的方法和理论,其中涉及的计算问题主要来源于科学研究和工程设计,因此人们又称这门学科为科学计算.今天,计算和实验、理论分析一起成为当今科学活动的主要方式.在物理、化学、力学、材料科学、环境科学、信息科学和生物科学等领域,计算方法和技术已经成为被广泛接受的科学研究手段,这一系列计算性的分支学科统称为计算科学.现在,计算在科学研究和工程设计中几乎无处不在,对科技的发展起到举足轻重的作用.由于计算数学的发展已有50多年的历史,在教学科研方面有着深厚的积累,传统的教材建设也相对比较规范.伴随着计算机技术突飞猛进的发展,特别是超大规模计算机平台的建立和使用,以及科学研究中不断增长的对计算方法和技术的需求,传统的计算数学教材已不能满足教学的需要.
信息化已成为当今世界发展的重要趋势,也是衡量一个国家现代化水平的重要标志.信息科学可以理解为信息获取、传输、处理与控制的科学.我国信息科学发展的时间相对较短,但发展迅猛.发展信息科学需要数学基础,当然也离不开计算机科学.由于信息科学的多学科交叉的特点,在不同院校和专业,信息科学都得到了一定的发展.但也正是这些原因,使得信息科学的学科定位,尤其是教材建设百家争鸣,缺乏统一的规范,给教学带来了很大的实际困难.
教育部1998年颁布的普通高等院校专业目录中,“信息与计算科学”专业被列为数学类下的一个新专业.这一新专业的设置很好地适应了新世纪以信息和计算技术为核心的数学人才的培养.然而,作为一个新专业,对其专业内涵、专业规范、教学内容与课程体系等有一个认识与探索的过程.教育部数学与统计学教学指导委员会经过多年艰苦细致的工作,对一些问题有了比较明确的指导意见,发表了《关于信息与计算科学专业办学现状与专业建设相关问题的调查报告》及《信息与计算科学专业教学规范》(讨论稿)(见《大学数学》第19卷1期(2003)).按照新的教学规范,信息与计算科学专业是以信息技术和计算技术的数学基础为研究对象的理科类专业.其目标是培养学生具有良好的数学基础和数学思维能力,掌握信息与计算科学基础理论、方法与技能,能解决信息技术和科学与工程计算中实际问题的高级专门人才.
近年来在教育部领导下,高等院校每年大量扩大招生,从而使得我国的高等教育从精英化向大众化转变.现在全国大约有400所高校开办了“信息与计算科学”专业,每年招收 3万名左右的本科生.其中大部分学校缺乏从事该领域教学科研经验的教师,对专业的定位及课程设置也不明确.即使是全国一流的高校,也是偏向于单一学科,新专业没有一个完整的切实可行的教学大纲,适合交叉学科专业的教材极其匮乏。
“信息与计算科学”专业属于数学类,前两年的课程基本上是明确的,教材也很多.本套系列教材重点建设后两年的专业课.由于重点高校大部分有自己的课程体系和教材建设,本系列教材主要针对普通高等学校开办的该专业.依据教育部“强基础,宽口径,重实际,有侧重,创特色”的办学指导思想,清华大学出版社组织的《高等院校信息与计算科学专业系列教材》编委会成员对专业定位、课程设置、教材内涵等进行了深入的探讨,并邀请有多年教学和科研经验的教师编写系列教材.特别是北京大学姜明教授等对涉及信息科学的教材建设花费了大量心血,在此对他们表示感谢.
为适应不同类型院校和不同层次要求的课程需求,教材建设也需要多样化和层次化.我们相信,该系列教材的出版对缓解本专业教材的紧缺局面,逐步形成专业定位与课程设置,推动信息与计算科学的发展,培养适应时代发展的交叉学科人才,提高中国数学教育水平起到一定的作用.
张平文2005年9月
前言
最优化方法广泛应用于工业、农业、交通运输、商业、国防、建筑、通信与政府机关、管理等各个部门、各个领域;它主要解决最优计划、最优分配、最优决策、最佳设计、最佳管理等最优化问题.掌握最优化思想并善于对遇到的问题进行优化处理是各级各类管理人员必须具备的基本素质,也是培养高层次创新人才所必须具有的重要素质.本教材就是帮助信息与计算科学专业的学生学习如何根据各类实际问题的特点,抽象出不同的数学模型,然后选择相应的方法进行计算及分析其结果,为在今后工作中进行优化处理打下基础.其次,本课程也是该专业的学生学习某些相关课程的前提.
本教材是一本着重实际应用又有一定理论深度的最优化方法教材,内容包括线性规划、运输问题、整数规划、目标规划,非线性规划(无约束最优化与有约束最优化),动态规划等最基本、应用最广又最有代表性的最优化方法.书中对于基本的理论、主要的定理都给予了证明,使读者不仅知其然,而且知其所以然,为其举一反三、扩大应用面打好基础.
本书注重联系实际.在介绍每一种规划模型前都以实际问题引入.在讲清概念和理论后,对各种算法都有详细的推导过程,且配有例题、参照例题的解法,读者可以比较容易理解算法的原理和掌握算法的基本步骤,并学会如何应用这些算法.书中还配有几十个各行各业的应用实例,读者参照这些实例可以学习到如何根据实际问题建立相应数学模型的方法与技巧.
建立数学模型是为了解决实际问题,得到计算结果.书中还列举了用新版本的MATLAB及LINDO/LINGO软件包进行计算分析结果的实例.
本教材在阐述基本概念与基本理论时,力求清晰、透彻,在适当地方配置了一些思考题,以促使读者深入思考,加深对内容的理解.在文字叙述方面力求语言浅显、简易明了、深入浅出,以便于读者学习.
书中各章都配有习题,书末给出了答案与提示.
本书主要对象是“信息与计算科学”专业的大学生.也可供其他专业的教学作参考.
在编写本书的过程中,得到“高等院校信息与计算科学专业系列教材”编委会成员与清华大学出版社的大力支持.在多年的教学实践及编写本书的过程中,编者从许多国内外专家、学者的著作中汲取了营养,获益匪浅,本书直接或间接地引用了他们的部分成果(见书末参考文献).第7章中用MATLAB及LINDO/LINGO软件计算的部分例题是由牛波同学完成的.在此一并表示感谢与敬意.
由于成书时间仓促,作者水平有限,书中缺点甚至错误在所难免,敬请专家、学者及读者不吝指教.
编者2006年10月
第1章线性规划1
1.1线性规划问题的基本概念1
1.1.1线性规划问题及其数学模型1
1.1.2两个变量问题的图解法5
1.1.3线性规划数学模型的标准形式及解的概念10
1.1.4线性规划的基本理论17
1.2单纯形法27
1.2.1单纯形法原理27
1.2.2单纯形表44
1.2.3人工变量及其处理方法53
1.2.4单纯形法的矩阵描述61
*1.2.5改进单纯形法66
1.3线性规划的对偶理论74
1.3.1对偶问题74
1.3.2对偶理论84
1.3.3对偶解(影子价格)的经济解释94
1.3.4对偶单纯形法95
1.3.5灵敏度分析102
1.4运输问题116
1.4.1运输问题的数学模型及其特点117
1.4.2表上作业法121
1.4.3产销不平衡的运输问题141
1.5线性目标规划147
1.5.1线性目标规划的基本概念与数学模型148
1.5.2线性目标规划的图解法153
1.5.3线性目标规划的序贯式算法159
1.5.4线性目标规划的单纯形算法166
1.6线性规划应用实例172
1.6.1配料问题172
1.6.2有配套约束的资源优化问题174
1.6.3多周期动态生产计划问题177
习题1179
第2章整数规划197
2.1整数规划问题的数学模型197
2.1.1整数规划问题举例197
2.1.2整数规划的一般数学模型199
2.2分枝定界法202
2.3割平面法212
2.401型整数规划220
2.4.1特殊约束的处理220
2.4.201型整数规划的典型应用问题222
2.4.3求解小规模01型规划问题的隐枚举法225
2.5指派问题与匈牙利解法227
2.5.1指派问题的数学模型227
2.5.2匈牙利法的基本原理228
2.5.3匈牙利法的求解步骤232
习题2242
第3章非线性规划的基本概念与基本原理246
3.1非线性规划的数学模型246
3.1.1非线性规划问题举例246
3.1.2非线性规划问题的一般数学模型249
3.1.3局部最优解与全局最优解252
3.2无约束问题的最优性条件253
3.2.1多元函数的导数与极值253
3.2.2无约束问题的最优性条件263
3.3凸函数与凸规划271
3.3.1凸函数的定义与性质271
3.3.2凸函数的判别准则277
3.3.3凸规划283
3.4解非线性规划的基本思路285
3.4.1基本迭代格式285
3.4.2下降方向与可行下降方向286
3.4.3非线性规划迭代算法的一般步骤288
3.4.4计算的终止条件291
3.4.5有关收敛速度问题291
3.5一维搜索292
3.5.1黄金分割法294
3.5.2加步探索法302
3.5.3牛顿法305
3.5.4抛物线法307
习题3311
第4章无约束问题的最优化方法313
4.1变量轮换法313
4.2最速下降法317
4.2.1基本原理317
4.2.2最速下降法的算法步骤320
4.3牛顿法323
4.3.1牛顿方向和牛顿法324
4.3.2计算举例326
4.3.3修正牛顿法328
4.4共轭梯度法330
4.4.1共轭方向与共轭方向法331
4.4.2正定二次函数的共轭梯度法335
4.4.3非二次函数的共轭梯度法344
*4.5变尺度法简介346
习题4347
第5章约束问题的最优化方法349
5.1约束极值问题的最优性条件349
5.1.1起作用约束与可行下降方向349
5.1.2库恩塔克条件353
5.2可行方向法360
5.2.1可行方向法的基本原理361
5.2.2可行方向法的计算步骤365
5.3近似规划法377
5.3.1线性近似规划的构成378
5.3.2近似规划法的算法步骤379
5.3.3计算举例380
5.4制约函数法384
5.4.1外点法385
5.4.2内点法391
5.5二次规划396
5.5.1正定二次规划的起作用集方法396
*5.5.2逐步二次逼近法介绍412
习题5414
第6章动态规划417
6.1动态规划问题实例417
6.2动态规划的基本概念420
6.2.1多阶段决策过程420
6.2.2动态规划的基本概念423
6.3最优性定理与基本方程428
6.3.1最优性原理428
6.3.2最优性定理429
6.3.3动态规划的基本方程430
6.4动态规划的应用举例439
6.4.1资源分配问题440
6.4.2生产与库存计划问题447
*6.4.3设备更新问题456
习题6461
第7章用优化软件计算实例464
7.1用MATLAB 7.0优化工具箱计算实例464
7.2用LINDO/LINGO软件计算实例480
习题答案与提示494
参考文献529