Feasible region — 実行可能領域

実行可能領域（じっこうかのうりょういき、英: Feasible region, feasible set）、または許容領域とは、オペレーションズ・リサーチ、最適化、数理モデリングにおいて、問題に課されたすべての制約を満たす、すべての可能な解（変数値の組）の集合です。

実行可能領域は、最適解を探索する部分空間を表します。この領域外にあるいかなる解も実行不可能です。

定義と形成

実行可能領域は、問題の個々の制約によって定義される集合の共通部分として形成されます。制約は以下の形式で表現されることがあります：

不等式： 変数またはその組み合わせの値に上限または下限を設定します（例：「リソースAの消費量は100単位を超えてはならない」、「生産される製品の数は50個以上でなければならない」）。
等式： 条件の厳密な達成を要求します（例：「総輸送量は1000トンに等しくなければならない」、「流入と流出のバランスはゼロである」）。
変数の符号条件： 多くの場合、変数は非負、整数、または特定の離散集合に属する必要があります。

ある点（または変数値のベクトル）が実行可能領域に属するのは、その点がこれらすべての制約を同時に満たす場合であり、その場合に限ります。

実行可能領域は、特に変数の数が少ない問題において、しばしば明確な幾何学的解釈を持ちます：

二次元空間（2変数）の場合： 各線形制約不等式は半平面を定義します。実行可能領域はこれらの半平面の共通部分であり、凸多角形となります（非有界または空の場合もあります）。
三次元空間（3変数）の場合： 各線形制約不等式は半空間を定義します。実行可能領域はこれらの半空間の共通部分であり、凸多面体（ポリヘドロン）となります。
多次元空間の場合： 線形制約によって定義される実行可能領域は、凸ポリトープとなります。

非線形制約の場合、実行可能領域はより複雑な形状を持ち、凸でない場合があります。

実行可能領域は最適化において基本的な役割を果たします：

探索空間の定義： 問題の最適解（存在する場合）は常に実行可能領域の内部または境界上に存在します。最適化アルゴリズムは、まさにこの領域内で目的関数の極値を探索します。
解の存在確認： 実行可能領域が空集合である場合（すなわち、制約が互いに矛盾している場合）、問題には実行可能解が存在せず、したがって最適解も存在しません。
最適解への影響： 実行可能領域の形状とサイズは、目的関数の極値を達成する可能性とその値に直接影響を与えます。

すべての制約と目的関数が線形である線形計画法（LP）の問題において、実行可能領域は重要な特性を持ちます：

凸性： 2点が実行可能領域に属する場合、それらの点を結ぶ線分全体も実行可能領域に属します。この特性により、最適解（存在し、かつ一意である場合）は実行可能領域をなす多面体の頂点のいずれかに存在することが保証されます。
閉性： 実行可能領域は（非厳密な不等式 ≤, ≥ および等式により）その境界を含みます。

実行可能領域は以下のいずれかであり得ます：

Ventsel E. S. 『オペレーションズ・リサーチ：課題、原理、方法論』モスクワ：ナウカ出版社、1988年。
Ackoff R. L., Sasieni M. W. 『オペレーションズ・リサーチの基礎』モスクワ：ミール出版社、1971年。
Taha H. A. Operations Research: An Introduction. — Pearson, 2017. (10th ed.)
Hillier F. S., Lieberman G. J. Introduction to Operations Research. — McGraw-Hill Education, 2021. (11th ed.)