Modi Method-Wikipedia

Posted on June 28, 2019 by lordneo

before-content-x4

Le Méthode de distribution modifiée ( Méthode Modi ), aussi comme Méthode potentielle , Méthode U-V ou Transportalgorithme Décrit est une procédure numérique avec laquelle vous pouvez résoudre de manière optimale un problème de transport standard (avec une solution de base initiale donnée).

after-content-x4

Il y a un certain nombre pour un bon numéro

{displaystyle n}

$n$ Offeur

{displayStyle a_ {i}}

$A_{i}$

{displayStyle (i = 1, …, n)}

$(i=1,...,n)$ Et un certain nombre

{displaystyle m}

$m$ Destinataire

{displaystyle b_ {j}}

$B_{j}$

{displayStyle (j = 1, …, m)}

$(j=1,...,m)$ donné. Dans le cas standard, l’ensemble du montant demandé est égal à l’ensemble offert. Pour le transport d’une unité

after-content-x4

{DisplayStyle x_ {ij}}

$x_{{ij}}$ entre

{displayStyle a_ {i}}

$A_{i}$ et

{displaystyle b_ {j}}

$B_{j}$ déchu

{DisplayStyle c_ {ij}}

$c_{ij}$ à. Le problème est que de

{displayStyle a_ {i}}

$A_{i}$ après

{displaystyle b_ {j}}

$B_{j}$ quantité livrée

{DisplayStyle x_ {ij}}

$x_{{ij}}$ Pour déterminer de sorte que les coûts totaux de transport sont minimisés.

Puisqu’il s’agit d’une procédure d’amélioration, une procédure d’ouverture (par exemple le processus de matrixminium, le processus d’angle nord-ouest ou la méthode d’approximation des oiseaux) est une solution de base initiale autorisée

{DisplayStyle s’il vous plaît mathbb {r} ^ {mn}}

$xin {mathbb {R}}^{{mn}}$ certainement. Les variables de la solution de base, qui étaient initialement nulles dans le processus d’ouverture, sont les Variables non à base , le reste de la Variables de base du système sous-jacent des équations. La méthode Modi réduit ensuite les coûts totaux en remplaçant une variable non-base par une variable de base. Si une amélioration ne peut plus être obtenue, une solution optimale a été trouvée.

La procédure d’optimisation est effectuée de manière itérative. À chaque étape, toutes les variables non de base sont vérifiées en ce qui concerne le potentiel de réduction des coûts. Pour chaque variable non basée

{DisplayStyle x_ {ij}}

$x_{{ij}}$ est analysé pour voir quelle valeur

{DisplayStyle k_ {ij}}

$k_{{ij}}$ Le coût total changerait si une unité du bien

{displayStyle a_ {i}}

$A_{i}$ après

{displaystyle b_ {j}}

$B_{j}$ serait transporté. À cette fin, la cellule

{displayStyle (i, j)}

$(i,j)$ Chaque variable non basée

{DisplayStyle x_ {ij}}

$x_{{ij}}$ Le changement de coûts avec

{DisplayStyle k_ {ij} = c_ {ij} -u_ {i} -v_ {j}}

$k_{{ij}}=c_{{ij}}-u_{i}-v_{j}$ calculé, par lequel le

{displayStyle u_ {1}, cdots, u_ {m}}

$u_{1},cdots ,u_{m}$ et

{displayStyle v_ {1}, cdots, v_ {n}}

$v_{1},cdots ,v_{n}$ itératif avec l’équation

{DisplayStyle u_ {i} + v_ {j} = c_ {ij}}

$u_{i}+v_{j}=c_{{ij}}$ ont été calculés et exactement un

{Displaystyle u_ {i}}

$u_{i}$ ou

{displayStyle v_ {j}}

$v_{{j}}$ a été réglé zéro et uniquement les coûts correspondants

{DisplayStyle c_ {ij}}

$c_{ij}$ Des variables de base

{DisplayStyle x_ {ij}}

$x_{{ij}}$ ont été utilisés pour le calcul.

Est

{DisplayStyle k_ {ij}}

$k_{{ij}}$ positif, si cela entraînait une augmentation des coûts totaux, est

{DisplayStyle k_ {ij}}

$k_{{ij}}$ Le coût total ne changerait pas. Afin d’obtenir la solution optimale avec le moins d’itérations possible, la variable non-base est donc

{DisplayStyle x_ {ij}}

$x_{{ij}}$ Avec le plus négatif

{DisplayStyle k_ {ij}}

