运筹学运输问题

1、Chapter4 运输问题运输问题运输模型运输模型运输问题的表上作业法运输问题的表上作业法 运输问题的应用运输问题的应用 中华图书进出口总公司的主营业务之一是中文书刊对国外出口业务，每年中华图书进出口总公司的主营业务之一是中文书刊对国外出口业务，每年10月月-12月为下一年度报刊订阅的征订期。在此期间，为巩固老订户，发展新订户，要向月为下一年度报刊订阅的征订期。在此期间，为巩固老订户，发展新订户，要向国外个人、大学图书馆、科研机构等无偿寄发小礼品和征订宣传推广材料。国外个人、大学图书馆、科研机构等无偿寄发小礼品和征订宣传推广材料。 中华图书进出口总公司在深圳、上海的分公司也部分经营中文报刊的出

2、口业务。中华图书进出口总公司在深圳、上海的分公司也部分经营中文报刊的出口业务。为维护公司整体利益，公司对征订期间三个部门寄发征订材料的工作做了整体安排。为维护公司整体利益，公司对征订期间三个部门寄发征订材料的工作做了整体安排。部部 门门份数份数/册册中文书刊出口部15000深圳分公司7500上海分公司7500总 计30000 日本、韩国以及中国香港地区集中了该公司的绝大部分中文报刊订户，根据订日本、韩国以及中国香港地区集中了该公司的绝大部分中文报刊订户，根据订户数分布数量不同，寄发征订材料的数量也不同，对此公司也做了安排。户数分布数量不同，寄发征订材料的数量也不同，对此公司也做了安排。国家和地

3、区国家和地区份数份数/册册日 本15000中国香港特别行政区10000韩 国5000总 计30000 这些材料无论由三家中哪个部门寄出，征收订户的效果大致相同；同时，无论这些材料无论由三家中哪个部门寄出，征收订户的效果大致相同；同时，无论读者向哪个部门订阅，为总公司创造的利益均是大致一样的。读者向哪个部门订阅，为总公司创造的利益均是大致一样的。 但由于各部门邮途距离不同，邮寄方式及人工费用不同，导致从各部门寄往各但由于各部门邮途距离不同，邮寄方式及人工费用不同，导致从各部门寄往各地的费用也不同。地的费用也不同。日日 本本中国香港特别行政区中国香港特别行政区韩韩 国国中文书刊出口部中文书刊出口部

4、10.2079深圳分公司深圳分公司12.50414上海分公司上海分公司687.50 要求：在服从公司总体安排的前提下，作出一个公司整体的中文书刊征订材料要求：在服从公司总体安排的前提下，作出一个公司整体的中文书刊征订材料的邮运方案，使得公司总的邮运费用最小。的邮运方案，使得公司总的邮运费用最小。5运输问题：解决把某种产品从若干个产地调运到若干个销地，在每个产运输问题：解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，各地之间的运输单价已知的前提地的供应量与每个销地的需求量已知，各地之间的运输单价已知的前提下，如何确定一个使得总的运输费用最小的方案的问题。下，

5、如何确定一个使得总的运输费用最小的方案的问题。1 1运运 输输 模模 型型例例 某公司从两个产地某公司从两个产地A1、A2将物品运往三个销地将物品运往三个销地B1、B2、B3，各产地，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？示，问：应如何调运可使总运输费用最小？B1B2B3产量A1646200A2655300销量1501502006解：解： 产销平衡问题：产销平衡问题： 总产量总产量 = 总销量总销量 设设 xij 为从产地为从产地Ai运往销地运往销地Bj的运输量，得到下

6、列运输量表：的运输量，得到下列运输量表： 满足产地产量的约束条件：满足销地销量的约束条件：使运费最小，即 1 1运运 输输 模模 型型B1B2B3产量A1x11x12x13200A2x21x22x23300销量150150200111213212223200300 xxxxxx112112221323150150200 xxxxxx111213212223min 646655fxxxxxxB1B2B3产 量A1646200A2655300销 量1501502007所以此线性规划问题的线性规划模型如下： 1 1运运 输输 模模 型型11121321222311121321222311211222

