《线性整数规划的数学基础》

引言1

第一章 线性规划12

1 基本概念12

2 单线形方法19

3 改进单纯形方法28

4 允许解的一般表达式32

5 对偶理论36

6 变量带上界限制的线性规划问题40

7 几何意义48

8 字典序单纯形方法51

9 列生成方法57

10 2-分解原则60

11 练习题66

1 基本概念和性质70

第二章 线性整数规划70

2 割平面算法89

3 练习题110

第三章 线性混合整数规划113

1 割平面方法113

2 分解方法121

3 选址问题的分解算法128

4 分枝估界法132

5 隐数法135

6 练习题139

第四章 组合线性规划141

1 图的基本概念141

2 图中的一些极大、极小问题143

3 匹配多面体149

4 2-匹配多面体155

5 均衡矩阵168

6 非负矩阵的配偶性177

7 全对偶整数系统190

第五章 网络流193

1 基本概念193

2 循环流算法199

3 截集树204

4 奇截集212

5 网络单纯形算法217

6 应用223

第六章 拟阵233

1 基本概念和性质233

2 拟阵最优基和最优交241

3 拟阵交多面体255

4 练习题259

第七章 集合分解与覆盖问题261

1 基本概念261

2 覆盖问题的割平面算法267

3 练习题272

第八章 背包问题274

1 背包问题的割平面274

2 背包问题的解法280

第九章 货郎问题286

1 基本概念和性质286

2 算法301

参考文献305