$k_{{ij}}$ enregistré comme une nouvelle variable de base. À la cellule associée

{displayStyle (i, j)}

$(i,j)$ Le tableau de transport en est un cercle élémentaire certainement. Les cellules

{Déplastyle z_ {1}}

$z_{1}$ jusqu’à

{displaystyle z_ {k}}

$z_k$

{DisplayStyle (KGEQ 5)}

$(kgeq 5)$ former un cercle élémentaire si

{Déplastyle z_ {1} = z_ {k}}

$z_{1}=z_{k}$ , deux cellules consécutives

{displaystyle z_ {i}}

$z_{i}$ et

{displaystyle z_ {i + 1}}

$z_{{i+1}}$ se trouvent dans la même ligne ou la même colonne du tableau et se trouvent au plus deux cellules du cercle élémentaire dans chaque colonne et ligne. Être maintenant les cellules

{displayStyle (i, o), (p, o), (p, q), cdots, (v, j)}

$(i,o),(p,o),(p,q),cdots ,(v,j)$ les variables de base qui avec la cellule

{displayStyle (i, j)}

$(i,j)$

{DisplayStyle x_ {ij}}

$x_{{ij}}$ Décrire un cercle élémentaire, déterminé. Comme pour la méthode de tremplin le long du cercle élémentaire, les premières variables de base sont maintenant en alternance

{displayStyle x_ {io}}

$x_{{io}}$ la valeur

{displaystyle h}

$h$ soustrait et sur la prochaine variable de base

{displayStyle x_ {po}}

$x_{{po}}$ ajoute jusqu’à la cellule

{displayStyle (i, j)}

$(i,j)$ est accompli. Y a-t-il

{displaystyle h}

$h$ La plus petite valeur des variables de base, dont

{displaystyle h}

$h$ devrait être soustrait. Cette variable de base devient une nouvelle variable non basée et à travers

{DisplayStyle x_ {ij}}

$x_{{ij}}$ avec valeur

{displaystyle h}

$h$ remplacé dans la nouvelle solution de base. La procédure est répétée jusqu’à ce que tout le monde (à déterminer dans chaque itération)

{DisplayStyle k_ {ij}}

$k_{{ij}}$ Plus élevé ou également nul, le coût total ne peut plus être réduit et la solution est optimale.

Si le montant total demandé est inférieur à la totalité du montant offert, il peut être inséré en insérant un client fictif ${displaystyle b_ {m + 1}}$

Est un changement possible des coûts dans la solution optimale ${DisplayStyle k_ {ij}}$

Une méthode similaire pour améliorer une solution de base initiale et trouver la solution optimale est la méthode de tremplin. Les changements de coût sont ${DisplayStyle k_ {ij}}$

Il y a plusieurs négatifs ${DisplayStyle k_ {ij}}$

Le problème de transport résumé suivant est disponible dans lequel les fournisseurs

{displayStyle a_ {1}}

$A_{1}$ et

{displayStyle a_ {2}}

$A_{2}$ Offrez les quantités de 12 ou 8 et à partir de trois demandes

{displayStyle b_ {1}}

$B_1$ ,

{displaystyle b_ {2}}

$B_2$ et

{displayStyle b_ {3}}

$B_3$ Les quantités 4, 10 ou 6 sont en demande. Dans la table à gauche, le

{DisplayStyle x_ {ij}}

$x_{{ij}}$ Celui de

{displayStyle i}

$i$ après

{displaystyle j}

$j$ quantité à livrer. Le tableau de droite contient les coûts

{DisplayStyle c_ {ij}}

$c_{ij}$ que pour le transport d’une unité

{DisplayStyle x_ {ij}}

$x_{{ij}}$ depuis

{displayStyle i}

$i$ après

{displaystyle j}

$j$ développer.

{displaystyle {begin{array}{c|ccc}20&4&10&6\hline 12&x_{11}&x_{12}&x_{13}\8&x_{21}&x_{22}&x_{23}\end{array}}qquad {begin{array}{c|ccc}c_{ij}&B_{1}&B_{2}&B_{3}\hline A_{1}&7&4&3\A_{2}&5&5&6\end{array}}}

${begin{array}{c|ccc}20&4&10&6\hline 12&x_{{11}}&x_{{12}}&x_{{13}}\8&x_{{21}}&x_{{22}}&x_{{23}}\end{array}}qquad {begin{array}{c|ccc}c_{{ij}}&B_{1}&B_{2}&B_{3}\hline A_{1}&7&4&3\A_{2}&5&5&6\end{array}}$

