U članku [1] opisan je problem jednostavne razdiobe ulaganja uz razmatranje nekoliko ilustrativnih primjera rješavanja toga problema. U njemu smo razmatrali problem razdiobe određene veličine na određene kategorije prema određenim uvjetima, pri čemu su sve kategorije bile međusobno ravnopravne, tj. niti jedna od njih nije bila preferirana u odnosu na bilo koju drugu. Stoga su komponente vrijednosti optimalnoga rješenja praktički bile zavisne samo o pripadnim koeficijentima u funkciji cilja, te o konačnim podskupovima skupa nenegativnih cijelih brojeva koji su bili definirani prema tzv. prirodnim uvjetima.

 

U ovom ćemo članku razmatrati odabrane primjene problema složene razdiobe ulaganja i način njihovih rješavanja primjenom metoda i tehnika dinamičkoga programiranja. Problem složene razdiobe ulaganja predstavlja svojevrsno poopćenje problema jednostavne razdiobe ulaganja. Temeljna razlika u odnosu na problem jednostavne razdiobe ulaganja jest što je svakoj pojedinoj kategoriji (npr. gospodarskoj grani, tvrtki, odjelu unutar iste tvrtke i sl.) pridružen tzv. težinski koeficijent. To konkretno znači da pri razdiobi ukupnoga novčanog iznosa na određene kategorije te kategorije nisu međusobno ravnopravne, nego rangirane prema nekom kriteriju. Pritom ne nužno postoji jedinstvena najbolje rangirana kategorija i/ili jedinstvena najslabije rangirana kategorija. Točnije, pretpostavljamo da postoje barem dvije kategorije s različitim rangovima jer se u suprotnom problem složene razdiobe ulaganja svodi na problem jednostavne razdiobe ulaganja. (Ekvivalentno, možemo reći da su u problemu jednostavne razdiobe ulaganja težinski koeficijenti unimorfno raspodijeljeni, dok su u problemu složene razdiobe ulaganja prilagođeni.)

 

U rješavanju problema složene razdiobe ulaganja također je pogodno primijeniti iste metode i tehnike dinamičkoga programiranja koje se primjenjuju u rješavanju problema jednostavne razdiobe ulaganja, ali uz neke neznatne preinake. Stoga su problem jednostavne razdiobe ulaganja i problem složene razdiobe ulaganja primjeri različitih klasa problema koji se rješavaju istim matematičkim metodama i tehnikama. Te se klase smatraju različitima (preciznije, neizomorfnima) zbog već spomenutog rangiranja kategorija. Slične primjere različitih klasa problema koji se rješavaju istim metodama susrećemo već i u srednjoj školi: npr. sustav jedne linearne jednadžbe s dvije nepoznanice i jedne kvadratne jednadžbe s dvije nepoznanice najprikladnije je riješiti metodom zamjene (supstitucije), a ista se metoda – kako nam je dobro poznato još iz osnovne škole – primjenjuje i npr. u rješavanju sustava dviju linearnih jednadžbi s dvije nepoznanice.

 

Odmah istaknimo uobičajenu „zamku" vezanu uz spomenuto rangiranje kategorija. Naime, posve se pogrešno smatra da kategorija s boljim rangom (tj. s većim težinskim koeficijentom) nužno ima i veću optimalnu vrijednost. Kako ćemo vidjeti u Primjeru 1., (naj)bolje rangirana kategorija uopće se ne mora pojaviti u optimalnom rješenju. U Primjeru 2. vidjet ćemo da se u optimalnom planu pojavljuju vrijednosti pridružene najboljoj i najslabije rangiranoj kategoriji, dok se srednje rangirana kategorija uopće ne pojavljuje u tom planu. Slobodno možemo reći da optimalna vrijednost pridružena pojedinoj kategoriji zavisi o pripadnom koeficijentu u funkciji cilja i o pripadnom težinskom koeficijentu.

 

Težinski koeficijenti u pravilu su unaprijed zadane strogo pozitivne realne konstante. Međutim, oni mogu biti zadani i kao funkcije. U Primjeru 3. težinski koeficijent pridružen jednoj kategoriji zadan je upravo na taj način, tj. kao tablično definirana funkcija. U Primjerima 4. i 5. vidjet ćemo kako nam težinski koeficijenti mogu bitno „smanjiti“, odnosno „povećati“ skupove nenegativnih cijelih brojeva koji su određeni tzv. prirodnim uvjetima koje moraju zadovoljavati vrijednosti pojedine varijable u matematičkom modelu. Takve „promjene“ nisu karakteristične za problem jednostavne razdiobe ulaganja, pa je to još jedna od važnih suštinskih razlika ovih dviju klasa problema.

 

Kad god to bude moguće, isti primjer riješit ćemo i analitički i pomoću računalnoga programa WinQSB [1]. U gotovo svim primjerima (osim Primjera 3.) provest ćemo i dodatnu što-ako analizu u kojoj ćemo – koristeći navedeni računalni program – ispitati osjetljivost optimalnoga rješenja u odnosu na promjene početnih uvjeta na pojedine komponente. Ta se analiza često rabi prigodom rješavanja problema iz gospodarske i tehničke prakse jer stjecajem različitih okolnosti može doći do naknadnih promjena početnih uvjeta.

 

Standardno označavamo:

 

[n] := {1, 2, …, n} – skup prvih n prirodnih brojeva;

[n]₀ := {0, 1, …, n} – skup prvih n + 1 elemenata skupa N₀ := {0, 1, 2, … }.

 

Primjer 1. [2], a montažom jednog objekta tipa B ostvaruje se dobit od 12 n.j. Pri montaži obaju tipova objekata koristi se posebna oprema čiji je ukupni raspoloživi kapacitet 10 komada. Za montažu jednoga objekta tipa A potrebna su 2 komada, a za montažu jednog objekta tipa B 3 komada te opreme. Tvrtka Muljažić – gradnja d.o.o. želi ostvariti maksimalnu dobit istodobnom montažom objekata obaju navedenih tipova, pri čemu je dopušteno da pojedini tip objekta uopće ne bude montiran i da ne bude korištena sva raspoloživa posebna oprema.

 

a) Odredimo matematički model promatranoga problema.

b) Nađimo optimalan plan montaže.

c) Ispitajmo kako na optimalan plan montaže utječe poseban ugovor kojim se tvrtka obvezuje da će montirati najmanje jedan, a najviše tri objekta tipa A.

 

Matematički model: Ovaj primjer pripada u opći problem razdiobe ulaganja jer dijelimo ukupan raspoloživi kapacitet dodatne opreme na dva dijela prema određenim kriterijima i uz ostvaraj određenoga cilja (maksimizacije ukupne dobiti). Označimo s x₁ ukupan broj objekata tipa A, a s x₂ ukupan broj objekata tipa B koje će tvrtka montirati. Ukupna dobit od montaže jednoga objekta tipa A iznosi 8 n.j., pa ukupna dobit od montaže x₁ objekata tipa A iznosi  8 × x₁ n.j. Analogno, ukupna dobit od montaže x₂ objekata tipa B iznosi 12 × x₂. Prema tome, ukupna dobit koja se dobije montažom obaju tipova objekata iznosi:

 

f (x₁, x₂) = 8 × x₁ + 12 × x₂.

 

