3

14日以内にやらなければならない仕事があります。私は5人の労働者を持っています。ある日、正確に 3 人の労働者が必要です。各労働者は最大 9 日間のみ働くことができます。各ワーカーにはその日の好みがあり、各ワーカーの毎日のコストは異なります。

さて、これを数学用語でどうやって解くか。ワーカーの割り当てに可能な限り低いコストを見つけるにはどうすればよいですか?

ハンガリー語のアルゴリズムは 1 対 1 の代入しか見つけられないように設計されているため、これは代入の問題ではないと思います。（この場合、1日1人）

4

3 に答える 3

1

これは、二部グラフの最小コスト ネットワーク フロー問題として解決できます。各ワーカーは 9 ユニットの供給を持つソースを表し、各日は 3 の需要を持つシンクを表します。供給と需要の間のアークはそれぞれ容量 1 を持ち、コストはその日に休みたいという好みに対応します。弧に沿って流れがある場合、それは特定の労働者がその日に働くべきであることを意味します。

これはハンガリーの方法では解決できませんが、ネットワークシンプレックスを含むいくつかの高速アルゴリズムで解決できます。

代数的に、定式化は

minimize sum_w sum_d p_wd x_wd
subject to
\sum_w x_wd = 3    forall d
\sum_d x_wd <= 5   forall w

p_wd が労働者 w の日の d の優先順位である場合。これは完全にユニモジュラーな制約行列であるため、混合整数ソルバーは必要ありません。

于 2012-10-28T18:11:17.110 に答える
1

この問題を解決するために必要なのは、IP (Integer Programming) の定式化です。あなたの直感は正しいです。これは割り当ての問題に非常に似ています。基本的に、特定の日に働くように労働者を割り当てています。

問題を定式化する手順は次のとおりです。

決定変数: (英語で) どの労働者がどの曜日に働くか?

日t (1..14) と労働者w1 から w5 にラベルを付けましょう。

そう、

X_wt = 1 if worker w works on day t

X_wt = 0 otherwise

制約は、書き留めるのがかなり簡単になりました。毎日正確に 3 人の労働者が必要です。

X_1t + X_2t + X_3t + X_4t + X_5t = 3 for each t (1..14)

各ワーカーは最大 9 日間働くことができます。

(sum over t=1..14) X_wt <= 9 for each w (1..5)

そして最後に、目的関数:

C_wtt 日に労働者 w を雇うコストを とする。二重合計を使用すると、次のようになります。

Min (sum over w 1..5)(sum over t 1..14) C_wt

また、従業員の好みに何日も対応するために、さらに別のコスト セットを重ねることができますP_wt。

それが基本的な処方です。実際の解を得るには、IP/LP ソルバー ( CPLEXorExcel Solverまたは R のoptimライブラリなど) が必要になります。

それが役立つことを願っています。

于 2012-10-28T07:24:42.230 に答える
0

ビンパッキングとtspの問題になる可能性があります。容量のある車両のルーティングの問題を探します。多くの問題を共有していますが、ちょうど 3 つのワーカーがあります。定員付き車両のルーティングでは、x 人の作業員がいます。もっと情報が必要だと思います。

于 2012-10-27T13:45:04.200 に答える