परिवहन सिद्धांत (गणित)

गणित और अर्थशास्त्र में, परिवहन सिद्धांत और संसाधन आवंटन को दिया गया नाम है। 1781 में फ्रांसीसी गणितज्ञ गैसपार्ड मोंज द्वारा समस्या को औपचारिक रूप दिया गया था।

1920 दशक में ए.एन. टॉल्स्टॉय परिवहन समस्या का गणितीय रूप से अध्ययन करने वाले प्रथम व्यक्तियों में से थे। 1930 में, सोवियत संघ के परिवहन के राष्ट्रीय आयुक्त के लिए परिवहन योजना खंड में, उन्होंने "अंतरिक्ष में कार्गो-परिवहन में न्यूनतम किलोमीटर की अविष्कार के विधि" नामक पत्र प्रकाशित किया।

सोवियत संघ के गणितज्ञ और अर्थशास्त्री लियोनिद कांटोरोविच द्वारा द्वितीय विश्व युद्ध के समय क्षेत्र में प्रमुख प्रगति की गई थी। परिणाम स्वरुप, जैसा कि कहा गया है, समस्या को कभी-कभी मोंगे-कांटोरोविच परिवहन समस्या के रूप में जाना जाता है। परिवहन समस्या के रैखिक प्रोग्रामिंग सूत्रीकरण को फ्रैंक लॉरेन हिचकॉक- कोपमैन्स परिवहन को समस्या के रूप में भी जाना जाता है।

प्रेरणा

खदानें और कारखानों

मान लीजिए कि हमारे निकट लौह अयस्क खनन करने वाली खदानों का संग्रह है, और खानों द्वारा उत्पादित लौह अयस्क का उपयोग करने वाले n कारखानों का संग्रह है। तर्क के लिए मान लीजिए कि ये खदानें और कारखाने यूक्लिडियन समतल 'R' के दो असंयुक्त उपसमुच्चय M और F बनाते हैं। यह भी मान लें कि हमारे निकट लागत फलन c : R² × R² → [0, ∞), है, जिससे कि c(x, y) लोहे के शिपमेंट को x से y तक ले जाने की लागत हो। सरलता के लिए, हम परिवहन करने में लगने वाले समय को उपेक्षा कर देते हैं। हम यह भी मानते हैं कि प्रत्येक खदान केवल कारखाने की आपूर्ति कर सकती है (शिपमेंट का विभाजन नहीं) और प्रत्येक कारखानों के संचालन के लिए त्रुटिहीन रूप से शिपमेंट की आवश्यकता होती है (कारखाने आधी या दोहरी क्षमता पर कार्य नहीं कर सकते हैं)। उपरोक्त मान्यताओं को बनाने के पश्चात, परिवहन योजना आक्षेप T : M → F है।

शब्दों में, प्रत्येक खदान m ∈ M त्रुटिहीन रूप से लक्ष्य कारखाने T(m) ∈ F की आपूर्ति करती है और प्रत्येक कारखाने की आपूर्ति उचित खान द्वारा की जाती है। हम इष्टतम परिवहन योजना अविष्कार करना चाहते हैं, योजना T जिसकी कुल लागत है:

$c(T):=\sum _{m\in M}c(m,T(m))$

M से F तक सभी संभावित परिवहन योजनाओं में से सबसे कम है। परिवहन समस्या का यह विशेष असाइनमेंट समस्या का उदाहरण है।

अधिक विशेष रूप से, यह द्विपक्षीय ग्राफ में मिलान करने वाले न्यूनतम वजन अविष्कार करने के समान है।

मूविंग बुक्स: लागत फलन का महत्व

निम्नलिखित सरल उदाहरण इष्टतम परिवहन योजना के निर्धारण में लागत फलन के महत्व को दर्शाता है। मान लीजिए कि हमारे निकट शेल्फ (वास्तविक रेखा) पर समान चौड़ाई की n किताबें हैं, जो एक ही सन्निहित ब्लॉक में व्यवस्थित हैं। हम उन्हें सन्निहित ब्लॉक में पुनर्व्यवस्थित करना चाहते हैं, किंतु पुस्तक-चौड़ाई को दाईं ओर स्थानांतरित कर दिया है। इष्टतम परिवहन योजना के लिए दो स्पष्ट प्रत्याशी स्वयं उपस्थित होते हैं:

