Modelosdetransporte 110919193810-phpapp01

Modelos de Transporte: Modelos de Transporte: método de la esquina método de la esquina

noroestenoroeste

M. En C. Eduardo Bustos FaríasM. En C. Eduardo Bustos Farías

2

Problemas de transporteProblemas de transporte

Surge cuando se necesita un modelo costo-efectividad Surge cuando se necesita un modelo costo-efectividad que permita transportar ciertos bienes desde un lugar que permita transportar ciertos bienes desde un lugar de origen a un destino que necesita aquellos bienes , de origen a un destino que necesita aquellos bienes , con ciertas restricciones en la cantidad que se puede con ciertas restricciones en la cantidad que se puede transportar.transportar.

Se presenta al planear la distribución de bienes y Se presenta al planear la distribución de bienes y servicios desde varias localizaciones de suministro servicios desde varias localizaciones de suministro hacia varias ubicaciones de la demanda.hacia varias ubicaciones de la demanda.

La cantidad de los bienes disponibles en cada La cantidad de los bienes disponibles en cada localización de su ministro (origen) es limitada, y la localización de su ministro (origen) es limitada, y la cantidad de los bienes necesarios en cada una de las cantidad de los bienes necesarios en cada una de las localizaciones de demanda (destino) es conocida.localizaciones de demanda (destino) es conocida.

El objetivo es minimizar el costo de embarcar los bienes El objetivo es minimizar el costo de embarcar los bienes desde los orígenes hasta los destinos.desde los orígenes hasta los destinos.

3

� Dentro de la amplia gama de problemas de Dentro de la amplia gama de problemas de programación lineal se encuentran los problemas de programación lineal se encuentran los problemas de transporte, los cuales poseen características transporte, los cuales poseen características particulares. particulares.

� En este caso específico de problemas, es necesario En este caso específico de problemas, es necesario determinar la ruta más eficiente para hacer llegar determinar la ruta más eficiente para hacer llegar productos o materiales desde puntos alternativos de productos o materiales desde puntos alternativos de origen hasta diferentes puntos de destino, origen hasta diferentes puntos de destino, cumpliendo las restricciones específicas de oferta y cumpliendo las restricciones específicas de oferta y demanda y con base en la estructura de costos de demanda y con base en la estructura de costos de las rutas de transporte.las rutas de transporte.

� Las diversas técnicas para abordar el problema de Las diversas técnicas para abordar el problema de transporte requieren de una tabla de transporte, transporte requieren de una tabla de transporte, dicha tabla en su forma estándar registra todos los dicha tabla en su forma estándar registra todos los elementos esenciales del problema de transporte elementos esenciales del problema de transporte que estamos solucionando: costos de transporte; que estamos solucionando: costos de transporte; puntos de origen y destino, cantidades de oferta y puntos de origen y destino, cantidades de oferta y demanda; tal y como se muestra a continuación:demanda; tal y como se muestra a continuación:

4En la tabla anterior la demanda (33) es igual a la oferta (33), lo cual significa que el problema está balanceado y ello facilita la búsqueda de la solución.

5

� Definición del problemaDefinición del problema

* Se tienen m lugares de origen. Cada lugar de origen tiene * Se tienen m lugares de origen. Cada lugar de origen tiene una capacidad de producción Suna capacidad de producción S ii

*Se tienen n destinos. Cada destino j demanda D*Se tienen n destinos. Cada destino j demanda D jj

*Objetivo:*Objetivo:

Minimizar el costo de transporte de la carga al lugar de destino Minimizar el costo de transporte de la carga al lugar de destino cumpliendo con las restricciones de los lugares de origen.cumpliendo con las restricciones de los lugares de origen.

6

Caso I. Caso I. Oferta igual a demandaOferta igual a demanda

7

EJEMPLO 1EJEMPLO 1

Farmacéutica CarltonFarmacéutica CarltonProblema de transporteProblema de transporte

8

Farmacéutica CarltonFarmacéutica Carlton

