6

私は常に、ビジネス上の問題を解決するためのソフトウェアを作成してきました。SOの投稿の1つを調べているときに、LIPについて出くわしました。私はそれをグーグルで検索しましたが、ビジネス上の問題を解決するためにそれをどのように使用できるかを関連付けることができません. 素人の言葉で理解するのを手伝ってくれる人がいれば感謝します。

4

6 に答える 6

2

まず、ウィキペディアから線形計画法の例を読んでください

ここで、豚や鶏を生産する農家、またはトースターや掃除機を生産する工場を想像してみてください。出力 (および場合によっては制約) は整数であるため、これらのきれいなグラフはすべて曲がって段階的に進みます。これは、線形計画問題として簡単に表現できるビジネス アプリケーションです。

以前に整数線形計画法を使用して、同じ比率の n 個の画像を並べて表示し、これらの画像を表示するために使用される画面スペースを最大化する方法を決定しました。形式主義は、スケジューリングなどの問題をカバーすることを表すことができますが、整数線形計画法のビジネス アプリケーションは、より自然なアプリケーションのように思えます。それの。

SO ユーザー flolo は次のように述べています: 私がよく遭遇する使用例: デジタル回路設計では、オブジェクトをチップの特定の部分に配置/マップする必要があります (FPGA 配置) - これは ILP で実行できます。また、ハードウェアとソフトウェアのコード設計では、パーティションの問題がしばしば発生します。つまり、プログラムのどの部分を CPU で実行し、ハードウェアで高速化する必要があるかということです。これも ILP で解決できます。

于 2011-09-30T07:12:26.567 に答える
2

ILP を使用すると、多数の決定を下すことを含む基本的にすべての問題を解決できます。各決定にはいくつかの可能な結果しかなく、すべて事前にわかっており、選択の任意の組み合わせの全体的な「品質」を関数を使用して記述できます。選択肢間の「相互作用」に依存しません。それがどのように機能するかを確認するには、変数を 0 または 1 (有効な整数の最小範囲) に限定するのが最も簡単です。今：

  • はい/いいえの答えを必要とする各決定は変数になります
  • 目的関数は、これらの変数の重み付けされた組み合わせとして、最大化 (または最小化) したいものを記述する必要があります。
  • 1 つまたは複数の線形等式または不等式の制約を使用して、各制約 (同時に行うことができない選択の組み合わせ) を表現する方法を見つける必要があります。

例

たとえば、Anne、Bill、Carl の 3 人の作業員と、Dasting、Typing、Packing の 3 つのジョブがあるとします。すべての人がすべての仕事を行うことができますが、それぞれの仕事で効率/能力レベルが異なるため、全体の効率を最大化するために、それぞれが行うのに最適なタスクを見つけたいと考えています。1 人 1 人に 1 つの仕事をしてもらいたいと考えています。

変数

この問題を設定する 1 つの方法は、worker と job の組み合わせごとに 1 つずつ、9 つの変数を使用することです。変数 x_ad は、Anne が最適解で Dust する必要がある場合は値 1 を取得し、それ以外の場合は 0 を取得します。x_bp は、Bill が最適解をパックする必要がある場合は値 1 を取得し、それ以外の場合は 0 を取得します。等々。

目的関数

次に行うことは、最大化または最小化する目的関数を定式化することです。Anne、Bill、および Carl の最新のパフォーマンス評価に基づいて、3 つのジョブのそれぞれを実行するのにそれぞれ何分かかるかを示す 9 つの数値の表があるとします。この場合、9 つの変数すべての合計に、その特定のワーカーがその特定のジョブを実行するのに必要な時間を掛けて、この合計を最小化すること、つまり、作業にかかる合計時間を最小化することが理にかなっています。すべての作業を完了します。

制約

最後のステップは、(a) 全員が正確に 1 つの仕事を行い、(b) すべての仕事を正確に 1 人が行うことを強制する制約を与えることです。(実際には、これらの手順は任意の順序で実行できることに注意してください。)

Anne が正確に 1 つのジョブを実行するようにするために、x_ad + x_at + x_ap = 1 という制約を追加できます。Bill と Carl にも同様の制約を追加できます。

ちょうど 1 人が Dusts であることを確認するために、x_ad + x_bd + x_cd = 1 という制約を追加できます。同様の制約を Typing と Packing に追加できます。

全部で 6 つの制約があります。この 9 つの変数と 6 つの制約の問題を ILP ソルバーに渡すと、最適解の 1 つの変数の値が返されます。そのうちの 3 つだけが 1 になり、残りは 0 になります。 1 である 3 は、どの人がどの仕事をすべきかを教えてくれます。

ILPは一般的です

たまたま、この特定の問題には、別のアルゴリズムを使用してより効率的に解決できる特別な構造があります。ILP を使用する利点は、問題のバリエーションを簡単に組み込むことができることです。たとえば、実際には 4 人で 3 つの仕事しかない場合、制約を緩和して、各人が厳密に行うのではなく、多くても1 つの仕事を行うようにする必要があります。 1 仕事。これは、最初の 3 つの制約のそれぞれの等号を小なり等号に変更することで簡単に表現できます。

