6 Simplexová metoda: Principy
V této přednášce si osvětlíme základy tzv. simplexové metody pro řešení úloh lineární optima-
lizace. Tyto základy zahrnují přípravu kanonického tvaru úlohy, definici a vysvětlení bázických
řešení a ukázání geometrických principů, které stojí za touto metodou.
Zjednodušeně řečeno, simplexová metoda přechází po hranách polyedru všech přípustných
řešení mezi jeho vrcholy (bázickými řešeními), až najde vrchol optimálního řešení.
Stručný přehled lekce
ˇ Kanonický tvar úlohy LP.
ˇ Bázická řešení úlohy LP a jejich vztah k vrcholům.
ˇ Geometrický princip simplexové metody ­ postup mezi vrcholy poly-
edru.
ˇ Simplexová tabulka a její interpretace.
Petr Hliněný, FI MU 1 IA102 "OU": Simplexová metoda
6.1 Kanonický tvar úlohy
Před použitím simplexové metody musíme nejprve vhodně upravit tvar naší úlohy LP.
Stručně řečeno, požadujeme tvar, kdy všechny proměnné jsou nezáporné a všechna
další omezení jsou vyjádřena jako rovnosti. (Jak uvidíme, není to na újmu obecnosti.)
Definice: Úloha LP je v kanonickém tvaru, pokud je vyjádřena jako
max c  x pro
A  x = b,
x  0 ,
kde matice A má plnou řádkovou hodnost.
Petr Hliněný, FI MU 2 IA102 "OU": Simplexová metoda
Lema 6.1. Každou úlohu LP lze převést do kanonického tvaru.
Důkaz: Podle Věty 3.5 vyjádříme danou úlohu v základním tvaru
max c
x
pro A
 x
 b, x
 0 .
Ke každé (i-té) nerovnosti v A
 x  b přidáme tzv. doplňkovou proměnnou x
i  0
následovně
a
i,1  x
1 + . . . + a
i,n  x
n  bi  a
i,1  x
1 + . . . + a
i,n  x
n + x
i = bi
Formálně zapsáno (s nulovou cenou doplňkových proměnných v účelovém vektoru)
A = (A
, I) , b = b
,
x = (x
, x
) , c = (c
, 0, . . . , 0)
a nový tvar úlohy zní
max c  x pro
A  x = b, x  0 ,
jak bylo našim cílem. Jelikož doplňkové proměnné x
jsou nezáporné, je snadné vidět
jednoznačnou korespondenci mezi řešeními kanonické a základní úlohy. 2
Petr Hliněný, FI MU 3 IA102 "OU": Simplexová metoda
6.2 Vrcholy, báze a bázická řešení
Důležitost vrcholů při řešení úloh LP je ukázána následujícím tvrzením. (Vzpomeňme
si, že polyedr má jen konečně mnoho vrcholů, viz Věta 4.12.)
Věta 6.2. Nechť daná úloha LP má optimální řešení a všechny její proměnné jsou
nezáporné. Pak se toto optimální řešení nabývá také v některém krajním bodě (vrcholu)
polyedru všech jejích přípustných řešení.
Důkaz: Nechť množinou přípustných řešení je polyedr P, účelovou funkcí je c  x a
optimem je co v bodě xo
. Označme Q = P  {x : c  x = co}. Q je podle předpokladu
optimality co stěnou P. Pokud |Q| = 1, jedná se o požadovaný vrchol. Jinak definujeme
poloprostor H+
= {x : (1, . . . , 1)  x  1 + (1, . . . , 1)  xo
}. Zřejmě je Q
= Q  H+
omezený polyedr, a proto podle Lematu 4.13 má Q
nějaký vrchol yo
nenáležející facetě
určené H+
. Potom yo
je vrcholem Q i vrcholem P. 2
Ve skutečnosti místo vrcholů budeme při řešení úlohy LP mluvit o tzv. bázických řeše-
ních, která budou hrát klíčovou roli v popisu simplexové metody.
Petr Hliněný, FI MU 4 IA102 "OU": Simplexová metoda
Definice: Bázickým řešením kanonické úlohy A  x = b, x  0 rozumíme vektor xo
splňující A  xo
= b a mající  m nenulových složek (m je počet rovností ­ řádků A),
kde nenulové složky xo
odpovídají nezávislým sloupcům A (tj. regulární podmatici).
Všimněme si dobře, že definice bázického řešení nevyžaduje nezápornost složek vektoru,
proto ne každé bázické řešení je zároveň přípustné.
Z elementární lineární algebry snadno plyne:
Fakt: Každé čtvercové regulární podmatici A1 v A jednoznačně odpovídá jedno bázické
řešení, jehož složky odpovídající sloupcům A1 jsou určeny vztahem A-1
1  b.
Značení: Mějme úlohu Ax = b, x  0, kde matice A má m řádků a n sloupců. Každé
bázické řešení xo
je určeno výběrem některé regulární čtvercové podmatice A1 v A,
neboli výběrem m nezávislých sloupců A.
Sloupce A1 budeme nazývat bází řešení xo
.
Zároveň složky vektoru x odpovídající sloupcům A1 budeme nazývat bázickými pro-
měnnými a ty zbylé nebázickými proměnnými.
Poznámka: Pokud bázické řešení xo
má právě m nenulových složek, pak je báze pro xo
určena
jednoznačně. Avšak pokud xo
má méně než m nenulových složek, pak všechny různé regulární
podmatice pokrývající nenulové složky xo
jsou zřejmě bázemi pro totéž řešení xo
. Takové
bázické řešení se nazývá degenerované.
Petr Hliněný, FI MU 5 IA102 "OU": Simplexová metoda
Lema 6.3. Přípustná bázická řešení úlohy LP jednoznačně odpovídají krajním bodům
(vrcholům) polyedru všech přípustných řešení.
Důkaz: Mějme vrchol v polyedru. Ten je přípustným řešením Av = b, v  0 z definice.
Předpokládejme pro spor, že v není bázické, tedy že v má více než m kladných složek,
nazvěme v1
tyto kladné složky v a vyberme podmatici A1 složenou ze sloupců A
odpovídajících v1
. Pak soustava A1  v1
= b má více proměnných než rovnic, a proto
množina jejích řešení obsahuje aspoň přímku p procházející v1
 v. Jelikož v1