� La farmacéutica Carlton abastece de medicamentos La farmacéutica Carlton abastece de medicamentos y otros suministros médicos.y otros suministros médicos.

� Esta tiene tres plantas en: Claveland, Detroit, Esta tiene tres plantas en: Claveland, Detroit, Greensboro.Greensboro.

� Tiene cuatro centros de distribución en: Boston, Tiene cuatro centros de distribución en: Boston, Atlanta, St Louis y Richmond.Atlanta, St Louis y Richmond.

� La gerencia de Carlton desea realizar el transporte La gerencia de Carlton desea realizar el transporte de sus productos de la manera más económica de sus productos de la manera más económica posible.posible.

9

� DatosDatos

Costo de transporte por unidad, oferta y demanda.Costo de transporte por unidad, oferta y demanda.

� SupuestosSupuestos

* El costo de transporte por unidad es constante* El costo de transporte por unidad es constante* Todos los transportes ocurren simultáneamente.* Todos los transportes ocurren simultáneamente.* Solo se considera el costo de transporte entre el lugar de * Solo se considera el costo de transporte entre el lugar de origen y el de destinoorigen y el de destino* La oferta total es igual a la demanda total.* La oferta total es igual a la demanda total.

HaciaDesde Boston Richmond Atlanta St. Louis Oferta Cleveland $35 30 40 32 1200 Detroit 37 40 42 25 1000 Greensboro 40 15 20 28 800Demanda 1100 400 750 750

10

SOLUCIÓNSOLUCIÓN

11

RED QUE RED QUE REPRESENTAREPRESENTA

EL PROBLEMAEL PROBLEMA Boston

Richmond

Atlanta

St.Louis

Destinos

Origenes

Cleveland

Detroit

Greensboro

S1=1200

S2=1000

S3= 800

D1=1100

D2=400

D3=750

D4=750

37

40

42

32

35

40

30

25

3515

20

28

12

� Modelo matemáticoModelo matemático* La estructura del modelo es la siguiente:* La estructura del modelo es la siguiente:

Minimizar <Costo total de transporte>Minimizar <Costo total de transporte>sujeto a :sujeto a :

cantidad a transportar desde la fabrica = oferta de la fábricacantidad a transportar desde la fabrica = oferta de la fábricacantidad a recibir por la distribuidora = demanda de la cantidad a recibir por la distribuidora = demanda de la distribuidora.distribuidora.

* Variables de decisión:* Variables de decisión:

XX i j i j = cantidad a transportar desde la fábrica i a la = cantidad a transportar desde la fábrica i a la distribuidora jdistribuidora jdonde i = 1(Claveland), 2(Detroit), 3(Greensboro)donde i = 1(Claveland), 2(Detroit), 3(Greensboro)

j = 1(Boston), 2(Richmond), 3(Atlanta), 4 (St,Louis)j = 1(Boston), 2(Richmond), 3(Atlanta), 4 (St,Louis)

13

Boston

Richmond

Atlanta

St.Louis

D1=1100

D2=400

D3=750

D4=750

Restricciones de la Oferta

Cleveland S1=1200

X11

X12

X13

X14

Oferta de Cleveland X11+X12+X13+X14 = 1200

Detroit

S2=1000

X21

X22

X23

X24

Oferta de Detroit X21+X22+X23+X24 = 1000

GreensboroS3= 800

X31

X32

X33

X34

Oferta de Greensboro X31+X32+X33+X34 = 800

14

� El modelo matemático completoEl modelo matemático completo

Restriccione de la oferta:X11+ X12+ X13+ X14 1200

X21+ X22+ X23+ X24 1000X31+ X32+ X33+ X34 800

Restricciones de la demanda:X11+ X21+ X31 1000

X12+ X22+ X32 400X13+ X23+ X33 750

X14+ X24+ X34 750

Todos los Xij mayores que cero

===

====

15

� Solución optima obtenida a través de ExcelSolución optima obtenida a través de Excel

FARMACUETICA CARLTON

COSTOS UNITARIOSBOSTON RICHMOND ATLANTA ST.LOUIS OFERTAS

