Algoritmo de pivote

Los algoritmos de pivote (o algoritmos de cambio de base) son algoritmos de la optimización matemática, y en especial de la Programación Lineal. Dado un sistema de ecuaciones lineales cuyas variables deben adoptar valores no negativos (esencialmente lo mismo que un sistema de inecuaciones lineales), se busca la mejor de entre muchas soluciones alternativas, es decir, una solución óptima del sistema. En cada paso de tal búsqueda, el algoritmo transforma el sistema sin alterar su conjunto de soluciones. Algoritmos de pivote importantes son los diversos algoritmos simplex^[1][2] y los algoritmos criss-cross.^[3]

Los algoritmos de pivote son de gran importancia para el tratamiento de inecuaciones lineales, donde juegan un papel análogo al de la eliminación de Gauss para ecuaciones lineales. Se encuentran numerosas aplicaciones^[2] de sistemas de inecuaciones en áreas tan diversas como la investigación de operaciones industriales, el transporte y distribución de bienes, en carteras de valores, la ingeniería estructural, la estadística, y la teoría de juegos. Frecuentemente se abordan sistemas con decenas de miles de variables.^[4]

Procedimiento general

El problema normalizado

Todo algoritmo de pivote parte de un sistema especialmente arreglado de ecuaciones lineales, cuyas variables todas, excepto tal vez una, deben tomar valores no negativos. De hecho, cualquier sistema de inecuaciones o ecuaciones lineales, así como todo problema de Programación Lineal, puede siempre reducirse a la siguiente forma diccionario:^[1][2]

${\displaystyle {\begin{matrix}z&=&f&+&d_{1}\,x_{1}&+&\cdots &+&d_{n}\,x_{n}\\[3pt]x_{n+1}&=&b_{n+1}&+&G_{n+1,1}\,x_{1}&+&\cdots &+&G_{n+1,n}\,x_{n}\\\vdots &&\vdots &&\vdots &&&&\vdots \\x_{n+m}&=&b_{n+m}&+&G_{n+m,1}\,x_{1}&+&\cdots &+&G_{n+m,n}\,x_{n}\end{matrix}}}$

${\displaystyle {\begin{matrix}\max ~z,\quad x_{1}\geq 0,\ \ldots \ x_{n+m}\geq 0,\end{matrix}}}$

donde los ${\displaystyle f,\;d_{j},\;b_{i},\;G_{i,j}}$ son números reales (en la práctica casi siempre números racionales). Este formato especifica que se busca valores para las incógnitas ${\displaystyle \,x_{1},\ldots x_{n+m},\ z\,}$, que satisfagan las ecuaciones e inecuaciones del sistema anterior de modo tal que la variable objetivo ${\displaystyle \,z}$ tome el mayor valor posible.

( Al convertir un problema a la forma anterior no disminuye el número de desigualdades; estas permanecen en su totalidad y sólo se convierten en condiciones de no-negatividad de algunas variables. De este modo, una inecuación como por ejemplo

${\displaystyle 3x_{1}~+~4x_{2}~-~x_{3}~\leq ~5x_{1}~+~8}$

es sustituida por

${\displaystyle x_{4}~=~8~+~2x_{1}~-~4x_{2}~+~x_{3},\quad x_{4}\geq 0}$   )

Definiendo los conjuntos de índices

${\displaystyle D=\{1,\ldots ,n\},\quad B=\{n+1,\ldots ,n+m\}}$

se escribirá esto en lo que sigue de la forma más compacta

${\displaystyle {\begin{matrix}&&z&=&f&+&\sum _{j\in D}\,d_{j}\,x_{j}\\[6pt]\forall ~i\in B&&x_{i}&=&b_{i}&+&\sum _{j\in D}\,G_{i,j}\,x_{j}\end{matrix}}}$

${\displaystyle {\begin{matrix}\max ~z\,,\quad \forall ~k\in D\cup B\quad x_{k}\geq 0\end{matrix}}}$

En cada iteración de un algoritmo de pivote se destaca un conjunto de variables independientes, mientras que las restantes son variables dependientes y se expresan como funciones lineales de las primeras. Al pasar de una iteración a la siguiente se intercambia una variable independiente por una dependiente; tales pares de variables se denominan pivotes.

Condiciones de optimalidad

En caso de que se cumplan las siguientes dos condiciones de optimalidad,

• ${\displaystyle b_{i}\geq 0}$  para todo  ${\displaystyle i\in B}$  (sistema factible)   y
• ${\displaystyle d_{j}\leq 0}$  para todo  ${\displaystyle j\in D}$  (sistema acotado),

