Optimiser sous contraintes

Une décision d'ingénieur est rarement un calcul libre. Il y a un objectif à maximiser, une marge, un débit, un nombre de machines servies, et il y a des limites qu'on ne franchit pas : un budget, des heures disponibles, une capacité. Le problème n'est pas de trouver la meilleure valeur dans l'absolu, mais la meilleure parmi celles qui sont permises.

Ce chapitre installe la méthode qui résout ce problème quand tout est linéaire. Elle a une particularité remarquable : la solution se trouve toujours à un coin, jamais au milieu, et cela réduit une recherche infinie à l'examen de quelques points.

Poser le problème avant de le résoudre

Un programme linéaire tient en trois parties, et les écrire séparément est la moitié du travail.

Les trois parties

Les variables de décision sont les quantités sur lesquelles on a la main. Elles portent un nom, une unité, et rien d'autre ne varie.

La fonction objectif est la quantité à maximiser ou minimiser, écrite comme une combinaison linéaire des variables.

Les contraintes sont les inégalités que toute solution doit respecter, elles aussi linéaires.

Un atelier, deux produits

Un atelier fabrique deux cartes électroniques, A et B. Chaque carte A rapporte 3, chaque carte B rapporte 5.

La ligne de soudure ne traite que 4 cartes A par jour. Le banc de test ne traite que 6 cartes B par jour. Enfin, l'atelier dispose de 18 heures de montage, une carte A en demandant 3 et une carte B en demandant 2.

Cela s'écrit :

\text{maximiser } 3x + 5y \quad \text{sous } \begin{cases} x \leq 4 \\ 2y \leq 12 \\ 3x + 2y \leq 18 \\ x \geq 0,\ y \geq 0 \end{cases}

Les contraintes de positivité ne sont pas décoratives

Oublier

x \geq 0

y \geq 0

transforme un problème d'atelier en un problème où l'on fabrique un nombre négatif de cartes, et la méthode répondra sans broncher.
Ces deux inégalités portent une information du métier, pas une convention d'écriture : elles disent qu'on ne peut pas défabriquer. Toute contrainte physique doit être écrite, y compris celles qui semblent aller de soi.

Le domaine réalisable

Chaque contrainte coupe le plan en deux et ne garde qu'un côté. L'intersection de tous ces demi-plans est le domaine réalisable : l'ensemble des décisions permises.

Pour l'atelier ci-dessus, ce domaine est un polygone à cinq sommets.

banc de test : y = 6montage : 3x + 2y = 18

Les trois contraintes de l'atelier. Le domaine réalisable est ce qui reste sous les deux droites, à gauche du trait vertical et dans le quart positif. Ses cinq sommets sont marqués, et ce sont les seuls points à examiner.

Le domaine est le polygone délimité par ces trois droites et les deux axes. Sa forme importe moins que ses sommets, et la section suivante dit pourquoi.

Trois issues possibles, et pas une de plus

Le domaine peut être vide : les contraintes se contredisent, et aucune décision n'est permise.

Il peut être non borné dans la direction de l'objectif : on peut faire croître la valeur sans limite, ce qui signale presque toujours une contrainte oubliée.

Sinon il est borné, et un optimum existe.

L'optimum est sur un sommet

C'est le résultat qui rend tout le reste possible.

Pourquoi la solution ne peut pas être au milieu

La fonction objectif est linéaire, donc ses lignes de niveau sont des droites parallèles. Optimiser revient à pousser cette droite aussi loin que possible dans la direction qui améliore, tant qu'elle touche encore le domaine.
Le dernier point de contact d'une droite qui balaie un polygone convexe est nécessairement un sommet, ou une arête entière quand la droite lui devient parallèle. Dans ce second cas, les deux extrémités de l'arête sont optimales elles aussi.
Un point strictement à l'intérieur n'est donc jamais le seul optimum : il existe toujours une direction où l'on peut encore avancer.

La conséquence est décisive. Un domaine contient une infinité de points, et il suffit d'en examiner quelques-uns. Pour l'atelier, cinq.

Sommet	$3x + 5y$
$(0 ; 0)$	0
$(4 ; 0)$	12
$(4 ; 3)$	27
$(2 ; 6)$	36
$(0 ; 6)$	30

L'optimum vaut 36, atteint en fabriquant 2 cartes A et 6 cartes B.

Le contrôle qui attrape une erreur de tracé

Chaque sommet est l'intersection de deux contraintes. Avant d'évaluer l'objectif, vérifier que le point trouvé respecte bien toutes les autres : une intersection de deux droites peut très bien tomber hors du domaine, et l'inclure dans le tableau donne un optimum trop grand.
Sur l'atelier, l'intersection de