Nadalje, ako za montažu jednog objekta tipa A tvrtka treba dva komada posebne opreme, onda za istodobnu montažu x₁ objekata tipa A tvrtka treba 2 × x₁ komada posebne opreme. Potpuno analogno, za istodobnu montažu x₂ objekata tipa B potrebno je 3 × x₂ komada posebne opreme. Budući da ukupan broj komada posebne opreme ne smije premašiti raspoloživi kapacitet, mora vrijediti nejednakost

 

2 × x₁  + 3 × x₂ \(\leq\)10.

 

Prema prirodi postavljenoga problema, x₁ i x₂ moraju biti nenegativni cijeli brojevi, jer broj montiranih komada ne može biti niti decimalan broj niti negativan broj, tj.

 

x_i Î N₀, za i = 1, 2.

 

Dakle, traženi matematički model je:

 

maksimizirati f(x₁, x₂) = 8 × x₁ + 12 × x₂

pod uvjetima

2 × x₁  + 3 × x₂ \(\leq\)10

x_i Î N₀, za i = 1, 2.

 

Napomena 1. U prvom od navedenih dvaju uvjeta prirodni brojevi 2 i 3 su ranije spomenuti težinski koeficijenti.  Iz tog uvjeta možemo „očitati" da su objekti tipa B „vrjedniji" prema kriteriju potrebne dodatne opreme jer je za montažu jednoga od njih potrebno više dodatne opreme nego za montažu jednoga objekta tipa A.  Da za jedan objekt svakoga od spomenutih dvaju tipova treba jednaka količina dodatne opreme, oba bi tipa objekata imala jednaki rang i problem bismo mogli svesti na problem jednostavne razdiobe ulaganja.

 

Napomena 2. Drugi uvjet možemo zamijeniti strožijim uvjetima: x₂ \(\in\) [5]₀, x₂ \(\in\) [3]₀ jer je iz prirode razmatranoga problema razvidno da ukupan broj montiranih objekata tipa A ne može biti strogo veći od 5, dok ukupan broj montiranih objekata tipa B ne može biti strogo veći od 3. (Navedene rezultate formalno dobijemo rješavajući nejednadžbe \(2 \cdot x_1 \le 10 \) i \(3\cdot x_2 \le 10\) u skupu N₀.) Takvo „postroženje“ uvjeta vrlo je korisno za analitičko rješavanje zadatka, dok za rješavanje zadatka pomoću računalnoga programa WinQSB formalno nije nužno, ali je korisno radi „ubrzanja“ rada programa.

 

Analitičko rješenje: Stavimo S = [10]₀, pa za svaki s Î S računajmo vrijednosti funkcija

 

f₁(s) = \(\mathop {\max }\limits_{0 \le 2 \cdot {x_1} \le s} (8 \cdot {x_1}) = \mathop {\max }\limits_{0 \le {x_1} \le \frac{s}{2}} (8 \cdot {x_1})\)

f₂(s) = \(\mathop {\max }\limits_{0 \le 3 \cdot {x_2} \le s} \left[ {12 \cdot {x_2} + {f_1}(s - 3 \cdot {x_2})} \right] = \mathop {\max }\limits_{0 \le {x_2} \le \frac{s}{3}} \left[ {12 \cdot {x_2} + {f_1}(s - 3 \cdot {x_2})} \right]\)

 

Prva funkcija računa optimalnu dobit u slučaju kad se sva raspoloživa posebna oprema koristi isključivo za montiranje objekata tipa A, a druga funkcija računa optimalnu dobit kad se sva raspoloživa posebna oprema koristi za montažu obaju tipova objekata. Budući da je dozvoljeno ne iskoristiti svu raspoloživu posebnu opremu, računaju se vrijednosti obiju funkcija za svaki s \(\in\) [10]₀.

Vrijednosti navedenih funkcija računamo potpuno analogno kao i u problemima jednostavne razdiobe ulaganja (vidjeti [1], [3], [4] ili [7]). Pripadnu optimalnu vrijednost varijable x₁ označavamo uobičajeno s \(x_1^*\). Radi ilustracije postupka, navodimo izračun vrijednosti  f₁(9) i f₁(10) :

 

f₁(9) = \(\mathop {\max }\limits_{0 \le 2 \cdot {x_1} \le 9} (8 \cdot {x_1}) = \mathop {\max }\limits_{0 \le {x_1} \le \frac{9}{2}} (8 \cdot {x_1})\) = (u segmentu [0, \(\frac{9}{2}\)] nalazi se točno pet cjelobrojnih vrijednosti: 0, 1, 2, 3 i 4) = max {8 × 0, 8 × 1, 8 × 2, 8 × 3, 8 × 4} =  32 (pripadna optimalna vrijednost varijable x₁ iznosi \(x_1^*\) = 4);

f₁(10) = \(\mathop {\max }\limits_{0 \le 2 \cdot {x_1} \le 10} (8 \cdot {x_1}) = \mathop {\max }\limits_{0 \le {x_1} \le 5} (8 \cdot {x_1})\) = max {8 × 0, 8 × 1, 8 × 2, 8 × 3, 8 × 4, 8 × 5} =  40 (pripadna optimalna vrijednost varijable x₁ iznosi \(x_1^*\) = 5).

 

Izračunom svih 11 vrijednosti funkcije  f₁ dobivamo sljedeću tablicu:

 

Tablica 1. Vrijednosti funkcije f₁

 

U sljedećem koraku za svaki s Î S  računamo vrijednosti funkcije f₂(s) koristeći Tablicu 1. Pripadnu optimalnu vrijednost varijable x₂ označavamo s \(x_2^*\). Radi ilustracije postupka, navodimo izračun f₂(9) i f₂(10):

 

f₂(9) = \(\mathop {\max }\limits_{0 \le 3 \cdot {x_2} \le 9} \left[ {12 \cdot {x_2} + {f_1}(9 - 3 \cdot {x_2})} \right] = \mathop {\max }\limits_{0 \le {x_2} \le 3} \left[ {12 \cdot {x_2} + {f_1}(9 - 3 \cdot {x_2})} \right]\) = max {12 × 0 + f₁(9 – 3 × 0), 12 × 1 + f₁(9 – 3 × 1), 12 × 2 + f₁(9 – 3 × 2), 12 × 3 + f₁(9 – 3 × 3)} = max {0 + f₁(9), 12 + f₁(6), 24 + f₁(3), 36 + f₁(0)} = max {0 + 32, 12 + 24, 24 + 8, 36 + 0} = 36 (pripadne optimalne vrijednosti varijable x₂ su \({(x_2^*)_1} = 1\) i \({(x_2^*)_2} = 3\));

f₂(10) = \(\mathop {\max }\limits_{0 \le 3 \cdot {x_2} \le 10} \left[ {12 \cdot {x_2} + {f_1}(10 - 3 \cdot {x_2})} \right] = \mathop {\max }\limits_{0 \le {x_2} \le \frac{{10}}{3}} \left[ {12 \cdot {x_2} + {f_1}(10 - 3 \cdot {x_2})} \right]\) = (u segmentu [0, \(\frac{{10}}{3}\)] nalaze se četiri cjelobrojne vrijednosti: 0, 1, 2 i 3) = max {12 × 0 + f₁(10 – 3 × 0), 12 × 1 + f₁(10 – 3 × 1), 12 × 2 + f₁(10 – 3 × 2), 12 × 3 + f₁(10 – 3 × 3)} = max {0 + f₁(10), 12 + f₁(7), 24 + f₁(4), 36 + f₁(1)} = max {0 + 40, 12 + 16, 24 + 16, 36 + 0} = 40 (pripadne optimalne vrijednosti varijable x₂ su \({(x_2^*)_1}\)= 0 i \({(x_2^*)_2}\)= 2).

 

