运筹学手册 基础和基本原理PDF电子书下载

卷I 运筹学的基础和哲学原理 3

I-1 运筹学的历史、性质和用途 3

1. 起源 3

2. 运筹科学 6

2.1 科学和科学方法 7

2.2 作为一门科学的运筹学 9

3. 运筹学的实践 11

4. 运筹学的成长，1945～1975 12

4.1 趋势 13

4.2 专业学会 15

4.3 期刊 18

4.4 书籍 19

4.5 教育 22

5. 运筹学的扩展 23

6. 运筹学的将来 24

参考文献 24

I-2 关于系统设计的哲学思考 29

1. 引言 29

2. 系统设计 30

3. “科学方法” 30

4. 社会现实 31

5. 改进 34

6. SD数据的悖论 35

7. 实行 37

8. 回到“科学方法” 38

9. 作为进步来看的“改进” 39

10. 再谈“社会现实”和“实行” 40

11. “社会现实”：个人 41

12. 叙述的中止 45

13. 参考资料：个人的感谢 45

I-3 运筹学研究的进行 47

1. 引言 47

2. 目标的规定 48

3. 方案计划的研制 51

4. 问题的表述 55

4.1 问题尺度的确定 58

4.2 可控制决策变量的确定 60

4.3 不可控制变量的确定 61

4.4 工艺的确定 62

4.5 有效性度量的确定 62

5. 模型的研制 63

5.1 定义关系 64

5.2 经验关系 65

5.3 规范关系 65

6. 计算手段的拟定 66

7. 程序明细表的编制，程序设计和调试 68

8. 数据收集 71

9. 证实 72

9.1 一致性 72

9.2 灵敏性 73

9.3 似然性 73

9.4 工作能力 74

10. 实行 75

参考文献 76

I-4 运筹学专业教育 78

1. 引言 78

2. 运筹学教育的结构 79

2.1 正规教育 80

2.2 半正规教育 82

2.3 非正规教育 83

2.4 在职教育 84

3. 运筹学教育的水平 84

3.1 博士水平 85

3.2 硕士水平 85

3.3 非运筹学专业 86

4. 主题 87

4.1 运筹学专业工作者所需要的数学 88

4.2 其他基础课程 89

4.3 运筹学成分 89

5. 充实队伍 91

参考文献 91

卷II 运筹学的方法论：确定性模型 95

II-1 线性规划 95

1. 引言 95

2. 线性规划应用的范围 96

3. 线性规划解的性质 102

4. 单纯形法 105

4.1 单纯形法的几何解释 109

4.2 退化与循环 112

4.3 有界变量 113

5. 对偶性理论 115

5.1 互补主元理论 119

5.2 对偶性的经济学解释 121

6. 灵敏度分析 123

7. 可分解线性规划 125

8. 结束语 126

参考文献 126

II-2 整数规划和组合学 132

1. 引言 132

1.1 一个实例 133

1.2 整数限制的重要性 133

1.3 应用范围 134

1.4 线性整数规划的数学提法 134

1.5 纯整数规划和混合整数规划 135

2. 整数规划问题举例 135

2.1 背袋(或装载)问题 135

2.2 固定费用问题 137

2.3 和睦探险队问题和组合学的对集问题 138

2.4 有效探险队问题和组合学的覆盖问题 139

2.5 送货问题 140

2.6 多抉择问题 141

2.7 0-1多项式问题 141

2.8 有界变量的整数规划与0-1整数规划的等价性 142

2.9 可分离的非线性函数的分段线性逼近 143

3. 整数规划问题的解法 145

3.1 衍生问题 145

3.2 松弛问题 146

3.3 对偶开拓法：一般框架 148

3.4 将原有与原有-对偶方法纳入对偶性开拓方法框架中 150

3.5 几个具体方法 151

4. 具有特殊结构的整数规划 154

参考文献 156

II-3图论：几种方法及应用 161

1. 引言 161

2. 基本定义 163

3. 连通性 168

3.1 Euler路 168

3.2 Hamilton路 170

3.3 有向图的Hamilton回路 171

3.4 正则图 171

3.5 树与支撑树 172

3.6 最短路和最长路 175

3.7 匹配 175

4. 极端图 176

4.1 有向完全图中有多少个圈？ 176

4.2 平面性与交叉 177

5. 嵌入 181

5.1 平面图及其对偶 182

5.2 四色问题 185

5.3 稳定性(关于染色的) 189

6. 几个基本定理 189

7. 矩阵 190

7.1 矩阵表示 190

7.2 邻接矩阵的一个应用 193

7.3 拟阵 195

8. 两个应用 195

8.1 图的矩阵在商业上的一个应用 195

8.2 利用图构造的模型 196

9. 附录 197

参考文献 197

II-4网络中的流 201

1. 引言 201

2. 最短路 202

2.1 定义 202

2.2 求从某一发点到某一收点的最短链的算法 202

3. 最大流 204

3.1 可扩充链 204

3.2 最大流-最小截集 206

3.3 Edmonds-Karp 的最大流算法 206

4. 原始-对偶算法 207

4.1 最小价格流 207

