2003数学建模B题(国家一等奖)-参考总结.doc

- 露天矿生产的车辆安排 摘要：本文讨论了铁矿运输问题中，在满足卸点产量和品位要求的前提下，针对不同的原则建立一般的最优生产计划的模型。用LINDO软件求解，速度很快，在实例求解的过程中，迭代次数分别为47次和45次。与经典的线性规划方法相比，具有一定的优越性。 针对原则一：列出多目标规划模型。然后将模型简化，分为两阶段求解。第一阶段为单目标线性规划模型，用LINDO软件求解，得出运输路线及运输次数。第二阶段采用MATLAB软件求解，用到第一阶段的结果，得出最优生产计划。结果：需要13辆卡车；7辆电铲，电铲分布在铲点1，2，3，4，8，9，10；总运量为8.57万吨公里。 针对原则二：列出多目标规划模型。然后分为三阶段来求解，前两阶段为单目标线性规划，第三阶段是分析的过程。采用LINDO软件求解。结果：需要20辆卡车；7辆电铲，电铲分布在铲点1，2，3，4，8，9，10；总产量为10.087万吨，其中矿石6.0022万吨，岩石4.0848万吨。 关键词：多目标规划 模型化简 分阶段求解 快速算法 一、问题的提出 钢铁工业是国家工业的基础之一，铁矿的运输工程的重要性由此可见。本题要求根据两个原则分别建立模型，在满足卸点的数量和品位的前提下，求解出最优生产计划。 原则一：总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小； 原则二：利用现有车辆运输，获得最大的产量(岩石产量优先；在产量相同的情况下，取总运量最小的解)。 生产计划包括：出动几台电铲，分别在那些铲位上；出动几辆卡车，分别在那些路线上各运输多少次；在卡车不等待条件下满足产量和品位要求。 二、问题的假设 1.铁矿的运输是周期性的，虽然本题只要求给出一个班次的生产计划，我们仍然把它放在一个周期性的运输过程当中来考虑，卡车完成本班次的运输任务以后仍回到出发点。 2 在确定生产计划时，不考虑随机因素的影响，即装车与卸车的时间严格遵守题目所给的时间。 3 运输成本不包括铲车的运行费用。 4 在运输过程中不会发生意外状况。 5 各个卸点的产量必须满足，即只许多运，不许少运。总的运输量满足卸点的品位要求。 6 假设卡车的初始位置是在卸点上。 7 卡车在空车与满载的情况下速度相同。 三、问题的分析 (一)整个运输铁矿的工程可分为5个部分： 1 各个铲位有一定数量的岩石，我们称之为岩石储量；还有一定数量的某个品位的矿石 我们称之为矿石储量。 2 每个卸点需要一定数量的岩石或某个品位范围内的矿石。 3 把铲位的岩石按照卸点的需求量运到卸点，把铲位的矿石按照卸点的产量和品位要求运到卸点。 4 原则一：总运量最小,并且卡车数最少，从而使运输成本最小。 5 原则二：产量最大；在产量相同的情况下，岩石产量优先；在前两个条件相同的情况下，取总运量最小的解。 这几个部分是相互依赖的，不能简单地孤立讨论。通过仔细分析，我们发现第四部分的成本事实上只与运输距离和运量有关；第五部分的产量只与铲位的储量和卸点的品位要求有关，并且二者都是运量的线性函数，具备可叠加性。 (二)对原则一的分析： 1 对运输成本的理解： 运输成本与两个方面有关：总运量（单位：吨公里），卡车的启动费用和消耗的油的费用。由于题目中并未给出这二者之间的关系，我们把这两点的要求看作同等重要的目标，将此问题化为多目标规划来求解。 2 对于卡车停放地点的考虑： 由于铁矿的运输是一个周期性的过程，我们认为卡车在完成运输任务以后应回到出发点。令出发点为卸点，这样可以方便求解，并且容易适用到真正的运输工程中去。 3对于最小卡车数的分析： 我们的假设是卡车最初是停在卸点上，这样有可能发生的情况是停在同一卸点的卡车在完成本卸点运输任务后，会有空余的时间，即，在若干辆卡车的运输时间均达到一个班次的时间时，这一卸点的产量要求仍未满足，但所剩余的运量又不足运行一个班次的时间。在寻找最小卡车数的时候，我们的原则是用一辆或多于一辆卡车来解决各个卸点所剩余的运量不足一个班次的运输问题，而其余的卡车均在用整个班次的时间向某一卸点运输。 4 对于总运量的理解： 根据题目中所给的总运量的单位为“吨公里”，因此只有在卡车满载时才能算入总运量。所以，在卡车空载时，只要运行的总时间不超过一个班次的时间，那么它的运行路程对运输成本无影响。 (三)对原则二的分析： 此问题显然是一个多目标的问题，与上一问题不同之处在于每个目标的重要性即权重不同。只要给定权重系数，此问题可以化为单目标规划问题。然而对于不同的决策者来说，权重系数是不同的。因此我们把此问题化为3个阶段来求解，当然，这3个阶段并不都是必须的。在第一阶段，仅以最大产量为目标，若此阶段存在最优解相同但生产计划不同的情况就进入第二阶段。在第二阶段，以最大岩石产量为目标，求出最优解，若此时的总产量小于第一阶段，则以第一阶段的解为最优解。否则采取第二阶段的解，若此时依然存在多种情况，进入第三阶段。在第三阶段，分析各个解的总运量，选择最优解。 (四)对于卡车不等待问题的分析： 卡车在等待时消耗的能量相当可观，原则上不应安排卡车等待的情况，我们假设装车和卸车的时间固定不变，这样得出一个理想的结果。 四、符号说明 ——铲点到卸点的距离。。 ——铲点向卸点运输的次数。。 ——卸点的需求量（单位：吨）。。 ——铲点的矿石储量（单位：吨）。。 ——铲点的岩石储量（单位：吨）。。 ——铲点的矿石品位（百分数）。 ——卸点的品位要求下限。（百分数）。 ——卸点的品位要求上限。（百分数）。 ——第辆卡车从铲点向卸点运输的次数。 ——卡车一次可运输的岩石量或矿石量（单位：吨）。 ——卡车的平均运行速度（单位：千米/小时）。 ——装车的时间（单位：分钟）。 ——卸车的时间（单位：分钟）。 ——铲位的个数。 ——铲车的数量（单位：台）。 ——卡车的数量（单位：台）。 ——一个班次的时间（单位：小时）。 ——需要矿石的卸点的个数； ——需要岩石的卸点的个数； 五、模型的建立 根据详细的分析和合理的假设，我们针对此类问题列出一般模型： (一) 模型的初建： 依据原则一建立数学模型： 目标：总运量最小和卡车数最少 约束条件：（1）满足卸点的产量要求。 （2）各个铲位运出的岩石量和矿石量不超出它的储量。 （3）卡车的数量不能超过现有的车辆数。 （4）电铲的数量不能超出现有的车辆数。 （5）满足各个卸点的品位要求。 （6）在不考虑随机因素的前提下，卡车不等待。 (二)模型的简化 ： 由于以上模型的求解比较复杂，因此我们将模型简化，分为两阶段来求解。 第一阶段： 这是一个单目标线性规划模型，可以求解出运输路线和运输次数。 第二阶段： 运用MATLAB软件求解 在第一阶段，我们可以得出运输次数的矩阵 1 用此矩阵按位乘以各个运输路线运输一次的运行时间，则可以得出各个运输路线的运输时间。 2 再将各个卸点的运输时间除以一个班次的时间就可以得出每个卸点应停的卡车数，这可能并不是最终结果。 3 将各个卸点的运输时间加和，得出总的运输时间，再用总的运输时间除以一个班次的时间，得出最少卡车数。 4 若2与3的结果不相同，则根据我们的原则，找出若干辆车来运输各个卸点不足一个班次的运量。直至达到满意的结果。 流程图见下：次数矩阵点乘时间矩阵得出各条路线的运输时间 开始 各条路线的运输时间除以一个班次的时间得出各条路线所需要的车辆数目，并输出车辆数目 将各条路线车辆数目 加和，设和为a输出a 将各条路线的输出时间 相加得出总运输时间 总输出时间除以一个班次的时间得出最小车辆数b，并输出b N 满意？ a=b? 调整 N Y Y 结束 (三)依据原则二得出的多目标模型： 1 目标: (1)产量最大； (2)岩石产量最大； (3)总运量最小。 2 约束条件: （1）满足卸点的产量要求； （2）各个铲位运出的岩石量和矿石量不超出它的储量； （3）卡车的数量不能超过现有的车辆数； （4）电铲的数量不能超出现有的车辆数； （5）满足各个卸点的品位要求； （6）在不考虑随机因素的前提下，卡车不等待。 第一阶段模型： 第二阶段模型： 六、模型的求解 根据实例： 某露天矿有铲位10个，卸点5个，现有铲车7台，卡车20辆。各卸点一个班次的产量要求：矿石漏1.2万吨、倒装场Ⅰ1.3万吨、倒装场Ⅱ1.3万吨、岩石漏1.9万吨、岩场1.3万吨。 各铲位和各卸点之间的距离（公里）如下表： 铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10 矿石漏 5.26 5.19 4.21 4.00 2.95 2.74 2.46 1.90 0.64 1.27 倒装场Ⅰ 1.90 0.99 1.90 1.13 1.27 2.25 1.48 2.04 3.09 3.51 岩场 5.89 5.61 5.61 4.56 3.51 3.65 2.46 2.46 1.06 0.57 岩石漏 0.64 1.76 1.27 1.83 2.74 2.60 4.21 3.72 5.05 6.10 倒装场Ⅱ 4.42 3.86 3.72 3.16 2.25 2.81 0.78 1.62 1.27 0.50 各铲位矿石、岩石数量(万吨)和矿石的平均铁含量如下表： 铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10 矿石量 0.95 1.05 1.00 1.05 1.10 1.25 1.05 1.30 1.35 1.25 岩石量 1.25 1.10 1.35 1.05 1.15 1.35 1.05 1.15 1.35 1.25 铁含量 30% 28% 29% 32% 31% 33% 32% 31% 33% 31% （一） 依据原则一的模型的求解： 我们用LINDO软件和MATLAB软件编制了程序，见附录。 得出依据原则一的卡车运行路线及运行时间： 卡车编号 第i个铲位 第j个卸点 次 数 时 间（分钟） 1 2 1 13 393.16 10 1 6 80.64 2 8 1 29 468.06 3 8 1 25 403.5 10 1 5 67.2 4 1 5 44 472.56 5 1 5 36 386064 3 5 8 83.52 6 3 5 35 470.4 7 2 2 39 477.36 8 2 2 1 12.24 4 2 36 462.3 9 2 3 15 368.14 10 3 10 101.43 10 10 3 47 476.7 11 9 4 38 476.6 12 10 4 15 156.04 9 4 25 313.5 13 9 4 7 87.78 10 3 23 233.22 4 2 9 115.56 1 5 1 10.74 第13辆车作为弥补各个卸点剩余的运量不足一个班次的问题。在这个调度过程中需要比预先多走一部分路程，比预先时间多出30分钟。但仍然不超过一个班次的运行时间。 路线图如下:（注：此图只表示供应关系，并不表示实际道路） 目标函数最优值为8.57万吨公里。需要卡车13辆；电铲7辆，分布在卸点1，2，3，4，8，9，10。 （二）依据原则二的模型的求解 根据实例，仍然用LINDO软件和 MATLAB软件求解，得出结果是： 卡车的编号 第个铲位 第个卸点 次数 时间（分钟） 1 3 1 18 468.72 2 3 1 2 52.08 8 1 26 419.64 3 8 1 29 468.06 4 1 2 15 242.1 8 2 9 150.7 4 2 6 77.04 5 2 2 39 477.36 6 2 2 29 354.96 4 2 9 115.56 7 4 2 37 475.08 8 8 3 8 119.5 3 3 15 359.14 9 3 3 20 478.86 10 3 3 9 215.49 10 3 26 263.7 11 10 3 26 263.7 9 3 9 120.96 9 4 4 50.16 12 8 4 21 389.4 9 4 7 87.8 13 10 4 44 459.5 9 4 1 12.54 14 9 4 38 476.52 15 9 4 38 476.52 16 4 5 19 301 1 5 16 171.84 17 2 5 28 435.2 1 5 4 42.97 18 3 5 32 430.2 1 5 4 42.97 19 1 5 44 472.56 20 1 5 13 139.62 8 1 4 64.56 4 2 16 205.44 第20辆车作为弥补各个卸点剩余的运量不足一个班次的问题。在这个调度过程中需要比预先多走一部分路程，比预先时间多出42分钟。但仍然不超过一个班次的运行时间。 路线图如下: （注：此图只表示供应关系，并不表示实际道路） 最优解为:最大产量为10.087万吨,其中岩石的产量为4.8048万吨,矿石的产量为5.2822万吨。 七、算法与结果的分析 针对原则一： 表一：对铲位供应量的分析 铲位 供应岩石量（吨） 供应矿石量（吨） 1 12474 0 2 0 10472 3 6622 0 4 0 6930 8 0 8316 9 10780 0 10 2310 12474 表二：对卸点需求量和矿石品位的分析 卸点 品位（百分数） 产量（吨） 1 30.5% 12012 2 30.17% 13090 3 30.48% 13090 4 13090 5 19096 由上表可见，结果满足所有限制条件，并且已经为最优解。按照运输总时间计算，最少卡车数应为12辆，但由于卸车时间的限制，只能为13辆，结果合理。 针对原则二： 表一：对铲位供应量的分析 铲位 供应岩石量（吨） 供应矿石量（吨） 1 12474 2310 2 4312 10472 3 4928 9856 4 2926 10472 8 3234 11704 9 13398 1386 10 6776 8008 表二：对卸点需求量和矿石品位的分析 卸点 品位（百分数） 产量（吨） 1 30.49% 12012 2 30.06% 24640 3 30.11% 17556 4 23408 5 24640 由上表可见，结果满足所有限制条件。用最大产量作为目标和用最大岩石产量作为目标结果相同。20辆卡车均被用上，结果合理。 经过模型简化后，我们做出的程序运行速度极快，在针对实例的运行过程中，运行时间不超过1秒，且跌代次数极少，在针对实例的运行过程中，跌代次数不超过50次，完全满足快速算法的要求。 在实际的运输工程中，随机因素很多，因此我们得出的结果是理想情况下的结果，对于结果的进一步分析在模型的改进方向中。 八、模型结果的检验 1.各模型结果的横向比较：经过计算机的多次运行，各模型的结果都相同，说明了解的稳定性比较好。 2.各模型结果的纵向比较：两个模型的结果相同，证明了简化后的模型的合理性。 九、模型的优缺点 1 优点： （1）模型的建立过程体现了模型由繁到简的过程。 （2）模型简化后，在计算机上求解，速度快，在假设检验中，我们通过两个模型结果的横向比较，说明了简化的合理性。 （3）模型中任何一个参数可以随意变化，不须改变模型，因此，可以方便地将其推广。 （4）本题用到的模型简单易懂。 2 缺点： 没有考虑随机因素的影响，因此得出的结果是理想的结果。在模型的改进方向中提出了有关这方面的想法。 十、模型的改进方向 从实际问题中考虑，运输中存在许多随机因素。对于此问题，我们可以根据经验，确定随机因素对运输过程的影响大小，再在模型中加限制条件。由于我们不知此问题的实际情况，因此只能得出理想的结果，决策者可以据实际情况进行调整。 附录：参考书目 [1] 甘应爱.运筹学.北京：清华大学出版社，1990年1月第2版。 [2] 何坚勇.运筹学基础.北京：清华大学出版社，2000年7月第1版。 [3] 陈 陈.优化方法与最优控制.北京：机械工业出版社，1993年5月第1版。 [4] 王永县.运筹学——规划论及网络.北京：清华大学出版社，1993年8月第1版。 程序和结果： 第一问题第一限制条件程序： model: min=5.26*n11+1.90*n12+4.42*n13+5.89*n14+0.64*n15+ 5.19*n21+0.99*n22+3.86*n23+5.61*n24+1.76*n25+ 4.21*n31+1.90*n32+3.72*n33+5.61*n34+1.27*n35+ 4.00*n41+1.13*n42+3.16*n43+4.56*n44+1.83*n45+ 2.95*n51+1.27*n52+2.25*n53+3.51*n54+2.74*n55+ 2.74*n61+2.25*n62+2.81*n63+3.65*n64+2.60*n65+ 2.46*n71+1.48*n72+0.78*n73+2.46*n74+4.21*n75+ 1.90*n81+2.04*n82+1.62*n83+2.46*n84+3.72*n85+ 0.64*n91+3.09*n92+1.27*n93+1.06*n94+5.05*n95+ 1.27*n101+3.51*n102+0.50*n103+0.57*n104+6.10*n105; (n11+n21+n31+n41+n51+n61+n71+n81+n91+n101)*154>=12000; (n12+n22+n32+n42+n52+n62+n72+n82+n92+n102)*154>=13000; (n13+n23+n33+n43+n53+n63+n73+n83+n93+n103)*154>=13000; (n14+n24+n34+n44+n54+n64+n74+n84+n94+n104)*154>=13000; (n15+n25+n35+n45+n55+n65+n75+n85+n95+n105)*154>=19000; (0.30*n11+0.28*n21+0.29*n31+0.32*n41+0.31*n51+0.33*n61+0.32*n71+0.31*n81+0.33*n91+0.31*n101)*154<=0.305*154*(n11+n21+n31+n41+n51+n61+n71+n81+n91+n101); (0.30*n12+0.28*n22+0.29*n32+0.32*n42+0.31*n52+0.33*n62+0.32*n72+0.31*n82+0.33*n92+0.31*n102)*154<=0.305*154*(n12+n22+n32+n42+n52+n62+n72+n82+n92+n102); (0.30*n13+0.28*n23+0.29*n33+0.32*n43+0.31*n53+0.33*n63+0.32*n73+0.31*n83+0.33*n93+0.31*n103)*154<=0.305*154*(n13+n23+n33+n43+n53+n63+n73+n83+n93+n103); (0.30*n11+0.28*n21+0.29*n31+0.32*n41+0.31*n51+0.33*n61+0.32*n71+0.31*n81+0.33*n91+0.31*n101)*154>=0.285*154*(n11+n21+n31+n41+n51+n61+n71+n81+n91+n101); (0.30*n12+0.28*n22+0.29*n32+0.32*n42+0.31*n52+0.33*n62+0.32*n72+0.31*n82+0.33*n92+0.31*n102)*154>=0.285*154*(n12+n22+n32+n42+n52+n62+n72+n82+n92+n102); (0.30*n13+0.28*n23+0.29*n33+0.32*n43+0.31*n53+0.33*n63+0.32*n73+0.31*n83+0.33*n93+0.31*n103)*154>=0.285*154*(n13+n23+n33+n43+n53+n63+n73+n83+n93+n103); 154*(n11+n12+n13)<=9500; 154*(n21+n22+n23)<=10500; 154*(n31+n32+n33)<=10000; 154*(n41+n42+n43)<=10500; 154*(n51+n52+n53)<=11000; 154*(n61+n62+n63)<=12500; 154*(n71+n72+n73)<=10500; 154*(n81+n82+n83)<=13000; 154*(n91+n92+n93)<=13500; 154*(n101+n102+n103)<=12500; 154*(n14+n15)<=12500; 154*(n24+n25)<=11000; 154*(n34+n35)<=13500; 154*(n44+n45)<=10500; 154*(n54+n55)<=11500; 154*(n64+n65)<=13500; 154*(n74+n75)<=10500; 154*(n84+n85)<=11500; 154*(n94+n95)<=13500; 154*(n104+n105)<=12500; 30.5429*n11+30.2429*n21+26.0429*n31+25.1429*n41+20.6429*n51+19.7429*n61+18.5429*n71+16.1429*n81+10.7429*n91+13.4429*n101+ 16.1429*n12+12.2429*n22+16.1429*n32+12.8429*n42+13.4429*n52+17.6429*n62+14.3429*n72+16.7429*n82+21.2429*n92+23.0429*n102+ 26.9429*n13+24.5429*n23+23.9429*n33+21.5429*n43+17.6429*n53+20.0429*n63+11.3429*n73+14.9429*n83+13.4429*n93+10.1429*n103+ 33.2429*n14+32.0429*n24+32.0429*n34+27.5429*n44+23.0429*n54+23.6429*n64+18.5429*n74+18.5429*n84+12.5429*n94+10.4429*n104+ 10.7429*n15+15.5429*n25+13.4429*n35+15.8429*n45+19.7429*n55+19.1429*n65+26.0429*n75+23.9429*n85+29.6429*n95+34.1429*n105 <=8*20*60; n11+n21+n31+n41+n51+n61+n71+n81+n91+n101<=160; n12+n22+n32+n42+n52+n62+n72+n82+n92+n102<=160; n13+n23+n33+n43+n53+n63+n73+n83+n93+n103<=160; n14+n24+n34+n44+n54+n64+n74+n84+n94+n104<=160; n15+n25+n35+n45+n55+n65+n75+n85+n95+n105<=160; n11+n12+n13+n14+n15<=96; n21+n22+n23+n24+n25<=96; n31+n32+n33+n34+n35<=96; n41+n42+n43+n44+n45<=96; n51+n52+n53+n54+n55<=96; n61+n62+n63+n64+n65<=96; n71+n72+n73+n74+n75<=96; n81+n82+n83+n84+n85<=96; n91+n92+n93+n94+n95<=96; n101+n102+n103+n104+n105<=96; End 第一问题限制条件程序结果： Global optimal solution found at iteration: 47 Objective value: 550.8388 Variable Value Reduced Cost N11 0.000000 2.216667 N12 0.000000 0.7700000 N13 0.000000 2.333333 N14 0.000000 5.460000 N15 81.16883 0.000000 N21 12.98701 0.000000 N22 41.12554 0.000000 N23 14.06926 0.000000 N24 0.000000 4.550000 N25 0.000000 0.4900000 N31 0.000000 0.2333333E-01 N32 0.000000 0.7700000 N33 0.000000 0.6766667 N34 0.000000 4.550000 N35 42.20779 0.000000 N41 0.000000 3.243333 N42 43.29004 0.000000 N43 0.000000 2.986667 N44 0.000000 3.500000 N45 0.000000 0.5600000 N51 0.000000 0.9100000 N52 0.000000 0.000000 N53 0.000000 0.9800000 N54 0.000000 2.310000 N55 0.000000 1.330000 N61 0.000000 3.126667 N62 0.000000 1.120000 N63 0.000000 3.593333 N64 0.000000 2.590000 N65 0.000000 1.330000 N71 0.000000 1.353333 N72 0.000000 0.000000 N73 0.000000 0.2566667 N74 0.000000 1.050000 N75