运筹学 应用范例与解法 第4版PDF电子书下载

第1章 建模理论概述 1

1.1 模型化概述 1

1.1.1 说明性模型或最优化模型 1

1.1.2 目标函数 2

1.1.3 决策变量 2

1.1.4 约束条件 2

1.1.5 完整的最优化模型 3

1.1.6 静态和动态模型 3

1.1.7 线性和非线性模型 3

1.1.8 整数和非整数模型 4

1.1.9 确定性和随机性模型 4

1.2 7步骤建模过程 4

1.3.1 最优化炼油厂的经营 5

1.3 C1TGO石油公司 5

1.3.2 SDM系统 6

1.4 旧金山警察局调度方法 6

1.5 GE Capital公司 8

参考文献 9

第2章 线性代数基础知识 10

2.1 矩阵和向量 10

2.1.1 矩阵 10

2.1.2 向量 11

2.1.3 两个向量的标量积 12

2.1.4 矩阵运算 13

2.1.5 矩阵乘法的性质 17

2.1.6 利用Excel的矩阵乘法 18

2.2 线性方程的矩阵和线性方程组 19

2.3.1 基本行运算 21

2.3 解线性方程组的高斯－约当方法 21

2.3.2 利用高斯－约当方法求解 23

2.3.3 特殊情况：无解或者有无穷多组解 27

2.3.4 高斯－约当方法小结 29

2.3.5 线性方程组的基变量和基本解 29

2.4 线性相关和线性无关 32

2.4.1 矩阵的秩 33

2.4.2 如何判别向量组是否线性无关 35

2.5 逆矩阵 36

2.5.1 没有逆矩阵的矩阵 39

2.5.2 利用高斯－约当方法求m×m矩阵A的逆矩阵 39

2.5.3 利用逆矩阵解线性方程组 39

2.5.4 利用Excel求逆矩阵 40

2.6 行列式 41

2.7.1 矩阵 43

2.7 小结 43

2.7.2 矩阵和线性方程 44

2.7.3 高斯－约当方法 44

2.7.4 线性无关、线性相关和矩阵的秩 45

2.7.5 逆矩阵 46

2.7.6 行列式 46

2.8 复习题 46

参考文献 49

第3章 线性规划 50

3.1 什么是线性规划问题 50

3.1.1 比例性假定和相加性假定 53

3.1.2 可除性假定 54

3.1.3 确定性假定 54

3.1.4 可行域和最优解 54

3.2 两变量线性规划问题的图解法 56

3.2.1 求可行解 57

3.2.2 求最优解 58

3.2.3 绑定和非绑定约束条件 59

3.2.4 凸集、极点和LP 59

3.2.5 最小化问题的图解法 60

3.3 特殊情况 64

3.3.1 可选或多个最优解 64

3.3.2 不可行LP 66

3.3.3 无界LP 67

3.4 饮食问题 69

3.5 工作调度问题 73

3.5.1 制定公平的员工调度方案 75

3.5.2 建模问题 75

3.5.3 现实应用 76

3.6 资本预算问题 77

3.6.1 利用Excel计算NPV 78

3.6.2 XNPV函数 80

3.7 短期财务计划 83

3.8 混合问题 86

3.8.1 建模问题 92

3.8.2 现实应用 92

3.9 生产过程模型 97

3.10 使用线性规划求解多阶段问题：库存模型 104

3.11 多阶段财务模型 110

3.12 多阶段工作调度 115

3.13 小结 118

3.13.1 线性规划的定义 118

3.13.2 线性规划问题的图解法 118

3.14 复习题 119

3.13.3 LP的解：4种情况 119

3.13.4 表述LP 119

参考文献 139

第4章 单纯形算法和目标规划 141

4.1 如何将LP转换成标准形式 141

4.2 单纯形算法概览 144

4.2.1 基变量和非基变量 145

4.2.2 可行解 145

4.3 无界方向 147

4.4 为什么LP有最优bfs 150

4.4.1 相邻基本可行解 151

4.4.2 三维LP的几何图形 152

4.5 单纯形算法 154

4.5.1 把LP转换成标准形式 155

4.5.3 确定换入变量 156

4.5.2 当前基本可行解是最优的吗 156

