多目的線形計画法

多目的線形計画法は、数学的最適化のサブ領域です。多目的線形計画法 (MOLP) は、複数の目的関数を持つ線形計画法です。MOLP は、ベクトル線形計画法の特殊なケースです。多目的線形計画法も、多目的最適化のサブ領域です。

数学的に言えば、MOLP は次のように表すことができます。

${\displaystyle \min _{x}Px\quad {\text{st}}\quad a\leq Bx\leq b,\;\ell \leq x\leq u}$

ここで、は行列、は行列、は の要素を持つ次元ベクトル、は の要素を持つ次元ベクトル、は の要素を持つ 次元ベクトル、はの要素を持つ 次元ベクトル${\displaystyle B}$${\displaystyle (m\times n)}$${\displaystyle P}$${\displaystyle (q\times n)}$${\displaystyle a}$${\displaystyle m}$${\displaystyle \mathbb {R} \cup \{-\infty \}}$${\displaystyle b}$${\displaystyle m}$${\displaystyle \mathbb {R} \cup \{+\infty \}}$${\displaystyle \ell}$${\displaystyle n}$${\displaystyle \mathbb {R} \cup \{-\infty \}}$${\displaystyle u}$${\displaystyle n}$${\displaystyle \mathbb {R} \cup \{+\infty \}}$

実行可能点は、、 （ここで は成分ごとの順序付けを表す） を満たす実行可能点が存在しない場合に効率的であると呼ばれます。${\displaystyle x}$${\displaystyle y}$${\displaystyle Px\leq Py}$${\displaystyle Px\neq Py}$${\displaystyle \leq}$

文献では、多目的線形計画法の目的は、すべての効率的な極値点の集合を計算することであるとよく言われています。 ^[1]また、すべての最大効率面の集合を決定するアルゴリズムもあります。^[2]これらの目標に基づくと、すべての効率的な（極値）点の集合がMOLPの解であると見なすことができます。このタイプの解の概念は、決定セットベースと呼ばれます。^[3]これは線形計画法の最適解とは互換性がありませんが、むしろ線形計画法のすべての最適解の集合（決定がより困難）に似ています。

効率的な点は、しばしば効率的な解と呼ばれます。この用語は誤解を招きます。なぜなら、単一の効率的な点は、同じ実行可能集合を持つ線形計画と、目的関数がMOLPの目的関数の合計であるような1つの線形計画を解くことによってすでに得られるからです。^[4]

最近の参考文献では、結果セットに基づくソリューションの概念^[5]と対応するアルゴリズムが検討されています。^{[6] [3]} MOLP が有界であると仮定します。つまり、すべての実行可能な に対してとなるようなものが存在するとします。MOLP のソリューションは、MOLP の上像を記述するのに十分な量の情報を持つ効率的な点の有限の部分集合として定義されます。MOLP の実行可能セットで表すと、 MOLP の上像はセット です。ソリューションの正式な定義^{[5] [7]}は次のとおりです。 ${\displaystyle y\in \mathbb {R} ^{q}}$${\displaystyle y\leq Px}$${\displaystyle x}$${\displaystyle {\bar {S}}}$${\displaystyle S}$${\displaystyle {\mathcal {P}}:=P[S]+\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:\;\exists x\in S:y\geq Px\}}$

効率的な点の有限集合は、 MOLP の 解と呼ばれます(「conv」は凸包を表します)。 ${\displaystyle {\bar {S}}}$${\displaystyle \operatorname {conv} P[{\bar {S}}]+\mathbb {R} _{+}^{q}={\mathcal {P}}}$

MOLPが有界でない場合、解は点だけでなく点と方向から構成される^{[7] [8]}

シンプレックスアルゴリズムの多目的変種は、決定セットベースのソリューション^{[1] [2] [9]と目的セットベースのソリューション[10]}を計算するために使用されます。

目的集合に基づく解はベンソンのアルゴリズムによって得られる。^{[3] [8]}

多目的線形計画法は多面体投影と同等である。^[11]