• Author / Uploaded
• Angie Osco

Citation preview

“Año de la lucha contra la corrupción e impunidad” E.A.P. Ingeniería Industrial

TRABAJO DE INVESTIGACIÓN OPERATIVA II

Universidad Nacional Mayor de San Marcos Facultad de Ingeniería Industrial E.A P. Ingeniería Industrial

INTEGRANTES:

16170207

Labán Medrano, Madeley Saori

16170069

Sihuay Torres, Miguel Ángel

16170058

Lino Paredes, Jhon Maykol

Contenido 1.

4

1.1.

4

1.1.1.

4

1.1.2.

5

1.1.3.

5

1.2.

8

1.2.1

8

1.2.2.

9

1.2.3.

9

2.

11

2.1.

11

2.1.1.

11

2.1.2.

12

2.1.3.

12

2.2.

16

2.2.1.

16

2.2.2.

17

2.2.3.

17

3.

21

3.1. Problema 5

21

3.1.1. Solución Manual

21

3.1.2. Solución en WinQSB

23

3.1.3. Solución en LINGO

24

3.2.

27

3.2.1.

27

3.2.2.

30

3.2.3.

32

4.

35

4.1. 4.1.1.

35 36

4.1.2.

36

4.1.3.

37

4.2.

37

4.2.1.

39

4.2.2.

40

4.2.3.

40

5.

41

5.1.

41

5.1.1.

42

5.1.2.

42

5.1.3.

43

5.2.

44

6.1.1.

44

6.1.2.

45

6.1.3.

46

7.

47

7.1.

47

7.1.1.

47

7.1.2.

49

7.1.3.

50

7.2.

52

7.2.1.

52

7.2.2.

54

7.2.3.

54

1. Método de la Ruta más corta 1.1.

Problema 1

Determine la distancia más corta entre el nodo CASA y SAN MARCOS de la siguiente red:

1.1.1. Solución Manual 1) mCASA = 0 2) m1 = min {mCASA+dCASA1} m1 = min {0+300} m1 =300 3) m3 = min {mCASA+dCASA3} m3 = min {0+300} m3 = 300 4) m2 = min {m1+d12, m3+d32} m2 = min {300+100, 300+200} m2 = min {400, 500} m2 = 400 5) m4 = min {m1+d14, m2+d24} m4 = min {300+200, 400+300} m4 = min {500, 700} m4 = 500 6) m5 = min {m2+d25, m3+d35, m4+d45} m5 = min {400+200, 300+100, 500+300} m5 = min {600, 400, 800} m5 = 400 7) mSANMARCOS = min {m3+c3SM, m5 + d5SM} mSANMARCOS = min {300+300, 400+200} mSANMARCOS = min {600, 600} mSANMARCOS = 600

Rpta: La distancia más corta es 600 metros. Rutas: CASA -> 3 -> SAN MARCOS CASA -> 3 -> 5 -> SAN MARCOS

1.1.2. Solución en WinQSB

1.1.3. Solución en LINGO

1.2. Problema 2 La municipalidad de Lima está desarrollando un plan de reposición de su flotilla de buses de la nueva “Línea amarilla” para un horizonte de planeación de 4 años, que comienza el 1 de enero del 2019 y termina el 31 de diciembre de 2022. Al iniciar cada año se toma la decisión de si un auto se debe mantener en operación o se debe sustituir. Un bus de dicha línea debe estar en servicio durante 1 año como mínimo, y 3 años como máximo. La tabla siguiente muestra el costo de reposición en función del año de adquisición del vehículo y los años que tiene en funcionamiento: Equipo adquirido al comenzar el 2019 2020 2021 2022

Costo de reposición ($) para los años de operación 1 4000 4300 4800 4900

2 5400 6200 7100 -

1.2.1 Solución Manual

