guje tak, e si na n m idi p ed j zdou nastav maxim ln p pustnou rychlost a p stroj se pak automaticky postar o to, aby auto b hem cel j zdy nikdy tuto

INFORMATIKA Omezova rychlosti (lohy z MO { kategorie P, 25. st)

;

PAVEL T PFER Matematicko-fyzikln fakulta UK, Praha

N mty soutnch loh pr v skonenho 59. ronku Matematick olympi dy { kategorie P ( koln rok 2009/2010) pipravili sloven t organiz toi olympi dy z Fakulty matematiky, fyziky a informatiky Univerzity Komenskho v Bratislav. V na em seri lu zajmavch loh z olympi dy si tentokr t rozebereme jednu lohu z krajskho kola soute, kterou bychom mohli oznait jako grafovou a z rove jako optimalizan. Akoliv se jedn o lohu netradin, k jejmu vye en nebudeme potebovat dn speci ln znalosti, ale pln vystame s prostou logickou vahou a se z kladnmi grafovmi algoritmy. Zaneme jako obvykle zad nm soutn lohy, kter jsme zde oproti pvodn verzi trochu upravili a zkr tili, ani by se ov em jakkoliv zmnil pvodn smysl lohy.

??? Spolenost Expresn po ta doruuje z silky po cel Evrop. V posledn dob ale jej idii asto pehleli dopravn znaky a dost vali pokuty za pekroen maxim ln povolen rychlosti. editel spolenosti proto rozhodl, e nech do kadho auta namontovat omezova rychlosti. Ten fun46

Matematika - fyzika - informatika 20 2010/2011

guje tak, e si na nm idi ped jzdou nastav maxim ln ppustnou rychlost a pstroj se pak automaticky postar o to, aby auto bhem cel jzdy nikdy tuto rychlost nepekroilo. editel spolenosti navc vydal nazen, e si idi mus ped kadou jzdou nastavit takov omezen rychlosti, aby nikde na sv trase nepekroil dnou maxim ln povolenou rychlost.

Sout n loha

Je d na silnin s, po n jezd idii spolenosti Expresn po ta. Tato silnin s obsahuje N mst, mezi nimi vede celkem M rznch silnic. Kad silnice spojuje dv msta, piem silnice se mimo msta k pouze mimorovov (tzn. mimo msta nelze odboit z jedn silnice na jinou). Pro kadou silnici zn me jej dlku (v kilometrech) a maxim ln povolenou rychlost (v kilometrech za hodinu). Pro danou dvojici mst x, y me existovat vce zpsob, jak lze po silnicch dojet z msta x do msta y. Napi te program, kter pro v echny dvojice mst x y ur minim ln as potebn na cestu z msta x do msta y pi pouit omezovae rychlosti a dodren nazen editele spolenosti.

Formt vstupu

Prvn dek obsahuje dv kladn cel sla N , M (1 N 50, 1 M 1000) { poet mst a poet silnic mezi nimi. Jednotliv msta jsou na vstupu oznaena sly 1 a N . Kad z n sledujcch M dk popisuje jednu silnici. Obsahuje tyi sla i, j , d, m, kter ud vaj, e silnice spojujc msta i, j m dlku d kilometr a maxim ln povolenou rychlost m kilometr za hodinu. V echny silnice jsou obousmrn. Mezi dvma msty me vst vce silnic rzn dlky a s rznou maxim ln povolenou rychlost. Mete pedpokl dat, e mezi kadou dvojic mst existuje aspo jedna trasa (kter me bt tvoena vce navazujcmi silnicemi). V echny vzd lenosti a rychlosti jsou na vstupu uvedeny s pesnost nejv e na ti desetinn msta. Pro kadou vzd lenost d plat 1 d 1000000, pro kadou maxim ln povolenou rychlost m plat 5 m 100000.

Formt vstupu

Vstup bude tvoen N dky, z nich kad obsahuje N sel. slo v itm dku a j -tm sloupci uruje minim ln as (v hodin ch) potebn na jzdu mezi msty i, j . Vsledek uvete s pesnost na ti desetinn msta. Matematika - fyzika - informatika 20 2010/2011

47

Poznmka

Pi pr ci s re lnmi sly v potai mohou vznikat zaokrouhlovac chyby. Tuto skutenost mete ve svm e en ignorovat { postupujte, jako kdyby v echny vpoty, kter prov dte, byly pesn.

???

Na konkrtnm pkladu vstupnch dat a jim odpovdajcch vsledk si objasnme zad n a z rove uk eme, m je tato loha zajmav a na co musme d t pozor pi jejm e en. Vstup 44 1 2 40.0 60.0 1 3 20.0 100.0 2 3 40.0 120.0 2 4 25.0 50.0 Vstup

0.000 0.600 0.200 1.300 0.600 0.000 0.333 0.500 0.200 0.333 0.000 1.300 1.300 0.500 1.300 0.000 Podle vstupnch dat si sami nakreslete jednoduch schma zadan silnin st. V uvedenm pkladu se z msta 1 do msta 2 nejrychleji dostaneme pes msto 3. Ujedeme pi tom celkem 60 kilometr rychlost 100 km/h, take doba jzdy bude 0,6 hod. Existuje krat pm spojen mezi msty 1 a 2, kter m dlku pouze 40 km, ale omezen rychlosti na tto silnici na 60 km/h zpsob del dobu jzdy 0,667 hod. Je tedy zejm, e nejkrat cesta mezi msty x, y nemus bt vdy asov nejvhodnj . lohu proto nememe jednodu e pevst na pouh hled n nejkrat ch cest mezi v emi dvojicemi mst, co bychom umli vye it pomoc standardnch grafovch algoritm (Dijkstrv algoritmus, Floydv-Warshallv algoritmus { viz nap. !1]). Ve v e uvedenm pkladu si d le v imnte, e nejrychlej cesta z msta 1 do msta 4 vede po trase 1-2-4, nikoliv 1-3-2-4. Vzhledem k omezen rychlosti na silnici 2-4 na 50 km/h musme takto nastavit omezova 48


rychlosti pro celou jzdu a ji se n m proto nevyplat optimalizovat cestu z msta 1 do msta 2 objkou pes msto 3, jako tomu bylo v pedchozm ppad. Vidme tedy, e pokud vede nejrychlej cesta z msta x do msta y pes msto z , nememe ji zskat prostm sloenm nejrychlej cesty z msta x do msta z a nejrychlej cesty z msta z do msta y. lohu proto nememe e it ani dnm jednoduchm dynamickm programov nm, kter by postupovalo s rostoucm potem mst, jimi na zvolen trase projdme. Pro v echny dal vahy pi e en lohy bude dleit n sledujc pozorov n. A si zvolme jakoukoliv trasu vedouc z msta x do msta y, optim ln nastaven omezovae rychlosti bude rovno minimu z maxim ln rychlosti povolen na silnicch, kter tvo zvolenou trasu. Vy

rychlost na omezovai nastavit nesmme, nastavit ni rychlost se n m nevyplat. Pro dosaen nejkrat doby jzdy mezi ktermikoliv dvma msty m proto smysl nastavovat omezova rychlosti jedin na nkterou z rychlost, kter jsou zad ny na vstupu. Nejrychlej cestu z msta x do msta y bychom mohli teoreticky zskat tak, e bychom nalezli v echny cesty vedouc z x do y, pro kadou z nich bychom urili nastaven omezovae rychlosti (minimum z maxim lnch povolench rychlost na silnicch tvocch tuto cestu) a jej dlku (souet dlek silnic tvocch tuto cestu) a spotali bychom dobu jzdy. Tento postup je ale velmi neefektivn, v ppad hust silnin st bude poet existujcch cest exponenci ln velk vzhledem k N . Vrazn lep e en zsk me vhodnm vyuitm nkterho ze standardnch grafovch algoritm. Uvaovan silnin s pedstavuje hranov ohodnocen neorientovan graf G, vrcholy grafu odpovdaj mstm (je jich N ) a hrany exitujcm silnicm (tch je M ). Ji jsme konstatovali, e omezova rychlosti bude vdy nastaven na nkterou z rychlost uvedench na vstupu. Tchto monch rychlost nen mnoho { nejv e tolik, kolik je silnic. Nabz se tedy monost vyzkou et postupn v echna mon nastaven omezovae rychlosti a pro kadou takovou rychlost v urit, za jak as se dok eme dostat z msta x do msta y. Ozname si symbolem Gv podgraf pvodnho grafu, kter obsahuje jen ty hrany, na nich je rychlost v je t povolena. M me-li tedy nastaven omezova rychlosti na hodnotu v, meme jet pouze po hran ch grafu Gv . Kdy u m me urenou rychlost jzdy, nejlep dobu jzdy dos hneme tehdy, pokud v grafu Gv zvolme nejkrat monou cestu (v kilometrech) vedouc z msta x do msta y. Cel postup e en je t jednou shrneme: Pro kadou rychlost v ze Matematika - fyzika - informatika 20 2010/2011

49

vstupu vytvome graf Gv . V nm urme dlky (v kilometrech) nejkrat ch cest mezi v emi dvojicemi mst x, y a ozname je Dv (x y). Vsledn optim ln doby jzdy pro rychlost v maj hodnotu Dv (x y)=v. Pro kadou dvojici mst x, y zvl pak sta urit, pi kterm v nabv vraz Dv (x y)=v minim ln hodnoty. Tato minim ln hodnota je hledanm vsledkem. Zbv uk zat, jakou asovou sloitost m popsan e en. Podle na eho vodnho pozorov n budeme jako hodnoty v uvaovat v echny rychlosti zadan na vstupu { tch je nejv e M rznch. Graf Gv sestrojme snadno v ase O(M ) tak, e projdeme v echny hrany pvodnho grafu. Pro uren dlky nejkrat cesty v grafu Gv mezi kadou dvojic vrchol se nabzej dva mon pstupy: { Floydv-Warshallv algoritmus, kter tento problm e v ase O(N 3 ) { N -kr t spu tn Dijkstrv algoritmus (pro kad vchoz vrchol), m dojdeme opt k asov sloitosti O(N 3 ), nebo v ppad vyuit haldy zsk me e en v ase O(NM log N ). Celkov asov sloitost e en je tedy O(MN 3 ), pp. O(NM 2 log N ), pamov sloitost algoritmu je O(N 2 ). Pr v popsan e en ale je t nen nejlep mon. Uk eme si nyn jin postup, kter vyuv trochu odli nm zpsobem podobnou my lenku, jako ji zmnn Floydv-Warshallv algoritmus (popis FloydovaWarshallova algoritmu najdete teba v uebnici !1] nebo ve studijnm textu !2]). Nejprve seadme v echny hrany v grafu G do posloupnosti e1 e2 : : : eM tak, aby pro jejich maxim ln povolen rychlosti platilo v1 = = v2 = v3 = = vM . lohu nyn vye me metodou dynamickho programov n. Postupn pro kad k od 1 do M spot me v echny hodnoty dk (x y), kter pedstavuj dlku nejkrat cesty (v kilometrech) mezi msty x y, jestlie se smme pohybovat pouze po hran ch e1 e2 : : : ek . Pokud takov cesta neexistuje, polome dk (x y) rovno nekonenu. Podle de&nice z pedch zejcho e en meme tak ci, e dk (x y) je dlka nejkrat cesty mezi msty x y v grafu Gvk . K vye en lohy sta nalzt hodnoty dk (x y) pro kad k = 1 2 : : : M . Hodnota vrazu dk (x y)=vk pak uruje pslu nou optim ln dobu jzdy pro rychlost vk . Podobn jako v pedchozm e en zsk me hledan vsledek pro kadou dvojici mst x y jako minimum z hodnot dk (x y)=vk zskanch pro k = 1 2 : : : M . Uk eme si nyn, jak lze rychle a elegantn spotat hodnoty dk (x y) na z klad ji zn mch hodnot dk;1 (x y). V k-tm kroku vpotu chceme 'zpstupnit( hranu ek a pepotat hodnoty dk (x y) pro v echny dvojice 50


mst x y. Pi stanoven hodnoty dk (x y) uvaujeme n sledujc dv monosti: 1. V ppad, e nejkrat cesta z msta x do msta y nepouije hranu ek , je dk (x y) = dk;1 (x y): 2. V opanm ppad lze nejkrat cestu z x do y rozdlit na ti seky: z vrcholu x pjdeme do nkterho vrcholu hrany ek , projdeme touto hranou a z jejho druhho konce pjdeme do vrcholu y. V prvnm i ve tetm seku cesty se vyskytuj pouze hrany s slem men m ne k, take optim ln dlku tchto sek u zn me. Jestlie ozname uk1 a uk2 vrcholy spojen hranou ek , potom plat bu

dk (x y) = dk;1 (x uk1) + jek j + dk;1 (uk2 y) nebo

dk (x y) = dk;1 (x uk2 ) + jek j + dk;1 (uk1 y) podle toho, kterm smrem na e trasa proch z hranou ek . Meme si zvolit, zda hranu ek pouijeme nebo ne, a pokud ano, tak

v kterm smru. Vybereme si samozejm nejlep z uvedench t monost. Proto je hodnota dk (x y) rovna minimu z uvedench t monost. Tm jsme zskali rekurzivn vztah pro vpoet hodnot dk (x y) pomoc hodnot dk;1 (x y). V kadm z M krok vpotu (pro k = 1 2 : : : M ) spot me kadou z N 2 hodnot (pro v echny dvojice x y = 1 2 : : : N ) podle uvedenho rekurzivnho vztahu v konstantnm ase. Toto e en m proto asovou sloitost O(MN 2 ). K tomu je je t teba pipotat as potebn na uspo d n hran podle maxim ln povolen rychlosti { to meme provst v ase O(M log M ). Celkov asov sloitost popsanho algoritmu je tedy O(MN 2 + M log M ). Pro dosaen nzk pamov sloitosti si sta uvdomit, e hodnoty dk z visej pouze na hodnot ch dk;1 , nikoliv na hodnot ch ze star ch krok vpotu. Vystame proto s pamt velikosti O(N 2 ), star hodnoty si nemusme pamatovat. Na z vr pipojujeme uk zkov program v Pascalu, kter demonstruje, jak lze pr v popsan algoritmus naprogramovat. Pro uspo d n hran Matematika - fyzika - informatika 20 2010/2011

51

podle maxim ln povolen rychlosti zde pouijeme jednoduch tdic algoritmus pmho vbru, kter m sice asovou sloitost O(M 2 ), ale jeho z pis je zato kr tk a pehledn. Mohli bychom ho samozejm v programu nahradit njakm efektivnj m tdicm algoritmem. Pokud bychom psali program pesn podle v e uvedenho algoritmu, potebovali bychom v nm mt dva exempl e pole na ukl d n vzd lenost mst. V kadm kroku vpotu bychom mli v jednom poli uloeny ji spotan hodnoty dk;1 (x y) a do druhho bychom ukl dali nov potan hodnoty dk (x y). Role obou pol by se pravideln stdaly. Ve skutenosti ale meme napsat program je t spornji { vystame s jedinm polem, v nm budeme v k-tm kroku vpotu uloen hodnoty dk;1 (x y) pmo nahrazovat novmi hodnotami dk (x y). Pi postupnm vpotu prvk dk se n m pak ov em me st t, e msto 'spr vn( hodnoty dk;1 nkde pouijeme ji upravenou novou hodnotu dk . Rozborem monch situac snadno zjistte, e i v takovm ppad zsk me po k-tm kroku vpotu spr vn hodnoty dk (x y). program OmezovacRychlosti const MaxN = 50 MaxM = 1000 NEKONECNO = 1e30

{maximln poet mst = vrchol } {maximln poet silnic = hran} {\uv{nekonen} vzdlenost mst}

type hrana = record i, j: integer d, m: real

{koncov vrcholy hrany} {vzdlenost, max. povolen rychlost}

end var n: m: h: d:

integer {poet mst = vrchol } integer {poet silnic = hran} array1..MaxM] of hrana {seznam vech hran} array1..MaxN, 1..MaxN] of real {vzdlenosti pi pouit prvnch k hran} vysl: array1..MaxN, 1..MaxN] of real {vsledn asy jzd mezi msty}

52


x, y, i, j, k: integer z: hrana function min(a, b: real):real begin if a hk].m then k:=j if k > i then {vmna hran s indexy i, k} begin z:=hk] hk]:=hi] hi]:=z end end {Vlastn vpoet vzdlenost a as :} for k:=1 to m do {k krok vpotu -- povolme vdy hranu hk]}


