Optimiser sous contraintes

Combien fabriquer, et quel poste agrandir ?

Un atelier dispose de 18 heures de montage par jour, d'une ligne de soudure et d'un banc de test. Il fabrique deux cartes électroniques, qui ne rapportent pas la même marge et n'occupent pas les mêmes postes. Combien fabriquer de chaque carte ? Et si un budget se libère, quel poste agrandir : le montage, la soudure ou le banc de test ? Le chapitre sur la complexité mesurait ce que coûte un calcul ; celui-ci pose d'abord la décision.

Une décision d'ingénieur est rarement un calcul libre. Il y a un objectif à atteindre au mieux, une marge ou un débit à maximiser, un coût à minimiser, 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 : quand une meilleure décision existe, il y en a toujours une à un coin du domaine des décisions permises, et cela réduit une recherche infinie à l'étude de quelques points. La réponse chiffrée à la question de l'atelier vient à la fin du chapitre.

Travailler seul

Chaque cadre de calcul, chaque quiz et chaque question à déplier est précédé d'un rappel de cours : la notion, sa formule et un petit exemple résolu. Le lire avant de répondre. Les calculs se font à la main ; le seul bloc Python du chapitre vérifie ces calculs avec un solveur, et il n'y a rien à y écrire.

Poser le problème avant de le résoudre

Un problème de ce type s'appelle un programme linéaire : « programme » au sens de plan d'action, pas de code, et « linéaire » parce que tout s'y écrit comme une somme de variables multipliées chacune par un nombre fixe, comme $3x + 5y$ , sans produit $xy$ , sans carré, sans racine. Il 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 et une unité. Tout le reste, prix, capacités, durées, est une donnée fixée du problème.

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 une marge de 3, chaque carte B une marge de 5, en centaines d'euros : 300 € et 500 €.

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.

On note $x$ le nombre de cartes A fabriquées par jour et $y$ le nombre de cartes B : ce sont les deux variables de décision. La marge d'une journée vaut $3x + 5y$ , en centaines d'euros, et chaque limite devient une inégalité :

\text{maximiser } 3x + 5y \quad \text{sous } \begin{cases} x \leq 4 & \text{(soudure)} \\ y \leq 6 & \text{(banc de test)} \\ 3x + 2y \leq 18 & \text{(montage, en heures)} \\ x \geq 0,\ y \geq 0 \end{cases}

Les contraintes de positivité ne sont pas décoratives

Sur l'atelier, oublier

x \geq 0

y \geq 0

passe inaperçu, mais par chance : le banc de test plafonne les cartes B. Sans lui, rien n'empêcherait de « défabriquer » des cartes A pour libérer des heures de montage et les donner aux cartes B, qui rapportent 2,5 par heure de montage contre 1 pour les cartes A, et la marge croîtrait sans limite. De même, si une carte B coûtait 1 au lieu de rapporter 5, l'objectif deviendrait

3x - y

, et sans

y \geq 0

chaque carte « fabriquée » sous zéro ajouterait 1 à la marge.
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.

L'atelier tient en trois phrases, et ses contraintes se lisent directement. Les données d'un vrai problème arrivent plus souvent en tableau, et c'est là que la traduction se trompe.

Rappel de cours : une contrainte par ressource

Un tableau de données a une ligne par ressource, une colonne par produit, et une dernière colonne pour ce qui est disponible. Chaque contrainte lit une ligne : ce que chaque produit consomme de cette ressource, multiplié par la quantité fabriquée, ne dépasse pas ce qui en est disponible.

(\text{consommation d'un produit 1}) \times x + (\text{consommation d'un produit 2}) \times y \leq \text{disponible}

Les deux membres s'écrivent dans la même unité. Une limite « au plus » donne $\leq$ , une exigence « au moins » donne $\geq$ . Les solveurs n'acceptent souvent que des « au plus » : on retourne alors une exigence en multipliant ses deux membres par $-1$ , ce qui change le sens de l'inégalité, et $b \geq 30$ devient $-b \leq -30$ .

