绪论 1
1 线性规划 7
1.1 线性规划的概念 7
1.1.1 线性规划问题的导出 7
1.1.2 线性规划问题的概念和模型 10
1.1.3 线性规划问题的标准型 11
1.1.4 线性规划问题的标准化 13
1.2 线性规划问题解的概念及性质 15
1.2.1 解的概念 15
1.2.2 图解法(解的几何表示) 16
1.2.3 基本可行解的几何意义 20
1.2.4 线性规划求解思路(单纯形法思想) 24
1.2.5 线性规划解的性质的证明 25
1.3 单纯形法 30
1.3.1 单纯形法引例 30
1.3.2 单纯形法的一般描述 35
1.3.3 表格单纯形法 40
1.3.4 一般线性规划问题的处理 45
1.3.5 单纯形法的矩阵描述 52
1.3.6 单纯形迭代过程中的几点注意事项 53
1.4 线性规划应用 55
1.4.1 线性规划建模 55
1.4.2 生产计划问题 56
1.4.3 合理下料问题 61
1.4.4 合理配料问题 64
1.4.5 运输问题 65
1.4.6 最大流量问题 66
1.5 习题1 68
2 线性规划问题的进一步研究 74
2.1 对偶原理 74
2.1.1 对偶线性规划问题的导出 74
2.1.2 对偶问题的定义 76
2.1.3 对偶定理 80
2.1.4 对偶最优解的经济含义--影子价格 83
2.1.5 由最优单纯形表求对偶问题最优解 84
2.2 对偶单纯形法 85
2.3 灵敏度分析 89
2.3.1 价值系数C发生改变 92
2.3.2 右端常数b发生改变 94
2.3.3 增加一个变量 95
2.3.4 增加一个约束 96
2.3.5 A中的元素发生改变 98
2.4 习题2 99
3 运输问题 102
3.1 运输问题模型与性质 102
3.1.1 约束方程组的系数矩阵具有特殊的结构 104
3.1.2 运输问题的基变量共有m+n-1个 105
3.1.3 m+n-1个变量构成基变量的充要条件是不含闭回路 106
3.2.1 初始基本可行解的确定 108
3.2 运输问题的求解(表上作业法) 108
3.2.2 最优性检验 113
3.2.3 主元变换 117
3.3 产销不平衡的运输问题 120
3.3.1 产量大于销量的情况 120
3.3.2 销量大于产量的情况 122
3.4 习题3 123
4 动态规划 126
4.1 动态规划概念与模型 126
4.1.1 引言 126
4.1.2 多段决策过程 127
4.1.3 动态规划模型 128
4.1.4 动态规划建模 129
4.2 动态规划求解 130
4.2.1 解的概念 130
4.2.2 最优性原理 131
4.2.3 贝尔曼函数 132
4.2.4 动态规划的基本方程 133
4.2.5 动态规划方法基本原理 134
4.2.6 动态规划问题求解的一般步骤 135
4.2.7 动态规划四大要素、一个方程 138
4.3 动态规划应用举例 138
4.3.1 工程路线问题 139
4.3.2 资源分配问题 149
4.3.3 串联系统可靠性问题 159
4.3.4 生产-库存问题 162
4.3.5 二维背包问题 167
4.3.6 设备更新问题 171
4.4 习题4 175
5 图与网络分析 179
5.1 图的基本概念 179
5.1.1 引言 179
5.1.2 图的概念 180
5.1.3 图的连通性 181
5.1.4 子图 182
5.1.5 有向图 183
5.1.6 树 184
5.2 网络最短路线问题 186
5.2.1 引言 186
5.2.2 最短路线问题的狄克斯拉算法 187
5.2.3 最短路线问题的海斯算法 192
5.2.4 最短路线问题的福德算法 196
5.3 最短树问题 198
5.3.1 引言 198
5.3.2 破圈法 199
5.3.3 生长法 200
5.4 最大流问题 201
5.4.1 引言 201
5.4.2 最大流最小割集定理 203
5.4.3 福德-富克逊算法 204
5.5 最小费用-最大流问题 212
5.5.1 引言 212
5.5.2 对偶法原理和步骤 212
5.5.3 对偶法示例 214
5.6 习题5 218
6 排队论 221
6.1 概述 221
6.1.1 引言 221
6.1.2 排除系统的特征 222
6.1.3 排除系统的结构 222
6.1.4 排队论研究的内容和目的 225
6.1.5 排队模型的分类 227
6.1.6 排队系统的常用符号 228
6.2 泊松输入-负指数服务的排队系统 229
6.2.1 典型分布 229
6.2.2 系统状态概率分布 232
6.2.3 状态转移速度图 235
6.2.4 系统的运行指标 237
6.3 M/M/1无限源系统 239
6.3.1 M/M/1/N系统 239
6.3.2 M/M/1等待制系统 242
6.3.3 M/M/1损失制系统 244
6.3.4 M/M/1无限源模型特点 245
6.4 M/M/C无限源系统 246
6.4.1 M/M/C/N系统 246
6.4.2 M/M/C等待制系统 249
6.4.3 M/M/C损失制系统 251
6.5 客源有限的排队系统 253
6.5.1 M/M/1/m/m系统 253
6.5.2 M/M/C/m/m系统 255
6.6 排队系统应用举例 258
6.7 本章小结 264
6.8 习题6 265