1. सभी n पुस्तकों को चौड़ाई में दाईं ओर ले जाएं;
2. बाईं ओर वाली n पुस्तक-चौड़ाई को दाईं ओर ले जाएं और अन्य सभी पुस्तकों को नियत छोड़ दें।

यदि लागत फलन यूक्लिडियन दूरी (c(x, y) = α|x − y|) के समानुपाती है, तो ये दोनों प्रत्याशी इष्टतम हैं। यदि, दूसरी ओर, हम यूक्लिडियन दूरी (c(x, y) = α|x − y|² के वर्ग के समानुपातिक रूप से उत्तल लागत फलन का चयन करते है।), तो कई छोटी चालों का विकल्प अद्वितीय मिनिमाइज़र बन जाता है।

ध्यान दें कि उपरोक्त लागत फलन केवल पुस्तकों द्वारा तय की गई क्षैतिज दूरी पर विचार करते हैं, प्रत्येक पुस्तक को उठाने और स्थिति में ले जाने के लिए उपयोग किए जाने वाले उपकरण द्वारा तय की गई क्षैतिज दूरी पर नहीं है। यदि इसके अतिरिक्त उत्तरार्द्ध पर विचार किया जाता है, तो, दो परिवहन योजनाओं में से, दूसरा सदैव यूक्लिडियन दूरी के लिए इष्टतम होता है, जबकि, कम से कम 3 पुस्तकें होने पर, प्रथम परिवहन योजना वर्गित यूक्लिडियन दूरी के लिए इष्टतम होती है।

हिचकॉक समस्या

निम्नलिखित परिवहन समस्या सूत्रीकरण का श्रेय एफ. एल. हिचकॉक को दिया जाता है:

मान लीजिए कि किसी वस्तु के लिए m स्रोत हैं $x_{1},\ldots ,x_{m}$वस्तु के लिए, $a(x_{i})$, x_i और n सिंक पर आपूर्ति की इकाइयां $y_{1},\ldots ,y_{n}$ वस्तु के लिए, आवश्यकता के साथ $b(y_{j})$ y_j है, यदि $a(x_{i},\ y_{j})$ x_i से y_j तक शिपमेंट की इकाई लागत है, तो ऐसा प्रवाह ज्ञात करें जो आपूर्ति से आवश्यकता को पूर्ण करता है और प्रवाह लागत को कम करता है। लॉजिस्टिक्स में इस उदेश्य को डी. आर. फुलकर्सन ने स्वीकार किया और एलआर फोर्ड जूनियर के साथ लिखी गई पुस्तक फ्लोज़ इन नेटवर्क्स (1962) में प्रकाशित की गयी है।

तजालिंग कोपमैन्स को परिवहन अर्थशास्त्र के सूत्रीकरण और संसाधनों के आवंटन का श्रेय भी दिया जाता है।

एक्सेल में संख्यात्मक समाधान

बड़ी संख्या में मार्गों के साथ, समस्या को संख्यात्मक रूप से समाधान किया जाता है।

इनपुट: परिवहन सेल 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-ट्रेडर मूल्य लेने वाला है।

फिर किसी भी कठोरता से लाभदायक मार्ग पर अधिक आवश्यकता होती है, और किसी भी कठोरता से लाभहीन मार्ग पर आवश्यकता शून्य होती है।

आभासी लाभ अधिकतमकरण वीपीएम

प्रत्येक मार्ग पर इकाई लाभ p_j - t_ij -c_i है इनकी गणना तालिका के नीचे दाईं ओर 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

समस्या का सार सूत्रीकरण

मोंज और कांटोरोविच फॉर्मूलेशन

परिवहन समस्या जैसा कि आधुनिक या अधिक तकनीकी साहित्य में कहा गया है, रीमैनियन ज्यामिति और माप सिद्धांत के विकास के कारण कुछ भिन्न दिखती है। खान-कारखानों का उदाहरण, जितना सरल है, सार स्तिथियों के बारे में सोचते समय उपयोगी संदर्भ बिंदु है। इस सेटिंग में, हम संभावना की अनुमति देते हैं कि हम सभी खानों और कारखानों को व्यवसाय के लिए खुला नहीं रखना चाहते हैं, और खानों को एक से अधिक कारखानों की आपूर्ति और कारखानों से लोहा स्वीकार करने की अनुमति देते हैं।

