INVESTIGACIÓN DE OPERACIONES

MODELO DE ASIGNACIÓN

Noviembre, 2022
 RESUMEN DE LA PRESENTACIÓN

En la presentación se hablará sobre los siguientes tópicos:

• Características propias del modelo de asignación.
• Balanceo de un problema de asignación que esté
desbalanceado.
• Método de solución: Método Húngaro. Descripción
del método.
• Ejemplo donde se encuentra la solución óptima de un
problema de asignación mediante la utilización del
método húngaro.
 MODELO DE ASIGNACIÓN

Características propias del modelo

Antes que todo, recuérdese cual fue la

formulación matemática general asociada a un
problema de asignación, que fue mencionada al
principio del semestre
 PROBLEMA DE ASIGNACIÓN

Objetivo: Minimizar el coste total de operación de modo que:

- Cada tarea se asigne a una y sólo una máquina.
- Cada máquina realice una y sólo una tarea.
Formulación
matemática xij: 1 si la tarea i se hace con la máquina j
m n
Min  c
i 1 j 1
ij xij
cij: coste de realizar la tarea i con máquina j

s .a . n tareas
m m máquinas
x
i 1
ij  1, j  1..n
Si hay más máquinas que tareas se formula
n

x
j 1
ij  1,i  1..m con desigualdades, y se resuelve con tareas
Ficticias.
xij  0 ,1
 MODELO DE ASIGNACIÓN

Características propias del modelo

• Los problemas de asignación constituyen un caso
particular de los problemas de transporte, siendo
en la práctica, la clase más sencilla de problemas
lineales.
• Supóngase que se tienen n exigencias que se
deben satisfacer, y n métodos para satisfacerlas,
y que cada exigencia debe ser satisfecha por uno
de los métodos, y que un método no se puede
utilizar para satisfacer más que una exigencia.
 MODELO DE ASIGNACIÓN

Características propias del modelo

• Se dispone también de una matriz de costos Cn,n,
siendo el elemento cij, el costo de satisfacer la
exigencia j por el método i. El problema de
asignación consiste en hallar aquella
combinación de métodos y exigencias que
minimizan el costo total.
 MODELO DE ASIGNACIÓN

Características propias del modelo

• El problema de asignación es un tipo de problema lineal,
con una estructura como la del modelo de transporte,
pero con una particularidad importante: cada uno de los
ai y bj son iguales a 1.
• Un problema de asignación típico es aquel
donde los orígenes son personas que están
solicitando puestos de trabajo, y los destinos
son los trabajos disponibles para esas personas.
 MODELO DE ASIGNACIÓN

Características propias del modelo

• El modelo de asignación se puede resolver directamente
como un modelo de transporte, pero dada su
característica especial en el que todas las cantidades de la
oferta y la demanda son iguales a 1, se ha desarrollado un
algoritmo de solución específico, llamado el “Método
Húngaro”.
• Cada persona ocupará un cargo y sólo uno, de forma tal
que habrá tantos cargos como ocupantes.
• Si el número de solicitantes m, es distinto del número de
cargos n, entonces el problema de asignación está
desbalanceado.
 MODELO DE ASIGNACIÓN

Características propias del modelo

• El costo de asignar una persona a un cargo se representa
por Cij y, al igual que en el problema de transporte, se
puede representar fácilmente por medio de un arreglo o
matriz como la señalada a continuación:

MÁQUINAS
1 2 3
1 50 130 190
OPERARIOS 2 130 100 150
3 110 150 270
4 150 90 60
 INVESTIGACIÓN DE OPERACIONES

BALANCEO DE UN MODELO DE
ASIGNACIÓN
 MODELO DE ASIGNACIÓN

Balanceo de un problema de asignación

• La manera de balancear un problema de
asignación que esté desbalanceado, es análoga a la
manera de hacerlo en el problema de transporte, es
decir, agregando filas o columnas ficticias según
sea el caso.
 INVESTIGACIÓN DE OPERACIONES

DESARROLLO DEL MÉTODO DE

SOLUCIÓN.
MÉTODO HÚNGARO
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

PASOS DEL MÉTODO HÚNGARO

1) Dada la matriz de costos de un problema de
asignación balanceado, identifique el menor costo de
cada una de las filas de la matriz.
Para cada fila obtenga la diferencia entre los costos
de cada elemento de la fila, y el costo menor ya
identificado.
Repita la misma operación con cada una de las
columnas, obteniéndose de esta manera una nueva
matriz de costos donde en cada fila y en cada
columna habrá por lo menos un elemento igual a 0.
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

PASOS DEL MÉTODO HÚNGARO

