2015年国赛A题
题目 太阳影子定位
如何确定视频的拍摄地点和拍摄日期是视频数据分析的重要方面,太阳影子定位技术就是通过分析视频中物体的太阳影子变化,确定视频拍摄的地点和日期的一种方法。
建立影子长度变化的数学模型,分析影子长度关于各个参数的变化规律,并应用你们建立的模型画出2015年10月22日北京时间9:00-15:00之间天安门广场(北纬39度54分26秒,东经116度23分29秒)3米高的直杆的太阳影子长度的变化曲线。
根据某固定直杆在水平地面上的太阳影子顶点坐标数据,建立数学模型确定直杆所处的地点。将你们的模型应用于附件1的影子顶点坐标数据,给出若干个可能的地点。
根据某固定直杆在水平地面上的太阳影子顶点坐标数据,建立数学模型确定直杆所处的地点和日期。将你们的模型分别应用于附件2和附件3的影子顶点坐标数据,给出若干个可能的地点与日期。
附件4为一根直杆在太阳下的影子变化的视频,并且已通过某种方式估计出直杆的高度为2米。请建立确定视频拍摄地点的数学模型,并应用你们的模型给出若干个可能的拍摄地点。
如果拍摄日期未知,你能否根据视频确定出拍摄地点与日期?
问题分析
问题一
针对问题一首先为了建立影子长度变化的数学模型,应先确定影响影子长度变化的因素, 拟选取直杆所在经度、纬度、日期、时刻及杆长为参数建立数学模型。 由于题设中未直接给出关于影长与五个参数的数据,所以拟通过中间量描述影长与上述五个参数之间的关系。查阅相关资料得到可以太阳高度角、太阳赤玮角、太阳时角及太阳方位角四个中间参量作为转换分析中间变量,再根据四个中间变量得到影长与 5 个参数的函数关系式,即影长长度变化的数学模型。最后将天安门广场的 5 个参数带入影长变化模型,可得到杆影的变化曲线,分析影子长度关于各个参数的变化规律。再次此基础上, 可运用控制变量法分析每个参数与影长的变化规律,并进行单因素敏感性分析。 由此,可建立影长变化模型,利用各参数求解变化规律。
问题二
针对问题二以直杆的太阳影子顶点为坐标数据建立数学模型,并应用于附件1 的影子顶点坐标数据求解直杆位置。可视为已知影长坐标、日期和时刻,求影长所在的地点的问题。首先应根据影长坐标计算太阳影长,本文拟将附件 1 中的影长、时刻及日期代入问题一中的影长变化函数中,可得到含有 21 个方程式的超定方程组。其次,该问题是一个单目标最优化问题,本文可建立影长差值绝对值最小为单目标的最优化模型对附件 1 进行求解,其中约束条件可考虑经纬度的范围。最后通过穷举搜索,得到直杆所在的地点。由此,可建立单目标最优化模型,利用穷举搜索法求解。
问题三
针对问题三可视为已知影长坐标及测量影长的时刻,求解直杆经纬度及测量日期的问题。首先应将附件 2、 3 中的 21 组影长及时刻代入问题一中的影长变化函数中,得到超定方程组。其次该问题是一个双目标最优化问题,本文可建立以影长差值最小、影长的曲线斜率差最小为目标的双目标最优化模型对附件 2、 3进行求解,得出地点与日期,其中约束条件可考虑经纬度范围。由此,可建立双目标最优化模型,利用=穷举搜索法求解,并对模型的正确性进行检验。
问题四
针对问题四首先需对视频中影子长度进行提取,通过对图像预处理,将彩色图像灰度化,再对小连通域处理。 拟采用一种 Canny 边缘检测算法提取预处理后的图像中的轮廓。 以直杆底座的左下方的顶点为原点建立平面直角坐标系,通过透视转换,将平面直角坐标转换到影长所在的平面内, 计算两坐标转换比例,其次提取影子长度, 求解超定方程组。最后以差值绝对值最小为目标函数,经纬范围为约束条件,建立单目标优化模型,通过穷举搜索,得到直杆所在的地点。以影长曲线斜率之差最小,影长差值最小建立双目标优化模型, 其中约束条件可考虑经纬度范围。 通过人工鱼群算法,得到直杆所在经纬度和影长测量的日期。 最后针对直杆的高度做敏感性分析, 观察杆高对直杆所处位置的影响。
所运用到的模型和算法
拟牛顿迭代法
牛顿法的基本思想是在迭代点xk初对目标函数f(x)进行二次函数近似,然后把二次模型的极小点作为新的迭代点,并不断重复这一过程,直至求得满足精度的近似极小点。
而拟牛顿法可以在保证收敛速度的同时,不用满足Hesse矩阵处处正定的条件并且可以避免每次都进行Hesse计算,通过构造可以近似Hesse矩阵(或Hesse矩阵的逆)的正定对称阵。
代码
function [xk,fk,k]=cauthy_newton_method1(x0,ess)
%目标函数f,有确定最优解x*=[0 0],f(x*)=400.0
syms x1 x2 t;
f=100*(2*x1^2+2)^2+x2^2;
%构造目标函数f的梯度函数
fx=diff(f,x1);
fy=diff(f,x2);
gf=[fx fy];
%初始点的梯度和函数值,,赋值
xk=x0;
fk=subs(f,[x1 x2],x0);
gk=subs(gf,[x1 x2],x0);
Hk=eye(2);
k=0;
%进入迭代循环
while((norm(gk)>ess)&&(k<15))%迭代终止条件
%确定搜索方向
dk=-Hk*gk' ;
%下一点x(k+1)
xk=xk+t*dk' ;
f_t=subs(f,[x1 x2],xk); %构造一元搜索的一元函数φ(t)
df_t=diff(f_t,t);
res=solve(df_t) ;%由一维搜索找到最优步长
tk=res(1) ;
if (tk~=0 )
tk=double(tk);
else
break;
end
%计算下一点的函数值和梯度
xk = subs(xk,t,tk) ;
fk = subs(f,[x1 x2],xk);
gk0=gk;
gk=subs(gf,[x1 x2],xk);
%DPF校正公式,找到修正矩阵
yk=gk-gk0;
sk=tk*dk';
Hk=Hk-(Hk*yk'*yk*Hk)/(yk*Hk*yk')+sk'*sk/(yk*sk');
k=k+1
end
然后在命令行输入:
x0:是初始点
k:迭代次数
f(xk):目标函数值
clear all;
x0=[10.8 11.8];
ess=1e-5;
[xk,fk,k]=cauthy_newton_method1(x0,ess);
xk=vpa(xk,5)
fk=vpa(fk,5)
k
人工鱼群算法
在一片水域中,鱼往往能自行或尾随其他鱼找到营养物质多的地方,因而鱼生存数目最多的地方一般就是本水域中营养物质最多的地方,人工鱼群算法就是根据这一特点,通过构造人工鱼来模仿鱼群的觅食、聚群及追尾行为,从而实现寻优。
中文名 人工鱼群算法 典型行为觅食行为
特点 具有较快的收敛速度
停止条件 均方差小于允许的误差。
算法描述
在一片水域中,鱼往往能自行或尾随其他鱼找到营养物质多的地方,因而鱼生存数目最多的地方一般就是本水域中营养物质最多的地方,人工鱼群算法就是根据这一特点,通过构造人工鱼来模仿鱼群的觅食、聚群及追尾行为,从而实现寻优,以下是鱼的几种典型行为:
1)觅食行为:一般情况下鱼在水中随机地自由游动,当发现食物时,则会向食物逐渐增多的方向快速游去。
2)聚群行为:鱼在游动过程中为了保证自身的生存和躲避危害会自然地聚集成群,鱼聚群时所遵守的规则有三条:
分隔规则:尽量避免与临近伙伴过于拥挤;
对准规则: 尽量与临近伙伴的平均方向一致;
内聚规则: 尽量朝临近伙伴的中心移动。
3)追尾行为:当鱼群中的一条或几条鱼发现食物时,其临近的伙伴会尾随其快速到达食物点。
4)随机行为:单独的鱼在水中通常都是随机游动的,这是为了更大范围地寻找食物点或身边的伙伴。
特点
1)具有较快的收敛速度,可以用于解决有实时性要求的问题;
2)对于一些精度要求不高的场合,可以用它快速的得到一个可行解;
3)不需要问题的严格机理模型,甚至不需要问题的精确描述,这使得它的应用范围得以延伸。
停止条件
判断连续多次所得的均方差小于允许的误差;
判断某个区域的人工鱼群的数目达到某个比率;
连续多次所获取的值均不能超过已找到的极值。
4)迭代次数达到预设次数
流程图
L-M 最优化算法
本题的最优化模型是一个利用最小二乘法原理对多个参数进行拟合的问题。经查阅资料我们发现 L-M(Levenberg-Marquardt)算法在解决这类问题时有较好的应用。
Levenberg-Marquardt 算法是介于牛顿法与梯度下降法之间的一种非线性优化方法,这个算法对于过参数化问题不敏感,能有效处理冗余参数问题,而且寻优速度较快。
例题
test.m
syms t;
f = [t^2+t-1;2*t^2-3];
[x_optimization,f_optimization] = Levenberg_Marquardt_Method(f,5,0.4,2,1.5,(t));
x_optimization = double(x_optimization);
f_optimization = double(f_optimization);
x_optimization
f_optimization
t = -2:0.01:2;
St = (t.^2 + t - 1).^2 + (2.*t.^2 - 3).^2;
figure(1)
plot(t,St);
Levenberg_Marquardt_Method.m
function [x_optimization,f_optimization] = Levenberg_Marquardt_Method(f,x0,beta,mu,v,var_x,epsilon)
format long;
% f:目标函数
% x0:初始点
% beta:参数
% mu:阻尼参数
% v:放大系数
% var_x:自变量向量
% epsilon:精度
% x_optimization:目标函数取最小值时的自变量值
% f_optimization:目标函数的最小值
if nargin == 6
epsilon = 1.0e-6;
end
S = transpose(f)*f;
k = length(f);
n = length(x0);
x0 = transpose(x0);
var_x = transpose(var_x);
grad_f = jacobian(f,var_x);
xk = x0;
dx = 1;
while norm(dx) > epsilon
fxk = zeros(k,1);
for i=1:k
fxk(i,1) = subs(f(i),var_x,xk); % 【2】
end
Sxk = subs(S,var_x,xk);
grad_fxk = subs(grad_f,var_x,xk); % 【3】
grad_Sxk = transpose(grad_fxk)*fxk; % 【4】
Q = transpose(grad_fxk)*grad_fxk; % 【5】
while 1
I = eye(size(Q));
dx = double(-(Q + mu*I)grad_Sxk);
xk_next = xk + dx; % 【6】
for i=1:k
fxk_next(i,1) = subs(f(i),var_x,xk_next);
end
Sxk_next = subs(S,var_x,xk_next);
if norm(dx) <= epsilon
break;
end
if Sxk_next >= Sxk + beta*transpose(grad_Sxk)*dx % 【7】
mu = v*mu;
continue;
else
mu = mu/v;
break;
end
end
xk = xk_next; % 【8】
end
x_optimization = xk;
f_optimization = subs(S,var_x,x_optimization);
format short;
2015年国赛B题
出租车是市民出行的重要交通工具之一,“打车难”是人们关注的一个社会热点问题。随着“互联网+”时代的到来,有多家公司依托移动互联网建立了打车软件服务平台,实现了乘客与出租车司机之间的信息互通,同时推出了多种出租车的补贴方案。
请你们搜集相关数据,建立数学模型研究如下问题:
(1) 试建立合理的指标,并分析不同时空出租车资源的“供求匹配”程度。
(2) 分析各公司的出租车补贴方案是否对“缓解打车难”有帮助?
(3) 如果要创建一个新的打车软件服务平台,你们将设计什么样的补贴方案,并论证其合理性。
问题分析
问题一
该问题要求建立合理的指标,并分析不同时空出租车资源的供求匹配”程度。本文基于“苍穹||滴滴快的智能出行平台”[1]中使用滴滴打车的出租车以及用户的行为情况,建立了供求匹配情况下的出租车模型,并用以评价上海市的出租车资源”供求匹配”程度。
衡量出租车运营情况的最直观数据就是出租车的位置分布,衡量出租车需求程度的最直观数据是打车人数即请求单数的分布,而直接和打车软件用户体验相关联的数据则是乘客打车时间,这里我们用接单时间来衡量。由于空驶率K可以对应出租车供应量,而乘客等待时间可以对应出租车需求量,故两者的函数关系可以作为衡量供应量的指标。通过对以上三个基本数据进行分析,我们得出可以用空驶率K和乘客等待时间T作为衡量供求情况的具体指标。通过考察城区和郊区全天24小时的K变化规律,我们得出空间(城郊)和时间(全天)两个维度的供求关系分布情况。
这部分我们分为三个部分进行探讨:
首先,我们想确定在某个时间段内,研究上海市出租车粗略的空间分配情况。我们对某工作日和节假日进行抽样,使用插值的方法在Matlab中分别绘制出了这一天低峰10:00、高峰17:00时段,全上海市的采样点地理位置(经度x, 纬度y)与出租车分布、乘客需求量分布、以及等待时间的三维图像,为进一步讨论打下了基础。
接下来,我们想讨论时间对于出租车分配调度的影响。由于数据量过大,且不同数据指标取样点的空间位置不是严格对应的,我们利用集簇的思想,选择了20个具有代表性的商圈以及城郊,并根据具体位置选择合适的半径,囊括其周边的采样数据点,并算出平均等待时间,作为某一具体时刻,具体地点的供求分配程度的量度。我们选择出具有代表性的商圈与城郊,考察他们在工作日、非工作日的情况,并作出了其周边一天内平均空载率Kave与真实时间t的二维图像。
最后,我们引入了供求满意度函数f,建立了出租车供需关系平衡的数学模型,并综合第二部分中的数据,利用曲线拟合工具得到了上海市区的供需平衡模型,并将其利用于评价上海市出租车资源“供求匹配”程度 。
问题二
该问题要求分析各公司的出租车补贴方案是否对缓解打车难”有帮助。为了更客观的研究整个出租车模型,我们想要建立一种合适的模拟过程方案,可以体现出在用打车软件的情况下,有无补贴以及补贴力度不同时出租车盈利、行为模式的不同。
此时为了在大量的数据中选取合适的研究对象,我们查阅资料后发现,可以应用智能城市过往研究方法网格化我们的地图,并进行近似处理。”打车难”具体可以表现为出租车总空驶路程:即空驶路程越长,说明司机浪费在搜寻乘客的路途上越长;反之,则说明乘客打车难受到了缓解。
在第一问的基础上,我们注意到此时的重点是考察补贴方案不同时,出租车盈利、行为模式有何不同。我们认识到补贴是双向的,既有用户的红包奖励,还有对司机的奖励或者燃油补助。所以,我们在思考后决定,将这两个方面用参数的形式体现在我们建立的模型中。并且,我们还提出了多种可能合适的数学模型进行研究,用以分析补贴对于”缓解打车难”的帮助情况。
最新评论