资源描述
,3.1 运输问题的数学模型,Mathematical Model of,T,P,Ch3 Transportation Problem,*,Page,11,of 11,Chapter 3 运输问题,Transportation Problem,运输问题是一种特殊的线性规划问题,用一种特殊的,方法(表上作业法)求解更为简单,运筹学,Operations Research,1.,运输模型,Mathematical Model of,Transportation Problems,2.,基变量与闭回路,Basis Variable and Closed path,3.,表上作业法,Transportation Simplex Method,4.,运输问题的变体,Variants of Transportation Problems,9/14/2024,运输问题,人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的,生产量,和,需要量,及各地之间的,运输费用,，如何制定一个运输方案，使总的运输费用最小。这样的问题称为,运输问题,。,9/14/2024,运输问题的特征,Characteristics of Transportation Problems,每一个,出发地,都有一定的,供应量,（,supply,）配送到目的地，每一个,目的地,都有需要从一定的,需求量,（,demand,）,，,接收从出发地发出的产品。,需求假设,（,The Requirements Assumption,）,可行解特性,（,The Feasible Solutions Property,）,成本假设（The Cost Assumption）,整数解性质（Integer Solutions Property）,9/14/2024,需求假设,（,The Requirements Assumption,）：,每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之相类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足，,即,总供应量 总需求量,可行解特性（The Feasible Solutions Property）：,当且仅当供应量的总和等于需求量的总和时，运输问题才有可行解,9/14/2024,成本假设（The Cost Assumption）：,从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系，因此这个成本就等于配送的单位成本乘以所配送的数量,整数解性质（Integer Solutions Property）,：,只要它的供应量和需求量都是整数，任何有可行解的运输问题必然有所有决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件,9/14/2024,【,例1,】现有,A,1,，,A,2,，,A,3,三个产粮区，可供应 粮食分别为10，8，5（万吨），现将粮食运往,B,1,，,B,2,，,B,3,，,B,4,四个地区，其需要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（10万元/万吨）如表31所示，问如何安排一个运输计划，使总的运输费用最少。,钢铁厂,矿山,B1,B2,B3,B4,产量,A1,3,2,6,3,10,A2,5,3,8,2,8,A3,4,1,2,9,5,需要量,5,7,8,3,23,运价表（元/吨）,表31,9/14/2024,设,x,ij,(,i,=1,2,3；,j,=1,2,3,4)为,i,个产粮地运往第,j,个需求地的运量，这样得到下列运输问题的数学模型：,运量应大于或等于零（非负要求），即,Min z = 3,x,11,+ 2,x,12,+ 6,x,13,+ 3,x,14,+ 5,x,21,+ 3,x,22,+ 8,x,23,+ 2,x,24,+ 4,x,31,+,x,32,+ 2,x,33,+ 9,x,34,x,ij, 0,i,=1, 2, 3;,j,=1, 2, 3, 4,9/14/2024,有些问题表面上与运输问题没有多大关系，但经过转换，也可以建立与运输问题形式相同的数学模型,看一个例子：,【,例2,】,有三台机床加工三种零件，计划第,i,台的生产任务为,a,i,(,i,=1,2,3)个零件，第,j,种零件的需要量为,b,j,(,j,=1,2,3)，第,i,台机床加工第,j,种零件需要的时间为,c,ij,，如表32所示。问如何安排生产任务使总的加工时间最少？,零件,机床,B1,B2,B3,生产任务,A1,5,2,3,50,A2,6,4,1,60,A3,7,3,4,40,需要量,70,30,50,150,表32,9/14/2024,【解】 设,x,i j,(,i,=1,2,3；,j,=1,2,3,)为第,i,台机床加工第,j,种零件的数量，则此问题的数学模型为,9/14/2024,运输问题的数学模型,设有,m,个产地（记作,A,1,，,A,2,，,A,3,Am,），生产某种物资，其产量分别为,a,1,a,2,，,a,m,；有,n,个销地（记作,B,1,，,B,2,，,B,n,），其需要量分别为,b,1,b,2,，,b,n,；且产销平衡，即 。从第,i,个产地到,j,个销地的单位运价为,c,ij,，在满足各地需要的前提下，求总运输费用最小的调运方案。 设,x,ij,(,i,=1,2,，,m,；,j,=1,2,n,)为第,i,个产地到第,j,个销地的运量，则数学模型为：,9/14/2024,基变量与闭回路,Exit,9/14/2024,
展开阅读全文