Exemple résolu. Une imprimerie tire chaque jour $a$ affiches et $b$ brochures, et un client exige au moins 30 brochures par jour.

Ressource	Affiche	Brochure	Disponible
Presse	2 min	3 min	6 h
Massicot	1 min	4 min	5 h

La presse lit sa ligne, en minutes : $2a + 3b \leq 360$ , puisque 6 heures font 360 minutes.
Le massicot : $a + 4b \leq 300$ .
Le client : $b \geq 30$ , un « au moins ».
Et toujours $a \geq 0$ , $b \geq 0$ .

Trois fautes de traduction

Lire une colonne au lieu d'une ligne. La colonne « affiche » mélange deux ressources : ses 2 minutes de presse et sa minute de massicot ne s'additionnent pas, puisque ce ne sont pas les mêmes machines.

Des unités qui ne se répondent pas. Des minutes par affiche face à des heures disponibles : $2a + 3b \leq 6$ n'autoriserait que trois affiches par jour.

Un « au moins » écrit « au plus ». $b \leq 30$ permettrait de ne rien livrer au client, et interdirait de dépasser sa commande.

Vérification rapideon peut se reprendre

1.Dans un autre atelier, une carte A demande 3 heures de montage et 1 heure de test ; une carte B, 2 heures de montage et 4 heures de test. Le test dispose de 20 heures. Quelle contrainte écrire pour le test ?

2.Une affiche demande 2 minutes de presse, une brochure 3 minutes, et la presse tourne 5 heures par jour. Quelle contrainte écrire pour la presse ?

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. Ses coins s'appellent les sommets, et ce sont eux qui comptent.

Rappel de cours : tracer une contrainte, trouver un sommet

Tracer une contrainte. La frontière de $ax + by \leq c$ est la droite $ax + by = c$ . Deux points suffisent à la tracer, et les plus simples sont sur les axes : poser $y = 0$ donne le point où elle coupe l'axe des $x$ , poser $x = 0$ celui où elle coupe l'axe des $y$ . Pour savoir quel côté garder, tester un point qui n'est pas sur la droite, l'origine le plus souvent : si $(0 ; 0)$ respecte l'inégalité, on garde le côté de l'origine, sinon l'autre.

Pour le montage, $3x + 2y \leq 18$  : la droite $3x + 2y = 18$ passe par $(6 ; 0)$ et par $(0 ; 9)$ . En $(0 ; 0)$ , $0 \leq 18$ est vrai, et le domaine est du côté de l'origine. Une contrainte comme $x \leq 4$ a pour frontière une droite verticale, $y \leq 6$ une droite horizontale.

Trouver un sommet. Un sommet est un point où deux frontières se croisent. On écrit les deux contraintes en égalités, puis on résout le système de deux équations à deux inconnues : isoler une inconnue dans la première, la reporter dans la seconde.

Exemple résolu, hors de l'atelier : $2x + y = 11$ et $x + 3y = 13$ . La première donne $y = 11 - 2x$  ; reportée dans la seconde, $x + 3(11 - 2x) = 13$ , soit $x + 33 - 6x = 13$ , donc $-5x = -20$ et $x = 4$ , puis $y = 11 - 8 = 3$ . Le point $(4 ; 3)$ vérifie bien les deux égalités : $8 + 3 = 11$ et $4 + 9 = 13$ .

Un point de croisement n'est un sommet du domaine que s'il respecte aussi toutes les autres contraintes. C'est le contrôle à ne jamais sauter.

Pour l'atelier, le domaine est un polygone à cinq sommets. La figure le dessine : chaque zone grisée est le côté interdit d'une contrainte, et le polygone coloré qui reste est le domaine. Les boutons qui cherchent le meilleur point entier serviront à la section sur les nombres entiers.

Polygone des contraintesmaximiser 3 x + 5 y

Droite: 3 x + 5 y = 15
Point retenu: aucun

Glisser la droite orange, ou la régler au curseur. Zone grisée : interdite par une contrainte. Points pleins : points entiers réalisables. Au clavier : Tab jusqu'au tracé, flèches pour parcourir la grille, Entrée pour retenir un point, Page haut ou bas pour avancer la droite.

