Network model (operations research) — ネットワークモデル
Jump to navigation
Jump to search
ネットワークモデル（オペレーションズ・リサーチにおいて、英語ではNetwork models）とは、問題をグラフ（ネットワーク）の形で表現する数理モデルの一種であり、頂点（ノード）がオブジェクトや状態を、辺（アーク）がそれらの間の接続やプロセスを表します[1]。最適化の文脈では、ネットワークとはしばしば有向グラフを指し、オペレーションズ分析ではこれを直接「ネットワーク」と呼びます。このようなネットワークの頂点はノード、辺はアークと呼ばれます[2]。
ネットワークモデルは、ロジスティクス、電気通信、プロジェクト管理、金融などの分野で、複雑なシステムを分析・最適化するための強力なツールです。その強みは抽象度の高さにあり、ノードは都市、コンピュータのルーター、あるいはプロジェクトの段階を表すことができ、アークは道路、通信チャネル、あるいは技術的な作業を表すことができます。
定義と用語
ネットワークモデルの基礎はグラフ理論です。主要な概念は以下の通りです。
- フローネットワーク（英語: flow network）：各辺が容量（capacity）とフロー（flow）を持つ有向グラフ。グラフ内には、フローが流れ出す始点（source）と、流れ込む終点（sink）という2つの特別な頂点が定義されます[1]。
- フロー保存則：始点でも終点でもない任意の頂点において、入ってくるフローの総和は、出ていくフローの総和と等しくなければなりません。この条件は、物理的な保存則の離散的な類似物です[3]。
- ネットワーク計画：プロジェクトを相互に関連する作業（アーク）とイベント（ノード）の複合体として表現するモデル。このようなネットワークは有向非巡回グラフであり、作業の実行順序を反映します[4]。
主要な特性と定理
ネットワークモデルは、その解決に非常に効率的なアルゴリズムを適用できる、いくつかの特別な特性を持っています。
- 解の整数性：多くのネットワーク最適化問題（最大フロー問題や最短経路問題など）は、制約行列が完全ユニモジュラ性という特性を持っています。このおかげで、問題のパラメータ（容量、長さ）が整数であれば、線形計画法で得られる最適解も、追加の制約なしに整数となります[5][6]。
- 最大フロー最小カット定理：フロー理論の中心的な結果です。始点から終点への最大フロー値は、始点と終点を分離するすべてのカットの中で最小の容量に等しいと主張します。この定理はフローの最適性基準を確立し、多くのアルゴリズムの基礎となっています[6][7]。
- 最短経路の最適性原理：点Aから点Cへの経路が最短である場合、その経路の任意の部分（例えば、中間点BからCまで）もまた、対応する頂点間の最短経路となります。この特性は動的計画法の基礎であり、ダイクストラ法などのアルゴリズムの正当性を保証します[8]。
- 最小全域木（MST）の特性：
- カット特性：グラフの任意のカットに対して、そのカットを横切る最小重みの辺は、少なくとも1つのMSTに属します。
- サイクル特性：グラフの任意のサイクルにおいて、最大重みの辺はどのMSTにも属しません。
これらの特性は、プリム法やクラスカル法といった「貪欲法」アルゴリズムの正当性の基礎となっています[9]。
ネットワーク最適化の主要な問題
- 最短経路問題：2つの指定されたノード間の合計長（重み）が最小となる経路を見つけます。ダイクストラ法（非負の重みの場合）やベルマン・フォード法（任意の重みの場合）によって解決されます[8]。
- 最大フロー問題：与えられたアークの容量の下で、始点から終点への最大可能なフローを決定します。古典的な解法はフォード・ファルカーソン法です[6]。
- 最小全域木問題：ネットワークのすべての頂点を接続し、辺の合計コストが最小となる部分グラフを見つけます。
- クリティカルパス法（CPM）：ネットワーク計画モデルにおいて、プロジェクト全体の最短完了時間を決定する最長の作業シーケンスを特定します。このパス上の作業には時間的な余裕（フロート）がありません[10]。
例
- 最短経路：ナビゲーションシステムが都市の地図上で2点間の最適ルートを検索する例。都市がノード、道路が長さや移動時間に等しい重みを持つアークに対応します。
- 最大フロー：パイプライン網の最大輸送能力を決定する例。ポンプ場がノード、パイプが制限された容量を持つアークに対応します。
- 最小全域木：複数の都市を最小の総ケーブル長で接続するための通信網（例：光ファイバーケーブルの敷設）の設計。
- クリティカルパス：住宅建設プロジェクトにおいて、各作業（基礎工事、壁の建設、屋根の設置）が所定の期間と技術的な依存関係を持つ場合、クリティカルパスは建設完了までの最短期間を決定します。このパス上の作業に遅れが生じると、プロジェクト全体の遅延につながります[10]。
注釈
- ↑ 1.0 1.1 "Flow network". Wikipedia. [1]
- ↑ 「テーマ10：ネットワークモデル」『教科書』ゴメリ：ベラルーシ国立交通大学。[2]
- ↑ 「輸送ネットワーク」『ウィキペディア』[3]
- ↑ 「ネットワーク計画」『ウィキペディア』[4]
- ↑ Bradley S. P., Hax A. C., Magnanti T. L. (1977). Applied Mathematical Programming. Addison-Wesley. Ch.8: Network Models. [5]
- ↑ 6.0 6.1 6.2 「最大フロー問題」『ウィキペディア』[6]
- ↑ Goldberg A. V., Tardos É., Tarjan R. E. (1990). "Network Flow Algorithms". In: Paths, Flows, and VLSI-Layout. Springer. [7]
- ↑ 8.0 8.1 「最短経路問題」『ウィキペディア』[8]
- ↑ 「最小全域木」『ウィキペディア』[9]
- ↑ 10.0 10.1 「クリティカルパス法」『ウィキペディア』[10]