Procedimiento de Solución Distribución de brigadas médicas Formulación (V)

En la siguiente tabla se muestran los cálculos parecidos para x1 = 2, 3, 4 (inténtese) y verifican que x*1 = 1 con f*1 = 170.

Procedimiento de Solución Distribución de brigadas médicas Formulación (IV)

Si se asignan x1 brigadas médicas al país se llega al estado (5-x1) brigadas disponibles en la etapa 2, la elección x1 = 0 se llega al nodo inferior de la derecha, x1 = 1 lleva al siguiente nodo hacia arriba, etc., hasta el nodo superior con x1 =  5. Junto a las ligaduras se muestran los valores correspondientes a p1(x1) de la tabla 11.1. Los números junto a los nodos se obtienen de la columna de f*2(s2) de la tabla para n = 2. Como antes, se resumen los cálculos para cada valor posible de la variable de decisión que implica sumar los valores de la ligadura correspondiente y el valor del nodo:

Procedimiento de Solución Distribución de brigadas médicas Formulación (III)

Debido a que el objetivo es maximizar, x*2 = 0 o con f*2(2) = 70

Continuando de una manera similar con los otros valores posibles de s2 (inténtese esto) se llega a la siguiente tabla.

Procedimiento de Solución Distribución de brigadas médicas Formulación (II)

ESte diagrama corresponde a la figura 11.3, sólo que ahora muestra los tres estados posibles en la etapa 3. Así, si x2 = 0, el estado que resulta de la etapa 3 será s2 - x2 = 2 -0 =2, mientras que si x2 = 1 se llega al estado 1 y x2 =  2 conduce el estado 0. Los valores correspondientes de p2(x2) en la columna del país 2 de la tabla 11.1 se muestran junto a las ligaduras y los valores de f*3(s2-x2) que se encontraron en la tabla para n = 3 se dan junto a los nodos de la etapa 3. A continuación se resumen los cálculos requeridos en este caso para s2 =2.

Procedimiento de Solución Distribución de brigadas médicas Formulación (I)

Comenzando con la última etapa (n=3), se observa que los valores de p3(x3), dados en la última columna de la tabla 11.1, aumentan hacia abajo de la columna. Entonces si se dispone de s3 brigadas médicas para asignar al país 3, el máximo de p3(x3) se logra de manera automática al asignar todas las s3 brigadas; así, x*3 = s3 y f*3(s3) = P3(s3), como se puede ver en la siguiente tabla

Ejemplo Distribución de brigadas médicas Formulación (IV)

Sea pi(xi) la medida de eficiencia obtenida si se asignan xi brigadas médicas  al país i, según los datos de la tabla 11.1. Entonces, el objetivo es elegir x1, x2, x3 tales que

Ejemplo Distribución de brigadas médicas Formulación (III)

La identificación de los estados puede no ser tan evidente. Para determinarlos se hacen preguntas como las que siguen. Qué es lo que cambia de una etapa a la otra? Dado que se han tomado las decisiones en las etapas anteriores, cómo se puede describir el estado de la situación? Qué información sobre el estado actual de las cosas se necesita para determinar la política óptima de aquí en adelante? Sobre esta base, una opción apropiada para "el estado del sistema" es

sn = número de brigadas médicas todavía disponibles para asignarse a los países restantes (n,......., 3)

Así  en la etapa 1 (país 1), cuando todavía quedan por asignar brigadas a los tres paises, s1 = 5. Sin embargo, en las etapas 2 o 3 (países 2 o 3), sn es sólo 5 menos el número de brigadas asignadas en etapas anteriores. Con el procedimiento de programación dinámica que resuelve hacia atrás etapa por etapa, cuando se trabaja en la etapa 2 o 3, todavía no se han obtenido las asignaciones de las etapas anteriores. Por lo tanto, se deben considerar todos los estados posible en los que se puede encontrar al iniciar la etapa 2 o 3, a saber, sn =0,1,2,3,4 o 5.

Ejemplo Distribución de brigadas médicas Formulación (II)

Este problema requiere que se tomen tres decisiones interrelacionadas, a saber, cuántas brigadas conviene asignar a cada uno de los tres países. Aun cuando no existe una secuencia fija, estos tres países se pueden considerar como las etapas en la formulación de programación dinámica. Las  variables de decisión xn (n = 1, 2, 3) serían el número de brigadas asignadas a la etapa (país) n.

Ejemplo Distribución de brigadas médicas (I)

