Chaque jour, nous prenons des décisions. Que manger pour le déjeuner ? Quel chemin prendre pour aller au travail ? La plupart de ces choix sont simples. Mais que se passe-t-il lorsque les décisions deviennent complexes, avec des dizaines d'options et de nombreuses limites à respecter ?

Imaginez que vous dirigez une usine. Vous voulez produire autant que possible pour maximiser vos profits, mais vous êtes limité par le nombre d'employés, les heures de travail et la quantité de matières premières. Comment trouver la combinaison parfaite ? C'est là qu'intervient l'optimisation.

L'optimisation consiste à trouver la meilleure solution possible à un problème, compte tenu d'un ensemble de règles ou de limites. La programmation linéaire est l'une des techniques d'optimisation les plus puissantes et les plus utilisées. Elle nous aide à traduire un problème concret en langage mathématique afin qu'un ordinateur puisse trouver la solution optimale.

Pour utiliser la programmation linéaire, nous devons d'abord construire un « modèle ». Ce modèle est une version simplifiée de notre problème, exprimée avec des mathématiques. Il repose sur trois piliers fondamentaux. Pour les comprendre, prenons l'exemple d'une artisane qui fabrique des tables et des chaises.

1. Les variables de décision

Ce sont les inconnues du problème, les choses que nous pouvons contrôler. Pour notre artisane, elle doit décider du nombre de tables et du nombre de chaises à fabriquer chaque semaine. Ce sont ses variables.

Nommons-les :

• $x_1$ = nombre de tables à fabriquer
• $x_2$ = nombre de chaises à fabriquer

Le but est de trouver les valeurs de $x_1$ et $x_2$ qui rendront son entreprise la plus performante possible.

2. La fonction objectif

La fonction objectif est la mesure de la performance que nous voulons maximiser ou minimiser. L'objectif de l'artisane est de maximiser son profit.

Supposons qu'elle réalise un profit de 50€ sur chaque table et de 30€ sur chaque chaise. Son profit total dépendra du nombre de tables et de chaises qu'elle vend. Nous pouvons l'écrire comme une équation simple :

3. Les contraintes

Les contraintes sont les règles ou les limites qui restreignent nos choix. L'artisane ne dispose pas de ressources illimitées. Elle doit faire face à des limites pratiques.

• Le temps de travail : Disons qu'elle dispose de 40 heures de travail par semaine. La fabrication d'une table prend 2 heures, et celle d'une chaise prend 1 heure.
• Le bois : Elle a un stock de 30 unités de bois pour la semaine. Chaque table et chaque chaise nécessitent 1 unité de bois.

Ces limites se traduisent par des inéquations mathématiques. Le temps total passé à fabriquer des tables et des chaises ne peut pas dépasser 40 heures. La quantité totale de bois utilisée ne peut pas dépasser 30 unités.

Il y a aussi une dernière contrainte, si évidente qu'on l'oublie parfois : l'artisane ne peut pas fabriquer un nombre négatif de tables ou de chaises. Nous ajoutons donc les contraintes de non-négativité : $x_1 \ge 0$ et $x_2 \ge 0$.

Le terme « linéaire » est crucial. Il signifie que les relations dans notre modèle sont directes et proportionnelles. Si une table rapporte 50€ de profit, deux tables rapportent 100€, et dix tables rapportent 500€. Il n'y a pas de remises sur volume ou de rendements décroissants. De même, si une table nécessite 2 heures de travail, dix tables nécessitent 20 heures.

Cette hypothèse de linéarité simplifie énormément le problème. Elle nous permet de représenter la fonction objectif et les contraintes comme des lignes droites sur un graphique. Le point optimal se trouvera toujours à l'un des coins de la zone délimitée par ces lignes. Grâce à cette propriété, des algorithmes efficaces peuvent trouver la meilleure solution très rapidement, même pour des problèmes avec des milliers de variables et de contraintes.

Maintenant que nous avons défini les composants de base d'un problème d'optimisation, nous sommes prêts à explorer comment ces modèles sont utilisés pour résoudre des défis concrets.