Rješavanje linearnog programa na ugradbenoj računalnoj arhitekturi

master's thesis

• Title (english): Solving a linear program on an embedded computer architecture
• Author: Jakov Petrina Trnski
• Mentor: Mario Vašak (mentor)
• Committee member: Mario Vašak (predsjednik povjerenstva)
• Committee member: Vinko Lešić (član povjerenstva)
• Committee member: Anita Banjac (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2021-02-23, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Electrical Engineering

Abstract

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.

Abstract (english)

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.

• Keywords: linearno programiranje; interior-point metoda; ugradbeni računalni sustavi
• Keywords (english): linear programming; interior-point method; embedded systems
• Language: croatian
• URN:NBN: urn:nbn:hr:168:197088
• Study programme: Title: Electrical Engineering and Information Technology; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka elektrotehnike i informacijske tehnologije (magistar/magistra inženjer/inženjerka elektrotehnike i informacijske tehnologije)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-15 11:03:19