线性规划

第一部分 单纯形法

第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 原偶单纯形法之二..1 48

习题五149

第二部分 几个专题

*第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 Konig定理176

6.8.3 标志数法176

6.8.4 匈牙利算法179

6.8.5 匹配算法183

6.9 任务安排的分支定界法184

6.1 0一般的任务安排问题186

6.1 1运输网络189

6.1 1.1 网络流189

6.1 1.2 割切190

6.1 1.3 Ford-Fulkerson定理191

6.1 1.4 标号法193

6.1 1.5 Edmonds-Karp修正算法194

6.1 1.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

全书共9章，分单纯形法和几个专题两部分。第一部分单纯形法，包括数学模型、单纯形法、改善的单纯形法、单纯形法的补充、对偶原理与对偶单纯形共5章。第二部分几个专题，包括运输问题及其他、内点法简介、目标规划、整数规划共4章。第一部分是基本内容；第二部分供各取所需选择内容，概括了线性规划的各个方面，算例丰富是其特点。本书可作为计算机系、数学系、经济管理学院本科生及研究生的教材。