Cours :Recherche Opérationnelle

Khalid BOUIHAT

Université Hassan 1er Settat

Ecole Nationale des Sciences Appliquées- Berrechid
Filière :DUT GLT
Semestre :S3

12 novembre 2018

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 1 / 93

Plan

1 Rappel sur le calcul matriciel-Matrices

Généralités sur les matrices
Opérations sur les matrices

2 Forme matricielle d’un système linéaire

3 Introduction à la recherche opérationnelle

4 Définitions générales

5 Modélisation

6 Résolution via le solveur d’Excel

7 Algorithme du simplexe : Préliminaires

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 2 / 93

 Rappel sur le calcul matriciel-Matrices Généralités sur les matrices

NOTION DE MATRICE
On appelle matrice de dimension m × n un tableau de nombres
comportant m lignes et n colonnes. Ces nombres sont appelés
coefficients
 de la matrice. 
a11 a12 · · · a1n
 a21 a22 · · · a2n 
A= .
 
.. .. .. 
 .. . . . 
am1 am2 · · · amn

Notations :
a11 , a12 , a13 , ...., amn désignent les coefficients de la matrice.
Le coefficient de la i ème ligne et de la j ème colonne est noté a ij
La matrice A se note aussi (aij )1≤i≤m,1≤j≤n Autrement dit, est la
matrice des coefficients aij

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 3 / 93

 Rappel sur le calcul matriciel-Matrices Généralités sur les matrices

 
1 3 4
ExempleSi A =  −2 5 2 , alors a12 désigne le coefficient de la
0 1 3
1ère ligne et de la 2ème colonne avec a12 = 3 et a21 désigne le
coefficient de la 2ème ligne et de la 1ère colonne avec a = −2. La 21
matrice A se compose de 3 lignes et de 3 colonnes donc est une
matrice de dimension 3 × 3.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 4 / 93

 Rappel sur le calcul matriciel-Matrices Généralités sur les matrices

Matrices Particulières
Une matrice comportant une seule ligne s’appelle un
vecteur-ligne. Un vecteur-ligne a donc pour dimension 1 × n. Dans
ce cas, m = 1 .
Une matrice comportant une seule colonne s’appelle un
vecteur-colonne. Un vecteur-colonne a donc pour dimension
m × 1. Dans ce cas, n = 1.
Une matrice comportant autant de lignes que de colonnes
s’appelle une matrice carrée. Une matrice carrée a donc pour
dimension n × n. Dans ce cas m = n.
On appelle matrice diagonale une matrice carrée dont tous les
coefficients sont nuls, exceptés ceux de la diagonale issue du coin
en haut à gauche. Autrement dit, A est une matrice diagonale
si :aij = k si i = j et aij = 0 si i 6= j

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 5 / 93

 Rappel sur le calcul matriciel-Matrices Généralités sur les matrices

On appelle matrice identité (ou matrice unité) une matrice carrée

dont tous les coefficients de la diagonale issue du coin en haut à
gauche sont égaux à 1, et dont tous les autres coefficients sont
nuls. Autrement dit, A est une matrice identité si : aij = 1 si i = j
et aij = 0 si i 6= j . On note In la matrice identité d’ordre n.
On appelle matrice nulle toute matrice dont les coefficients sont
tous nuls. Dans ce cas aij = 0
Exemple


A= 1 3 4
est un vecteur-ligne de dimension 1 × 3
 
1
B =  −2 
0
est un vecteur-colonne de dimension 3 × 1

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 6 / 93

 Rappel sur le calcul matriciel-Matrices Généralités sur les matrices

 
1 3 4
C =  −2 5 2 
0 1 3
est une matrice carrée de dimension 3 × 3
 
1 0 0
D= 0 5 0 
0 0 3
est une matrice diagonale
 
1 0 0
I3 =  0 1 0 
0 0 1
est la matrice identité d’ordre 3, que l’on note I3
 
0 0 0
O= 0 0 0 
0 0 0
est une matrice nulle.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 7 / 93

 Rappel sur le calcul matriciel-Matrices Généralités sur les matrices

Définition
Deux matrices sont égales si elles ont même dimension et si les
coefficients situés à la même place sont égaux. Autrement dit, deux
matrices A et B sont égales si A et B ont toutes deux pour dimension
m × n et si aij = bij (pour toute ligne et toute colonne ).

Exemple
   
1 4 a b
A= et B =
0 3 c d
sont deux matrices carrées de même dimension 2 × 2 ; elles ne
sont
 égales que si le système suivant est vérifié

 a=1
b=4


 c=0
d =3


Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 8 / 93

 Rappel sur le calcul matriciel-Matrices Généralités sur les matrices

Définition
On appelle matrice transposée de la matrice A la matrice obtenue en
permutant les lignes et les colonnes de A. Ainsi, à tout coefficient aij de
A la matrice correspond le coefficient aji de la matrice transposée AT .

Exemple
 
1 4
La matrice A =  6 5  a pour matrice transposée la matrice
0 3
 
1 6 0
AT =
4 5 3

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 9 / 93

 Rappel sur le calcul matriciel-Matrices Opérations sur les matrices

Définition de la somme de matrices