CLEVELAND 35,00$ 30,00$ 40,00$ 32,00$ 1200DETROIT 37,00$ 40,00$ 42,00$ 25,00$ 1000GREENSBORO 40,00$ 15,00$ 20,00$ 28,00$ 800

DEMANDAS 1100 400 750 750

ALTERNATIVAS DE TRANSPORTEBOSTON RICHMOND ATLANTA ST.LOUIS TOTAL

CLEVELAND 850 350 0 0 1200DETROIT 250 0 0 750 1000GREENSBORO 0 50 750 0 800

TOTAL 1100 400 750 750 COSTO TOTAL = 84000

16Rango Optim

o

Análisis de Sensibilidad por WINQSBAnálisis de Sensibilidad por WINQSB

Si utilizamos esta ruta, el costo total aumentara en $5 por unidad transportada.

17

Rango de factibilidad

Precio sombra de la distribuidora - el costo de mandar una unidad más por la distribuidora.

Precio sombra de la planta - el costo de cada unidad extra disponible en la planta.

18

� Interpretación de los resultados del Interpretación de los resultados del análisis de sensibilidad.análisis de sensibilidad.

* Reducción de Costos: * Reducción de Costos: - La cantidad a transportar que reduce - La cantidad a transportar que reduce

el costo por unidad el costo por unidad entrega la ruta más entrega la ruta más económicamente atractiva.económicamente atractiva.

- Si una ruta debe usarse - Si una ruta debe usarse obligatoriamente, incurriendo asíobligatoriamente, incurriendo así en en el costo que ello significa, por cada carga el costo que ello significa, por cada carga transportada , transportada , el costo total aumentara en el costo total aumentara en una cantidad igual a la una cantidad igual a la reducción reducción del costo hecha.del costo hecha.

19

* Precios Sombra:* Precios Sombra:- Para las plantas el precio sombra de - Para las plantas el precio sombra de

transporte transporte corresponde al costo de corresponde al costo de cada unidad disponible en la cada unidad disponible en la planta.planta.

- Para las distribuidoras, el precio sombra - Para las distribuidoras, el precio sombra de transporte de transporte corresponde al costo de corresponde al costo de cada unidad extra demandada por cada unidad extra demandada por la la distribuidora.distribuidora.

20

LA REGLA DE LA ESQUINA LA REGLA DE LA ESQUINA NOROESTE NOROESTE

21

Esta regla nos permite encontrar una Esta regla nos permite encontrar una solución factible básica inicial solución factible básica inicial (SFBI), una vez que tengamos el (SFBI), una vez que tengamos el problema de transporte problema de transporte “balanceado” o equilibrado, es “balanceado” o equilibrado, es decir que el total de ofertas iguales decir que el total de ofertas iguales al total de demandas.al total de demandas.

22

PROCEDIMIENTOPROCEDIMIENTO� Iniciar la asignación en el renglón 1 y Iniciar la asignación en el renglón 1 y

columna 1 (esquina noroeste) y formar una columna 1 (esquina noroeste) y formar una base asignando cantidades a las rutas, de base asignando cantidades a las rutas, de forma tal que se agoten las existencias de la forma tal que se agoten las existencias de la fabrica y se satisfaga la demanda de los fabrica y se satisfaga la demanda de los mercados. mercados.

� Así entonces, la asignación inicia en la casilla Así entonces, la asignación inicia en la casilla X11 (esquina noroeste) y si lo fábrica 1 no X11 (esquina noroeste) y si lo fábrica 1 no agotó su oferta continuara en la casilla X12 y agotó su oferta continuara en la casilla X12 y así sucesivamente. así sucesivamente.

23

� En el caso de que el total de la oferta En el caso de que el total de la oferta de la fabrica 1 no haya sido suficiente de la fabrica 1 no haya sido suficiente para cubrir la demanda del mercado 1, para cubrir la demanda del mercado 1, completar con la oferta de la fabrica 2, completar con la oferta de la fabrica 2, que es la casilla X21 y si no se agotó la que es la casilla X21 y si no se agotó la oferta pasar a la casilla X22 y así oferta pasar a la casilla X22 y así continuar hasta concluir el proceso de continuar hasta concluir el proceso de asignación.asignación.