7、1323min 646655200300150s.t. 15020001,2;1,2,3ijfxxxxxxxxxxxxxxxxxxxij81 1运运 输输 模模 型型产销平衡运输问题的一般模型：产销平衡运输问题的一般模型： A1、 A2、 Am 表示某物资的表示某物资的m个产地；个产地；B1、B2、Bn 表示某物质的表示某物质的n个销地；个销地；si 表示产地表示产地Ai的产量；的产量；dj 表示销地表示销地Bj 的销量；的销量； cij 表示把物资从产地表示把物资从产地Ai运往销地运往销地Bj的单位运价。的单位运价。 设设 xij 为从产地为从产地Ai运往销地运往销地Bj的运输量，得到下列一

8、般运输问题的模型：的运输量，得到下列一般运输问题的模型： 1111min ,i=1,2,ms.t. ,j=1,2,n0,ij.mnijijijnijijmijjiijfc xxsxdxLL对所有的 和91 1运运 输输 模模 型型上述运输问题一般模型的变体：上述运输问题一般模型的变体： 求目标函数的最大值，如求利润最大或营业额最大等；求目标函数的最大值，如求利润最大或营业额最大等； 当某些运输线路上的能力有限制时，在模型中要加入运输能力限制的当某些运输线路上的能力有限制时，在模型中要加入运输能力限制的约束条件；约束条件； 产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销产销不平衡时

9、，可加入假想的产地（销大于产时）或销地（产大于销时）。时）。B1B2B3产量A1x11x12x13200A2x21x22x23300销量15015020013100 x102 2运输问题的表上作业法运输问题的表上作业法表上作业法：是求解运输问题的方法，其实质是单纯形法。表上作业法：是求解运输问题的方法，其实质是单纯形法。表上作业法的计算过程：表上作业法的计算过程：找出初始基本可行解：由于产销平衡，运输问题有找出初始基本可行解：由于产销平衡，运输问题有m+n-1个基个基变量。在变量。在mn的产销平衡表上给出的产销平衡表上给出m+n-1个数字格，其相对个数字格，其相对应的调运量的值即为基变量的值；

10、应的调运量的值即为基变量的值；求各非基变量的检验数：检验除了上述求各非基变量的检验数：检验除了上述m+n-1个基变量以外的个基变量以外的空格的检验数，判别是否达到最优解，如果已是最优，停止空格的检验数，判别是否达到最优解，如果已是最优，停止计算，否则转到下一步；计算，否则转到下一步；确定入基变量和出基变量：在表上用闭回路法找出新的基本确定入基变量和出基变量：在表上用闭回路法找出新的基本可行解；可行解；重复重复2、3直到得到最优解。直到得到最优解。112 2运输问题的表上作业法运输问题的表上作业法例例 喜庆食品公司有三个生产面包的分厂喜庆食品公司有三个生产面包的分厂A1，A2，A3，有四个销售公

11、司，有四个销售公司B1，B2，B3，B4，其各分厂每日的产量、各销售公司每日的销量以及各，其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公司的单位运价如表所示，在表中产量与销量的单位为吨，分厂到各销售公司的单位运价如表所示，在表中产量与销量的单位为吨，运价的单位为百元运价的单位为百元/吨。问该公司应如何调运产品在满足各销点的需求量吨。问该公司应如何调运产品在满足各销点的需求量的前提下总运费最少？的前提下总运费最少？ 销地产地B1B2B3B4产量A13113107A219284A3741059销量3656 2020122 2运输问题的表上作业法运输问题的表上作业法一、确定初始基本可行

