Topic outline
General
Obveznosti študentov
- Sprotno delo - domače naloge.
- Pisni izpit iz nalog. Izpit iz nalog se lahko opravlja tudi z dvema kolokvijema, pri čemer so pogoj za pristop h kolokviju pravočasno oddane domače naloge.
- Ustni izpit iz teorije. Pogoj za pristop k izpitu iz teorije je uspešno opravljen izpit iz nalog.
Datumi kolokvijev
- kolokvij: sreda, 6. april 2022, ob 16.00 v 2.01 in 2.05
- kolokvij: sreda, 1. junij 2022, ob 10.00 v 2.01 in 2.05
Datumi izpitov
- izpit: četrtek, 9. junij 2022, ob 10.00 v 2.05
- izpit: torek, 28. junij 2022, ob 10.00 v 2.05
- izpit: ponedeljek, 22. avgust 2022, ob 10.00 v MFP
- This topic
Predavanja
- Meeting ID: 933 2776 6055
- Passcode: 952887
- Povedali smo, kaj so optimizacijski problemi, in si ogledali nekaj primerov. Definirali smo linearne programe in standardno obliko.
- Povedali smo, kaj so konveksne množice, in dokazali nekaj lastnosti.
- Pokazali smo, kako grafično rešujemo linearne programe z dvema spremenljivkama, in kako rešimo linearni program v standardni obliki z nenegativnimi desnimi stranmi s pomočjo simpleksne metode.
- Ogledali smo si še reševanje linearnega programa v standardni obliki s kako negativno desno stranjo s pomočjo dvofazne simpleksne metode.
- Ogledali smo si dualni problem linearnega programa. Dokazali smo šibki izrek o dualnosti in zapisali krepki izrek o dualnosti.
- Dokazali smo krepki izrek o dualnosti in zapisali izrek o dualnem dopolnjevanju.
- Dokazali smo izrek o dualnem dopolnjevanju. Povedali smo, kaj je ekonomski pomen dualnih spremenljivk in kaj je dual splošnega linearnega programa. Začeli smo s problemom razvoza.
- Za ogled je potrebna prijava.
- Nadaljevali smo s problemom razvoza. Motivirali in skicirali smo simpleksno metodo na omrežjih.
- Natančno smo si ogledali simpleksno metodo na omrežjih.
- Natančno smo si ogledali dvofazno simpleksno metodo na omrežjih.
- Preko stohastičnih in permutacijskih matrik smo dokazali Kőnigov izrek o plesnih parih.
- Definirali smo problem razvoza z omejitvami in pokazali simpleksno metodo na omrežjih zanj.
- Začeli smo s problemom maksimalnega pretoka in motivirali Ford-Fulkersonov algoritem.
- Definirali smo prereze in njihove kapacitete. Dokazali smo, da je prostornina vsakega pretoka manjša ali enaka od kapacitete vsakega prereza. Dokazali smo, da je problem maksimalnega pretoka neomejen ali pa je prostornina maksimalnega pretoka enaka kapaciteti minimalnega prereza.
- Opisali smo Ford-Fulkersonov algoritem ter pogledali primer njegove uporabe. Definirali smo prirejanja, pokritja in povečujoče poti ter dokazali Bergeev izrek.
- Pokazali smo madžarsko metodo za iskanje največjega prirejanja na dvodelnem grafu in naredili primer njene uporabe. Omenili smo Edmondsov algoritem.
- Dokazali smo Hallov izrek in si ogledali madžarsko metodo z utežmi.
- Lotili smo se konveksne optimizacije. Definirali smo konveksne množice in konveksno ogrinjačo.
- Definirali smo afine množice in konveksne stožce in si ogledali nekatere njihove lastnosti. Definirali smo dualni stožec ter dokazali Farkasevo lemo.
- Definirali smo konveksne in konkavne funkcije ter si ogledali nekaj osnovnih lastnosti konveksnih funkcij.
- Povedali smo, da je lokalni minimum konveksne funkcije nujno tudi globalni minimum. Dokazali smo kriterij 1. odvoda za konveksne funkcije in začeli z dokazom kriterija 2. odvoda za konveksne funkcije ene spremenljivke.
- Dokončali smo dokaz kriterija 2. odvoda za konveksne funkcije ene spremenljivke. Ponovili smo osnovna dejstva o simetričnih matrikah in kvadratnih formah.
- Dokazali smo še kriterij 2. odvoda za konveksne funkcije in povedali, da lahko strogo konveksna funkcija maksimum doseže le v ekstremni točki. Potem smo se lotili problema vezanih ekstremov z neenačbami (VEN).
- Videli smo, kako lahko poiščemo globalne ekstreme problema vezanih ekstremov z neenačbami s pomočjo Lagrangeeve funkcije.
- Povedali smo Karush-Kuhn-Tuckerjeve pogoje (KKT) in povedali, kdaj so potrebni in kdaj zadostni za to, da je v dani točki globalni minimum. Ogledali smo si primer uporabe pogojev KKT.
- Videli smo, da so KKT pogoji za linearno programiranje ekvivalentni izreku o dualnem dopolnjevanju. Zadnji primer, Fisherjev model trga (FMT), je večji in smo z njim samo začeli.
- Dokazali smo zadostni pogoj za ravnovesnost cen v Fisherjevem modelu trga. Začeli z Eisenberg-Galovim konveksnim programom (EGP) in dokazali, da ima vedno optimalno rešitev.
- Dokazali smo izrek, da sta rešitvi FMT in EGP ekvivalentni.
- Zaključili smo s Fisherjevim modelom trga. Obravnavali smo lokalno optimizacijo. Definirali smo, kaj je relacija sosednosti, kaj je S-lokalni minimum in kaj pomeni, da je relacija natančna. Ogledali smo si nekaj primerov, na primer linearno programiranje, iskanje najcenejšega vpetega drevesa in problem potujočega trgovca.
Vaje