Chapitre 0.

Introduction générale
Chapitre 1. Programmation linéaire
Chapitre 2. Eléments de la théorie des graphes et applications

Recherche opérationnelle
Semestre 5 – Parcours Gestion

Pr. Benmlih K.

Université Sidi Mohamed Ben Abdellah – Fès

Faculté des Sciences Juridiques Economiques et Sociales
Département des Sciences de gestion

2023–2024

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale
Chapitre 1. Programmation linéaire
Chapitre 2. Eléments de la théorie des graphes et applications

Chapitre 0
Introduction générale

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale
Chapitre 1. Programmation linéaire
Chapitre 2. Eléments de la théorie des graphes et applications

Définition
La recherche opérationnelle (RO) est l’étude quantitative des
opérations d’une organisation complexe, à l’aide d’outils
scientifiques (mathématiques, probabilité & statistique,
informatique), de façon à permettre au gestionnaire de réaliser un
rendement optimal des ressources disponibles.

■ Les étapes d’étude d’un projet de la recherche opérationnelle se

présentent comme suit (dans l’ordre) :
1 D’abord, identifier les différentes données du problème réel
2 Ensuite, modéliser (formaliser) le problème
3 Puis, résoudre le modèle obtenu
4 Prendre une décision quant à la faisabilité du problème réel
5 Enfin, faire une étude postoptimale (sensibilité de la solution par
rapport aux données)
3

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale
Chapitre 1. Programmation linéaire
Chapitre 2. Eléments de la théorie des graphes et applications

■ La RO est un outil d’aide à la décision.

■ La modélisation d’un problème de nature quantitative est la

traduction de ses données dans un langage scientifique.
Elle permet, entre autres, l’expoitation des outils et résultats scien-
tifiques adéquats dans la résolution du problème à étudier.
Un modèle d’optimisation est défini par 3 composantes essen-
tielles :
Les variables (inconnues du problème, continues ou discrètes)
Les contraintes (limitations sur les variables)
La fonction objectif (à maximiser où à minimiser, selon la
nature du problème)

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale
Chapitre 1. Programmation linéaire
Chapitre 2. Eléments de la théorie des graphes et applications

■ Les modèles mathématiques d’optimisation sont, généralement,

de type :
Programme linéaire (PL)
Programme non linéaire (PNL)
Graphe
....

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale
Chapitre 1. Programmation linéaire
Chapitre 2. Eléments de la théorie des graphes et applications

■ Quoique d’origine militaire (placements de radars de surveillance,

gestion de convois militaires, · · · ), la recherche opérationnelle
connait un champs d’application très large, notamment :

En gestion d’entreprise : gestion de stocks, ordonnancement,

transport et logistique, · · ·
En gestion stratégique d’investissement
Dans la conception, la configuration et l’exploitation de
systèmes techniques complexes (réseaux de communication,
systèmes d’information)
Dans l’industrie pétrolière, la santé, · · ·

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale
Chapitre 1. Programmation linéaire
Chapitre 2. Eléments de la théorie des graphes et applications

PLAN DU COURS

1 Chapitre 0. Introduction générale

2 Chapitre 1. Programmation linéaire

1. Modélisation linéaire
2. Résolution graphique
3. Résolution par les simplexes
4. Dualité en programmation linéaire

3 Chapitre 2. Eléments de la théorie des graphes et applications

1. Notions de base sur les graphes
2. Problème de cheminement optimal
3. Problèmes d’ordonnancement

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale
Chapitre 1. Programmation linéaire
Chapitre 2. Eléments de la théorie des graphes et applications

Bibliographie
[1] La recherche opérationnelle, Y. Nobert, R. Ouelley & R.
Parent, Ed. gaëtan morion, 3ème édition, 2001.
[2] Mathématiques pour les sciences sociales, tome 5, F. Roure,
G. Fritz & A.-M. Charles, Presses Universitaires de France, 1973.
[3] Programmation linéaire par l’exemple, F. Droesbeke, M.
Hallin & CL. Lefevre, Ed. Ellipses, 1986.
[4] Les graphes par l’exemple, F. Droesbeke, M. Hallin & CL.
Lefevre, Ed. Ellipses, 2001.

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Chapitre 1
Programmation linéaire

1 Modélisation linéaire
2 Résolution graphique d’un programme linéaire
3 Résolution d’un PL par les simplexes
4 Dualité en programmation

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

1. Modélisation linéaire : Un exemple détaillé

Définition 1
On considère n variables x1 , x2 , · · · , xn . On appelle combinaison
linéaire de ces variables toute écriture de la forme
X
λ1 x1 + λ2 x2 + · · · + λn xn = λi xi , λi ∈ R.
i

Définition 2
Un programme linéaire (PL) est un problème d’optimisation qui
consiste à maximiser ou à minimiser une fonction linéaire dont les
variables sont soumises à un ensemble de contraintes exprimées
sous forme d’équations ou d’inéquations linéaires.

10

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Autrement dit, un (PL) sous sa forme canonique s’écrit :

Max / Min Z = c1 x1 + c2 x2 + · · · + cn xn
s.c. a11 x1 + a12 x2 + · · · + a1n xn ≤ (=; ≥) b1
a21 x1 + a22 x2 + · · · + a2n xn ≤ (=; ≥) b2
···
am1 x1 + am2 x2 + · · · + amn xn ≤ (=; ≥) bm
xi ≥ 0 i = 1, 2, · · · , n
avec n, m ∈ N∗ et bi ≥ 0 ∀i.
⋆ Les variables x1 , x2 , · · · , xn sont appelées les variables de déci-
sion du problème.
⋆ La fonction linéaire à optimiser est appelée la fonction-objectif
(ou fonction économique)

11

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Ecriture matricielle d’un PL

Max Z = CX
s.c. AX ≤ B
X≥ 0

 
x1
.  
où X =  .. 

 ; C = c1 · · · cn
xn
 
a11 a12 · · · a1n  
b1
a
 21 a22 · · · a2n 
 .
A=
 .. ..  et
..  B =  .. 

.
 . . . 
bp
ap1 ap2 · · · apn
12

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Les problèmes réels sont loin d’être linéaires.

Néanmoins, la compréhension des programmes linéaires aide à
l’étude de modèles plus complexes. En effet, des techniques per-
mettent d’approcher certains problèmes non linéaires par un en-
semble de programmes linéaires pour en déduire l’étude attendue.
(linéarisation)

13

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Exemple (modélisation)

Un menuisier fabrique et vend deux types d’armoires A et B.

Il utilise 3 heures à la fabrication des morceaux d’une armoire A
et 2 heures à l’assemblage de ces morceaux. Les morceaux d’une
armoire B prennent 2 heures à fabriquer et 1 heure à assembler.
Certaines contraintes font que la production quotidienne des ar-
moires B ne doit pas excéder celle des A par plus de 30 unités.
Le menuisier dispose à chaque jour de 120 heures pour l’atelier
de fabrication des morceaux et de 72 heures pour l’atelier de l’as-
semblage.
Enfin, une armoire A rapporte un profit de 500 DH et une B un
profit de 600 DH.
Ecrire la forme canonique du programme linéaire permettant à ce
menuisier de déterminer le nombre d’armoires A et B à fabriquer
quotidiennement pour réaliser un profit journalier maximal.
14

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Démarche de la modélisation.
⋆ Nature du problème : Détermination des nombres d’armoires A
et B à fabriquer quotidiennement pour réaliser un profit journalier
global maximal.
⋆ Sens d’optimisation : Maximisation du profit total.
⋆ Les variables d’action :
x1 : nombre d’armoires A à fabriquer par jour.
x2 : nombre d’armoires B à fabriquer par jour.
⋆ Fonction économique :
Profit global journalier Z = 500x1 + 600x2 (à maximiser)

15

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

⋆ Les contraintes :
- Implicites : xi ≥ 0 pour tout i = 1; 2 (En fait : xi ∈ N)
- Explicites :
Atelier de fabrication de morçeaux : 3x1 + 2x2 ≤ 120 ;
Atelier d’assemblage : 2x1 + x2 ≤ 72 ;
Contrainte technique : x2 − x1 ≤ 30.
⋆ Forme canonique du modèle :

Max Z = 500x1 + 600x2

s.c. xi ≥ 0, ∀i
3x1 + 2x2 ≤ 120
2x1 + x2 ≤ 72
−x1 + x2 ≤ 30

16

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Exercice

Le mobilier d’une bibliothèque universitaire doit être changé

pour contenir au moins 4 400 livres de petit format et 2 600
livres de grand format.
Un premier fournisseur propose des meubles de type A pou-
vant contenir 110 livres de petit format et 100 livres de
grand format pour un prix de 4 000 DH.
Un deuxième fournisseur propose des meubles de type B
pouvant contenir 220 livres de petit format et 100 livres de
grand format pour un prix de 6 000 DH.
Par ailleurs le responsable de la bibliothèque a pour
consigne de ne passer aucune commande supérieure à
96 000 DH chez un même fournisseur.
Ecrire le programme mathématique correspondant.
17

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

2. Résolution graphique

Une fois le programme linéaire est mis en forme, l’étape suivante

consite à résoudre le modèle.
Techniques mathématiques de résolution d’un Programme linéaire :
Méthode graphique (nombre de variables de décision n = 2 ou à la
limite n = 3).
Méthode de simplexe (n ≥ 2).

18

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

2.1 Quelques rappels dans le plan R2

Equation droite de R2 : ax + by + c = 0, où (a, b) ̸= (0, 0).
−c
Si b = 0 (et a ̸= 0) : droite verticale d’équation x = .
a
−a c
Si b ̸= 0 : droite d’équation y = x − , de pente (ou
b b
−a
coefficient directeur) le nombre .
b
Deux droites sont parallèles si elles ont la même pente.
Une inéquation linéaire de type ax + by + c ≤ 0 correspond à
un demi-plan limité par la droite d’équation ax + by + c = 0.
l’intersection, non vide, d’un nombre fini de demi-plans est un
polygone convexe.

19

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

2.2 Procédure de résolution graphique d’un PL

1 D’abord, représenter graphiquement les différentes contraintes
=⇒ polygone admissible (ou réalisable) ;
2 Ensuite, déterminer éventuellement quelle(s) solution(s)
admissible(s) optimise la fonction objectif.

Proposition
S’il y’a une solution unique qui optimise la fonction objectif
linéaire alors cette solution n’est autre qu’un sommet du
polygone admissible.
S’il y’a plus d’une solution alors au moins deux de ces
solutions correspondent à deux sommets adjacents du
polygone des solutions admissibles.

20

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Exemple Une entreprise fabrique et vend 2 types de produits

P1 et P2 à partir de 3 facteurs de production (les ressources)
notés F1 , F2 et F3 . La consommation de la production de P1 et
P2 en F1 , F2 et F3 est donnée par le tableau

F1 F2 F3 Profit unitaire
P1 1 1 2 400
P2 1 2 1 500
Ressources/jour 50 80 80

1. Déterminer un programme de fabrication maximisant le pro-

fit global journalier de cette entreprise, tout en respectant les
contraintes liées à ses resources.
2. Répondre à la même question en supposant que les deux pro-
duits générent un même profit unitaire de 400 DH, les quantités
de productions étant mesurées en variables continues.
21

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Réponse Notons par x1 et x2 les quantités respectives des pro-

duits P1 et P2 à fabriquer par jour.
1. On montre aisément que le problème peut être modélisé par :
Max Z = 400x1 + 500x2
s.c. x1 ; x2 ≥ 0
x1 + x2 ≤ 50
x1 + 2x2 ≤ 80
2x1 + x2 ≤ 80
• Le polygone admissible est déterminé par :
D1 : x1 + x2 = 50 → A1 (50, 0) ; B1 (0, 50)
D2 : x1 + 2x2 = 80 → A2 (80, 0) ; B2 (0, 40)
D3 : 2x1 + x2 = 80 → A3 (40, 0) ; B3 (0, 80)
Echelle : 1cm ≡ 10unités
22

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Figure – polygone admissible

23

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Donc le polygone admissible est la région convexe (O, A3 , I, J, B2 ).

O A3 I J B2
x1 0 40 30 20 0
x2 0 0 20 30 40
Z = 400x1 + 500x2 0 16000 22000 23000 20000

La valeur maximale de Z est de 23000. Elle est atteinte en un

unique sommet J(20, 30).

Conclusion :
Le profit journalier maximal est de 23000 DH.
Ce profit est uniquement réalisé par la fabrication journalière
(et la vente) de 20 unités du produit P1 et de 30 u de P2 .

24

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

2. Ici l’expression de la fonction objectif est : Z = 400x1 + 400x2 .

Les contraintes n’ont pas changé ⇒ le polygone admissible reste
inchangé également.
O A3 I J B2
x1 0 40 30 20 0
x2 0 0 20 30 40
Z = 400x1 + 400x2 0 16000 20000 20000 16000

La valeur maximale de Z est de 20000. Elle est atteinte en

deux points sommets adjacents I(30, 20) et J(20, 30).
Vu que la fonction objectif Z est linéaire, elle aura la même
valeur (de 20000) sur tout point du segment [I, J].
Puisque les variables de décision sont continues, l’ensemble
des solutions S est infini : S = [I, J].
(le segment [I, J] ⊂ droite D1 )
25

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Conclusion :

Lorsque le profit unitaire du produit P2 est aussi de 400 DH,

Le profit journalier maximal est de valeur 20000 DH.
Ce profit peut être réalisé par une infinité de programmes de
fabrication (x1 , 50 − x1 ), avec 20 ≤ x1 ≤ 30.
| {z }
=x2

Question : Que peut-on dire si de plus, les variables de décision

ne peuvent prendre que des valeurs entières ?
Réponse :
...........................
...........................

26

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

3. Résolution d’un PL par les simplexes

Méthode due au mathématicien George Dantzig (1947)
Procédé itératif permettant d’atteindre progressivement une
solution optimale (éventuellement) :
On choisit un sommet du polygone convexe admissible puis on
vérifie si ce sommet optimise la fonction objectif,
Sinon on se déplace vers un sommet adjacent au précédent, de
façon à améliorer le plus vite possible la valeur de la fonction
objectif,
Lorsqu’aucun sommet adjacent n’améliore la valeur de la
fonction objectif, cela veut dire qu’une solution optimale du
(PL) est atteinte.

27

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

3.1 Cas où l’origine O(0, 0, · · · , 0) est une solution admissible

On s’interesse dans un premier temps au cas où

x1 = x2 = · · · = xn = 0

est une solution qui vérifie toutes les contraintes du PL.

Cette solution constituera une solution de base initiale pour l’algo-
rithme du simplexe.
Reprenons l’exemple précédant

Max Z = 400x1 + 500x2

