OI1 Usmeni

1. Konveksnost skupa, definicije duži, konveksne kombinacije i ekstremne tačke.

-Konveksnost skupa

-R^n prostor

-Definicija duzi

-Definicija poluprave

-Presek konveksnih skupova je konveksan skup

-Konveksne kombinacije

-Ekstremna vrednost skupa

-Dopustiva tacka

-Dopustiva oblast

2. Globalni i lokalni optimum, konveksnost funkcije i optimum konveksne funkcije.

-Konveksna funkcija

-globalni min/maks

-ako je funkcija neprekidna na ogranicenom i zatvorenom skupu s, dostize barem jedan globalni optimum

-lokalni min/maks

-ako je funkcija f konveksna na konveksnom skupu s, njen lokalni optimum je i globalni.

3. Osnovna svojstva opšteg zadatka LP.

1. Ako dopustiva oblast nije prazan skup, onda je konveksni poliedar, postoji bar jedno teme, konacan broj temena jednak m+n nad n

2. Ako postoji optimalno resenje, nalazi se na granici dopustive oblasti, jedinstveno u temenu, visestruko na stranici

3. Resenje problema x* je optimalno ako ne postoji susedno teme u kom je vrednost funkcije bolja

4. Ako je dopustiva oblast ogranicena i neprazna, postoji globalni optimum, a ako je neogranicena postoji samo ako je funkcija cilja ogranicena.

4. Opšti oblik zadatka LP i svođenje na standardni oblik.

-Opsti oblik

-Uslovi za standardni oblik

--bi>0

--ogranicenja tipa =

--funkcija cilja max

--n>m

-Primer standardnog

-Svodjenje na standardni

--max->min

--ogranicenja u = sa s i v

--b negativno->pozitivno mnozenje sa -1

5. Bazna rešenja (dopustiva, susedna, degenerisana).

Ax=b, rang(A)=m<n

-Bazno

-Dopustivo

-Susedno

-Degenerisano

T: X je bazno dopustivo resenje akko se nalazi u temenu dopustive oblasti D standardnog oblika.

6. Geometrijska interpretacija simpleks metode. Veza sa algoritmom lokalnog pretraživanja.

-o simpleksu

-koraci simpleksa

-grafik simpleks vs lokalno pretrazivanje

-tabela razlika

7. Svođenje na kanonski oblik opšteg problema LP i određivanje početnog baznog dopustivog rešenja (metoda velikog M).

-kanonski oblik

-uslovi za kanonski (standardni takodje)

svako ogranicenje ima promenljivu koja:

--jedinstvena za to ogranicenje

--ima koeficijent +1

--ne utice na funkciju cilja

-prebacivanje u kanonski

-pocetno bazno resenje

8. Uloga kanonskog oblika LP u postupku nalaženja optimalnog rešenja simpleks metodom.

-Olaksava nalazenje inicijalnog baznog dopustivog resenja

--Obezbedjuje Ab, det(Ab)/=0, koja je i jedinicna matrica.

--Svaka bazna promenljiva je jednaka slobodnom clanu svog ogranicenja

--Takvo bazno resenje je i dopustivo, jer su svi slobodni clanovi pozitivni

-Standardizuje algoritam

--Pivotovanje

--Kriterijum ulaska u bazu

9. Određivanje novog kanonskog oblika tj. nalaženje boljeg susednog baznog dopustivog rešenja.

-Pretpostavimo da je Xk neoptimalno

-Kriterijum optimalnosti neispunjen

-Ulazi max(cjk), sad u indexu s

-Izlazi min(brk/arsk), sad u indexu r

-Pivotuje se oko arsk.

10. Mogući ishodi simpleks metode: jedinstveno optimalno rešenje i prazna dopustiva oblast (grafička i algebarska interpretacija).

Slika i u simpleksu za oba slucaja

11. Mogući ishodi simpleks metode: višestruko optimalno rešenje i neograničena funkcija cilja (grafička i algebarska interpretacija).

Slika i u simpleksu za oba slucaja

12. Konačnost i računska složenost (definicija) simpleks metode.

Konacnost:

-Simpleks je iterativni algoritam koji iz koraka u korak ide u bolje i bolje resenje, zbog cega je konacan.

-Ako se desi da je bazno dopustivo resenje degenerisano, postoji mogucnost cikliranja

-Cikliranje je stanje u kom se simplex vrti kroz ista temena u krug

-Vremenom su nastala pravila kojima se ovo izbegne

-Blendovo pravilo, u bazu ulazi prva promenljiva u nizu za koju je c_j^k>0, a ne max(c_j^k).

Racunska slozenost:

-Racunska slozenost algoritma je broj operacija neophodan algoritmu da dodje do resenje, u najgorem slucaju.

-Svaki algoritam ima ulazne promenljive.

-Racunska slozenost zavisi od ulaznih promenljivih

-E=c*f(L)

-E je broj operacija, c neka konstanta, f(L) funkcija koja zavisi od ulaza.

-U simpleksu je elementarna operacija pivotiranje.

-Za jednu iteraciju, neophodno je n*m operacija.

-U najgorem slucaju, neophodan broj operacija je (n nad m)

-Maksimalan broj operacije je n*m*(n nad m), sto se takodje moze oznaciti kao O(nm(n nad m))

-Ovo cini simpleks eksponencijalne slozenosti

-U praksi simpleks ima performanse polinomijalne slozenosti zato sto su nastale razne tehnike kojima se optimizuje algoritam, kao slozen kriterijum za odabir ulaska/izlaska u bazu.