Programación dinámica probabilística (II)

Debido a la estructura probabílistica, la relación entre fn(sn, xn) y f*2(sn+1) necesariamentees más complicada que para el caso determinístico. La forma exacta de esta relación dependerá de la forma global de la función objetivo.

Para ilustrar esto, supóngase que el objetivo es minimizar la suma esperada de las contribuciones de las etapas individuales. En este caso, fn(sn, xn) representa la suma esperada mínima de la etapa n  en adelante, dado que en la etapa n, el estado es sn y la política de decisión es xn. En consecuencia

Programación dinámica probabilística (I)

La programación dinámica probabilística difiere de la deterministica en que el estado de la siguiente etapa no está completamente determinado por el estado y la política de decisión de la etapa actual. En este caso, existe una distribución de probabilidad para determinar cuál será el estado en la siguiente etapa. Sin embargo, esta distribución de probabilidad sí queda bien determinada por el estado y la política de decisión en la etapa actual. En la figura 11.8 se describe la estructura básica que resulta en los problemas de programación dinámica probabílistica.

En lo que se refiere a este diagrama, sea S el número de estados posibles en la etapa n +1 que se etiquetan al lado derecho por 1,2,...., S. El sistema cambia al estado i con probabilidad pi(i=1,2,.....,S) dados el estado sn y la decisión xn en la etapa n. Si el sistema cambia al estado i, Ci es la contribución de la etapa n a la función objetivo.

Cuando se expande la figura 11.8 para incluir todos los estados y las decisiones posibles en todas las etapas, se obtiene lo que con frecuencia se conoce como árbol de decisión. Si este árbol de decisión no es muy grande, proporciona una foma útil de resumir las distintas posibilidades que se tienen.

Solución Problema de la Wyndor Glass Company (VI)

Etapa I: Para resolver el problema de dos etapas (n=1), se sustituye la solución que se acaba de obtener para f*2(R1,R2, R3) en la ecuación (3). Para la etapa 2

Solución Problema de la Wyndor Glass Company (V)

Etapa 2

Formulación Problema de la Wyndor Glass Company (IV)

De manera parecida, para n = 1,2

La ecuación (1) se usará para resolver el problema de 2 etapas. La ecuación (2) muestra la estructura básica de programación dinámica para este problema, como puede ver en la figura 11.7. La ecuación (3) proporciona una relación recursiva entre f*1 y f*2 que se usará para resolver el problema de una etapa.

Formulación Problema de la Wyndor Glass Company (III)

Cada una de las tres variables de estado continua, por lo que, en lugar de considerar por separado las combinaciones posibles de valores, debe emplearse el método introducido en ele ejmplo 4 para obtener la información requerida como una función del estado del sistema.

Pese a estas complicaciones, el problema es lo suficientemente pequeño como para poder resolverse sin mucha dificultad. Para hacerlo es necesario introducir la notación usual de programación dinámica. Así.

fn(R1, R2, R3, x2) = contribución de la actividad 2 a Z si el sistema encuentra en el estado (R1, R2, R3) al inciar la etapa 2 y la decisión es x2

= 5x3.

Formulación Problema de la Wyndor Glass Company (II)

Pero al comenzar este problema en la etapa 2, todavía no se conoce el valor de x1 por lo que en ese momento se usa s2 = (R1, R2, R3).

Contrariamente a los ejemplos anteriores, este problema tiene tres variables de estado (es decir, es un vector estado con tres componentes) en lugar de una. Desde un punto de vista teórico, esta diferencia no es seria. Sólo significa que, en lugar de considerar todos los valores posibles de una variable de estado, deben considerarse todas las combinaciones posibles de valores de varias variables de estado. Sin embargo, desde un punto de vista de eficiencia computacional, esta diferencia tiende a ser una complicación muy seria. Como en general el número de combinaciones puede ser tan grande como el producto del número de valores posibles de las respectivas variables, la cantidad de cálculos que se requieren tiende a "explorar" muy rápido cuando se introducen variables de estado adicionales. Este fenómeno ha recibido el adecuado nombre de calamidad de la dimensión.