podemos obtener una solución al problema anterior, asignando a las variables independientes del sistema los valores ${\displaystyle \,x_{1}=0,\ldots ,x_{n}=0\,}$.  Por un lado, esto logra que las variables dependientes ${\displaystyle \,x_{n+1}=b_{n+1},\ldots ,x_{n+m}=b_{n+m}\,}$ adopten valores nonegativos, tal como se pedía. Por otro lado, toda solución alternativa al problema debe satisfacer la relación ${\displaystyle \,z\leq f\,}$,  ya que en ella las variables independientes también deben tomar valores nonegativos.

( Por ejemplo, en el siguiente sistema,

${\displaystyle {\begin{matrix}z&=&~~~0&-~3x_{1}&+~~\mathbf {x_{2}} \\[2pt]x_{3}&=&~~~3&-~~x_{1}&-~~x_{2}\\[2pt]x_{4}&=&~~~8&+~2x_{1}&-~4x_{2}\\[2pt]x_{5}&=&-~\mathbf {1} &+~3x_{1}&+~~x_{2}\end{matrix}}}$

las condiciones de optimalidad son violadas en dos lugares, ya que  ${\displaystyle b_{5}=-1<0}$  y  ${\displaystyle d_{2}=+1>0}$.  Por un lado, los valores obtenidos al anular las variables independientes,  ${\displaystyle x_{1}=x_{2}=0}$,  no constituyen una solución admisible porque contienen un valor negativo,  ${\displaystyle x_{5}=-1}$.  Por otro lado, no podemos descartar la posibilidad de aumentar el valor que adopta la variable objetivo  ${\displaystyle \;z=-3x_{1}+x_{2}\;}$  eligiendo conjuntos de variables independientes con ${\displaystyle x_{2}>0}$. )

Transformación de las ecuaciones

En el caso habitual de que las condiciones de optimalidad no se cumplan, puede reformularse el sistema de ecuaciones, eligiendo adecuadamente un nuevo subconjunto ${\displaystyle \,B\,}$ de entre las ${\displaystyle \,n+m\,}$ incógnitas, y expresando las incógnitas elegidas en función de las incógnitas restantes.  Sea ${\displaystyle \omega }$ un reordenamiento de las variables, es decir una función de los índices que cumpla

${\displaystyle \{x_{\omega (1)},\ldots x_{\omega (n+m)}\}=\{x_{1},\ldots x_{n+m}\}.}$

A partir de la partición ${\displaystyle \pi ={\bigl (}D(\pi ),~B(\pi ){\bigr )}}$, con

${\displaystyle D(\pi )=\{\omega (1),\ldots ,\omega (n)\},\quad B(\pi )=\{\omega (n+1),\ldots ,\omega (n+m)\},}$

que divide las variables del sistema en variables independientes ${\displaystyle x_{j}}$ con ${\displaystyle j\in D(\pi )}$ y las llamadas variables básicas ${\displaystyle x_{i}}$ con ${\displaystyle i\in B(\pi )}$, se construye entonces el sistema:

${\displaystyle {\begin{matrix}&&z&=&f^{\pi }&+&\sum _{j\in D(\pi )}\,d_{j}^{\pi }\,x_{j}\\[6pt]\forall ~i\in B(\pi )&&x_{i}&=&b_{i}^{\pi }&+&\sum _{j\in D(\pi )}\,G_{i,j}^{\pi }\,x_{j}\end{matrix}}}$

${\displaystyle {\begin{matrix}\max ~z\,,\quad \forall ~k\in D\cup B\quad x_{k}\geq 0\end{matrix}}}$

Nótese que los coeficientes ${\displaystyle G_{i,j}^{\pi }}$ existen solo para pares de subíndices con ${\displaystyle i\in B(\pi )}$ y con ${\displaystyle j\in D(\pi )}$. En cada iteración, los coeficientes del sistema así modificado vuelven a examinarse para ver si satisfacen las condiciones de optimalidad

• ${\displaystyle b_{i}^{\pi }\geq 0}$  para todo  ${\displaystyle i\in B(\pi )}$  (sistema factible)   y
• ${\displaystyle d_{j}^{\pi }\leq 0}$  para todo  ${\displaystyle j\in D(\pi )}$  (sistema acotado),

y de este modo generan una posible solución al problema. Un resultado estándar de la Programación Lineal establece que todo problema que tiene soluciones también posee un conjunto de variables básicas que conduce a una de ellas.^[1][2] Si los coeficientes del sistema satisfacen las condiciones de optimalidad, se dice que las variables básicas forman una base optimal del problema.

