运筹学实验报告

某大学计算机实验室聘用了勤工俭学的4名大学生（代号为

1,2,3,4）和两名研究生（代号为4,5）值班，已知每人从周一到周五每天可安排的值班时间及每人每小时值班的报酬如下表所示：

该实验室每天开放14个小时，开放时间内须有且仅有一名学生值班，规定大学生每周值班不少于8小时，研究生每周值班吧不少于7小时，每名学生每周值班不超过3次，每次值班不少于2个小时，每天安排值班的学生不超过3人，且其中必须至少有一名研究生。试用本书提供的软件为该实验室安排一张人员值班表，使总支付报酬为最少。 解:

设x[ij]为学生i在周j的值班时间y[ij]={[1,安排学生i在周j值班],[0,否则]}用a[ij]代表学生i在周j最多可安排时间，c[i]为学生i每小时报酬，则有：

min z=c1x11+c1x12+c1x13+c1x14+c1x15+c2x21+c2x22+c2x23+ c2x24+c2x25+c3x31+c3x32+c3x33+c3x34+c3x35+c4x41+c4x42+ c4x43+c4x44+c4x45+c5x51+c5x52+c5x53+c5x54+c5x55 s.t. y[ij]<=x[ij]<=a[if]y[ij],i=1,2,3,4,5,6,j=1,2,3,4,5 (不超过可安排时间)

x11+x12+x13+x14+x15>=8 x21+x22+x23+x24+x25>=8 x31+x32+x33+x34+x35>=8

x41+x42+43+x44+x45>=8(大学生每周值班不少于8小时) x51+x52+x53+x54+x55>=7

x61+x62+x63+x64+x65>=7(研究生每周值班不少于7小时)

x11+x12+x13+x14+x15=14

x21+x22+x23+x24+x25=14 x31+x32+x33+x34+x35=14 x41+x42+x43+x44+x45=14 x51+x52+x53+x54+x55=14

x61+x62+x63+x64+x65=14(实验室每天开放时间为14小

时)

y11+y12+y13+y14+y15<=3 y21+y22+y23+y24+y25<=3 y31+y32+y33+y34+y35<=3

y41+y42+y43+y44+y45<=3 y51+y52+y53+y54+y55<=3

y61+y62+y63+y64+y65<=3(每个学生每周值班不超过3

次)

y11+y21+y31+y41+y51+y61<=3 y12+y22+y32+y42+y52+y62<=3 y13+y23+y33+y43+y53+y63<=3 y14+y24+y34+y44+y54+y64<=3

y51+y52+y53+y54+y55+y65<=3(每天值班不超过3人) y51+y61>=1 y52+y62>=1 y53+y63>=1 y54+y64>=1

y55+y65>=1(每天有一个研究生值班) x[ij]>=0 ,y[ij]=0或1,i=1,2,3,4,5,6;j=1,2,3,,4,5

分析：值班方案如下:

按照以上方案安排值班，总支付的报酬最少，最少为：709元。