运输问题数学建模(共66张PPT)精选

运输(yùnshū)问题数学建模第一页，共66页。1．掌握运输问题的数学模型、系数矩阵特殊形式2．掌握用西北角法、最小元素法求初始(chūshǐ)基可行解3．掌握回路、位势法求解过程和表上作业法求解运输问题过程教学要求：第二页，共66页。Z0=3×1+6×4+4×3+1×2+3×10+3×5=86(元)u2+v3=c23=2销地Bj的销量。(1)由于问题中所有产地、中间(zhōngjiān)转运站、销地都可以看作产地，又可看作销地。注：应用西北角法和最小元素法，每次填完数，都只划去一行或一列。方案调整，从当前方案出发寻找更好方案，常采用闭回路法。（1）闭回路(huílù)法u1+v4=c14=10总运费(yùnfèi)为：f=5×3+2×10+3×1+1×8+6×4+3×5=85。销量，这样的运输问题称为产销(chǎnxiāo)不平衡的运输问题。单位(dānwèi)运价表解：这里，总产量为78+45=123；二、表上作业(zuòyè)法（续）总运费(yùnfèi)为：f=5×3+2×10+3×1+1×8+6×4+3×5=85。表上作业(zuòyè)法中需要说明的问题一、运输(yùnshū)问题及其数学模型

在经济建设中，经常碰到物资调拨中的运输问题。例如煤、钢材、粮食、木材等物资，在全国都有若干(ruògān)生产基地，分别将这些物资调到各消费基地去，应如何制定调运方案，使总的运输费用最少？问题(wèntí)的提出:第三页，共66页。运输问题的一般提法是：设某种物资(wùzī)有m个产地和n个销地。产地Ai的产量为；销地Bj的销量。从第i个产地向第j个销地运输每单位物资(wùzī)的运价为Cij。这就是由多个产地供应多个销地的单品种物资(wùzī)运输问题。问如何调运这些物资(wùzī)才能使总运费达到最小。1、运输问题的一般(yībān)提法第四页，共66页。单位(dānwèi)运价表第五页，共66页。（1）。即运输问题的总产量等于其总销量，这样的运输问题称为产销(chǎnxiāo)平衡的运输问题。（2）。即运输问题的总产量不等于总销量，这样的运输问题称为产销(chǎnxiāo)不平衡的运输问题。分两种情况(qíngkuàng)来讨论：第六页，共66页。若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，要求(yāoqiú)得总运费最小的调运方案，数学模型为：

2、运输(yùnshū)问题的数学模型其中，ai和bj满足：称为(chēnɡwéi)产销平衡条件。第七页，共66页。将约束(yuēshù)方程式展开可得约束方程式中共(zhōnɡɡònɡ)mn个变量，m+n个约束。第八页，共66页。上述模型是一个线性规划(xiànxìnɡɡuīhuá)问题。但是其结构很特殊，特点如下：1.变量(biànliàng)多（mn个），但结构简单。

