Forma Estándar y Método Simplex

El tema que más cae en la I2: pasar un LP a forma estándar, soluciones básicas factibles, costos reducidos, criterio de optimalidad e iteración completa del método Simplex (Fase II), con casos de múltiples óptimos y no acotamiento. Ejercicios resueltos de las Ayudantías 8 y 9.

Creado por

SebastianZ28

Valoración0 votos

-.-

functions

Forma estándar

El formato que necesita el Simplex

El método Simplex trabaja siempre sobre un LP escrito en forma estándar: minimización, restricciones de igualdad y variables no negativas.

min c^{⊤} x s.a. A x = b, x \geq 0

Transformaciones para llegar a la forma estándar

Maximizar → minimizar: $max c^{⊤} x \equiv min - c^{⊤} x$ .
Restricción $\leq$ : sumar una variable de holgura $s \geq 0$ .
Restricción $\geq$ : restar una variable de exceso $s \geq 0$ .
Variable irrestricta $x \in R$ : escribir $x = x^{+} - x^{-}$ con $x^{+}, x^{-} \geq 0$ .
Variable $x \leq 0$ : sustituir $x^{'} = - x$ con $x^{'} \geq 0$ .

¿Qué significan holgura y exceso?

La holgura mide el recurso que queda sin usar en una restricción $\leq$ ; el exceso mide cuánto se sobrecumple una restricción $\geq$ . Si la holgura vale 0, la restricción está activa (se cumple con igualdad exacta).

¿Por qué se exige $x \geq 0$ ? Porque el Simplex se mueve entre soluciones básicas, que deben corresponder a vértices del poliedro factible. La no negatividad y la forma $A x = b$ hacen que esos vértices sean fáciles de calcular paso a paso.

Por qué x ≥ 0

Ejemplo resuelto (Ayudantía 8)

Llevar a forma estándar: $max 2 x_{1} - x_{2} + 3 x_{3}$ con $x_{1} + x_{2} - x_{3} \geq 4$ , $2 x_{1} - x_{2} + x_{3} \leq 6$ , $x_{1}, x_{2} \geq 0$ , $x_{3} \leq 0$ . Sustituimos $x_{3}^{'} = - x_{3}$ ( $x_{3}^{'} \geq 0$ ), pasamos a min y agregamos exceso $y_{1}$ y holgura $y_{2}$ :

\min\ -2x_1 + x_2 + 3x_3' \quad\text{s.a.}\quad PH0\quad x \ge 0

Quedando los datos identificados así:

c = (- 2, 1, 3, 0, 0)^{⊤}, b = (4, 6)^{⊤}, A = (12 1 - 1 1 - 1 - 1 0 01)

Cargando Quiz...

schema

Bases y soluciones básicas factibles

¿Qué es una base?

Con $m$ restricciones y $n$ variables, una base $B$ es un conjunto de $m$ índices cuyas columnas de $A$ son linealmente independientes, de modo que la matriz $A_{B}$ es invertible.

Las variables se parten en básicas ( $x_{B}$ , índices en $B$ ) y no básicas ( $x_{N}$ ). Se fijan las no básicas en cero y se resuelve el sistema:

x_{N} = 0, x_{B} = A_{B}^{- 1} b

Solución básica factible (SBF)

Si además $x_{B} \geq 0$ , la solución básica es factible (SBF). Geométricamente, cada SBF corresponde a un vértice del poliedro factible. El Simplex se mueve de SBF en SBF, es decir, de vértice en vértice.

Ejemplo resuelto (Ayudantía 8)

Para $min 3 x_{1} + 4 x_{2}$ con $2 x_{1} - x_{2} + x_{3} \leq 5$ , $x_{1} + 3 x_{2} + 2 x_{3} \geq 4$ (estándar con $x_{4}$ holgura, $x_{5}$ exceso), tomamos como activas $R_{1}, R_{2}$ y $x_{3} = 0$ ⇒ básicas $x_{1}, x_{2}$ . Con $b = (5, 4)$ :

A_{B} = (21 - 1 3), A_{B}^{- 1} = \frac{1}{7} (3 - 1 12), x_{B} = A_{B}^{- 1} b = (19/7 3/7)

La solución $x = (19/7, 3/7, 0, 0, 0)$ tiene todas sus componentes $\geq 0$ , así que es una SBF (un vértice). $■$

Cargando Quiz...

tune

Costos reducidos y optimalidad

¿La SBF actual es óptima?

Para saberlo se calculan los costos reducidos de las variables no básicas. El costo reducido $r_{j}$ mide cuánto cambia el objetivo $z$ si la variable no básica $x_{j}$ entra a la base (sube desde 0).

\overset{c}{ˉ}_{N}^{⊤} = c_{N}^{⊤} - c_{B}^{⊤} A_{B}^{- 1} A_{N}, r_{j} = c_{j} - c_{B}^{⊤} A_{B}^{- 1} A_{j}

Criterio de optimalidad (minimización)

La SBF actual es óptima si y solo si todos los costos reducidos son no negativos. Si alguno es negativo, conviene hacer entrar esa variable porque reduce $z$ .

\overset{c}{ˉ}_{N} \geq 0 ⟺ SBF \overset{o}{ˊ} ptima

Ejemplo resuelto (Ayudantía 8, continuación)

