République Algérienne Démocratique et Populaire

Ministère de l’Enseignement Supérieur et de la Recherche Scientifique

Université des Sciences et de la Technologie Houari Boumediene

Faculté de Mathématiques

Département de Recherche Opérationnelle

Mémoire
En vue de l’obtention du Diplôme de Licence
En Recherche Opérationnelle

Thème :

Problème de la tension maximum

• Présenté par : AFNES Imen

NEMIR DOUAOUDA Chaïma

• Encadré par : Mme A. HISSOUM

Juin 2020
 Table des matières :

Introduction 6
1. Chapitre 1: la programmation linéaire 7
1.1 Introduction ...………………………………………………………………………... 8
1.2 Aperçu historique ……..……………………………………………………………. 8
1.3 Définition ……………………………………………………………………………. 8
1.4 La formulation d’un programme linéaire ……………………………………………. 8
1.4.1 La modèlisation d’un programme linéaire …………………………………… 8
1.4.2 Les différentes formes d’écriture d’un programme linéaire …………………. 8
1.4.2.1 Forme standard…………………………………………………………… 8
1.4.2.2 Forme canonique…………………………………………………………. 9
1.5 La résolution d’un programme linéaire ……………………………………………… 9
1.5.1 La résolution graphique……………………………………………………… 9
1.5.2 La résolution avec la méthode de simplexe ………………………………….. 9
1.5.2.1 Notion de base …………………………………………..……………… 9
1.5.2.1.1 Rappelle de la définition d’une base …………………………….. 10
1.5.2.1.2 Changement de base dans un programme linéaire ………………. 10
1.5.2.1.3 Variable de base et variable hors base …………………………… 10
1.5.2.1.4 Base optimale ……………………..……………………………. 10
1.5.2.1.5 Base réalisable ……..…………………………………………… 10
1.5.2.1.6 Notion de pivotage ………………………………………………. 10
1.5.3 Les étapes de l’algorithme de simplexe ………………………………………10
1.5.4 Algorithme de simplexe de deux phases …………………………………….. 12
1.6 Conclusion ………………………………………………………………………… 12
2. Chapitre 2 : Problème de la tension maximum 13
2.1. Introduction ………………………………………...……………………………… 14
2.2. La théorie des graphes ……………………………………………………………… 14
2.2.1. Définitions et notions de base ……………………………………………….. 14
2.3. Présentation de problème de la tension maximum …………………………………. 15
2.3.1.1. Définition de problème ……………………………………………… 15
2.3.1.2. La modélisation de problème sous forme d’un PL ………………..... 16
2.3.1.2.1. La formulation du dual de problème ………………………… 16
2.3.1.3. La résolution de PL associé au problème …………………………… 17
2.3.1.3.1. Exemple …………………………………………………….. 18
2.4. Conclusion ………………………………………………………………………. 19
3. Chapitre 3 : implémentation de problème de la tension maximum. 20
3.1. Introduction ………………………………………………………………………… 21
3.2. Le code source de programme ……………………………………………………... 21
Conclusion générale 24
Bibliographie 25

2
 Remerciement :

Au terme de cette étude, nous tenons à remercier le bon dieu qui nous
a donné le courage et la volonté d’aller jusqu’au bout.
Au terme du présent travail, nous tenons à remercier tout d’abord et
exprimer nos sincères remerciements à l’égard de : Mme Hissoum
qui nous a encadrer et diriger par ses conseils et ses orientations.
Merci pour tous les professeurs, intervenants et toutes les personnes
qui par leurs paroles, leurs écrits, leurs conseils et leurs critiques ont
guidé nos réflexions et ont accepté à répondre à tous nos questions
durant notre recherche.
Enfin, à celle et ceux qui ont apporté leur aide pour la réalisation de
ce travail trouvent ici notre profonde sympathie.

3
 Dédicace :

Je dédie ce modeste travail :

À mes chers parents qui chers parents qui m’ont comblé d’amour et
d’affection, qui m’ont toujours encouragé pour achever mes études
tout en espérant voir le fruit de leurs sacrifices. Qu’Allah les garde
pour moi sains et saufs.
À mon frére, mes sœurs et toutes ma famille. À mon binôme Chaïma
qui à été active et très ambitieuse.
Et en fin à tous ceux qui m’aiment.

Imen.

4
 Dédicace :

Aux deux personnes que j’aime le plus au monde, mes chers parents
pour tous leurs sacrifices, leur amour, leur tendresse, leur soutien et
leurs prières tout au long de mes études.
À mes deux chers frères pour leurs encouragements permanents et
leur soutien morale.
À tous les membre de ma famille qui m’ont soutenu tout au long de
mon parcours universitaire.
À ma meilleur amie Selma qui a toujours été là pour moi, à mon
binôme Imen pour tous ses efforts et sa patience.
Que ce modeste travail soit l’accomplissement de vos vœux tant
allégués et le fruit de votre soutien infaillible.

Chaïma.

5
 Introduction :

