运筹学原理与算法

前言
第1章 线性规划 1
1.1 线性规划的模型及概念 1
一、线性规划及其模型 1
二、线性规划的几何意义 6
1.2 单纯形法 9
· · · · · · (更多)

前言
第1章 线性规划 1
1.1 线性规划的模型及概念 1
一、线性规划及其模型 1
二、线性规划的几何意义 6
1.2 单纯形法 9
一、线性规划的单纯形表 9
二、可行基与基可行解的概念和性质 10
三、已知一个可行基的单纯形法 12
1.3 对偶单纯形法 18
一、正则基的概念和性质 18
二、已知一个正则基的对偶单纯形法 19
习题1 22
第2章 线性规划全过程算法 24
2.1 两阶段法 24
一、求可行基的方法 24
二、全过程算法一(两阶段法) 25
2.2 大M单纯形法 31
一、基本原理 31
二、全过程算法二(大M单纯形法) 32
2.3 大M对偶单纯形法 36
一、基本原理 36
二、全过程算法三(大M对偶单纯形法) 37
2.4 亚基迭代算法 41
一、概念 41
二、全过程算法四(亚基迭代算法) 42
习题2 45
第3章 线性规划的扩展问题 47
3.1 线性规划的对偶理论 47
一、对偶线性规划的概念 47
二、对偶线性规划之间的关系 48
3.2 线性规划的灵敏度问题 54
一、灵敏度的概念 54
二、目标函数中非最优基变量的系数c_j的灵敏度 55
三、目标函数中最优基变量的系数c_{R(i)}的灵敏度 55
四、约束条件中常数项b_i的灵敏度 57
五、约束条件中非最优基变量的系数a_{ij}的灵敏度 58
3.3 目标线性规划 59
一、关于无最优解的多目标线性规划 59
二、关于无可行解的线性规划 64
习题3 67
第4章 整数线性规划 69
4.1 整数线性规划概念 69
4.2 一般整数线性规划的解法 71
一、一般整数线性规划与线性规划的关系 71
二、分支定界法 72
三、割平面法 78
4.3 0-1整数规划的解法 85
一、隐枚举法 86
二、特殊0-1整数规划的特殊解法 88
习题4 92
第5章 最小支撑树和最优路径问题 94
5.1 图与网络的概念 94
一、图的概念 94
二、子图的概念与几种特殊子图 96
5.2 最小支撑树问题及其算法 97
一、破圈法 97
二、避圈法 98
三、生长树法 98
5.3 最短路问题及其算法 100
一、最短路的概念 100
二、延伸路径的方法与特点 100
三、无负权值最短路问题的Dijkstra算法 101
四、含负权值无回路最短路问题的强Dijkstra算法 106
五、最短路问题的Floyd算法 111
5.4 最长路径问题及其算法 114
一、最长路的概念 114
二、最长路问题的仿强Dijkstra算法 114
三、最长路问题的仿Floyd算法 119
5.5 最大增流路径问题 121
一、基本概念 121
二、最大增流路径问题的仿Dijkstra算法 121
三、最大增流路径问题的仿Floyd算法 124
习题5 126
第6章 网络最优选址和网络最优计划问题 129
6.1 网络最优选址问题 129
一、网络最优选址的概念 129
二、单点最优选址问题的算法 130
三、多点最优选址问题的算法 131
四、半径有界的最优选址问题的算法 135
6.2 网络最优计划问题 138
一、基本概念 138
二、网络最优计划问题的箭线图 139
6.3 网络最优计划问题的算法 140
一、基于单箭线图的网络最优计划问题的算法 140
二、基于复箭线图的网络最优计划问题的算法 145
三、关键作业和关键路径的概念与应用 147
习题6 149
第7章 最大流和最小费用流问题 151
7.1 最大流问题及其算法 151
一、有向网络最大流问题及其数学模型 151
二、有向网络的割与割量的概念与性质 152
三、有向网络最大流的Ford-Fulkersen算法 153
四、无向网络最大流算法 157
7.2 最小费用流问题及其算法 162
一、最小费用流的概念 162
二、调费图与负回路的概念与性质 163
三、最小费用流问题的算法 166
习题7 169
第8章 运输问题 171
8.1 运输问题及其特征 171
一、运输问题的数学模型 171
二、运输问题的特征 172
8.2 运输问题的解法一(表上回路法) 176
一、平衡运输问题的基可行解获取方法 176
二、平衡运输问题的最优解获取方法 179
三、不平衡运输问题的解法 184
8.3 运输问题的解法二(仿最小费用流算法) 187
一、运输问题与最小费用流问题的关系 187
二、运输问题的仿最小费用流算法 189
8.4 运输问题的解法三(平衡负回路算法) 196
一、运输问题的检测矩阵与位置矩阵 196
二、运输问题的平衡负回路算法 197
习题8 202
第9章 分配问题 205
9.1 分配问题及其特征 205
一、分配问题及其数学模型 205
二、几种分配问题之间的关系 207
三、典则分配问题的性质 208
9.2 分配问题的解法一(匈牙利算法) 209
一、典则分配问题的解法 209
二、一般平衡分配问题的解法 214
三、不平衡分配问题的解法 217
9.3 分配问题的解法二(平衡负回路算法) 221
一、典则分配问题的平衡负回路算法 221
二、一般平衡分配问题的平衡负回路算法 226
习题9 229
第10章 动态规划 231
10.1 阶段性网络上最优路径的动态规划算法 231
一、最优路径的延伸算法的共同特点 231
二、阶段性网络上最优路径的动态规划算法 233
10.2 适合动态规划的问题与最优性原理 236
一、动态规划的概念 236
二、动态规划在一些线性约束规划上的应用 237
三、动态规划在一些案例中的应用 246
习题10 251
第11章 存储论 254
11.1 存储论的基本概念 254
11.2 确定性存储模型 255
一、不允许缺货，即刻到货模型 255
二、不允许缺货，到货需一定时间模型 257
三、允许缺货，即刻到货模型 259
四、允许缺货，生产需一定时间 261
五、价格有折扣的存储问题 263
11.3 随机性存储模型 265
一、需求是随机离散的存储模型 265
二、需求是连续型随机变量的存储模型 267
三、(s,S)型存储策略 268
习题11 273
第12章 对策论 275
12.1 对策论概述 275
一、对策论的基本要素 275
二、对策的例子 276
12.2 矩阵对策中的策略 277
一、矩阵对策的最优纯策略 277
二、矩阵对策的混合策略 279
12.3 矩阵对策的基本定理 281
一、基本定理 281
二、基本性质 282
12.4 矩阵对策的求解 283
一、图解法 283
二、线性规划法 284
三、方程组法 286
12.5 其他对策模型简介 288
一、二人无限零和对策 288
二、二人无限非零和对策 289
三、合作对策 290
四、多人非合作对策 291
习题12 293
第13章 排队论 295
13.1 随机服务系统与过程 295
一、排队系统的描述 295
二、排队系统的符号表示 296
三、排队系统的主要数量指标和记号 297
13.2 排队系统的常用分布 297
一、指数分布 297
二、泊松分布 298
三、爱尔朗分布 299
13.3 单服务台排队模型 299
一、标准的M/M/1模型 300
二、系统容量有限的M/M/1/N/∞模型 302
三、顾客源有限的M/M/1/∞/m模型 304
13.4 多服务台排队模型 306
13.5 排队系统的优化问题 307
一、M/M/1模型的最优平均服务率 307
二、M/M/c模型的最佳服务台数 308
习题13 309
参考文献 311
· · · · · · (收起)