線形不等式の許容領域は凸多面体である。
変数が$n$個の場合は$n$次元空間内の凸多面体である。
集合$S$が凸であるとは、集合$S$に属する任意の2点$x, y\in S$に対して、$x$と$y$を結ぶ線分上の全ての点が$S$に属することを言う。
最適解が存在しないのは、
- 可能領域が有界でなく、目的関数が発散する。
- 可能領域が空集合である。(可能解が存在しない)
可能領域が有界でなくても目的関数の形によっては最適解が存在する場合がある。
目的関数の形に依存する。
半径$S$の球に含まれる集合を有界であるという。
