{"id":133,"date":"2009-07-16T12:16:08","date_gmt":"2009-07-16T10:16:08","guid":{"rendered":"http:\/\/wp1.fredptitgars.net\/index.php\/2009\/07\/16\/methode-de-balas-hammer\/"},"modified":"2009-07-16T12:16:08","modified_gmt":"2009-07-16T10:16:08","slug":"methode-de-balas-hammer","status":"publish","type":"post","link":"https:\/\/fredptitgars.ovh\/?p=133","title":{"rendered":"Methode de Balas-Hammer"},"content":{"rendered":"

M\u00e9thode<\/h2>\n

On calcule pour chaque rang\u00e9e, ligne ou colonne, la diff\u00e9rence entre le co\u00fbt le plus petit avec celui qui lui est imm\u00e9diatement sup\u00e9rieur. Affecter \u00e0 la relation de co\u00fbt le plus petit correspondant \u00e0 la rang\u00e9e pr\u00e9sentant la diff\u00e9rence maximale la quantit\u00e9 la plus \u00e9lev\u00e9e possible. Ce qui sature une ligne ou une colonne. Reprendre le processus jusqu’\u00e0 ce que toutes les rang\u00e9es soient satur\u00e9es.<\/p>\n

Algorithme<\/strong>
\n
Dl: diff\u00e9rence entre le co\u00fbt mini et celui imm\u00e9diatement sup\u00e9rieur sur une ligne
\n
Dc: diff\u00e9rence entre le co\u00fbt mini et celui imm\u00e9diatement sup\u00e9rieur sur une colonne<\/p>\n

    \n
  1. Calculer les diff\u00e9rences Dl et Dc pour chaque ligne et colonnes<\/li>\n
  2. S\u00e9lectionner la ligne ou la colonne ayant le Dl ou Dc maximum<\/li>\n
  3. Choisir dans cette ligne ou colonne le co\u00fbt le plus faible<\/li>\n
  4. Attribuer \u00e0 la relation (i,j) correspondante le maximum possible de mati\u00e8re transportable de fa\u00e7on \u00e0 saturer soit la destination soit la disponibilit\u00e9<\/li>\n
  5. calculer la quantit\u00e9 r\u00e9siduelle soit demande soit en disponibilit\u00e9.<\/li>\n
  6. Eliminer la ligne ou la colonne ayant sa disponibilit\u00e9 ou demande satisfaite<\/li>\n
  7. SI nombre de lignes ou colonnes> 2 retour en 2. SINON affecter les quantit\u00e9s restantes aux liaisons
    \n
    FIN<\/li>\n<\/ol>\n

    Exemple:
    \nSch\u00e9ma de d\u00e9part:<\/p>\n

    \"sch\u00e9ma
    sch\u00e9ma initial<\/strong><\/figcaption><\/figure>\n

    vous avez 3 points de production A1 A2 et A3 et 4 points de livraisons : D1 D2 D3 D4 <\/p>\n

    Tableaux des co\u00fbts de chaque trajet:<\/p>\n\n\n\n\n\n\n\n\n
    <\/td>\nD1<\/td>\nD2<\/td>\nD3<\/td>\nD4<\/td>\nai<\/strong><\/td>\n\u0394i<\/strong><\/td>\n<\/tr>\n
    A1<\/td>\n11<\/td>\n12<\/td>\n10<\/td>\n10<\/td>\n60<\/strong><\/td>\n1<\/strong><\/td>\n<\/tr>\n
    A2<\/td>\n17<\/td>\n16<\/td>\n15<\/td>\n18<\/td>\n30<\/strong><\/td>\n1<\/strong><\/td>\n<\/tr>\n
    A3<\/td>\n19<\/td>\n21<\/td>\n20<\/td>\n22<\/td>\n90<\/strong><\/td>\n1<\/strong><\/td>\n<\/tr>\n
    bj<\/strong><\/td>\n50<\/strong><\/td>\n75<\/strong><\/td>\n30<\/strong><\/td>\n25<\/strong><\/td>\n180<\/strong><\/td>\n<\/td>\n<\/tr>\n
    \u0394c<\/strong><\/td>\n6<\/strong><\/td>\n4<\/strong><\/td>\n5<\/strong><\/td>\n8<\/strong><\/td>\n<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    A1 vers D2 coute 12 unit\u00e9s (par exemple 8 mille francs)
    \n
    aj correspond aux capacit\u00e9 de production
    \n
    bj correspond aux besoins<\/p>\n

    on calcule les deltaL et deltaC donc les regrets
    \n
    les deltats:
    \n
    \u0394c= diff\u00e9rence entre les deux valeurs minimums<\/p>\n

    \u0394cD1=17-11
    \n
    \u0394cD2=16-12
    \n
    \u0394cD3=15-10
    \n
    \u0394cD4=18-10<\/p>\n

    La meilleure solution coute 10 mais si je prends la seconde meilleure solution, cela ne me coutera que 11
    \n
    \u0394i= 11-10 sur la ligne 1
    \n
    donc le second choix me fait perdre 1 <\/p>\n

    Le choix se fait en prenant le plus gros de tous les delta, Ligne et colonne.<\/p>\n

    Dans cet exemple, c’est D4 avec un delta de 8.
    \n
    Maintenant on sature D4. D4 a besoin de 25 unit\u00e9. On choisi la ligne avec le deltaL le plus haut. Ici il sont tous \u00e9gaux a 1 on prend au hasard,
    \npar exemple, je mets 25 unit\u00e9s sur A1 D4, on a satur\u00e9 D4
    \nA1 qui produit 60 ne compte plus que pour 60-25=35
    \net on recalcule les deltas<\/p>\n

    ce qui nous donne ce nouveau tableau:<\/p>\n\n\n\n\n\n\n\n\n
    <\/td>\nD1<\/td>\nD2<\/td>\nD3<\/td>\nD4<\/td>\nai<\/strong><\/td>\n\u0394i<\/strong><\/td>\n<\/tr>\n
    A1<\/td>\n11<\/td>\n12<\/td>\n10<\/td>\n <\/td>\n35<\/strong><\/td>\n1<\/strong><\/td>\n<\/tr>\n
    A2<\/td>\n17<\/td>\n16<\/td>\n15<\/td>\n <\/td>\n30<\/strong><\/td>\n1<\/strong><\/td>\n<\/tr>\n
    A3<\/td>\n19<\/td>\n21<\/td>\n20<\/td>\n <\/td>\n90<\/strong><\/td>\n1<\/strong><\/td>\n<\/tr>\n
    bj<\/strong><\/td>\n50<\/strong><\/td>\n75<\/strong><\/td>\n30<\/strong><\/td>\n <\/td>\n180<\/strong><\/td>\n<\/td>\n<\/tr>\n
    \u0394c<\/strong><\/td>\n6<\/strong><\/td>\n4<\/strong><\/td>\n5<\/strong><\/td>\n <\/td>\n<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\n\n\n\n\n\n
    <\/td>\nD1<\/td>\nD2<\/td>\nD3<\/td>\nD4<\/td>\nai<\/td>\n<\/tr>\n
    A1<\/td>\n <\/td>\n <\/td>\n <\/td>\n25 <\/td>\n <\/td>\n<\/tr>\n
    A2<\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n<\/tr>\n
    A3<\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    On recommence, on prend le plus grand delta (Ligne et colonne). C’est en D1 qui est \u00e9gale 6.
    \n
    On sature D1 avec le plus petit co\u00fbt qui est A1D1. A dispose encore de 35. On met 35 dans A1D1,
    \n
    On recalcule les delta<\/p>\n\n\n\n\n\n\n\n\n
    <\/td>\nD1<\/td>\nD2<\/td>\nD3<\/td>\nD4<\/td>\nai<\/strong><\/td>\n\u0394i<\/strong><\/td>\n<\/tr>\n
    A1<\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n<\/tr>\n
    A2<\/td>\n17<\/td>\n16<\/td>\n15<\/td>\n <\/td>\n30<\/strong><\/td>\n1<\/strong><\/td>\n<\/tr>\n
    A3<\/td>\n19<\/td>\n21<\/td>\n20<\/td>\n <\/td>\n90<\/strong><\/td>\n1<\/strong><\/td>\n<\/tr>\n
    bj<\/strong><\/td>\n15<\/strong><\/td>\n75<\/strong><\/td>\n30<\/strong><\/td>\n <\/td>\n180<\/strong><\/td>\n<\/td>\n<\/tr>\n
    \u0394c<\/strong><\/td>\n2<\/strong><\/td>\n5<\/strong><\/td>\n5<\/strong><\/td>\n <\/td>\n<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\n\n\n\n\n\n
    <\/td>\nD1<\/td>\nD2<\/td>\nD3<\/td>\nD4<\/td>\nai<\/td>\n<\/tr>\n
    A1<\/td>\n35<\/td>\n <\/td>\n <\/td>\n25 <\/td>\n <\/td>\n<\/tr>\n
    A2<\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n<\/tr>\n
    A3<\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    On recommence, on prend le plus grand deltat (Ligne, colonne). C’est en D2 qui est \u00e9gale \u00e0 5. On sature A2D2 qui est moins cher. A2 produit 30. On met 30 dans A2D2.<\/p>\n\n\n\n\n\n\n\n\n
    <\/td>\nD1<\/td>\nD2<\/td>\nD3<\/td>\nD4<\/td>\nai<\/strong><\/td>\n\u0394i<\/strong><\/td>\n<\/tr>\n
    A1<\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n<\/tr>\n
    A2<\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n<\/tr>\n
    A3<\/td>\n19<\/td>\n21<\/td>\n20<\/td>\n <\/td>\n90<\/strong><\/td>\n1<\/strong><\/td>\n<\/tr>\n
    bj<\/strong><\/td>\n15<\/strong><\/td>\n45<\/strong><\/td>\n30<\/strong><\/td>\n <\/td>\n180<\/strong><\/td>\n<\/td>\n<\/tr>\n
    \u0394c<\/strong><\/td>\n19<\/strong><\/td>\n21<\/strong><\/td>\n20<\/strong><\/td>\n <\/td>\n<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\n\n\n\n\n\n
    <\/td>\nD1<\/td>\nD2<\/td>\nD3<\/td>\nD4<\/td>\nai<\/td>\n<\/tr>\n
    A1<\/td>\n35<\/td>\n <\/td>\n <\/td>\n25 <\/td>\n <\/td>\n<\/tr>\n
    A2<\/td>\n <\/td>\n30<\/td>\n <\/td>\n <\/td>\n <\/td>\n<\/tr>\n
    A3<\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    Avec A3, il ne reste plus qu’a satur\u00e9 le moins cher, cela revient \u00e0 mettre les restes.
    \n
    D1 a encore besoin de 15, on lui donne
    \n
    D2 a besoin de 45, on lui donne
    \n
    D3 a besoin de 30, on lui donne
    \n
    et voil\u00e0 on a gagn\u00e9<\/em><\/p>\n

    solution final<\/strong><\/p>\n\n\n\n\n\n\n
    <\/td>\nD1<\/td>\nD2<\/td>\nD3<\/td>\nD4<\/td>\nai<\/td>\n<\/tr>\n
    A1<\/td>\n35<\/td>\n <\/td>\n <\/td>\n25 <\/td>\n <\/td>\n<\/tr>\n
    A2<\/td>\n <\/td>\n30<\/td>\n <\/td>\n <\/td>\n <\/td>\n<\/tr>\n
    A3<\/td>\n15<\/td>\n45<\/td>\n30<\/td>\n <\/td>\n <\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    Cout de la solution= 2945<\/p>\n

    optimisation des cycle<\/strong><\/p>\n

    Si nous avons un cycle on peut l’optimiser.<\/p>\n

    Sur ce graph:<\/p>\n

    \"graph
    graph \u00e0 optimiser<\/strong><\/figcaption><\/figure>\n

    on peut optimiser le cycle A2D3A3D4
    \n
    un cycle consiste a se retrouver au point de d\u00e9part en suivant un chemin
    \nOn prend le point de d\u00e9part et on ajoute un (+1) sur un axe. Du coup on enl\u00e8ve 1 (-1) sur le retour et +1 sur le 3e et -1 sur le quatri\u00e8me
    \nen faisant +1 -1 +1 -1, vous changez le cout si cela am\u00e9liore, vous continuez avec +2 -2 +2 -2 et ainsi de suite jusqu’\u00e0 disparition du cycle. Si cela n’am\u00e9liore PAS, vous faite -1 +1 -1 +1 et cela am\u00e9liore le cout obligatoirement et on traite tout les cycles<\/p>\n

    le stepping stone<\/p>\n

    Montrons que l’on peut am\u00e9liorer la solution de base obtenue.
    \n
    Supposons que l’on veuille transporter sur la liaison A1-D3, de co\u00fbt 10, une _ unit\u00e9. Nous avons alors:
    \n
    xA1D1-1=-11; xA3D1+1=19; xA3D3-1=-20; xA1D3+1=10;
    \n
    Co\u00fbt marginal Dx=-2 Nous gagnons de cette fa\u00e7on 2 unit\u00e9s.<\/p>\n

    On cr\u00e9e un cycle fictif en ajoutant un lien entre A1 et D3. On obtient le cycle A1D1A3D3. Nous avons un cycle et on peux optimiser<\/p>\n","protected":false},"excerpt":{"rendered":"

    M\u00e9thode On calcule pour chaque rang\u00e9e, ligne ou colonne, la diff\u00e9rence entre le co\u00fbt le plus petit avec celui qui lui est imm\u00e9diatement sup\u00e9rieur. Affecter \u00e0 la relation de co\u00fbt le plus petit correspondant \u00e0 la rang\u00e9e pr\u00e9sentant la diff\u00e9rence maximale la quantit\u00e9 la plus \u00e9lev\u00e9e possible. Ce qui sature une ligne ou une colonne. […]<\/p>\n","protected":false},"author":2,"featured_media":131,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[],"class_list":["post-133","post","type-post","status-publish","format-standard","has-post-thumbnail","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\/133","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=133"}],"version-history":[{"count":0,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/posts\/133\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/media\/131"}],"wp:attachment":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=133"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=133"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=133"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}