El pueblo tiene cuatro oficiales de tránsito que trabajan dos turnos por día, en la mañana y en la tarde. Los cuatro trabajan a la misma velocidad. Las rutas de la mañana tienen longitudes x1 > x2 > x3 > x4, y las rutas de la tarde tienen longitudes y1 > y2 > y3 > y4. A cada oficial que trabaja mas de H horas, se le pagan las horas extras.
Por cierto, los cuatro se juntan en la tienda de donas del pueblo para el almuerzo, alli hay cuatro cocineros en una situación similar: Para llegar al trabajo estacionan sus patinetas en la calle donde los parkimetros tienen tiempo limite de H horas. Sus jornadas de hornear son de x1 > x2 > x3 > x4 horas y sus jornadas de limpieza son de y1 > y2 > y3 > y4 horas. La tienda paga las multas de estacionamiento de los cocineros cuyas jornadas tienen mas de H horas.
Demuestre que la mejor forma de asignar las rutas de la mañana y de la tarde a cada oficial para minimizar las horas extras es x1 + y4, x2 + y3, x3 + y2, x4 + y1. ¿Es necesariamente ésta también la mejor forma de asignar las jornadas a los cocineros?
Solución
Recibimos una solución correcta de Patrick LoPresti (Estados Unidos),
quien basó su argumento en dos observaciones preliminares simples. La
primera describe un algoritmo que él llama algoritmo del sorteo de la
burbuja ilusa.
Observación 1. Dada una sucesión de N números reales a1, a2, .. , aN, el siguiente algoritmo siempre se para, y cuando lo hace la sucesión será sorteada en orden no creciente.
| Paso 1. | Si todo par adyacente de elementos está ordenado (esto es, si ai ≥ ai+1 para i del 1 a N – 1) entonces se para. |
| Paso 2. | Si no, encuentre un par de números adyacentes los cuales están fuera de orden e intercámbielos. |
| Demostración. | Si la sucesión no está sorteada, entonces por lo menos un elemento esta fuera de orden: aj es menor que ak para j < k. El primer elemento que esta fuera de orden, por definición, será precedido por un elemento menor. Simplemente intercámbielos y el número de parejas que están fuera de orden disminuye en uno menos. Ya que el número de parejas es finito, el algoritmo termina cuando no hay parejas fuera de orden. |
Observación 2. El problema análogo cuando hay solamente dos oficiales de tránsito es fácil. Más precisamente, si
| a. | Hay dos turnos de mañana con x1 > x2, |
| b. | Dos turnos de tarde con y1 > y2, y |
| c. | Cualquier trabajo de mas de H horas de tiempo extra, |
Entonces para minimizar el tiempo extra el horario sugerido (x1 +y2, x2 + y1) es tan bueno o mejor que el horario alternativo (x1 +y1, x2 + y2).
| Demostración. | Una buena forma de organizar toda la información es en una matriz de 2 por 2 cuyas columnas tienen el encabezado de x1 y x2, y cuyas hileras las llamamos y1 y y2. La entrada en la columna i, hilera j, es la más grande entre xi + yj – H y 0, esto es, las horas de tiempo extra que se suceden con la asignación xi e yj. Debemos asignar a cada oficial de tránsito una hilera y columna así que
Cada hilera y columna tiene un nombre. Esto lo
sabemos (por las condiciones (a) y (b)).
De donde, si la entrada de la primera hilera y columna es 0 entonces todas las entradas de la matriz son cero (porque H es mayor que cualquier número asignado); no se paga tiempo extra, no importa como los turnos son asignados. Esto significa que las asignaciones sugeridas son tan buenas como las alternativas. También, si ninguna entrada es 0, ambas asignaciones son igualmente malas: la cantidad total de horas extras sería x1 + x2 + y1 + y2 2H cualquiera que sea el horario que se use. La pregunta se reduce a que es lo que pasa cuando la entrada de la parte superior izquierda no es cero y la parte inferior derecha es cero. La asignación alternativa (x1 +y1, x2 + y2) pagará por x1 + y1H horas de tiempo extra. Necesitamos comparar esto con la asignación sugerida cuyas horas de sobre tiempo es a lo mas (x1 + y2 – H) + (x2 + y1 – H) = (x1 + y1 – H) + (x2 + y2 – H). La suma de la derecha es a lo mas x1 + y1 H porque el último término es a lo más 0. Por supuesto, uno de ellos o ambos de los dos términos en la izquierda podrían ser cero. En otras palabras, la asignación sugerida da ya sea las mismas o menos horas de tiempo extra, y otra vez, vemos que es por lo menos tan bueno como la alternativa. Esto termina la demostración de la segunda observación. |
. Combinando nuestras dos observaciones, el resultado se sigue fácilmente. Sin pérdida de generalidad fijamos una de las asignaciones de la mañana. Nuestra meta es asignar las rutas de la tarde para minimizar el tiempo extra. Empecemos haciendo parejas con cada x e y, por cualquier método que se desee. Encontamos un par adyacente cuyas rutas de la tarde están fuera de orden; esto es, xs esta asociado con yi, y xt esta asociado con yj, pero s < t e i < j. Este par de oficiales cumplen con las condiciones de la observación 2, así que podemos intercambias las rutas de la tarde sin aumentar las horas de tiempo extra. Por la primera observación este proceso termina eventualmente con las rutas de la tarde in el orden sugerido con las asignaciones x1+y4, x2+y3, x3+y2, x4+y1. Note que el argumento generaliza el número arbitrario de oficiales de tránsito.
Para la segunda parte de la pregunta, la respuesta es negativa, las asignaciones de los oficiales no necesariamente son las mejores para los cocineros. Aquí esta un contraejemplo simple. Sea (x1, x2, x3, x4) = (y1, y2, y3, y4) = (4, 3, 2, 1) y sea H = 4. Entonces el horario de los oficiales (x1+y4, x2+y3, x3+y2, x4+y1) = (5, 5, 5, 5) resulta en que todos los cuatro cocineros reciben multas. El horario alternativo (x1+y1, x2+y4, x3+y3, x4+y2) = (8, 4, 4, 4) resulta en que solamente un cocinero es multado.
Nuestro problema de noviembre fue inspirado por un problema en Introduction to Graph Theory, de Douglas B. West. Aparece en un capítulo en donde se discute como las gráficas pueden ser usadas para resolver problemas de emparejar pesos mínimos. El mensaje de West parece ser que no siempre es necesario que usted use su gran maquinaria en todos los problemas.