运筹学导论PDF电子书下载

第1章 绪论 1

1.1 运筹学的起源 1

1.2 运筹学的本质 2

1.3 分析和运筹的兴起 2

1.4 运筹的影响 4

1.5 算法和运筹课件 5

参考文献 7

习题 7

第2章 运筹学建模方法概述 8

2.1 确定问题并收集数据 8

2.2 构建数学模型 10

2.3 从模型中推演出解决方案 12

2.4 模型测试 13

2.5 模型应用 14

2.6 实施 15

2.7 结论 16

参考文献 16

习题 17

第3章 线性规划导论 20

3.1 原形示例 21

3.1.1 作为线性规划问题建模 22

3.1.2 图解法 22

3.1.3 结论 24

3.1.4 用运筹学课件继续学习过程 24

3.2 线性规划模型 25

3.2.1 模型的标准形式 26

3.2.2 其他形式 26

3.2.3 模型的解相关术语 27

3.3 线性规划的假设 29

3.3.1 比例性 29

3.3.2 可加性 31

3.3.3 可分割性 32

3.3.4 确定性 32

3.3.5 前景假设 33

3.4 附加示例 33

3.4.1 放射治疗的设计 34

3.4.2 区域规划 36

3.4.3 控制空气污染 38

3.4.4 回收固体废弃物 41

3.4.5 人员安排 44

3.4.6 通过配送网络来配送货物 46

3.5 用电子表格建立求解线性规划模型 47

3.5.1 在电子表格上建立模型 47

3.5.2 用Solver求解模型 50

3.5.3 用ASPE的Solver求解模型 54

3.6 构建大型线性规划模型 55

3.6.1 建模语言 56

3.6.2 一个有巨大模型的问题实例 57

3.6.3 导出模型的结构 57

3.6.4 用MPL建模 58

3.6.5 LINGO建模语言 61

3.7 结论 62

参考文献 62

习题 63

第4章 求解线性规划问题：单纯形法 79

4.1 单纯形法的本质 79

4.1.1 示例求解 80

4.1.2 关键求解原理 81

4.2 单纯形法的构建 82

4.3 单纯形法的代数运算 85

4.3.1 初始化 85

4.3.2 最优性检验 86

4.3.3 确定移动方向（迭代步骤1） 86

4.3.4 确定停止处（迭代步骤2） 87

4.3.5 求新的BF解（迭代步骤3） 87

4.3.6 新BF解的最优性检验 88

4.3.7 第二次迭代和求得最优解 89

4.4 单纯形法的表格形式 90

4.4.1 单纯形法总结（以迭代1为例） 90

4.4.2 最小比检验 91

4.4.3 例题的第二次迭代和最优解 92

4.5 破解单纯形法的纠结 93

4.5.1 进基变量的纠结 93

4.5.2 出基变量的纠结——退化 94

4.5.3 没有出基变量——Z无界 94

4.5.4 多个最优解 95

4.6 适应其他模型形式 96

4.6.1 等式约束 97

4.6.2 负的右端项 100

4.6.3 “≥”形式的约束条件 100

4.6.4 最小化 101

4.6.5 求解放射治疗例子 102

4.6.6 两阶段法 104

4.6.7 无可行解 108

4.6.8 允许为负的变量 109

4.7 优化后分析 110

4.7.1 再优化 111

4.7.2 影子价格 111

4.7.3 灵敏度分析 113

4.7.4 运用Excel产生灵敏度分析信息 114

4.7.5 参数线性规划 115

4.8 计算机实现 116

4.8.1 单纯形法的实施 116

4.8.2 本书特色线性规划软件 117

4.8.3 线性规划问题可用软件选项 118

4.9 求解线性规划问题的内点法 118

4.9.1 关键求解原理 118

4.9.2 与单纯形法的比较 120

4.9.3 优化后分析中单纯形法和内点算法的结合 120

4.10 结论 121

附录4.1 LINDO和LINGO的使用介绍 121

参考文献 124

习题 125

第5章 单纯形法 140

5.1 单纯形法基础 140

5.1.1 术语 140

5.1.2 相邻CPF解 142

5.1.3 CPF解的性质 143

5.1.4 扩展形式问题的延伸 145

5.2 单纯形法的矩阵形式 148

5.2.1 求一个基本可行解 149

