OPERACIONA
ISTRAŽIVANJA
*SKRIPTA ZA ZAVRŠNI 2012*
1. Koji ekonomski problemi mogu biti predmet modeliranja koriscenjem metoda
linearnog programiranja?
Veliki broj privrednih aktivnosti se ostvaruje u uslovima ograničenog iznosa resursa,
koji se na različite načine mogu koristiti za ostvarivanje unapred postavljenog cilja. Iz
niza mogućih načina (programa) korišćenja raspoloživih resursa ekonomski subjekti su
veoma zainteresovani da odaberu onaj najpovoljniji, onaj za koji će se ostvariti najveća
moguća efikasnost ukupnih aktivnosti. Zbog toga optimizacija ekonomskih aktivnosti
zauzima centralno mesto u okviru ekonomske analize i matematičkog modeliranja
ekonomskih problema. Jedan od matematičkih metoda optimizacije, koji je tokom ovog
veka doživeo punu afirmaciju, teorijsku razradu i široku primenu jeste model linearnog
programiranja.
Linearno programiranje predstavlja model koji se veoma uspjesno koristi za resavanje
velikog broja problema na nivou preduzeca. Tu spadaju:
a) Proizvodno planiranje - U uslovima ograničenog iznosa resursa proizvodno
preduzeće može proizvoditi različite količine proizvoda iz sopstvenog
asortimana. U namjeri da maksimizira ukupan rezultat svog poslovanja, koji je
najčešće izražen visinom ostvarenog profita, preduzeće je veoma zainteresovano
da iskoristi resurse sa kojima u određenom periodu raspolaže na najbolji mogući
(optimalan) način.S toga je za jedno preuzece veoma vazna uloga linearnog
programiranja u kreiranju optimalnog programa proizvodnje koji omogucava
sintezu raspolozivih resursa i pozitivnog poslovnog rezultata.
b) Planiranje investicija – Problem planiranja investicija javlja se prije svega na
podrucju finansijskih institucija, banaka, investicionih fondova kao i raznih
osiguravajucih kompanija. U ovom slucaju polazi se od pretpostavke o
ogranicenosti investicionih sredstava. Uloga linearnog programiranja zasniva se
na kreiranju optimalnog nivoa ulaganja u pojedine hartije od vrijednosti.
c) Planiranje transporta robe – Cilj svakog uspjesnog preduzeca jeste ne samo da
ostvari maksimalan profit vec i da trosak poslovanja svede na minimum. U tom
smislu trensport robe je veoma vazan. Naime, u uslovima teritorijalne
razdvojenosti potrosaca i proizvodjaca transport robe izaziva znacajan trosak
distribucije i prevoza. Metodom linearnog programiranja nastoji se odrediti
optimalan vid transporta koji ce omoguciti minimizaciju troskova. Uloga
linearnog programiranja u resavanju ovog problema je dvojaka jer ne samo da
doprinosi ostvarenju osnovnog cilja preduzeca vec putem smanjenja troskova
transporta indirektno utice i na smanjenje cijene proizvoda pa na taj nacin
zadovoljava i potrebe potrosaca.
d) Optimalno rasporedjivanje kadrova – Optimalno rasporejivanje kadrova odnosi
se na odredjivanje optimalnog rasporeda izvrsilaca za obavljanje razlicitih
poslova. Optimalan raspored podrazumijeva takav raspored koji ce omoguciti
maksimalnu efikasnost u radu. Pri tome efikasnost moze biti usmjerena na
minimizaciju troskova, minimizaciju radnog vremena ili maksimizaciju profita.
Optimalan raspored omogucava se posebnim vidom linearnog programiranja –
modelom asignacije, odnosno rasporedjivanja.
karakteristican za ovu proizvodnju. Shodno tome, druga faza u kvantitativnoj analizi
jeste definisanje modela. U ovoj fazi glavnu ulogu imaju strucnjaci za matematicko i
statisticko strukturiranje modela. U njoj se definise cilj i to u vidu neke funkcije (npr.
maksimiziranje profita) a matematicki se moraju izraziti i sva ogranjicenja koja postoje u
preduzecu. Treca faza predstavlja veoma kompleksan i znacajan posao pripreme
podataka, u okviru koga se moraju obezbijediti svi podaci neophodni za resavanje
definisanog modela. Dakle, neophodno je kreirati informacionu osnovu. Medjutim,
stalne promjene u poslovanju zahtjevaju da prikupljanje podataka bude permanentan
proces koji ce omoguciti vremenski uspjesno koriscenje dfinisanog modela. Nakon
prikupljanja neophodnih podataka prelazi se u fazu resavanja modela . U ovoj fazi vrsi
se verifikacija rethodnih faza kvantitativne analize pri cemu se prevashodno ocjenjuje
validnost modela i njegova upotrebljivost za konkretne potrebe. Ukoiko resavanjem
konkretnog modela dobijemo moguca resenja koja zadovoljavaju ograničavajuće uslove
i matematički izražen cilj realizacije konkretne odluke, onda takva rešenja možemo
smatrati optimalnim i koristiti ih kao povoljnu alternativu poslovne odluke. U
suprotnom, moramo se vratiti na prethodne faze i izvrsiti prilagodjavanje modela. U
poslednjoj fazi dobijena resenja koriste se za donosenje optimalnih poslovnih odluka, u
procesu poslovnog odlucivanja.
3. Objasniti opsti model matematickog programiranja.
Matematicko programiranje je oblast matematike ciji je predmet razmatranja teorijski i
numerick postupak odredjivanja ekstremne vrijednosti funkcija vise promenljivih, u
kojima postoje ogranicenja mogucih vrijednosti promjenljivih.
Matematicko programiranje moze biti:
a) Linearno
b) Nelinearno
Opšti oblik modela matematičkog programiranja možemo predstaviti u obliku zahteva
za određivanjem vrednosti promenljivih X
1
, X
2
,.....X
n
,koje zadovoljavaju m nejednačina
i jednačina oblika:
g
i
(X
1
, X
2
,.....X
n
) {≤, =, ≥} b
i
i= 1,....,m
I za koje se ostvaruje maksimalna ili minimalna vrijednost funkcije:
Z = f (X
1
, X
2
,.....X
n
)
Uslove nazivamo sistemom ograničenja, dok funkcija predstavlja funkciju cilja modela
matematičkog programiranja. U ovako predstavljenom modelu pretpostavljamo da su
funkcije gi i f poznate, dok vrednosti bi predstavljaju unapred zadata ograničenja. U
svakom od ograničenja pojavljuje se ili jednačina ili jedan od dva oblika nejednačina.
Ukoliko su u sistemu ograničenja svi uslovi predstavljeni u vidu jednačina, takav oblik
problema predstavlja klasičan problem optimizacije i ne predstavlja posebno
interesantan slučaj sa aspektra rešavanja zadataka matematičkog programiranja.
Ukoliko sistem ograničenja i odgovarajuću funkciju cilja predstavimo u razvijenom
obliku, model matematickog programiranja je:
(max)Z= f( x
1
,x
2
,...,x
n
)
g
1
(x)=g
1
(x
1
,x
2
,...,x
n
)≤b
1
g
2
(x)=g
2
(x
1
,x
2
,...,x
n
)≤b
2
.........
g
m
(x)=g
m
(x
1
,x
2
,...,x
n
)≤b
m
Sve vrijednosti promjenjivih x=(x
1
,x
2
,...,x
n
) za koje su zadovoljene sve nejednacine
sistema ogranicenja obrazuju tzv. Skup dopustivih ili mogucih rjesenja modela.
Cilj rjesavanja zadatka matematickog programiranja jeste određivanje one kombinacije
vrijednosti promjenjivih iz skupa mogucih rjesenja za koje funkcija cilja ostvaruje
ekstremnu vrijednost. Takvo rjesenje koje obiljezavamo sa x*=(x
1
,x
2
,...,x
n
) predstavlja
optimalno rjesenje zadatka matematickog programiranja.
Ukoliko je u modelu matematickog programiranja makar jedna funkcija gi ili f
nelinearna, takav oblik modela linearnog programiranja predstavlja nelinearno
programiranje. Suprotno ukoliko su sve funkcije sistema ogranicenja i funkcija cilja
modela linearne (i ukoliko predpostavimo da su promjenjive nenegativne velicine),
takav oblik modela predstavlja model linearnog programiranja.
4. Objasniti osnovne pretpostavke modela linearnog programiranja.
Svaki model linearnog programiranja karakterisu odredjene pretpostavke koje se
odnose Xna svaki od njih i to:
a) Linearnost
b) Izvjesnost
c) Djeljivost
d) Nenegativnost
Linearnost
Pretpostavka linearnosti podrazumeva postojanje linearnih zavisnosti između
promenljivih u zadatku linearnog programiranja. Kao posledica linearnosti u modelu
linearnog programiranja zadovoljene su takođe dve osnovne pretpostavke i to:
proporcionalnost i aditivnost.
Standardni problem maksimuma predstavlja takav oblik modela linearnog
programiranja u kome se postavlja zahtjev za određivanjem
maksimalne vrijednosti
unaprijed poznate linearne funkcije (funkcije cilja), pod uslovima koji su predstavljeni
sistemom nejednačina sa znakom ≤.
Ovakav oblik modela linearnog programiranja definiše se u uslovima postojanja
ograničenih resursa koje treba na najracionalniji način utrošiti radi ostvarivanja
maksimalnih ekonomskih efekata.
Zadatak standardnog problema maximuma predstavlja se na sljedeći način:
(max)Z= C
1
X
1
+ C
2
X
2
+...+ CpXp
a
11X1
+ a
12
x
2 +... +
a
1p
x
p
≤ b
1
a
21
x
1
+a
22
x
2
+...+a
2p
x
p
≤ b
2
..............................................
a
m1
x
1
+a
m2
x
2
+...+a
mp
x
p
≤ b
m
x
1
,x
2
,....,x
p
≥ 0
Svaki problem LP mora da sadrži:
1.funkciju cilja
2.sistem ograničenja
3.uslov nenegativnosti
Funkcija cilja
izražava osnovni cilj koji se unaprijed definiše i radi koga se formuliše i
rešava odgovarajući model linearnog programiranja(maksimizacija ukupnog
profita,maksimizacija deviznih efekata,maksimalni stepen zaposlenosti i sl.). Pri tome
radi ostvarivanja cilja predstavljenog funkcijom z u problemu postoji p djelatnosti(u
najširem smislu) koje su predstavljene promjenjivima x
1
,x
2
,...,x
p
čiji su pojedinačni efekti
izraženi parametrima c
1
,c
2
,...,c
p
(max)Z= C
1
X1+ C
2
X
2
+...+ CpXp
Sistem ograničenja
izražava
iznos
i
način
korišćenja ograničenih resursa.
Iznos resursa
je izražen slobodnim članovima sistema ograničenja:
b
1
,b
2
...,b
m
.
Način korišćenja
resursa izražen je koeficijentima a
ij
(i=1,...,m; j=1,...,p)
Uslov nenegativnosti
predstavlja obavezan elemenat modela. On osim metodoloških
razloga on mora biti zadovoljen jer nijedna djelatnost ne može biti negativna.
x
1
,x
2
,....,x
p
≥0
Svi elementi modela izuzev promjenjivih x
1
,x
2
,....,x
p
unaprijed su poznati što znači da su
koeficijenti u funkciji cilja (c
j
), koeficijenti u sistemu ograničenja (a
ij
) i slobodni članovi
sistema ograničenja(b
i
) parametri modela.
6. Zašto se u model LP uvode dodatne promenljive i koje je njihovo ekonomsko
značenje?
U cilju rješenja problema linearnog programiranja, sistem nejednačina koji sačinjava
sistem ograničenja transformišemo u sistem jednačina. Dodatne promjenjive uvodimo u
svaku nejednačinu da bismo izjednačili lijevu i desnu stranu, pa je s toga njihova
vrijednost jednaka razlici između lijeve i desne strane. Dodatne promjenjive imaju svoje
metodološko i ekonomsko značenje. Ekonomsko značenje odnosi se na to da pozitivne
vrijednosti dodatnih promjenjivih pokazuju iznos neiskorišćenih resursa u nekom od
rješenja. Tako, vrijednosti dodatnih promjenjivih iz optimalnog rješenja pokazuju koliko
resursa ostaje neiskorišćeno u situaciji kada su vrijednosti realnih promjenjivih
optimalne, tj. kada funkcija cilja ostvaruje svoju maksimalnu vrijednost. Dodatne
promjenjive uvode se i u funkciju cilja sa nultim vrijednostima koeficijenata.
7. Koje su osnovne karakteristike skupa mogućih rješenja?
Sve vrijednosti promjenjivih za koje su zadovoljene nejednačine, (jednačine) sistema
ograničenja predstavljaju moguća rješenja odnosno obrazuju skup mogućih rješenja.
Skup m.r obrazovan je od tačaka koje zadovoljavaju sve nejednačine(jednačine) sistema
ograničenja, odnosno predstavlja presjek skupova tačaka za koje su zadovoljene
pojedine nejednačine. Iz linearnog karaktera ograničavajućih uslova proizilazi da tačke
koje zadovoljavaju pojedine nejednačine obrazuju
konveksan
skup tačaka.Dakle, važna
osobina skupa mogućih rješenja jeste
konveksnost.
On je takođe
zatvoren skup,
a moze
biti i prazan skup u slucaju kada su postavljeni uslovi kontradiktorni, odnosno kada ne
postoji ni jedna tacka x= (x1,x2,...,xn) za koju su zadovoljeni svi uslovi zadatka.
8. Dokazati da je skup mogućih rješenja konveksan skup.
Da bi se dokazalo tvrđenje teoreme, potrebno je pokazati
da konveksna kombinacija svaka
dva moguća rješenja takođe predstavlja moguće rješenje.
Neka su tačke x'=(x
1',X2',...,Xn'
) i x"=(
X1 ",X2 ",...,Xn"
) moguća rješenja problema, na osnovu čega
je
Ax'= b i Ax"=b
Optimalno rešenje problema maksimuma nalazi se u jednoj ekstremnoj tacki
(najudaljenijoj od koordinatnog pocetka) konveksnog, ogranicenog i zatvorenog skupa
mogucih rešenja. Slicno, samo uz inverzan kriterijum, predstavljali smo uslov za
optimalnost rešenja problema minimuma. To je jedinstveno optimalno resenje, gdje
postoji samo jedna tacka u SMR koja zadovoljava sve uslove i u kojoj je vrijednost I SK
za nebazicne promjenljive <0, u slucaju problema maximuma. Medutim, u nekim
slucajevima može se dogoditi da izracunato optimalno rešenje zadatka linearnog
programiranja nije jedinstveno, odnosno da postoji višestruko optimalno rešenje.
Ukoliko u okviru nekog moguceg bazicnog resenja postoji makar jedna razlika prvog
simpleks kriterijuma (C
j
-Z
j
)
= 0 za prethodnu nebazicnu promenjivu, dok su vrednosti
ovih razlika za ostale nebazicne promenljive negativne, izracunato optimalno rešenje
nije jedinstveno. Uvodenjem u bazu promenljive xj u cilju odredivanja novog rešenja, i
iskljucivanjem neke od prethodno bazicnih promenljivih na osnovu drugog simpleks
kriterijuma, dobili bi takode optimalno rešenje za koje funkcija cilja ima istu vrijednost
kao i u slucaju prethodnog rešenja. Usled osobina skupa mogucih rešenja, postojanje
dva optimalna rešenja ima za posledicu da sve konveksne kombinacije ova dva rešenja
takode predstavljaju optimalna rešenja, zbog cega kažemo da takav zadatak ima
višestruko (beskonacno mnogo) optimalno rešenje. Geometrijski, slucaj postojanja
višestrukog optimalnog rešenja se javlja kada su koeficijenti pravca prave koja
reprezentuje neko od ogranicenja i koeficijent pravca prave funkcije cilja jednaki.
10. Dokazati da se optimalno resenje zadataka standardnog problema maximum
nalazi u jednoj od extremnih tacaka skupa mogucih resenja.
Optimalno rešenje zadatka linearnog programiranja nalazi se u ekstremnoj tacki
konveksnog skupa mogucih rešenja.
Dokaz
Kako je skup mogucih rešenja konveksan, ogranicen skup postoji konacan broj
(pretpostavimo k ) ekstremnih tacaka koje cemo oznaciti sa
x
1
,x
2
,….,x
k
.
Neka je x
*
tacka
za koju funkcija cilja ostvaruje maksimum, odnosno za koju imamo da je
z (x
*
) ≥ z (x),
za
svako moguce rešenje x . Ako je x
*
ekstremna tacka konveksnog skupa mogucih rešenja,
teorema je dokazana.
Pretpostavimo sada suprotno, tj. da x
*
nije ekstremna tacka skupa mogucih rešenja.
Tada tacku x
*
možemo izraziti kao konveksnu kombinaciju skupa ekstremnih tacaka ,
tj.
x
* =
λ
1
x
1
+ λ
2
x
2
+ … + λ
k
x
k
gdje je
λ
i
≥0 (i = 1,…,k) i
=1.
Kako je funkcija Z linearna, mozemo pisati :
z (x
*
) = z (λ
1
x
1
+ λ
2
x
2
+ … + λ
k
x
k
) = λ
1
z(x
1
) + λ
2
z(x
2
) .
Ukoliko sada u poslednjoj jednacini, od k mogucih rešenja predstavljenih ekstremnim
tackama moguceg skupa izaberemo tacku za koju funkcija z ostvaruje maksimalnu
vrijednost, na primer x
k
tada mozemo pisati :
λ
1
z(x
k
) + λ
2
z(x
k
) +… + λ
k
z(x
k
) ≥ λ
1
z(x
1
) + λ
2
z(x
2
) + … + + λ
k
z(x
k
) = z (x
*
)
.
Obzirom da su koeficijenti λ
i
≥0 i =1 dobijamo
λ
1
z (x
k
) + λ
2
z(x
k
) +… + λ
k
z(x
k
) = (λ
1 +
λ
2
+…+ λ
k
) z (x
k
) = z (x
k
)
odnosno
z (x
k
) ≥ z (x
*
),
sto je i trebalo dokazati. Na taj nacin pokazano je da tacka x predstavlja optimalno
resenje zadatka standardnog problema maximum jedino ukoliko je
x
*
= x
k
odnosno da
se maximalna vrijednost funkcije Z ostvaruje u extremnoj tacki skupa mogucih resenja.
11. Kada se primjenjuje graficki metod odredjivanja resenja u modelu LP i koji je
postupak njegove primjene?
Najjednostavniji nacin odredivanja rešenja u zadatku linearnog programiranja
predstavlja graficki metod. Medutim, i pored izrazite jednostavnosti i preglednosti,
mogucnosti korišcenja ovog metoda u rešavanju prakticnih problema linearnog
programiranja su veoma ogranicene. Naime, graficki metod resavanja zadatka
linearnog programiranja moze se primjeniti samo u slucaju kada u zadatku postoje
dvije realne promjenljive. Zbog toga, razmatranje grafickog metoda ima prevashodno
karakter predstavljanja skupa mogucih resenja i postupaka trazenja optimalnog resenja,
kao i ukazivanja na osnovni karakter postupka odredjivanja resenja koriscenjem
simplex metoda.
Postupak njegove primjene je sledeci :
1. Formulisanje problema u obliku zadatka linearnog programiranja;
2. Graficko predstavljanje pravih koje reprezentuju nejednacine sistema ogranicenja;
3. Identifikacija skupa mogucih rešenja za koja su zadovoljene sve nejednacine sistema
ogranicenja i uslov nenegativnosti;
4. Nanošenje prave koja reprezentuje funkciju cilja za nulte vrednosti promenljivih
(prava funkcije cilja koja prolazi kroz koordinatni pocetak);
5. Translacija prave funkcije cilja sleva udesno, (nanošenje paralelnih pravih) sve dok ne
ucrtamo jednu takvu pravu koja sa skupom mogucih rešenja ima samo jednu
zajednicku tacku;
6. Utvrdivanje optimalnih vrednosti promenljivih x
1
i x
2
u vidu koordinata ekstremne
tacke skupa mogucih rešenja najudaljenije od koordinatnog pocetka (identifikacijom sa
grafika ili rešavanjem sistema jednacina pravih na cijem preseku se tacka nalazi), i
7. Odredivanje vrednosti funkcije cilja za optimalne vrednosti promenljivih.
Na kraju, važno je napomenuti da je postupak primene grafickog metoda odredivanja
optimalnog rešenja istovetan sa razmatranim i u slucaju rešavanja problema
minimuma, kao i mešovitog problema maksimuma. U slucaju rešavanja problema
minimuma, inverzan zahtev definisan odgovarajucom funkcijom cilja, determiniše
egzistenciju optimalnog rešenja u tacki skupa mogucih rešenja koja je najbliža
koordinatnom pocetku. Kod mešovitog problema maksimuma razlika prilikom
utvrdivanja skupa mogucih rešenja u odnosu na razmatrani postupak posledica je
predstaviti
Kanonični oblik modela LP, kada koeficijente funkcije cilja izrazimo u obliku vektora
c
=
(c
1
,c
2
,…,c
p+m
), glasi :
Postupak određivanja
optimalnog
rešenja primjenom
simplex
metoda, započinje sa
određivanjem početnog
bazičnog
rešenja. Pocetno bazicno
rešenje
standardnog problema maksimuma određuje se tako što se pretpostavlja da su realne
promjenljive jednake 0, a dodatne promjenljive jednake slobodnim članovima sistema
ograničenja, tj.
x
j
= 0 za j = 1,...,p
x
p+i
= b
i
za i = 1,…,m .
Funkcija cilja za svako pocetno bazično rešenje jednaka je nuli, Z = 0. Prema tome,
slicno kao kod grafickog metoda, rešavanje zadatka standardnog problema maksimuma
zapocinjemo iz pocetka
m
–dimenzionalnog vektorskog prostora. Navedena
pretpostavka, prema tome, ima za posledicu da vektorsku bazu na osnovu koje se
utvrduje pocetno bazicno rešenje obrazuju
vektori koeficijenata uz dodatne promenljive, dok su vektori koeficijenata uz realne
promenljive nebazicni. Vektori koeficijenata uz dodatne promenljive (kojih u našem
problemu ima m) obrazuju jedinicnu matricu - cija inverzna matrica je takode jedinicna.
Postavlja se pitanje, na koji način se može odrediti rešenje za koje funkcija cilja ima
veću vrijednost od 0? Odgovor na to pitanje jeste : izmjenom elemenata (vektora)
vektorske baze. Na ovo pitanje nam odgovaraju I i II Dantzingov simpleks kriterijumi, I
koji odgovara na pitanje koji vector ulazi u bazu, a II koji vekor napušta bazu.
I SK – Kriterijum za uključivanje jednog od prethodno nebazičnih vektora u bazu sastoji
se u tome da treba odabrati onaj vector (l-ti) kod koga je zadovoljen uslov C
j
-Z
j
= max
( C
j
-Z
j
)>0.
Ovaj uslov predstavlja kriterijum oprimalnosti, odnosno I simplex kriterijum za
izmjenu vektorske baze. Ukoliko su za neko od rešenja ove razlike za sve nebazične
vektore negativne, tj ( C
j
-Z
j
) <0, takvo rešenje je optimalno rešenja ukoliko se radi o
standardnom problemu maximuma. (obrnuto je za minimum >0).
II SK – Kriterijum za izlazak vektora iz baze, odnosno II Dantzingov simplex kriterijum,
na osnovu kojeg možemo konstatovati da iz baze treba iskjučiti onaj vektor A
k
za koga
bude zadovoljen uslov :
Iz baze, prema tome, izlazi onaj vektor A
k
za koji ovako
određen količnik bude
minimalan
pozitivan broj (manji od
ostalih vrijednosti)
u slučaju problema minimuma
i maximuma.
Nakon smjene vektora u bazi,
na
osnovu
primene navedenih simpleks
kriterijuma,
izracunava se novo poboljšano
rešenje i ispituje da li ono daje optimalnu tj maximalnu/minimalnu vrijednost funkcije
cilja.
13. x
14. x
15. x
16. x
17. x
18. x
19. x
20. x
5. Slobodni clanovi sistema nejednacina dualnog problema jednaki su koeficijentima
koji se uz promenljive nalaze u funkciji cilja primarnog problema;
6. Sve promenljive dualnog problema moraju biti nenegativne, zbog cega je ovaj uslov
obavezno prisutan i u dualnom problemu.
Osnovni oblik standardnog problema maksimuma:
Dualni problem koji odgovara prethodnom problemu , možemo predstaviti u obliku:
Ukoliko problem maksimuma predstavimo u obliku
tada, njemu odgovarajuci dualni problem možemo predstaviti u obliku:
Ocigledno je da izmedu promenljivih primarnog i dualnog problema postoji
povezanost i medusobna uslovljenost rešenja. Da bi to pokazali, uvedimo u primarni
problem
dodatne
promenljive
x
p
+1
,…x
p+m
u njemu odgovarajuci dualni problem y
m+1
,…y
m+p
, i izrazimo ih u sledecem
kanonickom obliku:
Primarni problem - problem maksimuma
Dualni problem - problem minimum
Broj promenljivih u primarnom i dualnom problemu sada je jednak i iznosi p + m . Ova
veza, može se izraziti na sledeci nacin: svakoj dodatnoj promenljivoj primarnog
problema odgovara jedna realna promenljiva dualnog problema.A svakoj realnoj
promjenljivoj primarnog problema odgovara jedna dodatna promjenljiva dualnog
problema.
22. Kakav je odnos izmedju optimalnih vrijednosti dodatnih promjenljivih
primarnog i realnih promjenljivih dualnog problema i obrnuto. Dokazati i
objasniti
Optimalne vrijednosti primarnog problema
odredjuje se kao negativna
vrijednost razlike prvog simpleks kriterijuma,za dodatne promjenljive iy poslednjeg
optimalnog rjesenja dualnog prblema tj.
Gdje m predstavlja br realnih promjenljivih u DP a j index promjenljive cija se
vrijednost trazi.
Teorema
Ukoliko su
moguca rešenja
primarnog i dualnog problema za koje su vrednosti funkcija cilja primarnog i dualnog
problema jednake, tj.
Tada
predstavljaju optimalna rešenja primarnog i dualnog problema,
respektivno.
Dokaz
Neka je neko moguce rešenje primarnog problema, na osnovu prethodne
teoreme znamo da je
Na osnovu uslova teoreme 1.4 slijedi
odnosno
Zakljucak ove teoreme je da je optimalno rjesenje primarnog problema a y
*
optimalno
rjesenje dualnog problema.
Teorema
Ukoliko su
moguca rešenja primarnog idualnog problema, tada su to
i optimalna rešenja ako i samo ako imamo zadovoljene uslove
Zakljucak ove teoreme je da je dualna promenljiva je jednaka nuli kada je njoj
odgovarajuca dodatna promenljiva pozitivna u optimalnom rešenju primarnog
problema, kao i ukoliko je neka realna promenljiva u optimalnom rešenju primarnog
problema jednaka nuli onda je njoj odgovarajuca dodatna promenljiva u optimalnom
rešenju dualnog problema pozitivna.
23. Ekonomsko tumacenje dualnih promjenljivih. Dokazati i objasniti.
D
ualne promenljive, osim znacajnih metodoloških osobina, pružaju mogucnost za
dobijanje veoma znacajnih informacija o karakteru problema linearnog programiranja,
kao I ispitivanje uticaja promene nivoa korišcenja raspoloživih resursa na vrednost
funkcije cilja. Ako imamo problem standardnog maksimuma
(max)z=cx
Ax≤b
x≥0
ciji je odgovarajuci dualni problem
(min)v=b'y
A'y≥c'
y≥0
Ako je optimalno rjesenje PP a
optimalno rjesenje DP, Pretpostavimo, sada, da se
elementi vektora
b
(resursi) primarnog problema povecavaju za iznos Δ
b
, koji ne
izaziva promenu strukture optimalne baze. povecanje iznosa
i
-tog resursa za D
b
uticace
na promenu vrednosti
funkcije cilja primarnog problema za iznos od Δz(y
*
)=y
*
i
Δb
i
Dokaz prethodnog, veoma znacajnog tvrdenja proizilazi iz karaktera
bazicnih rešenja i teorema dualnosti I na osnovu teoreme dualnosti možemo pisati:
cx
**
=y
*
(b+Δb)
cx*=y
*
b
Nakon oduzimanja druge jednacine od prve, dobijamo Δz(y
*
)= y
*
Δb. Na osnovu
ovakvog rezultata, odnosno relacije možemo konstatovati da je:
na osnovu cega možemo konstatovati da vrijednost dualne
promjenljive pokazuje za koliko jedinica ce se povecati(smanjiti)vrijednost funkcije
cilja primarnog problema,ukoliko se koriscenje resursa
poveca
(smanji) za jednu jedinicu.Dualne promjenljive predstavljaju tzv.obracunske cijene
koriscenih resursa,odnosno tzv.cijene u sijenci.
24. Objasniti osnovne karakteristike i znacaj primjene simplex tabele
Visestruko optimalno rjesenje se javlja ukoliko u okviru neke simpleks tabele postoji
maker jedna razlika I SK (Cj-Zj)=0 za neku nebazicnu promjenljivu Xj, dok su
vrijednosti ovih razlika za ostale nebazicne promjenljive negativne, izracunato jersenje
nije jedinstveno.
Uvodjenjem u bazu promjenljive Xj u cilju odredjivanja novog rjesenja, i iskljucivanjem
neke od prethodno bazicnih promjenljivih na osnovu II SK, dobili bi takodje optimalno
rjesenje za koje funkcija cilja ima istu vrijednost.
Usled osobina SKR, postojanje dva optimalna rjesenja ima za posljedicu da sve
konveksne kombinacije dva dobijena rjesenja predstavljaju optimalna rjesenja, zbog
veka kazemo da takav slucaj ima
visestruko optimalno rjesenje
.
Geometrijski, slucaj postojanja optimalnog rjesenja se javlja kad su koeficijenti pravna
prave koja reprezentuje neko od ogranicenja i koeficijenata pravca prave funkcije cilja
jednaki.
30. Analitički i grafički objasniti slučaj zadatka LP u kome ne postoje moguća
rešenja
Prilikom formulisanja modela LP moze se dogoditi da model bude tako postavljen da
ne postoje moguce rjesenja. On se desava ukoliko ne postoje vrijednosti proomjenljivih
za koje su zadovoljeni svi ogranicavajuci uslovi.
Geometrijski, takav zadatak ima prazan skup mogucih rjesenja, odnosno ne moze se
naci ni jedna tacka za koju su zadovoljene sve nejednacine (jednacine) sistema
ogranicenja modela.Rjesavanjem ovakvog zadatka koriscenjem simpleks metoda
nepostojanje mogucih rjesenja mozemo konstatovati u posljednoj simpleks tabeli. U njoj
svi elementi vrste (Cj-Zj) pokazace postojanje optimalnog rjesenja, al ice se u
optimalnom rjesenju naci
vjestacka promjenljiva,
sto je glavni indicator postojanja
kontradiktornih uslova u zadatku.
31. Dati analitičku i grafičku interpretaciju zadatka LP u kome ne postoje
konačne vrednosti promenljivih i funkcije cilja
Neogranicena vrijednost f-je cilja i promjenljivih se javlja kada je :
1) Model formulisan tako da tako da se jedna ili vise promjenljivih mogu povecati
neograniceno, a da to ne bude narusen ni jedan od ogranicenja koji su u ulozi
uslova u zadatku, i
2) Funkcija cilja na skupu mogucih rjesenja nema konacnu vrijednost, tj. Skup
mogucih rjesenja nije ogranicen skup.
Rjesavanje problema max koriscenjem simpleks metoda, ovaj problem možemo
identifikovati prije dobijanja vrednosti elemenata finalne simpleks tabele. Naime,
problem mogucnosti postojanja neogranicene vrednosti promenljivih i funkcije cilja
konstatovacemo u nekoj iteraciji u postupku odredivanja promjenljive koja treba da
izadje iz baze, odnosno prilikom odredivanja vrijednosti kolicnika r . Da bi neka
promjenljiva izašla iz baze, potrebno je da u odnosu na ostale vrijednosti ima najmanji
pozitivan kolicnik II SK. Medutim, ukoliko svi ovakvi kolicnici budu negativni ili
nedefinisani, možemo konstatovati da problem
nema konacno rešenje.
Nakon dobijene tabele i nakon izracunate vrijednosti kolicnika II SK dobijamo da je
beskonacnu vrijednost ili negativna vrijednost promjenljive, nemamo uslova za
odredjivanje promjenljive koja treba da izadje iz baze. Ovakav slucaj upucije na
cinjenicu da ovaj zadatak LP nema konacno, optimalno rjesenje.
32. Dualni simplex metod
Pronasao ga je Lemke, 1954. Godine, kada je trazio rjesenja primarnog problema, iz
optimalnog dualnog problema i dosao do nove metode koju je nazvao
dualni simpleks
metod.
Osnovna karakteristika ovog metoda je što polazi od nekog bazicnog rješenja koje nije
nenegativno i uslova da je simpleks kriterijum za nebazicne vektore (Cj-Zj) ≤ 0.
Koristimo je kada nam je dat problem min.
Veoma cesto, korišcenje dualnog simpleks metoda, u rešavanju problema optimizacije
ima niz prednosti u odnosu na druge algoritme simpleks metoda. Takvi su prije svega
problemi minimizacije, kod kojih je potrebno uvoditi veštacke varijable, zatim problemi
postoptimalne analize, celobrojnog programiranja...
fabrici koja proizvodi građevinske mašine (bagere, utovarivače i sl.), pošto promenljive
označavaju broj proizvedenih mašina, logično je, po prirodi samog zadataka, da njihova
vrijednost mora biti cijeli broj.
Zadaci linearnog programiranja u kojima se postavlja uslov cjelobrojnosti promenljivih,
svih ili samo nekih, jesu zadaci cjelobrojnog linearnog programiranja. Problem
celobrojnosti promenljivih se može javiti samo u zadacima koji se rešavaju simpleks
metodom. Uzrok pojave necelobrojnog rešenja nalazi se u karakterističnom elementu koji
se koristi u postupku transformacije bazičnih rešenja. Naime, ako su svi koeficijenti u
početnom bazičnom rešenju celi brojevi, optimalno rešenje će biti celobrojno jedino ako je
karakteristični elemenat u svakoj iteraciji jednak jedinici. Kako je taj uslov retko ispunjen,
često se javljaju rešenja koja nisu celobrojna. U praksi se najčešće, prilikom određivanja
optimalnog rešenja zadatka celobrojnog linearnog programiranja, najpre, rešava dati
problem kao problem linearnog programiranja, zanemarujući postavljeni uslov
celobrojnosti. Zatim se, u dobijenom optimalnom rešenju zadatka linearnog programiranja
izvrši zaokruživanje rezultata. Takav postupak može dati rešenja koji nisu daleko od
optimalnih, ali zaokruženi rezultati najčešće ne zadovoljavaju jedno ili više datih
ograničenja. To je uticalo na pronalaženje algoritma za rešavanje zadataka celobrojnog
linearnog programiranja, pa se, od 1958. godine, radovima Gomory-ja, celobrojno linearno
programiranje, razvija u posebnu oblast linearnog programiranja.
U zavisnosti od toga kako je postavljen uslov celobrojnosti, razlikuju se dva osnovna tipa
celobrojnih problema:
a) Ako je n1 = n , tj. ako sve promenljive u problemu linearnog programiranja moraju biti
izražene u celim brojevima, radi se
o potpuno celobrojnom programiranju.
b) Ako je n1 < n , tj. ako uslov celobrojnosti važi za samo deo promenljivih, radi se
o
delimično celobrojnom programiranju.
*Metodi za rešavanje zadataka celobrojnog linearnog programiranja
Svi metodi koje se koriste za rešavanje zadataka celobrojnog linearnog programiranja,
mogu se svrstati u tri grupe. To su
- Metodi zaokruživanja
. Suština ove grupe metode jeste u zaokruživanju dobijenih
rezultata. Naime, najpre se izračuna optimalno rešenje zadatka linearnog programiranja,
zanemarujući uslov celobrojnosti promenljivih, a zatim se izvrši zaokruživanje rezultata, na
celobrojna rešenja,zbog čega ovi metodi, najčešće daju rezultate koji su daleko od
optimalnih.
- Metodi enumeracije
. Osnovni pristup rešavanju zadataka primenom ove grupe metoda
sastoji se u tome da se prebroje (implicitno ili eksplicitno) sva moguća celobrojna rešenja.
Proces pronalaženja rešenja sastoji se od etapa, tako da se u svakoj narednoj etapi usvaja
bolje, od najboljeg rešenja na svim prethodnim etapama. Pošto je potrebno pretražiti veliki
broj rešenja, problem je obiman i velika je mogućnost pojave greške.
- Metod odsecajućih ravni (Gomory-jev metod).
Ovaj metod se naziva i “metod
odsecajućih ravni”, jer je osnovna ideja algoritma u formiranju dodatnog ograničenja koje
treba da “odseče” deo konveksnog skupa mogućih rešenja u kome nema celobrojnih
rešenja. Ovim “odsecanjem” se ne gubi ni jedno celobrojno rešenje. Prvobitni sistem
ograničenja se proširuje sa dodatnim ograničenjem, pa se u konačnom broju iteracija dolazi
do optimalnog rešenja.
34. Gomorijevo ograničenje i potpuno celobrojno programiranje
Ovaj metod se naziva i “metod odsecajućih ravni”, jer je osnovna ideja algoritma u
formiranju dodatnog ograničenja koje treba da “odseče” deo konveksnog skupa mogućih
rešenja u kome nema celobrojnih rešenja. Ovim “odsecanjem” se ne gubi ni jedno
celobrojno rešenje. Prvobitni sistem ograničenja se proširuje sa dodatnim ograničenjem, pa
se u konačnom broju iteracija dolazi do optimalnog rešenja. Prema Gomory-jevom
metodu, prvo se, dati problem rešava simpleks metodom, ne uzimajući u obzir uslov
celobrojnosti. Ako dobijeno rešenje zadovoljava i uslov celobrojnosti, rešenje je optimalno.
Međutim, ako dobijeno rešenje ne ispunjava i uslov celobrojnosti, tada se formira dodatno
ograničenje. Ovo ograničenje se priključuje postojećem sistemu ograničenja, pa se zatim,
primenom dualnog simpleks metoda, traži novo optimalno rešenje. Dodatno ograničenje
treba da zadovolji sledeće uslove:
- svako dopustivo, celobrojno rešenje, zadatka celobrojnog linearnog programiranja, mora
ostati dopustivo rešenje zadataka linearnog programiranja i posle dodavanja novog
ograničenja;
- dobijeno rešenje zadatka linearnog programiranja u svim sledećim koracima mora postati
nedopustivo, za isti zadatak, posle dodavanja novog ograničenja.
Ukoliko ni ovako dobijeno rešenje ne zadovoljava uslov celobrojnosti promenljivih, opet se
formira novo, dodatno ograničenje. Postupak se ponavlja sve dok se, u konačnom broju
iteracija, ne nađe rešenje koje zadovoljava uslov celobrojnosti.
odnosno
Nejednačina
predstavlja dodatno ograničenje, koje se dodaje
početnom sistemu ograničenja i koja obezbeđuje uslov celobrojnosti promenljivih u
optimalnom rešenju zadatka celobrojnog linearnog programiranja. Posle formiranja
dodatne nejednačine, za dobijanje optimalnog celobrojnog rešenja, najjednostavnije je
koristiti dualni simpleks metod. Zbog toga je potrebno nejednačinu
Geometrijski, svakom dodatnom ograničenju u n - dimenzionalnom prostoru,
odgovara jedna hiperravan, koja, od skupa mogućih rešenja, odseca jedan deo. U
odsečenom delu mnogougla nalazi se optimalno, necelobrojno rešenje. Prilikom
odsecanja dela mnogougla, sve tačke sa celobrojnim koordinatama, a među njima i
tražena optimalna tačka, ostaju u neodsečenom delu mnogougla. Pošto se skup tačaka
sa celim koordinatama neodsečenog dela mnogougla, poklapa sa skupom tačaka sa
celim koordinatama početnog mnogougla, jasno je da ako optimalno rešenje zadatka
linearnog programiranja na neodsečenom delu zadovoljava uslov celobrojnosti, to će
ono biti ujedno i optimalno celobrojno rešenje početnog zadatka.
Kroz nekoliko koraka odsecanja, tražena celobrojna tačka će biti ponovo na granici
novog mnogougla i predstavljaće optimalno rešenje zadatka celobrojnog linearnog
programiranja. Na primer, u dvodimenzionalnom vektorskom prostoru, ograničenja, u
koordinatnom sistemu x1ox2, obrazuju mnogougao K. Funkcija cilja dostiže
maksimalnu vrednost u tački x*, ali to rešenje ne zadovoljava uslov celobrojnosti
promenljivih. Međutim, unutar mnogougla K , postoji konačan broj tačaka sa
celobrojnim koordinatama(na slici su te tačke obeležene zvezdicom).
Na grafiku su prikazane i tri prave l1, l2 i l3 koje odgovaraju dodatnim, linearnim
ograničenjima.
Svaka od njih odseca jedan deo od skupa mogućih rešenja K . Tako, posle odsecanja jednog
dela skupa K , sa pravom l1 , optimalno rešenje postaje tačka x1. . Ograničenje l2 odseca još
jedan deo mnogougla K , a novo rešenje je tačka x2. Na kraju, odsecajući deo mnogougla
pravom l3, dobija se optimalno celobrojno rešenje. To je tacka x3.
Teorema 1.8
. Nejednačina
, na osnovu koje se formira dodatno
ograničenje:
1) je linearna
2) odseca nađeno optimalno necelobrojno rešenje zadatka
3) ne odseca niti jedno celobrojno rešenje zadatka.
Dokaz
Neka je x*- optimalno necjelobrojno rijesenje zadatka i neka je u tom rijesenju koordinata
xio necjelobrojna. Pokažimo da ovo rešenje ne zadovoljava uslov
. Naime,
ukoliko je x* optimalno rešenje, tada je xj*=0, xj* S pa je:
Odnosno,
, što je u suprotnosti sa definicijom razlomljenog dela nekog broja. Prema
tome x*- optimalno rijesenje zadatka ne zadovoljava uslov.
Treći uslov je već dokazan prilikom formiranja dodatnog ograničenja. No ipak,
pretpostavimo da u zadatku postoji neka tacka xc*, sa cjelobrojnim koordinatama koja ne
zadovoljava uslov
nego je
Kako je
i
za izraz
vazi:
37. Teorema kod celobrojnog programiranja
Nejednačina
fio - ∑fijxj ≤ 0
na osnovu koje se formira dodatno ograničenje je :
1. linearna
2. odsijeca nadjeno optimalno necjelobrojno rešenje
3. ne odsijeca ni jedno cjelobrojno rješenje zadatka.
DOKAZ
Linearnost dodatnog ograničenja je očigledna.
Nek je
x*
- optimalno necjelobrojno rešenje zadatka
n
max(Z)= ∑CjXj , Xj ≥ 0 , (j=1,2,.......n)
j=1
i neka je u tom rešenju koordinata
Xio
necjelobrojna. Pokažimo da ovo rešenje
zadovoljava uslov
fio - ∑fijxj ≤ 0
j S
ϵ
Ukoliko je
x*
optimalno rešenje ,tada je
xj* = 0
, xj* S , pa je
ϵ
∑fijxj =0
, odnosno
fio ≤ 0
,
što je u suprotnosti sa definicijom razlomljenog dijela nekog broja .Prema tome
x*
tj.
Optimalno rešenje zadatka
n
(max) Z = ∑CjXj Xj ≥ 0 , (j=1,2,...n)
j=1
ne zadovoljava uslov
→
fio - ∑fijxj ≤ 0
j S
ϵ
Pretpostavimo da u zadatku
n
max(Z)= ∑CjXj , Xj –cio broj , j=1,2,.......n1 (n1 ≤ n )
j=1
postoji neka tačka
Xc*
sa cjelobrojnim koordinatama, koje ne zadovoljava uslov
fio - ∑fijxj ≤ 0
nego je
fio - ∑fijxj ≥ 0 ,
j S j S
ϵ
ϵ
Kako je
∑fijxj ≥ 0 , i 0 ≤ fio < 1 , to važi 0 ≤ fio - ∑fijxj < 1
što je
suprotno
j S
ϵ
pretpostavci
da je veličina (
fio - ∑fijxj )
za sva rešenja zadatka
j S
ϵ
max(Z)= ∑CjXj
cio broj.
Na kraju , treba reći da neki problemi pokazuju sporu konvergenciju ka cjelobrojnom
optimalnom rješenju , pa je potrebno učiniti veći broj iteracija dok se ne dobije
optimalno cjelobrojno rješenje .Pošto se kod promjene Gomory-jevog metoda postojeći
sistem linernih nejednačina proširuje uvodjenjem dodatne nejednačine ,može se desiti
da je potrebno uvesti nekolioko dodatnih ,što znatno povećava model,odnosno br
promjenjivih u zadatku.Takođe,posle uvođenja dodatnog ograničenja ,zbog
zaokruživanja rezultata na celobrojne vrednosti , gubi se značaj dualnih promjenjivih.
38.
Postoptimalna analiza
Ukoliko se u modelu linearnog programiranja,nakon određivanja optimalnog rešenja
promjeni neki od uslova zadataka postavlja se pitanje da li nastale promjene dovode do
promjene strukture vektorske baze na osnovu koje je određeno optimalno
rešenje.Umjesto rešavanja kompletno novog zadatka linearnog programiranja , koje bi
formulisali uvođenjem novih (promjenjenih) vrijednosti parametara modela ,
1. da li se mjenjaju koeficijenti uz
nebazične promjenjive
optimalnog rešenja;
2. da li se mjenjaju koeficijenti uz
bazične promjenjive
optimalnog rešenja.
PROMJENA KOEFICIJENATA NEBAZIČNIG PROMJENJIVIH
(
Cj se mjenja ,a Zj ostaje nepromjenjeno
)
Pretpostavimo da se koeficijent
C
koji se nalazi uz nebazičnu promjenjivu u f-ji cilja
mijenja, pri čemu nastalu promjenu možemo predstaviti oblikom
Cj
= Cj + ∆Cj
Da bi utvrdili da li u novim uslovima rešenje izračunato na osnovu baze
α-opt
i dalje
ostaje optimalno,neophodno je da provjerimo da li će povećanje vrijednosti koeficijenta
Cj
dovesti do potrebe za uvođenjem prethodno nebazičnog vektora
Aj
u bazu , da li je
narušen uslov optimalnosti.. U tom cilju primjenjuje se Simpex kriterijum za ulazak u
bazu sa novom vrijednošću koeficijenta
Cj
(vrijednost Zj
ostaje nepromjenjena jer je
ona izračunata na osnovu koeficijenata bazičnih promjenjivih) ,Odnosno
Cj
- Zj =( Cj + ∆Cj) -Zj = (Cj-Zj)+ ∆Cj ...(j=1,...p) .
Da bi rešenje određeno na osnovu baze
α-opt
ostalo optimalno rešenje neophodno je da
konstatujemo da nijedan od nebazičnih vektora ne treba da uđe u bazu ,to će se
dogoditi ukoliko je :
Cj
- Zj ≤O (j=1,.....p).
Odnosno ukoliko je
(Cj-Zj)+ ∆Cj ≤ O
Ukoliko se koeficijent uz nebazičnu promjenjivu smanjuje tada ne postoji mogućnost da
se optimalno rešenje promjeni.Ukoliko se ovaj koeficijent uvećava tj. , ukoliko je
∆Cj >
O
tada će optimalno rešenje ostati i dalje optimalno ukoliko je zadovoljen uslov:
∆Cj < Cj-Zj (j=1,......p)
│
│
Ukoliko je, međutim vrijednost prirastaja koeficijenta koji se u f-ji cilja nalaze uz
nebazičnu promjenjivu
Xj
veći od apsulutne vrijednosti I simplex kriterijuma za vektor
Aj
, tj. ukoliko je
∆Cj > Cj-Zj (j=1,......p)
│
│
Tada rešenje nije više optimalno već se u cilju određivanja poboljšanog rešenja
neophodno u bazu uključiti prethodno nebazični vektor
Aj.
PROMJENA KOEFICIJENATA BAZIČNIH PROMJENJIVIH
(Cj – Zj )
Da bi ispitali kako promjena vrijednosti koeficijenata koji se u funkciji nalazi uz
promjenjjive iz optimalne baze utiče na optimalnost rešenja , treba utvrditi vrijednosti
razlika
(Cj - Zj)
za nebazične vektore.S obzirom da vrijednosti koeficijenta
Cj (j=1,...p)
za nebazične vektore ostaju neprimjenjene neophodno je izračunati i vrijednosti
Zj
(j=1,....p)
za sve nebazične promjenjive.
Neka je
Cb
vektor koeficijenta koji se u f-ji cilja nalaze uz bazične promjenjive iz
optimalnog rešenja.Pretpostavimo da je došlo do povećanja vrijednosti ovih
koeficijenata za iznos
∆Cb
.Novi vektor ovih koeficijenata je
Cb
= Cb+ ∆Cb
Vrijednosti Zj za nebazične vektore bile su određene iz relacije
Zj = Cb j (j=1....p)
Gdje je
j
vektor koeficijenata linearne kombinacije bazičnih vektora i nebazičnog
vektora Aj izračunat u obliku
j=α
־
1
Aj (j=1....p)
ostaje nepromjenjen.
Vrednosti
Zj
u uslovima promjenjenih koeficijenatavektora
Cb
odred,đujemo na
sledeći način
Zj
= Cb
j = (Cb+∆Cb) j = Cbj +∆Cbj =Zj+∆Zj (j=1....p)
Uz pretpostavku da se mjenjaju samo koeficijenti bazičnih promjenjivih ,što znači da
vrijednosti Cj ostaju nepromjenjene kriterijum optimalnosti rešenja
će biti
Cj- Zj
+∆Zj =Cj-(Zj+∆Zj) ≤O
ukoliko je
∆Zj>(Cj-Zj) (j=1...p)
Tada već izračunato optimalno rešenje ostaje i dalje optimalno ,tj. Vektor
Aj
ne treba
da uđe u bazu. U suprotnom slučaju kada postoji makar jedna pozitivna razlika
kriterijuma optimalnosti,izračunato rešenje više nije optimalno rešenje već se u bazu
novog rešenja mora uključiti prethodno nebazični vektor
Aj
za koju je ova razlika
maximalno pozitivna.
Promjena elemenata matrice A tj.promjena koeficijenata
a
ij u sistemu ograničenja
modela linearnog programiranja, može izazvati neophodnost promjene optimalnog
rešenja, što se ispituje u postupku postoptimalne analize. U slučaju ovakve promjene u
postupku postoptimalne analize optimalnost rešenja u novim uslovima može biti
ispitivana za različite promjene I to:
Promjena nebazičnog vektora
Promjena bazičnog vektora,
Uvodjenje novog vektora aktivnosti (nove promjenljive)
Uvodjenje novog ograničenja
a)
Promjena nebazičnog vektora Aj
Ukoliko nakon odredjivanja optimalnog rešenja modela dodje do promjene elemenata
nebazičnog vektora Aj postupak ispitivanja optimalnosti realizujemo korišćenjem
kriterijuma optimalnosti.
Neka Aj* predstavlja promjenjeni j-ti nebazični vektor. Da bi utvrdili da li taj vektor
treba uključiti u bazu, odnosno da li optimalno rešenje treba mijenjati izračunavamo
vrijednosti:
X
j
*= (
αopt
)
−
1
× A
j
*
koje su nam neophodne radi odredjivanja vrijednosti Zj*, u obliku
Zj*= C
B
Xj*
nakon čega pretpostavljajući da su koeficijenti u funkciji cilja ostali nepormijenjeni
primjenjujemo kriterijum optimalnosti, odnosno izračunavamo razliku Cj-Zj* . Ukoliko
je (Cj-Z*j)<=0 , rešenje izračunato na osnovu baze αopt i dalje ostaje optimalno. Ukoliko
je, medjutim, (Cj-Zj*)> 0 , zaključak je suprotan –prethodno rešenje neće u novim
uslovima biti optimalno, vec se uvodjenjem u bazu vektora Aj*može dobiti poboljšano
rešenje.
Prikazana analiza uticaja promjene nebazičnog vektora na optimalnost rešenja, realizuje
se i u slučaju ispitivanja uticaja uvodjenjem novog vektora aktivnosti (uz poznati
koeficijent koji se u funkciji cilja nalazi uz novu promjenljivu).
b) Prom
jena bazičnog vektora Ai
Obilježimo promjenjeni i-ti vektor , koji se nalazi u bazi α
opt
, sa Ai*, odnosno novu
bazu sa α*. Rešenja za novu bazu ce biti:
X
B
*=(
α
∗)
−
1
× b
Xj*= (
α
∗)
−
1
× Aj
Z*=C
B
X
B
*
Zj*= C
B
Xj*
Ukoliko je X
B
*≥0 izračunato rešenje je moguće, a ukoliko su za takvo rešenje razlike (Cj-
Zj*)<=0. Rešenje X
B
* je i optimalno, tj.α
opt
=α*. Ako je rešenje moguće, ali postoji makar
jedna pozitivna vrijednost kriterijuma optimalnosti za nebazične vektore, takvo rešenje
nije optimalno. Ukoliko, pak, u okviru vektora X
B
* postoji makar jedna negatitivna
vrijednost, prethodno optimalno rešenje u uslovima izmijenjenog bazicnog vektora više
nije čak ni moguće rešenje.
c)
Uvodjenje dodatnih ograničenja
Pretpostavimo da je u sistem jednačina modela dodato jos
t
jednačina, odnosno u
osnovni oblik modela (sa nejednačinama)
t
nejednačina oblika
a
m+1,1
x
1
+ ....+
a
m+p,p
x
p
≤b
m+1
a
m+t,1
x
1
+ …+
a
m+t
, p x
p1
≤ b
m+1
Ovakva promjena uticaće na neophodnost proširivanje vektora aktivnosti sa dodatnih
t
komponenti. Nakon toga, ispitivanje optimalnosti rešenja odredjenog na osnovu baze
α
opt
realizuje se na uobičajeni način. Proširena matrica baze, koja uključuje prethodnu
optimalnu bazu i dodatna ograničenja ima oblik
α
∗
¿
[
αopt
0
T
I
]
gdje T predstavlja matricu koeficijenata dodatnih ograničenja sa kojima su prošireni
bazični vektori iz optimalnog rešenja, I jediničnu matricu, a 0 nula matricu.
Na osnovu nove baze dobija se
X
B
*=(
α
∗)
−
1
× b
X
j
*= (
α
∗)
−
1
× A
j
I postupak ispitivanja optimalnosti rešenja realizuje se na dalje uobičajeni način.
42. PARAMETARSKO PROGRAMIRANJE-Formulacija zadatka
U standardnom zadatku linearnog programiranja, sa funkcijom cilja
I ograničenjima
43. Geometrijska interpretacija i graficko rešenje
Neka je dat zadatak parametarskog programiranja
Sistem ogranicenja obrazuje konveksni skup mogućih rešenja K, koji je na slici
predstavljen mnogouglom B B1 B2 B3 B4 B5
Za t=0 i Zt=0 funkcija cilja dobija oblik
tj. predstavlja pravu (MN) koja prolazi kroz koordinantni početak. Ekstremnu
vrijednost, funkcija cilja dostiže u tački B, jer je u toj tački prava MN paralelna sa
pravom M’N‘. Tačka B će biti ekstremna tačka i za sve vrijednosti parametra
t
za koje
će se grafik funkcije cilja, tj. prava MN nalaziti izmedji pravih M1N1(paralelno sa BB5) i
M2N2 (paralelno sa BB1).
Ako je za
t=t1
grafik funkcije cilja prava M1N1, a za t=t2 grafik funkcije cilja prava
M2N2, tada će tačka B biti extremna tačka za sve vrijednosti parametra
t
u intervalu
t2<=t<=t1. A
ko parametar
t
uzima vrijednosti koje se nalaze izvan intervala
t2<=t<=t1,
dobija se novo optimalno rešenje, odnosno tačka B više neće biti extremna
tačka.
44. Varijabilnost koeficijenata funkcije cilja
Ako u zadatku parametarskog programiranja parametar t, varira u intervalu
zadatak je da se interval podeli na konačan broj manjih intervala, tako da za svaku
vrijednost parametra t iz tih intervala, funkcija cilja dostiže maksimalnu vrijednost u
jednoj i samo jednoj tački skupa mogućih rešenja K.
Alogoritam za rešavanje zadataka parametarskog programiranja sastoji se iz dvije
etape:
1. Prvo je potrebno parametru t dodijeliti neku fiksnu vrijednost , najbolje jednaku
donjoj granici , tj t=t
d
, ili t=0. Tada ce u funkciji cilja svi koeficijenti postati fiksni,
tj dobiće se standardni zadatak linearnog programiranja. Zatim je potrebno naći
tačku u kojoj funkciji cilja Z
1d
, odnosno Z
t0
dostiže maksimum.
2. U drugom koraku je potrebno odrediti sve vrijednosti parametra t , z a koje
funkcije cilja Z
1
dostiže maksimum u nadjenoj tački . Nadjeni interval se isključi
iz intervala ( t
d,
t
g
) pa se za interval koji je ostao opet rešava zadatak linearnog
programiranja tj prelazi se na korak broj jedan. Postupak se ponavlja sve dok se
cio interval (
t
d,
t
g
) ne podijeli na konačan broj manjih intervala tj dok gornja
granica za parametar
t
ne bude
t=t
g
.
Ako je t=td , funkcija cilja ( 1.89) dobija oblik
U prvoj simpleks tabeli treba predvidjeti dve vrste za koeficijente funkcije cilja . U
jednoj će se upisati koeficijenti c
j
a u drugoj koeficijenti d
j
, iz funkcije cilja. Takodje
2. Svi koeficijenti βj < 0. Iz nejednačine sledi
Jer se dijeljenjem sa negativnim brojem smisao nejednačine mijenja. Pošto brojeva
ima m , parametar t mora biti veći od svakog od njih. Ako od m količnika odaberemo
najveći, tada su svi uslovi ispunjeni tj.
Gornja granica za parametar t ne postoji, pa se on može povećavati beskonačno.
Interval vrijednosti parametra
t
, za koji nadjeno rešenje ostaje optimalno je
Znaci da je td
3. Ako medju koeficijentima βj ima i pozitivnih i negativnih.Interval vrijednosti
parametra
t
, za koji nadjeno rešenje ostaje optinalno je
Tj. Interval ima i donju i gornju granicu.
4. Ako je β j = 0, tada iz nejednacine
slijedi da je α
j
≤0 odnosno
uslov optimalnosti je ispunjen, pa na kolone kod kojih je βj =0 ne treba obracati
pažnju.
Prema tome, rešenjem nejednačine dobijaju se granice intervala promene
parametra
t
, tj. donja granica (t
d
) I gornja granica ( t
g
)u kojima optimalno resenje
ostaje nepromenjeno. Kada se utvrde granice , potrebno je uporediti dobijeni
interval [
t
d1,
t
g1
]sa intervalom [
t
d,
t
g
]
Ako je
t
g1
≥
t
g
interval [
t
d,
t
g
] se nalazi unutar intervala [
t
d1,
t
g1
] i zadatak je riješen.
Za bilo koju vrijednost
t koje pripada
[
t
d,
t
g
] funkcija Z dostiže maksimum u jednoj
i samo jednoj tački.
Ako je
t
g1
<
t
g
tada će u intervalu [
t
d1,
t
g1
] funkcija Zt, dostici maksimum u jednoj
tacki , a ostali dio intervala [
t
g1
, t
g
]treba dalje ispitivati.
Ispitujući model parametarskog programiranja sa varijabilnim parametrom u
funkciji cilja , došli smo do intervala
t
koji pripada [
t
d,
t
g
] u
kome može da varira
parametar
t
, tako da dobijeno optimalno rešenje ostaje nepromenjeno. To znači
da je moguće odrediti granice variranja parametra tako da odredjena struktura
izlaza, tj. proizvoda ostaje nepromenjena. I to je značajno iz dva razloga. Prvo, u
mogućnosti smo da odredimo ponašanje sistema ako se parametri C mijenjaju ( u
datim granicama), i drugo da odredimo parametre tako da se pri odredjenom
optimalnom rešenju postigne što bolji uspjeh. A najčešće, menadzment
preduzeća želi da zna u kom intervalu se mogu mijenjati ulazni parametri bez
suštinskog odstupanja od nadjenog optimuma i bez značajnog narušavanja
strukture optimlanog rešenja.
*Varijabilnost koeficijenta vektora ogranicenja
Ako je vektor ograničenja linearno zavisan od vremena
t
tada treba maximizirati
funkciju cilja
Pri ograničenjima
Koristeći poznatu proceduru za formulisanje dualnog problema parametarski zadatak
se transformiše u problem koji glasi
Prema tome,
problem
se sastoji u određivanju programa proizvodnje x koji će
obezbediti da odnos efekata i investicija bude, u datim uslovima, što veći. Radi se dakle
o problemu
maksimizacije efikasnosti investicija
. Razlomljeno linearno programiranja ima
značajnu ulogu u optimizaciji ekonomskih problema zbog toga što su, po pravilu,
relativni pokazatelji važniji od apsolutnih, pa modeli razlomljenog linearnog
programiranja ne zaostaju za modelima linearnog programiranja.
Za razmatranje ekonomskih problema, potrebno je uvesti još dva ograničenja:
(1)Skup mogućih rešenja zadatka razlomljenog linearnog programiranja nije prazan i
ograničen je, što znači da nijedna od ekonomskih aktivnosti koja se pojavljuje u modelu
ne može biti neograničena. Inače, skup mogućih rešenja je, kao i kod linearnog
programiranja, konveksan, tj. ima konačan broj ekstremnih tačaka.
(2)Imenilac funkcije cilja (2.1.) mora biti razlicit od nule, tj.
z
2
(x) ≠0
.
Naime, pošto je z
2
(x)
linearna i neprekidna funkcija, ona u zatvorenom konveksnom
skupu ne menja znak ( za svako x koje zadovoljava sistem linearnih ograničenja). Ako
bi se desilo da je imenilac funkcije cilja negativan, on se može prebaciti u brojilac, pa se
zato i uvodi ograničenje da je z
2
(x) > 0 . Ovo ograničenje omogućava da se isključi
mogućnost dobijanja neodređenog programa.
Uslov z
2
(x) ≠ 0 matematički nebitno sužava okvir zadatka a ekonomski ima veliki
značaj.
46. Dokazati teoremu o monotonosti funkcije cilja kod hiperboličnog
programiranja
Teorema.
Na bilo kom pravolinijskom odsečku koji pripada skupu K (K-skup mogućih
rešenja), razlomljena linearna funkcija je monotona.
Dokaz
Neka su x′ i x′′ krajnje tačke skupa mogućih rešenja. Tačka x predstavlja konveksnu
kombinaciju tačaka x′ i x′′ , odnosno:
x = λx′ + (1 − λ)x′′ , 0 ≤ λ ≤1 .
Pošto se svaka koordinata tačke x može izraziti u vidu konveksne kombinacije tačaka
x′ i x′′ ,
brojilac
funkcije cilja (2.1.) će biti :
Analogno se dobija i za imenilac, pa funkcija cilja (2.1.) dobija oblik :
Kako su
x′ i x′′ konstantne veličine
,
u izrazu (2.4.) promenljiva je samo veličina λ pa je
z razlomljeno linearna funkcija koja zavisi od parametra λ ( 0 ≤ λ ≤1).
Da bi dokazali monotonost funkcije z na datom odsječku tj. za (0 ≤ λ ≤1) potrebno je
utvrditi znak izvoda
.
Ako se, u brojiocu prethodnog razlomka, izvrše potrebne računske radnje a imenilac
izrazi u obliku [z
2
(x) ]
2
dobija se:
Brojilac
u ovom izrazu ne zavisi od λ , pa je za konstantne veličine x′ i x′′ i on
konstantan
, dok je
imenilac
kao kvadrat neke veličine uvijek
pozitivan
.
Zaključak:
Znak izvoda zavisi od znaka brojioca koji će na datom odsječku biti ili
pozitivan ili negativan.Pošto izvod ne mijenja znak slijedi da je funkcija cilja monotono
rastuća
ili opadajuća
, što je trebalo i dokazati.
47.
Dokazati da funkcija cilja RLP dostiže ekstremnu vrednost u ekstremnoj tački
skupa mogućih rešenja
Teorema.
Razlomljena linearna funkcija dostiže ekstremnu vrednost u ekstremnoj tački
konveksnog skupa mogućih rešenja.
Dokaz
Opšti oblik modela matematičkog programiranja možemo predstaviti u obliku zahtjeva
za određivanjem vrijednosti promenljivih x
1
, x
2
, ..., x
n
koje zadovoljavaju m nejednačina i
jednačina oblika:
g
i
(x
1
, x
2
, ..., x
n
) {≤, =, ≥} b
i
i=1,..., m
i za koje se ostvaruje maksimalna ili minimalna vrednost funkcije:
z= f (x
1
, x
2
, …, x
n
).
2)
Skup mogućih rješenja je neograničen.
Funkcija cilja dostiže maksimalnu i
minimalnu vrednost.
3)
Skup mogućih rješenja je neograničen.
Funkcija cilja dostiže samo maksimalnu
vrednost. Prava x
2
= kx
1
zauzima položaj paralelan jednom ograničenju, pa funkcija
cilja ima tkz. asimptotski minimum.
4) Skup mogućih rješenja je neograničen, oba ekstremuma su asimptotska.
Algoritam za dobijanje optimalnog rješenja, tj. ekstremnih tačaka skupa mogućih
rešenja, za razlomljenu linearnu funkciju cilja, oblika:
uz postojanje sistema linearnih ograničenja, potrebno je:
1) Grafički predstaviti prave koje reprezentuju nejednačine sistema ograničenja.
2) Identifikovati skup mogućih rešenja (K) tj. konveksni skup.
3) Da bi utvrdili tačke u kojima funkcija cilja dostiže ekstremnu vrijednost, potrebno je
izraziti funkciju cilja (2.11.) u obliku
x
2
= kx
1
, pri čemu je
Funkcija x
2
= kx
1
, geometrijski predstavlja pravu koja prolazi kroz koordinatni početak
i zavisi od veličine z.
k= f(x) pa za fiksirano z, koeficient pravca prave x
2
= kx
1
, je konstantan, prava
zauzima određeni položaj. Ako se z mijenja
,
mijenja se I koeficient pravca pa se prava
rotira oko koordinatnog pocetka, mijenjajuci samo pravac.
4) Utvrditi karakter zavisnosti koeficijenta pravca prave x
2
= kx
1
od veličine z preko
izvoda, tj.
Imenilac izvoda, kao kvadrat neke veličine, je uvijek pozitivan.
Brojilac izvoda ne zavisi od z, pa izvod ima konstantan znak tj. pri povećanju
vrednosti z, k će ili da raste ili da opada, a prava x
2
=kx
1
će se okretati samo u
jednu stranu.
Ako je znak izvoda negativan, prava x
2
=kx
1
se okreće u pravcu kazaljke na satu.
Ako je pozitivan u pravcu suprotno kazaljci na satu.
5) Izračunati koordinate ekstremnih tačaka i vrijednost funkcije cilja u tim tačkama.
49. Grafički metod-slučaj funkcionala bez slobodnog člana
Imamo funkciju razlomljenog linearnog programiranja koja nema slobodan član.
Funkcija ima samo dve nepoznate promenjive zato što je to ograničenje grafičkog
metoda. Ukoliko funkcija razlomljenog programiranja glasi
I ukoliko imamo dat sistem ograničenja koji predstavlja linearne jednačine zadatak,
rešavamo zadatak na sledeći način:
1)
Graficki predstavljamo prave koje predstavljaju nejednačine sistema ograničenja.
2)
Identifikujemo skup mogucih rešenja (
K
) tj. konveksni skup.
3)
Da bi utvrdili tacke u kojima funkcija cilja dostiže ekstremnu vrednost, potrebno
je izraziti datu funkciju cilja na sledeci način, tj dobijamo da je X
2
jednako
X
2
= (c
1
-z*t
1
)/(z*t
2
-c
2
) * x
1
X
2
= K*X
1
iz cega sledi da je koeficijent pravca funkcije cilja K jednak
Dalje odredimo za
?
i
?
vrednosti koje ce zadovoljiti jednacine
Posle svih zamena, dobija se nova FC i sistem ogranicenja ogranicenja oblika
Ovim smo FC koja je imala slobodni clan sveli na funkciju koja nema slobodni clan.
Sledeci korak je graficko unosenje jednacina sistema ogranicenja gde vidimo da sistem
ogranicenja u koordinatnom sistemu
?
0`
?
formira konveksan skup. Geometrijski
interpretirano to znaci da je zamena promenjivih dovela samo do pomeranja
koordinatnog pocetka iz 0 u 0` (
?
,). Sto i vidimo sledecoj slici. Na osnovu iste dolazimo
do nekoliko zakljucaka a to je da:
-
Sistem ogranicenja obrazuje konveksan skup
-
Zamena promenjivih znaci samo pomeranje koordinatnog pocetka iz 0 u 0`
-
Pri pomeranju koordinatnog pocetka konveksni skup ne menja svoj polozaj u
ravni jer se sa promenom koordinatnog sistema menjaju i ogranicenja koja ga
odredjuju. I upravo radi toga…
-
Nije potrebno transformisati ogranicenja, pa samim time ni odredjivati
konveksni skup.
Za kraj zakljucujemo da se graficki metod odredjivanja optimalnog rešenja zadatka
razlomljenog linearnog programiranja sa slobodnim clanom u FC sastoji od sledecih
aktivnosti:
1) U koordinatnom sistemu X
1
0X
2
graficki predstaviti prave koje reprezentuju
nejednacine sistema ogranicenja.
2) Identifikovati skup mogucih rešenja (konveksni skup
K
).
3) Nacrtati grafik prave koja predstavlja imenilac funkcije cilja i proveriti da li je
zadovoljen uslov da Z
2
(x) =/ 0 (tj da imenilac funkcije cilja nije jednak nuli)
4) Izracunati koordinate novog koordinatnog pocetka, tj. 0` (
?
,
?
)
5) Utvrditi koordinate ekstremnih tacaka i znak izvoda
dk/dz
6) Izracunati vrednost funkcije cilja u ekstremnim tackama.
51. Martošev metod za rešavanje problema hiperboličnog programiranja
Linearna ogranicenja u zadacima razlomljenog linearnog programiranja i postojanje
optimalnog rešenja zadatka u ekstremnoj tacki konveksnog skupa mogucih rešenja,
omogucava primenu simpleks metoda za rešavanje problema razlomljenog linearnog
programiranja. Potrebno je jedino definisati kriterijume optimalnosti zadatka
razlomljenog linearnog programiranja. Martosev metod predstavlja jedan od nacina
resavanja problema razlomljenog linearnog programiranja pomocu simplex metoda.
Martos je prilagodio standardnu simplex tabelu tako sto je vrstu Cj razlozio na dve
vrsta: Z
1
i Z
2
. U vrsti Z
1
upisuju se koeficijenti brojioca funkcije cilja a u vrsti Z
2
se
upisuju koeficijenti imenioca iste funkcije. Imamo jos jednu razliku a to je vrsta dj.
Zadatak razlomljenog linearnog programiranja cemo predstaviti na sledeci nacin:
U pocetnom bazicnom rešenju datog problema (kao i u modelu linearnog
programiranja) , vrednosti realnih promenljivih su jednake nuli, vrednosti dodatnih
promenljivih slobodnim clanovima sistema ogranicenja, a vrednost funkcije cilja je
Opsti oblik prve simplex tabele koja odgovara datom problem razlomljenog linearnog
programiranja je
Da bi dosli do OR potrebno je izvrsiti nekoliko iteracija prilikom kojih se vrsi promena
vektora u bazi. Pretpostavicemo da je odradjeno k iteracija i da u narednoj, k+1 iteraciji,
u bazu ulazi neki vektor X
s
a bazu napusta neki vektor X
p+r
. U tom slucaju
karakteristican element je a
rs
. U (
k
+1)-voj simpleks tabeli umesto C
0
(k)
nalazice se C
0
(k+1)
ii
mace vrednost jednaku
Tj kada skratimo a
rs
dobicemo izraz
Na isti nacin se dobija i T
0
(k+1)
. Kada smo izracunali vrednost C
0
i T
0
u (k+1)-oj interaciji,
mozemo da izracunamo vrednost FC u toj iteraciji kao odnos izmedju C
0
(k+1)
i T
0
(k+1)
tako
da je
b
r
/a
rs
predstavlja drugi simplex kriterijum. Sledeci korak je da nadjemo razliku izmedju
vrednosti funkcije cilja u k-toj iteraciji i (k+1)-oj iteraciji tj
odnosno
Ako imenilac razlomka oznacimo sa T
0
(k)
* T
0
(k+1)
a u brojiocu izdvojimo zajednicki clan –
b
r
/a
rs
dobijamo novi izraz
A s obzirom da je
izraz
postaje
Iz ovog izraza cemo dobiti kriterijum za ulazak promenjive u bazu. Kada ga vise
analiziramo vidimo da:
a) Da ne bi izašli iz skupa mogucih rešenja, kolicnik –b
r
/a
rs
mora biti pozitivan i
najmanji od svih mogucih, tj.
Zato mora biti da a
rs
>0 jer je po uslovu zadatka b
r
>0. U skladu sa njim i kolicnik –
b
r
/a
rs
ce biti uvek negativan.
b) Prema uslovu zadatka razlomljenog linearnog programiranja, imenilac funkcije
cilja (u skupu mogucih rešenja to je bilo T
0
(k)
* T
0
(k+1)
) mora biti pozitivan, tj. za ma
koje rešenje T
0
(k)
>0 i T
0
(k+1)
.
c) Znak razlike z
(k+1)
-z
(k)
zavisi od dj na sledeci nacin:
-
Ako je d
s
>0 onda je z
(k+1)
-z
(k)
>0
-
Ako je d
s
<0 onda je z
(k+1)
-z
(k)
<0
Drugim recima, ako se za karakteristicnu kolonu odabere kolona sa pozitivnom
vrednošcu
ds
, u narednoj iteraciji ce se smanjiti vrednost funkcije cilja. Ako je
d
s
<0 onda z
(k+1)
>z
(k)
tj vrednost funkcije cilja ce se povecati ako se za
karakteristicnu kolonu odabere kolona sa negativnom velicinom
ds
. Vazi i
obrnuto. A ako je d
s
=0 onda z
(k+1)
=z
(k)
tj vrednost FC ostaje nepromenjena.
U pocetku smo imali funkciju razlomljenog linearnog programiranja sa promenjivom X
a sada imamo funkciju linearnog programiranja sa promenjivom y. Dobijena funkcija
cilja dobija oblik
Zatim pomnozimo sistem ogranicenja sa y
0
pa dobijamo novi oblik sistema ogranicenja
Tj, kada uzmemo u obzir drugu smenu koju smo uveli i kada slobodne clanove
prebacimo na levu stranu , sistem ogranicenja izgleda
Iz uslova prve smene dobijamo novo ogranicenje koje glasi
I koje dodajemo postojecem sistemu ogranicenja.
Na kraju dobijamo novu funkciju cilja linearnog prigramiranja koja je mesoviti problem
maksimuma :
Zadatak resavamo kao mesoviti problem maksimizacije kod linearnog programiranja i
kada dobijemo optimalno resenje, koristimo smenu sa pocetka da dobijemo resenja
razlomljenog linearnog programiranja tj.
X
1
=
Y
1
Y
0
X
2
=
Y
2
Y
0
... X
p
=
Yp
Y
0
53. x
54. x
55. x
56. x
57. Dokazati da matrica koeficijenata sistema ograničenja kod TP ima r=m+n-1
Matricu koeficijenata sistema ogranicenja našeg transportnog problema možemo
predstaviti u obliku :
1 1 ... 1 0 0 ... 0 .... 0 0 ... 0
0 0 ... 0 1 1 ... 1 .... 0 0 ... 0
. . .
0 0 ... 0 0 0 ... 0 ... 1 1 .... 1
A = 1 0 ... 0 1 0 ... 0 .... 1 0 ... 0
0 1 ....0 0 1 ... 0 .... 0 1 .... 0
…
0 0 ... 1 0 0 ... 1 .... 0 0 ... 1
U matrici A ima ukupno
( m + n )
vrsta, I sve su linearno zavisne. Ukoliko saberemo
prvih
m
vrsta matrice A dobicemo vrstu ciji su svi elementi jedinice - isto takvu vrstu
cemo dobiti sabiranjem preostalih
n
vrsta matrice A, tj.
p
1
+ p
2
+…. + p
m
= p
m+1
+ p
m+2
+…+ p
m+n
( p
1
,…., p
m+n
= vrste matrice A)
Ovo znaci da svaku vrstu matrice A možemo izraziti u vidu linearne kombinacije
ostalih.
Na primjer, za prvu vrstu je
p
1
= (p
m+1
+ … + p
m+n
) – (p
2
+…. + p
m
)
Isto važi za bilo koju od preostalih vrsta matrice A.
Ukoliko sada iz matrice A iskljucimo poslednju vrstu, i uzmemo minor
(
m
n
1)
-
og
reda koji ukljucuje kolone koeficijenata uz promenljive x
1n
, … , x
mn
, x
11
, …. , x
1n-1
,
dobijamo
1 0 ... 0 1 1 ... 1
0 1 ... 0 0 0 ... 0
..... ….. .….
2. Metod minimalnih troškova
Prilikom rasporedivanja kolicina robe za prevoz ne uzimaju se u obzir iznosi
transportnih troškova na pojedinim putevima. Metod minimalnih troškova
podrazumijeva prevashodno korišcenje puteva (polja tabele) kojima odgovaraju
najmanji troškovi po jedinici prevezene robe. Zbog toga, ovaj metod u opštem slucaju
obezbeduje dobijanje pocetnog bazicnog rešenja koje je bliže optimalnom rešenju u
odnosu na odgovarajuce rešenje dobijeno metodom severozapadnog ugla. Postupak
odredivanja pocetnog bazicnog rešenja zapocinje korišcenjem puta kojem odgovaraju
najmanji troškovi, pri cemu u odgovarajuce polje tabele unosimo maksimalno mogucu
kolicinu (manji od iznosa ponude i tražnje) za prevoz. Naizmenicnim popunjavanjem
preostalih praznih polja kojima odgovaraju najmanji transportni troškovi, u
m
+
n
-1
koraka dolazi se do pocetnog bazicnog rešenja. Odredivanje pocetnog bazicnog rešenja
primjenom ovog metoda podrazumijeva prethodnu i sukcesivnu analizu troškova
transporta robe, što u problemima vecih dimenzija otežava postupak i povecava
mogucnost pogrešnog rasporedivanja. Prednost ovog metoda ogleda se cinjenici da
njegova primjena obezbjeduje znacajno skracivanje postupka odredivanja optimalnog
rešenja.
3. Vogelov metod
( metod maksimalnih razlika )
Predstavlja najsloženiji postupak odredivanja pocetnog bazicnog rešenja. Suština ovog
metoda sastoji se u izracunavanju
potencijalnih gubitaka
koji ce nastati ukoliko se
izmedu dva polja sa minimalnim transportnim troškovima, koja se nalaze u nekoj vrsti
(koloni) tabele, koristi ono polje u kome su transportni troškovi veci. Primjena ovoga
metoda obezbjeduje pocetno rasporedivanje kolicina robe za prevoz, tj. izracunavanje
vrednosti promenljivih bazicnog rešenja koje su
najbliže
optimalnom rešenju. Zbog
toga ovaj metod garantuje najkracu algoritamsku proceduru odredivanja optimalnog
programa transporta robe.
I korak
: Izracunavanjem
vrijednosti razlika
izmedu dva minimalna troška za svaku
vrstu i kolonu tabele. Tako izracunate razlike pridružujemo vrstama i kolonama tabele,
II korak
: Odredujemo vrstu, odnosno kolonu kojoj odgovara
najveca vrijednost
razlike.
III korak
: Pocetnu kolicinu rasporedujemo u polje sa
najnižim troškovima
koje
odgovara vrsti (koloni) sa najvecom izracunatom razlikom.
S obzirom da se u jednom koraku eliminiše ili vrsta ili kolona, nakon svakog
rasporedivanja vrši se izracunavanje promijenjenih razlika izmedu dva minimalna
elementa (od preostalih).
Postupak se, kao i kod drugih metoda za odredivanje pocetnog bazicnog rešenja,
završava nakon preraspodeljivanja ukupne ponude na mesta tražnje, tj. nakon
popunjavanja
m
+
n-
1 polja tabele.
60. Koji je razlog pojavljivanja i kako se manifestuje problem degeneracije kod
TP? Kako se on prevazilazi?
Ukoliko u postupku rešavanja transportnog problema odredimo rešenje u kome nema
m+n-1
bazicnih promenljivih, odnosno popunjenih polja tabele, konstatujemo da takvo
rešenje ne zadovoljava neophodan uslov za primjenu nekog od metoda optimizacije.
Takav slucaj predstavlja degeneraciju transportnog problema, dok ovakvo rešenje
smatramo degenerativnim.
Ovakav slucaj se javlja kad je neka od parcijalnih suma ponude jednaka nekoj od
parcijalnih
suma tražnje.
Slucaj degeneracije t.p. može se pojaviti:
prilikom odredivanja pocetnog bazicnog rešenja,
u postupku poboljšavanja nekog programa transporta u proceduri optimizacije.
Prilikom odredivanja pocetnog rešenja degeneracija se javlja u slucaju kada
popunjavanjem nekog od polja istovremeno eliminišemo raspoložive kolicine
odgovarajuce vrste i kolone, odnosno istovremeno iscrpimo svu raspoloživu ponudu
robe i zadovoljimo ukupnu tražnju koja odgovara tom odredištu. U postupku
optimizacije, kada u nekoj od iteracija odredujemo poboljšano rešenje, slucaj
degeneracije se javlja kada u jednom koraku iskljucimo iz baze dvije promenljive, a u
bazu ukljucimo samo jednu prethodno nebazicnu promenljivu.
Tabelarno, ovaj slucaj nastaje kada u jednom koraku dva (ili više) prethodno popunjena
polja ostaju prazna, dok popunjavamo samo jedno prethodno prazno polje.
Za primjenu nekog od metoda optimizacije programa transporta neophodno je da u
tabeli bude popunjeno tacno
n+m-1
polja, odnosno da se toliki broj promenljivih nade u
bazi.
Zbog toga, slucaj degeneracije se
prevazilazi
tako što se u neko od praznih polja unosi
kolicina od
ε
jedinica robe, gdje je
ε
infinitezimalno mali broj, koji ne narušava izražene
jednakosti ponude i tražnje. Obicno se ova velicina unosi u prazno polje kome
odgovaraju najniži transportni troškovi po jedinici prevezene robe.
61. Stepping stone metod iliti metod skakanja s kamena na kamen
Za određivanje optimalnog rješenja mogu se koristiti:
a) Stepping stone metod (u daljem textu SSM)
b) Metod potencijala (Modi metod)
SSM:
-Koristi se za provjeru pocetnog bazicnog rjesenja (u daljem textu PBR) tj. Da bismo
mogli da koristimo SSM moramo izracunati PBR. Sustina ovog metoda sastoji se u
ispitivanju NEzauzetih polja. Ako imamo u transportnoj tabeli polja preko kojih se vrsi
transport zovemo ih zauzeta. Preko tih polja se vise ne moze transportovati a znamo
troskove za ta polja i mi pokusavamo da ih snizimo tako sto cemo pokusati transport
preko drugih polja, pa je sustina ove metode da se ispituju nezauzeta polja. Znaci,
ispitujemo ta nezauzeta polja da vidimo da li ona mogu da se ukljuce u transport da bi
troskovi bili nizi u odnosu na pocetne. To nezauzeto polje pokusavamo da ukljucimo u
62. Metod potencijala – Modi metod(modifikovani simplex metod)
Metod potencijala predstavlja postupak za određivanje optimalnog programa
transporta robe na osnovu već određenog početnog programa transporta. Suština ovog
metoda sastoji se u ispitivanju mogućnosti poboljšanja već dobijenog programa
transporta, koji se u iterativnoj proceduri transformiše u optimalno rješenje. Postupak
primjene metoda potencijala podrazumijeva određivanje po jednog takozvanog
množitelja za svaku od jednačina ponude i tražnje sistema ograničenja modela
transporta.
Množitelaj ima m+n a bazičnih promjenljivih m+n-1. Jednom od množitelja dodjeljuje
se proizvoljna vrijednost, najčešće nula. Preostali množitelji se izračunavaju iz relacije:
Cij=Ui+Vj odnosno Cij-Ui+Vj=0 pri čemu je: i=1,...,m j=1,...n
Cij su vrijednosti potencijala a Ui i Vj množitelji i ova relacija važi za zauzeta polja.
Za nezauzeta polja potencijali se izračunavaju iz relacije:
Cij'=Cij-Ui-Vj
Ukoliko za jedno ili više praznih polja dobijemo negativne vrijednosti potencijala
(Cij'<0) izračunati program transporta nije optimalan. Za poboljšanje programa se
koristi polje kome odgovara negativni potencijal sa najvećom apsolutnom vrijednošću.
Za to polje crtamo poligon i balansiramo količine po istom principu kao kod SSM
(objašnjeno već kod SSM da ne mlatim istu priču sad). Nenegativne vrijednosti
potencijala za prazna polja nekog programa transporta pokazuju da se radi o
optimalnom rješenju.
Algoritam Modi metoda:
1) Odrediti početni program transporta robe (PBR)
2) Odrediti množitelje Ui i Vj za svaku vrstu i kolonu početnog rješenja
3) Izračunati potencijale za svako prazno polje tabele
4) Koristeći polje sa najvećom apsolutnom vrijednošću potencijala odrediti
poboljšani program transporta odgovarajućim balansiranjem količine prevezene
robe
5) Postupak se ponavlja sve dok svi potencijali ne budu pozitivni.
Optimalno rješenje je isto kao kod SSM.
63. Otvoreni problem transporta i postupak njegovog rješavanja
Kad radimo transportni problem potrebno je da postoji jednakost ponude i tražnje i
to znači da se radi o zatvorenom transportnom problemu, u kojem raspodjela robe
koja postoji u pojedinim mjestima ponude omogućuje zadovoljenje cjelokupne
tražnje svih potrošača. Pored zatvorenog transportnog problema postoji i otvoreni i
to onda kad nije zadovoljen uslov o postojanju jednakosti između ukupne ponude i
ukupne tražnje tj kada je
Σai ≠ Σbj
radi se o otvorenom transportnom problemu
.
Postoje dva slučaja otvorenog modela transporta:
1) Otvoreni model u kojem je ukupna ponuda veća od ukupne tražnje tj.
Σai > Σbj
2) Otvoreni model u kojem je ukupna ponuda manja od ukupne tražnje tj.
Σai < Σbj
Da bi problem mogao da se riješi potrebno je da ponuda I tražnja budu jednake
jer je algoritam za rješavanje tranansportnog problema takvog oblika pa ih moramo
izjednačiti.
1)
Slučaj kad je ponuda veća od tražnje:
Postupak rješavanja modela sastoji se u definisanju jednog uslovnog (fiktivnog)
mjesta tražnje (fiktivna kolona u tabeli) kojem se dodjeljuje iznos za koji je ukupna
tražnja
manja
od
ukupne
ponude
odnosno:
bn+1 = Σai - Σbj
2)
Slučaj kad je ponuda manja od tražnje:
Ako je ukupna ponuda manja od ukupne tražnje uvodi se uslovno(fiktivno) mjesto
ponude (fiktivna vrsta u tabeli) čija je ponuda jednaka razlici između ukupne tražnje
I
ukupne
ponude
tj:
am+1 = Σbj - Σai
Kad dodamo uslovnu ponudu ili tražnju moramo definisati i troškove. Cij=0 jer taj
potrošač ne postoji ali upisujemo taj višak u polje uslovnog potrošača I to je višak koji
će ostati na skladištu I to polje smatramo zauzetim da bi uslov m+n-1 bio zadovoljen
ali na kraju ne možemo komentarisati da smo poslali tu količinu nekom nego
kažemo da na nekom skladištu postoji višak ponude (odnosno višak tražnje u
obrnutom slučaju).
*Degeneracija
Rješenje u kojem nema m+n-1 bazičnih promjenljivih odnosno popunjenih polja
tabele ne zadovoljava neophodan uslov za primjenu nekog od metoda optimizacije.
Ovakav slučaj se javlja kada je
parcijalna
suma ponude jednaka nekoj od
parcijalnih
suma tražnje. Takav slučaj se predstavlja degeneraciju transportnog problema a
takvo rješenje smatramo degenerativnim.
Degeneracija transportnog problema može da se javi prilikom određivanja :
1)
Početnog
bazičnog
rješenja
2) U postupku poboljšavanja nekog problema transporta u proceduri optimizacije.
su okarakterisane dužinom. Dužina grane može biti: dužina puta, vrijeme putovanja,
transportni troškovi, pouzdanost itd. Ako se sa P označi proizvoljan konačan skup
elemenata pi, a sa K skup svih (nije obavezno svih) uređenih parova kij=(pi, pj), koji su
sastavljeni od različitih elemenata skupa P, tada skupovi P I K posmatrani zajedno
definišu transportnu mrežu. Par (P,K), dva skupa P I K, određuje potpuno jednu
transportnu mrežu.
Tjemena transportne mreže mogu biti:
-tjemena
proizvodnje
-tjemena
potrošnje
-tranzitna tjemena
U tjemenima proizvodnje veličina pi je pozitivna, u tjemenima potrošnje je
negativna a u tranzitnim tjemenima jednaka je nuli.
Elementi kij=(pi,pj) skupa K, nazivaju se komunikacije transportne mreže.
Komunikacija kod koje je jedan te isti punkt I početni I završni naziva se petlja.
Mreža
može
biti
-orjentisana
(označen
pravac
kretanja)
-neorjentisana
(ne
znamo
đe
se
što
prevozi)
-mješovita
Za svaku komunikaciju su vezana dva broja:
1)Propusna moć (dij) koja pokazuje kolika je maximalna količina robe koja se može
prevesti tom komunikacijom (ta vrijednost nije uvijek data)
2)Troškovi prevoza (cij) jedinica robe koja se transportuje iz jednog punkta u drugi
komunikacijom
(uvijek
dati)
(ako je na komunikaciji napisan samo jedan br to su uvijek troškovi!)
Transportna mreža se može prikazati I u obliku kvadratne matrice u kojoj svakom
punktu transportne mreže odgovara jedna vrsta I jedna kolona. Vrste matrice A
pokazuju u koja tjemena mreže je moguć prevoz iz tjemena koja odgovaraju datoj vrsti
a kolone pokazuju koje se komunikacije završavaju u dotičnom tjemenu mreže. Na
glavnoj dijagonali matrice transportne mreže uvijek se nalaze nule, zato što ne postoje
komunikacije koje polaze I završavaju se se u istim tjemenima.
65. x
66. x
67. x
68. x
69. Matrične igre sa mješovitim strategijama.
Strana 317. u knjizi. Ako matrična igra nema sedlastu tačku, tj. Ako pri optimalnim
strategijama za igrača A i igrača B, maximin vrijednost (maksimalni minimalan dobitak
za igrača A) i minimax vrijednost (minimalni maximalni gubitak igrača B) NISU jednaki
onda se ne radi više o prostoj matričnoj igri koja ima sedlastu tačku i čije rješenje se lako
nalazi. Ukoliko se igrači ponašaju racionalno , onda u želji da bolje prodju, tj. Da
povećaju svoj dobitak odnosno smanje svoj gubitak će u nizu poteza birati više
strategija. Vazno je reci da je vrijednost igre uvijek izmedju minimax i maximin
vrijednosti, što znači da igrač A može imati dobitak veći od minimalnog a igrač B
gubitak manji od maximalnog. Opredjeljivanje za izbor različitih strategija od strane
igrača A i B realizuje se slučajnim izborom, odnosno sa određenom vjerovatnoćom pri
čemu jedan slučajan izbor različitih strategija predstavlja tzv.
Mješovitu strategiju
(kombinacija različitih vjerovatnoća sa kojima će igrači u uzastopnom nizu poteza igrati
pojedine strategije koje im stoje na raspolaganju.) Za igrača A mješovita strategija
predstavlja se vektorom x = (x1,x2,...,xm) čiji elementi pokazuju vjerovatnoće sa kojima
igrač A primjenjuje pojedine strategije. Suma svih tih vjerovatnoća je jednaka jedinici. I
sansa za svaku strategiju da bude izabrana je veća ili jednaka nuli. Ako je veća od nule
onda je to
aktivna strategija.
Isto važi i za igrača B čija mješovita strategija je vektor y=(y1,y2,...,yn). Pri svakoj
odabranoj strategiji dobitak/gubitak zavise od vjerovatnoća x i y, i od matrice plaćanja,
te vrijednost igre možemo predstaviti formulom 5.5 iz knjige tj:
V= f (x,y) = (suma i=1 do m) (suma i=1 do n) aij xi yj
Ili vektorski
V= f (x,y) = xPy’
Primjer u knizi na str 219.
70. Rješavanje mješovitih matričnih igara.
Vrijednost igre ovdje je
prosječan
dobitak, odnosno gubitak za igrača A/B. Kao i u
prethodnom pitanju, svaki igrač ponašajući se racionalno pokušava da svede svoj
dobitak na maximalan nivo , tj. Gubitak na minimalan nivo. Različite vrste mješovitih
igara, zavisno od vrste i dimenzije matrice plaćanja, rješavaju se na različite načine. Npr.
Igre u kojima jedan igrač raspolaže sa 2 strategije, a drugi sa 2 ili više, tj. Sa konačnim
brojem strategija se mogu riješiti analitički i grafički. To su matrice reda 2x2, 2xn ili
mx2...Ako je m veće od 2 , a takodje i n veće od 2 onda pokušavamo da uprostimo
matricu u oblik pogodan za grafičko i analitičko rješavanje, ako ne može onda
rješavamo korišćenjem modela LP. Ovo je suština odgovora na ovo pitanje, zbog
nepogodnosti pisanja formula savjetujem da ipak pogledate u knjizi, nema tu puno...
71. Rješavanje igre reda 2x2
teorije. Matrica mx2 se odnosi na igrača B, tj. Grafički tražimo omega minimalno, tj.
Minimalan gubitak na osnovu kojih biramo optimalne strategije sa strane igrača A,
dobijamo matricu 2x2 i rješavamo analitički.
73. x
74. x
