実行可能多面体

【じっこうかのうためんたい (feasible polyhedron)】

線形計画問題が与えられたとき,その問題の制約条件を満たす点の集合は有限個の閉半空間の共通部分として表される領域であり, 凸多面体を構成する. この多面体を実行可能多面体と呼ぶ. 実行可能多面体の頂点は線形計画問題の実行可能な基底解に対応するため,実行可能多面体のすべての点は実行可能解となる. なお, 実行可能多面体は有界とは限らない.