Algorithme pour un problème d'optimisation
Bonjour, :D
J'ai rassemblé les données de ton problème, pour la clarté de l'énoncé.
Citation:
Envoyé par
Fixette2000
... 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 cadre A 30cm de large, cadre B 40cm de large, cadre C 50cm de large, cadre D 70cm de large).
Je dois respecter un écart de 8 cm entre chaque cadre et au minimum 6 cm 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 ...
Citation:
Envoyé par
Fixette2000
... je n'aurais pas de murs de plus de 35 m à priori ...
Citation:
Envoyé par
Fixette2000
... J'ai un stock de cadres photos de 4 largeurs différentes et je peux en racheter si besoin;
(ICI considérant que j'ai un stock illimité de cadres)
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
Cadre A de largeur 30cm (vA) au nombre illimité (n 8) ou limité (nA)*
Cadre B de largeur 40cm (vB) au nombre illimité (n 8) ou limité (nB)*
Cadre C de largeur 50cm (vC) au nombre illimité (n 8) ou limité (nC)*
Cadre D de largeur 70cm (vD) au nombre illimité (n 8) ou limité (nD)*
J'ai un mur (m) de largeur connue (vm)
Je cherche à obtenir la meilleure combinaison (et donc la quantité de chaque type de cadres nécessaire) pour remplir au maximum le mur
sachant que:
-on peut choisir plusieurs fois ou aucune fois chaque cadre.
-vm est supérieur ou égale à 1 vA
-vA, vB, vC, vD sont tous supérieur à 0
selon plusieurs cas:
Cas 1: J'ai un stock illimité de cadres et je cherche (dans l'ordre des opérations) la solution qui remplisse le plus le mur, puis qui utilise le moins de cadres.
(*Cas 2: j'ai un stock limité de chaque type de cadres (par exemple nA=12 nB=12 nC=12 nD=12) et je cherche (dans l'ordre des opérations) la solution qui remplisse le plus le mur, puis qui utilise le moins de cadres. )
Cas3: je veux utiliser en priorité les plus grands cadres (en dernier lieu les plus petits cadres, par exemple A+A+A+A+C+C+C+BB+A) quitte à accepter une solution de 10% moins optimale que la solution du cas 1 (ou*cas2)
=(algorithme glouton/division euclydienne)
Cas 4: je veux un calepinage de composition parfaitement symétrique (par exemple A + B + C + B +A
ou encore A+B+C+D+D+C+B+A)
Question programmation, je souhaiterais combiner ces 3 ou 4 algorithmes pour voir s'afficher dans l'ordre:
-La combinaison la plus optimale, c'est à dire la plus approchante de la valeur (vm) du mur
-La combinaison la plus optimale, à condition qu'elle utilise le maximum de grands cadres
-La combinaison la plus optimale, à condition qu'elle permette une symétrie dans son agencement, en utilisant si possible les plus grands cadres en priorité |
Ne pourrais-tu pas envisager d'introduire
a) la largeur effective du mur: Lm = Vm - 4 ;
b) les largeurs effectives de chaque cadre; La = Va + 2*(8/2) = Va + 8 ; Lb = Vb + 8 ... etc ?
Tu retrouverais ainsi les écarts minimaux à respecter
- entre deux cadres consécutifs: 8/2 + 8/2 = 8 cm ,
- entre le bord du mur et le premier (ou dernier) cadre: 8/2 + 4/2 = 6 cm ,
ainsi que les valeurs maximales des nombres de chaque type de cadres:
NaMax = Trunc(Lm/La) , NbMax = Trunc(Lm/Lb) , NcMax = Trunc(Lm/Lc) , NdMax = Trunc(Lm/Ld) .
Il te suffirait, dans le cas éventuel d'un stock limité, d'ajouter les corrections conditionnelles:
NaMax = Min(NaMax, NaLim) = Min(NaMax, 12) , NbMax = Min(NbBax, NbLim) ... etc
ce qui d'ailleurs limiterait salutairement le nombre total de combinaisons à
NaLim*NLlim*NcLim*NdLim = 124 = 20736
.
La recherche de la combinaison optimale pourrait alors relever
a) soit d'une énumération complète à l'aide de 4 boucles imbriquées, par un algorithme du type:
Code:
1
2
3
4
5
6
7
8
9
|
FOR Ia:= 1 TO NaMax DO
FOR Ib:= 1 TO NbMax DO
FOR Ic:= 1 TO NcMax DO
FOR Id:= 1 TO NdMax DO
BEGIN
Ltot:= Ia * La; Inc(Ltot, Ib * Lb); Inc(Ltot, Ic * Lc); Inc(Ltot, Id * Ld);
IF (Ltot<=Lm) THEN <Examen des critères>
END |
ou si le mur apparaît trop large et les combinaisons trop nombreuses, d'un tirage aléatoire:
Code:
1
2
3
4
5
6
7
|
REPEAT
Na:= 1 + Random(NaMax); Nb:= 1 + Random(NbMax);
Nc:= 1 + Random(NcMax); Nd:= 1 + Random(NdMax);
Ltot:= Ia * La; Inc(Ltot, Ib * Lb); Inc(Ltot, Ic * Lc); Inc(Ltot, Id * Ld);
IF (Ltot<=Lm) THEN <Examen des critères>
UNTIL <Critère d'arrêt>; |
Le bloc d'instructions <Examen des critères> consisterait à vérifier les conditions données, selon l'ordre de préséance indiqué.
Remarque: il est possible d'abréger l'énumération par une évaluation plus progressive des limites supérieures (NbLim, NcLim), et par la suppression de la dernière boucle: on peut en effet calculer directement (Nd) en fonction des 3 autres termes.
