TecnológicoNacionaldeMéxico
Instituto Tecnológico De Tijuana
Subdirección Académica
Departamento De Ingeniería Industrial
Carrera:
Ing. Industrial
Materia:
Investigacion de Operciones
Título:
Problema de asignación
Fecha de entrega:
11 de diciembre del 2023
Nombre Y Número De Control Del Alumno:
Basni Vetvirai Serrano Lopez 22210256
Nombre Del Maestro (A):
Ing. Alejandra Arana Lugo
viernes 09 de diciembre de 2023
1
Introducción
En este proyecto integrador se mostrará un problema aplicado en la vida real,
y es de asignación, para entrar en materia se debe decir hablar un poco de historia.
El problema de asignación tuvo su origen en la revolución industrial, ya que el
surgimiento de las máquinas hizo que fuera necesario asignar una tarea a un
trabajador. Pero no es hasta 1955 cuando Harold W. Kuhn plantea el Método
húngaro, es muy importante decir que el problema de asignación consiste en
encontrar la forma de asignar ciertos recursos disponibles (máquinas o personas)
para la realización de determinadas tareas al menor coste, suponiendo que cada
recurso se destina a una sola tarea, y que cada tarea es ejecutada por uno solo de
los recursos, por lo cual se abordará una solución por medio del método Hungaro
que es un método de optimización de problemas de asignación, conocido como tal
gracias a que los primeros aportes al método clásico definitivo fueron de Dénes
König y Jenő Egerváry dos matemáticos húngaros. El algoritmo que se detalla a
continuación está diseñado para la resolución de problemas de minimización
únicamente, para reducir el costo, el propósito la presentación de este proyecto es
mostrar al lector por medio del modelo de asignación como se puede plantear un
problema en la vida real y muestra un claro ejemplo de las soluciones que se
pueden optar para la resolución de alguna problemática de este tipo, este proyecto
integrador impacta en la investigación de operaciones porque lleva los principios y
reglas de lo que es asignación, es muy importante tener el conocimiento para este
tipo de problemas, que muy frecuentemente se viven o suelen presentarse en las
industrias, pues muchas veces se necesita llegar a una asignación correcta y sobre
todo óptima del personal a diferentes tareas o trabajos a realizar, pero como es el
objetivo de este modelo obtener ese resultado al menor costo.
2
Desarrollo
El modelo de asignación es un tipo especial de problema de programación
lineal en el que los asignados son recursos que se destinan a la realización de
tareas. Por ejemplo, los asignados pueden ser empleados a quienes se tiene que
dar trabajo. La asignación de personas a trabajos es una aplicación común del
problema de asignación. Sin embargo, los asignados no tienen que ser personas.
También pueden ser máquinas, vehículos o plantas, o incluso periodos a los que se
asignan tareas.
El objetivo del modelo es determinar la asignación óptima (de costo mínimo) de
trabajadores a puestos.
Metodo hungaro
El método Húngaro es un método de optimización de problemas de asignación,
conocido como tal gracias a que los primeros aportes al método clásico definitivo
fueron de Dénes König y Jenő Egerváry dos matemáticos húngaros. El algoritmo tal
como se detallará a continuación está diseñado para la resolución de problemas de
minimización únicamente.
Este método fue desarrollado por el matemático hungaro D. Konig. Por esta razón,
se le conoce como el método hungaro para problemas de asignación. También es
conocido como algoritmo de asignación de Kuhn-Munkres.
Una de las características más importantes del problema de asignación es que solo
se asigna un trabajo (o trabajador) a una máquina (o proyecto).
3
Problema formulado
En un negocio de ventas de tamales se necesita realizar 5 tareas diferentes para
llevar a cabo la realización de la producción, la dueña contrato a 5 empleados para
que cada uno realice una sola tarea, para lo cual se dispone de los costos
asociados a que cada empleado realice la actividad en la siguiente tabla, la dueña le
pide de su ayuda para encontrar la asignación de costo mínimo.
Actividad Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5
Empleado
Empleado 1 150 160 140 100 120
Empleado 2 130 170 110 120 150
Empleado 3 140 150 130 120 140
Empleado 4 130 180 120 100 160
Empleado 5 150 160 150 130 130
Paso 1: Identificar el elemento menor de cada fila y restarlos todos los elementos de
la misma fila.
Actividad Tarea Tarea 2 Tarea 3 Tarea 4 Tarea 5 Elemento
Empleado 1 menor de
la fila
Empleado 1 150 160 140 100 120 100
Empleado 2 130 170 110 120 150 110
Empleado 3 140 150 130 120 140 120
Empleado 4 130 180 120 100 160 100
Empleado 5 150 160 150 130 130 130
4
Paso 2: Construimos una nueva matriz con las diferencias entre los valores de la
matriz original y el elemento menor de la fila a la cual corresponde.
Actividad Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5
Empleado
Empleado 1 50 60 40 0 20
Empleado 2 20 60 0 10 40
Empleado 3 20 30 10 0 20
Empleado 4 30 80 20 0 60
Empleado 5 20 30 20 0 0
Paso 3: Identificar el elemento menor de cada columna y restarlos todos los
elementos de la misma columna.
Actividad Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5
Empleado
Empleado 1 50 60 40 0 20
Empleado 2 20 60 0 10 40
Empleado 3 20 30 10 0 20
Empleado 4 30 80 20 0 60
Empleado 5 20 30 20 0 0
Elemento 20 30 0 0 0
menor de la
columna
5
Paso 4: Construimos una nueva matriz con las diferencias entre los valores de la
matriz original y el elemento menor de la columna a la cual corresponde.
Actividad Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5
Empleado
Empleado 1 30 30 40 0 20
Empleado 2 0 30 0 10 40
Empleado 3 0 0 10 0 20
Empleado 4 10 50 20 0 60
Empleado 5 0 0 20 0 0
Paso 5: Localiza el elemento más pequeño de la tabla (sin tomar en cuenta los
ceros).
Actividad Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5
Empleado
Empleado 1 30 30 40 0 20
Empleado 2 0 30 0 10 40
Empleado 3 0 0 10 0 20
Empleado 4 10 50 20 0 60
Empleado 5 0 0 20 0 0
Paso 6: Restamos a toda toda la tabla el elemento más pequeño.
Actividad Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5
Empleado
Empleado 1 20 20 30 0 10
Empleado 2 0 20 0 0 30
Empleado 3 0 0 0 0 10
Empleado 4 0 40 10 0 50
Empleado 5 0 0 10 0 0
6
Paso 7: Realizamos la asignación (sumamos los valores que correspondan a
empleado, tarea).
Identificamos los ceros en las celdas y respecto a ellos realizamos la asignación
Por ejemplo:
Al empleado 1 al tener un cero en la tarea 4,es la que debe realizar con el fin de
minimizar costos.
Actividad Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5
Empleado
Empleado 1 20 20 30 0 10
El empleado 4 tiene dos opciones pero la tarea número 4 ya fue asignada al
empleado 1, por lo tanto se le asigna la tarea 1
Actividad Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5
Empleado
Empleado 4 0 40 10 0 50
El empleado 2 tiene tres opciones para ser asignado, pero la tarea 1 y 4 ya fueron
asignadas, por lo tanto se le asigna la tarea 3
Actividad Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5
Empleado
Empleado 2 0 20 0 0 30
El empleado 3 cuenta con 4 opciones, pero las tares 4,3,1 ya fueron asignadas, por
lo tanto se le asigna la tarea 2
Actividad Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5
Empleado
Empleado 3 0 0 0 0 10
7
El empleado 5 tiene 4 opciones para asignar, más sin embargo la tarea 1,2,4 ya
fueron asignadas anteriormente, por lo tanto se le asigna la tarea 5.
Actividad Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5
Empleado
Empleado 5 0 0 10 0 0
Tabla con las asignaciones
Actividad Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5
Empleado
Empleado 1 20 20 30 0 10
Empleado 2 0 20 0 0 30
Empleado 3 0 0 0 0 10
Empleado 4 0 40 10 0 50
Empleado 5 0 0 10 0 0
Por lo tanto las asignaciones quedan de la siguiente manera:
Empleado 1= Tarea 4
Empleado 2= Tarea 3
Empleado 3= Tarea 2
Empleado 4= Tarea 1
Empleado 5= Tarea 5
Hacemos la sumatoria de los costos por cada actividad par asi obtener el costo
mínimo.
Total= 100+110+150+130+130=620
8
Conclusión
Como conclusión, esta práctica integradora me sirvió mucho en comprender
cómo plantear un problema de asignación en la vida real, utilizando el conocimiento
previamente aprendido en clase sobre hablando en temas de la programación lineal,
también me llevo a encontrar e identificar las herramientas para llegar a una
solución o posibles soluciones óptimas y sobre todo real, ya que en este presente
trabajo se lleva a cabo un problema de asignación y presenta detalladamente los
pasos que son necesarios para llegar a una posible solución o más soluciones que
representen el costo mínimo, pues cabe decir que en este modelo el objetivo es
determinar la asignación óptima de costo mínimo esto aplica para personal a
máquinas, vendedores a zonas, personal a honorarios entre otras más, sin embargo
en este problema planteado es para empleados a tareas, para la resolución de este
planteamiento se llevó a cabo mediante el método hungaro que es un algoritmo de
optimización desarrollado por el matemático hungaro D. Konig con la función de
encontrar el costo mínimo que es el objetivo claro dentro de una empresa o dueño el
cual es siempre encontrar la solución que represente el costo menor, cabe
mencionar que una de las características más importante de este modelo es que
una sola tarea (trabajo) se puede asignar a una sola persona (trabajador)asi como
tambien tiene la particular característica que para su resolución no se hace
necesario que el número de fuentes sea igual al número de destinos, estos tipos de
problemas se ven dentro de la vida diaria y más a menudo en las industrias, pues es
una de las herramientas que llega a ocupar un ingeniero industrial, por lo cual estoy
segura que estos problemas serán muy relevante y útiles en el ambiente laboral.
9
Referencias bibliográficas
(S/f-c). [Link]. Recuperado el 11 de diciembre de 2023, de
[Link]
a/2019/[Link]
METODO [Link]. (s/f). [Link]. Recuperado el 11 de
diciembre de 2023, de
[Link]
MODELO DE ASIGNACIÓN. (2016, noviembre 9). Investigación de
Operaciones.
[Link]
imera-entrada-del-blog/
10
