Solución Ejemplo prototipo (II)

En el problema de la diligencia, se comienza con el problema sencillo en el que el agente casi ha llegado al final de su viaje y sólo tiene una etapa más (una jornada en la diligencia) por recorrer. La solución óptima obvia para este problema reducido es ir del estado actual (el que sea en el que se encuentre) a su destino final ( estado J). En cada una de las iteraciones siguientes, el problema se agranda aumentando de uno en uno el número de etapas que le quedan por recorrer para completar el viaje. En cada problema aumentado se puede encontrar la solución óptima del lugar al que debe dirigirse desde cada estado posible tomando en cuenta los resultados obtenidos en la iteración anterior. A continuación se describen los detalles de este procedimiento.

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

DEbido a la estructura probabílistica, la relación entre fn(sn, xn) y f*s(sn+1) necesariamente es más complicada que apra el caso deterministico. 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.

Solución Ejemplo prototipo (I)

Obsérvese primero que el procedimiento poco inteligente de elegir la ruta más barata en cada etapa sucesiva no conduce a una decisión óptima global. Al seguir esta estrategia se obtiene la ruta A → B → F → I → J, con un costo total de 13. Pero un pequeño sacrificio en una etapa puede permitir mayores ahorros más adelante. Por ejemplo, A→ D→ F es en total más barato que A →B→ F.

Un enfoque posible para resolver este problema es el de prueba y error. Sin embargo, el número de rutas posibles es grande (18) y el cálculo del costo total para cada ruta no es una tarea atractiva.

Por fortuna, la programación dinámica proporciona una solución con mucho menos esfuerzo que la enumeración exhaustiva. (El ahorro computacional es enorme cuando se trata de versiones más grandes de este problema). La programación dinámica comienza con una pequeña porción del problema original y encuentra la solución óptima actual a partir de la que le precede, hasta resolver el problema original completo.

Ejemplo prototipo

El problema de la diligencia fue elaborado especialmente para ilustrar las características e introducir la terminología de la programación dinámica. Trata sobre una cazafortunas mítico de Missouri que decide ir al oeste a unirse a la fiebre del oreo en California a mediados del siglo XIX. Tiene que hacer el viaje en diligencia a través de territorios sin ley cuando existían serios peligros de ser atacado por merodeadores. Aun cuando su punto de partida y su destino eran fijos, tenía muchas opciones en cuanto a qué estados (o territorios que más tarde se convirtieron en estados) debía elegir como puntos intermedios. En la figura 11.1 se muestran las rutas posibles, en donde cada estado está representado por un círculo numerado. Como se puede observar, se requerían cuatro etapas (jornadas en diligencia) para viajar desde su punto de partida en el estado A (Missouri) a su destino en el estado J (California).

Este cazafortunas era un hombre prudente que estaba preocupado por su seguridad. Después de reflexionar un poco se le ocurrió una manera bastante ingeniosa para determinar la ruta más segura. Se ofrecían pólizas de seguros de vida a los pasajeros. Como el costo de la póliza para cualquier jornada de la diligencia estaba basado en una evaluación cuidadosa de la seguridad del recorrido, la ruta más segura debía ser aquella que tuviera el costo total más barato.

El costo de la póliza estándar para el viaje en diligencia, del estado i al estado j, se denotará por cij,  y es

La atención se centrará sobre la pregunta Cuál es la ruta que minimiza el costo total de la póliza?

Programación dinámica

La programación dinámica es una técnica matemática útil en la toma de una serie de decisiones interrelacionados. Proporciona un procedimiento sistemático para determinar la combinación de decisiones que maximiza la efectividad total.

En contraste con la programación lineal, no cuenta con una formulación matemática estándar para "el" problema de programación dinámica, sino que se trata de un enfoque de tipo general para la solución de problemas y las ecuaciones específicas que se usan se deben desarrollar para que representen cada situación individual. Entonces, se necesita un cierto grado de creatividad y un buen conocimiento de la estructura general de los problemas de programación dinámica para reconocer cuándo un problema se puede resolver por medio de estos procedimientos y cómo esto se puede llevar a cabo. Estas habilidades se pueden desarrollar mejor mediante la exposición de una gran variedad de aplicaciones de la programación  dinámica y con el análisis detallado de las características comunes a estas situaciones. Con este fin se presentarán muchos ejemplos explicativos.

Conclusiones PERT y CPM (II)

Al mismo tiempo que todos estos modelos se ocupan de optimizar la operación de una red existente, el problema del árbol de mínima expansión es un ejemplo sobresaliente de un modelo para optimizar el diseño de una nueva red.

Este capítulo apenas ha tocado la superficie de lo que hasta la fecha se ha desarrollado en el campo de la metodología de redes. Por su naturaleza combinatoria, con frecuencia los problemas de redes son difíciles de resolver, pero se han hecho grandes avances en el desarrollo de técnicas poderosas de modelado y de metodologías de solución que incluso amplían el panorama de nuevas e importantes aplicaciones. De hecho, los nuevos algoritmos han permitido resolver aplicaciones. De hecho, los nuevos algoritmos han permitido resolver con éxito algunos problemas complejos de redes de gran tamaño.

La técnica de redes más utilizada ha sido la de sistemas tipo PERT para la planeación y el control de proyectos. Ha resultado una herramienta valiosa  en la organización de la planeación al probar diferentes opciones, revelar las dimensiones globales y los detalles del plan del proyecto, establecer las responsabilidades gerenciales bien entendidas e identificar en forma realista lo que se puede esperar del proyecto. También establece las bases para que la gerencia tome acciones anticipadas contra posibles problemas durante el desarrollo del proyecto. Aunque no es una panacea, ha sido una gran ayuda para el administrador en numerosas ocasiones.

Conclusiones PERT y CPM (I)

Las redes de ciertos tipos surgen en una amplia variedad de contextos. Las representaciones de redes son muy útiles para visualizar las relaciones y conexiones entre las componentes del sistema. Con frecuencia debe mandarse un flujo de algún tipo a través de la red y es necesario tomar una decisión sobre la mejor manera de hacerlo. En este capítulo se introdujeron dos tipos de modelos y algoritmos de optimización de redes que constituyen una herramienta poderosa para tomar tales decisiones.

El problema del flujo de costo mínimo juega un papel central entre estos nuevos modelos de optimización de redes, tanto por ser una aplicación tan extensa como porque se pueden resolver con gran eficiencia por el método símplex de redes. Dos de sus casos especiales, incluidos en este capítulo, el problema de la ruta más corta y el problema del flujo máximo, también son modelos importantes de optimización de redes, al igual que los otros tres casos especiales presentados en el capítulo 7 (el problema de transporte, el problema de trasbordo y el problema de asignación).