problème d'affectation avec les coûts

Question

J'ai un problème, que je suis coincé avec, et ne peux pas trouver n'importe où pour commencer, donc je me tourne désespérément vers stackoverflow. Le problème veut que nous sachions si c'est np-hard ou polynomial, si son np-hard prouve np-exhauseness, sinon donne l'algorithme.

le problème est le suivant:

un produit existe des modules n. Il y a deux entreprises qui peuvent construire chaque module, avec un certain coût (c_ij, i: numéro de module, j: numéro d'entreprise). Si les modules a et b sont construits par des entreprises différentes, ils ont aussi un coût supplémentaire (p_ab). les modules a et b ne doivent pas être successifs, le même coût supplémentaire s'applique pour a et c aussi. Comme prévu, le problème veut que nous trouvions l'affectation des modules aux entreprises pour que le coût total soit minimum.

des idées?

Answer 1

Il peut être réduit à un problème de coupe min, qui peut être trouvé par n'importe quel algorithme de débit maximum. Alors, quel est le réseau? Les modules seront des vertecies de notre graphique et nous ajoutons aussi 2 nouveaux sommets source et puits. De la source, nous ajoutons un bord à chaque module i de capacité Ci1. De même à partir de chaque module, nous ajoutons le bord à couler avec la capacité Ci2. De plus, pour tous les modules i et j, nous ajoutons le bord avec la capacité pij (orienté graphiquement donc il y aura deux arêtes (i j) et (j i)). Il est facile de voir que la valeur de la coupe min est la solution du problème (les modules dans une partie de la coupure avec la source assignent à la deuxième entreprise et les modules de repos à la première entreprise)