Formulez un problème d'optimisation

Chaque lundi, le gérant d’une petite brasserie rennaise se pose la même question : combien d’hectolitres de blonde et d’ambrée lancer cette semaine ? L’ambrée rapporte moins mais la blonde consomme un houblon rare, et les cuves de fermentation ne sont pas extensibles. Il pourrait tâtonner. Il peut aussi écrire le problème proprement, et laisser les mathématiques trouver la meilleure réponse.

Dans ce chapitre, vous allez apprendre à traduire une situation concrète en problème d’optimisation, puis à résoudre à la main le cas le plus simple : un programme linéaire à deux variables. Cette brasserie nous accompagnera pendant toute la première partie du cours.

Les trois ingrédients d’un problème d’optimisation

Tout problème d’optimisation se compose de trois éléments.

• Les variables de décision $x = (x_1, \dots, x_n)$ : ce que vous pouvez choisir. Pour la brasserie, $x_1$ et $x_2$ sont les volumes de blonde et d’ambrée, en hectolitres.
• La fonction objectif (ou critère, ou coût) $f$ : ce que vous voulez rendre le plus petit ou le plus grand possible. Ici, le bénéfice de la semaine.
• L’ensemble réalisable (on dit aussi admissible) $S$ : les choix autorisés par les contraintes. Un volume négatif n’a pas de sens, et on ne peut pas remplir plus de cuves qu’on n’en possède.

On écrit alors le problème sous la forme

$$\min_{x \in S} f(x)$$

ce qui se lit « trouver un point $x$ de $S$ qui rend $f(x)$ le plus petit possible ». Un point $x$ qui appartient à $S$ est dit réalisable ; un point réalisable qui atteint le minimum est une solution optimale, et la valeur $f(x^*)$ correspondante est la valeur optimale.

Et si l’on veut maximiser, comme notre brasseur avec son bénéfice ? Il suffit de remarquer que maximiser $f$ revient à minimiser $-f$ :

$$\max_{x \in S} f(x) = -\min_{x \in S} \big(-f(x)\big)$$

Les deux problèmes ont les mêmes solutions, seule la valeur change de signe. C’est pourquoi la théorie est presque toujours écrite pour des minimisations : vous n’aurez jamais qu’un seul cas à retenir.

Minimum global et minimum local

Deux notions de minimum coexistent, et il faut bien les distinguer.

• $x^*$ est un minimum global si $f(x^*) \leq f(x)$ pour tout $x$ de $S$.
• $x^*$ est un minimum local si $f(x^*) \leq f(x)$ pour tout $x$ de $S$ assez proche de $x^*$ (dans une petite boule autour de $x^*$).

Pensez à un paysage de montagne : le fond de chaque vallée est un minimum local, mais seul le fond de la vallée la plus basse est le minimum global. Un randonneur qui descend toujours la pente finit dans une vallée, pas forcément la plus basse. Vous retrouverez ce randonneur dans la deuxième partie, car c’est exactement ce que fait la descente de gradient.

Le fond de chaque vallée est un minimum local ; seul le plus bas est le minimum global. En descendant toujours, on s'arrête dans la première vallée rencontrée.

À retenir

Un problème d’optimisation, c’est des variables, un objectif et des contraintes. On se ramène toujours à une minimisation ($\max f = -\min(-f)$), et l’on distingue le minimum global (le meilleur partout) du minimum local (le meilleur dans un voisinage).

Un panorama des problèmes

Les méthodes de résolution dépendent beaucoup de la forme de $f$ et de $S$. Voici les grandes familles que vous rencontrerez dans ce cours :

Famille	Objectif	Contraintes	Méthode typique	Chapitres
Programmation linéaire	affine	affines (égalités, inégalités)	simplexe	1 à 4
Sans contrainte	quelconque, dérivable	aucune	gradient, Newton	5 à 7
Sous contraintes d’égalité	quelconque	$h(x) = 0$	multiplicateurs de Lagrange	8
Sous contraintes d’inégalité	quelconque	$g(x) \leq 0$	conditions KKT	9

Une fonction affine est de la forme $c_1 x_1 + \dots + c_n x_n + d$ : pas de carré, pas de produit de variables. Quand l’objectif et toutes les contraintes sont affines, on parle de programme linéaire (linear program, souvent abrégé PL, ou LP en anglais). C’est le cas de la brasserie.

