运筹学运输问题[1].pptx

运输问题简介运输问题是线性规划问题的特例。产地：产地：货物发出的地点。销地：销地：货物接收的地点。产量：产量：各产地的可供货量。销量：销量：各销地的需求数量。运输问题就是研究如何组织调运，既满足各销地的需求，又使总运费最小。一、运输模型引例：引例：某饮料在国内有三个生产厂，分布在城市A1、A2、A3,其一级承销商有4个，分布在城市B1、B2、B3、B4，已知各厂的产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为Cij，为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。销地销地产地产地B1B2B3B4产量产量A1 41241116A2 2103910A3 8511622销量销量 814121448(1)(1)决策变量决策变量。设从Ai到Bj的运输量为xij，(2)(2)目标函数目标函数 minZ=4x11+12x12+4x13+11x14+2x21+10 x22+3x23+9x24+8x31+5x32+11x33+6x34(3)(3)约束条件约束条件。产量之和等于销量之和,故要满足：运输问题的运输问题的LP模型模型 供应平衡条件供应平衡条件产地产地A1：x11+x12+x13+x14=16产地产地A2：x21+x22+x23+x24=10产地产地A3：x31+x32+x33+x34=22销售平衡条件销售平衡条件销地销地B1：x11+x21+x31=8销地销地B2：x12+x22+x32=14销地销地B3：x13+x23+x33=12销地销地B4：x14+x24+x34=14非负性约束非负性约束 xij0 (i=1,2,3；j=1,2,3,4)二、表式运输模型 销地产地A1A2Am产量a1a2amB1B2Bn销地b1b2bnc11c12c1nc21 c22c2ncm1cm2cmn x11 x12 x1nx21 x22 x2n xm1 xm2 xmn三、运输问题的三种类型 产销平衡产大于销产大于销产小于销四、运输模型的特点决策变量mn 约束方程m+n 系数矩阵的结构如下：x11x12x1nx21x22x2nxm1xm2 xmnm行行n列列例题的系数矩阵约束约束1约束约束2约束约束3约束约束4约束约束5约束约束6约束约束7运输问题求解思路先找到一个初始基可行解，判断其是否最优？如果是，计算结束，得到最佳运输方案。如果不是，则迭代到相邻的基可行解（向目标函数减少的方向），直到求得最优解！为了能按上述思路求解运输问题，要求每一步都必须是基可行解：（1）解必须满足模型中的所有约束条件（2）基变量对应的约束方程组的系数列向量线性无关（3）解中非零变量xij的个数不能大于（m+n-1)个，原因是运输问题中虽有(m+n)个结构约束条件，但由于总产量等于总销量，故只有(m+n-1)个结构约束条件是线性独立的，所以一般我们在迭代过程中都保持基变量的个数为(m+n-1)个。表上作业法表上作业法适合于产销平衡的运输问题求解步骤：l找出初始方案（初始基可行解）：在mn维产销平衡表上给出m+n-1个数字。l最优性检验：计算各非基变量的检验数，当ij0最优（因为现在是求最小化问题）。l方案调整与改进：确定进基变量和离基变量，找出新的基可行解。一、确定初始方案西北角法西北角法最小元素法最小元素法 “就近运给”，从单位运价表中最小运价开始确定供销关系，逐次挑选最小元素，安排运量minai,bj。最大差额法（沃格尔法）最大差额法（沃格尔法）不能按最小运费就近供应，就考虑次小运费。各行(各列)的最小运费与次小运费之差称为行差(列查)。差额越大，说明不能按最小运费调运时，运费增加最多。对最大差额处就采用最小运费调运。西北角法西北角法按照运输表格中的位置，安排最西北角（也就是左上角的位置），优先运输。销地销地产地产地B1B2B3B4产量产量A141241116A22103910A38511622销量销量814121448初始基可行解：初始基可行解：x11=8,x12=8,x22=6,x23=4,x33=8,x34=14，Z=3728864814（8）最小元素法人们容易直观想到，为了减少运费，应优先考虑单位运价最小（或运距最短）的供销业务，最大限度地满足其供销量，即对所有的i和j，从单位运价表中逐次挑选最小元素，安排运量 minai,bj，若xij=ai,则产地Ai的可供物品已用完，以后不再继续考虑这个产地，且Bj的需求量由bj减少为bj-ai，即当产小于销，划去该元素所在行；如果xij=bj，则销地Bj的需求已全部得到满足，以后不再考虑这个销地，且Ai的可供量由ai减少为 ai-bj，即当产大于销，划去该元素所在列；然后在余下的继续进行，直到安排完所有供销任务。销地销地产地产地B1B2B3B4产量产量A141241116A22103910A38511622销量销量814121448初始基可行解：初始基可行解：x13=10,x14=6,x21=8,x23=2,x32=14,x34=8，Z=24682101486最大差额法（沃格尔法）初看起来，最小元素法十分合理，但是，有时按某一最小单位运价优先安排物品调运时，却可能导致不得不采用运费很高的其它供销点对，从而使整个运输费用增加。对每一个供应地或销售地，均可由它到各销售地或到各供应地的单位运价中找出最小单位运价次最小单位运价，并称这两个单位运价之差为该供应地或销售地的罚数。当罚数的值不大，当不能按最小单位运价安排运输时当不能按最小单位运价安排运输时造成的运费损失不大；反之，如果罚数的值很大，造成的运费损失不大；反之，如果罚数的值很大，不按最小运价组织运输就会造成很大的损失，故不按最小运价组织运输就会造成很大的损失，故应尽量按最小单位运价安排运输应尽量按最小单位运价安排运输。销地销地产地产地B1B2B3B4产量产量A141241116A22103910A38511622销量销量814121448列列罚罚数数行罚数行罚数10111 2 5 1 31420122 2 1 383013 2 1 284764 1 2125005 224初始基可行解：初始基可行解：x13=12,x14=4,x21=8,x24=2,x32=14,x34=8，Z=244二、解的最优性检验从以上得的初始解之后，即应对这个解进行最优性判别，看它是不是最优解。闭回路法闭回路法对偶变量法对偶变量法闭回路法要判定运输问题的某个解是否为最优解，可仿照一般单纯形法，检验这个解的各非基变量（对应于运输表中的空格）的检验数，若有某空格（Ai,Bj)的检验数为负，说明将xij变为基变量将使运输费用减少，故当前这个解不是最优解。若所有空格的检验数全非负，则不管怎样变换解均不能使运输费用降低，即目标函数值已无法改进，这个解就是最优解。由线性规化的模型可以看出：由线性规化的模型可以看出：ij=cij CBPij=cij CBB-1Pij运输问题的目标函数要求为最小，即当运输问题的目标函数要求为最小，即当 ij 0视为最优。视为最优。也就是说只要存在也就是说只要存在 ij小零，此时就不能得到最优解。小零，此时就不能得到最优解。闭回路法就为我们提供了一种计算非基闭回路法就为我们提供了一种计算非基变量检验数的方法变量检验数的方法销地销地产地产地B1B2B3B4产量产量A141241116A22103910A38511622销量销量81412144882101486以最小元素法C11-C21+C23-C31=4-2+3-4=1C22-C32+C34-C14+C13-C23=10-5+6-11+4-3=1这样会得到初始调运方案的检验数 销地产地 B1B2B3B4产量A112A21-1A31012销量在这个之中存在检验数小于零，所以此时没有得到最优解。从中可以看出为了求某个空格（非基变量）的检验数，先要找出它在运输表上的闭回路，这个闭回路的顶点，除这个空格外，其它均为填有数字的格（基变量格），它是由水平线段和竖直线段依次联接这些顶点构成的一封闭多边形，可以证明，每个空格都唯一存在这样的一条闭回路。闭回路可以是一个简单的矩形，也可以是由水平和竖直边线组成的其它更复杂的封闭多边形。位于闭回路上的一组变量，它们对应的运输问题约束条件的系数列向量线性相关，因而在运输问题基可行解的迭代过程中，不允许出现全部顶点由填有数字的格构成的闭回路。这就是说，在确定运输问题的基可行解时，除要求非零变量的个数为（m+n-1）个外，还要求运输表中填有数字的格不构成闭回路（当然还要满足所有约束条件）。用前述最小元素法，西北角法和VOGEL法得到的解满足这些条件。对偶变量法(dual variable method)也称为位势法用闭回路法判定一个运输方案是否为最优方案，需要找出所有空格的闭回路，并计算出其检验数。当运输问题的产地和销地很多时，空格的数目很大，计算检验数的工作十分繁重，而且对偶变量法就要简便的多。对于产销平衡问题，若用 分别表示前m个约束等式相应的对偶变量，用 表示后n个等式约束相应的对偶变量。即有对偶变量及对偶规划：(3.7)线性规划问题的检验数Xj的检验数可表示为：所以运输问题某量的Xij的检验数为：现设我们已得到了运输问题的一个基可行解，其基变量是：对应于这些基变量的检验数都为零，即这些基变量的检验数可写为方程组：（3.9）显然，上述方程组有m+n-1 个方程。运输表中每个产地和每个销地都对应原运输问题的一个约束条件，从而也对应各自的一个对偶变量；由于运输表中每行和每列都含有基变量，可知这样构造的方程组中含有全部m+n个对偶变量。可以证明，方程组(3.9)有解，且由于对偶变量数比方程数多一个，故解不唯一。方程(3.9)的解称为位势位势。若由(3.9)解得的某组解满足(3.7)的所有约束条件，即对所有 i 和 j 均有其检验数大于0,即：由前面的互补松定理，此时对偶问题与原问题同时达到最优解。若由(3.9)解得的某组解不满足(3.7)的所有约束条件，即非基变量的检验数有负值存在，则上面得到的运输问题的解不是最优解，需要进行解的调整。用位势法对表3-5给出的运输问题作最优性检验销地销地产地产地aB1B2B3B4产量产量A141241116A22103910A38511622销量销量81412144882101486uiu1u2u3 vj v1 v2 v3 v4(1)对于上表中增加一位势列ui和位势行vj，如下所示(2)计算位势，依据上面的基变量建立方程组，并据此计算出运输表各行和各列的位势。对于左式的计算，为计算方便，常任意指定一位势等于一个较小的整数或零。为了和书上一致，我们假定u2=0，由此可算出：V1=3,V3=3,u1=1,v4=10,u3=-4V2=9,将其填入表中的圆括号内。如上页所示。一般情况下我们不用列方程求解，直接在表中假设任意一个位势为0,不妨我们也假设u2=0销地销地产地产地aB1B2B3B4产量产量A141241116A22103910A38511622销量销量81412144882101486Ui vjU2(0)V1(2)V3(3)U1(1)V4(10)U3(-4)V2(9)销地销地产地产地aB1B2B3B4产量产量A141241116A22103910A38511622销量销量814121448Ui vjU2(0)V1(2)V3(3)U1(1)V4(10)U3(-4)V2(9)(3)计算各个非基变量的检验数计算各个非基变量的检验数111=C11-U1-V1=121-11012由以上可以看出，位势法与用闭回路法算出的检验数完全相同，因24=-10,故这个解不是最优解。三、解的改进对于某一个ij小于0，则此时不存在最优解，所以必须对其进行改进。改进的方法：在运输表中找出这个空格对应的闭回路Lij，在满足所有约束条件的前提下，使Xij尽量增大并相应调整此闭回路上其它顶点的运输量，以得到另一个更好的基可行解。解改进的具体步骤：解改进的具体步骤：（1）以Xij为换入变量，找出它在运输表中的闭回路；（2）以空格（Ai,Bj)为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的顶点依次编号。（3）在闭回路上的所有偶数顶点中，找出运输量最小 的项点（格子），以该格中的变量为换出变量（4）以 为调整量，将该闭回路上所有奇数顶点处的运输量都增加这一数值，所有偶数顶点处的运输量都减去这一数值，从而得出一新的运输方案。该运输方案的总运费比原运输方案减少，改变量等于 然后，再对得到的新解进行最优性检验，如不是最优解，就重复以上步骤继续进行调整，一直到得出最优解为止。继续对上例的解进行改进解：由前面的表可知，由于 24=-10,故以X24为换入变量，它对应的闭回路示于如下表销地销地产地产地aB1B2B3B4产量产量A141241116A22103910A38511622销量销量81412144882101486在该闭回路的偶数顶点位于格（A1，B4）和（A2，B3），由于销地销地产地产地aB1B2B3B4产量产量A141241116A22103910A38511622销量销量81412144882101486所以对 x24+2 x14-2 x13+2 x23-2+2-2+2-2销地销地产地产地aB1B2B3B4产量产量A141241116A22103910A38511622销量销量81412144882121484现在用位势法或闭回路法求这个新基可行解各非基变量的检验数，结果如上图所示(0)(2)(2)(1)(9)(12)由于所有非基变量的检验数全非负，故这个解为最优解。从图中我们还可以看出，有一个非基变量的检验数为0，所以存在无穷多最优解。补充说明1、若运输问题的某一基可行解有几个非基变量的检验数均为负，在继续进行迭代时，取它们中的任一变量均可使目标函数值得到改善，但通常取ij0中最小者对应的变量为换入变量。2、当迭代到运输问题的最优解时，如果某非基变量的检验数等于零，则说明该运输问题有多重（无穷多）最优解。3、当运输问题某部分产地的产量和，与某一部分销地的销量和相等时，在迭代过程中有可能在某个格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。在运输问题中，退化解是时常发生的。为了使表上作业法的迭代工作进行下去，退化时应在同时划去的一行或一列中的某个格中填入数字0，表示这个格中的变量是取值为0的基变量，使迭代过程中基可行解的分量恰好为（m+n-1)个。第三节 运输问题的进一步讨论在运输问题中，并不是所有的运输问题都是产销平衡的，往存在产销不平衡问题。所以要利用表上作业法进行，就必须将产销不平衡问题化为产销平衡的问题进行求解。产大于销产大于销对于这种问对于这种问题，我们可题，我们可以增加一个以增加一个销地，使其销地，使其变为产销平变为产销平衡问题！衡问题！例：销地销地产地产地B1B2B3产量产量A159215A231718A362817销量销量181216增加一个销地销地销地产地产地B1B2B3产量产量A159215A231718A362817销量销量18121650-4650465050B40004初始基可行解初始基可行解(最小元素法最小元素法)销地销地产地产地B1B2B3B4产量产量A1592015A2317018A3628017销量销量1812164121561214 初始基可行解：初始基可行解：x13=15,x21=6,x22=12,x31=12,x33=1,x34=4，Z=140最优性检验销地销地产地产地B1B2B3B4产量产量uiA159215015A2361127018A36122810417销量销量1812164vj0260-63-25 511116 62 23 3-2-2 非基变量非基变量x32的检验数的检验数 32=-2，即让非基变量，即让非基变量x32进基。进基。闭回路调整x32 进基进基最小调整量为最小调整量为12，x22 离基离基销地销地产地产地B1B2B3B4产量产量A159215015A2361127018A36122 x32 810417销量销量1812164-+-+非最优方案的调整l所有偶点的值都加上调整量；所有奇点的值都减去调整量。基可行解：基可行解：x13=15,x21=18,x31=0,x32=12,x31=1,x34=4，Z=34销地销地产地产地B1B2B3B4产量产量A159215015A2317018A362810417销量销量181216461212 180 12 l基变量的检验数ij=cij ui vj=0，且令u1=0，计算位势量ui和vj最优性检验最优性检验 所有非基变量所有非基变量xij的检验数的检验数 ij=cij ui vj0，即得最优解。即得最优解。销地销地产地产地B1B2B3B4产量产量uiA159215015A231817018A360212810417销量销量1812164vj0260-4-635 513136 62 23 32 2产小于销对于这种问对于这种问题，我们可题，我们可以增加一个以增加一个产地，使其产地，使其变为产销平变为产销平衡问题！衡问题！增加一个产地例：例：销地销地产地产地B1B2B3产量产量A141210A234312销量销量8105销地销地产地产地B1B2B3产量产量A141210A234312A3销量销量810523-22000122232323初始基可行解销地销地产地产地B1B2B3产量产量A141210A234312A30001销量销量8105100571 初始基可行解：初始基可行解：x12=10,x13=0,x21=7,x23=5,x31=1，Z=46最优性检验销地销地产地产地B1B2B3产量产量uiA141102010A23743512A301001销量销量8105vj01212-22 22 21 10 0检验数检验数 ij0，得最优解得最优解:x12=10,x13=0,x21=7,x23=5,x31=1，Z=46由于非基变量由于非基变量 x33 的检验数的检验数 33=0，为多最优解。，为多最优解。让让x33进基进基,x31离基离基,得另一最优解得另一最优解:x12=10,x13=0,x21=8,x23=4,x33=1上例上例x12=10,x13=0,x21=7,x23=5,x31=1，表示销地表示销地B1脱销脱销1个单位；个单位；然而然而x12=10,x13=0,x21=8,x23=4,x33=1，则表示销地则表示销地B3 脱销脱销1个单位；个单位；二、有转运的运输问题有时，需先将物品由产地运到某个中间转运站（可能是另外的产地、销地或中间转运仓库），然后再转运到销售目的地。有时，经转运比直接运到目的地更为经济。总之，在很多情况下，在决定运输方案时有必要把转运也考虑进去。对于这样的问题，求解起来相当复杂，我们简要的给大家说一下原理！第四节 运输问题应用举例生产与储存问题生产与储存问题例例1、某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。解：解：设 xij为第 i 季度生产的第 j 季度交货的柴油机数目，那末应满足：交货：x11 =10 生产：x11+x12+x13+x14 25 x12+x22 =15 x22+x23+x24 35 x13+x23+x33 =25 x33+x34 30 x14+x24+x34+x44 =20 x44 10 建立如下运输表：建立如下运输表：把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量；把第 j 季度交货的柴油机数目看作第 j 个销售点的销量；成本加储存费用看作运费。可构造下列产销平衡问题：目标函数：目标函数：Min f=10.8 x11+10.95 x12+11.1 x13+11.25 x14+11.1 x22+11.25 x23+11.4 x24 +11.0 x33+11.15 x34 +11.3 x44 例2：自来水分配问题：水价水价90元元/千吨，管理费，管理费45元元/千吨，引引水费价格水费价格如下表：如下表：供区水库甲乙丙丁供水量kt/dA1613221750B1413191560C192023-50最低需求kt/d3070010最高需求kt/d507030不限如何分配供水量，保障各区最低需求，获利最大？利润=收入-成本，收入最大，成本最小，则利润最大。收入：l每天供水总量是一常数，水价也是常数，则每天总收入也是常数。l每天供水总量若能全部售出，每天总收入则能达到最大。l丁区最高需求不限，每天总供水量能全售出。l每天总收入是常数，与水量分配无关，可以不与考虑。成本：l各区管理费相同45元/kt，每天售水总量是一常数，则管理费也是常数。l各区引水费不同，如果总的引水费达到最小，总成本则最低。l如何分配水量，既满足最低需求，又使总的引水费最低？分析分析最大需求量：l供水总量=50+60+50=160，四区最低需求量=30+70+10=110，故丁区最大需求量160-110+10=60。l四区最大需求=50+70+30+60=210，比供水总量160多50，则是一个产小于销的不平衡问题。产小于销的运输问题化为平衡问题，虚设水库D，供水量50。l各区的最低需求为基本需求，不允许脱销，不能由虚设水库D供水，故单位引水费（运费）为M。l各区的最大需求与最低需求的差为额外需求，可以由虚设水库D供水，故单位引水费（运费）为0。供区水库供水量A50B60C50甲1甲2乙丙丁1丁216161322171714141319151519192023MM销量302070301050DM0M0M050用表上作业法求得最优方案供区水库甲1甲2乙丙丁1丁2供水量A5050B20103060C3020050D302050销量302070301050最优分配方案：水库最优分配方案：水库A向乙区供水向乙区供水50，水库，水库B分别向乙区、丁分别向乙区、丁区供水区供水20和和40，水库，水库C向甲区供水向甲区供水50，不给丙区供水。，不给丙区供水。最小引水费：最小引水费：13 50+13 20+15(10+30)+19(30+20)=2460 引水引水管理费：管理费：45(50+60+50)=7200 总成本：总成本：2460+7200=9600 总收入：总收入：90(50+60+50)=14400 最大获利：最大获利：14400-9600=47403.7 3.8表表3-35 3-9 及下例及下例1、设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表，试求总费用为最低的化肥调拨方案。2、石家庄北方研究院有一、二、三三个区。每年分别需要用煤3000、，1000、2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000吨，运价为如下表，由于需大于供，经院研究决定一区供应量可减少0-200吨，二区必须满足需求量三区供应量不少于1700吨，试求总费用为最低的调运方案。1、参考答案、参考答案解：解：根据题意，作出产销平衡与运价表如下，最低要求必须满足，因此把相应的虚设产地运费取为 M，而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为 0。对应 4”的销量 50 是考虑问题本身适当取的数据，根据产销平衡要求确定 D的产量为 50。2、参考答案：、参考答案：解：解：根据题意，作出产销平衡与运价表如下，这里 M 代表一个很大的正数，其作用是强迫相应的 x31、x33、x34取值为0。本章小结End