Marge de la droite15Marge par unité de x3Marge par unité de y5

Chercher le point entier le plus rentable : faire glisser la droite vers les grandes marges, puis retenir un point.

L'atelier. Zone grisée : interdite par une contrainte. Losanges : les cinq sommets. La droite orange rassemble les décisions de même marge, en centaines d'euros.

À manipuler

Cliquer un point plein du polygone, par exemple

(2 ; 6)

 : la figure le retient et affiche sa marge. Cliquer ensuite le point pâle

(4 ; 6)

, où la soudure croise le banc de test : la figure le refuse, montage dépassé. C'est le contrôle du rappel, fait par la figure : un croisement de deux frontières n'est un sommet que s'il respecte toutes les autres contraintes.

Trois sommets se lisent sur les axes et les plafonds : $(0 ; 0)$ , $(4 ; 0)$ et $(0 ; 6)$ . Les deux autres sont des croisements avec le montage, et se calculent.

Les sommets de l'atelier et leur marge

1.
Au sommet où la soudure, $x = 4$ , croise le montage, $3x + 2y = 18$ , combien de cartes B l'atelier fabrique-t-il ?
2.
Au sommet où le banc de test, $y = 6$ , croise le montage, combien de cartes A ?
3.
Que vaut la marge $3x + 5y$ au sommet $(0 ; 0)$  ?
4.
Et au sommet $(4 ; 0)$  ?
5.
Et au sommet où la soudure croise le montage ?
6.
Et au sommet où le banc de test croise le montage ?
7.
Et au sommet $(0 ; 6)$  ?

Le meilleur des cinq est le sommet $(2 ; 6)$ , à 36, soit 3 600 € par jour, et il n'y a rien d'autre à examiner : c'est la propriété que la section suivante justifie. Avant cela, une question : un programme linéaire a-t-il toujours un meilleur point ?

Rappel de cours : vide, non borné, ou un optimum

Il y a trois issues possibles, et pas une de plus.

Le domaine peut être vide : les contraintes se contredisent, et aucune décision n'est permise. Si un client exige au moins 7 cartes B par jour, la contrainte $y \geq 7$ contredit le banc de test, $y \leq 6$ .

L'objectif peut être non borné : le domaine s'étend sans fin dans une direction qui améliore, et la valeur croît sans limite. Sans le banc de test ni le montage, rien n'arrêterait $y$ , ni donc la marge. Ce cas signale presque toujours une contrainte oubliée.

Sinon un optimum existe. C'est toujours le cas quand le domaine est borné, et cela peut l'être aussi sur un domaine infini qui ne s'étend que dans des directions qui n'améliorent pas, par exemple quand on minimise un coût sous des contraintes « au moins », comme dans l'exemple qui suit.

Minimiser un coût : un chantier et ses deux carrières

Un chantier doit recevoir au moins 8 t de sable et au moins 7 t de gravier. Un camion de la carrière A apporte 2 t de sable et 1 t de gravier pour 300 €, un camion de la carrière B 1 t de sable et 2 t de gravier pour 200 €. Avec $a$ camions de A et $b$ camions de B :

\text{minimiser } 300a + 200b \quad \text{sous } \begin{cases} 2a + b \geq 8 & \text{(sable, en tonnes)} \\ a + 2b \geq 7 & \text{(gravier, en tonnes)} \\ a \geq 0,\ b \geq 0 \end{cases}

Le domaine n'a pas de plafond : rien n'interdit cent camions. Il a trois sommets. Sur l'axe des $b$ , $(0 ; 8)$ , où le sable est tout juste suffisant ; sur l'axe des $a$ , $(7 ; 0)$ , où c'est le gravier ; et leur croisement, où les deux exigences sont tout juste satisfaites : $b = 8 - 2a$ , reporté dans $a + 2b = 7$ , donne $a + 16 - 4a = 7$ , donc $a = 3$ et $b = 2$ . Les trois sommets coûtent 1 600 €, 1 300 € et 2 100 €.