On appelle somme de deux matrices (de même dimension m × n ) la
matrice obtenue enadditionnant les coefficients
 qui ont la même
a11 a12 · · · a1n
 a21 a22 · · · a2n 
position. A + B =  . ..  +
 
. .. . .
 . . . . 
am1 am2 · · · amn
 
b11 b12 · · · b1n
 b21 b22 · · · b2n 
 
 .. .. .. .. 
 . . . . 
b bm2 · · · bmn
m1 
a11 + b11 a12 + b12 ··· a1n + b1n
 a21 + b21 a22 + b22 ··· a2n + b2n 
=
 
.. .. .. .. 
 . . . . 
am1 + bm1 am2 + bm2 · · · amn + bmn

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 10 / 93

 Rappel sur le calcul matriciel-Matrices Opérations sur les matrices

Remarque importante : On ne peut pas additionner deux matrices de

dimensions différentes.
Proposition
Les propriétés habituelles de l’addition valent pour la somme de
matrices :
L’associativité : (A + B) + C = A + (B + C) = A + B + C
La commutativité : A + B = B + A

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 11 / 93

 Rappel sur le calcul matriciel-Matrices Opérations sur les matrices

Définition de la produit de deux matrices

Soit A une matrice de dimension n × p et soit B une matrice de
dimension p × m On appelle le Produit A × B la matrice C de
dimension n × m où chaque coefficient cij est le produit de la i ème
ligne de A et de la j ème colonne de B.
Autrement dit : Si on pose A = (aij ) avec 1 ≤ i ≤ n et 1 ≤ j ≤ p et
B = (bij ) avec 1 ≤ i ≤ p et 1 ≤ j ≤ m alors C = (cij ) avec 1 ≤ i ≤ n et
1 ≤ j ≤ m.
p
X
cij = aik bkj
k =1

Remarque importante : La matrice A × B n’est définie que si le nombre

de colonnes de A est égal au nombre de lignes de B.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 12 / 93

 Rappel sur le calcul matriciel-Matrices Opérations sur les matrices

Exemple  
 7 8 
1 2 −3
A×B = ×  9 −1  =
4 −5 6
3 5
 
1 × 7 + 2 × 9−3 × 3 1 × 8−1 × 2−3 × 5
4 × 7−5 × 9 + 6 × 3 4 × 8 + 5 × 1 + 6 × 5

Propriétés :
La multiplication de matrices est associative :
(A × B) × C = A × (B × C) = A × B × C
La multiplication de matrices n’est pas commutative :
A × B 6= B × A
La multiplication des matrices est distributive par rapport à
l’addition A × (B + C) = A × B + A × C

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 13 / 93

 Rappel sur le calcul matriciel-Matrices Opérations sur les matrices

Matrice inverse
Soit une matrice carrée A d’ordre n. La Matrice inverse de A, notée
A−1 , est définie, quand elle existe, par A × A−1 = In . Si une telle
matrice existe, on dit alors que A est inversible.

Déterminant


a b
Soit la matrice A = On appelle Déterminant de la matrice A,
c d
noté det(A) , le réel ad − bc.

Remarque importante : La matrice A est inversible si et seulement si

det(A) 6= 0

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 14 / 93

 Forme matricielle d’un système linéaire

Système d’équations linéaires

Un système d’équations linéaires est un ensemble d’équations portant

sur les mêmes inconnues.
En général, un système de m équations linéaires à n inconnues peut
être écrit sous la forme suivante :


 a11 x1 + a12 x2 + · · · + a1n xn = b1
 a21 x1 + a22 x2 + · · · + a2n xn = b2

(S) .. .. . . .


 . + . + . + ..
am1 x1 + am2 x2 + · · · + amn xn = bm


où x1 , x2 , ..., xn sont les inconnues.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 15 / 93

 Forme matricielle d’un système linéaire

Forme matricielle d’un système linéaire

Un système d’équations linéaires peut aussi s’écrire sous la forme

matricielle
Ax = b
où A est une matrice de taille m × n, x est un vecteur de taille n et b
est un
vecteur de taille m.     
a11 a12 · · · a1n x1 b1
 a21 a22 · · · a2n   x2   b2 
A= . , x =  .  et b =  . 
     
. .
. . . .
.  . .
 . . . .   .   . 
am1 am2 · · · amn xn bm

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 16 / 93

 Forme matricielle d’un système linéaire

Cas possibles pour un système linéaire

Soit le système linéaires

Ax = b
avec :
x vecteur contenant les n variables réelles rechérchées.
A matrice de taille m × n contenant des coefficients réels.
b vecteur contenant m réels.
Seulement 3 cas sont possibles pour ce système linéaire :
Le système n’a pas de solution.
Le système a une solution unique.
Le système a une infinité de solutions.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 17 / 93

 Introduction à la recherche opérationnelle

Introduction à la recherche opérationnelle

Période : 2eme guerre mondiale.
Responsable : armée britannique
Problèmes posés : implantation optimale de radars de
surveillance , le management des
bombardements.
anti sous-marins.
opérations de miniers · · ·
RO = Application des mathématiques et des méthodes
scientifiques aux opérations militaires.
RO = Approche scientifique à la prise des décisions, qui cherche
à déterminer comment concevoir et faire fonctionner un système
d’une façon optimale.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 18 / 93

 Introduction à la recherche opérationnelle

