管道订购与运输问题 杨志江李国欣张敏 (中国矿业大学,江苏徐州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)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%的范围内波动.同时,我们假定,钢厂的产量不可能成倍的增加或减少.我
钢管订购和运输策昭 545 们在减少300个单位,增加600个单位的范围内讨论,这意味着我们不考虑钢厂破产或者超 大规模扩大生产的情况 3.在具体铺设每一公里时,我们只把钢管运到每一公里开始的地方,沿运送方向向前 铺,然后往前铺设的运送费用我们不予考虑 3模型建立 1.问题1的模型 (1)决策变量 我们首先引入一组0-1变量x1,x2,…,x7,其中x1表示钢厂S1是否承担制造这种钢 管.如果钢厂S1承担制造这种钢管则x1=1,否则x;=0. 所有的钢管,都是先运到A1,A2,…,A15后,或者转运到其它地方,或者在包含A的 个区段内铺设我们设从钢厂S运抵A且在包含A的一个区段内铺设的钢管数量为y,这 里i=1,2 我们用变量x来表示从所有的钢厂运到A,的钢管总量中沿A→A1铺设的部分,这 里j=1,2,…,14 这样,我们一共引入了三组决策变量:x1(i=1,2,…,7);y(i=1,2,…,7;j=1,2 ,15);x(k=1,2,…,14) (2)目标函数 问题1的目的是寻求好的订购和运输方案,使得总费用最小.事实上,总费用可以分成 两部分.第一部分包括钢管的订购费用和钢管从钢厂运抵A1,A2,…,A15所需的运费;我 们用c来表示单位钢管从钢厂S;运抵A1所需的最小订购和运输费用,则第一部分费用为 第二部分费用是指钢管运抵A1,A2,…,A15后,再运到具体铺设地点的费用由假设3,从 A到A+1区段部分所需的费用为 (-1)+(叫+1-x)(,1-=1-1) 其中四,表示A到A+铺设管道的长度.这样,我们不难得知第二部分费用为 2=>[(5-15+(,5)(m--1) (3)约束条件 首先,由于一个钢厂如果承担制造这种钢管,则至少需要生产500个单位,而钢厂S在 指定期限内能生产钢管的最大数量为s个单位.所以,我们得到以下一组约束条件 500x;≤∑y≤s,i=1,2,…,7 由于订购的所有钢管总量等于A1→A2→…→A15的里程数那么 ∑ 5171 很显然我们可以设x≤,+1·因为如果x>,+1,则相当于有x,-v,+数量的
46 全国大学生数学建模竞赛优秀论文汇编 钢管是从A,直接运送到A+1后再送到具体铺设地点 抵A的钢管总数量等于向包含A的区段铺设的里程数,那么 y三 2 并且,我们还有∑m1=x1和∑y15=11=x (4)数学模型 通过上面的分析,我们得到问题1的如下模型 %%+∑[1(3-1)+(可,)(,--1) 500x;≤∑y≤sx j=1,2,,7 5171 (A)st 0≤x≤wy, 14 x;=0,1 i=1,2, y≥0, 1,2,…,7;j=1,2,…,15 可以看出,这是一个非线性规划问题 2.问题2的模型 为了分析钢厂钢管销价的变化对购运计划和总费用的影响,对于每个钢厂,利用模型 (A),我们分别算出它的钢管销价发生一系列的变化后,所得到的总费用和购运计划;并根 据所得到的数据,利用 Matlab软件拟合出销价变化和总费用变化量关系的曲线,对所得到 的曲线进行分析和对比,找到钢管销价变化对购运计划和总费用影响最大的钢厂.类似地 我们用同样的方法,对钢厂产量上限发生变化对购运计划和总费用的影响进行了分析 3.问题3的模型 如果要铺设的管道不是一条线,而是一个树形图,我们首先给树形图的每条边指定一 个方向,使得所得到的有向树有一个度数为1的顶点的入度为0,而其它每个顶点的入度均 为1.与问题1一样我们可以引入0-1变量x(i=1,2,…,7)以及变量y(i=1,2,… 7,j=1,2,…,21),它们的含义与问题1中的定义完全一致.类似于问题1,对于有向树的 有向边(A,A),我们用x表示运抵A,的所有钢管沿A1→A3铺设的里程数.数学模型为 )(
钢管订购和运输策路 547 500x;≤∑y≤sx j=1,2,…,7 ∑∑x=59 当d(A)>1时,∑=∑4+(-动),其中(A,A)∈E(T) (B)st 当d'(A)=0时,∑=,-,其中(A,A)∈E(T) 当d(4)=0时,∑=5,其中(A1,A)∈E(T) 0≤≤w,, (A1,A)∈E(T) 1,2,…,7 ≥0, i=1,2,…,7;j=1,2,…,21 参考文献 [1]甘应爱,田丰等著,运筹学,清华大学出版社,北京,1994 [2]袁亚湘,孙文瑜著,最优化理论与方法,科学出版社,北京,1997 [3]徐俊明著.图论及其应用,中国科学技术大学出版社,合肥,1997 ………,…· 国内正式出版的数学建模教材、译著及竞赛辅导材料 E.A. Bender,数学模型引论,朱尧辰、徐伟宣译,科学普及出版社,1982. 近滕次郎,数学模型,宫荣章等译,机械工业出版社,1985 C.L.戴姆,E.S.艾维著,教学构模原理,海洋出版社,1985 姜启源,数学模型高等教育出版社,1987 任善强,数学模型,重庆大学出版社,1987 ·M. Braun,C.S. Coleman,D.A.Drew,微分方程模型,朱短民、周宇虹译,国防科 技大学出版社,(本书为W.F. Lucas主编的 Modules in Applied Mathematics-书 的第一卷),1988 谌安琦,科技工程中的数学模型,中国铁道出版社,1988 江裕钊、辛培湾,数学模型与计算机模拟,电子科技大学出版社,1989 杨启帆、边馥萍,数学模型,浙江大学出版社,1990. ·董加礼、曹旭东、史明仁,数学模型,北京工业大学出版社,1990 唐焕文、恩民、孙育贤、孙丽华,数学模型引论,大连理工大学出版社,1990 要启源,数学模型(第二版),高等数育出版社,1993 ·H.P. williams,数学规划模型建立与计算机应用,国防工业出版社,1991 (下转第573页)
钢管的订购和运输解答模型 邵铮周天凌马健兵 (清华大学,北京100084) 指导老师扈志明 编者按本文把B题的问题1和3归结为网络最小费用流问题,建立了线性和非线性最小 费用流模型,井运用相应的解法和分支定界法求解,叙述清晰,简洁,层次分明,本刊予以部分 发表.我们指出:本文的网络流模型和线性规划中标号运输问题模型是等价的 摘要首先通过最短路算法简化了供需距离网络,去掉了铁路、公路等边的性质,使供需 距离网络简化为一个供需运输价格表,在此基础上构造了三个模型:线性费用的网络流模型、 改进的线性费用的网络流模型和具有非线性费用的网络流模型.通过改进传统的最小费用最 大流算法,解决了本题的非线性费用网络流模型,并给出了算法的正确性证明与复杂度分析 关键词运输问题;网络流;树形网络;分支定界 1问题的提出(略) 2基本假设和符号说明 2.1基本假设 1.原图是一个连通的简单图; 2.铁路、公路的运量没有限制; 3.为了满足费用最小的要求,允许出现生产过剩现象; 4.工厂的数目(图中S点的个数)不太多,约在10个以下 5.待铺设的钢管长度不太长,约在10000公里以下; 6.待铺设的线路的段数不太多,约在40段以下; 7.公路运输不足整公里部分按整公里算 2.2符号说明 1.工厂(图中S点),设有n个,记作S1、S2,…S 2.在不至于混淆的情况下,S1同时用来表示每个工厂的产量,i=1,…n; 待铺设线路的端点(图中A点以后简称关节点),设有m个,记作A1A2…An; 在不至于混淆的情况下,A,同时用来表示从各个工厂运到A1的钢管总数量,=1 5.待铺设的管道,记作P(j≠k),表示A与A4之间有一条待铺设的管道,它的长度 也用P来表示,如果A与A之间没有待铺设的管道,则Pk=0 6.SAQ表示从S到A的运输量,=1,…n,=1,…m 7.SAP表示从S到A运输单位长度钢管的最小费用,=1,…n,)=1,…m; 8.AAQ表示A提供的用于铺设A与A4之间管道的长度,,k=1,…m,显然有 LAQa t AAQh= P;
钢管的订购和运输解吝模型 9.下文所有费用的单位均为千元 3问题的分析与简化 3.1问题的分析 整个铺设管道的工程看似错综复杂,其实可分为三个部分 各个工厂(S点)生产一定数量的钢管 2.把钢管从工厂(S点)运送到铺设管道的关节点(A点) 3.从关节点(A点)将管道运至铺设地点 这三个部分是相互依赖的,不能简单地把三个部分孤立开来讨论.但是通过仔细观察 我们发现第二部分中的运费事实上只与出发点(S点)、目标点(A点)和运量有关,并且是 运量的线性函数,具备可叠加性 运输总费用:W=∑∑SAQn×SAP 因此,我们可以简化第二部分的计算,即先从铁路与公路网络得出SAP矩阵 3.2问题的简化 求SAP矩阵的基本思路是图的最短路算法 由于铁路的运输费用与线路的长度不是线性关系,必须对铁路网做一些预处理才能套 用图的标准最短路算法 下面叙述求SAP矩阵的过程: 1.利用图的标准最短路算法,从铁路网络得出图中任两个点之间的最短路径表T(如 果两个点之间不连通,认为它们之间的最短路长度为+∞) 2.利用题中的铁路运价表将T中的每个元素(即最短距离)转化为运输费用,将运输 费用表记为C. 3.将公路的长度换箅为运输费用,由公路路程图(包括要沿线铺设管道的公路)得出公 路费用图G,若i,j不连通,则令Ga=+∞ 4.对于任一组(i,j)∈1,n}×,…m}如果C<+∞,且小于G,那么就在公路 费用图中加一条边.即令G= min Ci,G 利用图的标准最短路算法,求公路费用图中任一个S点到任一个A点的最小费用 路径,得出SAP矩阵.如表1所示: 表1图1的SAP矩阵 5 6 10 1170716031402986380205312126429209601060121212801420 2215720531902171611109558607121142142014601560171217801920 3230722032002181612101055960862482820860960111211801320 420532610110510608970 5257245322522066146013051210111279257030510712730870 626572553235221661560140513101212842620510450262110280 727572653245222661660150514101312992760660560382260