CHAPITRE 3

Programmation linéaire

I) Formulation d’un programme linéaire (PL) et sa résolution graphique

1) Exemple Introductif (Problème d’agriculture)

Un agriculteur veut allouer 150 hectares de surface irrigable entre culture de tomates et celles de
piments. Il dispose de 480 heures de main d’œuvre et de 440 m3 d’eau. Un hectare de tomates demande
1 heure de main d’œuvre, 4 m3 d’eau et donne un bénéfice net de 1000 dirhams. Un hectare de piments
demande 4 heures de main d’œuvre, 2 m3 d’eau et donne un bénéfice net de 2000 dirhams.
Le bureau du périmètre irrigué veut protéger le prix des tomates et ne lui permet pas de cultiver plus
de 90 hectares de tomates. Quelle est la meilleure allocation de ses ressources ?
Formulation du problème en un PL :

Etape 1 : Identification des variables de décision. Les deux activités que l’agriculteur doit déterminer
sont les surfaces à allouer pour la culture de tomates et de piments :
 x1 : la surface allouée à la culture des tomates
 x2 : la surface allouée à la culture des piments
On vérifie bien que les variables de décision x1 et x2 sont positives : x1  0, x2  0 .
Etape 2 : Identification des contraintes. Dans ce problème les contraintes représentent la disponibilité
des facteurs de production :
 Terrain : l’agriculteur dispose de 150 hectares de terrain, ainsi la contrainte liée à la limitation de la
surface de terrain est x1  x2  150
 Eau : la culture d’un hectare de tomates demande 4 m3 d’eau et celle d’un hectare de piments
demande 2m3 mais l’agriculteur ne dispose que de 440m3. La contrainte qui exprime les limitations
des ressources en eau est 4 x1  2 x2  440 .
 Main d’œuvre : Les 480 heures de main d’œuvre seront départager (pas nécessairement en totalité)
entre la culture des tomates et celles des piments. Sachant qu’un hectare de tomates demande une
heure de main d’œuvre et un hectare de piments demande 4 heures de main d’œuvre alors la
contrainte représentant les limitations des ressources humaines est x1  4 x2  480
 Les limitations du bureau du périmètre irrigué : Ces limitations exigent que l’agriculteur ne cultive
pas plus de 90 hectares de tomates. La contrainte qui représente cette restriction est x1  90.
Etape 3 : Identification de la fonction «objectif». La fonction «objectif» consiste à maximiser le profit
apporté par la culture de tomates et de piments. Les contributions respectives 1000 et 2000, des deux
variables de décision x1 et x2 sont proportionnelles à leur valeur. La fonction «objectif» est donc
z  1000x1  2000x2 .
Max 1000x  2000x
1 2
s.c. x x  150
1 2
4 x  2 x  440
Le programme linéaire qui modélise le problème d’agriculture est : 1 2
x  4 x  480
1 2
x  90
1
x  0, x  0
1 2
 2) Les étapes de formulation d’un PL :
Généralement il y a trois étapes à suivre pour pouvoir construire le modèle d'un programme linéaire :
1. Identifier les variables du problème à valeur non connues (variable de décision) et les représenter
sous forme symbolique (exemple :x1, y1).
2. Identifier les restrictions (les contraintes) du problème et les exprimer par un système d’équations
linéaires.
3. Identifier l’objectif ou le critère de sélection et le représenter sous une forme linéaire en fonction
des variables de décision. Spécifier si le critère de sélection est à maximiser ou à minimiser.

Présentation Théorique
Un programme linéaire consiste à trouver le maximum ou le minimum d’une forme linéaire dite
fonction objectif en satisfaisant certaines équations et inégalités dites contraintes. En langage
mathématique, on décrira de tels modèles de la manière suivante

Soient N variables de décision x1, x2,…, xn, l’hypothèse que les variables de décision sont positives
implique que x1  0, x2  0, , x N  0 .

