RECHERCHE OPÉRATIONNELLE

FOUAD KISSI
F. S. J. E. S Oujda

2019-2020

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

La R.O , c'est quoi ?

Dénition : La recherche opérationnelle ( R.O ) ou ( la science de

la décision ) est la discipline des méthodes scientiques utilisable
pour élaborer de meilleurs décisions. Elle permet de rationaliser, de
simuler, de planier et d'optimiser l'architecture et le
fonctionnement des systèmes de production ou d'organisation.
La R.O est une discipline récente ( environ 60-70 ans ) qui est à la
frontière entre Informatique, Economie et Mathématiques
appliquées.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Histoire récente de la RO

Origines militaire de la RO
- objectif : optimisation de la logistique militaire et du
réapprovisionnement des troupes
- création par le gouvernement britannique au début de la
seconde guerre mondiale
- G. Dantzig,  conseiller scientique  à la U.S. Air force,
met au point en 1947 l'algorithme du simplexe.
A l'origine, le mot opérationnelle signie donc en vue de
programmer des opérations militaires.
Après , le domaine de la RO s'est étendu à des applications
civiles.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

R de RO = recherche de solutions concrètes
La science du : " comment mieux faire avec moins "

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

La RO en pratique

sert à résoudre tous types de problèmes diciles ( issus de

l'industrie ou de la nance ) :
Production
Problèmes de transport
Problèmes de télécoms
Planication de projets
gestion nancière ( banques et assurances )
et beaucoup d'autres.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Plan

Partie I : Programmation linéaire

Chap 1 : Formulation des problèmes linèaires : Modèlisation
Chap 2 : Algorithme du simplexe
Partie II : Théorie des graphes
Chap 1 : Éléments de théorie de graphe
Chap 2 : Problèmes d'ordonnancement
Chap 3 : Problèmes de transport
Partie III : Gestion des stocks

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

PREMIER CHAPITRE

Formulation des problèmes linèaires : Modèlisation

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

I) Programmation linéaire

Dénition : La programmation linéaire est une branche des

mathématiques appliquées et plus précisément de l'optimisation liée
dont l'objectif est minimiser ou maximiser une fonction numérique
à plusieurs variables sachant que ces dernières sont liées par des
relations appelées contrainte.
Le principe de la programmtion linéaire est fondé sur le fait que :
La fonction à optimiser appelée fonction objectif ou fonction
économique a une expression linéaire ;
les expressions des contraintes sont toutes linéaires.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Remarque

En économie et gestion, l'objectif est à :

Maximiser s'il s'agit d'un avantage ( bénice, coût de vente,
rendement.......) ;
Minimiser s'il s'agit d'un incovénient ( perte, coût de
production, dépense, consommation.....).

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

II) Construction des programmes linéaires :
Modélisation

Programme Linéaire (PL) = Problème de la programmation

linéaire.
Modéliser ( Modélisation ) = Formuler le problème sous forme
mathématique et créer un modèle de PL qui représente le
problème en réalité.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

II) Construction des programmes linéaires :
Modélisation

Pour modéliser un problème linéaire, il faut suivre les étapes

suivantes :
1 Identier les variables principales ou les variables de décision

du problème.
2 Exprimer la fonction objectif en termes des variables identiées

en précisant s'il s'agit d'un problème à maximiser ou à

minimiser (l'objectif traduit les buts et les préférences des
décideurs économistes).
3 Formuler les contraintes sous forme d'équations et ( ou )

d'inéquations linéaires.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

III) Exemples
1) Problème de maximisation du prot
Enoncé du problème :
Une entreprise fabrique deux produits A et B, en utilisant une
machine m et deux matières premières p et q. On dispose chaque
jour de 8 heures de m, de 10 kg de p et de 36 kg de q. On suppose
que :
La production d'une unité de A nécessite 2 kg de p et 9 kg de
q, et utilise la machine m durant 1 heure ;
La production d'une unité de B nécessite 2 kg de p et 4 kg de
q, et utilise la machine m durant 2 heure ;
les prots réalisés sont de 50 dh par unité de A et 60 dh par
unité de B.
L'objectif que poursuit l'entreprise est de maximiser le prot qu'elle
pourra tirer, par jour, de ces 2 produits en utilisant au mieux ses
ressources.
FOUAD KISSI RECHERCHE OPÉRATIONNELLE
Enoncé du problème

Le tableau suivant résume les données aérentes à ce problème de

production :
A B Disponible
m 1h 2h 8h
p 2 kg 2 kg 10 kg
q 9 kg 4 kg 36 kg
Prot unitaire 50 dh 60 dh

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

La construction d'un modèle linéaire

- Variables de décision : Notons par

x1 = la quantité du produit A à produire
x2 = la quantité du produit B à produire
Les variables x et x sont dites variables de décision.
1 2

- Fonction objectif :
- Pour le produit A, elle retire 50 dh par unité et en fabrique x 1

unités ; cette production lui rapporte donc un prot de (50x ) dh ;

1

- de même, la quantité x du produit B lui permet de faire un prot

2

de (60x ) dh.
2

Le prot total à tirer des deux produits s'élève donc à :

z = 50x1 + 60x2

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

La construction d'un modèle linéaire
Cette fonction z , qui traduit l'objectif de notre problème, s'appelle
fonction objectif ou fonction économique. Et comme nous
cherchons à rendre z aussi grand que possible, nous écrivons :
Maximiser z = 50x1 + 60x2
ou
Max z = 50x1 + 60x2
- Contrainte relative à la machine m :
Temps d'utilisation de m ≤ 8
Pour le produit A, le temps nécessaire à la fabrication de la
quantité x se calcul ainsi :
1

1 heure / (unité de A) ×x (unité de A) = x heures,

1 1

pour le produit B, on procède de façon analogue :

2 heure / (unité de B)×x (unité de B) = 2x heures
2 2

La contrainte relative à la machine m s'écrit donc :

x +x ≤8
1 2

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

La construction d'un modèle linéaire
- contraintes relatives aux matières premières :

2x 1 + 2x2 ≤ 10
9x 1 + 4x2 ≤ 36
- contraintes de positivité : Elles assurent que la solution ne
comporte pas des valeurs négatives (inacceptables).
x1 , x2 ≥ 0