53

for x:=1 to n do for y:=1 to n do begin dx,y]:=min(dx,y], dx,hk].i] + hk].d + + dhk].j,y]) dx,y]:=min(dx,y], dx,hk].j] + hk].d + + dhk].i,y]) vyslx,y]:=min(vyslx,y], dx,y]/hk].m) end {Vpis vsledk :} for x:=1 to n do begin for y:=1 to n do write(vyslx,y]:8:3) writeln end end.

Literatura 1] Tpfer, P: Algoritmy a programovac techniky, Prometheus, Praha 2007 (2. vydn) 2] Korespondenn semin z programovn MFF UK, studijn materily, http://ksp.m.cuni.cz/tasks/21/cook5.html

Dal mo nosti e itele v Excelu PETR EMANOVSK Prodovdeck fakulta Univerzity Palackho v Olomouci

V l nku !1] popisuj autoi doplkovou aplikaci MS Excelu zvanou eitel a na konkrtnch pkladech ukazuj jej uitenost pi hled n nulovch, maxim lnch a minim lnch hodnot funkc. lohy tohoto typu se asto vyskytuj v matematice, fyzice, ekonomii i v jinch oborech. Pro 54


stedo kolsk studenty je tento numerick n stroj vhodn napklad pi e en rovnic nebo optimalizanch loh, a to zejmna v situacch, kdy je 'run( e en asov n ron nebo stedo kolskmi prostedky obtn realizovateln. eitel tedy pedstavuje bn dostupn software, kter lze s vhodou pouvat v r mci vuky matematiky a dal ch pedmt na stedn kole. Z kladn n vod pro pr ci s eitelem je uveden v l nku !1], ppadn lze nahldnout napklad do publikac !2] nebo !3]. V pedloenm l nku uk eme dal vyuit eitele, konkrtn vyuit daj tzv. citlivostn zpr vy pi e en loh line rnho programov n.