La fonction «objectif» est une forme linéaire en fonction des variables de décision de type
z  c1x1  c2 x2    c N x N
où les coefficients c1,…,cN doivent avoir une valeur bien déterminée (avec certitude) et peuvent être
positifs, négatifs ou nuls. Par exemple le coefficient ci peut représenter un profit unitaire lié à la
production d’une unité supplémentaire du bien xi, ainsi la valeur de z est le profit total lié à la production
des différents biens en quantités égales à x1 , x2 , , x N .

Supposons que ces variables de décision doivent vérifier un système d’équations linéaires définis par
M inégalités

a11 x1  a12 x2    a1 N x N  b1
a21 x1  a22 x2    a2 N x N  b2

a M 1 x1  a M 2 x2    a MN x N  bM

Où les coefficients a1M,…, aMN et b1,…, bM doivent avoir une valeur bien déterminée (avec certitude) et
peuvent être positifs, négatifs ou nuls.

En suivant les étapes de formulation ci-dessus, on peut représenter le PL comme suit :

Max c1 x1  c2 x2    c N x N
s.c a11 x1  a12 x2    a1N x N  b1
a21 x1  a22 x2    a2 N x N  b2

aM 1 x1  aM 2 x2    aMN x N  bN
x1  0, x2  0, , x N  0
3) Résolution graphique
Soit le programme linéaire suivant : On le note par (P1)
 Min x1  x2
s.c. 2x1  x2 12
5x1 8x2  74
x1 6x2  24
x1  0, x2  0

a) Représentation graphique des contraintes

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 au-dessus.
Une des contraintes est :2𝑥1 + 𝑥2 ≥ 12.
L’ensemble des solutions qui vérifient cette inégalité est le même que celui qui vérifie
2𝑥1 + 𝑥2 = 12 et 2𝑥1 + 𝑥2 > 12.
x2

12

6
3

x1
6 12 24

L’ensemble des solutions qui correspond à l’équation est l’ensemble des points de la droite l définie
par𝑥2 = −2𝑥1 + 12. Cette droite admet une valeur de la pente égale à
–2 et intercepte l’axe des ordonnées en 12 (voir figure ci-dessus).
L’inégalité 2𝑥1 + 𝑥2 > 12 correspond à un demi-plan limité par la droite
𝑥2 = −2𝑥1 + 12. Or cette droite divise le plan en deux demi-plans ouverts donc quel est le demi-plan à
choisir ?
x2

12 P1

6
3

x1
6 12 24

Pour ce faire, il suffit de prendre un point de l’un des demi-plans (c’est à dire n’appartenant pas à la
droite𝑥2 = −2𝑥1 + 12) et voir s’il vérifie l’inégalité
2𝑥1 + 𝑥2 > 12. Par exemple le point de coordonnées (0,0) ne vérifie pas l’inégalité 2𝑥1 + 𝑥2 > 12 donc
le demi-plan 𝑃1 au-dessus de droite est celui recherché (voir figure ci-dessus).L’espace hachuré
représente le demi-plan fermé des solutions qui vérifient la contrainte 2𝑥1 + 𝑥2 > 12.
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 𝑒𝑡 𝑃3 relatifs aux solutions vérifiant
respectivement les contraintes 5𝑥1 + 8𝑥2 ≥ 74 𝑒𝑡 𝑥1 + 6𝑥2 ≥ 24.
 P3 P2
9.25

6
4
3

x1 x1
6 12 24 6 14,8 24

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 (voir figure).
x2
Ensembledes
12 solutions
réalisables

x1
6 12 24

Définition : Un ensemble E non vide est dit convexe si et seulement si pour tout élément x et y de E et
pour tout 𝜆 ∈ [0, 1], 𝜆𝑥 + (1 − 𝜆)𝑦 ∈ 𝐸 .
On peut vérifier facilement que chacun des demi-plans𝑃1 , 𝑃2 , 𝑃3 est convexe en vérifiant que pour toute
paire de points M1 et M2, l’ensemble des points qui forment le segment [M1M2] appartient au demi-plan.
Théorème : L’intersection d’ensembles convexes (non vide) est convexe.
Propositions : L’ensemble des solutions réalisables (non vide) est convexe.

