VYSOKÁ ŠKOLA POLYTECHNICKÁ JIHLAVA Katedra matematiky
MATEMATIKA PRO EKONOMY
Radek Stolín
2011
Za jazykovou a věcnou správnost obsahu díla odpovídá autor. Text neprošel jazykovou ani redakční úpravou. ©
Radek Stolín, 2011
ISBN 978-80-87035-35-1
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
3
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
4
Ú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 leden 2010 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 + 3 0 4 = 3 3 2 0 2 4 = 6 2 6 . a) K = A + B = 3 2 1 0 2 3 2 1 2 1 1 3 1 1 0 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 2 3 0 4 - 3 0 4 3 2 2 = c) Q = AB – BA = 3 2 1 0 2 1 1 3 1 1 3 1 0 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 8 - 10 3 2 = 13 5 6 . = 23 8 7 4 6 1 4 8 3 1 2 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 0 3
1 2 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 3 0 3 4 0 0
0 0 0 5 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). 4 3 2 2.2
Určete součin AB následujících dvojic matic:
7 7 1 3 5 1 , B = ; a) A = 4 5 5 10 9 11
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
7 12 1 5 3 11 ; 3 6 2 2 9 7
2 3 1 3 B = 5 10 . 2 5 4 3
2.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 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
4 3 2 B 5 5 1. 3 3 3
2.9 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 k1 , k2 , ..., kn
K
a1k1 a 2k2 ...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
1 4 0 3
Určíme doplněk prvku a32. Řešení Nejprve podle definice 3.2.1 určíme M32. Máme
28
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 1
r j
r 1
a rj M rj .
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
2 3 0 3
5 3 7 7 . 2 1 7 8
3.3 Vypočítejte determinant
1 4 2 5 9 3.4
2 7 5 9 1
3 4 5 6 7 8 9 10 11. 1 1 1 2 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 , ..., x n ) 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 , x 2 ... , x n 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 , x 2 , 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 x1
x 2 4 x3
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 3 x3 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 3 x 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 2 0 2 0
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 3 x 2 x3 2 x 4 7 x1 x 2 x3 x 4 3 3 x1 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 3 x 2 x3 3 x 4 4 x1 x 2 3 x3 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 3 x 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 , xn2 ... , xnm 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 3x1 5 x 2
1 x4
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 7 0 3 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 0 72 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 0 7 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 83 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
6 1 0 0 73 0 7 7 0 72 0 17 0 127 3 25 1 0 72 0 7 7 0 1 1 2 0 21 0 0 0 1 1 7 5 3 75 0 0 0 14 14 14 1 0 143 0 0 143 14 46 4 1 . 1 0 0 7 7 7 1 1 21 0 1 0 2 2 2 1 1 0 2 2 0 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 z 8 (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)
B (kg)
Disponibilní mnoţství (hod)
2 4 3 1 600
0,25 2 1 4 400
45 100 300 50 MAX
Nechť je x1 (x2) hmotnost vyráběných výrobků A (B) v kilogramech. Celkovou cenu výroby pak můţeme vyjádřit jako součet ceny x1 kg výrobku A, tj. 600x1, a ceny x2 kg výrobku B, tj. 400x2. Platí tedy, ţe celková cena výroby je
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
2 x1
1 x 2 45. 4
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
0
x2
0
x1 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 3x2 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)
P2 (j)
P3 (j)
P4 (j)
P5 (j)
P6 (j)
2 350 61 1,1 26
3 540 67 0,2 50
700 16 0,7 100 80
2 830 216 8,1 50
370 0,3 600 100
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
25 x6
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.
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
V2
2 1 20 3
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ři druhy 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)
T2 (ha)
T3 (ha)
T4 (ha)
20 40 20 000
60 40 40 000
20 60 30 000
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. Bílkoviny (g)
Vápník (g)
Vitamíny (mg)
50 20 180 2 000
6 4 3 120
2 1 1 40
Seno (kg) Siláţ (kg) Koncentráty (kg) Norma potřeby
6.8 Firma Nomo s.r.o. dostala zakázku na výrobu ţelezných regálů. Má k dispozici 400 tyčí o délce 2,20m, které potřebuje rozřezat na spoje o délce 50cm a 30cm. Pro splnění této zakázky bude těchto tyčí o délce 50cm potřebovat alespoň 180ks a tyčí o délce 30cm alespoň 120ks. Moţné varianty rozřezání tyčí jsou uvedeny v tabulce. 50cm 30cm Odpad (cm)
V1 4 0 0,2
V2 3 2 0,1
V3 2 4 0
V4 1 5 0,2
V5 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 Kávové boby K1 Kávové boby K2 Kávové boby K3
Standard
50% 50% -
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 x 2 25 0,5 x1 0,5 x2 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) x1 = 80, x2 = 0 (bod B) x1 = 40, x2 = 80 (bod C)
z A 20 000 0 14 000 0 0 z B 20 000 80 14 000 0 1 600 000 z C 20 000 40 14 000 80 1 920 000
x1 = 20, x2 = 100 (bod D) x1 = 0, x2 = 100 (bod E)
z D 20 000 20 14 000 100 1 800 000 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 x1 x2 x5 z
1 0 0 0
0 1 0 0
4 -4 1 24 000
-2 4 -1 16 000 78
0 0 1 0
40 80 5 1 920 000
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 Délka 50 (cm) Délka 80 (cm) Odpad (cm)
2 1 20
4 0 0
Neznámými veličinami xj jsou počty dvoumetrových tyčí řezaných podle varianty Vj, j = 1,2. Hledáme takové řešení soustavy nerovnic
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 1 x3 2 x6 1 x7 -20 z 0 z´ 3 Uprav. z´
x2 1 4 0 0 0 4
x3 1 0 0 0 0 0
x4 0 -1 0 0 0 -1
x5 0 0 -1 0 0 -1
x6 0 1 0 0 -1 0
x7 0 0 1 0 -1 0
bj 35 52 18 0 0 70
14
0
22 13 18 0 18
x3
1 2
0
1
1 4
0
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
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
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 3 x 2 9 2 x1 3x 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 Počet proměnných Počet vlastních omezení Matice strukturních koeficientů Vektor poţadavků Vektor cen Typ omezení Nezápornost proměnných Typ extrému účelové funkce
n m A b c ≤ ano max
m n AT c b ≥ ano min
Pozn. Jestliţe jsou některá vlastní omezení maximalizační úlohy typu „≥“, před formulací úlohy duálně sdruţené je musíme převést na omezení typu „≤“ vynásobením číslem (-1). Podobně jestliţe jsou v minimalizační úloze omezení typu „≤“, musíme je převést na omezení typu „≥“ vynásobením číslem (-1). Příklad 8.1.2 Ukáţeme si formulaci duální úlohy k úloze LP popsané matematickým modelem
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 3x3 6 x1 2 x 2 3x3 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
x2
x3
x4
x5
bi
0
0
24 000
16 000
0
1 920 000
z
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.
x2opt 4 x3opt 3 4 x2opt 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 0,5m (ks) 0,8m (ks) 1,2m (ks) Odpad (m)
4 0 0 0
2 1 0 0,2
V3
V4
V5
1 0 1 0,3
0 2 0 0,4
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
y7
y8
bj
f
4 2 1 0 0 -500
0 1 0 2 1 -1 000
0 0 1 0 1 -400
1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
1 1 1 1 1 0
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
1 2
0 0 0 0
y8 f
0 -500
0 0
1 -400
0 0
0 0
0 0
12 500
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
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
y4 y5 y6 y7 y8
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 3 x 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 -1 x3 7 x4 -5 z
x2 -1 2 -3
x3 1 0 0
x4 0 1 0
bi -10 14 0
1 5 -2
1 0 0
-1 2 -3
0 1 0
10 -6 30
x2 x4 z
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 3x 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 3x1 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 3x 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 všech rovnic soustavy (9.1.2), zmenšený o součet zbývajících rovnic soustavy (9.1.1) (stejný vztah platí pro libovolnou rovnici soustavy (9.1.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
Jestliţe platí
n
a b i 1
i
j 1
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 D1 D2 D3 Poţadavky
20
Kapacity
10
7
5
100
4
12
6
0
7
2
3
0
50
130
30 103
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
21
16
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 P1
44 460 22
P2
-
P3
460
Poţadavky
23 35
21 -
14 265
8
16
20
36
Kapacity
-
210
300
S4
3 -
30 365 575
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), (2, 2), (1, 4), (1, 3) atd., pokud některé z těchto polí nebude jiţ proškrtnuto po obsazení polí s niţšími sazbami - viz tabulka 9.3.3.
105
Tabulka 9.3.3 Indexová metoda S1 S2 44
P1
70
P2
-
P3 Poţadavky
23 -
22
S4 21
425 14
300 8
390 460
S3
300
16 -
20 150
36
Kapacity
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 21 425 14 300 20 150 3 25 8 390 22 400. 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 22 400tkm. 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 políčka (3, 1), (2, 1), (2, 4), (2, 2) a nakonec v libovolném pořadí (1, 3) a (2, 3). Pro úplnost poznamenejme, ţe sedlovými body při daném zadání byla políčka (2, 4) a (3, 1).
106
Tabulka 9.3.4 Metoda VAM S1 P1
44 70
P3
390 460 14 22 x x
Sloupcové rozdíly
S3 23
22
P2
Poţadavky
S2
21 495
14 300
8
80
16 3 25
30 575 1 1 1 1
49 25 13 13 13 x
Řádkové rozdíly
Kapacity
20
36 300 9 9 9 9
S4
495
5
5
5
2
475
11 11 11
6
390
22
x
x
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 21 495 22 70 14 300 20 80 3 25 8 390 20 930. Metodou VAM jsme tedy získali řešení s hodnotou účelové funkce 20 930tkm. 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 ,
n
z cij xij min. i 1 j 1
m
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
V1
-
V2
-
V3 Poţadavky
5 40
4
7
5
30 9
40
1
10
2
30 30
2
3 40
6 40
4 60 100
50 70 90 210
Řešení Soustava rovnic, ze které pro prověřované řešení spočítáme duální proměnné u1, u2, u3, v1, v2, v3, v4, má v tomto případě následující tvar:
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 V1 V2 V3 Poţadavky vj
-5
3 -
-3 30 30 -2
4 1 + 2 0
Z3
Z4
5
2 -1 1 40 10 + 7 5 3 30 40 9 0 6 4 60 40 40 100 5 2 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 -4 3 5 2 0 V1 - 10 40 -3 4 7 -1 5 V2 + 30 40 2 -1 9 -1 6 V3 30 60 30 40 40 100 Poţadavky -1 5 2 1 vj
1 + 3 4
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 -4 3 0 5 2 1 50 V1 40 10 -3 4 7 -1 5 3 70 V2 40 30 2 -1 9 -1 6 4 90 V3 30 60 30 40 40 100 210 Poţadavky -1 5 2 1 vj 111
ui 0 2 3
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
O2
O3
O4
Kapacity
10
7
5
100
4
12
6
0
7
2
3
0
20
50
130
30
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 třetího odběratele. Tabulka 9.5.2 Odstranění degenerace při určování výchozího základního řešení O1 O2 O3 O4 Kapacity Řádkové rozdíly D1
10 4
D2
20
D3
20 3 3 3 3
Poţadavky Sloupcové rozdíly
7 -
5 100
12 -
7
6 30
2 50 50 5 x x x
100 0 30
3 ε 130 + ε 2 2 3 3
0 30 0 0 0 x
100
2
5
x
x
80
4
4
4
2
50 + ε
2
3
3
4
230 + ε
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 -3 7 D1 4 -7 12 D2 20 -6 7 2 D3 50 20 50 Poţadavky 4 5 vj
O3
O4 Kapacity 5 -101 100 100 100 6 0 80 30 30 3 -3 0 50 + ε ε 130 + ε 30 230 + ε 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 , 0, 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.3, 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
Jihlava H. Brod Pelhřimov 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
P2
P3
Kapacity
2
1
3
4
2
5
3
8
5
7
9
10
500
200
350 250 100 300
300
9.3 Ze tří rybníků s plánovanými výlovy 10t , 8t a 5t kaprů mají být tyto ryby rozvezeny do tří obcí s poţadavky 6t, 7t a 8t kaprů. Vzdálenosti mezi jednotlivými rybníky a obcemi (v km) jsou uvedeny v tabulce. Jakým způsobem mají být ryby rozvezeny, aby celkový objem přepravy (v tkm) byl minimální a přitom aby z rybníka R2 bylo vyloveno a odvezeno všechno plánované mnoţství? O1 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
O3 9
10
11 -
2 90 4 6 100
O4
O5 3
-
10 30 11 70 3 100
Kapacity
11 -
4 -
8 -
8 60
1 -
1 40 100
4 100 100
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 základní řešení dopravní úlohy. Nalezněte optimální řešení této úlohy. O1 D1 D2 D3 D4 Poţadavky
38 200 15 18 25 200
O2
O3
20 26 300 19 24 300
O4
22 -
18 -
20 25 220 32 40 260
24 25 32 240 240
9.8 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) x = r + 2s + t; b) x = r - 2s + lt, l R; 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 a + c + d, 9 6
k = 2; k = -2; k1 = -2, k2 = 4; k1 = 1, k2 = 2; pravdivé; nepravdivé; nepravdivé; pravdivé;
118
c=-
4 1 8 a + b - d, d = a + 6b - 6c; 9 6 3
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 1 14 9 11 5 ; 5 9 5 2 8
2.1 a) U
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 42 32 19 51 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;
2.4
8 28 14 32 50 4 8 4 22 40 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 pětiúhelník ABCDE, A , 0, 3
56 12 43 B , 0, C , , D0, 5, 9 5 5
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 (
520 200 , 0, , 0, 0, 0) T , 31 31
z min 826Kč;
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;
7.9 a)
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 ,
z min 94tkm;
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 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 2. upravené vydání Vydala Vysoká škola polytechnická Jihlava, Tolstého 16, Jihlava, 2011 Tisk Ediční oddělení VŠPJ, Tolstého 16, Jihlava Náklad 500 výtisků ISBN 978-80-87035-35-1
128