Algoritme de pivot

Els algoritmes de pivot (o algoritmes de canvi de base) són algoritmes de l'optimisació matemàtica, i en especial de la Programació Llineal. Donat un sistema d'equacions llineals que les seues variables deuen adoptar valors no negatius (essencialment lo mateix que un sistema d'inecuaciones llineals), es busca la millor d'entre moltes solucions alternatives, és dir, una solució òptima del sistema. En cada pas de tal busca, l'algoritme transforma el sistema sense alterar el seu conjunt de solucions. Algoritmes de pivot importants són els diversos algoritmes simplex i els algoritmes criss-cross.

Els algoritmes de pivot són de gran importància per al tractament de inecuaciones llineals, a on juguen un paper anàlec al de l'eliminació de Gauss para equacions llineals. Es troben numeroses aplicacions de sistemes de inecuaciones en àrees tan diverses com l'investigació d'operacions industrials, el transporte i distribució de bens, en carteres de valors, l'ingenieria estructural, l'estadística, i la teoria de jocs. Freqüentment s'aborden sistemes en decenes de mils de variables.

Procediment general

El problema normalisat

Tot algoritme de pivot partix d'un sistema especialment arreglat d'equacions llineals, que les seues variables totes, llevat tal volta una, deuen prendre valors no negatius. De fet, qualsevol sistema de inecuaciones o equacions llineals, aixina com tot problema de Programació Llineal, pugues sempre reduir-se a la següent forma diccionari:

$\begin{array}{ccccccccc}z& =& f& +& d_1{x}_1& +& \cdots & +& d_n{x}_n\\ x_{n+1}& =& b_{n+1}& +& G_{n+1,1}{x}_1& +& \cdots & +& G_{n+1,n}{x}_n\\ ⋮& & ⋮& & ⋮& & & & ⋮\\ x_{n+m}& =& b_{n+m}& +& G_{n+m,1}{x}_1& +& \cdots & +& G_{n+m,n}{x}_n\end{array}$

$\begin{array}{c}\max z,x_1\ge 0,\dots x_{n+m}\ge 0,\end{array}$

a on els $f,d_j,b_i,G_{i,j}$ són número real (en la pràctica casi sempre números racionals). Este format especifica que es busca valors per a les incògnites $x_1,\dots x_{n+m},z$, que satisfacen les ecuacionés i inecuacionés del sistema anterior de modo tal que la variable objectiu $z$ prenga el major valor possible.

( En convertir un problema a la forma anterior no disminuïx el número de desigualtats; estes permaneixen en la seua totalitat i només es convertixen en condicions de no-negatividad d'algunes variables. D'esta manera, una inecuación com per eixemple

$3x_1+4x_2-x_3\le 5x_1+8$

és substituïda per

$x_4=8+2x_1-4x_2+x_3,x_4\ge 0$   )

Definint els conjunts d'índexs

$D=\{1,\dots ,n\},B=\{n+1,\dots ,n+m\}$

s'escriurà açò en lo que seguix de la forma més compacta

$\begin{array}{ccccccc}& & z& =& f& +& \sum _{j\in D}{d}_j{x}_j\\ \mathrm{\forall }i\in B& & x_i& =& b_i& +& \sum _{j\in D}{G}_{i,j}{x}_j\end{array}$

$\begin{array}{c}\max z,\mathrm{\forall }k\in D\cup B{x}_k\ge 0\end{array}$

En cada iteración d'un algoritme de pivot es destaca un conjunt de variables independents, mentres que les restants són variables dependents i s'expressen com a funcions llineals de les primeres. En passar d'una iteración a la següent s'intercanvia una variable independent per una depenent; tals parells de variables es denominen pivots.

Condicions de optimalidad

En cas de que es complixquen les següents dos condicions de optimalidad,

• $b_i\ge 0$  per a tot  $i\in B$  (sistema factible)   i
• $d_j\le 0$  per a tot  $j\in D$  (sistema acotat),

podem obtindre una solució al problema anterior, assignant a les variables independents del sistema els valors $x_1=0,\dots ,x_n=0$.  Per un costat, açò conseguix que les variables depenents $x_{n+1}=b_{n+1},\dots ,x_{n+m}=b_{n+m}$ adopten valors nonegativos, tal com es demanava. Per un atre costat, tota solució alternativa al problema deu satisfer la relació $z\le f$,  ya que en ella les variables independents també deuen prendre valors nonegativos.

( Per eixemple, en el següent sistema,

$\begin{array}{ccccc}z& =& 0& -3x_1& +{𝐱}_{\mathrm{𝟐}}\\ x_3& =& 3& -x_1& -x_2\\ x_4& =& 8& +2x_1& -4x_2\\ x_5& =& -\mathrm{𝟏}& +3x_1& +x_2\end{array}$

les condicions de optimalidad són violades en dos llocs, ya que  $b_5=-1<0$  i  $d_2=+1>0$.  Per un costat, els valors obtinguts en anular les variables independents,  $x_1=x_2=0$,  no constituïxen una solució admissible perque contenen un valor negatiu,  $x_5=-1$.  Per un atre costat, no podem descartar la possibilitat d'aumentar el valor que adopta la variable objectiu  $z=-3x_1+x_2$  elegint conjunts de variables independents en $x_2>0$. )

Transformació de les equacions

En el cas habitual de que les condicions de optimalidad no es complixquen, pot reformular-se el sistema d'equacions, elegint adequadament un nou subconjunt $B$ d'entre les $n+m$ incògnites, i expressant les incògnites elegides en funció de les incògnites restants.  Siga $\omega$ un reordenamiento de les variables, és dir una funció dels índexs que complixca

$\{x_{\omega (1)},\dots x_{\omega (n+m)}\}=\{x_1,\dots x_{n+m}\}.$

A partir de la partició $\pi =(D(\pi ),B(\pi ))$, en

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

que dividix les variables del sistema en variables independents $x_j$ en $j\in D(\pi )$ i les cridades variables bàsiques $x_i$ en $i\in B(\pi )$, es construïx llavors el sistema:

$\begin{array}{ccccccc}& & z& =& f^{\pi }& +& \sum _{j\in D(\pi )}{d}_j^{\pi }{x}_j\\ \mathrm{\forall }i\in B(\pi )& & x_i& =& b_i^{\pi }& +& \sum _{j\in D(\pi )}{G}_{i,j}^{\pi }{x}_j\end{array}$

$\begin{array}{c}\max z,\mathrm{\forall }k\in D\cup B{x}_k\ge 0\end{array}$

Note's que els coeficients $G_{i,j}^{\pi }$ existixen solament per a parells de subíndexs en $i\in B(\pi )$ i en $j\in D(\pi )$. En cada iteración, els coeficients del sistema aixina modificat tornen a examinar-se per a vore si satisfan les condicions de optimalidad

• $b_i^{\pi }\ge 0$  per a tot  $i\in B(\pi )$  (sistema factible)   i
• $d_j^{\pi }\le 0$  per a tot  $j\in D(\pi )$  (sistema acotat),

i d'esta manera generen una possible solució al problema. Un resultat estàndar de la Programació Llineal establix que tot problema que té solucions també posseïx un conjunt de variables bàsiques que conduïx a una d'elles. Si els coeficients del sistema satisfan les condicions de optimalidad, es diu que les variables bàsiques formen una base optimal del problema.

Pivots admissibles

Un coeficient no nul $G_{k,l}^{\pi }\ne 0$ del sistema d'equacions es diu element pivot, perque permet rebujar la variable independent $x_l$ en lloc de la variable bàsica $x_k,$ per a aixina seguir buscant una solució al problema. No obstant, els algoritmes de pivot no elegixen un element pivot qualsevol, sino solament els cridats pivots admissibles $(x_k,x_l)$, que deuen satisfer:

• O es complix simultàneament  $b_k^{\pi }<0$   i   $G_{k,l}^{\pi }>0$   (pivot de restricció),
• o es complix simultàneament  $d_l^{\pi }>0$   i   $G_{k,l}^{\pi }<0$   (pivot d'objectiu).

( En l'eixemple anterior,

$\begin{array}{ccccc}z& =& 0& -3x_1& +{𝐱}_{\mathrm{𝟐}}\\ x_3& =& 3& -x_1& -\underset{\_}{{𝐱}_{\mathrm{𝟐}}}\\ x_4& =& 8& +2x_1& -\underset{\_}{\mathrm{𝟒}{𝐱}_{\mathrm{𝟐}}}\\ x_5& =& -\mathrm{𝟏}& +\underset{\_}{\mathrm{𝟑}{𝐱}_{\mathrm{𝟏}}}& +\underset{\_}{{𝐱}_{\mathrm{𝟐}}}\end{array}$

el coeficient no optimal  $b_5<0$  permet seleccionar l'element pivot  $G_{5,1}=+3>0,$  corresponent a un pivot admissible en intercanvi de $(x_5,x_1),$ o també l'element pivot  $G_{5,2}=+1>0$  corresponent al pivot admissible $(x_5,x_2).$  Alternativament, el coeficient no optimal  $d_2>0$  permet també seleccionar l'element pivot  $G_{3,2}=-1<0$  corresponent al pivot admissible $(x_2,x_3),$  o l'element pivot  $G_{4,2}=-4<0$  en el pivot admissible $(x_2,x_4)$. )

La restricció a pivots admissibles impedix que en dos iteraciones successives s'elegixca el mateix pivot. Les regles segons les quals el pivot és elegit depenen de l'algoritme de pivot particular. No obstant, deu impondre's que l'algoritme termine en un número finito de passos, lo que no succeïx en una elecció de pivots inadequada. Fukuda & Terlaky varen demostrar en 1999 que para tot problema en solució i per a tota base inicial existix una seqüència de lo més $n+m$ pivots admissibles que conduïx a una base optimal. Llamentablement, eixa demostració no és constructiva en el sentit de que indique quin pivot dega elegir-se en cada pas.

Com es pot observar de les definicions anteriors, una base optimal no té pivots admissibles, per lo que l'algoritme no pot ser continuat a partir d'una base optimal. Per un atre costat, és fàcil demostrar en arguments similars als exposts que una base no optimal sense pivots admissibles sempre pertany a un problema sense solució; siga açò, perque el sistema d'equacions i inecuaciones no té solució alguna (problema infactible), o perque existixen solucions en un valor objectiu $z$ arbitrariamente gran (problema no acotat).

Implementació sense errors de grosseig

Per a evitar errors de grosseig es treballa en lo que seguix en número racional, elegint un únic denominador comú per a tot el sistema d'equacions. Per a trobar un denominador aixina en cada pas de l'algoritme no fa falta analisar els coeficients del sistema; en cas d'un sistema inicial en coeficients sancers, en cada iteración es complirà que

• El numerador de l'element pivot és un denominador comú per al sistema d'equacions següent.

En evaluar els coeficients d'un nou sistema el denominador comú del sistema anterior quedarà obsolet, per lo que es procedix a dividir els coeficients del sistema nou pel denominador antic, en resultats que sempre seran sancers.

Un apany matricial que conté els coeficients d'un sistema de pivot sol cridar-se taula de pivoteo o quadro de pivoteo. El següent esquema mostra cóm canvien els coeficients del sistema de pivoteo en passar d'una iteración a la que seguix:

$\begin{array}{ccccccc}\delta x_i& =& (\alpha )& x_j& +& (\sigma )& x_s\\ \delta x_r& =& (\zeta )& x_j& +& (p)& x_s\end{array}$

$x_r\leftrightarrow x_s$

$\begin{array}{ccccccc}p{x}_i& =& (\frac{\alpha p-\zeta \sigma }{\delta })& x_j& +& (\sigma )& x_r\\ p{x}_s& =& (-\zeta )& x_j& +& (\delta )& x_r\end{array}$

En eixe esquema, el símbol $\delta$ designa al denominador comú del sistema d'equacions, el símbol $p$ designa al numerador de l'element pivot, $\zeta$ designa qualsevol coeficient restant en la mateixa fila de l'element pivot, $\sigma$ designa qualsevol coeficient restant en la mateixa columna de l'element pivot, i $\alpha$ qualsevol coeficient alié a la fila i a la columna del pivot. Els coeficients $d_j^{\pi }$ de la variable a maximizar ($x_i=z$) i els coeficients $b_i^{\pi }$ de la columna de valors ($x_j=1$) es transformen d'acort a les mateixes regles.

Eixemple ilustrat

Representació gràfica

Les ilustracions en cada pas de l'eixemple següent mostren totes el mateix sistema d'equacions graficado en distints sistemes de coordenades. En estos gràfics,

• l'àrea vorejada de vert és el conjunt de solucions factibles, per al qual totes les variables prenen valors no negatius,
• els eixos de coordenades corresponen a equacions $x_k=0$ de variables independents, les demés rectes a equacions de variables bàsiques,
• la recta en roig recorre els punts a on la variable objectiu adopta el seu valor màxim,
• les interseccions de rectes corresponents a pivots admissibles duen punts rojos, el pivot seleccionat va vorejat de negre, i
• l'àrea anaranjada correspon al ortante no negatiu de la iteración següent.

Eixemple d'elecció de pivots

La següent estratègia d'elecció de pivot correspon a l'algoritme criss-cross en pivoteo en els índexs mínims (minimal index criss-cross-algorithm). En cada pas, el pivot admissible s'elegirà d'acort a la següent regla (el mínim d'un conjunt buit es considera igual a infinit):

1. Determinar els índexs $r=\min \{i\in B(\pi )|b_i^{\pi }<0\}$   i   $s=\min \{j\in D(\pi )|d_j^{\pi }>0\}$.
2. Si es té $r<s$,  elegir el pivot $(x_r,x_l)$  a on  $l=\min \{j\in D(\pi )|G_{r,j}^{\pi }>0\}$.
3. Si es té $s<r$,  elegir el pivot $(x_k,x_s)$  a on  $k=\min \{i\in B(\pi )|G_{i,s}^{\pi }<0\}$.

Es pot demostrar que este criteri simple (encara que no sempre eficient) conduïx sempre a una base optimal en un sistema que tinga solució.

En el següent eixemple es busca valors no negatius per a les variables $x_1\ge 0,\dots x_5\ge 0$ que maximizar la variable adicional $z$ satisfent el següent conjunt d'equacions llineals:

$\begin{array}{ccccccc}z& =& (& 0& +\mathrm{𝟑}{𝐱}_{\mathrm{𝟏}}& +2x_2& )/1\\ x_3& =& (& 3& -\underset{\_}{\mathrm{𝟐}{𝐱}_{\mathrm{𝟏}}}& -x_2& )/1\\ x_4& =& (& 7& -2x_1& -3x_2& )/1\\ x_5& =& (& 4& -3x_1& -x_2& )/1\end{array}$

En el sistema inicial de l'eixemple, els coeficients no optimales són $d_1=3$, $d_2=2$, i tots els pivots són admissibles. El criteri de selecció, no obstant, prescriu que rebugem $x_1$ en lloc de $x_3$:

(Ilustració animada d'un pas de l'algoritme de pivot)

Canvi de la base 0 a la base 1

(per a animar en Firefox, pulsar ací i després en l'image, mantenint pressionat)

En això obtenim:

$\begin{array}{ccccccc}z& =& (& 9& -3x_3& +{𝐱}_{\mathrm{𝟐}}& )/2\\ x_1& =& (& 3& -x_3& -\underset{\_}{{𝐱}_{\mathrm{𝟐}}}& )/2\\ x_4& =& (& 8& +2x_3& -4x_2& )/2\\ x_5& =& (& -1& +3x_3& +x_2& )/2\end{array}$

Ara els coeficients no optimales són $d_2^{\pi }=1/2$ en els pivots admissibles $(x_2,x_1)$, $(x_2,x_4)$, i el coeficient $b_5^{\pi }=-1/2$ en els pivots admissibles $(x_5,x_2)$, $(x_5,x_3)$. En conseqüència, rebugem $x_2$ en lloc de $x_1$:

(Ilustració animada d'un pas de l'algoritme de pivot)

Canvi de la base 1 a la base 2

(animat)

S'obté el sistema

$\begin{array}{ccccccc}z& =& (& 6& -2x_3& -x_1& )/1\\ x_2& =& (& 3& -x_3& -2x_1& )/1\\ x_4& =& (& -\mathrm{𝟐}& +3x_3& +\underset{\_}{\mathrm{𝟒}{𝐱}_{\mathrm{𝟏}}}& )/1\\ x_5& =& (& 1& +x_3& -x_1& )/1\end{array}$

L'únic coeficient no optimal en este sistema és $b_4^{\pi }=-2$ en els pivots admissibles $(x_4,x_1)$, $(x_4,x_3)$; rebugem $x_1$ en lloc de $x_4$:

(Ilustració animada d'un pas de l'algoritme de pivot)

Canvi de la base 2 a la base 3

(animat)

El sistema final és

$\begin{array}{ccccccc}z& =& (& 22& -5x_3& -x_4& )/4\\ x_2& =& (& 8& +2x_3& -2x_4& )/4\\ x_1& =& (& 2& -3x_3& +x_4& )/4\\ x_5& =& (& 2& +7x_3& -x_4& )/4\end{array}$

Com este sistema satisfà les condicions de optimalidad, hem obtingut la solució

$z=22/4=5.5,$  $x_1=2/4=0.5,$  $x_2=8/4=2.0,$  $x_3=0,$  $x_4=0,$  $x_5=2/4=0.5$