Lineární programování
- simplexová metoda - teorie
DEF:
Množina S  Rn je konvexní, pokud "x1, x2  S:
l  x1 + (1 - l)  x2  S pro každé l  [0, 1].
DEF:
Bod l  x1 + (1 - l)  x2 pro l  [0, 1] se nazývá
konvexní kombinací x1 a x2.
Lineární programování
- simplexová metoda - teorie II
DEF:
Konvexní obal množiny S je nejmenší konvexní
množina obsahující S. Označuje se conv(S).
DEF:
Množina P  Rn je konvexní polyedr, pokud P je
konvexním obalem konečné množiny.
Lineární programování
- simplexová metoda - teorie III
DEF:
Simplex je konvexní polyedr P = conv {v0, , vm}  Rn,
kde vm – v0, , v1 – v0 jsou lineárně nezávislé. Pokud
tedy m = n, jde o konvexní obal n + 1 bodů s
nenulovým objemem v Rn.
DEF:
Polyedrická množina je průnikem konečného počtu
poloprostorů (lze je zapsat ve tvaru {x  Rn; aTx  a },
kde a  Rn, a  R).
Je zřejmé, že množina přípustných řešení každé úlohy
lineárního programování je polyedrická.
Lineární programování
- simplexová metoda - teorie IV
DEF: Krajní bod konvexní množiny S  Rn je prvek S,
který není netriviální konvexní kombinací dvou
různých bodů z S. Neexistuje y1, y2  S, y1  y2, l 
(0, 1): x = l  y1 + (1 - l)  y2.
Lineární programování
- simplexová metoda - teorie IV
DEF: Směr (v bodě x  S) v uzavřené konvexní
množině S  Rn je takový nenulový vektor d  Rn,
pro který $ a > 0: x + a  d  S.
Lineární programování
- simplexová metoda - teorie V
DEF:
Krajní směr je směr, který není kladnou lineární
kombinací dvou různých směrů.
Lineární programování
- simplexová metoda - teorie VI
Věta:
Kladná lineární kombinace směrů je opět směrem:
Je-li a1, a2 > 0:
x + a1  d1  S
 x + a1  d1 + a2  d2  S
 x + b  (a1  d1 + a2  d2)  S pro b  0.
DEF:
Krajní směr je směr, který není kladnou lineární
kombinací dvou různých směrů.
Lineární programování
- charakteristika krajních bodů
Nechť S = { x | Ax = b, x  0}, A  Rm x n a h(A) = m.
x  S je krajní bod S 
 po permutaci sloupců matice A (a odpovídajících složek
vektoru x) lze matici A vyjádřit jako A = (B | N), tak že
platí:
kde B  Rm x m je regulární a B-1.b  0.
x
x
x
B bB
N
=





 =






−1
0
Lineární programování
- vlastnosti krajních bodů
Nechť S = { x | Ax = b, x  0}  
Pak platí:
a) Existuje krajní bod množiny S.
b) Každý krajní bod množiny S má nejvýše m kladných
složek.
c) Množina S má nejvýše krajních bodů.
n
m






Lineární programování
- charakteristika krajních bodů - příklad
Příklad:
max 4x1 + 3x2
x1 + x2  40
2x1 + x2  60
Přepis rovnic na standardní tvar:
x  0
1 1
2 1
1 0
0 1
40
60





 =





.x
( )min − −4 3 0 0 x
Lineární programování
- charakteristika krajních bodů - příklad
Příklad:
max 4x1 + 3x2
x1 + x2  40
2x1 + x2  60
Přepis rovnic na standardní tvar:
x  0
1 1
2 1
1 0
0 1
40
60





 =





.x
( )min − −4 3 0 0 x
Lineární programování
- charakteristika krajních bodů - příklad II
Následující tabulka uvádí přehled bázických
proměnných xB (zbylé proměnné xN označujeme jako
nebázické proměnné), bázickou matici B a
odpovídající bázické řešení x.
Dále je uvedeno, zda je bázické řešení přípustné tj.
splňuje x  0 (zkratka BFS značí basic feasible
solution).
Nakonec uvádíme, kterým bodům grafu přísluší daná
bázická řešení, zda se jedná o krajní body a kterými
omezeními jsou body určeny.
Lineární programování
- charakteristika krajních bodů - příklad III
Tabulka bázických proměnných:
xB B x BFS graf krajní omezení
Lineární programování
- charakteristika krajních bodů - příklad III
Tabulka bázických proměnných:
xB B x BFS graf krajní omezení
x1, x2 1 1
2 1






( )20 20 0 0 ano E ano AEB, CED
x1, x3 1 1
2 0






