• Author / Uploaded
• Angie Horna Fernandez

• Categories
• Procter & Gamble
• Transporte
• Ciencias económicas
• Economias
• Business

Citation preview

13/09/2017

Unidad 2 Programación multiobjetivo y modelos de transporte

Ing. Enrique M. Avendaño Delgado [email protected]

DEFINICIÓN: •

•

El Problema de Transporte corresponde a un tipo particular de un problema de programación lineal. Si bien este tipo de problema puede ser resuelto por el método Simplex, existe un algoritmo simplificado especial para resolverlo. El modelo de transporte se define como una técnica que determina un programa de transporte de productos o mercancías desde unas fuentes hasta los diferentes destinos al menor costo posible. Fuentes: i

a1

Destinos j

xij

: cij

1

b1

1

Unidades de Demanda

Unidades de Oferta

a2

2

2

b2

am

m

n

bn

xmn : cmn

1

13/09/2017

PROCTER & GAMBLE (P & G) Procter & Gamble (P & G) produce y comercializa más de 300 marcas de productos a nivel mundial. Esta compañía ha crecido continuamente a través de su larga historia que data desde 1830. Para mantener y acelerar ese crecimiento, un importante estudio de IO se realizó para fortalecer la efectividad global de P & G. Antes del estudio, la cadena de suministro de la compañía consistía en cientos de proveedores para las 50 categorías de productos en 60 plantas, 15 centros de distribución y más de 1 000 zonas de consumo. Sin embargo, en la medida en que la compañía consideró marcas globales, la administración se percató de que se requería consolidar las plantas a fi n de reducir los gastos de manufactura, mejorar la velocidad de entrega al mercado y reducir la inversión de capital. Por lo cual, el estudio se enfocó al rediseño del sistema de producción y distribución de la compañía para sus operaciones en Norteamérica. El resultado fue una reducción del número de plantas en Norteamérica de casi 20 por ciento, ahorrando más de 200 millones de dólares en costos antes de impuestos por año. Gran parte del estudio consistió en la formulación y solución de problemas de transporte de categorías individuales de producto. Para cada opción referente a mantener abiertas ciertas plantas, la solución del correspondiente problema de transporte para cierta categoría de producto mostró cuál sería el costo de distribución para enviar dicha categoría de producto desde esas plantas hacia los centros de distribución y zonas de consumo.

EJEMPLO

Uno de los productos más importantes de la P & T COMPANY es el chícharo enlatado. Los chícharos se preparan en tres enlatadoras —cercanas a Bellingham, Washington; Eugene, Oregon, y Albert Lea, Minnesota— y después se envían por camión a cuatro almacenes de distribución —Sacramento, California; Salt Lake City, Utah; Rapid City, South Dakota, y Albuquerque, Nuevo México— en el oeste de Estados Unidos, como se muestra en la figura 1. Debido a que los costos de embarque constituyen un gasto importante, la administración ha iniciado un estudio para reducirlos a su mínima expresión. Se ha estimado la producción de cada enlatadora durante la próxima temporada y se ha asignado a cada almacén cierta cantidad de la producción total de chícharos. En la tabla 2 se proporciona esta información —en unidades de carga de camión—, junto con el costo de transporte por camión cargado de cada combinación de enlatadora-almacén. Como se ve, hay un total de 300 cargas de camión que se deben transportar. El problema es determinar el plan de asignación de estos embarques a las distintas combinaciones de enlatadora-almacén que minimice el costo total de transporte. Costo de embarque ($) por carga Almacén 1

2

3

4

Producción

1

464

513

654

867

75

Enlatadora 2

352

416

690

791

125

3

995

682

388

685

100

80

65

70

85

Asignación

2

13/09/2017

EJEMPLO

EJEMPLO

3

13/09/2017

MODELO DEL PROBLEMA DE TRANSPORTE Para describir el modelo general del problema de transporte es necesario emplear términos mucho menos específicos que los que se usaron para designar los componentes del ejemplo prototípico. En particular, el problema general de transporte se refiere —en sentido literal o figurado— a la distribución de cualquier mercancía desde cualquier grupo de centros de suministro, llamados orígenes, a cualquier grupo de centros de recepción, llamados destinos, de tal manera que se minimicen los costos totales de distribución.

MÉTODOS DE SOLUCIÓN: Los métodos más empleados para obtener soluciones iniciales son:

