Chapitre 2 · Semestre 5

La résolution graphique d'un programme linéaire

Intelligence Artificielle et Recherche Opérationnelle

Cours Exercices Résumé QCM

Objectifs du chapitre — À la fin de ce chapitre, vous saurez :

tracer le domaine des solutions réalisables d'un programme à deux variables ;

trouver l'optimum par la méthode des droites d'iso-objectif et par l'énumération des sommets ;

reconnaître les contraintes saturées et non saturées ;

identifier les cas particuliers : optimum multiple, programme non borné, programme impossible, dégénérescence ;

mener une première analyse de sensibilité graphique sur un coefficient de l'objectif.

2.1 Le domaine des solutions réalisables

Avec deux variables, chaque contrainte $a_1 x_1 + a_2 x_2 \le b$ définit un demi-plan limité par la droite $a_1 x_1 + a_2 x_2 = b$. Pour la tracer, on calcule ses points d'intersection avec les axes : $(b/a_1 ; 0)$ et $(0 ; b/a_2)$. Pour savoir quel côté retenir, on teste un point simple, en général l'origine.

Définition — Domaine réalisable : ensemble des points qui vérifient toutes les contraintes, positivité comprise. C'est l'intersection des demi-plans : un polygone convexe (éventuellement non borné).

Pour l'atelier de meubles de Salé (chapitre 1), les droites sont :

menuiserie $2x_1 + x_2 = 100$ : points $(50 ; 0)$ et $(0 ; 100)$ ;
finition $x_1 + x_2 = 80$ : points $(80 ; 0)$ et $(0 ; 80)$ ;
bois $x_1 = 40$ : droite verticale.

L'origine vérifie les trois contraintes : on garde, pour chacune, le côté de l'origine. Le domaine est le polygone de sommets $O(0 ; 0)$, $A(40 ; 0)$, $B(40 ; 20)$, $C(20 ; 60)$ et $D(0 ; 80)$.

2.2 Le théorème fondamental

Théorème fondamental de la programmation linéaire : si un programme linéaire admet une solution optimale, alors au moins un sommet du domaine réalisable est optimal.

Ce résultat vient de la linéarité de l'objectif : en se déplaçant dans une direction, $Z$ augmente ou diminue de façon régulière, jusqu'à buter sur le bord du domaine. Il suffit donc d'examiner les sommets, en nombre fini. C'est aussi l'idée du simplexe (chapitre 3) : passer d'un sommet à un sommet voisin meilleur.

2.3 Deux méthodes pour trouver l'optimum

Méthode des droites d'iso-objectif. On trace une droite $300\,x_1 + 200\,x_2 = k$ pour une valeur arbitraire de $k$ (par exemple 6 000). Toutes les droites d'iso-profit sont parallèles, de pente $-c_1/c_2 = -1{,}5$. On déplace cette droite parallèlement à elle-même dans le sens où $Z$ augmente, jusqu'au dernier point de contact avec le domaine.

Méthode des sommets. On calcule les coordonnées de chaque sommet (intersection de deux droites) et la valeur de $Z$ :

Sommet	Intersection	$(x_1 ; x_2)$	$Z = 300\,x_1 + 200\,x_2$
O	axes	(0 ; 0)	0
A	bois et axe $x_1$	(40 ; 0)	12 000
B	bois et menuiserie	(40 ; 20)	16 000
C	menuiserie et finition	(20 ; 60)	18 000
D	finition et axe $x_2$	(0 ; 80)	16 000

Le sommet C s'obtient en résolvant $2x_1 + x_2 = 100$ et $x_1 + x_2 = 80$ : par soustraction, $x_1 = 20$, puis $x_2 = 60$.

L'atelier doit produire 20 tables et 60 chaises par semaine, pour une marge de 18 000 DH.

2.4 Contraintes saturées et ressources disponibles

On remplace la solution dans chaque contrainte :

menuiserie : $2 \times 20 + 60 = 100$ : contrainte saturée (toutes les heures sont utilisées) ;
finition : $20 + 60 = 80$ : saturée ;
bois : $20 < 40$ : non saturée, il reste de quoi faire 20 plateaux ($s_3 = 20$).

Une contrainte non saturée n'est pas une ressource rare : en acheter davantage ne servirait à rien. En revanche, une heure de menuiserie ou de finition supplémentaire augmenterait la marge : le chapitre 4 calcule de combien (prix fictif ou valeur marginale).

2.5 Les cas particuliers

Cas	Ce que l'on observe	Exemple
Optimum multiple	La droite d'iso-objectif est parallèle à un côté du domaine : tout le segment est optimal	Marge de la table portée à 400 DH : $Z$ parallèle à la menuiserie, B et C donnent 20 000
Programme non borné	Le domaine est ouvert dans la direction d'amélioration : $Z$ peut croître indéfiniment	Oubli d'une contrainte de capacité
Programme impossible	Les contraintes sont incompatibles : le domaine est vide	$x_1 + x_2 \le 5$ et $x_1 + x_2 \ge 8$
Dégénérescence	Plus de deux contraintes passent par le sommet optimal	Trois droites concourantes

