PROBLEMA DE FLUJO DE COSTO MINIMO. EL PROBLEMA DE TRANSPORTE 1. Una empresa energética dispone de tres plantas de generación para satisfacer la demanda eléctrica de cuatro ciudades. Las plantas 1, 2 y 3 pueden satisfacer 35, 50 y 40 millones de [kWh] respectivamente. El valor máximo de consumo ocurre a las 2 PM y es de 45, 20, 30 y 30 millones de [kWh] en las ciudades 1, 2, 3 y 4 respectivamente. El costo de enviar 1 [kWh] depende de la distancia que deba Hacia Oferta recorrer la energía. La siguiente tabla Desde Ciudad 1 Ciudad 2 Ciudad 3 Ciudad 4 (Millones kWh) muestra los costos de envío unitario Planta1 8 6 10 9 35 desde cada planta a cada ciudad. Planta 2 9 12 13 7 50 Formule un modelo de programación Planta 3 14 9 16 5 40 lineal que permita minimizar los costos Demanda 45 20 30 30 de satisfacción de la demanda máxima (Millones KWh) en todas las ciudades.

Oferta

8 15 9 20 14 10 45/30/10/0

6 20 12 9

10 13 16 30

9 7 30 5

35/15/0 50/20/0 40/30/0

20/0

30/0

30/0

125

125 Está en equilibrio

Costo total: 15(8)+20(9)+10(14)+20(6)+30(16) ═ 1250 R/ En la ciudad 1 si se quiere satisfacer la demanda se necesita 15 de la planta 1, 20 de la planta 2 y 10 de la planta 3. En la ciudad 2 se cubre la demanda con 20kw en la planta 1. En la ciudad 3 necesitan comprar 30 en la planta 3 y la ciudad 4 necesitan 30 en la planta 2 para un costo mínimo de 1250. 2.

Una empresa dedicada a la fabricación de componentes de ordenador tiene dos fábricas que producen, respectivamente, 800 y 1500 piezas mensuales. Estas piezas han de ser transportadas a tres tiendas que necesitan 1000, 700 y 600 piezas, respectivamente. Los costes de transporte, en pesetas por pieza son los que aparecen en la tabla adjunta. ¿Cómo debe organizarse el transporte para que el coste sea mínimo? Fabrica I Fabrica II

Tienda A 3 2

Tienda B 7 2

Tienda C 1 6

Oferta

3 200

7 2 2 700 1000/800/0 700/0 800

Demanda

1 600 6 600/0

800/200/0 1500/700/0 2300 2300

Es Equilibrado

Costo total: 200(3)+800(2)+700(2)+600(1) ═ 4200 R/ En la fábrica I la tienda A compra 200 y en la II compra 800, la tienda B compra en la fabrica II, 700 y la tienda C compra en la fábrica I, 600. Se reducirá costos a 4200.

3.

Una empresa dedicada a la distribución de aceite de oliva debe enviar 30 toneladas a Madrid, 40 a Barcelona, 20 a Valencia y 10 a Bilbao. Esta empresa suministra en Badajoz, Cáceres y Jaén, cuyas disponibilidades son de 35, 25 y 20 toneladas, respectivamente. Los costes en euros de envió de una tonelada de los lugares de promoción a los destinos son : Por cada tonelada no recibida en los puntos de destino, la empresa Madrid Barcelona Valencia Bilbao tiene unas pérdidas de 5, 8, 6 y 4 euros, respectivamente. La empresa Badajoz 10 15 20 9 desea minimizar el coste total de la distribución de la mercancía. Cáceres 6 7 10 15 ¿Como podría hacerse la distribución optima? Jaén 15 20 25 30

Oferta

10 25 65 15 0 30/5/0

Demanda

15 7 20 20 20 0 40/20/0

20 10 25 0 20 20/0

9 10 15 30 0 10/0

35/25/0 25/20/0 20/0 20/0 100

Oferente Ficticio 100

Se equilibró con un oferente ficticio

Costo total: 25(10)+5(6)+20(7)+20(20)+20(0)+10(9) ═ 910 R/ Madrid necesita que se le distribuya 25 de Badajoz, 5 de Cáceres; para Barcelona se necesitan 20 de Cáceres y 20 de Jaén; Valencia necesita 20 de un ficticio y Bilbao 10 de Cáceres y se reducen costos a 910. 4.

