Problema 1
La compañía de manufactura "Jimenez 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:
Método programación lineal
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 Xi,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.
𝑋1,1 + 𝑋1,2 + 𝑋1,3 = 1
𝑋2,1 + 𝑋2,2 + 𝑋2,3 = 1
𝑋3,1 + 𝑋3,2 + 𝑋3,3 = 1
Además debe restringirse el hecho de que cada máquina solo requiere de un equipo de
mantenimiento, por ende
𝑋1,1 + 𝑋2,1 + 𝑋3,1 = 1
𝑋1,2 + 𝑋2,2 + 𝑋3,2 = 1
𝑋_1,3 + 𝑋2,3 + 𝑋3,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).
𝑋𝑖,𝑗 ≥ 0
𝑋𝑖,𝑗 ∈ {𝑍}
Función Objetivo
𝑴𝑰𝑵 𝒁 = 𝟏𝟎𝑿𝟏,𝟏 + 𝟗𝑿𝟏,𝟐 + 𝟓𝑿𝟏,𝟑 + 𝟗𝑿𝟐,𝟏 + 𝟖𝑿𝟐,𝟐 + 𝟑𝑿𝟐,𝟑 + 𝟔𝑿𝟑,𝟏 + 𝟒𝑿𝟑,𝟐
+ 𝟕𝑿𝟑,𝟑
Resultados obtenidos mediante Win QSB
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.
Problema 2
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.
Solució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, 4×4) 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í:
Problema 3
Se cuenta con seis empleados para llevar a cabo cinco tareas. El tiempo (en minutos)
que toma a cada persona realizar cada tarea se da en la tabla siguiente:
El modelo matemático respectivo es:
𝑀𝑖𝑛 22𝑥11 + 18𝑥12 + 21𝑥13 + 18𝑥14 + 18𝑥15 + 18𝑥21 + 23𝑥22 + 27𝑥23 + 22𝑥24 + 22𝑥25
+ 26𝑥31 + 28𝑥32 + 28𝑥33 + 28𝑥34 + 24𝑥35 + 16𝑥41 + 22𝑥42 + 17𝑥43
+ 14𝑥44 + 14𝑥45 + 21𝑥51 + 24𝑥52 + 25𝑥53 + 28𝑥54 + 20𝑥55 + 28𝑥61
+ 25𝑥62 + 28𝑥63 + 28𝑥64 + 30𝑥65
Sujeto a:
𝑥11 + 𝑥12 + 𝑥13 + 𝑥14 + 𝑥15 ≤ 1
𝑥21 + 𝑥22 + 𝑥23 + 𝑥24 + 𝑥25 <= 1
𝑥31 + 𝑥32 + 𝑥33 + 𝑥34 + 𝑥35 <= 1
𝑥41 + 𝑥42 + 𝑥43 + 𝑥44 + 𝑥45 <= 1
𝑥51 + 𝑥52 + 𝑥53 + 𝑥54 + 𝑥55 <= 1
𝑥61 + 𝑥62 + 𝑥63 + 𝑥64 + 𝑥65 <= 1
𝑥11 + 𝑥21 + 𝑥31 + 𝑥41 + 𝑥51 + 𝑥61 = 1
𝑥12 + 𝑥22 + 𝑥32 + 𝑥42 + 𝑥52 + 𝑥62 = 1 𝑥13 + 𝑥23 + 𝑥33 + 𝑥43 + 𝑥53 + 𝑥63 = 1
𝑥13 + 𝑥23 + 𝑥33 + 𝑥43 + 𝑥53 + 𝑥63 = 1
𝑥14 + 𝑥24 + 𝑥34 + 𝑥44 + 𝑥54 + 𝑥64 = 1
𝑥15 + 𝑥25 + 𝑥35 + 𝑥45 + 𝑥55 + 𝑥65 = 1
𝑥43 = 1; 𝑥22 = 0 ; 𝑥53 = 0
donde x_ij=1, si la persona i es asignada a la tarea j, =0, en caso contrario. Salida del
Lindo:
La salida no indica que los operarios 1, 2, 4, 5 y 6 se deben asignar a
las tareas 4, 1, 3, 5 y 2 respectivamente. El operario que se queda sin
asignación es el .el operario 3. Ingresamos la información al WinQSB,
obtenemos la siguiente solución:
La solución indica que las personas 1, 2, 3, 4 y 5 deben realizar las tareas 2,
1, 3, 4 y 5 respectivamente. El operario 6 se queda sin asignación.
Problema 4
El gobierno desea instalar 5 proyectos de inversión (1, 2, 3, 4 y 5) en las regiones A, B,
C, D, E, F y G. Se instala a lo más un proyecto por región. La siguiente tabla muestra la
rentabilidad de la inversión en un horizonte de vida de 5 años (en millones de dólares):
Ingresamos la información de la siguiente manera:
Por lo tanto el proyecto 1, 2, 3, 4 y 5 se asignan a las regiones G, F, E, A y C
respectivamente.
- La rentabilidad total de la inversión es de 170 millones de dólares.
- Las regiones que se quedan sin inversión son la región B y la D.
El modelo matemático es el siguiente:
𝑀𝑎𝑥 40𝑥1𝑎 + 40𝑥1𝑏 + 35𝑥1𝑐 + 45𝑥1𝑑 + 40𝑥1𝑒 + 30𝑥1𝑓 + 50𝑥1𝑔 + 25𝑥2𝑎 + 20𝑥2𝑏 + 25𝑥2𝑐
+ 20𝑥2𝑑 + 25𝑥2𝑒 + 30𝑥2𝑓 + 30𝑥2𝑔 + 10𝑥3𝑎 + 15𝑥3𝑏 + 15𝑥3𝑐 + 10𝑥3𝑑
+ 20𝑥3𝑒 + 15𝑥3𝑓 + 20𝑥3𝑔 + 35𝑥4𝑎 + 30𝑥4𝑏 + 30𝑥4𝑐 + 35𝑥4𝑑 + 30𝑥4𝑒
+ 25𝑥4𝑓 + 30𝑥4𝑔 + 30𝑥5𝑎 + 25𝑥5𝑏 + 35𝑥5𝑐 + 30𝑥5𝑑 + 30𝑥5𝑒 + 30𝑥5𝑓
+ 35𝑥5𝑔
Sujeto a:
𝑥1𝑎 + 𝑥1𝑏 + 𝑥1𝑐 + 𝑥1𝑑 + 𝑥1𝑒 + 𝑥1𝑓 + 𝑥1𝑔 = 1
𝑥2𝑎 + 𝑥2𝑏 + 𝑥2𝑐 + 𝑥2𝑑 + 𝑥2𝑒 + 𝑥2𝑓 + 𝑥2𝑔 = 1
𝑥3𝑎 + 𝑥3𝑏 + 𝑥3𝑐 + 𝑥3𝑑 + 𝑥3𝑒 + 𝑥3𝑓 + 𝑥3𝑔 = 1
𝑥4𝑎 + 𝑥4𝑏 + 𝑥4𝑐 + 𝑥4𝑑 + 𝑥4𝑒 + 𝑥4𝑓 + 𝑥4𝑔 = 1
𝑥5𝑎 + 𝑥5𝑏 + 𝑥5𝑐 + 𝑥5𝑑 + 𝑥5𝑒 + 𝑥5𝑓 + 𝑥5𝑔 = 1
𝑥1𝑎 + 𝑥2𝑎 + 𝑥3𝑎 + 𝑥4𝑎 + 𝑥5𝑎 <= 1 𝑥1𝑏 + 𝑥2𝑏 + 𝑥3𝑏 + 𝑥4𝑏 + 𝑥5𝑏 <= 1
𝑥1𝑏 + 𝑥2𝑏 + 𝑥3𝑏 + 𝑥4𝑏 + 𝑥5𝑏 <= 1
𝑥1𝑐 + 𝑥2𝑐 + 𝑥3𝑐 + 𝑥4𝑐 + 𝑥5𝑐 <= 1
𝑥1𝑑 + 𝑥2𝑑 + 𝑥3𝑑 + 𝑥4𝑑 + 𝑥5𝑑 <= 1 𝑥1𝑒 + 𝑥2𝑒 + 𝑥3𝑒 + 𝑥4𝑒 + 𝑥5𝑒 <= 1
𝑥1𝑒 + 𝑥2𝑒 + 𝑥3𝑒 + 𝑥4𝑒 + 𝑥5𝑒 <= 1
𝑥1𝑓 + 𝑥2𝑓 + 𝑥3𝑓 + 𝑥4𝑓 + 𝑥5𝑓 <= 1
𝑥1𝑔 + 𝑥2𝑔 + 𝑥3𝑔 + 𝑥4𝑔 + 𝑥5𝑔 <= 1
𝑥3𝑎 = 0 ; 𝑥4𝑒 = 1
𝑖𝑛𝑡 35 𝑑𝑜𝑛𝑑𝑒 𝑋𝑖𝑗 = 1
si el proyecto i es asignado a la región j; =0, en caso contrario. Ingresando datos al
Lindo
Por lo tanto, los proyectos 1, 2, 3, 4 y 5 se deberán asignar a las regiones G,
F, B, E y C respectivamente. La rentabilidad de la inversión es 160 millones de
dólares. Las regiones que se quedan sin inversión son A y D.
