Paso 1: Formulación del Problema
* Identificar Orígenes y Destinos:
Determinar todas las fuentes de suministro (ej., fábricas,
almacenes).
Determinar todos los puntos de demanda (ej., tiendas, clientes).
Determinar Oferta y Demanda:
Para cada origen, cuantificar la cantidad de producto disponible
(oferta).
Para cada destino, cuantificar la cantidad de producto requerida
(demanda).
Determinar Costos de Transporte:
Establecer el costo unitario de transporte desde cada origen a
cada destino. Esto se representa en una matriz de costos.
Verificar Balance del Modelo:
Calcular la suma total de la oferta.
Calcular la suma total de la demanda.
Si la oferta total es igual a la demanda total, el modelo está
balanceado.
Si la oferta total no es igual a la demanda total, se debe introducir
una "fuente ficticia" (demanda sobrante) o un "destino ficticio"
(oferta sobrante) con costos de transporte de cero para balancear
el modelo.
Paso 2: Obtención de una Solución Inicial Básica Factible
El objetivo aquí es encontrar una primera asignación que cumpla con
las restricciones de oferta y demanda. Los métodos más comunes
son:
Método de la Esquina Noroeste (NWC - Northwest Corner Method):
Comenzar en la celda superior izquierda (esquina noroeste) de la
tabla de transporte.
Asignar la mayor cantidad posible a esa celda, limitada por la
oferta del origen y la demanda del destino.
Ajustar la oferta y la demanda de la fila y columna
correspondientes.
Si la oferta se agota, moverse a la siguiente fila. Si la demanda se
satisface, moverse a la siguiente columna.
Continuar hasta que todas las ofertas se agoten y todas las
demandas se satisfagan.
* Ventaja: Muy simple de aplicar.
* Desventaja: No considera los costos, por lo que la solución inicial
puede ser muy subóptima.
Método del Costo Mínimo (LCM - Least Cost Method):
Identificar la celda con el costo unitario de transporte más bajo
en toda la tabla.
Asignar la mayor cantidad posible a esa celda, limitada por la
oferta y la demanda.
Eliminar la fila o columna (o ambas) que se satisfizo
completamente.
Repetir el proceso con los costos restantes hasta que todas las
ofertas se agoten y todas las demandas se satisfagan.
* Ventaja: Considera los costos, lo que generalmente lleva a una
mejor solución inicial que NWC.
Método de Aproximación de Vogel (VAM - Vogel's Approximation
Method):
Para cada fila y columna no tachada, calcular la "penalidad", que
es la diferencia entre los dos costos unitarios más bajos.
Identificar la fila o columna con la mayor penalidad.
En esa fila o columna, asignar la mayor cantidad posible a la
celda con el costo más bajo, limitada por la oferta y la demanda.
Eliminar la fila o columna que se satisfizo.
Repetir hasta que todas las ofertas y demandas estén
satisfechas.
* Ventaja: Generalmente produce una solución inicial muy cercana a
la óptima, a menudo incluso la óptima.
* Desventaja: Más complejo de aplicar que NWC o LCM.
Paso 3: Pruebas de Optimalidad y Mejoras Iterativas
Una vez obtenida una solución inicial, debemos verificar si es óptima
y, si no lo es, mejorarla. Los métodos más comunes para esto son:
Método del Paso a Paso (Stepping-Stone Method):
Identificar Celdas No Básicas (Vacías): Estas son las rutas de
transporte que no se están utilizando actualmente.
Calcular el Costo de Mejora para Cada Celda No Básica:
Para cada celda vacía, trazar un camino cerrado (un circuito)
usando solo celdas básicas (ocupadas). El circuito debe
comenzar en la celda vacía, moverse horizontalmente o
verticalmente, girar solo en celdas ocupadas, y terminar de
nuevo en la celda vacía.
Alternar signos (+/-) en cada esquina del circuito, comenzando
con un "+" en la celda vacía.
Sumar los costos unitarios de las celdas con signo "+" y restar
los costos unitarios de las celdas con signo "-". Este es el "costo
de mejora" o "evaluación de la celda".
Criterio de Optimalidad: Si todos los costos de mejora son cero o
positivos (para minimización), la solución actual es óptima.
Mejora de la Solución (Si no es Óptima):
Seleccionar la celda no básica con el costo de mejora más
negativo (si estás minimizando). Esta celda entrará en la base.
Identificar la cantidad mínima asignada a las celdas básicas con
un signo "-" en el circuito de la celda seleccionada.
Restar esa cantidad de las celdas con signo "-" y sumar esa
cantidad a las celdas con signo "+".
La celda básica de donde se resta la cantidad mínima se vuelve
no básica (sale de la base).
Repetir el proceso desde la identificación de celdas no básicas.
Método de Distribución Modificada (MODI - Modified Distribution
Method / UV Method):
Establecer Variables Duales (u y v): Asignar una variable u_i a
cada origen i y una variable v_j a cada destino j.
Resolver para u y v: Para cada celda básica (ocupada) (i, j), la
relación es C_{ij} = u_i + v_j. Se puede establecer
arbitrariamente una de las variables u_i o v_j (generalmente u_1
= 0) y resolver las demás.
Calcular el Costo de Mejora para Celdas No Básicas: Para cada
celda no básica (vacía) (i, j), calcular d_{ij} = C_{ij} - (u_i + v_j).
Criterio de Optimalidad: Si todos los d_{ij} son cero o positivos
(para minimización), la solución actual es óptima.
Mejora de la Solución (Si no es Óptima):
Seleccionar la celda no básica con el d_{ij} más negativo. Esta
es la celda que entra a la base.
Formar un circuito con esta celda entrante y las celdas básicas,
similar al método de Paso a Paso.
Ajustar las asignaciones de la misma manera que en el método
del Paso a Paso.
Repetir el proceso desde el cálculo de las variables duales.
Ventaja: Generalmente más eficiente que el método del Paso a
Paso para problemas grandes, ya que no requiere trazar
circuitos para cada celda no básica.
Paso 4: Solución Óptima
Cuando el criterio de optimalidad se cumple (todos los costos de
mejora son >= 0 para minimización), la solución actual es la
óptima.
Las asignaciones en las celdas básicas representan las
cantidades óptimas a transportar desde cada origen a cada
destino.
Calcular el costo total mínimo multiplicando las cantidades
asignadas por sus respectivos costos unitarios y sumando los
resultados.