Izračunom svih 11 vrijednosti funkcije f₂ dobivamo sljedeću tablicu:

 

Tablica 2. Vrijednosti funkcije f₂

 

Dakle, optimalna dobit iznosi f₂(10) = 40 n.j. i postiže se za \(x_2^*\) = 0 ili \(x_2^*\) = 2. Stoga postoje dva moguća optimalna plana montaže:

Plan 1. \(x_2^*\) = 0 znači da se ne predviđa montaža niti jednog objekta tipa B. Pripadna optimalna vrijednost funkcije f₁ je f₁(10 –  3 × 0) = f₁(10) = 40, a postiže se za \(x_1^*\) = 5. Prema tome, treba montirati točno pet objekata tipa A.

 

Plan 2. \(x_2^*\) = 2 znači da treba montirati dva objekta tipa B. Pripadna optimalna vrijednost funkcije f₁ je f₁(10 –  3 × 2) = f₁(4) = 16, a postiže se za \(x_1^*\) = 2. U ovom slučaju, dakle, treba montirati po dva objekta svakoga tipa.

Analiza osjetljivosti rješenja na dodatan uvjet:  Činjenicu da prema posebnom ugovoru tvrtka treba montirati najmanje jedan, a najviše tri objekta tipa A, možemo zapisati u obliku nejednakosti:

 

\( 1 \le x_1 \le 3. \)

 

Možemo očekivati da ćemo kao optimalno rješenje dobiti Plan 2. jer dobiveno optimalno rješenje iz toga plana zadovoljava gornji dodatni uvjet. U ovom slučaju Tablica 1. izgleda ovako:

 

Tablica 3. Vrijednosti funkcije f₁ uz dodatan uvjet

 

U odnosu na prvotno analitičko rješenje, tj. Tablicu 1., rezultati se mijenjaju jedino za s Î {8, 9, 10}, pa se dodatnim izračunom vrijednosti funkcije f₂ za te vrijednosti varijable s dobiva:

 

Tablica 4. Vrijednosti funkcije f₂ uz dodatan uvjet.

 

Prema očekivanju, dobili smo \(x_1^*\) = \(x_2^*\) = 2, tj. Plan 2.

 

Rješenje pomoću programa WinQSB: Problem složene razdiobe ulaganja svodi se na ograničen cjelobrojni problem naprtnjače [3], u kojem je količina svakog predmeta ograničena nekom cjelobrojnom vrijednosti. Ukratko podsjetimo na formulaciju toga problema:

 

Lopov ima naprtnjaču čija je najveća dopuštena nosivost M kg. Iz trgovine može ukrasti n₁ komada namirnice N₁ čija je masa m₁, n₂ komada namirnice N₂ čija je masa m₂ itd. [4] Za svaki i \(\in\) [n] neka su x_i i v_i redom broj, odnosno vrijednost [5] ukradenih komada namirnice N_i. Kako napuniti naprtnjaču da ukupna masa svih ukradenih namirnica ne bude veća od M kg i da ukupna vrijednost svih ukradenih namirnica bude što veća? [6]

 

Promatrani problem naprtnjače možemo opisati sljedećim matematičkim modelom:

 

maksimizirati \(f({x_1},...,{x_n}) = \sum\limits_{i = 1}^n {{v_i} \cdot {x_i}} \)  

pod uvjetima

\(\begin{array}{l}\sum\limits_{i = 1}^n {{m_i} \cdot {x_i}}  \le M,\\{x_i} \in \left\{ {0,...,{n_i}} \right\}{\rm{, za svaki }}i \in \left[ n \right].\end{array}\)

Iz matematičkoga modela Primjera 1., te Napomena 1. i 2., slijedi da su problem iz Primjera 1. i ograničeni cjelobrojni problem naprtnjače međusobno izomorfni problemi [7]. Konkretno, u Primjeru 1. „ulogu“ namirnica N₁ i N₂ imaju objekti tipa A i B, „ulogu“ masa namirnica imaju komadi posebne opreme potrebni za montažu jednoga objekta, dok „ulogu“ vrijednosti namirnica imaju ukupne dobiti od montaže objekata. Lako se vidi da se matematički model Primjera 1. dobije tako da se u gornji model problema naprtnjače uvrsti i = 2, m₁ = 2, m₂ = 3, M = 10, v₁ = 8, v₂ = 12, n₁ = 5 i n₂ = 3.

Pokrenimo potprogram DP programa WinQSB. Lijevom tipkom miša kliknimo na izbornik File i odaberimo opciju New Problem. U dobivenom dijaloškom okviru lijevom tipkom miša kliknimo na kružić pored natpisa Knapsack Problem, pa u pravokutnik pored natpisa Problem Title upišimo Primjer 1, a u pravokutnik pored natpisa Number of Items upišimo 2 (jer imamo dva tipa objekata). Dobivamo Sliku 1.

 

Slika 1.  Unos naziva i broja objekata u Primjeru 1.

 

Lijevom tipkom miša kliknimo na OK. U sljedećem koraku unosimo ulazne podatke:

 

–  u drugi stupac (Item Identification) upisujemo nazive tipova objekata: A i B;

–  u treći stupac (Units Available) trebali bismo upisati koliko nam je maksimalno objekata kojega tipa na raspolaganju, ali te brojeve ne znamo. Sukladno Napomeni 2, riješimo nejednadžbe \(2\cdot x_1 \le 10\) i \(3\cdot x_2 \le 10\) u skupu N₀, pa dobivamo \(x_1\le 5\)  i \(x_2\le 3\). To znači da ne možemo montirati više od 5 objekata tipa A i više od 3 objekta tipa B, pa u ovaj stupac upisujemo 5 i 3.

– u četvrti stupac (Unit Capacity Required) upisujemo težinske koeficijente koji množe veličine x₁ i x₂ u uvjetu iz matematičkoga modela. To su brojevi 2 i 3, pa u četvrti stupac upisujemo redom 2 i 3.

–  u peti stupac (Return Function (X: Item ID)) upisujemo komponente funkcije cilja koje odgovaraju svakom pojedinom objektu, a to je zapravo dobit od montaže svakoga pojedinog objekta. Dakle, upisujemo redom: 8*X i 12*X.

–   u posljednji redak (Capacity=) upisujemo kapacitet raspoložive opreme, tj. 10.

 

Ovime je unos ulaznih podataka završen. Dobivamo Sliku 2.

 

Slika 2. Unos ulaznih podataka u Primjeru 1.

 

Lijevom tipkom miša kliknimo na izbornik Solve and Analyze, pa odaberimo opciju Solve the Problem. Dobivamo Sliku 3.

 

Slika 3. Izlazni podatci u Primjeru 1.

 

Iz trećega stupca dobivene tablice (Decision Quantity (X)) očitavamo optimalan plan montaže: treba montirati po dva objekta svakoga tipa. Dakle, riječ je o Planu 2. dobivenom u analitičkom rješenju.

 

