Discussion :

[scorbo]

Bonsoir,

Je cherche à résoudre un problème mathématiques collaboratif demande/fournisseurs. Le problème est le suivant : une demande globale arrive aux fournisseurs et ceux-ci doivent s'organiser pour répondre à la demande. Chaque fournisseur n'ayant pas les mêmes moyens chacun fournis ce qu'il peut. L'objectif étant également de répartir le plus équitablement possible les efforts entre eux. Par exemple, si un seul fournisseur peut répondre à la demande, le résultat ne sera pas optimum car le travail n'est pas réparti entre tous les fournisseurs. Donc il y a deux objectifs à tenir : répondre au mieux à la demande et le faire le plus équitablement possible.
Une difficulté s'ajoute à ce problème : certains fournisseurs produisent par lot et non par unité.

J'ai regardé du côté de la méthode simplex, mais elle fournie des solutions continues or comme certains fournisseurs produisent par lot leur solution est définie dans un ensemble. De plus, il y a deux équations à maximiser : atteindre la demande et l'équilibrage parmi les fournisseurs.

Je recherche un algorithme léger/simple et le plus efficace possible car le temps de calculs doit être très rapide. Je ne peux pas non plus utiliser de librairies, il me faudra écrire tout l'algorithme.


Toutes les idées sont les bienvenues !
Merci d'avance.

[anapurna]

salut

le plus simple c'est de distribuer tes pièces selon le minimum de tes fournisseur
si le mini est supérieur a la quantité restante a distribuer alors la distribution seras équitable entre tout les fournisseur restant
imaginons que tu ai 5 fournisseur dont 1 peut faire 10 pièces ,le second 15 et les autres pas de limite
donc le premier tour tu distribue
10 a tout le monde => 50 pièces fournis
au deuxième tour tu ajoute le 5 => 4*5 = 20 :=> 70 pièces fournis au total
il te reste donc 30 pièces a divise par 3 ce qui donne 10 pièces par fournisseur restant

[tbc92]

Tu dis que tu as 2 équations à maximiser. Aucun algorithme ne sait traiter cela.
Déjà, un élément de langage, on ne maximise pas une équation. On résout une équation, ou on maximise une valeur.
Du coup , bonne nouvelle, tu as en fait une équation à résoudre, et une valeur à maximiser.

L'équation à résoudre, c'est : la somme des fournitures produites par chaque fournisseur doit coïncider avec la commande.
La valeur à maximiser : il faut équilibrer les commandes.

Ah, mauvaise nouvelle, équilibrer les commandes, ça vaut dire quoi précisément. Si j'ai 5 fournisseurs (F=5), et 100 articles à produire (N=100) , tu veux que chaque fournisseur produise 20 articles, c'est ça ?
Donc , si on fait l'impasse sur le fait que certains fournisseurs ne savent pas produire à l'unité, on divise N par F, et voilà.
Et si un fournisseur n'est pas en mesure de produire ce montant, on lui demande quand même le max de ce qu'il peut faire, et on répartit ce qui manque entre tous les autres.

C'est ça ?

[scorbo]

Merci pour vos idées, elles rejoignent ce que j'avais en tête. Néanmoins :

Anapurna

imaginons que tu ai 5 fournisseur dont 1 peut faire 10 pièces ,le second 15 et les autres pas de limite... 10 a tout le monde => 50 pièces fournis

Ce n'est pas possible car le second ne sait pas faire 10 pièces, il les fabrique par lot de 15. Donc la commande de 10, il l'a refusera.


