Shetty - Lemkeho algoritmus

Shetty - Lemkeho metóda patrí medzi simplexové algoritmy a je založená na hľadaní bodu vyhovujúceho podmienkam optimálnosti Kuhn - Tuckera. Myšlienkou je zavedenie pomocnej premennej \(\mu\) do riadkov, v ktorých má vektor \(\vec{p}\) a \(\vec{b}\) zápornú zložku. Uvažujme všeobecnú formuláciu úlohy \(\hbox{KP}\) v tvare \[f(x)=x^TCx+p^Tx\to \min\hbox{ pre }x\in D,\]kde \(D\) je konvexná polyedrálna množina \(\mathbb{R}^n\) v špeciálnom tvare \(D_1=\{x:Ax\leq b,x\geq 0\}\). \(n\) - počet rozhodovacích premenných úlohy, \(x\in\mathbb{R}^n\) - vektor rozhodovacích premenných, \(C\) - je symetrická pozitívne semidefinitná matica \(n\)-tého stupňa, \(p\in\mathbb{R}^n\) - vektor lineárnej formy a \(A\) - matica sústavy ohraničení rozmeru \(m\times n\).

Inicializačná fáza:

Podmienky optimálnosti Kuhn - Tuckera (pozri  sekciu Kuhn - Tuckerove podmienky) upravíme o parameter \(\mu\) s príslušnými koeficientami \[-2Cx-A^Tu+v+q\mu=p\]\[Ax+y+t\mu =b\]\[x^Tv=0\hbox{ a }y^Tu=0\]\[x\geq 0,\,y\geq 0,\,u\geq 0,\, v\geq 0,\]kde \(q\in\mathbb{R}^n\) a \(t\in\mathbb{R}^m\) sú vektory definované nasledovne: \[q_j=\begin{cases}-1,& \hbox{ pre }p_j<0\\ 0, &\hbox{ pre }p_j\geq 0\end{cases}\quad t_i=\begin{cases}-1,& \hbox{ pre }b_i<0\\ 0, &\hbox{ pre }b_i\geq 0.\end{cases}\]

Fáza riešenia:

Riešením danej sústavy rovníc zodpovedá simplexová tabuľka v tvare:

a východiskové bázické riešenie \(\vec{x}=\vec{0}\), \(\vec{u}=\vec{0}\), \(\vec{v}=\vec{p}\), \(\vec{y}=\vec{b}\), \(\mu=0\).

1. Ak \(\vec{v}\geq \vec{0}\) a \(\vec{y}\geq \vec{0}\), tak vektor \(\vec{x}=\vec{0}\) je optimálnym riešením úlohy.
2. Inak realizujeme elementárnu zmenu bázy, pri ktorej sa vedúcim stĺpcom stáva stĺpec reprezentovaný premennou \(\mu\) a vedúci riadok  je určený minimálnym prvok pravej strany. Pokračujeme pokiaľ premenná \(\mu\) nevystúpi z bázy.

Nezápornosť vektorov \(\vec{x}\), \(\vec{v}\), \(\vec{v}\), \(\vec{y}\) garantuje kritérium prípustnosti riešenia pri primárnom riešení simplexovej metódy.

Pravidlo výpočtu:

Ak z bázy vystúpila v \((k-1)\) - ej iterácii premenná \(v_j\) (resp. \(x_j\)), alebo \(y_i\) (resp. \(u_i\)), tak v aktuálnej \((k)\) - ej iterácii vstúpi do bázy premenná \(x_j\) (resp. \(v_j\)), alebo \(u_i\) (resp. \(y_i\)).