掃一掃
關注中圖網
官方微博
本類五星書更多>
-
>
宇宙、量子和人類心靈
-
>
氣候文明史
-
>
南極100天
-
>
考研數學專題練1200題
-
>
希格斯:“上帝粒子”的發明與發現
-
>
神農架疊層石:10多億年前遠古海洋微生物建造的大堡礁
-
>
聲音簡史
整數規劃:基礎、擴展及應用 版權信息
- ISBN：9787030720641
- 條形碼：9787030720641 ; 978-7-03-072064-1
- 裝幀：一般膠版紙
- 冊數：暫無
- 重量：暫無
- 所屬分類：>
整數規劃:基礎、擴展及應用 本書特色
適讀人群 ：高等院校經濟管理類和理工類等專業本科生、研究生的必修教材，又可作為研究人員、專業人員整數規劃歷史可以追溯到20世紀50年代,美國學者丹齊格（G.B. Dantzig）首次發現可以通過0-1變量來刻畫優化模型中的固定費用、變量上界、非凸分片線性函數等.此后, 丹齊格等對旅行商問題(traveling salesman problem,TSP)的研究,成為分支定界法和現代混合整數規劃算法的開端. 1958年,戈莫里（R.E.Gomory）提出了求解一般整數線性規劃模型的收斂算法——割平面方法,至此整數規劃成為優化領域的一個獨立分支. ?隨著整數規劃理論和算法的不斷發展以及計算機計算速度和功能的迅猛提升,整數規劃已逐漸成為應用*廣泛的優化方法之一,在社會、軍事、生物、計算機以及經濟等各大領域得到了更廣泛的應用和長足的發展. 《整數規劃：基礎、擴展及應用》是電子科技大學、四川大學、中國科學技術大學三位教授多年一線教學經驗的總結，作為整數規劃課程教材本書聚焦于大規模整數規劃模型的求解方法和策略, 深入淺出地闡明了求解大規模整數規劃模型主流方法的基本思想、原理、執行步驟以及在實際問題中的應用,是一本研究性與教學性并重的專業教材.
整數規劃:基礎、擴展及應用 內容簡介
整數規劃是運籌學與優化領域中一個極其重要的研究方向，整數規劃理論和方法在管理科學、工業工程、金融工程、經濟和其他領域有著廣泛的應用。本書是整數規劃領域的入門與提高教材，注重理論與實際相結合，緊密結合經濟管理類專業的特點，系統、深入地講述求解大規模整數規劃問題的主流方法與理論，符號新工科人才培養理念與要求，是一本凸顯前沿性、交叉性與綜合性的教材。全書共分為引言、整數規劃模型、線性規劃、準確離散優化方法、割平面法、列生成算法、拉格朗日松弛算法、Benders分解算法和啟發式算法共9章，每章都加入了眾多案例，涉及算法和分析都配有計算練習并介紹了相關閱讀材料。本書主要介紹求解大規模整數規劃問題的主流方法與理論。全書共分為引言、整數規劃模型、線性規劃、準確離散優化方法、割平面法、列生成算法、拉格朗日松弛算法、Benders分解算法和啟發式算法共9章。
整數規劃:基礎、擴展及應用 目錄
目錄
前言
第1章 引言 1
1.1 *優化 1
1.2 整數規劃 2
1.3 整數規劃的發展歷程 4
1.3.1 模型和應用角度 4
1.3.2 模型求解角度 5
1.4 整數規劃的求解軟件 6
1.5 本書結構 8
第2章 整數規劃建模 9
2.1 背包模型 9
2.1.1 模型介紹 9
2.1.2 應用實例 10
2.2 廣義指派模型 14
2.2.1 模型介紹 14
2.2.2 應用實例 15
2.3 集合包裝、覆蓋和劃分模型 18
2.3.1 模型介紹 18
2.3.2 應用實例 18
2.4 含固定成本的整數規劃模型 27
2.4.1 設施選址模型 28
2.4.2 網絡設計模型 32
2.5 旅行商模型 36
2.5.1 模型介紹 36
2.5.2 模型應用 39
習題二 42
第3章 線性規劃 44
3.1 線性規劃的規范型 44
3.1.1 線性規劃模型的一般形式 44
3.1.2 線性規劃模型的標準型 44
3.1.3 線性規劃模型的規范型 45
3.1.4 線性規劃模型的矩陣形式 48
3.2 線性規劃的基本定理 50
3.2.1 凸集與極點 50
3.2.2 基本定理 52
3.3 單純形法 56
3.3.1 單純形法的思想 56
3.3.2 單純形法的步驟 56
3.3.3 單純形法一般步驟 63
3.3.4 單純形法的矩陣形式 64
3.4 對偶理論 66
3.4.1 對偶問題的基本形式 66
3.4.2 對偶問題的性質 69
3.4.3 對偶問題的經濟學解釋 71
3.4.4 對偶單純形法 73
習題三 77
第4章 精確離散優化方法 84
4.1 全枚舉法 84
4.1.1 全枚舉法介紹 84
4.1.2 全枚舉法復雜度分析 85
4.2 模型松弛 86
4.3 分支定界 89
4.3.1 分支定界介紹 89
4.3.2 分支定界算法 98
4.3.3 分支定界算法的進一步討論 105
4.4 分支定界算法的應用 109
4.4.1 背包問題 109
4.4.2 購買商品問題 113
習題四 119
第5章 割平面法 123
5.1 有效不等式 123
5.1.1 有效不等式定義 123
5.1.2 強有效不等式 126
5.1.3 多面體、面和刻面 128
5.2 Chvatal-Gomory割平面 130
5.3 Gomory割平面 133
5.3.1 純整數線性規劃模型 133
5.3.2 混合整數線性規劃模型 139
5.4 混合整數舍入切 140
5.5 覆蓋不等式 142
5.6 分支定切算法 144
習題五 147
第6章 列生成算法 152
6.1 Dantzig-Wolfe分解 153
6.1.1 基本定理 153
6.1.2 Dantzig-Wolfe分解 153
6.1.3 塊角結構 155
6.2 列生成算法 157
6.2.1 列生成算法 157
6.2.2 列生成算法的改進策略 167
6.3 分支定價算法 173
6.3.1 分支定價算法思想 173
6.3.2 分支策略 176
6.4 分支定價定切算法 177
6.4.1 分支定價定切算法思想 177
6.4.2 常見魯棒切 179
6.4.3 非魯棒切 181
6.5 列生成算法的應用 185
6.5.1 乘務調度問題 185
6.5.2 平行機調度問題 188
習題六 191
第7章 拉格朗日松弛算法 195
7.1 拉格朗日原問題和對偶問題 195
7.2 拉格朗日松弛的進一步討論 198
7.2.1 等式約束的松弛 198
7.2.2 含兩類約束的拉格朗日松弛 198
7.3 拉格朗日對偶問題的求解算法 200
7.3.1 次梯度算法 200
7.3.2 外逼近算法 204
7.3.3 Bundle算法 207
7.4 拉格朗日松弛算法的應用 210
7.4.1 廣義指派問題 210
7.4.2 開放車間調度問題 212
習題七 215
第8章 Benders分解算法 219
8.1 Benders分解算法 219
8.1.1 Benders重表示 220
8.1.2 Benders分解算法 222
8.2 改進策略 229
8.2.1 Benders主問題加速策略 229
8.2.2 Benders切的選擇策略 231
8.2.3 基于CPLEX的Benders分支定切算法 232
8.3 經典Benders分解算法的擴展 234
8.3.1 整數Benders分解算法 234
8.3.2 邏輯Benders分解算法 237
8.4 Benders分解算法的應用 239
8.4.1 無容量限制的多倉庫選址分配問題 239
8.4.2 概率旅行商問題 242
8.4.3 帶有準備時間的不相關平行機調度問題 245
習題八 249
第9章 啟發式算法 252
9.1 精確整數優化方法的局限性 252
9.2 局部搜索算法 253
9.3 元啟發式方法 256
9.3.1 禁忌搜索算法 257
9.3.2 模擬退火算法 262
9.3.3 遺傳算法 267
習題九 272
參考文獻 274
展開全部
整數規劃:基礎、擴展及應用 節選
**章引言 1.1*優化 *優化是一門適應性強、內容豐富的學科領域，不僅在學術界一直受到學者的關注，而且在社會生活領域對實際問題的解決也發揮著至關重要的作用.*優化研究是指在一定約束條件下，從眾多可行選擇中選出*優方案，使系統的目標函數在約束條件下達到*大或*小.它通過組建模型，掌握相關要素之間的關聯，推測各種可行的辦法以及可能發生的結果，從而選取能完成既定任務的*佳決策方案. 一個*優化模型，也稱為數學規劃模型，通常包含以下三個基本要素. 決策變量 *優化問題待定的量值，通過模型計算來確定的決策因素. 目標函數 度量決策方案優劣的標準，通常是與決策變量有關的待求極值(*大值或*小值)函數. 約束條件 限制決策選擇的約束，即求目標函數極值時，決策變量必須滿足的限制.*基本的約束條件是明確變量的類型. *優化模型的一般形式為 min或max目標函數(可以是多個) s.t. 主約束; 變量類型約束.(1.1) 其中s.t.代表subjectto(使服從). 將問題的決策用決策變量表示，其目標是在滿足給定約束的條件下，尋求能夠*大化或者*小化目標函數的決策變量取值. (單目標)*優化模型的一般代數形式為 min或maxf(x1， ，xn) s.t. 其中，x1， ，xn是決策變量，f(x1， ，xn)是目標函數，gi(x1， ，xn)(i=1， ，m)是約束函數，參數bi(i=1，2， ，m)是約束右端系數，每一個約束都可以是“≤”，“=”或者“≥”的形式. 決策變量的某個取值組合稱為模型(1.2)的一個解.滿足模型(1.2)的所有約束條件的解稱為一個可行解，所有可行解構成的集合稱為可行域.可行域中能使目標函數達到*優的解稱為*優解.求解模型(1.2)的方法稱為優化算法. 當f(x1， ，xn)和gi(x1， ，xn)(i=1， ，m)是決策變量x1， ，xn的線性函數時，稱模型(1.2)為線性規劃模型. 1.2整數規劃 當決策變量中含有取值被約束為整數的變量(即存在整數變量)時，稱模型(1.2)為整數規劃模型.其中，所有決策變量都是整數變量的優化問題稱為純整數規劃或全整數規劃模型，而部分變量是整數變量的優化問題稱為混合整數規劃模型.目標函數和約束函數均是線性函數的整數規劃模型，稱為整數線性規劃模型;否則，稱為整數非線性規劃模型. 取值為0或1的整數變量稱為0-1變量或邏輯變量，常被用來表示系統是否處于某個特定狀態，或者決策時是否選擇某個特定方案.如當問題含有多項要素，而每項要素皆有兩種選擇時，可用一組0-1變量來描述.含有0-1變量的整數規劃模型稱為0-1整數規劃模型.0-1整數規劃模型在整數規劃中具有重要地位，一方面，許多實際問題都可以歸結為該類問題，另一方面，任何不含有無界變量的整數規劃模型都與0-1整數規劃模型等價，此外許多非線性規劃模型也可以轉化為等價的0-1整數規劃模型. 整數規劃是運籌學和管理科學中使用*廣泛的優化模型之一.整數規劃在現實生活中尤其是企業的管理和運營中應用廣泛.在資源有限的條件下，針對提升生產和運營效率的問題進行建模優化，如原料分配、生產調度等;同時也可以針對其他計劃問題進行建模優化，如生產計劃問題、車輛路徑問題、物流運輸問題、設施選址、資金預算計劃等.此外，整數規劃的應用領域還包括：公共交通調度和班次安排、民航航班與機組調度安排、電廠發電計劃、通信與網絡設計、金融投資組合、大規模集成電路設計等.許多組合優化、圖論以及計算邏輯問題，也都可以歸結為整數規劃問題.盡管整數規劃模型在解空間結構上優于連續型模型，然而其求解計算的復雜程度卻更高，目前一些著名的難題都是整數規劃問題.因此，如何求解整數規劃模型是學界研究的關鍵. 在求解整數規劃模型時，如果可行域有界，*簡單的求解方法是窮舉所有的可行整數解，然后代入目標函數進行比較，得到*優解.當問題規模較小時，可以輕易窮舉所有滿足約束條件的整數解，這時窮舉的方法是可行且有效的.然而，當問題規模變大或可行域無界時，難以在短時間內甚至無法窮舉所有整數解.此時窮舉法失效，需要設計有效的優化算法進行模型求解. 目前，關于整數規劃模型的求解方法主要包括以下三種：精確算法、啟發式算法和近似算法. 精確算法是指能夠求出問題*優解的算法.整數規劃精確算法的一般步驟如下： 生成一個相關問題，稱為原問題的衍生問題; 在衍生問題基礎上，進一步生成一個更易于求解的松弛問題; 通過求解松弛問題間接得到原問題的解. 由于整數線性規劃模型與線性規劃模型有著密切的關系，而線性規劃模型易于求解，因此，整數規劃模型的精確算法通常是針對相應線性規劃模型的*優解設計有效的算法，主要包括分支定界算法、分支定切算法、分支定價算法和分支定價定切算法.分支定界算法的主要思路是求解整數規劃模型對應的線性規劃模型，把其可行域反復地分割為越來越小的子集(每個子集對應一個子線性規劃模型的可行域)，這稱為分支;然后計算每一支對應子整數規劃模型的一個目標下界(對于*小值問題)，這稱為定界;在每次分析后，凡是界限超出已知*好可行解目標值的那些子集不再進一步分支.因此許多子集可不予考慮，這稱為剪枝.加快分支定界算法收斂速度的一種有效途徑是加強每一支對應子整數規劃模型的目標下界.常用的方法包括 動態地增加相應線性規劃模型的有效不等式(切)，相應方法稱為分支定切算法; 將相應線性規劃模型轉化為等價的Dantzig-Wolfe模型(丹齊格–沃爾夫模型)，進而利用列生成方法進行求解，相應方法稱為分支定價算法; 針對每一支相應的Dantzig-Wolfe模型，既通過列生成方法進行求解，又動態地加切，相應方法稱為分支定價定切算法. 啟發式算法沒有嚴格的理論分析，是算法設計者根據觀察到的經驗或問題結構性質設計的，在可接受的花費(指計算時間和空間)下給出待解決整數規劃模型每一個實例的一個可行解.因此，該可行解與*優解的偏離程度一般不能被預計.當精確算法運行時間長或者無法在有限的時間內求出*優解時，啟發式算法可作為備選方法.通常，許多*優化問題往往需要龐大的計算量.雖然啟發式算法不能求出精確的*優值，但其至少在可控范圍內找到相對較好的可行解，因此啟發式算法在現實生活中應用廣泛.目前，啟發式算法包括構造型方法、局部搜索算法、松弛方法、智能算法等. 近似算法沒有嚴格的定義，一般來說能求出可行解的算法都能歸為近似算法.該類算法是針對特定問題使用貪婪策略、限制、松弛等方法設計的，需要進行算法的近似比和復雜度分析.因此，該類算法的求解規模通常是受限制的，*后獲得的解也可能不是*優解.但相比于啟發式算法，該類算法可以有效度量求得的可行解與*優解的偏離程度.常見的近似算法有貪婪算法、局部搜索算法、松弛算法、近似動態規劃等. 1.3整數規劃的發展歷程 整數規劃的歷史可以追溯到20世紀50年代，美國學者G.B.Dantzig(丹齊格)首次發現可以通過0-1變量來刻畫*優化模型中的固定費用、變量上界、非凸分片線性函數等.此后，Dantzig等對旅行商問題(traveling salesman problem，TSP)的研究，成為分支定界法和現代混合整數規劃算法的開端.1958年，R.E.Gomory(戈莫里)提出了求解一般整數線性規劃模型的收斂算法——割平面方法，至此整數規劃成為*優化領域的一個獨立分支.近年來，隨著整數規劃理論和算法的不斷發展以及計算機計算速度和功能的迅猛提升，整數規劃已逐漸成為應用*廣泛的*優化方法之一，在社會、軍事、生物、計算機以及經濟等各大領域得到了更廣泛的應用和長足的發展. 1.3.1模型和應用角度 整數規劃在實際應用中十分廣泛，很多優化問題都可以抽象為同一類整數規劃模型.如經典的旅行商問題、背包問題(knapsack problem)、切割下料(cutting stock problem)問題等.其中研究*為廣泛的問題為旅行商問題，其在運籌學和理論計算機科學中扮演著非常重要的角色，目前許多優化方法都將其作為一個測試基準.旅行商問題是指給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次并回到起始城市的*短回路.旅行商問題*初應用在交通運輸領域，例如飛機航線安排、郵件派送、快遞服務、校車行進路線設計等.隨著時間的推移，其應用范圍擴展到了許多其他領域，例如電路板印制、晶體結構分析、數據串聚類等. 整數規劃在背包問題方面的研究*早可追溯到1897年，至今已經延續了一個多世紀.其問題可以描述為：給定一組物品，每種物品都有自己的重量和價值，如何選擇物品才能在限定總重量內使得背包內物品的總價值*高.自從背包問題被提出之后，眾多學者對其進行了深入細致的研究和拓展，關于背包問題理論的文獻和研究也是不計其數.同時，背包問題在現實中也有著廣泛的應用，很多實際問題都被抽象為背包問題，例如股市投資、國家預算、資源分配、工業生產和運輸等.因此，背包問題也是組合優化領域中重要的基石之一. 切割下料問題是整數規劃在生產領域中*經典的應用之一.其問題可以描述為：給定一組原材料，如何通過切割、剪裁、沖壓等手段，按照工藝要求將原材料加工成規定大小的成材，從而使所用材料*少或利潤*大.此外，隨著越來越多的復雜系統使用數學框架建模，集劃分問題(set partition problem)、選址問題(facility location problem)、網絡設計問題(network design problem)等一系列整數規劃問題都廣泛應用于生產以及生活的方方面面，未來將會有更多的整數規劃應用模型被發掘. 目前，整數規劃應用研究的總體發展趨勢主要有兩個方面：.1整數規劃與管理科學、網絡科學、生命科學、服務科學等學科的交叉融合日益增強;.2現有算法往往還不能解決交通規劃、生產調度、通信、金融投資等領域中出現的大規模混合整數規劃模型，因此整數規劃研究正朝著大規模混合整數規劃模型的算法設計方向發展. 1.3.2模型求解角度 由于整數約束使得整數規劃模型變得難以求解，目前整數規劃模型求解算法的效率通常比不上求解線性規劃模型的單純形法.影響求解算法計算時間的*大因素是整數變量的數目，以及問題是否具有容易處理的特殊結構.在整數變量數目一定時，0-1整數規劃模型通常比一般整數規劃模型更容易求解.針對具有特殊結構的大規模0-1整數規劃模型，采用特殊的算法求解通常更加容易;而不具有特殊結構的問題，即使整數變量數目較少也難以求解.此外，基于實際問題建立的整數規劃模型通常含有不相關或冗余信息，這些信息也會降低算法求解效率. 自20世紀50年代以來，針對整數線性規劃的研究一直是整數規劃研究的核心內容.一般整數線性規劃模型的求解算法主要是基于分支定界的算法.目前提高分支定界算法效率的主要途徑有兩個：.1提高求解線性松弛模型的速度;.2利用割平面和有效不等式加快收斂速度.一方面，分支定界算法需要求解許多可行域不斷縮小的線性規劃子問題，改進的單純形算法(對偶單純形算法)可以利用熱啟動方法加速求解子問題;另一方面，自從割平面方法被提出以來，基于不同問題結構性質的有效不等式理論得到了很好發展.針對背包問題、旅行商問題和網絡流相關問題等，通過許多簡單或復雜的強有效不等式以及結合這些有效不等式的分支切割方法，大大提高了分支定界算法的速度和效率.針對具有特殊結構的大規模問題，如具有分塊結構的大規模整數線性規劃模型，Dantzig-Wolfe分解和Benders分解(本德爾斯分解)是有效的分解方法，列生成和Benders分解算法分別是求解相應分解模型的高
整數規劃:基礎、擴展及應用 作者簡介
殷允強，電子科技大學經濟與管理學院教授、博士生導師，國家萬人計劃青年拔尖人才，四川省杰青，四川省海內外引進高層次人才.主要從事智能決策與優化，生產與物流運作管理，數據挖掘等方面的研究. 主持國家自然科學基金項目4項，國家社科重大項目1項（子課題負責人），四川省杰出青年科技人才項目、國家留學基金委中法蔡元培國際合作項目等省部級項目多項.2014-2021連續8年入選Elsevier 中國高被引學者榜單.以第一或通訊作者在NRL、EJOR、TRE、Omega、IEEE Transactions on Cybernetics、IEEE Transactions on SMC等國際主流期刊發表SCI論文70余篇. 現任Complex & Intelligent Systems、International Journal of Production Research等多本SCI期刊的副主編、首席客邀編輯，中國管理科學與工程學會理事，中國優選法統籌法與經濟數學研究會船海經濟管理專業委員會副理事長、智能決策與博弈分會秘書長，以及中國運籌學會排序專業委員會等多個分會的（常務）理事. 王杜娟，四川大學商學院教授、博士生導師，入選四川省海內外引進高層次人才千人、四川省特聘專家、四川大學首批“雙百人才工程”百人計劃.主要從事生產與物流運作管理、商務智能與數據挖掘、決策優化理論與方法等領域的教學和科研工作. 主持國家自然科學基金項目、四川省科技計劃項目、中國博士后科學基金特別資助項目等10余項，作為主要完成人參與國家自然科學基金重點項目、科技部科技支撐計劃項目等10項.以第一/通訊作者在NRL、EJOR、Omega、IEEE SMC、JBR、IJPE、ANOR等國內外重要期刊發表高水平論文50余篇，出版學術專著3部. 現任SCI期刊Complex & Intelligent Systems副主編，中國物流學會常務理事、中國自動化學會大數據專委會副主任、中國仿真學會智能仿真優化與調度專委會委員，以及中國運籌學會排序專委會等多個分會的理事. 余玉剛，中國科學技術大學教授，博士生導師，基金委國家創新群體項目負責人，基金委重大項目負責人，國家杰出青年基金等領軍人才獲得者，中國高被引學者(Elsevier, 2014-2021, 連續8年)；現任中國科學技術大學校黨委委員，管理學院執行院長，國際金融研究院院長，現代物流與供應鏈安徽省重點實驗室主任. 研究成果主要集中在基于顛覆技術和數據的現代物流和現代供應鏈管理領域，包括機器人物流、平臺供應鏈、雙碳供應鏈、數據科學等.相關研究發表學術期刊論文150余篇，其中40余篇發表在FMS的A類期刊，近30篇發表在《管理世界》、《系統工程理論與實踐》等中文期刊，15篇發表（含錄用）在M&SOM(Manufacturing and Service Operations Management)、TS(Transportation Science)、ISR(Information Systems Research)、POM(Production and Operations Management)、IISE Transactions頂級期刊. 相關研究獲一項教育部人文社會科學一等獎，一項教育部自然科學一等獎，1篇論文入選十二五《國家自然科學基金資助項目優秀成果選編》，2篇論文被IIE Transactions主編選為“featured article”并在美國工業工程師協會行業期刊IE Magazine雜志專欄介紹，多篇論文被Science direct評為“top 25 hottest articles”，一篇論文被Elsevier出版社選為Elsevier經濟學期刊中大陸作者發表的“Most Cited Articles”(2004-2008)，獲美國電子與電氣工程師協會IEEE ICNSC會議(10th IEEE International Conference on Networking, Sensing and Control, April 10-12, 2013, France)的最佳應用論文獎，美國工業與系統工程協會（IISE）年會最佳應用論文提名獎，中國系統工程學會 理論貢獻獎（2016），中國物流與采購聯合會科技進步獎一等獎，獲得多項國家發明專利等.
書友推薦
- >
詩經-先民的歌唱
- >
史學評論
- >
回憶愛瑪儂
- >
莉莉和章魚
- >
苦雨齋序跋文-周作人自編集
- >
朝聞道
- >
月亮虎
- >
隨園食單
本類暢銷