5.2.2 当前方程组的矩阵形式 151

5.2.3 单纯形法矩阵形式的小结 153

5.2.4 最终的评述 155

5.3 基础的洞悉 155

5.3.1 使适用于其他模型形式 157

5.3.2 应用 157

5.4 改进单纯形法 158

5.5 结论 160

参考文献 161

习题 161

第6章 对偶理论 171

6.1 对偶理论的实质 171

6.1.1 对偶问题的起源 173

6.1.2 原问题——对偶问题关系总结 175

6.1.3 应用 177

6.2 对偶的经济解释 177

6.2.1 对偶问题的解释 178

6.2.2 单纯形法的解释 179

6.3 原问题与对偶问题的关系 180

6.3.1 互补基本解 180

6.3.2 互补的基本解之间的关系 182

6.4 改造适用于其他原问题形式 184

6.4.1 用SOB方法决定对偶问题约束形式 185

6.5 对偶理论在灵敏度分析中的作用 187

6.5.1 非基变量系数的改变 187

6.5.2 问题中引入新变量 188

6.5.3 其他应用 189

6.6 结论 189

参考文献 189

习题 189

第7章 不确定条件下的线性规划 196

7.1 灵敏度分析的本质 196

7.2 灵敏度分析的应用 202

7.3 通过电子表格进行灵敏度分析 216

7.3.1 检验模型单个参数变化 217

7.3.2 运用参数分析报告进行系统性灵敏度分析 219

7.3.3 检验模型双向变化 221

7.3.4 利用双向参数分析报告（ASPE）分析上述问题 222

7.3.5 利用灵敏度报告进行灵敏度分析 224

7.3.6 其他类型敏感度分析 228

7.4 鲁棒优化 229

7.4.1 具有独立参数的鲁棒优化法 229

7.4.2 示例 230

7.4.3 拓展应用 231

7.5 机会约束 231

7.5.1 机会约束的形式 232

7.5.2 示例 232

7.5.3 硬约束的处理 233

7.5.4 应用拓展 234

7.6 带补偿的随机规划 234

7.6.1 示例 234

7.6.2 一些典型应用 236

7.7 小结 237

参考文献 238

习题 238

第8章 线性规划的其他算法 254

8.1 对偶单纯形法 254

8.1.1 对偶单纯形法的总结 255

8.1.2 一个例子 255

8.2 参数线性规划 257

8.2.1 参数cj的系统改变 257

8.2.2 参数cj系统变化时参数线性规划过程小结 259

8.2.3 参数bj的系统变化 259

8.2.4 参数bj系统变化时参数线性规划过程小结 260

8.3 上界法 261

8.3.1 一个例子 262

8.4 内点算法 263

8.4.1 概念1和概念2梯度的相关性 264

8.4.2 使用投影梯度以实现概念1和概念2 265

8.4.3 实现概念3的中心化方案 266

8.4.4 本算法的总结与说明 267

8.4.5 内点算法总结 269

8.5 结论 272

参考文献 272

习题 273

第9章 运输与指派问题 279

9.1 运输问题 279

9.1.1 原型范例 279

9.1.2 运输问题模型 282

9.1.3 用Excel建立和求解运输问题 284

9.1.4 一个关于虚销地的例子 286

9.1.5 一个关于虚产地的例子 288

9.1.6 运输问题小结 290

9.2 用于运输问题的单纯形法 290

9.2.1 运输单纯形法的提出 290

9.2.2 初始化 292

9.2.3 最优性检验 297

9.2.4 一次迭代过程 298

9.2.5 运输单纯形法小结 300

9.2.6 本例的特征 302

9.3 指派问题 302

9.3.1 原型范例 303

9.3.2 指派问题模型 303

9.3.3 指派问题的求解步骤 305

9.4 求解指派问题的专用算法 309

9.4.1 等价成本表的作用 309

9.4.2 生成额外零元素 310

9.4.3 匈牙利算法小结 312

9.5 结论 312

习题 312

第10章 网络优化模型 325

10.1 原型范例 325

10.2 网络术语 326

10.3 最短路径问题 328

10.3.1 最短路径问题的算法 329

10.3.2 算法在Seervada公园最短路径问题中的应用 329

10.3.3 用Excel电子表格描述并求解最短路径问题 330

10.3.4 其他应用 332

