第六章分解算法 生产实际中遇到的线性规划问题常常是规模很大的,如果约束条件多到超过计算机容量 的程度,就会给求解造成困难。为了克服这一困难,对于大型问题,针对其具体结构,往往 可把它分解成几个较小问题来处理,这类方法称为分解算法。 §1分解定理 我们先介绍作为分解算法理论根据之一的分解定理。 对于线性规划问题 AX= b min CX 我们已定义可行解集D D={X|AX=b,X≥0} 相应地,定义集合D0 D={Y|AY=0,Y≥0} 以及集合D D={|AY=0,y≥0∑y=1 则易见是有界凸集,并且的极点个数有限,设它们为y,y2,…,y,常称为(1)的 基可行方向,而D中的元素则称为(1)的可行方向或极射向。 设B=(P,P2,…,Pn)是(1)的一个可行基,如果对某一非基变量x,其检验数x>0 系数≤0,=1…;m,令Y=(n,y2…y)2,满足 片=-B,=4,…m =0,k≠j,,…,mn 则Y≥0AY=yP+…+yP=-(BP+…+B1,P1)+P=-BBP+P=0,故 Y∈D,即为(1)的可行方向或极射向,并且Cy=-3<0,而=∑BY,便是(1)的 基可行方向,即y∈D。以上分析表明,若(1)的可行解无界,则它存在可行方向或极射 向 定理1如果D非空,则X∈D的充要条件是 x=∑aX+∑BF 这里x,=1…,s是D的极点,y,i=1,…l是(1)的基可行方向; a≥0,i=1…,S,∑a1=1,月≥0,=1,…,l 证明:充分性是显然的,故只需证必要性,任取X∈D,若X是D的极点,则(2)自 然成立,否则应有X,X(∈D,X(≠X2),使126 第六章 分解算法 生产实际中遇到的线性规划问题常常是规模很大的，如果约束条件多到超过计算机容量 的程度，就会给求解造成困难。为了克服这一困难，对于大型问题，针对其具体结构，往往 可把它分解成几个较小问题来处理，这类方法称为分解算法。 §1 分解定理 我们先介绍作为分解算法理论根据之一的分解定理。 对于线性规划问题       = CX X AX b min 0 （1） 我们已定义可行解集 D： D = {X | AX = b, X  0} 相应地，定义集合 D0 { | 0, 0} D0 = Y AY = Y  以及集合 D0 { | 0, 0, 1} 1 0 = =   = = n i i D Y AY Y y 则易见 D0 是有界凸集，并且 D0 的极点个数有限，设它们为 l Y ,Y , ,Y 1 2  ，常称为（1）的 基可行方向，而 D0 中的元素则称为（1）的可行方向或极射向。 设 ( , , , ) i1 i2 im B = P P  P 是（1）的一个可行基，如果对某一非基变量 j x ，其检验数  j  0 ， 系数 ij m 0,i i , ,i   = 1  ，令 T n Y ( y , y , , y ) = 1 2  ，满足      =  = = − = k m j i ij m y k j i i y y i i i 0, , , , 1 , , , 1 1    则 0, ( ) 0 1 1 1 1 1  = + + = − + + + = − + = − i j j j j Y AY y P ynPn i jPi i P P BB P P m m     ，故 Y  D0 ，即为（1）的可行方向或极射向，并且 CY = − j  0 ，而 Y Y − ij = 1  1 ，便是（1）的 基可行方向，即 Y  D0 。以上分析表明，若（1）的可行解无界，则它存在可行方向或极射 向。 定理 1 如果 D 非空，则 X D 的充要条件是 i l i i i S i X  iX  Y = = = + 1 1   (2) 这里 X i s i , = 1,  , 是 D 的极点，y i，i=1，l 是（1）的基可行方向； i  0,i =1,  ,S ， i l i S i i 1, 0, 1, , 1  =  =  =   证明：充分性是显然的，故只需证必要性，任取 X D ，若 X 是 D 的极点，则（2）自 然成立，否则应有 (1) (2) (1) (2) X , X  D, X  X ，使