Grafos

Un grafo no dirigido G (G = V, E) consiste en un conjunto V de vértices (o nodos) y un conjunto E de lados (ramas o enlaces) tales que cada lado e ∈ E está asociado a un par (1 o 2).

• 1. Grafo no dirigido: Un par no ordenado de vértices V y w. Si un lado e está asociado a un único par de vértices v y w, entonces e = (v, w) o e = (w, v).
• 2. Grafo dirigido: Un par ordenado de vértices. Si un lado e está asociado a un par ordenado único de vértices v y w, se escribe e = (v, w).

1 y 2 son incidentes en v y w, y viceversa, y también son vértices adyacentes.

Terminología en Grafos

• Nodo (vértice): Un círculo de una red utilizado para representar una planta, almacén o tienda.
• Nodo de suministro: Nodo desde el cual los productos se van a enviar.
• Nodo de demanda: Va a recibir los productos para cumplir con una demanda conocida.
• Nodo de transbordo: 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.
  • 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.

Representación de un Grafo

• Matemáticamente como una matriz, una lista enlazada, un árbol.
• Representación matricial como una matriz de adyacencia, una matriz de costo (beneficio).

Matrices en Grafos

• Matriz de adyacencia: Para un grafo G, es una matriz A de dimensión N x N donde A[i, j] es verdadero si, y solo si, existe un arco que va del vértice i al vértice j. En ausencia de arco directo se representa generalmente por 0.
• Matriz de costo: Para un grafo G etiquetado, es una matriz C de dimensión N x N, donde A[i, j] es el costo (valor de la etiqueta) si, y solo si, existe un arco que va del vértice i al vértice j. En ausencia de arco directo se representa generalmente por ∞ (costo extremadamente alto, para la simulación se hace uso de un valor fuera de contexto).
• Para un grafo no dirigido, tanto la matriz de adyacencia como la de costo son simétricas. A[i, j] = A[j, i].

Modelos de Optimización en Redes

Modelo de Transbordo con Capacidad

a) Expresar el problema como una programación lineal (PL). (Variable de decisión, 1: min Z = n° total que se enviará a través del arco (i, j) = se tiene o necesita).

Modelo de la Ruta más Corta

Dos casos pueden representar la red: a) grafo dirigido y b) no dirigido (cualquiera corresponde a los grafos ponderados (con peso)).

Algoritmo para Grafo no Dirigido

1. Considerar todos los nodos conectados directamente con el origen [distancia, nodo].
2. Escoger el que tenga la distancia menor y marcar como permanente (los no permanentes se etiquetan como temporales o sin etiqueta).
3. Las etiquetas permanentes indican la distancia más corta entre el nodo origen a cada nodo de la red.

Ruta más Corta (Grafo Dirigido): Algoritmo de Dijkstra

b) El algoritmo de Dijkstra opera a partir de un conjunto S de vértices cuya distancia más corta desde el origen ya es conocida.

Para conocer el camino hay que incluir otra matriz P de vértices, tal que P_v contenga el vértice inmediato anterior a V en el camino más corto. Se asigna a P_v el valor inicial 1 para todo P_v ≠ 1.

Árbol de Extensión de Costo Mínimo

Es un grafo que tiene sus n nodos (vértices) conectados con n – 1 arcos (aristas), no existiendo ciclos (caminos cerrados).

1. Se selecciona cualquier nodo y se conecta al nodo más cercano a este.
2. Los empates se deciden arbitrariamente, indican que existen soluciones alternativas para la construcción.

Algoritmo

0. Se construye una tabla de costos totales.
1. Se comienza con cualquier nodo, se designa este nodo como conectado y se pone una marca al lado de la fila correspondiente, se tacha el índice de la columna que corresponde a él.
2. Los empates se deciden arbitrariamente, indican que existen soluciones alternativas para la construcción.
3. Considerando todas las filas marcadas, buscar el mínimo en las columnas cuyo índice aún no ha sido tachado, encerrarlo en un círculo. Ahí se designa el nuevo nodo conectado. Se repite hasta que todos los nodos estén conectados.
4. Los nodos en círculos identifican el árbol.

