La programmation linéaire : optimiser sous contraintes

Algorithmes

Optimisation

Malgré son nom, la programmation linéaire n'a rien à voir avec l'écriture d'un programme informatique. Cette méthode mathématique, née dans les années 1940, permet d'optimiser des décisions sous contraintes. À travers l'exemple d'un maraîcher hésitant entre deux modes de culture, découvrons comment un dessin peut révéler la solution optimale, et passer à l'algorithme qui le résout.

Répartir des terres agricoles entre différentes productions, des heures de travail entre différents projets d’une entreprise, ou la circulation de véhicules dans un réseau routier, en maximisant le profit ou minimisant la pénibilité : dans ces trois problèmes de décision, l’objectif à optimiser comme les contraintes à respecter ont une structure qui permet de les modéliser comme des « programmes linéaires ».

Rappelons avant de commencer qu’une expression linéaire est de la forme $a_1x_1+a_2x_2 \ldots$ où les $a_i$ sont des constantes, des nombres, et les $x_i$ sont des variables. Par exemple, l’expression $3 x_1 + 2x_2$ est linéaire alors que les expressions $3x_1^2$ ou $5x_1x_2$ ne le sont pas. En dimension 2, c’est-à-dire avec deux variables, une équation linéaire correspond à une droite dans le plan. En dimension 3, on parle d’un plan et d’un hyperplan en dimension plus grande. Une inéquation (de la forme $a_1x_1+a_2x_2…\leq b$ par exemple) correspond à un demi-plan en dimension 2 et à un demi-espace en dimension 3.

L’expression « programmation linéaire » peut sembler déroutante car le mot « programmation » désigne depuis longtemps le fait d’écrire un programme en langage informatique. Cependant lorsque cette expression a été créée par George Dantzig (voir la référence bibliographique 1) dans les années 1940, un programme désignait tout ce qu’on pouvait imaginer demander à un ordinateur. Ici il s’agit de résoudre un problème mathématique : optimiser une fonction linéaire à plusieurs variables qui doivent respecter des inégalités linéaires.

Pour comprendre d’où provient ce genre de questions, nous allons prendre un exemple concret et regarder pourquoi cela demande d’utiliser un ordinateur.

Le dilemme du maraîcher

Un maraîcher produit des tomates. Il envisage deux sortes de production possibles. Une production, dite productiviste, pour laquelle il utilise des pesticides pour écarter les insectes, et une production, dite raisonnée, qui demande davantage d’effort de travail mais aucun pesticide. Le mode raisonné a un moins bon rendement que le productiviste, mais les tomates peuvent être vendues plus chères car les acheteurs acceptent de payer un prix plus élevé pour une production saine et respectueuse de la nature. Le maraîcher doit décider comment répartir la surface disponible entre les deux modes de production. Mais pour cela, il doit respecter des contraintes de surface, de temps et de ressources. En effet, il possède un terrain de $2000$ m$^2$ pour faire pousser ses tomates, il peut consacrer $27$ heures de travail par semaine à cette production et il ne veut pas utiliser plus de $16$ $\ell$ de pesticide sur ce terrain.

Voici le tableau comparatif des deux productions sur le prix de vente au kilogramme, le rendement en kilogramme par m$^2$, le temps hebdomadaire à passer sur le terrain par m$^2$ et la quantité de pesticide à utiliser par m$^2$ également.

	Prix	Rendement	Temps	Pesticide
Productiviste	1,9 € / kg	15 kg / m$^2$	0,6 min / m$^2$	0,01 $\ell$ / m$^2$
Raisonné	3,9 € / kg	8 kg / m$^2$	0,96 min / m$^2$	0 $\ell$ / m$^2$

On peut d’abord se demander si se concentrer sur une seule production est possible. Par exemple, la productiviste seule ne peut pas dépasser $1 600$ m$^2$ à cause de la ressource limitée de pesticide. Pour produire davantage, il est alors possible de compléter avec $400$ m$^2$ de production raisonnée.

Comme il n’est pas simple de réfléchir à tous les cas de figure, on peut dessiner l’ensemble des solutions possibles. Pour cela, on utilise deux variables : $x_p$ est la surface affectée au mode productiviste (en m$^2$) et $x_r$ est la surface dédiée au mode raisonné (en m$^2$ aussi). Le nombre total de m$^2$ utilisés est alors $x_p+x_r$ qui est borné par la surface du terrain disponible. On obtient alors une première contrainte qui doit être vérifiée par toutes les solutions : $x_p+x_r \leq 2000$. Le système complet de contraintes s’écrit :

