第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