4.5.4 求新的基本可行解：换入变量中的主元素 157

4.5.5 应用于max问题的单纯形算法小结 162

4.5.6 表示单纯形表 162

4.6 使用单纯形算法求解最小化问题 163

4.6.1 方法1 164

4.6.2 方法2 164

4.7 可选最优解 166

4.8 无界LP 169

4.9 LINDO计算机软件包 173

4.10 矩阵生成器、LINGO和LP的定标 177

4.10.1 LINGO软件包 177

4.10.2 LP的定标 181

4.11 单纯形算法的退化和集中 183

4.12 大M法 187

4.12.1 大M法的描述 189

4.12.2 如何判别不可行LP 192

4.13 两阶段单纯形法 195

4.14 符号无限制变量 201

4.15 求解LP的Karmarkar方法 206

4.16 不存在不确定性时的多属性决策：目标规划 207

4.16.1 优先目标规划 210

4.16.2 使用LINDO或LINGO求解优先目标规划问题 214

4.17 使用Excel Solver求解LP 222

4.17.1 使用Excel Solver求解饮食问题 222

4.17.2 使用Solver求解Sailco示例 225

4.17.3 使用Value of选项 226

4.17.4 Solver和不可行LP 227

4.17.5 So1ver和无界LP 228

4.18 本章小结 229

4.18.1 准备好利用单纯形算法进行求解的LP 229

4.18.2 单纯形算法 229

4.18.3 大M法 230

4.18.4 两阶段法 230

4.18.5 求解最小化问题 231

4.18.6 可选最优解 231

4.18.7 符号无限制变量 231

4.19 复习题 231

附录A LINDO菜单命令和语句 239

A.1 菜单命令 239

A.2 可选的建模语句 242

B.2 LINGO的基础知识 243

B.1 什么是LINOGO 243

附录B LINGO初步 243

附录C LINGO菜单命令和功能 244

C.1 菜单命令 244

C.2 函数 247

参考文献 248

第5章 灵敏度分析：应用方法 250

5.1 灵敏度分析的图形介绍 250

5.1.1 利用图形分析目标函数系数变化时的影响 250

5.1.2 利用图形分析右端项变化对LP最优解的影响 251

5.1.3 影子价格 253

5.1.4 灵敏度分析的重要性 254

5.2 计算机和灵敏度分析 255

5.2.1 目标函数系数范围 258

5.2.3 右端项范围 259

5.2.2 缩减成本和灵敏度分析 259

5.2.4 影子价格和对偶价格 260

5.2.5 影子价格的符号 261

5.2.6 灵敏度分析以及松弛和剩余变量 261

5.2.7 退化和灵敏度分析 262

5.3 影子价格的管理应用 272

5.4 如果当前基不再是最优的，最优z将发生什么情况 275

5.5 本章小结 279

5.5.1 图形灵敏度分析 279

5.5.2 影子价格 279

5.5.3 目标函数系数范围 279

5.5.4 缩减成本 279

5.5.8 作为目标函数系数之函数的最优z值 280

5.5.7 作为约束条件右端项之函数的最优z值 280

5.6 复习题 280

5.5.6 影子价格的符号 280

5.5.5 右端项范围 280

第6章 灵敏度分析和对偶理论 296

6.1 灵敏度分析的图形介绍 296

6.1.1 利用图形分析目标函数系数变化时的影响 296

6.1.2 利用图形分析右端项变化对LP最优解的影响 297

6.1.3 影子价格 299

6.1.4 灵敏度分析的重要性 300

6.2 一些重要的公式 301

6.2.1 根据B-1和原LP表示单纯形表中的约束条件 303

6.2.2 根据原LP确定最优表的第0行 305

6.2.3 简化变量为松弛、剩余或人工变量时的公式（10） 306

6.2.4 根据原表计算最优表的公式小结 306

6.3 灵敏度分析 309

6.3.1 改变非基变量的目标函数系数 310

6.3.2 改变基变量的目标函数系数 312

6.3.3 解释LINDO输出的目标系数范围块 315

6.3.4 改变约束条件的右端项 316

6.3.5 解释LINDO输出的右端项范围块 319

6.3.6 改变非基变量列 319

