Zuordnungsproblem mit Kosten

Question

ich habe ein Problem, das ich mit bin stecken und kann nicht überall zu beginnen, finden, so dass ich hoffnungslos drehe zu Stackoverflow.

das Problem will, dass wir herausfinden, ob es NP-schwer oder Polynom ist, wenn seine NP-schwer NP-Vollständigkeit beweisen, sonst den Algorithmus geben.

Das Problem ist wie folgt:

ein Produkt besteht aus n Modulen. gibt es zwei Unternehmen, die jedes Modul, mit einigen Kosten aufbauen können (c_ij, i: Modulnummer, j: Firmennummer). wenn Module a und b von verschiedenen Firmen gebaut werden, haben sie auch eine zusätzliche Gebühr, (p_ab). a und b die Module müssen nicht aufeinander folgen, die gleichen zusätzlichen Kosten gilt für zu a und c. wie erwartet, will das Problem uns die Zuordnung der Module zu Unternehmen finden, so dass die Gesamtkosten minimal sind.

irgendwelche Ideen?

Answer 1

Es kann auf min Schnitt Problem verringert werden, die von jedem max Flussalgorithmus gefunden werden kann. Also, was ist das Netzwerk? Module werden vertecies unserer Graph und wir 2 auch neue Eckpunkte Quelle und Senke hinzuzufügen. Von der Quelle fügen wir Kante mit einer Kapazität Ci1 zu jedem Modul i. In ähnlicher Weise von jedem Modul i fügen wir Kante mit einer Kapazität Ci2 zu versenken. Auch für alle Module i und j wir Kante mit einer Kapazität pij hinzufügen (Graph orientiert somit wird es zwei Kanten (i j) und (j i)). Es ist leicht einzusehen, dass Wert von min Schnitt zu sehen ist Lösung des Problems (Module in einem Teil des Schnittes mit der Quelle assign auf das zweite Unternehmen und Ruhe Module zum ersten Unternehmen)