Algo de combinaison de modules

Fermé
sam - 26 oct. 2007 à 14:03
mamiemando Messages postés 33446 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 20 décembre 2024 - 29 oct. 2007 à 09:26
Bonjour,
cela fait déjà quelques jours que je me creuse la tête et j'ai besoin d'aide, voilà je dois trouver la plus petite combinaison ( en nombre de modules et en dimension totale) possible de modules de différentes tailles afin d'arriver à une dimension mini
c'est comme les légos en fait j'ai par exemple une dimension de 5200 à faire, j'ai des modules de 2540, 2130, 1040 et 540 à ma disposition et je dois trouver la combinaison la plus proche en dimension soit pour l'exemple 2540+2130+540
et tout ça dans une procedure PL/SQL !!!
si qlq'un a une idée, enfin si je me suis fais comprendre...

3 réponses

mamiemando Messages postés 33446 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 20 décembre 2024 7 812
26 oct. 2007 à 16:01
A ta place je regarderais du côté des problèmes de sac à dos.
https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_sac_%C3%A0_dos

Bonne chance
0
Ouaou !!!

ça correspond effectivement à mon problème mais alors ne n'y comprend rien :>
merci en tout cas à mamiemando pour le tuyau !!!
0
mamiemando Messages postés 33446 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 20 décembre 2024 7 812
29 oct. 2007 à 09:26
HUm alors en fait le problème de sac à dos est un problème classique en recherche opérationnelle. Si ma mémoire et bonne il se définit ainsi :
- chaque élément (xi) à une valeur (vi) et un poids (wi)
- le sac à dos ne permet de transporter qu'un certain poids (W)
- on cherche à remplir le sac à dos de sorte à transporter une valeur maximale

Concrètement en recherche opérationnelle, un problème se décrit :
- avec des variables et les ensembles de définition de ces variables (prends-je l'élément i ou pas : xi in {0,1} etc) dans la mesure du possible continue (les variables booléennes et entières rendent le problème plus difficile à résoudre pour un solveur)
- avec des contraintes (poids max : W, poids des éléments : les constantes wi ; le poids du sac : sum(wi.xi) d'où la contrainte sum(wi.xi) <= W) dans la mesure du possible large (<= et >= au lieu de < et >). Il faut dans la mesure du possible avoir des contraintes linéaires (ie de la forme sum(ai.xi) <= K ou ai et K sont des constantes).
- avec un objectif (valeur d'un objet : constantes vi ; objectif : max(sum(vi.xi)))

Une fois le problème modélisé sur le papier, si le problème est "difficile" on utilise un solveur (par exemple coin ou cplex). Or le problème de sac à dos est un problème difficile ! Par problème difficile il faut comprendre qu'on ne connaît pas d'algorithme polynomial pour le résoudre de manière exacte (d'où l'utilisation d'un solveur qui va explorer chaque combinaison d'objet). Quand la résolution est trop longue avec un solveur, on utilise souvent des meta heuristiques qui donnent souvent et très rapidement une solution de bonne qualité (presque optimale).

Pour résumer ce que je viens de te dire :
- retiens que ton problème a été archi traité dans le domaine de la recherche opérationnelle si c'est bien un problème de sac à dos,
- un tel problème peut être résolu avec un solveur (coin ou cplex par exemple) mais si le problème est gros, le temps de calcul peut être très long,
- on peut le résoudre de manière approchée et sans solveur avec des méta heuristique dans un temps très raisonnable et avec une solution de bonne qualité.

Bonne chance
0