Aide Algorithme Optimisation

Question

Bonjour,

J'aurais besoin d'une petite contribution pour un algo pas très compliqué qui concerne des barres de bois. Je dois en effet optimiser la coupe de barres en morceaux de longueur 
variable, en ayant des barres standard de longueur variables également:

Exemple : J'ai des barres de 6m et 12m, 
  Il me faut 	- 10 morceaux de 75cm
- 5 morceaux de 150 cm
- 10 morceaux de 125 cm
- etc

Si l'un d'entre vous aurait un algorithme à me suggérer, ne serait-ce qu'une idée, je lui en serait très reconnaissant...
Merci d'avance.

cs_CanisLupus · Answer

Salut,

Quand je pense qu'il suffirait que tu augmentes ta production de 2 morceaux de 125cm et tu n'aurais aucune chute avec 3 barres de 6m + 1 de 12m ou 1 barre de 6m + 2 de 12m (si tu ne tiens pas compte des cm bouffés par la scie).

4*150 ds 1 barre de 6m = pas de chute
3*75 + 3*125 ds 1 barre de 6m = pas de chute
(ou 4*150 + 3*75 + 3*125 ds une 12m = pas de chute)
Faut ptete tenir compte du stock ?
6*75 + 6*125 ds la 12m = pas de chute
et le reste
1*75 + 1*125+ 1*150 ds une 6m= chute de 250cm
ou ds une 12m = chute de 850cm (encore le stock !)

Et tout ça sans prog, juste de tête.

Bon, sérieux, c un cas d'école ou un truc qui va servir en vrai ?
Tu veux savoir quoi ? La coupe qui produira le moins de chutes inutilisables ? Et d'ailleurs, les chutes doivent-elles etre réutilisées ? Le nombre de "barres" différentes est-il fini ? (2 longueurs ou il peut y en avoir plus ?), etc ....................
Et je suppose que ton exemple n'est qu'un exemple donc, les valeurs peuvent être différentes ;-) ?

Un "algo pas très compliqué" comme tu dis mais si on en savait un peu plus .............

Remarque, g rien à faire ce week, pourquoi pas ton casse tete ?

Cordialement

CanisLupus

cs_Bretelle · Answer

Déjà, merci d'avoir répondu si vite à mon appel !
En effet, ce n'est qu'un exemple (très simple) qui avait pour but d'expliquer la chose... Il est évident que pour cet exemple je n'aurais pas eu besoin d'un programme, ma tête aurait supporté !

Seulement voilà, j'ai des untités de barres en stock et une liste de "morceaux" à découper...Certaines chutes (suffisamment longue) peuvent en effet être réutilisées. Mais le problème n'et pas là. Ce que j'aimerais, c'est une idée de départ pour élaborer un algorithme permettant d'optimiser la coupe des mrceaux en fonction des barres dispo.

