产销平衡运输问题模型的特征分析

(1)一般模型。

对于一般的产销平衡运输问题,可以描述为:有m个产地(A1,A2,A3,…,Am),生产或供应某种物资,其产量分别为a1,a2,…,am;有n个销地(B1,B2,…,Bn),其需要量分别为b1,b2,…,bn;总的产量等于总的销量;已知从第i个产地到第j个销地的单位运价为cij,在满足各地需要的前提下,求总运输费用最小的调运方案。

对于产销平衡运输问题,通常设xij(i＝1,2,…,m;j＝1,2,…,n)为第i个产地到第j个销地的运量,则数学模型为:

模型(3－1)可简写为:

对于【例3-2】,该模型的系数矩阵为:

(2)模型特征。

以【例3-2】的系数矩阵(3-3)为例,说明产销平衡运输问题模型的特征。

①决策变量个数m×n(3×3＝9),其中m为产地的数量,n为销地的数量。

②约束条件个数m＋n(3＋3＝6)。

③系数矩阵为6(m＋n)行、9(m×n)列,而且具有特殊的结构:(www.xing528.com)

a.矩阵中所有元素要么为“1”,要么为“0”;

b.矩阵(3-3)中,每一列中都只有两个元素为“1”,分别位于第i行和第m＋j行;例如,在x12(xij)对应的列向量中,元素“1”分别位于第1(i＝1)行和第5(m＝3,j＝2,m＋j＝5)行;对于x21,元素“1”分别位于

基变量m＋n－1

第2(i＝2)行和第4(m＝3,j＝1,m＋j＝4)行。

c.基变量的个数为m＋n－1。

(3)运输问题模型的对偶形式。

对于m个产地、n个销地的运输问题,其对偶模型为:

运输问题模型的对偶形式