Rješavanje linearnog programa na ugradbenoj računalnoj arhitekturi

diplomski rad

• Naslov (engleski): Solving a linear program on an embedded computer architecture
• Autor: Jakov Petrina Trnski
• Mentor: Mario Vašak (mentor)
• Član povjerenstva: Mario Vašak (predsjednik povjerenstva)
• Član povjerenstva: Vinko Lešić (član povjerenstva)
• Član povjerenstva: Anita Banjac (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2021-02-23, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Elektrotehnika

Sažetak

Linearno programiranje je široko poznata metoda za rješavanje matematičkih problema određenih linearnom funkcijom cilja, a na koju se postavljaju linearni uvjeti jednakosti i nejednakosti. Premda postoje efikasni algoritmi za rješavanje linearnih programa na sustavima opće namjene, implementacija takvih algoritama na ugradbenim računalnim sustavima predstavlja značajan izazov. U ovom radu linearno programiranje uvodi se u kontekstu matematičke optimizacije. Potom je postavljena teoretska podloga za rješavanje linearnih programa koristeći interior-point metode. Sukladno razmatranjima o matematičkoj optimizaciji na ugradbenim računalnim sustavima, opisan je Mehrotra predictor-corrector algoritam. Navedeni algoritam implementiran je u MATLAB-u, te koristeći C++ programski jezik. Provjerena je točnost implementacije algoritma uz detaljnu analizu izvršavanja na GNU/Linux operacijskom sustavu. U konačnici, razmotrena su daljna unaprijeđenja implementacije.

Sažetak (engleski)

Linear programming is a well-known method for solving mathematical problems represented by a linear objective function which is subject to linear equality and linear inequality contraints. Although many efficient algorithms exist for solving linear programs on general purpose systems, implementation of such algorithms on embedded systems is a significant challenge. In this paper linear programming is introduced in the context of mathematical optimization. Theoretical background for solving linear programs is presented for interior-point methods. A description of the Mehrotra predictor-corrector algorithm is given, following considerations for mathematical optimization on embedded systems. The algorithm is implemented in MATLAB, as well as using the C++ programming language. The implementation of the algorithm is verified and its performance on GNU/Linux operating system analyzed in detail. Lastly, further improvements to the implementation are considered.

• Ključne riječi: linearno programiranje; interior-point metoda; ugradbeni računalni sustavi
• Ključne riječi (engleski): linear programming; interior-point method; embedded systems
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:197088
• Studijski program: Naziv: Elektrotehnika i informacijska tehnologija; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka elektrotehnike i informacijske tehnologije (mag. ing. el. techn. inf.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-15 11:03:19