$X$ और $Y$ दो वियोज्य अंतरिक्ष मीट्रिक रिक्त स्थान हों जैसे कि किसी भी संभाव्यता माप पर $X$ (या $Y$) रेडॉन माप है (अर्थात वे रेडॉन स्पेस हैं)। $c:X\times Y\to [0,\infty ]$ बोरेल-मापने योग्य फलन है। संभाव्यता उपायों को देखते हुए $\mu$ पर $X$ और $\nu$ पर $Y$ इष्टतम परिवहन समस्या का मोंज सूत्रीकरण परिवहन मानचित्र अविष्कार करना है जो कि $T:X\to Y$ न्यूनतम है:

$\inf \left\{\left.\int _{X}c(x,T(x))\,\mathrm {d} \mu (x)\;\right|\;T_{*}(\mu )=\nu \right\},$

जहाँ $T_{*}(\mu )$ के आगे पुशफॉरवर्ड माप को दर्शाता है $\mu$ द्वारा $T$ मानचित्र $T$ जो इस न्यूनतम को प्राप्त करता है (अर्थात इसे न्यूनतम बनाता है) जिसे इष्टतम परिवहन मानचित्र कहा जाता है।

इष्टतम परिवहन समस्या मोंज का निरूपण त्रुटिपूर्ण हो सकता है, क्योंकि कभी-कभी ऐसा नहीं होता है $T$ संतोषजनक $T_{*}(\mu )=\nu$: ऐसा होता है, उदाहरण के लिए, जब $\mu$ डायराक उपाय है किंतु $\nu$ क्या नहीं है।

इष्टतम परिवहन समस्या के कांटोरोविच के सूत्रीकरण को अपनाकर हम इस पर सुधार कर सकते हैं, जो कि संभाव्यता उपाय अविष्कार है $\gamma$ पर $X\times Y$ जो न्यूनतम को प्राप्त करता है:

$\inf \left\{\left.\int _{X\times Y}c(x,y)\,\mathrm {d} \gamma (x,y)\right|\gamma \in \Gamma (\mu ,\nu )\right\},$

जहाँ $\Gamma (\mu ,\nu )$ पर सभी संभाव्यता उपायों के संग्रह को दर्शाता है $X\times Y$ सशर्त संभाव्यता के साथ $\mu$ पर $X$ और $\nu$ पर $Y$ यह दिखाया जा सकता है कि लागत फलन होने पर इस समस्या के लिए न्यूनतमकर्ता सदैव उपस्तिथ रहता है $c$ निचला अर्ध-निरंतर है और $\Gamma (\mu ,\nu )$ उपायों का संग्रह है (जो रेडॉन रिक्त स्थान के लिए $X$ और $Y$ विश्वास है) (इस सूत्रीकरण की तुलना वासेरस्टीन मीट्रिक की परिभाषा से करें $W_{1}$ संभाव्यता उपायों के स्थान पर।) मोंगे-कैंटोरोविच समस्या के समाधान के लिए ग्रेडिएंट डिसेंट सूत्रीकरण सिगर्ड एजेंट, स्टीवन हैकर और एलन टैननबौम द्वारा दिया गया था।

द्वैत सूत्र

कांटोरोविच समस्या का न्यूनतम समान है

$\sup \left(\int _{X}\varphi (x)\,\mathrm {d} \mu (x)+\int _{Y}\psi (y)\,\mathrm {d} \nu (y)\right),$

जहां अंतिम बंधे हुए कार्य और निरंतर कार्यों के सभी जोड़े पर चलता है $\varphi :X\rightarrow \mathbf {R}$ और $\psi :Y\rightarrow \mathbf {R}$ ऐसा है कि

$\varphi (x)+\psi (y)\leq c(x,y).$

आर्थिक व्याख्या