S'éloigner des sommets ne fait que coûter plus, et c'est pourquoi ce domaine sans plafond a un optimum : 3 camions de A et 2 de B, pour 1 300 €. Le plus petit coût est atteint sur un sommet, comme la plus grande marge de l'atelier, pour la raison que donne la section suivante.

Vérification rapideon peut se reprendre

Sur son domaine, l'objectif d'un programme linéaire peut croître sans limite. Que faut-il en conclure ?

L'optimum est sur un sommet

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

Rappel de cours : la ligne de niveau, et pourquoi l'optimum est sur un sommet

Les décisions qui donnent une même valeur $z$ de l'objectif forment une droite, la ligne de niveau $3x + 5y = z$ . Elle se trace comme une contrainte, par ses points sur les axes : la ligne $3x + 5y = 30$ , qui rassemble les décisions à 3 000 €, passe par $(10 ; 0)$ et par $(0 ; 6)$ . Changer $z$ la déplace parallèlement à elle-même : à 36, elle passe par $(12 ; 0)$ et par $(0 ; 7{,}2)$ . Optimiser revient à la pousser aussi loin que possible dans la direction qui améliore, tant qu'elle touche encore le domaine.

Le domaine est convexe : il n'a ni creux ni partie rentrante, parce qu'aucun demi-plan n'en a et que leur intersection n'en crée pas. Le dernier point de contact d'une droite qui balaie un tel polygone est donc 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 optimal : autour de lui il reste de la place, et la droite peut encore avancer.

La figure du domaine, plus haut, le fait voir. Y glisser la droite orange vers les grandes marges, ou la régler au curseur « Marge de la droite », et lire la valeur écrite le long du trait. Le dernier point du domaine qu'elle touche avant d'en sortir est un sommet, $(2 ; 6)$ , à 36. Régler ensuite le curseur « Marge par unité de y » à 2 : la droite devient parallèle au montage, et en la poussant à 18 elle se pose sur toute une arête, de $(4 ; 3)$ à $(2 ; 6)$ .

Le plan $(2 ; 6)$ tient tant qu'une carte B rapporte au moins 2 et qu'une carte A rapporte au plus 7,5 : entre ces bornes, la droite pivote sans changer de dernier point de contact. Les deux curseurs de marge, déplacés un seul à la fois, le montrent.

La conséquence est décisive. Un domaine contient une infinité de points, et il suffit d'en examiner quelques-uns : pour l'atelier, les cinq sommets dont la marge a été calculée plus haut, 0, 12, 27, 36 et 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.

Vérification rapideon peut se reprendre

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

Contraintes saturées, restes et prix

À l'optimum $(2 ; 6)$ , on examine chaque contrainte : ce qu'elle permet, ce que le plan en consomme, et ce qui en reste.

Rappel de cours : le reste d'une contrainte, et la saturation

Le reste d'une contrainte « au plus », en un point, est ce qu'elle permet moins ce que le point en consomme :

\text{reste} = \text{limite} - \text{consommation}

Positif, la contrainte laisse du jeu. Nul, elle est saturée : atteinte avec égalité, elle bloque effectivement la solution. Négatif, elle est violée, et le point n'est pas réalisable. Les solveurs appellent ce reste la variable d'écart de la contrainte.

Exemple résolu, au sommet $(4 ; 3)$  : la soudure permet 4 cartes A et en emploie 4, reste 0, saturée ; le banc de test permet 6 cartes B et en emploie 3, reste 3 ; le montage permet 18 heures et en emploie $3 \times 4 + 2 \times 3 = 18$ , reste 0, saturé.

Contrainte	Consommation à l'optimum $(2 ; 6)$	Reste	État
Soudure, $x \leq 4$	2 cartes A	2	non saturée
Banc de test, $y \leq 6$	6 cartes B	0	saturée
Montage, $3x + 2y \leq 18$	$3 \times 2 + 2 \times 6 = 18$ heures	0	saturée