x = 4

y = 6

donne

(4 ; 6)

, qui viole la contrainte de montage puisque

3 \times 4 + 2 \times 6 = 24 > 18

. Ce point n'est pas un sommet du domaine, et il rapporterait 42.

Contraintes saturées et contraintes inutiles

À l'optimum $(2 ; 6)$ , regardons chaque contrainte.

Contrainte	À l'optimum	État
$x \leq 4$	$2 \leq 4$	non saturée
$y \leq 6$	$6 \leq 6$	saturée
$3x + 2y \leq 18$	$18 \leq 18$	saturée

Une contrainte saturée est atteinte avec égalité : elle bloque effectivement la solution. Une contrainte non saturée laisse de la marge, et la relâcher ne changerait rien.

Seules les contraintes saturées méritent qu'on y investisse

Acheter une heure de montage supplémentaire améliore la solution, puisque cette contrainte est saturée. Acheter une capacité de soudure supplémentaire n'améliore rien, puisqu'il en reste déjà.
C'est le résultat le plus directement utile du chapitre. Devant une chaîne où l'on veut investir, la question n'est pas « quel poste est le plus lent » mais « quelle contrainte est saturée à l'optimum », et la réponse se lit sur le tableau plutôt que sur l'intuition.

Quand les variables doivent être entières

L'atelier fabrique des cartes, qui ne se découpent pas. L'optimum trouvé donne heureusement des entiers, et ce n'est pas toujours le cas.

Arrondir la solution continue ne donne pas la solution entière

C'est l'erreur la plus fréquente et elle est parfois spectaculaire. La solution continue peut valoir

(2{,}4 ; 5{,}7)

, et ni

(2 ; 6)

, ni

(2 ; 5)

, ni

(3 ; 6)

n'être réalisables ou optimaux.
Pire, la meilleure solution entière peut se trouver loin du point continu, dans un coin du domaine que l'arrondi n'atteint jamais. Le problème en nombres entiers est d'une nature différente, et il est NP-difficile alors que le problème continu ne l'est pas.

La marche à suivre est donc : résoudre en continu pour obtenir une borne, puisque la solution entière ne peut pas faire mieux que la continue, puis chercher la solution entière par une méthode dédiée. La borne continue sert à savoir quand s'arrêter.

À calculer soi-même

Un programme linéaire à deux variables se résout entièrement à la main, et chaque étape se vérifie.

Résoudre l'atelier, sommet par sommet

1.
Combien vaut l'objectif $3x + 5y$ au sommet $(4 ; 3)$ ?
2.
Combien vaut-il au sommet $(2 ; 6)$ ?
3.
Combien vaut-il au sommet $(0 ; 6)$ ?
4.
Quelle est la valeur optimale, parmi les cinq sommets dont les valeurs sont 0, 12, 27, 36 et 30 ?
5.
Combien d'heures de montage le point $(4 ; 6)$ demanderait-il ?
6.
De combien ce point dépasse-t-il les 18 heures disponibles ?
7.
À l'optimum, combien d'heures de montage restent inutilisées ?
8.
Combien de cartes A de plus la ligne de soudure pourrait-elle encore traiter à l'optimum ?

Les deux dernières réponses sont l'essentiel. Le montage ne laisse rien, la soudure laisse deux cartes de marge : investir dans la soudure ne rapporterait donc strictement rien, et investir dans le montage rapporterait immédiatement. Aucune intuition sur « le poste le plus chargé » ne donne cette réponse, et le tableau la donne en deux soustractions.

Où la démarche dérape

Une intersection de deux contraintes prise pour un sommet du domaine.

Un sommet qui n'appartient pas au domaine

Une seule étape est fausse. Désigner laquelle.

L'atelier maximise $3x + 5y$ sous $x \leq 4$ , $y \leq 6$ et $3x + 2y \leq 18$ . On examine le point d'intersection des deux premières contraintes, $(4 ; 6)$ , et l'on cherche le nombre d'heures de montage qu'il consomme, sachant qu'une carte A en demande 3 et une carte B en demande $x$ .

Vérification

Vérification rapideon peut se reprendre

1.Pourquoi l'optimum d'un programme linéaire se trouve-t-il sur un sommet ?

2.Une contrainte non saturée à l'optimum signifie que…

3.Un domaine réalisable non borné signifie que…

4.La solution entière s'obtient-elle en arrondissant la solution continue ?

Exercices type

Combien de sommets faut-il examiner pour un problème à deux variables et cinq contraintes ?

