D1 · Decision Mathematics 1

Matemáticas de Decisión 1 (D1, examen WDM01/01, 1 hora 30 minutos, 75 puntos, primera evaluación Junio 2019) es la opción discreta del IAL: P1–P2 se asumen, y cada método es un ALGORITMO — una lista finita de instrucciones exactas. No hay entradas en el folleto de fórmulas más allá de los básicos: los puntos son por ejecutar procedimientos con precisión y presentar resultados en el formato requerido. Esta referencia cubre algoritmos de ordenamiento y empaquetado, árboles de expansión mínima, caminos más cortos, problemas del cartero chino y del viajante de comercio, análisis de ruta crítica y programación lineal. Reglas de casa para respuestas de algoritmos:

Reglas de casa para respuestas de algoritmos:

El ordenamiento burbuja compara elementos adyacentes, intercambiando pares desordenados, una pasada a la vez; una pasada sin intercambios lo termina. El ordenamiento rápido elige el elemento MEDIO de la lista como pivote, particiona los elementos restantes en "menores que el pivote", "iguales al pivote" y "mayores que el pivote" (conservando todas las copias); ordena recursivamente los grupos más pequeños y más grandes — siempre citar el pivote y el lista después de cada partición. La especificación fija la elección del elemento medio al método definido en su glosario, por lo que las listas de ejercicios aquí mantienen un número impar de elementos y el elemento medio es el en la posición $\tfrac{n+1}2$. Empaquetado en contenedores: first-fit coloca cada artículo en el primer contenedor con espacio disponible; first-fit decreasing ordena los artículos de mayor a menor y aplica first-fit; packing de llenado completo busca combinaciones que llenen un contenedor exactamente.

Ejemplo resuelto — ordenamiento rápido (original). Ordenar 9, 2, 7, 5, 3, 4, 6. El elemento medio (posición 4 de 7) es 5: menor = 2, 3, 4; mayor = 9, 7, 6, dando 2, 3, 4, 5, 9, 7, 6. Sublista 2, 3, 4 (pivote 3): 2, 3, 4 — ordenada. Sublista 9, 7, 6 (pivote 7): 6, 7, 9 — ordenada. Lista final: 2, 3, 4, 5, 6, 7, 9.

Ejemplo resuelto — empaquetado en contenedores (original). Contenedores de capacidad 10; artículos 7, 5, 4, 3, 6, 2 (total 27, por lo tanto al menos 3 contenedores). First-fit: 7→b1, 5→b2 (7+5 > 10), 4→b2 (9), 3→b1 (10), 6→b3, 2→b3 (8): contenedores (7,3), (5,4), (6,2). First-fit decreasing: 7, 6, 5, 4, 3, 2: 7→b1, 6→b2, 5→b3 (6+5 > 10), 4→b2 (10), 3→b1 (10), 2→b3 (7): contenedores (7,3), (6,4), (5,2) — también contenedores 3.

Un árbol de expansión mínima (MST) conecta todos los vértices con el menor peso total. Algoritmo de Kruskal: ordenar las aristas por peso, añadir la más pequeña que no forme un ciclo (rechazar y pasar a la siguiente cuando lo haría). Algoritmo de Prim: crecer un árbol desde cualquier vértice inicial, añadiendo repetidamente la arista más barata del árbol a un nuevo vértice. La forma matricial de Prim: tachar la fila inicial, rodear la entrada más pequeña restante en la columna del vértice elegido, y continuar. Kruskal es impulsado por aristas (bueno en redes dibujadas); Prim es impulsado por vértices (bueno en matrices). Ambos dan el mismo total; las aristas pueden diferir solo cuando hay empate de pesos. differen solo cuando los pesos están empatados.

Ejemplo resuelto (original). Bordes AB 4, AC 2, BC 3, BD 5, CD 1: Kruskal toma CD 1, AC 2, BC 3 (B joins — no cycle), then rejects AB 4 and BD 5 (cycles): MST total 6. Prim desde A: AC 2, CD 1 (borde más barato de {A,C} a un nuevo vértice), CB 3: el mismo árbol, y el total 6 ✓. Siempre enumere los bordes en el orden elegido y proporcione el total.

Para pesos de arista no negativos, el algoritmo de Dijkstra etiqueta los vértices con la menor distancia total encontrada hasta el momento: vértice inicial etiquetado 0; repite la selección del vértice no etiquetado de menor etiqueta temporal, hacerla permanente y actualizar sus vecinos (nuevo = permanente + peso, solo si es menor). Registrar el orden de permanencia y las etiquetas finales; el camino se recupera rastreando hacia atrás los vértices cuya etiqueta sea igual a la etiqueta final menos el peso de conexión.

Ejemplo resuelto (original). Aristas AB 4, AC 2, BC 1, BD 5, CD 8. Etiquetas: A = 0 permanente; C = 2 permanente; B = min(4, 2+1) = 3 permanente; D = min(3+5, 2+8) = 8 permanente. El camino más corto de A a D tiene longitud 8: A–C–B–D (rastreando hacia atrás: 8 = 3 + 5 en B, 3 = 2 + 1 en C).

