Optimización en el transporte con SÍMPLEX: Problema de transporte.

Por: Héctor Benítez -
El método del símplex es un algoritmo iterativo que se utiliza principalmente para resolver problemas de programación lineal, incluido el problema de transporte. El algoritmo se basa en la mejora iterativa de una solución factible hasta alcanzar la solución óptima. El proceso general es el siguiente:

  1. Formular el problema de transporte en forma estándar de programación lineal, estableciendo las variables de decisión, la función objetivo y las restricciones.
  2. Inicializar una solución factible básica, que cumpla con las restricciones de oferta y demanda. Esto puede hacerse mediante métodos heurísticos o algoritmos de asignación inicial.
  3. Verificar si la solución actual es óptima. Si lo es, se ha encontrado la solución óptima del problema de transporte. De lo contrario, continuar con el siguiente paso.
  4. Realizar iteraciones utilizando el método del símplex para mejorar la solución actual. Esto implica seleccionar una variable no básica para entrar en la base y una variable básica para salir de la base, siguiendo reglas específicas para determinar qué variable seleccionar.
  5. Actualizar la solución y repetir los pasos 3 y 4 hasta alcanzar la solución óptima.

Optimización de ubicaciones

En cuanto a las herramientas especializadas para resolver problemas de transporte, existen varios software y bibliotecas disponibles que pueden ayudarte en este proceso. Algunos ejemplos populares son:

  1. IBM CPLEX: Es una biblioteca de optimización matemática con capacidades para resolver problemas de transporte y otros problemas de programación lineal. Proporciona una interfaz en varios lenguajes de programación como C++, Python, Java, entre otros.
  2. PuLP: Es una biblioteca de optimización escrita en Python que proporciona una interfaz fácil de usar para resolver problemas de programación lineal, incluido el problema de transporte. PuLP utiliza solvers externos como CBC (Coin-or branch and cut) o GLPK (GNU Linear Programming Kit) para realizar los cálculos.
  3. Lingo: Lingo es un software de optimización que permite modelar y resolver una amplia gama de problemas de programación lineal y no lineal, incluido el problema de transporte. Proporciona una interfaz gráfica y un lenguaje de modelado para formular los problemas de manera fácil y eficiente. Lingo utiliza algoritmos avanzados para encontrar soluciones óptimas y permite una flexibilidad significativa en la formulación de restricciones y objetivos.
  4. Excel Solver: Excel Solver es un complemento integrado en Microsoft Excel que se utiliza para resolver problemas de optimización, incluido el problema de transporte. Permite definir variables de decisión, función objetivo y restricciones directamente en una hoja de cálculo de Excel. Con Solver, puedes especificar los parámetros del problema y encontrar una solución óptima utilizando algoritmos de optimización. Es una herramienta popular y ampliamente utilizada debido a su accesibilidad y familiaridad para los usuarios de Excel.
  5. WinQSB: (Win Quantitative System for Business) es un software de optimización y análisis cuantitativo utilizado para resolver diversos problemas de gestión y operaciones, incluido el problema de transporte. Proporciona una interfaz gráfica fácil de usar con módulos específicos para diferentes tipos de problemas, como programación lineal, transporte, asignación, entre otros. WinQSB ofrece opciones para modelar y resolver problemas de manera interactiva, lo que facilita la implementación de soluciones óptimas.
  6. Tora: (Tool for Operations Research Applications) es un software gratuito utilizado para resolver problemas de programación lineal y otros problemas de investigación de operaciones. Ofrece una interfaz gráfica intuitiva y fácil de usar para modelar y resolver problemas, incluido el problema de transporte. Tora utiliza algoritmos de optimización para encontrar soluciones óptimas y proporciona una amplia gama de herramientas y técnicas analíticas para ayudar en el análisis de problemas de gestión y operaciones.

Estas herramientas son solo algunas de las muchas disponibles para resolver problemas de transporte y otros problemas de optimización. Cada una tiene sus propias características y funcionalidades específicas, por lo que es importante evaluarlas y seleccionar la que mejor se ajuste a tus necesidades y preferencias.

Pero veamos un ejemplo de un problema de transporte resuelto con PuLP.

Supongamos que una fábrica tiene tres instalaciones que pueden producir diferentes productos, y cuatro puntos de venta que necesitan diferentes cantidades de esos productos. El objetivo es minimizar el costo total de transporte de los productos de las instalaciones a los puntos de venta, sabiendo que cada instalación tiene una capacidad limitada de producción y cada punto de venta tiene una demanda específica de productos. 

Una forma de resolver este problema es utilizando el método de símplex. El modelo de programación lineal resultante es:

Minimizar:

5x11 + 2x12 + 4x13 + 3x14 +

3x21 + 2x22 + 1x23 + 7x24 +

