上海交通大学：《线性规划与非线性规划》教学资源_第1章 线性规划与单纯形法 第2节 线性规划问题的几何意义

第1章线性规划与单纯形法

第1章 线性规划与单纯形法

第2节线性规划问题的几何意义 ·2.1基本概念 ·2.2几个定理

第2节线性规划问题的几何意义 • 2.1 基本概念 • 2.2 几个定理

2.1基本概念 1.凸集 2.凸组合 3.顶点

2.1 基本概念 1. 凸集 2. 凸组合 3. 顶点

1.凸集 ·设K是n维欧氏空间的一点集，若任意两点X1)∈K, X2)∈K的连线上的所有点aX1)+(1-a)X2)∈K, (0≤a≤1)则称K为凸集。 图1-7 X2 X1●X2 x 不2 (a) (b) (c) (d)

1.凸集 • 设K是n维欧氏空间的一点集，若任意两点X(1)∈K， X(2)∈K的连线上的所有点αX(1)+(1-α)X(2)∈K， (0≤α≤1)；则称K为凸集。 • 图1-7

实心圆，实心球体，实心立方体等都是凸 集，圆环不是凸集。从直观上讲，凸集没有 凹入部分，其内部没有空洞。图1-7中的(a)b) 是凸集，(c)不是凸集。 图1-2中的阴影部分 一x1+2x2=8 是凸集。 41=16 4x2=12 0 ·任何两个凸集的交集是凸集，见图1-7(d)

• 实心圆，实心球体，实心立方体等都是凸 集，圆环不是凸集。从直观上讲，凸集没有 凹入部分，其内部没有空洞。图1-7中的(a)(b) 是凸集，(c)不是凸集。 • 图1-2中的阴影部分 是凸集。 • 任何两个凸集的交集是凸集，见图1-7(d)

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的每一个分量是 将它代入约束条件，得到 则有