El World Helth Council se dedica a mejorar la atención médica en los países subdesarrollados del mundo. Dispone de cinco brigadas médicas para asignarlas a tres de estos países con el fin de mejorar el cuidado de la salud, la educación para la salud y los programas de capacitación. Entonces, el consejo necesita determinar cuántas brigadas debe asignar (sí lo hace)  a cada uno de estos países para maximizar la medida de eficiencia de las cinco brigadas. Los equipos deben mantenerse como están formados por lo que el número asignado a cada país debe ser un entero.

La medida de eficiencia se tomará en términos de los años de vida adicionales por persona. (Para un país específico, esta medida es igual al incremento en el promedio de vida esperado en años, multiplicado por su población) En la tabla 11.1 se dan las estimaciones de estos años de vida adicionales por persona (en múltiplos de 1000) para cada país y para cada número posible de brigadas médicas asignadas.

Cuál es la asignación que maximiza la medida de eficiencia?

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

Una manera de clasificar los problemas de programación dinámica determinística es por la forma de la función objetivo. Por ejemplo, el objetivo puede ser minimizar la suma de las contribuciones de cada una de las etapas individuales (como en el problema de la diligencia), o maximizar esa suma, o bien minimizar el producto de los términos, etc. Otra clasificación se puede hacer en términos de la naturaleza del conjunto de estados en las respectivas etapas. En particular, los estados sn pueden estar representados por una variable de estado discreta (como en el problema de la diligencia), o por una variable de estado continua, o tal vez se requiere un vector de estado (más de una variable)

Se presentarán varios ejemplos para ilustrar estas posibilidades, pero es más importante el hecho de que dichos ejemplos ponen de manifesto que estas diferencias, aparentemente grandes, en realidad son instrascendentes (excepto en términos de la dificultad de los cálculos) pues la estructura básica que se muestra en la figura 11.2 permanece igual.

El primero ejemplo surgen en un contexto muy distinto al del problema de la diligencia, pero tiene la misma formulación matemática, aunque esta vez se trata de maximizar en lugar de minimizar una suma.

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

Esta sección profundiza sobre el enfoque de programación dinámica en los problemas determínisticos, en donde el estado en la siguiente etapa está completamente determinado por el estado y la política de decisión de la etapa actual. El caso probabílistico en el que existe una distribución de probabilidad para el valor posible del siguiente estado, se analizará en la sección siguiente.


La programación dinámica determínistica se puede describir en forma de diagrama como se hace en la figura 11.2. En la etapa n el proceso se encontrará en algún estado sn. Al tomar la decisión xn se mueve a algún estado sn+1 en la etapa (n+1). El valor de la función objetivo para la política óptima de ese punto en adelante se calculó previamente como f*(n+1)(S(n+1)). La política de decisión también hace una contribución a la función objetivo. Al combinar estas dos cantidades en la forma apropiada se proporciona a la función objetivo fn(Sn, Xn) la contribución de la etapa n en adelante. La optimización respecto a xn proporciona entonces f*n(Sn) = fn(sn, x*n). Una ve que se encontraron x*n y f*n(sn) para cada valor posible de sn, el procedimiento de solución se mueve hacia atrás una etapa.

Características de los problemas de programación dinámica (IX)

8. Cuando se usa esta relación recursiva, el procedimiento de solución se mueve hacia atrás etapa por etapa -encontrando cada vez la política óptima para esa etapa- hasta que encuentra la política óptima desde la etapa inicial.

Este movimiento hacia atrás se mostró en el problema de la diligencia, en el que se encontró la política óptima, en forma sucesiva, comenzando en cada estado de las etapas 4,3,2 y 1, respectivamente. Para todos los problemas de programación dinámica, se obtiene una tabla como la siguiente para cada etapa (n= N, N-1, ....., 1).

Cuando se obtiene esta tabla para la etapa inicial (n=1), el problema queda resuelto. Como se conoce el estado de la etapa inicial, la primera decisión está especificada por x*n en esta tabla. El valor óptimo de las otras variables de decisión queda, a su vez, especificado por las otras tablas de acuerdo con el estado del sistema que resulta una vez tomada la decisión anterior.

Características de los problemas de programación dinámica (VIII)

La forma precisa de la relación recursiva difiere de un problema a otro, pero se usará una notación análoga a la introducida en la sección anterior, como se resume a continuación:

Características de los problemas de programación dinámica (VII)

