224
Recherche opérationnelle
9.6.1. Possibilités de résolutions
Constatons tout d'abord que si l'on voulait énumérer tous les cas possibles, il y en aurait
, ce qui exclue que l' on utilise cette méthode pour des nombres importants.
Par ailleurs, si nous voulons formaliser le problème, nous pouvons le faire de la façon
suivante :
Posons
si le moyen est affecté à la tâche .
si le moyen n'est pas affecté à la tâche .
Comme un moyen n'est affecté qu'à une tâche et une seule, on doit avoir :
Par ailleurs, il s'agit de minimiser la fonction
Là encore, nous obtenons un programme linéaire : sa particularité est que les variables
sont astreintes à ne prendre que les valeurs
. Ces programmes particuliers, on
l'a vu, sont appelés programmes en variables bivalentes.
On pourrait alors par exemple utiliser une procédure de recherche arborescente (cf.
chapitre précédent) en prenant pour sous-ensemble de la procédure les sous-ensembles
d'affectations possibles telles qu'une variable particulière soit égale à
.
L'expérience montre que l'exploration risque dans beaucoup de cas d'être assez longue.
On reconnaîtra également sur la formalisation ci-dessus un programme de transport. On
pourrait donc appliquer l'algorithme précédent. En fait c'est une légère variante de cet
algorithme que nous allons exposer, l'algorithme hongrois utilisant lui aussi la procédure
de Ford-Fulkerson.
9.6.2. Théorème fondamental
On ne change pas la solution du problème en retranchant ou en ajoutant à une ligne ou à
une colonne de la matrice des coûts une même quantité.
En effet, prenons une ligne k quelconque.