Dvoufázová simplexová metoda

Řešme následující úlohu simplexovou metodou:

Úlohu převedeme na standardní tvar zavedením doplňkových proměnných x₃ a x₄ (proměnná x₃ se odečítá, protože v první nerovnici je operátor ≥):

Tato úloha není v kanonickém tvaru, protože matice soustavy rovnic obsahuje pouze jeden jednotkový sloupec. Chybějící jednotkové sloupce do soustavy uměle zavedeme tak, že k levé straně první rovnice přičteme nezápornou pomocnou proměnnou x₅ a k levé straně druhé rovnice přičteme nezápornou pomocnou proměnnou x₆ . Tak dostaneme soustavu rovnic, která už je v kanonickém tvaru (poznamenejme, že sloupce jednotkové matice nemusejí být uspořádané), a bazickými proměnnými jsou proměnné x₅, x₆, x₄ . Abychom našli takové řešení, ve kterém jsou pomocné proměnné x₅ a x₆ nulové, musíme řešit následující pomocnou úlohu (pomocná účelová funkce z’ je součtem pomocných proměnných):

Účelovou funkci z’ budeme považovat za další rovnici a proměnné x₅ a x₆ převedeme na levou stranu. Pro pozdější použití přidáme do soustavy ještě rovnici vytvořenou stejným způsobem z funkce z. Dostaneme následující soustavu rovnic:

V této podobě je ale rovnice se z’ nepoužitelná pro testování kritéria optimality, protože obsahuje bazické proměnné x₅ a x₆ . To můžeme napravit tak, že k této rovnici přičteme první dvě rovnice. Tím získáme rovnici

z’ + 3 x₁ – x₃ = 9

Nyní můžeme sestavit výchozí simplexovou tabulku a zahájit první fázi simplexové metody, v níž se minimalizuje pomocná účelová funkce. Postup výpočtu je zachycen v následujících tabulkách 1 - 3.

Kritérium optimality pro z’ je porušeno ve sloupci x₁ (z’ se minimalizuje), a sloupec x₁ tedy bude klíčový. Nejmenší hodnota podílu b_i /a_i1 pro a_i1 > 0 nastává v řádku x₆, který tedy bude klíčovým řádkem. Provedeme simplexovou transformaci: od řádku x₅ odečteme jednu polovinu klíčového řádku, řádek x₆ podělíme dvěma, od řádku x₄ odečteme jednu polovinu klíčového řádku, k řádku z přičteme klíčový řádek násobený 3/2 a od řádku z’ odečteme klíčový řádek násobený 3/2. Tak dostaneme tabulku 2.

V této tabulce vidíme, že kritérium optimality pro z’ je porušeno ve sloupci x₂ a tento sloupec tedy bude klíčový. Klíčovým řádkem bude řádek x₅, protože pro tento řádek je nejmenší hodnota podílu b_i /a_i2 pro a_i2 > 0. Provedeme simplexovou transformaci: řádek x₅ vynásobíme 2/3, k řádku x₁ přičteme jednu třetinu klíčového řádku, od řádku x₄ odečteme klíčový řádek násobený 7/3, k řádku z přičteme klíčový řádek násobený 7/3 a od řádku z’ odečteme klíčový řádek. Tak získáme tabulku 3.

Po provedení dvou simplexových transformací je pro pomocnou úlohu splněno kritérium optimality, přičemž optimální hodnota pomocné účelové funkce je nulová. Z poslední simplexové tabulky odstraníme sloupce pomocných proměnných a řádek pomocné účelové funkce (tak obdržíme tabulku 4) a můžeme přejít ke druhé fázi simplexové metody.

Kritérium optimality je porušeno ve sloupci x₃, a tento sloupec tedy bude klíčový. Klíčovým řádkem bude řádek x₄, protože pouze v tomto řádku se nachází kladná hodnota a_i3. Provedeme simplexovou transformaci: k řádku x₂ přičteme klíčový řádek vynásobený 2/7, k řádku x₁ přičteme klíčový řádek vynásobený 1/7, řádek x₄ vynásobíme 3/7 a k řádku z přičteme klíčový řádek. Tak získáme tabulku 5.