ING. CARLOS L. ROJAS

PROBLEMA DE TRANSPORTE

•Busca determinar un plan de transporte de una mercancía de varias fuentes a varios destinos, contando con:

–Nivel de oferta en cada fuente y la cantidad de la demanda en cada destino.–El costo de transporte unitario de la mercancía de cada fuente a cada destino.

•El objetivo del modelo es determinar la cantidad que se enviará de cada fuente a cada destino, tal que se minimice el costo de transporte total.•Supone que el costo de transporte en una ruta es directamente proporcional al número de unidades transportadas.

PROBLEMA DE TRANSPORTEForma Estándar

•En las restricciones, todas las variables tienen

coeficiente +1.

•La oferta de productos es igual a la demanda

(Modelo de transporte equilibrado).

•Aun cuando este tipo de modelos se

resuelven utilizando el método simplex, puede

obtenerse la solución óptima más rápida y

eficientemente mediante algoritmos especiales.

PROBLEMAS DE TRANSPORTEAlgoritmo

•Encontrar una solución inicial factible.

•Determinar la variable que entra, que se elige entre las variables no básicas. Si todas las variables satisfacen la condición de optimidad (del método simplex), deténgase.

•Determinar la variable que sale (condición de factibilidad) de entre las variables de la solución básica actual.

•Obtener una nueva solución básica y regresar al paso 2.

PROBLEMAS DE TRANSPORTEMétodo de la Esquina Noroeste

1.- Comenzando en la esquina superior izquierda, asigne a esa celda tantas unidades como sea posible. La cantidad asignada será el mínimo entre la oferta y la demanda en esa celda.

2.- En esa celda, reduzca la oferta actual disponible y la demanda actual insatisfecha en la cantidad asignada.

3.- Identifique el primer origen con oferta disponible. Este es o bien el origen actual o el que está directamente abajo.

PROBLEMAS DE TRANSPORTEMétodo de la Esquina Noroeste

4.- Identifique el primer destino con demanda insatisfecha. Este es o bien el destino actual o el que está inmediatamente a la derecha de el.

5.- Asigne, como en el paso 1, tantos artículos como sea posible a la ruta asociada con la combinación origen- destino identificados anteriormente.

6.- Regrese al paso 2.

PROBLEMAS DE TRANSPORTEMétodo de Aproximación de Vogel

1.- Para cada renglón con una oferta disponible y cada columna con una demanda insatisfecha, calcule un costo de penalidad restando el dato menor del que le sigue en valor.

2.- Identifique el renglón o columna que tenga el mayor costo de penalidad (empates se rompen arbitrariamente).

3.- Asigne la máxima cantidad posible a la ruta disponible que tenga el costo mas bajo en el renglón o columna elegido en el paso 2.

PROBLEMAS DE TRANSPORTEMétodo de Aproximación de Vogel

4.- Reduzca la oferta y la demanda adecuados

en la cantidad asignada en el paso 3.

5.- Descarte cualquier renglón con oferta

disponible cero y columnas con demanda

insatisfecha cero, para consideraciones

posteriores.

6.- Regrese al paso 1.

PROBLEMAS DE TRANSPORTEMétodo de Aproximación de Vogel

7.- El paso final, es asignar las variables no básicas

faltantes a través del método del costo mínimo.

Nota: Si un renglón (origen) y una columna (destino)

se satisfacen al mismo tiempo, solo uno se tacha y al

otro se le asigna un valor de cero (0). Cualquier

renglón o columna con valor cero (0) no debe

utilizarse para calcular penalizaciones futuras.

PROBLEMAS DE TRANSPORTEDeterminación de la Solución Óptima

•Una vez obtenida la Solución Inicial Básica Factible

mediante el Método de la Esquina Noroeste o por el de

Aproximación de Vogel, se procede a iterar hasta alcanzar

la solución óptima.

•La Solución Óptima se obtiene utilizando el Método de los

Multiplicadores.

•Siendo M el número de Fuentes y N el número de

“Destinos”, toda solución (factible y óptima) deberá poseer

M+N-1 variables básicas.

PROBLEMAS DE TRANSPORTEMétodo de los Multiplicadores

•Asociar multiplicadores Ui con la fila “i” y Vj

con la columna “j” de la tabla de transporte.

•Para cada variable básica Xij de la solución

