\documentclass[a4paper,10pt]{article}
\usepackage[utf8]{inputenc} %linux
\usepackage[spanish, activeacute]{babel}
\usepackage{fancyhdr}

\pagestyle{fancy}
%\pdfpagewidth 5.5in
%\pdfpageheight 11in

%\pagestyle{fancy}
%\headheight 35pt

%\rhead{Right top}
%\chead{Middle top}
%\lhead{Left top}
%\rfoot{Right bottom}

%\cfoot{\thepage}
%\lfoot{Left bottom}

%\usepackage[latin1]{inputenc} %windows

%\usepackage[dvips]{epsfig}
%\usepackage{mathrsfs}
%\usepackage{amsmath}
%\usepackage{pst-all}
%\usepackage{amssymb}
%\usepackage{fullpage}
\usepackage{graphicx}

\begin{document}

\fancyhf{}
\fancyhead[L]{\leftmark} %nombre de capítulo
\fancyhead[R]{RMES} % RMES
\fancyfoot[C]{
    Centro de Desarrollo de Gestión Empresarial.\\
    Poniente 1206 – Viña del Mar, Chile.\\
    Fono:(56) (32)688987 – Fax:(56) (32)2684079
    }
\fancyfoot[R]{\thepage} % la pagina

\renewcommand{\footrulewidth}{0.4pt}


\title{\textbf{
Algoritmo Rushdi Optimizado \\
Software RMES\\
}}
\author{
    Centro de Desarrollo de Gestión Empresarial.\\
    Poniente 1206 – Viña del Mar, Chile.\\
    Fono:(56) (32)688987 – Fax:(56) (32)2684079\\
    empresa@mes.cl
    }
\date{Noviembre, 2009}

\maketitle

\section{Introducción}
Este algoritmo es usado para el cálculo de confiabilidad de sistemas en redundancia o fraccionamiento.
Estos sistemas se conocen como k-out-of-n:G, lo cual significa que el sistema funciona s'i y s'olo s'i
k de sus n componentes est'an operativos. La nomenclatura complementaria,
k-out-of-n:F, se refiere a que el sistema falla s'i y s'olo s'i k de los
n componentes fallan. RMES utiliza la primera definici'on.

El presente trabajo utiliza las definiciones existentes en el documento ''Algoritmo Rushdi'', por lo
cual, es necesario leer este documento antes de abordar el actual.

\section{El algoritmo optimizado}
Para implementar una optimizaci'on del algoritmo original, es necesario comprender
a cabalidad el original.

Para ello se explicar'a el algoritmo de forma gr'afica, de modo de entenderlo paso a paso.
Por ejemplo, digamos que se tiene un subsistema 3-out-of-4:G. Supongamos que los valores
de la confiabilidad de los 4 subsistemas se conocen y se almacenan en el vector ''P'':

$$
P = 
\left[
  \begin{array}{cccc}
    p_0 & p_1 & p_2 & p_3 \\
  \end{array}
\right]
$$

El algorimo original crearia la siguiente matriz A:

$$
A = 
\left(
  \begin{array}{ccccc}
    0 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 \\
  \end{array}
\right)
$$

Y luego igualaria la primera fila a 1.
$$
A =
\left(
  \begin{array}{ccccc}
    1 & 1 & 1 & 1 & 1 \\
    0 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 \\
  \end{array}
\right)
$$

Luego, se comenzaria por calcular la celda $a_{1,1}$ usando los
valores de las celdas $a_{0,0}$ y $a_{1,0}$ junto con el valor
$p_0$ del vector:

$$a_{1,1} = p_0 \cdot a_{0,0}+ (1-p_0) \cdot a_{1,0}$$ 

Notar que $a_{0,i} = 1$ y $a_{1,0}=0$, por lo tanto, para este caso
particular $a_{1,1} = p_0$

$$
A =
\left(
  \begin{array}{ccccc}
    a_{0,0} & 1 & 1 & 1 & 1 \\
    a_{1,0} & a_{1,1} & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 \\
  \end{array}
\right)
$$

Continuando con el algoritmo, se procede a calcular la siguiente celda, $a_{1,2}$,
el cual se obtendra de las celdas $a_{0,1}$ y $a_{1,1}$ junto con el valor
$p_1$ del vector:

$$a_{1,2} = p_1 \cdot a_{0,1}+ (1-p_1) \cdot a_{1,1}$$ 
$$
A =
\left(
  \begin{array}{ccccc}
    a_{0,0} & a_{0,1} & 1 & 1 & 1 \\
    a_{1,0} & a_{1,1} & a_{1,2} & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 \\
  \end{array}
\right)
$$

