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

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

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