Pivotes admisibles

Un coeficiente no nulo ${\displaystyle \,G_{k,l}^{\pi }\neq 0\,}$ del sistema de ecuaciones se llama elemento pivote, porque permite despejar la variable independiente ${\displaystyle \,x_{l}\,}$ en lugar de la variable básica ${\displaystyle \,x_{k}\,,}$ para así seguir buscando una solución al problema. Sin embargo, los algoritmos de pivote no eligen un elemento pivote cualquiera, sino solamente los llamados pivotes admisibles ${\displaystyle (x_{k},\,x_{l})}$, que deben satisfacer:

• O se cumple simultáneamente  ${\displaystyle \,b_{k}^{\pi }<0\,}$   y   ${\displaystyle \,G_{k,l}^{\pi }>0\,}$   (pivote de restricción),
• o se cumple simultáneamente  ${\displaystyle \,d_{l}^{\pi }>0\,}$   y   ${\displaystyle \,G_{k,l}^{\pi }<0\,}$   (pivote de objetivo).

( En el ejemplo anterior,

${\displaystyle {\begin{matrix}z&=&~~~0&-~3x_{1}&+~~~\mathbf {x_{2}} \\[2pt]x_{3}&=&~~~3&-~~x_{1}&-~~~{\underline {\mathbf {x_{2}} }}\\[2pt]x_{4}&=&~~~8&+~2x_{1}&-~{\underline {\mathbf {4x_{2}} }}\\[2pt]x_{5}&=&-~\mathbf {1} &+~{\underline {\mathbf {3x_{1}} }}&+~~~{\underline {\mathbf {x_{2}} }}\end{matrix}}}$

el coeficiente no optimal  ${\displaystyle b_{5}<0}$  permite seleccionar el elemento pivote  ${\displaystyle G_{5,1}=+3>0,}$  correspondiente a un pivote admisible con intercambio de ${\displaystyle (x_{5},\,x_{1}),}$ ó también el elemento pivote  ${\displaystyle G_{5,2}=+1>0}$  correspondiente al pivote admisible ${\displaystyle (x_{5},\,x_{2}).}$  Alternativamente, el coeficiente no optimal  ${\displaystyle d_{2}>0}$  permite también seleccionar el elemento pivote  ${\displaystyle G_{3,2}=-1<0}$  correspondiente al pivote admisible ${\displaystyle (x_{2},\,x_{3}),}$  ó el elemento pivote  ${\displaystyle G_{4,2}=-4<0}$  con el pivote admisible ${\displaystyle (x_{2},\,x_{4})}$. )

La restricción a pivotes admisibles impide que en dos iteraciones sucesivas se elija el mismo pivote. Las reglas según las cuales el pivote es elegido dependen del algoritmo de pivote particular. No obstante, debe imponerse que el algoritmo termine en un número finito de pasos, lo que no sucede con una elección de pivotes inadecuada. Fukuda & Terlaky demostraron^[5] en 1999 que para todo problema con solución y para toda base inicial existe una secuencia de a lo más ${\displaystyle \,n+m\,}$ pivotes admisibles que conduce a una base optimal. Lamentablemente, esa demostración no es constructiva en el sentido de que indique cuál pivote deba elegirse en cada paso.

Como se puede observar de las definiciones anteriores, una base optimal no tiene pivotes admisibles, por lo que el algoritmo no puede ser continuado a partir de una base optimal. Por otro lado, es fácil demostrar con argumentos similares a los expuestos que una base no optimal sin pivotes admisibles siempre pertenece a un problema sin solución; sea esto, porque el sistema de ecuaciones e inecuaciones no tiene solución alguna (problema infactible), o porque existen soluciones con un valor objetivo ${\displaystyle z\,}$ arbitrariamente grande (problema no acotado).

Implementación sin errores de redondeo

Para evitar errores de redondeo se trabaja en lo que sigue con números racionales, eligiendo un único denominador común para todo el sistema de ecuaciones. Para encontrar un denominador así en cada paso del algoritmo no hace falta analizar los coeficientes del sistema; en caso de un sistema inicial con coeficientes enteros, en cada iteración se cumplirá que

• El numerador del elemento pivote es un denominador común para el sistema de ecuaciones siguiente.

Al evaluar los coeficientes de un nuevo sistema el denominador común del sistema anterior quedará obsoleto, por lo que se procede a dividir los coeficientes del sistema nuevo por el denominador antiguo, con resultados que siempre serán enteros.^[6]