12、解一、确定初始基本可行解 为了把初始基本可行解与运价区分开，我们把运价放在每一栏的右上为了把初始基本可行解与运价区分开，我们把运价放在每一栏的右上角，每角，每一栏的中间写上初始基本可行解（调运量）。一栏的中间写上初始基本可行解（调运量）。 1.西北角法西北角法 销地产地 B1 B2 B3 B4 产量 A1 7 A2 4 A3 9 销量 3 6 5 6 2020311310851029471304420202203306600初始基本可行解：初始基本可行解：总运输费用为：总运输费用为：135（百元）（百元）1112222333343,4,2,2,3,6xxxxxx132 2运输问题的表上作业法运

13、输问题的表上作业法2.最小元素法最小元素法 最小元素法是就近供应，即对单位运价最小的变量分配运输量。最小元素法是就近供应，即对单位运价最小的变量分配运输量。 销地产地 B1 B2 B3 B4 产量 A1 7 A2 4 A3 9 销量 3 6 5 6 2020311310851029471301104430603303300初始基本可行解：初始基本可行解：总运输费用为：总运输费用为：86（百元）（百元）1314212332344,3,3,1,6,3xxxxxx通过西北角法求得的初始基本可行解对应的总运输费用为：通过西北角法求得的初始基本可行解对应的总运输费用为：135（百元）（百元）142 2运

14、输问题的表上作业法运输问题的表上作业法 注意：注意：当取定当取定xij的值之后，会出现的值之后，会出现Ai的产量与的产量与Bj的销量都的销量都改为零的情况，这时只能划去改为零的情况，这时只能划去Ai行或行或Bj列，但不列，但不能同时划去能同时划去Ai行与行与Bj列。列。用最小元素法时，可能会出现只剩下一行或一列的用最小元素法时，可能会出现只剩下一行或一列的所有格均未填数或未被划掉的情况，此时在这一所有格均未填数或未被划掉的情况，此时在这一行或者一列中除去已填上的数外均填上零，不能行或者一列中除去已填上的数外均填上零，不能按空格划掉。这样可以保证填过数或零的格为按空格划掉。这样可以保证填过数或零

15、的格为m+n-1个，即保证基变量的个数为个，即保证基变量的个数为m+n-1个。个。152 2运输问题的表上作业法运输问题的表上作业法二、最优解的判别二、最优解的判别 1.闭回路法：在已给出的调运方案的运输表上从一个代闭回路法：在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，只有表非基变量的空格出发，沿水平或垂直方向前进，只有遇到代表基变量的填入数字的格才能向左或右转遇到代表基变量的填入数字的格才能向左或右转90度继度继续前进，这样继续下去，直至回到出发的那个空格，由续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭回路。一个空格存在唯一的闭此

16、形成的封闭折线叫做闭回路。一个空格存在唯一的闭回路。回路。 销地产地 B1 B2 B3 B4 产量 A1 43 7 A2 3 1 4 A363 9 销量 3 6 5 6 2020311310851029471x11x11162 2运输问题的表上作业法运输问题的表上作业法 闭回路法：是对于代表非基变量的空格（其调运量为零），把它的闭回路法：是对于代表非基变量的空格（其调运量为零），把它的调运量调整为调运量调整为1，由于产销平衡的要求，由于产销平衡的要求,我们必须对这个空格的闭回路的我们必须对这个空格的闭回路的顶点的调运量加上或减少顶点的调运量加上或减少1。最后计算出由这些变化给整个运输方案的。最

17、后计算出由这些变化给整个运输方案的总运输费带来的变化，即这个空格代表的非基变量的检验数。如果所有总运输费带来的变化，即这个空格代表的非基变量的检验数。如果所有代表非基变量的空格的检验数都大于等于零，则已求得最优解，否则继代表非基变量的空格的检验数都大于等于零，则已求得最优解，否则继续迭代找出最优解。续迭代找出最优解。 销地产地 B1 B2 B3 B4 产量 A1 43 7 A2 3 1 4 A363 9 销量 3 6 5 6 2020311310851029471运费的变化：运费的变化：33-32+22-1=1172 2运输问题的表上作业法运输问题的表上作业法空空 格格闭闭 回回 路路检检 验