Napomena 3. Plan 1. dobiven analitičkim rješenjem nije moguće dobiti pomoću potprograma DP. Naime, iako taj potprogram dopušta mogućnost tzv. što–ako analize (engl.: What-If Analysis) u kojoj se unaprijed može zadati optimalna vrijednost jedne od varijabli, nije dopušten unos nule kao optimalne vrijednosti bilo koje varijable, pa nije moguće dobiti Plan 1.

 

Primjer 2. Tvrtka Muljarević–gradnja d.o.o. istodobno treba montirati tri tipa objekata: A₁, A₂ i A₃. Pri montaži svih tipova objekata koristi se posebna oprema čiji je ukupni kapacitet 18 komada. Osnovni podaci o broju potrebnih komada posebne opreme i dobiti za izradu svakoga pojedinog tipa opreme navedeni su u Tablici 5.

 

Tablica 5. Ulazni podatci za Primjer 2.

 

Odlukom uprave tvrtke dopuštena je istodobna montaža najviše tri objekta tipa A₁ i pet objekata tipa A₃. Dopušteno je da pojedini tip objekta ne bude montiran, te da ne bude iskorištena sva posebna oprema. Treba napraviti optimalan plan montaže tako da ukupna ostvarena neto–dobit bude maksimalna.

 

a) Odredimo matematički model promatranoga problema.

b) Nađimo optimalan plan montaže.

 

Matematički model: Za svaki i \(\in\) [3] neka je x_i broj objekata tipa A_i koji će biti montirani. Tada ukupna dobit od montaže objekata tipa A₁ iznosi 8 × x₁ n.j., ukupna dobit od montaže objekata tipa A₂ 12 × x₂ n.j., a ukupna dobit od montaže objekata tipa A₃ 10 × x₃ n.j. Stoga ukupna dobit od montaže svih triju tipova objekata iznosi:

 

f(x₁, x₂, x₃) = 8 × x₁ + 12 × x₂ + 10 × x₃.

 

Za montažu x₁ objekata tipa A₁ potrebno je ukupno 4 × x₁ komada posebne opreme, za montažu x₂ objekata tipa A₂ potrebno je ukupno 6 × x₂ komada posebne opreme, a za montažu x₃ objekata tipa A₃ potrebno je ukupno 3 × x₃ komada posebne opreme. Budući da ukupan broj potrebnih komada posebne opreme ne može premašiti ukupan kapacitet posebne opreme, mora vrijediti nejednakost:

 

\(4\cdot x_1 + 6 \cdot x_2 + 3\cdot x_3 \le 18\).

 

Nadalje, budući da je istodobno moguće montirati najviše tri objekta tipa A₁ i najviše pet objekata tipa A₃, moraju vrijediti nejednakosti:

 

x₁ \(\in\) [3]₀, x₃ \(\in\) [5]₀.

 

Primijetimo da zbog cjelobrojnosti i nenegativnosti vrijednosti varijable x₂ iz nejednakosti     4 × x₁ + 6 × x₂ + 3 × x₃ \leq18 slijedi x₂\in [3]₀. Prema tome, traženi matematički model je:

 

maksimizirati f(x₁, x₂, x₃) = 8 × x₁ + 12 × x₂ + 10 × x₃

pod uvjetima

\(4\cdot x_1 + 6 \cdot x_2 + 3\cdot x_3\le 18\)

x₁, x₂ Î [3]₀,

x₃ Î [5]₀.

 

Analitičko rješenje: Stavimo S = [18]₀, pa za svaki s Î S računajmo vrijednosti sljedećih funkcija:

 

f₁(s) = \(\mathop {\max }\limits_{\scriptstyle0 \le 4 \cdot {x_1} \le s\atop\scriptstyle0 \le {x_1} \le 3} (8 \cdot {x_1}) = \mathop {\max }\limits_{0 \le {x_1} \le \min \left\{ {\frac{s}{4},{\rm{ }}3} \right\}} (8 \cdot {x_1})\)

f₂(s) = \(\mathop {\max }\limits_{\scriptstyle0 \le 6 \cdot {x_2} \le s\atop\scriptstyle0 \le {x_2} \le 3} \left[ {12 \cdot {x_2} + {f_1}(s - 6 \cdot {x_2})} \right] = \mathop {\max }\limits_{0 \le {x_2} \le \min \left\{ {\frac{s}{6},{\rm{ }}3} \right\}} \left[ {12 \cdot {x_2} + {f_1}(s - 6 \cdot {x_2})} \right]\)

f₃(s) = \(\mathop {\max }\limits_{\scriptstyle0 \le 3 \cdot {x_3} \le s\atop\scriptstyle0 \le {x_3} \le 5} \left[ {10 \cdot {x_3} + {f_2}(s - 3 \cdot {x_3})} \right] = \mathop {\max }\limits_{0 \le {x_3} \le \min \left\{ {\frac{s}{3},{\rm{ }}5} \right\}} \left[ {10 \cdot {x_3} + {f_2}(s - 3 \cdot {x_2})} \right]\)

 

Funkcija f₁ računa optimalnu neto–dobit ako se s komada posebne opreme koristi isključivo za montažu objekata tipa A₁. Funkcija f₂ računa optimalnu neto–dobit ako se s komada posebne opreme koristi isključivo za montažu objekata tipa A₁ i A₂. Funkcija f₃ računa optimalnu neto–dobit ukoliko se s komada opreme koristi za montažu svih triju tipova objekata.

 

U prvom koraku dobivamo Tablicu 6.

 

 

Tablica 6. Vrijednosti funkcije f₁ u Primjeru 2.

 

u drugom koraku Tablicu 7.

 

Tablica 7. Vrijednosti funkcije f₂ u Primjeru 2.

 

a u trećem koraku Tablicu 8.

 

 

 

Tablica 8. Vrijednosti funkcije f₃ u Primjeru 2.

 

Prema tome, optimalna dobit je f₃(18) = 52 n.j. i postiže se za \(x_3^*\) = 4, što znači da treba montirati ukupno četiri objekta tipa A₃. Pripadna optimalna vrijednost funkcije f₂ je f₂(18 – 3 × 4) = f₂(6) = 12 koja se postiže za \(x_2^*\)  = 1, pa treba montirati jedan objekt tipa A₂. Napokon, pripadna optimalna vrijednost funkcije f₁ je f₁(6 – 6 × 1) = f₁(0) = 0 i postiže se za \(x_1^*  = 0\), pa ne treba montirati niti jedan objekt tipa A₁. Dakle, optimalan plan montaže je montirati jedan objekt tipa A₂ i četiri objekta tipa A₃ uz maksimalnu neto–dobit 52 n.j.

 

Rješenje pomoću programa WinQSB: Navodimo samo ulazne parametre prema kojima se rješenje ovoga problema razlikuje od rješenja Primjera 1.:

 

–        Problem Title: Primjer 2

–        Number of Items: 3

–        Item Identification: A1, A2, A3

–        Units Available: 3, 3, 5 (jer se mogu montirati najviše tri objekta tipa A₁, odnosno tipa A₂ i najviše pet objekata tipa A₃)

–        Unit Capacity Required: 4, 6, 3

–        Return Function (X: Item ID): 8*X, 12*X, 10*X

–        Capacity = 18

 