> 0,
v dostatečně blízkém okolí v1
na p jsou řešení soustavy také kladná, tedy přípustná v
naší úloze, a přitom v1
, potažmo v, je jejich konvexní kombinací. To je spor, v není
krajním bodem.
Naopak nechť v je přípustným bázickým řešením a A1 je odpovídající báze, tj. re-
gulární podmatice A. Pak v leží v polyedru. Pokud by v bylo v konvexní kombinací,
zjednodušeně v = 1
2 (u + w), pak bychom si označili v1
, u1
, w1
příslušné podvektory
odpovídající sloupcům báze A1. Vzhledem k jednoznačnosti řešení regulární soustavy
rovnic A1 v1
= b; pokud by u1
, w1
byly také přípustná řešení, některá nebázická složka
u i w by musela být nenulová. Ale jelikož i v této nebázické složce (kde v je nulové)
platí v = 1
2 (u + w), buď v u nebo v w by musela pak být tato složka záporná, spor s
přípustností. Takže v skutečně nelze získat jako konvexní kombinaci přípustných řešení.
Z definice je proto v vrcholem polyedru. 2
Značení: Báze A1 a A2 bázických řešení jsou sousední pokud se liší právě v jednom
sloupci.
Petr Hliněný, FI MU 6 IA102 "OU": Simplexová metoda
6.3 Geometrický princip metody
Algoritmus 6.4. Princip simplexové metody
V hrubých rysech algoritmus simplexové metody běží podle následujícího schématu.
(Upozorňujeme, že je v tomto zjednodušeném znění zanedbán problém získání výcho-
zího přípustného řešení i problém prevence zacyklení v degenerovaných řešeních.)
1. Začneme v některém (výchozím) přípustném bazickém řešení x0
s bází A0 v A.
Jinými slovy, jsme ve vrcholu x0
polyedru přípustných řešení.
ˇ Jak x0
a A0 najdeme? V A vybereme jednotkovou podmatici I = A0 velikosti
m × m, případně ji "vyrobíme" přidáním umělých proměnných.
ˇ Pozor na přípustnost výchozího řešení x0
 0.
