tag:blogger.com,1999:blog-4546566150511877344.post3288952196836648250..comments2024-02-22T00:46:16.358-08:00Comments on Viaje a Ítaca con Manoli: Un problema para resolver:Unknownnoreply@blogger.comBlogger10125tag:blogger.com,1999:blog-4546566150511877344.post-166482332257460572009-08-28T10:50:21.828-07:002009-08-28T10:50:21.828-07:00bwajajajaja...
De informática bien poco; matemáti...bwajajajaja...<br /><br />De informática bien poco; matemáticas y mal.<br />De todas formas lo miraré detenidamente y lo pasaré a la persona que me lo pidió por si le vale.<br /><br />De nuevo muchas gracias. <br />Un saludo<br />Mª JesúsAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-4546566150511877344.post-13724644803024402792009-08-28T07:45:00.381-07:002009-08-28T07:45:00.381-07:00Eso, Mª Jesús, ¡salga a la pizarra! :-)Eso, Mª Jesús, ¡salga a la pizarra! :-)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4546566150511877344.post-28692875522663891832009-08-26T09:15:43.485-07:002009-08-26T09:15:43.485-07:00Gracias Agustín, ese alguien no seré yo,-solo se ...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.Manolihttps://www.blogger.com/profile/01409439755723665019noreply@blogger.comtag:blogger.com,1999:blog-4546566150511877344.post-49253416096914415132009-08-25T15:25:14.205-07:002009-08-25T15:25:14.205-07:00PSEUDOCÖDIGO
Un pseudocódigo (no demasiado form...PSEUDOCÖDIGO <br /><br />Un pseudocódigo (no demasiado formal pero explicativo), quedaría algo asi:<br /><br />Asignar cvalores a D1, N1, D2 y N2 (los dos primeros dias)<br /><br />Inicializa array Vecesrepetidas () a cero<br /><br />PARA n = 3 a F<br /> PARA k= 1 a 64<br /> Define array posible (k)<br /> Define array Sumavacaciones (k)<br /> FIN PARA<br /><br /> sumavacaciones = -100<br /> Vecesrepetidas = 10000<br /> encontrado= 0 <br /><br /> PARA k=1 a 64<br /> Si posible (k) =1 ENTONCES<br /> SI (Sumavacaciones (k) > sumavacaciones) Y (Vecesrepetidas (k) < Vecesrepetidas) ENTONCES<br /> maximosuma = sumavacaciones (k)<br /> subindice = k<br /> encontrado =1<br /> FIN SI<br /> FIN PARA<br /><br /> SI encontrado =1 ENTONCES <br /> resultado = C(subindice) ;<br /> vecesrepetidas(subindice) = vecesrepetidas (subindice) + 1<br /> EN CASO CONTRARIO<br /> sumavacaciones = -100<br /> Vecesrepetidas = 10000 <br /> <br /> PARA k=1 a 64<br /> <br /> SI (Sumavacaciones (k) > sumavacaciones) Y (Vecesrepetidas (k) < Vecesrepetidas) ENTONCES<br /> maximosuma = sumavacaciones (k)<br /> subindice = k<br /> encontrado =1<br /> FIN SI<br /><br /> FIN PARA<br /> resultado = C(subindice) ;<br /> vecesrepetidas(subindice) = vecesrepetidas (subindice) + 1<br /><br /> FIN SI<br /><br />FIN PARA<br /> <br /><br />El resultado debe almacenarse también en un array. <br /><br /><br />Si alguien se anima a implementarlo, es solo cuestión de tiempo... :-)<br /><br /><br />Saludos.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4546566150511877344.post-29121986360617467072009-08-25T15:22:30.523-07:002009-08-25T15:22:30.523-07:00Bueno, después de pensarlo un tiempo, creo que se ...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. <br />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. <br /><br /><br />Explicación del Algoritmo:<br /><br />Llamamos C1 , C2 ... C64 a las distintas combinaciones posibles de tripulaciones.<br /><br />PARA el conjunto del problema se define el array<br /><br />Vecesrepetidas (n)<br />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. <br /><br />PARA CADA DIA asignamos las siguientes matrices o arrays:<br /><br />Posible (n)<br />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.<br /><br /><br />Sumavacaciones (n)<br />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)<br />Por ejemplo si el patrón lleva 1 dias de vacaciones, el marinero 1 y el maquinista 2 ; el valor del array será 4 <br /><br /><br /><br /> Ahora tenemos que rellenar una tabla como la siguiente:<br /><br />Dia 1 : D1 N1<br />Dia 2: D2 N2<br />Dia 3: D3 N3<br />...<br />Dia F DF NF<br /><br /><br />Donde Dx es una de las ternas C1.... C64 para el turno de 24 h y<br /> Nx es una de las ternas C1 .... C64 para el turno de 8 h<br /><br /><br />El algoritmo sería así:<br /><br />A) Para el los dos primeros dias cogemos 4 combinaciones distintas y compatibles del conjunto C1...C64<br />B) Para los dias sucesivos cogemos:<br /> De todas la s que cumplan Posible(n) =1<br /> la que tenga el MENOR valor en Vecesrepetidas (n)<br /> SI hay varias con el mismo valor cogemos el que tenga el MAYOR valor en Sumavacaciones (n)<br />C) Si no existe ninguno que cumpla Posible(n) = 1<br /> ENTONCES<br /> De todas se coge<br /> la que tenga el MENOR valor en Vecesrepetidas (n)<br /> SI hay varias con el mismo valor cogemos el que tenga el MAYOR valor en Sumavacaciones (n)<br /><br />El pseudocódigo en el siguiente comentario... (que si no excede de 4096 caracteres y no me deja)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4546566150511877344.post-6549648854765505432009-08-18T04:03:13.624-07:002009-08-18T04:03:13.624-07:00Como se ha descolocado la tabla, comento que la 1ª...Como se ha descolocado la tabla, comento que la 1ª columna es de T1 , la segunda de T2... <br /><br />Mª JesúsAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-4546566150511877344.post-69234798363092962212009-08-18T03:57:36.543-07:002009-08-18T03:57:36.543-07:00Agustin, gracias por el interés y por tu aportació...Agustin, gracias por el interés y por tu aportación. <br /><br />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.<br /><br />Una de las secuencias más óptima que he visto sería: M-D-D-T-M para todas las tripulaciones.<br /><br />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.<br /><br />Por ejemplo: <br /><br /> T1 T2 T3 T4<br />Día<br />1º M T ---- ---<br />2º ---- ---- M T<br />3º ---- M ---- T<br />4º T ---- ---- M<br />5º M ---- T ----<br />6º ---- T M ----<br />7º ---- M ---- T<br />8º T ----- ---- M<br />9º M ----- T ----<br />10º ---- T M ----<br />11 --- M --- T<br />12 T ----- ---- M<br />13 M ---- T ---<br />14 --- T M ----<br /><br /> <br />Las 64 posibles tripulaciones serían:<br /><br />T1 (a1 , b1 , c1 ) T2 (a2 , b2 , c2 ) T3 (a3 , b3 , c3 ) T4 (a4 , b4 , c4 )<br /><br /><br />T1 (a1 , b1 , c2 ) T2 (a2 , b2 , c1 ) T3 (a3 , b3 , c4 ) T4 (a4 , b4 , c3 )<br /><br /><br />T1 (a1 , b1 , c3 ) T2 (a2 , b2 , c4 ) T3 (a3 , b3 , c1 ) T4 (a4 , b4 , c2 )<br /><br /><br />T1 (a1 , b1 , c4 ) T2 (a2 , b2 , c3 ) T3 (a3 , b3 , c2 ) T4 (a4 , b4 , c1 )<br /><br /><br />T1 (a1 , b2 , c1 ) T2 (a2 , b1 , c2 ) T3 (a3 , b4 , c3 ) T4 (a4 , b3 , c4 )<br /><br /><br />T1 (a1 , b2 , c2 ) T2 (a2 , b1 , c1 ) T3 (a3 , b4 , c4 ) T4 (a4 , b3 , c3 )<br /><br /><br />T1 (a1 , b2 , c3 ) T2 (a2 , b1 , c4 ) T3 (a3 , b4 , c1 ) T4 (a4 , b3 , c2 )<br /><br /><br />T1 (a1 , b2 , c4 ) T2 (a2 , b1 , c3 ) T3 (a3 , b4 , c2 ) T4 (a4 , b3 , c1 )<br /><br /><br />T1 (a1 , b3 , c1 ) T2 (a2 , b4 , c2 ) T3 (a3 , b2 , c3 ) T4 (a4 , b1 , c4 )<br /><br /><br />T1 (a1 , b3 , c2 ) T2 (a2 , b4 , c1 ) T3 (a3 , b2 , c4 ) T4 (a4 , b1 , c3 )<br /><br /><br />T1 (a1 , b3 , c3 ) T2 (a2 , b4 , c4 ) T3 (a3 , b2 , c1 ) T4 (a4 , b1 , c2 )<br /><br /><br />T1 (a1 , b3 , c4 ) T2 (a2 , b4 , c3 ) T3 (a3 , b2 , c2 ) T4 (a4 , b1 , c1 )<br /><br /><br />T1 (a1 , b4 , c1 ) T2 (a2 , b3 , c2 ) T3 (a3 , b1 , c3 ) T4 (a4 , b2 , c4 )<br /><br /><br />T1 (a1 , b4 , c2 ) T2 (a2 , b3 , c1 ) T3 (a3 , b1 , c4 ) T4 (a4 , b2 , c3 )<br /><br /><br />T1 (a1 , b4 , c3 ) T2 (a2 , b3 , c4 ) T3 (a3 , b1 , c1 ) T4 (a4 , b2 , c2 )<br /><br /><br />T1 (a1 , b4 , c4 ) T2 (a2 , b3 , c3 ) T3 (a3 , b1 , c2 ) T4 (a4 , b2 , c1 )<br /><br /> <br />El problema está en qué momento cambiar las tripulaciones para que se respeten los descansos.<br /><br />De todas formas el objetivo es conseguir el mejor resultado posible aunque no coincida con el planteamiento inicial. Así que ... :)<br /><br />Un saludo<br /><br />Mª JesúsAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-4546566150511877344.post-52137271599114190032009-08-17T17:24:00.414-07:002009-08-17T17:24:00.414-07:00Antes que nada, felicidades por este magnífico blo...Antes que nada, felicidades por este magnífico blog.<br /><br />En cuanto al problema no parece que se pueda resolver con cuatro tripulaciones y tres dias de descanso. Intentaré justificarlo:<br /><br />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.<br /><br />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:<br /><br />c3, c4, c2, c1, c3, c4, c2, c1, c3, c4, c2, c1 ....<br /><br />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.<br /><br />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:<br /><br />Sean los marineros c1, c2, c3, c4 ; para los dos primeros dias cojamos cuatro de ellos, pej:<br /><br />Dia 1 :<br /><br />c1 (marinero 24 hras)<br />c2 (marinero 8 hras)<br /><br />Dia 2:<br /><br />c3 (marinero 24 hras)<br />c4 (marinero 8 hras)<br /><br />Para el dia 3 tenemos que eliminar a los marineros c1 y c3 (que están descansando) por lo que nos quedan dos posibilidades:<br /><br />Posibilidad 1:<br /><br />c2 (marinero 24 hras)<br />c4 (marinero 8 hras)<br /><br />Posibilidad 2:<br /><br />c4 (marinero 24 hras)<br />c2 (marinero 8 hras)<br /><br /><br />Para el dia 4, tenemos descansando a tres marineros ..... por tanto nos queda uno libre, ¡ y necesitamos dos ! :-)<br /><br />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.<br /><br />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)<br /><br />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.<br /><br />Pero habría que verlo con un poco más de detenimientoAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-4546566150511877344.post-80561151841818603602009-08-17T17:20:31.744-07:002009-08-17T17:20:31.744-07:00Este comentario ha sido eliminado por el autor.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4546566150511877344.post-74713879077187784952009-08-08T23:59:15.238-07:002009-08-08T23:59:15.238-07:00Ya hemos tirado la toalla jajajaajajja
Pero muchas...Ya hemos tirado la toalla jajajaajajja<br />Pero muchas gracias por "el detalle"...<br /><br />Parece que con una tripulación más si podrían hacerse las rotaciones, aunque no me ha dicho cómo...<br /><br />Hala, hala... seguid pensando...<br /><br />Un beso manuela, vaya viaje que te has pegado!<br /><br />María JesúsAnonymousnoreply@blogger.com