Eléments de théorie des graphes

Programmation linéaire :

La programmation linéaire est un outil très puissant de la recherche opérationnelle. C’est un outil générique qui peut résoudre un grand nombre de problèmes. En effet, une fois un problème modélise sous la forme d’équations linéaires, des méthodes assurent la résolution du problème de manière exacte. On distingue dans la programmation linéaire, la programmation linéaire en nombres réels, pour laquelle les variables des équations sont dans IR+ et la programmation en nombres entiers, pour laquelle les variables sont dans IN. Bien entendu, il est possible d’avoir les deux en même temps. Cependant, la résolution d’un problème avec des variables entières est nettement plus compliquée qu’un problème en nombres réels. Une des méthodes les plus connues pour résoudre des programmes linéaires en nombre réels est la méthode du Simplex. En théorie, elle a une complexité non polynomiale et est donc supposée peu efficace. Cependant, en pratique, il s’avère au contraire qu’il s’agit d’une bonne méthode. Un programme linéaire est la maximisation où la minimisation d’une fonction linéaire sous des contraintes linéaires.

Tableau de transport :

Le problème de transport peut être décrit en utilisant un modèle mathématique de programmation linéaire, et habituellement, il apparaît dans un tableau de transport. Le modèle d’un problème de transport peut être représenté sous forme de tableau concis avec tous les paramètres pertinents. Le tableau de transport (Un problème de transport typique est représenté sous forme de matrice standard), où la disponibilité d’approvisionnement (ai) à chaque source est affichée dans la colonne droite du tableau, et les demandes de destination (bj) sont affichées dans la ligne inférieure. Chaque cellule représente une voie, Le coût de transport unitaire (cij) est indiqué dans le coin supérieur droit de la cellule, la quantité de matériel transporté est affichée au centre de la cellule, Le tableau de transport exprime implicitement les contraintes de l’offre et de la demande et le coût de transport entre chaque source et destination.

Résolution de problème de transport Le problème de transport est ainsi un programme linéaire et peut donc être résolu par des méthodes du simplexe. Cependant elles existent des méthodes qui ont même principe de résolution de simplexe mais plus adaptées, Comme toute application de la méthode du simplexe à la résolution de ce type de problème, nécessite une solution de base initiale. La détermination de cette solution et son amélioration est l’objectif de ce chapitre.

Considérons un problème de transport impliquant m origines et n destinations. Étant donné que la somme des disponibilités d’origine est égale à la somme des demandes de destination, une solution réalisable existe toujours. La (m+n)-nième contrainte est redondante et peut donc être supprimée. Cela signifie également qu’une solution de base réalisable pour un problème de transport peut avoir au plus (m+n–1) composants strictement positifs, Sinon la solution dégénérera. Il est toujours possible d’assigner une solution réalisable initiale à un problème de transport. De telle sorte que les exigences des destinations soient satisfaites. Cela peut être réalisé soit par une inspection, soit par des règles simples. Nous commençons par imaginer que la table de transport est vide, c’est-à-dire initialement tout 𝒙𝒊𝒋 = 𝟎. Les procédures les plus simples pour l’allocation initiale seront discutées dans la section suivante.

Méthodes d’optimisation de solution de base :

Pour obtenir une solution optimale en apportant des améliorations successives à la solution de base initiale jusqu’à ce qu’il n’y ait plus de réduction du coût de transport. Une solution optimale est celle où il n’y a pas d’autre ensemble de routes de transport qui réduira encore le coût total du transport. Ainsi, nous devons évaluer chaque case inoccupée dans le tableau de transport sur l’opportunité de réduire le coût total du transport. Une case inoccupée avec le coût d’opportunité négatif le plus important est choisi pour inclure dans le nouvel ensemble de routes de transport (allocations). Cette valeur indique la réduction de coût par unité qui peut être obtenue en augmentant l’allocation d’expédition dans la case inoccupée à partir de son niveau actuel de zéro. Ceci est également connu comme une case entrante (variable d’entré comme dans le simplexe). La case sortante (variable sortante) dans la solution actuelle est la case occupée (variable de base) dans le chemin fermé unique (boucle) dont l’attribution deviendra nulle, car d’autres unités sont attribuées à la case inoccupée avec le plus grand coût d’opportunité négatif. C’est-à-dire que la solution actuelle ne peut plus être améliorée. C’est la solution optimale.

Méthode de Coin Nord-Ouest :