La recherche Opérationnelle doit son nom à son application aux opérations militaires au
seconde guerre mondiale, et même si l’appellation est plus au moins nouvelle la démarche
est ancienne. Ce n’est pas qu’aujourd’hui que l’homme cherche à optimiser les résultats
qu’il peut obtenir, dans des conditions déterminées et pour peu qu’il appelle l’esprit
scientifique à son secoure, il fait de la recherche opérationnelle sans le savoir. Mais c’était
qu’en 1938 que Sir Blackett a constitué le premier groupe de la recherche opérationnelle
défini à la fois la déontologie et la structure générale d’une équipe consacrée à cette
discipline.
La recherche opérationnelle c’est la mise en œuvre des méthodes scientifiques
essentiellement mathématiques, en vue d’analyser des situation complexes pour permettre
aux décideurs de faire des choix efficaces et robustes. Elle fournit des outils pour
rationaliser, simuler et optimiser le fonctionnement des systèmes industrielles et
économiques. Cette science s’attaque essentiellement aux problèmes qui constituent un défi
pour le sens commun qui se résument en trois types principaux : combinatoires, aléatoires
ou concurrentiels.
L’utilité et les champs d’exploitation de cette discipline n’ont fait que croitre au fils des
décennies : de l’organisation des lignes de production d’automobiles à la planification des
missions spatiales, de l’optimisation des portefeuilles bancaires à l’aide au séquençage de
l’ADN, de la gestion des stocks au plans d’acheminement pour des marchandises ou des
personnes… mais aussi dans la vie quotidienne de tous les jours pour le recyclage des
déchets, l’organisation de ramassages scolaire, les emplois du temps des infermières ou la
couverture satellite des lignes téléphoniques…
L’expert en RO exploite des connaissances provenant des sources très variées,
particulièrement mathématiques, il s’agit des méthodes qui constituent la boite à outils de
notre expert, à savoir la programmation linéaire qui a une relation directe avec la recherche
opérationnelle.
Le premier chapitre de ce mémoire est consacré à la définition de la programmation
linéaire, ses éléments de base et ses méthodes des résolutions.
À côté de la programmation linéaire figure la théorie des graphes qui est fréquemment
utilisée pour représenter des réseaux ou des schémas mais son utilisation dépasse largement
ce cadre, en effet, la théorie des graphes offre également des possibilités de modélisation
très riches (flux de transport, les problèmes d’ordonnancement, les problèmes de tension...).
Le deuxième chapitre de ce mémoire est consacré à la modélisation de l’un des problèmes
importants de la théorie des graphes `le problème de la tension maximum`.
Au fils des années, avec l’évolution de la technologie et l’insertion de l’informatique
dans de nombreux domaines, plusieurs solveurs de résolution des programmes linéaires sont
apparus. Dans le troisième chapitre de ce mémoire une l’implémentation de problème de la
tension maximum est abordée à travers un de ses solveurs, et à la fin de ce travail une petite
conclusion est insérée pour résumer ce qui a été présenté dans les chapitre précédents.

6
 Chapitre 01 :

La programmation linéaire

7
 Chapitre 01 : la programmation linéaire
Introduction :
Produire les meilleures décisions par une approche quantitative de la recherche
opérationnelle nécessite la variété des connaissances de l’expert en RO. En effet, les
acquisitions exploitées proviennent de différents domaines : mathématiques appliqués,
informatique.…
Sous le terme de mathématiques appliqués, on trouve en particulier La programmation
linéaire, en variables réelles ou entières, qui est intimement liées à l’histoire de la
recherche opérationnelle puisque c’est la suite de la création de la 1ere méthode de
résolution efficace de la programmation linéaire.
Aperçu historique : L’histoire de la programmation linéaire a commencé avec les
premiers mathématiciens qui se sont occupés de problèmes, que l’on ne nommait pas
encore à l’époque `programmes linéaires` sont : Laplace et le baron Fourier. En 1939 le
russe Kantorovitch a imaginé une méthode inspirée des multiplicateurs de Lagrange,
classiques en mécanique pour résoudre des programmes de transport. La contribution
décisive a été l’invention de l’algorithme de simplexe, développé à partir de 1947
notamment par G.B. Dantzig et le mathématicien Von Neumann et c’est au milieu des
années 80 que l’indien Karmarkar a proposé une nouvelle méthode crée aux Bell
Laboratoires qui permettait de résoudre de très gros problèmes linéaires, par une démarche
intérieure au polyèdre des solutions admissibles.
Définition : La Programmation Linéaire est un cadre mathématique général permettant de
modéliser et de résoudre certains problèmes d'optimisation. Mathématiquement le
problème consiste à Optimiser (maximiser ou minimiser) une Fonction Linéaire sous des
Contraintes également Linéaires ayant la forme d'inéquations liant des variables, elle vise
à sélectionner parmi différentes actions celle qui atteindra le plus probablement l'objectif
visé.
La formulation d’un PL:
1. La modélisation d’un problème linéaire : La modélisation d’un problème linéaire
consiste à identifier :
Les variables de décisions : Ce sont des symboles mathématiques qui représentent une
quantité physique pour le but de résoudre le problème.
Les contraintes : Ce sont des combinaisons linéaires qui représentent les limitations et les
restrictions auxquelles sont soumises les variables de décisions. Elles peuvent être de type
d’inégalité supérieur, inégalité inférieur ou égalité.
La fonction objectif : Appelée aussi critère de performance ou fonction économique,
c’est la fonction qui détermine l’optimum qu’il soit le maximum ou le minimum selon le
problème traité. Elle s’exprime sous forme de combinaison linéaire de variables de
décisions comme suite :
Max/Min (Z) = ∑Ci Xi Max/Min(Z)= C1X1 + C2X2 +…+ CnXn
Où les coefficients C1,…,Cn doivent avoir une valeur réelle bien déterminée.
2. Les différentes formes d’écritures d’un PL : La résolution d’un PL se fait avec
plusieurs méthodes nécessitant parfois le changement de la forme sous laquelle le PL est

8
 écrit, en effet, un PL peut être mis sous différentes formes équivalentes par des
