第三章 运输问题(1-3)

《管理运筹学》牧云志[e-mail]erationsResearch第三章运输问题2第三章运输问题第三章运输问题3第三章运输问题运输问题在工商管理中有着广泛的应用，是一类重要的和特殊的线性规划问题。由于这类线性规划问题在结构上有特殊性，所以有专门的解法——表上作业法等，用以简便求解这类问题。本章讨论：•§1运输问题及其数学模型•§2运输问题的表上作业法•§3运输问题应用举例•第三章习题第三章运输问题4本章学习要求•本章要求：•1．理解运输问题的典例和数学模型。•2．掌握表上作业法。•3．掌握产销不平衡的运输问题及其应用。•重点和难点：运输模型；表上作业法。第三章运输问题5§1运输问题及其数学模型•运输问题是线性规划问题的特例。•产地：货物发出的地点。•销地：货物接收的地点。•产量：各产地的可供货量。•销量：各销地的需求数量。•运输问题就是研究如何组织调运，既满足各销地的需求，又使总运费最小。第三章运输问题6门市部加工厂B1B2B3B4产量A162355A278542A339273需求量2134总产量=总需求量（产销平衡）例3.1某食品公司经销的主要产品之一是糖果，有三个加工厂A1、A2、A3，每天要把生产的糖果运往B1、B2、B3、B4四个门市部销售，已知各厂的产量（吨/天）、各门市部的销售量（吨/天）及运价（元/吨），见下表，求运费最小的调运方案。一、运输问题的数学模型第三章运输问题7(1)决策变量设从Ai到Bj的运输量为xij，(2)目标函数minz=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34(3)约束条件产量之和等于销量之和,故要满足：供应平衡条件x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34=3销售平衡条件x11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=1非负性约束xij≥0(i=1,2,3；j=1,2,3,4)建立运输问题的LP模型：第三章运输问题8111213142122232431323334111213142122232431323334112131122232132333142434min6235785439275232..1340(1,2,3;1,ijzxxxxxxxxxxxxxxxxxxxxxxxxxxxstxxxxxxxxxxij4)第三章运输问题91112131421222324313233341112131421222324min6235785439275..zxxxxxxxxxxxxxxxxxxxxst3132333411213112232xxxxxxxx2232132333142413xxxxxxx3440(1,2,,3;1,2,3,4)ijxxij第三章运输问题10上述例子中决策变量mn=34=12个约束方程m+n=3+4=7个系数矩阵结构如下：111213142122232431323334111111111111111111111111xxxxxxxxxxxxA3行4行第三章运输问题11一般运输问题的线性规划模型假设A1，A2，…，Am表示某物资的m个产地；B1，B2，…，Bn表示某物资的n个销地；ai表示产地Ai的产量（i=1,2,…,m）；bj表示销地Bj的销量（j=1,2,…,n）；cij表示把物资从产地Ai运往销地Bj的单位运价。xij表示把物资从产地Ai运往销地Bj的运输量。如果a1+a2+…+am=b1+b2+…+bn则称该运输问题是产销平衡的；否则，称它是产销不平衡的。下面我们首先讨论产销平衡的运输问题。第三章运输问题12销地产地B1B2…Bn产量A1x11c11x12c12…x1nc1na1A2x21c21x22c22…x2nc2na2┇┇┇┇┇┇Amxm1cm1xm2cm2…xmncmnam销量b1b2…bn表式运输模型第三章运输问题13对于产销平衡问题可得到下列运输问题的模型：1111min1,2,,..1,2,,01,2,,;1,2,,mnijijijnijijmijjiijzcxxaimstxbjnximjn11mnijijab第三章运输问题1411112122nnxxaxxa111211112222212mmnmmmnnxxaxxxbxxxbxxmnnxb第三章运输问题15决策变量mn约束方程m+n系数矩阵的结构如下：111111111111111111Ax11x12…x1nx21x22…x2n…………xm1xm2…xmnm行n行第三章运输问题16一般模型的系数矩阵特征1、共有m+n行，分别表示各产地和销地；m×n列，分别表示各变量；2、每列只有两个1，其余为0，分别表示只有一个产地和一个销地被使用（即每一个变量在前m个约束方程中出现一次，在后n个方程中出现一次）；第三章运输问题17二、运输问题数学模型的特点1、产销平衡的运输问题必有可行解，也必有最优解；11,mnijijijijijabqabxxq设就是运输问题的可行解0,,对极小化问题,目标函数有下界不会趋于则必有最优解根据推论1.22、产销平衡运输问题的系数矩阵A的秩等于m+n-1；m+n个约束方程去掉任何一个，剩下的m+n-1个方程都是独立的；运输问题的基可行解有m+n-1个基变量。3、如果产量ai（i=1,2,…,m）和销量bj（j=1,2,…,n）都是整数，那么任何一个基可行解是整数解。第三章运输问题18•产销平衡minjjiba111111min,1,2,...,..,1,2,...,0,1,2,...,,1,2,...,mnijijijnijijmijjiijzcxxaimstxbjnximjn运输问题的三种类型第三章运输问题19•产大于销minjjiba111111min,1,2,...,..,1,2,...,0,1,2,...,,1,2,...,mnijijijnijijmijjiijzcxxaimstxbjnximjn第三章运输问题20•产小于销minjjiba111111min,1,2,...,..,1,2,...,0,1,2,...,,1,2,...,mnijijijnijijmijjiijzcxxaimstxbjnximjn第三章运输问题21§2运输问题的表上作业法•表上作业法适合于产销平衡的运输问题•产销不平衡问题要转化为产销平衡问题•求解步骤：（1）求一个初始调运方案（初始基可行解）：在mn维产销平衡表上给出m+n-1个数字。用西北角法、最小元素法、Vogel法（2）判断当前方案是否为最优（最优性检验）：计算各非基变量的检验数，当ij0最优。用闭回路法、位势法（3）方案调整与改进：确定进基变量和离基变量，找出新的基可行解(闭回路调整法)。返回（2）第三章运输问题221、西北角法（缺点：没有考虑运价）规则：从运输问题的西北角x11开始，优先安排编号小的产地和销地的运输任务例3.2用西北角法求例3.1的一个初始调运方案首先安排A1到B1的运输任务，即从x11开始分配运输量，并使x11取尽可能大的数值。x11=min{a1,b1}=min{5,2}=2这时，A1还剩5-2=3个单位物资，将3填到a1的修正量处；B1接收到2个单位物资后，它的销量已得到满足，b1的修正量为0，A2，A3不能将物资运往B1（x21=x31=0），称第一列已饱和，划去第一列（见下表），重复上述过程一、初始方案的确定第三章运输问题23销地产地B1B2B3B4产量修正量A162355A278542A339273销量2134修正量230102201110103300初始解为：x11=2,x12=1,x13=2,x23=1,x24=1,x34=3，其余变量为0相应的目标函数值z=6×2+2×1+3×2+5×1+4×1+7×3=50第三章运输问题24西北角法的注意事项：(1)在填入一个数时，如果行和列同时饱和，规定只划去一行或一列，这时行和列的修正量均为0.(2)在剩下最后一个空格时，只能填数（必要时可取0），并划去所在的行和列。(3)在某一行（或列）填最后一个数时，如果行和列同时饱和，则规定只划去该行（或列）。第三章运输问题252、最小元素法规则：优先安排单位运价最小的产地和销地的运输任务例3.3用最小元素法求例3.1的一个初始调运方案首先从运输表（cij）上的最小元素所处的格子开始分配（若有几个格子同时达到最小值，则任取其中一个），其余作法与西北角法基本一致。第一个最小的元素是2，在c12，c33上取到，先分配x12，并使x12取尽可能大的数值。x12=min{a1,b2}=min{5,1}=1这时，A1还剩5-1=4个单位物资，将4填到a1的修正量处；B2接收到1个单位物资后，它的销量已得到满足，b2的修正量为0，A2，A3不能将物资运往B2（x22=x32=0），称第二列已饱和，划去第二列（见下表）。在剩下的运价中找最小元素，重复上述过程。一、初始方案的确定第三章运输问题26销地产地B1B2B3B4产量修正量A162355A278542A339273销量2134修正量040102203020220初始解为：x11=2,x12=1,x14=2,x24=2,x31=0,x33=3，其余变量为0相应的目标函数值z=6×2+2×1+5×2+4×2+3×0+2×3=380第三章运输问题273、Vogel法（元素差额法）规则：不能按最小运费就近供应，就考虑次小运费。各行(各列)的最小运费与次小运费之差称为行差(列差)，也称为罚数。罚数不大，说明不能按最小运费调运时，造成的运费损失不大；罚数越大，说明不能按最小运费调运时，运费增加越多，应尽量安排用最小运费调运。一、初始方案的确定第三章运输问题28例3.4用Vogel法求例3.1的一个初始调运方案①找出运输表（cij）上每行运价的最小元素和次小元素，计算其差额，填入表右边差额栏的第一列；对每列也如此处理（见下表）销地产地B1B2B3B4产量差额A162355A278542A339273销量2134差额1113611第三章运输问题29②在第一列差额和第一行差额中选出差额最大者，并对该最大差额所在的行（或列）中的最小元素进行分配（方法与最小元素法相同），如果出现几个相同的最大差额的行或列，则从中任取一行或一列进行分配。本例中的最大差额是6，出现在B2列，B2列中的最小元素是c12=2，先分配x12，并使x12取尽可能大的数值。x12=min{a1,b2}=min{5,1}=1这时，A1还剩5-1=4个单位物资；B2接收到1个单位物资后，它的销量已得到满足，第二列已饱和，划去第二列（见下表）。重新计算差额，重复上述过程。第三章运输问题30销地产地B1B2B3B4产量差额A162355A278542A339273销量2134差额1113611121131122151112121200122初始解为：x12=1,x13=2,x14=2,x24=2,x31=2,x33=1，其余变量为0相应的目标函数值z=2×1+3×2+5×2+4×2+3×2+2×1=34第三章