Un fabricante de chips tiene que planificar la producción para los próximos tres meses de tres diferentes chips (A,B,C). Los costes de producción por chip son de A, 6 céntimos en los primeros meses y de 9 céntimos en el tercero; de B, 8 los dos primeros y 11 el último mes; y de C, 6 céntimos los dos primeros meses y 8 el ultimo. El departamento de marketing ha llevado a cabo un estudio estimado que la demanda en los tres meses ser la de 300, 400 y 500 unidades, respectivamente. La fábrica puede producir 400 unidades de cada tipo de chip. ¿Cómo se puede optimizar la distribución de la fabricación de los chips en estos tres meses?

meses 1 2 3 Demanda

A 6 300 6 9 300/0

B 8 8 11 400 400/0

C 6 100 6 400 8 500/400/0

Oferta 400/100/0 400/0 400/0 1200 1200

Esta equilibrado

Costo total: 300(6)+100(6)+400(6)+400(11) ═ 9200 R/ Del chip A se deben producir 300 en el 1er mes, en el chip B deben producirse 400 en el 3er mes y del chip C 100 en el primero y 400 en el segundo para obtener un costo mínimo de 9200.

5.

Una empresa de componentes informáticos puede comprar discos duros a tres proveedores y su objetivo es minimizar el coste total de la compra. Los proveedores disponen de 1000, 3000 y 1000 discos respectivamente. La empresa necesita los discos en tres cadenas de montaje sitas en tres localidades distintas. Dichas cadenas requieren 1500, 1000 y 2500 discos respectivamente. Los precios en cientos de euros por cada disco entregado a cada cadena son como siguen: Calcular la solución óptima.

Proveedor

1 2 3

Cadena 1 2 4 7 3 5 9 11

3 2 2 10

Oferta 4 3 1500 9 1500/0

Demanda

2 1000 2 1500 10 2500/1500/0

7 5 11 1000 1000/0

1000/0 3000/1500 1000/0 5000

Esta equilibrado

5000

Costo total: 1500(3)+1000(11)+1000(2)+1500(2) ═ 20,500 R/ La cadena 1 necesita comprar al proveedor 2, 1500 discos; la cadena 2 debe comprar 1000 al proveedor 3 y la cadena 3 debe distribuir su compra con el proveedor 1, 1000 y con el 2, 1500 para reducir costos a 20,500.

6.

Una fábrica de vidrio cuenta con 40 toneladas de arena tipo A y 20 toneladas de arena tipo B para utilizar este mes. La arena se funde para fabricar vidrio óptico, vidrio para envases o vidrio para ventanas. La compañía tiene órdenes por 20 toneladas de vidrios óptico, 25 toneladas de vidrio para envases y 25 toneladas de vidrio para ventanas. Los costos para producir una tonelada de cada tipo de vidrio a partir de cada tipo de arena están a continuación. Resuelva el problema formulándolo como uno de transporte.

Problema 6.

Tipo de vidrio Arena A

Óptico

Envases

Ventanas

12

3

5

8

2

4

Arena B

Oferta

Demanda

12 8 10 0 10 20/10/0

3 25 2 0 25/0

5 15 4 10 0 25/10/0

40/15/0 20/10/0 10/0 70

Oferente ficticio 70

Se equilibra agregando un oferente ficticio

Costo total: 10(8)+10(0)+25(3)+15(5) ═ 230

7.

Cierta empresa tiene dos plantas y tres distribuidores. En la siguiente tabla se muestran los costos de transporte de cada planta a cada centro de distribución, junto con las ofertas disponibles de cada planta y los requerimientos de cada distribuidor. Resuelve el problema formulándolo como uno de transporte.

Planta J K Demanda

100

Distribuidor B C 85 20 110

90 15

105 5

A

15/0

25/5/0

75 20 20/0

Planta J K Demanda

Oferta 20/0 40/20/5/0 60 /60

Costo total: 20(85)+15(0)+105(5)+75(20) ═ 5075

Distribuidor A B C 100 85 110 90 105 75 15 25 20

Oferta 20 40

8.

Una empresa de camiones envía camiones cargados de grano desde tres silos a cuatro molinos. La oferta (en camiones cargados) y la demanda (también en camiones cargados), junto con los costes de transporte por carga de camión en las diferentes rutas se resumen en el modelo de transporte siguiente. Los costos de transporte por unidad, cij , son en cientos de soles. Determinar el costo mínimo del programa de envió entre los silos y los molinos.

Silos

1 2 3

1 10 12 4

Molinos 2 3 2 20 7 9 14 16

4 11 20 18

Método húngaro Molinos 1 2 3 4

Silos

1

10 2

20 11 2

2

12 7

9

3

4

8

