Technologie utilisée

Python

Objectifs du projet

L'ojectif de ce projet était de concevoir un programme capable de déterminer le chemin critique dans un problème d'ordonancement. De plus il fallait faire apparaitre les différentes étapes du calcul en passant de la recherche de circuit au calcul des rangs et au calcul des dates au plus tôt et plus tard.

Ce que le projet m’a apporté

Sachant que les problèmes d'ordonancement sont très présent dans le monde industriel, ce projet m'a permis de me plonger dans un contexte réel d'utilisation de la théorie des graphes. J'ai appris à dévelloper un solution applicable dans la vie réelle.

Galerie du projet

Objectifs du projet

Coder les deux algorithmes pour trouver un flot maximal par la méthode de Ford-Fulkerson et de l’algorithme pousser-réétiqueter. Et pour tout réseau de flot pondéré, coder l’algorithme permettant de trouver un flot de coût minimal pour une valeur de flot donnée en entrée

Explication

• Problème de flot maximal

• On part d'un graph orienté ou chaque arrête possède une capacitée.
  Pour faire une analogie imaginoins un systeme de canalisation où tous les tuyaux n'ont pas la même dimmension donc pas la même capacité et flot possible. Le problème de flot maximal reviens alors à chercher le flot maximal possible en sortie

• Problème de flot maximal à coût minimal

• On part d'un graph orienté ou chaque arrête possède une capacitée et un cout.
  On part d'un graphe orienté ou chaque arête possède une capacité et un coût. Pour reprendre l'analogie précédente, supposons que chaque tuyau possède un coût d'usure par litre transféré, il est alors intéressant de trouver le flow maximal qui nous permettra d'obtenir l'usure la plus faible.

Galerie du projet