Lexikografické a Blandovo pravidlo

Degenerované úlohy a anticyklické pravidlá

V prípade degenerovaných úloh lineárneho programovania sa v priebehu výpočtu môže stať, že pri výbere pivota v danom stĺpci nebude len jeden minimálny podiel. Dôsledkom takejto situácie bude, že sa v nasledujúcom kroku objaví v simplexovej tabuľke v nultom stĺpci aspoň jedna z bázických premenných s hodnotou \(0\). V takomto prípade nedôjde ku zmene hodnoty účelovej funkcie v ďalšom kroku prechodu od jednej bázy k druhej. Z tohto dôvodu je tu nebezpečie, že sa budeme znovu vracať k bázam, ktoré sme už predtým prechádzali (t.j. vzniká tu nebezpečie zacyklenia algoritmu). Existuje viacero spôsobov ako takejto situácii predísť. Základnou myšlienkou je upresnenie pravidiel výberu kľúčového  stĺpca a riadku tak, aby bol výber vždy jednoznačný. Takýmito  pravidlami sú lexikografické a Blandovo pravidlo.

Cyklom rozumieme konečnú postupnosť krokov simplexového algoritmu, ktorý začína a končí rovnakou bázou a teda aj rovnakou simplexovou tabuľkou.

Vlastnosť cyklu:

V priebehu každého cyklu sa hodnoty pravých strán ohraničení v nultom stĺpci nemenia a v každom kroku algoritmu pre riadok \(i\), ktorý obsahuje pivot platí, že \(x_{i0}=0\).

Lexikografické pravidlo

Autormi sú Dantzig, Orden a Wolfe. Od základnej procedúry sa líši iba spresneným výberom pivotového riadku, ktorý sa určuje pomocou zložitejšieho pravidla a to v prípade, ak by mohlo dôjsť k zacykleniu úlohy. Túto metódu môžeme použiť v ľubovoľnej iterácii za predpokladu primárnej prípustnosti simplexovej tabuľky.

Vektor \(\vec{x}=(x_1,\dots,x_n)^T\) je lexikograficky väčší ako vektor \(\vec{y}=(y_1,\dots,y_n)^T\), píšeme \(\vec{x}\succ\vec{y}\), ak platí \[(\exists i) (x_i>y_i) \wedge (\forall j<i) (x_i=y_j).\]Vektor \(\vec{x}\) je lexikograficky kladný, ak \(\vec{x}\succ\vec{0}\) t.j. ak prvá jeho nenulová zložka je kladná.

Algoritmus lexikografického pravidla:

Nech sú všetky riadky v simplexovej tabuľke lexikograficky kladné (okrem nultého), t.j. úloha je primárne prípustná. Pravidlá pre výber riadkov a stĺpcov:

• výber ľubovoľného stĺpca \(j\in\{1,\dots,n\}\) s relatívnou cenou \(\overline{c_j}<0\), odporúča sa výber stĺpca s najnižšou relatívnou cenou.
• výber riadka \(i\in\{1,\dots,m\}\), v ktorom sa nadobúda lexikografické minimum z riadkov simplexovej tabuľky \(\displaystyle\frac{1}{x_{ij}}(x_{i0},\dots,x_{in})^T\) pre \(x_{ij}>0\), t.j. v prípade, ak výber pivota nie je jednoznačný \[\lambda=\lambda(k)=\frac{x_{k0}}{x_{kj}}=\min \left\{\frac{x_{l0}}{x_{lj}}: \hbox{pre }l \hbox{ také, že }x_{lj}>0\right\}, \hbox{ pre } k\in K\subseteq\{1,\dots,m\}\]
  vyberáme \(i\)-ty riadok tak, aby  vektor \(\frac{1}{x_{ij}}(x_{i0},\dots,x_{in})^T\) bol lexikograficky minimálny zo všetkých vektorov \(\frac{1}{x_{kj}}(x_{k0},\dots,x_{kn})^T\)  pre dané  \(k\in K\).

