运筹学-5(运输问题)

1、运筹学基础教程运筹学基础教程5 黄桐城黄桐城 主编主编 赵弘志赵弘志 改编改编 主讲主讲 第五章第五章 运输问题运输问题l主要内容主要内容你们手中教材你们手中教材p-091第第4章章 运 输 问 题 及 其 数 学 模 型运 输 问 题 及 其 数 学 模 型 表 上 作 业 法表 上 作 业 法 产 销 不 平 衡 的 运 输 问 题产 销 不 平 衡 的 运 输 问 题4.1 4.1 运运 输输 问问 题及其数学模型题及其数学模型 在物流活动中，经常会有大宗货物的调运问题。在物流活动中，经常会有大宗货物的调运问题。如何编制调运方案，把货物从供应地运到各消费如何编制调运方案，把货物从供应地运

2、到各消费地，而总运费最小，就是我们要解决的问题。一般地，而总运费最小，就是我们要解决的问题。一般说来，这种物流中的运输问题可以用以下数学语言说来，这种物流中的运输问题可以用以下数学语言描述。描述。 已知有已知有 m m 个供应地点个供应地点 A Ai i, , i i=1,2,=1,2,m；可供应；可供应某种物资，其供应量分别为某种物资，其供应量分别为a ai i, , i i=1,2,=1,2,m； 以有以有n n个销地个销地 B Bj j, ,j j=1,2,=1,2,n; 其需要量分别为其需要量分别为 b bj j, , j j=1,2,=1,2,n; 从从A Ai i到到B Bj j运

3、输单位物资的运价运输单位物资的运价( (单价单价) )为为c cijij，这些数据，这些数据可以汇总到产销平衡表和单位运价表中。若用可以汇总到产销平衡表和单位运价表中。若用x xijij 表示从表示从A Ai i到到B Bj j 的运量，那么在供需平衡的条件下，的运量，那么在供需平衡的条件下，要求得总运费最小的调运方案，可求解以下数学模要求得总运费最小的调运方案，可求解以下数学模型：型： 0,2, 1,2, 1,min1111 ijnjiijmijijminiijijxmiaxnjbxStxcz运运 输输 表表运输价格表运输价格表 销地销地产地产地B1B2Bn产量产量 A1C11C12C1n

4、a1 A2C21C22C2n a2 AmCm1Cm2Cmn am 销量销量b1b2bn4.2. 4.2. 表上作业法表上作业法 表上作业法实质上是单纯形法。下面我们结合例表上作业法实质上是单纯形法。下面我们结合例题来解析表上作业法。题来解析表上作业法。 例例4 4 某物流公司有三个仓库，每天向四个超市某物流公司有三个仓库，每天向四个超市供应某种货物。已知三个仓库供应某种货物。已知三个仓库A A1 1，A A2 2和和A A3 3的此货物的此货物储藏量分别为储藏量分别为7 7箱、箱、4 4箱和箱和9 9箱。该物流公司把这些货箱。该物流公司把这些货物分别送往物分别送往B B1 1、B B2 2、B

5、 B3 3和和B B4 4四个超市，各超市每日销四个超市，各超市每日销量分别为量分别为3 3箱、箱、6 6箱、箱、5 5箱和箱和6 6箱。试用表上作业法求箱。试用表上作业法求解满足供需要求的最佳调运方案，使总运费最少。解满足供需要求的最佳调运方案，使总运费最少。解：步骤如下：解：步骤如下： 第一步：做出单位运价表与供销平衡表：第一步：做出单位运价表与供销平衡表： 第二步：第二步：求初始解。初始解一般可通过最小元求初始解。初始解一般可通过最小元素法和伏格尔法两种方法得到。素法和伏格尔法两种方法得到。 超市超市仓库仓库B1B2B3B4储量储量A13113107A219284A3741059销量销量

6、3656 20 204.2.1 确定初始基本可行解确定初始基本可行解 1 1最小元素法最小元素法 p095 最小元素法的基本思想是就近配送，即从单位运价表中最小元素法的基本思想是就近配送，即从单位运价表中最小的运价开始确定供需关系，然后次小，一直到给出初始最小的运价开始确定供需关系，然后次小，一直到给出初始可行解为止。可行解为止。 超市超市仓库仓库B1B2B3B4储量储量A13113107A21（3）9284-3=1A3741059销量销量3-3=0656 20 20继续继续B1B2B3B4储量储量A13113107A21（3）92（1）81-1=0A3741059销量销量065-1=46B1

7、B2B3B4储量储量A13113（4）107-4=3A21（3）92 （1）80A3741059销量销量064-4=06继续继续B1B2B3B4储量储量A13113（4）103A21（3）92 （1）80A374（6）1059-6=3销量销量06-6=006B1B2B3B4储量储量A13113（4）10（3）3A21（3）92 （1）80A374 （6）105（3）3销量销量0006-6=0最后，得到运输分配表。最后，得到运输分配表。（分配结果一定（分配结果一定= n + m - 1 个）个）它的运输总成本：它的运输总成本： 31+ 64 + 43 + 12 + 310 + 35=86元元 超

