2023
TRANSPORTE Y
ASIGNACIÓN
UNIDAD 4
PEDRO ENRIQUE DE LA CRUZ MORALES
INVESTIGACIÓN DE OPERACIONES I
INDICE
4.1 DEFINICIÓN DEL PROBLEMA DEL TRANSPORTE. ........................................................ 2
4.2 Algoritmo de Transporte. ......................................................................................... 3
4.3 Método de la esquina noroeste ........................................................................... 5
4.4 Método de costo mínimo. ................................................................................... 7
4.5 Método de aproximación de Vogel ...................................................................... 9
4.6 Definición del Problema de Asignación. ............................................................. 14
4.7 Método Húngaro ............................................................................................... 15
4.8 Uso de Software (WIN QSB, TORA, DS, for Windows, LINGO, LINDO, OTROS). .... 18
4.1 DEFINICIÓN DEL PROBLEMA DEL TRANSPORTE.
El problema de transporte clásico consiste en llevar cantidades de un cierto producto
de m orígenes a n destinos, de manera que, conocidos la cantidad de que se
dispone en cada origen, la cantidad demandada en cada destino y el costo de
transportar una unidad de producto de cada origen a cada destino, se satisfaga la
demanda con el costo total mínimo.
Como se sabe se trata de un problema de programación lineal y como tal necesita
de una solución factible básica inicial para que posteriormente al utilizar un criterio
de optimización se cambie de base mejorando la solución, de ser necesaria hasta
alcanzar el óptimo. Se puede formular matemáticamente el problema como:
4.2 Algoritmo de Transporte.
El algoritmo de transporte organiza los cálculos en una forma más cómoda
aprovechando la ventaja de la estructura especial del modelo de transporte. Pare
esto sigue los mismos pasos que el método simplex, sin embargo, en lugar de usar
la tabla simplex normal se aprovecha la ventaja de la estructura especial del modelo
de transporte para organizar los cálculos en una forma más cómoda.
Se debe agregar que el algoritmo especial de transporte fue desarrollado por
primera vez cuando la norma eran los cálculos a mano y se necesitaba de
soluciones con método abreviado.
Los pasos del algoritmo de transporte son exactamente iguales a los del algoritmo
simplex.
1. En el primer paso se determina una solución básica factible de inicio que nos
ayude a proseguir en el paso dos.
2. En el segundo paso se usa la condición de optimalidad del método simplex
para determinar la variable de entrada entre todas las variables básicas.
Detenerse si se satisface.
3. En el tercer paso se usa la condición de factibilidad del método simplex para
determinar la variable de salida y así obtener la nueva solución y
posteriormente regresar al paso dos.
Problema de transporte: Consiste en decidir cuántas unidades trasladar desde
ciertos puntos de origen (platas, ciudades, etc) a ciertos puntos de destino (centros
de distribución, ciudades, etc) de modo de minimizar los costos de transporte, dada
la oferta y demanda en dichos puntos. Se suponen conocidos los costos unitarios
de transporte, los requerimientos de demanda y la oferta disponible.
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 contexto en el que se aplica el modelo de transporte es amplio y puede generar
soluciones atinentes al área de operaciones, inventario y asignación de elementos.
Cualquier modelo de transporte se compone de unidades de un bien a distribuir, m
orígenes, n destinos, recursos en el origen, demandas en los destinos y costos de
distribución por unidad. Adicionalmente, se tienen varios supuestos:
1. Supuesto de requerimientos: cada origen tiene un suministro fijo de unidades
que se deben distribuir por completo entre los destinos.
2. Supuesto de costo: el costo de distribuir unidades de un origen a un destino
cualquiera es directamente proporcional al número de unidades distribuidas.
3. Propiedad de soluciones factibles: un problema de transporte tiene
soluciones factibles sólo si la sumatoria de recursos en los m orígenes es
igual a la sumatoria de demandas en los destinos.
4. Propiedad de soluciones enteras: En los casos en los que tanto los recursos
como las demandas toman un valor entero, todas las variables básicas
(asignaciones), de cualquiera de las soluciones básicas factibles (inclusive la
solución óptima), asumen también valores enteros.
PASOS BÁSICOS PARA EL ALGORITMO DE TRANSPORTE
1. Verificar que el problema esté balanceado, es decir que la disponibilidad
sea igual a la demanda.
2. Encontrar una solución básica inicial por uno de los métodos que se
mencionan en el punto 4.2.
3. Probar la solución para determinar si es óptima.
4. Mejorar la solución cuando no es óptima.
5. Repetir el paso 2 y 3 hasta que se obtenga la solución óptima.
Métodos para encontrar una solución básica inicial
1. Método de la esquina noroeste.
2. Método de costo mínimo.
3. Método de aproximación de Vogel.
4.3 Método de la esquina noroeste
Empezando con la celda (1,1) asignar a X11 tantas unidades como sea posible sin
ir en contra de las restricciones. Esta será el menor valor de A1 o de B1. En seguida
se continúa moviendo una celda hacia la derecha, si queda alguna cantidad
disponible o si no, una celda hacia abajo. En cada paso asignar tanto como sea
posible a la variable bajo consideración.
EJEMPLO:
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.
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.
4.4 Método de costo mínimo.
Asignar tanto como sea posible a la variable con el costo unitario más pequeño, en
la tabla completa (los empates se rompen arbitrariamente). Eliminar el renglón o la
columna satisfecha, si la columna y el renglón se satisfacen en forma simultánea
únicamente uno puede ser eliminado. Se continuará repitiendo el proceso para la
tabla resultante.
Consideremos nuevamente el Problema de Transporte donde se desea satisfacer
la demanda de 4 molinos a través de los envíos de 3 silos, donde los valores en la
esquina superior derecha de cada cuadro c_{ij} representan los costos unitarios de
transporte desde el silo i al molino j.
La aplicación del Método de Costo Mínimo al problema de transporte anterior da
origen a la siguiente solución factible de inicio:
Los pasos aplicados para llegar a dichos resultados se resumen a continuación:
La celda x_{12} tiene el menor costo unitario, por tanto se asigna lo máximo posible
(15 unidades correspondiente a la oferta del silo 1). Con x_{12}=15 se satisface
tanto la demanda del molino 2 como la oferta del silo 1. Se tacha de forma arbitraria
la columna 2.
Ahora la celda x_{31} tiene el mínimo costo unitario sin tachar. Se asigna x_{31}=5
y se tacha la columna 1 porque quedó satisfecha (lo cual deja una capacidad
remanente del silo 3 de 5 unidades).
Al continuar de este modo, se asignan en forma sucesiva 15 unidades a la celda
x_{23}, 0 unidades a la celda x_{14} (la capacidad del silo 1 ya fue asignada), 5
unidades a la celda x_{34} y 10 unidades a la celda x_{24}.
La solución básica factible de inicio resultante con 6 variables básicas es:
x_{12}=15, x_{14}=0, x_{23}=15, x_{24}=10, x_{31}=5, x_{34}=5 la cual reporta un
valor en la función objetivo (costo) de
Z=15(2)+0(11)+15(9)+10(20)+5(4)+5(18)=$475 que efectivamente es una mejor
solución inicial que la obtenida por el Método de la Esquina Noroeste (que provee
un valor de $520 al ser evaluado en la función objetivo) pero por cierto no es la
solución óptima según se aprecia en la siguiente imagen que resume la
implementación computacional del problema en Solver.
4.5 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
produce mejores resultados iniciales que los mismos.
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.
1. Determinar para cada fila y columna una medida de penalización restando
los dos costos menores en filas y columnas.
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).
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).
4. 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:
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.
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 las iteraciones 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 con
el método de aproximación de Vogel son:
De esta manera se ha determinado una solución, la cual también fue obtenida
mediante programación lineal, definitivamente desarrollar la capacidad para
modelar mediante programación lineal y apoyarse de una buena herramienta como
WinQSB, STORM, LINGO, TORA etc. termina siendo mucho más eficiente que la
utilización de los métodos heurísticos para problemas determinísticos.
4.6 Definición del Problema de Asignación.
Otra clase de modelo de distribución es el modelo de asignación. Específicamente,
está relacionado con la asignación de un determinado número de orígenes al mismo
número de destinos con el objeto de optimizar alguna función de efectividad.
Matemáticamente el modelo de asignación se define como la optimización
(maximización o minimización) de la función.
4.7 Método Húngaro
Este es un problema de programación lineal, pero es más eficiente resolverlo por el
método húngaro, siguiendo los siguientes pasos:
1. Restar el elemento más pequeño de cada fila de los demás elementos de la
misma fila.
2. Restar el elemento más pequeño de cada columna de los demás elementos
de la misma columna.
3. Verificar la optimalidad trazando el mínimo número de líneas que puedan
pasar a través de todos los ceros de la tabla. En algunos casos este paso
causa dificultades, ya que ordinariamente hay muchas formas de trazar estas
líneas. Las diferentes alternativas son posibles siempre y cuando el número
de líneas sea mínimo y se tracen horizontal o verticalmente. Las líneas
diagonales no se permiten.
4. Después de trazar el número mínimo de líneas, se hace la prueba de
optimalidad. Si el número de líneas es igual a n (número de filas o columnas),
puede hacerse una asignación óptima. Si el número de líneas es menor que
n, se requiere trazar más líneas de la siguiente manera: seleccionar el
elemento más pequeño, el cual no esté cruzado por una línea, restándolo de
todos los elementos no cruzados por una línea y sumar esta cantidad a todos
los elementos situados en la intersección de líneas. Los demás elementos
permanecen inalterados.
5. Comprobar nuevamente la optimalidad, si el mínimo número de líneas es
igual a n, realizar la asignación óptima.
Ejercicio
En el terreno de una universidad cuatro contratistas diferentes 1, 2, 3 y 4 se
proponen construir cuatro edificios diferentes A, B, C y D. Debido a que los
contratistas contribuyen generosamente al fondo de los alumnos, cada uno
construirá un edificio. Cada contratista ha remitido propuestas para la construcción
de los cuatro edificios. El problema consiste en determinar que edificio debe
adjudicarse a cada contratista para lograr un mínimo costo de construcción de los
cuatro edificios.
Se resta el elemento más pequeño de cada fila de los demás elementos de la misma
fila.
Se resta el elemento más pequeño de cada columna de los demás elementos de la
misma columna.
SOLUCIÓN ÓPTIMA:
4.8 Uso de Software (WIN QSB, TORA, DS, for Windows, LINGO,
LINDO, OTROS).
1. Mecalux 3PL
Es de las opciones más completas del mercado gracias
a sus herramientas para el manejo de clientes, las
opciones de gestión y reposición de stock y el sistema de
custodia de productos, proporcionando información en
tiempo real durante el transporte.
Uno de los aspectos en los que más incide es en la
trazabilidad del stock, permitiendo encargar nuevas
reposiciones de manera rápida, segura y muy sencilla. Además, es posible manejar
la logística de una empresa multi almacén, manejando todo lo relacionado con los
transportes en varias superficies de manera simultánea.
Permite mejorar el rendimiento de toda la flota de transportes, minimizando los
errores y los problemas durante el traslado y garantizando una entrega en fecha
cumpliendo con los estándares de la empresa.
2. Quonext
Se adapta a prácticamente cualquier tipo de empresa que necesite transportar algún
tipo de mercancía. Permite controlar el transporte hasta la dirección de entrega
gracias a su software integrado para la gestión de flotas, una herramienta de
excelentes resultados.
De entre todas sus funcionalidades destacadas cabe mencionar
el sistema de control de seguimientos y gestiones de entradas y salidas de
depósitos, la implementación de la función cross-docking, que gestiona la
mercancía de manera independiente en función del destinatario, es capaz de
detectar errores en el picking y sugiere rutas alternativas para mejorar la gestión de
los recursos durante las largas travesías.
Es una de las más extendidas a nivel global gracias a su sistema de optimización
de transportes, cuyas funciones en tiempo real permiten tener bajo control todos los
sistemas encargados de la recogida, el traslado y la recepción del paquete.
3. Exact
Más que en el transporte, Exact pone el foco en la
distribución. Es un programa basado en la obtención
de buenos márgenes de ganancias, lo que se traduce
en una mayor competitividad en el mercado.
Es una herramienta muy usada a la hora de reducir
costes y establecer límites presupuestarios, ya que su
herramienta de gestión está pensada para gestionar
de manera inteligente el stock.
Es una gran opción para mejorar la movilidad, ya que puede alojarse en un servidor
propio o en la nube manteniendo los datos encriptados con doble sistema de
autentificación, y es capaz de elaborar informes estadísticos y de enviar
notificaciones configurables a medida.
4. SAP Transportation Management
La conocida firma de transportes ha acuñado su propio
programa de control de transportes, que da al usuario control
total sobre las mercancías y el estado de los transportes.
Es una de las mejores a la hora de gestionar grandes
volúmenes de mercancía y de flota de vehículos, ofreciendo
visibilidad en tiempo real sobre la ruta más apta teniendo en
cuenta las condiciones de la carretera.
SAP Transportation es conocido por integrar un programa de compatibilidad
internacional capaz de ofrecer soluciones integrales a empresas. Sus amplias
prestaciones y su reducido coste lo han convertido en la opción favorita de las
pymes, ya que es uno de los software de transportes y logística más competitivos.
5. Elfos Software
Es uno de los programas más completos en cuanto a
logística y distribución. Uno de sus avales es la
experiencia, ya que es una de las firmas más veteranas:
más de 30 años de experiencia tiene el equipo de Elfos en
el sector de los transportes.
Su programa de gestión intuitiva y fácil de utilizar cubre
todas las necesidades de la empresa gracias a la inserción
de herramientas de fácil uso y de gran efectividad. Y dispone de una plataforma que
le proporciona actualizaciones constantes, por lo que su rendimiento y prestaciones
siempre están a la última.
6. BeOne
Hoy en día es habitual encontrar programas que se venden al usuario por módulos
para garantizar que casan perfectamente con lo que el cliente busca, y en el sector
de los transportes esto no iba a ser una excepción.
BeOne es la vertiente modular de los programas informáticos para transportes,
contando con packs que aglutinan varios de estos tokens y dando la posibilidad de
crear una herramienta de gestión de transportes
totalmente adaptada a las necesidades de la empresa.
Cuenta con servicios de alojamiento en la nube,
herramientas de gestión operativa aérea, marítima y
terrestre, control empresarial y supervisión de
depósitos y almacenes, que incluyen gestores
aduaneros, documentales y archivos electrónicos.
7. _b first
Es el ERP diseñado para operadores logísticos y transitarios de última generación,
capaz de optimizar todos los procesos informáticos y virtuales de las empresas
dedicadas al desarrollo de transportes.
El programa está dividido por funcionalidades
genéricas, las cuales incluyen varias opciones a
elegir en el desplegable.
La cantidad de opciones puede resultar
apabullante de entrada, aunque con el tiempo se
van descubriendo sus auténticas utilidades:
gestores de importaciones, Courier aéreos,
realización telemática de gestiones aduaneras.
8. IBM Sterling Logistics Management
Y no dejamos de lado los programas de logística, porque la propuesta de IBM,
diseñada en principio para optimizar los transportes por carretera, es a día de hoy
una de las mejores herramientas para la logística de
envíos a gran escala.
Ofrece soluciones integrales de transporte, contando
con gestores de documentos, certificados de
seguridad, vigilancia de transferencia de productos
con clientes, sincronización entre almacenes… la
cantidad de servicios que integra está pensada para
funcionar con grandes volúmenes de mercancías.
También tiene la capacidad de detectar y corregir incongruencias en los procesos
administrativos llevados a cabo, además de hacer revisiones fiscales con cierta
frecuencia para llevar la contabilidad y la facturación al día.
