Projekty 08

3 = 190.
Požadavky zákazníků jsou z1 = 250,z2 = 100,z3 = 150 a z4 = 200.
Nejprve vyvezeme všechno, co má první dodavatel: První zákazník chce 250 kusů, tak
mu je dáme: x11 = 250. Druhý zákazník chce 100 kusů, ale první dodavatel už má jenom
60 (původně měl 310, 250 vyvezl), takže x12 = 60. Tím je kapacita prvního dodavatele
vyčerpána a začne vyvážet druhý dodavatel.
První zákazník už je nasycen, takže od druhého dodavatele nedostane nic. Druhý zákazník
ještě potřebuje 40 kusů (původně potřeboval 100 kusů, 60 už dostal od prvního doda-
vatele), takže x22 = 40. Třetí zákazník chce 150 kusů a dostane je, protože druhý do-
davatel má ještě 160 kusů: x23 = 150. Čtvrtý zákazník chce 200, ale dostane už jen 10
– víc druhému dodavateli nezbývá, takže x24 = 10. Tím je vše od druhého dodavatele
vyvezeno a na řadě je třetí dodavatel.
První tři zákazníci už jsou nasyceni, nedostanou od třetího nic. Čtvrtý zákazník chce
ještě 190 kusů, tak je dostane, x34 = 190. Tím jsou všichni dodavatelé vyčerpáni a
všichni zákazníci nasyceni. Výsledná matice je
X =

 250 60 0 00 40 150 10
0 0 0 190

