Programmation linéaire — méthode du simplexe et solution graphique

La programmation linéaire est une méthode qui permet de trouver la meilleure valeur d’un objectif linéaire, comme un profit maximal ou un coût minimal, sous des contraintes linéaires. Dans un problème à deux variables, la solution graphique consiste à déterminer la région réalisable puis à examiner ses sommets. Dans les problèmes plus grands, la méthode du simplexe applique algébriquement cette même idée des sommets.

Utilisez la programmation linéaire uniquement lorsque l’objectif et les contraintes sont linéaires. Si la relation se courbe, n’est pas affine, ou dépend de produits comme $xy$, le modèle n’est pas un programme linéaire.

Définition de la programmation linéaire

$$\text{maximize or minimize } z = c_1x_1 + c_2x_2 + \cdots + c_nx_n$$

sous des contraintes telles que

$$a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \le b_1$$

ainsi que d’autres inégalités linéaires similaires, avec des conditions comme $x_i \ge 0$ lorsque les valeurs négatives n’ont pas de sens.

L’ensemble de tous les points qui satisfont chaque contrainte s’appelle la région réalisable. La programmation linéaire pose la question suivante : parmi ces points réalisables, lequel donne la meilleure valeur de l’objectif ?

Comment fonctionne la méthode graphique

S’il n’y a que deux variables de décision, vous pouvez tracer chaque contrainte dans le plan $xy$. L’intersection de toutes les zones autorisées forme la région réalisable.

Chaque point de cette région est une solution valide. La fonction objectif attribue une valeur à chacun d’eux.

Pour les programmes linéaires, un fait essentiel est le suivant : si une solution optimale existe, alors au moins une solution optimale se trouve en un sommet de la région réalisable. C’est pourquoi la méthode graphique se concentre sur les sommets au lieu de tester tous les points de la zone hachurée.

Exemple résolu : résoudre graphiquement un problème de programmation linéaire

Supposons qu’un atelier fabrique deux produits, $A$ et $B$.

• Profit par unité de $A$ : $3$
• Profit par unité de $B$ : $5$
• Limite de temps machine : chaque unité de $A$ utilise $1$ heure, chaque unité de $B$ utilise $2$ heures, et on dispose d’au plus $8$ heures
• Limite d’assemblage : chaque unité de $A$ utilise $1$ heure, chaque unité de $B$ utilise $1$ heure, et on dispose d’au plus $5$ heures

Soit $x$ le nombre d’unités de $A$ et $y$ le nombre d’unités de $B$.

Maximiser

$$P = 3x + 5y$$

sous les contraintes

$$x + 2y \le 8$$ $$x + y \le 5$$ $$x \ge 0,\quad y \ge 0$$

Trouver les sommets

À partir des axes et des droites de contrainte, les sommets réalisables sont

• $(0,0)$
• $(5,0)$
• $(0,4)$
• $(2,3)$

Le point $(2,3)$ s’obtient en résolvant les équations frontières

$$x + 2y = 8,\quad x + y = 5$$

En soustrayant, on obtient $y = 3$, puis $x = 2$.

Tester l’objectif à chaque sommet

Calculons le profit à chaque sommet :

• En $(0,0)$, $P = 0$
• En $(5,0)$, $P = 15$
• En $(0,4)$, $P = 20$
• En $(2,3)$, $P = 21$

Donc le profit maximal est

$$P = 21$$

atteint en

$$(x,y) = (2,3)$$

Voilà la méthode graphique en une phrase : tracer la région réalisable, trouver les sommets, puis y évaluer l’objectif.

Intuition de la méthode du simplexe

La méthode graphique n’est pratique que lorsqu’il y a deux variables, et parfois trois si vous acceptez de visualiser une région en 3D. Les vrais problèmes d’optimisation comportent souvent beaucoup de variables, donc représenter la région réalisable n’est plus réaliste.

La méthode du simplexe conserve la même logique des sommets, mais l’applique algébriquement. En termes généraux, elle passe d’un sommet réalisable à un autre qui améliore l’objectif, puis s’arrête lorsqu’aucun déplacement adjacent ne donne une meilleure valeur.

Un bon modèle mental est donc :

• Méthode graphique : voir les sommets
• Méthode du simplexe : parcourir les sommets sans les dessiner

Cette description donne l’intuition, pas l’algorithme complet. La procédure réelle du simplexe utilise un tableau, ou une forme algébrique équivalente, pour décider quelle variable entre et laquelle sort à chaque étape.

Pourquoi les sommets sont importants

Les fonctions objectif linéaires créent des droites de niveau telles que

$$3x + 5y = k$$

pour différentes valeurs de $k$. Lorsque vous faites glisser cette droite dans la direction d’un profit plus grand, le dernier point où elle touche encore la région réalisable est celui où le maximum est atteint.

Sur beaucoup de graphiques, ce dernier contact se produit en un seul sommet. Si la droite objectif est parallèle à un côté de la frontière, plusieurs points de ce côté peuvent tous être optimaux. Dans ce cas, il existe quand même au moins un sommet optimal.

Erreurs fréquentes

Confondre réalisable et optimal

Un point peut satisfaire toutes les contraintes sans pour autant maximiser ou minimiser l’objectif. Réalisable signifie seulement autorisé.

Oublier les conditions de non-négativité

Si $x$ et $y$ représentent des quantités produites ou transportées, des valeurs négatives n’ont généralement pas de sens. Oublier $x \ge 0$ ou $y \ge 0$ peut modifier le problème.

Supposer que toute réponse doit être un nombre entier

La programmation linéaire classique autorise des valeurs fractionnaires. Si les variables doivent être entières, comme un nombre de camions ou un nombre de travailleurs, il faut un modèle de programmation en nombres entiers ou une condition d’intégralité supplémentaire.

Supposer que tout problème a une meilleure réponse

Certains programmes linéaires sont irréalisables, ce qui signifie qu’aucun point ne satisfait toutes les contraintes. D’autres sont non bornés, ce qui signifie que l’objectif peut s’améliorer sans limite. On n’obtient un optimum fini que si les contraintes encadrent réellement suffisamment le problème.

Utiliser la méthode graphique quand il y a trop de variables

Dès qu’il y a beaucoup de variables, la représentation graphique n’est plus le bon outil. C’est là que le simplexe ou d’autres méthodes d’optimisation deviennent nécessaires.

Quand utilise-t-on la programmation linéaire ?

La programmation linéaire est utilisée lorsque des décisions se disputent des ressources limitées et que l’objectif comme les contraintes peuvent être modélisés de façon linéaire. Parmi les exemples typiques, on trouve la planification de production, le transport, les effectifs, les mélanges, l’ordonnancement et l’allocation budgétaire.

Un modèle n’est valable que dans la mesure où ses hypothèses le sont. Si la relation réelle n’est pas proche d’un modèle linéaire, ou si les variables doivent être entières, un programme linéaire classique peut n’être qu’un point de départ.

Essayez un problème similaire

Prenez un petit problème énoncé avec deux produits, deux limites de ressources et une fonction de profit. Définissez les variables, tracez les contraintes et testez vous-même les sommets. Une fois cette idée bien comprise, la méthode du simplexe devient beaucoup plus facile à comprendre, car elle prolonge la même logique dans des dimensions supérieures.