Bonjour, Est-il possible de prendre en compte des préférences par exemple des employés d'une tâche par rapport à une autre (en pondérant les arêtes entre les employés et les tâches d'une certaine manière) et/ou de prendre en compte le fait que plusieurs personnes peuvent faire une seul tâche (en modifiant la pondération entre les tâches et le puit) ? De plus, qu'est-ce qui nous dis que la pondération a posteriori (poids affecté aux arcs bleus) soit égale à 1 et pas une valeur inférieur ? Merci d'avance pour votre réponse.
+ Prendre en compte les préférences des employés : je ne crois pas que ça soit directement possible avec ce modèle. Par contre pour prendre en compte des choix, voir mes deux vidéos sur les mariages stables (le contexte est un peu différent). Il faudrait peut-être utiliser un mix des deux. + Prendre en compte le fait que des personnes ne peuvent faire qu'une tâche : à la fin de l'algorithme, une personne sera affectée à une tâche ou à 0 tâche, c'est un couplage. De plus si une personne P n'a les compétences que pour faire une tâche T (et aucune autre), il suffit, au départ, de mettre une arête entre cette personne P et T, sans autre arête pour P. + Pour ce que vous appelez la pondération a postériori, ça s'appelle la quantité de flot qui circule sur l'arc. Voir ma vidéo sur l'algorithme de Ford-Fulkerson : l'idée étant que lorsqu'on utilise une chaine améliorante, on améliore au maximum de la capacité de cette chaine (si on peut améliorer de 1, on ne va pas simplement améliorer de 0,5 par exemple).
s'il vous plait j'ai une question , dans la minute 4:00 pourquoi on a pas choisit une autre chaine améliorante car il y on a si on prend l'arc en inverse , plus precisement la chaine suivante : s-->Lola-->T1-->Fred-->T2-->t !
Bonjour monsieur, Tout d'abord merci pour votre vidéo ! Peut t'on dire qu'un problème de couplage max est un problème de flot max si l'on impose à chaque arc du groupe A vers le groupe B une capacité de 1 ? Si c'est le cas nous pouvons résoudre ce problème avec l'algorithme de ford-fulkerson non ? Bien à vous.
Bonjour. Oui ici on traite effectivement un problème de couplage de taille maximale grâce à un flot max. (que 'on peut trouver avec l'algorithme de F&F) en imposant les capacités données dans la vidéo. Ici je traite l'affectation de personnes à des travaux pour donner une idée d'application pratique mais cela revient à chercher un couplage. Attention, cela ne marche que grâce au fait que l'on est dans un graphe biparti avec tous les arêtes qui sont entre les sommets de A et de B.
Etant données les contraintes décrites : + Il n'est pas toujours possible d'exécuter toutes les tâches. + Il n'est pas toujours possible de donner une tâche à faire à chaque employé. Cela traduit tout simplement que les contraintes sont trop dures. Mais, en passant par le flots, on peut maximiser le nombre de tâches exécutées, ce qui était l'objectif.
![[RévisionsBac.com] - Coloriage d'un graphe](http://i.ytimg.com/vi/hzDxMDNcBVY/mqdefault.jpg)
Force a oit lolo
Bonjour,
Est-il possible de prendre en compte des préférences par exemple des employés d'une tâche par rapport à une autre (en pondérant les arêtes entre les employés et les tâches d'une certaine manière) et/ou de prendre en compte le fait que plusieurs personnes peuvent faire une seul tâche (en modifiant la pondération entre les tâches et le puit) ? De plus, qu'est-ce qui nous dis que la pondération a posteriori (poids affecté aux arcs bleus) soit égale à 1 et pas une valeur inférieur ?
Merci d'avance pour votre réponse.
+ Prendre en compte les préférences des employés : je ne crois pas que ça soit directement possible avec ce modèle. Par contre pour prendre en compte des choix, voir mes deux vidéos sur les mariages stables (le contexte est un peu différent). Il faudrait peut-être utiliser un mix des deux.
+ Prendre en compte le fait que des personnes ne peuvent faire qu'une tâche : à la fin de l'algorithme, une personne sera affectée à une tâche ou à 0 tâche, c'est un couplage. De plus si une personne P n'a les compétences que pour faire une tâche T (et aucune autre), il suffit, au départ, de mettre une arête entre cette personne P et T, sans autre arête pour P.
+ Pour ce que vous appelez la pondération a postériori, ça s'appelle la quantité de flot qui circule sur l'arc. Voir ma vidéo sur l'algorithme de Ford-Fulkerson : l'idée étant que lorsqu'on utilise une chaine améliorante, on améliore au maximum de la capacité de cette chaine (si on peut améliorer de 1, on ne va pas simplement améliorer de 0,5 par exemple).
s'il vous plait j'ai une question , dans la minute 4:00 pourquoi on a pas choisit une autre chaine améliorante car il y on a si on prend l'arc en inverse , plus precisement la chaine suivante : s-->Lola-->T1-->Fred-->T2-->t !
Vous ne pouvez prendre l'arc T1
c'est compris , elle est clair maintenant , merci beaucoup vraiment !
vous êtes le meilleur !
@@a_la_decouverte_des_graphes
Bonjour monsieur,
Tout d'abord merci pour votre vidéo !
Peut t'on dire qu'un problème de couplage max est un problème de flot max si l'on impose à chaque arc du groupe A vers le groupe B une capacité de 1 ?
Si c'est le cas nous pouvons résoudre ce problème avec l'algorithme de ford-fulkerson non ?
Bien à vous.
Bonjour.
Oui ici on traite effectivement un problème de couplage de taille maximale grâce à un flot max. (que 'on peut trouver avec l'algorithme de F&F) en imposant les capacités données dans la vidéo. Ici je traite l'affectation de personnes à des travaux pour donner une idée d'application pratique mais cela revient à chercher un couplage.
Attention, cela ne marche que grâce au fait que l'on est dans un graphe biparti avec tous les arêtes qui sont entre les sommets de A et de B.
À la découverte des graphes Merci beaucoup pour votre réponse ! :)
Il reste encore deux tâches non affectées et un employé sans la moindre tâche !
Je ne comprends pas en quoi le problème est résolu !?
Etant données les contraintes décrites :
+ Il n'est pas toujours possible d'exécuter toutes les tâches.
+ Il n'est pas toujours possible de donner une tâche à faire à chaque employé.
Cela traduit tout simplement que les contraintes sont trop dures. Mais, en passant par le flots, on peut maximiser le nombre de tâches exécutées, ce qui était l'objectif.
@@a_la_decouverte_des_graphes ah d'accord, merci pour ces précisions !