190
6 M´ ethodes de Monte Carlo par chaˆ ınes de Markov (MCMC)
Fig. 6.14. Remplissage de sac `
a dos
On notera que ce probl` eme de programmation lin´ eaire dans {0, 1}
d ne
peut ˆ etre r´ esolu par l’algorithme du simplexe qui fournit des solutions r´ eelles.
Comme la plupart des probl` emes d’optimisation combinatoire, le probl` eme du
sac `
a dos est riche d’interpr´ etations.
En math´ ematiques financi` eres, les objets de r´ ef´ erence peuvent repr´ esenter
des actifs financiers tels des actions ou des placements bancaires. Les valeurs
v i de chacun sont leurs prix en euros, les pond´ erations p i peuvent repr´ esenter
des indices de risques sur l’actif i. Le probl` eme de chargement d’un sac peut
s’´ etendre ` a des chargements de containers de bateaux. Dans ce contexte, les
objets de r´ ef´ erence sont bien entendu les d containers et leur valeur respective
v i . Les pond´ erations p i sont leur poids physique. Le but du remplissage est
d’optimiser la valeur du chargement sans faire une surcharge du bateau.
Ce probl` eme du sac ` a dos est bien connu en combinatoire. Il fait partie
de la classe des probl` emes dˆ ıts NP-complets. Tr` es bri` evement, ces probl` emes
peuvent ˆ etre r´ esolus en testant toutes les solutions possibles en un temps
polynomial.
6 M´ ethodes de Monte Carlo par chaˆ ınes de Markov (MCMC)
Fig. 6.14. Remplissage de sac `
a dos
On notera que ce probl` eme de programmation lin´ eaire dans {0, 1}
d ne
peut ˆ etre r´ esolu par l’algorithme du simplexe qui fournit des solutions r´ eelles.
Comme la plupart des probl` emes d’optimisation combinatoire, le probl` eme du
sac `
a dos est riche d’interpr´ etations.
En math´ ematiques financi` eres, les objets de r´ ef´ erence peuvent repr´ esenter
des actifs financiers tels des actions ou des placements bancaires. Les valeurs
v i de chacun sont leurs prix en euros, les pond´ erations p i peuvent repr´ esenter
des indices de risques sur l’actif i. Le probl` eme de chargement d’un sac peut
s’´ etendre ` a des chargements de containers de bateaux. Dans ce contexte, les
objets de r´ ef´ erence sont bien entendu les d containers et leur valeur respective
v i . Les pond´ erations p i sont leur poids physique. Le but du remplissage est
d’optimiser la valeur du chargement sans faire une surcharge du bateau.
Ce probl` eme du sac ` a dos est bien connu en combinatoire. Il fait partie
de la classe des probl` emes dˆ ıts NP-complets. Tr` es bri` evement, ces probl` emes
peuvent ˆ etre r´ esolus en testant toutes les solutions possibles en un temps
polynomial.