[PDF] Problèmes de transport et transbordement - Résolution

View - Download Problèmes de transport et transbordement - Résolution

Previous PDF

Next PDF

IntroductionSolution des problèmes de transportProblème de transbordementConclusion

Problèmes de transport et transbordement

Résolution

Hugues Talbot

Laboratoire A2SI

9 avril 2009

IntroductionSolution des problèmes de transportProblème de transbordementConclusion Plan

Introduction

Introduction

Solution des problèmes de transport

Solution de base initiale

Le simplexe pour les problèmes de transport

Problème de transbordement

Transbordement

Conclusion

Conclusion

IntroductionSolution des problèmes de transportProblème de transbordementConclusion

Introduction

Rappel : les problèmes de transport sont des problèmes de programmation linéaires associant des producteurs et des consommateurs;

•On peut toujours équilibrer un problème de transport detelle manière que toute la production soit consommée, auprix de noeuds supplémentaires;

•Les problèmes de transport se résolvent plus facilementque les PL standards. Il n'y a pas d'inversion de matrice,les seules opérations sont des additions et soustractions

•Les problèmes de transports entiers ne sont pas plusdifficiles que les autres. IntroductionSolution des problèmes de transportProblème de transbordementConclusion

Rappels

On peut représenter un problème de transport dans un tableau; •Un problème amproducteurs etnconsommateurs est au plus de rangm+n-1 (Q : pourquoi?); •Un problème de transport équilibré n'a que des égalités(Q : pourquoi?)

•Un problème avec uniquement des égalités est souventplus difficile à démarrer (c-à-d trouver une base réalisableinitiale) que les problèmes à égalités (Q : pourquoi?)

IntroductionSolution des problèmes de transportProblème de transbordementConclusion

Exemple

Problème de transport

32 454

Problème PL équivalent

2 6 6 6

41 1 1 0 0 00 0 0 1 1 11 0 0 1 0 00 1 0 0 1 00 0 1 0 0 137775

2 6 6 6 6 6 4x 11x 12x 13x 21x
22x

233777775

=266644532437775

•On doit éliminer une contrainte (p.ex. la première ligne)pour en faire un pb de rangm+n-1=4

•Trouver une base de départ n'est pas simple. Par exemple{x11,x12,x21,x22}ne marche pas. IntroductionSolution des problèmes de transportProblème de transbordementConclusion

Notion de boucle

Une boucle est une séquence de 4 cellules au moins, telle que : •Deux cellules consécutives sontdans la même ligne ou mêmecolonne; IntroductionSolution des problèmes de transportProblème de transbordementConclusion

Notion de boucle

Une boucle est une séquence de 4 cellules au moins, telle que : •Deux cellules consécutives sontdans la même ligne ou mêmecolonne; •Toute suite de trois cellulesconsécutives ne sontjamais dans la même ligne ou colonne; IntroductionSolution des problèmes de transportProblème de transbordementConclusion

Notion de boucle

Une boucle est une séquence de 4 cellules au moins, telle que : •Deux cellules consécutives sontdans la même ligne ou mêmecolonne; •Toute suite de trois cellulesconsécutives ne sontjamais dans la même ligne ou colonne;

•La dernière cellule dans laséquence a une ligne ou unecolonne en commun avec lapremière

IntroductionSolution des problèmes de transportProblème de transbordementConclusion

Notion de boucle

Une boucle est une séquence de 4 cellules au moins, telle que : •Deux cellules consécutives sontdans la même ligne ou mêmecolonne; •Toute suite de trois cellulesconsécutives ne sontjamais dans la même ligne ou colonne;

•La dernière cellule dans laséquence a une ligne ou unecolonne en commun avec lapremière

IntroductionSolution des problèmes de transportProblème de transbordementConclusion

Théorème des boucles

Théorème

Soit un problème de transport avec m producteurs et n consommateurs. Les cellules qui correspondent à un ensemble de m+n-1variables ne contiennent aucune boucle si et seulement si les m+n-1variables forment une solution de base.

Démonstration.

Ce théorème découle du fait qu'un ensemble dem+n-1 cellules ne contiennent aucune boucle si et seulement si les m+n-1 colonnes deAqui correspondent à ces cellules sont linéairement indépendantes. IntroductionSolution des problèmes de transportProblème de transbordementConclusion

