THÉORIE DES GRAPHES

&&
PROGRAMMATION LINÉAIRE
Mme Hajer Ayadi
 Plan
2

 Théorie des Graphes (TG)

 Définitionset concepts de base
 Coloration des graphes
 Arbre et arborescence
 Problème de plus courts chemins

 Programmation Linéaire (PL)

 Modélisation
 Résolution
graphique
 Méthode de simplexe
 Dualité

TG/PL- 2017/2018
3 TG: Histoire

TG/PL- 2017/2018
 Histoire
4

 La théorie des graphes débute avec les travaux d’Euler au XVIIIe siècle
 Origine: l’étude de certains problèmes, tels que celui des ponts de Königsberg

 Les habitants de Königsberg se demandaient s’il était possible, en partant d’un quartier quelconque
de la ville, de traverser tous les ponts sans passer deux fois par le même et de revenir à leur point
de départ
 Les graphes constituent une méthode de pensée qui permet de modéliser une
grande variété de problèmes en se ramenant à l’étude de sommets et d’arcs
 Les derniers travaux en théorie des graphes sont souvent effectués par des
informaticiens, du fait de l’importance qu’y revêt l’aspect algorithmique

TG/PL- 2017/2018
5 TG: Définitions et Concepts de base

TG/PL- 2017/2018
 Graphe Orienté
6

 Un Graphe Orienté G=(X,U) est déterminé par la donnée:

 D’un ensemble de sommets ou nœuds X
 D’un ensemble ordonné U de couples de sommets appelés arcs
 Le nombre de sommets d’un graphe est l’ordre du graphe
 Si u=(a,b) est un arc de G alors
 a est l’extrémité initiale de u . On note I(u)
 b est l’extrémité terminale de u. On note T(u)
 b est le successeur de a , a est le prédécesseur de b
 L’arc (a,a) est appelé une boucle
 Les arcs ont un sens. L’arc u=(a,b) va de a vers b
 Ils peuvent être munit d’un coût, d’une capacité, etc.

TG/PL- 2017/2018
 Graphe Orienté
7

TG/PL- 2017/2018
 Graphe Orienté
8

 Adjacence:
 Deux arcs sont dits adjacents s’ils ont une extrémité commune

 Deux sommets sont adjacents s’il existe un arcs entre eux

 Degré/demi-degré d’un sommet x: soit x un sommet de G(X,U):

 Le demi-degré extérieur de x, noté d+(x), est le nombre d’arcs ayant x
comme extrémité initiale:
 d+(x) =|{u  U / I(u)=x}|
 Le demi-degré intérieur de x, noté d-(x), est le nombre d’arcs ayant x
comme extrémité terminale:
 d-(x) =|{u  U / T(u)=x}|
 Le degré de x, noté d(x), est le nombre d’arcs ayant x comme extrémité

d(x)= d+(x)+ d-(x)

 Un sommet de degré nul est dit sommet isolé
TG/PL- 2017/2018
 Un sommet de degré 1 est dit sommet pendant
 Graphe Orienté
9

 Exemple:
 Déterminer les degrés et les demi-degrés des
sommets suivants:

1 2 3 4 5 6 7 8 9 10
d+(x)

d-(x)

d(x) ∑=
TG/PL- 2017/2018
 Graphe Orienté
10

 Théorème:
 Soit G(X,U) un graphe, Démonstration:

 d
xX

( x )   ( x)  U
xX
d 

 d ( x) 2 * U
xX

 Corollaire:
 Le nombre de sommets de degré impair est pair
 Démonstration:

TG/PL- 2017/2018
 Graphe Non Orienté
11

 Un Graphe non orienté G=(X,E) est déterminé par la donnée:

 d’un ensemble de sommets ou nœuds X
 d’un ensemble E de paires de sommets appelées arêtes
 Les arêtes ne sont pas orientées
 Adjacence:
 Deux sommets liées par une arête sont dit adjacents
 Deux arêtes qui possèdent une extrémité commune sont dites adjacentes
 Les arêtes n’ont un sens. L’arête e=(a,b) va de a vers b et de
b vers a

TG/PL- 2017/2018
 Graphe Non Orienté
12

TG/PL- 2017/2018
 Graphe Non Orienté
13

 Ordre de multiplicité:
 Si une arêtes u est représentée p fois dans un graphe, on dit
que l’ordre de multiplicité de u est p, et on note m(u)=p
 Graphe simple:
 Un graphe est dit simple si pour tout arête u du graphe
m(u)=1
 Il ne possède pas de boucle

 Graphe multiple:
 Un graphe est dit multiple ou multi-graphe s'il possède au
moins une arête u telle que m(u)>1
TG/PL- 2017/2018
 Isomorphisme
14

 Deux graphes G1(X1,U1) et G2(X2,U2) sont dit isomorphes s’il existe

deux bijections:
Ru: U1U2 Bx: X1X2
et x1x2
(x1,y1)(x2,y2) y1y2
 Remarque:
 Décider si deux graphes sont isomorphes est un problème ’difficile’ (NP-
complet)
 Conditions nécessaires: pour que deux graphes soient isomorphes,
ils doivent avoir:
 Même nombre de sommets
 Même nombre d’arêtes (arcs)
 Pour tout entier k, le degré de sommets x tel que d+(x)=k (ou/et d-
(x)=k) est le même dans les deux graphes
 Conditions ne sont pas suffisantes
 Exemple TG/PL- 2017/2018
 Graphe partiel/sous graphe
15

 Soit G(X,E) un graphe et E’  E:

 G’(X,E’) est dit graphe partiel de G
 Soit X’ X et E’’={(x,y) E tq x et yX’ }. Soit G’’(X’,E’’)
est dit sous graphe de G engendré par X
 Un sous graphe partiel est un graphe partiel du sous
graphe
 Les définitions précédents sont valables aussi pour un
graphe orienté
 Exemple1

 Exemple2

TG/PL- 2017/2018
 Chemins, chaînes, cycles et circuits
16

 Soit G(X,U) un graphe orienté

 Chemin: une séquence d’arcs U=(u1,u2,..,uk) tel que