6.3.7增加新活动 321

6.4 多个参数发生变化时的灵敏度分析：100％规则 324

6.4.1 改变目标函数系数的100％规则 324

6.4.2 改变右端项的100％规则 327

6.5 求LP的对偶 330

6.5.1 求规范max或min问题的对偶 330

6.5.2 求非规范LP的对偶 333

6.6 对偶问题的经济解释 337

6.6.1 解释max问题的对偶 337

6.6.2 解释min问题的对偶 339

6.7 对偶理论及其推论 340

6.7.1 弱对偶性 341

6.7.2 对偶理论 343

6.7.3 当原问题是max问题时，如何根据最优表的第0行判别最优对偶解 346

6.7.4 当原问题是min问题时，如何根据最优表的第0行判别最优对偶解 348

6.8 影子价格 350

6.8.1 影子价格符号的直观解释 352

6.8.2 解释LINDO输出的对偶价格列 355

6.8.3 退化和灵敏度分析 356

6.9 对偶性和灵敏度分析 360

6.10 互补松弛性 362

6.11 对偶单纯形法 366

6.11.1 max问题的对偶单纯形法 366

6.11.2 把一个约束条件添加到LP中以后，求新的最优解 367

6.11.3 改变右端项以后，求新的最优解 369

6.11.4 求解规范min问题 370

6.12 数据开发分析 372

6.12.1 使用LINGO运行DEA 375

6.12.2 对偶价格和DEA 376

6.13 本章小结 379

6.13.1 图形灵敏度分析 379

6.13.2 影子价格（1） 380

6.13.3 符号表示 380

6.13.4 如何根据初始LP计算最优表 380

6.13.5 灵敏度分析 380

6.13.6 目标函数系数范围 381

6.13.7 缩减成本 381

6.13.8 右端项范围 381

6.13.9 求LP的对偶问题 381

6.13.12 影子价格（2） 382

6.13.13 对偶性和灵敏度分析 382

6.13.11 求LP的最偶问题的最优解 382

6.13.10 对偶理论 382

6.13.14 互补松弛性 383

6.13.15 对偶单纯形法 383

6.14 复习题 384

参考文献 405

第7章 运输、指派和转运问题 406

7.1 表述运输问题 406

7.1.1 运输问题的一般性描述 408

7.1.2 对总供应量超过总需求量的运输问题进行平衡 409

7.1.3 对总供应量小于总需求量的运输问题进行平衡 410

7.1.4 把库存问题建模为运输问题 411

7.1.5 在计算机上求解运输问题 413

7.1.6 由Excel电子表格获得LINGO数据 414

7.1.7 运输问题的电子表格求解方法 415

7.2 求运输问题的基本可行解 419

7.2.1 求基本可行解的西北角法 421

7.2.2 求基本可行解的最少成本法 423

7.2.3 求基本可行解的伏格尔法 425

7.3 运输单纯形法 427

7.3.1 运输问题中的旋转运算 428

7.3.2 对非基变量进行定价（以第6章为基础） 429

7.3.3 如何确定换入非基变量（以第5章为基础） 431

7.3.4 运输单纯形法小结和举例 432

7.4 运输问题的灵敏度分析 434

7.4.1 改变非基变量的目标函数系数 435

7.4.2 改变基变量的目标函数系数 435

7.4.3 把供应量si和需求量dj同时增加△ 436

7.5 指派问题 437

7.5.1 匈牙利方法 439

7.5.2 指派问题的计算机解法 442

7.6 转运问题 446

7.7 本章小结 450

7.7.1 符号表示 450

7.7.2 求平衡运输问题的基本可行解 451

7.7.3 求运输问题的最优解 451

7.7.4 指派问题 452

7.7.5 转运问题 452

7.7.6 运输问题的灵敏度分析 453

7.8 复习题 453

参考文献 462

第8章 网络模型 463

8.1 基本定义 463

8.2 最短路径问题 464

8.2.1 Dijkstra算法 466

8.2.2 作为转运问题的最短路径问题 467

8.3 最大流量问题 470

8.3.1 最大流最问题的LP解法 470

8.3.2 利用LINGO求解最大流量问题 473

8.3.3 求解最大流量问题的Ford-Fulkerson方法 474

