Modelos

Programaci´n Estoc´stica o a
E. Cerd´a , J. Morenob a
a

Departamento An´lisis Econ´mico. UCM. a o
b

Departamento de Estad´ ıstica. UCM.

1

Introducci´n o

Tal como su nombre indica, la Programaci´n Estoc´stica trata problemas de Proo a gramaci´n Matem´tica en cuya formulaci´n aparece alg´n elemento estoc´stico. o a o u a Por tanto, mientras que en un problema determin´ ıstico deProgramaci´n Mao tem´tica, ya sea de Programaci´n Lineal, Programaci´n No Lineal, Programaci´n a o o o Entera, Programaci´n Mixta Lineal Entera o Programaci´n Mixta No Lineal Eno o tera, todos los datos (coeficientes) que aparecen en su formulaci´n son n´meros o u conocidos, en Programaci´n Estoc´stica dichos datos (o al menos alguno de ellos) o a son desconocidos, aunque para ellos se conoce o sepuede estimar su distribuci´n o de probabilidad. Para precisar m´s, veamos las dos definiciones que propone a Prekopa [29]: Primera definici´n: “Programaci´n Estoc´stica es la ciencia que ofrece soluo o a ciones para problemas formulados en conexi´n con sistemas estoc´sticos, en los o a que el problema num´rico resultante a resolver es un problema de Programaci´n e o Matem´tica de tama˜o no trivial“.a n Segunda definici´n: “La Programaci´n Estoc´stica trata problemas de Prograo o a maci´n Matem´tica en los que algunos de los par´metros son variables aleatorias, o a a bien estudiando las propiedades estad´ ısticas del valor optimo aleatorio o de otras ´ variables aleatorias presentes en el problema o bien reformulando el problema en otro de decisi´n en el que se tiene en cuenta la distribuci´nde probabilidad o o conjunta de los par´metros aleatorios“. a Los problemas resultantes de ambas definiciones son llamados problemas de Programaci´n Estoc´stica. o a Rect@ Monogr´fico 2 (2004) a

4

Programaci´n Estoc´stica o a

La aleatoriedad en coeficientes en unos casos se deber´ a la falta de fiabilidad a en los datos recogidos, en otros casos a errores de medida, en otros a eventosfuturos a´n no conocidos, etc. u Tal como indica Dantzig [11], la Programaci´n Estoc´stica comenz´ en 1955 o a o con los trabajos de Dantzig [10] y Beale [2]. y ya en la misma d´cada alcanz´ e o con Markowitz [23] una aplicaci´n muy destacada al problema de selecci´n de o o carteras que le llevar´ a la consecuci´n del Premio N´bel. En [34] se recogen ıa o o unas 800 referencias sobre trabajospublicados entre 1955 y 1975, clasificadas en funci´n de su contenido. o En 1974 se celebr´ en Oxford (Inglaterra) la primera conferencia internacioo nal en Programaci´n Estoc´stica, organizada por Michael Dempster. En 1981 o a se celebr´ en K¨szeg (Hungr´ la segunda conferencia, organizada por Andra o o ıa) Prekopa. En dicho encuentro se puso en marcha el Committee on Stochastic Programming (COSP), comouna rama de la Mathematical Programming Society. Dicho comit´ ha sido el responsable de organizar los sucesivas conferencias que e o ın se han ido celebrando. La novena conferencia internacional se celebr´ en Berl´ (Alemania) en 2001 y la d´cima se celebrar´ los d´ 9 a 12 de Octubre de 2004 e a ıas en Tucson, Arizona (USA). El COSP ha puesto en funcionamiento la p´gina web http// stoprog.org en la aque se puede encontrar mucha informaci´n y documentaci´n sobre Programaci´n o o o Estoc´stica. a

2

Definiciones b´sicas a
˜ m´ g0 x, ξ , ın ˜
x

Se considera el siguiente problema de Programaci´n Estoc´stica: o a

sujeto a : ˜ gi x, ξ ≤ 0, i = 1, 2, ..., m, ˜ x ∈ D,

(1.1)

˜ donde el conjunto D ⊂ Rn , ξ es un vector aleatorio definido sobre un conjunto s a E ⊂ R .Suponemos queest´n dados una familia de eventos F formada por subconjuntos de E y una distribuci´n de probabilidad P definida sobre F Por o tanto, para cada A ⊂ E, es A ∈ F, y la probabilidad P (A) es conocida. Adem´s a suponemos que las funciones gi (x, ·) : E → R, ∀x, i son variables aleatorias y ˜ que la distribuci´n de probabilidad P es independiente del vector de variables de o decisi´n x. o Obs´rvese que en...