序言

数学科学不仅是自然科学的基础，也是一切重要技术发展的基础.电子计算机的发明及计算技术的发展都以数学为其理论基础.计算机技术的发展使得数学的应用更加直接和广泛，同时也正在改变人们对数学的传统认识.数学素质已成为今天培养高层次创新人才的重要基础.

计算数学是一门随着计算机发展而形成的学科，研究如何应用计算机有效地求解各类计算问题的方法和理论，其中涉及的计算问题主要来源于科学研究和工程设计，因此人们又称这门学科为科学计算.今天，计算和实验、理论分析一起成为当今科学活动的主要方式.在物理、化学、力学、材料科学、环境科学、信息科学和生物科学等领域，计算方法和技术已经成为被广泛接受的科学研究手段，这一系列计算性的分支学科统称为计算科学.现在，计算在科学研究和工程设计中几乎无处不在，对科技的发展起到举足轻重的作用.由于计算数学的发展已有50多年的历史，在教学科研方面有着深厚的积累，传统的教材建设也相对比较规范.伴随着计算机技术突飞猛进的发展，特别是超大规模计算机平台的建立和使用，以及科学研究中不断增长的对计算方法和技术的需求，传统的计算数学教材已不能满足教学的需要.

信息化已成为当今世界发展的重要趋势，也是衡量一个国家现代化水平的重要标志.信息科学可以理解为信息获取、传输、处理与控制的科学.我国信息科学发展的时间相对较短，但发展迅猛.发展信息科学需要数学基础，当然也离不开计算机科学.由于信息科学的多学科交叉的特点，在不同院校和专业，信息科学都得到了一定的发展.但也正是这些原因，使得信息科学的学科定位，尤其是教材建设百家争鸣，缺乏统一的规范，给教学带来了很大的实际困难.

教育部1998年颁布的普通高等院校专业目录中，“信息与计算科学”专业被列为数学类下的一个新专业.这一新专业的设置很好地适应了新世纪以信息和计算技术为核心的数学人才的培养.然而，作为一个新专业，对其专业内涵、专业规范、教学内容与课程体系等有一个认识与探索的过程.教育部数学与统计学教学指导委员会经过多年艰苦细致的工作，对一些问题有了比较明确的指导意见，发表了《关于信息与计算科学专业办学现状与专业建设相关问题的调查报告》及《信息与计算科学专业教学规范》（讨论稿）（见《大学数学》第19卷1期（2003））.按照新的教学规范，信息与计算科学专业是以信息技术和计算技术的数学基础为研究对象的理科类专业.其目标是培养学生具有良好的数学基础和数学思维能力，掌握信息与计算科学基础理论、方法与技能，能解决信息技术和科学与工程计算中实际问题的高级专门人才.

近年来在教育部领导下，高等院校每年大量扩大招生，从而使得我国的高等教育从精英化向大众化转变.现在全国大约有400所高校开办了“信息与计算科学”专业，每年招收 3万名左右的本科生.其中大部分学校缺乏从事该领域教学科研经验的教师，对专业的定位及课程设置也不明确.即使是全国一流的高校，也是偏向于单一学科，新专业没有一个完整的切实可行的教学大纲，适合交叉学科专业的教材极其匮乏。

“信息与计算科学”专业属于数学类，前两年的课程基本上是明确的，教材也很多.本套系列教材重点建设后两年的专业课.由于重点高校大部分有自己的课程体系和教材建设，本系列教材主要针对普通高等学校开办的该专业.依据教育部“强基础，宽口径，重实际，有侧重，创特色”的办学指导思想，清华大学出版社组织的《高等院校信息与计算科学专业系列教材》编委会成员对专业定位、课程设置、教材内涵等进行了深入的探讨，并邀请有多年教学和科研经验的教师编写系列教材.特别是北京大学姜明教授等对涉及信息科学的教材建设花费了大量心血，在此对他们表示感谢.

为适应不同类型院校和不同层次要求的课程需求，教材建设也需要多样化和层次化.我们相信，该系列教材的出版对缓解本专业教材的紧缺局面，逐步形成专业定位与课程设置，推动信息与计算科学的发展，培养适应时代发展的交叉学科人才，提高中国数学教育水平起到一定的作用.

张平文2005年9月

前言

最优化方法广泛应用于工业、农业、交通运输、商业、国防、建筑、通信与政府机关、管理等各个部门、各个领域；它主要解决最优计划、最优分配、最优决策、最佳设计、最佳管理等最优化问题.掌握最优化思想并善于对遇到的问题进行优化处理是各级各类管理人员必须具备的基本素质，也是培养高层次创新人才所必须具有的重要素质.本教材就是帮助信息与计算科学专业的学生学习如何根据各类实际问题的特点，抽象出不同的数学模型，然后选择相应的方法进行计算及分析其结果，为在今后工作中进行优化处理打下基础.其次，本课程也是该专业的学生学习某些相关课程的前提.

本教材是一本着重实际应用又有一定理论深度的最优化方法教材，内容包括线性规划、运输问题、整数规划、目标规划，非线性规划（无约束最优化与有约束最优化），动态规划等最基本、应用最广又最有代表性的最优化方法.书中对于基本的理论、主要的定理都给予了证明，使读者不仅知其然，而且知其所以然，为其举一反三、扩大应用面打好基础.

本书注重联系实际.在介绍每一种规划模型前都以实际问题引入.在讲清概念和理论后，对各种算法都有详细的推导过程，且配有例题、参照例题的解法，读者可以比较容易理解算法的原理和掌握算法的基本步骤，并学会如何应用这些算法.书中还配有几十个各行各业的应用实例，读者参照这些实例可以学习到如何根据实际问题建立相应数学模型的方法与技巧.

建立数学模型是为了解决实际问题，得到计算结果.书中还列举了用新版本的MATLAB及LINDO/LINGO软件包进行计算分析结果的实例.

本教材在阐述基本概念与基本理论时，力求清晰、透彻，在适当地方配置了一些思考题，以促使读者深入思考，加深对内容的理解.在文字叙述方面力求语言浅显、简易明了、深入浅出，以便于读者学习.

书中各章都配有习题，书末给出了答案与提示.

本书主要对象是“信息与计算科学”专业的大学生.也可供其他专业的教学作参考.

在编写本书的过程中，得到“高等院校信息与计算科学专业系列教材”编委会成员与清华大学出版社的大力支持.在多年的教学实践及编写本书的过程中，编者从许多国内外专家、学者的著作中汲取了营养，获益匪浅，本书直接或间接地引用了他们的部分成果（见书末参考文献）.第7章中用MATLAB及LINDO/LINGO软件计算的部分例题是由牛波同学完成的.在此一并表示感谢与敬意.

由于成书时间仓促，作者水平有限，书中缺点甚至错误在所难免，敬请专家、学者及读者不吝指教.

编者2006年10月