8、市超市仓库仓库B1B2B3B4储量储量A1437A2314A3639销量销量3656 20 20 2 2伏格尔法伏格尔法 p098 最小元素法的缺点是：为了节省一处的费用最小元素法的缺点是：为了节省一处的费用, , 有有时造成在其他处要花几倍的运费。伏格尔法考虑时造成在其他处要花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费就考虑次小运费j j这就有一个差额，差额越大，说明这就有一个差额，差额越大，说明不能按最小运费调运时，运费增加越多，因而对差不能按最小运费调运时，运费增加越多，因而对差额最大处，就应当采用最小运

9、费调查。基于此，伏额最大处，就应当采用最小运费调查。基于此，伏格尔法的步骤是：格尔法的步骤是： 首先，在表首先，在表4 41 1中分别计算出各行各列的最小运中分别计算出各行各列的最小运费和次小运费的差额，并填入该列表的最右列和最费和次小运费的差额，并填入该列表的最右列和最下行下行, ,见下表：见下表： 然后，从行或列差额中选出最大者，选择它所在行或列然后，从行或列差额中选出最大者，选择它所在行或列的最小元素，在表的最小元素，在表4-84-8中中B2B2列是最大差额所在列。列是最大差额所在列。B2B2列中最列中最小元素为小元素为4 4，可确定，可确定A3A3的产品先供应的产品先供应B2B2的需要

10、，得表的需要，得表4-94-9。同。同时将运价表中的时将运价表中的B2B2列数字划去，如表列数字划去，如表 超市超市仓库仓库B1B2B3B4行差值行差值A13113100（7）A219281（4）A374（6）1051（9-6）列差值列差值 2（3） 5（6-6）1（5） 3（6） 20 20B1B2B3B4行差值行差值A13113100（7）A219281（4）A374 （6）105（3）2（3-3）列差值列差值2（3）（0）1（5）3（6-3）B1B2B3B4行差值行差值A13113100（7）A21 （3）9281（4-3）A374 （6）105 （3）（0）列差值列差值2（3-3）（0

11、）1（5）2（3）继续继续B1B2B3B4行差值行差值A13113 （5）107（7-5）A21 （3）9286（1）A374 （6）105 （3）（0）列差值列差值（0）（0）1（5-5）2（3）B1B2B3B4行差值行差值A13113 （5）10（2）（2）A21 （3）928（1）（1）A374 （6）105 （3）（0）列差值列差值（0）（0）（0）（ 3 -3）最后，得到运输方案：最后，得到运输方案： （分配结果一定（分配结果一定= n + m - 1 个）个）它的运输总成本：它的运输总成本： 31+ 64 + 53 + 210 + 18 + 35=82元元 超市超市仓库仓库B1B2

12、B3B4储量储量A1527A2314A3639销量销量3656 20 20 4.2.24.2.2 最优性检验与方案的调整最优性检验与方案的调整p101 运输问题中的闭合回路是指调运方案中由一个空格和若运输问题中的闭合回路是指调运方案中由一个空格和若干个有数字格的水平和垂直连线包围成的封闭回路。干个有数字格的水平和垂直连线包围成的封闭回路。 目的是要计算解中各非基变量目的是要计算解中各非基变量( (对应空格对应空格) )的的检验数检验数，方法是令某非基变量取值为方法是令某非基变量取值为1 1，通过变化原基变量的值，找，通过变化原基变量的值，找出一个新的可行解，将其同原来的基可行解目标函数值的变出

13、一个新的可行解，将其同原来的基可行解目标函数值的变化比较。化比较。 闭合回路应该这样选取：从某一空格出发，用水平或垂闭合回路应该这样选取：从某一空格出发，用水平或垂直直线向前划，每遇到一数字格，可以但并非一定要转直直线向前划，每遇到一数字格，可以但并非一定要转 90度，直到回到起点空格，一定能够找到唯一的闭合回路。度，直到回到起点空格，一定能够找到唯一的闭合回路。 如果如果检验数检验数 大于等于零，表明对调运方案作出任何改大于等于零，表明对调运方案作出任何改变不会减少运费，现有方案是最优的方案。变不会减少运费，现有方案是最优的方案。 如果如果检验数检验数为负，则方案需要进一步的改进。改进的为负

