运筹学PDF电子书下载

第一章 线性规划问题及单纯形算法 7

1.1 线性规划问题及其一般数学模型 7

1.1.1 线性规划问题举例 7

1.1.2 线性规划数学模型的一般表示方式 10

1.1.3 图解法的求解过程 12

1.2 线性规划问题的单纯形解法 15

1.2.1 线性规划问题的解 15

1.2.2 线性规划解题过程的基本步骤 18

1.2.3 线性规划单纯形表及其格式 20

1.2.4 目标函数为极大化(max)问题、约束条件为(≤)型的线性规划的单纯形算法 22

1.3 当目标函数为极小化(min)问题，约束条件为(≥)型情况下的原单纯形算法 28

1.3.1 当约束条件为(≥)型，引入剩余变量、人工变量的意义 28

1.3.2 大 M 法的求解过程 28

1.3.3 二阶段法的求解过程 30

1.4 原单纯形法迭代过程中的一些具体问题 33

1.4.1 关于无界解问题 33

1.4.2 关于退化问题 33

1.4.3 关于多重解问题 36

1.4.4 关于无可行解问题 38

1.5 修正单纯形算法 39

1.5.1 修正单纯形算法的基本思路 40

1.5.2 检验数(cj—zj)及入变量 xi*的确定 43

1.5.3 出变量 xl 的确定 44

1.5.4 简化型修正单纯形表及其算法 45

第二章 线性规划的对偶理论及其应用 51

2.1 线性规划的对偶理论 51

2.1.1 线性规划原问题与对偶问题的表达形式 51

2.1.2 非标准型线性规划的对偶变换 54

2.2 线性规划的对偶定理 56

2.2.1 弱对偶定理 56

2.2.2 最优解判别定理 59

2.2.3 主对偶定理 59

2.2.4 互补松弛定理 60

2.2.5 原问题的检验数(cj—zj)与对偶问题决策变量的解的相互关系 62

2.3 对偶单纯形算法 66

2.3.1 对偶单纯形算法的基本思路 66

2.3.2 对偶单纯形算法的迭代过程 67

2.4.1 关于边际值(影子价)qi 70

2.4 线性规划的灵敏度分析 70

2.4.2 目标函数中 cj 的灵敏度分析 72

2.4.3 对右端项 bi 值的灵敏度分析 75

2.4.4 对技术系数αij的灵敏度分析 78

2.4.5 当约束条件中增加新的决策变量的分析 80

2.4.6 增加新的约束条件的分析 81

2.4.7 线性规划灵敏度分析举例 83

第三章 运输问题与任务分配问题 91

3.1 运输问题的一般数学模型 91

3.2 运输问题数学模型的求解方法 94

3.2.1 寻找初始基础可行解 95

3.2.2 检验初始分配表是否为最优解 100

3.2.3 引入新基变量及其迭代过程 104

3.2.4 对新的基础可行解进行再检验、再调整直至最优 105

3.3 运输问题数学模型迭代过程中的一些具体问题 107

3.3.1 引入新基变量时闭回路的画法 107

3.3.2 关于产销不平衡运输问题 107

3.3.3 关于退化问题 109

3.4 有转运点的运输问题 112

3.5 任务分配问题 115

3.5.1 关于任务分配问题的匈牙利解法 117

3.5.2 求目标函数为 max 时的任务分配问题 121

第四章 整数规划 124

4.1 整数规划简述 124

4.2 整数规划的分枝定界解法 126

4.2.1 分枝定界法的基本思路及解题步骤 126

4.2.2 分枝定界法求解过程举例 128

4.3 纯整数规划的割平面解法 130

4.3.1 割平面法约束条件的推导 130

4.3.2 割平面法的求解过程举例 133

4.4 混合型整数规划的割平面解法 137

4.5 关于0-1规划简述 141

第五章 动态规划 142

5.1 动态规划的最优化原理及其算法 142

5.1.1 求解多阶段决策过程的方法 142

5.1.2 动态规划常用的基本概念及递推公式 146

5.2 动态规划模型举例 149

5.2.1 资源分配问题 149

5.2.2 项目选择问题 153

5.2.3 产品生产计划安排问题 158

5.2.4 机器串联运行的可靠性问题 164

5.2.5 其他应用问题 168

第六章 网路分析 172

6.1 图与网路的基本概念 172

6.2 树图及最短连线问题 174

6.2.1 树的定义及其性质 175

6.2.2 图的部分树 175

6.2.3 网路的最短连线 177

6.3.1 无循环有向网路从一个始点到其他各点(包括终点)的最短路算法 180

6.3 最短路径问题 180

6.3.2 无向网路中任意两点间的最短路算法 184

6.3.3 指定两点间最短路应用举例 190

6.4 网路的最大流、最小截集 192

6.4.1 网路最大流的概念 192

6.4.2 截集与截集容量 193

6.4.3 确定网路最大流的标号法 196

6.4.4 多端网路问题 199

6.4.5 最小费用最大流算法 202

6.4.6 以最短路为基础，网路上各段弧总流量的算法——弧扫描法 206

6.5.1 欧拉回路问题 210

6.5 欧拉(Euler)回路及邮路问题 210

6.5.2 中国邮路问题 211

6.6 哈密尔顿(Hamilton)回路及旅行员问题 213

6.6.1 哈密尔顿回路 213

6.6.2 旅行员问题 214

6.7 配对问题 219

第七章 随机服务理论概述 223

7.1 随机服务系统 223

7.2 随机服务过程 226

7.3.1 概述 231

7.3 服务时间 231

7.3.2 服务时间常用到的理论分布 233

7.3.3 负指数分布的特点 236

7.4 输入过程 237

7.4.1 到达率和常见的输入过程 237

7.4.2 波松输入过程及其特点 238

7.5 生灭过程 241

7.6 纯产生过程 245

8.1 Μ/Μ/n 系统、损失制、无限源 248

第八章 标准服务系统 248

8.2 Μ/Μ/n 系统、损失制、有限源 254

8.3 Μ/Μ/n 等待制、无限源、无限容量 257

8.3.1 系统的稳态概率 pj 及等待的概率 257

8.3.2 系统的各种指标 260

8.3.3 等待时间的概率分布 263

8.2.4 等待时间分布的布赫曼公式 266

8.4 Μ/Μ/n 等待制，有限来源 267

8.5 Μ/Μ/n 系统、等待制、无限源、有限容量 269

9.1.1 系统中逗留顾客的平均数 274

9.1 Μ/G/1 系统、无限源、无限容量 274

第九章 特殊随机服务系统 274

9.1.2 平均逗留时间和平均等待时间 277

9.1.3 平均剩余服务时间 277

9.2 优先权服务系统 278

9.3 部分利用度服务系统 282

9.4 溢流通路 286

9.5 网状服务系统、等待制 290

9.6 流体近似法 292

10.1 存储的过程、费用和管理 296

第十章 存储理论 296

10.2 确定型存储模型 299

10.2.1 不允许缺货模型 299

10.2.2 允许缺货模型 303

10.2.3 连续性进货、不允许缺货模型 306

10.2.4 两种存储费、不允许缺货模型 307

10.2.5 不允许缺货、批量折扣模型 309

10.3 多阶段存储模型 312

10.4 随机型存储模型 314

10.4.1 简单随机存储模型——报童问题 315

10.4.2 随机需求存储模型，缓冲储备量 318

第十一章 随机模拟 322

11.1 随机模拟的一般方法 322

11.2 产生随机数的方法 326

11.2.1 (0，1)均匀分布随机数的产生 326

11.2.2 其他分布函数的随机数 328

11.3 模拟举例 332

主要参考文献 344