Le modèle se résume ainsi :

Max z = 50x1 + 60x2


 x1 + 2x2 ≤ 8




(P) 2x1 + 2x2 ≤ 10

 9
 1
 x + 4x2 ≤ 36
x1 , x2 ≥ 0


FOUAD KISSI RECHERCHE OPÉRATIONNELLE

2) Généralisation : Problème de production

Soient m machines Mi ( i = 1, ....., m) qui fabriquent en série n

types de produits Pj ( j = 1, ...., n). La machine Mi a une capacité
maximum de bi unités de temps. La fabrication d'une unité du
produit Pj nécessite l'utilisation de la machine Mi durant aij unités
de temps.
Si cj représente le gain relatif à la production d'une unité du
produit Pj , la résolution du problème


 Max z = c1 x1 + c2 x2 + ..... + cn xn
a 11 x1 + a12 x2 + ..... + a1n xn ≤ b1 (M1 )




a21 x1 + a22 x2 + ..... + a2n xn ≤ b2 (M2 )


 ..... ......
a x + am2 x2 + ..... + amn xn ≤ bm (Mm )

 m1 1


x1 , x2 , ...., xn ≥ 0


FOUAD KISSI RECHERCHE OPÉRATIONNELLE

2) Généralisation : Problème de production

fournira les valeurs optimales des quantités xj à produire de chacun

des produits ; la fonction économique représente le gain total ; le
premier membre de chaque contrainte (Mi ) représente le temps
total d'utilisation de la machine Mi .

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

3) Formulation d'un problème de minimisation

Enoncé du problème : Un agriculteur souhaite que son troupeau

consomme la plus faible ration quotidienne de trois éléments
nutritifs A, B et C. Les exigences quotidiennes sont de 16 pour A,
12 pour B et 18 pour C. L'agriculteur achète deux types d'aliments
P et Q :
une unité de P comprend 2 unités de A, 1 unité de B et 1
unité de C ; et elle coûte 20 dh ;
une unité de Q comprend 1 unités de A, 1 unité de B et 3
unité de C ; et elle coûte 40 dh ;
L'agriculteur cherche la combinaison la moins coûteuse des
quantités de P et Q qui respectera l'exigence de consommation
minimale d'éléments nutritifs.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

2) Formulation d'un problème de minimisation

Le tableau suivant résume les données aérentes à ce problème :

P Q Besoins minimaux
A 2 1 16
B 1 1 12
C 1 3 18
Coût unitaire 20 dh 40 dh

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

La construction d'un modèle linéaire
Appelons x et x les quantités des aliments P et Q qu'il faut
1 2

chercher. L'objectif de l'agriculteur est évidemment de minimiser le

coût total des aliments qu'il faut acheter. Mathématiquement cela
s'écrit :
Minimiser z = 20x1 + 40x2
ou
Min z = 20x1 + 40x2
Pour les contraintes des 3 éléments nutritifs, on a :
2x1 + x2 ≥ 16 (A)
x1 + x2 ≥ 12 (B)
x1 + 3x2 ≥ 18 (C )

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

La construction d'un modèle linéaire

Enn, il faut pas oublier qu'on peut pas acheter des quantités
négatives de P ou Q :
x , x ≥0
1 2

Le modèle se résume ainsi :

 Min z = 20x + 40x

1 2

 2x + x ≥ 16


1 2

1x + x ≥ 12 2

x + 3x ≥ 18


 1 2

x , x ≥0


1 2

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

IV) Résolutions des programmes linéaires

Après la modélisation du problème, vient la recherche d'éventuelles

solutions. Et pour cela deux méthodes de résolution sont
proposées :
La méthode graphique privilégiée pour les programmes
linéaires à deux ou trois variables au maximum. Le cas de deux
variables se traite dans le plan et le cas de trois variables se
traite dans un espace à 3 dimensions.
La méthode générale du Simplexe (ou de Dantzig 1947 )
adaptée à tout type de problème linéaire même les plus
complexes ( des centaines de variables et des dizaines de
contraintes ).

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

DEUXIEME CHAPITRE

Méthode de Résolution Graphique (PL à Deux Variables)

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Introduction

Dans ce chapitre nous présentons une technique de résolution de

programme linéaire à deux variables x et x . Dans ce cas on peut
1 2

utiliser une représentation graphique du programme linéaire. La

formulation canonique d'un PL à deux variables peut s'écrire sous
l'une des deux formes suivantes :
 

 Max z = a0 x1 + b0 x2 
 Min z = a0 x1 + b0 x2
 a1 x1 + b1 x2 ≤ c1  a1 x1 + b1 x2 ≥ c1

 

(P) a2 x1 + b2 x2 ≤ c2 (D) a2 x1 + b2 x2 ≥ c2
..... ...... ..... ......

 

 
x1 , x2 ≥ 0 x1 , x2 ≥ 0

 


FOUAD KISSI RECHERCHE OPÉRATIONNELLE

I) Quelques rappels de géométrie

Equation d'une droite : L'expression : a x + a x = b (1)

1 1 2 2

est l'équation d'une droite (∆) qui a pour pente − aa12 (a 6= 0) et 2

qui passe par le point de coordonnées (0, ab2 ).

(1) s'écrit aussi : x = − aa21 x + ab2 .
2 1

Remarque : La droite (∆) sépare le plan (ox x ) en 2 demi-plans

1 2

d'équations : 
a1 x1 + a2 x2 < b
a1 x1 + a2 x2 > b
Exemple : (∆) : x + 2x = 4
1 2

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

I) Quelques rappels de géométrie

Ensemble convexe de Rn : Un ensemble D ⊂ Rn est convexe si :

∀x1 , x2 ∈ D, [x1 , x2 ] ⊂ D .

Résultat :Tout polygone convexe de R possède un nombre ni de

2

points extrémaux

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

II) Procédure de la méthode graphique

1 Réaliser un repère orthonormé (ox x ).

1 2

2 Tracer la région admissible (C) ( l'ensemble des solutions

possibles délimitées par toutes les contraintes du problème ).
3 Si (C) est borné, alors la solution optimale existe. Mais si (C)
est non borné, on distingue les deux cas suivants :
Si le problème est à maximiser, aucune solution.
Si le problème est à minimiser, une solution optimale existe.
4 Chercher tous les points sommets de (C) et parmi ceux-ci,
choisir le point ( ou les points ) qui rend l'objectif optimal par
deux méthodes :

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

