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

作业：P991003.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的运输量。则有,运输问题的系数矩阵,下面先讨论产销平衡的运输问题的解法，对产销不平衡的运输问题，只需化为产销平衡问题，即可求解。,产销平衡运输问题数学模型的特征：1.产地：m个；2.销地：n个；3.变量：mn个；4.约束条件：m+n个；5.约束矩阵具有：分布稀疏性，排列规律性，数据单一性（0或1）；6.约束矩阵的秩：r=m+n1;7.基变量个数：m+n1；8.非基变量个数：mn(m+n1)。,定理1.运输问题的数学模型必有最优解。定理2.若运输问题中产量和销量皆为整数，则必有整数最优解。,第二节求解运输问题的表上作业法,表上作业法的步骤：1.将运输问题化为产销平衡的问题（供过于求：增加假设销地；供不应求，增加假设产地）；2.确定初始调运方案（最小元素法，西北角法，vogel法）；3.最优性检验（闭回路法，位势法）；若所有非基变量的检验数都有ij0，则得最优方案，结束计算。否则，转4；4.调整方案（闭回路法），转3。,例1.已知运输问题见表,2-1初始方案的确定1.最小元素法（就近供应的思想）在单位运价表中的最小运价处确定供销关系，划去满足的行或列，以此类推，直至给出一个完整的调运方案。,初始调运方案见下，总运费为z=86,特殊情况：若运价表为:,在未被划掉的运价对应的空格处补0，然后划掉该行和该列。,2.西北角法在单位运价表中的左上角（西北角）处确定供销关系，划去满足的行或列，以此类推，直至给出一个完整的调运方案。对例1，已知单位运价表为,初始调运方案见下，总运费为z=111,3.vogel法从运价表上分别找出每行与每列的最小的两个元素之差，再从差值最大的行或列中找出最小运价确定供需关系和供需数量，划去运价表中对应的行或列，然后重复上述步骤。,初始调运方案为见下，总运费为z=85,2-2最优性检验1.进行最优性检验的闭回路法闭回路：在调运方案中，从一个空格处出发，以有数字格为顶点（或拐点），沿水平或垂直连线又回到空格处所形成的封闭回路。,定理3.对调运方案中的任一个空格，有且仅有一个以有数字格为顶点的闭回路。,推论：运输问题中n+m-1个变量能构成基变量的充要条件是他们不构成闭回路。,通过闭回路计算空格处的检验数ij，若ij0（因为是求minz)，则得最优调运方案，否则，转2-3。,这里定义：闭回路上空格顶点的编号为0，其余按1，2，3.类推。闭回路的可能形状：,11=c11-c13+c23-c21=3-3+2-1=131=7-1+2-3+10-5=10.,2-3调整方案，然后转2-2令调整量=闭回路上奇数顶点的最小运量。调整方法：闭回路上偶数顶点运量+闭回路上奇数顶点运量-,因所有检验数ij0，故得最优方案。Minz=85,作业P993.1表3-36（位势法）P1013.43.52.进行最优性检验的位势法运输问题的对偶问题数学模型为,对约束条件加松弛变量，得,已知运输问题的基变量有m+n-1个，因此，上式是一个具有m+n个变量，m+n-1个等式的方程组，由于变量数多于方程数，故有无穷多解。,对以上问题，可先选定任意一个变量的取值，然后就可计算出其它变量的值。(变量ui也称为行位势，vj称为列位势。)有了ui和vj，就可计算非基变量的检验数ij=cij(ui+vj)。对例1，可先令v1=1，根据cij就可求出其它的ui，vj，从而可计算出检验数。,例：求解下列运输问题,解:初始方案,检验表,一次调整后方案,检验表,因所有检验数都大于等于零,故得最优方案。minz=4025。,2-4表上作业法总结1.总结2.求最大值问题,例：求解下列运输问题,第三节产销不平衡的运输问题及应用,此时，可增加一个销量为供求差额的假设销地，从而化为产销平衡问题。可用表表示如下。,1.当供过于求时，运输问题的数学模型可写成下式，加松弛变量化为标准形式,2.当供不应求时，运输问题的数学模型可写成下式，加松弛变量化为标准形式,此时，可增加一个产量为供求差额的假设产地，从而化为产销平衡问题。可用表表示如下。,作业P1033.73.8(a)例2.已知见表：试决定总运费最少的调运方案。,解：这是一个产大于销的运输问题，先将其化为产销平衡问题，然后求解。,最优方案见下表，最小运费为minz=35,例3.已知见表，试决定使总运费最省的化肥调运方案。,解：这是一个产销不平