Discussion :

[ELIStheWORLD]

Bonjour à tous,
Je suis nouvel auto-entrepreneur et j'aurai besoin d'aide pour un calcul qui me pose problème. Je tiens à préciser que je ne suis pas expert en Excel, et vous remercie déjà de vous interesser à mon sujet.
Je veux réaliser des combinaisons avec des lames de bois qui devront être emballées dans des paquets de longueurs fixes (1500mm, 1800mm, 2000mm et 2200mm).
- Nb moyen de produits differents = 20 : allant de 300mm à 2200mm (tous les 100mm)
- Nb de paquets de longueurs differentes = 4 : 1500mm, 1800mm, 2000mm et 2200mm
- Nd de rangées de produits/paquets = 6
Ex: Pour réaliser un paquet de 2200mm. Je peux combiner :
1e rangée=2200
2e=1800+400
3e=1700+500
4e=1600+600
5e=1500+700
6e=1900+300
Ce n'est qu'un exemple mais chaque paquet doit contenir au moins un produit de la longueur du paquet.
On pourra, et devra, combiner plusieurs produits par rangée. Tous les produits doivent être combinés dans un paquet!!
VOICI UN EXEMPLE DU VRAI CHALLENGE : PJ
SVP aider moi à trouver une méthode sur excel pour faciliter ce casse-tête.
MERCI pour votre aide

EL

[Flodelarab]

Bonjour,

Quelle est la difficulté?
Qu'as-tu fait jusqu'ici?

[nono_31]

Bonjour,

La difficulté est que ce problème ressemble à un bin packing
Est-ce que toutes les lames ont la même largeur ?
Est-ce qu'il s'agit simplement de trouver un rangement de toutes les lames dans des paquets ou de minimiser aussi le nombre de paquets.

Je ne connais pas beaucoup excel, mais je doute qu'il s'agisse de l'outil le plus adapté.

Cordialement.

[kolodz]

C'est globalement un variante du problème du sac à dos.

Excle n'est clairement pas l'outil le plus utile pour ce genre de calcul. Sachant qu'une grande partie des calculs sont itératif...

Si une personne rédige un algorithme pour résoudre ce genre de problème. Il réalisera probablement celui-ci en sous solution.

1. Générer les combinaisons de produits possible pour chaque longueur.
2. Pour une combinaison de produit définir le nombre de ligne réalisable.
3. Ce que cela consomme en produit disponible et ce qu'il reste.
4. Itérer sont les deux précédents points de manière à obtenir un optimum.

A noter qu'une fois arriver sur la partie itération, c'est une la problématique du sac à dos qu'on a (avec une problématique légèrement différent)

Sous sa forme décisionnelle, le problème est NP-complet, ce qui signifie que l'on ne connaît pas de méthode générale pour construire une solution optimale, à part l'examen systématique de toutes les solutions envisageables. Le problème d'optimisation est NP-difficile, sa résolution est au moins aussi difficile que celle du problème de décision, et il n'existe pas d'algorithme polynomial connu qui, étant donné une solution, peut dire si elle est optimale (ce qui reviendrait à dire qu'il n'existe pas de solution avec un k plus grand, donc à résoudre le problème de décision NP-complet).

Cordialement,
Patrick Kolodziejczyk.

Source :
http://fr.wikipedia.org/wiki/Probl%C...sac_%C3%A0_dos

[tbc92]