10.4 最小支撑树问题 332

10.4.1 应用举例 333

10.4.2 算法 333

10.4.3 最小支撑树问题的算法 334

10.4.4 算法在Seervada公园最小支撑树问题上的应用 334

10.5 最大流问题 336

10.5.1 应用举例 337

10.5.2 算法 337

10.5.3 最大流问题的增广链算法 338

10.5.4 应用算法求解Seervada公园最大流问题 338

10.5.5 寻找增广链 340

10.5.6 用Excel描述和求解最大流问题 341

10.6 最小费用流问题 342

10.6.1 一些应用 343

10.6.2 建立模型 344

10.6.3 例子 345

10.6.4 用Excel描述和求解最小费用流问题 345

10.6.5 特殊案例 346

10.6.6 小结 348

10.7 网络单纯形法 348

10.7.1 引入上界法 348

10.7.2 基可行解和可行生成树的一致性 349

10.7.3 选择入基变量 350

10.7.4 寻找出基变量和下一个基可行解 351

10.7.5 本例的结尾 352

10.8 项目的时间-费用平衡优化网络模型 354

10.8.1 一个原型实例——Reliable建筑公司问题 355

10.8.2 项目网络图 356

10.8.3 关键路径 357

10.8.4 各项活动的时间-费用平衡 358

10.8.5 哪些活动应该赶工 359

10.8.6 用线性规划制定赶工决策 360

10.9 结论 363

参考文献 363

习题 364

第11章 动态规划 376

11.1 动态规划的范例 376

11.1.1 例1驿站马车问题 376

11.1.2 问题的求解 377

11.2 动态规划问题的特性 379

11.3 确定性动态规划 381

11.3.1 例2医疗队分配问题 382

11.3.2 一种常见的问题范例——工作分配问题 386

11.3.3 例3向科研小组分配科学家 387

11.3.4 例4车间雇佣问题 389

11.4 随机性动态规划 394

11.4.1 例5确定次品限额 394

11.4.2 例6在拉斯维加斯赢钱 396

11.5 结论 398

部分参考文献 398

习题 398

第12章 整数规划 405

12.1 范例 405

12.1.1 二值整数规划模型 406

12.1.2 用于求解此类模型的软件 407

12.2 整数规划的应用 408

12.2.1 投资分析 408

12.2.2 选址 409

12.2.3 设计生产和销售网络 409

12.2.4 发送运输 410

12.2.5 安排相互联系的活动 410

12.2.6 航空应用 411

12.3 0-1变量在模型构建中的创新应用 412

12.3.1 “或”约束 412

12.3.2 保留N个约束条件中的K个 413

12.3.3 有N个可能取值的函数 414

12.3.4 固定支出问题 414

12.3.5 一般整数变量的二值表示 416

12.4 一些建模举例 416

12.4.1 例1当决策变量是连续变量时的选择 417

12.4.2 例2违反比例性 419

12.4.3 例3覆盖所有特征 421

12.5 求解整数规划问题的若干展望 423

12.6 分支定界法及其在求解0-1整数规划中的应用 426

12.6.1 分支 427

12.6.2 定界 428

12.6.3 剪枝 428

12.6.4 0-1整数规划问题的分支定界算法总结 429

12.6.5 示例 430

12.6.6 分支定界法的其他方案 433

12.7 用于混合整数规划的分支定界算法 435

12.7.1 混合整数规划的分支定界算法总结 437

12.8 解0-1整数规划的分支——切割法 441

12.8.1 背景 441

12.8.2 对纯0-1整数规划问题的自动预处理 441

12.8.3 生成纯0-1整数规划问题的割平面 444

12.9 同约束规划的结合 445

12.9.1 约束规划的原理 446

12.9.2 约束规划的潜能 447

12.9.3 所有变量取不同值约束 447

12.9.4 元素约束 448

12.9.5 当前的研究 449

12.10 结论 449

参考文献 450

习题 450

第13章 非线性规划 465

13.1 应用实例 465

13.1.1 具有价格弹性的产品组合问题 465

13.1.2 运输成本存在总量折扣时的运输问题 466

13.1.3 存在风险的证券投资组合选择 467

13.2 非线性规划问题的图解说明 468

13.3 非线性规划问题的类型 472

13.3.1 无约束最优化 472

