dnes je 2.10.2022

Input:

Dvoufázová simplexová metoda

11.1.2008, , Zdroj: Verlag Dashöfer

17.4.6
Dvoufázová simplexová metoda

Doc. Ing. Alois Fiala, CSc.

Zabývejme se nyní případem, kdy úloha LP není v kanonickém tvaru. Pak musíme vytvořit pomocnou úlohu následujícím způsobem. Do původní úlohy zavedeme nezáporné pomocné (umělé) proměnné tak, abychom získali kanonický tvar, a původní účelovou funkci nahradíme pomocnou účelovou funkcí, která je součtem pomocných proměnných. V prvé fázi simplexové metody pak simplexovým algoritmem hledáme bazické řešení, které minimalizuje pomocnou účelovou funkci. Pokud jsou v tomto řešení všechny pomocné proměnné nulové, použijeme hodnoty ostatních proměnných jako výchozí pro druhou fázi simplexové metody, v níž pomocí simplexového algoritmu hledáme bazické řešení, které optimalizuje původní účelovou funkci. Jestliže se při minimalizaci pomocné účelové funkce nepodařilo anulovat všechny pomocné proměnné, pak to znamená, že původní úloha nemá žádné přípustné řešení.

Pomocná úloha má následující tvar:

minimalizovat

g(xP) = eTxP

za podmínek

Ax + EP xP = b
x ≥ 0, xP ≥ 0

kde

EP je matice typu (m, k) tvořená chybějícími jednotkovými sloupci,

e = (1, 1, . , 1)T je vektor dimenze k,

xP = (xn+1, xn+2, ... , xn+k)T je vektor pomocných proměnných.

Nechť je bazické optimální řešení pomocné úlohy složeno z vektorů xo a xop. Mohou nastat následující dvě situace:

  1. Je-li g(xop) = 0 (tj. jestliže jsou všechny pomocné proměnné rovny nule), pak je vektor xo výchozí přípustné bazické řešení původní úlohy.

  2. Je-li g(xop) ≠ 0, pak původní úloha nemá žádné přípustné řešení. Poznamenejme, že v takovém případě musí být hodnota pomocné účelové funkce kladná, protože tato funkce je součtem nezáporných pomocných proměnných. Pokud by tedy tato hodnota vyšla záporná, znamenalo by to, že při výpočtu došlo k nějaké chybě.

Příklad 1

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

         
z = 3 x1 + 2 x2 max
x1 + x2 4
2 x1 x2 = 5
x1 + 3 x2 27
x1, x2 0

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

                                     
z = 3 x1 + 2 x2 max
x1 +   x2 x3 = 4
    2 x1 x2   = 5
      x1 + 3 x2+ x4 =   27
  x1, x2, x3, x4 0

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 x5 a k levé straně druhé rovnice přičteme nezápornou pomocnou proměnnou x6 . 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é x5, x6, x4 . Abychom našli takové řešení, ve kterém jsou pomocné proměnné x5 a x6 nulové, musíme řešit následující pomocnou úlohu (pomocná účelová funkce z’ je součtem pomocných proměnných):

                                                                     
z’ = x5 + x6 min
x1 + x2 x3+ x5 =  4
2 x1   x2+ x6 = 5
    x1 + 3 x2+ x4 = 27
x1, x2, ..., x6 0

Účelovou funkci z’ budeme považovat za další rovnici a proměnné x5 a x6 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:

                                                                       
  x1 +   x2 x3+ x5=  4
2 x1   x2+ x6 =  5
  x1 + 3 x2+ x4= 27
z 3 x1 2 x2   =  0
z’ = x5 x6 =  0

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

z’ + 3 x1 – x3 = 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.

 
1. x1 x2 x3 x4 x5 x6
x5 1 1 –1 0 1 0   4
x6 2 –1 0 0 0 1   5
x4 1 3 0 1 0 0  27
z –3 –2 0 0 0 0   0
z’ 3 0 –1 0 0 0  9

Kritérium optimality pro z’ je porušeno ve sloupci x1 (z’ se minimalizuje), a sloupec x1 tedy bude klíčový. Nejmenší hodnota podílu bi /ai1 pro ai1 > 0 nastává v řádku x6, který tedy bude klíčovým řádkem. Provedeme simplexovou transformaci: od řádku x5 odečteme jednu polovinu klíčového řádku, řádek x6 podělíme dvěma, od řádku x4 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.

 
2. x1 x2 x3 x4 x5 x6
x5 0 3/2 –1 0 1 –1/2 3/2
x1 1 –1/2 0 0 0 1/2 5/2
x4 0 7/2 0 1 0 –1/2 49/2
z 0 –7/2 0 0 0 3/2 15/2
z’ 0 3/2 –1 0 0 –3/2 3/2

V této tabulce vidíme, že kritérium optimality pro z’ je porušeno ve sloupci x2 a tento sloupec tedy bude klíčový. Klíčovým řádkem bude řádek x5, protože pro tento řádek je nejmenší hodnota podílu bi /ai2 pro ai2 > 0. Provedeme simplexovou transformaci: řádek x5 vynásobíme 2/3, k řádku x1 přičteme jednu třetinu klíčového řádku, od řádku x4 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.

 
3. x1 x2 x3 x4 x5 x6
x2 0 1 –2/3 0 2/3 –1/3  1
x1 1 0 –1/3 0 1/3 1/3  3
x4 0 0 7/3 1 –7/3 2/3 21
z 0 0 –7/3 0 7/3 1/3 11
z’ 0 0 0 0 –1 –1  0

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.

 
4. x1 x2 x3 x4
x2 0 1 –2/3 0  1
x1 1 0 –1/3 0  3
x4 0 0 7/3 1 21
z 0 0 –7/3 0 11

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

 
5. x1 x2 x3 x4
x2 0 1 0 2/7  7
x1 1 0 0 1/7  6
Nahrávám...
Nahrávám...