[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/all2fr\/wiki1\/modi-method-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/all2fr\/wiki1\/modi-method-wikipedia\/","headline":"Modi Method-Wikipedia","name":"Modi Method-Wikipedia","description":"before-content-x4 Le M\u00e9thode de distribution modifi\u00e9e ( M\u00e9thode Modi ), aussi comme M\u00e9thode potentielle , M\u00e9thode U-V ou Transportalgorithme D\u00e9crit","datePublished":"2019-06-28","dateModified":"2019-06-28","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/all2fr\/wiki1\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/all2fr\/wiki1\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/a601995d55609f2d9f5e233e36fbe9ea26011b3b","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/a601995d55609f2d9f5e233e36fbe9ea26011b3b","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/all2fr\/wiki1\/modi-method-wikipedia\/","wordCount":15697,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4Le M\u00e9thode de distribution modifi\u00e9e ( M\u00e9thode Modi ), aussi comme M\u00e9thode potentielle , M\u00e9thode U-V ou Transportalgorithme D\u00e9crit est une proc\u00e9dure num\u00e9rique avec laquelle vous pouvez r\u00e9soudre de mani\u00e8re optimale un probl\u00e8me de transport standard (avec une solution de base initiale donn\u00e9e).        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Il y a un certain nombre pour un bon num\u00e9ro n {displaystyle n} Offeur UN je {displayStyle a_ {i}}         (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4( je = d’abord , . . . , n ) {displayStyle (i = 1, …, n)} Et un certain nombre m {displaystyle m} Destinataire B J {displaystyle b_ {j}}  ( J = d’abord , . . . , m ) {displayStyle (j = 1, …, m)} donn\u00e9. Dans le cas standard, l’ensemble du montant demand\u00e9 est \u00e9gal \u00e0 l’ensemble offert. Pour le transport d’une unit\u00e9        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4X je J {DisplayStyle x_ {ij}} entre UN je {displayStyle a_ {i}} et B J {displaystyle b_ {j}} d\u00e9chu c je J {DisplayStyle c_ {ij}} \u00e0. Le probl\u00e8me est que de UN je {displayStyle a_ {i}} apr\u00e8s B J {displaystyle b_ {j}} quantit\u00e9 livr\u00e9e X je J {DisplayStyle x_ {ij}} Pour d\u00e9terminer de sorte que les co\u00fbts totaux de transport sont minimis\u00e9s. Puisqu’il s’agit d’une proc\u00e9dure d’am\u00e9lioration, une proc\u00e9dure d’ouverture (par exemple le processus de matrixminium, le processus d’angle nord-ouest ou la m\u00e9thode d’approximation des oiseaux) est une solution de base initiale autoris\u00e9e X \u2208 R m n {DisplayStyle s’il vous pla\u00eet mathbb {r} ^ {mn}} certainement. Les variables de la solution de base, qui \u00e9taient initialement nulles dans le processus d’ouverture, sont les Variables non \u00e0 base , le reste de la Variables de base du syst\u00e8me sous-jacent des \u00e9quations. La m\u00e9thode Modi r\u00e9duit ensuite les co\u00fbts totaux en rempla\u00e7ant une variable non-base par une variable de base. Si une am\u00e9lioration ne peut plus \u00eatre obtenue, une solution optimale a \u00e9t\u00e9 trouv\u00e9e. La proc\u00e9dure d’optimisation est effectu\u00e9e de mani\u00e8re it\u00e9rative. \u00c0 chaque \u00e9tape, toutes les variables non de base sont v\u00e9rifi\u00e9es en ce qui concerne le potentiel de r\u00e9duction des co\u00fbts. Pour chaque variable non bas\u00e9e X je J {DisplayStyle x_ {ij}} est analys\u00e9 pour voir quelle valeur k je J {DisplayStyle k_ {ij}} Le co\u00fbt total changerait si une unit\u00e9 du bien UN je {displayStyle a_ {i}} apr\u00e8s B J {displaystyle b_ {j}} serait transport\u00e9. \u00c0 cette fin, la cellule ( je , J ) {displayStyle (i, j)} Chaque variable non bas\u00e9e X je J {DisplayStyle x_ {ij}} Le changement de co\u00fbts avec k je J = c je J – dans je – dans J {DisplayStyle k_ {ij} = c_ {ij} -u_ {i} -v_ {j}} calcul\u00e9, par lequel le dans d’abord , \u22ef , dans m {displayStyle u_ {1}, cdots, u_ {m}} et dans d’abord , \u22ef , dans n {displayStyle v_ {1}, cdots, v_ {n}} it\u00e9ratif avec l’\u00e9quation dans je + dans J = c je J {DisplayStyle u_ {i} + v_ {j} = c_ {ij}} ont \u00e9t\u00e9 calcul\u00e9s et exactement un dans je {Displaystyle u_ {i}} ou dans J {displayStyle v_ {j}} a \u00e9t\u00e9 r\u00e9gl\u00e9 z\u00e9ro et uniquement les co\u00fbts correspondants c je J {DisplayStyle c_ {ij}} Des variables de base X je J {DisplayStyle x_ {ij}} ont \u00e9t\u00e9 utilis\u00e9s pour le calcul. Est k je J {DisplayStyle k_ {ij}} positif, si cela entra\u00eenait une augmentation des co\u00fbts totaux, est k je J {DisplayStyle k_ {ij}} Le co\u00fbt total ne changerait pas. Afin d’obtenir la solution optimale avec le moins d’it\u00e9rations possible, la variable non-base est donc X je J {DisplayStyle x_ {ij}} Avec le plus n\u00e9gatif k je J {DisplayStyle k_ {ij}} enregistr\u00e9 comme une nouvelle variable de base. \u00c0 la cellule associ\u00e9e ( je , J ) {displayStyle (i, j)} Le tableau de transport en est un cercle \u00e9l\u00e9mentaire certainement. Les cellules Avec d’abord {D\u00e9plastyle z_ {1}} jusqu’\u00e0 Avec k {displaystyle z_ {k}}  ( k \u2265 5 ) {DisplayStyle (KGEQ 5)} former un cercle \u00e9l\u00e9mentaire si Avec d’abord = Avec k {D\u00e9plastyle z_ {1} = z_ {k}} , deux cellules cons\u00e9cutives Avec je {displaystyle z_ {i}} et Avec je + d’abord {displaystyle z_ {i + 1}} se trouvent dans la m\u00eame ligne ou la m\u00eame colonne du tableau et se trouvent au plus deux cellules du cercle \u00e9l\u00e9mentaire dans chaque colonne et ligne. \u00catre maintenant les cellules ( je , O ) , ( p , O ) , ( p , q ) , \u22ef , ( dans , J ) {displayStyle (i, o), (p, o), (p, q), cdots, (v, j)} les variables de base qui avec la cellule ( je , J ) {displayStyle (i, j)}  X je J {DisplayStyle x_ {ij}} D\u00e9crire un cercle \u00e9l\u00e9mentaire, d\u00e9termin\u00e9. Comme pour la m\u00e9thode de tremplin le long du cercle \u00e9l\u00e9mentaire, les premi\u00e8res variables de base sont maintenant en alternance X je O {displayStyle x_ {io}} la valeur H {displaystyle h} soustrait et sur la prochaine variable de base X p O {displayStyle x_ {po}} ajoute jusqu’\u00e0 la cellule ( je , J ) {displayStyle (i, j)} est accompli. Y a-t-il H {displaystyle h} La plus petite valeur des variables de base, dont H {displaystyle h} devrait \u00eatre soustrait. Cette variable de base devient une nouvelle variable non bas\u00e9e et \u00e0 travers X je J {DisplayStyle x_ {ij}} avec valeur H {displaystyle h} remplac\u00e9 dans la nouvelle solution de base. La proc\u00e9dure est r\u00e9p\u00e9t\u00e9e jusqu’\u00e0 ce que tout le monde (\u00e0 d\u00e9terminer dans chaque it\u00e9ration) k je J {DisplayStyle k_ {ij}} Plus \u00e9lev\u00e9 ou \u00e9galement nul, le co\u00fbt total ne peut plus \u00eatre r\u00e9duit et la solution est optimale. Si le montant total demand\u00e9 est inf\u00e9rieur \u00e0 la totalit\u00e9 du montant offert, il peut \u00eatre ins\u00e9r\u00e9 en ins\u00e9rant un client fictif B m+1{displaystyle b_ {m + 1}} , qui demande l’offre exc\u00e9dentaire et les frais de transport c i,m+1= 0 {displayStyle c_ {i, m + 1} = 0} Pour tous les fournisseurs UN i{displayStyle a_ {i}} a transform\u00e9 le probl\u00e8me de transport en un mod\u00e8le de transport standard et a donc \u00e9galement r\u00e9solu en utilisant la m\u00e9thode Modi. Est un changement possible des co\u00fbts dans la solution optimale k ij{DisplayStyle k_ {ij}} Lorsque vous prenez la variable X ij{DisplayStyle x_ {ij}} Comme z\u00e9ro, cela signifie que la valeur de la variable non-base associ\u00e9e peut \u00eatre \u00e9chang\u00e9e avec celle d’une variable de base sans modifier les co\u00fbts totaux et la solution optimale n’est pas claire. Une m\u00e9thode similaire pour am\u00e9liorer une solution de base initiale et trouver la solution optimale est la m\u00e9thode de tremplin. Les changements de co\u00fbt sont k ij{DisplayStyle k_ {ij}} avec une arithm\u00e9tique plus \u00e9lev\u00e9e (mais des valeurs identiques) que celle d\u00e9termin\u00e9e dans la m\u00e9thode Modi. Il y a plusieurs n\u00e9gatifs k ij{DisplayStyle k_ {ij}} Au lieu du plus grand, la plus grande variable non bas\u00e9e peut \u00e9galement \u00eatre s\u00e9lectionn\u00e9e, ce qui entra\u00eene une am\u00e9lioration maximale du montant du co\u00fbt ou peut \u00eatre s\u00e9lectionn\u00e9e par hasard. Le probl\u00e8me de transport r\u00e9sum\u00e9 suivant est disponible dans lequel les fournisseurs UN d’abord {displayStyle a_ {1}} et UN 2 {displayStyle a_ {2}} Offrez les quantit\u00e9s de 12 ou 8 et \u00e0 partir de trois demandes B d’abord {displayStyle b_ {1}} , B 2 {displaystyle b_ {2}} et B 3 {displayStyle b_ {3}} Les quantit\u00e9s 4, 10 ou 6 sont en demande. Dans la table \u00e0 gauche, le X je J {DisplayStyle x_ {ij}} Celui de je {displayStyle i} apr\u00e8s J {displaystyle j} quantit\u00e9 \u00e0 livrer. Le tableau de droite contient les co\u00fbts c je J {DisplayStyle c_ {ij}} que pour le transport d’une unit\u00e9 X je J {DisplayStyle x_ {ij}} depuis je {displayStyle i} apr\u00e8s J {displaystyle j} d\u00e9velopper. 20410612x11x12x138x21x22x23cijB1B2B3A1743A2556{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}}}  Le processus du coin nord-ouest est utilis\u00e9 comme processus d’ouverture. Il en r\u00e9sulte la solution de d\u00e9marrage suivante suivante, pas encore optimale: xij41061248826{displayStyle {begin {array} {c | ccc} x_ {ij} & 4 & 10 & 6 \\ hline 12 & 4 & 8 & \\ 8 && 2 & 6 \\ end {array}}}  Pour d\u00e9terminer le dans J {displayStyle v_ {j}} et dans je {Displaystyle u_ {i}} Les co\u00fbts des variables de base sont n\u00e9cessaires: cijB1B2B3A174u1A256u2v1v2v3{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 \u00e9e _ {3} & \\ end {array}}}  R\u00e9glez dans 3 = 0 {displayStyle v_ {3} = 0} . Avec dans 3 {displayStyle v_ {3}} Et les co\u00fbts c 23 {displaystyle c_ {23}} La variable de base X 23 {displayStyle x_ {23}} Vous pouvez maintenant utiliser la formule c je J = dans je + dans J {DisplayStyle c_ {ij} = u_ {i} + v_ {j}} La valeur de dans 2 {displaystyle u_ {2}} calculer: dans 2 = c 23 – dans 3 = 6 – 0 = 6 {displayStyle u_ {2} = c_ {23} -v_ {3} = 6-0 = 6} .Avec dans 2 {displaystyle u_ {2}} et c 22 {displayStyle c_ {22}} Peut maintenant \u00eatre dans 2 {displayStyle v_ {2}} calculer: dans 2 = c 22 – dans 2 = 5 – 6 = – d’abord {displayStyle v_ {2} = c_ {22} -u_ {2} = 5-6 = -1} . De m\u00eame, vous pouvez toujours \u00eatre dans d’abord = 4 – ( – d’abord ) = 5 {displayStyle u_ {1} = 4 – (- 1) = 5} et dans d’abord = 7 – 5 = 2 {displayStyle v_ {1} = 7-5 = 2} calculer. Avec le dans J {displayStyle v_ {j}} et dans je {Displaystyle u_ {i}} et c je J {DisplayStyle c_ {ij}} La formule peut maintenant \u00eatre fabriqu\u00e9e \u00e0 partir du tableau de co\u00fbts ci-dessus k je J = c je J – dans je – dans J {DisplayStyle k_ {ij} = c_ {ij} -u_ {i} -v_ {j}} Calculez le changement de co\u00fbt transport\u00e9 par une unit\u00e9 via les variables non bas\u00e9es X je J {DisplayStyle x_ {ij}} r\u00e9sultat: uik135k216vj2\u221210{displayStyle {begin {array} {c | ccc | c} &&&& u_ {i} \\ hline &&& k_ {13} & 5 \\ & k_ {21} &&& 6 \\ hline v_ {j} & 2 & -1 & 0 & \\ end {Array}}}}  Ainsi k 13 = c 13 – dans d’abord – dans 3 = 3 – 5 – 0 = – 2 {DisplayStyle k_ {13} = c_ {13} -u_ {1} -v_ {3} = 3-5-0 = -2} et k 21 = c 21 – dans 2 – dans d’abord = 5 – 6 – 2 = – 3 {DisplayStyle k_ {21} = c_ {21} -u_ {2} -v_ {1} = 5-6-2 = -3} . Avec les deux X je J {DisplayStyle x_ {ij}} Il y aurait donc une perte de co\u00fbts. Inclus X 21 {displayStyle x_ {21}} Les \u00e9conomies sont plus importantes, nous choisissons ces variables non bas\u00e9es et d\u00e9terminons le cercle \u00e9l\u00e9mentaire \u00e0 la cellule ( 2 , d’abord ) {DisplayStyle (2.1)} . C’est ( 2 , d’abord ) , ( 2 , 2 ) , ( d’abord , 2 ) {DisplayStyle (2.1), (2.2), (1,2)} et ( d’abord , d’abord ) {DisplayStyle (1,1)} . Un maximum de deux unit\u00e9s peut d\u00e9sormais \u00eatre termin\u00e9e X 21 {displayStyle x_ {21}} \u00eatre transport\u00e9, sinon X 22 {displayStyle x_ {22}} deviendrait n\u00e9gatif: le long du cercle \u00e9l\u00e9mentaire, les deux unit\u00e9s sont maintenant ajout\u00e9es alternativement ou soustraites. Ce sera X 21 {displayStyle x_ {21}} Aux variables de base et X 22 {displayStyle x_ {22}} Aux variables non bas\u00e9es: xij410612210826{displayStyle {begin {array} {c | ccc} x_ {ij} & 4 & 10 & 6 \\ hline 12 & 2 & 10 & \\ 8 & 2 && 6 \\ end {array}}}  Maintenant encore avec les co\u00fbts ci-dessus c je J {DisplayStyle c_ {ij}} \u00c0 partir du tableau ci-dessus des variables de base et en d\u00e9finissant dans 3 = 0 {displayStyle v_ {3} = 0} le reste dans J {displayStyle v_ {j}} et dans je {Displaystyle u_ {i}} Avec la formule c je J = dans je + dans J {DisplayStyle c_ {ij} = u_ {i} + v_ {j}} \u00eatre calcul\u00e9: cijui748566vj\u22121\u221240{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}}}}  Avec le dans J {displayStyle v_ {j}} , dans je {Displaystyle u_ {i}} et c je J {DisplayStyle c_ {ij}} Maintenant, les changements de co\u00fbt peuvent \u00eatre \u00e0 nouveau k 13 {displaystyle k_ {13}} et k 22 {displaystyle k_ {22}} calculer: k 13 = c 13 – dans d’abord – dans 3 = 3 – 8 – 0 = – 5 {DisplayStyle k_ {13} = c_ {13} -u_ {1} -v_ {3} = 3-8-0 = -5} et analogique k 22 = 5 + 4 – 6 = 3 {displayStyle k_ {22} = 5 + 4-6 = 3} . En transportant une unit\u00e9 sur X 13 {displayStyle x_ {13}} Une r\u00e9duction des co\u00fbts peut donc \u00eatre r\u00e9alis\u00e9e \u00e0 nouveau. Le cercle \u00e9l\u00e9mentaire de la cellule ( d’abord , 3 ) {DisplayStyle (1,3)} est: ( d’abord , 3 ) , ( d’abord , d’abord ) , ( 2 , d’abord ) {DisplayStyle (1,3), (1,1), (2.1)} et ( 2 , 3 ) {DisplayStyle (2,3)} . Donc un maximum de deux unit\u00e9s (\u00e0 cause de X 11 = 2 {displayStyle x_ {11} = 2} ) D\u00e9placer le long du cercle \u00e9l\u00e9mentaire et la nouvelle solution de base est cr\u00e9\u00e9e: xij410612102844{displayStyle {begin {array} {c | ccc} x_ {ij} & 4 & 10 & 6 \\ hline 12 && 10 & 2 \\ 8 & 4 && 4 \\ end {array}}}  Maintenant, vous devez d\u00e9terminer \u00e0 nouveau k 11 {displaystyle k_ {11}} et k 22 {displaystyle k_ {22}} le dans J {displayStyle v_ {j}} et dans je {Displaystyle u_ {i}} \u00eatre d\u00e9termin\u00e9. Ceci est r\u00e9p\u00e9t\u00e9 tant que le k je J {DisplayStyle k_ {ij}} tous ne sont pas n\u00e9gatifs et avec \u00e7a un Solution optimale, ou si tout le monde k je J {DisplayStyle k_ {ij}} sont plus grands que z\u00e9ro le Une solution optimale a \u00e9t\u00e9 trouv\u00e9e. La m\u00eame solution se traduit que dans l’exemple de la m\u00e9thode de tremplin.      (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/all2fr\/wiki1\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/all2fr\/wiki1\/modi-method-wikipedia\/#breadcrumbitem","name":"Modi Method-Wikipedia"}}]}]