s.c. x1 ; x2 ≥ 0
x1 + x2 ≤ 50
x1 + 2x2 ≤ 80
2x1 + x2 ≤ 80
28

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

La résolution se fera en plusieurs étapes :

• Etape 1 : Ecriture du (PL) sous la forme "standard" (PL=)

Ceci consiste à transformer toutes les contraintes explicites de type
inéquations en équations linéaires en introduisant de nouvelles va-
riables additives positives, appelées variables d’écart.
Ces variables d’écart seront affectées du signe (+).
X X
aij xj ≤ bi (bi > 0) −→ aij xj + ei = bi , ∀i
j j

Dans toute la suite, les variables prises ou rendues nulles seront

appelées des variables hors base (VHB) et toutes les autres des
variables de base (VB).

29

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

• Etape 2 : Construction du tableau de simplexe initial.

Dans ce premier tableau (T1 ), on prendra
comme variables hors base : VHB := {x1 , x2 , . . .}
comme variables de base : VB := {e1 , e2 , . . .}.

La dernière ligne du tableau sera composée des nombres appelés

coûts marginaux, représentés par (cj − zj ).

Signalons que chaque tableau correspond graphiquement à un

sommet du polytope admissible.

30

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

• Etape 3 : Test d’optimalité.

Le tableau est considéré optimal lorsque
les coûts marginaux des V.H.B. sont tous négatifs (≤ 0) pour
un problème de maximisation,
les coûts marginaux des V.H.B. sont tous positifs (≥ 0) pour
un problème de minimisation.
Ceci veut dire qu’une solution optimale finie est atteinte.

Si le tableau n’est pas optimal, on passe à l’étape suivante du

changement de base.

31

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

• Etape 4 : Changement de base.

On choisit d’abord, parmi les V.H.B., celle qui remplacera une des
variables de base :
La variable entrante (dans la base) xe est celle parmi les VHB
qui correspond au :
plus grand coût marginal positif, pour un problème de
maximisation,
plus faible coût marginal négatif, pour un problème de
minimisation.
La variable sortrante (de la base) xs est celle du plus petit des
rapports de chaque terme de la colonne des valeurs par son
coefficient ≥ 0 correspondant dans la colonne de la variable
xe
(les coefficients < 0 ne sont pas pris en compte).

Une fois les deux variables, entrante et sortante, sont choisies, un

autre tableau sera construit par pivotage (étape suivante). 32

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Etape 5 : Pivotage.
Dans le nouveau tableau, la variable entrante xe prendra la place
de la variable sortante xs .
On appellera pivot du tableau le nombre se trouvant à l’intersec-
tion de la ligne de la variable xs et la colonne de xe .
On notera par Lp la ligne du pivot.
Les transformations que subira le tableau en cours sont celles de la
méthode de Pivot consistant à rendre
le pivot égal à 1
les autres nombres de la colonne du pivot égaux tous à 0.

33

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Rappel : D’après la méthode de Pivot, on peut rendre :

le pivot égal à 1, en multipliant la ligne du pivot par 1/p :
Lp −→ (1/p)Lp .

les autres termes de la colonne du pivot nuls, en appliquant la

transformation :
Lα −→ Lα − (α/p)Lp
où α est le terme à annuler.

Ensuite, on complète le tableau en calculant les nouveaux termes

de la ligne des zj puis la ligne des coûts marginaux.
Si le nouveau tableau n’est pas optimal, on répète le même preces-
sus à partir de l’étape 2,... etc

34

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Remarque
On peut également utiliser la méthode du Pivot sous une forme
simplifiée, appelée la règle du rectangle, qui consiste à :
rendre le pivot = 1, en multipliant la ligne du pivot par 1/p,
remplacer les autres termes de la colonne du pivot par 0,
appliquer ailleurs, et partout, la règle du rectangle suivante :

a c
bc
a −→ a′ = a −
p
b p

35

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Résolution de l’exemple précédent par les simplexes :

Forme standard (PL=)

Max Z = 400x1 + 500x2 +0e1 + 0e2 + 0e3

s.c. x1 ; x2 ; e1 ; e2 ; e3 ≥ 0
x1 + x2 +e1 = 50
x1 + 2x2 +e2 = 80
2x1 + x2 +e3 = 80

Le tableau initial (T1 ) est établi comme suit :

36

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

(T1 )

Cj
PP
PP 400 500 0 0 0 Valeurs Rapport
Base PPP P
coef. var. x1 x2 e1 e2 e3
0 e1 1 1 1 0 0 50 50

0 e2 1 2
0 1 0 80 40
0 e3 2 1 0 0 1 80 80
Zj 0 0 0 0 0 0
Cj − Zj 400 500 0 0 0 ——

Variables de base : e1 = 50 ; e2 = 80 et e3 = 80
Variables hors base : x1 = x2 = 0

Remarque : Ce tableau correspond au sommet Origine : x1 = x2 = 0.

37

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

✓ (T1 ) non optimal : C1 − Z1 = 400 > 0 (ou C2 − Z2 > 0)

(problème de maximisation).

✓ Changement de base :
Variable entrante : x2 car correspond au
max{400; 500} = 500
Variable sortante : e2 car correspond au min{ 50 80 80
1 ; 2 ; 1 } = 40,
Pivot et transformations : p = 2 ;
−1 p
Lp → 21 Lp ; L1 → 2 L + L1
Ce qui nous ramène à un sommet adjacent, correspondant au ta-
bleau suivant :

38

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

(T2 )

Cj
PP
PP 400 500 0 0 0 Valeurs Rapport
Base PPP P
coef. var. x x2 e1 e2 e3
1 
0 e1 1/2 0 1 −1/2 0 10 20
 
500 x2 1/2 1 0 1/2 0 40 80
0 e3 3/2 0 0 −1/2 1 40 80/3
Zj 250 500 0 250 0 20000
Cj − Zj 150 0 0 -250 0 ——

Variables de base : e1 = 10 ; x2 = 40 et e3 = 40
Variables hors base : x1 = e2 = 0

Remarque : Ce tableau correspond au sommet B2 (0; 40).

39

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

✓ (T2 ) non optimal : C1 − Z1 = 150 > 0

✓ Changement de base :
Variable entrante : x1 (un seul choix)
10 40 40
Variable sortante : e1 car min{ 1/2 ; 1/2 ; 3/2 } = 20,
Pivot et transformations : p = 1/2 ;
Lp → 2Lp ; L2 → −Lp + L2 ; L3 → −3Lp + L3
Ce qui nous ramène à un sommet adjacent, correspondant au ta-
bleau suivant :

40

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

(T3 )

Cj
PP
PP 400 500 0 0 0 Valeurs Rapport
Base PPP P
coef. var. x1 x2 e1 e2 e3
400 x1 1 0 2 -1 0 20
500 x2 0 1 -1 1 0 30
0 e3 0 0 -3 1 1 10
Zj 400 500 300 100 0 23000
Cj − Zj 0 0 -300 -100 0 ——

Variables de base : x1 = 20 ; x2 = 30 et e3 = 10
Variables hors base : e1 = e2 = 0

Remarque : Ce tableau correspond au sommet J(20; 30).

41

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

✓ (T3 ) est optimal puisque les coûts marginaux des VHB sont
tous négatifs (problème de maximisation). La fonction objectif ne
peut être améliorée davantage.

✓ Conclusion :
L’optimum est atteint au point (20,30), avec Zmax = 23000.
(Même résultat obtenu par la méthode graphique)

