13/10/2023
Abdelaziz ZEGNANI
[Link]@[Link]
Introduction
Système d’axes
Représentation graphique des
contraintes
Représentation de la fonction objectif
Recherche de la solution optimale
Exemples
Analyse de sensibilité
1
13/10/2023
Après avoir illustrer comment un
problème pratique peut être modélisé
par un programme linéaire, l’étape qui
va suivre sera certainement celle de la
résolution de ce problème
mathématique. La méthode graphique
est l’une des premières méthodes
utilisées à ce sujet.
Si on parle de résolution graphique alors
on doit se limiter à une représentation à
deux variables et au plus à trois
variables.
3
Une des conditions de la réussite de notre
représentation graphique est le choix
d'un système d’axes. Un mauvais choix
peut rendre notre représentation non
claire et imprécise.
2
13/10/2023
A cause des contraintes de non-
négativité des variables de décision,
nous nous intéressons seulement au
cadran positif. Cette région s’appelle
la région des solutions possibles du
problème.
Prenons l’exemple relatif au problème
de médecine. Le programme linéaire
est le suivant :
Min x1 + x 2
s .c . 2 x1 + x 2 ≥ 12
5 x1 + 8 x 2 ≥ 74
x1 + 6 x 2 ≥ 24
x1 ≥ 0, x 2 ≥ 0
6
3
13/10/2023
Un bon choix se base sur une lecture des
différents paramètres du programme
linéaire. Dans notre cas, on ne peut
qualifier de bon, le choix de 20 comme
unité dans les deux axes.
Pour l’exemple, on peut choisir le
système d’axes suivant :
x2
12
6
3
x1
6 12 24
4
13/10/2023
Parmi les solutions possibles d’un
problème, il y a ceux qui vont satisfaire
toutes les contraintes du programme,
appelés solutions réalisables, et ceux qui
vont satisfaire une partie ou aucune de
ces contraintes, appelés solutions non
réalisables.
Une représentation graphique des
inégalités (des contraintes) va nous
permettre de déterminer l’ensemble des
solutions réalisables.
Revenons à l’exemple du problème de
médecine. Une des contraintes de ce
problème est celle relative au grain
d’aspirine : 2 x + x ≥ 12
1 2
L’ensemble des solutions qui vérifient
cette inégalité est le même que celui
qui vérifie
2 x1 + x2 = 12 et 2 x1 + x2 > 12
10
5
13/10/2023
L’ensemble des solutions qui correspond
à l’équation est l’ensemble des points de
la droite l définie par x2 = −2 x1 + 12
x2
12
6
3
x1
6 12 24
11
Cette droite admet une valeur de la pente
égale à –2 et intercepte l’axe des
ordonnées en 12.
L’inégalité 2 x1 + x2 > 12 correspond à un
demi-plan limité par la droite x2 = −2 x1 + 12..
Or cette droite divise le plan en deux
demi-plans ouverts donc quel est le
demi-plan à choisir ?
12
6
13/10/2023
Pour ce faire, il suffit de prendre un point
de l’un des demi-plans (c’est à dire
n’appartenant pas à la droite ) et voir s’il
vérifie l’inégalité . Par exemple le point
de coordonnées (0,0) ne vérifie pas
l’inégalité donc le demi-plan π1 au-
dessus de la droite est celui recherché.
13
L’espace hachuré représente le demi-
plan fermé des solutions qui vérifient la
contrainte 2 x1 + x2 > 12 .
x2
12 π1
6
3
x1
6 12 24
14
7
13/10/2023
Si on fait de même pour les deux autres
contraintes du problème (voir figures
ci-dessous), on obtient les deux autres
demi-plans π2 et π3 relatifs aux solutions
vérifiant respectivement les contrainte:
5 x1 + 8 x 2 ≥ 74
et
x1 + 6 x 2 ≥ 24
15
π2 π3
9.25
6
4
3
x1 x1
6 14,8 24 6 12 24
16
8
13/10/2023
Une solution possible du problème est
dite réalisable si et seulement si elle
vérifie toutes les contraintes, c’est à dire
si elle appartient aux trois demi-plans
relatifs à chaque contrainte du
programme linéaire, en d’autre terme à
π1 ∩ π2 ∩ π3 .
17
x2
E nse m b le d es
12 so lu t io n s
réa lisa b le s
x1
6 12 24
18
9
13/10/2023
Soit z la valeur de la fonction objectif du
problème de médecine .
z = x1 + x2
19
Pour z=0, la fonction objectif est
représentée de la manière suivante :
x2
12
x1
6 24
x1 + x 2 = 0
20
10
13/10/2023
Pour z=6, c’est à dire que le nombre de
pilules à prescrire est égale à 6 pilules.
La fonction objectif est représentée
comme suit : x2
12
x1
6 24
x1 + x 2 = 6
21
Pour z=6, c’est à dire que le nombre de
pilules à prescrire est égale à 6 pilules.
La fonction objectif est représentée
comme suit : x2
12
x1
6 24
x1 + x 2 = 6
22
11
13/10/2023
Chaque point du segment qui relie les
points (6,0) à (0,6) représente des
solutions qui engendrent une
prescription avec 6 pilules des deux
tailles.
On peut tracer une infinité de droites qui
représentent les différentes valeurs de la
fonction objectif, toutes ces droites ont le
même coefficient directeur (-1). Par suite
elles sont parallèles entre elles.
23
De plus on peut diminuer la valeur de z
indéfiniment dans le sens indiqué dans
la figure suivante.
x2
12
x1
6
z = 18
z = 6 z = 12 24
12
13/10/2023
Le problème est de connaître
qu’elle est la droite qui
correspond à la valeur minimal
de la fonction objectif ?
25
a. Résolution graphique
Si nous retraçons l’ensemble des droites
parallèles relatives à différentes
valeurs de la fonction objectif sur la
figure qui représente l’ensemble des
solutions réalisables, on peut localiser
la solution optimale. Elle correspond à
la solution réalisable qui intercepte la
droite à la plus petite valeur de z.
26
13
13/10/2023
x2
E n se mb le d e s
12 so lu tio n s
r éalisab le s
x1
6 12 24
Z= 6 Z = 12
27
x2
12
B
x1
6 12
Z = 10
28
14
13/10/2023
Elle correspond d’après le graphique au
point (2,8). Donc la prescription
optimale est de 2 pilules de petite taille
et 8 pilules de grande taille. Le nombre
de pilules (la valeur de la fonction
objectif) est égale à 10.
29
15