UNIVERSITE AUBE NOUVELLE

UFR Sciences et Technologies

2e année Licence IT
Année Académique 2024-2025

COURS DE RECHERCHE OPERATIONNELLE

Dr METCHEBON TAKOUGANG Stéphane Aimé

metchebon@[Link]

[Link]@u‐[Link]

1
COURS DE RECHERCHE OPERATIONNELLE (RO)

Introduction

Chapitre I : Programmation linéaire

Chapitre II : Méthode du simplexe

Chapitre III : Dualité et algorithme dual

Chapitre IV : Problème d’ordonnancement

2
COURS DE RECHERCHE OPERATIONNEL (RO)

Introduction

Chapitre I : Programmation linéaire

Chapitre II : Méthode du simplexe

Chapitre III : Dualité et algorithme dual

Chapitre IV : Problème d’ordonnancement

1
INTRODUCTION

La RO est une discipline dont l’objectif est d’aider les gestionnaires et les décideurs à mieux
prendre des décisions dans les situations complexes grâce à l’utilisation des méthodes
scientifiques, en particulier des modèles mathématiques.

L’environnement de la RO est constitué de l’économie :

- pour la définition des problèmes

- et de l’informatique
- pour l’obtention des solutions

Entrée
économique
Sortie
software RO
Modèle
mathématique

Contenu de la RO

La RO peut traiter des problèmes d’application très divers parmi les plus classiques on peut
citer :

- La gestion de la production au niveau de l’entreprise ou de l’atelier

- gestion des stocks ;
- gestion des transports ;
- des tournées de distribution et de ramassage ;
- planification d’activité sur un horizon de temps (ordonnancement) ;
- le choix d’investissement et de la gestion du personnel

2
Chapitre 1 : PROGRAMMATION LINEAIRE

Définition 1.1

.
Une optimisation sous contrainte est un programme mathématique sous la forme :

≤ = ,..,
étant la fonction à optimiser et les étant constantes

est linéaire sur ℝ ∀ , ∈ ℝ, ∀ , ∈ ℝ + = +

Par définition on a une programmation linéaire si et la fonction sont linéaires

= .." $
. %& & + %' ' + ⋯+ % ) * +,) -./0 ,% ., 1 ,é% 3) 4) &, ', … ,

ou %& , %' , … , % ∈ℝ
#

=6 + 67 7 + ⋯+ 6 89 : é6 ;8
est appelée fonction économique.

1.1. Formulation générale du problème

< , = = 1, . . , , .,* 1) ?%3 %01) 4+ @3.01è/). ., +@@. ) B+C .,% , ?%3 %01).
D< , = = 1, . . , , .,* 1) -.) - ),* % )-*é %+ <
Exemple : %& & %& = -E )* & = E
F) -.,*3% ,*) .,* ,4) é = , . . , G %?)- H -.,*3% ,*) 4′ ,éJ%1 *é
< , = 1, . . , / )* = = 1, . . , , sont des coefficients respectifs des variables < au niveau des

K , = 1, . . , / sont des contraintes réelles.

contraintes.

Toutes les variables et paramètres étant définies et nous avons la formulation générale
suivante :
QRST U D D éD G HW8
O
< <

O <V

O
O U < =K W; = , … , H LM
LM <
P
O U < <≤K W; = H + , … , G LM7
O <
O
O < ≥ W; < = , . . ,
N < HW8:D HW8 W; < = + , . . , LMY

3
Remarque 1.1
On peut ramener FG sous la forme canonique suivante
QG U D<
O
<
O <V

PU < < ≥ K ∀ = ,…,G

O
O <V
N < ≥ ∀< = , . . ,

En effet
- pour FG1 on a l’écriture équivalente suivante :
QU * ≥ 4Z Q U* ≥ 4Z
O ZE E
O ZE E

U *ZE = 4Z ⟺ ⟺
E E

P P
E

OU *ZE E ≤ 4Z OU *ZE ≥ −4Z

E
E
N E N E
- pour FG2 on a l’écriture équivalente suivante :
QU * ≥ 4Z Q U* ≥ 4Z
O ZE E
O ZE E

U *ZE = 4Z ⟺ ⟺
E E

P P
E

OU *ZE E ≤ 4Z OU *ZE ≥ −4Z

E
E
N E N E

E = /% ^0, E ` E = /% ^0, − E ` = −
pour FG3 on a l’écriture équivalente suivante :
] a ] a
-
E E E

min 2 & + 3 '

Exemple

2 &+ '≥1
b
− &+3 ' ≥2
& ≥0 ' ≤0

-& = 2 -' = 3
avec

*&& = 2 *&' = 1
*'& = −1 *'' = 3
4& = 1 4' = 2

Posons ' = '] − 'a ou ' = h − i .

Nous aurons la forme (FC) suivant :

min 2 & + 3 h − 3 i
Q2 + − ≥1
O & h i
− &+3 h−3 i ≥ 2
P &≥0
O h ≥ 0
N i≥0

4
Remarque 1.2
Résoudre
Q/ , U - Qmax − U -
O O
E E E E
O EV& O EV&
est équivalent à resoudre
P U *ZE E ≥ 4Z ∀ = 1, . . , / P − U *ZE E ≤ −4Z , ∀ = 1, . . , /
O
O EV& O
O EV&
N E ≥ 0 ∀= = 1, . . , , N E ≥ 0 ∀= = 1, . . , ,

1.2. Formulation canonique

Partant de FG, le principe est de se ramener à des inégalités au niveau de toutes les contraintes.
La nouvelle forme obtenue est appelé forme canonique (FC)

QG U D<
O
<
O <V
Lw
PU < < ≥ K ∀ = ,..,G
O
O <V
N <≥ ∀< = , . . ,

1.3. Formulation vectorielle

La formulation vectorielle est la suivante :

RST wy | = , × 1 Vecteur à n dimension

x zy ≥ K
y≥ ~ = 1 × , Vecteur ligne à n dimension
où

• = / × , Matrice / × , à m lignes et n colonnes

4 = / × 1 Vecteur colonne à m dimension

1.4. Forme standard

contraintes quitte à introduire une variable d’écart 8 (variable d’écart associée à la contrainte
Partant de la formulation générale, le principe est de se ramener à des égalités au niveau des

i).
Ainsi

