Optimizacijske metode

  • Predavanja:
    • Janoš Vidali (janos.vidali@fmf.uni-lj.si), kabinet 1.14
    • torek od 11h do 12h v predavalnici 2.01
    • četrtek od 12h do 14h v predavalnici 2.01
  • Vaje:
    • Timotej Hrga (timotej.hrga@fmf.uni-lj.si), kabinet 5.18
    • torek od 15h do 18h v predavalnici 1.01
    • sreda od 12h do 15h v predavalnici 2.05

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.
  • Izpit iz teorije. Pogoj za pristop k izpitu iz teorije je uspešno opravljen izpit iz nalog.
    • Kot ustni izpit, ali
    • kot pisni izpit, z dodatnim (krajšim) ustnim izpitom za oceno 9 ali 10.

Termini kolokvijev in izpitov

  • Kolokviji:
    • 1. kolokvij: sreda, 8. april 2026 ob 16:15 v 2.01 in 2.05
    • 2. kolokvij: sreda, 27. maj 2026 ob 16:15 v 2.01 in 2.05
  • Pisni izpiti:
    • 1. pisni izpit: četrtek, 11. junij 2026 v 2.05, vaje ob 9:15, teorija ob 11:30
    • 2. pisni izpit: petek, 26. junij 2026 v 2.05, vaje ob 9:15, teorija ob 11:30
    • 3. pisni izpit: četrtek, 20. avgust 2026 v 2.05, vaje ob 9:15, teorija ob 11:30
    • 4. pisni izpit iz teorije: četrtek, 27. avgust 2026 ob 10:15 v 2.01
  • Ustni izpiti: po dogovoru

Optimizacijski problemi

Primer. Od doma do fakultete iščemo pot, ki je

  • najkrajša
  • najhitrejša
  • najcenejša
  • najbolj udobna
  • ...

Optimizacijski problem - definicija

  • Definicija. Optimizacijski problem je trojica , kjer je

    • ... množica dopustnih (angl. feasible) rešitev
    • ... ciljna (kriterijska) funkcija
    • ... tip ekstrema

  • Če velja , je problem nedopusten, sicer pa je dopusten.

Primer 1

  • Dan je sledeči optimizacijski problem.

  • Metoda reševanja: kandidati za maksimum so ničle odvoda in krajišča dopustnega intervala.

  • Pišemo:

    • p.p. ... pri pogojih
    • angl. s.t. (subject to, tudi so that, such that)

Primer 2

  • Dan je sledeči optimizacijski problem.

  • Metoda reševanja: kandidati za minimum so ničle parcialnih odvodov in rob dopustnega območja.

Optimalna rešitev

  • Definicija. Optimalna rešitev je , da velja . Vrednosti pravimo optimalna vrednost.

  • Podobno, če .

  • Pozor! "bolj optimalna rešitev"

Primer 3

Na kmetiji velikosti 50 ha želimo gojiti pšenico, koruzo in krompir. Na voljo imamo 5000 človek-ur dela in 24000 € kapitala ter sledeče podatke

delo (človek-ur/ha) stroški (€/ha) dobiček (€/ha)
pšenica 60 240 400
koruza 80 400 600
krompir 100 320 480

Koliko ha posameznega pridelka naj posadimo, da bo dobiček čim večji?

Primer 3 - zapis

Taki nalogi rečemo linearni program (LP).

Primer 4

Imamo jabolk z masami . Jabolka bi radi razdelili v dve košari tako, da je v vsaki košari jabolk in da sta masi obeh košar čim bliže.

Primer 4 - zapis

Drugače zapisano:

šš

Primer 5

Ana, Barbara, Cvetka in Darja želijo prečkati most. Naenkrat lahko most prečkata le dve od njiju, imajo pa eno samo svetilko. Za prečkanje mostu A, B, C, D potrebujejo 1, 2, 5 oziroma 10 minut - pri skupnem prečkanju seveda potrebujejo toliko časa kot počasnejša od njiju. Kako naj prečkajo most, da bodo čim hitrejše?

Primer 5 - predstavitev

  • Definiramo graf z množico vozlišč - vsako vozlišče predstavlja stanje na eni strani mostu.
  • Vozlišči in sta sosedni, če lahko z enim prečkanjem pridemo od stanja do stanja (tj., , in ali ).
  • Uteži povezav so porabljeni časi.
  • Iščemo najkrajšo pot med in .
  • Rešujemo z Dijkstrovim algoritmom - spoznali ga bomo pri predmetu Operacijske raziskave.

Primer 6

Sestaviti želimo čim hitrejšo štafeto.

prsno hrbtno delfin prosto
1 65 73 63 57
2 67 76 65 58
3 68 72 69 55
4 67 75 70 59
5 71 69 75 57
6 69 71 66 59

Primer 6 - dopustna rešitev

Primer rešitve (ne nujno optimalne!):

  • prsno 3 (68)
  • hrbtno 5 (69)
  • delfin 1 (63)
  • prosto 6 (59)

Primer 7

  • Potujoči trgovec iz Ljubljane želi obiskati London, Pariz, Madrid, Berlin.

    Lj Lo P M B
    Lj / 5 10 5 10
    Lo 5 / 10 1 5
    P 10 10 / 5 5
    M 5 1 5 / 1
    B 10 5 5 1 /

  • Primer poti: Lj - B - P - Lo - M - Lj, cena 10+5+10+1+5 = 31

  • Iščemo najcenejšo pot, torej najcenejši Hamiltonov cikel. To je problem potujočega trgovca - učinkovit algoritem ni znan!

Optimizacijski problemi

Optimizacijski problemi - primeri

  • Nedopustni problemi:

  • Dopustni problemi:

    • Neomejeni problemi

    • Omejeni problemi

Optimizacijski problemi - primeri (2)

  • Omejeni problemi

    • Optimalni problemi

    • Neoptimalni problemi