试卷合理均衡分配问题最佳乘车路线问题

1第一部分训练任务简介任务一：考试公平性是评价考试质量的重要方面，也是一个受到广泛关注的问题。现代教育虽然趋向现代化，许多教学可以通过计算机实现，但也有许多的问题是计算机无法解决的，由绝大部分的考试是离不开评委亲自的审查，因为许多的学术问题上，计算机是不会知道的，所以工作量只可以是人为的评改。体现最主要的，就是试卷的合理均匀的分配。在大学生数学建模竞赛的评卷工作中，M个评委（M个评委来自不同的学校）要完成N份试卷的打分，竞赛试卷来自K个学校，第i个学校有竞赛试卷1份，为节省人力，每份试卷只要由其中p(pMKN)各评委进行打分就行了。1．根据回避原则，要求评委不能阅自己学校的试卷。要求给出试卷合理的均匀分配方案的数学模型，使各评委的阅卷工作量均衡，试卷分配均衡分散。2．给出试卷合理的均衡分配方案的计算机程序，所需参数为p,M,k,N,输出参数为各评委分别阅卷的号码。任务二：某城市现有公共汽车线路N条，横贯整个市区。由于城市比较大，从某地到另一个地方，乘坐公共汽车往往要在中间某地换车。请你设计一个算法，可算出从某地到另外一个地方（无论换车与否）的最佳乘车路线。请自拟一个例子（实际某城市交通路线更好）模拟仿真。任务三：学习数学软件（MathType5.2、MATLAB、Maple、Mathematica4.0、LINGO8.0）安装调试；基本命令使用（变量赋值、定义函数、过程控制、绘图命令、拟合、线性规划、非线性规划）；高等数学实验（绘图，极限，求导，积分，解微分方程）；线性代数实验（矩阵基本运算，线性方程组求解，解超定方程组，优化命令）。并在提交的综合训练文档附录中的给出下列6个程序的译文(数学模型)及解答：（1）c=[6,6,16,16,10,10,15,15];A=[0.5/10001.5/10000.5/10001.5/1000;01.5/10000.5/10000.5/10000.5/100;00000011;10101010;01010101];b=[0;0;50;100;200;Aeq=[1,1,1,1,1,1,1,1];beq=[350];lb=zeros(8,1);[x,fval]=linprog(c,A,b,Aeq,beq,lb)%目标为最小的线性规划（2）c=[400,1000,300,200];%目标函数系数（产出系数）A=[2,3,1,0;3,4,0,0;0,0,1,0];%约束条件系数b=[16;24;5];Aeq=[0,2,1,1];beq=[0];xL=[0,0,0,0];%x取值范围的最小值xU=[];%x取值范围的最大值x0=[0,0,0,0];%x取迭代初始值[t,w]=linprog(c,A,b,Aeq,beq,xL,xU);%目标为最小的线性规划t=t,y=w%等价转换目标为最大并输出（3）functionf=fun3(x);f=x(1)2*x(2)+(1/2)*x(1)^2+(1/2)*x(2)^2x0=[1;1];A=[23;14];b=[6;5];Aeq=[];beq=[];VLB=[0;0];VUB=[];[x,fval]=fmincon('fun3',x0,A,b,Aeq,beq,VLB,VUB)（4）x=linspace(0,2*pi,30);y=sin(x);z=cos(x);plot(x,y,'r',x,z,'go'),gtext('sin(x)');gtext('cos(x)');2（5）x=[1:1:12];y=[9,10,11,12,13,14,13,12,11,9,10,11];a1=polyfit(x,y,3)%三次多项式拟合系数降幂排列;a2=polyfit(x,y,5)%五次多项式拟合；a3=polyfit(x,y,8)%八次多项式拟合；b1=polyval(a1,x)%三次拟合多项式的值；b2=polyval(a2,x),b3=polyval(a3,x),r1=sum((yb1).^2)%三次多项式误差平方和，r2=sum((yb2).^2)%五次次多项式误差平方和；r3=sum((yb3).^2)%八次多项式误差平方和%plot(x,y,'*')%用*画出x,y图像%holdon，plot(x,b1,'r')%用红色线画出x,b1图像%holdon，plot(x,b2,'g')%用绿色线画出x,b2图像%holdon，plot(x,b3,'b:o')%（6）clear,forn=1:200x(n)=n;t(n)=sin(n*pi/50);plot(n,t(n),'*'),holdonend,plot(x,3*cos(2*t).*exp(t),'')第二部分题目解答任务一：本文就试卷评阅的几个方面作了对比分析，在试卷分配方面利用0-1规划的分层多目标规划解决了试卷的合理分配问题；在对分数的统计排名方面，建立基于关联度分析的试卷综合排名，并对评委评分的评分准确性进行排名，建立评委的评卷水平对试卷排名的反馈体系。比较发现，以上方法均优于传统的试卷评阅方式。对于问题一，本文根据题中抽象出的约束条件建立基于0-1整数分层多目标规划，实现了试卷分配的均衡分散型好的目标。在每份试卷有4位评委评阅的情况下，任意两份试卷间的相同评委数和同一学校的试卷的分散性同时实现了较好。对于问题二，本文基于最大相关度理论，将不完全打分矩阵转化为完全打分矩阵，消除了传统阅卷形式中因评委评分尺度不同造成的排名失真；同时在消除并列排名的问题；最后证明了本文的模型在对评委出现误判的情况下，具有较强的纠错能力。对于问题三，本文基于问题二中构建的完全打分矩阵引入偏差度，建立识别评委作用的反馈控制，给出了对评委打分排名的反评判指标体系；对问题二中引入的案例二求解，得到带反馈值的试卷排名。对于问题四，本文引入实际案例三，根据各个完全评分子模块的稳定性，引入修正系数。每个子模块的初始分数与各模块对应的修正系数即建立起具有相同评分标准的打分系统，实现全部试卷的真是排名；同样的根据评委打分的偏差度，得到了评委的排名。任务二：本文研究如何建立数学模型解决两类最佳乘车路线的问题：如何才能换乘最少的公交车（即最省钱）的乘车路线或经过最少的站点（即距离最短，最省时间）的乘车路线就能到达目的地。文章先阐述问题，然后提出假设简化问题，然后利用3图论中解决最短路径的算法建立数学模型解决问题，最后在计算机上实现解决问题的算法。任务三：学习数学软件（MathType5.2、MATLAB、Maple、Mathematica4.0、LINGO8.0）安装调试；基本命令使用（变量赋值、定义函数、过程控制、绘图命令、拟合、线性规划、非线性规划）；高等数学实验（绘图，极限，求导，积分，解微分方程）；线性代数实验（矩阵基本运算，线性方程组求解，解超定方程组，优化命令）。并在提交的综合训练文档附录中的给出6个程序的译文(数学模型)及解答。第三部分典型作品展示一、论文摘要平常我们出门乘车要去某一个地方，如果要去的地方我们经常去，就可以凭以前的经验就知道如何坐车去最好。如果那个地方以前没去过，我们会问身边的亲戚朋友，如果他们去过，就会知道怎么乘车，或者查看地图，看如何才能乘车去那个地方。这样虽然能找到一个乘车方案，但不一定是最佳的方案，这里指的最佳是指花最少的车费或花最少的时间就能到目的地的乘车方案。本文要解决的问题就是如何解决找到求解最佳乘车路线的数学模型。二、问题假设1.所有公交线路都是始终能乘坐的，或者所有的公交线路的首班和末班时间都是一样的。2.假设所有的公交线路的车费是一样的，而且同一条公交线路没有空调车与非空调车两种车费。3.假设所有的站点之间的距离是相同的，而且所有的公交车的时速是相同的，而且不考虑道路车流的情况。三、分析问题由问题可以很容易地看到可以用图论的相关知识来解决这个问题。由于所有公交线路都是始终能乘坐的，或者所有的公交线路的首班和末班时间都是一样的，所以只要构造一个图就可以了，或者构造的图不会随着时间而变化。由于一条公交线路来去两个方向经过的站点有可能是不同的，所以所构造的图是一个有向图。由于假设所有的公交线路的车费是一样的，而且同一条公交线路没有空调车与非空调车两种车费，也就意味着乘坐的公交车越少也就越省钱。所以在求解最经济的乘车路线，也就是最省钱的乘车路线时可以用换乘最少的公交车的乘车路线来近似最省钱的公交路线。由于所有的站点之间的距离是相同的，而且所有的公交车的时速是相同的，而且不考虑道路4车流的情况，也就意味着经过的站点越少就越省时间。所以在求解最省时间的乘车路线就可以用经过最少站点的乘车路线来近似花时间最少的乘车路线。四、建立模型以站点为图的结点，点之间的连线表示站点之间有公交线路经过这两个站点。点之间的连线是有向线段A-B,表示有从A站的下一站就是B站的公交线路,但没有从B站的下一站是A站的公交线路。A==B表示即有从A站的下一站是B站的公交线路又有从B站的下一站是A站的公交线路。模型如下定义结点之间的距离，设代表A站的图上的结点为a,代表B站的图上的结点为b。设A站的下一站就是B站。出发点为S站,代表S站的图上的结点为s，目的地为D站，代表D站的图上的结点为d.求解最少换乘的乘车路线时求a到b的连线的长度：设从出发站到A站的最短乘车路线上，到A站时乘坐的公交线路集合为Ca,设从出发站经A站到B站的最短乘车路线上，到B站时乘坐的公交线路集合为Cb,A站下一站就是B站的公交线路的集合为Ca-b,如果Ca与Ca-b的集合非空，则Cb等于Ca与Ca-b的交集，a到b的连线的距离为0，如果Ca与Ca-b的集合为空，则Cb等于Ca-b，a到b的连线的距离为1。出发点S站的Cs等于空集。如图1图1图中结点为公交站，连线上的数字代表公交线路Ca={1,2},Ca-b={1,4},因为Ca交Ca-b非空，所Cb=Ca交Ca-b={1}a到b的连线的长度为0。Cb-c=3,Cb交Cb-c为空集，所以Cb等于Cb-c，b到c的连线的长度为1。要注意的是在求解最少换乘的乘车路线时求a到b的连线的长度是在求最短路径时动态确定的。而求解经过最少站点的乘车路线时求a到b的连线的长度是恒定为1的求解经过最少站点的乘车路线时求a到b的连线的长度：如果A站的下一站就是B站的公交线路存在，a到b的连线的长度就为1。一旦定义了结点之间的距离，就可以采用Dijkstra算法计算出发站点到目的站点的最佳乘车路线，也就是结点s到结点d的最短路径。Dijkstra算法在各本图论或离散数学的书上都有介绍，这里就不做介绍了。5五、模型的计算机实现源代码（附于文章之后，从略）测试结果测试数据(data.txt):ABCDEF12341ABDF2ABE3ACE4AEF出发站点：A目的站点:F最少换乘（最经济）的乘车路线：A-B-D-F经过最少站点（最短距离，最省时间）的乘车路线：A-E-F六、模型的改进求解最少换乘的乘车路线由于结点过多，可能导致计算效率下降，可以如下改进：设图的结点代表公交线路，代表X路公交线路的图上的结点为x,代表Y路公交线路的图上的结点为y,如果X路公交线路与Y路公交线路有公共的站点，则图上结点x与y之间有连线，连线的长度为1，如果X路公交线路与Y路公交线路没有公共的站点，则图上结点x与y之间没有连线。经过出发站点的公交线路有n条，经过目的站点的公交线路有m条，增加一个连到代表经过出发站点的所有公交线路的n个结点的结点a，a到这n个结点的距离为0;再增加一个连到代表目的站点的所有公交线路的m个结点的结点b,m个结点到结点b的距离为0，然后用Dijkstra算法计算从结点a到结点b的最短路径，就是最少换乘的公交路线。如果去掉模型中所有的公交线路的车费是一样的，而且同一条公交线路没有空调车与非空调车两种车费这一个假设，可以把空调车与非空调车区分为两条不同的公交线路，并把每条线路的价格定义为结点之间的距离。这样就可以更精确地得到最经济的乘车路线了。模型假设所有公交线路都是始终能乘坐的，或者所有的公交线路的