U *ZE E ≤ 4Z 4.,,)3% U *ZE E + {

Z = 4Z
EV& EV&
De même pour le cas

5
U *ZE E ≥ 4Z ., %+3% U *ZE E − {
Z = 4Z {
Z ≥0
EV& EV&
De la formulation générale on obtient la forme standard suivante :

Q RST U D
O
< <
O <V

PU < < = K ∀ = ,…,G

O
O <V
N < ≥ ∀< = , . . ,

min ~|
La formulation vectorielle associée à la forme standard est :

x•| = 4
|≥0

1.5. Exemples de formulation

1.5.1. Problème de production

On dispose de 4 machines pour la fabrication de 5 produits. Les temps d’utilisation des
machines sont donnés dans les tableaux suivants :
P1 P2 P 3 P 4 P5 Le temps maximum d’utilisation des machines est
M1 4 - 2 - 4
•‚‚
donné par le vecteur

4 = €„‚‚†
ƒ‚‚
M2 2 3 - - 3
…‚‚
M3 3 - 1 4 -
M4 - 5 4 2 -

Le rendement pour les produits est donné par (100 ; 75 ; 50 ; 25 ; 50).

On demande combien de produits de chaque type faut-il fabriquer de façon à
maximiser le gain de la production tout en ne dépassant pas le temps d’utilisation
des machines.

Corrigé (formulation du problème)

Soit la quantité des produits de type fabriqués = ,…,‡

max 100 & + 75 ' + 50 h + 25 i + 50 •

On a
Q 4 + 2 + 4 ≤ 500
O & ' •
2
O & + 3 ' + +3 • ≤ 800
O3 & + h + 4 i ≤ 700
O
5 ' + 4 h + 2 ih ≤ 900
P &≥0
O '≥0
O h≥0
O
O i≥0
N •≥0

6
1.5.2. Problème de mélange ou de régime alimentaire
Le problème de régime alimentaire est celui de trouver une combinaison de produit
alimentaire qu’il soit le plus moins chère possible mais qui renferme tous les éléments

Les différents aliments sont indexés par <, < la quantité de l’aliment < et D< le coût de
nutritifs nécessaires.

l’aliment <.

U D< < 3)@3é ),*) 1) -.û* *.*%1 4) 1 C ), )/01) 4) %1 /),* =

<V

représente les éléments nutritif = , … , G

Il faut minimiser le coût sous les contraintes.

< représente la teneur en éléments nutritifs de l’aliment <

K représente la quantité minimale d’éléments nutritifs contenue dans le régime
alimentaire. Ainsi le problème du régime alimentaire se présente comme suit :

Q RST U D
O
< <
O <V

PU < < ≥ K ∀ = ,…,G

O
O <V
N < ≥ ∀< = , . . ,

1.6. Présentation générale d’un problème de programmation linéaire

1.6.1. Pour minimiser le coût des actions

Qmin U -
O
E E
O EV&
Ž. ~
PU *ZE E ≥ 4Z , = 1, … , /
O
OEV&
N E ≥ 0 ∀= = 1, . . , ,
Où

= représente les activités de production

représente les produits fabriqués

*ZE représente le taux de production de @%3 =

E représente le niveau de fonction de =
-E représente le coût unitaire de =
4Z représente la quantité minimale à produire de

1.6.2. Pour optimiser (maximiser) le rendement d’une production

7
 Q max U -
O
E E
O EV&
Ž. ~
PU *ZE E 4Z , 1, … , /
O
OEV&
N E X 0 ∀= 1, . . , ,
Où

4Z représente la quantité disponible

représente le produit consommé

= représente l’activité qui consomme la matière première

*ZE représente le taux de consommation de @%3 =
E représente le niveau de fonctionnement de =
-E représente le rendement unitaire de =

1.7. Propriétés fondamentale de la programmation linéaire

min • ~|
Soit le problème linéaire suivant : x •| X 4
|X0

|∈ , ) * %@@)1é ) @%-) 4) 4é- ., | • ." ‘)

!

..
#

&
'

Posons ’ “y / zy X K, y X •
D est appelé ensemble de solution admissible
Propriété 1.1

’ est un polyèdre convexe fermé borné (poly tope). C’est le plus petit ensemble convexe
Résoudre

qui contient un nombre fini de points.

Un hyperplan dans un espace de dimension n est un sous espace de dimension n-1.

– est une intersection d’un nombre fini de demi-espace fermé

Si nous sommes dans un espace de dimension 2 les hyperplans sont des droites.

U *ZE E 4Z ) * +, — @)3@1%,
EV&

U *ZE E X 4Z
EV&

8
 1- – peut-être un polyèdre convexe non borné
Deux cas particuliers peuvent se produire :

2- – peut-être un ensemble vide

max 6 & 5 '

Exemple : Résoudre graphiquement
Q 8
O & '
\2 & 3 ' 6
P &\ ' 2
O
N &X0 'X0

–& : & '\8 0

Il revient à tracer les droites suivantes :

–' : \2 & 3 ' 6

–h : & \ ' 2
–i : & 0
–• : ' 0
On pose š 6 & 5 ' (*)
–› : \•
› œ
' & •
–„ : \•
›
' &

D5
D1
D7

D4

D2

D3

• –& ∩ –' nous donnons la valeur maximale de M

8 5
• & ; ' tel que : & '
⇔ &
) * 1% .1+* ., 4+ @3.01è/) )*
&\ ' 2 & 3
š 6 } 5 5 } 3 30 15 45 ¡ ¢‡

9
Graphiquement le couple & ; ' qui permet d’avoir la valeur de M la plus grande
possible est le point I point d’intersection des droites –& )* –' .
1- On cherche le couple & ; ' appartenant au poly tope D qui rende la valeur de M
la plus grande possible dans (*)
; candidats sont suivant la direction ’£ : \‡
¤
2- Tous les couples 7 7 . On
se déplace sur D suivant la direction ’£ l’ordonnée à l’origine de la droite de
direction –„ nous donne la valeur maximale de
œ
•

Propriété 1.2
La solution du problème est la solution admissible qui donne la petite valeur de la fonction
optimale (fonction économique). La fonction économique, géométriquement est une
direction d’un hyperplan. Trois cas peuvent se présenter dans la recherche de la ou des
solution(s) :
a) La solution optimale est unique et c’est un sommet de D ;
b) Si il y a une infinité de solutions optimales, ce sont les points d’une face de D ;
c) Il peut arriver que la solution optimale soit à l’infinie c'est-à-dire le cas non borné
(D1 non borné).

Remarque : Si D est égale à l’ensemble vide, il n’y a pas de solution.

Propriété 1.3 : Caractérisation d’un sommet d’un polyèdre convexe

RST ¥ wy
Cette méthode n’est applicable qu’à la forme standard

x zy K
yX
Et sous l’hypothèse supplémentaire que ;6 z G c'est-à-dire pas de contrainte
inutile avec G ¦

2 & 2 ' 1
§ & ' 2
\
&
& ' '
Dans ce exemple n=2 (nombre de variable) et m=3 (nombre de contrainte).
Le nombre de contrainte ne doit pas dépasser celui des variable

Une base est une matrice ¨ G } G issue de T tel que ;6 z G c'est-à-dire que B
Définition

est inversible.
Choix de B
« ®
ª -
z ª -
ª -
© ¬
n=nombre de colonne noires et bleues
m=nombre de colonne bleues

10
colonnes. Le nombre maximal de base de rang m que l’on peut extraire dans T est wG
On choisit m vecteurs colonnes linéairement indépendants parmi ces n vecteurs

,…,
Soient , ∈ ¯ ù |¯| = G
Soit Ti les n vecteurs colonnes

Le reste des vecteurs est noté ou < , < ∈ ² ù |²| = − G

Les en bleus sont appelés vecteurs de base et i indice de base.

En fait les forment une base de ℝ³ qui est l’espace des contraintes. A chaque base B,
on associe une solution de base de la façon suivante :

