【2023新书】线性规划计算，第2版

这一专著代表了自George Dantzig于1947年首次发现单纯形法以来，线性规划(LP)领域的历史性突破。 它既周到又信息量大，通过强调LP方面的新成就，着重反映和促进最先进的技术。这个新版本分为两卷。第一卷讨论了LP的基础，包括可行域的几何形状、单纯形方法及其实现、对偶和对偶单纯形方法、原始-对偶单纯形方法、灵敏度分析和参数LP方法、广义单纯形方法、分解方法、内点法和整数LP方法。第二卷主要介绍作者的贡献，如有效的原始/对偶pivot规则、原始/对偶Phase-I方法、简化/d -简化单纯形方法、广义简化单纯形方法、原始/对偶亏基方法、原始/对偶面方法、一种新的分解原理等。 这一版做了许多重要的改进。第一卷包括一些新结果，如混合两阶段单纯形算法、对偶消除、降低成本的新定价机制、双层LP模型和最优解集的截取。特别地，对chapter Integer LP方法进行了改写，使其在新的ILP求解器{\it controlling -cutting/branch}方法的目标切割方面有了很大的改进，并对控制分支方法进行了很好的实现。

在第二卷中，“单纯形可行点算法”被重写，并从“关键内点法”一章中删去，改为“单纯形内点法”一章，它代表了由传统单纯形算法转化而来的一类高效内点算法。由于剩余的算法代表了由普通内点算法转化而来的另一类高效内点算法，因此原章的标题被改为“人脸内点方法”。在不利用稀疏性的情况下，使用Cholesky分解实现原始/双重人脸方法。为了处理稀疏计算，在第二卷中增加了两个讨论LU因子分解的章节。最令人兴奋的改进来自对简化单纯形法的重新发现。在第一版中，原型的推导是在一个标题相同的章节中介绍的，然后在另一章中转换为所谓的“改进”版本。幸运的是，作者最近找到了一个相当简洁的新推导，所以他现在可以在一章中介绍独特的fresh单纯形方法。令人兴奋的是，简化单纯形法有望成为有史以来最好的LP求解器。 以计算为重点，当前版本包含许多新颖的想法，理论和方法，由坚实的数值结果支持。它的内容简洁明了，从简单到深刻，呈现出一种新鲜的方式。特别是，大量的例子被用来演示算法。这本书是LP领域的稀有作品，是LP及其相关领域的本科生和研究生、教师、从业者和研究人员不可或缺的工具。