Asignación

1. planteamientos
  1. red
    1. la oferta es 1 por cada nodo fuente y la demanda -1 por cada nodo destino
  2. modelo de programación lineal
    1. # arcos = # variables
    2. # restricciones = # nodos
  3. matriz de costos
    1. características
      1. debe ser cuadrada
2. método húngaro
  1. Paso 1: Restar el número más pequeño de cada renglón a cada número del renglón. (Esto se llama reducción de renglón.) Introduzca los resultados en una nueva matr iz.
  2. Paso 2: Reste el número más pequeño de cada columna de la nueva matriz a cada número de la columna. (Esto se llama reducción de columna.) Introduzca los resultados en otra nueva matriz.
  3. Paso 3. Pruebe si se puede hacer una asignación óptima.
    1. Hágalo mediante la determinación del número mínimo de líneas necesario para cubrir (es decir, cruzar) todos los ceros. Si el número de líneas es igual al número de renglones, es posible un conjunto óptimo de asignaciones. En este caso vaya al paso 6. En caso contrario continué con el paso 4.
  4. Paso 4. Si el número de líneas es menor que el número de renglones modifique la matriz de la siguiente forma:
    1. 1. Reste el número no cubierto más pequeño de todos los números no cubiertos la matriz
    2. 2. Sume el número no cubierto más pequeño a los números que se encuentran en las intersecciones de las líneas.
    3. 3. Los números cruzados pero que no se encuentran en las intersecciones de las líneas permanecen sin cambio en la matriz.
  5. Paso 5. Repita los pasos 3 y 4 hasta que sea posible tener un conjunto de asignaciones óptimo.
  6. Paso 6. Haga las asignaciones una a una en las posiciones que tienen elementos de cero.
    1. Comience con los renglones y columnas que tienen un solo cero.
    2. Como cada renglón y columna necesita recibir exactamente una asignación, cruce tanto el renglón como la columna una vez hecha la asignación.
    3. Continuar de esta manera hasta hacer todas las asignaciones.
3. características
  1. es binario
  2. es minímizado
    1. cuando se quiere minimizar el costo total
  3. si es máximizado
    1. es un problema de selección
  4. a cada asignado se le asigna una sola tarea
  5. cada tarea es realizada por un solo trabajador
  6. existe un costo cij asociado al asignado i que realiza la tarea j

Next up

Asignación

Description

Resource summary

Media attachments

Similar

	Created by Quetzally Ortega over 8 years ago

	Copied by Quetzally Ortega over 8 years ago