线性规划导论：英文版

　　这本教材是从一门高级的本科生数学课程演变而来的。本书覆盖了线性规划的基本主题，同时包含许多高级主题。通过不同难易程度的习题，为学生提供逐步提高的机会，并使优秀的学生完成更具挑战性的任务。本书特点●强调逻辑和应用建模，使得管理、经济和运筹学等非数学专业的学生能在各自的领域中学习使用线性规划。●应用数学工具，但不依赖严密的数学发展，为数学专业的高年级学生提供进一步研究所需的理论。●不同难易的习题为不同程度的学生提供具有挑战性的任务。●附录介绍有关数学规划更深材料，为数学专业学生提供高级主题和为面向应用的学生提供已知方法的参考。●论述建模问题的系统方法论，为学生指明如何将建模发展为一种技能，而不是依赖他们的直觉解决问题。●利用计算机软件解决线性规划问题，指导学生利用各种计算机软件包以及在线软件解决线性规划问题。本书的习题答案可http：//www.math.psu.edu/vstein/LPbook/sol2.pdf上下载，也可登录华章网站。本书前言为什么要写本书？这本教材是从一门高级的本科生数学课程演变而来的，课程的对象是具有不同数学基础和来自不同专业的学生，包括数学、计算机科学、统计学、工程科学、中等教育、精算学、计算机工程学、理学、工商学专业的学生。有些是按五年制理学和工商学整合型教学计划读工商管理硕士的学生，而有些是攻读博士学位的学生。由于这门课程不需要诸如微积分、微分方程、抽象代数、拓扑学或数论等高深的数学理论，所以为那些只具有中等数学基础的学生学习一些实用而又重要的数学提供了一个机会。考虑到这一点，只要可能，本书就尽量避免使用诸如向量空间、行列式、梯矩阵、极限和导数等高深或复杂的数学概念。许多学生之所以选修这门课程，是因为线性规划在商业和其他领域有广泛的使用。他们需要学习如何对实际问题建模，如何改写模型以便用具体的计算机软件求解，以及如何解释计算结果并应用于实际问题。一旦计算机不能得到任何计算结果或者结果没有意义，他们应该能够对问题进行调整或者另外选择一个合适的软件。在线性规划方面有许多优秀的教科书，但其中大多数需要很强的数学基础，只适于数学专业使用，或者只有知识超前的学生能够阅读，而包含的材料又大大超出一个学期的课程。真正具有挑战性的是同时让高层次的学生和初学者在同一个课堂学习！在宾夕法尼亚州立大学，虽然线性代数是学习线性规划的先修课程，但课堂上有些学生解线性方程组存在困难。另一方面，课堂上有些学生在数学或计算机科学方面却很强。因此，我尝试不重蹈传统教材的老路，因为它们有点像民间故事中的金发姑娘拒绝食用的麦片粥一样—它们包含的题材要么太“冷”（内容过于平凡），要么太“热”（需要严格的数学基础）。前者会使许多学生感到厌烦；而后者会有一些内容使许多学生难于接受。这本教材从入门开始介绍，只假定读者具有很少的数学基础。因此，我给读者提供了一个机会，在学习线性规划的同时，在看到单纯形方法之前，首先了解线性代数和逻辑学中的相关工具。有关逻辑的一节是线性规划的重要组成部分，虽然这一点经常被忽视。在整本书中，我介绍了大量的例子和应用，并要求学生尝试不同难度的习题。学生们很喜欢这种学习线性规划的方法，这可以从选修这门课程的学生数量以及他们在学期末的评价表中给出的评价得到证实。计算机应用的普遍性并没有消除对计算技巧的需求，但增加了逻辑技巧的相对重要性。现在，如果你能通过手工计算得到圆周率的前100位数字，那只是出于好奇，而不能算是什么重要的结果，因为目前的计算机能够把圆周率的前1010位数字算出来。但是，从逻辑上看，是否有可能把圆周率的第10100位数字算出来呢？如何使用本书这本教材是按照三个层次写的。即使对于不了解线性代数和微积分的学生来说其中大部分内容也可以读懂。对于程度更高的学生，本书给出了一些注释和习题。在书后的附录中，给出了线性规划和数学规划其他方面发展的一般思想，为进一步研究提供指导。附录中还给出了第1章至第8章中提到过的需要更强数学基础的一些主题的细节，并对高于典型的美国大学本科生水准的那部分学生提供经验和高深知识。教材中给出了很多例子及其解答，所以我觉得没有必要给学生提供大量习题的答案。即便如此，在本书的最后，我还是给出部分习题的答案，包括那些比较棘手的习题。习题的难度是不同的，但所有习题都可以用手工计算求解。我没有提供用计算机求解具有很大优势的习题。第1章第1节的习题除了可以检查对各种定义的理解外，还可以测试学生的数学基础。致谢及参考资料我的课堂讲稿经过了几年的演进，很多学生和阅卷评分者对讲稿的改进做出了贡献，他们指出其中的印刷错误和其他错误，并提出各种各样的问题。PrenticeHall出版社的审阅人和编辑也提了许多修改和改进意见。我故意没有将本书与任何一个特定的软件联系起来，因为我相信学生学习了本书的材料后，当他们面对一个好的软件包时，能够聪明地应用这些知识。还有一个原因是，随着新软件包的出现以及计算机和操作系统的发展，任何一个特定的软件包都会很快过时。但是，允许上课的学生使用他们喜欢的任何软硬件，即使在测验时也是如此。能够求解线性规划问题的软件包包括Mathemetica、Maple、Excel等。在因特网上有很多有关线性规划的软件，有的可以免费下载，有的可以在线使用。因特网上也有很多关于线性规划的有用信息。这里我列举一些网址，不过要记住，网上的变化是很快的：*http：//carbon.cudenver.edu/hgreenbe/glossary/（数学规划词汇表）*http：//www.mathprog.org/（数学规划学会）*http：//iris.gmu.edu/asofer/siagopt.html（美国工业与应用数学学会最优化活动组）*http：//solon.cma.univie.ac.at/neum/glopt.html（全局最优化，维也纳）*http：//www.informs.org/Resources/（美国运筹学与管理科学学会）在网络上以“线性规划”为关键词，可以搜索到很多网站。有关线性规划的书也很多，在2002年8月16日，从网http：//www.amazon.com上检索到的“线性规划”的书多达771本。也有很多杂志发表线性规划和非线性规划方面的文章。在2002年8月16日，网http：//www.informs.org/Resources/上列出运筹学方面的36种纸介质的杂志和14种在线杂志。该网站还列出运筹学方面的35个学会。

