Chapitre X

Programmation linéaire et méthode du simplexe

Notes de cours préparées par Anik Soulière avec l’aide des documents de Julie Milot, Bruno Perron et Alain Tranchida.
Modification par Marc-Élie Lapointe.

L’objectif du présent chapitre est de voir comment on peut résoudre des problèmes où on veut
maximiser ou minimiser une fonction qui dépendant de plusieurs variables qui sont soumises à
plusieurs contraintes.

Le nom du domaine qui traite ce genre de problème est la recherche opérationnelle.

Recherche opérationnelle : (aussi appelée aide à la décision) peut être définie comme l'ensemble des
méthodes et techniques rationnelles orientées vers la recherche de la meilleure façon d'opérer des choix
en vue d'aboutir au meilleur résultat possible.

Optimisation : recherche du maximum (ou du minimum) d’une fonction ainsi que des valeurs des
variables qui maximisent (ou minimisent) la fonction.

Exercices
Où sont les maximums et minimums (absolus) de ces fonctions?

Exemple 1 Exemple 2 Exemple 3

y  x3  3x 2  x 2  3x avec 0  x  4 y  2x avec 0  x  1  x1  2 x2  20
une variable indépendante une variable indépendante, 2 x  x  22

fonction linéaire (droite) z  20 x1  30 x2 avec  1 2
 x1  x2  12
 x1  0, x2  0
deux variables indépendantes,
fonction linéaire (plan)

Programmation linéaire (ou optimisation linéaire) : branche des mathématiques qui s’intéresse à
l’optimisation de fonctions linéaires comportant plusieurs variables indépendantes soumises à des
contraintes pouvant être représentées à l’aide d’équations ou d’inéquations linéaires.

Fonction économique : fonction qui traduit ce que l’on veut maximiser ou minimiser (très souvent de
l’argent, mais pas toujours).

Variables de décision : variables indépendantes dont la fonction économique dépend.

Chapitre X : programmation linéaire, page 1

 Deux façons de résoudre un problème de programmation linéaire

Méthode graphique Méthode du simplexe

Pour résoudre un problème de programmation Méthode algorithmique plus rapide pour résoudre
linéaire simple ayant seulement 2 variables de les problèmes comportant un grand nombre de
décisions. Cela permet de visualiser le principe variables. Elle est généralement programmée et
général de la programmation linéaire. Cette calculée à l’ordinateur.
méthode est beaucoup trop longue et difficile,
voire impossible, à visualiser s’il y a plus de 2 Les étapes seront données plus loin.
variables.

Rappel :

Une fonction linéaire à plusieurs variables peut être traduit par une équation de la forme :

y  a1 x1  a2 x2  ...  an xn
où y est la variable dépendante,
a1 , a2 ,..., an sont des coefficients constants réels,
x1 , x2 ,..., xn sont des variables indépendantes.

Exercices
Parmi ces fonctions, indiquez lesquelles correspondent à une fonction linéaire ?

Question 1
A : y  x 3  3x 2  x 2  3x B: y  3x C: P  x 2 D: M  sin t  cos t

Question 2
A : y  ln x B: P  4 x  7 y  3z  9w C: P  e x +1000 D: P  4 x  7 y

Question 3
A : y  log 2 x B: y  x  5 C: P  3x1  45x2  0,78x3 D: M  xyz  x  3z

Remarque : une fonction linéaire peut être représentée par une droite, un plan, un ‘’hyper-plan’’, etc.

Chapitre X : programmation linéaire, page 2

Exemple 1 (par la méthode graphique)

Le directeur d’une manufacture de meubles décide de fabriquer deux nouveaux modèles de tables ;
le modèle « régulier » et le modèle « chic ». Le modèle « régulier » requière 1 heure de sciage, 2
heures d’assemblage et 1 heure de finition. Le modèle « chic » nécessite 2 heures de sciage, 1 heure
d’assemblage et 1 heure de finition. La manufacture dispose quotidiennement de 20 heures à
l’atelier de sciage, de 22 heures à l’atelier d’assemblage et de 12 heures à l’atelier de finition. Les
profits que la compagnie peut réaliser pour chacun des modèles sont de 20$ pour le modèle
« régulier » et de 30$ pour le modèle « chic ». Le directeur désire déterminer le nombre de tables de
chaque modèle qu’il doit fabriquer par jour pour obtenir un profit maximal.

Solution : ce problème est assez simple puisqu’il ne contient que 2 variables de décisions. Nous allons
utiliser la méthode graphique. Voici les étapes à suivre.

