نظرية النقل (الرياضيات)

لنفترض أن لدينا مجموعة من${\displaystyle m}$مناجم تستخرج خام الحديد، ومجموعة من${\displaystyle n}$المصانع التي تستخدم خام الحديد الذي تنتجه المناجم. لنفترض جدلاً أن هذه المناجم والمصانع تشكل مجموعتين فرعيتين منفصلتين.${\displaystyle M}$و${\displaystyle F}$المستوى الإقليدي${\displaystyle \mathbb {R} ^{2}}$لنفترض أيضاً أن لدينا دالة تكلفة${\displaystyle c:\mathbb {R} ^{2}\times \mathbb {R} ^{2}\to [0,\infty )}$، لهذا السبب${\displaystyle c(x,y)}$تكلفة نقل شحنة واحدة من الحديد من${\displaystyle x}$ل${\displaystyle y}$لتبسيط الأمور، نتجاهل الوقت المستغرق في النقل. نفترض أيضًا أن كل منجم لا يستطيع تزويد سوى مصنع واحد (دون تقسيم الشحنات)، وأن كل مصنع يحتاج إلى شحنة واحدة فقط ليعمل (لا يمكن للمصانع العمل بنصف طاقتها أو ضعفها). بناءً على هذه الافتراضات، تصبح خطة النقل تقابلًا.${\displaystyle T:M\to F}$بمعنى آخر، كل منجم${\displaystyle m\in M}$يزود مصنعًا مستهدفًا واحدًا فقط${\displaystyle T(m)\in F}$ويتم تزويد كل مصنع من منجم واحد فقط. نرغب في إيجاد خطة النقل الأمثل ، الخطة${\displaystyle T}$تكلفتها الإجمالية

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

وهو أقل ما يمكن أن تقدمه خطط النقل من${\displaystyle M}$ل${\displaystyle F}$تُعدّ هذه الحالة الخاصة المحفزة لمسألة النقل مثالاً على مسألة التخصيص . وبشكل أكثر تحديداً، فهي تُعادل إيجاد تطابق بأقل وزن في رسم بياني ثنائي الأجزاء .

يمكن تعميم هذا على الحالة المتصلة، حيث يوجد عدد لا نهائي من المناجم والمصانع موزعة على خط الأعداد الحقيقية، أو بشكل عام في أي فضاء متري. تُصوَّر هذه الحالة عادةً على أنها "تغيير شكل كومة من التراب"، ولذلك تُسمى مسألة جرافة الأرض .

يوضح المثال البسيط التالي أهمية دالة التكلفة في تحديد خطة النقل المثلى. لنفترض أن لدينا${\displaystyle n}$كتب متساوية العرض موضوعة على رف ( خط الأعداد الحقيقية )، مرتبة في كتلة متصلة واحدة. نريد إعادة ترتيبها في كتلة متصلة أخرى، ولكن مع إزاحتها بمقدار عرض كتاب واحد إلى اليمين. يبرز خياران واضحان لخطة النقل المثلى:

1. نقل الكل${\displaystyle n}$الكتب بعرض كتاب واحد إلى اليمين ("حركات صغيرة كثيرة")؛
2. انقل الكتاب الموجود في أقصى اليسار${\displaystyle n}$عرض الكتب إلى اليمين وترك جميع الكتب الأخرى ثابتة ("حركة كبيرة واحدة").