• El método de la Esquina Noroeste. • El método del Costo Mínimo. • El Método Vogel.

4

13/09/2017

METODO ESQUINA NOROESTE

MÉTODO NOROESTE Para encontrar una solución inicial se comienza por la esquina superior izquierda (noroeste) del tablea de transporte intentando asignar la máxima cantidad posible a x11. Evidentemente, el valor máximo de x11 debe ser el menor entre s1 y d1. Si x11 = s1, se puede descartar la primera fila, pues ya no podría asignarse más desde el primer punto de oferta, se avanza a la siguiente fila. Al mismo tiempo, se debe cambiar d1 por d1-s1, de forma de indicar la cantidad de demanda no satisfecha en el primer punto de demanda. En caso que x11 = d1, se debe descartar la primera columna y cambiar s1 por s1-d1, avanzando una columna. Si x11 = d1 = s1, se debe avanzar en una columna o en una fila (pero no en ambas). Se asigna un cero en la dirección escogida y se descarta la otra alternativa. • El método continua aplicando el mismo criterio desde la esquina noroeste del tablero restante. Una vez que están asignadas toda de demanda y oferta disponible, se terminan las asignaciones y está completa la asignación inicial.

5

13/09/2017

Método Noroeste

Costo Total: 75*464 + 5*352 + 65*416 + 55*690 + 15*388 + 85*685

Costo Total: 165595

METODO DEL COSTO MINIMO

6

13/09/2017

COSTO MÍNIMO: Características: • • •

Es más elaborado que el método de la esquina noroeste Tiene en cuenta los costos para hacer las asignaciones Generalmente nos deja alejados del óptimo

Pasos:

1. Construya una tabla de disponibilidades, requerimientos y costos 2. Empiece en la casilla que tenga el menor costo de toda la tabla, si hay empate, escoja arbitrariamente (Cualquiera de los empatados). 3. Asigne lo máximo posible entre la disponibilidad y el requerimiento (El menor de los dos). 4. Rellene con ceros (0) la fila o columna satisfecha y actualice la disponibilidad y el requerimiento, restándoles lo asignado. Nota: Recuerde que no debe eliminar ó satisfacer fila y columna al mismo tiempo, caso en que la oferta sea igual a la demanda, en tal caso recuerde usar la ε (Epsilon). 5. Muévase a la casilla con el costo mínimo de la tabla resultante (Sin tener en cuenta la fila o columna satisfecha). 6. Regrese a los puntos 3,4,5 sucesivamente, hasta que todas las casillas queden asignadas.

Costo mínimo:

Costo Total: 80*352 + 20*513 + 45*682 + 70*388 + 55*867 + 30*685

Costo Total: 152535

7

13/09/2017

METODO VOGEL

MÉTODO VOGEL: El método comienza calculando por cada columna y por cada fila el castigo o penalidad. El castigo se calcula como la diferencia entre los dos costos menores en la columna o en la fila según corresponda. A continuación, se determina la fila o columna con un mayor valor de castigo. Luego, se selecciona como variable basal la celda con menor costo de la fila o columna, según corresponda, y se le asigna la máxima cantidad posible. Una vez realizada la asignación, se descarta la fila o columna cuya oferta o demanda haya sido completa. Se recalcula la demanda u oferta disponible en la fila o columna. La primera asignación se ha completado. Se vuelven a calcular los castigos por fila y por columna y se repite el procedimiento descrito hasta completar las asignaciones posibles en el tablero. La ventaja del método de Vogel por sobre el de la Esquina Noroeste es que va adelante algunas iteraciones y por lo tanto se obtiene una solución inicial mejor. Eventualmente puede ocurrir que aplicando el método se llegue directamente a la solución óptima.

8

13/09/2017

Método Vogel

Método Vogel

9

13/09/2017

Método Vogel

Método Vogel

10

13/09/2017

Método Vogel

PROBLEMAS Material: •Papel •Lapicero •Calculadora

11

13/09/2017

EJERCICIO 1: • •

La compañía Deltron produce su producto líder en tres fábricas diferentes, los cuales se envían en lote a cuatro bodegas de distribución las cuales se encargan de su venta. La producción por fábrica en lotes es la siguiente La capacidad de cada bodega en lotes es la siguiente

•

Fábrica

Producción

Bodega

Capacidad

1

200

1

120

2

125

2

250

3

300

3

150

Total

625

4

105

Total

625