यदि संकेत फ़्लिप किए जाते हैं तो आर्थिक व्याख्या स्पष्ट होती है। होने देना ${\textstyle x\in X}$ एक कार्यकर्ता की विशेषताओं के सदिश के लिए खड़े हो जाओ, ${\textstyle y\in Y}$ एक फर्म की विशेषताओं के वेक्टर के लिए, और ${\textstyle \Phi (x,y)=-c(x,y)}$ कार्यकर्ता द्वारा उत्पन्न आर्थिक उत्पादन के लिए ${\textstyle x}$ फर्म से मेल खाता है ${\textstyle y}$. सेटिंग ${\textstyle u(x)=-\varphi (x)}$ और ${\textstyle v(y)=-\psi (y)}$मोंगे-कांटोरोविच समस्या फिर से लिखता है:

$$\sup \left\{\int _{X\times Y}\Phi (x,y)d\gamma (x,y),\gamma \in \Gamma (\mu ,\nu )\right\}$$

जिसमें द्वैत है (अनुकूलन):

$$\inf \left\{\int _{X}u(x)\,d\mu (x)+\int _{Y}v(y)\,d\nu (y):u(x)+v(y)\geq \Phi (x,y)\right\}$$

जहां इन्फिमम सीमित और निरंतर कार्य करता है ${\textstyle u:X\rightarrow \mathbf {R} }$ और ${\textstyle v:Y\rightarrow \mathbf {R} }$. यदि दोहरी समस्या का समाधान है, तो कोई यह देख सकता है कि:

$$v(y)=\sup _{x}\left\{\Phi (x,y)-u(x)\right\}$$

जिससे कि ${\textstyle u(x)}$ प्रकार के कार्यकर्ता के संतुलन वेतन के रूप में व्याख्या करता है ${\textstyle x}$, और ${\textstyle v(y)}$ एक प्रकार की फर्म के संतुलन लाभ के रूप में व्याख्या करता है ${\textstyle y}$.

समस्या का समाधान

वास्तविक लाइन पर इष्टतम परिवहन

Optimal transportation matrix

Continuous optimal transport

के लिए $1\leq p<\infty$, होने देना ${\mathcal {P}}_{p}(\mathbf {R} )$ संभाव्यता उपायों के संग्रह को निरूपित करें $\mathbf {R}$ कि परिमित है $p$-वाँ क्षण (गणित)। होने देना $\mu ,\nu \in {\mathcal {P}}_{p}(\mathbf {R} )$ और जाने $c(x,y)=h(x-y)$, जहाँ $h:\mathbf {R} \rightarrow [0,\infty )$ उत्तल कार्य है।

1. यदि $\mu$ कोई परमाणु नहीं है (माप सिद्धांत), अर्थात, यदि संचयी वितरण कार्य करता है $F_{\mu }:\mathbf {R} \rightarrow [0,1]$ का $\mu$ एक सतत कार्य है, फिर $F_{\nu }^{-1}\circ F_{\mu }:\mathbf {R} \to \mathbf {R}$ एक इष्टतम परिवहन मानचित्र है। यह अद्वितीय इष्टतम परिवहन मानचित्र है यदि $h$ कठोरता से उत्तल है।
2. अपने निकट

$\min _{\gamma \in \Gamma (\mu ,\nu )}\int _{\mathbf {R} ^{2}}c(x,y)\,\mathrm {d} \gamma (x,y)=\int _{0}^{1}c\left(F_{\mu }^{-1}(s),F_{\nu }^{-1}(s)\right)\,\mathrm {d} s.$

इस समाधान का प्रमाण राचेव एंड रुशचेंडॉर्फ (1998) में दिखाई देता है।

असतत संस्करण और रैखिक प्रोग्रामिंग सूत्रीकरण

स्तिथियों में जहां मार्जिन ${\textstyle \mu }$ और ${\textstyle \nu }$ असतत हैं, चलो ${\textstyle \mu _{x}}$ और ${\textstyle \nu _{y}}$ संभाव्यता द्रव्यमान क्रमशः असाइन करें ${\textstyle x\in \mathbf {X} }$ और ${\textstyle y\in \mathbf {Y} }$, और जाने ${\textstyle \gamma _{xy}}$ एक की संभावना हो ${\textstyle xy}$ कार्यभार। प्राइमल कांटोरोविच समस्या में वस्तुनिष्ठ कार्य तब है