manipulations appropriées :
• la forme standard :un PL est sous forme Standard si :
- Toutes les variables sont positives (Xi≥0, i=1, …, n).
- Toutes les contraintes sont de type d’égalité (ne contient pas des contrainte sous forme
d’inégalité).
- Le problème est de maximisation ou minimisation.
Son écriture matricielle générale est comme suite :
Max /Min (Z) = C X (produit vectorielle < 𝐶 𝑋 >)
(Ps) 𝐴𝑋=𝑏
Xi ≥ 0 , i=1, … , n .
Où : A est une 𝑚 × 𝑛 matrice (m le nombre de contrainte et n le nombre d’inconnues), b
est un vecteur à 𝑚 composantes appelé le second membre, C est un vecteur à 𝑛
composantes appelé le vecteur des coûts et X est un vecteur à 𝑛 composantes représentant
les variables ( les inconnues).
• La forme canonique : un PL est sous forme canonique si :
- Toutes les variables sont positives.
- Toutes les contraintes sont de type inégalité supérieure `≤` (resp. Inégalité inférieur `≥`)
i.e : pas de contrainte sous forme d’égalité.
- Le problème est de maximisation (resp. Minimisation).
Son écriture matricielle est comme suite :
Max (Z)= C X Min (Z)= C X
(Pc ) 𝐴𝑋≤𝑏 ou : (Pc) 𝐴𝑋≥𝑏
Xi ≥ 0, i=1,…,n Xi ≥ 0, i=1,…,n
Remarque : le passage de la forme canonique au forme standard se fait en ajoutant (ou
soustrayant) des variables qu’on les nomme ‘les variables d’écart` aux inégalités `≤` (aux
inégalités `≥`) pour les transformer en contrainte de type égalité ` = `.
3. La résolution d’un programme linéaire :
A) La résolution graphique :
Cette méthode géométrique est applicable qu’aux PL ayant un nombre de variables au
plus égale à 3.
Le principe de cette méthode consiste à formuler graphiquement les contraintes en traçant
des droites sur un plan, la région d’intersection représente le domaine réalisable `D`qui
contient toutes les valeurs qui vérifient le programme linéaire, et ensuite tracer le vecteur
de la fonction objectif pour enfin déterminer le point optimum qui appartient bien
évidement au domaine réalisable D formé par les droites des contrainte.
B) La résolution avec la méthode de simplexe :
Dite aussi l’algorithme de simplexe, il a été développé par le mathématicien américain
Georges Dantzig (1914-2005) et le mathématicien physicien américano-hangrois John
Neuman (1903-1957) à partir de 1947, puis été perfectionné au fil des années pour
accroitre la précision des résultats.
Notions de base :

9
 Avant que l’algorithme de simplexe puisse être appliqué pour résoudre le programme
linéaire, ce dernier doit être converti en un Ps (i.e doit être transformé au forme standard).
Rappelle de la définition d’une base : soit A une 𝑚 × 𝑛 matrice associée à un system
d’équation, une base J est un sous ensemble de colonnes de A linéairement indépendantes.
On note AJ la matrice associée au système dans la base J (la matrice A écrite dans la base
J).
Changement de base dans un programme linéaire : un PL est dit ``écrit sous forme
canonique par rapport à une base J`` si les deux conditions sont vérifiées :
a) AJ est une permutation près des colonnes de la matrice unité.
b) CJ=0.
Après l’effectuation du changement de base, le PL devient :
(PL)~(Pc) 𝐴̃X = 𝑏̃ avec : 𝐴̃ = (AJ)-1 A ; 𝑐̃ = c - cJ (AJ)-1 A ;
𝑐̃ X = Z(max) -𝜶 𝑏̃ = (AJ)-1 b ; 𝜶 = cj (AJ)-1 b =𝜋b ;
Variable de base et variable hors base : considérons un système d’équation a n
variables et m équations où n≥ 𝑚, une solution de base pour ce système est obtenue de
maniérer suivante :
- On pose n-m variables égale à 0, Ces variables sont appelées variable hors base.
- On résout le système pour les m variables restantes, ces variables sont appelées les
variables de base.
- Le vecteur de variable obtenue est appelé solution de base (il contient les variables de base
et hors base).
Base réalisable : soit J une base, si la solution XJ de PL associée à la base J est ≥ 0 alors
J est dite base réalisable et XJ est une solution réalisable de base du PL
Base optimale : soit J une base réalisable d’un PL. Si le vecteur coût relatif à J est négatif
ou nul pour un problème de maximisation (resp. Positif ou nul pour un problème de
minimisation), alors la base J est optimale et la solution de base associée à J est une
solution optimale de base du PL.
Notion de pivotage : le principe de pivotage est de changer une variable de base X k par
une variable hors base Xs dans 𝐴̃X = 𝑏̃ de sorte que XS devienne une variable de base et
Xk quittera la base sans que les autres variables de base quitte la base. X S est appelée
variable entrante, tandis que Xk est la variable sortante. Pour que cet échange soit
possible il faudrait que dans le système l’équation r contenant la variable X k où 𝐴̃rK =1 (la
ligne r, colonne k dans 𝐴̃) contienne aussi la variable XS avec un coefficient 𝐴̃rS ≠ 0 (dans
le cas contraire J’=J ∪ {𝑠}\{k} n’est pas une base !). L’élément 𝐴̃rS est le pivot par rapport
auquel le pivotage s’effectue en suivant les ces opérations :
1- On divise la ligne du pivot (i.e : la ligne r de 𝐴̃) par le pivot,
2- On élimine la variable Xk de toutes les autres équations (sauf l’équation r) en remplaçant
Li par Li – ( 𝐴̃iS ÷ 𝐴̃rS )Lr , pour tout i∈{i….m}\{r}.

Les étapes de l’algorithme de simplexe :

Le principe de simplexe se base à passer itérativement d’une solution de base réalisable X
à une solution de base voisine X’, en laquelle la valeur de Z est plus élevée partant d’un
point X0. Ses étapes peuvent être résumés en schéma suivant :

10
 Tableau initial

Solution oui
Optimale Stop

Pivotage Non
Choix de la variable entrante

Choix de la variable sortante

1- Etape 1 (tableau initial) : se construit de manière suivante :

X1 X2 ………. XN bi

Case correspondante aux coefficients des

Contraintes du Ps

Case correspondante aux coefficients de la

Z fonction objectif
Cj-
Zj
Case violet correspondante à l’emplacement des variables de base.
Case verte correspondante aux coefficients du vecteur bi (second membre).
Remarque : la case jaune contient toutes les variables de Ps (avec les variables d’écart si
elles existent).

2- Étape 2 (le choix de la variable entrante) : le choix se fait en cherchant le Max ( resp.
Min) des Cj-Zj pour un problème de maximisation (resp. Minimisation) la variable
entrante c’est la colonne correspondante à la valeur max (resp. Min) trouvée.
3- Étape 3 (Le choix de la variable sortante) : il s’agit de trouver le minimum entre les Li
où : Li= {| bi/ai,k | } , ai,k le coefficient de la i ème ligne k ème colonne (la colonne k est
supposée celle de la variable entrante trouvée dans l’étape 2), la variable sortante c’est la
ligne correspondante à la valeur min trouvée.
4- Étape 4 le pivotage.
5- Critère d’arrêt : les itérations de l’algorithme s’arrêtent lorsque l’optimum est atteint i.e
lorsque :
→ Cj-Zj ≤ 0 pour un problème de maximisation.
→ Cj-Zj≥ 0 pour un problème de minimisation.
Remarque : dans certains cas le system linéaire Ax=b n’est pas nécessairement de plein
rang, la redondance peut avoir lieu, l’ensemble des solutions peut être vide… Dans ce

11
 genre de situation on n’aura pas une solution réalisable de base pour commencer
l’algorithme de simplexe donc c’est la méthode de 2 phase qui sera appliquée.

Algorithme de simplexe de 2 phases :

Cette méthode permet de passer de la forme standard d’un PL (appartenant aux systèmes
linéaires mentionnés dans la remarque précédente) à l’écriture S.F.C% à une base
réalisable J, si une telle base existe et c’est d’ailleurs l’objectif de la phase 1.
Phase 1 : cette phase consiste à associer au PL le programme dit `programme auxiliaire`,
Ensuite lui appliquer le simplexe. Le programme auxiliaire est défini comme suit :
Ax + Uv = b.
(PA) ∑𝑣 i = 𝜓(min) , i=1,…m. Avec : U est la 𝑚 × 𝑚 matrice
unité.
X≥ 0 , v≥ 0
Les variables vi, i=1,…m sont dites ` variables artificielles` elles représentent l’écart
entre bi et AiXi qui doit être annulé pour que X (solution réalisable de PA) soit solution
réalisable de (PL) .
Phase 2 : appliquer l’algorithme de simplexe au programme linéaire PL initiale sous sa
forme obtenue à la fin de la phase 1.

De façon générale la méthode de simplexe de 2 phase se fait comme suit :

On commence d’abord par écrire le PL sous forme standard, ensuite on multiplie par -1
les équations dont le second membre est négatif, par la suite on ajoute des variables
artificielles aux équations nécessitant cet ajout i.e les équations de type `≥` (resp. ` ≤`)
pour un problème de maximisation (resp. Minimisation) et on aura un PL auxiliaire PA
associé à P ainsi qu’une solution réalisable de base qui nous permets d’applique la phase 1
de simplexe sur PA.
À la fin de la phase 1, une solution réalisable de P initial est recueillie et on pourra donc
passer à la phase 2 de simplexe qui sera appliqué sur le dernier tableau obtenu à la fin de
la phase précédente mais en supprimant d’abord les variables artificielles ajoutées et en
remplaçant la fonction objectif W de PA par la fonction Z de P.
On effectue le pivotage pour améliorer la valeur de Z à chaque itération, jusqu’à atteindre
l’optimalité (revoir les critères d’arrêt de simplexe).

Conclusion : La programmation linéaire est un outil d’analyse économique couramment

utilisé qui a permis à de nombreuses entreprises d’économiser des milliers ou des millions de
dollars grâce à ses méthodes de résolution précises, en particulier l’algorithme de simplexe.
Son efficacité réside dans sa précision et son adaptation avec tous types de problème linéaires.
Et même avec l’apparition de plusieurs nouvelles techniques de résolution modernes
essentiellement informatique, l’algorithme de simplexe est toujours l’outil le plus utilisé dans
nos jours et cela révèle son importance.

12
 Chapitre 02 :

Problème de la tension maximum

13
 Chapitre 2 : Problème de la tension maximum

Introduction :
La représentation graphique par un dessin, un plan, une esquisse contribue souvent à la
compréhension, c’est sur ce principe que la discipline théorie des graphes est construite.
En effet La théorie des graphes est l’une des branches des mathématiques discrètes et
d’informatique, elle représente un instrument très utile et efficace pour modéliser et
résoudre beaucoup de problèmes pratique dans plusieurs domaines tel que les problèmes
posés en Recherche opérationnelle. En générale cette discipline constitue donc une
méthode de pensée qui permet de formaliser une variété des problèmes (des problèmes de
réseau de communication, réseau de transport, arbre généalogique, diagramme de
succession de tâches en gestion de projet…) en se ramenant à l’études d’un graphe.

Définitions et notions de base de la théorie des graphes :

- Un graphe orienté noté G est un couple formé de deux ensembles non vides X et U liés
par une application mathématique, cette relation est notée `G= (X, U) `, tel que :
a) X= {x1, x2, ..., xn} dont les éléments sont appelés `sommet`, son cardinale |X|= n
représente le nombre de sommets de G, n est appelé` l’ordre` du graphe.
b) U= {u1, u2, ..., um} dont les éléments sont appelés `arcs’, son cardinale |U| = représente
le nombre d’arcs de G, m est appelé `la taille’ du graphe.
G est habituellement représenté par une figure dans le plan, où les sommets sont représentés
par des points et les arcs par des flèches entre les sommets.
- Un graphe G est dit simple, si G ne contient pas d’arcs multiples et pas de boucle (un arc
d’un somment xi vers lui-même).
- On appelle une matrice incidence sommets – arcs dans un graphe G orienté avec |X| = n
et |U| = m, la matrice notée M(G) ou E, dont les lignes et les colonnes sont indicés
respectivement par les sommets et les arcs définie par :
+1 si xi=I(u) Avec :
-I(u) représente l’extrémité initiale de l’arc u.
E = (ei,j) = -1 si xi=T(u) -T(u) représente l’extrémité terminale de u.
1≤ i≤ n, 1≤j≤ m
0 si u est une boucle
Un arc u est dit incident à un sommet xi, si xi est l’une de ses extrémités et xi est dit
incident à u.
- Soit G= (X, U) un graphe orienté, d : U →R est une application qui associe à chaque arc ui
∈ U une longueur noté d(u) et appelée distance, poids d’arc… , dans ce cas on détermine
le réseau R et on le note R = (X, U, d), autrement dit : R= (G, d).
- Soit R= (X, U, d) réseau, 𝜋 : X → R est une application qui associe à chaque sommet xi ∈
X une valeur qui représente la distance entre un sommets donnée s et le sommet x i, cette
fonction est appelée fonction potentiel de x noté 𝜋(x).
- Soit R= (X, U) un réseau avec |U|=m et |X|=n, et soit E la matrice d’incidence sommet-arc
associée à R, on définit l’application t qui attribue à chaque arc ui de R (reliant xi à yi tel
que I(u)=xi et T(u)=yi) une valeur de manière suivante :
tui = 𝜋(yi) - 𝜋(xi) , t est appelée une tension.

14
- Un chemin P reliant un sommet x0 à un sommet xp dans un graphe G = (X, U), est une
suite alternée de sommets et d’arcs : P = x0u1x1u2x2 …xp-1upxp tel que pour tout 1 ≤ i≤ p,
ui = (xi-1,xp). Si de plus le chemin P est fermé i.e : P`=Pup+1x0 , P` est appelé donc un
circuit noté C .
- La longueur d’un chemin P dans un réseau R = (X, U, d) est égale à la somme des
longueurs des arcs qui constituent le chemin P : L(P) =∑𝑢∈ P 𝑑(𝑢).
- On dit un plus court chemin d’un sommet x à un sommet y la longueur de plus court
chemin reliant x à y, ça représente aussi la plus courte distance de x à y.
Remarque : La plus courte distance d’un sommet à lui-même est nulle.
- Un circuit C est dit circuit absorbant dans un réseau R = (X, U, d) si sa longueur est
négative (resp. Positive) i.e :∑𝑢∈𝐶 𝑑(𝑢) < 0 (resp. ∑𝑢∈𝐶 𝑑(𝑢) > 0 ) dans le cas d’un plus
court chemin (resp. Plus long chemin).
- Un sommet x est appelé racine dans R = (X, U, d) noté s si et seulement si ∀ x ∈ X\s il
existe un chemin P de s à x, autrement dit il existe un chemin P de s vers tous les sommets
restants de R.
- G’= (U`, X) est dit arborescence si :
→ G’ n’a qu’un seule sommet d’entré ‘le sommet racine s’ (i.e : un sommet n’ayant
pas de prédécesseur).
→ Il existe un chemin, et un seul de s à tout autre sommet du graphe.

