2.凸组合 设X(),Ⅹ2,…,Ⅹ)是n维欧氏空间E中的k个点。 若存在μ1,μ2,…,μ,且0平<1,i=12灬,k 使X=μX()+2X(2.+X() 则称X为X(1),Ⅹ2),…,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.顶点 设K是凸集,Ⅹ∈K;若X不能用不同的两点X()∈K 和X(2)∈K的线性组合表示为 X=0X()+(1-0)X2),(0<0<1) 则称X为K的一个顶点(或极点) 图中0,Q1,23,4都是顶点 4x1=16 4x2=12
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都是顶点
22几个定理 定理1若线性规划问题存在可行域,则其可行 域 D=XP,x;=b,x;≥0 是凸集
2.2 几个定理 • 定理1 若线性规划问题存在可行域，则其可行 域 • 是凸集 = = = n j j j j D X P x b x 1 , 0
证:为了证明满足线性规划问题的约束条件 ∑ Px;=b,x;≥0,j=1,2,…,n 的所有点(可行解)组成的集合是凸集, 只要证明D中任意两点连线上的点必然在D内即可。 设 x(2)=(x(2),x2) 是D内的任意两点;X)≠X(2)
证：为了证明满足线性规划问题的约束条件 = = = n j Pj x j b x j j n 1 , 0, 1,2,, 的所有点(可行解)组成的集合是凸集， 只要证明D中任意两点连线上的点必然在D内即可。 设 是D内的任意两点；X (1)≠X(2) 。 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) T n T n X x x x X x x x 2 2 2 2 1 2 1 1 2 1 1 1 , , , , , , = =
则有 b,x)≥0,j=1,2,…,n b,x2)2≥0,j=1,2 令X=(x,x2,…,x)"为x,x2连线上的任意一点,即 X=ax+(1-a)x(0≤a≤1) X的每一个分量是x,=ax+(1-a)x2),将它代入约束条件, 得到
则有 ( ) ( ) ( ) ( ) = = = = = = n j j j j n j j j j P x b x j n P x b x j n 1 2 2 1 1 1 , 0, 1,2, , , 0, 1,2, , 令 X=(x1，x2，…，xn) T 为 x (1) ,x (2)连线上的任意一点，即 X=αX (1)+(1-α)X(2) (0≤α≤1) X 的每一个分量是 (1) (2) (1 ) j j j x =x + − x ，将它代入约束条件， 得到