Formulación Problema de la Wyndor Glass Company (I)

Este problema requiere tomar dos decisiones interrelacionadas, a saber, el nivel x1 de la actividad 1 y el nivel x2 de la actividad 2. Por ello, estas dos actividades se pueden interpretar como las dos etapas en una formulación de programación dinámica. Aunque se pueden tomar en cualquier orden, sea la etapa n = la actividad n(n=1,2). Así, xn es la variable de decisión en la etapa n.

Cuáles son los estados? es decir, dado que se toma una decisión en la etapas anteriores (si las hay) qué información se necesita sobre el estado actual de las cosas antes de poder tomar una decisión en la etapa n? Un poco de reflexión puede sugerir que la información requerida es la cantidad de holgura que queda en las restricciones funcionales. El lado derecho de estas restricciones (4,12 y 18) se interpreta como la cantidad total disponible de los recursos 1, 2 y 3, respectivamente (como se describió en la sección 3.1) Entonces el estado sn se puede definir como

Ejemplo Problema de la Wyndor Glass Company (I)

Considérese el siguiente problema de programación lineal

(puede reconocerse en este modelo el que se estableción para el problema de la Wyndor Glass Company en anteriores capitulos) Una manera de resolver problemas pequeño de programación línael (o no lineal) como éste es emplear programación dinámica. Esto se ilustra a continuación.

Procedimiento de solución Programación del nivel de empleados (VII)

Y como s1= 255, se concluye que x1 = 247.5 minimiza a f1(s1,x1) en la región 240 ≤ x1 ≤ 255.

Procedimiento de solución Programación del nivel de empleados (VI)

Etapa 1: Para el problema de cuatro etapas (n=1)

Procedimiento de solución Programación del nivel de empleados (V)

Entonces, todavia es necesario obtener el valor factible de x2 que minimiza f2(s2, x2) cuando 220 ≤ s2 < 240. La clave para analizar el comportamiento de f2(s2,x2) dentro de la región factible de x2 de nuevo es la derivada parcial de f2(s2,x2). Cuando s2 < 240.

Procedimiento de solución Programación del nivel de empleados (IV)

Etapa 2: Los problemas para tres (n=2) y cuatro (n=1) etapas se resuelven en forma parecida. Para n=2

este valor de x2 es el valor que da el mínimo si es factible (240 ≤ x2 ≤ 255). Sobre los valores posibles de s2 (220 ≤ s2 ≤ 255), esta solución es factible sólo si 240 ≤ s2 ≤ 255.

Procedimiento de solución Programación del nivel de empleados (III)

Como la segunda derivada es positiva y como es solución se encuentra en el intervalo factible de x3(200 ≤ x3 ≤ 255), para todos los valores posibles de s3 (240 ≤ s3 ≤ 255), sin duda se trata del mínimo que se busca.

Obsérvese la diferencia clave entre la naturaleza de esta solución y las obtenidas en el ejemplo anterior en donde sólo había unos cuantos estados posibles. Ahora se tiene un número infinito de estados posibles (240 ≤ s3 ≤ 255), por lo que ya no es factible resolver por separado el valor de x*3 para cada valor de s3. En lugar de esto, se obtiene x*3 como una función de la incógnita s3.

Al utilizar.

y reducir algebraicamente esta expresión, se obtienen los resultados requeridos para el problema de dos etapas que se resumen como sigue:

Procedimiento de solución Programación del nivel de empleados (II)

Una manera de obtener el valor de x3 que minimiza f3(x3,x3) para cualquier valor dado de sn es el método gráfico que se muestra en la figura 11.6.

Sin embargo, mediante el Cálculo se encuentra la solución más rápidamente. Se quiere obtener el valor que minimiza de x3 en términos de s3 considerando que s3 tiene un valor fijo (aunque desconocido). Se iguala a cero la primera derivada (parcial) de f3(sn,x3) con respecto a x3

Procedimiento de solución Programación del nivel de empleados (I)

