VYSOKÁ ŠKOLA POLYTECHNICKÁ JIHLAVA Katedra matematiky
MATEMATIKA PRO EKONOMY
Radek Stolín
2008
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 1.1 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Operace s aritmetickými vektory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Lineární kombinace vektorů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Lineární závislost vektorů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7 7 7 8 9 12
2
Matice 2.1 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Operace s maticemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Hodnost matice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Inverzní matice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Maticové rovnice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14 14 15 16 18 20 22
3
Determinanty 3.1 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Výpočet determinantů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26 26 27 32
4
Soustavy lineárních rovnic 4.1 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Řešení soustav lineárních rovnic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Řešení soustav lineárních rovnic pomocí inverzní matice. . . . . . . . . . . . . . . . . . . 4.4 Řešení soustav lineárních rovnic pomocí determinantů . . . . . . . . . . . . . . . . . . . . 4.5 Gaussova metoda řešení soustav lineárních rovnic . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Jordanova metoda řešení soustav lineárních rovnic. . . . . . . . . . . . . . . . . . . . . . . . Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34 34 35 36 38 40 43 45
5
Soustavy lineárních nerovnic 5.1 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Algebraické řešení soustav lineárních rovnic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Grafické řešení soustav lineárních rovnic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48 48 48 50 55
6
Lineární programování 6.1 Úlohy výrobního plánování. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Směšovací úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Úlohy o dělení materiálu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Obecné vlastnosti řešení úloh lineárního programování. . . . . . . . . . . . . . . . . . . . . Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57 57 61 63 64 66
7
Řešení úloh lineárního programování 7.1 Grafické řešení úloh lineárního programování . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Algebraické řešení úloh lineárního programování . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Jednofázová simplexová metoda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4 Dvoufázová simplexová metoda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68 68 74 76 79 82
8
Dualita úloh lineárního programování 8.1 Symetrická dualita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Nesymetrická dualita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Vztahy mezi řešením duálně sdružených úloh . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4 Ekonomická interpretace duálních proměnných . . . . . . . . . . . . . . . . . . . . . . . . . . 8.5 Duálně simplexová metoda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83 83 85 87 94 95 98
9
Dopravní úlohy 9.1 Formulace dopravní úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2 Vlastnosti dopravní úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.3 Metody určení výchozího základního řešení dopravní úlohy. . . . . . . . . . . . . . . . . 9.4 Nalezení optimálního řešení dopravní úlohy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.5 Degenerace v dopravní úloze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.6 Ekonomický význam duálních proměnných v dopravní úloze . . . . . . . . . . . . . . . Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
100 100 101 104 107 112 114 115
Výsledky cvičení
118
Literatura
127
Ú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
[email protected]
5
6
1.
Aritmetické vektory
1.1 Základní pojmy Definice 1.1.1 Uspořádanou n-tici reálných čísel a (a1 , a2 , ..., an ) , 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 o (0, 0, ..., 0) nazýváme nulový vektor. Definice 1.1.3 Vektor a (a1 , a2 , ..., an ) nazýváme vektor opačný k vektoru a (a1 , a2 , ..., an ) . Definice 1.1.4 Říkáme, že vektory a (a1 , a2 , ..., an ) , b (b1 , b2 , ..., bn ) se rovnají, jestliže pro všechna i 1, 2, ..., n je ai bi .
1.2 Operace s aritmetickými vektory Definice 1.2.1 Součtem dvou
a (a1 , a2 , ..., an ) , a b (a1 b1 , a2 b2 , ..., an bn ). vektorů
Definice 1.2.2 Nechť k R . Reálným ka (ka1 , ka2 , ..., kan ) .
násobkem
vektoru
b (b1 , b2 , ..., bn )
nazýváme
vektor
a (a1 , a2 , ..., an )
nazýváme
vektor
Definice 1.2.3 Skalárním součinem vektorů a (a1 , a2 , ..., an ) , b (b1 , b2 , ..., bn ) nazýváme číslo (skalár) ab a1b1 a2 b2 ... an bn . Příklad 1.2.1 Jsou dány vektory a = (1, 2, 3, 4, 5), b = (-1, -1, 8, 2, 3). Určíme a) x a b, b) y 3b, c) s ab.
7
Řešení a) Podle definice 1.2.1 máme x a b (1 - 1, 2 - 1, 3 8, 4 2, 5 3) (0,1,11, 6, 8).
b) Podle definice 1.2.2 je y 3b (3 (1), 3 (1), 3 8, 3 2, 3 3) (3, 3, 24, 6, 9).
c) Podle definice 1.2.3 dostáváme s ab 1 (1) 2 (1) 3 8 4 2 5 3 44.
1.3 Lineární kombinace vektorů Definice 1.3.1 Mějme n -rozměrné aritmetické vektory u, v1 , v 2 , ..., v r , kde r N . Říkáme, že vektor u je lineární kombinací vektorů v1 , v 2 , ..., v r , jestliže existují reálná čísla c1 , c2 , ..., cr taková, že platí
u c1 v1 c2 v 2 ... cr v r . Příklad 1.3.1 Je vektor u (3, 1, 1) lineární kombinací vektorů v1 (1, 2, 3), v 2 (0, -1, -3) v 3 (2, 1, 2)?
a
Řešení Hledáme tedy taková reálná čísla c1 , c2 , c3 , aby platilo
u c1 v1 c2 v 2 c3 v 3 . 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í
3 c1
2c3
1 2c1 c 2 c3 1 3c1 3c 2 2c3 . Snadno určíme, že této soustavě vyhovují čísla c1 = 1, c2 = 2 a c3 = 1. Vektor u tedy je lineární kombinací vektorů v1 , v 2 , v 3 a získáme jej jako součet vektoru v 1 , dvojnásobku vektoru v 2 a vektoru v 3 . Tedy platí, že
u v1 2 v 2 v 3 .
8
Příklad 1.3.2 Jsou dány vektory a1 = (3, 2, 0), a 2 = (1, 5, -1) a a 3 = (2, 2, 2). Zjistíme, zda je vektor a1 lineární kombinací vektorů a 2 , a 3 . Ř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
2 5
3 3 2 , 2 4
což samozřejmě neplatí. Protože tedy neexistují reálná čísla c1, c2 vyhovující dané soustavě, není vektor a1 lineární kombinací vektorů a 2 , a 3 , tj. pomocí základních vektorových operací (viz definice 1.1.3 a 1.1.4) nelze z vektorů a 2 , a 3 získat vektor a1 .
1.4 Lineární závislost vektorů Definice 1.4.1 Mějme n-rozměrné aritmetické vektory v1 , v 2 , ..., v r , kde r N . Říkáme, že tyto vektory jsou lineárně závislé, jestliže existují reálná čísla c1 , c2 , ..., cr , z nichž alespoň jedno je různé od nuly, taková, že
c1 v1 c2 v 2 ... cr v r o. 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
9
c1 a + c2 b + c3 c = 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 a, b, c 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 v1 , v 2 , ..., v r , 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 v1 , v 2 , ..., v r , kde r N {1} , jsou lineárně závislé. Podle definice 1.4.1 tedy existují reálná čísla c1 , c2 , ..., cr , z nichž alespoň jedno (řekněme, že je to např. číslo c1) je různé od nuly, taková, že
c1 v1 c2 v 2 ... cr v r o. Odtud je
c1 v1 c2 v 2 c3 v 3 ... cr v r . Vydělením číslem c1 0 máme
v1
c c c c c2 c v 2 3 v 3 ... r v r 2 v 2 3 v 3 ... r v r , c1 c1 c1 c1 c1 c1
10
b)
což podle definice 1.3.1 znamená, že vektor v 1 je lineární kombinací vektorů v 2 , v 3 , ..., v r . Předpokládejme nyní, že alespoň jeden (řekněme, že je to vektor v 1 ) z n-rozměrných aritmetických vektorů v1 , v 2 , ..., v r , kde r N {1}, je lineární kombinací ostatních. Podle definice 1.3.1 existují reálná čísla c2 , c3 , ..., cr taková, že platí
v1 c2 v 2 c3 v 3 ... cr v r . Odtud je
v1 c2 v 2 ... cr v r (1) v1 c2 v 2 ... cr v r o. Podle definice 1.4.1 jsou vektory v1 , v 2 , ..., v r lineárně nezávislé, protože c1 1 0 . 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) v1 (1, 2, 3), v 2 (0, -1, -3) a v 3 (2, 1, 2) jsou lineárně závislé, protože jsme ukázali, že vektor u je lineární kombinací vektorů v1 , v 2 , v 3 . Naopak z toho, že vektor a1 = (3, 2, 0) není lineární kombinací vektorů a 2 = (1, 5, -1) a a 3 = (2, 2, 2), nelze podle této věty ještě nic tvrdit o lineární závislosti vektorů a1 , a 2 a a 3 . 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 -2 =
- c3 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
- 1 - 2(3c2 2c3 - 1) - c3 - 2 c2 c3 , což je po úpravě
3 6c 2 5c3 - 2 c 2 c3 . Druhou rovnici vynásobíme (-5) a obě rovnice sečteme. Dostáváme, že
11
c2 = 13. Nyní už snadno dopočítáme c3 = -15, c1 = 8. Je tedy zřejmé, že vektor d je lineární kombinací vektorů a, b, c, a proto jsou podle věty 1.4.1 vektory a, b, c, d 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 = ( 3 2, 0, -2, -3, -4). Určete jejich lineární kombinace a) 3k + 4l – 5m; b) 4 8 k – 2l – 2m.
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.2
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). 12
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 o, v 2 , v 3 , ..., v r , kde r N 1. Dokažte, že tyto vektory jsou lineárně závislé.
13
2. Matice 2.1 Základní pojmy Definice 2.1.1 Schéma mn reálných čísel aij, kde i 1, 2, ..., m; j 1, 2, ..., n a m, n N, ve tvaru
a11 a12 ......a1n a 21 a 22 ......a 2 n ..................... a a ......a mn m1 m 2 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 i 1, 2, ..., m a j 1, 2, ..., n , 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 A T (n, m) = (aji) pro všechna i 1, 2, ..., m a j 1, 2, ..., n . Definice 2.1.3 Čtvercovou matici A(n, n) = (aij) nazýváme diagonální matice, jestliže pro všechna i, j 1, 2, ..., n 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 i 1, 2, ..., m a j 1, 2, ..., n 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 i 1, 2, ..., m a j 1, 2, ..., n platí, že aij = bij. Zapisujeme A = B. 14
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 i 1, 2, ..., m a j 1, 2, ..., n platí: cij = aij + bij. Zapisujeme C = A + B. Definice 2.2.2 Reálným násobkem matice A(m, n) = (aij) číslem k R nazýváme matici C(m, n) = (cij), jestliže pro všechna i 1, 2, ..., m a j 1, 2, ..., n 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 i 1, 2, ..., m a j 1, 2, ..., p platí: n
cij =
a k 1
ik
bkj .
Zapisujeme C = AB. Příklad 2.2.1 Jsou dány matice
2 1 2 2 , B = A = 3 2 1 0 2
5 2 2 4 , C = 3 0 1 1 3
5 1 2 2 3 8 . 0 2 1
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:
2 1 2 5 2 2 2 5 1 2 2 (2) 7 3 4 2 4 = 6 2 4 = 3 3 2 0 2 + 3 0 6 . a) K = A + B = 3 2 1 0 2 3 2 1 3 1 1 0 1 2 1 1 5 5 6 1 6 2 6 5 6 12 30 1 2 6 8 = 12 18 48 . b) L = 6C = 6 2 3 8 = 6 2 6 3 0 2 1 6 0 6 2 6 (1) 0 12 6
15
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.
2 1 2 5 2 2 5 2 2 2 1 2 4 - 3 0 4 3 2 2 3 0 2 = c) Q = AB – BA = 3 2 1 0 3 1 1 3 1 0 2 1 1 2 2 5 1 3 (2) 1 2 2 1 0 (2) 1 2 (2) 1 4 (2) 3 3 2 2 0 2 1 3 (2) 2 4 2 3 = 3 5 2 3 2 1 1 5 0 3 2 1 1 2 0 0 2 1 1 (2) 0 4 2 3 5 2 2 3 (2) 1 5 1 2 2 (2) 0 5 (2) 2 2 (2) 2 3 1 0 3 4 0 3 (2) 0 2 4 2 = - 3 2 0 3 4 1 1 2 1 3 3 1 11 1 2 3 0 1 (2) 1 2 3 2
4 11 2 6 14 9 10 3 7 2 = 13 5 8 - 10 3 6 . = 23 8 7 4 6 1 1 2 4 8 3 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á.
16
Věta 2.3.3 Pro hodnost h(A) matice A(m, n) platí, že h(A) min( m, n) . 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
2 3 2 5 2 2 A 2 0 2 . 3 1 1 1 2 0 Ř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.
2 3 1 3 1 1 3 1 1 3 1 1 2 1 0 0 5 2 2 5 2 2 0 17 3 0 2 0 2 2 0 2 0 6 0 0 17 3 0 3 1 2 2 3 0 4 1 0 4 1 0 1 1 2 0 1 2 0 0 5 1 0 5 1 0
3 1 1 0 1 3 1 0 3 0 1 0 . 0 1 0 0 1 0 1
Příklad 2.3.2 Pomocí hodnosti matice rozhodneme o lineární závislosti či nezávislosti vektorů a (2, 0, 1, 1, 3), b (3, 1, 0, 2, 5), c (0, 2, 3, 2, 1). Ř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 hC 3 , budou dané tři vektory lineárně nezávislé, jestliže ale bude hC 3 , 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
17
2 C 3 0
0 1 2
1 1 0 2 3 2
3 2 5 0 1 0
0 2 2
1 3 3
1 1 2
3 2 1 0 1 0
0 2 0
1 3 0
1 1 1
3 1. 2
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
2 0 1 1 3 2 0 1 1 3 0 2 3 1 1 0 2 1 3 1. 0 0 0 1 2 0 0 1 0 2 To už je lichoběžníková matice a podle věty 2.3.1 je hC 3 . 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 1 dělit reálné číslo b reálným číslem a různým od nuly znamená násobit číslo b číslem a 1 . a 1 1 1 Číslo a se nazývá převrácená hodnota čísla a a platí, že a a a a 1 . 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í AI IA A ), 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í AX I ,
potom X nazýváme inverzní matice k matici A a značíme ji A 1 . Definice 2.4.2 Nechť A je čtvercová matice n-tého stupně. Jestliže hA n , nazýváme A regulární maticí. Je-li hA n 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 A 1 je rovněž regulární a platí
A
1 1
18
A.
Věta 2.4.3 Jestliže A je regulární matice a I jednotková matice stejného stupně jako A, potom platí AA 1 A 1 A I .
Věta 2.4.4 Jestliže A je regulární matice, potom platí
A A T 1
1 T
.
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
A | I ... I | A 1 . Příklad 2.4.1 Nalezneme inverzní matici k matici
1 2 1 A 2 0 1. 1 2 1 Řešení Podle věty 2.3.2 postupně máme
1 2 1 1 0 1 0 2 1 2 1 0
0 1 2 1 1 0 0 4 3 2 1 0 4 2 1
0 1 0
1 2 00 1 1 2 0 01 0 0 4 0 1 2 3 0 4 01 2 0 0 1 1 1 1 0 0 11 1
0 1 2 1 1 0 0 0 4 32 1 1 0 0 1 1 1
0 1 0
1 1 3 0 1 0
0 1 0
0 12 0 14 1 1
0 0 1
. 1 1
0 1 2
1 2 3 4
Je tedy
A
1
12 14 1
2 1 1 1 2 4 1 1 4
0
1 2 3 4
0 2 2 3 . 4 4
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.
19
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 12 A T X 3X 4B , jestliže je
3 5 3 1 A 1 5 2 , 12 2 3 4
0 3 6 B 1 3 0 . 2 6 9
Ř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
12 A T X 3X 4B
12 A 3I 12 A
T
12 A
T
1
T
3I X 12 A 3I 4B X 412 A 3I B.
3I X 4B / . 12 A T 3I
zleva
1
T
T
1
1
Dále určíme matici 12 A T 3I .
3 12 A 3I 5 3 T
1 5 2
2 3 0 0 0 3 0 3 0 5 4 0 0 3 3
1 2 2
2 3 . 1
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
0 5 3
0 1 3 2 10 0 1 0 0 0 1 2 1 0 0 1 0 0 4 4 0 3 5 3 0 5 2 0 1 12 0 0 12 15 21 4 0 0 4 5 0 1 2 1 0 0 0 2 0 2 3 5 0 4 0 4 6 0 0 4 4 3 5 0 0 4 4 3 5 0 0 4 4 3 1 2 2
2 1 3 0 10
0 1 0
0 3 2 1 0 0 0 1 2 1 1 5 2 3 0
20
7 10 . 5
Je tedy
12 A
T
3I
1
4 5 7 1 4 6 10 . 4 4 3 5
Pro hledanou matici X tudíž máme
4 1 X 4 4 4 4
5 6 3
70 10 1 5 2
3 3 6
6 9 0 14 9 7
45 66 27
39 66 . 21
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
x1 x T x ( x1 , x 2 , ..., x n ) 2 x n a
x T ( x1 , x2 , ..., xn ). Příklad 2.5.2 Jsou dány matice
1 2 1 1 1 1 0 3 1 1 A , b 1 . 2 1 1 0 1 1 1 1 0 Určíme matici (vektor) x, pro kterou platí x Ax b.
Řešení Nejprve opět vyjádříme x:
x Ax b x Ax b I A x b x I A 1 b . Dále určíme I A . Máme 1
21
0 1 2 1 1 0 0 0
2 1 1 1 0 1 3 1 0 1 1 2 0 0 0 1 1 0 0 0
0 0 1 0
0 1 1 3 1 0 2 1 2 0 0 0 2 1 1 1 1 1 1 0
1 3 1 0 1 0 1 8 2 0 2 1 2 1 1 1 0 0 2 2 1 0 1 0
0 0 1 0
1 0 0 0
0 1 0 0
0 0 0 1
0 1 0 5 1 0 1 1 0 0 1 8 2 0 2 1 0 0 0 15 3 1 4 2 1 0 0 14 3 0 3 2
5 1 0 1 1 0 1 1 0 8 2 0 2 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 14 3 0 3 2 1 0 0 0 0 1 1 1 0 3 3 0 3 0 0 4 4 1 6 0 0 0 1 0 1 1 0 1 0 0 0 0 0 3 14 11 2 15
0 0 0 1
0 0 1 5 4 1 5 1 0 2 8 6 1 8 0 1 0 1 1 0 1 0 0 3 14 11 2 15 0 0 0 1 1 1 0 3 0 0 4 4 1 6 . 0 3 0 3 3 0 3 0 0 3 14 11 2 15
Odtud
I A 1
1 1 4 1 4 3 3 3 14 11
1 1 0 2
0 6 . 3 15
Při výpočtu matice I A 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 1
1 1 4 1 4 1 x I A b 3 3 3 14 11
1 1 0 2
0 1 1 6 1 3 . 3 1 2 15 0 9
Cvičení 3 2 1 5 3 12 7 9 3 1 , B = a 2.1 Jsou dány matice A = 7 0 5 5 2 2 6 5 0 0 2 2 2 2 2 . Vypočítejte následující matice: C = 7 3 0 2 8
22
a) b) c) d)
U = B + C; V = (-3)C; X = A + B – C; Y = 2A - (B -3C); 1 1 3 e) Z = (-2B + C - A). 3 4 2 2.2
Určete součin AB následujících dvojic matic:
1 3 5 1 7 7 , B = ; a) A = 5 10 9 11 4 5
3 1 2 1 0 0 b) A = 4 9 3 , B = 0 1 0 ; 0 0 1 2 1 2 4 1 c) A = 0 1
3 2 0 1
1 1 4 7 , B = 2 0 6 1
2 3 0 1
1 1 2 0 2 d) A = 1 1 1 1 1 , 3 3 3 3 3
2.3
2 3 1 3 B = 5 10 . 2 5 4 3
Určete součiny BA matic ze cvičení 2.2 (pokud existují).
2 1 2.4 Mějme matice A = 4 7 1
4 2 5 8 0
6 3 6 , B = 9 1
1 3 5 1 1 1 1 . Určete: 0 2 1 2 0
a) R = 2(AB)T; b) S = AAT. 2.5
7 12 1 5 3 11 ; 3 6 2 2 9 7
Určete hodnosti následujících matic:
2 1 3 7 4 2 a) A 5 0 1 4 5 3
23
2 3 2 3 2 4 8 5 b) B ; 11 7 2 0 4 5 6 7 3 2 7 2 c) C 5 0 ; 1 10 3 6
3 2 d) D ; 2 3 0 0 3 5 7 2 3 4 0 5 1 2 ; e) E 8 6 4 5 3 2 1 0 2 1 0 5
5 1 1 2 3 5 2 1 1 1 f) F 2 5 2 10 1 . 1 4 0 1 0 1 3 1 5 0 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 r R ; 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í.
3 2 ; a) A = 5 1 5 3 1 b) B = 3 1 5 ; 1 5 3 24
0 1 2 c) C = 5 1 4 ; 1 3 9 1 1 d) D = 1 2
1 1 2 2
1 2 2 2
2 2 . 2 3
2.8 Určete matici X tak, aby platilo AXA B, jestliže
2 1 1 A 2 0 1 a 3 3 0 2.9
4 3 2 B 5 5 1. 3 3 3
Určete matici X tak, aby platilo AX B 2X C, jestliže
1 6 2 1 1 0 2 1 3 A 2 2 1, B 4 3 2 a C 2 1 3 . 1 3 1 0 2 4 1 5 6
25
3. Determinanty 3.1 Základní pojmy Připomeňme nejprve několik pojmů z kombinatoriky. Definice 3.1.1 Mějme množinu M 1, 2, ..., n, kde n N . Každá uspořádaná n-tice
k1 , k 2 , ..., k n 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:
1, 2, 3, 4, 1, 2, 4, 3, 1, 3, 2, 4, 1, 3, 4, 2, 1, 4, 2, 3, 1, 4, 3, 2, 2, 1, 3, 4, 2, 1, 4, 3, 2, 3, 1, 4, 2, 3, 4, 1, 2, 4, 1, 3, 2, 4, 3, 1, 3, 2, 1, 4, 3, 2, 4, 1, 3, 1, 2, 4, 3, 1, 4, 2, 3, 4, 2, 1, 3, 4, 1, 2, 4, 2, 3, 1, 4, 2, 1, 3, 4, 3, 2, 1, 4, 3, 1, 2, 4, 1, 2, 3, 4, 1, 3, 2. Definice 3.1.2 Dvojice k i , k j
se nazývá inverze v permutaci
k1 , k 2 , ..., k n ,
jestliže je současně
i j a ki k j .
Příklad 3.1.2 V permutaci 3, 4, 1, 2 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 p
K
K k1 , k2 , ..., kn
a1k1 a 2 k2 ...a nkn ,
kde p K 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 a1k1 a2 k2 ...ankn , které jsou kladné v případě, že permutace k1 , k 2 , ..., k n má sudý počet inverzí a záporné v případě, že permutace k1 , k 2 , ..., k n má lichý počet inverzí.
26
3) Každý člen a1k1 a2 k2 ...ankn 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ř.
det A A aij .
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
det A
a11 a 21
a12 (1) 0 a11a 22 (1)1 a12 a 21 a11a 22 a12 a 21 . a 22
Příklad 3.2.2 Pomocí řešení předešlého příkladu platí, že
3 1
5 3 2 5 1 11. 2
Příklad 3.2.3 Určíme obecně podle definice 3.1.3 determinant matice třetího stupně. Řešení Máme
a11 det A a21 a31
a12 a22 a32
a13 a23 (1)0 a11a22a33 (1)1 a11a23a32 (1)1 a12a21a33 a33
(1) 2 a12a23a31 (1) 2 a13a21a32 (1)3 a13a22a31 a11a22a33 a12a23a31 a13a21a32 (a13a22a31 a11a23a32 a12a21a33 ). 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. +
+
+
a11 a 21 a31
-
a12 a 22 a32
a13 a11 a 23 a 21 a33 a31
27
-
a12 a 22 = a32
-
a11a22 a33 a12 a23 a31 a13 a21a32 (a13 a22 a31 a11a23 a32 a12 a21a33 ). Věta 3.2.1 (Sarrusovo pravidlo) Nechť A = (aij) je čtvercová matice třetího stupně. Potom platí
a11 det A a 21 a31
a12 a 22 a32
a13 a 23 a11a 22 a33 a12 a 23a31 a13a 21a32 (a13a 22 a31 a11a 23a32 a12 a 21a33 ). a33
Příklad 3.2.4 Pomocí řešení předchozího příkladu je
1 2 3 1 2 0 4 1 0 4 3 2 1 3 2 1 4 1 2 (1) 3 (3) 0 (2) (3) 4 3 1 (1) (2) 2 0 1 4 6 36 2 32. 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 kde Mij je subdeterminant prvku aij. Příklad 3.2.5 Je dán determinant matice A
2 1 3 1
0 0 2 0
Určíme doplněk prvku a32. Řešení Nejprve podle definice 3.2.1 určíme M32. Máme
28
1 4 0 3
5 0 . 2 4
1i j M ij ,
M 32
2 1 1
1 4 3
5 0. 4
Dále podle definice 3.2.2 je doplněk prvku a32
1
3 2
2 1 1
1 4 3
5 0 (1) (32 0 15 20 0 4) 23. 4
Věta 3.2.2 (o rozvoji determinantu podle i-tého řádku) Nechť A je čtvercová matice n-tého stupně. Potom pro i 1, 2, ..., n platí n
det A 1 air M ir . ir
r 1
Věta 3.2.3 (o rozvoji determinantu podle j-tého sloupce) Nechť A je čtvercová matice n-tého stupně. Potom pro j 1, 2, ..., n platí n
det A 1r j a rj M rj . r 1
Příklad 3.2.6 Určíme hodnotu determinantu
2 1 3 1
0 0 2 0
1 4 0 3
5 0 . 2 4
Řešení Použijeme větu 3.2.3 s j = 2 a výsledek příkladu 3.2.5. Máme 2 1 3 1
0 0 2 0
1 4 0 3
5 1 4 0 2 1 5 2 1 5 0 1 2 2 2 3 2 (1) 0 3 0 2 (1) 0 3 0 2 (1) 2 1 4 0 2 1 3 4 1 3 4 1 3 4 4 (1)
4 2
2 1 5 2 1 5 0 1 4 0 (1) 2 1 4 0 2 (23) 46. 3 0 2
1 3 4
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
29
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í:
det A det A T . 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
1 3 2 2 1 1 2 5 A . 3 1 2 1 2 1 3 0 Ř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
1 3 2 2 5 5 6 0 5 5 6 5 5 6 5 1 1 2 1 3 3 0 3 4 det A 1 1 1 3 3 1 3 3 . 3 1 2 1 3 1 2 1 2 1 3 2 1 3 2 1 3 0 2 1 3 0 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
30
5 5 6 15 5 9 15 9 15 9 3 2 det A 1 3 3 7 3 6 1 1 . 7 6 7 6 2 1 3 0 1 0 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
det A
15 9 15 3 3 3 30 21 27. 7 6 7 2
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
det A a11a 22 ...a nn . Příklad 3.2.8 Určíme hodnotu determinantu matice
1 3 2 2 1 1 2 5 A . 3 1 2 1 2 1 3 0 Řešení Podle věty 3.2.5 postupně máme
1 3 2 2 1 3 2 2 1 3 2 2 5 1 1 2 0 14 11 8 0 5 1 4 det A 3 1 2 1 0 10 8 5 0 10 8 5 2 1 3 0 0 5 1 4 0 14 11 8 1 1 0 5 0 0
3 2 2 1 5 1 4 0 1 3 0 6 3 0 5 0 41 16 0
3 2 2 1 5 1 4 1 1 0 3 0 2 1 5 2 0 0 41 16 0
3 2 2 5 1 4 . 0 2 1 0 0 9
Použijeme-li nyní větu 3.2.6, dostáváme
1 1 det A 3 1 5 2 9 27. 5 2 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.
31
Příklad 3.2.9 Prostřednictvím výpočtu determinantu matice
3 1 2 A 2 1 0 5 1 6 rozhodneme, zda je matice A regulární nebo singulární. Řešení Determinant matice A je
3 1 2 2 1 0 18 0 4 10 0 12 0. 5 1 6 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 det AB det A det B .
Věta 3.2.9 Je-li A regulární matice, potom determinant matice inverzní k matici A je
det A 1
1 . det A
Důkaz Podle věty 3.2.8, definice inverzní a jednotkové matice a věty 3.2.6 postupně máme det A det A 1 det AA 1 det I 1,
odkud již plyne tvrzení věty.
Cvičení 3.1
Vypočítejte determinant
1 6 8 2 9 7. 3 1 0
32
3.2
Vypočítejte determinant
4 4 2 4 3.3
2 3 0 3
5 3 7 7 . 2 1 7 8
Vypočítejte determinant
1 4 2 5 9
2 7 5 9 1
3 4 5 6 7 8 9 10 11. 1 1 1 2 3 4
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 A 1 , jestliže
6 3 2 1 8 5 A 5 3 6 8 7 6
33
7 2 . 4 5
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) x1 , x2 ... , xn R, rozumíme soustavu
m, n N
a11 x1 a12 x 2 ... a1n x n b1 a 21 x1 a 22 x 2 ... a 2 n x n b2 ................................................. a m1 x1 a m 2 x 2 ... a mn x n bm .
(4.1.1)
Reálná čísla aij, kde i 1, 2, ..., m a j 1, 2, ..., n , se nazývají koeficienty a reálná čísla bi , kde i 1, 2, ..., m, se nazývají pravé strany. Definice 4.1.2 Matici
a11 a12 a22 a A 21 ... ... a m1 am 2
... a1n ... a2 n ... ... ... amn
nazýváme matice soustavy (4.1.1). Matici
a11 a12 a22 a A r 21 ... ... a m1 am 2
... a1n ... a2 n ... ... ... amn
b1 b2 ... bm
nazýváme rozšířená matice soustavy (4.1.1). Definice 4.1.3 Vektor x ( x1 , x2 , ..., xn ) T nazýváme vektor neznámých (proměnných) soustavy (4.1.1) a vektor b (b1 , b2 , ..., bm ) T 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 Ax b.
34
(4.1.2)
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 x x1 , x2 ... , xn T , 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 hA h rovna hodnosti rozšířené matice soustavy hA r hr . 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:
x1 2 x2 4 x3 7 x2 x3 1. Řešení Dané soustavě přiřadíme rozšířenou matici soustavy
1 2 4 7 . A r 0 1 1 1 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
x 2 1 x3 . Po dosazení do první rovnice dostaneme po úpravě, že
x1 5 2 x3 . Všechna řešení soustavy tedy můžeme zapsat ve tvaru
35
x 5 2 x3 , 1 x3 , x3 T , kde x3 R nebo ve tvaru
x 5, 1, 0T x3 2, 1, 1T , kde x3 R. 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í: h hr n ).
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í
x A 1b .
(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
x1 x 2 2 x3 1 2 x1 x 2 7 x3 2 3x1 3x 2 4 x3 1. Řešení Neznámé x1 , x2 , x3 určíme podle (4.3.1). Nejprve Gaussovým algoritmem popsaným v části 2.4 určíme inverzní matici k matici soustavy
2 1 1 A 2 1 7 . 3 3 4 Máme
36
2 1 0 0 1 1 2 1 0 0 1 1 2 1 0 0 1 1 7 0 1 0 ~ 0 1 3 2 1 0 ~ 0 1 3 2 1 0 ~ 2 1 3 3 3 4 0 0 1 0 0 2 3 0 1 0 0 1 0 12 2 1 1 0 2 0 1 1 0 0 172 1 52 ~ 0 1 0 132 1 32 ~ 0 1 0 132 1 32 . 0 0 1 0 0 1 3 3 1 1 0 0 2 2 2 2 Je tedy zřejmé, že
17 2 5 1 A 1 13 2 3 . 2 1 3 0 Dosazením do (4.3.1) získáme hledané řešení dané soustavy rovnic:
17 2 5 1 4 1 x 13 2 3 . 2 3 . 2 1 1 1 3 0 Zkouškou se snadno můžeme přesvědčit, že x1 4, x2 3, x3 1 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
x1 2 x 2 3x3 0 2 x1 x 2 7 x3 2 3x1 3x 2 4 x3 2. Řešení Budeme postupovat stejně jako v řešení minulého příkladu. Hledáme tedy nejprve inverzní matici k matici
3 1 2 A 2 1 7 . 3 3 4 Postupně dostáváme
3 1 0 0 1 2 3 1 0 0 1 2 3 1 0 0 1 2 7 0 1 0 ~ 0 3 13 2 1 0 ~ 0 3 13 2 1 0 . 2 1 3 3 4 0 0 1 0 3 13 3 0 1 0 0 0 1 1 1 Matice dané soustavy je tedy singulární a podle věty 4.2.2 nemá soustava právě jedno řešení.
37
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
xj
det A j det A
, pro j 1, 2, ..., n,
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
x1 4 x 2 x3 3 3x1 x 2 x3 1 2 x1 x 2 2 x3 6. Řešení Determinant matice soustavy je
1 4 1 3 1 1 2 8 3 2 1 24 28. 2 1 2 Protože je det A 0 , je matice soustavy regulární, soustava má právě jedno řešení a můžeme použít Cramerovo pravidlo. Postupně vypočítáme
3 4 1 det A 1 1 1 1 6 24 1 6 3 8 28, 6 1 2 1 3 1 det A 2 3 1 1 2 6 18 2 6 18 0, 2 6 2 1 4 3 det A 3 3 1 1 6 8 9 6 1 72 56. 2 1 6 Podle věty 4.4.1 je tedy řešením dané soustavy vektor T
56 28 0 T x , , (1, 0, 2) . 28 28 28
38
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
x1 1x 2 x3 2
2 x1 2x 2 x3 3 x 2 4 x3
x1 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ě
1 1 1 det A 2 2 1 4 2 1 2 2 1 8 1 4 2. 1 1 4 1 . V tom případě je totiž det A 0 , 2 matice soustavy je regulární a lze použít Cramerovo pravidlo. Dále máme Soustava má tedy právě jedno řešení právě když
2 1 1 det A1 3 2 1 8 2 1 3 2 2 12 1 3 5, 1 4 1 2 1 det A 2 2 3 1 12 2 2 3 16 3, 1 4
1 1 2 det A 3 2 2 3 2 3 1 4 2 2 3 2 1 2 2. 1 1 Je tedy pro
1 2 3 5 3 2 2 x , , 4 2 4 2 4 2
T
.
1 , dostaneme soustavu rovnic, která podle věty 4.2.2 nemá právě jedno 2 řešení. Postupy při řešení takovýchto soustav se budeme zabývat v dalších odstavcích. V případě, že
39
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
x1 3x 2 x3 3 2 x1 x 2 4 x3 5 . 2 x2
2
Ř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.
1 3 1 3 1 3 1 3 A r 2 1 4 5 0 7 6 1. 0 2 0 2 0 2 0 2 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
2 x2 2 , tedy x2 = 1. To dosadíme do druhé rovnice a dostaneme, že x3 = 1. Dosazením do první T rovnice vyjde rovněž x1 = 1. Řešením dané soustavy je tudíž vektor x 1, 1, 1 .
40
Příklad 4.5.2 Gaussovou eliminační metodou vyřešíme soustavu lineárních rovnic
2 x1 x 2 3x3 x 4 2 x1
2 x3 3x 4 1 .
x1 2 x 2
7 x4 5
Řešení Podobně jako v řešení předešlého příkladu máme
1 2 1 2 0 7 5 2 1 3 Ar 1 0 2 3 1 1 0 2 3 1 1 2 0 7 5 2 1 3 1 2 2 0 7 5 1 2 0 7 5 1 0 2 2 10 6 0 2 2 10 6 . 0 3 3 15 8 0 0 0 0 2 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
x1 x 2 2 x3 3x 4 2 4 x1 3x 2 x3 5 x 4 5 x1
5 x3 4 x 4 1
2 x1 x 2 3x3 x 4 1 Ř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
1 4 Ar 1 2
1 2 3 2 1 1 2 3 2 3 1 5 5 0 1 7 7 3 1 1 2 3 2 . 0 5 4 1 0 1 7 7 3 0 1 7 7 3 1 3 1 1 0 1 7 7 3
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
x1 x 2 2 x3 3x 4 2 x 2 7 x3 7 x 4 3
,
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 41
x 2 3 7 x3 7 x 4 a po dosazení do první rovnice, vyjádření x1 a upravení získáme
x1 1 5x3 4 x4 . Všechna řešení dané soustavy tedy můžeme zapsat pomocí lineární kombinace vektorů. x (1 5 x3 4 x 4 , 3 7 x3 7 x 4 , x3 , x 4 ) T (1, 3, 0, 0) T x3 (5, 7, 1, 0) T x 4 (4, 7, 0, 1) T , kde x3 , x 4 R.
(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 x1 , x 2 , dosaďme postupně x3 = 1, x4 = 1 a x3 = 0, x4 = 1. Dosazením do (4.5.1) máme x1 (2, 3, 1, 1) T , x 2 (3, 4, 0, 1) T .
Základní řešení, označme je řekněme x z1 , dostaneme podle definice 4.5.4 tak, že dosadíme v (4.5.1) x3 x4 0 . Máme
42
x z1 (1, 3, 0, 0) T .
Toto řešení není degenerované, protože obě základní proměnné x1 , x 2 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ř. x1 , x 2 ), dostaneme obecné řešení dané soustavy vyjádřené jinou lineární kombinací vektorů (přirozeně za předpokladu, že bude možné zapsat x3 , x 4 pomocí x1 , x2 ). 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 4 4! 4 3 2 1 6. Je také zřejmé, že každému vyjádřen kombinačním číslem 2 (4 2)!2! 2 1 2 1 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ýš
n n! n h n h !h! 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
x1 3x 2 x3 x 4 2 x1 2 x 2 3x3 x 4 3 4 x1 x 2 2 x3 3x 4 7
.
x1 3x 2 x3 x 4 0 Ř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
43
1 1 2 1 1 3 2 3 1 3 0 1 Ar ~ 4 1 2 3 7 0 1 3 1 1 0 0 1 1 2 1 1 3 4 0 5 0 0 1 ~ ~ 0 0 46 1 50 0 0 0 0 2 0 2
3 1 1 2 1 4 0 5 ~ 13 6 1 15 0 2 0 2 3 1 1 2 1 3 1 1 1 4 0 5 0 1 4 0 ~ 0 1 0 1 0 0 1 0 0 46 1 50 0 0 0 1
2 5 . 1 4
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
1 1 3 1 0 0 1 4 0 0 1 0 0 0 0 1 0 1 3 0 0 0 1 0 ~ 0 0 1 0 0 0 0 1
2 1 3 1 0 5 0 1 4 0 ~ 1 0 0 1 0 4 0 0 0 1
5 1 0 0 0 1 0 1 0 0 ~ 1 0 0 1 0 4 0 0 0 1
2 1 1 0 ~ 1 0 4 0
6 5 ~ 1 4 0 1 0 0
0 0 1 0
0 2 0 1 . 0 1 1 4
Poslední matice odpovídá soustavě v kanonickém tvaru (viz definice 4.6.1)
2
x1
1
x2 x3
1
.
x4 4 Po této tzv. úplné eliminaci dostáváme přímo řešení x (2, 1, 1, 4) T .
Příklad 4.6.2 Jordanovou metodou nalezneme obecné a všechna základní řešení soustavy
x1 2 x 2 4 x3 7 x 2 x3 1
.
Řešení Dané soustavě přiřadíme rozšířenou matici soustavy a vynulujeme prvky pod i nad hlavní diagonálou
1 2 4 7 1 0 2 5 . A r 0 1 1 1 0 1 1 1
44
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
x 5 2 x3 , 1 x3 , x3 T (5, 1, 0) T x3 (2, 1, 1) T , kde x3 R a základní
x z1 (5, 1, 0) T . 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.
5 1 2 0 3 1 0 2 5 1 0 2 . 1 1 0 1 1 1 0 1 1 1 0 1 Další základní řešení je tedy x z 2 (3, 0, 1) T .
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. 3 12 1 0 32 12 1 2 0 1 0 1 1 1 0 1 1 1 2
1 0 32 . 0 1 52
Poslední základní řešení má tedy tvar T
x z3
3 5 0, , . 2 2
Ani jedno ze základních řešení není podle definice 4.5.5 degenerované.
3 Podle věty 4.5.2 je v tomto případě maximální počet základních řešení roven 3, což 2 výsledek potvrzuje.
Cvičení 4.1
Řešte soustavu
x1 2 x 2 3x3 x 4 5 2 x1 3x 2 x3 2 x 4 7 x1 x 2 x3 x 4 3 3x1 2 x 2 5 x3 x 4 1.
45
4.2
Řešte soustavu
1 1 1 x 2 x3 2 3 4 1 1 1 1 x1 x 2 x3 2 3 4 5 1 1 1 1 x1 x 2 x3 . 3 4 5 6 x1
4.3
Řešte soustavu s parametrem
3x1 6 x 2 x3
1
3x1 9 x 2 x3 3 12 x1 x 2 6 x3
3.
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
5 x1 6 x 2 2 x3 8 10 x1 12 x 2 3x3 16 15 x1 18 x 2 4 x3 24. 4.6
Nalezněte obecné a všechna základní řešení soustavy
x1 3x 2 x3 3 x 4 4 x1 x 2 3x3 3x 4 2 2 x1 4 x 2 x3 5 x 4 4 2 x1 x 2 8 x3 6 x 4 7. 4.7
Řešte soustavu
x1 2 x 2 3x3 x 4 2 x5 1 3 x1
x3 x 4 4 x5 0 x 2 2 x3 3 x 4 x5 2
4 x1 3x 2 2 x3 3x 4 3x5 7 x1 2 x 2 5 x3 4 x 4 x5 3.
46
4.8
Řešte soustavu
x1 4 x 2 x3 2 x 4 3 x5 4 2 x1 2 x 2
x 4 2 x5 8
x1 5 x 2
7 x5 12
3 x1 x 2 x3 2 x 4 x5 9 2 x1 5 x 2 2 x3 x 4 2 x5 3. 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?
47
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) x1 , x2 ... , xn R; m, n N rozumíme soustavu
a11 x1 a12 x 2 ... a1n x n b1 a 21 x1 a 22 x 2 ... a 2 n x n b2 ................................................. a m1 x1 a m 2 x 2 ... a mn x n bm .
(5.1.1)
Reálná čísla aij, kde i 1, 2, ..., m a j 1, 2, ..., n, se nazývají koeficienty a reálná čísla bi , i 1, 2, ..., m, se nazývají pravé strany. Pozn. 1) Maticově lze soustavu nerovnic z předchozí definice zapsat jako Ax b ,
(5.1.2)
kde
a11 a12 a22 a A 21 ... ... a m1 am 2
... a1n ... a2 n ... ... ... amn
a
b (b1 , b2 , ..., bm ) T . 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)
ai1x1 + ai2x2 + ... + ainxn+ xn+i = bi ,
(5.1.4)
lze ji nahradit rovnicí kde xn+i 0.
48
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) x1 , x2 , ... , xn R, xn1 , xn 2 , ... , xn m R0 , m, n N
a11 x1 a12 x 2 ... a1n x n x n 1 a 21 x1 a 22 x 2 ... a 2 n x n
b1 xn2
b2
.................................................................................. a m1 x1 a m 2 x 2 ... a mn x n x n m bm
(5.2.1)
nazýváme přidružená soustava rovnic k soustavě (5.1.1). Proměnné xn1 , xn 2 ... , xn m 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
x1 x 2 2 x3 2 x1 x 2 2 x3 3x1 2 x 2 x3
1 4 2.
Řešení Nejprve sestavíme přidruženou soustavu rovnic
x1 x 2 2 x3 x 4 2 x1 x 2 2 x3 x5 3x1 2 x 2 x3 x6
1 4, 2
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).
1 1 0 4 1 1 0 3 1 1 2 1 0 0 1 1 1 2 1 0 0 2 0 1 0 4 0 1 6 2 1 0 2 0 1 6 2 1 0 2 2 1 3 2 1 0 0 1 2 0 1 7 3 0 1 1 0 0 1 1 1 1 3
49
5 4 15 1 0 0 3 5 4 15 1 0 0 3 0 1 0 4 7 6 20 0 1 0 4 7 6 20 . 0 0 1 1 1 1 3 0 0 1 1 1 1 3 Vektor obecného řešení přidružené soustavy rovnic tedy je
x R 15 3x4 5 x5 4 x6 ; 20 4 x4 7 x5 6 x6 ; 3 x4 x5 x6 ; x4 ; x5 ; x6 , T
x 4 , x5 , x 6 0 a vektor obecného řešení soustavy nerovnic je:
x N 15 3x4 5x5 4 x6 ; 20 4 x4 7 x5 6 x6 ; 3 x4 x5 x6 , x4 , x5 , x6 0. T
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
n n! 6! 65 4 20. 3 2 n h n h !h! 6 3! 3! 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 1 1 2 1 0 0 1 1 1 2 1 0 2 0 1 0 4 2 1 2 0 1 2 1 3 2 1 0 0 1 2 3 2 1 0 0 1 2 1 0 0 1 1 0 0 3 1 0 1 6 2 1 0 2 0 1 0 4 0 1 7 3 0 1 1 0 0 1 1
50
0 1 0 4 1 2 5 4 15 7 6 20 . 1 1 3
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
x z1 (0, 0, 0, 1, 4, 2) T , x z 2 (1, 0, 0, 0, 2, 1) T , x z 3 (15, 20, 3, 0, 0, 0) T . 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
x1 x1 3 x1 2 x1 2 x1
x2 1 3x2 6 5 x 2 15 x2 0 x 2 7.
Řešení Převedeme nerovnice, pokud to bude možné, na tzv. úsekový tvar:
x1 1 x1 6 x1 5 2 x1 x1 7 2
x2 1 x2 2 x2 3 x2 x2 7
1
1
1
0
1.
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.
51
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:
2 x1 x 2 0 x1 3x 2 6. Jednoduchým výpočtem zjistíme, že x1
6 12 5 6 , x2 , tj. A , 1 . 7 7 7 7
Podobně určíme souřadnice zbývajících vrcholů. Postupně dostaneme: 5 6 2 1 6 1 1 B3 , , C2 , 1 , D1 , 2 a E - , 7 7 7 4 7 4 3
2 . 3
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 x1 a x 2 mezi základními proměnnými. Řešení Příslušná přidružená soustava rovnic je zřejmě
x1
x 2 x3
x1 3x 2
1 x4
3x1 5 x 2
6 x5
2 x1 x 2
15 x6
2 x1 x 2
0 x7 7,
52
kde x3 , x4 , x5 , x6 R0 , x7 R . 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 7 2 5 5 4 4.5.2, je takových řešení nanejvýš 10. Vyzbrojeni Jordanovou 2 2 2 metodou úplné eliminace a značnou dávkou trpělivosti postupně máme
1 1 0 1 1 3 0 1 3 5 0 0 2 1 0 0 2 1 0 0
0 0 1 0 0
0 0 0 1 0
0 0 1 1 1 1 12 12 0 0 0 8 3 0 1 0 0 0 3 2 0 3 2 0 0
0 1 1 1 0 6 0 2 0 15 0 8 0 0 0 3 1 7 0 3 0 0 1 1 0 0 72 0 0 0 18 0 1 0 2 0 0 1 9 0
1 0 0 0 0
0 32 1 12 7 0 4 7 0 2 7 0 2
12 0 0 0 92 1 12 0 0 0 72 0 23 0 1 14 0 0 2 32 0 1 0 252 0 3 39 0 0 1 2 2 0
1 0 0 0 0
0 85 3 1 8 7 0 4 0 73 7 0 8
1 0 8 1 0 8 1 1 4 0 1 0 83
1 0 0 0 0
0 13 2 1 3 7 0 3 0 73 0 0
0 0 1 0 0
1 0 0 0 0
0 1 0 0 0
0 0 0 1 0
1 0 0 7 2 0 7 0 3 1 0 7 0 1 1 0 0 0
0 0 0 0 0 0 8 0 3 0 1
5 4 9 4 23 2 38 3 9 4
1 0 0 0 0
1 0 2 1 3 1 0 3 0 3 2 0 13 0 3 0 83 6 0 1 1 7 0 3 27 0 1 7 7 5 1 0 7 0 7 39 2 0 0 7 7 0 2 7 0 1 1 7 0
53
1 1 3 2 2
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 32 12 1 12 12 0 7 4 0 72 32 7 3 0 2 2 0 85 3 1 8 7 0 4 7 0 8 7 0 8
0 13 2 1 3 7 0 3 0 73 0 0
1 0 8 1 0 8 1 1 4 3 0 8 0 83
0 0 1 0 0
0 13 0 13 0 23 8 1 3 0 1
0 13 0 0 2 1 0 0 3 0 1 73 0 0 73 0 1 0 0 0 0 0 1 0 0 0
0 0 1 0 0
0 0 1 0 0
0 0 0 0 1
0 1 0 7 0 18 0 2 1 9 0 0 92 0 0 72 0 0 46 1 0 252 39 0 1 2 0 0 0 1 0
0 0 0 0 1
5 4 9 4 23 2 19 4 9 4
0 13 2 0 3 0 253 0 383 1 7 1 2 3 1 3 3 39 2 7 7 8 3 6 1 7
5 0 17 0 7 2 0 0 73 7 8 0 73 0 7 1 1 0 2 0 0 1 1
7 7
20 7 9 7 18 7
0 17 75 3 2 0 7 7 0 73 87 1 1 2 0 0 1
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
1 0 0 0 0
0 1 0 0 0
1 0 7 0 72 3 1 7 1 0 2 0 0
0 0 0 1 2
0
0 157 1 0 30 0 0 1 7 38 0 7 0 0 0 21 0 0 1 7 0 0 6 73 0 1 0 7 1 12 7 0 7 0 1 25 0 0 72 0 7 21 0 0 1 0 2 0 0 1 1 7
1 0 0 73 7 0 72 0 17 3 1 0 72 7 0 1 1 2 0 0 0 1 5 3 0 14 14 1 0 143 14 4 1 1 7 7 1 1 0 2 2 0 12 12
0 0 0 1 0
6 0 7 0 127 25 0 7 0 21 1 7 75 0 14 0 143 46 . 0 7 21 0 2 1 72
Dostáváme tedy: T
7 25 39 9 x z1 , , 0, 0, 46, , , 2 2 2 2 T
x z2
23 19 9 5 9 , , 0, , 0, , , 2 4 4 4 4 T
25 38 1 2 x z 3 , , 0, , , 0, 7 , 3 3 3 3 x z 4 2, 3, 0, 13, 6, 7, 0 , T
T
x z5
5 39 27 , , , 0, 7, 7, 0 , 7 7 7 T
20 9 18 x z 6 , , , 7, 0, 7, 0 , 7 7 7 T
x z7
38 15 30 , , , 21, 0, 0, 7 , 7 7 7 T
6 12 25 x z8 , , , 0, 21, 0, 7 , 7 7 7 T
x z9
3 46 21 7 75 , , , 0, 0, , . 14 7 2 2 14
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 x z 2 (bod D), x z 3 (bod E) a x z8 (bod A).
54
Cvičení 5.1 Řešte soustavu
x1
3x3 2
x1 x 2 4 x3 0. 5.2 Řešte soustavu
x1 2 x 2 x3 1 x1
x3 2
2 x1 3x 2
1.
5.3 Řešte graficky soustavu
3 x1 2 x 2 10 9 x1 4 x 2 56 3 x1 5 x 2 4 0
x1
x 2 0. 5.4 Řešte graficky soustavu
3 x1 2 x 2 3 3 x1 2 x 2 15 5 x1 2 x 2 10 x1 2 x 2
6
0
x1
x 2 0. 5.5 Řešte graficky soustavu
x1 x 2 4 6 x1 2 x 2 8 x1 5 x 2 4 3
x1
x2 3 0
x1
x 2 0.
55
5.6 Řešte graficky soustavu
x1 x 2 4 5 x1 6 x 2 30 2 x1 7 x 2 28 0
x1
x 2 0.
56
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 j 1, 2, ..., n … vyráběné množství j-tého výrobku (tzv. strukturní neznámé); bi i 1, 2, ..., m … množství i-tého zdroje, které je k dispozici (tzv. požadavková čísla); aij i 1, 2 ,..., m; j 1, 2, ..., n … množství i-tého zdroje potřebné k výrobě jednotkového množství j-tého výrobku (tzv. strukturní koeficienty);
57
cj j 1, 2, ..., n …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
a11 x1 a12 x 2 ... a1n x n b1 a 21 x1 a 22 x 2 ... a 2 n x n b2 ................................................. a m1 x1 a m 2 x 2 ... a mn x n bm ,
(6.1.1)
x j 0, j 1, 2, ..., n
(6.1.2)
z c1 x1 c2 x2 ... cn xn
(6.1.3)
a současně maximalizují funkci
Maticově lze totéž zapsat v jednodušším tvaru:
Ax b, x o, z c T x max, 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 (S 1, 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
58
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 S1 (hod) S2 (hod) S3 (hod) S4 (hod) Cena (Kč/kg)
A (kg) 2 4 3 1 600
Disponibilní množství (hod) 45 100 300 50 MAX
B (kg) 0,25 2 1 4 400
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
600 x1 400 x2 . 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
1 x 2 45. 4
2 x1
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)
z 600 x1 400 x2 byla při splnění podmínek
1 x 2 45 4 4 x1 2 x 2 100
2 x1 3 x1
x 2 300
x1 4 x 2 50 x1
0
x2
0
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
59
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 Desky (bm) Ruční práce (hod) Tržba (Kč/ks)
S1 (ks)
S2 (ks)
Z (ks)
4 6 8 000
3 4 7 500
1 2 1 800
Kromě uvedených výrobků může firma prodávat komplety obsahující jeden stůl typu S 1 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:
4 x1 3x 2 x3 800 6 x1 4 x2 2 x3 1 240 (b) vztahem mezi počtem stolů typu S1 a počtem židlí a mezi počtem kompletů:
x1 x 4 x3 4x 4 (c) požadavkem na minimální počet kompletů
x4 20 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 60
4 x1 3 x 2 x3
800
6 x1 4 x 2 2 x3
1 240
x1
x4
0
x3 4 x 4
0
x 4 20
x j N 0 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 j 1, 2, ..., n … množství j-té komponenty ve směsi; bi i 1, 2, ..., m … minimální požadované množství i-té látky ve směsi; aij i 1, 2 ,..., m; j 1, 2, ..., n …množství i-té látky v jednotkovém množství j-té komponenty; cj j 1, 2, ..., n …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
a11 x1 a12 x 2 ... a1n x n b1 a 21 x1 a 22 x 2 ... a 2 n x n b2 ................................................. a m1 x1 a m 2 x 2 ... a mn x n bm , x j 0, j 1, 2, ..., n a současně minimalizují funkci
z c1 x1 c2 x2 ... cn xn Maticově lze totéž zapsat v jednodušším tvaru:
Ax b, x o, z c T x min, přičemž jednotlivé matice byly popsány již při formulaci obecného matematického modelu úlohy výrobního plánování.
61
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 Energie (kcal) Bílkoviny(g) Vitamin B (mg) Vitamin C (mg) Cena (Kč/j)
P1 (j) 2 350 61 1,1 26
P2 (j) 3 540 67 0,2 50
P3 (j) 700 16 0,7 100 80
P4 (j) 2 830 216 8,1 50
P5 (j) 370 0,3 600 100
P6 (j) 200 25 1,3 630 15
Sestavíme matematický model dané úlohy. Řešení Označíme xj j 1, 2, ..., 6 použité množství potraviny Pj v jídelníčku. Máme zřejmě nalézt minimum funkce
z 26 x1 50 x2 80 x3 50 x4 100 x5 15x6 za podmínek
2 350 x1 3 540 x 2 700 x3 2 830 x 4 370 x5 200 x6 3 000 61x1
67 x 2 16 x3 216 x 4
1,1x1
0,2 x 2 0,7 x3
8,1x 4 0,3x5 1,3x6
100 x3
600 x5 630 x6
75
xj
0.
25 x6
70 1,8
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
z 0,12 x1 0,14 x2 0,17 x3 za podmínek (postupně podle zadání) 62
x1 x 2 x3 800
x3 0,15 x1 x 2 x3 x1 0,2 x1 x 2 x3
x1 2 x 2 4 x3 2 x1 x 2 x3 x j 0 pro j 1, 2, 3, neboli (po úpravě)
x1
x2
x3 800
0,15 x1 0,15 x 2 0,85 x3
0
0,8 x1 0,2 x 2 0,2 x3
0
x1
2 x3 xj
0 0 pro j 1, 2, 3.
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 j 1, 2, ..., n … počet kusů výchozího celku rozděleného j-tým způsobem; bi i 1, 2, ..., m … minimální požadovaný počet kusů i-té části celku; aij i 1, 2 ,..., m; j 1, 2, ..., n …počet kusů i-té části celku vznikající j-tým způsobem dělení výchozího celku; cj j 1, 2, ..., n …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
a11 x1 a12 x 2 ... a1n x n b1 a 21 x1 a 22 x 2 ... a 2 n x n b2 ................................................. a m1 x1 a m 2 x 2 ... a mn x n bm , x j 0, j 1, 2, ..., n a současně minimalizují funkci
z c1 x1 c2 x2 ... cn xn Maticově:
Ax b, x o, z c T x min .
63
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 Délka 50cm Délka 80cm Odpad (cm) Počet řezů
V1 2 1 20 3
V2 4 0 0 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.
64
a11 x1 a12 x 2 ... a1n x n b1 a 21 x1 a 22 x 2 ... a 2 n x n b2 ................................................. a m1 x1 a m 2 x 2 ... a mn x n bm .
(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 R0 , 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
x kx1 (1 k )x 2 , kde k 0, 1 ,
(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 m n 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í.
65
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
S1 (t) S2 (t) S3 (t) Cena (Kč/t)
V1 (t)
V2 (t)
V3 (t)
V4 (t)
10 8 5 5 000
5 5 8 3 000
4 1,2 2,5 2 000
2 5,6 10 2 800
Disponibilní množství (t) 2 000 1 800 2 000
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.
N (kg) P (kg) K (kg) Náklady (Kč/kg)
H1 (kg)
H2 (kg)
H3 (kg)
H4 (kg)
0,02 0,04 0,015 20
0,5 0,06 0,09 40
0,4 0,2 0,018 35
0,3 0,1 0,06 32
66
Disponibilní množství (kg) 60 55 10
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. S (t) SZ (hod) Zisk (Kč/ha) 6.6
T1 (ha) 20 40 20 000
T2 (ha) 60 40 40 000
T3 (ha) 20 60 30 000
T4 (ha) 40 80 50 000
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. Seno (kg) Siláž (kg) Koncentráty (kg) Norma potřeby 6.8
Bílkoviny (g) 50 20 180 2 000
Vápník (g) 6 4 3 120
Vitamíny (mg) 2 1 1 40
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. 50cm 30cm Odpad (cm)
V1
V2
V3
V4
V5
4 0 0,2
3 2 0,1
2 4 0
1 5 0,2
0 7 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.
67
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 50% Kávové boby K1 50% Kávové boby K2 Kávové boby K3
Standard 25% 50% 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,5 x1 0,25 x 2 40 0,5 x1 0,5 x 2 60 0,25 x 2 25 0
x1
x2 0
68
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)
z 20 000 x1 14 000 x2 maximální. První tři nerovnice vyjádříme v úsekovém tvaru:
x1 x 2 1 80 160 x1 x 2 1 120 120 x2 1. 100 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í
1 400 000 20 000 x1 14 000 x2 , tj. x1 x 2 1. 70 100
Zakreslíme tuto přímku do množiny přípustných řešení.
69
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
70
Souřadnice bodu C získáme řešením soustavy rovnic
0,5 x1 0,25 x 2 40 0,5 x1 0,5 x 2 60. 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
0,25 x2 25 0,5 x1 0,5 x 2 60. 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) z A 20 000 0 14 000 0 0 x1 = 80, x2 = 0 (bod B) z B 20 000 80 14 000 0 1 600 000 x1 = 40, x2 = 80 (bod C) z C 20 000 40 14 000 80 1 920 000 x1 = 20, x2 = 100 (bod D) z D 20 000 20 14 000 100 1 800 000 x1 = 0, x2 = 100 (bod E) z E 20 000 0 14 000 100 1 400 000 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
z 22 000 x1 11 000 x2 .
71
Dosadíme-li za z zisk 1 100 000Kč a upravíme na úsekový tvar, dostaneme x1 x 2 1. 50 100
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í:
x1 x1B ( x1C x1B )k (1 k ) x1B kx1C x2 x2 B ( x2C x2 B )k (1 k ) x2 B kx2C ,
k 0, 1 .
Odtud pro libovolný vektor optimálního řešení x opt plyne, že
x opt (1 k )x B kx C , k 0, 1 ,
(7.1.3)
přičemž
x B (80, 0) T , x C (40, 80) T . 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
z max 22 000 80 11 000 0 1 760 000 .
72
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ě 0,
1 1 3 , , a 1. Máme 8 2 4
x1 (1 0)(80, 0) T 0(40, 80) T (80, 0) T x B , 1 1 x 2 1 (80, 0) T (40, 80) T (75, 10) T , 8 8 1 1 x 3 1 (80, 0) T (40, 80) T (60, 40) T , 2 2 3 3 x 4 1 (80, 0) T (40, 80) T (50, 60) T , 4 4 x 5 (1 1)(80, 0) T 1(40, 80) T (40, 80) T x C . 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
73
3 x1 4 x 2 30 x2 6 0
x1
x 2 0. 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
74
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í?
+
-
Je to jediné optimální řešení? řešení -
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í
Konec
75
+
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é. T Výchozím základním řešením je vektor x 0 0, 0, ..., 0, b1 , b2 , ..., bm . 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í.
76
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 z k xk u , kde B je množina indexů nezákladních proměnných, γk kB
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í z u k xk , ze které je patrné, proč se hodnota kB
úč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)
77
0,5 x1 0,25 x 2 40 0,5 x1 0,5 x 2 60 0,25 x 2 25 x j 0, j 1, 2 z 20 000 x1 14 000 x 2 max . Po převedení vlastních omezení na soustavu rovnic dostáváme
0,5 x1 0,25 x 2 x3
40
0,5 x1 0,5 x 2
60
x4
x5 25
0,25 x 2
x j 0, j 1, 2, 3, 4, 5. 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
1 2
1 4
1
0
0
40
80
x4
1 2
1 2
0
1
0
60
120
1 4
0 0
0 0
1 0
25 0
---
x5 z
0 -20 000 -14 000
Vektor výchozího základního řešení x 0 0, 0, 40, 60, 25 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). T
Tabulka 7.3.2 Simplexová tabulka z příkladu 7.1.1 po prvním přepočtu podíly Báze x1 x2 x3 x4 x5 bi x1
1
1 2
2
0
0
80
160
x4
0
1 4
-1
1
0
20
80
0 0
1 4
0 40 000
0 0
1 0
25 1 600 000
100
x5 z
-4 000
Z této tabulky je vidět další základní řešení x1 80, 0, 0, 20, 25 , 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. T
Tabulka 7.3.3 Výsledná simplexová tabulka z příkladu 7.1.1 Báze x1 x2 x3 x4 x5 bi 1 0 4 -2 0 40 x1 0 1 -4 4 0 80 x2 0 0 1 -1 1 5 x5 0 0 24 000 16 000 0 1 920 000 z 78
Protože v indexním řádku jsou samé nezáporné hodnoty, vyjadřuje tato tabulka optimální řešení, které je určeno vektorem
x 2 x opt 40, 80, 0, 0, 5
T
a z 2 z max 1 920 000.
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 2 4 Délka 50 (cm) 1 0 Délka 80 (cm) 20 0 Odpad (cm) 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
79
x1 x 2 35 2 x1 4 x 2 52 18,
x1 kde x1 , x2 N 0 , které minimalizuje funkci
z 20 x1 . Přidružená soustava rovnic v kanonickém tvaru je
x1 x 2 x3 2 x1 4 x 2
35 x4
x6 x5
x1
52
x7 18.
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
z x6 x7 . 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
1 2 1 -20 0 3
1 4 0 0 0 4
1 0 0 0 0 0
0 -1 0 0 0 -1
0 0 -1 0 0 -1
0 1 0 0 -1 0
0 0 1 0 -1 0
35 52 18 0 0 70
x3
1 2
0
1
1 4
0
14
0
22
x2 x7 z z´
1 2
1 -20 1
1 0 0 0
0 0 0 0
14 0 0 0
0 -1 0 -1
0 0 -1
0 1 0 0
13 18 0 18
x3
0
0
1
1 4
1 2
14
12
13
x2 x1 z z´
0 1 0 0
1 0 0 0
0 0 0 0
14 0 0 0
1 2
1 4
-1 -20 0
0 0 -1
12 1 20 -1
4 18 360 0
x3 x6 x7 z z´ Uprav.
z´
80
1 4
Optimální řešení je tedy dáno vektorem xopt1 (18, 4, 13, 0, 0) T . Tomuto řešení odpovídá hodnota účelové funkce z 360.
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
1 4
1 2
13
1 2
x2 x1 z
0 1 0
1 0 0
0 0 0
0 0
-1 -20
4 18 360
x4 x2 x1 z
0 0 1 0
0 1 0 0
4 1 0 0
1 0 0 0
2 1 -1 -20
52 17 18 360
1 4
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.
(18, 4, 13, 0, 0), (18, 5, 12, 4, 0), (18, 6, 11, 8, 0), (18, 7, 10, 12, 0), (18, 8, 9, 16, 0), (18, 9, 8, 20, 0), (18, 10, 7, 24, 0), (18, 11, 6, 28, 0), (18, 12, 5, 32, 0), (18, 13, 4, 36, 0), (18, 14, 3, 40, 0), (18, 15, 2, 44, 0), (18, 16, 1, 48, 0), (18, 17, 0, 52, 0). 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.
81
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
z 4 x1 2 x2 za podmínek
x1 3x 2 9 2 x1 3 x 2 18 2 x1 x 2 10 xj 0 7.4
j 1, 2.
Ř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.
S1 (q) S2 (q) Slévárna (hod) Zisk (Kč/q)
V1 (q)
V2 (q)
V3 (q)
V4 (q)
V5 (q)
10 5 4 1 000
8 6 1 900
12 2 5 800
20 4 4 1 200
6 6 1 900
Disponibilní množství (q) 6 000 2 000 1 000
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.
82
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
Ax b, x o,
(8.1.1)
z c x max, T
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ť y ( y1 , y 2 , ..., y m ) T . Úlohu LP s matematickým modelem
AT y cT , y o,
(8.1.2)
f y b min T
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 y i 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:
83
0,5 y1 0,5 y 2
20 000
0,25 y1 0,5 y 2 0,25 y3 14 000 yi 0, i 1, 2, 3 a současně minimalizují funkci
f 40 y1 60 y 2 25 y3 . 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 n m Počet proměnných m n Počet vlastních omezení AT Matice strukturních koeficientů A Vektor požadavků b c Vektor cen c b ≤ ≥ Typ omezení ano ano Nezápornost proměnných max min Typ extrému účelové funkce 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
z 15 x1 8 x 2 min 3 x1 4 x 2 18 x1 3 x 2 24 5 x1 2 x 2 25 3 x1 3 x 2 33 x j 0, j 1, 2. Ř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í.
84
Tabulka 8.1.2 Dvojice duálně sdružených omezení Primární model Duální model
z 15x1 8x2 min
f 18 y1 24 y 2 25 y3 33 y 4 max
3x1 4 x2 18 x1 3x2 24 5x1 2 x2 25
y1 0 y2 0 y3 0
3x1 3x2 33
y4 0
x1 0
3 y1 y 2 5 y3 3 y 4 15
x2 0
4 y1 3 y 2 2 y3 3 y 4 8
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
z 2 x1 7 x 2 max x1 2 x 2 3x3 6 x1 4 x 2 9 x3 12 x j 0, j 1, 2, 3 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
x1 2 x 2 3x3 6 x1 2 x 2 3x3 6 x1 4 x 2 9 x3 12 nebo ekvivalentně
x1 2 x 2 3x3 6 x1 2 x 2 3x3 6 x1 4 x 2 9 x3 12. Dostáváme tedy úlohu LP (ekvivalentní s úlohou ze zadání příkladu)
85
z 2 x1 7 x 2 max x1 2 x 2 3 x3 6 x1 2 x 2 3 x3 6 x1 4 x 2 9 x3 12 x j 0, j 1, 2, 3. K takto formulované úloze existuje podle definice 8.1.1 symetrická duálně sdružená úloha ve tvaru:
f 6 y1 6 y 2 12 y 3 min y1 y 2 y 3 2 2 y1 2 y 2 4 y 3 7 3 y1 3 y 2 9 y 3 0 y i 0, i 1, 2, 3. Tuto úlohu lze zapsat pouze pomocí dvou strukturních proměnných u1 y1 y 2 a u 2 y3 . Máme
f 6u1 12u 2 min u1 u 2 2 2u1 4u 2 7 3u1 9u 2 0 u 2 0. 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
z 2 x1 7 x2 max
f 6u1 12u 2 min
x1 2 x2 3x3 6
u1 R
x1 4 x2 9 x3 12
u2 0
x1 0 x2 0 x3 0
u1 u 2 2 2u1 4u 2 7 3u1 9u 2 0
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.
86
Uvažujme nyní úlohy LP popsané matematickými modely
Ax b, x o,
(8.2.1)
z c T x max a
Ax b, x o,
(8.2.2)
z c T x min, 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ť y ( y1 , y 2 , ..., y m ) T . Úlohu LP s matematickým modelem
AT y cT , f y T b min resp.
AT y cT , f y T b max 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).
87
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 0 z
x2 0
x3 24 000
x4 16 000
x5 0
bi 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 z 0 0 24 000 16 000 0 y4 y5 y1 y2 y3 Přídatné proměnné Strukturní proměnné Duální úloha
zmax 1 920 000 fmin
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.
y opt (24 000, 16 000, 0, 0, 0) T ,
88
f min 1 920 000.
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 = x1 , x2 , ..., xn
T
přípustné řešení primární úlohy a
y = y1 , y 2 , ..., y m přípustné řešení příslušné duální úlohy. Tato řešení jsou optimální tehdy a jen tehdy, když platí: T
m
x j 0 aij y i c j i 1 m
x j 0 aij y i c j i 1 n
y i 0 aij x j bi j 1 n
y i 0 aij x j bi . j 1
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
0,5 x1 0,25 x 2 40 0,5 x1 0,5 x 2 60 0,25 x 2 25 x j 0, j 1, 2, 3 a
x opt 40, 80, 0, 0, 5 . T
Pro duální úlohu potom
89
0,5 y1 0,5 y 2
20 000
0,25 y1 0,5 y 2 0,25 y3 14 000 yi 0, i 1, 2, 3 a
y opt (24 000, 16 000, 0, 0, 0) T . Ř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 0,5 40 0,25 80 40 0,5 40 0,5 80 60 0,25 80 25 40 > 0 80 > 0
Duální úloha 24 000
> 0 16 000 > 0 0 = 0 0,5 24 000 0,5 16 000 20 000 0,25 24 000 0,5 16 000 0,25 0 14 000
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
z 4 x1 18x2 30 x3 5x4 za podmínek
3x1 x 2 4 x3 x 4 3 2 x1 4 x 2 x3 x 4 3 x j 0, j 1, 2, 3, 4. Řešení Duální úloha: nalézt minimum funkce
f 3 y1 3 y 2 za podmínek
3 y1 2 y 2 4 y1 4 y 2 18 4 y1 y 2 30 y1 y 2 5 yi Tuto úlohu vyřešíme graficky.
90
0, i 1, 2.
Obrázek 8.3.1 Řešení duální úlohy
Je tedy optimální řešení v bodě A a f min 36. Souřadnice bodu A získáme zřejmě řešením soustavy
y1 4 y 2 18 4 y1 y 2 30. 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
x1opt x4opt 0. Protože je dále y1opt y 2opt 6 0, platí podle téže věty, že příslušná vlastní omezení primární úlohy (první a druhé) jsou splněna jako rovnosti, tj.
x 2opt 4 x3opt 3 4 x 2opt x3opt 3. Řešením této soustavy získáváme
x2opt
9 15 , x3opt . 17 17
Jediným optimálním řešením dané (primární) úlohy je tedy T
9 15 x opt 0, , , 0 , z max 36. 17 17
91
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 4 2 0,5m (ks) 0 1 0,8m (ks) 0 0 1,2m (ks) 0 0,2 Odpad (m)
V3 1 0 1 0,3
V4 0 2 0 0,4
V5 0 1 1 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í
4 x1 2 x 2 x3 x2
500 2 x 4 x5 1 000
x3
x5 400 xj
0,
j 1, 2, 3, 4, 5
a současně minimalizovat funkci
z x1 x2 x3 x4 x5 . 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
f 500 y1 1 000 y 2 400 y3 za podmínek
4 y1
1
2 y1 y 2
1
y1
y3 1 2 y2
1
y 2 y3 1 y i 0, i 1, 2, 3. 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.
92
Tabulka 8.3.5 Řešení duální úlohy simplexovou metodou Báze y1 y2 y3 y4 y5 y6 4 0 0 1 0 0 y4 2 1 0 0 1 0 y5 1 0 1 0 0 1 y6 0 2 0 0 0 0 y7 0 1 1 0 0 0 y8 f -500 -1 000 -400 0 0 0
y7 0 0 0 1 0 0
y8 0 0 0 0 1 0
bj 1 1 1 1 1 0 1
1 2
y4 y5 y6 y2
4 2 1 0
0 0 0 1
0 0 1 0
1 0 0 0
0 1 0 0
0 0 1 0
0 12 0 1 2
0 0 0 0
y8 f
0 -500
0 0
1 -400
0 0
0 0
0 0
12 500
1 0
y4 y1
0 1
0 0
0 0
1 0
-2
0 0
1 14
0 0
0
1 2
y6
0
0
1
0
12
1
1 4
0
3 4
y2
0
1
0
0
0
0
1 2
0
1 2
y8 f
0 0
0 0
1 -400
0 0
0 250
0 0
12 375
1 0
1 2
y4 y1
0 1
0 0
0 0
1 0
-2
0 0
1 14
0 0
0
1 2
y6
0
0
0
0
12
1
3 4
-1
1 4
y2
0
1
0
0
0
0
1 2
0
1 2
y3 f
0 0
0 0
1 0
0 0
0 250
0 0
12 175
1 400
1 2
1 2
1 1 2
500 1 4
625 1 4
825
Z výsledné simplexové tabulky je vidět řešení obou duálně sdružených úloh. Máme x opt (0, 250, 0, 175, 400, 0, 0, 0) T ,
z min 825,
T
y opt
1 1 1 1 , , , 0, 0, , 0, 0 , 4 4 2 2
f max 825.
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 x1opt 0 4 y1opt 1, což jenom potvrzuje oprávněnost předpokladů této věty. 93
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 y1opt , y 2opt , ..., y mopt , můžeme optimální hodnotu účelové funkce primární úlohy vyjádřit ve tvaru z max f min b1 y1opt b2 y 2opt ... bm y mopt .
Předpokládejme nyní změnu požadavkového čísla bk o hodnotu Δbk,, kde 1 k m . Označíme-li odpovídající změnu optimální hodnoty účelové funkce z , platí z max z b1 y1opt b2 y 2opt ... (bk bk ) y kopt ... bm y mopt ,
odkud po úpravě dostaneme vztah
z bk y kopt , tedy y kopt
z . bk
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) z max 24 000 5 120 000; b) z max 16 000 5 80 000; c) z max 0 5 0. 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
94
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í. n
bi ), jeho ocenění je nulové ( yiopt 0 ), zatímco Je-li výrobní zdroj nevyužit ( aij x opt j j 1
n
bi ) jeho ocenění je kladné ( yiopt 0 ). při vyčerpání výrobního zdroje ( aij x opt j j 1
Je-li ocenění všech výrobních činitelů spotřebovaných na určitý výrobek větší než zisk, m
0 ). Jestliže který tento výrobek vynáší ( aij yiopt c j ), jde o nerentabilní výrobek ( x opt j i 1
zisk určitého výrobku je stejný jako ocenění všech spotřebovaných výrobních činitelů m
0 ). ( aij yiopt c j ), je výhodné tento výrobek vyrábět ( x opt j i 1
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.
95
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
A (g) B (g) C (g) Cena (kg)
S1 (kg)
S2 (kg)
S3 (kg)
S4 (kg)
0 2 10 150
2 2 5 100
4 0 4 120
5 4 10 250
Požadované množství (kg) 5 6 18
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. 96
Řešení Označíme-li xj nakoupené množství suroviny Sj v kg ( j 1, 2, 3, 4 ), máme za úkol minimalizovat funkci
z 150 x1 100 x2 120 x3 250 x4 za podmínek
2 x 2 4 x3 5 x 4 5 000 2 x1 2 x 2
4 x 4 6 000
10 x1 5 x 2 4 x3 10 x 4 18 000 xj
0,
j 1, 2, 3, 4.
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 0 -2 -4 -5 x5 -2 -2 0 -4 x6 -10 -5 -4 -10 x7 -150 -100 -120 -250 z
x5 1 0 0 0
x6 0 1 0 0
x7 0 0 1 0
bi -5 000 -6 000 -18 000 0
-5 -2
1 0
0 1
0 102
-5 000 -2 400
0 0
0 0
101 -15
1 800 270 000 2 500 550 332 500
x5 x6
0 0
-2 -1
-4
x1 z
1 0
1 2
2 5
-25
-60
1 -100
x2
0
1
2
5 2
12
0
x6
0
0
14 5
1 2
12
1
0 102
0 0
-10
0 0
-15
x1 z
1 0
4 5
3 5
1 -37,5
0 -12,5
1 10
100
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í.
97
Příklad 8.5.2 Duálně simplexovou metodou vyřešíme úlohu
x1 x 2 10 7 x1 2 x 2 14 x j 0,
j 1, 2
z 5 x1 3x 2 min . Ř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 x4 z
-1 7 -5
-1 2 -3
1 0 0
0 1 0
-10 14 0
x2 x4 z
1 5 -2
1 0 0
-1 2 -3
0 1 0
10 -6 30
Cvičení 8.1
K dané úloze
z 105 x1 65 x 2 57 x3 min 5 x1 x 2 x3 20 10 x1 2 x 2 4 x3 25 x j 0, j 1, 2, 3. sestavte úlohu duální.
8.2
K dané úloze
z 6 x1 11x 2 x3 max x1
x3 5 2 x 2 4 x3 8
2 x1 3 x 2 4 x3 17 x j 0, j 1, 2, 3. sestavte úlohu duální tak, aby s ní byla a) symetricky sdružená; b) smíšeně symetricky sdružená. 98
8.3
Je dána úloha lineárního programování
z 60 x1 24 x 2 48 x3 max 4 x1 4 x 2 4 x3 120 3 x1 x 2 2 x3 78 x j 0, j 1, 2, 3. Pomocí věty o rovnováze rozhodněte, zda jsou vektory
x (18, 0, 12) T a y (6, 12) T 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í
z 144 x1 96 x 2 144 x3 min 3 x1 3 x 2 3x3 72 3 x1 x 2 2 x3 36 x j 0, j 1, 2, 3. 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 x2 z
1 0 0
0 1 0
3 -1 9
-1 1 1
2 -1 8
20 30 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.
99
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 i 1, 2 ,..., m; j 1, 2, ..., n …přepravované množství zboží od i-tého dodavatele k j-tému odběrateli (tzv. strukturní neznámé); ai i 1, 2, ..., m … kapacita i-tého dodavatele; bj j 1, 2, ..., n … požadavek j-tého odběratele; cij i 1, 2 ,..., m; j 1, 2, ..., n …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
x11 x12 ... x1n a1 x21 x22 ... x2 n a2 xm1 xm 2 ... xmn am
(9.1.1)
x11 x21 ... xm1 b1 x12 x22 ... xm 2 b2 x1n x2 n ... xmn bn
(9.1.2)
a současně minimalizují funkci
z c11 x11 c12 x12 ... c1n x1n c 21 x 21 c 22 x 22 ... c 2 n x 2 n c m1 x m1 c m 2 x m 2 ... c mn x mn
(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ě;
100
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 D1 D2 : : Dm Požadavky
O2 c11
c12
x11
x12
c21 x21 : : cm1 xm1 b1
c22 x22 : : cm2 xm2 b2
……
On
Kapacity c1n
……
x1n c2n
……
x2n : :
……
xmn bn
……
a2 : :
cmn
……
a1
am
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
n
i 1
j 1
ai b j .
(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. 101
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 m n ai b j např. hodnoty xij , kde K ai b j . K i 1 j 1 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. m
n
i 1
j 1
Jestliže platí ai b j , ú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
m
j 1
i 1
b j ai . 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 102
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
n
a b i 1
i
j 1
j
, ú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
n
a b i 1
i
j 1
j
. 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 D1 D2 D3
O3
10
7
5
4
12
6
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 10 7 5 100 D1 D2 D3 Požadavky
20
4
12
6
0
7
2
3
0
50
130
30
103
Kapacity 100 80 50 230
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 P1 P2 P3 Požadavky
S2
S3
S4
Kapacity
44
23
14
19
22
14
20
3
8
36
30
49
460
300
575
25
495 475 390 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 m
n
i 1
j 1
ai b j 1 360 tun.
104
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 44 23 14 P1 460 35 22 14 20 P2 265 210 8 36 30 P3 365 460 300 575 Požadavky
S4
Kapacity 19
3 49 25 25
495 475 390 1 360
Dostáváme výchozí základní řešení
x1 (460, 35, 0, 0, 0, 265, 210, 0, 0, 0, 365, 25) T a pro odpovídající hodnotu účelové funkce máme
z1 44 460 23 35 14 265 20 210 30 365 49 25 41 130. 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.
105
Tabulka 9.3.3 Indexová metoda S1 S2 44 23 P1 70 22 14 P2 300 8 36 P3 390 460 300 Požadavky
S3
S4 14
425
Kapacity 19
20
150
3 25
30 575
49 25
495 475 390 1 360
Dostáváme výchozí základní řešení
x 2 (70, 0, 425, 0, 0, 300, 150, 25, 390, 0, 0, 0) T a pro odpovídající hodnotu účelové funkce máme
z 2 44 70 14 425 14 300 20 150 3 25 8 390 19 425. 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).
106
Tabulka 9.3.4 Metoda VAM S1 P1
44 70
P3
390 460 14 22 x
Sloupcové rozdíly
S3 23
22
P2
Požadavky
S2
14 495
14 300
8
80
19 3 25
30 575 6 6
49 25 16 16 x
Řádkové rozdíly
Kapacity
20
36 300 9 9
S4
495
5
5
9
475
11
11
6
390
22
x
1 360
Z tabulky 9.3.4 dostáváme výchozí základní řešení x 3 (0, 0, 495, 0, 70, 300, 80, 25, 390, 0, 0, 0) T
a pro odpovídající hodnotu účelové funkce máme
z3 14 495 22 70 14 300 20 80 3 25 8 390 16 485. 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 u1 , u 2 , ..., u m a duální proměnné, které se vztahují k odběratelům, označujeme v1 , v2 , ..., vn . Příklad 9.4.1 Sestavíme duální úlohu k dopravní úloze se dvěma dodavateli a třemi odběrateli.
107
Řešení Primární úloha:
x11 x12 x13
a1 x 21 x 22 x 23 a 2
x11
b1
x 21 x12
b2
x 22
x13
x 23 b3 xij 0, i 1, 2,
j 1, 2, 3
z c11 x11 c12 x12 c13 x13 c 21 x 21 c 22 x 22 c 23 x 23 min . Duální úloha:
u1
c11
v1
u1
c12
v2
u1
v3 c13 u 2 v1 u2
c 21 c 22
v2
u2
v3 c 23
f a1u1 a 2 u 2 b1v1 b2 v 2 b3 v3 max . Příklad 9.4.2 Sestavíme duální úlohu k obecné dopravní úloze. Řešení Primární úloha: n
x j 1
ij
ai
ui R,
i 1, 2, ..., m
ij
bj
v j R,
j 1, 2, ..., n
m
x i 1
xij 0 m
Duální úloha:
ui + vj ≤ cij, i 1, 2, ..., m , m
n
z cij xij min. i 1 j 1
f =
n
a u b v i 1
i i
j 1
j
j
j 1, 2 ,..., n
max.
(9.4.1) (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í).
108
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 „-”.
109
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 3 5 2 1 50 V1 40 10 4 7 5 3 70 V2 30 40 2 9 6 4 90 V3 30 60 30 40 40 100 210 Požadavky Ř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:
u1 v 2 5 u1 v 3 2 u 2 v3 5 u 2 v4 3 u 3 v1 2 u3 v4 4 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.
110
Tabulka 9.4.2 Test optimálnosti Z1 Z2 Z3 -5 3 5 V1 - 40 10 -3 4 1 7 V2 + 30 2 0 9 0 V3 30 30 40 40 Požadavky -2 5 2 vj
Z4 2 -1 1 + 5 3 40 6 4 60 100 0
Kapacity
ui
50
0
70
3
90
4
210
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 1 30. Tabulka 9.4.3 Výpočet nového základního řešení Z1 Z2 Z3 Z4 V1 V2
-4
3 -
-3
5 - 10
4
2 0 40
7 -1
5
-
+ 30 2 -1 9 -1 6 30 30 40 40 -1 5 2
V3 Požadavky vj
1 - + 3 40 4 60 100 1
Kapacity
ui
50
0
70
2
90
3
210
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 V1 V2 V3 Požadavky vj
-4
3 0 -
-3
5 -
4 -
7 -1 40
2 -1 30 30 -1
2 40 5 -
9 -1 40 5
1 10 3 30
6 40 2
4 60 100 1
111
ui
50
0
70
2
90
3
210
Optimálním řešením dopravní úlohy z příkladu 9.4.1 je tedy
x opt kx opt1 (1 k )x opt2 , k 0, 1 x opt1 (0, 10, 40, 0, 0, 30, 0, 40, 30, 0, 0, 60) T x opt2 (0, 0, 40, 10, 0, 40, 0, 30, 30, 0, 0, 60) T s minimální hodnotou účelové funkce
z min 2 40 1 10 7 40 3 30 2 30 4 60 760. 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.
112
Tabulka 9.5.1 O1 D1 D2 D3 Požadavky
20
O2
O3
10
7
5
O4 100
4
12
6
0
7
2
3
0
50
130
30
Kapacity 100 80 50 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í Řádkové O1 O2 O3 O4 Kapacity rozdíly 10 7 5 100 100 2 5 x D1 100 4 12 6 0 80 4 4 6 D2 20 30 30 7 2 3 0 50 + ε 2 3 3 D3 50 ε 20 50 130 + ε 30 1 360 + ε Požadavky 3 5 2 0 Sloupcové 3 x 3 0 rozdíly 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 -7 10 -9 7 D1 4 -13 12 D2 20 -6 7 2 D3 50 20 50 Požadavky 4 -1 vj
O3
O4 Kapacity 5 -101 100 100 100 6 0 80 30 30 3 -3 0 50 + ε ε 130 + ε 30 1 360 + ε 6 0
113
ui -1 0 -3
Je tedy zřejmé, že získané řešení je jediné optimální řešení. Je tedy
x opt (0, 0, 100, 0, 20, 0, 30, 30 , 50, 0, 0) T a
z min 5 100 4 20 6 30 0 30 2 50 860. 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).
114
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 P1 P2 P3 Požadavky 9.2
5
8
6
3
2
7
11
5
4
6
9
9
460
580
340
Kapacity 560 800 400
380
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 D1 D2 D3 D4 Požadavky
9.3
H. Brod Pelhřimov
Jihlava
P2
P3
Kapacity
2
1
3
4
2
5
3
8
5
7
9
10
500
200
350 250 100 300
300
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 R1 R2 R3
O2
O3
5
7
10
4
12
5
7
2
3
115
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
9.5
11
S1
-
S2
-
S3
Z2 4
6
7
10
8
30 9
30
9
10
3
Z4 17
40
40 5
-
12
-
60
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 D1 D2 D3 D4 Požadavky
9.6
Z3
O2
6 100 13 10 6 100
9 10 2 90 4 6 100
O3 11 10 30 11 70 3 100
O4 3 4 8 60 1 40 100
O5 11 8 1 4 100 100
Kapacity 110 120 130 140
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 M1 M2 M3 M4 Požadavky
P2
P3
P4
P5
P6
Kapacity
12
15
14
20
16
13
11
10
14
15
20
18
15
12
19
15
13
19
18
16
17
14
16
12
162
175
220
116
264
312
267
200 320 380 500
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 D1 D2 D3 D4 Požadavky
9.8
38 200 15 18 25 200
O2 20 26 300 19 24 300
O3 22 20 25 220 32 40 260
O4 18 24 25 32 240 240
Nalezněte optimální řešení problému z příkladu 9.3.1.
117
Kapacity 200 300 220 280
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=
1.5
a) nelze; b) x = r - 2s + t; c) x = -(36 + 4l)r - (11 + 101l)s + lt, l R ; 27 8 1 d) x = r+ st; 19 19 19
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) b) c) d)
1.10 a) b) c) d)
9 9 3 b - c - d, 4 4 8
b=
4 1 4 1 8 a + c + d, c = - a + b - d, d = a + 6b - 6c; 9 6 9 6 3
k = 2; k = -2; k1 = -2, k2 = 4; k1 = 1, k2 = 2; pravdivé; nepravdivé; nepravdivé; pravdivé;
118
r
1.11
jistě platí, že c1o ci v i o, kde c1 0, ci 0, i 2, 3, ..., r , důkaz plyne i 2
bezprostředně z definice 1.4.1;
Matice 2.1
1 14 9 11 5 ; a) U 5 9 5 2 8
6 6 6 6 6 ; b) V 0 6 24 21 9 13 7 6 6 1 ; c) X 9 8 0 0 15
11 0 3 5 13 ; d) Y 23 13 15 10 10 e) Z
2.2
1 167 98 95 77 2 ; 24 38 111 15 14 79
28 91 28 84 ; a) AB = 21 62 25 59
3 1 2 b) AB = 4 9 3 ; 2 1 2 19 51 42 32 31 34 12 43 c) AB = ; 0 0 0 0 10 17 6 15
2 0 d) AB = 9 1 ; 15 21 2.3
a) BA neexistuje;
3 1 2 b) BA = 4 9 3 ; 2 1 2
119
2 10 18 26 44 42 40 38 c) BA = ; 7 2 3 8 33 29 25 21 d) BA neexistuje;
8 28 14 32 50 4 8 4 22 40 2.4 a) R = ; 36 18 54 90 14 4 2 2 2 2
56 28 64 b) S = 28 14 32 ; 64 32 77 2.5
a) b) c) d) e) f)
3; 4; 2; 1; 4; 3;
2.6
a) lineárně nezávislé; 1 b) pro r = lineárně závislé, jinak lineárně nezávislé; 2 c) lineárně nezávislé;
2.7 a) A-1 =
1 1 3 ; 13 5 2
2 7 11 1 b) A = 2 7 11 ; 54 2 7 11 -1
3 3 1 1 c) A = 41 19 13 ; 20 14 6 2 -1
2 0 1 2 0 1 1 0 -1 d) A = ; 1 1 0 0 2 0 0 1
120
1 1 0 2.8 X = 1 0 1; 0 1 1 5 6 15 2.9 X = 1 1 5 ; 10 11 22
Determinanty 3.1 365; 3.2 6; 3.3 0; 3.4 vektory jsou lineárně závislé, protože A 0; 3.5
1 ; 6 198
Soustavy lineárních rovnic 4.1
x 1, 2, 1, 1 ;
4.2
3 3 1 x , , ; 5 2 20
4.3
14 ... řešení neexistuje
T
T
T
7 2 9 9 ... x 3x3 , x3 , x3 , x3 R 15 3 2 3 17 5 9 14 ... x , , ; 14 14 14 T
4.4
x z1 1, 3, 0, 0
T
x z2
3 8 , 0, , 0 7 7
3 5 x z 3 , 0, 0, 7 7
x z4
T
T
1 8 0, , , 0 5 5
T
121
x z5
1 5 0, , 0, 4 4
T
T
5 8 x z 6 0, 0, , ; 7 7 T
4.5
8 4 x x2 , x2 , 0 , x2 R 5 3 8 x z1 , 0, 0 5
T
4 x z 2 0, , 0 3
4.6
degenerované T
degenerované;
x 5 2 x4 , 1 2 x4 , 2 x4 , x4 , x4 R T
x z1 5, 1, 2, 0
T
x z 2 1, 3, 0, 2
T T
x z3
3 1 4, 0, , 2 2
x z4
1 5 0, 4, , ; 2 2
T
4.7
nemá řešení;
4.8
x 3, 1, 1, 0, 2 ;
4.9
desítka stála 20Kč, dvanáctka 22Kč, čtrnáctka 26Kč a šestnáctka 33Kč;
T
Soustavy lineárních nerovnic 5.1 x 2 3x3 x4 ; 2 x3 x4 x5 ; x3 , x3 R, x4 0, x5 0; T
T
1 1 5.2 x (11 3x4 3x5 2 x6 ); 4 x4 x5 x6 ; (7 3x4 x5 2 x6 ) , x4 , x5 , x6 0; 2 2 5.3
4 19 pětiúhelník ABCDE, A , 0, B6, 0, C3, , D0, 5, 3 2
5.4
7 15 neomezená oblast s vrcholy ABC, A , , B2, 0, C5, 0; 2 4
5.5
8 4 1 pětiúhelník ABCDE, A , , B3, , C3, 1, D1, 3, 7 7 5 122
4 E 0, ; 5
1 E , 3; 3
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 2 x1 1,5 x 2 360
0,4 x1 0,6 x 2 120 5 x1 4 x 2 1 200 x1 , x 2 N 0 z 3 500 x1 3 000 x 2 max; 6.2 x j … vyráběné množství výrobku Vj v kg, j = 1, 2
x1 x 2
800
1,75 x1 4 x 2 2 400 5 x1 5 x 2 5 000 x1
300
x 2 400 z 3 000 x1 2 000 x 2 min; 6.3
x j … vyráběné množství výrobku Vj v t, j = 1, 2, 3, 4
10 x1 5 x 2 4 x3 2 x 4 2 000 8 x1 5 x 2 1,2 x3 5,6 x 4 1 800 5 x1 8 x 2 2,5 x3 10 x 4 2 000 xj
0,
j 1, 2, 3, 4
z 5 000 x1 3 000 x 2 2 000 x3 2 800 x 4 max; 6.4
x j … vyráběné množství hnojiva Hj v kg, j = 1, 2, 3, 4 a)
0,02 x1 0,5x2 0,4 x3 0,3x4 0,04 x1 0,06 x 2 0,2 x3 0,1x 4
60 55
0,015 x1 0,09 x 2 0,018 x3 0,06 x 4
10
20 x1 40 x 2
35 x3 32 x 4 7 000 xj
0,
j 1, 2, 3, 4
z x1 x 2 x3 x 4 max; b)
0,02 x1 0,5x2 0,4 x3 0,04 x1 0,06 x 2 0,2 x3
0,3x4 60 0,1x 4 55
0,015 x1 0,09 x 2 0,018 x3 0,06 x 4 10 x1
x2
x3
x 4 500 xj
z 20 x1 40 x 2 35 x3 32 x 4 min;
123
0,
j 1, 2, 3, 4
6.5 x j … množství vyrobených tašek v 10 000m2, j = 1, 2, 3, 4
x1
x2
x3
x4
800
20 x1 60 x 2 20 x3 40 x 4 2 400 40 x1 40 x 2 60 x3 80 x 4 4 000 xj
j 1, 2, 3, 4
0,
z 20 000 x1 40 000 x 2 30 000 x3 50 000 x 4 max; 6.6 x j … množství vyrobených tašek v 10 000m2, j = 1, 2, 3, 4
x1
x2
x3
x4
800
20 x1 60 x 2 20 x3 40 x 4 2 400 40 x1 40 x 2 60 x3 80 x 4 4 000 xj
j 1, 2, 3, 4
0,
z 20 000 x1 40 000 x 2 30 000 x3 50 000 x 4 max; 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
50 x1 20 x 2 180 x3 2 000 6 x1 4 x 2 2 x1
3x3 120
x2
x3
40
xj
0,
j 1, 2, 3
z 30 x1 20 x 2 50 x3 min; 6.8
x j … počet tyčí rozřezaných podle varianty Vj, j = 1, 2, 3, 4, 5 4 x1 3x 2 2 x3 x 4
180
2 x 2 4 x3 5 x 4 7 x5 120 x j N0 ,
j 1, 2, 3, 4, 5
a) z 0,2 x1 0,1x2 0,2 x4 0,1x5 min; b) z x1 x2 x3 x4 x5 min; c) z 4 x1 5x2 5x3 6 x4 7 x5 min;
Řešení úloh lineárního programování 7.1 x opt (60, 160) T ,
z max 690 000Kč;
7.2
x opt (355,56; 444,44) T ,
7.3
x opt (6, 2) T ,
z min 1 955 555,56Kč;
z max 28;
124
7.4
x opt (135, 0, 110, 105, 0, 0, 0) T ,
7.5
x opt kx opt1 (1 k )x opt2, k 0, 1
z max 1 189 000Kč;
x opt1 (0, 0, 0, 200, 200, 800, 0, 0) T x opt2 (0, 200, 0, 200, 0, 400, 0, 0) T , z max 420 000Kč; 7.6
x opt (0, 100, 0, 450, 250, 0, 0) T ,
z max 26 500 000Kč;
7.7
x opt (500, 100, 0, 200, 0, 0, 0) T ,
z max 24 000 000Kč;
7.8
x opt (
7.9
a)
x opt (0, 0, 90, 0, 0, 0, 240) T ,
z min 0;
b)
x opt (30, 0, 30, 0, 0, 0, 0) T ,
z min 60;
c)
x opt (30, 0, 30, 0, 0, 0, 0) T ,
z min 270;
520 200 , 0, , 0, 0, 0) T , 31 31
z min 826Kč;
7.10 x opt (160, 560, 80, 0, 40, 0, 0) T ,
z max 111 000 000Kč;
7.11 úloha nemá řešení;
Dualita 8.1
f 20 y1 25 y 2 max 5 y1 10 y 2 105 y1 2 y 2 65 y1 4 y 2 57 y i 0, i 1, 2;
8.2
a)
f 5 y1 5 y 2 18 y3 18 y 4 17 y5 max y1 y 2 2 y5 6
2 y 3 2 y 4 3 y 5 11 y1 y 2 4 y 3 4 y 4 4 y 5 1 y i 0, i 1, 2, ..., 5; b)
f 5 y1 18 y 2 17 y5 max y1 2 y3 6
2 y 2 3 y 3 11 y1 4 y 2 4 y 3 1 y 3 0; 125
8.3 dané vektory jsou optimální řešení; 8.4
x opt (24, 24, 0, 0, 24) T , y opt (6, 18, 0, 0, 0) T , z min f max 2 592;
8.5
a)
x opt (20, 30, 0, 0, 0) T ,
b)
y opt (1, 8, 0, 0, 9) , T
z max 480Kč;
f min 480Kč;
c) z max 490Kč; = 440Kč; d) z max = 462Kč; e) z max 8.6 x opt2 (125, 0, 0, 300, 400, 0, 0, 0) T , y opt ( 14 , 12 , 12 , 0, 0, 14 , 0, 0) T
z min f max 825 tvrzení věty o rovnováze splněno není;
Dopravní úlohy 9.1
x opt (0, 0, 340, 220, 460, 180, 0, 160, 0, 400, 0, 0) T ,
9.2
x opt kx opt1 (1 k )x opt2, k 0, 1
z min 8 080Kč;
x opt1 (50, 0, 300, 50, 200, 0, 100, 0, 0, 300, 0, 0) T x opt2 (100, 0, 250, 0, 200, 50, 100, 0, 0, 300, 0, 0) T , z min 4 000Kč; 9.3
x opt (6, 2, 0, 0, 0, 8, 0, 5, 0) T ,
9.4
x opt (0, 250, 0, 80, 120, 0, 0, 30, 60, 0, 160, 0) T ,
9.5
x opt (100, 0, 0, 10, 0, 0, 70, 0, 50, 0, 0, 30, 0, 0, 100, 0, 0, 100, 40, 0) T , z min 1 530;
9.6
x opt (0, 0, 200, 0, 0, 0, 162, 138, 20, 0, 0, 0, 0, 37, 0, 31, 312, 0, 0, 0, 0, 233, 0, 267) T
z min 94tkm;
z min 366 000Kč;
z min 17 673tkm; 9.7
x opt (0, 0, 0, 200, 40, 0, 260, 0, 160, 20, 0, 40, 0, 280, 0, 0) T ,
9.8
x opt (0, 0, 495, 0, 70, 300, 80, 25, 390, 0, 0, 0) T ,
126
z min 20 380;
z min 16 485tkm.
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.
127
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