II) Procédure de la méthode graphique

Méthode de recensement des sommets (Repérage analytique) :

comparer les valeurs de l'objectif correspondantes à chacun des
points sommets. La plus grande valeur réalise le maximum et
la plus petite valeur réalise le minimum.
Méthode des droites parallèles ( Repérage géométrique ) :
Désigner par z l'objectif et par (∆p ) la droite d'équation :
z = c1 x1 + c2 x2 = p

Ces droites (∆p , p ∈ R) sont les lignes de niveau de l'objectif.

Tracer (∆ ) ( pour p = 0, l'objectif vaut 0 ).
0

Déplacer parallèlement (∆ ) vers le point de (C) le plus

0

éloigné de l'origine en cas de maximisation ou vers le point de

(C) le plus proche de l'origine en cas de minimisation.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

III) Exemples d'application
1) Problème de maximisation

Enoncé du probème :
Une entreprise de fabrication de chassis envisage la production de
deux nouveau modèles au moyen des capacités de ses trois ateliers.
Il s'agit respectivement d'un chassis en aluminium et d'un chassis
en bois. Le premier produit nécessite le passage dans le premier
atelier pour fabriquer le cadre en aluminium et dans le troisième
atelier où le verre est monté sur le chassis. Tandis que le second
produit nécessite le passage dans le deuxième atelier pour fabriquer
le cadre en bois et dans le troisième atelier où le verre est monté
sur le chassis. Les prots unitaires, les temps de fabrication de
chacun des produits dans chacun des ateliers ainsi que les capacités
hebdomadaires de ces ateliers sont donnés au tableau suivant :

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

1) Problème de maximisation

Produit 1 Produit 2 Capacité disponible

(heures / produit) (heures / produit) (heures / semaine)
Atelier 1 1 0 4
Atelier 2 0 2 12
Atelier 3 3 2 18
prot 300 dh 500 dh
La question qui se pose est la suivante : " Combien faut-il produire
de chassis de chaque type par semaine an d'obtenir un prot
maximal ? "

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Le modèle linéaire

Quelles sont les quantités de chassis que l'entreprise devrait

produire par semaine, si elle veut maxmiser son prot ? Les
variables de décision seront :
x = le nombre de chassis de type 1 à produire par semaine
1

x = le nombre de chassis de type 2 à produire par semaine

2

Le problème de planication de la production de chassis se traduit

par le modèle linéaire suivant :
Max z = 300x1 + 500x2


 x1 ≤ 4 (A1)




(P) 2x2 ≤ 12 (A2)


 3 x1 + 2 x2 ≤ 18 (A3)
x1 , x2 ≥ 0



FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Construction de la région admissible

Toute inégalité est vériée par une moitié du plan

contrainte d'inégalité = demi - plan
frontière ( ou bord ) d'un demi plan = droite
Tracé du domaine admissible dans le plan
tracé la droite déni par chaque contrainte
région admissible = intersection de tous ces demi-plans.
Géométrie d'un PL : L'ensemble des solutions admissibles est
toujours un polyèdre.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Recherche d'une solution optimale

Dans le domaine admissible, on cherche une solution qui

maximise 300x + 500x
1 2

On trace la droite 300x + 500x = 0

1 2

La droite optimale est 300x1 + 500x2 =?

cette droite est donc parallèle à 300x1 + 500x2 = 0
idée visuelle : déplacer la droite 300x1 + 500x2 = 0
la faire glisser le plus possible dans le bon sens
c-à-d dans une direction qui augmente la valeur de la fonction
objectif 300x1 + 500x2
tout en restant dans le domaine admissible.
Optimum atteint au bord :
L'optimum de la fonction objectif, s'il existe, est atteint en ( au
moins )un sommet du polyèdre.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Recherche d'une solution optimale

L'optimum est atteint au point (x 1 , x2 ) = (2, 6) et la fonction

économique prend la valeur 3600
z = (300 × 2) + (500 × 6) = 3600

Ce point ce trouve à l'intersection des droites associées aux ateliers

2 et 3. On utilise à plein les capacités disponibles des ateliers 2 et
3. Par contre, pour cette solution optimale, les capacités
disponibles de l'atelier 1 seront plus que susantes.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Remarque

La région admissible peut être :

vide ( nombre de solutions optimales : 0 )
non vide et bornée ( nombre de solutions optimales : 1 ou ∞ )
non vide et non bornée ( nombre de solutions optimales : 0 ou
1 ou ∞ )

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

III) Exemples d'application
2) Problème de minimisation

Résoudre graphiquement le problème linéaire suivant :

Min z = 12x1 + 6x2


x1 + 2x2 ≥ 4



 3x1 + x2 ≥ 3
x1 , x2 ≥ 0



FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Recherche d'une solution optimale

La région admissible est convexe non borné donc une solution

optimale existe. Appliquons la méthode des recensements des
sommets, alors on a z(x , x ) = 12x + 6x
1 2 1 2

E (0, 3) → z(0, 3) = 18
1

E2 ( 52 , 95 ) → z( 52 , 95 ) = 78
5

E3 (4, 0) → z(4, 0) = 48
Alors c'est le sommet E2 ( 25 , 59 ) qui réalise l'objectif minimal de
valeur 78
5

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Exemple

Les contraintes suivantes

 2x1 + x2 ≤ 6


x1 ≥ 5
x1 , x2 ≥ 0


délimitent une région admissible vide.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

TROISIEME CHAPITRE

Algorithme du Simplexe (Méthode des tableaux)

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Introduction

Nous avons résolu des cas de programmes linéaires simples : deux

variables et trois ou cinq contraintes. Au fur et à mesure que le
nombre des contraintes s'accroît, la méthode graphique s'avère de
plus en plus dicile à mettre en ÷uvre. En présence de trois
variables, nous devons faire appel à une représentation graphique
dans l'espace, exercice très délicat..., Or, dans la pratique, les
programmes linéaires comportent plusieurs dizaines de variables et
de contraintes. Ainsi, le recours à une méthode générale devient
indispensable.
L'algorithme du simplexe est la plus utilisée des méthodes de
résolution des programmes linéaires. Il a été mis au point en 1948
par B. Dantzig.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