2. Krok i: Pokud žádný sousední vrchol k xi
nemá lepší hodnotu účelové funkce, je
xi
optimální řešení.
ˇ Pozor, musíme se dívat skutečně na sousední vrcholy, ne jen sousední báze!
ˇ Tuto situaci poznáme podle nekladných redukovaných cen všech nebázických pro-
měnných, Tvrzení 6.8.
3. Pokud z vrcholu xi
vede neomezená hrana polyedru ve směru zlepšující se účelové
funkce, optimální řešení neexistuje z důvodu neomezenosti.
ˇ Tuto situaci poznáme podle nekladných všech koeficientů některé nebázické pro-
měnné s kladnou redukovanou cenou, Tvrzení 6.9.
Petr Hliněný, FI MU 7 IA102 "OU": Simplexová metoda
4. K bázi Ai najdeme sousední bázi Ai+1, která zlepšuje naši účelovou funkci.
Pokud vyloučíme degenerovanost, přejdeme tak do sousedního vrcholu xi+1
s
lepší účelovou hodnotou.
ˇ Zlepšující sousední bázi najdeme takto: Pomocí sloupcového pravidla najdeme
nebázický sloupec matice A, který má do báze vstoupit (třeba ten s největší
kladnou redukovanou cenou). Pomocí řádkového pravidla pak najdeme bázický
sloupec matice Ai, který musí bázi opustit.
ˇ V degenerovaném případě může nastat xi+1
= xi
. Pak hrozí nebezpečí zacyklení
metody, čemuž zabráníme (třeba) použitím dodatečného lexikografického pravidla.
5. Jdeme zpět na bod 2 v iteraci i + 1.
Lema 6.5. Nechť daná úloha LP má přípustné řešení. Pokud vhodnými pravidly vý-
běru sousední báze zabráníme zacyklení v degenerovaném bázickém řešení, tak Algo-
ritmus 6.4 simplexové metody nalezne v konečném počtu kroků optimální řešení úlohy,
nebo případně potvrdí neexistenci řešení z důvodu neomezenosti.
Petr Hliněný, FI MU 8 IA102 "OU": Simplexová metoda
Poznámka: Třebaže nám předchozí tvrzení zaručuje skončení simplexové metody po konečném
počtu kroků, horní odhad tohoto počtu kroků nevychází příliš příznivě ­ počet kroků je nejvýše
rovný počtu všech čtvercových podmatic (bází) dané matice úlohy, což je číslo exponenciální
ve velikosti úlohy.
Bohužel se jedná o dosti hluboký problém, neboť přes velkou snahu se doposud nikomu ne-
podařilo dokázat polynomiální (tedy efektivní) horní odhad počtu kroků simplexové metody.
Dokonce pro běžná řádková a sloupcová pravidla jsou známy skutečné příklady exponenciálně
dlouhých výpočtů. Přesto je v praktických případech simplexová metoda velice rychlá a většina
uživatelů se nad jejím možným dlouhým průběhem ani nezamýšlí.
Petr Hliněný, FI MU 9 IA102 "OU": Simplexová metoda
6.4 Simplexová tabulka
Pro pohodlný (počítačově-orientovaný) zápis jak úlohy LP, tak i průběhu simplexové
metody se nejčastěji používá tzv. simplexová tabulka. Úlohu LP v kanonickém tvaru
max c  x :
A  x = b
x  0
si přepíšeme do ekvivaletního redukovaného zápisu
min x0
x0 + c  x = 0 (1)
A  x = b
x  0 .
Zde jsme zavedli novou proměnnou x0 vystupující pouze v novém nultém, tzv. účelovém
řádku podmínek úlohy. Všimněte si, že x0 je vždy jednoznačně určeno hodnotami
ostatních proměnných a udává opačnou hodnotu účelové funkce příslušné k řešení x.
Petr Hliněný, FI MU 10 IA102 "OU": Simplexová metoda
Značení: Redukovaný zápis kanonické úlohy LP se vyjádří simplexovou tabulkou
1 c1 c2 c3 . . . cn -b0
0 a11 a12 a13 . . . a1n b1
0 a21 a22 a23 . . . a2n b2
...
...
...
... . . .
...
...
0 am1 am2 am3 . . . amn bm
zapisující koeficienty soustavy lineárních rovnic
1 c
0 A

x0
x
=
-b0
b
. (2)
Nultý řádek a sloupec tabulky se nazývají účelový řádek a sloupec, přitom účelový
sloupec se do tabulky většinou vůbec nezapisuje. Hodnoty v účelovém řádku (mimo
nultého a posledního sloupce) se nazývají redukované ceny proměnných (složek) x.
Mějme matici C =
1 c
0 A
a v ní regulární čtvercovou podmatici C1 obsahující sloupce
podmatice A1 a navíc nultý sloupec. Pak vztah
x0
xB = C-1
1 
-b0
b
určuje hodnoty
bázických proměnných xB
v příslušném bázickém řešení (odpovídajícím bázi A1) a zároveň
i jeho účelovou hodnotu -x0. Ve spojení s faktem, že standardní řádkové maticové úpravy
nemění množinu řešení soustavy (úlohy), dostáváme klíčové pozorování, že řádkovými opera-
cemi na simplexové tabulce můžeme postupně vyjadřovat jednotlivá bázická řešení úlohy LP
včetně jejich účelových hodnot.
Petr Hliněný, FI MU 11 IA102 "OU": Simplexová metoda
Definice: Simplexová tabulka T je v jednotkovém tvaru, pokud v ní je vyznačena jed-
notková podmatice Im+1 obsahující nultý účelový sloupec a vybrané sloupce matice A.
Zároveň je simplexová tabulka v jednotkovém tvaru přípustná, pokud poslední sloupec
má mimo nultého řádku nezáporné hodnoty.
Tvrzení 6.6. Mějme pro danou úlohu LP zápis simplexovou tabulkou
T =
1 c 
| -b
0
0 A
| b
v jednotkovém tvaru. Pak složky vektoru b
vyjadřují hodnoty bázických proměnných
xB
příslušného bázického řešení (odpovídajícího vyznačené jednotkové podmatici v A
)
a b
0 je účelovou hodnotou tohoto řešení.
Lema 6.7. Mějme pro danou úlohu LP zápis simplexovou tabulkou T v jednotkovém
tvaru. Rozdělme si vektor x proměnných na bázické složky xB
a nebázické xN
a po-
dobně pro A
a c
. Pak pro zvolené nebázické hodnoty xN
 0 jsou odpovídající bázické
