Problema De La Mochila Y Ruta Mas Corta.docx

CAMPUS CD. ALEMAN

CADENA DE SUMINISTRO

“PROBLEMA DE LA MOCHILA, MÉTODO DE LA RUTA MÁS CORTA”.

INGENIERÍA EN GESTIÓN EMPRESARIAL-D07

PRESENTA:

MILAGROS ISABEL USCANGA MUÑOZ

DOCENTE:

I.I MARÍA DEL PILAR GARCÍA HERRERA

CD. ALEMÁN, VER. A 10/09/2018

INTRODUCCIÓN

El presente trabajo está diseñado de forma práctica y sencilla para entender. El problema de la mochila que es un problema de optimización combinatoria, es decir, que busca la mejor solución entre un conjunto finito de posibles soluciones a un problema. Modela una situación análoga al llenar una mochila, incapaz de soportar más de un peso determinado, con todo o parte de un conjunto de objetos, cada uno con un peso y valor especifico. Pero también para conocer el algoritmo la ruta más corta consiste, en una modalidad de problemas de redes, en la cual se debe determinar el plan de rutas que genere la trayectoria con la mínima distancia total, que una un nodo fuente con un nodo destino, sin importar el número de nodos que existan entre estos.

EJERCICIO 1 EJEMPLO DE LA MOCHILA (PROGRAMACIÓN DINÁMICA) Una persona debe elegir que objetos debe llevar su mochila, los artículos que tienen son los siguientes: A, B, C, E, F; el volumen de cada objeto es: 1, 2, 4, 5, 7, 8; y el valor (beneficio) de cada objeto es: 2, 5, 6, 10, 13, 16. La capacidad total o volumen de la mochila es de 8 unidades y se espera llevar los objetos que maximicen el valor. GANANCIAS- VOLUMEN. VALOR

VOLUMEN

OBJETOS

ETAPAS

0

0

1

2

3

0

0 2 (A) 2 (A) 2 (A) 2 (A) 2 (A) 2 (A)

0 2 (A) 5 (B) 5 (B) 5 (B) 5 (B) 5 (B)

0 2 (A) 7 (A,B) 7 (A,B) 7 (A,B) 7 (A,B) 7 (A,B)

1

A

1

2

0

2

B

2

5

0

3

C

4

6

0

4

D

5

10

0

5

E

7

13

0

6

F

8

16

0

4

5

6

7

8

0 0 0 0 0 2 2 2 2 2 (A) (A) (A) (A) (A) 7 7 7 7 7 (A,B) (A,B) (A,B) (A,B) (A,B) 7 8 11 13 13 (A,B) (C,A) (B,C) (A,B,C) (A,B,C) 7 10 12 15 17 (A,B) (D) (A,D) (B,D) (A,B,D) 7 10 12 15 17 (A,B) (D) (A,D) (B,D) (A,B,D) 7 10 12 15 17 (A,B) (D) (A,D) (B,D) (A,B,D)

Objetos que maximizan las ganancias: (A, B, D).

EJERCICIO 2 Elabora un ejercicio para una mochila de capacidad de 7 unidades cuyos objetos son: C, D, E, F, G. Cuyos beneficios son: 2, 5, 10, 14, 15. Y sus volúmenes son: 1, 3, 4, 5, 6. Ganancias- Volumen

VALOR

VOLUMEN

OBJETOS

ETAPAS

0

1

2

0 2 (C) 2 (C) 2 (C) 2 (C) 2 (C)

0 2 (C) 2 (C) 2 (C) 2 (C) 2 (C)

0 1

C

1

2

0 0

2

D

3

5

0

3

E

4

10

0

4

F

5

14

0

5

G

6

15

0

Objetos que maximizan las ganancias: (C, G).

3

4

5

6

7

0 0 0 0 0 2 2 2 2 2 (C) (C) (C) (C) (C) 5 7 7 7 7 (D) (C,D) (C,D) (C,D) (C,D) 5 10 12 12 15 (D) (E) (C,E) (C,E) (D,E) 5 10 14 16 16 (D) (E) (F) (C,F) (C,F) 5 10 14 16 17 (D) (E) (F) (C,F) (C,G)

EJERCICIO 3 MÉTODO DE LA RUTA MAS CORTA

55,4

40,3 2

1 0,-

30

15

3 30,1

Ruta más corta del Inicio al 5 -1° Ruta

1, 3, 5.

-2° Ruta

1, 3, 4, 5.

4

60

5 90,3 90,4

EJERCICIO 4

7,A

4,O A

6

4

D

6,O O

10,F

3

C

2

G

17,G

12,G

8,C F

5

H

0,-

1

B 3,O

6

5 9,B 9,F

Ruta más corta de O a T

-1° Ruta

I

E

O, C, F, G, T.

14,E

8

T

EJERCICIO 5

5,C

2,A 3 C

F

2 3 2

0,-

3

A

H 3,B

2,A

2

1

B

D

1

5 7 0,-

8,D 3

G E

Ruta más corta de A a H

-1° Ruta

A, C, F, H.

E 3,G

8,F

EJERCICIO 6

3,O

7,A 4

A

3

D

6

1 4,A

O

6,F 2

C

T

4

F

10,F

0,- 2

2

3

3

5

B

E 4

2,O

Ruta más corta de O a T

-1° Ruta

O, A, C, F, T.

6,C