《运筹学常用算法手册》求取 ⇩

定义与符号1

0.(引言)矩阵代数和有关知识(摘要)3

0.1定义3

0.2 基本运算4

第一章线性规划7

1.1 一般方法7

1.1.1 原始单纯形法7

1.1.2 二段法10

1.1.3 无明显单位矩阵的原始单纯形法14

1.1.4 对偶单纯形法17

1.1.5 灵敏度分析和参数规划(S.A.法和 P.P.法)21

1.1.5.1 具有预期变更的 S.A.法和 P.P.法21

1.1.5.2 具有非预期变更的 S.A.法和 P.P.法25

1.1.5.2.1 约束向量的变更序列25

1.1.5.2.2 目标函数系数的变更序列27

1.2 最短路线法29

1.2.1 运输问题29

1.2.1.1 西北角(Northwest-Corner)法则30

1.2.1.2 最小行法34

1.2.1.3 最小列法37

1.2.1.4 最小矩阵法41

1.2.1.5 双重优先法45

1.2.1.6 VOGEL 近似法(VAM法)51

1.2.1.7 频率法56

1.2.1.8 步进法57

1.2.2 匈牙利(Hungarian)法(Kuhn法)60

1.2.3 分解原理(Dantzig 法；Wolfe 法)65

1.2.4 FLOOD 法74

1.3.1 对偶问题75

1.3 定理和规则75

1.3.2 对偶定理77

1.3.3 “字典式”选择规则77

第二章整数规划79

2.1 割平面法79

2.1.1 GOMORY-Ⅰ全整数法79

2.1.2 GOMORY-Ⅱ全整数法82

2.1.3 GOMORY-Ⅲ混合整数法85

2.1.4 带强化割线的 GOMORY-Ⅲ混合整数法87

2.1.5 原始割平面法(Young法；G1over法；Ben-Israel法；Charnes法)89

2.2 分支界限法92

2.2.1 LAND 和 DOIG 法92

2.2.2 DAKIN 法98

2.2.3 DRIEBEEK 法102

2.2.4 辅助算法(Balas法)108

2.3 原始-对偶法112

2.3.1 混合整数问题的分割程序(Benders法)112

第三章图论120

3.0.1 定义120

3.0.2 图中秩的确定122

3.0.3 图的路数123

3.0.4 图的强连通部分的确定125

3.1 图的最短路径127

3.1.1 DIJKSTRA 法127

3.1.2 DANTZIG 法130

3.1.3 FORD 法Ⅰ(最短路径法)133

3.1.4 FORO 法Ⅱ(最长路径法)135

3.1.5 三重法137

3.1.6 HASSE 法140

3.1.7 串联法141

3.1.8 短距离法142

3.1.9 EASTMAN 法147

3.2 网络流150

3.2.1 FORD 和 FULKERSON 法150

3.2.2 BUSACKER 和 GOWEN 法155

3.2.3 KLEIN 法158

3.2.4 Kilter 法的推论(Ford法；Fulkerson法)162

3.3 图的最短生成子树170

3.3.1 KRUSKAL 法170

3.3.2 SOLLIN 法173

3.3.3 WOOLSEY 法176

3.3.4 BERGE 法178

3.4 Gozinto 图180

3.4.1 VAZSONYI 法180

3.4.2 TISCHER 法182

3.4.3 FLOYD 法183

3.4.4 Gozinto 列表法186

第四章计划网络188

4.0.1 关键路线法(CPM)188

4.0.2 关键路线法(CPM)项目的加速191

4.0.3 计划评审技术(PERT)195

4.0.4 Metra 位能法(MPM)197

4.0.5 作图评审技术(GERT)200

第五章对策论207

5.1 非矩阵对策207

5.1.1 正规形式207

5.1.2 谈判问题的 NASH 解212

5.1.3 扩大形式213

5.2.1 确定二人零和对策的纯策略对的方法220

5.2 矩阵对策220

5.2.2 应用单纯形法求解二人零和对策222

5.2.3 二人零和对策的近似法(“学习法”；Gale法；Brown法)224

5.2.4 解双矩阵对策的 LEMKE-HOWSON 法228

5.3 不确定情况下的决策(同自然界对策)232

5.3.1 WALD 解233

5.3.2 HURWICZ 解233

5.3.3 SAVAGE 和 NIEHANS 解234

5.3.4 BAYES 解235

5.3.6 HODGES 和 LEHMANN 解236

5.3.5 LAPLACE 解236

第六章动态规划238

6.0.1 n 阶段模型238

6.0.2 无限阶段模型(策略迭代程序)243

第七章排队模型247

7.0.1 单通道、单阶段模型249

7.0.2 单通道、r 阶段模型250

7.0.3 k 通道、单阶段模型251

8.1.1 KUHN 和 TUCKER 定理254

8.1 定理和方法254

第八章非线性规划254

8.1.2 拉格朗日方法255

8.1.3 线性约束下，非线性可分目标函数的最优化方法257

8.2 一般方法260

8.2.1 WOLFE 法(简捷形式)260

8.2.2 FRANK 和 WOLFE 法264

8.2.3 BEALE 法269

8.2.4 求解线性互补问题的算法(Lemke法)272

8.2.5 梯度投影法(Rosen法)275

9.0.2 平方取中法(J.V.Neumann法)281

第九章随机数的产生(模拟)281

9.0.1 AWF 骰子(赌博)法281

9.0.3 混合同余法283

9.0.4 乘同余法283

第十章替代模型285

10.1 关于逐步增加维护费的替代模型285

10.1.1 不考虑利率的模型285

10.1.2 考虑利率的模型286

10.2.1 不考虑利率的模型288

10.2 对于意外事故的替代模型288

10.2.2 考虑利率的模型290

第十一章库存模型292

11.0.1 经典的库存模型(Andler模型)292

11.0.2 用于供不应求的带亏损的库存模型293

11.0.3 具有交付期限的库存模型294

11.0.4 具有贮存损失的库存模型295

11.0.5 折扣库存模型(不同差价)296

11.0.6 关于运输能力的库存模型298

12.0.1 用于两台机器的 JOHNSON 算法301

第十二章序列模型301

12.0.2 用于三台机器的 JOHNSON 算法(特殊情况)303

12.0.3 序列问题的试探解法304

第十三章厂址模型308

13.1 精确方法308

13.1.1 在运输网路Ⅰ中的最优厂址问题308

13.1.2 在运输网路Ⅱ中的最优厂址问题309

13.1.3 位于直线上的最优厂址问题311

13.1.4 关于矩形运输的最优厂址问题312

13.2.1 重心法314

13.2 试探法314

13.2.2 用向量和求解316

13.2.3 迭代法320

附录323

表1qk＝(1+i)k323

表2 q-k＝(1+i)-k323

表3 e-k324

表4 具有等分布的随机数324

表5 标准正态分布函数下的面积326

参考书目327