Relâcher une contrainte, c'est repousser sa limite : 5 cartes A par jour en soudure au lieu de 4, par exemple. Relâcher une contrainte non saturée ne changerait rien, puisqu'il en reste déjà.

Seule une contrainte saturée peut mériter un investissement. Acheter une heure de montage peut améliorer la solution, puisque cette contrainte est saturée ; acheter de la soudure n'améliore rien, puisqu'il en reste. Saturée est une condition nécessaire, pas suffisante : quand plusieurs contraintes bloquent au même point, en relâcher une seule peut ne rien rapporter, et c'est le cas à 24 heures de montage, comme la fin de cette section le montre. Le gain se calcule.
Devant une chaîne où l'on veut investir, la question n'est donc pas « quel poste est le plus lent » mais « quelle contrainte est saturée à l'optimum, et que rapporte une unité de plus » : la réponse se lit sur le tableau, puis se calcule, plutôt que sur l'intuition.

Rappel de cours : le prix d'une contrainte, et comment le calculer

Le prix d'une contrainte est ce que l'optimum gagne quand on relâche cette contrainte d'une unité, les autres restant inchangées. Les solveurs l'appellent prix dual. Il vaut zéro pour une contrainte non saturée. Pour une contrainte saturée, il se calcule en quatre temps.

Relâcher la contrainte d'une unité.
Résoudre de nouveau le système des contraintes qui étaient saturées, la contrainte relâchée comprise : le sommet optimal glisse.
Vérifier que le nouveau point respecte toutes les autres contraintes. S'il en viole une, le prix calculé ne vaut pas : on est sorti de sa plage de validité.
Faire la différence entre la nouvelle valeur de l'objectif et l'ancienne.

Exemple résolu, le montage de l'atelier. On porte les heures de 18 à 19. Le banc de test reste saturé, $y = 6$ , et le montage devient $3x + 2y = 19$  : $3x = 19 - 12 = 7$ , donc $x = 7/3$ . Le point $(7/3 ; 6)$ respecte la soudure, puisque $7/3 \leq 4$ . La marge vaut $3 \times \frac{7}{3} + 5 \times 6 = 37$ , contre 36 : une heure de montage vaut 1, soit 100 €.

Le banc de test, saturé lui aussi, a son prix : porter sa capacité de 6 à 7 cartes B, le montage restant saturé, donne $3x = 18 - 14$ , donc $x = 4/3$ , qui respecte la soudure, et une marge de $3 \times \frac{4}{3} + 5 \times 7 = 39$ . Une carte de capacité de test vaut donc 3, soit 300 €. La soudure, qui garde un reste, vaut 0.

Que $7/3$ ne soit pas un nombre entier de cartes n'importe pas ici : le prix se lit sur le modèle continu. En cartes entières, il se lit par paquets. Une dix-neuvième heure seule ne fait aucune carte de plus ; il en faut trois pour une carte A, qui rapporte 3, soit bien 1 par heure. Et une septième carte de capacité de test ne rapporte que 2, en passant de $(2 ; 6)$ à $(1 ; 7)$ .

Ces nombres transforment une intuition en décision. Acheter une heure de montage se justifie tant qu'elle coûte moins de 100 € ; acheter de la soudure ne se justifie à aucun prix, puisque son reste n'est déjà pas employé. Et le prix n'est valable que localement. Le sommet optimal glisse le long de $y = 6$ tant que $x$ reste entre 0 et 4, c'est-à-dire tant que les heures de montage restent entre 12 et 24 : c'est la plage de validité du prix. Au-delà de 24 heures, la soudure devient saturée à son tour, l'optimum se fige en $(4 ; 6)$ , et une heure de plus ne rapporte plus rien : le prix du montage tombe à 0.

Vérification rapideon peut se reprendre

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

2.À 24 heures de montage, l'optimum de l'atelier est $(4 ; 6)$ , où la soudure, le banc de test et le montage sont saturés tous les trois. Que rapporte une vingt-cinquième heure de montage ?

Vérifier avec un solveur