Techniques de la RO
1 La programmation mathématique :
Programmation linéaire (objet du cours).
Programmation quadratique.
Programmation en nombres entiers.
Programmation dynamique.
2 Théorie des graphes :
Optimisation de chemins.
Ordonnancement de la production.
Allocation de ressources

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 19 / 93

 Introduction à la recherche opérationnelle

Champs d’application de la RO
Industrie.
Gouvernement.
Agences.
Hôpitaux.
Institutions d’éducation · · ·
Méthodologie de la RO
1 Identification du problème.
2 Collecte des données.
3 Modélisation (Formulation mathématique).
4 Vérification du modèle.
5 Recherche des solutions.
6 Présentation des solutions.
7 Implémentation et recommandations.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 20 / 93

 Définitions générales

Programmation linéaire

Programmation linéaire
Définition
Un programme linéaire est un problème d’optimisation avec
contraintes où la fonction à optimiser est linéaire et où les contraintes
sont linéaires.
Remarque
En générale les problèmes de programation linéaires est défini
comme étant un problème de maximisation ou de minimisation
d’une fonction sous ou sans contraintes. Les contraintes peuvent
être sous forme des inégalités ou des égalités linéaires.
Les exemples habituels d’optimisation sont la recherche d’un
bénéfice maximal ou d’un coût minimal.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 21 / 93

 Définitions générales

Formulation mathématique d’un programme linéaire


 X n
max Z = Cj Xj ,





j=1
(P.L) n
 X
aij Xj ≤ bi ∀Xj et ∀i = 1, · · ·, m





j=1

Ou sous la forme :

 X n
min Z = Cj Xj ,





j=1
(P.L) n
 X
aij Xj ≤ bi ∀Xj et ∀i = 1, · · ·, m





j=1

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 22 / 93

 Définitions générales

Exemple 1, de programme linéaire :



 max Z = 5x1 + 3x2 ,
x1 + 2x2 ≥ 6



(P.L) x1 − x2 = 4
x1 ≥ 0




x2 ≥ 0


Exemple 2, de P.L :


 max Z = 8x1 − 7x2 ,
3x1 + 4x2 ≤ 2



(P.L) x1 + 2x2 ≥ 9
x1 ≥ 0




x2 ≥ 0


Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 23 / 93

 Définitions générales

Exemple 2, de P.L :

min Z = −3x1 + x2 − 5x3 + 7x4 ,







 −x1 + 2x2 + 6x3 − 3x4 ≥ 15



 x1 + 5x2 − 3x3 − 2x4 = 27
5x1 + 3x2 + 7x3 ≤ 21

(P.L)

 x1 ≥ 0
x2 ∈ R




x3 ≤ 0




x4 ∈ R


Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 24 / 93

 Définitions générales

Solution réalisable et solution optimale

Une solution est dite réalisable pour un PL donné s’elle satisfait
toutes les contraintes de ce PL.
Une solution est dite optimale pour un PL donné de maximisation
(resp. minimisation) s’elle est réalisable et s’elle maximise (resp.
minimise) la fonction objectif de ce PL.
Exemples concernant la réalisabilité d’un PL :
La solution x1 = 5, x2 = 1 est une solution réalisable pour le PL de
l’exemple 1.
Le PL de l’exemple 2 n’admet aucune solution réalisable. Ce PL
est dit alors PL irréalisable (non réalisable).
La solution x1 = 1, x2 = 8, x3 = −2, x4 = −10 est une solution
réalisable pour le PL de l’exemple 3.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 25 / 93

 Modélisation

Exemple 1 : Fabrique de ceintures

Une usine de ceinture en fabrique de 2 sortes : luxe et standard

Chaque type demande 1m2 de cuir
Une ceinture standard demande 1h de travail
Une ceinture de luxe 2h
Chaque semaine, on dispose de 40m2 de cuir et de 60h de travail.
Chaque ceinture standard rapport 3 Dirhams
Chaque ceinture de luxe 4 Dirhams.
Maximiser le profit.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 26 / 93

 Modélisation

Formulation du programme linéaire

1 Variables de décision :
Elles doivent complètement décrire les décisions à prendre.
2 Fonction objectif :
Dans n’importe quel programme linéaire, le responsable de
décision veut maximiser (en général, le revenu ou profit) ou
minimiser (en général le coût) une fonction des variables de
décisions. Cette fonction est appelée fonction objectif.
L’objectif de l’usine
L’objectif de l’usine est de déterminer le programme de production qui
maximisera son profit (Z = profit).

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 27 / 93

 Modélisation

x1 = nombre de ceintures de luxe produites par semaine

x2 = nombre de ceintures standard produites par semaine
Modèle complet :


 max Z = 4x1 + 3x2 ,
x1 + x2 ≤ 40 contrainte sur le cuir



(P.L) 2x1 + x2 ≤ 60 contrainte sur le travail
x1 ≥ 0 contrainte de signe




x2 ≥ 0 contrainte de signe


Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 28 / 93

 Modélisation

