Download Linearno programiranje PDF

TitleLinearno programiranje
File Size421.5 KB
Total Pages66
Table of Contents
                            1. Konstrukcija matematickih modela
2. Matematicki model opsteg problema linearnog programiranja
3. Geometrijska interpretacija problema linearnog programiranja
4. Opsti oblik problema linearnog programiranja i njegova svojstva
5. Standardni oblik linearnog programiranja i njegova bazna resenja
6. Geometrijska interpretacija simpleks metode
7. Kanonski oblik linearnog programiranja i odredjivanje pocetnog baznog resenja
8. Kritetijum optimalnosti, ulaska i izlaska promenljive iz baze
9. Odredjivanje novog kanonskog oblika i novog dopustivog resenja
10. Vestacka pocetna baza
11. Dualni model problema linearnog programiranja, pravila za formiranje duala
12. Moguci ishodi simpleks metode
13. Jaka i slaba dualnost
14. Komplementarnost optimalnih resenja primala i duala
15. Model ZTP i OTP i njihove osobine
16. Metode za odredjivanje polaznog dopustivog resenja transportnog problema
17. Metoda potencijala i njeno tumacenje preko teorije dualnosti
18. Transportni zadaci sa ogranicenim propusnim osobinama
19. Minimizacija vremena transporta
20. Izbor izvrsilaca aktivnosti projekta
21. Optimizacija zeleznickog transporta
22. Model dvofaznog transporta (izbor lokacije)
23. Primena linearnog programiranja u planiranju ishrane-osnovini model
24. Model za podelu obradive povrsine na kulture
25. Model linearnog programiranja za optimizaciju plana setve na dislociranim njivama
26. Model linearnog programiranja za optimizaciju proizvodnje krmnih smesa
27. Model linearnog programiranja za optimizaciju sastava punjenja kupolne peci
28. Model linearnog programiranja za optimizaciju transporta proizvodnje
29. Model linearnog programiranja za izbor optimalnog asortimana za slucaj ogranicenja vise kategorija resursa
30. Model linearnog programiranja za optimizaciju utroska materijala
31. Primena linearnog programiranja u uskladjivanju programa proizvodnje
32. Primena linearnog programiranja na upravljanje zalihama
33. Opsta postavka i klasifikacija zadatka nelinearnog programiranja (lokalni i globalni ekstremum)
34. Bezuslovna optimizacija Odredjivanje stacionarnih tacaka
35. Klasicni problem uslovnog ekstremuma Metoda eliminacije promenljivih
36. Klasicni problem uslovnog ekstremuma Metoda Lagranzovih mnozilaca
37. Opsti slucaj nelinearnog programiranja Metode izravnavajucih funkcija
38. Konveksnost skupa i funkcija Ispitivanje konveksnosti funkcije Problem konveksnog programiranja
39. Kun-Takerova teorema
40. Metode kaznenih funkcija Spoljasnje i unutrasnje kaznene funkcije
41. Metode bezuslovne optimizacije (priblizne)
42. Celobrojno programiranje Neki karakteristicni zadaci celobrojnog programiranja
                        
Document Text Contents
Page 2

Нема предаје! ИЗДРЖИ!
Prekucana Maksina skripta!

Srecno! Nema predaje!!!

Pun je kurac indeksa, postoji mogucnost greske u kucanju!

Pitanja:

1. Konstrukcija matematickih modela.....................................................................4

2. Matematicki model opsteg problema linearnog programiranja...........................5

3. Geometrijska interpretacija problema linearnog programiranja..........................5

4. Opsti oblik problema linearnog programiranja i njegova svojstva.......................8

5. Standardni oblik linearnog programiranja i njegova bazna resenja.....................9

6. Geometrijska interpretacija simpleks metode..................................................10

7. Kanonski oblik linearnog programiranja i odredjivanje pocetnog baznog resenja
.............................................................................................................................. 10

8. Kritetijum optimalnosti, ulaska i izlaska promenljive iz baze.............................11

9. Odredjivanje novog kanonskog oblika i novog dopustivog resenja....................12

10. Vestacka pocetna baza....................................................................................13

11. Dualni model problema linearnog programiranja, pravila za formiranje duala14

12. Moguci ishodi simpleks metode......................................................................15

13. Jaka i slaba dualnost........................................................................................16

14. Komplementarnost optimalnih resenja primala i duala...................................17

15. Model ZTP i OTP i njihove osobine...................................................................17

16. Metode za odredjivanje polaznog dopustivog resenja transportnog problema19

17. Metoda potencijala i njeno tumacenje preko teorije dualnosti........................24

18. Transportni zadaci sa ogranicenim propusnim osobinama..............................26

19. Minimizacija vremena transporta....................................................................27

20. Izbor izvrsilaca aktivnosti projekta..................................................................27

21. Optimizacija zeleznickog transporta................................................................28

22. Model dvofaznog transporta (izbor lokacije)....................................................28

23. Primena linearnog programiranja u planiranju ishrane-osnovini model...........29

24. Model za podelu obradive povrsine na kulture................................................29