7. Se dispone de una relación recursiva que identifica la política óptima para la etapa n, dada la política óptima para la etapa (n+1).

En el problema de la diligencia, la relación recursiva que se obtuvo es

Entonces, para encontrar política óptima de decisión cuando se comienza en el estado s de la etapa n se necesita encontrar el valor de xn que dé un mínimo. El costo mínimo correspondiente se obtiene si se usa este valor de xn y después se sigue la política óptima cuando el proceso se encuentra en el estado xn en la etapa (n+1)

Características de los problemas de programación dinámica (VII)

6. El procedimiento de solución se inicia al encontrar la política óptima para la última etapa. La política óptima para la última etapa prescribe la política óptima de decisión para cada estado posible en esa etapa. Es común que la decisión de este problema de una etapa sea trivial como lo fue para el problema de la diligencia.

Características de los problemas de programación dinámica (VI)

5. Dado el estado actual, una política óptima para las etapas restantes es independiente de la política adoptada en etapas anteriores.

Dado el estado en el que se localiza el cazafortunas, la póliza de seguro de vida óptima (y su ruta asociada) desde este lugar en adelante es independiente de cómo llegó hasta ahí. En general, en los problemas de problemas de programación dinámica, el conocimiento del estado actual del sistema expresa toda la información sobre su comportamiento anterior, y esta información es necesaria para determinar la política óptima de ahí en adelante. (Esta propiedad es la propiedad markoviana que se presentará en la sección 15.3). Un problema que carezca de esta propiedad no se puede formular como un problema de programación dinámica.

Características de los problemas de programación dinámica (V)

4. El procedimiento de solución está diseñado para encontrar una política óptima para el problema completo, es decir, una receta para las decisiones de la política óptima en cada etapa para cada uno de lo estados posibles.

En el problema de la diligencia, el procedimiento de solución construyó una tabla para cada etapa (n) que prescribe la decisión óptima (x*n) para cada estado posible (s). Así, además de identificar las tres soluciones óptimas (rutas óptimas) para el problema completo, los resultados muestran también cómo debe proceder el cazafortunas en caso de que sea desviado a un estado que no se encuentra en la ruta óptima. En cualquier problema, la programación dinámica proporciona esta tipo de receta o política sobre qué hacer en todas la circunstancia posibles (a esto se debe que la decisión real que se toma al llegar a un estad en particular se llama política de decisión). El proporcionar esta información adicional más allá de especificar una solución óptima (secuencia óptima de decisiones) puede ser muy valiosa en muchas situaciones que incluyen el análisis de sensibilidad.

Características de los problemas de programación dinámica (IV)

3. El efecto de la política de decisión en cada etapa es transformar el estado actual en un estado asociado con la siguiente etapa. (tal vez de acuerdo a una distribución de probabilidad).

La decisión del cazafortunas en cuanto a su siguiente destino lo conduce de su estado actual al siguiente estado en su viaje. Este procedimiento sugiere que los problemas de programación dinámica se pueden interpretar en términos de las redes descritas en el capítulo 10. Cada nodo corresponde a un estado. La red consistiría en columnas de nodos, en donde cada columna corresponde a una etapa, en forma tal que el flujo que sale de un nodo sólo puede ir a un nodo de la siguiente columna derecha. El valor asignado a cada rama que conecta dos nodos puede interpretarse  algunas veces como la contribución a la función objetivo que se obtiene al ir de un estado al siguiente que corresponde a estos nodos. Si éste es el caso, el objetivo será encontrar la ruta más corta o bien la más larga a través de la red.

Características de los problemas de programación dinámica (III)

