MÉTODO DE TRANSPORTE
Es un método de programación lineal para la asignación de artículos de un conjunto de origines a un conjunto de destinos de tal manera que se optimice la función objetivo.
Esta técnica es particularmente usada en organizaciones que producen el mismo producto en numerosas plantas y que envía sus productos a diferentes destinos (Centros de distribución, almacenes). También se aplica en distribución, análisis de localización de plantas y programación de la producción.
Se han desarrollado diferentes enfoques para resolver este problema de distribución, tales como: El método de la esquina noroeste, el método modificado de la esquina noroeste (celda mínima), método del trampolín (Cruce de arroyo, stepping stone), método de la distribución modificada (MODI), método de aproximación de Vogel y el método simplex.
Se cubrirán únicamente en estas notas los siguientes métodos:
a) Esquina Noroeste
b) Modificado de la esquina Noroeste.
c) Aproximación de Vogel.
d) Del trampolín (Stepping stone)
Para que un problema pueda ser solucionado por el método de transporte, este debe reunir tres condiciones:
1) La función objetivo y las restricciones deben de ser lineales.
2) Los artículos deben de ser uniformes e intercambiables, los coeficientes de todas las variables en la ecuación deben de ser 0 o 1.
3) La suma de las capacidades de las fuentes debe ser igual a la suma de los requerimientos de los destinos, si alguna desigualdad existe una variable de holgura deberá ser añadida.
FORMULACIÓN DEL PROBLEMA DE TRANSPORTE.
Una cierta clase de problemas de programación lineal, conocida como problema de transporte se da muy frecuentemente en aplicaciones prácticas. El problema general de transporte puede ser formulado como sigue:
Un producto está disponible en ciertas cantidades conocidas en cada uno de los m orígenes. Es requerido que ciertas cantidades de un producto sean transportadas a cada uno de los n destinos. El mínimo costo de transportar una unidad de cualquier origen a cualquier destino es conocido. Se desea determinar el programa de los envíos que minimiza el costo total de transporte.
Sea ai la cantidad de producto disponible en el origen i y bj la cantidad de producto requerida en el destino j. El costo de transportar una unidad de origen i al destino j será escrita como cij. Se asumirá que la cantidad disponible sea igual a la cantidad producida.
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:
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 de inventarios, programación del empleo, asignación de personal, flujo de efectivo, programación de niveles de reservas en prensas entre otras.
Origen Destino
Donde:
ai = Capacidad de la 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.
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.
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. En los problemas de transporte con m recursos y n destinos el nú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 de suministros 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.
El procedimiento es el siguiente:
Asígnese el valor más grande posible a la variable con menor costo unitario de toda la tabla. (Los empates se rompen arbitrariamente). Táchese el renglón o columna satisfecho. (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 asignando el 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.
Este método es heurístico y suele producir una mejor solución inicial que los métodos anteriores. De hecho, suele producir una solución inicial óptima, o próxima al nivel óptimo.
Los pasos del procedimiento son los siguientes ( 18 ).
1.- Evalúese una una penalización para cada renglón (columna) restando el menor elemento de costo del renglón (columna) del elemento de costo menor siguiente en el mismo renglón (columna).
2.- Indentifíquese el renglón o columna con mayor penalización, rompiedo empates en forma arbitraria. Asigne el mayor valor posible a las variables con el costo más bajo del renglón o columna seleccionado. Ajústese la oferta y la demanda y tachese el renglón o columna satisfecho. Si un renglón y una columna se satisfacen al mismo tiempo, sólo uno de ellos se tacha y al renglón (columna) restante se le asigna una oferta (demanda) cero. Cualquier renglón o columna con oferta o demanda cero no debe utilizarse para calcular penalizaciones futuras (en el paso 3).
3: a) si sólo hay un renglón o columna sin tachar, detengase.
b) si sólo hay un renglón (columna) con oferta (demanda) positiva sin tachar,determinese las variables básicas del renglón ( columna) a través del método de costo mínimo.
c) si todos los renglones o columnas sin tachar tiene oferta y demanda cero asignadas, determínese las variables básicas cero a través del método de costo mínimo. Deténgase.
d) de lo contrario, calcúlese las penalizaciones de los renglones y columnas no tachados y después diríjase al paso 2. (Obsérvese que los renglones y columnas con oferta y demanda cero asignadas no deben utilizarse para determinar estas penalizaciones).
1. Use la solución actual para crear una trayectoria única del paso secuencial. Use estas trayectorias para calcular el costo marginal de introducir a la solución cada ruta no usada.
2. Si todos los costos marginales son iguales o mayores que cero, deténgase; se tendrá la solución óptima. Si no, elija la celdilla que tenga el costo marginal más negativo. (Los epates se resolverán arbitrariamente)
3. Usando la trayectoria del paso secuencial, determine el máximo número de artículos que se pueden asignar a la ruta elegida en el paso 2 y ajuste la distribución adecuadamente.
4. Regrese al paso 1.
Soluciónes degeneradas.
1. Supóngase que en el problema general hay m origenes y n destinos. En el ejemplo actual m = 3 , n = 4. Si una solución factible usa menos de m + n - 1 rutas el problema se llama degenerado. Se tiene que hacer ajustes para usar el metodo de multiplicadores.
La determinación de la trayectoria apropiada es más complicada que el mero hecho de saltar de una celdilla a otra ya usando en el mismo renglón o la misma columna. Pueden encontrarse callejones sin salida, en cuyo caso se deben hacer otro intento distinto.
Número de celdillas en una trayectoria
La trayectoria de pasos secuenciales obtenida en los pasos 1 - 5 contiene cuatro celdas. El hecho de que cualquier renglón o columna que tenga un signo + debe tener tambien un signo - obliga a ello. Aunque siempre debe haber por lo menos cuatro celdillas, la trayectoria podría necesitar más de cuatro.
Condiciones de detención para una trayectoria del paso secuencial.
El proceso continúa alternando los signos + y - tanto en los renglones como en las columnas hasta que se obtenga una sucesión de celdillas que satisfagan dos condiciones.
1. Hay un signo + en la celdilla desocupada original de interés.
2. Cualquier renglón o columna que tenga un signo + debe tener también un signo - y viceversa.
La sucesión de pasos que tenga esta propiedades se llama trayectoria.
La programación lineal es una herramienta de modelos cuantitativos para manejar diferentes tipos de problemas y ayudar a la toma de decisiones.
En este capítulo se considera el modelo de transporte por medio del cual un administrador debe determinar la mejor forma de como hacer llegar los productos de sus diversos almacenes a sus consumidores, con el fin de satisfacer de las clientes y a un costo mínimo.
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, minimizando los costos de envio.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:
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 de inventarios, programación del empleo, asignación de personal, flujo de efectivo, programación de niveles de reservas en prensas entre otras.
Origen Destino
Donde:
ai = Capacidad de la fuente i.
bj = Demanda del almacén j.
m = Número de fuentes distribuidoras.
n = Número de destinos receptores.
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.
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. En los problemas de transporte con m recursos y n destinos el nú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 de suministros 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.
El procedimiento es el siguiente:
Asígnese el valor más grande posible a la variable con menor costo unitario de toda la tabla. (Los empates se rompen arbitrariamente). Táchese el renglón o columna satisfecho. (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 asignando el 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.
Este método es heurístico y suele producir una mejor solución inicial que los métodos anteriores. De hecho, suele producir una solución inicial óptima, o próxima al nivel óptimo.
Los pasos del procedimiento son los siguientes ( 18 ).
1.- Evalúese una una penalización para cada renglón (columna) restando el menor elemento de costo del renglón (columna) del elemento de costo menor siguiente en el mismo renglón (columna).
2.- Indentifíquese el renglón o columna con mayor penalización, rompiedo empates en forma arbitraria. Asigne el mayor valor posible a las variables con el costo más bajo del renglón o columna seleccionado. Ajústese la oferta y la demanda y tachese el renglón o columna satisfecho. Si un renglón y una columna se satisfacen al mismo tiempo, sólo uno de ellos se tacha y al renglón (columna) restante se le asigna una oferta (demanda) cero. Cualquier renglón o columna con oferta o demanda cero no debe utilizarse para calcular penalizaciones futuras (en el paso 3).
3: a) si sólo hay un renglón o columna sin tachar, detengase.
b) si sólo hay un renglón (columna) con oferta (demanda) positiva sin tachar,determinese las variables básicas del renglón ( columna) a través del método de costo mínimo.
c) si todos los renglones o columnas sin tachar tiene oferta y demanda cero asignadas, determínese las variables básicas cero a través del método de costo mínimo. Deténgase.
d) de lo contrario, calcúlese las penalizaciones de los renglones y columnas no tachados y después diríjase al paso 2. (Obsérvese que los renglones y columnas con oferta y demanda cero asignadas no deben utilizarse para determinar estas penalizaciones).
1. Use la solución actual para crear una trayectoria única del paso secuencial. Use estas trayectorias para calcular el costo marginal de introducir a la solución cada ruta no usada.
2. Si todos los costos marginales son iguales o mayores que cero, deténgase; se tendrá la solución óptima. Si no, elija la celdilla que tenga el costo marginal más negativo. (Los epates se resolverán arbitrariamente)
3. Usando la trayectoria del paso secuencial, determine el máximo número de artículos que se pueden asignar a la ruta elegida en el paso 2 y ajuste la distribución adecuadamente.
4. Regrese al paso 1.
Soluciónes degeneradas.
1. Supóngase que en el problema general hay m origenes y n destinos. En el ejemplo actual m = 3 , n = 4. Si una solución factible usa menos de m + n - 1 rutas el problema se llama degenerado. Se tiene que hacer ajustes para usar el metodo de multiplicadores.
La determinación de la trayectoria apropiada es más complicada que el mero hecho de saltar de una celdilla a otra ya usando en el mismo renglón o la misma columna. Pueden encontrarse callejones sin salida, en cuyo caso se deben hacer otro intento distinto.
Número de celdillas en una trayectoria
La trayectoria de pasos secuenciales obtenida en los pasos 1 - 5 contiene cuatro celdas. El hecho de que cualquier renglón o columna que tenga un signo + debe tener tambien un signo - obliga a ello. Aunque siempre debe haber por lo menos cuatro celdillas, la trayectoria podría necesitar más de cuatro.
Condiciones de detención para una trayectoria del paso secuencial.
El proceso continúa alternando los signos + y - tanto en los renglones como en las columnas hasta que se obtenga una sucesión de celdillas que satisfagan dos condiciones.
1. Hay un signo + en la celdilla desocupada original de interés.
2. Cualquier renglón o columna que tenga un signo + debe tener también un signo - y viceversa.
La sucesión de pasos que tenga esta propiedades se llama trayectoria.
a1 1 
1 b1
1 b1
ai i j bj
j bj
am m n bn
n bn
Figura 1 Modelo de transporte
Mediante el uso del método simplex se pueden resolver los modelos de transporte y de cualquier otro tipos de problemas de programación lineal. Sin embargo debido a la estructura especial de modelo de transporte, podemos utilizar otro método que se ha diseñado para aprovechar las características de los problemas de transporte.
Este método es considera 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 la magnitud relativa de los costos Cij.
Costo mínimo.
Este es un procedimiento que se utiliza tomando como base a las rutas que tengan el menor costo:
Método de Vogel.
El método de multiplicadores es un procedimiento secuencial que empieza con una solución inicial factible del problema de transporte, para encontrar la solución óptima. En cada paso se intenta en este procedimiento enviar artículos por las rutas que no se hayan usado en la solución factible en curso, en tanto que se elimina una de las rutas que esté siendo usada actualmente. Este cambio de ruta se hace de modo que: la solución se conserve factible, mejore el valor de la función objetivo.
