论文部分内容阅读
摘要 本文以图论和优化理论为基础,综合利用最短路算法和优化模型的一般原理建立了防洪准备期和汛期的物资调运模型,解决了不同情况下的物资调运问题。本文首先通过建立该地区公路交通网的数学模型,利用Floyd算法寻求图中任意两个顶点间的最短路径,建立各企业到其管辖仓库的距离最小、仓库的总需求与企业的生产能力相匹配的双目标0-1规划模型,设计出防洪准备期的最佳调运方案。然后,将企业、仓库和储备库简化为13个顶点,采用顶点间的相互调运方式,建立非线性规划模型,得到汛期最短时间下的调运方案。
关键词最短路;多目标0-1规划;非线性规划;Floyd算法
中图分类号U116文献标识码A文章编号1673-9671-(2010)011-0090-02
1问题的重述
为完善某地区灾前准备工作,政府开展某种物资的储备及调运工作。该地有生产物资的企业三家,大小物资仓库八个,国家级储备库两个,该物资的运输成本为高等级公路2元/公里百件,普通公路1.2元/公里百件。已知各库库存及需求情况,以及生产企业,物资仓库及国家级储备库分布图,假设他们之间的物资可以通过公路运输互相调运。设计一个包含调运线路和调运量的防洪物资调运方案;如果某些路段因汛期中断,是否能用上述模型解决紧急调运问题?
2问题的分析
2.1调运方案的分析
本文先将该地区的分布图抽象为交通网得到各顶点间的距离矩阵,再利用Floyd算法来得到网络中任意两个顶点间的最短路由矩阵,建立交通网的数学模型。
关于调运有两种解决方案,方案一:由三家企业直接向各仓库调运物资;方案二:采用仓库与仓库之间调运的方式。可以证明在防洪准备阶段时间充足的情况下,前者的路径和最短,故本文考虑建立一个合理通用的企业管辖制模型指导物资调运工作。
当每天总运输量一定时,运输成本由运输距离唯一确定,故只要使各企业到其管辖的仓库的距离最小即可;为避免出现企业供求不均的情况,应保证各企业的生产能力与其管辖的仓库的需求量相匹配,即企业管辖制模型是一个最短路与最匹配的双目标规划模型。
当汛期导致两顶点间无法直接调运物资时,本文将该路段的距离等价为无穷大,同时紧急调运以时间为首要因素,如果仅仅从企业向各仓库调运,势必会增加调运时间,故本文采取仓库间互相调运的方式,将八个仓库、两个国家级储备库和三个企业简化为13个顶点,研究每天每个顶点的输入量、输出量和自身的生产量,用不同的量值来表征各顶点的特点,以此建立模型寻求尽快满足各仓库需求的最优方案。
经过分析比较,企业管辖制模型不能解决汛期紧急调用问题,原因有三:
1)前者调运方案是时间充足,以费用最小为目标,而汛期来临时,我们要研究如何调运才能使各仓库达到预测库存的时间最少;
2)二者采用的转换法则不同导致任意两顶点间的最短路径不同;
3)调运方式不同,两种方式下的某仓库第天的库存量不同。
2.2对于高等级公路和普通公路转化的分析
该地区的公路包括高等级公路和普通公路,由于汽车在不同公路上的行驶速度和运输成本不同,故为便于处理,本文运用转换法则(运输费用等价转换)对二者进行统一。其中,为某段高等级公路距离,为转换后的普通公路距离。
汛期的紧急调用采用运输时间等价转换法则,即按单位时间相等原则将任意两顶点间的高等级公路线转换为普通公路线。本文将运输成本理解为单位时间的单位效益,用运输成本反映速度关系:
3模型的建立与求解
假设汛期前的防洪调运方案暂不考虑时间问题;仓库的预测库存理解为汛期该地区对物资的需求量。
本文以公路交汇点为顶点,交汇点间的公路为边,公路区间距离为权建立网络图,见图1。
首先,写出邻接矩阵,当顶点与不相邻时,他们之间的距离。
其次,利用Floyd算法找出任意两顶点间的最短路,把各点之间的最短距离表示在图上,由路由矩阵画出以任一顶点为根结点,到其余顶点最短路径的生成树,即图1虚线表示。
图1该地区公路交通网络图
3.1双目标0-1规划模型
首先写出该交通网的距离矩阵,利用Floyd算法求出各企业到各仓库的最短路径和其对应的最短路长矩阵L(L=()n*m,n、m为企业、仓库的个数)。
第一,各企业到其管辖的仓库的距离最小:,,其中表示各企业到达其管辖仓库的总距离,表示第个企业到其管辖的仓库的最短路长之和,表示仓库和企业的隶属关系:
第二,各企业的生产能力与其管辖的仓库的总需求相匹配:, ,,表示企业生产能力的归一化,表示第个企业管辖仓库的归一化,(百件)为10个仓库的总需求。为第个企业管辖仓库的总需求,表示第个仓库的需求量,即预测库存。为便于统筹管理,调运方案考虑一个仓库只能归一个企业管理,则。
综上所述,即可得到以和为目标、、、、、为约束的双目标规划模型,本文采用两种方法求解。
方法一:把两个目标归一化加权处理为单目标。由于目标已经是无量纲单位,故只需对目标归一化,因此需要寻找一个不变的距离,这里取矩阵每列最大值之和,即(公里),,则归一化的目标为:,其中,表示偏好权值,取=0.6,用lingo求解,结果见下表1:(,为归一化需求的极差)
由表1可看出,该方案得到的归一化极差非常小,即企业的生产能力与其管辖仓库的总需求的匹配较好,运输总距离为1968公里,故当运输总量一定时,该距离确定了运输总费用,但并不能确定该距离为最小距离,还需要进一步验证。该方案充分考虑了企业生产和仓库需求的匹配问题,故较少出现一个仓库需要两个以上企业供货的情况。
方法二:将其中一个目标转化为约束。
根据实际情况,政府是在满足仓库需求的基础上追求路径最短,因此,可以把目标Q化为约束,建立单目标0-1规划模型,且,为可调精度,它可用于控制需求量比例与企业生产力比例的相似程度。取=0.38时,lingo求解得到的归一化极差比方案一大得多,即企业的生产能力与其管辖仓库的总需求的匹配欠佳,但是该方案下的运输总距离为1480公里,即当运输总量一定时,该方案的运输费用小,但同样不能确定该距离为最小距离。
比较两个方法,若重点考虑满足企业管辖区的总需求与其生产能力匹配,则选择方法一;若重点考虑总路长最小,则选择方法二。
3.2非线性规划模型
首先,求出新交通网的路由矩阵和长度矩阵以确定调运路线,写出该交通网的距离矩阵D,利用Floyd算法求出路由矩阵和长度矩阵,并依次对企业、仓库和储备库进行编号:1、2……13。
第二步,确定调运总时间,仓库和储备库的总预测库存量为9050百件,十三个点的现有库存量为8380件,而企业每天总产量为90百件,因此需要三个企业至少生产8天才能使各仓库的库存达到预测库存量,即调运时间。
本文假设一次调运的运输能力无限,即一天只做一次统筹调运,各点间互相调运,彼此调运互不影响,故一天的调运时间是由花费时间最长的两点决定,即调运路程最小:,是第个顶点到第个顶点的最短路,表示第天、第个顶点向第个顶点调运物资。
第天第个顶点的库存量为,其中,表示第天、第个顶点向第个顶点的调运量,表示第天、第个顶点的生产量。
13个顶点的库存要求有所差异:
1)企业的库存约束为:第个顶点的库存量应满足:,其中表示第天第个顶点的最大库存要求;
2)仓库与储备库的库存约束为:第天第个顶点的库存量应满足:;,其中,,分别表示第天第个顶点的最低库存量、预测库存量、最高库存量。
本文理解预测库存量是根据气象预报及历史条件预测出如果该地区发生洪涝时需要的最少库存量,因此汛期时调运结束的条件是各仓库达到预测库存量。
3)各顶点的调运量的约束:
Step1:各顶点给其他顶点的调运总量应小于它的当前库存量,即:;
Step2:由于要重点保护国家级储备库,应让国家级储备库只接受物资,不调出物资,即:,其中,。
Step3:由于企业只负责输出物资,没有输入物资,故:,其中,。
综上即可确定汛期紧急调运物资的非线性规划模型。
目标函数是一个最大最小的非线性函数,这用lingo是非常难解的,因此,本文考虑将该问题转化成对应的线性规划模型。由于最大的调运时间最小,其它参与调运的各顶点间的调运时间将会更小,那么它们调运时间的总和也是最小,如果不考虑时间的重叠,运输时间总和最小就意味着总路程最小。目标函数可以等价为下面的线性函数:,这时用lingo求解可以得到8天具体的调运方案。
4模型的评价
企业管辖制的优点是便于操作,各企业只需满足自己辖区内仓库的需求即可。但是,这种方案建立的是双目标规划模型,只能接近最优解,且通过不同处理方法得到解是不同的,到底选择那个解法的最优解视具体情况而定。另一方面,该方案规定各企业的调运相互独立导致解决方法不灵活,而事实上如果一个管辖区缺货,可以从其它企业调用。
非线性规划模型简单,便于移植,把企业、仓库和储备库同等看待为13个顶点,将他们的特性用不同的参数来表征,使模型变得简单,易于处理,但不易于求解,虽然将目标转化为线性目标,事实上并没有理论根据,缺乏说服力。
参考文献
[1]姜启源.数学模型[M].北京:高等教育出版社,1999.
[2]谢金星M薛毅.优化建模与LINDO/LINGO软件[M].北京:清华大学出版社,2005.
[3]韩中庚.实用运筹学[M].北京:清华大学出版社,2007.
[4]韩中庚.数学建模竞赛:获奖论文精选与点评[M].北京:科学出版社,2007.
[5]徐俊明.图论及其应用[M].合肥.中国科学技术大学出版社,2004.
[6]求是科技.MATLAB从入门到精通[M].北京.人民邮电出版社,2006.
[7]张伯生.运筹学[M].北京.科学出版社,2008.
关键词最短路;多目标0-1规划;非线性规划;Floyd算法
中图分类号U116文献标识码A文章编号1673-9671-(2010)011-0090-02
1问题的重述
为完善某地区灾前准备工作,政府开展某种物资的储备及调运工作。该地有生产物资的企业三家,大小物资仓库八个,国家级储备库两个,该物资的运输成本为高等级公路2元/公里百件,普通公路1.2元/公里百件。已知各库库存及需求情况,以及生产企业,物资仓库及国家级储备库分布图,假设他们之间的物资可以通过公路运输互相调运。设计一个包含调运线路和调运量的防洪物资调运方案;如果某些路段因汛期中断,是否能用上述模型解决紧急调运问题?
2问题的分析
2.1调运方案的分析
本文先将该地区的分布图抽象为交通网得到各顶点间的距离矩阵,再利用Floyd算法来得到网络中任意两个顶点间的最短路由矩阵,建立交通网的数学模型。
关于调运有两种解决方案,方案一:由三家企业直接向各仓库调运物资;方案二:采用仓库与仓库之间调运的方式。可以证明在防洪准备阶段时间充足的情况下,前者的路径和最短,故本文考虑建立一个合理通用的企业管辖制模型指导物资调运工作。
当每天总运输量一定时,运输成本由运输距离唯一确定,故只要使各企业到其管辖的仓库的距离最小即可;为避免出现企业供求不均的情况,应保证各企业的生产能力与其管辖的仓库的需求量相匹配,即企业管辖制模型是一个最短路与最匹配的双目标规划模型。
当汛期导致两顶点间无法直接调运物资时,本文将该路段的距离等价为无穷大,同时紧急调运以时间为首要因素,如果仅仅从企业向各仓库调运,势必会增加调运时间,故本文采取仓库间互相调运的方式,将八个仓库、两个国家级储备库和三个企业简化为13个顶点,研究每天每个顶点的输入量、输出量和自身的生产量,用不同的量值来表征各顶点的特点,以此建立模型寻求尽快满足各仓库需求的最优方案。
经过分析比较,企业管辖制模型不能解决汛期紧急调用问题,原因有三:
1)前者调运方案是时间充足,以费用最小为目标,而汛期来临时,我们要研究如何调运才能使各仓库达到预测库存的时间最少;
2)二者采用的转换法则不同导致任意两顶点间的最短路径不同;
3)调运方式不同,两种方式下的某仓库第天的库存量不同。
2.2对于高等级公路和普通公路转化的分析
该地区的公路包括高等级公路和普通公路,由于汽车在不同公路上的行驶速度和运输成本不同,故为便于处理,本文运用转换法则(运输费用等价转换)对二者进行统一。其中,为某段高等级公路距离,为转换后的普通公路距离。
汛期的紧急调用采用运输时间等价转换法则,即按单位时间相等原则将任意两顶点间的高等级公路线转换为普通公路线。本文将运输成本理解为单位时间的单位效益,用运输成本反映速度关系:
3模型的建立与求解
假设汛期前的防洪调运方案暂不考虑时间问题;仓库的预测库存理解为汛期该地区对物资的需求量。
本文以公路交汇点为顶点,交汇点间的公路为边,公路区间距离为权建立网络图,见图1。
首先,写出邻接矩阵,当顶点与不相邻时,他们之间的距离。
其次,利用Floyd算法找出任意两顶点间的最短路,把各点之间的最短距离表示在图上,由路由矩阵画出以任一顶点为根结点,到其余顶点最短路径的生成树,即图1虚线表示。
图1该地区公路交通网络图
3.1双目标0-1规划模型
首先写出该交通网的距离矩阵,利用Floyd算法求出各企业到各仓库的最短路径和其对应的最短路长矩阵L(L=()n*m,n、m为企业、仓库的个数)。
第一,各企业到其管辖的仓库的距离最小:,,其中表示各企业到达其管辖仓库的总距离,表示第个企业到其管辖的仓库的最短路长之和,表示仓库和企业的隶属关系:
第二,各企业的生产能力与其管辖的仓库的总需求相匹配:, ,,表示企业生产能力的归一化,表示第个企业管辖仓库的归一化,(百件)为10个仓库的总需求。为第个企业管辖仓库的总需求,表示第个仓库的需求量,即预测库存。为便于统筹管理,调运方案考虑一个仓库只能归一个企业管理,则。
综上所述,即可得到以和为目标、、、、、为约束的双目标规划模型,本文采用两种方法求解。
方法一:把两个目标归一化加权处理为单目标。由于目标已经是无量纲单位,故只需对目标归一化,因此需要寻找一个不变的距离,这里取矩阵每列最大值之和,即(公里),,则归一化的目标为:,其中,表示偏好权值,取=0.6,用lingo求解,结果见下表1:(,为归一化需求的极差)
由表1可看出,该方案得到的归一化极差非常小,即企业的生产能力与其管辖仓库的总需求的匹配较好,运输总距离为1968公里,故当运输总量一定时,该距离确定了运输总费用,但并不能确定该距离为最小距离,还需要进一步验证。该方案充分考虑了企业生产和仓库需求的匹配问题,故较少出现一个仓库需要两个以上企业供货的情况。
方法二:将其中一个目标转化为约束。
根据实际情况,政府是在满足仓库需求的基础上追求路径最短,因此,可以把目标Q化为约束,建立单目标0-1规划模型,且,为可调精度,它可用于控制需求量比例与企业生产力比例的相似程度。取=0.38时,lingo求解得到的归一化极差比方案一大得多,即企业的生产能力与其管辖仓库的总需求的匹配欠佳,但是该方案下的运输总距离为1480公里,即当运输总量一定时,该方案的运输费用小,但同样不能确定该距离为最小距离。
比较两个方法,若重点考虑满足企业管辖区的总需求与其生产能力匹配,则选择方法一;若重点考虑总路长最小,则选择方法二。
3.2非线性规划模型
首先,求出新交通网的路由矩阵和长度矩阵以确定调运路线,写出该交通网的距离矩阵D,利用Floyd算法求出路由矩阵和长度矩阵,并依次对企业、仓库和储备库进行编号:1、2……13。
第二步,确定调运总时间,仓库和储备库的总预测库存量为9050百件,十三个点的现有库存量为8380件,而企业每天总产量为90百件,因此需要三个企业至少生产8天才能使各仓库的库存达到预测库存量,即调运时间。
本文假设一次调运的运输能力无限,即一天只做一次统筹调运,各点间互相调运,彼此调运互不影响,故一天的调运时间是由花费时间最长的两点决定,即调运路程最小:,是第个顶点到第个顶点的最短路,表示第天、第个顶点向第个顶点调运物资。
第天第个顶点的库存量为,其中,表示第天、第个顶点向第个顶点的调运量,表示第天、第个顶点的生产量。
13个顶点的库存要求有所差异:
1)企业的库存约束为:第个顶点的库存量应满足:,其中表示第天第个顶点的最大库存要求;
2)仓库与储备库的库存约束为:第天第个顶点的库存量应满足:;,其中,,分别表示第天第个顶点的最低库存量、预测库存量、最高库存量。
本文理解预测库存量是根据气象预报及历史条件预测出如果该地区发生洪涝时需要的最少库存量,因此汛期时调运结束的条件是各仓库达到预测库存量。
3)各顶点的调运量的约束:
Step1:各顶点给其他顶点的调运总量应小于它的当前库存量,即:;
Step2:由于要重点保护国家级储备库,应让国家级储备库只接受物资,不调出物资,即:,其中,。
Step3:由于企业只负责输出物资,没有输入物资,故:,其中,。
综上即可确定汛期紧急调运物资的非线性规划模型。
目标函数是一个最大最小的非线性函数,这用lingo是非常难解的,因此,本文考虑将该问题转化成对应的线性规划模型。由于最大的调运时间最小,其它参与调运的各顶点间的调运时间将会更小,那么它们调运时间的总和也是最小,如果不考虑时间的重叠,运输时间总和最小就意味着总路程最小。目标函数可以等价为下面的线性函数:,这时用lingo求解可以得到8天具体的调运方案。
4模型的评价
企业管辖制的优点是便于操作,各企业只需满足自己辖区内仓库的需求即可。但是,这种方案建立的是双目标规划模型,只能接近最优解,且通过不同处理方法得到解是不同的,到底选择那个解法的最优解视具体情况而定。另一方面,该方案规定各企业的调运相互独立导致解决方法不灵活,而事实上如果一个管辖区缺货,可以从其它企业调用。
非线性规划模型简单,便于移植,把企业、仓库和储备库同等看待为13个顶点,将他们的特性用不同的参数来表征,使模型变得简单,易于处理,但不易于求解,虽然将目标转化为线性目标,事实上并没有理论根据,缺乏说服力。
参考文献
[1]姜启源.数学模型[M].北京:高等教育出版社,1999.
[2]谢金星M薛毅.优化建模与LINDO/LINGO软件[M].北京:清华大学出版社,2005.
[3]韩中庚.实用运筹学[M].北京:清华大学出版社,2007.
[4]韩中庚.数学建模竞赛:获奖论文精选与点评[M].北京:科学出版社,2007.
[5]徐俊明.图论及其应用[M].合肥.中国科学技术大学出版社,2004.
[6]求是科技.MATLAB从入门到精通[M].北京.人民邮电出版社,2006.
[7]张伯生.运筹学[M].北京.科学出版社,2008.