Au plus $\binom{5}{2} = 10$ , puisqu'un sommet est l'intersection de deux contraintes. En pratique bien moins, parce que la plupart de ces intersections tombent hors du domaine.

C'est ce qui rend la méthode graphique praticable à deux variables et impraticable au-delà : à dix variables et vingt contraintes, le nombre de sommets candidats devient astronomique, et c'est précisément le problème que l'algorithme du simplexe résout en ne visitant que les sommets qui améliorent.

Que se passe-t-il si la fonction objectif est parallèle à une arête du domaine ?

Tous les points de cette arête sont optimaux, et il y en a une infinité. Les deux sommets qui la bornent le sont donc aussi, ce qui suffit à trouver la valeur optimale.

C'est un cas fréquent en pratique, et il porte une bonne nouvelle : il laisse le choix. Parmi les solutions également optimales du point de vue de l'objectif, on peut alors en retenir une selon un second critère qui n'était pas modélisé.

Un atelier maximise sa marge et l'optimum dit de ne fabriquer aucun produit B. Que faut-il vérifier ?

Deux choses avant de conclure. D'abord que le modèle contient bien toutes les contraintes, en particulier celles de la demande : un produit qu'on s'est engagé à livrer doit apparaître comme une contrainte $y \geq$ quelque chose.

Ensuite que les marges employées sont les bonnes. Une marge unitaire mal estimée, par exemple en oubliant un coût variable, déplace l'optimum d'un sommet à l'autre, et c'est exactement le genre de décision qu'une erreur de saisie fait prendre.

Pourquoi la solution continue sert-elle de borne au problème entier ?

Parce que toute solution entière est aussi une solution continue : l'ensemble des solutions entières est inclus dans le domaine continu. L'optimum continu ne peut donc pas être moins bon que l'optimum entier.

Cette borne a un usage direct. Quand une solution entière atteint une valeur proche de la borne continue, il devient inutile de chercher plus loin : la marge de progression restante est connue et bornée, et l'on peut arrêter la recherche en connaissance de cause.

Le domaine est vide. Que faut-il faire ?

Chercher quelles contraintes se contredisent, et non chercher une solution. Un domaine vide n'est pas un échec du calcul, c'est un résultat : les exigences posées sont incompatibles entre elles.

La démarche consiste à retirer les contraintes une à une jusqu'à ce que le domaine cesse d'être vide. La dernière retirée est celle qui bloquait, et la discussion porte alors sur elle : est-elle négociable, a-t-elle été mal chiffrée, ou le projet est-il réellement infaisable tel qu'il est posé ?

La méthode

Nommer les variables de décision avec leur unité, avant toute inéquation. Une variable sans unité produit un modèle dont les contraintes ne se comparent pas.
Écrire l'objectif comme une combinaison linéaire, et dire s'il se maximise ou se minimise.
Écrire toutes les contraintes, y compris celles de positivité qui semblent aller de soi.
Tracer le domaine et repérer les sommets, en vérifiant pour chacun qu'il respecte toutes les contraintes et pas seulement les deux qui l'engendrent.
Évaluer l'objectif sur chaque sommet et retenir le meilleur.
Relever les contraintes saturées : ce sont les seules où un investissement rapporte.
Ne jamais arrondir une solution continue pour obtenir une solution entière.
Conclure en français, en disant quoi fabriquer, combien, et quelle limite bloque.

Synthèse

Un programme linéaire se compose de variables de décision, d'une fonction objectif linéaire et de contraintes linéaires.
Le domaine réalisable est l'intersection des demi-plans définis par les contraintes. Il peut être vide, non borné, ou borné.
L'optimum est toujours sur un sommet, parce que les lignes de niveau de l'objectif sont des droites. Cela ramène une infinité de points à quelques-uns.
Une intersection de deux contraintes n'est un sommet du domaine que si elle respecte toutes les autres. C'est le contrôle qui attrape un optimum trop beau.
Une contrainte saturée bloque la solution ; une contrainte non saturée laisse de la marge. Seules les premières méritent un investissement.
Un domaine non borné dans la direction de l'objectif signale presque toujours une contrainte oubliée.
La solution entière ne s'obtient pas en arrondissant la continue. Cette dernière sert de borne, et le problème entier est d'une difficulté supérieure.

Et ensuite

La méthode graphique s'arrête à deux variables. Au-delà, il faut un algorithme qui ne visite que les sommets améliorants, et son coût devient la question centrale : Complexité algorithmique donne les outils pour en juger. Quant au cas entier, il rejoint la famille des problèmes que Satisfiabilité traite par une autre voie.