2

最適化問題を見ると、たくさんのオプションがあります。1つは線形計画法です。LPがどのように機能するかは抽象的な言葉で理解できますが、特定の問題がLPに適しているかどうかを確認するのは難しいと思います。この決定を導くのに役立つヒューリスティックはありますか？

たとえば、「このタイプのマイニングを行うための良い方法はありますか？」で説明されている作業です。問題を正しく構成する方法を理解するまでに数週間かかりました。最初に「言い方」を見なくても、LPで問題が解決できることを「事前に」知ることは可能でしょうか。

問題がLPに適しているかどうかを判断するために使用できるチェックリストはありますか？このトピックの標準（読み取り可能な）リファレンスはありますか？

4

1 に答える 1

7

手元の問題が本当に線形計画法であるかどうかを判断するためのヒューリスティック（および/またはチェックリスト）。

これが私の答えの試みであり、私はこの問題にどのように取り組むかについても概説しようとしました。

特定の問題がLP/IPとして定式化するのに適していることを示す質問：

  1. さまざまな時間間隔で定期的に行う必要のある決定はありますか？
  2. タスクを割り当てる必要のあるリソース（労働者、機械、車両）はたくさんありますか？（時間、仕事、目的地）
  3. これは、さまざまな「ポイント」にアクセスする必要があるルーティングの問題ですか？
  4. これは場所ですか、それとも「レイアウト」の問題ですか？（ストックカット問題のクラス全体がこのグループに分類されます）

これらの質問に「はい」と答えると、LPの定式化が機能する可能性があります。

一般的に遭遇するLPには、リソースの割り当てが含まれます。:(割り当て、輸送、積み替え、ナップザック）、ポートフォリオの割り当て、ジョブスケジューリング、およびネットワークフローの問題。 これは、LPまたはIPを初めて使用する人のためのLPアプリケーションの優れたリストです。とはいえ、LP/IPとして定式化できる問題には文字通り何千もの異なるタイプがあります。私が一緒に働いた人々（研究者、同僚）は直感を発達させます。彼らは、問題が特定のタイプの整数計画であることを認識するのが得意です。たとえ詳細を覚えていなくても、詳細を調べて調べることができます。

この質問に答えるのが難しい理由： LPの定式化がそれを削減するかどうかを知ることが必ずしも簡単ではない理由はたくさんあります。

  1. モデリング/定式化へのアプローチには多くの「芸術」（主観性）があります。
  2. 経験は大いに役立ちます。人々は、この問題が別の既知の定式化に「例える」ことができることを認識するのが上手になります
  3. 問題がストレートLPでなくても、全体的な定式化を機能させる多くの巧妙なマスタースレーブ手法（サブ問題）またはネスト手法があります。
  4. 複数の目的のように見えるものは、適切な重みのセットを付加して、1つの目的関数に組み合わせることができます。
  5. 経験豊富なモデラーは、分解と制約緩和の手法を採用し、後でそれを補正します。

基本的な定式化を完了するにはどうすればよいですか？

以下は常に私を正しい方向に導いてくれました。私は通常、決定変数、制約、および目的関数をリストすることから始めます。次に、通常、これら3つを繰り返して、すべてが「適合する」ことを確認します。

したがって、手元に問題がある場合は、次のことを自問してください。

  • 決定変数（DV）とは何ですか？ これは、処方のプロセスを開始するのに常に良い場所だと思います。DVには何種類ありますか？（どのリソースがどのタスクを取得し、いつ開始する必要がありますか？）
  • 制約は何ですか？
    いくつかの制約は非常に簡単に確認できます。他の人は少しからかう。制約は、決定変数、および課せられる定数/制限の観点から記述する必要があります。
  • 目的関数とは何ですか？
    最大化または最小化する必要がある量は何ですか？注：目的関数が何であるかが明確でない場合があります。それは制約充足問題である可能性が高いので、それは問題ありません。

LPの定式化が完了したと思ったら、いくつかの簡単な健全性チェックを行います。

  1. 私は常に、些細な解（すべて0またはすべての大きな数）が解集合の一部ではないかどうかを確認しようとします。はいの場合、定式化はおそらく正しくありません。いくつかの制約がありません。
  2. すべての制約が決定変数に「関連」していることを確認してください。（私は時々「そこにぶら下がっている」だけの制約を見つけます。これは「簿記の制約」が見落とされたことを意味します。）

私の経験では、それを維持する人々はほとんどの場合、必要な直感を発達させます。お役に立てれば。

于 2012-03-31T02:56:27.410 に答える