运筹学原理与算法

前言

第1章 线性规划

1.1 线性规划的模型及概念

一、线性规划及其模型

二、线性规划的几何意义

1.2 单纯形法

一、线性规划的单纯形表

二、可行基与基可行解的概念和性质

三、已知一个可行基的单纯形法

1.3 对偶单纯形法

一、正则基的概念和性质

二、已知一个正则基的对偶单纯形法

习题1

第2章 线性规划全过程算法

2.1 两阶段法

一、求可行基的方法

二、全过程算法一（两阶段法）

2.2 大M单纯形法

一、基本原理

二、全过程算法二（大M单纯形法）

2.3 大M对偶单纯形法

一、基本原理

二、全过程算法三（大M对偶单纯形法）

2.4亚基迭代算法

一、概念

二、全过程算法四（亚基迭代算法）

习题2

第3章 线性规划的扩展问题

3.1 线性规划的对偶理论

一、对偶线性规划的概念

二、对偶线性规划之间的关系

3.2 线性规划的灵敏度问题

一、灵敏度的概念

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

三、目标函数中最优基变量的系数□的灵敏度

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

五、约束条件中非最优基变量的系数□的灵敏度

3.3 目标线性规划

一、关于无最优解的多目标线性规划

二、关于无可行解的线性规划

习题3

第4章 整数线性规划

4.1 整数线性规划概念

4.2 一般整数线性规划的解法

一、一般整数线性规划与线性规划的关系

二、分支定界法

三、割平面法

4.3 0-1整数规划的解法

一、隐枚举法

二、特殊0-1整数规划的特殊解法

习题4

第5章 最小支撑树和最优路径问题

5.1 图与网络的概念

一、图的概念

二、子图的概念与几种特殊子图

5.2 最小支撑树问题及其算法

一、破圈法

二、避圈法

三、生长树法

5.3 最短路问题及其算法

一、最短路的概念

二、延伸路径的方法与特点

三、无负权值最短路问题的Dijkstra算法

四、含负权值无回路最短路问题的强Dijkstra算法

五、最短路问题的Floyd算法

5.4 最长路径问题及其算法

一、最长路的概念

二、最长路问题的仿强Dijkstra算法

三、最长路问题的仿Floyd算法

5.5 最大增流路径问题

一、基本概念

二、最大增流路径问题的仿Dijkstra算法

三、最大增流路径问题的仿Floyd算法

习题5

第6章 网络最优选址和网络最优计划问题

6.1 网络最优选址问题

一、网络最优选址的概念

二、单点最优选址问题的算法

三、多点最优选址问题的算法

四、半径有界的最优选址问题的算法

6.2 网络最优计划问题

一、基本概念

二、网络最优计划问题的箭线图

6.3 网络最优计划问题的算法

一、基于单箭线图的网络最优计划问题的算法

二、基于复箭线图的网络最优计划问题的算法

三、关键作业和关键路径的概念与应用

习题6

第7章 最大流和最小费用流问题

7.1 最大流问题及其算法

一、有向网络最大流问题及其数学模型

二、有向网络的割与割量的概念与性质

三、有向网络最大流的Ford-Fulke en算法

四、无向网络最大流算法

7.2 最小费用流问题及其算法

一、最小费用流的概念

二、调费图与负回路的概念与性质

三、最小费用流问题的算法

习题7

第8章 运输问题

8.1 运输问题及其特征

一、运输问题的数学模型

二、运输问题的特征

8.2 运输问题的解法一（表上回路法）

一、平衡运输问题的基可行解获取方法

二、平衡运输问题的最优解获取方法

三、不平衡运输问题的解法

8.3 运输问题的解法二（仿最小费用流算法）

一、运输问题与最小费用流问题的关系

二、运输问题的仿最小费用流算法

8.4 运输问题的解法三（平衡负回路算法）

一、运输问题的检测矩阵与位置矩阵

二、运输问题的平衡负回路算法

习题8

第9章 分配问题

9.1 分配问题及其特征

一、分配问题及其数学模型

二、几种分配问题之间的关系

三、典则分配问题的性质

9.2 分配问题的解法一（匈牙利算法）

一、典则分配问题的解法

二、一般平衡分配问题的解法

三、不平衡分配问题的解法

9.3 分配问题的解法二（平衡负回路算法）

一、典则分配问题的平衡负回路算法

二、一般平衡分配问题的平衡负回路算法

习题9

第10章 动态规划

10.1 阶段性网络上最优路径的动态规划算法

一、最优路径的延伸算法的共同特点

二、阶段性网络上最优路径的动态规划算法

10.2 适合动态规划的问题与最优性原理

一、动态规划的概念

二、动态规划在一些线性约束规划上的应用

三、动态规划在一些案例中的应用

习题10

第11章 存储论

11.1 存储论的基本概念

11.2 确定性存储模型

一、不允许缺货，即刻到货模型

二、不允许缺货，到货需一定时间模型

三、允许缺货，即刻到货模型

四、允许缺货，生产需一定时间

五、价格有折扣的存储问题

11.3 随机性存储模型

一、需求是随机离散的存储模型

二、需求是连续型随机变量的存储模型

三、（s，S）型存储策略

习题11

第12章 对策论

12.1 对策论概述

一、对策论的基本要素

二、对策的例子

12.2 矩阵对策中的策略

一、矩阵对策的最优纯策略

二、矩阵对策的混合策略

12.3 矩阵对策的基本定理

一、基本定理

二、基本性质

12.4 矩阵对策的求解

一、图解法

二、线性规划法

三、方程组法

12.5 其他对策模型简介

一、二人无限零和对策

二、二人无限非零和对策

三、合作对策

四、多人非合作对策

习题12

第13章 排队论

13.1 随机服务系统与过程

一、排队系统的描述

二、排队系统的符号表示

三、排队系统的主要数量指标和记号

13.2 排队系统的常用分布

一、指数分布

二、泊松分布

三、爱尔朗分布

13.3 单服务台排队模型

一、标准的M／M／1模型

二、系统容量有限的M／M／1／N／∞模型

三、顾客源有限的M／M／1／∞／m模型

13.4 多服务台排队模型

13.5 排队系统的优化问题

一、M／M／1模型的最优平均服务率

二、M／M／c模型的最佳服务台数

习题13

参考文献

《运筹学原理与算法》与现行的其他运筹学教材相比，不涉及非线性规划，但增加了网络最优选址问题，扩充了网络规划和分配问题的内容。对一些经典运筹问题，补充了一些运筹理论，还补充了一些更加简便、实用的运筹算法。《运筹学原理与算法》的另一个特点是，把运筹方法的程序设计纳入教学内容中，详细、完整、规范地给出了各种运筹方法的算法步骤。

　　《运筹学原理与算法》是针对应用数学专业本科生编写的教材，也可作为经济管理、系统工程、计算机工程等专业的本科生教材，还可供相关专业研究生及科技工作者参考。