排班问题的最优数学规划.doc

排班问题的最优数学规划
摘要
本文主要研究的是在规定条件下排班问题的最优化方案。通过对问题条件的分析，建立相应的数学模型，得到各种情况下最小的机房总支付报酬。
针对问题一：我们用数学规划方法中的目标规划方法，确定总支付报酬的目标函数以及约束条件，建立目标规划模型。在模型中我们采用等效替代的方法，假设无人值班情况为学生7，学生7可在任意时刻“值班”，机房需支付学生7报酬50元/小时。借助于lingo软件对模型进行求解，最终得到多组值班表，且每组值班表所对应的最小机房总支付报酬均为827元。
针对问题二：我们延续问题一的目标规划模型，在模型中加入题设所给定的两个约束条件，在此基础上建立模型。借助lingo软件对模型进行求解，最终得到总支付报酬最小情况下唯一的一组值班表，且其所对应的最小机房总支付报酬为1071元。
针对问题三：通过Excel随机函数来产生6名学生的课表，针对此课表修改前面已建立模型。通过lingo软件对模型进行求解，最终可得到在该课表下最优的值班表，且其所对应的最小机房总支付报酬为809元。

关键字：目标规划模型 等效替代 lingo软件 Excel随机函数

目录

第一部分 问题重述……………………………………………………………(1)
第二部分 问题分析……………………………………………………………(1)
第三部分 模型的假设…………………………………………………………(2)
第四部分 定义与符号说明……………………………………………………(2)
第五部分 模型的建立与求解…………………………………………………(3)
1.问题1的模型………………………………………………………………(3)
模型Ⅰ ……………………………………………………………………(4)
2．问题2的模型………………………………………………………………(4)
模型Ⅰ ……………………………………………………………………(4)
3.问题3的模型………………………………………………………………(5)
模型Ⅰ……………………………………………………………………(5)
第六部分 模型的评价…………………………………………………………(6)
第七部分 参考文献…………………………………………………………(6)
第八部分 附录…………………………………………………………………………(7)

一、 问题重述
某实验教学中心机房准备聘用4名本科学生（代号1、2、3、4）和2名研究生（代号5、6）值班进行答疑。已知每人从周一到周五最多可安排的值班时间及每小时值班报酬。由于该机房开放时间为上午8:00到晚22:00，开放时间内须有且仅需一名学生值班，又规定每名本科生每周值班不得少于8小时，研究生每周值班不少于7小时。若某时段无人值班则每小时损失50元。要求 
1、建立该机房总支付报酬最小的数学模型并求解。
2、在上述基础上补充下面两个要求，一是每名学生每周值班不超过2次，二是每天安排的学生不超过3人，重新建立数学模型并求解。 
3、考虑到实际情况中，学生需要上课，学生只能在空闲时间值班（可以不考虑上表中的每天值班时间上限）。在此条件下建立数学模型，求解出支付报酬最小的值班方案。（学生课程表可以调查周围同学课程表或者按照一天3~6节课，一周两次晚自习的条件随机生成）。

二、 问题分析
本题属于求解最优化问题，需要用数学规划方法对问题进行求解；
针对问题一:本题属于在规定条件下的规划问题，在给定的条件下建立最小支付报酬的目标函数，同时确定约束条件，确立合适的数学模型。借助计算机软件lingo编程对模型进行求解，得到机房的最小支付报酬。模式图如下：

针对问题二：问题二在问题一的基础上新增了两个约束条件，保持问题一中的模型不变，再加上两个约束条件后得到新的模型，随后对模型进行求解。
针对问题三：问题三中，由于本科生和研究生的课表未确定，首先应用软件随机产生六名学生的课表。随后这个问题就回归到问题一的模型当中，然后再对模型进行求解，得到机房所需最低的支付报酬。

三、 模型假设
假设一：假设题目中所给的数据真实可靠；
假设二：假设本科生和研究生值班的效果相同；
假设三：无人值班时所支付的报酬相当于代号为7的学生值班所得报酬。则7号学生在岗位时无人值班，且机房需要支付报酬50元/小时；
假设四：本科生的课程数目比研究生多；

