Question

The NYPD employs 20 police officers. Each officer works for 5 days per week. The crime rate fluctuates with the day of week, so the number of the police officers required each day depends on which day of the week it is: Monday, 11; Tuesday, 12; Wednesday, 14; Thursday, 15; Friday, 14; Saturday, 18; Sunday;8. The Police Station wants to schedule police officers to maximize the number of the officers whose days off are consecutive.

Formulate LP and solve the problem. (manuel solution)

Answer 1

let :

the number of police officers who work continuosly for 5 days which start from monday = x1

the number of police officers who work continuosly for 5 days which start from tuesday = x2

the number of police officers who work continuosly for 5 days which start from wednesday = x3

the number of police officers who work continuosly for 5 days which start from thursday = x4

the number of police officers who work continuosly for 5 days which start from friday = x5

the number of police officers who work continuosly for 5 days which start from saturday = x6

the number of police officers who work continuosly for 5 days which start from sunday = x7

objective = maximize the number of the officers whose days off are consecutive.

ie , maximize z = x1+x2+x3+x4+x5+x6+x7

subject to constraints :

1), the number of officers who work on a specific day should not be more than the number specified in question

x1+x4+x5+x6+x7 ≤ 11

because the officers whos start on monday will definetly will be there but officers who start on tuesday will not be on monday because their 5 day will end on saturday they have to take two days off so monday will be off for them, this same for officers who start on wednesday because their 5 days end on sunday. for the rest monday will be included

x2+x5+x6+x7+x7 ≤ 12

x3+x6+x7+x1+x2 ≤ 14

x4+x7+x1+x2+x3 ≤ 15

x5+x1+x2+x3+x4 ≤ 14

x6+x2+x3+x4+x5 ≤ 18

x7+x3+x4+x5+x6 ≤ 8

2) next constraint is that the number of officer on single day should not be more than 20. because we have only 20 officers available.

x1 ≤ 20

x2 ≤ 20

x3 ≤ 20

x4 ≤ 20

x5 ≤ 20

x6 ≤ 20

x7 ≤ 20

non negetive constraint :

x1+x2+x3+x4+x5+x6+x7 ≥ 0