\[ \begin{array}{rclrcll}
& x_p & + & x_r & \le & 2000 & \quad \color{red}{(1)} \text{ (surface, m}^2\text{)} \\
& 0,\!01 \, x_p & + & 0,\!016 \, x_r & \le & 27 & \quad \color{purple}{(2)} \text{ (temps, h)} \\
& 0,\!01 \, x_p & & & \le & 16 & \quad \color{orange}{(3)} \text{ (pesticide, $\ell$)} \\
& x_p & & & \ge & 0 & \quad (Ox_r) \\
& & & x_r & \ge & 0 & \quad (Ox_p)
\end{array} \]

La deuxième contrainte indique que le temps passé sur chacune des deux productions est limité à $27$ h (il faut faire les conversions de temps de minutes en heures !) ; la troisième contrainte correspond à la limitation en pesticide ; et les deux dernières inégalités précisent que les variables qui représentent des surfaces sont nécessairement positives.

Le gain d’une solution, représenté par le prix de vente $z$ en euros (€), est calculé par la formule $z=1,\!9\times 15 \times x_p + 3,\!9\times 8\times x_r$ soit $28,\!5x_p+31,\!2x_r$. Il s’agit alors de trouver des valeurs de $x_p$ et $x_r$ qui satisfont toutes les contraintes (inégalités) et qui maximisent cette expression. La formulation complète de ce problème comme un programme linéaire s’écrit alors :

