运筹学 第3章 运输问题(18页).doc

-运筹学 第3章 运输问题-第 20 页第三章 运输问题在生产实际中，经常需要将某种物资从一些产地运往一些销地，因而存在如何调运使总的运费最小的问题。这类问题一般可用线性规划模型来描述，当然可以用单纯形法求解。但由于其模型结构特殊，学者们提供了更为简便和直观的解法表上作业法。此外，有些线性规划问题从实际意义上看，并非运输问题，但其模型结构类似运输问题，也可以化作运输问题进行求解。第一节 运输问题及其数学模型首先来分析下面的问题。 农产品经销公司有三个棉花收购站，向三个纺织厂供应棉花。三个收购站A1、A2、A3的供应量分别为50kt、45kt和65kt，三个纺织厂B1、B2、B3的需求量分别为20kt、70kt和70kt。已知各收购站到各纺织厂的单位运价如表31所示（单位：千元/kt），问如何安排运输方案，使得经销公司的总运费最少？表31纺织厂收购站B1B2B3A1A2A3462835567设xij表示从Ai运往Bj的棉花数量，则其运输量表如下表所示。表32纺织厂收购站B1B2B3供应量（kt）A1A2A3x11x21x31x12x22x32x13x23x33504565需求量（kt）207070160由于总供应量等于总需求量，因此，一方面从某收购站运往各纺织厂的总棉花数量等该收购站的供应量，即x11+x12+x13 = 50x21+x22+x23 = 45x31+x32+x33 = 65另一方面从各收购站运往某纺织厂的总棉花数量等该纺织厂的需要量，即x11+x21+x31 = 20x12+x22+x32 = 70x13+x23+x33 = 70因此有该问题的数学模型为min f= 4x11+8x12+5x13+6x21+3x22+6x23+2x31+5x32+7x33x11+x12+x13 = 50x21+x22+x23 = 45x31+x32+x33 = 65x11+x21+x31 = 20x12+x22+x32 = 70x13+x23+x33 = 70 xij0，i=1，2，3；j=1，2，3生产实际中的一般的运输问题可用以下数学语言描述。已知有m个生产地点Ai，i=1，m，可供应某种物资，其供应量（产量）为ai，i=1，m；有n个销售地点Bj，j=1，n， 需要该种物资，其需要量（销量）为bj，j=1，n； 从Ai到Bj运输单位物资的运价（单价）为cij； 设ai=bj，这些数据可汇总于如下产销平衡表，现要制定一个使总运费最小的调运方案。表33 运输问题产销平衡表销 地产地B1B2Bn产量A1c11c12c1na1A2c21c22c2na2Amcm1cm2cmnam销量b1b2bnaibj若用xij表示从Ai到Bj的运量，在产销平衡的条件下，要求得总运费最小的调运方案，其数学模型如下（模型Y）该模型中，包含了m×n个变量，（m+n）个约束条件，且有特殊结构的系数矩阵，即上述矩阵的列向量可用pij来描述，显然pij中除第i个元素和第m+j个元素为1以外，其余元素均为0。第二节 表上作业法一、运输问题数学模型的基本概念对于运输问题的数学模型（模型Y）有如下定理。定理3.1 运输问题的数学模型必有最优解。首先，运输问题一定有可行解；而任何单位运价cij0，因此对于任一可行解必有目标函数值大等于零，即目标函数有下界。因此，对于极小化的运输问题必有最优解。定理3.2 运输问题约束方程系数矩阵A的秩为m+n1，即R（A）=m+n1。由定理3.1可知，我们在求解运输问题时就不需要进行无最优解的判别；另外从定理3.2可知，运输问题任一基可行解的非零分量的个数不能多于m+n1，或者说基变量的个数为m+n1。定义3.1（闭回路的定义） 在运输问题的调运表中，凡能排成xi1j1，xi1j2，xi2j3，xisjs，xisj1形式的变量集合，称为一个闭回路，其中诸变量称为该闭回路的顶点。下表中即为两个闭回路。 表34B1B2B3B4B5B6B7A1x11x12x13x14x15x16x17A2x21x22x23x24x25x26x27A3x31x32x33x34x35x36x37闭回路1：x11，x12，x22，x23，x33，x31，x11；闭回路2：x15，x16，x36，x37，x27，x25，x15；闭回路有如下特点：每个顶点都是转角；每行或每列只有且仅有两个顶点；每个顶点的连线都是水平的或垂直的。定理3.3 运输问题m+n1个变量xi1j1，xi2j2，xisjs（s=m+n1）构成某一基可行解的基变量的充要条件是：不包含以这些变量为顶点的闭回路。该定理能帮助我们简便地求出基可行解或判别某一可行解是否为基可行解。二、表上作业法和一般线性规划一样，运输问题的最优解也一定可以在其基可行解中找到。类似于单纯形法，表上作业法仍然需要解决如下问题：（1）确定初始基可行解（2）最优解的判定；（3）基可行解的转换。（一）初始基可行解的确定确定初始基可行解的方法很多，如最小元素法、伏格尔法、西北角法等。这里仅介绍既常用又简便的方法最小元素法。这种方法的基本思想就是就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小。一直到求出初始基可行解为止。结合例3.2，给出最小元素法的具体步骤。 设有某物资从A1，A2，A3处运往B1，B2，B3，B4四个地方，各处供应量、需求量及单位运价见下表。问应如何安排运输方案，才能使总运费最少？ 表35销 地产地B1B2B3B4产量A1376450A2243320A3838930销量40201525100100（1）列出如表36所示的调运表（包括单价、产量与销量）；（2）在调运表中找出一个单位运价最小的格子，在相应的运量位置上填上尽可能大的数（必须满足约束条件）。如表36中，单位运价c21=2为最小，这样在c12所在格子相应运量位置上填上尽可能大的数20（满足A2产量为20的约束条件）；（3）在填有数字的格子所在行或者列运量应该为0的位置上打“×”，（即表示该运量为0，相应的变量为非基变量）且只能在行或列的方向上打“×”，不能同时在两个方向上打“×”；如第2行第1个填有运量为20的格子，由于A2的供应量已全部用完，因此，该行的其它格子的运量应全部为零，这样在相应的运量位置上打“×”。（4）在没有填数，也未打“×”的格子重复上述（2）、（3）步；（5）最后剩下的一行或列只能填数，不能打“×”。 表36销 地产地B1B2B3B4产量A120×525503764A220×××202433A3×2010×308389销量40201525表中给出的x11=20，x13=5，x14=25，x21=20，x32=20，x33=10，其它xij=0，显然是该运输问题的一个可行解，同时，调运表中不包含以这些非零变量为顶点的闭回路。因此，该可行解就是该运输问题的一个基可行解。更一般地，可以证明，由最小元素法给出的可行解就是运输问题的一个基可行解。（二）最优解的判定最优解的判定，通常有两种方法，即闭回路法和位势法。1闭回路法在表36所描述的调运表中，任一非基可变量都可以作出这样的闭回路：该闭回路以选定的非基变量为第一个顶点，其余的顶点都是基变量。可以证明，对于任一非基变量，这样的闭回路只有唯一一条。在这样的闭回路上，可以对调运方案进行调整，而能使调运方案仍然满足所有约束条件，即满足产销平衡的要求。例如，对表36中非基变量x12作闭回路，如表37。 表37销 地产地B1B2B3B4产量A120525503764A220 202433A32010308389销量40201525在表中所示的闭回路上，为满足产销平衡条件，若要使x12增加1个单位运量，x13就必须减少1个运量，同理x33必须增加1个运量，x32必须减少1个运量。再来观察这样调整后，目标函数的变化。x12增加1个单位运量，则运费增加7个单位，x13减少1个单位运量，则运费减少6个单位，x33增加1个单位运量，则运费增加8个单位，x32减少1个单位运量，则运费减少3个单位。这样，调整后目标函数总的变化量为：76 + 83=6，即目标函数增加6个单位。因此，以上的调整是不合算的，即上x12为非基变量的选择是正确的。这种在闭回路上进行的1个单位运量的调整所得到的目标函数值的变化量，实际上是相应非基变量的检验数。如上述x12的检验数12=6。，由于运输问题为极小化，所以若所有的非基变量的检验数大等于零，则表中的基可行解就是最优解，否则，就要进行基可行解的转换。对表36中，所有非基变量的检验数计算如下： 表38非基变量闭回路检验数x12x22x23x24x31x34x12x13x33x32x12x22x21x11x13x33x32x22x23x21x11x13x23x24x21x11x14x24x31x11x13x33x31x34x33x13x14x34642033x23的检验数23=2<0，故表36中的基可行解不是最优解。2位势法当运输问题变量个数较多时，闭回路法计算比较烦琐，此时位势法更为简便。对于运输问题min f=CXAX=bX0设B为其一可行基，则相应的基可行解的各变量的检验数可用下式计算，即ij = cijCBB-1pij又运输问题的对问题为max z=YbYACY无限制其中，Y=（u1，um，v1，vn）为对偶变量，其中的各分量分别对应m+n个条件。根据对偶理论有 Y= CBB-1因此有 ij = cijYpij又因为，pij中除第i个元素和第m+j个元素为1以外，其余元素均为0，即pij=ei+em+j所以有ij = cijYpij= cij（u1，um，v1，vn）pij  =cij（ui+vj）而所有基变量的检验数等于零，因此有cij（ui+vj）= 0 即 ui+vj = cij （i，j）I（基变量下标集）由于ui对应与调运表中的第i行，称其为第i行的行位势；vj对应与调运表中的第j列，称其为第j列的列位势；位势法的具体办法如下：（1）在调运表中，对于每一个基变量都按公式ui+vj = cij列出一个位势方程，形成位势方程组；（2）任决定其中一个位势的数值，然后求出其它位势的数值；（3）按公式ij =cij（ui+vj）计算非基变量的检验数，若所有非基变量的检验数均大等于零，则调运表中的基可行解就是最优解，否则不是最优解；下面用位势法对表36中的基可行解进行最优性检验。 表39销 地产地B1B2B3B4产量行位势A12052550u13764A22020u22433A3201030u38389销量40201525列位势v1v2v3v4位势方程组为u1+v1=3u1+v3=6u1+v4=4u2+v1=2u3+v2=3u3+v3=8取u1=0，解上述方程组得 u1=0 u2=1 u3=2v1=3v2=1v3=6v4=4各非基变量的检验数为12 =c12（u1+v2）=7（0+1）= 4>022 =c22（u2+v2）=4（1+1）= 2>023 =c23（u2+v3）=3（1+6）= 2<024 =c24（u2+v4）=3（1+4）= 031 =c31（u3+v1）=8（2+3）= 3>034 =c34（u3+v4）=9（2+4）= 3>0由于23 =2<0，故表中基可行解不是最优解。（三）基可行解的转换当调运表中，仍然有非基变量的检验数为负，则说明问题还没有得到最优解，需要进行基可行解的转换。具体办法为：（1）以某一个ij <0（若有多个则取最小者）对应的变量xij作为进基变量；（2）以所选的xij为第一个顶点作闭回路，该闭回路除xij外，其余顶点都是基变量，并排序；（3）以顺序为偶数的顶点的基变量最小值min（xij）k|k为偶数作为调整量，在顺序为奇数的顶点上加上该调整量，在顺序为偶数的顶点上减去该调整量，即可得到新的基可行解。这里对表36中的基可行解进行转换。由于23 =2<0，故以x23为进基变量，并以x23为第一个顶点作闭回路，如表310。 表310销 地产地B1B2B3B4产量A120525503764A220x23202433A32010308389销量40201525该闭回路上，偶数顶点上的基变量最小值为5，以该调整量进行调整得到如表311的新的基可行解。 表311销 地产地B1B2B3B4产量A12525503764A2155202433A32010308389销量40201525新基可行解的位势方程组为u1+v1=3u1+v4=4u2+v1=2u2+v3=3u3+v2=3u3+v3=8取u1=0，解上述方程组得 u1=0 u2=1 u3=4v1=3v2=1v3=4v4=4各非基变量的检验数为12 =7（01）= 8>013 =6（0+4）= 2>022 =4（11）= 6>024 =3（1+4）= 031 =8（4+3）= 1>034 =9（4+4）= 1>0由于所有非基变量的检验数均大等于零，故从表311中得到最优解为x11=25，x14=25，x21=15，x23=5，x32=20，x33=10，其它xij=0最优目标值为f*=3×25+4×25+2×15+3×5+3×20+8×10=360此外，由于24 = 0，故此问题有另一最优基可行解。具体求法是在表311中，以x24为进基变量作闭回路，进行调整后得到。由上面分析可知，表上作业法的实质是单纯形方法用于求解运输问题这样一类特殊形式线性规划问题的简化，因而也称它为运输单纯形法。最后总结表上作业法的解题步骤。（1）编制调运表（包括产销平衡表及单位运价表）；（2）正在调运表上求出初始基可行解；（3）用位势法或闭回路法计算非基变量的检验数。若所有非基变量的检验数0，则已得到问题的最优解，停止计算。否则转下一步；（4）选取小于0的检验数中的最小者对应的变量作为进基变量，用闭回路法进行基可行解的转换，得到新的基可行解，转（3）。第三节 产销不平衡的运输问题及其求解对于产销平衡的问题可用表上作业法求解，但对于产销不平衡的问题则需要进行处理，将其化成平衡问题，才能用表上作业法求解。一、产大于销产大于销的运输问题的特征是ai >bj，其数学模型为：解此类问题可假想一个销地Bn+1，其需要量为：bn+1=ai bj；若用xi，n+1表示从Ai到Bn+1的运量， 可令ci，n+1=0或等于第Ai产地储存单位物资的费用。 因为xi，n+1实际上表示Ai产地没有运出去而库存的物资数量。经处理后，问题变成了产销平衡的运输问题，其数学模型为：这样，m个产地、n个销地的不平衡运输问题，转化成了m个产地、n+1个销地的平衡运输问题，此时可用表上作业法求解。在用最小元素法求解该类问题初始基可行解时，若某列的运价全为零时，则该列最后考虑。二、销大于产销大于产的运输问题的特征是ai < bj，其数学模型为：解此问题可假想一个产地Am+1，其产量为：am+1 = bjai； 若用xm+1，j表示从Am+1到Bj的运量，可令cm+1，j=0或等于第Bj产地每缺单位物资的损失。因为xm+1，j实际上表示Bj销地所缺的物资数量。经处理后，问题变成了产销平衡的运输问题，其数学模型为：此时，可用表上作业法求解。在用最小元素法求解该问题初始基可行解时，若某行的运价全为零时，则该行最后考虑。第四节 运输问题的应用一、一般的产销不平衡运输问题例3.3 表312给出了三个产地及四个销地的某物资供应量与需求量及从各产到各销地的单位物资运价（元/单位物资），试求出运费最小的运输方案。 表312销 地产地B1B2B3B4供应量(t)A13245200A27521100A39635150需求量(t)5010015050450350解 由表可知，总供应量为450(t)，总需求量为350(t)，即问题为产大于销的运输问题。因此，需要假想一个销地B5，其需求量为450350=100(t)。问题并未给出物资的存储费用，因此，从各产地到B5的单位运价视为零，即ci5=0（i=1，2，3）。这样得到新的产销平衡表如表313。 表313销 地产地B1B2B3B4B5供应量(t)A132450200A275210100A396350150需求量(t)5010015050100450450用表上作业法解得该问题的最优运输方案为：x11=50，x12=100，x15=50，x23=50，x24=50，x33=100，x35=50。其中x15=50，x35=50表示A1，A3各有50个单位的物资库存。总运费为800元。 某运输问题有三个产地和三个销地，产地的总供应量小于销地的最高需求量之和，但超过了销地的最小需求量之和。现在，各销地的最低需求必须满足，最低需求到最高需求的之间的需求若不能满足，会造成经济损失，其中B1销量必须满足，B2、B3不能满足的单位损失分别为3元和2元。单位运价、供应量与需求量见表314。求出最优调运方案。 表314销 地产地B1B2B3供应量A1517200A2646800A3325150最低需求最高需求6006001202003004301150解 B2的最高需求与最低需求不相等，而B1的最低需求必须满足，因此可将B2看成两个销地B21和B22，其中B21的需求量为B2的最低需求量，该需求量必须全部满足；B22的需求量为B2的最高需求量减去最低需求量，即为200120=80，该需求量可以不被满足。对销地B3也可作同样的处理。这样问题就变为一个三个产地、五个销地的运输问题，其中总产量为1150，总供应量为1230，因此是一个销大于产的问题。为解此问题，又要假设一个产地A4，其产量为12301150 = 80。为了使各销地的最低销量得到满足，可令A4运往B1、B21、B31的运价为M，即给出一个很高的运价。这样就可以得到如下产销平衡表，见表315。 表315 产销平衡表销 地产地B1B21B22B31B32供应量(t)A151177200A264466800A332255150A4MM3M280需求量6001208030013012301230用表上作业法求解，可以得到如表316所示的调运方案。 表316 最优调运表销 地产地B1B21B22B31B32供应量(t)A112080200A245030050800A3150150A48080需求量6001208030013012301230从最优调运表中可以看出，B1和B2的需求量得到全部满足，而B3的需求量满足了350。总费用（包括缺货损失费160元）为8100元。二、生产与存储问题 某高科技企业生产某种光电通讯产品，现要安排今后4个季度的生产计划。已知今后四个季度的合同签定数，企业各季度生产能力以及各季度的生产成本如表315所示。考虑资金的机会成本，预计每件产品每存储一个季度的费用为0.1千元。在完成合同的条件下，试安排这四个季度的生产计划，使生产成本与存储费用之和最小。表317季 度合同签定数（台）生产能力（台）生产成本（千元）1234230265255245270260280270解 设xij表示第i季度生产第j季度交货的该种产品的数量，考虑生产成本与存储费用后，xij所对应的目标函数中的价格系数cij如表318所示。 表318 xij所对应的价格系数cij ji123413.2234这样问题的数学模型可以描述为：min f x11x12x13x14x22x23x24x33x34x44x11+x12+x13+x14270  x22+x23+x24260 x33+x34280x44270x11 =230x12+x22 =265x13+x23+x33 =255x14+x24+x34+x44 =245xij0，i=1，4；j=1，4；ij模型中，前4个条件为生产能力约束，后四各条件为合同限制约束。观察该模型，若将x21、x31、x32、x41、x42、x43等变量补齐，则模型变为一个标准的运输问题数学模型。为了保证模型的性质不变，必须使这些补齐的变量为0。为此，可在目标函数中令这些变量的系数为M，这样就得到一个产销不平衡的运输问题。此时，可假设一个销地，变成产销平衡问题。产销表及运价表如表319所示。表319 销地产地12345产量102702M02803MM02604MMM0270销量23026525524585 10801080用表上作业法，可求得四个季度的生产计划如表320所示。 表320 销地产地12345产量12304027022255528032555260424030270销量23026525524585 10801080从最优调运表中可以看出，第1季度生产270台，其中40台用于满足第季度需要，第2季度生产225台，第3季度生产260台，其中5台用于满足第4季度的需要，第4季度则生产240台。总费用为3299.15千元。三、转运问题例3.6 某公司生产某种高科技产品。该公司在大连和广州设有两个分厂生产这种，在上海和天津设有两个销售公司负责对南京、济南、南昌和青岛四个城市进行产品供应。因大连与青岛相距较近，公司同意也可以向青岛直接供货。各厂产量、各地需要量、线路网络及相应各城市间的每单位产品的运费均标在图41中，单位为百元。现在的问题是：如何调运这种产品使公司总的运费最小？解 如图所示，给各城市编号，即i=1，2，8分别代表广州、大连、上海、天津、南京、济南、南昌和青岛。设xij表示从i到j的调运量（台），则问题的目标函数为min f = 2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x481广 州2大 连4天津3上 海8青 岛7南昌6济 南5南京400600150200300350供应量需求量4366322465314图 31 公司运输网络 对于发点1、2有供应量约束x13+x14600x23+x24+x28400对于中转点3、4有平衡约束x13+x23 - x35 - x36 - x37 - x38 = 0x14+x24 - x45 - x46 - x47 - x48 = 0 对于需求点5、6、7、8有需求量约束x35+x45 = 200x36+x46 = 150x37+x47 = 350x38+x48 +x28 = 300由此可得该问题的线性规划模型min f = 2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48x13+x14600x23+x24+x28400x13+x23 - x35 - x36 - x37 - x38 = 0x14+x24 - x45 - x46 - x47 - x48 = 0x35+x45 = 200x36+x46 = 150x37+x47 = 350x38+x48 +x28 = 300 xij0，对于所有i、j对于上述模型，用单纯形法可以得到最优解，但如果将其转化成运输问题模型，用表上作业法求解不仅简单而且直观。具体做法是：每个中转站对于发点来说可以看作是销地，其销量为所有可以运到该地的产量之和；每个中转站对于销地来说可以看作是产地，其产量等于其销量。这样，该问题就变成了4个产地、6个销地的运输问题。产地到销地的单位运价的处理办法是：中转站自己到自己的运价为0，网络图中，不能直接运输的产地到销地之间的运价为M，其余运价直接用网络图中标明的数字。问题的产销平衡表如下表所示。 表321 销地产地3(上海)4(天津)5(南京)6(济南)7(南昌)8(青岛)供应量1（广州）23MMMM6002（大连）31MMM44003（上海）0M263610004（天津）M044651000需求量10001000200150350300 30003000用表上作业法，可求得该问题的最优调运方案如表322所示。 表322 销地产地3(上海)4(天津)5(南京)6(济南)7(南昌)8(青岛)供应量1（广州）550506002（大连）1003004003（上海）45020035010004（天津）8501501000需求量10001000200150350300 30003000即，广州向中转站上海运550台，天津运50台；大连向中转站天津运100台，直接向青岛运300台；中转站上海向南京和南昌分别运200台和350台；中转站天津向济南运150台。最小运费为4600元习 题 三1判断表323、表324中给出的调运方案能否作为表上作业法求解的初始基可行解？为什么？表323销 地产地B1B2B3B4供应量A150150200A201000100A35050需求量5010015050 表324销 地产地B1B2B3B4供应量A160140200A2100100A310105070需求量70100150502用表上作业法求解下面运输问题表325 销地单价产地B1B2B3B4供应量A13986600A212207101000A36111314700需求量3005009006003产地A1、A2及销地B1、B2、B3的有关数据如下表。销地B1、B2、B3允许缺货，产地A1、A2允许存储。问怎样调配，使总费用最少？建立其数学模型，并用表上作业法求解。表326 销地 单价产地B1B2B3供应量单位存储费A14682005A26242004需求量50100100单位缺货费3854某百货公司去外地采购A、B、C、D四种规格的服装，数量分别为A1500套；B2000套，C3000套，D3500套。有三个城市可供应上述规格服装，供应数量为城市I2500套，II2500套，III5000套。由于这些城市的服务质量、运价等销售情况不一，预计售出后的利润（元/套）也不同，详见表3-52。表327ABCDI10567II8276III9348请帮助该公司确定一个预期盈利最大的采购方案。5甲、乙、丙三个城市每年分别需煤炭320、250、350万吨，由A、B两处煤矿负责供应。已知煤炭年供应量为A400万吨，B450万吨。由煤矿至各城市的单位运价（万元/万吨）见表328。表328甲乙丙A151822B122516由于需大于供，经研究平衡决定，甲城市供应量不少于280万吨，乙城市需要量应全部满足，丙城市供应量不少于270万吨。此外甲城市每缺1万吨煤损失10万元，丙城市每缺1万吨煤损失12万元。试求将供应量分配完又使总费用（包括缺货费）为最低的调运方案。6某厂要完成合同规定的三个时期的某产品订货任务，现已知各时期工厂的生产能力、合同任务、生产单位产品的成本等数据如表329所示。又已知单位产品每时期存储费为1，现要求：建立该问题的LP数学模型；将其化为运输问题，并用表上作业法求解该问题。 表329时期生产能力定货量生产成本13020822015123252011