Optimizacija

2022/2023
Program:
Visokošolski strokovni študijski program 1. stopnje Praktična matematika
Letnik:
3 letnik
Semester:
prvi
Vrsta:
obvezni
ECTS:
7
Jezik:
slovenski
Ure na teden – 1. semester:
Predavanja
3
Seminar
0
Vaje
3
Laboratorij
0
Vsebina

Optimizacijske naloge in problemi, primeri. Lokalna optimizacija.
Linearni programi, standardna oblika in pretvorbe.
Metoda simpleksov, splošni korak, začetna dopustna rešitev, končnost metode, geometrijski opis.
Dualnost pri linearnem programiranju, šibka in krepka dualnost.
Matrične igre.
Problem razvoza. Celoštevilske rešitve.
Problem maksimalnega pretoka. Algoritem Forda in Fulkersona. Izrek o maksimalnem pretoku in minimalnem prerezu.
Prirejanja in pokritja v dvodelnih grafih. Razporejanje opravil in madžarska metoda.
Najkrajše poti v grafih. Dijkstrov algoritem. Floyd-Warshallov algoritem. Uporaba algoritmov za najkrajše poti, na primer kitajski problem poštarja.
Računalniška orodja za reševanje optimizacijskih problemov.

Temeljni literatura in viri

V. Chvátal: Linear Programming, Freeman, New York, 1983.
B. H. Korte, J. Vygen: Combinatorial Optimization : Theory and Algorithms, 3. izdaja, Springer, Berlin, 2006.
R. J. Vanderbei: Linear Programming : Foundations and Extensions, 2. izdaja, Kluwer, Boston, 2001.

Cilji in kompetence

Študentje bodo spoznali pojem optimizacijskega problema, se naučili zapisati probleme iz prakse v obliki optimizacijskih problemov in se natančneje seznanili z reševanjem linearnih optimizacijskih problemov.

Predvideni študijski rezultati

Znanje in razumevanje: Slušatelj je sposoben z matematičnim modelom dobro opisati različne probleme iz vsakdanjega življenja. Poudarek je na problemih, ki vodijo do linearnih modelov. Pozna osnovne prijeme za učinkovito reševanje dobljenih optimizacijskih problemov.
Uporaba:
Reševanje optimizacijskih problemov iz vsakdanjega življenja.
Refleksija:
Pomen predstavitve praktičnih problemov v formalizirani obliki za njihovo učinkovito in pravilno reševanje.
Prenosljive spretnosti – niso vezane le na en predmet:
Modeliranje nalog iz vsakdanjega življenja v obliki matematičnih optimizacijskih nalog, zmožnost razločevanja med računsko obvladljivimi in neobvladljivimi problemi.

Metode poučevanja in učenja

predavanja, vaje, domače naloge, konzultacije

Načini ocenjevanja

Domače naloge, izpit iz vaj (2 kolokvija ali pisni izpit)
Izpit iz teorije
Študentje dobijo dve oceni: eno iz vaj (pisnega izpita in domačih nalog), drugo iz teorije. Opravljen izpit iz vaj je pogoj za pristop k izpitu iz teorije.
(ocene: 5 (negativno), 6-10 (pozitivno), ob upoštevanju Statuta UL)

Reference nosilca

