1- Modèles de chemins (Programmation dynamique): le problème du sac a dos

[@ARO17]

Merci pour cette série de cours !

[@remicoutant7898]

Bonjour, J’étudie le problème du sac à dos et je cherche à déterminer une borne sup. Quel algorithme utilisez vous ou du moins de quel manière déterminez vous la borne 16,5 dans cet exemple? Et comment appliquer le problème du sac à dos à l’algorithme du simplexe pour déterminer des bornes? Merci pour votre vidéo

[@doubadmohamed5088]

Bonjour Et alors vous pouvez nous dire l'algorithme qui nous donne la solution de la relaxation linéaire du sac à dos sans passer par le simplexe.

[@rechercheoperationnelle8907]

Bonjour Doubad, La relaxation linéaire autorise de prendre des valeurs fractionnaires pour x_i, cela revient à s'autoriser à prendre des fractions d'objets. Autrement dit, il n'y aura pas de place perdue dans le sac si on peut fractionner les objets. On peut donc simplement trier les objets selon leur "valeur par unité de poids" (euros/kg) et remplir gloutonnement le sac jusqu'à saturer la capacité de 10 avec ceux qui rapportent le plus. Sur notre exemple cela donnerait des gains de: 3/2, 5/3, 6/4, 7/4, 10/8 c'est dire en valeur numérique (pour comparer facilement): 1.5, 1.666, 1.5, 1.75, 1.25 ainsi l'objet 4 rapporte le plus par kilo, il rapport 1.75 euros. La relaxation linéaire va donc prendre: l'objet 4, l'objet 2 et 3/4 de l'objet 3 (ou encore l'objet 1 + 1/4 de l'objet 3 car ils ont le même gain par unité de poids: 1.5 euros). Cela donne une valeur de 16.5 obtenue avec une fraction de l'objet 3. on aurait donc une solution optimale de relaxation linéaire égale par exemple à: x_1 = 0, x_2 = 1, x_3 = 0.75, x_4 = 1 Cela t'aide ? Bonne journée !

[@onetonice8406]

Je ne comprends pas pq, à 7:34 la borne optimal ne serait pas plutot v1;v4;v3 pour un poid max de 6 on aurait une valeur à 10 donc le sous chemin n'est optimal à part si l'on ai obligé de placer les objets dans le sac par ordre croissant de valeur ou d'indice

[@rechercheoperationnelle8907]

Bonjour, Je ne suis pas sûr de te comprendre. En tout cas il n'y a pas d'ordre dans le sac. Ta solution avec les objets 1,4,3 est la même que 1,3,4 (Poids 10, Valeur 16). Si on ignore l'objet 4 (on le considère comme étant dans le sac), on a sous-problème restreints aux objets {1,2,3,5} et à une capacité de 6. Une solution optimale est alors 1,3 (Valeur 9, Poids 6) et je n'en vois pas d'autres (attention sans l'objet 4 hein). Est ce que cela clarifie ?

[@onetonice8406]

@@rechercheoperationnelle8907 oui merci je n'avais pas encore assimilé la notion d'ordre topologique, la solution 1,3 semble donc la plus optimale merci pour votre réponse