Procesos Estocásticos (I)

Un proceso estocástico se define sencillamente como una colección indexada de variables aleatorias {Xt}, en donde el índice t toma valores de un conjunto T dado. Con frecuencia T se toma como el conjunto de enteros no negativos y Xt representa una característica de interés medible en el tiempo t. Por ejemplo, el proceso estocástico, X1, X2, X3,....., puede representar la colección de niveles de inventario semanales (o mensuales) de un producto dado, o puede representar la colección de demandas semanales (o mensuales) de este producto.

Existen muchos procesos estocásticos interesantes. Un estudio del comportamiento de un sistema en operación durante algún periodo suele llevar al análisis de un proceso estocástico con la siguiente estructura. En puntos específicos del tiempo t etiquetados 0,1,......., el sistema se encuentra exactamente en una de un número finito de categorías o estados mutuamente excluyentes y exhaustivos, etiquetados 0,1,....,M. Los puntos en el tiempo pueden encontrarse a intervalos iguales o el espacio entre ellos pueden depender del comportamiento general del sistema físico en el que se encuentra sumergido el proceso estocástico, por ejemplo, el tiempo entre ocurrencias de algún fenómeno de interés. Aunque los estados pueden constituir una caracterización tanto cualitativa como cuantitativa del sistema, no hya pérdida de generalidad con las etiquetas numéricas 0,1,....,M, que se usarán en adelante para denotar los estados posibles del sistema. Así, la representación matemática del sistema físico es la de un proceso estocástico {Xt}, en donde las variables aleatorias se observan en t = 0, 1, 2,......, y en donde cada variable aleatoria puede tomar el valor de cualquiera de los (M + 1) enteros 0, 1,.....,M. EStos enteros son una caracterización de los (M + 1) estados del proceso. Debe hacerse notar que a cada estado que alcanza el proceso estocástico se le da una etiqueta que denota el estado físico del sistema. Es sólo por conveniencia en la notación que este conjunto se etiqueta 0,1,...., M.

Cadenas de Markov

En los problemas de toma de decisiones, con frecuencia surge la necesidad de tomar decisiones basadas en fenómenos que tienen incertidumbre asociado a ellos. Esta incertidumbre proviene de la variación inherente a las fuentes de esa variación que eluden el control o proviene de la inconsistencia de los fenómenos naturales. En lugar de manejar esta variabilidad como cualitativa, puede incorporarse al modelo matemático y manejarse en forma cuantitativa. Por lo general, este tratamiento se puede lograr si el fenómeno natural muestra un cierto grado de regularidad, de manera que sea posible describir la variación mediante un modelo probabílistico. Se supone aquí que el lector tiene conocimientos básicos sobre teoría de probabilidad. Las secciones que se presentan a continuación se refieren a los tipos especiales de modelos de probabilidad.

Conclusiones Programación no lineal (II)

En los últimos años se ha tenido un gran interés en el desarrollo de paquetes de computadora (software) confiables y de alta calidad para el uso general en la aplicación del mejor de estos algoritmos por computadora. Por ejemplo, en el Systems Optimization Laboratory de la University of Stanford se cuenta con varios paquetes poderosos para computadora, como el MINOS. Estos paquetes son de uso común en otros centros para la solución de problemas de tipo que se presentó en este capítulo (al igual que de problemas de programación lineal). Las considerables mejoras que se han logrado, tanto en los algoritmos como en el software, permiten hoy día que algunos problemas grandes estén dentro de la factibilidad computacional.

Con el rápido crecimiento actual en el uso y potencial de las computadoras personales, se está logrando un buen progreso en el desarrollo de paquetes de programación no lineal para microcomputadoras. Por ejemplo, el paquete GAMS/MINOS (una combinación de dos programas bien conocidos para computadora grande) se encuentra ahora disponible para la computadora personal IBM. Otro paquete importante llamado GINO se desarrollo específicamente para microcomputadora.

La investigación en el campo de la programación no lineal sigue muy activa.

Conclusiones Programación no lineal (I)

Los problemas prácticos de optimización con frecuencia incluyen un comportamiento no lineal que debe tomarse en cuenta. A veces es posible reformular las no linealidades para que se ajusten al formato de programación lineal, como se puede hacer con los problemas de programación separable. Sin embargo, es frecuente la necesidad de usar una formulación de programación no lineal.

Al contrario del caso del método símplex para programación lineal, no existe un algoritmo eficiente que se pueda utilizar para resolver todos los problema de programación no lineal. De hecho, algunso de estos problemas no se pueden resolver satisfactoriamente por ningún método, pero se han hecho grandes progresos en ciertas clases importantes de problemas que incluyen programación cuadrática, programación convexa y algunos tipos especiales de programación no convexa, Se dispone de una gran variedad de algoritmos que casi siempre tienen un buen desempeño en estos casos. Algunos de estos algoritmos incorporan procedimientos de alta eficiencia par la optimización no restringida en una parte de cada iteración y algunos emplean una sucesión de aproximaciones lineales o cuadráticas al problema original.

Resumen de la técnica secuencial de minimización no restringida - Ejemplo

Para ilustrar la técnica secuencial considérese el siguiente problema de dos variables

Resumen de la técnica secuencial de minimización no restringida - Paso iterativo y regla de detención (III)

La técnica secuencial de minimización no restringida se ha usado ampliamente por su simplicidad y versatilidad. Sin embargo, quienes se dedican al análisis numérico han encontrado que es bastante propenso a la inestabilidad numérica, así que se aconseja tomar precauciones extremas. Para mayor información sobre este tema, igual que sobre análisis similares para otros algoritmos, véase la referencia 7.

Resumen de la técnica secuencial de minimización no restringida - Paso iterativo y regla de detención (II)

Cuando no se satisfacen las suposiciones de programación convexa, este algoritmo debe repetirse varias veces a partir de las soluciones prueba distintas. El mejor de los máximos locales que se obtiene para el problema original es que debe usarse como la mejor aproximación disponible de un máximo global.


Por último, obsérvese que la técnica secuencial de minimización no restringida se puede extender de manera sencilla para manejar restricciones de igualdad gi(x) = bi. Una manera estándar es la siguiente. Para cada restricción de igualdad,

Resumen de la técnica secuencial de minimización no restringida - Paso iterativo y regla de detención (I)

del problema original., De otra manera, se reestablece k = k + 1 y r = θr y se regresa al paso iterativo.

Resumen de la técnica secuencial de minimización no restringida - Paso inicial

Programación no convexa - Técnica secuencial de miniización no restringida (V)

Por desgracia, no se puede dar una garantía para el error máximo cuando se trata de problemas de programación no convexa. Sin embargo, todavía es probable que rB(x) exceda el error real cuando x y x* son máximos locales correspondientes de P(x, r) y del problema original, respectivamente.