prikaz prve stranice dokumenta Aukcijski algoritmi u mrežnoj optimizaciji
  Download
PDF 648.65 KB
master's thesis
Aukcijski algoritmi u mrežnoj optimizaciji
Zagreb: University of Zagreb, Faculty of Science, 2018. urn:nbn:hr:217:465785
Stoić, Dora
University of Zagreb
Faculty of Science
Department of Mathematics

Institutional repository: Repository of the Faculty of Science

Cite this document

Stoić, D. (2018). Aukcijski algoritmi u mrežnoj optimizaciji (Master's thesis). Zagreb: University of Zagreb, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:217:465785

Stoić, Dora. "Aukcijski algoritmi u mrežnoj optimizaciji." Master's thesis, University of Zagreb, Faculty of Science, 2018. https://urn.nsk.hr/urn:nbn:hr:217:465785

Stoić, Dora. "Aukcijski algoritmi u mrežnoj optimizaciji." Master's thesis, University of Zagreb, Faculty of Science, 2018. https://urn.nsk.hr/urn:nbn:hr:217:465785

Stoić, D. (2018). 'Aukcijski algoritmi u mrežnoj optimizaciji', Master's thesis, University of Zagreb, Faculty of Science, accessed 23 November 2024, https://urn.nsk.hr/urn:nbn:hr:217:465785

Stoić D. Aukcijski algoritmi u mrežnoj optimizaciji [Master's thesis]. Zagreb: University of Zagreb, Faculty of Science; 2018 [cited 2024 November 23] Available at: https://urn.nsk.hr/urn:nbn:hr:217:465785

D. Stoić, "Aukcijski algoritmi u mrežnoj optimizaciji", Master's thesis, University of Zagreb, Faculty of Science, Zagreb, 2018. Available at: https://urn.nsk.hr/urn:nbn:hr:217:465785

Metadata
TitleAukcijski algoritmi u mrežnoj optimizaciji
AuthorDora Stoić
MentorMarko Vrdoljak (mentor)
Committee memberMarko Vrdoljak (predsjednik povjerenstva)
Committee memberJosip Tambača (član povjerenstva)
Committee memberMiljenko Marušić (član povjerenstva)
Committee memberBoris Guljaš (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Science
(Department of Mathematics)
Zagreb
Defense date and country2018-07-16, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Abstract
Aukcijski algoritmi, temeljeni na principu klasične aukcije, djeluju suprotno klasičnim algoritmima mrežne optimizacije jer u svakoj iteraciji ne poboljšavaju nužno ni primarnu ni dualnu funkciju cilja, no na kraju nalaze optimalnu vrijednost. Zasnovani su na metodama nediferencijabilne optimizacije. U početku opisujemo aukcijski algoritam za klasični problem dodjeljivanja, te se bavimo raznim pitanjima kao što su \(\epsilon\)-skaliranje, problem nedopustivosti, obrnuti algoritam i slično. Razlog tomu je što se problem toka minimalnog troška lako može pretvoriti u problem dodjeljivanja, te su ta pitanja zajednička svim vrstama promatranih problema. Stoga, kasnije u radu, promatramo adaptaciju algoritma za problem maksimalnog toka, transportni problem, problem najkraćih putova i problem toka minimalnog troška. Za problem toka minimalnog troška uvodimo generički algoritam, te kao njegov specijalni slučaj, razvijamo metodu \(\epsilon\)-relaksacije.
Abstract (english)
Auction algorithms, based on real auction, work counter to classical network optimization algorithms because in each iteration they don’t necessarily improve the primal or dual cost, although in the end they find an optimal primal solution. They are based on methods of nondifferentiable optimization. Initially, we describe the auction algorithm for classical assignment problem and we deal with various issues such as \(\epsilon\)-scaling, dealing with infeasibility, reverse auction etc.. The reason is that the minimum cost flow problem can be easily transformed to an assignment problem, so these issues are common to all types of observed problems. Therefore, later in the paper, we observe the algorithm adaptation for the max-flow problem, transportation problem, shortest path problem and minimum cost flow problem. For minimum cost flow problem we introduce generic algorithm and develop \(\epsilon\)-relaxation method as a special case of the generic algorithm.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:217:465785
Study programmeTitle: Applied Mathematics
Study programme type: university
Study level: graduate
Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2019-06-19 10:07:19