สมมติว่าเรามีคอลเลกชันของ${\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}$เพื่อความง่าย เราจะไม่พิจารณาเวลาที่ใช้ในการขนส่ง นอกจากนี้ เรายังสมมติว่าเหมืองแต่ละแห่งสามารถจัดหาวัตถุดิบให้กับโรงงานได้เพียงแห่งเดียว (ไม่มีการแบ่งส่ง) และโรงงานแต่ละแห่งต้องการวัตถุดิบเพียงครั้งเดียวในการดำเนินงาน (โรงงานไม่สามารถทำงานที่กำลังการผลิตครึ่งหนึ่งหรือสองเท่าได้) เมื่อตั้งสมมติฐานข้างต้นแล้วแผนการขนส่งจึงเป็นการจับ คู่แบบหนึ่ง ต่อหนึ่ง (bijection )${\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}$) จากนั้นตัวเลือก "การเคลื่อนไหวเล็กๆ จำนวนมาก" จะกลายเป็นตัวลดค่าต่ำสุดเพียงตัวเดียว

โปรดทราบว่าฟังก์ชันต้นทุนข้างต้นพิจารณาเฉพาะระยะทางแนวนอนที่หนังสือเคลื่อนที่เท่านั้น ไม่ได้พิจารณาระยะทางแนวนอนที่อุปกรณ์ที่ใช้ในการหยิบหนังสือแต่ละเล่มและเคลื่อนย้ายไปยังตำแหน่งที่ต้องการ หากพิจารณาอย่างหลังแทนแล้ว แผนการขนส่งแบบที่สองจะเหมาะสมที่สุดเสมอสำหรับระยะทางแบบยูคลิด ในขณะที่หากมีหนังสืออย่างน้อย 3 เล่ม แผนการขนส่งแบบแรกจะเหมาะสมที่สุดสำหรับระยะทางแบบยูคลิดยกกำลังสอง

การกำหนดปัญหาการขนส่งต่อไปนี้เป็นผลงานของFL Hitchcock : ^{[ 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 ]}และในหนังสือFlows in Networks (1962) ที่เขียนร่วมกับLR Ford Jr. ^{[ 9 ]}

นอกจากนี้ Tjalling Koopmansยังได้รับการยกย่องว่าเป็นผู้ริเริ่มแนวคิดเศรษฐศาสตร์การขนส่งและการจัดสรรทรัพยากร อีกด้วย

ปัญหาการขนส่งตามที่ระบุไว้ในเอกสารสมัยใหม่หรือเอกสารทางเทคนิคที่ซับซ้อนกว่านั้น ดูแตกต่างออกไปบ้างเนื่องจากการพัฒนาของเรขาคณิตแบบรีมันน์และทฤษฎีการวัดตัวอย่างเหมืองแร่และโรงงาน แม้จะเรียบง่าย แต่ก็เป็นจุดอ้างอิงที่มีประโยชน์เมื่อคิดถึงกรณีเชิงนามธรรม ในบริบทนี้ เรายอมรับความเป็นไปได้ว่าเราอาจไม่ต้องการให้เหมืองแร่และโรงงานทั้งหมดเปิดดำเนินการต่อไป และอนุญาตให้เหมืองแร่จัดหาวัตถุดิบให้กับโรงงานมากกว่าหนึ่งแห่ง และโรงงานรับเหล็กจากเหมืองแร่มากกว่าหนึ่งแห่งได้

อนุญาต${\displaystyle X}$และ${\displaystyle Y}$เป็นปริภูมิเมตริกที่แยกออกจากกันได้ สอง ปริภูมิ โดยที่มาตรวัดความน่าจะเป็น ใดๆ บนปริภูมิ ทั้งสองนี้${\displaystyle X}$(หรือ${\displaystyle Y}$) เป็นการวัดแบบเรดอน (กล่าวคือ เป็นปริภูมิเรดอน ) ให้${\displaystyle c:X\times Y\to [0,\infty )}$เป็นฟังก์ชันที่วัดได้ แบบบอเรล โดยกำหนดมาตรวัดความน่าจะเป็น${\displaystyle \mu }$บน${\displaystyle X}$และ${\displaystyle \nu }$บน${\displaystyle Y}$การกำหนดปัญหาการขนส่งที่เหมาะสมที่สุดของ Monge คือการค้นหาแผนที่การขนส่ง${\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}$แผนที่การขนส่ง ที่ทำให้ค่านี้เป็นค่าต่ำสุด ( กล่าวคือทำให้เป็นค่าต่ำสุดแทนที่จะเป็นค่าต่ำสุด) เรียกว่า "แผนที่การขนส่งที่เหมาะสมที่สุด"

การกำหนดปัญหาการขนส่งที่เหมาะสมที่สุดของ Monge อาจเป็นปัญหาที่ไม่สมบูรณ์ เนื่องจากบางครั้งไม่มี${\displaystyle T}$น่าพอใจ${\displaystyle T_{*}(\mu )=\nu }$เหตุการณ์นี้เกิดขึ้นเมื่อ (ตัวอย่างเช่น)${\displaystyle \mu }$เป็นการวัดแบบ Diracแต่${\displaystyle \nu }$ไม่ใช่

