variable-assignment - 割り当て確率フローネットワークソリューション

Question

コストマトリックスCに割り当ての問題があります。例：

21 30 26 16 20
27 29 28 20 38
39 25 21 19 23
28 24 30 29 16
30 33 32 17 31

ここで、C [i] [j]は、ワーカーiがジョブjを実行するためのコストを意味します。

ネットワークフローアルゴリズムでこれを解決するにはどうすればよいですか？ヒントを歓迎します。

Answer 1

それでも解決策を探している場合は、最小コストフロー問題としてこれを解決できます。

1. 容量1、コスト0のエッジでN個のワーカーに接続されたソースノードを作成します
2. 容量1とコストC[i][j]のエッジで、各ワーカーiを各ジョブjに接続します。
3. 最後に、各ジョブを、容量1、コスト0のエッジを持つシンクノードに接続します。

問題は、N個のフローユニットをネットワークを介してソースからシンクにプッシュするコストを最小限に抑えることと同じです。