运筹学―运输问题(一)

运筹学—运输问题（一）一﹑运输问题的数学模型已知有m个生产地Aii=1,2,…,m。可供应某种物资，其供应量（产量）分别为ai,i=1,2,…,m，有n个销地Bj,j=1,2,…,n,其需要量分别为bj,j=1,2,…,n,从Ai

到Bj运输单位物资的运价（单价）为cij,这些数据汇总于产销平衡表和单位运价表7—1,7—2。销地产地1,2,…,n产量1·ma1·am销量b1,…,bn销地产地1,2,…,n1·mc11,…,c1n…cm1,…,cmn表7-1表7-2若用xij表示从Ai到Bj的运量，那么在产销平衡的条件，要求得总运费最小的调运方案，可求以下数学模型：这就是运输问题的数学模型。它含有m×n个变量，（m+n)个约束方程。其系数矩阵如下：

11

…

1

·········x11

x12…x1n

x21

x22…x2n…

xm1

xm2…xmn

11

…

1

11

…

1

11

1

11

1

·········

11

1m行n行i=1m∑minz＝j=1n∑cijxij＝bj

j=1,2,…,n(7.1)i=1m∑xij＝ai

i=1,2,…,m(7.2)j=1n∑xijxij≥0

11

…

1

·········x11

x12…x1n

x21

x22…x2n…

xm1

xm2…xmn

11

…

1

11

…

1

11

1

11

1

·········

11

1m行n行该系数矩阵中对应变量xij的系数向量pij,其分量除第i个和第m+j个为1，其余为零。即pij=（0,…,1,…,1,…,0

)T

=ei+em+j对产销平衡的运输问题，有以下关系式成立i=1m∑j=1n∑xij＝j=1n∑bji=1m∑ai＝j=1n∑i=1m∑xij＝所以模型最多只有m+n－1个独立约束方程。即系数矩阵的秩≤m+n－1。二﹑表上作业法表上作业法是单纯形法在求解运输问题时的一种简化方法。其实质是单纯形法。其步骤是：⑴找出初始基可行解。即在（m×n)产销平衡表上给出m+n－1个数字格。⑵求各非基变量的检验数，即表上计算空格的检验数。判断是否达到最优解。如已是最优解，则停止计算，否则转下一步。⑶确定换入变量和换出，找出新的基可行解。在表上用闭回路调整法。⑷重复（2）,（3）直到得到最优解。下面详细讨论在表上如何填上m+n－1个数字格？如何计算空格的检验数？如何用闭回路法实现基变换？1﹒确定初始基可行解（填上m+n－1个数字格）介绍两种方法：最小元素法和伏格尔法。下面通过一个例题来说明这两种方法。例1某公司经销甲产品。它下设三个加工厂。每日的产量分别为：A1－7吨，A2－4吨，A3－9吨。该公司把这些产品分别运往四个销售点。各销售点每日的销量为：B1－3吨，B2－6吨，B3－5吨，B4－6吨。已知从各工厂到各销售点的单位产品的运价为下表。问该公司应如何调运产品，在满足各销售点的需要量的前提下，使总费用为最小。

销地产地B1B2B3B4A1A2A3317119432101085运价表（单位：元/吨）销地产地B1B2B3B4产量A1A2A3749销量3656产销平衡表（单位：吨）

销地产地B1B2B3B4A1A2A3317119432101085运价表（单位：元/吨）

销地产地B1B2B3B4产量A1A2A3749销量3656产销平衡表（单位：吨）⑴﹒最小元素法确定初始基可行解这种方法的基本思想是：从单位运价表中最小的运价开始确定供销关系，然后次小。一直到给出初始基可行解为止。3做法：①从运价表中挑选最小元素，并比较所在的行和列的产量和销量的大小，确定供应量。当产大于销，划去该元素所在列；当产小于销，划去该元素所在行。②然后在未划去的元素中再最小元素，再确定供应关系。重复①。14633总费用：86元⑵﹒伏格尔法①计算运价表中各行和各列中最小费用与次小费用的差额，并填入表的最右列和最下行。②从行和列差额中选出最大者，再选择它所在的列或行中的最小元素。若出现两个以上相同的最大值，则从这几个最大值所在的行和列中选出最小元素。依此确定供应关系及供应量。同时根据最小元素法中“划行或划列的规则”，划去该元素所在的行或列。③对表中未划去的元素再分别计算各行和各列的最小费用与次小费用的差额，并填入表的最右列和最下行。重复第②步工作。④重复②，③步。直到给出初始解。

销地产地B1B2B3B4行差额A1A2A3317119432101085列差额运价表（单位：元/吨）

销地产地B1B2B3B4产量A1A2A3749销量3656产销平衡表（单位：吨）2513011621301232120131276512这样我们利用伏格尔法得到一个运输方案（右表）。它的总运费为：83元2﹒最优解的判别利用最小元素法或伏格尔法可以求出一个基可行解。在产销平衡表中填数字的格对应基变量，空格对应非基变量。下面讨论计算空格的检验数cij－CBB-1pij,i,j∈N。由于运输问题的目标函数是要求实现最小化，所以当cij－CBB-1pij≥0时，为最优解。介绍两种求空格检验数的方法：闭回路法，位势法。⑴闭回路法①以一个空格为起点，用水平线或垂直线向前划，每碰到一数字格转90°后继续前进，直到回到起始空格为止。②如果按①的方法无法进行时，则只要保持所找回路上只有起始空格，其余顶点都是数字格。闭回路寻找法：回路有下面几种：例如某运输问题的一个运输方案如下表：126109销量936丁1010丙770乙1129甲产量DCBA销产试找空格x21，x13的闭回路。空格x21的闭回路为：(21)－(11)－(14)－(24)－(21)空格x13的闭回路为：(13)－(43)－(44)－(14)－(13)每一个空格存在唯一回路：因(m+n－1)个数字对应的系数向量组成的矩阵是一基。任一空格对应的向量是这个基的线性组合。设pij

，i，j∈N，则pij=ei+em+j=ei+em+k

-em+k

+el-el+em+s

-em+s+eu

-eu

+em+j=(ei+em+k)-(em+k

+el)

+(el+em+s

)-(em+s+eu)+(eu

+em+j

)=pik

－plk

+pls

－pus+puj

其中pik

,plk,pls,pus,puj∈B而pik

,plk,pls,pus,puj

构成闭回路。空格的检验数：cij－CBB-1pij=cij－CBB-1(pik－

plk

+pls

－pus+puj)puj

pusplkplspijpik空格的检验数：cij－CBB-1pij=cij－CBB-1(pik－

plk

+pls

－pus+puj)又因对于基变量pik有cik－CBB-1pik=0所以有CBB-1pik=cik因此δij=cij－CBB-1pij=cij－cik

+clk

－cls

+cus

－cuj

空格的检验数的经济解释：

如果从Ai调运一吨给Bj，为了产销平衡，则必须从(Ai，Bk)减去一吨，(Al，Bk)加一吨，(Al，Bs)减去一吨，(Au，Bs)加一吨，(Au，Bj)减去一吨。此时，增加的运费：Cij

-cik

+clk-cls

+cus

-cuj

因此，δij等于上述调整方案所增加的费用。pikpijplsplkpuspuj

+1-1+1-1+1-1下面就利用经济解释，求空格的检验数。

销地产地B1B2B3B4产量A1437A2314A3639销量3656产销平衡表（单位：吨）空格闭回路检验数(11)(12)(22)(24)(31)(33)(11)－(1