222
Recherche opérationnelle
On prend ensuite le maximum des différences, ici 4, et l’on attribue à la case contenant
le coût minimum de la ligne ou de la colonne correspondante (ici la colonne (1)) le
minimum entre disponibilité et demande. Dans le cas présent, on attribuera
à la case
.
On raye alors la colonne ou la ligne saturée et l’on recommence les opérations sur le
tableau restant.
La solution ainsi obtenue est :
4
2
1
2
1
Cette solution est bien une solution de base puisqu’à chaque pas une ligne ou une
colonne est saturée, sauf au dernier pas où l’on sature une ligne et une colonne.
Optimisation de la solution de base. Algorithme du Stepping-Stone.
Nous allons maintenant, à partir de la solution de base obtenue, chercher une nouvelle
solution qui corresponde à un coût global moins élevé. Pour obtenir une solution plus
intéressante, supposons que l’on affecte une unité dans la case (1,1). Il faut alors en
retirer une de la case (1,3), en ajouter une dans la case (2,3) et en retirer une dans la case
(2,1).
(+)
(-)
(-)
(+)
Cet échange circulaire d’une unité fait varier le coût total d’une quantité
Les quantités
représentant les écarts unitaires quand on passe d’une base à une autre,
elles constituent les coûts marginaux unitaires.
7
8
5
4
2
3
7
2
3
1
9
5 10 3
4
2
2
6 10
4
2
3