运筹学_Ch5运输与指派问题.ppt

5.4.1问题的提出与数学模型 指派问题也称分配问题,是一种特殊的整数规划问题,是0-1整数线性规划问题.在生活中经常会遇到这样的问题,某单位需要指派m个人去完成m项任务,每个人只做一工作,同时,每项工作只由一个人完成.由于各人的专长不同,每个人完成各项任务的效率也不同.于是产生了应指派哪一个人去完成哪一项任务,使完成项任务的总效率最高(如所用的时间为最少)的问题.这类问题为指派问题或分配问题. 本题的最优解 X*= 最优分配方案为:让A1承建B3,A2承建B2,A3承建B1,A4承建B4,A5承建B5.这样安排能使总的建造费用最少,为7+9+6+6+6=34(万) 第六步:回到第三步,反复进行,一直到找到了最优分配方案. 得到两个最优解 有两个最优方案 第一种方案：第一个工厂加工产品1，第二工厂加工产品3，第三个工厂加工产品4，第四个工厂加工产品2； 第二种方案：第一个工厂加工产品1，第二工厂加工产品4，第三个工厂加工产品3，第四个工厂加工产品2； 单件产品总成本 Z＝58＋150＋250＋55＝513 5.4 指派问题 assignment problem 6 10 12 9 6 A5 10 6 14 7 6 A4 7 8 12 9 6 A3 10 14 17 9 7 A2 12 15 7 8 4 A1 B5 B4 B3 B2 B1 当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。 1.当产大于销时,即 数学模型为 5.2.5 不平衡运输问题 5.2 运输单纯形法 Transportation Simplex Method 由于总产量大于总销量，必有部分产地的产量不能全部 运送完，必须就地库存，即每个产地设一个仓库，库存量 为xi，n+1（i=1，2，…，m），总的库存量为 5.2 运输单纯形法 Transportation Simplex Method bn+1作为一个虚设的销地Bn+1的销量。各产地Ai到Bn+1的运价为零，即Ci，n+1=0,（i=1，…，m）。则平衡问题的数学模型为： 具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可 5.2 运输单纯形法 Transportation Simplex Method 2.当销大于产时,即 数学模型为 5.2 运输单纯形法 Transportation Simplex Method 由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为 xm+1,j 是Am+1运到Bj的运量，也是Bj不能满足需要的数量。Am+1到Bj的运价为零,即Cm+1,j=0(j=1,2,… ,n) 5.2 运输单纯形法 Transportation Simplex Method 销大于产平衡问题的数学模型为 ： 具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。 5.2 运输单纯形法 Transportation Simplex Method 180 160 45 35 60 20 bj 50 11 10 8 4 A4 30 2 4 6 3 A3 40 8 7 4 -- A2 60 3 2 9 5 A1 ai B4 B3 B2 B1 因为有： 【例5-11】求下列表中极小化运输问题的最优解。 所以是一个产大于销的运输问题。 5.2 运输单纯形法 Transportation Simplex Method 表5-21 表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180－160=20的销地B5，Ci5=0，i=1，2，3，4。表的右边增添一列 这样可得新的运价表： 180 20 45 35 60 20 bj 50 0 11 10 8 4 A4 30 0 2 4 6 3 A3 40 0 8 7 4 M A2 60 0 3 2 9 5 A1 ai B5 B4 B3 B2 B1 5.2 运输单纯形法 Transportation Simplex Method 180 20 45 35 60 20 Bj 50 20 10 20 A4 30 20 10 A3 40 40 A2 60 25 35 A1 Ai B5 B4 B3 B2 B1 下表为计算结果。可看出：产地A4还有20个单位没有运出。 5.2 运输单纯形法 Transportation Simplex Method 【例5-12】在例5-11中，假定B1的需要量是20到60之间，B2的需要量是50到70，试求极小化问题的最优解。 180 150～210 45 35 50～70