1. Variables : identifier les variables du problème.

2. Fonction économique : déterminer la fonction économique et indiquer s’il faut la maximiser

ou la minimiser.

3. Contraintes technologiques : définir les contraintes technologiques à l’aide d’inéquations

linéaires. Ajouter des contraintes de non-négativité sur les variables.

4. Polygone de contraintes : représenter graphiquement les contraintes et le polygone de

contraintes.

x1  2 x2  20 (sciage)

Droite frontière D1 : x1  2 x2  20
Truc pour la tracer :
trouver 2 points x1  0  x2  10
x2  0  x1  20

(0,10) et (20,0)

Choisir la bonne région. 0  2  0  0  20

Truc : est-ce que (0,0) Donc (0,0) fait partie de
satisfait l’inéquation ?
la région

Chapitre X : programmation linéaire, page 3

 10

0
10

Théorème fondamental de la programmation linéaire

Si la valeur optimale d’une fonction économique d’un problème de programmation linéaire existe, alors
cette valeur est atteinte à au moins un des sommets du polygone convexe délimitant le domaine
réalisable.

Pourquoi c’est vrai, en image :

Nous allons donc trouver les sommets à l’intersection des droites.

Chapitre X : programmation linéaire, page 4

 5. Sommets du polygone de contraintes : calculer les coordonnées des sommets du
polygone de contrainte. Cela revient à trouver l’intersection de chaque paire de droites.

6. Valeur de la fonction économique aux sommets.

Point (x1,x2) A(0,10) B(4,8) C(10,2) D(11,0) E(0,0)

P = 20x1+30x2 200$ 260$ 220$ 0$

7. Conclusion : interpréter le résultat dans le contexte.

Chapitre X : programmation linéaire, page 5

Méthode du simplexe

Reprenons le même problème que dans le dernier exemple pour vérifier que nous arrivons à la même
solution en appliquant la méthode du simplexe. Les trois premières étapes sont identiques à la méthode
graphique.

1. Identifier les variables du problème.

x1 : le nombre d’unités du modèle régulier,
x2 : le nombre d’unités du modèle chic et
P : le profit en dollars à maximiser.

2. Déterminer la fonction économique à maximiser.

P  20 x1  30 x2

3. Définir les contraintes à l’aide d’inéquations linéaires. Ne pas oublier les contraintes de
non-négativité. La fonction économique et ses contraintes ainsi définies constituent la
forme canonique du problème.
 x1  2 x2  20
2 x  x  22
 1 2

 x1  x2  12
 x1  0, x2  0

4. Traduire toutes les inéquations en équations en ajoutant des variables d’écart aux
contraintes. La nouvelle formulation du problème est appelée forme standard.
e1 : variable d’écart de la contrainte 1, explication :
ce qu’il manque à ________ pour atteindre 20
Forme Forme standard
canonique
 x1  2 x2  20  x1  2 x2  e1  20
2 x  x  22 2 x  x  22
 1 2  1 2
 
 x1  x2  12  x1  x2  12
 x1  0, x2  0 20 x1  30 x2 P 0
P  20 x1  30 x2

5. Représenter le problème sous forme matricielle

 
 
 
 
 

 

Chapitre X : programmation linéaire, page 6
« Méthode de Gauss modifiée »

 1 2 1 0 0 0 20 
 2 1 0 1 0 0 22 
 
 1 1 0 0 1 0 12 
 
 20
 30 0 0 0 1 
0 

6. Déterminer la colonne du pivot. C’est la colonne (sauf la dernière) dont l’élément de la

