Inscription / Connexion Nouveau Sujet
Un coup de pouce?
Bonjour,
je suis tout à fais nul en math, et j'ai un besoin. Je pense que c'est un algorithme d'optimisation avec contraintes qu'il me faut. Etant ignare de ce langage, je cherche un coup de pouce pour me dire comment je dois procéder, dans quel ordre je dois faire les choses, ou au mieux, s'il existe un algorithme tout fait.
Je vous explique mon problème:
Je cherche une formule me permettant d'afficher plusieurs solutions selon plusieurs critères en fonction d'une variable principale (largeur de mur) et des variables implicites (nombre de cadres).
On me donne un mur d'une certaine largeur; je dois y installer une série de cadres photos en utilisant un stock de 4 modèles de cadres différents. (Par exemple 30cm de large, 40cm de large 50cm de large, 70cm de large etc.).
Je dois respecter un écart de 8cm entre chaque cadre et au minimum 6cm d'espace entre les 2 cadres d'extrémité et le bord du mur, je peux utiliser plusieurs fois le même modèle de cadre.
1-je voudrais calculer automatiquement la meilleur combinaison pour remplir au maximum la largeur du mur selon les critères cités au dessus.
2-je voudrais également trouver la meilleur combinaison pour remplir au maximum le mur, mais en utilisant le minimum de cadres, donc en priorisant les plus grands cadres, tout en recouvrant au maximum le mur, selon les critères cités au dessus.
3-je voudrais aussi calculer la meilleure combinaison ui remplisse au maximum le mur, toujours selon les critères cités au dessus, mais cette fois en ayant une symétrie parfaite dans le calepinage.
En fait, j'aimerais pouvoir calculer automatiquement ces 3 solutions, et voir aussi les autres solutions, classées de la plus approchante à la moins approchante.
Les variables sont donc la dimension du mur et le nombre de cadres utilisés (donc nombre d'écarts de 8cm)
Comment pensez-vous que je doive faire?
Chaque tentative d'ajouter un cadre dans la combinaison implique un nombre d'écarts de 8cm différents, donc l'algorithme doit donc calculer automatiquement la somme totale des cadres et écarts au fur et à mesure.
ça ne me semble pas impossible mais je ne sais pas comment organiser les différentes fonctions à mettre en œuvre.
Pensez-vous qu'il faille avant tout faire un tableau de données avec toutes les solutions possibles (fastidieux) pour que l'algorithme puise dans ces données pour faire le calcul?
Je vous remercie d'avance pour tout conseil, suggestion qui pourrait me faire avancer.
salut
si a, b, c, d, ... sont le nombre de cadres de largeur 30, 40, 50, 60, 70, .... ben ça va faire combien de longueur au total ...
puis entre les cadres il faut insérer un écart de 6 donc ça va faire combien au total ...
et si ton mur mesure x avec un écart de 8 pour les extrémités ...
ben ça semble relativement facile à modéliser en formule ...
ensuite si tu veux optimiser ben tu commence par les plus grands cadres avec le nombres maximal possible puis tu diminues de un en un et tu "bouches les trous" avec des cadres plus petits ...
ça se programme assez aisément ...
Bonjour,
Il me semble que c'est le problème du sac à dos (
), qui est NP-complet. L'article wikipedia montre des algorithmes.
Merci trapangle.
Effectivement j'avais parcouru cette notion de NP-complet, effectivement je peux trouver la solution de façon empirique.
Ce qui me chagrine, dans mon cas, c'est le fait que l'ajout d'un cadre dans la recherche de combinaison implique un nouvel espace "entre cadre" et donc la valeur restant à comblée évolue à chaque calcul.
Penses-tu que cet aspect n'est qu'un détail technique que l'algorithme "sac à dos" peut résoudre?
Pour gérer les distances entre cadres, tu peux ajouter 8 cm à la largeur de chaque cadre (38cm, 48cm, 58cm, 78cm, ...) et "retirer artificiellement" 2*6-8 = 4cm à la largeur du mur.
Si le mur réel fait 300cm, tu essaies de caser des cadres de 38, 48, 58, 78 dans un mur de largeur 296cm. Ainsi le choix des cadres tiendra compte de l'écart entre eux.
salut Carpediem , c'est 8 entre les cadres et 6 6cm d'espace entre les 2 cadres d'extrémité et le bord du mur
Mais tout à fait, très bonne suggestion.
Vu mon ignorance en la matière, tes réponses me font grandement avancer.
Alors merci beaucoup 
Oui Flight.
Heureusement c'est un détail technique.
Je cherche surtout la façon d'organiser les problématiques, de structurer la pensée.
Après le type de problème (ici à priori sac à dos), je dois m'atteler à la façon d'afficher les solutions dans l'ordre de pertinence...mais la c'est du domaine de la programmation je pense.
Merci
une esquisse de solution rapide .
soit x le nombre de cadres de type A (30cm)
soit y le nombre de cadres de type B (40cm )
soit z le nombres de cadres de type C (50cm)
je m'arrête à 3 types de cadres alors si L est la largeur du mur , on a :
L = 6 + 30x + 40y+ 50z + (x+y+z -1).8 + 6 = 38x+48y+58z +4 ( on peut encor agir sur la valeur minimum d'espace entre les 2 cadres d'extrémité et le bord du mur qui est de 6 puisqu'elle peut etre plus grande) mais je garde 6 pour l'exemple .
puis ensuite on demande à un compilateur de sortir toutes les solutions de
L = 38x+48y+58z +4
Exactement, c'est la fonction que j'avais réussi à déterminer (enfin je crois)
Un compilateur donc... voilà le genre de termes qui me manque pour trouver les bons outils.
Un grand merci
si tu travail uniquement avec des valeurs entieres je te propose
à la barbare :
L = cint(inputbox("saisir la valeur de L")
for x = 0 to L
for y = 0 to L
for z = 0 to L
if 38x+48y+58z +4 =L then
solutions = solutions & " " & x &" " & y &" " & z
end if
next
next
next
msgbox solutions ' a tester sur excel vba
Pour gérer les distances entre cadres, tu peux ajouter 8 cm à la largeur de chaque cadre (38cm, 48cm, 58cm, 78cm, ...) et "retirer artificiellement" 2*6-8 = 4cm à la largeur du mur.
Si le mur réel fait 300cm, tu essaies de caser des cadres de 38, 48, 58, 78 dans un mur de largeur 296cm. Ainsi le choix des cadres tiendra compte de l'écart entre eux.
car 2 * 8 = 16 et 2 *4 = 8
je voulais effectivement lui parler de ce "classique" pb d'optimisation ...
et pardon pour le mélange des écarts ...
et pour la traduction de flight et en tenant compte que tu veux optimiser les plus grands cadres il me semble qu'il est judicieux de compter en commençant par les plus grands et dans le sens décroissant pour ton algo ...
Cool
là j'avoue il me faut plus de temps pour apprécier la qualité de ta réponse 
Je vais voir ça
Merci
Carpédiem,
effectivement j'ai essayé de façon empirique de combiner en priorité les grand cadres, pour ensuite combler petit à petit le manque.
C'est donc une toute autre façon de faire, puisqu'on impose dès le début un début de combinaison.
Mais dans mon cas, il semble que ce soit justifié.
suis bete .... on peut refaire le code comme suit si tu connait le stock de cadres A , B et C
et que tu a en a "U" de type "A" , "V" de type B et "W" de type C alors on peut raisonnablement ecrire que
sub optimisation()
L = cint(inputbox("saisir la valeur de L")
U = cint(inputbox("saisir la valeur du stock de cadres de type A")
V = cint(inputbox("saisir la valeur du stock de cadres de type B")
W = cint(inputbox("saisir la valeur du stock de cadres de type C")
for x = 0 to U
for y = 0 to V
for z = 0 to W
if 38x+48y+58z +4 =L then
solutions = solutions & " " & x &" " & y &" " & z
end if
next
next
next
msgbox solutions ' a tester sur excel vba
end sub
à placer dans un module
ben tout simplement avec l'algo de flight je commencerai par une boucle en z, puis y puis x et dans le sens décroissant en commençant par le max de z possible ...
Carpediem, tu veux dire:
Citation :
sub optimisation()
L = cint(inputbox("saisir la valeur de L")
U = cint(inputbox("saisir la valeur du stock de cadres de type A")
V = cint(inputbox("saisir la valeur du stock de cadres de type B")
W = cint(inputbox("saisir la valeur du stock de cadres de type C")
for z = 0 to U
for y = 0 to V
for x = 0 to W
if 38x+48y+58z +4 =L then
solutions = solutions & " " & x &" " & y &" " & z
end if
next
next
next
msgbox solutions ' a tester sur excel vba
end sub
?
ah non ! je dirais plutot :
sub optimisation()
L = cint(inputbox("saisir la valeur de L")
U = cint(inputbox("saisir la valeur du stock de cadres de type A")
V = cint(inputbox("saisir la valeur du stock de cadres de type B")
W = cint(inputbox("saisir la valeur du stock de cadres de type C")
for z = 0 to W
for y = 0 to V
for x = 0 to U
if 38x+48y+58z +4 =L then
solutions = solutions & " " & x &" " & y &" " & z
end if
next
next
next
msgbox solutions ' a tester sur excel vba
end sub
non : for z = U to 0 (pour commencer par le nombre maximal)
de toute façon x, y et z sont positifs donc z < (L - 4)/58 --> valeur maximale de U
où x compte les plus grands cadres ...
nouvelle rectification suite au "plus" proposé par Carpediem
sub optimisation()
L = cint(inputbox("saisir la valeur de L")
U = cint(inputbox("saisir la valeur du stock de cadres de type A")
V = cint(inputbox("saisir la valeur du stock de cadres de type B")
W = cint(inputbox("saisir la valeur du stock de cadres de type C")
for z = W to 0 step -1
for y = V to 0 step -1
for x = U to 0 step -1
if 38x+48y+58z +4 =L then
solutions = solutions & " " & x &" " & y &" " & z
end if
next
next
next
msgbox solutions ' a tester sur excel vba
end sub
Il me faut un certain temps pour digérer tout cela, d'autant que je ne connais pas le langage.
Mais je vais y arriver grâce à vous...
Merci
connaissez-vous un logiciel pour tester tout ça?
Jai essayé sur LARP mais le langage diffère visiblement
sur excel clique doit sur l'onglet d'une feuille , puis selectionner visualiser le code , puis
tu colles ce qui suit dans la zone blanche
Sub optimisation()
resultat = ""
L = CInt(InputBox("saisir la valeur de L"))
u = CInt(InputBox("saisir la valeur du stock de cadres de type A"))
V = CInt(InputBox("saisir la valeur du stock de cadres de type B"))
W = CInt(InputBox("saisir la valeur du stock de cadres de type C"))
For Z = W To 0 Step -1
For y = V To 0 Step -1
For x = u To 0 Step -1
If 38 * x + 48 * y + 58 * Z + 4 = L Then
resultat = resultat & " " & x & " " & y & " " & Z
End If
Next
Next
Next
MsgBox resultat
End Sub
tu vas ensuite sur "Execution" dans le menu du haut de la page et voila
Annuler
connectez vous