Tehnike dekompozicije u mrežnoj optimizaciji

diplomski rad

• Naslov (engleski): Decomposition techniques in network optimization
• Autor: Bernarda Jozepović
• Mentor: Marko Vrdoljak (mentor)
• Član povjerenstva: Marko Vrdoljak (predsjednik povjerenstva)
• Član povjerenstva: Tomislav Berić (član povjerenstva)
• Član povjerenstva: Matej Mihelčić (član povjerenstva)
• Član povjerenstva: Vjekoslav Kovač (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2022-07-21, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Cilj ovog diplomskog rada bio je obraditi nekoliko tehnika dekompozicije u mrežnoj optimizaciji poput Lagrangeove relaksacije, Dantzig-Wolfeove dekompozicije i Bendersove dekompozicije. Te tehnike svode zadaće koje ne možemo rješavati klasičnim algoritmima na klasicˇne zadaće. Nakon uvođenja nelinearne zadaće sa skoro mrežnom strukturom pokazali smo par primjera problema takvih zadaća koji se često koriste u praksi. Lagrangeova relaksacija jedna je od najčešće korištenih tehnika za rješavanje u cijelom matematičkom programiranju koja nam omogućava da pristupimo teškom optimizacijskom problemu pomo ću niza jednostavnijih problema. Dantzig-Wolfeova dekompozicija se koristi kada problem linearnog programiranja ima posebnu strukturu za generiranje podproblema koji se mogu učinkovito rješiti. Bendersova dekompozicija je široko korištena egzaktna metoda rješenja za stohastičke programe, koja se sve više primjenjuje za rješavanje problema planiranja transporta i logistike. Na kraju smo primjenili Lagrangeovu relaksaciju na nekapacitirani problem lokacije objekta s fiksnim troškom i Bendersovu dekompoziciju na kapacitirani problem lokacije objekta s fiksnim troškom.

Sažetak (engleski)

The aim of this master thesis has been to present several network optimization techniques with an emphasis on Lagrangean relaxation, Dantzig-Wolfe decomposition and Benders decomposition. These techniques reduce problems that we cannot solve using classical algorithms to classical problems. We have introduced a non-linear problem with an almost network structure and we have provided a few examples of such problems that are often used in practice. Lagrangean relaxation is one of the most commonly used solving techniques in mathematical programming which allows us to approach a difficult optimization problem with a simpler and more relaxed problem. Dantzig-Wolfe decomposition can be used when a linear optimization problem has special structure to generate subproblems that can be solved efficiently. Benders decomposition is a broadly used exact solution method for stochastic programs and it has been increasingly applied to transportation and logistics planning problems under uncertainty. Finally, we have applied Lagrange’s relaxation to the uncapacitated fixed charge facility location problems and Benders’ decomposition to the capacitated fixed charge facility location problems.

• Ključne riječi: Lagrangeova relaksacija; Dantzig-Wolfeova dekompozicija; Bendersova dekompozicija
• Ključne riječi (engleski): Lagrangean relaxation; Dantzig-Wolfe decomposition; Benders decomposition
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:962283
• Studijski program: Naziv: Financijska i poslovna matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2022-09-13 10:28:58