previous up next

Le problème du restaurant et des serviettes

Un restaurant sait qu'il aura besoin de 50 serviettes le jour J1, 60 le jour J2, 80 le jour J3, 70 le jour J4, 50 le jour J5, 60 le jour J6, 90 le jour J7, 80 le jour J8, 50 le jour J9 et 100 le jour J10.

On suppose qu'avant le jour J1 le restaurant n'a pas de serviette, et que chaque jour il peut acheter des serviettes 10F l'unité, il peut faire laver en 2 jours des serviettes pour 2F l'unité ou faire laver en 4 jours des serviettes pour 1F l'unité. Il faut bien sûr trouver la solution la plus économique.

Ce problème peut s'écrire (et se résoudre) sous forme d'un problème de transport. Le graphe correspondant peut être le suivant :

 
Figure 4.4: Le coût des arcs du graphe
\includegraphics[height=17cm]{restaurant.eps}

Les Ji représentent la demande en serviettes de chaque jour. Les SJi représentent les serviettes utilisées le i-ème jour. Le noeud S représente le fournisseur de serviettes neuves.

Comme source, on a S qui propose autant de serviettes que l'on veut. On peut lui attribuer la valeur 590 (la somme de toutes les serviettes requises). Les autres sources sont :

SJ1 SJ2 SJ3 SJ4 SJ5 SJ6 SJ7 SJ8 SJ9 SJ10
50 60 80 70 50 60 90 80 50 100

Comme puits on a :

J1 J2 J3 J4 J5 J6 J7 J8 J9 J10
50 60 80 70 50 60 90 80 50 100

Enfin, le puits Fin demande 590. Il assure que le nombre des serviettes vendues plus le nombre de serviettes non vendues vaut 590.

La résolution à l'aide du programme nous donne la solution suivante :

 
Figure 4.5: Une solution optimale
\includegraphics[height=17cm]{restaurant_sol.eps}

Le coût de cette solution est de 2660F.


previous up next

30-03-1999