第二篇 线性规划对于整个运筹学来说，线性规划是形成最早、最成熟的一个分支，它应用范围之广是其它任何分支所不能比的，有人统计过，线性规划问题占去了世界上计算机的大部分时间，它又是数学规划及运筹学其它一些分支的基础，故成为学习运筹学的首要课程。
在这一部分，除了较详细地介绍美国数学家G B Dantzig于1947年首先提出的求解一般线性规划问题的理论和方法之外，对其新近的发展也尽量予以反映和评述，以期有个全面深入的认识。
线性规划的基本理论
§1 线性规划问题及其标准形式例1 有限资源利用问题.某工厂可以生产两种产品，各种资源的可供量以及每种产品所耗资源的数量及利润详见下表表一产品单位消耗
资源
A
B
资源限制
电（度）
设备（台时）
劳动力（小时）
单位利润（百元）
5
1
3
4
3
1
5
3
200
50
220
设A、B两种产品各生产x,x，则问题变为，求x,x，满足下列条件
使得利润
取得最大值。
一般地，用m资源（其限制为）生产n种产品，如果已知生产第j种单位产品消耗第i种资源的数量是,利润为，则问题归结为,求一组变量，满足条件。
(1)
使
达到最大
用矩阵形式表示即为
其中（以下同）
，，,
例2 平衡运输问题。设某种物资从m个发点运到n个收点其中发量分别为，收量分别为，收发平衡，即,已知从第i个发点到第j个收点的单位运费是。问应如何分配才能使总运费最小？
设自第i个发点到第j个收点的运量为。则应有
(2)
此问题亦可概括写为，求x，满足
(2)
例3 营养问题。有n种食物，每种含有m种营养成分，第j种食物每个单位含第i种营养成分为，已知每人每天对第i种营养成分的最低需要量为，第j种食物的单价是，试问一个消费者应如何选购食物才能即满足需要，又花费最小。
设选购第j种食物的数量为。则应有关系
（3）
此即
以上几个问题虽然来自不同方向,并且数学形式各异，但也有共同的地方：求一组非负变量，满足一些线性限制条件，并使一个线性函数取得极值，我们把具有上述特点的问题称为线性规划问题。其中的限制条件叫做约束条件。要求极值的函数叫作目标函数。并称为其标准形式。
以下说明（1）和（3）等其它形式均可化为标准形式。
若约束条件是线性不等式。
则它显然等价于
这里的称为松驰变量。同理不等式约束
等价于
这里的称为剩余变量。
此外因。故求极大值问题可化为求的极小值问题。
最后可能在某些问题中，有一个或几个变量没有非负性限制。这样的变量称为自由变量。若是这样的变量，则只要作代换
就可化成非负限制的情形了。另一个处理办法是通过所在的等式约束，把 解出，再代入其它约束中，把变量消去。
若记约束方程系数矩阵A的第j列为，即A=。则有
故称与列向量相对应。满足约束条件的解，即方程组的非负解称为可行解。取得所要求的极值的解称为最优解。相应的目标函数值（极值）称为最优值。所有可行解构成的集合D可表为：
称为可行解集或约束区域，它是有限个超平面和半空间的交集。
不失一般性，我们还可假定常数项列b0。
§2 两个变量的图解法
当一个线性规划问题只有两个变量时，可以采用图解法来求解。现以例1说明之。
显然可行解集D是一个凸五边形（图1斜线部分）
令（如，取k=120）作出此直线（图1中虚线）。则此直线上的点均使目标函数取同一数值k，平行移动此直线（相当于改变k的值）。则易见,它离开可行解集D前与之的最后交点（常为多边形的顶点）即为所求之最优解。此时最优值。
注意，最后交点可能不存在,如图2所示，当可行解集是无限区域时，便不存在。也可能是一个边（仍如图2所示是边），它们分别表示问题无最优解或有无穷多最优解。当然，特别地，如可行解集D是空集，自然不会有最优解了。
综合以上分析，可以看出，对于一个n=2的二维规划问题，它的可行解集D如果非空，则是一个凸多边形区域（有限或无限）。若它有最优解，则最优解一定可以在凸多边形的某一个顶点上达到。这正是一般线性规划基本定理所要表达的内容。
显然,时，图解法已不能用。但图解法为我们探索线性规划问题解的情形及最优解的特点提供了直观、有益的启示。
§3 线性规划基本定理凸集定义1 设和是n维欧氏空间中的任意二点，所有满足下列条件点z之集合
叫做以,为端点的线段，它是通常几何空间线段概念的推广。,叫作线段的端点，其余的点叫做线段的内点。
定义2 设S是中的一个点集，若对任意，有，则称S为一凸集。
换言之，凸集是指这样的集合，其中任意两点，连接线上的所有点也在这个集合里。例如通常所见的球体，长方体，就是三维空间的凸集。规定空集和均为凸集。
定义3 设凸集S，若S中不存在两个不同的点，，使
则称Z为凸集S的顶点或极点。
换句话说，一个凸集S的顶点不是S中任何线段的内点。
定理1 任何一个线性规划的可行解集合是一个凸集。
证明 设可行解集合为，任取，，则因 故而
故
。
这说明D是一个凸集。
有关凸集的理论在学习非线性规划时将进一步讨论。
基本解设A的秩为m，n>m 。A的任意一个m阶可逆子矩阵B，称为的一个基，变量，若它所对应的列包含在基B中，则称为B的基变量；否则，称之为非基变量。
设有一基B=（。相应地，记B的基变量为。则方程组或有唯一解，若再令其余非基变量等于0，就得到原方程组的一个解,
其余，
称这个解为的对应于基B的基本解。
显然一个线性规划问题的基本解的个数是有限的。它不会超过个。
若上述基本解中所有变量均非负，则称之为基可行解。相应的基B叫作可行基。
由于矩阵A的秩为m，故每一基本解非0分量的个数不超过m,若非0分量的个数恰好等于m，这个基本解被称之为非退化的，否则称之为退化的。如果一个线性规划问题的所有基本解都是非退化的，则称问题本身是非退化的，否则称之为退化问题。
下面二个定理反映了基本解的性质。
定理2 方程组的任一解是基本解的充要条件是的非0分量所对应的列向量线性无关。
证明 必要性：可由基本解的定义直接得到。
充分性：因秩A=m，故有km，因而可找到，使
构成一无关向量组，相应的方程组
(4)
有唯一解（，再令其余变量等于0，就得到的一个基本解，因是的一个解。且时，，所以有
即也满足（4），由解的唯一性知必有。
注：当k<m时，只能说是“可以看作基本解”，因为这时基本解是退化的，取0值的基变量与非基变量表面无区别，它完全可能是用别的方法得到的“非基本解”。
根据这个定理对基本解可以重新认识如下：
对于的解，若其非0分量对应的列向量线性无关，就可以视为的基本解。
定理3 假定D是的可行解集，，则X是D的顶点的充要条件为X可视为的基可行解。
证明 设X的非0分量为，对应的列向量为。
必要性：用反证法 设X是极点但X不能视为基可行解。从而相关。于是必有不全为0的数，使
又因，所以有
于是有
令
，其中
，其中
并取适当小，如，则有，,进而，，。但是，此与X为D的极点矛盾，故X必可视为的基可行解。
充分性：也用反证法，设X可视为的基可行解，但不是D的顶点。则应有，，，使
即
注意到，则知当,t=1,时，，加之，于是
从而
这说明线性相关，因而X不是基可行解。矛盾，故充分性得证。
基本定理定理4 若线性规划问题有可行解，则必有基可行解。
证明 设是的任一可行解。从出发用下面的方法可得一基可行解。
不失一般性，可设的非0分量为，而，若线性无关，则即为基可行解。否则应有不全为0的，使
取适当小的，及，可使
(5)
而，这说明是的两个可行解，并且我们可选，使（5）中前k个式子中至少有一个取等号。于是可得到一个可行解或，它的非0分量至少比少一个。如果这个可行解还不是基可行解，则又可从它出发，重复以上步骤，得到新的可行解或，其一的非0分量又减少一个。仿此作下去。若，上述过程最多进行到只有一个正分量，比如，而得到基可行解（ 因故此时从而），若b=0，则显然顶点X=0即为基可行解。
定理5 如果线性规划问题有最优解，则存在一个基可行解是最优解。
证明 设是的最优解,即是f在可行解集D上的最小值。若不是基可行解，则对于定理4中作出的二个可行解，有
从而有，故必，说明和亦是最优解。按定理4的方法继续作下去，最后必得一基可行解X*，它同以上的,一样，有f（X*）=f（X0），即基可行解X* 是最优解。
在这一部分，除了较详细地介绍美国数学家G B Dantzig于1947年首先提出的求解一般线性规划问题的理论和方法之外，对其新近的发展也尽量予以反映和评述，以期有个全面深入的认识。
线性规划的基本理论
§1 线性规划问题及其标准形式例1 有限资源利用问题.某工厂可以生产两种产品，各种资源的可供量以及每种产品所耗资源的数量及利润详见下表表一产品单位消耗
资源
A
B
资源限制
电（度）
设备（台时）
劳动力（小时）
单位利润（百元）
5
1
3
4
3
1
5
3
200
50
220
设A、B两种产品各生产x,x，则问题变为，求x,x，满足下列条件
使得利润
取得最大值。
一般地，用m资源（其限制为）生产n种产品，如果已知生产第j种单位产品消耗第i种资源的数量是,利润为，则问题归结为,求一组变量，满足条件。
(1)
使
达到最大
用矩阵形式表示即为
其中（以下同）
，，,
例2 平衡运输问题。设某种物资从m个发点运到n个收点其中发量分别为，收量分别为，收发平衡，即,已知从第i个发点到第j个收点的单位运费是。问应如何分配才能使总运费最小？
设自第i个发点到第j个收点的运量为。则应有
(2)
此问题亦可概括写为，求x，满足
(2)
例3 营养问题。有n种食物，每种含有m种营养成分，第j种食物每个单位含第i种营养成分为，已知每人每天对第i种营养成分的最低需要量为，第j种食物的单价是，试问一个消费者应如何选购食物才能即满足需要，又花费最小。
设选购第j种食物的数量为。则应有关系
（3）
此即
以上几个问题虽然来自不同方向,并且数学形式各异，但也有共同的地方：求一组非负变量，满足一些线性限制条件，并使一个线性函数取得极值，我们把具有上述特点的问题称为线性规划问题。其中的限制条件叫做约束条件。要求极值的函数叫作目标函数。并称为其标准形式。
以下说明（1）和（3）等其它形式均可化为标准形式。
若约束条件是线性不等式。
则它显然等价于
这里的称为松驰变量。同理不等式约束
等价于
这里的称为剩余变量。
此外因。故求极大值问题可化为求的极小值问题。
最后可能在某些问题中，有一个或几个变量没有非负性限制。这样的变量称为自由变量。若是这样的变量，则只要作代换
就可化成非负限制的情形了。另一个处理办法是通过所在的等式约束，把 解出，再代入其它约束中，把变量消去。
若记约束方程系数矩阵A的第j列为，即A=。则有
故称与列向量相对应。满足约束条件的解，即方程组的非负解称为可行解。取得所要求的极值的解称为最优解。相应的目标函数值（极值）称为最优值。所有可行解构成的集合D可表为：
称为可行解集或约束区域，它是有限个超平面和半空间的交集。
不失一般性，我们还可假定常数项列b0。
§2 两个变量的图解法
当一个线性规划问题只有两个变量时，可以采用图解法来求解。现以例1说明之。
显然可行解集D是一个凸五边形（图1斜线部分）
令（如，取k=120）作出此直线（图1中虚线）。则此直线上的点均使目标函数取同一数值k，平行移动此直线（相当于改变k的值）。则易见,它离开可行解集D前与之的最后交点（常为多边形的顶点）即为所求之最优解。此时最优值。
注意，最后交点可能不存在,如图2所示，当可行解集是无限区域时，便不存在。也可能是一个边（仍如图2所示是边），它们分别表示问题无最优解或有无穷多最优解。当然，特别地，如可行解集D是空集，自然不会有最优解了。
综合以上分析，可以看出，对于一个n=2的二维规划问题，它的可行解集D如果非空，则是一个凸多边形区域（有限或无限）。若它有最优解，则最优解一定可以在凸多边形的某一个顶点上达到。这正是一般线性规划基本定理所要表达的内容。
显然,时，图解法已不能用。但图解法为我们探索线性规划问题解的情形及最优解的特点提供了直观、有益的启示。
§3 线性规划基本定理凸集定义1 设和是n维欧氏空间中的任意二点，所有满足下列条件点z之集合
叫做以,为端点的线段，它是通常几何空间线段概念的推广。,叫作线段的端点，其余的点叫做线段的内点。
定义2 设S是中的一个点集，若对任意，有，则称S为一凸集。
换言之，凸集是指这样的集合，其中任意两点，连接线上的所有点也在这个集合里。例如通常所见的球体，长方体，就是三维空间的凸集。规定空集和均为凸集。
定义3 设凸集S，若S中不存在两个不同的点，，使
则称Z为凸集S的顶点或极点。
换句话说，一个凸集S的顶点不是S中任何线段的内点。
定理1 任何一个线性规划的可行解集合是一个凸集。
证明 设可行解集合为，任取，，则因 故而
故
。
这说明D是一个凸集。
有关凸集的理论在学习非线性规划时将进一步讨论。
基本解设A的秩为m，n>m 。A的任意一个m阶可逆子矩阵B，称为的一个基，变量，若它所对应的列包含在基B中，则称为B的基变量；否则，称之为非基变量。
设有一基B=（。相应地，记B的基变量为。则方程组或有唯一解，若再令其余非基变量等于0，就得到原方程组的一个解,
其余，
称这个解为的对应于基B的基本解。
显然一个线性规划问题的基本解的个数是有限的。它不会超过个。
若上述基本解中所有变量均非负，则称之为基可行解。相应的基B叫作可行基。
由于矩阵A的秩为m，故每一基本解非0分量的个数不超过m,若非0分量的个数恰好等于m，这个基本解被称之为非退化的，否则称之为退化的。如果一个线性规划问题的所有基本解都是非退化的，则称问题本身是非退化的，否则称之为退化问题。
下面二个定理反映了基本解的性质。
定理2 方程组的任一解是基本解的充要条件是的非0分量所对应的列向量线性无关。
证明 必要性：可由基本解的定义直接得到。
充分性：因秩A=m，故有km，因而可找到，使
构成一无关向量组，相应的方程组
(4)
有唯一解（，再令其余变量等于0，就得到的一个基本解，因是的一个解。且时，，所以有
即也满足（4），由解的唯一性知必有。
注：当k<m时，只能说是“可以看作基本解”，因为这时基本解是退化的，取0值的基变量与非基变量表面无区别，它完全可能是用别的方法得到的“非基本解”。
根据这个定理对基本解可以重新认识如下：
对于的解，若其非0分量对应的列向量线性无关，就可以视为的基本解。
定理3 假定D是的可行解集，，则X是D的顶点的充要条件为X可视为的基可行解。
证明 设X的非0分量为，对应的列向量为。
必要性：用反证法 设X是极点但X不能视为基可行解。从而相关。于是必有不全为0的数，使
又因，所以有
于是有
令
，其中
，其中
并取适当小，如，则有，,进而，，。但是，此与X为D的极点矛盾，故X必可视为的基可行解。
充分性：也用反证法，设X可视为的基可行解，但不是D的顶点。则应有，，，使
即
注意到，则知当,t=1,时，，加之，于是
从而
这说明线性相关，因而X不是基可行解。矛盾，故充分性得证。
基本定理定理4 若线性规划问题有可行解，则必有基可行解。
证明 设是的任一可行解。从出发用下面的方法可得一基可行解。
不失一般性，可设的非0分量为，而，若线性无关，则即为基可行解。否则应有不全为0的，使
取适当小的，及，可使
(5)
而，这说明是的两个可行解，并且我们可选，使（5）中前k个式子中至少有一个取等号。于是可得到一个可行解或，它的非0分量至少比少一个。如果这个可行解还不是基可行解，则又可从它出发，重复以上步骤，得到新的可行解或，其一的非0分量又减少一个。仿此作下去。若，上述过程最多进行到只有一个正分量，比如，而得到基可行解（ 因故此时从而），若b=0，则显然顶点X=0即为基可行解。
定理5 如果线性规划问题有最优解，则存在一个基可行解是最优解。
证明 设是的最优解,即是f在可行解集D上的最小值。若不是基可行解，则对于定理4中作出的二个可行解，有
从而有，故必，说明和亦是最优解。按定理4的方法继续作下去，最后必得一基可行解X*，它同以上的,一样，有f（X*）=f（X0），即基可行解X* 是最优解。
