第一章引言 (1)
第二章最小费用最大流的求解原理 (2)
2.1流、割等基本概念和记号 (2)
2.1.1网络图基本定义 (2)
2.1.2可行流与最大流 (2)
2.1.3增广路 (3)
2.2最大流与最小割的求解 (4)
2.2.1求最大流和最小割的思路 (4)
2.2.2用标记法求最大流和最小割 (5)
2.3最小费用最大流的理论思想 (6)
2.3.1计算方法 (6)
2.3.2计算步骤 (7)
第三章最小费用最大流理论的两个应用 (8)
3.1出土石料运输问题 (8)
3.1.1求最大流和最小割 (9)
3.1.2最小费用最大流运输方案的设计 (10)
3.2防洪物资运输问题 (13)
3.2.1防洪物资运输模型的建立 (13)
3.2.2防洪物资运输模型的求解 (14)
3.2.3具体实例 (15)
第四章总结 (18)
参考文献 (19)
致 (20)
第一章引言
随着科学技术的发展,科学的管理越来越有必要.在经济管理、交通运输、工农业生产等经济活动中,提高经济效益是人们不可缺少的要求.而提高经济效果一种途径就是生产组织与计划的改进,即合理安排人力物力资源.要达到这样的要求,图论理论作为一种辅助人们进行科学管理的数学方法被越来越广泛的应用.
图论(Graph theory)是数学的一个分支,它以图为研究对象.图论中的图是由若干给定的点以及连接两点的线所构成的图形,这种图形通常被用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应的两个事物间具有这种关系.图论本身是应用数学的一部分.因此,图论问题曾经被历史上许多位数学家独立的研究过.关于图论的文字记载最早出现在欧拉1736年的论述中.图论研究的问题大都具有很强的实际背景.本文研究的运用图论理论优化运输方案,就是图论的应用问题的研究之一,对现实生活中的运输问题具有很好的指导意义.
本文运用图论理论对车辆流问题抽象和形式化,在线路连接有向图的基础上,建立数学模型,并运用最大流和最小割基本理论对具体问题进行求解.
在文章中首先引入流、割等概念与网络图知识点的基本定义[]4-3,对最大流与最小割基本理论和基本思想进行了概述,并结合实例对车辆流向问题抽象和形式化,建立以线路连接的有向图.在网络图中求出最大流和最小割,用最大流验证能否满足施工需要,用最小割为在割集弧上采取开拓、加宽等措施以加大容量,提高全运输线路上的流量.再着重介绍最小费用最大流的理论思想,包括
它的计算方法和算法步骤.接着把最小费用最大流理论应用到实际应用问题中,解决出土石料运输问题和防洪物资运输问题,求解给出合理的运输方案.此方法理论上严密、解题步骤直观清晰、适用性强,对公路、水路、铁路等运输系统有普遍意义.最后本文对应用图论理论优化运输方案的方法给予总结,并研究运用图论理论优化运输方案的优缺点,尝试对该结果进行推广、延展.
第二章 最小费用最大流的求解原理
2.1流、割等基本概念和记号
2.1.1网络图基本定义
我们记网络
(,,)D V A C =,
其中,V 为图中所有的顶点集i v ;A 为弧集{}()i j v ,v ;C 为各弧上容量集{}()i j c v ,v 或ij c .在V 中,s v 称为发点,t v 称为收点,其他点称为中间点.在A 上的一个函数{}()i j f f v ,v =是D 上的流,并称()i j f v ,v 为弧()i j v ,v 上的容量,简记为ij f .
2.1.2可行流与最大流
满足下列两个条件的流f 称为可行流[]5:
1. 容量限制:对于(,)i j v v A ∈,有ij ij c f ≤≤0;
2. 平衡条件:
(1) 对于发点s v :
,)(f v f f ji ij =-∑∑ (2.1.1)
其中.),(,),(,A v v A v v s i i j j i ∈∈=
(2) 对于中间点:
,0=-∑∑ji ij f f (2.1.2)
其中.),(,),(,,A v v A v v t s i i j j i ∈∈≠
(3) 对于收点t v :
,)(-f v f f ji ij =-∑∑ (2.1.3)
其中.),(,),(,A v v A v v t i i j j i ∈∈=
上述公式中j v 是与s v ,t v 相关联的任一顶点;()v f 称为可行流流量,即发点净输出方量,或者称收点净输入方量.求最大流就是求一个流ij f ,使其流量()v f 最大,且满足
⎪⎩⎪⎨⎧=-≠==-∑∑,)()(),(0
)()(t i f v t s i s i f v f f ji ij (2.1.4)
其中ij ij c f ≤≤0,()i j v ,v A ∈.
2.1.3增广路
1. 给定可行流{}ij f f =规定[]7-6:
ij ij c f =的弧为饱和弧;0=ij f 的弧为零流弧;
ij ij c f <的弧为非饱和弧;0>ij f 的弧为非零流弧.
2. 定义u 是方向自s v 到t v 的一条通路:
与u 方向一致的弧称为前向弧+u ,与u 方向相反的弧称为后向弧-u .
3. 可增广路的定义:
对于一个可行流f ,若u 满足
⎪⎩⎪⎨⎧≤<∈<≤∈++,)
(0,),()(0,),(--中各弧是非零弧即在弧中各弧是非饱和弧即在弧u c f u v v u c f u v v ij ij j i ij ij j i 则称u 为关于f 的可增广路(链),否则称为不可增广路.
2.1.4割
从网络D 中分离发点和收点的一个弧的集合称为D 的一个割.或者更直观的说割是网络D 从s v 到t v 的必经之路.因此割集中弧的容量大小对全网络的流量起到至关重要的作用.显然易得出:最大流的值不会大于最小割的容量,即
[][],)(min max ,k c f t s ≤ (2.1.5)
其中()k c 表示割集中弧的容量.
为了使全网络流量最大,必须设法利用割集中弧的全部容量,使得:
[][].)(min max ,k c f t s = (2.1.6)
2.2最大流与最小割的求解
为求解文中提出的问题,就是要在网络D 中求出最大流和最小割,从而用最大流验证能否满足施工需要,用最小割在割集弧上采取开拓、加宽等措施以加大容量,提高全运输线路上的流量.
2.2.1求最大流和最小割的思路
先假设网络D 中的任意可行流,然后自此出发设法逐渐增大流值.如果s v 到t v 中存在一条路,其所有的前向弧未饱和,所有后向弧的流具有正值,此时总有可能使这条路的前向弧的流增加一个正整数ε,所以后向弧的流减少一个ε,而且可以同时保持全部弧的流为正值且不超过弧的容量.所以这样不会破坏前面所要求的流的相容条件,同时也不会影响不属于此路的其他弧的流.但是D 自s v 到t v 的流值则增加了ε,所以总有可能逐次增加t s f ,,使得D 自s v 到t v 的全部路中任何一条路到至少有一个前向弧被饱和或一条后向弧的流为零,变为不可增广路为止.当自s v 到t v 无可增广路时,t s f ,就不再增大,即t s f ,达到最大.否则总可以按照上述
步骤继续增大t s f ,,最后求得最大流,最小割的流量满足:
[][])(min max ,k c f t s =[].8 (2.1.6)
2.2.2用标记法求最大流和最小割
确定最大流的标记法分为两个过程:一个是标记过程,二是增长过程[]7-5.
1. 标记过程:
标记过程的目的是寻找可增广路,求出最小割.
(1) 给s v 标记为(,,)s +∞,此时称s v 被标记,未检查.其他各点未标记,未检查.
其中，第一个记号是代表下标为i ,即要检查的下标.第二个记号用“+”,“-”是代表:若(,)(,)0c i j f i j ->则记之为“+”;若(,)0f j i >则记之为“-”.第三个记号则用来表示有关弧上所能增加的流量.
(2) 任选一个已标记未检查的顶点i ,若顶点j 与i 相关联,且尚未标记.则当: ① (,)i j A ∈,()()c i,j f i,j >时,将j 标上(())i,,εj +,其中
{}()min (),(,)(,)j i c i j f i j εε=-,此后称j 已标记,未检查.
② (,)j i A ∈并且(,)0f j i >时将j 上(,-,())i j ε,其中{}()min (),(,)j i f j i εε=此后称j 已标记,未检查.
③ 与i 相关联的顶点都被标记后,将i 的第二个记号“+”或“-”用一个小圆圈圈起来,称i 已标记且被检查.重复步骤2,直至收点t v 被标记或直至不再有顶点可以被标记.在后者情况下,整个算法结束,在前者的情况下,转向至增广过程.
2. 增广过程:
增广过程的目的是使沿可增广路的流量增加.
(1) 如果收点t v 的标记为()q,,ε+（其中q 是可增广路t v 前面的一个顶点的脚标)则把()t f q,v 增加ε.如果收点t v 的标记为(,-,)q ε,则把(,)t f q v 减小ε.
(2) 在增广路上调整至s v q =,则把全部标记去掉,重复标记过程和增广过程.当不再有顶点可以被标记,则此时的可行流便是最大流.同时可以找到最小割集
11(,)v v ,其中1v 为标号点集合;1v 为未标号点集合;弧集合11(,)v v 为最小割集.
2.3最小费用最大流的理论思想
运输方案设计所要考虑的不仅仅是取得最大流,而且还要设计出最小费用最大流运输方案才能达到优化的目的.
对于网络(,,)D V A C =,每条弧()i j v ,v A ∈上,除了给的ij c ,还给出了一个单位流量的费用ij b ,所谓的最小费用最大流[]9就是要求一个最大流f ,使得流的总运输费用取得最小值,即:()ij ij b f b f =∑,其中()i j v ,v A ∈.
2.3.1计算方法
求费用ij b 为权的赋权图的最短通路与网络D 中的增广路u 相对应,当沿着一条关于可行流f 的可增广路u 以1=ε调整f 得到可行流f '时,费用增量为:
--u u u u b()b()()()ij ij ij ij ij ij ij ij f f b f f b f f b b ++
⎡⎤'''-=---=-⎢⎥⎣⎦∑∑∑∑ [],10 (2.3.1)
称∑∑+-u u -
ij ij b b 为增广路u 的“费用”.
若f 是流量()v f 中所有可行流的费用最小者,而u 是关于f 的所有增广路中费用最小的增广路.那么沿着u 调整f ,即可得到f ',就是流量为()v f '的所有可行流的最小费用流.这样当f '为最大流时,即为所求的最小费用最大流.
由于0≥ij b ,所以0=f 必是流量为0的最小费用流.这样总可以从0=f 开始,去寻找关于f 的最小费用增广路.为此需要构造一个赋权有向图()w f ,它的顶点是原网络的顶点,而把D 中的每一条弧(,)i j v v 变成两个相反方向的弧(,)i j v v 和(,)j i v v ,定义()w f 的权ij w 为:
;,⎪⎩⎪⎨⎧=∞
+<=ij ij ij ij ij j i c f c f b w (2.3.2) ⎪⎩⎪⎨⎧=∞+>-=.00
,ij ij ij i j f f b w (2.3.3)
于是在D 中寻求关于f 的最小费用增广路等价于在赋权图()w f 中寻求以s v 到t v 的最短路.长度为∞的弧可以从()w f 中略去.
2.3.2计算步骤
1. 取)0(f = 0;
2. 若在第1-k 步得到最小费用流)1-k (f ,则构造赋权图(1)()k w f -;
3. 在(1)()k w f -中寻求s v 到t v 的最短路.
(1) 若不存在最短路(即最短路权为∞),则)1-k (f 就是最小费用最大流.
(2) 若存在最短路,则在原网络D 中取相对应的增广路u ,在u 上对)1-k (f 进行调整量为:
)),(min ),(min min()1()1(---+-=k ij u k ij ij u f f c ε (2.3.4)
令⎪⎪⎩⎪⎪⎨⎧∉∈-∈+=---+-.),(),(),()1()1()1()(u v v f u v v f u v v f f j i k ij j i k ij j i k ij k ij ε
ε (2.3.5)
得到新的可行流)k (f , 构造赋权有向图()()k w f ,重复上述步骤.
第三章最小费用最大流理论的两个应用
3.1出土石料运输问题
在一个新的施工工地提出需要的最大土石方量后,在图纸上设计出土石料运输线路,计算各段线路容量,然后计算总的最大流量,以验证是否满足施工需要.为了便于理论探讨.本节把某水利工地地形图上设计的运输线路简化为图1.运料线路自下游料场到坝上有三条,即左岸、中线和右岸.三条线路由于地形条件和维修费用等原因,容量也不尽相同,单位运输费用也不相等.图1中路旁第一个数字是线路容量,用
c表示,单位是万方;第二个数字是单位方量的运费,包括道路维修
ij
费、筑路费、运输费等,用
b表示,单位是百元.第三个数字是设计者认为可能的流
ij
量,用
f表示.
ij
图1 运输线路示意图
图1所示的运输图可以抽象为图2的有向网络D.
图2 有向图网络D
3.1.1求最大流和最小割
由图2进行标记过程得图3.由图3进行增广过程,增广路[]9为14(,,,)s t v v v v , 4=ε,得图4.在图4中去掉原标记,重新进行标记.按同样方法进行直至得到图5.经过分析可知图5中不再有可增广路,割集弧如图5虚线所截的饱和弧,被标记点为235(,,,)s v v v v ,未被标记点为146(,,,)t v v v v ;割为:
{}11136265(,)(,),(,),(,),(,)s t v v v v v v v v v v =, (3.1.1)
11,min(,)11421027max s t v v f ⎡⎤=+++==⎣⎦. (3.1.2)
图3 第一次标记过程图
图4第二次标记过程图
图5 最大流与最小割图
3.1.2最小费用最大流运输方案的设计
对图2取初始可行流0)0(=f ,见图6所示.构造赋权有向图(0)()w f ,如图7所示.观察可知从s v 到t v 的最短路为36(,,,)s t v v v v ,如图7中粗线所示.D 中与图7中最短路相应的增广路36(,,,)s t u v v v v =,在u 上对)1(f 进行调整,调整流量为4=ε,调整后见图8所示.再构造赋权有向图(1)()w f ,如图9所示.重复上述步骤直至(6)()w f ,如图11所示.
图6 赋权图0)0(=f
图7 赋权有向图(0)()w f
图8 赋权图)1(f ,(1)()4w f =
图9 赋权有向图(1)
w f
()
图10 赋权图)6(f,(6)
w f
()27
图11 赋权图(6)
w f
()
图11中(6)
w f已经经过六次调整,为了简单起见,中间几步省略.图中
()
(6)()w f 已经不存在s v 到t v 的最短路,所以)6(f 为最小费用最大流.每日最大上坝土石方量为27万3m ,最小费用为34,000元.
按照上述方法求出运输线路通行能力下的最大流量.若能满足施工需求量,按照此运输方案实施.若不能满足,则需要开拓和加大割集路段的容量或再增加路线.本例运输线路中影响提高运输流量的关键路段时前面所分析得到的割集路段.即料场s v 到工程指挥部1v 段,大桥3v 到坝脚6v 段,工人生活区2v 到坝脚6v 段,泄洪口施工区5v 到坝上t v 段.要提高土石运输量就要采取措施加大这些段的容量.
最优的运输方案,不仅要考虑运输量最大,还要使运输方案整体达到最优,即达到最小费用最大流[]8.本例中最小费用最大流运输方案如图10所示,最大流量为27万3m /日,最小费用为34,000元.这个运输方案比图5中计算的最大流量每日节约运输费用600元.当然执行这个方案要在原实施基础上对有关路段采取一定的措施.
3.2防洪物资运输问题
3.2.1防洪物资运输模型的建立
防洪物资运输要求在满足各水库防洪物资需求的前提下,以最低的运输费用将尽可能多的防洪物资从各仓库运送到各水库大坝,这要求考虑三个问题:
1. 满足各水库大坝的最低物资需求;
2. 满足各水库大坝的最低物资需求的前提下将尽可能多的物资从各水库运
输到各水库大坝;
3. 总运输费用最小.
为了更好地处理这三个问题,我们定义两个常量j i t ,和j i f ,.j i t ,为运送单位防
洪物资从第i 仓库到第j 水库所需要的费用;j i f ,为运送单位防洪物资从第i 仓库
到第j 水库运送防洪物资的数量.这样以总运输费用最小和物资运送量最大为目标函数,以各仓库的物资储备量、道路运输能力、各水库大坝所需要的最小物资量为约束条件构造模型如下:
⎪⎪⎩⎪⎪⎨⎧≤≥≤=∑∑∑∑==...min ,,11,,j i j i i
j i,j j i i,j m i n
j j
i j i c f q f p f t s f t Z (3.2.1)
式中i p 为第i 个仓库的物资储备数量;i q 为第j 个水库所至少需要的物资量;j i c ,为从第i 个仓库到第j 个水库的道路运输能力.第一个约束条件表示从第i 个仓库运走的所有物资数量必须小于第i 个仓库的物资储备量;第二个约束条件表示运输到第j 个水库的所有物资数量必须大于第j 个水库的至少需求量;第三个约束条件表示从第i 个仓库到第j 个水库的物资运输量必须在道路运输能力围.
3.2.2防洪物资运输模型的求解
最小费用最大流理论的求解过程[]13-12是对单一源点到单一汇点进行的,防洪物资运输问题涉及到多个储存物资的仓库(源点)和多个需求物资的水库(汇点).这就需要引进s 点作为单源,引进t 点作为单汇.规定从s 点到第i 个仓库的单位物资运输费用为0;规定从第j 个水库到t 点的道路运输能力为∞+,从第j 个水库到t 点的道路的单位运输费用为0.这样一来运输的总费用不会变,也可以应用最小费用最大流算法[]11对模型进行求解.求解步骤如下:
1. 对于初始可行流()00=f ,它是运输量为0的最小费用流;
2. 记()1-k f 为经过1-k 次调整得到的最小费用流,构造赋权有向图(-1)()k w f ;
3. 在赋权有向图(-1)()k w f 中寻求从源点s v 到汇点t v 的最小费用路(调用Floyd 算法),若不存在最小费用路,则(-1)k f 就是最小费用最大运量流,计算终止;若存在最小费用路,则此最小费用路即为原网络D 中相应的增广链u ,转入下一步;
4. 在增广链上对()1-k f 进行调整,调整量为:
(1)(1)min(min(),min())k k ij ij ij u u c f f ε+-
--=- , (3.2.2) 令(1)()(1)(1)(,)(,)(,)k ij i j k k ij ij i j k ij i j f v v u f f v v u f v v u
εε
-+---⎧+∈⎪⎪=-∈⎨⎪∉⎪⎩ . (3.2.3) 得到新的可行流)k (f , 使流值增大,令1+=k k ,返回到第(2)步骤.模型求解流程如图12所示.
图12 模型求解过程
3.2.3具体实例
桃曲坡水库、玉皇阁水库和高尔塬水库都位于渭河的支流上,古城的上游.这3座水库尤其是桃曲坡水库的防洪对的安全有着很大的影响,每逢汛期,都会有大量的防汛物资从附近的仓库运送到这3座水库,研究这3座水库的防汛物资运输问题对实际运输的有很大的指导作用.3座水库的最低防洪物资需求量为:桃曲坡,230t ;高尔塬,190t ;玉皇阁,110t .这附近有7个仓库，每个仓库的物资储备量和从某座仓库运输物资到某座水库的单位运输费用见表1.
将表1中的信息网络化,将得到图13,①,②,…⑦分别代表仓库:马栏、庙湾、瑶曲、柳林、石门关、青草坪、石柱;⑧,⑨,⑩分别代表水库桃曲坡、玉皇阁和高尔塬;每条弧上的标注为),(ij ij t c ,ij c 代表从i 到j 点的道路运输能力(即为第i 仓库的物资储备量);ij t 为从i 到j 点的单位物资运输费用.
表1 单位物资运费
图13 运输网络示意图 建立物资运输模型:
⎪⎪⎩⎪⎪⎨⎧==≤=≥=≤=∑∑∑∑==)
3,2,1,72,1( 3.2.3)(,)3,2,1()72,1(..min ,,713
1,,j i c f j q f i p f t s f t Z j i j i i
j i,j j i i,j i j j
i j i 式中Z 为总运输费用;ij f 代表道路运输流量.)72,1( =i p i 的值分别
为:90,80,110,105,95,115,95;1q ,2q ,3q 的值分别为:230,190,110;ij c ,ij t 的值见图13中的线上的标注.对模型根据最小费用最大流的求解步骤进行求解，结果见表2(表中物资运输流量表示从各仓库到各水库的防洪物资数量，单位为t ).
表2 运输计算结果
计算结果为,满足各水库最低物资需求量的运输方案,总运输费用为54650元.最小费用最大流理论可以求解出任意的对应于某个最低运输量的运输方案,即只要给定每座水库的最低需求量,就可以根据最小费用最大流理论求解出在这个最低运输量限制下的运输方案.实际中可以根据汛情的变化,随时改变每座水库的最低需求量,改变运输方案.
第一章引言 (1) 第二章最小费用最大流的求解原理 (2) 2.1流、割等基本概念和记号 (2) 2.1.1网络图基本定义 (2) 2.1.2可行流与最大流 (2) 2.1.3增广路 (3) 2.2最大流与最小割的求解 (4) 2.2.1求最大流和最小割的思路 (4) 2.2.2用标记法求最大流和最小割 (5) 2.3最小费用最大流的理论思想 (6) 2.3.1计算方法 (6) 2.3.2计算步骤 (7) 第三章最小费用最大流理论的两个应用 (8) 3.1出土石料运输问题 (8) 3.1.1求最大流和最小割 (9) 3.1.2最小费用最大流运输方案的设计 (10) 3.2防洪物资运输问题 (13) 3.2.1防洪物资运输模型的建立 (13) 3.2.2防洪物资运输模型的求解 (14) 3.2.3具体实例 (15) 第四章总结 (18) 参考文献 (19) 致 (20)
第一章引言 随着科学技术的发展,科学的管理越来越有必要.在经济管理、交通运输、工农业生产等经济活动中,提高经济效益是人们不可缺少的要求.而提高经济效果一种途径就是生产组织与计划的改进,即合理安排人力物力资源.要达到这样的要求,图论理论作为一种辅助人们进行科学管理的数学方法被越来越广泛的应用. 图论(Graph theory)是数学的一个分支,它以图为研究对象.图论中的图是由若干给定的点以及连接两点的线所构成的图形,这种图形通常被用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应的两个事物间具有这种关系.图论本身是应用数学的一部分.因此,图论问题曾经被历史上许多位数学家独立的研究过.关于图论的文字记载最早出现在欧拉1736年的论述中.图论研究的问题大都具有很强的实际背景.本文研究的运用图论理论优化运输方案,就是图论的应用问题的研究之一,对现实生活中的运输问题具有很好的指导意义. 本文运用图论理论对车辆流问题抽象和形式化,在线路连接有向图的基础上,建立数学模型,并运用最大流和最小割基本理论对具体问题进行求解. 在文章中首先引入流、割等概念与网络图知识点的基本定义[]4-3,对最大流与最小割基本理论和基本思想进行了概述,并结合实例对车辆流向问题抽象和形式化,建立以线路连接的有向图.在网络图中求出最大流和最小割,用最大流验证能否满足施工需要,用最小割为在割集弧上采取开拓、加宽等措施以加大容量,提高全运输线路上的流量.再着重介绍最小费用最大流的理论思想,包括
第三方物流运输路径优化研究--以安吉 汽车物流为例 摘要 第三方物流在汽车物流领域的迅猛发展，被誉为“未开发的经济领域”，是 继原材料节约和劳动生产率提高后，公司的第三大盈利来源。物流配送网络是一 个由各个环节和运输路线组成的一个整体，其终极目标是满足终端客户，实现全 供应链的价值。物流配送网络的合理与否，将直接关系到整个物流体系的运行效 率和成本，进而影响到企业的长期发展。 【关键词】第三方物流；优化方案；仓储作业 1研究背景及意义 当前经济发展迅速，商品流通的规模在逐渐扩大，在国内汽车行业的关税壁 垒逐渐消除、汽车行业正在寻求新的途经来提高竞争力的大背景之下，现代物流 作业规范、服务功能完善，具有便捷快速的优势，以及其一体化作业的流程使其 可以较好地迎合时代的需要，作为第三利润源成为行业关注的热点，并迅速成长 为我国国民经济中心的经济增长点，在经济全球化的大环境之中起着越来越重要 的作用。当下，在华投资的世界500强企业中有约90%的企业都选择了物流外包，足以说明第三方物流企业起到了极其重要的作用，随着经济发展的需要，汽车消 费市场对整个汽车行业提出了新的要求，主要包括在不影响总体质量的前提之下，力求低价、更新周期缩短等，各生产厂商同样面临着降低成本、抢占行业地位的 巨大压力，加之汽车制造厂也随着行业需求的提高而普遍开展订单式、JIT式等 生产方式，这些都对汽车整车和零部件物流提出了更高的要求。
21世纪，作为新兴行业之一的现代物流业迅速发展，我国的物流业迅速崛起，并在此基础上形成了一种第三方物流企业。与传统的物流公司相比，第三方物流 具有更高的专业化、更低的综合成本和更高的配送效率，是当今世界物流业发展 的必然趋势，也是社会化分工的必然趋势。因此，从现代物流的视角，结合汽车 产业的特性，对汽车的整车和零部件的运输进行研究，将会对汽车企业产生很大 的影响。 物流运输管理优化通常源于物流配送系统，物流配送系统中又包含着方方面面，在以往的文献中不难发现对其中某个点的分析，比如信息平台、运输路径等，但是针对某一具休公司，对其进行一方面的优化却是少见，论文的研究摆脱了以 往单方面研究的桎梏，进一步开拓了应用型的研究途径，从而为物流运输优化的 理论学习做出贡献。 针对安吉汽车物流公司的问题现状分别进行运输优化，使得资源得到更加合 理的利用，进而为企业更合理地安排车辆及路径优化方法的选择提供了借鉴，保 证企业的持续性成长，具有一定的实践意义。 2安吉汽车物流有限公司物流运输路径现状及问题分析 2.1安吉汽车物流公司简介 安吉汽车物流有限公司成立于2000年8月，是上汽集团所属专业从事物流 业务的全资子公司，目前员工约有10000人，以“以诚行道，以信载物”为服务 理念。2020年，安吉物流运输商品车占有率超过30%。为汽车行业提供着汽车整车、零部件物流、口岸、航运、特货、快运以及海外物流七大板块及物流策划、 信息技术等服务，并且全部实现联网运营，其合作伙伴范围极广，包含国内外主 要主机厂和零部件厂家。作为智能物流技术应用的先行者、互联网+汽车物流模 式的推动者、汽车供应链生态圈的规划和组织者，安吉汽车物流致力于智能物流 供应链的建设，打造高科技物流企业新标杆。 安吉物流目前的客户既包括上海大众、上海通用等业内业务，也包括蔚来汽车、VOLVO汽车、保时捷汽车等业外业务。
西南财经大学天府学院 2014 届 本科毕业论文（设计） 论文题目：永辉超市运输配送的优化设计 学生姓名：邓平 所在学院：西南财经大学天府学院 专业：物流管理 学号： 41002534 指导教师：柳玉寿
2014年 04 月
西南财经大学天府学院 本科毕业论文（设计）原创性及知识产权声明 本人郑重声明：所呈交的毕业论文（设计）是本人在导师的指导下取得的成果。对本论文（设计）的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。因本毕业论文（设计）引起的法律结果完全由本人承担。 本毕业论文（设计）成果归西南财经大学天府学院所有。 特此声明。 毕业论文（设计）作者签名： 作者专业：物流管理 作者学号：41002534 ________年____月____日
西南财经大学天府学院本科学生毕业论文（设计）开题报告表
摘要 随着经济发展的加快，现在企业之间的竞争更多的是体现在其成本方面的竞争。一个企业的成本降低了，那么利润空间将会大大提高，可以利用其低成本的产品降低商品价格从而获得更高的市场占有率。然而在零售行业的竞争体现上尤为明显，零售行业其商品特点体现在数量众多，商品价值小，高频繁运输。在运输与配送方面成本一直难以降低。本文通过众多前人对连锁超市的研究经验以及国内外物流运输与配送的相关技术和经验的研究，结合永辉超市近来运输与配送的失败经验和问题探索，找出一条适合永辉超市发展的运输与配送道路。运用Shapley 值法对优化方案进行论证，得出可行性报告，降低永辉超市运输与配送的成本，提高连锁超市的物流运作效率。 关键词：物流发展物流成本运输与配送连锁超市
图论的发展及其在生活中的应用 摘要主要介绍了图论的起源与发展及其生活中的若干应用，如：渡河问题、旅游推销员问题、最小生成树问题、四色问题、安排问题、中国邮递员问题。同时也涉及到了几种在图论中应用比较广泛的方法，如：最邻近法、求最小生成树的方法、求最优路线的方法等。 关键词图论生活问题应用 Graph Theory Development and the Application in Life Mathematics and applied mathematics Zhang Jiali Tutor Liu Xiuli Abstract This paper mainly introduces the origin and development of graph theory and its several applications in our life, such as: crossing river problem, traveling salesman problem, minimum spanning tree problem, four color problem，arrangement problem，Chinese postman problem．It also researches several methods that are more widely applied in graph theory, for example: the method of most neighboring,the method of solving the minimum spanning tree，the method of the best route，and so on． Key words graph theory life problem application
交通运输系统模型与优化 随着社会的发展，交通运输系统显得越来越重要，对经济、社 会的发展和人们生活产生着极大的影响。而交通运输系统的模型 与优化，则是如何提高交通运输系统的效率，降低交通运输系统 的成本、降低对环境的影响，提高整个社会的交通运输水平的问题。交通运输系统模型和优化是一个涉及到多学科的、复杂的问题，需要由交通学、运输学、控制论、计算机科学等学科的专家 和研究者共同努力。 一、交通运输系统模型 交通运输系统模型是指对现实交通运输系统的复杂性进行抽象，建立数学模型来描述交通运输系统的动态性、非线性、多变性等 特点的一种方法。交通运输系统模型可以分为静态模型和动态模 型两种。 静态模型：静态模型是指在某一个时间段内，对交通运输系统 进行全部描述和分析，忽略时间因素的变化。比如，对某一地区 的整个交通运输系统，可以建立一个该地区道路、铁路、水路、 航空等交通分支现状及设施的现状和性能参数的信息库，例如道 路长度、车道数、路段通行能力和车流量等。然后，可以利用图论、网络优化等数学方法对该数据库进行分析，如对道路进行图 示化显示、网络优化等。
动态模型：动态模型是指该模型对时间进行考虑，将交通运输 系统的变化过程分为不同时间段、阶段，然后建立相应的数学模型，来描述其中的变化过程。比如，可以对某一城市的繁忙路段，建立交通流模型，利用控制论等学科的技术，对路段的信号灯进 行协调，优化信号灯的周期和间隔时间，减少车辆的排队时间， 提高车流的通行能力。另外，还可以在公共交通上倡导共享单车、地铁等，即缓解城市交通道路交通拥堵，降低减排量，提高交通 系统的效率。 二、交通运输系统优化 交通运输系统优化是指考虑各个因素的关联，以达到最优解， 降低成本，提高效率和安全性为目标建立的科学方法。其内容包 括优化目标的制定与量化、决策变量的定义、约束条件的建立等，建立模型之后，可以采用蒙特卡洛方法、启发式算法等进行求解，以寻求局部或全局的最优解。 交通运输系统优化的实现需要得到可行的方案以及评价和改进 的步骤。一般而言，交通运输系统的优化目标可以设置为三个方面：效益最大化、成本最小化、安全性的最大化。 效益最大化：交通运输系统的效益优化是指通过提高交通运输 的价格、改善服务质量、增加运量等优化措施，来增加交通运输 的效益。比如，铁路客运优化，可以在保证客运安全的前提下，
我国连锁超市物流配送方案优化研究 电子商务巨红霞 指导教师周蓓 摘要：我国连锁超市发展令人瞩目，但连锁超市的物流配送体系建设仍然处于初级阶段，配送方式相对落后，严重制约了连锁经营规模效益的发挥。本文在对连锁超市物流配送组织方式和运行方式进行研究的基础上，结合条码技术、电子数据交换等信息化建设方面的知识，探索性地提出了我国连锁超市物流配送方式优化的思路。 关键词：连锁超市；物流配送；配送方式；条码技术；电子数据交换 The Optimization Study of Supermarket Chains' Distribution Scheme in China E-CommerceJu Hong-xia Instructor Zhou Bei Abstract: China's supermarket chains develop rapidly, but the supermarket chains' logistics system is still in its infancy, distribution methods are relatively backward,these questions hampered economies of scale seriously.Thetext analyzes logistics and distribution for supermarket chains and running mode,then it supplies the way of optimization for logistics distribution methods,combined with the construction ofinformation,such as barcode technology, electronic data interchange. Key words: Supermarket chains; Logistics distribution；Distribution methods； Barcode；EDI 随着经济的不断发展，连锁超市得到迅猛发展。国外大型连锁超市也来抢占我国零售市场，为了适应不同层次的消费需求，对连锁超市多品种、小批量、高频率快速配送商品的要求越来越高，人们开始认识到在销售业态进行变革的同时，还应在物流上进行对弈，通过先进的物流配送体系来构筑自己的核心竞争力。 1 我国连锁超市物流配送现状介绍 1．1 连锁超市概念
运输路径优化毕业论文 运输路径优化是近年来物流领域中研究的一个热点话题，随着企业物流管理的逐渐成熟和信息技术的普及，对运输路径的优化需求越来越迫切。本文旨在探讨运输路径优化的意义、现状以及优化方法。 一、运输路径优化的意义 （1）降低运输成本 优化运输路径可以有效地降低物流成本，减少人力、车辆和油耗的浪费，提高物流运输的效率。在现今市场竞争激烈的环境下，企业降低成本具有重要的战略意义。 （2）提高配送效率 优化运输路径可以缩短物流配送时间，具有更快的响应速度，能够有效地提高配送效率，提高企业的服务质量和满意度。 （3）减少环境污染 各类运输方式对环境产生影响，特别是物流行业中货车、轮船、飞机等运输方式的使用所产生的的废气等污染问题愈加突出。通过优化运输路径，可以有效的减少车辆在道路上行驶，从而达到减少汽车尾气排放的效果，保护环境，推进可持续发展。 二、运输路径优化的现状 在当前市场经济中，运输路径优化已经成为企业物流管理的必备环节。许多企业都开始关注并应用这一技术，通过不断
地实践、调整和优化，不断提高物流配送的效率和服务质量，从而降低成本，获取更高的市场份额和经济效益。 然而，运输路径优化仍存在一些问题： （1）数据不准确 由于数据采集过程中的问题，或者公司内部的数据系统存在错误，运输路径优化的结果可能会出现误差。 （2）信息不完善 优化运输路径需要大量的运输信息，这需要在流程上提高标准、完善流程，从而取得更多的运输信息。 （3）技术限制 现有的物流领域中，尚有许多技术的瓶颈未得到突破，如精准定位及交通信息的不完善。未来在物联网多层次的网络环节中信息的获取能力和性价比将会更优，在此之前，物流企业可以考虑采用现有的技术进行优化。 三、运输路径优化的方法 （1）基于网络问题的求解方法 网络问题求解通常采用路线规划、最短路径和模糊相关等方法，它可以分析策略问题和计划问题，并通过计算来确定运输路径。例如，Dijkstra算法可以用于最短路径问题的求解，支持多起点和多终点问题。 （2）基于贪心算法的求解方法 贪心算法是运输路径优化问题的一种解法，它是一种算法思想，通过不断地取最优解的方法，来求出最终的最优结果。贪心算法的重点在于在每一步都选择当前最佳的解决方案。
物流配送选址—运输路径优化问题研究 物流配送选址—运输路径优化问题研究 随着电商的不断兴起，物流配送也成为一项重要的业务。而物流配送选址和运输路径的优化问题便成为了一个重要的研究方向。本文将从物流配送选址和运输路径优化问题的定义入手，探讨其背后的原理和现实需求，并介绍一些常用的优化方法和算法。 一、物流配送选址与运输路径优化问题的定义 物流配送选址问题是指为了满足客户需求，选择合适的设施位置来实现商品的有效配送，以最小化配送成本和时效损失的问题。而运输路径优化问题则是在已经选定的物流设施的基础上，确定最优的配送路径，以最小化配送成本和时效损失。 二、物流配送选址与运输路径优化问题的原理与需求 物流配送选址和运输路径优化问题的原理是基于数学理论和运筹学原理，通过对各种因素的分析和量化，确定实现最优配送的方案。 这些因素包括配送的货物体积、重量和数量，收货人的地址和时效要求，还包括物流设施的地理位置、规模和运营成本等。这些因素的优化和调整必须要充分考虑经济、环境、社会等方面的因素，以保证所选方案的可行性和可持续性。
在现实中，物流配送选址和运输路径优化的需求非常强烈。一方面，随着电商的发展，顾客的需求变得越来越个性化，许多地方的超市和供应商需要及时地配送货物到客户手中，以获得更高的满意度和市场份额。另一方面，随着现代物流业越来越发达，物流设施和配送网点的数量也在不断增加，对运输路径的优化更加重要。对于企业而言，优化供应链所需的运输路径和配送网络越来越成为竞争的关键。因此，在物流配送领域中，如何选择最优的设施选址，建立有效的配送网络，以及怎么确定最优的运输路径，都成为了企业必须面对的问题。 三、常用的物流配送选址与运输路径优化的方法和算法 对于物流配送选址的问题，目前主要采用以下的几种方法和算法： 1. 整数规划 整数规划是一种经验丰富的数学方法，通过整数规划模型描述了决策问题所涉及的各种因素，包括经济效益、业务约束、地理限制等。通过数值计算可以找到最优化的位置和配送网络。 2. 最小生成树算法 最小生成树算法是一种常用的图论算法，用于找到一个加权无向连通图的所有结点之间满足路径最小，而且全部结点都连通的子树。在物流配送选址中，利用最小生成树算法可以找到合适的设施选址和优化的配送网络。
.毕业设计（论文）论文(设计)题目：运筹学在运输问题中的应用 姓名￥￥￥ 学院￥￥学院 专业￥￥￥ 年级￥￥￥级 指导教师￥￥￥ 2013年5 月23 日 .
目录 摘要 (1) 正文 (3) 1、前言 (3) 1.1论文研究的背景与意义 (3) 1.2运筹学在运输问题中的现状 (3) 1.3本文的主要工作及结构安排 (3) 2、预备知识 (4) 2.1运筹学的基本问题及概念 (4) 2.11运筹学简介： (4) 2.12 线性规划问题 (5) 2.13多阶段决策问题 (6) 2.14动态规划的最优化原理 (6) 2.2几种常见的运输物流问题 (7) 2.21最短路问题 (7) 2.22产销平衡的运输问题 (7) 2.23产销不平衡的运输问题 (7) 2.3解决运输问题的几种方法 (8) 2.31最小元素法 (8) 2.32伏格尔方法（Vogel） (8) 2.33表上作业法 (9) 3、经典运输问题中运筹学的应用 (9) 3.1最短路问题 (9) 3.11提出问题 (9) 3.12分析问题 (10) 3.13解决问题 (10) 3.2产销平衡的运输问题 (12) 3.21提出问题 (12) 3.22分析问题 (12) 3.23解决问题 (13) 3.24结果分析： (23) 4、总结与反思 (23) 参考文献： (24) 附录 (25)
摘要 运筹帷幄之中，决胜千里之外。运筹学作为一种科学决策的方法，早在《孙子兵法》中其思想和方法就被古人实施运用。在运输问题领域里，可以运用运筹学的知识，通过分析、计算得出最优的方案，以提高运输效率，节约运输成本，为运输企业和整个社会创造更高的经济效益。随着社会的发展和人们生活水平的提高，运输路线越来越复杂、运输企业也越来越多，在资源和人员有限的情况下，进行资源的优化配置和人员的合理分工,显得越来越重要。本文将从理论知识和实际应用这两大方面，对运输方案的优化进行全面、系统的解析，力求能让更多的人了解运筹学，应用运筹学，在提高企业效益的基础上，为运筹学的发展壮大尽一份力。 关键词：运筹学运输问题方法案例最优路径
物流供应链中的运输优化算法研究在当今全球化的商业环境中，物流供应链的运作对于企业的竞争力 至关重要。随着物流规模的不断扩大，如何提高运输效率、降低运输 成本成为物流管理中的重要课题。为了应对这一挑战，运输优化算法 成为了解决物流供应链问题的重要手段。本文将就物流供应链中的运 输优化算法进行深入研究。 一、算法概述 运输优化算法是一种通过数学模型和计算方法来解决物流运输问题 的技术手段。它通过对运输网络、运输成本和运输需求等因素进行量化，找出最优的运输方案，以实现运输效率的最大化和成本的最小化。 二、常用的运输优化算法 1. 最短路径算法 最短路径算法是一种基于图论的运输优化算法。它通过计算各个节 点之间的最短路径来确定货物的最佳运输路线。其中，Dijkstra算法和Floyd算法是最常用的最短路径算法。这些算法考虑了节点之间的距离、拓扑结构和运输成本等因素，可以准确计算出最短路径。 2. 车辆路径优化算法 在物流供应链中，配送车辆的路径安排对于运输效率和成本控制有 着重要影响。车辆路径优化算法旨在通过合理的路径规划，使得车辆 的行驶距离最短，同时满足各个客户的需求。常见的车辆路径优化算
法包括遗传算法、模拟退火算法和蚁群算法等。这些算法可以考虑各 个客户的距离、货物数量和配送时间窗等因素，得出最佳的车辆路径。 3. 货物装载优化算法 在物流供应链中，货物装载方案的合理性对于利用车辆空间、减少 运输成本具有重要意义。货物装载优化算法旨在通过合理的装载规划，最大限度地利用车辆空间，减少运输次数和车辆数目。常见的货物装 载优化算法包括模拟退火算法、禁忌搜索算法和遗传算法等。这些算 法可以通过多次优化迭代得到最佳的装载方案。 三、运输优化算法的应用 运输优化算法在物流供应链中具有广泛的应用。首先，它可以帮助 企业降低运输成本。通过运输优化算法，企业可以找到最佳的运输方案，减少运输距离和运输次数，从而降低物流成本。此外，它还可以 提高物流运输的效率。优化的运输路线和货物装载方案可以减少运输 时间，提高运输效率，保证货物及时送达。 四、运输优化算法的挑战与展望 尽管运输优化算法在物流供应链中有着广泛的应用前景，但在实际 应用中还面临一些挑战。首先，运输数据的获取和处理是一个重要的 问题。对于大规模的物流网络，需要收集和处理大量的数据，需要设 计适合的算法和技术来处理这些数据。其次，不同供应链环境下的运 输优化问题具有复杂性和多样性。如何根据具体情况选择合适的算法
关于运筹学论文范例整理分享（共5篇） 关于运筹学论文范例整理分享（共5篇） 运筹学是一门应用性很强的学科，在培养学生分析和解决问题的能力，提高学生应用和创新能力方面发挥着重大的作用.本文针对运筹学教学的特点和现今存在的问题，提出了一系列改革建议及方案，构建了理论与实践相结合的教学体系，该体系能够使学生学以致用，增强学生的实践能力，为培养应用创新型人才创造良好条件. 第1篇：新业态下民航类专业运筹学教学模式改革研究 从网络售票到微信值机，从单一的“售舱位”到运用大数据“提供综合服务”，互联网在深刻改变整个社会的同时，也在冲击传统的航空运输业，航空公司开始关注乘客的兴趣爱好、企业的运输需求，重新定义飞行。 在移动互联网时代，随着消费者对服务要求的不断提高，从关注服务本身，向客户体验和价值链两端不断延伸，服务提供方需要把标准化的服务产品或项目细化拆分，让客户选择自由结合。航空运输业要想取得竞争优势，也必须不断创新服务理念，发展新业态。 新业态是指基于不同产业间的组合、企业内部价值链和外部产业链环节的分化、融合、行业跨界整合以及嫁接信息及互联网技术所形成的新型企业、商业乃至产业的组织形态。信息技术革命、产业升级、消费者需求倒逼不断推动新业态产生和发展，也要求高校教育与人才培养模式必须进行与之相适应的变革。 运筹学是民航类专业的一门专业基础课，它是民航运营活动有关数量方面的理论，运用科学的方法来决定如何最佳地运营和设计各种系统的一门学科，对系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。通常以最优、最佳等作为决策目标，避开最劣的方案[1]。 近年来，郑州航院运筹学课程组秉承“航空为本管工结合”的办学理念，针对民航类专业的特点进行了一系列教育教学改革，达到了预期效果。本文旨在介绍《运筹学》课程的教学改革过程，研究总结
最小费用最大流模型在运输网络优化中的应用 运用图论的相关理论知识，针对物流系统中运输网络的特点，以最大限度的提高运输效率，同时以节约运输总成本为目标，提出了解决运输网络优化问题的最小费用最大流网络模型，并利用matlab编程实现，为优化物流运输网络路线提供了一种可行方法。 标签：运输网络；最小费用最大流；网络流量；matlab 0引言 运输作为现代物流过程的主要职能之一，是物流各项业务的中心活动。同时，运输产生的费用也是供应链和整个物流系统成本结构的重要组成部分。可以说，一个高效率、低成本和高反应能力的运输网络对一个成功的物流配送体系至关重要，这就使得运输网络的优化成为配送体系中一项重要的运营决策，关系到物流设计体系的成功与否。运输网络的优化主要是对运输路线的安排，即选择合理的配送路线，既能保证配送效率的最大化，又能同时使运输成本最低。 图论是运筹学中一个重要的分支，是用来描述运输网络的数学理论基础。本文基于图论的相关理论知识，针对物流运输中最小费用最大流问题，建立了基于matlab的优化数学模型，以求最大限度的提高运输效率，同时节约运输费用。 1最小费用最大流模型 1.1网络流量基本概念及定义 为了实现对网络流量最大流值和最低成本的优化，首先需明确几个基本定义： 定义1：容量—费用网络。给定一个有向图D=V，A，对任意的弧vi，vj∈A，设lij，uij为弧的运输容量上下界函数，其中0≤lij≤uij，也称uij为弧的容量；cij是弧vi，vj上单位流量的费用，称之为费用函数；对任意的节点vi∈V，称avi为节点vi的供应量或需求量，称之为供需函数，且满足vi∈Va（vi）=0。由此得到的网络称为容量—费用网络。 定义2：可行流及其总费用。设fij是给定网络N上的由节点vi到节点vj 的一个流量，且满足： f+（vi）-f-（vi）=f（vi） lij≤fij≤uij （1） 式中，f+vi=vj∈Vfij，f-vi=vj∈Vfji，分別称为流出和流入节点vi的流量，
摘要 随着科学技术和生产的发展，运筹学已渗入很多领域里，发挥了越来越重要的作用。运筹学本身也在不断发展，现在已经是一个包括好几个分支的数学部门了。比如：数学规划（又包含线性规划；非线性规划；整数规划；组合规划等）、图论、网络流、决策分析、排队论、可靠性数学理论、库存论、对策论、搜索论、模拟等等。 本文首先针对生产相同电子产品的A、B两个企业，如何在财力有限的情况下，选择合适的混合策略方案，使其得到最大的市场份额，并利用Lindo软件对此线性规划的混合策略问题进行求解、分析；然后利用Lingo软件，编程求解运输问题的案例模型，得到了最优调运方案。 关键词：线性规划、Lindo、混合策略、运输问题、Lingo
目录 摘要 (1) 最优分配问题 (3) 1.1 问题的提出 (3) 1.2 建模过程： (4) 1. 3模型的建立及求解 (6) 1.4 结果分析 (7) 运输问题 (10) 2.1问题的提出 (10) 2.2问题的分析及求解 (10) 2.3结果分析 (12) 总结 (16) 参考文献 (17)
最优分配问题 1.1 问题的提出 第十六题、某城市自来水的水源地为A、B、C三个水库，分别由地下管道把水送往该市所辖甲、乙、丙、丁四个区。唯一的例外是C水库与丁区没有地下管道。由于地理位置的差别，各水库通往各区的输水管道经过的涵洞、桥梁、加压站和净水站等设备各不相同，因此该公司对各区的引水管理费（元/千吨）各不相同（见下表）。但是对各区自来水的其他管理费均为45元/千吨，而且对各区用户都按统一标准计费，单价为90元/千吨。目前水库将临枯水期，该公司决策机构正考虑如何分配现有供水量的问题。首先，必须保证居民生活用水和某些重要机关、企业、事业单位用水的基本需求，各区的这部分用水量由下表的“最低需求”行表示，但是拥有一个独立水源的丙区这部分水量可自给自足，无须公司供给。其次，除乙区外，其他三个区都已向公司申请额外再分给如下水量（千吨/天）：甲区：20；丙区：30；丁区要求越多越好，无上限。这部分水量包含于“最高需求”行中。 该公司应如何分配供水量，才能在保障各区最低需求的基础上获利最多？并按要求分别完成下列分析： （1）水库B供应甲区的引水管理费（元/千吨）在何范围内变化时最优分配方案不变？ （2）水库A的供水量在何范围内变化时最优基不变？
---文档均为word文档，下载后可直接编辑使用亦可打印--- 摘要本文研究了航运公司有几个港口，有几条固定航线，求调配船只使船只数量最少的调配问题。类似产销不平衡问题进行假设产销地，达到产销平衡后设计航运公司的调运方案表。由沃格尔法给定初始货运调配方案，通过位势法对初始货运调配方案进行检验，由闭回路法进行方案调整，再检验及调整。基于表上作业法，最终设计出最优的货运调配方案。最后，得出最少的船只配备数。 关键词表上作业法产销平衡闭回路法沃格尔法位势法 A shipping company's freight allocation Abstract In this paper, we study the problem of a shipping company whichhas several ports and several fixed routs,and how toallocate the number of vessels to make the minimum number of vessels. Similar to the problem of production and marketing imbalance,assume the production and marketing place, and design the blank transportation scheme table of shipping company after reaching the production and marketing balance. The initial freight allocation scheme is given by the minimum element method. The initial freight allocation scheme is tested by the potential method. The scheme is adjusted by the closed-loop method, and then inspected and adjusted. Based on the table operation method, the optimal freight allocation scheme is finally designed. Finally, the minimum number of ships is obtained. Key words T able on the operating method, Balanced transportation problem, Closed loop adjustment method, Vogel's method, Potential method
数学建模论文 钢管订购和运输问题 摘要 在实际的生产建设的过程中，通常对于建设的材料，一般都是从原料生产地运输过来的。对于原材料的订购、运输，如何节约成本，减少费用，制定最优方案，是开发商们必须要解决的问题。本文就钢管订购和运输问题，建立相应的模型，研究订购运输问题的最优方案的制定。 针对问题一，通过对交通网络及管道图的分析，由于运输的路线中既有铁路又有公路，分别考虑只用铁路运输和只用公路运输情况下的最短路径，在考虑铁路公路交叉运输的情况，建立图论模型，利用MATLAB进行求解，对于管道的订购，建立规划模型，结合题中所给的数据，列出方程，利用LINGO软件进行编程求解，得到了总费用的最小值为127.8632亿元，并列出了主钢管的订购与运输计划。 针对问题二，结合问题一中的模型，利用LINGO软件进行灵敏度分析，得到了各钢厂的影子价格，通过对影子价格的分析，得到了各钢厂钢管销价与产量的上限变化对购运计划和总费用的影响，其中S5钢厂销价变化对购运计划和总费用的影响最大，S1钢厂产量变化对购运计划和总费用的影响最大。 针对问题三，由于管道为树状图，建立非线性规划模型，通过建立目标函数，利用LINGO软件求出最优解，得到到管道为树状图时，总费用的最小值为 140.6631亿元。 关键词：图论；非线性规划；最优解；LINGO
一、问题重述 钢管订购和运输问题： 1.要铺设一条1215A A A →→ →的输送天然气的主管道。 2.经筛选后可以生产这种主管道钢管的钢厂有127,, ,S S S 。 3.如图所示，图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道（假设沿管道或者原有公路，或者建有施工公路）。 4.圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位 km ） 5.为方便计算，1km 主管道钢管称为1单位钢管。 问题如下： （1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用）。 （2）请就（1）的模型分析：那个钢厂钢管的销价的变化对预购计划和中费用影响最大，那个钢厂钢管的产量的上限的变化对云购计划和总费用的影响最大，并给出相应的数字结果。 （3）如果要铺设的管道不是一条线，而是一个树形图，铁路，公路和管道构成网络，请就这种跟一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。 二、问题的分析 针对问题一，要求制定主管道的订购和运输计划，并且使得费用最小。通过对交通网络及管道图的分析，钢厂与主管道之间既存在铁路，又存在公路;对于管道的运输建立图论模型，将运输转化为求公路、铁路的最短路径问题，使得运费最小，求得最优的运输路径，结合管道订购，建立线性规划模型，运用LINGO 进行求解，进而得出总费用的最小值及订购与运输的最优方案。 针对问题二，要求对问题（1）中的模型，分析钢厂变化钢管的销价变化和产量上限的变化对购运计划和总费用的影响。根据问题一中的模型，运用LINGO 软件进行灵敏性分析，得到各变量变化的影响值。 针对问题三，要求对铁路，公路和管道构成的网络，给出一种解决办法，并按（1）中的要求给出模型和结果。由于是铁路，公路，管道构成的网络，且管道为树形图，建立非线性规划模型，通过列出目标函数和各约束条件，运用LINGO 软件进行求解。
承诺书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）：宁波工程学院 参赛队员(打印并签名) ：1. 焦跃强 2. 张爽爽 3. 王一迎 指导教师或指导教师组负责人(打印并签名)：数模组 日期： 2010 年 9 月 14 日赛区评阅编号（由赛区组委会评阅前进行编号）：
编号专用页 赛区评阅编号（由赛区组委会评阅前进行编号）： 全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：
运输问题的优化模型 摘 要 本文是一个对厂家到连锁店的供货运输问题。厂方为了能尽量减少运输成本，必然会面对货车的路线选择的问题，因此如何快速、高效地从众多可行路线中选出最优路线成为了解决此问题的关键。 问题一要求满足8个连锁店的供货需求，求运输车的线路问题。问题一的第1小题采用最短路模型里的Floyd 算法得出结果如下：91v v →的路线9v -1v ， 92v v →的路线9v -1v -2v ，93v v →的路线9v -5v -3v ，94v v →的路线9v -8v -6v -4v ，95v v →的路线9v -5v ，96v v →的路线9v -8v -6v ，97v v →的路线9v -5v -7v ，98 v v →的路线9v -8v 。第2小题在解决第1小题的基础上用哈密尔顿回路解决增加量的运输线路。结果如下：9v -1v -9v -1v -2v -1v -9v -5v -3v -5v -9v -8v -6v -4v -6v -8v -9v - 5v -9v -8v -6v -8v -9v -5v -7v -5v -9v -8v -9v -5v -7v -8v -6v -4v -2v -3v -1v -9v ，得出 最短路程为2079公里。第3小题考虑到油耗的问题，采用避圈法来求解最节油的路程，油耗公式为0.1⨯⨯车总质量车驶过的路程，求得油耗量915，路径为 9v -5v -3v -1v -2v -4v -6v -7v -8v -9v 问题二由于数据是各连锁店不定期日销售量，因此，要进行数据处理：先假设数据是服从正态分布的，然后采用卡方检验证实了我们的假设是正确的。然后用图论软件包求出最小生成树，进行分析计算，得出周平均总公里数3864公里，后改进得结果2736公里。 问题三是对整个运输问题的进一步改进和扩展，因此，在原模型的基础上考虑中转站进去，在求最短公里路之后与第二题相比较得出最优模型。 关键词：最短路模型，Floyd 算法，哈密尔顿圈，旅行商模型，最小生成树，卡方检验
石河子大学毕业论文 题目:新疆国美电器一级仓库向二级仓库配送路线优化研究院（系）：商学院商务管理系 年级： 2009级 专业：物流管理 班级： 2009（2）班 学号： 2009175390 姓名： XXX 指导教师： xxx 完成日期： 2013年3月14日
引言 (1) 第1章物流配送概述 (2) 1.1物流配送的概念 (2) 1.2 物流配送的功能 (2) 1.3 配送路线优化的意义 (3) 第2章物流配送模型及方法描述 (3) 2。1 多回路运输-VRP模型 (3) 2。2 节约里程算法 (4) 2。2。1节约里程算法的基本原理 (4) 2.2.2节约里程算法主要步骤 (5) 第3章新疆国美电器配送运作现状分析 (5) 3.1 公司简介 (5) 3.2 公司配送现状 (5) 3。3公司配送存在的问题分析 (6) 3。3。1运输成本较高 (6) 3。3.2二级仓库库存积压严重 (6) 3。3。3配送模式不合理,浪费严重 (7) 第4章新疆国美电器配送路线优化研究 (7) 4。1 建立VRP模型 (7) 4.2基于节约里程算法进行配送路线优化 (7) 4。3配送路线优化后的结果 (13) 4。4优化前与优化后比较分析 (13) 4。5结论 (15) 致谢语 (17) 参考文献 (18)
高效率合理的配送是物流系统顺利运行的保证,配送线路安排的合理与否对配送速度、成本、效益影响很大。正确合理地安排车辆的配送线路,实现合理的线路运输，可以有效地节约运输时间,增加车辆利用率,从而降低运输成本，提高企业经济效益与客户服务水平，使企业达到科学化的物流管理，这也是企业提高自身竞争力的有效途径之一。物流配送路径优化问题具有很高的计算复杂性，属于无确定解多项式难题，高效的精确算法存在的可能性不大,但可根据启发算法求得近似最优解。本文首先对物流配送进行概述，然后以新疆国美电器一级仓库向二级仓库配送方案为例，对新疆国美电器的配送现状进行分析，并运用节约里程算法对新疆国美电器的配送线路进行优化，提出最优配送方案。 ［关键词] 新疆国美电器配送节约里程算法路线优化
摘要 本文针对钢管订购和运输的一般特点和要求，建立了两个遵循题目要求的非线性规划模型。在给定钢管需求量，运输方式及价格，厂家生产量上下线，运输路线图等条件下，非线性规划模型和图论的最短路算法，从而得到线最优的钢管订购运输方案，是成本达到最小。 对于问题一，我们选取了钢管订购和运输的总费用最小作为模型的目标函数，用floyd算法分别求出铁路最短路矩阵和公路最短路矩阵，利用费用转化公式，得到两个矩阵的最小费用，将两者综合求得总体最小运输费用矩阵C(i,j)。然后用lingo求解得到最优的钢管订购运输方案。 对于问题二，我们根据要求改变钢厂钢管的销价和钢厂钢管的产量上限，然后用lingo求解，观察得到的图表，对改变以上两个条件后总运费及方案受到的影响进行分析。 考虑到问题三与问题一很相似，不同之处在于问题三中的钢管铺设路线变成了树形，因此我们仍然采用问题一的建模思路，对于特殊之处进行修改。采用图论中的floyd算法，求得总体最小运输费用矩阵C(i,j)。然后用lingo求解得到最优的钢管订购运输方案。 对问题一模型的求解得到最优钢管订购运输方案为： 总费用=1278632万元
每家厂家的生产量： 对问题二求解得： 厂家s5和厂家s6的单位钢管销售价发生变化时，对方案中总运费的影响最大。 厂家s1的钢管总产量上限变化对总费用影响最大。 对问题三的模型求解得到最优钢管订购运输方案为： 总费用=1403233万元。 每家厂家的生产量： 关键词： floyd算法非线性规划模型总体最小运输费用矩阵 一、问题重述
要铺设一条输送天然气的主管道。经筛选后可以生产这种主管道钢管的钢厂有七家。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。 为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。每个钢厂在指定期限内能生产该钢管的最大数量和钢管出厂销售1单位钢管价格均已给出。1000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。 1单位钢管的铁路运价如下表：