Základné vlastnosti algoritmu:

• na základe pravidiel výberu pivota v zmysle lexikografického usporiadania riadky zostávajú lexikograficky kladné;
• na základe pravidiel výberu pivota v zmysle lexikografického usporiadania a predchádzajúcej vlastnosti nultý riadok ostro lexikograficky rastie;
• z predchádzajúcej vlastnosti vyplýva, že simplexová metóda skončí po konečnom počte krokov, t.j algoritmus je konečný.
   

Blandovo pravidlo

Autorom je Bland (1977). Blandovo pravidlo je známe aj ako pravidlo najmenších indexov požaduje voľbu pivotovaného stĺpca s najmenším indexom (t.j. minimálne \(j\) s príslušnou zápornou relatívnou cenou) a z možných pivotovaných riadkov pre dané \(j\) ak výber pivota nie je jednoznačný kvôli viacerým rovnakým minimálnym podielom potom volíme ten, ktorého bázická premenná má minimálny index (t.j. \(B_k\) - "`index bázickej premennej v \(k\)-tom riadku"' je minimálny možný pre už zvolené \(j\)). Inak povedané, medzi bázické indexy prichádza minimálny možný a odchádza tiež z minimálny možný index. V revidovanej metóde je lexikografické pravidlo nepoužiteľné, no pravidlo najmenších indexov sa aplikuje bez problémov.

Myšlienka algoritmu:

Uvažujme základný problém \[\min\{c^Tx:Ax=b,x\geq 0\},\]kde \(A\) je matica typu \(m\times n\) pre \(m\leq n\) a nech \(B=(B_1,\dots,B_m)\) je usporiadaná \(m\)-tica vzájomne rôznych čísel z \(\{1,\dots,n\}\). Cieľom v danom kroku algoritmu je prejsť od \(B=(B_1,\dots,B_{i-1},B_i,B_{i+1},\dots,B_m)\) k \(B^{'}=(B_1,\dots,B_{i-1},B_j,B_{i+1},\dots,B_m)\), t.j v \(j\)-tom stĺpci sa má objaviť \(i\)-ty stĺpec jednotkovej matice. Inak povedané, aktuálnu simplexovú tabuľku prepivotujeme prvkom \(x_{ij}\). Samozrejmou požiadavkou pri výbere pivota je zachovanie primárnej prípustnosti simplexovej tabuľky, zachovanie bázičnosti a klesajúcosť hodnoty účelovej funkcie, z čoho dostávame nasledovné podmienky: \(x_{ij}>0\), \(\displaystyle\frac{x_{i0}}{x_{ij}}=\min \left\{\frac{x_{k0}}{x_{kj}}, x_{kj}>0\right\}\) a \(\overline{c_j}<0\).

Algoritmus Blandovho pravidla:

Nech v simplexovej tabuľke nie je splnená podmienka optimality a úloha nie je neohraničená.

• výber prvého stĺpca \(j\in\{1,\dots,n\}\) zľava s relatívnou cenou \(\overline{c_j}<0\), t.j. \[j=\min\{s:\overline{c_s}<0\}\]
• výber riadka \(i\in\{1,\dots,m\}\) s pivotom \(x_{ij}>0\) tak, aby  \(\frac{x_{i0}}{x_{ij}}=\min \left\{\frac{x_{k0}}{x_{kj}}, x_{kj}>0\right\}\). Ak výber pivota nie je jednoznačný \[\lambda=\lambda(k)=\frac{x_{k0}}{x_{kj}}=\min \left\{\frac{x_{l0}}{x_{lj}}: \hbox{pre }l \hbox{ také, že }x_{lj}>0\right\}, \hbox{ pre } k\in K\subseteq\{1,\dots,m\}\]vyberáme \(i\)-ty riadok tak, aby  \(i=\min\{B_k: k\in K\}\).