6.4 数学建模案例(二):曼哈顿距离 【学习目标】 了解曼哈顿距离,掌握建立数学模型的方法以及模型求解的方法.(数学建模) 【合作探究】 一、问题背景 在解析几何里最常用的一种计算方法,即已知平面两点A(x1,y1),B(x2,y2),|AB|=,但是计算起来比较复杂,要平方,加和,再开方,而人们在空间几何中度量距离很多场合其实是可以做一些简化的,曼哈顿距离就是由19世纪著名的德国犹太数学家赫尔曼·闵可夫斯基发明的距离简化计算所得到. 在平面内两点A(x1,y1),B(x2,y2)之间的曼哈顿距离为d(A,B)=|x1-x2|+|y1-y2|. 曼哈顿距离也叫出租车距离,出租车司机计算从一个位置到另一个位置的距离,通常直接用街区的两个坐标分别相减,再相加,这个结果就是他即将开车通过的街区数量,而完全没有必要用两点间的距离公式来求解. 曼哈顿距离中的距离计算公式比欧氏距离的计算公式看起来简洁很多,只需要把两个点坐标的横坐标相减取绝对值,纵坐标相减取绝对值,再加和. 从曼哈顿距离的概念来说,只能上、下、左、右四个方向进行移动,而且两点之间的曼哈顿距离是两点之间的最短距离(在只能向上、下、左、右四个方向进行移动的前提下).为什么呢 假设从一点到达另一点(只能向上、下、左、右四个方向进行移动,下同),要使路程最短,就只能每一步都有用(使之与另一点的南北距离或东西距离缩短). 不难验证,对于平面上任意三点A,B,C,曼哈顿距离满足d(A,C)≤d(A,B)+d(B,C).一般情况下,设平面上点A(x,y),以及点Bi(xi,yi)(i=1,2,…,n),则点A到点Bi(i=1,2,…,n)的曼哈顿距离Z定义为点A到n个点Bi(i=1,2,…,n)的曼哈顿距离之和,即Z=d(A,Bi). 二、问题解析 1.模型的建立与求解 先考虑一个简单的数学建模. 问题:某地街道呈现东-西、南-北向的网格状,相邻街距都为1,两街道相交的点称为格点.若以互相垂直的两条街道为坐标轴建立平面直角坐标系,现有下述格点(-2,2),(3,1),(3,4),(-2,3),(4,5)为报刊零售点.为使5个零售点沿街道到发行站之间路程的和最短,试确定发行站的位置使其到5个零售点的曼哈顿距离最短. (1)建立数学模型 设发行站的位置为P(x,y),y≥0,零售点到发行站的距离为Z, Z=d(x,y)=2|x+2|+|y-2|+2|x-3|+|y-1|+|y-4|+|y-3|+|x-4|+|y-5|=(2|x+2|+2|x-3|+|x-4|)+(|y-2|+|y-1|+|y-4|+|y-3|+|y-5|). (2)模型求解 因为水平方向与垂直方向的距离分别为 X=2|x+2|+2|x-3|+|x-4|,Y=|y-2|+|y-1|+|y-4|+|y-3|+|y-5|,它们互不影响,则Z=X+Y, 所以Zmin=Xmin+Ymin, 这五个点的横坐标与纵坐标的平均值分别为 ==, ==3. 记A,画图可知发行站的位置应该在点A附近, 代入附近的点的坐标进行比较可知,在(3,3)处Z取得最小值. 2.模型的进一步讨论 在实际生活中,还有许多的问题可以归结为基于曼哈顿距离的数学模型来求解.以设置机器零件检验台的位置为例来说明. 如图,工作效率相同的n台机器位于一条直线上,每台机器生产的零件均需送到同一个检验台上检验,检验合格后才能进入下一道工序.已知零件在这条直线上的传送速度均相同,问检验台的位置设在哪里可以使得零件传送时的距离最小 上述问题的数学模型为y=|x-A1|+|x-A2|+…+|x-An|,其中Ak(k=1,2,…,n)是第k个零件的位置,x是待求的检验台位置,y是零件传送的总距离. 将n个常数A1,A2,…,An从小到大排列,则有 (1)当n=2m+1(m∈N+),x=Am+1时,y取得最小值,且最小值为(Am+k+1-Ak); (2)当n=2m(m∈N+),x∈[Am,Am+1]时,y取得最小值,且最小值为(Am+k-Ak). 除了上面描述的曼哈顿距离外,许多实际问题还可以转化为以其他距离最值为约束条件的数学模型来解决. 问题研究一:确定垃圾集中回收站的位置 垃圾分类可以提高垃圾的资源价值和经济价值,具有社会、经济、生态等几方面的效益,某街道呈现东-西、南-北向的网格状,相邻街距都为1,两街道相交的点称为格点.若以互相垂直的两 ... ...
~~ 您好，已阅读到文档的结尾了 ~~