RST ¥ = w¨ y¨ + w´ y´
Q
O y¨ = ∈ ¯ = variable de base
y´ = ^ < ` < ∈ ² = variable hors base
P
Ozy = K ⇔ ¨y¨ + ´y´ = K
N y≥

On pose y´ =
La solution de base associée sera :

y´ =
La solution de base X¹ est admissible ssi y¨ ≥
y¨ = ¨a . K
Solution de base

CONCLUSION
Les solutions de bases admissibles représentent le sommet du polyèdre T.

Exemple

max 6 & + 5 '

Considérons l’exemple précédent i.e.

Q + ≤8
O & '
−2 & + 3 ' ≤ 6
P &− '≤2
O &≥0
N '≥0

max 6 & + 5 '

Forme standard avec introduction des variables d’écarts
Q + + =8
O & ' h
1 1 1 0 0
−2 & + 3 ' + i = 6
• = €−2 3 0 1 0† 4 = º›»
ƒ
P & − + = 2
' •
1 −1 0 0 1 '
O &≥0
N '≥0

Le nombre de base est wY‡ = = = =

‡! ‡×¢×Y! 7
‡aY !×Y! 7!×Y! 7

Q |½ = ¾ ¿ = 0
i
O •
&
P|À = € ' † = Á a& . 4
O
1- Posons la solution de base

N h

11
 1 1 1
−2 3 1 1 1 1
Á& €−2 3 0† 4)*Á& = 1 × −1 &]h
  + 0 × −1 ']h
  + 0 × −1 h]h
 Â
1 −1 1 −1 −2 3
1 −1 0

K8 ¨ = − ≠

1
Á& a& = . •3%, @. é 4) ~./Á&
4)*Á&

3 0 −2 0 −2 3
  −   Â
−1 0 1 0 1 −1 0 0 −1 0 −1 −3
Æ 1 1 1 1 1 1 É
~./Á& = Å−Â Â Â Â −Â Â È = €−1 −1 2 † •3%, @. é ~./Á& = € 0 −1 −2†
−1 0 1 0 1 −1
1 1 1 1 1 1 −3 −2 5 −1 2 5
Ä Â 3 0Â − Â−2 0Â Â
−2 3
ÂÇ

1 1 0 −1 −3 0 −1 −3
Á& a& = . •3%, @. é 4) ~./Á& ⇒ Á& a& = × € 0 −1 −2† = −1 × € 0 −1 −2†
4)*Á& −1
−1 2 5 −1 2 5

0 1 3
Á& a& = €0 1 2†
1 −2 −5

Q |½ = ¾ ¿ = 0 ⇔ = =0
i
O
i •
•
&
P|À = € ' † = Á a& . 4 ⇔ |À = Á& a& . 4
O
Solution de base

N
!
h

0 1 3 8 0×8+1×6+3×2 0+6+6 12
|À! = Á& a& . 4 = 0 1 2 $ 6$ = 0 × 8 + 1 × 6 + 2 × 2$ = 0+6+4 $= 10 $
1 −2 −5 2 1×8−2×6−5×2 8 − 12 − 10 −14

7
y¨ = $ C
89 69 W 8 9 :W K8 Ë698 6KG 99 Ë:8 D6; y¨ ≥
− ¢

x&
Q XÌ = ¾x ¿ = 0
O '
xh
PX¹ = €xi † = Ba& . d
O
2- Posons la solution de base

N x•
1 0 0
&]& Â1 0 ']& Â0 0 h]& Â00
Á' = €0 1 0† 4)*Á' = 1 × −1 Â + 0 × −1 Â + 0 × −1 Â
0 1 0 1 1 0
0 0 1

K8 ¨7 = ≠

1
Á' a& = . •3%, @. é 4) ~./Á'
4)*Á'

1 0 0 0 0 1
  −   Â
0 1 0 1 0 0 1 0 0 1 0 0
Æ 0 0 1 0 1 0É
~./Á' = Å− Â Â Â Â −Â ÂÈ = €0 1 0† •3%, @. é ~./Á' = €0 1 0†
0 1 0 1 0 0
0 0 1 0 1 0 0 0 1 0 0 1
Â
Ä 1 0 Â − Â Â Â ÂÇ
0 0 0 1
1 1 1 0 0 1 0 0 1 0 0
Á' a& = . •3%, @. é 4) ~./Á' ⇒ Á' a& = × €0 1 0† = 1 × €0 1 0† = €0 1 0†
4)*Á' 1
0 0 1 0 0 1 0 0 1

12
 Q |½ ¾ ¿ 0⇔ = =0
&
O
& '
'
h
P|À = € i † = Á a& . 4 ⇔ |À = Á' a& . 4
Solution de base
O "
N •
1 0 0 8 1×8+0×6+0×2 8+0+0 8
|À" = Á' a& . 4 = 0 1 0$ 6$ = 0 × 8 + 1 × 6 + 0 × 2$ = 0 + 6 + 0$ = 6$
0 0 1 2 0×8+0×6+1×2 0+0+2 2
Î
y¨7 = ¤$ 89 W 8 9 :W K8 Ë698 6KG 99 Ë:8 D6; y¨7 ≥
7

13
Chapitre 2 : METHODE DU SIMPLEXE

L’algorithme du simplexe se divise en 3 grandes parties :

- L’itération ;
- L’initialisation
- L’arrêt.
L’itération : elle consiste à passer d’une base admissible à une autre base admissible
meilleure (c'est-à-dire qui donne une meilleure valeur de la fonction économique). On
effectue un changement de base si cette condition est respectée.
L’initialisation : elle consiste à trouver une base admissible () ou à conclure que D={}
au cas où il n’y a pas de base admissible.
L’arrêt : la condition d’arrêt est déterminée si la solution optimale est finie auquel cas
on a un sommet du polyèdre pour solution c'est-à-dire la solution optimale est non
bornée.

2.1. Itération et arrêt

Tout se fait dans un tableau appelé tableau simplexe. Ledit tableau est obtenu après
une transformation du problème en une forme équivalente.

Le principe de transformation consiste à :

- Diagonaliser les contraintes avec un coefficient 1 sur les diagonales ;

- Pouvoir lire immédiatement la valeur de la fonction économique sur le tableau.

Ainsi on aura :

En rappel

RST ¥ wy
x zy K
yX

~ ~À ~½ , ~À 1 × / , ~½ ^1 × , − / `

•= ÁÏ , Á /×/ , Ï /× ,−/

|À
|= º », |À = / × 1 |½ = ,−/ ×1
|½

|
•| = 4 ⇔ Á Ï × º À » = 4 ⇔ Á|À + Ï|½ = 4
|½

|
D’où min • = ~| = ~À + ~½ º À » = ~À |À + ~½ |½ = ~À Á a& 4 − Á a& Ï|½ + ~½ |½
|½

min • = ~À Á a& 4 − ~À Á a& Ï − ~½ |½ en résumé le problème (2-1) devient

14
 RST ¥ w¨ ¨a K \ w¨ ¨a ´ \ w´ y´
§ y¨ ¨a ´y´ ¨a K
yX

On construit le tableau simplexe à partir de cette transformation

y´ <

¥ %‚‚ %‚E

y¨ %Z‚ X 0 %ZE

6 < coefficient des variables hors base dans la fonction économique

termes indépendants

6 valeur des variables base

CONDITION d’arrêt

(à compléter)

2.2. Propriétés

Si %ÐE 0 ∀= ∈ Ñ alors on une solution optimale finie.

Propriété 2.1

15
 ∃ Ó ∈ Ñ: %‚Ô Õ 0 )* %ZÔ 0 ∀ ∈ • alors on une solution optimale à l’infinie.
Propriété 2.2
Si

Résumé :

2- Examiner les %ÐE , = ∈ Ñ deux cas peuvent se présenter :

