IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Optimiser la constitution de listes


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2017
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Cher (Centre)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2017
    Messages : 3
    Points : 1
    Points
    1
    Par défaut Optimiser la constitution de listes
    Bonsoir.
    Il s'agit pour l'instant de construire un algorithme autre qu'en force brute.

    Exposé du contexte:
    Il s'agit d'un broker qui a un hangar de pièce d'avions. Il a disons 100.000 pièces classées en 8.000 références différentes (donc il a plusieurs exemplaires de certaines). Il a aussi 1.000 plans d'avions différents.
    Dans ces plans, certains ont des pièces communes entre eux certains ont quelques pièces spécifiques.

    Problème :
    Pour vider son hangar, notre broker souhaite établir toutes les listes différentes d'avions qu'il peut construire. Ensuite, il choisira en fonction d'autres paramètres ce qu'il fera de son hangar. Par exemple, il pourra chercher la liste permettant le plus d'avions (pour satisfaire le plus de client), la liste permettant le maximum de bénéfices (en associant les prix des avions) ou bien en s'obligeant à certains appareils pour satisfaire certains client et maximiser son profit ou d'autres...

    Comment faire et optimiser les parcours?
    Pour réduire le problème, j'ai chercher comment trouver ce qu'on ne peut pas faire. Donc, il faudrait parcourir les 1.000 plans et vérifier que chaque pièces est disponible ou extraire des 1000 plans ceux qui sont complets. Déjà, là ça coince je ne sait pas le faire "élégamment", c'est à dire sans créer de monstrueux tableaux de nombre...

    Ensuite, en supposant qu'il ne reste que ce que l'on peut faire, comment sortir toutes les listes en supposant qu'on a fait tel ou tel appareil. De plus, on est pas à l'abri d'obtenir des permutations dans les listes. Si je dit je fais le modèle Y et je vois ce qu'il reste, tiens le X. Mais je fais le X, et je vois ce qu'il reste tiens le Y... Même liste mais obtenu autrement...
    J'avais penser à une sorte de récursivité comme pour le calcul des factoriels mais ça revient à tout passer en revue...

    Du coup, est-ce que quelqu'un peut m'indiquer un modus operandus pour savoir comment partir...

    Évidemment, la question n'a pas de sens avec 100 pièces, 5 références et 2 plans...

    Merci d'avoir lu et si vous pouvez m'aider.
    @+

    Ps: j'aimerais autant ne pas avoir à implémenter des réseaux neuronaux ou autre usine à gaz...

  2. #2
    Membre averti
    Profil pro
    Inscrit en
    Février 2010
    Messages
    264
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2010
    Messages : 264
    Points : 360
    Points
    360
    Par défaut Dissocier les besoins des pièces disponibles des fonctions économiques
    Dans le besoin du problème,
    une liste des articles disponibles est disponible . Il faudra compter les pièces disponibles. Il faudra mettre en place une structure style tableau pour le nombre de pièces disponibles . Un algorithme du style programmation des nombres entiers est nécessaire ou pour le problème des sacs à dos

    une fonction de coût des pièces pour construire des avions est demandée. Pour cette partie, il faudra dénombrer le nombre de pièces par appareil . Pour la fonction de marge, il faudra utiliser un algorithme pour la convexité comme le simplexe de Dantzig

  3. #3
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2017
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Cher (Centre)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2017
    Messages : 3
    Points : 1
    Points
    1
    Par défaut
    Bonsoir,
    merci pour cette réponse. Au début se n'était pas clair mais avec un peu de recherche, je comprend mieux... que ça va pas être simple.

    Le problème du "sac à dos", le nom fait rigoler mais quand on commence à dire que c'est l'un des NP-complet... là, ça rigole moins. Les vieux souvenirs de math-sup T qui ressortent (oui je suis pré-réforme de l'éducation nationale...)

    Du coup, je vais me pencher sur les algorithmes qui permettent une solutions approchée ou exacte en fonction de ce qu'il est possible de faire...

    J'hésite à passer en "résolu" puisque la recherche est encore dessus...
    Si certains ont une solution (même théorique) qui ne débouche pas sur la genèse de la crypto (rien que ça!), je suis preneur.

    Merci encore et @+

  4. #4
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    Août 2008
    Messages
    26 607
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2008
    Messages : 26 607
    Points : 188 574
    Points
    188 574
    Par défaut


    Citation Envoyé par Albertdela Voir le message
    J'hésite à passer en "résolu" puisque la recherche est encore dessus...
    La recherche sera sur ce genre de problèmes tant qu'on n'aura pas prouvé P != NP. En attendant, ça fait plus de cinquante ans que des solutions de type MIP sont utilisées quotidiennement dans l'industrie...

    Tente d'abord de formuler ton problème comme un MIP, puis de balancer un solveur dessus (idéalement, SCIP, OR-Tools ou un solveur commercial, les autres ont du mal en comparaison) : si ça ne marche pas comme tu veux, alors on peut envisager d'autres solutions algorithmiques. Un modèle MIP est souvent idéal, car assez facile à expliquer et extrêmement facile à modifier si tu oublies une contrainte (vas-y pour adapter un algorithme d'approximation...).
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  5. #5
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 033
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 033
    Points : 9 333
    Points
    9 333
    Par défaut
    En moyenne, pour un avion, il faut combien de pièces ? Disons en gros 3000 ?
    Avec une forte disparité ou pas autour de cette moyenne ? Disons non. Disons 10% de plus ou de moins, selon les modèles.
    Donc avec nos 100000 pièces, si tout se combine bien, on va pouvoir faire une trentaine d'avions.
    Mais comme ça ne va pas bien se combiner, on va arriver à une vingtaine d'avions. Et il va nous rester un tiers des pièces, qu'on ne saura pas utiliser.

    C'est réaliste jusque là, ou j'ai tout faux ? Et corrige-moi, parce que forcément, j'ai faux par endroit.
    Le fait d'avoir quelques idées de ce type, ça peut aider...
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  6. #6
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2017
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Cher (Centre)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2017
    Messages : 3
    Points : 1
    Points
    1
    Par défaut des pistes, des pistes, des pistes ...
    Bonjour,

    @durouc05: si les "MIP dont tu parles c'est bien les "Mixed-Integer Programming", je suis en train de regarder ce que c'est et comment ça s'utilise. C'est pas très immédiat non plus mais un peu plus que les NP-complet.

    @tbc92: Je ne savais pas que la répartition pouvait changer quelque chose à l'approche mais pourquoi pas. il faut plutôt voir que tous les avions ont (dans leur pièces) au plus 5% de pièces en commun tous ensemble (les instruments de sécurité, les boites noires, …). Ensuite, on peut avoir entre 5 à 10% qui sont communes dans la même marque (les pneus, les tubes Pitot….) puis 10% de leur pièces communes entre générations d'appareils (moteurs, trains, …) et enfin 30% de leurs pièces communes dans la même gamme. Le reste est spécifique.
    Ca signifie donc qu'il y a jusqu'à 55% de pièce d'un avion que l'on va retrouver sur un autre avion.
    Mais comme le problème du sac, les 5% de pièce commune entre tous vont conditionner le nombre réalisable. Si on a 30 boites noires on ne fera pas plus de 30 avions mais c'est une limite haute (borne supérieure des solutions approximatives de NP-complet ?). De même, s'il manque une pièce spécifique, on ne peut pas faire l'avion donc ça libère toutes les pièce communes des autres…

    J'ai un peu de mal à positionner tout ça dans les arbres pour les NP-complet. Je ne suis pas encore assez savant sur les MIP pour me prononcer…
    Pour l'instant, je ne sais pas par quel bout prendre tout ça…

    Merci pour les pistes, @+

  7. #7
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 033
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 033
    Points : 9 333
    Points
    9 333
    Par défaut
    Je ne connais pas du tout les librairies disponibles sur le marché. Je réfléchis comme si je devais traiter ça 'à la main', réinventer la roue.
    Les volumes de données à traiter me paraissent gros. Comment réduire le volume des données pour redescendre sur des volumes plus raisonnables.
    C'est un peu ce que tu disais, quand tu disais que pour 100 pièces, 5 références et 2 plans, ce serait facile.
    En gros, on doit pouvoir identifier les références qui vont vite être en rupture.

    On regarde les 100 références les plus problématiques ... on a d'un coup une base de données 100 fois plus petite, on fait notre travail d'optimisation sur ce sous-univers, et parmi les solutions proposées, on filtre pour garder uniquement celles qui sont compatibles avec les autres contraintes.
    Si le boulon BB1234 s'utilise systématiquement avec l'écrou EC1234, si on a 50 boulons BB1234 et 60 écrous EC1234 en stock ... on peut retirer l'écrou EC1234 de notre analyse.

    Ou bien, on sait que sur tous les avions, il faut une boite noire. Il y a 5 références différentes de boites noires, et on n'en a que 15 en tout. (3 pour chacune des références). Donc on fera au plus 15 avions ... et on part du principe qu'on arrivera à faire 15 avions.
    Et ça permet de découper le gros chantier en 5 petits chantiers (pas indépendants ... attention)
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  8. #8
    Membre averti
    Profil pro
    Inscrit en
    Février 2010
    Messages
    264
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2010
    Messages : 264
    Points : 360
    Points
    360
    Par défaut Algo du simplexe
    Normalement on fait un algo du simplexe là dessus en disant qu'on met x variable de l'avion A y avions c etc....

  9. #9
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    Août 2008
    Messages
    26 607
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2008
    Messages : 26 607
    Points : 188 574
    Points
    188 574
    Par défaut
    Citation Envoyé par mach1974 Voir le message
    Normalement on fait un algo du simplexe là dessus en disant qu'on met x variable de l'avion A y avions c etc....
    Le gros problème du simplexe, c'est de s'assurer que les variables sont bien entières : j'ai du mal à imaginer 0,5 ou 1/e avion, très personnellement… C'est pour cela que je parlais de modèle MIP.
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

Discussions similaires

  1. [XL-2010] Combobox : Optimiser code : Additem ou List
    Par bickou dans le forum Macros et VBA Excel
    Réponses: 4
    Dernier message: 09/03/2015, 22h44
  2. Optimisations GWT (surtout les listes)
    Par TreyAzagthoth dans le forum GWT et Vaadin
    Réponses: 1
    Dernier message: 30/01/2012, 13h28
  3. Réponses: 6
    Dernier message: 04/07/2009, 15h46
  4. [optimisation] Minimum d'une liste
    Par Nemerle dans le forum Algorithmes et structures de données
    Réponses: 13
    Dernier message: 18/01/2007, 19h52
  5. [VBA-E]Listes Imbriquées : comment optimiser?
    Par hey_chuck dans le forum Macros et VBA Excel
    Réponses: 4
    Dernier message: 30/03/2006, 22h50

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo