PAUTAAyu PTransporte JP

Producción Profesor (a): Carlos Melo Ayudante (s): Jorge Pontigo

U N I V E R S I D A D D I E G O P O R T A L E S F A C U L T A D D E I N G E N I E R I A E S C U E L A D E I N G E N I E R I A I N D U S T R I A L

Semestre Primavera 2013

(Comprensión y resolución del problema de transporte)

1.- Una empresa fabricante de televisores posee dos plantas de producción, una en Corea del Sur y otra en

Brasil. La producción máxima factible en cada planta (en miles de unidades mensuales) son,

respectivamente, 60 y 35. La empresa cuenta con tres centros de distribución (América, Asia, y Europa)

con demandas mensuales de 30, 35 y 20, respectivamente. Los costos reportados por atender cada punto

de demanda (por cada mil unidades de demanda) desde cada planta se entregan en la tabla a continuación:

América Asia Europa Oferta

Corea del Sur 15 10 20 60

Brasil 12 20 15 35

Demanda 30 35 20

(a) Escriba el problema como un modelo de programación lineal.

(b) Realice la transformación del problema que estime conveniente para poder resolverlo como un

problema de transporte.

(c) Determine una solución inicial usando el método de la esquina noroeste.

(d) A partir de la solución inicial encontrada en b, realice una iteración del algoritmo para resolver este

problema. ¿Es la solución encontrada óptima?, ¿por qué?

(e) Encuentre la solución óptima del problema.

Hint:

Cálculo de los costos reducidos de la planta 𝑖 al centro 𝑗.

Número de variables básicas del problema (𝑚 + 𝑛 − 1)

Problema de transporte




2.- ¿Qué corresponde hacer según la heurística de Khumawala con 5 posibles candidatos de localización en

las siguientes situaciones?

(a) Al resolver MINSAVE se obtiene que todas las plantas tienen MINSAVE negativo.

(b) Al resolver MINSAVE se obtiene que dos plantas tienen MINSAVE positivo, una cero, y el resto

negativo.

(c) Al resolver MAXSAVE se obtiene que de las plantas pendientes todas tienen MAXSAVE negativo

excepto una que tiene MAXSAVE igual a cero.

(d) Al resolver MAXSAVE se obtiene que de las plantas pendientes todas tienen MAXSAVE positivo

excepto una que tiene MAXSAVE igual a cero.

(e) Al resolver MAXSAVE se obtiene que de las plantas pendientes una planta tiene MAXSAVE negativo,

una cero, y otras dos positivo.

PAUTA 1.-

Gráficamente, el problema queda:

a) Determine una solución inicial usando el método de la esquina noroeste.

Respuesta:

Utilizando el método expuesto, la solución inicial es la siguiente:

América Asia Europa D Si

Corea del Sur

30 30 - - 60

Bras

il

60

35

30

35

20

Core

a

Améric

a

Asi

Europ

a

1

0 D




Brasil - 5 20 10 35

Dj 30 35 20 10

Donde las variables básicas son: X11 = 30; X12 = 30; X22 = 5; X23 = 20; X24 = 10 Corresponde al valor de (m+n-1), que en este caso es 5.

b) A partir de la solución inicial encontrada en b, realice una iteración del algoritmo para resolver

este problema. ¿Es la solución encontrada óptima?, ¿por qué? Respuesta suponiendo los costos

ficticios iguales a 20:

La solución inicial es:


Corea del Sur

15

30 10

30 20

- 20

- 60

Brasil 12

- 20

5 15

20 20

10 35

Dj 30 35 20 10

Donde las variables básicas son: X11 = 30; X12 = 30; X22 = 5; X23 = 20; X24 = 10

Luego, para la primera iteración, tenemos que, para estas 5 variables, el costo reducido es igual a cero, por lo tanto:

11 1 1

1 1

12 1 2

2 2

22 2 2

3

23 2 3

4

24 2 4

0

15 00 15

10 010 10

20 05

15 010

20 0

ij ij i jr c u v

r u vu v

r u vu v

r u vv

r u vv

r u v

Calculamos el costo reducido ahora para los arcos que están fuera de la base, y tenemos que:

13 1 3

14 1 4

21 2 1

20 20 0 5 15

20 20 0 10 10

12 12 10 15 13

r u v

r u v

r u v




Como hay una variable con costo reducido negativo debe entrar esta variable a la base. Así, tenemos que:


Corea del Sur

15

30 (-) 10

30 (+) 20

- 20

- 60

Brasil 12

- (+) 20

5 (-) 15

20 20

10 35

Dj 30 35 20 10

