裝填多面體是一類組合構形，指由裝填問題的可行解集的凸包所形成的多面體。
基本介紹
- 中文名：裝填多面體
- 外文名：packing polytope
- 適用範圍：數理科學
簡介,性質,推廣,
簡介
裝填多面體是一類組合構形，指由裝填問題的可行解集的凸包所形成的多面體。
對於有限集
，E為I的所有子集所形成的簇，並且記
，E的任何一個子簇E'均可用向量
表示，其中當Ej∈E'時，
；否則
。
性質
xE'的向量表示中的T為轉置，或者說xE'為一個n維列向量。由於xE'的每個分量只有兩個可能值，可知共有2n個這種向量。類似的理由，可知n=2m。
推廣
設A=(aij)m×n為一個m×n的矩陣，使得aij=1，當vi∈Ej；否則aij=0(1≤i≤m,1≤j≤n)。即A為I與E的關聯陣，這時，I的裝填就與不等式組Ax≤e(0≤x≤e)的整數解一一對應。其中，e=(1,...,1)T，即所有分量均為1的那個n維列向量。由此，裝填多面體就是不等式組Ax≤e(0≤x≤e)的整數解集的凸包。
相應地，覆蓋多面體就是不等式組Ax≥e(0≤x≤e)的整數解集的凸包，劃分多面體就是不等式組Ax=e(0≤x≤e)的整數解集的凸包。