J'avais déjà une idée de départ, si ça peut aider :
- Calculer pour chaque type de barre, la meilleure façon de couper les morceaux (pour qu'il y ait le moins de chute possible) puis ne garder que les meilleures solutions.
- Faire cette opération récursivement jusqu'à ce que la liste des morceaux soit épuisée !

Voilà ! J'attends vos critiques et vos idées... Merci d'avance !

cs_CanisLupus · Answer

Ben dis, finalement c pas simple ton truc.
Comme je suis adepte du "Pourquoi réinventer la roue ?", g fait une tite recherche avec les mots "algorithme optimisation coupe" sur google.
Résultat : g vu des logiciels qui faisaient déjà ça (donc c possible), g vu des expliks scientifiques (de l'algo pur et dur) mais aucun ex en vb ni en un autre langage d'ailleurs.
Si ça peut t'intéresser, g même vu une question similaire à la tienne à l'adresse : 
http://www.phpcs.com/forum.v2.aspx?ID=257014&nb=0
mais c peut-être toi ?

Rien que pour ma culture perso, je vais creuser mais le résultat n'est pas garanti en 1 WE. Pourtant, g déjà pratiqué l'analyse récursive (pour un jeu d'échec).

Si tu trouves une solution avant moi, je te remercie de m'en parler.

Cordialement

CanisLupus

cs_CanisLupus · Answer

Ptete un tite piste ?
Pour tester : une form avec une listbox(list1)

Private Sub Form_Load()
Dim b(0 To 1) As Integer ' taille des barres
Dim m(0 To 2, 0 To 1) As Integer ' taille et nb des morceaux
Dim r As Integer
Dim i As Integer
Dim j As Integer
Dim t As Boolean
Dim tot As Integer
Dim l As String

' Initialisation des tableaux
b(0) = 600
b(1) = 1200

m(0, 0) = 75
m(0, 1) = 10
m(1, 0) = 150
m(1, 1) = 5
m(2, 0) = 125
m(2, 1) = 10

' Boucle de calcul
Do
  t = False
  r = b(0)
  l = ""
  tot = 0
  For j = LBound(m, 1) To UBound(m, 1)
    If m(j, 1) > 0 Then ' si le nb de morceaux est > 0
      t = True ' Pour continuer la boucle s'il reste des morceaux à couper
      For i = m(j, 1) To 1 Step -1
        If m(j, 0) * i <= r Then
          m(j, 1) = m(j, 1) - i
          ' Construction de la ligne pour affichage
          If l = "" Then
            l = m(j, 0) & " x " & i
          Else
            l = l & " + " & m(j, 0) & " x " & i
          End If
          ' Totalisation de la longueur des morceaux
          tot = tot + m(j, 0) * i
          ' Calcul du reste de longueur de la barre
          r = r - m(j, 0) * i
          Exit For
        End If
      Next
    End If
  Next
  ' Affichage des résultats  If t Then List1.AddItem l & " " & tot & " - Chute " & b(0) - tot
Loop While t

End Sub

Cordialement

CanisLupus

cs_Bretelle · Answer

Merci de ton aide, je vais tester ça au courant de la semaine...
Pour le message similaire que tu as vu, ce n'est pas le mien ! Mais il est vrai que c'est le même principe apparemment...

@+

cs_CanisLupus · Answer

Re salut, G eu un tit moment et g remanié le 1er code. Celui là t'affiche toutes les combis possibles avec autant de type de morceaux que tu veux mais seulement pour une seule longueur de barre. Reste à combiner ces résultats pour avoir le meilleur découpage. Ca peut etre un début. Pour tester, une form avec une listbox. Private Sub Form_Load() Dim i As Integer Dim j As Integer Dim k As Integer ' Initialisation des tableaux Barres(0) = 600 Barres(1) = 1200 Morceaux(0, 0) = 75 Morceaux(0, 1) = 10 Morceaux(1, 0) = 150 Morceaux(1, 1) = 5 Morceaux(2, 0) = 125 Morceaux(2, 1) = 10 ' Mémorisation de la longueur maxi des barres lg_barre_maxi = 0 For i = LBound(Barres()) To UBound(Barres()) If Barres(i) > lg_barre_maxi Then lg_barre_maxi = Barres(i) Next ' Mémorisation de la longueur mini des morceaux lg_morceau_mini = Morceaux(0, 0) For i = LBound(Morceaux()) To UBound(Morceaux()) If Morceaux(i, 0) < lg_morceau_mini Then lg_morceau_mini = Morceaux(i, 0) Next ' Dimensionnement du tableau des valeurs possibles par type morceaux ReDim Preserve Lst_Val_Possibles(UBound(Morceaux())) ' Mémorisation de toutes les valeurs possibles par type de morceaux For i = LBound(Morceaux()) To UBound(Morceaux()) Lst_Val_Possibles(i).lg = Morceaux(i, 0) k = 0 For j = 1 To Morceaux(i, 1) If Morceaux(i, 0) * j <= lg_barre_maxi Then k = k + 1 ReDim Preserve Lst_Val_Possibles(i).nb(k) ReDim Preserve Lst_Val_Possibles(i).r(k) Lst_Val_Possibles(i).nb(j) = j Lst_Val_Possibles(i).r(j) = Morceaux(i, 0) * j End If Next Next ' Calcul des combinaisons possibles entre valeurs possibles Calcul "", 0, LBound(Lst_Val_Possibles()), UBound(Lst_Val_Possibles()), 0, Barres(0) End Sub Function Calcul(s As String, tot As Long, d As Integer, f As Integer, old_lg As Integer, lg_barre As Integer) Dim i As Integer, j As Integer Dim s_calc As String Dim v_tot As Long For i = d To f If Lst_Val_Possibles(i).lg = old_lg Then Exit For For j = UBound(Lst_Val_Possibles(i).r()) To 1 Step -1 s_calc = Lst_Val_Possibles(i).lg & " * " & Lst_Val_Possibles(i).nb(j) v_tot = tot + Lst_Val_Possibles(i).r(j) Select Case lg_barre - v_tot Case Is < 0 Case Is = 0 If s = "" Then List1.AddItem s_calc & " = " & v_tot Else List1.AddItem s & " + " & s_calc & " = " & v_tot End If Case Is < lg_morceau_mini If s = "" Then List1.AddItem s_calc & " = " & v_tot Else List1.AddItem s & " + " & s_calc & " = " & v_tot End If Case Is >= lg_morceau_mini If s = "" Then Calcul s_calc, v_tot, d + 1, f, Lst_Val_Possibles(i).lg, lg_barre Else Calcul s & " + " & s_calc, v_tot, d + 1, f, Lst_Val_Possibles(i).lg, lg_barre End If End Select Next Next End Function Bonne prog Cordialement CanisLupus

cs_Bretelle · Answer

Salut,

   G enfin pu tester ton code (excuse du retard) et il me donne en effet une liste de combinaisons... Cela dit, j'ai pas trop conmpris cette liste, parfois elle me donne 16 morceaux (par exemple) alors qu'il ne m'en faut que 10.
De mon côté j'ai mis en place plusieurs algorithmes selon les paramètres que l'on cherche à optimiser (gain de matière, récupération des chutes, ...)

J'aimerais à terme me servir de ton système donc je te remercie pour le coup de main que tu m'as fourni...

@ +
Bretelle

scionexsystems · Answer

salut j'ai essayer d'utiliser votre code.  par compte il me demande de dim les tableau et la variable Lst_Val_Possibles.  de plus je ne comprend pas le . apres la varible Lst_Val_Possibles(i).r(j)

quelqu'un peux m'aider

Aide Algorithme Optimisation

8 réponses

Discussions similaires