Révisions — Optimisation en informatique

📘 Flots dans un réseau de transport

Cette application visualise pas-à-pas la construction d'un flot complet par la procédure gloutonne de référence, et la construction d'un flot maximum par l'algorithme de Ford-Fulkerson (graphe résiduel).

Vue d'ensemble de l'écran

Colonne de gauche : description du problème, édition du réseau (1 arc par ligne au format x y capacité), source, puits, et liste optionnelle des chemins augmentants à essayer dans l'ordre.
Centre : le graphe orienté avec capacités. Source en vert, puits en bleu, intermédiaires en blanc. Chaque arc porte une étiquette f/c (flux/capacité) sur fond blanc.
Colonne de droite : choix de l'algorithme, navigation pas-à-pas, état courant, notes de référence et pseudo-code synchronisé.

Interactions souris sur le graphe

Clic-glisser sur un sommet → déplace le sommet librement. Les positions personnalisées sont mémorisées entre les étapes et entre les algorithmes.
Clic-glisser sur le fond → pan du graphe.
Molette de la souris → zoom avant/arrière.
Boutons + − ⤢ en haut → zoom et recentrage.
Bouton ↻ positions → revient à la disposition automatique par couches.

Codage visuel des arcs

Gris pointillé fin = arc non utilisé (f = 0).
Vert plein moyen = flux partiel (0 < f < c).
Bleu foncé plein épais = arc saturé (f = c).
Rouge épais = arc du chemin courant à cette itération.

Définitions essentielles

Réseau de transport : graphe orienté avec deux sommets distingués (source s, puits p) et une capacité positive c(x,y) sur chaque arc.
Flot : valeur f(x,y) ≥ 0 sur chaque arc, avec f(x,y) ≤ c(x,y) (contrainte de capacité) et conservation aux nœuds intermédiaires (flux entrant = flux sortant).
Arc saturé : f(x,y) = c(x,y) (utilisé au maximum).
Flot complet : il existe au moins un arc saturé sur tout chemin de s à p.
Flot maximum : flot de valeur maximale. Tout flot maximum est complet, mais l'inverse est faux.

Flot complet — procédure gloutonne de référence

Étape 1. Choisis Flot complet dans le menu Algorithme.

Étape 2. Clique sur Exemple de référence (9 nœuds) pour charger le réseau étudié.

Étape 3. Clique sur Suivante →. À chaque itération, l'algorithme cherche un chemin de s à p en utilisant uniquement des arcs non saturés, puis pousse δ = min(c−f) le long de ce chemin, ce qui sature au moins un arc.

Les chemins augmentants sont pré-saisis dans la colonne de gauche dans l'ordre des slides de référence (S-C-G-P, S-C-F-P, S-B-F-P, S-B-E-P, S-B-D-P, S-A-G-P, S-A-E-P, S-A-D-P). Tu peux les modifier ou les vider — dans ce cas l'application choisit automatiquement un chemin par BFS.

Pourquoi un flot complet n'est pas toujours maximum

Sur l'exemple de référence, la procédure gloutonne produit un flot de valeur 80. Pourtant la valeur du flot maximum est 85. La procédure gloutonne est une heuristique : une fois qu'un arc est saturé, on s'interdit d'y toucher, alors qu'en réalité on pourrait « annuler » du flux pour le rediriger ailleurs.

Flot maximum — Ford-Fulkerson

L'algorithme construit le graphe résiduel G_f : à chaque arc (x,y) avec flux f, on associe :

une capacité résiduelle directe c−f (utilisable pour pousser du flux supplémentaire),
une capacité résiduelle inverse f (utilisable pour annuler du flux et le rediriger).

On cherche alors un chemin augmentant dans G_f ; tant qu'il en existe, on pousse δ le long, en ajoutant δ sur les arcs directs et en retranchant δ sur les arcs retour.

On rappelle que le flot maximum est calculé par programmation linéaire (solveur GLPK). Ford-Fulkerson est l'algorithme combinatoire historique qui résout le même problème. L'app le propose ici à titre pédagogique pour bien comprendre la différence avec la procédure gloutonne.

