Programación lineal Estoica

Universidad Católica Andrés Bello

Facultad de Ingeniería 

Ingeniería Industrial - Ingeniería Informática

Programación Lineal

PROYECTO 1

Profesor:

José Luis Quintero                                              

Caracas, 27 de Octubre del 2020

La Programación Estocástica reúne aquellos modelos de optimización en donde uno o más parámetros del problema son modelados a través de variables aleatorias. Una manera de enfrentar esta aleatoriedad consiste en reemplazar los parámetros aleatorios por su valor esperado, lo cual lleva a resolver un problema determinístico de programación matemática, los cuales son de especial interés en cursos introductorios de Investigación de Operaciones y donde la variabilidad inherente a los parámetros se aborda a través del Análisis de Sensibilidad o Postoptimal.

No obstante, la solución obtenida de esta manera puede no ser representativa de la realidad, al no considerar la dispersión de los valores que toman los parámetros en torno al valor esperado, lo cual entre otras cosas puede invalidar su implementación al resultar finalmente escenarios muy diferentes del promedio.

[pic 1]

En general, en los problemas de optimización lineal estocástica se modelizan las incertidumbres como variables aleatorias, asignando adecuadamente las variables y los parámetros, y calculando las distribuciones de probabilidad de dichas variables aleatorias para obtener respuestas sobre el comportamiento de las inversiones. Finalmente, la representación se hace mediante programas lineales matemáticos.

La primera aplicación de la programación lineal estocástica para la gestión de una cartera de inversiones fue introducida por (Beale y Dantzig, 1955). El principal problema al que se enfrentaron fue que la dimensión de los sistemas estocásticos obtenidos era enorme, con una matriz de coeficientes muy grande, y de ahí surgió la necesidad de descomponer el problema en sub-problemas. Se originaron así las técnicas de descomposición (Dantzig, G. B. and Wolf, 1960), (Dantzig, VanSlyke, 1964), (Avriel y Williams, 1969), (Huang, Ertinsky y Ziemba, 1975), también denominadas de optimización matemática a gran escala.

A pesar de que este problema fue introducido y estudiado hace muchos años, debido a las limitaciones computacionales en aquel momento no se le dio mucha importancia a la programación lineal estocástica. La resolución de estos problemas solo fue posible gracias a los avances posteriores de la tecnología de los ordenadores. La posibilidad de resolver computacionalmente los problemas de optimización de tamaño muy grande devolvió el interés en la programación estocástica y provocó nuevos avances en su modelización matemática (Ermoliev, Yu. M. and A. I. Yastremki, 1979)

Métodos de solución de la Programación Lineal Estocástica

En la Programación Lineal Estocástica se consideran tres métodos principales para la formulación de los problemas de optimización, que se denominan método “Aquí y Ahora” o “Here and Now”, método “Esperar y Ver” o “Wait and See”, y el método del Valor Esperado o “Expected Value”.

• “Wait and See”​: En este método se asume que se tiene toda la información completa y además perfecta sobre las realizaciones de las variables aleatorias, es decir, que no existe incertidumbre, entonces la solución puede encontrarse calculando los valores óptimos de las funciones objetivo para cada posible realización de dichas variables. Por ejemplo, consideremos el siguiente problema estocástico de minimización:

[pic 2]

Sujeto a [pic 3]

Resolveremos el problema calculando los valores óptimos de la función objetivo para cada posible realización del parámetro aleatorio ​.​ El valor esperado de la solución aplicando el método “Wait and See” será ​​ , definido por:[pic 4][pic 5]

[pic 6]

• “Here and Now”: En este método se asume que no se conoce toda la información y que es necesario tomar una decisión antes de conocer las realizaciones de ​, y se trata de encontrar las funciones de distribución de las variables aleatorias, así como estimar los valores de algunos parámetros (como la media, varianza, etc.), antes que se realicen las variables aleatorias, con el objetivo de encontrar la mejor solución óptima posible del problema. Una vez estimados los valores de los parámetros tendremos la opción de saber cuál es la mejor decisión, que se denota por ​Z​HN[pic 7]

Ejemplo: Asumimos que alguien tiene la competencia de tomar las decisiones y denotemos estas decisiones por ​ y los valores de la función objetivo por ,​ así estamos en condiciones de calcular el valor esperado de la solución óptima, del método “Here and Now”, también llamado problema de recurso. Este tiene la siguiente formulación matemática.[pic 8][pic 9]

[pic 10]

• “Expected Value”: En esta técnica todas las variables aleatorias son reemplazadas por sus valores esperados, por lo que los problemas de programación estocástica se reducen a problemas de programación lineal. Denotaremos la solución por ​ZEV​ ​(Zenios, Ziemba ,2005). Y se define con la siguiente fórmula.

[pic 11]

A continuación un ejemplo completo en donde estudiaremos ambos modelos de la programación estocástica

Un granjero cultiva maíz, trigo y remolacha en sus 500 hectáreas de tierra. Durante el invierno, debe decidir cuanta tierra asignar a cada cultivo. Este sabe que necesita, al menos, 200 toneladas de trigo y 240 de maíz para alimentar su ganado. Estas cantidades pueden ser cultivadas en la granja o compradas a un mayorista. Los excesos de producción se venden al precio de 170 y 150 dólares por tonelada de trigo y maíz, respectivamente. Los precios de compra son 238 y 210 dólares por tonelada, respectivamente. La remolacha se vende a 36 dólares por tonelada, aunque cualquier producción mayor a las 6000 toneladas será vendida por 10 dólares. Por su experiencia, sabe que la producción de cada cultivo por hectárea es de 2.5, 3 y 20 toneladas para el trigo, maíz y remolacha, respectivamente. Sabiendo que el coste por hectárea es de 150, 230 y 260 dólares por trigo, maíz y remolacha, respectivamente, nos interesa planificar la asignación a cada cultivo para obtener el mayor beneficio posible.

...