Répartition optimale d'une ressource

Cours · algorithmique (école d'ingénieur), chapitre 4 · école d'ingénieur, informatique · le début du chapitre, la suite sur Adloun

Objectifs du chapitre

Modéliser un problème d'allocation de ressource : une quantité à partager entre plusieurs bénéficiaires.
Écrire une récurrence dont l'hérédité est un maximum sur un nombre variable de cas, et en déduire une complexité en $Θ (n S^{2})$ .
Mémoriser les arguments du maximum dans un tableau $A = ar g M$ pour afficher une solution sans aucun calcul supplémentaire.

4.1 Le problème

Une entreprise dispose d'un stock de $S$ unités d'un produit (des palettes, des conteneurs…) et de $n$ entrepôts numérotés $0, \dots, n - 1$ . Elle doit décider combien d'unités livrer à chaque entrepôt. Livrer $s$ unités à l'entrepôt $i$ lui rapporte un gain $g (i, s)$ , connu à l'avance. On suppose :

qu'un entrepôt vide ne rapporte rien : $g (i, 0) = 0$ ;
que les gains sont croissants au sens large : $g (i, s + 1) \geq g (i, s)$ (une unité de plus ne fait jamais perdre d'argent, mais peut ne rien rapporter).

Définition 4.1Répartition

Une répartition du stock $S$ sur les $n$ entrepôts est une suite $(s_{0}, \dots, s_{n - 1})$ d'entiers positifs ou nuls telle que $s_{0} + \dots + s_{n - 1} \leq S$ . Son gain est $g (0, s_{0}) + \dots + g (n - 1, s_{n - 1})$ . Une répartition est optimale si son gain est maximum.

Comme les gains sont croissants, on peut toujours supposer que tout le stock est distribué ; mais l'inégalité $\leq S$ ne coûte rien et simplifie la base de la récurrence.

Exemple 4.2quatre entrepôts, un stock de cinq unités

Les gains sont donnés dans un tableau $G$ de terme général $G [i] [s] = g (i, s)$ :

	$1$	$2$	$3$	$4$	$5$
entrepôt $3$	2	2	3	4	4
entrepôt $2$	4	4	4	4	4
entrepôt $1$	1	2	3	3	3
entrepôt $0$	2	3	4	5	5

L'entrepôt $2$ est « vite saturé » : la première unité rapporte $4$ , les suivantes rien. L'entrepôt $0$ progresse régulièrement jusqu'à $4$ unités.

Le nombre de répartitions croît très vite : pour $n$ entrepôts et un stock $S$ , il y en a $(n S + n)$ , soit déjà plus de $1 0^{13}$ pour $n = 20$ et $S = 100$ . L'énumération exhaustive est exclue.

4.2 La tentation gloutonne : le gain marginal

L'idée naturelle consiste à distribuer les unités une par une, chaque unité allant à l'entrepôt où elle rapporte le plus, c'est-à-dire où le gain marginal $g (i, s_{i} + 1) - g (i, s_{i})$ est le plus grand. Cette stratégie paraît raisonnable ; elle est fausse.

La suite du cours est sur Adloun

Le chapitre en entier, formules et figures comprises, avec le tuteur, les fiches, les QCM et les exercices.

Lire la suite du cours

En accès libre, sans inscription.

Exercices corrigés de ce chapitre

Lire la suite du cours →