Optimizacija 1

Cilji in predmetno specifične kompetence

Študent spozna pojem optimizacijskega problema, se nauči zapisati dejanske probleme v obliki optimizacijskih problemov in se natančneje seznani z reševanjem linearnih optimizacijskih problemov.

Opis vsebine

• 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.

Temeljna literatura

• 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.

Predvideni študijski dosežki

Predvideni študijski dosežki
Znanje in razumevanje Slušatelj je sposoben z matematičnim mode¬lom dobro opisati različne probleme iz vsak¬danjega življenja. Poudarek je na proble¬mih, ki vodijo do linearnih modelov. Pozna osno¬vne 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.

Pogoji za vključitev v delo oziroma za opravljanje študijskih obveznosti

• opravljen izpit iz predmeta Algebra 1
• opravljen izpit iz vaj je pogoj za pristop k izpitu iz teorije

Metode ocenjevanja in ocenjevalna lestvica

• 2 kolokvija namesto izpita iz vaj, izpit iz vaj, izpit iz teorije
• ocene: 1-5 (negativno), 6-10 (pozitivno) (po Statutu UL)

Metode evalvacije kakovosti

Študentska anketa (univerzitetna in interna), samoevalvacija.

Sestavljalec učnega načrta

prof. dr. Martin Juvan