Présentation de problème de la tension maximum :

La théorie des graphes est un domaine très vaste, en effet de nombreux problèmes discrets
peuvent être modélisés par des graphes, dans ce chapitre on s’intéresse particulièrement au
problème de la tension maximum. C’est un problème qui s’impose souvent dans la vie
quotidienne car il constitue la base de tous les problèmes de planifications d’itinéraire comme:
certains problèmes d’investissement et de gestion de projet, problèmes de tournées, certains
problèmes liés au domaine des réseaux routiers ou de télécommunication, problème de
traitement numérique de signale de codage ou décodage d’information… il a d’ailleurs donné
lieu au développement des sites internet qui propose de déterminer pour les utilisateurs le
meilleur itinéraire que ce soit en distance, en temps ou en coût….
Définition de problème :
Soit R= (X, U, d), |U|=m. Le problème de la tension maximum entre les sommets s et x i (xi∈
𝑋 − {𝑠}) dans R consiste à trouver un vecteur t ∈ ℝm tel que :
i. t est une tension sur G= (X, U) i.e : ∃ 𝜋 : X →R tel que t(u) = 𝜋(T(u)) - 𝜋(I(u)) ∀ u∈ U.
ii. t(u) ≤ d(u) ∀ u∈ U.
iii. 𝜋 (s) - 𝜋(xi) soit maximum.
Remarque : Dans la théorie des graphes il existe des algorithmes efficaces pour résoudre le
problème de la tension maximum, or que dans ce chapitre on s’intéresse à la résolution
mathématique.
La modélisation de problème sous forme d’un PL :
Soit un réseau R =(X, U, d) et soit E la matrice d’incidence sommet-arc associé à R , le
problèmes de la tension maximum a pour objectif de trouver une fonction potentiel 𝜋 : X →R
tel que la différence des potentiels aux sommets xi et s soit la plus grande possible (pour tout

15
xi∈ 𝑋 − {𝑠}) sous réserve que la différence de potentiel des extrémités de chaque arc soit
inférieure ou égale à la longueur de cet arc, autrement dit qu’il s’agit d’un problème de
maximisation de la tension entre deux sommets s et xi sous contraintes que la tension sur
chaque arc ne dépasse pas la longueur de l’arc concerné.
Ce problème peut être modélisé de maniérer suivante :
1-On définit d’abord la variable de décision 𝜋(𝑥 i) ` représente le potentiel de sommet xi avec :
i=1,…,n.
2-Pour les contraintes, en plus de la condition qui exige que le potentiel de sommet s soit nul,
on associe à chaque arc de R une tension tout en respectant les conditions imposées, donc si
on parcourt tous les arcs de R on aura le système suivant :

tu1 = π(y1) - 𝜋(x1) ≤ d1 tj= Aj,i × 𝜋i ≤ d , 1≤ 𝑗 ≤ 𝑚 ,1≤ 𝑖 ≤ 𝑛

tu2 = 𝜋(y2) - 𝜋(x2) ≤d2 son écriture matricielle : tel que: -Aj,i est une matrice à m ligne
tu3= 𝜋(y3) - 𝜋(x3) ≤ d3 et n colonne.
… - 𝜋i est un vecteur à n composante.
tum = 𝜋(ym) - 𝜋(xm) ≤dm -tj et dj sont 2 vecteurs à m composante.

La matrice Aj,I qui a les arcs de R comme lignes et ses sommets comme colonnes ce n’est que
la transposée de la matrice d’incidence sommet-arc de R multipliée par `-1` (-Et), alors
l’application tension peut aussi se dèfinir comme suit:
t une tension dans R ⟺ ∃ 𝝅 ∈ 𝑹 , − 𝑬t 𝝅 = t .
3-La fonction objectif Z consiste à maximiser la somme des potentiels des sommets de R.
On aura donc un PL modélisant ce problème qui se présente comme suit :
𝜋(s)=0
(T Max) -Et 𝜋 ≤ 𝑑
∑𝑥∈𝑋 𝜋(𝑥) =Z (max)

(T Max) admet une solution optimale 𝜋* si et seulement si les conditions suivantes sont
réalisées :
i) R ne contient pas de circuit absorbant (preuve : soit 𝜋 une solution de T Max, en
sommant les inéquations 𝜋(T(u)) - 𝜋(I(u)) ≤d(u) sur tous les arcs u∈ 𝜋, on obtient : 0 ≤
∑𝑢∈𝜋, 𝑑(𝑢). Donc R ne contient pas de circuit absorbant si 𝜋 est une solution réalisable).
ii) s est une racine dans R .
iii) Si c’est le cas, alors 𝜋* représente un plus court chemin de sommet s à xi ∈ 𝑋 − {𝑠} dans
R, et G’=(X, U’) le graphe partiel, avec U’= { u∈ U / 𝜋*(T(u) ) - 𝜋*(I(u)) = d(u)
}représente une arborescence des plus court chemin de s à tous les autre sommets de R.
De façon générale, trouver une tension maximum entre deux sommets s et les autres sommets
d’un réseau revient à chercher un plus court chemin de s à eux.
La formulation du dual de T Max : le dual (D) de ce problème consiste à choisir l’ensemble
d’arcs de longueur totale minimal, pourvu que les arcs composent un chemin de s à tous les
autres sommets de R, et on peut le formuler comme suit :

16
-La variable de décision Xi,j de (D) est une variable booléenne qui représente `l’arc reliant le
sommet xi au sommet xj` Xi,j = 1 signifie que l’arc reliant xi à xj est pris , Xi,j = 0 signifie que
l’arc reliant xi à xj n’est pas pris. Avec i=1, ..., n et j=1, …, m.
-Les contraintes s’obtiennent en faisant le produit matriciel entre la matrice d’incidence
sommet-arc et le vecteur X à m-composantes (qui représentent les arcs de R) et ça vaut 1 si
i=s et ça vaut -1 sinon.
-La fonction objectif consiste à minimiser la somme de la quantité di,j×Xi,j ( di,j représente la
longueur de l’arc Xi,j), ∀Xi,j∈U.
1 si i=s
-E X= -1 sinon
(D)
𝑛
Min(Z)= ∑𝑚
𝑖=1 𝑑 i,j Xi,j
𝑗=1
NOTE : le dual D de problème de tension maximum représente en fait un problème de flot.
La résolution de programme linéaire T Max :
- On commence d’abord par déterminer la matrice d’incidence sommet-arc E de problème
traité, ensuite à partir de la transposée de E on exprime les contraintes ainsi que la fonction
objectif.
Ce genre de PL se résout avec l’algorithme de simplexe de 2 phases car on n’a pas une base
réalisable au départ pour commencer l’algorithme de simplexe, on procède alors comme suit :
- On commence par établir le PL auxiliaire associé à (T Max), pour cela il faut d’abord le
transformer sous sa forme standard en rajoutant une variable d’écart à chaque contrainte
d’inégalité `≤` et une variable artificielle à chaque contrainte de type égalité `=`.
- La fonction objectif Z va devenir une fonction de minimisation W de la somme des variables
artificielles ajoutées, on aura donc le PL auxiliaire suivant :
𝜋(s) + V=0 …(1) avec : 𝜋` un vecteur à m-composantes qui
(Ta Max) -E 𝜋 + 𝜋` = d
t représentent les variables d’écart.
∑𝑖∈𝑘 𝑉i =W(min) k : le nombre des contraintes d’égalité.
(T Max) contient une seule contraint d’égalité alors on a une seule variable artificielle V.de
(1) on a : 𝜋(s) + V=0 V= - 𝜋(s), on remplace dans la fonction objectif et on obtient :
𝜋(s) + V=0
(Ta Max) -Et 𝜋 + 𝜋` = d
-𝜋(s)= W (min)
- On applique ensuite l’algorithme de simplexe sur T a Max en commençant par la phase 1.
- Après avoir une base réalisable, on passe à la phase 2 qui sera appliquée sur le PL T Max
initial sous sa forme obtenue à la fin de la phase précédente.
- On effectue le pivotage jusqu’à atteindre l’optimalité, on aura à ce moment un vecteur 𝜋*
contenant les potentiels des sommets de R qui représentent la longueur d’un plus court
chemin issue de sommet s, et une arborescence des plus courts chemins à partir de s.

