运输问题数学模型2

1、 运输问题及其数学模型 表上作业法3 产销不平衡的运输问题本章主要内容: 若用x xijij表示从A Ai i到B Bj j的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案，数学模型为： 0, 2 , 1)13(, 2 , 1.min1111ijnjiijmijijminjijijxmiaxnjbxtsxcz运输问题的数学模型其中，ai和bj满足： 称为产销平衡条件。 njjmiiba11表上作业法是求解运输问题的一种简便而有效的方法，表上作业法是求解运输问题的一种简便而有效的方法，其求解工作在运输表上进行。其求解工作在运输表上进行。它是一它是一种迭代法，种迭代法，迭代步骤为：先按某

2、种规则找出一个迭代步骤为：先按某种规则找出一个初始解初始解(初始调运方案初始调运方案)，再对现行解作最优性判别；若，再对现行解作最优性判别；若这个解不是最忧解，就在运输表上对它进行调整改进，这个解不是最忧解，就在运输表上对它进行调整改进，得出一个新解；再判别，再改进；直至得到运输问题的得出一个新解；再判别，再改进；直至得到运输问题的最优解为止。最优解为止。迭代过程中得出的所有解都要求是运输问题的基可行解。迭代过程中得出的所有解都要求是运输问题的基可行解。下面用例子加以说明。下面用例子加以说明。实质是单纯形法实质是单纯形法. 表上作业法例例1 给定下列运输问题给定下列运输问题.B1B2B3B4产

3、量产量A1291079A213425A384257销量销量3846分析：分析：由于总产量是由于总产量是9+5+7=21，总销量是，总销量是3+8+4+6=21，故产销平衡。故产销平衡。该问题有该问题有3个产地，个产地，4个销地，故基可行解含有个销地，故基可行解含有3+4-1=6个基变量。个基变量。（一）确定初始基可行解（一）确定初始基可行解运输问题的初始方案的确定主要有三种方法：运输问题的初始方案的确定主要有三种方法：|.西北角法西北角法.最小元素法最小元素法.伏格尔法伏格尔法运输问题是一种特殊的线性规划问题（大型稀疏矩运输问题是一种特殊的线性规划问题（大型稀疏矩阵的处理）阵的处理）,它的初始

4、基的确定具有一定的难度它的初始基的确定具有一定的难度.伏格尔法伏格尔法 一产地的产品如若不能按最小运费就近供一产地的产品如若不能按最小运费就近供应，就考虑按次小运费供应，这里存在一应，就考虑按次小运费供应，这里存在一个差额。差额越大，说明不能按最小运费个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大调运时，运费增加越多。因而对差额最大处，应当采用最小运费调运。处，应当采用最小运费调运。伏格尔法的主要思想是：伏格尔法的主要思想是：最小元素法确定的初始方案往往缺乏全局的观点最小元素法确定的初始方案往往缺乏全局的观点,即即为了节省一处的运费为了节省一处的运费,而在其它处要多花

5、更大的运费而在其它处要多花更大的运费.B1B2B3B4ai行差行差A1291079A213425A384257bj3846列差列差伏格尔法计算伏格尔法计算1 1用伏格尔法寻找初始基：用伏格尔法寻找初始基：先算出运价表中各行与各列的最小运费与次小运先算出运价表中各行与各列的最小运费与次小运费的差额，并填入该运价表的最右列和最下行。费的差额，并填入该运价表的最右列和最下行。从行差或列差中选出最大者，并选择其所在行或从行差或列差中选出最大者，并选择其所在行或列的最小元素。列的最小元素。A1的行差最大，而其中运价的行差最大，而其中运价c11最小最小, 令令x11为优先为优先运输路线。运输路线。5121

6、123B1B2B3B4ai行差行差A12910795A2134251A3842572bj3846列差列差1123伏格尔法计算伏格尔法计算1 10303/09/6用伏格尔法寻找初始基：用伏格尔法寻找初始基：令令11min9,3 3x 销地销地B1的销量的销量3全由产地全由产地A1供给，所以供给，所以x21=x31=0。将将x11=3 填到调运方案表中第填到调运方案表中第1行第行第1列上。列上。画去运输数据表第一列，画去运输数据表第一列，A1的产量剩余为的产量剩余为9-3=6.得到新的产销平衡与单位运价表得到新的产销平衡与单位运价表.B1B2B3B4ai行差行差A1291079/65A213425

7、1A3842572bj3/0846列差列差1123伏格尔法计算伏格尔法计算2 20306/15/0用伏格尔法寻找初始基：用伏格尔法寻找初始基：再算出运价表中的行差与列差。再算出运价表中的行差与列差。 B4的列差最大，的列差最大，而其中运价而其中运价c24最小最小, 令令x24为优先运输路线。为优先运输路线。令令56 , 5min24x产地产地A2的产量的产量5全供给销地全供给销地B4，所以，所以x23=x24=0。画去运输数据表中第画去运输数据表中第2行，行，B4的销量还要的销量还要6-5=1。得到新的产销平衡与单位运价表得到新的产销平衡与单位运价表.521122112233050B1B2B3

8、B4ai行差行差A1291079/65A213425/01A3842572bj3/0846/1列差列差1123伏格尔法计算伏格尔法计算3 30304/07/3用伏格尔法寻找初始基：用伏格尔法寻找初始基：再算出运价表中的行差与列差。再算出运价表中的行差与列差。521122112233050 B3的列差最大，的列差最大，而其中运价而其中运价c33最小最小, 令令x33为优先运输路线。为优先运输路线。令令44 , 7min33x销地销地B3的销量的销量4全由产地全由产地A3供给，所以供给，所以x13=0。画去运输数据表中第画去运输数据表中第3列，列，A3的产量剩余为的产量剩余为7-4= 3.得到新的

9、产销平衡与单位运价表得到新的产销平衡与单位运价表.5 2 21 12 2 211522833204B1B2B3B4ai行差行差A1291079/65A213425/01A384257/32bj3/084/06/1列差列差1123伏格尔法计算伏格尔法计算4 40308/57/3/0用伏格尔法寻找初始基：用伏格尔法寻找初始基：再算出运价表中的行差与列差。再算出运价表中的行差与列差。5211221122330505 2 21 12 2 211522833204 B2的列差最大，的列差最大，而其中运价而其中运价c32最小最小, 令令x32为优先运输路线。为优先运输路线。令令38 , 3min32x产地

10、产地A3的产量的产量3全供给销地全供给销地B2，所以，所以x34=0.画去运输数据表中第画去运输数据表中第3行，行，B2的销量剩余为的销量剩余为8-3= 5.得到新的产销平衡与单位运价表得到新的产销平衡与单位运价表.5 2 2 21 12 2 2 11 1 5 5 2 2 83 3 2 203B1B2B3B4ai行差行差A1291079/65A213425/01A384257/32bj3/084/06/1列差列差1123伏格尔法计算伏格尔法计算5 50308/57/3/0用伏格尔法寻找初始基：用伏格尔法寻找初始基：050045 2 2 21 12 2 2 11 1 5 5 2 2 83 3 2

11、 203现在只有一个产地两个销地，故令现在只有一个产地两个销地，故令x12 =5 ,x14 =1为基变量，将其分别填到调运方案表中第为基变量，将其分别填到调运方案表中第1行第行第2列与第列与第1行第行第4列上。列上。51得到产销平衡运输问题的一个初始方案得到产销平衡运输问题的一个初始方案.B1B2B3B4aiA1291079A213425A384257bj3846354351得到产销平衡运输问题的一个初始方案得到产销平衡运输问题的一个初始方案.此方案的运费是此方案的运费是32+59+47+52+34+42=88。伏格尔法给出的初始解往往更接近于最优解。伏格尔法给出的初始解往往更接近于最优解。（

12、二）判断当前方案是否为最优 用单纯形法解线性规划问题时，在迭代过程中每次求得一个基本可行解以后，都要检验它是不是最优解，如果不是最优解，就要继续进行迭代，直到求得最优解或者判定无最优解。 表上作业法是用以下两种方法来处理这个问题的：闭回路法和位势法。（1）闭回路法 在单纯形法中，为了检验一个基本可行解是不是最优解，需要求出所有非基变量的检验数。在运输问题中，每个空格对应一个非基变量。因此，我们需要求出每个空格的检验数。 由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案。 B1B2B3B4A143A231A363 对方案表中每一空格，确定一条由空格出发的闭回路。 闭回

13、路是由水平或垂直线组成的闭合图形。闭回路上的顶点除了这个空格外，其余均为有数格。B1B2B3B4A143A231A363 可以证明，对每一个空格都存在而且惟一存在这样一条封闭回路。B1B2B3B4A143A231A363B1B2B3B4A143A231A363B1B2B3B4A143A231A363B1B2B3B4A143A231A363计算出空格的检验数：等于闭回路上由此空格起奇数顶点运价与偶数顶点运价负值的代数和。B1B2B3B4A143A231A363 11=3 - 3+2 - 1=1 22= 9-2+30+54 =1 31= 7-5+103+21=10 12=11 - 10+5 - 4

14、=2 24= 810 +3 2 =-1 33=10 - 5+10 -3=12 ij 具有确切的经济意义，它表示由Ai往Bj增运1单位时，引起的总运输成本的变化数。当所有空格检验数 ij 0则当前方案是最优的，若尚有空格检验数小于零，表明当前方案尚有待调整。 若所有的空格检验数都大于等于零，表明任何一个空格处调运1单位都会引起总成本的上升，这表明当前方案不能再改进，即定为最优方案。B1B2B3B4A143A231A363 闭回路法的主要缺点是：闭回路法的主要缺点是：当变量个数较多时，当变量个数较多时，寻找闭回路以及计算都会产生困难。寻找闭回路以及计算都会产生困难。（2）位势法（对偶变量法） 对于

15、一个调运方案的每列赋予一个值，称为列位势，记 ，对于每行赋予一个值，称为行位势，记为 nvvv,21muuu,21ijjicvu 则检验数为： ij = cij - ui - vj i = 1, , m ; j = 1, , n它们的值由下列方程组决定：其中， cij 是所有基变量（数字格）xij 的运价系数 。 销销产产A17311310A241928A3974105需需求求3656201321344653103方案表运价表u1 + v3 = c13 = 3 u2 + v1 = c21 = 1u3 + v2 = c32 = 4u1u2u3v1v3v2v4u1 + v4 = c14 = 10u

16、2 + v3 = c23 = 2 u3 + v4 = c34 = 5 令u1 = 5 则有 v4 = 5 v3 = -2u2 = 4 u3=0v2=4v1= -311 = c11 u1 - v1 = 3 5 (-3) = 1 12 = c12 u1 v2 = 11 5 4 = 222 = c22 u2 v2 = 9 4 4 = 1 24 = c24 u2 v4 = 8 4 5 = -1 31 = c31 u3 - v1 = 7 0 (-3) = 10 33 = c33 u3 v3 = 10 0 (-2) = 12 再求非基变量（空格）检验数：再求非基变量（空格）检验数： u1 + v3 = c

17、13 = 3 u2 + v1 = c21 = 1u3 + v2 = c32 = 4u1 + v4 = c14 = 10u2 + v3 = c23 = 2 u3 + v4 = c34 = 5 （1）在有数格上填上相应的运价 销销产产A143A231A363方案表运价表 销销产产A1310A212A345u1u2u3v1v3v2v4位势法在表上进行： (2) 设u1=0，然后根据cij=ui+vj （有数格），依次求得ui和vj的值，并填在相应的位置 销销产产A1310A212A345u1u2u3v1v3v2v4239100-1-5计算(ui+vj )表，把(ui+vj )位势和值填在表中相应位置

18、上，并将有数格位置上的值ui+vj 加上括号以示区别。（ ） （ ）（ ）（ ）（ ）（ ）2989-3-2(ui+vj )表 销销产产A1311310A21928A374105运价表 销销产产A129(3)(10)A2(1)8(2)9A3-3(4)-2(5)u1u2u3v1v3v2v4239100-1-5检验数表 销销产产A1A2A3（3）计算检验数表ij = cij ( ui + vj)(ui+vj )表121-110123、调整方案 若在检验数上有某空格的检验数为负，则可改进方案，降低成本。调整的方法是从具有负检验数的空格出发(有多个负检验数时，选择绝对值大的一个)，沿它的闭回路进行调整

19、，即在保持方案可行的条件下，尽量增加空格上的运量。当检验数确定后，若出现负检验数时，表明当检验数确定后，若出现负检验数时，表明得到的基可行解不是最优解，需要调整。如得到的基可行解不是最优解，需要调整。如果同时有几个负检验数，一般选其中绝对值果同时有几个负检验数，一般选其中绝对值大的一个负检验数，它所对应的非基变量作大的一个负检验数，它所对应的非基变量作为换入变量。用为换入变量。用闭回路法闭回路法进行迭代调整进行迭代调整.为了方便，一般称基变量对应的格为为了方便，一般称基变量对应的格为基格基格，非，非基变量对应的格为基变量对应的格为空格空格。3、调整方案1). 在闭回路中，记选定的空格为第在闭回

20、路中，记选定的空格为第1个顶点，并沿行个顶点，并沿行进方向依次对闭回路的顶点标号为进方向依次对闭回路的顶点标号为2,3,4, 。2).由标号可把闭回路上的顶点分成奇点或偶点。由标号可把闭回路上的顶点分成奇点或偶点。3).取闭回路中取闭回路中偶点偶点运量的最小值为调整量运量的最小值为调整量,相应的变量相应的变量为换出变量为换出变量.记记4). 进行调整：进行调整：迭代过程迭代过程闭回路法闭回路法n 在闭回路外的顶点上的值不变在闭回路外的顶点上的值不变ijijxxn 在闭回路的奇点上的值变为在闭回路的奇点上的值变为ijijxxn 在闭回路的偶点上的值变为在闭回路的偶点上的值变为ijijxxmin是

21、闭回路上的偶点ijijxx上述过程称为上述过程称为闭回路调整法。闭回路调整法。B1B2B3B4A143A231A363B1B2B3B4A152A231A36324= -1，作 x24 的闭回路，调整数=1，调整得检验数表 销销产产A1A2A3121-11012再用闭回路法或位势法求各空格的检验数，再用闭回路法或位势法求各空格的检验数，B1B2B3B4A152A231A363 x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3, 其余的其余的 xij = 0 总运费为总运费为53 + 210 + 31 + 18 + 64 + 35 = 85

