Discussion :

[Fixette2000]

Bonjour,

je suis tout à fais nul en math, et encore plus en algorithme, mais j'ai un gros 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 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 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. (exemple cadre D

3-je voudrais aussi calculer la meilleure combinaison qui 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 (exemple cadre A, cadre B, cadre C, cadre B, cadre A).

En fait, j'aimerais pouvoir calculer automatiquement ces 3 solutions, et voir aussi toutes les autres solutions, classées de la plus approchante à la moins approchante de la perfection.

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, 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 devine qu'il y a un problème de recalcule constant.
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.

[CliffeCSTL]

Je te propose de résoudre avec la programmation linéaire :

1 :

Données :

Variable de décisions :






Programme linéaire :

Contraintes :

2. Tu dois pondérer les deux critères d'optimisations.
3. Il suffit de résoudre le pb en remplissant la moitié du mur, avec la possibilité de mettre au maximum une fois la moitié d'un cadre.

[Fixette2000]

Bonjour,

merci pour cette réponse.

Hier sur un autre forum, 2 contributeurs m'ont plutôt guidés vers du code type VBA;
Ici vous me proposez une mise équation que j'ai beaucoup plus de mal à interpréter mais qui me semble plus didactique.

Je ne saurais pour l'instant mettre en parallèle les 2 langages mais je vais me faire mettre dans la peau de Champollion face à la pièce de rosette

En étudiant les problèmes de sac à dos, j'ai l'impression qu'il faut utiliser 3 méthodes différentes pour mes 3 objectifs:

-remplir le mur au maximum (sac à dos multi-objectif?/Procédure de séparation et d'évaluation?)

-utiliser le minimum d'éléments pour remplir au maximum le mur (Algorithme glouton? procédé d'exploration systématique?)

-obtenir une symétrie parfaite qui rempli au maximum le mur (comme vous dites, travailler sur la moitié de la dimension totale voulue))


Bon je mélange un peu tout, mais je sens que le choix de la méthode selon les objectifs est crucial pour ne passer à cotés de solutions plus efficaces que je pourrais trouver de façon empirique…

Je vis étudier tout ça au rythme de ma compréhension, vous avez peut-être exprimé tout cela mais je suis comme un aveugle à qui on essaye d'expliquer une couleur pas facile

Merci en tout cas

[CliffeCSTL]

La méthode pour résoudre ton problème va dépendre de :
1. la taille de celui-ci
2. le temps maximal autorisé pour avoir un résultat

Ma méthode ne te donnera que la solution exacte et est intéressante pour des instances de taille moyenne.



Une autre solution consiste à tester toutes les combinaisons possibles, à afficher celles qui sont réalisables, et à retourner la meilleure trouvée.
Avec un algo de principe ça donne ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
Pour toutes les combinaisons possibles parmi l'ensemble des cadres 
    Si la combinaison courante est réalisable alors
        Afficher la solution
        Si la combinaison courante est une meilleure solution  alors
            mémoriser la combinaison comme meilleure solution

Cette manière de faire est simple et rapide à coder, mais pas du tout adapter sur des grosses instances (Largeur très grande avec des milliers ou millions de cadres)



Après, pour les grosses instances, tu as aussi des méthodes exactes ou approchées mais plus compliquées à mettre en œuvre, à voir tes besoins...

[Fixette2000]

Ok, merci Cliffe CSTL, c'est très clair.

...Effectivement il est possible que j'ai des murs très grands, donc beaucoup plus de possibilités à tester.

Je me dis maintenant qu'il me faudrait peut-être 2 algorithme à utiliser selon la taille du mur.

J'y vois plus clair maintenant...au travers la brume, mais je devine mon objectif

Merci encore

[tbc92]

La question des performances et des temps de calcul : Ce n'est pas un problème.

Dans ton exemple, tu parles de 4 ou 5 cadres sur un mur. Dans la vraie vie, tu auras 10, 20, éventuellement 50 cadres au grand maximum ! Ca reste des petits nombres. Comme disait CliffeCTL, tu vas avoir des problèmes de performance si tu dois placer quelques milliers ou quelques millions de cadre sur un seul et même mur ... configuration purement théorique donc.
Et si par hasard, le calcul que tu dois lancer doit prendre 3 minutes pour trouver la meilleure réponse à chacune des questions, je pense que ça ne te dérange pas vraiment.

[Fixette2000]

CliffeCSTL :

je retourne la question depuis ce temps, et je recentre.

que penses-tu de cet algorithme?