产销不平衡的运输问题及其求解方法

1、运筹学（第二版）刁在筠等编第3章运输问题（继续）第3节 产销不平 衡的运输 问题及其 求解方法 第4节应用举例高等教育出版社第3节产销不平衡的运输问题及其求解方法?前面所讲表上作业法，都是以产销平衡为前提条件的；但是实际问题中产销往往是不平衡的。就需要把产销不平衡的问题化成产销平衡的问题。?当产大于销m n 亍勺 乞bj Al 1?满足 ：n Dijj 1m运输问题的数学模型可写成m n?目标函数：C?XJj 入 IJ kl J=112? E)Pijsbj,# 哪-储存量，于1P n+1工ij + G+lJ=1 mn+1=工 Xij ai, J=i0 = 12 皿)xjj=bj (/ = 1,

2、2, i=li=lcij=，将其分别代入，得到当? . , n日寸当 i 二 1, 时，m nMt m n+z =_L Hcijxij= E Hcjxij + i=l 1 Z=1 1m, j=l , ?, m, j 二 n+1mZ=1n+lYxij= ai满足：m汪 Xjj=bj |=|n+1二工巧J=1由于这个模型中m n工坷=工巧+乞+1i=l J T所以这是一个产销平衡的运输问题。若当产大于销时，j 二 n+1 （实际上是储存） ，该销地总需要量为=1 j=l而在单位运价表中从各产地到假想销地的单位运价为:A =0就转化成一个产销平衡的运输问题当销大于产时可以在产销平衡表中增加一个假想的

3、产地i=m+l, 该地产量为nmDj-djj=l心 1在单位运价表上令从该假想产地到各销地的运价， “ ?=0同样可以转化为-个产销平衡的运输问题例2设有三个化肥厂 (A, B, C ) 供应四个地区 ( I, II, III, IV ) 的农用化肥。假定等量的化肥在这些地 区使用效果相同。各化肥厂年产量，各地区年需要量 及从各化肥厂到各地区 运送单位化肥的运价如表 3-25所示。试求出总的运费最 节省的化肥调拨方案。表 325求地区化工厂IIIIIIIV产量（万吨）A BC1614191313202219231715/506050取低需求（万吨）取高 需求（力吨）707003010不限?解

4、这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为 110万吨，最高需求为 无限。根据现有产量，第IV个地区每年最多能分配 到60 万吨，这样最高需求为 210 万吨，大于产量。为 了求得平衡，在产销平衡表中增加一个假想的化肥 厂 D,其年产量为 50 万吨。由于各地区的需要量包含两部分，如地区 I ,其中 30万吨是最低需求，故不 能由假想化肥厂 D 供给，令相应运价为 M （任意大正 数），而另一部分20 万吨满足或不满足均可以，因此 可以 TOC o 1-5 h z 由假想化肥厂 D 供给，按前面讲的，令相应运价为0。对凡是需求分两种情况的地区，实际上可按照两个地区看

5、待。这样可以写出这个问题的产销平衡表（表3-26） 和单位运价表（表3-27） o产销平衡表（表3-26）,单位运价表（表3-27）求地区 化工广IIIIIIIIVIV产量（万 吨）A B C DO OOO 5 65 5销量（万吨）302070301050求地区化工广9I9。 IIIIII9 9IVA161613221717B141413191515C19192023MMDM0M0M0根据表上作业法计算，可以求得这个问题的最优方案如表3-28所示求地区化工IIIIIIIIVIV产量（万 吨）A B CD302050 200301030205 O1 65 O O O O销重（万吨）3020703

6、010502104 节应用举例?由于在变量个数相等的情况下，表上作业法的计算远比单纯形法简单得多。所 以在解决实际问题时，人们常常尽可能 把某些线性规划的问题化为运输问题的 数学模型。下面介绍几个典型的例子。?例 3 某厂按合同规定须于当年每个季度末分 别提供 10, 15, 25, 20 台同一规格的柴油机。 已知该厂各季度的生产能力及生产每台柴油 机的成本如表3-29 所示。又如果生产出来的 柴 TOC o 1-5 h z 油机当季不交货的，每台每积压一个季度需储存、维护等费用 0.15万元。要求在完成合同的情况下，作出使该厂全年生产（包括储存、维护）费用最小的决策表 329季度生产能力（

7、台）单位成本（万兀）I II III IV2535301010. 811.111. 011. 3解 由于每个季度生产出来的柴油机不一定当季交货，所以设 Xi ?为第 i 季度生产的用于第 j 季度交 货的柴油机数。根据合同要求，必须满足兀= 10*12 + x22 = 15x13+ x23+ x33=25+ 兀 24 + 兀 34 + 兀 44 = 20的柴, 故又 有：兀 11 + 兀 12 + 兀 13 + 兀 1425兀 22 + 兀 23 + 兀 24 141=1护 0显然，这是一个产大于销的运输问题模型。注意到这个 问题中当ij时，Xj-O,所以 应令对应的CjM,再加上一 个假想的