Rješavanjem problema u drugom stupcu (Decision Quantity) dobivamo vrijednosti 0, 1 i 4, pa „očitavamo'' da treba montirati točno jedan objekt tipa A₂ i četiri objekta tipa A₃. Ukupna optimalna dobit od montaže svih triju objekata (Total Return Value) iznosi 52 n.j.

 

Napomena 5: U ovome je slučaju zgodno provesti što – ako analizu, pa npr. istražiti kako će se promijeniti optimalni plan odlučimo li montirati točno jedan objekt tipa A₁. U tu svrhu iskoristimo rezultat dobiven programom WinQSB. Kliknemo lijevom tipkom miša na ikonicu What If, pa u presjeku retka A1 i stupca Preset Decision upišimo 1. Ovim smo zapravo unaprijed definirali odluku da želimo montirati točno jedan objekt tipa A₁.[8] Iz tablice na desnoj strani toga okvira „očitamo'' da, uz navedeni dodatni uvjet, treba montirati jedan objekt tipa A₁ i četiri objekta tipa A₃. Dakle, postavljanje dodatnoga uvjeta izazvalo je smanjenje optimalne vrijednosti varijable x₂, a nije utjecalo na optimalnu vrijednost varijable x₃.

 

Primjer 3. Brodom treba prevesti dvije vrste robe: A i B. Dobit po jednom komadu robe A iznosi 40 n.j., a dobit po jednom komadu robe B 60 n.j. Jedan komad robe B zauzima pet kub. jed.brodskoga prostora [9]. Roba A zauzima brodski prostor u zavisnosti o količini utovarene robe prema Tablici 9.:

 

Tablica 9. Zavisnost obujma brodskoga prostora o količini utovarene robe A

 

Obujam dijela broda namijenjenog za prijevoz robe iznosi 20 kub. jed. Komadi obiju vrsta robe su nedjeljivi. Moguće je ne prevesti niti jedan komad pojedine vrste robe, te ne iskoristiti sav obujam dijela broda namijenjenog za prijevoz robe. Treba napraviti optimalan plan utovara robe A i B tako da se ostvari maksimalna dobit.

 

a) Odredimo matematički model promatranoga problema.

b) Nađimo optimalan plan utovara broda i iznos maksimalne dobiti.

 

Matematički model: Neka je x_A količina utovarene robe vrste A, a x_B količina utovarene robe vrste B. Tada ukupna dobit ostvarena prijevozom robe vrste A iznosi 40 × x_A n.j., a ukupna dobit ostvarena prijevozom robe vrste B iznosi 60 × x_B n.j. Prema tome, ukupna dobit ostvarena prijevozom obiju vrsta roba iznosi

 

f(x_A, x_B) = 40 × x_A + 60 × x_B.

 

Označimo s O_A(x) funkciju koja količini robe A pridružuje potreban obujam brodskoga prostora. Funkcija O_A(x) je definirana tablično (Tablicom 9.) i najveća vrijednost njezina argumenta iznosi 6. To znači da se brodom može prevesti najviše šest komada robe A, pa zbog prirodne cjelobrojnosti vrijednosti x_A vrijedi uvjet:

 

x_A Î [6]₀.

 

S druge strane, vrijednost varijable B je također nenegativna i cjelobrojna. Da bismo izbjegli postavljanje „slaboga“ uvjeta x_B Î N₀, uočimo da iz podatka da jedan komad robe B zauzima pet kub.jed. i iz podatka da obujam dijela broda namijenjenoga za prijevoz robe iznosi 20 kub. jed. slijedi da na brod ne možemo utovariti strogo više od četiri komada robe B, tj. uvjet na vrijednost varijable x_B  možemo postrožiti na sljedeći uvjet:

 

x_B Î [4]₀.

 

Preostaje još uvjetom iskazati podatak da ukupan obujam utovarene robe ne može biti strogo veći od obujma dijela broda namijenjenog za prijevoz robe. Ukupan obujam x_A komada robe A iznosi O_A(x_A), a ukupan obujam x_B komada robe B iznosi 5 × x_B, pa mora vrijediti nejednakost:

 

\(O_A(x_A) + 5\cdot x_B \le 20\).

 

Dakle, traženi matematički model promatranoga problema je:

 

maksimizirati f(x_A, x_B) = 40 × x_A + 60 × x_B

pod uvjetima

\(O_A(x_A) + 5\cdot x_B \le 20\).

x_A Î [6]₀,

x_B Î [4]₀.

 

Rješenje: Odmah napomenimo da, zbog tabličnoga definiranja funkcije ovisnosti obujma brodskoga prostora o količini robe A, ovaj problem nije moguće riješiti primjenom programa WinQSB jer taj program zahtijeva definiranje navedene funkcije analitičkim izrazom (formulom). Stavimo S = [20]₀, pa za svaki s Î S računajmo vrijednosti funkcija:

f₁(s) = \(\mathop {\max }\limits_{0 \le {O_A}({x_A}) \le s} (40 \cdot {x_A})\)

f₂(s) = \(\mathop {\max }\limits_{\scriptstyle0 \le 5 \cdot {x_B} \le s\atop\scriptstyle0 \le {x_B} \le 4} \left[ {60 \cdot {x_B} + {f_1}(s - 5 \cdot {x_B})} \right] = \mathop {\max }\limits_{0 \le {x_B} \le \min \left\{ {\frac{s}{5},{\rm{ }}4} \right\}} \left[ {60 \cdot {x_B} + {f_1}(s - 5 \cdot {x_B})} \right]\)

 

Funkcija f₁(s) računa optimalnu dobit ako se svih s kub. jed. prostora namijenjenog za prijevoz robe iskoristi isključivo za prijevoz robe vrste A, dok funkcija f₂(s) računa optimalnu dobit ako se taj prostor iskoristi za prijevoz obiju vrsta roba.

 

Radi ilustracije postupka, prikazujemo izračun vrijednosti funkcija f₁ i f₂ za s = 17 i s = 20:

 

f₁(17) = \(\mathop {\max }\limits_{0 \le {O_A}({x_A}) \le 17} (40 \cdot {x_A})\) = max {40 × 0, 40 × 1, 40 × 2, 40 × 3, 40 × 4, 40 × 5} = 200;

f₂(17) = \(\mathop {\max }\limits_{0 \le {x_B} \le \frac{{17}}{5}} \left[ {60 \cdot {x_B} + {f_1}(17 - 5 \cdot {x_B})} \right]\) = max{60 × 0 + f₁(17), 60 × 1 + f₁(12), 60 × 2 + f₂(7),     60 × 3 + f₂(2)} = max{0 + 200,  60 + 160, 120 + 40, 180 + 0} = 220;

f₁(20) = \(\mathop {\max }\limits_{0 \le {O_A}({x_A}) \le 18} (40 \cdot {x_A})\) = max {40 × 0, 40 × 1, 40 × 2, 40 × 3, 40 × 4, 40 × 5, 40 × 6} = 240;

f₂(20) = \(\mathop {\max }\limits_{0 \le {x_B} \le 4} \left[ {60 \cdot {x_B} + {f_1}(20 - 5 \cdot {x_B})} \right]\) = max{60 × 0 + f₁(20), 60 × 1 + f₁(15), 60 × 2 + f₂(10),     60 × 3 + f₂(5), 60 × 4 + f₂(0)} = max{0 + 240,  60 + 200, 120 + 120, 180 + 40, 240 + 0} = 260.

 