8.3.4 Ford-Fulkerson方法小结和举例 478

8.4 CPM和PERT 482

8.4.1 计算事项最早时间 484

8.4.2 计算事项最迟时间 485

8.4.3 总时差 486

8.4.4 求关键路线 487

8.4.5 单时差 487

8.4.6 使用线性规划求关键路线 488

8.4.7 项目赶期 489

8.4.8 使用LINGO确定关键路线 491

8.4.9 PERT：计划评审法 493

8.4.10 PERT的难点 495

8.5 最少费用网络流量问题 501

8.5.1 把运输问题表述为MCNFP 502

8.5.2 把最大流量问题表述为MCNFP 502

8.5.3 利用LINGO求解MCNFP 504

8.6 最小生成树问题 508

8.7 网络单纯形法 511

8.7.1 MCNFP的基本可行解 512

8.7.2 计算bfs的第0行 513

8.7.3 网络单纯形法中的旋转变换 514

8.7.4 网络单纯形法小结 515

8.8.1 最短路径问题 519

8.8 本章小结 519

8.8.2 最大流量问题 520

8.8.3 关键路线法 520

8.8.4 PERT 522

8.8.5 最少费用网络流量问题 523

8.8.6 最小生成树问题 523

8.8.7 网络单纯形法 523

8.9 复习题 524

参考文献 528

第9章 整数规划 529

9.1 整数规划简介 529

9.2 表述整数规划问题 531

9.2.1 固定费用问题 534

9.2.2 集合覆盖问题 539

9.2.3 二选一约束条件 541

9.2.4 假设（if-then）约束条件 543

9.2.5 整数规划和分段线性函数 544

9.2.6 利用LINDO求解IP 550

9.2.7 利用LINGO求解IP 551

9.2.8 使用Excel Solver求解IP问题 554

9.3 求解纯整数规划问题的分枝定界法 572

9.4 求解混合整数规划问题的分枝定界法 584

9.5 利用分枝定界法求解背包问题 585

9.6 利用分枝定界法求解组合最优化问题 588

9.6.1 求解机器调度问题的分枝定界法 589

9.6.2 求解旅行推销员问题的分枝定界法 591

9.6.3 求解TSP的启发式方法 595

9.6.4 评价启发式方法 597

9.6.5 TSP的整数规划表述 597

9.6.6 使用LINGO求解TSP 599

9.7 隐枚举法 602

9.8 割平面法 608

9.9 本章小结 612

9.9.1 整数规划表述 612

9.9.2 固定费用问题 612

9.9.3 二选一约束条件 613

9.9.4 假设（if-then）约束条件 613

9.9.5 如何利用0—1型变量建立分段线性函数f(x)的模型 613

9.9.6 分枝定界法 614

9.9.7 求解纯IP的分枝定界法 614

9.9.8 求解混合IP的分枝定界法 614

9.9.9 求解背包问题的分枝定界法 614

9.9.10 使单台机器上的延迟时间最短的分枝定界法 614

9.9.11 求解旅行推销员问题的分枝定界法 614

9.9.13 隐枚举法 615

9.9.14 割平面法 615

9.9.12 求解TSP的启发式方法 615

9.10 复习题 616

参考文献 629

第10章 线性规划的高级主题 632

10.1 改进单纯形法 632

10.2 逆矩阵的乘积形式 637

10.3 使用列生成法求解大型LP 639

10.4 Dantzig-Wolfe分解算法 646

10.5 上界变量单纯形法 663

10.6 求解LP的Karmarkar方法 667

10.6.1 投影 668

10.6.2 Karmarkar方法的中心变换 668

10.6.3 Karmarkar方法的说明和示例 670

10.6.4 Karmarkar方法的第一次迭代 671

10.6.6 把LP变换成Karmarkar方法的标准形式 672

10.6.5 势函数 672

10.7 本章小结 675

10.7.1 改进单纯形法和逆矩阵的乘积形式 675

10.7.2 列生成法 676

10.7.3 Dantzig-Wolfe分解算法 676

10.7.4 上界变量单纯形法 678

10.7.5 Karmarkar方法 678

10.8 复习题 678

参考文献 679

第11章 非线性规划 681

