论文总字数：56178字

摘 要

本文研究了一个考虑学生之间不满意度的宿舍分配问题，建立了求解分配方案的几个数学模型及算法。

以学生学号为依据为学生安排宿舍可以方便学校管理，但不同学生有着不同的生活习惯和忍耐程度，被随机配对的舍友之间可能存在截然不同的生活习惯，这些生活习惯上的不同会带来摩擦和不协调，需要学生相互适应。

提出以生活习惯的不相容度作为学生之间作为舍友不满意程度的衡量指标，设计分配方案尽量使得学生的不相容度总和最小。本研究探索了这一问题三种形式的数学规划模型，并设计了求解该问题禁忌搜索算法。通过模拟比较，线性整数规划在求解宿舍分配问题时能保持最高的结果精度，时间上相比二次整数规划存在明显优势；禁忌搜索时间最快，在规模较大的问题上适用性强，且结果质量可以接受。

关键词：学生宿舍分配，组合优化，二次整数规划，线性整数规划，禁忌搜索

ABSTRACT

In this thesis, a student dorm assignment problem considering dissatisfaction was investigated, and several mathematical models and algorithms solving this problem were built.

It's convenient for school management to assign students to dormitories according to their student IDs. However, different students have different lifestyle and tolerance level, which may cause totally different habits among roommates. These differences can arouse disharmony and conflicts, and force the students to adapt to each other.

In this thesis, Incompatibility of Lifestyle was proposed as the measurement of dissatisfaction towards each other when students become roommates. An assignment schema with smallest students' total incompatibility is desired. Three mathematical programming models were explored, and a tabu search algorithm was designed. Simulation shows that linear integer programming can obtain most precise result and exceed quadratic integer programming on speed; while tabu search runs fastest, with an acceptable result quality on relatively-large scale instances.

KEY WORDS: student dorm assignment, combinatorial optimization, quadratic integer programming, linear integer programming, tabu search

目 录

摘 要 I

ABSTRACT II

第一章 绪论 1

1.1 问题背景和意义 1

1.2 国内外研究现状 1

第二章 模型的基本设定 4

2.1 基本假设 4

2.2 模型共通符号定义 4

2.3 不满意程度的度量 4

2.3.1 距离 5

2.3.2 不相容度 5

2.4 求解目标及目标函数 7

第三章 数学规划模型表示 8

3.1 二次整数规划模型 8

3.2 二次指派问题形式 10

3.3 线性整数规划模型 12

第四章 用于禁忌搜索的问题模型及算法设计 17

4.1 算法基本流程 17

4.2 算法关键要素的设计 18

4.2.1 解的形式 18

4.2.2 初始解 18

4.2.3 解的邻域与候选集 19

4.2.4 评价函数 20

4.2.5 禁忌表，禁忌对象与禁忌表长度 20

4.2.6 特赦规则 21

4.2.7 终止规则 21

第五章 模型的实施与算法测试 22

5.1 不相容度的获取 22

5.2 算法测试 22

5.2.1 参与测试的模型或算法 22

5.2.2 测试方法 23

5.2.3 模拟数据的生成 23

5.2.4 算法测试结果 24

第六章 总结与展望 29

6.1 模型考虑因素的扩展与效果优化 29

6.2 变种问题与模型改造 29

6.3 模型的局限 29

致 谢 30

参考文献 31

附录 32

附录 A 学生11项生活习惯问卷 32

附录 B 线性整数规划与二次整数规划C 代码 35

附录 C 禁忌搜索C 代码 41

附录 D 模拟生成学生生活习惯数据C 代码 47

附录 E 通过学生生活习惯数据计算增广学生不相容度矩阵的C 代码 48

绪论

问题背景和意义

在文化多元、开放的今天，人们的生活方式多种多样。步入大学后，由于课业紧张程度的下降和大学课程时间安排组织的灵活性，大学生们对课余时间以及作息规律等的安排，随各人个性的不同得以呈现出各异的差别。

在校大学生数量日益增多，大学的宿舍形式基本为多人同舍，根据各学校及具体实际情况的不同有2人间、4人间、6人间等。在同一间宿舍居住的学生如果生活习惯存在不同，会有诸多不便：有的学生习惯早睡早起，有的学生喜欢在熄灯后熬夜、早晨睡懒觉；有的学生睡眠不深，有的学生睡觉时打呼噜或在深夜喧闹；有的同学对温度变化敏感，有的学生喜欢开窗通风；有的学生只需要与外界适宜的温度，有的同学倾向于将夏天的空调温度调得较低或在冬天调得较高；有的同学需要睡午觉，有的中午喜欢放松娱乐；有的学生喜欢安静的环境、倾向于在宿舍学习，也有学生喧闹、不在意维持静谧的环境，在宿舍用语音玩游戏、使用扬声器放音乐或看视频；有的人喜欢干净的环境，有的人不重视个人卫生或宿舍卫生。

和与自己生活习惯不同的人一起生活，不但影响心情，休息质量无法得到保障，学习和工作效率都会受影响。不同生活习惯的人之间相互适应需要时间，在刚入学的一段时间内精神和生理状态难免会受影响。由于人们适应能力的强弱不同，受此影响的时间有长有短，适应能力弱、或与室友的生活习惯差别较大的人，可能需要很长时间才能适应；更甚会出现宿舍关系不和睦，引发不必要的冲突，对学习生活影响很大。

同宿生活导致的生活习惯的差异难以避免，但可以通过合理的宿舍安排方式减轻。目前已有部分学校在开学前调查学生生活习惯、行为爱好等，入学时为住校学生安排生活习惯相近的舍友，为学生提供和睦的宿舍环境以提高学生生活质量。而部分高校仍采用传统方式为学生安排宿舍，以专业、班级或学号依次将学生合并入一间宿舍中，以方便管理为目标，没有将学生的差异纳入考量；学生的宿舍生活质量存在相当大的优化空间。

国内外研究现状

国内有不少学者对学生宿舍分配问题进行过分析，提出了能获得可行且较满意解的算法。

剩余内容已隐藏，请支付后下载全文，论文总字数：56178字