Méthodes pour trouver une SBR initiale

Il y a trois méthodes classiques

1.La méthode du coin supérieur gauche;

2.La méthode du coût minimum;

3.La méthode de VOGEL.

IntroductionSolution des problèmes de transportProblème de transbordementConclusion

La méthode du coin supérieur gauche (MCSG)

2 4 2 1315

•On commence en haut à gauche parx11, et on augmentex11autant que possible; IntroductionSolution des problèmes de transportProblème de transbordementConclusion

La méthode du coin supérieur gauche (MCSG)

2

X 4 2 1313

•On commence en haut à gauche parx11, et on augmentex11autant que possible; •On élimine du tableau la ligne ou lacolonne saturée, on diminue dex11la ligne ou colonne non saturée; IntroductionSolution des problèmes de transportProblème de transbordementConclusion

La méthode du coin supérieur gauche (MCSG)

23

X 1 2 131X

•On commence en haut à gauche parx11, et on augmentex11autant que possible; •On élimine du tableau la ligne ou lacolonne saturée, on diminue dex11la ligne ou colonne non saturée; •On continue cette procédurerécursivement sur le reste du tableau; IntroductionSolution des problèmes de transportProblème de transbordementConclusion

La méthode du coin supérieur gauche (MCSG)

23
1

X02 13XX

•On commence en haut à gauche parx11, et on augmentex11autant que possible; •On élimine du tableau la ligne ou lacolonne saturée, on diminue dex11la ligne ou colonne non saturée; •On continue cette procédurerécursivement sur le reste du tableau;

•Dans le cas où une augmentation saturela ligne et la colonne en même temps, onchoisit d'éliminer seulement soit la ligne,soit la colonne;

IntroductionSolution des problèmes de transportProblème de transbordementConclusion

La méthode du coin supérieur gauche (MCSG)

23
1 0

X X 2 13XX

•On commence en haut à gauche parx11, et on augmentex11autant que possible; •On élimine du tableau la ligne ou lacolonne saturée, on diminue dex11la ligne ou colonne non saturée; •On continue cette procédurerécursivement sur le reste du tableau;

•Dans le cas où une augmentation saturela ligne et la colonne en même temps, onchoisit d'éliminer seulement soit la ligne,soit la colonne;

•Une saturation à zéro donne une baseinitiale dégénérée, comme ici; IntroductionSolution des problèmes de transportProblème de transbordementConclusion

La méthode du coin supérieur gauche (MCSG)

23
1 02

X X X 11XX

•On commence en haut à gauche parx11, et on augmentex11autant que possible; •On élimine du tableau la ligne ou lacolonne saturée, on diminue dex11la ligne ou colonne non saturée; •On continue cette procédurerécursivement sur le reste du tableau;

•Dans le cas où une augmentation saturela ligne et la colonne en même temps, onchoisit d'éliminer seulement soit la ligne,soit la colonne;

•Une saturation à zéro donne une baseinitiale dégénérée, comme ici; IntroductionSolution des problèmes de transportProblème de transbordementConclusion

La méthode du coin supérieur gauche (MCSG)

23
1 021

X X X XXXX

•On commence en haut à gauche parx11, et on augmentex11autant que possible;quotesdbs_dbs2.pdfusesText_2

[PDF] problème de transport stepping stone

[PDF] exercice corrige résolution du problème de transport en recherche opérationnelle

[PDF] transport et probléme d affectations

[PDF] exos corrigés problème d'affectation recherche opérationnelle

[PDF] développement limité fonction plusieurs variables

[PDF] recherche opérationnelle exercices corrigés gratuit

[PDF] programmation linéaire exercices corrigés simplex

[PDF] examen recherche opérationnelle corrigé

[PDF] exercice corrigé methode simplexe pdf

[PDF] multiples et sous multiples physique

[PDF] multiples et sous multiples physique exercices

[PDF] multiples et sous multiples du gramme

[PDF] multiple et sous multiple exercice

[PDF] multiples et sous multiples du litre

[PDF] multiplicateur fiscal formule