Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Chapitre 7 tg Chapitre Problèmes d ? a ?ectation Module Recherche Opérationnelle ème Année Ingénieur Préparé par Mr A SACI Année universitaire Chapitre Chapitre Problèmes d ? a ?ectation Introduction Le problème d ? a ?ectation est souvent présenté sous l

Chapitre Problèmes d ? a ?ectation Module Recherche Opérationnelle ème Année Ingénieur Préparé par Mr A SACI Année universitaire Chapitre Chapitre Problèmes d ? a ?ectation Introduction Le problème d ? a ?ectation est souvent présenté sous la forme suivante Un chef de projet veut a ?ecter n ? ouvriers à la réalisation de n ? t? ches di ?érentes de façon à minimiser le temps de réalisation de toutes les t? ches à la fois Le problème sera donc la recherche d ? une a ?ectation minimale des n ? ouvriers aux n ? t? ches Ce problème peut être représenté par le graphe biparti G X X U suivant O? X représente l ? ensemble des ouvriers X représente l ? ensemble des t? ches U est l ? ensemble des arêtes o? les valeurs des arêtes représentent le temps mis par chaque ouvrier pour réaliser chaque t? che dij durée de réalisation de la t? che j ? par l ? ouvrier i ? Ouvrier Ouvrier Ouvrier i i d d j d d dij T? che T? che j T? che j Ouvrier n n dnn n T? che n Description du problème d ? a ?ectation On considère les deux ensembles suivants P p p ? pn ensemble de personnes et T t t ? tm ensemble de t? ches Il s ? agit de répartir les di ?érentes t? ches entre les di ?érentes personnes de façon optimale en tenant compte des préférences de chaque personne aux di ?érentes t? ches allant de la satisfaction générale à la satisfaction individuelle La préférence de chaque personne pi ? à la t? che tj ? est représentée par un nombre noté aij ? qui peut correspondre à un temps un rendement un coût un pro ?t ? etc Soit G X X U le graphe biparti correspondant à ce problème o? X P est l ? ensemble de personnes X T est l ? ensemble de t? ches ?a a a j a m a a a j a m U pi tj i ? n et j ? m est l ? ensemble reliant les sommets de P aux sommets de T des arêtes A a i a i a ij a im Le problème sera ainsi modélisé par une matrice A aij appelée matrice d ? a ?ectation ? a n a n a nj a nm Résolution du problème d ? a ?ectation par la méthode Hongroise La recherche d ? une a ?ectation optimale maximale ou minimale par la méthode hongroise est basée sur la notion de zéros indépendants dans une matrice carrée Dé ?nition ? Zéros indépendants on appelle zéros indépendants les zéros qui n ? appartiennent ni à la même ligne ni à la même colonne d ? une matrice carrée Département d ? Informatique Université de BATNA Page CChapitre Problèmes d ? a ?ectation Module Recherche Opérationnelle ème Année Ingénieur Préparé par Mr A SACI Année universitaire Exemple Soit