La administración de Seervada Park

Ejemplo # 1

La administración de Seervada Park necesita determinar los caminos bajo los cuales se deben tender las líneas telefónicas para conectar todas las estaciones con una longitud mínima de cable. Se describirá paso a paso la solución de este problema con base en los datos que se dan en la siguiente figura:

nodos y distancias para el problema se resumen enseguida, en donde las líneas delgadas, ahora representan ligaduras potenciales.

En forma arbitraria, se selecciona el nodo O para comenzar. El nodo no conectado más cercano a O es el nodo A. Se conecta el nodo A al nodo O.

El nodo no conectado más cercano a cuales quiera de los nodos O o A es el nodo B (más cercano a A). Se conecta el nodo B al nodo A

El nodo no conectado más cercano a O, A o B es el nodo C (mas cercano a B). Se conecta el nodo C al nodo B.

El nodo no conectado más cercano a O, A, B o C es el nodo E (más cercano a B). Se conecta el nodo E al nodo B.

El nodo no conectado más cercano a los nodos O, A, B, C o E

es elnodo D (más cercano a E). Se conecta el nodo D al nodo E

El único nodo no conectado es el nodo T. está más cerca del nodo D. Se conecta el nodo T al nodo D

n Nodos resueltos conectados directamente a nodos no resueltos Nodo no resuelto mas cercano conectado Distancia total involucrada n-esimo nodo mas cercano Distancia mínima Ultima conexión

1 O A 2 A 2 OA

2-3 O

A C

B 4

2+2=4 C

B 4

4 OC

AB

4 A

B

C D

E

E 2+7=9

4+3=7

4+4=8

E

7

BE

5 A

B

E D

D

D 2+7=9

4+4=8

7+1=8

D

D

8

8

BD

ED

6 D

E T

T 8+5=13

7+7=14 T 13 DT

LA RUTA REQUIERE 13 KM

EJEMPLO #2

Sunco Oil quiere enviar (por hora) la máxima cantidad de petróleo por un oleoducto desde el nodo so al nodo si, el petróleo tiene que pasar por algunas, o por todas, las estaciones 1, 2 y 3. Los arcos de la Fig. 6 representan oleoductos de diferentes diámetros. En la Tabla 5 se muestra el máximo número de barriles de petróleo (millones de barriles por hora) que se pueden bombear por cada arco. Cada uno de estos números se llama capacidad de arco. Plantee un PL que se pueda utilizar para determinar el máximo número de barriles de petróleo que se pueden mandar de so a si.

Arco Capacidad

(So,1) 2

(So,2) 3

(1,2) 3

(1,3) 4

(3,Si) 1

(2,Si) 2

Variables de decisión:

xij= millones de barriles de petróleo que pasarán por hora por el arco i,j del oleoducto.

Para que un flujo sea factible, tiene que ocurrir:

• 0<= flujo a través de cada arco <= capacidad del arco

• Flujo que entra en el nodo i = Flujo que sale del nodo i (salvo en nodos 1 y m)

• X0= cantidad de petróleo que entra en el pozo.

Formulación:

Maximizar z =x0

s.a: Restricciones de capacidad:

...