Sergio Cabello:
CABELLO, Sergio, DÍAZ-BÁÑEZ, José Miguel, PÉREZ LANTERO, Pablo. Covering a bichromatic point set with two disjoint monochromatic disks. Computational geometry, ISSN 0925-7721. [Print ed.], 2013, vol. 46, iss. 3, str. 203-212. [COBISS-SI-ID 16326233]
CABELLO, Sergio, GIANNOPOULOS, Panos, KNAUER, Christian, MARX, Dániel, ROTE, Günter. Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension. ACM transactions on algorithms, ISSN 1549-6325, 2011, vol. 7, no. 4, article 43 (27 str.). [COBISS-SI-ID 16028761]
CABELLO, Sergio, ROTE, Günter. Obnoxious centers in graphs. SIAM journal on discrete mathematics, ISSN 0895-4801, 2010, vol. 24, no. 4, str. 1713-1730. [COBISS-SI-ID 15762265]
Emil Žagar:
JAKLIČ, Gašper, KANDUČ, Tadej, PRAPROTNIK, Selena, ŽAGAR, Emil. Energy minimizing mountain ascent. Journal of optimization theory and applications, ISSN 0022-3239, 2012, vol. 155, is. 2, str. 680-693. ,. [COBISS-SI-ID 4382935]
JAKLIČ, Gašper, ŽAGAR, Emil. Curvature variation minimizing cubic Hermite interpolants. Applied mathematics and computation, ISSN 0096-3003. [Print ed.], 2011, vol. 218, iss. 7, str. 3918-3924. [COBISS-SI-ID 16049241]
JAKLIČ, Gašper, ŽAGAR, Emil. Planar cubic G [sup] 1 interpolatory splines with small strain energy. Journal of Computational and Applied Mathematics, ISSN 0377-0427. [Print ed.], 2011, vol. 235, iss. 8, str. 2758-2765. [COBISS-SI-ID 15770969]
Arjana Žitnik:
MILANIČ, Martin, PISANSKI, Tomaž, ŽITNIK, Arjana. Dilation coefficient, plane-width, and resolution coefficient of graphs. Monatshefte für Mathematik, ISSN 0026-9255, 2013, vol. 170, no. 2, str. 179-193. [COBISS-SI-ID 1024499540]
PISANSKI, Tomaž, ŽITNIK, Arjana. Representing graphs and maps. V: BEINEKE, Lowell W. (ur.), WILSON, Robin J. (ur.). Topics in topological graph theory, (Encyclopedia of mathematics and its applications, ISSN 0953-4806, 128). Cambridge [etc.]: Cambridge University Press, cop. 2009, str. 151-180. [COBISS-SI-ID 15227481]
ŽITNIK, Arjana. Series parallel extensions of plane graphs to dual-eulerian graphs. Discrete Mathematics, ISSN 0012-365X. [Print ed.], 2007, vol. 307, iss. 3-5, str. 633-640. [COBISS-SI-ID 14183769]
Sandi Klavžar:
KLAVŽAR, Sandi, RAHBARNIA, Freydoon, TAVAKOLI, Mostafa. Some binary products and integer linear programming for k-metric dimension of graphs. Applied mathematics and computation. [Print ed.]. Nov. 2021, vol. 409, art. 126420 (7 str.). [COBISS-SI-ID 69333507]
HOLUB, Přemysl, JAKOVAC, Marko, KLAVŽAR, Sandi. S-packing chromatic vertex-critical graphs. Discrete applied mathematics. [Print ed.]. Oct. 2020, vol. 285, str. 119-127. [COBISS-SI-ID 19477507]
DEUTSCH, Emeric, KLAVŽAR, Sandi. M-polynomial revisited: Bethe cacti and an extension of Gutman's approach. Journal of Applied Mathematics and Computing. International Journal. June 2019, vol. 60, iss. 1-2, str. 253-264. [COBISS-SI-ID 18626905]
HINZ, Andreas M., KLAVŽAR, Sandi, PETR, Ciril. The Tower of Hanoi - Myths and Maths. 2nd ed. Cham: Birkhäuser, cop. 2018. XVIII, 458 str. [COBISS-SI-ID 18363737]
KLAVŽAR, Sandi, MANUEL, Paul. Strong geodetic problem in grid like architectures. Bulletin of the Malaysian Mathematical Sciences Society. July 2018, vol. 41, iss. 3, str. 1671-1680. [COBISS-SI-ID 18387033]
KLAVŽAR, Sandi, MA, Meijie. Average distance, surface area, and other structural properties of exchanged hypercubes. The journal of supercomputing. 2014, vol. 69, no. 1, str. 306-317. [COBISS-SI-ID 17064793]