13.3.2 线性约束优化 473

13.3.3 二次规划 473

13.3.4 凸规划 473

13.3.5 可分规划 474

13.3.6 非凸规划 474

13.3.7 几何规划 474

13.3.8 分式规划 475

13.3.9 互补问题 475

13.4 单变量无约束优化 476

13.4.1 二分法 476

13.4.2 二分法概述 477

13.4.3 牛顿法 478

13.4.4 牛顿法概述 479

13.5 多变量无约束优化 480

13.5.1 梯度搜索法 480

13.5.2 梯度搜索法概述 482

13.5.3 牛顿法 484

13.6 约束优化的库恩-塔克（KKT）条件 484

13.7 二次规划 488

13.7.1 二次规划的库恩-塔克条件 489

13.7.2 改进单纯形法 490

13.7.3 部分软件选项 492

13.8 可分规划 493

13.8.1 线性规划问题重写 494

13.8.2 展开 497

13.9 凸规划 497

13.9.1 逐次线性逼近算法（弗兰克-沃尔夫算法） 498

13.9.2 弗兰克-沃尔夫算法概述 499

13.9.3 一些其他算法 501

13.9.4 顺序无约束极小化技术（罚函数法） 502

13.9.5 罚函数法概述 502

13.9.6 凸规划的软件部分选项 504

13.10 非凸规划（带电子表格） 504

13.10.1 求解非凸规划问题所面临的挑战 504

13.10.2 利用求解程序找出局部最优解 505

13.10.3 寻找局部最优解的更系统方法 507

13.10.4 进化求解程序 507

13.11 结论 508

参考文献 508

习题 509

第14章 启发式算法 529

14.1 通用启发式算法的性质 529

14.1.1 示例：具有多个局部最优解的非线性规划问题 529

14.1.2 示例：旅行商问题 531

14.1.3 子游逆转算法 533

14.2 禁忌搜索 534

14.2.1 基本概念 534

14.2.2 基本禁忌搜索算法概述 535

14.2.3 有约束条件最小生成树问题 535

14.2.4 旅行商问题示例 539

14.3 模拟退火 542

14.3.1 基本概念 542

14.3.2 基本模拟退火算法概要 544

14.3.3 旅行商问题示例 544

14.3.4 非线性规划示例 547

14.4 遗传算法 550

14.4.1 基本概念 550

14.4.2 基本遗传算法概述 551

14.4.3 非线性规划示例的完整版本 552

14.4.4 旅行商问题示例 554

14.4.5 子代的生成程序 557

14.5 总结 558

参考文献 559

习题 559

第15章 博弈论 565

15.1 两人零和游戏制定 565

15.2 简单对策求解——典型范例 566

15.2.1 两人零和游戏模型 567

15.2.2 示例变形1 567

15.2.3 示例变形2 568

15.2.4 示例变形3 570

15.3 混合策略游戏 571

15.4 图示求解法 572

15.5 线性规划求解 574

15.5.1 线性规划模型 575

15.5.2 政治竞选问题变形3的应用 576

15.6 扩充 577

15.7 结论 578

参考文献 578

习题 578

第16章 决策理论 585

16.1 原型案例 585

16.2 不进行试验的决策 586

16.2.1 此框架下原型实例的建模 587

16.2.2 最大最小收益准则 587

16.2.3 最大似然值准则 588

16.2.4 贝时斯决策准则 589

16.2.5 贝叶斯决策的灵敏性分析 589

16.3 进行试验时的决策制定 590

16.3.1 继续原型实例 590

16.3.2 后验概率 591

16.3.3 试验的价值 593

16.4 决策树 595

16.4.1 建立决策树 595

16.4.2 进行分析 597

16.5 使用电子表格对决策树进行灵敏性分析 598

16.5.1 使用ASPE建立Goferbroke公司第一问题的决策树 599

16.5.2 Goferbroke公司完整问题的决策树 600

16.5.3 用电子数据表进行灵敏性分析 600

16.5.4 使用数据表进行系统的灵敏性分析图 602

16.6 效用理论 603

16.6.1 现金的效用函数 604

16.6.2 等价抽奖法 605

16.6.3 对Goferbroke公司完整问题应用效用理论 605

16.6.4 评估U（M）的另一个方法 607

