竞赛评卷地分配问的题目.doc

word
word
1 / 29
word
公平的竞赛评卷系统模型
摘 要
〔略〕
word
word
2 / 29
word
位屏蔽掉。显然这里的Y应该有4位为1，其他位为0。
对于明码D，通过掩码Y对无效位填充随机数码，得到64位码DY。
对DY进展DES加密，K为密钥，最终得到一个64的密码。
解密时按密钥K和掩码Y对密码进展解密得到原明码。
此加密算法基于DES，因此它的加密效果也更好，理论上破译可能很小，目前还只能通过计算机穷举，而DES实际密钥长度为56位，2的56次方的空间计算机要搜上千年，而掩码Y的穷举空间为C。这些都超过了解码的穷举空间10的4次方。综上可以说明这种加密算法是理论上最优的。
模块二 试卷的分配
数据分析：
分析给出的XX赛区参赛情况表得到如下图：
word
word
5 / 29
word
图2
其中深蓝，浅蓝，黄色，棕色分别代表A，B，C，D题。
从图中可以看出A，B题集中在1-19号学校，C,D题集中在20-35号学校，且A，B题总数量显著高于C，D。5号和14号学校有少量的Ｃ，Ｄ题。
现在综合考虑一下要求，每份试卷经四位评委评阅，每位评委回避本校试卷，每个评委只评一类型题。那么我们可以假定，对于Ｋ号评委，如果他评的一道题目为Ｘ类型，且学校Ｋ的Ｘ类型题数量不为０，为满足要求，如此需其他４位评委来评，也就是说Ｘ类型题至少需５位评委评阅。如果评Ｘ类型题的所有评委所在学校都无Ｘ题，如此最少需４位评委评阅X类型题。
现在考虑一个理想化的情况：对于评委Ｋ分配到的题目数Ｎ，Ｎ＝Ｎ＝．．．Ｎ即每位评委所评试卷数一样，Ｎ份卷子来自Ｎ个不同的学校〔满足广泛性〕，且均为同一类型题Ｘ〔依题型将评委分组〕，而所有学校的卷子都没有剩余，并且卷子的分配满足了所有评委的特殊需求。每份试卷至少经过四位评委评阅。
显然这是一个离散的整数优化问题。从数据中观察，试卷总数为２９８份，而评委为２５名，来自不同学校。所以所有Ｎ不可能全部一样。我们的优化目标应该是所有评委分配的试卷数量差的绝对值最小，并且使Ｎ份试卷来自的学校数Ｓ最大。
模型的建立与求解：
由分析得此优化问题的数学描述：
word
word
6 / 29
word
设　x表示评委ｋ是否评第ｉ个学校的ｊ号题〔Ｘ取值为０或１〕，Ｙ表示评委ｋ是否评ｎ题〔ｎ为ＡＢＣＤ中的一题〕，Ｔ为每份卷子的评阅次数，Ｚｉｊｎ表示学校ｉ的ｊ号题是否为ｎ题〔Ｚｉｊｎ取值为０或１〕。
ｍｉｎ．〔ｍａｘ〔〕，－ｍｉｎ〔〕〕
ｓ．ｔ．
＝１，ｋ＝１，２．．．Ｎ；
＝Ｔ，　ｉ＝１，２．．．Ｎ　ｊ＝１，２．．．Ｎ；
Ｙｎｋ·Ｚｉｊｎ≥Ｘｉｊｋ，ｉ＝１，２．．．　ｊ＝１，２．．．　ｋ＝１，２．．．　ｎ＝１，２．．．〔ｎ取ＡＢＣＤ中的一题〕
Ｘｉｊｋ＝０，ｉ＝ｋ，ｊ＝１，２．．．
n=1,2,3,4
另外还有一些其他的评委特殊要求。
〔后附ｌｉｎｇｏ源码〕
问题分析到这里已经很清晰，但用ｌｉｎｇｏ求解发现，此问题的数据量很大，变量数目庞杂，运算的时间复杂度和空间复杂度惊人，存在数据溢出问题。因此应重新修改模型，以获得一个可行的解决方案。
装箱法
我们知道，问题最终的最优解是一个全局最优解。设试卷总量为Ｓ，对于Ｓ中一局部Ｄ，如果Ｄ不是非常接近Ｓ，也就是说Ｄ和Ｓ相差一局部空间。那么Ｄ的最优解也是Ｓ的解的一局部。此法称为装箱法，即缩小问题的空间和规模，将解的空间想象为一个箱子进展填充，以求缩小问题求解难度。
综上修改后的模型可以表述为：
按照最优目标和要求对问题的解空间进展填充，将原问题转化为一个规模较小的问题；
通过前面的最优化模型对转化后的问题进展求解，得到该问题的解；
综合两局部解，得到最终的全局最优解。
对装箱程序的一点解释：此程序要求输入，试卷的信息，并指定评委参加哪个题组，即评阅哪道题〔Ａ，Ｂ，Ｃ，Ｄ〕。
设　　题目　有Ａ，Ｂ．．．Ｘ．．．；每道题的试卷数量为Ｎｘ，试卷总量为Ｎ，题目Ｘ分到的评委为Ｐｘ人，评委总数为Ｐ人。如此应有Ｐｘ／Ｐ≈Ｎｘ／Ｎ，即评委分配比例近似一样。对于此题的数据，评Ａ题８人，Ｂ题９人，Ｃ题４人，Ｄ题４人。
在满足评委特殊要求的前提下，为达到最优，还应尽量减少评委评到本校题目的可能性。仔细考虑一下，可以选择的方案并不多，可以通过枚举求得最优解。
评委分配的一个初始表：
题组
评委号
Ａ
１，４，６，１２，１４，１６，２０，２１
word
word
8 / 29
word
Ｂ
２，５，７，１０，２４，２６，２８，２９，３０
Ｃ
１１，１３，2