Un arreglo matricial que contiene los coeficientes de un sistema de pivote suele llamarse tabla de pivoteo o cuadro de pivoteo. El siguiente esquema muestra cómo cambian los coeficientes del sistema de pivoteo al pasar de una iteración a la que sigue:

${\displaystyle {\begin{matrix}\delta \,x_{i}&\!=\!&(~~\alpha )&\!\!\!x_{j}&\!+\!&(~~\sigma )&\!\!\!x_{s}\\[6pt]\delta \,x_{r}&\!=\!&(~~\zeta )&\!\!\!x_{j}&\!+\!&(~~p)&\!\!\!x_{s}\end{matrix}}}$

${\displaystyle {x_{r}\leftrightarrow x_{s}}}$

${\displaystyle {\begin{matrix}p\,x_{i}&\!=\!&(\textstyle {\frac {\alpha p\,-\,\zeta \sigma }{\delta }})&\!\!\!x_{j}&\!+\!\!&(~\sigma )&\!\!\!x_{r}\\[6pt]p\,x_{s}&\!=\!&(~-\zeta ~)&\!\!\!x_{j}&\!+\!\!&(~\delta )&\!\!\!x_{r}\\\end{matrix}}}$

En ese esquema, el símbolo ${\displaystyle \delta }$ designa al denominador común del sistema de ecuaciones, el símbolo ${\displaystyle p}$ designa al numerador del elemento pivote, ${\displaystyle \zeta }$ designa cualquier coeficiente restante en la misma fila del elemento pivote, ${\displaystyle \sigma }$ designa cualquier coeficiente restante en la misma columna del elemento pivote, y ${\displaystyle \alpha }$ cualquier coeficiente ajeno a la fila y a la columna del pivote. Los coeficientes ${\displaystyle d_{j}^{\pi }}$ de la variable a maximizar (${\displaystyle x_{i}\!=\!z\,}$) y los coeficientes ${\displaystyle b_{i}^{\pi }}$ de la columna de valores (${\displaystyle x_{j}\!=\!1\,}$) se transforman de acuerdo a las mismas reglas.

Ejemplo ilustrado

Representación gráfica

Las ilustraciones en cada paso del ejemplo siguiente muestran todas el mismo sistema de ecuaciones graficado en distintos sistemas de coordenadas. En estos gráficos,

• el área bordeada de verde es el conjunto de soluciones factibles, para el cual todas las variables toman valores no negativos,
• los ejes de coordenadas corresponden a ecuaciones ${\displaystyle x_{k}=0}$ de variables independientes, las demás rectas a ecuaciones de variables básicas,
• la recta en rojo recorre los puntos donde la variable objetivo adopta su valor máximo,
• las intersecciones de rectas correspondientes a pivotes admisibles llevan puntos rojos, el pivote seleccionado va bordeado de negro, y
• el área anaranjada corresponde al ortante no negativo de la iteración siguiente.

Ejemplo de elección de pivotes

La siguiente estrategia de elección de pivote corresponde al algoritmo criss-cross con pivoteo en los índices mínimos (minimal index criss-cross-algorithm). En cada paso, el pivote admisible se elegirá de acuerdo a la siguiente regla (el mínimo de un conjunto vacío se considera igual a infinito):

1. Determinar los índices ${\displaystyle r=\min\{i\in B(\pi )~|~b_{i}^{\pi }<0\}}$   y   ${\displaystyle s=\min\{j\in D(\pi )~|~d_{j}^{\pi }>0\}}$.
2. Si se tiene ${\displaystyle r<s\,}$,  elegir el pivote ${\displaystyle (x_{r},\,x_{l})}$  donde  ${\displaystyle l=\min\{j\in D(\pi )~|~G_{r,j}^{\pi }>0\}}$.
3. Si se tiene ${\displaystyle s<r\,}$,  elegir el pivote ${\displaystyle (x_{k},\,x_{s})}$  donde  ${\displaystyle k=\min\{i\in B(\pi )~|~G_{i,s}^{\pi }<0\}}$.

Se puede demostrar^[3] que este criterio simple (aunque no siempre eficiente) conduce siempre a una base optimal en un sistema que tenga solución.

En el siguiente ejemplo se busca valores no negativos para las variables ${\displaystyle \,x_{1}\geq 0,\ldots \ x_{5}\geq 0\,}$ que maximicen la variable adicional ${\displaystyle z\,}$ satisfaciendo el siguiente conjunto de ecuaciones lineales:

