1.1
Pogled proizvo ¯
da ˇca
Odrediti koliko jedinica
x
j
proizvoda
j
=
1,2, . . . ,
n
treba proizvesti da
bi se ostvarila maksimalna dobit
ζ
.
ζ
=
n
∑
j
=
1
c
j
x
j
→
max
n
∑
j
=
1
a
i
,
j
x
j
≤
b
i
,
i
=
1,2, . . . ,
m
(1)
x
j
≥
0,
j
=
1,2, . . . ,
n
Problem (1) zovemo
problem linearnog programiranja
, za ovaj na-
ˇcin zadavanja kažemo da je
standardni oblik
.
2
Ako se za problem (2) uvedu veliˇcine „dodate vrednosti” jedinice si-
rovine
i
:
y
i
=
w
i
−
ρ
i
,
i
=
1,2, . . . ,
m
,
dobija se problem
ξ
=
m
∑
i
=
1
y
i
b
i
→
min
m
∑
i
=
1
y
i
a
i
,
j
≥
c
j
,
j
=
1,2, . . . ,
n
(3)
y
i
≥
0,
i
=
1,2, . . . ,
m
.
2
Primer
Fabrika proizvodi artikle A, B i C.
4
Za Proizvodnju artikla A treba 2 jedinice sirovine S1, 3 jedinice siro-
vine S2 i 4 jedinice sirovine S3. Za proizvod B treba redom 1, 3, 2
jedinice sirovina S1, S2 i S3. Za artikal C treba redom 3, 1, 4 jedinice
sirovina S1, S2 i S3. Na raspolaganju nam je 10 jedinica sirovine S1,
25 jedinica sirovine S2 i 30 jedinica sirovine S3 dnevno.
Artikal A se na mašini M1 obra¯duje 3 sata, a na mašini M2 4 sata. Ar-
tikal B se obra¯duje na mašini M1 4 sata i na mašini M2 3 sata. Artikal
C se obra¯duje na mašini M1 2 sata i na mašini M2 3 sata. Mašine M1
i M2 mogu biti istovremeno angažovane na jednom artiklu. Na jednoj
mašini se može obra¯divati samo jedan artikal u jednom momentu.
Cena jednog komada artikla A je 8 novˇcanih jedinica, artikla B je 5
novˇcanih jedinica, artikla C je 7 novˇcanih jedinica.
Koliko dnevno treba proizvoditi kojeg proizvoda, da bi zarada bila
maksimalna?
5
3
Rešenje problema linearnog programiranja
Za problem (1)
skup dopustivih vrednosti
S
je skup ure¯denih
n
-torki
(
x
1
,
x
2
, . . . ,
x
n
)
koje zadovoljavaju
n
∑
j
=
1
a
i
,
j
x
j
≤
b
i
,
i
=
1,2, . . . ,
m
x
j
≥
0,
j
=
1,2, . . . ,
n
.
Ure¯dena
n
-torka
(
x
1
,
x
2
, . . . ,
x
n
)
iz
S
za koju
funkcija dobiti
ζ
=
n
∑
j
=
1
c
j
x
j
ostvaruje maksimum je
rešenje problema
(1).
7