25. Model linearnog programiranja za optimizaciju plana setve na dislociranim
njivama................................................................................................................. 30

-2-

Page 33

Нема предаје! ИЗДРЖИ!

19. Minimizacija vremena transporta
U nizu transportnih zadataka kvalitet organizacije transporta meri se utrosenim
vremenom za njegovo sporovodjenje.

ti
j

– vreme utroseno na transport porizvoda iz i-tog punkta proizvodnje u j-ti
punkt potrosnje

a
i

– proizvedena kolicina u Ai, i=1,2,…n

b
j

– potrebna kolicina u Bj, j=1,2,…,m

Zadatak se sastoji u odredjivanju plana transporta ǁxijǁ tj. skupa vrednosti xij (i=1,2,
…m; j=1,2,…n) za koje ce vreme t(x) najduzeg trajanja prevoza

t(x)=max{tij | xij>0 i=1,…,m
j=1,…,n}

postati minimalno pri skupu ogranicenja


j=1

n

xij≤ai i=1,

…,m


i=1

m

xij=bj j=1,

…,n
xij≥0

Funkcija cilja koja se minimizira predstavlja najduze vreme iz skupa vremena t ij
trajanja transporta iz bilo kog punkta Ai u punkt Bj gde su planirani transporti (xij>0).

20. Izbor izvrsilaca aktivnosti projekta

n – broj aktivnosti nekog projekta koje treba poveriti izvrsiocima i to tako da
svaki izvrsilac dobije samo po jednu aktivnost

cij – efikasnost i-tog izvrsioca na j-toj aktivnosti

Vrednosti cij obrazuju kvadratnu tablicu efikasnosti izvrsenja projekta. Izbor bilo koje
kolone ili vrste iz te tablice odredjuje neki plan raspodele aktivnosti na izvrsioce, dok
izbor broja koji se nalazi na preseku i-te vrednosti i j-te kolone ima znacenje da i-ti
izvrsilac radi na j-toj aktivnosti projekta.

Zadatak se sastoji u nalazenju plana raspodele aktivnosti na izvrsioce, odnosno u
izboru izvrsilaca kako bi bila obezbedjena najbolja ukupna efikasnost izvrsenja
projekta.

-33-

Page 34

Нема предаје! ИЗДРЖИ!

(max) f(x)= ∑
i=1

n


j=1

n

cijxij

(min) f*(x)=-f(x)= ∑
i=1

n


j=1

n

(-

cij)xij
Svaki izvrsilac moze biti zaposlen na jednoj i samo jednoj aktivnosti:


i=1

n

xij=1 j=1,

…,n
Na svakoj aktivnosti moze raditi jedan i samo jedan izvrsilac:


j=1

n

xij=1 i=1,

…,n
U slucaju transportnog problema u otvorenom obliku mogu nastupiti analogne
situacije, koje se ispoljavaju u narusavanju ravnoteze izmedju broja izvrsilaca i broja
aktivnosti projekta. Tako da ako je broj izvrsilaca m veci od broja aktivnosti n, tada
je sistem ogranicenja:


i=1

n

xij=1 j=1,

…,n


j=1

n

xij≤1 i=1,

…,n
xij≥0 i=1,…,m
j=1,…n

21. Optimizacija zeleznickog transporta
xi
j

– broj vagona j-tog tipa napunjenih i-tom robom

ai
j

– norma opterecenja jednog vagona j-tog tipa napunjenog i-tom robom

ai – kolicina robe koju treba transportovati u tonama
b
j

– raspolozivi broj vagona j-tog tipa

ci
j

– eksploatacioni rashodi koji nastaju usled transporta i-te robe na jednom
vagonu j-tog tipa

Funkcija cilja F odredjuje minimalne ukupne troskove transporta:

-34-

Page 65

Нема предаје! ИЗДРЖИ!
Neki primeri problema celobrojnog programiranja

Problem rasporedjivanja Rasporediti n ljudi na n poslova, svakog na po jedan
posao, tako da produktivnost bude najveca. Poznata je produktivnost cij i-tog coveka
na j-tom poslu za i,j∈{1,…,n}.

Model predstavlja problem binarnog programiranja:

max ∑
i=1

n


j=1

n

cijxij


i=1

n

xij=1

j=1,…,n


j=1

n

xij=1

i=1,…,n
xij∈{0,1}

Pritom je xij=1 ako i samo ako je i-ti covek rasporedjen na j-ti posao.

Transportni problem Treba transportovati robu iz skladista S1,…,Sm do kupca K1,
…,Kn tako da se zadovolji traznja a da cena transporta bude minimalna. Poznate su
zalihe na skaldistima: a1,…,am, potraznje kupaca b1,…,bn i cena wij transporta jednog
komada robe od Si do Kj za i=1,…,m, j=1,…,n.

min ∑
i=1

m


j=1

n

wijxij


i=1

m

xij=bj

j=1,…,n


j=1

n

xij=ai

i=1,…,n
xij≥0
xij∈Z

ai – zalihe na skladistima
bj – potraznje kupaca
wi
j

– cena transporta jednog komada robe
od Si do Kj

-65-

Similer Documents