目录 1
第1章 线性规划 1
1.1 运筹学和线性规划 1
1.1.1 运筹学 1
1.1.2 线性规划 2
1.2 线性规划问题 2
1.2.1 生产计划问题 2
1.2.2 配料问题 3
1.2.3 背包问题 4
1.2.4 运输问题 4
1.2.5 指派问题 5
1.3 线性规划问题的标准形式 7
1.3.1 极大化目标函数的问题 8
1.3.2 约束条件不是等式的问题 8
1.3.3 变量无符号限制的问题 9
1.3.4 变量小于等于零的问题 9
1.4 线性规划问题的几何解释 10
1.5 线性规划的基、基础可行解 13
1.6 单纯形法原理 17
1.6.1 用消元法描述单纯形法原理 17
1.6.2 用向量矩阵描述单纯形法原理 24
1.7 单纯形表 34
1.8 初始基础可行解——两阶段法 44
1.9 退化和循环 49
1.10.1 选择进基变量的进一步理解 53
1.10 注释和补充 53
1.10.2 单纯形表的结构 55
1.10.3 改进单纯形法 64
1.10.4 用两阶段法判定线性规划问题无可行解 69
1.10.5 初始基础可行解——大M法 70
习题 71
第2章 对偶与灵敏度分析 75
2.1 对偶问题的建立 75
2.1.1 对偶的定义 75
2.1.2 对偶的对偶 76
2.1.3 其他形式的对偶问题 77
2.2 原始对偶关系 80
2.2.1 原始和对偶问题目标函数值之间的关系 80
2.2.2 互补松弛关系 82
2.2.3 最优解的充分必要条件——Kuhn-Tucker条件 86
2.2.4 单纯形表的结构，单纯形表与Kuhn-Tucker条件的关系 87
2.3 对偶单纯形法 92
2.3.1 对偶可行基 92
2.3.2 对偶单纯形法 94
2.4 灵敏度分析 98
2.4.1 目标函数系数的灵敏度分析 98
2.4.2 右边常数的灵敏度分析 101
2.4.3 增加一个新的变量 103
2.4.4 增加一个新的约束 105
2.5 对偶的经济解释 106
2.5.1 最大利润问题以及对偶问题的经济解释 106
2.5.2 互补松弛条件的经济解释 107
2.5.4 经济解释的例子 108
2.5.3 定理2.4的经济解释 108
2.6 注释和补充 112
2.6.1 约束条件系数矩阵中系数的灵敏度分析 112
2.6.2 最小成本问题的线性规划模型及其经济解释 115
习题 118
第3章 整数规划 122
3.1 整数规划模型 122
3.2 分枝定界法 129
习题 135
第4章 运输问题 136
4.1 运输问题的定义 136
4.2 运输问题约束系数矩阵的性质 139
4.3 运输问题的基在网络图中的表示 140
4.4 基在运输表中的表示 142
4.5 非基向量用基向量表示 144
4.6 运输问题单纯形法 147
4.6.1 确定初始基础可行解 147
4.6.2 计算非基变量的检验数 152
4.6.3 确定进基变量 159
4.6.4 确定离基变量 159
4.6.5 进行基变换 160
4.7 几种特殊的运输问题 163
4.7.1 运输路线不完全的问题 163
4.7.2 供求不平衡的运输问题 164
4.7.3 运输问题的退化基础可行解 165
习题 167
5.1.2 多目标线性规划的例子 169
5.1.1 单目标和多目标线性规划问题 169
5.1 多目标线性规划问题 169
第5章 多目标规划 169
5.2 多目标规划问题的非劣解和非劣解集 172
5.2.1 多目标问题非劣解和非劣解集的定义 172
5.2.2 多目标线性规划非劣解集的例子 173
5.3 求解多目标规划的目标的线性加权法 174
5.3.1 多目标规划目标线性加权的图解 174
5.3.2 用目标线性加权法求解多目标线性规划的例子 175
5.4 层次分析法 177
5.4.1 层次分析法的基本原理 177
5.4.2 层次分析法的步骤 179
5.4.3 层次分析法应用实例 189
5.5.1 目标规划问题的基本概念和结构 194
5.5 目标规划 194
5.5.2 目标无优先级的目标规划模型 197
5.5.3 目标有权重的目标规划模型 199
5.5.4 目标规划的字典序优化 201
5.5.5 目标规划字典序优化的单纯形表 202
5.5.6 目标规划问题案例 206
习题 212
第6章 网络优化 214
6.1 网络的基本概念 214
6.2 网络最小费用流问题 217
6.3 网络的关联矩阵 218
6.3.1 网络关联矩阵的结构和关联矩阵的秩 218
6.3.2 虚拟边和网络关联矩阵的增广矩阵 222
6.3.3 生成树和基础解 223
6.4 网络的非基向量用基向量表出 225
6.5.1 确定初始基础可行解 227
6.5.2 计算非基边的检验数 227
6.5 网络最小费用流问题单纯形法 227
6.5.3 确定进基变量或判定最优基 230
6.5.4 确定离基变量，进行基变换 231
6.6 最小费用流问题的初始可行解 234
6.7 最大流问题 241
6.7.1 最大流问题 241
6.7.2 最大流问题的基本概念 242
6.7.3 最大流问题的对偶问题 244
6.7.4 最大流问题的算法 247
6.8.1 最短路径问题的线性规划形式 250
6.8.2 最短路径问题的对偶问题 250
6.8 最短路径问题 250
6.8.3 费用为非负的最短路径问题算法 251
6.8.4 费用不全为非负的最短路径问题算法 253
6.9 网络优化问题总结 257
习题 258
第7章 动态规划 261
7.1 引例 261
7.2 动态规划的基本概念 最短路径问题 263
7.3 资源分配问题 267
7.4 背包问题 269
7.5 设备更新问题 272
7.6 具有转向费用的最短路径问题 275
7.7 货郎担问题 279
7.8 机器负荷分配问题 283
7.9 生产库存问题 285
7.10 用动态规划求解非线性规划问题 288
习题 290
第8章 排队论 292
8.1 排队的基本概念 292
8.1.1 顾客、服务台、服务 292
8.1.2 排队系统的分类 293
8.1.3 排队论中常用的记号及各类排队系统的符号 294
8.2 顾客到达和服务的时间分布 295
8.2.1 Poisson流 295
8.2.2 负指数分布 297
8.2.3 k阶Erlang分布 298
8.3 基本排队模型 ［M/M/1］：［∞/∞/FCFS］ 299
8.3.1 系统在时刻t有n个顾客的概率Pn（t） 299
8.3.2 系统的运行指标 303
8.3.3 Little公式 305
8.4 有限队列模型［M/M/1］：［N/∞/FCFS］ 305
8.4.1 ［M/M/1］：［N/∞/FCFS］系统中有k个顾客的概率 306
8.4.2 ［M/M/1］：［N/∞/FCFS］系统的运行指标 307
8.5 有限顾客源模型［M/M/1］：［∞/m/FCFS］ 309
8.5.1 系统中有n个顾客的概率 309
8.5.2 有限源系统的运行指标 313
8.6 多服务台模型［M/M/c］ 314
8.6.1 ［M/M/c］：［∞/∞/FCFS］模型 314
8.6.2 系统容量有限的［M/M/c］：［N/∞/FCFS］模型 316
8.6.3 顾客源有限的［M/M/c］：［∞/m/FCFS］模型 318
习题 320
案例1 食用调和油生产计划 321
附录1 线性规划案例 321
案例2 机械产品生产计划 322
案例3 炼油厂生产计划优化 324
案例4 物流配送和配送中心选址问题 326
附录2 案例1分析报告 331
1 模型构造 331
1.1 变量设置 331
1.2 模型构建 332
2 LINDO模型和求解结果 335
2.1 LINDO模型 335
2.2 LINDO求解结果 340
3 最优采购、生产、储存计划的说明和分析 349
3.1 采购、生产和存储量 349
3.2 1～6月份五种原料油采购价格以及成品油销售价格的变动分析 351
3.3 生产线的能力及影子价格分析 352
3.4 原料油硬度上下界约束分析 353
3.5 储罐容量分析 354
附录3 LINDO6.1用户手册 355
1 LINDO6.1简介和版本信息 355
2 LINDO6.1的菜单和工具图标 357
2.1 LINDO菜单 357
2.2 LINDO工具图标 359
3 LINDO线性规划模型的创建和模型结构 359
3.1 LINDO线性规划模型的创建 359
3.2 LINDO线性规划模型的结构 362
4.1 关键词 363
4.2 变量和变量名 363
4 LINDO模型的基本语法规则 363
4.3 运算和关系符号 364
4.4 数字 364
4.5 标题 364
4.6 注释 364
4.7 目标函数 365
4.8 约束条件 365
4.9 定义整数变量 367
4.10 定义变量的上下界 370
5 LINDO模型的编译和求解 371
5.1 LINDO模型的编译 371
5.2 LINDO模型的求解 375
5.3 LINDO模型的一次旋转运算 380
6.1 解的报告 385
6 LINDO模型的报告和分析 385
6.2 灵敏度分析 388
6.3 参数分析 388
6.4 单纯形表 389
7 目标规划的字典序解法 392
7.1 目标规划简介 392
7.2 LINDO中目标规划的字典序解法 393
8 线性规划模型的MPS格式 395
8.1 从LINDO模型文件生成MPS格式模型文件 395
8.2 LINDO打开MPS格式模型文件 399
附录4 Excel“规划求解” 404
1 在系统中安装“规划求解” 404
2 在Excel中创建线性规划模型 405