I) Formes canonique et standard d'un programme
linéaire

1) Notion de formes canoniques

Lorsque l'ensemble de contraintes se présente sous forme
d'inégalités ( ≥ ou ≤ ) on parle de forme canonique.
Toutefois, il convient de distinguer un programme canonique de
type I d'un programme canonique de type II.
Un programme canonique de type I est un programme dans
lequel les contraintes inégalités sont tournées dans le sens
inférieur ou égal, l'objectif recherché étant la maximisation de
la fonction économique.
Un programme canonique de type II a des contraintes
inégalités tournées dans le sens supérieur ou égal et l'objectif
est un minimum.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Exemples

Max z = 2x1 + 9x2 + x3 Min z = 2x1 + 9x2 + x3

 

 2x1 + 2x2 + 7x3 ≤ 10  2x1 + 2x2 + 7x3 ≥ 10


 


 

x1 + 3x3 ≤ 7 x1 + 3x3 ≥ 7
x + 17x2 + 15x3 ≤ 25 x + 17x2 + 15x3 ≥ 25

 

 1  1
 
x1 , x2 , x3 ≥ 0 x1 , x2 , x3 ≥ 0
 

Forme canonique de type I Forme canonique de type II

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

I) Formes canonique et standard d'un programme
linéaire

2) Formes standard
Toutes les contraintes représentent des égalités. L'objectif pouvant
être le maximum ou le minimum.
Exemples :
Max z = 2x1 + 9x2 + x3 Min z = x1 + 4x2 + x3
 

 2x1 + 2x2 + 7x3 = 10  2x1 + x2 + 7x3 = 9


 


 

x1 + 3x3 = 7 2x1 + 3x3 = 6
 x1 + 17x2 + 15x3 = 25  x1 + 7x2 + 5x3 = 20

 

x1 , x2 , x3 ≥ 0 x1 , x2 , x3 ≥ 0

 


FOUAD KISSI RECHERCHE OPÉRATIONNELLE

I) Formes canonique et standard d'un programme
linéaire

Soulignons enn que dans la méthode simpliciale, tout programme

se présentant sous forme canonique, doit être ramené sous la forme
standard avec introduction de variables d'écart ou articielles selon
le cas et selon les règles bien précises, ainsi que nous le verrons par
la suite.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

3) Introduction de variables d'écart dans la
méthode du simplexe

Forme canonique de type I Forme Standard Correspondante

Max z = 50x1 + 60x2 Max z = 50x1 + 60x2
 

 x1 + 2x2 ≤ 8  1 + 2x2 + x3 = 8

 

x

 

2x1 + 2x2 ≤ 10 2x1 + 2x2 + x4 = 10

 9x + 4x2 ≤ 36
 1


 9
 1
 x + 4x2 + x5 = 36
x1 , x2 ≥ 0 x1 , x2 , x3 , x4 , x5 ≥ 0
 

La variable d'écart d'une contrainte représente la quantité

disponible non utilisée. C'est l'écart entre la disponibilité et le
besoin.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

II) Algorithme du simplexe : Méthode des
tableaux

Principe :
1 Dresser la forme canonique du problème posé ;

2 Passer de la forme canonique à la forme standard en

transformant les inéquations en équations et en introduisant

les variables d'écart ;
3 Tableau initial : recherche de la solution extrême de base , les

variables d'écart sont considérées au départ comme variables

principales ou variables dans la base. Les variables réelles sont
non principales et se trouvent dans le hors base. La fonction
objectif est alors nulle.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Principe

Avec le tableau initial, on prépare le tableau N 1 en choisissant

respectivement la variable entrante, sortante et le pivot :
la variable entrante correspondant au coecient le plus élevé
dans la fonction économique. La colonne de la variable
entrante prend alors le nom de colonne pivot.
la variable sortante correspondra au plus petit rapport positif
issu de la division de la colonne second-membre par la colonne
variable-entrante. Cette variable sortante se lira dans la base et
sur la même ligne que le plus petit rapport positif. La ligne de
la variable sortante prend le nom de ligne pivot.
le pivot se trouvera à l'intersection de la ligne pivot et de la
colonne pivot.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Principe

Il s'agira ensuite de rendre la colonne pivot unitaire, c-à-d, d'arriver

à un pivot égal à 1 et tous les autres éléments de la même colonne
pivot égaux à zero jusqu'à la fonction économique ( dernière ligne ).
- Pour obtenir la ligne du pivot transformée, il sut de diviser tous
ses éléments par le pivot.
- Pour transformer les autres éléments des autres lignes ou colonnes,
on utilise la règle du rectangle, c-à-d, la démarche suivante :
4) On construit les diérents tableaux jusqu'à ce que la fonction
économique ne contienne plus que des nombres négatifs ou nuls. Le
pivot ne peut jamais être égal à zéro.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Exemple d'application

Résoudre le programme linéaire suivant à l'aide de la méthode

pratique des tableaux :
Max z = 3x1 + 2x2


x1 + 5x2 ≤ 11



2x + 3x2 ≤ 5
 1
x1 ≥ 0, x2 ≥ 0



FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Forme standard

La forme standard du programme est

Max z = (3x1 + 2x2 + 0x3 + 0x4 )


x1 + 5x2 + x3 11


=

2x + 3x2 + x4
 1
= 5
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0



FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Tableau initial : Solution extrême de base

Le premier tableau de simplexe est

B x x x x Constantes constantes / x
1 2 3 4 1

x3 1 5 1 0 11 11
x4 2 3 0 1 5 5
2

z 3 2 0 0 0
Solution :
HB : x = x = 0
1 2

B : x = 11 , x = 5
3 4

z=0
Comme deux nombres de la dernière ligne sont positifs (3, 2), cette
solution de base réalisable n'est pas optimale.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Tableau initial : Solution extrême de base

D'après la procédure de détermination de la variable entrante et

celle sortante, on a,
1x entre en base ( plus grand coecient positif de z )
4x sort de base ( plus petit rapport positif b/x )
1

Dans le premier tableau nous avons entouré le pivot qui est égal à 2
par un petit cercle

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Tableau N 1 : 1 ère itération

