Université des Sciences et Technologies Houari Boumediene
Faculté de Génie des Procédés Département de Génie de l'Environnement
Spécialité de dessalement
Évaluation Technico-Économique des Projets
Resolution du Projet ETEP
présentée par Binôme 13 :
BOUAZZA haroune
NECIB hiba
2024/2025
Partie 01 : Programmation Linéaire
Partie 02: Théorie des Graphes
• Définition
• Représentation sagittale
• Représentation matricielle
• Algorithme de Dijkstra pour le chemin optimal
• La théorie des graphes est un domaine fascinant des
mathématiques discrètes qui offre des outils
puissants pour modéliser et analyser des relations
complexes entre objets.
• La théorie des graphes est la discipline
mathématique et informatique qui étudie les graphes.
• Un graphe G est défini comme un couple G = (V, E)
comprenant deux ensembles :
– • V : l'ensemble des sommets (vertices)
– • E : l'ensemble des arêtes (edges)
• Deux sommets reliés par une arête sont dits voisins
ou adjacents.
La représentation sagittale d’un graphe oriente G = (S,A) est la représentation graphique où
les sommets sont représentes par des points et les arcs (x, y) par des flèches allant de x vers y.
Les Types de graphes :
• Graphe non orienté : arêtes sans orientation.
• Graphe orienté : arêtes avec orientation.
• Graphe mixte : contient à la fois des arêtes orientées
et non orientées
• Graphe pondéré : arêtes associées à un poids
(distance, coût, capacité)
Cette méthode, bien qu'ayant des avantages notables en termes de simplicité,
est particulièrement adaptée aux petits graphes où la complexité des relations reste gérable.
Tout graphe G = (V, E) peut être représenté par une
matrice. Les relations entre arêtes et sommets, appelées
les relations d'incidence, sont toutes représentées par la
matrice d'incidence du graphe. Les relations
d'adjacences (si deux sommets sont reliés par une arête
ils sont adjacents) sont représentés par sa matrice
d'adjacence.
Le lien entre les matrices et les propriétés du graphe
est fort. L'utilité pour les algorithmes est claire.
L'algorithme de Dijkstra détermine le plus court chemin entre deux sommets d'un graphe
pondéré positivement.
Étapes de l'algorithme :
1. Initialisation : distance infinie à tous les sommets sauf le
départ(0)
2. Processus itératif :
• Choisir le sommet non visité avec la plus petite distance
• Marquer ce sommet comme visité
• Mettre à jour les distances des voisins non visités
3. Résultat : distances minimales du sommet de départ à
tous autres
L'algorithme de Dijkstra est crucial. Il trouve le chemin le plus court. Sa complexité
est bien définie. Applications : GPS, routage réseau, planification de trajets.
Ce projet nous a permis d'explorer deux domaines importants
des mathématiques appliquées : la programmation linéaire et
la théorie des graphes.
ü Dans la première partie, nous avons appliqué la méthode simplexe pour
résoudre des problèmes d'optimisation linéaire, en déterminant
notamment un tableau intermédiaire et en résolvant un problème de
maximisation.
ü Dans la seconde partie, nous avons étudié les fondements de la théorie
des graphes, en abordant les différentes représentations des graphes et
l'algorithme de Dijkstra pour la recherche de chemins optimaux.
ü Ces outils mathématiques sont essentiels dans de nombreux domaines
d'application, notamment en ingénierie, en économie et en informatique
