Problème de Transport et d’Affectation

Problème de Transport et Affectation

Notions de Base

Dans ce chapitre on va parler de quelles notions de base dans la théorie des graphes qu’on va utiliser par la suite soit dans la résolution du problème de transport ou bien on traitant le problème d’affectation, et des points générale sur l’optimisation combinatoire et la programmation linéaire. L’optimisation combinatoire occupe une place très importante en recherche opérationnelle, en mathématiques discrètes et en informatique. Son importance se justifie d’une part par la grande difficulté des problèmes d’optimisation et d’autre part par de nombreuses applications pratiques pouvant être formulées sous la forme d’un problème d’optimisation combinatoire. Bien que les problèmes d’optimisation combinatoire soient souvent faciles à définir, ils sont généralement difficiles à résoudre. En effet, la plupart de ces problèmes appartiennent à la classe des problèmes NP-difficiles et ne possèdent donc pas à ce jour de solution algorithmique efficace valable pour toutes les données.

Un problème d’optimisation combinatoire est défini par un ensemble d’instances. A chaque instance du problème est associé un ensemble discret de solutions S, un sous-ensemble X de S représentant les solutions admissibles (réalisables) et une fonction de coût f (ou fonction objectif) qui assigne à chaque solution s ∈X le nombre réel (ou entier) f(s). Résoudre un tel problème (plus précisément une telle instance du problème) consiste à trouver une solution s* ∈X optimisant la valeur de la fonction de coût f. Une telle solution s* s’appelle une solution optimale ou un optimum global. Nous avons donc la définition suivante : Notons que d’une manière similaire, on peut également définir les problèmes de maximisation en remplaçant simplement ≤ par ≥. L’optimisation combinatoire trouve des applications dans des domaines aussi variés que la gestion, l’ingénierie, la conception, la production, les télécommunications, les transports, l’énergie, les sciences sociales et l’informatique elle-même.

Programmation linéaire

Dans le contexte de la programmation linéaire, le terme programmation désigne l’organisation des calculs et non la réalisation d’un programme informatique. Du point de vue des applications, l’optimisation linéaire est d’une grande portée. Elle s’applique à des problèmes très variés qui sont issus de l’économie, de l’ingénierie, de la physique ou encore des modèles probabilistes. Dans ce cadre, on peut citer par exemple, les problèmes de type gestion de stock, gestion de production, transport de marchandise, affectation du personnel, systèmes industriels, réseaux de communication, etc. Pour les modèles de programmation linéaire, on est souvent amené à maximiser un gain ou minimiser un coût. Ceci explique d’ailleurs pourquoi la fonction à maximiser s’appelle fonction d’objectif ou économique. Un programme linéaire est un problème dans lequel on est amené à maximiser (ou minimiser) une application linéaire, appelée fonction d’objectif ou fonction économique, sur un ensemble d’équations et/ou d’inéquations linéaires, dites contraintes. Autrement dit, la programmation linéaire est une branche des mathématiques qui a pour but de résoudre des problèmes d’optimisation linéaire de type : Les coefficients cj, aij et bi sont des réels fixés et les xj sont des variables réelles. Les contraintes d’inégalités éventuelles sont toutes larges et non strictes. Il se peut qu’une contrainte d’inégalité soit de type » ≥ ». En multipliant chaque inégalité de type » ≥ » par (-1), on peut supposer que toutes les contraintes d’inégalité sont de type » ≤ ».

Conclusion

Il n’est pas possible de tirer une conclusion définitive sur un sujet en plein développement à l’heure actuelle. Dans ce projet on a traité seulement les cas linéaires des problèmes de transport et d’affectation, mais dans le domaine économique les contraints de ces deux problèmes changes d’une entreprise a l’autre, donc c’est un peu difficile de donner un programme générale qui peut être utilisé par tous les entreprises pour optimiser les coûts. A la fin je peux dire que ce travaille représente une base de départ pour résoudre les problèmes générale de transport et d’affectation.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport gratuit propose le téléchargement des modèles gratuits de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

1ère partie : Présentation
I.Introduction
II.Objectif
III. Les Technologies utilisées
IV.Langage utilisé
3ème partie : Problème de Transport et Affectation
Chapitre 1: Notion de Base
I.Introduction :
II.L’optimisation combinatoire
III. Théorie des Graphes
1.Un Graphe
2.Graphe bipartie
3.Couplage
4.Couplage dans un graphe biparti
IV.Programmation linéaire :
Chapitre 2: Problème de transport
I.Présentation du problème:
II.Formulation du problème :
III. La résolution du problème de transport
1.Recherche d’une solution de base
2.Recherche d’une solution Optimal
Chapitre 3: Problème d’affectation
I.Introduction
II.L’utilisation de l’affectation
1.L’occupation d’un bâtiment
2.L’élaboration du plan annuel de mutation
III. Formulation du problème :
IVLa résolution du problème d’affectation
3ème partie : Appliquation
Chapitre 1 : Application
I.Présentation du programme
II.Problème d’affectation
1.Méthode Hongrois
2.Méthode Cplex
III. Problème de transport :
Conclusion
Références bibliographiques