Problème de math du jour! - Page 1

on a N produit,

chaque produit a un prix différent,

on a un montant TOTAL,

le but est de trouver une combinaison de X nombres de produit pour chaque produit n, tel que cette combinaison est la plus proche du total, par exemple:

produit 1: 15 €
produit 2: 35 €
produit 3: 40 €
produit 4: 12 €

Total: 310 €

par exemple: 15* 2 + 40 * 7

il faut juste une solution

Bonne chance et arrachez vous les tcheveuls!!
C'est un algo qu'il faut trouver....

simplex ?

Le "brute force" fonctionne aussi si les montants sont suffisamment petits.

Pfff tout de suite ... c sur toi reflechir ..

Fatal error : NP-complete problem detected. Aborting.

Tu as l'algorithme LLL qui marche de manière approximative et qui est polynômial, mais évidemment ne t'attends pas à mieux qu'un algo exponentiel si tu veux une solution _exacte_.

Donc Kevin n'a pas tort

Comment tu vois que c'est un pb NP-Complet ?
Tu connaissais déjà le problème ?

Tu as appris ça où ?

Traduction ?

Sasume> Oui, c'est connu comme pb. D'ailleurs c'est marrant, je viens de faire une recherche Google sur le sujet et j'ai vu pas mal de fois le nom d'un de mes profs

alexis>
Voilà :

Erreur fatale : problème NP-complet détecté. Annulation en cours.

Et en pratique, NP-dur ça veut dire que si la classe P des programmes exécutables en temps polynômial sur un ordinateur est différente de la classe NP des programmes exécutables en temps polynômial sur un ordinateur "infiniment parallèle" [google machine de turing non déterministe pour plus de détails], hypothèse dont on ne sait pas si elle est vraie ou pas (mais qui a "pas mal de chances" de l'être), eh bien alors l'algorithme ne pourra pas être exécuté en temps polynômial. Donc ça veut plus ou moins dire que le problème est de complexité (au moins :-D en tout cas ici, exactement) exponentielle. NP-complet est comme NP-dur sauf qu'on a en plus la garantie que le problème est un problème appartenant à la classe NP. Et n'oublie pas que Google est ton ami si tu veux plus de détails :-p

Euh cela dit maintenant que j'y repense dans le cas qui nous intéresse les coefficients sont positifs, et donc ça doit simplifier énormément le problème si on a une borne supérieure de la somme à obtenir, et le rendre un peu plus complexe dans les autres cas


Au fait :
yAro> Ici les coefficients sont entiers, et le simplex s'applique plutôt à des corps, non?

Bah, c'est quand meme un probleme linéaire, on peut le relacher et traiter le probleme dans R avec un simplexe.
D'ailleur, c'est un probleme de simplexe classique : PL avec contraintes, a priori, tout se passe bien... D'ailleur, on a fait le meme en cours
Ensuite, on applique différentes contraintes pour trouver une solution dans N.

Euh, NP-complet, ça ne veut pas plutôt dire que si ce problème particulier est soluble en temps polynômial (de façon déterministe), alors P = NP ?

guilc>
Mais oui #pipo#

Bon alors on se partage le boulot : moi je traite dans R le problème, je te fournis même un algorithme polynomial (je le mets en spoiler, histoire de pas tout dévoiler non plus 310 = 20.6666*15+0*35+0*40+0*12). Maintenant à toi de jouer et de montrer comment tu appliques ces contraintes pour en dériver une solution dans N

Si par le plus grand des hasards tu ne trouvais pas, c'est peut-être que tu confonds espace vectoriel et anneau intègre (la multiplication dans Z ressemble bcp à l'addition dans un ev, mais l'addition dans Z donne des interactions très riches qui interviennent ici - et qui n'ont rien d'analogue aux opérations linéaires, donc ça ne sert à rien d'essayer d'appliquer des méthodes d'optimisation linéaire)

Sally> je ne vois pas de différence avec ma définition : j'ai dit que si P != NP, alors un NP-dur n'était pas soluble en temps polynômial. Ca serait pas la contraposée?

Oui pardon j'avais mal lu #malalatete#

Pollux :
guilc>
Mais oui #pipo#

Bon alors on se partage le boulot : moi je traite dans R le problème, je te fournis même un algorithme polynomial (je le mets en spoiler, histoire de pas tout dévoiler non plus 310 = 20.6666*15+0*35+0*40+0*12). Maintenant à toi de jouer et de montrer comment tu appliques ces contraintes pour en dériver une solution dans N

Si par le plus grand des hasards tu ne trouvais pas, c'est peut-être que tu confonds espace vectoriel et anneau intègre (la multiplication dans Z ressemble bcp à l'addition dans un ev, mais l'addition dans Z donne des interactions très riches qui interviennent ici - et qui n'ont rien d'analogue aux opérations linéaires, donc ça ne sert à rien d'essayer d'appliquer des méthodes d'optimisation linéaire)

Bon, j'en ai un peu marre qu'on se foute de ma gueule comme ça...
Ce genre de méthode existe, on les a évoqué en cours de recherche opérationnelle... Ca s'appelle le "Branch and Cut" sur une relaxation Lagrangienne.
Une petite recherche rapide sur google pour montrer rapidement de quoi il retourne :
http://www.ima.umn.edu/talks/workshops/9-9-13.2002/miller/hyg2gny9.pdf
http://www710.univ-lyon1.fr/~csolnon/publications/jfplc97.ps (page 17)
http://www.ms.ic.ac.uk/jeb/book/chapter5.pdf
et j'en passe... (vous avez aussi des doigts et un navigateur pour aller sur google).

Et si je ne répond pas a ta question, c'est qu'on ne l'a pas pratiqué en cours (on s'arretait a la relaxation lagrangienne), on l'a juste évoqué. Et d'autre part, c'est que j'ai me pas qu'on me prenne pour un con quand je dis quelque chose. Quand je me trompe, je veux bien qu'on me le dise gentillement, mais quand je dis un truc vrai, faudrait voir a pas trop me prendre pour un con...

A bon entendeur, Salut !

C'est vraiment nul, ton truc, là, franchement, on en mange tous les matins dix à notre petit déj, des trucs comme ça - par ex, estimation des paramètres d'ARMAV, en gros, t'as 100* plus de paramètres à chercher -

J'aurai dit moindres carrés, si on avait eu un peu plus de valeurs, mais sinon on peut sans doute tenter l'approche inverse généralisée.

http://www710.univ-lyon1.fr/~csolnon/publications/jfplc97.ps

tiens, ct ma prof d'algo en première année à l'IUT,
et un de mes deux prof responsable de projet de fin d'IUT en seconde année

Miles, tu peux m'expliquer la technique inverse généralisée?

Ou quelqu'un peut me donne run exemple d'algo solution à ce probleme, car la je patoge toujours

Je precise qu'en math, je suis un bille par rapport a vous, j'ai un niveau bts en math ...

BTS pOwA !!

alexis :
Miles, tu peux m'expliquer la technique inverse généralisée?

Ou quelqu'un peut me donne run exemple d'algo solution à ce probleme, car la je patoge toujours

tu pose ton problème sous forme matricielle Y = AX, sachant que tu aimerais bien inverser A, mais tu ne peux pas, alors tu multiplies par la transposée à gauche.

J'ai pas regardé ce que ça donnait comme résultat dans ce cas. Le résultat est peut-être négatif, auquel cas, il faudrait s'amuser avec des variations sur A, sans doute.