Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Problème d'allocation avec contraintes et exclusions

Posté par
namsaguine
25-04-19 à 15:06

Bonjour,

Voici mon problème ( voir la fin du post pour avoir un exemple concret qui aidera a comprendre bien mieux mon problème).

Pour x dimensions j'ai y valeurs. J'assigne à ces valeurs un pourcentage du budget total et je les combine avec toutes les autres valeurs de toutes les dimensions auquel cette valeur n'appartient pas. Je souhaite obtenir le budget pour chaque combinaison . Il m'est possible d'éliminer certaines combinaisons.

Voici mon problème:

J'ai découvert qu'il y avait plusieurs solutions pour mon problème donc potentiellement une infinité. De plus je souhaiterais le modéliser (équation ? ) mais n'y arrive pas.

Pourriez vous m'aider ? Ne serait-ce qu'en caractérisant ce type de problème mathématiques ou en m'aiguillant sur des pistes.

Voici l'exemple( simple)

J'ai deux dimensions : dimensions "LETTRE" et dimensions "CHIFFRE".

La dimensions LETTRE contient les attributs suivants : A, B, C, D

La dimensions CHIFFRE contient les attributs suivants : _1, _2, _3, _4

Voici les assignations budgétaires :

BUDGET TOTAL : 400

A : 15%

B : 10%

C : 50%

D : 25%

_1 : 20%

_2 : 40%

_3 : 10%

_4 : 30%

Par default en les combinant tous on obtient (4x4) 16 combinaisons (A et _1, A et _2 etc etc ).

Pour trouver le budget de chaque combinaison il suffit de faire:

BUDGET_TOTAL * LETTRE_POURCENTAGE * CHIFFRE_POURCENTAGE

Seulement si je décide de supprimer les combinaisons :

C et _2

A et _4

cela se complique, ma formule ne fonctionne plus.

Car la somme du budget des attributs doit respecter les pourcentage initialement définis.

J'ai réussi à la main a trouver une solution pour cette exemple mais je souhaiterais la mettre en formule . Je suis bien conscient qu'a un certains moment il n'y a plus de solution possible.

De plus j'ai déjà essayé avec la méthode la plus utilisée  pour résoudre le problème d'allocation; l'algorithme hongrois ( Kuhn-Munkres) dont le but est de trouver le couplage le plus optimisé pour affecter N projets à N équipes, mais j'ai pas réussi.

https://docs.google.com/spreadsheets/d/1qeOOsLOeE9QMHZUOG1uH5cjPbiDpxKKOFb8tBdPOP6w/edit?usp=sharing

Je vous remercie par avance

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !