Investigación de
Operaciones
UNIDAD 4. Método de transporte.
2.5.1. Modelo de asignación.
El problema de asignación

Este problema consiste en asignar n
individuos a n tareas de modo que todos
los individuos realicen una tarea y todas
las tareas se realicen. Se exige además
que el costo total sea mínimo.
Ejemplo
 Una empresa tiene 4 máquinas y debe
completar cuatro tareas. Cada máquina
puede y debe realizar una y sólo una de
las tareas. La tabla siguiente nos da el
tiempo que tarda cada máquina en
completar cada trabajo.
2.5.1. Modelo de asignación.

Asignar una tarea a cada máquina de
modo que la suma de los tiempos
trabajados por las cuatro máquinas sea
mínimo.
2.5.1. Modelo de asignación.

Este problema se puede resolver por el
algoritmo de transporte, ya que las
máquinas pueden ser interpretadas como
orígenes con oferta 1 y las tareas como
destinos con una demanda de 1, puesto
que cada maquina sólo hace una tarea y
todas las tareas han de ser realizadas.
2.5.1. Modelo de asignación.

Las soluciones de este problema sólo
pueden tomar los valores 0 ó 1. Un 1 en
la celda (i, j) significa que al individuo i se
asigna la tarea j.

Aunque el problema puede resolverse por
el algoritmo de transporte, se suele
presentar un alto grado de degeneración.
2.5.1. Modelo de asignación.

Para el problema de asignación es más
eficiente usar el método Húngaro, que
exponemos a continuación.
2.5.1. Modelo de asignación.
El algoritmo Húngaro (Forma minimizante)
 Partiendo de la matriz cuadrada de los
tiempos se realizan los pasos siguientes:
 Paso 1: Encontrar el mínimo de cada fila.
Construir una nueva matriz restando de
cada fila el mínimo coste de ésta. Para
esta nueva matriz realizar la misma
operación por columnas. Esta nueva
matriz se llama matriz de coste reducido.
2.5.2. Explicación del método húngaro con el
método simplex.

Paso 2: Considerando esta última matriz y
procurando comenzar por las filas o
columnas con menor número de ceros se
recuadra un cero en cada fila y columna y
se tachan los demás ceros de estas filas o
columnas. Se repite este proceso hasta
que no queden ceros sin tachar o
recuadrar.
2.5.2. Explicación del método húngaro con el
método simplex.

Paso 3: Si el número de ceros
recuadrados es igual que el número de
filas (también será igual que el número de
columnas), las posiciones de los ceros
recuadrados marcan la solución óptima. Si
no es así, continuar con el Paso 4.
2.5.2. Explicación del método húngaro con el
método simplex.
Paso 4: Tachar con el menor número de
líneas (filas o columnas) todos los ceros
de la matriz.
 Para conseguirlo se puede seguir el
siguiente procedimiento:
 a) Se marcan la filas que no tengan
ningún cero recuadrado.
 b) Se marcan las columnas que tengan
algún cero tachado en las filas marcadas.

2.5.2. Explicación del método húngaro con el
método simplex.
c) Considerando únicamente las columnas
marcadas se marcan las filas que tengan
algún cero recuadrado en estas columnas
marcadas.
 d) Se repite b y c hasta que no se puedan
marcar más filas o columnas.
 e) Se tachan las filas no marcadas y las
columnas marcadas.

2.5.2. Explicación del método húngaro con el
método simplex.
Paso 5: Se resta a todos los elementos sin
tachar el menor de ellos. Los elementos
de la parte tachada se dejan igual salvo
los que están tachados dos veces, a los
que se les suma ese número.
 Paso 6: Volver al paso 2

2.5.2. Explicación del método húngaro con el
método simplex.
Ejemplo de aplicación del algoritmo
Húngaro
 Vamos a aplicar este algoritmo al
problema del ejemplo.
 Se usarán los siguientes símbolos:
2.5.2. Explicación del método húngaro con el
método simplex.
Esta última es la matriz de costos reducidos.
2.5.2. Explicación del método húngaro con el
método simplex.

Paso 2 (se indica el orden en que se han
seleccionado los ceros):
2.5.2. Explicación del método húngaro con el
método simplex.

Como hay 4 ceros recuadrados, sus
posiciones marcan la solución óptima.

En este caso consiste en que la máquina 1
hace la tarea 2, la máquina 2 la tarea 4,
la 3 la tarea 3 y la 4 la tarea 1.
2.5.2. Explicación del método húngaro con el
método simplex.

El tiempo total requerido será 1 + 5 + 1 +
3 = 10.

Con el objeto de ilustrar el resto del
algoritmo lo aplicamos a la matriz del
siguiente ejemplo.
2.5.2. Explicación del método húngaro con el
método simplex.
Ejemplo
 Hallar la solución óptima en el problema
de asignación cuya matriz de costos
reducidos es:
2.5.2. Explicación del método húngaro con el
método simplex.
Como ya se ha realizado el paso 1
comenzamos el siguiente.
 Paso 2


Como hay menos ceros recuadrados que
filas (o columnas) continuamos con el
siguiente paso.
2.5.2. Explicación del método húngaro con el
método simplex.
Paso 4 a, b, c.
 Está indicado en la tabla el orden en que
se han marcado las filas y columnas.


Ya no pueden marcarse más filas ni más
columnas.
2.5.2. Explicación del método húngaro con el
método simplex.

Paso 4e ( los elementos marcados con ’xx’
son los que están tachados dos veces)
2.5.2. Explicación del método húngaro con el
método simplex.

Paso 5
Vuelta al paso 2.
 Se indica el orden en que se han
recuadrado los ceros.

2.5.2. Explicación del método húngaro con el
método simplex.

Ahora hay 4 ceros recuadrados que marcan
una solución óptima.
2.5.2. Explicación del método húngaro con el
método simplex.
Descargar

Diagramas de flujo - Pastranamoreno Blog