Construisons donc le deuxième tableau de simplexe

B x x x x 1 2Constantes
3 4

x 3 0 1 − 7
2
1
2
17
2

x 1 1 0 3
2
1
2
5
2

z 0 − 0 − 5
2
− 3
2
15
2

Comme tous les nombres de la dernière ligne sont négatifs ou nuls,

la solution obtenue
x = ,x =0,x =
1
5
2 2 et x = 0 , est optimale et la valeur
3
17
2 4

maximale de z est 15
2

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Partie II : LA THEORIE DES GRAPHES

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

INTRODUCTION

" Un petit dessin vaut mieux qu'un grand discours "

Napoléon

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

INTRODUCTION

La représentation d'un problème par un dessin, un plan , une

esquisse contribue souvent à sa compréhension. Le langage des
graphes est construit, à l'origine, sur ce principe. Nombres de
méthodes, de propriétés, de procédures ont été pensées ou trouvées
à partir d'un schéma pour être ensuite formalisées et développées.
Chacun d'entre nous a, au moins une fois , vu ou utilisé un plan
d'un roman, une carte de ligne ferroviaires, un plan électrique, un
organigramme d'entreprise. Ainsi tout le monde sait plus ou moins
intuitivement ce qu'est un graphe.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

PREMIER CHAPITRE

Eléments de théorie de graphe

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Qu'est-ce qu'un graphe ?

Denition
Un graphe est la donnée d'un ensemble de X de n éléments
(X = {x , ....., xn }) et d'une relation R liant ces éléments. On note
1

ce graphe : G (X , R).

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

I) Eléments terminologiques

Sommets : Les éléments xi (i = 1, ...., n) de X s'appellent les

sommets du graphe.
Arcs, Arrêtes : La relation entre deux sommets (xi , xj ) du
graphe est soit :
Un arc si elle est orientée ( à sens unique ) : xi → xj . Où xi est
l'extrimité initiale et xj est l'extrimité nale ( ou terminale ).
Une arrête si elle n'est pas orientée ( à deux sens ) : xi ↔ xj .

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

I) Eléments terminologiques

Graphe orienté : Un graphe dont toutes les relations sont des

arcs est appelé graphe orienté (en général, de la gauche vers la
droite ).
Graphe valué : Un graphe où l'on indique sur ses arcs et ses
arrêtes des valeurs numériques est dit graphe valué. Ces
valeurs peuvent représenter des quantités, des durées, des
coûts, ou des distances...

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

II) Représentations d'un graphe

Il existe plusieurs représentations d'un graphe, on cite les plus

utilisées :
1) Représentation sagittale : Le graphe G (X , R) est schématisé
graphiquement par un ensemble ni de sommets
(xi ∈ X , i = 1, ...., n) reliés entre eux par des arcs ou des arrêtes.
exemples : 1)
2) Soient x , ....., x six villes d'une région et dont les liaisons
1 6

routières sont représentées par le graphe suivant :

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

2) Représentations matricielle

Le graphe G (X , R) est représenté sous forme d'une matrice

booléenne ( ne contenant que 0 ou 1 ) d'ordre n telle que :
1 est aecté au couple (xi , xj ) s'il existe une relation directe de
xi vers xj .
0 est aecté au couple (xi , xj ) s'il n'existe aucune relation
directe de xi vers xj .

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Exemple

Le graphe donné dans l'exemple 1 s'écrit sous la forme matricielle :

x1 x2 x3 x4 x5 x6
x1 0 1 1 0 0 0
x2 0 0 1 0 0 0
x3 0 0 0 1 1 0
x4 0 1 1 0 1 1
x5 0 0 0 1 1 0
x6 0 0 0 0 0 0
Remarque : Pour les graphes valués, une semblable matrice peut
être construite à partir des valeurs inscrites sur les arcs et les
arrêtes.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

3) Représentation sous forme de dictionnaires

Les dictionnaires permettent d'exprimer la matrice booléenne d'un

graphe d'une autre façon. Plusieurs types de dictionnaires existent :
- Dictionnaire des précédents
- Dictionnaire des suivants
Exemple : La représentation matricielle du graphe précédent permet
de dégager les dictionnaires des précédents et des suivants :
Sommets Précédents Sommets Suivants
x
1 - x 1 x ,x 2 3

x2 x1 , x4 x2 x3
x3 x1 , x2 , x4 x3 x4 , x5
x4 x3 , x5 x4 x2 , x3 , x5 , x6
x5 x3 , x4 , x5 x5 x4 , x5
x6 x4 x6 -

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

III) Chemins d'un graphe

Un chemin est une succession d'arcs tels que l'extrémité nale de

l'un soit l'extrémité initiale du suivant. La longueur d'un chemin est
égale au nombre d'arcs qui le composent.
Exemple : Un des chemins du graphe précédent :
La longueur de ce chemin est égale à 4

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

III) Chemins particuliers

Chemin simple : Passe une fois au plus par chacun des arcs
( Exemple : (x , x , x )).
1 2 3

Chemin eulérien : Passe une seule fois par chacun des arcs
Circuit, Cycle : Chemin dont l'extrémité initiale du premier arc
coïncide avec l'extrémité nale du dernier ( Exemple :
(x , x , x , x )). Si les arcs sont des arrêtes, on parle de cycle.
2 3 4 2

Boucle : Arc dont l'extrémité nale coïncide avec l'extrémité

initiale ( Exemple : (x , x )) ou circuit ( ou cycle) de longueur
5 5

1.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Niveaux d'un graphe

Le niveau d'un sommet est le nombre d'arcs qui le séparent de

l'origine du graphe par le chemin le plus long.
La recherche des niveaux se fait à partir du dictionnaire des
précédents suivant la démarche ci-dessous :
1 Niveau 1 : contient les sommets qui n'ont pas de précédents (

ce sont des entrées du graphe ).

2 Niveau suivant : supprimer les sommets déjà classés ( du

niveau précédent ). Les sommets de ce niveau sont ceux dont

tous les précédents sont supprimés.
3 Répéter la même procédure (2) jusqu'à ce que tous les

sommets soient classés.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Exemple