Etapa 4: Al comenzar en la última etapa (n=4), se sabe que x*n = 255, de manera que los resultados son

Formulación Programación del nivel de empleados (III)

Obsérvese que el costo de la etapa actual depende sólo de la decisión xn que se tome en esa etapa y del número de empleados de la etapa anterior xn-1. El nivel de empleados anterior es toda la información sobre el estado actual que se necesita para determinar la política óptima de ahí en adelante. Por esto, el estado sn para la etapa n es:

Formulación Programación del nivel de empleados (II)

Es necesario que la temporada de primavera sea la última etapa porque debe conocerse o poderse obtener el valor óptimo de la variable de decisión para cada estado en esta última etapa sin tener que considerar otras. En todas las demás etapas, la solución del nivel óptimo de empleo debe tomar en cuenta el efecto sobre los costos de la siguiente temporada.

Sea

rn = la mano de obra mínima requerida en la etapa n,
 donde estos requerimientos se dieron antes como r1 = 220, r2 = 240, r3 = 200 y y r4 =255.

Los únicos valores factibles para xn son

rn ≤ xn ≤ 255

Si se hace referencia a los datos de costo dados en el enunciado del problema

Costo en la etapa n = 200(xn - xn-1)² + 2000 (xn- rn).

Formulación Programación del nivel de empleados (I)

Si el análisis se basa en los datos disponibles, se puede ver que no vale la pena que ningún nivel de empleo sea mayor que 255, que corresponde a los requerimientos de la temporada pico. Así, el número de empleados en primavera deberá ser 255 y el problema se reduce a encontrar el nivel para las otras temporadas.

Por lo que se refiere a la formulación de programación dinámica, las temporadas deben ser las etapas. En realidad existe un número indefinido de etapas pues el problema se proyecta a un futuro indefinido. Sin embargo, cada año comienza un ciclo idéntico y, como se conoce el nivel de empleados para la primavera, es factible tomar en cuenta sólo un ciclo de cuatro temporadas que termine en primavera, como se resume en seguida.

Etapa 1 = verano,
Etapa 2 = otoño,
Etapa 3 = invierno,
Etapa 4 =  primavera,
xn = nivel de empleados para la etapa n (n=1,2,3,4)
(x4 = 255)

Ejemplo 4 - Programación del nivel de empleados (II)

No se permitirá que el nivel de empleados baje estos niveles. Cualquier contratación más alta que estos niveles se desperdicia con un costo aproximado de $2000/personas/temporada. Se estima que los costos de contratación y despido son tales que el costo de cambiar  el nivel de empleados de una temporada a la siguiente es igual a $200 multiplicado por la raíz cuadrada de la diferencia de nivel. Es posible contar con niveles fraccionales gracias a que hay algunos empleados de tiempo parcial, y los datos de costos se aplican igual igual a estas fracciones.

Ejemplo 4 - Programación del nivel de empleados (I)

La carga de trabajo para un LOCALJOBSHOP está sujeta a grandes fluctuaciones que dependen de la temporada. Sin embargo, es difícil contratar y costoso capacitar a las operadores de las máquinas, por lo que el gerente rechaza la idea de despedir trabajadores durante las temporadas bajas. Tampoco quiere mantener su nómina de temporadas altas cuando no se requiere y definitivamente se opone a pagar tiempo extra en forma regular. Como todos los trabajos se hacen sobre pedido, no es posible acumular un inventario durante las temporadas bajas. Así, el gerente se encuentra en un dilema al respecto a cuál debe ser la política que debe seguir en cuanto a los niveles d empleados.

A continuación se dan las estimaciones sobre la mano de obra requerida durante las cuatro temporadas del año para un futuro cercano:

Procedimiento de Solución Distribución de científicos a grupos de investigación (II)

De esta manera, la solución óptima debe tener x*1 = 1 lo que hace s2 = 2-1 =1,  y con esto x*2 = 0, con lo que s3 = 1-0 = 1 y x*3 =1. ASí, cada uno de los equipos 1 y 3 debe recibir un científico adicional. La nueva probabilidad de que los tres equipos fracasen sería 0.060.

