problema de asignación de costes

Question

tengo un problema, lo que tengo que cargar con, y no puedo encontrar en cualquier lugar para empezar, así que estoy irremediablemente girando a stackoverflow.

el problema que nos quiere averiguar si es NP-duro o polinómica, si es NP-difícil demostrar NP-completitud, de lo contrario dar el algoritmo.

el problema es el siguiente:

existe un producto de n módulos. hay dos empresas que pueden construir cada módulo, con algún costo (c_ij, i: número de módulo, j: número de la compañía). si los módulos A y B son construidos por diferentes empresas, sino que también tienen un costo adicional, (p_ab). los módulos A y B no tienen que ser sucesiva, el mismo coste adicional se aplica de A y C también. como se esperaba, el problema que nos quiere encontrar la asignación de módulos a las empresas para que el costo total es mínimo.

alguna idea?

Answer 1

Se puede reducirse a un problema min corte, que se puede encontrar por cualquier algoritmo de flujo máximo. ¿Cuál es la red? Módulos estarán vertecies de nuestro gráfico y también añadimos fuente 2 nuevos vértices y lavabo. De fuente añadimos borde para cada módulo con capacidad i Ci1. Del mismo modo desde cada módulo de E añadimos borde de hundirse con capacidad Ci2. También para cualquier módulo de i y j añadimos borde con capacidad pij (Gráfico orientado por lo tanto habrá dos bordes (i j) y (j i)). Es fácil ver que el valor de min corte es solución del problema (módulos en parte del corte con la asignación de origen a la segunda empresa y módulos de reposo a la primera compañía)