3运输问题Word
3 运输问题3.1 运输问题及其数学模型 3.2 表上作业法 3.2.1 初始方案的给定 ①最小元素法② Vogel法 3.2.2 最优性检验 ①闭回路法②位势法 3.2.3 方案的调整——闭回路法 3.3 产销不平衡的运输问题 3.4 应用举例
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
解:设由产地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)
运输问题的典型数学形式:
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)
运输问题一般用表上作业法求解,需建立表格模 型: 销地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.2 表上作业法表上作业法的步骤类似于单纯形法: (1)给出初始调运方案。 (2)检验方案是否最优,若是最优解, 则停止计算;否则转下一步。
(3)调整调运方案,得新的方案。(4)重复(2),(3)直到求出最优方案。
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个,且有数字格不构成闭回路。一般, 用最小元素法给出的方案符合这一要求。
最小元素法中的退化情况销地 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.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
两种方法确定的初始调运方案对比 最小元素法确定 的初始调运方案销地 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.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.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 )
销地 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.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.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
有检验数为负,不是最优解。
表上作业法举例(续)销地 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.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
产销不平衡的运输问题举例设有三个化肥厂供应四个地区的农用化肥。 各化肥厂年产量,各地区年需要量及从各化肥 厂到各地区运送化肥的单位运价如又表:地区 化费厂
Ⅰ 16 14 19 30 50
Ⅱ 13 13 20 70 70
Ⅲ 22 19 23 0 30
Ⅳ 17 15 10 不限
产量
A B C 最低需求 最高需求
50 60 50
试求出总运费最省的化肥调运方案。
解:三个厂的总产量为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.4 应用举例例 某厂按合同规定须于当年每个季度末分 别提供10、15、25、20台同一规格的柴油机。 已知该厂各季度的生产能力及生产每台柴油机 的成本如右表。又知如果生产出来的柴油机当 季度不交货,每台每季度的存储维护费为0.15万 元。试安排全年生产计划,使总费用最低。 季度 生产能力 单位成本 Ⅰ 25 台 10.8 万元 Ⅱ 35 台 11.1 万元 Ⅲ 30 台 11.0 万元 Ⅳ 10 台 11.3 万元
解:各季 度都产出产品, 都可看作产地; 各季度都有定 货,都可看作 销地。这是一个产 大于销的运输 问题,需增加 虚销地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
例 某航运公司承担六 个港口城市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天,问该公 司至少应配备多少条船?
解 所需船只分成两部分: 为使配备船只数尽 (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条
下载文档
热门试卷
- 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月月考生物试卷
网友关注
- 压力容器常用英语词汇39722
- 克服初中生英语听力障碍
- [宝典]商务词典
- [指南]计算机词典
- 运用听力策略,提高高中生英语听力
- 任务型教学模式在初中英语听力教学中的应用
- [精品]家具英语词汇大全
- 机械专业英语词汇
- 语言焦虑对初中英语听力理解影响研究
- 【最新word论文】论英语影视作品在英语听力“零课时”教学中的应用【英语教学专业论文】
- BBC英语听力音频打包下载地址
- 职称英语学习的好帮手
- 建筑专业英语词汇(s)
- 美国英语口语教父——新东方王强老师和网友交谈录
- ABC英语基础学习
- [精华]占星词典
- 关于提升农村初中生英语听力水平的分析.doc
- 中考英语听力突破的5大技巧
- 【最新word论文】浅谈语音知识与英语听力能力的提高【英语教学专业论文】
- 浅析中学英语听力训练
- 英语六级写作考试常用词汇---连词篇
- [精彩]司法英语词汇第四篇
- 一个人练习口语的经典办法(宁波英语口语)
- [资料]物理学英语词汇
- 专业英语词汇水利水电工程专业
- 通过元认知策略培训提高大学非英语专业学生英语听力能力的研究
- 《新编简明英语语言学教程》学习手册
- 谈英语学习
- 印尼中级汉语口语学习情况调查——以两所大学非华裔学生为例
- 提高初中英语听力教学效率的探讨
网友关注视频
- 冀教版小学数学二年级下册第二周第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
- 冀教版小学数学二年级下册第二单元《有余数除法的整理与复习》
精品推荐
- 2016-2017学年高一语文人教版必修一+模块学业水平检测试题(含答案)
- 广西钦州市高新区2017届高三11月月考政治试卷
- 浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
- 浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
- 辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
- 广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
- 广西钦州市钦州港区2017届高三11月月考政治试卷
- 广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
- 广西钦州市高新区2016-2017学年高二11月月考政治试卷
- 广西钦州市高新区2016-2017学年高一11月月考政治试卷
分类导航
- 互联网
- 电脑基础知识
- 计算机软件及应用
- 计算机硬件及网络
- 计算机应用/办公自动化
- .NET
- 数据结构与算法
- Java
- SEO
- C/C++资料
- linux/Unix相关
- 手机开发
- UML理论/建模
- 并行计算/云计算
- 嵌入式开发
- windows相关
- 软件工程
- 管理信息系统
- 开发文档
- 图形图像
- 网络与通信
- 网络信息安全
- 电子支付
- Labview
- matlab
- 网络资源
- Python
- Delphi/Perl
- 评测
- Flash/Flex
- CSS/Script
- 计算机原理
- PHP资料
- 数据挖掘与模式识别
- Web服务
- 数据库
- Visual Basic
- 电子商务
- 服务器
- 搜索引擎优化
- 存储
- 架构
- 行业软件
- 人工智能
- 计算机辅助设计
- 多媒体
- 软件测试
- 计算机硬件与维护
- 网站策划/UE
- 网页设计/UI
- 网吧管理