下载掌阅APP，畅读海量书库
立即打开
下面以实例来归纳线性规划模型特征。
例2.1
某工厂近期要安排生产甲、乙两种产品，产品甲需要用原料A，产品乙需要用原料B，由于两种产品都在一个设备上生产，且设备使用时间有限，管理者必须合理安排两种产品的产量，使得在资源有限的条件下获得最大的利润。因此，这个问题的决策目标是收益的最大化。研究者根据这个目标需要收集以下相关数据：
（1）工厂两种原料存量以及可用设备工时数；
（2）甲、乙两种产品的单位产品需要的原料和设备工时数；
（3）甲、乙两种产品的单位产品利润。
这些数据可以通过调研或估算得出，如表2.1所示。
表2.1
为建立模型，引入变量如下：
x 1 ——产品甲的数量；
x 2 ——产品乙的数量；
z ——利润。
由表2.1最后一行知：
z ＝4 x 1 ＋3 x 2
目标是如何确定 x 1 和 x 2 ，使得利润 z 最大，同时需要满足资源约束。
对于原料A和原料B，有：
x 1 ≤6，2 x 2 ≤8
对于设备工时，有：
2 x 1 ＋3 x 2 ≤18
此外，甲、乙两种产品数量不可能是负值，因此，有如下对变量的非负约束：
x 1 ≥0， x 2 ≥0
于是，问题的数学模型现在可以用代数式表述如下：
max z ＝4 x 1 ＋3 x 2
满足：
从以上过程我们可以归纳出根据实际问题建立线性规划模型的步骤：
（1）根据实际需求或技术要求确定决策目标和收集相关数据。
（2）确定要做出的决策，引入决策变量。
（3）确定对这些决策的约束条件和目标函数。
例2.2
某饲料公司用玉米、红薯中原料配制一种混合饲料，各种原料包含的营养成分和采购成本都不同，需要确定混合饲料中的各种原料数量，使得饲料能够以最低成本达到一定的营养要求。研究者根据这一目标收集到的有关数据如表2.2所示。
表2.2
为建立线性规划模型，引入变量如下：
x 1 ＝混合饲料中玉米的数量；
x 2 ＝混合饲料中红薯的数量；
目标函数 z ＝0.8 x 1 ＋0.5 x 2 ，表示产量的成本函数，即如何确定 x 1 ， x 2 使得成本 z ＝0.8 x 1 ＋0.5 x 2 最低且满足最低营养要求的约束，这些约束条件是：
碳水化合物要求：8 x 1 ＋4 x 2 ≥20
蛋白质物要求：3 x 1 ＋6 x 2 ≥18
维他命物要求： x 1 ＋5 x 2 ≥16
另外非负约束： x 1 ≥0， x 2 ≥0
因此这个问题的线性规划模型为：
min z ＝0.8 x 1 ＋0.5 x 2
其中“s.t.”是“subject to”的缩写，意思是“受约束于……”。
从以上的几个例子可以看出，线性规划问题有如下共同特征：
（1）每个问题都用一组决策变量，这组决策变量的值都代表一个具体方案。
（2）有一个衡量决策方案优劣的函数，它是决策变量的线性函数，称为目标函数。按问题不同，要求目标函数实现最大化或最小化。
（3）存在一些约束条件，这些约束条件包括①函数约束；②决策变量的非负约束。
根据上文分析，线性规划的一般形式为：
线性规划问题有各种不同的形式。目标函数有的要求max，有的要求min；约束条件可以是“≤”，也可以是“≥”形式的不等式，还可以是等式。决策变量一般是非负约束，但也允许在（－∞，∞）范围内取值，即无约束。将这种多形式的数学模型统一变换为标准形式。这里规定的标准形式为：目标函数的要求是max，约束条件的要求是等式，决策变量的要求是非负约束。在标准型式中规定各约束条件的右端项 b i ≥0，否则等式两端乘以“－1”。
用向量和矩阵符号表述时为：
其中： C ＝（ c 1 ， c 2 ，…， c n ）
用矩阵描述时为：
其中：
称 A 为约束条件的 m × n 维系数矩阵，一般 m ＜ n ， m ， n ＞0； b 为资源向量； C 为价值向量； X 为决策变量向量。
化标准型的方法如下：
（1）若要求目标函数实现最小化，即min z ＝ CX 。这时只需将目标函数最小化变换求目标函数最大化，即令 z′ ＝－ z ，于是得到max z′ ＝－ CX 。这就同标准型的目标函数的形式一致了。
（2）约束方程为不等式。这里有两种情况：一种是约束方程为“≤”不等式，则可在“≤”不等式的左端加入非负松弛变量 x j ，把原“≤”不等式变为等式；另一种是约束方程为“≥”不等式，则可在“≥”不等式的左端减去一个非负剩余变量 x j （也可统称为松弛变量），把不等式约束条件变为等式约束条件。
（3）若变量约束中： x j ≤0，则令 x j ′ ＝－ x j ， x j ′ ≥0；若 x j 无约束，则令 x j ＝ x j ′ － x j ″ ，其中 x j ′ ， x j ″ ≥0，用新的非负变量分别代替原来的变量。
例2.3 将下述线性规划化标准型。
解：按上述规则化标准型如下：
用 x 3 ＝ x 4 － x 5 ，其中 x 4 ， x 5 ≥0；
在第一个约束不等式≤号的左端加入松弛变量 x 6 ；
在第二个约束不等式≥号的左端减去剩余变量 x 7 ；
令 z′ ＝－ z ，即可得到该问题的标准型：
max z′ ＝ x 1 －2 x 2 ＋3（ x 4 － x 5 ）＋0 x 6 ＋0 x 7
在讨论线性规划问题的求解前，先要了解线性规划解的概念。一般线性规划问题的标准型为：
定义2.1
满足上式约束条件的解
，称为线性规划问题的可行解。全部可行解的集合称为可行域。
定义2.2 使目标函数达到最大值的可行解称为最优解，对应的目标函数值称为最优值。
定义2.3 设 A m×n （ m ≤ n ）为约束方程组的系数矩阵，其秩为 m ． B m×m 是矩阵 A 中的子矩阵且是满秩阵，则称 B 是线性规划问题的一个基（基矩阵）。
定义2.4 在约束方程组的关系矩阵中，设 B ＝（ P 1 ， P 2 ，…， P m ），其列向量 P j （ j ＝1，2，…， m ）为基向量。则基向量 P j 对应的变量 x j 称为基变量，其他的变量称为非基变量。令所有非基变量 x m ＋1 ， x m ＋2 ，…， x n ＝0，得到约束方程 BX B ＝ b ，由克莱姆法则可得到唯一解 X B ＝（ x 1 ， x 2 ，…， x m ） T ，则称由约束方程确定的唯一解 X ＝（ x 1 ， x 2 ，…， x m ，0，…，0） T 为线性规划问题的基解。满足约束条件的基解称为基可行解。
若基变量中至少有一个分量为零，则称为退化的基可行解。由此可知，退化基可行解中的非零分量一定小于 m ，非退化解中非零分量一定等于 m ，若有关线性规划问题的所有基可行解都是非退化解，则该问题为非退化线性规划问题；否则，称为退化线性规划问题。各类解的关系如图2.1所示。
图2.1
例2.4 将例2.1转化为标准型，并找出一组基、基变量、基解、基可行解和可行基。
解：显然，标准型为：
max z ＝4 x 1 ＋3 x 2 ＋0 x 3 ＋0 x 4 ＋0 x 5
由此，约束方程的系数矩阵为
矩阵秩不大于3，而
是一个3阶的满秩阵，故（p
3
，p
4
，p
5
）是一个基，x
3
，x
4
，x
5
是基变量，x
1
，x
2
是非基变量。令x
3
＝6，x
4
＝8，x
5
＝18，则x＝（0，0，6，8，18）T是一个基解。因该基解中所有变量取值为非负，故又是基可行解，对应的基（p
3
，p
4
，p
5
）是一个可行基。
图解法简单直观，有助于了解线性规划问题求解的基本原理。现用例2.1来说明图解法。例2.1的线性规划问题是：
max z ＝4 x 1 ＋3 x 2
首先建立 x 1 Ox 2 坐标平面。由非负约束 x 1 ≥0、 x 2 ≥0可知，所有可行解的集合（称为可行域）应在第一象限。然后，要逐个地查看每个函数约束允许的解，最后再综合考虑所有的约束条件，寻找所有单个约束条件允许解的交集，确定可行域，如图2.2的阴影部分所示。
图2.2
在图中做出梯度方向
，在可行域做出一条直线垂直
，当该直线沿着梯度方向平移时，目标函数值增大；否则，沿着反梯度方向平移时，目标函数值减小。本题是求最大值，所以该直线沿梯度方向平移，离开可行域的最后一点（6，2）为最优解。
由上例可以看出，线性规划问题的最优解出现在可行域的一个顶点上，此时线性规划问题有唯一最优解。但有时线性规划问题还可能出现有无穷多个最优解，无有限最优解，甚至没有可行解的情况。
（1）无穷多最优解。
若将上例中的目标函数变为求max z ＝4 x 1 ＋6 x 2 ，则目标函数与等值区域边界线2 x 1 ＋3 x 2 ＝18平行，线段 BC 上的任意一点都使 z 取得相同的最大值，此时线性规划问题有无穷多最优解（见图2.3）。
图2.3
（2）无界解。
考虑下列线性规划问题：
max z ＝ x 1 ＋ x 2
确定可行域（如图2.4阴影部分所示），可以看出可行域无界，为求最优解做等值线 x 1 ＋ x 2 ＝ k ，当 k 由小变大时，等值线沿梯度方向（1，1） T 平行移动，不论 k 值增大多少，等值线上总有一段位于可行域内，因此目标函数无上界，该问题无有限最优解。
图2.4
事实上，可行域无界时线性规划问题有时也有有限最优解，如上例中当目标函数变为max z ＝－ x 1 － x 2 时，线性规划问题有时也有有限最优解 x 1 ＝3， x 2 ＝0，即目标函数在（3，0）点处取得最大值。
（3）无可行解。
如果在例2.1的线性规划问题中增加一个约束条件 x 1 ＋ x 2 ＞12，则该问题的可行域为空集，即没有一个点满足所有的约束条件，问题无可行解，所以也不存在最优解。
图解法适用于求解只有两个决策变量的线性规划问题，具体步骤如下：
（1）画出每个函数约束的约束边界，用原点（或其他不在边界上的点）判断直线的哪一边是约束条件所允许的。
（2）找出所有约束条件都同时满足的区域，即可行域。
（3）给目标函数一个特定的值 k ，画出目标函数等值线，当 k 变化时，目标函数等值线平行移动；对于目标函数最小化的问题，找出目标函数减少的方向，目标函数最后离开可行域的点是最优解。
（4）从图解法可以看出，线性规划问题的可行域非空时，它是一个凸多边形，若线性规划问题存在最优解，它一定在可行域的某个顶点得到，若有唯一最优解，则一定在可行域的顶点处得到；若两个顶点同时达到最优解，则两个顶点之间线段上的任意一点都是最优解。