第三章 运输问题主要内容 运输问题的模型、算法 讲授重点 运输问题的模型、算法 讲授方式讲授式、启发式第一节 运输问题及其数学模型一、运输问题的数学模型设某种物品有m 个产地A 1,A 2,…,A m ，各产地的产量分别是a 1,a 2,…,a m ；有n 个销地B l ,B 2,…,B n ,各销地的销量分别为b l ,b 2,…,b n 。

假定从产地A i (i ＝1,2,…,m)向销地B j (j ＝1,2,…,n)运输单位物品的运价是c ij ，问怎样调运这些物品才能使总运费最小?这是由多个产地供应多个销地的单品种物品运输问题。

为直观清楚起见，可列出该出该问题的运输表，如表3-1所示。

设ij表示从A i 运往B j 的物品数量，ij表示从A i 运往B j 的单位物品的运价。

则对于平衡运输问题（∑∑===nj jm i i ba 11），其数学模型的一般形式可表示为：∑∑===n j mi ijij x c s 11min()()()⎪⎪⎪⎩⎪⎪⎪⎨⎧==≥====∑∑==n j m i x n j b x m i a x ij j m i ij inj ij ,2,1;,2,10,,2,1,,2,111 (3.1)二、运输问题数学模型的特点对于平衡运输问题(∑∑===nj jm i iba 11)，可以证明其有如下两个特点： (1)矩阵A 的秩R(A)＝m+n-1。

(2)问题必有最优解，而且当ji b a ,皆为整数时，其最优解必为整数最优解。

第二节 表上作业法求解运输问题一、给出运输问题的初始可行解（初始调运方案） 1、最小元素法 解题步骤：⑴在运价表中找到最小运价c 1k ； ⑵将的A L 产品给B k ；①若a L>b k，则将a L改写为a L-b k，划掉b k，同时将运价表中K列的运价划掉；②若a L<b k，则将a L改写为b k-a L，划掉a L，同时将运价表中L列的运价划掉。

如此重复(1)、(2)，直到分配完毕。

例：某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点出售，各工1．用最小元素法编制初始调运方案这一步的实质是求第一个基础可行解。

也就是按照所谓的“最小元素法”在平衡表的m ×n个空格中，选取m+n-1空格，填上适当的运量，以形成初始方案—第一个基础可行解。

其中填有运量的格子对应着基变量，没填运量的空格对应着非基变量。

所谓最小元素法，就是按通常习惯，优先安排运价最小的收发点之间的物资调运量。

具体作法如下所述。

平衡表上反映的是一个初始调运方案(即第一个基础可行解)，如表3-2所示。

⑥②⑤)2、西北角法⑥②⑤×6＝372(元)3、沃格尔法（1）计算运输表中每一行和每一列的次最小单位运价和最小运价之间的差值该法优先满足运输表中西北角上空格的供销需求。

（2）从行或列差中选择最大者，选择它所在行或列中的最小元素c Lk，将A L的产品优先供应B k，同时将运价表中已满足的行或列划掉。

244(元)二、解的最优性检验1、闭回路法闭回路法：它是以某一空格为起点，用水平线或垂直线向前画，每碰到一个数字格转90度后，继续前进，直到回到起始空格为止。

判别即考察初始方案对应的基础可行解是否是基础最优解，也就是判别非基变量x ij对应的检验数σij是否全部非负。

若是，则初始方案就是最优方案；若否，则初始方案尚需改进调整。

那么，这里如何计算σij呢?这个方法就是所谓的“闭回路法”。

下面以σ11的计算为例加以说明。

为了计算σ11，我们暂时对初始方案作如下的局部调整：在σ11对应的空格中填入运量1，即非基变量x ll的取值由0增大1，但为了保持收发平衡，从表3-2可以看出：x ll增加1，x l3必需减去1，x23必需增加1，x21必需减去1．这样调整运量以后，依据运价表计算，总运费将要增加的数值为：c11-c13+c23-c21，而依据典式目标函数(3.3)计算应为σ11．由此可知σ11=c11-c13+c23-c21或σ11=（c11+c23）-（c13+c21）(3.4)如果我们把上述调整过运量的格子x ll、x l3、x23、x21(为了叙述方便，我们不妨把每个格子以其对应的变量来表记)连接起来恰巧形成一个封闭的回路。

过每一个空格能且只能做唯一的一条闭回路。

例如在表3-2中：空格x ll对应的闭回路是x ll－x l3－x23一x21一x ll；空格x l2对应的闭回路是x l2－x14－x34一x32一x12．以上两条闭回路画于表3-2中。

