(运筹学课件运输问题 )

《(运筹学课件运输问题 )》由会员分享，可在线阅读，更多相关《(运筹学课件运输问题 )（133页珍藏版）》请在金锄头文库上搜索。

1、运筹学,运输问题,第七章 运输问题,赵 玮,主要内容： 7.1 运输模型 7.2 运输问题的计算机求解 7.3 运输问题的应用 一、产销不平衡的运输问题 二、生产与储存问题 三、转运问题,7.4 运输问题的表上作业法 一、确定初始基本可行解 二、最优解的判别 三、改进运输方案的办法闭回路调整法 四、如何找多个最优方案,一般的运输问题就是要解决把某种产 品从若干个产地调运到若干个销地，在每 个产地的供应量与每个销地的需求量已知， 并知道各地之间的运输单价的前提下，如 何确定一个使得总的运输费用最小的方案。,7.1 运输模型,例1. 某公司从两个产地A1,A2将物品运往三个销地B1，B2，B3,各

2、产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示：,问应如何调运，使得总运输费最小？,解：我们知道A1、A2两个产地的总产量为： 200 + 300 = 500（件）；B1，B2，B3三个销地 的总销量为：150+150+200=500（件）,总产量 等于总销量这是一个产销平衡的运输问题。把 A1，A2 的产量全部分配给B1，B2，B3，正好 满足这三个销地的需要。,设xij表示从产地Ai调运到Bj的运输量（i = 1，2；j = 1，2，3），例如，x12表示从A1调运到B2的物品数量，现将安排的运输量列表如下：,从上表可写出此问题的数学模型。 满足产地产量的约束条件为：

3、 x11 + x12 + x13 = 200， x21 + x22 + x23 = 300. 满足销地销量的约束条件为： x11 + x21 = 200， x12 + x22 = 300， x13 + x23 = 200.,所以此运输问题的线性规划的模型如下： 目标函数： minf=6x11+4x12+6x13+6x21+5x22+5x23 约束条件： x11 + x12 + x13 = 200， x21 + x22 + x23 = 300， x11 + x21 = 150， x12 + x22 = 150， x13 + x23 = 200. xij0. (i = 1，2；j = 1，2，3)

4、,为了给出一般运输问题的线性规划的模 型，我们将使用以下的一些符号： A1，A2，Am表示某种物资的m个产地； B1，B2，Bn表示某种物资的n个销地； si表示产地Ai的产量； dj表示销地Bj的销量； cij表示把物资从产地Ai运到销地Bj的单 位运价。,7.1 运输模型,同样设xij表示从产地Ai运到销地Bj的 运输量，则产销平衡的运输问题的线性规 划模型如下所示： 目标函数：,7.1 运输模型,约束条件：,Xij0，对所有的i和j.,有时上述的运输问题的一般模型会发 生一些如下变化： 1.求目标函数的最大值而不是最小值 有些运输问题中，它的目标是要找出利润 最大或营业额最大的调运方案，

5、这时要求 目标函数的最大值了。,2.当某些运输线路的运输能力有一定限 制时，这时要在线性规划的模型的约束条件 上要加上运输能力限制的约束条件。例如从 A3 运到 B4的物品的数量受到运输能力的限 制，最多运送1000单位，这时只要在原来的 模型上加上约束条件x341000 即可。,3.当生产总量不等于销售总量，即 产销不平衡时，这时将通过增加一个假 想仓库或假想生产地来化成产销平衡的 问题，具体做法将在下面阐述。,7.2 运输问题的计算机求解,在上一节中我们讨论的是产销平衡的 运输问题，对于产销不平衡的运输问题， 我们可以先化为产销平衡的运输问题然后 再求解。,例2某公司从两个产地 A1，A2

6、 将物 品运往三个销地 B1，B2，B3，各产地产量 和各销地销量以及各产地运往各销地的每 件物品的运输费列表如下：,应如何组织运输，使总运输费用为最小？,例2的产销平衡表,例3某公司从两个产地A1，A2将物品运往三个销地B1，B2，B3，各销地的销量以及从产地到销地的每件物品的运输单价列表如下：,7.3 运输问题的应用,主要内容： 一、产销不平衡的运输问题 二、生产与储存问题 三、转运问题,一、产销不平衡的运输问题 例4石家庄北方研究院有三个区，即 一区、二区、三区，每年分别需要生活用 煤和取暖用煤3000、1000、2000吨，由河 北临城，山西盂县两处煤矿负责供应，这 两处煤矿的价格相同

7、，煤的质量也基本相 同，两处煤矿能供应北方研究院的单位运 价（百元/吨）见下表：,由于需大于供，经院研究平衡决定一区供应量可减少0200吨，二区需要量应全部满足，三区供应量不少于1700吨。试求总运费为最低的调运方案。,运价 百元/吨,解：根据题意，作出产销平衡与运价表如下：,例5设有三个化肥厂供应四个地区 的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量、各地区年需求量及从各化肥厂到各地区运送单位化肥的运价如下表，试求出总的运费最节省的化肥调拨方案。,输入“管理运筹学软件”即可得到最优调运方案如下（注：表中的M我们只要输入一个足够大的正数如10 000即可）,最小总运费为2

8、460万元。,二、生产与储存问题 例6. 某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如下表所示，又如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。要求在完成合同的情况下，做出使该厂全年生产（包括储存、维护）费用最小的决策。,解：由于每个季度生产出来的柴油机 不一定当月交货，故设xij为第i季度生产 的第j季度交货的柴油机的数目。,由合同规定，各季度交货数必须满足：,x11 = 10, x12 + x22 = 15, x13 + x23 + x33 = 15, x14 + x2

