網路最佳化：連續和離散模型

《網路最佳化：連續和離散模型》是2013年清華大學出版社出版的圖書，作者是美國的Dimitri P. Bertsekas，由王書寧、牟曉牧、李星野翻譯。

基本介紹

• 書名：《網路最佳化：連續和離散模型》
• 作者：Dimitri P. Bertsekas
• 出版社：清華大學出版社 
• 出版時間：2013年

圖書詳細信息

ISBN：9787302300526

定價：59元

印次：1-1

裝幀：平裝

印刷日期：2012-12-19

圖書簡介

本書介紹網路最佳化的模型、理論和方法，作者為美國麻省理工學院Dimitri P. Bertsekas 教授。

網路最佳化是一類非常有趣的數學規劃問題。

目錄

第1章

引言

1.1圖和流2

1.1.1路和環3

1.1.2流和散度4

1.1.3路流和共軛分解6

1.2網路流模型---例子7

1.2.1最小費用流問題7

1.2.2凸費用網路流問題14

1.2.3多商品流問題15

1.2.4離散網路最佳化問題16

1.3網路流算法---綜述18

1.3.1原費用改進18

1.3.2對偶費用改進21

1.3.3拍賣23

1.3.4好算法,壞算法及多項式算法30

1.4注釋,文獻和習題32

第2章最短路問題45

2.1問題表述與套用46

2.2通用最短路算法50

2.3標記設定(Dijkstra)法56

2.3.1標記設定法的性能59

2.3.2二叉堆法59

2.3.3Dial算法60

2.4標記修正法63

2.4.1Bellman-Ford算法63

2.4.2D'Esopo-Pape算法65

2.4.3SLF算法和LLL算法65

2.4.4閾值算法67

2.4.5標記設定法和標記修正法的比較68

2.5單起點單終點算法69

2.5.1標記設定69

2.5.2標記修正70

2.6拍賣算法73

2.7多起點多終點算法81

2.8注釋,文獻和習題83

第3章最大流問題99

3.1最大流最小割問題100

3.1.1圖的割集102

3.1.2最大流最小割定理104

3.1.3最大和最小飽和割集106

3.1.4不可行網路問題的分解106

3.2Ford-Fulkerson算法108

3.3基於價格的增廣路算法114

3.3.1基於價格的路構造算法116

3.3.2基於價格的最大流算法119

3.4注釋,文獻和習題120

第4章最小費用流問題129

4.1變換和等價130

4.1.1置流量下限為零130

4.1.2消除流量上限130

4.1.3簡化為循環形式131

4.1.4簡化為指派問題132

4.2對偶132

4.2.1互補鬆弛條件和對偶問題的解釋138

4.2.2非負約束的對偶和互補鬆弛條件139

4.3注釋,文獻和習題140

第5章單純形法145

5.1單純形法的主要思想146

5.1.1利用價格確定入邊151

5.1.2確定出邊153

5.1.3處理退化情況156

5.2基本單純形法159

5.2.1單純形法的終止性質159

5.2.2單純形法的初始化160

5.3推廣到具有上下界約束的問題166

5.4實現問題169

5.5注釋,文獻和習題173

第6章對偶上升方法181

6.1對偶上升182

6.2原對偶(序貫最短路)方法188

6.3鬆弛方法198

6.4求解已解決問題的變形206

6.5實現問題207

6.6注釋,文獻和習題209

第7章拍賣算法213

7.1指派問題的拍賣算法214

7.1.1主拍賣算法215

7.1.2近似坐標下降解釋218

7.1.3拍賣算法的變形218

7.1.4複雜性—$\e$-伸縮220

7.1.5處理不可行性224

7.2拍賣算法的推廣226

7.2.1逆向拍賣226

7.2.2非對稱指派問題的拍賣算法230

7.2.3同類人員拍賣算法236

7.3最大流的預流推進法238

7.3.1分析與複雜性241

7.3.2實現問題247

7.3.3與拍賣算法的關係247

7.4$\e$-鬆弛方法256

7.4.1計算複雜性—$\e$-伸縮260

7.4.2實現問題267

7.5拍賣/序貫最短路算法268

7.6注釋,文獻和習題272

第8章非線性網路最佳化283

8.1凸可分問題285

8.2有附加約束的問題290

8.3多商品流問題292

8.4整數約束298

8.5有增益的網路302

8.6最優性條件306

8.7對偶性310

8.8算法和近似314

8.8.1可行方向法314

8.8.2分片線性近似319

8.8.3內點法321

8.8.4罰函式和增廣Lagrange方法322

8.8.5近鄰最小化323

8.8.6光滑化324

8.8.7變換326

8.9注釋,文獻和習題333

第9章凸可分網路問題341

9.1單變數凸函式342

9.2最優性條件345

9.3對偶性347

9.4對偶函式可微性357

9.5可微對偶問題算法360

9.6拍賣算法362

9.6.1$\e$-鬆弛法369

9.6.2拍賣/序貫最短路算法372

9.7單變規劃374

9.8注釋,文獻和習題385

第10章整數約束網路問題389

10.1整數約束問題的描述390

10.2分支定界402

10.3Lagrange鬆弛410

10.3.1對偶函式的次梯度414

10.3.2次梯度法416

10.3.3割平面法419

10.3.4分解和多商品流422

10.4局部搜尋方法426

10.4.1遺傳算法428

10.4.2禁忌搜尋429

10.4.3模擬退火429

10.5部署算法430

10.6注釋,文獻和習題436

附錄A有關數學知識回顧453

A.1集合454

A.2Euclid空間455

A.3矩陣455

A.4分析456

A.5凸集和凸函式458

A.6次梯度459

參考文獻463

索引