35 CHAPITRE 3.
PLUS COURTS CHEMINS ET PROGRAMMATION DYNAMIQUE
acircuitique (Section 3.1.2), cela revient à dire qu’un ordre topologique est donné facilement
par le découpage temporel.
Remarquons enfin que tout graphe orienté acircuitique n’est pas issu d’une modélisation
d’un système dynamique. En effet, un graphe modélisant un processus de programmation
dynamique a tous ses chemins de s à t ayant le même nombre d’arcs, à savoir N .
Venons-en maintenant à quelques exemples de modélisation par la programmation dyna-
mique.
Exemple : Gestion de stock
Considérons le problème de la gestion d’un stock pour N périodes consécutives.
Un stock suit une dynamique de la forme xk+1 = xk − dk + uk , où dk désigne la demande
pour la période k, supposée connue, xk désigne le nombre d’unités disponibles en début de
kième période et uk désigne le nombre d’unités commandées (et reçues immédiatement) en
début de kième période. On prendra xk ∈ Z, une quantité négative signifiant une pénurie.
De plus, on a en général l’existence d’une capacité maximale de stockage K qui implique que
xk ≤ K. On supposera x0 fixé.
Les coûts de gestion de stock se décomposent pour chaque période k en
— un coût de réapprovisionnement c(uk ), c’est-à-dire le coût d’achat des uk unités, et
— un coût de gestion g(xk+1 ), qui comprend le coût de stockage des unités en excès en fin
de période et le coût de pénurie si la demande ne peut être totalement satisfaite sur la
période.
Typiquement, on a c(u) = b + au, où a est un coût unitaire d’achat et b un coût fixe et
sx si x ≥ 0
g(x) =
px si x ≤ 0,
où s est le coût unitaire de stockage et p le coût unitaire de défaillance. Si on veut interdire
les stocks négatifs, on pose p = +∞.
On veut minimiser
N
X −1
c(uk ) + g(xk+1 ).
k=0
Dans le vocabulaire de la programmation dynamique, les états sont les valeurs possibles de
niveau de stock, les transitions possibles sont tous les xk → xk+1 tels que xk+1 satisfasse
simultanément xk+1 ∈ Z, xk+1 ≤ K et xk+1 ≥ xk − dk . Le coût de la transition xk → xk+1
est c(xk+1 − xk + dk ) + g(xk+1 ). On souhaite donc trouver la trajectoire optimale pour ce
modèle de programmation dynamique.
On applique l’algorithme de plus court chemin dans le graphe acircuitique suivant. Pour
chaque période k, on aura un sommet pour chaque niveau de stock possible (inférieur à K et
supérieur à x0 − d0 − d1 − . . . − dk−1 ) en début de période. On notera un tel sommet (x, k),
où x est le niveau de stock, et k la période. Entre un sommet de période k et un sommet
de période k + 1, on a un arc ((x, k), (x0 , k + 1)) seulement si x0 ≥ x − dk . Le poids de l’arc
CHAPITRE 3. PLUS COURTS CHEMINS ET PROGRAMMATION DYNAMIQUE 36
((x, k), (x0 , k + 1)) est égal à c(x0 − x + dk ) + g(x0 ). On cherche un plus court chemin de (x0 , 0)
à un sommet de la forme (x, N ). Le poids de ce plus court chemin sera le coût optimal de la
gestion du stock.
Exemple : Remplissage d’un conteneur ou problème du sac-à-dos
Considérons un assortiment de N objets k = 1, . . . , N , l’objet k ayant une valeur ck ≥ 0
et un volume ak >P 0, et supposons que l’on ait à stocker ces objets dans un conteneur de
volume fini W . Si N k=1 ak > W , on va devoir sélectionner des objets afin de maximiser la
valeur des objets stockés. Ce problème est connu sous le nom du problème du sac-à-dos, car
le conteneur est vu comme un sac-à-dos avec lequel on veut transporter des objets de plus
grand valeur totale, sous des contraintes de capacité. On note x(j, W 0 ) la valeur maximale
qui peut être transportée dans un sac de capacité W 0 , en ne se servant que des j premiers
objets.
On a l’équation (programmation dynamique)
x(j, W 0 ) = max(x(j − 1, W 0 ), x(j − 1, W 0 − wj ) + cj )
qui se lit : le remplissage optimal x(j, W 0 ) d’un sac de capacité W 0 , avec les objets de 1 à j,
— soit n’utilise pas le jème objet, et dans ce cas x(j, W 0 ) = x(j − 1, W 0 )
— soit utilise le jème objet, et dans ce cas x(j, W 0 ) = x(j − 1, W 0 − wj ) + cj .
La complexité de l’algorithme est : O(nW ). En effet, il faut calculer tous les x(j, W 0 ) qui
sont au nombre de nW , et une fois calculés x(j − 1, W 0 ) et x(j − 1, W 0 − wj ), la quantité
x(j, W 0 ) se calcule en temps constant. Ce n’est pas polynomial car W nécessite log2 (W ) bits
pour être codé. On dit que c’est un algorithme pseudo-polynomial.
3.1.4 Les poids sont quelconques, mais le graphe est sans circuit absorbant : encore la
programmation dynamique
Supposons maintenant que l’on se demande comment calculer un plus court chemin dans
un graphe orienté pondéré, non nécessairement acircuitique. C’est encore possible si le graphe
ne possède pas de circuit absorbant, i.e. de circuit dont la somme des poids est < 0. Ce cas
contient les deux cas précédents (graphe avec poids ≥ 0 et graphe acircuitique). Noter qu’une
fois encore, il existe toujours un plus court chemin qui soit un chemin élémentaire car si le
plus court chemin passe par un circuit, on peut supprimer ce circuit sans détériorer le poids
du chemin.
En fait, pour calculer un plus court chemin dans un graphe sans circuit absorbant, on
peut appliquer la méthode de la programmation dynamique vue ci-dessus.
On considère que les états sont les sommets (Xk = V ) et qu’à chaque instant on traverse
un arc. Le coût de la transition u → v, c’est w(u, v) si (u, v) ∈ A, et +∞ sinon. Avec les
notations de la programmation dynamique, λ(k, v), c’est donc le poids minimal d’un s-v
chemin comportant exactement k arcs.