技术系数(xìshù)矩阵该系数矩阵中每列只有两个元素为1，其余的都为零。第九页，共66页。2.m+n个约束(yuēshù)中有一个是多余的（因为其间含有一个平衡关系式）所以R(A)=m+n-1，即解的mn个变量中基变量为m+n-1个。第十页，共66页。二、表上作业(zuòyè)法运输(yùnshū)问题仍然是线性规划问题，可以用线性规划法中的单纯形法来解决。但是：1.运输(yùnshū)问题所涉及的变量多，造成单纯形表太大；2.若把技术系数矩阵A中的0迭代成非0，会使问题更加复杂。以上两个原因使得我们不得不利用运输(yùnshū)问题的特点设计出它的特殊解法——表上作业法。第十一页，共66页。表上作业法，实质上还是单纯形法。其步骤(bùzhòu)如下：1.确定一个初始可行调运方案。可以通过最小元素(yuánsù)法、西北角法、Vogel法来完成；2.检验当前可行方案是否最优，常用的方法有闭回路法和位势法，用这两种方法计算出检验数，从而判别方案是否最优；3.方案调整，从当前方案出发寻找更好方案，常采用闭回路法。二、表上作业(zuòyè)法（续）第十二页，共66页。例某公司(ɡōnɡsī)从三个产地A1、A2、A3将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表3-4所示问应如何(rúhé)调运，可使得总运输费最小?第十三页，共66页。即初始基本可行解的确定，与一般(yībān)线性规划问题不同，产销平衡运输问题总是存在可行解。1、确定初始(chūshǐ)方案确定初始基本可行(kěxíng)解的方法很多，一般希望方法是既简便，又尽可能接近最优解。下面介绍两种方法：最小元素法，西北角法、Vogel法第十四页，共66页。（1）最小元素(yuánsù)法最小元素法的基本思想是优先满足单位运价最小的供销业务。首先找出运价最小的，并以最大限度满足其供销量(xiāoliànɡ)为原则确定供销业务。同样的方法反复进行直到确定了所有的供销业务，得到一个完整的调运方案即初始基本可行解为止。第十五页，共66页。销产B1B2B3B4产量B1B2B3B4A17311310A241928A3974105需求3656201321344653103方案(fāngàn)表运价(yùnjià)表第十六页，共66页。以此(yǐcǐ)，得到一初始方案：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条线；（ⅱ）如果填上一个变量之后(zhīhòu)能同时划去两条线（一行与一列），就须在所划去的该行或该列填一个0，此0格当有数格对待。初始(chūshǐ)方案运费Z0=3×1+6×4+4×3+1×2+3×10+3×5=86(元)第十七页，共66页。（2）西北角法西北角法与最小元素法不同，它不是优先考虑具有最小单位运价(yùnjià)的供销业务，而是优先满足运输表中西北角（左上角）上空格的供销需求。第十八页，共66页。销产B1B2B3B4产量B1B2B3B4A17311310A241928A3974105需求365620342236方案(fāngàn)表运价(yùnjià)表第十九页，共66页。注：应用西北角法和最小元素法，每次填完数，都只划去一行或一列。当填上一个数后行、列同时饱和时，也应任意(rènyì)划去一行(列)。在饱和的列（行）没被划去的格内标一个0,然后划去该列（行）。第二十页，共66页。例某公司(ɡōnɡsī)下属有生产一种化工产品的三个产地A1、A2、A3，有四个销售点B1、B2、B3、B4销售这种化工产品。各产地的产量、各销地的销量和各产地运往各销地每吨产品的运费（百元）如下表所示。销产B1B2B3B4产量B1B2B3B4A1753859A2402948A3806375需求35405565195问应如何(rúhé)调运，可使得总运输费最小?第二十一页，共66页。解：用西北角法求初始(chūshǐ)基本可行解销产B1B2B3B4产量B1B2B3B4A1753859A2402948A3806375需求35405565195方案(fāngàn)表运价(yùnjià)表35400401565第二十二页，共66页。(3)伏格尔法（次小运价(yùnjià)与最小运价(yùnjià)之差大者先安排）销产B1B2B3B4产量B1B2B3B4A17311310A241928A3974105需求365620方案(fāngàn)表运价(yùnjià)表

2513

01160123

212

376512第二十三页，共66页。2、判断当前(dāngqián)方案是否为最优用单纯形法解线性规划问题时，在迭代过程中每次求得一个基本可行解以后，都要检验它是不是最优解，如果不是最优解，就要继续进行迭代，直到求得最优解或者判定无最优解。表上作业法是用以下两种方法(fāngfǎ)来处理这个问题的：闭回路法和位势法。第二十四页，共66页。（1）闭回路(huílù)法在单纯形法中，为了检验一个基本(jīběn)可行解是不是最优解，需要求出所有非基变量的检验数。在运输问题中，每个空格对应一个非基变量。因此，我们需要求出每个空格的检验数。由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案。