2) En la nueva matriz de costos, identifique un cero en
cada fila y en cada columna.
Elimine la fila y la columna a la cual pertenece el cero
(0) identificado.
Si al finalizar la eliminación se ha hecho una
asignación completa de ceros, o sea, cada origen tiene
asignado un solo destino, y cada destino tiene
asignado un solo origen, quiere decir que se ha llegado
a la solución óptima. En caso contrario se tiene que
seguir al paso 3.
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

PASOS DEL MÉTODO HÚNGARO

3) PASO 3
a) Marque cada fila que no contiene un cero asignado.
b) Marque cada columna que contiene un cero,
independientemente de si está asignado o no, en la fila
marcada en a).
c) Marque cada fila que contiene un cero asignado en
la columna marcada en b).
d) Repita b) y c) hasta que no se puedan marcar más
columnas o filas.
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

PASOS DEL MÉTODO HÚNGARO

3) PASO 3
e) Tache las filas no marcadas y las columnas marcadas.
Utilice sólo líneas horizontales y verticales.
f) Seleccione al elemento de menor valor entre aquellos
no cubiertos por una línea horizontal o vertical.
Reste este elemento del resto de los no tachados y sume
ese elemento a los ceros que están en la intersección de
líneas horizontales y verticales. Los elementos tachados
por una sola línea no cambian. Retorne al paso 2).
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

PASOS DEL MÉTODO HÚNGARO

3) PASO 3.
Otra forma de ejecutar el paso 3 es siguiendo los
siguientes pasos:
I) Trace el mínimo número de líneas horizontales y
verticales en la última matriz reducida, de forma tal de
cubrir todas las entradas de cero.
II) Seleccione el elemento no cubierto más pequeño y
réstelo a todos los elementos no cubiertos, y luego
súmelo a todos los elementos ubicados en la
intersección de dos líneas (las definidas previamente).
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

PASOS DEL MÉTODO HÚNGARO

3) PASO 3.
III) Si no es posible encontrar una asignación
factible entre las entradas cero resultantes, repita
el paso 3, de lo contrario:
Identifique la asignación óptima como la
asociada con los cero elementos de la matriz
obtenida en el paso anterior.
 INVESTIGACIÓN DE OPERACIONES

MODELO DE ASIGNACIÓN.
EJEMPLO PARA ENCONTRAR LA
SOLUCIÓN ÓPTIMA MEDIANTE
EL MÉTODO HÚNGARO
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Enunciado del problema:
El departamento de personal de una fábrica ha
recibido cuatro (04) solicitudes de trabajo para operar
tres (03) máquinas nuevas que se han adquirido.
Se han realizado pruebas a los aspirantes y se ha
determinado que cualquiera de ellos está capacitado
para operar cualquiera de las máquinas, aunque hay
unos más experimentados que otros.
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Enunciado del problema:
Puesto que cada máquina va a ser operada por un
solo operario, uno de los aspirantes no podrá
ingresar a la fábrica.
Sabiendo que los costos diarios de los operarios
para cada máquina son los que se muestran a
continuación (Costos en Bolívares):
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Tabla de costos
MÁQUINAS
1 2 3
1 50 130 190
OPERARIOS 2 130 100 150
3 110 150 270
4 150 90 60

La fábrica desea asignar un operario a cada máquina, de tal

manera de que el costo total sea mínimo.
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Solución del problema
Dado que este es un problema de asignación donde cada
persona ocupa un cargo o realiza un tarea, se hace evidente
que el problema no está balanceado, ya que no hay el
mismo número de operarios (personas) que tareas por
realizar (manejo de máquinas).
Esto implica, que previo a la aplicación de cualquier
método de búsqueda de la solución óptima, lo primero que
debe realizarse es Balancear el problema.
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Solución del problema
Para balancear el problema se agrega una columna ficticia,
de forma tal de igualar el número de operarios con el
número de máquinas a ser operadas, recordándose que, al
igual que en el caso del problema de transporte, la columna
o fila ficticia añadida, debe tener costos asociados iguales
a 0.
Una vez añadida la columna ficticia la nueva tabla de
costos del problema, toma la siguiente estructura:
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Tabla de costos para el problema balanceado

