algorithm - 線形計画法とは

Question

ウィキペディアの記事を読みましたが、私の理解を超えているようです。最適化と書いてありますが、他の最適化方法とどう違うのですか？

初心者がアクセスしにくい資料に飛び込むことができるように、線形計画法を紹介する回答が最も役立ちます。

Answer 1

これまでの答えは、線形計画法の代数的定義と操作上の定義を与えました。しかし、幾何学的な定義もあります。ポリトープは、多角形 (2 次元) または多面体 (3 次元) を n 次元に一般化したものです。凸多面体は、凸集合でもある多面体です。定義上、線形計画法は、凸多面体上の線形関数を最大化または最小化する最適化問題です。

例: 赤砂と青砂の組み合わせを購入したいとします。また、次のように仮定します。

1. どちらの種類のマイナスの金額も購入できません。
2. 倉庫には、300 ポンドの赤砂と 400 ポンドの青砂しかありません。
3. また、ジープの重量制限は 500 ポンドです。

これらの制約でいくらで買えるかを平面で描くと、凸五角形になります。次に、最適化したいもの (たとえば、砂中の金の総量) が何であれ、最適 (必ずしも唯一の最適ではない) がポリトープの頂点の 1 つにあることがわかります。実際、はるかに強力な結果があります。高次元であっても、このような線形計画法の問題は、多項式時間、制約の数、またはポリトープの推定側で解決できます。すべての制約が側面に対応しているわけではないことに注意してください。制約が等式の場合、ポリトープの次元が減少する可能性があります。または、制約が不等式である場合、それが他のすべての制約によって既に暗示されている場合、辺が作成されない可能性があります。

線形計画法である実用的な最適化問題がたくさんあります。最初の例の 1 つは「食事の問題」でした。さまざまな種類の食品のメニューが与えられた場合、最も安価でバランスの取れた食事はどれでしょうか? コストが線形であり、すべての制約 (ビタミン、カロリー、負の量の食品を購入できないという仮定など) が線形であるため、これは線形計画法の問題です。

しかし、理論的な理由から、線形計画法はさらに重要です。これは、最適化またはその他の目的のための最も強力な多項式時間アルゴリズムの 1 つです。そのため、他の最適化問題を近似的に解くための代用として、またそれらを正確に解くためのサブルーチンとして非常に重要です。

はい、凸計画法と整数計画法という 2 つの一般化があります。いくつかの条件を満たせば、目的 (最大化する対象) が線形である場合、凸計画法は線形計画法と同じように機能します。線形計画法が優れたアルゴリズムを持つ主な理由は、平面ではなく凸面であることがわかります。

一方、整数計画法は通常難しいものです。たとえば、サンプルの問題で、砂をまとめて購入するのではなく、決まったサイズの袋で購入する必要があるとします。それが整数計画法です。NP 困難であるという定理があります。実際の難易度は、線形計画法にどれだけ近いかによって異なります。奇跡的に、線形計画法のすべての頂点が整数点である整数計画問題の有名な例がいくつかあります。次に、線形計画法を解くことができ、解はたまたま積分になります。そのような問題の 1 つの例は結婚問題であり、n 人の男性と n 人の女性を互いに結婚させて総幸福を最大化する方法です。(または、n 都市に n 工場、n 仕事に n 応募者、n コンピューターに n プリンターなど)

Answer 2

線形計画法は、「数学的最適化」とも呼ばれる「数理計画法」のトピックです。線形計画法は、線形計画法 (LP) ではすべての制約関数と目的関数が変数に関して線形であるという点で、一般的な数学プログラムとは異なります。

Dantzig のオリジナル作品が必要な場合、または教科書を入手したい場合は、ここをお勧めします。独自のリソースを調べたい場合は、シンプレックス法を調べることから始めます。これは、これらのプログラムを解くための非常に一般的な手法です。または、あまり一般的ではありませんが、間違いなく多項式時間楕円体法です。すべてを読んだわけではありませんが、ざっと目を通すと、このPDF が開始点として適している可能性があることがわかります。双対性 (およびおそらく特にFarkas の補題) は、ほとんどの LP ソルバーの中心的なアイデアであるため、最終的に読むものは何でもカバーするようにしてください。

最も自然な拡張は、整数プログラム (LP に似ていますが、すべての変数は整数値を取る必要があります。つまり、分数コンポーネントはありません) または凸プログラミング (おそらく、より一般的な拡張) です。優れた凸最適化のテキスト ブックは、PDF 形式で入手できます。

Answer 3

