Methode de Balas-Hammer

Méthode

On calcule pour chaque rangée, ligne ou colonne, la différence entre le coût le plus petit avec celui qui lui est immédiatement supérieur. Affecter à la relation de coût le plus petit correspondant à la rangée présentant la différence maximale la quantité la plus élevée possible. Ce qui sature une ligne ou une colonne. Reprendre le processus jusqu’à ce que toutes les rangées soient saturées.

Algorithme
Dl : différence entre le coût mini et celui immédiatement supérieur sur une ligne
Dc : différence entre le coût mini et celui immédiatement supérieur sur une colonne

1. Calculer les différences Dl et Dc pour chaque ligne et colonnes
2. Sélectionner la ligne ou la colonne ayant le Dl ou Dc maximum
3. Choisir dans cette ligne ou colonne le coût le plus faible
4. Attribuer à la relation (i,j) correspondante le maximum possible de matière transportable de façon à saturer soit la destination soit la disponibilité
5. calculer la quantité résiduelle soit demande soit en disponibilité.
6. Eliminer la ligne ou la colonne ayant sa disponibilité ou demande satisfaite
7. SI nombre de lignes ou colonnes> 2 retour en 2. SINON affecter les quantités restantes aux liaisons
   FIN

Exemple :
Schéma de départ :

vous avez 3 points de production A1 A2 et A3 et 4 points de livraisons : D1 D2 D3 D4

Tableaux des coûts de chaque trajet :

A1 vers D2 coute 12 unités (par exemple 8 mille francs)
aj correspond aux capacité de production
bj correspond aux besoins

on calcule les deltaL et deltaC donc les regrets
les deltats :
Δc= différence entre les deux valeurs minimums

ΔcD1=17-11
ΔcD2=16-12
ΔcD3=15-10
ΔcD4=18-10

La meilleure solution coute 10 mais si je prends la seconde meilleure solution, cela ne me coutera que 11
Δi= 11-10 sur la ligne 1
donc le second choix me fait perdre 1

Le choix se fait en prenant le plus gros de tous les delta, Ligne et colonne.

Dans cet exemple, c’est D4 avec un delta de 8.
Maintenant on sature D4. D4 a besoin de 25 unité. On choisi la ligne avec le deltaL le plus haut. Ici il sont tous égaux a 1 on prend au hasard,
par exemple, je mets 25 unités sur A1 D4, on a saturé D4
A1 qui produit 60 ne compte plus que pour 60-25=35
et on recalcule les deltas

ce qui nous donne ce nouveau tableau :

On recommence, on prend le plus grand delta (Ligne et colonne). C’est en D1 qui est égale 6.
On sature D1 avec le plus petit coût qui est A1D1. A dispose encore de 35. On met 35 dans A1D1,
On recalcule les delta

On recommence, on prend le plus grand deltat (Ligne, colonne). C’est en D2 qui est égale à 5. On sature A2D2 qui est moins cher. A2 produit 30. On met 30 dans A2D2.

Avec A3, il ne reste plus qu’a saturé le moins cher, cela revient à mettre les restes.
D1 a encore besoin de 15, on lui donne
D2 a besoin de 45, on lui donne
D3 a besoin de 30, on lui donne
et voilà on a gagné

solution final

Cout de la solution= 2945

optimisation des cycle

Si nous avons un cycle on peut l’optimiser.

Sur ce graph :

on peut optimiser le cycle A2D3A3D4
un cycle consiste a se retrouver au point de départ en suivant un chemin
On prend le point de départ et on ajoute un (+1) sur un axe. Du coup on enlève 1 (-1) sur le retour et +1 sur le 3e et -1 sur le quatrième
en faisant +1 -1 +1 -1, vous changez le cout si cela améliore, vous continuez avec +2 -2 +2 -2 et ainsi de suite jusqu’à disparition du cycle. Si cela n’améliore PAS, vous faite -1 +1 -1 +1 et cela améliore le cout obligatoirement et on traite tout les cycles

le stepping stone

Montrons que l’on peut améliorer la solution de base obtenue.
Supposons que l’on veuille transporter sur la liaison A1-D3, de coût 10, une _ unité. Nous avons alors :
xA1D1-1=-11 ; xA3D1+1=19 ; xA3D3-1=-20 ; xA1D3+1=10 ;
Coût marginal Dx=-2 Nous gagnons de cette façon 2 unités.

On crée un cycle fictif en ajoutant un lien entre A1 et D3. On obtient le cycle A1D1A3D3. Nous avons un cycle et on peux optimiser