Allocation de missiles

• Notons $m(k,s)$ l'espérance maximum de la valeur détruite avec $s$ missiles sur les $k$ premières cibles. Supposons le problème résolu : la $k$-ème cible reçoit $x$ missiles et apporte l'espérance $v_{k-1}{p}_{k-1}(x)$ ; les autres missiles sont répartis au mieux.

Base. $m(0,s)=0$ pour tout $s$.

Hérédité. $\forall k,1\le k<n+1$, $\forall s,0\le s<S+1$ :

$$m(k,s)=\underset{0\le x<s+1}{\max }\{v_{k-1}{p}_{k-1}(x)+m(k-1,s-x)\}.$$

C'est une répartition optimale, avec des gains réels :

double[][] M = new double[n + 1][S + 1];      // base : M[0][s] = 0
int[][] A = new int[n + 1][S + 1];
for (int k = 1; k < n + 1; k++)
    for (int s = 0; s < S + 1; s++) {
        M[k][s] = -1;
        for (int x = 0; x < s + 1; x++) {      // x missiles sur la k-ème cible
            double e = v[k - 1] * p(q[k - 1], x) + M[k - 1][s - x];
            if (e > M[k][s]) { M[k][s] = e; A[k][s] = x; }
        }
    }

avec static double p(double q, int x) { return 1 - Math.pow(1 - q, x); }.

• L'exécution donne une espérance maximum de $14,7$ avec $2$ missiles sur la cible $0$ et un sur chacune des deux autres : $10\times 0,75+6\times 0,8+8\times 0,3=7,5+4,8+2,4=14,7$.

Espérance maximum : 14,7000
  cible 0 : 2 missile(s)
  cible 1 : 1 missile(s)
  cible 2 : 1 missile(s)
Glouton : 14,7000 avec [2, 1, 1]

• Oui. Le gain marginal du $(x+1)$-ème missile sur la cible $i$ vaut $v_i(p_i(x+1)-p_i(x))=v_i{q}_i(1-q_i{)}^x$ : il décroît avec $x$. Les gains sont concaves, et l'exercice 4.3 montre qu'alors le glouton est optimal. Bellman avait étudié ce cas : lorsque les gains sont concaves, la programmation dynamique n'est pas nécessaire.