Dvoufázový simplexový algoritmus

Dvoufázový simplexový algoritmus, neboli také dvoufázová simplexová metoda, je úprava simplexového algoritmu, který dokáže vyřešit i takové úlohy lineárního programování, které mají v soustavě omezujících podmínek rovnice nebo nerovnice typu "${\displaystyle \geq }$".

Průběh algoritmu dvoufázové simplexové metody se liší v první fázi řešení úlohy - v získání výchozího řešení. Proto, abychom mohli použít simplexovou metodu, potřebujeme však všechna omezení vyjádřit ve formě rovnic a navíc mít jednotkovou submatici v matici koeficientů proměnných modelu.

Nerovnice typu "${\displaystyle \leq }$" dorovnáme na rovnice stejným způsobem jako u simplexové metody.

${\displaystyle a_{ij}*x_{ij}\leq b_{i}}$ → ${\displaystyle a_{ij}*x_{ij}+x_{n+1}=b_{i}\,\!}$

kde ${\displaystyle x_{n+1}}$ představuje tzv. přídatnou proměnnou. Ta se interpretuje jako nevyužitá kapacita - je rozdílem mezi levou a pravou stranou nerovnice.

Nerovnice typu "${\displaystyle \geq }$" dorovnáme na rovnice také pomocí přídatné proměnné (odečteme ji). Zavedeme však navíc tzv. pomocnou proměnnou ${\displaystyle y_{i}}$, která zajistí podmínku existence jednotkového vektoru, díky které můžeme na problém použít simplexovou metodu.

${\displaystyle a_{ij}*x_{ij}\geq b_{i}}$ → ${\displaystyle a_{ij}*x_{ij}-x_{n+1}+y_{k}=b_{i}\,\!}$

V první fázi sestavíme minimalizační tzv. pomocnou účelovou funkci ve tvaru:

${\displaystyle z^{pom}=\sum _{k}y_{k}}$

Pomocné proměnné vyjádříme z nerovnic omezujících podmínek typu "${\displaystyle \geq }$" nebo "=". Pomocná účelová funkce v typickém případě nabude nějaké hodnoty. V první fázi výpočtu se snažíme vynulovat pomocnou účelovou funkci pomocí Gaussovy eliminace. Pokud se nám to nepodaří, pak úloha LP nemá přípustné řešení. Pokud se nám povede pomocnou účelovou funkci vynulovat, pokračujeme druhou fází výpočtu.

Výpočet je výhodné provádět v upravené simplexové tabulce:

	Strukturní koeficienty	Koeficienty přídatných proměnných	Koeficienty pomocných proměnných	Pravé strany omezení
${\displaystyle z\,\!}$	${\displaystyle -c^{T}\,\!}$	${\displaystyle 0\,\!}$	${\displaystyle 0\,\!}$	${\displaystyle 0\,\!}$
${\displaystyle z^{pom}\,\!}$	${\displaystyle d_{1}^{T}\,\!}$	${\displaystyle d_{2}^{T}\,\!}$	${\displaystyle d_{3}^{T}\,\!}$	${\displaystyle H\,\!}$

kde:

• ${\displaystyle H\,\!}$ je hodnota pomocné účelové funkce
• ${\displaystyle d_{1}^{T}\,\!}$, ${\displaystyle d_{2}^{T}\,\!}$ a ${\displaystyle d_{3}^{T}\,\!}$ jsou vektory koeficientů proměnných modelu v pomocné účelové funkci

Tato fáze se ničím neliší od klasické simplexové metody. Při započetí výpočtu doporučují např. Lagová a Jablonský v [1] vypustit ze simplexové tabulky pomocné proměnné a řádek pomocné účelové funkce a pokračovat bez nich.

1. Lagová M., Jablonský J., Lineární modely, Praha, 2004, nakladatelství Oeconomica, ISBN 80-245-0816-8
2. Jablonský J., Programy pro matematické modelování, Praha, 2007, nakladatelství Oeconomica, ISBN 978-80-245-1178-8
3. Jablonský J., Operační výzkum - kvantitativní metody pro ekonomické rozhodování, Praha, 2002, Professional Publishing, ISBN 80-86419-42-8