[mathtruco]

Nota: Un problema interesante. No lo miren por sobre el hombro.

Hola,


 tengo el siguiente problema que no sé como agarrar. Parece ser un simple problema de optimización lineal, pero me ha pillado. Se los explico:




 Tengo que contratar trabajadores para que hagan trabajos en los puntos verdes. Siempre deben salir desde el punto rojo (la empresa) llegar al punto verde, realizar su trabajo y volver a la empresa. Los números en azul corresponden al tiempo que demoran en desplazarse desde la empresa (el punto rojo) hasta el lugar del trabajo (el punto verde), más el tiempo que demoran en resolverlo y el tiempo que demoran en regresar al punto rojo.

Los números en azul son los tiempos que acabo de explicar, por ejemplo:
 En el nodo verde 1 deben hacerse 2 trabajos (los números en azul), uno que demora 2 horas, y otro que demora 3 horas. En el nodo verde 2 hay que realizar sólo un trabajo que dura 5 horas, etc.

Lo que quiero minimizar es el número de trabajadores que necesito para realizar todos los trabajos en un día,  sujeto a que cada trabajador no puede trabajar más de 8 horas. Además, dos trabajadores no hacen el trabajo más rápido que uno solo.



Una solución factible es que a cada trabajo le asigne un trabajador, es decir, envíe 2 trabajadores al nodo 1, 1 al nodo 2, tres al nodo 3 y 1 al nodo 4, pero no es óptimo, ya que al ojo se ve que basta enviar a 1 trabajador al nodo 1 para hacer los dos trabajos, y puede además hacer el trabajo en el nodo 4 antes de cumplir sus 8 horas de trabajo. Puedo enviar otro trabajador que haga el trabajo del nodo 2, y que haga el trabajo que dura 1 hora del nodo 3, y por último un trabajador que haga los trabajos de 6 y dos horas resp del nodo 3. Con eso tendría la solución óptima: necesito 3 trabajadores que trabajando trabajando 8 horas o menos ese día hacen todos los trabajos.



Este ejemplo se los doy para motivar el problema.


 Lo que quiero qe me ayuden es a modelarlo para W trabajos que realizan en M nodos, cada uno con tiempo de resolución T (cada T es menor o igual a 8 horas).



 Espero sus comentarios, aunque no me den la solución, cualquier aporte es bienvenido y lo desarrollamos.

[Luis Fuentes]

Hola

 Hay algo que no entiendo. Tal cómo está planteado. ¿Qué importan los nodos? Si los números en azul computan desplazamiento más trabajo, en tu ejemplo, parece que directamente podría formularse como que hay siete trabajos cada uno de las duraciones dadas. ¿Es así o me estoy perdiendo algo?. Intuyo que si...

saludos.

[mathtruco]

gracias el_manco,

 tienes razón. Los nodos no son importantes, y puede considerarse que cada trabajo es un nodo (con su tiempo de ida, resolución y vuelta al punto rojo) como muestra la siguiente imagen




Como decía, una solución es que enviar a cada nodo verde (trabajo) un trabajador, pero como cada uno puede trabajar hasta 8 horas puedo enviar a un mismo trabajador a realizar varios trabajos. Lo que busco es cómo formular este problema para N trabajos (nodos verdes), y ojalá formular el problema como uno de optimización lineal.

[Luis Fuentes]

Hola

 Tengo que pensarlo un poco mas. Pero una observación, siempre que no haya un trabajo de más de ocho horas, tu problema es el mismo que este:

http://rinconmatematico.com/foros/index.php/topic,30821.msg121360.html#msg121360

 Los postes y su longitud, son los trabajos y su duración. Las filas son los trabajadores.

Saludos.

[mathtruco]

gracias el_manco,

 tienes razón, me has pillado. Pensando en este problema se me ocurrió formularlo como uno equivalente en http://rinconmatematico.com/foros/index.php/topic,30821.msg121360.html#msg121360 que me pareció más didáctico y simple.

 Resolviendo uno se tiene el otro.

 Pero se ven muy simples, y me llama la atención que se me hayan complicado. Dudaría que no se pueden resolver, pero no sé por donde agarrarlo.

 Agradecería me eches una mano.

[Luis Fuentes]

Hola

 Una cosa: ¿es obligatorio resolverlo por programación lineal? Es decir, ¿es un problema pensado para resolverlo en ese contexto?.

Saludos.

[mathtruco]

Lo ideal es ponerlo como programa lineal.

Pero también es interesante saber si existe otra forma de resolverlo. Quizás simplemente no es posible proponerlo como problema de optimización lineal.

[Luis Fuentes]

Hola

 mmmm.. creo que se trata de programación lineal entera. Pero nunca la estudié. El caso es que estuve investigando un poco.

 Tu problema, en particular es el problema de empaquetamiento de cajas en una dimensión (one-dimensional bin packing problem). Por ejemplo mira por aquí:

http://www.ams.org/featurecolumn/archive/bins1.html

 "googleando" tienes montones de artículos relacionados (la mayoría eso si en inglés).

Saludos.

[mathtruco]

Pareciera que es un problema bin_packing (embalaje). No los conocía. También los estudiaré y trataré de ver si se puede ver este problema como uno de "encajamiento".

[Luis Fuentes]

Hola

 Si, de hecho es exactamente el problema que se describe en el enlace. ¿No?.

Saludos.