Zobrazení zdroje stránky Dvoufázový simplexový algoritmus

'''Dvoufázový simplexový algoritmus''', neboli také dvoufázová simplexová metoda, je úprava [[Simplexový algoritmus|simplexového algoritmu]], který dokáže vyřešit i takové úlohy [[Lineární programování|lineárního programování]], které mají v soustavě omezujících podmínek [[rovnice]] nebo [[nerovnice]] typu "<math>\ge</math>".

== 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 [[matice|matici]] [[koeficient]]ů proměnných modelu.

Nerovnice typu "<math>\le</math>" dorovnáme na rovnice stejným způsobem jako u simplexové metody.


<math>a_{ij}*x_{ij} \le b_i</math> → <math>a_{ij}*x_{ij} + x_{n+1} = b_i\,\!</math>


kde <math>x_{n+1}</math> 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 "<math>\ge</math>" dorovnáme na rovnice také pomocí přídatné proměnné (odečteme ji). Zavedeme však navíc tzv. pomocnou proměnnou <math>y_i</math>, která zajistí podmínku existence jednotkového [[vektor]]u, díky které můžeme na problém použít simplexovou metodu.


<math>a_{ij}*x_{ij} \ge b_i</math> → <math>a_{ij}*x_{ij} - x_{n+1} + y_k = b_i\,\!</math>


=== První fáze výpočtu dvoufázovou simplexovou metodou ===
V první fázi sestavíme minimalizační tzv. ''pomocnou účelovou'' funkci ve tvaru:

:<math>z^{pom} = \sum_k y_k </math>

Pomocné proměnné vyjádříme z nerovnic omezujících podmínek typu "<math>\ge</math>" 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í [[Gaussova eliminační metoda|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:

{| border="1" cellpadding="5" cellspacing="0"
| || Strukturní koeficienty || Koeficienty přídatných proměnných ||Koeficienty pomocných proměnných ||Pravé strany omezení 
|-
| <math>z\,\!</math> || <math>-c^T\,\!</math> || <math>0\,\!</math> || <math>0\,\!</math> || <math>0 \,\!</math>
|-
| <math>z^{pom}\,\!</math>
| <math>d_1^T \,\!</math>
| <math>d_2^T \,\!</math>
| <math>d_3^T \,\!</math>
| <math>H \,\!</math>
|}

kde:

* <math>H \,\!</math> je hodnota pomocné účelové funkce
* <math>d_1^T\,\!</math>, <math>d_2^T\,\!</math> a <math>d_3^T\,\!</math> 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 ==
# 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}}

[[Kategorie:Optimalizace (matematika)]]
[[Kategorie:Lineární programování]]