Un solveur rend l'optimum, les restes et les prix d'un seul coup. Il ne procède pas comme la méthode graphique : il ne visite que des sommets qui améliorent l'objectif, ce qui compte dès que les variables se multiplient. Sur l'atelier, il doit retrouver les nombres calculés à la main, et le bloc ci-dessous le vérifie avec linprog, de la bibliothèque scipy. Le premier bloc qui importe scipy met quelques secondes à démarrer.

main.py

Sortie

>_ Prêt à exécuter…

Le solveur affiche l'optimum [2. 6.] et la marge 36.0, puis les restes [2. 0. 0.], dans l'ordre soudure, banc de test, montage, et les prix [0. 3. 1.] : ceux du tableau et des deux rappels. Le bloc change le signe des prix, comme celui de la marge, puisque le solveur a minimisé l'opposé de la marge. L'atelier de programmation linéaire du parcours Recherche opérationnelle se sert de ces trois lectures sur des problèmes que la méthode graphique ne suit plus.

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. Un petit exemple suffit : maximiser $21x + 11y$ sous $7x + 4y \leq 13$ , avec $x$ et $y$ entiers positifs. Une carte C demande 7 heures et rapporte 21, une carte D demande 4 heures et rapporte 11, et l'atelier dispose de 13 heures.

En continu, l'heure rapporte 3 sur C et 2,75 sur D : tout va à C, soit $x = 13/7 \approx 1{,}86$ et $y = 0$ , pour 39. Arrondir au plus proche donne $(2 ; 0)$ , qui demande 14 heures : hors du domaine. Arrondir vers le bas donne $(1 ; 0)$ , qui rapporte 21, et même $(1 ; 1)$ ne rapporte que 32. La meilleure solution entière est $(0 ; 3)$ , qui rapporte 33 : aucune carte C, dans un tout autre coin du domaine que le point continu.

Le problème en nombres entiers est d'une nature différente : aucune méthode connue ne le résout rapidement dans tous les cas dès qu'il grandit, alors que le problème continu se résout vite même avec des milliers de variables. Il appartient à la famille des problèmes que le chapitre sur la coloration des graphes appelle NP-complets : vérifier une solution proposée est rapide, en trouver une optimale peut demander un temps qui croît exponentiellement.

Polygone des contraintesmaximiser 21 x + 11 y

Droite: 21 x + 11 y = 21
Point retenu: aucun

Marge de la droite21Marge par unité de x21Marge par unité de y11

Chercher le point entier le plus rentable : faire glisser la droite vers les grandes marges, puis retenir un point.

Les cartes C et D, 13 heures d'atelier. Zone grisée : interdite. Points pleins : les fabrications entières possibles.

À manipuler

Pousser la droite orange vers les grandes marges et retenir le point plein qui semble le plus rentable, puis le vérifier. Demander ensuite la suite, dans l'ordre : l'optimum continu, son arrondi, puis le meilleur point entier, et comparer leur place dans la figure.

Rappel de cours : la borne continue, et comment chercher l'entier

Toute solution entière est aussi une solution du problème continu. L'optimum continu est donc une borne : la meilleure solution entière ne peut pas le dépasser.

La marche à suivre : résoudre en continu pour obtenir la borne, puis chercher la solution entière à part. Sur un petit problème à deux variables, il suffit d'énumérer les points entiers du domaine et de garder le meilleur ; sur un grand, les solveurs emploient une méthode dédiée, la séparation et évaluation. La borne sert à savoir quand s'arrêter.

Exemple résolu, les cartes C et D. La borne vaut 39. Les points entiers du domaine sont peu nombreux : $(0 ; 0)$ , $(0 ; 1)$ , $(0 ; 2)$ , $(0 ; 3)$ , $(1 ; 0)$ et $(1 ; 1)$ , qui rapportent 0, 11, 22, 33, 21 et 32. Le meilleur est $(0 ; 3)$ , à 33, à au plus 6 du meilleur possible, puisque rien ne dépasse 39.

Vérification rapideon peut se reprendre

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

Ce que l'atelier décide