dernière ligne a la plus grande valeur.
L’idée : on va d’abord travailler sur la colonne de la variable qui influence le plus le profit (nombre
de tables chics, c'est-à-dire x2)

7. Déterminer la ligne du pivot. Pour ce faire, diviser chaque élément de la dernière colonne
(sauf le dernier élément) par les éléments correspondant de la colonne du pivot. La ligne où
le résultat de la division est le plus petit sans être négatif est la ligne du pivot.
L’idée : si toutes les variables étaient = 0 sauf x2, quelle ligne serait la plus contraignante pour x2 ?
C’est la ligne du pivot.

8. Encadrer le pivot. Le pivot est l’élément situé à l’intersection de la colonne et de la ligne du

pivot.

9. Annuler tous les éléments de la colonne du pivot sauf le pivot lui-même en faisant des
opérations élémentaires de lignes de la forme
a Li  b L p  Li (ligne du pivot toujours en 2e)
0
ligne
du
pivot

où Li est une ligne où on veut annuler un élément de la colonne pivot,

Lp est la ligne du pivot et a et b sont des constantes réelles positives.
NE PAS PERMUTER DES LIGNES.

 
 
 
 
 

 


Chapitre X : programmation linéaire, page 7

10. Répéter les étapes 6,7,8 et 9 jusqu’à ce que tous les éléments de la dernière ligne soient
négatifs ou nuls.

 
 
 
 
 

 


11. Encadrer les pivots, ce sont les éléments qui sont les seuls à être non nuls dans leur
colonne.
L’idée : les variables dont la colonne n’a pas de pivot sont des variables libres. L’algorithme garantie
qu’en fixant ces variables libres = 0, la solution obtenue est la solution qui maximise P.

12. Rendre tous les pivots unitaires en multipliant leur ligne par une constante appropriée au
besoin. Rendre le coefficient de la fonction économique à 1 en multipliant la dernière
ligne par une constante appropriée.
(Remarque : cette étape est facultative lorsqu’on travaille à la main. Elle est utile lorsqu’on programme
l’algorithme à l’ordinateur.)

13. Déterminer la solution optimale. Pour ce faire, poser toutes les variables libres égales à 0.
Les variables libres sont celles dont la colonne ne contient pas de pivot.
(Si l’étape 12 a été effectuée, la réponse se trouve dans la colonne de droite.)

14. Interpréter le résultat dans le contexte.

Le profit maximal est atteint lorsque …

Avec cette solution, il reste …

Chapitre X : programmation linéaire, page 8

Procédure pour résoudre un problème de maximisation
par la méthode du simplexe

1. Variables : identifier les variables du problème.

2. Fonction économique : déterminer la fonction économique et indiquer s’il faut la maximiser

ou la minimiser.

3. Contraintes technologiques : définir les contraintes technologiques à l’aide d’inéquations

linéaires. Ajouter des contraintes de non-négativité sur les variables.

4. Forme standard : traduire toutes les inéquations en équations en ajoutant des variables
d’écart aux contraintes. La nouvelle formulation du problème est appelée forme standard.

5. Forme matricielle : représenter le problème sous forme matricielle

6. Déterminer la colonne du pivot. C’est la colonne (sauf la dernière) dont l’élément

de la dernière ligne a la plus grande valeur.
7. Déterminer la ligne du pivot. Pour ce faire, diviser chaque élément de la dernière
colonne (sauf de dernier élément) par les éléments correspondant de la colonne du
pivot. La ligne où le résultat de la division est le plus petit sans être négatif est la
ligne du pivot.
8. Encadrer le pivot. Le pivot est l’élément situé à l’intersection de la colonne et de la
ligne du pivot.

9. Annuler tous les éléments de la colonne du pivot sauf le pivot lui-même en faisant
des opérations élémentaires de lignes de la forme a Li  b L p  Li
0
ligne
du
pivot

10. Répéter les étapes 6,7,8 et 9 jusqu’à ce que tous les éléments de la dernière ligne soient négatifs
ou nuls.

11. Encadrer les pivots, ce sont les éléments qui sont les seuls à être non nuls dans leur colonne.

12. (FACULTATIF)Rendre tous les pivots unitaires en multipliant leur ligne par une constante
appropriée au besoin. Rendre le coefficient de la fonction économique à 1 en multipliant la
dernière ligne par une constante appropriée.

13. Déterminer la solution optimale. Pour ce faire, poser toutes les variables libres égales à 0. Les
variables libres sont celles dont la colonne ne contient pas de pivot.

14. Interpréter le résultat dans le contexte.

Le …… maximal est atteint lorsque …

Avec cette solution, il reste …

Chapitre X : programmation linéaire, page 9

Exercices pour pratiquer séparément les différentes étapes de la méthode du simplexe.

Exercice 1
Problème : On cherche à maximiser z  8x1  12 x2  9 x3 soumise aux contraintes
4 x1  4 x2  x3  24
4 x  12 x  9 x  72
 1 2 3

4 x1  3 x3  24
 x1  0, x2  0, x3  0

Trouver la forme standard, poser le problème sous forme matricielle et trouver le premier pivot.

Exercice 2
Problème : On cherche à maximiser z  3x1  3x2 soumise aux contraintes
 x1  4 x2  12
2 x  x  10
 1 2

 x1  0
 x2  0

Trouver la forme standard, poser le problème sous forme matricielle et trouver le premier pivot.

Chapitre X : programmation linéaire, page 10

Exercice 3
Voici la matrice finale d’un problème à 2 variables de décision après avoir appliqué la méthode du
simplexe. Trouver la solution optimale si les variables sont x1 et x2 et la fonction économique est z.
0 1 1 -1 0 0 0 280
1 0 0 1 0 0 0 360
0 1 0 0 1 0 0 380
0 1 0 -1 0 -1 0 -440
0 -12 0 -4 0 0 -1 -22320

Exercice 4
Voici la matrice finale d’un problème à 3 variables de décision après avoir appliqué la méthode du
simplexe. Trouver la solution optimale si les variables sont x1 x2 et x3 la fonction économique est z.
1 0 0 0,6667 -0,333 0 0 160
0 1 1 -0,333 0,6667 0 0 160
0 0 1 -0,167 -0,167 0,5 0 80
0 0 0 -3,333 -3,333 0 -1 -3200

Chapitre X : programmation linéaire, page 11

Exercice 5
Voici la matrice d’un problème à 3 variables de décision. Décrivez la prochaine étape qui permettrait de
poursuivre le problème jusqu’à trouver la solution optimale si les variables sont x1 x2 et x3 la fonction
économique est z.

2 1 1 1 0 0 0 480
0 3 3 -1 2 0 0 480
0 1 5 -1 0 2 0 480
0 5 5 -5 0 0 -1 -2400

Chapitre X : programmation linéaire, page 12

Exercice complet sans contexte
Particularité : tous les coefficients des variables de décision sont égaux.

2 x1  x2  x3  480
 x  2 x  2 x  480
 1
z  10 x1  10 x2  10 x3 avec 
2 3

 x1  x2  3x3  480
 x1  0, x2  0, x3  0

Réponse : La solution optimale est atteinte à (160; 160; 0). Le profit est alors de 3 200$.
Remarque: en faisant un choix de pivot différent, on peut trouver le même profit à (160; 80; 80) et
(160; 96; 64).

Chapitre X : programmation linéaire, page 13

EXERCICES SUR LA MÉTHODE DU SIMPLEXE (sans contextes)

(extrait des notes d’Alain Tranchida)

 x1  4 x2  12
2 x  x  10
 1 2
1. Maximiser z  3x1  3x2 , sujette aux contraintes suivantes : 
 x1  0
 x2  0
a) Par la méthode graphique
b) Par la méthode du simplexe.