MÁQUINAS
1 2 3 4
1 50 130 190 0
2 130 100 150 0
OPERARIOS 0
3 110 150 270
4 150 90 60 0
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Solución del problema. Paso 1
Se identifica el menor costo de cada fila (cero en este caso)
y se obtienen las diferencias entre el costo de cada
elemento y el menor costo de cada una de las filas. Si se
aplica esto a cada fila (dado que los costos menores son
cero), se obtiene la siguiente tabla de costos:
MÁQUINAS
1 2 3 4
1 50 130 190 0
2 130 100 150 0
OPERARIOS 0
3 110 150 270
4 150 90 60 0
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Solución del problema. Paso 1
Se repite la misma operación realizada para fila, pero esta
vez con cada columna. En este caso, los menores costos en
las columnas 1,2,3 y 4 son: 50, 90, 60 y 0, obteniéndose la
siguiente matriz de costos Cij:
MÁQUINAS
1 2 3 4
1 0 40 130 0
2 80 10 90 0
OPERARIOS
3 60 60 210 0
4 100 0 0 0
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Solución del problema. Paso 2
Recuérdese que el paso 2 consistía en identificar un cero en
cada fila y en cada columna.
Eliminar la fila y la columna a la cual pertenece el cero (0)
identificado, y ver si al finalizar la eliminación se ha hecho
una asignación completa de ceros, o sea, cada origen tiene
asignado un solo destino, y cada destino tiene asignado un
solo origen, lo cual quiere decir que se ha llegado a la
solución óptima.
En caso contrario se tiene que seguir al paso 3.
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Solución del problema. Paso 2
Al ejecutar el paso 2 se tienen las siguientes asignaciones i
a j:
- 1 a 1 (Se elimina la fila 1 y la columna 1), lo que quiere
decir que el operario 1 manejará la máquina 1.
MÁQUINAS
1 2 3 4
1 0 40 130 0
2 80 10 90 0
OPERARIOS
3 60 60 210 0
4 100 0 0 0
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Solución del problema. Paso 2
Al ejecutar el paso 2 se tienen las siguientes asignaciones i
a j:
- 2 a 4 (Se elimina la fila 2 y la columna 4), lo que quiere
decir que el operario 2 manejará la máquina 4.
MÁQUINAS
1 2 3 4
1 0 40 130 0
2 80 10 90 0
OPERARIOS
3 60 60 210 0
4 100 0 0 0
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Solución del problema. Paso 2
Al ejecutar el paso 2 se tienen las siguientes asignaciones i
a j:
- 4 a 2 (Se elimina la fila 4 y la columna 2), lo que quiere
decir que el operario 4 manejará la máquina 2.
MÁQUINAS
1 2 3 4
1 0 40 130 0
2 80 10 90 0
OPERARIOS
3 60 60 210 0
4 100 0 0 0
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Solución del problema. Paso 2
Al terminar de ejecutar el paso 2 se tiene que el operario
3 y la máquina 3 no tienen asignaciones, lo que quiere
decir que no se ha encontrado la solución óptima y debe
seguirse al paso 3.
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Solución del problema. Paso 3
Aplicando el paso 3 se definen el mínimo número de líneas
horizontales y verticales en la última matriz obtenida de
forma tal de cubrir todos los ceros.
Se tiene entonces lo siguiente:
MÁQUINAS
1 2 3 4
1 0 40 130 0
2 80 10 90 0
OPERARIOS
3 60 60 210 0
4 100 0 0 0
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Solución del problema. Paso 3
En esta matriz el menor elemento no cubierto es el x22
cuyo costo asociado es 10.
Se resta este valor a todos los elementos no cubiertos,
obteniéndose entonces lo siguiente:
MÁQUINAS
1 2 3 4
1 0 40 130 0
2 70 0* 80 0
OPERARIOS
3 50 50 200 0
4 100 0 0 0
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Solución del problema. Paso 3
A continuación se suma el elemento (costo= 10) a los
elementos ubicados en las intersecciones de las líneas
trazadas anteriormente, obteniéndose entonces lo
siguiente:
MÁQUINAS
1 2 3 4
1 0 40 130 10
2 70 0* 80 0
OPERARIOS
3 50 50 200 0
4 100 0 0 10
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Solución del problema. Paso 2
Al ejecutar el paso 2 se tienen las siguientes asignaciones i
a j:
- 1 a 1 (Se elimina la fila 1 y la columna 1), lo que quiere
decir que el operario 1 manejará la máquina 1.
MÁQUINAS
1 2 3 4
1 0 40 130 10
2 70 0* 80 0
OPERARIOS
3 50 50 200 0
4 100 0 0 10
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Solución del problema. Paso 2
Al ejecutar el paso 2 se tienen las siguientes asignaciones i
a j:
- 2 a 2 (Se elimina la fila 2 y la columna 2), lo que quiere
decir que el operario 2 manejará la máquina 2.
MÁQUINAS
1 2 3 4
1 0 40 130 10
2 70 0* 80 0
OPERARIOS
3 50 50 200 0
4 100 0 0 10
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Solución del problema. Paso 2
Al ejecutar el paso 2 se tienen las siguientes asignaciones i
a j:
- 3 a 4 (Se elimina la fila 3 y la columna 4), lo que quiere
decir que el operario 3 manejará la máquina 4.
MÁQUINAS
1 2 3 4
1 0 40 130 10
2 70 0* 80 0
OPERARIOS
3 50 50 200 0
4 100 0 0 10
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Solución del problema. Paso 2
Al ejecutar el paso 2 se tienen las siguientes asignaciones i
a j:
- 4 a 3 (Se elimina la fila 4 y la columna 3), lo que quiere
decir que el operario 4 manejará la máquina 3.
MÁQUINAS
1 2 3 4
1 0 40 130 10
2 70 0* 80 0
OPERARIOS
3 50 50 200 0
4 100 0 0 10
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Solución del problema.
Realizados todos los pasos anteriores, se regresa al paso
2 y se chequean las asignaciones i a j:
- 1 a 1 El operario 1 manejará la máquina 1.
- 2 a 2 El operario 2 manejará la máquina 2.
- 3 a 4 El operario 3 manejará la máquina 4.
- 4 a 3 El operario 4 manejará la máquina 3.
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Solución del problema.
Se tiene entonces que el operario 3, que está
asignado a la máquina ficticia 4, queda sin
contraste (sin costo asociado).
Las variables básicas son: x11=1 x22=1 x34=1 x43=1
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Solución del problema.
Las variables básicas son: x11=1 x22=1 x34=1 x43=1
MÁQUINAS
1 2 3 4
1 50 130 190 0
2 130 100 150 0
OPERARIOS 0
3 110 150 270
4 150 90 60 0

