Vrste optimizacijskih problemov. 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.
Optimizacija 1
2022/2023
Program:
Univerzitetni študijski program 1. stopnje Matematika
Letnik:
3 letnik
Semester:
prvi
Vrsta:
izbirni
Skupina:
B2
ECTS:
5
Jezik:
slovenski
Nosilec predmeta:
Izvajalec (kontaktna oseba):
Ure na teden – 1. semester:
Predavanja
2
Seminar
0
Vaje
2
Laboratorij
0
Vsebina
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
Študent spozna pojem optimizacijskega problema, se nauči zapisati probleme iz prakse v obliki optimizacijskih problemov in se natančneje seznani 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
2 kolokvija namesto izpita iz vaj / izpit iz vaj
izpit iz teorije
(ocene: 5 (negativno), 6-10 (pozitivno), ob upoštevanju Statuta UL)
Reference nosilca
Riste Škrekovski:
GREGOR, Petr, ŠKREKOVSKI, Riste. Long cycles in hypercubes with distant faulty vertices. Discrete mathematics and theoretical computer science, ISSN 1365-8050, 2009, vol. 11, no. 1, str. 185-198. [COBISS-SI-ID 15521113]
ŠKREKOVSKI, Riste. A Grötzsch-type theorem for list colourings with impropriety one. Combinatorics, probability & computing, ISSN 0963-5483, 1999, let. 8, št. 5, str. 493-507. [COBISS-SI-ID 9275225]
DIMITROV, Darko, DVOŘÁK, Tomáš, GREGOR, Petr, ŠKREKOVSKI, Riste. Gray codes avoiding matchings. Discrete mathematics and theoretical computer science, ISSN 1365-8050, 2009, vol. 11, no. 2, str. 123-148. [COBISS-SI-ID 15521369]
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]