${\displaystyle {\begin{matrix}z&=&(&~~~~0&+~\mathbf {3x_{1}} &+~2x_{2}&)~/~1\\[2pt]x_{3}&=&(&~~~3&-~{\underline {\mathbf {2x_{1}} }}&-~~x_{2}&)~/~1\\[2pt]x_{4}&=&(&~~~7&-~2x_{1}&-~3x_{2}&)~/~1\\[2pt]x_{5}&=&(&~~~4&-~3x_{1}&-~~x_{2}&)~/~1\end{matrix}}}$

En el sistema inicial del ejemplo, los coeficientes no optimales son ${\displaystyle \,d_{1}=3\,}$, ${\displaystyle \,d_{2}=2\,}$, y todos los pivotes son admisibles. El criterio de selección, sin embargo, prescribe que despejemos ${\displaystyle \,x_{1}\,}$ en lugar de ${\displaystyle \,x_{3}\;}$:

Cambio de la base 0 a la base 1

(para animar con Firefox, pulsar aquí y luego en la imagen, manteniendo presionado)

Con ello obtenemos:

${\displaystyle {\begin{matrix}z&=&(&~~~9&-~3x_{3}&+~~\mathbf {x_{2}} &)~/~2\\[2pt]x_{1}&=&(&~~~3&-~~x_{3}&-~~{\underline {\mathbf {x_{2}} }}&)~/~2\\[2pt]x_{4}&=&(&~~~8&+~2x_{3}&-~4x_{2}&)~/~2\\[2pt]x_{5}&=&(&-~1&+~3x_{3}&+~~x_{2}&)~/~2\end{matrix}}}$

Ahora los coeficientes no optimales son ${\displaystyle \,d_{2}^{\pi }=1/2\,}$ con los pivotes admisibles ${\displaystyle (x_{2},\,x_{1})}$, ${\displaystyle (x_{2},\,x_{4})}$, y el coeficiente ${\displaystyle \,b_{5}^{\pi }=-1/2\,}$ con los pivotes admisibles ${\displaystyle (x_{5},\,x_{2})}$, ${\displaystyle (x_{5},\,x_{3})}$. En consecuencia, despejamos ${\displaystyle \,x_{2}\,}$ en lugar de ${\displaystyle \,x_{1}\;}$:

Cambio de la base 1 a la base 2

(animado)

Se obtiene el sistema

${\displaystyle {\begin{matrix}z&=&(&~~~6&-~2x_{3}&-~~x_{1}&)~/~1\\[2pt]x_{2}&=&(&~~~3&-~~x_{3}&-~2x_{1}&)~/~1\\[2pt]x_{4}&=&(&-~\mathbf {2} &+~3x_{3}&+~{\underline {\mathbf {4x_{1}} }}&)~/~1\\[2pt]x_{5}&=&(&~~~1&+~~x_{3}&-~~x_{1}&)~/~1\end{matrix}}}$

El único coeficiente no optimal en este sistema es ${\displaystyle \,b_{4}^{\pi }=-2\,}$ con los pivotes admisibles ${\displaystyle (x_{4},\,x_{1})}$, ${\displaystyle (x_{4},\,x_{3})}$; despejamos ${\displaystyle \,x_{1}\,}$ en lugar de ${\displaystyle \,x_{4}\;}$:

Cambio de la base 2 a la base 3

(animado)

El sistema final es

${\displaystyle {\begin{matrix}z&=&(&~22&-~5x_{3}&-~~x_{4}&)~/~4\\[2pt]x_{2}&=&(&~~~8&+~2x_{3}&-~2x_{4}&)~/~4\\[2pt]x_{1}&=&(&~~~2&-~3x_{3}&+~~x_{4}&)~/~4\\[2pt]x_{5}&=&(&~~~2&+~7x_{3}&-~~x_{4}&)~/~4\end{matrix}}}$

Como este sistema satisface las condiciones de optimalidad, hemos obtenido la solución

${\displaystyle z=22/4=5.5,}$  ${\displaystyle x_{1}=2/4=0.5,}$  ${\displaystyle x_{2}=8/4=2.0,}$  ${\displaystyle x_{3}=0,}$  ${\displaystyle x_{4}=0,}$  ${\displaystyle x_{5}=2/4=0.5}$

Dualidad

Problemas duales

A todo problema de programación lineal llevado a la forma básica arriba descrita se le puede asociar un problema dual de programación lineal. Con respecto a esa forma básica, la matriz de coeficientes del problema dual es la matriz negativa traspuesta de la matriz de coeficientes del problema original, lo que muestra de paso que el dual del problema dual es el problema original, llamado problema primal en ese contexto.

