管理运筹学 第7章 运输问题

第七章运输问题§1运输模型§2运输问题的计算机求解§3运输问题的应用§4*运输问题的上作业法例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：产销平衡问题：总产量=总销量设xij为从产地Ai运往销地Bj的运输量，得到以下运输量表：Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0(i=1、2；j=1、2、3〕§1运输模型§1运输模型一般运输模型：产销平衡A1、A2、…、Am表示某物资的m个产地；B1、B2、…、Bn表示某物质的n个销地；si表示产地Ai的产量；dj表示销地Bj的销量；cij表示把物资从产地Ai运往销地Bj的单位运价。设xij为从产地Ai运往销地Bj的运输量，得到以下一般运输量问题的模型：mnMinf=cijxiji=1j=1ns.t.xij=sii=1,2,…,mj=1mxij=djj=1,2,…,ni=1xij≥0(i=1,2,…,m;j=1,2,…,n)变化：1〕有时目标函数求最大。如求利润最大或营业额最大等；2〕当某些运输线路上的能力有限制时，在模型中直接参加约束条件〔等式或不等式约束)；3〕产销不平衡时，可参加假想的产地〔销大于产时〕或销地〔产大于销时〕。§2运输问题的计算机求解例2、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：增加一个虚设的销地运输费用为0§2运输问题的计算机求解例3、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：增加一个虚设的产地运输费用为0§3运输问题的应用一、产销不平衡的运输问题例4、石家庄北方研究院有一、二、三三个区。每年分别需要用煤3000、1000、2000吨，由河北临城、山西盂县两处煤矿负责供给，价格、质量相同。供给能力分别为1500、4000吨，运价为：由于需大于供，经院研究决定一区供给量可减少0--300吨，二区必须满足需求量，三区供给量不少于1500吨，试求总费用为最低的调运。解：根据题意，作出产销平衡与运价表：这里M代表一个很大的正数，其作用是强迫相应的x31、x33、x34取值为0。§3运输问题的应用一、产销不平衡的运输问题例5、设有A、B、C三个化肥厂供给1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表：试求总费用为最低的化肥调拨方案。解：根据题意，作出产销平衡与运价表：最低要求必须满足，因此把相应的虚设产地运费取为M，而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为0。对应4〞的销量50是考虑问题本身适当取的数据，根据产销平衡要求确定D的产量为50。§3运输问题的应用二、生产与储存问题例6、某厂按合同须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。该厂各季度的生产能力及生产每台柴油机的本钱如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。§3运输问题的应用解：设xij为第i季度生产的第j季度交货的柴油机数目，那么应满足：交货：x11=10生产：x11+x12+x13+x14≤25x12+x22=15x22+x23+x24≤35x13+x23+x33=25x33+x34≤30x14+x24+x34+x44=20x44≤10目标函数：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x44把第i季度生产的柴油机数目看作第i个生产厂的产量；把第j季度交货的柴油机数目看作第j个销售点的销量；本钱加储存、维护等费用看作运费。可构造以下产销平衡问题：§3运输问题的应用二、生产与储存问题例7、光明仪器厂生产电脑绣花机是以产定销的。1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表：上年末库存103台绣花机，如果当月生产出来的机器当月不交货，那么需要运到分厂库房，每台增加运输本钱万元,每台机器每月的平均仓储费、维护费为万元。在7--8月份销售淡季，全厂停产1个月，因此在6月份完成销售合同后还要留出库存80台。加班生产机器每台增加本钱1万元。问应如何安排1--6月份的生产，可使总的生产费用〔包括运输、仓储、维护〕最少？§3运输问题的应用解：这个生产存储问题可化为运输问题来做。考虑：各月生产与交货分别视为产地和销地1〕1--6月份合计生产能力〔包括上年末储存量〕为743台，销量为707台。设一假想销地销量为36；2〕上年末库存103台，只有仓储费和运输费，把它列为第0行；3〕6月份的需求除70台销量外，还要80台库存，其需求应为70+80=150台；4〕1--6表示1--6月份正常生产情况，1’--6’表示1--6月份加班生产情况。产销平衡与运价表：§3运输问题的应用用“管理运筹学〞软件解得的结果是：1-6月最低生产费用为万元，每月的销售安排如下表所示§3运输问题的应用三、转运问题：在原运输问题上增加假设干转运站。运输方式有：产地转运站、转运站销地、产地产地、产地销地、销地转运站、销地产地等。例8、腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产400台，广州分厂每月生产600台。该公司在上海和天津有两个销售公司负责对南京、济南、南昌、青岛四个城市的仪器供给。另外因为大连距离青岛较近，公司同意大连分厂向青岛直接供货，运输费用如图，单位是百元。问应该如何调运仪器，可使总运输费用最低？图中1-广州、2-大连、3-上海、4-天津、5-南京、6-济南、7-南昌、8-青岛§3运输问题的应用解：设xij为从i到j的运输量，可得到有以下特点的线性规划模型：目标函数：Minf=所有可能的运输费用〔运输单价与运输量乘积之和〕约束条件：对产地〔发点〕i：输出量-输入量=产量对转运站〔中转点〕：输入量-输出量=0对销地〔收点〕j：输入量-输出量=销量目标函数：Minf=2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48约束条件：.x13+x14≤600(广州分厂供给量限制〕x23+x24+x28≤400(大连分厂供给量限制〕x13+x23=+x35+x36+x37+x38〔上海销售公司，转运站〕x14+x24=x45+x46+x47+x48〔天津销售公司，转运站〕x35+x45=200〔南京的销量〕x36+x46=150〔济南的销量〕x37+x47=350〔南昌的销量〕x38+x48+x28=300〔青岛的销量〕xij≥0,i,j=1,2,3,4,5,6,7,8用“管理运筹学〞软件求得结果：x13=550x14=50；x23=0x24=100x28=300；x35=200x36=0x37=350x38=0；x45=0x46=150x47=0x48=0。最小运输费用为：4600百元§3运输问题的应用例9、某公司有A1、A2、A3三个分厂生产某种物资，分别供给B1、B2、B3、B4四个地区的销售公司销售。假设质量相同，有关数据如下表：试求总费用为最少的调运方案。假设：1.每个分厂的物资不一定直接发运到销地，可以从其中几个产地集中一起运；2.运往各销地的物资可以先运给其中几个销地，再转运给其他销地；3.除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。§3运输问题的应用运价如下表：解：把此转运问题转化为一般运输问题：1、把所有产地、销地、转运站都同时看作产地和销地；2、运输表中不可能方案的运费取作M，自身对自身的运费为0；3、Ai：产量为20+原产量，销量为20；Ti：产量、销量均为20；Bi：产量为20，销量为20+原销量，其中20为各点可能变化的最大流量；4、对于最优方案，其中xii为自身对自身的运量，实际上不进行运作。§3运输问题的应用扩大的运输问题产销平衡与运价表：§4*运输问题的表上作业法表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。运输问题都存在最优解。计算过程〔假设产销平衡〕：1.找出初始根本可行解。对于有m个产地n个销地的产销平衡问题，那么有m个关于产量的约束方程和n个关于销量的约束方程。由于产销平衡，其模型最多只有m+n-1个独立的约束方程，即运输问题有m+n-1个基变量。在m×n的产销平衡表上给出m+n-1个数字格，其相对应的调运量的值即为基变量的值。2.求各非基变量的检验数，即检验除了上述m+n-1个基变量以外的空格的检验数判别是否到达最优解，如果已是最优，停止计算，否那么转到下一步。3.确定入基变量和出基变量，找出新的根本可行解。在表上用闭回路法调整。4.重复2、3直到得到最优解。§4*运输问题的表上作业法例10.喜庆食品公司有三个生产面包的分厂A1，A2，A3，有四个销售公司B1，B2，B3，B4，其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公司的单位运价如表所示，在表中产量与销量的单位为吨，运价的单位为百元/吨。问该公司应如何调运产品在满足各销点的需求量的前提下总运费最少？这是一个产销平衡的运输问题，因此不需要再设假想产地和销地了。销地产地B1B2B3B4产量A13113107A219284A3741059销量36562020§4*运输问题的表上作业法一、确定初始根本可行解为了把初始根本可行解与运价区分开，我们把运价放在每一栏的右上角，每一栏的中间写上初始根本可行解〔调运量〕。1.西北角法：先从表的左上角〔即西北角〕的变量x11开始分配运输量，并使x11取尽可能大的值，即x11=min(7,3)=3,那么x21与x31必为零。同时把B1的销量与A1的产量都减去3填入销量和产量处，划去原来的销量和产量。同理可得余下的初始基本可行解。销地产地B1B2B3B4产量A134740A222420A336960销量30620530602020311310851029471§4*运输问题的表上作业法2.最小元素法西北角法是对西北角的变量分配运输量，而最小元素法是就近供给，即对单位运价最小的变量分配运输量。在表上找到单位运价最小的x21，并使x21取尽可能大的值，即x21=min(4,3)=3,把A1的产量改为1，B1的销量改为0，并把B1列划去。在剩下的3×3矩阵中再找最小运价，同理可得其他的根本可行解。一般来说用最小元素法求得的初始根本可行解比西北角法求得的总运价要少。这样从用最小元素法求得的初始根本可行解出发求最优解的迭代次数可能少一些。销地产地B1B2B3B4产量A143730A231410A363930销量30605406302020311310851029471§4*运输问题的表上作业法在求初始根本可行解时要注意的两个问题：1.当我们取定xij的值之后，会出现Ai的产量与Bj的销量都改为零的情况，这时只能划去Ai行或Bj列，但不能同时划去Ai行与Bj列。2.用最小元素法时，可能会出现只剩下一行或一列的所有格均未填数或未被划掉的情况，此时在这一行或者一列中除去已填上的数外均填上零，不能按空格划掉。这样可以保证填过数或零的格为m+n-1个，即保证基变量的个数为m+n-1个。§4*运输问题的表上作业法二、最优解的判别1.闭回路法所谓闭回路是在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，只有遇到代表基变量的填入数字的格才能向左或右转90度〔当然也可以不改变方向〕继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭回路。一个空格存在唯一的闭回路。所谓闭回路法，就是对于代表非基变量的空格〔其调运量为零〕，把它的调运量调整为1，由于产销平衡的要求,我们必须对这个空格的闭回路的顶点的调运量加上或减少1。最后我们计算出由这些变化给整个运输方案的总运输费带来的变化。如果所有代表非基变量的空格的检验数也即非基变量的检验数都大于等于零，那么已求得最优解，否那么继续迭代找出最优解。§4*运输问题的表上作业法从非基变量x11出发，找到一个闭回路如上表所示。回路有四个顶点，除x11外，其余都为基变量。现在把x11的调运量从零增加为1吨，运费也增加了3元，为了使A1产量平衡，x13必须减少1吨，运费减少3元。为了B3的销量平衡，x23必须增加1吨，运费增加2元。同理把x21减少1吨，运费减少1元。调整后，总运费增加了3-3+2-1=1元。说明如果让x11为基变量，运费就会增加，其增加值1作为x11的检验数，为了区别调整量，我们把1加圈。用同样的方法可以找出所有空格〔即非基变量〕的检验数。销地产地B1B2B3B4产量A1147A2314A39销量36562020311310851029471§4*运输问题的表上作业法2.位势法所谓位势法，我们对运输表上的每一行赋予一个数值ui，对每一列赋予一个数值vj，它们的数值是由基变量xij的检验数所决定的，那么非基变量xij的检验数就可以用公式求出。我们先给u1赋个任意数值，不妨设u1=0，那么从基变量x13的检验数求得v3=c13-u1=3-0=3。同理可以求得v4=10，u2=-1等等见上表。检验值的求法即用公式，如。销地产地B1B2B3B4uiA112430A2311-1-1A3106123-5vj293102020311310851029471§4*运输问题的表上作业法三、改进运输方案的方法——闭回路调整法当表中的某个检验数小于零时，方案不为最优，需要调整。方法是：选取所有负检验数最小的非基变量作为入基变量，以求尽快实现最优。本例中取，说明增加一个单位的x24运输量，可使得总运费减少1。在以x24为出发点的闭回路中，找出所有偶数的顶点的调运量：x14=3，x23=1，x24=min(3,1)=1。把所有闭回路上为偶数顶点的运输量都减少这个值，奇数顶点的运输量都增加这个值(见下表)。销地产地B1B2B3B4uiA14(+1)3(-1)0A231(-1)+1-1A363-5vj293102020311310851029471§4*运输问题的表上作业法对上表用位势法进行检验如下表销地产地B1B2B3B4产量A1527A2314A3639销量36562020销地产地B1B2B3B4uiA102520A23211-1A396123-5vj293102020311310851029471§4*运输问题的表上作业法四、如何找多个最优方案识别是否有多个最优解的方法和单纯形表法一样，只需看最优方案中是否存在非基变量的检验数为零。如在此题中给出的最优运输方案中x11的检验数为0，可知此运输问题有多个最优解。只要把x11作为入基变量，调整运输方案，就可得到另一个最优方案。销地产地B1B2B3B4A1(+2)52(-2)A23(-2)1(+2)A363销地产地B1B2B3B4A125A213A363