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月月考生物试卷
网友关注
- 宝典09级本科卒业论文选题
- 洱海沉积物磷形态、释放通量及其生物有效性的研究(可编辑)
- 【优秀毕业论文】关于发展上海城市公共交通的思考
- 万能轧机毕业设计
- 自学考试行政管理专业(本科)毕业论文参考题目
- 2012年本科论文题目
- 《内蒙古日报通讯》(蒙文版)历史研究
- [最新]2011届本科管帐卒业论文选题参考(1)
- 土木工程概论学习指导
- 某校本科毕业设计(论文)英文摘要撰写指南
- 公共管理系2013届毕业论文选题
- 机器人模拟仿真毕业设计
- 2010论文获奖通讯
- 模拟卷厦门大学管理学院MBA学位论文工作规范
- 人力资源管理专业毕业论文题目
- 无功补偿毕业设计
- 土木工程毕业设详细模板
- 整理版人工智能论文格局
- 2005级人力资源管理本科班毕业论文选题
- 佛山禅城工商注册[金帐本]农民专业合作社变更登记审核表
- 通讯作者
- [整理版]人工智能论文 人工智能的发展
- 塑料模毕业设计
- 财务管理专业论文参考选题大全(557个)
- 2006级物流管理专业毕业论文选题参考
- 自考本科公管专业论文题目及格式要求
- 方向四企业财务管理论文论题
- 本科行政管理毕业论文提纲
- 安师大自考本科论文封面
- 丰东路路面中修工程施工组织设计[优质文档]
网友关注视频
- 【部编】人教版语文七年级下册《逢入京使》优质课教学视频+PPT课件+教案,辽宁省
- 沪教版牛津小学英语(深圳用) 五年级下册 Unit 10
- 化学九年级下册全册同步 人教版 第22集 酸和碱的中和反应(一)
- 【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案,天津市
- 外研版英语七年级下册module3 unit1第二课时
- 【部编】人教版语文七年级下册《逢入京使》优质课教学视频+PPT课件+教案,安徽省
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 7
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 3
- 外研版英语三起6年级下册(14版)Module3 Unit1
- 8.练习八_第一课时(特等奖)(苏教版三年级上册)_T142692
- 第12章 圆锥曲线_12.7 抛物线的标准方程_第一课时(特等奖)(沪教版高二下册)_T274713
- 冀教版小学数学二年级下册第二单元《有余数除法的简单应用》
- 【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案,辽宁省
- 二年级下册数学第二课
- 外研版八年级英语下学期 Module3
- 冀教版英语四年级下册第二课
- 【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案,湖北省
- 七年级英语下册 上海牛津版 Unit3
- 人教版二年级下册数学
- 【部编】人教版语文七年级下册《老山界》优质课教学视频+PPT课件+教案,安徽省
- 二年级下册数学第三课 搭一搭⚖⚖
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 12
- 第8课 对称剪纸_第一课时(二等奖)(沪书画版二年级上册)_T3784187
- 第五单元 民族艺术的瑰宝_15. 多姿多彩的民族服饰_第二课时(市一等奖)(岭南版六年级上册)_T129830
- 北师大版数学 四年级下册 第三单元 第二节 小数点搬家
- 冀教版小学英语四年级下册Lesson2授课视频
- 每天日常投篮练习第一天森哥打卡上脚 Nike PG 2 如何调整运球跳投手感?
- 外研版英语三起5年级下册(14版)Module3 Unit1
- 《空中课堂》二年级下册 数学第一单元第1课时
- 外研版英语三起6年级下册(14版)Module3 Unit2
精品推荐
- 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
- 网吧管理