actual, los multiplicadores Ui y Vj deben

satisfacer la siguiente ecuación: Ui + Vj = Cij

(donde Cij es el costo unitario de transporte).

–Se obtiene de esta manera un sistema de M+N-1

variables con m+n incógnitas (Ui y Vj).

PROBLEMAS DE TRANSPORTEMétodo de los Multiplicadores

•Igualar a cero (0) la Ui que tenga el mayor número de

asignaciones en su renglón.

•Sustituir este valor, en el sistema de ecuaciones y

resolver algebraicamente, encontrando de esta

manera los valores de Ui y Vj.

•Calcular y llenar el valor de Cij – (Ui + Vj), COSTO

MARGINAL, para cada variable no básica X ij y aplicar

la condición de optimidad.

PROBLEMAS DE TRANSPORTEMétodo de los Multiplicadores

•CONDICIÓN DE OPTIMIDAD: Una solución

básica factible es óptima si, y solo si, el costo

marginal para toda variable no básica es no

negativo [Cij – (Ui + Vj) 0]. Si esto no se

cumple, entonces:

•Determinar la variable no básica que entra: La

variable no básica que tenga el costo marginal

[Cij – (Ui + Vj)] mas negativo (los empates se

rompen arbitrariamente).

PROBLEMAS DE TRANSPORTEMétodo de los Multiplicadores

•Determinar la Variable básica que sale:

Construir, en la tabla de transporte, un ciclo

cerrado (reacción en cadena) para la variable

actual que entra.

–El ciclo debe empezar y terminar en la variable

no básica designada para entrar.

–Consta de segmentos sucesivos horizontales y

verticales (conectados) cuyos puntos esquinas

deben ser variables básicas.

PROBLEMAS DE TRANSPORTEMétodo de los Multiplicadores

•Determinar la Variable básica que sale (Cont):

–Identificar en el ciclo, las celdas receptoras (+) y

las donadoras (-): Partiendo de la variable básica

que entra (+), alternar los signos en cada esquina.

–La variable que sale es la celda donadora con

menor valor (en caso de empate, se selecciona

arbitrariamente la variable que sale y el resto se

le asigna un valor de 0).

PROBLEMAS DE TRANSPORTEMétodo de los Multiplicadores

•La nueva solución básica factible se identifica

sencillamente sumando el valor de la variable

básica que sale a la asignación de cada celda

receptora y restando esa misma cantidad de la

asignación de cada celda donadora.

•Calcular nuevamente los multiplicadores y

aplicar la regla de optimidad.

PROBLEMAS DE TRANSPORTEProblemas no Equilibrados

Suministro en Exceso: Ocurre cuando la oferta es mayor

que la demanda. Para convertir el problema en

equilibrado, se procede de la siguiente manera:

•Agregar un destino ficticio en la tabla de transporte,

cuya demanda debe ser igual a la diferencia entre la

oferta y la demanda actual.

• El costo de transporte desde cada fuente a este destino

ficticio es cero (0).

•En la solución óptima, todos los artículos enviados al

destino ficticio, permanecerán en el origen.

PROBLEMAS DE TRANSPORTEProblemas no Equilibrados

Demanda en Exceso: Ocurre cuando la oferta es menor

que la demanda. Para convertir el problema en

equilibrado, se procede de la siguiente manera:

•Agregar un origen ficticio en la tabla de transporte, cuya

oferta debe ser igual a la diferencia entre la oferta y la

demanda actual.

•El costo de transporte desde este origen ficticio a cada

destino es cero (0).

•En la solución óptima, todos los artículos enviados

desde este origen ficticio se consideran como una

demanda no cubierta.

PROBLEMAS DE TRANSPORTEEliminación de Rutas Inaceptables

En el caso de que ciertas rutas (origen-destino)

de transporte sean inaceptables por

limitaciones de la organización, se procede de

la siguiente manera:

•Asignar a la ruta inaceptable un costo

arbitrariamente grande (identificado como M).

Esto elimina el uso de esa ruta en la solución

óptima.

Los yacimientos que hay que Los yacimientos que hay que explotar, no están en la tierra, ni en el explotar, no están en la tierra, ni en el número, ni en la máquina, sino en la número, ni en la máquina, sino en la

mente”.mente”.Juan Germán RoscioJuan Germán Roscio