表上作业法.doc

第三章 运输问题主要内容运输问题的模型、算法讲授重点运输问题的模型、算法讲授方式讲授式、启发式第一节 运输问题及其数学模型一、运输问题的数学模型设某种物品有m个产地A1,A2,Am，各产地的产量分别是a1,a2,am；有n个销地Bl,B2,Bn,各销地的销量分别为bl,b2,bn。假定从产地Ai(i1,2,m)向销地Bj(j1,2,n)运输单位物品的运价是cij，问怎样调运这些物品才能使总运费最小?这是由多个产地供应多个销地的单品种物品运输问题。为直观清楚起见，可列出该出该问题的运输表，如表3-1所示。 表3-1BlB2Bn产量A1c11c12c1na1A2c21c22c2na2Amcm1cm2cmnam销量blblbn设表示从Ai运往Bj的物品数量，表示从Ai运往Bj的单位物品的运价。则对于平衡运输问题（），其数学模型的一般形式可表示为： (3.1)二、运输问题数学模型的特点对于平衡运输问题()，可以证明其有如下两个特点：(1)矩阵A的秩R(A)m+n-1。(2)问题必有最优解，而且当皆为整数时，其最优解必为整数最优解。第二节 表上作业法求解运输问题一、给出运输问题的初始可行解（初始调运方案）1、最小元素法解题步骤：在运价表中找到最小运价c1k；将的AL产品给B k；若aLb k，则将aL改写为aL-bk，划掉bk，同时将运价表中K列的运价划掉；若aLb k，则将aL改写为bk-aL，划掉aL，同时将运价表中L列的运价划掉。如此重复(1)、(2)，直到分配完毕。例：某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点出售，各工厂的有关资料如下表，问应怎样调运才使总运费最少? 收点发点B1B2B3B4产量B1B2B3B4A116412411A21021039A32285116销量814121448解 表上作业法的步骤如下： 1用最小元素法编制初始调运方案这一步的实质是求第一个基础可行解。也就是按照所谓的“最小元素法”在平衡表的mn个空格中，选取m+n-1空格，填上适当的运量，以形成初始方案第一个基础可行解。其中填有运量的格子对应着基变量，没填运量的空格对应着非基变量。 所谓最小元素法，就是按通常习惯，优先安排运价最小的收发点之间的物资调运量。具体作法如下所述。平衡表上反映的是一个初始调运方案(即第一个基础可行解)，如表3-2所示。表3-2 收点发点B1B2B3B4发 量(吨)B1B2B3B4A110616412411A2821021039A31482285116收量(吨)814121448 对应的目标函数值为：z104611十82十23145十86246(元)2、西北角法该法优先满足运输表中西北角上空格的供销需求。 收点发点B1B2B3B4发 量(吨)B1B2B3B42641021039A38142285116收量(吨)814121448 对应的目标函数值为(最总运费)z84812十610十43811十146372(元)3、沃格尔法（1）计算运输表中每一行和每一列的次最小单位运价和最小运价之间的差值该法优先满足运输表中西北角上空格的供销需求。（2）从行或列差中选择最大者，选择它所在行或列中的最小元素cLk，将AL的产品优先供应Bk，同时将运价表中已满足的行或列划掉。（3）在运价表中选择剩下的运价再重复（1）、（2）。 收点发点B1B2B3B4发 量(吨)B1B2B3B4A1124164124110A28210210391A314822851161收量(吨)8141214482513对应的目标函数值为(最总运费)z124411十82十29145十86244(元) 二、解的最优性检验1、闭回路法闭回路法：它是以某一空格为起点，用水平线或垂直线向前画，每碰到一个数字格转90度后，继续前进，直到回到起始空格为止。判别即考察初始方案对应的基础可行解是否是基础最优解，也就是判别非基变量xij对应的检验数ij是否全部非负。若是，则初始方案就是最优方案；若否，则初始方案尚需改进调整。那么，这里如何计算ij呢?这个方法就是所谓的“闭回路法”。下面以11的计算为例加以说明。为了计算11，我们暂时对初始方案作如下的局部调整：在11对应的空格中填入运量1，即非基变量xll的取值由0增大1，但为了保持收发平衡，从表3-2可以看出：xll增加1，xl3必需减去1，x23必需增加1，x21必需减去1这样调整运量以后，依据运价表计算，总运费将要增加的数值为： c11-c13+c23-c21，而依据典式目标函数(3.3)计算应为11由此可知 11=c11-c13+c23-c21或 11=（c11+c23）-（c13+c21） (3.4)如果我们把上述调整过运量的格子xll、xl3、x23、x21(为了叙述方便，我们不妨把每个格子以其对应的变量来表记)连接起来恰巧形成一个封闭的回路。 过每一个空格能且只能做唯一的一条闭回路。例如在表3-2中： 空格xll对应的闭回路是xllxl3x23一x21一xll； 空格xl2对应的闭回路是xl2x14x34一x32一x12 以上两条闭回路画于表3-2中。 有了闭回路概念，就可以分析检验数与闭回路的关系： (1)因为每一个空格xij都唯一对应一条闭回路，而每一空格又都对应非基变量的检验数ij，因此每一个非基变量的检验数ij也唯一对应一条闭回路（以起始空格为奇数次拐角点）。 (2)由(3.4)知， 11=（c11+c23）-（c13+c21）其中（c13+c21）正是11对应的闭回路第偶数次拐角点对应的运价之和，（c11+c23）正是第奇数次拐角点对应的运价之和。一般地，可以证明：空格xij对应的检验数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)若全部检验数ij0，则已有方案便是最优方案。 (3)若计算中遇到某检验数小于0，则停止计算其余的检验数，表明方案需要调整，转入下一步方案的调整。2、对偶变量法（位势法）（1）编制位势表：在运价表中，凡是对应于平衡表中有运量的运价都划上圈，同时在右侧和下边分别增加一行和一列；（2）填写位势数：最后一列为列位势数有m个，最后一行为行位势数有n个。 这m+n个位势数必须满足要求：UK+VL+=VKL (3)计算检验数：ij=Cij-(Ui+Vj)三、解的改进 调整的步骤如下： (1)作第一个出现的负检验数kj对应的闭回路； (2)求调整量：闭回路偶拐角点中的最小运量； (3)调整：闭回路中，奇拐角点处运量加上；偶拐角点处运量减去(其中出基变量对应的格子变成空格)；不在闭回路上的格子，运量不变；最后写出新的调运方案。四、几点说明 P94第三节 运输问题的进一步讨论 一、产销不平衡的运输问题 我们结合下面的例题作以说明。 例3 水泥调运的产销不平衡情况及运价表，如下表所示，试求最优调运方案。 收点发点B1B2B3B4发量(吨)B1B2B3B4A1721134A2510359A377812收 量(吨)2346 1915 解 在表中，A1、A2、A3的总发量为19吨，而月 B1、B2、B3、B4的总收量为15吨，总发量比总收量多4吨。如果各发点把多余的水泥库存下来的话，那么不论怎样组织运输(满足需求)总的库存数部是4吨。这样，我们就在平衡表中增加库存一列；同时在运价表也相应地增加一列，该列的运价都是零。于是就得到一个新的平衡表和运价表，如下表。 收点发点B1B2B3B4库存发 量(吨)B1B2B3B4库存A17211340A25103590A3778120收 量(吨)2346419 这样就可以按满足产销平衡的条件，用表上作业法求得最优调运方案。 这里要注意，在利用最小元素法编制初始调运方案时，应首先把运价表中库存一列的零运价划去，然后再在其余运价中逐次选取最小运价来编制初始调运方案。最后得到的最优调运方案如下表。 收点发点B1B2B3B4库存发 量(吨)A12327A2325A3437收量(吨)2346419二、作物布局问题的表工作业法 作物布局问题同物资调运问题的线性规划数学模型基本类似，只是作物布局问题是求目标函数(总产量或总产值)最大值，而物资调运问题是求目标函数(总运费)最小值，所以它们的解法也是基本相同的。下面只举一个例子，借以说明作物布局问题的表上作业法。 例4 某农场有土地9公顷。这些土地因土壤的肥沃程度和水源条件不同，可以分成三类。现在农场要在这三类土地上计划种植三种作物。各类土地面积、计划种植面积，以及各种作物在各类土地上的亩产量如下表所示。问应如何因地制宜安排作物布局，才使作物总产量最多? 土地类别作物种类B1B2B3播种面积（公顷）B1B2B3A11700500480A24850700600A34400300500土地面积（公顷）3249解 (1)用最大元素法编制种植计划的初始方案所谓最大元素法，就是按产量高的优先安排种植的原则。比如在表3-19中可以看到在土地B1上种植作物A2产量最高，所以B1的3公顷全部种植A2直至三种作物全部安排到三类土地上时,就得到初始方案如下表。 土地类别作物种类B1B2B3播种面积（公顷）B1B2B3A1101700500480A2314850700600A344400300500土地面积（公顷）3249(2)最优方案的判别用闭回路法计算检验数先求出初始方案中每个空格对应的检验数ij，其中计算公式与物资凋运问题一样，即 如果所有检验数ij0，就可判定这个方案是最优方案。否则，就要对方案进行调整。 对于这个例子的初始方案，因为11=50，所以需要调整。 (3)调整用闭回路法求调整方案 作物布局方案的调整与物资调运方案的调整类似，即:过第一个出现的负检验数对应的空格，作一闭回路；在闭回路奇拐角点的数字中，找一个最小的数，称为调整量；然后，在这条闭回路上，凡奇拐角点的数减去调整数，凡偶拐