Calculs à la main

• La base donne $M[0]=[0,0,0,0,0,0]$. Pour $k=1$, seul l'entrepôt $0$ est disponible : $m(1,s)={\max }_{s^{\prime }\le s}g(0,s^{\prime })=g(0,s)$ puisque les gains sont croissants. Donc $M[1]=[0,2,3,4,5,5]$ et $A[1]=[0,1,2,3,4,4]$ (pour $s=5$, livrer $4$ ou $5$ unités rapporte $5$ ; on garde le premier argument trouvé, $4$).

Pour $k=2$ : $m(2,s)={\max }_{0\le s^{\prime }\le s}\{g(1,s^{\prime })+m(1,s-s^{\prime })\}$. Par exemple $m(2,5)=\max \{0+5,1+5,2+4,3+3,3+2,3+0\}=6$, atteint d'abord en $s^{\prime }=1$. On obtient $M[2]=[0,2,3,4,5,6]$ et $A[2]=[0,0,0,0,0,1]$.

• $m(3,2)=\max \{g(2,0)+m(2,2),g(2,1)+m(2,1),g(2,2)+m(2,0)\}=\max \{0+3,4+2,4+0\}=6$, et $a(3,2)=1$.

nom : M[2]
valeurs : 0 2 3 4 5 6
vert : 0..2
legende : m(3,2) lit M[2][0:3] : max(0 + 3, 4 + 2, 4 + 0) = 6

• On lit les arguments à rebours, en partant de $(k,s)=(4,3)$ : $a(4,3)=1$ (une unité à l'entrepôt $3$), puis $a(3,2)=1$ (une unité à l'entrepôt $2$), puis $a(2,1)=0$, puis $a(1,1)=1$. La répartition $(1,0,1,1)$ rapporte $2+0+4+2=8=m(4,3)$.

Le programme Ex4_1Calculs.java confirme ces valeurs :

M[4] = [0, 4, 6, 8, 9, 10]   A[4] = [0, 0, 0, 1, 1, 1]
M[3] = [0, 4, 6, 7, 8, 9]   A[3] = [0, 1, 1, 1, 1, 1]
M[2] = [0, 2, 3, 4, 5, 6]   A[2] = [0, 0, 0, 0, 0, 1]
M[1] = [0, 2, 3, 4, 5, 5]   A[1] = [0, 1, 2, 3, 4, 4]
M[0] = [0, 0, 0, 0, 0, 0]   A[0] = [0, 0, 0, 0, 0, 0]
Répartition optimale d'un stock de 3 unités :
  entrepôt 0 <-- 1, gain 2
  entrepôt 1 <-- 0, gain 0
  entrepôt 2 <-- 1, gain 4
  entrepôt 3 <-- 1, gain 2