运筹学-5(运输问题)

运筹学基础教程5黄桐城主编赵弘志改编主讲第五章运输问题主要内容—你们手中教材p-091第4章★运输问题及其数学模型★表上作业法★产销不平衡的运输问题4.1运输问题及其数学模型在物流活动中，经常会有大宗货物的调运问题。如何编制调运方案，把货物从供应地运到各消费地，而总运费最小，就是我们要解决的问题。一般说来，这种物流中的运输问题可以用以下数学语言描述。已知有m个供应地点Ai,i=1,2,…m；可供应某种物资，其供应量分别为ai,i=1,2,…m；以有n个销地Bj,j=1,2,…n;其需要量分别为bj,j=1,2,…n;从Ai到Bj运输单位物资的运价(单价)为cij，这些数据可以汇总到产销平衡表和单位运价表中。若用xij表示从Ai到Bj的运量，那么在供需平衡的条件下，要求得总运费最小的调运方案，可求解以下数学模型：0,,2,1,,,2,1,min1111ijnjiijmijijminiijijxmiaxnjbxStxcz运输表——运输价格表销地产地B1B2…Bn产量A1C11C12…C1na1A2C21C22…C2na2………………AmCm1Cm2…Cmnam销量b1b2…bn4.2.表上作业法表上作业法实质上是单纯形法。下面我们结合例题来解析表上作业法。例4某物流公司有三个仓库，每天向四个超市供应某种货物。已知三个仓库A1，A2和A3的此货物储藏量分别为7箱、4箱和9箱。该物流公司把这些货物分别送往B1、B2、B3和B4四个超市，各超市每日销量分别为3箱、6箱、5箱和6箱。试用表上作业法求解满足供需要求的最佳调运方案，使总运费最少。解：步骤如下：第一步：做出单位运价表与供销平衡表：第二步：求初始解。初始解一般可通过最小元素法和伏格尔法两种方法得到。超市仓库B1B2B3B4储量A13113107A219284A3741059销量365620204.2.1确定初始基本可行解1．最小元素法——p095最小元素法的基本思想是就近配送，即从单位运价表中最小的运价开始确定供需关系，然后次小，一直到给出初始可行解为止。超市仓库B1B2B3B4储量A13113107A21（3）9284-3=1A3741059销量3-3=06562020继续B1B2B3B4储量A13113107A21（3）92（1）81-1=0A3741059销量065-1=46B1B2B3B4储量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个）它的运输总成本：3×1+6×4+4×3+1×2+3×10+3×5=86元超市仓库B1B2B3B4储量A1437A2314A3639销量365620202．伏格尔法——p098最小元素法的缺点是：为了节省一处的费用,有时造成在其他处要花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费j这就有一个差额，差额越大，说明不能按最小运费调运时，运费增加越多，因而对差额最大处，就应当采用最小运费调查。基于此，伏格尔法的步骤是：首先，在表4．1中分别计算出各行各列的最小运费和次小运费的差额，并填入该列表的最右列和最下行,见下表：然后，从行或列差额中选出最大者，选择它所在行或列的最小元素，在表4-8中B2列是最大差额所在列。B2列中最小元素为4，可确定A3的产品先供应B2的需要，得表4-9。同时将运价表中的B2列数字划去，如表超市仓库B1B2B3B4行差值A13113100（7）A219281（4）A374（6）1051（9-6）列差值2（3）5（6-6）1（5）3（6）2020B1B2B3B4行差值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）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个）它的运输总成本：3×1+6×4+5×3+2×10+1×8+3×5=82元超市仓库B1B2B3B4储量A1527A2314A3639销量365620204.2.2最优性检验与方案的调整——p101运输问题中的闭合回路是指调运方案中由一个空格和若干个有数字格的水平和垂直连线包围成的封闭回路。目的是要计算解中各非基变量(对应空格)的检验数σ，方法是令某非基变量取值为1，通过变化原基变量的值，找出一个新的可行解，将其同原来的基可行解目标函数值的变化比较。闭合回路应该这样选取：从某一空格出发，用水平或垂直直线向前划，每遇到一数字格，可以但并非一定要转90度，直到回到起点空格，一定能够找到唯一的闭合回路。如果检验数σ大于等于零，表明对调运方案作出任何改变不会减少运费，现有方案是最优的方案。如果检验数σ为负，则方案需要进一步的改进。改进的方法是从为负的格出发（当有两个以上检验数σ负的时，从绝对值最大的负检验数σ格出发），在这条闭合回路上，作运量的最大可能调整。刚才使用最小元素法得到下表值：a、b、c、d、e、f就是我们需要求的检验值。B1B2B3B4储A1a3b11433107A231c912d84A3e764f10359销3656检验数a（x11）=3–3+2–1=1检验数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=12B1B2B3B4A13-a11-b310A219-c28-dA37-e410-f5闭回路调整法——p47当所有检验数都不小于零时，方案即为最优调运方案。当检验数还存在负值时，说明该方案不是最优，需要调整。4+1=5，3–1=2（因为这里价格10，比较高）0+1=1,1–1=0。得到新方案。B1B2B3B4A14532A23101A3633、闭回路法。（运价）在给出调运方案的计算表(最终表)上，从每一空格出发找一条闭回路。即以某空格为起点，用水平或垂直线向前划，碰到数字格可转90度后，继续前进，直到回到起始空格。在表4-11中，空格(A1，B1)的闭回路之一如表中虚线所示，检验数δ=+3-10+8–1=O，其中：式中计算所用值为闭回路顶点所在格的运价，起始空格为奇数位，它的下一个顶点为偶数位，下面顶点依次奇偶相间，奇数位取正值，偶数位取负值，各数累加的和就为检验数。同样，可以计算出其他空格的检验数。当所有检验数都不小于零时，方案即为最优调运方案。当检验数还存在负值时，说明该方案不是最优，需要调整。本次课后的课外作业习题：请您用最小元素法以及伏格尔法解下面的习题。然后您想想办法，如何来进行调整？5161224014367491011126704212315111010104.3供需不平衡的运输问题前面的问题是供需平衡问题，即但实际问题往往不平衡，或供大于需，或需大于供。只要把供需不平衡问题转化成供需平衡问题，就可以用上述方法解决，具体方法如下。(1)当仓库供应量大于超市需求量时，只要增加一个假想的超市，j=n+1(实际上是储存)，该超市总需求量为：单位运价为0，这样，就转化为平衡的运输问题。njjmiiba11njjmiiba11(2)当超市需求量大于仓库供应量时，只要在供需平衡表中增加一个假想的仓库i=m+1，该仓库供应量为：而在单位运价表上从该假想仓库到各超市的运价为0，同样可以转化为一个供需平衡的运输问题。为了让同学们能够自觉理解这个问题，我们在下一页画一个供需不平衡的案例：miinjjab11例题供大于求的运输问题运费及产销量表：B1B2B3产量A1A2A3A464583275651270405020销量304030180100引入虚拟销地B4，（或理解为仓库），就地“销售”，运费为零。下面就用平衡问题求解。B1B2B3B4产量A1A2A3A4645083207560512070405020销量30403080180180复习与课外作业复习运输问题及其表上作业法，能够根据题目列出运输价格表，用表上作业法的最小元素法和伏格尔法求出最优解和总成本计算，并进行最优解检验。课外作业除了前面列举的2道题目以外，还有在我们教材p115的习题2，完成计算，所有习题都必须写在作业本上。学习运筹学的人生哲学：再难的坎坷也要过，再难的题也要做。运筹学这门课的课风：严格、认真、一丝不苟！THANKS