Hasta ahora, todos los ejemplos han tenido variables de estado sn discretas en cada etapa. Lo que más, todos han sido reversibles en el sentido de que, de hecho, el procedimiento de solución se puede mover hacia atrás o hacia adelante etapa por etapa. (Esta última alternativa se reduce a reenumerar las etapas en el orden inverso y después aplicar el procedimiento estándar.) Esta propiedad de ser reversible, en general es una característica de los problemas de distribución del esfuerzo como en los ejemplos 2 y 3, ya que las actividades (etapas) se pueden ordenar de cualquier manera.

El siguiente ejemplo es diferente en ambos aspectos; en lugar de estar restringida a valores enteros, su variable de estado sn en la etapa n es continua y puede tomar cualquier valor dentro de ciertos intervalos. Como sn ahora tiene un número infinito de valores, ya no es posible considerar cada uno de sus valores posibles en forma individual. Ahora la solución para f*n(sn) y x*n debe expresarse como funciones de sn. Aún más, este ejemplo no es reversible porque sus etapas corresponden a ciertos periodos en el tiempo, por lo que el procedimiento de solución debe proceder hacia atrás.

Procedimiento de Solución Distribución de científicos a grupos de investigación (I)

Los cálculos de programación dinámica que se obtienen son:

Formulación Distribución de científicos a grupos de investigación (II)

Sea pi(xi) la probabilidad de fracaso del equipo i si le asignan xi cientifícos adicionales, como se da en la tabla 11.2. Si el signo Π denota multiplicación, el objetivo del gobierno será elegir xi, x2, x3 para

Formulación Distribución de científicos a grupos de investigación (I)

Puesto que tanto el ejemplo 2 como el 3 tratan el problema de la distribución del esfuerzo, en realidad su estructura básica es muy semejante. En este caso, los científicos sustituyen a las brigadas médicas como el recurso con que se cuenta y los equipos de investigación sustituyen a los países como las actividades. Entonces, en lugar de brigadas médicas que se destinan a los países, se asignarán científicos a los equipos de investigación. La única diferencia básica entre los dos problemas está en su función objetivo.

Con un número tan pequeño de científicos y equipos, este problema se puede resolver fácilmente mediante un proceso de enumeración exhaustiva. El procedimiento de solución por programación dinámica se presenta con propósitos explicativos.

En este caso, las etapas (n = 1,2,3) corresponden a los equipos de investigación y el estado sn es el número todavia disponible de cientificos que van a asignarse a los equipos restantes. Las variables de decisión xn (n = 1,2,3) son el número de científicos adicionales que se asignan al equipo n.

Ejemplo Distribución de científicos a grupos de investigación

Un proyecto espacial del gobierno lleva a cabo una investigación sobre cierto problema de ingeniería que debe resolverse antes de que seres humanos puedan viajar a salvo a Marte. Por el momento, tres equipos de investigación tratan de resolver el problema desde tres puntos de vista diferentes. Se estima que en las circunstancias actuales, la probabilidad de que los respectivos equipos (llámense 1, 3 y 3) fracasen es de 0.40, 0.60 y 0.80. Así,  la probabilidad actual de que los tres equipos fracasen es (0.40)(0.60)(0.80) = 0.192. Como el objetivo es minimizar la probabilidad de fracaso, se asignarán al proyecto dos o más científicos de alto nivel.

La tabla 11.2 de la probabilidad estimada de que los equipos respectivos fracasen si se les asigna 0, 1 o 2 científicos para colaborar con ellos. Sólo se considerarán números enteros de científicos puesto que cada uno de ellos deberá dedicar su atención completa a un equipo al que se asignó. El problema es determinar cómo deben asignarse los científicos adicionales para minimizar la probabilidad de que los tres equipos fracasen.

Formulación Problema de distribución de esfuerzo (II)