Résoudre les problèmes suivants par la méthode du simplexe :

 x1  x2  13
5 x  2 x  50
 1 2

2. Maximiser z  5 x1  8 x2 , sujette aux contraintes suivantes : 4 x1  5 x2  60

x  0
 1
 x2  0
2 x1  x2  22
 x  2 x  20
 1 2

3. Maximiser z  300 x1  200 x2 , sujette aux contraintes :  x1  x2  12

x  0
 1
 x2  0
 x1  4 x2  24
3x  x  21
 1 2
4. Maximiser z  24 x1  60 x2 , sujette aux contraintes suivantes :  x1  x2  9
x  0
 1
 x2  0
3x1  3x2  2 x3  240
 x  x  2 x  120
 1 2
z  2 x1  1,5x2  x3 , sujette aux contraintes : 
3
5. Maximiser
3x1  x2  x3  120
 x1 , x2 et x3  0

RÉPONSES

1. Z=18 à (4,2)
2. Z=96 à (0,12)
3. Z=3400 à (10,2)
4. Z=396 à (4,5)
5. Z=130 à (20,60,0)

Chapitre X : programmation linéaire, page 14

 Liste d’exercices conseillés
Chapitre X Programmation linéaire et simplexe

Les exercices surlignés sont une présélection pour faire un survol complet de la matière en peu
d’exercices. Je vous recommande de faire la présélection d’abord, puis de compléter les autres exercices
ensuite.

Exercices tirés de :
AMYOTTE, Luc. Introduction à l’algèbre linéaire et à ses applications, Quatrième édition, ERPI,
2015. 540 p.

Chapitre Exercices
Algorithme du simplexe (sans contexte)
Voir p.14 des notes de cours # 1, 2, 3, 4, 5

Modélisation : poser le problème (programme linéaire)

Livre p.451 #1 a), 4, 5, 8 et 10.
X
Résolution avec la méthode graphique
Livre p.452 #11 a)

Résolution avec la méthode du simplexe

Livre p.452 #21, 22.

Chapitre X : programmation linéaire, page 15