单目标、多目标与整数规划PDF电子书下载

第1章 引论 1

1.1 引言 1

1.2 问题的提出 2

1.3 标准形式与矩阵表示法 6

1.4 几何解释 7

习题一 11

第2章 单纯形法 13

2.1 凸集 13

2.1.1 凸集概念 13

2.1.2 可行解域与极方向概念 14

2.2 凸多面体 15

2.3.1 松驰变量概念 17

2.3 松驰变量 17

2.3.2 松驰变量的几何意义 18

2.4 单纯形法的理论基础 19

2.4.1 极值点的特性 19

2.4.2 矩阵求逆 21

2.4.3 可行解域无界的情况 21

2.4.4 退化型举例 23

2.5 单纯形法基础 24

2.5.1 基本公式 24

2.5.2 退出基的确定与进入基的选择 26

2.5.3 例 27

2.6 单纯形法(续) 29

2.6.1 基本定理 29

2.6.2 退化型概念 30

2.6.3 单纯形法步骤 31

2.6.4 举例 33

2.7 单纯形表格 38

习题二 48

第3章 改善的单纯形法 50

3.1 数学准备 50

3.1.1 改善之一：CB(B？α)=(CB/B？)α 50

3.1.2 改善之二：矩阵求逆 50

3.2 改善的单纯形法 52

3.2.1 改善单纯形法步骤 52

3.2.2 举例 53

3.3 改善的单纯形法表格及其分析 58

3.3.1 改善的单纯形法表格 58

3.4.1 下界不为零的情况 62

3.4 变量有上下界约束的问题 62

3.3.2 改善单纯形法的复杂性分析 62

3.4.2 有上界的情况 63

3.5 分解原理 68

3.5.1 问题的提出 68

3.5.2 分解算法 69

3.5.3 说明举例 71

3.6 无界域问题的分解算法 80

3.6.1 分解原理 80

3.6.2 说明举例 81

习题三 86

第4章 单纯形法的若干补充与灵敏度分析 89

4.1 二阶段法 89

4.2 大M法 98

4.3.1 退化形问题 103

4.3 退化情形 103

4.3.2 出现循环举例 104

4.4 防止循环 106

4.4.1 退出基不唯一时的选择办法 106

4.4.2 首正向量概念 107

4.4.3 不出现循环的证明 108

4.5 灵敏度分析 109

4.5.1 C有变化 110

4.5.2 右端项改变 112

4.5.3 αij改变 112

4.5.4 A的列向量改变 114

4.5.5 A的行向量改变 115

4.5.6 增加新变量 117

4.5.7 增加新约束条件 118

4.5.8 应用举例 120

4.5.9 参数规划 121

习题四 123

第5章 对偶原理与对偶单纯形法 127

5.1 对偶问题 127

5.1.1 对偶问题定义 127

5.1.2 对偶问题的意义 128

5.1.3 互为对偶 129

5.1.4 Ax=b的情形 130

5.1.5 其他类型 131

5.2 对偶性质 132

5.2.1 弱对偶性质 132

5.2.2 强对偶定理 133

5.2.3 min问题的对偶解法 134

5.3 影子价格 139

5.4 对偶单纯形法 140

5.4.1 基本公式 140

5.4.2 对偶单纯形法 142

5.4.3 举例 142

5.5 主偶单纯形法 146

5.5.1 问题的引入 146

5.5.2 主偶单纯形法之一 147

5.5.3 主偶单纯形法之二 148

习题五 150

第6章 运输问题及其他 152

6.1 运输问题的数学模型 152

6.1.1 问题的提出 152

6.1.2 运输问题的特殊性 153

6.2 矩阵A的性质 154

6.3 运输问题的求解过程 155

6.3.1 求初始可行解的西北角法 155

6.3.2 最小元素法 157

6.3.3 图上作业法 158

6.4 ci-zi的计算，进入基的确定 159

6.5 退出基的确定 160

6.6 举例 162

6.7 任务安排问题 168

6.7.1 任务安排与运输问题 168

6.7.2 求解举例 168

6.8 任务安排的匈牙利算法 171

6.8.1 代价矩阵 171

6.8.2 科涅格(Kōnig)定理 172

6.8.3 标志数法 173

6.8.4 匈牙利算法 176

6.8.5 匹配算法 179

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

6.10 一般的任务安排问题 182

6.11 运输网络 185

6.11.1 网络流 185

