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

运筹学(第三版)《运筹学》教材编写组 编

第1章 线性规划 与单纯形 法第2节 线性规划问 题的几何意 义钱颂迪 制作

清华大学出版社

第1章 线性规划与单纯形法第2节线性规划问题的几何意义 2.1 基本概念 2.2 几个定理

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

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中的阴影部分 是凸集。

任何两个凸集的交集是凸集，见图1-7(d)

2. 凸组合 设X(1) ,X(2) ,…,X(k) 是n维欧氏空间E中的k个点。 若存在μ1,μ2,…,μk,且0≤μi≤1, i=1,2,…,k;

i 1

k

i

1

使X=μ1X(1)+μ2X(2)+…+μkX(k) 则称X为X(1),X(2),…,X(k)的凸组合。(当0<μi< 1时，称为严格凸组合).

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 域 若线性规划问题存在可行域，则其可行 D X x j 0

P xj j 1

n

j

b ,

是凸集

证：为了证明满足线性规划问题的约束条件

P xj j 1

n

j

b, x j 0, j 1,2, , n

的所有点(可行解)组成的集合是凸集， 只要证明D中任意两点连线上的点必然在D内即可。 设 X 1 x1 1 , x 21 , , x n1

X 2

x

2

1

, x 2 , , x 22 n

T

T

是D内的任意两点；X(1)≠X(2)。

则有

Pj x j1 b, x j1 0, j 1,2, , n j 1 n

n

Pj x j2 b, x j2 0, j 1,2, , n j 1T (1) (2)

令 X=(x1,x2, ,xn) 为 x ,x 连线上的任意一点，即 (1) (2) X=αX +(1-α)X (0≤α≤1) 1 2 x x j (1 ) x j X 的每一个分量是 j ,将它代入约束条件， 得到

j 1

n

Pj x j

n j 1 n

Pj x j1 1 x j2 Pj x j1

j 1 n

j 1

j 1

n

Pj x j2

Pj x j2

b b b bx j1 , x j2 0, 0,1 0 ,所以 xj≥0,j=1,2, ,n。 又因由此可见 X∈D,D 是凸集。 证毕。

引理 1 线性规划问题的可行解X=(x1,x2,…,xn)T为

基可行解的充要条件是X的正分量所对应的系数列向 量是线性独立的。

证: (1) 必要性由基可行解的定义

可知。 (2) 充分性若向量 P1,P2, ,Pk 线性独立， 则必有 k≤m;当 k=m 时，它们恰构成一个基，从而 X=(x1,x2, ,xk,0 0)为相应的基可行解。当 k<m 时， 则一定可以从其余的列向量中取出 m-k 个与

P1,P2, ,Pk 构成最大的线性独立向量组，其对应的解恰为 X, 所以根据定义它是基可行解。

定理2 线性规划问题的基可行解X对应于可行 D的顶点。 证：不失一般性，假设基可行解X的前m个分量为 正。故

Pj 1

m

j

xj b

(1-8)

现在分两步来讨论，分别用反证法。

(1) 若X不是基可行解， 则它一定不是可行域D的顶点

根据引理1,若X不是基可行解，则其正分量 所对应的系数列向量P1,P2,…,Pm线性相关， 即存在一组不全为零的数αi,i=1,2,…,m使得 α1P1+α2P2+…+αmPm=0 (1-9)

用一个μ>0的数乘(1-9)式再分别与(1-8)式 相加和相减，。

这样得到 (x1-μα1)P1+(x2-μα2)P2+…+(xm-μαm)Pm=b (x1+μα1)P1+(x2+μα2)P2+…+(xm+μαm)Pm=b 现取 X(1)=[(x1-μα1),(x2-μα2),…,(xm-μαm),0,…,0] X(2)=[(x1+μα1),(x2+μα2),…,(xm+μαm),0,…,0] 由X(1),X(2)可以得到X=(1/2)X(1)+(1/2)X(2), 即X是X(1),X(2)连线的中点

另一方面，当μ充分小时，可保证 xi±μαi≥0,i=1,2,…,m 即X(1),X(2)是可行解。 这证明了X 不是可行域 D 的顶点。

(2) 若X不是可行域D的顶点，则它一 定不是基可行解因为X不是可行域 D 的顶点，故在可行域D 中可找到不同的两点 X(1)=(x1(1),x2(1),…,xn(1))T X(2)=(x1(2),x2(2),…,xn(2))T 使 X=αX(1)+(1-α) X(2) , 0<α<1 设X是基可行解，对应向量组P1…Pm线性独 立。当j>m时，有xj=xj(1)=xj(2)=0,由于 X(1),X(2)是可行域的两点。应满足

j 1

m

1 b 与 Pj x j

j 1

m

2 b Pj x j

将这两式相减，即得

m j 1

Pj x 1 x 2 0 j j

因X(1)≠X(2) ,所以上式系数不全为零， 故向量组P1,P2,…,Pm 线性相关，与假设 矛盾。即X不是基可行解。

本文来源：https://www.bwwdw.com/article/dyvq.html