多面体理論とは?

Weblio 辞書 > 学問 > OR事典 > 多面体理論の意味・解説 

多面体理論

読み方ためんたいりろん
【英】:polyhedral theory

概要

d \,次元上の凸多面体とは, d \,次元上の有限個の閉半空間共通集合, すなわち  \{ \boldsymbol{x} \in \mathbf{R}^d \mid \boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b} \} \,という線形不等式システム満たすベクトル集合である. d \,次元多面体は, 有限個のd \,次元凸多面体和集合書き表せるものをいう. 多面体理論とは, 上で定義した多面体を, 数学的理論用いて解析すること, 或いは解析された結果をいう. オペレーションズ・リサーチ分野では, 1つ凸多面体 (convex polyhedron)について論じることがほとんどである.

詳説

 多面体理論 (polyhedral theory) には, 見方, 切り口によって様々な理論体系存在する. 第一に, 古代ギリシャ時代より研究されているプラトン正多面体, アルキメデス準正多面体などを代表例として挙げられる古典的正多面体理論. これらの多面体は, 見た目美しいだけでなく, 群論, 整数論, 組合せ理論など諸々美し数学的構造をも内包している. 詳しい内容については, 文献 [2, 1] を参照されたい.

 上述の多面体理論は, 2次元或いは3次元限定されたものである. 近年3次元多面体に関する新たな成果として, 3次元多面体展開図に関するものがある. 多く読者が, 立方体 (さいころ)の展開図厚紙に描いて切り取り, 組み立て経験があろう. このように一枚に描いて切り取り, 組み立てが可能な (面どうしが重なり合わない) 図形展開図, 英語表記では net という. 3次元正多面体には net存在することが知られているが, 任意の3次元多面体については, 必ず net存在するかどうかは, 未解決問題一つである. この未解決問題に対して, 理論的, 実験的考察与えている文献が [7] である. 3次元多面体の辺をどのように切ったら net ができるのかを多く種類3次元多面体に関して考察した興味ある文献であり, また, net of polyhedron に関する参考文献リスト充実しているので, 興味ある読者は是非参照されたい.

 さて, オペレーションズ・リサーチ分野において, 多大貢献をしている多面体理論は, より一般的 (正多面体限らないという意) かつ高次元凸多面体 (covex polyhedron) に関するのである.

 d\, 次元ユークリッド空間の閉半空間 (closed half space) とは, 与えられた \boldsymbol{a} \in \mathbf{R}^d, b \in \mathbf{R}\, に対して


\{\boldsymbol{x} \in \mathbf{R}^d \mid 
\boldsymbol{a}\boldsymbol{x} \leq b \}\,


で表される集合のことである. 凸多面体 (convex polyhedron) P\, とは, 有限個の閉半空間共通部分, すなわちm \times d\, 行列\boldsymbol{A}\, および, m\, 次元ベクトル\boldsymbol{b}\, 用いて, 次のような線形不等式システム満たすベクトル集合として定義される.


P = \{ \boldsymbol{x} \in \mathbf{R}^d \mid
 \boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b}\}\,


また, 凸多面体 P\, 別の表現として, 次のものが挙げられる.


P = \{\boldsymbol{x} + \boldsymbol{y} \mid
\boldsymbol{x} \in \mbox{conv}\{\boldsymbol{x}^1,
\boldsymbol{x}^2, \ldots , \boldsymbol{x}^k\}, \; 
\boldsymbol{y} \in \mbox{cone}\{\boldsymbol{y}^1,
\boldsymbol{y}^2, \ldots , \boldsymbol{y}^l\} \}\,


但し, \mbox{conv}\{\cdots\}\, 有限個の点集合からなる凸包, \mbox{cone}\{\cdots\}\, 有限個のベクトルからなる凸錘を表し, 数学的には以下のように記述される.


\displaystyle \mbox{conv}\{\boldsymbol{x}^1,
\boldsymbol{x}^2,\ldots,\boldsymbol{x}^k\} 
 = \{\boldsymbol{x} \mid \boldsymbol{x}
 = \alpha_1 \boldsymbol{x}^1 + \alpha_2 \boldsymbol{x}^2
 + \cdots + \alpha_k \boldsymbol{x}^k, \;
 \sum_{i=1}^{k}{\alpha_i} = 1, \alpha_i \geq 0\}

\mbox{cone}\{\boldsymbol{y}^1,\boldsymbol{y}^2,
 \ldots,\boldsymbol{y}^l\} 
 = \{\boldsymbol{y} \mid \boldsymbol{y} 
 = \beta_1 \boldsymbol{y}^1 + \beta_2 \boldsymbol{y}^2
 + \cdots + \beta_l \boldsymbol{y}^l,
 \beta_i \geq 0\}\,


