Importancia de Modelo de Redes

UNIVERSIDAD ANDINA DEL CUSCO
FACULTAD DE CIENCIAS ECONÓMICAS,

ADMINISTRATIVAS Y
CONTABLES
ESCUELA PROFESIONAL DE ECONOMÍA
i IMPORTANCIA DE MODELO DE REDES
ALUMNAS:
 KATERIN PAMELA TACUSI UHUINA
Cusco – Perú
2020
IMPORTANCIA DE MODELO DE REDES
Modelos de redes son utilizados porque pueden aplicarse de forma rápida.
Problemas de programación entera pueden formularse como modelo de redes obteniendo

soluciones enteras sin necesidad de restricciones adicionales, aumentando la eficiencia y
reduciendo el tiempo consumido por los algoritmos clásicos de programación lineal
No importando el tamaño del problema planteando según su estructura matemática se

pueden resolver por pequeños algoritmos.
Terminología
Una red es un conjunto de puntos y líneas que conectan pares de puntos. Los puntos se
llaman nodos o vértices y las líneas se llaman arcos o aristas, estos pueden tener una
dirección asociada, en este caso se denominan arcos dirigidos.
Flujo es el valor que se le asigna a un arco que
conecta dos nodos.
Para nombrar el arco se pone primero el nodo de
donde viene y luego el nodo hacia dónde va.
Por ejemplo, si el flujo sólo va desde el nodo C

hacia el nodo D, entonces el arco se llama CD y no
DC.
Una trayectoria entre 2 nodos es una sucesión de arcos distintos que conectan estos nodos.
Por ejemplo, una trayectoria que conecta al nodo A con el nodo G es AC-CE-EG.
Una trayectoria dirigida desde el nodo i al nodo j es una sucesión de arcos cuya dirección es
hacia el nodo j, de manera que el flujo del nodo i al nodo j a través de esta trayectoria es
factible
Una trayectoria no dirigida del nodo i al nodo j es una sucesión de arcos cuya dirección ( si
la tiene) puede ser hacia o desde el nodo j.
Ciclo es una trayectoria que comienza y termina en un mismo nodo

Ciclo dirigido cuando está formado por una trayectoria dirigida
Ciclo no dirigido cuando la trayectoria que lo conforma es no dirigida.
Ejemplo real de una modelo de redes es el mapa de carreteras en el departamento de

Managua.
La cantidad máxima de flujo que puede circular en un arco dirigido es llamada capacidad
del arco.
El nodo que tiene la propiedad de que su flujo que sale es mayor que el flujo que entra en el
se le llama nodo fuente o nodo de origen. Por el contrario, si su flujo que sale es menor que
el flujo que entra a el se le llama nodo demanda o nodo destino. Si el flujo que entra es
igual al flujo que sale, entonces se le llama nodo de trasbordo o nodo intermedio.
Árbol es una serie de nodos conectados que no contiene ciclos.
Árbol de expansión es un árbol que conecta todos los nodos de la red contiene n-1 arcos,
donde n es el número de nodos.
El Problema del Camino más Corto

Objetivo: Determinar la mejor manera de cruzar una red para encontrar una forma
económica para dirigirse desde un origen a un destino dado.
Suponga que en una red existen m nodos y n arcos (bordes) y un costo Cij asociado con
cada arco (i a j) en la red.
El problema del camino más corto (CC) es encontrar la vía más cercana (menor costo)
desde el nodo de comienzo 1 hasta el nodo final m. El costo del camino es la suma de los
costos de cada arco recorrido.
Defina las variables binarias Xij, donde Xij =1 si el arco (i a j) es sobre el CC y Xij = 0 de lo
contrario. Existen dos nodos especiales llamados origen y destino.
En la red siguiente, varios costos son asignados para el camino que va de un nodo a otro.
Por ejemplo, el costo de ir desde el nodo 2 al 4 es 6.
La función objetivo considera los costos de moverse de un nodo a otro, o de un origen a

un destino. Las restricciones están divididas en tres grupos:
1) La restricción del nodo de origen dice que debe dejar el nodo 1 para ir al 2 o 3.
2) La restricción del nodo intermedio dice que si siempre que se dirija a un nodo
usted deberá dejar ese nodo.
3) El nodo de destino es similar al nodo de origen dado que se puede alcanzar este
nodo solo desde los nodos vecinos.
Considere la siguiente red dirigida (para una red indirecta, haga que los arcos estén
dirigidos en ambas direcciones, luego aplique la misma formulación. Note que en este caso
usted tiene Xij y Xji variables. El objetivo es encontrar el camino más corto desde el nodo
1al nodo 7. La red sería:
Para encontrar la función objetivo para los costos se plantea:

Importancia de Modelo de Redes

Cargado por

Copyright:

Formatos disponibles

Importancia de Modelo de Redes

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Importancia de Modelo de Redes

Cargado por

Copyright:

Formatos disponibles

UNIVERSIDAD ANDINA DEL CUSCO

FACULTAD DE CIENCIAS ECONÓMICAS,

i IMPORTANCIA DE MODELO DE REDES

 KATERIN PAMELA TACUSI UHUINA

Modelos de redes son utilizados porque pueden aplicarse de forma rápida.

Problemas de programación entera pueden formularse como modelo de redes obteniendo

No importando el tamaño del problema planteando según su estructura matemática se

Por ejemplo, si el flujo sólo va desde el nodo C

Ciclo es una trayectoria que comienza y termina en un mismo nodo

Ciclo no dirigido cuando la trayectoria que lo conforma es no dirigida.

Ejemplo real de una modelo de redes es el mapa de carreteras en el departamento de

El Problema del Camino más Corto

La función objetivo considera los costos de moverse de un nodo a otro, o de un origen a

También podría gustarte