2. Cada etapa tiene un cierto número de estados asociados a ella.
Los estados asociados con cada etapa en el problema de la diligencia son los estados (o territorios) en los que el cazafortunas se puede encontrar al iniciar esa jornada específica del viaje. En general, los estados son las distintas condiciones posibles en las que se puede encontrar el sistema en cada etapa del problema. El número de estados puede ser finito (como en el problema de la diligencia) o infinito (como en algunos ejemplos subsecuentes.

Características de los problemas de programación dinámica (II)

1. El problema se puede dividir en etapas que requieren una política de decisión en cada una de ellas.

El problema de la diligencia se dividió literalmente en sus cuatro etapas (viajes en diligencia) que corresponden a las cuatro jornadas del viaje. La política de decisión en cada etapa fue qué poliza de seguro elegir (esto es, el destino para la siguiente jornada en diligencia). De manera parecida, otros problemas de programación dinámica requieren la toma de una serie de decisiones interrelacionadas, en donde cada decisión corresponde a una etapa del problema.

Características de los problemas de programación dinámica (I)

El problema de la diligencia es un prototipo literal de los problemas de programación dinámica. De hecho, el ejemplo se diseño así, con el propósito de disponer de una interpretación física literal de la estructura abstracta de problemas de este tipo. Por tanto, una manera de reconocer una situación que se puede formular como un problema de programación dinámica es poder identificar una estructura análoga a la del problema de la diligencia.

A continuación se presentarán y estudiarán estas características básicas que distinguen a los problemas de programación dinámica.

Procedimiento de solución Ejemplo prototipo (VI)

En este punto se puede identificar la solución óptima. Los resultados del problema para n=1 indican que el cazafortunas debe elegir como primer destino inmediato el estado C o el estado D. Supóngase que elige xi* = C. Con n = 2, el resultado para s = C es x2* = E. Este resultado conduce al problema con n =3, que da x3* = H para s = E y el problema con n = 4 indica que x*4 = J para s = H. Así, una ruta óptima es A →D→E → H → J y A → D → F → I → J. Todas tienen un costo total de f1*(A) = 11.

En la siguiente sección se verá que los términos especiales que describen el contexto particular de este problema - etapa, estado, política- en realidad son parte de la terminología general de programación dinámica con una interpretación análoga en otros contextos.

Procedimiento de solución Ejemplo prototipo (V)

Si se pasa al problema de cuatro etapas (n=1), los cálculos son parecidos a los que se acaban de mostrar para el problema de tres etapas (n=2), excepto que ahora sólo hay un inicio posible, s = A, como se muestra en el diagrama

Procedimiento de solución Ejemplo prototipo (IV)

Ahora deberá ir al estado E, F o G con un costo inmediato de cC,E = 3, cC,F = 2 o cC, G = 4, respectivamente. Al llegar ahí, el costo adicional mínimo hasta llegar al destino está dado en la tabla n=3 como f*3(E) = 4, f3*(G) = 6, respectivamente, como se muestra junto a los estados E, F y G en el diagrama anterior. A continuación se resumen los cálculos que resultan para las tres alternativas.

Procedimiento de solución Ejemplo prototipo (III)

Se necesitan cálculos similares cuando se comienza en los otros dos estados posibles s = E y s = G, cuando quedan dos jornadas por viajar. Intente el lector obtener la respuesta ayudándose tanto en un diagrama (Fig 11.1) como del álgebra [combinando los valores de cij y de f*4(s)] con el fin de verificar los siguientes resultados para el problema con n = 3.

Procedimiento de solución Ejemplo prototipo (II)

Cuando el cazafortunas tiene dos etapas por recorrer (n = 3), la solución requiere unos cuantos cálculos. Por ejemplo, supóngase que se encuentra en el estado F. Entonces, como se describe en el diagrama debe ir al estado H o al estado I a un costo de cF,H =6 o cF,I =3, respectivamente. Si elige el estado H, el costo adicional mínimo al llegar ahí está dado en la tabla anterior como f*4(H) = 3, de manera que el costo total e esta decisión es 6 + 3 = 9. De igual manera, si elige el estado I, el costo total es 3+4 = 7, que es menor. Por tanto, deberá escoger el estado I, x*3 = I, ya que da el costo mínimo, f*3(F) =7.

Procedimiento de solución Ejemplo prototipo (I)

Cuando el cazafortunas tiene sólo una etapa por recorrer (n= 4), su ruta de ahí en adelante está perfectamente determinada por su estado actual s (ya sea H o I) y su destino final, x4 =J, de manera que la ruta para esta última jornada en diligencia es s → J. Como f*4(s) = f4(s,J) =csj, la solución inmediata al problema para n=4.

Formulación Ejemplo prototipo

Sean xn (n = 1,2,3,4) las variables de decisión que representan el destino inmediato de la etapa n (el n-ésimo viaje que se hará en diligencia). Entonces, la ruta seleccionada es A→ x1→ x2→ x3→ x4, en donde x4 = J.

sea fn(s, xn) el costo total de la mejor política global para las etapas restantes, dado que el agente de ventas se encuentra en el estado s listo para iniciar la etapa n y elige xn como destino inmediato. Dados s y n, sea x*n el valor de xn que miniza fn(s,xn), y sea f*n(s) el valor mínimo correspondiente de fn(s, xn). Entonces