Optimización de Redes y Algoritmos de Investigación Operativa

Ejercicio 1: El Estudiante (Ruta Más Corta / Algoritmo de Dijkstra)

Un estudiante debe ir a la universidad lo más rápido posible, ya que no quiere perder tiempo para su examen. Actualmente su casa está ubicada en A y la Universidad en H. Otros lugares serían: B = Supermercado, C = Feria, D = Iglesia, E = Escuela, F = Bomberos, G = Playa. La tabla a continuación indica los minutos que tomaría ir entre cada lugar (considerar los tramos direccionales).

Pregunta

a) ¿Qué ruta debe tomar el alumno para llegar en el tiempo óptimo?

Ejercicio 2: Preguntas Conceptuales sobre Optimización de Redes

A) Para un problema donde tienes que pasar a buscar a tus amigos a distintos lugares, para llegar a un punto final. ¿Podrías ocupar el problema de Árbol de Expansión Mínima o Ruta Más Corta? ¿Qué problemáticas habría o supuestos tendrían que realizarse en cada caso?

R: Ninguno de los dos algoritmos se ajusta perfectamente, ya que el problema descrito se asemeja más al Problema del Agente Viajero (TSP) o a un Problema de Rutas de Vehículos (VRP), donde se requiere visitar múltiples nodos antes de llegar al destino final. Sin embargo, si se debe elegir el más óptimo en cuanto a distancia recorrida y tiempo total, la Ruta Más Corta es preferible, ya que trazaría una ruta directa hacia el destino final, aunque no garantiza pasar a buscar a todos los amigos en el trayecto.

Problemáticas o Supuestos:

• Árbol de Expansión Mínima (AEM): El AEM busca conectar todos los nodos con el costo mínimo total, pero no garantiza una ruta secuencial ni minimiza el tiempo de viaje entre un origen y un destino específico. Problemáticas: Se podrían formar ciclos (aunque un AEM no los tiene por definición, la aplicación práctica de la ruta sí podría ser ineficiente), se demoraría más y se recorrería más distancia de la necesaria para el objetivo final.
• Ruta Más Corta (Dijkstra): Minimiza el tiempo/distancia desde el origen (casa) hasta el destino (universidad), pero no asegura que se visiten todos los puntos intermedios (amigos). Problemática: No pasaría a buscar a todos los amigos.

B) ¿Qué es un algoritmo? ¿Cuál es la diferencia entre resolver un problema con un algoritmo y realizar la Programación Lineal (PL)? (Responde en tus palabras).

R: Un algoritmo es una metodología o conjunto finito de pasos e instrucciones bien definidas que sigue una secuencia lógica para resolver un problema o realizar un cálculo. La diferencia principal es que resolver un problema con un algoritmo (como Dijkstra o PERT) te entrega el resultado óptimo o factible para la estructura específica de ese problema (redes, secuencias), mientras que resolver un problema con Programación Lineal (PL) es una técnica de modelado matemático que, si se formula correctamente, garantiza encontrar el resultado globalmente más óptimo dentro de un conjunto de restricciones lineales.

C) Si quisiéramos plantear el problema de Árbol de Expansión Mínima como Programación Lineal, ¿Cómo tendría que ser la variable (descríbela: X=?), ¿cuál sería la función objetivo?, ¿cómo sería una restricción? Puedes explicarlo o aplicarlo en un ejercicio simple.

R:

• Variable de Decisión (X): La variable debe ser binaria, indicando si una arista (conexión) forma parte del árbol de expansión mínima. $$X_{ij} = \begin{cases} 1 & \text{si la arista entre el nodo } i \text{ y el nodo } j \text{ es seleccionada} \\ 0 & \text{en caso contrario} \end{cases}$$
• Función Objetivo: Minimizar el costo total de las aristas seleccionadas. $$\text{Minimizar } Z = \sum_{i} \sum_{j} C_{ij} X_{ij}$$ Donde $C_{ij}$ es el costo de la arista entre $i$ y $j$.
• Restricción (Ejemplo de Restricción de Conectividad): Para asegurar que se forme un árbol de expansión mínima, se requiere que el número total de aristas seleccionadas sea igual al número de nodos menos uno ($n-1$), y se deben incluir restricciones de corte para evitar la formación de ciclos y asegurar la conectividad de todos los subconjuntos de nodos.

Ejercicio 3: La Carretera (Problema de Flujo Máximo)

En la ciudad de Iquique existe una red de carreteras de norte a sur que le permite alcanzar un nivel de 15.000 vehículos/hora en el horario de máxima demanda.

Debido a una rotura de cañerías, el alcalde debe cerrar esa carretera y ha visualizado otras rutas alternativas para cruzar la ciudad de norte a sur, la cual incorpora avenidas importantes.

A continuación, se muestra un diagrama con la capacidad máxima de vehículos por cada una de las carreteras a pasar por hora.

Preguntas sobre la Capacidad de la Red

1. ¿Cuál es la cantidad máxima de vehículos que podemos pasar por esta red por minuto? Resuélvelo.
2. ¿Puede la nueva red soportar la capacidad de un flujo de 15.000 vehículos por hora de norte a sur?
3. Plantee este problema utilizando la Programación Lineal (PL) (solo plantearlo, NO resolver).
4. ¿Cuánto es el flujo de vehículos que se debe canalizar por cada calle por hora?
5. ¿Qué carretera podrías aumentar su capacidad para mejorar la capacidad total en este sistema? ¿Por qué?

Ejercicios Adicionales de Modelado de Redes

Ruta Más Corta (Ejemplo Inventado)