$\sum _{x\in \mathbf {X} ,y\in \mathbf {Y} }\gamma _{xy}c_{xy}$

और बाधा ${\textstyle \gamma \in \Gamma \left(\mu ,\nu \right)}$ रूप में व्यक्त करता है

$\sum _{y\in \mathbf {Y} }\gamma _{xy}=\mu _{x},\forall x\in \mathbf {X}$

और

$\sum _{x\in \mathbf {X} }\gamma _{xy}=\nu _{y},\forall y\in \mathbf {Y} .$

एक रैखिक प्रोग्रामिंग समस्या में इसे इनपुट करने के लिए, हमें मैट्रिक्स को वैश्वीकरण (गणित) करने की आवश्यकता है ${\textstyle \gamma _{xy}}$ पंक्ति और स्तंभ-प्रमुख क्रम को स्टैक करके, हम कॉल करते हैं ${\textstyle \operatorname {vec} }$ यह ऑपरेशन। पंक्ति- और स्तंभ-प्रमुख क्रम में | स्तंभ-प्रमुख क्रम में, ऊपर दी गई बाधाएँ इस रूप में फिर से लिखती हैं

$\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$ और $\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$

जहाँ ${\textstyle \otimes }$ क्रोनकर उत्पाद है, ${\textstyle 1_{n\times m}}$ आकार का एक मैट्रिक्स है ${\textstyle n\times m}$ सभी प्रविष्टियों के साथ, और ${\textstyle I_{n}}$ आकार की पहचान मैट्रिक्स है ${\textstyle n}$. परिणाम स्वरुप, सेटिंग ${\textstyle z=\operatorname {vec} \left(\gamma \right)}$, समस्या का रैखिक प्रोग्रामिंग सूत्रीकरण है

${\begin{aligned}&{\text{Minimize }}\operatorname {vec} (c)^{\top }z\\[4pt]&{\text{subject to:}}\\[4pt]&z\geq 0\\[4pt]&{\begin{pmatrix}1_{1\times \left\vert \mathbf {Y} \right\vert }\otimes I_{\left\vert \mathbf {X} \right\vert }\\I_{\left\vert \mathbf {Y} \right\vert }\otimes 1_{1\times \left\vert \mathbf {X} \right\vert }\end{pmatrix}}\\[4pt]&z={\binom {\mu }{\nu }}\end{aligned}}$

जिसे बड़े पैमाने पर रैखिक प्रोग्रामिंग सॉल्वर में आसानी से इनपुट किया जा सकता है (गैलिचॉन (2016) का अध्याय 3.4 देखें)).

सेमी-असतत मामला

अर्द्ध असतत स्तिथियों में, ${\textstyle X=Y=\mathbf {R} ^{d}}$ और ${\textstyle \mu }$ पर एक सतत वितरण है ${\textstyle \mathbf {R} ^{d}}$, जबकि ${\textstyle \nu =\sum _{j=1}^{J}\nu _{j}\delta _{y_{i}}}$ एक असतत वितरण है जो संभाव्यता द्रव्यमान प्रदान करता है ${\textstyle \nu _{j}}$ साइट को ${\textstyle y_{j}\in \mathbf {R} ^{d}}$. इस स्तिथियों में हम देख सकते हैं कि मूल और दोहरी कांटोरोविच समस्याएं क्रमशः कम हो जाती हैं:

$$\inf \left\{\int _{X}\sum _{j=1}^{J}c(x,y_{j})\,d\gamma _{j}(x),\gamma \in \Gamma (\mu ,\nu )\right\}$$

मौलिक के लिए, जहां ${\textstyle \gamma \in \Gamma \left(\mu ,\nu \right)}$ मतलब कि ${\textstyle \int _{X}d\gamma _{j}\left(x\right)=\nu _{j}}$ और ${\textstyle \sum _{j}d\gamma _{j}\left(x\right)=d\mu \left(x\right)}$, और:

$$\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\}$$

दोहरे के लिए, जिसे फिर से लिखा जा सकता है:

$$\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\}$$

जो एक परिमित-आयामी उत्तल अनुकूलन समस्या है जिसे मानक तकनीकों, जैसे ढाल वंश द्वारा समाधानकिया जा सकता है।