Comment utiliser les autres exemples

Petit réseau (4 nœuds) : un cas minimal pour suivre étape par étape sans se perdre.
Deux autoroutes parallèles : illustre que la valeur d'un flot est limitée par la somme des capacités des arcs sortant de s — ici 20.
Goulot d'étranglement : un arc central de petite capacité limite tout le débit, même si les arcs périphériques sont larges.

Le bouton de l'exemple chargé est surligné en bleu dans la liste, avec une barre verticale à gauche. Dès que tu modifies le réseau, la source, le puits ou la liste des chemins, la surbrillance disparaît : c'est le signe que le PL courant ne correspond plus à un exemple préenregistré.

Points-clés à retenir

Notion	Définition
Flot	f(x,y) ≥ 0 sur chaque arc, avec capacité et conservation aux nœuds intermédiaires
Valeur d'un flot	Σ flux sortant de s = Σ flux arrivant à p
Arc saturé	f(x,y) = c(x,y)
Flot complet	≥ 1 arc saturé sur tout chemin de s à p
Flot maximum	Flot de valeur max. Est complet, mais pas réciproquement.
Procédure gloutonne	Itérer chemins → saturation. Donne un flot complet, pas forcément max.
Ford-Fulkerson	Pareil mais sur le graphe résiduel (arcs retour). Donne le flot max.

📘 Routage & Arbres de connexion

Cette application visualise pas-à-pas les deux algorithmes : Dijkstra pour les tables de routage (plus courts chemins depuis une source) et Kruskal pour les arbres de connexion minimum (ACPM).

Tables de routage et plus courts chemins

Dans un réseau, on cherche le meilleur trajet entre un nœud origine o et un nœud destination d en minimisant la somme des temps de réponse des liens. La table de routage de o indique, pour chaque destination d, le prochain saut à effectuer.

Modélisation par un graphe orienté pondéré avec longueurs positives. Dijkstra (1959) trouve tous les plus courts chemins depuis une source unique en O(m + n·log n).

Dijkstra — étape par étape

L'algorithme associe à chaque sommet x_i deux informations :

λ_i = longueur du plus court chemin connu depuis la source jusqu'à x_i (initialement +∞, sauf λ_source=0),
p_i = prédécesseur de x_i dans ce plus court chemin (initialement non défini).

À chaque itération :

1. On choisit le sommet à traiter de plus petit λ parmi les non-traités → c'est x_j. Sa valeur λ_j ne changera plus.

2. Pour chaque arc (x_j, x_i) sortant de x_j vers un non-traité x_i : si λ_i > λ_j + longueur(j, i), on met à jour λ_i et p_i ← x_j.

3. On marque x_j comme traité.

Quand tous les sommets sont traités, on a une arborescence des plus courts chemins issue de la source. La table de routage s'en déduit : pour aller à x_i depuis la source, le premier saut est obtenu en remontant les p_k jusqu'à un voisin direct de la source.

Exemple de référence

Graphe à 6 sommets x₁…x₆. Source = x₁. Les arcs et longueurs sont chargés par le bouton « Dijkstra — exemple x₁..x₆ ».

Évolution du tableau : à chaque ligne on traite un nouveau sommet (celui de plus petit λ marqué *), puis on relâche ses arcs sortants.

Traité	(p₂, λ₂)	(p₃, λ₃)	(p₄, λ₄)	(p₅, λ₅)	(p₆, λ₆)
x₁	(x₁, 3)	(x₁, 8)	(−, ∞)	(x₁, 6)	(−, ∞)
x₂	(x₁, 3)*	(x₁, 8)	(x₂, 9)	(x₂, 5)	(x₂, 12)
x₅	(x₁, 3)*	(x₅, 7)	(x₂, 9)	(x₂, 5)*	(x₅, 11)
x₃	(x₁, 3)*	(x₅, 7)*	(x₃, 8)	(x₂, 5)*	(x₅, 10)
x₄	(x₁, 3)*	(x₅, 7)*	(x₃, 8)*	(x₂, 5)*	(x₃, 10)
x₆	(x₁, 3)*	(x₅, 7)*	(x₃, 8)*	(x₂, 5)*	(x₃, 10)*