✓ Récapitulons :

42

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

XXX j C
400 500 0 0 0 Valeurs Rapport
Base XXX
coef. var. x1 x2 e1 e2 e3
0 e1 1

1 1 0 0 50 50
0 e2 1
2
0 1 0 80 40
0 e3 2 1 0 0 1 80 80
Zj 0 0 0 0 0 0
Cj − Zj 400 500 0 0 0 ——
XX Cj
XXX 400 500 0 0 0 Valeurs Rapport
Base X
coef. var.
 x1 x2 e1 e2 e3
0 e1
1/2
0 1 −1/2 0 10 20
500 x2 1/2 1 0 1/2 0 40 80
0 e3 3/2 0 0 −1/2 1 40 80/3
Zj 250 500 0 250 0 20000
Cj − Zj 150 0 0 -250 0 ——
XXX j C
400 500 0 0 0 Valeurs Rapport
Base XXX
coef. var. x1 x2 e1 e2 e3
400 x1 1 0 2 -1 0 20
500 x2 0 1 -1 1 0 30
0 e3 0 0 -3 1 1 10
Zj 400 500 300 100 0 23000
Cj − Zj 0 0 -300 -100 0 ——

43

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Exercice supplémentaire
Résoudre le PL suivant par les tableaux de simplexe puis retrouver
le résultat obtenu par la méthode graphique :

Max Z = 7x1 + 9x2

s.c. x1 ; x2 ≥ 0
x1 + x2 ≤ 8
x2 ≤ 4
2x1 + 3x2 ≤ 19

44

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

3.2 Cas où l’origine O(0, 0, · · · , 0) n’est pas une solution ad-

missible : Méthode des variables artificielles

Exemple :

Forme canonique (PL) Forme standard (PL=)

Max Z = x1 + 4x2 Max Z = x1 + 4x2 −Ma

s.c. x1 ; x2 ≥ 0 s.c. x1 ; x2 ; e1 ; e2 ; e3 ; a ≥ 0
2x1 + x2 ≥ 6 2x1 + x2 −e1 + a = 6
x1 − x2 ≤ 3 x1 − x2 +e2 = 3
x1 + x2 ≤ 5 x1 + x2 +e3 = 5

où M est un nombre positif suffisamment grand (M → +∞).

45

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Démarche :
Lorqu’un PL contient une contrainte technologique de type :
X
αi xi ≥ (ou =) b (b > 0) (⋆)
i
1 Dans (PL=), on introduit dans toute contrainte
technologique de type (⋆), en plus de l’éventuelle variable
d’écart, une nouvelle variable artificielle positive aj

46

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Démarche :
Lorqu’un PL contient une contrainte technologique de type :
X
αi xi ≥ (ou =) b (b > 0) (⋆)
i
1 Dans (PL=), on introduit dans toute contrainte
technologique de type (⋆), en plus de l’éventuelle variable
d’écart, une nouvelle variable artificielle positive aj
2 Pour chaque variable artificielle aj , on ajoute à la fonction
objectif un terme de pénalité égal à :
−Maj pour un problème de maximisation
+Maj pour une minimisation

47

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Démarche :
Lorqu’un PL contient une contrainte technologique de type :
X
αi xi ≥ (ou =) b (b > 0) (⋆)
i
1 Dans (PL=), on introduit dans toute contrainte
technologique de type (⋆), en plus de l’éventuelle variable
d’écart, une nouvelle variable artificielle positive aj
2 Pour chaque variable artificielle aj , on ajoute à la fonction
objectif un terme de pénalité égal à :
−Maj pour un problème de maximisation
+Maj pour une minimisation
3 A l’optimum, toute variable artificielle aj = 0 (des V.H.B).

Le nombre M est une constante positive largement plus grande que

toutes les valeurs rencontrées dans l’étude du problème (M → +∞).
48

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

(T1 )

Cj
PP
PP 1 4 0 -M 0 0 Valeurs
Base PPP P
coef. var. x x2 e1 a e2 e3
1
-M a 2
1 -1 1 0 0 6
0 e2 1 -1 0 0 1 0 3
0 e3 1 1 0 0 0 1 5
Zj -2M -M M -M 0 0 -6M
Cj − Zj 1+2M 4+M -M 0 0 0 —–

Variables de base : a = 6 ; e2 = 3 et e3 = 5
Variables hors base : x1 = x2 = e1 = 0

49

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

✓ (T1 ) non optimal : Cj − Zj (x1 ) = 1 + 2M > 0 (problème de max.)

✓ Changement de base :

Variable entrante : x1 , car max{1 + 2M; 4 + M} = 1 + 2M

Variable sortante : a, car min{ 62 ; 31 ; 15 } = 6
2 (ou 13 )
Pivot et transformations : p = 2 ;
1 −1 p
Lp → Lp ; L1 → L + L1
2 2
Remarque : Lorsqu’une variable artificielle sort de la base dans
un tableau, elle sort définitivement du problème.

50

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

(T2 )

Cj
PP
PP 1 4 0 0 0 Valeurs
Base PPP P
coef. var. x1 x2 e1 e2 e3
1 x1 1 1/2 -1/2 0 0 3
0 e2 0 -3/2 1/2 1 0 0
 
0 e3 0 1/2 1/2 0 1 2
 
Zj 1 1/2 -1/2 0 0 3
Cj − Zj 0 7/2 1/2 0 0 —–

Variables de base : x1 = 3 ; e2 = 0 et e3 = 2
Variables hors base : x2 = e1 = 0

51

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

✓ (T2 ) non optimal : Cj − Zj (x2 ) = 7/2 > 0 (problème de max.)

✓ Changement de base :

Variable entrante : x2 , car max{7/2; 1/2} = 7/2

2 3
Variable sortante : e3 , car min{ 1/2 ; 1/2 }=4
Pivot et transformations : p = 1/2 ;

Lp → 2Lp ; L1/2 → −Lp + L1/2 ; L−3/2 → 3Lp + L−3/2

52

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

(T3 )

Cj
PP
PP 1 4 0 0 0 Valeurs
Base PPP P
coef. var. x1 x2 e1 e2 e3
1 x1 1 0 -1 0 -1 1
0 e2 0 -0 2 1 3 6
4 x2 0 1 1 0 2 4
Zj 1 4 3 0 7 17
Cj − Zj 0 0 -3 0 -7 —–

Variables de base : x1 = 1 ; e2 = 6 et x2 = 4
Variables hors base : e1 = e3 = 0

53

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

✓ (T3 ) est optimal puisque les coûts marginaux des VHB sont
tous négatifs (problème de maximisation).
✓ Conclusion :
L’optimum est atteint au point (1,4), avec Zmax = 17.

Remarque :
A l’optimum, les 1ère et 3e contraintes sont saturées (e1 = e3 =
0), contrairement à la 2e (e2 = 6 ̸= 0).

Récapitulons :

54

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

XXX j C
1 4 0 -M 0 0 Valeurs
Base XXX
coef. var.