( )30 0 10 0 ano C ano CED, ACF
x1, x4 1 0
2 1






( )40 0 0 10− ne A ne ABD, ACF
1 1
2 1
1 0
0 1
40
60





 =





.x
Lineární programování
- charakteristika krajních bodů - příklad III
Tabulka bázických proměnných:
xB B x BFS graf krajní omezení
x1, x2 1 1
2 1






( )20 20 0 0 ano E ano AEB, CED
x1, x3 1 1
2 0






( )30 0 10 0 ano C ano CED, ACF
x1, x4 1 0
2 1






( )40 0 0 10− ne A ne ABD, ACF
1 1
2 1
1 0
0 1
40
60





 =





.x
Lineární programování
- charakteristika krajních bodů - příklad III
Tabulka bázických proměnných:
xB B x BFS graf krajní omezení
x1, x2 1 1
2 1






( )20 20 0 0 ano E ano AEB, CED
x1, x3 1 1
2 0






( )30 0 10 0 ano C ano CED, ACF
x1, x4 1 0
2 1






( )40 0 0 10− ne A ne ABD, ACF
1 1
2 1
1 0
0 1
40
60





 =





.x
Lineární programování
- charakteristika krajních bodů - příklad III
Tabulka bázických proměnných:
xB B x BFS graf krajní omezení
x1, x2 1 1
2 1






( )20 20 0 0 ano E ano AEB, CED
x1, x3 1 1
2 0






( )30 0 10 0 ano C ano CED, ACF
x1, x4 1 0
2 1






( )40 0 0 10− ne A ne ABD, ACF
1 1
2 1
1 0
0 1
40
60





 =





.x
Lineární programování
- charakteristika krajních bodů - příklad III
Tabulka bázických proměnných:
xB B x BFS graf krajní omezení
x1, x2 1 1
2 1






( )20 20 0 0 ano E ano AEB, CED
x1, x3 1 1
2 0






( )30 0 10 0 ano C ano CED, ACF
x1, x4 1 0
2 1






( )40 0 0 10− ne A ne ABD, ACF
1 1
2 1
1 0
0 1
40
60





 =





.x
Lineární programování
- charakteristika krajních bodů - příklad III
Tabulka bázických proměnných:
xB B x BFS graf krajní omezení
x1, x2 1 1
2 1






( )20 20 0 0 ano E ano AEB, CED
x1, x3 1 1
2 0






( )30 0 10 0 ano C ano CED, ACF
x1, x4 1 0
2 1






( )40 0 0 10− ne A ne ABD, ACF
1 1
2 1
1 0
0 1
40
60





 =





.x
Lineární programování
- charakteristika krajních bodů - příklad III
Tabulka bázických proměnných:
xB B x BFS graf krajní omezení
x1, x2 1 1
2 1






( )20 20 0 0 ano E ano AEB, CED
x1, x3 1 1
2 0






( )30 0 10 0 ano C ano CED, ACF
x1, x4 1 0
2 1






( )40 0 0 10− ne A ne ABD, ACF
Lineární programování
- charakteristika krajních bodů - příklad III
Tabulka bázických proměnných:
xB B x BFS graf krajní omezení
x1, x2 1 1
2 1






( )20 20 0 0 ano E ano AEB, CED
x1, x3 1 1
2 0






( )30 0 10 0 ano C ano CED, ACF
x1, x4 1 0
2 1






( )40 0 0 10− ne A ne ABD, ACF
Lineární programování
- charakteristika krajních bodů - příklad III
Tabulka bázických proměnných:
xB B x BFS graf krajní omezení
x1, x2 1 1
2 1






( )20 20 0 0 ano E ano AEB, CED
x1, x3 1 1
2 0






( )30 0 10 0 ano C ano CED, ACF
x1, x4 1 0
2 1






( )40 0 0 10− ne A ne ABD, ACF
Lineární programování
- charakteristika krajních bodů - příklad IV
Tabulka bázických proměnných - 2. část:
xB B x BFS graf krajní omezení
x2, x3 1 1
1 0






( )0 60 20 0− ne D ne CED, DBF
x2, x4 1 1
2 0






( )0 40 0 20 ano B ano AEB, DBF
x3, x4 1 0
2 1






( )0 0 40 60 ano F ano DBF, ACF
Lineární programování
- charakteristika krajních bodů - příklad IV
Tabulka bázických proměnných - 2. část:
xB B x BFS graf krajní omezení
x2, x3 1 1
1 0






( )0 60 20 0− ne D ne CED, DBF
x2, x4 1 1
2 0






