《运输与指派模型问题.ppt》由会员分享，可在线阅读，更多相关《运输与指派模型问题.ppt（30页珍藏版）》请在三一文库上搜索。
1、,运筹学 Operations Research,Chapter 7 运输与指派问题 Transportationand Assignment Problem,7.1运输模型 Mathematical Model of Transportation Problems 7.2 运输单纯形法 Transportation Simplex Method 7.3 运输模型的应用 Aplication of Transportation Model 7.4 指派问题 Assignment problem,7.1 运输模型 Mathematical Model of Transportation Prob
2、lems,人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小。这样的问题称为运输问题。,7.1 运输模型 Model of Transportation Problems,7.1.1 数学模型,产地,销地,A1 10,A2 8,3,5,4,2,3,1,6,8,2,3,2,9,图7.1,【例7.1】现有A1，A2，A3三个产粮区，可供应 粮食分别为10，8，5（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需要量分别为5，7，
3、8，3（万吨）。产粮地到需求地的运价（元/吨）如表71所示. 问如何安排一个运输计划，使总的运输费用最少。,运价表（元/T）,表71,设 xij (i=1,2,3；j=1,2,3,4)为i个产粮地运往第j个需求地的运量，,则运输费用为：,从产粮区运出去的量,运给需求地的量,运量应大于或等于零（非负要求），即,这样得到下列运输问题的数学模型：,有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型,【例7.2】有三台机床加工三种零件， 计划第i台的生产任务为a i (i=1,2,3)个零件(三种零件)， 第 j 种零件的需要量为 bj (j=1,2,3)， 第 i 台机床加
4、工第j种零件需要的时间为 cij ， 如下表所示。问如何安排生产任务使总的加工时间最少？,【解】 设 xi j (i=1,2,3；j=1,2,3,)为第 i 台机床加工第 j 种零件的数量，,则总的加工时间为,则此问题的数学模型为,运输问题的一般数学模型,设有m个产地（记作A1，A2，A3,Am），生产某种物资，其产量分别为a1,a2，am；有n个销地（记作B1，B2，Bn），其需要量分别为b1,b2，bn；且产销平衡，即 。从第i个产地到j 个销地的单位运价为cij ，在满足各地需要的前提下，求总运输费用最小的调运方案。 设 xij (i=1,2,，m；j=1,2,n)为第i个产地到第j个销
5、地的运量，则数学模型为：,则数学模型为：,设数学模型为,7.1.2最大值问题,第一种方法：将极大化问题转化为极小化问题。 设极大化问题的运价表为C=（Cij）mn，用一个较大的数M（ MmaxCij ）去减每一个Cij得到矩阵C=（Cij）mn ，其中C/ij=MCij0,将C/作为极小化问题的运价表，用表上用业法求出最优解，目标函数值为,当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。,1.当产大于销时,即,7.1.3 不平衡运输问题,1.当产大于销时,数学模型为,即,由于总产量大于总销量，必有部分产地的产量
6、不能全部 运送完，必须就地库存，即每个产地设一个仓库，库存量 为xi，n+1（i=1，2，m），总的库存量为,bn+1作为一个虚设的销地Bn+1的销量。各产地Ai到Bn+1的运价为零，即Ci，n+1=0,（i=1，m）。则平衡问题的数学模型为：,具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可,2.当销大于产时,即,2.当销大于产时,即,数学模型为,由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为,xm+1,j 是Am+1运到Bj的运量，也是Bj不能满足需要的数量。Am+1到Bj的运价为零,即Cm+1,j=0(j=1,2, ,n),销大
7、于产平衡问题的数学模型为 ：,具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。,上例中，假定B1的需要量是20到60之间，B2的需要量是50到70，试求极小化问题的最优解。,7.1.4需求量不确定的运输问题,先作如下分析：（1）总产量为180，B1，B4的最低需求量 20+50+35+45=150 180，这时属产大于销；,（2）B1，B4的最高需求是60+70+35+45=210 180， 这时属销大于产;,（3）虚设一个产地A5，产量是210180=30， A5的产量只能供应B1或B2。,（4）将B1与B2各分成两部分 的需求量是20， 的需求量是40， 的需求量分别是50与20，因此 必须由A1，A4供应， 可由 A1、A5供应。,（5）上述A5不能供应某需求地的运价用大M表示，A5到 、 的运价为零。得到下表的产销平衡表。,7.1.5中转问题,产地,销地,3,5,4,2,3,1,6,8,2,3,2,9,图5.2,A4,A5,2,2,7,15,中转地,3,4,1,3,设xij为Ai到Aj的运量，i，j=1，2，m+n+r则中转运输问题的数学模型为,产大于销时将式(5.3a)改为“”约束，销大于产时将式(5.3c)改为“”约束,