第二讲运输问题---TransportationProblem(第七章P179-219)2005年9月龙子泉一、运输问题(TransportationProblem)以知有m个生产地点(source)Ai，i=1，…，m，可供应某种物资，其供应量（产量）(supply)为ai，i=1，…，m；有n个销售地点(destination)Bj，j=1，…，n，需要该种物资，其需要量（产量）(demand)为bj，j=1，…，n；从Ai到Bj运输单位物资的运价（单价）为cij；设Σai=Σbj，这些数据可汇总于如下产销平衡表，现要制定一个使总运费最小的调运方案。第一节运输问题及其数学模型销地产地B1B2…Bn产量A1c11c12…c1na1A2c21c22…c2na2………………Amcm1cm2…cmnam销量b1b2…bnΣaiΣbj产销平衡表(costandrequirementtable)若用xij表示从Ai到Bj的运量，在产销平衡的条件下，要求得总运费最小的调运方案，其数学模型如下（模型Y）mnijiji=1j=1nijij=1mijji=1ijminf=cxx=ai=1,...,mx=bj=1,...,nx>=0,i=1,...,m;j=1,...,n该模型中，包含了m×n个变量，（m+n）个约束条件，且有特殊结构的系数矩阵，即mnmmnnxxxxxxxxx21222211121111...111...1m11...1111111n111行行上述矩阵的列向量可用pij来描述，显然pij中除第i个元素和第m+j个元素为1以外，其余元素均为02005年9月龙子泉一、运输问题数学模型的基本概念–对于运输问题的数学模型（模型Y）有如下定理。–定理3.1运输问题的数学模型必有最优解。–定理3.2运输问题约束方程系数矩阵A的秩为m+n－1，即R（A）=m+n－1。第二节表上作业法----(TransportationSimplexMethod)定义3.1（闭回路的定义）在运输问题的调运表中，凡能排成xi1j1，xi1j2，xi2j3，…，xisjs，xisj1形式的变量集合，称为一个闭回路(closedpath,stepping-stone-path)，其中诸变量称为该闭回路的顶点(corner)。闭回路有如下特点：①每个顶点都是转角；②每行或每列只有且仅有两个顶点；③每个顶点的连线都是水平的或垂直的。B1B2B3B4B5B6B7A1x11x12x13x14x15x16x17A2x21x22x23x24x25x26x27A3x31x32x33x34x35x36x37–定理3.3运输问题m+n－1个变量xi1j1，xi2j2，…，xisjs（s=m+n－1）构成某一基可行解的基变量的充要条件是：不包含以这些变量为顶点的闭回路。–该定理能帮助我们简便地求出基可行解或判别某一可行解是否为基可行解。2005年9月龙子泉–表上作业法基本步骤（1）确定初始基可行解（2）最优解...