凸錘の部分空集合であるような多面体有界凸多面体といい, 英語では convex polytope区別する. 重要なことは, 同じ凸多面体P\, 記述するのに2通りあり, 一方可算有限個の線形不等式共通部分と表せ, 他方加算有限個の点の凸包内の点と可算有限個のベクトルによる凸錘内のベクトルの和として表せることである. 可算有限個という条件除けば, 2次元平面上の円や3次元空間内の球でさえ凸多面体として定義されうることを注意しておきたい.

 上述のように定義された一般凸多面体構造は, 記述が単純でありながら解析が非常に困難であるため, 特殊な凸多面体である整数多面体や, 凸多面体特徴付ける全ユニモジュラ性, 全双対整数性 (TDI性) 等の性質研究されており, 整数計画, 組合せ最適化問題解法等に大きく貢献している [8].

 P\, d\, 次元凸多面体, \boldsymbol{a} \in \mathbf{R}^d\, , b \in \mathbf{R}\, とする. 任意の\boldsymbol{x} \in P\, に対して, \boldsymbol{a x} \leq b\, 成り立つとき, \boldsymbol{a x} \leq b\, 凸多面体P\, の妥当不等式 (valid inequality) という. 凸多面体P\, 部分集合F\, P\, フェイス (face) であるとは, 妥当不等式\boldsymbol{a x} \leq b\, 存在し,


F = P \cap \{\boldsymbol{x} \in \mathbf{R}^d \mid 
 \boldsymbol{a} \boldsymbol{x} = b\}\,


成り立つことである. X =\{\boldsymbol{x}^1,\ldots,\boldsymbol{x}^m\} (\subseteq \mathbf{R}^d)\, d\, 次元空間m\, 個の点集合としたとき, X\, アフィン独立 (affinely independent) であるとは,


\displaystyle 
 \sum_{i=1}^{m}\lambda_i \boldsymbol{x}^i = 0,
\sum_{i=1}^{m}\lambda_i =0
 \Longrightarrow \lambda_i = 0 \mbox{ for } i=1,\ldots,m\,


成り立つことである. このようにアフィン独立性を定義すると, 多面体フェイスF\, 次元\mbox{dim}(F)\, 次のように定義できる.


\mbox{dim}(F) := (F\, 含まれる極大アフィン独立の点集合の数)-1\,


次元0,1, \mbox{dim}(P)-1\, フェイスそれぞれ頂点 (vertex) 或いは端点 (extreme point), 辺 (edge), ファセット (facet) とよぶ. 凸多面体P\, ファセット構成する妥当不等式を, ファセット制約 (facet constraints) という.

 2つの端点一つの辺を共有しているときその端点隣接しているという. 有界d\, 次元凸多面体P\, 端点とその隣接関係を表すグラフ構造を, 多面体グラフという. 2つの端点最短路とは, 辺の長さを1とした場合グラフ上で最短路をいう. P\, 直径 (diameter) とは, 最短路が最も長くなるような2端点間の最短路の長さのことである. この有界凸多面体直径に関する研究は, 端点逐一探索していく線形計画問題における単体法計算効率考える意味でも重要である. 以下, 証明はされていない凸多面体直径\delta\, に関する有名な予想を記しておこう.

任意のd\, 次元, 有界凸多面体P\, において, ファセットの数をf\, とするとP\, 直径 \delta\, は,


\delta \leq f - d\,


である.

これは Hirsch予想と呼ばれ, 一部特殊な多面体では証明されているが [5], 多面体理論における大きな未解決問題一つである. より一般場合に関する研究は, 文献 [4] を参照されたい.



参考文献

[1] 一松信, 「正多面体を解く」, 東海大学出版会, 1983.

[2] H. S. M. Coxeter, Regular Polytopes, Dover, 1973.

[3] B. Grunbaum, Convex Polytopes}, Wiley, New York, 1967.

[4] G. Kalai, "Liner programming, the simplex algorithm and simple polytopes," Mathematical Programming, Series B, Lectures on Mathematical Programming ISMP97, T. M. Liebling and D. de Werra, eds., 79 (1997), 217-234.

[5] D. Naddef, "The Hirsch conjecture is true for (0,1)-polytopes," Mathematical Programming, 45 (1989), 109-110.

[6] W. R. Pulleyblank, "Polyhedral Combinatorics," in Optimization, G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J.Todd, eds., North-Holland, 1989. 伊理正夫, 今野浩, 刀根薫監訳,『最適化ハンドブック』, 朝倉書店, 1995.

[7] W. Schlickenrieder, Nets of Polyhedra, Ph.D. thesis, Technische Universität Berlin, Germany, 1997.

[8] A. Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons Ltd., 1986.

[9] J. Stoera and C. Witzgall, Convexity and Optimization in Finite Dimensions, Springer, 1970.

[10] G. M. Ziegler, Lectures on Polytopes, Springer-Verlag, New York, 1995.



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

カテゴリ一覧

全て

ビジネス

業界用語

コンピュータ

電車

自動車・バイク

工学

建築・不動産

学問

文化

生活

ヘルスケア

趣味

スポーツ

生物

食品

人名

方言

辞書・百科事典

すべての辞書の索引

「多面体理論」の関連用語

多面体理論のお隣キーワード

   

英語⇒日本語
日本語⇒英語
   
検索ランキング



多面体理論のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2018 (社)日本オペレーションズ・リサーチ学会 All rights reserved.

©2018 Weblio RSS