露天矿生产的车辆安排（问题一的模型与求解）摘要本文针对2003年全国大学生数学建模赛题B的第一问建立了露天矿生产的总运量最优（目标一）和车辆安排最优（目标二）的数学模型。
首先，依据题目中的原则一，以及铲位、卸点、产量、品位、卡车不等待等诸多因素，分析出主次约束，在探讨的过程中对影响程度小的因素作出了合理的假设，明确目标函数，并对部分变量进行了整数约束或0-1约束，建立了双目标函数的整数规划模型。
其次，考虑到双目标函数同时求解的困难性，但又考虑到快速算法的实际需要，我们采用了“舍二求一法”，分别对两个目标进行了取舍性探究，并借助于LINGO软件的快速辅助计算（程序见附录），得出两种取舍法的相应结果，然后我们对两个结果进行了比较，并利用“递减决策法”对所得的结果合理性和最优性予以验证，经过回归实际探讨后给出了第一原则下的总运量和出动车辆的最优解，且根据计算所得的数据对出动的车辆具体安排情况列出表格（具体见表5），以供明览。
最后，我们综合评价了模型的优缺点，并阐述了模型在实际生产应用中的改进和推广，对于此类生产安排问题的决策者有一定的参考和指导意义。
关键词：多目标规划 0-1约束舍二求一法递减决策法1．问题重述与分析（1）问题重述某露天矿内有若干个铲位，铲位中已按铁含量将石料分为矿石和岩石（平均铁含量不低于25%的为矿石，否则为岩石）。
每个铲位至多能安置一台电铲，电铲的平均装车时间为5分钟。
卡车负责将铲位内的矿石和岩石运送到相应的卸货地点，卡车的平均卸车时间为3分钟。
卸货地点有卸矿石的矿石漏和2个铁路倒装场，卸岩石的岩石漏和岩场，总共五个卸点。
按要求，矿石卸点需要的铁含量品位限制都为29.5% 1%（在一个班次8小时内满足品位限制即可）。
km。
原则上在安排时不应发生卡所用卡车载重量为154吨，平均时速28h车等待的情况，电铲和卸点都不能同时为两辆及两辆以上卡车服务。
卡车每次都是满载运输，并且排除堵车现象。
一个班次的生产计划包含以下内容：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上。
一个合格的计划要在卡车不等待条件下满足产量和质量（品位）要求。
一个好的计划应该考虑下面两条原则之一：1.总运量（吨*公里）最小，同时出动最少的卡车，从而运输成本最小；2.利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。
问题一：就两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。
问题二：针对下面的实例，给出具体的生产计划、相应的总运量及岩石和矿石产量。
某露天矿有铲位10个，卸点5个，现有铲车7台，卡车20辆。
各卸点一个班次的产量要求：矿石漏1.2万吨、倒装场Ⅰ1.3万吨、倒装场Ⅱ1.3万吨、岩石漏1.9万吨、岩场1.3万吨。
各铲位和各卸点之间的距离（公里）如下表：各铲位矿石、岩石数量(万吨)和矿石的平均铁含量如下表：（表2）我们认为上表中给出的各铲位矿石、岩石数量为每个班次所能提供的最大量，矿石的平均铁含量恒定。
（2）问题分析首先，我们先考虑“一个合格的计划”要求，一个合格的计划要在卡车不等待条件下满足产量限制和品位限制，同时每个铲位一个班次的铲量和每个卸点一个班次的卸量也是有限制的，这点根据卡车装货时间5分钟，卡车卸货时间3分钟能够求出最大铲(卸)量，而又因铲车总数少于铲位总数故一个班次一定存在部分铲位无铲车铲矿，我们可以用0-1变量来达到这一约束，对于安排的车辆和车辆运输次数均应为整数，即模型部分变量（本文指运输次数）需用约束为整数取值。
其次，我们再分析“一个良好的计划”要求，一个好的计划应遵循原则一，即使总运量（吨*公里）最小，同时出动最少的卡车，以使投入的运输成本最低。
总运量由运输次数和运输路程决定，而运输次数又由卡车数量、铲（卸）量决定，运输路程由铲车位置、卸点最低产量决定，这样又回溯到“一个合格的计划”要求中的诸多限制中去。
显然，我们应该选择总运量和出动卡车数为此规划的目标函数，整个从铲位到运输到卸点的诸多限制因素便是两个目标函数的约束条件。
最后，通过合理的设出相应变量并用变量表示出约束条件和目标函数的表达式，我们便建立出该问题的数学模型。
这是一个双目标的整数非线性规划问题，在求解时，我们选择“舍二求一”转化为单目标的线性规划问题求解，借助于LINGO的软件求出结果，随即对结果进行了比较和带回实际要求进行探讨验证。
综合得出总运量的最优解和安排卡车的数量。
2．模型假设与符号说明（1）题目提供的相关统计数据真实可信符合实际；（2）不同铲位到达同一卸点的卡车数量不会在3分钟时间内超过两辆和两辆以上；（3）每个电铲和和铲位在一个班次内固定且卡车工作的路线固定；（4）运输过程中不会出现卡车堵车情况，路况优良，加油和司机休息时间不计 ； （5）一个班次铲车和卡车同一时刻开始工作，工作八小时后在同一时刻结束工作；（2）符号说明()i=1,2...10 j=1,2...5ij X 代表安排在第i 个铲位到第j 个卸点的卡车数；（个）ij Y 代表每辆卡车在第i 个铲位和第j 个卸点一个班次运输次数（次/辆）；()i=1,2...10 j=1,2...5ij d 代表第i 个铲位和第j 个卸点之间的距离（公里）； 10i i i f i f i f == 代表第个铲位有无铲车情况，表示第个铲位有一台铲车，反之；R i 代表第i 个铲位的岩石量； N i 代表第i 个铲位的矿石量；P i 代表第i 个铲位矿石的平均铁含量； M j 代表第j 个卸点产量的要求量；（吨）其他符号在模型中运用时再作说明。
3．模型建立与求解首先，根据上面对问题的分析，我们可以列出如下两个目标函数的表达式：510111510211min 154min ij ijijj i ijj i Z X Y dZ X=====⨯=∑∑∑∑接着，我们逐个找出约束条件：1. 由于卡车装货5分钟，卸货3分钟，且电铲每次只能为一辆车提供服务，故每条线路对于卡车数和运输次数有限制，对于一辆卡车在一条线路上运输一个周期的时间为：260/2835()ij ij T d =⨯⨯++分，因此在不等待条件下，每条线路最多可同时运行的卡车数/5ij ij A T ⎢⎥=⎣⎦（此处对最大运行卡车数取整，但在后文中对具体路线卡车数并未取整）。
一个班次从开始装车到最后一俩车的时间差为(1)5ij A -⨯，故一个班次该条路线允许的最大运输次数为860(1)5ij ij ij A B T ⎢⎥⨯--⨯=⎢⎥⎢⎥⎣⎦，这样可列出路线约束表达式：;;;ij ij ij ij ij ij ij ij X A Y B X Y A B ≤=⨯≤⨯2. 一个班次每个卸点产量的最低要求：4101M 10154j ij iji X Y=⨯≥∑3. 矿石品位限制要求：10110128.530.5ij ij ii ij iji X Y PX Y==%≤≤%∑∑4. 铲位每班次装货次数最大为：860965⨯= 故每铲位总运输次数限制有： 5196ij iji j X Yf =≤⨯∑5. 卸点每个班次卸货次数最大为：8601603⨯= 故每卸点的总运输次数限制有： 101160ij iji X Y=≤∑6. 每个铲位的矿石量和岩石量最大量限制，25143154(1,2, (10)154(1,2, (10)ij iji j ij iji j X YN i X YR i ==⨯≤=⨯≤=∑∑和7. 铲车数量和卡车数量限制：1017ii f=≤∑51011020ijj i X==≤≤∑∑这样我们便建立了如下的双目标整数规划模型：510111510211min 154min ij ijijj i ijj i Z X Y dZ X====⎧=⨯⎪⎪⎨⎪=⎪⎩∑∑∑∑s.t.4101101101;;;M 1015428.530.5ij ij ij ij ij ijij ijj ij ij i ij ij i i ij ij i X A Y B X Y A B X Y X Y P X Y ===≤⎧⎪=⎪⎪⨯≤⨯⎪⎪⨯≥⎪⎪⎨⎪⎪⎪%≤≤%⎪⎪⎪⎪⎩∑∑∑51101251431015101196160154(1,2,...,10)154(1,2, (10)7020ij ij i j ij ij i ij ij i j ij ij i j i i ij j i X Y f X Y X Y N i X Y R i f X 和=======⎧≤⨯⎪⎪⎪≤⎪⎪⎪⨯≤=⎪⎪⎨⎪⨯≤=⎪⎪⎪≤⎪⎪⎪≤≤⎪⎩∑∑∑∑∑∑∑（2）模型求解这是一个双目标的非线性整数规划模型，为使模型转化为线性的我们深入分析了目标函数的两个变量Y ij ij X 和，根据装卸时间的约束我们知道ij Y 有个最大的允许值ij B ，于是可令;ij ij Y B =将其转化为定量，同时也符合题意的原则一（即在各道路实际总运输次数一定情况下使每辆卡车运输次数达到最大，可使卡车的出动数最小）。
对于线性化后的双目标模型，我们采用“舍二求一法”，分别将两个目标函数中的一个视为主目标函数，另一个转化为约束条件，即简化成单目标的线性规划模型。
因题目原则一要求优先考虑总运量最小，在此基础之上考虑调派最少卡车数，所以我们先以总运量：1min Z 为目标函数。
借助LINGO 软件计算结果如下：8.56286•总运量最优解： （万吨公里）对应出动车辆数：12.98666（辆）对应岩石产量：3.2186 （万吨）对于矿石产量：38192（万吨）然后将目标函数改为总出动卡车数：510211min ijj i Z X===∑∑，再利用LINGO 计算，并输出此时的总运量，结果显示出动的车辆依然为12.98666，总运量也是8.56286，这说明上面得出的总运量最优解对应的卡车数量即是出动数的最优解。
对于双目标函数，采用上述逐个求解，得到的结果恰好一致，存在偶然性，对此我们用“递减决策法”对结果的合理性和最优性予以说明。
即在LINGO 程序中对限制51011020ijj i X==≤≤∑∑（即卡车数量限制）的下限进行从19到11的逐一递减，得出一组递减约束下的总运量最优解和对应所需出动卡车数的数据，见下表：由上面的表格中数据，可知卡车数大于13时总运量随着出动卡车数的减少而减少，当出动卡车数低于13量时不再变化，而最少出动卡车数依然是12.98666辆，因此可以得出总运量最优解是8.562862（万吨*公里）时，所需出动的最少卡车数的最优解就是13辆（在此只能进一取整）！其次，我们分析对13卡车的运输方案，由LINGO 计算出的结果列出如下表格：通过对上面表格中的所需卡车数、实际运输次数、最大运输次数的比较，本着原则一，对得出的车次结果合理取舍、并权衡矿厂利益取整后得出具体的卡车运输方案如下表：（表5 卡车安排及运输方案）之间调动方法解决，在此不再追加论述。