第二篇线性规划 对于整个运筹学来说,线性规划是形成最早、最成熟的一个分支,它应用范围之广 是其它任何分支所不能比的,有人统计过,线性规划问题占去了世界上计算机的大部分 时间,它又是数学规划及运筹学其它一些分支的基础,故成为学习运筹学的首要课程。 在这一部分,除了较详细地介绍美国数学家 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,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,0m。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 + 构成一无关向量组，相应的方程组
∑ Pi,x, =b (4) 有唯一解(x,…x2),再令其余变量等于0,就得到Ax=b的一个基本解x 是Ax=b的一个解。且j≠(k=1,…,m)时,x=0,所以有 P=∑x P=b 即x也满足(4),由解的唯一性知必有x°=x。 注:当k<m时,x只能说是“可以看作基本解”,因为这时基本解是退化的,取0 值的基变量与非基变量表面无区别,它完全可能是用别的方法得到的“非基本解” 根据这个定理对基本解可以重新认识如下: 对于Ax=b的解x,若其非0分量对应的列向量线性无关,就可以视x为(2)的 基本解 定理3假定D是(2)的可行解集,X∈D,则X是D的顶点的充要条件为X可视为 (2)的基可行解。 证明设X的非0分量为x,…,x,对应的列向量为P…,P 必要性:用反证法设X是极点但X不能视为基可行解。从而P…,P相关。于 是必有不全为0的数h?…h,使 h,P=0 又因X∈D,所以有 P=b 于是有 (xi, tEh, )P, 令 =(x1x2,…x),其中x x,+ah,j= J≠1 X2=(x2,x2…x),其中x2=-h,j= ≠l1 并取E适当小,如E=min ,则有X1≥0,X2≥0,进而X∈D,X2∈D I<sk x≠X2。但是X=X+X2,此与x为D的极点矛盾,故X必可视为(2)的基可行 充分性:也用反证法,设X可视为(2)的基可行解,但不是D的顶点。则应有X∈D X2∈D,X≠X2,使 X=aX+(1-a)X2,0<a<1 即x=ax+(1-a)x,j=1,2,…;n
61 P x b j j i m j i = =1 (4) 有唯一解（ T i im x , , x ) 1 1 1 ，再令其余变量等于0，就得到 Ax b = 的一个基本解 1 x ，因 x 是 Ax b = 的一个解。且 ( 1, , ) k j i k m = 时， 0 j x = ，所以有 1 1 j j n m j j i i j j x P x P b = = = = 即 x 也满足（4），由解的唯一性知必有 0 1 x x = 。 注：当k<m时， x 只能说是“可以看作基本解”，因为这时基本解是退化的，取0 值的基变量与非基变量表面无区别，它完全可能是用别的方法得到的“非基本解”。 根据这个定理对基本解可以重新认识如下： 对于 Ax b = 的解 x ，若其非0分量对应的列向量线性无关，就可以视 x 为 (2) 的 基本解。 定理3 假定D是 (2) 的可行解集， X D ，则X是D的顶点的充要条件为X可视为 (2) 的基可行解。 证明 设X的非0分量为 k i i x , , x 1 ，对应的列向量为 1 , , k P P i i 。 必要性：用反证法 设X是极点但X不能视为基可行解。从而 1 , , k P P i i 相关。于 是必有不全为0的数 k hi hi , , 1 ，使 1 0 t t k i i t h P = = 又因 X D ，所以有 1 t t k i i t x P b = = 于是有 1 ( ) t t t k i i i t x h P b = = 令 1 1 1 1 1 2 ( , , , ) X x x x = n ，其中 1 , 0 , t t i i t j t x h j i x j i + = = 2 2 2 2 1 2 ( , , , ) X x x x = n ，其中 2 , 0 , t t i i t j t x h j i x j i − = = 并取 适当小，如 = t t i i t k h x 1 min ，则有 1 X 0， 2 X 0 ，进而 1 X D ， 2 X D ， 1 2 X X 。但是 1 1 1 2 2 2 X X X = + ，此与X为D的极点矛盾，故X必可视为 (2) 的基可行 解。 充分性：也用反证法，设X可视为 (2) 的基可行解，但不是D的顶点。则应有 1 X D ， 2 X D ， 1 2 X X ，使 1 2 X X X = + − (1 ) ,0 1 即 2 (1 ) , 1, 2, , j j j x x x j n = + − =
注意到a>0,1-a>0,x20.x20,则知当j≠,t=1,…k,时,x=x=x2=0 加之x,x2∈D,于是∑xP=∑xP=b=∑xP 从而∑(x1-x2)P=0 这说明P…P线性相关,因而X不是基可行解。矛盾,故充分性得证。 、基本定理 定理4若线性规划问题(2)有可行解,则必有基可行解 证明设x0是(2)的任一可行解。从x°出发用下面的方法可得一基可行解 不失一般性,可设x”的非0分量为x,x2…x,而x1=…=x=0,若P 线性无关,则x"即为基可行解。否则应有不全为0的h1h2,…h,使 hP=0 取适当小的E,及h1=…=b=0,可使 x土6h≥0,j=1…,kk+1…,n 而∑(x动)B=∑xP±E∑hP,这说明X=X+h,x2=X-h是 (2)的两个可行解,并且我们可选E=min 使(5)中前k个式子中至少有一个 取等号。于是可得到一个可行解X或X2,它的非0分量至少比X°少一个。如果这个 可行解还不是基可行解,则又可从它出发,重复以上步骤,得到新的可行解X3或X4, 其一的非0分量又减少一个。仿此作下去。若b≠0,上述过程最多进行到只有一个正分 量,比如x1,而得到基可行解(因b≠0故此时Ax=xB=b≠0,从而P≠0),若 b=0,则显然顶点X=0即为基可行解。 定理5如果线性规划问题(2〕有最优解,则存在一个基可行解是最优解 证明设x是(2)的最优解,即f(X)=∑cx是在可行解集D上的最小值 若x°不是基可行解,则对于定理4中作出的二个可行解X=X0+h,X2=X0-bh, 有 f(X=f(x)+f(ch),f(X)=f(r)-fch 从而有f(x)-f(X)=f(Eh)≥0,f(X2)-f(x)=-f(Eh)≥0,故必f(h)=0, 说明X和X2亦是最优解。按定理4的方法继续作下去,最后必得一基可行解X,它同 以上的X,X2一样,有f(x)=f(x),即基可行解X是最优解
62 注意到 1 2 0,1 0, 0, 0 j j − x x ，则知当 t j i , t=1, , k, 时， 1 2 0 jjj xxx = = = ， 加之 1 2 X X D , ，于是 1 1 n j j j x P = = 1 1 t t k i i t x P b = = 2 1 t t k i i t x P = = 从而 1 2 1 ( ) 0 t t t k i i i t x x P = − = 这说明 1 , , k P P i i 线性相关，因而X不是基可行解。矛盾，故充分性得证。 三、 基本定理 定理4 若线性规划问题 (2) 有可行解，则必有基可行解。 证明 设 0 x 是 (2) 的任一可行解。从 0 x 出发用下面的方法可得一基可行解。 不失一般性，可设 0 x 的非0分量为 1 2 , , , k x x x ，而 1 0 k n x x + = = = ，若 P Pk , , 1 线性无关，则 0 x 即为基可行解。否则应有不全为0的 1 2 , , , k h h h ，使 1 0 k j j j h P = = 取适当小的 ，及 1 0 k n h h + = = = ，可使 0, 1, , , 1, , j j x h j k k n = + (5) 而 1 1 1 ( ) n n n j j j j j j j j j j x h P x P h P = = = = ，这说明 1 2 X X h X X h = + = − , 是 (2) 的两个可行解，并且我们可选 = j j j k h x 0 1 min ，使（5）中前k个式子中至少有一个 取等号。于是可得到一个可行解 1 X 或 2 X ，它的非0分量至少比 X 少一个。如果这个 可行解还不是基可行解，则又可从它出发，重复以上步骤，得到新的可行解 3 X 或 4 X ， 其一的非0分量又减少一个。仿此作下去。若 b 0 ，上述过程最多进行到只有一个正分 量，比如 1 x ，而得到基可行解（ 因 b 0 故此时 0, Ax = x1P1 = b 从而 P1 0 ），若 b=0，则显然顶点X=0即为基可行解。 定理5 如果线性规划问题 (2) 有最优解，则存在一个基可行解是最优解。 证明 设 0 x 是 (2) 的最优解 ，即 1 ( ) n j j j f X c x = = 是f在可行解集D上的最小值。 若 0 x 不是基可行解，则对于定理4中作出的二个可行解 1 0 2 0 X X h X X h = + = − , ， 有 1 2 f X f X f h f X f X f h ( ) ( ) ( ), ( ) ( ) ( ) = + = − 从而有 1 2 f X f X f h f X f X f h ( ) ( ) ( ) 0, ( ) ( ) ( ) 0 − = − = − ，故必 f h ( ) 0 = ， 说明 1 X 和 2 X 亦是最优解。按定理4的方法继续作下去，最后必得一基可行解X *，它同 以上的 1 X , 2 X 一样，有f（X *）=f（X 0），即基可行解X * 是最优解