Modelos y Algoritmos

MODELOS Y ALGORITMOS
PROBLEMAS DE TRANSPORTACION
UNIDAD 4
La programación lineal es una herramienta de modelos cuantitativos para manejar diferentes tipos de problemas y ayudar a la toma de decisiones.
El modelo de transporte es un problema de optimización de redes donde debe determinarse como hacer llegar los productos desde los puntos de existencia hasta los puntos de demanda, minimizandolos costos.
El modelo busca determinar un plan de transporte de una mercancía de varias fuentes a varios destinos. Entre los datos del modelo se cuenta:
Ejemplos:
1.- Nivel de oferta en cada fuente y la cantidad de demanda en cada destino.
2.- El costo de transporte unitario de la mercancía de cada fuente a cada destino.
El modelo se utiliza para realizar actividades como: control deinventarios, programación del empleo, asignación de personal, flujo de efectivo, programación de niveles de reservas en prensas entre otras.

Origen Destino
a1 1 1 b1

ai i j bj

am m n bn

Figura 1 Modelo de transporte
Donde:
ai = Capacidad dela fuente i.
bj = Demanda del almacén j.
m = Número de fuentes distribuidoras.
n = Número de destinos receptores.
MÉTODO DE SOLUCIÓN INICIAL
Mediante el uso del método simplex se pueden resolver los modelos de transporte y de cualquier otro tipo de problemas de programación lineal. Sin embargo debido a la estructura especial de modelo de transporte, podemos utilizar otro método que se hadiseñado para aprovechar las características de los problemas de transporte.
Los método de esquina noroeste, costo mínimo y aproximación de Vogel son alternativas para encontrar una solución inicial factible.

ESQUINA NOROESTE
Este método es considerado el más fácil. Es también considerado por ser el menos probable para dar una buena solución inicial y de “bajo costo” porque ignora lamagnitud relativa de los costos Cij.
Antes de describir el procedimiento, es necesario establecer que el número de variables básicas en cualquier solución básica de un problema de transporte es una menos de la que se espera. Normalmente, en los problemas de programación lineal, se tiene una variable básica para cada restricción.
Ejemplo:
En los problemas de transporte con m recursos y n destinos elnúmero de restricciones funcionales es m + n. Sin embargo, el número de variables básicas = m + n - 1

Este procedimiento esta dado por los siguientes tres pasos:
1.- Seleccionar la celda de la esquina noroeste (esquina superior izquierda) para envío.
2.- Efectuar el más grande envío como pueda en la celda de la esquina noroeste.
Esta operación agotará completamente la disponibilidad desuministros en un origen o los requerimientos de demanda en un destino.
3.- Corrija los números de suministro y los requerimientos para reflejar lo que va quedando de suministro y requerimiento y regresar al paso 1.
COSTO MÍNIMO
Este es un procedimiento que se utiliza tomando como base a las rutas que tengan el menor costo.
El procedimiento es el siguiente:

Asígnese el valor más grandeposible a la variable con menor costo unitario de toda la tabla. (Los empates se rompen arbitrariamente). Táchese el renglón o columna satisfecha. (Como en el método de la esquina noroeste, si una columna y un renglón se satisfacen de manera simultánea, sólo una puede tacharse). Después de ajustar la oferta y la demanda de todos los renglones y columnas no tachados, repítase el proceso asignandoel valor más grande posible a la variable con el costo unitario no tachado más pequeño. El procedimiento esta completo cuando queda exactamente un renglón o una columna sin tachar.

MÉTODO PARA LA OBTENCIÓN DE LA SOLUCIÓN ÓPTIMA (MULTIPLICADORES)
El método de multiplicadores es un procedimiento secuencial que empieza con una solución inicial factible del problema de transporte, para...