• Author / Uploaded
• elviracis

Citation preview

Investigación Operativa II

Marlon Villa Villa

UNIVERSIDAD NACIONAL DE CHIMBORAZO FACULTAD DE CIENCIAS POLÍTICAS Y ADMINISTRATIVAS CARRERAS DE CONTABILIDAD Y AUDITORIA INVESTIGACIÓN OPERATIVA II Nombre: Elvira Cislema Semestre: Sexto “A”

MODELOS DE REDES •

El problema del transporte y el problema de asignación, forman parte de un tipo más general de modelos, conocidos como modelos de red.

•

Los modelos de red son aplicaciones muy importantes para la logística y la distribución en la administración,

además de tener múltiples aplicaciones en ingeniería

ycomputación. •

Un modelo de red es un modelo de transbordo con capacidades, el cual puede adoptar diversas formas, como el modelo de la ruta más corta y el modelo del flujo máximo y mínimo, el problema de árbol de alcance mínimo, método de camino crítico, entre otras aplicaciones de la planeación financiera y de producción.

•

La principal característica de un modelo de transbordo con capacidades es que es una red donde las ofertas están en los puntos de origen específicos, las demandas en los puntos de destino específicos y las alternativas de embarque se ofrecen por medio de los nodos intermedios, de manera que siguen rutas con capacidades definidas desde los orígenes hasta los destinos.

Terminología de redes A continuación se presenta un diagrama de red y susprincipales componentes.

Unach

2.014

Investigación Operativa II



Marlon Villa Villa

Las flechas se conocen como arco o rama de la red. Generalmente el arco (flecha) de un punto A a B se designa (A, B)



Los puntos/elementos del modelo se conocen como nodos de la red.

En el nodo de la red comúnmente encontrarás un número con un signo positivo o negativo, el cual denota la oferta (+) y la demanda o requerimientos (-) del nodo.  

Una ruta es una secuencia de arcos distintos que conectan a dos nodos. En la red podemos observar las diferentes rutas que puede tomar el flujo por medio de los arcos o ramas dela red.

Consideraciones importantes: • Las flechas/líneas de una sola dirección son arcosdirectos. • Las líneas con flujo para ambas direcciones son arcosindirectos. • Una red que tiene solamente arcos directos es una reddirecta. • Una red que tiene arcos en ambas direcciones es unared indirecta. PROBLEMA. El gerente de distribución de una empresa distribuye tractores en cinco provincias. El gerente tiene 10 aparatos en la provincia

Unach

1, estos tractores deben ser

2.014

Investigación Operativa II

Marlon Villa Villa

enviados a las provincias 3 y 4 que demandan 3 y 7 tractores respectivamente. Elabore el diagrama de red, establezca las capacidades y los costos agregados, formule el problema, construya la matriz de incidencia (nodo – arco) y establezca la tabla de transporte. DIAGRAMA DE RED

-3

+10 -7

CAPACIDADES Y COSTOS AGREGADOS

C23 C12 C12 U12

C34 U23

C43

C24

C53 U24

C25

C54

U53

U54

U25

FORMULACIÓN DEL PROBLEMA Min Z=C12X12+C23X23+C24X24+C25X25+C34X34+C43X43+C53X53+C54X54 Sujeto a:

Unach

2.014

Investigación Operativa II

Marlon Villa Villa

+X12

=10

-X12+X23 +X24 +X25

=0

-X23

+X34

-X24

– X43 – X53

=-3

-X34 + X43 -X25

+X53

-X54

=-7

+X54

=0

0 ≤ Xij ≤ Uij, Paratodos los arcos (i,j) que pertenezcan a la red MATRIZ DE INCIDENCIA (NODOS – ARCOS) ARCOS NODO (1,2)

(2,3)

(2,4)

(2,5)

(3,4)

(4,3)

(5,3)

(5,4)

VALOR

1

+1

0

0

0

0

0

0

0

10

2

-1

1

1

1

0

0

0

0

0

3

0

-1

0

0

1

-1

-1

0

-3

4

0

0

-1

0

-1

1

0

-1

-7

5

0

0

0

-1

0

0

1

1

0

Unach

2.014

Investigación Operativa II

Marlon Villa Villa

EL PROBLEMA DE LA RUTA MAS CORTA Recordemos algunos conceptos básicos como son: GRAFO. Es una serie de nodos unidos por arcos, ramas o aristas Red.Es una grafo con algún tipo de flujo en sus ramales. Ejemplo: Eléctrica, transporte. Ruta: Una ruta corresponde a los nodos que constituyen una cadena, en el siguiente caso [1, 4, 7].

Ciclo: Un ciclo corresponde a la cadena que une a un nodo con sigo mismo, si los arcos tienen la misma dirección se conoce como circuitos, en el siguiente ejemplo el ciclo está compuesto por la cadena [4-2, 2-5, 5-7, 7-4].

Unach

2.014

Investigación Operativa II

Marlon Villa Villa

Ramal orientado: Un ramal o arco orientado es aquel que tiene un sentido determinado, es decir que posee un nodo fuente y un nodo destino.

Gráfica orientada o dirigida: Una gráfica orientada es aquella en la cual todos sus ramales se encuentran orientados.

