当前位置: 华文问答 > 科学

有哪些数学系看后久久不能平静的运筹学书籍?

2022-02-04科学

盲猜会有推荐线性规划相关的:

Introduction to Linear Optimization by Bertsimas.

Linear Optimizatio and Extensions: Theory and Algorithms by Shu-Cherng Fang(方述诚).

并且知乎上这两本书被推荐的足够多了,所以就不详细说这两本书了。

线性规划之后,自然的课程可能就是 数值优化和凸优化了。

我知道有的书有多个作者,出于方便我可能只写了一个作者,但没必要在评论区上纲上线。

【最优化:建模、算法与理论】文再文 等著

个人认为是数值优化课程最适合的入门教材了。直接了当切入核心,基本问题、算法、理论都有涉及但又不拘泥于细节使读者迷失方向。这是北大开的【大数据分析中算法】的配套教材,课程有视频可以在b站上找到,书的pdf搜 文再文 课程主页也可以找到。正如这课程和书名字所写的,机器学习问题的建模、算法与理论都讲到了,而且也强调建模出的问题怎么转化为经典的优化问题,比如转化为线性规划啥的。如果你之前有这方面的基础那看起这本书应该是酣畅淋漓。个人认为比Boyd的凸优化读起来舒服很多。

【线性锥优化导论】/【线性锥优化】方述诚、邢文训著

线性锥优化是线性规划最自然的推广,包括线性规划、二阶锥规划、半定规划等内容。这两本书其实内容差不多,第一本是清华数学系的研究生课程 数学规划Ⅱ的教材之一。从凸分析出发建立了完整的 Fenchel对偶理论,并将其应用到了线性锥优化问题中,并且花了极大的篇幅强调如何将模型转化为线性锥优化问题,并且用 二阶锥可表示 这种颇为数学化的方式来叙述。

值得一提的是,书强调了 并不是所有的凸优化问题都是可计算的 ,比如协正锥(co-positive cone)的判定就是个NP-Complete问题,更不要说一般的凸优化问题了。一些人可能看了点Boyd认为凸优化问题都可解(实际上Boyd的凸优化讲的问题都是可计算的线性锥优化问题),并不是这样的。

当然这书缺点也异常明显,写书人表达比较散漫,逻辑也很跳跃,为了书的理论深度和完备性极大牺牲了书的可读性,要不是我上过这门课我可能都没法读完这本书。

然后是一些可能不那么相关的书籍。

Algorithm Design by J.Kleinberg

【算法设计】这本书,也与普林斯顿的红宝书,算法导论并称为算法课程的三大圣经。但这本书我觉得是最推荐的一本,因为它非常强调算法设计的idea,而非算法本身和其实现,书很厚但是很容易读下来。后半部分也详细介绍了计算复杂性理论,进一步讲了随机算法、近似算法等专题,这些专题对于一个运筹学专业的学生来说是非常有必要的。

Lectures on Stochastic Programming: Model and Theory by Shapiro

最近读了一小部分的书,主要是看了关于 Sample Average Approximation 这个部分。由于很多问题其实都是和随机因素相关的,这就自然引出了随机规划问题,著名的代表就是报童问题。这本书作者应该也是数学专业出身,非常喜欢各种引用来给出定理的证明,什么泛函中心极限定理、一致强大数律都很平常。读起来比较困难。

顺带一提,Shapiro 2021年获得INFORMS Von Newmann Prize,运筹学领域的最高奖了

Fundamentals of Supply Chain Theory by Lawrence V. Snyder

很多同学看到供应链管理这个词可能都会比较懵逼,其实这本书包括了基本的库存理论、供应链中的几个著名的组合优化问题,还有一些供应链设计、合同、拍卖理论等内容,而且写的非常简单易懂。如果你对 Facility Location,TSP, VRP 等组合问题感兴趣,那么这本书很适合作为入手点,它介绍了精确解法、近似解,还有各种启发式算法并给出了相应的近似比的证明。

不过说到这本书,就不得不提另外两本著名的书

Logic of Logistics by David Simchi-Levi.

Foundations of Inventory Management by Zipkin.

都是库存管理还有物流相关的重要参考书,不过都写得很难懂,我也没怎么看过(寄。