D1 · Decision Mathematics 1

Mathématiques décisionnelles 1 (D1, sujet WDM01/01, 1 heure 30 minutes, 75 points, première évaluation juin 2019) est l'option discrète du IAL : P1–P2 sont supposées, et chaque méthode est un ALGORITHME — une liste finie d'instructions exactes. Aucune entrée dans le manuel de formules au-delà des bases : les points sont attribués pour exécuter précisément les procédures et énoncer les résultats dans la forme requise. Cette référence couvre les algorithmes de tri et d'emballage, les arbres couvrants minimaux, chemins les plus courts, les problèmes du facteur chinois et du voyageur de commerce, l'analyse du chemin critique et la programmation linéaire.

Règles spécifiques pour les réponses aux algorithmes :

Le tri bulle compare les éléments adjacents, échangeant les paires hors ordre, une passe à la fois ; une passe sans échange met fin au processus. Le tri rapide sélectionne l'élément du MILIEU de la liste comme pivot, partitionne les éléments restants en « inférieur au pivot », « égal au pivot » et « supérieur au pivot » (en conservant toutes les copies) ; il trie récursivement les groupes plus petits et plus grands — toujours citer le pivot et le liste après chaque partition. La spécification lie le choix de l'élément central à la méthode définie dans son glossaire, donc les listes d'exercices ici conservent un nombre impair d'éléments et l'élément central est celui à la position $\tfrac{n+1}2$. Emballage par bin : first-fit place chaque élément dans le premier bin ayant de la place ; first-fit decreasing trie les éléments du plus grand au plus petit puis applique first-fit ; full-bin packing cherche des combinaisons remplissant exactement un bin.

Exemple résolu — tri rapide (original). Trier 9, 2, 7, 5, 3, 4, 6. L'élément central (position 4 de 7) est 5 : less = 2, 3, 4 ; greater = 9, 7, 6, donnant 2, 3, 4, 5, 9, 7, 6. Sous-liste 2, 3, 4 (pivot 3) : 2, 3, 4 — triée. Sous-liste 9, 7, 6 (pivot 7) : 6, 7, 9 — triée. Liste finale : 2, 3, 4, 5, 6, 7, 9.

Exemple résolu — emballage par bin (original). Bins de capacité 10 ; éléments 7, 5, 4, 3, 6, 2 (total 27, donc au moins 3 bins). First-fit : 7→b1, 5→b2 (7+5 > 10), 4→b2 (9), 3→b1 (10), 6→b3, 2→b3 (8) : contenants (7,3), (5,4), (6,2). Décroissance de premier ajustement : 7, 6, 5, 4, 3, 2 : 7→b1, 6→b2, 5→b3 (6+5 > 10), 4→b2 (10), 3→b1 (10), 2→b3 (7) : contenants (7,3), (6,4), (5,2) — aussi 3 bins.

Un arbre couvrant minimal (ACM) relie tous les sommets avec le poids total le plus faible. Algorithme de Kruskal : trier les arêtes par poids, ajouter la plus petite qui ne forme pas un cycle (rejeter et passer à la suivante si elle le ferait). Algorithme de Prim : construire un arbre à partir de n'importe quel sommet initial, en ajoutant répétitivement l'arête la moins coûteuse reliant l'arbre à un nouveau sommet. La version matricielle de Prim : rayer la ligne du sommet initial, entourer l'entrée restante la plus petite dans la colonne du sommet choisi, et continuer. Kruskal est basé sur les arêtes (adapté pour un réseau dessiné) ; Prim est basé sur les sommets (adapté pour une matrice). Les deux donnent le même total ; les arêtes peuvent différer uniquement en cas d'égalité de poids. diffèrent uniquement lorsque les poids sont égaux.

Exemple résolu (original). Arêtes AB 4, AC 2, BC 3, BD 5, CD 1 : Kruskal sélectionne CD 1, AC 2, BC 3 (B se joint — pas de cycle), puis rejette AB 4 et BD 5 (cycles) : MST total 6. Prim à partir de A : AC 2, CD 1 (arête la moins coûteuse partant de {A,C} vers un nouveau sommet), CB 3 : le même arbre, et le total 6 ✓. lister toujours les arêtes dans l'ordre de sélection et donner le total.

Pour des poids d'arêtes non négatifs, l'algorithme de Dijkstra étiquette les sommets avec la distance totale minimale trouvée à ce jour : étiquette du sommet de départ 0 ; sélectionner répétéivement le sommet non étiqueté ayant la plus petite (nouvel = définitif + poids, seulement si inférieur). Enregistrer l'ordre de fixation et les étiquettes finales ; le chemin est obtenu en remontant depuis le sommet dont l'étiquette correspond à la (nouveau = permanent + poids, seulement si plus petit). Enregistrer l'ordre des permanences et les étiquettes finales ; le chemin est retrouvé en remontant par les sommets dont l'étiquette correspond à la étiquette finale moins le poids de connexion.

Exemple résolu (original). Arêtes AB 4, AC 2, BC 1, BD 5, CD 8. Étiquettes : A = 0 permanent ; C = 2 permanent ; B = min(4, 2+1) = 3 permanent ; D = min(3+5, 2+8) = 8 permanent. Le chemin le plus court de A à D a une longueur de 8 : A–C–B–D (remonter : 8 = 3 + 5 en B, 3 = 2 + 1 en C).

