Problème d'allocation avec contraintes et exclusions

[NAMSAGUINE]

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/ ... sp=sharing

Je vous remercie par avance

[fatal_error]

slt,

je sais pas si bon pour toi mais...
dans ton application ya des trucs un peu etranges.
par ex:
si tu traces

Code: Tout sélectionner

M =

   12    8   40   20
   24   16   80   40
    6    4   20   10
   18   12   60   30


pour la ligne 6,4,20,10
tu obtiens la nouvelles ligne
8.6;3.7;18.5;9.2
Or en terme de ratio A3 = 1.5B3 or 8.6/3.7 > 2
donc oui tu préserves la somme sur ligne et la somme sur colonne, mais les pourcentages sont plus respectés.

voici une variante
tu supprimes (tjs 18). tu multiplies tout le monde par un bon facteur et de fait tu préserves ton budget global (400) et tes pourcentages.

Code: Tout sélectionner

S=400
f = S/(S-18)
M(4,1) = 0
M2 = M*f
M2 =

   12.56545    8.37696   41.88482   20.94241
   25.13089   16.75393   83.76963   41.88482
    6.28272    4.18848   20.94241   10.47120
    0.00000   12.56545   62.82723   31.41361



on voit sans pb que on peut supprimer autant d'éel que l'on veut, les cases non concernées auront leur pourcentage préservé