Exemple : soit le réseau R= (X, U, d), X représente les villes, U l’ensemble des arcs de R (∃u
qui relie X1 et X2 s’il existe un vol entre les deux villes) et d représente la durée du vol entre
les villes en heurs, R se présente comme suit

17
 Ville 1=x1 u6 8 Ville 5=x5
u1 7
u4 2
x0 u3 3 u9 3
Ville 2=x2 u7 3
u2
4 u5 1 Ville 4 = x4
u8 2
ville 3=x3

On veut connaitre la durée minimale de vol du x0 à tous les villes ça revient à chercher un plus
court chemin de x0 à tous les sommets restants i.e il s’agit bien d’un problème de tension max.

→ La matrice d’incidence sommet-arc :

u1 u2 u3 u4 u5 u6 u7 u8 u9 x0 x1 x2 x3 x4 x5
x0 1 1 1 0 0 0 0 0 0 u1 1 -1 0 0 0 0
x1 -1 0 0 -1 0 1 0 0 0 u2 1 0 0 -1 0 0
t
E = x2 0 0 -1 1 1 0 -1 0 0 E = u3 1 0 -1 0 0 0
x3 0 -1 0 0 -1 0 0 1 0 u4 0 -1 1 0 0 0
x4 0 0 0 0 0 0 1 -1 1 u5 0 0 1 -1 0 0
x5 0 0 0 0 0 -1 0 0 -1 u6 0 1 0 0 0 -1
u7 0 0 -1 0 1 0
u8 0 0 0 1 -1 0
u9 0 0 0 0 1 -1
→ La modélisation de problème :
Les variables de décision : 𝜋(xi) : ` représente la durée de vol du ville x0 vers la ville xi`
i=0, …,5.
Les contraintes :
1) 𝜋(x0) = 0 heurs car le vol de la ville x0 à x0 prendra 0 heurs.
2) -Et 𝜋 ≤ d(uj), j=1, …, 9 on aura donc :
- Pour u1 : 𝜋(x1) - 𝜋(x0) ≤ d(u1) i.e : 𝜋(x1) ≤ 7.
- Pour u2 : 𝜋(x3) - 𝜋(x0) ≤ d(u2) i.e : 𝜋(x3) ≤ 4.
- Pour u3 : 𝜋(x2) - 𝜋(x0) ≤ d(u3) i.e : 𝜋(x2) ≤ 3.
- Pour u4 : 𝜋(x1) - 𝜋(x2) ≤ d(u4) i.e : 𝜋(x1)- 𝜋(x2) ≤ 2.
- Pour u5 : 𝜋(x3) - 𝜋(x2) ≤ d(u5) i.e : 𝜋(x3)- 𝜋(x2) ≤ 1.
- Pour u6 : 𝜋(x5) - 𝜋(x1) ≤ d(u6) i.e : 𝜋(x5)- 𝜋(x1) ≤ 8.
- Pour u7 : 𝜋(x2) - 𝜋(x4) ≤ d(u7) i.e : 𝜋(x2)- 𝜋(x4) ≤ 3.
- Pour u8 : 𝜋(x4) - 𝜋(x3) ≤ d(u8) i.e : 𝜋(x4)- 𝜋(x3) ≤ 2.
- Pour u9 : 𝜋(x5) - 𝜋(x4) ≤ d(u9) i.e : 𝜋(x5)- 𝜋(x4) ≤ 3.
La fonction objectif : Z(max) = 𝜋(x0) + 𝜋(x1) + 𝜋(x2) + 𝜋(x0) + 𝜋(x3) + 𝜋(x3) + 𝜋(x5)
comme 𝜋(x0)=0 donc Z devient : Z(max)= 𝜋(x1) + 𝜋(x2) + 𝜋(x0) + 𝜋(x3) + 𝜋(x3) + 𝜋(x5).
Le programme linéaire associé à ce problème s’écrit alors :

18
 𝜋(x0)=0 i=0, …,5 et j=1, …,9.
t
(T Max) -E 𝜋 ≤ d(uj)
Z(Max) = ∑5𝑖=0 𝜋(xi)

→ La résolution de T Max :
Après la transformation sous forme standard et l’ajout des variables d’écart et les variables
artificielles, et après l’application des deux phases de simplexe (1 itération en phase1 et 7
itérations en phase 2) on obtient la solution optimale suivante :
𝜋*=(𝜋(x0), 𝜋(x1), 𝜋(x2), 𝜋(x0), 𝜋(x3),𝜋(x3),𝜋(x5)) = (0, 5, 3, 4, 6, 9) heurs et 𝑧*= 27 heurs.
Les composantes de 𝜋* représentent la plus courte durée d’un vol de l’aéroport X0 vers la
ville Xi respectivement, et Z* représente la durée minimale de parcourir toutes les villes
en démarrant de X0.
Et on aura aussi une arborescence des vols des plus courtes durées G’=(X, U’) tel que
U’= { u∈U / / 𝜋*(T(u) ) - 𝜋*(I(u)) = d(u) } U’= { u2 , u3 , u4 , u8 , u9 }

Conclusion : Les développements récents les plus spectaculaires de la recherche

opérationnelle concernent la théorie des graphes ainsi que le mentionne Claude Berge dans
son livre `En fait, une théorie des graphe unifiée et abstraite n’a pu prendre sa forme que
grâce aux efforts de certains spécialistes de la RO et sous l’impulsion de préoccupation
pratique`, cela montre la relation importante entre les deux disciplines qui ont les deux le
même objectif principal et qui contribuent souvent à la simplification de nombreux problèmes
permettant donc de les résoudre, et le problème de la tension maximum ce n’est qu’une
illustration de ça. En effet de nombreux problèmes peuvent se ramener en graphe et tout
graphe peut être modélisés par un PL pour être ensuite résolut.

