文档介绍：2. 凸集与凸函数? 多面集(体)理论介绍命题 若仿射集 M={ x∈R n |Ax=b }非空,则M中仿射无关的向量组的最大数目是 n +1-r( A ). 1,多面体的维数{ | ( ) , } { | } n i T in P x a x b i x Ax b ? ? ???? ? ??? 1 2 | | 1 2 | | , ( , ,..., ), ( , ,..., ) . T I TI A a a a b b b b ??其中I表示不等式的指标集矩阵向量考虑多面体 2. 凸集与凸函数若P的维数 dim (P)= k,则包含多面体 P的仿射集的最小维数为 k,由此可证 P中仿射无关的点的最大数目是 k+1. 特别的, dim (P )=n,此时称 P为满维数多面体. 1 2 1 2 {1, 2,..., }, ( , ,..., ) ( , ,..., ) ( , ) , { | ,( ) }; { | ,( ) } \ . m T m n T n m i T i i T i I m A a a a b b b b A b P I i I x P a x b I i I x P a x b I I ??? ?? ??? ?? ????? ???????设指标集,,则可用表示记下面定理表明:若P不是满维数多面体,则对于 P中所有点来说,至少有一个表示 . 凸集与凸函数 , , dim( ) ( , ) . E E Th P P P r A b n ? ?设为一非空多面体则具有相对内点并且. ( , ) , ) ( , ) ( , ) , ) ( , ) , { | , } E E I I E E I I n E E I I I I P A b A b A b A b A b A b P x A x b A x b ? ?? ? ???和分别称为的等式和不等式指标集记和(分别是由中对应的行组成的, 和(分别称为多面体表示的等式和不等式集则 2. 凸集与凸函数推论 多面体 P? Rn 是满维数的当且仅当 P有一个内点 2,多面体的面 , , { | } ( ). ( ( , )) . . TTT Df p x P H F H P x P p x P face p x p F P F F P F P ??? ??????? ??? ?设是的一个有效不等式相应的超平面记为则集合称为的一个面此时不等式简记称为面的一个表示若的面且则称为的一个正常面 { | } , P { | }, ( ( , )) P . n T n T T Df H x p x H x p x p x p ?? ? ?? ??????给定超平面若多面体则称不等式记为为的一个有效不等式?? ??2. 凸集与凸函数 1 2 | | 1 2 | | { | }, ( , ,..., ), ( , ,..., ) , , . , , : { | ( ) ( ), ( ) ( )} () , \ n T I TI n i T i T i F i F F F F P x Ax b A a a a b b b b I I I P F P F F x a x b