2x31 + 4x32 + 5x33 + 2x34

sujeto a:

x11 + x12 + x13 + x14  <= 2500

x21 + x22 + x23 + x24  <= 3500

x31 + x32 + x33 + x34  <= 1500

x11 + x21 + x31        >= 1000

x12 + x22 + x32        >= 1500

x13 + x23 + x33        >= 800

x14 + x24 + x34        >= 1600

xij >= 0 para todo i, j

Donde xij es la cantidad de productos transportados desde la instalación i hasta el punto de venta j.

El siguiente es el código de ejemplo para resolver este problema utilizando  Python. 

Si quieres puedes copiar y pegar este código y correrlo en PuLP para que veas su funcionamiento.

# Importar la librería PuLP

import pulp

# Definir los datos del problema

fuentes = [1, 2, 3]

destinos = [1, 2, 3, 4]

capacidad = {1: 2500, 2: 3500, 3: 1500}

demanda = {1: 1000, 2: 1500, 3: 800, 4: 1600}

costo = {

    (1, 1): 5, (1, 2): 2, (1, 3): 4, (1, 4): 3,

    (2, 1): 3, (2, 2): 2, (2, 3): 1, (2, 4): 7,

    (3, 1): 2, (3, 2): 4, (3, 3): 5, (3, 4): 2

}

# Crear el problema

problema = pulp.LpProblem("Problema de transporte", pulp.LpMinimize)

# Crear las variables de decisión

variables = pulp.LpVariable.dicts("x", (fuentes, destinos), lowBound=0, cat='Continuous')

# Agregar la función objetivo

problema += pulp.lpSum([costo[(i,j)]*variables[i][j] for (i,j) in variables.keys()]), "Costo total"

# Agregar las restricciones

for i in fuentes:

    problema += pulp.lpSum([variables[i][j] for j in destinos]) <= capacidad[i], f"Capacidad de la fuente {i}"

for j in destinos:

    problema += pulp.lpSum([variables[i][j] for i in fuentes]) >= demanda[j], f"Demanda del destino {j}"

# Resolver el problema

problema.solve()

# Imprimir la solución

print("Status:", pulp.LpStatus[problema.status])

print("Costo total:", pulp.value(problema.objective))

for i in fuentes:

    for j in destinos:

        print(f"Cantidad transportada de la fuente {i} al destino {j}: {variables[i][j].value()}")


El resultado obtenido lo arroja de esta manera:


Status: Optimal

Costo total: 43250.0

Cantidad transportada de la fuente 1 al destino 1: 1000.0

Cantidad transportada de la fuente 1 al destino 2: 1500.0

Cantidad transportada de la fuente 1 al destino 3: 0.0

Cantidad transportada de la fuente 1 al destino 4: 0.0

Cantidad transportada de la fuente 2 al destino 1: 0.0

Cantidad transportada de la fuente 2 al destino 2: 0.0

Cantidad transportada de la fuente 2 al destino 3: 800.0

Cantidad transportada de la fuente 2 al destino 4: 1700.0

Cantidad transportada de la fuente 3 al destino 1: 0.0

Cantidad transportada de la fuente 3 al destino 2: 0.0

Cantidad transportada de la fuente 3 al destino 3: 0.0

Cantidad transportada de la fuente 3 al destino 4: 900.0


En base a esta tabla, se puede ver que la fábrica debe transportar 1000 unidades desde la instalación 1 al punto de venta 1, 1500 unidades desde la instalación 1 al punto de venta 2, y así sucesivamente.

El costo total mínimo de transporte obtenido por el modelo es de 43250.0. Significa que si la fábrica sigue estas recomendaciones, el costo de transporte total de los productos será de $43,250.

También se puede observar que todas las restricciones del problema (capacidad de producción de cada instalación y la demanda de cada punto de venta) se cumplen.

Este es un pequeño ejemplo de la aplicación del método simplex para optimizar un problema de transporte. Puedes explorar más según tus necesidades y preferencias. Cada herramienta tiene su propia documentación y ejemplos que te pueden guiar en la implementación de problemas de transporte y su resolución.


Héctor.

Location: Ciudad de México, CDMX, México

Entradas más populares de este blog

Mi paso por el Tecnológico Nacional de México