स्तिथियों में जब ${\textstyle c\left(x,y\right)=\left\vert x-y\right\vert ^{2}/2}$, कोई दिखा सकता है कि का सेट ${\textstyle x\in \mathbf {X} }$ किसी विशेष साइट को सौंपा गया ${\textstyle j}$ एक उत्तल बहुफलक है। परिणामी कॉन्फ़िगरेशन को पावर आरेख कहा जाता है।

द्विघात सामान्य मामला

विशेष मामला मान लें ${\textstyle \mu ={\mathcal {N}}\left(0,\Sigma _{X}\right)}$, ${\textstyle \nu ={\mathcal {N}}\left(0,\Sigma _{Y}\right)}$, और ${\textstyle c(x,y)=\left\vert y-Ax\right\vert ^{2}/2}$ जहाँ ${\textstyle A}$ उलटा है। एक तो है

$\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$

$\psi (y)=-y^{\top }A\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}Ay/2$

$T(x)=(A^{\top })^{-1}\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}$

इस समाधान का प्रमाण गैलिचोन (2016) में दिखाई देता है।

वियोज्य हिल्बर्ट रिक्त स्थान

होने देना $X$ एक वियोज्य स्थान हो हिल्बर्ट स्थान। होने देना ${\mathcal {P}}_{p}(X)$ संभाव्यता उपायों के संग्रह को निरूपित करें $X$ कि परिमित है $p$-वाँ क्षण; होने देना ${\mathcal {P}}_{p}^{r}(X)$ उन तत्वों को निरूपित करें $\mu \in {\mathcal {P}}_{p}(X)$ जो गाऊसी नियमित हैं: यदि $g$ गॉसियन माप पर कोई कठोरता से सकारात्मक उपाय है $X$ और $g(N)=0$, तब $\mu (N)=0$ भी।

होने देना $\mu \in {\mathcal {P}}_{p}^{r}(X)$, $\nu \in {\mathcal {P}}_{p}(X)$, $c(x,y)=|x-y|^{p}/p$ के लिए $p\in (1,\infty ),p^{-1}+q^{-1}=1$. तब कांटोरोविच समस्या का एक अनूठा समाधान है $\kappa$, और यह समाधान इष्टतम परिवहन मानचित्र से प्रेरित है: अर्थात, एक बोरेल नक्शा उपस्तिथ है $r\in L^{p}(X,\mu ;X)$ ऐसा है कि

$\kappa =(\mathrm {id} _{X}\times r)_{*}(\mu )\in \Gamma (\mu ,\nu ).$

इसके अतिरिक्त, यदि $\nu$ बंधा हुआ सेट सपोर्ट (माप सिद्धांत) है, फिर

$r(x)=x-|\nabla \varphi (x)|^{q-2}\,\nabla \varphi (x)$

के लिए $\mu$-लगभग सभी $x\in X$ कुछ लिप्सचिट्ज़ निरंतर, सी-अवतल और अधिकतम कांटोरोविच क्षमता के लिए $\varphi$. (यहाँ $\nabla \varphi$ के गेटॉक्स व्युत्पन्न को दर्शाता है $\varphi$.)

एंट्रोपिक नियमितीकरण

उपरोक्त असतत समस्या के एक प्रकार पर विचार करें, जहां हमने मूल समस्या के उद्देश्य समारोह में एक एंट्रोपिक नियमितीकरण शब्द जोड़ा है

${\begin{aligned}&{\text{Minimize }}\sum _{x\in \mathbf {X} ,y\in \mathbf {Y} }\gamma _{xy}c_{xy}+\varepsilon \gamma _{xy}\ln \gamma _{xy}\\[4pt]&{\text{subject to: }}\\[4pt]&\gamma \geq 0\\[4pt]&\sum _{y\in \mathbf {Y} }\gamma _{xy}=\mu _{x},\forall x\in \mathbf {X} \\[4pt]&\sum _{x\in \mathbf {X} }\gamma _{xy}=\nu _{y},\forall y\in \mathbf {Y} \end{aligned}}$

कोई दिखा सकता है कि दोहरी नियमित समस्या है