${\displaystyle {\begin{matrix}w&=&-f&-&b_{1}\,y_{n+1}&-&\cdots &-&b_{m}\,y_{n+m}\\[3pt]y_{1}&=&-d_{1}&-&G_{n+1,1}\,y_{n+1}&-&\cdots &-&G_{n+m,1}\,y_{n+m}\\\vdots &&\vdots &&\vdots &&&&\vdots \\y_{n}&=&-d_{n}&-&G_{n+1,n}\,y_{n+1}&-&\cdots &-&G_{n+m,n}\,y_{n+m}\end{matrix}}}$

${\displaystyle {\begin{matrix}\max ~w,\quad y_{1}\geq 0,\ \ldots \ y_{m+n}\geq 0\end{matrix}}}$

ó, en notación compacta,

${\displaystyle {\begin{matrix}&&w&=&(-f)&+&\sum _{i\in B}\,(-b_{i})\,y_{i}\\[6pt]\forall ~j\in D&&y_{j}&=&(-d_{j})&+&\sum _{i\in B}\,(-G_{i,j})\,y_{i}\end{matrix}}}$

${\displaystyle {\begin{matrix}\max ~w\,,\quad \forall ~k\in D\cup B\quad y_{k}\geq 0\end{matrix}}}$

Como se muestra a continuación, el máximo obtenido en el problema dual (si es que existe) es igual al negativo del máximo obtenido en el problema primal.

( Precaución: Al usar la forma diccionario para escribir el problema dual, no es lícito sustituir ${\displaystyle \max ~z,\,\max ~w}$ por ${\displaystyle \min ~z,\,\min ~w}$.   A menudo el problema dual se define con una función objetivo ${\displaystyle \min \,(-w)}$ en lugar de ${\displaystyle \max \,w}$, lo que es lícito pero un tanto engorroso. )

Transformaciones sucesivas

La relación anterior entre los coeficientes de un par de problemas duales no se cumple solamente para el sistema de partida, sino que persiste paso a paso a través de un algoritmo de pivotes, siempre y cuando el pivote elegido en cada iteración sea el mismo en ambos problemas:

${\displaystyle {\begin{matrix}&&w&=&(-f^{\pi })&+&\sum _{i\in B(\pi )}\,(-b_{i}^{\pi })\,y_{i}\\[6pt]\forall ~j\in D(\pi )&&y_{j}&=&(-d_{j}^{\pi })&+&\sum _{i\in B(\pi )}\,(-G_{i,j}^{\pi })\,y_{i}\end{matrix}}}$

${\displaystyle {\begin{matrix}\max ~w\,,\quad \forall ~k\in D\cup B\quad y_{k}\geq 0\end{matrix}}}$

La relación de dualidad es particularmente fácil de observar en un sistema de pivoteo que tiene solo dos variables independientes y dos variables despejadas. El sistema obtenido es el mismo si se intercambia el estado de dos de las variables y a continuación se construye el problema dual, o si se realiza estas operaciones en orden inverso:

${\displaystyle {\begin{matrix}\delta \,x_{i}&\!=\!&(~~\alpha )&\!\!\!x_{j}&\!+\!&(~~\sigma )&\!\!\!x_{s}\\[6pt]\delta \,x_{r}&\!=\!&(~~\zeta )&\!\!\!x_{j}&\!+\!&(~~p)&\!\!\!x_{s}\end{matrix}}}$	${\displaystyle {x_{r}\leftrightarrow x_{s}}}$	${\displaystyle {\begin{matrix}p\,x_{i}&\!=\!&({\frac {\alpha p\,-\,\zeta \sigma }{\delta }})&\!\!\!x_{j}&\!+\!\!&(~\sigma )&\!\!\!x_{r}\\[6pt]p\,x_{s}&\!=\!&(~-\zeta ~)&\!\!\!x_{j}&\!+\!\!&(~\delta )&\!\!\!x_{r}\\\end{matrix}}}$
${\displaystyle -\,[\cdots ]^{\,T}}$		${\displaystyle -\,[\cdots ]^{\,T}}$
${\displaystyle {\begin{matrix}\delta \,y_{j}&\!=\!&(-\alpha )&\!\!\!y_{i}&\!+\!&(-\zeta )&\!\!\!y_{r}\\[6pt]\delta \,y_{s}&\!=\!&(-\sigma )&\!\!\!y_{i}&\!+\!&(-p)&\!\!\!y_{r}\\\end{matrix}}}$	${\displaystyle {y_{s}\leftrightarrow y_{r}}}$	${\displaystyle {\begin{matrix}p\,y_{j}&\!=\!&({\frac {\zeta \sigma \,-\,\alpha p}{\delta }})&\!\!\!y_{i}&\!+\!\!&(~~\zeta )&\!\!\!y_{s}\\[6pt]p\,y_{r}&\!=\!&(~-\sigma ~)&\!\!\!y_{i}&\!+\!\!&(-\delta )&\!\!\!y_{s}\\\end{matrix}}}$

