Le problème du sac à dos833duparc.free.fr/Cours_IPT_942/Sac.pdf · sac à dos n objets de valeurs p ositives w 1,···,w n et p oids p ositifs p 1,··· n faire rentrer dans un

Le problème du sac à dos

ProblématiqueRésolutions théoriquesTests sur les partiesPrin ipe ré ursifRésolutions appro héesNé essité d'une résolution appro héePrin ipes généraux de la résolution appro héeTri par heuristiqueHeuristique F : (w , p) 7→p

wRe her he opérationnelle par programmation linéaireRésolution graphiqueMéthode du simplexeImplémentation Python de l'algorithme du simplexeCon lusionProblème du sa à dos par re her he opérationnellePortées du problème du sa à dos

Mise en pla e

Mise en pla eProblématique du sa à dos

Mise en pla eProblématique du sa à dos◮ n objets de valeurs positives w1, · · · ,wn

Mise en pla eProblématique du sa à dos◮ n objets de valeurs positives w1, · · · ,wn et de poidspositifs p1, · · · , pn

Mise en pla eProblématique du sa à dos◮ n objets de valeurs positives w1, · · · ,wn et de poidspositifs p1, · · · , pn◮ faire rentrer dans un sa des objets dont la somme despoids ne dépasse pas un seuil P [ ontrainte℄ et la sommedes valeurs est maximale

Mise en pla eProblématique du sa à dos◮ n objets de valeurs positives w1, · · · ,wn et de poidspositifs p1, · · · , pn◮ faire rentrer dans un sa des objets dont la somme despoids ne dépasse pas un seuil P [ ontrainte℄ et la sommedes valeurs est maximaleModélisation

Mise en pla eProblématique du sa à dos◮ n objets de valeurs positives w1, · · · ,wn et de poidspositifs p1, · · · , pn◮ faire rentrer dans un sa des objets dont la somme despoids ne dépasse pas un seuil P [ ontrainte℄ et la sommedes valeurs est maximaleModélisation◮ al uler max{∑

k∈A

wk | A ⊂ J1, nK et ∑

k∈A

pk 6 P

}.



Test sur P(n)

Test sur P(n)Prin ipe

Test sur P(n)Prin ipe◮ liste L d'objets de format ["objet",valeur,poids℄ et P la ontrainte de poids

Test sur P(n)Prin ipe◮ liste L d'objets de format ["objet",valeur,poids℄ et P la ontrainte de poids◮ génération de P(n) par ré ursivité, ave n = len(L)


◮ valeur_test ←− 0


◮ valeur_test ←− 0◮ passage de revue des parties A dans P(n)



◮ si π =∑

k∈A

L[k][2] 6 P et ω =∑

k∈A

L[k][1] > valeur_test :



◮ si π =∑

k∈A

L[k][2] 6 P et ω =∑

k∈A

L[k][1] > valeur_test :⊲ mise à jour de valeur_test



◮ si π =∑

k∈A

L[k][2] 6 P et ω =∑

k∈A

L[k][1] > valeur_test :⊲ mise à jour de valeur_test⊲ mise en mémoire dans Sac = [[L[k] for k in A], ω, π]



◮ si π =∑

k∈A

L[k][2] 6 P et ω =∑

k∈A

L[k][1] > valeur_test :⊲ mise à jour de valeur_test⊲ mise en mémoire dans Sac = [[L[k] for k in A], ω, π]

◮ sortie : Sac

+ et −

+ et −Avantage

+ et −Avantage◮ solution optimale au problème

+ et −Avantage◮ solution optimale au problèmeIn onvénients

+ et −Avantage◮ solution optimale au problèmeIn onvénients◮ omplexité en mémoire lourde pour P(n)


◮ temps d'exé ution exponentiels :


◮ temps d'exé ution exponentiels :

Ré ursivité

Ré ursivitéPrin ipe de la fon tion ré ursive Pb_Sa _Re (L,P)

Ré ursivitéPrin ipe de la fon tion ré ursive Pb_Sa _Re (L,P)◮ liste L d'objets de format ["objet",valeur,poids℄ et P la ontrainte de poids

Ré ursivitéPrin ipe de la fon tion ré ursive Pb_Sa _Re (L,P)◮ liste L d'objets de format ["objet",valeur,poids℄ et P la ontrainte de poids◮ si L = [ ] ou (len(L) = 1 et L[0][2] > P), sortie :[[ ℄,0,0℄

Ré ursivitéPrin ipe de la fon tion ré ursive Pb_Sa _Re (L,P)◮ liste L d'objets de format ["objet",valeur,poids℄ et P la ontrainte de poids◮ si L = [ ] ou (len(L) = 1 et L[0][2] > P), sortie :[[ ℄,0,0℄◮ si len(L) = 1 et L[0][2] 6 P, sortie :[L,L[0℄[1℄,L[0℄[2℄℄

Ré ursivitéPrin ipe de la fon tion ré ursive Pb_Sa _Re (L,P)◮ liste L d'objets de format ["objet",valeur,poids℄ et P la ontrainte de poids◮ si L = [ ] ou (len(L) = 1 et L[0][2] > P), sortie :[[ ℄,0,0℄◮ si len(L) = 1 et L[0][2] 6 P, sortie :[L,L[0℄[1℄,L[0℄[2℄℄◮ si len(L) > 2 :


⊲ x ←− L[0]


⊲ x ←− L[0]⊲ Res1←− Pb_Sa _Re (L[1:℄,P)


⊲ x ←− L[0]⊲ Res1←− Pb_Sa _Re (L[1:℄,P)⊲ si x [2] > P , sortie Res1


⊲ x ←− L[0]⊲ Res1←− Pb_Sa _Re (L[1:℄,P)⊲ si x [2] > P , sortie Res1⊲ si x [2] 6 P , Res2←− PB_Sa _Re (L[1:℄,P-x[2℄) :



⋄ si Res1[1] > Res2[1] + x [1], sortie : Res1



⋄ si Res1[1] > Res2[1] + x [1], sortie : Res1⋄ sinon, sortie :[[x℄+Res2[0℄,x[1℄+Res2[1℄,x[2℄+Res2[2℄℄

+ et −

+ et −Avantages

+ et −Avantages◮ solution optimale au problème

+ et −Avantages◮ solution optimale au problème◮ temps de al uls réduits

+ et −Avantages◮ solution optimale au problème◮ temps de al uls réduitsIn onvénient

+ et −Avantages◮ solution optimale au problème◮ temps de al uls réduitsIn onvénient◮ temps d'exé ution en ore importants :

+ et −Avantages◮ solution optimale au problème◮ temps de al uls réduitsIn onvénient◮ temps d'exé ution en ore importants :



Né essité d'une résolution appro hée

Né essité d'une résolution appro héeEstimations des temps de al uls

Né essité d'une résolution appro héeEstimations des temps de al uls◮ lois approximatives des temps d'exé ution des algorithmesexa ts : T (n) = 10a log n+b


◮ algorithme ré ursif au moins 30 fois plus rapide


◮ algorithme ré ursif au moins 30 fois plus rapide◮ pour n = 30 objets, estimations :



{ pour la re her he dans P(n) : ≃ 6 heures et demie



{ pour la re her he dans P(n) : ≃ 6 heures et demiepour la re her he ré ursive : ≃ 10 minutes



{ pour la re her he dans P(n) : ≃ 6 heures et demiepour la re her he ré ursive : ≃ 10 minutes◮ pour n = 40 objets, estimations :




{ pour la re her he dans P(n) : ≃ 333 jours




{ pour la re her he dans P(n) : ≃ 333 jourspour la re her he ré ursive : ≃ 7 jours 5 heures




{ pour la re her he dans P(n) : ≃ 333 jourspour la re her he ré ursive : ≃ 7 jours 5 heures◮ pour n = 50 objets, estimations :





{ pour la re her he dans P(n) : ≃ 1114 années !!





{ pour la re her he dans P(n) : ≃ 1114 années !!pour la re her he ré ursive : ≃ 20 années 283 jours





{ pour la re her he dans P(n) : ≃ 1114 années !!pour la re her he ré ursive : ≃ 20 années 283 jours

Présentation du on eptPrin ipes et obje tifs

Présentation du on eptPrin ipes et obje tifs◮ avoir une résolution appro hée en temps raisonnable

Présentation du on eptPrin ipes et obje tifs◮ avoir une résolution appro hée en temps raisonnable◮ quanti�er la perte d'informations sur le résultat en sortie

Tri par Heuristique

Tri par HeuristiquePrin ipe

Tri par HeuristiquePrin ipe◮ liste L d'objets de format ["objet",valeur,poids℄ et P la ontrainte de poids

Tri par HeuristiquePrin ipe◮ liste L d'objets de format ["objet",valeur,poids℄ et P la ontrainte de poids◮ F : (v , p) 7→ F (v , p) une fon tion heuristique réelle

Tri par HeuristiquePrin ipe◮ liste L d'objets de format ["objet",valeur,poids℄ et P la ontrainte de poids◮ F : (v , p) 7→ F (v , p) une fon tion heuristique réelle◮ tri des objets selon F (valeur , poids) roissant

Tri par HeuristiquePrin ipe◮ liste L d'objets de format ["objet",valeur,poids℄ et P la ontrainte de poids◮ F : (v , p) 7→ F (v , p) une fon tion heuristique réelle◮ tri des objets selon F (valeur , poids) roissant◮ remplissage du sa selon et ordre

Tri par HeuristiquePrin ipe◮ liste L d'objets de format ["objet",valeur,poids℄ et P la ontrainte de poids◮ F : (v , p) 7→ F (v , p) une fon tion heuristique réelle◮ tri des objets selon F (valeur , poids) roissant◮ remplissage du sa selon et ordre

b

bb

b

b

bb

b

bvaleurspoids

wk

pk

Heuristique F : (w , p) 7→p

w


wPrin ipe


wPrin ipe◮ tri des objets par quotients poids

valeur roissants



valeur roissants

valeurspoids

wk

pk

b

bb

b

b

bb

b

b



valeur roissants

valeurspoids

wk

pk

b

bb

b

b

bb

b

bb



valeur roissants

valeurspoids

wk

pk

b

bb

b

b

bb

b

bb

b



valeur roissants

valeurspoids

wk

pk

b

bb

b

b

bb

b

bb

b

b



valeur roissants

valeurspoids

wk

pk

b

bb

b

b

bb

b

bb

b

b

b



valeur roissants

valeurspoids

wk

pk

b

bb

b

b

bb

b

bb

b

b

b

b



valeur roissants

valeurspoids

wk

pk

b

bb

b

b

bb

b

bb

b

b

b

b

b



valeur roissants

valeurspoids

wk

pk

b

bb

b

b

bb

b

bb

b

b

b

b

bb



valeur roissants

valeurspoids

wk

pk

b

bb

b

b

bb

b

bb

b

b

b

b

bb

b



valeur roissants

valeurspoids

wk

pk

b

bb

b

b

bb

b

bb

b

b

b

b

bb

b

b



valeur roissants

valeurspoids

wk

pk

b

bb

b

b

bb

b

bb

b

b

b

b

bb

b

b

b

bb

b

b

bb

b

bImplémentation : tri rapide par λ- al ul



valeur roissants

valeurspoids

wk

pk

b

bb

b

b

bb

b

bb

b

b

b

b

bb

b

b

b

bb

b

b

bb

b

bImplémentation : tri rapide par λ- al ulsorted(L,key=lambda objet : F(objet[1℄,objet[2℄))


wAvantages de ette heuristique


wAvantages de ette heuristique◮ temps de al uls très ourts :


wAvantages de ette heuristique◮ temps de al uls très ourts :


wAvantages de ette heuristique◮ sortie assez performante :


wAvantages de ette heuristique◮ sortie assez performante :


wAvantages de ette heuristique◮ sortie assez performante :◮ meilleure sortie que pour les tris dé roissants sur lesvaleurs puis roissants sur les poids ou vi e-versa puisremplissage du sa selon et ordre



Exemple

ExempleDonnées

ExempleDonnées◮ produ tion de deux types de pro esseurs Pr A et Pr B


◮ tableau des ara téristiques :


◮ tableau des ara téristiques :Pr nbre barrettes tps (en min) pro�t (en e)A 2 3 400B 6 1 800


◮ tableau des ara téristiques :Pr nbre barrettes tps (en min) pro�t (en e)A 2 3 400B 6 1 800◮ ontraintes supplémentaires :



⊲ 24000 minutes disponibles pour l'assemblage



⊲ 24000 minutes disponibles pour l'assemblage⊲ au maximum 10000 pro esseurs à vendre



⊲ 24000 minutes disponibles pour l'assemblage⊲ au maximum 10000 pro esseurs à vendre⊲ au maximum 48000 barrettes



⊲ 24000 minutes disponibles pour l'assemblage⊲ au maximum 10000 pro esseurs à vendre⊲ au maximum 48000 barrettes

◮ obje tif : maximiser le pro�t

Reformulation du problème

Reformulation du problèmeDonnées

Reformulation du problèmeDonnées◮ x1 : nbre de Pr A ; x2 : nbre de Pr B


◮ fon tion obje tif : z = 400 x1 + 800 x2


◮ fon tion obje tif : z = 400 x1 + 800 x2◮ ontraintes :

2 x1 + 6 x2 6 48000x1 + x2 6 100003 x1 + x2 6 24000x1 > 0x2 > 0



2 x1 + 6 x2 6 48000x1 + x2 6 100003 x1 + x2 6 24000x1 > 0x2 > 0Prin ipe de résolution graphique




◮ haque ontrainte ←→ demi-plan




◮ haque ontrainte ←→ demi-plan◮ ensemble des ontraintes ←→ polygone onvexe C





◮ tra é des droites parallèles Dk : 400 x + 800 y = k





◮ tra é des droites parallèles Dk : 400 x + 800 y = k

◮ al ul de la plus grande valeur k telle que Dk ∩ C 6= ∅

Résolution graphique


x2 > 0


x2 > 0

x 1>0


x2 > 0

x 1>0x1 +

x2 6 10000


x2 > 0

x 1>0x1 +

x2 6 100002 x1 + 6 x2 6 48000x1 + x2 6 10000


x2 > 0

x 1>0x1 +

x2 6 100002 x1 + 6 x2 6 48000x1 + x2 6 100003x1

+x2

6 24000x1 +

x2 6 10000


x2 > 0

x 1>0x1 +

x2 6 100002 x1 + 6 x2 6 48000x1 + x2 6 100003x1

+x2

6 24000x1 +

x2 6 10000b

b

b

b

b

C


b

b

b

b

b


b

b

b

b

b

k = 0


b

b

b

b

b

k = 10 6


b

b

b

b

b

k = 1.5 · 10 6


b

b

b

b

b

k = 2 · 10 6


b

b

b

b

b

k = 2.5 · 10 6


b

b

b

b

b

k = 3 · 10 6


b

b

b

b

b

k = 3.5 · 10 6


b

b

b

b

b

k = 4 · 10 6


b

b

b

b

b

k = 4.5 · 10 6


b

b

b

b

b

k = 5 · 10 6


b

b

b

b

b

k = 5.5 · 10 6


b

b

b

b

b

k = 6 · 10 6


b

b

b

b

b

k = 6.5 · 10 6


b

b

b

b

b

k = 7 · 10 6


b

b

b

b

b

k = 6.8 · 10 6


b

b

b

b

b

k = 6.8 · 10 6


b

b

b

b

b

k = 6.8 · 10 6x1 = 3000

x2 = 7000

Méthode du simplexe

Méthode du simplexePrin ipes généraux

Méthode du simplexePrin ipes généraux◮ la fon tion obje tif z atteint un maximum en un sommetde C


◮ transformation des ontraintes en égalités : ajout devariables auxiliaires


◮ transformation des ontraintes en égalités : ajout devariables auxiliaires◮ navigation sur les sommets d'un polytope onvexe pouraugmenter z à partir d'un sommet initial eninter hangeant des variables de base et auxiliaires


◮ transformation des ontraintes en égalités : ajout devariables auxiliaires◮ navigation sur les sommets d'un polytope onvexe pouraugmenter z à partir d'un sommet initial eninter hangeant des variables de base et auxiliaires◮ variables de base : variables n'apparaissant pas dans z etapparaissant dans la solution ourante du système


◮ transformation des ontraintes en égalités : ajout devariables auxiliaires◮ navigation sur les sommets d'un polytope onvexe pouraugmenter z à partir d'un sommet initial eninter hangeant des variables de base et auxiliaires◮ variables de base : variables n'apparaissant pas dans z etapparaissant dans la solution ourante du système◮ systèmes linéaires de Cramer pour les variables de base :pivot de Gauss


◮ transformation des ontraintes en égalités : ajout devariables auxiliaires◮ navigation sur les sommets d'un polytope onvexe pouraugmenter z à partir d'un sommet initial eninter hangeant des variables de base et auxiliaires◮ variables de base : variables n'apparaissant pas dans z etapparaissant dans la solution ourante du système◮ systèmes linéaires de Cramer pour les variables de base :pivot de Gauss◮ ondition d'arrêt lorsque les oe� ients devant lesvariables de base sont tous négatifs dans z

Appli ation à l'exemple

Appli ation à l'exempleSystème standardisé

Appli ation à l'exempleSystème standardisé◮ ontraintes :

2 x1 + 6 x2 + x3 = 48000x1 + x2 + x4 = 100003 x1 + x2 + x5 = 24000x1, x2, x3, x4, x5 > 0


2 x1 + 6 x2 + x3 = 48000x1 + x2 + x4 = 100003 x1 + x2 + x5 = 24000x1, x2, x3, x4, x5 > 0

◮ fon tion obje tif : z = 400 x1 + 800 x2


2 x1 + 6 x2 + x3 = 48000x1 + x2 + x4 = 100003 x1 + x2 + x5 = 24000x1, x2, x3, x4, x5 > 0

◮ fon tion obje tif : z = 400 x1 + 800 x2Solution de départ


2 x1 + 6 x2 + x3 = 48000x1 + x2 + x4 = 100003 x1 + x2 + x5 = 24000x1, x2, x3, x4, x5 > 0

◮ fon tion obje tif : z = 400 x1 + 800 x2Solution de départ◮ solution : x1 = x2 = 0 ; x3 = 48000, x4 = 10000 et

x5 = 24000


2 x1 + 6 x2 + x3 = 48000x1 + x2 + x4 = 100003 x1 + x2 + x5 = 24000x1, x2, x3, x4, x5 > 0

◮ fon tion obje tif : z = 400 x1 + 800 x2Solution de départ◮ solution : x1 = x2 = 0 ; x3 = 48000, x4 = 10000 et

x5 = 24000◮ obje tif asso ié : z = 0

Cal uls sur les systèmes linéaires

Cal uls sur les systèmes linéairesÉtape 1

Cal uls sur les systèmes linéairesÉtape 1◮

x1 x2 x3 x4 x52 6 1 0 0 480001 1 0 1 0 100003 1 0 0 1 24000400 800 0 0 0 0


x1 x2 x3 x4 x52 6 1 0 0 480001 1 0 1 0 100003 1 0 0 1 24000400 800 0 0 0 0◮ solution (0, 0, 48000, 10000, 24000) et z = 400x1 + 800x2


x1 x2 x3 x4 x52 6 1 0 0 480001 1 0 1 0 100003 1 0 0 1 24000400 800 0 0 0 0◮ solution (0, 0, 48000, 10000, 24000) et z = 400x1 + 800x2◮ variables de base x3, x4, x5


x1 x2 x3 x4 x52 6 1 0 0 480001 1 0 1 0 100003 1 0 0 1 24000400 800 0 0 0 0◮ solution (0, 0, 48000, 10000, 24000) et z = 400x1 + 800x2◮ variables de base x3, x4, x5◮ augmenter au maximum x2 (pour optimiser z) pourrespe ter les ontraintes : x2 ←− 8000


x1 x2 x3 x4 x52 6 1 0 0 480001 1 0 1 0 100003 1 0 0 1 24000400 800 0 0 0 0◮ solution (0, 0, 48000, 10000, 24000) et z = 400x1 + 800x2◮ variables de base x3, x4, x5◮ augmenter au maximum x2 (pour optimiser z) pourrespe ter les ontraintes : x2 ←− 8000◮ annulation de x3 : x3 sort de la base et x2 rentre


x1 x2 x3 x4 x52 6 1 0 0 480001 1 0 1 0 100003 1 0 0 1 24000400 800 0 0 0 0◮ solution (0, 0, 48000, 10000, 24000) et z = 400x1 + 800x2◮ variables de base x3, x4, x5◮ augmenter au maximum x2 (pour optimiser z) pourrespe ter les ontraintes : x2 ←− 8000◮ annulation de x3 : x3 sort de la base et x2 rentre◮ opération L1 ←− 1/6 L1 puis élimination de x2 dans lesautres lignes


x1 x2 x3 x4 x51/3 1 1/6 0 0 80002/3 0 −1/6 1 0 20008/3 0 −1/6 0 1 16000400/3 0 −400/3 0 0 −6.4 106


x1 x2 x3 x4 x51/3 1 1/6 0 0 80002/3 0 −1/6 1 0 20008/3 0 −1/6 0 1 16000400/3 0 −400/3 0 0 −6.4 106◮ solution (0, 8000, 0, 2000, 16000) et

z = 400/3x1 − 400/3x3 + 6.4 106



z = 400/3x1 − 400/3x3 + 6.4 106◮ variables de base x2, x4, x5



z = 400/3x1 − 400/3x3 + 6.4 106◮ variables de base x2, x4, x5◮ augmenter au maximum x1 (pour optimiser z) pourrespe ter les ontraintes : x1 ←− 3000



z = 400/3x1 − 400/3x3 + 6.4 106◮ variables de base x2, x4, x5◮ augmenter au maximum x1 (pour optimiser z) pourrespe ter les ontraintes : x1 ←− 3000◮ annulation de x4 : x4 sort de la base et x1 rentre



z = 400/3x1 − 400/3x3 + 6.4 106◮ variables de base x2, x4, x5◮ augmenter au maximum x1 (pour optimiser z) pourrespe ter les ontraintes : x1 ←− 3000◮ annulation de x4 : x4 sort de la base et x1 rentre◮ opération L2 ←− 3/2 L2 puis élimination de x1 dans lesautres lignes


x1 x2 x3 x4 x50 1 1/4 −1/2 0 70001 0 −1/4 3/2 0 30000 0 1/2 −4 1 80000 0 −100 −200 0 −6.8 106


x1 x2 x3 x4 x50 1 1/4 −1/2 0 70001 0 −1/4 3/2 0 30000 0 1/2 −4 1 80000 0 −100 −200 0 −6.8 106◮ solution (3000, 7000, 0, 0, 8000) et

z = −100x3 − 200x4 + 6.8 106



z = −100x3 − 200x4 + 6.8 106◮ variables de base x1, x2, x5



z = −100x3 − 200x4 + 6.8 106◮ variables de base x1, x2, x5◮ augmentation des variables impossible sans diminuer z : ondition d'arrêt

Cal uls sur les systèmes linéairesFin

Cal uls sur les systèmes linéairesFin◮ solution optimale (3000, 7000, 0, 0, 8000)

Cal uls sur les systèmes linéairesFin◮ solution optimale (3000, 7000, 0, 0, 8000)◮ obje tif optimal : z = 6.8 106.

Implémentation Python de l'algorithme du simplexe

Implémentation Python de l'algorithme du simplexeS ript Python

Implémentation Python de l'algorithme du simplexeS ript Pythondef Algo_Simplexe(M_standard) :M=M_standard. opy()p,q=M.shapej_max=argmax(M[-1,:-1℄)while M[-1,j_max℄>0 :i_ligne=0val=inffor i in range(p) :if M[i,j_max℄>0 and M[i,-1℄>0 and M[i,-1℄/M[i,j_max℄< val :i_ligne=ival=M[i,-1℄/M[i,j_max℄M[i_ligne,:℄/=M[i_ligne,j_max℄for k in range(p) :if k!=i_ligne :M[k,:℄-=M[k,j_max℄*M[i_ligne,:℄j_max=argmax(M[-1,:-1℄)Res=[℄for j in range(q-1) :if M[-1,j℄==0 :for i in range(p) :if M[i,j℄!= 0 : # on repère la ase de la variable hors baseRes.append(M[i,-1℄)breakelse :Res.append(0) # variable de base nullereturn [Res,-M[-1,-1℄℄ # solution optimale, obje tif optimal



Problème du sa à dos par re her he opérationnelle

Problème du sa à dos par re her he opérationnellePrin ipe

Problème du sa à dos par re her he opérationnellePrin ipe◮ obje tif : z =

n∑

k=1 xk wk


n∑

k=1 xk wk/ ontrainte : n∑

k=1 xk pk 6 P


n∑


k=1 xk pk 6 P

◮ optimisation ombinatoire : in onnues xk ∈ {0, 1}


n∑


k=1 xk pk 6 P

◮ optimisation ombinatoire : in onnues xk ∈ {0, 1}◮ re her he opérationnelle : in onnues xk ∈ [0, 1]


n∑


k=1 xk pk 6 P

◮ optimisation ombinatoire : in onnues xk ∈ {0, 1}◮ re her he opérationnelle : in onnues xk ∈ [0, 1]Exemple


n∑


k=1 xk pk 6 P

◮ optimisation ombinatoire : in onnues xk ∈ {0, 1}◮ re her he opérationnelle : in onnues xk ∈ [0, 1]Exemple◮ n = 3, sa : [[11, 7], [8, 6], [5, 4]] et P = 10


n∑


k=1 xk pk 6 P

◮ optimisation ombinatoire : in onnues xk ∈ {0, 1}◮ re her he opérationnelle : in onnues xk ∈ [0, 1]Exemple◮ n = 3, sa : [[11, 7], [8, 6], [5, 4]] et P = 10◮ tableau : x1 x2 x3 x4 x5 x6 x77 6 4 1 0 0 0 101 0 0 0 1 0 0 10 1 0 0 0 1 0 10 0 1 0 0 0 1 111 8 5 0 0 0 0 0

Di�érentes résolutions

Di�érentes résolutionsSolution exa te par ré ursivité

Di�érentes résolutionsSolution exa te par ré ursivité◮ solution optimale : [[8, 6], [5, 4]] de valeur 13

Di�érentes résolutionsSolution exa te par ré ursivité◮ solution optimale : [[8, 6], [5, 4]] de valeur 13Solution appro hée par heuristique

Di�érentes résolutionsSolution exa te par ré ursivité◮ solution optimale : [[8, 6], [5, 4]] de valeur 13Solution appro hée par heuristique◮ solution appro hée : [[11, 7]] de valeur 11

Di�érentes résolutionsSolution exa te par ré ursivité◮ solution optimale : [[8, 6], [5, 4]] de valeur 13Solution appro hée par heuristique◮ solution appro hée : [[11, 7]] de valeur 11Solution optimale en re her he opérationnelle

Di�érentes résolutionsSolution exa te par ré ursivité◮ solution optimale : [[8, 6], [5, 4]] de valeur 13Solution appro hée par heuristique◮ solution appro hée : [[11, 7]] de valeur 11Solution optimale en re her he opérationnelle◮ solution optimale : (1, 12 , 0, 0, 0, 12 , 1) de valeur z = 15

Di�érentes résolutionsSolution exa te par ré ursivité◮ solution optimale : [[8, 6], [5, 4]] de valeur 13Solution appro hée par heuristique◮ solution appro hée : [[11, 7]] de valeur 11Solution optimale en re her he opérationnelle◮ solution optimale : (1, 12 , 0, 0, 0, 12 , 1) de valeur z = 15◮ solution non entière ...

Portées du problème du sa à dos

Portées du problème du sa à dosImportan e pratique

Portées du problème du sa à dosImportan e pratique◮ problème universel trouvant des appli ations dansd'innombrables domaines (industriels, é onomiques, et .)

Portées du problème du sa à dosImportan e pratique◮ problème universel trouvant des appli ations dansd'innombrables domaines (industriels, é onomiques, et .)Importan e théorique

Portées du problème du sa à dosImportan e pratique◮ problème universel trouvant des appli ations dansd'innombrables domaines (industriels, é onomiques, et .)Importan e théorique◮ problème NP- omplet

Portées du problème du sa à dosImportan e pratique◮ problème universel trouvant des appli ations dansd'innombrables domaines (industriels, é onomiques, et .)Importan e théorique◮ problème NP- omplet◮ en lien dire t ave la onje ture P = NP.

Documents

Le problème du sac à dos833duparc.free.fr/Cours_IPT_942/Sac.pdf · sac à dos n objets de valeurs p ositives w 1,···,w n et p oids p ositifs p 1,··· n faire rentrer dans un