Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 25-04-2019 13:52:04

Noura Amsaguine
Membre
Inscription : 25-04-2019
Messages : 1

Problème d'allocation avec contraintes et exclusions

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

Hors ligne

#2 28-04-2019 08:01:22

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : Problème d'allocation avec contraintes et exclusions

Bonjour,

Une suite de matrices (4x4) à éléments réels ne pourrait-elle pas convenir, pour approcher la solution ?

Chaque ligne pourrait correspondre aux subdivisions (A, B, C, D) de la 1ère catégorie, caractérisées par les proportions idéales (ou recherchées) L°i = (0.15, 0.10, 0.50, 0.25) pour i = (1, 2, 3, 4);
chaque colonne aux subdivisions (_1, _2, _3, _4) de la seconde, caractérisées par les proportions idéales  C°j = (0.20, 0.40, 0.10, 0.30) pour j = (1, 2, 3, 4) .

Le terme initial de cette suite serait représenté par la matrice M0 = [mij]0 , dont chaque élément admettrait pour valeur (mij)0 = L°i*C°j dans le cas d'une combinaison autorisée, zéro dans le cas contraire.

Second point: la relation de récurrence permettant de passer du terme de rang (k) au suivant (k+1); il faut disposer:
a) de la somme Sk de tous les éléments de la matrice (Mk) ,
b) des sommes partielles correspondant à chaque ligne (Sli)k (soit quatre termes dans le cas présent),
c) et de celles correspondant à chaque colonne (Scj)k (là encore, 4 termes).
Les deux séquences vérifient par définition:

Sk = (Sl1)k + (Sl2)k + (Sl3)k + (Sl4)k = (Sc1)k + (Sc2)k + (Sc3)k + (Sc4)k .

Les proportions de chaque subdivision de la première catégorie ont alors représentées par les rapports:

(pi)k = (Sli)k/Sk ≠ L°i,

celles de chaque subdivision de la seconde par les rapports:

(qj)k = (Scj)k/Sk ≠ C°j ;

ce qui conduit à envisager la matrice de transformation (Tk), dont chaque élément admettrait pour expression:

(tij)k = ((L°i*C°j)/((pi)k*(qj)k))1/2

La nouvelle matrice (Mk+1) pourrait alors résulter du produit terme à terme Mk+1 = Mk│Tk ,
où chaque élément serait simplement donné par

(mij)k+1 = (mij)k*(tij)k ;

les termes initialement nuls le resteraient indéfiniment.

Je n'ai aucune idée de la convergence de la suite engendrée, faute d'avoir abordé ce problème.
La convergence pourrait être constatée en calculant la norme euclidienne de la différence entre deux termes successifs

∆Mk = Mk+1 - Mk ;

Cette norme N(Ek) devrait tendre vers zéro - ou tout au moins devenir inférieure au seuil de précision attendu.
Autre critère, encore plus important finalement: s'assurer que les conditions recherchées sont bien vérifiées en calculant les écarts-types (uk, vk)  donnés par les relations:

4*uk2 = i=14((Sli)k - L°i*Sk)2   ,   4*vk2 = i=14((Sci)k - C°i*Sk)2

et qui doivent devenir très petits devant la moyenne des termes non nuls.

C'est un bon sujet de programmation.

Dernière modification par Wiwaxia (28-04-2019 17:30:29)

Hors ligne

#3 28-04-2019 21:43:12

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : Problème d'allocation avec contraintes et exclusions

Re-bonjour,

J'ai regardé ce que cela pouvait donner par programmation.

La suite matricielle converge assez rapidement, et la limite obtenue vérifie les conditions imposées à condition de prendre pour les éléments de la matrice de transformation (à l'étape de rang k) l'expression:

tij = (p/q)1/2 , avec p = L°i*C°j et q = Sli*Scj .

Voici ce que l'on obtient au bout de 10 itérations:

k=10

Tous les éléments de la matrice (Tk) se rapprochent de l'unité, et l'on peut calculer la moyenne quadratique des 16 écarts

eij = (tij - 1) .

La condition d'arrêt du programme est ainsi toute trouvée: l'itération cesse lorsque l'écart-type de vient inférieur à un seuil convenu.
Voici la matrice limite obtenue dans le cas où elim = 10-7:

Résultat_2

On retrouve bien les proportions définies en début de discussion.
L'approche de la limite peut être poussée plus loin, pour des valeurs plus faibles du seuil:
     elim = 10-12     k = 265     Ec = 9.61E-13
     elim = 10-15     k = 339     Ec = 9.23E-16
     elim = 10-18     k = 412     Ec = 9.75E-19
     elim = 10-20     k = 468     Ec = 0

Le programme source est rédigé en Pascal.

Dernière modification par Wiwaxia (29-04-2019 10:49:17)

Hors ligne

Pied de page des forums