Egzaktno rješavanje problema cjelobrojnog linearnog programiranja

diplomski rad

• Naslov (engleski): Exact solution of integer linear programming problems
• Autor: Nikolina Križaić
• Mentor: Robert Manger (mentor)
• Član povjerenstva: Robert Manger (predsjednik povjerenstva)
• Član povjerenstva: Eduard Marušić-Paloka (član povjerenstva)
• Član povjerenstva: Matej Mihelčić (član povjerenstva)
• Član povjerenstva: Dijana Ilišević (č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: 2023-11-30, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Cjelobrojno linearno programiranje se bavi problemom optimizacije gdje su funkcija cilja i ograničenja linearni, a neke od varijabli odlučivanja su cjelobrojne. Najpoznatije metode za egzaktno rješavanje ovakvih problema su branch-and-bound odnosno cutting-plane metoda. U ovom radu veći je naglasak na metodi branch-and-bound. U prvom poglavlju upoznali smo se osnovnim pojmovima iz teorije grafova koje su nam potrebne za razumijevanje modela pojedinih problema. U drugom, trećem i četvrtom poglavlju upoznali smo se s poznatim problemima cjelobrojnog linearnog programiranja: problemom naprtnjače, problemom dodjeljivanja te problemom trgovačkog putnika. U petom poglavlju opisali smo branch-and-bound algoritam te smo riješili jednostavan problem naprtnjače tom metodom. U šestom i sedmom poglavlju smo se upoznali s teorije grafovaom te smo implementirali rješenje za problem trgovačkog putnika koristeći Gurobi softver.

Sažetak (engleski)

Integer linear programming deals with optimization problems where the objective function and constraints are linear and some decision variables are integers. The most common exact methods for solving such problems include the branch-and-bound method and the cutting plane method. In this work, there is more emphasis on the branch-and-bound method. In the first chapter, we have introduced some to basic concepts from graph theory that we need to understand the models of certain problems. In the second, third and fourth chapters, we have introduced the well-known integer linear programming problems: the knapsack problem, the assignment problem and the traveling salesman problem. In the fifth chapter, we have described the branch-and-bound algorithm and solved a simple knapsack problem with that method. In the sixth and seventh chapters, we have got acquainted with the Gurobi software and implemented a solution to the traveling salesman problem using the Gurobi software.

• Ključne riječi: branch-and-bound metoda; cutting-plane metoda; teorija grafova; teorija grafova
• Ključne riječi (engleski): branch-and-bound method; cutting plane method; graph theory; Gurobi software
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:597108
• Studijski program: Naziv: Matematička statistika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: sveučilišni magistar matematike (univ. mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2024-02-12 13:01:00