[PDF] Chapitre 5 – Solutions des exercices de révision

View - Download Chapitre 5 – Solutions des exercices de révision

Previous PDF

Next PDF

Chapitre 5 Solutions des exercices de révision Section 5.2 Quelques exemples supplémentaires de problèmes de réseaux

1. Érébus et les châteaux de neige.

La figure ci-dessous illustre un réseau associé à ce problème. Les éléments de ce modèle graphique

sont :

Flot. Les charges de parpaings de neige expédiées des glacières aux villes constituent

clairement le flot qui circulera dans le réseau.

Sommets émetteurs. Les glacières constituent le point de départ des charges de parpaings et

on crée donc dans le réseau les deux sommets émetteurs G1 et G2. Sommets récepteurs. Les villes constituent la destination finale des charges de parpaings et on crée donc dans le réseau les trois sommets récepteurs A, B et C. Sommets de transbordement. Il n'y a aucun sommet de transbordement dans le réseau, car les charges de parpaings sont acheminées directement des glacières aux villes.

Arcs. La présence ou l'absence d'un arc entre deux sommets se déduit des définitions

précédentes et du tableau des coûts d'acheminement des charges de parpaings fourni dans

l'énoncé. Le coût et les bornes reportés sur un arc se déduisent aisément du texte.

Le problème de réseau associé à la figure ci-dessus a été résolu à l'aide du solveur d'Excel. Une

solution optimale consiste à

2 Chapitre 5 Les problèmes de réseaux

produire, en G1 , 200 charges de parpaings, dont 75 seront acheminées à la ville A et 125, à la

ville C; produire, en G2 , 280 charges de parpaings, dont 25, 200 et 55 respectivement seront livrées aux villes A, B et C.

Le coût minimal d'approvisionnement des villes s'élève à 290 875 $. Noter que les besoins des

trois villes sont satisfaits selon les minimums indiqués dans l'énoncé.

2. La collecte de déchets domestiques.

Pour chacun des quatre secteurs, S1 à S4, on introduit un sommet émetteur dans le réseau; de

même, les sommets récepteurs correspondront aux trois sites d'enfouissement, D1 à D3. On

ajoute des sommets de transbordement, T1 et T2, que l'on dédouble afin de traduire dans le

réseau les données (capacité et coût de traitement) associées aux centres. Voici le réseau

résultant. Une solution optimale, dont le coût est de 2 280 euros par jour, recommande : d'acheminer tous les déchets des secteurs S1 et S4 au centre de transbordement T1, tous ceux de S3 au centre T2 et de répartir moitié-moitié les 20 tonnes de S2; de traiter 40 tonnes par jour en T1 et 42 tonnes en T2;

de transporter les 42 tonnes traitées en T2 vers le site d'enfouissement D1 et de répartir les 20

tonnes de T2 moitié-moitié entre D2 et D3.

Solutions des exercices de révision 3

3. La société Kola.

Composantes du réseau

El Hadj doit décider combien de sacs acheter et vendre chaque mois. On associe dans un premier

temps les mois aux sommets du réseau, et le flot se composera de sacs de kola. Au début de chaque

mois i, El Hadj doit décider :

du nombre de sacs à acheter, ce qui se modélise en traitant comme émetteur le sommet associé

au mois i-à-dire en i; du nombre de sacs à vendre, ce qui se modélise en considérant i comme sommet récepteur, -à-dire en ajoutant un arc virtuel i ;

du nombre de sacs à entreposer dans le but de les vendre à la fin d'un mois subséquent, ce qui

associé au mois i et dont le sommet terminal est associé au mois i+1.

Schématisées, les décisions de El Hadj associées au mois i se représentent par la figure suivante.

Comme la capacité d'entreposage de l'entrepôt durant le mois i est limitée, on dédouble le

sommet i en deux sommets notés Di et Fi , "début» et "fin» du mois. La figure au haut de la page

suivante donne la partie du réseau associée au mois 4. Par l'arc F3 D4 transitent les sacs de kola

qui étaient en stock à la fin du mois 3 et qui n'ont pas été vendus; ils resteront entreposés durant

le mois 4. D4 achemine les sacs de kola achetés au début du mois 4; le coût de

transmission d'une unité de flot par cet arc est le coût d'achat (en milliers de FCFA) d'un sac de

kola au début du mois 4. Les coûts d'entreposage durant le mois 4 sont imputés à l'arc D4 F4

qui acceptera, comme flot, la somme des sacs non vendus à la fin du mois précédent (F3 D4) et

de ceux achetés au tout début du mois ( D4); une borne supérieure de 6 500 et un coût unitaire

de 50 FCFA sont donc attribués à cet arc. Le flot sur l'arc F4 correspond au nombre de sacs

de kola vendus à la fin du mois 4 : pour tenir compte de la demande, ce nombre doit appartenir à

l'intervalle [1 400; 2 000]. Chaque sac qui emprunte l'arc F4 rapporte un revenu de 17 000

F CFA, ce qui dans le réseau se traduit par un coût de 17. L'arc F4 D5 est similaire à l'arc

F3 D4 . Noter que, d'après la figure, une unité de flot incidente en D4 sera forcément transmise à

F4 pour ensuite se diriger soit vers le sommet virtuel , soit vers D5 , ce qui correspond au fait

qu'un sac de kola acheté au début du mois 4 sera forcément entreposé au moins pendant un mois

avant d'être soit vendu en fin de mois 4, soit entreposé pendant le mois 5.

4 Chapitre 5 Les problèmes de réseaux

Modélisation graphique et solution optimale

Voici un réseau qui modélise le problème de la société Kola.

Une solution optimale

La figure ci-dessous illustre une solution optimale du modèle, le nombre reporté sur un arc

applique la stratégie recommandée par cette solution, El Hadj répondra à la demande maximale seulement lors des mois 1, 2, 3, 5 et 8 ; durant les autres mois, il limitera ses livraisons à 70

Vquotesdbs_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