Le problème d'inspection de route (facteur chinois) parcourt chaque ARÊTE au moins une fois et revient au point de départ. Longueur totale = somme de toutes les arêtes + la plus courte façon de dupliquer des arêtes pour que chaque sommet devienne pair. Trouver les sommets impairs (au maximum quatre), lister leurs appariements, choisir l'appariement de poids total minimal, et dupliquer ces arêtes. Indiquer l'appariement avant le total.

Exemple résolu (original). Arêtes AB 4, AC 2, BC 3, BD 5, CD 1 (total 15). Degrés : A 2, B 3, C 3, D 2 — les nœuds impairs sont B et C, donc dupliquer BC (poids 3) : la plus courte boucle parcourant chaque arête au moins une fois a une longueur de 15 + 3 = 18.

Le problème classique du voyageur de commerce effectue un circuit visitant chaque SOMMET exactement une et retourne, sur un graphe complet vérifiant l'inégalité triangulaire. Bornes : le ASM du réseau doublé fournit un itinéraire borné SUPÉRIEUR (parcourir chaque arête de l'ASM deux fois) ; une meilleure borne supérieure utilise des raccourcis. Les bornes inférieures proviennent d'arguments basés sur l'AEP (par ex. l'AEP lui-même, ou la suppression d'un sommet et l'ajout de ses deux arêtes les moins chères). L'algorithme du voisin le plus proche construit un circuit : depuis le sommet de départ, aller répétitivement vers le voisin le plus sommet non visité, puis revenir. Convertir d'abord en réseau complet de distances minimales lorsque le graphe n'est pas complet (via Dijkstra ou inspection).

Exemple résolu (original). Réseau complet : AB 4, AC 2, AD 7, BC 3, BD 5, CD 6 (la inégalité triangulaire est satisfaite partout). Voisin le plus proche à partir de A : A–C (2), C–B (3), B–D (5), D–A (7) : longueur de la tournée 17 — une borne supérieure. L'AMST est AC + BC + BD = 10, donc en le doublant on obtient la borne supérieure grossière 20, améliorée à 17 par des raccourcis ; une borne inférieure obtenue en supprimant A (AMST de B, C, D est 3 + 5 = 8, plus les deux arcs les moins chers de A : AC + AB = 2 + 4 = 6) est 14. Le parcours optimal se situe entre 14 et 17.

Modéliser un projet comme un réseau activité sur arc à partir d'un tableau de précédence ; les arcs fantômes (arcs de poids nul) résolvent les dépendances que des extrémités communes ne peuvent exprimer. Le chemin critique est la chaîne la plus longue dans le réseau : la durée du projet. Calculer les dates au plus tôt des événements (passage avant : le max des arrivées) et les dates au plus tard des événements (passage arrière : le min des départs). La marge totale d'une activité = date de fin au plus tard − date de début au plus tôt − durée ; les activités critiques ont une marge nulle. Les graphiques de Gantt (en cascade) représentent chaque activité sous forme de barre partant de sa date de début au plus tôt avec sa marge comme espace terminal ; l'affectation alloue les travailleurs jour par jour.

Exemple résolu (original). Activités A (3 jours), B (4), C (4 après A), D (1 après B), E (5 après C et D). Chaîne A–C–E = 12 jours ; chaîne B–D–E = 10 jours : le chemin critique est A–C–E et le projet dure 12 jours ; la marge totale de D = 12 − (4 + 1 + 5) = 2 jours.

Formuler : définir les variables de décision, rédiger l'objectif (maximiser/minimiser) et chaque contrainte sous forme d'inégalité, y compris $x, y \ge 0$. Résoudre graphiquement les problèmes à deux variables : hachurer la région réalisable, puis utiliser la méthode de la règle (faire glisser une règle le long du gradient de l'objectif) ou la méthode des sommets (évaluer l'objectif à chaque sommet de la région réalisable). Solutions entières : tester les points entiers situés près du sommet optimal à l'intérieur de la région.

• Exécuter les tri par bulle et tri rapide en montrant chaque passe et pivot ; empilement par première place disponible, première place disponible décroissante et pleine-bac avec placements indiqués.
• Trouver les ATM par Kruskal et par Prim (formes matricielle et arborescente) ; dessiner un réseau à partir d'une matrice et inversement.
• Appliquer l'algorithme de Dijkstra avec étiquettes dans l'ordre de permanence ; récupérer le chemin, pas seulement la longueur.
• Résoudre l'inspection de route : nœuds impairs, tous les appariements avec leurs poids, moindre redondance, longueur totale du parcours.
• Minorer le TSP classique : double ATM et raccourcis pour les bornes supérieures, suppression d'ATM pour les bornes inférieures ; appliquer le plus proche voisin sur le réseau complet des plus courtes distances.
• Construire des réseaux d'activités avec des activities fictives ; passages avant et arrière pour les temps des événements ; flot total ; identifier le chemin critique ; dessiner le diagramme de Gantt et le planning.

Exemple résolu — programmation linéaire (original). Maximiser $P = 3x + 2y$ sous contraintes $x + y \le 10$, $2x + y \le 14$, $x, y \ge 0$. Les sommets de la région réalisable sont $(0,0)$, $(7,0)$, $(4,6)$, $(0,10)$ ; évaluation de $P$ : 0, 21, 24, 20 — le maximum est $P = 24$ au point $(4,6)$, où les deux contraintes sont serrées.

• Formuler entièrement des programmes linéaires ; résoudre graphiquement par méthodes de règle ou de sommet ; trouver les meilleures solutions entières.