數學建模與數學規劃：方法、案例及編程實戰(Python+COPT/Gurobi實現)（簡體書）

本書主要從數學規劃的視角出發，系統地介紹了數學優化問題建模和求解的相關理論、方法、實際案例，以及基於 Python 和數學規劃求解器（COPT 和 Gurobi）的編程實戰。全書共分為四部分。第一部分為基本理論和建模方法，重點介紹了數學規劃模型分類和建模方法（包括邏輯約束與大 M 建模方法、線性化方法）以及計算複雜性理論。第二部分為建模案例詳解，通過理論、案例和實戰相結合的方式，詳細介紹了如何利用各種建模方法和數學規劃求解器對實際生產活動中的優化問題進行建模和求解。這部分內容豐富，案例翔實，代碼完整，旨在提高讀者的實戰能力。第三部分和第四部分聚焦於編程實戰，主要講解如何使用 COPT 和 Gurobi 求解器進行數學規劃模型的編程求解。這兩部分內容涵蓋了調用數學規劃求解器的各種高級用法，可以滿足讀者實現定制化求解的需求。本書適合用作運籌學、數學建模、最優化理論、離散優化等相關課程的高年級本科生、研究生的參考教材，也可供從事數學規劃、運籌學、物流與供應鏈等領域的科研人員、算法開發人員，以及各類數學建模競賽的參賽者閱讀。

劉興祿，2012年至2016年就讀於東北大學工業工程專業（本科）；2016年至2018年就讀於清華大學工業工程系（碩士），專業為物流工程；2018年至今，就讀於清華大學（博士），清華-伯克利深圳學院，管理科學與工程專業。博士期間的主要研究方向為運籌優化模型與算法，強化學習及其應用等，主要應用場景為共享出行、交通優化、物流配送優化、物流倉庫運作優化等；目前，本人已發表3篇SCI期刊論文，1篇SCI期刊論文二輪審稿，2篇EI期刊論文以及多篇EI會議論文和發明專利，並即將在清華大學出版社出版教材一本，名為《運籌優化常用模型、算法及案例實戰：Python+Java實現》。本人於2020年11月創辦"運小籌”公眾號，迄今為止，已經發布技術、科普推文100余篇，粉絲量超過11000，總閱讀量超過23萬次。本人的CSDN帳號，累計閱讀量也超過了23萬次。

目 錄
第 I 部分 基本理論和建模方法
第 1 章 幾種重要的數學規劃模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1 數學規劃模型的分類 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 幾種數學規劃模型的一般形式及簡單案例. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5
1.2.1 線性規劃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 混合整數規劃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.3 二次規劃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.4 二次約束規劃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.5 二次約束二次規劃. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8
1.2.6 二階錐規劃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.7 半定規劃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 數學規劃求解器. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12
第 2 章 邏輯約束和大 M 建模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1 命題和邏輯連接詞 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 邏輯運算與建模. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15
2.2.1 邏輯非 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.2 邏輯與 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.3 邏輯或 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.4 邏輯異或 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 邏輯約束與大 M 建模方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.1 常見邏輯條件建模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.2 大 M 建模方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.3 If-then 約束. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23
2.4 其他邏輯約束建模案例. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.1 至少有 m 個不等式約束成立. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25
2.4.2 至少有 m 個等式約束成立 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.3 計數問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.4 設施選址問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
第 3 章 線性化方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.1 乘積式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32
3.1.1 兩個或多個 0-1 變量相乘 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.1.2 0-1 變量乘以連續變量：情形 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .33
3.1.3 0-1 變量乘以連續變量：情形 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .34
3.1.4 兩個連續變量相乘的凸松弛方法：McCormick 包絡 . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.1.5 調用求解器驗證乘積式線性化方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2 取整 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.3 絕對值. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .38
3.4 min/max 函數 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4.1 max {x1, x2} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4.2 min {x1, x2} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.5 分式函數 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.6 分段線性函數. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.7 特殊有序集約束及其在線性化中的應用. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.7.1 特殊有序集約束 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.7.2 應用案例 1：絕對值表達式的線性化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.7.3 應用案例 2：分段線性函數的線性化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.7.4 應用案例 3：平方根表達式的近似線性化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.8 學術論文中線性化方法的應用案例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
第 4 章 計算複雜性理論簡介. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.1 引言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.2 時間複雜度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2.1 什麼是時間複雜度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2.2 時間複雜度的分析方法與案例. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.3 P、NP、NPC 和 NP-hard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.3.1 P 和 NP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .65
4.3.2 判定問題和優化問題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .66
4.3.3 約化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.3.4 NPC 和 NP-Hard. . . .