1. m1 = 0 2. m2 = min {m1+c12} m2 = min {0+4000} m2 =4000 3. m3 = min {m1+c13, m2+c23} m3 = min {0+5400, 4000+4300} m3 = 5400 4. m4 = min {m1+c14, m2+c24, m3+c34} m4 = min {0+9800, 4000+6200, 5400+4800} m4 = min {9800, 10200, 10200} m4 = 9800 5. m5 = min {m3+c35, m4+c45, m2+c25} m5 = min {5400+7100, 9800+4900, 4000+8700} m5 = 12500 Rpta: El camino más corto es: 1 -> 3 -> 5 con un costo total de $12500.

3 9800 8700 -

1.2.2. Solución en WINQSB

1.2.3. Solución en LINGO

2. Árbol de Expansión Mínima 2.1. Problema 3 Determinar el árbol de expansión mínima de la red

2.1.1. Solución Manual 1. C = {} C’ = {1,2,3,4,5,6} 2. C = {1} C’ = {2,3,4,5,6} 3. min = {1,9,5,7} C = {1,2} C’ = {3,4,5,6} 4. min = {7,5,9,4,6,3} C = {1,2,5} C’ = {3,4,6} 5. min = {7,5,4,6,8,2} C = {1,2,5,6} C’ = {3,4} 6. min = {7,5,4,6,8,10,3} C = {1,2,5,6,4} C’ = {3} 7. min = {5,6,5,10} C = {1,2,3,4,5,6} C’ = {} Rpta: 1-2-5-6-4-3. Longitud: 14 km.

2.1.2. Solución en WINQSB

2.1.3. Solución en LINGO

2.2. Problema 4 La administración de Claro Perú debe determinar los caminos bajo los cuales se deben tender las líneas telefónicas en el distrito de Lince para conectar todas las estaciones con una longitud total mínima de cable. Los nodos y las distancias se resumen a continuación, en donde las líneas representan ligaduras potenciales.

2.2.1. Solución Manual 1. C = {} C’ = {O,A,B,C,D,E,T} 2. C = {O} C’ = {A,B,C,D,E,T} 3. min = {2,5,4} C = {O,A} C’ = {B,C,D,E,T} 4. min = {5,4,2,7} C = {O,A,B} C’ = {C,D,E,T} 5. min = {4,1,7,4,3} C = {0,A,B,C} C’ = {D,E,T} 6. min = {7,4,3,4} C = {O,A,B,C,E} C’ = {D,T} 7. min = {7,4,1} C = {O,A,B,C,D,E} C’ = {T} 8. min = {5,7} C = {O,A,B,C,D,E,T} C’ ={} Rpta: O-A-B-C-E-D-T. Longitud: 2+2+1+3+1+5 = 14

2.2.2. Solución en WINQSB

2.2.3. Solución en LINGO

3. Algoritmo de Dijkstra 3.1. Problema 5 Encuentre la ruta más corta de la siguiente red para que el gasto de envío sea el menor posible. Los números entre nodos están en cientos de soles y representan el costo de envío del nodo i al nodo j.

3.1.1. Solución Manual 1) O A B C D E F G H I T [ 0*, 4, 3, 6, ∞, ∞, ∞, ∞, ∞, ∞, ∞ ] 2) O A B C D E F G H I T [ 0*, 4, 3*, 6, ∞, ∞, ∞, ∞, ∞, ∞, ∞ ] 3) Nueva etiqueta C = Min[6, 3+4] = Min[6, 7]=6 Nueva etiqueta E = Min[∞, 3+6] = Min[∞, 9]=9 O A B C D E F G H I T [ 0*, 4, 3*, 6, ∞, 9, ∞, ∞, ∞, ∞,∞ ] 4) O A B C D E F G H I T [ 0*, 4*, 3*, 6, ∞, 9, ∞, ∞, ∞, ∞,∞ ] 5) Nueva etiqueta C = Min[6, 4+5] = Min[6, 9]=6 Nueva etiqueta D = Min[∞, 4+3] = Min[6, 7]=6 O A B C DE F G H I T [ 0*, 4*, 3*, 6, 6, 9, ∞, ∞, ∞, ∞,∞ ] 6) O A B C D E F G H I T [ 0*, 4*, 3*, 6*, 6, 9, ∞, ∞, ∞, ∞,∞ ]