Le processus du coin nord-ouest est utilisé comme processus d’ouverture. Il en résulte la solution de démarrage suivante suivante, pas encore optimale:

{displayStyle {begin {array} {c | ccc} x_ {ij} & 4 & 10 & 6 \ hline 12 & 4 & 8 & \ 8 && 2 & 6 \ end {array}}}

${begin{array}{c|ccc}x_{{ij}}&4&10&6\hline 12&4&8&\8&&2&6\end{array}}$

Pour déterminer le

{displayStyle v_ {j}}

$v_{j}$ et

{Displaystyle u_ {i}}

$u_{i}$ Les coûts des variables de base sont nécessaires:

{displayStyle {begin {array} {c | ccc | c} c_ {ij} & b_ {1} & b_ {2} & b_ {3} & \ hline a_ {1} & 7 & 4 && u_ {1} \ a_ {2} && 5 & 6 & u_ {2} \ hline & v_} & V_ & 6 & u_ {2 ée _ {3} & \ end {array}}}

${begin{array}{c|ccc|c}c_{{ij}}&B_{1}&B_{2}&B_{3}&\hline A_{1}&7&4&&u_{1}\A_{2}&&5&6&u_{2}\hline &v_{1}&v_{2}&v_{3}&\end{array}}$

Réglez

{displayStyle v_ {3} = 0}

$v_{3}=0$ . Avec

{displayStyle v_ {3}}

$v_{3}$ Et les coûts

{displaystyle c_ {23}}

$c_{{23}}$ La variable de base

{displayStyle x_ {23}}

$x_{{23}}$ Vous pouvez maintenant utiliser la formule

{DisplayStyle c_ {ij} = u_ {i} + v_ {j}}

$c_{{ij}}=u_{i}+v_{j}$ La valeur de

{displaystyle u_ {2}}

$u_{2}$ calculer:

{displayStyle u_ {2} = c_ {23} -v_ {3} = 6-0 = 6}

$u_{2}=c_{{23}}-v_{3}=6-0=6$ .
Avec

{displaystyle u_ {2}}

$u_{2}$ et

{displayStyle c_ {22}}

$c_{{22}}$ Peut maintenant être

{displayStyle v_ {2}}

$v_{2}$ calculer:

{displayStyle v_ {2} = c_ {22} -u_ {2} = 5-6 = -1}

$v_{2}=c_{{22}}-u_{2}=5-6=-1$ . De même, vous pouvez toujours être

{displayStyle u_ {1} = 4 – (- 1) = 5}

$u_{1}=4-(-1)=5$ et

{displayStyle v_ {1} = 7-5 = 2}

$v_{1}=7-5=2$ calculer. Avec le

{displayStyle v_ {j}}

$v_{j}$ et

{Displaystyle u_ {i}}

$u_{i}$ et

{DisplayStyle c_ {ij}}

$c_{ij}$ La formule peut maintenant être fabriquée à partir du tableau de coûts ci-dessus

{DisplayStyle k_ {ij} = c_ {ij} -u_ {i} -v_ {j}}

$k_{{ij}}=c_{{ij}}-u_{i}-v_{j}$ Calculez le changement de coût transporté par une unité via les variables non basées

{DisplayStyle x_ {ij}}

$x_{{ij}}$ résultat:

{displayStyle {begin {array} {c | ccc | c} &&&& u_ {i} \ hline &&& k_ {13} & 5 \ & k_ {21} &&& 6 \ hline v_ {j} & 2 & -1 & 0 & \ end {Array}}}}

${begin{array}{c|ccc|c}&&&&u_{i}\hline &&&k_{{13}}&5\&k_{{21}}&&&6\hline v_{j}&2&-1&0&\end{array}}$

Ainsi

{DisplayStyle k_ {13} = c_ {13} -u_ {1} -v_ {3} = 3-5-0 = -2}

$k_{{13}}=c_{{13}}-u_{1}-v_{3}=3-5-0=-2$ et

{DisplayStyle k_ {21} = c_ {21} -u_ {2} -v_ {1} = 5-6-2 = -3}

$k_{{21}}=c_{{21}}-u_{2}-v_{1}=5-6-2=-3$ . Avec les deux

{DisplayStyle x_ {ij}}

$x_{{ij}}$ Il y aurait donc une perte de coûts. Inclus

{displayStyle x_ {21}}

$x_{{21}}$ Les économies sont plus importantes, nous choisissons ces variables non basées et déterminons le cercle élémentaire à la cellule

{DisplayStyle (2.1)}

$(2,1)$ . C’est