第二十五页，共66页。B1B2B3B4A143A231A363①对方案表中每一空格，确定一条由空格出发的闭回路。闭回路是由水平或垂直线组成的闭合图形。闭回路上的顶点除了这个空格外(géwài)，其余均为有数格。B1B2B3B4A143A231A363可以证明，对每一个空格都存在而且惟一存在这样(zhèyàng)一条封闭回路。第二十六页，共66页。B1B2B3B4A143A231A363B1B2B3B4A143A231A363B1B2B3B4A143A231A363B1B2B3B4A143A231A363第二十七页，共66页。②计算出空格的检验数—等于闭回路上由此空格起奇数顶点运价与偶数(ǒushù)顶点运价负值的代数和。B1B2B3B4A143A231A36311=3-3+2-1=122=9-2+3–0+5–4=131=7-5+10–3+2–1=1012=11-10+5-4=224=8–10+3–2=-133=10-5+10-3=12第二十八页，共66页。③当所有空格(kōnɡɡé)检验数 σij≥0则当前方案(fāngàn)是最优的，若尚有空格检验数小于零，表明当前方案(fāngàn)尚有待调整。若所有的空格(kōnɡɡé)检验数都大于等于零，表明任何一个空格(kōnɡɡé)处调运1单位都会引起总成本的上升，这表明当前方案不能再改进，即定为最优方案。σij

具有确切的经济意义，它表示由Ai往Bj增运1单位时，引起的总运输成本的变化数。B1B2B3B4A143A231A363

闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算都会产生困难。第二十九页，共66页。（2）位势法（对偶(duìǒu)变量法）对于一个调运方案的每列赋予一个值，称为列位(lièwèi)势，记，对于每行赋予一个值，称为行位势，记为则检验(jiǎnyàn)数为：ij=cij-ui-vji=1,…,m;j=1,…,n它们的值由下列方程组决定：其中，cij

是所有基变量（数字格）xij

的运价系数。第三十页，共66页。销产B1B2B3B4产量B1B2B3B4A17311310A241928A3974105需求3656201321344653103方案(fāngàn)表运价(yùnjià)表u1+v3=c13=3u2+v1=c21=1u3+v2=c32=4u1u2u3v1v3v2v4u1+v4=c14=10u2+v3=c23=2u3+v4=c34=5第三十一页，共66页。令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)=1033=c33–u3–v3=10–0–(-2)=12再求非基变量(biànliàng)（空格）检验数：u1+v3=c13=3u2+v1=c21=1u3+v2=c32=4u1+v4=c14=10u2+v3=c23=2u3+v4=c34=5第三十二页，共66页。（1）在有数格上填上相应(xiāngyīng)的运价销产B1B2B3B4A143A231A363方案(fāngàn)表运价(yùnjià)表销产B1B2B3B4A1310A212A345u1u2u3v1v3v2v4位势法在表上进行：第三十三页，共66页。(2)设u1=0，然后根据cij=ui+vj（有数格），依次(yīcì)求得ui和vj的值，并填在相应的位置销产B1B2B3B4A1310A212A345u1u2u3v1v3v2v4239100-1-5计算(ui+vj)表，把(ui+vj)位势和值填在表中相应位置(wèizhi)上，并将有数格位置(wèizhi)上的值ui+vj加上括号以示区别。（）（）（）（）（）（）2989-3-2(ui+vj)表第三十四页，共66页。销产B1B2B3B4A1311310A21928A374105运价(yùnjià)表销产B1B2B3B4A129(3)(10)A2(1)8(2)9A3-3(4)-2(5)u1u2u3v1v3v2v4239100-1-5检验(jiǎnyàn)数表销产B1B2B3B4A1A2A3（3）计算检验(jiǎnyàn)数表ij=cij–(ui+vj)(ui+vj)表121-11012第三十五页，共66页。3、调整(tiáozhěng)方案若在检验数上有某空格的检验数为负，则可改进(gǎijìn)方案，降低成本。调整的方法是从具有负检验数的空格出发(有多个负检验数时，选择绝对值大的一个)，沿它的闭回路进行调整，即在保持方案可行的条件下，尽量增加空格上的运量。第三十六页，共66页。从σijθ,偶数顶点(dǐngdiǎn)的运量减少θ(这才能保证新的平衡)，其中调整量θ为该空格闭回路中偶数顶点(dǐngdiǎn)的最小值。B1B2B3B4A143A231A363注：若闭回路的偶数顶点中同时有两个格以上运量为θ，则调整后其中一个变空格，其余(qíyú)填0。（保证基变量个数不变）（p48）B1B2B3B4A152A231A36324=-1，作x24的闭回路(huílù)，调整数=1，调整得第三十七页，共66页。再用闭回路(huílù)法或位势法求各空格的检验数，B1B2B3B4A152A231A363x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,其余(qíyú)的xij=0总运费(yùnfèi)为：f=5×3+2×10+3×1+1×8+6×4+3×5=85。销产B1B2B3B4A102A221A3912表中的所有检验数都非负，故上表中的解为最优解。检验数表方案表第三十八页，共66页。表上作业(zuòyè)法中需要说明的问题（1）无穷多最优解当迭代(diédài)到运输问题的最优解时，如果有某非基变量的检验数等于零，则说明该运输问题有多重（无穷多）最优解。上面的例题是多解情况销产B1B2B3B4A102A221A3912B1B2B3B4A152A231A363检验(jiǎnyàn)数表方案表B1B2B3B4A1250A213A363调整方案表第三十九页，共66页。（2）退化当运输问题某部分产地的产量和，与某一部分销地的销量和相等时，在迭代过程中有可能在某个格填入一个运量时需同时划去运输表的一行和一列(yīliè)，这时就出现了退化。在运输问题中，退化解是时常发生的。为了使表上作业法的迭代工作进行下去，退化时应在同时划去的一行或一列(yīliè)中的某个格中填入数字0，表示这个格中的变量是取值为0的基变量，使迭代过程中基可行解的分量恰好为（m+n-1）个。表上作业(zuòyè)法中需要说明的问题第四十页，共66页。三、产销(chǎnxiāo)不平衡的运输问题前面我们讨论的运输问题，都是产销平衡的问题，即满足在实际问题中，产销往往是不平衡的，遇到这种情况，我们可以经过简单的处理(chǔlǐ)，使其转化为产销平衡问题，然后再按前面的方法来求解。第四十一页，共66页。1、产量(chǎnliàng)大于销量对于(duìyú)产大于销问题，可得到下列运输问题的模型：第四十二页，共66页。可增加一个假想的销地，其销量为：某个产地Ai运到这个假想销地Bn+1的物资量xi,n+1，实际上就意味着将这些物资在原产地贮存，其相应的运价，转化为产销平衡(pínghéng)的问题，其数学模型为：第四十三页，共66页。例3-3某公司(ɡōnɡsī)从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？销产B1B2B3产量A113151278A211292245需求533625