24

Con la forma anterior se conseguirá la Con la forma anterior se conseguirá la siguiente solución básica factible inicial:siguiente solución básica factible inicial:

x11 15

x12 15

x13 x14 30

x21 x22 5

x23 31

x24 9

45

x31 x32 x33 x34 50

50

x41 x42 x43 x44 25

25

15 20 31 84

25

Supuestos del método:Supuestos del método:1.1. Asignamos lo más que podamos a la Asignamos lo más que podamos a la

variable x11 que ocupa la posición noroeste variable x11 que ocupa la posición noroeste de la tabla.de la tabla.

2.2. La oferta es igual a la demanda.La oferta es igual a la demanda.3.3. El proceso de asignar a la variable el El proceso de asignar a la variable el

mínimo valor entre oferta y demanda mínimo valor entre oferta y demanda disponibles se repite hasta que toda la disponibles se repite hasta que toda la oferta y demanda totales sean satisfechas.oferta y demanda totales sean satisfechas.

4.4. Genera una solución factible básica inicial.Genera una solución factible básica inicial.5.5. Las celdas en blanco corresponden a Las celdas en blanco corresponden a

variables no básicas y sus valores son cero.variables no básicas y sus valores son cero.6.6. Se obtienen variables básicas en las celdas Se obtienen variables básicas en las celdas

con asignación.con asignación.

26

EJEMPLO 1EJEMPLO 1

27

x11 x12 x13 x14 30

x21 x22 x23 x24 45

x31 x32 x33 x34 50

x41 x42 x43 x44 25

15 20 31 84

Encontrar la ruta de costo mínimo para el Encontrar la ruta de costo mínimo para el siguiente problema de transporte, usando el siguiente problema de transporte, usando el método de la esquina noroeste.método de la esquina noroeste.

28

X11

15

x12 x13 x14 30 15

x21 x22 x23 x24 45

x31 x32 x33 x34 50

x41 x42 x43 x44 25

150

20 31 84

29

X11

15

X12

15

x13 x14 30 15 0

x21 x22 x23 x24 45

x31 x32 x33 x34 50

x41 x42 x43 x44 25

150

205

31 84

30

X11

15

X12

15

x13 x14 30 15 0

x21 X22

5

x23 x24 45 40

x31 x32 x33 x34 50

x41 x42 x43 x44 25

150

2050

31 84

31

X11

15

X12

15

x13 x14 30 15 0

x21 X22

5

X23

31

X24 45 40 9

x31 x32 x33 x34 50

x41 x42 x43 x44 25

150

2050

310

84

32

X11

15

X12

15

x13 x14 30 15 0

x21 X22

5

X23

31

X24

9

45 40 9 0

x31 x32 x33 x34 50

x41 x42 x43 x44 25

150

2050

310

8475

33

X11

15

X12

15

x13 x14 30 15 0

x21 X22

5

X23

31

X24

9

45 40 9 0

x31 x32 x33 X34

50

50 0

x41 x42 x43 x44 25

150

2050

310

847525

34

X11

15

X12

15

x13 x14 30 15 0

x21 X22

5

X23

31

X24

9

45 40 9 0

x31 x32 x33 X34

50

50 0

x41 x42 x43 X44

25

25 0

150

2050

310

8475250

35

EJEMPLO 2EJEMPLO 2

37

SOLUCIÓNSOLUCIÓN

39

U

=+1-5+2-4=-6

Modelos de Transporte: Modelos de Transporte: método de costo mínimo método de costo mínimo

y de Vogely de Vogel


45

Método de costo mínimoMétodo de costo mínimo

46

Métodos de Costo Métodos de Costo mínimo:mínimo:

– de la matrizde la matriz– por columnapor columna– por fi lapor fi la

47

