Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Un coup de pouce?

Posté par
Fixette
16-10-19 à 15:38

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.

Posté par
carpediem
re : Un coup de pouce? 16-10-19 à 16:27

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 ...

Posté par
trapangle
re : Un coup de pouce? 16-10-19 à 16:33

Bonjour,

Il me semble que c'est le problème du sac à dos (), qui est NP-complet. L'article wikipedia montre des algorithmes.

Posté par
Fixette
re : Un coup de pouce? 16-10-19 à 16:52

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?

Posté par
trapangle
re : Un coup de pouce? 16-10-19 à 16:57

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.

Posté par
flight
re : Un coup de pouce? 16-10-19 à 17:01

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

Posté par
Fixette
re : Un coup de pouce? 16-10-19 à 17:02

Mais tout à fait, très bonne suggestion.

Vu mon ignorance en la matière, tes réponses me font grandement avancer.

Alors merci beaucoup

Posté par
trapangle
re : Un coup de pouce? 16-10-19 à 17:03

De rien

Posté par
Fixette
re : Un coup de pouce? 16-10-19 à 17:05

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

Posté par
flight
re : Un coup de pouce? 16-10-19 à 17:07

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

Posté par
Fixette
re : Un coup de pouce? 16-10-19 à 17:12

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

Posté par
flight
re : Un coup de pouce? 16-10-19 à 17:14

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

    
          
    

Posté par
carpediem
re : Un coup de pouce? 16-10-19 à 17:15

trapangle @ 16-10-2019 à 16:57

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.
ce ne serait pas plutôt 4

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 ...

Posté par
carpediem
re : Un coup de pouce? 16-10-19 à 17:16

ha non pardon pour l'idée de carpediem : un cadre possède deux côtés ...

Posté par
carpediem
re : Un coup de pouce? 16-10-19 à 17:17

pour l'idée de trapangle ...

Posté par
Fixette
re : Un coup de pouce? 16-10-19 à 17:17

Cool

là j'avoue il me faut plus de temps pour apprécier la qualité de ta réponse
Je vais voir ça

Merci

Posté par
Fixette
re : Un coup de pouce? 16-10-19 à 17:23

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é.

Posté par
flight
re : Un coup de pouce? 16-10-19 à 17:25

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  

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 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

Posté par
carpediem
re : Un coup de pouce? 16-10-19 à 17:27

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 ...

Posté par
Fixette
re : Un coup de pouce? 16-10-19 à 17:30

Mais c'est magnifique.

Voilà de très bonnes pistes.

Je vais tester tout ça, comme je peux

Merci

Posté par
Fixette
re : Un coup de pouce? 16-10-19 à 17:31

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

?

Posté par
flight
re : Un coup de pouce? 16-10-19 à 17:36

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

Posté par
carpediem
re : Un coup de pouce? 16-10-19 à 17:36

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 ...

Posté par
carpediem
re : Un coup de pouce? 16-10-19 à 17:36

z compte les plus grands cadres ...

Posté par
carpediem
re : Un coup de pouce? 16-10-19 à 17:38

de plus il faudra la variable n = x + y + z = nombre total de cadre que tu veux minimiser ...

Posté par
Fixette
re : Un coup de pouce? 16-10-19 à 17:38

de voir qu'on se bat pour moi ça me réchauffe le cœur

Posté par
flight
re : Un coup de pouce? 16-10-19 à 17:39

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

Posté par
Fixette
re : Un coup de pouce? 16-10-19 à 17:40

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

Posté par
Fixette
re : Un coup de pouce? 16-10-19 à 17:41

connaissez-vous un logiciel pour tester tout ça?
Jai essayé sur LARP mais le langage diffère visiblement

Posté par
flight
re : Un coup de pouce? 16-10-19 à 17:46

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

Citation :
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

Posté par
Fixette
re : Un coup de pouce? 16-10-19 à 17:52

Nickel, je vais tester ça.
Merci encore et bravo!

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !