Programación Dinámica – Investigación de Operaciones

TEORÍA

La programación dinámica es un técnica muy útil para la toma de decisiones de problemas complejos que pueden ser discretizados y secuencializados, proporciona un procedimiento sistemático para determinar la combinación óptima de decisiones; este método no tiene una formulación estándar ya que las ecuaciones que se planteen responden al problema específico.

Esta técnica es muy útil para la reducción el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas y subestructuras óptimas, todo ello haciendo uso del principio de optimalidad:

“Dada una secuencia óptima de decisiones, toda subsecuencia de ella es, a su vez, óptima”

Para la introducción de las características y terminologías de la programación dinámica se creo el problema de la diligencia por parte del profesor Harvey M Wagner:

Un cazafortunas mítico de Missouri que decide ir al oeste a sumergirse en la fiebre del oro que surgió en California a mediados del siglo XIX. Tiene que hacer ek viaje en diligencia a través de territorios sin ley, donde existen serios peligros de ser atacado por merodeadores. A pesar de que su punto de partida y su destino son fijos, tiene muchas opciones en cuanto a qué estados – o territorios – debe elegir como puntos intermedios (tomar en cuenta que el viaje es siempre de izquierda a derecha).

planos1

Para lograr el viaje se requieren de 4 etapas para ir desde el estado A a su destino en el estado J, este cazafortunas es un hombre prudente preocupado por su seguridad. Después de reflexionar un poco ideó una manera bastante ingeniosa para determinar la ruta más segura. Se ofrecen pólizas de seguros de vida a los pasajeros. Como el costo de la póliza de cualquier jornada en la diligencia está basado en una evaluación cuidadosa de la seguridad del recorrida, la ruta más segura debe ser aquella cuya póliza represente el menor costo total“.

El costo de la póliza estándar del viaje en diligencia, del estado i al estado j se denota como:

costo

Creamos las tablas asociadas a cada uno de estos costos tenemos:

pd_1

FORMULACIÓN

Vamos a dividir el problema en etapas, las etapas serán evaluadas en la solución más óptima y se agregarán en el análisis de la siguiente etapa hasta encontrar la solución más óptima general, entonces:

Sean Xn=El destino inmediato de la etapa n (el n-ésimo viaje que se hará en diligencia), tal que la ruta seleccionada final para este problema será:

A->X1->X2->X3->X4, donde X4=J

Sea fn(s,xn) el costo total de la mejor política global para enfrentar las etapas restantes, mientras el cazafortunas se encuentra en el estado “s“, listo para iniciar la etapa n y elige xn como destino inmediato. Dados s y n, sea yn el valor de xn – no necesariamente único – que minimiza fn(s,xn) y gn(s) el valor mínimo correspondiente de fn(s,xn). Entonces:

gn(s)=mínf(s,xn)=f(s,yn)

Donde:

 fn(s,xn)=costo inmediato (etapa n) + costo futuro mínimo (etapas n+1 en adelante)

Representado de la siguiente forma:

pd_3

Entonces nuestro objetivo es encontrar g1(A) y su ruta correspondiente, pero para encontrarlo debemos de resolver de forma sucesiva g4(s), g3(s), g2(s) para cada uno de los estados posibles de s y usar g2(s) para encontrar g1(A).  Entonces es una suerte de ir del fin hacia el inicio obteniendo el costo mínimo (para este caso) en cada una de las etapas.

PROCEDIMIENTO

Recordemos que hemos de ir de adelante hacia atrás, entonces partimos de la última etapa, en nuestro ejemplo esta es la etapa 4, la cual es la última etapa por recorrer, cuando esto sucede su ruta está perfectamente definida, sea por H o por I la ruta se dirige hacia J:

pd_1

Podemos entonces hacer lo siguiente:

pd_2

para el caso de la etapa 4 no existe un g(S) ya que es la última, podemos considerar entonces que este es cero, así que está solo calculado directamente con el costo que representa ir por cada una de las rutas H o I hacia J.

En la etapa 3 se nos representa que ahora se deben de recorrer 2 etapas, aquí debemos de tomar especial atención a lo siguiente; tomemos como base que desde F podemos ir sea hacia H o I:

pd_4

Sabemos por la resolución anterior que el g4(H)=3 y g4(I)=4, entonces si decidimos ir de F->H tendríamos un costo total 6+3=9, ya que estamos haciendo la ruta F->H->J; si hacemos F-I tendríamos un costo total de 3+4=7 siendo menor el costo  y haciendo que g3(F)=7, lo mismo ocurre con E y G, en consecuencia realizando la tabla:

pd_5

En cada una de las celdas hemos hecho la operación descrita para F.

Al resolver la segunda etapa, realizamos los mismos cálculos donde obtenemos la siguiente tabla:

pd_6

Solo podemos observar que el destino inmediato de B y D pueden ser E o F ya que minimizan el valor de “g“, ahora debemos de ocuparnos de la primera etapa:

pd_7

Resuelta la última etapa ya nos es  posible obtener la ruta o rutas óptimas para nuestro problema, tenemos entonces que:

A->C->E->H->J  o  A->D->E->H->J o A->D->F->I->J

Tenemos estas 3 rutas disponibles donde todas tienen el costo mínimo de 11.

CARACTERÍSTICAS

  • El problema se puede dividir por etapas, y cada una de las etapas requiere de una política de decisión.
  • Cada etapa tiene cierto número de estados, los estados son las distintas condiciones posibles en las que se puede encontrar el sistema en cada etapa.
  • El efecto de la política de decisión en cada etapa es transformar el estado actual en un estado asociado con el inicio de la siguiente etapa, entonces podemos decir que un estado es una columna de nodos, cada nodo representa un estado y cada rama una política de decisión.
  • El procedimiento de resolución de la programación dinámica está diseñado para encontrar una política óptima para cada etapa logrando así la política óptima general.
  • Dado el estado actual, una política óptima para las etapas restantes es independiente de la política adoptada en etapas anteriores, por ende la decisión inmediata óptima solo depende del estado actual y no de cómo se llegó ahí, esto es el principio de optimalidad de la programación dinámica.
  • 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. La relación recursiva en su forma difiere de un problema a otro, pero se puede emplear las notaciones que ya se han usado en el problema de la diligencia, tal que finalmente siempre será cuestión de hallar un máximo o un mínimo.
  • Cuando se hace uso de la relación recursiva, el procedimiento de solución comienza al final se mueve hacia atrás etapa por etapa hasta encontrar la política óptima en cada etapa hasta la etapa inicial.

APLICACIONES

La Ruta Crítica

Hallar la ruta crítica con programación dinámica:

pd_8

Resolución

Recordemos que debemos de dividir por etapas nuestra red, sabemos que una etapa es un conjunto nodos o estados y los arcos con su valor con las contribuciones directas; podemos notar que existe la particularidad que el estado 3 está conectado tanto al estado final como a un estado intermedio, este estado 3 en consecuencia estará presente en al menos 2 etapas, si hiciéramos un corte podríamos observar que nuestro problema puede segmentarse en 4 etapas, entonces:

La etapa 4 es la última etapa por recorrer, y el único estado siguiente es 7 y no existe un g5 por lo cual el esfuerzo o tiempo será solo la contribución directa del arco:

 

pd_9

La etapa 3, ahora son dos etapas que debemos de considerar, en este caso en particular, recuerda tomar en cuenta todos los estados previos que te permiten llegar a los estados futuros, para ello observemos el estado 4 que si bien se encuentra en un estado final para la etapa también es parte del estado actual ya que conecta con otros estados finales, se puede observar que por ejemplo en el estado 2 que va hacia el estado 6 y 4 la contribución inmediata de ir de 2 a 6 más el g4(6)  máximo que hasta el momento es 1, igualmente ocurre de 2 a 4, de entre ellos dos elegimos el máximo, ¿Por qué el máximo?, pues porqué estamos buscando la ruta crítica, la ruta crítica está representada por la ruta más larga que me permita ir de 1 a 7.

pd_10

La etapa 2, correspondería ubicar en los estados finales a 1, 2, 4 y 5, pero no tiene sentido colocar a 1 ya que no existe un estado previo para él, entonces solo colocaremos a 2, 4 y 5, hacemos la misma lógica que ya está sustentada en la relación recursiva que aplica para este caso:

pd_11

La etapa 1 y última etapa se consideran las 3 etapas anteriores, entonces tenemos:

pd_12

Hecho todo ello, ¿Cómo hallamos la ruta crítica?, debemos de seleccionar todos los valores máximos, si existe un estado (nodo) que se encuentre en más de una etapa debemos de seleccionar en cual de ellos es el mayor por ejemplo, revisemos la ruta de 1 a 2 y 1 a 3 aparentemente sea de 1 a 3 la ruta más larga; sin embargo, la ruta de 1 a 2 en la etapa 2  es mayor que la ruta de 1 a 3, es por ello que tomamos dicha ruta, luego, en la etapa 2 se obtuvo ese valor del estado 2 ya que provenía del estado 6 y de 6 a 7, entonces nuestra ruta crítica será:

1->2->6->7 longitud de 13

 

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s