补考日程安排问题.doc

1数学建模选修课程论文数学建模选修课程论文论文题目：论文题目：A题：补考日程安排问题题：补考日程安排问题2A题：补考日程安排问题目录摘要·························21、问题重述·····················32、符号说明·····················33、模型假设·····················34、问题分析·····················45、模型的建立与求解·················46、模型的检验····················107、模型的评价····················108、模型的推广····················109、参考文献·····················1010、附录·······················113题目： A题：补考日程安排问题摘要本问题是一个补考日程安排的最优化问题首先在考虑这 11 种课程安排是否发生冲突的前提下，以尽量将考试安排在上午为目标函数，定义相关的决策变量最后运用 Lingo 工具进行操作，得到了课程安排的最优化解。

问题的答案：最多可以有 8 门考试安排在上午，安排的时间表大致如下：其中上午四个时间段的考试安排时间和日期可以相互调换，但是每个时间段中的考试课程组合不能够改变，下午四个考试时间段的考试安排时间和日期可以相互调换关键词：冲突与不冲突 ，上午考试 ，时间安排 ，最优解 时间 日期2 月 16 日2 月 17 日8:00–9:35K1K3 K89:55–11:30K2 K6K1 K4 K913:30–15:05K1015:25–17:00K7K541、问题重述北京工业大学开学前补考课程共有11门，现在要进行补考时间的安排，补考课程的冲突情况见下表 表表A：：11门课程补考有冲突的情况（门课程补考有冲突的情况（××为有冲突，－为无冲突）为有冲突，－为无冲突）课程K1K2K3K4K5K6K7K8K9K10K11K1－×－－×－×－－××K2×－－－×－×－－××K3－－－××××－×××K4－－×－×××－－××K5××××－××××××K6－－×××－×－×××K7××××××－××××K8－－－－×－×－－××K9－－×－×××－－××K10×××××××××－×K11××××××××××－补考一共在连续的两天中有四个时间段，其中上午有两个时间段，下午有两个时间段，由于有的学生有多门补考，故要在考虑考试课程安排是否有冲突的前提下，尽量将考试安排在两天的上午，避免冲突，尤其是重要考试的科目。

2、符号说明k(i)：表示课程序号，i 取 1,2,3,4,5,6,7,8,9,10,11time：表示时间段，共八个时间段，其中 1,2,3,4 代表上午的四个时间段，5,6,7,8 代表下午的四个时间段a(k,k)：代表两种课程是否发生冲突，0 表示不冲突，1 表示冲突c(k,time)：表示该课程是否安排在此时间段，1 表示能安排，0 表示不能安排53、模型假设1、每位学生在每个时段都只需参加一门考试可理解为该时间段的任何考试之间不发生冲突2、所给的考试课程是否发生冲突的数据基本上有效3、每一门考试必须要安排，不能漏缺4、目标函数就是所求的考试时间安排的最优方案4、问题分析本问题是一个考试时间安排的最优化问题数学模型，需要优化的就是在上午考试的门数尽量多主要是根据 11 门考试的时间安排是否发生冲突来决定如何安排考试的问题, 在考试的课程不发生冲突下，而且每一门考试必须安排也只能安排在一个时间段下，我们追求的是尽量将考试安排在上午，故要首先应定义相关的决策变量，列出相应的目标函数,加上所有的约束条件,利用相关的工具 lingo 软件进行操作求解,最后对结果进行分析问题的关键：1、找出所有的决策变量，并给以合适的定义。

2、列出目标函数，并用程序求解5、模型的建立与求解根据模型假设，以能够尽量多的把考试课程安排在上午为目标函数，列出模型如下：max=@sum(k(i):c(i,1))+@sum(k(i):c(i,2))+@sum(k(i):c(i,3))+@sum(k(i):c(i,4));！上午的四个时间段用 1,2,3,4 表示，具体表示哪天哪个时间段不区分，下午的四个时间段用 5,6,7,8 表示约束条件则为：每门考试必须要安排在一个时间段，且要满足考试课程相互间不冲突，即满足表 A 的所有情况，程序语句如下 @for(arrange:@bin(c));！C 的值只能取 0 或 1，即不能安排和能安排；@for(k(i):@sum(time(j):c(i,j))=1);！满足所有考试课程必须要安排；@for(time(j):@sum(k(u):@sum(k(v):c(u,j)*c(v,j)*a(u,v)))=0);！满足考试课程间不冲突；6用lingo软件求解，所求的结果如下：Global optimal solution found.Objective value: 8.000000Objective bound: 8.000000Infeasibilities: 0.000000Extended solver steps: 1Total solver iterations: 12Variable Value Reduced Cost A( 1, 1) 0.000000 0.000000A( 1, 2) 1.000000 0.000000A( 1, 3) 0.000000 0.000000A( 1, 4) 0.000000 0.000000A( 1, 5) 1.000000 0.000000A( 1, 6) 0.000000 0.000000A( 1, 7) 1.000000 0.000000A( 1, 8) 0.000000 0.000000A( 1, 9) 0.000000 0.000000A( 1, 10) 1.000000 0.000000A( 1, 11) 1.000000 0.000000A( 2, 1) 1.000000 0.000000A( 2, 2) 0.000000 0.000000A( 2, 3) 0.000000 0.000000A( 2, 4) 0.000000 0.000000A( 2, 5) 1.000000 0.000000A( 2, 6) 0.000000 0.000000A( 2, 7) 1.000000 0.000000A( 2, 8) 0.000000 0.000000A( 2, 9) 0.000000 0.000000A( 2, 10) 1.000000 0.000000A( 2, 11) 1.000000 0.000000A( 3, 1) 0.000000 0.000000A( 3, 2) 0.000000 0.000000A( 3, 3) 0.000000 0.000000A( 3, 4) 1.000000 0.000000A( 3, 5) 1.000000 0.000000A( 3, 6) 1.000000 0.000000A( 3, 7) 1.000000 0.000000A( 3, 8) 0.000000 0.000000A( 3, 9) 1.000000 0.000000A( 3, 10) 1.000000 0.000000A( 3, 11) 1.000000 0.000000A( 4, 1) 0.000000 0.000000A( 4, 2) 0.000000 0.000000A( 4, 3) 1.000000 0.0000007A( 4, 4) 0.000000 0.000000A( 4, 5) 1.000000 0.000000A( 4, 6) 1.000000 0.000000A( 4, 7) 1.000000 0.000000A( 4, 8) 0.000000 0.000000A( 4, 9) 0.000000 0.000000A( 4, 10) 1.000000 0.000000A( 4, 11) 1.000000 0.000000A( 5, 1) 1.000000 0.000000A( 5, 2) 1.000000 0.000000A( 5, 3) 1.000000 0.000000A( 5, 4) 1.000000 0.000000A( 5, 5) 0.000000 0.000000A( 5, 6) 1.000000 0.000000A( 5, 7) 1.000000 0.000000A( 5, 8) 1.000000 0.000000A( 5, 9) 1.000000 0.000000A( 5, 10) 1.000000 0.000000A( 5, 11) 1.000000 0.000000A( 6, 1) 0.000000 0.000000A( 6, 2) 0.000000 0.000000A( 6, 3) 1.000000 0.。