高级运筹学9787030776754

目录

第1章 基本概念与基本理论 1

1.1 运筹学*优化问题举例 1

1.2 凸集、凸函数和凸规划 5

1.2.1 凸集 5

1.2.2 凸函数 6

1.2.3 凸规划 8

1.3 *优性条件 10

1.3.1 非线性规划的数学模型 10

1.3.2 极值问题 11

1.4 迭代算法收敛性 13

1.4.1 迭代的基本格式 13

1.4.2 收敛性与收敛速度 15

习题 1 16

第2章 线性规划与灵敏度分析 17

2.1 线性规划问题及其数学模型 17

2.1.1 线性规划问题的数学模型 17

2.1.2 线性规划问题的标准型 19

2.2 线性规划问题的图解法及几何意义 21

2.2.1 线性规划问题解的概念 21

2.2.2 线性规划问题的图解法 24

2.2.3 基本定理 27

2.3 单纯形算法 27

2.3.1 确定初始基可行解 28

2.3.2 *优性检验 29

2.3.3 基变换 30

2.4 单纯形算法的进一步讨论 34

2.4.1 初始基本可行解的确定 34

2.4.2 大M法 35

2.4.3 两阶段法 37

2.4.4 检验数的几种表示方法 39

2.5 线性规划的对偶理论 40

2.5.1 对偶问题 40

2.5.2 对偶理论 42

2.5.3 对偶解的经济解释 48

2.5.4 对偶单纯形法 51

2.6 灵敏度分析 54

2.6.1 目标函数价值系数 cj 的灵敏度分析 55

2.6.2 资源约束量 b 的灵敏度分析 57

2.6.3 添加新变量的灵敏度分析 58

2.6.4 添加新约束的灵敏度分析 59

2.6.5 技术系数 aij 的改变 (计划生产的产品工艺结构发生改变) 60

2.7 应用举例 63

习题 2 66

第3章 整数规划 70

3.1 整数规划的数学建模 70

3.1.1 装箱问题 70

3.1.2 工厂选址问题 70

3.1.3 背包问题 71

3.2 整数规划的求解算法 72

3.2.1 分支定界算法 72

3.2.2 割平面法 74

3.2.3 0-1 规划及隐枚举法 76

3.2.4 指派问题及匈牙利法 77

3.3 案例分析 82

3.3.1 分销中心选址问题 82

3.3.2 航线的优化安排问题 84

3.3.3 投资项目选择问题 86

3.3.4 值班人员安排问题 87

习题 3 89

第4章 动态规划 92

4.1 多阶段决策过程与实例 92

4.2 动态规划的基本概念和递归方程 94

4.3 *优性原理与建模方程 98

4.4 动态规划的应用案例 99

4.4.1 背包问题 99

4.4.2 投资问题 101

4.4.3 排序问题 103

4.4.4 旅行售货商问题 106

4.4.5 Stackelberg 博弈 108

4.4.6 动态规划在非线性规划求解中的应用 108

4.4.7 动态规划在基础数学中的应用 109

4.5 案例分析 110

习题 4 114

第5章 目标规划 116

5.1 目标规划问题 116

5.1.1 目标规划的定义 116

5.1.2 目标规划问题举例 116

5.1.3 多目标优化问题处理方法的一般讨论 120

5.2 目标规划的数学模型 122

5.2.1 多目标优化问题的处理 123

5.2.2 目标约束的处理 124

5.2.3 带有优先级的目标规划 125

5.3 目标规划的图解法 129

5.4 目标规划的算法 132

5.4.1 单纯形法 132

5.4.2 序列解法 137

5.5 应用举例 140

习题 5 145

第6章 一维极值优化问题 149

6.1 分数法 (斐波那契法) 150

6.2 黄金分割法 (0.618 法) 152

6.3 牛顿法 (切线法) 154

6.4 抛物线法 (二次插值法) 156

6.5 外推内插法 160

习题 6 161

第7章 无约束*优化方法 162

7.1 梯度法 (*速下降法) 162

7.2 共轭梯度法 165

7.3 牛顿法 169

7.4 变尺度法 173

7.5 坐标轮换法 178

7.6 单纯形法 180

7.7 模式搜索法 183

7.8 鲍威尔方法 185

习题 7 192

第8章 约束*优化方法 193

8.1 约束优化方法概述 193

8.1.1 约束优化问题的类型 193

8.1.2 约束优化方法的分类 193

8.1.3 约束优化问题的*优解及其必要条件 194

8.2 库恩-塔克条件 196

8.2.1 等式约束优化问题的*优性条件 196

