摘要本文根据我校大学生自主选修课程的选课情况，应用整数规划中的指派问题建立模型解决如何合理安排课程的相关问题。我们根据每位同学对每门课程的感兴趣程度与该课程的通过率的不同，统计出相关学生的选择放弃选择该课程的概率系数。并在学生，课程，弃选概率系数给定的条件下，利用整数规划模型对该学生选课问题进行了优化调整。50420

In this paper we try to solve the problem how students select their courses rationally. According to the students’ interests and the difficulties of the courses, we assign a rate to each student and each course. This rate shows the probability the student will abandon the course. Then we established an integer programming model to obtain the optimized assignment of the courses.   

毕业论文关键词：学生选课； 整数规划； 指派问题

Keyword: students’ course¬-selection; integer programming; assignment problem

目录

1 整数规划问题 4

1.1整数规划的历史与发展 4

1.2整数规划数学模型的一般形式 5

1.3整数规划的分类及建模举例 5

1.3.1混合整数规划 5

1.3.2 纯整数规划 6

1.3.3 全整数规划 7

1.3.4  0-1规划/0-1整数规划 8

2 指派问题与匈牙利法 9

2.1指派问题的提出与数学模型 9

2.1.1指派问题的提出 9

2.1.2指派问题的数学模型 9

2.2 匈牙利法 10

2.2.1 匈牙利法的基本原理 10

2.2.2 匈牙利法的解题步骤 12

3  整数规划在大学生自主选课中实际应用 13

3.1 当代大学生自主选课所面临的问题 13

3.2 指派模型的建立 14

3.2.1选择原始数据 14

3.2.2 建立整数规划模型 15

3.3 指派模型的求解 16

3.3.1 求解的程序 16

3.3.2求解的结论 17

3.3.3确定弃选概率系数的可信性 17

致谢 18

参考文献 19

1 整数规划问题1.1整数规划的历史与发展

整数规划它的历史可以追溯到古希腊伟大数学家丢帆图（Diophantine）对线性不定方程的整数解的研究。现代整数规划的理论和方法几乎是和（运筹学的）线性规划同时生产和发展的。20世纪50年代，运筹学的创始人和线性规划中单纯形算法的发明者Dantzig首先发现可以用0-1变量来刻画最优化模型中的固定费用和变量上界及非凸分片线性函数等。他和Fulkerson及Johnson对旅行售货员问题（TSP）的研究成为后来的分枝-割方法和现代混合整数规划的算法的开端。经过50多年的研究，随着整数规划理论和算法的发展，整数规划已成为最广泛应用的最优化方法之一。特别是近几年来整数规划算法技术和软件系统（如CPLEX）的发展、推广、完善，整数规划在生产企业、服务、运营管理、交通、通信等领域得到了极大的应用和发展，并日益受到人们的重视。如基于分枝定界和各种松弛技术的算法已日趋成熟并开发为各种优化模型和算法商业软件，使得整数规划在学术界、工业界得到了广泛的应用；二次0-1规划和多项式规划的领域近些年来都取得了不小突破，是目前国际运筹学和最优化研究的热点之一。整数规划的应用领域包括：民航航班与机组的调度；列车和公共交通的调度；生产计划与调度；通信与网络；电厂发电计划；大规模集成电路设计等等。