运筹学 (第三版) 第3节 《运筹学》教材编写组 产销不平 衡的运输 第3章运输问题 问题及其 求解方法 (继续) 第4节 应用举例 钱颂迪制作 清华大学出版社
第3节 产销不平 衡的运输 问题及其 求解方法 第4节 应用举例 钱颂迪制作 运筹学 (第三版) 《运筹学》教材编写组 第3章 运输问题 (继续) 清华大学出版社
第3节产销不平衡的运输问题及其求解方法 前面所讲表上作业法,都是以产销平衡 为前提条件的;但是实际问题中产销往 往是不平衡的。就需要把产销不平衡的 问题化成产销平衡的问题 当产大于销
第3节 产销不平衡的运输问题及其求解方法 • 前面所讲表上作业法,都是以产销平衡 为前提条件的;但是实际问题中产销往 往是不平衡的。就需要把产销不平衡的 问题化成产销平衡的问题。 • 当产大于销 = = m i n j ai bj 1 1
运输问题的数学模型可写成 目标函数:mn=∑∑x 满足:∑≤a,(=12…m) ∑x≤b,(=12…m) ≥0
运输问题的数学模型可写成 • 目标函数: • 满足: = = = m i n j ij ij z c x 1 1 min = = = = 0 , ( 1,2, , ) , ( 1,2, , ) 1 1 ij m i ij j n j ij i x x b j n x a i m
由于总的产量大于销量,就要考虑多余的物资在 哪一个产地就地储存的问题。设xpm是产地A的 储存量,于是有: X:;+x, 1,+/又+1 八少=4,(i=1,2, ∑ ∑xm+1=∑41-∑b=b1
由于总的产量大于销量,就要考虑多余的物资在 哪一个产地就地储存的问题。设xi , n+1是产地Ai的 储存量,于是有: = + = + + = = = n j n j xi j xi n xi j ai i m 1 1 1 , 1 , ( 1,2,, ) = = = m i xij bj j n 1 ( 1,2,, ) = = = + = − = + m i m i n j i n ai bj bn x 1 1 1 , 1 1
令: G=G 当i=-1,…,m,j=1,,n时 c=0,当i=1,…,m,jn+1时 将其分别代入,得到 n+1 mi=∑∑x=∑∑x+∑m+1 ∑∑
令: ij ij c = c ' 0, ' cij = 当 i=1,…,m,j=1,…,n时 当 i=1,…,m,j=n+1时 将其分别代入,得到 = = = + = = + = = = = = + m i n j i j i j m i n j m i i n m i n j i j i j i j i j c x z c x c x c 1 1 1 1 1 1 ' , 1 1 1 ' ' ' min
满足: ≥0 由于这个模型中 n+1 ∑a=∑b+bn+1=∑b 所以这是一个产销平衡的运输问题
满足: = = = + = 0 1 1 1 ij m i ij j n j ij i x x b x a + = = + = = + = 1 1 1 1 1 n j j n j j n m i ai b b b 由于这个模型中 所以这是一个产销平衡的运输问题
若当产大于销时, 只要增加一个假想的销地j=n+1(实际上是储存), 该销地总需要量为 ∑a,-∑ 而在单位运价表中从各产地到假想销地的单位运价为, CinH1=0就转化成一个产销平衡的运输间题
若当产大于销时, 只要增加一个假想的销地j=n+1(实际上是储存), 该销地总需要量为 = = − n j j m i ai b 1 1 而在单位运价表中从各产地到假想销地的单位运价为, ci ; ,n+1 = 0 就转化成一个产销平衡的运输问题
当销大于产时, 可以在产销平衡表中增加一个假想的产地 i=m+1,该地产量为 在单位运价表上令从该假想产地到各销地的运价 n,=0同样可以转化为一个产销平衡的运输问题
当销大于产时, 可以在产销平衡表中增加一个假想的产地 i=m+1,该地产量为 = = − n j m i bj a j 1 1 在单位运价表上令从该假想产地到各销地的运价, 0 同样可以转化为一个产销平衡的运输问题.。 ; cm+1, j =
例2设有三个化肥厂(A,B,C)供应四个地区(I, Ⅱ,Ⅲ,Ⅳ)的农用化肥。假定等量的化肥在这些地 区使用效果相同。各化肥厂年产量,各地区年需要量 及从各化肥厂到各地区运送单位化肥的运价如表3-25 所示。试求出总的运费最节省的化肥调拨方案。 表3-25 需求地区IⅡⅢⅣ|产量(万吨) 化工厂 ABC 16132217 50 14|131915 60 192023 50 最低需求(万吨) 30700 10 最高需求(万吨) 507030不限
例2 设有三个化肥厂(A,B,C)供应四个地区(Ⅰ, Ⅱ,Ⅲ,Ⅳ)的农用化肥。假定等量的化肥在这些地 区使用效果相同。各化肥厂年产量,各地区年需要量 及从各化肥厂到各地区运送单位化肥的运价如表3-25 所示。试求出总的运费最节省的化肥调拨方案。 表3-25 需求地区 化工厂 Ⅰ Ⅱ Ⅲ Ⅳ 产量(万吨) A B C 16 14 19 13 13 20 22 19 23 17 15 / 50 60 50 最低需求(万吨) 最高需求(万吨) 30 50 70 70 0 30 10 不限
解这是一个产销不平衡的运输问题,总产量为160 万吨,四个地区的最低需求为110万吨,最高需求为 无限。根据现有产量,第Ⅳ个地区每年最多能分配 到60万吨,这样最高需求为210万吨,大于产量。为 了求得平衡,在产销平衡表中增加一个假想的化肥 厂D,其年产量为50万吨。由于各地区的需要量包含 两部分,如地区Ⅰ,其中30万吨是最低需求,故不 能由假想化肥厂D供给,令相应运价为M(任意大正 数),而另一部分20万吨满足或不满足均可以,因此 可以由假想化肥厂D供给,按前面讲的,令相应运价 为0。对凡是需求分两种情况的地区,实际上可按照 两个地区看待。这样可以写出这个问题的产销平衡 表(表3-26)和单位运价表(表3-27)
• 解 这是一个产销不平衡的运输问题,总产量为160 万吨,四个地区的最低需求为110万吨,最高需求为 无限。根据现有产量,第Ⅳ个地区每年最多能分配 到60万吨,这样最高需求为210万吨,大于产量。为 了求得平衡,在产销平衡表中增加一个假想的化肥 厂D,其年产量为50万吨。由于各地区的需要量包含 两部分,如地区Ⅰ,其中30万吨是最低需求,故不 能由假想化肥厂D供给,令相应运价为M(任意大正 数),而另一部分20万吨满足或不满足均可以,因此 可以由假想化肥厂D供给,按前面讲的,令相应运价 为0。对凡是需求分两种情况的地区,实际上可按照 两个地区看待。这样可以写出这个问题的产销平衡 表(表3-26)和单位运价表(表3-27)