1- Ecrire le tableau simplexe pour la base admissible ;

• Si %ÐE 0 ∀= ∈ Ñ stop solution optimale finie

• Sinon choisir %ÐÔ *)1 B+) %ÐÔ max %ÐE , = ∈ Ñ /%ÐE Õ 0

%‚‚ %‚Ô Õ 0
%Z‚ %ZÔ
Ö %ÖÔ Õ 0

- Si %ZÔ 0 ∀ ∈ • stop solution optimale à l’infinie

le coefficient aâá positif est appelé
×ØÙ ÛÜÝ ×ßÙ
×ØÚ Ü∈Þ / ×ßÚ à‚ ×Üá
- Sinon on pose
pivot.

2.3. Règles pour le changement de base admissible

Quatre règles sont essentielles pour le changement de base :

Règle 1- Elle concerne le coefficient à la place du pivot ;

1
Règle 2- Elle concerne les coefficients sur la ligne du pivot sauf celui-ci
%ÖÔ
∗
aâá
%
%ÖE = ∈ Ñ \ “Ó• “0•
∗ ÖE
%ÖÔ
%ZÔ
∈ • \ “1• “0•
Règle 3- Elle concerne les coefficients sur la colonne du pivot
%ZÔ
∗
\
%ÖÔ

%ZÔ } %ÖE
Règle 4- Elle concerne tous les autres coefficients (règle des rectangles)
%ZE
∗
%ZÔ \
%ÖÔ

Exemple :

max 6 & 5 ' min \6 & \ 5 '

Considérons l’exemple précédent i.e.

Q 8 Q 8
O & '
O & '
\2 & 3 ' 6 \2 & 3 ' 6
⇔
P &\ ' 2 P &\ ' 2
O & X 0 O &X0
N 'X0 N 'X0

Introduisons des variables d’écart h, i, •

16
 min −6 & − 5 '
Q + + =8
O & ' h
O −2 & + 3 ' + i=6
O &− '+ •=2
& ≥0
P '≥0
O ≥0
O h
O i≥0
N •≥0

1. Ecrire le tableau simplexe pour la base admissible ;

& '
0 6 5
h 8 1 1
i 6 -1 3
• 2 1 -1

2. Examiner les aäå , j ∈ J deux cas peuvent se présenter :

• Si %ÐE ≤ 0 ∀= ∈ Ñ stop solution optimale finie (non vérifié)
• Sinon choisir %ÐÔ *)1 B+) %ÐÔ = /% %ÐE , = ∈ Ñ /%ÐE > 0
%ÐÔ = -.1.,,) &
= Ü∈Þ / × le coefficient aâá positif est appelé
×ÙÙ ÛÜÝ ×ßÙ
×ØÚ ßÚ à‚ ×Üá
- Sinon on pose
pivot. Le pivot =1 case colorée

Application des règles

• '
-12 -6 11
h 6 -1 2
i 10 2 1
&
Exemple application règles des rectangle 11 = 5 − &
›×a&
2 1 -1

• '
-45 -1/2 -11/2
h 3 -1/2 ½
i 7 -1/2
&
= 5, = 3, =7
5 ½
D’où solution optimale finie avec & ' i

La valeur de fonction économique avec min = -45 et avec max = 45

2.4. Initialisation

L’objectif c’est de construire une première base admissible. Pour cela on utilise la
technique des variables artificielles qui est applicable à toute matrice T quelconque.

variables dans P on obtient un autre problème appelé èé avec une matrice

Principe : soit P le problème à traiter en introduisant des éléments artificiels i,e des

17
• é *)1 B+) 3J • é / ¦ , et cette condition est une condition d’existence d’une base
admissible initiale.

On résout le problème èé et de cette solution on déduira les solutions du problème

initial P

P èé *)1 B+) 3J • é /¦,

∋ une base admissible

algébrique simplex

Solution optimale à l’infinie Solution optimale à l’infinie

ï.1+* ., .@* /%1) , )

ð
è3.01è/) /@. 01)
Solution optimale finie

RST ¥ wy
ê x zy X K 9W 98 K X
yX

é
Dans chacune des contraintes, on introduit une variable artificielle Z

U *ZE E
é
Z 4Z , | é é
Z /}1
EV&

On aura une matrice • é •, •4 , / ?%3 %01) de • é ., %

| 0
Á¾ ¿ B+ %4/ 01)
|é 4

• On introduit M qui représente un nombre aussi grand qu’on veut appeler big

G
M tel que

QRST ¥ wy ¡ U 6
O
ê6 V
9W 98 K X
P zy ¯Ky6 K
O yX
N y6 X

Si • ↘ \∞ )* š ↗ ∞ et on a les solutions de P qui sont à l’infinie

Si ê6 a une solution optimale finie, on a deux cas :

- Les variables artificielles sont toutes égales à zéro. ce qui entraine

- On a une variable artificielle positive dans la base. La solution est impossible
on ne peut pas trouver une solution de base.

18
Exemple

Soit le problème P sous la forme standard avec des variables d’écarts h, i, •

min • = −6 & − 5 '

Q
&+ '− h =8
O
−2 & + 3 ' + i = 6
P &− '+ • =2
O & 0, ' ≥ 0, h ≥ 0
≥
N i ≥ 0, • ≥ 0

La base ( h , i, •) n’est pas admissible car h = −8, @.+3 & = ' = 0.

èé sera alors

min • = −6 & − 5 ' + š

Q
›
+ '− h+ ›=8 1
O &
−2 & + 3 ' + i = 6
P &− '+ • =2
O & ≥ 0, ' ≥ 0, h ≥ 0
N i ≥ 0, • ≥ 0, › ≥ 0

On a une base initiale ( › , i, •) qui est admissible.

En tirant la valeur de › dans (1) on a la forme suivante de la fonction économique :

min • = 8š − 6 + š & − 5+š ' −š h

On a donc le Tableau simplexe

• › h
0 0 -M 0
& ' h -45 -1/2 -11/2 11/2
'
8M M M -M 3 -1/2 1/2 -1/2
i
0 6 5 0 7 5/2 -1/2 1/2
› 8 1 1 -1 & 5 1/2 1/2 -1/2
i 6 -2 3 0
• 2 1 -1 0
• › i
0 0 -M 0
• ' h -122 -28 0 -11
'
6M -M 2M -M 10 1 0 1
h
-12 -6 11 0 14 5 -1 2
› 6 -1 2 -1 & 12 2 0 1
i 10 2 1 0
& 2 1 -1 0

D’où la solution du problème (P) est : & = 12 )* ' = 10 Donc la valeur optimale de la
fonction économique du problème P est • = −122.

Remarque :

19
Si on a problème de maximisation alors on aura :

Rñò ¥ wy RST ¥ \wy

x zy X K ⇒ x zy X K
yX yX

1. %‚E X 0 ∀= ∈ Ñ → ï*.@ solution optimale finie < ∞ (on suppose que %Z‚ ≥ 0 ∀ ∈ •)
2. ∃Ó ∈ Ñ *)1 B+) %‚Ô < 0 )* %ZÔ ≤ 0 ∀ ∈ • → on a une solution optimale à l’infinie
3. ∃Ó ∈ Ñ *)1 B+) %‚Ô < 0 )* ∃ ∈ • *)1 B+) %ZÔ > 0 alors on choisit
%‚Ô = min %ÐE / %‚E < 0 a une solution optimale à l’infinie

