Vaccination against the human papillomavirus (HPV) is a recent development in the UK. This paper uses an optimal control model to explore how best to target vaccination. We find that the vaccination of sexually active individuals has a greater impact on disease control than the vaccination of sexually non-active individuals. Extending the model to include male vaccination, we find that including males in a vaccination strategy is cost-effective. We compare the optimal control solution to that from a constant control model and show that the optimal control model is more efficient at forcing the system to a disease-controlled steady state.