7) Nueva etiqueta D = Min[6, 6+2] = Min[6, 8]=6 Nueva etiqueta E = Min[9, 6+5] = Min[9, 11]=9 Nueva etiqueta F = Min[∞, 6+2] = Min[∞, 8]=8 O A B C DE F G H I T [ 0*, 4*, 3*, 6*, 6, 9, 8, ∞, ∞, ∞,∞ ]

8) O A B C D E F G H I T [ 0*, 4*, 3*, 6*, 6*, 9, 8, ∞, ∞, ∞,∞ ] 9) Nueva etiqueta F = Min[8, 6+2] = Min[8, 8]=8 Nueva etiqueta G = Min[∞, 6+4] = Min[∞, 10]=10 O A B C D E F G H I T [ 0*, 4*, 3*, 6*, 6*, 9, 8, 10, ∞, ∞,∞ ] 10) O A B C D E F G H I T [ 0*, 4*, 3*, 6*, 6*, 9, 8*, 10, ∞, ∞,∞ ] 11) Nueva etiqueta E = Min[9, 8+1] = Min[9, 9]=9 Nueva etiqueta G = Min[10, 8+2] = Min[10, 10]=10 Nueva etiqueta H = Min[∞, 8+5] = Min[∞, 13]=13 O A B C D E F G H I T [ 0*, 4*, 3*, 6*, 6*, 9, 8*, 10, 13, ∞,∞ ] 12) O A B C D E F G H I T [ 0*, 4*, 3*, 6*, 6*, 9*, 8*, 10, 13, ∞,∞ ] 13) Nueva etiqueta H = Min[13, 9+2] = Min[13,11]=11 Nueva etiqueta I = Min[∞, 9+5] = Min[∞, 14]=14 O A B C D E F G H I T [ 0*, 4*, 3*, 6*, 6*, 9*, 8*, 10, 11, 14,∞ ] 14) O A B C D E F G H I T [ 0*, 4*, 3*, 6*, 6*, 9*, 8*, 10*, 11, 14,∞ ] 15) Nueva etiqueta H = Min[11, 10+2] = Min[11,12]=11 Nueva etiqueta T = Min[∞, 10+7] = Min[∞, 17]=17 O A B C D E F G H I T [ 0*, 4*, 3*, 6*, 6*, 9*, 8*, 10*, 11, 14,17 ] 16) O A B C D E F G H I T [ 0*, 4*, 3*, 6*, 6*, 9*, 8*, 10*, 11*, 14,17 ]

17) Nueva etiqueta I = Min[14, 11+3] = Min[14,14]=14 Nueva etiqueta T = Min[17, 11+8] = Min[17, 19]=17 O A B C D E F G H I T [ 0*, 4*, 3*, 6*, 6*, 9*, 8*, 10*, 11*, 14,17 ] 18) O A B C D E F G H I [ 0*, 4*, 3*, 6*, 6*, 9*, 8*, 10*, 11*, 14*,17 ]

T

19) Nueva etiqueta T = Min[17, 14+4] = Min[17, 18]=17 O A B C D E F G H I T [ 0*, 4*, 3*, 6*, 6*, 9*, 8*, 10*, 11*, 14*,17 ] 20) O A B C D E F G H I [ 0*, 4*, 3*, 6*, 6*, 9*, 8*, 10*, 11*, 14*,17* ]

T

Ruta más corta: O-C-F-G-T L(u)=17. Por lo tanto el costo mínimo de envío será de S/. 1700.

3.1.2. Solución en WinQSB

3.1.3. Solución en LINGO

3.2. Problema 6 La empresa Transvo S.A.C. ofrece el servicio de trasporte de carga pesada a diferentes departamentos del país. Una empresa constructora requiere que se transporte madera, cemento y tubos metálicos desde Lima a Ayacucho y luego a Arequipa lo más pronto posible. La empresa Transvo S.A.C. desea saber cuál sería la ruta óptima para llevar el material de construcción a ambos departamentos en el menor tiempo.