On pose éôõ = min é ÷Ù / %ZÔ > 0 et on a un pivot. Le tableau simplexe s’obtient avec les
é é
ôö ÷ö
mêmes transformations que précédent.

2.5. Dégénérescence et cyclage

=
é÷õ éøÙ
on dit qu’une solution de base est dégénérée si il existe une solution de base avec une

é÷ö éøö
variable de base nulle. C’est ce qui arrive quand on a c'est-à-dire que la ligne l
et la ligne p donne le même résultat et on ne sait pas laquelle choisir. En fait c’est
intersection de trois contraintes et si on ne fait pas attention on tourne rond et
l’algorithme n’avance pas : c’est le cyclage.

= )*
é÷! Ù é÷" Ù é÷! ! é÷" !
La solution à ce problème est la suivante :

é÷! ö é÷" ö é÷! ö é÷" ö

Si on compare alors on perd le plus petit rapport

= )*
é÷! ! é÷" ! é÷! " é÷" "
é÷! ö é÷" ö é÷! ö é÷" ö
Si on compare alors on perd le plus petit rapport

Ô
%‚‚ %‚& %‚' … %‚Ô
%&‚ %&& %&' %&Ô

% Z! ‚ > 0 % Z! & > 0 % Z! ' > 0 % Z! Ô > 0

. .

% Z! ‚ % Z" & > 0 % Z" ' > 0 % Z" Ô > 0

. .

20
Chapitre 3 : Dualité et algorithme dual

[Link] du Primal en Dual

La dualité a trois intérêts :

1- Un intérêt lié à l’interprétation économique ;

2- Un intérêt lié à des propriétés mathématiques ;
3- Il est pratique et surtout algorithmique.

L’algorithme dual a un intérêt sur le simplexe : il est surtout utilisé en programmation

linéaire en nombre entier.

On appelle primal le problème linéaire de base (celui qu’on doit résoudre). Soit le primal
suivant :

Q RST U D
O
< <

O <V

O
OU < < X K ,…,H
<V
P
OU < < = K = H + , … , G
O <V
O
O <≥ < = ,…,
N < HW8:D HW8 < = + , … ,

Convention importante :

Au niveau des contraintes si on a un problème en min alors « ≥ » au niveau des

contraintes. Si on a un problème en max alors on a « ≤ » au niveau des contrainte dans
les cas on peut avoir en plus l’égalité « = »

Le principe de la dualité c’est d’associer au problème linéaire un autre problème linéaire

(avec moins de variable appelé dual).

Le problème primal précédent donne le dual suivant qui peut être caractérisé de dual
général. On a des variables duals suivants :

W , = ,…,G

21
 G
Q Rñò U K W
O
O V
O W X ,…,H
O W HW8:D HW8 = H + , … , G
G
PU <W ≤ D< < = , … ,
OV
OG
O
OU <W = D< < = + ,…,
NV

Si le primal est min alors le dual est max et vice versa

G
Primal Dual

RST U D< < Rñò U K W

<V V

U < < ≤K = ,…,H W ≥ = ,…,H

<V

U < < =K = H + ,…,G W HW8:D HW8 = H + , … , G

<V
G

< ≥ < = ,…, U <W ≤ D< < = , … ,

V
G

< HW8:D HW8 < = + ,…, U <W = D< < = + ,…,

V

Exemple

min 7 & − 4 ' + 5 h min 7 & − 4 ' + 5 h

Q − + 3 − ≤ −1 Q −3 '+ h ≥1
O & ' h
O &
2 & + h = −4 2 & + h = −4
→
P &≥0 P &≥0
O ' ≥ 0 O '≥0
N h B+)1-.,B+) N h B+)1-.,B+)

1 −3 1
+& , +' • = ¾ ¿
0 2 1
Dual

22
 max +& \ 4+'
Q+ X 0
O
&
+' B+)1-.,B+)
O ' max +& \ 4+'
O Q+ X 0
O U *Z' +Z 7 O &
ZV& +' B+)1-.,B+)
P '
P +& 7
OU *Zh +Z \4 O \3+& 2+' \4
O ZV& N +& +' 5
O '
O U *Zh +Z 5
N ZV&

Pour la forme canonique du primal, on a un dual particulier

RST ¥ wy Rñò ù ú. K
Primal Dual

zy X K úX
yX zú w

On a une symétrie

+ +& , +' , … . , +³ • /}, ~ 1}, 4 /}1

Pour la forme standard du primal on n’a pas de symétrie

RST ¥ wy Rñò ù ú. K
Primal Dual

zy X K ú HW8:D HW8
yX úz w

Propriétés mathématiques

Soit | une solution admissible du primal et soit û une solution admissible du dual
Propriété 1

Alors ~| X û ü4 on obtient une borne inferieure de la fonction économique du primal et

une borne supérieur de la fonction économique du dual

Soit | une solution admissible du primal et soit û une solution admissible du dual
Propriété 2

telque ~| û4 alors | )* û sont des solutions optimales.

Propriété 3
Si le primal a une solution optimale à l’infinie alors le dual est impossible. Si le dual une
solution optimal à l’infinie alors le primal est impossible.

23
Si le primal a une solution optimale finie |ý, •̂ ~|ý alors le dual a une solution optimal
Propriété 4

finie û, 4û de plus •̂ ~|ý 4û.

Théorème des écarts complémentaire :

A l’optimum (on a solution optimale finie), dans chaque couple de contraintes liées par
la dualité, au moins une des contraintes est serrée.

Definition : on dit qu’une contrainte est serrée si on a une égalité au niveau de ladite
contraintes.

24
 [Link] du Primal en Dual

[Link] du Primal en Dual

[Link] Dual

① ûÀ Á ~À )* ② ûÀ Ï ~½

ûÀ est une intersection de n contrainte comme pour le primal

ûÀ ∈ ⇔ ûÀ • ≤ ~ ⟺ ûÀ Á + Ï ≤ ~À + ~½

⇔ ûÀ Á+ûÀ Ï ≤ ~À + ~½

ûÀ Á ~À
⟺
ûÀ Ï ~½

La deuxième contrainte implique que ~À Áa& Ï\ûÀ Ï ~À ~½

Alors dire que ûÀ est admissible pour le problème dual revient à dire que %‚E 0. On applique
le simplexe pour résoudre le problème sauf que l’on part de %‚E ≤ 0 et on fait évoluer jusqu'à
%Z‚ ≥ 0

%‚E ≤ 0

%‚E ≤ 0
%Z‚ ≥ 0

25
 on choisit la base de telle sorte qu’elle soit une base admissible i.e.

Géométriquement la solution de base admissible est un sommet de D.

Une solution de base non admissible n’est pas un sommet de D mais une intersection des
contraintes. L’algorithme dual procède de sommet d base non admissible en sommet de base
non admissible jusqu’à rencontrer un sommet de base admissible et c’est la solution optimale.

Au niveau du tableau simplexe on a cette situation à l’optimum

%‚E 0
%Z‚ ≥ 0
Le bleu on solution dual

Le rouge on a un primal admissible

3.4.3 Algorithme dual dans la pratique

[Link] Initialisation

Construire une première base dual admissible

On peut éventuellement utiliser la technique des variables artificielles. Si on n’y arrive