Y el costo total será: Z=∑cij.xij=210

MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Solución del problema.
Este mismo costo se puede obtener si se suman todos los
elementos que se restaron en el paso 1 a cada columna y
cada fila, y además se agrega el valor que se restó en el
paso 3 (menor costo no cubierto) que tuvo un valor de 10.
Para el problema estudiado estos valores fueron:
0 para cada fila debido a la columna ficticia agregada y 50
para la columna 1, 90 para la 2, y 60 para la 3.
La suma total dá: 50+90+60+10= 210
 INVESTIGACIÓN DE OPERACIONES

MODELO DE ASIGNACIÓN.
EJEMPLO 2
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Enunciado del problema:
Cinco (5) personas deben ser asignadas en cinco (5)
puestos de trabajo durante dos (2) semanas
consecutivas.
Las utilidades de cada persona en cada puesto de
trabajo durante la primera semana se muestran a
continuación:
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA UTILIZANDO

EL MÉTODO HÚNGARO
Tabla de utilidades
PUESTOS
Personas I II III IV V
1 8 7 9 8 6
2 4 5 3 5 3
3 2 3 4 3 2
4 7 6 8 6 7
5 5 4 4 6 3
Se desea saber las asignaciones a realizar durante la
primera semana, a los fines de obtener la máxima utilidad
posible y a la vez garantizar que para la segunda semana
ninguna persona repita en el mismo puesto.
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Resolución del problema:
Como el problema no es de minimización, sino de
maximizar lo más posible la utilidad, el problema no
es resolver Min Z sino Maz –Z.
Por ello, toda la matriz de costos debe ser multiplicada
por (-1), luego de lo cual se hace exactamente lo
mismo que si el problema fuera de minimización (se
aplica el método húngaro).
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA UTILIZANDO

EL MÉTODO HÚNGARO
Tabla de utilidades multiplicada por (-1)

PUESTOS
Personas I II III IV V
1 -8 -7 -9 -8 -6
2 -4 -5 -3 -5 -3
3 -2 -3 -4 -3 -2
4 -7 -6 -8 -6 -7
5 -5 -4 -4 -6 -3
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOL. ÓPTIMA. MÉTODO HÚNGARO

Solución del problema. Paso 1

Se identifica la menor utilidad de cada fila (las más negativas
en este caso) y se obtienen las diferencias entre la utilidad de
cada elemento y la menor utilidad de cada una de las filas. Si
se aplica esto a cada fila (dado que las utilidades son
menores que cero), se obtiene la siguiente tabla de utilidades:
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA UTILIZANDO

EL MÉTODO HÚNGARO
El menor elemento en cada fila es el siguiente:
PUESTOS Menor elemento
Personas I II III IV V en cada fila
1 -8 -7 -9 -8 -6 -9
2 -4 -5 -3 -5 -3 -5
3 -2 -3 -4 -3 -2 -4
4 -7 -6 -8 -6 -7 -8
5 -5 -4 -4 -6 -3 -6

