Problèmes de flots
223
De la même manière évaluons de tels échanges pour les autres cases :
Pour diminuer le coût total, il faut que l’échange corresponde à un
négatif. On prend
le plus négatif ; ici, il n’y a qu’un seul
négatif :
Pour passer d’une solution de base à une autre, il faut « vider » l’une des cases et en
remplir une vide de la quantité correspondante.
(-)
(+)
(+)
(-)
Ici, nous ne pouvons enlever que la plus petite quantité dans ces cases et enlèverons
donc 1 aux cases
pour l’ajouter aux cases
Le coût total de transport a diminué de
La nouvelle solution de base est optimale. En effet, tous les
sont maintenant positifs :
Remarque : On constate que les méthodes proposées de tiennent pas compte des
contraintes de la forme
. On suppose donc les arcs de capacité infinie ou, sous
une autre forme, qu’il n’ya pas de limitations quant aux quantités transportées d’un
point à un autre.
Nous allons clore maintenant ce chapitre par un cas particulier du programme de
transport, qui est le problème de l'affectation optimale.
9.6. LES PROBLEMES D’AFFECTATION
Supposons que nous ayons à résoudre le problème suivant : nous disposons de tâches
auxquelles on peut affecter moyens, chaque moyen étant affecté à une tâche et à une
seule.
Le coût de l'affectation du moyen à la tâche est évalué à une constante .
Nous appellerons la matrice constituée par les
( indice de la ligne, indice de la
colonne).
Le problème est : comment affecter les moyens pour que le coût total soit minimal ?
223
De la même manière évaluons de tels échanges pour les autres cases :
Pour diminuer le coût total, il faut que l’échange corresponde à un
négatif. On prend
le plus négatif ; ici, il n’y a qu’un seul
négatif :
Pour passer d’une solution de base à une autre, il faut « vider » l’une des cases et en
remplir une vide de la quantité correspondante.
(-)
(+)
(+)
(-)
Ici, nous ne pouvons enlever que la plus petite quantité dans ces cases et enlèverons
donc 1 aux cases
pour l’ajouter aux cases
Le coût total de transport a diminué de
La nouvelle solution de base est optimale. En effet, tous les
sont maintenant positifs :
Remarque : On constate que les méthodes proposées de tiennent pas compte des
contraintes de la forme
. On suppose donc les arcs de capacité infinie ou, sous
une autre forme, qu’il n’ya pas de limitations quant aux quantités transportées d’un
point à un autre.
Nous allons clore maintenant ce chapitre par un cas particulier du programme de
transport, qui est le problème de l'affectation optimale.
9.6. LES PROBLEMES D’AFFECTATION
Supposons que nous ayons à résoudre le problème suivant : nous disposons de tâches
auxquelles on peut affecter moyens, chaque moyen étant affecté à une tâche et à une
seule.
Le coût de l'affectation du moyen à la tâche est évalué à une constante .
Nous appellerons la matrice constituée par les
( indice de la ligne, indice de la
colonne).
Le problème est : comment affecter les moyens pour que le coût total soit minimal ?