8、需求D, 就可以把这个问题变成含销平衡的运输模型，并写出产销平衡表和单位运价表（合在一起， 见表3-31） o肖地 产土卜、IIIIIIIVD产量I 11 III IV10.8 M M M9510 M M11. 1011.2511.00 M11.2511.4011. 1511.30000025353010销量1015252030100?经用表上作业法求解，可得多个最优方 案，八3-32中列山最优方案之一即第 i季应生产25 台， 10 台占季交货， 15 台 II 季度交货； II5 台，用于 III 季 度交货 ;III 季度生30 台，其中 20 台于 当季交货， 10 台于 IVIV 季

9、度 生产 10 台，于当季交货。, 该厂总的生产（包括储存、维为 773万元。表 3-32季度 生产辜IIIIIIIVD产量 I101505OII510O5III20103IV103销量1015252030100例4某航运公司承担六个港口城市 A、B、C、D、F的四条固定航线的物资运输任务。已知各条航线点、终点城市及每天航班数E、的起见表3-33o航线起点城市终点城市每天航班数1234E B A DD C F B3211假定各条航线使用相同型号的船只，又各城市间 的航程天数见表3-34o从、ABCDEFA B C D E F01 2 147 710313882 30 1555141315017

10、2078517037852030又知每条船只每次装卸货的时间各需 1 天，则该 航运公司至少应配备多少条船，才能满足所有航 线的运货 需求？?解 该公司所需配备船只分两部分。?(1)载货航程需要的周转船只数。例如航 线 1, 在港口 E装货1无E-D航程17天，在D卸 货 1 天，总计 19天。每天 3航班，故 该航 线周转船只需 57 条。各条航线周转 所需船 只数见表 3-35 o表 335航线装货天 数航程天 数卸货天 数小计航班数需周转船只 数12341111173713111119 591532115710 915?以上累计共需周转船只数 91条.(2)各港口间调度所需船只数。有些港

11、口每天到达船数多于需要船数，例如港口 D,每天到达3条，需求1条; 而有些港口到达数少于需求数，例如港口 Bo各港口每天余缺船只数的计算见表 3-36o港口城市每天到达每天需求余缺数A B C DE F012301120130-1-122-31为使配备船只数最少，应做到周转的空船数为最 少。因此建立以下运输问题，其产销平衡表见 表 3-37。港口ABE每天多余船只C2D2F1每天缺少船只113单位运价表应为相应各港口之间的船只航程天数，见表3-38。港口ABEC235D141317F783用表上作业法求出空船的最优调度方案见表 339o港口ABE每天多余船只C112D112F11每天缺少船只1

12、135由表3-39知最少需周转的空船数为2X 1+13 X 1+5 X 1+17 X 1+3 X 1=40 条 这样在不考虑维修、储备等情况下， 该公司至少应配备40+91=131条船。例5在本章的例1中，如果假定?每个工厂生产的产品不一定直接发运到销售点，可以将其中几个产地集中一起运；?运往各销地的产品可以先运给其中几个销地，再 转 运给其他销地；?除产、销地之外，中间还可以有几个转运站，在 产地之间、销地之间或产地与销地间转运。已知各产地、销地、中间转运站及相互之间每吨产品的运价如表 3-40 所示，问在考虑到产销地之间直接运输 和非直接运输的各种可能方案的情况下，如何将三 个厂每天生产的

13、产品运往销售地，使总的运费最少。表 3-40项目r.匚地中间转运站销地A!A2A3T1T2T3T4B1B2B3B4产A1132143311310地A21/35/21928A33/1/2374105中T12311322846间T215/1114527转T34/23121824运T43232121/26站销B1B2311197424511/11422188地B332104222423B110856746213?解 从表3-40中看出，从A到企每吨产品 的直接运费为11元，如从A经A?运往 虽， 每吨运价为 3+4=7 元，从 A 经丁 2运 往企只 需 1+5二 6元，而从 A 到：运费兹 少的略

14、径 是从A 经 A?, B1l!jB 2,令吨产品的运费 只需 1+1+1=3 元。可见这个问题中从每个 产地到各销地之间的运输方案是很多的o 为了把这个问题仍当作一般的运输问题处理，可以这样做：? (1) 由于问题中所有产地、中间转运站、 销地都可以看作产地，又可看作销地。 因此把整个问题当作有 11 个产地和 11 个 销地的扩大的运输问题。? (2)对扩大的运输问题建立单位运价表。 方法将表 3-40 中不可能的运输方案的运价用任意大的正数M 代替。?(3) 所有中间转运站的产量等于销量。由 于运费最少时不可能出现一批物资来回倒运的现象，所以每个转运站的转运数不超 过 20 吨。可以规定

15、 Tl, T2, T3, T4 的产量 和销量均为 20吨。由于实际的转运量nmDij ， 工乂产耳j=i 心 1Xi ： , 乂订相当于一个虚构的转运站，意义就是自己运给自己。(20-X)就是每个转运站的实际转运量，音的对应运 价Cii 二 0。?(4)扩大的运输问题中原来的产地与销地 因为也有转运站的作用，所以同样在原 来产量与销量的数字上加 20 吨，即三个 厂每天糖果产量改成 27, 24, 29吨，销 量均为 20 吨；四个销售点的每天销量改 为 23, 26, 25, 26吨,产量均为 20 吨， 同时引进 ?作为松弛变量。下面写出扩大运输问题的产销平衡表与单位运价表（见表3-41）,由于这是一个产销平衡的运输问 题, 所以可以用表上作业法求