2000年全国数学建模竞赛B题优秀论文

管道订购与运输问题1问题重述2基本假设(1)只考虑订购费用和运输费用，不考虑装卸等其它费用．(2)钢管单价与订购量、订购次数、订购日期无关．(3)订购汁划是指对每个厂商的定货数量；运输方案是指具有如下属性的一批记录：管道区间，供应厂商，具体运输路线．(4)将每一单位的管道所在地看成一个需求点，向一单位管道的所在地运输钢管即为向一个点运输钢管．3符号说明M：钢厂总数.n：单位管道总数.:iS第i个钢厂:iS第i个钢厂的产量上限。:ip第i个钢厂单位钢管的销售价iA管道线上第i个站点。id管道线上第i个单位管道的位置。F：总费用。:ijC从钢厂(1,2,,)iSim到点(1,2,,)jdjn的最低单位费用。4问题的简化求SAP矩阵的基本思路是图的最短路算法.由于铁路的运输费用与线路的长度不是线性关系,必须对铁路网做一些预处理才能套用图的标准最短路算法.下面叙述求SAP矩阵的过程:1.利用图的标准最短路算法,从铁路网络得出图中任两个点之间的最短路径表T(如果两个点之间不连通,认为它们之间的最短路长度为+∞).2.利用题中的铁路运价表将T中的每个元素(即最短距离)转化为运输费用,将运输费用表记为C.3.将公路的长度换算为运输费用,由公路路程图(包括要沿线铺设管道的公路)得出公路费用图G,若i,j不连通,则令Gij=+∞.4.对于任一组(i,j)∈{1,…n}×{1,…m}如果Cij+∞,且小于Gij,那么就在公路费用图中加一条边.即令Gij=min{Cij,Gij}.5.利用图的标准最短路算法,求公路费用图中任一个S点到任一个A点的最小费用路径,得出SAP矩阵.如表1所示:SAP矩阵A123456789101112131415S117071603140298638020531212642920960106012121280142022157205319021716111095586071211421420146015601712178019203230722032002181612101055960862482820860960111211801320426072503235221661560140513101162842620510610762830970525572453225220661460130512101112792570330510712730870626572553235221661560140513101212842620510450262110280727572653245222661660150514101312992760660560382260205问题分析运输费用等价转换法则：按单位运费相等原则将任意两点间的最短铁路线转换为公路线．对于铁路线上的任意两点,ijVV，用F1oyd算法找出两点间最短铁路路线的长度ijL查铁路运价表求得ijL，对应的铁路单位运费ijf;又设与该段铁路等费用的公路长度为ijl，则：0.1ijijfl由此，我们就在,ijVV之间用一条等价的公路线来代替,ijVV间的最短铁路线．如果,ijVV之间原来就有公路，就选择新旧公路中较短的一条．这样，我们就把铁路运输网络转换成了公路运输网络．销价等价转换法则：按单位费用相等将任意钢厂的单位销价转换为公路单位运价．对于钢厂Si的销售单价Pi，我们可以虚设一条公路线，连接钢厂Si及另一虚拟钢厂'is，其长度为il，并且满足0.1iilp；从而将钢厂的销售单价转换成公路运输单价，而新钢厂'is的销售价为0.将铁路和销价转换为公路的过程可以由计算机编程实现．通过上述的分析，我们可以将原问题化为一个相对简单的产量未定的运输问题，利用115AA到之间的管道距离和钢厂和站点之间的公路距离建立一个产量未定的运输问题的模型．但是由于1215,AAA,并不能代表所有的实际需求点(实际需求点是n个单位管道)，因此，我们可以用F1oyd算法进一步算出7个钢厂到所有实际的n个需求点(对于问题一，n＝5171;对于问题三，n＝5903)的最短路径，并由此得出一个具有7个供应点、n个需求点的产址未定的运输模型．6模型的建立产量未定的运输模型根据假设4，我们可以将每一单位的管道看成一个需求点，向一单位管道的所在地运输钢管即为向一个点运输钢管．对每个点，我们可以根据该点的位置和最短等价公路距离，求出各钢厂与该点之间最小单位运输费用ijC(销价已经归人运输费用之中了)．设总共有m个供应点(钢厂)，n个需求点，我们就可以得到一个产量未定的运输模型：有m个供应点、n个需求点，每个供应点的供应量{0}{500,}iius；每个需求点需要1单位，运输单价矩阵为C，求使得总运输费用最小的运输方案．其数学规划模型：11minmnijijijFCx11{0}{500,}1,2,,..11,2,01nijijmijiijxSimstxjnx或其中：1112112nmmmnCCCCCCC为单位费用矩阵1112112nmmmnxxxXxxx为决策矩阵，也为0-1矩阵代码如下7模型的求解对于本题，上述0-1规划规模宏大，现有的一些算法不能胜任，我们必须具体问题具体分析，结合本题实际情况，寻找行之有效的算法．(1)初始方案的改进的最小元素法和改进的伏格尔法*改进的最小元素法改进的最小元素法又称为贪婪法或瞎子爬山法，它的宗旨是每一步都取当前的最优值算法步骤为，对费用矩阵C作n次下列循环：①C中找一个最小值ijC；②令1;ijx③C的第j的所有数据改为+；④如果1nijijxs，第i个供应点的供应量已达上限，将C的第i行数据全改为+。对于问题一和问题三，我们用贪婪法求得的最小总费用的初始分别为1286692.1万元和1414515.2万元。（2）调整优化调整优化是将一个离最优解很近的初始解调整到在调整算法下无法更优的程度．调整优化分两个部分，第一部分是用试探法对供应点的供应量进行优化．第二部分是用迭代法对供应点进行两两对调优化．*试探法调整优化实际供应量在500以下的供应点对每个实际供应量在500以·F的供应点，只存在两种合理的优化方法：一种是将其供应量增加到500，另一种是将其供应量减少到0．试探法将分别试探进行下列两种优化：其一是先将供应点的供应量强行提升至500，使用改进的伏格尔法的优先顺序，从其它供应点负责供应的需求点抢夺一部分，再用对调法优化至无法更优，得出一个总费用F1；其二是先将该供应点的供应量调整为0，其原供应的需求点由其它钢厂用改进的伏格尔法的优先顺序补充，再用对调法优化至无法更优，得出一个总费用F2那么，就应当采取总费用较小的方法．例如，对于第一问，按改进的伏格尔法获得的初始方案中，S7的用量仅为245，优化时，试探将其降为0和将其提升为500后的最优结果，分别为1279019万元和1280506万元，则说明应将S，降为0．*用迭代法进行对调优化改进的伏格尔法给出的初始值虽然很接近最优值，但仍有不足之处，即可能存在两个需求点，调换供应点能使总费用更小，例如，需求点a和6的供应点是x和y，费用分别是C(x,a)和C(y,b)，如果让y供应a，x供应b的话，费用将是C(y，a)和r(c，b)，如果：C(y，a)+r(x，b)C(x，a)+C(y，b)则说明对调后总费用更低．因此，我们可以采用迭代法对任意两个需求点的供应点两两对调至无法更优．由于一共只有m＝7个供应点，所以两两对调的可行方案一共有2721C种，因此，两两对调供应点的方法是可行的，具体步骤如下：Stepl对于任意两个供应点xi和xji＝1，2，…，mj=1，2，…，mij1)找出所有由xi供应的需求点，构成点集A＝{a1,a2,c}2)找出所有由xj供应的需求点，构成点集B＝{b1,b2,…}3)对A中所有点，如果改用xj来供应，将付出的代价构成向量''11'{,,}Aaa4)对B中所有点，如果改用xi来供应，将付出的代价构成向量''11'{,,}Bbb5)对''AB和分别按升序排序．6)同时对''AB和从前向后遍历，如果''0iiab(表示对调供应者将降低总费用)，则对调其供应者，直到出现''0iiab为止．Step2统计这2mC轮对调后的总费用'F是否比原来的总费用F有明显的进步，即'()FF为一固定的较小值。如果有明显的进步，则再回Stepl执行，否则结束优化．采用改进的最小元素法和改进的伏格尔法得到问题一的初始方案分别采用这种优化方案后，竟都达到了相同的最小费用：1279019万元．8结果：通过合理假设并引人等价转换原则，将管道订购与运输问题转化为单一的公路运输问题．运用组合优化的思想和方法，给出了数学模型·——产量未定的运输模型．针对此模型，我们设计了“改进的最小元素法”和“改进的伏格尔Ph，先求得了—个初始解。再通过“试探法”和“迭代法”进行调调优化．最后得出结果：对第—·问．最小总费用为1279019万元；对第三问．最小总费用为1407383万元．参考文献[1]薛秀谦等编著．《运筹学》.中国矿业大学出版社．1998年．[2]赵新泽著．《线性规划的新方法和应用》．世界图书出版社，1996年．[3]王树禾著．《图论极其算法》．中国科学技术大学出版社．1990年．[4]LUCASWF著．《离散与系统模型3．国防科技大学出版社，1996年钢管订购和运输策略1符号说明·is：钢厂is在指定期限内钢管的最大产量；·,:ijijAA到，之间铺设管道的里程数；·:ijc：单位钢管从钢厂iS运到jA，所需最小订购和运输费用；·:ix钢厂iS是否承担制造这种钢管；·:ijy钢厂iS运抵Aj点的钢管数量，不含路过Aj的部分；·:jz运到Ai的所有钢管沿1jjAA铺设的数量；·ijz：运抵Ai的所有钢管沿1jjAA铺设的数量；·()jdA：树中Aj的度数；·():jdA树中Aj的入度；·():jdA树中Aj的出度；·:单位钢管1公里的公路运输费用。2基本假设根据题目的要求，并为达到简化问题的目的，我们有以下假设：1．假设运到Aj的钢管，只能在11jjAA到之间包含Aj的某个区段内铺设,并且到达Aj的钢管在11jjAA到之间包含Aj的铺设区段和到达Aj+1，的钢管在Aj到Aj+2之间包含Aj+l的铺设区段不相交．否则的话，总可以调节铺设方案，使得总费用减少．2．在考虑问题2时，假设钢管价格不可能有太大幅度变化．所以，我们只考虑钢管价格在其原售价10％的范围内波动．同时，我们假定，钢厂的产量不可能成倍的增加或减少．我们在减少300个单位，增加600个单位的范围内讨论，这意味着我们不考虑钢厂破产或者超大规模扩大生产的情况．3．在具体铺设每一公里时，我们只把钢管运到每一公里开始的地方，沿运送方向向前铺，然后往前铺设的运送费用我们不予考虑．3模型建立1．问题l的模型(1)决策变量我们首先引入一组0一1变量127,,xxx,其中ix表示钢厂Si是否承担制造这种钢管．如果钢厂Si承担制造这种钢管，则1ix，否则0ix.所有的钢管，都是先运用215,,,AAA后，或者转运到其它地方，或者在包含Aj的一个区段内铺设，我们设从钢厂Si运抵Aj的一个区段内铺设的钢管数量为ijy,这里1,2,,7;1,2,15.ij我们用变量Zj来表示从所有的钢厂运到Aj的钢管总量中沿1jjAA铺设的部分，这里j=1,2,,14.这样，我们一共引入了三组决策变量：(1,2,,7);(1,2,,7,iijxiyij1,2,,15);(1,2,,14)kzk。（2）目标函数问题的目的是求好的订购和运输方案，使得总费用最小，事实上，总费用可以分成两部分。第一部分包括钢管的订购费用和钢管从钢厂运抵1215,,AAA所需的运费；我们用ijc来表示单位钢管从钢厂ijSA运抵所需的最小订购和运输费用，则第一部分费用为715111ijijijucy第二部分费用是指钢管运抵12