Indépendamment de la question de genre, vice se lie normalement avec un trait d’union avec le nom auquel il est associé, je pense donc qu’il vaudrait mieux écrire le (ou la) vice-Premier ministre.

D’autre part, je me demandais si il ne conviendrait pas de prendre en compte le genre du Premier ministre : si c’est un homme et que son « second » (sa seconde ?) est une femme, celle-ci serait alors la vice-Premier ministre. Mais si c’est l’inverse, le second ne devrait-il pas être appelé le vice-Première ministre… ? 🙂