第3章-运输问题

1、第三章第三章 运输问题运输问题1 运输问题的典例和数学模型运输问题的典例和数学模型2 表上作业法表上作业法3 产销不平衡的运输问题及其应用产销不平衡的运输问题及其应用1 运输问题的典例和数学模型运输问题的典例和数学模型1.1 问题的提出问题的提出例例1：某公司从两个产地：某公司从两个产地A1，A2将物品运往将物品运往三个销地三个销地B1，B2，B3，各产地的产量、各销，各产地的产量、各销地的销量和各产地运往各销地的每件物品的地的销量和各产地运往各销地的每件物品的运费如下表所示。问如何调运，使得总运输运费如下表所示。问如何调运，使得总运输费最小？费最小？产销平衡及单位运价表（运输表）：产销平衡及

2、单位运价表（运输表）： 销地销地产地产地B1B2B3产量产量A1646200A2655300销量销量150150200646655运输问题网络图：运输问题网络图：s3=300s1=200供应量供应量供应地供应地运价运价需求地需求地d1=150d2=150d3=200需求量需求量n设设xij表示从产地表示从产地Ai调运到调运到Bj的运输量。则的运输量。则安排的运量列表如下：安排的运量列表如下： 销地销地产地产地B1B2B3产量产量A1x11x12x13200A2x21x22x23300销量销量150150200建立数学模型如下：建立数学模型如下：) 3 , 2 , 1; 2 , 1(020015

3、0150300200. .556646min231322122111232221131211232221131211jixxxxxxxxxxxxxtsxxxxxxfij符号约定：符号约定：nA1，A2，Am表示某表示某种物资的种物资的m个产地；个产地；nB1，B2，Bn 表示某表示某种物资的种物资的n个销地；个销地；nsi表示产地表示产地Ai的产量；的产量；ndj表示销地表示销地Bj的销量；的销量；ncij表示把物资从产地表示把物资从产地Ai 运到运到Bj的单位运价。的单位运价。),(0, 2 , 1, 2 , 1. .min1111jixnjdxmisxtsxcfijmijijnjiijmi

4、njijij对所有一般运输问题的产销平衡表一般运输问题的产销平衡表销销地地 产产量量 运运量量 1 2 n si 产产地地 1 x11 x12 x1n s1 2 x21 x22 x2n s2 m xm1 xm2 xmn sm 销销量量 dj d1 d2 dn 销销地地 产产量量 运运价价 1 2 n si 产产地地 1 c11 c12 c1n s1 2 c21 c22 c2n s2 m cm1 cm2 cmn sm 销销量量 dj d1 d2 dn 运价表：运价表： 产销平衡表产销平衡表2 表上作业法表上作业法n表上作业法是求解运输问题的特殊方表上作业法是求解运输问题的特殊方法，其实质是单纯形

5、法，所以也称运法，其实质是单纯形法，所以也称运输单纯形法。输单纯形法。表上作业法的步骤：表上作业法的步骤：n找出初始基本可行解。找出初始基本可行解。 n求各非基变量的检验数，判断是否求各非基变量的检验数，判断是否最优。如最优，停止计算，否则转最优。如最优，停止计算，否则转到下一步。到下一步。n确定入基变量与出基变量，找出新确定入基变量与出基变量，找出新的基本可行解。的基本可行解。n重复重复2、3步骤直到得到最优解。步骤直到得到最优解。一、确定初始基本可行解一、确定初始基本可行解n运输问题的基变运输问题的基变量个数为量个数为m+n-1。n在产销平衡表上在产销平衡表上给出给出m+n-1个数个数字格

6、，其相应数字格，其相应数字表示调运量。字表示调运量。有数字格对应基有数字格对应基变量；空格对应变量；空格对应非基变量。非基变量。销地销地产地产地B1B2B3产量产量A1x11x12x13200A2x21x22x23300销量销量150150200销地销地产地产地B1B2B3产量产量A150150200A2100200300销量销量150150200n方法：方法：n最小元素法最小元素法nVogle法（最大差额法（最大差额法）法）1、最小元素法、最小元素法 最小元素法的基本思想是最小元素法的基本思想是就近供应就近供应。即从单位运价最小的变量开始分配运即从单位运价最小的变量开始分配运输量输量, ,依

7、次类推依次类推, ,直到给出初始方案为直到给出初始方案为止。止。 B1B2B3B4产产量量A13113107A219284A3741059销销量量 3 6 5 6 2020314633注意事项：注意事项：n有两个最小运价时任选其一。有两个最小运价时任选其一。n在计算中（最后一步除外），当选出在计算中（最后一步除外），当选出最小元素后，如果所在行未分配产量最小元素后，如果所在行未分配产量刚好等于所在列尚未满足的需求量，刚好等于所在列尚未满足的需求量，则在产销平衡表上填上一个数后，需则在产销平衡表上填上一个数后，需要划去一行和一列，为使有数字格仍要划去一行和一列，为使有数字格仍为为m+n-1，需要

8、在同时划去的该行或，需要在同时划去的该行或列的任一空格位置补填一个列的任一空格位置补填一个“0”。补补“0”的原则：的原则：n尽量先选运费小的实变量；尽量先选运费小的实变量；n补充后不能有某个基变量独占一行补充后不能有某个基变量独占一行一列一列B1B2B3B4产产量量A1311457A277384A3121069销销量量 3 6 5 6 202036例：例：0416判断是否为基本可行解：判断是否为基本可行解：n表中填数字的格有表中填数字的格有m+n-1个。个。n不存在有数字的格为顶点组成的闭回路。不存在有数字的格为顶点组成的闭回路。-存在有数字的格为顶点组成的闭回路，是存在有数字的格为顶点组成

9、的闭回路，是指从调运方案的任一有数字格出发，沿水指从调运方案的任一有数字格出发，沿水平或垂直方向前进，只有并且也只有碰到平或垂直方向前进，只有并且也只有碰到另一有数字的格才允许前进方向转另一有数字的格才允许前进方向转 90，依次进行下去，最后总能找到一条回到原依次进行下去，最后总能找到一条回到原出发点的数字格的回路。出发点的数字格的回路。第一种闭回路第一种闭回路：顶顶 点点 x12、 x13、 x23、 x22 构成了闭回路。构成了闭回路。 销地产地B1B2B3B4A1x12x13A2x22x23A3 销地产地B1B2B3B4A1x11x12A2x22x24A3x31x34第二种闭回路第二种闭

10、回路：顶顶 点点 x11、 x12、 x22、 x24、 x34 、x31、 x11 构成闭回路。构成闭回路。 第三种闭回路第三种闭回路： 销地产地B1B2B3B4A1x11x12A2x21x24A3x32x34 x11、 x12、 x32、 x34、 x24、 x21 构成一个闭回路构成一个闭回路2、Vogle法（最大差额法）法（最大差额法） 基本思想：基本思想：考虑到一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。 2、Vogle法（最大差额法）法（最大差额法） 基本步骤：（

11、结合例题讲）基本步骤：（结合例题讲）1、画出作业表2、在运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行3、从行或列差额中选出最大者，选择它所在行或列中的最小元素，确定该行的产量首先要保证最小元素的需求量，同时将运价表中的列数字划去。4、对运价表中未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。重复1、2步。直到给出初始解为止。2、Vogle法（最大差额法）法（最大差额法）对对VogelVogel法的几点说明：法的几点说明：nA、最大差额法得到的表中数字格也为m+n-1个；且满足所有约束方程；且满足无闭回路的条件；

12、nB、一般来说最大差额法给出的方案要比最小元素法要好。当产销地的数量不多时，Vogel法给出的初始方案有时就是最优方案，所以，Vogel法有时就用作求运输问题最优方案的近似解，但不一定对所有平衡问题都能给出最优方案。 二、最优解的判别二、最优解的判别 检验数检验数 的含义：假设在非基变量的含义：假设在非基变量 处增加一个运量，形成的新运输方案与处增加一个运量，形成的新运输方案与被检验的运输方案的总运费之差。被检验的运输方案的总运费之差。 如果所有空格（非基变量）的检验数均如果所有空格（非基变量）的检验数均大于等于零，即大于等于零，即 ，则达到最优解。，则达到最优解。求检验数的方法有两种：求检验

13、数的方法有两种：n闭回路法闭回路法n位势法位势法ijijx0ij1、闭回路法、闭回路法n从代表非基变量的空格出发，寻找一从代表非基变量的空格出发，寻找一条除这个空格外，其余均由有数字格条除这个空格外，其余均由有数字格为顶点组成的为顶点组成的闭回路。闭回路。按按“加奇减偶加奇减偶”方法计算运费的增加值，作为检验数方法计算运费的增加值，作为检验数填入空格中。填入空格中。n一个空格存在一个空格存在唯一闭回路唯一闭回路。3146331非基变量非基变量x11检验数的计算：检验数的计算：B1B2B3B4产产量量A13113107（+1）（-1）A219284（-1）（+1）A3741059销销量量 3 6

14、 5 6 2020314633121-11012非基变量的检验数表：非基变量的检验数表：B1B2B3B4产产量量A13113107A219284A3741059销销量量 3 6 5 6 2020空空 格格闭闭 回回 路路检验数检验数(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,

15、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、位势法、位势法0, 2 , 1 , 2 , 1 )(min1111ijjmiijnjiijminjijijxnjdxmisxxcxfnjmivucvuvdusvugjiijjinjjjmiii, 2, 1 , 2 , 1,),(max11不限运输问题的对偶问题：运输问题的对偶问题：3323132222121121112223222111131211232322222121131312121111minvdx xvd xxvdxxusxxxusx

16、xxxcxcxcxcxcx cf不限,v,v,v,uucv ucv ucv ucv ucvucvuvdvdvdusu s321212332222221121331122111113322112211max如：如：2个产地，个产地，3个销地的运个销地的运输问题的对偶输问题的对偶问题问题位势法的基本原理：位势法的基本原理：由线性规划公式：由线性规划公式：ij=cij-CBB-1Pij= cij- (ui+vj)对于基变量，对于基变量， cij=ui+vj 。由。由m+n-1个基变量，个基变量，可以列出可以列出m+n-1个等式。而共有个等式。而共有m个个ui 和和n 个个vj ，所以可，所以可令任一

17、个令任一个ui 或或 vj =0，从而解出其它，从而解出其它 m+n 1个的值。（所以个的值。（所以m个个ui 和和n 个个vj 的值不唯的值不唯一。）一。）对于非基变量，由对于非基变量，由ij=cij-（ui+vj）求得其检验求得其检验数。数。位势法的操作：位势法的操作：对运输表上每一行赋予一个数值对运输表上每一行赋予一个数值ui，对每一，对每一列赋予一个数值列赋予一个数值vj，它们的数值由基变量（，它们的数值由基变量（有数字格）有数字格）xij的检验数的检验数ij=cij-（ui+vj）=0 即即 cij=ui+vj求得。求得。在位势法中只能令一个在位势法中只能令一个 ui 或或 vj 为

18、为 0；若不；若不能求出全部能求出全部 ui和和 vj ，说明基变量未选够或，说明基变量未选够或未选对。未选对。非基变量（空格）的检验数由公式：非基变量（空格）的检验数由公式： ij=cij-（ui+vj）求得。求得。 B1B2B3B4A1310A212A345 销地产地B1B2B3B4行位势 uiA1310A212A345列位势 vj 0310-12-59运价 B1B2B3B4A1310A212A345 销地产地B1B2B3B4行位势 uiA1310A212A345列位势 vj 10219-48B1B2B3B4uiA1311310A21928A374105vj 2020314633121-1

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

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

21、整量调整量 ，也是入，也是入基变量基变量 xij 的值。的值。n标有标有“ ”的变量减去调整量的变量减去调整量，标有标有“+”的变量的变量加上调整量。加上调整量。 （加奇减偶加奇减偶） 4、用闭回路法或位势法求新基变量的检、用闭回路法或位势法求新基变量的检验数。验数。n若所有若所有 检验数检验数 0，则达到最优，算法停止；否，则达到最优，算法停止；否则返回则返回 第第1步。步。迭代：迭代： （注意用（注意用“调运量调运量”算）算）B1B2B3B4产产量量A13113107A219284A3741059销销量量 3 6 5 6 2020314633121-11012+-1250调整并求非基变量的

22、检验数：调整并求非基变量的检验数：B1B2B3B4产产量量A13113107A219284A3741059销销量量 3 6 5 6 20203563210221912如何找多个最优方案：如何找多个最优方案：n如果某个非基变量（空格）的检验数如果某个非基变量（空格）的检验数为为0，说明有多个最优解。，说明有多个最优解。n把检验数为把检验数为0的变量作为入基变量，的变量作为入基变量，调整运输方案，即得到另一个最优解。调整运输方案，即得到另一个最优解。X11的检验数为零，作为入基变量的检验数为零，作为入基变量B1B2B3B4产产量量A13113107A219284A3741059销销量量 3 6 5 6 20203563210221912+-调整及用闭回路法求检验数：调整及用闭回路法求检验数： ：B1B2B3B4产产量量A13113107A219284A