Sommets Précédents
A Aucun - - -
B A - - -
C A - - -
D B, C B, C - -
E D D D -
F D D D -
G D D D -
H E, G E, G E, G E, G
I E E E E
J I I I I
Niveaux N = {A}
1 N2 = {B, C } N3 = {D} N4 = {E , F , G } N

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Remarques

1 Les niveaux d'un graphe permettent de rendre la

représentation sagittale plus claire et sans redondance.
2 Un sommet sans suivant n'est pas nécessairement du dernier
niveau ( les sommets F et H ).
3 Un sommet sans suivant est une sortie du graphe ( le sommet
J).

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

DEUXIEME CHAPITRE

Problèmes d'ordonnancement

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

1) Objectifs

L'ordonnancement a pour but principal l'étude de la réalisation des

projets ( objectifs économiques ) tout en permettant :
de déterminer le meilleur temps de réalisation ;
d'organiser ( ordonner ) l'ensemble des travaux ( tâches ou
opérations ) qui concourent à cette réalisation et d'indiquer
ceux qui ne peuvent être retardés sans mettre en cause la durée
du projet ( établir un calendrier ou planing pour les tâches ) ;
d'optimiser les ressources et les moyens utilisés pour la
réalisation du projet .

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Notion de projet

Un projet est un ensemble de tâches ou opérations a, b, c, d...

permettant d'atteindre un objectif xé, lesquelles tâches sont
elles-mêmes soumises à un certain nombre de contraintes telles
que :
les contraintes potentielles (relatives au temps ) ;
les contraintes disjonctives ;
les contraintes cumulatives.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Contraintes potentielles

Contraintes d'antériorité ( ou de postériorité ) : une tâche ne

peut débuter qu'après une autre ne soit achevée ( on ne peut
construire qu'après avoir obtenu le permis de construction ).
Contraintes de localisation temporelle : une tâche ne peut
commencer qu'à une certaine date xée ( la date du début
d'une tâche est xée d'avance par son exécuteur qui ne sera
disponible qu'en cette date ).

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Contraintes disjonctives

Elles impose l'impossibilité de la réalisation simultanée de deux

tâches ( une même et unique machine exécute deux tâches
diérentes, donc nécessairement pas en même temps ).

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Contraintes cumulatives

Elles concernent la disponibilité dans le temps des diérents

facteurs de la réalisation du projet ( le nombre d'exécutants du
projet est limité ).

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Notion de tâche

Une tâche ou activité est une opération . L'ensemble des tâches

forme le projet. On peut donc la dénir comme étant l'unité ou
l'élément d'un projet. On associe à chaque tâche sa durée et une
contrainte d'antériorité par rapport aux autres tâches. C'est ainsi
qu'on dira que A est immédiatement antérieure à B si B ne peut
débuter que lorsque A est achevée.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Exemple

Pour la construction d'un entrepôt on énumère 10 tâches reliées

entre elles par des contraintes d'antériorité :
Tâches Précédentes Durée approx/semaines
A. Plans Aucune 2
B. Obtention de permis A 2
C. Achat des matériaux A 6
D. Fondation B, C 5
E. Murs D 2
F. Electricité D 3
G. Divers D 6
H. Toiture E, G 2
I. Peinture E 2
J. Pose d'une alarme I 1

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Remarque

Avant la recherche de toute solution d'un problème

d'ordonnancement, il faudra d'abord commencer par une phase
préliminaire d'analyse du projet et de ses contraintes et pour cela, il
faut :
Préciser l'objectif du projet ;
identier les diérentes tâches élémentaires nécessaires pour
atteindre cet objectif ;
évaluer par estimation pour chaque tâche, la durée, le coût et
les moyens nécessaires à sa rálisation ;
déterminer les contraintes qui peuvent peser sur les tâches ( de
type potentiel , cumulatif ou disjonctif ).

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Méthode d'ordonnancement

C'est un ensemble de méthodes qui permettent au responsable du

projet de prendre des décisions nécessaires dans de meilleures
conditions possibles. Un telle méthode doit donc permettre :
d'anlyser le projet en profondeur, c-à-d le décomposer en
tâches ;
de mettre sur pied un plan d'action contribuant à réaliser ledit
projet tout en respectant les contraintes ;
et enn, de contrôler le bon déroulement du projet.
Par conséquent, une méthode d'ordonnancement n'est ni plus ni
moins qu'un problème d'organisation du projet.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Diagramme de Gantt

A tout problème d'ordonnancement, on peut associer un

diagramme dit de Gantt où chaque tâche est représentée par un
segment qui commence au plus tôt et de longueur proportionnelle à
la durée de la tâche.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Conclusion

On n'a pas intérêt à retarder les tâches critiques car cela

retardera d'autant le projet.
Les tâches non critiques peuvent être retardées dans la limite
de leur marge totale sans remettre en cause la durée totale
minimale du projet.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

La méthode d'ordonnancement PERT

La méthode de PERT (Programm Evaluation and Review Technic)

connue aussi sous l'appellation de méthode des potentiels-étapes,
est d'origine américaine conçue vers 1958 pour la réalisation de la
fusée Polaris.
Dans son contexte le plus simplié, la méthode PERT ne tient
compte que des contraintes potentielles.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

3.1) Représentation sagittale d'un graphe PERT

L'ensemble des tâches est représenté par un graphe orienté et valué

sans boucle et sans circuit, dont les principes sont :
Sommets : étape ou évenement qui représente le début ou la
n d'une ou de plusieurs opération.
Arcs : Un arc d'un graphe représente dans la méthode PERT
une tâche ou une opération. Une tâche est délimitée par deux
sommets ( ou événements ) qui représentent le début et la n
de la tâche. Une tâche est une activité qui consomme du
temps, nécessite des ressources physiques et des dépenses.
valeur sur l'arc : temps opératoire de la tâche.
Exemple :

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

3.1) Représentation sagittale d'un graphe PERT

Dans un graphe d'ordonnancement PERT , on doit respecter les

conventions suivantes :
Les sommets sont numérotés de 1 à n ;
le sommet ( numéro 1 ) qui débute les travaux n'est terminal à
aucun arc ;
le sommet indiquant la n des travaux, n'est initial à aucun
arc ;
toute autre sommet doit être extrémité initial et nal en même
temps ;
le numéro d'un sommet initial d'un arc doit être inférieur à
celui de son sommet nal ;
les arcs associés à des tâches distinctes ne peuvent avoir à la
fois même sommet initial et même sommet nal.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

