Embed Size (px)
Citation preview
Universidad Nacional de Colombia
INTRODUCCIÓN A LA INVESTIGACION DE OPERACIONES ESTOCÁSTICAS MODELOS PROBABILÍSTICOS
Jorge Eduardo Ortiz Triviño 08 de Marzo de 2012
2
3
Tabla de Contenido
TABLA DE CONTENIDO .............................................................................................................. 3
I. LISTA DE FIGURAS .............................................................................................................. 8
II. LISTA DE TABLAS ................................................................................................................ 9
III. PREFACIO ....................................................................................................................... 10
OBJETIVOS ............................................................................................................................. 12
COMENTARIOS SOBRE LOS EJERCICIOS .................................................................................... 12
1 INTRODUCCIÓN ................................................................................................................ 15
2 COMPENDIO DE TEORÍA DE PROBABILIDADES.................................................................... 15
2.1 INTRODUCCIÓN .............................................................................................................. 15
2.2 ESPACIOS DE PROBABILIDAD .......................................................................................... 15
2.3 VECTORES ALEATORIOS Y FUNCIONES DE DISTRIBUCIÓN CONJUNTAS .............................. 15
2.3.1 INTRODUCCIÓN ......................................................................................................................... 15
2.3.2 DEFINICIONES ........................................................................................................................... 15
2.4 FUNCIONES DE DENSIDAD CONJUNTAS ........................................................................... 15
2.4.1 VECTORES ALEATORIOS DISCRETOS................................................................................................ 15
2.4.2 VECTORES ALEATORIOS CONTINUOS.............................................................................................. 15
2.4.3 OTRAS CLASES DE VECTORES ALEATORIOS ....................................................................................... 16
2.5 DISTRIBUCIONES CONDICIONALES E INDEPENDENCIA ESTOCÁSTICA ................................ 16
2.5.1 VECTORES ALEATORIOS DISCRETOS ............................................................................................... 16
2.5.2 VECTORES ALEATORIOS CONTINUOS ............................................................................................. 16
2.5.3 INDEPENDENCIA ........................................................................................................................ 16
2.6 ESPERANZA MATEMÁTICA Y MOMENTOS ....................................................................... 16
2.6.1 DEFINICIÓN .............................................................................................................................. 17
2.6.2 VECTOR DE MEDIAS ................................................................................................................... 17
2.6.3 COVARIANZA Y COEFICIENTE DE CORRELACIÓN ............................................................................... 17
2.6.4 VALOR ESPERADO DE FUNCIONES DE VARIABLES ALEATORIAS ........................................................... 17
2.6.5 MOMENTOS CONJUNTOS Y FUNCIONES GENERADORAS DE MOMENTOS ............................................. 17
2.6.6 ESPERANZA E INDEPENDENCIA ..................................................................................................... 17
2.7 FAMILIA DE GASUSS MULTIDIMENSIONAL ....................................................................... 17
4
2.7.1 DENSIDAD CONJUNTA ................................................................................................................ 17
2.7.2 FUNCIÓN GENERADORA DE MOMENTOS Y MOMENTOS ................................................................... 17
2.7.3 DENSIDADES MARGINALES Y CONDICIONALES................................................................................. 17
2.8 FAMILIAS DE DISTRIBUCIONES UNIPARAMÉTRICAS ......................................................... 17
2.8.1 INTRODUCCIÓN ......................................................................................................................... 17
2.8.2 FAMILIAS DE DISTRIBUCIONES DISCRETAS ...................................................................................... 18
2.8.3 FAMILIAS DE DISTRIBUCIONES CONTINUAS ..................................................................................... 18
2.8.4 RELACIONES ENTRE FAMILIAS ............................................................................................... 18
2.9 EJERCICIOS ..................................................................................................................... 19
2.10 RESUMEN DEL CAPÍTULO .............................................................................................. 19
3 TEORÍA DE LA DECISIÓN .................................................................................................... 20
3.1 INTRODUCCIÓN .............................................................................................................. 20
3.2 LOS ELEMENTOS EN UN PROBLEMA DE DECISIÓN ............................................................ 20
3.2.1 DECISOR ................................................................................................................................... 21
3.2.2 ALTERNATIVAS .......................................................................................................................... 21
3.2.3 ESTADOS DE LA NATURALEZA ....................................................................................................... 21
3.2.4 EFECTOS O CONSECUENCIAS DE LA DECISIÓN ................................................................................... 22
3.2.5 ESTRUCTURA DE PREFERENCIAS DEL DECISOR .................................................................................. 22
3.3 MODELOS DE DECISIÓN .................................................................................................. 23
3.3.1 PROYECTOS Y DECISIONES ........................................................................................................... 23
3.3.2 DECISIONES BAJO CERTEZA .......................................................................................................... 24
3.3.3 DECISIONES BAJO RIESGO: ESPERANZA MATEMÁTICA CRITERIO RACIONAL. ......................................... 24
3.3.4 DECISIONES BAJO INCERTIDUMBRE ............................................................................................... 27
3.4 ARBOLES DE DECISIÓN .................................................................................................... 36
3.5 VALOR ESPERADO DE LA INFORMACIÓN PERFECTA .......................................................... 40
3.5.1 REIP: RESULTADO ESPERADO CON INFORMACIÓN PERFECTA ............................................................. 41
3.5.2 RER: RESULTADO ESPERADO EN RIESGO ......................................................................................... 41
3.5.3 VIP: VALOR DE LA INFORMACIÓN PERFECTA ................................................................................... 41
3.5.4 CIP: COSTO DE LA INFORMACIÓN PERFECTA ................................................................................... 41
3.6 TEORÍA DE LA UTILIDAD .................................................................................................. 43
3.6.1 INTRODUCCIÓN ......................................................................................................................... 43
3.6.2 FUNCIONES DE UTILIDAD............................................................................................................. 43
3.6.3 CURVAS TÍPICAS DE UTILIDAD ...................................................................................................... 43
3.7 DECISIONES MULTIOBJETIVO .......................................................................................... 43
3.7.1 INTRODUCCIÓN ......................................................................................................................... 43
3.7.2 SOLUCIONES NO DOMINADAS ...................................................................................................... 43
3.7.3 INCLUSIÓN DE LA ESTRUCTURA DE PREFERENCIAS DE DECISOR ........................................................... 43
3.7.4 MÉTODO DE LAS RESTRICCIONES .................................................................................................. 43
3.7.5 MÉTODO DE LAS PONDERACIONES ............................................................................................... 43
5
3.8 MÚLTIPLES ACTORES DECISORES ..................................................................................... 43
4 PROGRAMACIÓN DINÁMICA ............................................................................................. 44
4.1 INTRODUCCIÓN .............................................................................................................. 44
4.2 PROGRAMACIÓN DINÁMICA DETERMINÍSTICA ................................................................ 44
4.2.1 INTRODUCCIÓN ......................................................................................................................... 44
4.2.2 DECISOR ................................................................................................................................... 45
4.2.3 ALTERNATIVAS Y VARIABLES DE ESTADO Y DE DECISIÓN ................................................................... 45
4.2.4 CRITERIO DE EVALUACIÓN Y FUNCIÓN DE RETORNO GLOBAL ............................................................. 46
4.2.5 SOLUCIÓN Y CRITERIO DE OPTIMALIDAD DE BELLMAN ...................................................................... 46
4.2.6 EJEMPLOS................................................................................................................................. 47
4.3 PROGRAMACIÓN DINÁMICA ESTOCÁSTICA ..................................................................... 59
4.4 APLICACIONES. ............................................................................................................... 60
4.5 EJERCICIOS ..................................................................................................................... 61
4.6 RESUMEN DEL CAPÍTULO ................................................................................................ 61
5 PROCESOS ESTOCÁSTICOS ................................................................................................. 62
5.1 INTRODUCCIÓN .............................................................................................................. 62
5.2 DEFINICIÓN .................................................................................................................... 62
5.3 LAS FUNCIONES DE AUTOCOVARIANZA Y AUTOCORRELACIÓN ......................................... 67
5.4 FUNCION DE AUTOCORRELACIÓN PARCIAL ...................................................................... 69
5.5 PROCESOS CON RUIDO BLANCO ...................................................................................... 70
5.6 CADENAS DE MARKOV EN TIEMPO DISCRETO .................................................................. 70
EJEMPLO1.1.1 ........................................................................................................................... 71
EJEMPLO1.1.2 ........................................................................................................................... 71
5.7 ECUACIONES DE CHAPMAN–KOLMOGOROV ................................................................... 72
5.7.1 INTRODUCCIÓN ......................................................................................................................... 75
5.7.2 ECUACIONES DE CHAPMAN–KOLMOGOROV ................................................................................... 75
5.7.3 CLASIFICACIÓN DE LOS ESTADOS ................................................................................................... 75
5.8 CADENAS DE MARKOV DE TIEMPO CONTINUO ................................................................ 75
5.8.1 INTRODUCCIÓN ......................................................................................................................... 75
5.8.2 DEFINICIÓN .............................................................................................................................. 75
5.8.3 PROCESOS DE NACIMIENTO Y MUERTE .......................................................................................... 75
5.8.4 FUNCIÓN DE TRANSICIÓN DE PROBABILIDAD .................................................................................. 75
5.8.5 REVERSIBILIDAD ......................................................................................................................... 76
5.9 DISTRIBUCIÓN EXPONENCIAL Y EL PROCESO DE POISSON ................................................ 76
5.9.1 INTRODUCCIÓN ......................................................................................................................... 76
5.9.2 DEFINICIÓN DE PROCESO DE POISSON ........................................................................................... 76
5.9.3 DISTRIBUCIONES DE LOS TIEMPOS ENTRE LLEGADAS Y DE ESPERAS ..................................................... 76
6
5.9.4 PROCESO DE POISSON NO HOMOGÉNEO ........................................................................................ 76
5.10 **TEORÍA DE RENOVACIÓN ........................................................................................... 76
5.11 EJERCICIOS ................................................................................................................... 76
5.12 RESUMEN DEL CAPÍTULO .............................................................................................. 76
6 TEORÍA DE COLAS .............................................................................................................. 76
6.1 INTRODUCCIÓN .............................................................................................................. 76
6.2 ESTRUCTURA GENERAL DE UN SISTEMA DE LÍNEAS DE ESPERA ......................................... 77
6.3 NOTACIÓN DE KENDALL .................................................................................................. 77
6.4 LEY DE LITTLE .................................................................................................................. 77
6.5 TEOREMA DE BURKE ....................................................................................................... 77
6.6 MODELO / /1M M
EN DETALLE .................................................................................. 77
6.7 ***OTROS MODELOS...................................................................................................... 77
6.8 EJERCICIOS ..................................................................................................................... 77
6.9 RESUMEN DEL CAPÍTULO ................................................................................................ 77
7 TEORÍA DE INVENTARIOS .................................................................................................. 77
7.1 INTRODUCCIÓN .............................................................................................................. 77
7.2 MODELOS DE INVENTARIOS DETERMINÍSTICOS ............................................................... 78
7.3 MODELOS DE INVENTARIOS ESTOCÁSTCOS ..................................................................... 78
7.4 APLICACIONES ................................................................................................................ 78
7.5 EJERCICIOS ..................................................................................................................... 78
7.6 RESUMEN DEL CAPÍTULO ................................................................................................ 78
8 TEORÍA DE JUEGOS ............................................................................................................ 78
8.1 INTRODUCCIÓN .............................................................................................................. 78
8.2 JUEGOS COOPERATIVOS ................................................................................................. 78
8.3 JUEGOS NO COOPERATIVOS............................................................................................ 79
8.4 EQUILIBRIOS .................................................................................................................. 79
8.5 ANÁLISIS DE CONFLICTOS ............................................................................................... 79
8.6 EJERCICIOS ..................................................................................................................... 79
8.7 RESUMEN DEL CAPÍTULO ................................................................................................ 79
9 EL FUTURO DE LA INVESTIGACIÓN OPERACIONAL ESTOCÁSTICA ......................................... 79
IV. REFERENCIAS BIBLIOGRÁFICAS ........................................................................................ 79
7
V. ÍNDICE ............................................................................................................................. 79
8
i. LISTA DE FIGURAS
9
ii. LISTA DE TABLAS
10
iii. PREFACIO
We all learn best de things that we have discovered ourselves.
Donald Knuth
Dentro de la formación integral que las instituciones de educación superior propenden por sus estudiantes, la capacitación en ciencias básicas es muy importante para un ingeniero industrial. En particular se considera muy importante el manejo formal (y no solamente intuitivo) de las ideas de azar y de aleatoriedad. Pero ¿No es por definición el azar la antítesis de orden, de teoría? ¿Cómo formular una teoría sobre esa base? ¿Tendrá sentido? Y si lo tiene ¿Realmente es aplicable en ingeniería de la computación?
Como se sabe, una teoría matemática está constituida, principalmente, por axiomas, definiciones, lemas, teoremas y la deducción o formulación de leyes generales que pueden deducirse a partir de todos esos conceptos. Los axiomas apelan a la intuición y subjetividad que, aparentemente, no tiene discusión, es decir son afirmaciones que se aceptan, sin necesidad de demostración, como universalmente válidos en un campo específico.
Los axiomas se constituyen en los ladrillos que permiten construir definiciones (usualmente premeditadas para que la teoría sea coherente) junto con otras definiciones de la misma teoría. Las definiciones clarifican conceptos y tienden a establecer notaciones y acuerdos generales sobre alguna idea en particular. Por su parte los lemas y teoremas (a diferencia de las conjeturas) se distinguen por ser afirmaciones generales que pueden deducirse a partir de una serie de premisas y supuestos con la característica de que cuentan con una demostración formal de la conclusión que presentan. Se suele emplear la palabra lema cada vez que su resultado (aparentemente) no tiene una aplicación práctica directa sino que sirve de puente para establecer otros resultados de otros teoremas. Los teoremas frecuentemente tienen aplicación en la vida práctica y se les suele dar el nombre de sus autores cuando el resultado tiene un impacto significativo en ciencia y en tecnología.
Las leyes generales hacen uso de los teoremas, lemas y definiciones y axiomas para describir resultados de aplicación general bajo un universo particular que se rige por los teoremas de esa teoría. Es frecuente que, en
11
ingeniería, por ejemplo, el ingeniero indague por alguna o algunas de esas leyes con el fin de solucionar problemas prácticos en ese universo regido por esos resultados.
De esta manera se persigue en este texto el planteamiento de la teoría que regula los procesos estocásticos y sus aplicaciones directas en el modelamiento de sistemas de líneas de espera. Los programas académicos, tanto de pregrado como de postgrado, incluyen como asignaturas obligatorias sobre teoría de probabilidades la razón principal se fundamenta en que los principales concepto que se relacionan análisis formal de sistemas (y en particular de los sistemas de colas) emerge el comportamiento aleatorio en los sistemas en estudio. Por citar solamente dos casos, las oficinas bancarias y los aeropuertos basan su comportamiento en las leyes del azar y, por lo tanto, en la teoría de probabilidades y más específicamente en modelos avanzados de probabilidad que se conocen como procesos estocásticos. Para cumplir ese objetivo se vale de técnicas que, en general, son sencillas de aplicar e implementar y, la mayoría de las veces, fáciles de deducir y demostrar analíticamente; salvo algunos casos en los cuales se requieren desarrollos matemáticos fuertes para construir o demostrar que el modelo funciona. Así mismo, se aplica la teoría de procesos estocásticos al análisis de aquellos sistemas en los que se formas filas con el fin de deducir un conjunto de medidas de desempeño que permitan tomar decisiones que optimicen esos sistemas
En Procesos estocásticos se reúnen tres áreas de particular interés: matemáticas discretas, Cálculo diferencial e integral, y Teoría de probabilidades 1. Un profesional en el área de ciencias de la computación, por ejemplo, requiere aleatoriedad en la prueba de algoritmos, construcción de juegos, comparación entre algoritmos, construcción de sistemas inteligentes, ecosistemas de agentes autónomos, diseño y construcción de sistemas de realidad virtual, sistemas de vida artificial, diseño de computadores para la inteligencia artificial, etc. Un estadístico, por otra parte, puede requerirla para probar y comparar estimadores (antes de usarlos), calcular potencia de estadísticas, estimar distribuciones de probabilidad, etc. Los especialistas en optimización la
1 En la literatura el área de optimización es más comúnmente conocida como Investigación de operaciones;
sin embargo, el autor prefiere no usar esa terminología por considerarla muy restrictiva y no acorde con su
filosofía y fines.
12
ven como elemento clave en decisiones y simulaciones de larga escala, tales como análisis de sistemas de transporte masivo.
En esta labor debo agradecer principalmente a mis estudiantes de la Universidad Nacional de Colombia y de la Universidad Javeriana de Bogotá, quienes, con sus comentarios y sugerencias, han hecho evolucionar unas notas de clase en un libro escrito principalmente para ingenieros pero que, seguramente, será de utilidad a otros profesionales interesados en el tema.
OBJETIVOS
Este libro ofrece un nivel introductorio al manejo formal de Procesos estocásticos basado en la teoría de probabilidades. El tratamiento del tema es, a la vez, riguroso en el sentido de presentar las principales demostraciones de los teoremas planteados, así como práctico al incluir una serie de ejemplos extraídos de la vida cotidiana y, en especial, del ámbito de la ingeniería industrial.. Se pretende que el estudiante adquiera la destreza en el manejo de los temas relacionados con el manejo del azar, la aleatoriedad y la incertidumbre y la pueda aplicar con solvencia a la solución y modelamiento de situaciones y problemas propios de la ingeniería.
Para alcanzar este propósito, se hace uso de numerosos resultados tomados, principalmente, de Teoría de conjuntos, matemáticas discretas, calculo diferencial e integral, algebra lineal, entre otras.
COMENTARIOS SOBRE LOS EJERCICIOS
La experiencia muestra que es difícil, en la mayoría de los casos imposible, aprender los contenidos de una asignatura con la sola actividad de lectura del material teórico y los ejemplos desarrollados en el mismo, sin su debida aplicación a problemas específicos. Por ello es necesario que el lector se cuestione sobre lo que ha leído y se pruebe así mismo que los contenidos han sido asimilados apropiadamente. En ese sentido, los conjuntos de ejercicios propuestos al final de cada capítulo le ayudarán a aclarar ese dilema.
Con el propósito de que el lector tenga una referencia rápida sobre la dificultad que envuelven los ejercicios propuestos, cada uno ha sido rotulado en forma general de la siguiente manera:
13
CCXX
Donde, CC representan dos caracteres que indican el área de orientación y que deben interpretarse de acuerdo con la Tabla 1:
CARACTERES ORIENTACION
MS Matemática simple.
MI Matemática intermedia.
MA Matemática avanzada.
ES Estadística y probabilidad Simple.
EI Estadística y probabilidad Intermedia.
EA Estadística y probabilidad avanzada.
IO Ingeniería área de optimización.
IR Ingeniería área de Realidad Virtual.
IV Ingeniería área de vida artificial.
** Recomendado.
Tabla 1: Áreas temáticas de orientación de los ejercicios propuestos
Similarmente, las XX representan el nivel de dificultad el cual se interpreta con la
información contenida en la Tabla 2:
CODIGO DIFICULTAD
DESCRIPCION
00 Solución inmediata (ejercicio mental).
10 Simple (Uno a tres minutos).
20 Medio (aprox. 15 minutos).
30 Moderadamente duro.
40 Plazo de proyecto.
50 Problema de Investigación.
Tabla 2: Nivel de dificultad de los ejercicios propuestos.
14
15
1 INTRODUCCIÓN
2 COMPENDIO DE TEORÍA DE PROBABILIDADES
2.1 INTRODUCCIÓN
2.2 ESPACIOS DE PROBABILIDAD
2.3 VECTORES ALEATORIOS Y FUNCIONES DE DISTRIBUCIÓN
CONJUNTAS
2.3.1 INTRODUCCIÓN
2.3.2 DEFINICIONES
2.4 FUNCIONES DE DENSIDAD CONJUNTAS
2.4.1 VECTORES ALEATORIOS DISCRETOS
2.4.2 VECTORES ALEATORIOS CONTINUOS
16
2.4.3 OTRAS CLASES DE VECTORES ALEATORIOS
2.5 DISTRIBUCIONES CONDICIONALES E INDEPENDENCIA
ESTOCÁSTICA
2.5.1 VECTORES ALEATORIOS DISCRETOS
2.5.1.1 Distribuciones Marginales
2.5.1.2 Distribuciones Condicionales
2.5.2 VECTORES ALEATORIOS CONTINUOS
2.5.2.1 Distribuciones Marginales
2.5.2.2 Distribuciones Condicionales
2.5.3 INDEPENDENCIA
2.6 ESPERANZA MATEMÁTICA Y MOMENTOS
17
2.6.1 DEFINICIÓN
2.6.2 VECTOR DE MEDIAS
2.6.3 COVARIANZA Y COEFICIENTE DE CORRELACIÓN
2.6.4 VALOR ESPERADO DE FUNCIONES DE VARIABLES ALEATORIAS
2.6.5 MOMENTOS CONJUNTOS Y FUNCIONES GENERADORAS DE MOMENTOS
2.6.6 ESPERANZA E INDEPENDENCIA
2.7 FAMILIA DE GASUSS MULTIDIMENSIONAL
2.7.1 DENSIDAD CONJUNTA
2.7.2 FUNCIÓN GENERADORA DE MOMENTOS Y MOMENTOS
2.7.3 DENSIDADES MARGINALES Y CONDICIONALES.
2.8 FAMILIAS DE DISTRIBUCIONES UNIPARAMÉTRICAS
2.8.1 INTRODUCCIÓN
18
2.8.2 FAMILIAS DE DISTRIBUCIONES DISCRETAS
2.8.2.1 Bernoulli
2.8.2.2 Poisson
2.8.2.3 Geométrica
2.8.3 FAMILIAS DE DISTRIBUCIONES CONTINUAS
2.8.3.1 Uniforme
2.8.3.2 Gauss
2.8.3.3 Exponencial
2.8.3.4 Erlang
2.8.3.5 Gamma
2.8.4 RELACIONES ENTRE FAMILIAS
19
2.9 EJERCICIOS
2.10 RESUMEN DEL CAPÍTULO
20
3 TEORÍA DE LA DECISIÓN
3.1 INTRODUCCIÓN
Todos los sistemas autónomos, bien sean naturales o artificiales, cuentan
con mecanismos que les permite asumir cursos de acción con el propósito
de coexistir en un ambiente caracterizado por el azar y la aleatoriedad.
Esos mecanismos que les permiten tomar decisiones están, usualmente,
regidos por factores psicológicos, por la experiencia y por la información
con la cual el sistema cuenta.
En Inteligencia Artificial, por ejemplo, a estos sistemas se les llama
agentes mientras que entre los sistemas naturales es el ser humano el
mejor de los representantes de ejercicio de autonomía. Un director de
Tecnologías de la Información en una empresa, para solo poner un caso,
requiere tomar buenas y acertadas decisiones en el ejercicio de su
profesión para lograr sus objetivos y con ello ser exitoso.
En cualquier proceso de toma de decisiones el mecanismos se dispara
ante un estimulo externo que el agente recibe desde el contexto, desde su
interior o bien desde ambos simultáneamente. Una vez el mecanismo se
activa el componente ejecuta algún método de decisión (tan simple o
complejo dependiendo del agente) el cual responde con la alternativa
seleccionada, cuya criterio de optimalidad depende del método. La
alternativa seleccionada produce un conjunto de acciones específicas que
tienen como resultado uno o varios efectos internos al sistema y/o al
contexto en el cual se desenvuelve el sistema.
3.2 LOS ELEMENTOS EN UN PROBLEMA DE DECISIÓN
Los principales elementos que entran en juego a la hora de analizar un
problema de decisión son: El Decisor, Las Alternativas, Los Estados de
la Naturaleza, Los Criterio de Evaluación, Los Retornos o
Consecuencias de la decisión y La Estructura de preferencias del
decisor. A continuación se hacen algunos comentarios sobre cada uno de
ellos.
21
3.2.1 DECISOR
Definición 3—1: Decisor
El sistema o Agente que tiene la potestad de elegir el curso de acción a
seguir, es decir, asumir una decisión, se denomina Decisor.
Aunque los avances en la teoría de Decisiones incluyen elementos de
subjetividad y sentimientos de quien adopta la decisión, es decir en los
actores decisores, en este capítulo, se supone a un decisor objetivo, y
coherente y consistente en su forma de decidir, y que emplea
racionalidad absoluta en el método que emplea para encontrar la
alternativa óptima.
3.2.2 ALTERNATIVAS
Definición 3—2: Alternativa
Para un problema de Toma de Decisiones se debe determinar la lista
exhaustiva y excluyente de posibles decisiones. A cada uno de los
elementos de esa lista se le denomina Alternativa. Formalmente, se
denotará por 1
i n
i iA a
a este conjunto.
Observación 3—1
Aunque usualmente el número de alternativas es contable finito existe la
posibilidad de que sea infinito e incontable.
3.2.3 ESTADOS DE LA NATURALEZA
Existen circunstancias creadas por acciones de la naturaleza o por otros
individuos o grupos que afectan los efectos de la decisión y que no están
bajo el control del Decisor.
Definición 3—3: Estados de la Naturaleza
Aquellas circunstancias externas al actor decisor bajo las cuales se
desenvolverá la decisión adoptada y que se suponen, al igual que las
alternativas, exhaustivas y excluyentes se denominan Los Estados de la
naturaleza. Se denotará por 1
i m
i i
a este conjunto.
22
Observación 3—2
1. Aunque es frecuente que el número de alternativas n sea igual al
número de estados de la naturaleza m , en general son distintos.
2. Normalmente este conjunto es contable finito pero existe la
posibilidad de que sea infinito e incontable.
Definición 3—4: Estructura probabilística de .
A la función de densidad de probabilidad f de ocurrencia de los
estados de la naturaleza se le denomina Estructura probabilística de los
estados de la Naturaleza.
3.2.4 EFECTOS O CONSECUENCIAS DE LA DECISIÓN
Definición 3—5: Retorno de una decisión.
La función :r A se denomina función de retorno si ,i jr a
representa el costo o la ganancia de haber asumido como decisión a la
alternativa ia y haberse presentado el estado de la naturaleza j .
3.2.5 ESTRUCTURA DE PREFERENCIAS DEL DECISOR
Pueden existir situaciones en las cuales los métodos formales produzcan
no solamente una alternativa óptima sino un conjunto de ellas que
cumplen con el criterio establecido. La pregunta que surge de inmediato
es ¿Por cuál de ellas optar?
Definición 3—6: Soluciones óptimas no dominadas.
Al conjunto * * * *, ,k k kA a a A a esóptima de alternativas óptimas se
conoce con el nombre de alternativas no dominadas.
En el caso en el * 1A el decisor debe poner su subjetividad para
seleccionar la alternativa definitiva. Para ello impone un orden sobre este
conjunto basado en sus preferencias. Puesto que todas las alternativas de
este conjunto cumplen el criterio establecido de optimalidad, cualquiera
de ellas estará bien como decisión.
23
Definición 3—7: Estructura de preferencias del decisor.
Un orden subjetivo basado en las preferencias del decisor impuesto sobre *A y que le da un ranking a las alternativas no dominadas se le llama
estructura de preferencias del decisor.
3.3 MODELOS DE DECISIÓN
Existen tres clases de problemas de decisión a considerar que dependen
de la información que se tenga de la Estructura probabilística de
ocurrencia de los estados de la naturaleza. Las Definiciones establecen
las distinciones entre estos tres casos.
3.3.1 PROYECTOS Y DECISIONES
En ingeniería normalmente las decisiones están asociadas a la ejecución
de proyectos. Implementación de una red de computadores, diseño de un
computador, desarrollo de un sistema de información, etc, son ejemplos
en los cuales las decisiones juegan un rol importante.
Los criterios para caracterizar una decisión frente a un determinado
proyecto de ingeniaría se resume en la Tabla 3—1.
Flexibilidad Se refiere a la capacidad del proyecto a responder a cambios que no pueden predecirse.
Robustez Hace alusión a la capacidad de un proyecto de soportar satisfactoriamente todos los estados de la naturaleza previstos.
Vulnerabilidad Es la capacidad del proyecto de soportar satisfactoriamente cambios que pueden predecirse.
Adaptabilidad Es la capacidad del proyecto a responder a cambios que pueden predecirse.
Elasticidad Es la capacidad del proyecto a retornar a una situación normal ante un cambio en las situaciones del entorno.
Liquidez Es la facilidad de transición desde una situación dada en un periodo de tiempo a una situación deseada en el próximo periodo de tiempo.
Plasticidad Es la capacidad del proyecto de permanecer en una misma situación. A diferencia de la flexibilidad que permite
24
transformación, la plasticidad no lo hace. Tabla 3—1: Características de las alternativas según los proyectos.
3.3.2 DECISIONES BAJO CERTEZA
Definición 3—8: Problema de decisión bajo certeza.
Cuando para el problema solo existe un posible estado de la naturaleza
bajo el cual se desenvolverá la decisión asumida lo que implica que su
probabilidad de ocurrencia es 1, se dice que el problema es de decisión
bajo certeza.
En otras palabras, el decisor conoce exactamente el contexto bajo el cual
se desenvolverá la decisión tomada.
Ejemplo 3—1: Modelos de programación lineal.
Para un determinado problema de optimización se ha formulado el
modelo de programación lineal:
1 2
1 2
1 2
1 2
3 2
. . 5 15
2 4 10
, 0
Máx Z x x
s a x x
x x
x x
Puesto que todos los coeficientes del modelo constituyen el contexto, esto
es estados de la naturaleza, sobre el cual la decisión se va a desenvolver y
ellos son contantes el problema es de decisión bajo certeza. En este caso
es fácil verificar (aplicando el método SIMPLEX) que su solución óptima
está dada por * * *
1 2, 2.7778,1.1111a x x y, además, * 10.5555Z .
3.3.3 DECISIONES BAJO RIESGO: ESPERANZA MATEMÁTICA CRITERIO RACIONAL.
Definición 3—9: Problema de decisión bajo Riesgo.
Un problema de decisión se dice bajo riesgo cuando el decisor conoce
todos los posibles estados de la naturaleza bajo los cuales se puede
desenvolver la decisión y cuenta con su función de densidad de
probabilidad f de ocurrencia de los mismos.
25
Ejemplo 3—2: Modelos de programación lineal estocástico.
Un determinado problema de optimización que pueda formularse
mediante el modelo:
.
. .
0
Ópt Z CX
s a AX B
X
Para el cual A , B , y C son vectores aleatorios correlacionados con
función de densidad conjunta , , , ,A B Cf a b c conocida por el decisor antes
de asumir un determinado curso de acción, es un problema clásico de
decisión bajo riesgo. En esta clase de modelos, el método SIMPLEX no es
aplicable de forma directa para encontrar la solución óptima.
Definición 3—10: Modelo del problema de decisión bajo riesgo.
A la cuádrupla , , ,R A f r se le llama el modelo del problema
de decisión bajo riesgo.
Definición 3—11: Método de solución de racionalidad absoluta.
Para un modelo R se dice que el método racionalidad absoluta es aquel
que obtiene * * * *
, ,, ,k k k k i j ii
A a a A E r a Ópt E r a . Dónde
*
, ,
1
m
k k k j j
j
E r a r f
. Es decir es un método de optimalidad basado en la
esperanza matemática de los retornos de las alternativas.
Ejemplo 3—3: POZO PETROLERO.
En un proyecto de perforación petrolera se piensa que se pueden
encontrar 500.000, 200.000 o 50.000 barriles o un pozo seco. La
dirección general de la petrolera desea examinar las siguientes
alternativas: Perforar directamente, Alquilar incondicionalmente o un
alquiler condicionado. El alquiler incondicional consiste en cobrar
US$45.000,oo por la explotación del campo sin ninguna otra
contraprestación; mientras que en el alquiles condicionado se asume
26
algún riesgo compartido de manera que si el pozo resulta de 200.000 o
más barriles la petrolera estatal recibirá regalías de US$0.50 por barril de
lo contrario no habrá cobro alguno.
Se sabe que el costo de perforación de un pozo productivo es de
US$100.000,oo sin embargo, si el pozo es seco los costos de perforación
ascenderán a US$75.000,oo. También se sabe que la utilidad de la
operación por cada barril obtenido es de US$1.50,oo (Sin descontar el
costo de perforación).
Un estudio encontró que la probabilidad de que en un pozo se encuentren
500.000 barriles es de 0.1 de 200.000 es 0.15 de encontrar 50.000
barriles es 0.25 mientras que encontrarlo seco es de 0.5. ¿Cuál debe ser la
decisión racional que el presidente de la compañía petrolera debería
adoptar?
Solución:
En este problema el decisor es único y se supone absolutamente racional.
Existen 3n alternativas y, por lo tanto 1 2 3, ,A a a a definidas de la
siguiente manera:
1a : Perforar directamente.
2a : Alquilar incondicionalmente.
3a : Alquiler condicionado.
De acuerdo con la información dada en el problema hay 3m estados de
la naturaleza. Estos son:
1 : El pozo tiene 500.000 barriles.
2 : El pozo tiene 200.000 barriles.
3 : El pozo tiene 50.000 barriles.
4 : El pozo está seco.
27
Por su lado, la estructura probabilística de los estados de la naturaleza se
puede sintetizar en la tabla:
i 1 2 3 4
if 0.10 0.15 0.25 0.50
Los efectos o consecuencias de la decisión se resumen en la tabla:
1 2 3 4
1a 65.000,oo 200.000,oo -25.000,oo -75.000,oo
2a 45.000,oo 45.000,oo 45.000,oo 45.000,oo
3a 250.000,oo 100.000,oo 0,oo 0,oo
Las Esperanzas Matemáticas
, ,
1
m
i i i j j
j
E r a r f
1a 51.250,oo
2a 45.000,oo
3a 40.000,oo
En consecuencia * *
1 51.250,A a oo que muestra que solamente existe
una alternativa óptima y no dominada. Por lo tanto no es necesario
recurrir a la Estructura de preferencias del decisor.
Finalmente, la decisión racional debe ser perforar directamente.
3.3.4 DECISIONES BAJO INCERTIDUMBRE
Definición 3—12: Problema de decisión bajo Incertidumbre.
Un problema de decisión es bajo incertidumbre cuando, aunque la
ocurrencia de los estados de la naturaleza depende del azar y la
aleatoriedad, su estructura probabilística f es desconocida.
Si el conjunto de alternativas es finito y el número de realizaciones de los
estados de la naturaleza es igualmente finito es posible representar el
problema mediante la siguiente matriz de resultados.
28
1
j m
1a 11r 1 jr 1mr
ia 1ir ijr imr
na 1nr njr nmr
Ejemplo 3—4 : Producción de vehículos
Una empresa fabricante de vehículos estudia lanzar un nuevo modelo al
mercado, pudiéndolo posicionar en cuatro segmentos distintos. Los
segmentos candidatos son: Deportivo de bajo costo, Berlina familiar
media, monovolumen y todo terreno. Los beneficios esperados
(expresados en millones de dólares) en el año siguiente al lanzamiento en
función del tipo de interés al consumo son:
1 2 3 4
1a : Deportivo 24 19 10 16
2a : Berlina 22 22 23 20
3a : Monovolumen 23 23 21 15
4a : Todo terreno 25 24 18 14
¿Cuál sería la decisión que la empresa debería tomar?
El criterio de decisión que se debe emplear depende de la hipótesis de
comportamiento psicológico del jugador, y será alguno de los siguientes:
1. Criterio de decisión de Wald.
29
2. Criterio de decisión MÁXIMAX.
3. Criterio de decisión de Hurwicz.
4. Criterio de decisión de Savage.
5. Criterio de decisión de Laplace.
Estos criterios de decisión no son objetivos y por lo tanto, los resultados
de aplicar uno u otro no son comparables entre ellos.
3.3.4.1 Criterio de decisión de Laplace
Está basado en el principio de indiferencia, es decir, en desconocimiento
de las probabilidades de los distintos estados de la naturaleza, el jugador
no puede decidir que una realización sea más probable que otra. En
consecuencia los considera equi–probables, puesto que éstos le resultan
indiferentes. Bajo este criterio, ahora sí se conocen las probabilidades de
los estados de la naturaleza y por lo tanto lo ha trasformado en un
problema bajo riesgo para el cual debe emplear el criterio de la esperanza
matemática óptima.
Formalmente, el criterio establece que de no tener las probabilidades de
realización de los estados de la naturaleza, el comportamiento que se
debe suponer es uniforme.
Cuando 1
j m
j j
es discreto y finito se tiene que las probabilidades
1
1j m
j j
j
P p fm
que satisfacen la condición de que
1 1
1m m
j
j j
p p mp
se concluye que 1
pm
y, por lo tanto, el criterio
establece que * * * *
,
1
1, ,
m
k k k k ij iji j
A a a A E r a Ópt r rm
.
Por su parte, de forma similar como en el caso discreto, cuando 1
j m
j j
es continuo la función que describe sus probabilidades es una densidad
30
uniforme continua en consecuencia, el criterio establece que
* * * *
,, ,k k k k ii
A a a A E r a Ópt r f d
.
3.3.4.2 Criterios de vulnerabilidad
Los criterios de vulnerabilidad son muy útiles cuando se consideran
posibles estados de la naturaleza críticos tales como sequías, grandes
avenidas, etc. Los criterios de vulnerabilidad más aplicados son: El
criterio de la distancia al peor valor, el criterio basado en las funciones de
arrepentimiento y el criterio de minimizar el máximo arrepentimiento.
3.3.4.2.1 Criterio de decisión MAXIMAX
Este criterio supone un comportamiento optimista del jugador, es decir el
decisor piensa que para la alternativa por la que opte le va a ocurrir lo
mejor. Por este motivo le asocia a cada alternativa el mejor de los posibles
resultados, declarando como alternativa óptima aquella que le
proporcione el mejor de los mejores resultados.
Designaremos por iM al mejor de los resultados de la alternativa iA , es
decir, ( )i iji
M mejor r
* * * , ,k k kj iji j
A a a A r mejor mejor r
Esto nos lleva a hablar de dos expresiones de este modo, según los
resultados sean favorables o desfavorables.
3.3.4.2.2 Criterio de decisión de Wald
Este criterio se basa en la idea de que el jugador es prudente o pesimista.
Ello le lleva a observar el problema de decisión en ambiente de
incertidumbre de la siguiente manera, piensa que le va a ocurrir lo peor,
por lo tanto, asocia a cada alternativa el peor de sus posibles resultados.
De esta manera la alternativa optima será aquella que lleva asociado el
mejor de los peores resultados
i ijj
a peor r
31
Designando por im al peor de los resultados de la alternativa
ia , es decir,
i ijj
m peor r
* * * , ,k k kj ij ii j i
A a a A r mejor peor r mejor m
Esto nos lleva a hablar de dos expresiones de este criterio, según los
resultados sean favorables o desfavorables:
Resultados favorables:
mini ij ij
a r m
* max min maxij iji i
a r m
Resultados desfavorables:
maxi ij ij
a r m
* min max minij ii ij
a r m
3.3.4.2.3 Criterio de decisión de Savage
Savage plantea el problema de evaluar la consecuencia de la decisión
errónea en los siguientes términos. Si el decisor supiera con certeza la
realización del estado de la naturaleza que se va a presentar, elegiría
aquella alternativa que en su realización, le proporcionase un resultado
óptimo. No hacerlo así supondría un costo de oportunidad, medido
matemáticamente por la diferencia entre este resultado más favorable y
el obtenido, es decir, por la comparación de la alternativa acertada y la
elegida.
De esta forma, se puede construir la llamada matriz de costos de
oportunidad también conocida por otros nombres como matriz de
arrepentimientos o pesares que será el punto de partida para solucionar el
problema. Sobre dicha matriz se aplica el criterio de Wald, siempre con la
expresión de resultados desfavorables debido a que en este caso los
retornos representan siempre costos.
En general, en la distancia al peor valor se puede emplear el criterio
1
* * * *, ,q q
k k ij jA a a A Máx E R R
. Mientras que con la
32
comparación con otra alternativa ideal se emplea:
1
* * * *, ,q q
k k j ijA a a A Mín E R R
.
3.3.4.2.4 Criterio de decisión de HURWICZ
Este criterio supone una posición intermedia entre los extremos de
pesimismo y optimismo. Hurwicz razona en el sentido de que la postura
de decisión es intermedia entre el optimismo absoluto del criterio
Máximax y el pesimismo extremo del criterio de Wald. La hipótesis
fundamental de ese criterio es que el decisor es capaz de decidir su grado
de pesimismo relativo a través de un coeficiente 0,1 , que llamamos
coeficiente de pesimismo relativo. De esta forma, este criterio propone
asignar a cada alternativa iA un valor real ic que se obtiene como
combinación lineal convexa del mejor y el peor resultad de cada
alternativa, ponderando el peor resultado con el coeficiente de pesimismo
relativo. La alternativa optima es aquella que proporciona un mejor valor
de ic , es decir
1i i i iA c m M
Donde i iji
m peor r representa el peor resultado de la alternativa iA y
( )i ijj
M mejor r representa el mejor resultado de la alternativa iA
*
ii
A mejor c
Esto lleva a considerar dos versiones de este criterio según los resultados
sean favorables o desfavorables:
Resultados favorables:
1i i i iA c m M
Resultados desfavorables:
1i i i iA c m M
33
Donde mini iji
m r y maxi iji
M r
* max ii
A c
Donde maxi ijj
m r y i ijj
M mínr
* min ii
A c
El principal problema que presenta este criterio es que no todo decisor es
siempre capaz de definir su coeficiente de pesimismo relativo. Se debe
hacer notar que si el grado de pesimismo total es 1 la regla de
decisión de Hurwicz Coincide con la de Wald, y que si el grado de
pesimismo es nulo 0 la regla de decisión de Hurwicz coincide con el
Maximax
Ejemplo 3—5 : Producción de vehículos (Cont.)
La aplicación del criterio de Hurwicz al planteamiento del Ejemplo 4—2
conduce al siguiente análisis.
Criterios de Wald
Es un criterio de decisión para un comportamiento prudente. Por lo que a
cada alternativa le asigna su peor resultado y de ellos escoge el mejor, es
decir,
mini ij ijj
a r m
* max min maxj ij ijji i
a r m
Por tanto para
1 1min min 24, 19, 10, 16 10jj
a r
2 2min min 22, 22, 23, 20 20jj
a r
3 3min min 23, 23, 21, 15 15jj
a r
4 4min min 25, 24, 18, 14 14jj
a r
34
Luego 2014,15,20,10maxminmax
iij
jir es decir, la alternativa
optima según el criterio de Wald es la segunda, lanzar el modelo berlina.
Criterio maximax
Es un criterio de decisión para un comportamiento optimista o
arriesgado. Por ello, a cada alternativa se le asigna su mejor resultado y
de ellos elige el mejor, dicho de otra forma, elige la alternativa que
proporciona el mejor resultado posible. Por lo tanto
maxj ij ijj
a r M
* max max maxj ij iji j i
a r M
Y así
1 1max max 24, 19, 10, 16 24jj j
a r
4 4max max 25, 24, 18, 14 25jj
a r
3 3max max 23, 23, 21, 15 23jj
a r
2 2max max 22, 22, 23, 20 23jj
a r
Como 2525,23,23,24maxmaxmax
iij
jir , la alternativa elegida según el
criterio optimista, es lanzar el modelo todo-terreno.
Criterio de HURWICZ
Es un criterio de decisión intermedio entre el criterio de Wald y el de
Máximax, en el cual el decidor puede evaluar su grado de pesimismo con
un coeficiente al que se denota por . Con dicho coeficiente se establece
una combinación lineal convexa entre el mejor y el peor resultado para
cada alternativa y se elige al mejor, es decir,
35
1i i i ia c m M
Donde ij
ji rM max
y ij
ji rm min
* max max 1i i ij j
a c m M
Así pues para cada alternativa elegimos el peor y el mejor resultado y
establecemos la combinación lineal convexa entre ambos que se expresa
en la siguiente tabla:
1 2 3 4 im iM 1i i ic m M
1a : Deportivo 24 19 10 16 10 24 124101c
2a : Berlina 22 22 23 20 20 23 2 20 23 1c
3a : Monovolumen 23 23 21 15 15 23 3 15 23 1c
4a : Todo terreno 25 24 18 14 14 25 4 14 25 1c
Como el decidor no expresa de manera concreta su coeficiente de
pesimismo, estudiaremos lo que sucede para todos los posibles valores de
. Un sencillo análisis matemático (posiblemente gráfico) conduce a las
siguientes conclusiones. Para valores de 10, la alternativa
preferida es 4a mientras que para 1,1 es 2a . En consecuencia el
valor de 1 se puede calcular al resolver la ecuación 4 2c c n, o,
equivalentemente, 14 25 1 20 23 1 . De donde 1 0.25 .
De esta manera si 0,0.25 decidirá la alternativa 4a en caso
contrario optará por 2a .
3.3.4.3 Alternativas Pareto Óptimas
3.3.4.4 Criterios de Robustez
36
3.3.4.5 Criterios de Satisfacción
3.3.4.6 Criterios de Flexibilidad
3.4 ARBOLES DE DECISIÓN
El modelo de decisión basado en matrices es adecuado para juegos
sencillos pero dejan de ser útiles en situaciones más complejas. En este
último caso los árboles de decisión se constituyen en la estructura de
datos por excelencia para representar la situación de riesgo en la que el
jugador participará. La Figura 3—1 muestra la representación de un
juego complejo mediante el uso de una estructura de datos en forma de
árbol. En un árbol de decisión, los nodos pueden ser de tres tipos
distintos: Los nodos de decisión representados por un cuadrado, los
nodos de incertidumbre representados por una circunferencia y,
finalmente, las hojas o nodos de retornos que se simbolizan por medio de
un rectángulo.
Un árbol de decisión representa una situación de decisiones secuenciales
complejas cuyos sub–árboles representan un problema de decisión más
simple. Hasta llegar a un sub–árbol cuya solución se puede calcular
mediante una matriz como las ya expuestas en la sección 3.3.3
Ejemplo 3—6: Licitación pública.
Una empresa tiene la posibilidad de presentarse a un concurso público
para la adjudicación del servicio internacional de correo aéreo, que le
supondría un beneficio de 5 millones de euros al año. Para presentarse al
concurso debe preparar un proyecto que le costará medio millón de
euros, considerando que la probabilidad de conseguir el contrato es de un
70%.
La empresa no posee aviones suficientes para cubrir el servicio por lo que
en caso de conseguir el contrato, debe decidir si compra los aviones que le
falta o los alquila a una empresa nacional o extranjera. El costo de cada
37
opción planteada es de 3, 1.5 y 1.3 millones de euros respectivamente. La
empresa sabe que tiene una probabilidad de un 50% de conseguir una
subvención estatal del 50% del importe de la compra, de un 30% del
precio del alquiler si el proveedor es una empresa nacional y de un 20% si
es extranjera. En este último caso, también tiene que tener en cuenta que
el pago se realizará en dólares y que una devaluación del euro supondrá
una pérdida adicional de 100.000 euros. Según la situación actual del
mercado monetario, esta empresa considera que la probabilidad de una
devaluación del euro es de un 75%. ¿Qué decisión deberá tomar la
empresa?
Solución
Este es un problema de decisión secuencial, ya que la empresa debe
tomar dos decisiones interdependientes: primero debe decidir si realiza
el proyecto (se presenta al concurso) y, en caso de conseguir el contrato,
si compra o alquila a una empresa nacional o extranjera los aviones que le
faltan. La forma de representar y resolver este tipo de problemas es
mediante el árbol de decisión.
38
1a
2a
3a
4a
5a
-0,5
0
3,20
3,10
3,46
3,36
3
3,45
1,5
3
1
2
3
4
56
7
1 0,7P
2 0,3P
3 0,5P
4 0,5P
3 0,5P
4 0,5P
3 0,5P
4 0,5P
5 0,75P
6 0,25P
5 0,75P
6 0,25P
Figura 3—1: Árbol de decisión típico.
Donde:
1 :a Presentarse al concurso. 1 : Tener éxito.
2 :a No presentarse al concurso. 2 : No tener éxito.
3 :a Comprar los aviones. 3 : Conseguir la subvención.
4 :a Alquilar los aviones a una empresa nacional.
4 : No conseguir la subvención.
5 :a Alquilar los aviones a una empresa extranjera.
5 : Devaluación.
6 : No devaluación.
Como se conocen las probabilidades de ocurrencia de cada estado de la
naturaleza (ambiente de riesgo), se utilizar el criterio de valor monetario
esperado para solucionar el problema. Ello supone que el valor de los
nodos de incertidumbre será el promedio de los resultados a los que
conducen las diferentes ramas que parten de dichos nodos. Así:
1 3,36 0,75 3,46 0,25 3,385
2 3,10 0,75 3,20 0,25 3,125
39
Si planteamos el problema resultante en forma normal se tiene:
3 4
3
4
5
0,5 0,5
3 1,5
3,45 3
3,385 3,125
a
a
a
Aplicando el criterio de valor esperado
3 3 3 0,5 1,5 0,5 2,25E R a
4 4 3,45 0,5 3 0,5 3,225E R a
5 5 1 20,5 0,5 3,385 0,5 3,125 0,5 3,255E R A
Para valorar el segundo nodo de decisión optimizamos los resultados
esperados correspondientes a cada alternativa:
5 53,4,5 3,4,5
3,225i ii i
máx E R a opt a a
es decir alquilar los aviones a
una empresa extranjera
Al valorar el siguiente nodo de incertidumbre, que escrito en forma
normal resulta:
1 2
1
2
0,7 0,3
/
3,255 0,5
0 0
A
a
a
Así pues
1 6 3,255 0,7 0,5 0,30 2,1285E R A
2 0E R A
40
El valor del primer nodo de decisión será
6 11,2 1,2
2,1285i ii i
máx E R a opt a a
es decir presentarse al concurso.
Por tanto la decisión óptima será presentarse al concurso y, si lo gana,
alquilar los aviones a una empresa extranjera. Con esta forma de actuar,
el decisor espera conseguir 2,1285 millones de euros.
3.5 VALOR ESPERADO DE LA INFORMACIÓN PERFECTA
Es evidente que un decisor tomaría siempre la mejor decisión si supiera el
estado de la naturaleza que va a presentarse, es decir, si tuviera
información perfecta de su entorno. Así, todo decisor, una vez resuelto el
problema, se plantea si puede obtener más información sobre el estado
de la naturaleza, de manera que lo ideal sería que tuviera certeza sobre la
presentación de las concreciones. Por tanto, toda mejora en la
información sobre el entorno supone, en general, una mejora en los
resultados obtenidos. En consecuencia, todo decisor podría estar
interesado en obtener información adicional que le permitiese un mejor
conocimiento del entorno.
Esa información adicional puede ser de dos tipos:
1. Información adicional de carácter perfecto o información
cierta: se caracteriza porque le permite al decisor comportarse
como si supiera exactamente qué concreción del estado de la
naturaleza va a presentarse, es decir, como si el problema se
plantease en ambiente de certeza.
2. Información adicional de carácter imperfecto o información
aleatoria: se caracteriza porque tiene distintas posibles
concreciones, permitiéndole al decisor rectificar la distribución de
probabilidad que en un principio otorgó el estado de la naturaleza
(Teorema de Bayes).
41
Ahora bien, toda información adicional tiene un costo. Por ello, el decisor,
antes de contar con esa información, debe conocer el valor que para él
tiene y determinar si le interesa o no comprarla.
Para valorar la información adicional de carácter perfecto introducimos
los siguientes conceptos:
3.5.1 REIP: RESULTADO ESPERADO CON INFORMACIÓN PERFECTA
Representa la cantidad que el decisor espera ganar si supiera con certeza
qué concreción del estado de la naturaleza va a presentarse. Se calcula
como *jREIP E r donde * ( )j iji
r mejor r j . Si E es una variable aleatoria
discreta entonces *j j
j
REIP r P mientras que Si E es una variable
aleatoria continua entonces * ( )j j j
j J
REIP r f E d
. Cabe advertir que si los
resultados son favorables, ese <<mejor>> es máximo y, en caso contrario,
es mínimo.
3.5.2 RER: RESULTADO ESPERADO EN RIESGO
Corresponde al valor esperado en ambiente de riesgo.
3.5.3 VIP: VALOR DE LA INFORMACIÓN PERFECTA
Representa el valor que la información adicional perfecta tiene para el
decisor porque supone la mejora en los resultados esperados que
obtendría con esa información. Se calcula, por tanto, como
VIP REIP RER . Este valor representa la cantidad máxima que el decisor
estará dispuesto a pagar por la información adicional de carácter
perfecto.
3.5.4 CIP: COSTO DE LA INFORMACIÓN PERFECTA
Representa la cantidad de dinero que le cuesta al decisor adquirir la
información perfecta. Por tanto el criterio de decisión está dado por:
1. Si CIP VIP , el decisor adquirirá la información perfecta.
2. Si CIP VIP , el decisor no adquirirá la información perfecta.
42
Ejemplo 3—7: Licitación pública (cont.).
Para el mismo enunciado del Ejemplo 3—6 . Si pudiera disponer de
información perfecta sobre la concesión de las subvenciones ¿Cuánto
estaría dispuesto a pagar por ella?
Solución:
Para poder contestar a esta pregunta debemos conocer el valor que para
el decisor tiene la información de carácter perfecto sobre la consecución
de las subvenciones. Matemáticamente podemos calcular como
VIP REIP RER , siendo:
*
*
3
*
4
3,45 0,5 3,125 0,5 3,2875
3 3,45
4 3,125
ij j
i
i
REIP r p
si j r
si j r
5 3,255RER
Por tanto
3,455 3,255 0,2VIP
Esta es la cantidad, en millones de euros, que el decisor está dispuesto a
pagar, como máximo, por una información perfecta sobre la concesión de
las subvenciones.
43
3.6 TEORÍA DE LA UTILIDAD
3.6.1 INTRODUCCIÓN
3.6.2 FUNCIONES DE UTILIDAD
3.6.3 CURVAS TÍPICAS DE UTILIDAD
3.7 DECISIONES MULTIOBJETIVO
3.7.1 INTRODUCCIÓN
3.7.2 SOLUCIONES NO DOMINADAS
3.7.3 INCLUSIÓN DE LA ESTRUCTURA DE PREFERENCIAS DE DECISOR
3.7.4 MÉTODO DE LAS RESTRICCIONES
3.7.5 MÉTODO DE LAS PONDERACIONES
3.8 MÚLTIPLES ACTORES DECISORES
44
4 PROGRAMACIÓN DINÁMICA
4.1 INTRODUCCIÓN
La programación dinámica es una herramienta matemática que permite
resolver problemas de decisión secuencial. En este tipo de problemas las
decisiones son interdependientes entre sí.
Dependiendo de los estados de la naturaleza los problemas de
programación dinámica se pueden clasificar en dos grandes grupos:
Problemas determinísticos y Problemas de naturaleza estocástica.
A un problema que puede solucionarse empleando los métodos de
Programación dinámica se le denomina el sistema, mientras que a los
subsistemas secuenciales de que consta se les llama etapas.
iETAPA
1ix
id
ir
ix H
G 1if if
mETAPA
1mx
md
mr
mx H
G 1mf mf
1ETAPA
0x
1d
1r
1x H
G 0f 1f
SISTEMA
Figura 4—1: Esquema general de un problema de programación dinámica.
4.2 PROGRAMACIÓN DINÁMICA DETERMINÍSTICA
4.2.1 INTRODUCCIÓN
Como se estableció en la sección 3.2.3 en los problemas determinísticos
se conocen tanto los estados de la naturaleza (en los que la decisión se va
a desenvolver) como los resultados. Se trata pues de encontrar la mejor
política que optimice la situación en este ambiente de certeza.
45
El problema se subdivide en m etapas. Cada etapa se caracteriza por la
toma de una y solo una decisión.
Tanto en el sistema como en la i ésima etapa 1,2, ,i n se plantea un
problema de decisión con los siguientes elementos:
4.2.2 DECISOR
En este tipo de problemas de decisión se supone un único decisor
absolutamente racional.
4.2.3 ALTERNATIVAS Y VARIABLES DE ESTADO Y DE DECISIÓN
En cada etapa el decisor debe optar por una cantidad id denominada
variable de decisión de ese subsistema.
Definición 4—1: Política
A una posible tupla 1 2, , , , ,j md d d d conformada por valores
posibles de todas las variables de decisión del sistema se le denomina
política del decisor.
Definición 4—2: Alternativas
El conjunto de todas las posibles políticas del sistema corresponde a las
alternativas del problema de decisión. Formalmente hablando
1 21
, , , , ,i n
i j m i iA a d d d d
se conoce como las alternativas del
problema de programación dinámica.
En este tipo de problemas se define adicionalmente, una variable
adicional que describe el entorno del sistema y de cada subsistema o
etapa y que contendrá toda la información necesaria para la toma de
decisión coherente en cada una de las etapas y, en consecuencia, del
sistema.
Definición 4—3: Variable de estado
46
La variable X cuyo valor jx recuerda el estado (memoria) del sistema
luego de tomar la decisión en la etapa j se conoce con el nombre de
Variable de estado.
Observación 4—1
1. La variable de estado X es especialmente útil en dos momentos:
1jx y jx . Es decir antes y después de tomar la decisión j .
2. Aunque la mayoría de problemas requieren únicamente una
variable de estado, existen situaciones en las que es necesario
manejar un vector de estado, esto es 1, , , ,k sX X X X .
La relación entre los diferentes valores de la variable de estado se
establece de manera recursiva mediante las ecuaciones de recurrencia
dada por 1,j j jx H x d en la que ,H es la función de actualización de
estado a veces conocida como la dinámica del cambio de la variable de
estado. Puesto que esta ecuación en diferencias es de primer orden
únicamente se requiere una condición de frontera 0x . Este valor inicial
de X representa el estado de antes de tomar cualquier decisión.
4.2.4 CRITERIO DE EVALUACIÓN Y FUNCIÓN DE RETORNO GLOBAL
jr representa el resultado o retorno de la etapa j ésima y con ello la
contribución de esa etapa al rendimiento total del sistema. Puesto que el
propósito es encontrar una política óptima y no solamente optimizar el
resultado de la j ésima etapa, es necesario definir una función de
rendimiento global ,G . En general, el rendimiento global obtenido
hasta la j ésima etapa se denota como jf y su dinámica se expresa como
una relación de recurrencia de la de la forma 1,j j jf G f r con
condición inicial o de frontera 0f . Este valor de arranque denota el
rendimiento acumulado antes de empezar a resolver el problema.
4.2.5 SOLUCIÓN Y CRITERIO DE OPTIMALIDAD DE BELLMAN
47
4.2.5.1 Solución del problema de programación dinámica.
La solución del problema (o sistema) será la política
*
*
1 2, , , , ,i j m ia d d d d para la cual el rendimiento global jf tras la
decisión en la última etapa sea óptimo. Es decir, aquella política *
ia para
la cual *
m mf opt f .
4.2.5.2 Principio de Bellman.
El principio de Bellman establece que una política es óptima si
cualesquiera que sean el estado y la decisión iniciales en una etapa
dada las decisiones que quedan por tomar constituyen una política
óptima respecto del estado restante de la primera decisión.
En otras palabras una política es óptima si está constituida por
subpolíticas óptimas.
4.2.5.3 Ecuación de Bellman.
Dada la función mf que debe optimizarse en m etapas y siendo *
1mf el
valor óptimo global hasta la etapa 1m , mf debe construirse a partir de *
1mf para que el problema sea óptimo también en m etapas.
Recursivamente significa que *
1,j j jf f f r dado 0f .
El orden de los cálculos para llegar a una solución depende de las
características del problema en cuestión.
4.2.6 EJEMPLOS
Ejemplo 4—1: Pasar el tercio en la Universidad Nacional.
Suponga que para poder continuar sus estudios en la Universidad
Nacional, un estudiante debe aprobar la tercera parte de las asignaturas
inscritas. Juan, un estudiante de Ingeniería de Sistemas, tiene inscritas
Algebra, Cálculo y dibujo. Ya solo le quedan 4 semanas para los
exámenes y sabe que la probabilidad de aprobar cada una de las materias
48
depende del número de semanas que dedique a estudiarla. Una reflexión
sobre sus aptitudes personales le llevó a concluir que estas
probabilidades son:
No. Semanas Algebra Cálculo Dibujo 0 0.2 0.25 0.1
1 0.3 0.3 0.3
2 0.35 0.33 0.4 3 0.38 0.35 0.45
4 0.4 0,38 0.5 Determine, mediante programación dinámica el número de semanas que
debe dedicar a estudiar cada asignatura en el tiempo que le queda para
que la probabilidad de continuar como estudiante regular de la
Universidad Nacional sea máxima.
Solución:
Etapas:
:iETAPA CÁLCULO
id
2r
H
G
:mETAPA DIBUJO
2x
3d
3r
3x H
G 2f 3f
1 :ETAPA ÁLGEBRA
0x
1d
1r
1x H
G 0f 1f
PasarElTercio
Figura 4—2: Diagrama de etapas para el problema del tercio de permanencia
49
Variable de decisión:
Para este problema hay 3 variables de decisión por lo cual las
alternativas son de la forma 1 2 3 1, ,
i n
i i iA a d d d
en la cual jd
es el
número de semanas de estudio utilizadas en la etapa j . Sus posible
valores son 0,1,2,3,4
Variable de estado:
La variable de estado jx representa el número de semanas de estudio
utilizadas hasta la etapa j . Es fácil ver que 1 1,j j j j jx H x d x d .
Ambien en este caso sus posible valores son 0,1,2,3,4.
Función de rendimiento:
El objetivo es maximizar la probabilidad de aprobar al menos una de las
tres asignaturas. Esto es máx P A C D . Puesto que
A C D A C D y los eventos son independientes
1 1P A C D P A C D P A P C P D .
En consecuencia, maximizar la probabilidad de aprobar al menos una de
las asignaturas es lo mismo que minimizar la probabilidad de no aprobar
ninguna.
El rendimiento en cada etapa jr representa la probabilidad de no
aprobar la asignatura correspondiente de la j ésima etapa. Esta
corresponde a la complementaria de la que viene dada en la tabla de
probabilidades del enunciado.
Ecuación recursiva del rendimiento:
1
*
1 1d
f x mín P A
*
2 2 1 1f x P C f x 2
*
2 2 2 2d
f x mín f x
50
*
3 3 2 2f x P D f x 3
*
3 3 3 3d
f x mín f x
Ahora es posible el modelo comenzando desde la primera etapa a la
última etapa.
PRIMERA ETAPA(Algebra)
1 0x x 0 1 1f x *
1 1f x *
0x *
1d
0 0.80 0.80 0.80 0 0
1 0.70 0.70 0.70 0 1 2 0.65 0.65 0.65 0 2
3 0.62 0.62 0.62 0 3 4 0.60 0.60 0.60 0 4
P A
SEGUNDA ETAPA(Cálculo)
2 1x x 0 1 2 3 4 0 1 2 3 4 *
2 2f x *
1x *
2d
0 0.75 – – – – 0.60 – – – – 0.6000 0 0
1 0.70 0.75 – – – 0.56 0.525 – – – 0.5250 1 0
2 0.67 0.70 0.75 – – 0.536 0.490 0.4875 – – 0.4874 2 0
3 0.65 0.67 0.70 0.75 – 0.52 0.469 0.455 0.465 – 0.4550 2 1
4 0.62 0.65 0.67 0.70 0.75 0.496 0.455 0.4355 0.434 0.45 0.4340 3 1
P C *
2 2 1 1f x P C f x
TERCERA ETAPA(Dibujo)
3 2x x 0 1 2 3 4 0 1 2 3 4 *
3 3f x *
2x *
3d
4 0.5 0.55 0.6 0.7 0.9 0.3 0.28875 0.2925 0.3185 0.3906 0.28875 1 3
P D *
3 3 2 2f x P D f x
Política óptima:
Leyendo las tablas de la última a la primera resulta
1 2 3
* * * *, , 1,0,3a d d d con *
3 4x , *
2 1x , *
1 1x y *
0 0x . Por lo tanto el
estudiante debe dedicar a estudiar Algebra una semana, ninguna a cálculo
51
y tres semanas a Dibujo. Además la probabilidad de continuar como
estudiante regular de la Universidad es 0.71125.
Ejemplo 4—2: El problema de Fabricación.
El presidente de una compañía de alimentos quiere saber cómo distribuir
de forma óptima las 9 unidades de materia prima que diariamente entran
a la empresa entre los tres productos que ellos fabrican. El producto A
necesita como mínimo 2 unidades, el producto B requiere 1 y el producto
C necesita 3. Sea iu el número de unidades que se utilizan de cada
producto. El costo de fabricación es 2
Au para A, 3 Bu
para B y 6 Cu
para C.
1. Justifique si es posible resolver este problema a través de
programación dinámica.
2. Si la respuesta de 1 es afirmativa, plantee el problema para su
resolución mediante programación Dinámica indicando sus
elementos.
3. Determine la política óptima.
Solución:
1. Es posible dividir este problema en tres sub problemas de decisión
interdependientes: Cantidad de materia prima a asignar a cada uno
de los productos A,B y C. lo que permite aplicar la Programación
dinámica.
2. Programación dinámica:
Etapas:
La Figura 4—3 muestra el esquema general de programación dinámica
para este ejemplo.
Variable de decisión:
Para este problema hay 3 variables de decisión por lo cual las
alternativas son de la forma 1 2 3 1, , , ,
i n
i A B Ci i iA a d d d u u u
en la cual
jd es el número de unidades de materia prima que asigna al producto
52
(etapa) j . Sus posibles valores son de 2 a 5, de 1 a 4 y de 3 a 6
respectivamente.
:iETAPA B
2 Bd u
2r
H
G
3 :ETAPA C
2x
3 Cd u
3r
3x H
G 2f 3f
1 :ETAPA A
0x
1 Ad u
1r
1x H
G 0f 1f
FABRICACIÓN
Figura 4—3: Diagrama de etapas para el problema de Fabricación
Variable de estado:
La variable de estado jx representa el número de unidades de materia
prima repartidas una vez se ha tomado la decisión del producto j . Es
fácil ver que 1 1,j j j j jx H x d x d . De acuerdo con la información
disponible los posibles valores del estado son 0 0x , 1 2,3,4,5x
,
2 3,4,5,6x , y 3 9x
Función de rendimiento:
jr mide la consecuencia de la decisión tomada en la j ésima etapa. En
este caso son los costos de fabricación de cada productos y con ello la
contribución de esa etapa al rendimiento total del sistema. 2
1 Ar u,
2 3 Br u, 3 6 Cr u
.
53
La función de rendimiento global R es el costo total de la fabricación de
los productos A, B y C. De modo que 1 2 3R r r r . Por su parte, el
rendimiento óptimo global es 1 2 3
*
1 2 3, ,d d d
R mín R mín r r r .
Ecuación recursiva del rendimiento:
La ecuación recursiva recoge el rendimiento acumulado hasta la etapa j ,
contemplando solo los rendimientos óptimos de cada etapa y descartando
el resto de valores correspondientes a políticas no óptimas.
0 0 0f x
*
1 1j j j j jf x r f x
Dadas las características del problema es posible ordenar los cálculos
para su solución de la siguiente manera:
PRIMERA ETAPA(Producto A)
Ecuación de transformación de la primera etapa: 1 0 1 1x x d d
Ecuación recursiva de la primera etapa: * 2
1 1 1 0 0 1 Af x r f x r u , siendo
1
*
1 1 1d
f x mín r .
1 0x x 0 *
1 1 1 1f x f x *
1d *
0x
2 4(2) 4 2 0
3 9(3) 9 3 0
4 16(4) 16 4 0 5 25(5) 25 5 0
1 1r d
SEGUNDA ETAPA(Producto B)
Ecuación de transformación de la segunda etapa: 2 1 2x x d entonces
2 2 1d x x .
54
Ecuación recursiva de la segunda etapa: * *
2 2 2 1 1 1 13 Bf x r f x u f x ,
siendo 2
* *
2 2 2 1 1d
f x mín r f x .
2 1x x 2 3 4 5 2 3 4 5 *
2 2f x *
2d *
1x
3 3(1) – – – 7 – – – 7 1 2 4 6(2) 3(1) – – 10 12 – – 10 2 2
5 9(3) 6(2) 3(1) – 13 15 19 – 13 3 2
6 12(4) 9(3) 6(2) 3(1) 16 18 22 28 16 4 2 2 2r d *
2 2 2 1 1f x r f x
TERCERA ETAPA(Producto C)
Ecuación de transformación de la tercera etapa: 3 2 39x x d entonces
3 29d x .
Ecuación recursiva de la tercera etapa: * *
3 3 3 2 2 2 26 Cf x r f x u f x ,
siendo 3
* *
3 3 3 2 2d
f x mín r f x .
3 2x x 3 4 5 6 3 4 5 6 *
3 3f x *
3d *
2x
9 36(6) 30(5) 24(4) 18(3) 43 40 37 34 34 3 6
3 3r d *
3 3 3 2 2f x r f x
3. Política óptima:
De la tercera tabla se obtiene *
3 9x y *
3 3d entonces *
2 6x . Por su parte
de la segunda tabla tenemos que si *
2 6x entonces *
2 4d y *
1 2x . Con
este resultado, en la primera tabla si *
1 2x entonces *
1 2d y *
0 0x .
Equivalentemente * *
1 1 2 3, , 2,4,3i i
A a d d d .
La política óptima es asignar dos unidades de materia prima al producto
A, cuatro al B y tres al C. Consiguiendo con esta asignación un costo
mínimo de 34 u.m.
55
Ejemplo 4—3: Modelo de programación lineal.
Resolver a través de programación dinámica el problema de
programación lineal formulado en el Ejemplo 3—1.
Solución:
Por conveniencia en la notación es posible rescribir el problema dado de
la siguiente manera:
1 2
1 2
1 2
1 2
3 2
. . 5 15
2 4 10
, 0
Máx Z d d
s a d d
d d
x x
Etapas:
La Figura 4—3 muestra el esquema general de programación dinámica
para este ejemplo. Nótese que se han definido dos etapas una por cada
una de las variables de decisión.
Variable de decisión:
En el problema de programación lineal planteado se pueden determinar
2 variables de decisión por lo cual las alternativas son de la forma
1 2 1,
i n
i i iA a d d
en la cual jd
es el nivel decidido para la j ésima
variable de decisión del modelo propuesto.
Variable de estado:
La variable de estado jx será la cantidad de recurso disponible después
de tomada la decisión de la etapa j . Ahora la variable de estado es
bidimensional, esto es:
2 2
1
2
:
, ,j
j j j j j
j
H
xr f x H r f
x
56
En donde cada k
jx se obtiene de la k ésima restricción del modelo de
programación lineal original y
1 j
k k k
j j jx x d representa la cantidad
disponible del k ésimo recurso; así que
j
k
jd es la cantidad del recurso
k consumido. Específicamente,
1
0
0 2
0
15
10
xx
x
11
0 11 1
1 2210 11
5 15 5
10 22
x dx dx
dx dx
1 1
2 1 1 1 2
2 2 21 22 1 1
15 5
10 2 44
x x d d dx
d dx x d
Posible valores para las variable de decisión:
Dadas las condiciones de no negatividad del modelo de programación
lineal, 0jd para 1,2j . Lo que significa que para las dos variables el
menor valor posible es 0.
Una observación cuidadosa a las restricciones del modelo permite
establecer los valores máximos para cada una. Si solamente existiera la
primera restricción, el mayor valor para 1d es 3 puesto que es el primer
valor que se asume de las variables de decisión. Este valor se obtiene 1
0 153
5 5
x . Ahora bien, si solamente existiera la segunda restricción, su
mayor valor sería
2
0 105
2 2
x . Puesto que se deben cumplir
simultáneamente ambas restricciones 1 0,3d .
Al llegar a la segunda etapa ya se tiene el valor de 1d . Y de forma similar
se puede deducir el mayor posible valor para 2d . Si solamente existiera
57
la primera restricción, el mayor valor para 2d será
1
1115 5
1
xd . Ahora
bien, si solamente existiera la segunda restricción, su mayor valor sería 2
1 110 2
4 4
x d . Puesto que se deben cumplir simultáneamente ambas
restricciones 1
2 1
10 20, 15 5 ,
4
dd mín d
.
2ETAPA
2
1 02 00, ,
4
xd mín x
2 22r d
1
1 2
2 2
1 24
x dx
x d
H
G 3 3 0f x
1ETAPA
1 0,3d
1 13r d
H
G
Programación Lineal
1
0
0 2
0
15
10
xx
x
*
3 3 3 3 2f x f x r *
1 1 2 2 1f x f x r
1
0 1
1 2
0 14
x dx
x d
Figura 4—4: Elementos del problema de Programación lineal.
Función de rendimiento:
jr mide la consecuencia sobre la función objetivo de la decisión tomada
en la j ésima etapa. En este caso son las ganancias que aportan al
modelo la decisión j ésima . Esto es 1 13r d, 2 22r d .
La función de rendimiento global Z es la ganancia (función objetivo). De
modo que 1 2Z r r . Por su parte, el rendimiento óptimo global es
1 2
*
1 2,d d
Z máx Z más r r . Con lo cual la función recursiva es
*
1j j jf f r . Específicamente,
58
3 0f
*
2 3 2 2 22f f r r d
* * *
1 2 1 2 1 2 12 3f f r r r d d
SEGUNDA ETAPA
Aquí,
1
2 1
10 20, 15 5 ,
4
dd mín d
y
*
2 3 2 2 22f f r r d luego *
2 22f máx d . Obsérvese que al ser una
función lineal de pendiente positiva, su máximo se alcanzará en el
extremo derecho del intervalo. En consecuencia,
* 12 1
10 215 5 ,
4
dd mín d
y
* 12 1
10 22 15 5 ,
4
df mín d
o escrito de
otra manera:
1 1* 12 1 1
1
15 5 2.777810 2
15 5 , 10 24 2.7778
4
d Si dd
d mín d dSi d
y
1 1* 1
2 1 11
30 10 2.777810 2
2 15 5 , 10 24 2.7778
2
d Si dd
f mín d dSi d
PRIMERA ETAPA
De manera similar,
1 0,3d y
59
1 1 1 1*
1 2 1 1 1 11 1
30 10 2.7778 30 7 2.7778,3
3 10 2 10 42.7778 0,2.7778,3
2 2
d Si d d Si d
f f r d d dSi d Si d
1 1*
1 1 11
30 7 2.7778,3
10 40,2.7778,3
2
d Si d
f máxf máx dSi d
.
Luego *
1 2.7778d y *
1 10,5555f . Como también
* 12 1
10 215 5 ,
4
dd mín d
.
10 2 2.777815 5 2.7778,
4mín
1.1111 con *
1 10,5555f .
La política óptima es adoptar a decisión óptima
* * * *
1 1 2 11 1, 2.7778,1.1111
i n
iA a d d
con un valor óptimo de la función
objetivo * 10.5555Z .
4.3 PROGRAMACIÓN DINÁMICA ESTOCÁSTICA
En esencia, el planteamiento del modelo es el mismo en la programación
dinámica determinística que en la estocástica. Véase la Figura 4—1. La
diferencia está en que en programación dinámica estocástica tanto las
variables x de estado como los retornos jr son de naturaleza estocástica
y, por lo tanto, tendrán asociadas funciones de densidad de probabilidad.
Formalmente hablando XX f x o /y jj R jR f r .
Este hecho hace que el problema de la programación estocástica se
enmarque dentro de la teoría de decisiones bajo riesgo. En consecuencia,
el criterio de decisión racional será, principalmente, optimizar el valor
esperado de la función de rendimiento global.
Ejemplo 4—4: El problema de inversión.
Una persona quiere invertir $C miles en el mercado de valores durante los
siguientes n años. El plan de inversión requiere comprar las acciones al
60
inicio del año y venderlas al final del mismo año. Posteriormente, el
dinero acumulado se puede reinvertir (todo o parte) al inicio del siguiente
año. El grado de riesgo en la inversión se representa expresando el
rendimiento en forma probabilística. Un estudio del mercado muestra
que el rendimiento sobre la inversión está afectado por m (favorable o
desfavorable) condiciones de mercado y que la condición j da un
rendimiento jr nn con probabilidad jp con 1,2, ,j m ¿Cómo debe
invertir la cantidad $C para conseguir la acumulación más alta al final de
los n años?
Solución:
En este caso las etapas están representando a los años, las alternativas
serán los jd que corresponden a los montos de capital invertidos en ese
año mientras que el estado jx del sistema será el capital que queda
después de tomar la decisión en el respectivo año. Los resultados de cada
etapa serán jr . Que representan el capital invertido actualizado con su
ganancia o pérdida. La función de transformación es tal que ella actualiza
el estado de la siguiente forma 1j k j j j j k jx d x d x d
Finalmente, el rendimiento global es *
10
1j j
m
i k j j k jd x
k
f máx p f x d
.
Nótese que 1 1 1n n nf x x . Puesto que ninguna inversión ocurre luego del
año n .
4.4 APLICACIONES.
Son diversas las aplicaciones de la programación dinámica.
Prácticamente en todas las áreas del conocimiento se encuentran
aplicaciones: Derecho, Ingeniería, matemáticas, economía, etc. En
particular, la programación dinámica, bien sea estocástica o
determinística, tendrá una aplicación directa en los modelos de decisión
markoviamos y en teoría de juegos que se discutirán más adelante.
61
4.5 EJERCICIOS
4.6 RESUMEN DEL CAPÍTULO
62
5 PROCESOS ESTOCÁSTICOS
Ejemplo 5—1: Borrachito.
Suponga que un borracho se encuentra en el borde de un precipicio, si da
un paso hacia delante, él caerá en el abismo. Nuestro borracho da pasos
aleatorios, es decir hacia el precipicio o en sentido contrario
indiferentemente, si la probabilidad de que el borracho de el paso hacia el
precipicio es 1/ 3 y la probabilidad de que se aleje de este es 2 / 3 , cual es la
probabilidad de que nuestro borracho se salve.
5.1 INTRODUCCIÓN
Una generalización interesante del concepto de vector aleatorio se
encuentra en la idea de proceso estocástico. En un proceso estocástico,
las estructuras probabilísticas de los vectores aleatorios dependen del
tiempo y del espacio en el cual se desenvuelvan las variables del vector.
5.2 DEFINICIÓN
Definición 5—1: Proceso Estocástico.
Un Proceso estocástico es una familia de variables aleatorias indexadas
por el tiempo ,tZ
, donde pertenece al espacio muestral y t pertenece
al conjunto de índices.
Observación 5—1
Para un t fijo, ,tZ
es una variable aleatoria. Mientras que para un
dado, ,tZ
es una función de t , llamada función muestral o realización.
La población que consiste en todas las posibles realizaciones se denomina
el conjunto de series de tiempo del proceso.
Se asume que el conjunto de índices serán los enteros, a menos que se
establezca lo contrario. Considere un conjunto finito de variables
aleatorias 1 2, , ,
nt t tZ Z Z de un proceso estocástico ,
: 0, 1, 2,t
Z t
, La
distribución n -dimensional (conjunta)está definida como
63
1 11, , : , , , ,
n nt t t n tF z z p z t z z t z
Definición 5—2: Proceso Estocástico estacionario.
1. Se dice que un proceso estocástico es estacionario en distribución
de primer orden si su función de distribución uni -dimensional es
invariante al tiempo, es decir, si 1 1t t kF z F z para todo
1t y k
en los enteros,
2. estacionario en distribución si 1 2 1 2, ,t t t k t kF z z F z z , y
estacionario de n -ésimo orden si 1 1, , , ,
k nt tn t t kF z z F z z ,
Para cualquier n -úpla 1, , nt t y k en los enteros.
3. Un proceso se dice estrictamente estacionario si
1 1, , , ,
k nt tn t t kF z z F z z es valido para todo n , es decir,
1,2,n . También denotada por estacionariedad fuerte o completa.
Observación 5—2
1. Claramente si 1 1, , , ,
k nt tn t t kF z z F z z es valida para n m ,
también será verdadera para n m porque la función de
distribución de orden m determina todas las funciones de
distribución de orden menor. Por lo tanto, que una función de
distribución de orden superior sea estacionaria, siempre determina
que las funciones de distribución que sean de orden menor que ella
también lo sean.
2. Es posible entender adecuadamente lo que es ser un proceso
estocástico ,tZ
, como un conjunto de variables aleatorias definidas
sobre un espacio muestral indexadas por el tiempo. Usualmente se
suprime y simplemente se escribe ,tZ
como t
Z o tZ , también
denotamos la variable aleatoria por X o por X
. El proceso
estocástico es llamado proceso de valor real, si solamente asume
valores en , el conjunto de los números reales, a menos que se
64
establezca lo contrario, solo trabajaremos con procesos de valor
real.
Definición 5—3: Función de media del proceso estocástico.
Para un proceso de valor real : 0, 1, 2,tZ t , definimos la función de
media del proceso como t tE Z .
Definición 5—4: Función de varianza del proceso estocástico.
Para un proceso de valor real : 0, 1, 2,tZ t , definimos la función de e
varianza del proceso 2
t t tE Z
Definición 5—5: Función de covarianza del proceso estocástico.
Para un proceso de valor real : 0, 1, 2,tZ t , definimos La función de
covarianza del proceso entre 1t
Z y 2t
Z
1 1 2 21 2, t t t tt t E Z Z
Y la función de correlación entre 1t
Z y 2t
Z
1 2
1 2
1 2 2 2
,,
t t
t tt t
Observación 5—3
1. Para un proceso estacionario estricto, la función de distribución es
la misma para todo t , la función de media t es una constante,
siempre que tE Z .
2. Igualmente, si tE Z entonces 1
2 2 para todo t , por lo tanto
es también una constante.
3. Además, puesto que 1 2 1 2, ,t t t k t kF z z F z z para todo 1 2,t t en los
enteros y k , tenemos 1 2 1 2, ,t t t k t k y 1 2 1 2, ,t t t k t k
tomando 1t t k y 2t t , tenemos 2 1, , , kt t t k t t t k y
1 2, , , kt t t k t t t k .
65
4. Entonces, para un proceso estrictamente estacionario, con los dos
primeros momentos finitos, la covarianza y la correlación entre tZ
y t kZ
, depende solo de la diferencia del tiempo k .
Un ejemplo trivial de estacionariedad fuerte es una secuencia de
experimentos relacionados a variables aleatorias independientes e
idénticamente distribuidas. Esta secuencia de variables aleatorias
independientes usualmente no existe o no interesan en procesos
estocásticos o series de tiempo. Sin embargo distinto de este simple caso,
en el que son independientes e idénticamente distribuidas, es muy difícil
o imposible actualmente, verificar la función de distribución,
particularmente la distribución conjunta de una serie de tiempo
observada. Entonces, en análisis de procesos estocásticos (series de
tiempo), frecuentemente usamos estacionariedad más débil en términos
de los momentos del proceso.
Un proceso se dice de orden n -ésimo débil si todos los momentos
conjuntos de orden superior a n existen y son invariantes al tiempo, por
ejemplo, independientes del momento de origen. Por lo tanto, un proceso
de segundo orden tendrá media y varianza constantes, y la función de
covarianzas y correlación solo dependerá de la diferencia en el tiempo.
Algunas veces, el sentido de estacionariedad en el sentido débil, o
varianza estacionaria, son también utilizados para describir procesos de
segundo orden débil. Se sigue de las definiciones que los procesos
estrictamente estacionarios con los dos primeros momentos finitos
también son procesos de segundo orden débil, o de covarianza
estacionaria. Sin embargo, un proceso estrictamente estacionario, podria
no tener momentos finitos, por lo tanto, no tendría covarianza
estacionaria. Un ejemplo trivial es el proceso que consiste en una
secuencia de variables aleatorias independientes e idénticamente
distribuidas con distribución Cauchy. Claramente el proceso es
estrictamente estacionario, pero no es débilmente estacionario, de
cualquier orden, pues no existen los momentos conjuntos de ningún
orden.
66
Ejemplo 5—2
Considere la siguiente secuencia en el tiempo:
tZ Asen t
Donde a A es una variable aleatoria con media cero y varianza uno y es
una variable aleatoria con distribución uniforme en el intervalo , ,
independiente de A . Entonces:
0tE Z E A E sen t
2
t t kE Z Z E A sen t sen t k
2 1cos cos 2 2
2E A E k t k
1 1
cos cos 2 22 2
k E t k
1 1 1
cos cos 2 22 2 2
k t k d
1 1
cos 2 22 8
k sen t k
1
cos2
k
El cual depende solo de la diferencia en el tiempo k . Entonces el proceso
es de varianza estacionaria
Ejemplo 5—3
Sea tZ una secuencia de variables aleatorias independientes
provenientes, alternadamente, de una distribución normal estándar
67
0,1N y dos valores 1 y 1 cada uno con probabilidad 1
2, claramente,
0tE Z y 2 1t
E Z para todo t . Ahora
0,
,1,
t s
si t sE Z Z
si t s
Y
2 2
0,,
1,
t s
t s
si t sE Z Zt s
si t sE Z E Z
De donde, el proceso es de varianza estacionaria. Sin embargo, el proceso
no es estrictamente estacionario. De hecho, no es estacionario en
distribución de ningún orden.
Definición 5—6: Proceso estocástico gaussiano.
Un proceso estocástico se dice normal o proceso Gaussiano si su función
de distribución conjunta es normal.
Observación 5—4
1. Puesto que una distribución normal está caracterizada por sus dos
primeros momentos, la estacionariedad estricta y la
estacionariedad débil son equivalentes en un proceso Gaussiano.
5.3 LAS FUNCIONES DE AUTOCOVARIANZA Y AUTOCORRELACIÓN
Definición 5—7: Función de autocavarianza.
Sea tZ un proceso estacionario, tenemos el valor esperado tE Z y la
varianza 2 2
t tVar Z E Z , las cuales son constantes, y las
covarianzas ,t sCov Z Z , las cuales dependen solo de la diferencia del
tiempo t s . Por lo tanto, en este caso, se escribe la covarianza entre tZ y
t kZ como:
68
,k t t k t t kCov Z Z E Z Z
Definición 5—8: Función de autocorrelación .
Sea tZ un proceso estacionario, tenemos el valor esperado tE Z y la
varianza 2 2
t tVar Z E Z , las cuales son constantes, y las
covarianzas ,t sCov Z Z , las cuales dependen solo de la diferencia del
tiempo t s . Por lo tanto, en este caso, se escribe la autocorrelación entre
tZ y t kZ
como:
0
,t t k kk
t t k
Cov Z Z
Var Z Var Z
Donde notamos que 0t t kVar Z Var Z . Como función de k , k es
llamada la función de autocovarianza y k es llamada la función de
Autocorrelación (FAC) en analisis de series de tiempo representaremos la
covarianza y la correlacion entre tZ y t kZ , de el mismo porceso , separado
solo por los desfaces de tiempo k .
Es facil ver que un proceso estocástico estacionario la función de
covarianza k , y la función de correlacion k cumplen con las siguientes
propiedades:
1. 0 0: 1tVar Z
2. 0 : 1k k
3. k k y k k para todo k , por ejemplo, k y k son funciones
simetricas, por lo tanto simetricas alrededor del origen, 0k . Se
sigue, de hecho que la diferencia del tiempo entre tZ y t kZ y tZ y
t kZ es la misma. Por lo tanto, la función es graficada solo para
valores no negativos como se muestra en la ilustración 1. esta
grafica es frecuentemente llamada correlograma.
69
5.4 FUNCION DE AUTOCORRELACIÓN PARCIAL
Definición 5—9: Función de autocorrelación parcial kk .
A la correlacion entre tZ y t kZ , después de que su dependencia lineal en
el rango de intervalo de las variables 1 2,, ,t tZ Z
y 1t kZ se ha suprimido,
esta es la siguiente correlacion condicional:
1 1, | , ,kk t t k t t kCorr Z Z Z Z
Usando la regla de cramer para 1,2, ,k tenemos que:
11 1
1
1 2
22
1
1
1
1
1
1 1
1 2
2 1 3
33
1 2
1 1
2 1
1
1
1
1
1
1 2 2 1
1 2 3 2
1 2 3 1
1 2 2 1
1 2 3 2
1 2 3 1
1
1
1
1
1
k
k
k k k k
kk
k k
k k
k k k
70
5.5 PROCESOS CON RUIDO BLANCO 2 0
0 0
a
k
k
k
5.6 CADENAS DE MARKOV EN TIEMPO DISCRETO
Como se dijo un proceso estocástico ,X X t t T es una colección de
variables aleatorias, es decir para cada t perteneciente al conjunto de
valores T, X t es una variable aleatoria. Interpretamos a menudo t como
un tiempo y llamamos a X t el estado del proceso en un tiempo t. Si el
conjunto de valores T es contable (discreto), entonces X es un proceso
estocástico discreto, mientras que si T consta de un continuo de posibles
valores, entonces X es un proceso estocástico continuo.
Definición 5—10: Proceso estocástico discreto.
Consideraremos un proceso estocástico discreto nX , 0,1,2,3n que toma
un finito o contable número de posibles valores.
Observación 5—5
1. A menos que se mencionara de otra manera, el conjunto de los
posibles valores pude ser denotado como el conjunto de enteros no
negativos 0,1,2 .
2. Si nX i entonces se dice que el proceso se encuentra en el estado i
en el tiempo n.
Definición 5—11: Cadena de Markov.
Cuando siempre que el proceso este en un estado i, hay una probabilidad
fija ,i jP que el siguiente estado pase al estado j, es decir
1 1 1 0 0 ,, , ,n n n n i jP X j X i X i X i P , para todos los estados
0 1, , ,ni i i j y todo los 0n . Tal proceso estocástico es conocido como la
cadena de Markov.
Observación 5—6
71
1. La distribución condicional de cualquier estado futuro 1nX , dados
los pasados estados 0 1 1, , , nX X X
y el presente estado nx , es
independiente de los pasados estados y depende solamente del
presente estado. Es decir, determinado el presente estado, el
pasado y el futuro estado de una cadena de Harkov son
independientes.
2. El valor de ,i jP representa la probabilidad de que el proceso,
estando en un estado i, haga una transición a un estado j. Como las
probabilidades no son negativas y el proceso debe hacer una
transición en algunos estados , 0i jP , 1i j
j
P
3. La letra P denota la matriz de probabilidades de transición en cada
paso ,i jP
0,0 0,1 0,
1,0 1,1 1,
,0 ,1 ,
j
j
i i i j
P P P
P P P
P
P P P
Ejemplo1.1.1 Considere un sistema de comunicación que transmite los dígitos o y 1.
Cada digito transmitido debe pasar a través de algunas etapas, en cada
una de las cuales hay una probabilidad p que el digito puesto no cambiara
cuando parta. La letra nX denota que el digito entrado es la van etapa,
entonces ¨ , 0nX n es una cadena de Harkov de dos estados teniendo una
matriz de probabilidad de transición
1
1
p pP
p p
Ejemplo1.1.2 Suponga que si llueve hoy depende de las condiciones climáticas de los
dos últimos días. Específicamente, suponga que si ha llovido durante los
dos últimos días, entonces mañana lloverá con 0.7 de probabilidad; si
72
llovió hoy pero no ayer, entonces mañana lloverá con 0.5 de probabilidad;
si llovió ayer pero no hoy, entonces mañana lloverá con 0.4 de
probabilidad; si no ha llovido en los dos últimos días, entonces mañana
lloverá con 0.2 de probabilidad.
Si dejamos que el estado del tiempo n dependa de si llueve en el día n,
entonces el precedente no sería una cadena de Markov (¿Por Qué no?).
Sin embargo, podemos transformarlo en una cadena de Markov dejando
que el estado durante cualquier día dependa de las condiciones
meteorológicas de ese día y los precedentes. Por ejemplo, podemos decir
que el proceso está en
Estado 0 Si llovió tanto hoy como ayer.
Estado 1 Si llovió hoy pero no ayer.
Estado 2 Si llovió ayer pero no hoy.
Estado 3 Sino llovió, ni hoy ni ayer.
El precedente entonces representaría una cadena de Markov de cuatro
estados cuya matriz de probabilidad de transición se muestra fácilmente:
0.7 0 0.3 0
0.5 0 0.5 0
0 0.4 0 0.6
0 0.2 0 0.8
P
5.7 ECUACIONES DE CHAPMAN–KOLMOGOROV
La probabilidad de transición de n pasos ,
n
i jP de la cadena de Markov es
definida como la probabilidad condicional, dado que la cadena esta
actualmente en un estado i, que será estad j después de una adicional
transición de n, es decir
73
,
n
i j n m mP P X j X i , 0n , i , 0j
Por supuesto 1
, ,i j i jP P . La ecuación de Chapman-Kolmogorov provee un
método de computación para esta probabilidad de n pasos. Esta ecuación
es , , ,
0
n m n m
i j i k k j
k
P P P
y son obtenidos por nada , ,
n m
i k k jP P es la probabilidad que la
cadena, actualmente en el estado i , vaya al estado j después de n m
transiciones por un camino que lo lleva a un estado k en la van transición.
Por lo tanto, sumar estas probabilidades durante todos los estados
intermedio k produce la probabilidad de que el proceso estará en el
estado j después de n m transiciones. Formalmente, tenemos
, 0¨n m
i j n mP P X j X i
0
0
,n m n
k
P X j X k X i
0 0
0
,n m n n
k
P X j X k X i P X k X i
, ,
0
m n
k j i k
k
P P
Si denotamos a nP como la matriz reprobabilidad de transición de n
pasos ,
n
i jP , entonces la ecuación de Chapman – Kolmogorov Afirma que
n mn mP P P
Donde el punto representa la matriz de multiplicación Hence
74
2 1 1 2P P P P P
Y, por la inducción,
1 1 1n n n nP P P P P
Es decir, los n-pasos de la matriz de probabilidad de transición pueden
ser obtenidos multiplicando la matriz P por si misma n veces.
Ejemplo 1.2.1 Suponga, en el ejemplo 1.1.2 que llovió Tato el lunes como
el martes. ¿Cual es la probabilidad de que llueva el jueves?
Solución: Como la matriz de probabilidad de transición es
0.7 0 0.3 0
0.5 0 0.5 0
0 0.4 0 0.6
0 0.2 0 0.8
P
El segundo paso de la matriz de probabilidad de transición es
0.49 0.12 0.21 0.18
0.35 0.20 0.15 0.30
0.20 0.12 0.20 0.48
0.10 0.16 0.10 0.64
P
75
Porque la cadena en el estado 0 el martes, y porque lloverá el jueves si la
cadena está en el estado 0 o en el estado 1 durante el día, la probabilidad
deseada es
2 2
0,0 0,1 0.49 0.12 0.61P P
5.7.1 INTRODUCCIÓN
5.7.2 ECUACIONES DE CHAPMAN–KOLMOGOROV
5.7.3 CLASIFICACIÓN DE LOS ESTADOS
5.8 CADENAS DE MARKOV DE TIEMPO CONTINUO
5.8.1 INTRODUCCIÓN
5.8.2 DEFINICIÓN
5.8.3 PROCESOS DE NACIMIENTO Y MUERTE
5.8.4 FUNCIÓN DE TRANSICIÓN DE PROBABILIDAD
76
5.8.5 REVERSIBILIDAD
5.9 DISTRIBUCIÓN EXPONENCIAL Y EL PROCESO DE POISSON
5.9.1 INTRODUCCIÓN
5.9.2 DEFINICIÓN DE PROCESO DE POISSON
5.9.3 DISTRIBUCIONES DE LOS TIEMPOS ENTRE LLEGADAS Y DE ESPERAS
5.9.4 PROCESO DE POISSON NO HOMOGÉNEO
5.10 **TEORÍA DE RENOVACIÓN
5.11 EJERCICIOS
5.12 RESUMEN DEL CAPÍTULO
6 TEORÍA DE COLAS
6.1 INTRODUCCIÓN
77
6.2 ESTRUCTURA GENERAL DE UN SISTEMA DE LÍNEAS DE ESPERA
6.3 NOTACIÓN DE KENDALL
6.4 LEY DE LITTLE
6.5 TEOREMA DE BURKE
6.6 MODELO / /1M M
EN DETALLE
6.7 ***OTROS MODELOS
6.8 EJERCICIOS
6.9 RESUMEN DEL CAPÍTULO
7 TEORÍA DE INVENTARIOS
7.1 INTRODUCCIÓN
78
7.2 MODELOS DE INVENTARIOS DETERMINÍSTICOS
7.3 MODELOS DE INVENTARIOS ESTOCÁSTCOS
7.4 APLICACIONES
7.5 EJERCICIOS
7.6 RESUMEN DEL CAPÍTULO
8 TEORÍA DE JUEGOS
8.1 INTRODUCCIÓN
8.2 JUEGOS COOPERATIVOS
79
8.3 JUEGOS NO COOPERATIVOS
8.4 EQUILIBRIOS
8.5 ANÁLISIS DE CONFLICTOS
8.6 EJERCICIOS
8.7 RESUMEN DEL CAPÍTULO
9 EL FUTURO DE LA INVESTIGACIÓN OPERACIONAL
ESTOCÁSTICA
iv. REFERENCIAS BIBLIOGRÁFICAS
v. ÍNDICE
80
