[probleme de math] problème de RO

Alors voila j suis étudiant et pô forcément tres tres bon en math .. sur le forum "taverne" on m a dit de venir ici donc je viens.. voila mon prob :

-> c 'est un probleme d'évaluation/séparation (Recherche opérationnelle) => je cherche la formule mathématique permettant d'évaluer ce problème :
comment miniser la place totale perdue lorsque l on veut :
-> ranger n fichiers (de tailles différentes contenues dans un tableau T[i]) dans m cd (de taille différents contenus dans un table C[j])...


Une séparation (peut etre mauvaise) consisterai à ranger les fichiers et les cd en ordre croissant puis mettre le plus gros fichier sur le plus gros cd .. puis faire ansi de suite avec tous les fichiers... (si un fichier ne tient pô sur un Cd on passe au Cd suivant et on essaye d'y mettre le fichier...)
Mais l'évaluation = ???? (faut qu'elle soit optimiste , qu'on puisse faire des ébranchage apres (pour la guerre de front..))

Voila je sais que c'est un prob de math mais plz aidez moi j sui perdu !! et j suis nul en math !! (c'est peu etre pour ca que je suis perdu d ailleur :oops: )

Voila en attendant une reponse merci d avance... et bonne chance car moi j'ai pas mal galéré la dessus sans avoir trouvé une bonne soluce (ne bonne évaluation)