有了闭回路概念，就可以分析检验数与闭回路的关系：(1)因为每一个空格x ij都唯一对应一条闭回路，而每一空格又都对应非基变量的检验数σij，因此每一个非基变量的检验数σij也唯一对应一条闭回路（以起始空格为奇数次拐角点）。

(2)由(3.4)知，σ11=（c11+c23）-（c13+c21）其中（c13+c21）正是σ11对应的闭回路第偶数次拐角点对应的运价之和，（c11+c23）正是第奇数次拐角点对应的运价之和。

一般地，可以证明：空格x ij对应的检验数σij与其相应的闭回路的关系是：σij=[奇角点对应运价之和]－[偶角点对应运价之和] （3.5）在上例中，利用表3-2可以求出：σ11＝(4+3)-(2+4)＝1σ22＝(10+6+4)-(5+11+3)＝1σ12＝(12+6)-(5+11)＝2……σ24＝(9+4)-(11+3)＝-1经过以上分析，至此我们便可对调运方案的判别准则作以下概述：(1)从调运方案表中的第一行开始，从左到右，按公式(3.5),依次计算每个空格对应的检验数。

(2)若全部检验数σij≥0，则已有方案便是最优方案。

(3)若计算中遇到某检验数小于0，则停止计算其余的检验数，表明方案需要调整，转入下一步—方案的调整。

2、对偶变量法（位势法）（1）编制位势表：在运价表中，凡是对应于平衡表中有运量的运价都划上圈，同时在右侧和下边分别增加一行和一列；（2）填写位势数：最后一列为列位势数有m个，最后一行为行位势数有n个。

这m+n个位势数必须满足要求：U K+V L+=V KL(3)计算检验数：σij=C ij-(U i+V j)三、解的改进调整的步骤如下：(1)作第一个出现的负检验数σkj对应的闭回路；(2)求调整量ε：ε＝闭回路偶拐角点中的最小运量；(3)调整：闭回路中，奇拐角点处运量加上ε；偶拐角点处运量减去ε(其中出基变量对应的格子变成空格)；不在闭回路上的格子，运量不变；最后写出新的调运方案。

四、几点说明P94第三节运输问题的进一步讨论一、产销不平衡的运输问题我们结合下面的例题作以说明。

吨，1231234总发量比总收量多4吨。

如果各发点把多余的水泥库存下来的话，那么不论怎样组织运输(满足需求)总的库存数部是4吨。

这样，我们就在平衡表中增加库存一列；同时在运价表也相这里要注意，在利用最小元素法编制初始调运方案时，应首先把运价表中库存一列的零运价划去，然后再在其余运价中逐次选取最小运价来编制初始调运方案。

最后得到的最优调二、作物布局问题的表工作业法作物布局问题同物资调运问题的线性规划数学模型基本类似，只是作物布局问题是求目标函数(总产量或总产值)最大值，而物资调运问题是求目标函数(总运费)最小值，所以它们的解法也是基本相同的。

下面只举一个例子，借以说明作物布局问题的表上作业法。

例4 某农场有土地9公顷。

这些土地因土壤的肥沃程度和水源条件不同，可以分成三类。

现在农场要在这三类土地上计划种植三种作物。

各类土地面积、计划种植面积，以及各种作物在各类土地上的亩产量如下表所示。

问应如何因地制宜安解 所谓最大元素法，就是按产量高的优先安排种植的原则。

比如在表3-19中可以看到在土地B 1上种植作物A 2产量最高，所以B 1的3公顷全部种植A 2……直至三种作物全部安排⑤ ②④先求出初始方案中每个空格对应的检验数λij ，其中计算公式与物资凋运问题一样，即⎪⎪⎭⎫⎝⎛-⎪⎪⎭⎫ ⎝⎛=亩产总和偶拐角点亩产总和奇拐角点ij λ如果所有检验数λij ≤0，就可判定这个方案是最优方案。

否则，就要对方案进行调整。

对于这个例子的初始方案，因为λ11=50，所以需要调整。

(3)调整——用闭回路法求调整方案作物布局方案的调整与物资调运方案的调整类似，即:过第一个出现的负检验数对应的空格，作一闭回路；在闭回路奇拐角点的数字中，找一个最小的数，称为调整量；然后，在这条闭回路上，凡奇拐角点的数减去调整数，凡偶拐角点的数加上调整数，便得新的种植方案，经过若干次调整，总能得到最优方案。

对表案。

最大总产量为：s=100×700+200×850+200×700+400×500=580 000公斤第四节应用问题举例见例6－例7作业2，3，7，9，10。