pas c’est que le problème dual est impossible. Donc la solution

[Link] Itération

On évolue de base dual admissible en base de dual admissible du point de vue de H

1- Tester si Tapez une équation ici.

2- ∃1 ∈ • / %Z‚ < 0
% %ÖZ ≥ 0 ∀= ∈ Ñ ⇒

%‚E ≤ 0
%&‚

%Z‚ < 0 %Ö& ≥ 0

0 ∃= ∈ Ñ /%ÖZ < 0 %1.3 ., -ℎ. * 1 1) @1+ @)* * / %Ö‚ = / ,%Z‚ ∈ •, %Z‚ < 0
On pose éÙö = / , º é » < 0 6: 89 :8
é éÙ E
ôö ô éô
Remarque : on un pivot 6: ¦ et on a les mêmes formules pour le changement
de base que le simplexe.

[Link] Arrêt

Solution optimale finie pour le primal entraine une solution optimale finie pour le dual.
La solution est impossible pour le primal entraîne une solution impossible pour le dual

26
Exemple :

Q
h X6
min • = 6 & + 3 ' + 2
O
h
& '
2 &−2 h ≥ 9
.3/) *%,4%34 ,*3.4+ ., 4)+ ?%3 %01) 4C é-%3* ., %:
P &≥0
O '≥0
N h ≥0

Les coefficients des variables de base sont toujours positifs

Q\ \ \ \6
min • = 6 & + 3 ' + 2 h
O & ' h i
−2 & + 2 h + • = −9
i, •
P &≥0
Variable de base
O ' ≥0
N h ≥ 0, i ≥ 0 , • ≥ 0

1- Il faut utiliser la méthode du variable artificielle

2- On a une solution dual admissible : utilisation algorithme dual

Solution de base i = −6 • = −9

& ' h
0 -6 -3 -2
i -6 -1 -1 -1
• -9 -2 0 2

• ' h
27 -3 -3 -8
i -3/2 -1/2 -1 -2
& 9/2 -1/2 0 -1

• i h
63/2 -3/2 -3 -8
' 3/2 1/2 -1 2
& 9/2 -1/2 0 -1

=' , = ', = 0, 1% ?%1)+3 .@* /%1) ) * •̂ =

La solution est
… h ›h
& ' h '

27
 Chapitre IV
4.1. Notion sur la théorie des graphes

4.1.1 Définition

Soit deux ensembles A et B et des éléments x et y tel x ∈ A et y ∈ B. Toute partie G de A×B est un graphe;
ce graphe est défini par une correspondance F entre A et B tel que

= / ∈ , ∈ . La relation F défini un graphe orienté. F(x) est l'image de x par F. Cette

image peut ne pas exister. En R.O, les ensembles A et B sont généralement finis et confondu.

4.1.2 Les différentes représentations d'un graphe

= = , , , ,

[Link] Tableau de correspondance

Les relations → sont représentées dans un tableau.

Xi F(xi)
X1 X1,x2,x5
X2 X3,x4
X3 X5
X4 -
X5 X4,x1

[Link] Représentation graphique

Un graphe peut être représenté par un ensemble de sommet xi relié par des arcs fléchés.

1
2

3
5
4
La disposition des sommets dans le plan peut être quelconque même la longueur des arcs.

[Link] Représentation algébrique

Si X désigne l'ensemble des sommets alors = , , , , . Un arc peut être défini par le couple
(xi,xj). Si on appelle U l'ensemble des arcs de notre exemple, alors
= , , , , , ; , , , ; , ; , , ,

Le graphe peut s'exprimer par G=(X,U). L'arc (x1,x1) est une boucle.

[Link] Représentation matricielle

Un graphe peut être représenté par une matrice booléenne. Le 1 dans la case signifie que l'arc (xi,xj) existe.

X1 X2 X3 X4 X5
X1 1 1 0 0 1
X2 0 0 1 1 0
X3 0 0 0 0 1
X4 0 0 0 0 0
X5 1 0 0 1 0

4.2 Dictionnaire d'un graphe

Considérons l'arc (xi,xj). xi est un sommet immédiatement antérieur à xj est appelé un précédant de xj. Le
sommet xj qui suit immédiatement xi est appelé un suivant de xi.

Pour la construction et l'analyse d'un graphe, il important de connaitre l'ensemble des suivants ou des
précédant d'un graphe.

4.2.1 Dictionnaire des suivants

Soit S(xi) l'ensembles des suivants de xi défini par la relation F. Le dictionnaire des suivants donne pour
chaque sommet xi la liste de ses suivants.

Dans notre exemple, nous avons le dictionnaire des suivants comme suit :

xi S(xi)
x1 x1,x2,x5
x2 x3,x4
x3 x5
x4 -
x5 x4,x1

4.2.2 Dictionnaire des précédents

Soit P(xi) l'ensemble des précédents de xi défini par la relation F. Le dictionnaire de précédents donne pour
chaque sommet l'ensemble de ses précédents.

xi P(xi)
x1 x1,x5
x2 X1
x3 x2
x4 x2, x5
x5 x1,x3

4.2.3 Chemin dans un graphe orienté

Un chemin dans un graphe orienté est une suite non vide d'arc qui permet d'aller d'un sommet du graphe à
un autre sommet du graphe.

Dans notre exemple supposons que nous voulions nous rendre du sommet x1 au sommet x4.

= , , ,
 = , , ,

= , , , , , , ,

, et sont des chemins satisfaisant au problème.

Un circuit est un chemin qui revient à son point de départ. Dans notre exemple, on a:

= ,
!
= , , , , , , ,

Par simplification, on peut noter :

=
!
= , , ,

4.2.4 Niveaux des sommets d'un graphe orienté sans circuits

Le classement par niveau des sommets d'un graphe orienté sans circuit permet l'ordonnancement de ses
sommets et facilite la construction de ce graphe.

Soit les sommets x d'un graphe dont les antérieurs sont les suivants:

x Sommets précédents Col1 Col2 Col3

antérieurs
1 3,4,6 4 4 4 .
(on élimine 3 et 6 car ils
précèdent 4)
2 1,3,6,7 1,7 1,7 1,7 1
3 - - - - -
4 3,5,6 3,6 6 . -
5 - - - - -
6 5 5 . - -
7 6 6 6 . -

Travail à faire :

1. Déterminer le dictionnaire des précédents

2. Déterminer le graphe
3. Ordonnancer les sommets du graphe en niveau
4. Retracer le graphe en utilisant l'ordonnancement par niveau

Solution :

1. Dictionnaire des précédents (voir tableau précédant)

2. Dessin du graphe
 2

1 3

4 6

3. Ordonnancer les sommets du graphe consiste à mettre en évidence les sommets de départ puis
progressivement les sommets qui suivent dans l'ordre fixé par la relation x F(x) qui défini le
graphe fixé G=(X,U). Cet ordonnancement s'effectue à partir du dictionnaire des précédents.

Le niveau de départ est N0 = {3,5} parce que ces sommets n'ont pas de précédents. Dans la colonne 1 on
reporte les sommets après élimination des points 3 et 5.

Le niveau suivant N1 correspond aux sommets qui deviennent sans précédents après ces éliminations. N1 =
{6}

Dans la colonne 2 on élimine le sommet 6. Les points 4 et 7 constituent le niveau 2 donc N2 = {4,7}.