Attention

Ce cours traite de variables continues : on peut brasser 2,7 hectolitres. Si les variables doivent être entières (un nombre de camions, une décision oui/non), on parle de programmation en nombres entiers, un problème beaucoup plus difficile qu’on ne résout pas en arrondissant simplement la solution continue.

Modéliser la brasserie

Voici les données du brasseur, pour une semaine :

Ressource	Blonde (par hl)	Ambrée (par hl)	Disponible
Cuves de fermentation (hl)	1	1	4
Malt (sacs)	1	3	9
Houblon aromatique (lots)	1	0	3
Bénéfice (centaines d’euros)	3	2

L’ambrée est plus maltée (3 sacs par hectolitre), la blonde est la seule à utiliser le houblon aromatique. La modélisation se fait en trois questions.

1. Que choisit-on ? $x_1$ hectolitres de blonde et $x_2$ hectolitres d’ambrée.
2. Que veut-on ? Maximiser le bénéfice $z = 3x_1 + 2x_2$ (en centaines d’euros).
3. Qu’est-ce qui limite ? Chaque ressource donne une contrainte : la consommation ne dépasse pas le disponible.

On obtient le programme linéaire :

$$\begin{aligned} \max \quad & z = 3x_1 + 2x_2 \\ \text{s.c.} \quad & x_1 + x_2 \leq 4 && \text{(cuves)} \\ & x_1 + 3x_2 \leq 9 && \text{(malt)} \\ & x_1 \leq 3 && \text{(houblon)} \\ & x_1 \geq 0, \; x_2 \geq 0 \end{aligned}$$

« s.c. » signifie « sous les contraintes ». Les deux dernières, les contraintes de positivité, sont faciles à oublier et pourtant indispensables : sans elles, le modèle pourrait proposer de brasser $-5$ hectolitres d’ambrée pour libérer du malt.

Piège

Vérifiez toujours les unités de chaque contrainte. Si le malt était compté en kilogrammes pour la blonde et en sacs pour l’ambrée, la contrainte additionnerait des choses qui ne s’additionnent pas, et le modèle donnerait une réponse fausse sans le moindre message d’erreur.

La méthode graphique

Avec deux variables, on peut tout dessiner dans le plan $(x_1, x_2)$. Chaque contrainte $a_1 x_1 + a_2 x_2 \leq b$ découpe le plan en deux par la droite $a_1 x_1 + a_2 x_2 = b$ et ne garde qu’un côté (pour savoir lequel, testez l’origine : $(0, 0)$ vérifie-t-il l’inégalité ?). L’ensemble réalisable est l’intersection de tous ces demi-plans : un polygone convexe, c’est-à-dire sans creux.

Reste à placer l’objectif. Pour une valeur donnée $z$, les points qui rapportent exactement $z$ forment la droite $3x_1 + 2x_2 = z$ : une ligne de niveau de l’objectif. Toutes ces droites sont parallèles, et elles s’éloignent de l’origine quand $z$ augmente. La méthode consiste donc à faire glisser la droite dans le sens où $z$ grandit, tant qu’elle touche encore le polygone. Le dernier point touché est l’optimum.

Sur la figure, la droite $z = 6$ traverse le polygone : on peut mieux faire. En la poussant vers le haut à droite, elle quitte le polygone au sommet $(3, 1)$, pour $z = 11$.

Exemple

On peut aussi vérifier en calculant le bénéfice en chaque sommet du polygone. Les sommets sont les intersections de deux droites de contraintes qui respectent toutes les autres :

Sommet	Contraintes saturées	$z = 3x_1 + 2x_2$
$(0, 0)$	positivité	0
$(3, 0)$	houblon, $x_2 = 0$	9
$(3, 1)$	houblon, cuves	11
$(1{,}5 ; 2{,}5)$	cuves, malt	9,5
$(0, 3)$	malt, $x_1 = 0$	6

Le brasseur doit lancer 3 hl de blonde et 1 hl d’ambrée, pour un bénéfice de 1 100 €. Les cuves et le houblon sont utilisés à fond ; il reste $9 - (3 + 3) = 3$ sacs de malt.

Pourquoi l’optimum tombe-t-il sur un sommet ? Parce que l’objectif est affine : sur un segment, il varie de façon linéaire, donc il est toujours au moins aussi bon à l’une des deux extrémités qu’au milieu. En répétant l’argument, on arrive au résultat fondamental de la programmation linéaire.

