运输与指派模型问题.ppt

* 运筹学 Operations Research Chapter 7 运输与指派问题 Transportation?and 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 Problems 人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小。这样的问题称为运输问题。 7.1 运输模型 Model of Transportation Problems 7.1.1 数学模型 产地 销地 A1 10 A2 8 A3 5 B4 3 B3 8 B2 7 B1 5 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，8，3（万吨）。产粮地到需求地的运价（元/吨）如表7－1所示. 问如何安排一个运输计划，使总的运输费用最少。 23 3 8 7 5 需要量 5 9 2 1 4 A3 8 2 8 3 5 A2 10 3 6 2 3 A1 产量 B4 B3 B2 B1 地区 产粮区 运价表（元/T） 表7－1 设 xij (i=1,2,3；j=1,2,3,4)为i个产粮地运往第j个需求地的运量， 则运输费用为： 23 3 8 7 5 需要量 5 9 2 1 4 A3 8 2 8 3 5 A2 10 3 6 2 3 A1 产量 B4 B3 B2 B1 地区 产粮区 23 3 8 7 5 需要量 5 9 2 1 4 A3 8 2 8 3 5 A2 10 3 6 2 3 A1 产量 B4 B3 B2 B1 地区 产粮区 从产粮区运出去的量 运给需求地的量 23 3 8 7 5 需要量 5 9 2 1 4 A3 8 2 8 3 5 A2 10 3 6 2 3 A1 产量 B4 B3 B2 B1 地区 产粮区 运量应大于或等于零（非负要求），即 这样得到下列运输问题的数学模型： 有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型 【例7.2】有三台机床加工三种零件， 计划第i台的生产任务为a i (i=1,2,3)个零件(三种零件)， 第 j 种零件的需要量为 bj (j=1,2,3)， 第 i 台机床加工第j种零件需要的时间为 cij ， 如下表所示。问如何安排生产任务使总的加工时间最少？ 150 50 30 70 需要量 40 4 3 7 A3 60 1 4 6 A2 50 3 2 5 A1 生产任务 B3 B2 B1 零件 机床 【解】 设 xi j (i=1,2,3；j=1,2,3,)为第 i 台机床加工第 j 种零件的数量， 150 50 30 70 需要量 40 4 3 7 A3 60 1 4 6 A2 50 3 2 5 A1 生产任务 B3 B2 B1 零件 机床 则总的加工时间为 则此问题的数学模型为 运输问题的一般数学模型 设有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个销地的运量，则数学模型为： 则数学模型为： 设数学模型为 7.1.2最大值问题 第一种方法：将极大化问题转化为极小化问题。 设极大化问题的运价表为C=（Cij）m×n，用一个较大的数M（ M≥max{Cij} ）去减每一个Cij得到矩阵C′=（C′ij）m×n ，其中C/ij=M－Cij≥0,将C/作为极小化问题的运价表，用表上用业法求出最优解，目标函数值为 当总产量与总销量不相等时,称为不平衡运输问题.