于 2011-09-30T12:33:49.970 に答える
1

サンプルの ILP 問題は次のようになります。

  • 最大37∙x1 + 45∙x2

どこ

  • x1、x2、... は正の整数でなければなりません

...しかし、フォームには一連の制約があります

  • a1∙x1+b1∙x2 < k1
  • a2∙x1+b2∙x2 < k2
  • a3∙x1+b3∙x2 < k3
  • ...

ここで、ウィキペディアの例をより簡単に表現します。

  • 農民は、小麦か大麦のいずれか、またはその 2 つの組み合わせを植えるL m² の土地を持っています。
  • 農家はFグラムの肥料とPグラムの殺虫剤を持っています。
  • 小麦 1 m² ごとにF1グラムの肥料とP1グラムの殺虫剤が必要です
  • 大麦 1 m² ごとにF2グラムの肥料とP2グラムの殺虫剤が必要です

今、

  • a1を 1 m² あたりの小麦の販売価格とする
  • a2を 1 m² あたりの大麦の販売価格とする
  • 小麦を植える土地の面積をx1とする
  • 大麦を植える土地の面積をx2とする
  • x1、x2は正の整数です (1 m² の解像度で植えることができると仮定します)

そう、

  • 利益はa1∙x1 + a2∙x2 - 最大化したい
  • 農家の土地面積は限られているため: x1+x2<=L
  • 農家の肥料の量は限られているため: F1∙x1+F2∙x2 < F
  • 農家の殺虫剤の量は限られているため: P1∙x1+P2∙x2 < P

a1,a2,L,F1,F2,F,P1,P2,P - すべて定数 (この例では正)

示された制約を考慮して、示された式を最大化する正の整数x1,x2を探しています。

それが明確であることを願っています...

于 2011-09-30T07:33:20.163 に答える
1

ILP は「単独で」多くのものを直接モデル化できます。LP の例を検索すると、ダイエット問題などの有名な教科書の事例がたくさん見つかるでしょう。

それぞれにビタミン含有量と 1 日のビタミン割り当て量が設定された一連の錠剤が与えられた場合、割り当て量に一致する最も安いカクテルを見つけます。

そのような問題の多くには、自然に変数変数を整数にする必要がある場合があります (おそらく、丸薬を半分に分割することはできません)。

しかし、本当に興味深いのは、実際には多くの組み合わせ問題が LP に還元されるということです。私のお気に入りの 1 つは割り当て問題です。

N 個のワーカーのセット、N 個のタスク、および各ワーカーが各タスクに対して課金する金額を表す N x N 行列が与えられた場合、コストを最小限に抑えるために各ワーカーに与えるタスクを決定します。

自然に発生するほとんどのソリューションは指数関数的な複雑さを持ちますが、線形計画法を使用した多項式ソリューションがあります。

ILP に関して言えば、ILP には NP 完全であるという追加の利点と難しさがあります。これは、非常に幅広い問題をモデル化するために使用できることを意味します (ブール充足可能性もこの点で非常に人気があります)。優れた最適化された ILP ソルバーが数多く存在するため、独自のカスタム アルゴリズムを考案する代わりに、NP 完全問題を ILP に変換することが実行可能であることがよくあります。

于 2011-09-30T13:56:57.493 に答える
0

最適化したい場所ならどこでも線形計画法を簡単に適用でき、ターゲット関数は線形です。スケジュール (車両と線路の利用を最適化する必要がある鉄道会社のような大規模なサービス)、制作 (勝利の最適化)、ほとんどすべてを作成できます。問題を IP として定式化するのが難しい場合や、最適な勝利のために 0.345 台の車を生産しなければならないなど、解決策の問題に直面する場合があります。もちろんそれは不可能なので、さらに制約を加えます。車の数の変数は整数でなければなりません。単純に聞こえるようになったとしても (変数の選択肢が無限に少ないため)、実際にはより困難です。この瞬間、NP 困難になります。これは実際には、ILP を使用してコンピューターからあらゆる問題を解決できることを意味します。それを変換するだけで済みます。

あなたのために、いくつかの基本的な (I)LP に関する入門書を読むことをお勧めします。私の考えでは、良いオンライン サイトを知りません (ただし、ググればいくつか見つかります)。本として、 Chvatal のLinear Programmingをお勧めします。非常に良い例があり、実際の使用例についても説明しています。

于 2011-09-30T07:44:48.087 に答える
0

ここでの他の回答には、優れた例があります。整数計画法とより一般的なオペレーションズ リサーチを使用するビジネスのゴールド スタンダードのうちの 2 つは、次のとおりです。

  1. INFORMS (The Institute for Operations Research and the Management Sciences) 発行の雑誌 Interfaces
  2. オペレーションズ リサーチと経営科学の業績に対するフランツ エデルマン賞の受賞者

Interfaces は、現実世界の問題に適用されるオペレーションズ リサーチを使用した研究を発表しており、Edelman 賞は、オペレーションズ リサーチ技術のビジネスでの使用に対して非常に競争力のある賞です。

于 2013-03-19T17:22:06.547 に答える