Problema de transporte

UNIVERSIDAD METROPOLITANA

ESCUELA DE INGENIERIA

DEPARTAMENTO PRODUCCIÓN INDUSTRIAL

GESTION DE CADENA DE SUMINISTRO I

PROF. GERARDO MARTINEZ

PROBLEMA DE TRANSPORTE

Una empresa tiene tres sucursales en occidente del país: Barinas con diez (10) unidades de capacidad de producción mensual; Trujillo con veinte (20) unidades de capacidad de producción mensual y Mérida con treinta (30) unidades de capacidad de producción mensual.

Si su producto debe ser enviado a Caracas (necesitan 28 unidades), Maracaibo (necesitan 20 unidades) y Los Teques (necesitan 12 unidades) y tienen los costos de envío entre ciudades, según la Tabla 1, ¿cuánto deben enviar desde cada fuente a cada destino? y ¿cuánto es el costo total de estos envíos?

[pic 1]

        El modelo de este problema queda:

Min: Zo = 50 X11 + 20 X12 + 30 X13 + 15 X21 + 12 X22 + 10 X23 + 20 X31 + 30 X32 + 40 X 33

s.a.

X11 + X12 + X13 = 10

X21 + X22 + X23 = 20

X31 + X32 + X33 = 30

X11 + X21 + X31 = 12

X12 + X22 + X32 = 20

X13 + X23 + X33 = 28

Se tiene la restricción redundante, que hace perder un grado de libertad:

X11 + X12 + X13 + X21 + X22 + X23 + X31 + X32 + X33 =

X11 + X21 + X31 + X12 + X22 + X32 + X13 + X23 + X33

La cual no se incluye en el modelo.

Además se tendrían las restricciones de variables enteras:

Xij ع Z+ √ i, √ j.

Por lo cual la tabla Simplex será:

[pic 2]

Donde se puede observar que es una tabla esparcida, por lo cual resolver el problema por Simplex no debe resultar muy eficiente. De allí que se hayan creado métodos especiales para resolver el problema de transporte, los cuales parten de la siguiente tabla:

Tabla del modelo de transporte

[pic 3]

En este caso, como se tienen tres fuentes y tres restricciones, se deben conseguir: 3 + 3 - 1 = 5 Variables básicas.

En este caso se dispone de varios métodos para conseguir una solución inicial:

Esquina noroeste o superior izquierda.

Costo mínimo

Por fila

Por columna

General

Vogel

Russell

: Por esquina superior izquierda:

[pic 4]

Y la última iteración, donde se consigue la quinta variable básica queda:

[pic 5]

Que arrojaría un costo total de: 50*10 + 20*0 + 30*0 + 15*2 + 12*18 + 10*0 + 20*0 + 30*2 + 40*28 = 500 + 30 + 216 + 60 + 1120 = 1926.

Con X11 = 10; X21 = 2; X22 = 18; X32 = 2 y X33 = 28.

La cual es una solución factible, pero no necesariamente óptima.

En el caso que se hubiese usado costo mínimo: Por columnas:

[pic 6]

Se pasa finalmente a la tercera columna:

[pic 7]

Que de nuevo sería una solución básica inicial, la cual arroja un costo total de:

15*12 + 20*10 + 12*8 + 30*2 + 40*28 = 180 + + 200 + 96 + 60 + 1120 = 1656.

Con X21 = 12; X12 = 10; X22 = 8; X32 = 2 y X33 = 28.

Y aunque mejor que la anterior, no tiene garantía de ser óptima.

En el caso que se hubiese usado costo mínimo: Por filas:

[pic 8]

Y para finalizar, aún en la tercera fila:

[pic 9]

Que de nuevo sería una solución básica inicial, la cual arroja un costo total de:

20*10 + 10*20 + 20*12 + 30*10 + 40*8 = 200 + 200 + 240 + 300 + 320 = 1260.

Con X12 = 10; X23 = 20; X31 = 12; X32 = 10 y X33 = 8.

Y aunque mejor que las anteriores, no tiene garantía de ser óptima.

En el caso que se hubiese usado costo mínimo: General:

[pic 10]

Y finalmente:

[pic 11]

Que de nuevo sería una solución básica inicial, la cual arroja un costo total de:

20*10 + 10*20 + 20*12 + 10*30 + 40*8 = 200 + 200 + 240 + 300 + 320 = 1260.

Con X12 = 10; X23 = 20; X31 = 12; X32 = 10 y X33 = 8.

Que coincide con la anterior y no tiene garantía de ser óptima.

Aunque costo mínimo suele dar una mejor solución de partida que esquina noroeste, no necesariamente es una buena solución inicial, hay dos métodos, que por lo menos en teoría suelen ofrecer mejores soluciones básicas: Vogel y Russell.

Ambos métodos, en la práctica, son algoritmos que tratan de evitar que se haga uso de alternativas que pueden resultar muy costosas.

Vogel se puede resumir en:

Determinar una penalización para cada fila y columna restando al segundo menor costo el menor costo de la respectiva fila o columna.

Se escoge como variable a ser usada la de costo mínimo de la fila o columna de mayor penalización (los empates se resuelven al azar) e igual que los métodos anteriores se asigna la máxima cantidad posible (Min {fi, dj}).

Se elimina la fila o columna cuyas unidades necesarias ya estén asignadas, si tanto la fila como la columna se anulan simultáneamente, sólo una se elimina y a la otra se deja en cero. Aquellas filas o columnas en cero no se usarán para calcular nuevas penalizaciones.

Se regresa a calcular las penalizaciones de las filas y columnas activas (no tachadas y distintas de cero)

Si sólo queda una fila o columna por eliminar, o si todas las filas o columnas no eliminadas tienen valor cero, se hace la asignación de las variables por el método de costo mínimo general.

Una solución inicial por Vogel sería:

[pic 12]

Y finalmente:

[pic 13]

Que de nuevo sería una solución básica inicial, la cual arroja un costo total de:

20*10 + 10*20 + 20*12 + 10*30 + 40*8 = 200 + 200 + 240 + 300 + 320 = 1260.

Con X12 = 10; X23 = 20; X31 = 12; X32 = 10 y X33 = 8.

Que coincide con la anterior y no tiene garantía de ser óptima.

...