运筹学（第三版）

运输问题71
3.1运输问题的数学模型71
3.2表上作业法72
3.3产销不平衡的运输问题83
3.4转运问题87
3.5案例分析91
习题398
第4章
整数规划101
4.l整数规划的数学建模l0l
4.2整数规划的求解算法103
4.3案例分析115
习题4122
第5章
动态规划125
5.1多阶段决策过程与实例126
5.2动态规划的基本概念和递归方程127
5.3最优性原理与建模方程132
5.4动态规划的应用案例133
5.5案例分析143
习题5148
第6章
图论与网络计划150
6.1图与网络151
6.2树155
6.3最短路问题158
6.4网络最大流问题162
6.5最小费用流问题168
6.6网络计划技术171
6.7案例分析189 习题6195
第7章
存储论198
7.1存储概述198
7.2确定性存储模型202
7.3单周期的随机性存储模型209
7.4案例分析212
习题7216
第8章
决策分析218
8.1决策分析概论218
8.2不确定型决策方法219
8.3风险型决策分析方法221
8.4多属性决策方法229
8.5案例分析238
习题8212
第9章
排队论245
9.1排队论的基本概念245
9.2单服务台排队系统分析249
9.3多服务台排队系统分析257
9.4案例分析262
习题9266
第10章
实验268
lO.1运筹学中几种常见软件介绍268
10.2利用Exccl求解线性规划问题272
10.3利用Excel进行线性规划的灵敏度分析274
10.4利用Excel对运输问题求解276
10.5利用Excel求解整数规划279
参考文献283

.　　 而最终目标是求满足约束条件和使采购成本最小时的解。由此，建立的数学模型为从以上两个例子的数学模型可以看出，目标函数为决策变量的线性函数，约束条件也为决策变量的线性不等式（或等式），该类数学模型具有如下特点。
　　 (l)有一组非负的决策变量(decisionorcontrolvariable)，这组决策变量的值都代表一个具体方案。
　　 (2)有一组约束条件，含有决策变量的线性不等式（或等式）组(linearfunctionconstraints)，
　　 (3)有一个含有决策变量的线性目标函数(objectivelinearfunction)，按研究问题的不同，要求目标函数实现最大化或最小化。
　　 我们把满足上述三个条件的数学模型称为线性规划数学模型。如果目标函数是决策变量的非线性函数或约束条件含有决策变量的非线性不等式（或等式），我们就称这类数学模型为非线性规划数学模型。
　　 线性规划数学模型的一般形式如下：
　　 在该数学模型中，式(1.1)称为日标函数；式(1.2)称为约束条件；式(1.3)称为变量的非负约束条件。
　　 1.1.2线性规划问题的标准型
　　 由前面所举的例子可知，线性规划问题可能有各种不同的形式。根据实际问题的要求，目标函数可能是求最大化，也可能是求最小化；约束条件可以是“≤”形式、“≥”形式的不等式，也可以是等式。决策变量有时有非负限制，有时没有非负限制。这种多样性给讨论问题带来了不便。为了便于讨论，我们规定线性规划问题描述为如下的标准形式：
　　 这里我们假设
　　 以上模型的简写形式为
　　 用向量形式表达时，上述模型可以写为
　　 用矩阵形式表达时，上述模型可以写为
　　 我们称A为约束方程组的系数矩阵（m×n阶），一般情况下为正整数，分别表示约束条件的个数和决策变量的个数，C为价值向量，X为决策向量，通常为已知常数。
　　 实际上，具体问题的线性规划数学模型是各式各样的，需要把它们化成标准型，并借助于标准型的求解方法进行求解。
　　 以下就具体讨论如何把一般的线性规划模型化成标准型。
　　 (1)目标函数的转化。若原问题的目标函数是求最小化，即，这时只需要将目标函数的最小值变换为求目标函数的最大值，即。令就是将目标函数乘以后转化为如下最大化问题：
　　 (2)不等式约束转化为等式约束。不等式约束有两种情况：一是约束条件为“≤”形式的不等式，则在“≤”号的左边加入非负的松弛变量，把原“≤”形式的不等式转化为等式；另一种是约束条件为“≥”形式的不等式，则可在“≥”号的左边减去一个非负的剩余变量，把原“≥”形式的不等式转化为等式。同时相应的松弛变量或剩余变量在目标函数中的价值系数取值为O。
　　 (3)变量约束的转换。若原线性规划问题巾某个变量为无非负要求的变量，即有某一个变量z，取正值或负值都口以。这时为了满足标准型对变量的非负要求，可令，其中，将其代入原问题，即在原问题中将z，用两个非负变量之差代替。
　　 上述的标准型具有如下特点。
　　 (l)日标函数求最大值。
　　 (2)所求的决策变量都要求是非负的。
　　 (3)所有的约束条仵都是等式。
　　 (4)常数项为非负。
　　 综合以上的讨论，我们可以把任意形式的线性规划问题通过上述手段化成标准型的线性规划问题。
　　 例1.3将例1.1的线性规划数学模型化为标准型
　　 解：引进3个新的非负变量使不等式变为等式，标准型为
　　 例1.4试将如下线性规划问题化成标准型
　　 解：由于无限制，所以令，第一个约束不等式左端加上非负松弛变量。第二个约束小等式左端减去非负剩余变量，目标函数由于求最小化，所以令，同时将目标函数及约束条件巾的。换为，则可将上述线性规划问题化成如下的标准型：
　　 1.2线性规划问题的图解法及几何意义
　　 1.2.1线性规划问题解的概念
　　 在讨论线性规划问题的求解之前，要先了解线性规划问题解的概念。由前面讨论可知，线性规划问题的标准型如式(1.8)、式(1.9)、式(1.10)所示：
　　 1．可行解
　　 满足约束条件式(1.9)和式(1.10)的解称为线性规划问题的可行解；所有可行解的集合称为可行解集或可行域。
　　 2．最优解
　　 满足约束条件及目标函数(1.8)的可行解称为线性规划问题的最优解。
　　 3．基
　　 假设A是约束方程组的系教矩阵，其秩数为m，B是矩阵A中F列构成的非奇异子矩阵(B的行列式值不为0)，则称B是线性规划问题的一个基。这就是说，矩阵B由m个线性无关的列向量组成。不失一般性，可假设：为线性规划问题的一个基。