Ingeniero Civil Matemático / El Problema de la Secretaria (SP) (por Secretary Problem), un problema con mucho
interés desde los años 50, se trata de encontrar una manera de procesar las entrevistas de N
candidatos a un puesto de secretaria para maximizar la probabilidad de contratar al mejor de
ellos, bajo el supuesto que las entrevistas se realizan en orden aleatorio y que las decisiones
tomadas: rechazar o aceptar, son irrevocables. Esto permite modelar directamente la versión
discreta del problema. También se puede considerar una versión contínua con una infinidad de
candidatos, suponiendo que los instantes de entrevista son tiempos aleatorios uniformes sobre
el intervalo [0,1]. Este problema y sus variantes tienen muchas aplicaciones. Esta memoria
se enfoca en el estudio de la variante llamada Problema de la Secretaria con Restricciones de
Tiempo (TCSP).
En la formulación discreta del (TCSP) se rechazan k candidatos y luego se quiere contratar
al mejor de los N−k que quedan, mientras que en su formulación contínua se rechazan todos
los candidatos entrevistados antes de un tiempo T y luego se quiere contratar al mejor de los
candidatos entrevistados después del tiempo T. En ambos casos los candidatos rechazados al
principio forman un sampleo, y se puede utilizar la información acumulada en este sampleo
inicial para mejorar la toma de decisión durante la fase de aceptación que sigue.
Después de familiarizarse con esta variante, se demuestran propiedades que cumple la
regla óptima que resuelve el (TCSP) discreto. Basándose en esto, se estudia la siguiente
estrategia para el caso contínuo. Se selecciona una sucesión creciente de constantes absolutas
{T_i} en [0,1] o tiempos barreras, independientes del tiempo T del sampleo. El proceso
de selección se realiza del siguiente modo: sólo se acepta un candidato entrevistado entre los
tiempos T_i y T_{i+1} si es mejor que todos los ya entrevistado después del tiempo T y mejor que
el i-ésimo mejor del sampleo inicial. Se encuentran fórmulas explícitas para calcular dichas
barreras. La regla óptima para resolver el (TCSP) discreto tiene una forma similar, donde
en vez de tiempos barreras, se usan candidatos barreras. Se comprueba que a medida que N
tiende a infinito, las razones entre la posición del candidato barrera i-ésimo y el número de
candidatos tienden al valor encontrado para los tiempos barreras en el caso contínuo.
Finalmente, se estudia una variante del (TCSP) en la cual el empleador sólo puede recordar
un candidato del periodo del sampleo (no necesariamente el mejor) y al mejor candidato
entrevistado luego del sampleo. Se deduce en el caso discreto la forma de la regla óptima
en la situación donde el algoritmo guarda el i-ésimo mejor candidato de la zona sampleada.
Esta regla interpretada en el caso contínuo consiste en: rechazar a todos los candidatos hasta
un tiempo T_1 > T, luego aceptar un candidato entrevistado entre los tiempos T_1 y T_0 > T_1
si es mejor que ambos miembros en memoria, y luego si no se aceptó a nadie, aceptar a un
candidato entrevistado después del tiempo T_0 solamente si es mejor que el mejor entrevistado
después del tiempo T. Se encuentran fórmulas explícitas para las barreras T_1 y T_0 como
función de T y del rango i del candidato del sampleo guardado en memoria.
| Identifer | oai:union.ndltd.org:UCHILE/oai:repositorio.uchile.cl:2250/137963 |
| Date | January 2016 |
| Creators | García, Émilien |
| Contributors | Soto San Martín, José, Facultad de Ciencias Físicas y Matemáticas, Departamento de Ingeniería Matemática, Martínez Aguilera, Servet, Matamala Vásquez, Martín |
| Publisher | Universidad de Chile |
| Source Sets | Universidad de Chile |
| Language | Spanish |
| Detected Language | Spanish |
| Type | Tesis |
| Rights | Atribución-NoComercial-SinDerivadas 3.0 Chile, http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ |
Page generated in 0.0024 seconds