论文部分内容阅读
【摘要】本文通过对整数规划原理的分析，结合自身实际研究了一个由整数规划所描述的选课模型。利用计算机软件编程，给出了该整数规划的解，进而获得该模型的所有最优方案。
【关键词】整数规划 选课模型 最优解
1．整数规划原理。在整数规划中，为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。整数规划的一种特殊情形是0－1规划，它的变数仅限于0或1。0－1规划在整数规划中占有重要地位，可以解决许多实际问题，例如指派问题、选地问题、送货问题等等。
0－1整数规划的一般模型是：
2．课程优选模型的建立。
2．1 问题的提出。现在，多数高校采取的都是学分制，大学课程是按学分值进行设置的，大学生学费主要依据按学分多少收取。学生可以根据自己的兴趣爱好选择自己所喜欢的课程，但是不合理的选课将造成学校资源的浪费，同时也将增加学生的选课费用。因此，合理选择所学课程是大学生学习过程中的一个重要组成部分。能否合理优选自己的课程，不但是我们顺利完成学业的关键，还可以为我们自己节约大笔费用，节约学校的教学资源，达到经济合理学好知识的目的。
目前，高校所学课程类型主要有三种：必修课程、限选课程和选修课程。必修课程是必选学科，而限选课程和任选课程则可以根据个人的爱好自己决定。学生可以根据自己的实际情况和学校关于学分选择的规定，采用适合的方法，合理优选出自己的选课计划。我们可以借助0－1整数规划原理建立课程优选模型来解决此问题。下面结合某高校学生的选课实例对课程优选模型予以阐述。
2．2 模型的建立。
某高校学生要求经济合理地选择大三下学期课程。该学期可选课程中包括必修课程共7门，总共17个学分（此7门必修课程未在文中列出）；限选课程共有14门，任选课程有15门。限选课程和任选课程的学分设置情况以及部分课程之间的关系见表1。另外，学校关于选课的相关规定如下：
①所选课程的总学分不能少于26学分；
②任选课的至少选1门；
③限选课的至少选2门；
④必选课的学分为120元/学分，限选课程为108元/学分，任选课程为98元/学分。
我们针对上述情况建立0－1整数规划模型。具体如下：
①选取所选学分总费用最小值作为本问题的目标函数z；
②用xi表示是否选择课程，其中，xi=1表示该课程被选择，xi=0表示该课程未选择；
③若选课程i时必须同时选课程j，则可以用xi-xj=0表示；
④若选课程i前先选课程j，则用 ， 表示；
⑤若两门课程不能同时选，则用 表示。
于是，建立如下的数学规劃模型：
2．3 求解模型。用VB编程来求解上述问题，运行结果为：x3=x4=x23=x25=1，其他xi=0。即选修4门课程，课程标号分别是3，4，23，25；本学期的最低学费为2962元。
一般来说，得到一个整数规划问题的最优解是很困难的，所以该整数规划模型的解也不唯一。我们通过对变量的约束进行隐式枚举的方法给出其他一些选课方案，见表2。
由于必修，限选和任选课程学分的费用不一样。所以由表2可以得出，要使费用最低，则在满足模型的情况下，尽量选择费用最低的任选课程，并所选的学分不超过总选修的9个学分。在本文中所给出的所有最优的选课方案中，学费最低的为选修4个学分的限选，5个学分的任选，其总的最低学费为2962元。
3．结束语。本文利用0－1整数规划原理建立模型解决了高校学生课程优选问题。实际上，整数规划原理已广泛应用于我们的生产生活当中，它不仅在工业和工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。
参考文献
1 焦永兰主编.《管理运筹学》[M].北京:中国铁道出版社, 2007
2 郭耀煌主编.《运筹学原理与方法》[M].成都:西南交通大学出版社,1994
3 刘寿春.整数规划模型研究.皖西学院学报[J].2004.4(2)
【关键词】整数规划 选课模型 最优解
1．整数规划原理。在整数规划中，为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。整数规划的一种特殊情形是0－1规划，它的变数仅限于0或1。0－1规划在整数规划中占有重要地位，可以解决许多实际问题，例如指派问题、选地问题、送货问题等等。
0－1整数规划的一般模型是：
2．课程优选模型的建立。
2．1 问题的提出。现在，多数高校采取的都是学分制，大学课程是按学分值进行设置的，大学生学费主要依据按学分多少收取。学生可以根据自己的兴趣爱好选择自己所喜欢的课程，但是不合理的选课将造成学校资源的浪费，同时也将增加学生的选课费用。因此，合理选择所学课程是大学生学习过程中的一个重要组成部分。能否合理优选自己的课程，不但是我们顺利完成学业的关键，还可以为我们自己节约大笔费用，节约学校的教学资源，达到经济合理学好知识的目的。
目前，高校所学课程类型主要有三种：必修课程、限选课程和选修课程。必修课程是必选学科，而限选课程和任选课程则可以根据个人的爱好自己决定。学生可以根据自己的实际情况和学校关于学分选择的规定，采用适合的方法，合理优选出自己的选课计划。我们可以借助0－1整数规划原理建立课程优选模型来解决此问题。下面结合某高校学生的选课实例对课程优选模型予以阐述。
2．2 模型的建立。
某高校学生要求经济合理地选择大三下学期课程。该学期可选课程中包括必修课程共7门，总共17个学分（此7门必修课程未在文中列出）；限选课程共有14门，任选课程有15门。限选课程和任选课程的学分设置情况以及部分课程之间的关系见表1。另外，学校关于选课的相关规定如下：
①所选课程的总学分不能少于26学分；
②任选课的至少选1门；
③限选课的至少选2门；
④必选课的学分为120元/学分，限选课程为108元/学分，任选课程为98元/学分。
我们针对上述情况建立0－1整数规划模型。具体如下：
①选取所选学分总费用最小值作为本问题的目标函数z；
②用xi表示是否选择课程，其中，xi=1表示该课程被选择，xi=0表示该课程未选择；
③若选课程i时必须同时选课程j，则可以用xi-xj=0表示；
④若选课程i前先选课程j，则用 ， 表示；
⑤若两门课程不能同时选，则用 表示。
于是，建立如下的数学规劃模型：
2．3 求解模型。用VB编程来求解上述问题，运行结果为：x3=x4=x23=x25=1，其他xi=0。即选修4门课程，课程标号分别是3，4，23，25；本学期的最低学费为2962元。
一般来说，得到一个整数规划问题的最优解是很困难的，所以该整数规划模型的解也不唯一。我们通过对变量的约束进行隐式枚举的方法给出其他一些选课方案，见表2。
由于必修，限选和任选课程学分的费用不一样。所以由表2可以得出，要使费用最低，则在满足模型的情况下，尽量选择费用最低的任选课程，并所选的学分不超过总选修的9个学分。在本文中所给出的所有最优的选课方案中，学费最低的为选修4个学分的限选，5个学分的任选，其总的最低学费为2962元。
3．结束语。本文利用0－1整数规划原理建立模型解决了高校学生课程优选问题。实际上，整数规划原理已广泛应用于我们的生产生活当中，它不仅在工业和工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。
参考文献
1 焦永兰主编.《管理运筹学》[M].北京:中国铁道出版社, 2007
2 郭耀煌主编.《运筹学原理与方法》[M].成都:西南交通大学出版社,1994
3 刘寿春.整数规划模型研究.皖西学院学报[J].2004.4(2)