View
1
Download
0
Category
Preview:
Citation preview
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
}.
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
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)
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
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◮ passage de revue des parties A dans P(n)
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◮ 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 :
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◮ 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 :⊲ mise à jour de valeur_test
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◮ 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 :⊲ mise à jour de valeur_test⊲ mise en mémoire dans Sac = [[L[k] for k in A], ω, π]
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◮ 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 :⊲ 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)
+ et −Avantage◮ solution optimale au problèmeIn onvénients◮ omplexité en mémoire lourde pour P(n)
◮ temps d'exé ution exponentiels :
+ et −Avantage◮ solution optimale au problèmeIn onvénients◮ omplexité en mémoire lourde pour P(n)
◮ 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 :
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]
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]⊲ Res1←− Pb_Sa _Re (L[1:℄,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◮ 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]⊲ Res1←− Pb_Sa _Re (L[1:℄,P)⊲ si x [2] > P , sortie Res1
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]⊲ 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℄) :
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]⊲ 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
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]⊲ 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⋄ 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 :
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
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
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
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◮ pour n = 30 objets, estimations :
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◮ pour n = 30 objets, estimations :
{ pour la re her he dans P(n) : ≃ 6 heures et demie
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◮ pour n = 30 objets, estimations :
{ pour la re her he dans P(n) : ≃ 6 heures et demiepour la re her he ré ursive : ≃ 10 minutes
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◮ pour n = 30 objets, estimations :
{ 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 :
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◮ pour n = 30 objets, estimations :
{ 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
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◮ pour n = 30 objets, estimations :
{ 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 jourspour la re her he ré ursive : ≃ 7 jours 5 heures
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◮ pour n = 30 objets, estimations :
{ 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 jourspour la re her he ré ursive : ≃ 7 jours 5 heures◮ pour n = 50 objets, estimations :
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◮ pour n = 30 objets, estimations :
{ 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 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 !!
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◮ pour n = 30 objets, estimations :
{ 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 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 ré ursive : ≃ 20 années 283 jours
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◮ pour n = 30 objets, estimations :
{ 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 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 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
Heuristique F : (w , p) 7→p
wPrin ipe
Heuristique F : (w , p) 7→p
wPrin ipe◮ tri des objets par quotients poids
valeur roissants
Heuristique F : (w , p) 7→p
wPrin ipe◮ tri des objets par quotients poids
valeur roissants
valeurspoids
wk
pk
b
bb
b
b
bb
b
b
Heuristique F : (w , p) 7→p
wPrin ipe◮ tri des objets par quotients poids
valeur roissants
valeurspoids
wk
pk
b
bb
b
b
bb
b
bb
Heuristique F : (w , p) 7→p
wPrin ipe◮ tri des objets par quotients poids
valeur roissants
valeurspoids
wk
pk
b
bb
b
b
bb
b
bb
b
Heuristique F : (w , p) 7→p
wPrin ipe◮ tri des objets par quotients poids
valeur roissants
valeurspoids
wk
pk
b
bb
b
b
bb
b
bb
b
b
Heuristique F : (w , p) 7→p
wPrin ipe◮ tri des objets par quotients poids
valeur roissants
valeurspoids
wk
pk
b
bb
b
b
bb
b
bb
b
b
b
Heuristique F : (w , p) 7→p
wPrin ipe◮ tri des objets par quotients poids
valeur roissants
valeurspoids
wk
pk
b
bb
b
b
bb
b
bb
b
b
b
b
Heuristique F : (w , p) 7→p
wPrin ipe◮ tri des objets par quotients poids
valeur roissants
valeurspoids
wk
pk
b
bb
b
b
bb
b
bb
b
b
b
b
b
Heuristique F : (w , p) 7→p
wPrin ipe◮ tri des objets par quotients poids
valeur roissants
valeurspoids
wk
pk
b
bb
b
b
bb
b
bb
b
b
b
b
bb
Heuristique F : (w , p) 7→p
wPrin ipe◮ tri des objets par quotients poids
valeur roissants
valeurspoids
wk
pk
b
bb
b
b
bb
b
bb
b
b
b
b
bb
b
Heuristique F : (w , p) 7→p
wPrin ipe◮ tri des objets par quotients poids
valeur roissants
valeurspoids
wk
pk
b
bb
b
b
bb
b
bb
b
b
b
b
bb
b
b
Heuristique F : (w , p) 7→p
wPrin ipe◮ tri des objets par quotients poids
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
Heuristique F : (w , p) 7→p
wPrin ipe◮ tri des objets par quotients poids
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℄))
Heuristique F : (w , p) 7→p
wAvantages de ette heuristique
Heuristique F : (w , p) 7→p
wAvantages de ette heuristique◮ temps de al uls très ourts :
Heuristique F : (w , p) 7→p
wAvantages de ette heuristique◮ temps de al uls très ourts :
Heuristique F : (w , p) 7→p
wAvantages de ette heuristique◮ sortie assez performante :
Heuristique F : (w , p) 7→p
wAvantages de ette heuristique◮ sortie assez performante :
Heuristique F : (w , p) 7→p
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
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
Exemple
ExempleDonnées
ExempleDonnées◮ produ tion de deux types de pro esseurs Pr A et Pr B
ExempleDonnées◮ produ tion de deux types de pro esseurs Pr A et Pr B
◮ tableau des ara téristiques :
ExempleDonnées◮ produ tion de deux types de pro esseurs Pr A et Pr B
◮ tableau des ara téristiques :Pr nbre barrettes tps (en min) pro�t (en e)A 2 3 400B 6 1 800
ExempleDonnées◮ produ tion de deux types de pro esseurs Pr A et Pr B
◮ 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 :
ExempleDonnées◮ produ tion de deux types de pro esseurs Pr A et Pr B
◮ 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
ExempleDonnées◮ produ tion de deux types de pro esseurs Pr A et Pr B
◮ 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⊲ au maximum 10000 pro esseurs à vendre
ExempleDonnées◮ produ tion de deux types de pro esseurs Pr A et Pr B
◮ 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⊲ au maximum 10000 pro esseurs à vendre⊲ au maximum 48000 barrettes
ExempleDonnées◮ produ tion de deux types de pro esseurs Pr A et Pr B
◮ 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⊲ 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
Reformulation du problèmeDonnées◮ x1 : nbre de Pr A ; x2 : nbre de Pr B
◮ fon tion obje tif : z = 400 x1 + 800 x2
Reformulation du problèmeDonnées◮ x1 : nbre de Pr A ; x2 : nbre de Pr B
◮ 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
Reformulation du problèmeDonnées◮ x1 : nbre de Pr A ; x2 : nbre de Pr B
◮ fon tion obje tif : z = 400 x1 + 800 x2◮ ontraintes :
2 x1 + 6 x2 6 48000x1 + x2 6 100003 x1 + x2 6 24000x1 > 0x2 > 0Prin ipe de résolution graphique
Reformulation du problèmeDonnées◮ x1 : nbre de Pr A ; x2 : nbre de Pr B
◮ fon tion obje tif : z = 400 x1 + 800 x2◮ ontraintes :
2 x1 + 6 x2 6 48000x1 + x2 6 100003 x1 + x2 6 24000x1 > 0x2 > 0Prin ipe de résolution graphique
◮ haque ontrainte ←→ demi-plan
Reformulation du problèmeDonnées◮ x1 : nbre de Pr A ; x2 : nbre de Pr B
◮ fon tion obje tif : z = 400 x1 + 800 x2◮ ontraintes :
2 x1 + 6 x2 6 48000x1 + x2 6 100003 x1 + x2 6 24000x1 > 0x2 > 0Prin ipe de résolution graphique
◮ haque ontrainte ←→ demi-plan◮ ensemble des ontraintes ←→ polygone onvexe C
Reformulation du problèmeDonnées◮ x1 : nbre de Pr A ; x2 : nbre de Pr B
◮ fon tion obje tif : z = 400 x1 + 800 x2◮ ontraintes :
2 x1 + 6 x2 6 48000x1 + x2 6 100003 x1 + x2 6 24000x1 > 0x2 > 0Prin ipe de résolution graphique
◮ haque ontrainte ←→ demi-plan◮ ensemble des ontraintes ←→ polygone onvexe C
◮ tra é des droites parallèles Dk : 400 x + 800 y = k
Reformulation du problèmeDonnées◮ x1 : nbre de Pr A ; x2 : nbre de Pr B
◮ fon tion obje tif : z = 400 x1 + 800 x2◮ ontraintes :
2 x1 + 6 x2 6 48000x1 + x2 6 100003 x1 + x2 6 24000x1 > 0x2 > 0Prin ipe de résolution graphique
◮ haque ontrainte ←→ demi-plan◮ ensemble des ontraintes ←→ polygone onvexe C
◮ 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
Résolution graphique
x2 > 0
Résolution graphique
x2 > 0
x 1>0
Résolution graphique
x2 > 0
x 1>0x1 +
x2 6 10000
Résolution graphique
x2 > 0
x 1>0x1 +
x2 6 100002 x1 + 6 x2 6 48000x1 + x2 6 10000
Résolution graphique
x2 > 0
x 1>0x1 +
x2 6 100002 x1 + 6 x2 6 48000x1 + x2 6 100003x1
+x2
6 24000x1 +
x2 6 10000
Résolution graphique
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
Résolution graphique
b
b
b
b
b
Résolution graphique
b
b
b
b
b
k = 0
Résolution graphique
b
b
b
b
b
k = 10 6
Résolution graphique
b
b
b
b
b
k = 1.5 · 10 6
Résolution graphique
b
b
b
b
b
k = 2 · 10 6
Résolution graphique
b
b
b
b
b
k = 2.5 · 10 6
Résolution graphique
b
b
b
b
b
k = 3 · 10 6
Résolution graphique
b
b
b
b
b
k = 3.5 · 10 6
Résolution graphique
b
b
b
b
b
k = 4 · 10 6
Résolution graphique
b
b
b
b
b
k = 4.5 · 10 6
Résolution graphique
b
b
b
b
b
k = 5 · 10 6
Résolution graphique
b
b
b
b
b
k = 5.5 · 10 6
Résolution graphique
b
b
b
b
b
k = 6 · 10 6
Résolution graphique
b
b
b
b
b
k = 6.5 · 10 6
Résolution graphique
b
b
b
b
b
k = 7 · 10 6
Résolution graphique
b
b
b
b
b
k = 6.8 · 10 6
Résolution graphique
b
b
b
b
b
k = 6.8 · 10 6
Résolution graphique
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
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
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◮ navigation sur les sommets d'un polytope onvexe pouraugmenter z à partir d'un sommet initial eninter hangeant des variables de base et auxiliaires
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◮ 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
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◮ 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
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◮ 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
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
◮ fon tion obje tif : z = 400 x1 + 800 x2
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
◮ fon tion obje tif : z = 400 x1 + 800 x2Solution de départ
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
◮ fon tion obje tif : z = 400 x1 + 800 x2Solution de départ◮ solution : x1 = x2 = 0 ; x3 = 48000, x4 = 10000 et
x5 = 24000
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
◮ 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
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◮ solution (0, 0, 48000, 10000, 24000) et z = 400x1 + 800x2
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◮ solution (0, 0, 48000, 10000, 24000) et z = 400x1 + 800x2◮ variables de base x3, x4, x5
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◮ 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
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◮ 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
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◮ 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
Cal uls sur les systèmes linéairesÉtape 2◮
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
Cal uls sur les systèmes linéairesÉtape 2◮
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
Cal uls sur les systèmes linéairesÉtape 2◮
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◮ variables de base x2, x4, x5
Cal uls sur les systèmes linéairesÉtape 2◮
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◮ variables de base x2, x4, x5◮ augmenter au maximum x1 (pour optimiser z) pourrespe ter les ontraintes : x1 ←− 3000
Cal uls sur les systèmes linéairesÉtape 2◮
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◮ 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
Cal uls sur les systèmes linéairesÉtape 2◮
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◮ 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
Cal uls sur les systèmes linéairesÉtape 3◮
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
Cal uls sur les systèmes linéairesÉtape 3◮
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
Cal uls sur les systèmes linéairesÉtape 3◮
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◮ variables de base x1, x2, x5
Cal uls sur les systèmes linéairesÉtape 3◮
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◮ 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é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
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
Problème du sa à dos par re her he opérationnellePrin ipe◮ obje tif : z =
n∑
k=1 xk wk/ ontrainte : n∑
k=1 xk pk 6 P
Problème du sa à dos par re her he opérationnellePrin ipe◮ obje tif : z =
n∑
k=1 xk wk/ ontrainte : n∑
k=1 xk pk 6 P
◮ optimisation ombinatoire : in onnues xk ∈ {0, 1}
Problème du sa à dos par re her he opérationnellePrin ipe◮ obje tif : z =
n∑
k=1 xk wk/ ontrainte : n∑
k=1 xk pk 6 P
◮ optimisation ombinatoire : in onnues xk ∈ {0, 1}◮ re her he opérationnelle : in onnues xk ∈ [0, 1]
Problème du sa à dos par re her he opérationnellePrin ipe◮ obje tif : z =
n∑
k=1 xk wk/ ontrainte : 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
Problème du sa à dos par re her he opérationnellePrin ipe◮ obje tif : z =
n∑
k=1 xk wk/ ontrainte : 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
Problème du sa à dos par re her he opérationnellePrin ipe◮ obje tif : z =
n∑
k=1 xk wk/ ontrainte : 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.
Recommended