<rt id="q93yy"></rt>
|
關于我們
 書單推薦 新書推薦 |
數(shù)學建模與數(shù)學規(guī)劃：方法、案例及編程實戰(zhàn)（Python+COPT/Gurobi實現(xiàn)） 
定 價：98 元
9 7 4 8 8 7 7 1 1 2 7 1 0 讀者對象:本書適合用作運籌學、數(shù)學建模、最優(yōu)化理論、離散優(yōu)化等相關課程的高年級本科生、研究生的參考教材，也可供從事數(shù)學規(guī)劃、運籌學、物流與供應鏈等領域的科研人員、算法開發(fā)人員，以及各類數(shù)學建模競賽的參賽者閱讀。 
本書主要從數(shù)學規(guī)劃的視角出發(fā)，系統(tǒng)地介紹了數(shù)學優(yōu)化問題建模和求解的相關理論、方法、實際案例，以及基于 Python 和數(shù)學規(guī)劃求解器（COPT 和 Gurobi）的編程實戰(zhàn)。全書共分為四部分。第一部分為基本理論和建模方法，重點介紹了數(shù)學規(guī)劃模型分類和建模方法（包括邏輯約束與大 M 建模方法、線性化方法）以及計算復雜性理論。第二部分為建模案例詳解，通過理論、案例和實戰(zhàn)相結合的方式，詳細介紹了如何利用各種建模方法和數(shù)學規(guī)劃求解器對實際生產(chǎn)活動中的優(yōu)化問題進行建模和求解。這部分內容豐富，案例翔實，代碼完整，旨在提高讀者的實戰(zhàn)能力。第三部分和第四部分聚焦于編程實戰(zhàn)，主要講解如何使用 COPT 和 Gurobi 求解器進行數(shù)學規(guī)劃模型的編程求解。這兩部分內容涵蓋了調用數(shù)學規(guī)劃求解器的各種高級用法，可以滿足讀者實現(xiàn)定制化求解的需求。本書適合用作運籌學、數(shù)學建模、最優(yōu)化理論、離散優(yōu)化等相關課程的高年級本科生、研究生的參考教材，也可供從事數(shù)學規(guī)劃、運籌學、物流與供應鏈等領域的科研人員、算法開發(fā)人員，以及各類數(shù)學建模競賽的參賽者閱讀。
劉興祿，2012年至2016年就讀于東北大學工業(yè)工程專業(yè)（本科）；2016年至2018年就讀于清華大學工業(yè)工程系（碩士），專業(yè)為物流工程；2018年至今，就讀于清華大學（博士），清華-伯克利深圳學院，管理科學與工程專業(yè)。博士期間的主要研究方向為運籌優(yōu)化模型與算法，強化學習及其應用等，主要應用場景為共享出行、交通優(yōu)化、物流配送優(yōu)化、物流倉庫運作優(yōu)化等；目前，本人已發(fā)表3篇SCI期刊論文，1篇SCI期刊論文二輪審稿，2篇EI期刊論文以及多篇EI會議論文和發(fā)明專利，并即將在清華大學出版社出版教材一本，名為《運籌優(yōu)化常用模型、算法及案例實戰(zhàn)：Python+Java實現(xiàn)》。本人于2020年11月創(chuàng)辦"運小籌”公眾號，迄今為止，已經(jīng)發(fā)布技術、科普推文100余篇，粉絲量超過11000，總閱讀量超過23萬次。本人的CSDN賬號，累計閱讀量也超過了23萬次。
目 錄
第 I 部分 基本理論和建模方法 第 1 章 幾種重要的數(shù)學規(guī)劃模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1 數(shù)學規(guī)劃模型的分類 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 幾種數(shù)學規(guī)劃模型的一般形式及簡單案例. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 1.2.1 線性規(guī)劃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.2 混合整數(shù)規(guī)劃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.3 二次規(guī)劃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.4 二次約束規(guī)劃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.5 二次約束二次規(guī)劃. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8 1.2.6 二階錐規(guī)劃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.7 半定規(guī)劃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3 數(shù)學規(guī)劃求解器. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .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 計數(shù)問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.4.4 設施選址問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 第 3 章 線性化方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.1 乘積式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32 3.1.1 兩個或多個 0-1 變量相乘 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.1.2 0-1 變量乘以連續(xù)變量：情形 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .33 3.1.3 0-1 變量乘以連續(xù)變量：情形 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .34 3.1.4 兩個連續(xù)變量相乘的凸松弛方法：McCormick 包絡 . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.1.5 調用求解器驗證乘積式線性化方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2 取整 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.3 絕對值. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .38 3.4 min/max 函數(shù) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.4.1 max {x1, x2} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.4.2 min {x1, x2} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.5 分式函數(shù) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.6 分段線性函數(shù). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.7 特殊有序集約束及其在線性化中的應用. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.7.1 特殊有序集約束 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.7.2 應用案例 1：絕對值表達式的線性化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.7.3 應用案例 2：分段線性函數(shù)的線性化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 判定問題和優(yōu)化問題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .66 4.3.3 約化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.3.4 NPC 和 NP-Hard. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .67 4.4 常見的 NPC 和 NP-hard 問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4.5 小結 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 第 II 部分 建模案例詳解 第 5 章 生產(chǎn)計劃優(yōu)化問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 5.1 問題介紹 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 5.2 問題建模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 5.3 完整數(shù)學模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.4 編程實戰(zhàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 5.4.1 算例準備 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 5.4.2 建立模型并求解: Python 調用 COPT 實現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 5.4.3 建立模型并求解: Python 調用 Gurobi 實現(xiàn). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .78 5.5 拓展 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 第 6 章 數(shù)論方程的數(shù)學規(guī)劃模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 6.1 問題簡介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 6.2 方法 1：引入輔助變量進行轉換 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 6.3 方法 2：消去除法運算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 6.4 問題拓展 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 6.5 總結 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 第 7 章 機組排班優(yōu)化問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 7.1 問題描述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 7.2 問題分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 7.3 問題建模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 7.3.1 模型假設 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 7.3.2 符號說明 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 7.3.3 數(shù)學模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 7.4 航班鄰接網(wǎng)絡的相關問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 7.5 編程實戰(zhàn)：Python 調用 COPT 實現(xiàn). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 7.6 編程實戰(zhàn)：Python 調用 Gurobi 實現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 7.7 算例參數(shù)設計與求解結果展示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 7.8 小結 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 第 8 章 配送網(wǎng)絡規(guī)劃問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 8.1 問題描述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 8.2 問題建模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 8.3 完整數(shù)學模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .102 8.4 編程實戰(zhàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 8.4.1 算例數(shù)據(jù)準備 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 8.4.2 建立模型并求解: Python 調用 COPT 實現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 8.4.3 建立模型并求解: Python 調用 Gurobi 實現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 8.4.4 求解結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 8.5 拓展. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 第 9 章 數(shù)字華容道問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 9.1 數(shù)字華容道問題簡介. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 9.2 建模思路詳解. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .108 9.3 完整數(shù)學模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .112 9.4 編程實戰(zhàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 9.4.1 參數(shù)準備 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 9.4.2 測試算例及其相關參數(shù)初始化. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .115 9.4.3 建立模型并求解: Python 調用 COPT 實現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 9.4.4 建立模型并求解: Python 調用 Gurobi 實現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 9.4.5 數(shù)值實驗結果及分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 9.5 拓展. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 9.5.1 允許區(qū)塊移動 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 9.5.2 模型的收緊 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 第 10 章 密集存儲倉庫取貨路徑優(yōu)化問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 10.1 密集存儲倉庫簡介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 10.2 建模思路詳解. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .122 10.2.1 建模方法 1：基于物品編號的模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 10.2.2 建模方法 2：不考慮非目標貨物編號的模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 10.2.3 完整數(shù)學模型：以建模方法 2 為例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 10.3 編程實戰(zhàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 10.3.1 參數(shù)準備 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 10.3.2 建立 NIPA 模型并求解: Python 調用 COPT 實現(xiàn). . . . . . . . . . . . . . . . . . . . . . . . . .133 10.3.3 建立 NIPA 模型并求解: Python 調用 Gurobi 實現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . 134 10.3.4 建立 NIPF 模型并求解: Python 調用 COPT 實現(xiàn). . . . . . . . . . . . . . . . . . . . . . . . . .134 10.3.5 建立 NIPF 模型并求解: Python 調用 Gurobi 實現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . 135 10.4 數(shù)值實驗結果展示及分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 10.5 模型拓展 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 10.5.1 NIPF 模型的約束分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 10.5.2 允許同時移動 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 第 11 章 機器人組裝生產(chǎn)計劃優(yōu)化問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 11.1 問題介紹與分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 11.2 問題一的建模和求解. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 11.2.1 問題分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 11.2.2 模型參數(shù) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 11.2.3 決策變量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 11.2.4 目標函數(shù) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 11.2.5 構建約束 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 11.2.6 完整數(shù)學模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 11.2.7 編程實戰(zhàn)：Python 調用 COPT 實現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 11.2.8 編程實戰(zhàn)：Python 調用 Gurobi 實現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 11.2.9 求解結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 11.3 問題二的建模和求解. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 11.3.1 發(fā)生變化的約束 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 11.3.2 完整數(shù)學模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 11.3.3 編程實戰(zhàn)：Python 調用 COPT 實現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 11.3.4 編程實戰(zhàn)：Python 調用 Gurobi 實現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 11.3.5 求解結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 11.4 總結與拓展. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 第 12 章 車輛路徑規(guī)劃問題及其若干變體 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 12.1 車輛路徑規(guī)劃問題簡介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 12.2 帶容量約束的車輛路徑規(guī)劃問題的建模. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .150 12.2.1 基于弧的建模方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 12.2.2 基于路徑的建模方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 12.3 多車場車輛路徑規(guī)劃問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 12.3.1 問題介紹 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 12.3.2 MDVRP1：允許返回不同車場. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 12.3.3 MDVRP2：必須返回原車場. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .162 12.3.4 小結 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 12.4 帶時間窗的車輛路徑規(guī)劃問題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .163 12.4.1 問題介紹 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 12.4.2 帶硬時間窗的車輛路徑規(guī)劃問題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .164 12.4.3 帶軟時間窗的車輛路徑規(guī)劃問題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .166 12.4.4 小結 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 12.5 帶時間窗的多行程車輛路徑規(guī)劃問題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 12.5.1 問題介紹 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 12.5.2 第一種建模方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 12.5.3 第二種建模方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 12.5.4 小結 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 12.6 帶時間窗的電動車輛路徑規(guī)劃問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 12.6.1 背景簡介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 12.6.2 問題描述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 12.6.3 問題建模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 12.6.4 小結 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 12.7 編程實戰(zhàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 12.7.1 算例數(shù)據(jù)讀取 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 12.7.2 Python 調用 COPT 實現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 12.7.3 Python 調用 Gurobi 實現(xiàn). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .191 12.8 數(shù)值實驗和結果分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 12.8.1 CVRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 12.8.2 MDVRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 12.8.3 VRPTW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 12.8.4 MTVRPTW. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 12.8.5 EVRPTW. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .204 12.9 總結. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .205 第 13 章 取送貨問題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .206 13.1 問題描述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 13.2 問題建模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 13.2.1 一對一的場景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 13.2.2 多對多的場景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 13.2.3 一對多對一的場景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 13.3 一對一場景的編程實戰(zhàn)及結果展示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 13.3.1 算例的生成和讀取 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 13.3.2 建立模型并求解: Python 調用 COPT 實現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 13.3.3 建立模型并求解: Python 調用 Gurobi 實現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 13.3.4 算例參數(shù)設計與結果展示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 13.4 多對多場景的編程實戰(zhàn)及結果展示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 13.4.1 算例的生成和讀取 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 13.4.2 建立模型并求解: Python 調用 COPT 實現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 13.4.3 建立模型并求解: Python 調用 Gurobi 實現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 13.4.4 算例參數(shù)設計與結果展示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 13.5 一對多對一場景的編程實戰(zhàn)及結果展示. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .220 13.5.1 算例的生成和讀取 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 13.5.2 建立模型并求解: Python 調用 COPT 實現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 13.5.3 建立模型并求解: Python 調用 Gurobi 實現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 13.5.4 算例參數(shù)設計與結果展示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 13.6 總結. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .222 第 14 章 無人機與卡車聯(lián)合配送問題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .223 14.1 問題背景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 14.2 兩種聯(lián)合配送模式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 14.2.1 聯(lián)合但無交互的模式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 14.2.2 聯(lián)合有交互的模式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 14.3 建模過程詳解. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .226 14.4 完整數(shù)學模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .231 14.5 編程實戰(zhàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 14.5.1 算例設計 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 14.5.2 算例讀取 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 14.5.3 建立模型并求解：Python 調用 COPT 實現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 14.5.4 建立模型并求解：Python 調用 Gurobi 實現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 14.5.5 解的提取和可視化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 14.6 數(shù)值實驗及結果展示. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 14.7 拓展. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .238 第 III 部分 編程實戰(zhàn)：COPT 第 15 章 基本建模求解方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 15.1 杉數(shù)求解器 COPT 基本介紹. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .241 15.2 COPT 建模求解的準備工作和基本步驟 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 15.2.1 準備工作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 15.2.2 基本步驟 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 15.3 COPT 建模求解入門：食譜搭配問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 15.4 獲取模型的屬性和結果信息 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 第 16 章 建模求解方法進階. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 16.1 建模技巧和輔助工具函數(shù)的使用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 16.1.1 構建表達式的技巧 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 16.1.2 批量添加決策變量/約束 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 16.2 COPT 的重要求解參數(shù) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 16.3 COPT 建模求解進階：下料問題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 第 17 章 非線性優(yōu)化問題建模與求解. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .253 17.1 半定規(guī)劃（SDP） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 17.2 二階錐規(guī)劃（SOCP） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 17.3 凸二次規(guī)劃和凸二次約束規(guī)劃（Convex QP/Convex QCP）. . . . . . . . . . . . . . .257 第 18 章 不可行問題的處理. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 18.1 計算 IIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 18.1.1 實例演示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260 18.1.2 獲取 IIS 計算結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 18.2 可行化松弛. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 18.2.1 計算可行化松弛 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 18.2.2 可行化松弛結果解讀與模型改進. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .262 第 19 章 參數(shù)調優(yōu)工具 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265 19.1 引言. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .265 19.2 參數(shù)調優(yōu)工具的重要功能及參數(shù) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265 19.3 代碼示例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267 第 20 章 初始解和解池 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 20.1 初始解和解池簡介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 20.2 初始解重要參數(shù)介紹. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270 20.3 代碼示例：木材切割問題的初始解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270 20.4 初始解日志解讀 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272 第 21 章 回調函數(shù)的使用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 21.1 引言. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .274 21.2 使用步驟 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 21.3 詳細案例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 第 IV 部分 編程實戰(zhàn)：Gurobi 第 22 章 基本建模方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 22.1 Gurobi 中的建模方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 22.1.1 建模流程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 22.1.2 按行建模和按非零系數(shù)建模. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .283 22.1.3 按列建模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285 22.1.4 按矩陣建模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 22.1.5 Gurobi 中的模型屬性與求解參數(shù). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .289 22.2 Gurobi 中的各類文件格式與相關操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 22.2.1 一個簡單的例子 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 22.2.2 各種類型的文件格式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 22.2.3 模型導入與導出的方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 22.3 模型拷貝與模型松弛. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 22.3.1 模型淺拷貝與深拷貝 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 22.3.2 模型松弛 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 第 23 章 高級建模方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 23.1 多目標優(yōu)化模型的相關操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 23.1.1 Gurobi 多目標函數(shù)詳解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 23.1.2 多目標優(yōu)化模型的建模方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .300 23.1.3 一些注意事項 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 23.2 惰性約束的使用技巧. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 23.2.1 Gurobi 中的惰性更新機制. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .305 23.2.2 Gurobi 中的回調函數(shù) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 23.2.3 惰性約束 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 23.2.4 惰性約束與割平面的區(qū)別 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309 23.3 特殊約束的表達方式及建模方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310 23.3.1 一般約束 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310 23.3.2 廣義約束 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310 23.3.3 其他類型的約束 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312 第 24 章 基本求解進程控制方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 24.1 設置求解終止條件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 24.1.1 設置 TimeLimit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 24.1.2 設置 MIPGap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 24.1.3 其他常見的終止條件參數(shù) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 24.2 設置預處理算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 24.3 設置割平面算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318 24.4 設置啟發(fā)式算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 24.4.1 Gurobi 中的啟發(fā)式方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 24.4.2 Gurobi 啟發(fā)式算法的參數(shù)設置. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .321 24.5 設置優(yōu)化求解策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322 24.5.1 全局優(yōu)化策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322 24.5.2 提升可行解質量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323 24.5.3 加速根節(jié)點松弛求解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323 24.5.4 變量分支選擇 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324 第 25 章 高級求解進程控制方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 25.1 解池管理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 25.1.1 解池的參數(shù)與屬性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 25.1.2 解池功能詳解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 25.1.3 案例演示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327 25.1.4 一些注意事項 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330 25.2 給 MIP 模型賦初始解的方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .331 25.2.1 相關屬性與參數(shù)匯總 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331 25.2.2 為 MIP 模型賦一個初始解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 25.2.3 為 MIP 模型賦多個初始解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 25.2.4 案例演示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 25.2.5 其他相關操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334 第 26 章 各種信息的解讀與獲取方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .335 26.1 求解日志信息. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .335 26.1.1 Gurobi 中的日志類型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 26.1.2 頭部信息 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 26.1.3 MIP 日志 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336 26.1.4 單純形法日志 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 26.1.5 解池與多場景日志 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340 26.1.6 多目標日志 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 26.1.7 分布式 MIP 日志 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 26.1.8 IIS 日志. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342 26.1.9 日志的相關操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 26.2 解的狀態(tài)信息. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .344 26.3 對偶信息獲取. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .345 26.3.1 通過文件操作直接獲取對偶模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .345 26.3.2 當模型可行時，獲取對偶變量 Pi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .345 26.3.3 當模型無界時，獲取極射線 UnbdRay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346 26.3.4 當模型不可行時，獲取 FarkasDual 與 FarkasProof . . . . . . . . . . . . . . . . . . . . . . . 346 26.3.5 對偶信息的應用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348 第 27 章 求解參數(shù)調優(yōu)與模型報錯調試 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349 27.1 參數(shù)調優(yōu) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349 27.1.1 主要功能及相關參數(shù) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349 27.1.2 案例演示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350 27.2 模型的錯誤診斷 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351 27.2.1 使用 IIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351 27.2.2 對模型進行逐步診斷 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353 參考文獻 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355
你還可能感興趣
我要評論
|