Exemple 2 : Produit deux types de ciments

Une usine produit deux types de ciments C1 et C2 , rapportant

respectivement 400Dh et 500Dh par tonne. Une tonne du ciment C1
nécessite 40min de calcination dans un four à chaux et 20min de
broyage. Une tonne du ciment C2 nécessite 30min de calcination dans
un four à chaux et 30min de broyage. Le four et l’atelier de broyage
sont disponibles 6h et 8h par jour.
Combien de ciment de chaque type peut-on produire par jour pour
maximiser le bénéfice ?

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 29 / 93

 Modélisation

Formulation du programme linéaire

L’objectif de l’usine
L’objectif de l’usine est de déterminer le programme de production qui
maximisera le bénéfice ?
Q(C1 ) = x1 : quantité de C1 .
Q(C2 ) = x2 : quantité de C2

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 30 / 93

 Modélisation

Modèle complet :


 max Z = 400x1 + 500x2 ,
40x1 + 30x2 ≤ 360 contrainte sur la disponibilité de four



(P.L) 20x1 + 30x2 ≤ 480 contrainte sur disponibilité de l’atelier
x1 ≥ 0 contrainte sur la positivité




x2 ≥ 0 contrainte sur la positivité


Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 31 / 93

 Modélisation

Exemple 3 : Problème du régime

On veut suivre un régime qui impose de manger un élément des 4

groupes de base : chocolat, crème glacée, soda et gâteau.
Une barre de chocolat coûte 50 Dh, une part de crème glacée 20
Dh, chaque bouteille de soda 30Dh et une part de gâteau 80 Dh.
Chaque jour je dois ingérer 500 calories, 60g de chocolat, 100g
de sucre et 80g de lipides.
Le contenu nutritionnel de chaque type de nourriture est donné
ainsi
Elément Cal.(g) Choc.(g) Suc.(g) Lip.(g)
barre chocolat 400 30 20 20
crème glacée 200 20 20 40
cola 150 0 40 10
gâteau 500 0 40 50

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 32 / 93

 Modélisation

Formulation

On veut minimizer le coût du régime.

Combien de variables ?
Exprimer la fonction objectif
Exprimer les contraintes
Mettre sous forme standard

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 33 / 93

 Modélisation

Formulation-régime

Objectif = min z = 50x1 + 20x2 + 30x3 + 80x4

Total calories = 400x1 + 200x2 + 150x3 + 500x4 ≥ 500
Total chocolat = 30x1 + 20x2 ≥ 60
Total sucres = 20x1 + 20x2 + 40x3 + 40x4 ≥ 100
Total lipides= 20x1 + 40x2 + 10x3 + 50x4 ≥ 80
Finalement, tous les xi sont positifs.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 34 / 93

 Modélisation

Exemple 4 : Fabrication d’appareils électroménagers

L’entreprise GENCO fabrique divers modèles d’appareils

électroménagers. Suite à une réunion départementale de divers chefs
de services de l’entreprise, il a été convenu d’examiner la possibilité
de modifier le programme actuel de fabrication des
grille-painspermettant de produire deux modèles : le modèle
électronique (QL-500) et le modèle grille-pain/four (QL-700X).
L’assemblage se fait essentiellement en deux phases et, par la suite,
une vérification (contrôle exhaustif) est effectuée sur toutes les unités.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 35 / 93

 Modélisation

Le tableau suivant donne l’information concernant le nombre d’heures

exigées pour fabriquer chaque modèle ainsi que les disponibilités en
heures de chaque département.
[Link] : Nombres d’heures requises.
[Link] : Heures disponibles.

[Link] [Link]
Départements QL-500 QL-700X h. dis
Assemblage (phase 1) 3 4 4200
Assemblage (phase 2) 1 3 2250
Vérification/Empaquetage 2 2 2600

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 36 / 93

 Modélisation

Étant donné la situation du marché, l’entreprise ne veut pas

fabriquer plus de 1100 unités du modèle électronique QL-500.
La contribution au bénéfice du modèle QL-500 est de 66 Dh
l’unité alors que celle du modèle QL-700X est de 84 Dh.
On veut déterminer le programme optimal de fabrication à mettre
en oeuvre c’est-à-dire celui qui maximiserait les bénéfices.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 37 / 93

 Modélisation

Variables :
x1 : le nombre d’unites a fabriquer du modele QL-500.
x2 : le nombre d’unites a fabriquer du modele QL-700X.
Fonction objectif :
MaxZ = 66x1 + 84x2
Contraintes :
Assemblage/Phase 1 : 3x1 + 4x2 ≤ 4200 (C1)
Assemblage/Phase 2 :x1 + 3x2 ≤ 2250 (C2)
Verification/Empaquetage : 2x1 + 2x2 ≤ 2600 (C3)
Quantite maximale du modele QL-500 :x1 ≤ 1100 (C4)
Types des variables : x1 et x2 entiers positifs.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 38 / 93

 Résolution via le solveur d’Excel

Nous allons résoudre le PL correspondant à l’exemple 4 en