Obsérvese que la estructura de este diagrama corresponde a la que se mostró en la figura 11.3 para el ejemplo del World Health Council de distribución de esfuerzo. Lo que puede diferir de un ejemplo a otro es el resto de lo que se muestra en la figura 11.3, es decir, la relación entre fn(sn, xn) y f*n(sn-xn) y después la relación recursiva que se obtiene entre las funciones f*n y f*(n+1). Estas relaciones dependen de la función objetivo específica para el problema.

La estructura del siguiente ejemplo puede parecer que no es un problema deterministico de programación dinámica, pues trata con probabilidades. No obstante, se ajusta a la definición porque el estado en la siguiente etapa queda completamente determinado por el estado y la política de decisión en la etapa actual.

Formulación Problema de distribución de esfuerzo (I)

Debido a que los problemas de distribución del esfuerzo siempre incluyen la asignación de un tipo de recurso a cierto número de actividades, siempre tiene la siguiente formulación de programación dinámica (en donde el orden de las actividades es arbitrario):

Etapa n = actividad n (n = 1,2,.... N).
xn = cantidad de recursos asignados a la actividad n.
Estado Sn = cantidad de recurso que todavía están disponibles para asignarse a las actividades restantes (n,...,N)

Entonces, al iniciar la etapa n en el estado sn, la elección de xn siempre da como resultado que el siguiente estado en la etapa (n+1) sea s(n+1) = (sn - xn), como lo muestra el diagrama:

Suposiciones Problema de distribución de esfuerzo (II)

Por otro lado, el problema de la distribución del esfuerzo es mucho más general que la programación líneal, si se consideran las cuatro suposiciones de programación líneal presentadas en la sección 3.3 (proporcionalidad, aditividad, divisibilidad y certidumbre). La proporcionalidad se viola constantemente en casi todos los problemas de programación dinámica, incluyendo los de distribución del esfuerzo (por ejemplo, la tabla 11.1 viola la proporcionalidad). La divisibilidad también se viola con frecuencia, como en el ejemplo 2, en donde las variables de decisión deben ser enteros. De hecho, los cálculos de programación dinámica se vuelven más complejos cuando se cumple la divisibilidad (como en los ejemplos 4 y 5). Aunque en este blog se considerará el problema de la distribución del esfuerzo sólo bajo condiciones de certidumbre, ésta no es necesaria y muchos otros problemas de programación dinámica violan también esta suposición.

De las cuatro suposiciones de programación líneal, la única necesaria en el problema de la distribución del esfuerzo (u otros problemas de programación dinámica) es la aditividad (o su análogo para funciones que implican el producto de términos). Esta suposición se requiere para satisfacer el principio de optimalidad para programación dinámica.

Suposiciones Problema de distribución de esfuerzo (I)

Esta interpretación de distribución de recursos a actividades debe ser familiar al lector ya que es la más común de los problemas de programación lineal dada al principio del capítulo 3. Sin embargo, existen algunas diferencias importantes entre el problema de la distribución del esfuerzo y la programación líneal que deben ayudar a aclarar las distinciones generales entre programación dinámica y otras áreas de la programación matemática.

Una diferencia clave es que el problema de la distribución del esfuerzo incluye sólo un recurso (una restricción funcional), mientras que programación lineal puede manejar cientos o miles de recursos. (En principio, la programación dinámica puede manejar algo más que un recurso, como se verá en el ejemplo 5, en el que se resuelve el problema de tres recursos de la Wyndor Glass Co., pero pronto se vuelve muy ineficiente conforme se aumenta el número de recursos.)

Un problema de tipo prevalente - Problema de distribución de esfuerzo

Un ejemplo anterior ilustra un tipo particularmente común de problemas de programación dinámica llamado problema de distribución de esfuerzo. En este grupo de problemas existe sólo una clase de recurso que debe asignarse a un cierto número de actividades. El objetivo es determinar cómo distribuir el esfuerzo (el recurso) entre las actividades de la manera más efectiva. En el caso del World Health Council, el recurso de que se trata es el conjunto de brigadas médicas, y las tres actividades son los trabajos sobre cuidado de la salud en los tres países.