管理运筹学讲义第3章运输问题

石家庄经济学院管理科学与工程学院1第3章运输问题Subtitle学习要点•1．掌握运输问题的数学模型、系数矩阵特殊形式•2．掌握用西北角法、最小元素法求初始基可行解•3．掌握位势法求解、牢固掌握三合一表格求解运输问题过程石家庄经济学院管理科学与工程学院2§3.1运输问题及其数学模型§3.2表上作业法§3.3产销不平衡的运输问题§3.4应用举例本章主要内容第3章运输问题石家庄经济学院管理科学与工程学院3§3.1运输问题及其数学模型问题的提出一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。回本章目录石家庄经济学院管理科学与工程学院4例3.1某公司从三个产地A1、A2、A3将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示销地产地B1B2B3B4产量A13113107A219284A3741059销量365620（产销平衡）问应如何调运，可使得总运输费最小?石家庄经济学院管理科学与工程学院5解：这是一个产销平衡的运输问题，设xij为从产地Ai运往销地Bj的运输量（i=1，2，3；j=1，2，3，4）该运输问题的线性规划模型如下：Minf=3x11+11x12+3x13+10x14+x21+9x22+2x23+8x24+7x31+4x32+10x33+5x34石家庄经济学院管理科学与工程学院6s.t.x11+x12+x13+x14=7x21+x22+x23+x24=4x31+x32+x33+x34=9x11+x21+x31=3x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6xij≥0(i=1、2、3；j=1、2、3石家庄经济学院管理科学与工程学院7其系数矩阵为：100010001000010001000100001000100010000100010001111100000000000011110000000000001111A共有m+n行，分别表示产地和销地；有mn列分别表示各变量；每列只有两个1，其余为0。石家庄经济学院管理科学与工程学院8运输问题的一般提法是：设某种物资有m个产地和n个销地。产地Ai的产量为；销地Bj的销量为。从第i个产地向第j个销地运输每单位物资的运价为Cij，这就是由多个产地供应多个销地的单品种物资运输问题。问如何调运这些物资才能使总运费达到最小。),,2,1(miai),,2,1(njbj石家庄经济学院管理科学与工程学院9表3-1产销平衡表销地产地B1B2…Bn产量A1A2┇Amx11x12…x1nx21x22…x2n┇┇┇┇xm1xm2…xmna1a2┇am销量b1b2…bn石家庄经济学院管理科学与工程学院10表3-2单位运价表销地产地B1B2…Bn产量A1A2┇Amc11c12…c1nc21c22…c2n┇┇┇┇cm1cm2…cmna1a2┇am销量b1b2…bn石家庄经济学院管理科学与工程学院11表中的表示由产地Ai向销地Bj运输物资的数量（即运量）。在产销平衡表3-1中，去掉最后一行和最后一列余下的部分，称为一个调运方案，或简称为一个方案。或者将上述两个表格合在一起，称为运输表（表3-3）。),,2,1;,2,1(njmixij石家庄经济学院管理科学与工程学院12销地产地B1B2…Bn产量A1x11x12…x1na1A2x21x22…x2na2Amxm1xm2…xmnam销量b1b2…bn11c12cnc121c22cnc21mc2mcmnc表3-3运输表石家庄经济学院管理科学与工程学院13下面分两种情况来讨论：（1）。即运输问题的总产量等于其总销量，这样的运输问题称为产销平衡的运输问题。（2）。即运输问题的总产量不等于总销量，这样的运输问题称为产销不平衡的运输问题。我们重点讨论产销平衡的运输问题及其求解方法。然后在此基础上讨论产销不平衡的运输问题应该如何转化为产销平衡的运输问题。njjmiiba11njjmiiba11石家庄经济学院管理科学与工程学院14若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案，数学模型为：0)13(,,2,1,,2,1..min1111ijmijijnjiijminjijijxnjbxmiaxtsxcz石家庄经济学院管理科学与工程学院15其中，ai和bj满足：(3-2)称为产销平衡条件。njjmiiba11石家庄经济学院管理科学与工程学院16将（3-1）的结构约束加以整理，可知其系数矩阵的结构比较松散，且特殊行行nmvvvuuuxxxxxxxxxnmmnmmnn1111111111111111112121212222111211石家庄经济学院管理科学与工程学院17该系数矩阵中对应于变量xij的系数向量Pij，其分量中除第i个和第m+j个为1以外，其余的都为零。即Tijp0,0,1,0,,0,1,0,,0石家庄经济学院管理科学与工程学院18根据运输问题的数学模型求出的运输问题的解，代表着一个运输方案，其中每一个变量xij的值表示由Ai调运数量为xij的物品给Bj。前已指出运输问题是一种线性规划问题，可设想用迭代法进行求解，即先找出它的某一个基可行解，再进行解的最优性检验，若它不是最优解，就进行迭代调整，以得到一个新的更好的解，继续检验和调整改进，直至得到最优解为止。ijxX石家庄经济学院管理科学与工程学院19为了能按上述思路求解运输问题，要求每步得到的解X=(xij)都必须是基可行解，这意味着:（1）解X必须满足模型中的所有约束条件；（2）解中基变量xij的个数不能大于(m+n-1)个；原因是运输问题中虽有(m+n)个约束条件，但由于总产量等于总销量，故只有(m+n-1)个约束条件是线性独立的。石家庄经济学院管理科学与工程学院20§3.2表上作业法表上作业法是求解产销平衡运输问题的一种简便而有效的方法，其求解工作在运输表上进行。其实质是单纯形法。但具体计算和术语有所有同。可归纳为以下步骤：回本章目录石家庄经济学院管理科学与工程学院21（1）找出初始基本可行解（初始运输方案）（2）求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。（3）确定换入变量和换出变量，找出新的基本可行解。（4）重复（2），（3）直到得到最优解为止。以上运算都可以在运输表上完成。石家庄经济学院管理科学与工程学院22§3.2.1初始基本可行解的确定与一般线性规划问题不同，产销平衡运输问题总是存在可行解。不难验证≥就是模型（3-1）的可行解。又因，目标函数值有下界，故产销平衡的运输问题必有最优解。);,,2,1;,,2,1(011njjmiijiijbadnjmidbax石家庄经济学院管理科学与工程学院23确定初始基本可行解的方法很多，一般希望方法是既简便，又尽可能接近最优解。下面介绍三种方法：最小元素法，西北角法和伏格尔（Vogel）法。石家庄经济学院管理科学与工程学院24（1）最小元素法最小元素法的基本思想是优先满足单位运价最小的供销业务。首先找出运价最小的，并以最大限度满足其供销量为原则确定供销业务。然后，在余下的未确定的供销业务中找运价最小的，同样以最大限度满足其供销量为原则确定供销业务，同样的方法反复进行直到确定了所有的供销业务，得到一个完整的调运方案即初始基本可行解为止。由于该方法基于优先满足单位运价最小的供销业务，故称为最小元素法。石家庄经济学院管理科学与工程学院25表3-5运输表（运价小者先安排）销产B1B2B3B4产量B1B2B3B4A17311310A241928A3974105需求3656201321344653103产销平衡表运价表石家庄经济学院管理科学与工程学院26（2）西北角法西北角法与最小元素法不同，它不是优先考虑具有最小单位运价的供销业务，而是优先满足运输表中西北角（左上角）上空格的供销需求。石家庄经济学院管理科学与工程学院27考虑例3.1某公司从三个产地A1、A2、A3将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示。石家庄经济学院管理科学与工程学院28销地产地B1B2B3B4产量A13113107A219284A3741059销量365620（产销平衡）问应如何调运，可使得总运输费最小?石家庄经济学院管理科学与工程学院29销产B1B2B3B4产量B1B2B3B4A17311310A241928A3974105需求365620342236产销平衡表运价表石家庄经济学院管理科学与工程学院30注：应用西北角法和最小元素法，每次填完数，都应只划去一行或一列。当填上一个数后行、列同时饱和时，也应任意划去一行(列)，然后在保留的列（行）没被划去的格内标一个0。例3.2某公司下属有生产一种化工产品的三个产地A1、A2、A3，有四个销售点B1、B2、B3、B4销售这种化工产品。各产地的产量、各销地的销量和各产地运往各销地每吨产品的运费（百元）如下表所示。石家庄经济学院管理科学与工程学院31销产B1B2B3B4产量B1B2B3B4A1753859A2402948A3806375需求35405565195产销平衡表运价表问应如何调运，可使得总运输费最小?石家庄经济学院管理科学与工程学院32解：用西北角法求初始基本可行解销产B1B2B3B4产量B1B2B3B4A1753859A2402948A3806375需求35405565195产销平衡表运价表35400401565石家庄经济学院管理科学与工程学院33（3）伏格尔法(沃格尔法Vogel)最小元素法的缺点是：为了节省一处的费用，有时造成在其它处要多花几倍的运价。伏格尔法考虑到，某产地的产品假如不能按最小运价就近供应，就考虑次小运价，这就有一个差额。差额越大，说明不能按最小运价调运时，运费增加越多。因而对差额最大的行或列，就应当采用最小运价调运。伏格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。石家庄经济学院管理科学与工程学院34销产B1B2B3B4产量B1B2B3B4A17311310A241928A3974105需求365620产销平衡表运价表251301160123212376512石家庄经济学院管理科学与工程学院35§3.2.2解的最优性检验用单纯形法解线性规划问题时，在迭代过程中每次求得一个基本可行解以后，都要检验它是不是最优解，如果不是最优解，就要继续进行迭代，直到求得最优解或者判定无最优解。对于运输问题来说，按单纯形法来求检验数并进行迭代是非常困难的。表上作业法是用以下两种方法来处理这个问题的：闭回路法和位势法。石家庄经济学院管理科学与工程学院36一、闭回路法在单纯形法中，为了检验一个基本可行解是不是最优解，需要求出所有非基变量的检验数。在运输问题中，每个空格对应一个非基变量。因此，我们需要求出每个空格的检验数。由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案。石家庄经济学院管理科学与工程学院37定义3.1闭回路是在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，只有遇到代表基变量的填入数字的格才能向左或右转90度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭回路。一个空格存在唯一的闭回路。石家庄经济学院管理科学与工程学院38①闭回路均为一封闭折线，它的每一条边，或为水平的，或为垂直的；②闭回路的每一条边（水平的或垂直的）均