UP - logo
(UL)
  • Interaktivni prikaz delovanja omrežnega simpleksnega algoritma za problem razvoza [Elektronski vir] = An interactive demonstration of the network simplex algorithm for the transshipment problem : magistrsko delo
    Kosmač, Maja, poučevanje
    Magistrsko delo sestoji iz teoretičnega raziskovalnega in praktičnega dela. V prvem delu obravnavamo dva zelo pomembna problema, ki se ukvarjata z optimizacijo pretokov v omrežjih. To sta problem ... najcenejšega pretoka in njegova posebna, malce poenostavljena oblika, imenovana problem razvoza. Pri slednjem imamo za določanje pretoka po povezavah med vozlišči eno omejitev manj, pri obeh pa strmimo k optimizaciji cene oziroma stroškov prenosa blaga med vozlišči po omrežju. Rešitev vsakega izmed obeh problemov lahko dobimo z uporabo omrežnega simpleksnega algoritma. Za namen razumevanja obeh omenjenih optimizacijskih problemov in delovanja samega algoritma se osredotočamo na matematične koncepte, kot so s-pretok, drevesna rešitev, dopusten in krepko dopusten par vpetega drevesa T in referenčnega vozlišča r, potencial in znižane cene. Navedemo in dokažemo nekatere trditve in izreke. Eden ključnih izrekov nam poda kriterij, kdaj je s-pretok, prirejen dopustnemu paru (T,r), optimalen. Ta rezultat izkorišča tudi omrežni simpleksni algoritem, čigar korake navajamo v tem delu. Nadalje natančno predstavimo posamezen korak algoritma in dokažemo, da algoritem res deluje pravilno. V ta namen se prepričamo, da po vsaki iteraciji algoritma dobimo nek s-pretok, da se po vsaki iteraciji cena s-pretoka zmanjša ali ne spremeni, da je po vsaki iteraciji novi par (T,r) spet krepko dopusten, da se algoritem vedno ustavi po končnem številu iteracij, ter da je s-pretok, prirejen zadnjemu vpetemu drevesu, res optimalna rešitev podanega problema razvoza. Praktični del magistrskega dela vključuje razvoj interaktivne aplikacije v okolju Unity. Aplikacija po korakih prikazuje delovanje omrežnega simpleksnega algoritma na poljubnem omrežju, ki ga vnese uporabnik, na koncu pa vrne optimalno rešitev problema razvoza. Za izdelavo aplikacije smo se odločili, ker je omrežni simpleksni algoritem precej kompleksen in posledično lahko povzroča težave pri razumevanju. V izdelano učno gradivo smo vključili ideje konstruktivistične teorije učenja ter omogočili, da je uporabnik v ta proces aktivno vključen, saj aplikacija na nekaterih korakih od njega zahteva, da izpolni določene naloge, povezane z izvajanjem algoritma. Z izdelavo takšne aplikacije skušamo prispevati k boljšemu razumevanju delovanja algoritma za reševanje problema razvoza, v prvi vrsti študentov 4. letnika Pedagoške fakultete Univerze v Ljubljani, prvostopenjskega študijskega programa Dvopredmetni učitelj, smer: matematika - računalništvo, ki omenjeno učno vsebino spoznajo pri predmetu Kombinatorična optimizacija. Obenem smo s tem izvajalcem tega predmeta omogočili uporabo učnega pripomočka, ki jim je lahko v pomoč pri predstavitvi te učne vsebine študentom. Aplikacija je brezplačno na voljo vsakemu, ki ga ta tematika zanima. V magistrskem delu predstavimo izvor ideje o ustvarjanju takšne aplikacije in njen namen. Predstavimo programsko okolje Unity in navedemo razloge, zakaj smo se odločili za izdelavo aplikacije ravno v tem okolju. Omogoča nam namreč dokaj enostavno realizacijo vizualnih in interakcijskih elementov v primerjavi z nekaterimi drugimi orodji. Korake v aplikaciji vizualiziramo tudi s pomočjo diagramov poteka in opišemo izgled uporabniškega vmesnika aplikacije. Nato podrobno predstavimo celotno implementacijo aplikacije tako z uporabniškega kot tudi s tehničnega oziroma programerskega vidika.
    Vrsta gradiva - magistrsko delo ; neleposlovje za odrasle
    Založništvo in izdelava - Ljubljana : [M. Kosmač], 2024
    Jezik - slovenski
    COBISS.SI-ID - 201475331

    Povezava(-e):

    Repozitorij Univerze v Ljubljani – RUL

Vnos na polico