{"id":134,"date":"2009-07-21T13:22:37","date_gmt":"2009-07-21T11:22:37","guid":{"rendered":"http:\/\/wp1.fredptitgars.net\/index.php\/2009\/07\/21\/probleme-daffectation\/"},"modified":"2009-07-21T13:22:37","modified_gmt":"2009-07-21T11:22:37","slug":"probleme-daffectation","status":"publish","type":"post","link":"https:\/\/fredptitgars.ovh\/?p=134","title":{"rendered":"Probl\u00e8me d’affectation"},"content":{"rendered":"

Affecter 4 personnes \u00e0 4 taches comment faire?
\nSoit 4 personnes A, B,C,D
\net 4 taches a,b,c,d<\/p>\n

La m\u00e9thode hongroise<\/strong><\/p>\n

tableau repr\u00e9sentant les coefficients de pr\u00e9f\u00e9rence des diff\u00e9rentes personnes:<\/p>\n\n\n\n\n\n\n\n\n
<\/td>\nA<\/td>\nB<\/td>\nC<\/td>\nD<\/td>\nE<\/td>\n<\/tr>\n
a<\/td>\n9<\/td>\n6<\/td>\n7<\/td>\n3<\/td>\n4<\/td>\n<\/tr>\n
b<\/td>\n2<\/td>\n1<\/td>\n9<\/td>\n1<\/td>\n8<\/td>\n<\/tr>\n
c<\/td>\n4<\/td>\n3<\/td>\n2<\/td>\n2<\/td>\n7<\/td>\n<\/tr>\n
d<\/td>\n9<\/td>\n1<\/td>\n8<\/td>\n8<\/td>\n3<\/td>\n<\/tr>\n
e<\/td>\n1<\/td>\n7<\/td>\n8<\/td>\n9<\/td>\n5<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

la personne ‘a’ veut vraiment aller sur le poste A \u00e9ventuellement C voir B mais ne veut pas aller en E ou D, etc…<\/p>\n

la m\u00e9thode hongroise est que c’est un algorithme de minimisation donc la premi\u00e8re \u00e9tape est de transformer la formulation du probl\u00e8me en introduisant _ la notion de regret.
\n
Le regret est \u00e9gal au max moins chaque note sur tout le tableau.
\n
Exemple de la ligne 1
\n
Le max \u00e9gale 9
\n
Les valeur d’origine: 9 6 7 3 4
\n
on fait 9- a chaque valeur, ce qui nous donne:<\/p>\n\n\n\n\n\n\n\n\n
<\/td>\nA<\/td>\nB<\/td>\nC<\/td>\nD<\/td>\nE<\/td>\n<\/tr>\n
a<\/td>\n9-9<\/td>\n9-6<\/td>\n9-7<\/td>\n9-3<\/td>\n9-4<\/td>\n<\/tr>\n
b<\/td>\n9-2<\/td>\n9-1<\/td>\n9-9<\/td>\n9-1<\/td>\n9-8<\/td>\n<\/tr>\n
c<\/td>\n9-4<\/td>\n9-3<\/td>\n9-2<\/td>\n9-2<\/td>\n9-7<\/td>\n<\/tr>\n
d<\/td>\n9-9<\/td>\n9-1<\/td>\n9-8<\/td>\n9-8<\/td>\n9-3<\/td>\n<\/tr>\n
e<\/td>\n9-1<\/td>\n9-7<\/td>\n9-8<\/td>\n9-9<\/td>\n9-5<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Ce qui nous donne le tableau final:<\/p>\n\n\n\n\n\n\n\n\n
<\/td>\nA<\/td>\nB<\/td>\nC<\/td>\nD<\/td>\nE<\/td>\n<\/tr>\n
a<\/td>\n0<\/td>\n3<\/td>\n2<\/td>\n6<\/td>\n5<\/td>\n<\/tr>\n
b<\/td>\n7<\/td>\n8<\/td>\n0<\/td>\n8<\/td>\n1<\/td>\n<\/tr>\n
c<\/td>\n5<\/td>\n6<\/td>\n7<\/td>\n7<\/td>\n2<\/td>\n<\/tr>\n
d<\/td>\n0<\/td>\n8<\/td>\n1<\/td>\n1<\/td>\n6<\/td>\n<\/tr>\n
e<\/td>\n8<\/td>\n2<\/td>\n1<\/td>\n0<\/td>\n4<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Ensuite pour les colonnes, il faut avoir un 0 dans chaque colonne:
\n
Colonne B, on enl\u00e8ve 2 (le min sur cette colonne)
\n
Colonne E, on enl\u00e8ve 1 (le min sur cette colonne)<\/p>\n\n\n\n\n\n\n\n\n\n
<\/td>\nA<\/td>\nB<\/td>\nC<\/td>\nD<\/td>\nE<\/td>\n<\/tr>\n
a<\/td>\n0<\/td>\n3<\/td>\n2<\/td>\n6<\/td>\n5<\/td>\n<\/tr>\n
b<\/td>\n7<\/td>\n8<\/td>\n0<\/td>\n8<\/td>\n1<\/td>\n<\/tr>\n
c<\/td>\n5<\/td>\n6<\/td>\n7<\/td>\n7<\/td>\n2<\/td>\n<\/tr>\n
d<\/td>\n0<\/td>\n8<\/td>\n1<\/td>\n1<\/td>\n6<\/td>\n<\/tr>\n
e<\/td>\n8<\/td>\n2<\/td>\n1<\/td>\n0<\/td>\n4<\/td>\n<\/td>\n<\/tr>\n
vi<\/td>\n0<\/td>\n2<\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\n\n\n\n\n\n\n\n
<\/td>\nA<\/td>\nB<\/td>\nC<\/td>\nD<\/td>\nE<\/td>\n<\/tr>\n
a<\/td>\n0<\/td>\n1<\/td>\n2<\/td>\n6<\/td>\n4<\/td>\n<\/tr>\n
b<\/td>\n7<\/td>\n6<\/td>\n0<\/td>\n8<\/td>\n0<\/td>\n<\/tr>\n
c<\/td>\n5<\/td>\n4<\/td>\n7<\/td>\n7<\/td>\n1<\/td>\n<\/tr>\n
d<\/td>\n0<\/td>\n6<\/td>\n1<\/td>\n1<\/td>\n5<\/td>\n<\/tr>\n
e<\/td>\n8<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n3<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Vi correspond au minimum de chaque colonne.<\/p>\n

Idem pour les lignes:<\/p>\n\n\n\n\n\n\n\n\n
<\/td>\nA<\/td>\nB<\/td>\nC<\/td>\nD<\/td>\nE<\/td>\nui<\/td>\n<\/tr>\n
a<\/td>\n0<\/td>\n1<\/td>\n2<\/td>\n6<\/td>\n4<\/td>\n0<\/td>\n<\/tr>\n
b<\/td>\n7<\/td>\n6<\/td>\n0<\/td>\n8<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n
c<\/td>\n5<\/td>\n4<\/td>\n7<\/td>\n7<\/td>\n1<\/td>\n1<\/td>\n<\/tr>\n
d<\/td>\n0<\/td>\n6<\/td>\n1<\/td>\n1<\/td>\n5<\/td>\n0<\/td>\n<\/tr>\n
e<\/td>\n8<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n3<\/td>\n0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\n\n\n\n\n\n\n\n
<\/td>\nA<\/td>\nB<\/td>\nC<\/td>\nD<\/td>\nE<\/td>\n<\/tr>\n
a<\/td>\n0<\/td>\n1<\/td>\n2<\/td>\n6<\/td>\n4<\/td>\n<\/tr>\n
b<\/td>\n7<\/td>\n6<\/td>\n0<\/td>\n8<\/td>\n0<\/td>\n<\/tr>\n
c<\/td>\n4<\/td>\n3<\/td>\n6<\/td>\n6<\/td>\n0<\/td>\n<\/tr>\n
d<\/td>\n0<\/td>\n6<\/td>\n1<\/td>\n1<\/td>\n5<\/td>\n<\/tr>\n
e<\/td>\n8<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n3<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Vi correspond au minimum de chaque colonne.<\/p>\n

Au final on doit avoir un 0 pour chaque ligne et chaque colonne<\/p>\n

Algorithme d’affectation des z\u00e9ros.<\/em>
\n
Consid\u00e9rer les lignes ayant le nombre minimum de z\u00e9ro (lignes a, c, d, dans notre exemple comportent un z\u00e9ro)<\/p>\n

    \n
  1. Choisir la ligne ayant un nombre minimum de z\u00e9ros, affecter le z\u00e9ro \u00e0 la liaison correspondante. Le z\u00e9ro est dit encadr\u00e9.
    \n
    \tex:Ligne, a, et affectons le z\u00e9ro correspondant \u00e0 la liaison aA, z\u00e9ro (aA) encadr\u00e9.<\/li>\n
  2. Du fait ce choix, il n’est plus possible d’utiliser le(s) z\u00e9ro(s), s’il en existe, de la colonne ou de la ligne correspondant \u00e0 ce z\u00e9ro encadr\u00e9 nous dirons que ce(s) z\u00e9ro(s) est(sont barr\u00e9(s). ex: z\u00e9ro (dA). <\/li>\n
  3. Retour en 1 tant qu’il existe des z\u00e9ros non encadr\u00e9s ou non barr\u00e9s.<\/li>\n<\/ol>\n

    Pour des raison d’affichage:
    \n– les valeurs encadr\u00e9e sont remplac\u00e9 par du gras<\/p>\n

    Ligne a: aA, z\u00e9ro (aA) encadr\u00e9
    \n
    Les 0 de la ligne a et de la colonne A sont barr\u00e9<\/p>\n

    <\/p>\n\n\n\n\n\n\n\n\n
    <\/td>\nA<\/td>\nB<\/td>\nC<\/td>\nD<\/td>\nE<\/td>\n<\/tr>\n
    a<\/td>\n0<\/strong> <\/td>\n1<\/td>\n2<\/td>\n6<\/td>\n4<\/td>\n<\/tr>\n
    b<\/td>\n7<\/td>\n6<\/td>\n0<\/td>\n8<\/td>\n0<\/td>\n<\/tr>\n
    c<\/td>\n4<\/td>\n3<\/td>\n6<\/td>\n6<\/td>\n0<\/td>\n<\/tr>\n
    d<\/td>\n$\\not0<\/em>$<\/td>\n6<\/td>\n1<\/td>\n1<\/td>\n5<\/td>\n<\/tr>\n
    e<\/td>\n8<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n3<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
    \n

    Ligne c : cE, z\u00e9ro (cE) encadr\u00e9\nLes 0 de la ligne c et de la colonne E sont barr\u00e9<\/p>\n\n\n\n\n\n\n\n\n
    <\/td>\nA<\/td>\nB<\/td>\nC<\/td>\nD<\/td>\nE<\/td>\n<\/tr>\n
    a<\/td>\n0<\/strong><\/td>\n1<\/td>\n2<\/td>\n6<\/td>\n4<\/td>\n<\/tr>\n
    b<\/td>\n7<\/td>\n6<\/td>\n0<\/td>\n8<\/td>\n0B<\/td>\n<\/tr>\n
    c<\/td>\n4<\/td>\n3<\/td>\n6<\/td>\n6<\/td>\n0<\/strong><\/td>\n<\/tr>\n
    d<\/td>\n$\\not0<\/em>$<\/td>\n6<\/td>\n1<\/td>\n1<\/td>\n5<\/td>\n<\/tr>\n
    e<\/td>\n8<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n3<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
    \n

    Ligne b: bC, z\u00e9ro (bC) encadr\u00e9\n
    les 0 de la ligne b et de la colonne C sont barr\u00e9<\/p>\n\n\n\n\n\n\n\n\n
    <\/td>\nA<\/td>\nB<\/td>\nC<\/td>\nD<\/td>\nE<\/td>\n<\/tr>\n
    a<\/td>\n0<\/strong><\/td>\n1<\/td>\n2<\/td>\n6<\/td>\n4<\/td>\n<\/tr>\n
    b<\/td>\n7<\/td>\n6<\/td>\n0<\/strong><\/td>\n8<\/td>\n$\\not0<\/em>$<\/td>\n<\/tr>\n
    c<\/td>\n4<\/td>\n3<\/td>\n6<\/td>\n6<\/td>\n0<\/strong><\/td>\n<\/tr>\n
    d<\/td>\n$\\not0<\/em>$<\/td>\n6<\/td>\n1<\/td>\n1<\/td>\n5<\/td>\n<\/tr>\n
    e<\/td>\n8<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n3<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
    \n

    Ligne e: eB, z\u00e9ro (eB) encadr\u00e9\n
    Les 0 de la ligne e et de la colonne B sont barr\u00e9<\/p>\n\n\n\n\n\n\n\n\n
    <\/td>\nA<\/td>\nB<\/td>\nC<\/td>\nD<\/td>\nE<\/td>\n<\/tr>\n
    a<\/td>\n0<\/strong><\/td>\n1<\/td>\n2<\/td>\n6<\/td>\n4<\/td>\n<\/tr>\n
    b<\/td>\n7<\/td>\n6<\/td>\n0<\/strong><\/td>\n8<\/td>\n$\\not0<\/em>$<\/td>\n<\/tr>\n
    c<\/td>\n4<\/td>\n3<\/td>\n6<\/td>\n6<\/td>\n0<\/strong><\/td>\n<\/tr>\n
    d<\/td>\n$\\not0<\/em>$<\/td>\n6<\/td>\n1<\/td>\n1<\/td>\n5<\/td>\n<\/tr>\n
    e<\/td>\n8<\/td>\n0<\/strong><\/td>\n1<\/td>\n$\\not0<\/em>$<\/td>\n3<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    <\/math><\/p>\n","protected":false},"excerpt":{"rendered":"

    Affecter 4 personnes \u00e0 4 taches comment faire? Soit 4 personnes A, B,C,D et 4 taches a,b,c,d La m\u00e9thode hongroise tableau repr\u00e9sentant les coefficients de pr\u00e9f\u00e9rence des diff\u00e9rentes personnes: A B C D E a 9 6 7 3 4 b 2 1 9 1 8 c 4 3 2 2 7 d 9 1 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[],"class_list":["post-134","post","type-post","status-publish","format-standard","hentry","category-rcp101-recherche-operationnelle-et-aide-a-la-decision"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/posts\/134","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=134"}],"version-history":[{"count":0,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/posts\/134\/revisions"}],"wp:attachment":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=134"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=134"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=134"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}