( )0 40 0 20 ano B ano AEB, DBF
x3, x4 1 0
2 1






( )0 0 40 60 ano F ano DBF, ACF
Lineární programování
- charakteristika krajních směrů
Nechť S = { x | Ax = b, x  0}, A  Rm x n a h(A) = m.
d  Rn je krajní směr v S 
 po permutaci sloupců matice A (a odpovídajících složek
vektoru x) lze matici A vyjádřit jako A = (B | N), tak že
B-1 .aj  0 pro některý sloupec aj matice N a platí:
kde a > 0 a ej = (ej,1, ... ,ej,n-m) a dále ej,j = 1 a ej,i = 0 pro
i  j.
d
B a
e
j
j
=
−





−
a
1
Lineární programování
- vlastnosti krajních směrů
Nechť S = { x | Ax = b, x  0}  
Pak platí:
Množina S má nejvýše krajních směrů.
n
m
n m





 −( )
Lineární programování
- věta o reprezentaci
Věta o reprezentaci:
Nechť S = { x | Ax = b, x  0}  , A  Rm x n a h(A) = m
a nechť x1, ..., xk jsou všechny krajní body S a d1, ..., dl
všechny krajní směry S.
Pak platí x  S 
$li  0, , $mi  0 tak, že:li
i
k
=
=
 1
1
x x di i
i
k
j j
j
l
= +
= =
 l m
1 1
Lineární programování
- základní věta LP
Základní věta lineárního programování:
Mějme úlohu lineárního programování ve standardním
tvaru, h(A) = m, S  . Nechť x1, ..., xk jsou všechny
krajní body S a d1, ..., dl všechny krajní směry S.
Pak existuje min{cTx; x  S} 
cTdj  0 pro "j = 1, ..., l
Jestliže existují optimální řešení, pak existuje mezi nimi
alespoň jeden krajní bod.
Lineární programování
- metody nalezení minima
• Přímá metoda
• Simplexová metoda.
Přímá metoda:
• najdeme všechny krajní body
• spočítáme hodnotu účelové funkce pro tyto body
• má-li úloha optimální řešení, je jím krajní bod s největší
hodnotou účelové funkce
Lineární programování
- přímá metoda
Problém při této metodě spočívá v tom, že počet krajních
bodů s rostoucím počtem proměnných rychle narůstá:
N proměnných => 2N kandidátů na krajní bod
Vyhledat všechny krajní body znamená vybrat z matice A
všechny regulární submatice řádu m a vyřešit pro
každou z nich soustavu:
B.xB= b
Pokud je její řešení nezáporné, získali jsme (po
doplnění nulovými složkami) krajní bod množiny M.
Lineární programování
- přímá metoda 2
Takový postup je numericky schůdný jen pro úlohy malé
dimenze.
Navíc nemáme předem zaručenou existenci optimálního
řešení, takže nalezené nejlepší základní řešení nemusí
být řešením optimálním.
Lineární programování
- simplexová metoda - princip
Prochází krajní body množiny přípustných řešení jistým
racionálním způsobem (například nikdy nepřejde do
bodu s vyšší funkční hodnotou).
Způsob procházení množiny přípustných řešení lze snadno
popsat geometricky:
• Předpokládejme, že máme krajní bod x0 množiny
přípustných řešení M.
• Z tohoto krajního bodu vychází konečné množství hran
množiny M, z nichž každá buď obsahuje buď jediný
další krajní bod množiny M, nebo je neomezená.
Lineární programování
- simplexová metoda - princip II
• Jestliže na některé neomezené hraně existuje bod, pro
který je hodnota účelové funkce nižší než cTx0, nemá
úloha optimální řešení a postup končí.
• V opačném případě hledáme sousední krajní bod, pro
který je hodnota kriteriální funkce nižší než cTx0.
• Nechť je to krajní bod x1. Pak stejný postup, který jsme
dosud aplikovali na bod x0, aplikujeme nyní na bod x1.
• Pokud neexistuje sousední krajní bod s vlasností cTx >
cTx0, je x0 hledaným optimálním řešením.
Lineární programování
- simplexová metoda - princip III
Princip:
x = (xB, xN), xN = 0, xB  Rm, xN  Rm-n
A = (B | N), B  Rm x m, B  Rm x (m-n), B je regulární
Krok metody = výměna jedné nebázové proměnné (z xN)
za bázovou proměnnou (z xB) tak, aby cTx kleslo.
Výměna znamená, že tato dosud bázová proměnná pak
bude mít hodnotu 0, a ta dosud nebázová nějakou
kladnou hodnotu => budeme opět v krajním bodě.
Lineární programování
- simplexová metoda - princip IV
• Jak vybrat nebázovou proměnnou, kterou
přesuneme do báze?
Pomocí redukovaného cenového vektoru :-).
Odvození vztahu pro redukovaný cenový vektor:
=> Vyjádříme cTx za předpokladu Ax = b pouze
pomocí proměnné xN.
Lineární programování
- simplexová metoda - princip V
=> Vyjádříme cTx za předpokladu Ax = b pouze pomocí
proměnné xN.
Platí: (B | N) (xB, xN)T = b
=> B.xB + N.xN = b
=> xB = B-1.(b – N.xN)
cTx = cB
T.xB + cN
T.xN = cB
T. B-1.(b – N.xN) + cN
T.xN =
= cB
T. B-1.b + (cN – NT.B-T.cB)T.xN =
= konst. + dN
kde dN je redukovaný cenový vektor
Lineární programování
- simplexová metoda - princip VI
Pokud jsou všechny složky xB kladné a některá
složka (například dN,i) vektoru dN záporná, můžeme
snížit hodnotu cTx tím, že do xB přesuneme xN,i.
Teoreticky můžeme zvolit libovolnou složku xN,i s
dN,i < 0.
Pokud neexistuje v dN záporná složka, aktuální bod
x je minimem.
Lineární programování
- simplexová metoda - princip VII
Pokud je zde více než jedna záporná složka, pak v
ideálním případě zvolíme tu složku, která vede k
největšímu poklesu cTx.
Existuje mnoho heuristik pro výběr vhodné složky.
Například Dantzigovo pravidlo:
Zvolte tu složku dN, která má co největší zápornou
hodnotu.
Lineární programování
- simplexová metoda - princip VIII
Pokud máme vybrán index i složky vektoru xN,
kterou přesuneme do báze, musíme vypočítat
hodnotu xN,i:
Pomocí této hodnoty můžeme dopočítat xB:
xB = B-1.(b – Ni.xN,i)