1. lohy linernho programovn

lohy line rnho programov n pedstavuj speci ln ppad optimalizanch loh, pi nich je teba nalzt maxim ln nebo minim ln hodnotu njak line rn funkce, piem je teba vyhovt v em omezujcm podmnk m, kter maj tvar line rnch nerovnic nebo line rnch rovnic. Studenti stednch kol se s jednoduchmi lohami line rnho programov n mohou setkat v semin i z matematiky viz loha o maximalizaci zisku v !1]. Ukame si na tto loze a nkolika jejch modi&kacch z kladn pojmy a postupy tzv. citlivostn analzy line rnho programov n (viz nap. !3]), kter zkoum , jak se mn optim ln e en lohy v z vislosti na zmn ch vstupnch dat modelu. K tto analze lze vyut ji zmiovan citlivostn zpr vy eitele.

1.1 P klad { maximalizace zisku

Paprensk &rma vyr b dva typy se it. Pro konkrtnost je ozname jako A, resp. B . Pi vrob tchto se it jsou pouity dva stroje { stroj na stih n papru a stroj na se v n list. Se it typu A se na stihacm stroji pipravuje 2 minuty a se it typu B se pipravuje 6 minut. Na icm stroji se se it typu A se v 8 minut a se it typu B 4 minuty. Protoe vrobce najm ke kadmu stroji pouze jednoho pracovnka, me kad z obou vrobnch proces trvat pouze 8 hodin denn, tj. 480 minut. Zisk z prodeje kadho se itu typu A in 30 K a zisk z prodeje kadho se itu typu B 40 K. Kolik se it jednotlivch typ by mla &rma vyr bt, aby bylo dosaeno maxim lnho zisku? Jedn se o jednoduchou lohu line rnho programov n s matematickm modelem tvaru: Matematika - fyzika - informatika 20 2010/2011

55

maximalizovat funkci

P (x y) = 30x + 40y za podmnek

2x + 6y 480 8x + 4y 480 x0ay0

(viz !1]).

1.2 e en v Excelu

Pro e en loh line rnho programov n se doporuuje nejprve nastavit nkter parametry eitele. Toto nastaven lze provst v dialogovm okn Monosti e itele, kter je sou st okna Parametry e itele (obr. 1). Pro na e ely je dleit zejmna vybrat poloky Linern model a Nezporn sla. Zapnutm dvoupolohovho pepnae 'Linern model( meme vrazn zkr tit dobu vpotu a rovn tm zmnme podobu nkterch vstupnch dat (nap. tzv. citlivostn zpr vy). Druh dvoupolohov pepna 'Nez porn sla( umouje automaticky zajistit podmnky nez pornosti, kter pak ji nemusme zad vat spolu s ostatnmi omezujcmi podmnkami modelu.

;; ;; ;

Obr. 1 Nastaven parametr eitele pro lohy linernho programovn

56


Pomoc postupu popsanho v !1] lze efektivn urit optim ln e en lohy. V na em ppad se jedn o hodnoty x = 24 a y = 72, co znamen , e je teba vyr bt 24 kus se it typu A a 72 kus se it typu B za den. Maxim ln zisk pak bude init 3600 K (obr. 2).

;;

Obr. 2 Vstup MS Excelu po vpotu optimlnho een eitelem

2. Zprvy e itele

Po ukonen vpotu eitelem m uivatel krom z kladn podoby vstupu vypotench hodnot monost volby vstupu podrobnj ch informac ve form zpr v. eitel nabz ti druhy zpr v { vsledkovou, citlivostn a limitn. Zvolme-li poadovan typ zpr vy v dialogovm okn Vsledky e en (obr. 3), je tato zpr va vygenerov na do samostatnho listu spreadsheet (obr. 4).

;;

Obr. 3 Volba citlivostn zprvy v dialogovm okn Vsledky een


57

; ; Obr. 4 Citlivostn zprva 1

Jak ji bylo uvedeno, budeme se v tomto l nku vnovat citlivostn zpr v. Tato zpr va obsahuje adu dal ch zajmavch informac, kterch me uitel vyut pi diskusi o e en loh line rnho programov n se studenty. Pedpokladem tto innosti je spr vn pochopit nkter pojmy (intervaly stability pro cenov koe&cienty, redukovan ceny, stnov ceny, intervaly stability pro prav strany podmnek) a dok zat je interpretovat pro konkrtn podmnky dan lohy. Podrobn vysvtlen uvedench pojm lze nalzt napklad v publikaci !3]. V n sledujcch odstavcch se budeme vnovat rozboru tchto pojm pro n konkrtn ppad vroby se it.

2.1 Snen nklady a intervaly stability pro cenov koecienty

V imnme si nejprve prvn sti tabulky, viz obr. 4, nadepsan 'Mnn buky(. 'Konen hodnota( zde zejm pedstavuje vypoten optim ln e en x = 24, y = 72 a 'Clov koe&cient( (spr vn by mlo bt 'Cenov koe&cient() ud v zisk z prodeje jednoho se itu typu A, resp. typu B , tj. 50 K, resp. 40 K. Ve sloupci 'Snen n klady( lze pest tzv. redukovan ceny, kter ud vaj maxim ln monou zmnu cenovch koe&cient, kter je t neovlivn celkov zisk. Vzhledem k tomu, e v na em ppad jsou ob hodnoty v tomto sloupci nulov, znamen to, e jak koliv zmna cenovch koe&cient m za n sledek zmnu celkovho zisku. Posledn dva sloupce s nadpisem 'Povolen n rst( a 'Povolen pokles( ud vaj tzv. intervaly stability pro cenov koe&cienty. Pokud budou nap. hodnoty prvnho cenovho koe&cientu 30 mnny v intervalu od 30 ; 16 66666667 do 30 + 50, optim ln e en x = 24, y = 72 se nezmn (zmn se pouze 58


celkov zisk z ). Poznamenejme, e ve skutenosti by Excel bral za krajn body intervalu stability piblin hodnoty 13,3334 a 79,9999. Snadno se meme pesvdit, e pro hodnotu cenovho koe&cientu 13,3333 se optim ln e en skokem mn na x = 0, y = 80 a pro hodnotu 80 na x = 60, y = 0. Pokud by tedy zisk z prodeje jednoho se itu typu A klesl pod spodn hranici intervalu stability (13,3334 K), je ji vhodnj vyr bt pouze se ity typu B , kterch se vyrob 80 kus. Vzroste-li naopak tento zisk nad horn hranici intervalu stability (79,9999 K), je vhodnj vyr bt pouze se ity typu A, kterch se vyrob 60 kus.

2.2 Stnov ceny a intervaly stability pro omezujc podmnky

Ve druh sti tabulky nadepsan 'Omezujc podmnky( jsou nejprve uvedeny 'Konen hodnoty(, kter vyjaduj re ln as, po kter byly oba stroje bhem smny v provozu (kad 480 minut). Porovn me-li tyto hodnoty s hodnotami ve tetm sloupci ('Omezujc podmnka { Prav strana(), vidme, e strojov as byl v obou ppadech vyuit stoprocentn. Tuto informaci lze samozejm vyst i z vstupu na obr. 2 (buky D2, D3). Hodnoty ve sloupci s nadpisem 'Stnov cena( ud vaj n rst celkovho zisku v korun ch pi nav en prav strany pslu n omezujc podmnky o jednotku (v na em ppad o 1 minutu). Pokud by tedy nap. sthac stroj pracoval o 1 minutu dle, pak by pi zachov n v ech ostatnch podmnek vzrostl zisk o 5 K. Prodlouenm pracovn doby icho stroje o 1 minutu by zisk vzrostl o 2,50 K. Poznamenejme, e hodnoty stnovch cen 5 a 2,5 rovn uruj koe&cienty modelu tzv. du ln lohy line rnho programov n (viz nap. !3]), ale tato problematika ji pesahuje r mec monho stedo kolskho uiva. Posledn dva sloupce ud vaj tzv. intervaly stability pro prav strany omezujcch podmnek. Napklad povolen n rst pro pravou stranu prvn omezujc podmnky je 240 a povolen pokles 360, tj. prvn stroj, kter prov d sth n papru, me pracovat bu o 240 minut dle nebo o 360 minut mn, ani by do lo ke zmn optim lnho rozvren vroby. Znamen to, e vzroste-li hodnota prav strany prvn nerovnice modelu o vce ne 240 nebo klesne-li o vce ne 360, pest v bt vroba jednoho z typ se itu vhodn . Konkrtn, pro hodnotu prav strany prvn podmnky 118, dost v me optim ln e en x = 59, y = 0 (obr. 5), tj. pokud pracovn vyuit prvnho stroje nepev hodnotu 118 minut, je optim ln vyr bt 59 kus se itu A se ziskem 1770 K. Vidme rovn, e as druhho stroje, tj. icho, nebude v tomto ppad zcela vyuit (buka D3). Matematika - fyzika - informatika 20 2010/2011

59

; ;

Obr. 5 Vstup MS Excelu po vpotu optimlnho een eitelem 2

Z citlivostn zpr vy (obr. 6) lze tak vyst, e snen n klady pro

y nyn in ;50. To lze interpretovat tak, e zv enm zisku z prodeje jednoho se itu typu B o jakoukoliv hodnotu nepesahujc 50 K se celkov zisk nezmn. Pokud tedy bude zisk ze se itu B men ne 90 K, st le je vhodnj vyr bt pouze se it typu A.

Obr. 6 Citlivostn zprva 2

Bude-li hodnota prav strany prvn podmnky 721, dostaneme optim ln e en x = 0 a y = 120 (obr. 7), tj. pokud pracovn vyuit prvnho stroje neklesne pod hodnotu 721 minut, je optim ln vyr bt 120 kus se itu B se ziskem 4800 K. Vidme rovn, e as druhho stroje, tj. icho, bude v tomto ppad zcela vyuit (buka D3). V tomto ppad lze vyst z citlivostn zpr vy (obr. 8), e snen n klady pro x in ;50. To lze interpretovat tak, e zv enm zisku z prodeje jednoho se itu typu A o jakoukoliv hodnotu nepesahujc 50 K se celkov zisk nezmn. V ppad, e zisk ze se itu A bude men ne 80 K, je st le vhodnj vyr bt pouze se it typu B . 60


; ; ;

Obr. 7 Vstup MS Excelu po vpotu optimlnho een eitelem 3

Obr. 8 Citlivostn zprva 3

Podobnou diskusi lze provst i pro druhou podmnku. V echny uveden vztahy lze studentm demonstrovat postupnm mnnm pslu nch bunk excelovskho se itu a n slednm vpotem novho optim lnho e en eitelem, pp. vygenerov nm nov citlivostn zpr vy. Poznamenejme, e v nkterch ppadech meme dostat neceloseln optim ln e en, kter nem pro na i lohu re ln smysl. Tuto nepjemnost lze odstranit doplnnm podmnek celoselnosti pro mnn buky B5 a C5 v dialogovm okn 'Parametry e itele(. Po pid n tchto podmnek ji e itel ur celoseln optim ln e en, nevygeneruje v ak citlivostn zpr vu.

3. Zv r

Uveden uk zky naznauj, e eitel me bt opravdu uitenm pomocnkem usnadujcm a zpestujcm vuku matematiky a dal ch stedo kolskch pedmt. Jakm zpsobem se jej poda ve vuce vyut ji z le na uitelov kreativit a invenci. Matematika - fyzika - informatika 20 2010/2011

61

Literatura 1] Pra k, P.{ Pra kov , B.: Zkladn pouit eitele v Excelu, Matematika-fyzikainformatika.18, 433{441, 2009. 2] Bro, M.: Microsoft Excel pro manaery a ekonomy, Computer Press, a. s, Brno 2006. 3] Jablonsk , J.: Operan vzkum, kvantitativn modely pro ekonomick rozhodovn, Professional Publishing, Praha 2002.

ZPR VY stedn ronkuMatematick MO #stednkolo kolo 59. 59. ronku olympidy v kategorii A se uskutenilo v termnu 21. { 24. 3. 2010 v Chebu. Organiztorem III. (zvrenho) kola soute byla v letonm roce Krajsk komise MO v Karlovarskm kraji. Ztitu nad $nlovou st MO pevzali PaedDr. Josef Novotn , hejtman Karlovarskho kraje, MUDr. Jan Svoboda, starosta msta Chebu a Mons. Frantiek Radkovsk , biskup plze%sk, kte se zastnili slavnostnho zahjen stednho kola. To se uskutenilo v nedli 21. bezna 2010 v prostorch Fakulty ekonomick Zpadoesk Univerzity v Chebu. Krom soutcch, len #K MO a garant se zahjen soute zastnili rovn pozvan host, mezi nimi byli pedevm zstupci spoleenskho ivota v Chebu a v Karlovarskm kraji a dle zstupci sponzor (skupina &EZ, ECOVIS Corporate Finance s. r. o.). Soutc a lenov #stedn komise MO (#K MO) byli ubytovni v Domov mldee Stedn zdravotnick koly v Chebu. Vlastn sout se pitom po oba soutn dny konala v uebnch Gymnzia Cheb. Na zklad jednotn koordinace loh krajskho (II.) kola v kategorii A pozvala #K MO k asti ve III. kole 51 nejlep62

ch eitel z cel republiky (jeden z nich se vak pedem omluvil). Svho zstupce v stednm kole neml tentokrt pouze Libereck kraj. Soutnmi dny byly 22. a 23. bezen 2010. Na een obou trojic soutnch loh mli soutc ji tradin vyhrazeny vdy 4,5 hodiny istho asu a za kadou lohu mohli pitom zskat maximln 7 bod. Chebt organiztoi pipravili pro soutc a pro leny #K MO atraktivn doprovodn program. Odpoledne po prvnm soutnm dnu bylo vyhrazeno zjezdu do prodn rezervace SOOS pobl Frantikovch Lzn a prohldce historickho centra Chebu. Nsledujc den odpoledne byla pro zjemce zajitna prohldka zmku Kynvart spojen s nvtvou nedalekch Marinskch Lzn. Slavnostn vyhlen vsledk a pedn cen nejlepm soutcm se uskutenilo ve stedu 24. bezna 2010 dopoledne v aule FEK Z&U v Chebu za ptomnosti pedstavitel msta Plze% a zstupc Z&U v Plzni. Pedseda #K MO doc. Jarom r ima podkoval ve svm zvrenm projevu vem, kte se zaslouili o zdrn prbh stednho kola MO v kategorii A, pedevm pak pedsedovi Krajsk komise MO v Karlovarskm kraji { Mgr. Josefu Hazimu { a krtce informoval vechny ptomn o stednm kole v jubilejnm, 60. ronku MO, kter se uskuten v terminu 27. { 30. 3. 2011 v Brn.


guje tak, e si na n m idi p ed j zdou nastav maxim ln p pustnou rychlost a p stroj se pak automaticky postar o to, aby auto b hem cel j zdy nikdy tuto

Recommend Documents