1

2

4 5 3

6

7

3.2.1. Solución Manual Primero calculamos la ruta óptima para trasportar la mercadería de Lima a Ayacucho.

1) 1 2 3 [ 0*, 327, 325, ∞ ] 2) 1 2 3 [ 0*, 327, 325*, ∞ ]

4

4

3) Nueva etiqueta 2 = Min[327, 325+473] = Min[327, 789]=327 Nueva etiqueta 4 = Min[∞, 325+325] = Min[∞, 650]=650 1 2 3 4 [ 0*, 327, 325*, 650 ] 4) 1 2 3 [ 0*, 327*, 325*, 650 ]

4

5) Nueva etiqueta 4 = Min[650, 327+261] = Min[650, 588]=588 1 2 3 4 [ 0*, 327*, 325*, 588 ] 6) 1 2 3 [ 0*, 327*, 325*, 588* ]

4

Ruta más corta: 1-2-4 L1(u)= 588 km. Ahora calculamos la ruta óptima para transportar la mercadería de Ayacucho a Arequipa.

1) 4 3 5 6 7 [ 0*, 325*, 575, ∞, ∞ ] 2) Nueva etiqueta 5 = Min[575, 325+798] = Min[575, 1123]=575 Nueva etiqueta 6 = Min[∞, 325+1013] = Min[∞, 1338]=1338 Nueva etiqueta 7 = Min[∞, 325+708] = Min[∞, 1033]=1033 4 3 5 6 7 [ 0*, 325*, 575, 1338, 1033 ] 3) 4 3 5 6 [ 0*, 325*, 575*, 1338, 1033 ]

7

4) Nueva etiqueta 6 = Min[1338, 575+386] = Min[1338, 961]=961 Nueva etiqueta 7 = Min[1033, 575+508] = Min[1033, 1083]=1033 4 3 5 6 7 [ 0*, 325*, 575*, 961, 1033 ] 5) 4 3 5 6 [ 0*, 325*, 575*, 961*, 1033 ] 6)

7

Nueva etiqueta 7 = Min[1033, 961+292] = Min[1033,1253]=1033

4 3 5 6 7 [ 0*, 325*, 575*, 961*, 1033 ] 7) 4 3 5 6 7 [ 0*, 325*, 575*, 961*, 1033* ]

Ruta más corta: 4-3-7 L2(u)= 1033 km. La ruta optima es: 1-2-4-3-7 Es decir: Lima-Huancayo-Ayacucho-Ica-Arequipa L1(u) + L2(u)= 588+1033=1621 km.

3.2.2. Solución en WINQSB

L1(u) + L2(u)= 588+1033=1621 km.

3.2.3. Solución en LINGO

4. Flujo máximo 4.1.

Problema 9

Pedro es gerente de una fábrica SAMSI S.A que produce tres tipos de productos (A, B, C) dos fábricas cercanas F1 y F2 en las cuales se puede fabricar cualquiera de los productos y tiene capacidades de producción de 75 y 48 mil productos al mes respectivamente. Los productos fabricados son llevados a los almacenes de la empresa (A1, A2, A3, A4) desde donde se transportan a los centros de distribución CD1 y CD2 cuyas capacidades de almacenamiento son 45 mil productos al mes c/u. Las capacidades máximas de transporte (en miles de unidades) para llevar productos de las fábricas a los almacenes y de los almacenes a los centros de distribución son: Se desea llevar la máxima cantidad de productos desde las fábricas hacia los centros de distribución.

A) Determinar un programa de producción y distribución en cada una de las fábricas, centros de distribución y almacenes. B) Formular un PL para hallar el flujo máximo

4.1.1. Solución Manual