123114单位(dānwèi)运价表第四十四页，共66页。解：这里，总产量为78+45=123；总销量为53+36+25=114。产销不平衡，增加一个虚设(xūshè)的销地，得到下表销产B1B2B3B4产量B1B2B3B4A1781315120A2451129220需求5236259123销产B1B2B3产量A113151278A211292245需求533625

123114第四十五页，共66页。2、产量(chǎnliàng)小于销量对于(duìyú)产小于销问题可增加一个假想的产地，其产量为：其相应的运费为上述(shàngshù)不平衡问题就转化为平衡的问题，第四十六页，共66页。例3-4某公司从两个产地(chǎndì)A1、A2将物品运往三个销地B1、B2、B3，各产地(chǎndì)的产量、各销地的销量和各产地(chǎndì)运往各销地每件物品的运费如下表，问：应如何调运可使总运输费用最小？销产B1B2B3产量A113151278A211292245需求533665

123154单位(dānwèi)运价表第四十七页，共66页。解:这里，总产量小于总销量，产销不平衡，增加一个(yīɡè)虚设的产地，得到下表销产B1B2B3产量B1B2B3A178131512A245112922A331000需求533665

154销产B1B2B3产量A113151278A211292245需求533665

123154第四十八页，共66页。四、应用(yìngyòng)举例在变量个数相等的情况下，表上作业法的计算远比单纯形法简单。解决实际问题时，人们常常(chángcháng)尽可能把某些线性规划的问题化为运输问题的数学模型。下面为几个典型的例子。第四十九页，共66页。例3-5有A1、A2、A3三个生产某种物资的产地，五个地区B1、B2、B3、B4、B5对这种物资有需求。现要将这种物资从三个产地运往五个需求地区，各产地的产量、各需求地区的需要量和各产地运往各地区每单位(dānwèi)物资的运费如下表所示，其中B2地区的115个单位(dānwèi)必须满足。问：应如何调运可使总运输费用最小？销地产地B1B2B3B4B5产量A1101520204050A22040153030100A33035405525130需求25115603070280300运输费用(fèiyong)及产量、需求量表第五十页，共66页。解：由于产量小于需求量，因此设一虚设(xūshè)产地A4,它的产量为需求量与产量的差20，与这一项有关的运输费用一般为零。因为B2地区的115个单位必须满足，即不能有物资从A4运往B2地区，于是取相应的费用为M（M是一个充分大的正数），以保证在求最小运输费用的前提下，该变量的值为零。销地产地B1B2B3B4B5产量A1101520204050A22040153030100A33035405525130需求25115603070280300第五十一页，共66页。可以建立如下产销平衡的运输(yùnshū)费用表销地产地B1B2B3B4B5产量A1101520204050A22040153030100A33035405525130A40M00020需求25115603070第五十二页，共66页。例3-6某研究院有B1、B2、B3三个区。每年取暖分别需要用煤3500吨、1100吨、2400吨，这些煤都要由A1、A2两处煤矿负责供应，价格、质量均相同。A1、A2煤矿的供应能力分别为1500吨、4000吨，运价（元/吨）如下表。由于需求大于供给，经院研究决定(juédìng)B1区供应量可减少0—900吨，B2区必须满足需求量，B3区供应量不少于1600吨，试求总费用为最低的调运方案。销地产地B1B2B3产量A11751952081500A21601822154000需求量350011002400第五十三页，共66页。由于B1区供应量可减少(jiǎnshǎo)0—900吨，B3区供应量不少于1600吨，可以把B1区和B3区分别设为两个区：一个为必须满足需求量的区域，另一个为可以调整供应量的区域。原问题化为五个需求区域B1、B1’、B2、B3、B3’的问题，同时增加一个虚设的产地A3。在运输费方面,必须满足需求量的相应变量，运费的取值为M，可调整需求量的相应变量，运费的取值为0，作出产销(chǎnxiāo)平衡的运价表解：这是需求量大于生产量的运输(yùnshū)问题第五十四页，共66页。销地产地B1B1*B2B3B3*产量A11751751952082081500A21601601822152154000A2M0MM01500需求量260090011001600800第五十五页，共66页。例3-7某公司(ɡōnɡsī)生产某种规格的设备，由于生产与季节有关系，生产能力与成本有差异，如下表所示。某种规格(guīgé)设备各季节的生产能力与成本第一季度第二季度第三季度第四季度生产能力(台)500700600200成本(万元/台）9.810.510.310.6该厂年初(niánchū)签订的合同规定：当年一、二、三、四每个季度末分别需要提供200、300、500、400台这种规格的设备。如果生产出来的设备当季不交货，每台每积压一个季度需储存、维护等费用为万元。试求在完成合同的前提下，使该厂全年生产总费用为最小的决策方案。第五十六页，共66页。解：设xij为第i季度生产的第j季度交货的设备数目(shùmù)，则问题的线性规划模型为：cij=第i季度每台的生产成本(j-i)（储存(chǔcún)、维护等费用）。计算可得：

c11=9.8,c12=9.95,c13=10.1,c14=10.25,c22=10.5,c23=10.65,c24=10.8,c33=10.3,c34=10.45,c44=10.6。第五十七页，共66页。于是得到(dédào)目标函数：

x11x12x13x14+x22x23x24x33+x34x44x11=200x12+x22=300x13+x23+x33=500x14+x24+x34+x44=400

交货(jiāohuò)：生产(shēngchǎn)：x11+x12+x13+x14≤500x22+x23+x24≤700x33+x34≤600x44≤200xij

0i=1,2,3,4ji第五十八页，共66页。由于产大于销，虚构一个(yīɡè)销地，可构造下列产销平衡问题:各季节(jìjié)的生产、交货费用表交货生产第一季度第二季度第三季度第四季度虚设交货生产能力第一