utilisant l’outil Solveur du logiciel MS Excel.
Il y a trois parties principales à fournir au solveur d’Excel :
1 La plage des variables de décision.
2 Les expressions des contraintes et leurs seconds membres.
3 La référence de la cellule qui représente la fonction objectif
maximiser/minimiser

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 39 / 93

 Résolution via le solveur d’Excel

Les cellules B2 et C2 seront les variables du problème (x1 etx2 ).

Chacun des coefficients reliés aux variables pour chaque
contrainte est inscrit de B5 : C8.
La quantité des ressources est indiquée et le sens de la
contrainte. Ce dernier élément est facultatif, il aide seulement
comme aide-mémoire au problème.
Il faut indiquer le bénéfice/unité pour chaque variable (B11 : C11)
(Figure 1).

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 40 / 93

 Résolution via le solveur d’Excel

Figure 1 :

F IGURE: Cellules des variables du problème.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 41 / 93

 Résolution via le solveur d’Excel

Premiere contrainte : 3x1 + 4x2 ≤ 4200. Vous devez calculer

l’éxpression de la partie gauche de l’équation avant d’activer le
solveur. Exemple dans la cellule D5 la formule = B2*B5 + C2*C5
est inscrite, equivalente à 3x1 + 4x2 (Figure 2).
Copiez cette formule pour les autres contraintes.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 42 / 93

 Résolution via le solveur d’Excel

Figure 2 :

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 43 / 93

 Résolution via le solveur d’Excel

La formule =B11*B2+C11*C2 est inscrite dans la cellule F12.

C’est cette cellule qu’on maximisera car elle correspond à la
fonction objectif 66x1 + 84x2 (Figure 3).

Figure 3 :

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 44 / 93

 Résolution via le solveur d’Excel

Si le solveur est déjà installé, lancez-le. Sinon, procédez à son

installation, puis lancez-le.
Entrez les paramètres du solveur (Figure 4).
Figure 4 :

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 45 / 93

 Résolution via le solveur d’Excel

Cellule cible à définir : (Exemple F12) Ceci correspond à l’adresse

de la fonction à optimiser.
Egale à : Cochez le type d’optimisation voulu. Le Max est coché
car dans cet exemple nous voulons maximiser le bénéfice total.
Cellules variables : Sélectionnez l’endroit dans le tableur où les
variables se trouvent. Il ne doit pas avoir de cellules vides entre
les variables. Les cellules B2 :C2 représentent les variables de
notre problème, c’est-à-dire celles qu’on désire déterminer.
Contraintes : Vous devez spécifier chacune des contraintes de
votre problème.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 46 / 93

 Résolution via le solveur d’Excel

Ensuite, ajoutez les contraintes séparément (Exemple pour la

dernière contrainte x1 <= 1100) :
Le membre gauche de l’équation : c’est-à-dire l’adresse de la
cellule contenant la formule B2*B8+C2*C8 donc D8.
Le sens de l’équation : <=
Le membre gauche de l’équation : c’est-à-dire le nombre de
ressources 1100 ou son adresse F8 (Figure 5).
Procédez de la même manière pour les autres contraintes.
Lorsque vous avez terminé d’insérer toutes les contraintes,
validez par OK.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 47 / 93

 Résolution via le solveur d’Excel

Figure 5 :

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 48 / 93

 Résolution via le solveur d’Excel

Dans l’exemple traité, x1 et x2 doivent être des entiers afin de ne

pas produire des fractions d’unités :
Cliquez sur "Ajouter".
Sélectionnez toutes vos variables (Exemple B2 :C2).
Choisissez "ent".
Pour les contraintes de positivite (non-negativite) x1 ≥ 0 et x2 ≥ 0,
vous pouvez eventuellement les communiquer au solveur en
procedant de la facon suivante (qui n’est pas la seule !) :
Cliquez sur "Ajouter".
Sélectionnez toutes vos variables (ExempleB2 :C2).
Inscrivez le sens >=.
Tapez 0 dans la rubrique "Contrainte".
Étant donné que nous voulons résoudre un programme linéaire, il
est possible de le spécifier au solveur afin qu’il utilise la méthode
adéquate pour résoudre le problème. Cliquez sur "options" (voir
Figure 4), cochez "Modèle supposé linéaire" (Figure 6) et cliquez
sur "OK".
Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 49 / 93
 Résolution via le solveur d’Excel

Figure 6 :

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 50 / 93

 Résolution via le solveur d’Excel

Cliquez sur "Résoudre" (voir Figure 4).

Le solveur a trouvé la solution optimale selon les contraintes
spécifiées (Figure 7).
Le solveur vous demande si vous voulez garder cette solution à
l’écran ou revenir à celle de départ. Choisissez "Garder la solution
du solveur" (Figure 7).
Appuyez sur "OK".

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 51 / 93

 Résolution via le solveur d’Excel

Figure 7 :

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 52 / 93

 Algorithme du simplexe : Préliminaires

Introduction
L’algorithme du simplexe est l’une des méthodes les plus
anciennes (Dantzig, 1947), et la plus utilisée jusqu’à nos jours,
pour résoudre même des programmes linéaires de grande taille
avec des milliers de variables et des milliers de contraintes.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 53 / 93

 Algorithme du simplexe : Préliminaires

