Unidad 1 Programación Lineal


Introducción a la Teoría de Grafos



Descargar 2,86 Mb.
Página14/22
Fecha de conversión21.06.2017
Tamaño2,86 Mb.
1   ...   10   11   12   13   14   15   16   17   ...   22

2.4.1 Introducción a la Teoría de Grafos

  • Nodo de demanda:
  • Nodo que va a recibir los productos para cumplir con una demanda conocida.
  • Nodo de transbordo:
  • Nodo que recibe productos desde otros nodos para su distribución.
  • Arco (enlace):
  • Línea de una red que conecta un par de nodos. Se le utiliza para representar una ruta válida desde el nodo origen al nodo de distribución.

2.4.1 Introducción a la Teoría de Grafos

  • Arco dirigido:
  • Indica el sentido de movimiento de los productos.
  • Camino:
  • Una secuencia de nodos en una red unidos por arcos (dirigidos o no dirigidos)
  • Trayectoria (lazo):
  • Es un camino cerrado (ciclo) donde el primer nodo es a su vez el último.

2.4.1 Introducción a la Teoría de Grafos

  • Representación de un grafo:
  • Un grafo se puede representar matemáticamente como:
  • a) Una matriz
  • b) Una lista enlazada
  • c) Árbol

2.4.1 Introducción a la Teoría de Grafos (cont.)

  • Matriz de Adyacencia:
  • Para un grafo G, es una matriz A de dimensión NxN, donde A[i,j] es verdadero (1) si, y sólo si, existe un arco que vaya del vértice i al vértice j. En ausencia de arco directo se representa generalmente por 0.
  • Ejemplo: Dado el siguiente grafo encontrar su matriz de adyacencia

2.4.1 Introducción a la Teoría de Grafos (cont.)

  • 2
  • 3
  • 4
  • 1
  • 1
  • 2
  • 3
  • 4
  • 1
  • 1
  • 1
  • 2
  • 1
  • 3
  • 1
  • 4
  • 1

2.4.1 Introducción a la Teoría de Grafos (cont.)

  • Matriz de Costo:
  • Para un grafo G etiquetado, es una matriz C de dimensión NxN, donde A[i,j] es el costo (valor de la etiqueta) si, y sólo si, existe un arco que vaya del vértice i al vértice j. En ausencia de arco directo se representa generalmente por infinito (costo extremadamente alto, para la simulación se hace uso de un valor fuera de contexto).
  • Ejemplo: Dado el siguiente grafo encontrar su matriz de costo

2.4.1 Introducción a la Teoría de Grafos (cont.)

  • 2
  • 3
  • 4
  • 1
  • 1
  • 2
  • 3
  • 4
  • 1
  • 10
  • 15
  • 2
  • 12
  • 3
  • 20
  • 4
  • 5
  • 10
  • 15
  • 20
  • 12
  • 5

2.4.1 Introducción a la Teoría de Grafos (cont.)

  • Para un grafo no dirigido, tanto la matriz de adyacencia como la matriz de costo son simétricas, esto es:
  • A[i,j] = A[j,i]
  • ó
  • C[i,j] = C[j,i]

Ejemplo Introductorio

  • Seymour Miles es el gerente de distribución de Zigwell. Zigwell distribuye sus motores oruga en cinco estados del medio oeste. Por lo regular, Seymour Miles tiene 10 aparatos E-9 in situ en lo que designaremos como local 1. Estos tractores deben ser enviados a los dos locales de construcción más importantes designados como 3 y 4. Se necesitan tres E-9 en el local 3 y siete en el local 4. Debido a itinerarios arreglados con anterioridad, relativos a la disponibilidad de conductores, los tractores solo pueden ser distribuidos de acuerdo con las rutas alternativas que se muestran en el grafo de la figura.
  • La figura tiene un número +10 en el nodo 1, esto significa que hay 10 aparatos E-9 disponibles (oferta). Los indicadores -3 y -7 asociados a los locales 3 y 4, respectivamente, denotan los requerimientos (demandas) de éstos.
  • 1
  • 2
  • 4
  • 5
  • 3
  • c12
  • c34
  • c24
  • c25
  • c54
  • u43
  • c53
  • c23
  • +10
  • -3
  • -7
  • Rutas alternativas para el destino 3
  • 1-2-3, 1-2-4-3, 1-2-5-4-3, 1-2-5-3
  • u12
  • u23
  • u34
  • c43
  • u53
  • c54
  • u25
  • u24
  • Los costos cij son unitarios. Por ejemplo el costo de recorrer el arco (5,3) es c53 por cada tractor.
  • Debido a los acuerdos sostenidos con los conductores, Zigwell debe cambiarlos en cada local que se encuentre sobre la ruta. Las limitaciones en la disponibilidad de conductores ocasionan que haya una cota superior en el número de tractores que pueden recorrer cualquier arco dado.
  • Por ejemplo: u53 es la cota superior o capacidad en el arco (5,3).
  • El problema de Sygmour consiste en encontrar un plan de embarque que satisfaga la demanda y las restricciones de capacidad a costo mínimo.
  • El problema en particular se conoce como modelo de transbordo con capacidades.
  • Expresar el problema como un PL
  • a) Variables de decisión
  • xij = número total de E-9 que se enviarán a través del arco (i,j).
  • = flujo del nodo i al nodo j
  • b) Función Objetivo
  • MIN Z =C12X12+C23X23+C24X24+C25X25+C34X34+C43X43+C53X53+C54X54
  • c) Restricciones
  • s a
  • + X12 = 10
  • - X12+X23+X24+X25 = 0
  • -X23 -X43 -X53 +X34 = -3
  • -X24 +X43 -X34 -X54 = -7
  • -X25 +X53 +X54 = 0
  • Balance
  • de
  • flujo



Compartir con tus amigos:
1   ...   10   11   12   13   14   15   16   17   ...   22


La base de datos está protegida por derechos de autor ©absta.info 2019
enviar mensaje

    Página principal