1
SADRŽAJ
Uvod………………….……………………………………………….3
1. Standardni probmem maksimuma…………………………………….4
2. Dancigovi kriterijumi………………………………………………….7
Zaključak……………………………………………………………..16
Literatura……………………………………………………………..17
2
Privredne aktivnosti se, u najvećem broju slučajeva, odvijaju u uslovima ograničenih
resursa. Svako ko učestvuje u toj aktivnosti želi da za sebe dođe do najboljeg mogućeh ishoda, da
na što bolji način, za sebe, iskoristi te ograničene resurse. To se postiže optimizacijom, gde se
može iskoristiti metod zasnovan na matematičkom modeliranju ekonomskih pojava. Jedan od
takvih metoda je metod
linearnog programiranja
.
Linearno programiranje je grana matematike koja se bavi problemom optimizacije sastava
unutar zadatih ograničenja. Uveo ju je Leonid Kantorovič kasnih 1930-ih godina kao metodu
rešavanja problema planiranja proizvodnje. U SAD-u je linearno programiranje razvijeno tokom
Drugog Svetskog rata prvenstveno za probleme vojne logistike, kao što je optimiziranje prevoza
vojske i opreme. Danas metod lineranog programiranja razvija se u bogatu matematičku oblast
koja se i dalje razvija i primenjuje se u raznim oblastima nauke.
Proizvođač želi da odredi kako iskoristiti ograničene količine sirovina uz najveći profit,
poslovođa kako rasporediti zadati posao između svojih zaposlenih tako da bude napravljen u
najkraćem mogućem vremenskom periodu. Cilj ovih problema je optimizacija, maksimiziranje
korisnosti ili minimiziranje troškova uz zadata ograničenja što se rešava linearnim
programiranjem. Područje primene linearnog programiranja je široko: proizvodnja, transport i
distribucija, marketing, telekomunikacije, financijsko ulaganje i planiranje, raspored zaposlenika.
Formulirati realni životni problem kao problem linearnog programiranja zahteva timski rad
stručnjaka iz više područja. Pretpostavke koje moraju biti zadovoljene da bi određeni model
predstavljao model linearnog programiranja su:
1) Linearnost – podrzumeva postojanje lineanih zavisnosti između promenjivih u zadatku
linearnog programiranja. Ova prepostavka je zadovoljena tako što su fukcija cilja i sistemi
ograničenja izraženi lineranim fukcijama u modelu linearnog programiranja.
2) Izvesnost
– svi parametri modela su unapred jednoznačno određeni, što znači da su
koeficijenti funkcije cilja i sistema ograničenja deterministički određeni i ne menjaju se u
toku rešavanja
3) Deljivost
– podrazumeva da promenljive u modelu ne moraju biti celi brojevi već mogu
biti izražene i u obliku decimalnih brojeva
4) Nenegativnost
– ova pretpostavka ima svoj metodološki i ekonomski značaj.
Metodološki
– kako je opšti algoritam rešavanja modela (simpleks metod), to je za
njegovu primenu neophodno zadovoljenje uslova nenegativnosti.
Ekonomski
– kako promenljive u modelu predstavljaju ekonomske veličine one ne mogu
biti negativne.
Problem linearnog programiranja može biti maksimizacija i minimizacija određene
fukcije, odnosno nalaženje optimalne linearne fukcije,pod uslovom koji su predstavljeni
sistemom nejednačina.
4
a
11
x
1
a
12
x
2
… a
1
n
x
n
+
x
n
+
1
=
b
1
a
21
x
1
a
22
x
2
… a
2
n
x
n
+
x
n
+
2
=
b
1
. . . .
. . . .
a
m
1
x
1
a
m
2
x
2
… a
mn
x
n
+
x
n
+
m
=
b
m
x
1
, x
2
… , x
n
+
m
≥
0
Uvedene dodatne promenljive osim metodološke uloge u pretvaranju sistema nejednačina
u sistem jednačina, imaju veoma ogroman ekonomski značaj prilikom rešavanja zadatka
linearnog programiranja jer pozitivne vrednosti dodatnih promenljivih pokazuju iznos
neiskorišćenih resursa, odnosno kapaciteta (
b
1
,
b
2
… , b
n
)
u trenutku kada su vrednosti realnih
promenjivih (
x
1
,
x
2
… , x
n
)
optimalne. Zbog toga, uslov nenegativnosti važi za kako realne tako i
za dodatne promenjive.
Osim u sistemu ograničenja dodatne promenljive se uvode u funkciju cilja
F
, nakon čega
će kompletan oblik standardnog problema maksimuma biti:
(
max
)
F
=
c
1
x
1
c
2
x
2
… . c
n
x
n
+
0
x
n
+
1
+
0
x
n
+
2
+
… .
0
x
n
+
m
a
11
x
1
a
12
x
2
… a
1
n
x
n
+
x
n
+
1
=
b
1
a
21
x
1
a
22
x
2
… a
2
n
x
n
+
x
n
+
2
=
b
1
. . . .
. . . .
a
m
1
x
1
a
m
2
x
2
… a
mn
x
n
+
x
n
+
m
=
b
m
x
1
, x
2
… , x
n
≥
0
Znači, imamo
n
realnih (osnovnih) promenjivih i
m
dodatnih promenljivih. Dodatne
promenljive u funkciju cilja
F
su uvedene sa nultim vrednostima koeficijenata, tj.
c
n
+
1
=
c
n
+
2
=
…
=
c
n
+
m
=
0
što znači da se u funkciju cilja uvode isključivo iz metodoloških
razloga. Ako prihvatimo da je
c
n
+
m
=
0
, problem možemo izraziti u kraćem obliku na sledeći
način:
(
max
)
F
=
∑
j
=
0
n
c
j
x
j
∑
j
=
0
n
a
ij
x
j
=
b
i
5
(
i
=
1,2
, … , m
)(
j
=
1,2
, … , m
)
x
j
≥
0.
odnosno u matričnom obliku:
(
max
)
F
=
c
T
x
Ax
=
b
x ≥
0
x
- vektor kolona promenljivih,
c
– vektor vrsta koeficijenata funkcije cilja n-tog reda,
A
– matrica koeficijenata sistema ograničenja reda (m,n),
b
– vektor kolona slobodnih članova ograničenja m-tog reda.
Način, odnosno oblik na koji smo formulisali standardni problem maksimuma nazivamo
još i kanonski oblik zadatka linearnog programiranja. Kanonski oblik standardnog problema
maksimuma glasi:
Fukcija cilja:
F
=
[
c
1
c
1
… c
n
+
m
]
x
1
x
2
.
.
.
.
x
n
+
m
Sistem ograničenja:
a
11
a
12
… a
1
n
1 0
…
0
a
21
.
.
.
.
¿
¿
a
m
2
¿
a
mn
0 0
…
0
¿
x
1
x
2
.
.
.
.
x
n
+
m
=
b
1
b
2
.
.
.
.
b
m
x
1
, x
2
… , x
n
+
m
≥
0
Zapažamo da matrica A pored koeficijenata uz realne promenjive nalaze i koeficijenti uz
dodatme promenjive, i zajedno formiraju jediničnu
blok matricu
:
1
A
n
+
1
=
0
0
,
0
A
n
+
2
=
1
0
0
, … , A
n
+
m
=
1
0
