128
VYSOKÁ ŠKOLA POLYTECHNICKÁ JIHLAVA MATEMATIKA PRO EKONOMY Radek Stolín 2008 Katedra matematiky
VYSOKÁ ŠKOLA POLYTECHNICKÁ JIHLAVA
MATEMATIKA PRO EKONOMY
Radek Stolín
2008
Katedra matematiky
Recenzovaly: doc. RNDr. Eva Vaněčková, CSc.
Mgr. Andrea Kubišová
Za jazykovou a věcnou správnost obsahu díla odpovídá autor.
Text neprošel jazykovou ani redakční úpravou.
© Radek Stolín, 2008
ISBN 978-80-87035-17-7
Obsah
Úvod 5
1 Aritmetické vektory 7
1.1 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Operace s aritmetickými vektory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Lineární kombinace vektorů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 Lineární závislost vektorů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Matice 14
2.1 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Operace s maticemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Hodnost matice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4 Inverzní matice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.5 Maticové rovnice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 Determinanty 26
3.1 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2 Výpočet determinantů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4 Soustavy lineárních rovnic 34
4.1 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.2 Řešení soustav lineárních rovnic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.3 Řešení soustav lineárních rovnic pomocí inverzní matice. . . . . . . . . . . . . . . . . . . 36
4.4 Řešení soustav lineárních rovnic pomocí determinantů . . . . . . . . . . . . . . . . . . . . 38
4.5 Gaussova metoda řešení soustav lineárních rovnic . . . . . . . . . . . . . . . . . . . . . . . . 40
4.6 Jordanova metoda řešení soustav lineárních rovnic. . . . . . . . . . . . . . . . . . . . . . . . 43
Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5 Soustavy lineárních nerovnic 48
5.1 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.2 Algebraické řešení soustav lineárních rovnic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.3 Grafické řešení soustav lineárních rovnic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
6 Lineární programování 57
6.1 Úlohy výrobního plánování. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
6.2 Směšovací úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.3 Úlohy o dělení materiálu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6.4 Obecné vlastnosti řešení úloh lineárního programování. . . . . . . . . . . . . . . . . . . . . 64
Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
7 Řešení úloh lineárního programování 68
7.1 Grafické řešení úloh lineárního programování . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
7.2 Algebraické řešení úloh lineárního programování . . . . . . . . . . . . . . . . . . . . . . . . 74
7.3 Jednofázová simplexová metoda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
7.4 Dvoufázová simplexová metoda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
8 Dualita úloh lineárního programování 83
8.1 Symetrická dualita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
8.2 Nesymetrická dualita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
8.3 Vztahy mezi řešením duálně sdružených úloh . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
8.4 Ekonomická interpretace duálních proměnných . . . . . . . . . . . . . . . . . . . . . . . . . . 94
8.5 Duálně simplexová metoda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
9 Dopravní úlohy 100
9.1 Formulace dopravní úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
9.2 Vlastnosti dopravní úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
9.3 Metody určení výchozího základního řešení dopravní úlohy. . . . . . . . . . . . . . . . . 104
9.4 Nalezení optimálního řešení dopravní úlohy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
9.5 Degenerace v dopravní úloze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
9.6 Ekonomický význam duálních proměnných v dopravní úloze . . . . . . . . . . . . . . . 114
Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
Výsledky cvičení 118
Literatura 127
5
Úvod
Toto skriptum je určeno především pro ty studenty Vysoké školy polytechnické Jihlava, kteří
mají za povinnost absolvovat stejnojmenný předmět Matematika pro ekonomy.
Obsahově je text rozdělen do 9 kapitol. Prvních pět kapitol se věnuje vybraným částem
lineární algebry. Výběr je motivován získáním matematických znalostí potřebných pro řešení
úloh lineárního programování, kterými se zabývám v dalších čtyřech kapitolách. Každá
kapitola kromě teoretického výkladu obsahuje i ilustrační příklady a na konci je vždy uvedeno
několik úloh k samostatnému procvičení vyložené látky. Student si jistě po důkladném
prostudování teorie a propočítání předložených cvičení bude schopen sám vytvořit zadání
řady dalších zajímavých úloh.
I když na VŠPJ existuje dostatečné vybavení matematickým softwarem (např. Maple,
Excel), který umožňuje poměrně jednoduché řešení většiny předložených úloh, doporučuji
čtenáři, aby těchto prostředků používal pouze k ověření dosažených výsledků, popřípadě
k vyřešení komplikovanějších úloh. Rutinní a bezmyšlenkovité používání softwaru sice může
vést k získávání správných výsledků úloh určitých typů, ale hrozí nebezpečí, že student
nepochopí podstatu způsobu řešení a nebude tudíž schopen reagovat třeba i na drobné
odchylky v zadání.
Čtenářům budu velmi vděčný za upozornění na chyby a nejasnosti v textu.
Vysoká škola polytechnická Jihlava
prosinec 2007
Radek Stolín
6
7
1. Aritmetické vektory
1.1 Základní pojmy
Definice 1.1.1
Uspořádanou n-tici reálných čísel ),...,,( 21 naaaa , kde n N , nazýváme n-rozměrný
aritmetický vektor. Reálná čísla ai nazýváme i-tými složkami (souřadnicemi) n-rozměrného
aritmetického vektoru.
Pozn.
Dále budeme pojmem vektor rozumět n-rozměrný aritmetický vektor.
Definice 1.1.2
Vektor )0...,,0,0(o nazýváme nulový vektor.
Definice 1.1.3
Vektor ),...,,( 21 naaa a nazýváme vektor opačný k vektoru ),...,,( 21 naaaa .
Definice 1.1.4
Říkáme, že vektory ),...,,( 21 naaaa , )...,,,( 21 nbbbb se rovnají, jestliže pro všechna
ni ...,,2,1 je a bi i .
1.2 Operace s aritmetickými vektory
Definice 1.2.1
Součtem dvou vektorů ),...,,( 21 naaaa , )...,,,( 21 nbbbb nazýváme vektor
).,...,,( 2211 nn bababa ba
Definice 1.2.2
Nechť k R . Reálným násobkem vektoru ),...,,( 21 naaaa nazýváme vektor
),...,,( 21 nkakakak a .
Definice 1.2.3
Skalárním součinem vektorů ),...,,( 21 naaaa , )...,,,( 21 nbbbb nazýváme číslo (skalár)
....2211 nnbababa ab
Příklad 1.2.1
Jsou dány vektory a = (1, 2, 3, 4, 5), b = (-1, -1, 8, 2, 3). Určíme
a) ,bax
b) ,3by
c) .abs
8
Řešení
a) Podle definice 1.2.1 máme
).8,6,11,1,0(3)5 2,4 8,3 1,-2 1,-(1 bax
b) Podle definice 1.2.2 je
).9,6,24,3,3()33,23,83),1(3),1(3(3 by
c) Podle definice 1.2.3 dostáváme
.44352483)1(2)1(1 abs
1.3 Lineární kombinace vektorů
Definice 1.3.1
Mějme n -rozměrné aritmetické vektory ,...,,,, 21 rvvvu kde r N . Říkáme, že vektor u je
lineární kombinací vektorů rvvv ...,,, 21 , jestliže existují reálná čísla rccc ...,,, 21 taková, že
platí
....2211 rrccc vvvu
Příklad 1.3.1
Je vektor )1,1,3( u lineární kombinací vektorů 1v (1, 2, 3), 2v (0, -1, -3) a
3v (2, 1, 2)?
Řešení
Hledáme tedy taková reálná čísla c c c1 2 3, , , aby platilo
.332211 vvvu ccc
Po dosazení do této vektorové rovnice máme
(3, 1, -1) = c1(1, 2, 3) + c2(0, -1, -3) + c3(2, 1, 2).
Z definic 1.2.1 a 1.2.2 je zřejmé, že
(3, 1, -1) = (c1 + 2c3, 2c1 - c2 + c3, 3c1 - 3c2 +2c3).
Dále z definice 1.2.3 vyplývá, že tato rovnost platí právě tehdy, když současně platí
.2331
21
23
321
321
31
ccc
ccc
cc
Snadno určíme, že této soustavě vyhovují čísla
c1 = 1, c2 = 2 a c3 = 1.
Vektor u tedy je lineární kombinací vektorů 321 ,, vvv a získáme jej jako součet vektoru 1v ,
dvojnásobku vektoru 2v a vektoru 3v . Tedy platí, že
.2 321 vvvu
9
Příklad 1.3.2
Jsou dány vektory 1a = (3, 2, 0), 2a = (1, 5, -1) a 3a = (2, 2, 2). Zjistíme, zda je vektor 1a
lineární kombinací vektorů 2a , 3a .
Řešení
Podobně jako v předcházejícím příkladu sestavíme příslušnou soustavu rovnic
3 = c1 + 2c2
2 = 5c1 + 2c2
0 = -c1 + 2c2.
Sečtením první a třetí rovnice dostaneme
3 = 4c2
c2 = 3
4,
dosazením do třetí (nebo první) rovnice určíme
c1 = 3
2.
Nakonec zjistíme, zda vypočítané hodnoty vyhovují i zbývající (tedy druhé) rovnici.
Dostáváme
,4
32
2
352
což samozřejmě neplatí.
Protože tedy neexistují reálná čísla c1, c2 vyhovující dané soustavě, není vektor 1a
lineární kombinací vektorů 2a , 3a , tj. pomocí základních vektorových operací (viz definice
1.1.3 a 1.1.4) nelze z vektorů 2a , 3a získat vektor 1a .
1.4 Lineární závislost vektorů
Definice 1.4.1
Mějme n-rozměrné aritmetické vektory ,...,,, 21 rvvv kde r N . Říkáme, že tyto vektory
jsou lineárně závislé, jestliže existují reálná čísla ,...,,, 21 rccc z nichž alespoň jedno je různé
od nuly, taková, že
....2211 ovvv rrccc
V opačném případě nazýváme tyto vektory lineárně nezávislé.
Příklad 1.4.1
Rozhodneme, zda jsou vektory a = (2, -3, 4), b = (1, -1, 3), c = (3, 5, -1) lineárně závislé či
lineárně nezávislé.
Řešení
Podle definice 1.4.1 je třeba k určení lineární závislosti či nezávislosti hledat řešení rovnice
10
c1a + c2b+ c3c = o .
Obdobným postupem jako v řešení příkladu 1.3.1 odtud získáme soustavu, která má v tomto
případě tvar
2c1+ c2 + 3c3 = 0
-3c1 - c2 + 5c3 = 0
4c1+ 3c2 - c3 = 0.
Tuto soustavu můžeme řešit například tak, že ze třetí rovnice vyjádříme c3 a dosadíme do
prvních dvou rovnic, čímž dostaneme soustavu dvou rovnic o dvou neznámých. Postupně
tedy máme
c3 = 4c1+ 3c2
a
2c1+ c2 + 3(4c1+ 3c2) = 0
-3c1 - c2 + 5(4c1+ 3c2) = 0.
Po úpravě:
14c1+ 10c2 = 0
17c1+ 14c2 = 0.
Z toho je zřejmé, že existuje pouze jediné (tzv. triviální) řešení dané soustavy, a to
c1 = c2 = c3 = 0.
Podle definice jsou tudíž vektory cba ,, lineárně nezávislé.
Při dokazování lineární závislosti dané skupiny vektorů je jednodušší použít následující větu.
Věta 1.4.1
Mějme n-rozměrné aritmetické vektory ,...,,, 21 rvvv kde r N { }.1 Tyto vektory jsou
lineárně závislé právě tehdy, když je alespoň jeden z nich lineární kombinací ostatních.
Důkaz
a) Předpokládejme nejprve, že n-rozměrné aritmetické vektory ,...,,, 21 rvvv kde
}1{Nr , jsou lineárně závislé. Podle definice 1.4.1 tedy existují reálná čísla
,...,,, 21 rccc z nichž alespoň jedno (řekněme, že je to např. číslo c1) je různé od nuly,
taková, že
....2211 ovvv rrccc
Odtud je
....332211 rrcccc vvvv
Vydělením číslem 01 c máme
,......1
3
1
32
1
2
1
3
1
32
1
21 r
rr
r
c
c
c
c
c
c
c
c
c
c
c
cvvvvvvv
11
což podle definice 1.3.1 znamená, že vektor 1v je lineární kombinací vektorů
....,,, 32 rvvv
b) Předpokládejme nyní, že alespoň jeden (řekněme, že je to vektor 1v ) z n-rozměrných
aritmetických vektorů ,...,,, 21 rvvv kde },1{Nr je lineární kombinací ostatních.
Podle definice 1.3.1 existují reálná čísla rccc ...,,, 32 taková, že platí
....33221 rrccc vvvv
Odtud je
....)1(... 221221 ovvvvvv rrrr cccc
Podle definice 1.4.1 jsou vektory rvvv ...,,, 21 lineárně nezávislé, protože 011 c .
Tím je věta 1.4.1 dokázána.
Pozn.
Z věty 1.4.1 okamžitě vyplývá, že vektory, u = (3, 1, -1) 1v (1, 2, 3), 2v (0, -1, -3) a
3v (2, 1, 2) jsou lineárně závislé, protože jsme ukázali, že vektor u je lineární kombinací
vektorů 321 ,, vvv . Naopak z toho, že vektor 1a = (3, 2, 0) není lineární kombinací vektorů
2a = (1, 5, -1) a 3a = (2, 2, 2), nelze podle této věty ještě nic tvrdit o lineární závislosti
vektorů 1a , 2a a 3a .
Příklad 1.4.2
Ukážeme, že skupina vektorů a = (-1, -2, 0), b= (3, 0, 1), c = (2, -1, 1), d = (1, -1, -2) je
lineárně závislá.
Řešení
Zkusíme vyjádřit například vektor d jako lineární kombinaci zbývajících vektorů. Řešíme
tedy soustavu
1 = -c1 + 3c2 + 2c3
-1 = -2c1 - c3
-2 = c2 + c3.
Z první rovnice soustavy vyjádříme c1:
c1 = 3c2 + 2c3 - 1
a dosadíme do druhé rovnice. Spolu s opsanou třetí rovnicí získáme soustavu dvou rovnic o
dvou neznámých
, 2-
- 1) - 2 2(3- 1-
32
332
cc
ccc
což je po úpravě
. 2-
5 6 3
32
32
cc
cc
Druhou rovnici vynásobíme (-5) a obě rovnice sečteme. Dostáváme, že
12
c2 = 13.
Nyní už snadno dopočítáme
c3 = -15, c1 = 8.
Je tedy zřejmé, že vektor d je lineární kombinací vektorů ,,, cba a proto jsou podle
věty 1.4.1 vektory dcba ,,, lineárně závislé.
Určení lineární závislosti skupiny vektorů podle uvedené věty je v tomto příkladu méně
pracné než použití definice 1.4.1. To by totiž vedlo k řešení soustavy tří rovnic o čtyřech
neznámých, zatímco takto jsme pracovali při stejném počtu rovnic pouze se třemi
neznámými. Uvědomme si však, že věta 1.4.1 obecně neumožňuje rozhodnout o lineární
závislosti nebo nezávislosti skupiny vektorů v případě, že vybraný vektor z dané skupiny není
lineární kombinací vektorů ostatních. Např. vektory (2, -3, 1, -5), (4, 3, 2, 1) a (-6, 9, -3, 15)
jsou lineárně závislé a přitom vektor (4, 3, 2, 1) není lineární kombinací ostatních dvou
vektorů.
Poznamenejme závěrem, že o lineární závislosti či nezávislosti skupiny vektorů lze
pohodlněji rozhodnout výpočtem hodnosti matice, jak bude zřejmé z následující kapitoly.
Cvičení
1.1 Jsou dány vektory k = (1, -2, 0, 3, -2), l = ( 2, 2, -3, 6, 1) a m = ( ,23 0, -2, -3, -4).
Určete jejich lineární kombinace
a) 3k + 4l – 5m;
b) 84 k – 2l – 2m.
1.2 Určete skalární součiny následujících dvojic vektorů:
a) (4, -1, -2, 3, 0, 0, 1), (0, -1, -2, 5, 4, 0, -3);
b) (5, 1, 3), (2, 2, 2, 2);
c) (a, b, -b, -a), (b, a, a, b).
1.3 Vypočítejte číslo a tak, aby skalární součiny následujících dvojic vektorů byly rovny
nule.
a) (-2, a, 5, -3), (a, -7, 0, 3);
b) (a, -4, 3, 0), (a, 2a, -11, 77).
1.4 Mějme vektory a = (3, 1, 2), b = (2, 1, 0), c = (-1, -2, -3), d = (2, 2, 2). Zapište každý
z nich (pokud je to možné) jako lineární kombinaci ostatních.
1.5 Vyjádřete (pokud je to možné) vektor x jako lineární kombinaci vektorů r, s, t, jestliže
a) x = (8, 3, 2), r = (4, 1, 1), s = (1, 1, -1), t = (2, 0, 3);
b) x = (9, -7, -1), r = (-3, 3, 5), s = (-6, 5, 3), t = o;
c) x = (1, -1), r = (-14, 3), s = (5, -1), t = (1, 7);
d) x = (-1, 0, -3, -1), r = (0, 0, -3, 1), s = (2, 0, 0, 4), t = (3, 0, 3, -7).
1.6 Určete reálné číslo k tak, aby vektor u = (3, 1, -3) byl lineární kombinací vektorů
v = (2, -2, 2) a w = (5, -1, k).
1.7 Stanovte reálné číslo k tak, aby vektor x = (2, 5, k) byl lineární kombinací vektorů
x1 = (2, 3, 6), x2 = (1, 5, 3), x3 = (3, 7, 9).
13
1.8 Rozhodněte, zda je lineárně závislá nebo nezávislá skupina vektorů:
a) a = (-1, -2, 0), b = (3, 0, 1), c = (2, -1, 1);
b) a = (3, 5, -2), b = (0, -1, 1), c = (6, 7, -1);
c) a = (2, 1, 0), b = (0, 1, 2), c = (4, 1, -2), d = (1, 1, 1);
d) a = (1, 0, 2), b = (-2, 1, 0), c = (5, 2, -2), d = (-3, 2, 2);
e) a = (1, 0, -1, 0), b = (0, 1, 1, -1), c = (2, 3, 1, -3);
f) a = (1, 3, 5, 7), b = (0, 2, 5, 1), c = (0, 0, 2, -1), d = (0, 0, 0, 5);
g) a = (1, 3, -2, 1), b = (2, 7, -2, 5), c = (1, 4, 1, 3), d = (1, 5, 1, 9).
1.9 Určete, pro které hodnoty reálného čísla k jsou následující skupiny vektorů lineárně
závislé:
a) x = (3, 2, 4), y = (-2, 1, k), z = (1, 1, 2);
b) x = (2, -1, 3), y = (4, 1, 5), z = (-1, 2, k);
c) x = (1, 2, 4), y = (2, k, -4), z = (-1, -2, 2k);
d) x = (1, k, 1), y = (2, 2, k), z = (1, 1, 1).
1.10 Jsou pravdivá následující tvrzení?
a) Přidáme-li k lineárně závislým vektorům libovolný vektor, dostaneme lineárně
závislé vektory.
b) Přidáme-li k lineárně nezávislým vektorům libovolný vektor, získáme lineárně
nezávislé vektory.
c) Ubereme-li z lineárně závislých vektorů libovolný vektor, obdržíme opět
vektory lineárně závislé.
d) Ubereme-li z lineárně nezávislých vektorů libovolný vektor, dostaneme
vektory lineárně nezávislé.
1.11 Mějme n -rozměrné aritmetické vektory ,...,,,, 32 rvvvo kde .1Nr Dokažte, že
tyto vektory jsou lineárně závislé.
14
2. Matice
2.1 Základní pojmy
Definice 2.1.1
Schéma mn reálných čísel aij, kde ;...,,2,1 mi nj ...,,2,1 a m, n N, ve tvaru
mnmm
n
n
aaa
aaa
aaa
......
.....................
......
......
21
22221
11211
se nazývá matice typu m x n. Značíme A(m, n), A nebo (aij). Čísla aii jsou prvky tzv. hlavní
diagonály. V případě, že m = n, hovoříme o čtvercové matici n-tého stupně. Jsou-li všechny
prvky matice rovny nule, tj. aij = 0 pro všechna mi ...,,2,1 a nj ...,,2,1 , nazýváme
matici nulová matice.
Pozn.
Na matici A(m, n) lze pohlížet také tak, že je složena z m n-rozměrných (řádkových) vektorů
nebo z n m-rozměrných (sloupcových) vektorů. Pokud se v dalším textu budeme zmiňovat o
řádcích resp. sloupcích matice, budeme tím myslet příslušné řádkové resp. sloupcové vektory.
Definice 2.1.2
Transponovanou maticí k matici A(m, n) = (aij) nazýváme matici TA (n, m) = (aji) pro
všechna mi ...,,2,1 a nj ...,,2,1 .
Definice 2.1.3
Čtvercovou matici A(n, n) = (aij) nazýváme diagonální matice, jestliže pro všechna
nji ...,,2,1, platí, že
aij = 0 pro i j.
Je-li navíc aij = 1 pro i = j, nazýváme příslušnou matici jednotková matice a značíme ji I.
Definice 2.1.4
Takový tvar matice A(m, n) = (aij), ve kterém pro všechna mi ...,,2,1 a nj ...,,2,1 platí,
že
aij = 0 pro i > j a současně aij 0 pro i = j,
nazýváme lichoběžníkový tvar. Pokud je navíc m = n, nazýváme tento tvar trojúhelníkový
tvar.
Definice 2.1.5
Říkáme, že matice A(m, n) = (aij) a B(m, n) = (bij) se rovnají, jestliže pro všechna
mi ...,,2,1 a nj ...,,2,1 platí, že
aij = bij.
Zapisujeme A = B.
15
2.2 Operace s maticemi
Definice 2.2.1
Součtem matic A(m, n) = (aij) a B(m, n) = (bij) nazýváme matici C(m, n) = (cij), jestliže pro
všechna mi ...,,2,1 a nj ...,,2,1 platí:
cij = aij + bij.
Zapisujeme C = A + B.
Definice 2.2.2
Reálným násobkem matice A(m, n) = (aij) číslem kR nazýváme matici C(m, n) = (cij),
jestliže pro všechna mi ...,,2,1 a nj ...,,2,1 platí:
cij = kaij.
Zapisujeme C = kA.
Definice 2.2.3
Součinem matic A(m, n) = (aik) a B(n, p) = (bkj) nazýváme matici C(m, p) = (cij), jestliže pro
všechna mi ...,,2,1 a pj ...,,2,1 platí:
cij = .1
kj
n
k
ikba
Zapisujeme C = AB.
Příklad 2.2.1
Jsou dány matice
A =
201
223
212
, B =
311
403
225
, C =
120
832
521
.
Určíme matice a) K = A + B;
b) L = 6C;
c) Q = AB – BA.
Řešení
Podle definice 2.2.1 sčítáme matice tak, že sčítáme jejich stejnolehlé prvky a podle definice
2.2.2 násobíme matici reálným číslem tak, že vynásobíme tímto číslem všechny její prvky.
Tedy postupně dostáváme:
a) K = A + B =
201
223
212
+
311
403
225
=
321011
420233
)2(22152
=
512
626
437
.
b) L = 6C = 6
120
832
521
=
)1(62606
863626
562616
=
6120
481812
30126
.
16
Podle definice 2.2.3 se prvek v i-tém řádku a j-tém sloupci matice C, která je součinem matic
A, B v tomto pořadí, určí jako skalární součin i-tého řádkového vektoru matice A a j-tého
sloupcového vektoru matice B.
c) Q = AB – BA =
201
223
212
311
403
225
-
311
403
225
201
223
212
=
=
3240)2(1120021123051
3242)2(3120223123253
3)2(41)2(21)2(01221)2(3152
-
-
2321)2(1032111133121
2420)2(3043013143023
2)2(22)2(50)2(22151)2(3225
=
=
447
8823
6211
-
638
2310
10914
=
211
6513
473
.
Poslední výsledek pouze potvrzuje skutečnost zřejmou již z definice 2.2.3. Násobení matic
není komutativní operace (tedy obecně neplatí, že AB = BA), na rozdíl od násobení reálných
čísel.
2.3 Hodnost matice
Definice 2.3.1
Hodností matice A(m, n) nazýváme číslo, které se rovná maximálnímu počtu lineárně
nezávislých řádků této matice. Označujeme h(A).
Věta 2.3.1
Hodnost matice A(m, n) v lichoběžníkovém tvaru je rovna počtu nenulových řádků této
matice.
Věta 2.3.2 (úpravy neměnící hodnost matice)
Hodnost matice A se nezmění, jestliže provedeme některou z následujících úprav:
1) Matici transponujeme.
2) Vyměníme libovolné dva řádky.
3) Libovolný řádek vynásobíme libovolným nenulovým reálným číslem.
4) K libovolnému řádku přičteme libovolnou lineární kombinaci ostatních řádků.
5) Vynecháme řádek, který je lineární kombinací ostatních řádků.
Pozn.
Řádkové úpravy v bodech 2) až 5), označme je (u2) až (u5), se tedy podle bodu 1) dají dělat i
se sloupci matice A.
Z uvedeného je okamžitě zřejmá následující věta, jejíž znalost při určování hodnosti matice
může být užitečná.
17
Věta 2.3.3
Pro hodnost h(A) matice A(m, n) platí, že
h(A) ),min( nm .
Z vět 2.3.1 a 2.3.2 je zřejmé, jak lze postupovat při určování hodnosti dané matice. Pomocí
úprav, které nemění hodnost, získat matici v lichoběžníkovém tvaru, která má stejnou hodnost
jako původní matice a ze které lze tuto hodnost pohodlně určit. Skutečnost, že dvě matice
mají stejnou hodnost, budeme vyjadřovat symbolem .
Příklad 2.3.1
Určíme hodnost matice
021
131
202
225
322
A .
Řešení
Nejprve provedeme výměnu 1. a 4. řádku (u2). Dále násobíme první řádek číslem(-5) a
přičteme jej ke 2. řádku. První řádek násobíme číslem (-2) a přičteme ke třetímu a znovu
násobíme první řádek číslem (-2) a přičteme ke čtvrtému a konečně přičteme první řádek
k pátému (u4). Vynásobíme 3. řádek číslem (-1/6) (u3) a současně vyměníme 2. a 3. řádek
(u2). Druhý řádek násobíme postupně čísly 17, 4 a (-5) a přičítáme ke třetímu, čtvrtému a
pátému řádku (u4). Vynecháme třetí a čtvrtý řádek, protože jsou násobky pátého řádku (u5).
Výsledná matice má lichoběžníkový tvar a obsahuje tři nenulové řádky, tedy je její hodnost 3,
a tudíž také h(A) = 3.
.
100
010
131
100
100
300
010
131
150
140
3170
010
131
150
140
060
3170
131
021
322
202
225
131
021
131
202
225
322
Příklad 2.3.2
Pomocí hodnosti matice rozhodneme o lineární závislosti či nezávislosti vektorů
).1,2,3,2,0(),5,2,0,1,3(),3,1,1,0,2( cba
Řešení
Z definice 2.3.1 okamžitě vyplývá možný postup řešení. Z daných vektorů vytvoříme matici,
řekněme C, typu 3 x 5 a určíme její hodnost. Jestliže bude 3Ch , budou dané tři vektory
lineárně nezávislé, jestliže ale bude 3Ch , budou tyto vektory lineárně závislé. Analogicky
jako při řešení předchozího příkladu postupně použitím úprav (u3) a (u4) dostáváme
18
.
21000
11320
31102
12320
11320
31102
12320
52013
31102
C
Poslední matice však není lichoběžníková (nula na hlavní diagonále). Jedinou možností, jak
se v tomto případě dostat k lichoběžníkové matici, je vyžít úpravu (u1) ve smyslu poznámky
za větou 2.3.2 a vyměnit třetí a čtvrtý sloupec uvažované matice. Máme
.
20100
13120
31102
21000
11320
31102
To už je lichoběžníková matice a podle věty 2.3.1 je 3Ch . Vektory a, b, c jsou tedy
s ohledem na definici 2.3.1 lineárně nezávislé.
2.4 Inverzní matice
Analogie operací s reálnými čísly a s maticemi nás vede k otázce, zda existuje nějaká operace
s maticemi, která by byla obdobou operace dělení reálných čísel. Ze střední školy víme, že
dělit reálné číslo b reálným číslem a různým od nuly znamená násobit číslo b číslem 11 aa
.
Číslo 1a se nazývá převrácená hodnota čísla a a platí, že 111 aaaa .
Uvědomíme-li si, že u matic představuje neutrální prvek vzhledem k násobení jednotková
matice I (je zřejmé, že pro libovolnou čtvercovou matici A platí AIAAI ), nabízí se
následující definice.
Definice 2.4.1
Nechť A, X, I jsou čtvercové matice n-tého stupně. Jestliže platí
IAX ,
potom X nazýváme inverzní matice k matici A a značíme ji 1A .
Definice 2.4.2
Nechť A je čtvercová matice n-tého stupně. Jestliže nh A , nazýváme A regulární maticí.
Je-li nh A nazýváme A singulární maticí.
Věta 2.4.1
Ke čtvercové matici A existuje inverzní matice právě tehdy, když A je regulární. V tom
případě je inverzní matice určena jednoznačně.
Věta 2.4.2
Jestliže A je regulární matice, potom 1A je rovněž regulární a platí
AA 11 .
19
Věta 2.4.3
Jestliže A je regulární matice a I jednotková matice stejného stupně jako A, potom platí
IAAAA 11 .
Věta 2.4.4
Jestliže A je regulární matice, potom platí
T11T AA .
Popíšeme si dále jeden ze způsobů, jak lze k dané matici vypočítat matici inverzní (pokud
existuje), kterému se říká Gaussův algoritmus výpočtu inverzní matice. Předpokládejme, že
máme čtvercovou regulární matici A n-tého stupně a jednotkovou matici I téhož stupně jako
A. Vytvoříme matici typu (n, 2n) tak, že matice A a I zapíšeme vedle sebe v tomto pořadí.
Označme takto vzniklou matici jako A|I. Dále upravíme tuto matici pomocí úprav neměnících
hodnost matice (u2) až (u4) z věty 2.3.2 (tedy zásadně pouze řádkové úpravy) tak, aby
v jejích prvních n sloupcích byla jednotková matice. Lze dokázat, že v posledních n sloupcích
získané matice je hledaná matice inverzní k matici A. Schematicky lze situaci vyjádřit jako
1... A|II|A .
Příklad 2.4.1
Nalezneme inverzní matici k matici
.
121
102
121
A
Řešení
Podle věty 2.3.2 postupně máme
.
111
0
100
010
001
111
321
101
100
040
002
111
321
110
100
040
021
111
012
001
100
340
121
101
012
001
240
340
121
100
010
001
121
102
121
43
21
41
21
21
Je tedy
.
444
321
202
4
1
111
0
43
21
41
21
21
1
A
Poslední tvar zápisu výsledné inverzní matice se často používá v případě, že matice
neobsahuje celočíselné prvky. Zápis v uvedeném tvaru umožňuje definice 2.2.2.
20
Ověřit správnost vypočítané inverzní matice lze podle věty 2.4.3 pomocí součinu nalezené
inverzní matice a matice původní (v libovolném pořadí). Tento součin by měl být roven
příslušné jednotkové matici.
2.5 Maticové rovnice
Úloha řešit maticovou rovnici o jedné neznámé matici X znamená nalézt takovou matici X,
která po dosazení do příslušné maticové rovnice převede tuto rovnici po provedení
naznačených početních operací s maticemi na rovnost.
Příklad 2.5.1
Určíme matici X tak, aby platilo BXXA 4312 T , jestliže je
.
962
031
630
,
432
251
353
12
1
BA
Řešení
Nejdříve z dané maticové rovnice vyjádříme explicitně matici X. Přitom ale musíme mít stále
na paměti, že se jedná o matice, a vzít např. v úvahu, že násobení matic není komutativní.
Máme
.3124
4312312312
zleva312./4312
4312
1T
1TT1T
1TT
T
BIAX
BIAXIAIA
IABXIA
BXXA
Dále určíme matici IA 312 T .
.
123
325
210
300
030
003
423
355
213
312 T
IA
Analogicky jako v příkladu 2.4.1 nalezneme k této matici matici inverzní. Celý postup jen
trochu urychlíme tím, že budeme „nulovat“ v daném sloupci prvky pod a současně i nad
hlavní diagonálou. Můžeme postupně psát
.
534
1064
754
400
040
004
534
532
211512
400
020
0012
534
001
102
400
210
503
530
001
100
440
210
123
010
001
100
325
210
123
100
010
001
123
325
210
21
Je tedy
.
534
1064
754
4
1312
1T
IA
Pro hledanou matici X tudíž máme
.
21277
666614
39459
962
031
630
534
1064
754
4
14
X
Aritmetické n-rozměrné vektory, které jsme zavedli v předešlé kapitole, je zvykem při práci
s maticovými rovnicemi zapisovat do sloupců a chápat jako matice typu n x 1. Tuto konvenci
budeme v dalším dodržovat i my, takže nadále bude
n
n
x
x
x
xxx2
1
T21 )...,,,(x
a
)....,,,( 21T
nxxxx
Příklad 2.5.2
Jsou dány matice
.
0
1
1
1
,
1111
0112
1301
1121
bA
Určíme matici (vektor) x, pro kterou platí
.bAxx
Řešení
Nejprve opět vyjádříme x:
.1bAIx
bxAI
bAxx
bAxx
Dále určíme 1AI . Máme
22
.
15211143000
30330300
61440030
01110003
15211143000
10110100
61440030
01110003
15211143000
10110100
81682010
51451001
123031400
10110100
01202810
01101501
123031400
024131500
01202810
01101501
10101220
00011120
01202810
00101311
10000111
00011120
01000212
00101311
10000111
01000212
00101311
00011120
Odtud
.
1521114
3033
6144
0111
3
11
AI
Při výpočtu matice 1AI stojí za povšimnutí úprava, kterou jsme použili při přechodu od
čtvrtého tvaru matice k pátému – čtvrtý řádek jsme přičetli k řádku třetímu (u4). Touto
úpravou jsme totiž celý další postup podstatně zjednodušili.
Hledanou matici (vektor) x vypočítáme pomocí součinu. Platí, že
.
9
2
3
1
0
1
1
1
1521114
3033
6144
0111
3
11
bAIx
Cvičení
2.1 Jsou dány matice A =
72550
35123, B =
00562
139712 a
C =
82037
22222. Vypočítejte následující matice:
23
a) U = B + C;
b) V = (-3)C;
c) X = A + B – C;
d) Y = 2A - (B -3C);
e) Z =4
1(-2B +
3
1C -
2
3A).
2.2 Určete součin AB následujících dvojic matic:
a) A =
54
77, B =
119105
1531;
b) A =
212
394
213
, B =
100
010
001
;
c) A =
1111
0000
4321
1234
, B =
7926
2632
11357
11271
;
d) A =
33333
11111
12021
, B =
34
25
105
13
32
.
2.3 Určete součiny BA matic ze cvičení 2.2 (pokud existují).
2.4 Mějme matice A =
101
987
654
321
642
, B =
0212
1110
1531
. Určete:
a) R = 2(AB)T;
b) S = AAT.
2.5 Určete hodnosti následujících matic:
a)
3541
2405
1273
A
24
b)
7654
02711
8425
3232
B ;
c)
63
101
05
27
32
C ;
d)
3
2
2
3
D ;
e)
5012
0123
5468
2150
3274
0053
E ;
f)
05131
10410
110252
12511
15321
F .
2.6 Pomocí hodnosti matice rozhodněte o lineární závislosti daných skupin vektorů:
a) k = (2, 3, -2, 1), l = (-1, 3, 2, 1), m = (4, -1, -2, -1), n = (1, 0, 0, -2);
b) k = (1, -2, -1), l = (3, 2, 1), m = (4, -1, r), kde Rr ;
c) k = (5, 0, -1, 1), l = (2, 3, -2, 4), m = (-3, -1, -3, -1), n = (3, -3, 1, 2).
2.7 U následujících matic rozhodněte, zda jsou regulární nebo singulární. Pokud jsou
regulární, nalezněte matici inverzní.
a) A = ;15
32
b) B = ;
351
513
135
25
c) C = ;
931
415
102
d) D = .
3222
2221
2211
2111
2.8 Určete matici X tak, aby platilo ,BAXA jestliže
.
333
155
234
a
033
102
112
BA
2.9 Určete matici X tak, aby platilo ,2 CXBAX jestliže
.
651
312
231
a
420
234
612
,
131
122
011
CBA
26
3. Determinanty
3.1 Základní pojmy
Připomeňme nejprve několik pojmů z kombinatoriky.
Definice 3.1.1
Mějme množinu .kde,...,,2,1 NnnM Každá uspořádaná n-tice
nkkk ...,,, 21
vytvořená ze všech prvků množiny M se nazývá permutace z n prvků.
Věta 3.1.1
Počet všech permutací z n prvků je n!.
Příklad 3.1.1
Pro n = 4 tedy existuje celkem 4! = 4.3.2.1 = 24 permutací. Jsou to:
.2,3,1,4,3,2,1,4,2,1,3,4,1,2,3,4,3,1,2,4,1,3,2,4
,2,1,4,3,1,2,4,3,2,4,1,3,4,2,1,3,1,4,2,3,4,1,2,3
,1,3,4,2,3,1,4,2,1,4,3,2,4,1,3,2,3,4,1,2,4,3,1,2
,2,3,4,1,3,2,4,1,2,4,3,1,4,2,3,1,3,4,2,1,4,3,2,1
Definice 3.1.2
Dvojice ji kk , se nazývá inverze v permutaci nkkk ...,,, 21 , jestliže je současně
ji kkji a .
Příklad 3.1.2
V permutaci 2,1,4,3 jsou inverzemi dvojice
3,1; 3,2; 4,1 a 4,2.
Definice 3.1.3
Mějme čtvercovou matici n-tého stupně A(n) =(aij). Součet
,...1...,,,
21
21
21
n
n
K
kkkK
nkkkp
aaa
kde Kp je počet inverzí v permutaci K, se nazývá determinant matice A a značí se det A.
Pozn.
1) Determinant matice je definován pouze v případě, že je tato matice čtvercová.
2) Determinant čtvercové matice n-tého stupně A je součtem n! členů ve tvaru
nnkkk aaa ...21 21 , které jsou kladné v případě, že permutace nkkk ...,,, 21 má sudý
počet inverzí a záporné v případě, že permutace nkkk ...,,, 21 má lichý počet
inverzí.
27
3) Každý člen nnkkk aaa ...
21 21 determinantu matice A obsahuje právě jednoho činitele
z každého řádku a každého sloupce matice A.
4) Pro determinant matice A používáme i jiná označení např.
ija AAdet .
3.2 Výpočet determinantů
Příklad 3.2.1
Určíme obecně podle definice 3.1.3 determinant matice druhého stupně.
Řešení
Máme
.)1()1(det 2112221121121
22110
2221
1211aaaaaaaa
aa
aaA
Příklad 3.2.2
Pomocí řešení předešlého příkladu platí, že
.11152321
53
Příklad 3.2.3
Určíme obecně podle definice 3.1.3 determinant matice třetího stupně.
Řešení
Máme
).(
)1()1()1(
)1()1()1(det
332112322311312213322113312312332211
312213
3
322113
2
312312
2
332112
1
322311
1
332211
0
333231
232221
131211
aaaaaaaaaaaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaa
aaa
aaa
A
Odvozený vzorec z příkladu 3.2.3 vyjadřuje tzv. Sarrusovo pravidlo pro výpočet
determinantu třetího stupně. Toto pravidlo si lze snadno zapamatovat podle naznačeného
schématu.
+ + + - - -
3231
2221
1211
333231
232221
131211
aa
aa
aa
aaa
aaa
aaa
=
28
).( 332112322311312213322113312312332211 aaaaaaaaaaaaaaaaaa
Věta 3.2.1 (Sarrusovo pravidlo)
Nechť A = (aij) je čtvercová matice třetího stupně. Potom platí
).(det 332112322311312213322113312312332211
333231
232221
131211
aaaaaaaaaaaaaaaaaa
aaa
aaa
aaa
A
Příklad 3.2.4
Pomocí řešení předchozího příkladu je
.3223664
102)2()1(134)3()2(0)3(3)1(2141
23123
40140
21321
Determinanty čtvrtého a vyšších stupňů se podle definice nepočítají, protože by to bylo velmi
nepřehledné a pracné. Postupuje se většinou tak, že se determinant n-tého stupně převede na
determinant stupně (n – 1). Takto se postupuje dál až k determinantu třetího stupně, který
vypočteme pomocí dříve uvedeného Sarrusova pravidla. Způsob, kterým lze převádět
determinanty n-tého stupně na determinant stupně (n – 1), dále popíšeme.
Definice 3.2.1
Mějme čtvercovou matici n-tého stupně A. Determinant, který vznikne z determinantu matice
A vynecháním i-tého řádku a j-tého sloupce, nazýváme subdeterminant (minor) prvku aij
matice A a značíme Mij.
Definice 3.2.2
Mějme čtvercovou matici n-tého stupně A. Doplňkem prvku aij nazýváme číslo ,1 ij
jiM
kde Mij je subdeterminant prvku aij.
Příklad 3.2.5
Je dán determinant matice A
.
4301
2023
0401
5102
Určíme doplněk prvku a32.
Řešení
Nejprve podle definice 3.2.1 určíme M32. Máme
29
.
431
041
512
32 M
Dále podle definice 3.2.2 je doplněk prvku a32
.23)402015032()1(
431
041
512
123
Věta 3.2.2 (o rozvoji determinantu podle i-tého řádku)
Nechť A je čtvercová matice n-tého stupně. Potom pro ni ...,,2,1 platí
n
r
irir
riMa
1
.1det A
Věta 3.2.3 (o rozvoji determinantu podle j-tého sloupce)
Nechť A je čtvercová matice n-tého stupně. Potom pro nj ...,,2,1 platí
n
r
rjrjjr
Ma1
.1det A
Příklad 3.2.6
Určíme hodnotu determinantu
.
4301
2023
0401
5102
Řešení
Použijeme větu 3.2.3 s j = 2 a výsledek příkladu 3.2.5. Máme
.46)23(2
431
041
512
2)1(
203
041
512
0)1(
431
041
512
2)1(
431
203
512
0)1(
431
203
041
0)1(
4301
2023
0401
5102
24
232221
Tento příklad ukazuje, jak výhodné je mít v řádku nebo sloupci determinantu, podle kterého
rozvoj provádíme, nuly. Snadno si spočítáme, že například pro výpočet determinantu pátého
30
stupně s nenulovými prvky bychom museli spočítat 5.4 = 20 determinantů třetího stupně, což
je příliš pracné.
Následující dvě věty nám umožní upravit determinant před vlastním výpočtem tak, aby
ve vybrané řadě byl pouze jeden nenulový prvek, což samotný výpočet podstatně zjednoduší.
Věta 3.2.4
Pro libovolnou čtvercovou matici A platí:
Tdetdet AA .
Pozn.
Z této věty plyne, že není nutné rozlišovat řádky a sloupce determinantu (platí-li nějaké
tvrzení pro řádky determinantu, platí i pro jeho sloupce). Proto budeme řádky a sloupce
determinantu napříště označovat společným názvem řady determinantu.
Věta 3.2.5
Pro libovolný determinant platí:
a) násobíme-li libovolnou řadu determinantu reálným číslem c, potom se číslem c násobí
celý determinant;
b) vyměníme-li v determinantu navzájem libovolnou dvojici rovnoběžných řad, změní
determinant znaménko;
c) přičteme-li k některé řadě determinantu libovolnou lineární kombinaci řad s ní
rovnoběžných, pak se hodnota determinantu nezmění.
Pozn.
Z věty 3.2.5 plyne, že jsou-li řady v determinantu lineárně závislé, je determinant roven nule.
Lineární závislost řad determinantu poznáme okamžitě v případě, že jsou dvě rovnoběžné
řady úměrné.
Příklad 3.2.7
Určíme hodnotu determinantu matice
.
0312
1213
2115
2231
A
Řešení
Nejprve se zbavíme nenulových prvků v prvním a ve druhém řádku čtvrtého sloupce pomocí
úprav z věty 3.2.5 a potom rozvineme podle čtvrtého sloupce. Máme
.
312
331
655
312
331
655
11
0312
1213
0331
0655
0312
1213
2115
2231
det43
A
Dále si můžeme vybrat. Buď použijeme Sarrusovo pravidlo, nebo ještě jednou poslední
determinant upravíme a rozvineme. Ukažme si druhou možnost – úpravu a rozvinutí podle
třetího řádku. Postupně dostáváme
31
.67
915
67
91511
010
637
9515
312
331
655
det23
A
Získali jsme tedy determinant druhého stupně, který ještě můžeme zjednodušit úpravou podle
věty 3.2.5 a snadno vypočítat. Je
.272130327
3153
67
915det
A
Někdy se determinanty počítají podle následující věty.
Věta 3.2.6
Mějme čtvercovou matici n-tého stupně A(n) = (aij). Je-li tato matice v trojúhelníkovém tvaru,
potom platí, že
nnaaa ...det 2211A .
Příklad 3.2.8
Určíme hodnotu determinantu matice
.
0312
1213
2115
2231
A
Řešení
Podle věty 3.2.5 postupně máme
811140
58100
4150
2231
4150
58100
811140
2231
0312
1213
2115
2231
det A
.
9000
1200
4150
2231
2
13
5
1
164100
1200
4150
2231
35
1
164100
3600
4150
2231
5
1
Použijeme-li nyní větu 3.2.6, dostáváme
.2792512
13
5
1det A
Věta 3.2.7
Mějme čtvercovou matici A. Matice A je regulární tehdy a jen tehdy, když je její determinant
různý od nuly.
32
Příklad 3.2.9
Prostřednictvím výpočtu determinantu matice
615
012
213
A
rozhodneme, zda je matice A regulární nebo singulární.
Řešení
Determinant matice A je
.0120104018
615
012
213
Matice A je tedy podle věty 3.2.7 singulární (její řádkové vektory jsou lineárně závislé).
Věta 3.2.8
Jestliže jsou A, B čtvercové matice stejného řádu, potom je
BAAB detdetdet .
Věta 3.2.9
Je-li A regulární matice, potom determinant matice inverzní k matici A je
AA
det
1det 1 .
Důkaz
Podle věty 3.2.8, definice inverzní a jednotkové matice a věty 3.2.6 postupně máme
,1detdetdetdet 11 IAAAA
odkud již plyne tvrzení věty.
Cvičení
3.1 Vypočítejte determinant
.
013
792
861
33
3.2 Vypočítejte determinant
.
8734
1202
7734
3524
3.3 Vypočítejte determinant
.
43219
11195
1110952
87674
54321
3.4 Rozhodněte, zda jsou vektory a = (1, 3, 5, 7), b = (4, 2, 5, 1), c = (-2, 2, 2, -1) a
d = (0, 0, 0, 5) lineárně závislé či nezávislé.
3.5 Vypočtěte determinant matice 1A , jestliže
.
5678
4635
2158
7623
A
34
4. Soustavy lineárních rovnic
4.1 Základní pojmy
Definice 4.1.1
Soustavou m lineárních rovnic o n neznámých (proměnných) ,,..., 21 Rxxx n Nnm ,
rozumíme soustavu
....
.................................................
...
...
2211
22222121
11212111
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
(4.1.1)
Reálná čísla aij, kde mi ...,,2,1 a nj ...,,2,1 , se nazývají koeficienty a reálná čísla ,ib
kde ,...,,2,1 mi se nazývají pravé strany.
Definice 4.1.2
Matici
mnmm
n
n
aaa
aaa
aaa
...
............
...
...
21
22221
11211
A
nazýváme matice soustavy (4.1.1). Matici
mmnmm
n
n
r
baaa
baaa
baaa
...
...............
...
...
21
222221
111211
A
nazýváme rozšířená matice soustavy (4.1.1).
Definice 4.1.3
Vektor T21 )...,,,( nxxxx nazýváme vektor neznámých (proměnných) soustavy (4.1.1) a
vektor T21 )...,,,( mbbbb nazýváme vektor pravých stran soustavy (4.1.1).
S použitím definic 4.1.2 a 4.1.3 a definic součinu a rovnosti matic z druhé kapitoly lze
soustavu (4.1.1) zapsat v maticovém tvaru
.bAx (4.1.2)
35
4.2 Řešení soustav lineárních rovnic
Řešit soustavu lineárních rovnic (4.1.1) znamená nalézt všechny vektory neznámých
,,...,T
21 nxxxx které vyhovují každé rovnici soustavy (4.1.1). Tyto vektory tvoří tzv.
množinu řešení soustavy (4.1.1).
Ze střední školy je známo, že při řešení soustavy lineárních rovnic může nastat jeden ze tří
následujících případů:
soustava lineárních rovnic nemá řešení;
soustava lineárních rovnic má právě jedno řešení;
soustava lineárních rovnic má nekonečně mnoho řešení.
Věta 4.2.1 (Frobeniova)
Soustava lineárních rovnic (4.1.1) má alespoň jedno řešení tehdy a jen tehdy, když je hodnost
matice soustavy hh A rovna hodnosti rozšířené matice soustavy rr hh A .
Pozn.
Tato věta tedy (pouze) stanovuje, kdy daná soustava má a kdy nemá řešení. V případě, že
řešení existuje, neříká nic o jejich počtu.
Věta 4.2.2 Nechť soustava lineárních rovnic (4.1.1) má řešení, h je hodnost matice soustavy a n je počet
neznámých. Potom platí:
(a) Jestliže h = n, potom má soustava (4.1.1) právě jedno řešení.
(b) Jestliže h < n, potom má soustava (4.1.1) nekonečně mnoho řešení, přičemž za n – h
neznámých lze volit libovolná reálná čísla a ostatní neznámé jsou určeny jednoznačně.
Příklad 4.2.1
Určíme počet řešení soustavy dvou lineárních rovnic o třech neznámých a zapíšeme je:
.1
742
32
321
xx
xxx
Řešení
Dané soustavě přiřadíme rozšířenou matici soustavy
.1110
7421
rA
Je zřejmé, že hodnost rozšířené matice soustavy hr = 2, hodnost matice soustavy h = 2 a počet
neznámých n = 3. Z věty 4.2.2 vyplývá, že soustava má nekonečně mnoho řešení, přičemž
jedna neznámá je volitelná. Zvolme například za neznámou x3 libovolné reálné číslo a
vyjádřeme pomocí ní neznámé zbývající. Z druhé rovnice dostaneme, že
.1 32 xx
Po dosazení do první rovnice dostaneme po úpravě, že
.25 31 xx
Všechna řešení soustavy tedy můžeme zapsat ve tvaru
36
Rxxxx 3T
333 kde,,1,25x
nebo ve tvaru
.kde,1,1,20,1,5 3T
3T
Rxx x
V dalším výkladu uvedeme několik metod používaných pro řešení soustav lineárních rovnic.
Pro první dvě metody je společné, že je lze použít pouze v případě, kdy má soustava právě
jedno řešení (podle vět 4.2.1 a 4.2.2 tedy v případě, že platí: nhh r ).
4.3 Řešení soustav lineárních rovnic pomocí inverzní matice
Věta 4.3.1
Jestliže je matice soustavy (4.1.1) A regulární, potom má tato soustava právě jedno řešení
bAx 1 . (4.3.1)
Důkaz Podle věty 2.4.1 existuje k regulární matici A matice inverzní a je určena jednoznačně. Vztah
(4.3.1) pak dostaneme explicitním vyjádřením x z (4.1.2).
Pozn.
Podle předpokladu věty 4.3.1 se jedná pouze o soustavy, ve kterých m = n.
Příklad 4.3.1
Pomocí inverzní matice nalezneme řešení soustavy tří lineárních rovnic o třech neznámých
.1433
272
12
321
321
321
xxx
xxx
xxx
Řešení
Neznámé 321 ,, xxx určíme podle (4.3.1). Nejprve Gaussovým algoritmem popsaným v části
2.4 určíme inverzní matici k matici soustavy
.
433
712
211
A
Máme
37
.
0100
1010
1001
~
0100
1010
102011
~
~
0100
012310
001211
~
103200
012310
001211
~
100433
010712
001211
2
1
2
3
2
3
2
13
2
5
2
17
2
1
2
3
2
3
2
13
2
1
2
3
Je tedy zřejmé, že
.
103
3213
5217
2
11
A
Dosazením do (4.3.1) získáme hledané řešení dané soustavy rovnic:
.
1
3
4
1
2
1
.
103
3213
5217
2
1
x
Zkouškou se snadno můžeme přesvědčit, že 1,3,4 321 xxx vyhovují zadané
soustavě.
Příklad 4.3.2
Pomocí inverzní matice se pokusíme vyřešit soustavu tří lineárních rovnic o třech neznámých
.2433
272
032
321
321
321
xxx
xxx
xxx
Řešení
Budeme postupovat stejně jako v řešení minulého příkladu. Hledáme tedy nejprve inverzní
matici k matici
.
433
712
321
A
Postupně dostáváme
.
111000
0121330
001321
~
1031330
0121330
001321
~
100433
010712
001321
Matice dané soustavy je tedy singulární a podle věty 4.2.2 nemá soustava právě jedno řešení.
38
4.4 Řešení soustav lineárních rovnic pomocí determinantů
Věta 4.4.1 (Cramerovo pravidlo)
Jestliže je matice soustavy (4.1.1) regulární matice n-tého stupně, potom má tato soustava
právě jedno řešení, které se dá zapsat ve tvaru
,...,,2,1pro,det
detnjx
j
j A
A
kde Aj je matice, která vznikne z matice A nahrazením j-tého sloupce sloupcem pravých stran
rovnic soustavy (4.1.1).
Příklad 4.4.1
Cramerovým pravidlem vyřešíme soustavu tří lineárních rovnic o třech neznámých
.622
13
34
321
321
321
xxx
xxx
xxx
Řešení
Determinant matice soustavy je
.282412382
212
113
141
Protože je 0det A , je matice soustavy regulární, soustava má právě jedno řešení a můžeme
použít Cramerovo pravidlo.
Postupně vypočítáme
.567216986
612
113
341
det
,018621862
262
113
131
det
,288361246
216
111
143
det
3
2
1
A
A
A
Podle věty 4.4.1 je tedy řešením dané soustavy vektor
.)2,0,1(28
56,
28
0,
28
28 T
T
x
39
Výhodou řešení soustav lineárních rovnic pomocí Cramerova pravidla je možnost explicitního
vyjádření každé složky řešení pomocí prvků příslušné rozšířené matice soustavy a také
skutečnost, že je možné vypočítat libovolnou složku řešení nezávisle na ostatních. Cramerovo
pravidlo je rovněž vhodné pro řešení soustav lineárních rovnic s parametry, jak demonstruje
následující příklad.
Příklad 4.4.2
Určíme, pro které hodnoty reálného parametru má soustava rovnic
321
321
321
4
322
21
xxx
xxx
xxx
právě jedno řešení a toto řešení vyjádříme.
Řešení
V tomto případě je det A funkcí parametru . Konkrétně
.2418122124
411
122
111
det
A
Soustava má tedy právě jedno řešení právě když 2
1 . V tom případě je totiž 0det A ,
matice soustavy je regulární a lze použít Cramerovo pravidlo. Dále máme
,31632212
41
132
121
det
,53112223128
41
123
112
det
2
1
A
A
.2123224132
11
322
211
det 23
A
Je tedy pro 2
1
.24
2,
24
3,
24
53T
2
x
V případě, že 2
1 , dostaneme soustavu rovnic, která podle věty 4.2.2 nemá právě jedno
řešení. Postupy při řešení takovýchto soustav se budeme zabývat v dalších odstavcích.
40
4.5 Gaussova metoda řešení soustav lineárních rovnic
Věta 4.5.1
Množina všech řešení soustavy lineárních rovnic (4.1.1) se nezmění, jestliže provedeme
některou z následujících úprav této soustavy:
1) vyměníme libovolné dvě rovnice soustavy;
2) libovolnou rovnici soustavy vynásobíme libovolným nenulovým reálným číslem;
3) k libovolné rovnici přičteme libovolnou lineární kombinaci ostatních rovnic soustavy;
4) vynecháme rovnici, která je lineární kombinací ostatních rovnic soustavy.
Věta 4.5.1 spolu se znalostí postupu při určování hodnosti matice nám dává návod, jakým
způsobem lze postupovat při řešení dané soustavy lineárních rovnic. Nejprve sestavíme
rozšířenou matici dané soustavy lineárních rovnic. Pomocí řádkových úprav převedeme tuto
matici (pokud je to možné) na lichoběžníkový tvar. Z tohoto tvaru určíme hr i h, a tudíž i
počet řešení dané soustavy. V tomto stadiu výpočtu přejdeme od matice (která určuje
soustavu lineárních rovnic se stejnou množinou řešení jako má daná soustava) zpět k soustavě
rovnic a „odzadu“ ji postupným dosazováním snadno vyřešíme.
Může nastat situace, kdy k úpravě na lichoběžníkový tvar bude zapotřebí v závěrečné fázi
změnit pořadí sloupců v matici nebo nám záměna pořadí sloupců podstatně usnadní výpočet.
Jelikož by to však znamenalo stejnou záměnu pořadí neznámých a poslední sloupec (sloupec
pravých stran) navíc stejně musí zůstat na svém místě, je lepší určit hodnosti obou matic
pomocí pouhé ‚představy‘ výsledného lichoběžníkového tvaru a záměnu sloupců fakticky
neprovádět. Postup při dokončení řešení je už potom analogický.
Příklad 4.5.1
Vyřešíme soustavu
22
542
33
2
321
321
x
xxx
xxx
.
Řešení
Nejprve sestavíme příslušnou rozšířenou matici soustavy. Potom násobíme první řádek (-2) a
přičteme ke 2. řádku.
.
2020
1670
3131
2020
5412
3131
rA
Tím získáme tvar, který sice není lichoběžníkový, ale lze si snadno domyslet, jak bychom se
k němu dostali (výměna druhého a třetího sloupce) a jak by vypadal. Je tedy zřejmé, že
v tomto případě platí hr = h = n = 3. Soustava má tudíž právě jedno řešení. To nalezneme tak,
že přejdeme od řádků matice zpět k rovnicím. Poslední řádek odpovídá rovnici
22 2 x ,
tedy x2 = 1. To dosadíme do druhé rovnice a dostaneme, že x3 = 1. Dosazením do první
rovnice vyjde rovněž x1 = 1. Řešením dané soustavy je tudíž vektor .1,1,1T
x
41
Příklad 4.5.2
Gaussovou eliminační metodou vyřešíme soustavu lineárních rovnic
572
132
232
421
431
4321
xxx
xxx
xxxx
.
Řešení
Podobně jako v řešení předešlého příkladu máme
.
20000
610220
57021
815330
610220
57021
21312
13201
57021
57021
13201
21312
rA
Z poslední matice je zřejmé, že h = 2, zatímco hr = 3. Daná soustava tedy podle Frobeniovy
věty nemá řešení. Tato skutečnost je zřejmá i z posledního řádku poslední matice, který
odpovídá rovnici 0 = 2.
Příklad 4.5.3
Gaussovou eliminační metodou vyřešíme soustavu lineárních rovnic
132
145
5534
232
4321
431
4321
4321
xxxx
xxx
xxxx
xxxx
Řešení
Opět vyjdeme z rozšířené matice soustavy a pomocí úprav neměnících množinu všech řešení
soustavy (viz věta 4.5.1) budeme postupně získávat lichoběžníkový tvar. Dostáváme
37710
23211
37710
37710
37710
23211
11312
14501
55134
23211
rA .
Je zřejmé, že hodnost matice soustavy h = 2, hodnost rozšířené matice soustavy hr je také 2.
Je tedy splněna podmínka Frobeniovy věty a řešení dané soustavy existuje. Jelikož je navíc
n = 4, má soustava podle věty 4.2.2 nekonečně mnoho řešení, přičemž za dvě neznámé
(n – h = 2) můžeme volit libovolná reálná čísla. Všechna řešení nalezneme ze soustavy
377
232
432
4321
xxx
xxxx,
která má podle věty 4.5.1 stejnou množinu řešení jako soustava ze zadání. Jako nejjednodušší
se ukazuje vyjádřit všechny neznámé pomocí x3 a x4. Z druhé rovnice dostaneme
42
432 773 xxx
a po dosazení do první rovnice, vyjádření x1 a upravení získáme
431 451 xxx .
Všechna řešení dané soustavy tedy můžeme zapsat pomocí lineární kombinace vektorů.
.,kde,)1,0,7,4()0,1,7,5()0,0,3,1(
),,773,451(
43T
4T
3T
T434343
Rxxxx
xxxxxx
x (4.5.1)
Zaveďme nyní několik pojmů, které souvisejí s řešením soustav majících nekonečně mnoho
řešení.
Definice 4.5.1
Nechť má soustava (4.1.1) nekonečně mnoho řešení. Vztah, ve kterém jsou explicitně
vyjádřena všechna řešení dané soustavy, se nazývá obecné řešení soustavy.
Definice 4.5.2
Nechť má soustava (4.1.1) nekonečně mnoho řešení. Proměnné (neznámé), pomocí nichž je
vyjádřeno obecné řešení soustavy, se nazývají nezákladní proměnné, zbývající proměnné
soustavy se nazývají základní proměnné.
Definice 4.5.3
Nechť má soustava (4.1.1) nekonečně mnoho řešení. Dosazením konkrétních reálných čísel za
nezákladní proměnné do obecného řešení této soustavy získáme jedno řešení soustavy, které
nazýváme partikulární řešení soustavy.
Definice 4.5.4
Nechť má soustava (4.1.1) nekonečně mnoho řešení. Takové partikulární řešení této soustavy,
ve kterém jsou všechny nezákladní proměnné rovny nule, se nazývá základní řešení soustavy.
Definice 4.5.5
Nechť má soustava (4.1.1) nekonečně mnoho řešení. Takové základní řešení této soustavy, ve
kterém je alespoň jedna základní proměnná rovna nule, se nazývá degenerované základní
řešení soustavy.
Příklad 4.5.4
Určíme obecné řešení, dvě partikulární (nezákladní) řešení a základní řešení soustavy
z příkladu 4.5.3.
Řešení
Obecným řešením jsou podle definice 4.5.1 oba tvary zápisu (4.5.1).
Pro získání partikulárních řešení, označme je 21, xx , dosaďme postupně x3 = 1, x4 = 1 a
x3 = 0, x4 = 1. Dosazením do (4.5.1) máme
.)1,0,4,3(,)1,1,3,2( T2
T1 xx
Základní řešení, označme je řekněme 1zx , dostaneme podle definice 4.5.4 tak, že dosadíme
v (4.5.1) 043 xx . Máme
43
T1 )0,0,3,1(zx .
Toto řešení není degenerované, protože obě základní proměnné 21, xx jsou v něm různé od
nuly.
Pozn.
Je zřejmé, že vyjádření obecného řešení (4.5.1) není jediným možným. Pokud bychom zvolili
při řešení příkladu 4.5.3 jinou dvojici nezákladních proměnných (např. 21, xx ), dostaneme
obecné řešení dané soustavy vyjádřené jinou lineární kombinací vektorů (přirozeně za
předpokladu, že bude možné zapsat 43 , xx pomocí 21, xx ). Platí zde tedy, že maximální
počet různých možností vyjádření obecného řešení je tolik, kolik existuje různých způsobů
výběru dvou prvků ze čtyřprvkové množiny. Z kombinatoriky víme, že tento počet je
vyjádřen kombinačním číslem .61212
1234
!2)!24(
!4
2
4
Je také zřejmé, že každému
vyjádření obecného řešení odpovídá právě jedno základní řešení. Platí tedy následující věta.
Věta 4.5.2
Nechť má soustava (4.1.1) nekonečně mnoho řešení. Potom existuje nanejvýš
!!
!
hhn
n
hn
n
základních řešení této soustavy.
4.6 Jordanova metoda řešení soustav lineárních rovnic
Definice 4.6.1
Jestliže lze ze sloupců matice soustavy (4.1.1) sestavit jednotkovou matici, říkáme, že tato
soustava je v kanonickém tvaru.
Jordanova metoda spočívá v tom, že pomocí řádkových úprav, které nemění hodnost matice
(a tedy ani množinu všech řešení odpovídajících soustav lineárních rovnic), upravíme matici
soustavy (4.1.1) na kanonický tvar. Takto upravené matici odpovídá soustava, jejíž řešení je
zřejmé a je možné jej okamžitě zapsat, aniž bychom přecházeli zpět k rovnicím.
Příklad 4.6.1
Jordanovou metodou řešení soustav lineárních rovnic nalezneme řešení soustavy
03
7324
332
23
4321
4321
4321
4321
xxxx
xxxx
xxxx
xxxx
.
Řešení
Opět budeme nejprve upravovat rozšířenou matici soustavy řádkovými úpravami podle věty
4.5.1 do lichoběžníkového tvaru. Postupně máme
44
.
41000
10100
50410
21131
~
5014600
10100
50410
21131
~
20200
5014600
50410
21131
~
~
20200
1516130
50410
21131
~
01131
73214
31321
21131
rA
Protože h = hr = n = 4, má soustava právě jedno řešení. Dosavadní postup se nelišil od
Gaussovy eliminační metody. Podle ní bychom se vrátili zpět k rovnicím a „odspodu“
soustavu dořešili. Při Jordanově metodě budeme pokračovat v nulování prvků nad hlavní
diagonálou. Máme
.
41000
10100
10010
20001
~
41000
10100
10010
20001
~
41000
10100
10010
50031
~
~
41000
10100
50410
60131
~
41000
10100
50410
21131
Poslední matice odpovídá soustavě v kanonickém tvaru (viz definice 4.6.1)
4
1
1
2
4
3
2
1
x
x
x
x
.
Po této tzv. úplné eliminaci dostáváme přímo řešení
T)4,1,1,2( x .
Příklad 4.6.2
Jordanovou metodou nalezneme obecné a všechna základní řešení soustavy
1
742
32
321
xx
xxx.
Řešení
Dané soustavě přiřadíme rozšířenou matici soustavy a vynulujeme prvky pod i nad hlavní
diagonálou
.1110
5201
1110
7421
rA
45
Je zřejmé, že hodnost rozšířené matice soustavy hr = 2, hodnost matice soustavy h = 2, počet
neznámých n = 3. Z věty 4.2.2 vyplývá, že soustava má nekonečně mnoho řešení, přičemž
jedna neznámá je volitelná. Dále je zřejmé, že zvolíme-li za volitelnou neznámou x3 (podle
definice 4.5.2 v tomto okamžiku nezákladní proměnná), můžeme přímo z výsledného tvaru
poslední matice zapsat obecné řešení a příslušné základní řešení (viz poslední sloupec).
Obecné řešení je
Rxxxxx 3T
3TT
333 kde,)1,1,2()0,1,5(,1,25x
a základní
.)0,1,5( T1 zx
Zvolme nyní za volitelnou neznámou nezákladní proměnnou x2. Jedna z možností (obvykle
užívaná), jak nalézt odpovídající základní řešení, je upravit matici tak, aby jednotkové vektory
(1, 0) a (0, 1), které jsou současně v prvním a druhém sloupci, byly ve sloupcích základních
proměnných, tedy v prvním a třetím. Jedná se opět o kanonický tvar soustavy, u něhož lze
z posledního sloupce matice vyčíst příslušné základní řešení. Připomeňme, že u základního
řešení je nezákladní proměnná rovna nule.
.1110
3021
1110
5201
1110
5201
Další základní řešení je tedy
.)1,0,3( T2 zx
Poslední možností volby nezákladní proměnné je x1. Opět se budeme snažit upravit matici tak,
aby jednotkové vektory byly ve sloupcích zbývajících proměnných, tj. ve druhém a ve třetím.
.10
01
1110
01
1110
3021
25
21
23
21
23
21
Poslední základní řešení má tedy tvar
.2
5,
2
3,0
T
3
zx
Ani jedno ze základních řešení není podle definice 4.5.5 degenerované.
Podle věty 4.5.2 je v tomto případě maximální počet základních řešení roven ,32
3
což
výsledek potvrzuje.
Cvičení
4.1 Řešte soustavu
.1523
3
7232
532
4321
4321
4321
4321
xxxx
xxxx
xxxx
xxxx
46
4.2 Řešte soustavu
.6
1
5
1
4
1
3
1
5
1
4
1
3
1
2
1
4
1
3
1
2
1
321
321
321
xxx
xxx
xxx
4.3 Řešte soustavu s parametrem
.3612
393
163
321
321
321
xxx
xxx
xxx
4.4 Nalezněte všechna základní řešení z příkladu 4.5.3.
4.5 Nalezněte obecné a všechna základní řešení soustavy
.2441815
1631210
8265
321
321
321
xxx
xxx
xxx
4.6 Nalezněte obecné a všechna základní řešení soustavy
.7682
4542
233
433
4321
4321
4321
4321
xxxx
xxxx
xxxx
xxxx
4.7 Řešte soustavu
.3452
733234
232
043
1232
54321
54321
5432
5431
54321
xxxxx
xxxxx
xxxx
xxxx
xxxxx
47
4.8 Řešte soustavu
.32252
923
1275
8222
4324
54321
54321
521
5421
54321
xxxxx
xxxxx
xxx
xxxx
xxxxx
4.9 Čtyři kamarádi strávili večer v jedné pivovarské hospůdce, kde v různé míře ochutnávali
čtyři druhy piv, které vyrábí příslušný pivovar. Jednalo se o šestnáctku, čtrnáctku,
dvanáctku a desítku. Když dopili, zaplatili a vyšli ven, uvědomili si, že vlastně nevědí,
kolik který druh piva stojí. Pamatovali si, že společně začali tím, že ochutnali od
každého druhu jedno pivo. Jirka si vzpomněl, že dál vypil dvě dvanáctky a účet zněl na
145Kč. Aleš si dal ještě jednu šestnáctku a platil 134Kč. Mirek vypil po ochutnávce
ještě tři čtrnáctky a jeho útrata činila 179Kč. Konečně Pavel pil potom už jenom desítky,
ty si dal ještě čtyři a platil 181Kč. Jaká cena byla účtována za jednotlivé druhy piva?
48
5. Soustavy lineárních nerovnic
5.1 Základní pojmy
Definice 5.1.1
Soustavou m lineárních nerovnic o n neznámých (proměnných) ;,..., 21 Rxxx n Nnm ,
rozumíme soustavu
....
.................................................
...
...
2211
22222121
11212111
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
(5.1.1)
Reálná čísla aij, kde mi ...,,2,1 a ,...,,2,1 nj se nazývají koeficienty a reálná čísla ,ib
,...,,2,1 mi se nazývají pravé strany.
Pozn.
1) Maticově lze soustavu nerovnic z předchozí definice zapsat jako
bAx , (5.1.2)
kde
mnmm
n
n
aaa
aaa
aaa
...
............
...
...
21
22221
11211
A
a
T21 )...,,,( mbbbb .
2) Všechny nerovnice v (5.1.1) jsou typu „ “. Je zřejmé, že pod pojmem soustava lineárních
nerovnic je obecně možné představit si i soustavu, která bude obsahovat také nerovnice
zbývajících typů, tedy „ “, „<“ a „>“.
5.2 Algebraické řešení soustav lineárních nerovnic
Soustavu lineárních nerovnic lze řešit převedením na soustavu lineárních rovnic. Každou
nerovnici soustavy (5.1.1) lze totiž převést (vyrovnat) na rovnici tak, že k její levé straně
přičteme další nezápornou proměnnou. Jestliže má tedy i-tá nerovnice soustavy tvar
ai1x1 + ai2x2 + ... + ainxn bi , (5.1.3)
lze ji nahradit rovnicí
ai1x1 + ai2x2 + ... + ainxn+ xn+i = bi , (5.1.4)
kde xn+i 0.
49
Je zřejmé, že množina řešení nerovnice (5.1.3) se rovná množině, která vznikne z množiny
řešení rovnice (5.1.4) odstraněním posledních souřadnic příslušných vektorů. Rovněž je
zřejmé, že ony odstraněné poslední souřadnice ukazují, o kolik je v příslušném řešení
nerovnice (5.1.3) levá strana menší než pravá.
Definice 5.2.1
Soustavu m lineárních rovnic o (n + m) neznámých (proměnných) ,,...,, 21 Rxxx n
,,...,, 021
Rxxx mnnn Nnm ,
mmnnmnmm
nnn
nnn
bxxaxaxa
bxxaxaxa
bxxaxaxa
...
..................................................................................
...
...
2211
222222121
111212111
(5.2.1)
nazýváme přidružená soustava rovnic k soustavě (5.1.1). Proměnné mnnn xxx ,..., 21
nazýváme přídatné (doplňkové) proměnné.
Pozn.
Pro nerovnici typu „<“ nabývá příslušná přídatná proměnná pouze kladných hodnot a
nerovnici typu „ “(„>“) převedeme na rovnici tak, že přídatnou proměnnou odečteme od její
levé strany. Dostaneme rovnici
ai1x1 + ai2x2 + ... + ainxn - xn+i = bi ,
přičemž je opět xn+i 0 (xn+i > 0).
Příklad 5.2.1
Vyřešíme soustavu
.223
422
12
321
321
321
xxx
xxx
xxx
Řešení
Nejprve sestavíme přidruženou soustavu rovnic
223
422
12
6321
5321
4321
xxxx
xxxx
xxxx
,
kde pro přídatné proměnné platí, že x4, x5, x6 0.
Tuto soustavu rovnic vyřešíme Jordanovou metodou úplné eliminace (přirozeně se
snažíme, aby mezi základními proměnnými byly původní proměnné, tj. x1, x2, x3).
3111100
2012610
3011401
1103710
2012610
1001211
2100123
4010212
1001211
50
.
3111100
20674010
15453001
3111100
20674010
15453001
Vektor obecného řešení přidružené soustavy rovnic tedy je
0,,
,;;;3;67420;45315
654
T
654654654654R
xxx
xxxxxxxxxxxxx
a vektor obecného řešení soustavy nerovnic je:
.0,,,3;67420;45315 654
T
654654654N xxxxxxxxxxxxx
Z porovnání je zřejmé, že matice soustavy (5.2.1) je speciálním případem matice soustavy m
lineárních rovnic o (n + m) proměnných ve smyslu definice (4.1.1). Dále upozorněme, že u
soustavy (5.2.1) je oborem některých proměnných (těch přídatných) pouze množina
nezáporných reálných čísel. Podle poznámky za definicí 5.2.1 může nastat případ, kdy některé
přídatné proměnné mohou nabývat jen kladných hodnot. V dalších kapitolách se dokonce
setkáme se soustavami rovnic, ve kterých i proměnné, které nejsou přídatné, nemohou
nabývat libovolných reálných hodnot. Pochopitelným důsledkem těchto skutečností je to, že
se mezi základními řešeními příslušné soustavy (viz definici 4.5.4) mohou objevit i taková,
jejichž jedna nebo více složek nepatří do oboru odpovídající proměnné. Proto následující
definice.
Definice 5.2.2
Nechť má soustava m lineárních rovnic o n proměnných nekonečně mnoho řešení. Přípustným
řešením soustavy nazýváme takové její řešení, ve kterém jsou všechny složky z daného oboru
odpovídající proměnné.
Příklad 5.2.2
Určíme maximální počet základních řešení přidružené soustavy rovnic (přípustných nebo
nepřípustných) z příkladu 5.2.1 a nalezneme tři z těchto základních řešení.
Řešení
Podle věty 4.5.2 máme
.20
23
456
!3!36
!6
!!
!
hhn
n
hn
n
Tedy přidružená soustava rovnic z příkladu 5.2.1 má nanejvýš 20 základních řešení. Dále je
z řešení tohoto příkladu zřejmé, že
.
3111100
20674010
15453001
1103710
2012610
1001211
2100123
4010212
1001211
2100123
4010212
1001211
51
Protože poslední tři matice vesměs odpovídají kanonickému tvaru příslušné soustavy rovnic,
můžeme z nich základní řešení postupně přečíst. Máme
.)0,0,0,3,20,15(
,)1,2,0,0,0,1(
,)2,4,1,0,0,0(
T3
T2
T1
z
z
z
x
x
x
Je zřejmé, že první dvě základní řešení nejsou přípustná (má být x4, x5, x6 0), zatímco třetí
základní řešení je přípustné základní řešení.
5.3 Grafické řešení soustav lineárních nerovnic
Sluší se poznamenat (a z řešení příkladu 5.2.1 je to i dobře patrné), že v některých případech
je obecné řešení soustavy nerovnic spolu s omezeními volitelných proměnných značně
komplikované. Přehledně lze vyjádřit množinu všech řešení soustavy m lineárních nerovnic o
dvou neznámých graficky. V tomto případě se jedná o průnik m polorovin v rovině (u ostrých
nerovnic nepatří k polorovině hraniční přímka).
Příklad 5.3.1
Vyřešíme graficky soustavu
.72
02
1553
63
1
21
21
21
21
21
xx
xx
xx
xx
xx
Řešení
Převedeme nerovnice, pokud to bude možné, na tzv. úsekový tvar:
.17
2
7
02
135
126
111
21
21
21
21
21
xx
xx
xx
xx
xx
Z tohoto zápisu jsou dobře vidět „úseky“, které vytínají hraniční přímky daných polorovin na
souřadnicových osách (hraniční přímka poloroviny, která odpovídá čtvrté nerovnici, prochází
počátkem soustavy souřadnic). Orientaci poloroviny určíme zjištěním, zda vybraný bod
(pokud možno, nejlépe [0,0]) leží či neleží ve vnitřní oblasti příslušné poloroviny.
52
Obrázek 5.3.1 Grafické řešení soustavy nerovnic
Řešením dané soustavy je pětiúhelník ABCDE bez hrany BC. Souřadnice vrcholů
pětiúhelníku lze dopočítat vyřešením soustav dvou rovnic o dvou neznámých. např. A:
.63
02
21
21
xx
xx
Jednoduchým výpočtem zjistíme, že
.7
51,
7
6A tj.,
7
12,
7
621
xx
Podobně určíme souřadnice zbývajících vrcholů. Postupně dostaneme:
.3
2,
3
1E a
4
12,
4
11D,
7
21,
7
62C,
7
5,
7
63B
-
Příklad 5.3.2
Nalezneme taková základní řešení soustavy rovnic přidružené k soustavě nerovnic z příkladu
5.3.1, ve kterých jsou 1x a 2x mezi základními proměnnými.
Řešení
Příslušná přidružená soustava rovnic je zřejmě
,72
02
1553
63
1
721
621
521
421
321
xxx
xxx
xxx
xxx
xxx
53
kde .,,,, 706543
RxRxxxx
Podle podmínky v zadání hledáme takové tvary rozšířené matice sestavené přidružené
soustavy, ve kterých jsou jednotkové vektory v prvních dvou sloupcích. Dále, s využitím věty
4.5.2, je takových řešení nanejvýš .102
45
2
5
2
27
Vyzbrojeni Jordanovou
metodou úplné eliminace a značnou dávkou trpělivosti postupně máme
71100000
72011000
00100
00010
00001
71100000
72011000
00100
00010
00001
71100000
601000
00100
300010
200001
71100000
601000
1300100
300010
200001
71100000
01000
00100
00010
00001
10000
01000
00100
00010
00001
10000
01000
00100
00010
00001
10000
01000
00100
00010
00001
10000
01000
460014700
00010
00001
91000230
20100230
180010380
00010
10000111
91000230
20100230
180010380
70001120
10000111
71000012
00100012
150010053
60001031
10000111
718
78
73
79
73
72
720
75
71
739
72
73
75
71
72
727
73
71
38
37
739
72
73
31
32
31
31
38
37
32
37
31
32
31
31
338
38
37
325
32
37
32
31
32
31
31
31
49
83
87
338
38
37
223
41
47
49
81
83
45
81
85
49
83
87
419
83
87
223
41
47
49
81
83
45
81
85
239
23
27
225
23
27
223
41
47
27
21
21
29
21
23
239
23
27
225
23
27
27
21
21
29
21
23
27
21
21
54
.
10000
01000
00100
00010
00001
71100000
01000
00100
00010
00001
71100000
210211000
00100
00010
00001
71100000
210211000
00100
00010
00001
27
21
21
221
21
21
746
71
74
143
141
143
1475
143
145
221
21
21
725
72
73
712
71
72
76
73
71
725
72
73
712
71
72
76
73
71
738
78
73
730
73
72
715
75
71
Dostáváme tedy:
.2
7,
2
21,0,0,
7
46,
14
3,
14
75
,7,0,21,0,7
25,
7
12,
7
6
,7,0,0,21,7
38,
7
30,
7
15
,0,7,0,7,7
18,
7
9,
7
20
,0,7,7,0,7
39,
7
5,
7
27
,0,7,6,13,0,3,2
,7,0,3
38,
3
25,0,
3
2,
3
1
,4
9,
4
19,0,
2
23,0,
4
9,
4
5
,2
39,
2
25,46,0,0,
2
7,
2
9
T
9
T
8
T
7
T
6
T
5
T
4
T
3
T
2
T
1
z
z
z
z
z
z
z
z
z
x
x
x
x
x
x
x
x
x
Povšimněme si, že první dvě souřadnice uvedených vektorů odpovídají souřadnicím
průsečíků hraničních přímek v grafickém řešení příkladu 5.3.1. Desáté základní řešení
neexistuje, jelikož příslušné hraniční přímky jsou rovnoběžné. Dále je zřejmé, že přípustná
základní řešení jsou pouze ).Abod(a)Ebod(),Dbod( 832 zzz xxx
55
Cvičení
5.1 Řešte soustavu
.04
23
321
31
xxx
xx
5.2 Řešte soustavu
.132
2
12
21
31
321
xx
xx
xxx
5.3 Řešte graficky soustavu
.0
0
453
5649
1023
2
1
21
21
21
x
x
xx
xx
xx
5.4 Řešte graficky soustavu
.0
0
62
1025
1523
323
2
1
21
21
21
21
x
x
xx
xx
xx
xx
5.5 Řešte graficky soustavu
.0
0
3
3
45
826
4
2
1
2
1
21
21
21
x
x
x
x
xx
xx
xx
56
5.6 Řešte graficky soustavu
.0
0
2872
3065
4
2
1
21
21
21
x
x
xx
xx
xx
57
6. Lineární programování
Jednou z oblastí, ve které lze úspěšně aplikovat dosud popsané matematické poznatky, je
oblast ekonomie a řízení. Speciální matematické metody, používané při řešení problémů
z těchto oblastí, se ve světové literatuře nazývají metodami operačního výzkumu (anglickým
ekvivalentem tohoto označení je Operations research nebo též Management science).
Uvedený název souvisí s tím, že k rozvoji těchto metod došlo za 2. světové války při analýze
a řešení složitých vojenských problémů a operací. Postupem času vznikla řada relativně
samostatných disciplín operačního výzkumu, vyznačujících se některými společnými rysy,
např. používáním modelové techniky.
Modelování spočívá v tom, že se jeden systém (originál) zobrazuje jiným systémem
(modelem). Výsledkem modelování je model, který představuje záměrně zjednodušený obraz
podstatných znaků reality za účelem jejího poznání. Jsou-li zobrazovací prostředky
matematické povahy (např. rovnice, nerovnice, matice), jde o matematický model, který je
v operačním výzkumu nejčastější.
Význam matematického modelování spočívá v tom, že
umožňuje popis systému v jakémkoliv jeho stavu, třeba i teprve zamýšleném;
urychluje chování systému, které by ve skutečnosti trvalo velmi dlouho;
umožňuje rychle vyhodnotit změny vzniklé v důsledku změn v modelovaném
systému, a to – na rozdíl od experimentu v reálném systému – bez nebezpečí
jakýchkoliv ztrát;
za pomoci výpočetní techniky umožňuje rychlé řešení i rozsáhlých problémů;
vnáší pořádek do našeho myšlení tím, že vyžaduje jasnou formulaci řešeného
problému.
K nejpoužívanějším a nejvíce propracovaným metodám operačního výzkumu patří
lineární programování, jehož metody umožňují řešení speciální skupiny optimalizačních
úloh. Lineární programování je zaměřeno na hledání optimálního (nejlepšího) řešení při
současném splnění daných podmínek. Podmínky jsou zapsány pomocí lineárních rovnic a
nerovnic. Kritérium optimálnosti je vyjádřeno lineární funkcí. Jsou tedy všechny vazby v
modelech lineárního programování vazbami lineárními. Slovo programování v názvu je pak
spíše synonymem pro plánování nebo vytváření programů (scénářů) budoucího vývoje.
V následujících odstavcích budeme obecně formulovat některé typické úlohy lineárního
programování v jejich základní podobě spolu s odpovídajícím obecným matematickým
modelem. Ke každému typu uvedeme i konkrétní příklady.
6.1 Úlohy výrobního plánování
Představme si, že výrobce má možnost vyrábět n různých výrobků, přičemž má k dispozici
omezenou kapacitu m zdrojů (pracovní síly, suroviny, strojové vybavení apod.). Přirozeně se
zajímá o to, jaké výrobky a v jaké míře má vyrábět, aby při respektování všech omezení
dosáhl např. maximálního zisku, minimální spotřeby energie atd.
Označme:
xj nj ...,,2,1 … vyráběné množství j-tého výrobku (tzv. strukturní neznámé);
bi mi ...,,2,1 … množství i-tého zdroje, které je k dispozici (tzv. požadavková čísla);
aij njmi ...,,2,1;,...,2,1 … množství i-tého zdroje potřebné k výrobě jednotkového
množství j-tého výrobku (tzv. strukturní koeficienty);
58
cj nj ...,,2,1 …ocenění jednotkového množství j-tého výrobku v souladu se zvoleným
kriteriem efektivnosti (tzv. cenové koeficienty).
Úlohou je tedy nalézt neznámé xj, které splňují podmínky
,...
.................................................
...
...
2211
22222121
11212111
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
(6.1.1)
njx j ...,,2,1,0 (6.1.2)
a současně maximalizují funkci
nnxcxcxcz ...2211 (6.1.3)
Maticově lze totéž zapsat v jednodušším tvaru:
max,
,
,
T
xc
ox
bAx
z
kde A je matice strukturních koeficientů typu m x n;
b je m-složkový sloupcový vektor požadavkových čísel;
cT
je n-složkový řádkový vektor cenových koeficientů;
o je n-složkový sloupcový nulový vektor.
Definice 6.1.1
Nerovnice (6.1.1) nazýváme vlastní omezení úlohy lineárního programování, nerovnice
(6.1.2) nazýváme podmínky nezápornosti a funkci (6.1.3) nazýváme účelová (kriteriální,
cílová) funkce.
Pozn.
V praxi se velmi často vyskytují úlohy, ve kterých hledáme pouze celočíselná řešení. Jejich
řešením se zabývá tzv. celočíselné lineární programování. My se obecným řešením
takovýchto úloh zabývat nebudeme (je složitější než řešení s podmínkami ve tvaru (6.1.2)) a
v dalším textu se omezíme pouze na řešení těch případů, kdy podmínky celočíselnosti
neovlivňují optimální řešení.
Při sestavování konkrétních matematických modelů úloh lineárního programování
postupujeme tak, že nejprve určíme, co má být výsledkem výpočtu, tzn. co představují složky
vektoru x a v jakých měrných jednotkách budou uváděny. Dále musíme rozhodnout, z jakého
hlediska budeme řešení dané úlohy optimalizovat, tzn. musíme zformulovat účelovou funkci,
a konečně musíme nejdříve věcně a potom též matematicky formulovat vlastní omezující
podmínky (pořadí formulace účelové funkce a omezujících podmínek můžeme zaměnit).
Příklad 6.1.1
Podnik vyrábí dva výrobky (A, B), které musí projít zpracováním na čtyřech strojích (S1, S2,
S3, S4), přičemž kapacita těchto strojů je pro dané období postupně 45, 100, 300 a 50 hodin.
K výrobě jednoho kilogramu výrobku A je zapotřebí pracovat 2 hodiny na S1, 4 hodiny na S2,
3 hodiny na S3 a hodinu na S4. Jeden kilogram výrobku B se vyrábí s využitím 15 minut práce
na S1, dvou hodin na S2, hodiny na S3 a čtyř hodin na S4. Cena hotových výrobků A, B je
59
600Kč, resp. 400Kč za 1kg. Je třeba naplánovat jejich výrobu tak, aby celková cena produkce
byla maximální. Sestavíme matematický model této úlohy.
Řešení
Nejprve sestavíme tabulku s přehledným uvedením všech údajů.
Tabulka 6.1.1
A (kg) B (kg) Disponibilní množství (hod)
S1 (hod) 2 0,25 45
S2 (hod) 4 2 100
S3 (hod) 3 1 300
S4 (hod) 1 4 50
Cena (Kč/kg) 600 400 MAX
Nechť je x1 (x2) hmotnost vyráběných výrobků A (B) v kilogramech. Celkovou cenu výroby
pak můžeme vyjádřit jako součet ceny x1 kg výrobku A, tj. 600x1, a ceny x2 kg výrobku B, tj.
400x2. Platí tedy, že celková cena výroby je
.400600 21 xx
Jelikož nemáme k dispozici neomezené množství pracovního času na S1 (stejně jako na
ostatních strojích), je třeba, aby doba potřebná k vyrobení x1 kg výrobku A na tomto stroji, tj.
2x1, spolu s 0,25x2 (tj. dobou potřebnou k výrobě x2 kg výrobku B) nepřesáhla 45 hodin,
čemuž odpovídá nerovnice
.454
12 21 xx
Podobně získáme tři další podmínky (nerovnice) pro ostatní tři strojová zařízení.
Nakonec je třeba, abychom si uvědomili, že vzhledem k významu neznámých x1, x2
nemohou být tyto záporné.
Hledáme tedy hodnoty x1 a x2 tak, aby účelová funkce (celková cena produkce)
21 400600 xxz
byla při splnění podmínek
0
0
504
3003
10024
454
12
2
1
21
21
21
21
x
x
xx
xx
xx
xx
maximální.
Často se v praxi setkáváme s úlohami výrobního plánování, ve kterých existují navíc další
podmínky kromě těch uvedených v obecném matematickém modelu. Není například
neobvyklé, že se některé výrobky mohou prodávat buď samostatně, nebo sloužit jako
polotovar či součást výrobku jiného. Může se dále stát, že určitého výrobku je třeba
60
z nějakého důvodu vyrobit alespoň určité množství atd. Následující příklad ukazuje, ze i při
těchto „komplikacích“ lze matematický model relativně snadno sestavit.
Příklad 6.1.2
Nábytkářská firma vyrábí dva druhy stolů (S1, S2) a židle (Z). Při produkci je omezena
disponibilním množstvím desek (v období, pro které firma plánuje výrobu, bude k dispozici
800 běžných metrů desek) a omezenými pracovními možnostmi dělníků (v uvažovaném
období bude kapacita pracovní doby 1 240 hodin). Spotřeba uvedených zdrojů na jednotlivé
výrobky je zapsána v tabulce 6.1.2, stejně jako tržba z prodeje jednoho výrobku.
Tabulka 6.1.2
S1 (ks) S2 (ks) Z (ks)
Desky (bm) 4 3 1
Ruční práce (hod) 6 4 2
Tržba (Kč/ks) 8 000 7 500 1 800
Kromě uvedených výrobků může firma prodávat komplety obsahující jeden stůl typu S1 a
čtyři židle. Tržba z prodeje tohoto kompletu činí 14 900Kč, přičemž vzhledem k poptávce je
zapotřebí nabídnout těchto kompletů alespoň 20.
Je třeba určit takové množství prodávaných výrobků a kompletů, které firmě zajistí
maximální tržbu. Sestavíme matematický model této úlohy.
Řešení
V matematické formulaci uvedené úlohy budou 4 strukturní proměnné, a to
x1 ………..počet stolů typu S1;
x2 ………. počet stolů typu S2;
x3 ………. počet židlí;
x4 ………. počet kompletů.
Omezující podmínky jsou dány:
(a) vztahem mezi disponibilním množstvím výrobních zdrojů (tj. desek a ruční práce) a jejich
spotřebou:
2401246
80034
321
321
xxx
xxx
(b) vztahem mezi počtem stolů typu S1 a počtem židlí a mezi počtem kompletů:
43
41
4xx
xx
(c) požadavkem na minimální počet kompletů
204 x
Všechny uvedené proměnné musí být nezáporné (xj ≥ 0 pro j =1, 2, 3, 4) a celočíselné.
V účelové funkci bude vyjádřen požadavek na maximalizaci tržeb, přičemž je třeba
uvážit, že se budou prodávat pouze ty stoly typu S1 a ty židle, které nebudou součástí
kompletů. Bude tedy platit
z = 8 000(x1 - x4) + 7 500x2 + 1 800(x3 - 4x4) + 14 900x4→ max.
Po úpravě účelové funkce a vlastních omezujících podmínek (b) dostáváme matematický
model daného příkladu ve tvaru
61
20
04
0
2401246
80034
4
43
41
321
321
x
xx
xx
xxx
xxx
0Nx j pro j =1, 2, 3, 4
a
z = 8 000x1 + 7 500x2 + 1 800x3 - 300x4 → max.
6.2 Směšovací úlohy
V těchto úlohách jde o to navrhnout směs požadovaných vlastností tak, aby bylo
optimalizováno zvolené kritérium (např. aby se minimalizovaly náklady na vytvoření směsi).
Uvažujme n komponent, ze kterých má být vytvořena směs, jež má obsahovat m
sledovaných látek v dostatečném množství. Otázka zní: Které komponenty a v jakém
množství použít při sestavování směsi tak, aby její vybraná charakteristika byla nejlepší?
Označme:
xj nj ...,,2,1 … množství j-té komponenty ve směsi;
bi mi ...,,2,1 … minimální požadované množství i-té látky ve směsi;
aij njmi ...,,2,1;,...,2,1 …množství i-té látky v jednotkovém množství j-té
komponenty;
cj nj ...,,2,1 …ocenění jednotkového množství j-té komponenty v souladu se zvoleným
kriteriem efektivnosti.
Úlohou je tedy nalézt neznámé xj, které splňují podmínky
,...
.................................................
...
...
2211
22222121
11212111
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
njx j ...,,2,1,0
a současně minimalizují funkci
nnxcxcxcz ...2211
Maticově lze totéž zapsat v jednodušším tvaru:
min,
,
,
T
xc
ox
bAx
z
přičemž jednotlivé matice byly popsány již při formulaci obecného matematického modelu
úlohy výrobního plánování.
62
Příklad 6.2.1
Ze šesti druhů potravin (P1 až P6), které máme k dispozici, je třeba připravit denní jídelníček
tak, aby v něm bylo alespoň 3 000kcal využitelné energie, 70g bílkovin, 1,8mg vitamínu B a
75mg vitamínu C. V tabulce 6.2.1 jsou uvedeny údaje o obsahu účinných látek v jednotce
příslušného druhu potraviny, jakož i ceny jednotek potravin.
Tabulka 6.2.1
P1 (j) P2 (j) P3 (j) P4 (j) P5 (j) P6 (j)
Energie (kcal) 2 350 3 540 700 2 830 370 200
Bílkoviny(g) 61 67 16 216 - 25
Vitamin B (mg) 1,1 0,2 0,7 8,1 0,3 1,3
Vitamin C (mg) - - 100 - 600 630
Cena (Kč/j) 26 50 80 50 100 15
Sestavíme matematický model dané úlohy.
Řešení
Označíme xj 6...,,2,1j použité množství potraviny Pj v jídelníčku. Máme zřejmě nalézt
minimum funkce
654321 1510050805026 xxxxxxz
za podmínek
.0
75630600100
8,13,13,01,87,02,01,1
7025216166761
0003200370830270054033502
653
654321
64321
654321
jx
xxx
xxxxxx
xxxxx
xxxxxx
Mezi směšovací úlohy počítáme i problémy, ve kterých jsou podmínky stanoveny tak, že
vlastní omezení jsou i v jiném tvaru než ve dříve popsaném obecném modelu. Ukázkou toho
je i další příklad, ve kterém se jedná o „směs“ úvěrů s různou úrokovou sazbou.
Příklad 6.2.2
Banka plánuje poskytnout v běžném roce úvěry v maximální celkové výši 800 mil. Kč.
Poskytované úvěry jsou podle výše poskytnuté úrokové míry rozděleny do tří skupin (A, B,
C), přičemž úroková míra v těchto skupinách je postupně 12%, 14% a 17%. Rizikovost u
úvěrů je potom oceněna koeficienty 1, 2 a 4. Úlohou je maximalizovat čistý roční úrokový
výnos z poskytovaných úvěrů, přičemž ve třídě C má být maximálně 15% z celkově
poskytnutých úvěrů a ve třídě A naopak minimálně 20% z celkově poskytnutých úvěrů. Dále
je nutné, aby průměrná vážená míra rizika (vahami jsou půjčené částky) poskytnutých úvěrů
nebyla větší než 2. Sestavíme matematický model úlohy.
Řešení
Označíme množství bankou půjčených mil. Kč v jednotlivých skupinách A, B, C jako x1, x2 a
x3. Tentokrát máme zřejmě nalézt maximum funkce
321 17,014,012,0 xxxz
za podmínek (postupně podle zadání)
63
,3,2,1pro0
242
2,0
15,0
800
321
321
3211
3213
321
jx
xxx
xxx
xxxx
xxxx
xxx
j
neboli (po úpravě)
.3,2,1pro0
02
02,02,08,0
085,015,015,0
800
31
321
321
321
jx
xx
xxx
xxx
xxx
j
6.3 Úlohy o dělení materiálu
Představme si, že z dostatečného počtu kusů výchozího celku můžeme při n možnostech
dělení každého kusu získat jeho m různých menších částí v požadovaném množství s tím, že
dělení bude co nejracionálnější. Říkáme, že hledáme optimální řezný plán.
Označme:
xj nj ...,,2,1 … počet kusů výchozího celku rozděleného j-tým způsobem;
bi mi ...,,2,1 … minimální požadovaný počet kusů i-té části celku;
aij njmi ...,,2,1;,...,2,1 …počet kusů i-té části celku vznikající j-tým způsobem
dělení výchozího celku;
cj nj ...,,2,1 …ocenění j-tého dělení celku v souladu se zvoleným kriteriem efektivnosti.
Úlohou je tedy nalézt neznámé xj, které splňují podmínky
,...
.................................................
...
...
2211
22222121
11212111
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
njx j ...,,2,1,0
a současně minimalizují funkci
nnxcxcxcz ...2211
Maticově:
.min
,
,
T
xc
ox
bAx
z
64
Příklad 6.3.1
Podnik na výrobu železných konstrukcí potřebuje z dvoumetrových tyčí nařezat alespoň 52
tyčí délky 50cm a alespoň 18 tyčí délky 80cm. Jak má tyče řezat, aby získal požadovaný
počet kratších tyčí
a) s minimálním odpadem;
b) při minimálním počtu řezů;
c) při minimální spotřebě výchozích dvoumetrových tyčí.
Budeme vycházet z předpokladu, že způsoby řezání dvoumetrových tyčí s odpadem větším
než 20cm vůbec neuvažujeme.
Řešení
Před sestavením matematického modelu pro určení optimálního řezného plánu je nutné
stanovit všechny možné varianty řezání dvoumetrových tyčí na tyče délky 50cm a 80cm. Tyto
možnosti jsou uvedeny tabulce 6.3.1.
Tabulka 6.3.1
V1 V2
Délka 50cm 2 4
Délka 80cm 1 0
Odpad (cm) 20 0
Počet řezů 3 3
Neznámými veličinami xj v řešené úloze jsou počty dvoumetrových tyčí řezaných podle
varianty Vj, j = 1,2. Platí x1 ≥ 0, x2 ≥ 0, celočíselné.
Vlastní omezující podmínky úlohy vyjadřují
(i) požadavek na výrobu minimálně 52 tyčí délky 50cm:
2x1 + 4x2 ≥ 52;
(ii) požadavek na výrobu minimálně 18 tyčí délky 80cm:
x1 ≥ 18.
Pro každé ze zvolených kritérií formulujeme účelovou funkci:
a) minimalizace odpadu z1 = 20x1 → min.
b) minimalizace počtu řezů z2 = 3x1 + 3x2 → min.
c) minimalizace počtu výchozích tyčí z3 = x1 + x2 → min.
Velkou skupinu úloh lineárního programování tvoří tzv. dopravní úlohy, kterými se budeme
zabývat až později, protože tyto úlohy mají v porovnání s předcházejícími typy úloh poněkud
odlišnou strukturu.
6.4 Obecné vlastnosti řešení úloh lineárního programování
Z předchozích odstavců této kapitoly je zřejmé, že řešit úlohu lineárního programování
znamená obecně řešit soustavu m lineárních rovnic (v páté kapitole jsme ukázali, že každá
nerovnice může být pomocí přídatné proměnné nahrazena ekvivalentní rovnicí) o n
proměnných.
65
....
.................................................
...
...
2211
22222121
11212111
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
(6.4.1)
O soustavě rovnic (6.4.1) předpokládejme, že je tvořena nezávislými rovnicemi, tzn. že
hodnost matice soustavy těchto rovnic se rovná jejich počtu. Protože v úlohách lineárního
programování je počet proměnných vždy větší než počet rovnic (n > m), soustava má
nekonečně mnoho řešení (viz věta 4.2.2). Předpokládejme dále, že oborem každé z n
proměnných soustavy (6.4.1) je množina
0R , tedy že každé řešení soustavy (6.4.1)
s nezápornými složkami je přípustné.
Definice 6.4.1
Přípustné řešení soustavy (6.4.1), pro které účelová funkce (6.1.3) nabývá nejlepší, tj.
maximální nebo minimální hodnoty, se nazývá optimální řešení úlohy lineárního
programování.
Definice 6.4.2
Přípustné základní řešení soustavy (6.4.1) budeme nazývat základním řešením úlohy
lineárního programování.
Definice 6.4.3
Přípustné základní řešení soustavy (6.4.1), v němž počet kladných složek se rovná počtu
rovnic, se nazývá nedegenerované řešení. Je-li počet kladných složek menší než počet rovnic,
řešení je degenerované
Věta 6.4.1
Jsou-li x1 a x2 libovolná přípustná řešení soustavy (6.4.1), je i každý vektor x ve tvaru
,1,0kde,)1( 21 kkk xxx (6.4.2)
přípustným řešení soustavy (6.4.1).
Pozn.
Lineární kombinace vektorů x1, x2 ze vztahu (6.4.2) se nazývá konvexní lineární kombinace
vektorů x1, x2 a v dalším textu se sní ještě setkáme.
Věta 6.4.2
Počet přípustných základních řešení soustavy (6.4.1) je roven nejvýše číslu
!
! !
n n n
n m mn m m
Důkaz této věty plyne okamžitě z věty 4.5.2 a předchozí definice.
Věta 6.4.3 (tzv. základní věta lineárního programování)
Má-li úloha lineárního programování optimální řešení, má též základní optimální řešení.
66
Cvičení
6.1 Management firmy Sporten a. s. vyrábějící sportovní potřeby uvažuje o výrobě dvou
nových typů sjezdových lyží. Sjezdové lyže A jsou ve sportovním provedení a typ B pro
rekreační lyžaře. Limitující faktory při výrobě jsou:
a) spotřeba laminátu (2bm pro A, 1,5bm pro B);
b) spotřeba barev (400g pro A, 600g pro B);
c) spotřeba strojového času při výrobě (50min pro A, 40min pro B).
K dispozici je celkem 360bm laminátu, 120kg barev a 200 hodin strojového času. Za
jeden pár lyží typu A bude zisk 3 500Kč, za jeden pár lyží typu B pak 3 000 Kč.
Management chce naplánovat výrobní program tak, aby bylo dosaženo co nejvyššího
zisku. Sestavte matematický model
6.2 Výrobní družstvo produkuje dva výrobky V1 a V2. V daném roce má vyrobit celkem
minimálně 800kg obou výrobků, přičemž se již smluvně zavázalo na dodání 300kg
výrobku V1 a 400kg V2. Oba výrobky se vyrábějí na dvou strojích. Výroba 1kg výrobku
V1 trvá 105 minut na prvním stroji a 5 hodin na druhém stroji a náklady na výrobu jsou
3 000Kč. Kilogram výrobku V2 se vyrábí 4 hodiny na prvním a 5 hodin na druhém stroji
s náklady 2 000Kč. Disponibilní časový fond prvního stroje je 2 400 hodin a druhého
stroje 5 000 hodin. Vedení družstva chce sestavit výrobní program, kterým splní své
závazky s minimálními náklady. Sestavte matematický model.
6.3 Podnik vyrábí čtyři výrobky a má omezení ve třech surovinách. Potřeba surovin na tunu
jednotlivých výrobků, disponibilní množství surovin i ceny jednotlivých výrobků jsou
uvedeny v tabulce
V1 (t) V2 (t) V3 (t) V4 (t)
Disponibilní
množství (t)
S1 (t) 10 5 4 2 2 000
S2 (t) 8 5 1,2 5,6 1 800
S3 (t) 5 8 2,5 10 2 000
Cena (Kč/t) 5 000 3 000 2 000 2 800
Je třeba sestavit optimální výrobní program tak, aby hodnota odbytu byla maximální.
Sestavte matematický model.
6.4 Jistá chemická firma vyrábí čtyř druhů hnojiv. Při výrobě používá mimo jiné látky N, P,
K. Údaje o spotřebě jednotlivých látek na jeden kilogram příslušného druhu hnojiva,
jejich disponibilní množství a výrobní cenu 1kg každého druhu hnojiva naleznete
v tabulce. Naplánujte výrobu tak, aby firma vyrobila
a) co nejvíce hnojiva za 7 000Kč;
b) co nejlevněji 500kg hnojiva.
Sestavte matematický model.
H1 (kg) H2 (kg) H3 (kg) H4 (kg)
Disponibilní
množství (kg)
N (kg) 0,02 0,5 0,4 0,3 60
P (kg) 0,04 0,06 0,2 0,1 55
K (kg) 0,015 0,09 0,018 0,06 10
Náklady (Kč/kg) 20 40 35 32
67
6.5 Společnost zabývající se výrobou pálených střešních tašek předpokládá na příští období
odbyt svých výrobků v maximální výši 8 000 000m2
(= 800ha). Vyrábí čtyři druhy
střešních tašek s různou spotřebou nedostatkové suroviny a časovou kapacitou strojního
zařízení. V daném období má k dispozici 24 000t suroviny a 40 000 hodin strojního
zařízení. V tabulce je uvedena spotřeba suroviny a strojního zařízení pro jednotlivé
druhy tašek a zisk z jejich výroby (vše vztaženo na 10 000m2 = 1ha). Je třeba sestavit
takový výrobní program, při kterém společnost dosáhne maximálního zisku. Sestavte
matematický model.
T1 (ha) T2 (ha) T3 (ha) T4 (ha)
S (t) 20 60 20 40
SZ (hod) 40 40 60 80
Zisk (Kč/ha) 20 000 40 000 30 000 50 000
6.6 Sestavte matematický model úlohy z předchozího cvičení za předpokladu, že se
management společnosti rozhodne v daném období pro výrobu právě 8 000 000m2
tašek.
6.7 Krmná směs se skládá ze sena, siláže a koncentrátů, které obsahují bílkoviny, vápník a
vitamíny. Obsah jednotlivých živin v gramech na 1kg příslušné složky krmné směsi a
minimální normy potřeby těchto živin jsou uvedeny v tabulce. Máme určit optimální
složení krmné směsi za podmínky minimální ceny, jestliže 1kg sena stojí 30Kč, 1kg
siláže 20Kč a 1kg koncentrátů 50Kč. Sestavte matematický model.
Bílkoviny (g) Vápník (g) Vitamíny (mg)
Seno (kg) 50 6 2
Siláž (kg) 20 4 1
Koncentráty (kg) 180 3 1
Norma potřeby 2 000 120 40
6.8 Firma Nomo s.r.o. dostala zakázku na výrobu železných regálů. Má k dispozici 400 tyčí
o délce 2,20m, které potřebuje rozřezat na spoje o délce 50cm a 30cm. Pro splnění této
zakázky bude těchto tyčí o délce 50cm potřebovat alespoň 180ks a tyčí o délce 30cm
alespoň 120ks. Možné varianty rozřezání tyčí jsou uvedeny v tabulce.
V1 V2 V3 V4 V5
50cm 4 3 2 1 0
30cm 0 2 4 5 7
Odpad (cm) 0,2 0,1 0 0,2 0,1
Je třeba rozhodnout, které z variant a kolikrát použít, aby bylo k dispozici dostatečné
množství tyčí v požadované délce a současně byl minimalizován
a) odpad;
b) počet výchozích tyčí;
c) počet řezů.
Sestavte matematický model.
68
7. Řešení úloh lineární programování
7.1 Grafické řešení úloh lineárního programování
Pokud matematický model úlohy lineárního programování obsahuje pouze dvě strukturní
proměnné, můžeme nalézt množinu přípustných řešení a vyhledat na ní extrém účelové
funkce pomocí grafického znázornění v rovině kartézské soustavy souřadnic.
Grafické řešení libovolné soustavy lineárních nerovnic se dvěma neznámými bylo
vysvětleno v 5. kapitole. V úlohách lineárního programování je nutné ještě respektovat
podmínky nezápornosti obou neznámých, tzn. uvažovat průnik příslušných polorovin pouze v
I. kvadrantu. Kromě toho může soustava vlastních omezujících podmínek obsahovat též
rovnice (jejich grafickým znázorněním jsou přímky), takže obecně množinu přípustných
řešení tvoří průnik všech odpovídajících polorovin, přímek a I. kvadrantu.
Neprázdný průnik polorovin a přímek, které jsou konvexními útvary (s každými dvěma
body v nich leží i jejich spojnice), je opět konvexní útvar, který má konečný počet krajních
bodů (vrcholů) a který je buď omezený (pak jde o tzv. konvexní polyedr), nebo neomezený.
Tento průnik budeme označovat jako množinu M.
Příklad 7.1.1
Balírny a pražírny kávy DE, a.s. plánují pro následující období výrobu dvou směsí kávy Super
a Standard. Pro výrobu obou směsí mají přitom na toto období smluvně k dispozici od
dodavatelů tři druhy kávových bobů (označme je K1, K2 a K3) postupně v kapacitě 40, 60 a 25
tun. Při výrobě je třeba dodržovat technologické postupy, které mimo jiné určují, jaké
procento jednotlivých komponent bude použito při výrobě jednotlivých směsí, což ukazuje
následující tabulka 7.1.1.
Tabulka 7.1.1 Složení vyráběných směsí kávy
Super Standard
Kávové boby K1 50% 25%
Kávové boby K2 50% 50%
Kávové boby K3 - 25%
Na základě nákladů a vzhledem k předpokládané ceně obou směsí byl vykalkulován zisk,
který činí 20 000Kč resp. 14 000Kč na 1 tunu směsi Super resp. Standard. Naplánujeme
výrobu firmy tak, aby dosáhla maximálního zisku a určíme tento zisk.
Řešení
Označme x1 vyrobené množství směsi Super (v tunách) a x2 vyrobené množství směsi
Standard (v tunách). Naším úkolem je tedy graficky vyřešit následující soustavu pěti
lineárních nerovnic (tři vlastní omezení a dvě podmínky nezápornosti) o dvou neznámých
0
0
2525,0
605,05,0
4025,05,0
2
1
2
21
21
x
x
x
xx
xx
69
a ze všech přípustných řešení nalézt graficky takové, pro které je hodnota výrazu (účelové
funkce představující zisk firmy)
21 0001400020 xxz
maximální.
První tři nerovnice vyjádříme v úsekovém tvaru:
.1100
1120120
116080
2
21
21
x
xx
xx
Spolu s podmínkami nezápornosti znázorníme tyto nerovnice a jejich průnik graficky.
Obrázek 7.1.1 Množina přípustných řešení z příkladu 7.1.1
Množinu všech přípustných řešení M dané soustavy tedy tvoří vybarvený pětiúhelník
ABCDE. Otázkou zůstává, který z bodů tohoto trojúhelníka představuje optimální řešení
z hlediska celkového zisku. V postupu vedoucímu k zodpovězení této otázky začneme tím, že
graficky znázorníme množinu bodů, které odpovídají určitému „vhodně“ zvolenému zisku.
Zvolme za tento zisk částku 1 400 000Kč. Hledanou množinou bodů bude zřejmě přímka,
která je dána rovnicí
,00014000200004001 21 xx
tj.
.110070
21 xx
Zakreslíme tuto přímku do množiny přípustných řešení.
70
Obrázek 7.1.2 Množina všech bodů odpovídajících zisku 1 400 000Kč v příkladu 7.1.1
Z obrázku je zřejmé, že existuje nekonečně mnoho uskutečnitelných výrobních programů
(průnik přímky a pětiúhelníka), které přinesou zisk 1 400 000Kč (např. výroba pouze směsi
Standard v množství 100 tun , což odpovídá bodu E[0, 100]). Dále je třeba, abychom si
uvědomili, že přímky, které odpovídají jiným ziskům, mají stejný normálový vektor jako
přímka odpovídající zisku 1 400 000Kč a jsou s ní tudíž rovnoběžné. Dále je zřejmé, že čím
větší zisk, tím víc je příslušná přímka posunuta v naší soustavě souřadnic „severovýchodním
směrem“. Stačí si totiž např. uvědomit, že nulovému zisku odpovídá rovnoběžka procházející
počátkem soustavy souřadnic. Z této úvahy je zřejmé, že optimálnímu řešení odpovídá bod C
(viz obrázek 7.1.3).
Obrázek 7.1.3 Optimální řešení příkladu 7.1.1
71
Souřadnice bodu C získáme řešením soustavy rovnic
.605,05,0
4025,05,0
21
21
xx
xx
Snadno se přesvědčíme, že x1 = 40 a x2 = 80. Dosadíme-li tyto hodnoty do cílové funkce,
získáme hodnotu 1 920 000.
Firma tedy dosáhne maximálního zisku, jestliže bude vyrábět 40 tun směsi Super a 80 tun
směsi Standard. Tento zisk bude činit 1 920 000Kč.
Pozn.
Podle věty 6.4.3 bychom mohli postupovat tak, že určíme hodnotu cílové funkce pro všechna
základní přípustná řešení, kterými jsou (viz řešení příkladu 5.3.2) všechny vrcholy daného
pětiúhelníka. Souřadnice bodu D získáme podle obrázku 7.1.1 řešením soustavy
.605,05,0
2525,0
21
2
xx
x
Odtud snadno máme x1 = 20 a x2 = 100, tedy D[20, 100]. Hodnoty cílové funkce odpovídající
jednotlivým přípustným základním řešením uvedeme přehledně v tabulce 7.1.2.
Tabulka 7.1.2
Přípustné základní řešení Hodnota účelové funkce (zisku) vKč
x1 = 0, x2 = 0 (bod A) 0000014000020A z
x1 = 80, x2 = 0 (bod B) 00060010000148000020B z
x1 = 40, x2 = 80 (bod C) 0009201 80000144000020Cz
x1 = 20, x2 = 100 (bod D) 0008001100000142000020D z
x1 = 0, x2 = 100 (bod E) 000400110000014000020E z
Tím je výsledek potvrzen.
Je zřejmé, že úloha lineárního programování nemusí mít právě jedno optimální řešení, jako
tomu bylo v předchozím příkladu. Řešení může být také nekonečně mnoho (v našem příkladu
by stačilo, aby přímky, které vyjadřují zisk, byly rovnoběžné s jednou ze stran pětiúhelníka).
V takovém případě mluvíme o tom, že má úloha lineárního programování alternativní
optimální řešení. Naopak si jistě umíme představit případy, kdy úloha LP nemá řešení, což
může nastat jednak tím, že množina přípustných řešení je prázdná, jednak může být
neuzavřená, a hodnota cílové funkce je tím pádem neomezená. Na dalších příkladech budeme
některé zmíněné případy demonstrovat.
Příklad 7.1.2
Řešme příklad 7.1.1 pouze s tou změnou, že zisk z prodeje jedné tuny směsi Super je
22 000Kč a z jedné tuny směsi Standard je 11 000Kč.
Řešení
Množina přípustných řešení zůstane pochopitelně stejná – viz obrázek 7.1.1. Změní se poloha
grafu účelové funkce v soustavě souřadnic, protože účelová funkce vyjadřující zisk
v závislosti na vyrobeném množství obou směsí bude mít nyní tvar
21 0001100022 xxz .
72
Dosadíme-li za z zisk 1 100 000Kč a upravíme na úsekový tvar, dostaneme
.110050
21 xx
Obrázek 7.1.4 Množina všech bodů odpovídajících zisku 1 100 000Kč v příkladu 7.1.2
Zakreslíme-li tuto přímku do množiny přípustných řešení, vidíme, že je rovnoběžná se stranou
BC množiny přípustných řešení. Je tedy zřejmé, že existuje nekonečně mnoho optimálních
řešení úlohy z příkladu 7.1.2, která odpovídají bodům úsečky BC - viz obrázek 7.1.5. Dvě
z těchto optimálních řešení jsou základní optimální řešení. Jsou to řešení odpovídající krajním
bodům úsečky BC. Libovolné optimální řešení můžeme vyjádřit pomocí parametrického
vyjádření úsečky. Ze středoškolské analytické geometrie víme, že pro libovolný bod [x1, x2]
úsečky BC, kde B[x1B, x2B] a C[x1C, x2C] platí:
.1,0,)1()(
)1()(
C2B2B2C2B22
C1B1B1C1B11
kkxxkkxxxx
kxxkkxxxx
Odtud pro libovolný vektor optimálního řešení optx plyne, že
,1,0,)1( CBopt kkk xxx (7.1.3)
přičemž
T
C
T
B )80,40(,)0,80( xx .
Dosazením libovolného optimálního řešení do účelové funkce dostaneme maximální možný
zisk. Dosadíme-li tedy např. optimální řešení odpovídající bodu B, máme
00076010000118000022max z .
73
Obrázek 7.1.5 Optimální řešení příkladu 7.1.2
Příklad 7.1.3
Nalezneme pět rovnocenných optimálních řešení úlohy formulované v příkladu 7.1.2.
Řešení
Do vztahu (7.1.3) dosadíme například za k postupně .1a4
3,
2
1,
8
1,0 Máme
.)80,40()80,40(1)0,80)(11(
,)60,50()80,40(4
3)0,80(
4
31
,)40,60()80,40(2
1)0,80(
2
11
,)10,75()80,40(8
1)0,80(
8
11
,)0,80()80,40(0)0,80)(01(
C
TTT
5
TTT
4
TTT
3
TTT
2
B
TTT
1
xx
x
x
x
xx
Příklad 7.1.4
Firma usiluje o co největší úhrnný počet výrobků V1 a V2, jejichž prodejem by získala
alespoň 30 000Kč. Cena 1q výrobku V1 je 3 000Kč a 1q V2 se prodává za 4 000Kč. Výrobek
V2 vyžaduje speciální výrobní zařízení, které umožňuje jeho výrobu v rozsahu nejvýše 600kg.
Jaké množství výrobků V1 a V2 má firma vyrábět?
Řešení
Matematický model bude mít dvě strukturní proměnné, a to x1 (množství výrobků V1 v q) a x2
(množství V2 v q). Tyto proměnné jsou omezeny podmínkami
74
.0
0
6
3043
2
1
2
21
x
x
x
xx
Naším úkolem je najít takové řešení této soustavy, které maximalizuje funkci
z = x1 + x2 .
Množina přípustných řešení M je znázorněna na obrázku 7.1.6, z něhož je zřejmé, že tato
množina je neuzavřená. Za z dosadíme postupně 10 resp. 15, čímž dostaneme dvě přímky
vyjadřující množinu bodů, které odpovídají řešením, jež znamenají výrobu celkem10q resp.
15q výrobků. Poloha těchto přímek je na obrázku 7.1.6 rovněž vyznačena. Je zřejmé, že daná
účelová funkce může neomezeně vzrůstat a úloha tudíž nemá řešení. Z obrázku je dále vidět,
že minimum účelové funkce za uvedených podmínek existuje a je reprezentováno bodem A.
Obrázek 7.1.6 Množina přípustných řešení z příkladu 7.1.4
Grafické řešení úloh lineárního programování je velmi názorné, nicméně neumožňuje řešit
úlohy, ve kterých se objeví více než dvě strukturní proměnné. V dalším se budeme zabývat
metodami algebraickými, které uvedený omezující nedostatek nemají.
7.2 Algebraické řešení úloh lineárního programování
Z dosud provedených úvah je zřejmé, jak bychom mohli postupovat při algebraickém
(početním) řešení úloh lineárního programování (LP). V odstavci 4.6 jsme ukázali postup při
určování základních řešení soustavy rovnic, kterých je podle věty 4.5.2 konečný počet.
Jestliže má úloha lineárního programování optimální řešení, stačí podle věty 6.4.3 nalézt
požadovaný extrém účelové funkce na množině základních řešení úlohy lineárního
75
programování, která tvoří podle definic 6.4.2 a 5.2.2 dokonce pouze podmnožinu množiny
základních řešení příslušné soustavy rovnic. Možná cesta je tedy následující:
1) sestavit přidruženou soustavu rovnic k vlastním omezením úlohy LP;
2) nalézt všechna základní řešení přidružené soustavy rovnic;
3) dosazováním přípustných základních řešeních úlohy LP do účelové funkce nalézt to
(ta) řešení, při kterém (kterých) účelová funkce nabývá požadované extrémní hodnoty.
Tato cesta je tedy možná, ale musíme si uvědomit, že při rozsáhlejších úlohách jen těžko
schůdná, protože např. soustava rovnic s deseti proměnnými a pěti omezeními může mít až
252 základních řešení, soustava deseti rovnic s padesáti proměnnými může mít přes 10
miliard základních řešení atd.
Postup řešení by se jistě velmi zefektivnil, pokud bychom našli metodu, při které bychom
se zabývali hledáním pouze přípustných základních řešení. Pokud bychom navíc měli
zaručeno, že každé nově určené přípustné základní řešení dává lepší hodnotu účelové funkce
než to předchozí, bylo by to skvělé. A právě takovou metodu popsal v polovině minulého
století G. B. Dantzig, který ji nazval simplexová metoda. Podstata jejího algoritmu je
znázorněna na obrázku 7.3.1.
Obrázek 7.3.1 Vývojový diagram výpočetního postupu podle simplexové metody v případě,
že úloha má alespoň jedno řešení
Začátek
+ +
- -
Nalezení výchozího
přípustného základního řešení
Je toto
řešení
optimální?
Nalezení nového přípustného
základního řešení s lepší
hodnotou účelové funkce
Určení všech
optimálních řešení
Je to jediné
optimální
řešení?
řešení
Konec
76
7.3 Jednofázová simplexová metoda
O jednofázové simplexové metodě mluvíme v případě, že všechna vlastní omezení úlohy jsou
vyjádřena nerovnicemi typu „ “ a současně jsou všechny pravé strany nezáporné. Přidružená
soustava rovnic je potom přímo v kanonickém tvaru a tím pádem je okamžitě vidět jedno její
základní řešení, které je přípustným základním řešením úlohy lineárního programování a
můžeme ho tedy pokládat za výchozí. Je to řešení, v němž jsou základními (nevolitelnými)
proměnnými přídatné proměnné. První „fáze“ simplexové metody - nalezení výchozího
základního řešení zde tedy prakticky odpadá.
Celý výpočet optimálního řešení simplexovou metodou se provádí v tzv. simplexové
tabulce. Její výchozí tvar ukazuje tabulka 7.3.1.
Tabulka 7.3.1 Výchozí simplexová tabulka při jednofázové simplexové metodě
Báze x1 x2 … xn xn+1 xn+2 … xn+m bi
xn+1 a11 a12 … a1n 1 0 … 0 b1
xn+2 a21 a22 … a2n 0 1 … 0 b2
… … … … … … … … … …
xn+m am1 am1 … amn 0 0 … 1 bm
z -c1 -c2 … -cn 0 0 0 0 0
Je zřejmé, že vnitřek tabulky tvoří rozšířená matice přidružené soustavy rovnic plus řádek,
v němž jsou uvedeny opačné hodnoty cenových koeficientů - jedná se vlastně o koeficienty u
příslušných proměnných při zápisu účelové funkce v anulovaném tvaru. Záhlaví řádků tvoří
základní proměnné, které vytvářejí tzv. bázi. Ve výchozí simplexové tabulce jsou to přirozeně
přídatné proměnné.
Výchozím základním řešením je vektor T210 ...,,,,0...,,0,0 mbbbx . Tento vektor
odpovídá např. výrobnímu plánu, při němž se nevyrábí ani jeden z n výrobků (prvních n nul)
a tudíž všech m výrobních činitelů zůstane k dispozici v původním množství (hodnoty b1 až
bm). Odpovídající hodnota účelové funkce je vidět v pravém dolním rohu tabulky a logicky je
při tomto výchozím řešení nulová.
Definice 7.3.1
Řádek simplexové tabulky s anulovanou rovnicí účelové funkce budeme nazývat indexním
řádkem. Koeficienty u jednotlivých proměnných v indexním řádku budeme nazývat
indexními čísly.
Věta 7.3.1 (kritérium optimálnosti)
V maximalizačních (minimalizačních) úlohách je optimální hodnoty účelové funkce dosaženo
tehdy, když všechna indexní čísla jsou nezáporná (nekladná).
Pokud příslušné řešení úlohy LP není optimální, přejdeme postupem známým z Jordanovy
eliminační metody k novému přípustnému základnímu řešení, které má „lepší“ hodnotu
účelové funkce, což je zajištěno způsobem zvolení nové množiny základních proměnných -
nové báze. Ve stávající bázi nahradíme jednu základní proměnnou (vystupující proměnná)
jinou (vstupující proměnná). Za vstupující proměnnou volíme podle věty 7.3.1 tu nezákladní
proměnnou, u které je nejvíc porušeno kritérium optimálnosti, tj. tu, jež má v posledním řádku
nejmenší zápornou hodnotu u maximalizační úlohy a největší kladnou u minimalizační.
77
Definice 7.3.2
Sloupec vstupující proměnné se nazývá klíčový sloupec a řádek vystupující proměnné má
název klíčový řádek. V průsečíku klíčového řádku a klíčového sloupce je tzv. klíčové pole a
číslo v něm je tzv. klíčový prvek.
Věta 7.3.2
V maximalizačních (minimalizačních) úlohách do řešení vstoupí proměnná, která má
v indexním řádku nejnižší záporné (největší kladné) číslo.
Pozn.
Uvažujme maximalizační úlohu. V prvním kroku algoritmu jde ve větě 7.3.2 o proměnnou,
která má v původním neanulovaném tvaru účelové funkce největší kladný koeficient.
V dalších krocích lze uvedené pravidlo odvodit z tvaru účelové funkce zapsané do indexního
řádku, tzn. z rovnice
Bk
kk uxz , kde B je množina indexů nezákladních proměnných, γk
jsou indexní čísla těchto proměnných a u je hodnota účelové funkce v příslušném kroku.
Uvedený zápis je totožný s rovnicí
Bk
kk xuz , ze které je patrné, proč se hodnota
účelové funkce nejvíce zvýší po zařazení proměnné s nejnižším záporným indexním číslem.
Analogická úvaha platí i pro minimalizační úlohy.
Věta 7.3.3
Klíčový řádek v maximalizačních i minimalizačních úlohách je určen nejmenším podílem
pravých stran rovnic a odpovídajících kladných koeficientů v klíčovém sloupci.
Pozn.
Z báze tedy vystoupí proměnná, pro kterou vyjde nejmenší podíl čísel ve sloupci pravých
stran a odpovídajících kladných koeficientů v klíčovém sloupci. Jestliže toto pravidlo
porušíme, ve sloupci pravých stran se objeví záporné číslo, tzn. některá ze základních
proměnných bude záporná.
Věta 7.3.4
Úloha lineárního programování má neomezenou hodnotu účelové funkce, pokud jsou všechny
koeficienty klíčového sloupce nekladné.
Po určení vstupující a vystupující proměnné pomocí ekvivalentních řádkových úprav
přepočítáme simplexovou tabulku tak, aby z ní bylo vidět základní řešení odpovídající nově
vytvořené bázi, což jak víme, znamená upravit tabulku do takového tvaru, v němž je
v klíčovém sloupci jednotkový vektor s jednotkou v klíčovém poli.
Popsaný postup opakujeme tak dlouho, dokud nezískáme optimální řešení nebo
nezjistíme, že úloha řešení nemá. V následujícím příkladu ukážeme konkrétní postup
v případě jediného optimálního řešení úlohy.
Příklad 7.3.1
Ukážeme řešení úlohy zadané v příkladu 7.1.1 (výroba dvou směsí kávy).
Řešení
Připomeňme, že matematický model této úlohy vypadá takto:
x1 … vyrobené množství směsi Super (v tunách)
x2 …vyrobené množství směsi Standard (v tunách)
78
.max0001400020
2,1,0
2525,0
605,05,0
4025,05,0
21
2
21
21
xxz
jx
x
xx
xx
j
Po převedení vlastních omezení na soustavu rovnic dostáváme
.5,4,3,2,1,0
2525,0
605,05,0
4025,05,0
52
421
321
jx
xx
xxx
xxx
j
Tabulka 7.3.2 Výchozí simplexová tabulka z příkladu 7.1.1
Báze x1 x2 x3 x4 x5 bi podíly
x3 21
41 1 0 0 40 80
x4 21
21 0 1 0 60 120
x5 0 41 0 0 1 25 ---
z -20 000 -14 000 0 0 0 0
Vektor výchozího základního řešení T0 25,60,40,0,0x odpovídá výrobnímu programu,
ve kterém se nebude vyrábět ani směs Super ani Standard, přičemž zůstane k dispozici 40 tun
K1 (kávových bobů prvního druhu), 60 tun K2 a 25 tun K3, což pochopitelně přinese nulový
zisk, tedy z0 = 0. Poznamenejme ještě, že toto řešení odpovídá vrcholu A pětiúhelníka
z grafického řešení – obrázek 7.1.1. Protože toto řešení není evidentně optimální (viz záporná
indexní čísla), nalezneme jiné s vyšší hodnotou účelové funkce. Snadno zjistíme, že vstupující
proměnná je v této fázi x1 a vystupující x3 (příslušné podíly jsou uvedeny v doplněném
sloupci).
Tabulka 7.3.2 Simplexová tabulka z příkladu 7.1.1 po prvním přepočtu
Báze x1 x2 x3 x4 x5 bi podíly
x1 1 21 2 0 0 80 160
x4 0 41 -1 1 0 20 80
x5 0 41 0 0 1 25 100
z 0 -4 000 40 000 0 0 1 600 000
Z této tabulky je vidět další základní řešení T1 25,20,0,0,80x , které odpovídá výrobě
80 tun směsi Super, přičemž se nespotřebuje 20 tun K2 a 25 tun K3. Firma dosáhne v tomto
případě zisku 1 600 000Kč (z1 = 1 600 000). Tomuto výrobnímu programu odpovídá
v grafickém řešení vrchol B. Jelikož ani toto řešení není optimální, provedeme další přepočet.
Tabulka 7.3.3 Výsledná simplexová tabulka z příkladu 7.1.1
Báze x1 x2 x3 x4 x5 bi
x1 1 0 4 -2 0 40
x2 0 1 -4 4 0 80
x5 0 0 1 -1 1 5
z 0 0 24 000 16 000 0 1 920 000
79
Protože v indexním řádku jsou samé nezáporné hodnoty, vyjadřuje tato tabulka optimální
řešení, které je určeno vektorem
Topt2 5,0,0,80,40 xx a .0009201max2 zz
Ekonomická interpretace tohoto výsledku je následující: optimální výrobní program firmy
z hlediska zisku je vyrábět 40 tun směsi Super a 80 tun směsi Standard s tím, že zisk je
1 920 000Kč a že navíc při této výrobě zůstane 5 tun K3. Je zřejmé, že u grafického řešení
odpovídá tomuto řešení vrchol C. Současně si povšimněte toho, že řešení simplexovou
metodou dává úplnější informaci o příslušném základním řešení, totiž informaci o příslušných
hodnotách přídatných proměnných, které vyjadřují obecně nevyužití odpovídajícího zdroje.
7.4 Dvoufázová simplexová metoda
Dvoufázovou simplexovou metodu můžeme uplatnit při řešení úloh lineárního programování,
které mají některá omezení ve tvaru nerovnice typu „≥“ nebo rovnice. V tomto případě je po
vyjádření všech vlastních omezení ve tvaru rovnic nutné pro získání kanonického tvaru
soustavy vlastních omezení zavést ještě tzv. pomocné (umělé) proměnné. Je zřejmé, že
soustava omezení, která je rozšířená o umělé proměnné, je ekvivalentní s původní soustavou
rovnic právě tehdy, když všechny umělé proměnné jsou rovny nule. Vynulování umělých
proměnných lze dosáhnout právě tzv. dvoufázovou simplexovou metodou, kdy v 1. fázi
minimalizujeme součet umělých proměnných (tzv. pomocnou účelovou funkci) a v případě,
že dosáhneme její nulové hodnoty (vynulování všech pomocných proměnných), nalezneme
přípustné výchozí základní řešení. Následně přejdeme k 2. fázi výpočtu, kdy v simplexové
tabulce vynecháme sloupce umělých proměnných a řádek s pomocnou účelovou funkcí a
hledáme extrém původně zadané účelové funkce.
Věta 7.4.1
Úloha lineárního programování nemá přípustné řešení, pokud je minimum pomocné účelové
funkce kladné.
Příklad 7.4.1
Podnik na výrobu železných konstrukcí potřebuje z 35 dvoumetrových tyčí nařezat alespoň 52
tyčí délky 50cm a alespoň 18 tyčí délky 80cm. Jak má tyče řezat, aby získal požadovaný
počet kratších tyčí s minimálním odpadem. Budeme vycházet z předpokladu, že neuvažujeme
způsoby řezání dvoumetrových tyčí s odpadem větším než 20cm.
Řešení
Matematický model téměř stejné úlohy LP jsme sestavili v řešení příkladu 6.3.1. Zde je navíc
omezené množství výchozích dvoumetrových tyčí.
Tabulka 7.4.1 Řezné plány úlohy z příkladu 7.4.1
V1 V2
Délka 50 (cm) 2 4
Délka 80 (cm) 1 0
Odpad (cm) 20 0
Neznámými veličinami xj jsou počty dvoumetrových tyčí řezaných podle varianty Vj, j = 1,2.
Hledáme takové řešení soustavy nerovnic
80
,18
5242
35
1
21
21
x
xx
xx
kde 021, Nxx , které minimalizuje funkci
.20 1xz
Přidružená soustava rovnic v kanonickém tvaru je
.18
5242
35
751
6421
321
xxx
xxxx
xxx
Proměnné x3, x4 , x5 jsou přídatné, proměnné x6, x7 jsou umělé. Pomocná účelová funkce,
kterou máme v první fázi minimalizovat, má tvar
.76 xxz
Anulovanou rovnici pomocné účelové funkce přidáme do výchozí simplexové tabulky pod
řádek s anulovanou rovnicí původní účelové funkce z = 20x1 → min. (viz 1. část tabulky
7.4.2). Aby umělé proměnné x6 a x7, které jsou ve výchozím řešení základními proměnnými,
měly jednotkové vektory koeficientů včetně řádku s pomocnou účelovou funkcí, vyloučíme je
před zahájením výpočtu z řádku z´ tak, že k němu přičteme 2. a 3. řádek. V 1. fázi výpočtu o
zařazovaných proměnných rozhodují čísla v řádku z´. Po 2. kroku simplexového algoritmu
tento řádek obsahuje pouze nekladná čísla, takže bylo dosaženo minimální, a to nulové
hodnoty pomocné účelové funkce, a tedy i nulových hodnot obou umělých proměnných.
Protože po vynechání sloupců umělých proměnných x6 a x7 v indexním řádku z též není
žádné kladné číslo, bylo současně dosaženo minima původní účelové funkce.
Tabulka 7.4.2
Báze x1 x2 x3 x4 x5 x6 x7 bj
x3 1 1 1 0 0 0 0 35
x6 2 4 0 -1 0 1 0 52
x7 1 0 0 0 -1 0 1 18
z -20 0 0 0 0 0 0 0
z´ 0 0 0 0 0 -1 -1 0
Uprav. z´ 3 4 0 -1 -1 0 0 70
x3 21 0 1 4
1 0 41 0 22
x2 21 1 0 4
1 0 41 0 13
x7 1 0 0 0 -1 0 1 18
z -20 0 0 0 0 0 0 0
z´ 1 0 0 0 -1 -1 0 18
x3 0 0 1 41
21
41
21 13
x2 0 1 0 41
21
41
21 4
x1 1 0 0 0 -1 0 1 18
z 0 0 0 0 -20 0 20 360
z´ 0 0 0 0 0 -1 -1 0
81
Optimální řešení je tedy dáno vektorem
xopt1 T)0,0,13,4,18( .
Tomuto řešení odpovídá hodnota účelové funkce
.360z
Minimálního odpadu 360cm bude dosaženo, jestliže 18 dvoumetrových tyčí se rozřeže podle
1. řezné varianty a 4 tyče podle 2. varianty, takže zbude 13 nerozřezaných tyčí (x3 = 13).
Počet získaných tyčí délky 50cm a 80cm bude na jejich dolní požadované hranici (x4 = x5 =
= 0).
V poslední části tabulky 7.4.1 je u nezákladní proměnné x4 odpovídající indexní číslo
rovno nule. Jednoduchou úvahou dojdeme k závěru, že pokud bychom v dalším kroku
simplexové metody zvolili za vstupující proměnnou právě x4 a podle věty 7.3.3 určili
vystupující proměnnou, dostaneme nové základní řešení, které bude mít stejnou hodnotu
účelové funkce - bude tedy také optimální. Označme jej řekněme xopt2.
Podle úvah v řešení příkladu 7.1.2 by tedy v takovém případě bylo optimální i každé další
řešení, které lze získat konvexní lineární kombinací (7.1.3) vektorů xopt1 a xopt2. Jen je třeba si
uvědomit, že v tomto případě bude počet všech optimálních řešení konečný, protože
vzhledem k charakteru proměnných přicházejí v úvahu pouze jejich celočíselné hodnoty.
Tabulka 7.4.3 Určení alternativního základního řešení
Báze x1 x2 x3 x4 x5 bj
x3 0 0 1 41
21 13
x2 0 1 0 41
21 4
x1 1 0 0 0 -1 18
z 0 0 0 0 -20 360
x4 0 0 4 1 2 52
x2 0 1 1 0 1 17
x1 1 0 0 0 -1 18
z 0 0 0 0 -20 360
Je tedy
xopt2 = (18, 17, 0, 52, 0)T.
Toto řešení odpovídá situaci, kdy bude 18 tyčí rozřezáno podle první varianty a 17 podle
druhé. Spotřebují se tedy všechny výchozí tyče s tím, že půlmetrových tyčí bude vyrobeno o
52 víc než je požadováno a tyčí o délce 80cm vznikne přesně tolik, kolik bylo požadováno.
Použitím vztahu (7.1.3) nakonec nalezneme množinu všech optimální řešení úlohy LP
z tohoto příkladu.
.)0,52,0,17,18(),0,48,1,16,18(),0,44,2,15,18(),0,40,3,14,18(
),0,36,4,13,18(),0,32,5,12,18(),0,28,6,11,18(),0,24,7,10,18(),0,20,8,9,18(
),0,16,9,8,18(),0,12,10,7,18(),0,8,11,6,18(),0,4,12,5,18(),0,0,13,4,18(
Věta 7.4.2
Úloha lineárního programování má alternativní optimální řešení, jestliže všechna indexní čísla
vyhovují podmínkám optimálnosti a současně je alespoň jedno indexní číslo u nezákladní
proměnné rovno nule.
82
Cvičení
7.1 Řešte graficky úlohu ze cvičení 6.1.
7.2 Řešte graficky úlohu ze cvičení 6.2.
7.3 Řešte graficky následující úlohu LP. Nalézt maximum funkce
21 24 xxz
za podmínek
.2,10
102
1832
93
21
21
21
jx
xx
xx
xx
j
7.4 Řešte úlohu ze cvičení 6.3.
7.5 Podnik vyrábí pět výrobků a má omezení ve dvou surovinách a v časové kapacitě
slévárny. Potřeba surovin na 1q výrobku a časové nároky jednotlivých výrobků na
slévárnu jsou uvedeny v tabulce.
V1 (q) V2 (q) V3 (q) V4 (q) V5 (q)
Disponibilní
množství (q)
S1 (q) 10 8 12 20 6 6 000
S2 (q) 5 6 2 4 6 2 000
Slévárna (hod) 4 1 5 4 1 1 000
Zisk (Kč/q) 1 000 900 800 1 200 900
Sestavte výrobní program s maximálně dosažitelným ziskem.
7.6 Řešte úlohu ze cvičení 6.5.
7.7 Řešte úlohu ze cvičení 6.6.
7.8 Řešte úlohu ze cvičení 6.7.
7.9 Řešte úlohu ze cvičení 6.8.
7.10 Řešte úlohu z příkladu 6.2.2.
7.11 Řešte příklad 7.4.1 za předpokladu, že výchozích tyčí je k dispozici pouze 20.
83
8. Dualita úloh lineárního programování
Ke každé úloze lineárního programování lze podle určitých pravidel sestavit úlohu s ní
sdruženou. Jednu z této dvojice sdružených úloh nazýváme primární úloha a druhou duální
úloha. Obě úlohy jsou rovnocenné v tom smyslu, že duální úloha k duální úloze je totožná
s primární úlohou. Často proto hovoříme spíše o dvojici duálně sdružených úloh. Mezi dvěma
duálně sdruženými úlohami existuje celá řada vazeb, které se ukazují jako užitečné při řešení
úloh LP i ekonomické interpretaci řešení těchto úloh.
8.1 Symetrická dualita
Uvažujme úlohu LP popsanou matematickým modelem
max,
,
,
T
xc
ox
bAx
z
(8.1.1)
kde A je matice strukturních koeficientů typu m x n;
x je n-složkový sloupcový vektor proměnných;
b je m-složkový sloupcový vektor požadavkových čísel;
cT
je n-složkový řádkový vektor cenových koeficientů;
o je n-složkový sloupcový nulový vektor.
Definice 8.1.1
Nechť .)...,,,( T
21 myyyy Úlohu LP s matematickým modelem
min
,
,
T
TT
by
oy
cyA
f
(8.1.2)
nazýváme symetricky duálně sdruženou s úlohou (8.1.1).
Příklad 8.1.1
Představme si, že společnost zabývající se výrobou kávy z příkladu 7.1.1 se z nějakých
důvodů rozhodla odprodat své zásoby surovin (tři druhy kávových bobů K1, K2 a K3 postupně
v kapacitě 40, 60 a 25 tun). V tom případě se přirozeně zabývá problémem určení prodejní
ceny jednotlivých surovin. Společnost chce, aby prodejní cena každé suroviny byla
přinejmenším taková, jakou by se daná surovina podílela na maximálním možném zisku
z prodeje jednotlivých druhů kávy. Za těchto podmínek se realisticky uvažující management
společnosti spokojí s minimální celkovou částkou inkasovanou z prodeje surovin. Sestavíme
matematický model takové úlohy.
Řešení
Označme iy prodejní cenu jedné tuny suroviny Ki, kde i = 1, 2, 3. Hledáme takové hodnoty
těchto proměnných, které (podle zadání a údajů z tabulky 7.1.1) splňují podmínky:
84
3,2,1,0
0001425,05,025,0
000205,05,0
321
21
iy
yyy
yy
i
a současně minimalizují funkci
321 256040 yyyf .
Je zřejmé, že úlohy LP formulované v příkladech (7.1.1) a (8.1.1) jsou symetricky duálně
sdružené. Vidíme tedy, že mezi dvojicí symetricky duálně sdružených úloh neexistují pouze
formální vztahy, jak by se zdálo z definice 8.1.1, ale i vztahy věcné.
Vztahy mezi dvěma symetrickými duálně sdruženými úlohami jsou přehledně zapsány
v tabulce 8.1.1. Pouze ze zvyku označme úlohu s proměnnými x jako úlohu primární (klidně
by to mohlo být i naopak).
Tabulka 8.1.1 Vztahy mezi dvěma symetrickými duálně sdruženými úlohami
Primární úloha Duální úloha
Počet proměnných n m
Počet vlastních omezení m n
Matice strukturních koeficientů A AT
Vektor požadavků b c
Vektor cen c b
Typ omezení ≤ ≥
Nezápornost proměnných ano ano
Typ extrému účelové funkce max min
Pozn.
Jestliže jsou některá vlastní omezení maximalizační úlohy typu „≥“, před formulací úlohy
duálně sdružené je musíme převést na omezení typu „≤“ vynásobením číslem (-1). Podobně
jestliže jsou v minimalizační úloze omezení typu „≤“, musíme je převést na omezení typu
„≥“ vynásobením číslem (-1).
Příklad 8.1.2
Ukážeme si formulaci duální úlohy k úloze LP popsané matematickým modelem
.2,1,0
3333
2525
243
1843
min815
21
21
21
21
21
jx
xx
xx
xx
xx
xxz
j
Řešení
Poslední z vlastních omezení je tedy třeba vynásobit číslem (-1). Ve sloupcích tabulky 8.1.2
jsou potom uvedeny obě duálně sdružené úlohy, přičemž v řádcích této tabulky jsou vždy
dvojice omezení, které si odpovídají a označují se jako dvojice duálně sdružených omezení.
85
Tabulka 8.1.2 Dvojice duálně sdružených omezení
Primární model Duální model
min815 21 xxz max33252418 4321 yyyyf
1843 21 xx 01 y
243 21 xx 02 y
2525 21 xx 03 y
3333 21 xx 04 y
01 x 15353 4321 yyyy
02 x 83234 4321 yyyy
8.2 Nesymetrická dualita
Pokud se v matematickém modelu úlohy LP objeví ve vlastních omezeních některá podmínka
ve tvaru rovnice, lze při sestavování matematického modelu duálně sdružené úlohy
postupovat tak, jak ukazuje následující příklad.
Příklad 8.2.1
K úloze LP
3,2,1,0
1294
632
max72
321
321
21
jx
xxx
xxx
xxz
j
Sestavíme úlohu duálně sdruženou.
Řešení
První vlastní omezení lze chápat a zapsat jako soustavu dvou nerovnic. Všechna vlastní
omezení dané úlohy lze tedy zapsat jako
1294
632
632
321
321
321
xxx
xxx
xxx
nebo ekvivalentně
.1294
632
632
321
321
321
xxx
xxx
xxx
Dostáváme tedy úlohu LP (ekvivalentní s úlohou ze zadání příkladu)
86
.3,2,1,0
1294
632
632
max72
321
321
321
21
jx
xxx
xxx
xxx
xxz
j
K takto formulované úloze existuje podle definice 8.1.1 symetrická duálně sdružená úloha ve
tvaru:
.3,2,1,0
0933
7422
2
min1266
321
321
321
321
iy
yyy
yyy
yyy
yyyf
i
Tuto úlohu lze zapsat pouze pomocí dvou strukturních proměnných .a 32211 yuyyu
Máme
.0
093
742
2
min126
2
21
21
21
21
u
uu
uu
uu
uuf
Tato poslední formulace úlohy je ekvivalentní s předchozí formulací pomocí proměnných yi.
Lze tedy tuto úlohu LP označit za úlohu duálně sdruženou k zadané úloze a přehledně sepsat
odpovídající dvojice sdružených omezení. Za upozornění stojí, že proměnná u1 nemusí být
nutně nezáporná (rozdíl dvou nezáporných čísel nemusí být číslo nezáporné).
Tabulka 8.2.1 Dvojice duálně sdružených omezení z příkladu 8.2.1
Primární model Duální model
max72 21 xxz min126 21 uuf
632 321 xxx Ru 1
1294 321 xxx 02 u
01 x 221 uu
02 x 742 21 uu
03 x 093 21 uu
Věta 8.2.1
Jestliže některá vlastní omezující podmínka primární úlohy je dána rovnicí, odpovídající
duální proměnná nemusí být nezáporná.
Skutečnost, že v duální úloze nemusí být strukturní proměnná nezáporná chápeme jako
narušení symetrie, přičemž za totéž lze jistě považovat i výskyt rovnice v primárním modelu.
87
Uvažujme nyní úlohy LP popsané matematickými modely
max
,
,
T
xc
ox
bAx
z
(8.2.1)
a
min,
,
,
T
xc
ox
bAx
z
(8.2.2)
kde A je matice strukturních koeficientů typu m x n;
x je n-složkový sloupcový vektor proměnných;
b je m-složkový sloupcový vektor požadavkových čísel;
cT
je n-složkový řádkový vektor cenových koeficientů;
o je n-složkový sloupcový nulový vektor.
Definice 8.2.1
Nechť .)...,,,( T
21 myyyy Úlohu LP s matematickým modelem
min
,
T
TT
by
cyA
f
resp.
max
,
T
TT
by
cyA
f
nazýváme nesymetricky duálně sdruženou s úlohou (8.2.1) resp. (8.2.2).
Pozn.
Jestliže se v matematickém modelu úlohy LP vyskytují vlastní omezení současně ve tvaru
rovnic i nerovnic a my pracujeme i s úlohou duální, mluvíme o jejich vztahu jako o smíšené
dualitě - viz příklad 8.2.1.
8.3 Vztahy mezi řešením duálně sdružených úloh
Na začátku této kapitoly jsme konstatovali, že dualita je vztah užitečný. Uveďme nyní několik
vět, které popisují vlastnosti řešení duálně sdružených úloh. Ve všech větách tohoto odstavce
uvažujme dvojice duálně sdružených úloh definovaných vztahy (8.1.1) a (8.1.2).
Věta 8.3.1
Má-li jedna z dvojice duálně sdružených úloh jediné optimální řešení, které je
nedegenerované, má jediné nedegenerované optimální řešení i úloha druhá a optimální
hodnoty obou účelových funkcí jsou stejné (zmax = fmin).
88
Věta 8.3.2
Má-li jedna z dvojice duálně sdružených úloh jediné optimální řešení, které je degenerované,
má druhá úloha alternativní optimální řešení a optimální hodnoty obou účelových funkcí jsou
stejné (zmax = fmin).
Věta 8.3.3
Má-li jedna z dvojice duálně sdružených úloh neomezenou hodnotu účelové funkce, druhá
úloha nemá přípustné řešení.
Věta 8.3.4
Nemá-li jedna z dvojice duálně sdružených úloh přípustné řešení, druhá úloha nemá optimální
řešení.
Další dvě věty říkají, že řešením jedné ze sdružených úloh získáme i řešení druhé úlohy a
optimální hodnoty duálních proměnných najdeme v indexním řádku výsledné simplexové
tabulky primární úlohy.
Věta 8.3.5
Optimální hodnoty strukturních proměnných duální úlohy se rovnají absolutním hodnotám
indexních čísel primárních přídatných proměnných.
Věta 8.3.6
Optimální hodnoty přídatných proměnných duální úlohy se rovnají absolutním hodnotám
indexních čísel primárních strukturních proměnných.
Příklad 8.3.1
Pomocí uvedených vět nalezneme optimální řešení úlohy LP z příkladu 8.1.1.
Řešení
Indexní řádek výsledné simplexové tabulky řešení primární úlohy (viz řešení příkladu 7.3.1)
má tvar:
Tabulka 8.3.1
Báze x1 x2 x3 x4 x5 bi
z 0 0 24 000 16 000 0 1 920 000
Tabulka 8.3.2 Určení optimálního řešení duálně sdružených úloh
Primární úloha
Strukturní proměnné Přídatné proměnné
x1 x2 x3 x4 x5 zmax
z 0 0 24 000 16 000 0 1 920 000
y4 y5 y1 y2 y3 fmin
Přídatné proměnné Strukturní proměnné
Duální úloha
Tabulka 8.3.2 pak byla sestavena s využitím vět 8.3.5, 8.3.6 a 8.3.1 a je z ní patrné optimální
řešení úlohy LP z příkladu 8.1.1.
.0009201,)0,0,0,00016,00024( min
T
opt fy
89
Firma by tedy za daných měla prodat 1 tunu kávových bobů K1 za 24 000Kč a 1 tunu
kávových bobů K2 za 16 000Kč, kávové boby K3 by pak neměla prodávat vůbec. Prodejní
cena každé suroviny je přesně taková, jakou by se daná surovina podílela na zisku z prodeje
jednotlivých druhů kávy, pokud by se káva vyráběla. Celkově by firma za prodané suroviny
získala 1 920 000Kč.
Vzhledem k tomu, že dualita je vztah vzájemný, je zřejmé, že vyřešením kterékoliv z dvojice
duálně sdružených úloh získáme současně řešení úlohy druhé. Můžeme si tedy vybrat, kterou
z dvojice duálně sdružených úloh řešit.
Věta 8.3.7 (o rovnováze)
Mějme dvojici symetrických duálně sdružených úloh takovou, že každá z nich má právě jedno
optimální řešení. Nechť je x = T21 ...,,, nxxx přípustné řešení primární úlohy a
y = T21 ...,,, myyy přípustné řešení příslušné duální úlohy. Tato řešení jsou optimální tehdy
a jen tehdy, když platí:
.0
0
0
0
1
1
1
1
i
n
j
jiji
i
n
j
jiji
j
m
i
iijj
j
m
i
iijj
bxay
bxay
cyax
cyax
Pozn.
Dvojice přípustných řešení duálně sdružených úloh s danými vlastnostmi je tedy podle věty o
rovnováze optimální tehdy a jen tehdy, když pro všechny dvojice sdružených omezení platí:
je-li jedno z dvojice duálně sdružených omezení splněno jako ostrá nerovnost, je druhé
omezení splněno jako rovnost a naopak.
Příklad 8.3.2
Ověříme, že optimální řešení dvojice duálně sdružených úloh z příkladů 7.1.1 a 8.1.1. splňují
větu o rovnováze.
Řešení
Pro primární úlohu máme
3,2,1,0
2525,0
605,05,0
4025,05,0
2
21
21
jx
x
xx
xx
j
a
.5,0,0,80,40T
opt x
Pro duální úlohu potom
90
3,2,1,0
0001425,05,025,0
000205,05,0
321
21
iy
yyy
yy
i
a
.)0,0,0,00016,00024( T
opt y
Řešení jsou nedegenerovaná a jsou tedy splněny předpoklady věty o rovnováze. Dosadíme
postupně optimální řešení obou úloh do jednotlivých dvojic duálně sdružených omezení.
Tabulka 8.3.3 Věta o rovnováze
Primární úloha Duální úloha
408025,0405,0 24 000 > 0
60805,0405,0 16 000 > 0
258025,0 0 = 0
40 > 0 00020000165,0000245,0
80 > 0 00014025,0000165,00002425,0
Vypočtená optimální řešení tedy splňují větu o rovnováze.
Příklad 8.3.3
Ukážeme si, jak lze pomocí vět o dualitě využít grafického řešení k nalezení optimálního
řešení úlohy LP se čtyřmi strukturními proměnnými. Máme nalézt maximum funkce
4321 530184 xxxxz
za podmínek
.4,3,2,1,0
342
343
4321
4321
jx
xxxx
xxxx
j
Řešení
Duální úloha: nalézt minimum funkce
21 33 yyf
za podmínek
.2,1,0
5
304
184
423
21
21
21
21
iy
yy
yy
yy
yy
i
Tuto úlohu vyřešíme graficky.
91
Obrázek 8.3.1 Řešení duální úlohy
Je tedy optimální řešení v bodě A a .36min f Souřadnice bodu A získáme zřejmě řešením
soustavy
.304
184
21
21
yy
yy
Snadno vypočítáme, že A[6, 6], tedy yopt = (6, 6)T.
Podle věty 8.3.1 existuje jediné optimální řešení primární úlohy a platí, že optimální
hodnota účelové funkce zmax = -36. Jelikož dosazením yopt do prvního a čtvrtého vlastního
omezení dostaneme ostré nerovnosti, platí podle věty 8.3.7, že
.0opt
4
opt
1 xx
Protože je dále ,06opt
2
opt
1 yy platí podle téže věty, že příslušná vlastní omezení
primární úlohy (první a druhé) jsou splněna jako rovnosti, tj.
.34
34
opt
3
opt
2
opt
3
opt
2
xx
xx
Řešením této soustavy získáváme
.17
15,
17
9 opt
3
opt
2 xx
Jediným optimálním řešením dané (primární) úlohy je tedy
.36,0,17
15,
17
9,0 max
T
opt
zx
92
Příklad 8.3.4
Papírny vyrábějí role papíru o délce 500 metrů ve standardní šířce 2 metry. Někteří odběratelé
však preferují menší šířky rolí, které jsou získávány z rolí standardních rozměrů jejich
dělením. V rámci jisté zakázky je třeba vyrobit alespoň 500ks rolí o šířce 0,5m, alespoň
1 000ks rolí o šířce 0,8m a alespoň 400ks rolí o šířce 1,2m. Ukážeme jak postupovat, aby byly
splněny požadavky odběratele a zároveň se spotřebovalo co nejméně výchozích rolí.
Řešení
Začneme tím, že si vypíšeme možné způsoby dělení výchozích rolí.
Tabulka 8.3.4 Varianty dělení
V1 V2 V3 V4 V5
0,5m (ks) 4 2 1 0 0
0,8m (ks) 0 1 0 2 1
1,2m (ks) 0 0 1 0 1
Odpad (m) 0 0,2 0,3 0,4 0
Dále matematický model.
Nechť xj označuje počet výchozích rolí rozdělených podle varianty Vj, j = 1, 2, 3, 4, 5.
Tyto proměnné mají splňovat omezení
5,4,3,2,1,0
400
00012
50024
53
542
321
jx
xx
xxx
xxx
j
a současně minimalizovat funkci
.54321 xxxxxz
Takovouto úlohu umíme zatím řešit pouze dvoufázovou simplexovou metodou. Nicméně je
zřejmé, že při řešení úlohy duální bychom vystačili s jednofázovou simplexovou metodou.
Formulujme tedy úlohu duální.
Maximalizovat funkci
321 4000001500 yyyf
za podmínek
.3,2,1,0
1
12
1
12
14
32
2
31
21
1
iy
yy
y
yy
yy
y
i
Pozn.
Pozornému čtenáři jistě neuniklo, že ignorujeme podmínky celočíselnosti, ale jak optimální
řešení za chvíli ukáže, můžeme si to dovolit.
93
Tabulka 8.3.5 Řešení duální úlohy simplexovou metodou
Báze y1 y2 y3 y4 y5 y6 y7 y8 bj
y4 4 0 0 1 0 0 0 0 1
y5 2 1 0 0 1 0 0 0 1
y6 1 0 1 0 0 1 0 0 1
y7 0 2 0 0 0 0 1 0 1
y8 0 1 1 0 0 0 0 1 1
f -500 -1 000 -400 0 0 0 0 0 0
y4 4 0 0 1 0 0 0 0 1
y5 2 0 0 0 1 0 21 0 2
1
y6 1 0 1 0 0 1 0 0 1
y2 0 1 0 0 0 0 21 0 2
1
y8 0 0 1 0 0 0 21 1 2
1
f -500 0 -400 0 0 0 500 0 500
y4 0 0 0 1 -2 0 1 0 0
y1 1 0 0 0 21 0 4
1 0 41
y6 0 0 1 0 21 1 4
1 0 43
y2 0 1 0 0 0 0 21 0 2
1
y8 0 0 1 0 0 0 21 1 2
1
f 0 0 -400 0 250 0 375 0 625
y4 0 0 0 1 -2 0 1 0 0
y1 1 0 0 0 21 0 4
1 0 41
y6 0 0 0 0 21 1 4
3 -1 41
y2 0 1 0 0 0 0 21 0 2
1
y3 0 0 1 0 0 0 21 1 2
1
f 0 0 0 0 250 0 175 400 825
Z výsledné simplexové tabulky je vidět řešení obou duálně sdružených úloh. Máme
.825,0,0,4
1,0,0,
2
1,
2
1,
4
1
,825,)0,0,0,400,175,0,250,0(
max
T
opt
min
T
opt
f
z
y
x
Postup dělení rolí, který uspokojí požadavky odběratele a minimalizuje spotřebu výchozích
rolí, spočívá v rozdělení 250 rolí podle varianty V2, 175 rolí podle varianty V4 a 400 rolí
podle varianty V5. Při tomto postupu nebude žádná z požadovaných kratších šířek přebývat a
bude spotřebováno 825 výchozích dvoumetrových rolí.
Vzhledem ke skutečnosti, že je optimální řešení duální úlohy degenerované, má podle
věty 8.3.2 primární úloha alternativní optimální řešení a popsaný postup tedy není jediný,
který zajistí spotřebu 825 výchozích rolí. K druhému základnímu optimálnímu řešení primární
úlohy bychom se dostali alternativní volbou vystupující proměnné y4 místo proměnné y5
(stejné podíly).
Další pozoruhodností řešení této úlohy je skutečnost, že pro uvedená optimální řešení
duálně sdružených úloh není splněno tvrzení věty o rovnováze, protože ,140 opt
1
opt
1 yx
což jenom potvrzuje oprávněnost předpokladů této věty.
94
8.4 Ekonomická interpretace duálních proměnných
Uvažujme dvojici duálně sdružených úloh (8.1.1) a (8.1.2), které mají optimální řešení.
Věta 8.4.1
Optimální hodnota strukturní duální proměnné udává změnu optimální hodnoty účelové
funkce připadající na jednotkovou změnu pravé strany příslušného omezení v primární úloze.
Důkaz této věty lze odvodit z rovnosti optimálních hodnot účelových funkcí dvou duálně
sdružených úloh (viz věty 8.3.1 a 8.3.2). Známe-li optimální hodnoty strukturních duálních
proměnných optopt
2
opt
1 ...,,, myyy , můžeme optimální hodnotu účelové funkce primární úlohy
vyjádřit ve tvaru
.... optopt
22
opt
11minmax mm ybybybfz
Předpokládejme nyní změnu požadavkového čísla bk o hodnotu Δbk,, kde mk 1 .
Označíme-li odpovídající změnu optimální hodnoty účelové funkce z , platí
,...)(... optoptopt
22
opt
11max mmkkk ybybbybybzz
odkud po úpravě dostaneme vztah
opt
kk ybz , tedy .opt
k
kb
zy
Z odvozeného zlomku pak vyplývá tvrzení věty 8.4.1. Jestliže se omezující podmínka zmírní,
tzn. v nerovnicích „≤“ se pravá strana zvýší nebo v nerovnicích „≥“ se sníží, optimální
hodnota účelové funkce se zlepší, tj. v maximalizačních úlohách se zvýší a v případě
minimalizační účelové funkce se sníží. Naopak zpřísnění omezující podmínky, tj. snížení
pravé strany nerovnice „≤“ nebo zvýšení pravé strany nerovnice „≥“ , má za následek
zhoršení optimální hodnoty účelové funkce. Optimální hodnoty strukturních duálních
proměnných tedy představují ocenění činitelů tvořících jednotlivé omezující podmínky
primární úlohy a bývají někdy nazývány jejich stínovými cenami. Konkrétní význam tohoto
názvu je dobře patrný z řešení příkladu 8.1.1.
Příklad 8.4.1
Z výsledné simplexové tabulky 7.3.3 úlohy o výrobě dvou směsí kávy určíme, jak by se
změnila hodnota maximálního zisku, kdyby suroviny
a) K1; b) K2; c) K3
bylo za jinak nezměněných podmínek k dispozici o 5 tun víc.
Řešení
Podle věty 8.4.1 postupně máme
a) ;000120500024max z
b) ;00080500016max z
c) .050max z
Vzhledem k tomu, že při optimálním výrobním programu se surovina K3 nespotřebuje
v původním množství, její navýšení by nepřineslo změnu maximálního zisku. Je třeba si
ovšem uvědomit, že kdyby došlo např. ke snížení kapacity K3 pod určitou mez (zde je to 20
tun), potom by se tato surovina stala nedostatkovou, což by pochopitelně mělo vliv na
optimální řešení. Existují tedy pro všechny kapacity zdrojů konkrétní intervaly, tzv. intervaly
95
stability, v rámci kterých lze úvahy podobného typu provádět. Určováním intervalů stability
se zde zabývat nebudeme. Spokojíme se na tomto místě pouze s konstatováním, že zvýšením
jednotlivých kapacit o uvažovaných 5 tun (při současné fixaci zbývajících) se do intervalů
stability vejdeme.
Věta 8.4.2
Optimální hodnota přídatné duální proměnné udává, o kolik by se zhoršila optimální hodnota
účelové funkce zařazením jedné jednotky této proměnné do řešení.
Pozn.
Jinými slovy optimální hodnota přídatné duální proměnné udává, o kolik je třeba cenu této
nezákladní proměnné v maximalizační úloze zvýšit a v minimalizační úloze snížit, aby se
stala základní proměnnou.
Příklad 8.4.2
Z výsledné simplexové tabulky 7.3.3 úlohy o výrobě dvou směsí kávy je zřejmé, že obě
optimální hodnoty přídatných duálních proměnných jsou nulové. Obě směsi tedy mají
výhodný jednotkový zisk, který není třeba zvyšovat.
Uveďme ještě na závěr ekonomickou interpretaci věty o rovnováze, kterou lze dobře
ilustrovat na úloze optimálního výrobního plánování.
Je-li výrobní zdroj nevyužit ( i
n
j
jij bxa 1
opt ), jeho ocenění je nulové ( 0opt iy ), zatímco
při vyčerpání výrobního zdroje ( i
n
j
jij bxa 1
opt ) jeho ocenění je kladné ( 0opt iy ).
Je-li ocenění všech výrobních činitelů spotřebovaných na určitý výrobek větší než zisk,
který tento výrobek vynáší ( j
m
i
iij cya 1
opt ), jde o nerentabilní výrobek ( 0opt jx ). Jestliže
zisk určitého výrobku je stejný jako ocenění všech spotřebovaných výrobních činitelů
( j
m
i
iij cya 1
opt ), je výhodné tento výrobek vyrábět ( 0opt jx ).
8.5 Duálně simplexová metoda
V řešení příkladu 8.3.4 jsme postupovali tak, že jsme k primární úloze vytvořili úlohu duální,
kterou bylo možné řešit jednofázovou simplexovou metodou. Duální úlohu jsme vyřešili a
z výsledné simplexové tabulky nalezli optimální řešení primární úlohy. Nabízí se otázka, zda
by nebylo možné použít metodu, která by umožňovala řešit duální úlohu přímo v simplexové
tabulce úlohy primární. Tím bychom si totiž mohli ušetřit sestavování úlohy duální a
optimální řešení primární úlohy by se objevilo standardně v posledním sloupci výsledné
tabulky. Jednotlivé kroky takové metody by jistě bylo možné odvodit ze vztahů mezi řádky a
sloupci simplexových tabulek dvou duálně sdružených úloh.
Metoda, o které hovoříme, byla vytvořena a nazývá se duálně simplexová metoda. Před
jejím vysvětlením definujme dva důležité pojmy.
96
Definice 8.5.1
Řešení úlohy lineárního programování je primárně přípustné, když všechny jeho základní
proměnné jsou nezáporné, tzn. sloupec b v simplexové tabulce obsahuje pouze nezáporná
čísla (kromě hodnoty účelové funkce).
Definice 8.5.2
Řešení úlohy lineárního programování je duálně přípustné, když v maximalizačních
(minimalizačních) úlohách všechna indexní čísla v simplexové tabulce jsou nezáporná
(nekladná).
Je-li řešení v simplexové tabulce primárně i duálně přípustné a hodnoty účelové funkce
primární i duální úlohy stejné, platí podle vět 8.3.1 a 8.3.2, že toto řešení je optimální.
Při primárně simplexové metodě se vychází z řešení primárně přípustného, ale duálně
nepřípustného a provádějí se takové kroky, aby při zachování primární přípustnosti se získalo
řešení i duálně přípustné. Při duálně simplexové metodě je postup opačný. Výchozí řešení je
duálně přípustné, ale primárně nepřípustné a v jednotlivých krocích se při zachování duální
přípustnosti upravuje tak, aby se stalo řešením i primárně přípustným. Při duálně simplexové
metodě nejdříve stanovíme vystupující proměnnou a pak teprve vstupující proměnnou.
Věta 8.5.1
Z řešení vystoupí proměnná s nejnižší zápornou hodnotou. Tato proměnná určuje klíčový
řádek.
Věta 8.5.2
Do řešení vstoupí proměnná, pro kterou vyjde nejmenší absolutní hodnota podílů indexních
čísel nezákladních proměnných a odpovídajících záporných koeficientů v klíčovém řádku.
Pozn.
Klíčový prvek je tedy vždy záporný.
Přechod mezi jednotlivými základními řešeními spočívá tedy rovněž ve výměně jedné
základní a jedné nezákladní proměnné a provádí se opět Jordanovou metodou.
Pomocí duálně simplexové metody lze řešit například minimalizační úlohy s
nezápornými koeficienty v účelové funkci, které mají omezující podmínky vesměs vyjádřeny
nerovnicemi, z nichž alespoň jedna je typu „≥“ .
Příklad 8.5.1
Tři prvky A, B a C jsou obsaženy ve čtyřech různých sloučeninách S1, S2, S3, a S4. Obsah
prvků v jednotlivých sloučeninách, jakož i ceny sloučenin a požadované množství prvků
uvádí tabulka 8.5.1
Tabulka 8.5.1
S1 (kg) S2 (kg) S3 (kg) S4 (kg) Požadované
množství (kg)
A (g) 0 2 4 5 5
B (g) 2 2 0 4 6
C (g) 10 5 4 10 18
Cena (kg) 150 100 120 250
Určíme, které sloučeniny a v jakém množství je třeba nakoupit, abychom získali požadované
množství prvků za nejnižší cenu.
97
Řešení
Označíme-li xj nakoupené množství suroviny Sj v kg ( 4,3,2,1j ), máme za úkol
minimalizovat funkci
4321 250120100150 xxxxz
za podmínek
.4,3,2,1,0
00018104510
0006422
0005542
4321
421
432
jx
xxxx
xxx
xxx
j
Každé z vlastních omezení vynásobíme číslem (-1) a doplníme pomocí přídatné proměnné na
rovnici. Takto vzniklá soustava rovnic bude v kanonickém tvaru. Výpočet optimálního řešení
provedeme popsanou duálně simplexovou metodou. Tuto metodu je možné použít, protože
vycházíme z duálně přípustného řešení - viz poslední řádek výchozí simplexové tabulky
8.5.2. Z této tabulky jsou patrné i jednotlivé kroky výpočtu a volby klíčových prvků.
Tabulka 8.5.2 Duálně simplexová metoda
Báze x1 x2 x3 x4 x5 x6 x7 bi
x5 0 -2 -4 -5 1 0 0 -5 000
x6 -2 -2 0 -4 0 1 0 -6 000
x7 -10 -5 -4 -10 0 0 1 -18 000
z -150 -100 -120 -250 0 0 0 0
x5 0 -2 -4 -5 1 0 0 -5 000
x6 0 -1 54 -2 0 1 10
2 -2 400
x1 1 21
52 1 0 0 10
1 1 800
z 0 -25 -60 -100 0 0 -15 270 000
x2 0 1 2 25
21 0 0 2 500
x6 0 0 514
21
21 1 10
2 100
x1 1 0 53 1 0 0 10
1 550
z 0 0 -10 -37,5 -12,5 0 -15 332 500
Nejlevněji tedy zajistíme požadované množství prvků nákupem 550kg sloučeniny S1 a
2 500kg sloučeniny S2 v celkové ceně 332 500Kč. Při této variantě získáme ještě navíc 100g
prvku B. Čtenář si může v rámci cvičení vyřešit tutéž úlohu dvoufázovou simplexovou
metodou, aby docenil jednoduchost demonstrovaného postupu.
Věta 8.5.3
Jestliže při duálně simplexovém algoritmu klíčový řádek obsahuje pouze nezáporná čísla,
hodnota účelové funkce příslušné duální úlohy je neomezená.
Pozn.
Podle věty 8.3.3 tedy nemá příslušná primární úloha přípustné řešení.
98
Příklad 8.5.2
Duálně simplexovou metodou vyřešíme úlohu
.min35
2,1,0
1427
10
21
21
21
xxz
jx
xx
xx
j
Řešení Po vynásobení 1. nerovnice číslem (-1) a po zavedení přičítaných přídatných proměnných
získáme řešení duálně přípustné, ale primárně nepřípustné, které je zapsáno v 1. části tabulky
8.5.3 Po 1. kroku duálně simplexové metody získáme řešení, které je ještě primárně
nepřípustné, ale v řádku vystupující proměnné x4 jsou pouze nezáporná čísla. Daná úloha
tedy podle věty 8.5.3 a poznámky za ní nemá přípustné řešení.
Tabulka 8.5.3
Báze x1 x2 x3 x4 bi
x3 -1 -1 1 0 -10
x4 7 2 0 1 14
z -5 -3 0 0 0
x2 1 1 -1 0 10
x4 5 0 2 1 -6
z -2 0 -3 0 30
Cvičení
8.1 K dané úloze
.3,2,1,0
254210
205
min5765105
321
321
321
jx
xxx
xxx
xxxz
j
sestavte úlohu duální.
8.2 K dané úloze
.3,2,1,0
17432
842
5
max116
321
32
31
321
jx
xxx
xx
xx
xxxz
j
sestavte úlohu duální tak, aby s ní byla
a) symetricky sdružená;
b) smíšeně symetricky sdružená.
99
8.3 Je dána úloha lineárního programování
.3,2,1,0
7823
120444
max482460
321
321
321
jx
xxx
xxx
xxxz
j
Pomocí věty o rovnováze rozhodněte, zda jsou vektory
TT )12,6(a)12,0,18( yx
optimálními řešeními dané úlohy a úlohy s ní duálně sdružené.
8.4 Je dána úloha lineárního programování
.3,2,1,0
3623
72333
min14496144
321
321
321
jx
xxx
xxx
xxxz
j
Pomocí duálně simplexové metody nalezněte optimální řešení této úlohy i úlohy s ní
duálně sdružené.
8.5 Následující tabulka je výsledná simplexová tabulka úlohy LP, ve které se určoval
maximální zisk (v Kč) při výrobě tří výrobků (v kg) za předpokladu, že výroba byla
omezena daným disponibilním množstvím dvou surovin (v kg). Z tabulky určete:
a) optimální řešení primární úlohy;
b) optimální řešení duální úlohy;
c) maximální zisk za předpokladu, že by první suroviny bylo o 10kg více;
d) maximální zisk za předpokladu, že by druhé suroviny bylo o 5kg méně;
e) maximální zisk za předpokladu, že by v úloze byla přidána podmínka o nutnosti
vyrobit alespoň 2kg třetího výrobku.
Báze x1 x2 x3 x4 x5 bi
x1 1 0 3 -1 2 20
x2 0 1 -1 1 -1 30
z 0 0 9 1 8 480
Úkoly c), d) a e) řešte za předpokladu, že se při uvedených změnách v zadání ostatní
parametry zachovají a že změny v disponibilním množství surovin nezpůsobí změnu
struktury optimálního řešení.
8.6 Řešte úlohu z příkladu 8.3.4 duálně simplexovou metodou. Nalezněte druhé základní
optimální řešení primární úlohy a ověřte, zda toto řešení spolu s optimálním řešením
duální úlohy splňuje tvrzení věty o rovnováze.
100
9. Dopravní úlohy
9.1 Formulace dopravní úlohy
Dopravní úloha patří mezi tzv. distribuční úlohy, ve kterých jde o distribuci neboli
rozdělování určitých prostředků z míst jejich zdrojů na místa jejich potřeby.
Představme si, že chceme distribuovat určité komodity (zboží, výrobky, materiál apod.) od
m dodavatelů k n odběratelům. Naší snahou přirozeně bude pokud možno uspokojit všechny
požadavky odběratelů, vyčerpat výrobní kapacity dodavatelů a přitom určit způsob přepravy
komodit tak, aby sledovaná veličina (celkový rozsah přepravy, náklady na přepravu atd.) byla
minimální.
Označme:
xij njmi ...,,2,1;,...,2,1 …přepravované množství zboží od i-tého dodavatele k j-tému
odběrateli (tzv. strukturní neznámé);
ai mi ...,,2,1 … kapacita i-tého dodavatele;
bj nj ...,,2,1 … požadavek j-tého odběratele;
cij njmi ...,,2,1;,...,2,1 …ocenění spojení mezi i-tým dodavatelem a j-tým
odběratelem (tzv. cenové koeficienty).
Úlohou je tedy nalézt neznámé xij, které splňují podmínky
mmnmm
n
n
axxx
axxx
axxx
...
...
...
21
222221
111211
(9.1.1)
nmnnn
m
m
bxxx
bxxx
bxxx
...
...
...
21
222212
112111
(9.1.2)
a současně minimalizují funkci
mnmnmmmm
nn
nn
xcxcxc
xcxcxc
xcxcxcz
...
...
...
2211
2222222121
1112121111
(9.1.3)
Doplníme-li soustavy rovnic (9.1.1), (9.1.2) a funkci (9.1.3) podmínkami nezápornosti všech
neznámých xij, získáme úlohu lineárního programování s (m + n) vlastními omezujícími
podmínkami a s mn neznámými.
Matematický model dopravní úlohy se vyznačuje některými zvláštnostmi, kvůli kterým
jsme jej nezařadili mezi zbývající typy úloh lineárního programování, ale pojednáváme o něm
zvlášť. Vypišme ty nejpodstatnější odlišnosti:
- všechna vlastní omezení jsou vyjádřena rovnicemi;
- vektor koeficientů každé proměnné xij má pouze dvě nenulové složky, a to jedničky
na i-tém a (j + m)-tém místě;
101
- jednotlivé neznámé i pravé strany všech omezujících podmínek jsou vyjádřeny ve
stejné měrné jednotce, což umožňuje přímý výpočet výchozího řešení;
- po vhodné úpravě mohou být jak kapacity dodavatelů a požadavky odběratelů, tak i
všechny proměnné vyjádřeny celými čísly, takže odpadá problém s neceločíselností
výsledku.
Zadání dopravního problému můžeme přehledně zapsat do tabulky (budeme ji nadále
nazývat dopravní tabulkou), v níž se zpravidla jednotlivé řádky vztahují k dodavatelům a
sloupce k odběratelům. Obecný tvar dopravní tabulky představuje tabulka 9.1.1, ve které jsou
kromě vstupních dat ai, bj, cij zapsány též neznámé xij. Schéma této tabulky usnadňuje
matematickou formulaci dopravního problému a v dopravní tabulce též výhodně úlohy
řešíme.
Tabulka 9.1.1 Obecná dopravní tabulka
O1 O2 …… On Kapacity
D1 c11
x11
c12
x12 ……
c1n
x1n a1
D2 c21
x21
c22
x22 ……
c2n
x2n a2
:
:
:
:
:
: ……
:
: :
:
Dm cm1
xm1
cm2
xm2 ……
cmn
xmn am
Požadavky b1 b2 …… bn
Vzhledem k umístění kapacit dodavatelů a požadavků odběratelů v dopravní tabulce budeme
tato čísla nazývat okrajovými podmínkami. Číslům cij budeme říkat sazby. Pokud bude
proměnná xij kladná, řekneme, že políčko (i, j) je obsazené.
9.2 Vlastnosti dopravní úlohy
Definice 9.2.1
Dopravní problém nazýváme vyrovnaný, jestliže součet kapacit dodavatelů se rovná součtu
požadavků odběratelů, tzn. pokud platí
m
i
n
j
ji ba1 1
. (9.2.1)
Jestliže uvedená rovnost neplatí, nazýváme dopravní problém nevyrovnaný.
Při splnění rovnosti (9.2.1) je možné libovolnou rovnici v soustavě (9.1.1) vyjádřit jako součet
rovnic soustavy (9.2.2), zmenšený o součet zbývajících rovnic soustavy (9.1.1) (stejný vztah
platí pro libovolnou rovnici soustavy (9.2.2)).
Věta 9.2.1
Počet nezávislých rovnic v soustavě vlastních omezujících podmínek vyrovnaného
dopravního problému s m dodavateli a n odběrateli je (m + n – 1), tzn. základní přípustné
řešení dopravního problému obsahuje maximálně (m + n – 1) kladných složek. Aby řešení
bylo základní, nesmí navíc spojením obsazených políček svislými a vodorovnými čarami
vzniknout uzavřený okruh.
102
Co rozumíme uzavřeným okruhem, je zřejmé z tabulek 9.2.1 a 9.2.2, ve kterých jsou křížky
označena obsazená políčka. Počet obsazených políček v obou tabulkách je stejný, rovný číslu
(m + n - 1) = 3 + 3 - 1 = 5. Obsazená políčka v tab. 9.2.1 nelze spojit vodorovnými a svislými
čarami v uzavřený obvod, takže řešení v této tabulce je základní. Naproti tomu obsazená
políčka (1, 1), (1, 3), (2, 3), (2, 1) v tabulce 9.2.2 lze spojit v uzavřený obvod, takže toto
řešení není základní.
Tabulka 9.2.1 Základní řešení
+ +
+ +
+
Tabulka 9.2.2 Nezákladní řešení
+ +
+ +
+
Definice 9.2.2
Základní řešení dopravního problému s m dodavateli a n odběrateli, které obsahuje méně než
(m + n – 1) kladných složek se nazývá degenerované základní řešení dopravního problému.
Pozn.
Řešením dopravních problémů, ve kterých se vyskytne degenerované základní řešení, se
budeme systematicky věnovat později v části 9.5.
Věta 9.2.2
Každý vyrovnaný dopravní problém je řešitelný.
Důkaz
Snadno lze ověřit, že přípustným řešením dopravního problému za podmínky (9.2.1) jsou
např. hodnoty K
bax
ji
ij , kde
n
j
j
m
i
i baK11
.
Při řešení praktických dopravních úloh se zpravidla nerovná úhrn kapacit dodavatelů úhrnu
požadavků odběratelů, tedy neplatí rovnost (9.2.1) a dopravní problém je nevyrovnaný. Aby
byla splněna podmínka řešitelnosti dopravního problému, tj. rovnost (9.2.1), stačí každý
nevyrovnaný dopravní problém převést na vyrovnaný pomocí tzv. fiktivního dodavatele nebo
fiktivního odběratele.
Jestliže platí
m
i
n
j
ji ba1 1
, úlohu rozšíříme o fiktivního dodavatele, který „dodá“
nedostávající se množství. Zavedení fiktivního dodavatele si vyžádá připojení dalšího řádku
k dopravní tabulce s okrajovou podmínkou rovnou nedostávajícímu se množství, tzn. rozdílu
n
j
m
i
ij ab1 1
. Dodávky od fiktivního dodavatele znamenají výši neuspokojených požadavků
jednotlivých odběratelů a protože jejich přeprava se nepodílí na celkovém rozsahu dopravy,
volíme v řádku fiktivního dodavatele všechny sazby nulové, pokud ovšem některý spotřebitel
103
není preferován a nevyžaduje uspokojení svého požadavku od skutečných dodavatelů.
V tomto případě spoj od fiktivního dodavatele k preferovanému spotřebiteli zablokujeme
vysokou tzv. prohibitivní sazbou, která se řádově liší od ostatních sazeb v dopravní tabulce.
Jestliže platí
m
i
n
j
ji ba1 1
, úlohu rozšíříme o fiktivního odběratele, který „odebere“
přebytečné kapacity. V dopravní tabulce přiřadíme fiktivnímu odběrateli další sloupec
s okrajovou podmínkou rovnou přebývajícímu množství, tzn. rozdílu
m
i
n
j
ji ba1 1
. Protože
přebývající množství u dodavatelů se zpravidla nikam nedopravuje, ve sloupci fiktivního
odběratele volíme sazby nulové, pokud nejde o preferovaného dodavatele, jehož kapacita
musí být rozdělena mezi skutečné odběratele. V tomto případě spoj od tohoto dodavatele
k fiktivnímu odběrateli zablokujeme vysokou prohibitivní sazbou.
Příklad 9.2.1
V jednom lyžařském středisku se vyrábí na třech místech umělý sníh, kterého je k dispozici
postupně 100 tun, 80 tun a 50 tun. Tento sníh má být rozvezen na dvě sjezdovky a jeden
běžecký okruh, přičemž požadavky znějí postupně na 20 tun, 50 tun, 130 tun sněhu. Průměrné
vzdálenosti mezi jednotlivými místy, kde se umělý sníh vyrábí a místy jeho potřeby (v km),
jsou uvedeny v tabulce 9.2.3. Ukážeme si v dopravní tabulce postup vyrovnání dané dopravní
úlohy za podmínky, že z místa, kde je k dispozici 100 tun sněhu, má být odvezena celá
zásoba. Dále zformulujeme matematický model.
Tabulka 9.2.3 Sazby
O1 O2 O3
D1 10 7 5
D2 4 12 6
D3 7 2 3
Řešení
Celkové množství vyrobeného umělého sněhu je 230 tun, zatímco jeho potřeba je pouze
200 tun. Je proto nutné zavést fiktivní místo odběru, které „odebere“ přebývajících 30 tun
umělého sněhu. Protože z místa D1 musí být všechno odvezeno, zablokujeme spojení od
tohoto místa k fiktivnímu odběrateli prohibitivní sazbou např. ve výši 100 (o řád vyšší než
ostatní sazby). Takto upravený a již řešitelný vyrovnaný dopravní problém je zapsán v tabulce
9.2.4
Tabulka 9.2.4 Vyrovnání dopravního problému
O1 O2 O3 FO Kapacity
D1 10 7 5 100
100
D2 4 12 6 0
80
D3 7 2 3 0
50
Požadavky 20 50 130 30 230
104
Zdůrazněme ještě jednou, že přebytečný sníh se nikam vozit nebude, zůstane tam, kde byl
vyroben. Zavedení fiktivního odběratele slouží pouze k tomu, aby byla úloha matematicky
řešitelná a v našem konkrétním případě navíc, aby nadbytečný sníh nezůstal na místě D1.
9.3 Metody určení výchozího základního řešení dopravní úlohy
Přestože dopravní problém jakožto úlohu lineárního programování lze řešit univerzální
simplexovou metodou, zvláštnosti jeho matematického modelu vedly k vypracování
speciálních, výhodnějších metod pro jeho řešení, které se realizují přímo v dopravní tabulce.
Všechny tyto metody mají společný postup (podobný jako u simplexové metody), který
spočívá v provedení následujících kroků:
- získání výchozího základního přípustného řešení;
- test optima;
- přechod k jinému základnímu řešení s lepší hodnotou účelové funkce, pokud
testované řešení nebylo optimální.
V tomto odstavci si popíšeme některé metody, které se používají při určování výchozího
základního řešení. Tyto metody se liší svou náročností. Ve výkladu budeme postupovat od
jednodušších k složitějším a současně uvidíme, že větší obtížnost při určování výchozího
základního řešení se vrátí v tom, že příslušné výchozí základní je většinou „blíže“
k optimálnímu řešení ve smyslu velikosti hodnoty odpovídající účelové funkce.
Příklad 9.3.1
V regionu jsou tři pískovny a čtyři stavby, na nichž se písek používá. Kapacity pískoven a
požadavky stavenišť (obojí v tunách) stejně jako vzdálenosti mezi pískovnami a stavbami (v
km) jsou v tabulce 9.3.1. Je třeba určit, odkud si budou jednotlivé stavby odvážet písek tak,
aby jejich požadavky byly uspokojeny a celkový rozsah přepravy (v tkm) byl minimální.
Tabulka 9.3.1
S1 S2 S3 S4 Kapacity
P1 44 23 14 19
495
P2 22 14 20 3
475
P3 8 36 30 49
390
Požadavky 460 300 575 25 1 360
Ukážeme tři metody určení výchozího základního řešení této úlohy a odpovídající hodnoty
účelové funkce (celkový rozsah přepravy).
Řešení
Z tabulky 9.3.1 je vidět, že se jedná o vyrovnaný dopravní problém. Platí, že
36011 1
m
i
n
j
ji ba tun.
105
1) Metoda severozápadního rohu
Při této metodě nejprve obsadíme políčko v severozápadním, tj. levém horním rohu tabulky
9.3.2. Aby tato hodnota, tj. hodnota neznámé x11, uspokojila alespoň jednu z okrajových
podmínek, volíme x11 = min(a1, b1). V našem případě x11 = min(495, 460) = 460 a protože
touto hodnotou je uspokojena okrajová podmínka prvního sloupce, zbývající políčka v tomto
sloupci proškrtneme (hodnoty odpovídajících neznámých jsou nulové). Dále určíme hodnotu
neznámé x12, a to opět jako minimum již z pozměněných okrajových podmínek. Konkrétně
min(495 - 460, 300) = 35. Obsazením políčka (1, 2) hodnotou 35 je uspokojena okrajová
podmínka v prvním řádku, takže zbývající políčka v tomto řádku proškrtneme a přejdeme ke
stanovení hodnoty x22. Uvedeným způsobem určujeme hodnoty ostatních proměnných,
přičemž postupujeme od levého horního k pravému dolnímu rohu tabulky, tzn. od každého
obsazeného pole buď napravo nebo dolů. Výpočet končí vyčerpáním kapacit všech
dodavatelů a uspokojením požadavků všech odběratelů. Tabulka 9.3.2 ukazuje základní řešení
získané metodou severozápadního rohu.
Tabulka 9.3.2 Metoda severozápadního rohu
S1 S2 S3 S4 Kapacity
P1 44
460
23
35
14
-
19
- 495
P2 22
-
14
265
20
210
3
- 475
P3 8
-
36
-
30
365
49
25 390
Požadavky 460 300 575 25 1 360
Dostáváme výchozí základní řešení
T
1 )25,365,0,0,0,210,265,0,0,0,35,460(x
a pro odpovídající hodnotu účelové funkce máme
.1304125493653021020265143523460441 z
Tomuto řešení odpovídá situace, kdy se bude z P1 vozit 460 tun písku do S1 a 35 tun do S2.
Z pískovny P2 se bude na stavbu S2 vozit 265 tun a na stavbu S3 210 tun. Konečně z pískovny
P3 se bude vozit písek na stavby S3 (365 tun) a S4 (25 tun). Celkový rozsah přepravy bude
činit 41 130tkm.
Pokud by čtenář něco zásadního namítal proti volbě právě severozápadního rohu, může si
klidně jako výchozí místo zvolit roh jihozápadní. Podstata metody bude stejná, pouze název
by asi měl být jiný.
2) Indexová metoda
Při indexové metodě seřadíme sazby od nejmenší k největší a v tomto pořadí obsazujeme
políčka vždy maximálně možnou hodnotou. Jestliže nejnižší sazba je stejná ve více polích,
přednost dáme políčku, které můžeme obsadit větší hodnotou. V našem případě budeme pole
obsazovat v pořadí (2, 4), (3, 1), (1, 3), (2, 2) atd., pokud některé z těchto polí nebude již
proškrtnuto po obsazení polí s nižšími sazbami. Postup řešení je patrný z tabulky 9.3.3.
106
Tabulka 9.3.3 Indexová metoda
S1 S2 S3 S4 Kapacity
P1 44
70
23
-
14
425
19
- 495
P2 22
-
14
300
20
150
3
25 475
P3 8
390
36
-
30
-
49
- 390
Požadavky 460 300 575 25 1 360
Dostáváme výchozí základní řešení
T
2 )0,0,0,390,25,150,300,0,0,425,0,70(x
a pro odpovídající hodnotu účelové funkce máme
.42519390825315020300144251470442 z
Interpretace tohoto výchozího základního řešení je jistě zřejmá. Za zmínku stojí podstatné
snížení hodnoty účelové funkce na 19 425tkm.
3) Vogelova aproximační metoda (VAM)
Na rozdíl od indexové metody u VAM neurčujeme výhodnost nebo nevýhodnost polí podle
absolutní velikosti příslušných sazeb, ale přihlížíme k jejich relativní výhodnosti. Přednostně
obsadíme pole s tou malou sazbou, od které se nejblíže vyšší sazba v odpovídající řadě (tj.
řádku nebo sloupci) co nejvíce liší. Kdybychom totiž toto pole neobsadili, obsazení pole
s nejblíže vyšší sazbou by znamenalo velké zvýšení hodnoty účelové funkce.
Algoritmus VAM probíhá v těchto krocích (připomeňme, že termínem řada souhrnně
označujeme řádek nebo sloupec):
- V každé řadě stanovíme rozdíl mezi dvěma nejnižšími sazbami v dosud
neproškrtnutých políčkách (pokud v dopravní tabulce je řádek fiktivního dodavatele
nebo sloupec fiktivního odběratele, uvažují se i nulové sazby v těchto řadách).
- V řadě s nejvyšším rozdílem najdeme pole s nejnižší sazbou a to přednostně
obsadíme maximálně možným množstvím. Pokud tento rozdíl vyjde stejný pro více
řad, hledáme v nich tzv. sedlový bod, tj. pole s nejmenší sazbou z hlediska řádku i
sloupce. Pokud sedlový bod neexistuje, obsadíme políčko s nejnižší sazbou nebo
políčko, které můžeme obsadit větším množstvím.
- Po uspokojení řádkové (sloupcové) okrajové podmínky zbývající políčka v příslušné
řadě proškrtneme, přepočítáme sloupcové (řádkové) rozdíly a postup opakujeme tak
dlouho, až v dopravní tabulce zbude jen jeden nevyplněný řádek nebo sloupec.
Potom stačí obsadit neproškrtnutá políčka v této řadě zbylými kapacitami nebo
požadavky.
V tabulce 9.3.4 je popsaný algoritmus aplikován na řešení příkladu 9.3.1. Dopravní tabulka je
rozšířena o sloupce s řádkovými diferencemi a o řádky se sloupcovými diferencemi
počítanými v jednotlivých krocích. Postupně byla obsazována plíčka (3, 1), (2, 1), (2, 4),
(1, 3) - sedlový bod a nakonec v libovolném pořadí (2, 2) a (2, 3).
107
Tabulka 9.3.4 Metoda VAM
S1 S2 S3 S4 Kapacity
Řádkové
rozdíly
P1 44
-
23
-
14
495
19
- 495 5 5 9
P2 22
70
14
300
20
80
3
25 475 11 11 6
P3 8
390
36
-
30
-
49
- 390 22 x
Požadavky 460 300 575 25 1 360
Sloupcové
rozdíly
14 9 6 16
22 9 6 16
x x
Z tabulky 9.3.4 dostáváme výchozí základní řešení
T
3 )0,0,0,390,25,80,300,70,0,495,0,0(x
a pro odpovídající hodnotu účelové funkce máme
.4851639082538020300147022495143 z
Metodou VAM jsme tedy získali řešení s hodnotou účelové funkce 16 485tkm.
Metoda VAM poskytuje obvykle řešení nejlepší. Pro malé dopravní úlohy (do rozměru 5 x 5)
to může často být dokonce i řešení optimální. Proto je vhodné nenechat se odradit její
relativní obtížností a používat ji.
9.4 Nalezení optimálního řešení dopravní úlohy
Jednou z možností, jak získat optimální řešení dopravního problému, je použití zavedené
dvoufázové simplexové metody. Vzhledem k některým vlastnostem matematického modelu
dopravního problému (velký počet neznámých, všechna vlastní omezení ve tvaru rovnic
vyžadujících zavedení umělých proměnných) se běžně simplexová metoda pro řešení
dopravního problému nepoužívá a využívá se toho, že lze poměrně snadno získat výchozí,
základní, primárně přípustné řešení. Aby toto řešení bylo optimální, musí být též duálně
přípustné, což lze ověřit pomocí tzv. MODI metody (modifikované distribuční metody)
založené na vztazích mezi duálně sdruženými úlohami.
Vzhledem k tomu, že všechna vlastní omezení dopravního problému jsou ve tvaru rovnic
a že jde o úlohu minimalizační, žádná z duálních proměnných nemusí splňovat podmínky
nezápornosti a všechna vlastní omezení duální úlohy jsou vyjádřena nerovnicemi typu „≤“
(jde tedy o nesymetrickou dualitu).
Duální proměnné, které jsou přiřazeny omezujícím podmínkám dodavatelů, označujeme
muuu ...,,, 21 a duální proměnné, které se vztahují k odběratelům, označujeme nvvv ...,,, 21 .
Příklad 9.4.1
Sestavíme duální úlohu k dopravní úloze se dvěma dodavateli a třemi odběrateli.
108
Řešení
Primární úloha:
.min
3,2,1,2,1,0
232322222121131312121111
32313
22212
12111
2232221
1131211
xcxcxcxcxcxcz
jix
bxx
bxx
bxx
axxx
axxx
ij
Duální úloha:
.max3322112211
2332
2222
2112
1331
1221
1111
vbvbvbuauaf
cvu
cvu
cvu
cvu
cvu
cvu
Příklad 9.4.2
Sestavíme duální úlohu k obecné dopravní úloze.
Řešení
Primární úloha: Duální úloha:
n
j
iij ax1
miRui ...,,2,1,
m
i
jij bx1
njRv j ...,,2,1,
0ijx ui + vj ≤ cij, mi ...,,2,1 , nj ,...,2,1 (9.4.1)
1 1
min.m n
ij ij
i j
z c x
f = 1 1
m n
i i j j
i j
a u b v
max. (9.4.2)
Z věty o rovnováze 8.3.7 vyplývá, že kladné hodnotě proměnné xij odpovídá v duálním
modelu rovnost ui + vj = cij, neboli v soustavě (9.4.1) je splněno tolik omezení ve tvaru
rovnic, kolik je v řešení kladných složek, neboli kolik je obsazených políček v dopravní
tabulce daného problému. Tyto rovnice slouží k určení hodnot duálních proměnných (na
rozdíl od simplexové tabulky se tyto hodnoty nepočítají automaticky, ale musíme je v každé
iteraci dopočítat). V nedegenerovaném řešení dopravního problému s m dodavateli a n
odběrateli je podle věty 9.2.1 počet obsazených polí, tj. počet rovnic pro výpočet duálních
proměnných, roven číslu (m + n - 1), zatímco počet těchto proměnných je (m + n). Můžeme
tedy jednu duální proměnnou zvolit libovolně (soustava rovnic má nekonečně mnoho řešení).
109
Primárně přípustné řešení daného dopravního problému bude optimální tehdy, budou-li
splněny všechny vlastní omezující podmínky duální úlohy, tj. budou-li ve všech políčkách
platit nerovnice (9.4.1). Označíme-li
zij = ui + vj - cij, (9.4.3)
jsou nerovnice (9.4.1) ekvivalentní s nerovnicemi
zij ≤ 0.
Věta 9.4.1 (kritérium optimálnosti)
V dopravní úloze je dosaženo optimální hodnoty účelové funkce tehdy, když všechny hodnoty
zij jsou nekladné.
Jestliže alespoň v jednom neobsazeném políčku platí zij > 0, prověřované řešení není
optimální a lze je zlepšit obsazením tohoto políčka v tzv. Dantzigově uzavřeném cyklu. Tento
cyklus představuje lomenou čáru, která vychází z neobsazeného políčka, je tvořena
vodorovnými a svislými čarami, které se lámou v obsazených políčkách, a končí ve výchozím
políčku. Lze dokázat, že v tabulce se základním nedegenerovaným řešením dopravního
problému existuje ke každému neobsazenému políčku právě jeden uzavřený cyklus. Jeho tvar
může být různý, jak ukazuje následující obrázek.
Obrázek 9.4.1 Základní tvary Dantzigova cyklu
Hodnoty zij zapisujeme do dopravní tabulky do levého horního rohu neobsazených políček.
Pokud ve více neobsazených polích je zij > 0, přednostně obsadíme políčko, ve kterém je zij
největší (čísla zij jsou obdobou indexních čísel v simplexové tabulce a jejich kladné hodnoty
tedy představují snížení hodnoty účelové funkce způsobené zařazením jedné jednotky
proměnné xij do řešení).
Věta 9.4.2
V dopravní úloze do řešení vstoupí proměnná, jejíž hodnota zij je největší kladné číslo.
Jestliže největší hodnota zij vyjde stejná pro více políček, o výběru políčka rozhodne
buď nejnižší sazba, nebo maximálně možné množství, kterým lze toto políčko obsadit. Po
vytvoření uzavřeného cyklu ke zvolenému neobsazenému poli zapíšeme do tohoto pole
znaménko „+“ a do dalších rohů cyklu střídavě znaménka „-“ a „+“, abychom věděli,
ve kterém rohu cyklu budeme přesouvané množství přičítat a kde ho budeme odečítat (po
provedeném přesunu musí zůstat okrajové podmínky zachovány). Protože po přesunu musí
řešení zůstat základní a primárně přípustné, přesouvané množství určíme jako minimum
z hodnot xij, která jsou v rozích cyklu, označených znaménkem „-“ (jedno políčko se musí
uvolnit).
Věta 9.4.3
V dopravní úloze z řešení vystupuje proměnná, která je minimem z hodnot těch proměnných
z polí dopravní tabulky, které jsou označeny symbolem „-”.
110
Po takto provedeném obsazení např. políčka (r, s) množstvím xrs hodnota účelové funkce
klesne o zrsxrs. Z toho vyplývá existence rovnocenných optimálních řešení v případě, že
v některém neobsazeném poli vyjde zij = 0.
Na zlepšené řešení musíme opět aplikovat test optima a MODI metodu opakovat tak
dlouho, dokud není dosaženo minimální hodnoty účelové funkce, tzn. dokud ve všech
neobsazených políčkách neplatí zij ≤ 0.
Příklad 9.4.3
Ze tří výrobních závodů V1, V2, V3 se rozvážejí výrobky k dalšímu zpracování do čtyř
závodů Z1, Z2, Z3, Z4. Výrobní a zpracovatelské kapacity závodů (v tunách) a vzdálenosti
mezi dodavatelskými a odběratelskými místy (v km) jsou dány. Úkolem je stanovit takový
plán rozvozu polotovarů, aby rozsah dopravy (v tkm) byl minimální. Kapacity, požadavky,
sazby jakož i výchozí základní řešení nalezneme v tabulce 9.4.1 Zjistíme, zda je toto řešení
optimální a pokud nebude, nalezneme dříve popsanou metodou optimální řešení.
Tabulka 9.4.1 Výchozí základní řešení dopravní úlohy z příkladu 9.4.1
Z1 Z2 Z3 Z4 Kapacity
V1 3
-
5
40
2
10
1
- 50
V2 4
-
7
-
5
30
3
40 70
V3 2
30
9
-
6
-
4
60 90
Požadavky 30 40 40 100 210
Řešení
Soustava rovnic, ze které pro prověřované řešení spočítáme duální proměnné u1, u2, u3, v1, v2,
v3, v4, má v tomto případě následující tvar:
4
2
3
5
2
5
43
13
42
32
31
21
vu
vu
vu
vu
vu
vu
Uvedenou soustavu 6 rovnic pro 7 neznámých lze výhodně řešit přímo v tabulce s výchozím
řešením daného dopravního problému, a to tak, že vpravo od tabulky vytvoříme sloupec
proměnných ui a pod tabulku přidáme řádek proměnných vj (viz tabulka 9.4.2).
Protože jednu z duálních proměnných můžeme volit libovolně, položíme ji rovnou nule.
S výhodou volíme nulové to ui nebo vj, které přísluší řadě s největším počtem obsazených
polí. V tabulce 9.4.2 bylo zvoleno u1 = 0 a ze sazeb v obsazených políčkách 1. řádku byly
určeny hodnoty v2 = c12 - u1 = 5 - 0 = 5 a v3 = c13 - u1 = 2 - 0 = 2. Výpočet dalších duálních
proměnných probíhal v tomto pořadí: u2 = c23 - v3 = 5 - 2 = 3, v4 = c24 - u2 = 3 - 3 = 0,
u3 = c34 - v4 = 4 - 0 = 4, v1 = c31 - u3 = 2 - 4 = -2 (potvrdilo se, že při nesymetrické dualitě
může být duální proměnná záporná). Po výpočtu všech duálních proměnných spočítáme
v každém neobsazeném poli hodnoty zij a zapíšeme je do levého horního rohu příslušného
políčka.
111
Tabulka 9.4.2 Test optimálnosti
Z1 Z2 Z3 Z4 Kapacity ui
V1 -5 3
-
5
- 40
2
10 +
-1 1
- 50 0
V2 -3 4
-
1 7
+ -
5
30 -
3
40 70 3
V3 2
30
0 9
-
0 6
-
4
60 90 4
Požadavky 30 40 40 100 210
vj -2 5 2 0
Protože v poli (2, 2) vyšlo z22 kladné, není dané řešení optimální a dá se zlepšit obsazením
tohoto políčka ve vyznačeném cyklu. Nalezneme v tabulce 9.4.2 Dantzigův cyklus. Tvoří ho
políčka (2, 2), (2, 3), (1, 3) a (1, 2). Dále podle věty 9.4.3 určíme vystupující proměnnou a tím
i přesouvané množství. Maximálně možné přesouvané množství v tomto cyklu je min(30, 40)
= 30, takže po provedeném přesunu, jehož výsledek je zapsán v tabulce 9.4.3, se hodnota
účelové funkce snížila o .301
Tabulka 9.4.3 Výpočet nového základního řešení
Z1 Z2 Z3 Z4 Kapacity ui
V1 -4 3
-
5
- 10
2
40
0 1
- + 50 0
V2 -3 4
-
7
+ 30
-1 5
-
3
40 - 70 2
V3 2
30
-1 9
-
-1 6
-
4
60 90 3
Požadavky 30 40 40 100 210
vj -1 5 2 1
Z tabulky 9.4.3 a věty 9.4.1 je zřejmé, že získané řešení je optimální. Protože je ale z14 = 0 a
my jsme dříve konstatovali, že hodnoty zij jsou vlastně obdoby indexních čísel v simplexové
tabulce, je zřejmé, že úloha bude mít alternativní optimální řešení. To nalezneme zřejmě tak,
že proměnnou x14 volíme za vstupující a vytvoříme příslušný Dantzigův okruh a podle
popsaného algoritmu nalezneme další základní optimální řešení. To je uvedeno v tabulce
9.4.4. Přesouvané množství je tentokrát 10, ale vzhledem k tomu, že z14 = 0, hodnota účelové
funkce se nezmění. Pokud provedeme stejnou volbu u1 = 0, nezmění se ani hodnoty duálních
proměnných.
Tabulka 9.4.4 Výpočet alternativního optimálního řešení
Z1 Z2 Z3 Z4 Kapacity ui
V1 -4 3
-
0 5
-
2
40
1
10 50 0
V2 -3 4
-
7
40
-1 5
-
3
30 70 2
V3 2
30
-1 9
-
-1 6
-
4
60 90 3
Požadavky 30 40 40 100 210
vj -1 5 2 1
112
Optimálním řešením dopravní úlohy z příkladu 9.4.1 je tedy
T
opt2
T
1opt
opt21optopt
)60,0,0,30,30,0,40,0,10,40,0,0(
)60,0,0,30,40,0,30,0,0,40,10,0(
1,0,)1(
x
x
xxx kkk
s minimální hodnotou účelové funkce
.760604302303407101402min z
Minimální rozsah přepravy tedy činí 760tkm.
9.5 Degenerace v dopravní úloze
V degenerovaném řešení dopravního problému s m dodavateli a n odběrateli je počet
obsazených políček podle definice 9.2.2 menší než (m + n - 1). Degenerace může být
z praktického hlediska žádoucí, neboť doprava je více koncentrovaná po menším počtu cest.
Potíže ale vznikají při některých výpočtech, konkrétně při MODI metodě, kdy
v degenerovaném řešení nelze sestrojit pro všechna neobsazená políčka uzavřené cykly a kdy
též obecně nelze vypočítat všechny duální proměnné. Pokud chceme MODI metodu
aplikovat, musíme degeneraci formálně odstranit, a to například pomocí zanedbatelně malého
množství ε, které umístíme do některého neobsazeného políčka tak, aby vzniklé řešení bylo
základní a nedegenerované (výběr tohoto pole, popř. více polí tedy není libovolný).
Degenerované řešení dopravního problému může vzniknout při sestavování výchozího
řešení, kdy po obsazení políčka maximálně možným množstvím současně vyčerpáme
kapacitu dodavatele a uspokojíme požadavek spotřebitele, tzn. proškrtneme zbývající políčka
v příslušném řádku i sloupci. Aby k tomuto jevu nedošlo, zvýšíme jednu z uvažovaných
okrajových podmínek o ε, takže můžeme proškrtnout již jen řádek nebo sloupec. Pokud máme
k dispozici výchozí základní řešení, které je degenerované, není nutné zpětně pátrat, jak
k degeneraci došlo. Stačí prostě doplnit nepatrné množství ε do takového políčka, které
netvoří s již obsazenými políčky uzavřený okruh – viz věta 9.2.1
Další možnost pro vznik degenerovaného řešení dopravního problému nastává při
přesunech v uzavřených cyklech, kdy v rozích cyklu, označených zápornými znaménky, jsou
alespoň dvě stejné nejmenší hodnoty xij. Po přesunu se tedy jedno políčko obsadí, ale více
než jedno se uvolní. V tomto případě zachováme počet obsazených políček tak, že do
nadbytečně uvolněných políček zapíšeme ε.
V některých úlohách se může stát, že MODI metoda si vyžádá přesun pomocného množství ε.
I když po tomto přesunu se hodnota účelové funkce prakticky nezmění, je nutné zachovat
postup stanovený MODI metodou a tento krok provést.
Možnost vzniku degenerovaného řešení dopravního problému i jeho formální odstranění
ilustrujeme na příkladu 9.5.1.
Příklad 9.5.1
Vyřešíme dopravní úlohu danou tabulkou 9.5.1.
113
Tabulka 9.5.1
O1 O2 O3 O4 Kapacity
D1 10 7 5 100
100
D2 4 12 6 0
80
D3 7 2 3 0
50
Požadavky 20 50 130 30 230
Řešení
Vidíme, že se vlastně jedná o problém rozvozu umělého sněhu, formulovaný v příkladu 9.2.1.
Nejprve metodou VAM nalezneme výchozí základní řešení a ověříme, zda je optimální.
Postup je zřejmý tabulky z 9.5.2. K degeneraci dochází hned při prvním obsazení políčka (3,
2), kdy je současně vyčerpána kapacita dodavatele D3 i uspokojen požadavek odběratele O2.
Aby nedošlo k proškrtnutí všech zbývajících políček v odpovídajících řadách, zvýšíme jednu
z okrajových podmínek (např. kapacitu D3) o zanedbatelné množství ε a počítáme dál.
V dalším průběhu metody VAM bylo pomocné množství ε umístěno do políčka (3, 3) a aby
řešený dopravní problém zůstal vyrovnaný, o toto nepatrné množství byl navýšen požadavek
3. odběratele.
Tabulka 9.5.2 Odstranění degenerace při určování výchozího základního řešení
O1 O2 O3 O4 Kapacity
Řádkové
rozdíly
D1 10
-
7
-
5
100
100
- 100 2 5 x
D2 4
20
12
-
6
30
0
30 80 4 4 6
D3 7
-
2
50
3
ε
0
- 50 + ε 2 3 3
Požadavky 20 50 130 + ε 30 1 360 + ε
Sloupcové
rozdíly
3 5 2 0
3 x 3 0
x
Zjistíme dále, zda je získané řešení optimální, přičemž políčko (3, 3) pokládáme za obsazené.
Test optimálnosti je proveden v tabulce 9.5.3.
Tabulka 9.5.3 Test optimálnosti
O1 O2 O3 O4 Kapacity ui
D1 -7 10
-
-9 7
-
5
100
-101 100
- 100 -1
D2 4
20
-13 12
-
6
30
0
30 80 0
D3 -6 7
-
2
50
3
ε
-3 0
- 50 + ε -3
Požadavky 20 50 130 + ε 30 1 360 + ε
vj 4 -1 6 0
114
Je tedy zřejmé, že získané řešení je jediné optimální řešení. Je tedy
T
opt )0,0,50,30,30,0,20,0,100,0,0(x
a
.8605023003062041005min z
Nejmenší rozsah přepravy (860tkm) bude dosažen, jestliže se všech 100 tun umělého sněhu
z prvního místa výroby bude vozit na běžeckou trať, z druhého místa se pak doveze 20 tun na
první sjezdovku, 30 tun na běžeckou trať a zbylých 30 tun se nechá na místě a ze třetího místa
se veškeré vyrobené množství (50 tun) odveze na druhou sjezdovku.
9.6 Ekonomický význam duálních proměnných v dopravní úloze
Duální proměnné ui, vj mají význam nejen výpočetní (při MODI metodě), ale též věcný.
Podobně jako u obecné úlohy lineárního programování i u dopravního problému představují
optimální hodnoty duálních proměnných ocenění příslušných omezujících podmínek, tj.
kapacit dodavatelů a požadavků odběratelů. Protože však při výpočtu hodnot ui a vj můžeme
jednu z nich volit libovolně, tzn. optimální hodnoty duálních proměnných nejsou určeny
jednoznačně, při jejich interpretaci musíme uvažovat vždy dva dodavatele, dva odběratele
nebo jednoho dodavatele a jednoho odběratele. Jestliže např. u dodavatele Dg rozšíříme
kapacitu o jednotku a kapacitu dodavatele Dh současně snížíme o jednotku (dopravní problém
musí zůstat vyrovnaný), účelová funkce se změní o rozdíl ug - uh. Z hlediska minimalizace
účelové funkce je tedy nejvýhodnější rozšiřovat kapacitu dodavatele, kterému připadá nejnižší
hodnota duální proměnné a naopak snižovat kapacitu dodavatele s nejvyšší hodnotou duální
proměnné. V příkladu 9.4.1, jehož optimální řešení je uvedeno v tabulce 9.4.4, je např.
výhodné rozšiřovat kapacitu závodu V1 a omezovat kapacitu závodu V3. S každou tunou
výrobků, přesunutou mezi těmito výrobními závody, se celkový počet tkm sníží o 3, protože
u1 - u3 = 0 - 3 = -3.
Stejná pravidla jako pro dodavatele platí i pro odběratele.
Z tvaru účelové funkce duální úlohy k dopravnímu problému 9.4.2 vyplývá, že při
zvýšení, popř. snížení kapacity r-tého dodavatele a požadavku s-tého odběratele o jednotku se
hodnota účelové funkce obou duálně sdružených úloh změní o hodnotu ur + vs , popř. - ur - vs.
Uvedená ekonomická interpretace duálních proměnných ui a vj platí ovšem jen potud,
pokud provedená změna okrajových podmínek nezpůsobí jiný výběr základních proměnných,
tj. obsazených políček (viz dříve zmíněné intervaly stability).
115
Cvičení
9.1 Potravinářský řetězec Kaufland má v Kraji Vysočina zastoupení ve městech Žďár nad
Sázavou, Jihlava, Havlíčkův Brod a Pelhřimov. Vzhledem k tomu, že nemá v těchto
prodejnách pekárny, využívá 3 smluvních dodavatelů, kteří pravidelně do těchto obchodů
dovážejí čerstvé pečivo. V tabulce jsou uvedeny všechny údaje týkající se počtu
požadovaných beden pečiva jednotlivých obchodů, kapacity dodavatelů a náklady v Kč
spojené s přepravou jedné bedny. Nalezněte optimální řešení.
Žďár Jihlava H. Brod Pelhřimov Kapacity
P1 5 8 6 3
560
P2 2 7 11 5
800
P3 4 6 9 9
400
Požadavky 460 580 340 380
9.2 Firma Asko se zabývá výrobou nábytku. Její zaměstnanci pracují ve 3 výrobních
pobočkách. Ani v jedné pobočce nemá firma zázemí pro přípravu jídel pro zaměstnance,
proto využívá služeb čtyř externích firem, které jídla do poboček rozvezou. V tabulce
jsou uvedeny všechny údaje týkající se počtu jídel požadovaných jednotlivými
pobočkami, kapacity dodavatelů a náklady spojené s přepravou jednoho jídla v Kč.
Úkolem je uspokojit požadavky poboček tak, aby celkové náklady byly minimální.
P1 P2 P3 Kapacity
D1 2 1 3 350
D2 4 2 5
250
D3 3 8 5
100
D4 7 9 10
300
Požadavky 500 200 300
9.3 Ze tří rybníků s plánovanými výlovy 10t , 8t a 5t kaprů mají být tyto ryby rozvezeny do
tří obcí s požadavky 6t, 7t a 8t kaprů. Vzdálenosti mezi jednotlivými rybníky a obcemi
(v km) jsou uvedeny v tabulce. Jakým způsobem mají být ryby rozvezeny, aby celkový
objem přepravy (v tkm) byl minimální a přitom aby z rybníka R2 bylo vyloveno a
odvezeno všechno plánované množství?
O1 O2 O3
R1 5 7 10
R2 4 12 5
R3 7 2 3
116
9.4 Společnost Sony a.s. má 3 střediska (S1, S2, S3), ve kterých montuje televizory. Kapacita
středisek je postupně 330, 150 a 220 kusů televizních přijímačů. Tyto přijímače pak
distribuuje 4 zákazníkům – velkoobchodům (Z1, Z2, Z3, Z4). Jejich požadavky jsou
postupně 180, 250, 160 a 110 kusů. Distribuční náklady mezi společností a zákazníky
byly stanoveny na jeden televizor ve výši uvedené v tabulce (údaje jsou ve stovkách
Kč). Nalezněte co nejlevnější způsob distribuce televizorů.
Z1 Z2 Z3 Z4
S1 11
-
4
40
17
10
9
-
S2 6
-
7
-
10
30
8
40
S3 3
30
9
-
5
-
12
60
9.5 V následující tabulce je obsaženo základní řešení dopravního problému. Nalezněte
optimální řešení tohoto problému.
O1 O2 O3 O4 O5 Kapacity
D1 6
100
9
10
11
-
3
-
11
- 110
D2 13
-
2
90
10
30
4
-
8
- 120
D3 10
-
4
-
11
70
8
60
1
- 130
D4 6
-
6
-
3
-
1
40
4
100 140
Požadavky 100 100 100 100 100
9.6 Ze čtyř mlýnů, které skladují mouku, je třeba tuto mouku rozvézt do šesti velkopekáren.
Množství skladované mouky v jednotlivých mlýnech, požadavky pekáren (obojí
v tunách) stejně jako příslušné vzdálenosti (v km) uvádí tabulka dopravní úlohy.
Úkolem je nalézt optimální způsob rozvozu mouky, aby celkový rozsah přepravy byl co
nejmenší.
P1 P2 P3 P4 P5 P6 Kapacity
M1 12
15
14
20
16 13
200
M2 11
10
14
15
20 18
320
M3 15
12
19
15
13 19
380
M4 18
16
17
14
16 12
500
Požadavky 162 175 220 264 312 267
117
9.7 V následující tabulce je obsaženo degenerované základní řešení dopravní úlohy.
Nalezněte optimální řešení této úlohy.
O1 O2 O3 O4 Kapacity
D1 38
200
20
-
22
-
18
- 200
D2 15
-
26
300
20
-
24
- 300
D3 18
-
19
-
25
220
25
- 220
D4 25
-
24
-
32
40
32
240 280
Požadavky 200 300 260 240
9.8 Nalezněte optimální řešení problému z příkladu 9.3.1.
118
Výsledky cvičení
Aritmetické vektory
1.1 a) (3 - 11 2, 2, 3, 48, 18);
b) (0, -16 2 - 4, 10, 24 2 - 6, -16 2 + 6);
1.2 a) 17;
b) není definován;
c) 0;
1.3 a) a = -1;
b) a1 = -3, a2 = 11;
1.4 a = 4
9b -
4
9c -
8
3d, b =
9
4a + c +
6
1d, c = -
9
4a + b -
6
1d, d =
3
8a + 6b - 6c;
1.5 a) nelze;
b) x = r - 2s + t;
c) x = -(36 + 4l)r - (11 + 101l)s + lt, Rl ;
d) x = 19
27r +
19
8s -
19
1t;
1.6 k = -1;
1.7 k = 6;
1.8 a) lineárně nezávislé;
b) lineárně závislé;
c) lineárně závislé;
d) lineárně závislé;
e) lineárně závislé;
f) lineárně nezávislé;
g) lineárně nezávislé;
1.9 a) k = 2;
b) k = -2;
c) k1 = -2, k2 = 4;
d) k1 = 1, k2 = 2;
1.10 a) pravdivé;
b) nepravdivé;
c) nepravdivé;
d) pravdivé;
119
1.11 jistě platí, že ,2
1 ovo
r
i
iicc kde ,...,,3,2,0,01 ricc i důkaz plyne
bezprostředně z definice 1.4.1;
Matice
2.1 a)
82595
1511914U ;
b)
2460921
66666V ;
c)
150089
166713X ;
d)
1010151323
1113530Y ;
e) ;79141511138
2779598167
24
1
Z
2.2 a) AB =
59256221
84289128;
b) AB =
212
394
213
;
c) AB =
1561710
0000
43123431
32425119
;
d) AB =
2115
19
02
;
2.3 a) BA neexistuje;
b) BA =
212
394
213
;
120
c) BA =
21252933
8327
38404244
2618102
;
d) BA neexistuje;
2.4 a) R =
22224
1490541836
4402248
850321428
;
b) S =
773264
321428
642856
;
2.5 a) 3;
b) 4;
c) 2;
d) 1;
e) 4;
f) 3;
2.6 a) lineárně nezávislé;
b) pro r = 2
1 lineárně závislé, jinak lineárně nezávislé;
c) lineárně nezávislé;
2.7 a) A-1
=
25
31
13
1;
b) A-1
=
2117
1172
7211
54
1;
c) A-1
=
2614
131941
133
20
1;
d) A-1
=
1002
0011
0110
2102
;
121
2.8 X = ;
110
101
011
2.9 X = ;
221110
511
1565
Determinanty
3.1 365;
3.2 6;
3.3 0;
3.4 vektory jsou lineárně závislé, protože ;0A
3.5 1986
1 ;
Soustavy lineárních rovnic
4.1 ;1,1,2,1T
x
4.2 ;2
3,
5
3,
20
1T
x
4.3 neexistujeřešení...14
;14
17,
14
3,
14
5...149
,,3
2
15
7,3
2
9...9
T
3
T
333
x
x Rxxxx
4.4 T1 0,0,3,1zx T
2 0,7
3,0,
7
8
zx
T
37
3,0,0,
7
5
zx
T
4 0,5
1,
5
8,0
zx
122
;7
8,
7
5,0,0
4
1,0,
4
5,0
T
6
T
5
z
z
x
x
4.5 Rxxx
2
T
22 ,0,,3
4
5
8x
T
1 0,0,5
8
zx degenerované
T
2 0,3
4,0
zx degenerované;
4.6 Rxxxxx 4
T
4444 ,,2,21,25x
;2
5,
2
1,4,0
2
1,
2
3,0,4
2,0,3,1
0,2,1,5
T
4
T
3
T
2
T
1
z
z
z
z
x
x
x
x
4.7 nemá řešení;
4.8 ;2,0,1,1,3T
x
4.9 desítka stála 20Kč, dvanáctka 22Kč, čtrnáctka 26Kč a šestnáctka 33Kč;
Soustavy lineárních nerovnic
5.1 ;0,0,,;2;32 543
T
354343 xxRxxxxxxxx
5.2 ;0,,,)237(2
1;4);23311(
2
1654
T
654654654
xxxxxxxxxxxxx
5.3 pětiúhelník ABCDE, ;5
4,0E,5,0D,
2
19,3C,0,6B,0,
3
4A
5.4 neomezená oblast s vrcholy ABC, ;0,5C,0,2B,4
15,
2
7A
5.5 pětiúhelník ABCDE, ;3,3
1E,3,1D,1,3C,
5
1,3B,
7
4,
7
8A
123
5.6 prázdná množina;
Lineární programování
6.1 x1 … počet vyráběných párů lyží A, x2 … počet vyráběných párů lyží B
max;00035003
,
200145
1206,04,0
3605,12
21
021
21
21
21
xxz
Nxx
xx
xx
xx
6.2 jx … vyráběné množství výrobku Vj v kg, j = 1, 2
min;00020003
400
300
000555
4002475,1
800
21
2
1
21
21
21
xxz
x
x
xx
xx
xx
6.3 jx … vyráběné množství výrobku Vj v t, j = 1, 2, 3, 4
max;8002000200030005
4,3,2,1,0
0002105,285
80016,52,158
000224510
4321
4321
4321
4321
xxxxz
jx
xxxx
xxxx
xxxx
j
6.4 jx … vyráběné množství hnojiva Hj v kg, j = 1, 2, 3, 4
a) 603,04,05,002,0 4321 xxxx
max;
4,3,2,1,0
000732354020
1006,0018,009,0015,0
551,02,006,004,0
4321
4321
4321
4321
xxxxz
jx
xxxx
xxxx
xxxx
j
b) 603,04,05,002,0 4321 xxxx
min;32354020
4,3,2,1,0
500
1006,0018,009,0015,0
551,02,006,004,0
4321
4321
4321
4321
xxxxz
jx
xxxx
xxxx
xxxx
j
124
6.5 jx … množství vyrobených tašek v 10 000m2, j = 1, 2, 3, 4
max;00050000300004000020
4,3,2,1,0
000480604040
400240206020
800
4321
4321
4321
4321
xxxxz
jx
xxxx
xxxx
xxxx
j
6.6 jx … množství vyrobených tašek v 10 000m2, j = 1, 2, 3, 4
max;00050000300004000020
4,3,2,1,0
000480604040
400240206020
800
4321
4321
4321
4321
xxxxz
jx
xxxx
xxxx
xxxx
j
6.7 x1 … množství sena ve směsi v kg
x2 … množství siláže ve směsi v kg
x3 … množství koncentrátu ve směsi v kg
min;502030
3,2,1,0
402
120346
00021802050
321
321
321
321
xxxz
jx
xxx
xxx
xxx
j
6.8 jx … počet tyčí rozřezaných podle varianty Vj, j = 1, 2, 3, 4, 5
5,4,3,2,1,
1207542
180234
0
5432
4321
jNx
xxxx
xxxx
j
a) min;1,02,01,02,0 5421 xxxxz
b) min;54321 xxxxxz
c) min;76554 54321 xxxxxz
Řešení úloh lineárního programování
7.1 ;Kč000690,)160,60( max
T
opt zx
7.2 ;Kč56,5559551,)44,444;56,355( min
T
opt zx
7.3 ;28,)2,6( max
T
opt zx
125
7.4 ;Kč0001891,)0,0,0,105,110,0,135( max
T
opt zx
7.5 1,0,)1( opt2opt1opt kkk xxx
;Kč000420,)0,0,400,0,200,0,200,0(
)0,0,800,200,200,0,0,0(
max
T
2opt
T
1opt
zx
x
7.6 ;Kč00050026,)0,0,250,450,0,100,0( max
T
opt zx
7.7 ;Kč00000024,)0,0,0,200,0,100,500( max
T
opt zx
7.8 ;Kč826,)0,0,0,31
200,0,
31
520( min
T
opt zx
7.9 a) ;0,)240,0,0,0,90,0,0( min
T
opt zx
b) ;60,)0,0,0,0,30,0,30( min
T
opt zx
c) ;270,)0,0,0,0,30,0,30( min
T
opt zx
7.10 ;Kč000000111,)0,0,40,0,80,560,160( max
T
opt zx
7.11 úloha nemá řešení;
Dualita
8.1 max2520 21 yyf
;2,1,0
574
652
105105
21
21
21
iy
yy
yy
yy
i
8.2 a) max17181855 54321 yyyyyf
;5...,,2,1,0
1444
11322
62
54321
543
521
iy
yyyyy
yyy
yyy
i
b) max17185 521 yyyf
;0
144
1132
62
3
321
32
31
y
yyy
yy
yy
126
8.3 dané vektory jsou optimální řešení;
8.4 ;5922,)0,0,0,18,6(,)24,0,0,24,24( maxmin
T
opt
T
opt fzyx
8.5 a) ;Kč480,)0,0,0,30,20( max
T
opt zx
b) ;Kč480,)9,0,0,8,1( min
T
opt fy
c) maxz 490Kč;
d) maxz = 440Kč;
e) maxz = 462Kč;
8.6 T
41
21
21
41
opt
T
opt2 )0,0,,0,0,,,(,)0,0,0,400,300,0,0,125( yx
825maxmin fz
tvrzení věty o rovnováze splněno není;
Dopravní úlohy
9.1 ;Kč0808,)0,0,400,0,160,0,180,460,220,340,0,0( min
T
opt zx
9.2 1,0,)1( opt2opt1opt kkk xxx
;Kč0004,)0,0,300,0,0,100,50,200,0,250,0,100(
)0,0,300,0,0,100,0,200,50,300,0,50(
min
T
2opt
T
1opt
zx
x
9.3 ;tkm94,)0,5,0,8,0,0,0,2,6( min
T
opt zx
9.4 ;Kč000366,)0,160,0,60,30,0,0,120,80,0,250,0( min
T
opt zx
9.5 ,)0,40,100,0,0,100,0,0,30,0,0,50,0,70,0,0,10,0,0,100( T
opt x ;5301min z
9.6 T
opt )267,0,233,0,0,0,0,312,31,0,37,0,0,0,0,20,138,162,0,0,0,200,0,0(x
;tkm67317min z
9.7 ,)0,0,280,0,40,0,20,160,0,260,0,40,200,0,0,0( T
opt x ;38020min z
9.8 ,)0,0,0,390,25,80,300,70,0,495,0,0( T
opt x .tkm48516min z
127
Literatura
Eichler, B., Bukovský, K.: Lineární programování. SPN, Praha 1975.
Charvát, J., Hála, M., Šibrava, Z.: Příklady k matematice I. ČVUT, Praha 1997.
Jablonský, J: Operační výzkum. VŠE, Praha 1996.
Klůfa, J.: Vybrané partie z lineární algebry. VŠE, Praha 1996.
Konečný, L.: Matematika – lineární algebra. VŠZ, Brno 1976.
Korda, B. a kol.: Matematické metody v ekonomii. SNTL, Praha 1967.
Lagová, M.: Lineární modely v příkladech. VŠE, Praha 2002.
Lagová, M., Jablonský, J.: Lineární modely. VŠE, Praha 2004.
Lagová, M., Pelikán, J.: Metody lineárního programování. VŠE, Praha 1988.
Vaněčková, E.: Ekonomicko-matematické metody. JČU, České Budějovice 1996.
RNDr. Radek Stolín, Ph.D.
MATEMATIKA PRO EKONOMY 1. vydání
Vydala Vysoká škola polytechnická Jihlava, Tolstého 16, Jihlava, 2008
Tisk Ediční oddělení VŠPJ, Tolstého 16, Jihlava
Náklad 800 výtisků
ISBN 978-80-87035-17-7