18、验 数数121-1101211x12x22x24x31x33x1113232111xxxxx1214343212xxxxx22231314343222xxxxxxx2423131424xxxxx31341413232131xxxxxxx3334141333xxxxx182 2运输问题的表上作业法运输问题的表上作业法2.位势法：对运输表上的每一行赋予一个数值位势法：对运输表上的每一行赋予一个数值ui，对每一列赋予一个数值，对每一列赋予一个数值vj，它们的数值是由基变量，它们的数值是由基变量xij的检验数的检验数 所决定的，则非所决定的，则非基变量基变量xij的检验数就可以用公式的检验数就可以用公

19、式 求出。求出。 销地产地 B1 B2 B3 B4 ui A1 4 3 A2 3 1 A3 6 3 vj 3113108510294710jiijijvucjiijijvuc0310-1-529-192 2运输问题的表上作业法运输问题的表上作业法三、改进运输方案的办法三、改进运输方案的办法闭回路调整法闭回路调整法 方法是：选取所有负检验数最小的非基变量作为入基变量，以求尽快实方法是：选取所有负检验数最小的非基变量作为入基变量，以求尽快实现最优。现最优。 销地产地 B1 B2 B3 B4 ui A1 4(+1) 3(-1) 0 A2 3 1 (-1) +1 -1 A3 6 3 -5 vj 2 9

20、 3 10 2020311310851029471202 2运输问题的表上作业法运输问题的表上作业法 销地产地 B1 B2 B3 B4 产量 A1 5 2 7 A2 3 1 4 A3 6 3 9 销量 3 6 5 6 2020 销地产地 B1 B2 B3 B4 ui A1 0 2 5 2 0 A2 3 2 1 1 -1 A3 9 6 12 3 -5 vj 2 9 3 10 2020311310851029471上表给出的运输方案对应的检验数如下表所示：上表给出的运输方案对应的检验数如下表所示：212 2运输问题的表上作业法运输问题的表上作业法四、如何找多个最优方案四、如何找多个最优方案 识别是

21、否有多个最优解的方法和单纯形表法一样，只需看最优方案中是否识别是否有多个最优解的方法和单纯形表法一样，只需看最优方案中是否存在非基变量的检验数为零。如在本题中给出的最优运输方案中存在非基变量的检验数为零。如在本题中给出的最优运输方案中x11的检验数为的检验数为0，可知此运输问题有多个最优解。只要把，可知此运输问题有多个最优解。只要把x11作为入基变量，调整运输方案，就可作为入基变量，调整运输方案，就可得到另一个最优方案。得到另一个最优方案。 销地产地 B1 B2 B3 B4A1 (+2) 5 2(-2)A2 3(-2) 1(+2)A3 6 3 销地产地 B1 B2 B3 B4A1 2 5 A2

22、 1 3A3 6 322课堂作业课堂作业有个玩具制造商在不同的地方开设了三个工厂，从这些长将有个玩具制造商在不同的地方开设了三个工厂，从这些长将汽车零件运至设在全国各地的四个仓库，并希望运费最小，汽车零件运至设在全国各地的四个仓库，并希望运费最小，下表列出了运价及三个厂的供应量和四个仓库的需求量，请下表列出了运价及三个厂的供应量和四个仓库的需求量，请求出运费最小的方案。求出运费最小的方案。 仓库工厂1234供应量121355022241303143270销量40502535 150150233 3运输问题的应用运输问题的应用一、产销不平衡的运输问题一、产销不平衡的运输问题例例 石家庄北方研究院

23、有一、二、三三个区。每年分别需要用煤石家庄北方研究院有一、二、三三个区。每年分别需要用煤3000、1000、2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为应能力分别为1500、4000吨，运价为：吨，运价为： 由于需大于供，经院研究决定一区供应量可减少由于需大于供，经院研究决定一区供应量可减少0-300吨，二区必须满吨，二区必须满足需求量，三区供应量不少于足需求量，三区供应量不少于1500吨，试求总费用为最低的调运方案。吨，试求总费用为最低的调运方案。解：解： 根据题意，作出产销平衡与运价表：根据题意

