2 多胞形的表示定理.ppt

《2 多胞形的表示定理.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、多胞形的表示定理例：K={xRnAx=b,x≥0}多胞形Rn中有限个闭半空间的交集.多面体非空有界的多胞形.polytopepolyhedronPOLYTOPESANDPOLYHEDRA定义设为凸集，若中不存在两个相异的点及某一实数使得则称为的极点．例：在平面上，闭三角形区域的极点是三角形的三个顶点；闭圆域的圆周上任一点都是极点；开圆域没有极点；原点是每个象限区域的惟一极点；整个平面没有极点.极点(ExtremePoint)多胞形的表示定理证：设若存在及使得则：若等号成立，必须且容易证明根据

2、定义可知为极点．例：证上的点均为极点．多胞形的表示定理定理2.2.1若K≠，则K必有极点.设K={xRnAx=b,x≥0}.定理2.2.2若y∈K，则y为K的极点当且仅当y的非零分量对应的列向量线性无关.推论2.2.3K的极点个数是有限的.多胞形的表示定理(ii)设K0={yRnAy=b,y≥0}.(i)若K≠，设K的全部极点为x1,x2,…,xk,k≥1.记有限点集{x1,x2,…,xk}的凸包为定义多胞形的表示定理定理2.2.4若K≠，则推论2.2.5若K≠，则K有界当且仅当

3、K0={0}.推论2.2.6多面体表示定理若K≠且有界，x1,x2,…,xk是K的全部极点,则x∈K当且仅当存在多胞形的表示定理方向(direction)设S是Rn中的非空凸集,dRn,d0,如果对任意xS，任意λ>0,总有x+λdS，则称d是S的一个方向.注：d(1)=λd(2)(λ>0)时，称d(1)和d(2)同方向.多胞形的表示定理极方向(extremedirection)如果方向d不能表示为两个不同方向的正的线性组合，则称d为S的极方向.d1d2d3方向d1和d3是极方向；方向

4、d2不是极方向.多胞形的表示定理定理2.2.7若K≠，则d为K的方向当且仅当d≥0,d≠0,Ad=0.推论2.2.8若K≠，则K为有界集当且仅当K没有方向.定理2.2.10多胞形表示定理若K≠且无界，x1,x2,…,xk是K的全部极点,d1,d2,…,dm是K的全部极点,则x∈K当且仅当存在多胞形的表示定理单纯形(Simplex)设x1,x2,…,xk∈Rn,则由x1,x2,…,xk所生成凸包为Rn中的多面体.如果x2-x1,x3-x1,…,xk-x1线性无关，则称Rn中的多面体H({x1

5、,x2,…,xk})是Rn中以x1,x2,…,xk为顶点的单纯形.注：Rn中的单纯形的顶点个数不超过n+1.注：R中的单纯形是单点集和线段；R2中的单纯形是单点集、线段和三角形；R3中的单纯形是单点集、线段、三角形和四面体；注：单纯形是一种重要的多面体.多胞形的表示定理设x1,x2,…,xk∈Rn,则(1)多面体H({x1,x2,…,xk})中的极点必定是某个xr(1≤r≤k)；(2)如果H({x1,x2,…,xk})是单纯形，则它的极点的全体就是顶点的全体.定理2.2.11多胞形的表示定理相邻

6、极点(adjacentextremepoint)、棱(edge)设S为Rn中的多胞形,x1,x2∈S为两个不同的极点，对于任何，如果存在x3,x4∈S使得x0为的内点，就一定有,则称x1和x2是S的相邻极点，此时，线段称为S的棱.单纯形中任何两个相异的顶点都是相邻的极点.定理2.2.12多胞形的表示定理单纯形中任何两个相异的顶点都是相邻的极点.定理2.2.12x1x2x3x1与x2是相邻极点；x2与x3是相邻极点；x1与x3不是相邻极点；例