16.6.5 使用带有效用的决策树分析Goferbroke公司问题 607

16.7 决策分析的实际应用 608

16.8 结论 609

参考文献 609

习题 610

第17章 排队论 623

17.1 典型案例 623

17.2 排队模型的基本组成 623

17.3 排队系统实例 627

17.4 指数分布的作用 629

17.5 生灭过程 633

17.6 基于生灭过程的排队模型 637

17.7 非指数分布的排队模型 646

17.8 有优先规则的排队模型 651

17.9 排队网络 655

17.10 排队论的应用 658

17.11 本章小结 660

参考文献 661

习题 662

第18章 库存理论 681

18.1 示例 682

18.1.1 示例1：电视机扬声器生产 682

18.1.2 示例2：自行车批发销售 682

18.2 库存模型组成要素 683

18.3 确定性连续监控模型 685

18.3.1 基本EOQ模型 685

18.3.2 计划内断货的EOQ模型 687

18.3.3 含数量折扣的EOQ模型 689

18.3.4 一些实用的Excel模板 690

18.3.5 关于EOQ模型的探讨 691

18.3.6 产品需求的不同类型 691

18.3.7 适时制（JIT）库存管理的作用 692

18.4 确定性定期监控模型 692

18.4.1 示例 693

18.4.2 算法 694

18.4.3 运用算法求解飞机生产问题 695

18.4.4 最优生产计划 696

18.5 供应链管理的确定性多级库存模型 696

18.5.1 二级库存系统模型 697

18.5.2 多级库存系统模型 701

18.6 随机连续监控库存模型 709

18.6.1 模型假设 709

18.6.2 选择订货量Q 710

18.6.3 选择再订货点R 710

18.6.4 示例 712

18.7 易逝品单周期随机模型 712

18.7.1 易逝品的类型 713

18.7.2 示例 713

18.7.3 易逝品单周期随机模型假设 715

18.7.4 不含初始库存（I=0）和准备成本（K=0）的模型分析 715

18.7.5 初始库存I＞0、准备成本K=0时的模型分析 718

18.7.6 准备成本K＞0时的模型分析 718

18.7.7 需求呈指数分布时的最优策略近似解 720

18.8 收益管理 721

18.8.1 基于容量控制的折扣票价模型 722

18.8.2 基于容量控制的折扣票价模型应用示例 723

18.8.3 超售模型 724

18.8.4 超售模型应用示例 726

18.8.5 其他模型 727

18.9 小结 727

参考文献 728

习题 729

第19章 马尔可夫决策过程 746

19.1 典型范例 746

19.2 马尔可夫决策过程模型 748

19.3 线性规划与最优策略 751

19.4 结语 754

参考文献 755

习题 755

第20章 仿真 759

20.1 仿真本质 759

20.1.1 仿真在运筹学研究中的作用 759

20.1.2 离散事件系统仿真与连续系统仿真 760

20.1.3 游戏规则 761

20.1.4 时间步长法步骤简介 765

20.1.5 事件步长法步骤简介 766

20.1.6 更多示例请参阅运筹学课件 768

20.2 仿真应用的部分常见类型 768

20.2.1 排队系统的设计与运行 768

20.2.2 库存管理系统 769

20.2.3 估算按时完成项目的概率 769

20.2.4 制造系统的设计与运行 769

20.2.5 配送系统的设计与运行 770

20.2.6 金融风险分析 770

20.2.7 医保应用 770

20.2.8 其他服务行业的应用 771

20.2.9 军事应用 771

20.2.10 新应用 771

20.3 随机数生成 771

20.3.1 随机数特征 772

20.3.2 随机数生成同余法 772

20.4 概率分布随机观测值的生成 774

20.4.1 简单离散分布 774

20.4.2 逆转换法 775

20.4.3 逆转换方法步骤简介 775

20.4.4 指数分布和厄兰分布 776

20.4.5 正态分布和卡方分布 776

20.4.6 舍选法 777

20.5 主要仿真研究概述 777

20.6 用电子数据表实施模拟 780

20.6.1 库存管理示例——报贩弗雷迪问题 781

20.6.2 上述问题的电子数据表模型 781

20.6.3 分析求解程序平台教学版应用 783

20.6.4 用仿真和ASPE求解器进行优化 791

20.7 结论 794

参考文献 795

习题 796