0<a<1 设X有P个正分量,则由(3)知,若x1=0,亦有鸡=x2=0,故x,x2)正分量不多 于P个,取a=mn、1x>0,g2=min!1x2>0再取Q=m,则0<Q<1,不 妨设Q=,令N=,(X-Qx①),则易见∈D,且其正分量个数不多于P1个,而 X=(1-Q)x)+Qx0。若X≥x(3,则pD=X-X10)20,AyD=0,且有X=X+y。而X13)的 正分量个数不多于P1个:若x≥X不成立,则Q2=mm|x>0<g3>0,取 x==a(x=.x),则X“的正分量个数不多于Pl,而x=x0+4-②x“,其中x 和x(4正分量的个数均不多于P-1,即比X少1 若x(3,x(4仍不是极点,则对之重复以上步骤,经有限步,必可将X表成 X aix+y (4) 其中a20,∑=1y∈D。故以下只需证Y=∑月y。若Y=0,只需取 B=0,i=1…,1。若y≠0,则B=∑y>0,取F=1y,则F∈。再注意到(4)对有界 集合D0亦成立,且此时y=0。(若D有界而Y≠0,则易证X+M∈D,令M→+∞。导致 D无界,矛盾)从而必有 ∑,≥0∑ 令月=丽,便有y=所-∑r,≥0,至此,定理获证 这样,由定理1,得到了(1)之可行解的一般表达式(2),且知若可行解集D有界, 其一般表达式为 X=>aX 其中a≥0.∑a=1x,=1…S,是D的极点,亦即X可表为极点的凸组合。 §2二分法 考虑如下线性规划问题 AX=b minf= CX (7) 这里4k是mxn矩阵,b是m维向量k=1,2 设D2={X|42X=b2,X≥0}127 (1 ) 0 1 (1) (2) X = X + − X    （3） 设 X 有 P 个正分量，则由（3）知，若 xj = 0 ，亦有 0 (1) (2) xj = xj = ，故 (1) (2) , j j x x 正分量不多 于 P 个，取 min{ | 0} (1) 1 (1) = i  i i x x x Q ， min{ | 0} (2) 2 (2) = i  i i x x x Q 再取 min{ , } Q = Q1 Q2 ，则 0  Q  1 ，不 妨设 Q = Q1 ，令 ( ) 1 (3) 1 (1) X QX Q X − − = ，则易见 X  D (3) ，且其正分量个数不多于 P-1 个，而 (3) (1) X = (1−Q)X + QX 。若 (3) X  X ，则 0, 0 (1) (3) (1) Y = X − X  AY = ，且有 (3) (1) X = X + Y 。而 (3) X 的 正 分 量 个数 不 多于 P-1 个；若 (3) X  X 不 成 立， 则 min{ | 0} 1, 3 0 (3) 3 (3) = x   Q  x x Q i i i , 取 ( ) 1 1 (3) 3 3 4 X Q X Q X − − = ，则 (4) X 的正分量个数不多于 P-1，而 (4) 3 (3) 3 X = Q X +（1− Q )X ，其中 (3) X 和 (4) X 正分量的个数均不多于 P-1，即比 X 少 1。 若 (3) X ， (4) X 仍不是极点，则对之重复以上步骤，经有限步，必可将 X 表成 X X Y I s I =  i + =1  （4） 其 中 I  0 ,  = =  S i i Y D 1 0  1, 。故以下只需证 = = l i i i Y y 1  。 若 Y=0 ，只需取 i l i  = 0, = 1,  , 。若 Y  0 ，则 0 1 =   = n i i  y ，取 Y Y  1 = ，则 Y  D0 。再注意到（4）对有界 集合 D0 亦成立，且此时 Y = 0 。（若 D 有界而 Y≠0，则易证 X + MY D ，令 M → + 。导致 D 无界，矛盾）从而必有 , 0, 1 1 1 =    = = = l i i i i l i Y iY   令 i = i ，便有 , 0 1 = =   = i l i i Y Y iY  ，至此，定理获证。 这样，由定理 1，得到了（1）之可行解的一般表达式（2），且知若可行解集 D 有界， 其一般表达式为 i S i X  iX = = 1  其中 X i S i S i i i 0, 1, , 1, , 1   = =  =   ，是 D 的极点，亦即 X 可表为极点的凸组合。 §2 二分法 考虑如下线性规划问题        =  = = min (7) 0 (6) (5) 2 2 1 1 f CX X A X b A X b 这里 AK 是 mk  n 矩阵， k b 是 mk 维向量,k=1,2 设 { | , 0 2 D2 = X A2X = b X  }