第3章-运输问题

第三章运输问题§1运输问题的典例和数学模型§2表上作业法§3产销不平衡的运输问题及其应用§1运输问题的典例和数学模型1.1问题的提出例1：某公司从两个产地A1，A2将物品运往三个销地B1，B2，B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示。问如何调运，使得总运输费最小？产销平衡及单位运价表（运输表）：销地产地B1B2B3产量A1646200A2655300销量150150200··646655运输问题网络图：s3=300s1=200供应量供应地运价需求地d1=150d2=150d3=200需求量设xij表示从产地Ai调运到Bj的运输量。则安排的运量列表如下：销地产地B1B2B3产量A1x11x12x13200A2x21x22x23300销量150150200建立数学模型如下：1.2产销平衡运输问题的一般数学模型：符号约定：A1，A2，…Am表示某种物资的m个产地；B1，B2，…Bn表示某种物资的n个销地；si表示产地Ai的产量；dj表示销地Bj的销量；cij表示把物资从产地Ai运到Bj的单位运价。一般运输问题的产销平衡表运价表：产销平衡表§2表上作业法表上作业法是求解运输问题的特殊方法，其实质是单纯形法，所以也称运输单纯形法。表上作业法的步骤：找出初始基本可行解。求各非基变量的检验数，判断是否最优。如最优，停止计算，否则转到下一步。确定入基变量与出基变量，找出新的基本可行解。重复2、3步骤直到得到最优解。一、确定初始基本可行解运输问题的基变量个数为m+n-1。在产销平衡表上给出m+n-1个数字格，其相应数字表示调运量。有数字格对应基变量；空格对应非基变量。销地产地B1B2B3产量A1x11x12x13200A2x21x22x23300销量150150200销地产地B1B2B3产量A150150200A2100200300销量150150200方法：最小元素法Vogle法（最大差额法）1、最小元素法最小元素法的基本思想是就近供应。即从单位运价最小的变量开始分配运输量,依次类推,直到给出初始方案为止。

B1B2B3B4产量A13113107A219284A3741059销量36562020314633注意事项：有两个最小运价时任选其一。在计算中（最后一步除外），当选出最小元素后，如果所在行未分配产量刚好等于所在列尚未满足的需求量，则在产销平衡表上填上一个数后，需要划去一行和一列，为使有数字格仍为m+n-1，需要在同时划去的该行或列的任一空格位置补填一个“0”。补“0”的原则：尽量先选运费小的实变量；补充后不能有某个基变量独占一行一列B1B2B3B4产量A1311457A277384A3121069销量3656202036例：0416判断是否为基本可行解：表中填数字的格有m+n-1个。不存在有数字的格为顶点组成的闭回路。--存在有数字的格为顶点组成的闭回路，是指从调运方案的任一有数字格出发，沿水平或垂直方向前进，只有并且也只有碰到另一有数字的格才允许前进方向转90°，依次进行下去，最后总能找到一条回到原出发点的数字格的回路。第一种闭回路：顶点{x12、x13、x23、x22}构成了闭回路。

销地产地B1B2B3B4A1x12x13A2x22x23A3销地产地B1B2B3B4A1x11x12A2x22x24A3x31x34第二种闭回路：顶点{x11、x12、x22、x24、x34、x31、x11}构成闭回路。

第三种闭回路：销地产地B1B2B3B4A1x11x12A2x21x24A3x32x34x11、x12、x32、x34、x24、x21构成一个闭回路2、Vogle法（最大差额法）

基本思想：考虑到一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。

2、Vogle法（最大差额法）基本步骤：（结合例题讲）1、画出作业表2、在运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行3、从行或列差额中选出最大者，选择它所在行或列中的最小元素，确定该行的产量首先要保证最小元素的需求量，同时将运价表中的列数字划去。4、对运价表中未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。重复1、2步。直到给出初始解为止。2、Vogle法（最大差额法）对Vogel法的几点说明：A、最大差额法得到的表中数字格也为m+n-1个；且满足所有约束方程；且满足无闭回路的条件；B、一般来说最大差额法给出的方案要比最小元素法要好。当产销地的数量不多时，Vogel法给出的初始方案有时就是最优方案，所以，Vogel法有时就用作求运输问题最优方案的近似解，但不一定对所有平衡问题都能给出最优方案。