Un programme non borné ou impossible signale presque toujours une erreur de modélisation : une contrainte oubliée ou mal orientée.

2.6 Une première analyse de sensibilité

Jusqu'où la marge d'une table peut-elle varier sans que la solution change ? Le sommet C reste optimal tant que la pente de l'objectif reste comprise entre les pentes des deux contraintes saturées : $-2$ (menuiserie) et $-1$ (finition). Avec $c_2 = 200$ :

$$1 \le \frac{c_1}{200} \le 2 \quad \Longleftrightarrow \quad 200 \le c_1 \le 400$$

Tant que la marge d'une table reste entre 200 et 400 DH, le programme de production (20 tables, 60 chaises) ne change pas ; seule la valeur de $Z$ varie. Au-delà de 400 DH, il devient intéressant de produire davantage de tables (sommet B) ; en dessous de 200 DH, davantage de chaises (sommet D).

2.7 Méthode : résoudre graphiquement un programme linéaire

Tracer chaque droite-frontière avec ses deux points d'intersection avec les axes.
Pour chaque contrainte, déterminer le demi-plan valide (test de l'origine) et hachurer.
Repérer le domaine réalisable et ses sommets.
Calculer les coordonnées des sommets (systèmes de deux équations) et la valeur de l'objectif.
Retenir le meilleur sommet ; confirmer avec une droite d'iso-objectif.
Identifier les contraintes saturées et les écarts ; commenter.

Les pièges à éviter

Retenir le mauvais côté d'une contrainte $\ge$ : l'origine ne la vérifie généralement pas.
Calculer l'intersection de deux droites dont le point d'intersection n'appartient pas au domaine (il viole une autre contrainte).
Conclure qu'il n'y a pas d'optimum quand le domaine est non borné : en minimisation, un domaine ouvert « vers le haut » admet souvent un optimum.
Oublier que l'optimum peut ne pas être unique.
Confondre la pente $-c_1/c_2$ de la droite d'iso-objectif avec $-c_2/c_1$.

Exercice 1 — Ration alimentaire au moindre coût

Un éleveur de la région de Béni Mellal compose une ration journalière à partir de deux aliments. L'aliment 1 coûte 4 DH le kg et l'aliment 2 coûte 3 DH le kg. La ration doit apporter au moins 10 unités de protéines, 7 unités d'énergie et 12 unités de minéraux. Un kg d'aliment 1 apporte 2 unités de protéines, 1 d'énergie et 1 de minéraux ; un kg d'aliment 2 apporte 1, 1 et 3 unités.

Travail à faire :

Formulez le programme linéaire.
Représentez le domaine réalisable et déterminez ses sommets.
Déterminez la ration optimale et son coût. Quelles contraintes sont saturées ?
Le prix de l'aliment 1 baisse à 3 DH. Que devient la solution ?

Voir le corrigé

1) Variables : $x_1$, $x_2$ = kg d'aliment 1 et 2 par jour.

$$\min Z = 4\,x_1 + 3\,x_2 \quad \text{s.c.} \quad \begin{cases} 2x_1 + x_2 \ge 10 & \text{(protéines)} \\ x_1 + x_2 \ge 7 & \text{(énergie)} \\ x_1 + 3x_2 \ge 12 & \text{(minéraux)} \\ x_1, x_2 \ge 0 \end{cases}$$

2) Droites : protéines $(5 ; 0)$-$(0 ; 10)$ ; énergie $(7 ; 0)$-$(0 ; 7)$ ; minéraux $(12 ; 0)$-$(0 ; 4)$. L'origine ne vérifie aucune contrainte : on garde les demi-plans « au-dessus ». Le domaine est non borné vers le haut, de sommets :

$P(0 ; 10)$ : protéines et axe $x_2$ ;
$Q(3 ; 4)$ : protéines et énergie ($2x_1 + x_2 = 10$ et $x_1 + x_2 = 7$ donnent $x_1 = 3$) ;
$R(4{,}5 ; 2{,}5)$ : énergie et minéraux ($x_1 + x_2 = 7$ et $x_1 + 3x_2 = 12$ donnent $2x_2 = 5$) ;
$S(12 ; 0)$ : minéraux et axe $x_1$.

3) Coûts : $Z(P) = 30$ ; $Z(Q) = 12 + 12 = \mathbf{24}$ ; $Z(R) = 18 + 7{,}5 = 25{,}5$ ; $Z(S) = 48$. La ration optimale est 3 kg d'aliment 1 et 4 kg d'aliment 2, pour 24 DH par jour. Le domaine est non borné, mais en minimisation avec des coûts positifs, l'optimum existe.

Contraintes : protéines $6 + 4 = 10$ (saturée) ; énergie $3 + 4 = 7$ (saturée) ; minéraux $3 + 12 = 15 > 12$ (excédent de 3 unités).