l’extrémité terminale d’un arc coïncide avec l’extrémité
initiale de l’arc suivant. T(ui)=I(ui+1) pour i=1,2,…, k-1
 Chemin simple: passe une et une seule fois par chaque arc du
chemin
 Chemin élémentaire: passe une et une seule fois par chaque
sommet du chemin
 Circuit: un chemin simple dont l’extrémité initiale du 1er arc
coïncide avec l’extrémité terminale du dernier arc. I(u1)=T(uk)
 Circuit élémentaire: passe une et une seule fois par chaque sommet
du circuit
 Longueur d’un chemin: le nombre d’arcs qui composent le
chemin (ou le circuit)

TG/PL- 2017/2018
 Chemins, chaînes, cycles et circuits
17

 Soit G(X,E) un graphe non orienté

 Chaine : une suite d’arêtes tel que chaque arête est rattachée à la
précédente par une extrémité et à la suivante par l’autre extrémité
 Chaine simple: passe une et une seule fois par chaque arête de la chaine
 Chaine élémentaire: passe une et une seule fois par chaque sommet de la
chaine
 Cycle: un chaine simple dont les extrémités sont confondues
 Cycle élémentaire: passe une et une seule fois par chaque sommet de la chaine
 Longueur d’une chaine: le nombre d’arêtes qui composent la chaine (ou le
cycle)
 Distance: La distance entre deux sommets x et y est la longueur de la plus
courte chaine (chemin) entre x et y. On note D(x,y)
 Diamètre: La distance la plus grande entre deux points de graphe
∂ (G)=Max d(x,y)
TG/PL- 2017/2018
 Connexité
18

 Soit G(X,E) un graphe non orienté

 Un graphe connexe : s’il existe au moins une chaîne entre un paire
de sommets de G
 La relation xi R xj il existe une chaine entre xi et xj
 R est une relation d’équivalence (réflexive, symétrique, transitive).
Les classes d’équivalence induites sur X par R forment une partition
de X en X1,X2,…, Xp
 Le nombre P de classe d’équivalence est appelé nombre de
connexité de graphe
 Un graphe est dit connexe ssi son nombre de connexité est égal à 1
 Les sous-graphes Gi engendrés par les sous ensembles Xi sont
appelés les composantes connexes (C) du graphes.
 Chaque composante connexe est un graphe connexe

TG/PL- 2017/2018
 Connexité
19

 Un point d’articulation d’un graphe est un sommet dont

la suppression augmente le nombre de composantes
connexes
 Un isthme est une arêtes dont la suppression augmente
le nombre de composantes connexes
 Un ensemble d’articulation d’un graphe connexe G est
un ensemble de sommets tel que le sous graphe G’
déduite de G par la suppression des sommets de E ne
soit plus connexe

TG/PL- 2017/2018
 Forte Connexité
20

 Soit G(X,U) un graphe orienté

 Un graphe fortement connexe : s’il existe un chemin
joignant deux sommets quelconque
 La relation xi R xj il existe à la fois un chemin joignant
xi à xj et un chemin joignant xj à xi
 R est une relation d’équivalence et les classes
d’équivalence induites sur X par R forment une partition
de X en X1,X2,…, Xq
 Une classe d’équivalence de R est dite composante
fortement connexe (CFC)
 Un graphe est dit fortement connexe s’il n’a qu’une seul
CFC

TG/PL- 2017/2018
 Forte Connexité
21

 Algorithme de détermination des CFC:

 Soitx X, déterminant les composantes fortement
connexes contenant le sommet x
 Etape (0): Donner à x la marque ‘+’ et ‘-’
 Etape (1): Tant qu’il existe un arc U=(x,y) tel que x est
marqué ‘+’ et y non marqué ‘+’, alors donner à y la marque
‘+’
 Etape (2): Tant qu’il existe un arc U=(x,y) tel que y est
marqué ‘-’ et x non marqué (-), alors donner à x la marque
(-)
 Etape (3): L’ensemble des sommets qui sont marquée à la
fois (+) et (-) constituent une CFC contenant le sommet (x)

TG/PL- 2017/2018
 Forte Connexité
22

 Exemple1:

TG/PL- 2017/2018
 Forte Connexité
23

 Exemple2:
 Donner l’ensemble des successeurs et des
prédécesseurs de chaque sommet.
 Calculer les demi-degrés intérieurs et
extérieurs de chaque sommet.
 Donner un exemple de chemin simple
mais non élémentaire.
 Existe-t-il un circuit hamiltonien dans G?
 Tracer le graphe non orienté déduit de
G.
 G est-il connexe ? Fortement connexe?

TG/PL- 2017/2018
 Graphe particuliers
24

 Graphe hamiltonien:
 Chemin hamiltonien (chaine hamiltonienne): s’il passe une et une
seule fois par chaque sommet du graphe
 Graphe hamiltonien s’il contient un circuit (cycle) hamiltonien
 Graphe eulérien:
 Une chemin eulérien (chaine eulérienne): s’il passe une et une
seule fois par chaque arc (arête) du graphe
 Graphe eulérien s’il contient un circuit (cycle) eulérien

TG/PL- 2017/2018
 Graphe particuliers
25

 Graphe biparti: si ses sommets peuvent être divisés en

deux ensembles X et Y , de sorte que toutes les arêtes
du graphe relient un sommet dans X à un sommet dans Y
 Graphe complet: si chaque sommet du graphe est relié
directement à tous les autres sommets
 Graphe régulier: un graphe dont tous les sommets ont
le même degré. Si le degré commun est k, alors on dit
que le graphe est k-régulier
 Graphe planaire: peut être dessiner dans le plan de
sorte que ses arêtes ne se croisent pas
 Un clique un sous-graphe complet de G.

TG/PL- 2017/2018
 Matrices d’incidences et d’adjacences
26

 Matrice d’adjacence:
 SoitG=(X,A) un graphe orienté simple comportant n
sommets
 La matrice d’adjacence de G est une matrice booléenne
U=(uij) de dimension n*n telle que:

 Exemple:

TG/PL- 2017/2018
 Matrices d’incidences et d’adjacences
27

 Matrice d’adjacence:

 Propriétés:
 La somme des éléments de la ième ligne de U est égale au degré sortant
d+(xi) du sommet xi de G