� Costo mínimo de la matrizCosto mínimo de la matriz : Consiste : Consiste en seleccionar en cada etapa aquella en seleccionar en cada etapa aquella variable xij cuyo costo Cij sea el variable xij cuyo costo Cij sea el mínimo para todos los i, j .mínimo para todos los i, j .

� Costo mínimo por columnaCosto mínimo por columna : : Comenzando con la columna de la Comenzando con la columna de la izquierda, seleccionamos aquella izquierda, seleccionamos aquella variable de menor costo.variable de menor costo.

� Costo mínimo por f i laCosto mínimo por f i la : Comenzando : Comenzando por la primera fi la, seleccionamos xi j por la primera fi la, seleccionamos xi j como la variable correspondiente que como la variable correspondiente que tenga menor costo.tenga menor costo.

48

� Este es un procedimiento que aventaja a la Este es un procedimiento que aventaja a la regla de la esquina noroeste en la búsqueda regla de la esquina noroeste en la búsqueda de la solución óptima. de la solución óptima.

� Aquí emplearemos la misma técnica básica Aquí emplearemos la misma técnica básica de agotar alternativamente ya sea la oferta de agotar alternativamente ya sea la oferta de las fábricas o la demanda de los de las fábricas o la demanda de los mercados, pero modifica el requisito de mercados, pero modifica el requisito de proceder geográficamente desde la esquina proceder geográficamente desde la esquina superior izquierda. superior izquierda.

� En lugar de lo anterior, la asignación En lugar de lo anterior, la asignación corresponde a la casilla de menor costo de la corresponde a la casilla de menor costo de la tabla de transporte. tabla de transporte.

49

� Si esta asignación satisface el requisito de Si esta asignación satisface el requisito de demanda de un mercado, se sigue adelante demanda de un mercado, se sigue adelante con el costo más bajo siguiente en el mismo con el costo más bajo siguiente en el mismo renglón y agotando, de ser posible, las renglón y agotando, de ser posible, las existencias de la fabrica en cuestión.existencias de la fabrica en cuestión.

� El procedimiento agota de la misma manera El procedimiento agota de la misma manera la oferta de las fábricas y la demanda de los la oferta de las fábricas y la demanda de los mercados, inspeccionando siempre los mercados, inspeccionando siempre los costos a fin de encontrar la casilla siguiente costos a fin de encontrar la casilla siguiente para una asignación en el renglón o la para una asignación en el renglón o la columna de que se trata.columna de que se trata.

50

EJEMPLO 1EJEMPLO 1

Método de costo mínimoMétodo de costo mínimo

51Se resolverá la siguiente tabla de transporte por los 3 métodos de costo

52

Costo mínimo de la Costo mínimo de la matrizmatriz

53

2500 0

3500

54

2500 0

3500

2000 4000

0

55

2500 0

3500

2000 4000

0

4000

0

1000

56

2500 0

35002500

2000 4000

0

4000

0

1000 0

1000

57

2500 0

35002500

2000 40002500

0

4000

0

1000 0

1000

1500

0

58

2500 0

35002500 0

2000 40002500 0

0

4000

0

1000 0

1000

1500

0

2500

59

Costo mínimo por f i laCosto mínimo por f i la

60

4000

0

1000

61

2000

4000

0

1000

0

4000

62

2000

4000

0

1000

0

4000

2500 0

3500

63

2000

4000

0

10000

0

4000

2500 0

35002500

1000

64

2000

4000

0

10000

0

40002500

2500 0

35002500

1000

1500

0

65

2000

4000

0

10000

0

40002500

0

2500 0

35002500

0

1000

1500

0

2500

66

Costo mínimo por Costo mínimo por columnacolumna

67

2500 0

3500

68

2500 0

3500

4000

0

1000

69

2500 0

3500

4000

0

1000

2000 4000

0

70

2500 0

3500

4000

0

1000

2000 40002500

0

1500

0

71

2500 0

35002500

4000

0

10000

2000 40002500

0

1500

0

1000

72

2500 0

35002500

0

4000

0

10000

2000 40002500

0

0

1500

0

1000

