第一部分 单纯形法 3
第1章 数学模型 3
1.1 引言 3
1.2 问题的提出 4
1.3 标准形式与矩阵表示 8
1.4 几何解释 9
习题一 12
第2章 单纯形法 15
2.1 凸集 15
2.1.1 凸集概念 15
2.1.2 可行解域与极方向概念 16
2.2 凸多面体 17
2.3 松弛变量 18
2.3.1 松弛变量概念 18
2.3.2 松弛变量的几何意义 19
2.4 单纯形法的理论基础 21
2.4.1 极值点的特性 21
2.4.2 矩阵求逆 22
2.4.3 可行解域无界的情况 23
2.4.4 退化型举例 25
2.5 单纯形法基础 26
2.5.1 基本公式 26
2.5.2 退出基的确定与进入基的选择 27
2.5.3 举例 29
2.6 单纯形法（续） 31
2.6.1 基本定理 31
2.6.2 退化型概念 32
2.6.3 单纯形法步骤 33
2.6.4 举例 34
2.7 单纯形表格 40
习题二 49
第3章 改善的单纯形法 52
3.1 数学准备 52
3.2 改善的单纯形法 54
3.2.1 改善的单纯形法的步骤 54
3.2.2 举例 55
3.3 改善的单纯形法表格 60
3.3.1 表格的介绍 60
3.3.2 复杂性分析 63
习题三 64
第4章 单纯形法的补充 66
4.1 二阶段法 66
4.2 大M法 74
4.3 变量有上下界约束问题 79
4.3.1 下界不为零的情况 79
4.3.2 有上界的约束 79
4.4 退化情形 87
4.4.1 退化形问题 87
4.4.2 出现循环举例与防止循环的Bland准则 88
4.5 灵敏度分析 90
4.5.1 C有变化 91
4.5.2 右端项改变 93
4.5.3 aij改变 94
4.5.4 A的列向量改变 95
4.5.5 A的行向量改变 96
4.5.6 增加新变量 98
4.5.7 增加新约束条件 99
4.5.8 应用举例 101
4.5.9 参数规划 102
4.6 分解原理 104
4.6.1 分解算法 105
4.6.2 说明举例 106
4.7 无界域问题的分解算法 116
4.7.1 分解原理 116
4.7.2 说明举例 116
习题四 121
第5章 对偶原理与对偶单纯形法 126
5.1 对偶问题 126
5.1.1 对偶问题定义 126
5.1.2 对偶问题的意义 127
5.1.3 互为对偶 128
5.1.4 Ax＝b的情形 129
5.1.5 其他类型 130
5.2 对偶性质 132
5.2.1 弱对偶性质 132
5.2.2 强对偶性质 133
5.2.3 min问题的对偶解法 133
5.3 影子价格 138
5.4 对偶单纯形法 140
5.4.1 基本公式 140
5.4.2 对偶单纯形法 141
5.4.3 举例 142
5.5 原偶单纯形法 146
5.5.1 问题的引入 146
5.5.2 原偶单纯形法之一 147
5.5.3 原偶单纯形法之二 148
习题五 149
第二部分 几个专题 155
第6章 运输问题及其他 155
6.1 运输问题的数学模型 155
6.1.1 问题的提出 155
6.1.2 运输问题的特殊性 156
6.2 矩阵A的性质 157
6.3 运输问题的求解过程 158
6.3.1 求初始可行解的西北角法 158
6.3.2 最小元素法 160
6.3.3 图上作业法 161
6.4 ci—zi的计算，进入基的确定 162
6.5 退出基的确定 163
6.6 举例 165
6.7 任务安排问题 171
6.7.1 任务安排与运输问题 171
6.7.2 求解举例 172
6.8 任务安排的匈牙利算法 174
6.8.1 代价矩阵 174
6.8.2 K？nig定理 176
6.8.3 标志数法 176
6.8.4 匈牙利算法 179
6.8.5 匹配算法 183
6.9 任务安排的分支定界法 184
6.10 一般的任务安排问题 186
6.11 运输网络 189
6.11.1 网络流 189
6.11.2 割切 190
6.11.3 Ford-Fulkerson定理 191
6.11.4 标号法 193
6.11.5 Edmonds-Karp修正算法 194
6.11.6 Dinic算法 196
习题六 198
第7章 内点法简介 200
7.1 Klee与Minty举例 200
7.2 数学准备 202
7.2.1 Lagrange乘数法 202
7.2.2 Kuhn-Tucker条件 203
7.2.3 垂直投影矩阵 204
7.2.4 最速下降法 205
7.2.5 牛顿法介绍 205
7.2.6 罚函数概念 206
7.2.7 中心路径 207
7.3 路径跟踪法 207
7.3.1 原偶对称型 207
7.3.2 KKT方程组及牛顿法 209
7.3.3 μ的确定，步长的确定 210
7.3.4 初始值和结束准则 211
7.3.5 算法步骤 211
7.3.6 收敛性的讨论 212
7.3.7 KKT方程组的重要归约 214
7.4 梯度法与仿射变换 215
第8章 目标规划 218
8.1 问题的提出 218
8.2 目标规划的几何解释 221
8.3 目标规划的单纯形表格 226
8.4 目标序列化方法 229
8.5 目标规划的灵敏度分析 234
8.6 应用举例 245
习题八 248
第9章 整数规划 252
9.1 问题的提出 252
9.2 整数规划的几何意义 256
9.3 0-1规划和DFS搜索法 258
9.3.1 穷举法 258
9.3.2 DFS搜索法 259
9.4 0-1规划的DFS搜索法 262
9.4.1 搜索策略 262
9.4.2 举例 264
9.5 替代约束 267
9.5.1 Geoffrion替代约束 267
9.5.2 举例 269
9.6 分支定界法 275
9.6.1 对称型流动推销员问题 275
9.6.2 非对称型流动推销员问题 276
9.7 整数规划的分支定界解法 278
9.8 分支定界法在解混合规划上的应用 288
9.9 背包问题的分支定界解法 292
9.10 整数规划的割平面法 297
9.10.1 Gomory割平面方程 297
9.10.2 举例 298
9.11 割平面的选择 304
9.12 Martin割平面法 307
9.13 全整数割平面法 312
9.13.1 全整数单纯形表格 312
9.13.2 举例 314
9.14 混合规划的割平面法 319
习题九 321