La question d'ouverture a maintenant sa réponse, chiffrée.

L'atelier fabrique 2 cartes A et 6 cartes B par jour, pour une marge de 3 600 €. Le banc de test et le montage bloquent ; la soudure garde 2 cartes de reste, et l'agrandir ne rapporterait rien. Un budget va au banc de test si une carte de capacité coûte moins de 300 € par jour, au montage si une heure coûte moins de 100 €, et seulement jusqu'à 24 heures ; entre les deux, le coût de chaque unité tranche. La charge d'un poste dans le plan du jour ne suffit pas à décider : c'est la saturation à l'optimum, puis le prix, qui désignent le bon investissement.

Deux réserves, que la méthode apprend à dire. Ces prix sont ceux du modèle continu : en cartes entières, les heures de montage s'achètent par trois, et la septième carte de capacité de test ne rapporte que 200 €. Et chaque prix ne vaut que sur sa plage : après un achat, le calcul se refait.

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, une par ressource, chacune dans une seule unité, y compris celles de positivité qui semblent aller de soi. Un « au moins » s'écrit $\geq$ .
Tracer le domaine et calculer 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 : le plus grand pour une marge, le plus petit pour un coût.
Relever les contraintes saturées, celles dont le reste est nul, et calculer leur prix en relâchant d'une unité : ce sont les seules où un investissement peut rapporter, et ce prix dit jusqu'à quel coût il se justifie, sur sa plage de validité.
Ne jamais arrondir une solution continue pour obtenir une solution entière : la garder comme borne, et chercher la solution entière parmi les points entiers du domaine.
Conclure en français, en disant quoi fabriquer, combien, et quelle limite bloque.

Mettre en pratique

Une torréfaction prépare chaque jour deux mélanges de café, en lots : $x$ lots d'Espresso et $y$ lots de Filtre. Un lot d'Espresso rapporte une marge de 4, un lot de Filtre une marge de 5, en centaines d'euros. Trois ressources limitent la journée.

Ressource	Espresso	Filtre	Disponible
Torréfacteur	1 h	1 h	10 h
Arabica	1 sac	2 sacs	16 sacs
Robusta	3 sacs	1 sac	24 sacs

\text{maximiser } 4x + 5y \quad \text{sous } \begin{cases} x + y \leq 10 & \text{(torréfacteur, en heures)} \\ x + 2y \leq 16 & \text{(arabica, en sacs)} \\ 3x + y \leq 24 & \text{(robusta, en sacs)} \\ x \geq 0,\ y \geq 0 \end{cases}

Rappel de cours : du sommet à la plage de validité

Les questions ci-dessous enchaînent les gestes du chapitre.

Un sommet : écrire en égalités les deux contraintes qui s'y croisent, et résoudre le système.
Un reste : la limite moins la consommation ; négatif, le point est hors du domaine.
Un prix : relâcher d'une unité, résoudre le même système, vérifier les autres contraintes, faire la différence.
La plage de validité : remplacer la limite relâchée par une lettre, résoudre le système en fonction de cette lettre, et chercher jusqu'où le point obtenu respecte les autres contraintes.

Exemple résolu de ce dernier geste, sur l'atelier. Avec $H$ heures de montage, le banc de test restant saturé : $y = 6$ et $3x + 12 = H$ , donc $x = (H - 12)/3$ . La soudure exige $x \leq 4$ , soit $H - 12 \leq 12$ , donc $H \leq 24$  ; et $x \geq 0$ exige $H \geq 12$ . Le prix de 1 par heure vaut de 12 à 24 heures.

Une torréfaction, deux mélanges

1.
Au sommet où le torréfacteur et l'arabica sont saturés, combien de lots Filtre ?
2.
Et combien de lots Espresso ?
3.
Combien de sacs de robusta restent inemployés en ce point ?
4.
Quelle marge donne ce sommet, en centaines d'euros ?
5.
Et le sommet $(7 ; 3)$ , où le torréfacteur et le robusta sont saturés ?
6.
Une onzième heure de torréfaction, les mêmes contraintes restant saturées : combien de lots Filtre ?
7.
Combien rapporte cette heure, en centaines d'euros ?
8.
Et un dix-septième sac d'arabica, le torréfacteur restant à 10 heures ?
9.
Jusqu'à combien d'heures de torréfaction le prix de l'heure reste-t-il valable, avant que le robusta ne bloque à son tour ?