四、 定义与符号说明
为了便于描述问题，我们用一些符号来代替问题中涉及的一些基本变量，如下图所示。期同期的一些变量将陆续在文中说明。
符号
意义

学生编号

星期数

总支付报酬

编号为的学生星期值班时间

编号为的学生星期值班报酬

媒介函数

五、 模型的建立与求解
第一部分：准备工作
（1） 数据的处理：
由于考虑到某时刻无人值班，假设无人值班这种情况为学生编号为7。则学生7在周一到周五任何时段均有可能“值班”，且机房需支付50元/小时报酬。经过处理，可得到以下数据：
学生代号
报酬（元/小时）
每天最多安排的值班时间/小时
周一
周二
周三
周四
周五
1
10
6
0
6
0
7
2
10
0
6
0
6
0
3
12
4
8
3
0
5
4
12
5
5
6
0
4
5
15
3
0
4
8
0
6
16
0
6
0
6
3
7
50
14
14
14
14
14

第二部分:问题一的模型
（1） 模型Ⅰ
根据题意可知，令机房总支付报酬取最小值，得到目标函数为：
(1)

(2)
(3)
(4)
(5)
注：为媒介函数，且：
=0；=0

=1；≠0

模型Ⅰ的求解：
通过lingo软件编程(源程序见附录【1】)，可以得到多组最优解，每组最优解的机房支付总报酬为827元。因为最优解在一般条件下一组已经足够，此处列出具体两种值班安排:
值班安排表1

值班安排表2

第三部分:问题二的数学模型
(1) 模型Ⅱ
问题二在问题一的模型Ⅰ基础上，补充了两个要求。保持模型Ⅰ的条件不变，在模型Ⅰ的条件下增加两个约束条件。即：
（6）
（7）

模型Ⅱ的求解：
再次通过lingo软件编程(源程序见附录【2】)，只得到一组最优解，而且最优解的机房支付总报酬为1071元。在此列出程序执行所得结果以及值班安排表，如下：

值班时间分布图

学生代号
报酬
周一
周二
周三
周四
周五
总计
1
10
6
0
0
0
7
130
2
10
0
6
0
6
0
120
3
12
0
8
0
0
5
156
4
12
5
0
6
0
0
132
5
15
3
0
4
0
0
105
6
16
0
0
0
6
2
128
7
50
0
0
4
2
0
300

1071

值班安排表3

第四部分:问题三的数学模型
(1) 应用模型Ⅰ求解：
通过Excel软件通过随机函数产生学生的课程表。在产生课程表的时，按照一天3~6节课（包括晚自习），并且考虑本科生的课程数目较多、而研究生的课程数目较少。具体的产生结果如下：

由于问题三和问题一的前提条件相同，因此将生成的课程表代入模型Ⅰ，通过lingo软件编程（源程序见附录【3】），得到在此课表下的支付报酬最小的排班情况和排班表如下，机房最少总支付报酬为809元。

六、 模型的推广与评价
模型Ⅰ的评价：
(1) 模型利用目标规划问题的基本方法，采用lingo软件对模型进行求解，最终可以具体地列出排班情况表，最终求得的结果比较精确、可靠性好。
(2) 模型Ⅰ在利用软件求解时得到的排班情况较多，不可能一一列出，而且不能将学生在当时时间段是否有课。同时采用excel软件产生本科生和研究生的课表，与实际情况相差可能比较大。
(3) 模型Ⅰ可以进行适当改进，使用多种算法，如“模拟退火算法”或者“遗传算法”来进一步解决排班问题，实现总支付报酬最低。同时也可以将计算结果育模型一的结果进行比较，进一步得到排班问题的最优解，实现支付报酬最小化。
(4) 模型的运用功能强大，可以应用到生活中的各种排班问题当中，实现支付报酬的最优化。
模型的推广：
此模型利用起来相对容易，可以容易地用各大于企业、学校等单位的排班问题，实现经费的最低化。
七、 参考文献
[1] 马超群、兰秋军、周忠宝，《运筹学》，长沙：湖南大学出版社，2008.12。第33~43页；
[2] 隋树林、杨树国、朱善良，《数学建模教程》，北京：化学工业出版社，2015.7。第93页；
[3] 赖炎连、贺国平，《最优化方法》，北京：清华大学出版社，2008.12。
[4] 张冬梅、颜丽、金鑫，数学建模排班问题

