管道订购与运输问题 杨志江李国欣张敏 (中国矿业大学,江苏徐州221008) 指导老师中国矿业大学数模教练组 编者按本文采用将待铺设管道按单位长度分解成n个需求点,建立运输模型的方法 避免了问题一和三的差别,模型切合原赛题要求,并针对原问题的规模,对算法作了一定的改 进,得到了较好的结果,本刊予以摘要发表 摘要本文在详细分析的基础上,通过合理假设并引入等价转换原则,将管道订购与运 输问题转化为单一的公路运输问题.运用组合优化的思想和方法,给出了数学模型一产量 未定的运输模型.针对此模型,我们设计了“改进的最小元素法”和“改进的伏格尔法”,先求得 了一个初始解,再通过“试探法”和“选代法”进行调整优化,最后得出结果:对第一问,最小总费 用为1279019万元;对第三问,最小总费用为1407383万元 1问题的重述(賂) 2基本假设 (1)只考虑订购费用和运输费用,不考虑装卸等其它费用 (2)钢管单价与订购量、订购次数、订购日期无关 (3)订购计划是指对每个厂商的定货数量;运输方案是指具有如下属性的一批记录:管 道区间,供应厂商,具体运输路线 (4)将每一单位的管道所在地看成一个需求点,向一单位管道的所在地运输钢管即为 向一个点运输钢管 3符号说明 m:钢厂总数 n:单位管道总数 S:第i个钢厂 s1:第i个钢厂的产量上限 p;:第i个钢厂单位钢管的销售价 A1:管道线上第i个站点 d:管道线上第i个单位管道的位置 F:总费用 C:从钢厂S:(i=1,2,…,m)到点d(j=1,2,…,n)的最低单位费用 4问题分析 运输费用等价转换法则:按单位运费相等原则将任意两点间的最短铁路线转换为公路 线.对于铁路线上的任意两点V、V,用 Floyd算法找出两点间最短铁路路线的长度L,查 铁路运价表求得L对应的铁路单位运费fG;又设与该段铁路等费用的公路长度为la,则 f=0.1×l 由此我们就在V1、V之间用一条等价的公路线来代替V,V间的最短铁路线.如果
管道订购与运翰问题 541 VV之间原来就有公路就选择新旧公路中较短的一条.这样,我们就把铁路运输网络转 换成了公路运输网络 销价等价转换法则:按单位费用相等将任意钢厂的单位销价转换为公路单位运价 对于钢厂S;的销售单价p,我们可以虚设一条公路线,连接钢厂S;及另一虚拟钢厂 S,其长度为l1,并且满足l1=0.1×p2;从而将钢厂的销售单价转换成公路运输单价,而新 钢厂S的销售价为0 将铁路和销价转换为公路的过程可以由计算机编程实现 通过上述的分析我们可以将原问题化为一个相对简单的产量未定的运输问题,利用 A1到A15之间的管道距离和钢厂和站点之间的公路距离建立一个产量未定的运输问题的 模型但是由于A1,A2,…A1并不能代表所有的实际需求点(实际需求点是n个单位管 道),因此,我们可以用 Floyd算法进一步算出7个钢厂到所有实际的n个需求点(对于问题 n=5171;对于问题三,n=5903)的最短路径,并由此得出一个具有7个供应点、n个需 求点的产量未定的运输模型 5模型的建立 产量未定的运输模型 根据假设4,我们可以将每一单位的管道看成一个需求点,向一单位管道的所在地运输 钢管即为向一个点运输钢管,对每个点,我们可以根据该点的位置和最短等价公路距离,求 出各钢厂与该点之间最小单位运输费用C;(销价已经归入运输费用之中了),设总共有m 个供应点(钢厂),n个需求点,我们就可以得到一个产量未定的运输模型: 有m个供应点、n个需求点,每个供应点的供应量u1∈|0}U500,sl;每个需求点需 要1单位,运输单价矩阵为C,求使得总运输费用最小的运输方案, 其数学规划模型 F ∈0U1500,S t x=0或1 其中: CuC12… C 出…为单位费用矩阵 CmI C X= …为决策矩阵,也为0-1矩阵 6模型的求解 对于本题,上述01规划规模宏大,现有的一些算法不能胜任,我们必须具体问题具体
542 全国大学生数学建模竞赛优秀论文汇编 分析,结合本题实际情况,寻找行之有效的算法 (1)初始方案的改进的最小元素法和改进的伏格尔法 改进的最小元素法 改进的最小元素法又称为贪婪法或瞎子爬山法,它的宗旨是每一步都取当前的最优值 算法步骤为,对费用矩阵C作n次下列循环 ①C中找一个最小值C ②令x1=1; ③C的第j列的所有数据改为+∞o; ④如果∑x=5,第i个供应点的供应量已达上限,将C的第i行数据全改为+ 对于问题一和问题三,我们用贪婪法求得的最小总费用的初始分别为:1286692,1万元 和14145152万元 改进的伏格尔法 改进的最小元素法确定的初始方案往往缺乏全局观念,即为了节省一处的费用,在其它 处要花费更多,改进的伏格尔法的主要思想:一个目的地如果不能采用最小值供应(供应点 供应不足),就必须考虑次小值供应,这里就存在一个差额,差额越大,在不能采用最小值 时,损失越大.因此,改进的伏格尔法的宗旨是每一步对当前差值最大的点取当前最小值 算法的步骤为,对矩阵C做n次下列循环 ①指出每一行最小值与最大值之差最大的一行,第i行,找出该行的最小值为Ca; ②令 一③令C的第;列的数据为+∞; ④如果∑x=5,第i个供应点供应量已达上限,令C的第i行的所有数据为 对于问题一和问题三,我们用改进的伏格尔法求得方案的总费用分别为1279019万元 和1407383万元 (2)调整优化 调整优化是将一个离最优解很近的初始解调整到在调整算法下无法更优的程度,调整 优化分两个部分,第一部分是用试探法对供应点的供应量进行优化.第二部分是用迭代法 对供应点进行两两对调优化 试探法调整优化实际供应量在500以下的供应点 对每个实际供应量在500以下的供应点,只存在两种合理的优化方法:一种是将其供应 量增加到500,另一种是将其供应量减少到0.试探法将分别试探进行下列两种优化 其一是先将供应点的供应量强行提升至500,使用改进的伏格尔法的优先顺序,从其它 供应点负责供应的需求点抢夺一部分,再用对调法优化至无法更优,得出一个总费用F1;其 二是先将该供应点的供应量调整为0,其原供应的需求点由其它钢厂用改进的伏格尔法的 优先顺序补充,再用对调法优化至无法更优,得出一个总费用F2,那么,就应当采取总费用 较小的方法 例如,对于第一问,按改进的伏格尔法获得的初始方案中,S7的用量仅为245,优化时, 试探将其降为0和将其提升为500后的最优结果,分别为1279019万元和1280506万元,则
管道订购与运输问题 543 说明应将S7降为0. 用迭代法进行对调优化 改进的伏格尔法给出的初始值虽然很接近最优值,但仍有不足之处,即可能存在两个需 求点调换供应点能使总费用更小,例如,需求点a和b的供应点是x和y,费用分别是C (x,a)和C(y,b),如果让y供应a,x供应b的话,费用将是C(y,a)和r(x,b),如果 C(y,a)+r(r, b)<C(x, a)+ C(y, b) 则说明对调后总费用更低 因此,我们可以采用迭代法对任意两个需求点的供应点两两对调至无法更优 由于一共只有m=7个供应点,所以两两对调的可行方案一共有G号=21种,因此,两 两对调供应点的方法是可行的,具体步骤如下: Stpl对于任意两个供应点x和为i=1,2,…,mj=1,2,…,mi 1)找出所有由x供应的需求点,构成点集A=|a1,a,c 2)找出所有由x供应的需求点,构成点集B={b1,2,}元 3)对A中所有点,如果改用x来供应,将付出的代价构成向量A=a1,a,…青 4)对B中所有点,如果改用x来供应,将付出的代价构成向量B={b1,b1,… 5)对A和B分别按升序排序 6)同时对A和B从前向后遍历,如果a+b1<0(表示对调供应者将降低总费用),则 对调其供应者,直到出现a;+b2≥0为止 Stcp2统计这Cm轮对调后的总费用F是否比原来的总费用F有明显的进步,即F F>6(为一固定的较小值).如果有明显的进步,则再回Sepl执行,否则结束优化 令人振奋的是,采用改进的最小元素法和改进的伏格尔法得到问题一的初始方案分别 采用这种优化方案后,竟都达到了相同的最小费用:1279019万元 (3)结果(略) 参考文献 ]薛秀谦等编著《运筹学》,中国矿业大学出版社,1998年 2]赵新泽著.《线性规划的新方法和应用》世界图书出版社,1996年 3]王树禾著,《图论极其算法)中国科学技术大学出版社,190年 [4] LUCAS WF著.《离散与系统模型》国防科技大学出版社,1996年
钢管订购和运输策略 段晓军俞昌盛吴建德 (西北工业大学,西安710072) 指导老师张胜贵 编者按本文节选的是原论文中模型的分析与建立以及之前的准备工作部分该部分通 过单位钢管的最小运购费,建立了问题求解的二次规划模型,特点是思路、表述简明、清晰,尤 其是第3问的模型具有较强的一般性,适用于树形结构的通常情形.值得注意的是,模型中有 关铺设费的假设和表达式与常见情形略有不同 摘要在铺设管道为一条线的情况下,我们建立了解决钢管订购和运输问题的非线性 规划模型,由于变量较少,约束条件大都为线性的,目标函数为二次函数,所以利用 Lingo软 件,可以很快求得比较满意的订购和运输方案.我们利用 Matlab软件,对所得到的数据进行 拟合,得到相应的反映销价变化对总费用影响的曲线,然后比较各个钢厂钢管销价变化对总费 用影响的大小,对于钢厂钢管产量上限变化对总费用和购运计划的影响我们也作了类似的 处理.如果要铺设的管道是树形图,我们对树形图的每条边定向建立了与铺设管道为一条线 时类似的数学模型,从而大大拓广了模型的使用范围.在论文中我们还对所建立的模型的优 缺点和需要改进的方向进行了讨论 1符号说明 s:钢厂S;在指定期限内钢管的最大产量 A到A,之间铺设管道的里程数 c:单位钢管从钢厂S运到A,所需最小订购和运输费用; x;:钢厂S;是否承担制造这种钢管; y:钢厂S运抵A点的钢管数量,不含路过A的部分 x:运到A的所有钢管沿A→A+1铺设的数量 z;运抵A1的所有钢管沿A1→A,铺设的数量 d(A):树中A的度数 d-(A):树中A,的人度; d(A1):树中A的出度; p:单位钢管1公里的公路运输费用 2基本假设 根据题目的要求,并为达到简化问题的目的,我们有以下假设 1.假设运到A的钢管,只能在A-1到A+1之间包含A的某个区段内铺设,并且到达 A的钢管在A-1到A1之间包含A的铺设区段和到达A+1的钢管在A到A+2之间包含 A+的铺设区段不相交,否则的话,总可以调节铺设方案使得总费用减少 2.在考虑问題2时,假设钢管价格不可能有太大幅度变化,所以,我们只考虑钢管价格 在其原售价10%的范围内波动.同时,我们假定,钢厂的产量不可能成倍的增加或减少.我