コストの割り当ての問題

Question

私には問題がありますが、私はそれに固執していて、どこからでもどこにでも見つけることができないので、私は絶望的にStackoverflowに目を向けています。

この問題は、NPハードがNP不完全性を証明する場合、それがアルゴリズムを与える場合、それがNPハードか多項式であるかを調べることを望んでいます。

問題は次のとおりです。

Nモジュールの製品が存在します。各モジュールを構築できる2つの企業があり、ある程度のコストで（C_IJ、i：モジュール番号、J：会社番号）。モジュールAとBが異なる企業によって構築されている場合、追加のコストもあります（P_AB）。モジュールAとBは連続する必要はありません。AとCにも同じ追加コストが適用されます。予想どおり、この問題は、総コストが最小になるように、企業へのモジュールの割り当てを見つけることを望んでいます。

何か案は ？

Answer 1

最大フローアルゴリズムで見つけることができるMinカットの問題に減らすことができます。では、ネットワークは何ですか？モジュールはグラフの頂点になり、2つの新しい頂点ソースとシンクも追加します。ソースから、容量CI1を持つすべてのモジュールIにエッジを追加します。同様に、すべてのモジュールから私は容量CI2でシンクにエッジを追加します。また、任意のモジュールIおよびJの場合、容量PIJを備えたエッジを追加します（したがって、2つのエッジ（IJ）と（JI）があります）。 Min Cutの価値が問題の解決策であることがわかります（ソースが2番目の会社に割り当て、最初の会社にModulesをRESで割り当てたカットの一部のモジュール）