Para estos casos se asume una capacidad grande de la fábrica para cada producto, esto se hace simplemente para anexar fabricas con juguetes en este caso asumiremos 300, si le quieres poner 500 o 600, sale lo mismo. Pero deben ser capacidades grandes. 1-2-4-7-11-13 Min{75,300,4,2,45}=2 1-2-4-7-12-13 Min{73,298,2,4,45}=2 1-2-4-8-11-13 Min{71,296,3,10,43}=3 1-2-4-9-11-13 Min{68,293,12,7,40}=7 1-2-4-9-12-13 Min{61,286,5,6,43}=5 1-2-4-10-11-13 Min{56,281,4,8,33}=4 INTERPRETACIÓN: 1-2-5-8-11-13 Min{52,300,10,7,29}=7 1-2-5-8-12-13 Min{45,293,3,7,33}=3 FLUJOMAXIMO: 51 mil productos Dado el flujo de mercadería, se puede trasladar como máximo 51 mil productos. 1-2-5-9-12-13 Min{42,290,5,1,30}=1 1-2-6-8-12-13 Min{41,300,4,4,29}=4 1-2-6-7-12-13 Min{37,296,6,2,29}=2 1-2-5-10-11-13 Min{35,289,7,4,27}=4 1-2-5-10-12-13 Min{31,285,3,14,23}=3 4.1.2. Solución en WinQSB 1-3-6-10-12-13 Min{48,300,4,11,20}=4

4.1.3. Solución en LINGO

4.2.

Problema 9

Una panadería (la de la esquina de mi casa), tiene 2 carros de distribución de panes a 5 Minimarket’s; cada Minimarket’s tiene diferentes capacidades de compra debido a la densidad poblacional donde están ubicadas. Esta información se encuentra en estos cuadros. La capacidad del 1° carro es de 3500 panes, la capacidad del 2° auto es de 7000 panes, y la capacidad de las bodegas es la siguiente; y estas 3 Minimarket’s. Posterior a ello hay 3 panaderos 1 perteneciente a cada Minimarket que vende esos panes desde muy temprano, los triciclos tienen una capacidad que se muestra en el siguiente cuadro.

Auto 1

M.M 1

1000

M.M 2

720

M.M 3

1000

Panadero. 1 Panadero. 2 Panadero. 3

A u t o 2 1 0 0 0 2 5 0 0 3 5 0 0

M.M 1 700

M.M 2 1800

M.M 3 1500

700

1800

1500

700

1800

1500

El siguiente cuadro representa la capacidad de los panaderos en sus triciclos.

Capacidad Panadero.1 1500 Panadero.2 2000 Panadero.3 1800

A) Determine mediante un algoritmo de flujo máximo la mayor capacidad que la panadería puede distribuir de tal forma que los panaderos vendan la cantidad óptima y corregir fallas en la distribución de planta.

4.2.1. Solución Manual

1-2-4-7-10 1-2-4-8-10 1-2-5-7-10 1-2-6-7-10

Min{3500,1000,700,1500}=700 Min{2000,300,700,2000}=300 Min{2500,720,1800,800}=720 Min{1780,1000,1500,80}=80

1-3-4-8-10 1-3-4-9-10 1-3-5-8-10 1-2-5-9-10

Min{7000,1000,400,1700}=400 Min{6600,600,700,1800}=600 Min{6000,2500,1800,1300}=1400 Min{4700,1200,1800,1200}=1400

Tiene un flujo máximo de 5300

4.2.2. Solución en WinQSB

4.2.3. Solución en LINGO

5. Ford Fulkerson 5.1.

Problema 9

Una empresa ABC posee 3 centros de producción (C1, C2, C3) en las que se fabrica un producto XX, cuyas capacidades de producción son 30,18,22 mil unidades de XX en mes. De los centros de producción se debe trasladara el producto a 3 almacenes de la empresa (A1, A2, A3) ubicadas en lugares distantes de la empresa cuyas capacidades de almacenamiento son de 15,20 y 25 mil unidades al mes. Debido a las limitaciones de transporte se cuenta con capacidades máxima de traslado (en miles de unidades/mes) que se ha dado en el siguiente cuadro. A .

DE C1 C2 C3

A1 11 16 -

A2 6 10 12

A3 9 4 5

