INDICE
MTODO CON ETAPAS INFINITAS......................................................................2
1.
MTODO DE ENUMERACIN EXHAUSTIVA...........................................5
2.
METODO DE ITERACIN DE POLITICA SIN DESCUENTO.......................9
3.
MTODO DE ITERACIN DE POLTICA CON DESCUENTO....................15
CONCLUSIONES.......................................................................................... 19
BIBLIOGRAFIA............................................................................................ 19
MTODO CON ETAPAS INFINITAS
Hay dos mtodos para resolver el problema con etapas infinitas. En el primero se deben
evaluar todas las polticas estacionarias del problema de decisin. Esto equivale a un proceso
de enumeracin exhaustiva y slo se puede usar si la cantidad de polticas estacionarias es
razonablemente pequea. El segundo mtodo, llamado iteracin de poltica, en general es ms
eficiente, porque determina en forma iterativa la poltica ptima (Thaja, 2004)
Ejemplo
Cada ao, al comenzar la estacin para trabajar los jardines (de marzo a septiembre) un
jardinero usa una prueba qumica para determinar el estado del suelo. Dependiendo de los
resultados de las pruebas, la productividad para la nueva estacin cae en uno de tres estados:
1) bueno, 2) regular y 3) malo.
A travs de los aos el jardinero observ que las condiciones meteorolgicas prevalecientes
durante el invierno (de octubre a febrero) juegan un papel importante en la determinacin de
la condicin del suelo, dejndolo igual o empeorndolo, pero nunca mejorndolo. En este
respecto, el estado del suelo en el ao anterior es un factor importante para la productividad
del presente ao. Usando los datos de las pruebas hechas por el jardinero, las probabilidades
de transicin durante un periodo de un ao, de un estado de productividad a otro, se
representa con la siguiente cadena de Markov: (Thaja, 2004)
Las probabilidades de transicin en P1 indican que la productividad de determinado ao no
puede ser mejor que la del ao anterior. Por ejemplo, si las condiciones del suelo en el
presente ao son regulares (estado 2), la productividad en el prximo ao permanecer regular
con una probabilidad de 0.5, o se volvern malas (estado 3) con una probabilidad de 0.5.
(Thaja, 2004)
El jardinero puede alterar las probabilidades de transicin P1 con otras acciones. En el caso
normal, se aplica fertilizante para mejorar las condiciones del suelo, y se produce la siguiente
matriz de transicin: (Thaja, 2004)
Para poner en perspectiva el problema de decisin, el jardinero asocia una funcin de ingreso
(o una estructura de recompensa) con la transicin de un estado a otro. La funcin de ingreso
expresa la ganancia o la prdida durante un periodo de 1 ao, dependiendo de los estados
entre los que se hace la transicin. Como el jardinero tiene la opcin de usar fertilizante o no,
la ganancia o la prdida varan dependiendo de la decisin tomada. Las matrices R1 y R2
resumen las funciones de ingreso, en cientos de $, correspondientes a las matrices P1 y P2,
respectivamente (Thaja, 2004)
Los elementos rij2 de R2 tienen en cuenta el costo de aplicar el fertilizante. Por ejemplo, si las
condiciones del suelo fueron regulares el ao anterior (estado 2) y se vuelven malas (estado 3)
en este ao, su ganancia ser r 23
= 0 en comparacin con r 23 1= 1 cuando no se usa
fertilizante. (Thaja, 2004)
A este respecto, R expresa la recompensa neta despus de haber introducido el costo del
fertilizante.
Qu clase de problema de decisin tiene el jardinero? Primero, se debe conocer si la
actividad de jardinera continuar durante una cantidad limitada de aos, o en forma
indefinida. Aestos casos se les llama problemas de decisin con etapas finitas o con etapas
infinitas. En ambos casos, el jardinero usa el resultado de las pruebas qumicas (estado del
sistema) para determinar la mejor accin (fertilizar o no) que maximice el ingreso esperado.
(Thaja, 2004)
Tambin, al jardinero le puede interesar evaluar el ingreso esperado que resulte de las
acciones especificadas de antemano para determinado estado del sistema. Por ejemplo, se
puede aplicar fertilizante siempre que las condiciones del suelo sean malas (estado 3). Se dice
que el proceso de toma de decisiones en este caso se representa por una poltica estacionaria.
(Thaja, 2004)
Cada poltica estacionaria corresponder a matrices de transicin y de ingreso distintas, que se
obtienen a partir de las matrices P1, P2, R1 y R2. Por ejemplo, para la poltica estacionaria de
aplicar fertilizante slo cuando las condiciones del suelo sean malas (estado 3), las matrices
resultantes de transicin y de ingreso son: (Thaja, 2004)
Estas matrices son distintas de P1 y R1 slo en los terceros renglones, que se toman
directamente de P2 y R2, las matrices asociadas con la aplicacin del fertilizante (Thaja,
2004)
1. MTODO DE ENUMERACIN EXHAUSTIVA
Consiste en enumerar todas las soluciones posibles, a partir de los valores tomados
para las variables enteras y realizar todas las combinaciones posibles hasta encontrar
una combinacin que nos proporcione el valor ptimo de la funcin objetivo y que
cumpla con todas las restricciones del problema. Una de las objeciones principales que
presenta ste mtodo es el nmero de variables, ya que se presentan demasiadas
combinaciones antes de encontrar la solucin ptima. (Thaja, 2004)
Supongamos que el problema de decisin tiene S polticas estacionarias, y
supondremos que
Ps
Rs
son las matrices de transicin y de ingreso (de un
paso) correspondientes a la poltica, s = 1, 2, ..., S. Los pasos del mtodo de
enumeracin son los siguientes: (Thaja, 2004)
Paso 1. Calcule
V si , el ingreso esperado de un paso (un periodo) de la poltica s,
dado el estado i, i = 1, 2, ..., m. (Thaja, 2004)
Paso 2. Calcule
transicin
si , las probabilidades estacionarias a largo plazo de la matriz de
asociadas con la poltica s. Estas probabilidades, cuando existen, se
calculan con las ecuaciones (Thaja, 2004)
5
Paso 3. Determine
, el ingreso esperado de la poltica s por paso (periodo) de
transicin, con la frmula (Thaja, 2004)
Paso 4. Se determina la poltica ptima s* tal que: (Thaja, 2004)
Ilustraremos el mtodo resolviendo el problema del jardinero con un horizonte de
planeacin de periodos infinitos. (Thaja, 2004)
Ejemplo:
El problema del jardinero tiene un total de ocho polticas estacionarias, como se ve en
la siguiente tabla: (Thaja, 2004)
Las matrices
de las polticas 3 a 8 se deducen de las correspondientes
a las polticas 1 y 2, y son las siguientes:
s
As, se pueden calcular los valores de V i que aparecen en la tabla siguiente:
Los clculos de las
probabilidades
estacionarias se hacen
con las ecuaciones
Por ejemplo, si s =2, las ecuaciones correspondientes son
(Observe que una de las tres primeras ecuaciones es redundante.) La solucin es:
7
En este caso, el ingreso anual esperado es:
En la tabla siguiente se resumen
Es
para todas las polticas estacionarias.
(Aunque no afectar esto a los clculos en modo alguno, observe que cada una de las
polticas 1, 3, 4 y 6 tiene un estado absorbente: el estado 3. Es la razn por la que
1= 2=0
y 3
= 1 para todas esas polticas.) (Thaja, 2004)
La poltica 2 produce el mximo ingreso anual esperado. La poltica ptima a largo
plazo es aplicar fertilizante independientemente del estado del sistema. (Thaja, 2004)
2. METODO DE ITERACIN DE POLITICA SIN DESCUENTO
El mtodo de iteracin por poltica est basado principalmente en el desarrollo
siguiente. Para cualquier poltica especfica el rendimiento total esperado en la etapa n
se expresa atraves de la ecuacin recursiva (Thaja, 2004)
m
f n ( i )=v i+ P ij f n+1 ( j ) , i=1,2, .. ,m
j=1
Esta accin recursiva es la base del desarrollo del mtodo de iteracin de poltica. Sin
embargo, se debe modificar un poco la forma actual, para permitir el estudio del
comportamiento asinttico del proceso. Se definir como la cantidad de etapas
restantes por considerar. Es distinto de n en la ecuacin, que define a la etapa n. La
ecuacin recursiva se escribe entonces como sigue: (Thaja, 2004)
f ( i )=v i+ P ij f 1 ( j ) , i=1,2,3,. .. , m
j=1
Obsrvese que f es el ingreso esperado acumulado si
es la cantidad de etapas
que faltan por considerar. Con la nueva definicin, se puede estudiar el
comportamiento asinttico del proceso haciendo que
Ham04 \l 13322
CITATION
(Thaja, 2004)
Ya que
=( 1 , 2 , . , m)
Es el vector de probabilidades de estado estable de la matriz de transicin
P= pij y
=( 1 v 1 , 2 v 2 + . , m v m )
es el ingreso esperado por etapa, como se calcul en el problema anterior, se puede
demostrar que cuando es muy grande, (Thaja, 2004)
f ( i )=E+ f (i)
Donde
f ( i ) es un trmino constante que representa la interseccin asinttica de
f dado el estado i
Ya que f ( i )
es el ingreso ptimo acumulado cuando hay
dado el estado i
y como E
forma intuitiva por qu f ( i )
es el ingreso esperado por etapa, se puede ver en
es igual a
para tener en cuenta el estado especfico i
etapas restantes,
CITATION Ham04 \l 13322
ms un factor de correccin f (i)
. En este resultado se supone que
(Thaja, 2004)
Ahora, con esta informacin, la ecuacin recursiva se escribe como sigue:
10
E+ f (i ) =v i + Pij {( 1 ) E+f ( j) } ,i=1,2, . , m
j=1
Luego se simplifica y se obtiene
m
E+ f ( i ) P ij f ( j ) =v i ,i =1,2, . , m
j=1
En este caso hay
ecuaciones con
+1 incgnitas, f(1), f(2), ..., f(m) y E.
(Thaja, 2004)
Como en el problema anterior , el objetivo es determinar la poltica ptima que
produce el valor mximo de E . Como hay
incgnitas, el valor ptimo de
ecuaciones con m+ 1
no se puede determinar en un paso. En lugar de
ello se usa un mtodo iterativo de dos pasos que, a partir de una poltica arbitraria,
determina una nueva poltica que produce un valor mejor de E . (Thaja, 2004)
El proceso iterativo termina cuando hay dos polticas sucesivas que son idnticas.
1 Paso de determinacin de valor: Se elige la poltica s en forma arbitraria. Con sus
matrices correspondientes
Ps
Rs y suponiendo, en forma arbitraria, que
f s ( m ) =0 , se resuelven las ecuaciones (Thaja, 2004)
m
E + f ( i ) P ij f ( j )=v i , i=1,2, . ,m
S
j=1
11
Con las incgnitas
, f
(1),..., y f
(m 1). Continuar en el paso de
mejoramiento de poltica
2 Paso de mejoramiento de poltica: Para cada estado i, determinar la poltica t que
corresponde a (Thaja, 2004)
Los valores de
f s ( j ) , j=1,2, ., m son los que se determinan en el paso de
determinacin de valor. Las decisiones ptimas resultantes para los estados 1, 2, ..., y
m son la nueva poltica t. Si s y t son idnticas, t es ptima. En caso contrario, hacer s
= t y regresar al paso de determinacin de valor. (Thaja, 2004)
Ejemplo
Se resolver el problema del jardinero con el mtodo de iteracin de poltica. Se
comienza con la poltica arbitraria que indica no aplicar fertilizante. Las matrices
correspondientes son (Thaja, 2004)
Las ecuaciones del paso de iteracin de valores son
12
Si
en
forma
arbitraria f(3) = 0, la solucin de las ecuaciones es
Continuacin se aplica el paso de mejoramiento de poltica. Los clculos
correspondientes se ven en el cuadro siguiente. (Thaja, 2004)
Cuadro n 01 mejoramiento de la calidad
Fuente: investigacin de operaciones
La nueva poltica indica aplicar fertilizante independientemente del estado. Como es
distinta de la anterior, se hace de nuevo el paso de determinacin de valor. Las
matrices correspondientes a la nueva poltica son (Thaja, 2004)
13
Estas
matrices definen las siguientes ecuaciones:
De nuevo si f (3) =0, se llega a la solucin
Los clculos del paso de mejoramiento de poltica se ven en el siguiente cuadro
Cuadro n 02 mejoramiento de la calidad
Fuente: investigacin de operaciones
La nueva poltica, que establece aplicar fertilizante independientemente del estado, es
idntica a la anterior. Entonces esta ltima poltica es ptima, y termina el proceso
14
iterativo. Es la misma conclusin a la que se llega con el mtodo de enumeracin
exhaustiva . Sin embargo, obsrvese que el mtodo de iteracin de poltica converge
con rapidez hacia al poltica ptima; sta es una caracterstica normal del nuevo
mtodo. (Thaja, 2004)
3. MTODO DE ITERACIN DE POLTICA CON DESCUENTO
El algoritmo de iteracin de poltica se puede ampliar para abarcar descuentos. Dado
el factor de descuento (< 1), la ecuacin recursiva de etapas finitas se puede plantear
como sigue: (Thaja, 2004)
(Ntese que representa la cantidad de etapas que faltan.) Se puede demostrar que
cuando (modelo infinito), f(i) =f (i), siendo f (i) el ingreso a valor presente
(descontado), si el sistema est en el estado i y funciona durante un horizonte infinito.
As, el comportamiento de f(i) a largo plazo, cuando es independiente del valor
de . Esto contrasta con el caso donde no hay descuentos, en el que f(i)=E +f (i).
Cabra esperar este resultado, porque al descontar, el efecto de los ingresos futuros
disminuye a cero, en forma asinttica. En realidad, el valor presente f (i) debe tender a
un valor constante cuando .
Con base en esta informacin, se modifican como sigue los pasos de iteracin de
poltica. (Thaja, 2004)
15
1. Paso de determinacin de valor. Para una poltica arbitraria s con matrices Ps y
Rs, resolver las m ecuaciones (Thaja, 2004)
Con las m incgnitas f s(1), f s(2), ..., fs(m).
2. Paso de mejoramiento de poltica. Para cada estado i, determinar la poltica t
que corresponda (Thaja, 2004)
f s(j) se obtiene en el paso de determinacin de valor. Si la poltica resultante t
es la misma, detenerse; t es ptima. En caso contrario, poner s = t y regresar al
paso de determinacin de valor. (Thaja, 2004)
Ejemplo:
Se resolver el ejemplo con el factor de descuento =0.6.
Partiremos de la poltica arbitraria S={1,1,1}. Las matrices asociadas P y R (P1 y R1
en el ejemplo de enumeracin exhaustiva) dan las ecuaciones (Thaja, 2004)
La solucin de estas ecuaciones es
f1 = 6.61, f2 = 3.21, f3 = -2.5
16
En el siguiente cuadro se presenta un resumen de la iteracin de mejoramiento de
poltica:
Cuadro n 03 mejoramiento de la calidad
F
uente: investigacin de operaciones
El paso de determinacin de valor usando P2 y R2 (Ejemplo de enumeracin
exhaustiva) produce las siguientes ecuaciones: (Thaja, 2004)
La solucin de esas ecuaciones es
f (1) = 8.89, f (2) = 6.62, f (3) = 3.37
17
El paso de mejoramiento de poltica da como resultado el siguiente cuadro:
Cuadro n 04 mejoramiento de la calidad
Fuente: investigacin de operaciones
Como la nueva poltica (1, 2, 2) es distinta de la anterior, se repite el paso de
determinacin de valor con P3 y R3 (Ejemplo de enumeracin exhaustiva). Esto da
como resultado las siguientes ecuaciones: (Thaja, 2004)
La solucin de estas ecuaciones es
f (1) = 8.97, f (2) = 6.63, f(3) = 3.38
18
El paso de mejoramiento de poltica da como resultado el siguiente cuadro:
Cuadro n 04 mejoramiento de la calidad
Fuente: investigacin de operaciones
Como la nueva poltica (1, 2, 2) es idntica a la anterior, es ptima. Obsrvese que los
descuentos han producido una poltica ptima distinta que establece no aplicar
fertilizante si el estado del sistema es bueno (estado 3). (Thaja, 2004)
19
CONCLUSIONES
20
Bibliografa
Thaja, H. A. (2004). INVESTIGACION DE APERACIONES SEXTA EDICION . Mexico:
pearson educacion .
21