Izračunom svih vrijednosti funkcija f₁ i f₂ dobiva se Tablica 10.:

 

s	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
f1(s)	0	0	0	0	0	40	40	40	80	80	120	120	160	160	160	200	200	200
\(x_A^*\)	0	0	0	0	0	1	1	1	2	2	3	3	4	4	4	5	5	5
f2(s)	0	0	0	0	0	60	60	60	80	80	120	120	160	160	160	200	200	220
\(x_B^*\)	0	0	0	0	0	1	1	1	0	0	0, 2	0, 2	0	0	0	0	0	1

 

s	18	19	20
f1(s)	240	240	240
\(x_A^*\)	6	6	6
f2(s)	240	240	260
\(x_B^*\)	0	0	1

Tablica 10. Vrijednosti funkcija f₁ i f₂.

Prema tome, optimalna dobit je f₂(20) = 260 i postiže se za \(x_B^*\) = 1. Odgovarajuća optimalna vrijednost funkcije f₁ je f₁(20 – 5 × 1) = f₁(15) = 200 i postiže se za \(x_A^*\) = 5. Dakle, optimalan plan prijevoza robe je prevesti pet komada robe vrste A i jedan komad robe vrste B.

 

Primjer 4. Zrakoplovom nosivosti 83 tone treba prevesti tri vrste robe čije su jedinične mase i jedinične dobiti od prijevoza naveden u sljedećoj tablici.

 

Tablica 11. Ulazni podatci za Primjer 4.

 

Komadi svih triju vrsta robe su nedjeljivi. Treba napraviti plan utovara svih triju vrsta robe tako da se ostvari maksimalna dobit.

 

a) Odredimo matematički model promatranoga problema.

b) Nađimo optimalan plan utovara i odgovarajuću maksimalnu dobit.

 

Matematički model: Neka su x_A količina utovarene robe vrste A, x_B količina utovarene robe vrste B i x_C količina utovarene robe vrste C. Tada ukupna dobit od prijevoza robe vrste A iznosi 96 × x_A, ukupna dobit od prijevoza robe vrste B iznosi 85 × x_B, a ukupna dobit od prijevoza robe vrste C iznosi 50 × x_C. Stoga je ukupna dobit od prijevoza svih triju vrsta roba

 

f(x_A, x_B, x_C) = 96 × x_A + 85 × x_B + 50 × x_C.

 

Nadalje, ukupna masa x_A komada robe vrste A iznosi 24 × x_A tona, ukupna masa x_B komada robe vrste B iznosi 22 × x_B tona, a ukupna masa x_C komada robe vrste C iznosi 16 × x_C tona. Ukupna masa svih triju vrsta robe ne smije biti strogo veća od nosivosti zrakoplova, što znači da mora vrijediti uvjet:

 

24 × x_A + 22 × x_B + 16 × x_C \(\le\) 83.

 

Prema prirodi problema, sve tri vrijednosti x_A, x_B i x_C su nenegativni cijeli brojevi. Kao i u prethodnim primjerima, međutim, možemo postupiti „lukavije“, pa uočiti da iz nejednakosti

 

\(24\cdot x_A \le 83\),

\(22\cdot x_B \le 83\),

\(16\cdot x_C \le 83\),

slijedi

 

x_A, x_B \(\in\) [3]₀,

x_C \(\in\) [5]₀,

 

Dakle, traženi matematički model promatranoga problema je:

maksimizirati f(x_A, x_B, x_C) = 96 × x_A + 85 × x_B + 50 × x_C

pod uvjetima

24 × x_A + 22 × x_B + 16 × x_C \(\le\) 83

x_A, x_B \(\in\) [3]₀,

x_C \(\in\) [5]₀,

 

Analitičko rješenje: Prepuštamo ga čitatelju.

 

Rješenje pomoću računalnoga programa WinQSB: Navodimo samo parametre prema kojima se rješenje ovoga primjera razlikuje od prethodno navedenih rješenja:

–        Problem Title: Primjer 4

–        Number of Items: 3

–        Item Identification: A, B, C

–        Units Available:  3, 3, 5.

–        Unit Capacity Required: 24, 22, 16

–        Return Function (X: Item ID): 96*X, 85*X, 50*X

–        Capacity = 83

 

Nakon pokretanja procedure Solve and Analyze u stupcu Decision Quantity  „očitavamo'' vrijednosti 0, 3 i 1. Dakle, optimalan plan utovara je: utovariti tri komada robe B i jedan komad robe C. Ukupna optimalna dobit (Total Return Value) iznosi 305 n.j.

 

I ovdje možemo provesti što–ako analizu, pa promotriti kako na dobiveno optimalno rješenje utječe npr. dodatni uvjet da se mora prevesti točno jedan komad robe A. U tom je slučaju optimalni plan utovara: utovariti po jedan komad robe svake od vrsta A i B, te točno 2 komada robe vrste C. Dakle, postavljanje dodatnoga uvjeta uzrokuje promjenu obiju optimalnih vrijednosti: optimalna vrijednost x_B se smanjila, dok se optimalna vrijednost x_C povećala.

 

Primjer 5. Zrakoplovom nosivosti 50 tona na određenoj se liniji mogu prevoziti putnici, poštanske pošiljke i ostali teret. Prosječna masa i dobit ostvarena po jedinici transporta navedeni su u donjoj tablici.

 

Tablica 12. Ulazni podatci za Primjer 5.

 

U zrakoplov se može smjestiti najviše 120 putnika. Treba odrediti optimalnu strukturu transporta tako da se ostvari maksimalna dobit. Formirajmo odgovarajući matematički model, pa odredimo traženu optimalnu strukturu.

 

Matematički model: Neka su x₁ broj putnika, x₂ broj poštanskih paketa i x₃ broj paketa drugoga tereta koji će se prevoziti zrakoplovom. Ukupna dobit ostvarena prijevozom x₁ putnika iznosi 2 × x₁ [000 n.j.], ukupna dobit ostvarena prijevozom x₂ poštanskih paketa iznosi 2.5 × x₂ [000 n.j.], a ukupna dobit ostvarena prijevozom x₃ paketa ostaloga tereta je 4.5 × x₃ [000 n.j.]. Stoga ukupna dobit nastala prijevozom svih triju kategorija tereta iznosi:

 

  f (x₁, x₂, x₃) = 2 × x₁ + 2.5 × x₂ + 4.5 × x₃.

 

Nadalje, ukupna masa svih x₁ putnika iznosi 0.085 × x₁ tona, ukupna masa x₂ poštanskih paketa iznosi 0.2 × x₂ tona, a ukupna masa x₃ paketa ostaloga tereta je 0.9 × x₃ tona. Budući da ukupna masa svih triju vrsta tereta ne smije biti strogo veća od nosivosti zrakoplova, mora vrijediti nejednakost:

 

0.085 × x₁ + 0.2 × x₂ + 0.9 × x₃ \(\le\) 50.

 

Analogno kao u prethodnim primjerima, iz navedene nejednakosti slijedi:

 

x₁ \(\in\) [588]₀,

x₂ \(\in\) [250]₀,

x₃ \(\in\) [56]₀.

 

Međutim, zbog podatka da se u zrakoplov može smjestiti najviše 120 putnika, prvi uvjet moramo preinačiti u:

 

