Método simplex revisado

En optimización matemática , el método simplex revisado es una variante del método simplex de George Dantzig para programación lineal .

El método simplex revisado es matemáticamente equivalente al método simplex estándar, pero difiere en su implementación. En lugar de mantener una tabla que represente explícitamente las restricciones ajustadas a un conjunto de variables básicas, mantiene una representación de una base de la matriz que representa las restricciones. El enfoque orientado a matrices permite una mayor eficiencia computacional al posibilitar operaciones con matrices dispersas. ^{[ 1 ]}

Formulación del problema

Para el resto de la discusión, se supone que un problema de programación lineal se ha convertido a la siguiente forma estándar:

{\begin{array}{rl}{\text{minimizar}}&{\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}}\\{\text{sujeto a}}&{\boldsymbol {Ax}}={\boldsymbol {b}},{\boldsymbol {x}}\geq {\boldsymbol {0}}\end{array}}

donde $A \in ℝ m \times n$ . Sin pérdida de generalidad, se supone que la matriz de restricciones $A$ tiene rango completo por filas y que el problema es factible, es decir, existe al menos un $x \geq 0$ tal que $Ax = b$ . Si $A$ tiene un rango deficiente, o bien existen restricciones redundantes, o bien el problema es infactible. Ambas situaciones pueden resolverse mediante un paso de preprocesamiento.

Descripción algorítmica

Condiciones óptimas

Para la programación lineal, las condiciones de Karush-Kuhn-Tucker son necesarias y suficientes para la optimalidad. Las condiciones KKT de un problema de programación lineal en la forma estándar son:

{\begin{aligned}{\boldsymbol {Ax}}&={\boldsymbol {b}},\\{\boldsymbol {A}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s}}&={\boldsymbol {c}},\\{\boldsymbol {x}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}^{\mathrm {T} }{\boldsymbol {x}}&=0\end{aligned}}

donde $λ$ y $s$ son los multiplicadores de Lagrange asociados con las restricciones $Ax = b$ y $x \geq 0$ , respectivamente. ^{[ 2 ]} La última condición, que es equivalente a $s i x i = 0$ para todo $1 < i < n$ , se llama condición de holgura complementaria .

Por lo que a veces se conoce como el teorema fundamental de la programación lineal , un vértice $x$ del politopo factible puede identificarse siendo una base $B$ de $A$ elegida de las columnas de este último. ^{[ a ]} Dado que $A$ tiene rango completo, $B$ es no singular. Sin pérdida de generalidad, supongamos que $A = [B N]$ . Entonces $x$ viene dado por

{\boldsymbol {x}}={\begin{bmatrix}{\boldsymbol {x_{B}}}\\{\boldsymbol {x_{N}}}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {B}}^{-1}{\boldsymbol {b}}\\{\boldsymbol {0}}\end{bmatrix}}

donde $x B \geq 0$ . Particione $c$ y $s$ en consecuencia en

{\begin{aligned}{\boldsymbol {c}}&={\begin{bmatrix}{\boldsymbol {c_{B}}}\\{\boldsymbol {c_{N}}}\end{bmatrix}},\\{\boldsymbol {s}}&={\begin{bmatrix}{\boldsymbol {s_{B}}}\\{\boldsymbol {s_{N}}}\end{bmatrix}}.\end{aligned}}

Para satisfacer la condición de holgura complementaria, sea $s B = 0.$ De ello se deduce que

{\begin{aligned}{\boldsymbol {B}}^{\mathrm {T} }{\boldsymbol {\lambda }}&={\boldsymbol {c_{B}}},\\{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}},\end{aligned}}

lo cual implica que

{\begin{aligned}{\boldsymbol {\lambda }}&=({\boldsymbol {B}}^{\mathrm {T} })^{-1}{\boldsymbol {c_{B}}},\\{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}}-{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}.\end{aligned}}

Si $s N \geq 0$ en este punto, se cumplen las condiciones KKT y, por lo tanto, $x$ es óptimo.

