《单目标、多目标与整数规划》求取 ⇩

第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-1a)=(CB/B-1)a50

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 aij改变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

第八章 多目标规划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