24、，作出产销平衡与运价表：解：解： 根据题意，作出产销平衡与运价表：根据题意，作出产销平衡与运价表： 最低要求必须满足，因此把相应的虚设产地运费取为最低要求必须满足，因此把相应的虚设产地运费取为 M ，而最高要求与最低要，而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为求的差允许按需要安排，因此把相应的虚设产地运费取为 0 。对应。对应 4”的销量的销量 50 是考虑问题本身适当取的数据，根据产销平衡要求确定是考虑问题本身适当取的数据，根据产销平衡要求确定 D的产量为的产量为 50。243 3运输问题的应用运输问题的应用例例 设有设有A、B、C三个化肥厂供应三个化肥厂供应1、

25、2、3、4四个地区的农用化肥。假设效果相四个地区的农用化肥。假设效果相同，有关数据如下表，试求总费用为最低的化肥调拨方案。同，有关数据如下表，试求总费用为最低的化肥调拨方案。1234产量A1613221750B1413191560C192023-50最低需要量3070010最高需要量507030不限 1 1” 2 3 4 4” 产量 A 16 16 13 22 17 17 50 B 14 14 13 19 15 15 60 C 19 19 20 23 M M 50 D M 0 M 0 M 0 50 销量 30 20 70 30 10 50 210 210 253 3运输问题的应用运输问题的应用

26、二、生产与储存问题二、生产与储存问题例例 某厂按合同规定须于当年每个季度末分别提供某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。厂全年生产总费用为最小的决策方案。生产能力（台） 单位成本（万

27、元）一季度2510.8二季度3511.1三季度3011.0四季度1011.3263 3运输问题的应用运输问题的应用解：解： 设设 xij为第为第 i 季度生产的第季度生产的第 j 季度交货的柴油机数目，那么应满足：季度交货的柴油机数目，那么应满足： 交货：交货：x11 = 10 生产：生产：x11 + x12 + x13 + x14 25 x12 + x22 = 15 x22 + x23 + x24 35 x13 + x23 + x33 = 25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10 把第把第 i 季度生产的柴油机数目看作第季度生产的柴油

28、机数目看作第 i 个生产厂的产量；把第个生产厂的产量；把第 j 季度季度交货的柴油机数目看作第交货的柴油机数目看作第 j 个销售点的销量；成本加储存、维护等费个销售点的销量；成本加储存、维护等费用看作运费。用看作运费。 可构造下列产销平衡问题：可构造下列产销平衡问题：目标函数：目标函数：Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44 第一季度 第二季度 第三季度 第四季度 D 产量 第一季度 10.80 10.95 11.

29、10 11.25 0 25 第二季度 M 11.10 11.25 11.40 0 35 第三季度 M M 11.00 11.15 0 30 第四季度 M M M 11.30 0 10 销量 10 15 25 20 30 100 100 273 3运输问题的应用运输问题的应用例例 光明仪器厂生产电脑绣花机是以产定销的。已知光明仪器厂生产电脑绣花机是以产定销的。已知1至至6月份各月的生月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表：产能力、合同销量和单台电脑绣花机平均生产费用见下表： 已知上年末库存已知上年末库存103台绣花机，如果当月生产出来的机器当月不交货台绣花机，如果当月生产

30、出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本，则需要运到分厂库房，每台增加运输成本0.1万元万元,每台机器每月的每台机器每月的平均仓储费、维护费为平均仓储费、维护费为0.2万元。在万元。在7-8月份销售淡季，全厂停产月份销售淡季，全厂停产1个个月，因此在月，因此在6月份完成销售合同后还要留出库存月份完成销售合同后还要留出库存80台。加班生产机器台。加班生产机器每台增加成本每台增加成本1万元。问应如何安排万元。问应如何安排1-6月份的生产，可使总的生产月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？费用（包括运输、仓储、维护）最少？正常生产能力（台） 加班生产能力（台）