TG/PL- 2017/2018
 Matrices d’incidences et d’adjacences
28

 Matrice d’adjacence:

 Propriétés:
 La somme des éléments de la ième ligne de U est égale au degré sortant
d+(xi) du sommet xi de G
 La somme des éléments de la jème colonne de U est égale au degré
entrant d-(xj) du sommet xj de G
TG/PL- 2017/2018
 Matrices d’incidences et d’adjacences
29

 Matrice d’incidence:
 SoitG=(X,A) un graphe orienté sans boucle comportant
n sommets X={x1,…,xn} et m arcs A={a1,…, am}
 Matrice d’incidence (aux arcs) de G: matrice M=(mij)
de dimension n*m telle que:

 Pour un graphe non orienté sans boucle, la matrice

d’incidence (aux arêtes) est définie par

TG/PL- 2017/2018
 Matrices d’incidences et d’adjacences
30

 Matrice d’incidence:

TG/PL- 2017/2018
31 TG: Coloration des graphes
Dans ce chapitre le graphe G(X,E) est supposé
non orienté

TG/PL- 2017/2018
 Coloration des sommets d’un graphe
32

 Exemple:
 On veut transporter des produits chimiques par des camion.
 A, B, C, D, E, F, G et H désignent huit produits chimiques.
 Certains produits (par paires) ne peuvent pas être transportés dans un même camion à
cause du risque d'explosion.
 Objectif: Transporter les différents produits sans risque et au moindre coût (c.à.d. en
utilisant le moins de camions possible).
 Dans le tableau ci-dessous, une croix signifie que les produits ne peuvent pas être
transportés dans le même camion, car il y aurait risque d’explosion :
 Coloration des sommets d’un graphe
33

 Exemple:
 Solution:
 Construire un graphe dont les sommets sont les produits chimiques:
 deux produits chimiques (nœuds) sont reliés si et seulement s'ils ne peuvent pas
être transportés ensemble.
 Transporter un des produits dans un camion revient à attribuer une couleur à ce produit
(celui du camion correspondant).
 Les conditions de sécurité imposent d'attribuer ces couleurs de sorte que deux produits
adjacents n'aient pas la même couleur.
 Coloration des sommets d’un graphe
34

 Définition: Soit k N,

 Une k-coloration des sommets d'un graphe G: coloration de ses sommets en k
couleurs de telle sorte que deux sommets adjacents ne portent pas la même
couleur
 Un stable: sous ensemble S de X qui ne comporte que des sommets non
adjacents deux à deux.
 Dans le graphe ci-dessous, les stables sont: {v1, v2}, {v2, v4}, {v2, v5} et {v3, v5}.

 Le nombre de stabilité de G, noté α(G): le cardinal du plus grand stable.

 Dans le graphe précédent, on a α(G)=2.
 le nombre chromatique du graphe G, noté  (G ) : le nombre minimal des k
couleurs nécessaires
 Coloration des sommets d’un graphe
35

 Exemple:
 Sur le graphe ci-dessous, on a trois stables : {v1, v2}, {v3, v5} et {v4}.
 On a besoin de trois couleurs (notées 1, 2 et 3) pour colorer les sommets de sorte que
deux sommets adjacents aient des couleurs différentes.
 On ne peut pas utiliser moins de couleurs, à cause des cliques {v1, v4, v5} et {v1, v3, v4}

 Remarque: le sommet v2 peut être coloré «3».

 La coloration minimale n’est donc pas forcément unique.

TG/PL- 2017/2018
 Coloration des sommets d’un graphe
36

 Encadrement du nombre chromatique

 Majoration:
  (G )  1  D où D est le plus grand degré des sommets de G:
 Preuve : Soit G(X,E) un graphe et D le degré maximum de ses sommets.
 Donnons-nous une palette de (D+1) couleurs.

 Pour chaque sommet du graphe, on peut tenir le raisonnement suivant :

 Ce sommet est adjacent à D sommets au plus, et le nombre de couleurs déjà

utilisées pour colorer ces sommets est donc <=D .
 Il reste donc au moins une couleur non utilisée dans la palette, avec laquelle
nous pouvons colorer notre sommet
  (G )  n  1   (G ) où n=|X|
 Preuve: Considérons S un stable de X de cardinalité α(G)
 Une coloration possible des sommets consiste à colorer les sommets de S d’une
même couleur et les n-α(G) autres sommets de couleurs toutes différentes.
   (G )  n  1   (G )
 Coloration des sommets d’un graphe
37

 Encadrement du nombre chromatique

 Minoration
 Le nombre chromatique d’un graphe est supérieur ou égal à celui
de chacun de ses sous-graphes

 Preuve : Ce résultat découle de la définition même du

nombre chromatique

 Le nombre chromatique du graphe sera supérieur ou égal à

l’ordre de sa plus grande clique, que l’on note  (G )  (G )   (G )

 Preuve : dans une clique d’ordre m, tous les sommets sont

adjacents entre eux, il faudra m couleurs.
 il faudra au moins  (G ) couleurs pour colorer le graphe
G
TG/PL- 2017/2018
 Coloration des sommets d’un graphe
38

 Algorithme de coloration de Welsh et Powell:

 permet d’obtenir une bonne coloration d’un graphe. Cependant il
n’assure pas que le nombre de couleurs soit minimum (nombre
chromatique du graphe)
 Étape 1: Classer les sommets du graphe dans l’ordre décroissant de leur
degré, et attribuer à chacun des sommets son numéro d’ordre dans la liste
obtenue.
 Étape 2: En parcourant la liste dans l’ordre, attribuer une couleur non
encore utilisée au premier sommet non encore coloré, et attribuer cette
même couleur à chaque sommet non encore coloré et non adjacent à un
sommet de cette couleur
 Étape 3: S’il reste des sommets non colorés dans le graphe, revenir à
l’étape 2.
 Sinon, FIN.

TG/PL- 2017/2018
 Coloration des sommets d’un graphe
39

 Algorithme de coloration de Welsh et Powell:

 Exemple: Soit le graphe G(X,E) ci-dessous:
 1.On liste les sommets par ordre décroissant des degrés
(plusieurs possibilites).

 2. On attribue une couleur c1 au premier sommet de la