x₁ \(\in\) [120]₀,.

 

Tako matematički model promatranoga problema glasi:

 

maksimizirati  f (x₁, x₂, x₃) = 2 × x₁ + 2.5 × x₂ + 4.5 × x₃

pod uvjetima

0.085 × x₁ + 0.2 × x₂ + 0.9 × x₃ \(\le\) 50

x₁ \(\in\) [120]₀,

x₂ \(\in\) [250]₀,

x₃ \(\in\) [56]₀.

 

Analitičko rješenje: Zbog opsežnosti ga izostavljamo.

 

Rješenje pomoću programa WinQSB: Navodimo samo parametre prema kojima se rješenje ovoga primjera razlikuje od ranije navedenih rješenja:

 

–        Problem Title: Primjer 5

–        Number of Items: 3

–        Item Identification: putnici, poštanski paket, ostali teret

–        Units Available: opet postupimo lukavo, pa u skupu N riješimo nejednadžbe 0.2 × x₂\(\le\) 50 i 0.9 × x₃ \(\le\) 50  i dobivamo: x₂ \(\le\)250, x₃ \(\le\) 55. Stoga u ovaj stupac upisujemo: 120, 250, 55.

–        Unit Capacity Required: 0.085, 0.2, 0.9

–        Return Function (X: Item ID): 2*X, 2.5*X, 4.5*X

–        Capacity = 50

 

Nakon pokretanja procedure Solve and Analyze u stupcu Decision Quantity „očitavamo'' vrijednosti 120, 199 i 0. Dakle, optimalnu strukturu transporta tvori 120 putnika i 199 poštanskih paketa uz ukupnu optimalnu dobit (Total Return Value) 737.50 [000 n.j.], odnosno 737 500 n.j.

 

Postavimo li npr. dodatni uvjet da moramo prevesti i točno jedan paket ostaloga tereta, što–ako analizom dobivamo sljedeću optimalnu strukturu transporta: 120 putnika, 194 poštanska paketa i 1 paket ostaloga tereta. Dakle, postavljanje dodatnog uvjeta nije utjecalo na optimalan broj putnika u optimalnoj strukturi transporta, ali je smanjilo optimalan broj poštanskih paketa u optimalnoj strukturi transporta.

 

 

 

 

Zaključak

 

Ovim primjerom završavamo razmatranje problema složene razdiobe ulaganja. Primijetimo da smo u rješavanju gotovo svakoga primjera zapravo preinačili originalni matematički model (koji je proizašao iz formulacije problema), a s ciljem što jednostavnijega i bržega iznalaženja optimalnoga rješenja. Takve preinake u rješavanju problema jednostavne razdiobe ulaganja u pravilu nisu moguće, odnosno praktički se pojavljuju jedino u naknadnim što-ako analizama. Također, u Primjerima 1. i 2. iz članka [1] mogli smo unaprijed naslutiti optimalno rješenje (koristeći npr. pohlepni algoritam). No, pri rješavanju problema složene razdiobe ulaganja optimalno rješenje u pravilu ne možemo unaprijed naslutiti, pa treba izbjegavati procjenjivanje vrijednosti njegovih komponenti (čemu su rješavači problema nerijetko vrlo skloni).

 

Zbog mogućnosti pojave najmanje dvaju optimalnih planova (vidjeti Primjer 1.), od kojih računalnim programom možemo dobiti točno jedno, u praksi treba nastojati što je više moguće kombinirati oba izložena načina rješavanja. Rješavanje samo pomoću računalnoga programa treba primijeniti ponajviše u slučajevima poput Primjera 5. kad je provedba analitičkoga načina rješavanja tehnički relativno složena i spora.  

 

LITERATURA:

 

[1.]      T. Strmečki i B. Kovačić: Kvantitativne metode odlučivanja – problem jednostavne razdiobe ulaganja, Math.e Vol. 19, Zagreb, 2011.

[2.]      M.J. Beckmann: Dynamic Programming of Economic Decisions, Springer–Verlag, New York, 1968.

[3.]      R.Bellman: Dynamic Programming, Dover Publications, 2003.

[4.]      D. Kalpić, V. Mornar: Operacijska istraživanja, ZEUS, Zagreb, 1996.

[5.]      L. Neralić: Uvod u matematičko programiranje 1, Element, Zagreb, 2003.

[6.]      J. Petrić: Operaciona istraživanja, Nauka, Beograd, 1997.

[7.]      J. Petrić et.al.: Operaciona istraživanja – zbirka rešenih zadataka, Nauka, Beograd, 1996.

[8.]      H. Kellerer,U. Pferschy,D. Pisinger: Knapsack problems, Springer, 2004.

[9.]      S. Martello, P. Toth: Knapsack problems, Wiley, 1990.

 

DODATAK

 

U Dodatku navodimo još nekoliko primjera iz klase problema složene razdiobe ulaganja, a u čijem se rješavanju primjenjuju metode i tehnike dinamičkoga programiranja. Ti se primjeri rješavaju na potpuno analogan način kao i Primjeri 1. – 5., pa njihovo rješavanje prepuštamo čitatelju. U svakom pojedinom primjeru osobitu pozornost treba posvetiti formiranju matematičkoga modela razmatranoga problema jer je to najvažnija (i najteža) faza u procesu rješavanja zadatka. Kad god je to moguće, preporučujemo riješiti primjer i analitički i pomoću računalnoga programa WinQSB.

 

 

Zadatak 1. Brodski teret tvore četiri različita artikla. Jedinična masa i jedinična dobit za svaki pojedini artikl navedeni su u sljedećoj tablici.

 

 

Ukupna masa brodskoga tereta može biti najviše 9 tona. Niti jedan komad svake vrste robe

nije moguće podijeliti na manje dijelove. Treba naći optimalan plan utovara kojim se postiže maksimalna dobit.

 

a) Formirajte matematički model promatranoga problema.

b) Nađite optimalan plan utovara i odgovarajuću maksimalnu dobit.

c) Ako je optimalna količina nekog artikla jednaka nuli, istražite kako njeno povećanje za 1 komad utječe na optimalne količine ostalih artikala.

 

Rezultati: Neka su x_A, x_B, x_C i x_D redom količine artikala A, B, C i D.

 

a) Matematički model glasi:

 

maksimizirati \(z=50\cdot x_A + 120\cdot x_B +170\cdot x_C + 80\cdot x_D\)

pod uvjetima

\(2\cdot x_A+4\cdot x_B+ 5\cdot x_C+3\cdot x_D \le 9\),

x_A, x_B, x_C, x_D \(\in\)  N₀.

 

b) \(\left( {x_A^*,x_B^*,x_C^*,x_D^*} \right) = (0,1,1,0)\), tj. optimalan plan je utovariti po točno jedan komad svakoga od artikala B i C. Pripadna optimalna dobit iznosi z* = 290 n.j.

 

c) Za \(x_A^* = 1\)ili \(x_D^* = 1\) dobivamo \(\left( {x_A^*,x_B^*,x_C^*,x_D^*} \right) = (1,1,0,1)\), pa zaključujemo da ispunjenjem dodatnog zahtjeva optimalna količina artikla B ostaje nepromijenjena, dok se optimalna količina artikla C smanji za jedan komad.

 

