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