線形計画法の用語 3 線形計画法 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム
- 3.0 線形計画問題(Linear Programming;LP)
において
の制約のもとで
を最大化せよ、という問題である
- 意味を書き下すと、m個の１次線形不等式を制約条件とし、その制約条件を満たす、n個の値のセット(ベクトル)
の中で、
によって定められるスカラー量を最大にするものがあるかどうかを判断し、あるなら求めよ、となる
- ただし、
- 意味を書き下すと、m個の１次線形不等式を制約条件とし、その制約条件を満たす、n個の値のセット(ベクトル)
- 実行可能解 feasible solution
- 最適解 optimum solution
- 最大値条件を達成する実行可能解のこと
- 最適解が存在しない場合
- 3.1 多面体 polyhedron
が規定する実行可能解の集合を
の多面体と言う
- 有理数の空間であれば有理数多面体(rational polyhedron)、整数ならば整数多面体
- 非有界であることももちろんあるが、有界である(bounded)場合には、有界多面体(polytope)と呼ぶ
- 多面体Pの次元(dimension)(dim(P))と全次元(full-dimensional)
- 有界多面体Pの内部にある任意の２点について
を満たすような
を考える。このような
は複数存在しうるが、そのランクの最大値を
と表すとする。このとき、
と言い、
のとき、Pは全次元であると呼ばれる
- 多面体が全次元であることと、内部に点を持つことは等価である
- 有界多面体Pの内部にある任意の２点について
- 多面体の支持超平面(supporting superplane),面(face),頂点(vertex),基底解(basic solution)
- 多面体に対して、ベクトル
を最大にするPの部分集合が定義できる。これを
のときの
と書くこととする。このPの部分集合をPの面と呼ぶ。Pの面を含む、n次元空間全体の超平面を支持超平面と呼ぶ。逆に言うと、Pの面は、支持超平面とPとの共通部分である。また、Pの面がP全体であることもある。
- Pの面をただ１つの点が構成するとき、それをPの頂点と言う。Pの頂点は条件式
- 多面体に対して、ベクトル
- 極大面 facetと極小な面
- 頂点付き多面体(pointed)
- 錘 cone,多面錘 polyhedral cone
- 多面体の面
- 多面体は、多面体を定義する不等式のセットによって定められ、多面体の面は、多面体に対して、ベクトルに応じて定められる
- 多面体の面もまた多面体である
- 多面体の面はもっとも大きいものが多面体そのものであり、もっとも小さいものとしては頂点がありえる
- ある多面体の２つの面の間には包含関係が成り立つ
- 多面体の面であって、多面体そのものを除くどの面にも含まれないようなものを極大な面と呼び、ファセット(facet)と言う。ファセットを与えるベクトルが多面体の定義不等式セットとともに作る条件をファセット定義(facet-drfining)不等式と呼ぶ
- 多面体の面であって、他の面に含まれる要素をまったく含まないようなものを極小の面と呼ぶ。極小な面は、その次元が
となる。今、
のとき極小な面は頂点となる。極小な面が頂点であるような多面体を頂点を持つ(pointed)と呼ぶ
- 多面錘(polyhedral cone)
- 多面体の一種
- 定義不等式セットが
と表されるようなもの
- 多面錘の点は有限個のベクトルの非負の一次線形和で生成される(generated)空間となっている
