第七章瑜问题 §1运输模型 §2运输问题的计算机求解 §3运输问题的应用 §4*运输问题的表上作业法 管理蓦
管 理 运 筹 学 1 第七章 运 输 问 题 • §1 运 输 模 型 • §2 运输问题的计算机求解 • §3 运输问题的应用 • §4 * 运输问题的表上作业法
81输 例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3,各产地 的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所 示,问:应如何调运可使总运输费用最小? B B 产量 6 200 A 销量 150 150 200 解:产销平衡问题:总产量=总销量 设x1为从产地A运往销地B的运输量,得到下列运输量表 B B B 3 产量 200 「销量 200 linf=6x114x12+6x13+6x21+5x2+5x2 s.t.x1+x1p+x12=200 X X XO 300 x1+x21=150 X12W÷150 x13+x23=200 i=1、2;j=1、2、3) 筹些
管 理 运 筹 学 2 例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地 的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所 示，问：应如何调运可使总运输费用最小？ B1 B2 B3 产量 A1 6 4 6 200 A2 6 5 5 300 销量 150 150 200 解： 产销平衡问题：总产量 = 总销量 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表： B1 B2 B3 产量 A1 x11 x12 x13 200 A2 x21 x22 x23 300 销量 150 150 200 Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij ≥ 0 ( i = 1、2；j = 1、2、3） §1 运 输 模 型
§1运输模型 般运输模型:产销平衡 A1、A2、…、An表示某物资的m个产地;B1、B2、…、Bn表示某物质的 n个销地;S表示产地A的产量:4表示销地B的销量;c表示把物资从产地 A运往销地B的单位运价。 设x;为从产地A运往销地B;的运输量,得到下列一般运输量问题的模型: Minf=2∑c1x 1J=1 S t ∑x=S1i=1,2,…,m ∑x=dj=1,2,…,n x≥0(1=1,2,…,m;j=1,2,…,n) 变化 1)有时目标函数求最大。如求利润最大或营业额最大等; 2)当某些运输线路上的能力有限制时,在模型中直接加入约束条件 (等式或不等式约束); 3)产销不平衡时,可加入假想的产地(销大于产时)或销地(产大于 销时)。 管理蓦
管 理 运 筹 学 3 §1 运 输 模 型 • 一般运输模型：产销平衡 A1、 A2、…、 Am 表示某物资的m个产地； B1、B2、…、Bn 表示某物质的 n个销地；si 表示产地Ai的产量； dj 表示销地Bj 的销量； cij 表示把物资从产地 Ai运往销地Bj的单位运价。 • 设 xij 为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型： m n Min f = cij xij i = 1 j = 1 n s.t. xij = si i = 1,2,…,m j = 1 m xij = dj j = 1,2,…,n i = 1 xij ≥ 0 (i = 1,2,…,m ; j = 1,2,…,n) • 变化： 1）有时目标函数求最大。如求利润最大或营业额最大等； 2）当某些运输线路上的能力有限制时，在模型中直接加入约束条件 （等式或不等式约束)； 3）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于 销时）
§2运输问题的计算机求解 例2、某公司从两个产地A1、A2将物品运往三个销地B1、B2、 B3,各产地的产量、各销地的销量和各产地运往各销地每 件物品的运费如下表所示,问:应如何调运可使总运输费 用最小? BI By 66 4 B65 产量 300 300 解:增加一个销量 150 150 200 600 虚设的销地 500 运输费用为0 BI B2 B3 B 产量 300 300 销量 150 150 200 100 600 600 管理蓦 4
管 理 运 筹 学 4 §2 运输问题的计算机求解 例2、某公司从两个产地A1、A2将物品运往三个销地B1、B2、 B3，各产地的产量、各销地的销量和各产地运往各销地每 件物品的运费如下表所示，问：应如何调运可使总运输费 用最小？ 解：增加一个 虚设的销地 运输费用为0 B1 B2 B3 产量 A1 6 4 6 300 A2 6 5 5 300 销量 150 150 200 600 500 B1 B2 B3 B4 产量 A1 6 4 6 0 300 A2 6 5 5 0 300 销量 150 150 200 100 600 600
§2运榆问题的计算机求解 例3、某公司从两个产地A1、A2将物品运往三个销地B1、B2、 B3,各产地的产量、各销地的销量和各产地运往各销地每 件物品的运费如下表所示,问:应如何调运可使总运输费 用最小? BI B2 产量 66 200 解:增加 300 销量 250 200 200 500 虚设的产地 650 运输费用为0 B2 B3 B660 产量 450 200 300 150 销量 250 200 650 650 运莓
管 理 运 筹 学 5 §2 运输问题的计算机求解 例3、某公司从两个产地A1、A2将物品运往三个销地B1、B2、 B3，各产地的产量、各销地的销量和各产地运往各销地每 件物品的运费如下表所示，问：应如何调运可使总运输费 用最小？ 解：增加一个 虚设的产地 运输费用为0 B1 B2 B3 产量 A1 6 4 6 200 A2 6 5 5 300 销量 250 200 200 500 650 B1 B2 B3 产量 A1 6 4 6 200 A2 6 5 5 300 A3 0 0 0 150 销量 250 200 200 650 650
§3諭问题的应用 、产销不平衡的运输问题 例4、石家庄北方研究院有一、二、三三个区。每年分别需要用煤3000、1000、 2000吨,由河北临城、山西盂县两处煤矿负责供应,价格、质量相同。供 应能力分别为1500、4000吨,运价为: 区 三区 量 山西盂县 1.80 1.70 155 4000 河北临城 1.60 1.50 1.75 需要量 301100 2000 由于需大于供,经院研究决定一区供应量可减少0-300吨,二区必须满 足需求量,三区供应量不少于150吨,试求总费用为最低的调运方案 解:根据题意,作出产销平衡与运价表 区 区 二区 三区 山西盂县 1.80 1.80 1.70 1.55 1.55 4000 河北临城 1.60 1.60 150 175 175 1500 假想生产点 M 0 M 500 需要量 2700 300 1000 1500 500 6000 6000 这里M代表一个很大的正数,其作用是强迫相应的x31、x3、x34取值为0。 管理蓦
管 理 运 筹 学 6 §3 运输问题的应用 一、产销不平衡的运输问题 例4、石家庄北方研究院有一、二、三三个区。每年分别需要用煤3000、1000、 2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供 应能力分别为1500、4000吨，运价为： 由于需大于供，经院研究决定一区供应量可减少0--300吨，二区必须满 足需求量，三区供应量不少于1500吨，试求总费用为最低的调运方案。 解： 根据题意，作出产销平衡与运价表： 这里 M 代表一个很大的正数，其作用是强迫相应的x31、 x33、 x34取值为0。 一区 二区 三区 产量 山西盂县 1.80 1.70 1.55 4000 河北临城 1.60 1.50 1.75 1500 需要量 3000 1000 2000 一区 一区 二区 三区 三区 产量 山西盂县 1.80 1.80 1.70 1.55 1.55 4000 河北临城 1.60 1.60 1.50 1.75 1.75 1500 假想生产点 M 0 M M 0 500 需要量 2700 300 1000 1500 500 6000 6000
§3运輸问题的应用 、产销不平衡的运输问题 例5、设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相 同,有关数据如下表: 产量 16 22 B 14 13 19 15 20 最低需要量30 10 最高需要量50 30 不限 试求总费用为最低的化肥调拨方案 解:根据题意,作出产销平衡与运价表 2 产量 A 16 16 13 22 17 17 50 14 14 13191515 6 C 19 19 20 23 M M 50 50 销量 30 20 70 30 10 50 210 210 最低要求必须满足,因此把相应的虚改广地运费取为M,而最高要求与最低 要求的差允许按需要安排,因此把相应的虚设产地运费取为0。对应4”的销量 50是考虑问题本身适当取的数据,根据产销平衡要求确定D的产量为50。 运筹
管 理 运 筹 学 7 §3 运输问题的应用 一、产销不平衡的运输问题 例5、设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相 同，有关数据如下表： 试求总费用为最低的化肥调拨方案。 解： 根据题意，作出产销平衡与运价表： 最低要求必须满足，因此把相应的虚设产地运费取为 M ，而最高要求与最低 要求的差允许按需要安排，因此把相应的虚设产地运费取为 0 。对应 4”的销量 50 是考虑问题本身适当取的数据，根据产销平衡要求确定 D的产量为 50。 1 2 3 4 产量 A 16 13 22 17 50 B 14 13 19 15 60 C 19 20 23 --- 50 最低需要量 30 70 0 10 最高需要量 50 70 30 不限 1’ 1” 2 3 4’ 4” 产量 A 16 16 13 2 2 1 7 1 7 5 0 B 1 4 1 4 13 1 9 1 5 1 5 6 0 C 1 9 1 9 2 0 2 3 M M 5 0 D M 0 M 0 M 0 5 0 销量 3 0 2 0 7 0 3 0 1 0 5 0 210 210
§3运输问题的应用 二、生产与储存问题 例6、某厂按合同规定须于当年每个季度末分别提供10、15、 25、20台同一规格的柴油机。已知该厂各季度的生产能力 及生产每台柴油机的成本如右表。如果生产出来的柴油机 当季不交货,每台每积压一个季度需储存、维护等费用0.15 万元。试求在完成合同的情况下,使该厂全年生产总费用 为最小的决策方案。 生产能力(台)单位成本(万元) 季度 25 10.8 季度 35 11.1 三季度 30 11.0 四季度 10 11.3 管理蓦
管 理 运 筹 学 8 §3 运输问题的应用 二、生产与储存问题 例6、某厂按合同规定须于当年每个季度末分别提供10、15、 25、20台同一规格的柴油机。已知该厂各季度的生产能力 及生产每台柴油机的成本如右表。如果生产出来的柴油机 当季不交货，每台每积压一个季度需储存、维护等费用0.15 万元。试求在完成合同的情况下，使该厂全年生产总费用 为最小的决策方案。 生产能力（台） 单位成本（万元） 一季度 25 10.8 二季度 35 11.1 三季度 30 11.0 四季度 10 11.3
§3运輸问题的应用 解:设x1为第i季度生产的第j季度交货的柴油机数目,那么应满足 交货:x 生产:x1+x12+x13+x14≤25 12+x22 15 x2+x23+x24≤35 13 +x2+x 25 x33+x34≤30 14 24 +x34+xA=20 x4≤10 把第i季度生产的柴油机数目看作第i个生产厂的产量;把第j季度交 货的柴油机数目看作第j个销售点的销量;成本加储存、维护等费用看作 运费。可构造下列产销平衡问题: 目标函数:Minf=10.8x1+10.95x1+111x13+1125x14+111x2+1125 x23+11.4x24+110x3+11.15x34+11.3x44 第一季度「第二季度第三季度第四季度 第一季度 10.80 10.95 11.10 11.25 第二季度 M 11.10 11.25 11.40 第三季度 M 11.00 11.15 D0000 30 第四季度 M 11.30 10 销量 10 15 25 20 30 100 100 运筹
管 理 运 筹 学 9 §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 季度生产的柴油机数目看作第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.10 11.25 0 2 5 第二季度 M 11.10 11.25 11.40 0 3 5 第三季度 M M 11.00 11.15 0 3 0 第四季度 M M M 11.30 0 1 0 销量 1 0 1 5 2 5 2 0 3 0 100 100
§3运输问题的应用 二、生产与储存问题 例7、光明仪器厂生产电脑绣花机是以产定销的。已知1至6月份各月的生 产能力、合同销量和单台电脑绣花机平均生产费用见下表: 正常生产能力(台)加班生产能力(台)销量(台)单台费用(万元) 1月份 10 104 2月份 50 10 75 14 3月份 20 115 13.5 4月份 100 160 13 5月份 100 40 103 13 6月份 80 40 70 13.5 已知上年末库存103台绣花机,如果当月生产出来的机器当月不交货, 则需要运到分厂库房,每台增加运输成本0.1万元每台机器每月的平均仓 储费、维护费为0.2万元。在7-8月份销售淡季,全厂停产1个月,因此在6 月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万 元。问应如何安排1-6月份的生产,可使总的生产费用(包括运输、仓 储、维护)最少? 管理蓦 10
管 理 运 筹 学 10 §3 运输问题的应用 二、生产与储存问题 例7、光明仪器厂生产电脑绣花机是以产定销的。已知1至6月份各月的生 产能力、合同销量和单台电脑绣花机平均生产费用见下表： 已知上年末库存103台绣花机，如果当月生产出来的机器当月不交货， 则需要运到分厂库房，每台增加运输成本0.1万元,每台机器每月的平均仓 储费、维护费为0.2万元。在7--8月份销售淡季，全厂停产1个月，因此在6 月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万 元。问应如何安排1--6月份的生产，可使总的生产费用（包括运输、仓 储、维护）最少？ 正常生产能力（台） 加班生产能力（台） 销量（台） 单台费用（万元） 1 月份 60 10 104 15 2 月份 50 10 75 14 3 月份 90 20 115 13.5 4 月份 100 40 160 13 5 月份 100 40 103 13 6 月份 80 40 70 13.5