$\max _{\varphi ,\psi }\sum _{x\in \mathbf {X} }\varphi _{x}\mu _{x}+\sum _{y\in \mathbf {Y} }\psi _{y}v_{y}-\varepsilon \sum _{x\in \mathbf {X} ,y\in \mathbf {Y} }\exp \left({\frac {\varphi _{x}+\psi _{y}-c_{xy}}{\varepsilon }}\right)$

जहां, अनियमित संस्करण की तुलना में, पूर्व दोहरी में कठिन बाधा (${\textstyle \varphi _{x}+\psi _{y}-c_{xy}\geq 0}$) को उस बाधा के नरम दंड द्वारा प्रतिस्थापित किया गया है ( ${\textstyle \varepsilon \exp \left((\varphi _{x}+\psi _{y}-c_{xy})/\varepsilon \right)}$ शर्तें )। दोहरी समस्या में इष्टतमता की स्थिति के रूप में व्यक्त किया जा सकता है

Eq. 5.1: $\mu _{x}=\sum _{y\in \mathbf {Y} }\exp \left({\frac {\varphi _{x}+\psi _{y}-c_{xy}}{\varepsilon }}\right)~\forall x\in \mathbf {X}$

Eq. 5.2: $\nu _{y}=\sum _{x\in \mathbf {X} }\exp \left({\frac {\varphi _{x}+\psi _{y}-c_{xy}}{\varepsilon }}\right)~\forall y\in \mathbf {Y}$

दर्शाने ${\textstyle A}$ के रूप में ${\textstyle \left\vert \mathbf {X} \right\vert \times \left\vert \mathbf {Y} \right\vert }$ पद का मैट्रिक्स ${\textstyle A_{xy}=\exp \left(-c_{xy}/\varepsilon \right)}$, इसलिए द्वैत को समाधानकरना दो विकर्ण धनात्मक आव्यूहों को अविष्कारने के समान है ${\textstyle D_{1}}$ और ${\textstyle D_{2}}$ संबंधित आकार के ${\textstyle \left\vert \mathbf {X} \right\vert }$ और ${\textstyle \left\vert \mathbf {Y} \right\vert }$, ऐसा है कि ${\textstyle D_{1}AD_{2}1_{\left\vert \mathbf {Y} \right\vert }=\mu }$ और ${\textstyle \left(D_{1}AD_{2}\right)^{\top }1_{\left\vert \mathbf {X} \right\vert }=\nu }$. ऐसे मैट्रिसेस का अस्तित्व सिंकहॉर्न के प्रमेय को सामान्य करता है और सिंकहॉर्न के प्रमेय का उपयोग करके मैट्रिसेस की गणना की जा सकती है # सिंकहॉर्न-नॉप्प एल्गोरिथम। जिसमें केवल पुनरावृत्ति की तलाश होती है ${\textstyle \varphi _{x}}$ समाधान करना Equation 5.1, और ${\textstyle \psi _{y}}$ समाधान करना Equation 5.2. इसलिए सिंकहोर्न-नोप का एल्गोरिथम दोहरी नियमित समस्या पर एक समन्वित डिसेंट एल्गोरिथम है।

अनुप्रयोग

Monge-Kantorovich इष्टतम परिवहन ने विभिन्न क्षेत्रों में व्यापक श्रेणी में आवेदन पाया है। उनमें से हैं:

• छवि पंजीकरण और ताना-बाना
• परावर्तक डिजाइन
• एक्स-रे फ़ोटो और प्रोटॉन रेडियोग्राफी से जानकारी प्राप्त करना
• भूकंपीय टोमोग्राफी और प्रतिबिंब भूकंप विज्ञान
• अर्थशास्त्र मॉडलिंग का व्यापक वर्ग जिसमें सकल स्थानापन्न संपत्ति (दूसरों के बीच, स्थिर मिलान सिद्धांत और असतत पसंद के मॉडल) सम्मिलित हैं।

यह भी देखें

• वासेरस्टीन मीट्रिक
• परिवहन समारोह
• हंगेरियन एल्गोरिथम
• परिवहन योजना
• पृथ्वी मूवर की दूरी
• मोंज-एम्पीयर समीकरण

अग्रिम पठन

• 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.