La Méthode de Vogel Modifiée et ses Approches

Principe de la Méthode de Vogel modifiée

Elle comprend principalement deux étapes. La première permet de déterminer un problème équivalent au problème de transport PT et qui correspond à la matrice des coûts réduits. Cette procédure, assez bien connue, est souvent utilisée pour résoudre le problème d’affectation . La deuxième étape consiste à appliquer la méthode de Vogel à ce nouveau problème. Notons la réduction de la matrice est effectuée après chaque étape d’assignation. Dans le cas d’embarras de choix, quelques règles supplémentaires permettent de le lever. Elles sont également présentées ci-dessous. Recherche Opérationnelle  La matrice des coûts réduits de la première partie s’obtient en soustrayant à tous les éléments de chaque rangée ( ligne et colonne ) le plus petit coût de cette rangée. Ce qui introduit donc un zéro au niveau de chaque rangée ( ligne et colonne ). La réduction de la matrice peut se faire de deux approches : La première approche qui consiste à réduire d’abord les lignes ensuite les colonnes , nous l’appellerons : méthode de Vogel modifiée Ligne-Colonne ( MVMLC ). Et la deuxième est celle qui réduit premièrement les colonnes et les lignes après nous l’appellerons : méthode de Vogel modifiée Colonne-Ligne ( MVMCL ).

Les deux Approches de la Méthode Modifiée

Les deux approches de la Méthode de Vogel Modifiée sont, comme nous l’avons spécifié ci-dessus 3.2.1 Algorithme de l’approche ligne-colonne Étape 1. Matrice Initiale de coûts réduits Déterminer la matrice de coûts réduits de la manière suivante : Réduire chaque ligne i en déterminant ui = min j {Cij} (3.1) et en posant C´ ij = Cij − ui ; ∀j = 1, · · · , m (3.2) Ensuite réduire chaque colonne j en déterminant vj = min i {C´ ij} (3.3) et en posant Cij = C´ ij − vj ; ∀i = 1, · · · , n (3.4) Étape 2. Détermination de la variable à assigner Appliquer une itération de la méthode de Vogel au problème de transport réduit défini par la matrice C. Dans le cas d’existence d’embarras de choix, il faut utiliser les Recherche Opérationnelle :Ev et Val de Méthode de Vogel Modifiée Ould Abdallahi Ismail c 2012 UCAD Les deux Approches de la Méthode Modifiée 28 règles supplémentaires énoncées ci dessous. Étape 3. Test d’arrêt S’il reste une colonne ou une ligne non rayée dans le tableau, la remplir et FIN Étape 4. Mise à jour de la matrice de coûts réduits Si une ligne i (colonne j) a été rayée durant l’étape 2, alors seules les colonnes (lignes) k telles que Cik = 0 (respectivement Ckj = 0) sont à réduire.

Autres choix imposés

Au niveau de la ligne i (colonne j), le troisième moindre coût constitue le moindre coût de la colonne (ligne) de plus grande pénalité. Son choix s’impose donc au niveau de la ligne i (colonne j) aux dépens du moindre coût. Dans les situations 1 et 2, la perte unitaire est égale à pi au niveau de la ligne i tandis qu’elle est supérieure dans la situation 3. Cependant, l’analyse globale de chacune des situations 1, 2 et 3 devrait tenir compte du gain résultant respectivement de la colonne (ligne) du moindre, du second et du troisième moindre coût. Cette étude n’a pas été entièrement présentée dans ce mémoire. Cependant, elle révèle dans chacune de ces situations que les pénalités pi et qj fournies par la méthode de Vogel ne mesurent pas, contrairement à la méthode modifiée, les pertes unitaires au niveau de la ligne i (colonne j). Pour cette raison, le choix dicté par la méthode de Vogel quant à la ligne et colonne à assigner n’est pas nécessairement le plus pertinent. La méthode de Vogel effectue une analyse locale au niveau de chaque ligne et colonne tandis que la méthode modifiée effectue une analyse plus globale. Toute la différence réside dans le fait que la valeur zéro est le moindre coût de chaque ligne et colonne de la matrice. La méthode de vogel modifiée contrairement à son origine réduit comme la méthode du simplexe les coûts avant d’assigner les variables.