3.2) Problèmes de la représentation sagittale d'un
graphe PERT

Tâches successives : Pour indiquer que la tâche A est prédécesseur

immédiat de la tâche B, l'arc correspondant à B prend son départ
là où aboutit l'arc associé à A.
Tâches simultanées : les tâches qui peuvent être exécutées en
même temps, elles partent du même sommet : deux tâches A et B
qui commencent en même temps se représentent ainsi :
Tâches convergentes : les tâches qui sont prédécesseurs immédiats
de la même tâche, vont vers un événement commun : deux tâches
A et B qui précédent le même événement se représentent ainsi :

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

3.2) Problèmes de la représentation sagittale d'un
graphe PERT

Tâche ctives :
On recourt parfois à l'introduction de tâches ctives ( représentées
par des arcs ctifs en pointillées ) pour bien respecter les
contraintes réellement.
Exemples :
1) C et B succède A, D succède B et C : dans ce qui suit, la
première représentation ne respecte pas la dernière convention
sus-citée et nécessite une modication par ajout d'une tâche ctive
F.
2) C et D succède A, D succède B : la première représentation qui
suit, ne traduit pas correctement la réalité puisqu'on n'a pas la
contrainte C succède B. Pour remédier à cela , on introduit une
tâche ctive F qui supprime cette contrainte du graphe.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

3.2) Problèmes de la représentation sagittale d'un
graphe PERT

Tâche ctives :
3) A débute le projet, B peut s'eectuer en 2 périodes après le
commencement du projet. On introduit une tâche ctive de durée 2
dont l'extrémité initiale de l'arc correspond à l'événement "début
de projet" et son extrémité nale correspond à l'événement "début
de la tâche B" :
Tâche fractionnaires :
Si une tâche peut commencer au cours de la réalisation d'une autre
tâche, il faut la fractionner en deus tâches successives.
Exemple :
B succède A 3 péroides après le commencement de A et A dure 7
périodes : on subdivise la taâche A en deux tâches A et A de
1 2

durée respectives égales à 3 et 4.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Exemples de construction du graphe PERT

Exemple 1 :
La réalisation d'un ouvrage se décompose en 8 tâches reliées entre
elles par des conditions d'antériorité :
Tâches Précédentes Durée /jours
A Aucune 3 jours
B Aucune 4 jours
C A 4 jours
D B 2 jours
E A 6 jours
F C,D 2 jours
G B 4 jours
H F, G 1 jours

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Exemples de construction du graphe PERT

Niveaux des tâches

N = {A, B} , N = {C , D, E , G }, N
1 2 3 = {F } , N4 = {H}

Graphe de PERT

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

R±olution par la méthode PERT : Recherche de
chemins critiques

La méthode PERT permet une résolution sur le graphe PERT.

Pour cela on doit inscrire en chaque sommet, en plus du numéro
(N) de l'événement, la date au plus tôt et la date au plus tard
correspondantes de la manière suivante :
1) La date au plus tôt d'un événement :il s'agit de la date avant
laquelle une tâche ne peut démarrer. C'est donc la date attendue de
réalisation d'un événement ou date avant laquelle un événement ne
peut se réaliser.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

R±olution par la méthode PERT : Recherche de
chemins critiques

On note par : E = entrée du du réseau-PERT ; S = sortie du

réseau-PERT
On aecte à l'entrée, la date tE = 0
Pour un sommet j , on calcule la date au plus tôt (tj ) en posant :
tj = max{ti + dij }

avec
i = antécédent de j
dij = durée de l'arc (i,j)
ti = date au plus tôt du sommet i
tj = date au plus tôt du sommet j
tS = durée minimum de l'ouvrage

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Exemple 1

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

R±olution par la méthode PERT : Recherche de
chemins critiques
2) La date au plus tard d'un événement : c'est la date limite de
réalisation d'un événement. Si l'événement venait, en eet, à se
réaliser après ladite date, le projet tout entier ne pourrait jamais se
réaliser dans le délai correspondant à la longueur du chemin
critique.
Pour calculer la date au plus tard, on peut adopter, entre autres
raisonnements, la méthode suivante :
inversion de l'orientation de tous les arcs du graphe ;
avec ce nouveau graphe, on calcule les dates au plus tôt ( les
rôles de l'entrée et de la sortie sont inversés ) ;
les dates au plus tard sont alors obtenues par diérence entre
la durée minimum du projet et les dates ainsi calculées comme
le montre le graphe inversé ci-dessous

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

R±olution par la méthode PERT : Recherche de
chemins critiques

3) Chemin critique : dans un graphe PERT est tout chemin reliant

le sommet initial (entrée) et le sommet nal ( n projet ) dont la
valeur est maximale. C'est le chemin dont la durée totale coïncide
avec le temps minimum nécessaire pour la réalisation du projet. Il
est composé exclusivement de tâches critiques, c-à-d celles dont
l'exécution ne doit pas être retardée . Ce chemin passe par les
sommets dont les dattes au plus tôt et au plus tard coïncident.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Exemple 1

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

R±olution par la méthode PERT : Recherche de
chemins critiques

4) Les marges :
On appelle marge d'une tâche le retard qu'il est possible de tolérer
dans la réalisation de celle-ci, sans que la durée optimale prévue du
projet global en soit aectée. Il est possible de calculer trois types
de marges : la marge totale, la marge libre et la marge
indépendante ( ou certaine ).
4.1) La marge totale : d'une tâche Tij indique le retard maximal
que l'on peut admettre dans sa réalisation ( sous réserve qu'elle ait
commencé à sa date au plus tôt ) sans allonger la durée optimale
du projet. 0
Mt = tj − ti − dij

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

R±olution par la méthode PERT : Recherche de
chemins critiques
4.2) La marge libre : d'une tâche Tij indique le retard que l'on peut
admettre dans sa réalisation ( sous réserve qu'elle ait commencé à
sa date au plus tôt ) sans modier les dates au plus tôt des tâches
suivantes et sans allonger la durée optimale du projet.
Ml = tj − ti − dij

4.3) La marge indépendante ( certaine ) : est le retard maximum,