0

20 11

5

0

9

0

10 16 18

2

20 7

14 16 18 4

20

9

8

0

16 0

5

0

0

0

10 10 5

4

Costo total: 4+9+11=24

9.

Una compañía fabrica estufas y hornos. La compañía tiene tres almacenes y dos tiendas de Cadena venta al detalle. En los tres almacenes se dispone, respectivamente, de 60, 80 y 50 estufas, y 1 2 de 80, 50 y 50 hornos. En las tiendas de detalle se requieren, respectivamente, 100 y 90 1 3 5 estufas, y 60 y 120 hornos. En la siguiente tabla se dan los costos de envío por unidad, de los Almacén 2 2 3 almacenes a las tiendas de detalle, los cuales se aplican tanto a estufas como a hornos. 3 6 3 Encontrar las soluciones factibles óptimas para estos problemas de transporte. Los costos de envío por unidad de los almacenes a las tiendas, los cuales se aplican tanto a estufas como a hornos la suma de ellos se detalla en la primera tabla. Esto para equilibrar el problema.

1

Almacén

1 2 3

Estufas Hornos Demanda Estufas y Hornos

3 2 6 100 60 160

Oferta

Cadena 2 5 3 3 90 120

Estufas

Hornos

Estufas y Hornos

60 80 50

80 50 50

140 130 100

370 210

370

Cadena 2

1

Almacén

Demanda

Oferta Estufas y Hornos

1

3

140

5

2

2

20

3

110

130/110/0

3

6

3

100

100/0

Estufas y Hornos

160/20/0

140/0

370 370

210/100/0

Costo total: 140(3)+20(2)+110(3)+100(3) ═ 1090 R/ Para satisfacer la demanda de los almacenes y solucionar el problema de transporte se deben enviar 140 del almacén 1 a la cadena 1 y 20 del almacén 2 a la cadena 1; del almacén 2 a la cadena 2, 110 y del almacén 3 deben enviarse 100 a la cadena 2. 10. Una fábrica produce tres artículos A, B y C, en las siguientes tres plantas que posee. La primera y segunda planta pueden fabricar los tres artículos pero la tercera solo los artículos A y C. La demanda de los artículos A, B y C son 600, 800 y 700 unidades diarias respectivamente. La primera como la tercera planta su producción es de 600 unidades diarias y la segunda planta es de 900 unidades diarias. El costo de fabricación Soles/unidad es: Artículos Planta

A

B

C

1

5

8

6

2

6

8

5

3

7

X

5

Plantear y resolver el problema como un modelo de transporte.

Artículos A 1

5

600

B

C

8

Oferta

6

600

600/0 Planta

2

6

8

3

7

X

800

5

100

900

5

600

600

900/100/0 600/0 600

Demanda

700

800 600/0

800/100/0

2100

2100

700/600/0

Costo total: 600(5)+800(8)+100(5)+600(5) ═ 12900 R/ Para satisfacer la demanda el articulo A de la planta 1, 600; el articulo B de la planta 2, 800; y del articulo C es necesario satisfacer 100 de la planta 2 y 600 de la planta 3.

11. Tres plantas producen un producto, que luego es transportado a dos centros de consumo. Los costos de producción, los costos de transporte desde las plantas a los centros de consumo, así como la oferta y la demanda se dan en la siguiente tabla: Costo de Producción $/u

Costo de Transporte $/u C. de consumo1 C. de consumo2

Planta

Oferta

1

50

5

7

900

2

55

8

5

500

3

53

6

6

600

Demanda

1.200

700

Resolver el problema como un modelo de transporte con el objetivo de minimizar el costo total e interpretar los resultados.

Planta

Costo de Producción $/u

Costo de C. de consumo1

Transporte $/u C. de consumo2

Oferta

1

50

5

7

900

2

55

8

5

500

3

53

6

6

600

Demanda

1.200

700

Planta

Costo de Producción $/u

1

50

5

2

55

8

3

53 Demanda

Costo de C. de consumo1

6

500

300

Transporte $/u C. de consumo2 7

0

5

500

6

200

1.200/300/0 700/0

Ficticio

900/0

0 0

Oferta

500/0 100

100/0

600/300/100/0 2000/2000

CT=500(5)+500(5)+300(6)+200(6)=5500 R/ Para satisfacer los centros de consumo se distribuyen 500 de la planta 1 al centro 1 y 300 de la planta 3 al centro 1; para el centro 2, 500 de la planta 2 y 200 de la planta 3; al 3er centro 100 de la planta 3.

