Optimisation d'une combinaison linéaire - Page 1

1

Le 09/09/2011 à 21:13

Bonjour,

J'ai l'impression que mon problème est pourtant simple, mais je n'arrive pas à trouver une piste de départ.

Mon problème :
J'ai un total T
J'ai une liste de valeurs connues.
Je cherche la combinaison linéaire de ces valeurs optimale qui me permettra d'atteindre au plus près le total T.

Avec une équation, je cherche à maximiser :

Merci d'avance pour toute idée

2

Le 10/09/2011 à 16:21

Hmmm ça ne m'étonnerait pas que ça soit NP-complet, ce problème...

Les droits inaliénables du troll :
1) le droit d'avoir raison
2) le droit d'être péremptoire
3) le droit de ne pas lire
4) le droit de ne pas répondre
5) le droit d'être de mauvaise foi
6) Autant pour moi / Faignant / Vivent Tintin et Milou

3

Le 11/09/2011 à 23:38

Ce n'est pas assimilable à une version unidimensionnelle du problème de rangement des colis (NP-complet, apparemment) dont on parlait y'a pas longtemps dans un autre topic ?

— Zeroblog —

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

4

Le 12/09/2011 à 17:40

En effet, ça y ressemble en dimension 1 je pense.

Le lien du topic auquel tu penses à mon avis :
topics/118803-cherche-programme-plan-de-chargement#11

Effectivement, je pense que c'est un problème du type :
http://fr.wikipedia.org/wiki/Optimisation_lin%C3%A9aire_en_nombres_entiers#Optimisation_lin.C3.A9aire_en_nombres_entiers

5

Le 12/09/2011 à 21:50

Oui, c'est bien à ça que je pensais

— Zeroblog —

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo