PROBLEMA DEL TRANSPORTE

• El PT es un caso particular de la PL

• Se debe determinar un esquema óptimo de transporte que se origina en los lugares de oferta donde la existencia de cierta mercancía es conocida, y llega a los lugares de donde se conoce la cantidad requerida. El costo de cada envió es proporcional a la cantidad transportada y, el costo total es la suma de los costos individuales.

Esquema tabular del PT

D1 D2 ............... Dn ai

O1

c11 c12...............

c1na1

O2

c12 c22...............

c2na2

.........

.........

.........

...............

.........

.........

Om

cm1 cm2

...............

cmn

am

bj b1 b2 ................ bn

D E S T I N O SO

R I G

E N

E S

Una solución al PT queda definido por un conjunto de mxn número Xij, donde:

Xij : Número de unidades a enviar desde el origen i al destino j

Siendo Xij ≥ 0

X11 X12 ..... X1n

X21 X22 ..... X2n

... .... .... ....Xm1 Xm2 …. Xmn

X =

El programa lineal del Problema del transporte queda expresado de la siguiente manera:

Sujeto a:

i=1,....,m

j=1,....,n

m

i

n

jijij XcZMin

1 1

)(

0ijX

n

jiij aX

1

m

ijij bX

1

METODOS PARA HALLAR SOLUCION FACTIBLE BASICA INICIAL

METODO DE LA ESQUINA NOR OESTE

Se empieza en la casilla (1,1) calculando X11 = min(a1,b1). Si a1 < b1, se hace b1 = b1 – a1 y se pasa a la casilla (2,1) calculando X21 = min(a2,b1).

Si a1 > b1 entonces se hace a1 = a1 – b1 y se pasa a la casilla (1,2) para calcular X12 = min (a1, b2), y así se continua hasta obtener la sfbi.

EJEMPLO:Una compañía tiene 3 fábricas ubicadas en A, B y C, las cuales proveen a los almacenes que están ubicados en D, E, F y G.

La capacidad de producción de las fábricas son de 70, 90 y 115 unidades mensuales respectivamente, mientras que las capacidades de los almacenes es de 50, 60 , 70 y 95 unidades respectivamente.

El costo de envió de una unidad desde cada una de las fábricas a cada una de los almacenes se presenta en el siguiente cuadro (en $).

Determinar la solución factible básica inicial utilizando el método de la esquina NO

D1 D2 D3 D4

O1 17 20 13 12

O2 15 21 26 25

O3 15 14 15 17

D1 D2 D3 D4 ai

17 20 13 12

15 21 26 25

15 14 15 17

bj 50 60 70 95

O1

O2

O3

70

90

115

Se colocan los datos en forma tabular.

X11 = min (a1,b1)=min (70,50) = 50 a1 = a1 - b1 = 70 – 50 = 20

X12 = min (a1,b2)=min (20,60) = 20 b2 = b2 - a1 = 60 – 20 = 40

X22= min (a2,b21)=min (90,40) = 40 a2 = a2 – b2 = 90 – 40 = 50

X23 = min (a2,b3)=min (50,70) = 50 b3 = b3 – b2 = 70 – 50 = 20

X33= min (a3,b3)=min (115,200) = 50 a3 = a3 – b3 = 115 – 20 = 95

X34= min (a3,b41)=min (95,95) = 95

Por consiguiente la solución es:

Z = 17*50+20*20+21*40+26*50+15*20+17*95

Z = $ 5305

D1 D2 D3 D4 ai

17 20 13 12

15 21 26 25

15 14 15 17

bj 50 60 70 95

O1

O2

O3

70

90

115

50 20

40 50

20 95

Caso 1: Minimización de costos de desplazamiento

El hospital Saludmuch pertenece a la Compañía de Seguros Todosalud SA. Esta sociedad tiene un Centro de Asistencia Primaria (CAP) en 5 ciudades de una región (un CAP en cada ciudad). Para obtener un buen funcionamiento global del servicio y poder planificar el número de visitas en función del personal previsto en cada CAP y de su dimensión, Todosalud S.A. ha decidido organizar el servicio de tal forma que todos sus asegurados tengan un CAP de referencia asignado, pero que sea éste el más cercano posible a su lugar de residencia. En la región hay 5 ciudades y la compañía sabe cuantos asegurados tiene en cada uno de ellos. Los CAP tienen una capacidad máxima de pacientes que pueden soportar. El objetivo es asignar a los asegurados a los CAPs minimizando el coste de desplazamiento o la distancia total.

CAP 1 CAP 2 CAP 3 CAP 4 CAP 5Número de asegurados

Ciudad 1 2 5 4 8 6 500Ciudad 2 5 6 3 8 7 700Ciudad 3 6 2 8 10 5 1000Ciudad 4 6 8 9 5 3 800Ciudad 5 8 5 7 10 6 600Capacidad máxima de atención

750 800 650 900 500

Si no existiera el problema de capacidad de los CAPs, el modelo sería trivial, ya que bastaría asignar cada ciudad al CAP más cercano, obteniéndose el coste de transporte más barato. Al tener límites en la capacidad, puede ser que no todas las ciudades tengan asignado el centro más cercano, ya que esto implicaría una sobre utilización. Entonces, puede ser que alguna ciudad, o parte de ella tenga asignada un CAP que no es el más cercano, en función de la disponibilidad o holgura del sistema.

El PT en sus forma tabular quedaría de la siguiente manera:

El PT es un problema balanceado:

ji ba

El número de variables básicas esta dado por (m + n – 1)

D1 D2 D3 D4 D5 ai

O12 5 4 8 6

500

O25 6 3 8 7

700

O36 2 8 10 5

1000

O46 8 9 5 3

800

O58 5 7 10 6

600bj 750 800 650 900 500

METODO DE RUSSELL

Proporciona una solución inicia cercana a la óptima.

El procedimiento es el siguiente:

1. Calcular ui = max cij vj = max cij

2. Encuentre la variable Xij = max (i,j) [(ui + vj –cij) > 0]

3. Introducir a la base Xij = min (ai , bj )

Si ai < bj hágase bj = bj – ai y elimine la fila i

Si ai > bj hágase ai = ai – bj y elimine la columna j

Si ai = bj elimínese fila i o columna j

4. El método termina cuando loa ai y los bj son ceros.

ai ui

17 20 13 12

15 21 26 25

15 14 15 17

bj

vj

20

26

17

17 21 26 25

90

115

50 60 70 95

D2 D3 D4

70O1

O2

O3

D1

20 21 33 3328 26 26 2618 24 28 25

(ui + vj - cij)

Introducimos a la base la variable:

X14 = min (70, 95) = 70 b4 = 95 – 70 = 25

y elimine la fila 1.

Repetimos el proceso:ai ui

15 21 26 25

15 14 15 17

bj

vj 15 21 26 25

O3 115 17

50 60 70 95

O1 0

O2 90 26

D1 D2 D3 D4

Introducimos a la baseX33 = min (115, 70) = 70 a3 = 115 – 70 = 45y elimine la columna 3

26 26 26 2617 24 28 25

(ui + vj - cij)

ai ui

15 21 25

15 14 17

bj

vj 15 21 25

O3 115 17

50 60 0 95

O1 0

O2 90 25

D1 D2 D3 D4

Introducimos a la baseX21 = min (90 , 50) = 50 a2 = 90 - 50= 40y elimine la columna 1

25 25 2517 24 25

(ui + vj - cij)

ai ui

21 25

14 17

bj

vj 21 25

O3 115 17

0 60 0 95

O1 0

O2 90 25

D1 D2 D3 D4

Introducimos a la baseX34= min (45, 25) = 25 a3 = 45 - 25= 20y elimine la columna 4

25 2524 25

(ui + vj - cij)

Introducimos a la baseX22= min (40 , 60) = 40 a2 = 60 - 40= 20y elimine la columna 2

Introducimos a la baseX32= min (20 , 20) = 20

La solución por lo tanto es :ai

17 20 13 1270

15 21 26 2550 40

15 14 15 1720 70 25

bj

O3 115

50 60 70 95

O1 70

O2 90

D1 D2 D3 D4

El costo de la solución es Z = $ 4,185

Generación de nuevas solucionesConsideremos la solución inicial hallada por el método de la esquina N.O.

El costo de la solución era Z = $ 5,305Si se ingresa a la base la variable X14, el nuevo valor de Z1 = Z + X14 * D14 = 5305 + 20 (-15) = $5,005DondeD14 = c14 – c34 + c33 – c23 + c22 – c12 = 12-17+15-26+21-20= -15

ai- +

50 20

+ -

40 50

+ -

20 95

bj

90

115

50 60 70 95

D2 D3 D4

70O1

O2

O3

D1

Solución OptimaMétodo MODI o UVConsideremos la solución inicial hallada por el método de la Esquina N.O.

ai17 20 13 12

50 20

15 21 26 25

40 50

15 14 15 17

20 95

bj

Z = $ 5305

90

115

50 60 70 95

D2 D3 D4

70O1

O2

O3

D1

Paso 2: Se dibuja la matriz Zij que contiene los costos de la variable solución

17 2021 26

15 17

Paso 3: Se construye un conjunto de números vj y ui tal que la suma iguale a los valores de la matriz Zij del paso 2 y se completa las celdas vacías con la suma de los ui y vj la matriz Zij que contiene los costos de la variable solución.

Se tiene las siguientes ecuaciones de las celdas básicas:U1 + v1 = 17 u2 + v3 = 26U1 + v2 = 20 u3 + v3 = 15U2 + v2 = 21 u3 + v4 = 17

Haciendo v1 = 0 se encuentra que: u1 = 17 ; v2 = 3 ; u2 = 18V3 = 8 ; u3 = 7 ; v4 = 10

vjui 0 3 8 10

17 17 20 25 2718 18 21 26 287 7 10 15 17

Paso 4: Se calcula Cij - Zij

vjui 0 3 8 10

17 17 20 25 2718 18 21 26 287 7 10 15 17

17 20 13 1215 21 26 2515 14 15 17

-

= 0 0 -12 -15-3 0 0 -38 4 0 0

Cij - Zij

Se selecciona la casilla (1,4) que tiene el costo de entrada mas pequeño, por consiguiente debe entrar a la base la variable X14

ai

- +50 20

+ -40 50

+ -20 95

bj

O3 115

50 60 70 95

O1 70

O2 90

D1 D2 D3 D4

ai

50 20

60 30

40 75

bj

O3 115

50 60 70 95

O1 70

O2 90

D1 D2 D3 D4

El costo de la nueva solución es: Z1 = 5305 + (20)(-15) = 3005

A continuación probamos si esta solución es o no la óptima

Se calcula Cij - Zij

vjui 0 -12 -7 -5

17 17 5 10 1233 33 21 26 2822 22 10 15 17

17 20 13 1215 21 26 2515 14 15 17

-

=0 15 3 0

-18 0 0 -3-7 4 0 0

Cij - Zij

Se selecciona la casilla (2,1) que tiene el costo de entrada mas pequeño, por consiguiente debe entrar a la base la variable X21

ai

- +50 20

+ -60 30

+ -40 75

115

50 60 70 95

70

90

D1 D2 D3 D4

El costo de la nueva solución es: Z2 = 5005 + (30)(-18) = 4465

A continuación probamos si esta solución es o no la óptima

ai

20 50

30 60

70 45115

50 60 70 95

70

90

D1 D2 D3 D4

Se calcula Cij - Zij

vjui 0 -6 -7 -5

17 17 23 10 1215 15 21 8 1022 22 28 15 17

17 20 13 1215 21 26 2515 14 15 17

-

= 0 -3 3 00 0 18 15-7 -14 0 0

Cij - Zij

Se selecciona la casilla (3,2) que tiene el costo de entrada mas pequeño, por consiguiente debe entrar a la base la variable X32

ai

70

50 40

20 70 25

bj

O3 115

50 60 70 95

O1 70

O2 90

D1 D2 D3 D4

El costo de la nueva solución es: Z2 = 4465+ (20)(-14) = 4185

A continuación probamos si esta solución es o no la óptima

ai

- +50 20

+ -60 30

+ -40 75

bj

O3 115

50 60 70 95

O1 70

O2 90

D1 D2 D3 D4

Se calcula Cij - Zij vjui 0 6 7 9

3 3 9 10 1215 15 21 22 248 8 14 15 17

17 20 13 1215 21 26 2515 14 15 17

-

=14 11 3 00 0 4 17 0 0 0

Cij - Zij

Esta es la solución óptima