title: Algorithme de Balas-Hammer
text: # Algorithme de Balas-Hammer
  
  L’algorithme de Balas-Hammer, aussi appelé méthode des différences maximales ou méthode des regrets, est un heuristique permettant d'optimiser un programme de transport (cas particulier d'un problème d'optimisation linéaire).
  
  Le but de cet algorithme est d'assurer les transports à moindre coût.
  
  ## Principe
  
  À partir d'une matrice des coûts de transports entre sources et destinataires :
  
  * Calculer pour chaque ligne et chaque colonne la différence entre le coût le plus faible et le coût immédiatement supérieur. Cette différence est appelée "regret".
  * Choisir l'affectation correspondant à la rangée présentant le regret maximum (lignes et colonnes confondues), pour remplir une matrice de transports.
  * Réitérer le processus.
  
  ## Exemple
  
  ### Données initiales
  
  Tableau représentant les coûts entre des sources et des destinataires, ainsi que les stocks disponibles pour les sources et les demandes des destinataires :
  
  Coûts / Besoins / Stocks :
  
  | Sources/Destinataires | 1 | 2 | 3 | 4 | 5 | Stocks |
  | - | - | - | - | - | - | - |
  | 1 | 10 | 6 | 3 | 5 | 25 | 49 |
  | 2 | 5 | 2 | 6 | 12 | 5 | 30 |
  | Demandes | 15 | 20 | 5 | 25 | 14 |
  
  ### Calcul des Regrets
  
  Coûts / Besoins / Stocks / Regrets :
  
  | Sources/Destinataires | 1 | 2 | 3 | 4 | 5 | Stocks | Regrets |
  | - | - | - | - | - | - | - | - |
  | 1 | 10 | 6 | 3 | 5 | 25 | 49 | 5-3=2 |
  | 2 | 5 | 2 | 6 | 12 | 5 | 30 | 5-2=3 |
  | Demandes | 15 | 20 | 5 | 25 | 14 |
  | Regrets | 10-5=5 | 6-2=4 | 6-3=3 | 12-5=7 | 25-5=20 |
  
  Le regret le plus important est celui de la colonne 5 : 20. Dans cette rangée, on repère le coût minimal : C(25 ,5) = 5.
  
  ### Remplissage de la matrice des transports
  
  Transports :
  
  | Sources/Destinataires | 1 | 2 | 3 | 4 | 5 |
  | - | - | - | - | - | - |
  | 1 | | | | | 0 |
  | 2 | | | | | 14 |
  
  ### Réitération du principe
  
  Coûts / Besoins / Stocks / Regrets :
  
  | Sources/Destinataires | 1 | 2 | 3 | 4 | Stocks | Regrets |
  | - | - | - | - | - | - | - |
  | 1 | 10 | 6 | 3 | 5 | 49 | 5-3=2 |
  | 2 | 5 | 2 | 6 | 12 | 30-14=16 | 5-2=3 |
  | Demandes | 15 | 20 | 5 | 25 |
  | Regrets | 10-5=5 | 6-2=4 | 6-3=3 | 12-5=7 |
  
  ETC...
  
  ### Résultat
  
  On en arrive à établir le tableau des transports :
  
  Transports :
  
  | Sources/Destinataires | 1 | 2 | 3 | 4 | 5 |
  | - | - | - | - | - | - |
  | 1 | 0 | 19 | 5 | 25 | 0 |
  | 2 | 15 | 1 | 0 | 0 | 14 |
  
  Le coût total se calcule par un produit scalaire entre les matrices des coûts et des transports.
  
  Ici, le coût optimal est donc : 0*10 + 19*6 + 5*3 + 25*5 + 0*25 + 15*5 + 1*2 + 0*6 + 0*12 + 14*5 = 401
  
  