De esta relación de dualidad se concluye que toda base optimal para el problema primal provee también una base optimal para el problema dual. Al ejemplo anteriormente desarrollado le corresponde el problema dual

${\displaystyle {\begin{matrix}~w~&=&(&~~0&-~~3y_{3}&-~~7y_{4}&-~~4y_{5}&)~/~1\\[2pt]y_{1}&=&(&-3&+~~2y_{3}&+~~2y_{4}&+~~3y_{5}&)~/~1\\[2pt]y_{2}&=&(&-2&+~~~y_{3}&+~~3y_{4}&+~~~y_{5}&)~/~1\end{matrix}}}$

${\displaystyle {\begin{matrix}\max ~w,\quad y_{1}\geq 0,\ y_{2}\geq 0,\ y_{3}\geq 0,\ y_{4}\geq 0,\ y_{5}\geq 0\end{matrix}}}$

El sistema optimal de este problema es entonces

${\displaystyle {\begin{matrix}~w~&=&(&-22&-~~8y_{2}&-~~2y_{1}&-~~2y_{5}&)~/~4\\[2pt]y_{3}&=&(&~~~5&-~~2y_{2}&+~~3y_{1}&-~~7y_{5}&)~/~4\\[2pt]y_{4}&=&(&~~~1&+~~2y_{2}&-~~~y_{1}&+~~~y_{5}&)~/~4\end{matrix}}}$

En el problema original, la variable a maximizarse toma el valor óptimo ${\displaystyle z=22/4}$; el valor óptimo del problema dual es el negativo de este valor: el mayor valor posible que su variable objetivo puede adoptar es ${\displaystyle w=-z=-22/4=-5.5}$. Una posible solución óptima para el problema dual es

${\displaystyle y_{1}=0,}$  ${\displaystyle y_{2}=0,}$  ${\displaystyle y_{3}=5/4=1.25,}$  ${\displaystyle y_{4}=1/4=0.25,}$  ${\displaystyle y_{5}=0}$.

Tratamiento conjunto

Una importante consecuencia teórica de la dualidad es la siguiente: para resolver problemas de optimización lineal no se requiere un algoritmo que maximice (o minimice) una de las variables, basta para ello cualquier algoritmo capaz de resolver sistemas de desigualdades lineales. Esto es así porque las relaciones de dualidad implican que toda base optimal para el problema primal también provee una base optimal para el problema dual, donde el valor óptimo de la variable ${\displaystyle w\,}$ del problema dual es el negativo del valor óptimo de la variable ${\displaystyle z\,}$ del problema original. Por tanto, para pares de soluciones óptimas se tiene

${\displaystyle z+w~=~(\max z)\!+\!(\max w)}$   ${\displaystyle ~=~(\max z)\!+\!(-\max z)~=~0}$

Por otro lado, para pares de soluciones factibles de las cuales al menos una no es óptima se cumple

${\displaystyle z+w~<~(\max z)\!+\!(\max w)~=~0}$

De ahí podemos concluir que las soluciones óptimas para un par de problemas duales son exactamente las soluciones de los sistemas de igualdades escritos arriba más las siguientes desigualdades,

${\displaystyle z\,+\,w\,\geq \,0,\qquad \forall ~k\in D\cup B\qquad x_{k}\geq 0,\quad y_{k}\geq 0,}$

lo que se reduce a

${\displaystyle {\begin{matrix}\forall ~i\in B\quad x_{i}~=~b_{i}~+~\sum _{j\in D}\,G_{i,j}\,x_{j}\\[6pt]\forall ~j\in D\quad y_{j}~=~(-d_{j})~+~\sum _{i\in B}\,(-G_{i,j})\,y_{i}\\[6pt]\sum _{j\in D}\,d_{j}\,x_{j}~~+~~\sum _{i\in B}\,(-b_{i})\,y_{i}~~\geq ~~0\\[6pt]\forall ~k\in D\cup B\qquad x_{k}\geq 0,\quad y_{k}\geq 0\end{matrix}}}$

