多目的線形計画法(MOLP)
- 提唱者
- Steuer, R. E.; Charnes, A.; Cooper, W. W.
- 年
- 1955–1986
- 種類
- Mathematical optimization / vector optimization
- 系統
- Simulation / optimization
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
多目的線形計画法(MOLP)は、古典的な線形計画法を拡張し、線形制約によって定義される実行可能領域において、複数の相反する線形目的関数を同時に扱う。単一の最適解ではなく、MOLPは意思決定者が望ましいトレードオフを選択するためのパレート効率的フロンティアを生成する。これは、資源配分、計画、および競合する目標を持つ設計問題におけるオペレーションズ・リサーチと経営科学の基礎となる。
手法の背後にある直感
通常の線形計画法では、1つのコストを最小化するか、1つの利益を最大化するが、実際の意思決定はほぼ常に複数の競合する目標を伴う――サービスレベルを最大化しつつ排出量を最小化しながらコストを最小化する。MOLPは、単一の解がすべての目的において同時に最良であるわけではないことを認識する。それは、一方の目的を改善すると必然的にもう一方が悪化するような、非劣(パレート効率的)解の完全なフロンティアをマッピングする。意思決定者はその後、選好情報――重み、願望レベル、または対話型クエリ――を使用して、そのフロンティアから最終的な解を選択し、トレードオフを複合スコアの中に隠すのではなく、明示的にする。
歴史学
多目的線形計画法の理論的基礎は、目標計画法に関する1950年代のCharnesとCooper、および効率的生産に関するKoopmansの研究に遡る。Steuerの1986年の教科書は、現在も標準である重み付き和法、イプシロン制約法、および対話型手法を体系化し、この分野を統合した。MOLPは現在、世界中のオペレーションズ・リサーチのカリキュラムにおける中心的なトピックである。
使うべき場面
問題が複数の競合する線形目的関数と線形制約を持ち、データが連続的で正確にわかっている(または決定論的として扱える)場合、そして意思決定者が集約されたスコアを受け入れるのではなく、トレードオフを明示的に理解する必要がある場合に使用する。典型的な設定には、生産計画、ポートフォリオ配分、輸送ルーティング、および公共資源予算編成が含まれる。目的関数または制約が非線形である場合(多目的非線形計画法またはメタヒューリスティクスを使用)、データが離散的または二値的である場合(多目的整数計画法を使用)、目的関数の数が5つまたは6つを超える場合(効率的フロンティアが計算上扱いにくくなる)、または意思決定者が反復的な選好抽出に関与することを望まない場合は使用しない。
限界と注意点
- 線形目的関数と線形制約に限定される。現実世界の問題はしばしば非線形である。
- 効率的フロンティアは、高次元では指数関数的に多くの極点を含む可能性があり、包括的な列挙を非現実的にする。
- 正確な数値データを必要とする。係数における不確実性またはあいまいさはネイティブには処理されない。
- 対話型手法は、意思決定者の可用性と選好を一貫して明確に表現する能力に大きく依存する。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 意思決定者にトレードオフの完全な全体像を与える、完全なパレート効率的フロンティアを生成する。
- シンプレックスベースソルバーを介して、中程度の問題サイズに対して計算上扱いにくい。
- 効率的フロンティア上の各点の数学的最適性を保証する。
- 成熟したソフトウェア(CPLEX、Gurobi、オープンソースの代替品)によってよくサポートされている。
- トレードオフは、不透明な複合指数に崩壊するのではなく、明示的に行われる。
応用
- コスト、スループット、およびリソース利用率のバランスをとる生産計画。
- リターン、リスク、および流動性のトレードオフを行うポートフォリオ最適化。
- コストとサービス目標が競合する輸送および物流ネットワーク設計。
- コストを最小化しつつ、排出量と信頼性の目標を満たすエネルギーシステム計画。
- 公平性、効率性、および予算制約のバランスをとるヘルスケア資源配分。
- 経済的および生態学的パフォーマンスを同時に最適化する環境管理。
使い方
使い方
k個の線形目的関数f1(x)からfk(x)と、線形不等式および等式制約(Ax <= b, x >= 0)によって定義される実行可能領域Xを定式化する。最小化すべき目的関数と最大化すべき目的関数を特定する。すべての目的関数と制約が決定変数において線形であることを確認する。
数式
\min_{x \in X} \mathbf{f}(x) = (f_1(x), f_2(x), \ldots, f_k(x))^T \text{ s.t. } Ax \leq b,\; x \geq 0パレート効率的(非劣)解の集合を生成する。一般的なアプローチには、重み付き和法(シンプレックス全体で重みを変化させる)、イプシロン制約法(他の目的を境界付けながら1つの目的を最適化する)、およびチェビシェフ法が含まれる。それぞれのアプローチが、効率的フロンティアの一部または全体をトレースする。
ベクトル問題を単一目的LPのシーケンスに変換するためにスカラー化手法を適用する。重み付き和アプローチでは、体系的に変化させた重みベクトルに対してmin sum(wi * fi(x))を解く。目的空間の各効率的極点を記録する。
数式
\min_{x \in X} \sum_{i=1}^{k} w_i f_i(x), \quad w_i \geq 0, \; \sum w_i = 1効率的極点とその間のエッジを収集して、パレートフロンティアを特徴付ける。フロンティア全体にわたる各目的の範囲を分析して、トレードオフの大きさを理解する。フロンティアをテーブルまたは二目的プロットを介して意思決定者に提示する。
効率的集合から望ましい解を選択するために意思決定者と関与する。対話型手法(STEM、NIMBUS)は、解を提示し、意思決定者に選好を表明するように求めることを交互に行い、最終的な選択に収束させ、その優先順位を最もよく反映させる。
よくある落とし穴
- 重み付き和スカラー化で固定重みを使用し、1つの解のみを報告すると、フロンティアが不明瞭になり、MOLPの目的が損なわれる。
- パレート効率性と最適性を混同する。フロンティア上の各点は効率的であるが、選好情報なしではどれも全体的に「最良」ではない。
- 実行可能領域が有界であるかどうかを確認しない。有界でない問題は、有限な効率的集合を生成しない。
- MOLPをブラックボックスとして扱い、意思決定者を選定に関与させないと、恣意的な最終選択につながる。
- 本質的に整数問題にMOLPを適用し、多目的整数計画法に切り替えずに、整数性を満たさない解を生成する。
よくある質問
MOLPは目標計画法とどう違うのか?
目標計画法は特別なケースまたはバリアントである。各目的を願望レベルに変換し、その目標からの逸脱を最小化することで、単一の解を生成する。一般的な形式のMOLPは、目標レベルを事前に指定せずに完全な効率的フロンティアを特徴付けることを目指し、意思決定者にさらなる柔軟性を提供する。
MOLPは2つ以上の目的を扱えるか?
はい、しかしパレートフロンティアは2つまたは3つ以上の目的を超えると視覚化が困難になり、効率的極点の数は指数関数的に増加する可能性がある。4つ以上の目的には、対話型手法と代表的サブセット技術が推奨される。
データが不確かな場合はどうなるか?
標準的なMOLPは決定論的な係数を仮定する。不確実性は、確率的多目的線形計画法(チャンス制約、シナリオベースのアプローチ)またはロバスト多目的最適化に拡張することで対処できるが、これらは別個の手法である。
MOLPは多目的最適化と同じか?
MOLPは、すべての目的関数と制約が線形である多目的最適化の特殊なケースである。多目的最適化は、非線形、整数、および組み合わせバリアントも含む、より広範な分野である。
どのスカラー化手法を使用すべきか?
重み付き和法は単純だが、フロンティアの非凸部分を見逃す。イプシロン制約法は、非凸領域であっても完全なフロンティアを回復でき、徹底的な分析には一般的に好まれる。意思決定者の関与が可能であれば、対話型手法が最適である。
関連する手法
参考文献
Steuer, R. E. (1986). Multiple Criteria Optimization: Theory, Computation, and Application. John Wiley & Sons, New York.
ISBN:9780471888468コピーしました。Chankong, V., Haimes, Y. Y. (1983). Multiobjective Decision Making: Theory and Methodology. North-Holland, New York.
出版物の文献を開くコピーしました。