31、销量（台）单台费用（万元）1 月份6010104152 月份501075143 月份902011513.54 月份10040160135 月份10040103136 月份80407013.5283 3运输问题的应用运输问题的应用解：解： 这个生产存储问题可化为运输问题来做。这个生产存储问题可化为运输问题来做。 考虑：各月生产与交货分别视为产地和销地考虑：各月生产与交货分别视为产地和销地 1）1-6月份合计生产能力（包括上年末储存量）为月份合计生产能力（包括上年末储存量）为743台，销量为台，销量为707台。台。 设一假想销地销量为设一假想销地销量为36； 2）上年末库存）上年末库存103台，只

32、有仓储费和运输费，把它列为第台，只有仓储费和运输费，把它列为第0行；行； 3）6月份的需求除月份的需求除70台销量外，还要台销量外，还要80台库存，其需求应为台库存，其需求应为70+80=150台；台； 4）1-6表示表示1-6月份正常生产情况，月份正常生产情况， 1-6表示表示1-6月份加班生产情况。月份加班生产情况。产销平衡与运价表：产销平衡与运价表： 1 月 2 月 3 月 4 月 5 月 6 月 虚销地 正常产量 加班产量 0 0.3 0.5 0.7 0.9 1.1 1.3 0 103 1 15 15.3 15.5 15.7 15.9 16.1 0 60 1 16 16.3 16.5

33、16.7 6.9 17.1 0 10 2 M 14 14.3 14.5 14.7 14.9 0 50 2 M 15 15.3 15.5 15.7 15.9 0 10 3 M M 13.5 13.8 14.0 14.2 0 90 3 M M 14.5 14.8 15.0 15.2 0 20 4 M M M 13.0 13.3 13.5 0 100 4 M M M 14.0 14.3 14.5 0 40 5 M M M M 13.0 13.3 0 100 5 M M M M 14.0 14.3 0 40 6 M M M M M 13.5 0 80 6 M M M M M 14.5 0 40 销量

34、104 75 115 160 103 150 36 743 743 29三、转运问题三、转运问题 在原运输问题上增加若干转运站。运输方式有：产地在原运输问题上增加若干转运站。运输方式有：产地 转运站、转转运站、转运站运站 销地、产地销地、产地 产地、产地产地、产地 销地、销地销地、销地 转运站、销地转运站、销地 产地等产地等例例 腾飞电子仪器公司在大连和广州有两个分厂腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产生产同一种仪器，大连分厂每月生产400台，广台，广州分厂每月生产州分厂每月生产600台。该公司在上海和天津有台。该公司在上海和天津有两个销售公司负责对南京、济南

35、、南昌、青岛两个销售公司负责对南京、济南、南昌、青岛四个城市的仪器供应。另外因为大连距离青岛四个城市的仪器供应。另外因为大连距离青岛较近，公司同意大连分厂向青岛直接供货，运较近，公司同意大连分厂向青岛直接供货，运输费用如图，单位是百元。问应该如何调运仪输费用如图，单位是百元。问应该如何调运仪器，可使总运输费用最低？器，可使总运输费用最低？1 - 广州广州 2 - 大连大连 3 - 上海上海 4 - 天津天津5 - 南京南京 6 - 济南济南 7 - 南昌南昌 8 - 青岛青岛30解：设解：设 xij xij 为从为从 i i 到到 j j 的运输量，可得到有下列特点的线性规划模型：的运输量，可得到有下列特点的线性规划模型：目标函数：目标函数：Min f = Min f = 所有可能的运输费用（运输单价与运输量乘积之和）所有可能的运输费用（运输单价与运输量乘积之和）约束条件：约束条件： 对产地（发点）对产地（发点） i i ：输出量：输出量 - - 输入量输入量 = = 产量产量 对转运站（中转点）：输入量对转运站（中转点）：输入量 - - 输出