เราสามารถปรับปรุงสิ่งนี้ได้โดยการนำสูตรของ Kantorovich มาใช้ในการแก้ปัญหาการขนส่งที่เหมาะสมที่สุด ซึ่งก็คือการหามาตรวัดความน่าจะเป็น${\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 ก็ ต่อเมื่อกราฟทั้งหมดของมันสามารถ "สัมผัส" ได้ด้วย " เครื่องมือปลายแหลม " ที่เคลื่อนที่และเปลี่ยนรูปร่างได้ เมื่อเครื่องมือปลายแหลมอยู่ที่${\displaystyle x}$มันมีรูปร่างเป็น${\displaystyle y\mapsto c(x,y)}$และถูกยกขึ้นให้สูงถึง${\displaystyle -\psi (x)}$กราฟของc-นูน${\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 -subdifferential ที่เป็นเอกลักษณ์ที่${\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 }$.

ทฤษฎีบทคู่ของ Kantorovichระบุว่า: ^{[ 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 -subdifferential${\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 ] : Cor. 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 ]} Cédric Villaniเล่าถึงการตีความต่อไปนี้จากLuis Caffarelli : ^{[ 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)}$ทฤษฎีทวิภาวะของ Kantorovich กล่าวว่า ผู้ขนส่งสามารถกำหนดตารางราคาที่ทำให้คุณต้องจ่ายเกือบเท่ากับที่คุณจะขนส่งเอง

ในการตีความ การแปลงแบบทวิภาวะจะแปลงฟังก์ชันต้นทุนการโหลด${\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),}$$ทฤษฎีทวิภาวะของ Kantorovich กล่าวว่า แท้จริงแล้วมันคือความเท่าเทียมกัน กล่าวคือ ผู้ขนส่งสามารถทำให้คุณจ่ายได้มากเท่ากับที่คุณอยากจ่ายเอง แม้ว่าผู้ขนส่งอาจจะไม่เคยไปถึงขอบเขตนั้นอย่างแม่นยำ (ดังนั้นจึงใช้ค่าต่ำสุดและค่าสูงสุดแทนค่าต่ำสุดและค่าสูงสุด)

สมมติว่าผู้ส่งสินค้าต้องจ่ายค่าใช้จ่ายตามฟังก์ชันต้นทุนเดียวกันกับเรา และสามารถบรรลุรายได้สูงสุดได้โดยใช้ฟังก์ชันต้นทุนเดียวกัน${\displaystyle (\varphi ,\psi )}$ตามแผนภูมิราคาของพวกเขา จากนั้นผู้ขนส่งจะต้องใช้แผนที่เหมาะสมที่สุด ซึ่งในจุดนั้นผู้ขนส่งจะคุ้มทุนโดยไม่มีกำไร ในทางกลับกัน แผนการขนส่งใดๆ ที่ทำให้ผู้ขนส่งคุ้มทุนได้พอดีจะต้องเป็นแผนที่เหมาะสมที่สุด

เมทริกซ์การขนส่งที่เหมาะสมที่สุด

การขนส่งที่เหมาะสมอย่างต่อเนื่อง

สำหรับ${\displaystyle 1\leq p<\infty }$, อนุญาต${\displaystyle {\mathcal {P}}_{p}(\mathbb {R} )}$แสดงถึงชุดของการวัดความน่าจะเป็นบน${\displaystyle \mathbb {R} }$ที่มีขีดจำกัด${\displaystyle p}$ช่วงเวลาที่ -th . ให้${\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.}$

หลักฐานของวิธีแก้ปัญหานี้ปรากฏใน Rachev & Rüschendorf (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}$การมอบหมาย ฟังก์ชันวัตถุประสงค์ในปัญหา Kantorovich ดั้งเดิมคือ

${\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 ]}ว่าปัญหา Kantorovich แบบดั้งเดิมและแบบคู่ ตามลำดับ ลดลงเหลือ:

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

ซึ่งเป็นปัญหา การหาค่าเหมาะสมที่สุดแบบนูนในมิติจำกัดที่สามารถแก้ไขได้ด้วยเทคนิคมาตรฐาน เช่นการไล่ระดับความชัน (gradient descent )

ในกรณีที่${\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}$

หลักฐานของวิธีแก้ปัญหานี้ปรากฏใน Galichon (2016) ^{[ 11 ]}

อนุญาต${\displaystyle X}$เป็นปริภูมิฮิลเบิร์ตที่แยกส่วนได้ ให้${\displaystyle {\mathcal {P}}_{p}(X)}$แสดงถึงชุดของการวัดความน่าจะเป็นบน${\displaystyle X}$ที่มีขีดจำกัด${\displaystyle p}$ช่วงเวลาที่ -th; ให้${\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}$ดังนั้น ปัญหาของ Kantorovich จึงมีคำตอบเพียงหนึ่งเดียว${\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}$-เว้าและศักยภาพ Kantorovich สูงสุด${\displaystyle \varphi }$. (ที่นี่${\displaystyle \nabla \varphi }$แสดงถึงอนุพันธ์ Gateauxของ${\displaystyle \varphi }$.)

Sigurd Angenent , Steven Haker และAllen Tannenbaumได้เสนอสูตรการลดระดับความชันสำหรับการแก้ปัญหา Monge–Kantorovich ^{[ 16 ]}