14、，则方案需要进一步的改进。改进的方法是从为负的格出发（当有两个以上方法是从为负的格出发（当有两个以上检验数检验数负的时，从负的时，从绝对值最大的负绝对值最大的负检验数检验数格出发），在这条闭合回路上，作格出发），在这条闭合回路上，作运量的最大可能调整。刚才使用最小元素法得到下表值：运量的最大可能调整。刚才使用最小元素法得到下表值： a、b、c、d、e、f 就是我们需要求的检验值。就是我们需要求的检验值。B1B2B3B4储储A1a 3b 114 33 107A23 1c 9 1 2d 84A3e 76 4f 103 59销销3656 检验数检验数 a （x11）= 3 3 + 2 1 =1 检验

15、数检验数 b （x12） = 11 10 + 5 4 =2 检验数检验数 c （x22） = 9 2 + 3 10 + 5 4 =1 检验数检验数 d （x24） = 8 10 + 3 2 = -1 检验数检验数 e （x31） = 7 5 + 10 3 + 2 1 =10 检验数检验数 f （x33） = 10 5 + 10 3 =12B1B2B3B4A111-b310A219-c28-dA37-e410-f5 闭回路调整法闭回路调整法 p47 当所有检验数都不小于零时，方案即为最优调运方案。当所有检验数都不小于零时，方案即为最优调运方案。当检验数还存在负值时，说明该方案不是最优，需要调整。

16、当检验数还存在负值时，说明该方案不是最优，需要调整。 4 + 1 = 5，3 1 = 2（因为这里价格（因为这里价格10，比较高），比较高） 0 + 1 = 1, 1 1= 0 。 得到新方案。得到新方案。B1B2B3B4A14 53 2A231 0 1A363 3 3、闭回路法。、闭回路法。（运价）（运价） 在给出调运方案的计算表在给出调运方案的计算表( (最终表最终表) )上，从每一空格出发上，从每一空格出发找一条闭回路。即以某空格为起点，用水平或垂直线向前找一条闭回路。即以某空格为起点，用水平或垂直线向前划，碰到数字格可转划，碰到数字格可转9090度后，继续前进，直到回到起始空度后，继续

17、前进，直到回到起始空格。在表格。在表4-114-11中，空格中，空格(A1(A1，B1)B1)的闭回路之一如表中虚线所的闭回路之一如表中虚线所示，检验数示，检验数=+3 -10 + 8 =+3 -10 + 8 1 = O 1 = O，其中：式中计算所用，其中：式中计算所用值为闭回路顶点所在格的运价，起始空格为奇数位，它的下值为闭回路顶点所在格的运价，起始空格为奇数位，它的下一个顶点为偶数位，下面顶点依次奇偶相间，奇数位取正一个顶点为偶数位，下面顶点依次奇偶相间，奇数位取正值，偶数位取负值，各数累加的和就为检验数。同样，可以值，偶数位取负值，各数累加的和就为检验数。同样，可以计算出其他空格的检验

18、数。计算出其他空格的检验数。 当所有检验数都不小于零时，方案即为最优调运方案。当所有检验数都不小于零时，方案即为最优调运方案。当检验数还存在负值时，说明该方案不是最优，需要调整。当检验数还存在负值时，说明该方案不是最优，需要调整。 本次课后的课外作业本次课后的课外作业习题：请您用习题：请您用最小元素法最小元素法以及以及伏格尔法伏格尔法解下面的习解下面的习题。然后您想想办法，如何来进行调整？题。然后您想想办法，如何来进行调整？ 5161224014367491011126704212315111010104.3 4.3 供需不平衡的运输问题供需不平衡的运输问题 前面的问题是供需平衡问题，即前面的

19、问题是供需平衡问题，即但实际问题往往不平衡，或供大于需，或需大于但实际问题往往不平衡，或供大于需，或需大于供。只要把供需不平衡问题转化成供需平衡问题，供。只要把供需不平衡问题转化成供需平衡问题，就可以用上述方法解决，具体方法如下。就可以用上述方法解决，具体方法如下。 (1)(1)当仓库供应量大于超市需求量时，只要增加当仓库供应量大于超市需求量时，只要增加一个假想的超市，一个假想的超市，j=n+1(j=n+1(实际上是储存实际上是储存) )，该超市，该超市总总需求量为：需求量为： 单位运价为单位运价为0 0，这样，就转，这样，就转化为平衡化为平衡 的运输问题。的运输问题。 njjmiiba11njjmiiba11 (2) (2)当超市需求量大于仓库供应量时，只要在供当超市需求量大于仓库供应量时，只要在供需平衡表中增加一个假想的仓库需平衡表中增加一个假想的仓库i=m+1i=m+1，该仓库供，该仓库供应应量为：量为： 而在单位运价表上从该假想仓而在单位运价表上从该假想仓库库到各超市的运价为到各超市的运价为0 0，同样可以转化为一个供需平衡，同样可以转化为一个供需平衡的运输问题。的运输问题。 为了让同学们能够自觉理解这个问题，我们在为了让同学们能够自觉理解这个问题，我们在下一页画一个供需不平衡的案例：下一页画一个供需不平衡的案例：m