En el caso de aplicaciones prácticas, sin embargo, esta forma de proceder solo es competitiva si se logra aprovechar adecuadamente la estructura de datos común a los sistemas primal y dual.

Problemas con muchas variables

La implementación computacional de problemas prácticos a menudo dista mucho de ser trivial.^[7] Los coeficientes de sistemas con decenas de miles de variables siempre presentan una u otra estructura, la cual debe ser aprovechada para determinar los sistemas de iteraciones subsecuentes de manera relativamente rápida y numéricamente estable (sin mayores errores de redondeo):

• Los sistemas iniciales de problemas grandes (no los sistemas transformados) contienen una inmensa mayoría de coeficientes iguales a cero (el sistema es disperso), lo que permite ahorrar muchas operaciones aritméticas si se recurre al sistema de partida.
• Muchos procedimientos se basan en una evaluación retardada, donde se calcula solo aquellos coeficientes de un sistema que sean necesarios para determinar un pivote, y esto solamente en el instante en que se ocupan. Para evitar la evaluación de coeficientes superfluos tales procedimientos emplean permutaciones de las variables en el sistema de partida, factorizaciones de las inversas de matrices básicas, una factorización de la matriz de coeficientes, y otras técnicas más. En todos estos casos suele ser necesario referirse a sistemas de iteraciones previas a la última, por lo que las transformaciones adoptan formas bastante más complejas que la directa.
• A menudo se encuentran insertas en la estructura del sistema diversas estructuras especiales, por ejemplo de flujos en redes,^[1][8] y para tales estructuras especiales se ha desarrollado implementaciones particularmente eficientes.

No obstante lo anterior, hay también muchas aplicaciones que dan origen a problemas de tamaño moderado, para los cuales basta una implementación simple como la presentada.

Herramienta interactiva

El applet de pivoteo interactivo de Robert Vanderbei, programado en 1997, permite definir un sistema de ecuaciones lineales de tamaño reducido y realizar en ese sistema pivoteos sobre pares arbitrarios de variables. La herramienta (en inglés) se autodenomina «Simplex Pivot Tool», pero está orientada a algoritmos de pivote totalmente arbitrarios. Para evitar redondeo, los coeficientes del sistema pueden también verse en forma de fracciones, aunque éstas no adoptan un denominador común.

Literatura complementaria

• George Dantzig (1963): Linear Programming and Extensions, Princeton University Press, archivo pdf
• Vašek Chvátal (1983): Linear Programming, Freeman and Company, New York NY, ISBN 0-7167-1587-2
• Robert Vanderbei (2007): Linear Programming. Foundations and Extensions, 3a ed., Springer, ISBN 978-0-387-74387-5, archivo pdf

Referencias

1. Vašek Chvátal (1983): Linear Programming., Freeman and Company, ISBN 0-716-71587-2
2. Robert Vanderbei (1996/2007): Linear Programming; Foundations and Extensions, 3.ed. Springer, ISBN 978-0-387-74385-5, archivo pdf, (edición alternativa: Linear Programming; Foundations and Extensions, Kluwer, 1996, ISBN 0-7923-9804-1)
3. Komei Fukuda & Tamás Terlaky (1997): Criss-cross methods: A fresh view on pivot algorithms, Mathematical Programming, 79, 369-395, archivo ps (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).
4. Robert Vanderbei: Linear Programming. Foundations and Extensions, Kluwer, ISBN 978-0-7923-9804-2}}, capítulo 21.4: Simplex Method vs Interior-Point Methods.
5. Komei Fukuda & Tamás Terlaky (1999): On the Existence of a Short Admissible Pivot Sequences for Feasibility and Linear Optimization Problems, Pure Mathematics and Applications, vol.10, 431-447, archivo ps (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).
6. Erwin Bareiss (1968): Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination, Mathematics of Computation, vol.22 (102), 565-578, archivo pdf
7. Robert Vanderbei: Linear Programming. Foundations and Extensions (= International Series in Operations Research & Management Science. Bd. 114). 3rd edition. Springer, New York NY 2007, ISBN 978-0-387-74387-5, Kapitel 8: Implementation Issues.
8. Robert Vanderbei: Linear Programming. Foundations and Extensions (= International Series in Operations Research & Management Science. Bd. 114). 3rd edition. Springer, New York NY 2007, ISBN 978-0-387-74387-5, Kapitel 13: Network Flow Problems.

• Datos: Q2097496