19
 Chapitre 03 :

Implémentation de problème de la tension

maximum

20
 Chapitre 03 : l’implémentation de problème de la tension maximum

Introduction : les progrès de l’informatique sont intimement liés à

l’accroissement des applications de la recherche opérationnelle. En effet il existe
plusieurs solveurs de la résolution des programmes linéaires de grandes tailles
qui ont une puissance de calcul importante qui permette de résoudre ses
problèmes de maniéré optimale dans un temps raisonnable.

Dans ce chapitre et à l’aide de l’un de ses solveurs on a établi un programme qui

permet de résoudre le problème de la tension maximum de taille quelconque
en lui introduisant la matrice d’incidence sommet-arc de réseau R traité et le
vecteur qui contient les longueurs de ses arcs ensuite et le programme nous
fournit avec une note ‘solution trouvée’ le nombre d’arcs et de sommets de R,les
potentielles optimales des sommets de R (i.e : la solution optimale), un vecteur
contenant les tensions sur chaque arcs de R, un vecteur des plus court chemin
(i.e : une arborescence optimale) ainsi qu’une valeur optimale, sinon si le
problème n’admet pas de solution on va avoir une note l’indiquant . Pour
faciliter et simplifier la manipulation aux utilisateurs, on a créé une interface
graphique pour le programme. Ce dernier contient une fonction qu’on a créé
appelée tmax qui a deux entrées (une matrice A et un vecteur b) et une seule
sortie (le vecteur des solutions optimales),une fonction appelée arbo qui sert à
déterminer l’arborescence, ainsi qu’une fonction pour calculer la tension des
arcs.On a aussi utilisé une fonction prédéfinie de solveur, il s’agit de la fonction
‘linprog’ qui résout les PL de type minimisation sous contraintes de type
AX<=b / AX=b.
Lors de la résolution et après introduire les données nécessaires par l’utilisateur
l’application va lui donner la solution grâce au lien établit entre la fonction crée
et l’interface graphique ‘calback’.