Resolverlo utilizando los tres métodos: 1. El método de la Esquina Noroeste. 2. El método del Costo Mínimo. 3. El Método Vogel

•

Los costos asociados a enviar un lote de productos desde las diferentes fabricas a las bodegas, es el siguiente:

Fábrica

Bodega 1

Bodega 2

Bodega 3

Bodega 4

1

$ 664

$ 613

$ 290

$ 867

2

$ 452

$ 316

$ 690

$ 391

3

$ 795

$ 682

$ 488

$ 685

EJERCICIO 2: •

Una aerolínea regional puede comprar su combustible para jet a cualquiera de tres proveedores. Las necesidades de la aerolínea para el próximo mes, en cada uno de los tres aeropuertos a los que da servicio, son 200 galones en el aeropuerto 1. 230 en el aeropuerto 2, y 350 galones en el aeropuerto 3. Cada proveedor puede suministrar combustible a cada aeropuerto a los precios que se dan en el siguiente cuadro:

Cada proveedor, sin embargo, tiene limitaciones en cuanto al número total de galones que puede proporcionar durante un mes dado. Estas capacidades son 320 para el proveedor 1. 270 galones para el proveedor 2 y 190 para el proveedor 3. Determine una política de compra que cubra los requerimientos de la aerolínea en cada

Aeropuerto 1

Aeropuerto 2

Aeropuerto 3

Proveedor 1

92

89

90

Proveedor 2

91

91

95

Proveedor 3

87

90

92

aeropuerto, a un costo mínimo. Cual es el costo de esa política de compra. • Resolverlo utilizando el método de Vogel

12

13/09/2017

EJERCICIO 3: El gobierno de Estados Unidos está subastando contratos de arrendamientos de petróleo en dos sitios 1 y 2. En cada sitio, se subastan 100 000 acres de tierra. Cliff Erwing, Blake Barnes y Alexis Pickens llevan a cabo licitaciones para el petróleo. Las reglas del gobierno establecen que ningún licitador puede recibir más de 40% de la tierra que esta siendo subastada. Cliff oferto $ 1 000/acre para el suelo del sitio 1 y $ 2 000/acre para el suelo del sitio 2. Blake ofreció $ 900/acre para el suelo del sitio 1 y $2 200/acre para el suelo del sitio 2. Alexis ofertó $1 100/acre para el sitio 1 y $ 1 900/acre para el sitio 2. Formule un modelo de transporte equilibrado para maximizar el ingreso del gobierno.

EJERCICIO 4 La Compañía Childfair tiene tres plantas de producción de carros para bebés que deben distribuirse a cuatro centros de distribución. Las plantas 1, 2 y 3 producen 34, 25 y 11 cargamentos por mes, respectivamente. Cada centro de distribución necesita recibir : Centro1, 15 cargamentos por mes, Centro2, 20 cargamentos por mes; Centro3, 15 cargamentos por mes y la diferencia para el centro4. En la siguiente tabla se da la distancia de cada planta a su respectivo centro de distribución:

El costo del flete de cada embarque es de $100 más 0.50 centavos por milla. ¿Cuánto se debería embarcar a cada centro de distribución para minimizar el costo total del envío?

Distancia (millas) Centro de distribución

Planta

1

2

3

4

1

800

1300

400

700

2

1100

1400

600

1000

3

600

1200

800

900

a) Formule el problema como uno de transporte mediante la elaboración de una tabla de parámetros apropiada. b) Utilice vogel para una asignación inicial

13

13/09/2017

Unidad 2 Programación multiobjetivo y modelos de transporte

Ing. Enrique M. Avendaño Delgado [email protected]

INTRODUCCIÓN:

•

•

Dentro de los modelos de Transportes, por lo general nos encontramos ante la disyuntiva de que el tablero no esta equilibrado, eso significa que tanto las ofertas como las demandas no son iguales. Existe dos situaciones, que la Demanda sea mayor que la Oferta ó que la Oferta sea mayor que la Demanda.

14

13/09/2017

COMO EQUILIBRAR UN PROBLEMA DE TRANSPORTE LA OFERTA TOTAL EXCEDE A LA DEMANDA •

Si la Oferta total excede a la Demanda total, un problema de transporte se equilibra creando un punto de demanda ficticio que tiene una demanda igual a la cantidad de suministro en exceso. Debido a que los envíos al punto de demanda ficticio no son envíos reales, se les asigna un costo cero. Los envíos al punto de demanda ficticio indican capacidad de suministro sin uso. 1. Crear una Demanda Ficticia

