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 "".
Průběh algoritmu dvoufázové simplexové metody
[editovat | editovat zdroj]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 "" dorovnáme na rovnice stejným způsobem jako u simplexové metody.
→
kde 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 "" dorovnáme na rovnice také pomocí přídatné proměnné (odečteme ji). Zavedeme však navíc tzv. pomocnou proměnnou , která zajistí podmínku existence jednotkového vektoru, díky které můžeme na problém použít simplexovou metodu.
→
První fáze výpočtu dvoufázovou simplexovou metodou
[editovat | editovat zdroj]V první fázi sestavíme minimalizační tzv. pomocnou účelovou funkci ve tvaru:
Pomocné proměnné vyjádříme z nerovnic omezujících podmínek typu "" 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í | |
kde:
- je hodnota pomocné účelové funkce
- , a jsou vektory koeficientů proměnných modelu v pomocné účelové funkci
Druhá fáze výpočtu dvoufázové simplexové metody
[editovat | editovat zdroj]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
[editovat | editovat zdroj]- Lagová M., Jablonský J., Lineární modely, Praha, 2004, nakladatelství Oeconomica, ISBN 80-245-0816-8
- Jablonský J., Programy pro matematické modelování, Praha, 2007, nakladatelství Oeconomica, ISBN 978-80-245-1178-8
- Jablonský J., Operační výzkum - kvantitativní metody pro ekonomické rozhodování, Praha, 2002, Professional Publishing, ISBN 80-86419-42-8