Por: Héctor Benítez -
Aquí te voy a exponer un poco de lo que pasa con la docencia en varias instituciones. Tengo más de 15 años de experiencia docente, sé de lo que hablo y aclaro que estoy siendo muy general y hablo desde mi perspectiva, que bien puede estar equivocada. No puedo decir mucho sobre el Tecnológico Nacional de México porque no estuve mucho tiempo ahí. También debo aclarar que, aunque por momentos hablaré en general del TecNM, en realidad me refiero principalmente al Tecnológico donde yo trabajé. Aun así, por mi experiencia como profesor y en la investigación, sí puedo responder la pregunta que seguramente ya te has hecho (y si no, deberías hacerlo): ¿Por qué el Tecnológico Nacional de México no aparece en los listados de las mejores universidades del país? Siendo una institución con una gran trayectoria y ya bastantes años de existencia (aunque ha cambiado de nombre), uno pensaría que al menos debería figurar como una opción sólida para estudiar. Sin embargo, en mi caso, jamás escuché hablar ...
Read more »

Los mejores autores y libros de transporte y movilidad

Por: Héctor Benítez -
Imagen
Nota: Revisa con frecuencia este artículo, lo iré actualizando, es que son muchos libros y me estoy tardando en subirlos.           Con el paso de los años he notado que cada vez se le da menos interés a los libros. Digo, desde hace ya muchos años se había dejado un poco de lado el leer un libro para dar paso a buscar un resumen en internet o un video. La realidad es que sí es bastante cómodo ver un buen video tutorial que leer un ejercicio en un libro. Cuando era estudiante siempre preferí ver videos o buscaba algún ejercicio en internet, tratando de que se pareciera lo más posible a lo que el profesor había dejado de tarea. Y si eras bueno buscando y había suerte, te podías encontrar el ejercicio exacto que dejó el profesor, sobre todo si era de esos profesores flojos que copiaban el ejercicio tal cual de internet. Ya como profesor, me di cuenta de que los videos tenían una gran deficiencia, y es que para no ser aburridos son muy “al grano”: no explican d...
Read more »

Aforos vehiculares y cálculo de confiabilidad

Por: Héctor Benítez -
Imagen
     Los conteos de tráfico vehicular (aforos vehiculares) se refieren al proceso de medir y registrar el flujo de vehículos en una determinada área o carretera durante un período de tiempo específico. Estas mediciones son fundamentales para comprender y gestionar el tráfico, planificar infraestructuras viales, mejorar la seguridad en las carreteras y tomar decisiones informadas en el campo del transporte.  La historia de los conteos de tráfico vehicular tiene sus raíces en la creciente complejidad del tráfico y la necesidad de obtener datos precisos para hacer frente a los desafíos asociados con el aumento del número de vehículos en las carreteras. A lo largo del tiempo, la tecnología utilizada para realizar estos conteos ha evolucionado notablemente. La implementación de los primeros aforos vehiculares se remonta a principios del siglo XX. La necesidad de medir y entender el tráfico surgió con el aumento del número de automóviles en las carreteras. A continuación, ...
Read more »

La capacidad de línea en los transportes

Por: Héctor Benítez -
Imagen
La capacidad de línea de un sistema de transporte, también conocida como capacidad de transporte, se refiere a la cantidad máxima de pasajeros o carga que puede ser transportada por esa línea específica durante un período determinado de tiempo. Es una medida importante para evaluar la eficiencia y la efectividad del sistema de transporte en satisfacer la demanda de movilidad de los usuarios, y de vital importancia que todo ingeniero en en el área de transportes conozca las capacidades de línea de su área de estudio y conozca la metodología para calcularlas en caso de carecer de la información. Para los sistemas de transporte público, como el metro, el tren ligero o el metrobús entre otros, la capacidad de línea se expresa generalmente en términos de pasajeros por hora por sentido (PPHPS). Es decir, cuántos pasajeros pueden ser transportados en una dirección específica durante una hora. Para conocer y calcular la capacidad de línea se deben tomar en cuenta muchos factores los c...
Read more »

Navier Stokes, una de las ecuaciones del milenio que usamos en modelación de sistemas de transporte

Por: Héctor Benítez -
Imagen
Cuando uno escucha “ecuaciones de Navier-Stokes” suele imaginar túneles de viento, alas de avión o científicos con cara de sufrimiento frente a pizarrones interminables. Y sí, todo eso está ahí. Pero hay una sorpresa: esas mismas ecuaciones, o mejor dicho, su espíritu matemático, están muy presentes cuando estudiamos cómo se mueven personas y vehículos en una ciudad.  Y eso cambia la conversación. A principios del siglo XIX, Claude-Louis Navier y George Gabriel Stokes estaban obsesionados con una pregunta aparentemente simple: ¿cómo se mueve un fluido real? No un fluido ideal de libro como el que normalmente nos enseñan en la carrera en termidinámica, sino uno con fricción, con viscosidad, con remolinos, con comportamientos caprichosos. Euler ya había trabajado mucho en el comportamiento de fluidos, pero estos dos lograron un resultado con un conjunto de ecuaciones diferenciales que describen la conservación de masa, de cantidad de movimiento y la influencia de fuerzas internas y e...
Read more »