\[ (P)\left\{ \begin{array}{ccccccc} \max z = & {28,\!5x_{p}} & + & {31,\!2 x_{r}} & & & \\ & {x_{p}} & + & {x_{r}} & \le & 2000 & {\color{red}{(1)}}\\ & {0,\!01 x_{p}} & + & {0,\!016 x_{r}} & \le & 27 & {\color{purple}{(2)}} \\ & {0,\!01 x_{p}} & & & \le & 16 & {\color{orange}{(3)}}\\ & {x_{p}} & & & \ge & 0 & {(Ox_{r})}\\ & & & {x_{r}} & \ge & 0 & {(Ox_{p})}\\ \end{array} \right. \]

Dessiner le problème pour le résoudre

Avec deux variables, on peut « dessiner » ce problème. On représente alors deux axes d’un repère orthonormé comme sur la figure ci-dessous. Par exemple, la droite en orange correspond à la limitation en pesticide, c’est-à-dire $0,\!01 x_p = 16$ et les solutions sont donc à gauche de cette droite pour respecter l’inégalité linéaire (pesticide) qui lui correspond dans l’écriture algébrique ci-dessus.

La surface coloriée en rose représente ainsi l’ensemble des points de coordonnées $(x_p, x_r)$ qui respectent toutes les inégalités du problème : ce sont toutes les solutions possibles ! Cette surface est un polyèdre, c’est-à-dire une zone de l’espace définie par l’intersection de demi-plans. Dans cet exemple en dimension 2, comme le polyèdre est borné, son périmètre est un polygone convexe. Et les points saillants du périmètre du polyèdre (représentés par des croix noires) sont appelés des points extrêmes ou sommets. Ainsi, on peut voir que la solution évoquée plus haut $(1600 ; 400)$ est un sommet de cette surface.

Pour trouver une « meilleure » solution, il suffit de considérer les solutions correspondant à des points extrêmes et de calculer le gain correspondant. En effet, on peut prouver qu’il y a parmi elles (au moins) une solution optimale, c’est-à-dire qui rapporte le plus. Ici, il y a 5 points extrêmes. Parmi eux, bien sûr le point $(0 ; 0)$ qui ne rapporte rien n’est pas optimal et on peut facilement se convaincre que le point $(1600 ; 0)$ rapporte moins que le point $(1600 ; 400)$.

On peut imaginer calculer le gain de chacun des trois points restants pour trouver le meilleur : c’est tout à fait possible pour cet exemple. Mais pour des problèmes plus gros, c’est impensable de les énumérer : on se heurte à l’explosion combinatoire et il peut y avoir un nombre exponentiel (dans le nombre de contraintes) de points à explorer.

Heureusement, on est guidé par notre objectif qui correspond à maximiser une fonction linéaire, dite fonction objectif $z = 28,\!5x_p + 31,\!2x_r$. Ainsi on cherche la plus grande valeur possible de $z$. Pour cela, on a représenté ci-dessous la fonction pour différentes valeurs de $z$. Tous les points d’une ligne bleue correspondent à la même valeur de $z$. On peut ainsi imaginer voir glisser une même ligne dans la direction d’augmentation (représentée par une flèche verte orthogonale) jusqu’à la limite du polyèdre.

On voit que la valeur maximale pour laquelle il existe une solution est $z = 60 150$ € pour le point extrême $( 2500/ 3 ; 3500 / 3 )$. En effet, pour une valeur de $z$ plus grande, il n’y a plus de solution satisfaisant toutes les contraintes. Cette solution correspond à $833,\!33$ m$^2$ pour le mode productiviste et $1166,\!66$ m$^2$ pour le mode raisonné. Il est à noter que ce chiffre d’affaires ne tient pas compte des remboursements de crédits pour l’investissement, des frais d’exploitation et de commercialisation, etc.

Du dessin à l’algorithme

Un programme linéaire est exactement l’écriture de la formule algébrique $(P)$ de l’exemple précédent : maximiser (ou minimiser) une fonction linéaire en respectant des inégalités linéaires. Mais la représentation graphique proposée dans l’exemple précédent ne peut pas être faite dès qu’on a plus de 3 variables ! Il faut donc recourir à des algorithmes efficaces bien différents de ce qui a été utilisé dans la section précédente.

Puisqu’on a identifié qu’il existait une solution optimale qui est un sommet du polyèdre défini par les contraintes, on pourrait énumérer tous les sommets de ce polyèdre. Ceci peut être réalisé par un calcul algébrique en transformant certaines inégalités en égalités (qui correspondent alors à des équations de droites se croisant en un sommet). On obtient les coordonnées de ce sommet en résolvant le système composé de ces égalités et d’autant de variables. Pour chaque sommet ainsi obtenu, on peut calculer la valeur de la fonction objectif et garder la meilleure (plus grande ou plus petite, selon ce qu’on souhaite). Cette énumération permet bien de répondre à la question qui est de trouver une meilleure solution. Malheureusement, le nombre de sommets possibles du polyèdre est exponentiel, ce qui signifie que l’énumération de ces sommets demande un temps qui explose et peut rapidement dépasser la durée de vie du soleil.

Plusieurs algorithmes permettent de résoudre efficacement la recherche de l’optimum d’un programme linéaire. Ces algorithmes sont efficaces soit en théorie comme l’algorithme des ellipsoïdes (qui est de complexité polynomiale), soit efficace en pratique comme l’algorithme du simplexe, soit à la fois en théorie et en pratique comme les méthodes de points intérieurs.

L’algorithme du simplexe, largement utilisé encore aujourd’hui, a été inventé par Georges Dantzig en 1947. Dans le petit exemple précédent, il commence par le sommet $(0,0)$ du polyèdre, puis passe itérativement à un sommet voisin meilleur que le sommet courant jusqu’à ne plus pouvoir avancer : ce qui pourrait donner ici $(1600,0)$, puis $(1600,400)$ et enfin $( 2500/3 , 3500/3 )$. Il s’arrête alors et renvoie, avec les valeurs du sommet optimal, la preuve de son optimalité.

Une méthode éprouvée

La programmation linéaire a ouvert des questions d’algorithmique parmi les plus célèbres et l’algorithme du simplexe est dans le Top 10 des algorithmes les plus importants du 20ème siècle (voir la référence bibliographique 2). Résoudre des programmes linéaires est devenu une fonctionnalité de base de nombreux logiciels grands publics (MSExcel, LibreOffice, Wolfram Mathematica, Sage Math, GLPK, etc.).

Cet algorithme du simplexe, comme celui des points intérieurs, a bénéficié de nombreuses améliorations au fil des années, résultant en des outils efficaces embarqués dans les logiciels d’optimisation pour l’industrie et les services publics. Ils permettent de résoudre des problèmes avec plusieurs centaines de milliers de variables en quelques secondes, comme il peut y en avoir pour la conception et le dimensionnement de systèmes énergétiques ou les organisations d’un service complexe comme un hôpital.

Dantzig, George B., Reminiscences About the Origin of Linear Programming, 1983.
Dongarra and F. Sullivan, Guest Editors Introduction to the top 10 algorithms, in Computing in Science & Engineering, vol.2, issue.1, pp.22-23, 2000.