problème de recherche opérationnelle.

[pouic92]

Bonjour à tous

Mes cours de RO sont très très très loins et j'ai besoin d'un coup de main pour résoudre le problème suivant :

J'ai x des familles de produits P : P1 à Px (environ 500)
J'ai y fournisseurs F : F1 à Fy (environ 2000)
J'ai 100000 produits qui sont répartis entre les fournisseurs et les familles de produits (Qxy représente le nombre de produits associés à la famille x et au fournisseur y)

Enfin, j'ai trois techniciens et je veux affecter mes produits à chacun d'eux, de telle manière que :
- Tous les produits d'une famille soient affectés a 1 et 1 seul technicien
- Tous les produits d'un fournisseurs soient affectés à 1 et 1 seul technicien

L'optimum : Je veux que les techniciens aient une charge de travail la mieux répartie possible, c'est à dire qu'il aient chacun un nombre de produit aussi proche que possible de 100000/3

Je me doute qu'il s'agit d'un problème PL en nombres entiers mais j'ai du mal à aller plus loin.

Pouvez vous m'aider à modéliser ce problème et à identifier la méthode de résolution ?

Comment décire la fonction à optimiser ?
Comment décire les contraintes ?

Merci
-----

[Tryss2]

Premièrement, il faut se rendre compte que ton problème n'a pas nécessairement de solution : tes contraintes peuvent en effet entrainer que tout les produits doivent être affectés au même technicien (si un fournisseur fait toutes les familles de produits par exemple, mais des cas plus complexes peuvent se produire).

Mais voila comment je procèderai : Je choisi une famille de produit P1, Je mets tout les produits qui la composent dans la boite A1. Ensuite, je prends tout les éléments de la boite A1, et je fait la liste de toutes les fournisseurs qui produisent cette famille. Je rajoute tout les produits qui ont ces fournisseurs. Je fait alors la liste de toutes les familles produites par ces fournisseurs, et j'ajoute tout les produits de ces familles... je réitère jusqu'à ce que plus rien ne soit ajouté : ça me donne un groupe A1 qui devra nécessairement être attribué au même technicien.

Je prends ensuite la première famille de produits Pi qui n'est pas dans A1, et j'utilise la même procédure, ça me donne un groupe A2. Et ainsi de suite.

On va donc se retrouver avec un problème plus simple/classique : comment répartir un certain nombre de groupes Ai entre 3 techniciens de la sorte que les effectifs des groupes attribués soient les mieux répartis possibles.

[choom]

Je crois même que la solution de Tryss2 est la plus efficace, simple et la seule logique possible.

J'espère pour vous que les partitions de votre ensemble de produits que constituent les familles et les fournisseurs permettent en effet des groupes cohérents de tailles suffisemment petites que pour pour que vos techniciens puissent se répartir les produits de manières plus ou poins égales. Ce n'est pas gagné si l'un des gros fournisseurs est actif sur beaucoup de familles, ni si l'une des familles de produits est à ce point commune qu'une majorité de fournisseurs en vendent au moins un produit...