Arborescence finale : x₁→x₂ (3), x₂→x₅ (5 cumul), x₅→x₃ (7 cumul), x₃→x₄ (8 cumul), x₃→x₆ (10 cumul). Table de routage depuis x₁ : pour toute destination, le prochain saut est x₂.

Arbres de connexion et Kruskal

Étant donné un réseau non orienté pondéré, on veut un sous-graphe connectant tous les sommets de coût total minimum — un arbre couvrant de poids minimum (ACPM). Kruskal construit l'ACPM gloutonnement :

1. Trier toutes les arêtes par poids croissant.

2. Parcourir les arêtes dans cet ordre. Ajouter une arête à l'ACPM si elle ne crée pas de cycle avec les arêtes déjà sélectionnées.

3. S'arrêter quand on a (n − 1) arêtes (n = nombre de sommets).

La détection de cycle se fait efficacement avec une structure Union-Find : chaque composante connexe est représentée par un « chef de classe », et on fusionne deux composantes quand on ajoute une arête entre elles.

Comment lire les visualisations

Centre : le graphe est dessiné avec les sommets en cercles. Tu peux les déplacer par glisser-déposer. Zoom à la molette, pan avec un drag sur le fond.
Bas du centre : tableau d'évolution. Pour Dijkstra, les colonnes sont les sommets et les lignes les itérations. Pour Kruskal, le tableau liste les arêtes triées par poids et indique si chacune est ajoutée à l'ACPM ou rejetée (cycle).
Édition : panneau de gauche pour ajouter/supprimer sommets et arêtes, ou pour saisir le graphe sous forme textuelle.

Points-clés à retenir

Notion	Définition
Table de routage	Pour chaque destination, indique le prochain nœud à atteindre depuis le nœud courant.
Plus court chemin	Minimise la somme des longueurs des arcs.
Dijkstra	Tous les plus courts chemins depuis une source, longueurs ≥ 0 requises.
Arbre de connexion	Sous-graphe connexe qui touche tous les sommets et n'a pas de cycle.
ACPM	Arbre couvrant de poids minimum.
Kruskal	Glouton : tri par poids + ajout sans cycle (Union-Find).

📘 Programmation linéaire & Simplexe

Cette application visualise pas-à-pas la résolution d'un programme linéaire (PL) selon deux approches : la résolution graphique (valable uniquement pour 2 variables) et la méthode du simplexe de référence, applicable à n'importe quelle taille.

Vue d'ensemble de l'écran

Colonne de gauche : saisie du PL (type max/min, fonction objectif, contraintes), exemples de référence.
Centre : pour les PL à 2 variables, le polyèdre admissible avec les droites des contraintes, le gradient ∇Z, les sommets, et le sommet courant du simplexe matérialisé par un cercle rouge.
Colonne de droite : choix de l'algorithme, navigation pas-à-pas, PL réécrit dans la base courante, test des ratios, notes de référence, pseudo-code.

Comment saisir le PL

Les variables doivent être nommées x1, x2, x3, …. La non-négativité (x_j ≥ 0) est implicite, ne pas la saisir.

Fonction objectif : exemple 4 x1 + 3 x2 ou 4x1+3x2. Les espaces sont optionnels.
Contraintes : une par ligne, opérateurs <= >= =. Exemple : 2 x1 + x2 <= 18.
Type : max ou min. La V1 du simplexe ne gère que max avec contraintes ≤ et b ≥ 0 ; pour un min, multiplie l'objectif par −1.

Méthode du simplexe — étape par étape

L'algorithme se déroule selon le schéma de référence :