2. Establecer la cantidad de unidades demandadas igual al exceso de la Oferta 3. Establecer un costo cero (0)

COMO EQUILIBRAR UN PROBLEMA DE TRANSPORTE LA OFERTA TOTAL EXCEDEA A LA DEMANDA

Problema de distribución de P&T Co. Ejemplo con Demanda Ficticia Costo uni. Origen

Destino (almacén) Sacramento

Salt Lake City

Rapid City

Alburquerque

Suministro

464

513

654

867

130

352

416

690

791

125

Albert Lea

995

682

388

685

100

Demanda:

80

65

70

85

Bellingham

(enlatadora) Eugene

355 300

55 Crear una demanda ficticia por 55 unidades

15

13/09/2017

COMO EQUILIBRAR UN PROBLEMA DE TRANSPORTE LA OFERTA TOTAL EXCEDEA A LA DEMANDA

Ejemplo con Demanda Ficticia Costo uni.

55 unidades a Costo Cero

Destino (almacén) Sacramento Salt Lake City

Rapid City

Alburquerque

DF

Suministro

464

513

654

867

0

130

Albert Lea

352 995

416 682

690 388

791 685

0 0

125 100

Demanda:

80

65

70

85

55

Origen Bellingham (enlatador a) Eugene

355 355

0

Luego proceder a la solución con uno de los métodos iniciales de asignación y luego aplicar simplex para Transporte

SOLUCIÓN: VOGEL Ejemplo con Demanda Ficticia

Aplicando Vogel Destino (almacén) Salt Sacram Lake Rapid Alburq ento City City uerque

Bellingha m

464

513

654

DF 867

Oferta 0

55 Origen

Eugene

352

416

690

791

464 130

0

75 352

125

(enlatadora)

Albert Lea

995

682

388

685

0

388 100

Demanda

80

65 112

70 97

85 266

55 106

0

16

13/09/2017

SOLUCIÓN: VOGEL Ejemplo con Demanda Ficticia

Aplicando Vogel Destino (almacén) Salt Sacram Lake Rapid Alburq ento City City uerque

Bellingha m

DF

Oferta

464

513

654

867

0

352

416

690

791

0

995

682

388

685

0

55 Origen Eugene (enlatador a) Albert Lea

49 75 64 125

70 Demanda

80

65 112

70 97

294 100

85 266

30

55 0 106

SOLUCIÓN: VOGEL Ejemplo con Demanda Ficticia

Aplicando Vogel Destino (almacén) Salt Lake City

Sacram ento Bellingha m

464

Rapid City 513

Alburq uerque 654

DF 867

Oferta 0

55 Origen Eugene (enlatador a) Albert Lea

Demanda

49 75

352

416

690

791

0

995

682

388

685

0

64 125

80

65 112

97

70

30

70 0

85 55

3 30

0

0 106

17

13/09/2017

SOLUCIÓN: VOGEL Ejemplo con Demanda Ficticia

Aplicando Vogel Destino (almacén) Salt Lake City

Sacram ento Bellingha m

Rapid City

464

513

Alburq uerque 654

DF 867

Oferta 0

55 Origen Eugene (enlatador a)

352

416

690

791

0

995

682

388

685

0

80

Albert Lea

Demanda

49 75 64 125

80

65

70

30

0

55

45

0 0

0 112

97

76

SOLUCIÓN: VOGEL Ejemplo con Demanda Ficticia

Aplicando Vogel Destino (almacén) Salt Lake City

Sacram ento Bellingha m

464

Rapid City 513

Alburqu erque 654

20 Origen Eugene (enlatador a)

352 80

Albert Lea

Demanda

867 55

Oferta 0

55

354 75

416

690

791

0

682

388

685

0

45 995

0

DF

375 45

65 0

70

30

0

55

0

0

0

0

0 97

76

18

13/09/2017

COMO EQUILIBRAR UN PROBLEMA DE TRANSPORTE LA OFERTA TOTAL MENOR A LA DEMANDA •

•

Si un problema de transporte tiene una Oferta total que es estrictamente menor que la Demanda total, entonces el problema no tiene solución factible. Cuando la Oferta total es menor que la Demanda total, a veces es deseable permitir la posibilidad de dejar sin satisfacer parte de la demanda. En este tipo de situaciones, se asocia una penalización con la demanda no cumplida.