4.2 最短路步骤 209

4.3 最大流步骤 210

4.4 互补松弛性 211

4.5 不良状态 212

5. 修正的最短路 212

6. 线性规划 214

6.1 基本解与树 214

6.2 相邻顶点 217

6.3 原始单纯形法(SM) 217

6.4 对偶单纯形法(DSM) 219

6.5 基本解 221

7. 应用 222

8. 具有增益的流 224

9. 多终端流和多商品流 225

参考文献 227

II-5 几何规划 230

1. 引言 230

2. 问题的阐述和某些例子 231

2.1 无约束情形 231

2.2 有约束情形 236

2.3 小结 241

3. 基本理论 241

3.1 无约束情形 242

3.2 有约束与无约束情形间的关系 260

3.3 有约束情形 261

参考文献 272

II-6 非线性规划 275

1. 引言 275

2. 最优性条件 277

2.1 一阶Kuhn-Tuc-ker条件 277

2.2 二阶Kuhn-Tuc-ker条件 278

2.3 一阶增广Lagran-ge最优性条件 279

2.4 精确罚最优性条件 280

2.5 一阶梯度投影最优性条件 281

3. 对偶性 281

3.1 弱对偶定理 282

3.2 对偶定理 282

3.3 严格逆对偶定理 282

4. 一维极小化算法 283

4.1 黄金分割法和Fi-bonacci搜索法 283

4.2 黄金分割法和Fi-bonacci搜索法的收敛性 284

4.3 割线法 284

4.4 割线法的收敛性 285

5. 无约束极小化算法 285

5.1 变尺度法 286

5.2 变尺度法的收敛性和收敛阶 286

5.3 共轭方向法 287

5.4 共轭梯度法的收敛性与收敛阶 287

6. 有约束极小化算法 288

6.1 渐近内罚算法 289

6.2 外罚函数法 289

6.3 精确极小化罚函数法 291

6.4 精确平稳点罚函数法(增广Lagrange乘子法) 291

6.5 可行方向法 291

6.6 梯度投影法 292

6.7 非线性约束问题的Newton法 293

参考文献 294

II-7大型规划 299

1. 引言 299

2. 用修正单纯形法(RSM)求解大型线性规划问题 300

2.1 有效的求逆算法 302

2.2 LU分解 303

2.3 “超稀疏性” 303

2.4 倍数价格 304

3. 广义上界 305

3.1 有约束资源分配的能力 306

3.2 多项目时间表问题 308

3.3 生产及分配问题 309

3.4 GUB的推广 310

4. 列生成 311

4.1 材料切割问题 311

4.2 多项目时间表 314

5. Dantzig-Wolfe分解原理 316

5.1 分解算法 316

5.2 经济解释 318

5.3 计算 319

5.4 主规划的实际解释 320

5.5 应用于非线性子系统 320

5.6 Dantzig-Wolfe分解法的现状 321

5.7 用箱形步加速 322

6. 大型非线性规划(NLP) 322

6.1 可分规划 323

6.2 近似规划 324

7. 大型数学规划的未来发展 325

参考文献 327

II-8最佳控制 331

1. 问题的提法 331

2. 必要条件 334

2.1 Pontrygin最大原理 334

2.2 Mayer方程和Weierstrass条件 336

2.3 具有可变端点的最佳控制问题 340

3. 综合 341

3.1 线性时间最佳控制问题 341

3.2 控制区为紧凸多面体的非线性最佳控制问题 342

4. 充分条件 345

4.1 线性时间最佳控制问题 346

4.2 关于状态变量是线性的最佳控制问题 346

4.3 场 347

5. 结束附记 350

参考文献 351

卷III 运筹学的方法论：随机性模型 356

III-1 随机过程 356

1. 引言 356

2. 随机游动 362

3. 简单随机游动 365

4. 循环事件 368

5. Markov链 370

6. 鞅 374

7. 更新过程 376

8. 累积过程 378

9. 分枝过程 380

10. 广义生灭过程 381

11. 时间序列和平稳过程 384

自回归过程 387

滑动平均过程 388

一般的注记 389

参考文献与进一步的读物 389

III-2 排队论 391

1. 引言 391

2. 问题、术语和记号 392

(a)性态问题 393

(b)统计问题 394

(c)运行问题 394

3. 应用领域 395

4. 性态分析 397

4.1 M/M/1排队系统 399

4.2 M/G/1排队系统 401

4.3 GI/M/1排队系统 403

4.4 GI/G/1排队系统 404

4.5 多服务员的排队系统 406

4.6 有限排队系统 407

4.7 其他排队系统 410

5. 统计分析 411

6. 运行分析 415

(1)简单费用模型 416

(2)变化服务率 417

(3)服务员在-离策略 418

(4)设计考虑 419

(5)优先权排队系统 419

7. 理论分析技巧 420

(a)生灭过程 423

(b)补充变量 425

(c)Takács积分-微分方程 426

(d)嵌入Markov链 426

(e)半Markov分析 427

(f)更新论方法 428

(g)组合方法 428

(h)Pollaczek方法 429

(i)扩散近似 429

8. 计算问题 430