b) Représentation de la fonction objectif

Soit z la valeur de la fonction objectif du problème (P1) : 𝑧 = 𝑥1 + 𝑥2 .

On a 𝑧 = 𝑥1 + 𝑥2 ⇔ 𝑥1 + 𝑥2 − 𝑧 = 0, d'où z représente l'abscisse à l'origine de la droite
𝑥1 + 𝑥2 − 𝑧 = 0, son vecteur directeur est 𝑢 ⃗ = (−1,1).
Pour z=0, la fonction «objectif» est représentée de la manière suivante :

x2

12

𝑢
⃗ 3
z

x1
6 24

x1  x2  z

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. De
plus on peut diminuer la valeur de z indéfiniment
Le problème est de connaître qu’elle est la droite qui correspond à la valeur minimal de la fonction
objectif ?
c) Recherche de la solution optimale
i. 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.
x2

12
B

x1
6 12
Z=10

Dans notre exemple, la solution optimale est l’intersection des deux contraintes
5𝑥1 + 8𝑥2 ≥ 74 𝑒𝑡 2𝑥1 + 𝑥2 ≥ 12. Une évaluation des coordonnées de ce point revient à résoudre le
système linéaire suivant :

2𝑥1 + 𝑥2 = 12
{
5𝑥1 + 8𝑥2 = 74

Elle correspond d’après le graphique au point (2,8). Le nombre minimal de z (la valeur de la fonction
objectif) est égale à 10.

ii. Résolution par énumération :

On remarque que la solution optimale du problème est un point extrême qui se trouve sur le bord de
l’ensemble des solutions. Une telle solution est dite solution réalisable de base.
On peut admettre le résultat suivant :
« Si un programme linéaire admet une solution optimale alors il existe une solution réalisable de base
pour laquelle la fonction objectif atteint la valeur optimale »

Une méthode de résolution du programme linéaire consiste donc à déterminer les solutions réalisables
de base (les points d’intersection des droites qui forment les contraintes) et à calculer pour chaque
point la valeur de la fonction objectif. La solution du programme linéaire est la solution à qui on associe
la valeur optimale de la fonction objectif.
x2

12 A
B

3 C D

x1
6 12

Dans le problème, l’ensemble des solutions réalisables de base présente 4 points extrêmes A(0,12),
B(2,8), C(23/11, 126/11) et D(24,0). La valeur de la fonction «objectif» associée respectivement à A, B,
C et D est 12, 10, 149/11 et 24. On vérifie bien que B est la solution optimale du problème avec une
valeur optimale égale à 10.

iii. Exemples

Dans cette section on donne quelques exemples de résolution graphique de problèmes

linéaires relatifs au différents cas possibles :
 Problème de maximisation
Max 100x1 + 200x 2 x2 (2)
(4)
s.c. x1 + x 2  150 (1 ) A
B
4 x1 + 2 x 2  440 ( 2 ) 110
C
x1 + 4 x 2  480 (3) (3)
x1  90 (4) Z=0 30
D (1)
x1  0, x 2  0
E x1
40

la solution optimale est B(40,110)

Problème avec solution non bornée

Min - 2 x1 + 3x 2 x2

s.c. x1  5 (1 ) (2)

2 x1  3x 2  6 (2)
x1  0, x 2  0
5 x1
Z=0
(1)

On peut augmenter la valeur de la fonction objectif dans la direction des

flèches indéfiniment donc la solution est non bornée

Problème impossible
Min 31
x 2x2 x2
s
.c. 1
x 2x22 (1)
21
x 4x28 (2)
1
x 0,x20

x1
(2)
(1)

L’espace des solutions réalisables est vide, il est l’intersection des deux
zones grises de la figure ci-dessus

Problème à solutions multiples

Max x13x2 x2
(2)
s.c. 2x16x2 30 (1) (1)
x110 (2) A (3)

x2 4 (3) B

x10,x2 0
10 x1

Z=0

L’ensemble des points décrit par le segment [AB] représente les solutions
optimales du problème linéaire