Sur chaque côté du polygone, le bénéfice varie en ligne droite : le maximum ne peut donc être atteint qu'à un sommet, ici (3, 1) avec z = 11.

À retenir

L’ensemble réalisable d’un programme linéaire est un polyèdre convexe (un polygone en dimension 2). Si le problème admet un optimum fini, il est atteint en au moins un sommet. Il suffit donc de chercher parmi les sommets, qui sont en nombre fini : c’est l’idée du simplexe, au chapitre suivant.

Les cas particuliers

Tout ne se passe pas toujours aussi bien. Trois situations méritent d’être reconnues au premier coup d’œil.

• Une infinité de solutions : si la droite de l’objectif est parallèle à un côté du polygone, elle quitte le polygone par tout un côté. Tous les points de ce côté sont optimaux (et en particulier ses deux sommets, ce qui est cohérent avec le résultat précédent).
• Un problème non borné : si le polygone est ouvert dans la direction où l’objectif augmente, on peut faire grandir $z$ indéfiniment. Il n’y a pas d’optimum. En pratique, c’est presque toujours le signe d’une contrainte oubliée.
• Un problème irréalisable : si les contraintes se contredisent (par exemple $x_1 + x_2 \leq 2$ et $x_1 + x_2 \geq 3$), l’ensemble réalisable est vide.

Les trois cas particuliers : une ligne de niveau parallèle à un côté (infinité de solutions), un ensemble ouvert dans la direction où z grandit (non borné), des contraintes contradictoires (irréalisable).

En Python, on délègue la résolution à scipy.optimize.linprog, qui minimise par convention. Pour maximiser le bénéfice, on minimise donc son opposé :

from scipy.optimize import linprog

c = [-3, -2]                  # on minimise -z = -3 x1 - 2 x2
A_ub = [[1, 1],               # cuves
        [1, 3],               # malt
        [1, 0]]               # houblon
b_ub = [4, 9, 3]

res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=[(0, None), (0, None)])
print(res.status, res.x, -res.fun)   # 0 = succès ; x = [3, 1] ; bénéfice 11

L’attribut status vaut 2 si le problème est irréalisable et 3 s’il est non borné : pensez à le tester avant de lire la solution.

En entretien

« Un programme linéaire a un objectif et des contraintes affines ; son ensemble réalisable est un polyèdre convexe, et s’il existe un optimum fini, il est atteint en un sommet. C’est ce qui permet au simplexe de ne visiter que les sommets. »

En résumé

• Un problème d’optimisation se compose de variables de décision, d’une fonction objectif et d’un ensemble réalisable défini par les contraintes.
• On se ramène toujours à une minimisation grâce à $\max f = -\min(-f)$.
• Un minimum global est le meilleur de tout l’ensemble réalisable ; un minimum local n’est le meilleur que dans un voisinage.
• Un programme linéaire a un objectif et des contraintes affines ; n’oubliez pas les contraintes de positivité.
• En deux variables, la méthode graphique trace le polygone réalisable et fait glisser la ligne de niveau de l’objectif.
• L’optimum d’un programme linéaire, s’il existe, est atteint en un sommet ; le problème peut aussi avoir une infinité de solutions, être non borné ou irréalisable.

Exercices

Exercice · Résoudre graphiquement

facile

Résolvez graphiquement le programme linéaire suivant, puis vérifiez en évaluant l’objectif en chaque sommet :

$$\max \; z = x_1 + x_2 \quad \text{s.c.} \quad 2x_1 + x_2 \leq 8, \quad x_1 + 2x_2 \leq 7, \quad x_1, x_2 \geq 0$$

Voir la solution

La droite $2x_1 + x_2 = 8$ coupe les axes en $(4, 0)$ et $(0, 8)$ ; la droite $x_1 + 2x_2 = 7$ en $(7, 0)$ et $(0 ; 3{,}5)$. Leur intersection s’obtient en résolvant le système : en soustrayant deux fois la seconde équation à la première, on trouve $-3x_2 = -6$, donc $x_2 = 2$ puis $x_1 = 3$.

