Poopćeni problem dodjeljivanja

Zamislite da ste lopov koji se nalazi u sefu nekog poznatog muzeja. Namjera vam je ukrasti što vrjednije predmete, ali dolazite do problema - na raspolaganju imate malu naprtnjaču. Želite odabrati predmete koji će stati u naprtnjaču, a da im ukupna vrijednost bude što veća. Možete zamisliti i jedan legalan scenarij: imate \(n\) poslova i isto toliko radnika. Svakom radniku trebate platiti da odradi po jedan posao, a svaki od njih ima drugačiju cijenu za pojedini posao. Naravno, cilj vam je dodijeliti poslove tako da vam trošak bude što manji. Poopćeni problem dodjeljivanja je generalizacija ova dva problema. On pretpostavlja da imate \(n\) predmeta i \(m\) naprtnjača, te da vrijednost i težina svakog predmeta ovisi i o naprtnjači u koju ćete ga staviti. Cilj vam je rasporediti sve predmete po naprtnjačama na takav način da ukupna vrijednost bude što veća, a da se ne prekorači kapacitet ni jedne naprtnjače. Ovaj diplomski rad se bavi upravo tim trima problemima. Svaki problem ćemo opisati, analizirati i navesti neke algoritme za njihovo rješavanje. Opisat ćemo i način na koji su problem naprtnjače i linearni problem dodjeljivanja povezani sa poopćenim problemom dodjeljivanja. Na kraju rada ćemo reći nešto više i o implementaciji algoritama za rješavanje ovih problema te navesti neke eksperimentalne rezultate.Imagine yourself in an action movie scene: you are a thief inside a museum vault. You are there to steal as much valuable items as you can, but there is a problem - you only have a small knapsack. You want to choose items that will fit into your knapsack, but will also have the highest possible value. You can imagine another situation: you have \(n\) number of jobs that need to be done by \(n\) workers. For every job, every worker has a price which you need to pay in order for him to get that job done. You need to assign one job to every worker with the objective of minimizing the total cost. Generalized Assignment Problem is a generalization of these two problems. You are given \(n\) number of items and \(m\) number of knapsacks, with the value and size of each item depending on the knapsack you will put it in. Your goal is to maximize the total value by placing each item in one of the knapsacks, making sure none of the knapsacks is overfilled. This master thesis deals with exactly these problems. We will describe and analyze all three problems and give a few algorithms that solve them. We will also describe the connection between Linear Assignment Problem, Knapsack Problem and Generalized Assignment Problem. At the end we will present implementation of some algorithms that are discussed throughout the thesis