线性规划与单纯形法-第2节-清华大学运筹学第三版ppt演示文稿.ppt

文档介绍：运筹学
（第三版）
《运筹学》教材编写组 编
清华大学出版社
第1章 线性规划与单纯形法  第2节 线性规划问题的几何意义
钱颂迪 制作
1
第1章 线性规划与单纯形法 第2节线性规划问题的几何意义
基本概念
几个定理
2
基本概念
凸集
凸组合
顶点
3

设K是n维欧氏空间的一点集，若任意两点X(1)∈K，X(2)∈K的连线上的所有点αX(1)+(1-α)X(2)∈K，(0≤α≤1)；则称K为凸集。
图1-7
4
实心圆，实心球体，实心立方体等都是凸集，圆环不是凸集。从直观上讲，凸集没有凹入部分，其内部没有空洞。图1-7中的(a)(b)是凸集，(c)不是凸集。
图1-2中的阴影部分
是凸集。
任何两个凸集的交集是凸集，见图1-7(d)
5
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时，称为严格凸组合）.
6
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都是顶点。
7
几个定理
定理1 若线性规划问题存在可行域，则其可行域
是凸集
8
证：为了证明满足线性规划问题的约束条件
的所有点(可行解)组成的集合是凸集，
只要证明D中任意两点连线上的点必然在D内即可。
设
是D内的任意两点；X(1)≠X(2)。
9
10