Finalmente las ultimas celdas se calcularian de la siguiente manera:

$$a_{1,3} = p_2 \cdot a_{0,2}+ (1-p_2) \cdot a_{1,2}$$
$$a_{1,4} = p_3 \cdot a_{0,3}+ (1-p_3) \cdot a_{1,3}$$

$$
A =
\left(
  \begin{array}{ccccc}
    a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3} & 1 \\
    a_{1,0} & a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4} \\
    0 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 \\
  \end{array}
\right)
$$

En la siguiente iteraci'on, el calculo comienza en la celda
$a_{2,2}$ y algoritmo es id'entico:

$$a_{2,2} = p_1 \cdot a_{1,1}+ (1-p_1) \cdot a_{2,1}$$
$$
A =
\left(
  \begin{array}{ccccc}
    a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3} & 1 \\
    a_{1,0} & a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4} \\
    0       & a_{2,1} & a_{2,2} & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 \\
  \end{array}
\right)
$$

$$a_{2,3} = p_2 \cdot a_{1,2}+ (1-p_2) \cdot a_{2,2}$$
$$
A =
\left(
  \begin{array}{ccccc}
    a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3} & 1 \\
    a_{1,0} & a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4} \\
    0       & a_{2,1} & a_{2,2} & a_{2,3} & 0 \\
    0 & 0 & 0 & 0 & 0 \\
  \end{array}
\right)
$$

$$a_{2,3} = p_4 \cdot a_{1,3}+ (1-p_3) \cdot a_{2,3}$$
$$
A =
\left(
  \begin{array}{ccccc}
    a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3} & 1 \\
    a_{1,0} & a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4} \\
    0       & a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4} \\
    0 & 0 & 0 & 0 & 0 \\
  \end{array}
\right)
$$

Y en la siguiente y 'ultima iteraci'on el calculo
comienza en la celda $a_{3,3}$ hasta llegar a la celda $a_{3,4}$,
valor que retorna el algoritmo.

$$a_{3,3} = p_2 \cdot a_{2,2}+ (1-p_2) \cdot a_{3,2}$$
$$
A =
\left(
  \begin{array}{ccccc}
    a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3} & 1 \\
    a_{1,0} & a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4} \\
    0       & a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4} \\
    0       &  0      & a_{3,2} & a_{3,3} & 0 \\
  \end{array}
\right)
$$

$$a_{3,4} = p_3 \cdot a_{2,3}+ (1-p_3) \cdot a_{3,3}$$
$$
A =
\left(
  \begin{array}{ccccc}
    a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3} & 1 \\
    a_{1,0} & a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4} \\
    0       & a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4} \\
    0       &  0      & a_{3,2} & a_{3,3} & a_{3,4} \\
  \end{array}
\right)
$$

De todo el proceso se pueden desprender que en
cada paso unitario del algoritmo se necesita 'unicamente
saber el valor de la celda superior izquierda y de la celda inmediatamente
izquierda respecto de la actual. Mientras el algoritmo avanza, los valores
que se calcularon para las primeras filas no se vuelven a utilizar. Esto
lleva a pensar de que s'olo es necesario utilizar un vector de tamaño n
(la cantidad de subsistemas hijos) que almacene los valores por cada iteraci'on.

Teniendo presente este esquema, es necesario aislar la primera iteraci'on del
resto, debido a que los valores iniciales de las celdas superiores deben ser igual
a 1, lo que implica que la f'ormula puede ser modificada para este caso particular.

Ubicaremos gr'aficamente un vector V dentro la matriz A para observar el comportamiento
del algoritmo modificado. El vector V almacenar'a los valores del algoritmo.

$$
V =
\left[
  \begin{array}{cccc}
    v_0 & v_1 & v_2 & v_2 \\
  \end{array}
\right]
$$

$$
A =
\left(
  \begin{array}{ccccc}
    1 & 1 & 1 & 1 & 1 \\
    0 & v_0 & v_1 & v_2 & v_3 \\
    0 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 \\
  \end{array}
\right)
$$

Para la primera iteraci'on se cumple que $a_{0,i}=1$, por lo tanto
la f'ormula puede ser modificada de la siguiente manera:

$$a_{1,j} = p_{j-1} + (1-p_{j-1}) \cdot a_{1,j-1} \ \ \ \forall_{j=1 \ldots n}$$ 

Reemplazando para el vector V:

$$v_{j} = p_j + (1-p_j) \cdot a_{1,j} \ \ \ \forall_{j=0 \ldots n-1}$$ 