= −
−
−
= 0)NB(:
)NB(
)bB(
minx ji
1
ji
1
j
1
m...1ji,N
Lineární programování
- simplexová metoda - algoritmus
0) Najdi nějaký krajní bod x = (xB, xN), xN = 0 a
Ax = b.
1) Vypočítej redukovaný cenový vektor:
dN = (cN – NT.B-T.cB)T
Pokud dN  0, pak jsme v minimu
jinak zvol i tak, aby di = mink dk
2) Vypočítej xN,i a xB.
3) Pro první j, pro které xB,j = 0 vyměň xN,i a xB,j.
4) Jdi na 1).
Lineární programování
- simplexová metoda - dvoufázová
ad 0): Pro výběr prvního krajního bodu lze rovněž
využít minimalizační algoritmus => tzv. dvoufázová
metoda.
I) Řešení pomocné úlohy:
za předpokladu r = Ax – b, x  0, r  0
II) Řešení min cTx za předpokladu Ax = b, x  0.
=
m
1i
irmin
Lineární programování
- simplexová metoda - praxe - simplexová tabulka
Při ručním řešení úloh se velmi dobře osvědčuje
uspořádání výpočtů do tzv. simplexové tabulky,
která obsahuje koeficienty soustavy m+1 lineárních
rovnic ve standardním tvaru o n+1 neznámých.
Lineární programování
- simplexová metoda - praxe - simplexová tabulka
f(x) x1 x2 ... xn
xk1
...
xkm
f(x)
Lineární programování
- simplexová metoda - praxe - simplexová tabulka
Do hlavičky simplexové tabulky píšeme označení všech
proměnných (první z nich je proměná f(x)).
Do prvního sloupce píšeme označení proměnných, které
tvoří v příslušném kroku zkoumaný krajní bod (=
tzv. základní řešení).
Lineární programování
- simplexová metoda - praxe - simplexová tabulka II
Do posledního sloupce píšeme pravé strany soustavy
lineárních rovnic.
Poslední řádka odpovídá rovnici pro účelovou funkci.
Vstupující proměnné odpovídá v tabulce tzv. klíčový
sloupec.
Řádek, obsahující vystupující proměnnou, je klíčový
řádek.
Prvek ležící v průsečíku klíčového řádku a klíčového
sloupce nazveme klíčovým prvkem.
Lineární programování
- simplexová metoda - praxe - iniciace
Mějme úlohu LP ve
standardním tvaru:
a a
a a
a
a
x
b
bm m
n
mn m
11 21
1 2
1 1...
...
.    










=










