山东大学 运筹学课件及课后解答3第三章 运输问题(新)a

作业：P99~1003.1表3-353.23.3第三章运输问题第一节运输问题的数学模型有某种物资需要调运，已知有m个产地（产地用Ai表示，i=1，2，…，m)供应该种物资，产地Ai的产量为ai；有n个销地（销地用Bj表示，j=1，2，…，n)需要该种物资，销地Bj的销量为bj，从第i个产地到第j个销地的单位物资运价为cij，要求：制定一个调运方案，在满足供需关系的条件下，使总运费最少。（上述资料见下面的产销平衡表和单位运价表，也可将两表合并起来，见后）解：设为xij表示从产地为Ai给销地为Bj的运输量。则有),...,2,1;,...,2,1(0),...,2,1(),...,2,1(min1111njmixnjbxmiaxxczijmijijnjiijminjijij运输问题的系数矩阵nnmmmnmnmmmmnnnnvbvbvbuauauaybxcxcxcxcxcxcxcxcxc111..............1111111...11.....1...111...11........................22112211221122222221211112121111问题。时，为供不应求的运输当问题；时，为供过于求的运输当问题；时，为产销平衡的运输当njjmiiminjjiminjjibababa111111)...21...21(,),...,2,1;,...,2,1(max11njmivunjmicvuvbuawjiijjijnjjimii，，，；，，，无约束下面先讨论产销平衡的运输问题的解法，对产销不平衡的运输问题，只需化为产销平衡问题，即可求解。产销平衡运输问题数学模型的特征：1.产地：m个；2.销地：n个；3.变量：m×n个；4.约束条件：m+n个；5.约束矩阵具有：分布稀疏性，排列规律性，数据单一性（0或1）；6.约束矩阵的秩：r=m+n–1;7.基变量个数：m+n–1；8.非基变量个数：m×n–(m+n–1)。定理1.运输问题的数学模型必有最优解。定理2.若运输问题中产量和销量皆为整数，则必有整数最优解。关。所以，约束条件线性相求和得两边对对求和得两边对对njjnjmiijjmiijmiiminjijnjiijbxjbxaxiax1111111第二节求解运输问题的表上作业法表上作业法的步骤：1.将运输问题化为产销平衡的问题（供过于求：增加假设销地；供不应求，增加假设产地）；2.确定初始调运方案（最小元素法，西北角法，vogel法）；3.最优性检验（闭回路法，位势法）；若所有非基变量的检验数都有σij≥0，则得最优方案，结束计算。否则，转4；4.调整方案（闭回路法），转3。例1.已知运输问题见表销地产地B1B2B3B4产量A1A2A3311310192874105749销量3656202-1初始方案的确定1.最小元素法（就近供应的思想）在单位运价表中的最小运价处确定供销关系，划去满足的行或列，以此类推，直至给出一个完整的调运方案。初始调运方案见下，总运费为z=86销地产地B1B2B3B4产量A1A2A3433163749销量365620特殊情况：若运价表为:销地产地B1B2B3B4产量A1A2A331131791812105749销量365620销地产地B1B2B3B4产量A1A2A3016433749销量365620在未被划掉的运价对应的空格处补0，然后划掉该行和该列。2.西北角法在单位运价表中的左上角（西北角）处确定供销关系，划去满足的行或列，以此类推，直至给出一个完整的调运方案。对例1，已知单位运价表为销地产地B1B2B3B4产量A1A2A3311310192874105749销量365620初始调运方案见下，总运费为z=111销地产地B1B2B3B4产量A1A2A3342236749销量3656203.vogel法从运价表上分别找出每行与每列的最小的两个元素之差，再从差值最大的行或列中找出最小运价确定供需关系和供需数量，划去运价表中对应的行或列，然后重复上述步骤。销地产地B1B2B3B4产量A1A2A3523163749销量365620初始调运方案为见下，总运费为z=852-2最优性检验1.进行最优性检验的闭回路法闭回路：在调运方案中，从一个空格处出发，以有数字格为顶点（或拐点），沿水平或垂直连线又回到空格处所形成的封闭回路。定理3.对调运方案中的任一个空格，有且仅有一个以有数字格为顶点的闭回路。推论：运输问题中n+m-1个变量能构成基变量的充要条件是他们不构成闭回路。通过闭回路计算空格处的检验数σij，若σij≥0（因为是求minz)，则得最优调运方案，否则，转2-3。这里定义：闭回路上空格顶点的编号为0，其余按1，2，3...类推。闭回路的可能形状：σ11=c11-c13+c23-c21=3-3+2-1=1σ31=7-1+2-3+10-5=10......2-3调整方案，然后转2-2令调整量θ=闭回路上奇数顶点的最小运量。调整方法：闭回路上偶数顶点运量+θ闭回路上奇数顶点运量-θ因所有检验数σij≥0，故得最优方案。Minz=85作业P993.1表3-36（位势法）P1013.43.52.进行最优性检验的位势法运输问题的对偶问题数学模型为)...21...21(,),...,2,1;,...,2,1(max11njmivunjmicvuvbuawjiijjijnjjimii，，，；，，，无约束对约束条件加松弛变量，得已知运输问题的基变量有m+n-1个，因此，上式是一个具有m+n个变量，m+n-1个等式的方程组，由于变量数多于方程数，故有无穷多解。ijjiijijjiijsijijsijjicvuvucycyvu因此，对基变量有：由于基变量的检验数或写成,0)(对以上问题，可先选定任意一个变量的取值，然后就可计算出其它变量的值。(变量ui也称为行位势，vj称为列位势。)有了ui和vj，就可计算非基变量的检验数σij=cij–(ui+vj)。对例1，可先令v1=1，根据cij就可求出其它的ui，vj，从而可计算出检验数。销地产地B1B2B3B4产量A1A2A3311310192874105749销量365620例：求解下列运输问题销地产地B1B2B3B4B5产量A1A2A3101520204020401530303035405525506090销量2535601070200销地产地B1B2B3B4B5产量A1A2A32525600101070506090销量2535601070200解:初始方案销地产地B1B2B3B4B5uiA1A2A31015(0)(-15)(35)(15)(30)1530(30)(0)35(0)55250-520vj101520355检验表销地产地B1B2B3B4B5产量A1A2A32525600101070506090销量2535601070200一次调整后方案销地产地B1B2B3B4B5产量A1A2A32515106002070506090销量2535601070200检验表销地产地B1B2B3B4B5uiA1A2A31015(15)20(35)(0)(15)1530(15)(0)35(15)(15)2501020vj10155205因所有检验数都大于等于零,故得最优方案。minz=4025。2-4表上作业法总结1.总结2.求最大值问题例：求解下列运输问题销地产地B1B2B3B4产量A1A2A3376424324385523销量323210第三节产销不平衡的运输问题及应用),...,2,1;,...,2,1(0),...,2,1(),...,2,1(min1111njmixnjbxmiaxxczijmijijnjiijminjijij)1,...,2,1;,...,2,1(0)1,...,2,1(),...,2,1(0min111,11,11njmixnjbxmiaxxxxczijmijijnjiniijminiminjijij此时，可增加一个销量为供求差额的假设销地，从而化为产销平衡问题。可用表表示如下。1.当供过于求时，运输问题的数学模型可写成下式，加松弛变量化为标准形式销地产地B1B2…BnBn+1产量A1A2...Amc11c12…c1nc1,n+1c21c22…c2nc2,n+1..…....…....…..cm1cm2…cmncm,n+1a1a2...am销量b1b2…bnbn+1。，即化为产销平衡问题运费为），，销量为视为假设销地将剩余产量就地储存（为剩余产量。两式相减得求和得两边对对求和得两边对对011,111111,11111111,11,mininnminjjimininjjnjmiijjmiijmiiminjminiijnjiniijxbBbaxbxjbxaxxiaxx2.当供不应求时，运输问题的数学模型可写成下式，加松弛变量化为标准形式),...,2,1;,...,2,1(0),...,2,1(),...,2,1(min1111njmixnjbxmiaxxczijmijijnjiijminjijij),...,2,1;1,...,2,1(0),...,2,1()1,...,2,1(0min1,1111,11njmixnjbxxmiaxxxczijmijjmijnjiijminiminjijij此时，可增加一个产量为供求差额的假设产地，从而化为产销平衡问题。可用表表示如下。销地产地B1B2…Bn产量A1A2...AmAm+1c11c12…c1nc21c22…c2n..…...…...….cm1cm2…cmncm+1,1cm+1,2…cm+1,na1a2...amam+1销量b1b2…bn作业P1033.73.8(a)例2.已知见表：试决定总运费最少的调运方案。销地产地B1B2B3B4产量A1A2A321134103597812757销量23461915解：这是一个产大于销的运输问题，先将其化为产销平衡问题，然后求解。最优方案见下表，最小运费为minz=35销地产地B1B2B3B4库存产量A1A2A32323243757销量2346419销地产地B1B2B3B4库存产量A1A2A321134010359078120757销量2346419例3.已知见表，试决定使总运费最省的化肥调运方案。解：这是一个产销不平衡的运输问题，将其处理后可得如下的产销平衡表和单价表。最优调运方案见下表，最小运费为minz=2460需求地区化肥厂Ⅰ’Ⅰ’’ⅡⅢⅣ’Ⅳ’’产量ABCD16161322171714141319151519192023MMM0M0M050605050销量302070301050210需求地区化肥厂Ⅰ’Ⅰ’’ⅡⅢⅣ’Ⅳ’’产量ABCD5020103030200302050605050销量302070301050210例4.转运问题表上作业法与单纯形法1.确定初始基本可行解2.最优性检验3.确定换入变量4.确定换出变量