Forme standard (Définition) Un PL peut avoir des contraintes d’égalite

(=) et des contraintes d’inégalité ( ≤ et ≥ ).
Avant l’application du simplexe, le PL doit être converti en un PL
équivalent où :
toutes les contraintes sont des égalités,
toutes les variables sont positives,
le second membre est positif,
la fonction objectif est à maximiser.
Un tel PL est dit sous forme standard.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 54 / 93

 Algorithme du simplexe : Préliminaires

Forme standard (Définition)

En général, la mise en forme standard d’un PL donne :


 max Z = c1 x1 + c2 x2 + · · · + cn xn ,
sous contrainte




 a11 x1 + a12 x2 + · · · + a1n xn = b1

(P.L) a21 x1 + a22 x2 + · · · + a2n xn = b2


 ..
.




am1 x1 + am2 x2 + · · · + amn xn = bm


Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 55 / 93

 Algorithme du simplexe : Préliminaires

Forme standard (Règles)

Minimiser f (x) ⇔ Maximiser (−f (x)) et multiplier le resultat par
−1.
ax ≤ b ⇔ ax + s = b avec s ≥ 0 (ajouter une variable d’écart
s ≥ 0).
ax ≥ b ⇔ ax − s = b avec s ≥ 0 (retrancher une variable d’écart
s ≥ 0).
x ≤ 0 ⇔ x = −y avec y ≥ 0.
0 00 0 00
x ∈ R ⇔ x = x − x avec x ≥ 0 et x ≥ 0.
Si une équation contient un second membre négatif, on la
multiplie par -1.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 56 / 93

 Algorithme du simplexe : Préliminaires

Forme standard (Exemples)

Exemple 1 :

 
 max Z = 3x1 + 7x2 ,

 max Z = 3x1 + 7x2 , 


 2x1 − 5x2 + x3 = 6
2x1 − 5x2 ≤ 6 4x1 + 3x2 + x4 = 8

 

 
(P.L) 4x1 + 3x2 ≤ 8 ⇔ (F .S) x1 ≥ 0
x1 ≥ 0 x2 ≥ 0

 


 

x2 ≥ 0 x 3 ≥0
 



x4 ≥ 0


Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 57 / 93

 Algorithme du simplexe : Préliminaires

Exemple 2 :
max Z = 2y1 − 3y2 ,

 


 min Z = −2x1 − 3x2 , 


 y1 − 4y2 + y3 = 4



 x1 + 4x2 ≤ 4 


 5y 1 + 6y2 = 9
5x1 − 6x2 = 9 −9y1 + 2y2 + y4 =
 
(P.L) ⇔ (F .S)

 9x1 + 2x2 ≥ −3 
 y 1 ≥0
x1 ≥ 0 y2 ≥ 0

 


 

x2 ≤ 0 y 3 ≥0
 



y4 ≥ 0

Posons y1 = x1 et y2 = −x2

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 58 / 93

 Algorithme du simplexe : Préliminaires

Exemple 3 :


 max Z = 3x1 + 2x2 − 2x3 ,



 −2x1 + x2 + 3x3 = 10
x1 + 4x2 − x3 ≥ 15

(P.L)

 9x1 + 2x2 ≥ −3
x2 ≥ 20




x1 ≤ 0; x2 ≥ 0; x3 ∈ R


Posonons y1 = −x1 ; y2 = x2 et x3 = y3 − y4
Forme standard :


 max Z = −3y1 + 2y2 − 2y3 + 2y4 ,



 2y1 + y2 + 3y3 − 3y4 = 10
−y1 + 4y2 − y3 + y4 − y5 = 15

(F .S)

 9y1 − 2y2 + y6 = 3
y2 − y7 = 20




yi ≥ 0 pour i = 1, 2, 3, 4, 5, 6, 7


Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 59 / 93

 Algorithme du simplexe : Préliminaires

Forme matricielle
On définit
 :     
a11 a12 ··· a1n x1 b1
 a21 a22 ··· a2n   x2   b2 
A= .  ,X =   ,b =  ,
     
.. .. .. .. ..
 .. . . .   .   . 
am1 am2 · · · amn xn bm
et  
c1
 c2 
C= .. .
 
 . 
cn

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 60 / 93

 Algorithme du simplexe : Préliminaires

On suppose que n ≥ m

 max Z = C t .X ,


(P.L) AX = b
xi ≥ 0 pouri = 1, 2, · · · , n


Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 61 / 93

 Algorithme du simplexe : Préliminaires

Variables de base et variables hors-base

On appelle Base une sous matrice régulière (inversible) de A.
Une solution de base est obtenue en posant n − m variables
égales à 0, et en résolvant pour les m variables restantes, qui sont
les variables de base (VB).
Les n − m variables à 0 sont les variables hors-base (VHB).
Des choix différents de VHB donnent lieu à des différentes
solutions de base.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 62 / 93

 Algorithme du simplexe : Préliminaires

Représentation

B base H hors base

XBt XHt
CBt CHt
m colonnes n − m colonnes

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 63 / 93

 Algorithme du simplexe : Préliminaires