Les sommets du polygone sont $(0, 0)$, $(4, 0)$, $(3, 2)$ et $(0 ; 3{,}5)$, où $z$ vaut respectivement 0, 4, 5 et 3,5. L’optimum est $(3, 2)$, avec $z = 5$. Graphiquement, la droite $x_1 + x_2 = z$ (de pente $-1$) quitte le polygone en ce sommet, car sa pente est comprise entre celles des deux contraintes ($-2$ et $-1/2$).

En code

Python

import numpy as np
from scipy.optimize import linprog

# Vérification aux sommets trouvés graphiquement
sommets = np.array([[0, 0], [4, 0], [3, 2], [0, 3.5]])
print(sommets @ [1, 1])                    # [0.  4.  5.  3.5]

# Résolution directe (linprog minimise : on passe -z)
res = linprog([-1, -1], A_ub=[[2, 1], [1, 2]], b_ub=[8, 7],
              bounds=[(0, None), (0, None)])
print(res.x, -res.fun)                     # [3. 2.] 5.0

R

# Contraintes A x <= b, positivité comprise (-x1 <= 0, -x2 <= 0)
A <- rbind(c(2, 1), c(1, 2), c(-1, 0), c(0, -1))
b <- c(8, 7, 0, 0)
sommets <- NULL
for (i in combn(nrow(A), 2, simplify = FALSE)) {
  if (abs(det(A[i, ])) < 1e-9) next              # droites parallèles
  x <- solve(A[i, ], b[i])                       # intersection de deux droites
  if (all(A %*% x <= b + 1e-9)) sommets <- rbind(sommets, x)   # réalisable ?
}
z <- sommets %*% c(1, 1)
cbind(sommets, z)            # (3, 2) : 5 ; (4, 0) : 4 ; (0, 3.5) : 3.5 ; (0, 0) : 0
sommets[which.max(z), ]      # 3 2

Exercice · Modéliser une crêperie

moyen

Une crêperie prépare chaque matin des galettes de sarrasin et des crêpes de froment, par douzaines. Une douzaine de galettes rapporte 4 €, une douzaine de crêpes 3 €. La plaque (la billig) permet de cuire au plus 10 douzaines au total. La farine de sarrasin disponible suffit pour 6 douzaines de galettes, et le lait pour 8 douzaines de crêpes. Écrivez le programme linéaire, puis résolvez-le.

Voir la solution

Notons $x_1$ le nombre de douzaines de galettes et $x_2$ celui de crêpes. Le programme est :

$$\max \; z = 4x_1 + 3x_2 \quad \text{s.c.} \quad x_1 + x_2 \leq 10, \quad x_1 \leq 6, \quad x_2 \leq 8, \quad x_1, x_2 \geq 0$$

Les sommets du polygone sont $(0, 0)$, $(6, 0)$, $(6, 4)$, $(2, 8)$ et $(0, 8)$, où $z$ vaut 0, 24, 36, 32 et 24. La crêperie doit faire 6 douzaines de galettes et 4 douzaines de crêpes, pour 36 € : la plaque et le sarrasin sont saturés, il reste du lait pour 4 douzaines de crêpes.

En code

Python

from scipy.optimize import linprog

# x1 : douzaines de galettes, x2 : douzaines de crêpes
c = [-4, -3]                    # on minimise -z = -4 x1 - 3 x2
A_ub = [[1, 1],                 # billig : 10 douzaines au total
        [1, 0],                 # sarrasin : 6 douzaines de galettes
        [0, 1]]                 # lait : 8 douzaines de crêpes
b_ub = [10, 6, 8]
res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=[(0, None), (0, None)])
print(res.x, -res.fun)          # [6. 4.] 36.0
print(res.slack)                # [0. 0. 4.] : billig et sarrasin saturés, lait restant 4

R

# Contraintes A x <= b : billig, sarrasin, lait, puis positivité
A <- rbind(c(1, 1), c(1, 0), c(0, 1), c(-1, 0), c(0, -1))
b <- c(10, 6, 8, 0, 0)
sommets <- NULL
for (i in combn(nrow(A), 2, simplify = FALSE)) {
  if (abs(det(A[i, ])) < 1e-9) next
  x <- solve(A[i, ], b[i])
  if (all(A %*% x <= b + 1e-9)) sommets <- rbind(sommets, x)
}
sommets <- unique(round(sommets, 9))
z <- sommets %*% c(4, 3)
cbind(sommets, z)            # (6, 4) : 36 ; (2, 8) : 32 ; (6, 0) : 24 ; (0, 8) : 24 ; (0, 0) : 0
sommets[which.max(z), ]      # 6 4