f(x) x1 x2 ... xn
xk1 0 a11 a21 ... a1n b1
: : : : : :
xkm 0 am1 am2 ... amn bm
f(x) 1 c1 c2 ... cn 0
Do simplexové tabulky
ji zapíšeme takto:
( )c c c x f xn1 2  . ( )=
Lineární programování
- simplexová metoda - praxe - výpočet
Kritérium pro to, zda je řešení optimální, dává řádka
f(x). Pokud obsahuje záporné koeficienty, není řešení
optimální.
Vstupující proměnná (proměnná, která se přidá do báze)
je ta, která má největší zápornou hodnotu v
posledním řádku.
Lineární programování
- simplexová metoda - praxe - simplexová tabulka II
Vystupující proměnnou určíme tak, že dělíme postupně
čísla v posledním sloupci tabulky čísly z klíčového
sloupce, pokud jsou tato čísla kladná. Zvolíme tu
proměnnou, pro niž vyjde nejmenší hodnota.
V dalším řešení postupujeme takto:
V prvním sloupci nahradíme označení vystupující
proměnné označením vstupující proměnné.
Lineární programování
- simplexová metoda - praxe - simplexová tabulka II
Prvky v řádku vstupující proměnné dostaneme tak, že
dělíme prvky klíčového řádku klíčovým prvkem
Prvky v ostatních řádcích dostaneme tak, že od každého
řádku odečteme takový násobek řádu vstupující
proměnné, aby v klíčovém sloupci byly nuly (kromě
jedničky v řádku vstupující proměnné)
Lineární programování
- simplexová metoda - praxe - příklad
Nalézt maximum funkce: f(x) = 4x1 + 2x2
Za podmínek: -x1 + 3x2  9; 2x1 + 3x2  18
2x1 - x2  10; x1, x2  0
Standardní tvar rovnic:
-x1 + 3x2 + x3 = 9
2x1 + 3x2 + x4 = 18
2x1 - x2 + x5 = 10
f(x) - 4x1 - 2x2 = 0
Lineární programování
- simplexová metoda - praxe - příklad
Standardní tvar rovnic:
-x1 + 3x2 + x3 = 9; 2x1 + 3x2 + x4 = 18
2x1 - x2 + x5 = 10; f(x) - 4x1 - 2x2 = 0
I. f(x) x1 x2 x3 x4 x5
x3 0 -1 3 1 0 0 9
x4 0 2 3 0 1 0 18
x5 0 2 -1 0 0 1 10
f(x) 1 -4 -2 0 0 0 0
Do simplexové
tabulky je
zapíšeme
takto:
Lineární programování
- simplexová metoda - praxe - příklad
Výchozí základní řešení:
x1 = 0, x2 = 0, x3 = 9, x4 = 18, x5 = 10, f(x) = 0
I. f(x) x1 x2 x3 x4 x5
x3 0 -1 3 1 0 0 9
x4 0 2 3 0 1 0 18
x5 0 2 -1 0 0 1 10
f(x) 1 -4 -2 0 0 0 0
Do simplexové
tabulky je
zapíšeme
takto:
Lineární programování
- simplexová metoda - praxe - příklad
Výchozí základní řešení:
x1 = 5, x2 = 0, x3 = 14, x4 = 8, x5 = 0, f(x) = 20
Do simplexové
tabulky je
zapíšeme
takto:
II. f(x) x1 x2 x3 x4 x5
x3 0 0 5/2 1 0 1/2 14
x4 0 0 4 0 1 -1 8
x1 0 1 -1/2 0 0 1/2 5
f(x) 1 0 -4 0 0 2 20
Lineární programování
- simplexová metoda - praxe - příklad
Optimální řešení:
x1 = 6, x2 = 2, x3 = 9, x4 = 0, x5 = 0, f(x) = 28
Do simplexové
tabulky je
zapíšeme
takto:
III. f(x) x1 x2 x3 x4 x5
x3 0 0 0 1 -5/8 9/8 9
x4 0 0 1 0 1/4 -1/4 2
x1 0 1 0 0 1/8 3/8 6
f(x) 1 0 0 0 1 1 28
Cvičení
- příklad 1
Nalezněte krajní body množiny přípustných řešení
úlohy:
Nalézt maximum funkce:
f(x) = 15x1 + 2x2
Za podmínek:
x1 + x2  6
x1 - x2  0
xi  0
Cvičení
- příklad 2
Nalézt maximum funkce:
f(x) = 15x1 + 10x2 + 12x3 + 25x4
Za podmínek:
2x2 + 4x3 + 5x4  5000
2x1 + 2x2 + 4x4  6000
10x1 + 5x2 + 4x3 + 10x4  18000
xi  0