Te pongo más abajo el código con los siguientes cambios:
Clase Colocacion: añadido el método hayTrabajo
Clase Perfil: añadido el método equals
Clase PerfilEspecialista: añadido el método equals
Clase PerfilTitulado: añadido el método equals
Clase Empleo: el atributo perfil se declara como protected en vez de como public. Añadido el método getPerfil
Por cierto que hay una cosa que no entiendo ¿qué diferencia hay entre Empleo y Perfil, porque si Empleo lo único que tiene es un atributo Perfil es lo mismo no?
Clase test: añadidas algunas líneas para hacer el test del método hayTrabajo
Lo que dices: "Un método hayParesOfertaDemandaEmpleo() que devuelva en otro ArrayList los pares oferta y demanda empleo para los perfiles o null si no existe ningún par." no entiendo bien qué es lo que se quiere hacer.
public class Perfil {
    private boolean carnetDeConducir;
    public Perfil(boolean carnetDeConducir)
    {
        this.carnetDeConducir=carnetDeConducir;
    }
    public String getconducir()
    {
        String s;
        if(carnetDeConducir==true)
        {
            s="con carnet de conducir";
        }
        else
        {
            s="sin carnet de conducir";
        }
        return s;
    }
    //borrar si no funciona
    public boolean getcarnet()
    {
        return carnetDeConducir;
    }//borrar si no funciona
    public String ToString()
    {
        String salida="";
        salida="\n"+getconducir();
        return salida;
    }
    // Código que añadimos 
    public boolean equals (Object obj) {
        if (obj instanceof Perfil) {
            Perfil tmpPerfil = (Perfil) obj;
            if (this.carnetDeConducir==tmpPerfil.carnetDeConducir) {return true; } else { return false; }
        } else { return false; }
    } //Cierre del método equals
}
-------------------------------------------------------------------------------------
public class PerfilEspecialista extends Perfil{
    private String especialidad;
    public PerfilEspecialista(boolean carnetDeConducir,String especialidad)
    {
    super(carnetDeConducir);
    this.especialidad=especialidad;
    }
    public String getespecialidad()
    {
    return especialidad;
    }
    public String toString()
    {
    String salida="";
    salida=""+getconducir()+
            "\nEl presente cuenta con la especialidad: "+especialidad;
    return salida;
    }
    
    // Código que añadimos 
public boolean equals (Object obj) {
        if (obj instanceof PerfilEspecialista) {
            PerfilEspecialista tmpPerfilEspecialista = (PerfilEspecialista) obj;
            if (super.equals(tmpPerfilEspecialista) && this.especialidad.equals(tmpPerfilEspecialista.especialidad) ) {
                return true; } else { return false; }
        }  else { return false; }
    } // Cierre del método equals
    
}
-------------------------------------------------------------------------------------
ppublic class PerfilTitulado extends Perfil {
    private String titulo;
    private boolean conocimientoInformatica;
    public PerfilTitulado(boolean carnetDeConducir,String titulo,boolean conocimiento)
    {
    super(carnetDeConducir);
    this.titulo=titulo;
    conocimientoInformatica=conocimiento;
    }
    public String gettitulo()
    {
    return titulo;
    }
    public String getconocimiento()
    {
        String s;
        if(conocimientoInformatica==true)
        {
        s="El presente cuenta con conocimientos de informatica";
        }
        else
        {
        s="El presente no cuenta con conocimientos de informatica";
        }
        return s;
    }
    public String toString()
    {
    String salida="";
    salida="\n"+super.getconducir()+
            "\ntitulo: "+titulo+
            "\n"+getconocimiento();
    return salida;
    }
    
    public boolean equals (Object obj) {
        if (obj instanceof PerfilTitulado) {
            PerfilTitulado tmpPerfilTitulado = (PerfilTitulado) obj;
            if (super.equals(tmpPerfilTitulado) && this.titulo.equals(tmpPerfilTitulado.titulo) &&
            this.conocimientoInformatica == tmpPerfilTitulado.conocimientoInformatica ) {
                return true; } else { return false; }
        }  else { return false; }
    } // Cierre del método equals
    
}
---------------------------------------------------------------------------------------
import java.util.*;
public class Empleo {
    protected Perfil perfil;
    
    //ArrayList<PerfilEspecialista> perfil = new ArrayList<PerfilEspecialista>();
    //ArrayList<PerfilTitulado> perfil1 = new ArrayList<PerfilTitulado>();
    public Empleo(Perfil perfil)
    {
        this.perfil=perfil;
    }
    /*public void agregarobjeto (boolean carnetDeConducir,String especialidad){
        perfil.add(new PerfilEspecialista(carnetDeConducir,especialidad));
    }
    public void agregarobjeto (boolean carnetDeConducir,String titulo,boolean conocimiento){
        perfil1.add(new PerfilTitulado(carnetDeConducir,titulo,conocimiento));
    }*/
    public String toString()
    {
    String salida="";
    return salida;
    }
    