que l'on peut apporter à son démarrage sans perturber la date de
réalisation au plus tôt de l'événement suivant, bien que l'événement
précédent n'ait été réalisé qu'à sa date limite.
Mi = max[0, (tj − ti − dij ]
0

D'après cette formule, la marge indépendante est considérée

comme nulle lorsque son calcul donne un nombre négatif.
FOUAD KISSI RECHERCHE OPÉRATIONNELLE
TROISIEME CHAPITRE

Problèmes de transport

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Introduction

Un réseau de transport à n sommets est un graphe valué, orienté

sans boucle et dont :
un sommet est une entrée au graphe ( sans précédent ) et un
sommet est une sortie du graphe ( sans suivant ) ;
les autres sommets sont les n÷uds du réseau ;
les arcs (xi , xj ) sont des liaisons entre les sommets adjacents
ayant pour valeurs associées νij .

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

1) Problème du chemin optimal : Algorithme de
Ford

Dans ce cas, les valeurs νij associées aux arcs (xi , xj ) peuvent
représenter des coûts de transport, des distances ou aussi des
durées entre les extrémités xi et xj .
Il s'agit d'aller de l'entrée jusqu'à la sortie du graphe par le chemin
le plus court ( c'est à dire en un minimum de temps ou de
distances ou avec un coût minimal ) ou le plus long.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

1-1) Méthode de résolution de chemin minimal :
Algorithme de Ford

1 Numéroter les sommets du graphe dans un ordre quelconque

avec x l'entrée et xn− la sortie.
0 1

2 A chaque sommet xj , aecter la valeur αj du chemin minimal

de l'entrée x à xj tel que :
0

 α =0

0

α = min(αi + νij ), i parcourt les indices de tous les sommets

 j
pr cdents de xj
3 αn est la valeur du chemin minimal de x à xn−
0 1

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Exemple

On veut se rendre de la ville A à la ville F le plus rapidement

possible. Les diérentes communications et distances ( en km )
entre ces villes représentées dans le graphe suivant :

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

1-2) Méthode de résolution de chemin maximal :
Algorithme de Ford

1 Numéroter les sommets du graphe dans un ordre quelconque

avec x l'entrée et xn− la sortie.
0 1

2 A chaque sommet xj , aecter la valeur αj du chemin minimal

de l'entrée x à xj tel que :
0

 α =0

0

α = max(αi + νij ), i parcourt les indices de tous les sommets

 j
pr cdents de xj
3 αn est la valeur du chemin maximal de x à xn−
0 1

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Exemple

Déterminer le chemin maximal du graphe suivant ( A est l'entrée et

I est la sortie du graphe ) par l'algorithme de Ford :

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

2) Problème de ot maximal : Algorithme de Ford
- Fulkerson

Dans ce cas, les valeurs νij associées aux arcs (xi , xj ) représentent
les capacités maximales de transport entre les extrémités xi et xj .
Il s'agit de maximiser les ots ou les ux qui circulent dans le
réseau entre l'entrée E et la sortie S compte tenu des capacités de
transport.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Dénitions

1 Le ot est la quantité réelle qui circule sur le réseau et ne peut

dépasser la capacité des arcs.
2 Une chaîne est une suite ordonnée d'arrêtes.
3 Un chemin ou une chaîne de E à S est saturé si au moins un
de ses arcs est saturé ( le ot circulant dans l'arc atteint sa
capacité maximale).
4 Le ot est complet si tous les chemins de l'entrée à la sortie
sont saturés.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Méthode de résolution : Algorithme de Ford -
Fulkerson

Principe
1 La somme des ots qui partent de E est égale à la somme des
ots qui arrivent à S
2 Principe de conservation : en chaque n÷ud du réseau les ots
entrants sont égaux aux ots sortants.
3 Le ot est maximale si toutes les chaînes du réseau sont
saturées.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Méthode de résolution : Algorithme de Ford -
Fulkerson

Algorithme
1 Choix d'un ot au hasard : faire passer un ot entre l'entrée E
et la sortie S compte tenu des capacités maximales de
transport.
2 Recherche d'un ot complet : améliorer ce ot de façon à ce
que tout chemin allant de E à S comprenne au moins un arc
saturé. Et pour cela, il faut saturer l'arc qui possède le
minimum des capacités résiduelles de tous les arcs du chemin
non saturé.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Méthode de résolution : Algorithme de Ford -
Fulkerson
Algorithme
3 Détermination du ot maximal : améliorer ( augmenter ou
diminuer ) le ot complet s'il existe une chaîne non saturée de
E à S.
recherche des chaînes non saturées par la méthode de
marquage :
i) marquer l'entrée E d'un signe (+) ;
ii) marquer l'extrémité initiale xi d'un arc (xi , xj ) dont le ot
est non nul et dont l'extrémité nale xj est marquée. On
marque avec (−xj ).
iii) marquer l'extrémité nale xj d'un arc non saturé (xi , xj ) et
dont l'extrémité initiale xi est marquée. On marque avec (+xi ).
Condition d'arrêt : Si l'on ne peut pas marquer la sortie S,
alors il n'existe aucune chaîne non saturée et le ot est
maximal, l'algorithme s'arrête.
Si non, c'est à dire S est marquée, alors on passe à l'étape
suivante.
FOUAD KISSI RECHERCHE OPÉRATIONNELLE
Méthode de résolution : Algorithme de Ford -
Fulkerson

Algorithme
Amélioration du ot dans la chaîne non saturée :
i) Calculer la capacité résiduelle minimale CRM des arcs
orientés dans le sens du graphe.
ii) Calculer le ot minimale FM des arcs orientés dans le sens
inverse du graphe.
iii) Soit C = min(CRM, FM)
iv) Ajouter la valeur C à tous les arcs orientés dans le sens du
graphe et retrancher la valeur C à tous les arcs orientés dans le
sens inverse du graphe
4 Reprendre l'étape 3 : jusqu'à ce que l'algorithme s'arrête à une
certaine itération.

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Exemple

Soit à maximiser les ots circulant dans le réseau suivant compte

tenu des capacités de transport :

FOUAD KISSI RECHERCHE OPÉRATIONNELLE

Merci pour votre attention

FOUAD KISSI RECHERCHE OPÉRATIONNELLE