x1 x2 e1 a e2 e3
-M a
2
1 -1 1 0 0 6
0 e2 1 -1 0 0 1 0 3
0 e3 1 1 0 0 0 1 5
Zj -2M -M M -M 0 0 -6M
Cj − Zj 1+2M 4+M -M 0 0 0 —–
XXX Cj
1 4 0 0 0 Valeurs
XBase XX
coef. var. x1 x2 e1 e2 e3
1 x1 1 1/2 -1/2 0 0 3
0 e2 0
-3/2 1/2 1 0 0
0 e3 0
1/2
1/2 0 1 2
Zj 1 1/2 -1/2 0 0 3
Cj − Z j 0 7/2 1/2 0 0 —–
XXX Cj
1 4 0 0 0 Valeurs
Base XXX
coef. var. x1 x2 e1 e2 e3
1 x1 1 0 -1 0 -1 1
0 e2 0 -0 2 1 3 6
4 x2 0 1 1 0 2 4
Zj 1 4 3 0 7 17
Cj − Zj 0 0 -3 0 -7 —–

55

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Exercice supplémentaire
Résoudre le PL suivant par les tableaux de simplexe puis retrouver
le résultat obtenu par la méthode graphique :

Min Z = 4x1 + x2
s.c. x1 ; x2 ≥ 0
−x1 + 2x2 ≤ 4
2x1 − x2 ≤ 16
x1 + 2x2 ≥ 8

56

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

3.3 Différents cas lus sur les tableaux du simplexe

Lorsque dans un PL, les variables de décision sont continues, sa
résolution aboutit à l’une des situations suivantes :
1 La fonction objectif n’a pas d’optimum fini :
C’est le cas où un coût marginal d’une VHB est strictement
positif pour un problème de maximisation (ou strictement
négatif pour une minimisation) et tous les termes dans la
colonne correspondante sont négatifs ≤ 0.
Exemple :

Max Z = x1 + 3x2
s.c. x1 ; x2 ≥ 0
x1 − x2 ≤ 60
−x1 + x2 ≤ 80

57

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

2 La fonction objectif a un optimum fini unique :

C’est le cas lorsque le tableau est optimal avec tous les coûts
marginaux des V.H.B. sont non nuls.
3 La fonction objectif a une infinité d’optimums finis :
C’est le cas lorsque le tableau est optimal avec un des coûts
marginaux des V.H.B. (non artificielles) est nul.
Les variables étant continues.
Exemple :

Max Z = x1 + x2
s.c. x1 ; x2 ≥ 0
x1 + x2 ≤ 80
x1 − x2 ≤ 30
−x1 + 4x2 ≤160
58

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

4. Dualité en programmation linéaire

4.1 Ecriture du programme dual
Considérons le programme linéaire

Max Z = x1 + 3x2 + x3
s.c. x1 ; x2 ; x3 ≥ 0
x1 + x2 + 2x3 ≤ 12
2x1 − x2 + 6x3 ≥ 8

59

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Le programme dual s’écrit :

Min W = 12p1 − 8p2

s.c. p1 ; p2 ≥ 0
p1 − 2p2 ≥ 1
p1 + p2 ≥ 3
2p1 − 6p2 ≥ 1

60

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Règle générale :

Primal Dual

n r
X
Min W = bi pi
X
Max Z = cj xj
j=1 i=1

s.c. X ≥ 0 s.c. P≥0

AX ≤ B ( A)P ≥ t C
t

     
x1 b1 p1
  . . .
où C = c1 · · · cn , X =   ..  , B =  .. , et P =  .. .
    
xn br pr
A : la matrice des coefficients techniques du primal (d’ordre (r , n)),
(t A) : sa matrice transposée.
61

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

4.2 Interprétation économique de la dualité

Rappelons un exemple précédent (résolu par les 2 méthodes) :
Une entreprise E fabrique et vend 2 types de produits A et B à
partir de 3 facteurs de production (les ressources) notés F1 , F2 et
F3 . La consommation de la production de A et B en F1 , F2 et F3
est donnée par le tableau

F1 F2 F3 Profit unitaire
A 1 1 2 400
B 1 2 1 500
Ressources/jour 50 80 80

L’entreprise cherche à déterminer un programme de fabrication

maximisant son profit global journalier, tout en respectant les
contraintes liées à ses resources.
62

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

En notant par x1 et x2 les quantités respectives des produits A et

B à fabriquer, nous avons montré que ce problème qui peut être
modélisé par

Max Z = 400x1 + 500x2

s.c. x1 ; x2 ≥ 0
x1 + x2 ≤ 50
x1 + 2x2 ≤ 80
2x1 + x2 ≤ 80

admet une solution unique atteinte au point (20; 30) avec Zmax =
23 000.

63

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Imaginons une entreprise concurrente E ′ qui souhaite racheter

la totalité des ressources de E . Elle cherchera des prix d’achat uni-
taires p1 , p2 et p3 de chaque facteur de production F1 , F2 et F3
respectivement, de telle façon que

Le prix de rachat total 50p1 + 80p2 + 80p3 soit minimal,

L’entreprise E acceptera lorsque le prix de vente équivalent à chaque

unité de production de A et B sera au moins égal au profit auquel
elle renoncerait.
Autrement dit :

p1 + p2 + 2p3 ≥ 400,

p1 + 2p2 + p3 ≥ 500.

64

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Ces prix unitaires sont donc obtenus en résolvant

Min W = 50p1 + 80p2 + 80p3

s.c. p1 ; p2 ; p3 ≥ 0
p1 + p2 + 2p3 ≥ 400
p1 + 2p2 + p3 ≥ 500

Remarque : On vérifie aisément par les tableaux de simplexe

que ce PL dual admet également une solution atteinte au point
(300; 100; 0) avec Wmin = 23 000.

65

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

4.3 Recherche d’une solution optimale du dual

Primal Dual
n r
X
Min W = bi pi
X
Max Z = cj xj
j=1 i=1

s.c. X ≥ 0 s.c. P≥ 0
AX ≤ B ( A)P ≥ t C
t

variables d’écart : ei variables d’écart : hj

66

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Considérons d’abord le résultat fondamental suivant :

Théorème de dualité
Etant donné deux PL duaux, on a l’une des situations suivantes :
1 Les deux PL admettent des solutions optimales finies X ∗ pour
le primal et P ∗ pour le dual, avec la même valeur optimale :
Z (X ∗ ) = W (P ∗ )
2 L’un n’a pas de solution admissible finie et l’autre admet des
solutions admissibles mais ne possède pas de solution
optimale finie.
3 Aucun des deux PL n’a de solution admissible.

Par conséquent :
Lorsque le primal possède une solution finie X ∗ , le théorème de
dualité garantit l’existence d’une solution finie P ∗ pour le dual
avec
W (P ∗ ) = Z (X ∗ ) 67

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Question :
Comment calculer les coordonnées de P ∗ = (p1 , p2 , · · · , pr ) ?

Réponse :
Selon la démarche adoptée pour la résolution du primal, on peut
utiliser l’une des 2 méthodes suivantes :
1 Cas où la solution du primal X = (x1 , x2 , · · · , xn ) a été
oblenue par les tableaux de simplexe : formules simples ;
2 Cas général : par le théorème des relations d’exclusion.

68

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Exemple : Soit le programme linéaire

Min Z = 4x1 + x2
s.c. x1 ; x2 ≥ 0
−x1 + 2x2 ≤ 4
2x1 − x2 ≤ 16
x1 + 2x2 ≥ 8

1. Résoudre ce programme linéaire par les tableaux de simplexe.

2. En déduire les coordonnées d’une solution optimale finie pour le
programme dual, par deux méthodes différentes.