8.2.2 不等式约束优化问题的*优性条件 197

8.2.3 一般约束优化问题的*优性条件 199

8.3 罚函数法与障碍函数法 203

8.3.1 罚函数法 203

8.3.2 障碍函数法 207

8.3.3 混合罚函数法 210

8.3.4 乘子法 211

8.4 复形法 212

习题 8 214

第9章 运筹学软件介绍 215

9.1 运筹学中几种常见软件介绍 215

9.2 利用Excel求解线性规划问题 218

9.2.1Excel求解线性规划问题步骤 218

9.2.2 利用Excel进行线性规划的灵敏度分析 221

9.3 利用Excel求解整数规划 223

9.3.1 整数规划求解 223

9.3.2 0-1整数规划求解 225

9.4 LINGO软件求解非线性规划 226

9.4.1 LINGO软件介绍 226

9.4.2 LINGO求解一维极值优化问题 228

9.4.3 LINGO求解无约束*优问题 229

9.4.4 LINGO求解约束*优问题 230

9.5 LINGO求解多目标规划问题 230

9.5.1 多目标规划实例 230

9.5.2 多目标规划的有效解 233

参考文献 238

第1章 基本概念与基本理论

1.1 运筹学*优化问题举例

在运筹学模型中，一类*重要的模型是数学规划模型，它们有如下共同形式：

其中，i， j， k， h 为指标变量取值从 1 开始顺序排列的有限自然数；f 为实值函数 (或向量函数)，称为目标函数；gh 为一系列函数，称为约束函数；opt. 表示对右端函数优化，一般取*大 (max) 或*小 (min)；s.t. 是 subject to的缩写，表示问题的解要满足后面的等式或不等式组，xi 为决策变量，cj ， dk 为问题的参数。

这类模型的形式表示要在限定的约束条件下求得目标函数的*优解。

在讨论中常把约束条件表示为集合的形式：

称为约束集合或可行解集合 (简称可行集)，为了便于讨论，常把模型记为如下的简单形式：

数学规划模型按其函数特征及变量性质可以划分为不同类型。

(1) 线性规划模型。各函数均为线性函数，变量均为确定型的问题。

(2) 非线性规划模型。各函数中含有非线性函数，变量均为确定型的问题。

(3) 多目标规划模型。上两类问题中，若目标函数是向量值函数，变量即多个目标函数的问题。

(4) 整数规划模型。上述问题中，若决策变量的取值范围是整数的问题，则为整数规划模型。

(5) 动态规划模型。求解多阶段决策过程的问题。

(6) 随机规划模型。当问题存在随机因素时，求解过程有其特殊的要求。

为了帮助读者建立运筹学模型的概念，并了解建模思想的实际应用，下面举一些运筹学优化的例子。

例 1.1 多参数的*线拟合问题。已知热敏电阻 R 依赖于温度 t 的函数关系：

其中，x1， x2， x3 为待定参数。

经过实验测得一组数据 {(ti，Ri) |i = 1， 2，？？？， n}，问题是如何确定参数 x1， x2， x3 使得偏差的平方和*小。

给定一组数据 (x1， x2， x3)，由上式可以确定 R 关于 t 的函数关系式，但这条*线不一定正好通过测量点，通常使用*小平方和误差来度量。

这就是*小二乘问题。

例 1.2 生产成本问题。设 x1 为资本，x2 为劳动力，Q 为产出产量。则

其中，A 为生产技术水平；α， β 为参数；Q(x1， x2) 称为柯布-道格拉斯 (Cobb-Douglas) 生产函数。

已知工资率为 ω，资本报酬率为 r，则生产成本为

生产成本问题就是产量不低于某一水平 Q0 的条件下，使生产成本*小化

例 1.3 资源分配问题。考虑将 m 种资源安排给n种活动，问应如何分配资源，才能使收益*大？

《高级运筹学（第二版）》主要包括高级运筹学的基本概念与基本理论、线性规划与灵敏度分析、整数规划、动态规划、目标规划、一维极值优化问题、无约束*优化方法、约束*优化方法、运筹学软件介绍等定量分析和优化的理论与方法。这些内容是经济管理类研究生应具备的基础知识，《高级运筹学（第二版）》强调学以致用，以大量实际问题为背景引出各分支的基本概念、模型和方法，具有很强的实用性；在基本原理和方法的介绍方面，《高级运筹学（第二版）》尽量避免复杂的理论证明，通过大量通俗易懂的例子进行理论方法的讲解，具有较强的趣味性，又不失理论性，理论难度由浅入深，适合不同层次的读者。