Je crois (si j'ai bien compris) que ton probleme est un probleme logistique de Bin Packing. Y a plusieurs algo dejas existants pour ce prob. Moi j suis un peu rouillé la dessus et on a pas forcement tres developper le sujet lors de mes cours alors je pourrai pas t'expliquer exactement les diff algo.
Mais si je me rappel bien, la solution que tu donne est le premier type d'algo que l'on ait vu. Fait une recherche sur le Bin Packing ' devrai y avoir pas mal de truc...
Bonne chance !

j'ai fait un utilitaire qui minimise la place perdue sur un seul CD.
Cet utilitaire a une liste de fichiers de taille connue et une taille à ne pas dépasser.
Le principe est le suivant :
sur les n fichiers, j'en sélectionne de 1 à n (avec toutes les combinaisons possibles) et je calcule la taille de la sélection.

Je te cache pas que j'ai fait quelques améliorations pour optimiser les temps de réponse, mais c le principe.

Sinon tu peux faire ton heuristique glouton (mettre le plus grands en premier etc...) puis tu fais une petite methode tabou de derriere les fagots (j suis tres methode tabou moi) ! Seul probleme est de definir l'ensemble de voisinage, mais ca devrait pas etre trop complique !

Effectivement c bien un prob de Bin packing .. mias je ne trouve pas forcément de doc tres tres interessantes dessus car souvent le bin packing est fait pour des conteneurs de tailles similaires (ce qui n 'est pas un prob en fait...). Voila en fait ma soluce math mais a vérifier :


Variable de decision :
Oij = {0,1} : le fichier i est il sur le media j ? 0 = non et 1 = oui
Uj = {0,1} : le media (cd) j est il utilisé ?

Les contraintes :
=> Somme(sur j) Oij = 1 pour tt i : 1 <= i <= NbFichiers
=> Somme(sur i) Taille(i) * Oij <= Taille du Media j avec j : 1<= j<= Nombre media
et peut etre une ou deux autre on verra...

La fonction Eco (objective ) : minimiser la place perdue ...

Min ( Somme (j:1->NbCds)[ Uj *(taille media(j)-Somme(i:1->fichiers)[ Oijh * taille du fichier(i)])])

Voila mais maintenant je recherche a faire une Guerre Eclair et une Guerre de front (po obligé la guerre de front)) Mais problème je ne c po quoi mettre comme évaluation pour les différents noeuds de l'arbre que je vais construire....
c'est pas gagné tout ca je vous le dit moi :(

Mais déja merci pour l'info sur bin packing .. c cool...
et sinon Pour l autre soluce j'ai po tres bien compris un truc en fait :
Tu dis que tu fais un calcul de toutes les possibilités existantes pour ranger tes fichiers dans t cd ??? mais ca va te prendre un temps de fou si ton Cd fait (hypotétiquement) 1000 giga et que tu as 10000 fichiers de 1000 giga a traiter .. tu vois le prob si tu as de grandes valeurs (=> grand nombre de fichiers) alors ton algo va mettre 1000 ans a se resoudre.. mais peut etre que j'ai po tres tres bien compris ce que tu m as dit ..
Bon ben j attends une joli reponse m expliquant pourquoi je suis trop bete et pourquoi mon probleme est en fait "trivial"
Merci

Pour résoudre le problème, tu peux aussi utiliser un algorithme génétique...

peux-tu developper ton id ca m interesse la ....
tu entends quoi par algo genetique sur ce genre de probleme ??

Les algorithmes génétiques très appropriés pour les problèmes de recherches opérationnelles. Notamment pour le problèmes NP Complet.

Les algorithmes génétiques ne te garantissent pas de trouver la solution optimale mais une solution très proche de cet optimum. Il n'y a pas de 'formules mathématiques'. Il s'agit d'une suite qui converge vers la solution optimale (il me semble que la convergence vers la solution optimal se démontre).

Pour plus de renseigenement fais une recherche sous algorithme génétiques et Goldberg (il me semble).

Notion de base

* Individu : c'est une solution de ton problème (pas forcément la meilleure)
* Population : un groupe d'individu
* Taille de la population : nombre d'individu de ta population
* Croisement : un 'accouplement' entre deux individus. Ce croissement donne généralement deux nouveau individu
* Mutation : modification d'un individu
* Sélection : diminution d'une population. Cette diminution supprime généralement les individus les moins forts.
* Emprunte génétique (je ne me souviens plus du terme approprié): Codage de l'individu
* Force (je ne me souviens plus du terme approprié): détermine la force d'un inidividu. Plus individu est fort plus il est proche de l'optimum.
* Génération : niveau de sélection

Pour ton problème de rangement de fichier :

* l'emprunte génétique est :
C[1] | C[2] | ... | C[M]
----------------------------
T[i11] | T[i21]
T[i12] | ...
...

* La force est naturellement place (1/ place total perdue)

* Un croissement est par exemple (mais tu peux imaginer d'autres croissement)
Tu considéres 3 génes T[1], T[2], T[3] (par exemple) est tu crées deux nouveaux individus. L'un est l'individu fils qui hérite de sont père pour tout les gènes sauf T[1], T[2] et T[3] dont les positions sont ceux de la mère et l'autre individu est la fille (c'est l'inverse).

Attention vérifie que les deux nouveaux individus sont viables (il ne faut pas que l'un des cds contiennent trop de fichier)

* une mutation est par exemple l'inversion de deux colonnes d'une même individu ou l'inversion de deux fichiers (contenus sur des cds différents)

Principe:

1 Initialisation d'une population
2 Phase de croissement
3 Phase de mutation
4 Introduction de nouveaux individus (optionnel)
5 Sélection des meilleurs individus
on reboucle sur la phase 2 en prenant la population obtenue en phase 5 jusqu'a qu'on atteigne la génération N.

Taille et fréquence
L'initialisation de la population peut se faire aléatoirement ou alors on peut utiliser des heuristiques pour s'assurer que la population initiale soit forte.

Le taux de mutation par individu est par génération est relativement faible. (je crois de l'ordre de 2%). Tu peux jouer sur se taux pour voir la vitesse à laquelle converge la solution.

On peut définir le nombre de croissement en fonction du nombre de nouveaux individus que l'on veut obtenir.

Ta population initiale peut être fixé à 10 et le nombre de génération à 100.

La sélection peut supprimer autant individu qu'il faut pour maintenir la taille population constante. Ou en peut faire du multi-thead pour fair évoluer différente population avec inter-échange entre les différentes populations.

Tu peux exprimer la force pour obtenir le plus petit nombre de cd utilisé, pour minimser la place perdu. Pour minimiser le maximum perdu pour un cd, etc...

Salut,
Quand tu dis que c'est un pbe d'évaluation/séparation, c'est une contrainte que t'as fixé ton prof?
Parce que si c'est ça il veut vous faire résoudre le pbe de manière exacte avec une méthode type Branch&Bound...

Oui, pour ma methode où je calcule tout, c un probleme qd on a bcp de fichiers. :(
Moi j'ai contourné le probleme en :
- s'arretant à une solution proche
- par exemple, si j'ai un cd de 700 Mo et que la somme de mes fichiers fait 800 Mo, je cherche à faire 100 Mo...
- plein de petites choses comme ca quoi... :)

Je trouve la methode du Bin-Packing vraiment inaproprié dans mon cas mais bon...

Bonjour,

Je me permet de faire les deux remarques suivantes :

Soient Ti la taille fu fichier i ; i = 1 ... n
Soient Ck la taille du support k ; k= 1 ...m

1°. Considérons le plus fichier de plus grande taille et le support de plus grande taille. Autrement dit, tmax=max{Ti ; i=1...n} et Cmax=max{Ck ; k=1...m}. Le problème n'aura de solution que si tmax est plus petit ou égal à Cmax. Si on cherche à résoudre le problème par un programme linéaire il faut donc que l'on fasse l'hypothèse que cette condition est bien remplise. (Ne pas chercher à mettre cete condition dans l'ensemble des contraintes).

2°. Il ne faut pas perdre de vue une contrainte cumulative : La taille totale des fichiers doit être inférieure ou égale au total de la taille des supports. Autrement dit, on a:
sum(i=1 à n) Ci <= sum(k=1 à m) Tk

En ce qui concerne des autres contraintes je te laisse le soin de les trouver (il me semble que tu les as presques toutes). Enfin, ne pas perdre de vue également que la résolution d'un programme linéaire au moyen de variable binaire n'implique pas obligatoirement une méthode bound and branch.

Bien à toi Pignouf.

Vous vous cassez tous la tête : la solution proposée de l'algorithme glouton est simple et donne une solution optimale.
Tu classes les fichiers par taille (du plus gros au plus petit). Ensuite tu n'as qu'à mettre le plus gros qui rentre dans ton cd.

Par exemple avec des cd de 700 mo et des fichiers de 500, 400, 350, 250, 200, 100, 50, 20, 10 et 10.
Tu prends 500 + 200, il te reste les fichiers de 400, 350, 250, 100, 50, 20, 10 et 10.
Tu prends 400 + 250 + 50, il te reste les fichiers de 350, 100, 50, 20, 10 et 10.
Tu prends 350 + 100 + 50 + 20 + 10 + 10 et t'as fini : tous les fichiers sont pris.
Bon si t'as des fichiers qui dépassent la capacité ils ne rentreront jamais naturellement et si ton algo ne prend pas en compte ce cas il risque de boucler indéfiniment mais c'est tout.

Salut Tom,

Dans l'exemple que tu donnes tu fais 2 hypothèses à savoir
1°. les fichiers sont tous de tailles inférieures à celle du plus grand support. Ce qui est une bonne chose. Evidement comme tu le mentionnes très justement il faut faire un test dans l'algo. (cette hypothèse ne me pose pas de problème).
2°. tu fais une hypothèse implicite et assez forte. Tu supposes que tu as un nombre de support telle que la taille totale de l'ensemble de ces supports puissent contenir tout les fichiers. Supposons que dans ton exemple tu n'as pas au moins 3 CD de 700 mais 2. Dans ce cas que ce passe-t-il ? Il faut donc vérifier également dès le début si tu as à ta disponibilité suffisament de place sur l'ensemble des supports.

Bien à toi, Pignouf.

C'est pas bien compliqué ça :
- tu peux calculer la place dont tu disposes (taille d'un cd x nombre de cds)
- tu peux calculer la taille de ce que tu veux mettre (somme de toutes les tailles de fichiers)

Mais ce que je te suggère c'est de faire tourner l'algo tant que tu as de la place de libre (des cd en gros). Vu que tu as certainement un nombre limité de cd tu fais une boucle pour.
C'est pas un problème en soi ça.

Pb. l'algo de tom ne fonctione pas :twisted: : GRRRRRRR !!!!!

Mais un tout p'tit peu à cause de moi :oops:

En effet, si on a comme taille de fichiers : 9 et 2
Comme taille de supports : 10 et 1

On peut toujours placer l'un des fichiers mais pas le second et ce malgré le fait que la taille du plus grand fichier est plus petit que la taille du plus grand support et d'autre part on a bien que 9+2=11 qui est égal à la taille totale des fichiers qui est bien inférieur ou égal à la taille total des supports (10+1=11)

Tu portes bien ton pseudo toi (humour je dis pas ça méchament)
J'ai bien dit que mon algo c'est pour des supports qui ont tous la même taille.

Mais il y a quand même moyen de s'en sortir peut être en refaisant une approche gloutonne sur les tailles de cds.