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

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

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

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

प्रेरणा

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

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

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

एम से एफ तक सभी संभावित परिवहन योजनाओं में से सबसे कम है। परिवहन समस्या का यह प्रेरक विशेष मामला असाइनमेंट समस्या का एक उदाहरण है। अधिक विशेष रूप से, यह द्विपक्षीय ग्राफ में मिलान करने वाले न्यूनतम वजन को अविष्कारने के बराबर है।

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

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

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

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

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

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

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

मान लीजिए कि एम स्रोत हैं $x_{1},\ldots ,x_{m}$ एक वस्तु के लिए, के साथ $a(x_{i})$ एक्स पर आपूर्ति की इकाइयां_i और n डूबता है $y_{1},\ldots ,y_{n}$ वस्तु के लिए, मांग के साथ $b(y_{j})$ वाई पर_j. यदि $a(x_{i},\ y_{j})$ x से शिपमेंट की इकाई लागत है_i यह वाई है_j, एक प्रवाह अविष्कारें जो आपूर्ति से मांग को पूरा करता है और प्रवाह लागत को कम करता है। लॉजिस्टिक्स में इस चुनौती को डी. आर. फुलकर्सन ने स्वीकार किया और एलआर फोर्ड जूनियर के साथ लिखी गई पुस्तक फ्लो इन नेटवर्क्स (1962) में।

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

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

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

इनपुट: परिवहन सेल T हैं। आपूर्ति डेटा सेल एस हैं। डिमांड डेटा सेल डी हैं।

आपूर्ति की प्रत्येक इकाई को एक बड़े बॉक्स (एक शिपिंग कंटेनर) के रूप में सोचें।

आउटपुट: शिपमेंट योजना 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 और एक वर्चुअल ट्रेडर प्रस्तुत करता है।

वर्चुअल ट्रेडर वास्तविक प्रभाव प्रदान करता है।

महत्वपूर्ण रूप से, वी-ट्रेडर एक मूल्य लेने वाला है।

फिर किसी भी सख्ती से लाभदायक मार्ग पर अधिक मांग होगी और किसी भी सख्ती से लाभहीन मार्ग पर मांग शून्य होगी।

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

प्रत्येक मार्ग पर इकाई लाभ p है_j - टी_ij -सी_i इनकी गणना तालिका के नीचे दाईं ओर V-PROFIT बॉक्स में की जाती है।

(यदि आप एक्सेल के साथ काम कर रहे हैं, तो इन सूत्रों को अंकित करें और फिर संख्यात्मक रूप से परिकलित अधिकतम के लिए सॉल्वर का उपयोग करें।)

उपयोग किए गए सभी मार्गों पर लाभ शून्य होना चाहिए और कोई भी मार्ग निश्चित रूप से लाभप्रद नहीं है।

चरण 1: नीचे की तरह एक तालिका बनाएँ। तालिका में छोटी संख्याएँ डेटा बिंदु हैं। बड़ी बोल्ड संख्याएँ चर हैं।

प्रत्येक कॉलम में V-PRICE कम से कम VPM को संतुष्ट करने के लिए न्यूनतम लागत होनी चाहिए।

	A	B	D				E	F	G	H	I
1			वी-प्रिंसेस				5		5
				वी-कॉस्ट			P1		P2
												वी-प्रॉफिट
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-COSTS और V-कीमतें चुनें जिससे कि वी-ट्रेडर सभी सक्रिय रूटों पर बराबरी पर आ जाए।

सबसे कम प्रविष्टियों वाले कॉलम से प्रारंभ करें (कॉलम 2)

वी-सुडोकू

वी-लागतों को प्रारंभ में 2 (शून्य) खाली छोड़ दिया जाता है। कॉलम 2 में ब्रेक इवेन के लिए, P2 = C2 + T22 = 0 + 5 = 5

कॉलम 1 में दोनों मार्गों का उपयोग किया जाता है। चूँकि C2 शून्य है, C1 = 1। तब P1=C1 + T21 =5

V-चेक यदि आप इस V-PUZZLE को एक स्प्रेडशीट पर सेट करते हैं, तो प्रॉफिट बॉक्स पहले ही भर जाएगा।

वी-कीमतों का वास्तविक मूल्य

आपूर्ति:

यदि आप S1 पर आपूर्ति की एक इकाई जोड़ते हैं तो आप सेल [S1:C2] में 1 जोड़कर और सेल [S2;C2] से 1 घटाकर परिवहन लागत को कम कर सकते हैं।

यह शिपिंग लागत को 1 से कम करता है, यह C1 का अर्थ है। यदि फर्म 1 से कम पर एक अतिरिक्त कंटेनर किराए पर ले सकती है (एक हजार सोचें) तो अतिरिक्त लागत बचत होती है।

यदि आप इसे S2 पर आजमाते हैं, तो अतिरिक्त कंटेनर शिपिंग लागत को कम नहीं करता है। यह C1 का अर्थ है।

माँग:

यदि उत्पाद की एक और इकाई स्थानीय रूप से (गंतव्य पर) प्राप्त की जा सकती है तो शिपिंग लागत में क्या कमी आएगी।

D1 को एक इकाई से कम करने का प्रयास करें। शिपिंग लागत कितनी गिरती है...? हाँ, V-PRICE द्वारा

वी-वर्चुअल ट्रेडर पद्धति का उपयोग करने से आभासी मूल्य और वास्तविक महत्व की लागत प्राप्त होती है।

प्रोग्रामिंग नोट:

यदि आप एक्सेल ऐड-इन <बिग>एसओल्वर जैसे कैन्ड मैक्सिमाइज़िंग प्रोग्राम का उपयोग करते हैं, तो यह एक फ्लैश में सही उत्तर प्राप्त करेगा।

यदि आप लग्रेंज मल्टीप्लायरों या छाया मूल्यों को देखते हैं जो एक संवेदनशीलता रिपोर्ट में दिखाई दे सकते हैं, तो वे भ्रामक हो सकते हैं।

चूंकि सॉल्वर समाधान प्रदान करता है, आपको बस इतना करना है कि वी-कॉस्ट और वी-कीमतों के लिए सुडोकू आपके लिए है।

यहां 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.