Dans la colonne 3 on élimine les sommets 4 et 7. Le point 1 constitue le niveau 3 donc N3 = {1}. Dans la
colonne 3, il ne reste plus que le sommet 2 avec un précédant. Donc N4 = {2}

4. L'ordonnancement par niveau des sommets permet un dessin plus lisible. Les dessins vont de la
gauche vers la droite.

3 4 1

6 7 2
5

4.3 Chemin optimal dans un graphe orienté sans circuit et sans boucle

4.3.1 Graphe valué

Un graphe est valué lors qu'a tout a du graphe est associé une valeur. Communément appelé longueur
cette valeur représente une pondération correspondant au problème à traiter. Elle peut représenter une
distance, un point ou des unités monétaires. La liste n'est pas exhaustive.

Soit un graphe orienté sans circuit et sans boucle G=(X,U) et soit u=(xi,xj) un arc. u ∈ U et xi,xj ∈ X. La
longueur de l'arc u est noté aij=a(u).

4.3.2 Longueur d'un chemin

La longueur lik d'un chemin quelconque permettant de se rendre d'un sommet i à un sommet k non
consécutif de i est égale la sommet des longueurs des arc que comprend ce schéma.

4.3.3 Recherche d'un chemin optimal

L'utilité d'un graphe est la recherche d'un chemin optimal pour se rendre d'un point à un autre. Ce chemin
optimal peut être soit le plus court soit le plus long. Pour effectuer ces recherches nous allons développer
un algorithme à partir d'un exemple d'application.

Exemple d'application

Soit les sommets X d'un graphe valué dont les antérieurs sont les suivant.

x Sommets antérieurs Précédents Col1 Col2 Col3

1 - - - - -
2 1,3 1,3 . - -
3 - - - - -
4 1 1 . - -
5 3 3 . - -
6 2,4,8,9 8,9 8,9 8,9 .
7 2,3,5 2,5 2,5 . -
8 1,2,3,4,5 2,4,5 2,4,5 . -
9 1,4 4 4 . -
10 7,8,9 7,8,9 7,8,9 7,8,5 .

Les arcs sont affectés des valeurs suivantes :

Arc Valuations
(1,2) 5
(1,4) 2
(2,7) 1
(2,8) 6
(3,2) 3
(3,5) 1
(4,8) 5
(4,9) 4
(5,7) 2
(5,8) 3
(7,10) 5
(8,6) 3
(8,10) 6
(9,6) 3
(9,10) 3
TAF:
1. Dessiner le graphe ordonnancé par niveau
2. Rechercher tous les chemins de longueur minimale partant du sommet 1
3. Recherche tous les chemins de longueur maximale partant du sommet 1
 9
4 6

1
8

2 10

3 7

[Link] Recherche d'un chemin de longueur minimal

L'algorithme que nous allons développer permet de déterminer la longueur minimale de tout chemin
partant d'un sommet i choisi par marquage. La marque Mj correspond au sommet j et est égale à la
longueur du chemin minimal lij parcouru du sommet de départ i au sommet j. Par convention, le sommet de
depart i a une marque nulle.

Solution :

2. Recherche des chemins minimaux au départ du sommet 1

Soit aij la longueur de l'arc (i,j) et P(i) l'ensemble des précédents de i.

Marquage des sommets de tous les chemins partant du sommet 1.

M1: l1,1=0

M2: l1,2 = Min(l1,I + ai,2) i ∈ P(2) = Min(l1,1 + a1,2,l3,2 + a2,3) = Min(l1,1 + a1,2) = l1,1 + a1,2 = 0 + 5 = 5

M4 : l1,4 = Min(l1,i + ai,4) i ∈ P(4) = l1,1 + a1,4 = 0 + 2 = 2

M9 : l1,9 = Min(l1,i + ai,9) i ∈ P(9) = l1,4 + a4,9 = 2 + 4 = 6

M8 : l1,8 = Min(l1,i + ai,8) i ∈ P(8) = Min(l1,4 + ai,8 )

M7 : l1,7 = Min(l1,i + ai,7) i ∈ P(7) (Précédent de 7) = Min(l1,5 + a5,7 , l1,2 + a2,7 ) = l1,2 + a2,7 = 5+1 = 6

M6 : l1,6 = Min(l1,i + ai,6) i ∈ P(6) = Min(l1,9 + a9,6 , l1,8 + a8,6 ) = Min(6 + 3 , 7 + 3 ) = 9

M10 : l1,10 = Min(l1,i + ai,10) i ∈ P(10) = Min(l1,9 + a9,10 , l1,8 + a8,10 , l1,7 + a7,10) = Min(6 + 3 , 7 + 6 , 6 + 5)
= Min(9 , 13 , 11) 9

[Link] Recherche d'un chemin de longueur maximale

L'algorithme qui permet de déterminer la longueur maximale de tous les chemins partant d'un sommet i
est identique au précédant; la seule différence est une recherche de maximum au lieu d'une recherche de
minimum. La marque Mj correspondant au sommet j est égale à la longueur du chemin maximal mij
parcouru du sommet de départ i au sommet j.
 4.4 Problème d'ordonnancement
4.4.1 Introduction

La conception est la réalisation de grands travaux ou de grands projets nécessite une suite d'opération
nombreuse dont la coordination est complexe du fait de contraintes diverses. Celles-ci peuvent être
financière, matérielle, humaine ou chronologique. L'ordonnancement de ces opérations ou taches
consistent à établir le programme ou l'ordre dans lequel ces taches seront exécutées. Ce programme
implique l'établissement d'un calendrier et le contrôle du déroulement de la bonne exécution des
prévisions. L'étude d'un ordonnancement commence nécessairement par l'analyse préalable du projet.
Celui-ci doit être décomposé en caches élémentaires. Pour chacune de ces opérations élémentaires, il est
importe de déterminer la durée, les contraintes spécifiques et les taches qui doivent nécessairement la
précéder. Après cette analyse, la théorie des graphes intervient en tant qu'aide à la réalisation de
l'ordonnancement.

4.4.2 La méthode PERT

Cette méthode a été élaborée aux Etats-Unis à partir de 1958 sous l'impulsion de Robert Mac Namara et de
la NASA pour la construction de fusée. Elle permet d'ordonnancer dans le temps des opérations
élémentaires d'un projet complexe. Le sigle PERT signifie Program Evaluation Reasearch Task.

[Link] Graphe PERT

L'ordonnancement est établi au moyen d'un graphe dans lequel chaque arc représente une opération
élémentaire. Un sommet représente un évènement ou une étape, il indique le début de l'opération pour
l'arc dont il est l'origine et la fin d'une autre opération pour l'arc dont il est l'extrémité.

Exemple : L'opération P dure trois (3) jours et elle suit l'opération A qui dure 2 jours. La représentation du
graphe PERT est la suivante :

A(2) B(3)
1 2 3

L'opération A commence à l'étape 1 dure 2 jours et se termine à l'étape 2;

L'opération B commence à l'étape 2 dure 3 jours et se termine à l'étape 3.

Pour commencer le graphe, on introduit un sommet qui correspond à évènement: le programme démarre.
On introduit aussi un sommet pour marquer la fin du graphe. Il correspond à l'évènement : le programme
est fini.

L'opération parallèle donne lieu à la représentation d'un multi-graphe.

