Problema de Transporte: tres métodos comparados

El problema de transporte en lenguaje claro

Qué problema resuelve

Tienes m orígenes (fábricas, almacenes, plantas) con cierta oferta cada uno, y n destinos (clientes, ciudades) con cierta demanda. Conoces el costo unitario de mover una unidad desde cada origen a cada destino. ¿Cuántas unidades enviar por cada ruta para minimizar el costo total cumpliendo oferta y demanda? Es un caso especial de programación lineal con estructura tan particular que tiene algoritmos específicos más eficientes.

Las tres heurísticas comparadas

1. Esquina Noroeste (NW): empieza en la celda (1,1), asigna lo máximo posible, mueve fila o columna agotada. Simple pero ignora costos - suele dar la peor solución inicial.
2. Costo Mínimo: busca la celda con menor costo, asigna lo máximo, repite. Mejora claramente sobre NW.
3. Vogel (VAM): calcula la "penalización" de cada fila y columna (diferencia entre los dos menores costos), trabaja primero las filas/columnas con mayor penalización. Es la heurística que generalmente da la mejor solución inicial - a veces ya es óptima.

Problema balanceado

El problema clásico asume Σ oferta = Σ demanda. Si no se cumple:

• Si oferta > demanda: agrega un destino ficticio con demanda = exceso y costo 0 a todas las celdas.
• Si demanda > oferta: agrega un origen ficticio con oferta = faltante. El problema se vuelve infactible si no puedes inventar oferta - tienes una demanda que no podrás cubrir.

De solución inicial a solución óptima

Las tres heurísticas dan una solución factible básica inicial, no necesariamente óptima. Para llegar al óptimo se usa el método MODI (modified distribution) o el método del salto (stepping stone), que evalúan si cambiar asignaciones reduce el costo. Esta calculadora se enfoca en la fase de solución inicial para fines educativos - en la práctica, optimizadores como CPLEX/Gurobi resuelven todo en milisegundos.

Aplicaciones reales

• Logística: distribución de productos terminados desde plantas a centros de distribución.
• Cadena de suministro: compras de materia prima desde proveedores múltiples a fábricas múltiples.
• Asignación de personal: ubicar trabajadores a turnos minimizando costo (variante).
• Energía: distribución de electricidad desde plantas a regiones.
• Catástrofes/emergencias: distribución de ayuda humanitaria desde almacenes a zonas afectadas.

Características que lo hacen especial

El problema de transporte tiene la propiedad de integralidad: si oferta y demanda son enteros, la solución óptima del relajamiento lineal es entera automáticamente (no necesita programación entera). Esto lo hace muy eficiente computacionalmente.

Limitaciones

• Capacidades de ruta: el modelo básico no las contempla. Para ello, agregar restricciones de capacidad.
• Costos no lineales: descuentos por volumen, costos fijos por usar una ruta - requieren modelos más generales.
• Tiempos: el modelo es estático. Para multi-período, modelo con tiempo discreto.

Tip de examen: en ejercicios de cursos de IO, Vogel casi siempre da la mejor solución inicial. Si tu examen permite elegir un método, ese es el seguro. La esquina noroeste se enseña primero porque es la más fácil de explicar, no porque sea la mejor.