4) Avec $Z = 3x_1 + 3x_2 = 3\,(x_1 + x_2)$, la droite d'iso-coût est parallèle à la contrainte d'énergie. Tous les points du segment $[Q ; R]$ ont $x_1 + x_2 = 7$ et coûtent 21 DH : $Z(Q) = Z(R) = 21$, alors que $Z(P) = 30$ et $Z(S) = 36$. L'optimum est multiple : l'éleveur peut choisir n'importe quelle ration de ce segment, par exemple selon la disponibilité des aliments.

Exercice 2 — Une huilerie de Taounate

Une huilerie produit de l'huile d'olive vierge extra ($x_1$, en centaines de litres) et de l'huile vierge ($x_2$). Marges : 50 et 40 (centaines de DH). Contraintes hebdomadaires : pressoir $3x_1 + 5x_2 \le 150$ heures, filtration $8x_1 + 5x_2 \le 300$ heures, demande d'huile vierge $x_2 \le 20$.

Déterminez les sommets du domaine réalisable.
Trouvez la production optimale et la marge maximale.
Quelles contraintes sont saturées ? Interprétez l'écart de la contrainte de demande.

Voir le corrigé

1) Sommets : $O(0 ; 0)$ ; $(37{,}5 ; 0)$ sur la filtration ; intersection pressoir-filtration : $8x_1 - 3x_1 = 300 - 150$, d'où $x_1 = 30$ et $x_2 = (150 - 90)/5 = 12$ ; intersection pressoir-demande : $x_2 = 20$, $x_1 = (150 - 100)/3 \approx 16{,}67$ ; $(0 ; 20)$.

2) $Z(37{,}5 ; 0) = 1\,875$ ; $Z(30 ; 12) = 1\,500 + 480 = \mathbf{1\,980}$ ; $Z(16{,}67 ; 20) \approx 833 + 800 = 1\,633$ ; $Z(0 ; 20) = 800$. Optimum : 3 000 litres d'extra et 1 200 litres de vierge, marge de 198 000 DH.

3) Pressoir ($90 + 60 = 150$) et filtration ($240 + 60 = 300$) sont saturés. La demande d'huile vierge n'est pas saturée ($12 < 20$) : l'huilerie pourrait vendre 800 litres de plus, mais ce n'est pas rentable compte tenu des capacités.

Exercice 3 — Reconnaître les cas particuliers

Pour chaque programme, dites s'il a une solution optimale, et laquelle :

$\max Z = 3x_1 + 2x_2$ sous $x_1 - x_2 \le 2$, $x_1 \ge 1$, $x_1, x_2 \ge 0$.
$\max Z = x_1 + x_2$ sous $x_1 + 2x_2 \le 4$, $x_1 + 2x_2 \ge 6$, $x_1, x_2 \ge 0$.
$\min Z = 3x_1 + 2x_2$ sous les mêmes contraintes qu'au 1).

Voir le corrigé

1) Non borné. Les points $(1 ; t)$ vérifient les contraintes pour tout $t \ge 0$ et $Z = 3 + 2t$ croît sans limite : une contrainte de capacité a sans doute été oubliée.

2) Impossible. On ne peut avoir à la fois $x_1 + 2x_2 \le 4$ et $x_1 + 2x_2 \ge 6$ : le domaine est vide.

3) Le domaine est le même (non borné), mais on minimise un objectif à coefficients positifs : on cherche le point le plus proche de l'origine. Avec $x_1 \ge 1$ et $x_2 \ge 0$, le minimum est en $(1 ; 0)$, qui vérifie $1 - 0 \le 2$ : $Z = \mathbf{3}$. Un domaine non borné n'empêche pas l'existence d'un optimum.

L'essentiel — Méthode graphique

Chaque contrainte = demi-plan ; domaine réalisable = intersection = polygone convexe.
Théorème fondamental : si un optimum existe, il est atteint en (au moins) un sommet.
Droites d'iso-objectif $c_1 x_1 + c_2 x_2 = k$ parallèles, de pente $-c_1/c_2$ ; on les déplace dans le sens d'amélioration.
Méthode des sommets : coordonnées (systèmes 2 × 2) et valeur de $Z$ en chaque sommet.
Contrainte saturée : utilisée à 100 % (ressource rare) ; non saturée : écart positif.
Cas particuliers : optimum multiple (objectif parallèle à un côté), non borné, impossible (domaine vide), dégénérescence.
Sensibilité : le sommet reste optimal tant que la pente de l'objectif reste entre celles des contraintes saturées.
Fil rouge : 20 tables, 60 chaises, $Z = 18\,000$ DH ; $c_1 \in [200 ; 400]$.

S'entraîner sur des sujets réels

Des sujets réels de concours (master, licence d'excellence) avec une épreuve de Intelligence Artificielle et Recherche Opérationnelle : énoncé complet et corrigé indicatif.

Voir les 13 sujets de concours en Intelligence Artificielle et Recherche Opérationnelle →