2.凸组合 。 设X(),X2),.,Xk是n维欧氏空间E中的k个点。 若存在μ1”μ2”，μk且0≤μ≤1，i=1,2,k, ∑4=1 i=l ·使X=μX+μ2X2++μkX o 则称X为X),X2),.,X)的凸组合。（当0<μ <1时，称为严格凸组合)
2. 凸组合 • 设X(1)，X(2)，…，X(k)是n维欧氏空间E中的k个点。 若存在μ1，μ2，…，μk，且0≤μi≤1, i=1,2,…，k; • 使X=μ1X(1)+μ2X(2)+…+μkX(k) • 则称X为X(1)，X(2)，…，X(k)的凸组合。（当0＜μi ＜1时，称为严格凸组合）. ∑ = = k i i 1 μ 1
3.顶点 。i 设K是凸集，X∈K;若X不能用不同的两点X)∈K 和X(2)∈K的线性组合表示为 X=aX1+(1-a)X2),(0<a<1) 。 则称X为K的一个顶点（或极点）。 一x1+2x2=8 ·图中0，Q1,2,3,4都是顶点。 —4x1=16 4x2=12 22
3. 顶点 • 设K是凸集，X∈K；若X不能用不同的两点X(1)∈K 和X(2)∈K的线性组合表示为 X=αX(1)+(1-α)X(2)，(0＜α＜1) • 则称X为K的一个顶点(或极点)。 • 图中0，Q1,2,3,4都是顶点
2.2几个定理 ·定理1若线性规划问题存在可行域，则其可 行域 2%马0 是凸集
2.2 几个定理 • 定理1 若线性规划问题存在可行域，则其可 行域 是凸集 ⎟⎟⎟⎠⎞ ⎜⎜⎜⎝⎛ = ∑ ≥= =nj jj j xbxPXD 1 0
证：为了证明满足线性规划问题的约束条件 ∑Pjx,=b,￥20，j=12,…,m j=1 的所有点（可行解）组成的集合是凸集， 只要证明D中任意两点连线上的点必然在D内 即可。 设 X()=(),x0),…,x0) Xe)=(),x2),.,x) 是D内的任意两点；X1)≠X(2)
证：为了证明满足线性规划问题的约束条件 ∑= =≥= n j jj j njxbxP 1 ",,2,1,0, 的所有点(可行解)组成的集合是凸集， 只要证明D中任意两点连线上的点必然在D内 即可。 设 是D内的任意两点；X(1)≠X(2) 。 ( ) () () ( ) ( ) () () () () ( ) T n T n X xx x X xx x 2 2 2 2 1 2 1 1 2 1 1 1 ,,, ,,, " " = =
则有 ∑Px9=b,x9≥0，j=1,2,n i ∑Px2=bx2≥0，j=1,2,,n i=l 令X=(X1,x2,,X)T为X,X2连线上的任 意一点，即 X=aX+(1-a)X2)(0≤a≤1) X的每一个分量是 x,=ax9+(1-a)x2) 将它代入约束条件，得到
() () () () ∑ ∑ = = =≥= =≥= n j jj j n j jj j njxbxP njxbxP 1 2 2 1 1 1 ,,2,1,0, ,,2,1,0, " " ( 1 ) ( 2 ) )1( jj j xx −+= αα x 令X=(x 1 ， x 2 ， … ， x n ) T 为 X(1),X(2)连线上的任 意一点，即 X= α X(1)+(1- α)X(2) (0≤α≤1) X的每一个分量是 将它代入约束条件，得到 则有