运筹学 第1章 线性规划 与单纯形 (第三版) 法 《运筹学》教材编写组编 第2节 线性规划问 题的几何意 义 钱颂迪制作 清华大学出版社
运筹学 （第三版） 《运筹学》教材编写组 编 清华大学出版社 第1章 线性规划 与单纯形 法 第2节 线性规划问 题的几何意 义 钱颂迪 制作
第1章线性规划与单纯形法 第2节线性规划问题的几何意义 21基本概念 22几个定理
第1章 线性规划与单纯形法 第2节线性规划问题的几何意义 • 2.1 基本概念 • 2.2 几个定理
21基本概念 1.凸集 2.凸组合 3.顶点
2.1 基本概念 1. 凸集 2. 凸组合 3. 顶点
1.凸集 设K是n维欧氏空间的一点集,若任意两点X(1)∈K, X2∈K的连线上的所有点aX()+(1-0)X(2)∈K, (0≤≤1);则称K为凸集 图1-7 X X1°
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中的阴影部分 4x1=16 是凸集。 4x2=12 Q2 X x··2 (c) 任何两个凸集的交集是凸集,见图1-7d
• 实心圆，实心球体，实心立方体等都是凸集， 圆环不是凸集。从直观上讲，凸集没有凹入 部分，其内部没有空洞。图1-7中的(a)(b)是凸 集，(c)不是凸集。 • 图1-2中的阴影部分 是凸集。 • 任何两个凸集的交集是凸集，见图1-7(d)
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 ，将它代入约束条件， 得到