當前位置: 華文問答 > 科學

有哪些數學系看後久久不能平靜的運籌學書籍?

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.

都是庫存管理還有物流相關的重要參考書,不過都寫得很難懂,我也沒怎麽看過(寄。