logo资料库

分配问题的优化模型-试卷的合理分配问题.doc

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.09M 资料格式：doc 举报 版权申诉
第1页 / 共16页
第2页 / 共16页
第3页 / 共16页
第4页 / 共16页
第5页 / 共16页
第6页 / 共16页
第7页 / 共16页
第8页 / 共16页
资料共16页，剩余部分请下载后查看
    试卷分配问题的优化模型 摘要 本文主要研究试卷的合理分配问题。试卷分配的合理性既是竞赛 规则的要求，也是竞赛评判的公平性的重要保证。因此，解决试卷分 配的合理性问题有很强的现实意义。本文所考察的考试涉及 200 余份 试卷和 12 位评委，数据规模大，人工求解分配方案计算量较大，难 以实现。为此，我们采用了计算机编程的方法解决问题。
    对问题一，我们采取了下面的方法： （1）利用计算机随机产生一系列的试卷分配方案，在此过程中，通 过机器判断，使产生的试卷分配方案满足 R1、R2 和 D2 的要 求。 （2）利用不均衡度 D 对（1）中的试卷分配方案进行限制，使产生 的试卷分配方案满足 D1 的要求。 （3）利用不均衡度 Dd 对（2）得到的方案进行筛选，使得输出的试 卷分配方案满足 D3 的要求。从而得出问题一的比较公平合理 的分配方案。 （4）用上述方法产生 50 个可行解，筛选出它们中两位或三位评委相 同的情况较少的解。 这样我们得到了问题一的解。 在问题一的基础上，我们通过讨论，采用了同一份试卷的四个评 委中，判高分和判低分的评委数最多相差 1 的限制条件，得到问题二 的解。 关键词：公平 随机 不均衡度 D 加权不均衡度 Dd 一、 问题背景 数模竞赛一般采取多位评委打分的方式确定名次，评委大都来自 各参赛高校。
    竞赛规则规定： R1.每份试卷由四位不同的评委评阅。 R2.每个评委只能评阅非本单位的试卷。 同时，为了保证最终阅卷结果的客观性与公正性，竞赛组委认为 一个理想的试卷分配方案应满足如下要求： D1. 各评委评阅的试卷数量应尽可能均衡。 D2. 任意两份试卷不能由相同的四位评委评阅，并应尽量减少 有两位或三位评委相同的情况。 D3. 同一单位的试卷在评委中的分布应尽量均衡。 我们需要根据上述要求设计合理的试卷分配方案，并就附录中的 数据实例给出具体的分配方案及该方案对 D1～D3 的满足情况。 在此基础上，根据以往评阅记录，统计得出各位评委的判分高低 倾向，例如附录中评委 1、2、3 有判高分倾向，评委 4、5、6 有判低 分倾向，如何利用此信息结合以上要求设计公平合理的试卷分配方案 是我们面临的又一问题。 二、符号说明 D——不均衡度
    Dd——加权不均衡度 iN——第 i 个单位的试卷总数 p[i]——第 i 位评委（1≤i≤12）的实际阅卷量 iA(j)——第 j 个评委评阅的第 i 个单位的试卷的份数（1≤j≤12） iB——i 号单位的试卷按理想情况平均分给各位评委时，每位评 委得到的 i 号单位试卷数 三、问题分析 我们的目标是建立一个公平合理的试卷分配方案。所谓“公平合 理”是指满足竞赛规则规定 R1、R2 并尽量满足理想的试卷分配方案 的要求 D1、D2、D3。其中 R1 是对评委评阅试卷“广泛性”的要求， 即一份试卷尽量由较多数量的评委评阅以避免仅由一位评委评阅所 引起的成绩的不公平性、主观性和偶然性；R2 是为了避免评委对本 单位的试卷人为的抬高分数；D1 是为了使每位评委都能够同等程度 的参与到试卷的评阅之中，避免少数评委对整体的评卷结果影响过 大；D2 增加了评委组合的多样性；D3 避免了同一单位的试卷仅由 少数的几位评委评阅，当这几位评委有判分不公正倾向时，该单位整 体将会受到不公正的待遇。 1、不均衡度 D 与要求 D1
    对于条件 D1 我们设置一个参数 D，称为“不均衡度”。227 份试 卷共需要 227*4=928 人次评阅，因此，每位评委在理想情况（试卷分 配均衡）下，每人评阅的试卷数是 928/12=227/3 份。对于一种确定的 试卷分配方案，我们统计出第 i 位评委（1≤i≤12）的实际阅卷量 p[i]， 以此计算 D。 D 的计算公式为： D=∑{(p[i]-227/3)*(p[i]-227/3)} （1≤i≤12） 2、加权不均衡度 Dd 与要求 D3 1）选择了 Dd 作为条件 D3 的限制条件的原因 对于条件 D3 我们设置了一个参数 Dd，称为“加权不均衡度”， 具体含义、计算方法见步骤 2）。对于某一种试卷分配方案，我们可 以统计出 33 个单位各自的试卷在评委中的分布情况。由此，对于单 位 i ， 我 们 有 了 12 个 数 据 iA(1)--iA(12) ，（ 其 中 1 ≤ i ≤ 11 时 ， iA(i)=0）,iA(j)表示第 j 个评委评阅的第 i 个单位的试卷的份数（1≤j ≤12）。D3 要求同一单位的试卷在评委中的分布应尽量均衡。我们固 然可以对每个单位都设置限制条件，使试卷的分配方案很好的满足 D3 的要求，但这些限制条件的增加，有可能成为计算机程序运行时 的主要．．障碍，导致时间复杂度过大，况且仍有其他多项限制条件，若 此处条件过窄，有可能得不到较好满足题目其他要求的解。从整体考 虑，我们选择了 Dd 作为 D3 的限制条件。
    2）设参数 iN 表示第 i 个单位的试卷总数，设参数 iB 表示 i 号单 位的试卷平均分给各位评委时，每位评委得到的 i 号单位试卷数(由于 本单位的评委不评阅本单位的试卷，当 i≤11 时 iB=iN*4/11)。比如， i=14 时，14 号单位有 4 分试卷，需要 4*4=16 人次评阅，因此，每位 评 委 在 理 想 情 况 （ 试 卷 分 配 均 衡 ） 下 ， 每 人 评 阅 的 试 卷 数 是 14B=16/12=1.3 份。第 j 个评委实际评阅的 14 号单位的试卷的份数（1 ≤j≤12）是 14A(j),此时实际情况与理想情况下的偏差可以用 Dd(14)=∑{（14A(j)- 14B）*（14A(j)- 14B）}（1≤j≤12）表示。 当 i≥12 时，Dd(i)=∑{（iA(j)- iB）*（iA(j)- iB）}（1≤j≤12）, 当 i≤11 时，Dd(i)=∑{（iA(j)- iB）*（iA(j)- iB）}（1≤j≤12，j ≠i）, Dd 的计算公式为：Dd=∑{Dd(i)*iN/227}（1≤i≤33） 3、D2 的较好满足 对 D2 中任意两份试卷不能由相同的四位评委评阅的要求，我 们在将评委组合进行排序时加以控制；对于 D 2 中要求尽量减少有 两位或三位评委相同的情况，我们采取了让计算机随机产生 50 组可 行的解，通过比较各可行解的三位评委和两位评委数目相同情况的 多少，检验并输出三位评委相同的情况最少的解，。这样保证了在一 定的范围内能够较好的满足 D2。 4、问题一的解题思路
    该题出现了较多的数据，且评委有多种组合，人工求解较为繁琐。 因此我们采用了计算机编程求解的方法。 我们的整体思路是：利用计算机随机的产生一系列的试卷分配方 案，根据竞赛规则规定 R1、R2 和要求 D1、D2、D3 对方案进行筛选， 使得输出的试卷分配方案满足 R1、R2 并尽量满足 D1、D2、D3。从 而得出问题一的比较公平合理的分配方案。 5、对问题二的讨论 评委 1、2、3 有判高分倾向，评委 4、5、6 有判低分倾向，我们 采用了在问题一求解的基础上，增加限制条件，求问题二情况下较公 平合理的分配方案的方法。我们认为一位高分评委和一位低分评委所 打的分可以“相互抵消”，即由他们打的分数计算出来的试卷的平均 成绩仍是正常的成绩。由此我们给出问题二的具体的限制条件是：在 同一份试卷的四个评委中，判高分和判低分的评委数最多相差 1。若 判高分和判低分的评委数相差大于 1，我们认为这份试卷的成绩将过 分的偏高或偏低，造成该试卷评分不公。这样就排除了下表所列的情 况： 高分评委数目 低分评委数目 3 0 3 1 0 3 1 3
    2 0 0 2 这样我们在问题一求解的基础上得到了满足问题二的比较合理 的解。 四、模型的建立与求解 1、问题一 模型的建立与求解 解决问题一时，我们采用 c++语言进行编程，具体步骤如下： 1) 产生 495 种满足 R1 的由四位评委组成的评委组合，并 依次对其进行编号为 1—495。（见附录一） 2) 从以上 495 种评委组合中，随机抽取 227 种且排序，在 排序的过程中，检验其是否满足 R2 和 D2。排序的过程中，若 出现某一单位的评委评阅本单位试卷的情况（违背了 R2）或任 意两份试卷由相同的四位评委评阅的情况（违背了 D2），则停止 排序，返回步骤 2）的开始并重复步骤 2），直至产生满足 R2 和 D2 的试卷分配方案，对这个方案进行编号，依次对应 1—227 号试卷。 3) 对 2 中产生的 1—227 号试卷的分配方案，若满足 D≤ 150 且 Dd≤24 时，进入下一步骤，否则返回步骤 2）的开始并 重复步骤 2）（150 与 24 的产生：在不限制 D、Dd 的值的情况
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料