Représentation matricielle
A = [B|H], X = [ XXHB ] et C t = [CBt |CHt ]
Ce qui donne :
Z = C t X = CBt XB + CHt XH
AX = b ⇒ BXB + HXH = b
Une solution de base est telle que

 XH = 0,
BXB = b
XB = B −1 b


Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 64 / 93

 Algorithme du simplexe : Préliminaires

Exemple :
Soit le système suivant :

x1 + x2 = 3,
−x1 + x3 = −1
Si on pose VHB = {x3 }, alors VB = {x1 , x2 }. On résout

x1 + x2 = 3,
−x1 = −1

Ce qui donne x1 = 1 et x2 = 2.
Certains choix de variables peuvent ne pas générer de solution de
base.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 65 / 93

 Algorithme du simplexe : Préliminaires

Solutions de base réalisables :

Proposition : Une solution de base est realisable (SBR) si
xB = B −1 b ≥ 0.
Exemple de SBR

 min Z = −x1 − 2x2 ,

x1 + x2 ≤ 4

(P.L)

 2x1 + x2 ≤ 5
x1 ≥ 0; x2 ≥ 0


Forme standard : 

 max Z = x1 + 2x2 ,
x1 + x2 + x3 = 4

(F .S)

 2x1 + x2 + x4 = 5
xi ≥ 0 pour i = 1, 2, 3, 4.


4 variables (n = 4) et 2 contraintes (m = 2).

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 66 / 93

 Algorithme du simplexe : Préliminaires

La matrice A de ce PL est :
 
1 2 1 0
A=
2 1 0 1

On peut essayer de constituer une base en utilisant l’ensemble

B = {1, 3}  
1 1
B = [A1 A3 ] =
2 0
et  
2 0
H = [A2 A4 ] =
1 1
 
x1
xB =
x3
et  
x2
xH =
x4
Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 67 / 93
 Algorithme du simplexe : Préliminaires

L’inverse de B existe, donc B correspond à une base

0 21
 
B −1 =
1 −12

La solution debase correspondante

   est5 donc :
1

0 4
xB = B −1 b = 2 = 2
1 −12
5 3
2
Cette solution est bien une SBR.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 68 / 93

 Algorithme du simplexe : Préliminaires

Exemples :
Déterminer les bases et les bases réalisables du système suivant :

 x1 + x2 + x3 = 6
x2 + x4 = 3
xi ≥ 0 pour i = 1, 2, 3, 4.


La matrice A de ce système est :

 
1 1 1 0
A=
0 1 0 1

On peut constituer une base en utilisant l’ensemble B = {1, 2}

 
1 1
B = [A1 A2 ] =
0 1

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 69 / 93

 Algorithme du simplexe : Préliminaires

La solution debase correspondante

   est donc
 :
1 −1 6 3
xB = B −1 b = =
0 1 3 3
Cette solution est bien une SBR (xB = B −1 b > 0).

On peut constituer une base en utilisant l’ensemble B = {2, 4}

 
1 0
B = [A2 A4 ] =
1 1

La solution debase correspondante

   est donc  :
1 0 6 6
xB = B −1 b = =
−1 1 3 −3
Cette solution n’est pas une sloution de base réalisable
(xB = B −1 b < 0).

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 70 / 93

 Algorithme du simplexe : Préliminaires

Conditions d’optimalité d’une SBR :

Théorème : Soit x une SBR de PL. Notons 4(x) = (c − cB B −1 A). Si
4(x) ≤ 0, alors x est optimal.
Définition d’un algorithme
Un algorithme est un ensemble de règles employées pour obtenir des
résultats à partir de données spécifiques, dans lequel chaque étape
est bien définie et peut être traduite sous forme d’un programme
informatique.
Simplexe
Le simplexe est un algorithme ou méthode de recherche qui garantit de
trouver un optimum d’un PL (s’il existe) en un nombre fini d’itérations.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 71 / 93

 Algorithme du simplexe : Préliminaires

Principe général :
Pour un problème de maximisation, l’algorithme du simplexe suit les
étapes générales suivantes :
1 Trouver une SBR pour le PL, appelée la SBR initiale.
2 Déterminer si la SBR courante est optimale (∆ ≤ 0). Sinon,
trouver une autre SBR qui possède une valeur z plus élevée.
3 Retourner au point (2) avec la nouvelle SBR comme SBR
courante.
La question est donc : Comment se déplacer ?

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 72 / 93

 Algorithme du simplexe : Préliminaires

   
x1 xm+1
 x1   xm+2 
Soient : xB =  , xH =  .
   
.. ..
 .   . 
xm xn
Notons
 par
 :      
a1j a1j b1j b1j
 a2j   a2j   b2j   b2j 
 = B −1  ..  et   = B −1  .
       
 .. .. ..
 .   .   .   . 
amj amj bmj bmj

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 73 / 93

 Algorithme du simplexe : Préliminaires

Tableau du simplexe :

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 74 / 93

 Algorithme du simplexe : Préliminaires

Pour se déplacer d’une SBR à une autre adjacente, une variable

hors base (variable entrante xe ) va prendre la place de l’une des
variables de base (xs ).
Questions :
1 Quelle est la variable entrante xe ?
2 Quelle est la variable sortante xs ?

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 75 / 93

 Algorithme du simplexe : Préliminaires