12. Tres plantas de energía eléctrica con capacidad de 20, 35 y 40 millones de kilovatios/hora, proporcionan electricidad a tres ciudades. La demanda máxima en las tres ciudades se calcula en 30, 35 y 25 millones de kilovatios/hora. La tabla proporciona el precio por millón de kilovatios/hora en las tres ciudades. Durante el mes de agosto hay un incremento de 20% en la demanda en cada una de las tres ciudades, que se puede satisfacer comprándole electricidad a otra red, a un precio de $1000 por millón de kilovatios/hora. Sin embargo esta red no está conectada con la ciudad 1. La Compañía de Servicios Públicos quiere determinar el plan más económico para la distribución y la compra de energía eléctrica adicional. Resuelva e interprete la solución óptima.

Ciudades Planta

1

2

3

1

$600

$700

$400

2

$320

$300

$350

3

$500

$480

$450

Planta

1

2

3 $400

1

$600

$700

2

$320

$300

3

$500

Demanda

30/0

30

35

4 20

$350

$480

$450

35/0

25/5/0

5

Oferta

0

20/0

0

35/0

0

5

5/0

40/10/ 5/0 95/95

CT=400(20)+300(35)+500(30)+450(5)=35750 R/Se debe distribuir 30 kw de la planta 3 a la ciudad 1, 35 de la planta 2 a la ciudad 2; 20 de la planta 1 a la ciudad 3 y 5 de la planta 3 a la ciudad 3 y por ultimo 5 de la planta 3 a la ciudad 4.

13. Una compañía dispone de tres fábricas para elaborar cuatro productos: A, B, C y D. La oferta de producción de las tres fábricas son: 900, 1200 y 700 respectivamente sin importar que producto se fabrica. Las demandas son 500 unidades de A, 700 unidades de B, 900 unidades de C y 900 unidades de D. La fábrica 3 no puede elaborar el producto B. Hay una penalización por demanda insatisfecha de un producto, la cual es para cada producto de un 25% de su menor costo de fabricación, pero el producto B se debe satisfacer toda su demanda. Los costos de fabricación se dan en la siguiente tabla: Resuelva e interprete la solución óptima con el objetivo de minimizar el costo. Fabrica

A

B

1

4

3

2

5

3 4

4

300

4

C

D 900

2

3

900/0

300

4

400

5

4

700/300/0

0

200/0

0

0

0

500/200/0

700/400/ 0

900/0

CT= 900(2)+300(4)+900(2)+300(4)=6000

900

2

900/0

1200/300/ 0

300/300

Productos Fábricas

A

B

C

D

1

4

3

2

3

2

5

4

4

2

3

4

5

4

14. Tres refinerías con capacidades diarias máximas de 6, 5 y 6 millones de galones de gasolina reparten a tres áreas de distribución con demandas diarias de 5, 7 y 7 millones de galones del combustible. La gasolina se transporta a las tres áreas de distribución a través de una red de tubería. El costo de transporte se calcula con base en la longitud de la tubería a un dólar por 10000 galones por milla recorrido. La tabla siguiente indica la distancia de la Refinería a las áreas de distribución en millas. Área de distribución Refinería

1

2

3

1

120

180

80

2

300

100

90

3

200

250

120

Asimismo, el área de distribución 1 debe recibir toda su demanda y cualquier escasez en las áreas 2 y 3 dará lugar a una penalización de diez dólares por 10000 galones. Hallar e interpretar la solución óptima. 120

180

80

6/0

90

5/4/0

120

6/1/0

6 300

100

4 200

1 250

5

1

0

0

0

2/0

5/0

2 7/3/2/0

7/1/0

19/19

CT= 6(80)+ 4(100) +1(90)+ 5(200)+ 1(250)+ 2(0)=2220 15. Una empresa dispone de tres obreros los cuales pueden ser asignados a dos trabajos a la vez. La empresa ofrece cuatro trabajos diferentes. T1 T2 T3 T4 La empresa suministra la tabla de rendimiento de obreros & trabajo. ¿Cómo se debe hacer la asignación y cuál es el valor del óptimo del O1 10 12 12 8 rendimiento? O2 9 10 10 5 O3 8 8 10 8

O1 O2 03

2 4 0

4 4 0 5 5 0 0 2 0

O1 O2 03

2 4 0

4 2 0 5 3 0 0 0 0

O1 O2 03

0 2 0

2 0 0 3 1 0 0 0 1

O1 O2 03

0 0 0 0 2 1 1 0 1 0 0 2

CT= 12+8+5=25