A) Determine el flujo máximo que circula por la red mediante el método Ford Fulkerson B) Realizar un P.L para hallar el flujo máximo

5.1.1. Solución Manual

1-2-5-8 1-2-6-8 1-2-7-8 1-3-6-8

Min{30,11,15}=11 Min{19,6,20}=6 Min{13,9,25}=9 Min{14,10,14}=10

1-4-6-8 1-4-7-8 1-3-5-8 1-3-7-8

Min{22,12,4}=4 Min{18,5,12}=5 Min{18,16,4}=4 Min{4,4,16}=4

MÁXIMO FLUJO: 53 mil unidades

S.A

INTERPRETACIÓN: Dado el flujo de mercadería, se puede trasladar como máximo 53 mil unidades/mes.

5.1.2. Solución en WinQSB

5.1.3. Solución en LINGO

5.2.

Problema 10

Juan Carlos es Gerente de una empresa y posee 3 fábricas (F1, F2, F3) en las cuales produce un determinad producto en varios modelos diferentes. De las fábricas se envían los productos a los almacenes (A1, A2, A3, A4) y de los almacenes se envían a los puntos de distribución (D1, D2, D3, D4). Las capacidades de producción de cada fábrica F1, F2 y F3 son de 55 cientos de unidades al mes. Los almacenes tienen capacidad de almacenamiento ilimitado. Los puntos de distribución D1, D2, D3, D4 puede recibir como máximo 25,38,35 y 30 cientos de unidades al mes. Las capacidades máximas de transporte de las fábricas a los almacenes y de los almacenes a los puntos de distribución, se dan en la tabla siguiente: De/a F1 F2 F3

A1

A2

A3

A4

15 13 -

13 10 16

12 14

10 18 10

De/a A1 A2 A3 A4

D1

D2

D3

D4

12 10 8 -

9 14 10 12

15 11 8

10 6 8 10

6. A) Se desea determinar el plan de producción óptimo, aplique el algoritmo adecuado B) Formular un P.L para calcular el flujo máximo

6.1.1. Solución Manual

1-2-5-9-13 1-2-5-10-13 1-2-6-9-13 1-2-6-10-13 1-2-8-10-13 1-3-5-10-13 1-3-5-12-13 1-3-6-10-13 1-3-7-9-13 1-3-7-9-12 1-3-7-10-13

Min{55,15,12,25}=12 Min{43,3,9,3}=3 Min{40,13,10,13}=10 Min{30,3,14,35}=3 Min{27,10,12,32}=10 Min{55,13,6,22}=6 Min{47,7,10,30}=7 Min{42,10,13,16}=10 Min{32,12,8,3}=3 Min{29,9,10,6}=6 Min{23,3,11,35}=3

1-3-8-11-13 Min{20,18,8,32}=8 1-3-8-12-13 Min{10,10,10,23}=10 1-4-6-11-13 Min{55,16,15,24}=15 1-4-6-12-13 Min{40,1,6,13}=1 1-4-7-11-13 Min{39,14,8,9}=8 1-4-7-12-13 Min{31,14,8,12}=8 FLUJO MÁXIMO: 123 cientos de unidades/mes

INTERPRETACION: Dado el flujo de mercadería, se puede trasladar como máximo 123 cientos unidades/mes. B) S.A

CAPCACIDADES

6.1.2. Solución en WinQSB

6.1.3. Solución en LINGO

7. Flujo máximo a costo mínimo 7.1.

Problema 11

Se requiere minimizar el costo total sujeto a la disponibilidad y la demanda de algunos nodos, y de la conexión superior de flujo a través de cada arco.

7.1.1. Solución Manual

Variables: Xij=Cantidad de flujo que va del nodo i al nodo j (unidades) Función objetivo: Min Z= 4X12 + 4X13 + 2X23 + 2X24 + 6X25 + X34 + 3X35 + 2X45 Sujeto a: ● ●

X12 + X13 = 20 -X46 - X56 = -20

Capacidad de arco ● ● ● ● ● ● ● ●

X12