Choix de la variable entrante :

1er critere de Dantzig : nous indique le choix de la variable entrante.
Ce choix est basé sur la contribution eventuelle de xe à la fonction
objectif.
xe est telle que :∆e = {max ∆j , avec j = m + 1, · · ·, n; ∆j > 0}.
2eme critère de Dantzig : nous indique le choix de la variable sortante.
Ce choix est basé sur le fait que les variables de base doivent changer
tout en satisfaisant les contraintes du problème.
xs est telle que : abs,e
s
= min{ abi , avec j = m + 1, · · ·, n; ai,e > 0}.
i,e

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 76 / 93

 Algorithme du simplexe : Préliminaires

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 77 / 93

 Algorithme du simplexe : Préliminaires

On appelle :as,e : element pivot, Ligne s : ligne pivot, Colonne e :

colonne pivot
Maintenant on a donc une nouvelle base B 0 = 1, , e, , m avec xs
étant une nouvelle variable hors base.
Il faudra ainsi représenter le PL sous la forme d’un nouveau
tableau du simplexe associé à la nouvelle base B 0 .
La colonne de xe doit être transformée afin de conserver la
matrice d’identité (opération de pivotage) :
   
a1,e 0

 a2,e 
 0 
 
 ..   .. 

 .  ⇒  . .
  

 as,e 

 1 
 
 ..   .. 
 .   . 
am,e 0

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 78 / 93

 Algorithme du simplexe : Préliminaires

Résumé de l’algorithme du simplexe : :

1 Mettre le PL sous la forme standard.
2 Trouver une solution initiale de base (SBR initiale).
3 Ecrire le PL sous la forme canonique relative à la SBR initiale.
4 Itérations :
1 Si le critere d’arret est satisfait (∆ ≤ 0), donner le resultat final
(solution optimale) ; sinon aller à l’etape 4-2.
2 Déterminer la variable entrante (ou la colonne pivot) selon le 1er
critère de DANTZIG.
3 Déterminer la variable sortante (ou la ligne pivot) selon le 2eme
critère de DANTZIG.
4 Calculer le nouveau tableau en effectuant une opération de
pivotage. Retour à 4-1.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 79 / 93

 Algorithme du simplexe : Préliminaires

Exemple 1 :
Soitle PL suivant : :


 max Z = 15x1 + 6x2 ,
x1 + x2 ≤ 15



(P.L) 2x1 + x2 ≤ 20
x1 ≤ 8




x1 ≥ 0; x2 ≥ 0,


Appliquons l’algorithme du simplexe pour résoudre ce PL.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 80 / 93

 Algorithme du simplexe : Préliminaires

Mise en forme standard :



 max Z = 15x1 + 6x2 ,
x1 + x2 + x3 = 15



(F .S) 2x1 + x2 + x4 = 20
x1 + x5 = 8




xi ≥ 0 pour i = 1, 2, 3, 4, 5.


Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 81 / 93

 Algorithme du simplexe : Préliminaires

Tableau initial :

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 82 / 93

 Algorithme du simplexe : Préliminaires

Second tableau :

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 83 / 93

 Algorithme du simplexe : Préliminaires

Tableau final (optimal) :

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 84 / 93

 Algorithme du simplexe : Préliminaires

Exemple 2 :
Soitle PL suivant : :


 max Z = 30x + 50y ,
3x + 2y ≤ 1800



(P.L) x ≤ 400
y ≤ 600




x ≥ 0; y ≥ 0,


Appliquons l’algorithme du simplexe pour résoudre ce PL.

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 85 / 93

 Algorithme du simplexe : Préliminaires

Écrire le système sous forme standard :



 max Z = 30x + 50y ,
3x + 2y + e1 = 1800



(F .S) x + e2 = 400
y + e3 = 600




x ≥ 0 y ≥ 0 ei ≥ 0; pour i = 1, 2, 3.


Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 86 / 93

 Algorithme du simplexe : Préliminaires

Construire le premier tableau correspondant à la forme standard :

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 87 / 93

 Algorithme du simplexe : Préliminaires

Choisir les variables à introduire dans la base. Pour cela choisir le

coefficient le plus forte de la fonction économique :

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 88 / 93

 Algorithme du simplexe : Préliminaires

Choisir la variable à enlever de la base (rapport : second membre/

coefficient de la variable chosie ) retenir le plus faible :

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 89 / 93

 Algorithme du simplexe : Préliminaires

Encadrer le pivot :

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 90 / 93

 Algorithme du simplexe : Préliminaires

Calculer les valeurs des autres lignes :

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 91 / 93

 Algorithme du simplexe : Préliminaires

Choisir les variables à introduire dans la base. Pour cela choisir le

coefficient le plus forte de la fonction économique :

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 92 / 93

 Algorithme du simplexe : Préliminaires

Solution optimal :

Les coefficients de la fonction économique sont tous nuls ou négatifs,

la solution optimal donc est max z = 36000, les quantités produites est
x = 200 et y = 600

Khalid BOUIHAT (ESTB) Cours :Recherche Opérationnelle 12 novembre 2018 93 / 93