Con la base anterior ( $c_{B} = (3, 4)$ , $c_{N} = (0, 0, 0)$ ) se calcula $\overset{ˉ}{A}_{N} = A_{B}^{- 1} A_{N}$ y luego:

\overset{c}{ˉ}_{N}^{⊤} = c_{N}^{⊤} - c_{B}^{⊤} A_{B}^{- 1} A_{N} = (- \frac{27}{7}, - \frac{5}{7}, \frac{11}{7})

Como hay componentes negativas ( $- 27/7$ y $- 5/7$ ), la SBF no es óptima: todavía se puede mejorar haciendo entrar una de esas variables. $■$

Cargando Quiz...

calculate

Iteración del Simplex (Fase II)

Una iteración, paso a paso

Cuando la SBF no es óptima, una iteración del Simplex la mejora moviéndose a un vértice vecino:

1. Variable entrante. Elige una no básica $x_{j}$ con costo reducido negativo ( $r_{j} < 0$ ).

2. Columna de la dirección. Calcula $A_{B}^{- 1} A_{j}$ .

3. Ratio test (variable saliente). Determina cuánto puede crecer $x_{j}$ antes de que una básica se haga 0:

δ^{*} = i : (A_{B}^{- 1} A_{j})_{i} > 0 min \frac{( A _{B}^{- 1} b ) _{i}}{( A _{B}^{- 1} A _{j} ) _{i}}

La variable básica que alcanza ese mínimo sale de la base. 4. Actualiza la base y repite hasta que $\overset{c}{ˉ}_{N} \geq 0$ .

Error típico en el ratio test: solo se consideran las filas con $(A_{B}^{- 1} A_{j})_{i} > 0$ (estrictamente positivas). Las componentes $\leq 0$ se ignoran. Si NINGUNA es positiva, el problema es no acotado.

Ojo

Ejemplo resuelto completo (Ayudantía 9)

min 5 x_{1} + 2 x_{2}

con

4 x_{1} + 2 x_{2} - x_{3} = 2

5 x_{1} + 4 x_{2} \geq 3

. En estándar (exceso

x_{4}

), con

R_{1}, R_{2}, x_{3} = 0

activas, la SBF inicial es:

A_{B} = (4524), x_{B} = A_{B}^{- 1} b = (\frac{1}{3}, \frac{1}{3}) \Rightarrow x^{(0)} = (\frac{1}{3}, \frac{1}{3}, 0, 0)

Iteración: con base $B = {1, 2}$ los costos reducidos de $x_{3}, x_{4}$ son:

\overset{c}{ˉ}_{N} = (\frac{5}{3}, - \frac{1}{3}) \Rightarrow r_{4} < 0 \Rightarrow entra x_{4}

El ratio test da $δ^{*} = 1$ y sale $x_{1}$ . Nueva base $B = {2, 4}$ . Recalculando:

\overset{c}{ˉ}_{N} = [1, 1.5] \geq 0 \Rightarrow \overset{o}{ˊ} ptimo x^{*} = (0, 1, 0, 1), z^{*} = 2

El algoritmo saltó del vértice $(1/3, 1/3)$ al vértice óptimo $(0, 1)$ . $■$

warning

Casos especiales: múltiples óptimos y no acotamiento

Dos situaciones que debes reconocer

Múltiples soluciones óptimas

Si en el óptimo algún costo reducido de una variable no básica es exactamente 0, se puede mover hacia esa variable sin cambiar el valor de $z$ : hay un conjunto (arista) de soluciones óptimas.

\overset{c}{ˉ}_{N} \geq 0 y \exists j \in / B : \overset{c}{ˉ}_{j} = 0 ⟹ m \overset{u}{ˊ} ltiples \overset{o}{ˊ} ptimos

Ejemplo (Ayudantía 9): para $min c_{1} x_{1} + c_{2} x_{2}$ con base $B = {3, 4}$ ( $A_{B} = I$ ), se tiene $\overset{c}{ˉ}_{N} = (c_{1}, c_{2})$ . Con $c_{1} = 2, c_{2} = 4$ el óptimo $(0, 0, 3, 2)$ es único; pero si $c_{1} = 0$ o $c_{2} = 0$ , aparecen múltiples óptimos.

Problema no acotado

Si la variable entrante tiene su columna $A_{B}^{- 1} A_{j}$ completamente $\leq 0$ , el ratio test no tiene mínimo positivo: la variable crece sin límite y $z \to - \infty$ . Se certifica con un rayo de soluciones factibles que baja el objetivo.

x (λ) = x^{0} + λ r, λ \geq 0, con c^{⊤} r < 0 ⟹ no acotado

Ejemplo (Ayudantía 9): $min - 3 x_{1} + 2 x_{2}$ con holguras como base inicial; entra $x_{1}$ y su columna es toda negativa. El certificado es:

x (λ) = (0, 0, 2, 1) + λ (1, 0, 3, 4), c^{⊤} r = - 3 < 0

Resumen rápido al iterar: (a) si todos $\overset{c}{ˉ}_{N} > 0$ → óptimo único; (b) si todos $\overset{c}{ˉ}_{N} \geq 0$ con algún $\overset{c}{ˉ}_{j} = 0$ → múltiples óptimos; (c) si entra una variable y su columna es toda $\leq 0$ → no acotado.

Checklist final

Cargando Quiz...