　　利奥尼德·尼森·瓦泽斯坦，于1966年在莫斯科国立大学获得数学硕士学位，1969年在该校获得数学博士学位。1984-1985年是普林斯顿高级研究所的成员，曾担任几种数学期刊和文摘杂志的评论员。现任宾夕法尼亚州立大学教学教授。

Chapter 1.  Introduction
 1.  What Is Linear Programming?
 2.  Examples of Linear Programs
 3.  Graphical Method
 Chapter 2.  Background
 4.  Logic
 5.  Matrices
 6.  Systems of Linear Equations
 Chapter 3.  Tableaux and Pivoting
 7.  Standard and Canonical Forms for Linear Programs
 8.  Pivoting Tableaux
 9.  Standard Row Tableaux
 Chapter 4.  Simplex Method
 10.  Simplex Method, Phase 2
 11.  Simplex Method, Phase 1
 12.  Geometric Interpretation
 Chapter 5.  Duality
 13.  Dual Problems
 14.  Sensitivity Analysis and Parametric Programming
 15.  More on Duality
 Chapter 6.  Transportation Problems
 16.  Phase 1
 17.  Phase 2
 18.  Job Assignment Problem
 Chapter 7.  Matrix Games
 19.  What are Matrix Games?
 20.  Matrix Games and Linear Programming
 21.  Other Methods
 Chapter 8.  Linear Approximation
 22.  What is Linear Approximation?
 23.  Linear Approximation and Linear Programming
 24.  More Examples
 Appendix. Guide to Mathematical Programming
 A1.  Mathematical Programming
 A2.  Univariate Programming
 A3.  Convex and Quadratic Programming
 A4.  Multivariate Programming
 A5.  Interior Methods
 A6.  Perturbation
 A7.  Goal Programming
 A8.  Linear Programming in Small Dimension
 A9.  Integer Programming
 A10.  Sorting, Order Statistics, and Saddle Points
 A11.  Other Topics and Recent Developments
 Bibliography
 Index
</font>