1. Crear una Oferta Ficticia 2. Establecer la cantidad de unidades ofertadas igual al exceso de la Demanda 3. Establecer un costo Muy Alto

COMO EQUILIBRAR UN PROBLEMA DE TRANSPORTE LA OFERTA TOTAL MENOR A LA DEMANDA Problema de distribución de P&T Co. Ejemplo con Oferta Ficticia Costo uni.

Destino (almacén) Sacramento Salt Lake City

Rapid City

Alburquerque

Suministro

464

513

654

867

75

352

416

690

791

125

Albert Lea

995

682

388

685

60

Demanda:

80

65

70

85

Origen Bellingham (enlatadora ) Eugene

260 300

-40

Crear una oferta ficticia por 40 unidades

19

13/09/2017

COMO EQUILIBRAR UN PROBLEMA DE TRANSPORTE LA OFERTA TOTAL MENOR A LA DEMANDA

Ejemplo con Oferta Ficticia Costo uni. Origen Bellingham (enlatador a) Eugene Albert Lea OF

Destino (almacén) Sacramento Salt Lake City Rapid City 464 513 654

40 unidades a Costo 5000 Alburquerque 867

Suministro 75 125 60 40

352 995 5000

416 682 5000

690 388 5000

791 685 5000

80

65

70

85

300 Demanda:

0 los Luego proceder300 a la solución con uno de métodos iniciales de asignación y luego aplicar simplex para Transporte

SOLUCIÓN: Después de aplicar la esquina noroeste y el simplex para Transporte, se obtiene:

Ejemplo con Oferta Ficticia Cantidad por enviar

Destino (almacén) Salt Lake Sacramento City Rapid City Bellingham 0 20 10

Origen (enlatado ra) Eugene Albert Lea Total enviado

Demanda:

Alburquerqu Total e recibido 45 75

80 0 0

45 0 0

0 60 0

0 0 40

80 = 80

65 = 65

70 = 70

85 = 85

125 60 40

= = =

Suministro 75 125 60 40

Costo Total 325975

Se entiende que Alburquerque, deja de recibir 40 unidades

20

13/09/2017

EJERCICIO 1 •

Una empresa de manufactura, tiene 4 plantas de procesos industriales ubicados en diversas ciudades del país, los cuales abastecen a 5 almacenes, los costos por unidad se detallan en la siguiente tabla: Almacén 1

•

Almacén 2

Almacén 3

Almacén 4

Almacén 5

Industria 1

125

90

110

90

140

Industria 2

120

95

85

85

130

Industria 3

115

100

100

70

120

Industria 4

100

115

120

105

100

Se sabe también que las ofertas son de 500,750,1000 y 1500 y las demandas son de 1500, 500, 1000, 800, 1300; establezca una solución inicial con el método de los costos mínimos y además utilice solver para encontrar una solución

EJERCICIO 2 •

Una empresa de manufactura de producción de sombreros, tiene que satisfacer la demanda de 4 clientes semanalmente, las cuales son: 5000, 10000, 12000 y 15000 unidades, actualmente se tiene 4 plantas de fabricación, los costos por unidad se detallan en la siguiente tabla:

Almacén 1

•

Almacén 2

Almacén 3

Almacén 4

Planta 1

2

5

3

2

Planta 2

3

9

4

3

Planta 3

4

6

6

4

Planta 4

5

7

8

5

Se sabe también que las ofertas son de 11000 unidades por planta de producción, establezca una solución inicial con el método de vogel y además utilice solver para encontrar una solución. Nota trabajar en lotes de 1000

21

13/09/2017

EJERCICIO 3 •

• •

Siltex, debe decir un plan de distribución entre sus 4 almacenes y 4 plantas de producción. Los costos por kilometro recorrido es de 0.90 centavos de dólar por producto, un camión puede llevar hasta 20,000 unidades por viaje. Las ofertas son de 150, 250, 200 y 300 camiones, las demandas de cada en cada uno de los almacenes es de 185, 350, 150, 287 camiones. En la siguiente tabla se dan los kilómetros recorridos. Establecer un plan de distribución a un mínimo costo.

Kilómetros recorridos

Almacén 1

Almacén 2

Almacén 3

Almacén 4

Planta 1

480

550

600

870

Planta 2

950

870

703

500

Planta 3

750

850

700

650

Planta 4

800

600

750

550

22