Para eliminar la dependencia con la matriz A, el valor de la celda
$a_{1,j}$ simplemente es el valor de la celda calculada en el paso anterior,
la cual puede ser referenciada directamente. Para primer elemento $v_{0}$,
$v_{-1}$ no existe y se considera con valor 0, por ende, la f'ormula puede
ser a'un m'as concisa.

$$v_{0} = p_{j}$$ 
$$v_{j} = p_{j} + (1-p_{j}) \cdot v_{j-1} \ \ \ \forall_{j=1 \ldots n-1}$$ 

Gráficamente, el algoritmo seria el siguiente:

$$v_{0} = p_{0}$$ 
$$
A =
\left(
  \begin{array}{ccccc}
    1 & 1 & 1 & 1 & 1 \\
    0 & v_0 & - & - & - \\
    0 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 \\
  \end{array}
\right)
$$

$$v_{1} = p_{1} + (1-p_{1}) \cdot v_{0}$$
$$
A =
\left(
  \begin{array}{ccccc}
    1 & 1 & 1 & 1 & 1 \\
    0 & v_0 & v_1 & - & - \\
    0 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 \\
  \end{array}
\right)
$$

$$v_{2} = p_{2} + (1-p_{2}) \cdot v_{1}$$
$$
A =
\left(
  \begin{array}{ccccc}
    1 & 1 & 1 & 1 & 1 \\
    0 & v_0 & v_1 & v_2 & - \\
    0 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 \\
  \end{array}
\right)
$$

$$v_{3} = p_{3} + (1-p_{3}) \cdot v_{2}$$
$$
A =
\left(
  \begin{array}{ccccc}
    1 & 1 & 1 & 1 & 1 \\
    0 & v_0 & v_1 & v_2 & v_3 \\
    0 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 \\
  \end{array}
\right)
$$

Para la siguiente iteraci'on, es necesario modificar el criterio anterior.
El valor de la celda $v_1$ es el que debe ser calculado, entonces, siguiendo
la f'ormula:

$$v_{1} = p_{1} \cdot \widehat{v_{0}} + (1-p_{1}) \cdot v_{0}$$
$$
A =
\left(
  \begin{array}{ccccc}
    1 & 1 & 1 & 1 & 1 \\
    0 & \widehat{v_0} &  -  & v_2 & v_3 \\
    0 & v_0           & v_1 & - & - \\
    0 & 0 & 0 & 0 & 0 \\
  \end{array}
\right)
$$

En donde $\widehat{v_i}$ se refiere al valor antiguo de la celda $i$
del vector $V$ antes de ser calculada. Particularmente, para el primer
paso de la iteraci'on, no se realiza c'alculo sobre $v_0$, adem'as, su
valor es $v_0 = 0$, y se debe de recordar que $\widehat{v_i}$ tiene
un valor calculado en la iteraci'on anterior, por lo tanto, s'olo es necesario
modificar la f'ormula:

$$v_{1} = p_{1} \cdot \widehat{v_{0}}$$
$$
A =
\left(
  \begin{array}{ccccc}
    1 & 1 & 1 & 1 & 1 \\
    0 & \widehat{v_0} &  -  & v_2 & v_3 \\
    0 &      0         & v_1 & - & - \\
    0 & 0 & 0 & 0 & 0 \\
  \end{array}
\right)
$$

El problema de esto es que se pierde el valor original de $v_1$, el cual
se utiliza en el paso siguiente de la iteraci'on. Por lo tanto, el valor
de $v_1$ debe ser almacenado en una variable auxiliar antes de realizar
el calculo. Esta variable se llamar'a ''actualOldValue'', o AOV

$$AOV = v_{1}$$
$$v_{1} = p_{1} \cdot \widehat{v_{0}}$$
$$
A =
\left(
  \begin{array}{ccccc}
    1 & 1 & 1 & 1 & 1 \\
    0 & \widehat{v_0} &  AOV  & v_2 & v_3 \\
    0 & 0  & v_1 & - & - \\
    0 & 0 & 0 & 0 & 0 \\
  \end{array}
\right)
$$

Para la siguiente iteraci'on, es necesario
utilizar el valor $AOV$ y $v_1$ para calcular
el nuevo valor de la celda $v_2$, pero tambi'en
es necesario almacenar el valor de la celda $v_2$ anterior
al c'alculo, dado que se necesita el valor
antiguo para el c'alculo de la siguiente celda en la iteraci'ion.
Se utilizar'a la variable $AOV$ para almacenar el valor de
$v_2$ previo al calculo, pero ademas, se debe almacenar el
valor que $AOV$ ten'ia almacenado. Para ello, se utilizar'a
la variable ''upperOldValue'', o UOV. Esta se utilizar'a
para realizar el c'alculo de la celda actual $v_2$. Entonces:

