Le recours est donc mal fondé. Le département aurait dû s'abstenir d'entrer en matière sur le fond, mais il ne se justifie pas d'annuler sa décision puisqu'il a rejeté le recours.
Au vu du sort de la cause, les frais seront mis à la charge du recourant (art.47 al.1 LPJA).
Par ces motifs,
LE TRIBUNAL ADMINISTRATIF
1. Rejette le recours.
2. Met à la charge du recourant les frais de procédure par 500 francs et
les débours par 50 francs (montants compensés par son avance).
Neuchâtel, le 28 mars 1996