Problème de couplage / optimisation
Bonjour,
je suis face à un problème concernant un exercice de recherche opérationnelle.
Dans une école primaire nous avons 4 professeurs qui doivent enseigner 6 matières (Maths, Français, Sport, Histoire-Géo, Anglais, SVT) pour une classe.
Certains de ces professeurs sont multi compétences (ils peuvent enseigner de 2 à 6 matières) et d'autres sont mono compétences.
Le nombre d'heures d'études par matière doit être garanti (chaque matière doit être dispensée à la hauteur de ce qui a été fixé en terme d'heures).
Je cherche donc une répartition à faire entre les professeurs : exemple il faut faire 15h de maths, 12h de Français, 4h de sport : Professeur A va enseigner 50% de son temps les maths, 25% le sport et 25% le Français, professeur B enseignera 75% le sport et 25% le Français, professeur C va enseigner 50% de son temps les maths et 50% le Français (il n'est pas qualifié pour faire prof de sport). Il ne reste plus d'heure à faire pour professeur D.
Comment trouver une répartition optimisée ?
Je sais qu'il faudra peut être passer par un algo de couplage (mais je sais pas lequel), puis il y aura sûrement de l'optimisation à faire via Simplex
Je ne sais pas par ou commencer donc je suis un peu perdu.
Merci de votre aide.
je suis face à un problème concernant un exercice de recherche opérationnelle.
Dans une école primaire nous avons 4 professeurs qui doivent enseigner 6 matières (Maths, Français, Sport, Histoire-Géo, Anglais, SVT) pour une classe.
Certains de ces professeurs sont multi compétences (ils peuvent enseigner de 2 à 6 matières) et d'autres sont mono compétences.
Le nombre d'heures d'études par matière doit être garanti (chaque matière doit être dispensée à la hauteur de ce qui a été fixé en terme d'heures).
Je cherche donc une répartition à faire entre les professeurs : exemple il faut faire 15h de maths, 12h de Français, 4h de sport : Professeur A va enseigner 50% de son temps les maths, 25% le sport et 25% le Français, professeur B enseignera 75% le sport et 25% le Français, professeur C va enseigner 50% de son temps les maths et 50% le Français (il n'est pas qualifié pour faire prof de sport). Il ne reste plus d'heure à faire pour professeur D.
Comment trouver une répartition optimisée ?
Je sais qu'il faudra peut être passer par un algo de couplage (mais je sais pas lequel), puis il y aura sûrement de l'optimisation à faire via Simplex
Je ne sais pas par ou commencer donc je suis un peu perdu.
Merci de votre aide.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Je connais bien la recherche opérationnelle, mais si je comprends bien ton problème, tu cherches le nombre d'heures à affecter à chaque prof pour remplir au mieux le quantum horaire pour chaque matière.
Pour ton exemple, je trouve 13 heures pour le prof A, 1 heure pour le prof B et 17 heures pour le prof C, le prof D n'a pas de temps de travail.
Est ce que j'ai compris ?
Effectivement c'est ça, mais comment tu as fait?
En réalité je cherche à faire ça sur une bien plus grande échelle, donc je cherche à implémenter un algorithme pour faire ça.
Merci d'avance pour l'aide
Ce qu'il faut optimiser en priorité est bien les heures à dispenser.
Donc le type de réponse qu'il faut donner est : prof A : 27% maths, 53% Francais, 20% sport etc..
Trouver Le pourcentage 'Idéal' pour chaque prof : comment tu traduis ça en termes mathématiques ou informatiques ?
Dans un problème d'optimisation, on a plein de dispositions qui correspondent aux contraintes, et on veut choisir celle qui donne le meilleur résultat pour une certaine fonction d'évaluation.
Extrait d'un cours pour lycéens : Résoudre un problème d'optimisation, c'est rechercher le couple $(x,y)$ qui, selon le contexte, maximise ou minimise la fonction à optimiser.
Ici, éventuellement, chaque prof a des souhaits, tous les profs préfèrent enseigner les maths et pas le sport. Et on va essayer de satisfaire le prof A, parce que c'est un râleur ... On a les débuts d'une base pour une fonction d'évaluation.
Et selon les volumes de données (nombre de profs , nombre de matières ...) les outils à utiliser sont variables. Pour beaucoup de données, une base serait la méthode de Monte-Carlo. L'autre mot-clé qui va te permettre de trouver des informations, c'est la méthode du gradient. Ou des outils comme Simplex, tu en parles dans le 1er message.
Si tu as peu de données, une recherche systématique de toutes les solutions est même envisageable.
Et a priori, on est plus dans le domaine 'Informatique' que dans le domaine 'Combinatoire'.
Dans ce cas là, on a trouvé une solution optimale très facilement parce il n'y a pas beaucoup de contraintes, presque pas si ce n'est le pourcentage sur leur temps qu'ils veulent allouer à chaque matière, et le respect du quantum horaire pour chaque matière. En fait dans ce genre de problème il faut savoir ce qu'on veut. Y a pas besoin de spéculer sur des données qui ne sont pas dans le problème.
Dans ce cas précis, toute autre répartition des heures de travail différente de la solution que j'ai donnée, soit ne permettrait pas de pouvoir respecter le quantum horaire pour chaque matière, soit affecterait à certains profs des heures superflues (sans travail). C'est ça qui signifie que le résultat donné est optimal.
Une solution optimale serait alors de mettre le plus de professeur possible sans heure de cours.
Amsel n'a toujours pas formulé correctement sa question.
J'essaie péniblement de comprendre le 1er message. En particulier ce passage :
Babsgueye, tu parles de solution optimale.... Tu pourrais aussi dire que tu as trouvé la pire solution, ce serait aussi correct. On parle de solution optimale quand on choisit parmi plusieurs solutions. Quand il n'y a qu'une solution, ça n'a pas de sens de parler de solution optimale.
Tant que Amsel n'aura pas donné une formulation correcte de son besoin, il est illusoire de lui apporter des solutions.
Pourquoi la solution est optimale, je l'ai dit dans le message précédent. Par exemple 20 heures pour le prof A, 20 heures pour le prof B, 20 heures pour le prof C ça arrangerait aussi son problème, mais c'est pas une solution optimale parce que des profs resteront un temps à ne rien faire (''et ils seront payés par exemple'').
Merci beaucoup pour vos réponses et pour votre implication.
Effectivement je me suis rendu compte que j'avais très mal exprimé mon problème.
Je vais retenter de l'expliquer en prenant en compte tous vos super messages.
Pour cela je vais changer d'exemple et beaucoup plus l'expliciter.
Nous sommes dans un fast food qui fait uniquement des burgers.
La cuisine comporte plusieurs postes de travail: 2 fours à pain, 3 postes de cuisson des steaks, 1 poste de préparation des toppings (salade tomate fromage) et 4 postes d'assemblage des burgers.
Je me limite à ça pour le moment mais on peut imaginer qu'il y ait beaucoup plus de postes de travail (ex: 3 postes en plus qui font des desserts, 2 postes de boissons).
Dans notre fast food il y a également des employés polyvalents, avec chacun leurs compétences :
Compétences Employé 1 : four à pain, cuisson des steaks
Compétences Employé 2 : cuisson des steaks, assemblage, desserts
Compétences Employé 3: préparation des toppings, cuisson des steaks, desserts
Compétences Employé 4: four à pain, préparation des toppings
Compétences Employé X : etc......
On considère qu'on reçoit la liste des burgers à faire le matin même et qu'ils doivent être prêts pour le soir même et donc il faut organiser notre journée de travail.
En réalité cela revient à savoir combien de temps chaque poste de travail va être occupé.
Ce que je cherche à faire, c'est compte tenu des compétences de chaque employé, et du travail à faire sur chaque poste, comment faire pour les répartir de façon à ce qu'on arrive à fabriquer tous les burgers demandés.
Les employés n'ont pas de préférence, ils peuvent être affectés partout du moment qu'ils sont compétents pour réaliser la tâche.'
La vraie contrainte que je vois est que les postes qui seront les plus utilisés (ex: cuisson des steaks, car tous les burgers ont un steak) doivent tout le temps être occupés pour faire le maximum de steaks.
Si vraiment il faut ajouter des contraintes, on peut par exemple imaginer que certains employés sont meilleurs sur un poste que l'autre et donc il faut le prioriser sur le poste où il est le plus fort.
Je comprends bien que d'un point de vue mathématique, on cherche surtout à savoir qu'est ce qu'il faut maximiser, quelles sont les contraintes, mais en réalité j'ai du mal à définir cela et trouver le point de départ.
En sortie de mon algorithme / Solveur: (ce à quoi je m'attends c'est bien une répartition du temps de mes employés que me proposera le solveur, et qui me garantie que les burgers seront fabriqués)
Je veux avoir quelque chose comme ça:
Sur une journée de 7h de travail :
Employé 1: 50% de son temps sur four a pain; 50% de son temps sur cuisson des steaks (cela veut dire qu'il reste (2x7h) - 3,5h = 10,5h à distribuer sur les fours à pain et (3x7h) - 3,5h = 17,5h
Employé 2 : 25% de son temps sur la cuisson des steaks; 25% sur l'assemblage; 50% sur les desserts ( cela veut dire qu'il reste 10,5h - 25%x7h=8,25h de temps à distribuer sur la cuisson des steaks)
Employé 3: etc.... je pense que vous avez compris ^^ sinon dites le moi.
Le problème que je pense identifier c'est que si je raisonne de manière séquentielle (employé par employé) je ne suis pas sûr de trouver la bonne répartition puisque j'ai bloqué la répartition de l'employé 1. ( peut etre que je me trompe)
Il faudrait donc penser à une autre manière de faire ( si vous avez des propositions, je serais ravi)
Je vous remercie et j'ai hâte de vous lire !!
N'hésitez pas s'il vous manque des précisions
Les mots clés pour trouver de la littérature sur le sujet, ça ressemble à 'optimisation planning production' ; tu vas trouver plein de publicités, parce que c'est un problème compliqué, et il y a beaucoup de business autour de ces questions.
Tu peux faire ton planning demi-heure par demi-heure.
Pour la Première demi-heure, tu sais que tu ne peux pas faire d'assemblage, puisqu'il n'y a aucun steack de cuit. Tu regardes les taches où il y a le plus de besoin par rapport au nombre de personnes capables de faire ces taches. Et tu mets un max d'individu sur ces taches les plus 'demandeuses' de temps.
Et tu répartis les ressources ainsi...
En gardant en tête que certaines taches sont bloquantes. Si tu ne mets pas beaucoup de personnes sur la cuisson, tu ne pourra commencer l'assemblage que très tard. Et ça risque de bloquer.
Faire cette planification rigoureusement, c'est compliqué. Et c'est pour ça qu'il y a des outils commerciaux sur le créneau.
Tu dois pouvoir faire quelques plannings type. Sauf si les employés présents changent trop d'un jour sur l'autre,