Problema del Flujo Máximo

Hay un solo nodo fuente (nodo de entrada) y un solo nodo destino (nodo salida), y el resto son nodos de transbordo. El problema consiste en encontrar la máxima cantidad de flujo total (petróleo, gas, efectivo, mensaje, tránsito, etc.). La cantidad de flujo por unidad de tiempo en cada arco está limitada por las restricciones de capacidad. Se puede representar como una red dirigida y conexa.

Para cada nodo interno debe cumplirse que: flujo que sale del nodo = flujo que entra al nodo.

La cantidad de flujo a lo largo de dicho recorrido es factible si:

1. No excede la capacidad de ningún arco del camino.
2. Con excepción de los nodos 1 y 6, el flujo en cada nodo debe satisfacer la condición de conservación.

La cantidad máxima que puede fluir desde la fuente a lo largo de un camino es igual a la menor de las capacidades de los arcos de dicho camino.

Reglas para Asignar Flujos

1. Se reduce la capacidad en la dirección del flujo (cantidad de flujo).
2. Se aumenta la capacidad en sentido opuesto (cantidad de flujo).

Modelo de Transporte

Técnica que busca determinar un programa de transporte de productos o mercancías desde los orígenes hasta los diferentes destinos posibles.

Objetivo

Busca determinar la cantidad que debe ser enviada desde cada origen a cada destino para satisfacer los requerimientos de demanda y abastecimiento de materiales a un costo mínimo.

Aplicaciones

• Control y diseño de plantas de fabricación.
• Determinar zonas o territorios de ventas.
• Determinación de centros de distribución o almacenamiento.
• Programación de producción periódica.
• Decisiones de producción en tiempo extra y tiempo normal.
• Problemas de proveedores de empresas manufactureras o de servicios.

Supuestos Considerados como Desventajas

1. Los costos de transporte son una función lineal del número de unidades.
2. Tanto la oferta como la demanda se expresan en unidades.
3. Los costos unitarios de transporte no varían de acuerdo con la cantidad transportada.
4. La oferta y la demanda deben ser iguales.
5. Las cantidades de oferta y demanda no varían con el tiempo.
6. No considerar más efecto para la localización que los costos del transporte.

Un modelo de transporte desbalanceado puede ocurrir por dos situaciones:

• a) Suministros en exceso y demandas insuficientes.
• b) Demanda en exceso y suministros insuficientes.

En estas situaciones, agregar un destino (a) o un origen (b) para balancear el modelo C_ij = 0, ya que se convierten las celdas del renglón o columnas ficticias en variables de holgura con contribuciones de cero.

Objetivo: Encontrar el mejor plan. Es aquel que minimiza los costos totales de envíos. Oferta = Demanda.

Pasos para la Formulación del Modelo de Transporte

1. Variable de decisión: X_ij = Número de motores enviados del puerto i a la planta j. i = 1, 2, 3; j = 1, 2, 3, 4.
2. Función objetivo: min Z = 12X₁₁ + 13X₁₂ + … (12 = costo de transporte; 1 = i (columna), 1 = j (fila)).
3. Restricciones:
   • a) Oferta: Cantidad de elementos enviados (columnas): X₁₁ + X₁₂ + X₁₃ + X₁₄ ≤ 500, X₂₁ + X₂₂ + … ≤ 700, …
   • b) Demanda: Filas o plantas donde reciben: X₁₁ + X₂₁ + X₃₁ ≥ 400, …

Tipos de Soluciones

Regla de la Esquina Noroeste (MEN)

Se empieza en la esquina noroeste y se asigna a la demanda lo máximo que se pueda en el primer renglón. Si se agota la oferta, se baja una columna y se asignan las faltantes de la fila. Una vez completo, se pasa inmediatamente al costado del último rellenado y se asigna lo que se pueda desde ese punto. Si falta para completar la demanda, se baja uno… Una vez completa toda la demanda:

