परिवहन सिद्धांत (गणित): Difference between revisions
No edit summary |
No edit summary |
||
| Line 430: | Line 430: | ||
\sum_{x\in \mathbf{X}} \gamma_{xy}=\nu_y,\forall y\in \mathbf{Y}. | \sum_{x\in \mathbf{X}} \gamma_{xy}=\nu_y,\forall y\in \mathbf{Y}. | ||
</math> | </math> | ||
एक रैखिक प्रोग्रामिंग समस्या में इसे इनपुट करने के लिए, हमें मैट्रिक्स <math display="inline"> \gamma_{xy}</math> को [[वैश्वीकरण (गणित)|सदिश (गणित)]] बनाने की आवश्यकता है या तो इसके स्तंभों या पंक्तियों को स्टैक करके, हम, <math display="inline"> \operatorname{vec} </math> | एक रैखिक प्रोग्रामिंग समस्या में इसे इनपुट करने के लिए, हमें मैट्रिक्स <math display="inline"> \gamma_{xy}</math> को [[वैश्वीकरण (गणित)|सदिश (गणित)]] बनाने की आवश्यकता है या तो इसके स्तंभों या पंक्तियों को स्टैक करके, हम, <math display="inline"> \operatorname{vec} </math> ऑपरेशन स्तंभ-प्रमुख क्रम में, ऊपर दी गई बाधाएँ इस रूप में फिर से लिखती हैं | ||
: <math> \left( 1_{1\times \left\vert \mathbf{Y}\right\vert }\otimes I_{\left\vert \mathbf{X}\right\vert }\right) \operatorname{vec}\left( \gamma \right) =\mu </math> और <math> \left( I_{\left\vert \mathbf{Y}\right\vert }\otimes 1_{1\times \left\vert \mathbf{X}\right\vert}\right) \operatorname{vec}\left( \gamma \right) =\nu </math> | : <math> \left( 1_{1\times \left\vert \mathbf{Y}\right\vert }\otimes I_{\left\vert \mathbf{X}\right\vert }\right) \operatorname{vec}\left( \gamma \right) =\mu </math> और <math> \left( I_{\left\vert \mathbf{Y}\right\vert }\otimes 1_{1\times \left\vert \mathbf{X}\right\vert}\right) \operatorname{vec}\left( \gamma \right) =\nu </math> | ||
जहाँ <math display=inline> \otimes </math> [[क्रोनकर उत्पाद]] है, <math display=inline> 1_{n\times m}</math> आकार का | जहाँ <math display=inline> \otimes </math> [[क्रोनकर उत्पाद]] है, <math display=inline> 1_{n\times m}</math> आकार का मैट्रिक्स है <math display=inline> n\times m </math> सभी प्रविष्टियों के साथ, और <math display=inline> I_{n}</math> आकार की पहचान <math display="inline"> n</math> मैट्रिक्स है, परिणाम स्वरुप, सेटिंग <math display="inline"> z=\operatorname{vec}\left( \gamma \right) </math>, समस्या का रैखिक प्रोग्रामिंग सूत्रीकरण है: | ||
: <math> | : <math> | ||
| Line 449: | Line 449: | ||
\end{align} | \end{align} | ||
</math> | </math> | ||
जिसे बड़े पैमाने पर रैखिक प्रोग्रामिंग सॉल्वर में | जिसे बड़े पैमाने पर रैखिक प्रोग्रामिंग सॉल्वर में सरलता से इनपुट किया जा सकता है (गैलिचॉन (2016) का अध्याय 3.4 देखें)<ref name="Galichon2016">[[Alfred Galichon|Galichon, Alfred]]. ''Optimal Transport Methods in Economics''. Princeton University Press, 2016.</ref>). | ||
=== | === अर्द्ध असतत केस === | ||
अर्द्ध असतत | अर्द्ध असतत केस में, <math display=inline> X=Y=\mathbf{R}^d </math> और <math display=inline> \mu </math> पर सतत वितरण है, जबकि <math display="inline"> \nu =\sum_{j=1}^{J}\nu _{j}\delta_{y_{i}}</math>असतत वितरण है जो संभाव्यता द्रव्यमान प्रदान करता है <math display="inline"> \nu _{j} </math> साइट को <math display=inline> y_j \in \mathbf{R}^d</math>इन स्तिथियों में हम देख सकते हैं<ref>Santambrogio, Filippo. ''Optimal Transport for Applied Mathematicians''. Birkhäuser Basel, 2016. In particular chapter 6, section 4.2.</ref> कि मूल और दोहरी कांटोरोविच समस्याएं क्रमशः कम हो जाती हैं: | ||
<math display=block> \inf \left\{ \int_X \sum_{j=1}^J c(x,y_j) \, d\gamma_j(x) ,\gamma \in \Gamma(\mu,\nu)\right\} </math> | <math display=block> \inf \left\{ \int_X \sum_{j=1}^J c(x,y_j) \, d\gamma_j(x) ,\gamma \in \Gamma(\mu,\nu)\right\} </math> | ||
प्रारंभिक के लिए, जहां <math display=inline> \gamma \in \Gamma \left( \mu ,\nu \right) </math> का अर्थ है कि <math display=inline> \int_{X} d\gamma _{j}\left( x\right) =\nu _{j}</math> और <math display=inline> \sum_{j}d\gamma_{j}\left( x\right) =d\mu \left( x\right)</math>, और: | |||
<math display=block> \sup \left\{ \int_{X}\varphi (x)d\mu (x)+\sum_{j=1}^{J}\psi _{j}\nu_{j}:\psi _{j}+\varphi (x)\leq c\left( x,y_{j}\right) \right\}</math> | <math display=block> \sup \left\{ \int_{X}\varphi (x)d\mu (x)+\sum_{j=1}^{J}\psi _{j}\nu_{j}:\psi _{j}+\varphi (x)\leq c\left( x,y_{j}\right) \right\}</math> | ||
दोहरे के लिए, जिसे फिर से लिखा जा सकता है: | दोहरे के लिए, जिसे फिर से लिखा जा सकता है: | ||
<math display=block> \sup_{\psi \in \mathbf{R}^{J}}\left\{ \int_{X}\inf_{j}\left\{ c\left(x,y_{j}\right) -\psi _{j}\right\} d\mu (x)+\sum_{j=1}^{J}\psi_{j}\nu_{j}\right\} </math> | <math display=block> \sup_{\psi \in \mathbf{R}^{J}}\left\{ \int_{X}\inf_{j}\left\{ c\left(x,y_{j}\right) -\psi _{j}\right\} d\mu (x)+\sum_{j=1}^{J}\psi_{j}\nu_{j}\right\} </math> | ||
जो | जो परिमित-आयामी उत्तल अनुकूलन समस्या है जिसे मानक तकनीकों, जैसे ढाल वंश द्वारा समाधान किया जा सकता है। | ||
स्तिथियों में जब | स्तिथियों में जब <math display=inline> c\left( x,y\right) =\left\vert x-y\right\vert ^{2}/2 </math>, कोई दिखा सकता है कि <math display="inline"> x\in \mathbf{X}</math> का सेट किसी विशेष साइट को प्रदान किया गया, साइट <math display="inline"> j </math> उत्तल बहुफलक है। परिणामी कॉन्फ़िगरेशन को पावर आरेख कहा जाता है।<ref>{{citation | ||
| last = Aurenhammer | first = Franz | authorlink = Franz Aurenhammer | | last = Aurenhammer | first = Franz | authorlink = Franz Aurenhammer | ||
| doi = 10.1137/0216006 | | doi = 10.1137/0216006 | ||
| Line 476: | Line 476: | ||
=== द्विघात सामान्य मामला === | === द्विघात सामान्य मामला === | ||
विशेष | विशेष स्थिति में मान लें <math display=inline> \mu =\mathcal{N}\left( 0,\Sigma_X\right) </math>, <math display=inline> \nu =\mathcal{N} \left( 0,\Sigma _{Y}\right) </math>, और <math display=inline> c(x,y) =\left\vert y-Ax\right\vert^2/2 </math> जहाँ <math display=inline> A </math> व्युत्क्रमणीय है। एक तो है | ||
: <math> \varphi(x) =-x^\top \Sigma_X^{-1/2}\left( \Sigma_X^{1/2}A^\top \Sigma_Y A\Sigma_X^{1/2}\right) ^{1/2}\Sigma_{X}^{-1/2}x/2 </math> | : <math> \varphi(x) =-x^\top \Sigma_X^{-1/2}\left( \Sigma_X^{1/2}A^\top \Sigma_Y A\Sigma_X^{1/2}\right) ^{1/2}\Sigma_{X}^{-1/2}x/2 </math> | ||
| Line 485: | Line 485: | ||
=== वियोज्य हिल्बर्ट रिक्त स्थान === | === वियोज्य हिल्बर्ट रिक्त स्थान === | ||
मान लें कि <math>X</math> वियोज्य हिल्बर्ट स्पेस है। होने देना <math>\mathcal{P}_p(X)</math> संभाव्यता उपायों के संग्रह को निरूपित करें <math>X</math> कि परिमित है <math>p</math>-वाँ क्षण; होने देना <math>\mathcal{P}_p^r(X)</math> उन तत्वों को निरूपित करें <math>\mu \in \mathcal{P}_p(X)</math> जो गाऊसी नियमित हैं: यदि <math>g</math> गॉसियन माप पर कोई [[सख्ती से सकारात्मक उपाय|कठोरता से सकारात्मक उपाय]] है <math>X</math> और <math>g(N) = 0</math>, तब <math>\mu(N) = 0</math> भी। | |||
होने देना <math>\mu \in \mathcal{P}_p^r (X)</math>, <math>\nu \in \mathcal{P}_p(X)</math>, <math>c (x, y) = | x - y |^p/p</math> के लिए <math>p\in(1,\infty), p^{-1} + q^{-1} = 1</math>. तब कांटोरोविच समस्या का एक अनूठा समाधान है <math>\kappa</math>, और यह समाधान इष्टतम परिवहन मानचित्र से प्रेरित है: अर्थात, एक बोरेल नक्शा उपस्तिथ है <math>r\in L^p(X, \mu; X)</math> ऐसा है कि | होने देना <math>\mu \in \mathcal{P}_p^r (X)</math>, <math>\nu \in \mathcal{P}_p(X)</math>, <math>c (x, y) = | x - y |^p/p</math> के लिए <math>p\in(1,\infty), p^{-1} + q^{-1} = 1</math>. तब कांटोरोविच समस्या का एक अनूठा समाधान है <math>\kappa</math>, और यह समाधान इष्टतम परिवहन मानचित्र से प्रेरित है: अर्थात, एक बोरेल नक्शा उपस्तिथ है <math>r\in L^p(X, \mu; X)</math> ऐसा है कि | ||
Revision as of 17:50, 3 May 2023
गणित और अर्थशास्त्र में, परिवहन सिद्धांत और संसाधन आवंटन को दिया गया नाम है। 1781 में फ्रांसीसी गणितज्ञ गैसपार्ड मोंज द्वारा समस्या को औपचारिक रूप दिया गया था।[1]
1920 दशक में ए. एन. टॉल्स्टॉय परिवहन समस्या का गणितीय रूप से अध्ययन करने वाले प्रथम व्यक्तियों में से थे। 1930 में, सोवियत संघ के परिवहन के राष्ट्रीय आयुक्त के लिए परिवहन योजना खंड में, उन्होंने "अंतरिक्ष में कार्गो-परिवहन में न्यूनतम किलोमीटर के अविष्कार की विधि" नामक पत्र प्रकाशित किया।[2][3]
सोवियत संघ के गणितज्ञ और अर्थशास्त्री लियोनिद कांटोरोविच द्वारा द्वितीय विश्व युद्ध के समय क्षेत्र में प्रमुख प्रगति की गई थी।[4] परिणाम स्वरुप, जैसा कि कहा गया है, कि कभी-कभी मोंगे-कांटोरोविच को परिवहन समस्या के रूप में जाना जाता है।[5] परिवहन समस्या के रैखिक प्रोग्रामिंग सूत्रीकरण को फ्रैंक लॉरेन हिचकॉक कोपमैन्स परिवहन को समस्या के रूप में भी जाना जाता है।[6]
प्रेरणा
खदानें और कारखानों
मान लीजिए कि लौह अयस्क खनन खदानों का संग्रह है, और खानों द्वारा उत्पादित लौह अयस्क का उपयोग करने वाले n कारखानों का संग्रह है। तर्क के लिए मान लीजिए कि ये खदानें और कारखाने यूक्लिडियन समतल 'R' के दो असंयुक्त उप-समुच्चय M और F बनाते हैं। यह भी मान लें कि लागत फलन c : R2 × R2 → [0, ∞), है, जिससे कि c(x, y) लोहे के शिपमेंट को x से y तक ले जाने की लागत हो। सरलता के लिए, हम परिवहन करने में लगने वाले समय की उपेक्षा करते हैं। हम यह भी मानते हैं कि प्रत्येक खदान केवल कारखाने की आपूर्ति कर सकते है (शिपमेंट का विभाजन नहीं) और प्रत्येक कारखानों के संचालन के लिए त्रुटिहीन रूप से शिपमेंट की आवश्यकता होती है (कारखाने आधी या दोहरी क्षमता पर कार्य नहीं कर सकते हैं)। उपरोक्त मान्यताओं को बनाने के पश्चात, परिवहन योजना आक्षेप T : M → F है।
प्रत्येक खदान m ∈ M त्रुटिहीन रूप से लक्ष्य कारखाने T(m) ∈ F की आपूर्ति करते है और प्रत्येक कारखाने की आपूर्ति उचित खान द्वारा की जाती है। हम इष्टतम परिवहन योजना अविष्कार करना चाहते हैं, योजना T जिसकी कुल लागत है:
M से F तक सभी संभावित परिवहन योजनाओं में से सबसे कम है। परिवहन समस्या का यह विशेष असाइनमेंट समस्या का उदाहरण है।
अधिक विशेष रूप से, यह द्विपक्षीय ग्राफ में मिलान करने वाले न्यूनतम वजन अविष्कार करने के समान है।
मूविंग बुक्स: लागत फलन का महत्व
निम्नलिखित सरल उदाहरण इष्टतम परिवहन योजना के निर्धारण में लागत फलन के महत्व को दर्शाता है। मान लीजिए कि शेल्फ (वास्तविक रेखा) पर समान चौड़ाई की n किताबें हैं, जो एक ही सन्निहित ब्लॉक में व्यवस्थित हैं। हम उन्हें सन्निहित ब्लॉक में पुनर्व्यवस्थित करना चाहते हैं, किंतु पुस्तक-चौड़ाई को दाईं ओर स्थानांतरित कर दिया है। इष्टतम परिवहन योजना के लिए दो स्पष्ट प्रत्याशी स्वयं उपस्थित होते हैं:
- सभी n पुस्तकों को चौड़ाई में दाईं ओर ले जाएं;
- बाईं ओर वाली n पुस्तक-चौड़ाई को दाईं ओर ले जाएं और अन्य सभी पुस्तकों को नियत छोड़ दें।
यदि लागत फलन यूक्लिडियन दूरी (c(x, y) = α|x − y|) के समानुपाती है, तो ये दोनों प्रत्याशी इष्टतम हैं। यदि, दूसरी ओर, यूक्लिडियन दूरी (c(x, y) = α|x − y|2 के वर्ग के समानुपातिक रूप से उत्तल लागत फलन का चयन करते है।), तो कई छोटी चालों का विकल्प अद्वितीय मिनिमाइज़र बन जाता है।
ध्यान दें कि उपरोक्त लागत फलन केवल पुस्तकों द्वारा तय की गई क्षैतिज दूरी पर विचार करते हैं, प्रत्येक पुस्तक को उठाने और स्थिति में ले जाने के लिए उपयोग किए जाने वाले उपकरण द्वारा तय की गई क्षैतिज दूरी पर नहीं है। यदि इसके अतिरिक्त उत्तरार्द्ध पर विचार किया जाता है, तो, दो परिवहन योजनाओं में से, दूसरा सदैव यूक्लिडियन दूरी के लिए इष्टतम होता है, जबकि, कम से कम 3 पुस्तकें होने पर, प्रथम परिवहन योजना वर्गित यूक्लिडियन दूरी के लिए इष्टतम होती है।
हिचकॉक समस्या
निम्नलिखित परिवहन समस्या सूत्रीकरण का श्रेय एफ. एल. हिचकॉक को दिया जाता है:[7]
- मान लीजिए कि किसी वस्तु के लिए m स्रोत हैं वस्तु के लिए, , xi और n सिंक पर आपूर्ति की इकाइयां वस्तु के लिए, आवश्यकता के साथ yj है, यदि xi से yj तक शिपमेंट की इकाई लागत है, तो ऐसा प्रवाह ज्ञात करें जो आपूर्ति से आवश्यकता को पूर्ण करता है और प्रवाह लागत को कम करता है। लॉजिस्टिक्स में इस उदेश्य को डी. आर. फुलकर्सन ने स्वीकार किया[8] और एलआर फोर्ड जूनियर के साथ लिखी गई पुस्तक फ्लोज़ इन नेटवर्क्स (1962) में प्रकाशित की गयी है।[9]
तजालिंग कोपमैन्स को परिवहन अर्थशास्त्र के सूत्रीकरण और संसाधनों के आवंटन का श्रेय भी दिया जाता है।
एक्सेल में संख्यात्मक समाधान
बड़ी संख्या में मार्गों के साथ, समस्या को संख्यात्मक रूप से समाधान किया जाता है।
इनपुट: परिवहन सेल T हैं। आपूर्ति डेटा सेल S हैं। डिमांड डेटा सेल D हैं।
आपूर्ति की प्रत्येक इकाई को बड़े बॉक्स (शिपिंग कंटेनर) के रूप में सोचें।
आउटपुट: शिपमेंट योजना X है।
वर्तमान शिपिंग लागत K है।
उद्देश्य: लागत में कमी को अधिकतम करना।
MAX R(X)=K-T·X
शिपमेंट योजना, X, को तीन प्रकार की बाधाओं को पूर्ण करना होगा।
(1) गैर-नकारात्मकता बाधाएँ X >= 0
(2) आपूर्ति की अल्पता S-1•X >= 0
(3) आवश्यकता की अल्पता X•1-D >= 0
एक्सेल में समस्या को सेट करने की विधि नीचे दी गई तालिका में दर्शायी गयी है:
कुल शिपिंग लागत T·X सरणी [e2:H3] में शब्दों का गुणनफल है।
R-V समाधान विधि (सरल विधि का अद्यतन):
मार्गों की छोटी संख्या के लिए, समस्या को प्रारंभिक क्रॉस वर्ड पहेली या सुडोकू के जैसे समाधान किया जा सकता है।
आर-वी सॉल्यूशन मेथड वर्चुअल यूनिट कॉस्ट c, वर्चुअल प्राइस p और एक वर्चुअल ट्रेडर प्रस्तुत करता है।
वर्चुअल ट्रेडर वास्तविक प्रभाव प्रदान करता है।
महत्वपूर्ण रूप से, V-ट्रेडर मूल्य लेने वाला है।
फिर किसी भी कठोरता से लाभदायक मार्ग पर अधिक आवश्यकता होती है, और किसी भी कठोरता से लाभहीन मार्ग पर आवश्यकता शून्य होती है।
आभासी लाभ अधिकतमकरण वीपीएम
प्रत्येक मार्ग पर इकाई लाभ pj - tij -ci है इनकी गणना तालिका के नीचे दाईं ओर V-प्रॉफिट बॉक्स में की जाती है।
(यदि आप एक्सेल के साथ कार्य कर रहे हैं, तो इन सूत्रों को अंकित करें और फिर संख्यात्मक रूप से परिकलित अधिकतम के लिए सॉल्वर का उपयोग करें।)
उपयोग किए गए सभी मार्गों पर लाभ शून्य होना चाहिए और कोई भी मार्ग निश्चित रूप से लाभप्रद नहीं है।
चरण 1: नीचे के जैसे तालिका बनाएँ। तालिका में छोटी संख्याएँ डेटा बिंदु हैं। बड़ी बोल्ड संख्याएँ चर हैं।
प्रत्येक कॉलम में V-प्राइस कम से कम वीपीएम को संतुष्ट करने के लिए न्यूनतम लागत होनी चाहिए।
| A | B | D | E | F | G | H | I | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | V-प्रिंसेस | 5 | 5 | ||||||||||
| V-कॉस्ट | P1 | P2 | |||||||||||
| V-प्रॉफिट | |||||||||||||
| 2 | S1 | 10 | सप्लाई | 1 | C1 | 4 | 10 | 6 | 0 | 0 | -1 | ||
| 3 | S2 | 30 | 0 | C2 | 3 | 20 | 5 | 10 | 0 | 0 | |||
| 4 | डिमांड्स | 20 | 20 | ||||||||||
| D1 | D2 | ||||||||||||
चरण 2: सबसे कम लागत वाले को 1 आपूर्तिकर्ता (शीर्ष पंक्ति) बनाएं।
चरण 3: आदेशों को क्रम से भरें। भरा जाने वाला प्रथम मार्ग शीर्ष पंक्ति [S1:D1] में होना चाहिए। फिर क्रमिक रूप से लागत भरें जिससे कि [S2;D1] आगे भरा जाए।
चरण 3: भरा जाने वाला अंतिम आदेश इटैलिक में है। इस पंक्ति में स्रोत कम मूल्यवान है। तब C2 शून्य है। C2 के बाईं ओर के सेल को भरें।
चरण 4: V-मूल्य और V-लागतों के लिए समाधान करें।
प्रत्येक मार्गों पर V-कॉस्ट्स और V-लागतों का चयन करे, जिससे कि V-ट्रेडर सभी सक्रिय मार्गों पर समानता से आ जाए।
सबसे कम प्रविष्टियों वाले कॉलम से प्रारंभ करें (कॉलम 2)
V-सुडोकू
V-लागतों को प्रारंभ में 2 (शून्य) खाली छोड़ दिया जाता है। कॉलम 2 में ब्रेक इवेन के लिए, P2 = C2 + T22 = 0 + 5 = 5 है।
कॉलम 1 में दोनों मार्गों का उपयोग किया जाता है। चूँकि C2 शून्य है, C1 = 1 है। तब P1=C1 + T21 =5 है।
V-चेक यदि आप इस V-पहेली को स्प्रेडशीट पर सेट करते हैं, तो प्रॉफिट बॉक्स पूर्व ही भर जाएगा।
V-लागतों का वास्तविक मूल्य
आपूर्ति:
यदि आप S1 पर आपूर्ति की इकाई जोड़ते हैं तो आप सेल [S1:C2] में 1 जोड़कर और सेल [S2;C2] से 1 घटाकर परिवहन लागत को कम कर सकते हैं।
यह शिपिंग लागत को 1 से कम करता है, यह C1 का अर्थ है। यदि फर्म 1 से कम पर अतिरिक्त कंटेनर किराए पर ले सकते है (एक हजार सोचें) तो अतिरिक्त लागत बचत होती है।
यदि आप इसे S2 पर अवलोकना करते हैं, तो अतिरिक्त कंटेनर शिपिंग लागत को कम नहीं करता है। यह C1 का अर्थ है।
आवश्यकता:
यदि उत्पाद की इकाई स्थानीय रूप से (गंतव्य पर) प्राप्त की जा सकती है तो शिपिंग लागत में क्या कमी आएगी।
D1 को इकाई से कम करने का प्रयास करें। शिपिंग लागत V-प्राइस द्वारा कितनी कम होती है?
V-वर्चुअल ट्रेडर पद्धति का उपयोग करने से आभासी मूल्य और वास्तविक महत्व की लागत प्राप्त होती है।
प्रोग्रामिंग नोट:
यदि आप एक्सेल ऐड-इन सॉल्वर जैसे कैन्ड मैक्सिमाइज़िंग प्रोग्राम का उपयोग करते हैं, तो यह फ्लैश में उत्तम उत्तर प्राप्त करेगा।
यदि आप लग्रेंज गुणक या छाया मूल्यों को देखते हैं जो संवेदनशीलता रिपोर्ट में दिखाई दे सकते हैं, तो वे भ्रामक हो सकते हैं।
चूंकि सॉल्वर समाधान प्रदान करता है, आपको केवल इतना करना है कि V-कॉस्ट और V-कीमतों के लिए सुडोकू का उपयोग किया जाता है।
यहां 3 आपूर्तिकर्ताओं और 3 गंतव्यों के लिए सेट-अप है। मेरा विचार है कि आप प्रारंभ में S3 = 0 सेट करें और समाधान के लिए सुडोकू अपना मार्ग बनाएं।
| वी-प्रिंसेस | 3 | 5 | 6 | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| वी-कॉस्ट | p1 | P2 | P3 | ||||||||||||
| वी-प्रॉफिट | |||||||||||||||
| S1 | 10 | सप्लाई | 1 | C1 | 8 | 1 | + | 6 | |||||||
| S2 | 30 | c2 | 3 | 5 | + | 7 | |||||||||
| S3 | 20 | C3 | 4 | 9 | 0 | 2 | + | ||||||||
| डिमांड्स | 15 | 25 | 20 | ||||||||||||
| D1 | D2 | D3 | |||||||||||||
समस्या का सार सूत्रीकरण
मोंज और कांटोरोविच सूत्रीकरण
परिवहन समस्या जैसा कि आधुनिक या अधिक तकनीकी साहित्य में कहा गया है, रीमैनियन ज्यामिति और माप सिद्धांत के विकास के कारण कुछ भिन्न दिखती है। खान-कारखानों का उदाहरण, जितना सरल है, सार स्तिथियों के बारे में सोचते समय उपयोगी संदर्भ बिंदु है। इस सेटिंग में, हम संभावना की अनुमति देते हैं कि हम सभी खानों और कारखानों को व्यवसाय के लिए खुला नहीं रखना चाहते हैं, और खानों को एक से अधिक कारखानों की आपूर्ति और कारखानों से लोहा स्वीकार करने की अनुमति देते हैं।
और दो वियोज्य अंतरिक्ष मीट्रिक रिक्त स्थान हों जैसे कि किसी भी संभाव्यता माप पर (या ) रेडॉन माप है (अर्थात वे रेडॉन स्पेस हैं)। बोरेल-मापने योग्य फलन है। संभाव्यता उपायों को देखते हुए पर और पर इष्टतम परिवहन समस्या का मोंज सूत्रीकरण परिवहन मानचित्र अविष्कार करना है जो कि न्यूनतम है:
जहाँ के आगे पुशफॉरवर्ड माप को दर्शाता है द्वारा मानचित्र जो इस न्यूनतम को प्राप्त करता है (अर्थात इसे न्यूनतम बनाता है) जिसे इष्टतम परिवहन मानचित्र कहा जाता है।
इष्टतम परिवहन समस्या मोंज का निरूपण त्रुटिपूर्ण हो सकता है, क्योंकि कभी-कभी ऐसा नहीं होता है संतोषजनक : ऐसा होता है, उदाहरण के लिए, जब डायराक उपाय है किंतु क्या नहीं है।
इष्टतम परिवहन समस्या के कांटोरोविच के सूत्रीकरण को अपनाकर हम इस पर सुधार कर सकते हैं, जो कि संभाव्यता उपाय अविष्कार है पर जो न्यूनतम को प्राप्त करता है:
जहाँ सभी संभाव्यता उपायों के संग्रह को दर्शाता है सशर्त संभाव्यता के साथ पर और पर यह दिखाया जा सकता है[10] कि लागत फलन होने पर इस समस्या के लिए न्यूनतमकर्ता सदैव उपस्तिथ रहता है निचला अर्ध-निरंतर है और उपायों का संग्रह है (जो रेडॉन रिक्त स्थान के लिए और विश्वास है) (इस सूत्रीकरण की तुलना वासेरस्टीन मीट्रिक की परिभाषा से करें संभाव्यता उपायों के स्थान पर।) मोंगे-कैंटोरोविच समस्या के समाधान के लिए ग्रेडिएंट डिसेंट सूत्रीकरण सिगर्ड एजेंट, स्टीवन हैकर और एलन टैननबौम द्वारा दिया गया था।[11]
द्वैत सूत्र
कांटोरोविच समस्या का न्यूनतम मान है
जहां अंतिम बंधे हुए कार्य और निरंतर कार्य के जोड़े है
और ऐसा है कि
आर्थिक व्याख्या
यदि संकेत फ़्लिप किए जाते हैं तो आर्थिक व्याख्या स्पष्ट होती है। कि एक कार्यकर्ता की विशेषताओं के सदिश के लिए, एक फर्म की विशेषताओं के वेक्टर के लिए, और कार्यकर्ता द्वारा उत्पन्न आर्थिक उत्पादन के लिए फर्म से मेल खाता है . सेटिंग और मोंगे-कांटोरोविच समस्या है:
समस्या का समाधान
वास्तविक लाइन पर इष्टतम परिवहन
के लिए, मान लीजिए संभाव्यता उपायों के संग्रह को दर्शाता है परिमित -वाँ क्षण (गणित) होता है। मान लीजिए कि और, जहाँ उत्तल कार्य है।
- यदि कोई परमाणु नहीं है (माप सिद्धांत), अर्थात, यदि संचयी वितरण फलन का सतत फलन है, फिर एक इष्टतम परिवहन मानचित्र है। यह अद्वितीय इष्टतम परिवहन मानचित्र है यदि कठोरता से उत्तल है।
- अपने निकट
इस समाधान का प्रमाण राचेव एंड रुशचेंडॉर्फ (1998) में दिखाई देता है।[13]
असतत संस्करण और रैखिक प्रोग्रामिंग सूत्रीकरण
ऐसी स्तिथियों में जहां मार्जिन और असतत हैं, जहाँ और संभाव्यता द्रव्यमान क्रमशः असाइन करें और , और एक की संभावना हो कार्यभार है। प्राइमल कांटोरोविच समस्या में वस्तुनिष्ठ कार्य तब है:
और बाधा रूप में व्यक्त करता है:
और
एक रैखिक प्रोग्रामिंग समस्या में इसे इनपुट करने के लिए, हमें मैट्रिक्स को सदिश (गणित) बनाने की आवश्यकता है या तो इसके स्तंभों या पंक्तियों को स्टैक करके, हम, ऑपरेशन स्तंभ-प्रमुख क्रम में, ऊपर दी गई बाधाएँ इस रूप में फिर से लिखती हैं
- और
जहाँ क्रोनकर उत्पाद है, आकार का मैट्रिक्स है सभी प्रविष्टियों के साथ, और आकार की पहचान मैट्रिक्स है, परिणाम स्वरुप, सेटिंग , समस्या का रैखिक प्रोग्रामिंग सूत्रीकरण है:
जिसे बड़े पैमाने पर रैखिक प्रोग्रामिंग सॉल्वर में सरलता से इनपुट किया जा सकता है (गैलिचॉन (2016) का अध्याय 3.4 देखें)[12]).
अर्द्ध असतत केस
अर्द्ध असतत केस में, और पर सतत वितरण है, जबकि असतत वितरण है जो संभाव्यता द्रव्यमान प्रदान करता है साइट को इन स्तिथियों में हम देख सकते हैं[14] कि मूल और दोहरी कांटोरोविच समस्याएं क्रमशः कम हो जाती हैं:
स्तिथियों में जब , कोई दिखा सकता है कि का सेट किसी विशेष साइट को प्रदान किया गया, साइट उत्तल बहुफलक है। परिणामी कॉन्फ़िगरेशन को पावर आरेख कहा जाता है।[15]
द्विघात सामान्य मामला
विशेष स्थिति में मान लें , , और जहाँ व्युत्क्रमणीय है। एक तो है
इस समाधान का प्रमाण गैलिचोन (2016) में दिखाई देता है।[12]
वियोज्य हिल्बर्ट रिक्त स्थान
मान लें कि वियोज्य हिल्बर्ट स्पेस है। होने देना संभाव्यता उपायों के संग्रह को निरूपित करें कि परिमित है -वाँ क्षण; होने देना उन तत्वों को निरूपित करें जो गाऊसी नियमित हैं: यदि गॉसियन माप पर कोई कठोरता से सकारात्मक उपाय है और , तब भी।
होने देना , , के लिए . तब कांटोरोविच समस्या का एक अनूठा समाधान है , और यह समाधान इष्टतम परिवहन मानचित्र से प्रेरित है: अर्थात, एक बोरेल नक्शा उपस्तिथ है ऐसा है कि
इसके अतिरिक्त, यदि बंधा हुआ सेट सपोर्ट (माप सिद्धांत) है, फिर
के लिए -लगभग सभी कुछ लिप्सचिट्ज़ निरंतर, सी-अवतल और अधिकतम कांटोरोविच क्षमता के लिए . (यहाँ के गेटॉक्स व्युत्पन्न को दर्शाता है .)
एंट्रोपिक नियमितीकरण
उपरोक्त असतत समस्या के एक प्रकार पर विचार करें, जहां हमने मूल समस्या के उद्देश्य समारोह में एक एंट्रोपिक नियमितीकरण शब्द जोड़ा है
कोई दिखा सकता है कि दोहरी नियमित समस्या है
जहां, अनियमित संस्करण की तुलना में, पूर्व दोहरी में कठिन बाधा () को उस बाधा के नरम दंड द्वारा प्रतिस्थापित किया गया है ( शर्तें )। दोहरी समस्या में इष्टतमता की स्थिति के रूप में व्यक्त किया जा सकता है
- Eq. 5.1:
- Eq. 5.2:
दर्शाने के रूप में पद का मैट्रिक्स , इसलिए द्वैत को समाधानकरना दो विकर्ण धनात्मक आव्यूहों को अविष्कारने के समान है और संबंधित आकार के और , ऐसा है कि और . ऐसे मैट्रिसेस का अस्तित्व सिंकहॉर्न के प्रमेय को सामान्य करता है और सिंकहॉर्न के प्रमेय का उपयोग करके मैट्रिसेस की गणना की जा सकती है # सिंकहॉर्न-नॉप्प एल्गोरिथम।[16] जिसमें केवल पुनरावृत्ति की तलाश होती है समाधान करना Equation 5.1, और समाधान करना Equation 5.2. इसलिए सिंकहोर्न-नोप का एल्गोरिथम दोहरी नियमित समस्या पर एक समन्वित डिसेंट एल्गोरिथम है।
अनुप्रयोग
Monge-Kantorovich इष्टतम परिवहन ने विभिन्न क्षेत्रों में व्यापक श्रेणी में आवेदन पाया है। उनमें से हैं:
- छवि पंजीकरण और ताना-बाना[17]
- परावर्तक डिजाइन[18]
- एक्स-रे फ़ोटो और प्रोटॉन रेडियोग्राफी से जानकारी प्राप्त करना[19]
- भूकंपीय टोमोग्राफी और प्रतिबिंब भूकंप विज्ञान[20]
- अर्थशास्त्र मॉडलिंग का व्यापक वर्ग जिसमें सकल स्थानापन्न संपत्ति (दूसरों के बीच, स्थिर मिलान सिद्धांत और असतत पसंद के मॉडल) सम्मिलित हैं।
यह भी देखें
- वासेरस्टीन मीट्रिक
- परिवहन समारोह
- हंगेरियन एल्गोरिथम
- परिवहन योजना
- पृथ्वी मूवर की दूरी
- मोंज-एम्पीयर समीकरण
संदर्भ
- ↑ G. Monge. Mémoire sur la théorie des déblais et des remblais. Histoire de l’Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année, pages 666–704, 1781.
- ↑ Schrijver, Alexander, Combinatorial Optimization, Berlin ; New York : Springer, 2003. ISBN 3540443894. Cf. p. 362
- ↑ Ivor Grattan-Guinness, Ivor, Companion encyclopedia of the history and philosophy of the mathematical sciences, Volume 1, JHU Press, 2003. Cf. p.831
- ↑ L. Kantorovich. On the translocation of masses. C.R. (Doklady) Acad. Sci. URSS (N.S.), 37:199–201, 1942.
- ↑ Cédric Villani (2003). इष्टतम परिवहन में विषय. American Mathematical Soc. p. 66. ISBN 978-0-8218-3312-4.
- ↑ Singiresu S. Rao (2009). Engineering Optimization: Theory and Practice (4th ed.). John Wiley & Sons. p. 221. ISBN 978-0-470-18352-6.
- ↑ Frank L. Hitchcock (1941) "The distribution of a product from several sources to numerous localities", MIT Journal of Mathematics and Physics 20:224–230 MR0004469.
- ↑ D. R. Fulkerson (1956) Hitchcock Transportation Problem, RAND corporation.
- ↑ L. R. Ford Jr. & D. R. Fulkerson (1962) § 3.1 in Flows in Networks, page 95, Princeton University Press
- ↑ L. Ambrosio, N. Gigli & G. Savaré. Gradient Flows in Metric Spaces and in the Space of Probability Measures. Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel. (2005)
- ↑ Angenent, S.; Haker, S.; Tannenbaum, A. (2003). "Minimizing flows for the Monge–Kantorovich problem". SIAM J. Math. Anal. 35 (1): 61–97. CiteSeerX 10.1.1.424.1064. doi:10.1137/S0036141002410927.
- ↑ 12.0 12.1 12.2 Galichon, Alfred. Optimal Transport Methods in Economics. Princeton University Press, 2016.
- ↑ रैशेव, स्वेतलोज़र टी., और लुडगेर रशचेंडॉर्फ। मास ट्रांसपोर्टेशन प्रॉब्लम्स: वॉल्यूम I: थ्योरी। वॉल्यूम। 1. स्प्रिंगर, 1998।
- ↑ Santambrogio, Filippo. Optimal Transport for Applied Mathematicians. Birkhäuser Basel, 2016. In particular chapter 6, section 4.2.
- ↑ Aurenhammer, Franz (1987), "Power diagrams: properties, algorithms and applications", SIAM Journal on Computing, 16 (1): 78–96, doi:10.1137/0216006, MR 0873251.
- ↑ Peyré, Gabriel and Marco Cuturi (2019), "Computational Optimal Transport: With Applications to Data Science", Foundations and Trends in Machine Learning: Vol. 11: No. 5-6, pp 355–607. DOI: 10.1561/2200000073.
- ↑ Haker, Steven; Zhu, Lei; Tannenbaum, Allen; Angenent, Sigurd (1 December 2004). "पंजीकरण और वारपिंग के लिए इष्टतम जन परिवहन". International Journal of Computer Vision (in English). 60 (3): 225–240. CiteSeerX 10.1.1.59.4082. doi:10.1023/B:VISI.0000036836.66311.97. ISSN 0920-5691. S2CID 13261370.
- ↑ Glimm, T.; Oliker, V. (1 September 2003). "Optical Design of Single Reflector Systems and the Monge–Kantorovich Mass Transfer Problem". Journal of Mathematical Sciences (in English). 117 (3): 4096–4108. doi:10.1023/A:1024856201493. ISSN 1072-3374. S2CID 8301248.
- ↑ Kasim, Muhammad Firmansyah; Ceurvorst, Luke; Ratan, Naren; Sadler, James; Chen, Nicholas; Sävert, Alexander; Trines, Raoul; Bingham, Robert; Burrows, Philip N. (16 February 2017). "बड़ी तीव्रता के मॉडुलन के लिए मात्रात्मक छायाचित्रण और प्रोटॉन रेडियोग्राफी". Physical Review E. 95 (2): 023306. arXiv:1607.04179. Bibcode:2017PhRvE..95b3306K. doi:10.1103/PhysRevE.95.023306. PMID 28297858. S2CID 13326345.
- ↑ Metivier, Ludovic (24 February 2016). "Measuring the misfit between seismograms using an optimal transport distance: application to full waveform inversion". Geophysical Journal International. 205 (1): 345–377. Bibcode:2016GeoJI.205..345M. doi:10.1093/gji/ggw014.
अग्रिम पठन
- Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications. Vol. 108. Cambridge: Cambridge University Press. ISBN 978-0-521-86565-4. Zbl 1106.05001.
