文档介绍：2000年论文选
管道订购与运输问题
杨志江, 李国欣, 张敏
指导老师: 中国矿业大学数模教练组
( 221008)
编者按:本文采用将待铺设管道按单位长度分解成n个需求点,,对算法作y--定的改进,.
摘要:本文在详细分析的基础上,通过合理假设并引人等价转换原则,,给出了数学模型·——,我们设计了“改进的最小元素法”和“改进的伏格尔Ph",先求得了—个初始解。再通过“试探法”和“迭代法”:对第—·;.
1 问题的重述(略)
2 基本假设
(1)只考虑订购费用和运输费用,不考虑装卸等其它费用.
(2)钢管单价与订购量、订购次数、订购日期无关.
(3)订购汁划是指对每个厂商的定货数量;运输方案是指具有如下属性的
(4)订购汁划是指对每个厂商的定货数量;运输方案是指具有如下属性的一批记录:管道区间,供应厂商,具体运输路线.
(4)将每一单位的管道所在地看成一个需求点,向一单位管道的所在地运输钢管即为
向一个点运输钢管.
3 符号说明
M:钢厂总数. n:单位管道总数.
第i个钢厂第i个钢厂的产量上限。
第i个钢厂单位钢管的销售价管道线上第i个站点。
管道线上第i个单位管道的位置。 F:总费用。
从钢厂到点的最低单位费用。
4 问题分析
运输费用等价转换法则:按单位运费相等原则将任意两点间的最短铁路线转换为公路
,用F1oyd算法找出两点间最短铁路路线的长度查
铁路运价表求得,对应的铁路单位运费;又设与该段铁路等费用的公路长度为,则:
由此,,,我们就把铁路运输网络转换成了公路运输网络.
销价等价转换法则:按单位费用相等将任意钢厂的单位销价转换为公路单位运价.
对于钢厂Si的销售单价Pi,我们可以虚设一条公路线,连接钢厂Si及另一虚拟钢厂,其长度为,并且满足;从而将钢厂的销售单价转换成公路运输单价,而新钢厂的销售价为0.
将铁路和销价转换为公路的过程可以由计算机编程实现.
通过上述的分析,我们可以将原问题化为一个相对简单的产量未定的运输问题,(实际需求点是n个单位管道),因此,我们可以用F1oyd算法进一步算出7个钢厂到所有实际的n个需求点(对于问题一,n=5171;对于问题三,n=5903)的最短路径,并由此得出一个具有7个供应点、n个需求点的产址未定的运输模型.
5 模型的建立
产量未定的运输模型
根据假设4,我们可以将每一单位的管道看成一个需求点,,我们可以根据该点的位置和最短等价公路距离,求出各钢厂与该点之间最小单位运输费用(销价已经归人运输费用之中了).设总共有m个供应点(钢厂),n个需求点,我们就可以得到一个产量未定的运输模型:
有m个供应点、n个需求点,每个供应点的供应量;每个需求点需要1单位,运输单价矩阵为C,求使得总运输费用最小的运输方案.
其数学规划模型:
其中: 为单位费用矩阵
为决策矩阵,也为0-1矩阵
6 模型的求解
对于本题,上述0-1规划规模宏大,现有的一些算法不能胜任,我们必须具体问题具体分析,结合本题实际情况,寻找行之有效的算法.
(1)初始方案的改进的最小元素法和改进的伏格尔法
*改进的最小元素法
改进的最小元素法又称为贪婪法或瞎子爬山法,它的宗旨是每一步都取当前的最优值算法步骤为,对费用矩阵C作n次下列循环:
①C中找一个最小值;
②令
③C的第j的所有数据改为+;
④如果,第i个供应点的供应量已达上限,将C的第i行数据全改为+。
对于问题一和问题三,。
*改进的伏格尔法
改进的最小元素法确定的初始方案往往缺乏全局观念,即为了省节一处的费用,在其它处要花费更多,改进的伏格尔法的主要思想:一个目的地如果不能采用最小值供应(供应点供应不足),就必须考虑次小值供应,这里就存在一个差额,差额越大,在不能采用最小值时,损失越大,因此,改进的伏格尔法的宗旨是每一