Le code source de programme :

La fonction tmax :
function [x] = tmax(A,b)
%avoir la transposée de A
A=A';
%avoir le nombre de sommets et le nombre d'arcs
[m,n]=size(A);
%etablir la fonction objectif
f=-ones(1,n);
%definir la contraite d'égalité

21
Aeq=[1 zeros(1,n-1)];
beq=0;
x=linprog(f,-A,b,Aeq,beq);
x=x';
end
la fonction arbo :
function [c] = arbo(y,b)
n=size(y);
for i=1:n
if y(i)==b(i)

c(i)=i;
else c(i)=0;
end
le lien entre l’interface graphique et la fonction tmax :
function pushbutton1_Callback(~, ~, handles)
A=get(handles.edit1,'string');
b= get (handles.edit2,'string');
A= str2num(A);
b=str2num(b);
[x,s,m,n]=tmax(A,b);
m=m; n=n;
A=A';
y = -A * x';
z= sum(x);
c=arbo(y,b);
c(c==0)=[];
set(handles.edit12,'string',c);
set(handles.edit11,'string',z);
set(handles.edit8,'string','le nombre d`arc:');
set(handles.edit9,'string','le nombre de sommet:');
set(handles.edit6,'string',m);
set(handles.edit7,'string',n);
set(handles.edit4,'string',x);
if s<1
set(handles.edit5,'string','pas de solution ')
else
set(handles.edit5,'string','solution trouvèe')

set(handles.edit10,'string',y);
end
On a repris l’exemple qu’on a abordé dans le chapitre 2 pour le résoudre cette fois avec
l’application créé :
1- On commence d’abord par introduire la matrice d’incidence sommet-arc de R dans le
champ ``saisir la matrice d’incidence`` et introduire le vecteur b dans le champ`
`saisir les longueurs des arcs`` , ensuite appuyer sur le boutton ‘ Résoudre’ comme
suite :

22
 2- On aura la solution avec les informations souhaitées sur chaque champs, présenté
comme suite :

Et pour recommencer avec un autre exemple on a qu’a presser le bouton

``Recommencer`` pour tout effacer et recommencer à 0.

23
 Conclusion Générale :

Dans ce travail, nous nous sommes intéressés à un problème particulier de la théorie des
graphes souvent rencontré dans la vie quotidienne, il s’agit de problème de la tension
maximum qui peut se définir aussi comme le problème de la recherche de plus court chemin.

L’objectif de notre mini-projet portait essentiellement sur la modélisation d’un problème

de la théorie des graphes avec des techniques de la programmation linéaire et ensuite le
résoudre en utilisant l’une des méthodes les plus efficaces, à savoir l’algorithme de
simplexe.

Notre modest travail nous aura montré le lien étroit entre les deux disciplines de la
recherche opérationnelle, leur importance qui figure dans leur précision et efficacité de
résoudre de nombreux problèmes dans tous les domaines et la diversité de leur application
dans le monde réel.

24
Bibliographie :
[1] Bernard Fortz ; Recherche opérationnelle et applications ; Université libre de
Bruxelles ; 2012-2013.

[2] Robert Faure, Bernard Lemaire, Christophe Picouleau ; Précis de rechercher

opérationnelle ; 7ème édition ; Dunod ;2014

[3] Robert Faure, J.-P. Boss, Andrè Le Garf ; La recherche opérationnelle. Presses
universitaires de France ; 1995.

[4] Michel Sakarovic ; Eléments de théorie des graphes ; Paris 1985.

[5] Frank Harary ; Graph theory ; Addision-wesley ; 1969.

[6] Michel Sakarovic; Optimisation dans les réseaux ; Herman ; 1985.

25