Valor de la función objetivo (completar con valores de cuadrados rellenados): X₁₁ * costoX₁₁ + X₁₂ * costoX₁₂ + X₂₂ * costoX₂₂ + … = Z

Método de Aproximación de Vogel (MAV)

Usa información de costo mediante el concepto de costo de oportunidad para determinar una solución inicial factible.

Seleccionar una fila, la ruta más barata y la que le sigue, sacar diferencia entre ambas (penalidad), que es el costo adicional por enviar una unidad desde el origen actual al segundo destino y no al primero. Se repite para cada fila y columna.

Pasos

1. Identificar la fila o columna con máxima penalidad.
2. Colocar la máxima asignación posible a la ruta no usada que tenga menor costo en la fila o columna seleccionada en el punto 1 (los empates se resuelven arbitrariamente).
3. Reajustar la oferta y demanda en vista de esta asignación.
4. Eliminar la columna en la que haya quedado una demanda 0 (o la fila con oferta 0) de consideraciones posteriores.
5. Calcular los nuevos costos de penalidad.

¿La solución es factible? ¿m + n – 1 = 6? Sí, se cumple con la demanda de las plantas y se entregan todos los productos, o sea, demanda = oferta.

Costo: X₁₃ * costoX₁₃ + X₁₂ * costoX₁₂ + … = Z

Método del Costo Mínimo

Asignar la mayor cantidad de unidades a una ruta disponible de costo mínimo.

Algoritmo

1. Dada una tabla de transporte.
2. Asignar la mayor cantidad de unidades a la variable (ruta) con el menor costo unitario de toda la tabla.
3. Tachar la fila o columna satisfecha.
4. Ajustar oferta y demanda de todas las filas y columnas.
5. Si hay más de una fila o columna no tachada, repetir puntos 2, 3, 4.

Costo: X₁₁ * costoX₁₁ + X₁₃ * costoX₁₃ + … = Z

Comparación de Resultados

Método, rutas y costo: MEN; cantidad de rutas; Z, MAV; cantidad de rutas; Z, MCM; …

Rutas = n° cuadritos rellenos, Costo = valor calculado en cada método de Z

Conclusión: Los tres métodos entregan soluciones básicas factibles, pero ninguna asegura que sea óptima.

Para sacar el óptimo se ocupa el método de pasos secuenciales a partir de uno de los métodos anteriores.

Planeación de Proyectos

Objetivo: Controlar la eficiencia y gasto económico de este.

• Proyectos: Poseen un principio y un final, es un conjunto de tareas que deben ser completadas en un tiempo determinado y a un mínimo costo.
• Características: Combinación de actividades, relación secuencial entre actividades, preocupación por el tiempo, preocupación por los recursos.
• Planeación: Requiere desglosar el proyecto en actividades, estimar recursos, tiempo e interrelaciones entre actividades.
• Programación: Requiere detallar fechas de inicio y terminación.
• Control: Requiere información sobre el estado actual y analiza posibles trueques cuando surgen dificultades.

Método de la Ruta Crítica (CPM)

Los tiempos se conocen con relativa certeza.

Herramientas: Gráfica de Gantt, modelo de redes (PERT o CPM).

Ruta crítica: Conjunto de actividades que no tiene tiempo de holgura y que conectan el nodo inicial con el nodo final. La suma del tiempo de la ruta crítica corresponde al mínimo tiempo del proyecto.

• Tiempo de holgura (h = l_f – e_f): Cantidad de tiempo en que pueden retrasarse.
• Tiempo de inicio temprano (e_s): Es el tiempo más temprano posible para iniciar una actividad.
• Tiempo de terminación temprano (e_f): El tiempo de inicio temprano más el tiempo para completar la actividad.
• Tiempo de terminación más lejana (l_s): El tiempo más tardío en que se puede completar la actividad sin afectar la duración total del proyecto.
• Tiempo de inicio más lejano (l_f): El tiempo de terminación más lejano de la actividad anterior menos la duración de la actividad.

Es la ruta más larga a través de la red, determina la longitud del proyecto. Todo proyecto tiene al menos una ruta crítica. Existen proyectos con más de una ruta crítica.