y si a cada fila se le resta ese elemento, la matriz queda

de la siguiente forma:
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA UTILIZANDO

EL MÉTODO HÚNGARO
PUESTOS
Personas I II III IV V
1 1 2 0 1 3
2 1 0 2 0 2
3 2 1 0 1 2
4 1 2 0 2 1
5 1 2 2 0 3
Ahora se busca el menor elemento en cada columna y
se le resta a todos los elementos de esa columna, dando
como resultado, la siguiente matriz:
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA UTILIZANDO

EL MÉTODO HÚNGARO
El menor elemento en cada columna es el siguiente:
PUESTOS
Personas I II III IV V
1 1 2 0 1 3
2 1 0 2 0 2
3 2 1 0 1 2
4 1 2 0 2 1
5 1 2 2 0 3
Menor elemento
1 0 0 0 1 en cada columna

y si a cada columna se le resta ese elemento, la matriz

queda de la siguiente forma:
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA UTILIZANDO

EL MÉTODO HÚNGARO
PUESTOS
Personas I II III IV V
1 0 2 0 1 2
2 0 0 2 0 1
3 1 1 0 1 1
4 0 2 0 2 0
5 0 2 2 0 2
Ahora se busca el menor elemento en cada columna y
se le resta a todos los elementos de esa columna, dando
como resultado, la siguiente matriz:
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA UTILIZANDO

EL MÉTODO HÚNGARO
Solución del problema. Paso 2
Al ejecutar el paso 2 se tienen las siguientes asignaciones i a j:
- Persona 3 se asigna al puesto III (no tiene otra opción).
PUESTOS
Personas I II III IV V
1 0 2 0 1 2
2 0 0 2 0 1
3 1 1 0 1 1
4 0 2 0 2 0
5 0 2 2 0 2
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA UTILIZANDO

EL MÉTODO HÚNGARO
Solución del problema. Paso 2
Al ejecutar el paso 2 se tienen las siguientes asignaciones i a j:
- Persona 1 se asigna al puesto I (no tiene otra opción).
PUESTOS
Personas I II III IV V
1 0 2 0 1 2
2 0 0 2 0 1
3 1 1 0 1 1
4 0 2 0 2 0
5 0 2 2 0 2
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA UTILIZANDO

EL MÉTODO HÚNGARO
Solución del problema. Paso 2
Al ejecutar el paso 2 se tienen las siguientes asignaciones i a j:
- Persona 4 se asigna al puesto V (no tiene otra opción).
PUESTOS
Personas I II III IV V
1 0 2 0 1 2
2 0 0 2 0 1
3 1 1 0 1 1
4 0 2 0 2 0
5 0 2 2 0 2
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA UTILIZANDO

EL MÉTODO HÚNGARO
Solución del problema. Paso 2
Al ejecutar el paso 2 se tienen las siguientes asignaciones i a j:
- Persona 5 se asigna al puesto IV (no tiene otra opción).
PUESTOS
Personas I II III IV V
1 0 2 0 1 2
2 0 0 2 0 1
3 1 1 0 1 1
4 0 2 0 2 0
5 0 2 2 0 2
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA UTILIZANDO

EL MÉTODO HÚNGARO
Solución del problema. Paso 2
Al ejecutar el paso 2 se tienen las siguientes asignaciones i a j:
- Persona 2 se asigna al puesto II (no tiene otra opción).
PUESTOS
Personas I II III IV V
1 0 2 0 1 2
2 0 0 2 0 1
3 1 1 0 1 1
4 0 2 0 2 0
5 0 2 2 0 2
MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Solución del problema.
Realizados todos los pasos anteriores, se obtuvo que las
asignaciones que maximizan las utilidades son:
- 1 a 1 La persona 1 ocupará el puesto I.
- 2 a 2 La persona 2 ocupará el puesto II.
- 3 a 3 La persona 3 ocupará el puesto III.
- 4 a 5 La persona 4 ocupará el puesto V.
- 5 a 4 La persona 5 ocupará el puesto IV.
 MODELO DE ASIGNACIÓN. MÉTODO HÚNGARO

BÚSQUEDA DE LA SOLUCIÓN ÓPTIMA

UTILIZANDO EL MÉTODO HÚNGARO
Solución del problema.
Se tiene entonces que el máximo valor de Z es: 30,
asociado a las siguientes variables básicas).
Las variables básicas son: x11=1 x22=1 x33=1 x45=1
y x54=1 cuyas utilidades asociadas son:
C11=8 C22=5 C33=4 C45=7 y C54=6