69

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Réponse
1. Après écriture de la forme standard, qui donne naissance d’une
seule variable artificielle dans la 3e contrainte, on passe aux ta-
bleaux de simplexe
(T1 )
Cj
PP
PP 4 1 0 0 0 M Valeurs
Base PPP P
coef. var. x1 x e1 e2 e3 a
2
0 e1 -1 2
1 0 0 0 4
0 e2 2 -1 0 1 0 0 16
M a 1 2 0 0 -1 1 8
Zj M 2M 0 0 -M M 8M
Cj − Zj 4-M 1-2M 0 0 M 0 —–

(T1 ) n’est pas optimal.

70

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

(T2 )
Cj
PP
PP 4 1 0 0 0 M Valeurs
Base PPP P
coef. var. x1 x2 e1 e2 e3 a
1 x2 -1/2 1 1/2 0 0 0 2
0 e2 3/2
 0 1/2 1 0 0 18
M a 2
0 -1 0 -1 1 4
Zj (-1/2)+2M 1 (1/2)-M 0 -M M 2+4M
Cj − Zj (9/2)-2M 0 (-1/2)+M 0 M 0 —–

(T2 ) n’est pas optimal.

71

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

(T3 )
Cj
PP
PP 4 1 0 0 0 Valeurs
Base PPP P
coef. var. x1 x2 e1 e2 e3
1 x2 0 1 1/4 0 -1/4 3
0 e2 0 0 5/4 1 3/4 15
4 x1 1 0 -1/2 0 -1/2 2
Zj 4 1 -7/4 0 -9/4 11
Cj − Zj 0 0 7/4 0 9/4 —–

Puisque les coûts marginaux des VHB sont strictement positifs (pro-
blème de min), (T3 ) est optimal en une solution unique atteinte au point
(2; 3), avec Zmin = 11 .

72

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

2. Dans le primal, la matrice des coefficients techniques est :

 
1 −2
A = −2 1 
 
1 2
Sa matrice transposée est égale à :
!
t 1 −2 1
A=
−2 1 2
Le programme dual s’écrit donc :
Max W = −4p1 − 16p2 + 8p3
s.c. pi ≥ 0, ∀i
p1 − 2p2 + p3 ≤ 4
−2p1 + p2 + 2p3 ≤ 1

73

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Rappelons que le programme primal possède une solution unique

donnée, selon le tableau optimal (T3 ), par :
(x1 , x2 ) = (2, 3) et (e1 , e2 , e3 ) = (0, 15, 0) avec Zmin = 11

Donc, selon le théorème de dualité, le programme dual admet éga-

lement une solution optimale finie (p1 , p2 , p3 ) verifiant

W (p1 , p2 , p3 ) = 11

74

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Méthode 1 :
Selon le tableau de simplexe optimal (T3 ) :
p1 = |coût marginal(e1 )| = |7/4| = 7/4 ;
p2 = |coût marginal(e2 )| = |0| = 0 ;
p3 = |coût marginal(e3 )| = |9/4| = 9/4.

Vérification du théorème de la dualité :

W (7/4, 0, 9/4) = −4(7/4) − 16(0) + 8(9/4)

= −7 − 0 + 18
= 11
= Zmin

75

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Méthode 2 :
En appliquant les relations d’exclusion, on obtient :
• x1 = 2 ̸= 0
⇒ la 1ere contrainte dans le dual est saturée : p1 −2p2 +p3 = 4 ;
• x2 = 3 ̸= 0
⇒ la 2e contrainte est saturée : −2p1 + p2 + 2p3 = 1 ;
• e2 = 15 ̸= 0 (la 2e contrainte dans le primal n’est pas saturée en
(2, 3)) ⇒ la 2e variable de décision dans le dual est nulle : p2 = 0.




p1 − 2p2 + p3 = 4
2 p =0

−2p + p + 2p = 1

1 2 3

La résolution de ce système mène au même résultat :

p1 = 7/4, p2 = 0, p3 = 9/4.
76

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

En conclusion :
Pour déterminer les coordonnées d’une solution optimale

P ∗ = (p1 , p2 , · · · , pr )

du programme dual, on peut utiliser l’une des 2 méthodes ci-après,

selon la démarche adoptée pour la résolution du primal :
1 Cas où la solution du primal X = (x1 , x2 , · · · , xn ) a été
oblenue par les tableaux de simplexe :
On montre que les coordonnées pi sont calculées à partir du
tableau de simplexe optimal par les relations simples :

pi = | coût marginal (ei )|, ∀i = 1, 2, · · · , r

77

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

2 Cas général : On utilise le théorème des relations d’exclusion

suivant
Théorème des relations d’exclusion
Deux solutions admissibles X = (x1 , · · · , xn ) et P = (p1 , · · · , pr ),
respectivement du primal et du dual, sont optimales si et
seulement si les deux relations suivantes sont réalisées :
1 xj · hj = 0 , pour tout j = 1, · · · , n ;
2 pi · ei = 0 , pour tout i = 1, · · · , r .
Ce résultat est aussi connu sous le nom du "Théorème des écarts
complémentaires".

78

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Avant d’expliciter ce théorème, rappelons la définition suivante

Définition
Une contrainte de type
X
aij xj ≤ bi ( ou ≥ bi )
j

est dite saturée en X ∗ = (x1∗ , · · · , xn∗ ) si

aij xj∗ = bi .
X

(autrement dit, la variable d’écart est nulle).

79

Pr. Benmlih K. Recherche opérationnelle

 1. Modélisation linéaire
Chapitre 0. Introduction générale
2. Résolution graphique
Chapitre 1. Programmation linéaire
3. Résolution par les simplexes
Chapitre 2. Eléments de la théorie des graphes et applications
4. Dualité en programmation linéaire

Dans la pratique :
Supposons que les coordonnées xj d’une solution optimale X =
(x1 , · · · , xn ) du primal sont connues ainsi que les valeurs des va-
riables décarts ei .
D’abord, le théorème de dualité garantit l’existence d’une
solution optimale du dual P = (p1 , · · · , pr ).
Ensuite, le théorème des relations d’exclusion peut s’énoncer
comme suit :
Chaque xj ̸= 0 implique que la contrainte j correspondante
dans le dual est saturée en P (c-à-d hj = 0) ;
Toute contrainte du primal, de numéro i, non saturée en X
(c-à-d que ei ̸= 0) implique que pi = 0.

80

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

Chapitre 2
Eléments de la théorie des graphes et applications

1 Notions de base sur les graphes

2 Problème de cheminement optimal
3 Problèmes d’ordonnacement

81

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

1. Quelques notions de base

1.1. Principales définitions
Un graphe orienté G = (X , U) est la donnée de deux
ensembles :
Un ensemble X = {x1 , x2 , · · · , xn } dont les éléments sont
appelés sommets ;
Un sous-ensemble U ⊂ X × X noté U = {u1 , u2 , · · · , um } dont
les éléments sont appelés arcs.
Pour un arc u = (xi , xj ), le sommet xi s’appelle extrémité
initiale (ou origine) et xj son extrémité finale (ou destination).
Dans l’arc (xi , xj ), le sommet xj est dit un successeur de xi .
On dit aussi que le sommet xi est un prédecesseur de xj .
Lorsque xi = xj , l’arc (xi , xi ) s’appelle une boucle.
Un arc privé de son orientation s’appelle une arête.
82

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

Deux sommets sont dits adjacents s’ils sont joints par un arc
(ou une arête).
Deux arcs sont dits adjacents s’ils ont au moins une extrémité
commune.
Un sous-graphe est obtenu par suppression d’un certain
nombre de sommets (et par conséquent de tous les arcs qui
leur sont liés).
Un graphe partiel est obtenu par suppression d’un certain
nombre d’arcs.