1. Mise sous forme standard. Chaque contrainte ≤ devient une égalité par ajout d'une variable d'écart u_i ≥ 0. Par exemple 2x1 + x2 ≤ 18 devient 2x1 + x2 + u4 = 18.

2. Base de départ. On choisit B⁽⁰⁾ = {u₁, …, u_m}. La solution de base associée est x_j=0 pour les variables originales, et u_i=b_i pour les écarts. Cette solution correspond à l'origine du polyèdre.

3. Réécriture dans la base. Chaque variable de base est exprimée en fonction des hors-base, et l'objectif Z aussi. Les coefficients de Z s'appellent les coûts réduits.

4. Critère d'optimalité. Si tous les coûts réduits sont ≤ 0, la solution courante est optimale (pour un max). Sinon on itère.

5. Variable entrante. On choisit la variable hors-base de plus grand coût réduit > 0 (surlignée en jaune dans l'app).

6. Variable sortante. Par test des ratios : pour chaque ligne de base où le coefficient de la variable entrante est négatif (la variable de base décroît quand l'entrante augmente), on calcule le ratio −const/coef. La variable sortante est celle de plus petit ratio (surlignée en rouge).

7. Pivot. On isole l'entrante dans l'équation de la sortante, on substitue dans toutes les autres équations et dans l'objectif. La nouvelle base est B' = B + {entrante} − {sortante}.

Visualisation pour les PL à 2 variables

Le centre affiche le polyèdre admissible avec :

Les droites de contraintes en couleurs (rouge, orange, vert, violet…) avec leur étiquette.
Le domaine réalisable en bleu clair (intersection des demi-plans).
Tous les sommets du polyèdre en petits points bleus.
Le sommet courant du simplexe en gros cercle rouge — il se déplace à chaque pivot. Sur l'exemple de référence, on voit la trajectoire O → E → D → C.
Pour la résolution graphique, on ajoute le gradient ∇Z en rouge et plusieurs droites de niveau Z=const en jaune pointillé.

Au survol du graphique tu peux panner (clic-glisser sur le fond) et zoomer à la molette ou avec les boutons + − ⤢ en haut. Le bouton ⤢ recentre tout.

Trois exemples tirés de référence

Exemple Simplexe : max 4x₁+3x₂, 4 contraintes. Optimum Z*=40 en (7, 4), trajectoire O→E→D→C. C'est le cas étudié en détail dans Methode_simplexe.pdf.
Exemple résolution graphique — intro PL : max 3x₁+5x₂, 3 contraintes. Cas classique de la fiche d'introduction un support de référence.
Exo 1 (graphique) & Exo 5 (simplexe) — fiche d'exercices : max 3x₁+x₂, 3 contraintes (dont une avec coefficient négatif). Optimum (5, 6) avec Z*=21. C'est le même PL résolu par la méthode graphique dans l'exercice 1 et par le simplexe dans l'exercice 5 de Exercices_PL.pdf. Idéal pour vérifier que les deux méthodes donnent bien le même résultat. Le déroulé du simplexe est : B⁽⁰⁾={u₁,u₂,u₃} (Z=0) → B⁽¹⁾={u₁,x₁,u₃} (Z=15) → B⁽²⁾={u₁,x₁,x₂} (Z=21).

Le bouton de l'exemple chargé est surligné en bleu avec une barre verticale à gauche. Dès que tu modifies le type, l'objectif ou les contraintes, la surbrillance disparaît : ton PL ne correspond plus à un exemple préenregistré.

Points-clés à retenir

Notion	Définition
Variable d'écart	u_i ≥ 0 ajoutée à chaque contrainte ≤ pour passer en égalité.
Base / hors-base	m variables en base (≠ 0 a priori) et n−m hors-base (fixées à 0).
Solution de base	Sommet du polyèdre : x_j=0 pour hors-base, valeur déduite pour la base.
Coût réduit	Coefficient d'une variable hors-base dans Z exprimée en fonction des seules hors-base.
Optimalité (max)	Tous les coûts réduits ≤ 0.
Variable entrante	Hors-base de plus grand coût réduit > 0.
Variable sortante	Base de plus petit ratio −const/coef (coef < 0 sur la colonne de l'entrante).
Pivot	Une opération = un nouveau sommet adjacent du polyèdre.

📘 PLNE & Branch and Bound

Cette application visualise pas-à-pas la résolution d'un programme linéaire en nombres entiers (PLNE) par l'algorithme de séparation et évaluation (Branch and Bound). Elle illustre aussi la notion de relaxation continue.

Pourquoi un PLNE est difficile

Un PL classique se résout efficacement (simplexe, polynomial dans la plupart des cas). Mais dès qu'on impose x_j ∈ ℤ, le problème devient en général NP-difficile : il n'y a pas (à ce jour) d'algorithme polynomial connu, et arrondir naïvement la solution du PL relâché ne donne pas l'optimum entier.

Relaxation continue

On supprime la contrainte d'intégrité — on garde x_j ∈ ℝ⁺. Le PL obtenu est facile à résoudre. Sa valeur optimale Z_PL est une borne supérieure sur la valeur optimale Z_PLNE :

Z_PLNE ≤ Z_PL (pour un max). En effet, toute solution entière est aussi admissible pour le PL relâché.
Si la solution du PL est entière par chance → c'est aussi l'optimum de la PLNE.
Sinon, on sait juste que l'optimum entier vaut au plus Z_PL.

Choisis l'algorithme « Relaxation continue seule (PL) » pour voir ce que donne le PL relâché tout seul. Le cercle rouge sur le polyèdre marque la solution non entière du PL.

Branch and Bound — principe

L'algorithme explore un arbre de problèmes où chaque nœud représente une PLNE restreinte (avec des contraintes de branchement supplémentaires). À chaque nœud :

Évaluation. On résout la relaxation continue du nœud. La valeur Z_PL obtenue est une borne supérieure locale.

Mise à jour de la borne inférieure BI. La BI est la meilleure solution entière jamais trouvée à ce stade (elle joue le rôle de borne inférieure globale pour un max ; on l'appelle aussi « incumbent » en anglais — terme absent de référence). Si la solution du PL est entière et meilleure → on met à jour BI.

Élagage. On coupe la branche dans 3 cas :
• PL infaisable → pas de solution dans ce sous-arbre.
• Z_PL ≤ BI → aucune amélioration possible.
• Solution entière → branche close (avec ou sans mise à jour de la BI).

Séparation. Si la solution PL a une composante x_i = v non entière, on crée deux fils en ajoutant x_i ≤ ⌊v⌋ à gauche et x_i ≥ ⌈v⌉ à droite. On choisit la variable dont la partie décimale (v − ⌊v⌋) est la plus proche de 0,5 — c'est celle qui est la plus « ambiguë » entre les deux entiers voisins.

Quand la pile (ou file) de nœuds à traiter est vide, la BI finale est l'optimum entier.

Comment lire la visualisation

Arbre B&B à gauche : chaque nœud est étiqueté N_k, montre la solution PL (x₁*, x₂*) et la valeur Z. La couleur indique le statut :
- Bleu = en attente (à explorer)
- Jaune-orange = branché (a des fils)
- Vert = solution entière (candidate pour la BI)
- Rouge = élagué (par borne ou infaisabilité)
- Bordure rouge épaisse = nœud courant à l'étape affichée
Les arêtes portent l'étiquette de la contrainte ajoutée (par ex. x1 ≤ 2).
Polyèdre à droite : domaine admissible de la PLNE de base (en bleu pâle), les points entiers admissibles (en bleu foncé), les contraintes de branchement du nœud courant (lignes rouges pointillées), la solution PL courante (cercle rouge), et la meilleure solution entière (BI) (cercle vert).

Trois exemples de référence

Cambrioleur (or/billets) — sac à dos : max 3x₁+x₂, 8x₁+3x₂≤20, 6x₁+6x₂≤32. Optimum du PL relâché (2.5, 0) → Z_PL=7.5 ; optimum entier (2, 1) → Z*=7.
Exercice B&B : max 3x₁+x₂, 8x₁+4x₂≤22, 6x₁+6x₂≤32. Optimum du PL relâché (22/8, 0) → Z_PL=8.25 ; après branchement, optimum entier (2, 1) → Z*=7.
Exercice B&B (variante) — relaxé 32 : max 2x₁+x₂, 8x₁+3x₂≤20, 6x₁+6x₂≤29. Variante avec second membre 29.

Pour bien comprendre le B&B, clique « Suivante → » étape par étape sur l'exemple du cambrioleur : tu verras la racine s'évaluer à Z=7.5 avec un x* non entier, puis le branchement sur x₁, l'évaluation des fils, et finalement l'apparition de la première solution entière BI.

Points-clés à retenir

Notion	Définition
PLNE	PL avec x ∈ ℤ⁺. NP-difficile en général.
Relaxation continue	On supprime x ∈ ℤ → PL classique. Donne une borne supérieure (max).
Branch and Bound	Arbre de sous-PLNE où chaque évaluation = relaxation continue.
Borne inférieure (BI)	Meilleure solution entière trouvée à date (« incumbent » en anglais, terme absent de référence).
Élagage	Couper une branche : infaisable, Z_PL ≤ BI, ou intégrité atteinte.
Séparation	Sur x_i = v non entière : créer 2 fils avec x_i ≤ ⌊v⌋ et x_i ≥ ⌈v⌉.

📘 Programmation dynamique

Cette application visualise pas-à-pas deux algorithmes classiques de programmation dynamique : le sac à dos exact (récurrence sur f(i, P)) et l'affectation de tâches à 1 processeur (récurrence sur h(i)).

Principe d'optimalité de Bellman

De nombreux problèmes d'optimisation vérifient le principe : si une partie d'une solution optimale est identifiée, le reste doit être optimal sur le reste de l'instance. Ce principe permet d'écrire la valeur optimale d'une instance comme une combinaison des valeurs optimales d'instances plus petites du même problème, reliées par des équations de récurrence.

Un algorithme de PD se compose de :

une fonction récursive (souvent à plusieurs variables : f(i, P), h(i), …),
des cas terminaux (pour i = 0 ou 1),
une initialisation de la récurrence,
un tableau qui stocke les valeurs déjà calculées pour éviter les recalculs (mémoïsation).

Algorithme 1 — Sac à dos exact, fonction f(i, P)

On a n objets, chacun avec poids p_i et valeur v_i. La capacité du sac est P_max. On veut maximiser la valeur totale en respectant la capacité.

On définit f(i, P) = valeur max d'un sous-ensemble choisi parmi les i premiers objets, avec poids total ≤ P.

Équation de récurrence. Pour i ≥ 2 et P ≥ 0 :
• Si p_i ≤ P : f(i,P) = max( v_i + f(i-1, P-p_i) , f(i-1, P) ) — on prend ou on refuse l'objet i.
• Si p_i > P : f(i,P) = f(i-1, P) — objet trop lourd, on l'oublie.

Cas terminal (ligne 1). f(1, P) = v₁ si p₁ ≤ P, sinon 0.

Initialisation : on calcule t[n][P_max] en remplissant le tableau ligne par ligne (i de 1 à n), colonne par colonne (P de 0 à P_max).

Complexité : O(n × P_max) étapes — efficace tant que P_max n'explose pas.

Comment lire la visualisation (sac à dos)

Tableau 2D avec lignes i = 1..n et colonnes P = 0..P_max.
À chaque étape, la case en cours de calcul est jaune avec bordure orange.
Les cases-source dont elle dépend sont en bleu clair, reliées par des flèches pointillées. Au-dessus = « objet i refusé ». En diagonale en haut-à-gauche = « objet i pris ».
À la dernière étape, on lit la valeur optimale dans la case t[n][P_max], et on remonte par backtrack pour identifier les objets choisis.

Exemple de référence

n = 4, P_max = 7, poids = (5, 3, 1, 4), valeurs = (100, 55, 18, 70). Le tableau final :

i \ P	1	2	3	4	5	6	7
i=1	0	0	0	0	100	100	100
i=2	0	0	55	55	100	100	100
i=3	18	18	55	73	100	118	118
i=4	18	18	55	73	100	118	125

Valeur optimale = 125, obtenue en prenant les objets {2, 4} (poids 3+4 = 7 = P_max, valeur 55+70 = 125). L'app fait le backtrack automatique et affiche cet ensemble.

Algorithme 2 — Affectation de tâches à 1 processeur, fonction h(i)

On a n tâches, chacune avec une date de début d_i, une date de fin f_i, et un profit p_i. Deux tâches qui se chevauchent sont incompatibles. On veut maximiser le profit total d'un sous-ensemble de tâches compatibles.

On commence par trier les tâches par f_i croissant. Soit h(i) = profit max d'un sous-ensemble compatible dont la dernière tâche est i.

Équation de récurrence.
h(i) = p_i + max{ h(j) : j < i et f_j ≤ d_i }
(avec la convention max = 0 s'il n'existe aucun tel j).

Valeur optimale : max(h(1), h(2), …, h(n)).

Complexité : O(n²) — ne dépend que du nombre de tâches.

Comment lire la visualisation (affectation)

Tableau 1D avec colonnes i = 1..n. Quatre lignes : d_i, f_i, p_i, et h(i) qui se remplit.
La case h(i) en cours est en jaune.
La case h(j) qui a servi de max est en bleu clair.
Un diagramme de Gantt en bas montre les plages horaires des tâches, avec la tâche courante en orange et la tâche-source en bleu.

Quatre exemples

Sac à dos — exemple de référence : n=4, P_max=7, exactement les valeurs de référence. Optimum = 125.
Sac à dos — petit cas : n=3 pour suivre toutes les étapes facilement.
Affectation — 11 tâches (profits=1) : valeur optimale = 4 (h(11)).
Affectation — profits variés : 5 tâches avec profits différents pour montrer l'effet du choix.

Points-clés à retenir

Notion	Définition
Principe d'optimalité (Bellman)	Toute partie d'une solution optimale est optimale sur le sous-problème correspondant.
Équation de récurrence	Lien entre la valeur optimale d'une instance et celles d'instances plus petites.
Mémoïsation	Stockage des valeurs intermédiaires dans un tableau pour éviter les recalculs.
Complexité sac à dos	O(n × P_max) — pseudo-polynomial (dépend de la valeur de P_max, pas seulement de sa taille).
Complexité affectation	O(n²) — vraiment polynomial.

📘 Métaheuristiques sur le sac à dos élastique

Cette application visualise quatre métaheuristiques sur le problème du sac à dos élastique : descente locale, recherche tabou, recuit simulé, algorithme génétique.

Le problème

On a n articles, chacun avec un poids et un prix. Le sac a une capacité C. On peut dépasser la capacité : un dépassement de Δ kg coûte Δ^p € de pénalité (p paramétrable, p=2 pour le TP noté, p=3 pour le TP de révision). Objectif : maximiser le bénéfice = Σ prix − pénalité.

Vue d'ensemble

Gauche : paramètres du problème (n, capacité, exposant, poids et prix séparés par ;, solution initiale), exemples de solutions initiales.
Centre : visualisation pas-à-pas (chromosomes, voisins, populations) avec zoom +/−/reset.
Droite : choix de l'algorithme, paramètres spécifiques (taille tabou, température, taux de mutation…), état courant, notes de référence, pseudo-code.

Les boutons d'exemples de solution initiale (Sac vide, Sac plein, Moitié alternée, 5 derniers articles pris) se surlignent en bleu quand tu cliques dessus. Dès que tu édites manuellement le champ « Solution initiale » ou que tu changes n, la surbrillance disparaît : ta solution courante ne correspond plus à un des 4 patterns.

Descente locale (best improvement)

On démarre d'une solution initiale ; à chaque itération on génère tous les voisins (flip d'un bit) et on garde le meilleur, tant qu'il améliore strictement. S'arrête sur un minimum local.

Recherche tabou

Comme la descente, mais on accepte des dégradations pour s'échapper des minima locaux. Une liste tabou de longueur T mémorise les derniers éléments visités pour interdire le retour immédiat. Deux variantes :

Variante A (référence) : la liste tabou contient les solutions visitées.
Variante B (pratique) : la liste tabou contient les indices des derniers articles flippés (swaps récents).

Recuit simulé

À chaque itération, on tire un voisin au hasard. S'il est meilleur, on l'accepte. S'il est moins bon (variation δ < 0), on l'accepte avec une probabilité e^δ/T où T est la température. T décroît géométriquement : T ← T × α.

Au début (T grand), presque tout est accepté → exploration. À la fin (T petit), on rejette presque tout → exploitation. Le bon réglage de T₀ et α est crucial.

Algorithme génétique

Population de chromosomes binaires. À chaque génération :

Sélection par tournoi : tirage de 2 chromosomes, on garde le meilleur. Répété popSize fois → liste de parents.
Croisement à 1 point par paires : chaque couple (P_2k-1, P_2k) produit deux enfants en échangeant leurs préfixes/suffixes au point de coupure k tiré au hasard.
Mutation : chaque bit de chaque enfant est flippé avec probabilité mutRate (≈ 0,1).
Remplacement élitiste : on garde les popSize meilleurs parmi parents+enfants.

La solution finale = le meilleur chromosome jamais rencontré au cours de l'évolution.

À l'étape mutation, trois blocs sont affichés : Parents (issus du tournoi), Enfants avant mutation (issus du croisement), Enfants après mutation (avec bits flippés en jaune). On peut comparer ligne à ligne pour vérifier le nombre de flips.

Comparaison rapide

Algorithme	Idée principale	Échappe minimum local ?
Descente locale	Toujours descendre vers un voisin meilleur	Non
Recherche tabou	Mémoire à court terme pour éviter le retour immédiat	Oui (partiellement)
Recuit simulé	Acceptation probabiliste de mauvais voisins, décroissante	Oui
Algorithme génétique	Population de solutions, croisement + mutation	Oui (exploration globale)

Tutoriels d'utilisation

📘 Flots dans un réseau de transport

Vue d'ensemble de l'écran

Interactions souris sur le graphe

Codage visuel des arcs

Définitions essentielles

Flot complet — procédure gloutonne de référence

Pourquoi un flot complet n'est pas toujours maximum

Flot maximum — Ford-Fulkerson

Comment utiliser les autres exemples

Points-clés à retenir

📘 Routage & Arbres de connexion

Tables de routage et plus courts chemins

Dijkstra — étape par étape

Exemple de référence

Arbres de connexion et Kruskal

Comment lire les visualisations

Points-clés à retenir

📘 Programmation linéaire & Simplexe

Vue d'ensemble de l'écran

Comment saisir le PL

Méthode du simplexe — étape par étape

Visualisation pour les PL à 2 variables

Trois exemples tirés de référence

Points-clés à retenir

📘 PLNE & Branch and Bound

Pourquoi un PLNE est difficile

Relaxation continue

Branch and Bound — principe

Comment lire la visualisation

Trois exemples de référence

Points-clés à retenir

📘 Programmation dynamique

Principe d'optimalité de Bellman

Algorithme 1 — Sac à dos exact, fonction f(i, P)

Comment lire la visualisation (sac à dos)

Exemple de référence

Algorithme 2 — Affectation de tâches à 1 processeur, fonction h(i)

Comment lire la visualisation (affectation)

Quatre exemples

Points-clés à retenir

📘 Métaheuristiques sur le sac à dos élastique

Le problème

Vue d'ensemble

Descente locale (best improvement)

Recherche tabou

Recuit simulé

Algorithme génétique

Comparaison rapide