Zadatak 2. Brodom se prevoze dvije vrste robe: A i B.  Po komadu prevezene robe A ostvaruje se dobit od 40 n.j., a po komadu prevezene robe B dobit od 60 n.j. Nadalje, 1 komad robe A ima obujam 3 kub. jed., a 1 komad robe B obujam 5 kub. jed. Obujam brodskoga prostora previđenoga za prijevoz obiju vrsta robe iznosi 30 kub. jed. Niti jedan komad svake vrste robe nije moguće podijeliti na manje dijelove. Treba naći optimalan plan utovara broda navedenim vrstama robe tako da dobit ostvarena od prijevoza obiju vrsta roba bude maksimalna.

 

a) Formirajte matematički model promatranoga problema.

b) Nađite optimalan plan utovara i odgovarajuću maksimalnu dobit.

c) Riješite b) podzadatak uz uvjet da se brodom može prevesti najviše 6 komada robe A.

 

Rezultati: Neka su x_A i x_B redom količine robe A i B.

 

a) Matematički model glasi:

 

maksimizirati \(z= 40\cdot x_A+60\cdot x_B\)

pod uvjetima

\(3 \cdot x_A + 5\cdot x_B \le 30\),

x_A, x_B \(\in\) N₀.

 

b) \(\left( {x_A^*,x_B^*} \right) = (10,0)\), tj. optimalan plan je prevesti točno 10 komada robe A. Pripadna optimalna dobit iznosi z* = 400 n.j.

 

c)  \(\left( {x_A^*,x_B^*} \right) = (5,3)\), tj. novi optimalan plan je prevesti točno 5 komada robe A i točno 3 komada robe B. Pripadna optimalna dobit iznosi z* = 380 n.j.

 

Zadatak 3. Zrakoplovom nosivosti 85 tona treba prevesti tri vrste robe čije su jedinične mase i jedinične dobiti navedene u sljedećoj tablici:

 

 

Komade svih triju vrsta robe nije moguće razdijeliti na manje dijelove. Treba napraviti optimalan plan utovara robe tako da ukupna dobit bude maksimalna.

 

a) Formirajte matematički model promatranoga problema.

b) Nađite optimalan plan utovara i odgovarajuću maksimalnu dobit.

c) Nađite optimalan plan utovara uz dodatni uvjet da se mora prevesti najmanje jedan komad svake vrste robe.

 

Rezultati: Neka su x_A, x_B i x_C redom količine robe A, B i C.

 

a) Matematički model glasi:

 

maksimizirati \(z=64\cdot x_A+ 56\cdot x_B+ 60 \cdot x_C\)

pod uvjetima

\(14 \cdot x_A + 12 \cdot x_B + 13 \cdot x_C \le 85\),

x_A, x_B, x_C \(\in\)  N₀.

 

b) \(\left( {x_A^*,x_B^*,x_C^*} \right) = (0,6,1)\), tj. optimalan plan je prevesti točno 6 komada robe B i točno jedan komad robe C. Pripadna optimalna dobit iznosi z* = 396 000 €.

 

c) \(\left( {x_A^*,x_B^*,x_C^*} \right) = (1,1,4)\), tj. optimalan plan je: prevesti po točno jedan komad svake od roba A i B, te točno 4 komada robe C. Pripadna optimalna dobit iznosi z* = 360 000 €.

 

Zadatak 4. Tvrtka Smotalić–gradnja d.o.o. izvodi montažu dvaju tipova objekata: A i B. Montažom jednoga objekta tipa A ostvaruje se dobit od 10 n.j., a montažom jednoga objekta tipa B dobit od 12 n.j. Pri istodobnoj montaži obaju tipova objekata može se koristiti najviše 20 komada posebne vrste opreme, pri čemu za montažu jednoga objekta tipa A trebaju 4 komada opreme, a za montažu jednog objekta tipa B 3 komada opreme. Tvrtka želi istodobnim montiranjem objekata A i B ostvariti maksimalnu dobit.

 

a) Formirajte matematički model promatranoga problema.

b) Nađite optimalan plan montaže i odgovarajuću optimalnu dobit.

c) Ispitajte kako na optimalan plan montaže utječe poseban ugovor kojim se tvrtka obvezuje montirati barem 2, a najviše 5 objekata tipa A.

 

Rezultati: Neka su x_A i x_B redom brojevi („količine“) montiranih objekata tipa A i tipa B.

 

a) Matematički model glasi:

 

maksimizirati \(z= 10\cdot x_A +12 \cdot x_B\)

pod uvjetima

\(4\cdot x_A + 3\cdot x_B \le 20\),

x_A, x_B \(\in\) N₀.

 

b) \(\left( {x_A^*,x_B^*} \right) = (0,6)\), tj. optimalan plan je montirati samo točno 6 objekata tipa B. Pripadna optimalna dobit iznosi z* = 72 n.j.

 

c) \(\left( {x_A^*,x_B^*} \right) = (2,4)\), tj. optimalan plan je montirati točno 2 objekta tipa A i 4 objekta tipa B. Pripadna optimalna dobit iznosi z* = 68 n.j.

 

Zadatak 5. Tvrtka Gulikožić–gradnja d.o.o. raspolaže s kamionom nosivosti 45 jed. Tim kamionom treba prevesti dvije vrste tereta: A i B. Masa jednoga komada tereta A iznosi 5 jed., a dobit ostvarena njegovim transportom iznosi 6 n.j. Masa jednoga komada tereta B iznosi 3 jed., a dobit ostvarena njegovim transportom iznosi 4 n.j. Tvrtka želi prevesti što više tereta obiju vrsta tako da ukupna ostvarena dobit bude maksimalna.

 

a) Formirajte matematički model promatranoga problema.

b) Nađite optimalan plan prijevoza i odgovarajuću optimalnu ostvarenu dobit.

c) Ako je optimalna količina neke vrste tereta jednaka nuli, istražite kako njezino povećanje za 1 komad utječe na optimalnu količinu druge vrste tereta.

d) Riješite podzadatke a) i b) uz dodatni uvjet da se kamionom može prevesti najviše 5 komada tereta B.

 

Rezultati: Neka su x_A i x_B redom prevezene količine tereta A i tereta B.

 

a) Matematički model glasi:

 

maksimizirati \(z= 6\cdot x_A + 4\cdot x_B\)

pod uvjetima

\(5\cdot x_A + 3\cdot x_B \le 45\),

 \(x_A, x_B \in \mathbf{N}_0\).

 

b) \(\left( {x_A^*,x_B^*} \right) = (0,15)\), tj. optimalan plan prijevoza je prevesti samo točno 15 komada tereta B. Pripadna optimalna dobit iznosi z* = 60 n.j.

 

c) \(\left( {x_A^*,x_B^*} \right) = (1,13)\), pa povećanje optimalne količine tereta A za 1 komad uzrokuje smanjenje optimalne količine tereta B za 2 komada.

 

d) Matematički model glasi:

 

maksimizirati \(z = 6\cdot x_A + 4\cdot x_B\)

pod uvjetima

\(5\cdot x_A + 3\cdot x_B \le 45\),

x_A \(\in\) N₀, x_B \(\in\) [5]₀.

 

Rješavanjem se dobije \(\left( {x_A^*,x_B^*} \right) = (6,5)\), tj. optimalan plan prijevoza je prevesti točno 6 komada tereta A i točno 5 komada tereta B. Pripadna optimalna dobit iznosi z* = 56 n.j.