Le torréfacteur et l'arabica bloquent ; le robusta garde 6 sacs de reste et ne vaut rien de plus. Une heure de torréfaction vaut 300 €, un sac d'arabica 100 €, et le premier prix ne tient que jusqu'à 11,2 heures : au-delà, le robusta s'épuise à son tour, et le sommet optimal change de contraintes.

Rappel de cours : compter des choix

Le nombre de façons de choisir $k$ objets parmi $n$ , sans tenir compte de l'ordre, se note $\binom{n}{k}$  :

\binom{n}{k} = \frac{n!}{k!\,(n - k)!}

Exemple résolu : choisir 2 contraintes parmi 4 donne $\binom{4}{2} = \frac{4 \times 3}{2} = 6$ paires. Quand $k$ grandit avec $n$ , ce nombre explose à la manière des coûts en $2^n$ du chapitre sur la complexité.

Les autres questions de cette section reprennent les rappels précédents : la ligne de niveau et l'arête optimale, la contrainte « au moins », la borne continue, et le domaine vide.

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

Au plus $\binom{5}{2} = 10$ , le nombre de façons de choisir 2 contraintes parmi 5, puisqu'à deux variables un sommet est l'intersection de deux contraintes. En pratique bien moins, parce que des frontières sont parallèles et que des intersections tombent hors du domaine. L'atelier en est l'exemple, avec ses cinq contraintes, positivité comprise : dix paires, dont deux de droites parallèles, huit intersections, et cinq sommets seulement ; les trois autres intersections, $(4 ; 6)$ , $(6 ; 0)$ et $(0 ; 9)$ , tombent hors du domaine.

Avec plus de variables, la règle change : à $n$ variables, un sommet est l'intersection de $n$ contraintes, et non plus de deux. À 50 variables, 100 contraintes et les 50 contraintes de positivité, les candidats sont $\binom{150}{50}$ , environ $2 \times 10^{40}$  : aucune énumération n'en vient à bout. C'est le problème que l'algorithme du simplexe résout en ne visitant que les sommets qui améliorent. La méthode graphique, elle, s'arrête plus tôt, pour une raison plus simple : au-delà de deux variables, on ne dessine plus.

Que se passe-t-il si les lignes de niveau de l'objectif sont parallèles à 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. Sur l'atelier, si une carte B ne rapportait que 2, l'objectif $3x + 2y$ aurait les mêmes coefficients que le montage : toute l'arête qui va de $(4 ; 3)$ à $(2 ; 6)$ rapporterait 18, ses deux extrémités comprises.

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 : le gain encore possible est connu et borné, 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 fait partie du conflit, mais pas seule : elle contredit l'ensemble de celles qui restent, parfois une seule, parfois plusieurs ensemble. Une commande d'au moins 7 cartes B, $y \geq 7$ , contredit le banc de test, $y \leq 6$ , et la discussion porte sur ce couple. Une commande d'au moins 4 cartes A et d'au moins 4 cartes B, elle, s'écrit $x \geq 4$ et $y \geq 4$  : aucune paire de contraintes ne se contredit, mais ces deux exigences et le montage, pris ensemble, demanderaient au moins $3 \times 4 + 2 \times 4 = 20$ heures pour 18. Laquelle est négociable, laquelle a été mal chiffrée, ou le projet est-il réellement infaisable tel qu'il est posé ?

Poser le problème avant de le résoudre

Le domaine réalisable

L'optimum est sur un sommet

Contraintes saturées, restes et prix

Vérifier avec un solveur

Quand les variables doivent être entières

Ce que l'atelier décide

La méthode

Mettre en pratique

Dans la bibliothèque d'exercices