6.11.2 割切 186

6.11.3 福德-福克逊(Ford-Fulkerson)定理 188

6.11.4 标号法 189

6.11.5 埃德蒙斯-卡普(Edmonds-Karp)修正算法 191

6.11.6 狄尼(Dinic)算法 192

习题六 194

第7章 哈奇扬(Хачиян)算法与卡玛卡(Karmarkar)算法 196

7.1 克里(Klee)与明特(Minty)举例 196

7.2.2 哈奇扬算法步骤 198

7.2 哈奇扬算法 198

7.2.1 问题的转化 198

7.2.3 算法的正确性证明的准备 202

7.2.4 定理的证明 205

7.2.5 严格不等式组 208

7.2.6 复杂性分析 210

7.3 卡玛卡算法与卡玛卡典型问题 212

7.3.1 卡玛卡标准型 212

7.3.2 化为标准型的方法之一 212

7.3.3 化为标准型的方法之二 216

7.3.4 T0变换 218

7.3.5 卡玛卡算法步骤 219

7.3.6 卡玛卡算法的若干基本概念 226

7.3.7 Tk变换的若干性质 228

7.3.8 势函数及卡玛卡算法复杂性 233

习题七 239

第8章 多目标规划 241

8.1 问题的提出 241

8.2 多目标规划的几何解释 244

8.3 多目标规划的单纯形表格 249

8.4 多目标规划的目标序列化方法 253

8.5 多目标规划的灵敏度分析 258

8.6 应用举例 269

习题八 272

第9章 整数规划问题的DFS搜索法与分支定界法 277

9.1 问题的提出 277

9.2 整数规划的几何意义 281

9.3 可用线性规划求解的整数规划问题 283

9.4 0-1规划和DFS搜索法 284

9.4.1 穷举法 284

9.4.2 DFS搜索法 285

9.5 整数规划的DFS搜索法 288

9.5.1 搜索策略 288

9.5.2 举例 291

9.6 替代约束 293

9.6.1 吉阿福里昂(Geoffrion)替代约束 293

9.6.2 举例 295

9.7 分支定界法介绍 301

9.7.1 对称型流动推销员问题 301

9.7.2 非对称型流动推销员问题 302

9.7.3 最佳匹配问题 305

9.8 整数规划问题的分支定界解法 306

9.9 分支定界法在解混合规划上的应用 311

9.10 估界方法 315

习题九 321

第10章 整数规划的割平面法 323

10.1 割平面 323

10.1.1 郭莫莱(Gomory)割平面方程 323

10.1.2 例 324

10.2 割平面的选择 329

10.3 马丁(Martin)割平面法 331

10.4 全整数割平面法 336

10.4.1 全整数单纯形表格 336

10.4.2 举例 338

10.4.3 确定λ的策略 341

10.5 混合规划的割平面法 344

习题十 346

第11章 奔德斯(Benders)分解算法与群的解法 348

11.1 混合规划的奔德斯分解算法 348

11.1.1 分解算法的原理 348

11.1.2 奔德斯分解算法 349

11.1.3 算法举例 350

11.2 群的解法 360

11.2.1 群的解法原理 360

11.2.2 举例 361

11.3 群的解法和最短路径问题 365

11.3.1 图的构造 365

11.3.2 求最短路径的戴克斯特拉(Dijkstra)算法 368

11.4 背包问题 369

11.5 将整数规划归约为背包问题 371

11.6 背包问题的网络解法 373

11.7 背包问题的分支定界解法 374

11.8 流动推销员问题的近似解法 380

11.8.1 最近插入法 380

11.8.2 最小增量法 381

11.8.3 回路改进法 385

习题十一 387

第12章 动态规划算法 388

12.1 最短路径问题 388

12.1.1 穷举法 388

12.1.2 改进的算法 389

12.1.3 复杂性分析 390

12.2.2 最佳原理的应用举例 391

12.2.1 最佳原理 391

12.2 最佳原理 391

12.3 流动推销员问题 394

12.3.1 动态规划解法 394

12.3.2 复杂性分析 397

12.4 任意两点间的最短距离 399

12.4.1 距离矩阵算法 399

12.4.2 动态规划算法 399

12.5 同顺序流水作业的任务安排 401

12.6 整数规划的动态规划解法 403

12.6.1 多段判决公式 403

12.6.2 举例 404

12.7 背包问题的动态规划解法 408

习题十二 412

参考文献 413