凸多面形分解定理

凸多面形分解定理(polyhedral decomposition theorem)亦稱法爾卡斯-閔科夫斯基-外爾定理，是反映線性不等式組解集結構的一個命題。

基本介紹

• 中文名：凸多面形分解定理
• 外文名：polyhedral decomposition theorem
• 所屬學科：數學
• 所屬問題：組合學（組合多面形)
• 別稱：法爾卡斯-閔科夫斯基-外爾定理

基本介紹

凸多面形分解定理是反映線性不等式組解集結構的一個命題，由非齊次聯立不等式組之解集構成的凸多面形可做如下分解：P=M+K(“+”的意義，參見下文“多面體之和”)，其中M為凸多面體，K為由齊次聯立不等式組之解集構成的凸多面錐。此定理把凸多面形分解為相對簡單的凸多面體和凸多面錐，從而給多面形的處理帶來方便。例如，線性規劃理論的基本定理是得益於此分解定理。

多面體之和

多面體之和是一類多面體運算，多面體P₁和P₂之和，記為

多面形的分解定理使用的正是此類運算。

相鄰多面體的和是相鄰多面體的一種合成，即由相鄰多面體導出的一個多面體，兩個相鄰多面體，剔除其所有的公共點後，所形成的第三個多面體，稱為兩個相鄰多面體的和。

相關介紹

當凸多面形為滿足線性不等式組

的解集時，稱為凸多面形的法式描述。

當凸多面形為滿足線性約束

的解集時，稱為凸多面形的典式描述。這是線性規劃通常採用的描述形式，在這裡，凸多面形為兩部分的交集：其一為k個線性獨立的超平面之交集;其二為n個半空間之交集。

更一般地，當凸多面形為滿足線性約束

之解集時，稱為凸多面形的剛性約束。

對於凸多面形的典式描述，把決定線性方程組的係數矩陣A稱為凸多面形的約束矩陣。以A的列為向量，其m個線性獨立向量，稱為凸多面形的基。由基所確定的多面形的點，被稱為極點。若由基求得線性方程組的解滿足第二部分約束： ，則稱此基為凸多面形的可行基，這樣的解稱為基礎可行解，可行基的討論構成線性規劃及其單純形方法的基礎。