数学建模竞赛中的部分课件

2.1一个飞行管理问题一个飞行管理问题2.1.1 2.1.1 问题描述问题描述1995年全国大学生数学建模竞赛中的年全国大学生数学建模竞赛中的A题（题（“一一个飞行管理问题个飞行管理问题”）。）。在约在约10000米高空的某边长为米高空的某边长为160km的正方形区的正方形区域内，经常有若干架飞机做水平飞行，区域内每域内，经常有若干架飞机做水平飞行，区域内每架飞机的位置和速度向量均由计算机记录其数据，架飞机的位置和速度向量均由计算机记录其数据，以便进行飞行管理，当一架欲进入该区域的飞机以便进行飞行管理，当一架欲进入该区域的飞机到达区域边缘时，记录其数据后，要立即计算并到达区域边缘时，记录其数据后，要立即计算并判断是否会与区域内的飞机发生碰撞。判断是否会与区域内的飞机发生碰撞。现假定条件如下：现假定条件如下：不碰撞的标准为任意两架飞机的距离大于不碰撞的标准为任意两架飞机的距离大于8km；飞机飞行方向角调整幅度不应超过飞机飞行方向角调整幅度不应超过30；所有飞机飞行速度均为所有飞机飞行速度均为800kmh；进入该区域的飞机在到达该区域边缘时，进入该区域的飞机在到达该区域边缘时，与区域内飞机的距离应在与区域内飞机的距离应在60km以上；以上；最多需考虑最多需考虑6架飞机；架飞机；不必考虑飞机离开此区域后的情况。不必考虑飞机离开此区域后的情况。请你对这个避免碰撞的飞行管理问题建立数学模请你对这个避免碰撞的飞行管理问题建立数学模型，列出计算步骤，对以下数据进行计算（方向型，列出计算步骤，对以下数据进行计算（方向角误差不超过角误差不超过0.01），要求飞机飞行方向角调整），要求飞机飞行方向角调整的幅度尽量小。的幅度尽量小。该区域四个定点的坐标为（该区域四个定点的坐标为（0，0）、（160，0）、（160，160）、（、（0，160）。）。记录数据见表记录数据见表21。表表21飞机位置和方向角记录数据飞机位置和方向角记录数据飞机编号横坐标纵坐标方向角（飞机编号横坐标纵坐标方向角（）飞机编号横坐标）飞机编号横坐标x纵纵坐标坐标y方向角（方向角（）飞机编飞机编号号横坐横坐标标纵坐纵坐标标方向角方向角（）飞机编飞机编号号横坐横坐标标x x纵坐纵坐标标y y方向角方向角（）1 11501501401402432434 414514550501591592 2858585852362365 51301301501502302303 31551551551552202205 5新进入新进入0 00 05252说明：说明：方向角指飞行方向与方向角指飞行方向与x轴正向的夹角轴正向的夹角。试根据实际应用背景对你的模型进行评价和推广试根据实际应用背景对你的模型进行评价和推广 212模型一及求解模型一及求解模型建立模型建立这个问题显然是一个优化问题。设第这个问题显然是一个优化问题。设第i 架飞架飞机在调整时的方向角为机在调整时的方向角为（题目中已给出）（题目中已给出），调整后的方向为，调整后的方向为，题目，题目中就是要求飞机飞行方向角调整的幅度尽中就是要求飞机飞行方向角调整的幅度尽量小，因此有化的目的函数可以是：量小，因此有化的目的函数可以是：（1）为了建立这个问题的优化模型，只需要明确约束为了建立这个问题的优化模型，只需要明确约束条件就可以了。一个简单的约束是飞机飞行方向条件就可以了。一个简单的约束是飞机飞行方向角调整的幅度不应超过角调整的幅度不应超过30，即，即（2）题目中要求进入该区域的飞机在到达该区题目中要求进入该区域的飞机在到达该区域边缘时，与区域内的飞机的距离应在域边缘时，与区域内的飞机的距离应在60km以上。这个条件是个初始条件，很容以上。这个条件是个初始条件，很容易验证目前所给的数据是满足的，因此本易验证目前所给的数据是满足的，因此本模型中可以不予考虑。剩下的关键是模型中可以不予考虑。剩下的关键是要满要满足题目中描述的任意两架位于该区域内的足题目中描述的任意两架位于该区域内的飞机的距离应该大于飞机的距离应该大于8km。但这个问题的。但这个问题的难点在于飞机是动态的，这个约束不好直难点在于飞机是动态的，这个约束不好直接描述，为此我们首先需要描述每架飞机接描述，为此我们首先需要描述每架飞机的飞行轨迹。的飞行轨迹。记飞机飞行速率为（记飞机飞行速率为（800kmh），以当前），以当前时刻为时刻为0时刻。设第时刻。设第架飞机在调整时的位架飞机在调整时的位置坐标为置坐标为（已知条件），时刻的位（已知条件），时刻的位置坐标为置坐标为，则，则（3）如果要严格表示两架位于该区域内的飞机如果要严格表示两架位于该区域内的飞机的距离应大于的距离应大于8km，则需要考虑每架飞机，则需要考虑每架飞机在区域内的飞行时间的长度。记在区域内的飞行时间的长度。记Ti为第为第架飞机飞出区域的时间，即架飞机飞出区域的时间，即（4）记记时刻第时刻第架飞机与第架飞机与第架飞机的距离为架飞机的距离为，并记，并记，这时在区域内飞，这时在区域内飞机不相撞的约束条件就变成了机不相撞的约束条件就变成了 （5）其中其中（6）此外，经过计算可以得到此外，经过计算可以得到 （7）（8）（9）（10）所以所以是一个关于是一个关于t 的二次函数，表示的的二次函数，表示的是一条开口向上的抛物线。当是一条开口向上的抛物线。当即即（记为（记为）时，）时，函数取最小函数取最小值值。注意到。注意到（初始时刻不相（初始时刻不相撞），如果撞），如果（即（即）则此时约束条）则此时约束条件（件（5）一定成立，所以）一定成立，所以如果如果且且，只要在右端点的函数值，只要在右端点的函数值非负即可，即非负即可，即 （11）如果如果且且，只需要求最小值，只需要求最小值即可，即即可，即（12）实际上，约束（实际上，约束（11）表示的是）表示的是在右端点在右端点的函数值非负，这个约束在（的函数值非负，这个约束在（12）的条件）的条件下也是自然成立的，所以可以是对约束下也是自然成立的，所以可以是对约束（11）不再附加且的条件。）不再附加且的条件。于是我们的模型就是于是我们的模型就是（13）（14）（15）（16）模型求解模型求解上面这是一个非线性规划模型，虽然是严格上面这是一个非线性规划模型，虽然是严格满足题目要求的模型，但得到的模型逻辑关满足题目要求的模型，但得到的模型逻辑关系比较复杂，约束（系比较复杂，约束（16）是在一定条件下才）是在一定条件下才成立的约束，而且其中的计算式（成立的约束，而且其中的计算式（4）也含有）也含有相当复杂的关系式，使用相当复杂的关系式，使用LINGO软件不太容软件不太容易将模型很方便的输入，因为逻辑处理不是易将模型很方便的输入，因为逻辑处理不是LINGO的优势所在。即使想办法把这个模型的优势所在。即使想办法把这个模型输入到输入到LINGO，也不一定能求出好的解（笔，也不一定能求出好的解（笔者尝试过，但是者尝试过，但是LINGO运行时有时会出现系运行时有时会出现系统内部错误，可能是系统有问题，无法继续统内部错误，可能是系统有问题，无法继续求解）。而且，在实时飞行调度中显然需要求解）。而且，在实时飞行调度中显然需要快速求解，所以下面我们想办法简化模型。快速求解，所以下面我们想办法简化模型。这个模型麻烦之处就在于，要求严格表示这个模型麻烦之处就在于，要求严格表示两架飞机的飞行距离应大于两架飞机的飞行距离应大于8km，所以需，所以需要考虑每架飞机在区域内的飞行时间的长要考虑每架飞机在区域内的飞行时间的长度，比较繁琐。注意到区域对角线的长度度，比较繁琐。注意到区域对角线的长度只有只有，任何一架飞机在所考虑的区域，任何一架飞机在所考虑的区域内停留的时间不会超内停留的时间不会超过过。因此这里我们简化一下问题；。因此这里我们简化一下问题；不再单独考虑每架飞机在区域内停留的时不再单独考虑每架飞机在区域内停留的时间，而是以最大时间间，而是以最大时间（这是已经是一个常（这是已经是一个常数）代替之，此时所有数）代替之，此时所有，这实际上，这实际上强化了问题的要求，即考虑了有些飞机可强化了问题的要求，即考虑了有些飞机可能已经飞出区域，但仍不允许两架飞机的能已经飞出区域，但仍不允许两架飞机的距离小于距离小于8km。程序：程序：MODEL:TITLE飞行管理问题的非线性规划模型飞行管理问题的非线性规划模型;SETS:Plane/1.6/:x0,y0,cita0,cita1,d_cita;!cita0表示初始角度，表示初始角度，cita1为调整后的角度为调整后的角度,d_cita为调整的角度为调整的角度;link(plane,plane)|&1#LT#&2:b,c;ENDSETSDATA:1501402438585236150155220.5145501591301502300052x0y0cita0=max_cita=30;T_max=0.283;V=800;ENDDATAINIT:d_cita=000000;ENDINITfor(plane:cita1-cita0=d_cita);for(link(i,j):b(i,j)=-2*(x0(i)-x0(j)*sin(cita1(i)+cita1(j)*3.14159265/360)+2*(y0(i)-y0(j)*cos(cita1(i)+cita1(j)*3.14159265/360);c(i,j)=(x0(i)-x0(j)2+(y0(i)-y0(j)2-64;);!避免碰撞的条件避免碰撞的条件;!右端点非负右端点非负;for(link(i,j):Right(2*V*T_max*sin(cita1(i)-cita1(j)*3.14159265/360)2+b(i,j)*(2*V*T_max*sin(cita1(i)-cita1(j)*3.14159265/360)+c(i,j)0);!最小点非负最小点非负;for(link(i,j):Minimumif(b(i,j)#lt#0#and#-b(i,j)/4/V/sin(cita1(i)-cita1(j)*3.14159265/360)#gt#0#and#-b(i,j)/4/V/sin(cita1(i)-cita1(j)*3.14159265/360)#lt#T_max,b(i,j)2-4*c(i,j),-1)0);!for(link(i,j):if(b(i,j)#lt#0,b(i,j)2-4*c(i,j),-1)0);for(link:free(b);!调整角度上下限，单位为角度调整角度上下限，单位为角度;for(plane:bnd(-max_cita,d_cita,max_cita);objMIN=SUM(plane:(d_cita)2);!objMIN=SUM(plane:abs(d_cita);END运行这个程序，结果得到的是一个局部极小点，调运行这个程序，结果得到的是一个局部极小点，调整角度较大。能找到更好的解吗？如果不用全局求整角度较大。能找到更好的解吗？如果不用全局求解程序，通常很难得到稍大规模的非线性规划问题解程序，通常很难得到稍大规模的非线性规划问题的全局最优解。所以我们启动的全局最优解。所以我们启动LINGO全局求解程序全局求解程序求解这个模型（过程省略），可以得到全局最优解。求解这个模型（过程省略），可以得到全局最优解。可以看出，在可以看出，在0.01度的误差要求下，需要调整第度的误差要求下，需要调整第3、4、6三架飞机的角度，分别调整三架飞机的角度，分别调整2.06度、度、0.5度、度、1.57度度，调整量的平方和为，调整量的平方和为6.95。其实，使用全局变量求解程序，通常也不一定要等其实，使用全局变量求解程序，通常也不一定要等到全局最优解，而是观察求解状态窗口，看到一个到全局最优解，而是观察求解状态窗口，看到一个较好的当前解（或当前最好解在较长时间内不发生较好的当前解（或当前最好解在较长时间内不发生变化）时，就可以中止程序，用当前最好的局部最变化）时，就可以中止程序，用当前最好的局部最优解作为最后结果。例如对于本例，优解作为最后结果。例如对于本例，LINGO求出最求出最优解大约需要一分，而实际上优解大约需要一分，而实际上5秒内秒内LINGO得到了得到了与全局最优解类似的解。与全局最优解类似的解。此外此外，上面的模型还可以进一步简化，例如可，上面的模型还可以进一步简化，例如可以假设要求飞机永远不相撞，即认为为无穷大，以假设要求飞机永远不相撞，即认为为无穷大，这时显然约束条件（这时显然约束条件（15）是多余的，而且约束）是多余的，而且约束（16）中只需要的条件就可以了。也就是说上）中只需要的条件就可以了。也就是说上面程序中的对应部分（约束和可以改写为更简面程序中的对应部分（约束和可以改写为更简单的形式：单的形式：！右端点非负，不再需要；！右端点非负，不再需要；！最小点非负，需化为以下形式：！最小点非负，需化为以下形式：实际计算结果显示，此时得到的结果与前面计实际计算结果显示，此时得到的结果与前面计算的结果几乎没有差别。算的结果几乎没有差别。备注：优化的目标函数除了备注：优化的目标函数除了外，也可以假定为外，也可以假定为或或等，用等，用LINGO求解的过程的求解的过程的是完全类似的，计算结果略有差异，这里就不再对这个目是完全类似的，计算结果略有差异，这里就不再对这个目标函数进行计算了，甚至可以考虑让参与调整的飞机的数标函数进行计算了，甚至可以考虑让参与调整的飞机的数量尽量少，这种想法在实际中也不能说没有道理，但与题量尽量少，这种想法在实际中也不能说没有道理，但与题目的要求不符，而且解题难度并没有减小，意义似乎不大。目的要求不符，而且解题难度并没有减小，意义似乎不大。在实际调度中，由于计算上面的调度方案，需要时间将调在实际调度中，由于计算上面的调度方案，需要时间将调度信息告知飞机驾驶员并做出调整方向角的操作也需要时度信息告知飞机驾驶员并做出调整方向角的操作也需要时间，因此如果考虑一定的反应滞后时间应该是比较合理的。间，因此如果考虑一定的反应滞后时间应该是比较合理的。也就是说，如果反应时间是也就是说，如果反应时间是10秒，则计算中应采用飞机沿秒，则计算中应采用飞机沿当前方向角飞行当前方向角飞行10秒以后的位置作为计算的基础。秒以后的位置作为计算的基础。2.2钢管订购和运输钢管订购和运输2.2.12.2.1问题描述问题描述要铺设一条要铺设一条的输送天然气的主管道的输送天然气的主管道,如图一所示如图一所示(见下页见下页)。经筛选后可以生产这种主管。经筛选后可以生产这种主管道钢管的钢厂有道钢管的钢厂有。图中粗线表示铁路，。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道单细线表示公路，双细线表示要铺设的管道(假设假设沿管道或者原来有公路，或者建有施工公路沿管道或者原来有公路，或者建有施工公路)，圆，圆圈表示火车站，每段铁路、公路和管道旁的阿拉圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程伯数字表示里程(单位单位km)。为方便计，为方便计，1km主管道钢管称为主管道钢管称为1单位钢管。单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂个单位。钢厂在指定期限内能生产该钢管在指定期限内能生产该钢管的最大数量为的最大数量为个单位，钢管出厂销价个单位，钢管出厂销价1单位钢管单位钢管为为万元，如下表：万元，如下表：1 12 23 34 45 56 67 78008008008001000100020002000200020002000200030003000160160155155155155160160155155150150160160里程里程(km)(km)300300301301350350351351400400401401450450451451500500运价运价(万元万元)20202323262629293232里程里程(km)(km)50150160060060160170070070170180080080180190090090190110001000运价运价(万元万元)373744445050555560601000km以上每增加以上每增加1至至100km运价增加运价增加5万元。万元。公路运输费用为公路运输费用为1单位钢管每公里单位钢管每公里0.1万元（不万元（不足整公里部分按整公里计算）。足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点，钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。而是管道全线）。（1）请制定一个主管道钢管的订购和运输计划，使总）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用费用最小（给出总费用)。（2）请就（）请就（1）的模型分析：哪个钢厂钢管的销价的）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。并给出相应的数字结果。（3）如果要铺设的管道不是一条线，而是一个树形图，）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（给出一种解决办法，并对图二按（1）的要求给出模型）的要求给出模型和结果。和结果。图一A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A11A711A11A8A11A911A11A10A11A12A13A14A15S1S2S3S4S5S6S7图一图二 A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A19130190260100A2A3A4A5A6A7A8A11A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16A17A18A20(A21)图二 2.2.2运费矩阵的计算模型运费矩阵的计算模型问题分析问题分析我们只考虑本题第一问的求解。首先，所我们只考虑本题第一问的求解。首先，所有钢管必须要运到天然气主管道铺设线路有钢管必须要运到天然气主管道铺设线路上的结点上的结点，然后才能向左或向右铺，然后才能向左或向右铺设。因此，必须求出从每个钢管厂设。因此，必须求出从每个钢管厂（记为（记为i=1，2，7）到每个结）到每个结点点（记为（记为j=1，2，15）的每）的每单位钢管的最小运费单位钢管的最小运费（不妨称为运费矩阵）（不妨称为运费矩阵）及其对应的运输方式和路线。及其对应的运输方式和路线。因为题目中没有给出装卸成本，我们简单地假设总是因为题目中没有给出装卸成本，我们简单地假设总是采用最经济的运输方式，虽然这个假设在实际中可能采用最经济的运输方式，虽然这个假设在实际中可能不太接近事实。也就是说，在运输过程中需要多次装不太接近事实。也就是说，在运输过程中需要多次装卸也是允许的（如铁路转公路，再转铁路，等等）。卸也是允许的（如铁路转公路，再转铁路，等等）。自然的想法是运输路线应该是走最短路径，但由于有自然的想法是运输路线应该是走最短路径，但由于有两种运输和计价方式（铁路和公路），公路运输费用两种运输和计价方式（铁路和公路），公路运输费用为为1单位钢管每公里单位钢管每公里0.1万元（不足整公里部分按整公万元（不足整公里部分按整公里计算），运费是路程的线性函数；然而，铁路运输里计算），运费是路程的线性函数；然而，铁路运输要通过运输里程查表得到，是一个阶梯函数，这两种要通过运输里程查表得到，是一个阶梯函数，这两种运输计价方式混合在一起，使得我们不能直接在整个运输计价方式混合在一起，使得我们不能直接在整个铁路、公路混合的运输网络上计算最短路径作为运输铁路、公路混合的运输网络上计算最短路径作为运输路线，但可以分别在铁路、公路网上计算最短路径，路线，但可以分别在铁路、公路网上计算最短路径，然后换算成相应的费用；最后在整个网络上以两个子然后换算成相应的费用；最后在整个网络上以两个子网上相应的运费为权，再求一次最短路问题，就可以网上相应的运费为权，再求一次最短路问题，就可以把它们统一成一个标准的运费矩阵。把它们统一成一个标准的运费矩阵。铁路子网络铁路子网络假设铁路运输路线应该是走最短路径，而且采用假设铁路运输路线应该是走最短路径，而且采用连续路径计价方式一定优于分段计价方式（其实连续路径计价方式一定优于分段计价方式（其实题中数据并不符合这一假定，例如题中题中数据并不符合这一假定，例如题中650km的的运价计为运价计为44万元，而分成万元，而分成300km和和350km两段计两段计价只需要价只需要43万元，这种情况应该是不太符合实际万元，这种情况应该是不太符合实际的，可能是命题时选择数据的疏忽，我们不过多的，可能是命题时选择数据的疏忽，我们不过多地考虑这种情况）。这时我们可以把铁路运输子地考虑这种情况）。这时我们可以把铁路运输子网独立出来，在这个网络上计算任意两个节点网独立出来，在这个网络上计算任意两个节点i，j之间的最短路之间的最短路，然后按照这个最短路长度查铁，然后按照这个最短路长度查铁路运价表得到最小运费路运价表得到最小运费。在无向网络上求任意两点之间最短路的算法很多，在无向网络上求任意两点之间最短路的算法很多，尤其对本题这种弧上的权（距离）全为正数的情尤其对本题这种弧上的权（距离）全为正数的情况，存在相对比较简单的算法。例如，求任意两况，存在相对比较简单的算法。例如，求任意两点之间最段路径的点之间最段路径的Floyd-Warshall算法是算法是 这实际上是一种标号算法，其中这实际上是一种标号算法，其中n是网络中是网络中的节点数（节点编号为的节点数（节点编号为1，2，n）；）；是给定的网络上相邻接点是给定的网络上相邻接点i，j之间的之间的直接距离（直接距离（i，j不相邻时取不相邻时取充分大就可以充分大就可以了）；了）；可以看成任意两个接点可以看成任意两个接点i，j之间距之间距离的中间迭代值（或称为临时编号），既离的中间迭代值（或称为临时编号），既成节点成节点i到到j但不允许经过其他节点但不允许经过其他节点k，k+1，n时的最短距离；自然时的最短距离；自然就是就是i，j之间的最短距离（或称为永久标号），即之间的最短距离（或称为永久标号），即。公路子网络公路子网络类似地，可以假设公路运输路线应该是走类似地，可以假设公路运输路线应该是走最短路径，把公路运输子网独立出来，在最短路径，把公路运输子网独立出来，在这个网络上计算任意两个节点这个网络上计算任意两个节点i，j之间的最之间的最短路长度短路长度，然后按照这个最短路长度乘，然后按照这个最短路长度乘以以0.1得到最小费用得到最小费用（因为公路运输费用（因为公路运输费用为为1单位钢管每公里单位钢管每公里0.1万元）。万元）。购运费用矩阵购运费用矩阵在次基础上，就可以将以上两个子网络（需要分在次基础上，就可以将以上两个子网络（需要分别看成两个完全子图）组合成一个网络，每条弧别看成两个完全子图）组合成一个网络，每条弧上相应的运费上相应的运费或或为权（如果某条弧（为权（如果某条弧（i，j）上）上既有铁路运费既有铁路运费，又有公路运费，又有公路运费，只需要取其，只需要取其中较小的一个即可）。此时，再计算从每个钢管中较小的一个即可）。此时，再计算从每个钢管厂厂（记为（记为i=1，2，7）到每个节点）到每个节点（记为（记为j=1，2，15）的最短路，）的最短路，得到的就是每个单位钢管的最小运费得到的就是每个单位钢管的最小运费。算法仍然可以采用算法仍然可以采用Floyd-Warshall算法。算法。2.2.3运输量的计算模型及求解运输量的计算模型及求解记第记第i个钢厂的采购费用为个钢厂的采购费用为，最大供应量，最大供应量为为，最小供应量为，最小供应量为500，从第，从第i个钢厂到个钢厂到铺设节点铺设节点j的运输费用为的运输费用为；用表示管道第；用表示管道第j段需要铺设的钢管量。这些已经是已知的段需要铺设的钢管量。这些已经是已知的（或已经求得的）。（或已经求得的）。决策变量：用决策变量：用表示钢厂表示钢厂i是否使用；是否使用；是从是从钢厂钢厂i运到节点运到节点j的钢管量；的钢管量；是从节点是从节点j向左向左铺设的钢管量；铺设的钢管量；是从节点是从节点j向右铺设的钢管向右铺设的钢管量。量。目标函数：目标函数应该包括两部分费用。目标函数：目标函数应该包括两部分费用。从第从第i个钢厂采购钢管并将钢管运到铺设节点个钢厂采购钢管并将钢管运到铺设节点j的运费费用，对所有的运费费用，对所有i，j求和，即求和，即从铺设节点从铺设节点j向左铺设的钢管量向左铺设的钢管量和从节点和从节点j向向右铺设的钢管量右铺设的钢管量导致的运输费：这部分费导致的运输费：这部分费用是以用是以0.1为首项、为首项、0.1为公差的等差级数，为公差的等差级数，所以对所有所以对所有j求和，可得这部分费用为求和，可得这部分费用为约束条件是比较明显的，所以下面直接给约束条件是比较明显的，所以下面直接给出本题第一问求运输量的模型如下：出本题第一问求运输量的模型如下：约束（约束（1）表示每个钢厂的生产总量限制（不低于）表示每个钢厂的生产总量限制（不低于500t，也不超过总能力限制），约束（，也不超过总能力限制），约束（2）表示运输到每个）表示运输到每个辅助节点的钢管数量刚好等于从这个节点向左和向右铺辅助节点的钢管数量刚好等于从这个节点向左和向右铺设的钢管的钢管数量；约束（设的钢管的钢管数量；约束（3）表示每一段管道上铺）表示每一段管道上铺设的钢管数量正好等于前一个节点向右、后一个节点向设的钢管数量正好等于前一个节点向右、后一个节点向左铺设的钢管数量之和；约束（左铺设的钢管数量之和；约束（4）是对端点）是对端点和和的的自然限制；约束（自然限制；约束（5）表示是否使用某个钢厂的）表示是否使用某个钢厂的0-1限制。限制。这是一个二次规划模型。有些读者可能已经注意到，由这是一个二次规划模型。有些读者可能已经注意到，由于题目中说明运输不足整数公里需要按照整数公里计算，于题目中说明运输不足整数公里需要按照整数公里计算，所以上面费用中的第二项只有当所以上面费用中的第二项只有当，为整数时才是精为整数时才是精确成立，否则只能看成是一种近似。不过，由于题目中确成立，否则只能看成是一种近似。不过，由于题目中所给的距离都是整数，所以虽然上面的模型中最优解未所给的距离都是整数，所以虽然上面的模型中最优解未必一定是整数，但这个问题必然存在必一定是整数，但这个问题必然存在，为整数的解为整数的解（自然，此时也是整数），因此我们只需要在模型中再（自然，此时也是整数），因此我们只需要在模型中再加上加上（或（或）为整数的限制就完全没有问题了。这样）为整数的限制就完全没有问题了。这样的性质通常为的性质通常为“占优占优”性质，在优化建模中利用这种性性质，在优化建模中利用这种性质有时是非常方便的。质有时是非常方便的。2.3 2.3 露天矿生产的车辆安排露天矿生产的车辆安排2.3.1 2.3.1 问题描述问题描述20032003高教社杯全国大学生数学建模竞赛题目高教社杯全国大学生数学建模竞赛题目B B题题 露天矿生产的车辆安排露天矿生产的车辆安排钢铁工业是国家工业的基础之一，铁矿是钢铁工业的主要原料基钢铁工业是国家工业的基础之一，铁矿是钢铁工业的主要原料基地。许多现代化铁矿是露天开采的，它的生产主要是由电动铲车地。许多现代化铁矿是露天开采的，它的生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输来完成。提高这些大型设备的利用率是增加露天矿经济效益的首来完成。提高这些大型设备的利用率是增加露天矿经济效益的首要任务。要任务。露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石。一般来说，平均铲位已预先根据铁含量将石料分成矿石和岩石。一般来说，平均铁含量不低于铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多能安置一台电铲，电铲的平均装车时间为铲位至多能安置一台电铲，电铲的平均装车时间为5分钟。分钟。卸货地点（以下简称卸点）有卸矿石的矿石漏、卸货地点（以下简称卸点）有卸矿石的矿石漏、2个铁路倒装场个铁路倒装场（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都有（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都有各自的产量要求。从保护国家资源的角度及矿山的经济效益考虑，各自的产量要求。从保护国家资源的角度及矿山的经济效益考虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都为应该尽量把矿石按矿石卸点需要的铁含量（假设要求都为29.5%1%，称为品位限制）搭配起来送到卸点，搭配的量在一个班次，称为品位限制）搭配起来送到卸点，搭配的量在一个班次（8小时）内满足品位限制即可。从长远看，卸点可以移动，但小时）内满足品位限制即可。从长远看，卸点可以移动，但一个班次内不变。卡车的平均卸车时间为一个班次内不变。卡车的平均卸车时间为3分钟。分钟。所用卡车载重量为所用卡车载重量为154吨，平均时速吨，平均时速28。卡车的耗油量很大，。卡车的耗油量很大，每个班次每台车消耗近每个班次每台车消耗近1吨柴油。发动机点火时需要消耗相当吨柴油。发动机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始工作时点火一次。卡车多的电瓶能量，故一个班次中只在开始工作时点火一次。卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆以发生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车每次都是满载运输。上卡车服务。卡车每次都是满载运输。每个铲位到每个卸点的道路都是专用的宽每个铲位到每个卸点的道路都是专用的宽60的双向车道，不会的双向车道，不会出现堵车现象，每段道路的里程都是已知的。出现堵车现象，每段道路的里程都是已知的。一个班次的生产计划应该包含以下内容：出动几台电铲，分别一个班次的生产计划应该包含以下内容：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次（因为随机因素影响，装卸时间与运输时间都不精确，所以次（因为随机因素影响，装卸时间与运输时间都不精确，所以排时计划无效，只求出各条路线上的卡车数及安排即可）。一排时计划无效，只求出各条路线上的卡车数及安排即可）。一个合格的计划要在卡车不等待条件下满足产量和质量（品位）个合格的计划要在卡车不等待条件下满足产量和质量（品位）要求，而一个好的计划还应该考虑下面两条原则之一：要求，而一个好的计划还应该考虑下面两条原则之一：1.总运量（吨公里）最小，同时出动最少的卡车，从而运输成总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小；本最小；2.利用现有车辆运输，获得最大的产量（岩石产量优先；在产利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。量相同的情况下，取总运量最小的解）。请你就两条原则分别建立数学模型，并给出请你就两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。针对下面的一个班次生产计划的快速算法。针对下面的实例，给出具体的生产计划、相应的总运量实例，给出具体的生产计划、相应的总运量及岩石和矿石产量。及岩石和矿石产量。某露天矿有铲位某露天矿有铲位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.265.194.214.002.952.742.461.900.641.27倒装倒装场场1.900.991.901.131.272.251.482.043.093.51岩场岩场5.895.615.614.563.513.652.462.461.060.57岩石岩石漏漏0.641.761.271.832.742.604.213.725.056.10倒装倒装场场4.423.863.723.162.252.810.781.621.270.50各铲位矿石、岩石数量各铲位矿石、岩石数量(万吨万吨)和矿石的平均铁含和矿石的平均铁含量如下表：量如下表：铲位铲位1铲位铲位2铲位铲位3铲位铲位4铲位铲位5铲位铲位6铲位铲位7铲位铲位8铲位铲位9铲位铲位10矿石矿石量量095105100105110125105130135125岩石岩石量量125110135105115135105115135125铁含铁含量量30%28%29%32%31%33%32%31%33%31%示意图2.3.2运输运输计划模型及求解计划模型及求解问题分析问题分析与与2.2节的问题类似，本题也可以看成是经典运输问题节的问题类似，本题也可以看成是经典运输问题的一种变形和扩展，它与典型的运输问题明显有以下不的一种变形和扩展，它与典型的运输问题明显有以下不同：同：这是运输矿石与岩石两种物资的问题；这是运输矿石与岩石两种物资的问题；属于产量大于销量的不平衡运输问题；属于产量大于销量的不平衡运输问题；为了完成品位约束，矿石要搭配运输；为了完成品位约束，矿石要搭配运输；产地、销地均有单位时间的流量限制；产地、销地均有单位时间的流量限制；运输车辆只有一种，每次都是满载运输，运输车辆只有一种，每次都是满载运输，154t/车次；车次；铲位数多于铲车数意味着最优的选择不多于铲位数多于铲车数意味着最优的选择不多于7个产地作个产地作为最后结果的产地为最后结果的产地最后求出各条路线上的派出车辆数及安排最后求出各条路线上的派出车辆数及安排每个运输问题对应着一个线形规划问题，以上不同每个运输问题对应着一个线形规划问题，以上不同点对它的影响不同，（点对它的影响不同，（1）（）（2）（）（3）（）（4）条可）条可通过变量的设计、调整约束条件实现；（通过变量的设计、调整约束条件实现；（5）条是）条是整数要求将使其变为整数线形规划；（整数要求将使其变为整数线形规划；（6）条不容）条不容易用线形模型实现，一易用线形模型实现，一种简单的办法是从种简单的办法是从=120个个整数规划中取最优的即得到最佳物流；为完成整数规划中取最优的即得到最佳物流；为完成（7）条，由最佳物流算出各条路线上的最少派车）条，由最佳物流算出各条路线上的最少派车数（整数）再给出具体安排即完成全部计算。然而数（整数）再给出具体安排即完成全部计算。然而这是个实际问题，为了及时指挥生产，题中要求算这是个实际问题，为了及时指挥生产，题中要求算法是快速算法，而整数规划的本质是法是快速算法，而整数规划的本质是NPC问题，仅问题，仅就就20min内计算含内计算含50个变量的整数规划来说就不一个变量的整数规划来说就不一定办得到。从另一个角度看，这是一个二层规划问定办得到。从另一个角度看，这是一个二层规划问题，第二层规划是组合优化，如果求最优解计算量题，第二层规划是组合优化，如果求最优解计算量较大，现成的各种算法都无能为力。于是问题变为较大，现成的各种算法都无能为力。于是问题变为找一个寻求近优解的近似解法，例如可用启发式方找一个寻求近优解的近似解法，例如可用启发式方法求解。法求解。调用调用120次整数规划可用三种方法避免：次整数规划可用三种方法避免：1.先不考虑电铲先不考虑电铲数量约束运行整数规划，再对解中运量最少的几个铲位进数量约束运行整数规划，再对解中运量最少的几个铲位进行筛选；行筛选；2.在整数线形规划的铲车约束中调用在整数线形规划的铲车约束中调用sign函数函数来实现；来实现；3.增加增加10个个1-0个变量了来标志各个铲位是否有个变量了来标志各个铲位是否有产量。产量。从每个运输问题都有目标函数的角度看，这又是一个多目从每个运输问题都有目标函数的角度看，这又是一个多目标规划问题，第一问的主要目标有：标规划问题，第一问的主要目标有：1重载路程最小；重载路程最小；2总路程最小；总路程最小；3出动卡车数最少。仔细分析可得：出动卡车数最少。仔细分析可得：1和和2在在第一层，第一层，3在第二层；在第二层；1与与2基本等价，于是只用基本等价，于是只用1于第一层，于第一层，对其结果在第二层中派最少的卡车，实现全局目标生产成对其结果在第二层中派最少的卡车，实现全局目标生产成本最小。第二问的主要目标有：本最小。第二问的主要目标有：4岩石产量最大；岩石产量最大；5矿石矿石产量最大；产量最大；6运量最小。三者之间的关系根据应该理解为运量最小。三者之间的关系根据应该理解为字典序。字典序。合理的假设主要有：合理的假设主要有：卡车在一个班次中不应发生等待或熄火再启动的情况卡车在一个班次中不应发生等待或熄火再启动的情况在铲位或卸点处由两条路线以上造成的冲突问题面前，我在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认为不冲突。不进行们认为只要平均时间能完成任务，就认为不冲突。不进行具体排时方面的讨论具体排时方面的讨论空载与重载的速度都是空载与重载的速度都是28km/h，耗油相差却很大，耗油相差却很大卡车可提前退出系统，等等卡车可提前退出系统，等等模型建立模型建立我们将只考虑本题第一问（求运输量）的模型。首先定义我们将只考虑本题第一问（求运输量）的模型。首先定义如下数学符号：如下数学符号：Xij为为i号铲位到号铲位到j号卸点路线上运行一个周号卸点路线上运行一个周期平均所需要时间（期平均所需要时间（min）；）；Aij为从为从i号铲位到号铲位到j号卸点最号卸点最多能同时运行的卡车数（辆）；多能同时运行的卡车数（辆）；Bij为从为从i号铲位到号铲位到j号卸点号卸点路线上一辆车最多可以运行的次数（次）；路线上一辆车最多可以运行的次数（次）；Pi为为i号铲位的号铲位的矿石铁含量（矿石铁含量（%）；）；P=（3028293231332323331）；）；qj为为i号卸点任务需要（号卸点任务需要（t）；）；q=（1.2，1.3，1.3，1.9，1.3）*10000。CKi为为i号铲位的铁矿石储量（万号铲位的铁矿石储量（万t）；）；CYi为为i号铲位的岩石储量（万号铲位的岩石储量（万t）；）；fi为描述第为描述第i号铲位是否号铲位是否使用的使用的0-1开关变量，取开关变量，取1为使用，取为使用，取0为关闭为关闭。目标函数与约束条件的分析；目标函数与约束条件的分析；目标函数取为重载运输时的目标函数取为重载运输时的运量（运量（.t.km）最）最小（因小（因Xij代表整数车次数，乘代表整数车次数，乘154后等于运后等于运量；再乘以运输距离等于吨公里）。量；再乘以运输距离等于吨公里）。道路能力约束；由于一个电铲（卸点）不能道路能力约束；由于一个电铲（卸点）不能同时为两辆卡车服务，所以一条路线上最多同时为两辆卡车服务，所以一条路线上最多能同时运行的卡车数是有限的，卡车在能同时运行的卡车数是有限的，卡车在i号铲号铲位到位到j号卸点路线上运行一个周期平均所需的号卸点路线上运行一个周期平均所需的时间为时间为T=（i到到j距离距离*2/平均速度）平均速度）+3+5（min）由于装车时间由于装车时间5min大于卸车时间大于卸车时间3min，所以可分析出这条路线，所以可分析出这条路线上在卡车不等待条件下最多能同时运行的卡车数为：上在卡车不等待条件下最多能同时运行的卡车数为：Aij=Tij/5。同样可分析每辆卡车一个班次中在这条路线上最多可以运行的次同样可分析每辆卡车一个班次中在这条路线上最多可以运行的次数为数为Bij=8*60-（Aij-1）*5/Tij，其中（，其中（Aij-1）*5是开始装车时是开始装车时最后一辆车的延时时间。则一个班次中这条固定路线上最多可能最后一辆车的延时时间。则一个班次中这条固定路线上最多可能运行的总车次大约为：运行的总车次大约为：Lij=Aij*Bij。电铲能力约束：还是因为一台电铲不能同时为两辆卡车服务，所电铲能力约束：还是因为一台电铲不能同时为两辆卡车服务，所以一台电铲早一个班次中的最大可能产量为：以一台电铲早一个班次中的最大可能产量为：8*60/5（车）（车）卸点能力约束：卸点的最大吞吐量为每小时卸点能力约束：卸点的最大吞吐量为每小时60/3=20车次。于是车次。于是一个卸点在一个班次中的最大可能产量为：一个卸点在一个班次中的最大可能产量为：8*20车车铲位储量约束：铲位的矿石和岩石产量都不能超过相应储藏量铲位储量约束：铲位的矿石和岩石产量都不能超过相应储藏量产量任务约束：各卸点的产量大于等于该卸点的任务要求产量任务约束：各卸点的产量大于等于该卸点的任务要求铁含量约束：各矿石卸点的平均品位要求都在指定的范围内铁含量约束：各矿石卸点的平均品位要求都在指定的范围内电铲数量约束：电铲数量约束无法用普通不等式表达，但算法运电铲数量约束：电铲数量约束无法用普通不等式表达，但算法运行时间增加了，也可以用其他方法解决该问题行时间增加了，也可以用其他方法解决该问题卡车数量约束：卡车总数不超过卡车数量约束：卡车总数不超过20辆辆整数约束：当把问题作为整数规划模型时，车流量整数约束：当把问题作为整数规划模型时，车流量Xij为非负整数为非负整数这样，我们可以得到的各种模型之一为：这样，我们可以得到的各种模型之一为：2.4空洞探测空洞探测2.4.1问题描述问题描述山体、隧洞、坝体等的某些内部结构可用弹性波测量来确定。山体、隧洞、坝体等的某些内部结构可用弹性波测量来确定。一个简化问题可描述为，一块均匀介质构成的矩形平板内有一一个简化问题可描述为，一块均匀介质构成的矩形平板内有一些充满空气的空洞，在平板的两个邻边分别等距地设置若干波些充满空气的空洞，在平板的两个邻边分别等距地设置若干波源，在它们的对边对等地安放同样多的接收器，记录弹性波由源，在它们的对边对等地安放同样多的接收器，记录弹性波由每个波源到达对边上每个接收器的时间，根据弹性波在介质中每个波源到达对边上每个接收器的时间，根据弹性波在介质中和在空气中不同的传播速度，来确定板内空洞的位置。现考察和在空气中不同的传播速度，来确定板内空洞的位置。现考察如下的具体问题：如下的具体问题：一块一块240（米）（米）240（米）的平板（如图），在（米）的平板（如图），在AB边等距地设边等距地设置置7个波源个波源Pi(i=1,7)，CD边对等地安放边对等地安放7个接收器个接收器Qj(j=1,7)，记录由，记录由Pi发出的弹性波到达发出的弹性波到达Qj的时间的时间tij(秒秒);在在AD边等距地设置边等距地设置7个波源个波源Ri(i=1,7)，BC边对等地安放边对等地安放7个接收个接收器器Sj(j=1,7)，记录由，记录由Ri发出的弹性波到达发出的弹性波到达Sj的时间的时间ij(秒秒)。已知弹性波在介质和空气中的传播速度分别为已知弹性波在介质和空气中的传播速度分别为2880（米（米/秒）和秒）和320（米（米/秒），且弹性波沿板边缘的传播速度与在介质中的传秒），且弹性波沿板边缘的传播速度与在介质中的传播速度相同。播速度相同。1）确定该平板内空洞的位置。）确定该平板内空洞的位置。QjABCDPiRiSj2）只根据由）只根据由Pi发出的弹性波到达发出的弹性波到达Qj的时间的时间tij(i,j=1,7)，能确，能确定空洞的位置吗；讨论在同样能够确定空洞位置的前提下，减定空洞的位置吗；讨论在同样能够确定空洞位置的前提下，减少波源和接受器的方法。少波源和接受器的方法。图QjABCDPiRiSjt tijijQ Q1 1Q Q2 2Q Q3 3Q Q4 4Q Q5 5Q Q6 6Q Q7 7P P1 10.06110.06110.08950.08950.19960.19960.20320.20320.41810.41810.49230.49230.56460.5646P P2 20.09890.09890.05920.05920.44130.44130.43180.43180.47700.47700.52420.52420.38050.3805P P3 30.30520.30520.41310.41310.05980.05980.41530.41530.41560.41560.35630.35630.19190.1919P P4 40.32210.32210.44530.44530.40400.40400.07380.07380.17890.17890.07400.07400.21220.2122P P5 50.34900.34900.45290.45290.22630.22630.19170.19170.08390.08390.17680.17680.18100.1810P P6 60.38070.38070.31770.31770.23640.23640.30640.30640.22170.22170.09390.09390.10310.1031P P7 70.43110.43110.33970.33970.35660.35660.19540.19540.07600.07600.06880.06880.10420.1042ijijS S1 1S S2 2S S3 3S S4 4S S5 5S S6 6S S7 7R R1 10.06450.06450.06020.06020.08130.08130.35160.35160.38670.38670.43140.43140.57210.5721R R2 20.07530.07530.07000.07000.28520.28520.43410.43410.34910.34910.48000.48000.49800.4980R R3 30.34560.34560.32050.32050.09740.09740.40930.40930.42400.42400.45400.45400.31120.3112R R4 40.36550.36550.32890.32890.42470.42470.10070.10070.32490.32490.21340.21340.10170.1017R R5 50.31650.31650.24090.24090.32140.32140.32560.32560.09040.09040.18740.18740.21300.2130R R6 60.27490.27490.38910.38910.58950.58950.30160.30160.20580.20580.08410.08410.07060.0706R R7 70.44340.44340.49190.49190.39040.39040.07860.07860