第_12_讲次课程名称：《运筹学》授课题目产销不平衡的运输问题及其求解方法本讲目的要求及重点难点：【目的要求]通过本讲课程的学习，进一步理解并掌握运输问题的求解方法。[重点及难点】产销不平衡问题如何转为平衡运输问题。内容[本讲课程的引入]前面讲的表上作业法，都是以产销平衡为前提的，但在实际问题中产销往往是不平衡的，这就需要把产销不平衡的问题化成产销平衡的问题。[本讲课程的内容]当产大于销时，运输问题的数学模型为：mnZNminz =CijXiji=1j=lmZ ij = bj，j=1, 2,,ni=1hZxj≤ai,i=1, 2,mj=1xij≥0由于总的产量大于销量，就要考虑多余的物资在哪一个产地就地贮存的问题。设xi，n+1是产地Ai的贮存量，于是有：m2xj=bj,j=l,2,,ni=1nn+1ZExj=ai,i=l,2,,mxij+Xi, n+I =j=1j=1xij ≥0
课程名称：《运筹学》 第 12 讲次 授课题目 产销不平衡的运输问题及其求解方法 本讲目的要求及重点难点： 目的要求] 通过本讲课程的学习，进一步理解并掌握运输问题的求解方法。 [重点及难点] 产销不平衡问题如何转为平衡运输问题。 内 容 [本讲课程的引入] 前面讲的表上作业法，都是以产销平衡为前提的，但在实际问题中产销往往是不平 衡的，这就需要把产销不平衡的问题化成产销平衡的问题。 [本讲课程的内容] 当产大于销时，运输问题的数学模型为： min z ＝ ∑ ∑ cij xij ∑ xij ＝ bj ，j ＝ 1，2，.，n ∑ xij ≤ ai ，i ＝ 1，2，.，m xij ≥ 0 由于总的产量大于销量，就要考虑多余的物资在哪一个产地就地贮存的问题。设 xi，n+1 是产 地 Ai 的贮存量，于是有： ∑ x ij ＝ b j ，j ＝ 1，2，.，n ∑ xij ＋ xi，n+1 ＝ ∑ x ij ＝ a i ，i ＝ 1，2，.，m xij ≥ 0 m i=1 n j=1 m i=1 n j=1 i=1 m j=1 n j=1 n+1
内容nmm2Z bj = bn+1 ai -/Xi,n+1i=1i=1j=1即nn+1mZ ai = bi + tZ bjbn+1=j=1=1=1这样，就把原产大于销的问题转化为产销平衡的问题，只是增加了一个假想的销地j=n+1（实际上是贮存），该销地的总需要量为nmZ ai-Z bji=1 j=1而在单位运价表中从各产地到假想销地的单位运价ci，n+1=0。当销大于产时，可以在产销平衡表中增加一个假想的产地i=m+1，该地产量为nm bi - aii=1j=1在单位运价表上令从该假想产地到各销地的运价cm+1，j=0，同样可以转化为一个产销平衡的运输问题。例1某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？销B3B1B2B1B2B3产量产78131512A145291122A212336需求2553114
内 容 ∑ xi，n+1 ＝ ∑ ai － ∑ bj ＝ bn+1 即 ∑ ai ＝ ∑ bj ＋ bn+1 ＝ ∑ bj 这样，就把原产大于销的问题转化为产销平衡的问题，只是增加了一个假想的销地 j = n + 1（实际上是贮存），该销地的总需要量为 ∑ ai － ∑ bj 而在单位运价表中从各产地到假想销地的单位运价 c i，n+1 = 0 。 当销大于产时，可以在产销平衡表中增加一个假想的产地 i = m + 1 ，该地产量为 ∑ bj － ∑ ai 在单位运价表上令从该假想产地到各销地的运价 c m+1，j = 0 ，同样可以转化为一个产销平衡 的运输问题。 例 1 某公司从两个产地 A1、A2 将物品运往三个销地 B1、B2、B3，各产地的产量、各销地的 销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ 销 产 B1 B2 B3 产量 B1 B2 B3 A1 78 13 15 12 A2 45 11 29 22 需求 53 36 25 123 114 i=1 i=1 m m i=1 m j=1 j=1 j=1 n n n+1 i=1 i=1 m m j=1 j=1 n n
内容解：这里，总产量为78+45=123；总销量为53+36+25=114。产销不平衡，增加一个虚设的销地，得到下表销产量B1B2B3B4B1B2B3B4产01315120A14529220A211123需求522536例2某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表，问：应如何调运可使总运输费用最小？销B3B2B1B2产量B1B3产131512A17845A2112922123需求533665154解：这里，总产量小于总销量，产销不平衡，增加一个虚设的产地，行得到下表销BB3BB2产量B1B3产78131512A1A24511292231A300065需求5336154例3有A1、A2、A3三个生产某种物资的产地，五个地区B1、B2、B3、B4、B5对这种物资有需求。现要将这种物资从三个产地运往五个需求地区，各产地的产量、各需求地区的需要量和各产地运往各地区每单位物资的运费如下表所示，其中B2地区的115个单位必须满足。问：应如何调运可使总运输费用最小？B1B2B3B4B5产量1020204050A115201530A240301003035405525A313025603070需求115
内 容 解： 这里，总产量为 78 + 45 = 123 ；总销量为 53 +36 + 25 = 114 。产销不平衡，增加一个 虚设的销地，得到下表 销 产 B1 B2 B3 B4 产量 B1 B2 B3 B4 A1 78 13 15 12 0 A2 45 11 29 22 0 需求 52 36 25 9 123 例 2 某公司从两个产地 A1、A2 将物品运往三个销地 B1、B2、B3，各产地的产量、各销地的 销量和各产地运往各销地每件物品的运费如下表，问：应如何调运可使总运输费用最小？ 销 产 B1 B2 B3 产量 B1 B2 B3 A1 78 13 15 12 A2 45 11 29 22 需求 53 36 65 123 154 解: 这里，总产量小于总销量，产销不平衡，增加一个虚设的产地，得到下表 销 产 B1 B2 B3 产量 B1 B2 B3 A1 78 13 15 12 A2 45 11 29 22 A3 31 0 0 0 需求 53 36 65 154 例 3 有 A1、A2、A3 三个生产某种物资的产地，五个地区 B1、B2、B3、B4、B5 对这种物 资有需求。现要将这种物资从三个产地运往五个需求地区，各产地的产量、各需求地区的需要 量和各产地运往各地区每单位物资的运费如下表所示，其中 B2 地区的 115 个单位必须满足。 问：应如何调运可使总运输费用最小？ B1 B2 B3 B4 B5 产量 A1 10 15 20 20 40 50 A2 20 40 15 30 30 100 A3 30 35 40 55 25 130 需求 25 115 60 30 70
内容解：由于产量小于需求量，因此设一虚设产地A4，它的产量为需求量与产量的差20，与这项有关的运输费用一般为零。因为B2地区的115个单位必须满足，即不能有物资从A4运往B2地区，于是取相应的费用为M（M是一个充分大的正数），以保证在求最小运输费用的前提下，该变量的值为零。销地BB1B4BSB3产量产地A1101520204050A22040153030100A33035552540130A40M0002025603070115需求例4.8某研究院有B1、B2、B3三个区。每年取暖分别需要用煤3500吨、1100吨、2400吨，这些煤都要由A1、A2两处煤矿负责供应，价格、质量均相同。A1、A2煤矿的供应能力分别为1500吨、4000吨，运价（元/吨）如下表。由于需求大于供给，经院研究决定B1区供应量可减少0—900吨，B2区必须满足需求量，B3区供应量不少于1600吨，试求总费用为最低的调运方案。销地B1B2B3产量产地Z1751952081500A21822151604000需求量350011002400解：这是需求量大于生产量的运输问题，由于B1区供应量可减少0一900吨，B2区必须满足需求量，B3区供应量不少于1600吨，可以把B1区和B3区分别设为两个区：一个为必须满足需求量的区域，另一个为可以调整供应量的区域。这样，原问题化为五个需求区域B1B1'、B2、B3、B3的问题，同时增加一个虚设的产地A3。在运输费方面，必须满足需求量的相应变量，运费的取值为M，可调整需求量的相应变量，运费的取值为0，作出产销平衡的运价表
内 容 解：由于产量小于需求量，因此设一虚设产地 A4 ,它的产量为需求量与产量的差 20，与这一 项有关的运输费用一般为零。因为 B2 地区的 115 个单位必须满足，即不能有物资从 A4 运往 B2 地区，于是取相应的费用为 M（M 是一个充分大的正数），以保证在求最小运输费用的前 提下，该变量的值为零。 销地 产地 B1 B2 B3 B4 B5 产量 A1 10 15 20 20 40 50 A2 20 40 15 30 30 100 A3 30 35 40 55 25 130 A4 0 M 0 0 0 20 需求 25 115 60 30 70 例 4.8 某研究院有 B1 、B2、B3 三个区。每年取暖分别需要用煤 3500 吨、1100 吨、2400 吨， 这些煤都要由 A1、A2 两处煤矿负责供应，价格、质量均相同。A1、A2 煤矿的供应能力分 别为 1500 吨、4000 吨，运价（元/吨）如下表。由于需求大于供给，经院研究决定 B1 区供 应量可减少 0—900 吨，B2 区必须满足需求量，B3 区供应量不少于 1600 吨，试求总费用 为最低的调运方案。 销地 产地 B1 B2 B3 产量 A1 175 195 208 1500 A2 160 182 215 4000 需求量 3500 1100 2400 解： 这是需求量大于生产量的运输问题，由于 B1 区供应量可减少 0—900 吨，B2 区必须 满足需求量，B3 区供应量不少于 1600 吨，可以把 B1 区和 B3 区分别设为两个区：一个为 必须满足需求量的区域，另一个为可以调整供应量的区域。这样，原问题化为五个需求区域 B1、 B1’、B2、B3、B3’ 的问题，同时增加一个虚设的产地 A3 。在运输费方面, 必须满足需求量 的相应变量，运费的取值为 M ，可调整需求量的相应变量 ，运费的取值为 0，作出产销平 衡的运价表
内容销地B2B1*B3B3*产量B1产地A11751751952082081500A2160160182P152154000MMA2M001500需求量260090011008001600【本讲小结】通过今天的学习我们可以知道产销不平衡的运输问题总是可以通过转化为产销平衡的运输问题来求解的。转化过程中必须处理好运价问题。[本讲课程的作业]：复习整章内容
内 容 销地 产地 B1 B1* B2 B3 B3* 产量 A1 175 175 195 208 208 1500 A2 160 160 182 215 215 4000 A2 M 0 M M 0 1500 需求量 2600 900 1100 1600 800 [本讲小结] 通过今天的学习我们可以知道产销不平衡的运输问题总是可以通过转化为产销平衡的 运输问题来求解的。转化过程中必须处理好运价问题。 [本讲课程的作业] ：复习整章内容