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 con
ecta dos nodos.
ecta 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 llamadacapacidad 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 Xjivariables. 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:
Min Z = 15X12+10X13+8X32 +4X35+6X24+17X27+4X45+5X47+2X56+6X67
Entra al nodo es +
Sale del nodo es -
|
S.a.:
Nodo 1: X12+X13 = 1
Nodo 2: X12+X32-X24-X27 = 0
Nodo 3: X13-X32-X35 = 0
Nodo 4: X24-X47-X45 = 0
Nodo 5: X35+X45 – X56 = 0
Nodo 6: X56-X67 = 0
Nodo 7: X27+X47+X67 = 1
| Nodo | Ruta |
Distancia o Costos, $
|
| Origen, 1
2
3
4
5
6
7
| 1
1 – 2
1 – 3
1 – 2 – 4
1 – 3 – 5
1 – 3 – 5 – 6
1 – 3 – 5 – 6 – 7
| 0
15
10
21
14
16
22
|
El camino más corto del origen al nodo 7 es un total de 22 unidades de longitud.
Te invito a realizar los problemas de Ruta Corta, siguientes:
Problema 1:
- El Supermercado la Colonia central tiene 13 establecimientos al que distribuye sus productos en Managua. El cuadro siguiente muestra las distancias:
| O | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | |
| Origen, O | 5 | 8 | 6 | |||||||||||
| 1 | 5 | 7 | 10 | 12 | ||||||||||
| 2 | 8 | 7 | 4 | 3 | 11 | |||||||||
| 3 | 6 | 7 | ||||||||||||
| 4 | 3 | 6 | ||||||||||||
| 5 | 12 | 9 | 11 | 8 | ||||||||||
| 6 | 7 | 3 | 9 | |||||||||||
| 7 | 9 | 3 | 12 | |||||||||||
| 8 | 6 | 4 | 3 | 7 | 4 | |||||||||
| 9 | 8 | 3 | 7 | 6 | ||||||||||
| 10 | 9 | 4 | 5 | 6 | ||||||||||
| 11 | 12 | 6 | 5 | 3 | 10 | |||||||||
| 12 | 6 | 3 | 12 | |||||||||||
| 13 | 10 | 12 |
Si el nodo de origen es 1 y nodo final es 1. Se solicita:
1) Formular como Programación lineal.
2) Realizar el diagrama
3) Se solicita encontrar las distancias más cercanas para llegar a cada local en kilómetros.
Problema 2:
Una compañía arrendadora de automóviles está desarrollando un plan de reemplazo de su flotilla para los próximos cinco años. Un automóvil debe de estar en servicio cuando menos un año antes de que se considere ser reemplazado. La tabla resume el costo de reemplazo por unidad (en miles de unidades monetarias) como función del tiempo y el número de años en operación. El costo incluye la compra, prima del seguro, operación y mantenimiento.
Año
|
1
|
2
|
3
|
4
|
5
|
1
|
5.0
|
6.4
|
7.8
|
13.7
| |
2
|
5.3
|
6.2
|
7.1
| ||
3
|
5.7
|
7.1
| |||
4
|
5.9
|
Se solicita:
1) Dibujar el diagrama
2) Proporcionar la distancia más corta a cada nodo en la red, junto con su ruta.
Ver El árbol de Comunicación mínima para la clase del día 23 de mayo del 2013
Ver el Algorimo del Flujo máximo
No hay comentarios. :
Publicar un comentario