353
© Dunod – Toute reproduction non autorisée est un délit.
8.8 Pro gramme linéaire en nombres entiers…
et plus géné ra le ment :
c
a 1 # x 1 1 a 2 # x 2 1 c 1 a n # x n < b
x 1
,
x 2
,
,
x n
5 0 ou 1
c 1 # x 1 1 c 2 # x 2 1 c 1 c n # x n 5 z 3max4
Onrésoutlespro blèmesdeknapsackàl’aidederecherchesarbo res centes(pro cé -
dures de sépa ra tion et éva lua tion pro gres sives, cf 4.10.2), ou bien à l’aide de la pro -
gram ma tion dyna mique. Pour l’exemple ci- dessus, l’opti mum est : x 1 = x 4 = 1 ; x 2 =
x 3 = 0 ; z* = 6 400 euros.
Don nons main te nant une brève des crip tion des pro blèmes de par tion ne ment et de
recou vre ment : soit un ensemble Ε = {e 1 , e 2 , …, e m }dem élé ments et une famille F
de n sous- ensembles (ou « par ties ») de E, non vides : ^ 5{P 1 , P 2 …, P n }.
Un tableau A = [a ij ] de for mat m × n indique si l’élé ment e i de E appar tient à la
par tie P j (alors a ij = 1) ou pas (a ij =0).Onrechercheàsélec tion nerunensembledepar ties extraites de ^, tel que tout élé ment de Ε soit cou vert une fois et une seule
(pro blème de « par tition ne ment ») ou bien au moins une fois (pro blème de « recou
vre ment »).
Dans l’exemple ci- dessus : Ε = {e 1 , e 2 , …, e 6 }et^ = {P 1 , P 2 , …, P 5 }
{P 1 , P 2 , P 4 , P 5 }estunepar titiondeE, tan dis que {P 1 , P 2 , P 3 }estunrecou vre ment(l’élé ment e 2 étant cou vert deux fois).
On asso cie à chaque par tie P j un coût c j > 0 ; le cri tère est alors de minimi ser la
sommedescoûtsdespar tiessélec tion nées.Lafor mu la tiondupro blèmedepar tition -
ne ment est la sui vante (la variable x j , j = 1, c , n, sera prise égale à 1 si la par tie P j
est sélec tion née et à 0 sinon).
Sur l’exemple de partitionnement ci- dessus :
c
x 1 5 1 (e 1 couvert) ; x 1 1 x 3 5 1 (e 2 couvert) ; x 2 5 1 (e 3 couvert);
x 3 1 x 4 5 1 (e 4 couvert) ; x 3 1 x 5 5 1 (e 5 couvert) ; x 3 5 x 4 5 1 (e 6 couvert).
x j 5 0 ou 1 (j 5 1, 2, c , 6) ; minimiser c 1 ? x 1 1 c 2 ? x 2 1 c 1 c 6 ? x 6 = z
En fait ce sys tème de contraintes admet une seule solu tion : x 1 = x 2 = x 4 = x 5 = 1 et
x 3 = 0 car l’exemple est de très petite taille et très contraint.
© Dunod – Toute reproduction non autorisée est un délit.
8.8 Pro gramme linéaire en nombres entiers…
et plus géné ra le ment :
c
a 1 # x 1 1 a 2 # x 2 1 c 1 a n # x n < b
x 1
,
x 2
,
,
x n
5 0 ou 1
c 1 # x 1 1 c 2 # x 2 1 c 1 c n # x n 5 z 3max4
Onrésoutlespro blèmesdeknapsackàl’aidederecherchesarbo res centes(pro cé -
dures de sépa ra tion et éva lua tion pro gres sives, cf 4.10.2), ou bien à l’aide de la pro -
gram ma tion dyna mique. Pour l’exemple ci- dessus, l’opti mum est : x 1 = x 4 = 1 ; x 2 =
x 3 = 0 ; z* = 6 400 euros.
Don nons main te nant une brève des crip tion des pro blèmes de par tion ne ment et de
recou vre ment : soit un ensemble Ε = {e 1 , e 2 , …, e m }dem élé ments et une famille F
de n sous- ensembles (ou « par ties ») de E, non vides : ^ 5{P 1 , P 2 …, P n }.
Un tableau A = [a ij ] de for mat m × n indique si l’élé ment e i de E appar tient à la
par tie P j (alors a ij = 1) ou pas (a ij =0).Onrechercheàsélec tion nerunensembledepar ties extraites de ^, tel que tout élé ment de Ε soit cou vert une fois et une seule
(pro blème de « par tition ne ment ») ou bien au moins une fois (pro blème de « recou
vre ment »).
Dans l’exemple ci- dessus : Ε = {e 1 , e 2 , …, e 6 }et^ = {P 1 , P 2 , …, P 5 }
{P 1 , P 2 , P 4 , P 5 }estunepar titiondeE, tan dis que {P 1 , P 2 , P 3 }estunrecou vre ment(l’élé ment e 2 étant cou vert deux fois).
On asso cie à chaque par tie P j un coût c j > 0 ; le cri tère est alors de minimi ser la
sommedescoûtsdespar tiessélec tion nées.Lafor mu la tiondupro blèmedepar tition -
ne ment est la sui vante (la variable x j , j = 1, c , n, sera prise égale à 1 si la par tie P j
est sélec tion née et à 0 sinon).
Sur l’exemple de partitionnement ci- dessus :
c
x 1 5 1 (e 1 couvert) ; x 1 1 x 3 5 1 (e 2 couvert) ; x 2 5 1 (e 3 couvert);
x 3 1 x 4 5 1 (e 4 couvert) ; x 3 1 x 5 5 1 (e 5 couvert) ; x 3 5 x 4 5 1 (e 6 couvert).
x j 5 0 ou 1 (j 5 1, 2, c , 6) ; minimiser c 1 ? x 1 1 c 2 ? x 2 1 c 1 c 6 ? x 6 = z
En fait ce sys tème de contraintes admet une seule solu tion : x 1 = x 2 = x 4 = x 5 = 1 et
x 3 = 0 car l’exemple est de très petite taille et très contraint.