Kantorovich 输运问题

输运矩阵的每一行是一份源质量的去向清单，每一列是一处目标收到的总量。固定边缘后，能够选择的是依赖结构；独立计划只是众多选择之一，通常并不最省成本。

存在性来自可行计划集合的紧性，而非成本一定严格凸。两组固定边缘在 Polish 空间上都是紧的。给定 $\delta >0$，分别取遗漏质量小于 $\delta /2$ 的紧集 $A,B$，则任意耦合都满足 $\pi ((A\times B{)}^c)\le \mu (A^c)+\nu (B^c)<\delta$。Prokhorov 定理公理库Prokhorov 定理Prokhorov theorem · Prokhorov's theorem · 普罗霍罗夫定理在 Polish 空间上把概率测度族的一致紧性等价为弱拓扑中的相对紧性。因此给成本极小化序列提供弱收敛子列。对任意有界连续 $f$，$f(x)$ 在乘积上仍是有界连续探针，故极限保留第一边缘；第二边缘同理。最后，对平移后的非负下半连续成本使用Portmanteau 的积分下界公理库Portmanteau 定理Portmanteau theorem · Portmanteau lemma · 移植定理把概率测度的弱收敛等价改写为开闭集不等式、半连续函数不等式与连续集上的测度收敛。，得到极限计划的成本不超过下确界。成本线性，最优解可能不唯一。

取源分布 $\mu =\frac{1}{2}{\delta }_0+\frac{1}{2}{\delta }_2$，目标 $\nu =\frac{1}{4}{\delta }_1+\frac{3}{4}{\delta }_3$，成本为平方距离。源按 $0,2$ 排列，目标按 $1,3$ 排列，则

由四个边缘方程，所有可行计划可写成

成本为 $5-8s$，所以取 $s=1/4$ 得

这个计划把位于零点的半单位质量拆成两份，分别送到 $1$ 和 $3$。本例没有可行Monge 映射公理库Monge 输运问题Monge transport problem用确定映射搬运概率质量，先检查推前约束是否可行，再讨论最小成本。，因为两个源原子的质量均为 $1/2$，确定映射无法在目标 $1$ 处恰好产生 $1/4$ 质量。松弛真正扩大了可行集合。

若目标总质量不等于源总质量，以上行列和约束就不相容；非平衡输运需要另外允许创造、销毁或惩罚边缘误差。负成本若无下界，或缺少下半连续性，也可能破坏上述直接法条件。

Kantorovich 对偶公理库Kantorovich 对偶性Kantorovich duality用满足两侧势之和不超过成本的对偶函数，构造可核验的输运最优性证书。用两侧势函数为成本提供下界，能够证实计划最优而不枚举所有方案。若成本取距离的 $p$ 次幂，再开 $p$ 次方，就得到Wasserstein 距离公理库Wasserstein 距离Wasserstein distance用最小平均搬运距离定义概率测度的度量，并用矩条件说明它比弱收敛多控制什么。；不是每个任意成本的最小值都构成度量。