Optimiser une quantité sous des contraintes, quand tout s'écrit avec des droites. Une géométrie simple, un théorème décisif et un algorithme qui marche de sommet en sommet.
Un programme linéaire cherche le maximum, ou le minimum, d'une fonction linéaire, sous des contraintes elles aussi linéaires. Le mot « programme » veut dire ici « plan d'action », et non programme informatique.
maximiser z = 5 x + 4 y sous 6 x + 4 y ≤ 24, x + 2 y ≤ 6, y − x ≤ 1, y ≤ 2, x ≥ 0, y ≥ 0
Ce problème servira de fil rouge : une fabrique produit x tonnes de peinture d'extérieur et y tonnes de peinture d'intérieur, avec un bénéfice de 5 et de 4 milliers d'euros par tonne. Deux matières premières sont limitées (24 et 6 tonnes), le marché de la peinture d'intérieur ne dépasse pas celui d'extérieur de plus d'une tonne, et plafonne à 2 tonnes. Les données sont pédagogiques. Les résultats, eux, sont calculés sur place et contrôlés par une seconde méthode.
Planche 1
Qu'est-ce qui est linéaire, et qu'est-ce qui ne l'est pas ?
Une fonction est linéaire si chaque variable y apparaît seule, multipliée par un nombre, et que tout s'additionne : f(x, y) = a x + b y. Cela traduit deux idées concrètes : proportionnalité (deux fois plus de produit, deux fois plus de bénéfice) et additivité (les produits ne se gênent pas et ne s'aident pas).
Bonnes réponses0 sur 8
L'allure d'une fonction linéaire : un plan incliné
La surface z = f(x, y), qui tourne lentement. Une fonction linéaire donne un plan ; les autres se courbent ou se plient.
La même fonction vue de dessus, en bandes de niveau (une couleur = une plage de valeurs). Pour une fonction linéaire, les bandes sont droites, parallèles et de même largeur, et la flèche rouge (a ; b) leur est perpendiculaire.
Test d'additivité : f(u + v) − f(u) − f(v)–
Test de proportionnalité : f(3u) − 3 f(u)–
Verdict des deux tests, sur 2 000 couples au hasard–
Pente mesurée contre (a ; b) : écart–
Une contrainte linéaire coupe le plan en deux
L'inégalité a x + b y ≤ c sépare le plan par une droite : d'un côté les points permis, de l'autre les points interdits. Le coefficient c déplace la droite sans la tourner ; a et b la font tourner.
Chaque point se colore selon qu'il respecte (vert) ou non (gris) la contrainte. Flèche rouge : la direction (a ; b), qui pointe vers le côté interdit quand le signe est ≤.
Part du carré permise, par calcul d'aire–
Même part, 50 000 points au hasard–
Toutes les écritures se ramènent à celle-ci : a x + b y ≥ c équivaut à −a x − b y ≤ −c, et une égalité vaut deux inégalités opposées.
Ce qu'il faut retenir. Ce sont des hypothèses, et le modèle ne vaut que si elles sont raisonnables. Un rabais sur quantité, un effet de seuil ou un produit x·y sortent du cadre. Une constante ajoutée, comme 4x − y + 7, ne gêne pas : elle décale la valeur de l'objectif sans changer le meilleur point.
Planche 2
La résolution graphique, en six gestes
Avec deux variables, chaque plan de production est un point d'une feuille. On peut donc résoudre le problème à la règle : c'est la méthode qui fait comprendre toutes les autres.
→→→→→
Sommet optimal (x ; y)–
Valeur optimale z–
Contraintes qui se croisent à l'optimum–
Contrôle : simplexe exact, écart sur z–
Le sommet reste optimal si le bénéfice d'extérieur est entre–
Contrôle de cette fourchette, par balayage–
Ce qu'il faut retenir. Faites varier les bénéfices : la droite de niveau tourne. Le meilleur sommet ne bouge pas, puis saute d'un coup au voisin quand la droite devient parallèle à un côté. Le plan optimal est donc stable : une petite erreur sur les prix ne change pas forcément la décision. C'est une précieuse qualité de ce type de modèle.
Planche 3
Domaine admissible, sommets et optimum
Le domaine admissible est l'ensemble des points qui respectent toutes les contraintes. Il a une forme très particulière, et de cette forme découle le théorème fondamental : si un optimum existe, il y en a un sur un sommet. Cliquez deux points A et B pour le constater.
Ronds verts : intersections admissibles, les sommets. Croix grises : intersections de deux droites, mais hors du domaine. Le segment [A ; B] et, depuis B, la montée de z jusqu'au bord. Les traits violets relient B aux sommets dont il est la moyenne pondérée.
–
Intersections de deux droites–
Dont sommets admissibles–
Segment [A ; B] à l'intérieur du domaine–
z(B) puis moyenne pondérée des z des sommets–
En montant depuis B jusqu'au bord–
Meilleur z sur 50 000 points admissibles au hasard–
Le raisonnement en trois temps. Le domaine est convexe : le segment entre deux points admissibles reste admissible, car chaque contrainte linéaire l'est le long d'une droite. Tout point du domaine est donc une moyenne pondérée des sommets. Or z est linéaire : z en ce point est la même moyenne des z des sommets, et une moyenne ne dépasse jamais son plus grand terme. Il suffit de regarder les sommets. Ajoutez x · y ≤ 2 : le domaine se creuse, le segment sort, le meilleur point n'est plus à l'intersection de deux droites, et le sommet (1 ; 2) devient un piège, où aucun petit pas n'améliore, à z = 13 au lieu de 20,35.
Planche 4
La méthode du simplexe : marcher de sommet en sommet
Dantzig, en 1947, a eu l'idée qui rend tout praticable : partir d'un sommet et passer à un sommet voisin meilleur, jusqu'à ce qu'aucun voisin ne fasse mieux. Comme le domaine est convexe, un sommet sans meilleur voisin est forcément le meilleur de tous. Il reste à traduire cette promenade en calcul.
La mise en tableau. On transforme chaque inégalité en égalité par une variable d'écart, qui mesure ce qu'il reste de la ressource : 6x + 4y + e₁ = 24. Au départ, on ne produit rien : x = y = 0 et les écarts valent tout le stock. Les variables nulles sont dites hors base, les autres en base. Un sommet, c'est un choix de variables nulles, et une variable nulle signifie : « on est sur cette droite ».
Le sommet courant (rouge) et le chemin parcouru. Traits épais : les droites sur lesquelles on se trouve, celles dont la variable est hors base.
–
Les trois gestes.Qui entre ? Une colonne négative dans la ligne z : augmenter cette variable fait monter z. Cliquez sur l'en-tête orange de votre choix. Qui sort ? On divise la dernière colonne par les coefficients positifs de la colonne : le plus petit rapport est la première ressource épuisée. Pivoter : on rend la colonne égale à celle d'une variable en base, par des combinaisons de lignes.
Sommet courant–
z courant–
Pivots effectués–
Contrôle : meilleur sommet par énumération–
Essayez deux chemins. Si x entre d'abord, comme le dicte la règle du plus fort coefficient, deux pivots suffisent. Si y entre d'abord, on fait le tour du polygone par l'autre côté, en quatre pivots, pour arriver au même sommet (3 ; 1,5). Le tableau final donne la réponse : dernière colonne pour les valeurs, ligne z sans aucun négatif pour la preuve d'optimalité.
Rien ne change en dimension 3, sauf le décor : le domaine devient un polyèdre, et le tableau grandit d'une colonne. Le simplexe suit les arêtes. Il y a maintenant trois variables, x, y et w, et l'objectif z reste à maximiser. Faites tourner la figure en la faisant glisser, et choisissez d'autres objectifs.
Le polyèdre 2x + 3y + w ≤ 5, 4x + y + 2w ≤ 11, 3x + 4y + 2w ≤ 8, x, y, w ≥ 0. Chemin rouge : les pivots du simplexe. Point vert : le meilleur sommet trouvé par énumération.
Sommet–
Valeur–
Pivots du chemin–
Sommets du polyèdre / contrôle par énumération–
Examiner tous les sommets est vite impossible : avec n variables et m contraintes, il peut y en avoir jusqu'au nombre de combinaisons C(n + m ; n). Le simplexe n'en visite d'ordinaire qu'une poignée. Mais il existe des problèmes piégés, comme celui de Klee et Minty (1972), où il les visite presque tous.
Logarithme décimal du nombre de sommets à examiner dans le pire cas (orange) et des pivots moyens du simplexe sur 200 problèmes tirés au hasard (bleu), avec m = n.
Le cube déformé de Klee et Minty : pivots mesurés (rouge) contre 2ⁿ − 1 (trait), avec la règle du plus fort coefficient, en échelle logarithmique. En bleu, les problèmes au hasard, avec m = n.
Sommets possibles au plus, C(n + m ; n)–
Pivots moyens, 200 tirages–
Le plus grand nombre de pivots observé–
Contrôle sur de petits problèmes : simplexe contre tous les sommets–
Une énigme encore ouverte. Sur nos tirages, très faciles, il faut quelques pivots ; sur les problèmes réels, de l'ordre de quelques fois m. Pourtant le pire cas est exponentiel, et personne ne connaît de règle de pivot qui garantisse le contraire. D'autres méthodes y parviennent en théorie : l'ellipsoïde de Khachiyan (1979), les points intérieurs de Karmarkar (1984). Le simplexe reste très utilisé, car rapide en pratique.
Planche 5
Quand tout ne se passe pas bien : les cas particuliers
Un programme linéaire n'a pas toujours une solution unique. Il y a exactement quatre issues possibles, et le simplexe sait reconnaître chacune. Trois onglets pour voir les cas particuliers, et une carte pour les réunir.
Les contraintes se contredisent : le domaine est vide. Ici, il faut 3x + 4y ≥ t, alors que 2x + y ≤ 2 ne le permet pas toujours. Comme l'origine n'est plus admissible, le simplexe doit d'abord trouver un sommet : c'est la phase 1. On ajoute une variable artificielle a₁ qui comble ce qui manque, et on cherche à l'annuler. Si elle ne peut pas revenir à 0, le domaine est vide.
Bleu : ce que permet 2x + y ≤ 2. Vert : le côté permis par 3x + 4y ≥ t. Les deux doivent se recouvrir.
–
Artificielle a₁ en fin de phase 1 : ce qui manque–
Contrôle : t − meilleur 3x + 4y sur le domaine–
Le signe à reconnaître : phase 1 terminée, et l'artificielle reste positive. Sa valeur est utile : elle dit de combien il faudrait relâcher l'exigence. En pratique, cela indique une erreur de données ou des demandes incompatibles, et c'est aux décideurs de trancher.
L'objectif peut croître sans fin. Attention : un domaine non borné ne suffit pas. Ici la bande −3 ≤ x − y ≤ 2 s'étend vers l'infini dans la direction (1 ; 1). Tout dépend du sens de l'objectif. Faites varier ses coefficients.
La bande admissible, coupée à la limite de la figure. Flèche verte : le sens où z augmente. Point rouge : le point du simplexe, qui s'échappe si rien ne l'arrête.
–
Produit scalaire objectif · (1 ; 1)–
Résultat / contrôle géométrique–
z au point qui s'échappe–
Le signe à reconnaître : une variable peut entrer, car sa colonne est négative en ligne z, mais aucun coefficient de la colonne n'est positif. Rien ne l'arrête : aucune ressource ne s'épuise. Dans la réalité, personne ne gagne l'infini : c'est toujours qu'une contrainte a été oubliée.
L'objectif est parallèle à un côté du domaine : deux sommets ex æquo, et tout le segment qui les relie est optimal. Il y a donc une infinité de solutions. Sur cet exemple, cela arrive pour deux valeurs exactes du curseur : a = 2 et a = 6.
Trait vert : la droite de niveau optimale. Quand elle longe un côté, tout ce côté est optimal (en rouge), et le point violet s'y promène.
–
z optimal–
z au point violet, écart avec l'optimum–
Le signe à reconnaître : dans le tableau final, une variable hors base a un 0 en ligne z. La faire entrer ne change pas z, mais mène à un autre optimum : essayez le bouton. Cette liberté est une bonne nouvelle, car on peut alors choisir parmi ces plans selon un critère que le modèle ne contient pas.
Voici tous les cas sur une même carte. Le domaine reste celui de deux contraintes fixes, x − 2y ≤ 2 et y − 2x ≤ 2, plus une contrainte mobile : cos φ · x + sin φ · y ≤ t. Chaque pixel de la carte est un programme linéaire, résolu par le simplexe. Cliquez sur la carte pour voir le problème correspondant.
Horizontalement, l'orientation φ de la contrainte mobile ; verticalement, sa position t. Bleu : optimum unique. Orange : non borné. Rouge : sans solution. Violet : infinité d'optimums, en trait là où la contrainte mobile est parallèle à l'objectif.
Le problème du point choisi sur la carte. Trait épais : la contrainte mobile. Flèche verte : l'objectif.
–
Point choisi (φ ; t)–
Pivots du simplexe–
Optimum unique, part de la carte–
Non borné, part de la carte–
Sans solution, part de la carte–
Contrôle : désaccords avec le découpage géométrique–
Ce que dit la carte. Les trois premières issues occupent des régions : une petite erreur de données ne les change pas, sauf près d'une frontière. Les optimums multiples n'occupent qu'une ligne sans épaisseur : avec des coefficients pris au hasard, on ne tombe jamais dessus. Pourtant, ils sont fréquents en pratique, car les données réelles sont souvent rondes et les coûts égaux. Faites varier θ : le trait violet suit l'objectif, et les frontières bougent à leur façon. Deux réglages font exception, θ = −90° et θ = 180° : l'objectif est alors parallèle à un axe, côté fixe du domaine, et ce sont des régions entières qui deviennent violettes. C'est exactement ce qui arrive avec des données « rondes ».
Comment reconnaître chaque issue
Issue
Sur la figure
Dans le tableau du simplexe
Que faire ?
Optimum unique
La droite de niveau touche un seul sommet
Aucun négatif en ligne z, aucun 0 hors base
Lire la solution
Plusieurs optimums
La droite longe un côté
Aucun négatif, mais un 0 sur une variable hors base
Choisir selon un autre critère
Non borné
On peut glisser à l'infini
Colonne entrante sans aucun coefficient positif
Chercher la contrainte oubliée
Sans solution
Domaine vide
Phase 1 finie, artificielle encore positive
Revoir données et exigences
Ce qu'il faut garder
La géométrie
Des contraintes linéaires découpent un polygone, ou un polyèdre, convexe. Une fonction linéaire a des niveaux plats. Le meilleur point se trouve donc sur un sommet, si un optimum existe.
L'algorithme
Le simplexe passe d'un sommet à un voisin meilleur. Qui entre ? Qui sort ? Pivoter. Quand la ligne z n'a plus de négatif, la convexité garantit que c'est fini.
Le diagnostic
Sans solution, non borné, plusieurs optimums : ce ne sont pas des pannes. Chaque issue a son signe dans le tableau, et dit quelque chose du problème réel.
Pour aller plus loin
Dans ce cahier.Modéliser un problème de décision montre comment écrire le modèle. La recherche opérationnelle aborde la dualité et les prix duaux, que cette page laisse de côté. Le problème de transport et Le problème d'affectation sont des programmes linéaires à structure particulière.
Dégénérescence. Quand plus de deux droites passent par un même sommet (en dimension 2), un pivot peut laisser z inchangé, et une règle mal choisie peut, en théorie, tourner en rond. La règle de Bland, qui fait entrer et sortir le premier candidat dans l'ordre des variables, garantit que cela n'arrive pas.
Sur les calculs. Les tableaux affichés sont calculés en fractions exactes. La carte et les statistiques utilisent une version en nombres à virgule, à deux phases. Les problèmes au hasard ont des coefficients positifs, tirés uniformément : ils sont faciles, et ne prétendent pas représenter les problèmes industriels.