本书是陈宝林教授在多年实践基础上编著的.书中包括线性规划单纯形方法、对偶理论、灵敏度分析、运输问题、内点算法、非线性规划KT条件、无约束最优化方法、约束最优化方法、整数规划和动态规划等内容.本书含有大量经典的和新近的算法,有比较系统的理论分析,实用性比较强;定理的证明和算法的推导主要以数学分析和线性代数为基础,比较简单易学.本书可以作为运筹学类课程的教学参考书,也可供应用数学工作者和工程技术人员参考.
本书自1989年出版以来,被一些高等学校选作教学参考书,作者本人也在研究生学位课“最优化方法”和“运筹学”的教学中使用了本教材.经多年教学实践,收到比较满意的效果,总体反映良好,但也发现一些有待改进之处.为了改进教材的不足,拓宽使用范围,更好地适应教学和自学的需要,作者认真听取关心教材建设的专家和读者的建议,决定再版.
第2版教材保持第1版的理论体系和写作特点.增加了基本数学概念介绍、强互补松弛定理、含参数线性规划、运输问题、线性规划路径跟踪法、信赖域方法、二次规划路径跟踪法、整数规划、动态规划等内容.删除一些原有算法,改写了部分章节.与第1版相比,本版教材算法更加丰富,理论有所深入,在一定程度上反映出近些年运筹学一些分支的新进展.
本书由预备知识、线性规划、非线性规划、整数规划和动态规划等五部分组成.使用本教材时,可根据需要决定取舍.一般来讲,要求较多的专业,可用64学时讲授去掉带*号章节后的全部内容;要求较少的专业,可用32学时讲授线性规划和动态规划部分;标有*号的章节可酌情选用.
责任编辑刘颖为本书付出了辛勤劳动,部分插图是清华大学建筑设计研究院陈若光所绘,在此向两位年轻专家表示衷心感谢.
第1章引言1
1.1学科简述1
1.2线性与非线性规划问题2
*1.3几个数学概念5
1.4凸集和凸函数10
习题23
第2章线性规划的基本性质26
2.1标准形式及图解法26
2.2基本性质28
习题35
第3章单纯形方法37
3.1单纯形方法原理37
3.2两阶段法与大M法50
3.3退化情形66
3.4修正单纯形法74
*3.5变量有界的情形85
*3.6分解算法94
习题118
第4章对偶原理及灵敏度分析122
4.1线性规划中的对偶理论122
4.2对偶单纯形法133
4.3原始对偶算法143
4.4灵敏度分析149
*4.5含参数线性规划157
习题163
第5章运输问题167
5.1运输问题的数学模型与基本性质167
5.2表上作业法170
5.3产销不平衡运输问题177
习题178
第6章线性规划的内点算法180
*6.1Karmarkar算法180
*6.2内点法193
6.3路径跟踪法196
第7章最优性条件203
7.1无约束问题的极值条件203
7.2约束极值问题的最优性条件206
*7.3对偶及鞍点问题232
习题243
*第8章算法246
8.1算法概念246
8.2算法收敛问题250
习题253
第9章一维搜索254
9.1一维搜索概念254
9.2试探法256
9.3函数逼近法265
习题280
第10章使用导数的最优化方法281
10.1最速下降法281
10.2牛顿法287
10.3共轭梯度法291
10.4拟牛顿法306
10.5信赖域方法315
10.6最小二乘法322
习题328
第11章无约束最优化的直接方法332
11.1模式搜索法332
11.2Rosenbrock方法337
11.3单纯形搜索法343
11.4Powell方法349
习题358
第12章可行方向法360
12.1Zoutendijk可行方向法360
12.2Rosen梯度投影法371
*12.3既约梯度法379
12.4FrankWolfe方法388
习题392
第13章惩罚函数法394
13.1外点罚函数法394
13.2内点罚函数法401
*13.3乘子法405
习题413
第14章二次规划415
14.1Lagrange方法415
14.2起作用集方法417
14.3Lemke方法422
14.4路径跟踪法426
习题431
*第15章整数规划简介432
15.1分支定界法432
15.2割平面法436
15.301规划的隐数法439
15.4指派问题444
习题450
第16章动态规划简介452
16.1动态规划的一些基本概念452
16.2动态规划的基本定理和基本方程454
16.3逆推解法和顺推解法456
16.4动态规划与静态规划的关系459
16.5函数迭代法463
习题466
参考文献467