Optimizacijske metode

2022/2023
Program:
Interdisciplinarni univerzitetni študijski program 1. stopnje Računalništvo in matematika
Letnik:
2 letnik
Semester:
drugi
Vrsta:
obvezni
ECTS:
7
Jezik:
slovenski
Nosilci predmeta:
Ure na teden – 2. semester:
Predavanja
3
Seminar
0
Vaje
3
Laboratorij
0
Vsebina

• Optimizacijske naloge in problemi, primeri, podobne in enakovredne naloge,
• rešljivost, globalni in lokalni ekstremi,
• lokalna optimizacija, konveksnost, reševanje v Rn, sedla, prirejene in dualne naloge,
• Lagrangeova prirejenost, Karush‐Kuhn‐Tuckerjev izrek, numerični postopki, kazenske metode,
• linearno programiranje, metoda simpleksov, dualne naloge,
• diskretne optimizacijske naloge, zahtevnost problemov, pristopi k reševanju diskretnih nalog,
primeri (predavatelj izbere nekatere izmed naslednjih tem: najcenejši razvoz, pretoki po omrežju, prirejanja in pokritja, barvanje grafov, razvrščanje v skupine, ...).

Temeljni literatura in viri

Vašek Chvátal: Linear Programming, W. H. Freeman and Co., New York, 1983
B. H. Korte, J. Vygen: Combinatorial Optimization : Theory and Algorithms, 3. izdaja, Springer, Berlin, 2006.
Stephen Boyd, Lieven Vandenberghe: Convex Optimization, Cambridge University Press, Cambridge, 2004
V. Batagelj: Optimizacijske metode, Zapiski predavanj, Ljubljana.http://vlado.fmf.uni-lj.si/vlado/optim/opt1.pdfhttp://vlado.fmf.uni-lj.si/vlado/optim/lp.pdf
V. Batagelj, M. Kaufman: Naloge iz optimizacijskih metod, Ljubljana.http://vlado.fmf.uni-lj.si/vlado/optim/optnal.pdf
Jiří Matoušek, Bernd Gärtner: Understanding and Using Linear Programming, Springer 2007
M.Minoux: Mathematical programming. Theory and algorithms. Wiley, Chichester, 1986
M.S.Bazaraa, H.D.Sherali, C.M.Shetty: Nonlinear Programming, Theory and Algorithms. Wiley, New York 1993.
C.H.Papadimitriou, K.Steiglitz: Combinatorial optimization: Algorithms and complexity. Prentice‐Hall, Englewood Cliffs, New Jersey 1990

Cilji in kompetence

Podati v poenoteni obliki osnovna znanja o ``zvezni'' in kombinatorični optimizaciji.

Predvideni študijski rezultati

Znanje in razumevanje: Študent pridobi osnovno znanje o zvezni in kombinatorični optimizaciji. Obvlada temeljne optimizacijske postopke in jih zna uporabiti ob pomoči računalnika.
Uporaba: Reševanje optimizacijskih problemov v vsakdanjem življenju.
Refleksija: Pomen ustreznega modeliranja problemov iz uporabe za njihovo učinkovito reševanje.
Prenosljive spretnosti – niso vezane le na en predmet: Sposobnost predstavitve različnih praktičnih problemov v obliki matematičnih optimizacijskih nalog. Veščina uporabe izbranega programskega orodja za reševanje osnovnih optimizacijskih problemov.

Metode poučevanja in učenja

predavanja, vaje, domače naloge, konzultacije

Načini ocenjevanja

Domače naloge ali projekt
Pisni izpit
Ustni izpit
(ocene: 5 (negativno), 6-10 (pozitivno), ob upoštevanju Statuta UL)

Reference nosilca

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]