教育资源为主的文档平台

当前位置: 查字典文档网> 所有文档分类> 经管营销> 经济/市场> 3运输问题Word

3运输问题Word

上传者:顾文
|
上传时间:2017-06-03
|
次下载

3运输问题Word

  3 运输问题3.1 运输问题及其数学模型 3.2 表上作业法 3.2.1 初始方案的给定 ①最小元素法② Vogel法 3.2.2 最优性检验 ①闭回路法②位势法 3.2.3 方案的调整——闭回路法 3.3 产销不平衡的运输问题 3.4 应用举例

  3运输问题Word1

  3.1 运输问题及其模型例 某公司经销一种产品,它下设三个工厂、四个 销售部。三个工厂的日产量分别为:A1—7吨, A2—4吨,A3—9吨;各销售部的日销量分别为: B1—3吨,B2—6吨,B3—5吨,B4—6吨。各厂到 各销售部的单位产品的运价如下表。问该公司应 如何调运产品,才能完成运输任务而使运费最省。销地 产地

  B1 3 1 7

  B2 11 9 4

  B3 3 3 10

  B4 10 8 5

  A1 A2 A3

  3运输问题Word2

  解:设由产地i到销地j的运量为xij,模型为:min z= 3x11+11x12+3x13+10x14 +x21 +9x22 +2x23 +8x24 +7x31 +4x32+10x33+5x34 x11+x12+x13+x14=7 x21+x22+x23+x24=4 x31+x32+x33+x34=9 x11+x21+x31=3 x12+x22+x32=6 x13+x23+x33=5 x14+x24+x34=6 xij≥0 (i=1,2,3; j=1,2,3,4)

  3运输问题Word3

  运输问题的典型数学形式:

  min z cij xiji 1 j 1

  m

  n

  xj 1 m

  n

  ij

  a i , (i 1, 2, , m) b j , ( j 1, 2, , n)

  xi 1

  ij

  xij 0, (i 1, 2, , m;j 1, 2, , n)

  3运输问题Word4

  运输问题一般用表上作业法求解,需建立表格模 型: 销地B1 产地 B2 B3 B4 产量 7 4 9 3 6 5 6 A1 A2 A3 销量

  产销平衡表

  销地 产地

  B1 3 1 7

  B2 11 9 4

  B3 3 3 10

  B4 10 8 5

  单位运价表

  A1 A2 A3

  3运输问题Word5

  3.2 表上作业法表上作业法的步骤类似于单纯形法: (1)给出初始调运方案。 (2)检验方案是否最优,若是最优解, 则停止计算;否则转下一步。

  (3)调整调运方案,得新的方案。(4)重复(2),(3)直到求出最优方案。

  3运输问题Word6

  3.2.1 初始方案的给定 ①最小元素法产销平衡表及初始调运方案销地 B1 产地 A1 A2 A3 销量 B2 B3 B4 产量 7 4 9销地 产地

  单位运价表B1 3 1 7 B2 11 9 4 B3 3 2 10 B4 10 8 5

  3 63 6

  4 15

  336

  A1 A2 A3

  此时,z=86元。

  表上作业法要求,调运方案的有数字格必须 为m+n-1个,且有数字格不构成闭回路。一般, 用最小元素法给出的方案符合这一要求。

  3运输问题Word7

  最小元素法中的退化情况销地 B1 产地 A1 A2 A3 销量 B2 B3 B4 产量产地

  销地

  B1 3 3 1

  B2 11 9 2

  B3 3 4 10

  B4 10 8 5

  5 33

  66 5

  2 4 06

  7 4 9

  A1 A2 A3

  出现退化时,要在同时被划去的行或列中任 选一个空格填0,此格作为有数字格。

  3运输问题Word8

  3.2.1 初始方案的给定② Vogel法销地 产地

  B1 B2 3 1 7 11 9 4

  B3 3 2 10

  B4 10 8 5

  行两最小 元素之差

  A1 A2 A3列两最 小元素 之差

  2 5 2 2

  1 1 1 1

  3 3 2 2

  0007 1116 12销地 B1 产地 A1 A2 A3 销量 B2 B3 B4 产量 7 4 9

  此时,z=85元。

  33

  5 66 5

  2 1 36

  3运输问题Word9

  两种方法确定的初始调运方案对比 最小元素法确定 的初始调运方案销地 B1 产地 A1 A2 A3 销量 B2 B3 B4 产量

  Vogel法确定的

  初始调运方案销地 B1 产地

  A1 A2 A3 销量 B2 B3 B4 产量 7 4 9

  3

  63 6

  4 15

  3 7 36 4 9

  33

  5 66 5

  2 1 36

  3运输问题Word10

  3.2.2 最优性检验的方法——闭回路法根据基的定义,非基变量可以由基变量唯一地线性 表示。在表上作业法中,这种线性表示关系可以由 闭回路的形式来体现。 任一空格与有限个有效的有数字格有且只有唯一的闭回路销地 产地 A1 A2 A3

  检验数 表 B1 B2

  销地

  B3

  B4

  产地

  B1 3 1 7

  B2 11 9 4

  B3 3 2 10

  B4 10 8 5

  A1 (1) (2) 3 10 A2 1 (1) 2 (-1) A3 (12) 5 (10) 4

  若所有检验数非负则是最优 解

  3运输问题Word11

  3.2.2 最优性检验的方法——位势法x11 1 1 x12 1 x1n x21 1 1 1 1 0 1 p ij 1 0

  x22 1

  x2 n 1

  xm1

  xm 2

  xmn 1 1

  1 1 1 1 1 1 1

  0 1 ij cij Y * P ij cij (u1 , u 2 , , u m , v1 , v2 , vn ) 1 0 cij (ui v j )

  3运输问题Word12

  销地 B1 产地 A1 A2 A3 销量 B2 B3 4 1 6 3 6 5 B4 3 3 6 产量

  销地 产地

  B1 3 1 7

  B2 11 9 4

  B3 3 2 10

  B4 10 8 5

  3

  7 4 9

  A1 A2 A3

  位势表销地 B1 产地 A1 A2 A3 vj B2 B3 B4 ui

  检验数表销地 产地

  B1 1 10

  B2 2 1

  B3

  B4 -1

  10 1 (2) (9) 3 1 (8) 2 (9) 0 (-3) 4 (-2) 5 -4

  A1 A2 A3

  12

  1

  8

  2

  9

  3运输问题Word13

  3.2.3 方案调整的方法——闭回路法销地 B1 产地 A1 A2 A3 销量 B2 B3 4 1 6 3 6 5 B4 3 3 6 产量 7 4 9产地 A1 A2 A3 销量 销地 B1 B2 B3 5 0 6 3 6 5 B4 2 1 3 6 产量 7 4 9

  3

  3

  (1)从一个检验数为负数且最小的空格出发,和其它 数字格构成闭回路。 (2)在闭回路上进行运量调整,使选定空格处的运量 尽可能地增加。 (3)运量调整后,必然使某个数字格变成零。把一个 变成零的数字格抹去,得新的调运方案。

  3运输问题Word14

  3.2.4 表上作业法举例销地 B1 产地 A1 A2 A3 销量 B2 B3 4 1 6 3 6 5 B4 3 3 6 产量

  销地 产地3 7 4 9

  B1 3 1 7

  B2 11 9 4

  B3 3 2 10

  B4 10 8 5

  A1 A2 A3

  位势表销地 B1 产地 A1 A2 A3 vj B2 B3 B4 ui

  检验数表销地 产地

  B1 1 10

  B2 2 1

  B3

  B4 -1

  10 1 (2) (9) 3 1 (8) 2 (9) 0 (-3) 4 (-2) 5 -4

  A1 A2 A3

  12

  1

  8

  2

  9

  有检验数为负,不是最优解。

  3运输问题Word15

  表上作业法举例(续)销地 B1 产地 A1 A2 A3 销量 B2 B3 5 3 6 3 6 5 B4 2 1 3 6 产量

  销地 产地7 4 9

  B1 3 1 7

  B2 11 9 4

  B3 3 2 10

  B4 10 8 5

  A1 A2 A3

  位势表销地 B1 产地 A1 A2 A3 vj B2 B3 B4 10 8 5 ui

  检验数表销地 产地

  B1 0 9

  B2 2 2

  B3 1 12

  B4

  (3) (9) 3 1 (7) (1) (-2) 4 (-2)

  20

  -3

  A1 A2 A3

  1

  7

  1

  8

  检验数都非负,得最优解。

  3运输问题Word16

  3.3 产销不平衡的运输问题表上作业法是以产销平衡为

  前提的,即当实际 问题产销不平衡时,需要转化为产销平衡的运 输问题,具体来说有两种情况: (1)产大于销,即 a b 此时增加一个假想的销地n+1,该销地的销 a b ,而各产地到假想销地的单位运价 量为 一般定为0,就转化成产销平衡的运输问题。 (2)销大于产,即 a b 此时增加一个假想的产地m+1,该产地的产 量为 b a ,而假想产地到各销地的单位运价 一般定为0,就转化成产销平衡的运输问题。m n i 1 i j 1 jm n i 1 i j 1 j

  m

  n

  i 1

  i

  j 1

  j

  n

  m

  j 1

  j

  i 1

  i

  3运输问题Word17

  产销不平衡的运输问题举例设有三个化肥厂供应四个地区的农用化肥。 各化肥厂年产量,各地区年需要量及从各化肥 厂到各地区运送化肥的单位运价如又表:地区 化费厂

  Ⅰ 16 14 19 30 50

  Ⅱ 13 13 20 70 70

  Ⅲ 22 19 23 0 30

  Ⅳ 17 15 10 不限

  产量

  A B C 最低需求 最高需求

  50 60 50

  试求出总运费最省的化肥调运方案。

  3运输问题Word18

  解:三个厂的总产量为160万吨,四个地区的 最低需求为110万吨,最高需求为无限。地区Ⅳ 每年最多能分配到60万吨,这样四个地区最高 需求为210万吨,销大于产。于是,增加虚产地 D,产量为50万吨。还要把地区Ⅰ和Ⅳ的产量 分为两部分。建立如下表格模型:产地 Ⅰ′ Ⅰ″ Ⅱ Ⅲ Ⅳ′ 销地 50 A 20 10 B C 30 20 0 30 D 销量 30 20 70 30 10Ⅳ″ 产量

  销地

  50 产地 30 60 A 50 B 20 50 C 50 D

  Ⅰ′ Ⅰ″ Ⅱ Ⅲ Ⅳ′ Ⅳ″ 16 16 13 22 17 14 14 13 19 15 19 19 20 23 M M 0 M 0 M 17 15 M 0

  3运输问题Word19

  3.4 应用举例例 某厂按合同规定须于当年每个季度末分 别提供10、15、25、20台同一规格的柴油机。 已知该厂各季度的生产能力及生产每台柴油机 的成本如右表。又知如果生产出来的柴油机当 季度不交货,每台每季度的存储维护费为0.15万 元。试安排全年生产计划,使总费用最低。 季度 生产能力 单位成本 Ⅰ 25 台 10.8 万元 Ⅱ 35 台 11.1 万元 Ⅲ 30 台 11.0 万元 Ⅳ 10 台 11.3 万元

  3运输问题Word20

  解:各季 度都产出产品, 都可看作产地; 各季度都有定 货,都可看作 销地。这是一个产 大于销的运输 问题,需增加 虚销地D。表 格模型如下:

  产销平衡表销地 产地 Ⅰ Ⅱ Ⅲ Ⅳ 销量 Ⅰ Ⅱ Ⅲ Ⅳ D

  10 15 0 5 2010 15 25

  产量 25 30 35 30 10 10 10 20 30

  单位运价表销地 Ⅰ 产地 Ⅰ Ⅱ Ⅲ Ⅳ Ⅱ Ⅲ Ⅳ D

  10.8 10.95 11.10 11.25 0 M 11.10 11.25 11.40 0 M M 11.00 11.15 0 M M M 11.30 0

  3运输问题Word21

  例 某航运公司承担六 个港口城市A,B,C,D, E,F间四条航线的货物 运输任务。各航线的 起点、终点、日航班 数如下:航线 起点 终点 日航班数 1 E D 3 2 B C 2 3 A F 1 4 D B 1

  假定各航线使用的船只 相同,各城市间的航程 天数如下:到 A 从 A B C D E F 0 1 2 14 7 7 B 1 0 3

  13 8 8 C 2 3 0 15 5 5 D 14 13 15 0 17 20 E 7 8 5 17 0 3 F 7 8 5 20 3 0

  又知每条船每次装卸货时间各需1天,问该公 司至少应配备多少条船?

  3运输问题Word22

  解 所需船只分成两部分: 为使配备船只数尽 (1)载货航行需要的船只数. 可能少,建立如下运 输模型: 3*19+2*5+9+15=91条. A B E 产量 (2)各港口间调度需要的船 1 1 C 2 只数. 1 1 D 2 各港口每天船只的余 1 F 1 缺数为: 销量 1 1 3城市 到达 A 0 B 1 C 2 D 3 E 0 F 1 发出 1 2 0 1 3 0 余缺数 -1 -1 2 2 -3 1

  A C D F 2 15 7

  B 3 13 8

  E 5 17 3

  调度需要的船只数为 2+5+13+17+3=40条

  3运输问题Word23