Árbol de Expansión Mínima (Diseño de Rutas en Fortnite)

Eres el diseñador de rutas en la isla del Fortnite. Debes conectar todas las zonas principales del mapa con caminos, de forma que todas queden conectadas (directa o indirectamente) y que el costo total de construcción sea el mínimo.

Zonas:

1. Pico Polar
2. Parque Placentero
3. Señorío de la Sal
4. Balsa Botín
5. Ciudad Comercio
6. Caserío Colesterol
7. Costa Creciente
8. Bosque Frenético

Costos en pesos ($):

• 1-2 = 2
• 1-3 = 4
• 1-4 = 5
• 2-5 = 9
• 2-4 = 2
• 2-6 = 7
• 3-4 = 1
• 3-7 = 4
• 4-5 = 8
• 4-6 = 4
• 4-7 = 3
• 4-8 = 3
• 5-6 = 9
• 5-8 = 10
• 6-8 = 5
• 6-7 = 1
• 7-8 = 7

Preguntas

A) Crea el diagrama que represente la red, tomando en cuenta los costos.

B) Encuentra la ruta con un costo mínimo y dibuje el diagrama final. Justifique su respuesta.

Enunciado: Carlos se está preparando para un evento deportivo importante y desea optimizar el tiempo de su preparación. Para ello, decide usar el algoritmo PERT-CPM. A continuación, se muestra un listado de las tareas a realizar con su respectivo tiempo. Las actividades predecesoras deben terminarse para recién ejecutar la actividad en cuestión.

Nota importante: Las actividades A y F son paralelas.

Conclusiones del Ejercicio (Respuestas del Estudiante)

D) La actividad en la cual se puede retrasar más es la actividad F y G, debido a sus holguras.

E) Si la actividad B se retrasa en 5 minutos, sí afectará la duración del proyecto, por lo que durará 28 minutos.

Ejercicio 5: Optimización de Procesos con PERT/CPM – Receta de Pastel de Choclo

Después de este 18 de septiembre, usted ha quedado sorprendido de lo rico que es el pastel de choclo, y quiere aplicar todos sus conocimientos ingenieriles para hacerlo en el tiempo más corto posible. Por lo cual, realizará un modelo PERT/CPM de la receta.

Para hacer el pastel debe seguir los siguientes pasos:

• Pica la cebolla en cuadritos muy pequeños (8 minutos).
• Paralelamente, debes picar la carne (15 minutos).
• Luego, en una sartén con el aceite, fríe la carne y la cebolla por unos 5 minutos hasta que se cuezan ligeramente (5 minutos).
• Luego agrega el ají de color, el comino, sal y pimienta al gusto (1 minuto).
• Deja enfriar, llevando el pino al refrigerador. Esto es para que el pino no suelte el jugo antes de tiempo (15 minutos).
• Paralelamente, pela y limpia los choclos (ESTO CONSIDÉRALO ACTIVIDAD INICIAL), cuidando de quitar todos los pelos. Luego desgránalos, rebanándolos con un cuchillo (12 minutos).
• Finalmente, pásalos por una máquina de moler (CHOCLO), y en una olla, pon la mantequilla con una cucharadita de aceite y déjala cocinar (20 minutos).
• Luego agrega un poco de Leche, sal y albahaca (2 min).
• Una vez esté todo listo (CARNE Y CHOCLO, UNIRLOS AQUÍ), aceitas un platillo de greda y pon como base 4 cucharadas de pino (5 minutos).
• Luego cubre todo con una capa de la mezcla de choclo de aproximadamente 2cm (6 minutos).
• Y finalmente pon en el horno a llama alta unos 5 minutos.

Para contestar, suponga lo siguiente: usted tiene más amigos a su alrededor para hacer las actividades paralelas.

Preguntas y Respuestas

a) Cree un diagrama que represente las actividades anteriormente descritas, considere solo las actividades que tienen tiempo indicadas, no agregue más.

b) Encuentre la ruta crítica y la duración mínima de la receta. Para esto, calcule el tiempo de inicio más temprano y más tardío, y tiempo de término más temprano y más tardío de todas las actividades.

c) ¿Cuál es la actividad en la cual me puedo demorar más, sin afectar la duración mínima de la receta?

d) Como soy inexperto, me demoré en realidad 12 minutos en picar la cebolla. ¿Cuál es la duración final de la receta ahora? ¿Es la misma? ¿Sí, no, por qué?

e) Si la preparación la comenzó a las 13:00 horas, y mis invitados llegaran a las 14:00 horas, y justo por mi mala suerte el horno se me echó a perder y tuve que poner la preparación 15 minutos en vez de 5 para poder prepararlos. ¿Alcanzaré a recibir a mis invitados con su plato servido?

Respuestas del Estudiante (Corregidas)

a) y b) Las actividades críticas son: B, C, D, E, I, J y K. La duración mínima del proyecto es 52 minutos.

c) La actividad A es la actividad con mayor margen de demora (holgura): 7 minutos.

d) No, no habría variación en la duración de la receta. Como nos demoramos 4 minutos adicionales (12 min en lugar de 8 min), este retraso es cubierto por el margen de holgura de 7 minutos de la actividad A.

e) Desde las 13:00 hasta las 14:00 horas, hay 60 minutos disponibles. Si la actividad K (Hornear), que es parte de la ruta crítica, se incrementa de 5 a 15 minutos (un aumento de 10 minutos), la duración total del proyecto aumentará de 52 minutos a 62 minutos. Por lo tanto, el plato estará listo a las 14:02 horas, y no se alcanzará a recibir a los invitados con el plato servido a las 14:00 horas.