Claramente se observa que, de las variables que bajan, la primera que llega a cero es X22, luego sale de la base. Así, la nueva solución es:


Corea del Sur

15

25 10

35 20

- 20

- 60

Brasil 12

5 20

- 15

20 20

10 35

Dj 30 35 20 10


Luego, para la esta solución, tenemos que, para estas 5 variables, el costo reducido es igual a cero, por lo tanto:

11 1 1

1 1

12 1 2

2 2

21 2 1

3

23 2 3

4

24 2 4

0

15 00 15

10 03 10

12 018

15 023

20 0

ij ij i jr c u v

r u vu v

r u vu v

r u vv

r u vv

r u v


13 1 3

14 1 4

22 2 2

20 20 0 18 2

20 20 0 23 3

20 20 3 10 13

r u v

r u v

r u v




Luego, la solución encontrada no es óptima, porque existe un costo reducido negativo fuera de la base.

Respuesta suponiendo los costos ficticios iguales a 0:

La solución inicial es:


Corea del Sur

15

30 10

30 20

- 0

- 60

Brasil 12

- 20

5 15

20 0

10 35

Dj 30 35 20 10


Luego, para la primera iteración, tenemos que, para estas 5 variables, el costo reducido es igual a cero, por lo tanto:

11 1 1

1 1

12 1 2

2 2

22 2 2

3

23 2 3

4

24 2 4

0

15 00 15

10 010 10

20 05

15 010

0 0

ij ij i jr c u v

r u vu v

r u vu v

r u vv

r u vv

r u v


13 1 3

14 1 4

21 2 1

20 20 0 5 15

0 0 0 10 10

12 12 10 15 13

r u v

r u v

r u v

Como hay una variable con costo reducido negativo debe entrar esta variable a la base. Así, tenemos que:


Corea del Sur

15

30 (-) 10

30 (+) 20

- 0

- 60

Brasil 12

- (+) 20

5 (-) 15

20 0

10 35

Dj 30 35 20 10




Claramente se observa que, de las variables que bajan, la primera que llega a cero es X22, luego sale de la base. Así, la nueva solución es:


Corea del Sur

15

25 10

35 20

- 0

- 60

Brasil 12

5 20

- 15

20 0

10 35

Dj 30 35 20 10


Luego, para la esta solución, tenemos que, para estas 5 variables, el costo reducido es igual a cero, por lo tanto:

11 1 1

1 1

12 1 2

2 2

21 2 1

3

23 2 3

4

24 2 4

0

15 00 15

10 03 10

12 018

15 03

0 0

ij ij i jr c u v

r u vu v

r u vu v

r u vv

r u vv

r u v


13 1 3

14 1 4

22 2 2

20 20 0 18 2

0 0 0 3 3

20 20 3 10 13

r u v

r u v

r u v




Luego, la solución encontrada no es óptima, porque existe un costo reducido negativo fuera de la base.

OJO FALTA REALIZAR OTRA ITERACION HASTA QUE LOS COSTOS

REDUCIDOS SEAN TODOS POSITIVOS, EN ESE CASO SE DICE QUE ESTAMOS EN EL ÓPTIMO, AUN NO ENCONTRAMOS LA SOLUCION OPTIMA

2.-

Respuesta:

a. Se abre la menos negativa (si hay empate se escoge una en forma arbitraria), y las demás permanecen pendientes.

b. Se deben abrir todas las positivas. La con MINSAVE cero puede abrirse o permanecer pendiente, pero dado que el ahorro mínimo asegurado es cero, resulta razonable abrirla para que haya menos iteraciones. Las de MINSAVE negativo permanecen pendientes.

c. Se cierran todas las con MAXSAVE negativo. La otra se puede abrir o cerrar, da lo mismo porque el costo total será el mismo.

d. Se debe abrir la de mayor MAXSAVE. La de MAXSAVE cero se puede dejar pendiente o cerrar, pero como su ahorro máximo es cero, podemos cerrarla inmediatamente sabiendo que no se pierde nada. Las demás plantas permanecen pendientes.

e. Se debe abrir la de mayor MAXSAVE. La de MAXSAVE cero se puede dejar pendiente o cerrar, pero como su ahorro máximo es cero, podemos cerrarla inmediatamente sabiendo que no se pierde nada. Las plantas con MAXSAVE negativo se cierran. Las plantas positivas que no se abrieron permanecen pendientes.

⋯⋯Material y ayudantías: jpontigo.ublog.cl o a través de e-learning || Correo: [email protected]⋯⋯

http://jpontigo.ublog.cl/

Documents

PAUTAAyu PTransporte JP