运输问题 运输问题是一类特殊的线性规划问题，研究如何以最小的成本或最短的时间，将某种货物从多个供应点（产地）调运到多个需求点（销地），并且满足各地的供应量和需求量。 第一步：理解问题的基本要素 我们可以通过一个简单的例子来构建直观认识。假设有两个仓库（供应点）和三个零售商店（需求点）。 供应量： 仓库A有20单位货物，仓库B有30单位货物。 需求量： 商店1需要15单位，商店2需要25单位，商店3需要10单位。 运输成本： 从每个仓库运送到每个商店的单位成本是不同的。我们可以用一个成本表格来表示： | | 商店1 | 商店2 | 商店3 | 供应量 | | :--- | :---: | :---: | :---: | :---: | | 仓库A | 2元 | 3元 | 1元 | 20 | | 仓库B | 5元 | 4元 | 2元 | 30 | | 需求量 | 15 | 25 | 10 | | 我们的目标是找到一个运输方案，即确定从每个仓库到每个商店具体运送多少单位货物，使得总运输成本最低，同时所有仓库的货物被运完，所有商店的需求得到满足。 第二步：建立数学模型 现在我们将这个直观问题转化为严格的数学模型。定义决策变量： \( x_ {ij} \)：从仓库 \( i \) 运送到商店 \( j \) 的货物量（其中 \( i = A, B \)； \( j = 1, 2, 3 \)）。 目标函数是总运输成本最小化： \( \text{Minimize} \quad Z = 2x_ {A1} + 3x_ {A2} + 1x_ {A3} + 5x_ {B1} + 4x_ {B2} + 2x_ {B3} \) 约束条件包括两类： 供应约束（从每个仓库运出的总量等于其供应量）： \( x_ {A1} + x_ {A2} + x_ {A3} = 20 \) （仓库A） \( x_ {B1} + x_ {B2} + x_ {B3} = 30 \) （仓库B） 需求约束（运到每个商店的总量等于其需求量）： \( x_ {A1} + x_ {B1} = 15 \) （商店1） \( x_ {A2} + x_ {B2} = 25 \) （商店2） \( x_ {A3} + x_ {B3} = 10 \) （商店3） 非负约束： \( x_ {ij} \geq 0 \) （对于所有的 \( i, j \)） 这个数学模型就是一个标准的线性规划模型，但它的约束矩阵具有非常特殊的结构（所有系数都是0或1，并且每列恰好有两个1），这使其成为“运输问题”。 第三步：问题的平衡与扩展 在建立模型时，一个关键前提是“供需平衡”，即总供应量等于总需求量。 在上例中，总供应 = 20 + 30 = 50，总需求 = 15 + 25 + 10 = 50。 如果现实问题中供需不平衡，我们需要先将其转化为平衡问题。 当供应 > 需求 ：我们引入一个虚拟的需求点（例如，理解为“库存”或“废弃”），其需求量等于供需差额，并且到该点的运输成本通常设为0。 当需求 > 供应 ：我们引入一个虚拟的供应点，其供应量等于供需差额，从该点到各需求点的运输成本可能设为0（表示缺货不处罚）或一个很大的罚金（表示不允许缺货）。 第四步：求解方法——表上作业法 虽然运输问题可以用通用的单纯形法求解，但利用其模型特性，我们有更高效的专门算法—— 表上作业法 。该方法直接在成本表上进行操作，非常直观。其核心步骤如下： 寻找初始基可行解 ：常用的方法有西北角法、最小元素法和伏格尔（Vogel）法。其中最小元素法（优先安排单位成本最小的路线）和伏格尔法（考虑次小成本与最小成本的差额，能给出更好的初始解）更为常用。 最优性检验 ：判断当前方案是否已是最优。常用方法是位势法。通过计算每个供应点（行位势 \( u_ i \)）和每个需求点（列位势 \( v_ j \)）的位势，使得对于所有有运输量的格子（基变量），满足 \( c_ {ij} = u_ i + v_ j \)。然后，对于所有空格子（非基变量），计算检验数 \( \sigma_ {ij} = c_ {ij} - u_ i - v_ j \)。如果所有检验数都大于等于0，则当前方案就是最优解。否则，存在改进空间。 方案改进（闭回路调整） ：如果存在负检验数，则选择其中一个（通常选最小的）作为调入变量。以该格子为起点，在当前的运输表中寻找一条闭合回路，这条回路由水平或垂直的线段构成，且转角点除了起点外，都必须是当前有运输量的格子。然后，沿着这条回路调整运量：在奇数次转角点减少运量，在偶数次转角点（包括起点）增加运量，调整量是奇数次转角点中的最小运量。这样就能得到一个新的、总成本更低的运输方案。 重复步骤2和3，直到所有检验数非负，即得到最优解。