Duálny algoritmus

Na úvod je potrebné si zopakovať dôležité pojmy:

• Úloha \(\hbox{LP}\) je prípustná, ak má aspoň jedno prípustné riešenie. V opačnom prípade je neprípustná.
• Tabuľka je primárne prípustná, ak \(x_{i0} \geq 0\) pre každé \(i = 1,\dots,m\). Simplexová tabuľka je duálne prípustná, ak \(x_{0j} \geq 0\) pre každé \(j = 1,\dots,n\).
• Simplexová tabuľka úlohy je optimálna, ak je primárne aj duálne prípustná.

Ak úloha \(\hbox{LP}\) nie je primárne prípustná, tak teória duality nám umožňuje riešiť namiesto danej primárnej úlohy k nej príslušnú duálnu úlohu a následne z optimálnej tabuľky určiť výsledok aj pre pôvodnú primárnu úlohu. Lemke (1954) navrhol postup, pomocou ktorého môžeme riešiť priamo pôvodnú primárnu úlohu bez nejakého explicitného prechodu k duálnej úlohe. Keďže v daných krokoch postupujeme po prípustných riešeniach duálnej úlohy, tak algoritmus dostal aj názov duálna simplexová metóda alebo duálny algoritmus. Zapísaním úlohy do simplexovej tabuľky, ktorá musí byť duálne prípustná, sa snažíme dosiahnuť aj primárnu prípustnosť vhodným výberom pivota spomedzi záporných elementov podľa istého pravidla, ktoré nám zabezpečí po prepivotovaní duálnu prípustnosť.

Algoritmus:

Nech  je úloha  \(\hbox{LP}\) duálne prípustná, ale nie je primárne prípustná. Pravidlá pre výber riadkov a stĺpcov:

• výber riadka \(i\in\{1,\dots,m\}\), pre ktorý  \(x_{i0}<0\),
• výber stĺpca  \(j\in\{1,\dots,n\}\) s pivotom \(x_{ij}<0\) tak, aby  \[\lambda=\frac{x_{0i}}{x_{ij}}=\max \left\{\frac{x_{0k}}{x_{ik}}:\hbox{pre }k \hbox{ také, že } x_{ik}<0\right\}.\]
• ak v každom riadku \(x_{i0}<0\) je \(x_{ij}\geq 0\) pre každé \(j\in\{1,\dots,n\}\), tak úloha \(\hbox{LP}\) je neprípustná.

Vlastnosti duálneho algoritmu:

• nevýhodou algoritmu je, že prípustné riešenie nájdeme až vtedy, keď je zároveň optimálne, t.j. na konci výpočtov;
• významné využitie má hlavne v parametrickom a celočíselnom programovaní.

Postup  ako  dosiahnuť, aby bola úloha duálne prípustná v prípade, ak nie je:

• Vytvorení­m umelého obmedzenia \(\displaystyle\sum_{j\in N}x_j\leq M\), kde \(M\) je veľké číslo. (V úlohách z praktického života vieme nájsť takéto ohraničenie s požiadavkou, aby dané obmedzenie neovplyvnilo optimálne riešenie pôvodnej úlohy.) Zavedenením pomocnej premennej \(x_{n+1}\) do danej nerovnosti, môžeme rozšíriť pôvodnú simplexovú tabuľku o \(1\) riadok a o \(1\) stĺpec. Vyberáme pivota zo stĺpca s minimálnou zápornou relatívnou cenou a z novopridaného riadku  tabuľky, následným prepivotovaním dosiahneme duálne prípustnú úlohu.
• Dvojfázová duálno - primárna úloha - nech úloha nie je primárne ani duálne prípustná t.j., ani \(\overline{b}\geq 0\) a ani \(-\overline{c}\geq0\). Zmeníme účelovú funkciu \(c\to c^{'}\) tak, aby \(-\overline{c^{'}}\geq0\) (napr. \(\overline{c^{'}}=0\)) a riešime úlohu duálnym algoritmom. V prípade, ak skončí neprípustne, tak aj pôvodná úloha je neprípustná. Ak skončí optimálne, tak v druhej fáze zavedieme pôvodnú účelovú funkciu a riešime ju primárnym simplexovým algoritmom.