Tehnike dekompozicije u mrežnoj optimizaciji

master's thesis

• Title (english): Decomposition techniques in network optimization
• Author: Bernarda Jozepović
• Mentor: Marko Vrdoljak (mentor)
• Committee member: Marko Vrdoljak (predsjednik povjerenstva)
• Committee member: Tomislav Berić (član povjerenstva)
• Committee member: Matej Mihelčić (član povjerenstva)
• Committee member: Vjekoslav Kovač (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2022-07-21, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: Lagrangeova relaksacija; Dantzig-Wolfeova dekompozicija; Bendersova dekompozicija
• Keywords (english): Lagrangean relaxation; Dantzig-Wolfe decomposition; Benders decomposition
• Language: croatian
• URN:NBN: urn:nbn:hr:217:962283
• Study programme: Title: Finance and Business Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2022-09-13 10:28:58