Bonsoir,
Déjà, une solution en Excel 'pur' ( c'est à dire sans VB), c'est impossible.
Au mieux, tu pourras faire des macros qui vont faire des itérations, et trouver une ou des solutions.
Mais sans macros, sans programmation, point de salut.

Deuxième point, il manque quelques points dans la description du besoin.
Par exemple, dans le fichier joint, si on fait la somme de toutes les lames, on arrive à une longueur totale de 2 276 900mm.
Et ce nombre n'est pas un multiple de 6x100.
Il n'y a donc aucune solution avec des paquets qui auraient tous EXACTEMENT 6 rangées de longueurs égales.
Quelle est la contrainte que je n'ai pas comprise ?

Et toujours dans la pièce jointe, tu as mis en colonne F un titre 'Nombre de paquets possibles'.
Du coup, nouvelle question, quel est ton besoin :
- Trouver au moins un assemblage pour mettre toutes les lames dans des paquets de 6 rangées, de longueur .... ?
- Ou bien trouver toutes les façons de solution le problème (à vue de nez, ça se compte en milliards)

[dourouc05]

Quid du solveur d'Excel pour éviter de programmer ? (Voir http://jpcheck.developpez.com/tutori...ur-sous-excel/ et http://tcuvelier.developpez.com/tuto...nception-jeux/, par exemple.) Maintenant, l'outil n'ira pas forcément assez vite pour te donner une réponse dans des temps satisfaisants, vu la complexité du problème .

[Deuzz]

Bonjour

Quid du solveur d'Excel pour éviter de programmer ?

J'ai tenté de me pencher sur le problème en essayant de solutionner avec le solveur d'excel, mais il y a à mon sens trop d'inconnues pour trop peu d'équations.

En effet, rien que pour les paquets de 1500 mm il y a 15 configurations possibles :

• 1200 + 300
• 1100 + 400
• 1000 + 500
• 900 + 600
• 900 + 300 + 300
• 800 + 700
• 800 + 400 + 300
• 700 + 500 + 300
• 700 + 400 + 400
• 600 + 500 + 400
• 600 + 300 + 300 + 300
• 500 + 500 + 500
• 500 + 400 + 300 + 300
• 400 + 400 + 400 + 300
• 300 + 300 + 300 + 300 + 300

Le nombre de chacune de ces combinaisons est une inconnue. Mais pour ce qui est des équations elles sont au nombre de 20 et toutes de la forme :

Nbre de lame de longeur X = Somme des combinaisons où la longueur X est présente (éventuellement pondéré par le nombre de fois où la lame d'une longueur X est présente dans la combinaison)

EDIT : J'oubliais 4 équations : celles qui précisent que la somme des différentes combinaisons de chaque longueur est un multiple de 6

A moins de réduire drastiquement le nombre d'inconnues en supprimant des combinaisons possibles de façon arbitraire (en risquant toutefois que le problème devienne insolvable) je ne vois pas comment Excel pourrait répondre à ce problème.

De plus, si la règle est : toutes les lames sont dans un paquet, il est impossible de placer celles de 2100 mm dans une quelconque combinaison.

[dourouc05]

J'ai tenté de me pencher sur le problème en essayant de solutionner avec le solveur d'excel, mais il y a à mon sens trop d'inconnues pour trop peu d'équations.

Malgré son nom, le solveur n'est pas là pour résoudre des systèmes d'équations (je n'ai jamais dit que le nom était parfaitement choisi ). Il s'agit plutôt d'un outil d'optimisation complet, qui peut notamment résoudre des problèmes formulés comme http://en.wikipedia.org/wiki/Bin_pac...rmal_statement (qui me semble être une brique de base du problème de ce sujet, même si je n'ai pas encore trop creusé la question).

[kolodz]

Juste pour montrer l'étandu de la compléxité du problème :

Disposition Possible pour le packaging 1500 : 17
longeur : 1500, composition {1200,300}
longeur : 1500, composition {1100,400}
longeur : 1500, composition {1000,500}
longeur : 1500, composition {900,300,300}
longeur : 1500, composition {900,600}
longeur : 1500, composition {800,400,300}
longeur : 1500, composition {800,700}
longeur : 1500, composition {700,500,300}
longeur : 1500, composition {700,400,400}
longeur : 1500, composition {600,600,300}
longeur : 1500, composition {600,500,400}
longeur : 1500, composition {600,300,300,300}
longeur : 1500, composition {500,500,500}
longeur : 1500, composition {500,400,300,300}
longeur : 1500, composition {400,400,400,300}
longeur : 1500, composition {300,300,300,300,300}
longeur : 1500, composition {1500}
Disposition Possible pour le packaging 1800 : 33
longeur : 1800, composition {1500,300}
...
longeur : 1800, composition {1800}
Disposition Possible pour le packaging 2000 : 49
longeur : 2000, composition {1700,300}
...
longeur : 2000, composition {2000}
Disposition Possible pour le packaging 2400 : 109
longeur : 2400, composition {2100,300}
...
longeur : 2400, composition {300,300,300,300,300,300,300,300}

Et cela seulement pour les longueurs exact.
Sachant qu'il n'est pas possible de faire rentré la longueur 2200 dans une longueur exacte.

Une fois que l'ensemble des ces dispositions possibles sont établies, il n'y a plus qu'à remplir des paquets en fonction... au mieux...
Sachant qu'on a aucune indication sur la préférence des packaging.

Cordialement,
Patrick Kolodziejczyk.

[tbc92]

L'exercice pourrait être intéressant pour les férus d'algorithme.

Mais la moindre des choses serait qu'ELIStheWORLD réapparaisse pour définir correctement son besoin, et répondre aux questions en suspens !

Ca paraît vraiment inimaginable qu'une personne soumette un besoin, puis disparaisse totalement, mais parfois, la réalité dépasse ce qu'on peut imaginer.

[250rgv]

En fait, son problème me semble être un exercice de cours qu'il a essayé de camoufler en problème de la vraie vie.

Je sais pas pourquoi, une impression : le texte qui commence par "Je suis nouvel auto-entrepreneur" avec un statut "étudiant", la formulation du problème ("On pourra, et devra, combiner..."), etc.

Et il a du arriver au terme de son délai de rédaction de l'exercice

[Flodelarab]

Pour une fois, je ne vais pas faire le rabat-joie. Je trouve le problème assez intéressant. Par contre, je ferais ça en C++. Pas avec Excel.

Première phase: trouver tous les lots unitaires possibles.
Deuxième phase: combiner les lots unitaires pour avoir la quantité maximale de lots

[kolodz]

Comme moi ! Sauf que je préfère le java !
Sachant qu'avec solveur relativement simpliste, j'arrive à une solution approchante :

Code javascript :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
Lames restantes :
[2200, 25]
[900, 1]
[800, 2]
Paquet incomplet :
Paquet { longeur : 2400, composition 
	{
	longeur : 2400, composition {800,800,800},
	longeur : 2400, composition {800,800,800},
	longeur : 2400, composition {800,800,800}
	}
}
Paquet { longeur : 2000, composition 
	{} //Paquet vide - pas de ligne de lame dedans
}
Paquet { longeur : 1800, composition 
	{
	longeur : 1800, composition {900,900}
	}
}

Sachant que les autres paquets sont des paquets de 6 lignes dont les lignes font la taille du paquet.
Algorithme de calcul cherche à faire tout les paquets de grandes tailles en premiers quand il ne peux plus faire la longueur exacte pour la taille de paquet en question, il passe à la taille suivante.

Cordialement,
Patrick Kolodziejczyk.

[tbc92]

@250rgv : 100% d'accord. Je vois mal un auto-entrepreneur confronté à ce type de problème d'optimisation.

@kolodz : Oui, l'exercice est intéressant, mais il manque quelques précisions dans l'intitulé de l'exercice.
Tentons de pallier à ces lacunes :

1. A partir de lame de longueur 300 à 2200 mm
2. Constituer des paquets de longueur 2200 2000 1800 ou 1500 mm
3. Dans un paquet de longueur L , il doit y avoir au moins une lame de longueur L.
4. Un paquet est constitué de 6 rangées au maximum
5. Comme déjà vu, la première rangée est constituée d'une et une seule lame de longueur L. Les rangées suivantes sont constituées de 1 ou plusieurs lames. Et la somme des longueurs doit être au maximum L
6. L'objectif est e regrouper toutes les lames du stock en paquets de longueur imposées ( 2200 2000 1800 ou 1500)
7. Il faut faire en sorte d'avoir le moins de paquets possibles.


Les points 1 à 6 sont en gros la copie de l'exercice de départ ; le point 7 est le critère qui permettra de choisir entre toutes les solutions possibles au problème.

Vous avez 4 heures

[ELIStheWORLD]

Re-bonjour,
Désolé pour la "disparition". Je suis reparti sur une résolution manuelle du problème. La création d'un algorithme étant quasi-impossible à mon niveau. Pour explication, je travaille avec un fabricant de parquet, et mon activité nécessite également de prévoir des combinaisons de colis contenant des lames de parquets de longueurs différentes, facilitant ainsi la pose de celles-ci sur le chantier. Pour la formulation, j'essaye simplement de créer un cahier de charges le plus lisible possible.

Toutefois, des personnes expérimentées en Excel m'ont averti de la complexité du problème.

Pour répondre aux questions posées:
- nono_31 : Est-ce que toutes les lames ont la même largeur ?
Les lames sont de même largeur et de même épaisseur, seule la longueur diffère (il s'agit de travailler avec seul produit, puis adapter la méthode à chaque produit à combiner);

- tbc 92: a bien compris l'ampleur du problème (sorti du contexte de l'étudiant passant un exam bien sûr )
1. A partir de lame de longueur 300 à 2200 mm
2. Constituer des paquets de longueur 2200 2000 1800 ou 1500 mm
3. Dans un paquet de longueur L , il doit y avoir au moins une lame de longueur L.
4. Un paquet est constitué de 6 rangées au maximum
5. Comme déjà vu, la première rangée est constituée d'une et une seule lame de longueur L. Les rangées suivantes sont constituées de 1 ou plusieurs lames. Et la somme des longueurs doit être au maximum L
6. L'objectif est e regrouper toutes les lames du stock en paquets de longueur imposées ( 2200 2000 1800 ou 1500)
7. Il faut faire en sorte d'avoir le moins de paquets possibles.

Les points 1 à 6 sont en gros la copie de l'exercice de départ ; le point 7 est le critère qui permettra de choisir entre toutes les solutions possibles au problème.

Il existe toujours des lames restantes, ne pouvant pas rentrer dans les paquets de 2200, 2000, 1800, et 1500. (je réalise également des colisages de 1200 mais je voulais pas surcharger le problème). Ces lames restantes seront insérer dans un colis "spécial" de longueur permettant d'insérer au maximum de lames, et il peut y avoir plusieurs longueurs de colis "spécial" en fonction des lames restantes.

- Flodelarab:
Première phase: trouver tous les lots unitaires possibles :
Deuxième phase: combiner les lots unitaires pour avoir la quantité maximale de lots


Je sais que c'est complexe, c'est bien pour cela me prends des heures à chaque fois!

EXEMPLE CONCRET terminé manuellement, je vous présente les étapes pour réaliser mes combinaisons :

ETAPE 1 :

Je recois une packing list (1er tab) du produit avec les longueurs triées, leur quantités par longueur et la surface (en m2) qu'elles représentent.
Le produit : 14 mm x 130 mm = je peux me permettre un colisage de 8 rangées (j'ai défini un colisage qui évolue en fonction de l'épaisseur des lames pour éviter le surpoids des paquets/colis) ;

A partir du 1er Tab, je vois vite que je peux essayer de créer 3 longueurs de paquets : 2200 mm, 2000 mm et 1800 mm.

Pour cela, j'ai défini les combinaisons possibles et j'utilise donc:

- Pour le paquet de 2200mm, les 26 lames que j'ai, les 7 autres rangées pourront être des combinaisons suivantes (je n'utilise pas les 2000 ni les 1800 qui me serviront plus tard) : 1500+700/1400+800/1300+500+400/1200+500+500/1200+1000 ;
SACHANT QUE JE VEUX ME DEBARASSER DES GRANDES LONGUEURS AU PLUS VITE.

- Pour le paquet de 2000mm, les 27 lames que j'ai, les 7 autres rangées pourront être des combinaisons suivantes (sans utiliser les 1800 et après avoir déduit les lames emballées dans les paquets de 2200mm) : 1400+600/1300+700/500+500+500+500/700+700+600/1200+800/800+800+400 ;

- Pour le paquet de 1800mm, les 50 lames que j'ai, les 7 autres rangées pourront être des combinaisons suivantes: 1000+400+400/900+500+400/700+600+500/500*2+400*2, voire même 1 lame de 1800mm si j'ai besoin de combler;

Je défini également la surface (en m2) de chacun de mes paquets : L x l x NB par paquet
- 2200 = 2.2 x 0.13 x 8 = 2.288 m2 (total à emballer en paquet de 2200mm = 59.488m2)
- 2000 = 2 x 0.13 x 8 = 2.08 m2 (total à emballer en paquet de 2000mm = 56.16m2)
- 1800 = 1.8 x 0.13 x 8 = 1.872 m2 (total à emballer en paquet de 1800mm = 93.6 m2)

Mes clients peuvent également exiger une longueur et surface précise par paquets.


Je m’arrête à ces 3 colisage car je connais ma surface totale à emballer = 197.82m2, et la surface totale que je peux emballer avec mes 3 colisages = 209.248 m2 (soit 59.488 + 56.16 + 93.6 = 209.248 m2)
Je sais donc que je peux emballer plus avec ces 3 choix de longueur de paquet que ce dont j'ai besoin.
J'espère que je n’ai perdu personne, désolé si je ne suis pas clair!!


ETAPE 2:

J'ai les 3 colisages et les possibles combinaisons par colisage. Je créé maintenant 3 paires de tableaux (en dessous) et les remplir de sorte de me débarrasser des grandes longueurs en premier, et de ne mettre dans un paquet de longueur L , qu'une lame de longueur L.

Le tableau du haut reprend toutes les longueurs que j'utilise pour faire mes combinaisons dans le tableau du bas. J'enlève alors les longueurs au fur et à mesures que je réalise mes combinaisons, et inscrit dans une colonne la quantité restante par longueur, autrement dit restant disponible pour le prochain colisage (2000mm, puis 1800mm)

Quand j'ai terminé le premier colisage (en occurence 2200mm), j'attaque le suivant (2000mm), puis le dernier (1800mm).

S'il y a des restes encore à la fin, et que je ne peux pas créer un autre colisage au vu de la faible quantité, ces derniers sont simplement mis de côtés.



UN GRAND MERCI DEJA A TOUS CEUX QUI ONT PRIS LE TEMPS DE ME REPONDRE ET DE REFLECHIR A MON PROBEME, ET MERCI D'AVANCE A TOUS CEUX QUI POURRONT M'AIDER A TROUVER UNE SOLUTION "AUTOMATISEE" A CE CALCUL QUI ME PREND ENORMEMENT DE TEMPS.

[yahiko]

Ca ressemble fortement à un problème d'optimisation linéaire.

[nono_31]

Ca ressemble fortement à un problème d'optimisation linéaire.

Tout à fait d'accord. Au risque de me répéter, cela ressemble un peu au problème de bin packing ou de cutting stock.
Au vu de la taille du problème, je dirais que n'importe quel solveur linéaire correct peut faire le job une fois le problème correctement modélisé.

[anapurna]

salut


on as deja repondu a ce genre de problematique

voir ici

[ELIStheWORLD]

Tout à fait d'accord. Au risque de me répéter, cela ressemble un peu au problème de bin packing ou de cutting stock.
Au vu de la taille du problème, je dirais que n'importe quel solveur linéaire correct peut faire le job une fois le problème correctement modélisé.

Salut,
Sans doute, le souci c'est que je travaille avec Excel, c'est à dire à partir d'un tableau excel où je rempli les longueurs du produit fabriqué à emballer.
J'aimerais pourvoir utiliser ce tableau comme base pour la recherche d'optimisation, et rendre mon algo évolutif (c.a.d. que je dois être capable de l'adapter à chaque produit que je recois (les quantités par longueur changent constamment selon le produit). Et évidemment, je ne sais pas créer un algo!!! ; mais je veux prendre le temps d'apprendre!

Ce que j'aimerais formuler dans un algo :


1. A partir de lame de longueur 300 à 2200 mm (en utilisant mon tableau avec Packing list comme base (variables))
2. Definir manuellement la longueurs des paquets à constituer : 2200, 2000, 1800 (et 1500, 1200 mm peut être) ;
3. Définir les combinaisons possible par paquet selon leur longueur (en utilisant un tableau des combinaisons possibles comme sous-base) ;

Contraintes :
4. Dans un paquet de longueur L , il doit y avoir au moins une lame de longueur L.
5. Un paquet est constitué de 4, 6, 8 ou 10 rangées selon le produit (choisir une solution uniquement par produit)
6. Comme déjà vu, la première rangée est constituée d'une et une seule lame de longueur L. Les rangées suivantes sont constituées de 1 ou plusieurs lames. Et la somme des longueurs doit être au maximum L;
7. Lorsque pour contituer une combinaison dans un paquet, il n'est pas possible d'utiliser une longueur, choisir une longueur inférieure et répéter l'opération jusqu'à ce qu'une combinaison soit possible;
8. Toutes les lames du stock seront mises en paquets de longueur imposées ( 2200 2000 1800: déterminé en point 2), si quelques restes = pas important ;
8. Optimiser le calcul pour avoir le moins de paquets possibles.


Voilà, j'oublie sans doute des choses, mais je pense que l'essentiel est là. Et j'aimerais voir à quoi pourrait ressembler un algo et surtout si c'est possible!
Merci de votre aide

[yahiko]

Vous pouvez soit étudier la programmation linéaire pour modéliser et implémenter votre problématique professionnelle. Plusieurs membres ont ici donné des pistes.
Soit demander à une société de conseil de le faire.