运筹学原理与算法PDF电子书下载

第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

二、目标函数中非最优基变量的系数cj的灵敏度 55

三、目标函数中最优基变量的系数cR（i）的灵敏度 55

四、约束条件中常数项bi的灵敏度 57

五、约束条件中非最优基变量的系数α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

二、最长路问题的仿强Dij kstra算法 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