例1^[41] 某公司经销一种产品，来自于三个产地A₁，A₂，A₃，每日的产量分别为7t、4t、9t。该公司要把这些产品分别运往四个销地B₁，B₂，B₃，B₄，各个销地每日销量分别为3t、6t、5t、6t。已知从各产地到各销地的单位运价如表8-10所示，从各产地到各销地的距离如表8-11所示。假设各个产地的装车速度均为1h/t，各条线路上的空载行驶速度均为100km/h，各条线路上的附加运输时间与运输量之间的关系为：t¹_ij=f（x_ij）=0.5x_ij。问该公司应该如何安排调运，才能在15h之内完成调运任务且使总费用最小？

表8-10 单位运费表 （单位：万元/t）

表8-11 距离表 （单位：100km）

解：首先，根据公式t⁰_ij=a_i/u_i+d_ij/v_ij计算出与运输量无关的运输时间t⁰_ij，结果如表8-12所示。

表8-12 各个产地到销地与运输量无关的运输时间t⁰_ij （单位：h）

然后，令t^s_ij=max{0，15-t⁰_ij}，据公式0.5x_ij≤t^s_ij计算出各条线路上的货物运输量上限d_ij，计算结果如表8-13所示。

表8-13 各条线路上的货物运输量上限d_ij （单位：t）

由于A₃行的货物运输量上限之和小于A₃产地的产量，B₁列的货物运输量上限之和小于B₁销地的销量，因此15h之内无法完成调运任务，即本题无可行解。

例2 如果把例1中的运输时间限制改为17h，其他条件不变，问如何安排调运？

解：首先，计算出与运输量无关的运输时间如表8-12所示。(www.daowen.com)

其次，令t^s_ij=max{0，17-t⁰_ij}，据公式0.5x_ij≤t^s_ij计算出各条线路上的货物运输量上限d_ij，计算结果如表8-14所示。

表8-14 各条线路上的货物运输量上限d_ij （单位：t）

再次，将容量为0的线路对应的单位运费改为M。

然后，去掉容量限制，用表上作业法求解松弛的产销平衡运输问题，得到松弛问题的最优解，如表8-15所示。

表8-15 松弛运输问题的最优解

注：其中每个格子左上角的数字为单位运费，右上角的数字为变量取值上限，左下角的数字为检验数，右下角带圆圈的数字为基变量取值，带方框的数字为第二类非基变量取值；产地和销地旁边的数字为位势值。

由于x₁₃＞d₁₃，所以当前的解不是原问题的最优解。选择x₂₃为进基变量，构成闭回路x₂₃x₁₃x₁₂x₂₂，调整量为Q=x₁₃-d₁₃=1，调整后，x₁₃成为第二类非基变量，新的解如表8-16所示。

表8-16 调整后的解

从表8-16中可以看出，所有变量取值均为非负且不超过上限，第一类非基变量检验数均为非负，第二类非基变量检验数均为非正，因此，表8-16中对应的运输方案即为例2的最优解。完成该调运任务需要的时间为17h（在A₁到B₃的线路上达到），总运费为125万元。