Problema de atribuição com custos

Question

Tenho um problema, com o qual estou preso e não consigo encontrar em qualquer lugar para começar, por isso estou irremediavelmente me virando para o StackOverflow.

O problema quer que descubram se é NP-Hard ou Polinomial, se o seu NP-hard provar a completude NP, caso contrário, dê o algoritmo.

O problema é o seguinte:

Existe um produto de n módulos. Existem duas empresas que podem construir cada módulo, com algum custo (c_ij, i: número do módulo, j: número da empresa). Se os módulos A e B forem construídos por diferentes empresas, eles também terão um custo adicional (P_AB). Os módulos A e B não precisam ser sucessivos, o mesmo custo adicional também se aplica a A e C. Como esperado, o problema deseja que encontremos a atribuição de módulos às empresas, para que o custo total seja mínimo.

alguma ideia ?

Answer 1

Pode ser reduzido a um problema de corte min, que pode ser encontrado por qualquer algoritmo de fluxo máximo. Então, qual é a rede? Os módulos serão vertecias do nosso gráfico e também adicionamos 2 novas fontes e coletor de vértices. Da fonte, adicionamos Edge a todos os módulos I com capacidade CI1. Da mesma forma, de todos os módulos, eu adicionamos borda para afundar com capacidade CI2. Também para qualquer módulo I e J, adicionamos Edge com Capacidade PIJ (Orientado por gráficos, portanto, haverá duas arestas (IJ) e (JI)). É fácil ver que o valor do corte min é a solução do problema (módulos em parte do corte com a fonte atribuída à segunda empresa e módulos de descanso para a primeira empresa)