Problema del transporte o
distribución
El problema del transporte o distribución, es un problema de
redes especial en programación lineal que se funda en la necesidad de llevar
unidades de un punto específico llamado fuente u origen hacia otro punto específico llamado destino.
Los principales objetivos de un modelo de transporte son la satisfacción de
todos los requerimientos establecidos por los destinos, y claro está, la
minimización de los costos relacionados con el plan determinado por las rutas
escogidas.
El procedimiento de resolución de un modelo de transporte se
puede llevar a cabo mediante programación lineal común, sin embargo su
estructura permite la creación de múltiples alternativas de solución tales como
la estructura de asignación o los métodos heurísticos más populares como Vogel,
Esquina Noroeste o Mínimos Costos.
Método de
aproximación de vogel
El método de aproximación de Vogel es un método heurístico
de resolución de problemas de transporte capaz de alcanzar una solución básica
no artificial de inicio, este modelo requiere de la realización de un número
generalmente mayor de iteraciones que los demás métodos heurísticos existentes
con este fin, sin embargo producen mejores resultados iniciales que los mismos.
Algoritmo de vogel
El método consiste en la realización de un algoritmo que
consta de 3 pasos fundamentales y 1 más que asegura el ciclo hasta la
culminación del método.
Paso 1
Determinar para cada fila y columna una medida de penalización restando
los dos costos menores en filas y columnas.
Paso 2
Escoger la fila o columna con la mayor penalización, es decir que de la
resta realizada en el "Paso 1" se debe escoger el número mayor. En
caso de haber empate, se debe escoger arbitrariamente (a juicio personal).
Paso 3
De la fila o columna de mayor penalización determinada en el paso
anterior debemos de escoger la celda con el menor costo, y en esta asignar la
mayor cantidad posible de unidades. Una vez se realiza este paso una oferta o
demanda quedará satisfecha por ende se tachará la fila o columna, en caso de
empate solo se tachará 1, la restante quedará con oferta o demanda igual a cero
(0).
Paso 4: de ciclo y excepciones
- Si queda sin tachar exactamente una fila o columna con cero oferta o
demanda, detenerse.
- Si queda sin tachar una fila o columna con oferta o demanda positiva,
determine las variables básicas en la fila o columna con el método de costos
mínimos, detenerse.
- Si todas las filas y columnas que no se tacharon tienen cero oferta y
demanda, determine las variables básicas cero por el método del costo mínimo,
detenerse.
- Si no se presenta ninguno de los casos anteriores vuelva al paso 1
hasta que las ofertas y las demandas se hayan agotado.
Ejemplo del método de
aproximación de vogel.
Por medio de este método resolveremos
el ejercicio de transporte resuelto en módulos anteriores mediante
programación lineal.
El problema
Una empresa energética colombiana
dispone de cuatro plantas de generación para satisfacer la demanda diaria
eléctrica en cuatro ciudades, Cali, Bogotá, Medellín y Barranquilla. Las
plantas 1,2,3 y 4 pueden satisfacer 80, 30, 60 y 45 millones de KW al día
respectivamente. Las necesidades de las ciudades de Cali, Bogotá, Medellín y
Barranquilla son de 70, 40, 70 y 35 millones de Kw al día respectivamente.
Los costos asociados al envío de suministro energético por cada millón de KW
entre cada planta y cada ciudad son los registrados en la siguiente tabla.
Formule un modelo de
programación lineal que permita satisfacer las necesidades de todas las
ciudades al tiempo que minimice los costos asociados al transporte.
Solución paso a paso
El primer paso es
determinar las medidas de penalización y consignarlas en el tabulado de costos,
tal como se muestra a continuación.
El
paso siguiente es escoger la mayor penalización, de esta manera:
El paso siguiente es
escoger de esta columna el menor valor, y en una tabla paralela se le asigna la
mayor cantidad posible de unidades, podemos observar como el menor costo es
"2" y que a esa celda se le pueden asignar como máximo 60 unidades
"que es la capacidad de la planta 3".
Dado que la fila de la "Planta
3" ya ha asignado toda su capacidad (60 unidades) esta debe desaparecer.
Se ha llegado al final
del ciclo, por ende se repite el proceso
Al finalizar esta
iteración podemos observar como el tabulado queda una fila sin tachar y con
valores positivos, por ende asignamos las variables básicas y hemos concluido
el método.
Los costos asociados a la
distribución son:
Método de la esquina
noroeste
El método de la esquina Noroeste es
un algoritmo heurístico capaz de solucionar problemas de transporte o
distribución, mediante la consecución de una solución básica inicial que
satisfaga todas las restricciones existentes, sin que esto implique que se
alcance el costo óptimo total.
Algoritmo de resolución de
la esquina noroeste
Se parte por esbozar en forma matricial el problema, es decir, filas que
representen fuentes y columnas que representen destinos, luego el algoritmo
debe de iniciar en la celda, ruta o esquina Noroeste de la tabla (esquina
superior izquierda).
Paso 1:
En la celda seleccionada como esquina Noroeste se debe asignar la máxima
cantidad de unidades posibles, cantidad que se ve restringida ya sea por las
restricciones de oferta o de demanda. En este mismo paso se procede a ajustar
la oferta y demanda de la fila y columna afectada, restándole la cantidad
asignada a la celda.
Paso 2:
En este paso se procede a eliminar la fila o destino cuya oferta o
demanda sea 0 después del "Paso 1", si dado el caso ambas son cero
arbitrariamente se elige cual eliminar y la restante se deja con demanda u
oferta cero (0) según sea el caso.
Paso 3:
Una vez en este paso existen dos posibilidades, la primera que quede un
solo renglón o columna, si este es el caso se ha llegado al final el método,
"detenerse".
La segunda es que quede más de un renglón o columna, si este es el caso
iniciar nuevamente el "Paso 1".
Por
medio de este método resolveremos el problema de transporte propuesto y
resuelto en módulos anteriores mediante programación lineal.
El problema
Una
empresa energética colombiana dispone de cuatro plantas de generación para
satisfacer la demanda diaria eléctrica en cuatro ciudades, Cali, Bogotá,
Medellín y Barranquilla. Las plantas 1,2,3 y 4 pueden satisfacer 80, 30, 60 y
45 millones de KW al día respectivamente. Las necesidades de las ciudades de
Cali, Bogotá, Medellín y Barranquilla son de 70, 40, 70 y 35 millones de KW al
día respectivamente.
Los
costos asociados al envío de suministro energético por cada millón de KW entre
cada planta y cada ciudad son los registrados en la siguiente tabla.
Formule un modelo de
programación lineal que permita satisfacer las necesidades de todas las
ciudades al tiempo que minimice los costos asociados al transporte.
Solución paso a paso
Ahora la cantidad
asignada a la esquina noroeste es restada a la demanda de Cali y a la oferta de
la "Planta 1", en un procedimiento muy lógico. Dado que la demanda de
Cali una vez restada la cantidad asignada es cero (0), se procede a eliminar la
columna. El proceso de asignación nuevamente se repite.
Continuamos con las
iteraciones.
En este caso nos
encontramos frente a la elección de la fila o columna a eliminar (tachar), sin
embargo podemos utilizar un criterio mediante el cual eliminemos la fila o
columna que presente los costos más elevados. En este caso la "Planta
2".
Nueva iteración.
Una vez finalizada esta
asignación, se elimina la "Planta 3" que ya ha sido satisfecha con la
asignación de 60 unidades, por ende nos queda una sola fila a la cual le
asignamos las unidades estrictamente requeridas y hemos finalizado el método.
El cuadro de las
asignaciones (que debemos desarrollarlo paralelamente) queda así:
Los costos asociados a
la distribución son:
El
costo total es evidentemente superior al obtenido mediante Programación
Lineal y el Método
de Aproximación de Vogel, lo cual demuestra lo enunciado en la
descripción del algoritmo que cita que no obtiene siempre la mejor solución,
sin embargo presenta un cumplimiento de todas las restricciones y una rapidez
de elaboración, lo cual es una ventaja en problemas con innumerables fuentes y
destinos en los cuales no nos importe más que satisfacer las restricciones
Método del costo mínimo
El método del costo mínimo o método
de los mínimos costos es un algoritmo desarrollado con el objetivo de resolver
problemas de transporte o distribución, arrojando mejores resultados que
métodos como el de la esquina noroeste, dado que se enfoca en las rutas que
presentan menores costos.
El diagrama de flujo de este
algoritmo es mucho más sencillo que los anteriores, dado que se trata
simplemente de la asignación de la mayor cantidad de unidades posibles
(sujeta a las restricciones de oferta y/o demanda) a la celda menos costosa de
toda la matriz hasta finalizar el método.
Algoritmo del costo mínimo
Paso 1:
De la matriz se elige la ruta (celda) menos
costosa (en caso de un empate, este se rompe arbitrariamente) y se le asigna la
mayor cantidad de unidades posible, cantidad que se ve restringida ya sea por
las restricciones de oferta o de demanda. En este mismo paso se procede a
ajustar la oferta y demanda de la fila y columna afectada, restándole la
cantidad asignada a la celda.
Paso 2:
En este paso se procede a eliminar la fila o
destino cuya oferta o demanda sea 0 después del "Paso 1", si dado el
caso ambas son cero arbitrariamente se elige cual eliminar y la restante se
deja con demanda u oferta cero (0) según sea el caso.
Paso 3:
Una vez en este paso existen dos
posibilidades, la primera que quede un solo renglón o columna, si este es el
caso se ha llegado al final el método, "detenerse".
La segunda es que quede más de un renglón o
columna, si este es el caso iniciar nuevamente el "Paso 1".
Ejemplo del método del costo mínimo
Por medio de este método
resolveremos el problema de transporte propuesto y resuelto en módulos
anteriores mediante programación lineal.
El problema
Una empresa energética
colombiana dispone de cuatro plantas de generación para satisfacer la demanda
diaria eléctrica en cuatro ciudades, Cali, Bogotá, Medellín y Barranquilla. Las
plantas 1,2,3 y 4 pueden satisfacer 80, 30, 60 y 45 millones de KW al día
respectivamente. Las necesidades de las ciudades de Cali, Bogotá, Medellín y
Barranquilla son de 70, 40, 70 y 35 millones de KW al día respectivamente.
Los costos asociados al
envío de suministro energético por cada millón de KW entre cada planta y cada
ciudad son los registrados en la siguiente tabla.
Formule un modelo de
programación lineal que permita satisfacer las necesidades de todas las
ciudades al tiempo que minimice los costos asociados al transporte.
SOLUCIÓN PASO A PASO
Luego esa cantidad asignada
se resta a la demanda de Bogotá y a la oferta de la "Planta 3", en un
proceso muy lógico. Dado que Bogotá se queda sin demanda esta columna
desaparece, y se repite el primer proceso.
Nuevo proceso de asignación
Una vez finalizado el
cuadro anterior nos daremos cuenta que solo quedará una fila, por ende
asignamos las unidades y se ha terminado el método.
El cuadro de las
asignaciones (que debemos desarrollarlo paralelamente) queda así:
Los costos asociados a la
distribución son:
En este caso el método del
costo mínimo presenta un costo total superior al obtenido mediante Programación
Lineal y el Método
de Aproximación Vogel, sin embargo comúnmente no es
así, además es simple de desarrollar y tiene un mejor rendimiento en cuanto a
resultados respecto al Método
de la Esquina Noroeste.
Método húngaro
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,
será entonces cuestión de agregar un paso adicional para abordar ejercicios de
maximización.
Algoritmo húngaro, paso 1
Antes que nada cabe
recordar que el método húngaro trabaja en una matriz de costos n*m (en este
caso conocida como matriz m*m, dado que el número de filas es igual al número
de columnas n = m), una vez construida esta se debe encontrar el elemento más
pequeño en cada fila de la matriz.
Algoritmo húngaro, paso 2
Una vez se cumple el procedimiento
anterior se debe construir una nueva matriz n*m, en la cual se consignarán los
valores resultantes de la diferencia entre cada costo y el valor mínimo de la
fila a la cual cada costo corresponde (valor mínimo hallado en el primer paso).
Algoritmo húngaro, paso 3
Este paso consiste en
realizar el mismo procedimiento de los dos pasos anteriores referidos ahora a
las columnas, es decir, se halla el valor mínimo de cada columna, con la
diferencia que este se halla de la matriz resultante en el segundo paso, luego
se construirá una nueva matriz en la cual se consignarán los valores
resultantes de la diferencia entre cada costo y el valor mínimo de la columna a
la cual cada costo corresponde, matriz llamada "Matriz de Costos
Reducidos".
Algoritmo húngaro, paso 4
A continuación se deben de
trazar líneas horizontales o verticales o ambas (únicamente de esos tipos) con
el objetivo de cubrir todos los ceros de la matriz de costos reducidos con el
menor número de líneas posibles, si el número de lineas es igual al número de
filas o columnas se ha logrado obtener la solución óptima (la mejor asignación
según el contexto de optimización), si el número de líneas es inferior al
número de filas o columnas se debe de proceder con el paso 5.
Algoritmo húngaro, paso 5
Este paso consiste en
encontrar el menor elemento de aquellos valores que no se encuentran cubiertos
por las líneas del paso 4, ahora se restará del restante de elementos que no se
encuentran cubiertos por las líneas; a continuación este mismo valor se sumará
a los valores que se encuentren en las intersecciones de las líneas
horizontales y verticales, una vez finalizado este paso se debe volver al paso
4.
Resolución de un problema
de asignación mediante el método húngaro
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:
Paso 1
Encontramos el menor
elemento de cada fila
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.
Paso 3
En la matriz construida en
el paso anterior se procede a efectuar el paso 1 esta vez en relación a las
columnas, por ende escogemos el elemento menor de cada columna. Igualmente
construimos una nueva matriz con la diferencia entre los valores de la matriz 2
y el elemento menor de la columna a la cual corresponde cada valor.
Paso 4
En este paso trazaremos la
menor cantidad de combinaciones de líneas horizontales y verticales con el
objetivo de cubrir todos los ceros de la matriz de costos reducidos.
Como se puede observar el
menor número de líneas horizontales y/o verticales necesarias para cubrir los
ceros de la matriz de costos reducidos es igual a 2, por ende al ser menor que
el número de filas o columnas es necesario recurrir al paso 5.
Paso 5
En este paso seleccionamos
el menor elemento de los elementos no subrayados.
Luego se procede a restarse
de los elementos no subrayados y a adicionarse a los elementos ubicados en las
intersecciones de las líneas, en este caso existe una única intersección (3).
Ahora ya efectuado este
paso pasamos al paso 4.
Ahora observamos cómo se
hace necesario trazar tres líneas (la misma cantidad de filas o columnas de la
matriz) por ende se ha llegado al tabulado final, en el que por simple
observación se determina las asignaciones óptimas.
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.
Conclusión:
Hoy en día, la mayoría de las
industrias a nivel mundial, utilizan
este tipo de estrategias para lograr un mayor nivel de competividad comercial,
ya que, se logra obtener las mejores rutas para incrementar la economía y
estabilidad empresarial.
El método de transporte es tan solo
una parte de todo el sistema de distribución que se encuentra dentro de la
compañía. Es muy difícil resolver o encontrar el mejor programa de transporte
que interactúe en cuestiones de servicio y bajo costo al mismo tiempo. Esa área
de le empresa requiere de una constante atención y un análisis muy preciso para
implementar todos los cambios que genere la solución factible del método.
El uso de este
modelo le permite a la empresa a mejorar su gestión administrativa, al tener
información valiosa que le permitirá tomar mejores decisiones relacionadas al incremento
de su rentabilidad y disminución de sus costos de envío, generando una ventaja
frente a la competencia al ser más efectivos.
