第二篇线性规划 对于整个运筹学来说,线性规划是形成最早、最成熟的一个分支,它应用范围之广 是其它任何分支所不能比的,有人统计过,线性规划问题占去了世界上计算机的大部分 时间,它又是数学规划及运筹学其它一些分支的基础,故成为学习运筹学的首要课程。 在这一部分,除了较详细地介绍美国数学家 G B Dantzig于1947年首先提出的求解 一般线性规划问题的理论和方法之外,对其新近的发展也尽量予以反映和评述,以期有 个全面深入的认识 第一章线性规划的基本理论 §1线性规划问题及其标准形式 例1有限资源利用问题某工厂可以生产两种产品,各种资源的可供量以及每种产 品所耗资源的数量及利润详见下表 产品 单位消耗 资源限制 电(度) 设备(台时) 劳动力(小时) 3 5 220 单位利润(百元) 设A、B两种产品各生产x1,x2,则问题变为,求x1,x2,满足下列条件 5x1+3x,≤200 x1+x2≤50 3x,+5x,≤220 X1 使得利润 f(x1x2)=4x+3x2 取得最大值。 般地,用m资源(其限制为b,=1,…,m)生产n种产品,如果已知生产第j种单 位产品消耗第i种资源的数量是a。,利润为c,则问题归结为,求一组变量 满足条件 x ≥0,j=1,2 使 Ckxk
56 第二篇 线性规划 对于整个运筹学来说，线性规划是形成最早、最成熟的一个分支，它应用范围之广 是其它任何分支所不能比的，有人统计过，线性规划问题占去了世界上计算机的大部分 时间，它又是数学规划及运筹学其它一些分支的基础，故成为学习运筹学的首要课程。 在这一部分，除了较详细地介绍美国数学家G B Dantzig于1947年首先提出的求解 一般线性规划问题的理论和方法之外，对其新近的发展也尽量予以反映和评述，以期有 个全面深入的认识。 第一章 线性规划的基本理论 §1 线性规划问题及其标准形式 例1 有限资源利用问题.某工厂可以生产两种产品，各种资源的可供量以及每种产 品所耗资源的数量及利润详见下表 表一 产品 单位消耗 资源 A B 资源限制 电（度） 设备（台时） 劳动力（小时） 单位利润（百元） 5 1 3 4 3 1 5 3 200 50 220 设A、B两种产品各生产x 1 ,x 2 ，则问题变为，求x 1 ,x 2 ，满足下列条件 1 2 1 2 1 2 1 2 5 3 200 50 3 5 220 , 0 x x x x x x x x + + + 使得利润 1 2 1 2 f x x x x ( , ) 4 3 = + 取得最大值。 一般地，用m资源（其限制为 , 1, , i b i m = ）生产n种产品，如果已知生产第j种单 位产品消耗第i种资源的数量是 ij a ,利润为 j c ，则问题归结为,求一组变量 1 2 , , , n x x x ，满足条件。 1 , 1, 2, , 0, 1, 2, , . n ij j i j j a x b i m x j n = = = (1) 使 1 n k k k f c x = =
达到最大 用矩阵形式表示即为 Ax≤b x≥0 max =Cx 其中(以下同) 例2平衡运输问题。设某种物资从m个发点A1…,An运到n个收点B1…,Bn其中发 量分别为a,…an,收量分别为b…b,收发平衡,即∑a=∑b,已知从第个发 点到第j个收点的单位运费是c(=1…,m=1…m)。问应如何分配才能使总运费最 小? 设自第i个发点到第j个收点的运量为x(=1,…,mj=1,…,n)。则应有 Ci=ai x≥0 min 此问题亦可概括写为,求x,满足 Ax= b x≥ 0 例3营养问题。有n种食物,每种含有m种营养成分,第j种食物每个单位含第i种 营养成分为a,已知每人每天对第i种营养成分的最低需要量为b,第j种食物的单价 是C,,试问一个消费者应如何选购食物才能即满足需要,又花费最小 设选购第j种食物的数量为x(=1…,m)。则应有关系 o2, x1≥0,j=1,…,n (3) minf=∑cx
57 达到最大 用矩阵形式表示即为 0 max Ax b x f cx = (1) 其中（以下同） 11 12 1 21 22 2 1 2 n n m m mn a a a a a a A a a a = ， 1 2 n x x x x = ， 1 2 n b b b b = , 1 T 2 n c c c c = 例2 平衡运输问题。设某种物资从m个发点 1 , , A A m 运到n个收点 1 , , B B n 其中发 量分别为 1 , , m a a ，收量分别为 1 , , n b b ，收发平衡，即 1 1 m n i j i j a b = = = ,已知从第i个发 点到第j个收点的单位运费是 ( 1, , . 1, , ) ij c i m j n = = 。问应如何分配才能使总运费最 小？ 设自第i个发点到第j个收点的运量为 ( 1, , . 1, , ) ij x i m j n = = 。则应有 1 1 1 1 ( 1, 2, , ) ( 1, 2, , ) 0 min n ij i j m ij j i ij m n ij ij i j x a i m x b j n x f c x = = = = = = = = = (2) 此问题亦可概括写为，求x，满足 0 min Ax b x f cx = = (2 , ) 例3 营养问题。有n种食物，每种含有m种营养成分，第j种食物每个单位含第i种 营养成分为 ij a ，已知每人每天对第i种营养成分的最低需要量为 i b ，第j种食物的单价 是 j c ，试问一个消费者应如何选购食物才能即满足需要，又花费最小。 设选购第j种食物的数量为 ( 1, , ) j x j n = 。则应有关系 1 1 , 1, , 0 , 1, , min n ij j i j j n k k k a x b i m x j n f c x = = = = = （3） 此即
Ax≥b min f 以上几个问题虽然来自不同方向,并且数学形式各异,但也有共同的地方:求一组 非负变量,满足一些线性限制条件,并使一个线性函数取得极值,我们把具有上述特点 的问题称为线性规划问题。其中的限制条件叫做约束条件。要求极值的函数叫作目标函 数。并称(2)’为其标准形式 以下说明(1)和(3)等其它形式均可化为标准形式(2) 若约束条件是线性不等式 a1x1+…+anxn≤b 则它显然等价于 a1x1+…+amxn+y=b y≥ 这里的y称为松驰变量。同理不等式约束 b 等价于 a,x, J≥0 这里的y称为剩余变量。 此外因maxf(x)=-min[-∫(x)。故求f(x)极大值问题可化为求 f(x)=-f(x)的极小值问题 最后可能在某些问题中,有一个或几个变量没有非负性限制。这样的变量称为自由 变量。若x是这样的变量,则只要作代换x=l1-V1(1≥0,v1≥0) 就可化成非负限制的情形了。另一个处理办法是通过x1所在的等式约束,把x1解出, 再代入其它约束中,把变量x消去 若记约束方程系数矩阵A第j列为P,即A=(P,P2,…P)。则有 Ax=b分x1P+x2P xp=b 故称x与列向量P相对应。满足约束条件的解,即方程组的非负解称为可行解。取得 所要求的极值的解称为最优解。相应的目标函数值(极值)称为最优值。所有可行解构 成的集合D可表为: D={x|AX=b,X≥0} 称为可行解集或约束区域,它是有限个超平面和半空间的交集 不失一般性,我们还可假定常数项列b≥0 §2两个变量的图解法 当一个线性规划问题只有两个变量时,可以采用图解法来求解。现以例1说明之。 显然可行解集D是一个凸五边形(图1斜线部分)
58 0 min Ax b x f cx = (3) 以上几个问题虽然来自不同方向,并且数学形式各异，但也有共同的地方：求一组 非负变量，满足一些线性限制条件，并使一个线性函数取得极值，我们把具有上述特点 的问题称为线性规划问题。其中的限制条件叫做约束条件。要求极值的函数叫作目标函 数。并称 (2) 为其标准形式。 以下说明（1）和（3）等其它形式均可化为标准形式 (2) 。 若约束条件是线性不等式。 i in n i 1 1 a x a x b + + 则它显然等价于 1 1 0 i in n i i i a x a x y b y + + + = 这里的 i y 称为松驰变量。同理不等式约束 i in n i 1 1 a x a x b + + 等价于 1 1 0 i in n i i i a x a x y b y + + − = 这里的 i y 称为剩余变量。 此外因 max ( ) min[ ( )] f x f x = − − 。故求 f x( ) 极大值问题可化为求 1 f x f x ( ) ( ) = − 的极小值问题。 最后可能在某些问题中，有一个或几个变量没有非负性限制。这样的变量称为自由 变量。若 1 x 是这样的变量，则只要作代换 1 1 1 1 1 x u v u v = − ( 0, 0) 就可化成非负限制的情形了。另一个处理办法是通过 1 x 所在的等式约束，把 1 x 解出， 再代入其它约束中，把变量 1 x 消去。 若记约束方程系数矩阵A的第j列为 Pj ，即A= 1 2 ( , , , ) P P P n 。则有 Ax b x P x P x P b = + + + = 1 1 2 2 n n 故称 j x 与列向量 Pj 相对应。满足约束条件的解，即方程组的非负解称为可行解。取得 所要求的极值的解称为最优解。相应的目标函数值（极值）称为最优值。所有可行解构 成的集合D可表为： D x AX b X = = { | , 0} 称为可行解集或约束区域，它是有限个超平面和半空间的交集。 不失一般性，我们还可假定常数项列b 0。 §2 两个变量的图解法 当一个线性规划问题只有两个变量时，可以采用图解法来求解。现以例1说明之。 显然可行解集D是一个凸五边形（图1斜线部分）
A,,A4O A 令f(x,x2)=4x1+3x2=k(如,取k=120)作出此直线(图1中虚线)。则此直线上的 点均使目标函数取同一数值k,平行移动此直线(相当于改变k的值)。则易见,它离开 可行解集D前与之的最后交点(常为多边形的顶点)A3=(25,25)即为所求之最优解。 此时最优值f(25,25)=175。 +2x,<2 2x1+x2≥1 A 注意,最后交点可能不存在,如图2所示,当可行解集是无限区域时,max(2x1+x2)便 不存在。也可能是一个边(仍如图2所示min(2x1+x2)是A42边),它们分别表示问 题无最优解或有无穷多最优解。当然,特别地,如可行解集D是空集,自然不会有最优 解了。 综合以上分析,可以看出,对于一个n=2的二维规划问题,它的可行解集D如果非空, 则是一个凸多边形区域(有限或无限)。若它有最优解,则最优解一定可以在凸多边形 的某一个顶点上达到。这正是一般线性规划基本定理所要表达的内容 显然,n>3时,图解法已不能用。但图解法为我们探索线性规划问题解的情形及 最优解的特点提供了直观、有益的启示。 §3线性规划基本定理 、凸集 定义1设Z和Z2是n维欧氏空间R中的任意二点,所有满足下列条件点z之集合 Z=az+(1-a)z,0≤a≤1
59 1 2 3 4 A A A A O : 令 1 2 1 2 f x x x x k ( , ) 4 3 = + = （如，取k=120）作出此直线（图1中虚线）。则此直线上的 点均使目标函数取同一数值k，平行移动此直线（相当于改变k的值）。则易见,它离开 可行解集D前与之的最后交点（常为多边形的顶点） 3 A = (25, 25) 即为所求之最优解。 此时最优值 f (25, 25) 175 = 。 注意，最后交点可能不存在,如图2所示，当可行解集是无限区域时， max(2 ) 1 2 x x + 便 不存在。也可能是一个边（仍如图2所示 min(2 ) 1 2 x x + 是 AA1 2 边），它们分别表示问 题无最优解或有无穷多最优解。当然，特别地，如可行解集D是空集，自然不会有最优 解了。 综合以上分析，可以看出，对于一个n=2的二维规划问题，它的可行解集D如果非空， 则是一个凸多边形区域（有限或无限）。若它有最优解，则最优解一定可以在凸多边形 的某一个顶点上达到。这正是一般线性规划基本定理所要表达的内容。 显然, n 3 时，图解法已不能用。但图解法为我们探索线性规划问题解的情形及 最优解的特点提供了直观、有益的启示。 §3 线性规划基本定理 一、 凸集 定义1 设 1 Z 和 2 Z 是n维欧氏空间 n R 中的任意二点，所有满足下列条件点z之集合 1 2 Z Z Z = + − (1 ) ,0 1 D A3 A2 1 x 2x1 + x2 1 A1 A2 图2 0 2 2 x 2 1 1 − x1 + 2x2 2 2 x 1 x A1 A4 20 10 0 10 20 图1
叫做以Z,Z为端点的线段,它是通常几何空间线段概念的推广。z,Z2叫作线段的 端点,其余的点叫做线段的内点。 定义2设S是R中的一个点集,若对任意z∈S,z2∈S,有 Z=az+(1-a)z2∈S,0≤a≤1,则称S为一凸集 换言之,凸集是指这样的集合,其中任意两点Z,Z2连接线上的所有点也在这个 集合里。例如通常所见的球体,长方体,就是三维空间的凸集。规定空集Φ和R"均为 凸集。 定义3设Z∈凸集S,若S中不存在两个不同的点Z,Z2,使 Z=az+(1-a)z2,0<a<1 则称Z为凸集S的顶点或极点 换句话说,一个凸集S的顶点不是S中任何线段的内点。 定理1任何一个线性规划的可行解集合是一个凸集 证明设可行解集合为D={2|AZ=b,Z≥0},任取Z,z2∈D,则因 Z1≥0,z2≥0,0≤a≤1故az+(1-a)z2≥0而 Aaz +(1-a)z]=AaZ+(1-a)AZ=ab+(l-ab=b 故 az+(1-a) 这说明D是一个凸集。 有关凸集的理论在学习非线性规划时将进一步讨论。 、基本解 设A的秩为m,n>m。A的任意一个m阶可逆子矩阵B,称为(2)的一个基,变量x, 若它所对应的列P包含在基B中,则称x,为B的基变量:否则,称之为非基变量。 设有一基B=(P,…P)。相应地,记B的基变量为xB=(x…x)。则方程组 Bx=b或∑Px4=b有唯一解xB=Bb=(x10…x),若再令其余非基变量等 于0,就得到原方程组Ax=b的一个解x° x,k=1,2,…,m其余x1=0 称这个解为(2)的对应于基B的基本解。 显然一个线性规划问题的基本解的个数是有限的。它不会超过cm个 若上述基本解中所有变量均非负,则称之为基可行解。相应的基B叫作可行基 由于矩阵A的秩为m,故每一基本解非0分量的个数不超过m,若非0分量的个数恰好等 于m,这个基本解被称之为非退化的,否则称之为退化的。如果一个线性规划问题的所 有基本解都是非退化的,则称问题本身是非退化的,否则称之为退化问题 下面二个定理反映了基本解的性质。 定理2方程组Ax=b的任一解x°是基本解的充要条件是x0的非0分量 x,x,…x所对应的列向量P,…P线性无关 证明必要性:可由基本解的定义直接得到 充分性:因秩A=m,故有k≤m,因而可找到Pn,…,P,使 ,…,P.,P 构成一无关向量组,相应的方程组
60 叫做以 1 Z , 2 Z 为端点的线段，它是通常几何空间线段概念的推广。 1 Z , 2 Z 叫作线段的 端点，其余的点叫做线段的内点。 定义2 设S是 n R 中的一个点集，若对任意 1 2 Z S Z S , ，有 1 2 Z Z Z S = + − (1 ) ,0 1 ，则称S为一凸集。 换言之，凸集是指这样的集合，其中任意两点 1 Z ， 2 Z 连接线上的所有点也在这个 集合里。例如通常所见的球体，长方体，就是三维空间的凸集。规定空集 和 n R 均为 凸集。 定义3 设 Z 凸集S，若S中不存在两个不同的点 1 Z ， 2 Z ，使 1 2 Z Z Z = + − (1 ) ,0 1 则称Z为凸集S的顶点或极点。 换句话说，一个凸集S的顶点不是S中任何线段的内点。 定理1 任何一个线性规划的可行解集合是一个凸集。 证明 设可行解集合为 D Z AZ b Z = = { | , 0} ，任取 1 Z ， 2 Z D ，则因 1 2 Z Z 0, 0,0 1 故 1 2 Z Z + − (1 ) 0 而 1 2 1 2 A Z Z A Z AZ b b b [ (1 ) ] (1 ) (1 ) + − = + − = + − = 故 1 2 Z Z D + − (1 ) 。 这说明D是一个凸集。 有关凸集的理论在学习非线性规划时将进一步讨论。 二、 基本解 设A的秩为m，n>m 。A的任意一个m阶可逆子矩阵B，称为 (2) 的一个基，变量 j x ， 若它所对应的列 Pj 包含在基B中，则称 j x 为B的基变量；否则，称之为非基变量。 设有一基B=（ , , ) 1 k Pi Pi 。相应地，记B的基变量为 T B i im x (x , x ) = 1 。则方程组 Bx b B = 或 P x b k k i m k i = =1 有唯一解 T B i im x B b (x , x ) 1 0 0 = − = 1 ，若再令其余非基变量等 于0，就得到原方程组 Ax b = 的一个解 0 x ： , 1,2, , , 0 x x k m k k i = i = 其余 0 j x = ， 称这个解为 (2) 的对应于基B的基本解。 显然一个线性规划问题的基本解的个数是有限的。它不会超过 m n c 个。 若上述基本解中所有变量均非负，则称之为基可行解。相应的基B叫作可行基。 由于矩阵A的秩为m，故每一基本解非0分量的个数不超过m,若非0分量的个数恰好等 于m，这个基本解被称之为非退化的，否则称之为退化的。如果一个线性规划问题的所 有基本解都是非退化的，则称问题本身是非退化的，否则称之为退化问题。 下面二个定理反映了基本解的性质。 定理2 方程组 Ax b = 的任一解 0 x 是基本解的充要条件是 0 x 的非0分量 0 0 0 , , 1 2 k i i i x x x 所对应的列向量 1 , , k P P i i 线性无关。 证明 必要性：可由基本解的定义直接得到。 充分性：因秩A=m，故有k m，因而可找到 1 , , i i k m P P + ，使 1 1 , , , , , i i i i k k m P P P P + 构成一无关向量组，相应的方程组