钢管的订购和运输解答模型 邵铮周天凌马健兵 (清华大学,北京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;