1

これが問題です。N 人の労働者と N 人の仕事があるとします。各ジョブに正確に 1 人のワーカーを割り当てたいと考えています。各ワーカー i について、彼はいくらかのコストでいくつかの仕事を行うことができます。私たちの目標は、単一のコストがある値よりも小さくなければならないという条件で、総コストを最小化することです。

たとえば、10 人のワーカーと 10 のジョブです。ワーカー 1 は $0.8 でジョブ 1、$2.3 でジョブ 2、$15.8 でジョブ 3、$100 でジョブ 4 から 8、$3.2 でジョブ 9、$15.3 でジョブ 10 を実行できます。

ワーカー 2 は $3.5 でジョブ 1、$2.3 でジョブ 2、$4.6 でジョブ 3、$17 でジョブ 4 を実行できます。

私たちの目標は、マッチングを見つけることです。または、総コストが最小化されるように割り当てと呼ぶことができますが、作業 i とジョブ i の間の対応するペア/マッチングの単一のコストは $50 のような値よりも小さくなります。

可能であれば、 MATLABで解決したいと思っています。

4

1 に答える 1

2

これは割り当て問題のわずかなバリエーションです。単一の仕事のコストが特定の値を超えてはならないという追加の制約を処理するには、このしきい値よりも大きいコストのマトリックス内のすべてのエントリを巨大な値に変更するだけです (他のすべてのエントリの合計よりも大きい値で十分です)。ハンガリーのアルゴリズムなどを使用して、通常どおり解決します。

于 2013-10-23T23:19:43.370 に答える