Sommet fictif – Liaison fictive :

Pour constituer un graphe G(X,U), on associe à chaque nœud un sommet xi ∈ X et à chaque liaison un arc
u=(xi,xj) tel que u ∈ U.
Dans la suite nous ne traiterons que les réseaux de circulation pouvant être représenté par un graphe
orienté. En appliquant cette méthode, il arrive fréquemment que plusieurs arcs joignent dans le même ses
un sommet xi à un sommet xj. Nous sommes alors en présence un multi-graphe qui soulève des difficultés
de traitement. Pour palier cet inconvénient, on peut soit remplacer des liaisons par une seule liaison fictive,
soit si l'opération précédente n'est pas possible, créer un ou plusieurs sommets fictifs sur des liaisons
excédentaires. Exemple : Soit les liaisons
Xi Xj
qu'il n'est pas possible de condenser une seule liaison. On introduit le sommet fictif xk tel qu'un des deux
arcs soit remplacé par deux liaisons. Cette difficulté réglée, il est donc possible d'associer un graphe G à un
réseau de circulation.

Xi Xj

Xk
[Link] Le respect des contraintes de succession

Le graphe doit précisément respecter les contraintes de succession. Exemple : L'opération B dure 3 jours et
elle suit l'opération A qui dure 2 jours; l'opération C dure 4 jours. C est indépendant de A et B. La
représentation est la suivante :

A(2)
1 2

B(3)
C(4)

Au besoin, il est possible de décomposer une opération sous opérations avec introduction de sommets
fictifs. Exemple : l'opération B dure 3 jours et elle suit l'opération A qui dure 2 jours; l'opération C dure 4
jours, C est indépendant de B mais ne peut commencer qu'un (1) jour après le début de A. L'opération A
est décomposé en 2 sous opérations : A1 de durée 1 jour et A2 de duré 1 jour. La représentation est la
suivante.

A1(1) A2(1)
1 2 3

B(3)
C(4)

[Link] Chemin critique

Le chemin critique est un chemin de longueur maximal reliant le sommet de départ au sommet d'arrivé. Il
peut ne pas être unique. La longuer du chemin critique est la durée minimale de réalisation du projet. Les sommets
de ce chemin sont des évènements critiques. Les arcs qui le composent sont des opérations critiques. Tout
retard de réalisation d'une opération crique retarde d'autant tout le projet.
 [Link] Date au plus tôt et date au plus tard d'un évènement

Date au plus tôt (de début de l'évènement) :

L'évènement i est le début de l'opération I qui est précédé par les opérations J et K. Ces opérations
débutent respectivement par les évènements j et k. La date à laquelle se produira l'évènement i dépendra
de la durée de réalisation la plus longue de l'opération J ou K et de la plus tardive de l'opération j et k.

D'une manière générale, la date au plus tôt d'un sommet i d'un graphe PERT commençant par le sommet 1
est la marque l1,i du sommet i dans la recherche du chemin de longueur maximale pour relier 1 à i.
Appelons ti cette date au plus tôt. l1,i = ti = max(tk + tki) k∈P(i).

P(i) est l'ensemble des précédents de i

tk est la marque du sommet k dans la recherche d'un chemin de longueur maximal de 1 à k

tki est la durée de l'opération reliant k à i.

ti est la date à laquelle l'opération I pourra être commencée au plus tôt. Sur le graphe PERT cette date au
plus tôt sera représentée de la manière suivante.

j
J

I
i

La date au plus tôt du sommet de départ est égale à 0 : t1 = 0.

Date au plus tard (de début de l'évènement):

Tout retard sur une opération critique retarde d'autant tout projet; la date ou l'évènement à laquelle se
termine cette opération est repoussée d'autant. Pour une opération non critique, on peut concevoir qu'il
possible de prendre un certain retard sans retarder tout le projet. La date au plus tard relative à
l'évènement i donne la date à laquelle l'opération I pourra être commencée sans que tout le projet soit
retardé. Appelons t*i la date au plus tard du sommet i. Pour calculer cette date au plus tard, il faut partir du
sommet d'arrivé n du graphe PERT. Pour ce sommet terminal, on obtient obligatoirement l'égalité entre la
date au plus tôt et la date au plus tard : t*n = tn. La date au plus tard d'un sommet i est obtenu de proche en
proche en partant de n de tel sorte que t*i = Min(t*h - tih) h∈S(i). S(i) représente l'ensemble des suivants de i.

t*h représente la date au plus tard du sommet h

tih représente la durée de l'opération ih

Sur le graphe PERT cette date au plus tard sera représenté par le graphe suivant :

j
J

ti t *i I
i

Remarque : Sur le chemin critique, les sommets ont tous une date au plus tôt égale à la date au plus tard :
ti=t*i.

Soit le graphe PERT suivant :

3 D(8)
B(4)
F(3)
A(3) 5 6
1 2
C(5) E(3)
4

t1 = 0

t2 = Max(ti + ti2) i e P(2) = t1 + t12 = 0 + 3 = 3

t3 = Max(ti + ti3) i e P(3) = t2 + t23 = 3 + 4 = 7

t4 = Max(ti + ti4) i e P(4) = t2 + t24 = 3 + 5 = 8

t5 = Max(ti + ti5) i e P(5) = Max(t3 + t35 , t4 + t45) = Max(7 + 8 , 8 + 3) = 15

t6 = Max(ti + ti6) i e P(6) = t5 + t56 = 15 + 3 = 18

Les dates au plus tard sont obtenues en partant du sommet 6

t*6 = t6 = 18

t*5 = Min(t*k – t5h) h e S(5) = t*6 – t56 = 18 – 3 = 15

t*3 = Min(t*h – t3h) h e S(3) = t*5 – t35 = 15 – 8 = 7

t*4 = Min(t*h – t4k) h e S(4) = t*5 – t45 = 15 – 3 = 12

t*2 = Min(t*h – t2h) h e S(2) = Min(t*3 – t23 , t*4 – t24) = Min(7 - 4 , 12 - 5) = 3

t*1 = Min(t*h – t1h) h 3 S(1) = t*2 – t12 = 3 – 3 = 0

7 7 I
3

0 0 3 3
15 15 18 18
1 2
5 6
8 12
4

Nous constatons que le chemin critique est (1, 2, 3, 5, 6) et les taches critiques sont (A, B, D, F)

[Link] Les marges

Intervalle ou marge de flottement de l'évènement i :

La marge de flottement d'un sommet est égale à la différence t*i – ti. Elle indique le retard que peut
prendre le démarrage d'une opération commençant en i sans que la durée globale du projet soit remise en
cause.

Marge libre de l'opération (i , j) :

Elle est égale à Mij= tj –ti – tij. Cette marge indique le retard que l'on peut prendre au démarrage ou durant
l'exécution de l'opération (i, j) sans modifier la date au plus tôt de l'évènement j et la durée globale du
projet.

Marge totale de l'opération (i, j) :

Elle est égale à MTij = t*j – ti –tij. Cette marge représente le retard maximal que l'on peut prendre au
démarrage ou durant l'exécution de la tache (i, j) sans modifier la date au plus tard de l'évènement j et la
durée globale du projet.

Exemple : reprenons l'exemple précédant

Opération Marge totale Marge libre

A 0 0
B 0 0
C 4 0
D 0 0
E 4 4
F 0 0