liste, et on attribue cette même couleur aux sommets qui ne
lui sont pas adjacents.

 3. On attribue une couleur c2 au premier sommet non

colorie de la liste

 4. on recommence comme en 2 tant qu'il reste des sommets

non colories dans la liste
TG/PL- 2017/2018
 Coloration des arêtes d’un graphe
40

 Définition:
 Une k-coloration des arêtes d'un graphe G: coloration de ses arêtes en
k couleurs de telle sorte que deux arêtes adjacents ne portent pas la
même couleur
 le nombre chromatique du graphe G, noté  (G ) : le nombre minimal
des k couleurs nécessaires
 Si D(G) est le degré maximum de G alors  (G )  D(G )
 Si G’ est un sous graphe ou graphe partiel de G alors  (G ' )   (G )

 Si C est un cycle alors  (G)  2 si C est un cycle pair

3 si C est cycle impair
n-1 si n est pair
 Si G est un graphe complet d’ordre n, alors:  (G)  n si n est impair

TG/PL- 2017/2018
41 TG: Arbre et arborescence
Dans ce chapitre le graphe est supposé non
orienté

TG/PL- 2017/2018
 Arbre
42

 Un arbre est un graphe connexe sans cycles.

 Une forêt est un graphe dont chaque composante
est un arbre
 Théorème:
 G=(X,E) est un arbre si et seulement si il existe une
unique chaîne reliant toute paire de sommet
 Preuve:
 Sion a 2 chaines alors on aurait un cycle
 connexe équivaut à il existe toujours une chaine entre toute
paire de sommet

TG/PL- 2017/2018
 Arbre
43

 Théorème :
 Soit H=(X,E) un graphe d’ordre ≥ 2;
 les propriétés suivantes sont équivalentes pour caractériser un arbre
 H est connexe et sans cycle
 H est sans cycle et admet n-1 arcs
 H est connexe et admet n-1 arcs
 H est connexe et en ajoutant un arc on crée un cycle (et un seul)
 H est sans cycle et si on supprime un arc quelconque , il n’est plus connexe
 Tout couple de sommets est relié par une chaîne et une seule
 Corollaire1: toute arête d’un arbre est un isthme
 Corollaire2: un arbre contient au moins 2 sommets pendants
 Corollaire3: un arbre est un graphe biparti (  ( H )  2 )
 Corollaire4: tout graphe connexe possède un graphe partiel qui est un
arbre TG/PL- 2017/2018
 Arbre couvrant
44

 Un arbre couvrant est un graphe partiel qui est

aussi un arbre.

TG/PL- 2017/2018
 Arbre couvrant de poids minimum
45

 Soit le graphe G = (V,E) avec un poids associé à chacune de ses arêtes. On veut
trouver, dans G, un arbre couvrant A = (V,F) de poids total minimum
 Algorithme de Kruskal (1956)
 Données :
 Graphe G = (V,E) (|V| = n, |E| = m)
 Pour chaque arête e de E , son poids c(e).
 Résultat :
 Arbre ou forêt maximale A = (V,F) de poids minimum.
 Trier et renuméroter les arêtes de G dans l’ordre croissant de leur poids :
c(e1) =< c(e2) =< . . . =< c(em).
 Poser F :=Ф , k := 0
 Tant que k < m et |F| < n−1 faire
 Début
 si ek+1 ne forme pas de cycle avec F alors F := F U {ek+1}
 k := k+1
 Fin

TG/PL- 2017/2018
 Arbre couvrant de poids minimum
46

 Exemple:
 Trouver l’arbre couvrant de poids minimum du graphe ci-dessous

TG/PL- 2017/2018
 Arbre couvrant de poids minimum
47

 Solution:

 Les arêtes de poids 3 n’ont pas pu être placées, car elles auraient formé un cycle.
 L’algorithme s’est arrêté dès que cinq arêtes ont été placées.
 Toute arête supplémentaire aurait créé un cycle.
 S’il y a plusieurs arêtes de même poids, il peut y avoir plusieurs arbres couvrants de poids
minimum : tout dépend de l’ordre dans lequel ces arêtes ont été triées.

TG/PL- 2017/2018
 Arborecence
48

 Dans un graphe G(X,E), on appelle racine, un point a tel que

tout autre sommet du graphe puisse être atteint par un chemin
issu de a.
 Une racine n’existe pas toujours.
 Une arborescence est un arbre muni d’une racine
 Propriétés:
 Soit A une arborescence de racine a, on a alors:
x  a , d-(a)=0 et d-(x)=1
 Tout graphe G de racine a admet un graphe partiel qui est une
arborescence de racine a

TG/PL- 2017/2018
49 TG: Problème de plus courts chemins
Dans ce chapitre le graphe est supposé orienté

TG/PL- 2017/2018
 Position du problème
50

 Soit G(X,U) un graphe orienté,

et l’application l : U  R dit longueur de l’arc u
u  l (u )
 est dit réseau
R  ( X ,U , l )

 La longueur d’un chemin C : la somme des longueurs des arcs

qui le compose. l (C )   l (u )
uC
 Exemple:

TG/PL- 2017/2018
 Position du problème
51

 Définitions:
 Un circuit C absorbant, noté CA, si l(C)<0
 Dans un graphe G, un sommeta  X est une racine, s’il existe dans G, un
chemin de a vers x,x  X \ a
 La distance d’un sommet x à y, noté d(x,y) est la longueur du plus court
chemin de x à y. Par convention, s’il n’existe pas de chemin de x à y,
d(x,y)=+∞
 d(x,x)=0
 Généralisation du problème:
 Pb1: trouver le plus court chemin d’un sommet i vers un sommet j
 Pb2: trouver le plus court chemin d’un sommet i vers tout sommet j du graphe
 Pb3: trouver un plus court chemin de tout sommet i à tout sommet j

TG/PL- 2017/2018
 Position du problème
52

 Théorème1:
 Les conditions nécessaires et suffisantes (CNS) pour que le problème pb1 (resp
pb2 et pb3) ait une solution sont:
 L’ensemble des sommets qui sont à la fois des descendant de (i) (successeurs) et ascendant (
prédécesseur) de (j) soit non vide; autrement dit, il existe au moins un chemin de i à j.
 Il n’existe pas de CA sur le chemin allant de i à j, si non la longueur de ce chemin ne sera pas
borné inférieurement.
 Théorème 2:
 Soit C un plus court de chemin de i à j et soit x et y deux sommets de C, le sous
chemin de C partant de x vers y, noté Cxy, est un plus court chemin de x à y.
 Théorème 3:
 Soit un graphe G(X,U,l), sans CA, admettant a comme racine.
 On associe à chaque sommet x  X , la valeur π(x) = π(a,x) représentant le
plus court chemin de a à x.
 On au  U ,  (T (u ))   ( I (u ))  l (u )

TG/PL- 2017/2018
 Algorithmes de plus court chemin
53

 Algorithme de Ford:
 Etape 0: Le graphe ne contient pas de circuit absorbant
 Numéroter les n sommets du graphe dans un ordre quelconque de x1 à xn-1 à
l’exception du sommet racine (sommet origine: x0, sommet destination: xn-1)
 Initialisation: poser π(x0) =0, π(xj)=+∞ j  1,..., n  1 , i=0
 Etape1:
 u U / I (u)  xi ,faire
 Si π(xj)> π(i)+ l(xi,xj) alors
 { π(xj)= π(i)+ l(xi,xj)
 Si j<i alors
 { i=j
 Aller à (1)
 }
 }
 Etape2:
 i=i+1
 Si i<n-1 aller à (1)
 Sinon Fin

TG/PL- 2017/2018
 Algorithmes de plus court chemin
54

 Exemple

TG/PL- 2017/2018
 Algorithmes de plus court chemin
55

 Algorithme de Bellman:
 Etape0: poser S={x0} et π(x0) =0
 Etape1: si x  S / T 1 ( x)  S (tous les prédécesseurs de x sort dans S)
alors
 { π(x) = Min{π(I(u)+ l(u)} avec T(u)=x ( I ( x)  S )
 S=S U{x}
 }
 Sinon FIN

TG/PL- 2017/2018
 Algorithmes de plus court chemin
56

 Exemple

TG/PL- 2017/2018
 Algorithmes de plus court chemin
57

 Algorithme de Dijkstra :u  U , l (u )  0

 Soit S l’ensemble de sommet pour lesquelles on a trouvé le plus court
chemin y aboutissant de x0.
 Le cardinal de S augment d’une unité à chaque itération.
 Les sommets s’introduisent dans S suivant l’ordre de leurs plus courte
distance de x0
 c.à.d. Si S={x0, xi, xj, xk} alors π(x0) =< π(xi) =< π(xj) =< π(x0)

 Soit xp un sommet qu’on nomme sommet pivot

TG/PL- 2017/2018
 Algorithmes de plus court chemin
58

 Algorithme de Dijkstra : u  U , l (u )  0
 Etape0:
 S={x0}; xp= x0; π(x0) =0; π(x) = +∞ x  x0
 Etape1:
Tant que (S  X et π(xp) < +∞)
{ u U / I(u)=xp
Si T (u )  S alors
{ x= T(u)
Si π(x) > π(xp) +l(u) alors π(x) = π(xp) +l(u)
}
Choisir x  S /Min π(x); xp= x; S=SU{x};
aller à (1);
}
TG/PL- 2017/2018
 Algorithmes de plus court chemin
59

 Exemple:
 On cherche à déterminer le plus court chemin entre D et G.

TG/PL- 2017/2018
 Algorithmes de plus court chemin
60

 Exemple:
 Voici le graphe obtenu après l'algorithme.
 On écrit à côté de chaque sommet le poids (provisoire ou fixe), et le sommet précédent.
 On peut présenter également le résultat dans un tableau ou chaque ligne représente une
étape de l'algorithme.

D A B C E F G
0 +∞ +∞ +∞ +∞ +∞ +∞
3, D 12,D +∞ +∞ +∞ +∞
3, D 12,D 8,A +∞ 38,A +∞
12,D 8,A 18,C 16,C +∞
12,D 18,C 16,C +∞
18,C 16,C 29,F
18,C 29,F
29,F
 La chaine la plus courte est donc D-A-C-F-G

TG/PL- 2017/2018
61 Programmation Linéaire
Modélisation

TG/PL- 2017/2018
 Introduction
62

 La programmation linéaire (PL): consiste à la résolution

des problèmes d’optimisation complexes visant à
obtenir le meilleur résultat possible en tenant compte
de certaines contraintes.
 Modélisation d’un problème: consiste à identifier :
 Les variables (inconnues)
 Les contraintes
 L’objectif à atteindre (optimisation)

 Dans un problème de programmation linéaire, les

contraintes et l'objectif sont des fonctions linéaires des
variables.
TG/PL- 2017/2018
 Exemple: Problème de production
63

 Une usine de textile doit fabriquer dans une durée bien déterminée: 3 variétés de tissus à
partir de 3 variétés de fils.
 Les stocks sont respectivement 4000kg, 800kg et1500kg pour les fils de qualité A, B et C.
 Chaque tissu fabriqué doit respecter les proportions suivantes (le poids en gramme) de
chaque qualité de fils.
T1 T2 T3
g/m g/m g/m
A 375 500 500
B 125 50 200
C 100 200 150
 La vente en gros est respectivement 2.6 unité monétaire, 4 unité monétaire et 3.6 unité
monétaire pour un mètre de tissus 1, 2 et 3.
 les métiers à tisser, dont la production est 10m par heure, sont disponibles pour 800 heures.
 Proposer une modélisation de ce problème de production de manière à satisfaire la demande,
à partir des quantités disponibles et en maximisant le profit de cette entreprise.
 Exemple: Problème de production
64

 Etapes de modélisation:
 Déterminer les variables de décision (variables à
déterminer par le modèle)
 X1: Quantité (en mètre) de tissu 1 produit
 X2: Quantité (en mètre) de tissu 2 produit
 X3: Quantité (en mètre) de tissu 3 produit
 La fonction objective (maximisation du profit)
 Max Z= 2.6*X1+4*X2+3.6*X3
 Formulation des contraintes
 0.375*X1+0.5*X2+0.5*X3<=4000 (Qte de stock du Fil A)
 0.125*X1+0.05*X2+0.2*X3<=800 (Qte de stock du Fil B)
 0.1*X1+0.2*X2+0.5*X3<=1500 (Qte de stock du Fil C)
 Nombre total d’heures <=800

TG/PL- 2017/2018
 Exemple: Problème de Transport
65

 Une entreprise de construction d'automobiles possède 3 usines à Paris, Strasbourg et

Lyon.
 Elle a besoin d'acheminer les métaux nécessaires à partir de 2 ports (Le Havre ou
Marseille).
 Chaque usine nécessite hebdomadairement 400 tonnes à Paris, 300 tonnes à Strasbourg
et 200 tonnes à Lyon.
 Les ports du Havre et de Marseille peuvent fournir respectivement 550 tonnes et 350
tonnes. Les coûts de transport entre ces villes sont donnés en kilo-€ par tonne dans le
tableau suivant.
Paris (U1) Strasbourg (U2) Lyon (U3)
Le Havre (Port A) 5 6 3
Marseille (Port B) 3 5 4

 Proposer une modélisation de ce problème de transport de manière à satisfaire la

demande, à partir des quantités disponibles et en minimisant les coûts de transport.

TG/PL- 2017/2018
 Exemple: Problème de Transport
66

 Etape de modélisation:
 Déterminer les variables de décision
 XAi: Quantité transportée du port A vers Ui, i=1,2,3
 XBi : Quantité transportée du port B vers Ui, i=1,2,3
 La fonction objective
 MinZ= 5*XA1+6*XA2+3*XA3+3*XB1+5*XB2+4*XB3
 Formulation des contraintes
 XA1+XB1=400 (Qte transportée vers U1)
 XA2+XB2=300 (Qte transportée vers U2)
 XA3+XB3=200 (Qte transportée vers U3)
 XA1+XA2+XA3<=550
 XB3+XB2+XB1 <=350
 XAi>=0, XBi >=0 / i=1,2, 3

TG/PL- 2017/2018
 Exemple
67

 Forme matricielle d’un programme linéaire

Max Z = 5*X1+8*X2
S/C 3*X1+2*X2<=10 Forme canonique
4*X1+X2<=7
X1,X2>=0
X= X1 variables de décisions (principales)
X2
C= 5 coefficients des variables dans la fonction objectives
8
A= 3 2 coefficients des variables dans les contraintes
4 1
B= 10 coté droite des contraintes
7
Trouver X = X1 >=0/ AX<=B de façon à maximiser Z= CX
X2
TG/PL- 2017/2018
 Formes générales d’un PL
68
 Forme canoniques  Forme standard
 Type de maximisation:  Type de maximisation:
 Trouver X=(X1,…,Xn)>=0 / Ax<=B  Trouver X=(X1,…,Xn)>=0 / Ax=B
 Max Z= CX  Max Z= CX
 Type de minimisation  Type de minimisation
 Trouver X=(X1,…,Xn)>=0/ Ax>=B  Trouver X=(X1,…,Xn)>=0/ Ax=B
 Min Z= CX  Min Z= CX

Passage de la forme canonique vers la forme standard:

 Soit le PL suivant:  F.S
 F.C. Max Z =5X1+ 8X2  Max Z =5X1+ 8X2+ 0 e1+0s1
 S/c:  S/c:
 3X1+2X2<=5  3X1+2X2+e1=5
 4X1+X2>=6  4X1+X2-s1=6
 2X1+X2=8  2X1+X2=8
 X1,X2>=0  X1,X2,e1,s1>=0 (e1 var d’ecart, s1 var
de surplus)
69 Programmation Linéaire
Résolution graphique

TG/PL- 2017/2018
 Rappel: La convexité
70

 Définition: Ensemble convexe

 Un ensemble de points est convexe, si pour toute paires de points
x et y de l’ensemble, [xy] est entièrement contenu dans
l’ensemble

 Propriétés:
 L’ensemble de solution d’une inéquation linéaire est un ensemble
convexe
 L’intersection de deux ou plusieurs ensembles convexes est un
ensemble convexe
 L’ensemble de solution d’un système d’inéquation linéaire est un
ensemble convexe

TG/PL- 2017/2018
 Rappel: Polyèdre Convexe
71

 Définition:
 L’intersection
d’un nombre fini d’un demi espace fermé
est appelé polyèdre convexe
 Propriétés:
 L’ensemble des solutions d’un système d’inéquation
linéaire forme un polyèdre convexe
 Lorsque les demi espaces sont des demi-plans de R2
l’intersection est un polygone convexe

TG/PL- 2017/2018
 Technique de résolution graphique d’un PL
72

 Soit le PL suivant:
 Max Z= 2*X1 + X2
 S/C
 X1<=10
 X2<=7
 X1+X2<=12
 X1,X2>=0

 Solution
 C1, ∆1: X1=10
 C2, ∆2: X2=7
 C3, ∆3: X1+X2=12

TG/PL- 2017/2018
 Technique de résolution graphique d’un PL
73

 Définitions:
 solution réalisable: le vecteur X(x1,x2,…x3) qui vérifie
toutes les contraintes
 domaine de définition (ou l’ensemble des solutions
réalisables): la partie du plan qui représente
l’intersection de l’ensemble des solutions de l’inéquation
linéaire correspondant aux contraintes
 solution optimale: la solution réalisable qui maximise (ou
minimise) la fonction objective
 Remarque: la solution optimale n’est pas nécessairement
unique

TG/PL- 2017/2018
 Technique de résolution graphique d’un PL
74

 Solution optimale:
 On pose ∆z= 2x1+X2
 Pour ∆z =0 / A=(0,0) et B=(1,-2)
 Pour ∆z =1/ A’=(1,-1) et B’=(0,1)
Pour maximiser Z, on va faire glisser la droite de l’équation
∆z=0 vers le sens qui maximise le Z, de façon à garder au
moins un point d’intersection entre ∆z et le domaine de
définition.
 Ce dernier point de contact représente la solution optimale
 Théorème:
 La solution optimale d’un problème PL (lorsqu’elle existe) est
nécessairement dans l’un des sommets du polyèdre.

TG/PL- 2017/2018
 Etapes de résolution graphique d’un PL
75

 Déterminer la partie du plan qui satisfait les contraintes des

signes et des variables (contrainte non négativité)
 Les contraintes:
 Il s’agit de déterminer les zones correspondantes à la
satisfaction de chacune des contraintes (en traçant la droite
correspondante)
 puis d’en chercher l’intersection.
 Comme les contraintes sont généralement des inéquations
linéaires, la satisfaction de chaque contrainte entraine
l’élimination d’un demi plan.
 Généralement, l’intersection de tous les demi plans
satisfaisants les contraintes de système se présente soit
 sous forme d’un polygone convexe,
 un ensemble vide(si les contraintes sont incompatibles)
TG/PL- 2017/2018
 Etapes de résolution graphique d’un PL
76

 Première méthode:
 Déterminer les points optimaux
 Considérer la fonction objective Z= aX1+ bX2
 Les droites représentant cette fonction objective sont tous des
droites de l’équation
 aX1+bX2=k avec k R
 Toutes ces droites sont parallèles à la droite ∆z: (ax1+bX2=0)
 Dans un problème de maximisation, si:
 A>0 alors plus X1 est grand plus Z est grand
 Pour déterminer la valeur maximale de la fonction objective;
 il suffit d’effectuer une translation parallèle de la direction de
∆z=0 dans le sens qui maximise X1
 jusqu’au dernier points de contacte avec le domaine de définition
 Les points de contactes ainsi obtenu correspond au solution optimal
du PL
 Etapes de résolution graphique d’un PL
77

 Deuxième méthode:
 Sachant que la solution optimale d’un PL est représentée
par l’un des sommets du polygone dans R2, on peut
également trouver la solution optimale à partir du
graphique par recensement des sommets du polygone.
 Il est alors inutile de tracer ∆z et ces parallèles et il suffit
de chercher la valeur de Z correspondant à chaque sommet.
 Les points optimales dans un problème de maximisation est
le point pour lequel la valeur de la fonction objective est
maximale

TG/PL- 2017/2018
 Exemple de Résolution graphique:
78
Problème non borné:

TG/PL- 2017/2018
79 Programmation Linéaire
Méthodes de Résolution d’un PL

TG/PL- 2017/2018
80 Programmation Linéaire
Méthode de simplexe

TG/PL- 2017/2018
 Passage de la Forme Canonique à la
81
Forme Standard
 Les Contraintes
 Contraintes de type≤:
 X1+X2 ≤5  X1+X2+ e1=5
 On ajoute une variable d’écart: représente l’écart entre la
quantité disponible de la ressource et la quantité effectivement
utilisée
 Si la contrainte relative exprime une contrainte de stock, la variable
d’écart introduite représentera alors la quantité de stock non
consommée
 Cette quantité restante n’affecte pas la fonction objective
 La variable d’écart est multipliée par un coefficient nul dans la
fonction objective
 MaxZ= 2*X1+X2+0*e1

TG/PL- 2017/2018
 Passage de la Forme Canonique à la
82
Forme Standard
 Les Contraintes
 Contraintes de type≥:
 X1+X2 ≥ 5  X1+X2-S1=5
 On ajoute une variable de surplus
 Si la contrainte relative exprime une contrainte de demande, la
variable de surplus introduite représentera alors la quantité
excédentaire produite
 Son coefficient, dans la fonction objective, est nul
 MaxZ= 2*X1+X2-0*s1

TG/PL- 2017/2018
 Passage de la Forme Canonique à la
83
Forme Standard
 Les Variables:
 Pour passer à la forme standard, il faut que toutes les variables doivent
être non-négative (positives ou nulles)
 Cas d’une Variable Négative
 Forme générale:
 Max Z=4X1+5X2
 S/C X1-X2 ≤ 7
3X1+2X2 ≤12
X1≥0, X2≤0
 Si une variable Xi est négative dans la forme générale, on posera Xi’=-Xi et
on la remplace dans le PL.
 On pose X2’=-X2; X2’ ≥0
 Max Z=4X1-5X2’+0e1+ 0e2
 S/C X1+X2’+e1 = 7
3X1-2X2’+e2 =12
X1 , X2’ , e1,e2≥0

TG/PL- 2017/2018
 Passage de la Forme Canonique à la
84
Forme Standard
 Les Variables:
 Cas d’une Variable <>
 Max Z=4X1+5X2
 S/C X1-X2 ≤ 7
3X1+2X2 ≤12
X1≥0, X2 <>
 Si une variable Xi est quelconque dans la forme générale, on
posera Xi= Xi+-Xi- tel que Xi+≥0 Xi- ≥0 et on la remplace dans le
PL.
 On pose X2=X2+ - X2-≥0 avec X2+≥0 X2- ≥0
 Max Z=4X1-5 X2+ -5 X2- -0e1+ 0e2
 S/C X1+ X2+ - X2- +e1 = 7
3X1+2 X2+ - 2X2- +e2 =12
X1 , X2+,X2-, e1,e2≥0

TG/PL- 2017/2018
 Résolution Algébrique
85

 Notion de Base:
 Pour un PL standard constitué de n variables et m contraintes avec n ≥ m
alors
 une Solution de Base est obtenue en
 annulant (n-m) variables et
 en résolvant les m contraintes pour déterminer les valeurs des autres m variables
 Les n-m variable nulles sont dite variables Hors Base et les autres variables
(pouvant être ≥0) sont dites variables de base
 Une solution de base est une solution qui satisfait les contraintes et possède
au moins (n-m) variables
 Une solution de base, qui n’est pas toujours réalisable, est dite Réalisable de
Base, elle satisfait:
 Les contraintes de PL
 Les contraintes de non négativité
 Tout point extrême de l’ensemble des solutions réalisables, correspond à une
solution Réalisable de Base

TG/PL- 2017/2018
 Résolution Graphique
86

 Etapes de réalisation graphique

 Ajouter des variables d’écart et de surplus pour passer
à des équations linéaires (passer à la forme standard)
 Partir d’une Solution Réalisable de Base (SRB) vers une
autre solution meilleur (la fonction objective)
 Tant qu’on n’est pas encore à l’optimalité, on doit
chercher une nouvelle solution réalisable de base qui
améliore la fonction objective

TG/PL- 2017/2018
 Résolution Graphique
87

 Exécution
 Max Z=5X1+4X2+3 X3
 S/C 2X1+3X2+X3≤5
4X1+X2+2X3 ≤11
3X1+4X2+2X3≤8
X1,X2,X3≥0

TG/PL- 2017/2018
 Résolution Par La Méthode De Simplexe
88

 Exemple Introductif:
 Max Z= 5X1+4X2+X3 +0e1+0e2+0e3
 S/C: 2X1+3X2+X3+e1=5

4X1+X2+2X3+e2=11
3X1+4X2+2X3+e3=8
X1,X2,X3,e1,e2,e3≥0

TG/PL- 2017/2018
 Résolution Par La Méthode De Simplexe
89

TG/PL- 2017/2018
 Résolution Par La Méthode De Simplexe
90

 Passage À La Forme Canonique Par Rapport À Une Base:

 Les Variables
 Cas d’une variable négative Xi≤0
 On pose Xi’=-Xi Xi’ ≥0
 Cas d’une variable quelconque Xi qq
 On pose Xi=Xi+ -Xi-  Xi ≥0 , Xi- ≥0
 Cas où la valeur du second nombre d’une contrainte est négative

FG FCB
Max Z= 2X1+X2 Max Z= 2X1+X2
S/C X1-3X2 ≤-3 S/C -X1+3X2 ≥ 3
X1,X2 ≥0 X1,X2 ≥0
 Résolution Par La Méthode De Simplexe
91

 Passage À La Forme Canonique Par Rapport À Une Base :

 Cas d’une contrainte de type ≤
FG FCB
Max Z= 2X1+X2 Max Z= 2X1+X2+0e1
S/C X1+X2 ≤5 S/C X1+X2+e1=5
X1,X2 ≥0 X1,X2, e1 ≥0
 Cas d’une contrainte de type ≥
FG FCB
Max Z= 2X1+X2 Max Z= 2X1+X2+0S1- Ma1
S/C X1+X2 ≥5 S/C X1+X2-S1+a1=5
X1,X2 ≥0 X1,X2, e1 ≥0

TG/PL- 2017/2018
 Résolution Par La Méthode De Simplexe
92

 Passage À La Forme Canonique Par Rapport À Une Base :

 Cas d’une contrainte de type =
FG FCB
Max Z= 2X1+X2 Max Z= 2X1+X2+Ma1
S/C X1+X2 =5 S/C X1+X2+a1=5
X1,X2 ≥0 X1,X2, a1 ≥0

TG/PL- 2017/2018
 Résolution Par La Méthode De Simplexe
93

 Différents cas de résolution par la méthode de

Simplexe
 Problème de Minimisation
FG FCB
Min Z= 10X1+7X2+12X3 MinZ=10X1+7X2+12X3+0S1+Ma1+0S2+Ma2
S/C X1+X2 ≥2 S/C X1+X2 ≥2
X2+X3 ≥1 X2+X3 ≥1
X1,X2,X3 ≥0
X1,X2,X3,S1,S2,a1,a2 ≥0
 Résolution Par La Méthode De Simplexe
94

 Différents Cas De Résolution Par La Méthode De

Simplexe
 Problème non borné
 Résolution Par La Méthode De Simplexe
95

 Différents Cas De Résolution Par La Méthode De

Simplexe
 Problème à solution multiple
 Résolution Par La Méthode De Simplexe
96

 Différents Cas De Résolution Par La Méthode De

Simplexe
 Problème non Réalisable
 Résolution Par La Méthode De Simplexe
97

 Différents Cas De Résolution Par La Méthode De

Simplexe
 Problème à solution dégénérée
 Résolution Par La Méthode De Simplexe
98

 Représentation Matricielle Des Tableaux De

Simplexe
99 Programmation Linéaire
Dualité et Analyse de post optimalité

TG/PL- 2017/2018
 Dualité
100

 Pour tout PL ayant une solution optimale finie, il

existe un PL appelé dual ayant une solution
optimale tel que Z*p=Z*D
 Généralement, à tout programme linéaire appelé
PRIMAL est associé un programme linéaire appelé
DUAL tel que:
 le nombre de contraintes dans P est égale au nombre
de variables dans D
 Le nombre de variables dans P est égale au nombre de
contraintes dans D

TG/PL- 2017/2018
 Dualité
101

Primal Dual
Fonction Objective à Maximiser Fonction objective à Minimiser
J ème contrainte de type ≥ J ème variable de type ≤ 0
J ème contrainte de type ≤ J ème variable de type ≥ 0
J ème contrainte de type = J ème variable de type < >
I ème variable de type ≥ 0 I ème contrainte de type ≥
I ème variable de type ≤ 0 I ème contrainte de type ≤
I ème variable de type < > I ème contrainte de type =

 Exemple:
 MaxZ=5X1+3X2+X3 Min Z=6y1+2y2
 S/C 2X1+X2+X3 ≤6  S/C 2y1+2y2 ≥5
 X1+2X2+X3≥2 Y1+2y2 ≥3
Y1+y2=1
 X1≥0 X2≥0 X3<>
y1 ≥0 y2 ≤0
TG/PL- 2017/2018
 Dualité
102

 Les coefficients des variables dans Z dans (D) sont

les parties droites des contraintes dans le problème
primale et vise versa
 Théorème:
 Le dual du Dual est le primale
 Exemple:
 Reproduire l’exemple précédent et essayer de trouver
le dual du dual

TG/PL- 2017/2018
 Dualité
103

 Théorème des écarts complémentaires

A l’optimalité, le produit d’une variable principale
primale et la variable d’écart dual de la contrainte
correspondante est nulle
 Le produit d’une variable d’écart primale et d’une
variable principale est nul
 Exemple:

TG/PL- 2017/2018
 Analyse de la poste optimalité
104

 Changement du coefficient d’une variable de la

fonction objective
 Cas variable hors base

 Cas d’une variable de base

TG/PL- 2017/2018
 Analyse de la poste optimalité
105

 Changement de la partie droit d’une contrainte

 Sila contrainte est toujours satisfait, la base optimale
ne change pas

TG/PL- 2017/2018