Exercice · Reconnaître les cas particuliers

difficile

On reprend les contraintes de la brasserie.

1. Le prix de l’ambrée augmente : le bénéfice devient $z = 3x_1 + 3x_2$. Quelles sont les solutions optimales ?
2. On revient à $z = 3x_1 + 2x_2$, mais le brasseur loue autant de cuves et achète autant de houblon qu’il veut : seule la contrainte du malt subsiste. Que se passe-t-il ?

Voir la solution

1. La nouvelle ligne de niveau $3x_1 + 3x_2 = z$ est parallèle à la contrainte des cuves $x_1 + x_2 = 4$. En chaque sommet : $(3, 0)$ donne 9, $(3, 1)$ donne 12, $(1{,}5 ; 2{,}5)$ donne 12, $(0, 3)$ donne 9. Les deux sommets $(3, 1)$ et $(1{,}5 ; 2{,}5)$ sont optimaux, ainsi que tout le segment qui les relie, où les cuves sont pleines : il y a une infinité de solutions, toutes de valeur 12.
2. Il ne reste que $x_1 + 3x_2 \leq 9$ et la positivité. Contrairement aux apparences, le problème reste borné : les coefficients de cette contrainte sont tous positifs, donc elle impose à elle seule $x_1 \leq 9$ et $x_2 \leq 3$. L’ensemble réalisable est le triangle de sommets $(0, 0)$, $(9, 0)$ et $(0, 3)$, où $z$ vaut 0, 27 et 6 : le brasseur ne produit plus que de la blonde, 9 hl, pour 2 700 €. Pour obtenir un problème non borné, il faudrait lever aussi la contrainte du malt : le point $(t, 0)$ serait alors réalisable pour tout $t \geq 0$ et rapporterait $3t$, qui tend vers l’infini. Ce n’est évidemment pas la réalité, c’est le modèle qui aurait perdu ses contraintes (aucune ressource n’est infinie).

En code

Python

import numpy as np
from scipy.optimize import linprog

A_ub, b_ub = [[1, 1], [1, 3], [1, 0]], [4, 9, 3]
# 1. z = 3 x1 + 3 x2 : tout le segment entre (3, 1) et (1,5 ; 2,5) vaut 12
for p in [(3, 0), (3, 1), (1.5, 2.5), (0, 3), (2, 2)]:
    print(p, 3 * p[0] + 3 * p[1])          # 9, 12, 12, 9, 12 : (2, 2) est aussi optimal
res = linprog([-3, -3], A_ub=A_ub, b_ub=b_ub, bounds=[(0, None)] * 2)
print(-res.fun)                            # 12.0 (le solveur renvoie un seul des optimums)

# 2. Seule la contrainte du malt : le problème reste borné !
res = linprog([-3, -2], A_ub=[[1, 3]], b_ub=[9], bounds=[(0, None)] * 2)
print(res.status, res.x, -res.fun)         # 0 [9. 0.] 27.0
# Sans aucune contrainte de ressource, en revanche, il devient non borné
res = linprog([-3, -2], bounds=[(0, None)] * 2)
print(res.status)                          # 3 = non borné

R

sommets_pl <- function(A, b) {             # sommets du polygone A x <= b
  S <- NULL
  for (i in combn(nrow(A), 2, simplify = FALSE)) {
    if (abs(det(A[i, ])) < 1e-9) next
    x <- solve(A[i, ], b[i])
    if (all(A %*% x <= b + 1e-9)) S <- rbind(S, x)
  }
  unique(round(S, 9))
}
positivite <- rbind(c(-1, 0), c(0, -1))
# 1. Brasserie avec z = 3 x1 + 3 x2 : deux sommets à égalité
S <- sommets_pl(rbind(c(1, 1), c(1, 3), c(1, 0), positivite), c(4, 9, 3, 0, 0))
cbind(S, S %*% c(3, 3))        # (1.5, 2.5) et (3, 1) valent 12 ; (0, 3) et (3, 0) valent 9
# 2. Seul le malt subsiste : un triangle, donc un problème borné
S <- sommets_pl(rbind(c(1, 3), positivite), c(9, 0, 0))
cbind(S, S %*% c(3, 2))        # (0, 3) : 6 ; (9, 0) : 27 ; (0, 0) : 0