Operación de pivote

Si se incumplen las condiciones de KKT, se realiza una operación de pivote que consiste en introducir una columna de $N$ en la base a expensas de una columna existente en $B.$ En ausencia de degeneración , una operación de pivote siempre resulta en una disminución estricta de $c T x$ . Por lo tanto, si el problema está acotado, el método simplex revisado debe terminar en un vértice óptimo después de repetidas operaciones de pivote porque solo hay un número finito de vértices. ^{[ 4 ]}

Seleccione un índice $m < q \leq n$ tal que $s q < 0$ como índice de entrada . La columna correspondiente de $A$ , $A q$ , se moverá a la base, y se permitirá que $x q aumente desde cero. Se puede demostrar que$

{\frac {\partial ({\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}})}{\partial x_{q}}}=s_{q},

es decir, cada aumento de una unidad en $x q$ resulta en una disminución de $- s q$ en $c T x$ . ^{[ 5 ]} Dado que

{\boldsymbol {Bx_{B}}}+{\boldsymbol {A}}_{q}x_{q}={\boldsymbol {b}},

$x B$ debe disminuirse correspondientemente en $Δ x B = B -1 A q x q$ sujeto a $x B - Δ x B \geq 0$ . Sea $d = B -1 A q$ . Si $d \leq 0$ , no importa cuántoaumente $x q ,$ $x B - Δ x B$ permanecerá no negativo. Por lo tanto, $c T x$ puede disminuirse arbitrariamente, y por lo tanto el problema no está acotado. De lo contrario, seleccione un índice $p = argmin 1\leq i \leq m {x i / d i | d i > 0}$ comoíndice de salida. Esta elección aumenta efectivamente $x q$ desde cero hasta que $x p$ se reduce a cero mientras mantiene la factibilidad. La operación de pivote concluye con reemplazar $A p$ con $A q$ en la base.

Ejemplo numérico

Consideremos un programa lineal donde

{\begin{aligned}{\boldsymbol {c}}&={\begin{bmatrix}-2&-3&-4&0&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {A}}&={\begin{bmatrix}3&2&1&1&0\\2&5&3&0&1\end{bmatrix}},\\{\boldsymbol {b}}&={\begin{bmatrix}10\\15\end{bmatrix}}.\end{aligned}}

Dejar

{\begin{aligned}{\boldsymbol {B}}&={\begin{bmatrix}{\boldsymbol {A}}_{4}&{\boldsymbol {A}}_{5}\end{bmatrix}},\\{\boldsymbol {N}}&={\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {A}}_{2}&{\boldsymbol {A}}_{3}\end{bmatrix}}\end{aligned}}

inicialmente, lo que corresponde a un vértice factible $x = [0 0 0 10 15] T$ . En este momento,

{\begin{aligned}{\boldsymbol {\lambda }}&={\begin{bmatrix}0&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {s_{N}}}&={\begin{bmatrix}-2&-3&-4\end{bmatrix}}^{\mathrm {T} }.\end{aligned}}

Elija $q = 3$ como índice de entrada. Entonces $d = [1 3] T$ , lo que significa que un aumento de una unidad en $x 3$ resulta en que $x 4$ y $x 5$ disminuyan en $1$ y $3$ , respectivamente. Por lo tanto, $x 3$ aumenta a $5$ , momento en el cual $x 5$ se reduce a cero, y $p = 5$ se convierte en el índice de salida.

Después de la operación de pivote,

{\begin{aligned}{\boldsymbol {B}}&={\begin{bmatrix}{\boldsymbol {A}}_{3}&{\boldsymbol {A}}_{4}\end{bmatrix}},\\{\boldsymbol {N}}&={\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {A}}_{2}&{\boldsymbol {A}}_{5}\end{bmatrix}}.\end{aligned}}

En consecuencia,