二、最优解的判别检验数的含义：假设在非基变量处增加一个运量，形成的新运输方案与被检验的运输方案的总运费之差。如果所有空格（非基变量）的检验数均大于等于零，即，则达到最优解。求检验数的方法有两种：闭回路法位势法1、闭回路法从代表非基变量的空格出发，寻找一条除这个空格外，其余均由有数字格为顶点组成的闭回路。按“加奇减偶”方法计算运费的增加值，作为检验数填入空格中。一个空格存在唯一闭回路。3146331非基变量x11检验数的计算：B1B2B3B4产量A13113107（+1）（-1）A219284（-1）（+1）A3741059销量36562020314633121-11012非基变量的检验数表：B1B2B3B4产量A13113107A219284A3741059销量36562020空格闭回路检验数(A1,B1)(1,1)(1,3)(2,3)(2,1)(1,1)1(A1,B2)(1,2)(1,4)(3,4)(3,2)(1,2)2(A2,B2)(2,2)(2,3)(1,3)(1,4)(3,4)(3,2)(2,2)1(A2,B4)(2,4)(2,3)(3,3)(1,4)(2,4)-1(A3,B1)(3,1)(3,4)(1,4)(1,3)(2,3)(2,1)(3,1)10(A3,B3)(3,3)(3,4)(1,4)(1,3)(3,3)122、位势法运输问题的对偶问题：如：2个产地，3个销地的运输问题的对偶问题位势法的基本原理：由线性规划公式：σij=cij-CBB-1Pij=cij-(ui+vj)对于基变量，cij=ui+vj

。由m+n-1个基变量，可以列出m+n-1个等式。而共有m个ui

和n个vj

，所以可令任一个ui

或vj=0，从而解出其它m+n1个的值。（所以m个ui

和n个vj

的值不唯一。）对于非基变量，由σij=cij-（ui+vj）求得其检验数。位势法的操作：对运输表上每一行赋予一个数值ui，对每一列赋予一个数值vj，它们的数值由基变量（有数字格）xij的检验数σij=cij-（ui+vj）=0即cij=ui+vj求得。在位势法中只能令一个ui

或vj

为0；若不能求出全部ui和vj

，说明基变量未选够或未选对。非基变量（空格）的检验数由公式：

σij=cij-（ui+vj）求得。

B1B2B3B4A1310A212A345销地产地B1B2B3B4行位势uiA1310A212A345列位势vj

0310-12-59运价

B1B2B3B4A1310A212A345销地产地B1B2B3B4行位势uiA1310A212A345列位势vj

10219-48B1B2B3B4uiA1311310A21928A374105vj2020314633121-11012前例的检验数：（注意用“运价”算）0310-12-59B1B2B3B4uiA1311310A21928A374105vj2020314633前例的检验数：（注意用“运价”算）01128-37121-11012求解过程中常出现的错误：错误地将运输表中基变量的解（即运输量）当作运价参与计算；不能正确画闭合回路；初始解退化，未能补足基变量的个数。因此在位势法中多次令某个ui

或vj

为0。三、改进运输方案的办法—闭回路调整法1、找入基变量（检验数最小的空格对应的变量）2、以xij为起点，寻找由原基变量构成的闭合回路3、迭代计算。从xij出发，标“+”，然后沿任一个方向对回路顶点处的基变量依次标“”和“+”，表示“”和“+”xij，从而使迭代后仍满足分配的平衡。标有“”的变量中最小值就是调整量，也是入基变量xij的值。标有“”的变量减去调整量，标有“+”的变量加上调整量。（加奇减偶）

4、用闭回路法或位势法求新基变量的检验数。若所有检验数

≥0，则达到最优，算法停止；否则返回第1步。迭代：（注意用“调运量”算）B1B2B3B4产量A13113107A219284A3741059销量36562020314633121-11012++--1250调整并求非基变量的检验数：B1B2B3B4产量A13113107A219284A3741059销量365620203563210221912如何找多个最优方案：如果某个非基变量（空格）的检验数为0，说明有多个最优解。把检验数为0的变量作为入基变量，调整运输方案，即得到另一个最优解。X11的检验数为零，作为入基变量B1B2B3B4产量A13113107A219284A3741059销量365620203563210221912++--调整及用闭回路法求检验数：：B1B2B3B4产量A13113107A219284A3741059销量365620205632312021912B1B2B3B4uiA13113100A21928-2A374105-5vj39310202013563用位势法求检验数：22021912

思路：产销不平衡问题化为产销平衡问题，再用表上作业法求解。产>销时，假想一个销地（实为库存），该销地需要量为总产量与总销量之差，并在单位运价表中将从各产地到假想销地的单位运价设为0。产<销时，假想一个产地，该产地产量为总销量与总产量之差，并在单位运价表中将该假想产地到各销地的单位运价设为M。§3产销不平衡的运输问题及其应用例1：设有A1、A2、A3三个产地生产某种物资，其产量分别为7、5、7t，B1、B2、B3、B4