八、 附录
附录【1】
model:
title:实验教学中心机房值班问题1;
sets:
peo/1..7/:pay;
week/1..5/;
link(peo,week):t,a,b;
endsets
data:
pay=10,10,12,12,15,16,50;
a=
6 0 6 0 7
0 6 0 6 0
4 8 3 0 5
5 5 6 0 4
3 0 4 8 0
0 6 0 6 3
14 14 14 14 14;
enddata
min=@sum(link(i,j):t(i,j)*pay(i));
@for(week(j):@sum(peo(i):t(i,j))=14);
@for(link(i,j):t(i,j)>=b(i,j));
@for(link(i,j):t(i,j)<=a(i,j)*b(i,j));
@for(peo(i)|i#le#4:@sum(week(j):t(i,j))>=8);
@for(peo(i)|i#le#6:@sum(week(j):t(i,j))>=7);
@for(link:@bin(b));
end

附录【2】
model:
title:实验教学中心机房值班问题2;
sets:
peo/1..7/:pay;
week/1..5/;
link(peo,week):t,a,b;
endsets
data:
pay=10,10,12,12,15,16,50;
a=
6 0 6 0 7
0 6 0 6 0
4 8 3 0 5
5 5 6 0 4
3 0 4 8 0
0 6 0 6 3
14 14 14 14 14;
enddata
min=@sum(link(i,j):t(i,j)*pay(i));
@for(week(j):@sum(peo(i):t(i,j))=14);
@for(link(i,j):t(i,j)>=b(i,j));
@for(link(i,j):t(i,j)<=a(i,j)*b(i,j));
@for(peo(i)|i#le#4:@sum(week(j):t(i,j))>=8);
@for(peo(i)|i#le#6:@sum(week(j):t(i,j))>=7);
@for(week(j):@sum(peo(i)|i#le#6:b(i,j))<=3);
@for(peo(i):@sum(week(j)|i#le#6:b(i,j))<=2);
@for(link:@bin(b));
end

附录【3】
model:
title:实验教学中心机房值班问题3;
sets:
peo/1..7/:pay;
week/1..35/;
link(peo,week):t,a,b;
endsets
data:
pay=10,10,12,12,15,16,50;
a=
2 0 2 2 2 0 0 0 0 2 0 2 2 0 0 0 2 0 0 0 0 0 0 2 0 0 2 0 2 0 2 0 0 0 0
0 2 2 0 0 2 0 0 0 2 2 2 2 0 2 2 2 0 0 2 0 2 2 2 0 0 2 0 0 0 2 2 0 0 0
0 0 2 0 0 0 2 2 2 2 2 0 2 2 0 0 2 0 2 0 2 0 2 2 2 0 0 0 0 2 2 2 0 0 0
2 0 2 0 0 2 0 0 2 2 0 0 0 0 0 0 2 0 0 2 0 0 0 2 0 0 2 0 0 0 2 0 0 2 2
2 0 2 2 0 2 0 2 2 2 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 2 2 0 2 2 2 2 2
2 2 2 2 0 0 2 2 0 2 2 0 0 2 2 0 2 0 2 2 2 0 2 2 0 2 2 0 0 2 2 2 2 0 2
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
;
enddata
min=@sum(link(i,j):t(i,j)*pay(i));
@for(week(j):@sum(peo(i):t(i,j))=2);
@for(link(i,j):t(i,j)>=b(i,j));
@for(link(i,j):t(i,j)<=a(i,j)*b(i,j));
@for(peo(i)|i#le#4:@sum(week(j):t(i,j))>=8);
@for(peo(i)|i#le#6:@sum(week(j):t(i,j))>=7);
@for(link:@bin(b));
end
- 9 -