proměnné určeny vztahy
xB
= b
- AN
 xN
(3)
a účelová hodnota řešení je
b
0 + c N
 xN
. (4)
Petr Hliněný, FI MU 12 IA102 "OU": Simplexová metoda
Z pohledu xN
 0 na vztah (4) ihned plyne:
Tvrzení 6.8. Pokud pro danou úlohu LP má zápis simplexovou tabulkou v přípustném
jednotkovém tvaru všechny redukované ceny nekladné c
 0, pak vyjádřené bázické
řešení xB
= b
, xN
= 0 je optimálním řešením úlohy.
Dále si všimněme, že pokud některá nebázická proměnná xs ve vztahu (3) má všechny
koeficienty nekladné, pak pro libovolně velkou hodnotu xs   se zachová přípustnost
řešení xB
 0. Z toho již s použitím (4) plyne:
Tvrzení 6.9. Mějme pro danou úlohu LP zápis simplexovou tabulkou v přípustném
jednotkovém tvaru. Pokud v některém sloupci s tabulky je redukovaná cena kladná
c
s > 0 a zároveň zbytek sloupce je nekladný, tj. a
js  0, j = 1, . . . , m, pak optimální
řešení úlohy neexistuje z důvodu neomezenosti.
Pro dobré pochopení simplexové tabulky je třeba si ujasnit praktickou roli redukovaných cen
proměnných v účelovém řádku. Za prvé, redukované ceny bázických proměnných jsou vždy
nulové. Pro každou nebázickou proměnnou, dle vztahu (4), její redukovaná cena vyjadřuje
změnu výsledné účelové hodnoty při změně hodnoty této proměnné o 1. (Tato změna je
celková, již bere do úvahy indukované změny (3) bázických proměnných!)
Petr Hliněný, FI MU 13 IA102 "OU": Simplexová metoda
Příklad 6.10. Hranolky, slané a paprikové lupínky.
Firma chce vyrobit hranolky, slané lupínky a paprikové lupínky. K dispozici má přitom 1000 kg
brambor a může nakupovat neomezeně sůl za 6 Kč/kg, olej za 30 Kč/kg a paprikové koření
za 200 Kč/kg. Bohužel má firma celkem na nákup surovin pouze 5000 Kč. Spotřeby surovin
a prodejní ceny na 10 kg jsou následující:
Produkt (10kg) Brambory Olej Paprika Sůl Prodejní cena
hranolky 15 2 0 0.5 450
slané lupínky 20 4 0 1 650
paprikové lupínky 20 3 0.2 0.5 800
Sestavte počáteční simplexovou tabulku úlohy.
Řešení: Ze zadaných hodnot se snadno spočítá zisk a cena surovin na 10 kg produktu:
Produkt (10kg) Zisk Cena surovin
hranolky 387 63
slané lupínky 524 126
paprikové lupínky 667 133
Za proměnné zvolíme vyrobená množství produktů: 10x1 hranolků, 10x2 slaných lupínků a
10x3 paprikových lupínků. Základní tvar úlohy
max 387x1 + 524x2 + 667x3 :
15x1 + 20x2 + 20x3  1000
63x1 + 126x2 + 133x3  5000
x1, x2, x3  0
Petr Hliněný, FI MU 14 IA102 "OU": Simplexová metoda
převedeme na kanonický tvar přidáním dvou doplňkových proměnných
min x0
x0 + 387x1 + 524x2 + 667x3 = 0
15x1 + 20x2 + 20x3 +x4 = 1000
63x1 + 126x2 + 133x3 +x5 = 5000
x1, x2, x3, x4, x5  0
a z toho již vypíšeme výchozí simplexovou tabulku (bez nultého řádku)
387 524 667 0 0 0
15 20 20 1 0 1000
63 126 133 0 1 5000
.
Umíte najít řešení této úlohy? 2
Petr Hliněný, FI MU 15 IA102 "OU": Simplexová metoda