RESOLUCIÓN DE UN PROBLEMA DE
MAXIMIZACIÓN MEDIANTE EL
MÉTODO HÚNGARO
EL PROBLEMA
Una organización de recolección de café cuenta con tres equipos de siembra y
cosecha del mismo (equipos 1, 2, 3). Estos equipos de trabajo se encuentran
entrenados para trabajar en condiciones particulares del proceso, condiciones
como lo son el tipo de suelo, las condiciones del clima y el tipo de grano.
La organización cuenta con cuatro terrenos disponibles para efectuar el
proceso de siembra y cosecha (terrenos A, B, C, D), estos terrenos tienen
condiciones particulares de suelo, clima y tipo de grano. Cada equipo cuenta
con la capacidad de efectuar el proceso en solo uno de los terrenos
disponibles, salvo el equipo 2, que cuenta con una serie de herramientas
tecnológicas que le permiten realizar la siembra y cosecha del grano en dos de
los terrenos disponibles.
Se ha contratado a un Ingeniero Industrial con el objetivo de realizar las
asignaciones precisas que maximicen la cantidad de sacos de café cosechados
en total. El siguiente tabulado muestra la capacidad (en cientos de sacos) de
cosecha de café de cada uno de los equipos dependiendo de cada uno de los
terrenos.
RESOLUCIÓN
En este problema debemos recordar un concepto fundamental para la
aplicación del método húngaro, este concepto nos dice que el número de filas
debe ser exactamente igual al número de columnas. Por ende, la acción a
realizar debería ser crear un equipo ficticio, el cual nos deje el tabulado
balanceado y a este asignarle un número de sacos cosechados equivalente a
cero en cada uno de los terrenos. Sin embargo el problema nos indica que uno
de los equipos se encuentra en capacidad de que se le asignen dos terrenos,
en este caso crearemos un equipo 2 alternativo (Equipo 2B) el cual nos
balanceará el tabulado y nos hará prescindir del equipo ficticio pensado
inicialmente. A este equipo 2B que crearemos le corresponderá la misma
capacidad de cosecha del equipo 2 (en adelante equipo 2A) según el terreno,
lógicamente.
Una vez balanceado el tabulado debemos de cuestionarnos acerca del criterio
de optimización, pues recordemos que el método húngaro se encuentra
diseñado para ejercicios de minimización. En este caso nuestro objetivo es
maximizar, por lo que tendremos que aplicar un paso adicional.
Lo primero que debemos hacer es ubicar el mayor valor del tabulado inicial.
En este caso este valor es 15, por lo cual procederemos a realizar la siguiente
operación con cada uno de los valores:
Restaremos a 15, el valor de cada una de las celdas y este valor quedará en
cada una de las celdas correspondientes.
Ahora nuestro tabulado inicial quedará de la siguiente manera:
A partir de este tabulado ya podemos aplicar el algoritmo del método húngaro
como se aplicaría en un caso e minimización (normalmente).
Ahora encontramos el menor elemento de cada fila.
y se lo restamos a todas las celdas de la fila.
Ahora efectuamos este mismo paso, pero esta vez con las columnas. Elegimos
el menor de los valores de cada columna y se lo restamos a cada una de las
celdas de la columna correspondiente.
Ahora procedemos a cubrir la mayor cantidad de ceros, con la menor cantidad
de líneas, si el número de líneas que empleemos es igual al grado de la matriz
(en este caso matriz grado 4, 4x4) habremos llegado al final del ejercicio.
Dado que el número de líneas es igual al grado de la matriz, hemos concluido
el algoritmo. Lo único que quedará será asignar a cada equipo el terreno en el
que el intercepto es igual a 0 (cero).
Las asignaciones, como es lógico deberán iniciarse por el equipo al cual solo
corresponda un terreno, en este caso al Equipo 3 le corresponde el Terreno A.
De esta manera al Equipo 1 le corresponde el Terreno D. Mientras tanto el
Equipo 2 se encargará de la cosecha en los terrenos B y C. Según el tabulado
del problema (recordemos que es de maximización), la cantidad de sacos
(expresada en cientos de sacos) será así:
RESOLUCIÓN DE UN PROBLEMA DE
ASIGNACIÓN MEDIANTE
PROGRAMACIÓN LINEAL
EL PROBLEMA
La compañía de manufactura "Jiménez y Asociados" desea realizar una
jornada de mantenimiento preventivo a sus tres máquinas principales A, B y C.
El tiempo que demanda realizar el mantenimiento de cada máquina es de 1
día, sin embargo la jornada de mantenimiento no puede durar más de un día,
teniendo en cuenta que la compañía cuenta con tres proveedores de servicios
de mantenimiento debe de asignarse un equipo de mantenimiento a cada
máquina para poder cumplir con la realización del mantenimiento preventivo.
Teniendo en cuenta que según el grado de especialización de cada equipo
prestador de servicios de mantenimiento el costo de la tarea varía para cada
máquina en particular, debe de asignarse el equipo correcto a la máquina
indicada con el objetivo de minimizar el costo total de la jornada. Los costos
asociados se pueden observar en la siguiente tabla:
VARIABLES DE DECISIÓN
Las variables de decisión de este tipo de problemas es igual a las variables de
cualquier modelo de transporte tradicional, es decir variables X i,j donde i
{Equipo de mantenimiento 1,2,3} y j {Máquina 1,2,3}, y corresponden a
variables binarias en las cuales el valor 1 significa la asignación de un equipo
de mantenimiento a una máquina en particular.
RESTRICCIONES
Dado que un equipo de mantenimiento no puede ser asignado a más de una
maquinaria, esta característica debe de restringirse mediante las siguientes
inecuaciones.
X1,1 + X1,2 + X1,3 = 1
X2,1 + X2,2 + X2,3 = 1
X3,1 + X3,2 + X3,3 = 1
Además debe restringirse el hecho de que cada máquina solo requiere de un
equipo de mantenimiento, por ende
X1,1 + X2,1 + X3,1 = 1
X1,2 + X2,2 + X3,2 = 1
X1,3 + X2,3 + X3,3 = 1
Además se hace necesario que para efectos de resolución en cualquier
paquete de herramientas se especifique que estas variables corresponden al
conjunto de los enteros (por obvias razones) y que deben ser mayores que
cero (dado que es un problema de minimización esta restricción se hace muy
necesario).
Xi,j ≥ 0
Xi,j ∈ {Z}
FUNCIÓN OBJETIVO
ZMIN = 10X1,1 + 9X1,2 + 5X1,3 + 9X2,1 + 8X2,2 + 3X2,3 + 6X3,1 + 4X3,2 + 7X3,3
INGRESANDO LOS DATOS A WINQSB
RESULTADOS OBTENIDO MEDIANTE EL WINQSB
Por ende la asignación que representa el menor costo para la jornada de
mantenimiento preventivo determina que el Equipo 1 realice el mantenimiento
de la Máquina 1, el Equipo 2 realice el mantenimiento de la Máquina 3 y el
Equipo 3 realice el mantenimiento de la Máquina 2, jornada que tendrá un
costo total de 17 unidades monetarias.
RESOLUCIÓN DE UN PROBLEMA DE
ASIGNACIÓN MEDIANTE WINQSB -
NETWORK MODELING
La facilidad de resolver un problema de asignación mediante WinQSB es aún
mayor a la que se incurre mediante programación lineal, y esta metodología
justifica el pensar en que el método húngaro es sumamente anacrónico
únicamente contemplado para fines históricos y académicos. En el módulo
NETWORK MODELING del paquete de herramientas WinQSB se puede
resolver el modelo tan solo traspasando los costos de una matriz n*m a otra
que brinda el módulo n*m.
INGRESANDO LOS DATOS A WINQSB -
NETWORK MODELING
RESULTADOS OBTENIDOS MEDIANTE WINQSB -
NETWORK MODELING
Por ende la asignación que representa el menor costo para la jornada de
mantenimiento preventivo determina que el Equipo 1 realice el mantenimiento
de la Máquina 1, el Equipo 2 realice el mantenimiento de la Máquina 3 y el
Equipo 3 realice el mantenimiento de la Máquina 2, jornada que tendrá un
costo total de 17 unidades monetarias.
De esta manera se hace evidente cual es la alternativa predilecta para resolver
problemas de asignación.
Investigación de Operaciones
o Programación Lineal
o Ejercicios de programación lineal
o Ejercicios de programación lineal - 2
o Ejercicios de programación lineal - 3
o Programación Lineal en WinQSB
o Programación Lineal en Solver
o Programación Lineal en Tora
o Programación Lineal en Lingo
o Método Gráfico
o Método Simplex
o Problema del Transporte o Distribución
o Método de Aproximación de Vogel
o Dualidad en Programación Lineal
o Método del Costo Mínimo
o Problema del Transporte en WinQSB
o Método de la Esquina Noroeste
o Problema de Transbordo
o Variables Binarias - El Caso de la Bauxita
o Problemas de Asignación
o Problema del Agente Viajero - TSP
o Teoría de Redes
o CPM - Metodo de la Ruta Critica
o Modelos CPM en WinQSB
o PERT - Tecnica de evaluacion y revision de proyectos
o Descargas y multimedia
Producción
Estudio del Trabajo
Ingeniería de Metodos
Estudio de Tiempos
Salud Ocupacional
Pronóstico de Ventas
Logística
Administración de Inventarios
Gestión de Almacenes
Medios y Gestión del Transporte
Diseño y Distribución en Planta
Procesos Industriales
Gestión y Control de Calidad
Lean Manufacturing
Administración de Recursos Humanos
Mantenimiento
Educación financiera
Ocio
Donde estudiar Ingenieria Industrial?
Con la tecnología de Traductor de Google
Comparte conocimiento...
Modelos de Programación Entera
Problema Asignación: Una universidad está programando las clases para el próximo
semestre académico y requiere buscar la mejor asignación posible de profesores a los
distintos cursos que se deben dictar. Considere que existen 5 profesores: A, B, C, D, E y 5
cursos (asignaturas): C1, C2, C3, C4, C5. Adicionalmente, los profesores han manifestado
sus preferencias por dictar los distintos cursos en una escala de 1 a 10, donde 10 es la
máxima puntuación y 1 la mínima puntuación o preferencia. Se asume que cada profesor es
apto para dictar cualquier curso, independiente del puntaje de su preferencia. La siguiente
tabla resume las puntuaciones que asigna cada profesor a cada curso:
PROFESORES
CURSOS A B C D E
C1 5 8 5 9 7
C2 7 2 3 6 8
C3 9 10 8 9 8
C4 8 7 9 7 8
C5 6 9 9 10 5
Se ha establecido como criterio que cada profesor debe dictar sólo un curso y a la vez que
cada curso obviamente debe tener un profesor. En base a lo anterior se desea encontrar la
asignación de profesores que maximize el total de las preferencias.
Variables de Decisión:
Función Objetivo: Maximizar el total de las preferencias de los profesores
Donde P(i,j) corresponde a una forma sintética de resumir los parámetros del modelo, es
decir, P(i,j) es la preferencia del profesor i (en una escala de 1 a 10) por dictar el curso j. Por
ejemplo, P(D,C3)=9.
Restricciones:
Verifique utilizando Solver de Excel que la solución óptima de este problema es asignar el
profesor A a C3, B a C5, C a C4, D a C1 y E a C2. Valor Óptimo = 44.
Problema Inclusión Costos Fijos: Usted ha sido designado por el gerente de su empresa
para decidir cómo distribuirá su tráfico telefónico en el próximo mes, seleccionando entre 3
proveedores posibles y asignando la cantidad de tráfico (minutos) que desee en cada caso,
es decir, puede repartir el tráfico en 1, 2 o 3 proveedores a su antojo y su decisión sólo
dependerá de los costos de cada alternativa.
El proveedor 1 cobra un cargo fijo mensual de US$50 y el costo por minuto a red fija es de
US$0,02 y a celular de US$0,12. El proveedor 2 tiene un cargo fijo mensual de US$60, con
un costo por minuto de US$0,015 y US$0,15 a red fija y celular respectivamente. Finalmente
el proveedor 3 tiene un cargo fijo mensual de US$40 con un costo por minuto a red fija de
US$0,03 y a celular de US$0,14. Si usted llama por uno de estos proveedores (aunque hable
sólo un minuto) deberá pagar el cargo fijo. Asuma que la cantidad de minutos que la
empresa consume mensualmente es de 30.000 para red fija y 18.000 para celular. Formule
y resuelva un modelo de Programación Entera que permita decidir cómo distribuir
el tráfico telefónico mensual de la forma más económica para la empresa.