Dans la méthode du coin nord-ouest, la plus grande répartition possible est faite à la case dans le coin supérieur gauche du tableau, suivie d’allocations vers des cases adjacentes. Nous attribuons d’abord autant que possible à la case 1A (coin nord-ouest). Ce montant est de 150 tonnes, puisqu’il s’agit du maximum pouvant être fourni par l’élévateur à grain 1, Même si 200 tonnes sont demandées par l’usine A. dans cette allocation initiale, est présentée dans le tableau 2.0. Nous allons ensuite allouer à une case adjacente à la case 1A, dans ce cas soit la case 2A où la case 1B. Cependant, la case 1B ne représente plus une répartition possible, car le tonnage total de blé disponible à la source 1 (150 tonnes) a été alloué. Ainsi, la case 2A représente la seule alternative possible, et autant que possible est alloué à cette case, Le montant alloué à 2A peut être de 175 tonnes, la fourniture disponible à partir de la source 2 est 50 tonnes, le montant actuellement demandé à la destination A, Parce que 50 tonnes sont le montant le plus contraint, il est attribué à la case 2A. Comme le montre le tableau 2.0 . La troisième répartition est faite de la même manière que la deuxième répartition la seule case possible adjacente à la case 2A est la case 2B. Le plus qui peut être attribué soit 100 tonnes (le montant demandé à l’usine B) soit 125 tonnes (175 tonnes moins les 50 tonnes attribuées à la case 2A) Le montant le plus petit (le plus contraint), 100 tonnes, est attribué à la case 2B, comme le montre le tableau 2.0 . La quatrième allocation est de 25 tonnes à la case 2C et la cinquième allocation est de 275 tonnes à la case 3C, toutes deux reprises dans le tableau 2.1.

Conclusion générale :

Cette étude m’a donné l’opportunité de me familiariser au domaine de la recherche opérationnelle, ce domaine qui est la discipline des méthodes scientifiques pour aider à mieux décider et traiter les problèmes stratégiques et économiques, Le problème de transport est l’un de ces problèmes classique les plus connus, Mais la complexité et la variation des contraintes de ce problème dans le domaine économique impliquent la recherche d’autres heuristiques et même des métaheuristiques plus efficaces pour la résolution. Ce qui rend difficile de tirer une conclusion définitive sur la résolution de ce type des problèmes. Dans ce rapport, on s’est intéressé d’avantage à la modélisation et la résolution de problème de transport équilibré par des différentes méthodes qui nous permettons d’obtenir une solution de base réalisable (Nord-Ouest, Coût minimum, Approximation de vogel), Ensuite nous avons essayé d’expliquer l’optimisation d’un telle solution de base initiale par la méthode de stepping stone et la méthode de distribution modifiée, puis nous avons essayé de faire une comparaison entre ces méthodes et les programmer en langage C comme un programme de résolution d’un problème de transport. 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.

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

Introduction générale
Chapitre 1 : Notions de base
1.Eléments de Théorie des graphes
1.1 Un graphe
1.2 Ordre, orientation et multiplicité d’un graphe
1.3 Qualificatifs des graphes
1.4 Matrices associées à un graphe
1.5 Vocabulaire lié a la connexité
2.Programmation linéaire
2.1 Forme générale d’un programme linéaire
2.2 Formes matricielles classiques et conventions
2.3 Interprétation économique
2.4 La méthode de simplexe
Chapitre 2 : Problème de transport
1.Positionnement de problème
2.Modélisation
2.1 Les variables de décision
2.2 La fonction objective
2.3 Les contraintes
2.4 Formulation mathématique
Problème de transport non équilibré
Tableaux de transport
Réseau de transport
Dégénérescence en problème de transport
Chapitre 3 : Résolution de problème de transport
1.Structure de la résolution d’un problème de transport
1.1 Solution de base réalisable
1.2 Solution optimale
1.3 Diagramme de résolution de problème de transport
2.Méthodes de détermination de la solution de base initiale
2.1 Méthode de Coin Nord-Ouest
2.2 Méthode de Coût Minimum
2.3 Méthode d’Approximation de Vogel
3.Méthodes d’optimisation de solution de base
3.1 Méthode de stepping-stone
3.2 Méthode de distribution modifiée
Chapitre 4 : Application
1.Problématique
2.Modélisation
3.Détermination de solution de base
3.1 Méthode de coin nord-ouest
3.2 Méthode du coût minimum
3.3 Méthode d’approximation de vogel
4.Optimisation de solution de base
4.1 Méthode de steeping stone
4.2 Méthode de distribution modifiée
5.Implémentation en langage C
5.1 Langage de programmation C
5.2 L’outil de programmation
5.3 Programme de résolution de problème de transport
6.Comparaison des méthodes
Conclusion générale
Bibliographie