Árbol: Un árbol es una gráfica en la cual no existen ciclos, como el siguiente ejemplo.

Unach

2.014

Investigación Operativa II

Marlon Villa Villa

Árbol de expansión: Un árbol de expansión es aquel árbol que enlaza todos los nodos de la red, de igual manera no permite la existencia de ciclos.

Bosque.Es una gráfica sin ciclos, se considera también comoun conjunto de árboles. Arborescencia. Es un árboldirigido con un nodo llamadoraíz

.

.

EL PROBLEMA DE LA RUTA MAS CORTA Los problemas conocidos como problemas del camino mínimo o camino más corto, tratan como su nombre indica de hallar la ruta mínima o más corta entre dos puntos. Este mínimo puede ser la distancia entre los puntos origen y destino o bien el tiempo transcurrido para trasladarse desde un punto a otro. Se aplica mucho para problemas de redes de comunicaciones.

Unach

2.014

Investigación Operativa II

Marlon Villa Villa

Este tipo de problemas pueden ser resueltos por el método del Simplex, sin embargo existen otros métodos más eficientes como por ejemplo el algoritmo de Dijkstra o el de Bellman-Ford. EL PROBLEMA DEL ÁRBOL EXPANDIDO MÍNIMO La tarea consiste en construir un árbol que conecte todos los nodos de la red con un costo total mínimo El algoritmo que nos permite resolver este tipo de problemas es el ALGORITMO GLOTÓN y se puede hacer de dos formas: el método gráfico y el método Tabular.

MÉTODO GRÁFICO. 1. Empiece en cualquier nodo. Seleccione el arco más barato que parta de ese nodo. Este es su primer enlace. Forma un segmento de conexión entre dos nodos. Los nodos restantes se llaman NODOS DESCONECTADOS. 2. Considere todos los arcos que parten del segmento de conexión a los nodos desconectados. Seleccione el más barato como enlace. Si hay empates rompa de manera arbitraria. Esto agrega un nuevo nodo al segmento de conexión. Repita este paso hasta que todos los nodos estén conectados lo cual requiere n -1 pasos. MÉTODO TABULAR. 1. Comience con cualquier nodo, se designa este nodo como conectado y se coloca un V al lado del renglón correspondiente a este nodo. Se tacha el índice de la columna que corresponde a él. 2. Considerando todos los renglones que tienen V, busque el valor mínimo en las columnas cuyo índice aún no haya sido tachado y se encierra ese valor en un círculo. Se rompe arbitrariamente los empates. La columna que contenga a ese elemento encerrado en un círculo designa al nuevo nodo conectado. Se tacha el índice de esta columna y se

Unach

2.014

Investigación Operativa II

Marlon Villa Villa

coloca una marca en el renglón correspondiente a este nodo. Se repite este paso hasta que todos los nodos sean conectados. 3. Una vez que todos los nodos hayan sido conectados, se identifica el árbol expandido mínimo mediante los elementos circundados. EL PROBLEMA DEL FLUJO MÁXIMO. En este problema hay un solo nodo FUENTE( origen, entrada) y un solo nodo DESTINO ( sumidero, salida), El problema consiste en determinar el máximo flujo que se puede enviar desde el nodo fuente al nodo destino, teniendo en cuenta las capacidades kij sobre el flujo de cada arco (i,j) y que el flujo se debe conservar.Se utiliza para saber cuál es la cantidad máxima de vehículos, peatones, líquidos o llamadas telefónicas que pueden entrar y salir del sistema, para reducir los embotellamientos entre ciertos puntos de partida y destino en una red. El único requerimiento en ellos es que para cada nodo (que no sea la fuente o el destino) la relación de equilibrio debe cumplirse: flujo que sale = flujo que entra La cantidad de flujo a lo largo de dicho recorrido es FACTIBLE si: 1. No se excede la capacidad de ningún arco del camino. 2. A excepción de los nodos de entrada y salida se debe cumplir la condición de conservación: flujo que sale = flujo que entra ALGORITMO PARA RESOLVER ESTE PROBLEMA. 1. Encontrar un camino que vaya del origen al destino y que tenga capacidad mayor a cero en el sentido deseado.

Unach

2.014

Investigación Operativa II

Marlon Villa Villa

2. Encontrar la rama de menor capacidad (Pf) del camino seleccionado en el paso anterior y programar el envío de dicha capacidad (Pf). 3. Para el camino elegido en el paso 1 reducir la cantidad Pf en las ramas involucradas y aumentar dicha cantidad en el sentido contrario. 4. Repetir el procedimiento desde el paso 1. 5. Si la capacidad final es menor que la capacidad inicial, calcule la diferencia y esta es la cantidad de flujo a través del arco. CORTE. Partición del conjunto de nodos en dos clases ajenas, digamos C1 y Cn donde la fuente está en C1 y el destino en Cn. CAPACIDAD DE CORTE. Considérense todos los arcos que conectan directamente un nodo de C1 a un nodo Cn. La suma de las capacidades de esos arcos, en la dirección C1 – Cn se llama capacidad de corte. TEOREMA DE FLUJO MÁXIMO Y CORTE MÍNIMO. El flujo máximo de cualquier red es igual a la capacidad del corte mínimo.

Unach

2.014