版权声明:此文档由查字典文档网用户提供,如用于商业用途请与作者联系,查字典文档网保持最终解释权!

下载文档

热门试卷

2016年四川省内江市中考化学试卷
广西钦州市高新区2017届高三11月月考政治试卷
浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
广西钦州市钦州港区2017届高三11月月考政治试卷
广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
广西钦州市高新区2016-2017学年高二11月月考政治试卷
广西钦州市高新区2016-2017学年高一11月月考政治试卷
山东省滨州市三校2017届第一学期阶段测试初三英语试题
四川省成都七中2017届高三一诊模拟考试文科综合试卷
2017届普通高等学校招生全国统一考试模拟试题(附答案)
重庆市永川中学高2017级上期12月月考语文试题
江西宜春三中2017届高三第一学期第二次月考文科综合试题
内蒙古赤峰二中2017届高三上学期第三次月考英语试题
2017年六年级(上)数学期末考试卷
2017人教版小学英语三年级上期末笔试题
江苏省常州西藏民族中学2016-2017学年九年级思想品德第一学期第二次阶段测试试卷
重庆市九龙坡区七校2016-2017学年上期八年级素质测查(二)语文学科试题卷
江苏省无锡市钱桥中学2016年12月八年级语文阶段性测试卷
江苏省无锡市钱桥中学2016-2017学年七年级英语12月阶段检测试卷
山东省邹城市第八中学2016-2017学年八年级12月物理第4章试题(无答案)
【人教版】河北省2015-2016学年度九年级上期末语文试题卷(附答案)
四川省简阳市阳安中学2016年12月高二月考英语试卷
四川省成都龙泉中学高三上学期2016年12月月考试题文科综合能力测试
安徽省滁州中学2016—2017学年度第一学期12月月考​高三英语试卷
山东省武城县第二中学2016.12高一年级上学期第二次月考历史试题(必修一第四、五单元)
福建省四地六校联考2016-2017学年上学期第三次月考高三化学试卷
甘肃省武威第二十三中学2016—2017学年度八年级第一学期12月月考生物试卷