    public Perfil getPerfil() { return perfil;}
}
----------------------------------------------------------------------------------------
public class OfertaEmpleo extends Empleo {
    private String nombreEmpresa;
    private String puesto;
    private double sueldo;
    public OfertaEmpleo(Perfil perfil,String nombreEmpresa, String puesto,double sueldo)
    {
        super(perfil);
    this.nombreEmpresa=nombreEmpresa;
    this.puesto=puesto;
    this.sueldo=sueldo;
    }
    public String toString()
    {
    String salida="";
    salida = "\n"+perfil.toString()+
             "\nNombre de la empresa: "+nombreEmpresa+
             "\nPuesto a disposicion: "+puesto+
             "\nSueldo a cobrar: "+sueldo;
    return salida;
    }
}
------------------------------------------------------------------------------------------
public class DemandaEmpleo extends Empleo {
    private String persona;
    public DemandaEmpleo(Perfil perfil,String persona)
    {
        super(perfil);
    this.persona=persona;
    }
    public String toString()
    {
    String salida="";
    salida="\n"+perfil.toString()+
            "\nNombre del candidato: "+persona;
    return salida;
    }
}
-------------------------------------------------------------------------------------------
import java.util.*;
public class Colocacion {
    ArrayList<Empleo> empleo;
    public Colocacion()       
    {
        empleo=new ArrayList<Empleo>();
    }
    public void agregarOfertaEmpleo (Perfil perfil,String nombreEmpresa, String puesto,double sueldo)
    {       
        empleo.add(new OfertaEmpleo(perfil,nombreEmpresa,puesto,sueldo));
    }
    public void agregarDemandaEmpleo (Perfil perfil,String persona)
    {
        empleo.add(new DemandaEmpleo(perfil,persona));
    }
    
    
    //Recibe un perfil y comprueba si existe al mismo tiempo una oferta y una demanda de empleo
    //con ese perfil
    public boolean hayTrabajo (Perfil perfil) {
    //Determinamos si existe una demanda de empleo dentro del arraylist para ese perfil
    boolean existeOferta = false;
    boolean existeDemanda = false;
    
    for (Empleo e: empleo) {
        if (e instanceof OfertaEmpleo && e.getPerfil().equals(perfil)){
            existeOferta = true;
        }
        if (e instanceof DemandaEmpleo && e.getPerfil().equals(perfil)){
            existeDemanda = true;
        }
    }
    
    if (existeOferta == true & existeDemanda == true) {
        return true;
    } else { return false;}
        
        
    }
    
    
    public String toString()
    {
    String salida="";
    salida="\n"+empleo+"\n";
    return salida;
    }
}
------------------------------------------------------------------------------------------
public class test {
    public static void main (String [] args)
    {
        Colocacion emp=new Colocacion();
        
        
        PerfilEspecialista emp1= new PerfilEspecialista(true,"sumar");
        
        PerfilTitulado emp2= new PerfilTitulado(false,"analisis",true);
        
        PerfilEspecialista emp3= new PerfilEspecialista(true,"restar");
        
        emp.agregarOfertaEmpleo(emp1,"empritotal", "gerente",15000);
        emp.agregarOfertaEmpleo(emp2,"empritotal", "gerente",15000);
        
        PerfilEspecialista demp1= new PerfilEspecialista(true,"sumar");
        PerfilTitulado demp2= new PerfilTitulado(false,"analisis",true);
        
        emp.agregarDemandaEmpleo(demp1,"jose");
        emp.agregarDemandaEmpleo(demp2,"jose");
        
        System.out.println(emp);
        
        System.out.println ("¿Existe dentro de la lista de oferta-demanda una oferta y una demanda para un perfil" +
        "de especialista en sumar? :" + emp.hayTrabajo(emp1));
        
        System.out.println ("¿Existe dentro de la lista de oferta-demanda una oferta y una demanda para un perfil" +
        "de especialista en restar? :" + emp.hayTrabajo(emp3));
        
    }
}
-------------------------------------------------------------------------------------------
                                        resultado del codigo
[
con carnet de conducir
El presente cuenta con la especialidad: sumar
Nombre de la empresa: empritotal
Puesto a disposicion: gerente
Sueldo a cobrar: 15000.0, 
sin carnet de conducir
titulo: analisis
El presente cuenta con conocimientos de informatica
Nombre de la empresa: empritotal
Puesto a disposicion: gerente
Sueldo a cobrar: 15000.0, 
con carnet de conducir
El presente cuenta con la especialidad: sumar
Nombre del candidato: jose, 
sin carnet de conducir
titulo: analisis
El presente cuenta con conocimientos de informatica
Nombre del candidato: jose]
¿Existe dentro de la lista de oferta-demanda una oferta y una demanda para un perfilde especialista en sumar? :true
¿Existe dentro de la lista de oferta-demanda una oferta y una demanda para un perfilde especialista en restar? :false