導入
数学における線形計画法(LP) 問題は、目的関数と制約がすべて線形である最適化問題です。ただし、ここで示した結果のほとんどは、目的が考慮されている各変数の単調増加関数である場合にも当てはまります。線形計画法は、線形問題を解決する方法も指します。
LP 問題は最も簡単な最適化問題であり、すべての制約が線形であるため、線形計画法は最適化の中心領域です。実際の オペレーションズ リサーチの問題の多くは、PL 問題として表現できます。このため、他の最適化問題を解決するための多数のアルゴリズムは、線形問題の解決に基づいています。
線形計画法という用語は、求められる解が実数変数で表現されなければならないことを前提としています。問題のモデリング (いわゆる整合性制約) で離散変数を使用する必要がある場合は、整数の線形計画法 (PLNE) について話します。後者は連続変数を使用した PL よりも解くのが大幅に複雑であることを知っておくことが重要です。
例
Hヘクタールに等しい面積の土地を所有し、小麦やトウモロコシを植えることができる農家を考えてみましょう。農家は量Eの肥料とIの殺虫剤を持っています。小麦には、1 ヘクタールあたりE 1の量の肥料と、1 ヘクタールあたりI 1の殺虫剤が必要です。トウモロコシの対応する量はE 2およびI 2で示されます。
P 1 を小麦の販売価格、 P 2 をトウモロコシの販売価格とします。小麦とトウモロコシを植えるヘクタールの数をx 1とx 2で表すと、小麦とトウモロコシを植える最適なヘクタール数は線形プログラムとして表すことができます。
| 最大化する | D1 × 1 + D2 × 2 | （純利益の最大化） |
| 制約の下で | $$ { x_1 + x_2 \le H } $$ | （総ヘクタール数の制限） |
$$ { E_1 x_1 + E_2 x_2 \le E } $$ | （肥料の量の制限） | |
$$ { I_1 x_1 + I_2 x_2 \le I } $$ | （殺虫剤の使用量制限） | |
$$ { x_1 \ge 0,\, x_2 \ge 0 } $$ | (負のヘクタール数を植えることはできません) |
二元性
すべての線形プログラムは次の形式で記述できます。
ここで、 cとx はサイズnのベクトル、 b はサイズmのベクトル、 A はサイズの行列です
ここで、 A 、 b 、 cは同じであり、 y はサイズmのベクトルです。
2 つの問題は非常に強く関連しています。そのうちの 1 つが最適な解決策を持っている場合、もう一方も最適な解決策を持っています。さらに、両方の解は同じ値になります ( w * = z * )。そのうちの 1 つが制限されていない場合、もう 1 つは解決策がありません。
双対問題には、理論的な面白さに加えて、非常に興味深い経済的応用もあります。各主制約は二重変数に対応します。最適解におけるこの変数の値は、主制約に関連付けられた限界費用を表します。
理論
前の例が示すように、プログラミングは、たとえばn 個の変数を決定することで構成されます。
- $$ {L(x_1, \cdots, x_n) = \sum_{i=1}^n c_i x_i} $$
たとえば次のm不等式など、さまざまな制約の下で
- $$ {\sum_{j=1}^n A_{i,j} x_j \leq b_i} $$
私は1 からmまでの範囲です。このような制約により、次のような符号制約を含めることが可能になります。
- $$ { \begin{array}{rrll} \max L(x) = & {}^tc\,x & &\\ s.c & Ax &\leq& b\\ & x &\geq&0 \end{array} } $$
線形計画法では、目的関数を最小化することを試みることができます。最大化を図ることで、前のケース (標準形式) に戻ります。
幾何学的観点から見ると、線形拘束は凸多面体(または多面体) を形成します。目的関数も線形の場合、すべての局所最適値は大域最適値でもあります。これは、考慮される各変数で単調増加する場合に当てはまります。線形ケースは、プロパティが使用されない特定のケースのみを表します。
最適な解決策が存在しないケースが 2 つあります。 1 つ目は、制約が互いに矛盾する場合です (例:
多面体は、目的関数で定義された方向に無制限にすることもできます (たとえば、次のようなx 1 + 3 x 2) 。
これら 2 つのケース (実際の問題では究極的にはまれです) を除けば、最適値は常に多面体の頂点で達成されます。ただし、最適解は必ずしも一意であるとは限りません。ポリトープのエッジや面、あるいはポリトープ全体に対応する最適解のセットを持つことも可能です。