他の誰もが言ったように、線形計画法は項が線形である最適化問題を解決する方法です。

LPが解決する問題の種類を理解するのに役立つかもしれません

私が線形計画法を使用した 1 つの例は、レストランのスケジュールを作成することです。レストランには次のようなスキル セットがあります。

• 料理人
• サーバー
• 食器洗い機
• ホスト
• バスサーズ
• マネージャーなど

そして、それぞれが 1 つ以上のスキル セットを持つ従業員がいます。また、各従業員には特定の可用性があります。たとえば、ボブは地元の教会の牧師であるため、日曜日の朝は働くことができません。従業員にも関連するコストがあります。ボブは 1 時間あたり 10.50 ドル、スージーは 1 時間あたり 5.15 ドルかもしれません。最後に、従業員には最低保証時間がある場合があります。ボブは 15 年間従業員として働いているので、ボスは彼が常に少なくとも 35 時間は得ると言います。

レストラン自体には要求があります。たとえば、朝、午後、夜の 3 つのシフトがあり、これらの各シフトには一連の人員配置要件があります。調理員 1 人、サーバー 1 人、朝のマネージャー 1 人、調理人 3 人、サーバー 2 人、ホスト​​ 2 人、午後はマネージャー、夕方は料理人 4 人、サーバー 4 人、ホスト​​ 3 人、マネージャー 2 人、バス担当者 2 人。各シフトには期間があり、期間に従業員の時給を掛けることで、各シフトのコストを計算できます。

最後に、州法と連邦法、およびいくつかの基本的な「ビジネス」ルールがあります。従業員は残業なしで 8 時間以上働くことはできません。従業員は 2 時間未満の勤務を予定することはできません (2 時間のシフトで 30 分通勤するのはつまらないため)、従業員は 2 つの重複するシフトで働くことはできません。

これらすべての要件を考慮して、すべての要件を満たし、人件費が最も低くなるスケジュールを教えてください。

これは、線形計画法の最適化問題の例です。

線形プログラムは通常、次のもので構成されます。

目的関数、変数、変数の範囲、および制約。

コストを最小限に抑えたいので、目的関数には、従業員が勤務するシフトと、関連するコスト (シフト期間 * 賃金) が含まれます。

この場合の変数は、各従業員が勤務できるシフトです。

従業員がシフトで働いている (1) か、従業員がシフトで働いていない (0) ため、これらの変数の範囲は 0 から 1 の間の整数になります。ところで、これは特殊なプログラムで、Binary Integer Program または略して BIP と呼ばれます。これは、すべての変数が整数 (小数値なし) であり、すべての値が 0 または 1 であるためです。

制約は、上記の要件に基づく等式/不等式の制約です。

たとえば、Bob と Suzy が両方とも朝に料理人として働くことができる場合、上記の範囲によりBob_Morning_Cook1_Shift + Suzy_Morning_Cook1_Shift = 1、 とBob_Morning_Cook_Shift = {0,1}なります。Suzy_Morning_Cook_Shift = {0,1}これら 3 つの情報により、最初の朝の料理人として最大 1 人の従業員のみを割り当てることができることが指定されます。

したがって、問題をモデル化するすべての制約を定義したら、問題の解決を開始できます。解決策が見つかった場合 (制約によっては問題が実行不可能な場合もあります)、週あたりの人件費が最も低くなる従業員の割り当てが示されます。

Answer 4

線形計画法は、線形制約と線形目的関数を含む最適化手法です。制約は問題空間を制限するように記述されていますが、目的関数は制約を満たす最小化 (または最大化) しようとしているものです。通常、シンプレックス アルゴリズムは、制約を満たす目的関数の最小 (または最大) 値を見つけるために、制約の交差のエッジに沿って移動するために使用されます。

LP 問題を設定するときは、制約が目的関数を適切に制限していることを確認することが重要です。可能な解が得られない制約を定義することは可能です (例: x > 1 および -x > 1)。これは過度に制約されています。問題を過少に制約することも可能です (たとえば、x < 1 となる最小 x を見つけます)。

Answer 5

線形計画法の 1 つの大きな違い (または少なくとも特徴的な機能) は、制約が線形方程式としてモデル化されることです。つまり、それらはすべて の形式c_1 x_1 + c_2 x_2...です。ウィキペディアの記事の標準形式のセクションでは、この概要がよくわかります。

もう 1 つの違い/機能は、線形計画法が 1 つの関数を最大化 (または最小化) しようとしていることです。多目的最適化を効果的に行うことはできません。