9. 重要的发展方向 432

10. 结论 433

参考文献 433

III-3 价值论 444

1. 引言 444

1.1 历史梗概 445

1.2 大要 446

2. 偏好与效用 448

2.1 偏好与无殊 449

2.2 传递性 450

2.3 效用 452

3. 期望效用理论 454

3.1 线性效用函数 454

3.2 线性效用的公理 457

3.3 关于财富效用 459

4. 多元价值理论 461

4.1 独立条件 462

4.2 可加性效用 463

4.3 可加性与其他线性效用 465

5. 主观概率与期望效用 466

5.1 公理与量度 467

6. 结尾的话 469

参考文献 470

III-4 决策分析 474

1. 引言 474

1.1 什么是决策分析？ 474

1.2 决策分析的作用 475

1.3 决策分析所致力的问题 476

1.4 决策分析的历史 477

1.5 决策分析的应用 479

2. 决策分析的公理系统 480

3. 决策分析的方法论 482

3.1 分析一般的决策问题 483

3.2 选取决策策略 484

3.3 确定性当量 486

4. 判断不确定性的定量化 487

4.1 基于物理现象的判断概率 487

4.2 基于数据和模型的判断概率 487

4.3 确定离散事件的概率 488

4.4 概率分布的判断评定 489

4.5 判断评定与样本信息的结合 490

4.6 评定判断概率的实际方法 490

5. 评定效用 491

5.1 实际评定的准备 492

5.2 确定有关的定性特征 492

5.3 确定定量限制 494

5.4 选取效用函数 495

5.5 检验相容性 496

6. 决策分析中的进一步结果 497

6.1 多属性问题 497

6.2 时时偏好 498

6.3 集体决策问题 498

7. 未来 499

参考文献 500

III-5 对策论和对策模拟 505

历史介绍 505

1. 广义型和正规型 505

2. 零和二人对策 508

2.1 简介 508

2.2 矩阵对策 509

2.3 最优策略的计算 511

2.4 约束对策 513

2.5 无限对策 515

2.6 多阶段对策 518

2.7 微分对策 521

3. 双人非零和对策 525

3.1 引言 525

3.2 非合作对策 525

3.3 合作对策 527

4. n人对策 528

4.1 定义 528

4.2 控制，核心，稳定集 531

4.3 Shapley值 532

4.4 交易集 533

4.5 无附加支付的对策 536

4.6 局中人为连续统的对策 537

5. 对策模拟 538

5.1 教学与训练 538

5.2 运用对策模拟 539

5.3 实验 539

5.4 娱乐 539

5.5 治疗 540

参考文献 540

III-6 搜索论--寻找物体的原理 542

引言 542

1. 基本概念 544

1.1 区域的目力搜索 544

1.2 虚警，非均匀扫描 546

2. 搜索运动 548

2.1 目力搜索 548

2.2 不同探测设备的横距概率 551

2.3 搜索宽度及其度量 553

3. 区域搜索 556

3.1 平行搜扫 556

3.2 随机分布搜扫 560

3.3 杂例 561

4. 搜索力的最优分配 562

4.1 目标位置信息的影响 562

4.2 公式的应用 566

5. 目标运动 575

5.1 目标位置和运动未知的情况 576

5.2 往返式封锁巡逻 581

5.3 滞后搜索 583

6. 箱盒搜索--离散位置的搜索 587

6.1 区域搜索与箱盒搜索的相拟性 588

6.2 探测的差错 590

7. 对抗搜索--主动规避目标 596

8. 应用 599

参考文献 600

III-7 模拟理论 602

1. 引言 602

2. 模拟研究的步骤 602

3. 模型的阐述 604

3.1 模型元素 604

3.2 例：种群增殖模型 604

3.3 例：简化的排序模型 604

4. 随机数的产生 605

4.1 均匀随机数 605

4.2 变换法 606

4.3 合成 608

4.4 舍取法 609

5. 模拟设计与降低方差 611

5.1 直接抽样 612

5.2 对偶变数 613

5.3 分层 614

5.4 重要性抽样 615

5.5 控制变量与回归 616

5.6 排队网络中控制和循环事件法 617

6. 数据的统计分析 617

6.1 独立实现 618

6.2 比较 620

6.3 建立联系与相依性 620

6.4 动态过程 621

参考文献 622

III-8 模拟计算 625

1. 系统模拟 625

2. 系统模型 626

3. 一个机器加工车间的例子 628

4. 系统的影象 629

5. 模拟过程 631

6. 统计数据的收集 632

7. 表处理法 632

8. 模拟语言 633

9. 模拟控制方法 634

10. GPSS的结构 635

11. 用GPSS描述机加工车间的例子 637

12. SIMSCRIPT的结构 638

13. 用SIMSCRIPT描述机器加工车间的例子 639

14. 语言的比较 642

参考文献 643

III-9 动态规划 649

1. 引言 649

2. 序贯决策过程的范例 650

3. 动态规划的一些论题 653

4. 例 655

5. 状态 657

6. 不确定性 659

7. 序贯决策过程的语言 660

8. Markov决策模型 664

9. 要点重述 670

参考文献 670