运输问题的数学模型

运输问题的数学模型§3.1运输问题及其数学模型§3.2表上作业法§3.3产销不平衡的运输问题§3.4应用举例本章主要内容:1．掌握运输问题的数学模型、系数矩阵特殊形式2．掌握用西北角法、最小元素法求初始基可行解3．掌握回路、位势法求解过程和表上作业法求解运输问题过程教学要求：一、运输问题及其数学模型在经济建设中，经常碰到物资调拨中的运输问题。例如煤、钢材、粮食、木材等物资，在全国都有若干生产基地，分别将这些物资调到各消费基地去，应如何制定调运方案，使总的运输费用最少？问题的提出:运输问题的一般提法是：设某种物资有m个产地和n个销地。产地Ai的产量为；销地Bj的销量。从第i个产地向第j个销地运输每单位物资的运价为Cij。这就是由多个产地供应多个销地的单品种物资运输问题。问如何调运这些物资才能使总运费达到最小。),,2,1(miai),,2,1(njbj1、运输问题的一般提法单位运价表销地产地B1B2…Bn产量A1A2┇Amc11c12…c1nc21c22…c2n┇┇┇┇cm1cm2…cmna1a2┇am销量b1b2…bn（1）。即运输问题的总产量等于其总销量，这样的运输问题称为产销平衡的运输问题。（2）。即运输问题的总产量不等于总销量，这样的运输问题称为产销不平衡的运输问题。njjmiiba11njjmiiba11分两种情况来讨论：若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案，数学模型为：0,,2,1)13(,,2,1..min1111ijnjiijmijijminjijijxmiaxnjbxtsxcz2、运输问题的数学模型其中，ai和bj满足：称为产销平衡条件。njjmiiba11将约束方程式展开可得11112122111211112222nnmmnmmmxxaxxaxxaxxxbxxx212nnmnnbxxxb约束方程式中共mn个变量，m+n个约束。行行nmAxxxxxxxxxmnmmnn111111111111111111212222111211上述模型是一个线性规划问题。但是其结构很特殊，特点如下：1.变量多（mn个），但结构简单。技术系数矩阵该系数矩阵中每列只有两个元素为1，其余的都为零。ijab2.m+n个约束中有一个是多余的（因为其间含有一个平衡关系式）所以R(A)=m+n-1，即解的mn个变量中基变量为m+n-1个。二、表上作业法运输问题仍然是线性规划问题，可以用线性规划法中的单纯形法来解决。但是：1.运输问题所涉及的变量多，造成单纯形表太大；2.若把技术系数矩阵A中的0迭代成非0，会使问题更加复杂。以上两个原因使得我们不得不利用运输问题的特点设计出它的特殊解法——表上作业法。表上作业法，实质上还是单纯形法。其步骤如下：1.确定一个初始可行调运方案。可以通过最小元素法、西北角法、Vogel法来完成；2.检验当前可行方案是否最优，常用的方法有闭回路法和位势法，用这两种方法计算出检验数，从而判别方案是否最优；3.方案调整，从当前方案出发寻找更好方案，常采用闭回路法。二、表上作业法（续）例3.1某公司从三个产地A1、A2、A3将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表3-4所示销地产地B1B2B3B4产量A13113107A219284A3741059销量365620（产销平衡）问应如何调运，可使得总运输费最小?即初始基本可行解的确定，与一般线性规划问题不同，产销平衡运输问题总是存在可行解。1、确定初始方案确定初始基本可行解的方法很多，一般希望方法是既简便，又尽可能接近最优解。下面介绍两种方法：最小元素法，西北角法、Vogel法（1）最小元素法最小元素法的基本思想是优先满足单位运价最小的供销业务。首先找出运价最小的，并以最大限度满足其供销量为原则确定供销业务。同样的方法反复进行直到确定了所有的供销业务，得到一个完整的调运方案即初始基本可行解为止。销产B1B2B3B4产量B1B2B3B4A17311310A241928A3974105需求3656201321344653103方案表运价表以此，得到一初始方案：X13=4,X14=3，X21=3，X23=1，X32=6，X34=3（有数格）X11=X31=X12=X22=X33=X24=0（空格）B1B2B3B4A143A231A363注：（ⅰ）有数格是基变量，共m+n-1=3+4-1=6个。空格是非基变量，共划去m+n=7条线；（ⅱ）如果填上一个变量之后能同时划去两条线（一行与一列），就须在所划去的该行或该列填一个0，此0格当有数格对待。初始方案运费Z0=3×1+6×4+4×3+1×2+3×10+3×5=86(元)（2）西北角法西北角法与最小元素法不同，它不是优先考虑具有最小单位运价的供销业务，而是优先满足运输表中西北角（左上角）上空格的供销需求。销产B1B2B3B4产量B1B2B3B4A17311310A241928A3974105需求365620342236方案表运价表注：应用西北角法和最小元素法，每次填完数，都只划去一行或一列。当填上一个数后行、列同时饱和时，也应任意划去一行(列)。在饱和的列（行）没被划去的格内标一个0,然后划去该列（行）。例3.2某公司下属有生产一种化工产品的三个产地A1、A2、A3，有四个销售点B1、B2、B3、B4销售这种化工产品。各产地的产量、各销地的销量和各产地运往各销地每吨产品的运费（百元）如下表所示。销产B1B2B3B4产量B1B2B3B4A1753859A2402948A3806375需求35405565195问应如何调运，可使得总运输费最小?解：用西北角法求初始基本可行解销产B1B2B3B4产量B1B2B3B4A1753859A2402948A3806375需求35405565195方案表运价表35400401565(3)伏格尔法（次小运价与最小运价之差大者先安排）销产B1B2B3B4产量B1B2B3B4A17311310A241928A3974105需求365620方案表运价表2513011601232123765122、判断当前方案是否为最优用单纯形法解线性规划问题时，在迭代过程中每次求得一个基本可行解以后，都要检验它是不是最优解，如果不是最优解，就要继续进行迭代，直到求得最优解或者判定无最优解。表上作业法是用以下两种方法来处理这个问题的：闭回路法和位势法。（1）闭回路法在单纯形法中，为了检验一个基本可行解是不是最优解，需要求出所有非基变量的检验数。在运输问题中，每个空格对应一个非基变量。因此，我们需要求出每个空格的检验数。由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案。B1B2B3B4A143A231A363①对方案表中每一空格，确定一条由空格出发的闭回路。闭回路是由水平或垂直线组成的闭合图形。闭回路上的顶点除了这个空格外，其余均为有数格。B1B2B3B4A143A231A363可以证明，对每一个空格都存在而且惟一存在这样一条封闭回路。B1B2B3B4A143A231A363B1B2B3B4A143A231A363B1B2B3B4A143A231A363B1B2B3B4A143A231A363②计算出空格的检验数—等于闭回路上由此空格起奇数顶点运价与偶数顶点运价负值的代数和。销地产地B1B2B3B4A1311310A21928A374105B1B2B3B4A143A231A36311=3-3+2-1=122=9-2+3–0+5–4=131=7-5+10–3+2–1=1012=11-10+5-4=224=8–10+3–2=-133=10-5+10-3=12③当所有空格检验数ij0则当前方案是最优的，若尚有空格检验数小于零，表明当前方案尚有待调整。若所有的空格检验数都大于等于零，表明任何一个空格处调运1单位都会引起总成本的上升，这表明当前方案不能再改进，即定为最优方案。σij具有确切的经济意义，它表示由Ai往Bj增运1单位时，引起的总运输成本的变化数。B1B2B3B4A143A231A363闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算都会产生困难。（2）位势法（对偶变量法）对于一个调运方案的每列赋予一个值，称为列位势，记，对于每行赋予一个值，称为行位势，记为nvvv,,,21muuu,,,21ijjicvu则检验数为：ij=cij-ui-vji=1,…,m;j=1,…,n它们的值由下列方程组决定：其中，cij是所有基变量（数字格）xij的运价系数。销产B1B2B3B4产量B1B2B3B4A17311310A241928A3974105需求3656201321344653103方案表运价表u1+v3=c13=3u2+v1=c21=1u3+v2=c32=4u1u2u3v1v3v2v4u1+v4=c14=10u2+v3=c23=2u3+v4=c34=5令u1=5则有v4=5v3=-2u2=4u3=0v2=4v1=-311=c11–u1-v1=3–5–(-3)=112=c12–u1–v2=11–5–4=222=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=c13=3u2+v1=c21=1u3+v2=c32=4u1+v4=c14=10u2+v3=c23=2u3+v4=c34=5（1）在有数格上填上相应的运价销产B1B2B3B4A143A231A363方案表运价表销产B1B2B3B4A1310A212A345u1u2u3v1v3v2v4位势法在表上进行：(2)设u1=0，然后根据cij=ui+vj（有数格），依次求得ui和vj的值，并填在相应的位置销产B1B2B3B4A1310A212A345u1u2u3v1v3v2v4239100-1-5计算(ui+vj)表，把(ui+vj)位势和值填在表中相应位置上，并将有数格位置上的值ui+vj加上括号以示区别。（）（）（）（）（）（）2989-3-2(ui+vj)表销产B1B2B3B4A1311310A21928A374105运价表销产B1B2B3B4A129(3)(10)A2(1)8(2)9A3-3(4)-2(5)u1u2u3v1v3v2v4239100-1-5检验数表销产B1B2B3B4A1A2A3（3）计算检验数表ij=cij–(ui+vj)(ui+vj)表121-110123、调整方案若在检验数上有某空格的检验数为负，则可改进方案，降低成本。调整的方法是从具有负检验数的空格出发(有多个负检验数时，选择绝对值大的一个)，沿它的闭回路进行调整，即在保持方案可行的条件下，尽量增加空格上的运量。从σij为最小负值的空格出发.对其闭回路上的奇数顶点运量增加θ,偶数顶点的运量减少θ(这才能保证新的平衡)，其中调整量θ为该空格闭回路中偶数顶点的最小值。B1B2B3B4A143A231A363注：若闭回路的偶数顶点中同时有两个格以上运量为θ，则调整后其中一个变空格，其余填0。（保证基变量个数不变）（p48）B1B2B3B4A152A231A36324=-1，作x24的闭回路，调整数=1，调整得再用闭回路法或位势法求各空格的检验数，B1B2B3B4A152A231A363x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,其余的xij=0总运费为：f=5×3+2×10+3×1+1×8+6×4+3×5=85。销产B1B2B3B4A102A221