algorithme de Dantzig

Imaginez une carte dont la zone autorisée est un polygone. Chaque point représente un choix possible, et une hauteur fictive indique la qualité de ce choix. L'algorithme de Dantzig ne visite pas tous les points : il part d'un coin, compare les directions permises et gagne un coin voisin. Il répète ce déplacement tant qu'il peut améliorer le résultat. Dans ce cadre polygonal, où la zone possède des coins admissibles, le dernier coin atteint sans amélioration possible donne la meilleure valeur lorsque le problème possède une solution optimale.

L'algorithme de Dantzig, ou méthode du simplexe, résout un problème d'optimisation linéaire : une fonction objectif linéaire doit être maximisée ou minimisée parmi des variables soumises à des contraintes linéaires. Les points qui satisfont toutes les contraintes forment le domaine admissible. Géométriquement, ce domaine est un polyèdre convexe ; ses coins sont appelés sommets.

La méthode représente un sommet admissible par une solution de base. À chaque itération, elle choisit une variable dont l'entrée peut améliorer l'objectif, détermine quelle variable doit sortir pour préserver les contraintes, puis effectue un pivot. Dans le cas non dégénéré, ce changement de base correspond au passage vers un sommet adjacent ; lors d'un pivot dégénéré, la base peut changer sans que le sommet change. L'arrêt survient lorsque le critère d'amélioration ne désigne plus de déplacement admissible.

Une solution de départ admissible est nécessaire ; si elle n'est pas immédiatement visible, une phase préalable doit en rechercher une. Plusieurs règles de choix du pivot sont possibles et peuvent produire des chemins différents. La méthode est algébrique : le dessin aide avec deux ou trois variables, mais le calcul reste utilisable lorsque le nombre de variables rend la représentation graphique impraticable. George B. Dantzig l'a introduite en 1947.

On part d'une solution de base admissible d'un programme linéaire. Pour une maximisation, on choisit une variable entrante capable d'accroître la fonction objectif, puis une variable sortante qui maintient toutes les contraintes. Le pivot fournit la base voisine.

Pour l'exemple où x et y sont les quantités choisies, le problème est :

Les pivots sont répétés jusqu'à ce qu'aucun déplacement admissible ne puisse améliorer z. Si une direction d'amélioration reste possible sans rencontrer de contrainte, le problème est non borné au lieu de posséder un maximum fini.

La fonction objectif et chaque contrainte doivent être linéaires dans les variables. Il faut aussi un domaine admissible non vide et une solution de base de départ, trouvée directement ou par une phase préalable. Enfin, un maximum fini n'est obtenu que si l'objectif est borné dans la direction recherchée.

Un contre-cas concret apparaît si l'on impose simultanément x ≥ 3 et x ≤ 2 : aucun point ne satisfait les deux contraintes, donc aucun sommet de départ ne peut être retenu. La phase de recherche d'admissibilité doit alors conclure que le problème est impossible. Si les relations ou l'objectif ne sont pas linéaires, il faut employer une méthode adaptée à cette autre structure.

On veut maximiser le score z = 3x + 2y. Les quantités x et y sont positives ou nulles. Elles vérifient x + y ≤ 4 et x ≤ 2. Les quatre sommets admissibles sont (0,0), (2,0), (2,2) et (0,4). Le schéma associé rend visibles le domaine et un trajet possible entre ces sommets.

Étape 1. Au sommet (0,0), le score vaut z = 0. Faire entrer x augmente le score de 3 par unité. La contrainte x ≤ 2 conduit au sommet adjacent (2,0), où z = 3 × 2 + 2 × 0 = 6.

Étape 2. Depuis (2,0), x ne peut plus augmenter, mais y le peut jusqu'à saturer x + y ≤ 4. On atteint (2,2), et z = 3 × 2 + 2 × 2 = 10.

Étape 3. Les déplacements le long des deux arêtes issues de (2,2) n'améliorent pas le score. Le maximum vaut donc 10. Pour le contrôler, on évalue l'autre sommet non parcouru : en (0,4), z = 8, tandis que les deux sommets précédents donnent 0 et 6.

Pour répartir des ressources limitées, on traduit chaque capacité par une contrainte et le gain recherché par la fonction objectif. Le simplexe convient lorsque ces relations sont linéaires ; une relation non linéaire appelle une autre méthode d'optimisation.

Avec deux variables, un tracé du domaine permet de vérifier les sommets à la main. Dès que les variables sont trop nombreuses pour être dessinées, le tableau algébrique du simplexe remplace cette lecture graphique sans changer le principe des sommets adjacents.

Avant d'interpréter le résultat, on contrôle l'admissibilité de la solution, la valeur de l'objectif et le statut d'arrêt. Ce dernier distingue un optimum fini d'un problème impossible ou non borné.

Avec une résolution graphique. Le graphique énumère visuellement les sommets, ce qui devient impraticable au-delà de trois variables. Le simplexe effectue algébriquement les changements de sommet et reste donc formulable en dimension supérieure.

Avec l'optimisation en nombres entiers. Le simplexe ordinaire autorise des valeurs réelles. Si x doit obligatoirement être entier, une solution comme x = 3/2 n'est pas recevable, même si elle optimise le problème linéaire relâché.

Avec un algorithme glouton. Un choix glouton est généralement pris sans retour à partir d'une règle locale propre au problème. Un pivot du simplexe change au contraire une base complète tout en respectant l'ensemble des contraintes linéaires.

Dégénérescence. Plusieurs contraintes peuvent être actives au même sommet. Un pivot peut alors changer la base sans changer le point ni la valeur de l'objectif. Il faut appliquer une règle de pivot qui évite de tourner indéfiniment entre des bases.

Optimum non unique. Si l'objectif reste constant le long d'une arête située au niveau optimal, deux sommets voisins et tous les points du segment qui les relie sont optimaux. Il ne faut pas présenter le sommet retourné comme l'unique solution.

Domaine non borné. Une zone admissible peut s'étendre à l'infini. Ce seul constat ne suffit pas : le maximum est absent seulement lorsqu'une direction admissible améliore indéfiniment l'objectif. Le statut de non-bornage doit remplacer toute valeur optimale fictive.

Variables discrètes. Arrondir séparément les coordonnées d'un optimum réel peut violer une contrainte ou manquer la meilleure solution entière. Lorsque des quantités doivent être entières, le résultat du simplexe sert de relaxation et non de verdict final.

Optimisation linéaire — Replacer le simplexe dans la famille des problèmes où objectif et contraintes sont linéaires.

Polyèdre convexe — Approfondir la géométrie du domaine admissible, de ses faces et de ses sommets.

La programmation linéaire en nombres entiers — Voir ce qui change lorsque les variables ne peuvent plus prendre toutes les valeurs réelles.