Analiza algoritmov linearnega programiranja

LAMPREHT, ROBERT (author), Dobravec, Tomaž (mentor)

Uporaba linearnega programiranja je danes zelo razširjena saj se lahko nanj prevedejo številni problemi. Nekatere od pomembnejših industrijskih panog, ki uporabljajo optimizacijske motode so: logistika, telekomunikacija in predelovalne dejavnosti. Cilj linearnega programiranja je optimizacija kompleksnih problemov z namenskimi algoritmi. V diplomski nalogi želimo predstaviti različne tipe algoritmov za optimizacijo ter njihovo delovanje. Osredotočili se bomo predvsem na dva različni metodi: metodo simpleksov in metodo notranje točke. Za testiranje bomo standardne optimizacijeske testne množice s katerimi bomo prišli do rezultatov. Dobljene rezultate bomo analizirali in poskušali utemeljiti kateri način optimizacijskega postopka je učinkovitejši.

• Language: Slovenian
• Keywords: linearno programiranje, optimizacijske metode in algoritmi, metoda simpleksov, metoda notranjih točk
• Work type: Bachelor thesis/paper
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2014
• PID: 20.500.12556/RUL-29629
• Publication date in RUL: 30.09.2014

Secondary language

• Language: English
• Title: Analysis of the linear programming algorithms

Abstract

The use of linearprogramming today is very wide spread because of useful optimizations problems that can solve. Some of the more important industries that are using optimization methods are: logistics, telecommunications and manufacturing. The objective of linear programming is optimization of complex problems with algorithms. In out thesis we want to introduce different types of optimization algorithms and how they work. Our main focus will be on simplex method and interior-point method. For testing purposes we will use standardized test set for optimization problems. With given results we will try to decide which optimization method is better suited for the job.

• Keywords: linear programming, optimization methods and algorithms, simplex method, interior-point method