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 "$\geq$".

Průběh algoritmu dvoufázové simplexové metody

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 "$\leq$" dorovnáme na rovnice stejným způsobem jako u simplexové metody.

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

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

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

První fáze výpočtu dvoufázovou simplexovou metodou

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

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

Pomocné proměnné vyjádříme z nerovnic omezujících podmínek typu "$\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í
$z\,\!$	$-c^{T}\,\!$	$0\,\!$	$0\,\!$	$0\,\!$
$z^{pom}\,\!$	$d_{1}^{T}\,\!$	$d_{2}^{T}\,\!$	$d_{3}^{T}\,\!$	$H\,\!$

kde:

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

Druhá fáze výpočtu dvoufázové simplexové metody

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.

Literatura

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