22、销销产产A102A221A3912表中的所有检验数表中的所有检验数都非负，故上表中都非负，故上表中的解为最优解。的解为最优解。检验数检验数表表方案表方案表三、 产销不平衡的运输问题 前面我们讨论的运输问题，都是产销平衡的问题，即满足 在实际问题中，产销往往是不平衡的，遇到这种情况，我们可以经过简单的处理，使其转化为产销平衡问题，然后再按前面的方法来求解。 njjmiiba111、产量大于销量 对于产大于销问题 ，可得到下列运输问题的模型： njjmiiba11ijminjijxcz 11minmiaxtsinjij, 2 , 1.1 njbxjmiij, 2 , 11 njmixij, 2 ,

23、 1, 2 , 10 可增加一个假想的销地 ，其销量为： 某个产地Ai运到这个假想销地Bn+1的物资量xi,n+1，实际上就意味着将这些物资在原产地贮存，其相应的运价 ，转化为产销平衡的问题，其数学模型为：1 nB njjmiinbab111), 2 , 1( 01,micni minjijijxcz111min)1, 2 , 1 ;, 2 , 1( 0 )1, 2 , 1( ), 2 , 1( 111 njmixnjbxmiaxijjmiijinjij 例 某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：

24、应如何调运可使总运输费用最小？ 销产A113151278A211292245需求533625 123114单位运价表解： 这里，总产量为 78 + 45 = 123 ；总销量为 53 +36 + 25 = 114 。产销不平衡，增加一个虚设的销地，得到下表 销产A1781315120A2451129220需求5236259123 销产A113151278A211292245需求533625 1231142、产量小于销量 对于产小于销问题 njjmiiba11 可增加一个假想的产地 ，其产量为： 其相应的运费为 上述不平衡问题就转化为平衡的问题， 1mA miinjjmaba111), 2 , 1( 0, 1njcjm 111minminjijijxcz), 2 , 1; 1, 2 , 1( 0 ),