视频字幕
最优运输问题是一个数学问题，旨在找到将一个概率分布或质量分布最优地转换到另一个概率分布所需的最小成本或最小工作量。简单来说，就是如何以最经济的方式将东西从一个地方的分布移动到另一个地方的分布。在这个例子中，蓝色点代表源分布，红色点代表目标分布。我们需要找到一种方式，将源分布中的所有点移动到目标分布中，使得总运输成本最小。
让我们来看看最优运输问题的数学定义。在最优运输问题中，我们有两个关键元素：一个是源分布μ和目标分布ν，另一个是成本函数c(x,y)，它表示将单位质量从位置x移动到位置y所需的成本。我们的目标是找到一个运输计划γ，使得总运输成本最小化。这可以用数学公式表示为：在所有可能的运输计划中，最小化积分c(x,y)dγ(x,y)。在图中，蓝色柱状图表示源分布μ，红色柱状图表示目标分布ν，而黄色曲面表示成本函数c(x,y)。绿色箭头表示可能的运输路径，箭头的透明度反映了运输成本的大小。
让我们来看一个最优运输问题的经典例子：蒙日-坎托洛维奇运输问题。在这个问题中，我们有m个矿山，每个矿山i有产量aᵢ；有n个工厂，每个工厂j有需求bⱼ；从矿山i运输到工厂j的单位成本为cᵢⱼ。我们的目标是找到一个运输方案，使得总运输成本最小化。这可以表示为最小化总成本的数学公式，同时满足一些约束条件：每个矿山的产出必须全部运出，每个工厂的需求必须全部满足，且运输量不能为负。在图中，我们有3个矿山和3个工厂，绿色箭头表示最优的运输方案，数字表示运输的数量。这种类型的问题可以使用线性规划方法求解。
现在让我们来看看最优运输问题的求解方法。求解最优运输问题的方法主要分为三类：首先是线性规划方法，包括单纯形法和内点法；其次是专门为运输问题设计的特殊算法，如西北角法和最小成本法用于构造初始解，跳跃法用于求最优解；最后是一些现代方法，如Sinkhorn算法和熵正则化方法，这些方法在大规模问题上表现更好。在图中，我们可以看到不同算法的收敛速度比较：蓝色曲线代表单纯形法，红色曲线代表内点法，绿色曲线代表Sinkhorn算法。单纯形法的求解步骤包括：构建初始可行解，检查当前解是否最优，如果不是最优则找入基变量和出基变量，更新解并重复这个过程直到找到最优解。
最后，让我们来看看最优运输问题的广泛应用。首先，在物流与供应链管理领域，最优运输问题可以用于优化仓库到零售店的配送路线，以及多工厂的生产计划。其次，在计算机视觉与图像处理领域，它可以用于图像匹配、比较和颜色迁移等任务。第三，在机器学习领域，最优运输被用于领域适应和生成模型评估。最后，在经济学中，它可以应用于资源分配和劳动力市场匹配问题。这些应用都基于最优运输理论中的Wasserstein距离，这是一种衡量两个概率分布之间差异的度量。最优运输问题的理论和算法不断发展，为各个领域提供了强大的数学工具。