martes, 4 de agosto de 2009

Un problema para resolver:

Andaba yo por la costa del mar Adriático ( en la foto practicando " la barandilla" en Opatija, te tiras al mar accediendo directamente por una baranda de hormigón),cuando mi amiga Mº Jesús, a petición de un amigo, me pide que resuelva un problema, al que se considere amigo-lector de este blog, le pido que intente resolverlo y nos de alguna pista:
"El mantenimiento y protección de una reserva marina durante un día requiere de un servicio de personal muy concreto y distribuido en dos modalidades:
· Servicio marítimo : Tripulación compuesta por tres miembros (patrón, maquinista, marinero), que se encuentran embarcados durante una jornada completa de 24 horas · Servicio terrestre: Tripulación compuesta por el mismo número de personas y cualificaciones, que se encuentran patrullando por tierra durante en un turno de 8 horas
Esto implica que cada día están operativas dos tripulaciones (una terrestre de 8 horas y otra marítima de 24 horas).
El personal de la reserva esta compuesto por 4 tripulaciones, 12 personas (Tripulación=T=Patrón+maquinista+marinero), donde a=patrón, b=maquinista, c=marinero:
· T1 (a1,b1,c1)
· T2 (a2,b2,c2)
· T3 (a3,b3,c3)
· T4 (a4,b4,c4)
Todas las tripulaciones pueden/deben hacer el servicio de 24 horas y el de 8 horas, y en la medida de lo posible, las tripulaciones deben variar para que todos trabajen con todos sin que varíe la composición de una tripulación de patrón+maquinista+marinero.
Teniendo en cuenta que la tripulación que haga el turno de 24 horas tiene que librar al menos 3 días, ¿Cómo deben de distribuirse los turnos? ¿eh? ¿eh? ¿eh? ¿eh?
Yo creo que es imposible que puedan librar 3 días, como mucho 2 y me es muy complicado resolver lo de las rotaciones."... ...

