运输问题的数学模型

1．运输问题的数学模型

首先考虑下列问题。

例3.16某种物资在A₁、A₂、A₃三个地方进行生产，生产出来的物资需要运到B₁、B₂、B₃、B₄四个地方去销售，产地的供应量、销售地的需求量，以及从产地运到销售地物资的单位运费见表3.20。

表3.20

这是一个平衡运输问题，因为产地的总供应量恰好与销售地的总需求量相等。现在的任务是，在不超过产地生产能力、保证销售地需要的前提下，如何合理地制定产地到销售地的运送方案，以使总的运输成本最小。根据给定的条件，我们已经知道产地的产量、销售地的需要量，以及物资从产地运到销售地的单位运价，需要求解的是，各个产地应该分别运送多少物资到各个销售地去。为此，我们可以用xij表示由产地i（i= 1，2，3）运到销售地j（j=1，2，3，4）的物资数量，则可以建立如下的线性规划模型。

Minf=20x₁₁+11x₁₂+8x₁₃+6x₁₄+5x₂₁+9x₂₂+10x₂₃+2x₂₄+18x₃₁+7x₃₂+4x₃₃+x₃₄

式中，方程①、②、③分别表示由各个产地运往全部四个销售地的物资数量刚好等于产地的生产量，方程④、⑤、⑥、⑦分别表示由三个产地运到某个销售地的物资数量恰好等于该销售地对物资的需要量。

通过上述例子，我们不难看出，运输问题的数学规划模型，在形式上同一般的线性规划模型几乎没有什么两样，它也是由线性目标函数和线性约束方程所构成的，区别只不过在于，运输问题模型约束系数矩阵中的每一列，除两个元素为1外，其余位置上的元素都是零。就上面的例子来说，其约束系数矩阵为：

对于平衡运输问题，运输数学规划模型另外一个特征是，所有约束方程都取等号。运输问题的一般性提法及数学规划模型：有m个地区生产某种物资，有n个需求地需要这种物资，物资由产地运到销售地的单位运费见表3.21。

表3.21

假设xij表示由产地i（i=1，2，3）运到销售地j（j=1，2，3，4）的物资数量，产地的供应量和销售地的需求量由表3.22给出。

表3.22

在产销平衡的条件下，运输问题的数学模型可以写成：

在产销不平衡（产量大于销量，或产量小于销量）的条件下，这一问题的数学模型变

对于平衡运输问题，下面两个结论是重要的。

①平衡运输问题模型中的约束系数矩阵的秩为m+n－1。②平衡运输问题一定存在最优解。