整数多面体
2007年7月12日 (木) 23:01時点における122.17.2.240 (トーク)による版 (新しいページ: ''''【せいすうためんたい (integral polyhedron)】''' 凸多面体 $P=\{\mbox{\boldmath $x$} \mid \mbox{\boldmath $A x$} \leq b\}$ において, $P_I$ を, 凸多面...')
【せいすうためんたい (integral polyhedron)】
凸多面体 $P=\{\mbox{\boldmath $x$} \mid \mbox{\boldmath $A x$} \leq b\}$ において, $P_I$ を, 凸多面体 $P$ に含まれる整数ベクトルの集合の凸包とする. このとき $ P = P_I $ となる $P$ を整数多面体という. 任意のコストベクトル {\boldmath $c$} に対する整数多面体 $P = P_I$ 上での整数計画問題は$P$ 上での線形計画問題として解くことができる.