11.1 微积分理论 681

11.1.1 极限 681

11.1.2 连续性 681

11.1.3 微分 682

11.1.5 泰勒级数展开式 683

11.1.4 高阶导数 683

11.1.6 偏导数 684

11.2 基本概念 686

11.2.1 NLP的示例 687

11.2.2 利用LINGO求解NLP 688

11.2.3 NLP和LP之间的区别 688

11.2.4 局部极值 690

11.2.5 NP表述的其他示例 690

11.2.6 利用Excel求解NLP 696

11.3 凸函数和凹函数 699

11.4 求解单变量的NLP 706

11.4.1 情况1：a＜x＜b且f′(x)=0的点 707

11.4.2 情况2：f′(x)不存在的点 709

11.4.3 情况3：区间［a,b］的端点a和b 710

11.4.4 定价和非线性优化 712

11.4.5 利用LINGO求解单变量NLP 716

11.5 黄金分割搜索法 719

11.6 具有多个变量的无约束最大化和最小化问题 725

11.7 最速上升法 730

11.8 拉格朗日乘子 734

11.8.1 拉格朗日乘子的几何解释 735

11.8.2 拉格朗日乘子和灵敏度分析 737

11.8.3 在LINGO上求解具有等式约束条件的NLP 739

11.9 库恩－塔克条件 741

11.9.1 库恩－塔克条件的几何解释 745

11.9.2 制约条件 748

11.9.3 在LINGO上求解具有不等式（也许还有等式） 749

约束条件的NLP 749

11.9.4 解释LINGO输出的Price列 749

11.10.1 二次规划和投资组合选择 751

11.10 二次规划 751

11.10.2 利用LINGO求解NLP 753

11.10.3 NLP的电子表格解法 754

11.10.4 求解二次规划问题的Wolfe方法 755

11.11 分离规划 760

11.12 可行方向法 765

11.13 帕累托最优化理论和权衡曲线 767

11.14 本章小结 773

11.14.1 凸函数和凹函数 773

11.14.2 求解单变量的NLP 773

11.14.3 黄金分割搜索法 773

11.14.4 具有多个变量的无约束最大化和最小化问题 774

11.14.5 最速上升法 774

11.14.6 拉格朗日乘子 774

11.14.8 二次规划 775

11.14.7 库恩－塔克条件 775

11.14.9 分离规划 776

11.14.10 可行方向法 776

11.14.11 权衡曲线过程小结 777

11.15 复习题 777

参考文献 779

第12章 对策论 781

12.1 二人零和与恒定和对策：鞍点 781

12.1.1 二人零和对策的特点 781

12.1.2 二人零和对策理论的基本假设 782

12.1.3 二人恒定和对策 783

12.2 二人零和对策：随机化策略、控制和图解法 785

12.2.1 随机化策略或混合策略 786

12.2.2 Odd和Even的图解 786

12.2.3 更多关于值和最优策略的概念 788

12.3 线性规划和零和对策 794

12.3.1 行局中人的LP 795

12.3.2 列局中人的LP 796

12.3.3 行局中人的LP和列局中人的LP之间的关系 796

12.3.4 如何求解行和列局中人的LP 798

12.3.5 使用LINDO或LINGO来求解二人零和对策 804

12.3.6 关于如何求解二人零和对策的小结 805

12.4 二人非恒定和对策 807

12.5 n人对策理论简介 811

12.6 n人对策的核心 812

12.7 沙普利值 816

12.8 本章小结 822

12.8.1 二人零和与恒定和对策 822

12.8.2 二人非恒定和对策 822

12.9 复习题 823

12.8.3 n人对策 823

参考文献 825

附录A @Risk锦囊 827

附录B 案例 838

案例1 帮帮忙，我一点都没有变年轻！ 838

案例2 你们家的太阳能 839

案例3 Golf-Sport：管理运营 840

案例4 Vision公司：生产规划和装运 843

案例5 通用邮件处理设施的材料处理 845

案例6 选择公司培训计划 848

案例7 BestChip：扩张策略 852

案例8 消防车在Springfield的位置 854

案例9 System Design：项目管理 855

案例10 Help-You公司的模块化设计 857

案例11 Brite Power：容量扩展 859