إذا كانت دالة التكلفة تتناسب مع المسافة الإقليدية (${\displaystyle c(x,y)=\alpha \|x-y\|}$بالنسبة للبعض${\displaystyle \alpha >0}$إذاً، فإن هذين المرشحين كلاهما مثاليان. أما إذا اخترنا، من ناحية أخرى، دالة التكلفة المحدبة تماماً والمتناسبة مع مربع المسافة الإقليدية (${\displaystyle c(x,y)=\alpha \|x-y\|^{2}}$بالنسبة للبعض${\displaystyle \alpha >0}$ثم يصبح خيار "العديد من التحركات الصغيرة" هو الخيار الأمثل لتقليل الخطأ.

لاحظ أن دوال التكلفة المذكورة أعلاه لا تأخذ في الحسبان سوى المسافة الأفقية التي تقطعها الكتب، وليس المسافة الأفقية التي تقطعها الآلة المستخدمة لالتقاط كل كتاب ونقله إلى مكانه. إذا أُخذت المسافة الأفقية في الحسبان، فإن خطة النقل الثانية هي الأمثل دائمًا من حيث المسافة الإقليدية، بينما تكون خطة النقل الأولى هي الأمثل من حيث مربع المسافة الإقليدية، شريطة وجود ثلاثة كتب على الأقل.

يُنسب صياغة مشكلة النقل التالية إلى إف إل هيتشكوك : ^{[ 7 ]}

لنفترض أن هناك${\displaystyle m}$مصادر${\displaystyle x_{1},\ldots ,x_{m}}$بالنسبة لسلعة، مع${\displaystyle a(x_{i})}$وحدات التوريد في${\displaystyle x_{i}}$و${\displaystyle n}$أحواض الغسيل${\displaystyle y_{1},\ldots ,y_{n}}$بالنسبة للسلعة، مع الطلب${\displaystyle b(y_{j})}$في${\displaystyle y_{j}}$. لو${\displaystyle c(x_{i},\ y_{j})}$هي تكلفة الشحن للوحدة من${\displaystyle x_{i}}$ل${\displaystyle y_{j}}$إيجاد تدفق يلبي الطلب من الإمدادات ويقلل من تكلفة التدفق. وقد تناول هذا التحدي في مجال الخدمات اللوجستية د. ر. فولكرسون ^{[ 8 ]} في كتابه " التدفقات في الشبكات " (1962) الذي شارك في تأليفه مع ل. ر. فورد الابن ^{[ 9 ].}

يُنسب إلى تجالينج كوبمانز أيضاً وضع صياغات لاقتصاديات النقل وتخصيص الموارد.

تختلف مشكلة النقل، كما وردت في الأدبيات الحديثة أو المتخصصة، نوعًا ما نتيجة لتطور الهندسة الريمانية ونظرية القياس . ويُعد مثال المناجم والمصانع، على بساطته، مرجعًا مفيدًا عند التفكير في الحالة المجردة. في هذا السياق، نفترض إمكانية عدم رغبتنا في إبقاء جميع المناجم والمصانع مفتوحة، ونسمح للمناجم بتزويد أكثر من مصنع، وللمصانع باستلام الحديد من أكثر من منجم.

يترك${\displaystyle X}$و${\displaystyle Y}$ليكن فضاءان متريان قابلان للفصل بحيث يكون أي مقياس احتمالي على${\displaystyle X}$(أو${\displaystyle Y}$) هو مقياس رادون (أي أنها فضاءات رادون ). ليكن${\displaystyle c:X\times Y\to [0,\infty )}$لتكن دالة قابلة للقياس وفقًا لبوريل . مع الأخذ في الاعتبار مقاييس الاحتمال${\displaystyle \mu }$على${\displaystyle X}$و${\displaystyle \nu }$على${\displaystyle Y}$تتمثل صياغة مونج لمشكلة النقل الأمثل في إيجاد خريطة نقل${\displaystyle T:X\to Y}$الذي يحقق الحد الأدنى

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

أين${\displaystyle T_{*}(\mu )}$يشير إلى الدفع إلى الأمام${\displaystyle \mu }$بواسطة${\displaystyle T}$خريطة${\displaystyle T}$يُطلق على ما يصل إلى هذا الحد الأدنى ( أي يجعله الحد الأدنى بدلاً من الحد الأدنى) اسم "خريطة النقل المثلى".

قد تكون صياغة مونج لمسألة النقل الأمثل غير محددة جيدًا، لأنه في بعض الأحيان لا يوجد${\displaystyle T}$مُرضٍ${\displaystyle T_{*}(\mu )=\nu }$يحدث هذا، على سبيل المثال، عندما${\displaystyle \mu }$هو مقياس ديراك ولكن${\displaystyle \nu }$ليس كذلك.

يمكننا تحسين ذلك من خلال تبني صياغة كانتوروفيتش لمسألة النقل الأمثل، والتي تتمثل في إيجاد مقياس احتمالي${\displaystyle \gamma }$على${\displaystyle X\times Y}$الذي يصل إلى الحد الأدنى

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

أين${\displaystyle \Gamma (\mu ,\nu )}$يشير إلى مجموعة جميع مقاييس الاحتمال على${\displaystyle X\times Y}$مع الهوامش${\displaystyle \mu }$على${\displaystyle X}$و${\displaystyle \nu }$على${\displaystyle Y}$.

بافتراض دالة التكلفة${\displaystyle c(x,y)}$ينتج عنه تحويل ثنائي${\displaystyle \psi \mapsto \psi ^{c}}$محدد بواسطة$${\displaystyle \psi ^{c}(y):=\inf _{x}(c(x,y)-\psi (x))}$$هذا يعمم تحويل ليجندر ، وهو الحالة التي${\displaystyle c(x,y)=-xy}$مع قلب اللافتة.

${\displaystyle \leq 1}$.

نقول إن الدالة${\displaystyle \psi }$يكون محدبًا من الدرجة c إذا${\displaystyle \psi =\varphi ^{c}}$بالنسبة للبعض${\displaystyle \varphi }$لاحظ ذلك لأن${\displaystyle \varphi ^{ccc}=\varphi ^{c}}$يمكننا دائماً أن نفترض أن${\displaystyle \varphi }$هي دالة محدبة من الدرجة c . التحدب من الدرجة c للدالة${\displaystyle \psi }$يكون${\displaystyle \psi ^{cc}}$أو بعبارة أخرى، هي أصغر دالة محدبة من الرتبة c${\displaystyle \psi '}$بحيث${\displaystyle \psi '\geq \psi }$نقطة بنقطة. ^{[ 10 ] : الخاصية 5.8} كما هو الحال في التحويل المحدب،${\displaystyle \psi }$يكون محدبًا من النوع c إذا وفقط إذا${\displaystyle \psi =\psi ^{cc}}$.

لو${\displaystyle \psi =\varphi ^{c}:X\to \mathbb {R} }$إذا كانت دالة محدبة من الرتبة c ، فإن مجموعة التفاضلات الجزئية من الرتبة c لـ${\displaystyle \psi }$في${\displaystyle x\in X}$هي مجموعة${\displaystyle y\in Y}$بحيث${\displaystyle \psi (x)=c(x,y)-\varphi (y)}$وبالمثل بالنسبة لـ${\displaystyle Y}$.

متى${\displaystyle X=Y}$الرسم البياني${\displaystyle (y,\psi ^{c}(y))}$يمكن إنشاء الرسم البياني على النحو التالي: خذ الرسم البياني لـ${\displaystyle \psi }$ثم اقلبها رأسًا على عقب. عند كل نقطة${\displaystyle (x,-\psi (x))}$، قم بإنشاء رسم بياني لـ${\displaystyle y\mapsto c(x,y)}$بلغت ذروتها عند${\displaystyle (x,-\psi (x))}$أي أنه الرسم البياني لـ${\displaystyle y\mapsto c(x,y)-\psi (x)}$نحصل على مجموعة كاملة من هذه الرسوم البيانية. غلاف الحافة السفلية لها هو الرسم البياني لـ${\displaystyle \psi ^{c}}$.

في الصورة نفسها، يمكننا أن نرى ما يعنيه ذلك بالنسبة للدالة.${\displaystyle \varphi (y)}$أن يكون محدبًا من الدرجة c . يكون محدبًا من الدرجة c إذا وفقط إذا كان من الممكن "لمس" رسمه البياني بالكامل بواسطة " أداة ذات طرف مدبب " تتحرك وتتغير شكلها. عندما تكون الأداة ذات الطرف المدبب في${\displaystyle x}$، وله شكل${\displaystyle y\mapsto c(x,y)}$ويرتفع إلى ارتفاع${\displaystyle -\psi (x)}$رسم بياني للتحدب من الرتبة ج${\displaystyle \varphi ^{cc}(y)}$يتم إنشاء ذلك عن طريق تشغيل الأداة ذات الطرف بحيث يتم خفضها قدر الإمكان، مع استمرار ملامستها للرسم البياني لـ${\displaystyle \varphi (y)}$في الجانب العلوي. الغلاف السفلي الذي تم مسحه بواسطة الأداة ذات الطرف المدبب هو الرسم البياني لـ${\displaystyle \varphi ^{cc}(y)}$[ ^{10 ] : الشكل 5.2}

على سبيل المثال، إذا${\displaystyle X=Y=\mathbb {R} ^{n}}$هو فضاء متري و${\displaystyle c(x,y)=\|x-y\|}$، ثم${\displaystyle \varphi :X\to \mathbb {R} }$تكون الدالة محدبة من الدرجة c إذا وفقط إذا كانت تحقق شرط ليبشيتز -1 . يُستخدم هذا الشرط في تعريف مسافة واسرشتين -1 .${\displaystyle c(x,y)=\|x-y\|^{2}}$، ثم${\displaystyle \varphi }$يكون الشكل محدبًا من الدرجة c إذا وفقط إذا كان من الممكن لمس رسمه البياني من الأعلى بواسطة أداة ذات طرف مدبب على شكل قطع مكافئ .

في ظل افتراضات متساهلة إلى حد ما، توجد خطة نقل مثالية.

لو

• ${\displaystyle (X,\mu _{X}),(Y,\mu _{Y})}$هي فضاءات احتمالية بولندية ،
• ${\displaystyle c:X\times Y\to \mathbb {R} \cup \{\infty \}}$شبه متصلة من الأسفل ،
• وتوجد بعض الدوال شبه المتصلة من الأعلى${\displaystyle a\in L^{1}(\mu _{X}),b\in L^{1}(\mu _{Y})}$من النوع${\displaystyle a:X\to \mathbb {R} \cup \{-\infty \},\;b:Y\to \mathbb {R} \cup \{-\infty \}}$بحيث${\displaystyle c(x,y)\geq a(x)+b(y)}$،

إذن، توجد خطة نقل مثالية . أي أنها موجودة.${\displaystyle \gamma ^{*}\in \Gamma (\mu _{X},\mu _{Y})}$بحيث يصل إلى الحد الأدنى. ^{[ 10 ] : نظرية 4.1}

لاحظ أن الحد الأدنى قد يكون لانهائيًا إذا تبين أن جميع خطط النقل لانهائية. على سبيل المثال، إذا${\displaystyle X=Y=\mathbb {R} ,c(x,y)=|x-y|,\;\mu _{X}}$هو توزيع كوشي ، و${\displaystyle \mu _{Y}=\delta _{0}}$.

لو

• ${\displaystyle (X,\mu _{X}),(Y,\mu _{Y})}$هي فضاءات احتمالية بولندية،
• ${\displaystyle c:X\times Y\to \mathbb {R} }$هي شبه متصلة سفلية،
• توجد بعض الدوال شبه المتصلة العليا${\displaystyle a\in L^{1}(\mu _{X}),b\in L^{1}(\mu _{Y})}$من النوع${\displaystyle a:X\to \mathbb {R} ,\;b:Y\to \mathbb {R} }$بحيث${\displaystyle c(x,y)\geq a(x)+b(y)}$،
• توجد خطة نقل ذات تكلفة محدودة،
• ولأي دالة محدبة من الرتبة c${\displaystyle \psi :X\to \mathbb {R} \cup \{\infty \}}$، ل${\displaystyle \mu _{X}}$-جميعهم تقريبًا${\displaystyle x\in X}$،${\displaystyle \psi }$له تفاضل فرعي فريد من نوعه من النوع c عند${\displaystyle x}$

إذن توجد خريطة نقل مثالية . ^{[ 10 ] : نظرية 5.30}

إن تقييد خطة النقل المثلى يظل مثالياً. أي، لنفترض${\displaystyle \gamma \in \Gamma (\mu ,\nu )}$وهو الأمثل،${\displaystyle 0<\gamma '<\gamma }$وتحديد خطة النقل المعيارية${\displaystyle {\bar {\gamma }}':=\gamma '/\gamma '(X\times Y)}$، ثم${\displaystyle {\bar {\gamma }}'}$هي خطة نقل مثلى بين حدودها الخاصة. ^{[ 10 ] : نظرية 4.6} إذا${\displaystyle {\bar {\gamma }}'}$إذا لم يكن الوضع مثاليًا، فهناك تحسين له، والذي بدوره يُترجم إلى تحسين للوضع الأصلي.${\displaystyle \gamma }$.

تنص ثنائية كانتوروفيتش على ما يلي: ^{[ 10 ] : نظرية 5.10}

لو${\displaystyle (X,\mu _{X}),(Y,\mu _{Y})}$هي فضاءات احتمالية بولندية ،${\displaystyle c:X\times Y\to \mathbb {R} \cup \{\infty \}}$هي شبه متصلة من الأسفل ، وتوجد بعض الدوال شبه المتصلة من الأعلى${\displaystyle a\in L^{1}(\mu _{X}),b\in L^{1}(\mu _{Y})}$من النوع${\displaystyle a:X\to \mathbb {R} ,\;b:Y\to \mathbb {R} }$بحيث${\displaystyle c(x,y)\geq a(x)+b(y)}$، ثم$${\displaystyle \inf _{\gamma \in \Gamma (\mu ,\nu )}\left(\int _{X\times Y}c(x,y)\,\mathrm {d} \gamma (x,y)\right)=\sup _{\varphi {\text{ is }}c{\text{-convex}}}\left(\int _{X}\varphi (x)\,\mathrm {d} \mu (x)+\int _{Y}\varphi ^{c}(y)\,\mathrm {d} \nu (y)\right)}$$وإذا كان الأمر كذلك،${\displaystyle c}$لا تأخذ إلا القيم الحقيقية، وتوجد خطة نقل بتكلفة محدودة، وتوجد بعض الدوال${\displaystyle a'\in L^{1}(\mu _{X}),b'\in L^{1}(\mu _{Y})}$بحيث${\displaystyle c(x,y)\leq a'(x)+b'(y)}$، ثم$${\displaystyle \min _{\gamma \in \Gamma (\mu ,\nu )}\left(\int _{X\times Y}c(x,y)\,\mathrm {d} \gamma (x,y)\right)=\max _{\varphi {\text{ is }}c{\text{-convex}}}\left(\int _{X}\varphi (x)\,\mathrm {d} \mu (x)+\int _{Y}\varphi ^{c}(y)\,\mathrm {d} \nu (y)\right)}$$

لننظر في الحالة الثانية، حيث يمكننا بالفعل الوصول إلى خطة مثالية تمامًا، بدلاً من مجرد الاقتراب منها أكثر فأكثر. في هذه الحالة، خطة النقل المثلى${\displaystyle \gamma \in \Gamma (\mu ,\nu )}$، يقيد شكل زوج التسعير الأمثل${\displaystyle (\varphi ,\psi )}$والعكس صحيح.

بالنظر إلى زوج التسعير الأمثل هذا${\displaystyle (\varphi ,\psi )}$، ^{[ 10 ] : ملاحظة 5.13}

• بافتراض خطة نقل عشوائية${\displaystyle \gamma \in \Gamma (\mu ,\nu )}$، إن كان كل${\displaystyle (x,y)\in \operatorname {supp} (\gamma )}$يحقق المساواة التامة${\displaystyle c(x,y)=\varphi (x)+\psi (y)}$، ثم${\displaystyle \gamma }$هي خطة مثالية؛
• بافتراض وجود خطة نقل مثالية${\displaystyle \gamma \in \Gamma (\mu ,\nu )}$، أي${\displaystyle (x,y)\in \operatorname {supp} (\gamma )}$يجب أن تحقق المساواة التامة${\displaystyle c(x,y)=\varphi (x)+\psi (y)}$.

باختصار، تكون خطة النقل مثالية إذا وفقط إذا كانت مدعومة على مجموعة أزواج التفاضل الجزئي من الرتبة c.${\displaystyle (\varphi ,\psi )}$.

يكون النقل الأمثل مستقرًا بالمعنى التالي: ^{[ 10 ] : نظرية 5.20}

افترض أن${\displaystyle (X,\mu ),(Y,\nu )}$هي فضاءات احتمالية بولندية ،${\displaystyle c:X\times Y\to \mathbb {R} }$متصلة، و${\displaystyle \inf c}$هي محدودة. بالنظر إلى متتالية من الدوال المتصلة${\displaystyle c:X\times Y\to \mathbb {R} }$تتقارب بشكل منتظم إلى${\displaystyle c}$زيادة${\displaystyle X\times Y}$، سلسلة${\displaystyle \mu _{k}\to \mu }$بشكل ضعيف، تسلسل${\displaystyle \nu _{k}\to \nu }$بشكل ضعيف، وسلسلة من خطط النقل المثلى${\displaystyle \gamma _{k}\in \Gamma (\mu _{k},\nu _{k})}$إذا كانت تكاليف النقل${\displaystyle \int c_{k}d\pi _{k}}$مُرضٍ${\displaystyle \int c_{k}d\pi _{k}<+\infty ,\;\forall k}$و${\displaystyle \liminf _{k}\int c_{k}d\pi _{k}<+\infty }$، ثم${\displaystyle \gamma _{k}}$يتقارب بشكل ضعيف إلى شيء ما${\displaystyle \gamma }$، و${\displaystyle \gamma }$خطة نقل مثالية من${\displaystyle \mu }$ل${\displaystyle \nu }$.

وبالمثل، فإن خريطة النقل المثلى مستقرة أيضًا. ^{[ 10 ] : الارتباط 5.23}

افترض أن${\displaystyle (X,\mu ),(Y,\nu )}$هي فضاءات احتمالية بولندية ،${\displaystyle X}$مضغوطة محلياً،${\displaystyle c:X\times Y\to \mathbb {R} }$شبه متصلة من الأسفل، و${\displaystyle \inf c}$هي مجموعة منتهية. بالنظر إلى متتالية من الدوال شبه المتصلة من الأسفل${\displaystyle c:X\times Y\to \mathbb {R} }$تتقارب بشكل منتظم إلى${\displaystyle c}$زيادة${\displaystyle X\times Y}$، سلسلة${\displaystyle \nu _{k}\to \nu }$بشكل ضعيف،

لمسألة النقل الأمثل تفسير اقتصادي. ^{[ 11 ]} ويورد سيدريك فيلاني التفسير التالي من لويس كافاريلي : ^{[ 12 ]}

لنفترض أنك تريد شحن بعض الفحم من المناجم، وتوزيعه على النحو التالي:${\displaystyle \mu }$، إلى المصانع، موزعة على النحو التالي${\displaystyle \nu }$دالة تكلفة النقل هي${\displaystyle c}$ثم يأتي أحد وكلاء الشحن ويعرض عليك القيام بعملية النقل. ستدفع له.${\displaystyle f(x)}$لكل فحم لتحميل الفحم في${\displaystyle x}$وادفع له${\displaystyle g(y)}$لكل فحم لتفريغ الفحم في${\displaystyle y}$لكي تقبل الصفقة، يجب أن يفي جدول الأسعار بمتطلباتك.${\displaystyle f(x)+g(y)\leq c(x,y)}$تنص ثنائية كانتوروفيتش على أن الشاحن يمكنه وضع جدول أسعار يجعلك تدفع تقريبًا نفس المبلغ الذي كنت ستدفعه لو شحنت بنفسك.

في التفسير، يحول تحويل الازدواجية دالة تكلفة التحميل${\displaystyle \varphi (x)}$في دالة تكلفة التفريغ المثلى (بالنسبة للشاحن)${\displaystyle \psi (y)=\varphi ^{c}(y)}$إذا كانت دالة تكلفة التفريغ${\displaystyle \psi (y)}$لو كانت أعلى من ذلك في أي وقت، لكان هناك مسار ما${\displaystyle x\to y}$على أي${\displaystyle c(x,y)<\varphi (x)+\psi (y)}$وهذا يعني أن هناك مسارًا تفضل أن تشحن به بنفسك. ولكن إذا كانت تكلفة التفريغ أقل في أي وقت، لكان بإمكان الشاحن أن يربح المزيد من المال برفع السعر عند تلك النقطة. لذلك، ينبغي على الشاحن دائمًا اختيار${\displaystyle \psi =\varphi ^{c}}$ثم يُعاد تطبيق الحجة نفسها لتنص على أنه ينبغي على الشاحن دائمًا اختيار${\displaystyle \varphi =\psi ^{c}}$وبالتالي نحصل على النصف الأدنى من صيغة الازدواجية:$${\displaystyle \inf _{\gamma \in \Gamma (\mu ,\nu )}\left(\int _{X\times Y}c(x,y)\,\mathrm {d} \gamma (x,y)\right)\geq \sup _{\varphi {\text{ is }}c{\text{-convex}}}\left(\int _{X}\varphi (x)\,\mathrm {d} \mu (x)+\int _{Y}\varphi ^{c}(y)\,\mathrm {d} \nu (y)\right),}$$تنص ثنائية كانتوروفيتش على أنها في الواقع مساواة، أي أن الشاحن يمكنه أن يجعلك تدفع بقدر ما تدفعه لنفسك، على الرغم من أن الشاحن قد لا يصل أبدًا إلى الحد الأدنى (ومن هنا استخدام الحد الأدنى والحد الأقصى، بدلاً من الحد الأدنى والحد الأقصى).

افترض أن الشاحن في الواقع يجب أن يدفع نفس دالة التكلفة ونحن، ويمكنه بالضبط الوصول إلى أقصى إيرادات باستخدام${\displaystyle (\varphi ,\psi )}$وفقًا لجدول أسعارهم. عندها يجب على الشاحن استخدام خطة مثالية، وعندها بالكاد يغطي تكاليفه دون تحقيق أي ربح. في المقابل، أي خطة شحن تسمح للشاحن بتغطية تكاليفه تمامًا تُعتبر مثالية.

مصفوفة النقل الأمثل

النقل الأمثل المستمر

ل${\displaystyle 1\leq p<\infty }$، يترك${\displaystyle {\mathcal {P}}_{p}(\mathbb {R} )}$تشير إلى مجموعة مقاييس الاحتمال على${\displaystyle \mathbb {R} }$التي لها محدودية${\displaystyle p}$اللحظة رقم . ليكن${\displaystyle \mu ,\nu \in {\mathcal {P}}_{p}(\mathbb {R} )}$ودع${\displaystyle c(x,y)=h(x-y)}$، أين${\displaystyle h:\mathbb {R} \to [0,\infty )}$هي دالة محدبة .

1. لو${\displaystyle \mu }$ليس لها ذرة ، أي إذا كانت دالة التوزيع التراكمي${\displaystyle F_{\mu }:\mathbb {R} \to [0,1]}$ل${\displaystyle \mu }$إذا كانت دالة متصلة ، فإن${\displaystyle F_{\nu }^{-1}\circ F_{\mu }:\mathbb {R} \to \mathbb {R} }$هي خريطة نقل مثالية. وهي خريطة النقل المثالية الوحيدة إذا${\displaystyle h}$محدب تمامًا.
2. لدينا

${\displaystyle \min _{\gamma \in \Gamma (\mu ,\nu )}\int _{\mathbb {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). ^{[ 13 ]}

في حالة الهوامش${\displaystyle \mu }$و${\displaystyle \nu }$منفصلة، ​​دع${\displaystyle \mu _{x}}$ و${\displaystyle \nu _{y}}$لتكن كتل الاحتمال المخصصة على التوالي لـ${\displaystyle x\in \mathbf {X} }$و${\displaystyle y\in \mathbf {Y} }$ودع${\displaystyle \gamma _{xy}}$ليكن احتمال حدوث${\displaystyle xy}$التعيين. دالة الهدف في مسألة كانتوروفيتش الأولية هي

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

والقيد${\displaystyle \gamma \in \Gamma (\mu ,\nu )}$يعبر عن نفسه

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

و

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

لإدخال هذا في مسألة برمجة خطية ، نحتاج إلى تحويل المصفوفة إلى متجه.${\displaystyle \gamma _{xy}}$إما عن طريق تكديس أعمدتها أو صفوفها ، نسمي${\displaystyle \operatorname {vec} }$هذه العملية. في ترتيب الأعمدة ، تُعاد كتابة القيود أعلاه على النحو التالي:

${\displaystyle \left(1_{1\times |\mathbf {Y} |}\otimes I_{|\mathbf {X} |}\right)\operatorname {vec} (\gamma )=\mu }$و${\displaystyle \left(I_{|\mathbf {Y} \|}\otimes 1_{1\times |\mathbf {X} |}\right)\operatorname {vec} (\gamma )=\nu }$

أين${\displaystyle \otimes }$هو منتج كرونيكر ،${\displaystyle 1_{n\times m}}$هي مصفوفة بحجم${\displaystyle n\times m}$مع جميع المدخلات التي تساوي واحدًا، و${\displaystyle I_{n}}$هي مصفوفة الوحدة ذات الحجم${\displaystyle n}$ونتيجة لذلك، فإن تحديد${\displaystyle z=\operatorname {vec} (\gamma )}$، الصيغة البرمجية الخطية للمسألة هي

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

والتي يمكن إدخالها بسهولة في برنامج حل البرمجة الخطية واسع النطاق (انظر الفصل 3.4 من Galichon (2016) ^{[ 11 ]} ).

في الحالة شبه المنفصلة،${\displaystyle X=Y=\mathbb {R} ^{d}}$و${\displaystyle \mu }$هو توزيع مستمر على${\displaystyle \mathbb {R} ^{d}}$، بينما${\displaystyle \nu =\sum _{j=1}^{J}\nu _{j}\delta _{y_{i}}}$هو توزيع منفصل يحدد كتلة احتمالية${\displaystyle \nu _{j}}$إلى الموقع${\displaystyle y_{j}\in \mathbb {R} ^{d}}$في هذه الحالة، يمكننا أن نرى ^{[ 14 ]} أن مشكلتي كانتوروفيتش الأولية والثنائية تختزلان على التوالي إلى:

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

بالنسبة للأصلي، حيث${\displaystyle \gamma \in \Gamma (\mu ,\nu )}$هذا يعني أن${\displaystyle \int _{X}d\gamma _{j}(x)=\nu _{j}}$و${\displaystyle \sum _{j}d\gamma _{j}(x)=d\mu (x)}$، و:

${\displaystyle \sup \left\{\int _{X}\varphi (x)d\mu (x)+\sum _{j=1}^{J}\psi _{j}\nu _{j}:\psi _{j}+\varphi (x)\leq c(x,y_{j})\right\}}$

بالنسبة للمزدوج، والذي يمكن إعادة كتابته على النحو التالي:

${\displaystyle \sup _{\psi \in \mathbb {R} ^{J}}\left\{\int _{X}\inf _{j}\left\{c(x,y_{j})-\psi _{j}\right\}d\mu (x)+\sum _{j=1}^{J}\psi _{j}\nu _{j}\right\}}$

وهي مسألة تحسين محدبة ذات أبعاد محدودة يمكن حلها باستخدام تقنيات قياسية، مثل انحدار التدرج .

في حالة عندما${\displaystyle c(x,y)=|x-y|^{2}/2}$يمكن للمرء أن يثبت أن مجموعة${\displaystyle x\in \mathbf {X} }$مخصص لموقع معين${\displaystyle j}$هو متعدد السطوح محدب. ويسمى التكوين الناتج مخطط القوة . ^{[ 15 ]}

لنفترض الحالة الخاصة${\displaystyle \mu ={\mathcal {N}}(0,\Sigma _{X})}$،${\displaystyle \nu ={\mathcal {N}}(0,\Sigma _{Y})}$، و${\displaystyle c(x,y)=|y-Ax|^{2}/2}$أين${\displaystyle A}$قابلة للعكس. عندئذٍ يكون لدينا

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

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

${\displaystyle 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}x}$

يظهر برهان هذا الحل في غاليشون (2016). ^{[ 11 ]}

يترك${\displaystyle X}$ليكن فضاء هيلبرت قابلاً للفصل .${\displaystyle {\mathcal {P}}_{p}(X)}$تشير إلى مجموعة مقاييس الاحتمال على${\displaystyle X}$التي لها محدودية${\displaystyle p}$اللحظة رقم -؛ ليكن${\displaystyle {\mathcal {P}}_{p}^{r}(X)}$تشير إلى تلك العناصر${\displaystyle \mu \in {\mathcal {P}}_{p}(X)}$التي تكون منتظمة غاوسية : إذا${\displaystyle g}$أي مقياس غاوسي موجب تمامًا على${\displaystyle X}$و${\displaystyle g(N)=0}$، ثم${\displaystyle \mu (N)=0}$أيضًا.

يترك${\displaystyle \mu \in {\mathcal {P}}_{p}^{r}(X)}$،${\displaystyle \nu \in {\mathcal {P}}_{p}(X)}$،${\displaystyle c(x,y)=|x-y|^{p}/p}$ل${\displaystyle p\in (1,\infty ),p^{-1}+q^{-1}=1}$إذن، فإن مسألة كانتوروفيتش لها حل وحيد${\displaystyle \kappa }$وهذا الحل ناتج عن خريطة نقل مثالية: أي، توجد خريطة بوريل${\displaystyle r\in L^{p}(X,\mu ;X)}$بحيث

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

علاوة على ذلك، إذا${\displaystyle \nu }$إذا كان له دعم محدود ،

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

ل${\displaystyle \mu }$-جميعهم تقريبًا${\displaystyle x\in X}$بالنسبة لبعض السكان المحليين، ليبشيتز ،${\displaystyle c}$-مقعر وأقصى جهد كانتوروفيتش${\displaystyle \varphi }$. (هنا${\displaystyle \nabla \varphi }$يشير إلى مشتق جاتو من${\displaystyle \varphi }$.)

تم تقديم صيغة انحدار التدرج لحل مشكلة مونج-كانتوروفيتش بواسطة سيجورد أنجينينت وستيفن هاكر وألين تانينباوم . ^{[ 16 ]}