9、4 + x34 + x44 = 20,又各季生产的柴油机数目都不能超过各 季度的生产能力，故又有,x11 + x12 + x13 + x1425, x22 + x23 + x24 15, x33 + x34 30, x44 10.,设cij是第i季度生产的第j季度交货的每台柴油机的实际成本，cij应该是该季度单位成本加上储存、维护等费用cij值看下表。,这样此问题的目标函数可写成： minf=10.8 x11+10.95x12+11.10 x13+ 11.25x14+11.10 x22+11.25x23+ 11.40 x24+11.00 x33+11.15x34+ 11.30 x44 我们把目

10、标函数和以上的约束条件以及xij 非负限制放在一起就建立此问题的线性规划的 模型。把它输入管理运筹学软件，我们就可以 得到结果。,如果我们写出此问题的产销平衡与运 价表并输入运输问题的软件。我们也可以 立即得到结果。这时由于产大于销，我们 可以加上一个假想的需求D（实际上，不 加这个假想需求D,此软件也能自动平衡产 销，求解），并注意到当ij时，xij=0， 所以应令对应的cij = M。产销平衡与运 价表如下：,在输入数据时，关于M我们可以选择相对表中的价格足够大的正数如1 000既可，从计算机输出我们得到最优解如下所示,其最优解为773万元。,例7光明仪器厂生产电脑绣花机是以销定产 的。已

11、知1至6月份各月的生产能力、合同销量和单 台电脑绣花机平均生产费用见下表。又已知上年末 库存103台绣花机,又如果当月生产出来的机器当月 不交货，则需要运到分厂库房，每台增加运输成本 0.1万元，每台机器每月的平均仓储费、维护费为 0.2万元，在 78月份销售淡季，全厂停产1个月， 因此在6月份完成销售合同后还要留出库存 80台。 加班生产机器每台增加成本1万元。问应如何安排 16月份的生产使总的生产(包括运输、仓储、维 护）费用最少？,解：这是一个生产储存问题，可以化为运输问题来做。根据已知条件可列出产销平衡与运价表，制定此表主要考虑如下条件： 11至6月份合计生产能力（包括上年末储存量）为

12、743台，销量为707台，产大于销36台，所以在销地栏中设一个假想销地（仓库），其销量实为不安排生产的剩余生产能力。,2上年末库存103台，只有仓储费和运输费我们把它列在序号0行里。 36月份的需求除了70台销量外还要80台库存，其需求应为80+70=150台。 4产销平衡与运价表中,生产时间中的序号16表示16月份正常生产情况，序号16表示16月份加班生产情况。,用“管理运筹学软件”解得结果是 1至6月份最低总生产（包括运输、仓 储、维护）费用为8307.5万元，每月 的生产销售安排见下表。,产销平衡与运价表,最优生产销售安排,三、转运问题 所谓的转运问题是运输问题的一个扩充，在原来的运输问

13、题中的产地（也称发点）、销地（也称收点）之外还增加了中转点。,在运输问题中我们只允许物品从发点运往收点，而在转运问题中我们还允许把物品从一个发点运往另一个发点或中转点或收点，也允许把物品从一个中转点运往另一个中转点或发点或收点，也允许把物品从一个收点运往另一个收点或中转点或发点。 在每一个发点的供应量限定，每一个收点的需求一定，每两个点之间的运输单价已知的条件下如何进行调运使得总的运输费用最小。,例8腾飞电子仪器公司在大连和广州有两个分厂,大连分厂每月生产400台某种仪器，广州分厂每月生产600台某种仪器。该公司在上海与天津有两个销售公司负责对南京、济南、南昌与青岛四个城市的仪器供应，又因为大

14、连与青岛相距较近，公司也同意大连分厂直接向青岛供货，这些城市间的每台仪器的运输费用我们标在两个城市间的弧上，单位为百元，问应该如何调运仪器，使得总的运输费最低。,解：如图7-1所示，我们用 1代表在广州；2代表大连；3代表上海；4代表天津；5代表南京；6代表济南；7代表南昌；8代表青岛。 设xij表示从i到j的调运量，如x36表示从上海运到济南的仪器台数。,x13 + x14600, x23 + x24600, -x13 - x23 + x35 + x36 + x37 + x38 = 0, -x14 - x24 + x45 + x46 + x47 + x48 = 0, x35 + x45 =

15、200, x36 + x46 = 150, X37 + x47= 350, x28 + x38 + x48 = 300, xij0,对所有的i、j.,约束条件：,目标函数： minf= 2x13+3x14 +3x23+ x24 +2x35+6x36+3x37 + 6x38+4x45 +4x46+6x47+5x48+4x28,用“管理运筹学”软件求解得到结 果如下： x13=550,x14=0, x23=0, x24=150, x35=200,x36=0, x37=350,x38=0, x45=0,x46=150, x47=0, x48=0, x28=300. 最小的运输费用为4500百元。,对

16、于转运问题的一般线性规划的模型如下： 目标函数：,约束条件：,对于中转点有,对于收点j有,对发点i有,其中：,为从i点运到j点的单位运价，,为发点i的供应量，,为收点j的需求量。,我们也可以用产销平衡与运价表使用管理运筹学软件的运输问题来解决转运问题。 例9某公司有三个分厂生产某种物资，分别运往四个地区的销售公司去销售。有关分厂的产量，各销售公司的销量及运价见表所列，要求总的运费最少的调运方案。,这是一个普通的产销平衡问题，但是如果假定： 1. 每个分厂的物资不一定直接发运到销地，可以从其中几个产地击中一起运。 2. 运往各销地的物资可以先运给其中几个销地，再转运给其他销地。 3. 除产销之外, 还有几个中转站，在产地之间、销地之间或产地