Método Simplex en Programación Lineal

Study Notes

El método Simplex es un proceso iterativo para resolver problemas de programación lineal.

Se requiere convertir el problema de programación lineal a su forma estándar.
Es necesario convertir todas las restricciones en ecuaciones agregando variables de holgura o excedente.
Todos los lados derechos de las ecuaciones de restricción deben ser no negativos.

Construir la tabla Simplex inicial.
La tabla consta de coeficientes de variables en la función objetivo y restricciones, junto con los lados derechos de las restricciones.
Identificar la variable básica inicial, normalmente variables de holgura o excedente.

La variable entrante entrará en la base.
Para la maximización, seleccione la variable con el coeficiente más negativo en la fila de la función objetivo.
Para la minimización, seleccione la variable con el coeficiente más positivo.
Esta variable se conoce como la columna pivotal.

La variable saliente saldrá de la base.
Divida los lados derechos de las restricciones por los elementos positivos correspondientes en la columna pivotal.
Seleccione la fila con la relación más pequeña no negativa, conocida como la fila pivotal.
El elemento pivotal es donde la columna y la fila pivotal se cruzan.

Realizar operaciones de fila para establecer el elemento pivotal a 1 y todos los demás elementos en la columna pivotal a 0.
Divida la fila pivotal por el elemento pivotal, luego realice operaciones de fila en las otras filas para eliminar los coeficientes que no son cero en la columna pivotal.

Para un problema de maximización, la solución es óptima si todos los coeficientes en la fila de la función objetivo son no negativos.
Para un problema de minimización, la solución es óptima si todos los coeficientes en la fila de la función objetivo son no positivos.
Si la solución no es óptima, repita el proceso.

Leer la solución óptima de la tabla Simplex.
Los valores de las variables básicas están en la columna de la solución.
El valor óptimo de la función objetivo está en la esquina inferior derecha de la tabla.

En lugar de P(Datos | Hipótesis) [frecuentista], calcule P(Hipótesis | Datos).
Regla de Bayes:
- $P(A|B) = \frac{P(B|A)P(A)}{P(B)}$
- $P(H|D) = \frac{P(D|H)P(H)}{P(D)}$

Necesita ser especificado un previo $P(H)$ sobre los posibles valores de $p$.
$H_0$: La moneda es justa, es decir, $p = 0.5$
$H_1$: La moneda no es justa, es decir, $p \neq 0.5$
Giramos la moneda $n$ veces y observamos $k$ caras. El estadístico de prueba es $T = |k - \frac{n}{2}|$.
El valor P es $P(T \geq t | H_0)$. Rechazamos $H_0$ si el valor P es menor que $\alpha$.

Necesitamos especificar un previo $P(H)$ sobre los posibles valores de $p$. Una elección común es una distribución Beta:
- $P(p) = Beta(\alpha, \beta) = \frac{p^{\alpha - 1}(1 - p)^{\beta - 1}}{B(\alpha, \beta)}$ donde $B(\alpha, \beta)$ es la función Beta.
La verosimilitud es dada por la distribución Binomial:
- $P(D|H) = \binom{n}{k} p^k (1 - p)^{n - k}$
La posterior es proporcional al producto de las anteriores y la verosimilitud:
- $P(p|D) \propto P(p)P(D|p)$
- $P(p|D) \propto Beta(\alpha + k, \beta + n - k)$

Supongamos que giramos la moneda 10 veces y observamos 7 caras.
Usemos un previo uniforme, es decir, $Beta(1, 1)$. Entonces la posterior es $P(p|D) = Beta(8, 4)$.
Podemos ahora calcular la probabilidad de que $p > 0.5$:
- $P(p > 0.5 | D) = \int_{0.5}^{1} Beta(8, 4) dp \approx 0.967$
También podemos calcular un intervalo creíble para $p$, que es un intervalo que contiene $95%$ de la probabilidad posterior. Por ejemplo, un intervalo creíble de $95%$ para $p$ es $[0.45, 0.92]$.