2500

Modelos de Transporte: Modelos de Transporte: Problemas de asignaciónProblemas de asignación


74

EJEMPLO 1EJEMPLO 1

El profesor MichellEl profesor MichellProblema de asignaciónProblema de asignación

75

Solución mediante el método Solución mediante el método HúngaroHúngaro

� Problema:Problema:El profesor Michell ha terminado 4 capítulos de su libro y esta El profesor Michell ha terminado 4 capítulos de su libro y esta pensando en pedir ayuda para terminarlo. El ha elegido a 4 pensando en pedir ayuda para terminarlo. El ha elegido a 4 secretarias que podrían tipearle cada uno de sus capítulos. El secretarias que podrían tipearle cada uno de sus capítulos. El costo asociado refleja la velocidad de la secretaria y la costo asociado refleja la velocidad de la secretaria y la exactitud con la que realiza el trabajo. Además los capítulo exactitud con la que realiza el trabajo. Además los capítulo difieren en la cantidad de hojas y en la complejidad. ¿Qué difieren en la cantidad de hojas y en la complejidad. ¿Qué puede hacer el profesor si conoce la siguiente tabla:puede hacer el profesor si conoce la siguiente tabla:

CapítulosCapítulosSecretaría 13 14 15 16Secretaría 13 14 15 16JuanaJuana 96 99 105 108 96 99 105 108MaríaMaría 116 116 109 107 96 109 107 96JackelineJackeline 120 102 113 111 120 102 113 111

EdithEdith 114 114 105 118 115 105 118 115

76

� Restricciones del MétodoRestricciones del Método

* Solo problemas de minimización.* Solo problemas de minimización.* Número de personas a asignar m es igual al número de * Número de personas a asignar m es igual al número de lugares m.lugares m.* Todas las asignaciones son posibles* Todas las asignaciones son posibles* Una asignación por persona y una persona por asignación* Una asignación por persona y una persona por asignación

� Matriz de CostosMatriz de CostosCapítulosCapítulos

Secretaría 13 14 15 16Secretaría 13 14 15 16JuanaJuana 96 99 105 108 96 99 105 108MaríaMaría 116 116 109 107 96 109 107 96JackelineJackeline 120 102 113 111 120 102 113 111

EdithEdith 114 114 105 118 115 105 118 115

77

� Restar el Menor valor de cada filaRestar el Menor valor de cada filaCapítulosCapítulos


EdithEdith 9 9 0 13 10 0 13 10� Restar el menor valor de cada columna en la matriz Restar el menor valor de cada columna en la matriz

anterioranteriorCapítulosCapítulos


EdithEdith 9 9 0 4 10 0 4 10

78

� Trazar el mínimo número de líneas que cubran los Trazar el mínimo número de líneas que cubran los ceros de la matriz obtenida en el punto anterior.ceros de la matriz obtenida en el punto anterior.


EdithEdith 9 9 0 4 10 0 4 10

� Si el número de líneas es igual al número de filas se Si el número de líneas es igual al número de filas se esta en la solución óptima, sino identificar el menor esta en la solución óptima, sino identificar el menor valor no rayado restarselo a los demás números no valor no rayado restarselo a los demás números no rayados y sumarlo en las intersecciones.rayados y sumarlo en las intersecciones.

Para este caso corresponde al valor 2Para este caso corresponde al valor 2

79


EdithEdith 7 7 0 2 10 0 2 10

� Se obtuvo la asignación óptima.Se obtuvo la asignación óptima.� Las asignaciones corresponde a los valores donde Las asignaciones corresponde a los valores donde

existen 0existen 0Juana Cap. 13Juana Cap. 13María Cap. 16María Cap. 16Jackeline Cap. 15Jackeline Cap. 15Edith Cap. 14Edith Cap. 14

*Costo Asignación: 96 + 96 +113 +105 =410*Costo Asignación: 96 + 96 +113 +105 =410

Modelosdetransporte 110919193810-phpapp01

Engineering

Transcript of Modelosdetransporte 110919193810-phpapp01