{DisplayStyle (2.1), (2.2), (1,2)}

$(2,1),(2,2),(1,2)$ et

{DisplayStyle (1,1)}

$(1,1)$ . Un maximum de deux unités peut désormais être terminée

{displayStyle x_ {21}}

$x_{{21}}$ être transporté, sinon

{displayStyle x_ {22}}

$x_{{22}}$ deviendrait négatif: le long du cercle élémentaire, les deux unités sont maintenant ajoutées alternativement ou soustraites. Ce sera

{displayStyle x_ {21}}

$x_{{21}}$ Aux variables de base et

{displayStyle x_ {22}}

$x_{{22}}$ Aux variables non basées:

{displayStyle {begin {array} {c | ccc} x_ {ij} & 4 & 10 & 6 \ hline 12 & 2 & 10 & \ 8 & 2 && 6 \ end {array}}}

${begin{array}{c|ccc}x_{{ij}}&4&10&6\hline 12&2&10&\8&2&&6\end{array}}$

Maintenant encore avec les coûts ci-dessus

{DisplayStyle c_ {ij}}

$c_{ij}$ À partir du tableau ci-dessus des variables de base et en définissant

{displayStyle v_ {3} = 0}

$v_{3}=0$ le reste

{displayStyle v_ {j}}

$v_{j}$ et

{Displaystyle u_ {i}}

$u_{i}$ Avec la formule

{DisplayStyle c_ {ij} = u_ {i} + v_ {j}}

$c_{{ij}}=u_{i}+v_{j}$ être calculé:

{displayStyle {begin {array} {c | ccc | c} c_ {ij} &&&& u_ {i} \ hline & 7 & 4 && 8 \ & 5 && 6 & 6 \ hline v_ {j} & – 1 & -4 & 0 & \ end {Array}}}}

${begin{array}{c|ccc|c}c_{{ij}}&&&&u_{i}\hline &7&4&&8\&5&&6&6\hline v_{j}&-1&-4&0&\end{array}}$

Avec le

{displayStyle v_ {j}}

$v_{j}$ ,

{Displaystyle u_ {i}}

$u_{i}$ et

{DisplayStyle c_ {ij}}

$c_{ij}$ Maintenant, les changements de coût peuvent être à nouveau

{displaystyle k_ {13}}

$k_{{13}}$ et

{displaystyle k_ {22}}

$k_{{22}}$ calculer:

{DisplayStyle k_ {13} = c_ {13} -u_ {1} -v_ {3} = 3-8-0 = -5}

$k_{{13}}=c_{{13}}-u_{1}-v_{3}=3-8-0=-5$ et analogique

{displayStyle k_ {22} = 5 + 4-6 = 3}

$k_{{22}}=5+4-6=3$ . En transportant une unité sur

{displayStyle x_ {13}}

$x_{{13}}$ Une réduction des coûts peut donc être réalisée à nouveau. Le cercle élémentaire de la cellule

{DisplayStyle (1,3)}

$(1,3)$ est:

{DisplayStyle (1,3), (1,1), (2.1)}

$(1,3),(1,1),(2,1)$ et

{DisplayStyle (2,3)}

$(2,3)$ . Donc un maximum de deux unités (à cause de

{displayStyle x_ {11} = 2}

${displaystyle x_{11}=2}$ ) Déplacer le long du cercle élémentaire et la nouvelle solution de base est créée:

{displayStyle {begin {array} {c | ccc} x_ {ij} & 4 & 10 & 6 \ hline 12 && 10 & 2 \ 8 & 4 && 4 \ end {array}}}

${begin{array}{c|ccc}x_{{ij}}&4&10&6\hline 12&&10&2\8&4&&4\end{array}}$

Maintenant, vous devez déterminer à nouveau

{displaystyle k_ {11}}

$k_{{11}}$ et

{displaystyle k_ {22}}

$k_{{22}}$ le

{displayStyle v_ {j}}

$v_{j}$ et

{Displaystyle u_ {i}}

$u_{i}$ être déterminé. Ceci est répété tant que le

{DisplayStyle k_ {ij}}

$k_{{ij}}$ tous ne sont pas négatifs et avec ça un Solution optimale, ou si tout le monde

{DisplayStyle k_ {ij}}

$k_{{ij}}$ sont plus grands que zéro le Une solution optimale a été trouvée. La même solution se traduit que dans l’exemple de la méthode de tremplin.

after-content-x4

Modi Method-Wikipedia

Recent Posts

Recent Comments

Archives

Categories

Meta