$$UOV = AOV$$
$$AOV = v_2$$
$$v_{2} = p_{2} \cdot UOV + (1-p_{2}) \cdot v_1$$
$$
A =
\left(
  \begin{array}{ccccc}
    1 & 1 & 1 & 1 & 1 \\
    0 & \widehat{v_0} & UOV & AOV & v_3 \\
    0 & 0   & v_1 & v_2 & - \\
    0 & 0 & 0 & 0 & 0 \\
  \end{array}
\right)
$$

Para la siguiente iteraci'on, no es necesario agregar m'as variables,
s'olo actualizar las existentes:

$$UOV = AOV$$
$$AOV = v_3$$
$$v_{3} = p_{3} \cdot UOV + (1-p_{3}) \cdot v_2$$
$$
A =
\left(
  \begin{array}{ccccc}
    1 & 1 & 1 & 1 & 1 \\
    0 & \widehat{v_0} & - &   UOV & AOV \\
    0 & 0  & v_1 & v_2 & v_3 \\
    0 & 0 & 0 & 0 & 0 \\
  \end{array}
\right)
$$

Para la 'ultima iteraci'on, se ocupa el mismo criterio anterior.
Sabemos que $v_1 = 0$, entonces el primer paso de la iteraci'on ser'ia:

$$AOV = v_2$$
$$v_{2} = p_{2} \cdot \widehat{v_{1}}$$
$$
A =
\left(
  \begin{array}{ccccc}
    1 & 1 & 1 & 1 & 1 \\
    0 & - &  - & - & - \\
    0 & - & \widehat{v_1} & AOV & v_3 \\
    0 & - & 0 & v_2 & 0 \\
  \end{array}
\right)
$$

El ultimo paso de la iteraci'on ser'ia:

$$UOV = AOV$$
$$AOV = v_3$$
$$v_{3} = p_{3} \cdot UOV + (1-p_{3}) \cdot v_2$$
$$
A =
\left(
  \begin{array}{ccccc}
    1 & 1 & 1 & 1 & 1 \\
    0 & - &  - & - & - \\
    0 & - &  \widehat{v_1} & UOV & AOV \\
    0 & 0 & 0 & v_2 & v_3 \\
  \end{array}
\right)
$$

El codigo de este algoritmo es el siguiente:
\begin{verbatim}
private static double rushdiGeneral(double[] ssR, int k) {
 
  int n = ssR.length;
  double upperOldValue;
  double actualOldValue;
  double array[] = new double[n];
  int i, j;

  array[0] = ssR[0];
  for (j = 1; j < n; j++) {
    array[j] = ssR[j] + (1 - ssR[j]) * array[j - 1];
  }

  for (i = 1; i < k; i++) {
    actualOldValue = array[i];
    array[i] = ssR[i] * array[i - 1];

    for (j = i + 1; j < n; j++) {
      upperOldValue = actualOldValue;
      actualOldValue = array[j];
      array[j] = ssR[j] * upperOldValue + (1 - ssR[j]) * array[j - 1];
    }
  }

  return array[n - 1];

}
\end{verbatim}

En donde $ssR$ es el vector de contiene la confiabilidad de los hijos de la
maquina y $k$ es la m'nima cantidad de equipos en operaci'on. El valor de $k$
puede ir entre $1$ y $n$, donde $n$ es la cantidad de elementos del vector $ssR$.

Para el caso particular $k=1$ se implement'o un algoritmo recursivo que tiene
mejor performance que el presente algoritmo, pero 'unicamente para un valor de $k=1$, para
cualquier otro valor, su performance es pobre y de hasta menor calidad
que el algoritmo rushdi original.

El codigo se basa en la siguiente f'ormula:
$$R(i,j) = p_j R(i-1,j-1) + q_j R(i,j-1)$$

Y esta es su implementaci'on:

\begin{verbatim}
private static double rushdiOneMinToWork(double[] ssR, int n) 
  if (n == 0) {
    return 0;
  }
  return ssR[n - 1] + (1 - ssR[n - 1]) * rushdiOneMinToWork(ssR, n - 1);
}
\end{verbatim}

En donde $ssR$ es el vector de contiene la confiabilidad de los hijos de la
maquina y $n$ un par'ametro que var'ia con la recursi'on, inicialmente es
la cantidad de elementos del vector $ssR$.

\end{document} 