problème d'affectation des coûts

Question

J'ai un problème, que je suis coincé avec, et ne peux pas trouver nulle part où commencer, donc je me tourne désespérément à stackoverflow.

le problème nous veut savoir si elle est np-dur ou polynomiale, si son np dur prouver np-complet, sinon donner l'algorithme.

le problème est le suivant:

un produit existe de n modules. il y a deux entreprises qui peuvent construire chaque module, avec un coût (c_ij, i: numéro du module, j: numéro d'entreprise). si des modules a et b sont construits par des sociétés 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 pour applique et c aussi. comme prévu, le problème veut que nous trouvions l'attribution des modules aux entreprises de sorte que le coût total est minimum.

idées?

Answer 1

Il peut être réduit à un problème min de coupe, qui peut être trouvé par un algorithme de débit max. Alors, quel est le réseau? Les modules seront vertecies de notre graphique et aussi nous ajoutons 2 nouvelles sources et puits sommets. De la source, nous ajoutons bord à chaque module i avec une capacité CI1. De même de chaque module i nous ajoutons bord à s'enfoncer avec une capacité Ci2. De plus pour tous les modules i et j nous ajoutons bord avec une capacité JIP (Graphe orienté, il y aura donc deux bords (i j) et (j i)). Il est facile de voir que la valeur de coupe min est la solution du problème (modules en partie de la coupe avec la assign source à la deuxième société et de repos des modules à la première entreprise)