,
Při jejím vyplňování jsme postupovali z jejího levého horního rohu (tj. ze severozápadního
rohu při pohledu jako na mapu) směrem doprava nebo dolů (podle toho, kterým směrem
to ještě šlo), dokud jsme nedošli do pravého dolního rohu.
23. Numerická integrace – lichoběžníková metoda
Napište program, který bude přibližně počítat bintegraltext
a
f(x)dx lichoběžníkovou metodou.
Popis metody: Interval 〈a,b〉 rozdělíme na n stejných dílků. Dělicí body označíme
x0,x1,...xn. Délku jednoho dílku označíme h. Integrál se pak vypočte přibližně jako
bintegraldisplay
a
f(x)dx .= Ln = h
parenleftbigg1
2 f(x0) +f(x1) +f(x2) + ··· +f(xn−1) +
1
2f(xn)
parenrightbigg
Např. 4integraltext
2
ln(x2 + 1)dx by se pro n = 8 spočítal přibližně jako
4integraldisplay
2
ln(x2 + 1)dx .= L8 = 0,25
parenleftbigg1
2 ln(2
2 + 1) + ln(2,252 + 1) + ln(2,52 + 1) + ···
··· + ln(3,752 + 1) + 12 ln(42 + 1)
parenrightbigg
Bližší popis metody a další příklady najdete ve skriptech z BMA3 v kapitole o numerickém
integrování.
♥ Jednoduchá varianta: Funkce f bude zadaná přímo v programu. Zadávat se budou
jen krajní body intervalu 〈a,b〉 a počet dílkůn. Když se bude chtít integrovat jiná funkce,
program se přepíše. Případně lze mít v programu definováno několik různých funkcí,
uživatel si bude moci vybrat některou z nich.
Trochu složitější varianta: Funkce se bude zadávat až po spuštění programu (knihovnu
na tohle najdete na Q).
Složitější varianta: Funkce f se bude zadávat až po spuštění programu. Dále se budou
zadávat krajní body intervalu 〈a,b〉 a přesnost ε, s jakou chceme integrál vypočítat.
Pak se bude postupně počítat L1,L2,L4,L8,..., dokud nezačne vycházet zhruba tentýž
výsledek, tj. dokud nebude pro nějaké n platit |L2n −Ln| < ε. (Pokuste se při výpočtu
L2n použít Ln a jenom k němu něco přidat.)
Ošetřete případ, kdy se hodnoty na ničem neustalují: Zadejte nejmenší možnou hodnotu
kroku h. Bude-li překročena, výpočet ukončete a vypište vhodné hlášení.
Můžete též ošetřit možné chybové stavy – zadání špatného výrazu pro funkci, nemožnost
dosazení některého z dělicích bodů do funkce apod.
24. Numerická integrace – Simpsonova metoda
Napište program, který bude přibližně počítat bintegraltext
a
f(x)dx Simpsonovou metodou.
Popis metody: Interval 〈a,b〉 rozdělíme na n stejných dílků, přičemž n musí být sudé.
Dělicí body označíme x0,x1,...xn. Délku jednoho dílku označíme h. Integrál se pak
vypočte přibližně jako
bintegraldisplay
a
f(x)dx .= Sn = h3 (f(x0) + 4f(x1) + 2f(x2) + 4f(x3) + ··· + 2f(xn−1) + 4f(xn−1) +f(xn))
(funkční hodnoty v krajních bodech jsou tam jednou, ve vnitřních bodech s lichými indexy
čtyřikrát, ve vnitřních bodech se sudými indexy dvakrát).
Např. 4integraltext
2
ln(x2 + 1)dx by se pro n = 8 spočítal přibližně jako
4integraldisplay
2
ln(x2 + 1)dx .= S8 = 0,253
parenleftBig
ln(22 + 1) + 4ln(2,252 + 1) + 2ln(2,52 + 1) + 4ln(2,752 + 1)+
+2ln(32 + 1) + 4ln(3,252 + 1) + 2ln(3,52 + 1) + 4ln(3,752 + 1) + ln(42 + 1)
parenrightBig
Bližší popis metody a další příklady najdete ve skriptech z BMA3 v kapitole o numerickém
integrování.
♥ Jednoduchá varianta: Funkce f bude zadaná přímo v programu. Zadávat se budou
jen krajní body intervalu 〈a,b〉 a počet dílkůn. Když se bude chtít integrovat jiná funkce,
program se přepíše. Případně lze mít v programu definováno několik různých funkcí,
uživatel si bude moci vybrat některou z nich.
Trochu složitější varianta: Funkce se bude zadávat až po spuštění programu (knihovnu
na tohle najdete na Q).
Složitější varianta: Funkce f se bude zadávat až po spuštění programu. Dále se budou
zadávat krajní body intervalu 〈a,b〉 a přesnost ε, s jakou chceme integrál vypočítat.
Pak se bude postupně počítat S2,S4,S8,S16,..., dokud nezačne vycházet zhruba tentýž
výsledek, tj. dokud nebude pro nějaké n platit |S2n −Sn| < ε. (Můžete se při výpočtu
S2n pokusit použít nějaké předchozí výsledky z výpočtu Sn.)
Ošetřete případ, kdy se hodnoty na ničem neustalují: Zadejte nejmenší možnou hodnotu
kroku h. Bude-li překročena, výpočet ukončete a vypište vhodné hlášení.
Můžete též ošetřit možné chybové stavy – zadání špatného výrazu pro funkci, nemožnost
dosazení některého z dělicích bodů do funkce apod.
25. Interpolace nebo kubický splajn
Trochu složitější než ostatní zde uvedené numerické metody, ale dají se k tomu kreslit
celkem pěkné obrázky.
Zběžný popis problému: Je zadáno n + 1 bodů [x0,y0],[x1,y1],...,[xn,yn] (x-ové
souřadnice jsou navzájem různé) a chceme těmito body proložit křivku. Bližší popis
metod pro hledání těchto křivek najdete ve skriptech z BMA3.
26. Metoda nejmenších čtverců – přímka
Napište program, který pomocí metody nejmenších čtverců aproximuje zadanou tabulku
hodnot přímkou.
♥ Jednoduchá varianta: K zadaným bodů najděte pouze rovnici přímky. (Pro řešení
soustavy dvou rovnic o dvou neznámých doporučuji Cramerovo pravidlo.)
Složitější varianta: Najděte rovnici přímky. Výslednou přímku nakreslete spolu se
zadanými body. Umožněte zadávání bodů i ze souboru (nebo jenom ze souboru – dle
vlastního uvážení).
Bližší popis problému: Mámen+1 bodů [x0,y0],[x1,y1],...,[xn,yn] a hledáme přímku
y = ax+b, která by procházela mezi těmito body co nejlépe.
Koeficienty a,b hledané přímky najdeme jako řešení soustavy rovnic (pozor na pořadí
neznámých!)
A11b + A12a = B1
A21b + A22a = B2,
kde A11 = (n+ 1) (tj. počet zadaných bodů), A12 = A21 = x0 +x1 + ··· +xn,
A22 = x20 +x21 + ··· +x2n,
B1 = y0 +y1 + ··· +yn, B2 = x0 ·y0 +x1 ·y1 + ··· +xn ·yn.
(Odvození těchto rovnic a řešený příklad i s obrázkem najdete ve skriptech z BMA3,
kapitola Aproximace funkcí.)
27. Metoda nejmenších čtverců - parabola
Napište program, který pomocí metody nejmenších čtverců aproximuje zadanou tabulku
hodnot parabolou.
♥ Jednoduchá varianta: K zadaným bodů najděte pouze rovnici paraboly. (Pro řešení
soustavy tří rovnic o třech neznámých doporučuji Cramerovo pravidlo.)
Složitější varianta: Najděte rovnici paraboly. Výslednou parabolu nakreslete spolu se
zadanými body. Umožněte zadávání bodů i ze souboru (nebo jenom ze souboru – dle
vlastního uvážení).
Bližší popis problému:Mámen+1 bodů [x0,y0],[x1,y1],...,[xn,yn] a hledáme parabolu
y = ax2 +bx+c, která by procházela mezi těmito body co nejlépe.
Koeficienty a,b,c hledané paraboly najdeme jako řešení soustavy rovnic (pozor na pořadí
neznámých!)
A11c + A12b + A13a = B1
A21c + A22b + A23a = B2
A31c + A32b + A33a = B3,
kde A11 = (n+ 1) (tj. počet zadaných bodů), A12 = A21 = x0 +x1 + ··· +xn,
A13 = A31 = A22 = x20+x21+···+x2n, A23 = A32 = x30+x31+···+x3n, A33 = x40+x41+···+x4n,
B1 = y0+y1+···+yn, B2 = x0·y0+x1·y1+···+xn·yn, B3 = x20·y0+x21·y1+···+x2n·yn
(Odvození těchto rovnic a podobný příklad (i když ne zrovna na parabolu) najdete ve
skriptech z BMA3, kapitola Aproximace funkcí.)