83

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

1.2 Modes de représentation d’un graphe

1 Représentation par dictionnaire (liste) : Il s’agit d’un tableau
à entrée simple où chaque ligne correspond à un sommet et
comporte la liste de ses prédecesseurs ou de ses successeurs.
2 Représentation sagittale : par un dessin contenant des points
et des flèches.
3 Représentation par la matrice d’adjacence : Considérons un
graphe G = (X , U) contenant n sommets. La matrice
d’adjacence (ou matrice booléenne) est une matrice carrée
d’ordre n de terme général :
(
1, si (xi , xj ) ∈ U
aij =
0, sinon.

84

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

Exemple. Soit un graphe donné par son disctionnaire des sui-

vants :
Sommet Successeurs
x1 x3 ; x4
x2 x1 ; x5 ; x6
x3 x1 ; x3 ; x5
x4 –
x5 x1 ; x6
x6 x2 ; x5

Représenter ce graphe autrement.

Réponse :

85

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

Remarques :
Dans la matrice d’adjacence,
La ligne i représente les successeures du sommet xi .
La colonne j représente les prédecesseures du sommet xj .
La présence du chiffre 1 sur la diagonale principale désigne la
présence d’une boucle.
Si la matrice est symétrique, le graphe peut être considéré
comme non orienté.

86

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

2. Problèmes de cheminement optimal

Un graphe G = (X , U) est dit valué lorsqu’à chaque arc a ∈ U on
associe une longueur l(a).
Cette longueur l(a) peut représenter une durée de parcours, un
bénéfice de transport, ...
Le problème du plus court chemin (plus long chemin) entre les
sommets i et j consiste à trouver un chemin µ(i, j) dont la lon-
gueur X
l(µ) = l(a)
a∈µ(i,j)

est minimale (respectivement maximale).

87

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

2.1 Principe d’optimalité

Théorème
Tout sous-chemin d’un plus court chemin (respectivement d’un
plus long chemin) est un chemin de longueur minimale
(respectivement maximale).
Autrement dit :
Si un chemin est optimal, tous ses sous-chemins sont aussi opti-
maux.

88

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

2.2 Recherche d’un chemin optimal à origine unique

Lorsqu’on cherche un chemin optimal d’un sommet fixé x1 à
tous les autres sommets du graphe, plusieurs algorithmes peuvent
être appliqués selon les propriétés et la nature du graphe :
algorithme de Bellman-Ford : pour les graphes sans circuit
(longueurs quelconques), avec min. ou max.,
algorithme de Dijkstra : pour les graphes de longueurs
positives (même en présence de circuit), avec min.
...

89

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

Principe : affecter à chaque sommet xi une marque mi . En fin

d’algorithme, cette marque représente la longueur d’un chemin
optimal de l’origine x1 au sommet considéré xi .

Algorithme de Bellman-Ford (sans circuit, de longueurs ∀) (1958)

L’algorithme s’applique au graphe après l’avoir ordonné en ni-
veaux. La démarche se fait donc en 2 étapes :
a) Etape 1 : Décomposition en niveaux du graphe
Définition
On appelle niveau d’un sommet xi la longueur maximale au sens
des arcs allant de l’origine vers ce sommet.

90

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

Procédure
L’ensemble de niveau 0 est celui des sommets sans
prédecessurs : N0 = {x ∈ X ; P(x ) = ∅} ;
D’un niveau à un autre immédiatement supérieur, on a
Nk = {x ∈ X \ Nk−1 ; P(x ) = ∅} ;
S
S’arrêter lorsque k Nk = X (c-à-d. les niveaux de tous les
sommets du graphe sont déterminés).
Le graphe ordonné en niveaux est représenté dans l’ordre croissant
des niveaux des différents sommets.
Remarques :
✓ Si à une quelconque étape k ≥ 0 on trouve Nk = ∅, cela
signifie que le graphe contient au moins un circuit.
✓ Lorsque l’origine n’est pas l’unique sommet de niveau 0, la
suite de l’étude portera sur le sous-graphe obtenu en
éliminant tous les autres sommets de niveaux inférieurs ou
égaux à celui de l’origine. 91

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

b) Etape 2 : Détermination des marques

Pour l’origine x1 (de niveau 0), on pose m(x1 ) = 0 ;

D’un niveau à un autre immédiatement supérieur, on pose :

m(xi ) = min{m(xj ) + l(xj , xi ) ; xj ∈ P(xi )}

Remarque Dans le cas de la recherche d’un plus long chemin,

remplacer "min" par "max".

Question : Comment identifier un chemin de valeur optimale

allant de x1 à xn ?
On affecte à chaque sommet xj sa marque définitive mj ;
On pose xp = xn et on cherche les sommets xj ∈ P(xp )
vérifiant mj = mp − l(xj , xp ) ;
Pour chaque chemin identifié, s’arrêter lorsque x1 est atteint.
92

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

Exemple : Le tableau ci-dessous représente les liaisons possibles

entre 12 villes, avec les coûts nets de transport d’une marchandise
(en millier de dirhams par centaine de boites).
Ville Ville suivante coût de transport respectif
1 10 ; 12 20 ; 20
2 5 30
3 1; 6; 7; 9 40 ; 22 ; 18 ; 11
4 5 20
5 – –
6 1 ; 11 15 ; 13
7 4 ; 12 15 ; 40
8 3; 6 12 ; 40
9 1 ; 7 ; 11 26 ; 17 ; 25
10 2 27
11 10 ; 12 18 ; 21
12 2; 4 23 ; 40
93

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

Travail à faire :
1 Donner la matrice d’adjacence de ce graphe.
2 Représenter le graphe G sous sa forme ordonnée par niveaux.
3 Par la procédure de marquage, déterminer :
3.1 le coût net minimal et le(s) chemin(s) correspondant(s) pour
expédier une centaine de boites, au départ de la ville (8) vers
la ville (2).
3.2 le coût net maximal et le(s) chemin(s) correspondant(s) pour
expédier une centaine de boites, au départ de la ville (9) vers
la ville (5).

Réponse :

94

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

Figure – Coût minimal

95

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

Figure – Coût maximal

96

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

3. Problèmes d’ordonnancement
3.1. Introduction
Objectif : Ordonner dans le temps un ensemble d’opérations contri-
buant à la réalisation d’un même projet (construction d’un bâti-
ment, lancement d’un nouveau produit, ... )
Le déroulement de ces diverses tâches doit respecter certaines
contraintes de type :
- contrainte de succession,
- contrainte de date.

Il s’agit donc de minimiser la durée totale de réalisation du projet

en tenant compte des durées nécessaires à la réalisation de chaque
opération et des contraintes qu’elles doivent respecter.

97

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

Le problème ainsi posé peut être schématisé sous forme d’un graphe
sans circuit, selon deux modes :
✓ la méthode M.P.M.
(Méthode des potentiels Metra), appelée également méthode
graphe-tâches ;
✓ la méthode PERT
(Programm Evaluation Research Task), appelée également méthode
graphe-étapes.

Exemple : Les opérations mises en jeu dans la construction d’un

ensemble hydro-électrique sont notées par les lettres a, b, · · · , i.
On suppose que toutes les contraintes sont de type contraintes de
succession stricte.
Les données du problème sont résumées dans le tableau suivant :
98

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

