目錄
《運(yùn)籌與管理科學(xué)叢書(shū)》序
序
第1章 引言 1
1.1 整數(shù)規(guī)劃問(wèn)題 1
1.2 整數(shù)規(guī)劃分類與建模 2
1. 2.1 線性混合整數(shù)規(guī)劃 2
1.2.2 非線性整數(shù)規(guī)劃 4
1.2.3 分片線性函數(shù)與分離約束 7
1.3 整數(shù)規(guī)劃問(wèn)題的挑戰(zhàn)性 9
1.4 本書(shū)的結(jié)構(gòu) 10
第2章 線性規(guī)劃 11
2.1 凸分析初步 11
2.1.1 凸集和分離定理 ll
2.1.2 多面體基本知識(shí) 12
2.2 線性規(guī)劃與原始單純形算法 17
2.3 線性規(guī)劃對(duì)偶與對(duì)偶單純形方法 22
第3章 全單模矩陣 26
3.1 全單模性與最優(yōu)性 26
3.2 全單模矩陣的性質(zhì) 28
3.3 全單模矩陣在網(wǎng)絡(luò)問(wèn)題中的應(yīng)用 31
3.3.1 二部圖 31
3.3.2 指派問(wèn)題 32
3.3.3 最小費(fèi)用網(wǎng)絡(luò)流問(wèn)題 33
3.3.4 最大流最小割問(wèn)題 35
3.3.5 最短路問(wèn)題 36
第4章 圖和網(wǎng)絡(luò)流問(wèn)題 38
4.1 基本知識(shí) 38
4.2 最優(yōu)樹(shù) 4l
4.2.1 最小支撐樹(shù) 41
4.2.2 Steiner樹(shù)問(wèn)題 42
4.3 匹配與指派問(wèn)題 43
4.3.1 匹配問(wèn)題 43
4.3.2 指派問(wèn)題 47
4.4 網(wǎng)絡(luò)流問(wèn)題 49
第5章 動(dòng)態(tài)規(guī)劃方法 55
5.1 最短路和最優(yōu)性原理 55
5.2 背包問(wèn)題動(dòng)態(tài)規(guī)劃方法 58
5.2.1 0-1線性背包問(wèn)題 58
5.2.2 線性整數(shù)背包問(wèn)題 60
第6章 計(jì)算復(fù)雜性理論 64
6.1 基本概念 64
6.1.1 判定問(wèn)題和最優(yōu)化問(wèn)題 64
6.1.2 衡量算法的有效性及問(wèn)題的難度 65
6.1.3 NP及P類問(wèn)題 67
6.2 NP完備問(wèn)題 69
6.3 線性整數(shù)規(guī)劃問(wèn)題的復(fù)雜性 70
6.3.1 一般線性整數(shù)規(guī)劃問(wèn)題 70
6.3.2 線性方程組的有界整數(shù)解問(wèn)題 71
6.3.3 線性背包問(wèn)題 72
第7章 分枝定界算法 74
7.1 最優(yōu)性條件和界 74
7.2 分枝定界方法：0-1背包問(wèn)題 75
7.3 分枝定界方法：一般線性整數(shù)規(guī)劃 79
7.4 一般分枝定界方法 82
第8章 割平面方法 85
8.1 有效不等式 85
8.2 Gomory剖平面方法 89
8.3 混合整數(shù)割 94
第9章 多面體和強(qiáng)有效不等式理論 100
9.1 多面體理論及強(qiáng)有效不等式 100
9.2 0-1背包不等式 104
9.3 混合0-1不等式 108
第10章 整數(shù)規(guī)劃對(duì)偶理論 ll4
10.1 拉格朗日對(duì)偶 114
10.1.1 線性整數(shù)規(guī)劃的對(duì)偶 114
10.1.2 線性整數(shù)規(guī)劃對(duì)偶松弛應(yīng)用 115
10.1.3 二次約束0 1二次規(guī)劃對(duì)偶 119
10.1.4 非線性整數(shù)規(guī)劃對(duì)偶問(wèn)題 120
10.2 對(duì)偶搜索方法 122
10.2.1 次梯度方法 122
10.2.2 外逼近方法 125
10.2.3 Bundle方法 127
10.3 對(duì)偶松弛與連續(xù)松弛 130
10.4 替代對(duì)偶 132
第11章 0-1二次規(guī)劃 137
11.1 無(wú)約束0 1二次規(guī)劃 137
11.1.1 問(wèn)題及多項(xiàng)式可解類 137
11.1.2 線性化方法 144
11.1.3 半定規(guī)劃松弛方法 146
11.1.4 分枝定界方法 155
11.2 二次背包問(wèn)題 159
11.2.1 線性松弛方法 159
11.2.2 SDP松弛方法 163
11.2.3 拉格朗日對(duì)偶方法 167
第12章 多項(xiàng)式0—1整數(shù)規(guī)劃 l73
12.1 線性化方法 173
12.2 代數(shù)算法 178
12.3 連續(xù)化方法 181
12.4 SOS與SDP松弛方法 182
12.4.1 元多頊?zhǔn)絻?yōu)化 183
12.4.2 無(wú)約束多元多項(xiàng)式優(yōu)化與SOS松弛 186
12.4.3 約束多項(xiàng)式優(yōu)化問(wèn)題的SOS松弛 191
12.4.4 0-1多項(xiàng)式問(wèn)題的SDP松弛 195
參考文獻(xiàn) 199
《運(yùn)籌與管理科學(xué)叢書(shū)》已出版書(shū)目 201