Vérification de l'optimalité
Le test d'optimalité peut être effectué si deux conditions sont remplies, à savoir
1. Il y a m + n - 1 attributions, dont m est le nombre de lignes, n le nombre de colonnes. Ici m + n - 1 = 6. Mais le nombre d'allocation est cinq.
2. Ces attributions m + n - 1 doivent être indépendantes. En d’autres termes, il ne devrait pas être possible d’augmenter ou de diminuer une allocation sans modifier la position des allocations ou ne pas enfreindre les restrictions relatives aux lignes ou aux colonnes.
Une règle simple pour que les allocations soient dans des positions indépendantes est qu’il est impossible de revenir d’une allocation à l’autre par une série d’étapes horizontales et verticales d’une cellule occupée à une autre, sans inversion directe d’itinéraire. On peut voir que, dans le présent exemple, l'allocation se situe à des positions indépendantes, aucune boucle fermée ne pouvant être formée au niveau des cellules allouées.
Par conséquent, la première condition n'est pas remplie et, par conséquent, afin de satisfaire à la première condition, nous devrons allouer une petite quantité E aux cellules vacantes ayant le coût de transport le plus bas. On peut voir que t peut être attribué à la cellule (2, 2) avec un coût de 7 unités et que les allocations resteront à une position indépendante, comme décrit ci-dessous:
Maintenant, le nombre d'allocation est m + n- = 6 et ils occupent des postes indépendants.
Écrivez la matrice des coûts dans les cellules allouées.
Matrice des coûts initiaux pour les cellules allouées.
Écrivez aussi les valeurs de u i et v j comme expliqué précédemment.
Matrice d'évaluation cellulaire
On voit sur le tableau 5 que l'évaluation de la cellule à la cellule (1, 4) est négative, c'est-à-dire -4; par conséquent, en allouant à la cellule (1, 4) le coût de transport est encore réduit. Écrivons les allocations originales et la nouvelle allocation proposée.
Le tableau 6 montre que si nous affectons à la cellule (1, 4) une boucle est formée comme indiqué et que nous allouons 10 unités de sorte que l’attribution à la cellule (2, 4) s’annule comme indiqué ci-dessous dans le tableau 7.
La nouvelle table d'allocation deviendra
Coût de transport = 5X 2 + 10X 1 1 + 10X 7 + 15X9 + 5X 4 + 18 + 5 = 435 unités. Les coûts de transport sont passés de 475 unités à 435 unités.
Vérifiez pour Optimaiity:
Voyons si cette solution est optima! ou pas? Pour cela encore deux conditions doivent être vérifiées à savoir
Nombre d'attribution = m + n - 1 = 6 (satisfait)
Allocation à une position indépendante (satisfait puisque la boucle fermée pour les cellules allouées n'est pas formée)
Ecrire le coût aux alls alloués et aux valeurs de u i et v j
Exemple 2:
(Offre et demande non équilibrées). Résoudre le problème de transport suivant
Offre totale = 200 unités, demande = 185 unités.
Solution:
Puisque l'offre et la demande ne sont pas égales, le problème est déséquilibré. Pour équilibrer le problème, vous devez ajouter une colonne factice comme indiqué ci-dessous. La demande à ce magasin factice sera de 15 unités.
Solution réalisable de base:
Nous utiliserons la méthode d'approximation de Vogel pour trouver la solution réalisable initiale.
La solution réalisable initiale est donnée par la matrice suivante:
Test d'optimalité:
Dans la matrice ci-dessus, nous trouvons que:
(a) Nombre d'attributions = m + n - 1 = 4 + 5-1 = 8
(b) Ces attributions m + n - 1 occupent des positions indépendantes.
Par conséquent, le test d'optimalité peut être effectué. Cela comprend les sous-étapes expliquées précédemment, comme indiqué dans les tableaux ci-dessous:
Comme les valeurs des cellules sont + ve, la première solution réalisable est optimale. Comme le tableau 6 ne contient aucune entrée, il existe d’autres solutions optimales. L’importance pratique de la demande étant de 15 unités inférieure à celle de l’offre, c’est que l’entreprise peut réduire la production de 15 unités à l’usine où elle n’est pas rentable.
Le transport optimal (minimum) plus les coûts de production.
Z = Rs. (4 x 25 + 6 x 5 + 8 x 20 + 10 x 70 + 4 x 30 + 13 x 15 + 8 x 20 + 0 x 15)
= Rs. (100 + 30 + 160 + 170 + 120 + 195 + 160 + 0) = Rs. 1 465.
Exemple 3:
Résoudre le problème de transport suivant pour maximiser les profits. En raison des différences de coût des matières premières et des coûts de transport, le bénéfice par unité de roupies diffère, comme indiqué dans le tableau ci-dessous:
Résoudre le problème pour maximiser le profit.
Solution:
Le problème est déséquilibré et il faut donc ajouter une ligne factice pour l’équilibrer.
Trouver la solution initiale de base réalisable:
Nous utiliserons la méthode d'approximation de vogel pour déterminer la solution réalisable initiale.
Notez que nous avons affaire à un problème de maximisation. Nous allons donc entrer la différence entre le plus haut et le deuxième plus haut élément dans chaque rangée à droite de la rangée et la différence entre le plus haut et le deuxième plus haut élément dans chaque colonne en dessous de la colonne correspondante.
Chacune de ces différences représente le profit unitaire perdu pour ne pas allouer à la cellule de profit le plus élevé. Ainsi, tout en effectuant des affectations, nous sélectionnons d'abord la cellule (2, 3) avec l'entrée la plus élevée de la ligne 2, ce qui correspond à la plus grande différence de [45].
Test d'optimalité:
Nombre requis d'allocations = m + n - 1 = 3 + 4 - 1 = 6
Nombre réel d'allocation = 5.
Par conséquent, nous affectons un petit nombre positif € à la cellule (1, 3) (cellule générant un profit maximal sur les cellules vacantes), de sorte que le nombre d'attributions passe à 6. Ces 6 attributions sont dans des positions indépendantes. Par conséquent, le test d'optimalité peut être effectué.
Étant donné que toutes les valeurs de cellules sont négatives ou nulles (problème de maximisation), la solution réalisable de base initiale est optimale. La demande à la première destination est laissée non satisfaite par 5 unités. Le profit est
Z max = Rs. [90 x 70 + 90 x 100 + 110 x 30 + 130 x 100 + 0 x 5]
= Rs. 31 600.