OPERATIONS
OPERATION DESIGNATION DUREE (mois) PREREQUISES
Construction des voies
d’accès a 4 –
Travaux des terrassemets b 6 a
Construction des bâtiments
administratifs c 4 –
Commande du matériel
électrique d 12 –
Construction de la centrale e 10 b; c; d
Construction du barrage f 24 b; c
Installation des galeries et
conduites forcées g 7 a
Montage des machines h 10 e; g
Essais de fonctionnement i 3 f; h

99

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

Déterminer successivement :
1 La durée minimale d’exécution du projet
2 Le calendrier de début d’exécution au plus tôt des différentes
tâches,
3 Le calendrier de début d’exécution au plus tard des différentes
tâches,
4 Le(s) chemin(s) critique(s) (succession de tâches ne tolérant
aucun retard d’exécution),
5 Pour chaque tâche, le retard maximal qu’elle pourrait prendre
sans retarder la date de la fin de projet.

100

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

3.2. Méthode MPM

3.2.1 Principe :
Le graphe pour ce mode de représentation est construit comme
suit :
1 Chaque tâche xi est représentée par un sommet i.
2 Toute relation d’antériorité immédiate est représentée par un
arc.
3 La longueur l(i, j) d’un arc (i, j) est égale à la durée minimale
qui doit s’écouler entre le début de la tâche xi et le début de
la tâche xj .
Lorsque les contraintes sont uniquement de type "succession
stricte", cette longueur est égale à la durée de la tâche
origine.

101

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

3.2.2 Construction du graphe MPM :

1 Le graphe MPM est ordonné par niveaux (graphe sans
circuit).
2 Chaque sommet sera représenté par un rectangle où
x : désigne la tâche ;
Tx : désigne la date de début au plus tôt de la tâche x ;
Tx∗ : désigne la date de début au plus tard de la tâche x .

3 On introduit à la fin du graphe un sommet représentant une

tâche fin (notée souvent par la lettre z) auquel seront reliés
tous les sommets qui n’ont pas de successeurs. 102

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

3.2.3 Détermination du calendrier au plus tôt

Afin de déterminer les dates de début d’exécution au plus tôt TK
des différentes tâches K du projet, nous utilisons l’algorithme sui-
vant :
1 Pour les sommets x de niveau 0, on pose Tx = 0.
2 Pour les sommets de niveaux supérieurs, on pose
Tx = longueur du chemin le plus long allant d’un sommet de
niveau 0 au sommet x .

De ce fait, la durée minimale de réalisation du projet est Tz

où z désigne la tâche finale.

103

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

3.2.4 Détermination du chemin critique

Le chemin critique est le chemin le plus long allant d’un sommet
de niveau 0 au sommet final z.

Tout retard observé sur l’exécution de l’une des tâches situées sur
le chemin critique retardera la date à laquelle peut s’achever au
plus tôt l’ensemble des travaux du projet.

104

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

3.2.5 Détermination du calendrier au plus tard

Pour déterminer les dates de début d’exécution au plus tard TK∗
des différentes tâches K du projet, on procède de la manière sui-
vante :
1 Pour le sommet final z, on pose Tz∗ = Tz .
2 D’un niveau à un autre inférieur, on pose
Tx∗ = Min {Ty∗ − l(x , y ) ; y ∈ S(x )}

105

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

3.2.6 Marge libre et marge totale d’une tâche

La marge libre d’une tâche :

C’est le retard maximal que l’on peut prendre dans la
réalisation de la tâche sans retarder la date de début au plus
tôt de toute autre tâche qui suit immédiatement.
Donc, la marge libre d’une tâche x est donnée par :
ML(x ) = Min {Ty − Tx − l(x , y ); y ∈ S(x )}

La marge totale d’une tâche :

C’est le retard maximal que l’on peut prendre dans la mise en
route de la tâche, sans remettre en cause la date de la fin des
travaux.
Donc, la marge totale d’une tâche x est donnée par :
MT (x ) = Tx∗ − Tx

106

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

Application au problème de construction de barage

107

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

4.2 Méthode PERT

4.2.1 Principe :
Le graphe pour ce mode de représentation est construit comme
suit :
1 Chaque tâche x est représentée par un arc (i, j) dont la
longueur est égale à la durée de la tâche.
2 Chaque sommet du graphe est une étape signifiant que :
toutes les tâches qui arrivent sont achevées,
toutes les tâches qui partent peuvent commencer.

Remarque : La représentation de certaines relations d’antériorité

nécessite l’introduction de certaines tâches fictives de durée 0.
Exemple 1 :

Exemple 2 :
108

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

4.2.2 Construction du graphe PERT :

1 Chaque sommet sera représenté par un cercle où
x : désigne le numéro de l’étape
tx : désigne la date attendue de l’étape x
tx∗ : désigne la date limite de l’étape x .

2 On introduit
un sommet initial d’où partent toutes les tâches sans
contrainte d’antériorité
un sommet final z auquel arrivent toutes les tâches sans
suivantes. Ce sommet permettra de dater la fin des travaux.
109

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

4.2.3 Détermination du calendrier au plus tôt

Il s’agit de déterminer les dates de début d’exécution au plus tôt
TK des différentes tâches K du projet.
Pour ce faire, on détermine d’abord les différentes dates attendues
tx comme suit :
1 Pour le sommet initial n◦ 1, on pose t1 = 0.
2 Pour les sommets x suivants : tx = longueur du chemin le
plus long allant du sommet initial 1 au sommet x .
Ensuite, si une tâche K est représentée par un arc (i, j), sa date
de début au plus tôt est :

TK = t i

110

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

4.2.4 Détermination du chemin critique

Le chemin critique est le chemin le plus long allant d’un sommet
de niveau 0 au sommet final z.

Tout retard observé sur l’exécution de l’une des tâches situées sur
le chemin critique retardera la date à laquelle peut s’achever au
plus tôt l’ensemble des travaux du projet.

111

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

4.2.5 Détermination du calendrier au plus tard

Il s’agit de déterminer les dates de début d’exécution au plus tard
TK∗ des différentes tâches K du projet.
Pour cela, on détermine d’abord les différentes dates limites tx∗
comme suit :
1 Pour le sommet final z, on pose tz∗ = tz .
2 D’un niveau à un autre inférieur, on pose
tx∗ = Min {ty∗ − l(x , y ) ; y ∈ S(x )}

Enfin, la date de début au plus tard pour la tâche K , représentée

par l’arc (i, j) et de durée dK , est

TK∗ = tj∗ − dK

112

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

4.2.6 Marge libre et marge totale d’une tâche

La marge libre d’une tâche :

C’est le retard que l’on peut prendre dans la réalisation de la
tâche sans retarder la date de début au plus tôt de toute
autre tâche qui suit.
Donc, la marge libre d’une tâche K , entre deux étapes i et j,
est donnée par : ML(K ) = tj − ti − dK

La marge totale d’une tâche :

C’est le retard maximal que l’on peut prendre dans la mise en
route de la tâche, sans remettre en cause la date de la fin des
travaux.
Donc, la marge totale d’une tâche K , entre deux étapes i et
j, est donnée par : MT (K ) = tj∗ − ti − dK = TK∗ − TK

113

Pr. Benmlih K. Recherche opérationnelle

 Chapitre 0. Introduction générale 1. Notions de base sur les graphes
Chapitre 1. Programmation linéaire 2. Problème de cheminement optimal
Chapitre 2. Eléments de la théorie des graphes et applications 3. Problèmes d’ordonnancement

Application au problème de construction de barage

114

Pr. Benmlih K. Recherche opérationnelle