Aide Algorithme Optimisation

Messages postés
4
Date d'inscription
dimanche 23 février 2003
Statut
Membre
Dernière intervention
27 juillet 2004
- - Dernière réponse : scionexsystems
Messages postés
1
Date d'inscription
jeudi 17 septembre 2009
Statut
Membre
Dernière intervention
17 septembre 2009
- 17 sept. 2009 à 18:56
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.
Afficher la suite 

8 réponses

Meilleure réponse
Messages postés
4
Date d'inscription
dimanche 23 février 2003
Statut
Membre
Dernière intervention
27 juillet 2004
1
1
Merci
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

Dire « Merci » 1

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

Codes Sources 215 internautes nous ont dit merci ce mois-ci

Messages postés
3758
Date d'inscription
mardi 23 septembre 2003
Statut
Modérateur
Dernière intervention
13 mars 2006
10
0
Merci
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
Messages postés
4
Date d'inscription
dimanche 23 février 2003
Statut
Membre
Dernière intervention
27 juillet 2004
1
0
Merci
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 !
Messages postés
3758
Date d'inscription
mardi 23 septembre 2003
Statut
Modérateur
Dernière intervention
13 mars 2006
10
0
Merci
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
Messages postés
3758
Date d'inscription
mardi 23 septembre 2003
Statut
Modérateur
Dernière intervention
13 mars 2006
10
0
Merci
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
Messages postés
4
Date d'inscription
dimanche 23 février 2003
Statut
Membre
Dernière intervention
27 juillet 2004
1
0
Merci
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...

@+
Messages postés
3758
Date d'inscription
mardi 23 septembre 2003
Statut
Modérateur
Dernière intervention
13 mars 2006
10
0
Merci
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
Messages postés
1
Date d'inscription
jeudi 17 septembre 2009
Statut
Membre
Dernière intervention
17 septembre 2009
0
Merci
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