10 comentarios:

  1. Ya hemos tirado la toalla jajajaajajja
    Pero muchas gracias por "el detalle"...

    Parece que con una tripulación más si podrían hacerse las rotaciones, aunque no me ha dicho cómo...

    Hala, hala... seguid pensando...

    Un beso manuela, vaya viaje que te has pegado!

    María Jesús

    ResponderEliminar
  2. Este comentario ha sido eliminado por el autor.

    ResponderEliminar
  3. Antes que nada, felicidades por este magnífico blog.

    En cuanto al problema no parece que se pueda resolver con cuatro tripulaciones y tres dias de descanso. Intentaré justificarlo:

    Imaginemos unas condiciones mucho menos restrictivas, a saber, que solo fuera necesaria la patrulla de 24 horas y no fuera necesaria la terrestre de 8 horas.

    Ahora centrémonos solo en los marineros que trabajarían en esta patrulla marítima de 24 horas. Hay cuatro disponibles. Puesto que descansan tres dias, esto los fuerza a trabajar siempre en el mismo orden, es decir si comienzan con una secuencia, pej: c3,c4,c2,c1 se verán obligados a repetirla:

    c3, c4, c2, c1, c3, c4, c2, c1, c3, c4, c2, c1 ....

    Lo mismo ocurre con patrones y maquinistas (solo pueden trabajar en el mismo orden) . Esto implica que: tras los primeros cuatro dias, los equipos tendrían que repetirse forzosamente.

    Por tanto solo con la patrulla marítima, resulta que todos los equipos están ya ocupados en una tarea y sin posibilidad de rotación. Si añadimos la patrulla de tierra la resolución del problema sería imposible. Veamoslo intuitivamente mediante un ejemplo:

    Sean los marineros c1, c2, c3, c4 ; para los dos primeros dias cojamos cuatro de ellos, pej:

    Dia 1 :

    c1 (marinero 24 hras)
    c2 (marinero 8 hras)

    Dia 2:

    c3 (marinero 24 hras)
    c4 (marinero 8 hras)

    Para el dia 3 tenemos que eliminar a los marineros c1 y c3 (que están descansando) por lo que nos quedan dos posibilidades:

    Posibilidad 1:

    c2 (marinero 24 hras)
    c4 (marinero 8 hras)

    Posibilidad 2:

    c4 (marinero 24 hras)
    c2 (marinero 8 hras)


    Para el dia 4, tenemos descansando a tres marineros ..... por tanto nos queda uno libre, ¡ y necesitamos dos ! :-)

    Para solucionar el desaguisado podemos aumentar la tripulación o reducir la jornada. En cualquiera de los dos casos creo que el problema se puede atacar mejor de la forma expuesta es decir cogiendo por separado a patrones, maquinistas y marineros, en pares ordenados y aplicándoles las restricciones de los dias de descanso. Definido así, se podría hacer un programa informático que resolviera la cuestión teniendo en cuenta estas restricciones; que es lo que se suele hacer en investigación operativa.

    Después de alguna pruebecilla en este sentido, parece que aumentando la tripulación en un equipo es posible rotar a la tripulación en distintas configuraciones cumpliendo su cometido, pero lo que no está claro es que se puedan alcanzar las (5x5x5) 125 combinaciones posibles de (patron, maquinista, marinero)

    Si lo que hacemos es poner un dia menos de descanso (lo cual no deja de ser cruel), tampoco está claro que se alcancen las (4x4x4) 64 combinaciones posibles de (patron, maquinista, marinero) ...pero al menos habría cierta rotación y el cometido se cumpliría al igual que en el caso de la ampliación de tripulación.

    Pero habría que verlo con un poco más de detenimiento

    ResponderEliminar
  4. Agustin, gracias por el interés y por tu aportación.

    Yo sólo he trabajado con las 4 tripulaciones y restringiendo a dos días de descanso tras la jornada marítima de 24 horas, a los que le seguiría la terrestre de 8 horas.

    Una de las secuencias más óptima que he visto sería: M-D-D-T-M para todas las tripulaciones.

    No veo que puedan rotar los componentes de las tripulaciones, siendo un total de 64, ya que las secuencias anteriores se van alternando en cada tripulación para cubrir las jornadas de trabajo; y cuando una libra, otra realiza otro turno diferente. Si cambiamos a los miembros de la tripulación de secuencia no respetamos los descansos.

    Por ejemplo:

    T1 T2 T3 T4
    Día
    1º M T ---- ---
    2º ---- ---- M T
    3º ---- M ---- T
    4º T ---- ---- M
    5º M ---- T ----
    6º ---- T M ----
    7º ---- M ---- T
    8º T ----- ---- M
    9º M ----- T ----
    10º ---- T M ----
    11 --- M --- T
    12 T ----- ---- M
    13 M ---- T ---
    14 --- T M ----


    Las 64 posibles tripulaciones serían:

    T1 (a1 , b1 , c1 ) T2 (a2 , b2 , c2 ) T3 (a3 , b3 , c3 ) T4 (a4 , b4 , c4 )


    T1 (a1 , b1 , c2 ) T2 (a2 , b2 , c1 ) T3 (a3 , b3 , c4 ) T4 (a4 , b4 , c3 )


    T1 (a1 , b1 , c3 ) T2 (a2 , b2 , c4 ) T3 (a3 , b3 , c1 ) T4 (a4 , b4 , c2 )


    T1 (a1 , b1 , c4 ) T2 (a2 , b2 , c3 ) T3 (a3 , b3 , c2 ) T4 (a4 , b4 , c1 )


    T1 (a1 , b2 , c1 ) T2 (a2 , b1 , c2 ) T3 (a3 , b4 , c3 ) T4 (a4 , b3 , c4 )


    T1 (a1 , b2 , c2 ) T2 (a2 , b1 , c1 ) T3 (a3 , b4 , c4 ) T4 (a4 , b3 , c3 )


    T1 (a1 , b2 , c3 ) T2 (a2 , b1 , c4 ) T3 (a3 , b4 , c1 ) T4 (a4 , b3 , c2 )


    T1 (a1 , b2 , c4 ) T2 (a2 , b1 , c3 ) T3 (a3 , b4 , c2 ) T4 (a4 , b3 , c1 )


    T1 (a1 , b3 , c1 ) T2 (a2 , b4 , c2 ) T3 (a3 , b2 , c3 ) T4 (a4 , b1 , c4 )


    T1 (a1 , b3 , c2 ) T2 (a2 , b4 , c1 ) T3 (a3 , b2 , c4 ) T4 (a4 , b1 , c3 )


    T1 (a1 , b3 , c3 ) T2 (a2 , b4 , c4 ) T3 (a3 , b2 , c1 ) T4 (a4 , b1 , c2 )


    T1 (a1 , b3 , c4 ) T2 (a2 , b4 , c3 ) T3 (a3 , b2 , c2 ) T4 (a4 , b1 , c1 )


    T1 (a1 , b4 , c1 ) T2 (a2 , b3 , c2 ) T3 (a3 , b1 , c3 ) T4 (a4 , b2 , c4 )


    T1 (a1 , b4 , c2 ) T2 (a2 , b3 , c1 ) T3 (a3 , b1 , c4 ) T4 (a4 , b2 , c3 )


    T1 (a1 , b4 , c3 ) T2 (a2 , b3 , c4 ) T3 (a3 , b1 , c1 ) T4 (a4 , b2 , c2 )


    T1 (a1 , b4 , c4 ) T2 (a2 , b3 , c3 ) T3 (a3 , b1 , c2 ) T4 (a4 , b2 , c1 )


    El problema está en qué momento cambiar las tripulaciones para que se respeten los descansos.

    De todas formas el objetivo es conseguir el mejor resultado posible aunque no coincida con el planteamiento inicial. Así que ... :)

    Un saludo

    Mª Jesús

    ResponderEliminar
  5. Como se ha descolocado la tabla, comento que la 1ª columna es de T1 , la segunda de T2...

    Mª Jesús

    ResponderEliminar
  6. Bueno, después de pensarlo un tiempo, creo que se puede implementar una solución a través de un algoritmo. La explicación parece más complicada de lo que es. Realmente es muy sencilla aunque no tengo tiempo para implementarlo y depurarlo.
    Asegura que se cogerán todas las combinaciones posibles en un número de dias más o menos óptimo. Un criterio para seleccionar cada combinación es la suma de las vacaciones que ha cogido cada uno. Intentando que nadie se alargue en las vacaciones. Todavía es perfeccionable esto último pero creo que es suficiente. El programa una vez hecho no tardaría más de diez segundos en darnos la solución para, por ejemplo, un año.


    Explicación del Algoritmo:

    Llamamos C1 , C2 ... C64 a las distintas combinaciones posibles de tripulaciones.

    PARA el conjunto del problema se define el array

    Vecesrepetidas (n)
    Con n entre 1 y 64 . Tendrá el número de veces que se ha cogido la combinación C(n) a lo largo de los dias.

    PARA CADA DIA asignamos las siguientes matrices o arrays:

    Posible (n)
    Con n entre 1 y 64 ; Que tendrá el valor 1 si esa combinación es posible insertarla en ese dia; es decir si patrón, marinero y maquinista no trabajaron en turno de 24 horas en los dos dias anteriores y 0 en caso contrario.


    Sumavacaciones (n)
    Con n entre 1 y 64. Que tendrá la suma de los dias que llevan de vacaciones patrón, marinero y maquinista en la combinación para ese esa combinación C(n)
    Por ejemplo si el patrón lleva 1 dias de vacaciones, el marinero 1 y el maquinista 2 ; el valor del array será 4



    Ahora tenemos que rellenar una tabla como la siguiente:

    Dia 1 : D1 N1
    Dia 2: D2 N2
    Dia 3: D3 N3
    ...
    Dia F DF NF


    Donde Dx es una de las ternas C1.... C64 para el turno de 24 h y
    Nx es una de las ternas C1 .... C64 para el turno de 8 h


    El algoritmo sería así:

    A) Para el los dos primeros dias cogemos 4 combinaciones distintas y compatibles del conjunto C1...C64
    B) Para los dias sucesivos cogemos:
    De todas la s que cumplan Posible(n) =1
    la que tenga el MENOR valor en Vecesrepetidas (n)
    SI hay varias con el mismo valor cogemos el que tenga el MAYOR valor en Sumavacaciones (n)
    C) Si no existe ninguno que cumpla Posible(n) = 1
    ENTONCES
    De todas se coge
    la que tenga el MENOR valor en Vecesrepetidas (n)
    SI hay varias con el mismo valor cogemos el que tenga el MAYOR valor en Sumavacaciones (n)

    El pseudocódigo en el siguiente comentario... (que si no excede de 4096 caracteres y no me deja)

    ResponderEliminar
  7. PSEUDOCÖDIGO

    Un pseudocódigo (no demasiado formal pero explicativo), quedaría algo asi:

    Asignar cvalores a D1, N1, D2 y N2 (los dos primeros dias)

    Inicializa array Vecesrepetidas () a cero

    PARA n = 3 a F
    PARA k= 1 a 64
    Define array posible (k)
    Define array Sumavacaciones (k)
    FIN PARA

    sumavacaciones = -100
    Vecesrepetidas = 10000
    encontrado= 0

    PARA k=1 a 64
    Si posible (k) =1 ENTONCES
    SI (Sumavacaciones (k) > sumavacaciones) Y (Vecesrepetidas (k) < Vecesrepetidas) ENTONCES
    maximosuma = sumavacaciones (k)
    subindice = k
    encontrado =1
    FIN SI
    FIN PARA

    SI encontrado =1 ENTONCES
    resultado = C(subindice) ;
    vecesrepetidas(subindice) = vecesrepetidas (subindice) + 1
    EN CASO CONTRARIO
    sumavacaciones = -100
    Vecesrepetidas = 10000

    PARA k=1 a 64

    SI (Sumavacaciones (k) > sumavacaciones) Y (Vecesrepetidas (k) < Vecesrepetidas) ENTONCES
    maximosuma = sumavacaciones (k)
    subindice = k
    encontrado =1
    FIN SI

    FIN PARA
    resultado = C(subindice) ;
    vecesrepetidas(subindice) = vecesrepetidas (subindice) + 1

    FIN SI

    FIN PARA


    El resultado debe almacenarse también en un array.


    Si alguien se anima a implementarlo, es solo cuestión de tiempo... :-)


    Saludos.

    ResponderEliminar
  8. Gracias Agustín, ese alguien no seré yo,-solo se matemáticas y pocas -; paso el testigo al que pidió ayuda para resolver el problema. Gracias.

    ResponderEliminar
  9. Eso, Mª Jesús, ¡salga a la pizarra! :-)

    ResponderEliminar
  10. bwajajajaja...

    De informática bien poco; matemáticas y mal.
    De todas formas lo miraré detenidamente y lo pasaré a la persona que me lo pidió por si le vale.

    De nuevo muchas gracias.
    Un saludo
    Mª Jesús

    ResponderEliminar

Descubriendo a Emmy Noether de la mano de Eduardo Sáenz de Cabezón.

                Verano, es tiempo de aprender, y para ello hay que leer; empiezo un libro : "El árbol de Emmy. Emmy Noether, la mayor ...