El problema de inspección de rutas (cartero chino) recorre cada ARISTA al menos una vez y regresa al punto de partida. Longitud total = suma de todas las aristas + el camino más corto para duplicar aristas de modo que todos los vértices queden de grado par. Identificar los vértices impares (máximo cuatro), listar sus emparejamientos, elegir el emparejamiento de menor peso total y duplicar esas aristas. Indicar el emparejamiento antes del total.

Ejemplo resuelto (original). Aristas AB 4, AC 2, BC 3, BD 5, CD 1 (total 15). Grados: A 2, B 3, C 3, D 2 — los nodos impares son B y C, por lo tanto duplicar BC (peso 3): el ciclo cerrado más corto que recorre cada arista al menos una vez tiene longitud 15 + 3 = 18.

El problema clásico del viajante de comercio visita cada VÉRTICE exactamente una y retorna, en un grafo completo con la desigualdad triangular. Cotas: el MST de la red duplicada ofrece una ruta de cota SUPERIOR (recorre cada arista del MST dos veces); una mejor Los límites superiores aplican atajos. Los límites inferiores provienen de argumentos basados en el AEM (p. ej., el AEM mismo, o eliminando un vértice y añadiendo sus dos arcos más baratos). El **algoritmo del vecino más cercano construye un recorrido: desde el vértice inicial, ir repetidamente al vértice no visitado más cercano luego regresar. Convertir primero a una red completa de distancias más cortas cuando el grafo no es completo (mediante Dijkstra o inspección).

Ejemplo resuelto (original). Red completa: AB 4, AC 2, AD 7, BC 3, BD 5, CD 6 (el desigualdad triangular se cumple en todo momento). Vecino más cercano desde A: A–C (2), C–B (3), B–D (5), D–A (7): longitud del recorrido 17 — un límite superior. El AEM es AC + BC + BD = 10, por lo que duplicarlo da el límite superior grosero 20, mejorado a 17 mediante atajos; un límite inferior eliminando A (AEM de B, C, D es 3 + 5 = 8, más los dos arcos más baratos de A AC + AB = 2 + 4 = 6) es 14. El recorrido óptimo está entre 14 y 17.

Modelar un proyecto como una red de actividades sobre arcos a partir de una tabla de precedencias; actividades ficticias (arcos de peso cero) resuelven dependencias que los puntos finales compartidos no pueden expresar. El camino crítico es la cadena más larga a través de la red: la duración del proyecto. Calcular los tiempos de evento más temprano (paso hacia adelante: el máximo de llegadas) y los tiempos de evento más tardío (paso hacia atrás: el mínimo de salidas). La holgura total de una actividad = terminación más tardía − inicio más temprano − duración; las actividades críticas tienen holgura cero. Los gráficos de Gantt (en cascada) representan cada actividad con barras desde su inicio más temprano con su holgura como espacio posterior; la programación asigna trabajadores día a día.

Ejemplo resuelto (original). Actividades A (3 días), B (4), C (4 después de A), D (1 después de B), E (5 después de C y D). Cadena A–C–E = 12 días; cadena B–D–E = 10 días: la ruta crítica es A–C–E y el proyecto dura 12 días; holgura total de D = 12 − (4 + 1 + 5) = 2 días.

Formular: definir las variables de decisión, escribir la función objetivo (maximizar/minimizar) y cada restricción como una desigualdad, incluyendo $x, y \ge 0$. Resolver problemas de dos variables gráficamente: sombrear la región factible, luego usar el método de la regla (deslizar una regla a lo largo del gradiente de la función objetivo) o el método de los vértices (evaluar la función objetivo en cada vértice de la región factible). Soluciones enteras: probar puntos enteros cercanos al vértice óptimo dentro de la región.

• Ejecutar bubble sort y quick sort mostrando cada pasada y pivote; empaquetado por first-fit, first-fit decreciente y full-bin con colocaciones mostradas.
• Encontrar árboles de expansión mínima por Kruskal y por Prim (formas de nodo y matriz); dibujar una red desde una matriz y viceversa.
• Ejecutar Dijkstra con etiquetas en orden de permanencia; recuperar la ruta, no solo la longitud.
• Resolver inspección de rutas: nodos impares, todos los apareamientos con pesos, menor duplicación, longitud total del recorrido.
• Acotar el TSP clásico: doble árbol de expansión mínima y atajos para cotas superiores, eliminación de árbol de expansión mínima para cotas inferiores; ejecutar vecino más cercano en la red completa de distancias mínimas.
• Construir redes de actividades con activities ficticias; pasadas hacia adelante y hacia atrás para tiempos de evento; holguras totales; identificar la ruta crítica; dibujar el diagrama de Gantt y el cronograma.

Ejemplo resuelto — programación lineal (original). Maximizar $P = 3x + 2y$ sujeto a $x + y \le 10$, $2x + y \le 14$, $x, y \ge 0$. Los vértices de la región factible son $(0,0)$, $(7,0)$, $(4,6)$, $(0,10)$; evaluando $P$: 0, 21, 24, 20 — el máximo es $P = 24$ en $(4,6)$, donde ambas restricciones son activas.

• Formular programas lineales completamente; resolver gráficamente con regla o métodos de vértice; encontrar las mejores soluciones enteras.