网友关注视频

冀教版小学数学二年级下册第二周第2课时《我们的测量》宝丰街小学庞志荣.mp4
8.对剪花样_第一课时(二等奖)(冀美版二年级上册)_T515402
第12章 圆锥曲线_12.7 抛物线的标准方程_第一课时(特等奖)(沪教版高二下册)_T274713
外研版英语七年级下册module3 unit2第二课时
七年级英语下册 上海牛津版 Unit9
沪教版牛津小学英语(深圳用) 五年级下册 Unit 12
苏科版数学七年级下册7.2《探索平行线的性质》
8.练习八_第一课时(特等奖)(苏教版三年级上册)_T142692
第五单元 民族艺术的瑰宝_16. 形形色色的民族乐器_第一课时(岭南版六年级上册)_T3751175
沪教版八年级下次数学练习册21.4(2)无理方程P19
化学九年级下册全册同步 人教版 第25集 生活中常见的盐(二)
每天日常投篮练习第一天森哥打卡上脚 Nike PG 2 如何调整运球跳投手感?
二年级下册数学第二课
【部编】人教版语文七年级下册《过松源晨炊漆公店(其五)》优质课教学视频+PPT课件+教案,辽宁省
二次函数求实际问题中的最值_第一课时(特等奖)(冀教版九年级下册)_T144339
沪教版牛津小学英语(深圳用) 四年级下册 Unit 2
苏科版数学 八年级下册 第八章第二节 可能性的大小
冀教版小学英语五年级下册lesson2教学视频(2)
3月2日小学二年级数学下册(数一数)
北师大版八年级物理下册 第六章 常见的光学仪器(二)探究凸透镜成像的规律
第五单元 民族艺术的瑰宝_16. 形形色色的民族乐器_第一课时(岭南版六年级上册)_T1406126
第4章 幂函数、指数函数和对数函数(下)_六 指数方程和对数方程_4.7 简单的指数方程_第一课时(沪教版高一下册)_T1566237
【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案,广东省
沪教版牛津小学英语(深圳用) 六年级下册 Unit 7
8 随形想象_第一课时(二等奖)(沪教版二年级上册)_T3786594
沪教版八年级下册数学练习册一次函数复习题B组(P11)
冀教版小学数学二年级下册第二周第2课时《我们的测量》宝丰街小学庞志荣
【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案,天津市
沪教版牛津小学英语(深圳用) 四年级下册 Unit 7
冀教版小学数学二年级下册第二单元《有余数除法的整理与复习》