{\begin{aligned}{\boldsymbol {x}}&={\begin{bmatrix}0&0&5&5&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {\lambda }}&={\begin{bmatrix}0&-4/3\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {s_{N}}}&={\begin{bmatrix}2/3&11/3&4/3\end{bmatrix}}^{\mathrm {T} }.\end{aligned}}

$Un s N$ positivo indica que $x$ ahora es óptimo.

Cuestiones prácticas

Degeneración

Debido a que el método simplex revisado es matemáticamente equivalente al método simplex, también sufre de degeneración, donde una operación de pivote no resulta en una disminución de $c T x$ , y una cadena de operaciones de pivote provoca que la base entre en un ciclo. Se puede utilizar una estrategia de perturbación o lexicográfica para evitar el ciclo y garantizar la terminación. ^{[ 6 ]}

Representación de la base

En el método simplex revisado se presentan dos tipos de sistemas lineales que involucran $a B :$

{\begin{aligned}{\boldsymbol {Bz}}&={\boldsymbol {y}},\\{\boldsymbol {B}}^{\mathrm {T} }{\boldsymbol {z}}&={\boldsymbol {y}}.\end{aligned}}

En lugar de refactorizar $B$ , normalmente se actualiza directamente una factorización LU después de cada operación de pivote, para lo cual existen varias estrategias como los métodos de Forrest-Tomlin y Bartels-Golub. Sin embargo, la cantidad de datos que representan las actualizaciones, así como los errores numéricos, se acumula con el tiempo y hace necesaria la refactorización periódica. ^{[ 1 ]}^{[ 7 ]}

Notas y referencias

Notas

↑ El mismo teorema también establece que el politopo factible tiene al menos un vértice y que existe al menos un vértice que es óptimo.^{[ 3 ]}

Referencias

1 2 Morgan 1997 , §2.
↑ Nocedal y Wright 2006 , pág. 358, ecuación 13.4.
↑ Nocedal y Wright 2006 , pág. 363, Teorema 13.2.
↑ Nocedal y Wright 2006 , pág. 370, Teorema 13.4.
↑ Nocedal y Wright 2006 , pág. 369, ecuación 13.24.
↑ Nocedal y Wright 2006 , pág. 381, §13.5.
↑ Nocedal y Wright 2006 , pág. 372, §13.4.

Bibliografía

Morgan, SS (1997). Comparación de algoritmos del método simplex (tesis de maestría). Universidad de Florida . Archivado del original el 7 de agosto de 2011.
Nocedal, J.; Wright, SJ (2006). Mikosch, TV; Resnick, SI; Robinson, SM (eds.). Optimización numérica . Springer Series in Operations Research and Financial Engineering (2.ª ed.). Nueva York, NY, EE. UU.: Springer . ISBN 978-0-387-30303-1.

[4] El mismo teorema también establece que el politopo factible tiene al menos un vértice y que existe al menos un vértice que es óptimo.^{[ 3 ]}

[FOOTNOTEMorgan1997§2-1] 1 2 Morgan 1997 , §2.

[FOOTNOTENocedalWright2006358Eq.&nbsp;13.4-2] Nocedal y Wright 2006 , pág. 358, ecuación 13.4.

[FOOTNOTENocedalWright2006363Theorem&nbsp;13.2-3] Nocedal y Wright 2006 , pág. 363, Teorema 13.2.

[FOOTNOTENocedalWright2006370Theorem&nbsp;13.4-5] Nocedal y Wright 2006 , pág. 370, Teorema 13.4.

[FOOTNOTENocedalWright2006369Eq.&nbsp;13.24-6] Nocedal y Wright 2006 , pág. 369, ecuación 13.24.

[FOOTNOTENocedalWright2006381§13.5-7] Nocedal y Wright 2006 , pág. 381, §13.5.

[FOOTNOTENocedalWright2006372§13.4-8] Nocedal y Wright 2006 , pág. 372, §13.4.

[ 1 ]

[ 2 ]

[ a ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 3 ]