tbc92
Dans l'idée c'est ça, par contre la difficulté c'est que parfois on peut produire exactement ce qui est demandé au déprimé d'un moins bon équilibre.
Par exemple : le fournisseur 1 sait produire des lots de 10, 30 et 50, le fournisseur 2 des lots de 20, 40 et 50. On passe une commande 40 unités. On pourrait répartir : 10 pour le fournisseur 1 et 20 pour le fournisseur 2 donc on produit 30 unités avec un certain équilibrage. Mais la priorité étant d'atteindre la commande, il vaut mieux que ce soit le fournisseur 2 qui s'en occupe : 40 et là on a le compte ! (un fournisseur ne produit qu'une fois par commande).

[tbc92]

Et dans cet exemple, on ne peut pas avoir :
Fournisseur 1 = 2x10
Fournisseur 2 = 20
Le fournisseur 1 sait produire soit 10, soit 30, mais pas 2 fois 10 ?

Et autre question, si la commande est de 100, avec ces 2 mêmes fournisseurs, une des solutions , c'est de demander au fournisseur 1 un lot de 10, un lot de 50, et au fournisseur 2, un lot de 40.
Ok, le fournisseur 1 ne peut pas produire 2 lots de 10, mais peut il produire un lot de 10 et un lot de 50 ?

[scorbo]

Le fournisseur 1 sait produire soit 10, soit 30, mais pas 2 fois 10 ?

C'est exactement ça !

Ok, le fournisseur 1 ne peut pas produire 2 lots de 10, mais peut il produire un lot de 10 et un lot de 50 ?

Oui, il peut.

[tbc92]

Ok. A ce niveau, je pense que les règles entre ce qui est autorisé et interdit sont connues.

Nouvelles questions, c'est quoi les ordres de grandeurs. Dans cet exemple, on a 2 fournisseurs, et 6 lots disponibles (10 , 30, 50, 20, 40 et 50).
Dans la pratique, j'imagine qu'on parle de montants bien supérieurs, mais combien ? Accessoirement, as-tu des jeux de données réalistes.

Ensuite, il va falloir définir ce que veut dire le mot "équilibré"
Par exemple, si j'ai 4 fournisseurs, si j'hésite entre 40+40+45+60 et 35+40+55+55, laquelle de ces 2 combinaisons est la pus équilibrée. As-tu une idée de comment quantifier un équilibre, comment classer différentes combinaisons de la moins équilibrée à la plus équilibrée. As-tu des règles spécifiques à ton domaine d'activité ?

[scorbo]

Actuellement j'ai 3 fournisseurs, ça peut monter à environs 8, 10. Le nombre de lots par fournisseurs serait de l'ordre de 5.
Le nombre d'unité par lot n'est pas très grand de 0.5 à environs 8. Un exemple concret est :
F1 = [1, 1, 1] (ça peut paraitre bizarre comme fournisseur... mais il a en interne 3 lignes de productions d'une unité chacune).
F2 = [1, 3, 4]
F3 = [0...4] (continu)

Concernant l'équilibrage, je pense calculer l'écart-type. Exemple :
F1 et F2 peuvent fournir chacun au maximum 6 unités et la commande est de 6 unités. Si F1 produit 6 et F2 0, on aura un écart type de sqrt((6-6)² + (6-0)²)= 6 alors que si chacun en produit 3 on obtient sqrt((6-3)² + (6-3)²)= 4.24.

Donc plus ce résultat sera petit et plus on sera équilibré.


Dans l'idéal, je préfèrerai (si possible), un algo collaboratif. J'entends par là que ce sont les fournisseurs qui s'arrangent entre eux et non un intermédiaire qui calcul pour eux. Car ça serait plus simple d'ajouter un fournisseur. Du coup, on leur passe la commande et c'est eux qui se débrouille. Plus besoin de connaitre leur caractéristiques (continu, discret, nombre de lots...).

[tbc92]

On est donc sur des nombres de fournisseurs et des nombres de combinaisons relativement limités. Rechercher toutes les combinaisons, puis rechercher la plus équilibrée parmi ces solutions, ça devrait prendre peu de temps.

Sur le principe de prendre l'écart-type, je suis Ok. Mais je calculerais l'écart-type différemment. A priori, ça donne le même classement, mais pas sur.
C = la commande
NF = le nombre de fournisseur
M = C/NF = le montant moyen commandé à chaque fournisseur (éventuellement un nombre non-entier).
Xi = le montant commandé au fournisseur n°i.
Ecart-type = racine ( somme [ (Xi-M)² ] )

Et comme on veut que le calcul aille vite, on va seulement calculer :
variance = somme [ (Xi-M)² ]

Rechercher toutes les combinaisons, c'est du parcours d'arbre. Regarde ce que tu trouves sur ce sujet, et adapté au langage que tu comptes utiliser.

Dans la recherche de toutes les combinaisons, il faut considérer chaque ligne de production comme indépendante.

Mais il y a un point dans ton dernier message qui me fait un peu peur, et qui pourrait remettre en cause toute la réflexion depuis le début.
Tu dis que le fournisseur 3 peut produire [0...4] (continu), et tu dis qu'une commande, ça peut valoir 0.5, donc un nombre à virgule.

On travaille avec des valeurs discrètes, ou des valeurs continues ? Si on travaille avec des valeurs continues, on ne peut plus recenser toutes les combinaisons, ça change beaucoup de choses.

[scorbo]

Mais je calculerais l'écart-type différemment. A priori, ça donne le même classement, mais pas sur.

J'ai testé, il semblerait que le classement ne soit pas identique :
F1, F2 et F3 peuvent fournir chacun des lots [1, 2, 3]. La commande est de 6. Si on "équilibre" en demandant :
F1 = 6 lots (1+2+3)
F2 = 0
F3 = 0
Dans ton cas, la variance est de : 24 dans mon cas, elle est de 72.

Si on équilibre :
F1 = 3 lots
F2 = 1 lot
F3 = 2 lots

Dans ton cas, la variance est de : 50 (donc pire) dans mon cas, elle est de 14.

Dans mon idée, la variance calcule la satisfaction d'un fournisseur à contribuer au maximum à la commande. Mais il y a peut être un meilleur calcul à faire...



Ca m'embête, tu en es arrivé à la même conclusion que moi : parcours d'arbre ! Je dis que ça m'embête parce que j'aurai bien aimé avoir une toute autre idée
En effet, ça marcherait et on peut également couper des branches dans certains cas pour accélérer le parcours. Ce n'est pas un algo collaboratif, mais il devrait fonctionner. Ceci dis, le parcours me parait pouvoir être très long : si on prend au maximum : 10 fournisseurs avec chacun 5 chaines de production. Pour chaque fournisseur on a 2^5=32 combinaisons possibles à multiplier pour chaque fournisseur, soit 32*32*32*32... = 1125899906842624 (j'ai fait une erreur quelques part ??)

On travaille avec des valeurs discrètes, ou des valeurs continues ? Si on travaille avec des valeurs continues, on ne peut plus recenser toutes les combinaisons, ça change beaucoup de choses.

C'est un point qui m'embête également !
Il y a deux types de fournisseurs, ceux qui fournissent des lots de valeurs continue dans un intervalle connu par exemple [0...4] et d'autres qui fournissent des lots de valeurs fixes et connues mais qui peuvent être à virgule (même à virgule je ne vois aucun souci à parcourir le graphe).
Ceci dis, le premier type de fournisseur n'est peut être pas si bloquant que ça. Ce n'est pas l'idéal, mais il suffirait de diviser les fournisseurs de type continus par un lot de taille choisi, selon la granularité que l'on souhaite (problème : plus la granularité sera fine, plus ça ajoutera de combinaisons).

[anapurna]

Merci pour vos idées, elles rejoignent ce que j'avais en tête. Néanmoins :

Anapurna

Ce n'est pas possible car le second ne sait pas faire 10 pièces, il les fabrique par lot de 15. Donc la commande de 10, il l'a refusera.


tbc92
Dans l'idée c'est ça, par contre la difficulté c'est que parfois on peut produire exactement ce qui est demandé au déprimé d'un moins bon équilibre.
Par exemple : le fournisseur 1 sait produire des lots de 10, 30 et 50, le fournisseur 2 des lots de 20, 40 et 50. On passe une commande 40 unités. On pourrait répartir : 10 pour le fournisseur 1 et 20 pour le fournisseur 2 donc on produit 30 unités avec un certain équilibrage. Mais la priorité étant d'atteindre la commande, il vaut mieux que ce soit le fournisseur 2 qui s'en occupe : 40 et là on a le compte ! (un fournisseur ne produit qu'une fois par commande).

dans ce cas je pense qu'il va falloir lisser tes commandes sur l'année en prenant par exemple les commandes passé sur l'année d'avant
il est quasi impossible d’équilibré sur une commande ... il y a des contraintes que tu ne pourras supprimer qu'en cumulant les commandes annuellement