“先取紧度量空间 $X,Y$、连续实成本 $c$ 和 Borel 概率测度 $\mu,\nu$。Kantorovich 问题满足强对偶”
形式陈述
Monge 映射可能因为原子不能拆分而无解。若只规定每个出发地供给多少、每个目的地接收多少,搬运怎样成为一个可行的优化问题?
对Polish 空间
目标采用Lebesgue 积分;成本有下界,所以不存在正负无穷抵消。
有限分布
直觉
输运矩阵的每一行是一份源质量的去向清单,每一列是一处目标收到的总量。固定边缘后,能够选择的是依赖结构;独立计划只是众多选择之一,通常并不最省成本。
存在性来自可行计划集合的紧性,而非成本一定严格凸。两组固定边缘在 Polish 空间上都是紧的。给定
例子与边界
取源分布
由四个边缘方程,所有可行计划可写成
成本为
这个计划把位于零点的半单位质量拆成两份,分别送到
若目标总质量不等于源总质量,以上行列和约束就不相容;非平衡输运需要另外允许创造、销毁或惩罚边缘误差。负成本若无下界,或缺少下半连续性,也可能破坏上述直接法条件。
推论与应用
Kantorovich 对偶用两侧势函数为成本提供下界,能够证实计划最优而不枚举所有方案。若成本取距离的
若还要求
参考资料
- Filippo Santambrogio, 2010,§1.1, transport plans and existence。
- Marco Cuturi, 2013,§2.1–2.2, Transportation tables。