problema incarico con costi

Question

ho un problema, che mi sono bloccato con, e cant trovare ovunque per cominciare, quindi sono irrimediabilmente rivolgendosi a StackOverflow.

il problema ci vuole scoprire se è NP-hard o polinomiale, se NP-difficile dimostrare NP-completo, altrimenti dare l'algoritmo.

il problema è il seguente:

un prodotto esistente di n moduli. ci sono due aziende che possono costruire ogni modulo, con un certo costo (c_ij, i: numero di modulo, j: numero di società). se i moduli A e B sono costruiti da aziende diverse, essi hanno anche un costo aggiuntivo, (p_ab). i moduli A e B non devono essere successive, lo stesso costo aggiuntivo vale per aec troppo. come previsto, il problema ci vuole trovare l'assegnazione dei moduli per le aziende in modo che il costo totale è minimo.

tutte le idee?

Answer 1

Si può essere ridotta a problema min taglio, che può essere trovato da qualsiasi algoritmo max flusso. Quindi qual è la rete? I moduli saranno vertecies del nostro grafico e anche noi aggiungere sorgente 2 nuovi vertici e lavandino. Da fonte aggiungiamo bordo per ogni i moduli con una capacità Ci1. Allo stesso modo da ogni modulo di I aggiungiamo bordo ad affondare con una capacità Ci2. Anche per tutti i moduli i e j si aggiungo bordo con capacità Pij (Grafico orientato quindi ci saranno due bordi (i j) e (j i)). È facile vedere che valore minimo taglio è soluzione del problema (moduli parte del taglio con l'assegnazione sorgente alla seconda società e di riposo moduli alla prima compagnia)