Uvod

Do sada smo većinu problema formulirali kao klasično linearno programiranje (LP):

imamo jedan cilj (npr. maksimizirati profit, minimizirati trošak),
imamo skup klasičnih ograničenja (kapacitet, budžet, radno vrijeme…),
rješenje je ono koje najbolje optimizira jedan broj (funkciju cilja), uz uvjet da se sva ograničenja strogo poštuju.

U praksi, menadžerske odluke rijetko su tako jednostavne:

želimo maksimalan profit, ali istovremeno
želimo i stabilan rizik, zadovoljstvo zaposlenika, ekološku prihvatljivost, razuman broj projekata u tijeku itd.

Drugim riječima:

Umjesto jednog cilja imamo više ciljeva koji se međusobno sukobljavaju.
Umjesto jedne funkcije cilja imamo vektor ciljeva.

U tom trenutku “obični” LP više nije dovoljan. Trebaju nam alati koji:

dopuštaju da ciljeve postavimo kao mete (npr. “želim barem 15% povrata”),
ili da više ciljeva optimiziramo odjednom, umjesto da unaprijed izaberemo samo jedan.

Tu na scenu stupaju:

ciljno programiranje (goal programming, GP) i
višeciljno programiranje (multiobjective programming, MOLP)

(Tamiz, Jones & El-Darzi, 1995; Tamiz, Jones & Romero, 1998; Tanino, Tanaka & Inuiguchi (ur.), 2013; Sen & Nandi, 2012)

U ovoj lekciji:

prvo ćemo se kratko podsjetiti općeg zapisa LP modela,
zatim uvodimo ciljno programiranje kroz varijable odstupanja $d^+$ i $d^-$,
potom proširujemo priču na višeciljno programiranje (više ciljeva istovremeno, također kao ekstenziju LP-a),
i na kraju pokazujemo kako se sve to može primijeniti na konkretne slučajeve (kriptovalute, izbor tehnologija, sigurnost…).

Napomena o širem kontekstu

Ciljno i višeciljno programiranje u literaturi su puno širi pojmovi nego što ćemo ih mi obraditi u ovom kolegiju. Mogu se formulirati i za nelinearne modele, pa čak i rješavati heuristikama i evolucijskim algoritmima.

U ovoj ćemo se lekciji ograničiti na linearne modele i promatrati ciljno i višeciljno programiranje kao ekstenzije prvenstveno linearnog programiranja. To znači da:

svi naši primjeri ostaju linearni (kao u klasičnom LP-u),
dodajemo im nove koncepte (varijable odstupanja, više ciljeva, težine),
koristimo standardne LP solve-re (poput lpSolve u R-u)
u pravilu, varijable odluke će biti kontinuirane, ali mogu biti i cjelobrojne ili binarne.

Za one koje zanima više, ciljno i višeciljno programiranje možete kasnije susresti i u širem kontekstu: npr. u nelinearnim modelima, optimizaciji portfelja s ograničenjima rizika, ili u kombinaciji s višekriterijskim metodama odlučivanja (AHP, PROMETHEE i sl.; Tamiz, Jones & Romero, 1998).

Opći zapis modela u linearnom programiranju

Prvo podsjetnik kako izgleda “običan” LP u vektorskom zapisu:

\[ \begin{aligned} \max \quad & z = \mathbf{c}^\top \mathbf{x} \\ \text{uz ograničenja} \quad & A\mathbf{x} \le \mathbf{b} \\ & \mathbf{x} \ge \mathbf{0} \end{aligned} \]

$\mathbf{x} = (x_1, \dots, x_n)^\top$ – varijable odluke (npr. koliko proizvoda, koliko sati rada, koliko uložiti u koji instrument…)
$\mathbf{c}$ – koeficijenti funkcije cilja (profit po jedinici, prinos po jedinici…)
$A$ – matrica koeficijenata ograničenja
$\mathbf{b}$ – desna strana ograničenja (kapaciteti, budžeti…)

U LP-u:

funkcija cilja je jedna,
sva ograničenja su tvrda: ili su zadovoljena, ili rješenje nije dopušteno.

Već ovdje možemo naslutiti problem: što ako je “cilj” tipa “želimo 130 000 € dobiti” više aspiracija nego strogo ograničenje? Ako model ne može točno doseći 130 000, želimo znati koliko odstupamo – i u plus, i u minus.

Ciljno programiranje

Ideja ciljnog programiranja (Goal Programming, GP) je vrlo jednostavna:

Za svaki važan kriterij zadajemo “cilj” (aspiracijsku razinu), npr.:
- dobit = 130 000 €
- udio rizika = 10 %
- broj zaposlenih ≥ 20
Umjesto da te ciljeve tretiramo kao tvrda ograničenja, uvodimo

varijable odstupanja koje mjere:
- koliko podbacujemo u odnosu na cilj ($d_i^-$, negativno odstupanje od cilja),
- varijabla $d_i^-$ ima pozitivni predznak u ograničenju, jer tu vrijednost pribrajamo ostvarenoj vrijednosti cilja kako bismo postigli traženu/ ciljanu vrijednost.
- koliko premašujemo cilj ($d_i^+$, pozitivno odstupanje od cilja).
- varijabla $d_i^+$ ima negativnu predznak u ograničenju, jer tu vrijednost oduzimamo od ostvarene vrijednosti cilja kako bismo postigli traženu/ ciljanu vrijednost.
Zatim kao funkciju cilja uzimamo:
- minimizaciju kombinacije tih odstupanja
- (obično je u pitanju zbroj, a u kompleksnijim slučajevima - ponekad ponderirani zbroj, ponekad hijerarhijski).

Drugim riječima, u ciljnom programiranju ne optimiziramo izravno profit/rizik/bilo što, nego optimiziramo koliko smo blizu svojim ciljevima.

Strukturiranje modela

Varijable odstupanja $d_i^+$ i $d_i^-$

Za svaki cilj $i$ uvodimo dva tipa varijabli:

$d_i^+$ – pozitivno odstupanje
(koliko premašujemo cilj),
$d_i^-$ – negativno odstupanje
(koliko padamo ispod cilja).

Ograničenja temeljem ciljne vrijednosti

Tipičan zapis za cilj tipa “ciljamo vrijednost $g_i$” izgleda:

\[ f_i(\mathbf{x}) + d_i^- - d_i^+ = g_i, \]

gdje je:

$f_i(\mathbf{x})$ – izraz koji daje ostvarenu vrijednost (npr. dobit, rizik…, uobičajeno zapisujemo u obliku $c_1x_1+c_2x_2+... +c_nx_n$),
$g_i$ – ciljna vrijednost (npr. 130 000 € dobiti),
$d_i^-$ i $d_i^+$ mjere koliko smo iznad/ispod te vrijednosti.

Uz to uvijek dodajemo:

\[ d_i^+ \ge 0,\quad d_i^- \ge 0. \]

Intuicija:

ako je, npr., cilj dobit 130 000 €, onda

– $d_i^- > 0$: nedostaje dobiti do cilja → nismo zaradili koliko smo htjeli;
– $d_i^+ > 0$: zaradili smo više od cilja (premašili smo ga).

Koje odstupanje nas “boli”?

ponekad želimo kažnjavati samo jedno (npr. samo manjak profita),
ponekad obje strane (npr. prevelik i premali rizik su loši).

Funkcija cilja

Najjednostavniji (i najčešći) oblik funkcije cilja u ciljnom programiranju je:

\[ \min \sum_i (d_i^+ + d_i^-), \]

odnosno:

želimo da su sva odstupanja od naših ciljnih vrijednosti ukupno što je moguće manja.

Kasnije ćemo dodati:

težine (neki ciljevi su važniji),
ili hijerarhiju ciljeva (prvo minimiziramo odstupanje od cilja 1, tek onda od cilja 2, itd.).

Primjena

Lin & O’Leary (1993) daju pregled kako se ciljno programiranje koristi u financijskom menadžmentu: od strukturiranja portfelja, preko upravljanja likvidnošću do financijskog planiranja. U tipičnom modelu više se financijskih ciljeva (npr. maksimalni prinos, minimalni rizik, zadovoljenje regulatornih omjera, ograničenje duga) pretvara u ciljeve s odstupanjima, a GP model onda traži kombinaciju ulaganja koja najbolje “pogodi” zadane aspiracije.

Price & Piskor (1972) koriste GP za planiranje kadrova u organizaciji: broj zaposlenih po razinama, internalne promocije, zapošljavanje izvana, uz više ciljeva (minimizirati trošak, zadržati strukturu kompetencija, poštovati pravila o napredovanju). Ciljevi poput “održati broj iskusnih zaposlenih” ili “ograničiti broj novih zapošljavanja” postavljaju se kao meki ciljevi, a GP model pomaže pronaći plan koji najbolje uravnotežuje trošak i strukturu radne snage.

Karpak, Kumcu & Kasuganti (1999) pokazuju kako se odabir dobavljača (gdje imamo više kriterija: cijena, kvaliteta, pouzdanost, rok isporuke…) može riješiti ciljnim programiranjem uz vizualno sučelje. Menadžer postavlja cilj i ograničenja (maksimalni broj dobavljača, minimalni udio skupih dobavljača, minimalna razina kvalitete…), a interaktivni GP model vizualizira kako promjena težina i ciljeva utječe na konačnu preporuku.

Sundaram (1978) koriste GP za optimizaciju parametara obrade metala (npr. brzina rezanja, posmak) uz više ciljeva: minimizirati vrijeme obrade, minimizirati trošenje alata i održavati kvalitetu površine u zadanim granicama. Svaki od ovih tehnoloških kriterija pretvara se u cilj s odstupanjima, a GP nalazi kompromisni skup parametara.

Rad Broz et al. (2019) opisuje primjenu GP-a u dnevnom planiranju proizvodnje u pilanama. Ciljevi uključuju: ispuniti narudžbe kupaca određenih dimenzija, minimizirati ostatak (otpad), ograničiti promjene postavki strojeva i poštovati raspoložive kapacitete. Model s više ciljeva i ograničenja pretvara se u ciljni LP gdje se minimizira skup odstupanja od kvota i kapaciteta, pružajući planerima alat za svakodnevno odlučivanje.

Ignizio (1980) daje uvod u GP kroz niz primjera u urbanom planiranju i javnim sustavima: raspored policijskih patrola, planiranje javnog prijevoza, raspodjela budžeta gradskih službi. Ciljevi tipa “minimizirati vrijeme putovanja”, “maksimizirati pokrivenost područja” ili “ne prekoračiti proračun” postavljaju se kao ciljevi s odstupanjima, i služe kao ilustracija kako GP radi u javnom sektoru.

Dave (2015) pruža pregled primjena GP-a u poljoprivrednom menadžmentu: planiranje usjeva, raspodjela zemljišta, izbor kombinacije kultura uz ciljeve poput maksimalnog prinosa, minimalnog rizika, ravnoteže radne snage ili poštivanja ekoloških standarda.

Primjeri iz financijskog menadžmenta, planiranja radne snage, odabira dobavljača, planiranja proizvodnje, urbanih sustava i poljoprivrede pokazuju da se ciljno programiranje prirodno javlja svugdje gdje imamo više željenih razina (ciljeva) i ograničen skup resursa. Umjesto da donositelj odluke unaprijed odabere samo jedan kriterij, GP mu omogućuje da sve važne ciljeve prevede u ciljne jednadžbe i eksplicitno promatra odstupanja od njih. Na taj način model ne daje samo „najbolje rješenje”, već i informaciju koliko i na koji način je određeni skup ciljeva uopće ostvariv. U nastavku to koristimo na konkretnom primjeru portfelja kriptovaluta, a kasnije i kao most prema višeciljnom programiranju.

Primjer

Imate na raspolaganju nekoliko različitih kriptovaluta u koje možete ulagati. Vaš cilj je maksimizirati vrijednost svog portfelja uz određene financijske i rizične parametre. Imate mogućnost ulaganja u tri kriptovalute: Bitcoin (BTC), Ethereum (ETH) i Ripple (XRP). Svaka od ovih kriptovaluta ima predviđeni godišnji prinos i očekivani rizik, izražen kao standardna devijacija.

Bitcoin (BTC) ima očekivani godišnji prinos od 12% s rizikom (standardnom devijacijom) od 20%.
Ethereum (ETH) ima očekivani godišnji prinos od 18% s rizikom od 25%.
Ripple (XRP) ima očekivani godišnji prinos od 24% s rizikom od 30%.

Imate na raspolaganju ukupan iznos novca za ulaganje, koji je 500.000 eura i cilj Vam je ostvariti dobit od 130 000 eura.

Osim toga, postavljate sljedeća četiri ograničenja:

Želite uložiti najmanje 100.000 eura u Bitcoin (BTC).
Ne želite ulagati više od 200.000 eura u Ethereum (ETH).
Želite da Ripple (XRP) čini najmanje 20% ukupnog portfelja.
Ne želite prekoračiti rizik portfelja od 27%.

Kako ćete rasporediti svoja sredstva između tih kriptovaluta kako biste maksimizirali očekivani godišnji prinos uz zadovoljenje navedenih ograničenja?

Iščitavanje:

“očekivani godišnji prinos od 12%” - Očekivani godišnji prinos = koliko će ulog porasti u godinu dana
“s rizikom (standardnom devijacijom) od 27%” - Standardna devijacija se u financijama često koristi kao mjera rizika
“cilj Vam je ostvariti dobit od 130 000 €” - Cilj je izražen kao specifična vrijednost koja se želi postići

Od teksta do matematičkog modela

Neka su varijable odluke:

$B$ – iznos uložen u Bitcoin
$E$ – iznos uložen u Ethereum
$R$ – iznos uložen u Ripple

Očekivana dobit portfelja dana je linearnom kombinacijom prinosa:

\[ \text{Dobit} \;=\; 0.12B + 0.18E + 0.24R \]

Umjesto da tu dobit maksimiziramo, u ciljnom programiranju uvodimo ciljnu razinu 130 000 $ i dozvoljavamo odstupanje. Za to uvodimo dvije dodatne varijable:

$d_f^-$ – koliko zaostajemo za ciljem (premala dobit)
$d_f^+$ – koliko prelazimo cilj (prevelika dobit)

Ciljni uvjet zapisujemo kao:

\[ 0.12B + 0.18E + 0.24R + d_f^- - d_f^+ = 130000 \]

Ako portfelj ostvaruje profit manji od 130 000, razlika će se “upisati” u $d_f^-$. Ako je profit veći, odstupanje ide u $d_f^+$. U najjednostavnijoj verziji ciljnog programiranja cilj je minimizirati ukupno odstupanje:

\[ \min (d_f^+ + d_f^-) \]

Ostala ograničenja slijede iz priče (zapisujemo na uobičajen način).

Strukturiranje problema:

Varijable odluke:

B – Bitcoin

E – Ethereum

R – Ripple

$df^+, df^-$ - pozitivna i negativna odstupanja od cilja

Funkcija cilja:

$\min (df^+ + df^-)$

Ograničenja

$B+E+R \leq 500000$

$B \geq 100000$

$E \leq 200000$

$R \geq 0.2 \cdot 500000$

$0.2 \cdot B+0.25 \cdot E+0.3 \cdot R \leq 0.27 \cdot 500000$

$0.12 \cdot B+0.18 \cdot E +0.24 \cdot R - df^+ + df^- =130000$

$B, E, R, df^+, df^- \geq 0$

library(lpSolve)

## Warning: package 'lpSolve' was built under R version 4.4.2

# B, E, R, df^+, df^-
cvec <- c(0, 0, 0, 1, 1)
matA <- matrix(c(1, 1, 1, 0, 0,
                 1, 0, 0, 0, 0,
                 0, 1, 0, 0, 0,
                 0, 0, 1, 0, 0,
                 0.2, 0.25, 0.3, 0, 0,
                 0.12, 0.18, 0.24, -1, 1),
               ncol = 5, byrow = TRUE)
dirvec <- c("<=", ">=", "<=", ">=", "<=", "=")
rhsvec <- c(500000, 100000, 200000, 0.2*500000, 0.27*500000, 130000)
rjesenje <- lp("min", cvec, matA, dirvec, rhsvec)
rjesenje

## Success: the objective function is 26000

rjesenje$solution

## [1] 100000.0      0.0 383333.3      0.0  26000.0

Vektor rješenja možemo pročitati ovako:

$B=100000$

$E=0$

$R=383333.3$

$df^+=0$

$df^−=26000$

To znači da optimalna politika ulaganja u ovom modelu glasi: u Bitcoin ulažemo točno minimalno dopuštenih 100 000 €, u Ethereum ne ulažemo ništa, a sav preostali novac stavljamo u Ripple, ukupno 383 333.33 €. Zbroj ulaganja je točno 483 333.3 €, pa vidimo da nije iskorišten cijeli raspoloživi iznos.

Ako sada izračunamo očekivanu dobit za tu kombinaciju,

$\text{Dobit}=0.12⋅100000+0.18⋅0+0.24⋅383333.3=104000$,

postaje jasno što znače varijable odstupanja. Cilj smo zadali na 130 000 €, a model nam javlja

$df^−=26000$ i $df^+=0$

Negativno odstupanje od cilja iznosi 26 000 €, što je upravo razlika između zadane ciljne dobiti (130 000 €) i ostvarive dobiti (104 000 €) za najbolju dopuštenu kombinaciju ulaganja. Pozitivno odstupanje je nula, što znači da u optimalnom rješenju nigdje ne “pretjerujemo” preko cilja; problem je isključivo u tome što cilj ne možemo dostići, nego mu se samo možemo što više približiti.

Drugim riječima, ovaj rezultat nam istovremeno govori dvije stvari. Prvo, u zadanom skupu ograničenja najracionalnije je gotovo sve uložiti u najrizičniju, ali najprofitabilniju kriptovalutu (Ripple), uz minimalni udio Bitcoina i bez Ethereuma. Drugo, čak i s takvom agresivnom strategijom, cilj od 130 000 € je preambiciozan: model nam eksplicitno kvantificira da nam “nedostaje” 26 000 € do željene razine. Ako bismo željeli taj cilj učiniti ostvarivim, morali bismo ili popustiti neka ograničenja (npr. dozvoliti veći rizik portfelja, povećati budžet) ili smanjiti očekivanja i postaviti realističniji cilj dobiti.

Težinski pristup u ciljnom programiranju

U prethodnim primjerima ciljnog programiranja promatrali smo jedan cilj i uvodili varijable odstupanja $d_f^+$ i $d_f^-$ kako bismo mjerili koliko smo daleko od zadane ciljne vrijednosti.

U prethodnom primjeru ciljnog programiranja pretpostavili smo da imamo jedan cilj (ostvariti dobit od 130 000 eura) i da jednostavno želimo minimizirati ukupno odstupanje od tog cilja, bez dodatnih prioriteta. U funkciji cilja pojavila se suma $d_f^+ + d_f^-$, tako da model minimizira i „podbacivanje“ i „prekoračenje“ cilja na isti način.

U praksi to ponekad nije dovoljno. Ponekad nam je važnije izbjeći podbacivanje cilja (npr. dobit ne smije pasti ispod neke razine), a u drugim situacijama je važnije ne prekoračiti određenu granicu (npr. regulatorni limit rizika, emisija CO₂, broj radnih sati).

Osnovna ideja težinskog pristupa je vrlo intuitivna: svi ciljevi ulaze u jednu jedinstvenu funkciju cilja, ali svakom odstupanju pridružujemo težinu koja odražava njegov relativni značaj. Umjesto da odstupanja rangiramo leksički (npr. prvo zadovoljimo pozitivno odstupanje, tek onda brinemo o negativnom), ovdje priznajemo da su svi aktivni istovremeno, ali ne jednakog prioriteta. Matematički, umjesto da minimiziramo sumu odstupanja, minimiziramo ponderiranu sumu:

\[ \min \left( w^+ \, df^+ + w^- \, df^- \right) \]

gdje su $df^+$ i $df^-$ su pozitivno i negativno odstupanje od cilja, a $w^+$ i $w^-$ su odgovarajuće težine. Velika težina znači da ne želimo dopustiti veliko odstupanje za taj cilj; mala težina znači da smo spremni tolerirati veće odstupanje.

Za razliku od leksičkog pristupa, gdje je hijerarhija ciljeva uklesana u kamen (dok god se prvi cilj može poboljšati, drugi uopće “ne dolazi na red”), u težinskom pristupu ciljevi se međusobno mogu kompenzirati. Model smije malo pogoršati jedan cilj ako time postiže znatno bolje ispunjenje nekog drugog cilja kojem smo dali veću težinu. Upravo zato je izbor težina ključan: one kodiraju preferencije donositelja odluka, slično kao što u višekriterijskom odlučivanju (više u lekciji na tu temu) radimo s težinama kriterija.

Tipična struktura modela izgleda ovako:

u funkciju cilja stavimo ponderiranu sumu $d_k^+$ i $d_k^-$,
elemente koji oblikuju cilj (ono što bismo u LP-u oblikovali u funkciju cilja) zapisujemo u ograničenje uz dodavanje $+ d_k^- - d_k^+$ i izjednačavanje s ciljnom vrijednosti
ostatak ograničenja opisuje “tvrde” uvjete problema (budžet, kapacitet, logičke veze…) koji se moraju poštovati bez odstupanja.

Na taj način težinski pristup ciljnog programiranja povezuje intuiciju “kompromisa” između ciljeva s vrlo jasnim, linearnim modelom koji standardni LP solver može riješiti bez dodatnih trikova: sve što solver vidi je jedna linearna funkcija cilja i sustav linearnih ograničenja.

Težinski pristup u ciljnom programiranju omogućuje da i za jedan cilj odvojeno kontroliramo koliko nas „boli” podbacivanje, a koliko prekoračenje ciljne vrijednosti, i sve to unutar standardnog LP okvira. Kasnije, kod višeciljnog programiranja, ista će se ideja proširiti na više ciljeva, svaki sa svojim parom odstupanja i odgovarajućim težinama.

Primjer

Vratimo se na isti primjer kojim smo se ranije bavili, ali pretpostavimo da je $w^+ = 0.7$, a $w^-=0.3$.

Strukturiranje problema:

Varijable odluke:

B – Bitcoin

E – Ethereum

R – Ripple

$df^+, df^-$ - pozitivna i negativna odstupanja od cilja

Funkcija cilja:

$min⁡(0.7 \cdot df^+ + 0.3 \cdot df^-)$

Ograničenja

$B+E+R \leq 500000$

$B \geq 100000$

$E \leq 200000$

$R \geq 0.2 \cdot 500000$

$0.2 \cdot B+0.25 \cdot E+0.3 \cdot R \leq 0.27 \cdot 500000$

$0.12 \cdot B+0.18 \cdot E +0.24 \cdot R - df^+ + df^- =130000$

$B, E, R, df^+, df^- \geq 0$

library(lpSolve)
# B,𝐸,𝑅, df^+, df^-
cvec <- c(0, 0, 0, 0.7, 0.3)
matA <- matrix(c(1, 1, 1, 0, 0,
                 1, 0, 0, 0, 0,
                 0, 1, 0, 0, 0,
                 0, 0, 1, 0, 0,
                 0.2, 0.25, 0.3, 0, 0,
                 0.12, 0.18, 0.24, -1, 1),
               ncol = 5, byrow = TRUE)
dirvec <- c("<=", ">=", "<=", ">=", "<=", "=")
rhsvec <- c(500000, 100000, 200000, 100000, 135000, 130000)
rjesenje <- lp("min", cvec, matA, dirvec, rhsvec)
rjesenje

## Success: the objective function is 7800

rjesenje$solution

## [1] 100000.0      0.0 383333.3      0.0  26000.0

Dobivamo isti rezultat. Pokušajmo sa zamjenom težina.

library(lpSolve)
# B,𝐸,𝑅, df^+, df^-
cvec <- c(0, 0, 0, 0.3, 0.7)
matA <- matrix(c(1, 1, 1, 0, 0,
                 1, 0, 0, 0, 0,
                 0, 1, 0, 0, 0,
                 0, 0, 1, 0, 0,
                 0.2, 0.25, 0.3, 0, 0,
                 0.12, 0.18, 0.24, -1, 1),
               ncol = 5, byrow = TRUE)
dirvec <- c("<=", ">=", "<=", ">=", "<=", "=")
rhsvec <- c(500000, 100000, 200000, 100000, 135000, 130000)
rjesenje <- lp("min", cvec, matA, dirvec, rhsvec)
rjesenje

## Success: the objective function is 18200

rjesenje$solution

## [1] 100000.0      0.0 383333.3      0.0  26000.0

Naš cilj dobiti (130 000) je izvan dosega (maksimum je 104 000). Bez obzira stavili mi težinu 0.3, 1 ili 100 na negativno odstupanje ($d^−$), algoritam će uvijek pokušati smanjiti to odstupanje što je više moguće. Budući da postoji samo jedan smjer poboljšanja (povećanje dobiti do maksimuma), težine ne mijenjaju odluku – samo mijenjaju vrijednost funkcije cilja.

Da bi težinski pristup imao više smisla i pokazao različite rezultate, moramo imati sukobljene ciljeve (trade-off). I to nas upravo dovodi do sljedeće vezane teme - višeciljno programiranje, u kojoj ćemo se prvo pozabaviti klasičnim pristupom.

No, prije prelaska na višeciljno programiranje, iskoristit ćemo uvide iz prethodnog primjera. U prethodnom primjeru vidjeli smo dva ekstrema:

Kada dominira težina za dobit $w_{dobit} \gg w_{rizik}$, trebali bismo dobiti portfelj visokog rizika i visoke dobiti.
Kada dominira težina za rizik $w_{rizik} \gg w_{dobit}$, trebali bismo dobiti portfelj niskog rizika i niske dobiti.

No, što ako nam nisu važni ekstremi? Što ako nam je dobit 60% važna, a rizik 40% važan? Ili 70-30?

Promjenom težina u ciljnom programiranju mi zapravo “šećemo” po skupu najboljih mogućih kompromisa. Taj skup nazivamo Pareto granica ili granica efikasnosti.

Pogledajmo to kroz vizualni prikaz. Važna napomena: Kako bismo ovo demonstrirali, moramo malo modificirati naš primjer. Do sada je rizik bio klasično ograničenje (ne smije preći 27%). Sada ćemo rizik pretvoriti u drugi cilj: ciljamo rizik od 27%. Kažnjavat ćemo svako prekoračenje tog rizika, dok ćemo istovremeno kažnjavati svaki manjak dobiti u odnosu na 130.000 €. Tako dobivamo dva sukobljena cilja: želimo što veću dobit (što traži rizične valute), ali želimo i što manji rizik (što traži sigurne valute). Zavrtjet ćemo petlju gdje ćemo postupno mijenjati težinu (w) od 0 do 1. Težina za dobit će biti (w), a težina za rizik (1-w).

## Warning: package 'ggplot2' was built under R version 4.4.3

Što nam ovaj grafikon govori?

Svaka točka na ovoj liniji predstavlja jedno optimalno rješenje za određenu kombinaciju težina.

Točke ispod linije su neučinkovite (mogli bismo ostvariti više dobiti za isti rizik).
Točke iznad linije su nemoguće (uz zadana ograničenja).
Sama linija predstavlja najbolje moguće kompromise.

Ovo nas dovodi do definicije višeciljnog programiranja.

U višeciljnom programiranju ne tražimo “jedan broj” (jedinstveni optimum), nego tražimo upravo ovakav skup rješenja (Pareto skup) iz kojeg donositelj odluke može birati ovisno o svojim preferencijama. Ciljno programiranje (s težinama) je, dakle, samo jedan od načina kako možemo “uhvatiti” točku na ovoj krivulji.

Višeciljno programiranje

U stvarnim menadžerskim i inženjerskim problemima, rijetko donosimo odluke temeljem samo jednog kriterija. Najčešće želimo istovremeno:

maksimizirati dobit,
minimizirati rizik,
očuvati likvidnost,
zadržati stabilnost radne snage,
smanjiti emisiju CO2…

Ovi ciljevi su često konfliktni – poboljšanje jednog cilja (npr. veća dobit) često dovodi do pogoršanja drugog (npr. veći rizik). U takvom okruženju pojam optimalnog rješenja se mijenja. Ne tražimo rješenje koje je matematički najveće, već rješenje koje predstavlja najbolji prihvatljivi kompromis između suprotstavljenih zahtjeva. Upravo takve probleme rješavamo višeciljnim programiranjem.

Za razliku od standardnog linearnog programiranja gdje tražimo jednu točku koja maksimizira jednu vrijednost, u višeciljnom programiranju (multi objective linear programming, MOLP) tražimo rješenje koje istovremeno zadovoljava više, često suprotstavljenih kriterija.

Koristeći naučeno o ciljnom programiranju, koncept ćemo proširiti na više ciljeva kroz osnovni, najjednostavniji pristup višeciljnom programiranju.

Pretpostavimo da imamo $n$ varijabli odluka $x_1, x_2, \dots, x_n$
i $p$ ciljeva. Svaki cilj $k = 1,\dots,p$ zadan je:

ciljnom vrijednošću $G_k$
linearnom funkcijom u varijablama odluke \[ f_k(x) = \sum_{j=1}^n a_{kj} x_j. \]

Uz ciljeve imamo i uobičajena ograničenja (resursi, kapaciteti, logičke veze…) koja se ne smiju kršiti:

\[ \sum_{j=1}^n a_{ij} x_j \le b_i,\quad i = 1,\dots,m, \] \[ x_j \ge 0,\quad j = 1,\dots,n. \]

Za svaki cilj $k = 1,\dots,p$ uvodimo dvije dodatne varijable:

$d_k^+$ – pozitivno odstupanje od cilja (prekoračenje cilja)
$d_k^-$ – negativno odstupanje od cilja (podbacivanje cilja)

i vezujemo ih uz „idealnu“ jednadžbu koja predstavlja vezano ograničenje:

\[ f_k(x) + d_k^- - d_k^+ = G_k,\quad k = 1,\dots,p. \]

Ako je $f_k(x) < G_k$, jednadžba se može zadovoljiti samo uz $d_k^- > 0$ (zaostajemo za ciljem).
Ako je $f_k(x) > G_k$, mora biti $d_k^+ > 0$ (prekoračujemo cilj).
Ako točno pogodimo cilj, oba odstupanja mogu biti jednaka nuli.

Naravno, vrijedi: \[ d_k^+ \ge 0,\quad d_k^- \ge 0,\quad k = 1,\dots,p. \]

Sveukupno, skup varijabli u modelu čine:

\[ x_1,\dots,x_n,\; d_1^+, d_1^-,\dots, d_p^+, d_p^-. \]

U najjednostavnijoj varijanti višeciljnog programiranja ne razlikujemo važnost ciljeva: želimo smanjiti ukupno odstupanje od svih ciljeva zajedno. Funkciju cilja tada pišemo kao:

\[ \min \left( d_1^+ + d_1^- + d_2^+ + d_2^- + \dots + d_p^+ + d_p^- \right). \]

Model tada ima sljedeću strukturu:

Funkcija cilja: \[ \min \sum_{k=1}^p \left( d_k^+ + d_k^- \right) \]
Ciljna ograničenja (po jedan redak za svaki cilj): \[ f_k(x) + d_k^- - d_k^+ = G_k,\quad k = 1,\dots,p \]
Uz ostala ograničenja: \[ \sum_{j=1}^n a_{ij} x_j \le b_i,\quad i = 1,\dots,m \] \[ x_j \ge 0,\quad j = 1,\dots,n \] \[ d_k^+, d_k^- \ge 0,\quad k = 1,\dots,p. \]

Na taj način višeciljno programiranje zadržava istu logiku kao i ciljni slučaj:
svaki cilj dobiva svoj par odstupanja $d_k^+$ i $d_k^-$, a solver i dalje vidi jedan LP problem – jednu linearnu funkciju cilja i sustav linearnih ograničenja u proširenom prostoru varijabli.

Općenitije, matematički model višeciljnog linearnog programiranja (MOLP) definira se na sljedeći način:

\[\begin{aligned} \max \quad & \mathbf{Z}(\mathbf{x}) = [z_1(\mathbf{x}), z_2(\mathbf{x}), \dots, z_k(\mathbf{x})]^\top \\ \text{uz ograničenja} \quad & \mathbf{x} \in S \end{aligned} \] gdje je:

$\mathbf{x}$ – vektor varijabli odluke,
$S$ – skup dopustivih rješenja definiran linearnim ograničenjima ((A , )),
$z\_1(\mathbf{x}), \dots, z\_k(\mathbf{x})$ – linearne funkcije cilja koje želimo optimizirati.

Ključna razlika u odnosu na klasični LP je u tome što $\mathbf{Z}(\mathbf{x})$ nije skalar (jedan broj), već vektor.

Koncept rješenja: zašto nema “jednog najboljeg”?

U ciljnom (jednociljnom) problemu lako je usporediti dva rješenja: rješenje A je bolje od rješenja B ako donosi veći profit. U višeciljnom problemu usporedba nije trivijalna.

Zamislimo naš prethodni primjer s kriptovalutama, npr.:

Rješenje A: dobit = 120.000, rizik = 25%
Rješenje B: dobit = 100.000, rizik = 15%

Koje je rješenje “optimalno”? Ne možemo reći bez subjektivne procjene investitora. Rješenje A je bolje po prvom kriteriju, ali gore po drugom. Zbog toga u MOLP-u uvodimo dva ključna koncepta: Idealnu točku i Pareto optimalnost.

1. Idealna točka (Utopia Point)

Idealna točka $\mathbf{Z}^{ideal}$ nastaje kada bismo svaki cilj optimizirali zasebno, potpuno ignorirajući ostale ciljeve.

\[z\_j^{ideal} = \max\_{\mathbf{x} \in S} z\_j(\mathbf{x}) \]

U našem primjeru to bi bio portfelj koji ima maksimalnu moguću dobit (kao da rizik nije bitan) i istovremeno minimalni mogući rizik (kao da dobit nije bitna). U praksi je takva točka gotovo uvijek nedostižna jer su ciljevi u konfliktu (ne postoji jedan $\mathbf{x}$ koji postiže te maksimume istovremeno).

2. Pareto optimalnost (Efikasna rješenja)

Budući da idealnu točku ne možemo doseći, tražimo rješenja koja su ne-dominirana.

Rješenje $\mathbf{x}^\*$ je Pareto optimalno (efikasno) ako ne postoji niti jedno drugo dopustivo rješenje $\mathbf{x}$ koje bi:

poboljšalo barem jedan cilj,
a da pritom ne pogorša niti jedan drugi cilj.

Skup svih takvih rješenja naziva se Pareto granica (ili Efficient Frontier).

Rješavanje problema višeciljnog programiranja zapravo znači:

Generiranje skupa Pareto optimalnih rješenja, ili
Pronalaženje jednog specifičnog Pareto rješenja koje najbolje odgovara preferencijama donositelja odluke.

Primjena

Foued & Sameh (2001) modeliraju upravljanje vodnim rezervoarom s više ciljeva: osigurati vodoopskrbu, proizvodnju hidroenergije, navodnjavanje i smanjenje poplavnih rizika. Svaki cilj ima svoju ciljnu razinu (minimalni protok, minimalna proizvodnja, itd.), a GP se koristi kao alat za višeciljno upravljanje – zapravo konkretna primjena višeciljnog programiranja u vodnom gospodarstvu.

San Cristóbal (2012) koristi višeciljni GP model za analizu okolišne politike Španjolske - balansira ciljeve poput smanjenja emisija, troška energetskog sustava i sigurnosti opskrbe. Različiti scenariji (npr. veći udio obnovljivih izvora) uspoređuju se kroz odstupanja od ciljeva za emisije, cijene i strukturu proizvodnje. To je dobar realni primjer gdje višeciljno programiranje može poslužiti za modeliranje energetske tranzicije i klimatskih politika.

U radu Prišenk et al. (2014), LP i težinsko ciljno programiranje kombiniraju se za planiranje poljoprivredne proizvodnje (kultura, rotacije, resursi) s više ciljeva: maksimizacija dobiti, stabilnost prihoda, minimizacija rizika i poštivanje agronomskih i okolišnih ograničenja. Autorice pokazuju da GP sloj omogućuje finije postavljanje preferencija između ciljeva, praktički generirajući Pareto-kompromise.

Uz teorijski dio, Tanino, Tanaka & Inuiguchi (2013) u svojoj knjizi predstavljaju niz studija slučaja iz inženjerstva, financija, transporta i upravljanja okolišem, gdje se višeciljno programiranje (ponekad u GP formi) koristi za traženje Pareto-efikasnih rješenja.

Primjene u upravljanju rezervoarima, okolišnoj politici, poljoprivredi i različitim inženjerskim sustavima pokazuju da višeciljno programiranje nije teorijska egzotika, nego svakodnevni alat kada istovremeno brinemo o ekonomskim, tehnološkim i okolišnim učincima. U svim tim slučajevima ne postoji jedinstveno „najbolje” rješenje, već skup Pareto-efikasnih kompromisa između ciljeva. Ciljno programiranje s varijablama odstupanja daje praktičan način da takve situacije prevedemo u jedan prošireni LP model i iz njega izvučemo rješenja koja su u skladu s preferencijama donositelja odluke. U nastavku to ilustriramo na jednostavnom, ali dovoljno bogatom primjeru portfelja kriptovaluta s dva cilja: dobiti i rizik.

Primjer

Bitcoin (BTC) ima očekivani godišnji prinos od 12% s rizikom (standardnom devijacijom) od 20%.
Ethereum (ETH) ima očekivani godišnji prinos od 18% s rizikom od 25%.
Ripple (XRP) ima očekivani godišnji prinos od 24% s rizikom od 30%.

Imate na raspolaganju ukupan iznos novca za ulaganje, koji je 500.000 eura i želite ostvariti dobit od 150000 eura.

Osim toga, postavljate sljedeća četiri ograničenja:

Želite uložiti najmanje 100.000 eura u Bitcoin (BTC).
Ne želite ulagati više od 200.000 eura u Ethereum (ETH).
Želite da Ripple (XRP) čini najmanje 20% ukupnog portfelja.
Želite minimizirati rizik s ciljem postizanja rizika od 10 %.

Kako ćete rasporediti svoja sredstva između tih kriptovaluta kako biste maksimizirali očekivani godišnji prinos uz zadovoljenje navedenih ograničenja?

Iščitavanje:

“želite ostvariti dobit od 150000 eura” - 1. cilj

“Želite minimizirati rizik s ciljem postizanja rizika od 10 %” - 2. cilj

Strukturiranje problema

Varijable odluke:

B – Bitcoin

E – Ethereum

R – Ripple

$df1^-, df1^+$ - pozitivna i negativna odstupanja od 1. cilja

$df2^-, df2^+$ - pozitivna i negativna odstupanja od 2. cilja

Funkcija cilja:

$min⁡(𝑑𝑓_1^++ 𝑑𝑓_1^−+𝑑𝑓_2^++ 𝑑𝑓_2^−)$

Ograničenja

$𝐵+𝐸+𝑅≤500000$

$𝐵≥100000$

$𝐸≤200000$

$𝑅≥0.2 \cdot 500000$

$0.2 \cdot 𝐵+0.25 \cdot𝐸+0.3 \cdot 𝑅+𝑑𝑓_2^−−𝑑𝑓_2^+=0.1 \cdot 500000$

$0.12 \cdot 𝐵+0.18 \cdot 𝐸+0.24 \cdot 𝑅+𝑑𝑓_1^−−𝑑𝑓_1^+=150000$

$B,𝐸,𝑅, df1^-, df1^+, df2^-, df2^+≥0$

library(lpSolve)
# B,𝐸,𝑅, df1^-, df1^+, df2^-, df2^+
cvec <- c(0, 0, 0, 1, 1, 1, 1)
matA <- matrix(c(1, 1, 1, 0, 0, 0, 0,
                 1, 0, 0, 0, 0, 0, 0,
                 0, 1, 0, 0, 0, 0, 0, 
                 0, 0, 1, 0, 0, 0, 0,
                 0.2, 0.25, 0.3, 0, 0, 1, -1,
                 0.12, 0.18, 0.24, 1, -1, 0, 0),
               ncol = 7, byrow = TRUE)
dirvec <- c("<=", ">=", "<=", ">=", "=", "=")
rhsvec <- c(500000, 100000, 200000, 100000, 50000, 150000)
rjesenje <- lp("min", cvec, matA, dirvec, rhsvec)
rjesenje

## Success: the objective function is 114000

rjesenje$solution

## [1] 100000      0 100000 114000      0      0      0

Uz ove postavke, podjednako se ulaže u Bitcoin i Ripple, po 100000 eura. Odstupanje od 114000 eura zabilježeno je za $df1^-$, što znači da nismo uspjeli doseći ciljanu dobit. Istovremeno, nisu zabilježena odstupanja od drugog cilja, što znači da je ciljana razina rizika od 10% u potpunosti ostvarena ovom raspodjelom.

Primijetite da se ovdje ne koristi cijeli budžet od 500 000 €, jer je ograničenje budžeta postavljeno kao ≤, a ne =. Model radije ostavlja novac neiskorištenim kako bi mogao točno pogoditi cilj rizika od 10 %.

Pareto efikasnost za dobit i rizik

U prethodnom primjeru postavili smo dva cilja za isti portfelj:

maksimizirati očekivanu dobit
minimizirati rizik portfelja

Umjesto da ih zadamo kao ciljne vrijednosti (150 000 € dobiti, 10 % rizika), ovdje ćemo ih promatrati kao dva konfliktna cilja koja želimo optimizirati istovremeno.

To nam omogućuje da nacrtamo Pareto granicu – skup najboljih kompromisa između dobiti i rizika.

O Pareto efikasnosti možemo razmišljati slično kao o analizi osjetljivosti, ali umjesto da mijenjamo parametre modela, ovdje istražujemo različita dopuštena rješenja. Pareto analiza nam pokazuje koje kombinacije varijabli daju rezultate koje je nemoguće poboljšati u jednom cilju, a da barem jedan drugi ne pogoršamo. Iz te perspektive, Pareto granicu možete shvatiti kao svojevrsnu “analizu osjetljivosti po ciljevima”: ona opisuje skup rješenja za koja ne postoji drugo rješenje koje je u jednom cilju bolje, a da istovremeno u nekom drugom cilju nije lošije.

library(lpSolve)
library(ggplot2)

# Koeficijenti ciljeva

c_profit <- c(0.12, 0.18, 0.24)  # B, E, R
c_risk   <- c(0.20, 0.25, 0.30)

# Ograničenja (bez ciljeva, samo klasični uvjeti)
# B + E + R <= 500000
# B >= 100000
# E <= 200000
# R >= 0.2 * 500000 = 100000

matA <- matrix(c( 1,  1,  1,      # budžet
1,  0,  0,      # B >= 100000
0,  1,  0,      # E <= 200000
0,  0,  1),     # R >= 100000
ncol = 3, byrow = TRUE)

dirvec <- c("<=", ">=", "<=", ">=")
rhsvec <- c(500000, 100000, 200000, 100000)

# Funkcija koja za zadanu težinu w rješava LP:
# max [ w * profit  - (1 - w) * risk ]

solve_for_w <- function(w) {
cvec <- w * c_profit - (1 - w) * c_risk
res <- lp(direction = "max",
objective.in = cvec,
const.mat    = matA,
const.dir    = dirvec,
const.rhs    = rhsvec)

if (res$status != 0) return(NULL)

BER <- res$solution
names(BER) <- c("B", "E", "R")

profit <- sum(c_profit * BER)
risk   <- sum(c_risk   * BER)

data.frame(w = w,
B = BER["B"],
E = BER["E"],
R = BER["R"],
profit = profit,
risk   = risk)
}

# Generiramo rješenja za razne kombinacije težina
ws <- seq(0, 1, by = 0.05)
sols_list <- lapply(ws, solve_for_w)
pareto_df <- do.call(rbind, sols_list)

head(pareto_df)

##       w     B E     R profit  risk
## B  0.00 1e+05 0 1e+05  36000 50000
## B1 0.05 1e+05 0 1e+05  36000 50000
## B2 0.10 1e+05 0 1e+05  36000 50000
## B3 0.15 1e+05 0 1e+05  36000 50000
## B4 0.20 1e+05 0 1e+05  36000 50000
## B5 0.25 1e+05 0 1e+05  36000 50000

# Idealna točka: maksimizacija samo dobiti

res_profit <- lp("max", c_profit, matA, dirvec, rhsvec)
BEP_profit <- res_profit$solution
profit_max <- sum(c_profit * BEP_profit)
risk_at_profit_max <- sum(c_risk * BEP_profit)

# Idealna točka: minimizacija samo rizika

res_risk <- lp("min", c_risk, matA, dirvec, rhsvec)
BEP_risk <- res_risk$solution
risk_min <- sum(c_risk * BEP_risk)
profit_at_risk_min <- sum(c_profit * BEP_risk)

# Idealna ("utopijska") točka u prostoru ciljeva

ideal_point <- data.frame(
risk   = risk_min,
profit = profit_max
)

ideal_point

##    risk profit
## 1 50000 108000

ggplot(pareto_df, aes(x = risk, y = profit)) +
geom_line() +
geom_point() +
geom_point(data = ideal_point, aes(x = risk, y = profit), shape = 8, size = 3) +
labs(x = "Rizik portfelja",
y = "Očekivana dobit",
title = "Pareto granica između dobiti i rizika") +
theme_minimal()

Na grafikonu:

svaka točka na liniji predstavlja optimalno rješenje za određenu kombinaciju težina $w$:
- kada je $w$ blizu 1, naglasak je na dobiti → visoka dobit, visoki rizik
- kada je $w$ blizu 0, naglasak je na riziku → nizak rizik, niža dobit
točke ispod linije su neučinkovite (dominirana rješenja): za isti rizik postoji rješenje s većom dobiti, ili za istu dobit rješenje s manjim rizikom.
točke na liniji čine Pareto granicu (skup Pareto efikasnih rješenja): ne možemo poboljšati jedan cilj (povećati dobit ili smanjiti rizik) a da barem drugi ne pogoršamo.

Zvjezdicom je označena idealna (utopijska) točka:

ona kombinira najveću moguću dobit (da je dobit jedini cilj) i najmanji mogući rizik (da je rizik jedini cilj).

U pravilu takva točka nije ostvariva jednim konkretnim portfeljem:
maksimalna dobit i minimalni rizik postižu se različitim kombinacijama $B, E, R$.

U višeciljnom programiranju zato ne tražimo uvijek jedinu najbolju točku, nego skup Pareto efikasnih rješenja. Iz tog skupa donositelj odluke odabire rješenje ovisno o svojim preferencijama – u našem slučaju, koliko je spreman žrtvovati dio dobiti da bi smanjio rizik, ili obratno.

Ovaj koncept je osnova za naprednije teme (npr. višekriterijsko odlučivanje, optimizacija portfelja u financijama). U ovom kolegiju zadržat ćemo se na ciljnim modelima i osnovnom višeciljnom programiranju uz varijable odstupanja, dok se detaljna analiza Pareto granice ostavlja za daljnje predmete i literaturu.

Težinski pristup u višeciljnom programiranju

Kod višeciljnog programiranja već smo vidjeli da svaki cilj može dobiti svoj par varijabli odstupanja $d_k^+$ i $d_k^−$, a zatim minimiziramo zbroj svih odstupanja. Time zapravo kažemo: „sva odstupanja su jednako važna, samo želimo da ih ukupno bude što manje”.

U praksi, naravno, ciljevi rijetko imaju jednaku važnost. Često imamo situacije tipa:

profit je važniji od stabilnosti broja projekata
rizik je važniji od prinosa
emisije CO2 imaju granicu koja se ne smije preći, dok je npr. marketing budžet fleksibilniji

Težinski pristup upravo služi da kodiramo te razlike u važnosti.

Za svaki cilj $k$ uvodimo težine i to možemo učiniti na dva načina:

težine koje se pripisuju odstupanjima:

$w_k^+$ za pozitivno odstupanje $d_k^+$
$w_k^−$ za negativno odstupanje $d_k^−$

i kao funkciju cilja uzimamo

\[\min \sum_{k=1}^p(w_k^+ \cdot d_k^+ +w_k^−d_k^−)\]

težine koje se pripisuju funkcijama:

npr. $w_1$ za funkciju $\max Z_1$
npr. $w_2$ za funkciju $\min Z_2$

i kao funkciju cilja tad dobivamo:

\[\max \big(w_1 \cdot Z_1 - w_2 \cdot Z_2 \big)\] ili

\[\min \big(w_2 \cdot Z_2 - w_1 \cdot Z_1 \big)\]

Težine ne moraju matematički zbrojem dati 1, ali ako ipak to napravimo, praktično ih je iščitati: tada ih možemo čitati kao postotke važnosti (npr. 0.6 za rizik, 0.4 za dobit).

Prva varijanta omogućuje nijansiranje preferencija odstupanja. Ako je, recimo, podbacivanje ispod cilja za dobit izrazito nepoželjno, stavit ćemo veliku težinu na odgovarajući $w_k^−$. Ako nam povremeno premašivanje iznad cilja (npr. nešto viši trošak ili malo veći rizik) nije tako strašno, stavit ćemo manju težinu na odgovarajući $w_k^+$.

U drugoj varijanti, težine usmjeravaju vrijednost čitave funkcije, bez posebnih preferencija vezanih uz odstupanja prema premašivanju ili podbacivanju u odnosu na cilj.

Primjer

Tvrtka “Closeden” razmatra izradu web aplikacije i mora odabrati između pet različitih tehnoloških okvira: React, Vue.js, Angular, Ruby on Rails i Django. Odluka će se temeljiti na nekoliko kriterija kako bi se osiguralo da je odabrana najbolja opcija za projekt. Kriteriji uključuju popularnost okvira, dostupnost programera, cijenu programera po satu, veličinu zajednice i mogućnosti integracije.

Evo tablice s ocjenama za svaki okvir na temelju svakog od kriterija (skala od 1 do 10, gdje je 10 najbolja ocjena):

Okvir	Popularnost	Velicina.zajednice	Integracija	Dostupnost.programera	Cijena.programera.po.satu
React	9	9	8	8	35
Vue.js	8	8	7	9	30
Angular	7	7	9	7	40
Ruby on Rails	6	6	6	6	45
Django	7	7	8	8	40

U Closedenu imaju proračun od 68 tisuća eura za razvoj i žele brzo započeti projekt, ali također žele osigurati da će imati dovoljno programera na raspolaganju po razumnoj cijeni. Planirana web aplikacija iziskivat će barem 1920 sati rada, a namjeravaju zaposliti toliko programera koliko je potrebno da uspiju završiti aplikaciju u 2 mjeseca. Pritom se pretpostavlja da programeri rade 40 sati tjedno.

Dok menadžeri Closedena žele maksimizirati ocjenu okvira (temeljem popularnosti, veličine zajednice i integracije), također žele minimizirati trošak plaća programera. Pritom veću težinu stavljaju na trošak plaća programera, 0.6, dok ocjeni okvira pripisuju težinu 0.4.

Struktura problema

Varijable odluke

Neka $x_i$ budu binarne varijable koje označavaju odabir $i$-tog tehnološkog okvira, gdje je
$x_i = 1$ ako je okvir odabran, inače $x_i = 0$:

$x_1$: React
$x_2$: Vue.js
$x_3$: Angular
$x_4$: Ruby on Rails
$x_5$: Django

Neka $p_i$ budu cjelobrojne varijable koje označavaju broj programera specijaliziranih za $i$-ti tehnološki okvir:

$p_1$: broj programera specijaliziranih za React
$p_2$: broj programera specijaliziranih za Vue.js
$p_3$: broj programera specijaliziranih za Angular
$p_4$: broj programera specijaliziranih za Ruby on Rails
$p_5$: broj programera specijaliziranih za Django

Funkcije cilja

Zasebne funkcije cilja:

\[ \max Z_1 = \sum_{i=1}^{5} o_i \cdot x_i \] – maksimizacija ocjene, gdje je $o_i$ ocjena $i$-tog okvira.

\[ \min Z_2 = \sum_{i=1}^{5} 320 \cdot c_i \cdot p_i \] – minimizacija troška plaća, uz cijenu sata $c_i$ i pretpostavku da svaki odabrani programer radi
40 sati tjedno tijekom 2 mjeseca (ukupno 320 sati).

Agregirana težinska funkcija cilja:

\[ \max \left( 0.4 \cdot \left( \sum_{i=1}^{5} o_i \cdot x_i \right) - 0.6 \cdot \left( \sum_{i=1}^{5} 320 \cdot c_i \cdot p_i \right)\right) \]

Što je Z veći, to je kombinacija više ocjene i manje troška povoljnija.

Ograničenja

Samo jedan okvir može biti odabran:

\[ \sum_{i=1}^{5} x_i = 1 \]

Ukupna cijena programera ne smije premašiti 68 000 eura:

\[ \sum_{i=1}^{5} 320 \cdot c_i \cdot p_i \le 68000, \] gdje je $c_i$ cijena programera po satu za $i$-ti okvir.

Potrebno je osigurati dovoljno programerskih sati (1920 sati):

\[ \sum_{i=1}^{5} 320 \cdot p_i \ge 1920, \] uz pretpostavku da svaki programer radi 40 sati tjedno tijekom 2 mjeseca (320 sati po programeru).

Povezanost okvira i programera (Big-M uvjet):

Napomena: Big-M uvjet detaljnije je objašenjen u štivu o cjelobrojnom i mješovitom programiranju

\[ p_i \le M \cdot x_i,\quad i = 1,\dots,5, \] gdje je $p_i$ broj programera specijaliziranih za $i$-ti tehnološki okvir,
$x_i$ binarna varijabla odluke, a $M$ proizvoljno odabran veliki broj (veći od bilo kojeg mogućeg $p_i$).

Da bismo ovo unijeli u solver, prebacujemo sve na lijevu stranu: \[ p_i - M \cdot x_i \le 0 \] (Gdje je $M$ veliki broj, npr. 50).

Binarna priroda varijabli $x_i$:

\[ x_i \in \{0,1\}, \quad \forall i \in \{1,2,3,4,5\} \]

Cjelobrojnost varijabli $p_i$:

\[ p_i \in \mathbb{Z}_+, \quad \forall i \in \{1,2,3,4,5\} \]

library(lpSolve)

# Definiranje ocjena i troškova
ocjene <- c(9 + 9 + 8,
            8 + 8 + 7,
            7 + 7 + 9,
            6 + 6 + 6,
            7 + 7 + 8)

cijene <- c(35, 30, 40, 45, 40)

# Agregirana funkcija cilja
# 0.4 * ocjene - 0.6 * troškovi
f.obj <- c(0.4 * ocjene, -0.6 * 320 * cijene)

# Matrica ograničenja
f.con <- rbind(
  c(1, 1, 1, 1, 1, 0, 0, 0, 0, 0),                 # samo jedan okvir
  c(rep(0, 5), cijene * 320),                      # budžet
  c(rep(0, 5), 320, 320, 320, 320, 320),           # sati rada
  # U matrici: koeficijent za x je -50, koeficijent za p je 1
  c(-50, 0, 0, 0, 0, 1, 0, 0, 0, 0),         # veza x1–p1
  c(0, -50, 0, 0, 0, 0, 1, 0, 0, 0),         # veza x2–p2
  c(0, 0, -50, 0, 0, 0, 0, 1, 0, 0),         # veza x3–p3
  c(0, 0, 0, -50, 0, 0, 0, 0, 1, 0),         # veza x4–p4
  c(0, 0, 0, 0, -50, 0, 0, 0, 0, 1)          # veza x5–p5
)

# Vektor smjerova ograničenja
f.dir <- c("=", "<=", ">=", rep("<=", 5))

# Desna strana ograničenja
f.rhs <- c(1, 68000, 1920, rep(0, 5))

# Binarne i cjelobrojne varijable
bin.vec <- 1:5
int.vec <- 6:10

# Rješavanje problema
solution <- lp("max",
               f.obj,
               f.con,
               f.dir,
               f.rhs,
               binary.vec = bin.vec,
               int.vec = int.vec,
               compute.sens = TRUE)

solution

## Success: the objective function is -34550.8

solution$solution

##  [1] 0 1 0 0 0 0 6 0 0 0

Dobiveni vektor rješenja (redoslijedom $(x_1,\dots,x_5,p_1,\dots,p_5)$) je:

$x_1 = 0$
$x_2 = 1$
$x_3 = 0$
$x_4 = 0$
$x_5 = 0$
$p_1 = 0$
$p_2 = 6$
$p_3 = 0$
$p_4 = 0$
$p_5 = 0$

Budući da je jedino $x_2 = 1$, a svi ostali $x_i = 0$, model bira Vue.js kao jedini tehnološki okvir. To je u skladu s ograničenjem $\sum_{i=1}^5 x_i = 1$, koje traži da se odabere točno jedan okvir.

Jedina pozitivna cjelobrojna varijabla je $p_2 = 6$, što znači da trebamo šest programera specijaliziranih za Vue.js. Svi ostali $p_i$ su nula, pa se programeri za ostale okvire ne angažiraju.

Ovo je u skladu s big-M ograničenjima tipa $p_i \le M \cdot x_i$:
budući da je samo za $i = 2$ vrijednost $x_i = 1$, samo $p_2$ smije biti veći od nule.

Svaki programer radi 40 sati tjedno tijekom 2 mjeseca, tj. ukupno
$40 \cdot 4 = 160$ sati mjesečno, odnosno $40 \cdot 8 = 320$ sati u dva mjeseca.

Za šest Vue.js programera to daje:

\[ 6 \cdot 320 = 1920 \text{ sati}, \]

što točno zadovoljava zahtjev projekta da se odradi barem 1920 sati razvoja.

Cijena sata Vue.js programera iznosi 30 € pa je ukupan trošak:

\[ \text{Trošak} = 6 \cdot 320 \cdot 30 = 57\,600 \, \text{€}, \]

što je manje od zadanog proračuna od 68 000 €. Ograničenje budžeta je zadovoljeno, ali nije vezujuće (ima slack - preostaje „lufta“ u budžetu).

Agregirana funkcija cilja koju maksimiziramo glasi:

\[ Z = 0.4 \cdot \text{ocjena} - 0.6 \cdot \text{trošak}. \]

Za Vue.js:

ukupna ocjena okvira (popularnost + zajednica + integracija) iznosi
$8 + 8 + 7 = 23$,
trošak je $57600$ €.

Uvrštavanjem u funkciju cilja:

\[ \max Z = 0.4 \cdot \left( \sum_{i=1}^{5} o_i \cdot x_i \right) - 0.6 \cdot \left( \sum_{i=1}^{5} 320 \cdot c_i \cdot p_i \right) \]

dobivamo:

\[ Z = - 0.6 \cdot 57600 + 0.4 \cdot 23 = - 34560 + 9.2 = - 34550.8. \]

Solver javlja upravo ovu vrijednost kao maksimalnu vrijednost funkcije cilja.

Model zaključuje da je, uz zadana ograničenja i zadane težine (0.4 za ocjenu i 0.6 za trošak), najbolji kompromis:

odabrati Vue.js kao tehnološki okvir,
angažirati 6 Vue.js programera,
pritom točno zadovoljiti zahtjev za satima rada (1920 sati),
ostati unutar budžeta (57 600 € < 68 000 €).

Iako postoji više okvira s različitim kombinacijama ocjene i cijene, nijedan od njih uz zadane težine ne pruža bolju (manju) vrijednost funkcije cilja od ove kombinacije.
Vue.js je, u ovom modelu, težinski najpovoljniji odabir.

Do sada smo koristili fiksne težine ($w_{ocjena}=0.4$, $w_{trosak}=0.6$) i dobili Vue.js kao pobjednika. No, postavlja se pitanje: Postoji li scenarij u kojem bismo odabrali React? (On je skuplji, ali ima bolju ocjenu). Ili neki treći okvir?

Da bismo to saznali, mijenjat ćemo važnost ocjene (w) od 0 do 1.

Napomena o skalama: Budući da su troškovi u desecima tisuća eura, a ocjene su dvoznamenkasti brojevi, trošak će matematički dominirati funkcijom cilja sve dok težina na ocjeni ne postane ekstremno visoka. Ipak, princip granice Pareto efikasnosti ostaje isti: tražimo rješenja gdje ne možemo dobiti bolju ocjenu bez da platimo više.

library(lpSolve)
library(ggplot2)

# Podaci
imena_okvira <- c("React", "Vue.js", "Angular", "Ruby on Rails", "Django")

# Ocjene (Popularnost + Zajednica + Integracija)
ocjene <- c(9 + 9 + 8,  # React = 26
            8 + 8 + 7,  # Vue = 23
            7 + 7 + 9,  # Angular = 23
            6 + 6 + 6,  # Ruby = 18
            7 + 7 + 8)  # Django = 22

cijene_po_satu <- c(35, 30, 40, 45, 40)
sati_ukupno <- 320 * 6 # 6 programera * 320 sati = 1920 sati (minimum)

# Fiksni trošak za svaki okvir (ako uzmemo minimalnih 6 programera)
troskovi_total <- cijene_po_satu * 1920

# Matrica ograničenja (Ista kao u prethodnom ispravnom modelu)
f.con <- rbind(
  c(1, 1, 1, 1, 1, 0, 0, 0, 0, 0),                 # 1. Samo jedan okvir
  c(rep(0, 5), cijene_po_satu * 320),              # 2. Budžet
  c(rep(0, 5), 320, 320, 320, 320, 320),           # 3. Sati rada
  # Big-M: p_i - 1000x_i <= 0
  c(-1000, 0, 0, 0, 0, 1, 0, 0, 0, 0),
  c(0, -1000, 0, 0, 0, 0, 1, 0, 0, 0),
  c(0, 0, -1000, 0, 0, 0, 0, 1, 0, 0),
  c(0, 0, 0, -1000, 0, 0, 0, 0, 1, 0),
  c(0, 0, 0, 0, -1000, 0, 0, 0, 0, 1)
)

f.dir <- c("=", "<=", ">=", rep("<=", 5))
f.rhs <- c(1, 68000, 1920, rep(0, 5))
bin.vec <- 1:5
int.vec <- 6:10

# Funkcija za rješavanje za težinu w (gdje je w važnost OCJENE)
solve_closeden_pareto <- function(w) {
  
  # Maksimiziramo: w * Ocjena - (1-w) * Trošak
  # Budući da su skale drastično različite, da bismo uopće vidjeli promjenu na grafu,
  # možemo uvesti faktor skaliranja samo za potrebe "okidača" promjene odluke,
  # ili jednostavno pustiti solver da računa s "raw" brojevima. 
  # Ovdje koristimo raw brojeve, ali ćemo u ispisu vidjeti da React pobjeđuje 
  # tek kad je w jako blizu 1 (ili ako 'Cost' ima malu težinu).
  
  obj_vec <- c(w * ocjene, -(1 - w) * 320 * cijene_po_satu)
  
  res <- lp("max", obj_vec, f.con, f.dir, f.rhs, binary.vec=bin.vec, int.vec=int.vec)
  
  # Identifikacija odabranog okvira
  chosen_index <- which(res$solution[1:5] == 1)
  
  if(length(chosen_index) == 0) return(NULL) # Ako nema rješenja
  
  # Stvarne vrijednosti
  real_score <- ocjene[chosen_index]
  real_cost <- troskovi_total[chosen_index]
  name <- imena_okvira[chosen_index]
  
  return(data.frame(Okvir = name, Ocjena = real_score, Trosak = real_cost))
}

# Generiramo rješenja.
# Zbog osjetljivosti skale, koristimo logiku:
# React košta ~10.000 više, a donosi 3 boda više.
# Točka prijelaza je kad nam 3 boda vrijede više od 10.000 €.
# Solver će to naći sam ako prođemo kroz dovoljno težina.

weights <- seq(0, 1, by = 0.001) 
pareto_results <- do.call(rbind, lapply(weights, solve_closeden_pareto))

# Uzimamo samo jedinstvene točke
pareto_unique <- unique(pareto_results)

# Vizualizacija
ggplot(pareto_unique, aes(x = Trosak, y = Ocjena)) +
  geom_point(aes(color = Okvir), size = 5) +
  geom_text(aes(label = paste(Okvir, "\n", Trosak, "€\n", Ocjena, "b")), 
            vjust = -0.5, size = 3.5) +
  labs(title = "Pareto granica: Izbor okvira (Closeden)",
       subtitle = "Samo Vue.js i React su efikasne opcije. Ostali su dominirani.",
       x = "Ukupni trošak (€) - Manje je bolje",
       y = "Ukupna ocjena (bodovi) - Više je bolje") +
  theme_minimal() +
  scale_x_continuous(limits = c(50000, 75000)) +
  scale_y_continuous(limits = c(20, 30))

Od 5 mogućih opcija, graf je pokazao da su samo dvije ekonomski racionalne (Pareto efikasne):

Vue.js: Najbolji izbor ako želimo minimizirati trošak. Košta 57.600 € i daje ocjenu 23.
React: Najbolji izbor ako želimo maksimizirati kvalitetu. Košta 67.200 € i daje ocjenu 26.

Svi ostali okviri (Angular, Ruby, Django) se ne pojavljuju na grafikonu. Zašto? Zato što su dominirani.

Na primjer, Angular ima istu ocjenu kao Vue.js (23), ali košta znatno više (76.800 €). Nema nikakvog razloga odabrati Angular uz ove kriterije.
Django ima manju ocjenu od Vue.js (22 < 23), a veću cijenu.

Dilema se svodi na jednostavno pitanje: “Isplati li nam se platiti dodatnih 9.600 € (razlika između Reacta i Vuea) za 3 dodatna boda u ocjeni kvalitete”? Ako je odgovor da, biramo React. Ako ne, biramo Vue.js. To je suština Pareto analize.

Primjeri - kombinacija s predznanjem

Višeciljno programiranje + mrežni modeli

Tvrtka StreamNow dnevno prenosi velik volumen video-prometa između glavnog podatkovnog centra u Zagrebu (čvor Z) i rezervnog podatkovnog centra u Amsterdamu (čvor A).

Promet se može slati preko tri različita operatorska backbone-ruta:

Ruta preko Frankfurta (F)
Ruta preko Beča (V)
Ruta preko Milana (M)

Svaka ruta ima:

cijenu po jedinici prometa (€/TB),
prosječnu mrežnu latenciju (ms),
maksimalni kapacitet (TB/dan).

Tvrtka svaki dan mora prenijeti ukupno 120 TB podataka iz Z u A.

Podaci po ruti:

Ruta	Oznaka	Cijena (€/TB)	Latencija (ms)	Kapacitet (TB/dan)
Z – F – A	1	8	20	80
Z – V – A	2	5	35	90
Z – M – A	3	4	45	70

Tvrtka može raspodijeliti promet na više ruta (npr. dio preko Frankfurta, dio preko Beča…).

Međutim, pritom želi istovremeno:

minimizirati ukupni dnevni trošak prijenosa i
minimizirati prosječnu latenciju koju korisnici doživljavaju.

Ovo je tipičan primjer višeciljnog mrežnog programiranja: postoji jasan trade-off – jeftinije rute imaju veću latenciju.

Kako bismo postavili model ciljnog programiranja, prvo moramo definirati ciljne vrijednosti (aspiracije).

Pretpostavimo sljedeći scenarij menadžmenta:

Cilj troška: Želimo da ukupni dnevni trošak bude 600 € (što je prosjek od 5 €/TB).
Cilj latencije: Želimo da prosječna latencija bude 30 ms.

Budući da želimo minimizirati i trošak i latenciju, želimo minimizirati prvenstveno pozitivna odstupanja (prekoračenja). Ako potrošimo manje ili je latencija manja (negativno odstupanje), to je dobro i ne “kažnjavamo”. Dakle, ovdje bi imalo smisla proizvoljno zadati težine.

Varijable odluke

Neka $x_i$ označava količinu prometa (u TB) prenesenu preko rute $i$:

$x_1$ – promet preko Frankfurta
$x_2$ – promet preko Beča
$x_3$ – promet preko Milana

Varijable odstupanja za ciljeve:

$df_C^+, df_C^-$ – odstupanja od ciljanog troška (Cost)
$df_L^+, df_L^-$ – odstupanja od ciljane latencije (Latency)

Funkcija cilja

Budući da želimo da trošak ne prelazi 600 € i latencija ne prelazi 30 ms, u funkciji cilja minimiziramo pozitivna odstupanja ($df^+$). Možemo dodati i težine ($w_C, w_L$) ako nam je npr. latencija važnija od troška.

\[ \min Z = w_C \cdot df_C^+ + w_L \cdot df_L^+ \] (Minimiziramo prekoračenje budžeta i prekoračenje ciljane latencije)

Recimo da je latencija dvostruko važnija od troška, pa zadajemo $w_L=2$ i $w_C=1$.

Ograničenja

Ukupan promet mora biti točno 120 TB: \[ x_1 + x_2 + x_3 = 120 \]

Kapaciteti pojedinih ruta ne smiju biti prekoračeni: \[ x_1 \le 80 \] \[ x_2 \le 90 \] \[ x_3 \le 70 \]

Cilj 1: Trošak

Ukupni trošak je suma umnožaka cijene i količine. Ciljamo 600 €.

\[ 8x_1 + 5x_2 + 4x_3 + df_C^- - df_C^+ = 600 \]

Cilj 2: Prosječna latencija

Prosječna latencija je (Ukupna latencija / Ukupni promet). Budući da je ukupan promet fiksiran na 120 TB, jednadžbu pišemo kao:

\[ \frac{20x_1 + 35x_2 + 45x_3}{120} + df_L^- - df_L^+ = 30 \]

Napomena: Radi lakšeg unosa u solver (izbjegavanja razlomaka), gornju jednadžbu često množimo sa 120:

\[ 20x_1 + 35x_2 + 45x_3 + 120 \cdot df_L^- - 120 \cdot df_L^+ = 3600 \]

3. Nenegativnost varijabli: \[ x_1, x_2, x_3, df_C^+, df_C^-, df_L^+, df_L^- \ge 0 \]

library(lpSolve)

# Definiramo redoslijed varijabli u vektorima i matrici:
# x1 (F), x2 (V), x3 (M), df_C-, df_C+, df_L-, df_L+
cvec <- c(0, 0, 0, 0, 1, 0, 2)

matA <- matrix(c(
  1, 1, 1, 0, 0, 0, 0,          # Ukupan promet = 120
  1, 0, 0, 0, 0, 0, 0,          # Kapacitet F <= 80
  0, 1, 0, 0, 0, 0, 0,          # Kapacitet V <= 90
  0, 0, 1, 0, 0, 0, 0,          # Kapacitet M <= 70
  8, 5, 4, 1, -1, 0, 0,         # Trošak: 8x1 + 5x2 + 4x3 + d- - d+ = 600
  20, 35, 45, 0, 0, 120, -120   # Latencija: 20x1 + 35x2 + 45x3 + 120d- - 120d+ = 3600
  ), ncol = 7, byrow = TRUE)

dirvec <- c("=", "<=", "<=", "<=", "=", "=")

rhsvec <- c(120, 80, 90, 70, 600, 3600)

rjesenje <- lp("min", cvec, matA, dirvec, rhsvec)

# Ispis rezultata
rjesenje

## Success: the objective function is 11.875

cat("Promet Frankfurt (x1):", rjesenje$solution[1], "TB\n",
    "Promet Beč (x2):      ", rjesenje$solution[2], "TB\n",
    "Promet Milano (x3):   ", rjesenje$solution[3], "TB\n",
    "Ukupan promet", rjesenje$solution[1] + rjesenje$solution[2]+rjesenje$solution[3], "TB\n",
    "Prekoracenje troška:  ", rjesenje$solution[5], "€\n",
    "Ukupan trošak", 8*rjesenje$solution[1] + 5*rjesenje$solution[2]+4*rjesenje$solution[3], "€\n",
    "Prekoracenje latencije:", rjesenje$solution[7], "ms\n",
    "Ukupna ponderirana latencija (ms·TB):", 20*rjesenje$solution[1] + 35*rjesenje$solution[2]+45*rjesenje$solution[3],
    "\nProsječna latencija:", (20*rjesenje$solution[1] + 35*rjesenje$solution[2]+45*rjesenje$solution[3])/120, "ms\n")

## Promet Frankfurt (x1): 7.5 TB
##  Promet Beč (x2):       90 TB
##  Promet Milano (x3):    22.5 TB
##  Ukupan promet 120 TB
##  Prekoracenje troška:   0 €
##  Ukupan trošak 600 €
##  Prekoracenje latencije: 5.9375 ms
##  Ukupna ponderirana latencija (ms·TB): 4312.5 
## Prosječna latencija: 35.9375 ms

Model nam daje najbolje moguće rješenje za specifične želje menadžera (cilj: 600€, 30ms, Težina latencije = 2). Pareto granica nam pokazuje sva moguća najbolja rješenja. Rezultat ciljnog programiranja je točno jedna točka na Pareto granici.

Ispitivanje Pareto efikasnosti

Ne možemo imati i najjeftiniji i najbrži prijenos istovremeno. Pareto granica će nam pokazati točnu “cijenu brzine” – koliko eura moramo platiti za svaku milisekundu smanjenja latencije.

Kako bismo ovo vizualizirali, maknut ćemo fiksne ciljeve (600€ i 30ms) i promatrati samo ograničenja mreže (ukupni promet 120 TB i kapaciteti ruta). Mijenjat ćemo težinu (w) od 0 do 1 u funkciji:

$\min \big(w \cdot \text{Ukupni trošak}+(1−w) \cdot \text{Prosječna latencija}$

library(lpSolve)
library(ggplot2)

# Koeficijenti troška (po TB)
c_cost <- c(8, 5, 4)

# Koeficijenti latencije (po TB). 
# Da bismo dobili prosjek u funkciji cilja, dijelimo s ukupnim prometom (120).
c_latency_avg <- c(20, 35, 45) / 120

# Tvrda ograničenja (samo fizička ograničenja mreže)
# x1 + x2 + x3 = 120
# x1 <= 80, x2 <= 90, x3 <= 70
mat_hard <- matrix(c(1, 1, 1,
                     1, 0, 0,
                     0, 1, 0,
                     0, 0, 1), 
                   nrow = 4, byrow = TRUE)

dir_hard <- c("=", "<=", "<=", "<=")
rhs_hard <- c(120, 80, 90, 70)

# Funkcija za generiranje Pareto točaka
solve_network_pareto <- function(w) {
  
  # Zbog razlike u skalama (Trošak je cca 600, Latencija cca 30),
  # latencija bi mogla biti zanemarena ako ne normaliziramo.
  # Ovdje ćemo koristiti jednostavni trik: 
  # w * Cost + (1-w) * (Latency * 10) 
  # Množenjem latencije s faktorom (npr. 10 ili 20) dovodimo je na sličan red veličine kao trošak
  # kako bi promjena w imala ljepši efekt na grafu.
  
  scaling_factor <- 20 
  
  # Funkcija cilja: w * Cost + (1-w) * Scaled_Latency
  obj_vec <- w * c_cost + (1 - w) * (c_latency_avg * scaling_factor)
  
  res <- lp("min", obj_vec, mat_hard, dir_hard, rhs_hard)
  
  # Izračun stvarnih vrijednosti (bez skaliranja)
  x <- res$solution
  
  real_cost <- sum(x * c_cost)
  real_latency <- sum(x * c_latency_avg) # Ovo je prosječna latencija
  
  return(data.frame(w = w, Cost = real_cost, Latency = real_latency))
}

# Generiranje točaka
weights <- seq(0, 1, by = 0.05)
pareto_net <- do.call(rbind, lapply(weights, solve_network_pareto))

# Vizualizacija
ggplot(pareto_net, aes(x = Latency, y = Cost)) +
  geom_point(color = "blue", size = 3) +
  geom_line(color = "darkgrey") +
  labs(title = "Pareto granica: StreamNow mreža",
       x = "Prosječna latencija (ms) - Manje je bolje",
       y = "Ukupni dnevni trošak (€) - Manje je bolje") +
  theme_minimal() +
  # Dodajemo oznake na krajnje točke
  geom_text(data = subset(pareto_net), 
            aes(label = paste0(round(Cost), "€\n", round(Latency,1), "ms")),
            vjust = -0.5, size = 3.5)

Ako naše rješenje ucrtamo na Pareto grafikon, vidjet ćemo da ono pada točno na liniju (ili vrlo blizu nje). To dokazuje da je rješenje efikasno.

Također, grafikon objašnjava zašto nismo postigli cilj od 30ms u prvom zadatku.

# 1. Izračun koordinata rješenja iz ciljnog programiranja
# (Podatke uzimamo iz outputa prvog dijela)

gp_trosak <- 8*rjesenje$solution[1] + 5*rjesenje$solution[2] + 4*rjesenje$solution[3]
gp_latencija_ukupna <- 4312.5 
gp_latencija_prosjecna <- gp_latencija_ukupna / 120 # Moramo pretvoriti u prosjek jer je x-os grafa prosjek

gp_tocka <- data.frame(
  Latency = gp_latencija_prosjecna,
  Cost = gp_trosak
)

# 2. Dodavanje te točke na postojeći Pareto grafikon
# (Koristimo 'pareto_net' objekt iz prethodnog chunka)

ggplot(pareto_net, aes(x = Latency, y = Cost)) +
  # Linija Pareto granice
  geom_line(color = "darkgrey") +
  geom_point(color = "blue", size = 2) +
  
  # Naše specifično GP rješenje (Crvena točka)
  geom_point(data = gp_tocka, aes(x = Latency, y = Cost), 
             color = "red", size = 5, shape = 18) +
  
  # Oznake
  geom_text(data = gp_tocka, 
            aes(label = paste("GP Rješenje:\n", round(Cost), "€, ", round(Latency, 1), "ms")), 
            vjust = 1.5, fontface = "bold", color = "red") +
  
  labs(title = "Pozicija GP rješenja na Pareto granici",
       x = "Prosječna latencija (ms)",
       y = "Ukupni dnevni trošak (€)") +
  theme_minimal()

Ovaj grafikon nam daje koristan menadžerski uvid:

Efikasnost: naše rješenje (crvena točka) nalazi se točno na liniji. To znači da je matematički nemoguće postići manju latenciju za 600 €, niti manji trošak za 35.9 ms.
- Objašnjenje neuspjeha: U ciljnom programiranju htjeli smo 30 ms i 600 €.
- Točka (30 ms, 600 €) nalazi se ispod sive linije.
- To područje je nedostižno (Infeasible).
- Da bismo stvarno dobili 30 ms (pomičući se lijevo po x-osi), morali bismo se popeti po liniji gore do troška od otprilike 700-750 €.

Ciljno/ višeciljno programiranje je, dakle, metoda kojom utvrđujemo jednu specifičnu točku Pareto granice koja najbolje odgovara našim zadanim prioritetima, dok nam Pareto analiza daje širu sliku svih mogućih opcija.

Višeciljno programiranje + problem pridruživanja

Nakon velikog kibernetičkog napada, tvrtka mora hitno formirati “Tiger Team” od 4 stručnjaka za 4 ključna zadatka. Svaki stručnjak može raditi točno jedan zadatak.

Potrebno je dodijeliti 4 vrhunska stručnjaka (Ivan, Marko, Ana, Petra) na 4 hitna zadatka:

Forenzika (Z1)
Oporavak baze (Z2)
Sigurnosna zakrpa (Z3)
PR i komunikacija (Z4)

Menadžment ima dva suprotstavljena cilja:

Minimizirati ukupno vrijeme rješavanja (zbroj sati potrebnih da se zadaci završe).
Maksimizirati kvalitetu izvedbe (zbroj ocjena kvalitete rješenja, skala 1-100)

Procijenjeno vrijeme (u satima) – Manje je bolje:

Stručnjak	Forenzika (Z1)	Oporavak (Z2)	Zakrpa (Z3)	PR (Z4)
Ivan	9	15	11	22
Marko	18	19	14	9
Ana	12	10	16	18
Petra	20	25	10	24

Ocjena kvalitete (bodovi 0-100) – Više je bolje:

Stručnjak	Forenzika (Z1)	Oporavak (Z2)	Zakrpa (Z3)	PR (Z4)
Ivan	60	85	70	95
Marko	90	95	80	70
Ana	75	65	90	85
Petra	98	99	60	92

Budući da je situacija kritična, menadžment je odlučio da je brzina (vrijeme) prioritet s težinom 0.7, dok je kvaliteta sekundarna s težinom 0.3. No, budući da su mjerne jedinice različite (sati vs. bodovi), i smjerovi su različiti (min vs. max), moramo pažljivo postaviti funkciju cilja.

Varijable odluke:

Neka je $x_{ij}$ binarna varijabla: \[ x_{ij} = \begin{cases} 1, & \text{ako stručnjak } i \text{ radi zadatak } j \\ 0, & \text{inače} \end{cases} \] gdje je $i \in \{\text{Ivan, Marko, Ana, Petra}\}$, a $j \in \{Z1, Z2, Z3, Z4\}$.

Funkcija cilja (težinska):

Ovdje imamo specifičan izazov: 1. Jedan cilj je MIN (sati), drugi je MAX (kvaliteta). 2. Da bismo ih spojili u jednu funkciju minimalizacije, problem maksimizacije kvalitete pretvaramo u minimizaciju tako da mu promijenimo predznak (oduzimamo kvalitetu).

Funkcija cilja glasi:

\[ \min Z = 0.7 \cdot (\text{Ukupni sati}) - 0.3 \cdot (\text{Ukupna kvaliteta}) \]

Matematički zapisano:

\[ \min \sum_{i=1}^4 \sum_{j=1}^4 (0.7 \cdot t_{ij} - 0.3 \cdot k_{ij}) \cdot x_{ij} \]

gdje je $t_{ij}$ vrijeme (iz Tablice 1), a $k_{ij}$ kvaliteta (iz Tablice 2). Napomena: Što je veća kvaliteta, to više oduzimamo od funkcije cilja, čime ona postaje manja (bolja).

Ograničenja (klasična):

Svaki stručnjak mora dobiti točno jedan zadatak: \[ \sum_{j=1}^4 x_{ij} = 1, \quad \text{za svakog stručnjaka } i \]
Svaki zadatak mora obavljati točno jedan stručnjak: \[ \sum_{i=1}^4 x_{ij} = 1, \quad \text{za svaki zadatak } j \]
Binarnost varijabli: \[ x_{ij} \in \{0, 1\} \]

library(lpSolve)
# Matrica vremena (sati)
time_mat <- matrix(c(9, 15, 11, 22,
                     18, 19, 14,  9,
                     12, 10, 16, 18,
                     20, 25, 10, 24), 
                   nrow=4, byrow=TRUE)

# Matrica kvalitete (bodovi)
quality_mat <- matrix(c(60, 85, 70, 95,
                        90, 95, 80, 70,
                        75, 65, 90, 85,
                        98, 99, 60, 92), 
                      nrow=4, byrow=TRUE)

# Težine
w_time <- 0.7
w_qual <- 0.3

# Kombinirana matrica troškova za solver
cost_matrix <- (w_time * time_mat) - (w_qual * quality_mat)

# Ispis kombinirane matrice 
# (Niži brojevi su bolji za odabir)
print("Kombinirana matrica troškova (težinski prilagođena):")

## [1] "Kombinirana matrica troškova (težinski prilagođena):"

print(cost_matrix)

##       [,1]  [,2]  [,3]  [,4]
## [1,] -11.7 -15.0 -13.3 -13.1
## [2,] -14.4 -15.2 -14.2 -14.7
## [3,] -14.1 -12.5 -15.8 -12.9
## [4,] -15.4 -12.2 -11.0 -10.8

# Rješavanje problema pridruživanja
# lp.assign automatski postavlja binarna ograničenja i ograničenja redaka/stupaca
res <- lp.assign(cost_matrix)

res

## Success: the objective function is -60.9

# Prikaz rješenja u obliku matrice
print("Optimalno pridruživanje (1 = dodijeljen):\n",)

## [1] "Optimalno pridruživanje (1 = dodijeljen):\n"

print(res$solution)

##      [,1] [,2] [,3] [,4]
## [1,]    0    1    0    0
## [2,]    0    0    0    1
## [3,]    0    0    1    0
## [4,]    1    0    0    0

# Izračun stvarnih vrijednosti za odabrano rješenje
total_time <- sum(res$solution * time_mat)
total_quality <- sum(res$solution * quality_mat)

cat("Ukupno vrijeme tima:", total_time, "sati\n",
    "Ukupna kvaliteta tima:", total_quality, "bodova\n")

## Ukupno vrijeme tima: 60 sati
##  Ukupna kvaliteta tima: 343 bodova

Kod kontinuiranih problema, Pareto granica je glatka krivulja. Kod binarnih problema (poput ovog), Pareto granica je skup diskretnih točaka. Naime, ne možete uzeti “pola Ivana” i “pola Marka”. Kako mijenjamo težine, rješenje će dugo ostati isto, a onda naglo “skočiti” na drugu kombinaciju ljudi.

Budući da su naši ciljevi u konfliktu (brzina često znači manju kvalitetu i obrnuto), ne postoji jedan savršeni tim. Postoji samo skup najboljih mogućih kompromisa.

U binarnom programiranju, za razliku od financijskog portfelja gdje možemo fino ugađati postotke, rješenja su diskretna. To znači da nećemo dobiti glatku krivulju, već nekoliko specifičnih kombinacija timova koje predstavljaju Pareto granicu.

Analizirajmo to promjenom težine (w) za vrijeme od 0 do 1. Funkcija koju minimiziramo bit će: $Z=w \cdot \text{Vrijeme}−(1−w) \cdot \text{Kvaliteta}$

library(lpSolve)
library(ggplot2)

# 1. Definiranje matrica
time_mat <- matrix(c(9, 15, 11, 22,
                     18, 19, 14,  9,
                     12, 10, 16, 18,
                     20, 25, 10, 24), 
                   nrow=4, byrow=TRUE)

quality_mat <- matrix(c(60, 85, 70, 95,
                        90, 95, 80, 70,
                        75, 65, 90, 85,
                        98, 99, 60, 92), 
                      nrow=4, byrow=TRUE)

# 2. Funkcija za rješavanje za zadani w
# w je težina za VRIJEME (koje minimiziramo)
# (1-w) je težina za KVALITETU (koju maksimiziramo -> dakle oduzimamo u min funkciji)

solve_assignment_pareto <- function(w) {
  
  # Kombinirana matrica troškova
  # cost = w * Time - (1-w) * Quality
  cost_mat <- (w * time_mat) - ((1 - w) * quality_mat)
  
  # Rješavanje problema pridruživanja
  res <- lp.assign(cost_mat)
  
  # Izračunavanje stvarnih vrijednosti rješenja
  # Množimo binarno rješenje (0 ili 1) s originalnim matricama
  actual_time <- sum(res$solution * time_mat)
  actual_quality <- sum(res$solution * quality_mat)
  
  return(data.frame(
    w_time = w,
    Total_Time = actual_time,
    Total_Quality = actual_quality
  ))
}

# 3. Generiranje rješenja za niz težina
weights <- seq(0, 1, by = 0.02) # Fini korak da uhvatimo sve promjene
pareto_results <- do.call(rbind, lapply(weights, solve_assignment_pareto))

# Uklanjanje duplikata (jer za npr. w=0.4 i w=0.42 rješenje može biti isto)
pareto_results <- unique(pareto_results[, c("Total_Time", "Total_Quality")])

# 4. Vizualizacija
ggplot(pareto_results, aes(x = Total_Time, y = Total_Quality)) +
  geom_point(size = 4, color = "darkred") +
  geom_line(linetype = "dashed", color = "gray") +
  geom_text(aes(label = paste(Total_Time, "h /", Total_Quality, "b")), 
            vjust = -1, size = 3.5) +
  labs(title = "Pareto granica: Krizni tim",
       subtitle = "Diskretne opcije pridruživanja zadataka",
       x = "Ukupno vrijeme (Manje je bolje)",
       y = "Ukupna kvaliteta (Više je bolje)") +
  theme_minimal() +
  scale_x_continuous(limits = c(min(pareto_results$Total_Time)-2, max(pareto_results$Total_Time)+2)) +
  scale_y_continuous(limits = c(min(pareto_results$Total_Quality)-10, max(pareto_results$Total_Quality)+10))

Interpretacija grafikona:

Idealni smjer: Na ovom grafikonu najbolje mjesto je gore-lijevo. Tamo je kvaliteta maksimalna (visoko na y-osi), a vrijeme minimalno (lijevo na x-osi).
Diskretne točke: Vidimo da nemamo beskonačno puno opcija. Postoji samo nekoliko efikasnih kombinacija tima. Na primjer:
Možemo dobiti tim koji završi posao za 38 sati, ali kvaliteta pada na 255 bodova.
- Ako želimo maksimalnu kvalitetu od 378 bodova, posao će trajati 77 sati.
- Između te dvije krajnosti postoji nekoliko kompromisnih rješenja.
Dominacija: Bilo koja kombinacija tima koja bi rezultirala točkom koja se nalazi ispod ili desno od ovih točaka bila bi loša odluka (potrošili bismo više vremena za istu ili manju kvalitetu).

Ovo menadžmentu daje jasan pregled opcija: “Koliko ste kvalitete spremni žrtvovati za svakih sat vremena uštede?”

U ovim smo primjerima povezali ciljno i višeciljno programiranje s modelima koje već poznajete otprije - mrežnim tokovima, transportom, problemom pridruživanja i mješovitim cjelobrojnim modelima. Ideja je uvijek ista: postoje ciljevi (profit, trošak, vrijeme, rizik, emisije…) koje bi klasični LP teško obuhvatio jednim skalarnim kriterijem, dok GP/MOLP omogućuju da ciljeve izrazimo eksplicitno i da odstupanja od njih kvantificiramo. Time dobivamo ne samo vrijednost rješenja, nego i dodatne uvide o ostvarivosti, kompromisima i Pareto-efikasnim alternativama. Zadaci za vježbu u nastavku zamišljeni su tako da isti obrazac možete samostalno primijeniti u novim kontekstima.

Zadaci za vježbu

Slučaj 1

Tvrtka “BioSokovi” proizvodi tri vrste hladno prešanih sokova: Detox (povrće), Energy (voće) i Balance (miks).

Za proizvodnju jedne litre soka potrebni su sljedeći resursi (u kg voća/povrća i minutama rada stroja):

Resurs	Detox	Energy	Balance
Voće (kg)	0.2	1.5	0.8
Povrće (kg)	1.8	0.0	0.7
Strojna obrada (min)	5	4	6
Profit po litri (€)	2.5	2.0	3.0

Tvrtka na tjednoj bazi raspolaže s maksimalno 2000 kg voća i 1500 kg povrća (to su zalihe koje se ne mogu prekoračiti jer bi se pokvarile). Stroj je fizički dostupan najviše 100 sati tjedno.

Uprava je postavila sljedeće ciljeve za nadolazeći tjedan:

Žele ostvariti ukupni profit od točno 5000 €.
Zbog ugovora s lokalnim teretanama, žele proizvesti točno 300 litara Detox soka.
Žele optimalno iskoristiti stroj, odnosno ciljaju na iskorištenost od 6000 minuta (kako bi opravdali amortizaciju, ali bez prekovremenih sati).

Postavite model koji minimizira ukupna odstupanja od zadanih ciljeva, strogo poštujući ograničenja zaliha i maksimalnog vremena stroja.

Slučaj 2

Agencija organizira veliku IT konferenciju i mora formirati timove za podršku. Na raspolaganju su tri tipa osoblja: Studenti, Profesionalni domaćini/hostese i Tehničari.

Troškovi i učinkovitost po osobi (po danu) su:

Tip osoblja	Dnevnica (€)	Kapacitet (br. gostiju)	Tehnička kompetencija (bodovi 1-10)
Student	50	20	2
Profesionalac	100	50	4
Tehničar	150	10	9

Agencija mora poštovati sljedeća ograničenja:

Ukupan broj osoblja ne smije biti veći od 40 (zbog ograničenog kapaciteta garderobe i hrane za osoblje).
Mora biti angažiran najmanje 1 tehničar na svakih 10 ostalih članova tima (studenata i profesionalaca zajedno).

Osim toga, menadžer projekta ima sljedeće ciljeve:

Ukupni budžet za dnevnice trebao bi iznositi 3500 €.
Tim mora biti sposoban uslužiti ciljanu brojku od 1200 gostiju (manjak kapaciteta je problem).
Ukupna tehnička kompetencija tima (zbroj bodova svih članova) trebala bi biti barem 150 bodova.

Formulirajte problem tako da se minimiziraju sva nepoželjna odstupanja.

Slučaj 3

Tvrtka “FitBox” priprema gotove obroke za sportaše. Trenutno dizajniraju novi veganski ručak koji se sastoji od mješavine tri sastojka: Seitan, Smeđe riže i Brokule.

Nutritivne vrijednosti i cijena po 100g namirnice:

Sastojak (100g)	Proteini (g)	Ugljikohidrati (g)	Masti (g)	Cijena (€)
Seitan	30	0	3	1.20
Smeđa riža	3	25	1	0.30
Brokula	3	7	0	0.50

Fizičko ograničenje ambalaže nalaže da ukupna masa obroka ne smije prelaziti 500g. Također, zbog okusa i teksture, u obroku mora biti barem 50g brokule. Cijena proizvodnje obroka trebala bi biti do 2.50 €.

Nutricionist je postavio sljedeće ciljeve za “idealan” obrok:

Obrok treba imati točno 40g proteina.
Obrok treba imati točno 50g ugljikohidrata.

Postavite model koji pronalazi optimalne količine sastojaka (u jedinicama od 100g ili gramima) kako bi se masa i minimalna količina brokule strogo poštivale, a odstupanja od nutritivnih ciljeva i ciljane cijene bila minimalna.

Slučaj 4

Direktorica marketinga planira kampanju za novi parfem. Na raspolaganju su tri kanala oglašavanja: Društvene mreže, TV reklame i Jumbo plakati.

Podaci po jedinici oglašavanja (jedna objava/emitiranje/plakat):

Kanal	Doseg (ljudi)	Cijena (€)	Angažman (klikovi/pozivi)
Društvene mreže	5000	200	500
TV reklama	50000	4000	100
Jumbo plakat	20000	1500	50

Dostupan je budžet od 50000 €.
Mora se zakupiti barem 5 Jumbo plakata zbog vidljivosti u gradu.
Želi se ostvariti barem 10000 angažmana.

Ciljevi kampanje:

Postići ukupan doseg od 800.000 ljudi. (Manjak dosega je nepoželjan).
Zakupiti točno 20 objava na društvenim mrežama (kako ne bi “spamali” korisnike previše, ali niti bili nevidljivi).

Utvrdite optimalnu raspodjelu oglasa prema kanalima oglašavanja, na način da poštujete dostupne resurse i približite se što više zadanim ciljevima.

Slučaj 5

Logistička tvrtka “EcoLog” mora prevesti 100 tona tereta iz skladišta A u skladište B. Na raspolaganju imaju dvije vrste vozila: Dizelski kamioni i Električni kombiji.

Karakteristike jednog vozila (za jednu turu):

Vozilo	Kapacitet (tone)	Trošak (€)	Emisija CO2 (kg)	Vrijeme utovara (h)
Dizelski kamion	20	500	100	2
Električni kombi	5	100	10	1

Svi tereti moraju biti prevezeni (ukupni kapacitet odabranih vozila $\ge$ 100 tona).
Na raspolaganju je maksimalno 15 vozača (svako vozilo treba jednog vozača).

Tvrtka ima tri konfliktna cilja, ali oni nisu jednako važni upravi:

Ekološki cilj: Žele da ukupna emisija CO2 bude maksimalno 400 kg. Ovo je prioritet zbog imidža tvrtke (“zeleno poslovanje”).
Financijski cilj: Žele da ukupni trošak bude 2.500 €.
Operativni cilj: Žele da ukupno vrijeme utovara bude 20 sati.

Uprava je definirala prioritete kroz težine:

Prekoračenje emisije CO2 je najgori ishod – težina 0.5.
Prekoračenje budžeta je srednje važno – težina 0.3.
Prekoračenje vremena utovara je manje važno – težina 0.2.
Pozitivna odstupanja (npr. manja emisija ili manji trošak od cilja) se ne kažnjavaju.

Definirajte funkciju cilja koristeći zadane težine kako biste pronašli optimalan broj kamiona i kombija.

Pitanja za ponavljanje

1. Slučaj: Tvornica namještaja postavila je cilj proizvodnje od točno 500 stolica tjedno. Nakon tjedan dana, izvještaj pokazuje da je stvarna proizvodnja iznosila 480 stolica. U modelu ciljnog programiranja, koje vrijednosti poprimaju varijable odstupanja za ovaj cilj?

1. $d^- = 20, \quad d^+ = 20$
1. $d^- = 20, \quad d^+ = 0$
1. $d^- = 0, \quad d^+ = 20$
1. $d^- = -20, \quad d^+ = 0$

2. Slučaj: Menadžer projekta ima budžet od 10.000 €, ali je rečeno da je to “meko” ograničenje. Ipak, poželjno je da trošak ne prelazi taj iznos (manjak troška je prihvatljiv i poželjan). Kako glasi funkcija cilja ako želimo minimizirati samo nepoželjno odstupanje?

1. $\min (d^-)$
1. $\min (d^+ + d^-)$
1. $\min (d^+)$
1. $\min (10000 - d^+)$

3. Slučaj: Restoran želi imati barem 10 konobara u smjeni vikendom kako bi održao kvalitetu usluge. Ako postavimo ciljno ograničenje $x_{konobari} + d^- - d^+ = 10$, koju varijablu moramo minimizirati u funkciji cilja da bismo zadovoljili zahtjev “barem”?

1. Minimiziramo $d^-$, jer ono predstavlja manjak radnika u odnosu na cilj.
1. Minimiziramo $d^+$, jer ne želimo previše radnika zbog troškova.
1. Minimiziramo $d^+ + d^-$, jer želimo točno 10 radnika.
1. Ne minimiziramo ništa, ovo moramo zapisati kao klasično ograničenje ($\ge$).

4. Slučaj: Prilikom rješavanja modela za jedan specifičan cilj (npr. dobit = 100), solver je vratio rezultat gdje su $d^- = 5$ i $d^+ = 12$. Što možemo zaključiti o ovom rješenju?

1. Cilj je premašen za 7 jedinica.
1. Rješenje je neinterpretabilno u smislu “koliko smo iznad ili ispod cilja” (istovremeno si i ispod i iznad), a u dobro postavljenom GP modelu i s razumnom funkcijom cilja optimalno rješenje u praksi neće imati oba > 0.
1. Rješenje je optimalno i pokazuje visoku fleksibilnost sustava.
1. Stvarna vrijednost je točno između tih vrijednosti.

5. Slučaj: Turistička agencija želi ostvariti prihod od točno 200.000 €. Koje je ispravno ograničenje cilja u linearnom modelu?

1. $\text{Prihod} + d^- + d^+ = 200000$
1. $\text{Prihod} - d^- + d^+ = 200000$
1. $\text{Prihod} + d^- - d^+ = 200000$
1. $\text{Prihod} \le 200000 + d^+$

6. Slučaj: Tvrtka proizvodi prehrambeni proizvod i ima dva cilja: (1) zadržati razinu alergena točno na 0g (zakonski propis, strogo) i (2) zadržati cijenu ambalaže na 0.5€ (interna želja). Odstupanje od zakonskog propisa je nedopustivo, dok je cijena fleksibilna. Kako biste postavili težine u funkciji cilja $\min (w_1 d_1^+ + w_2 d_2^+)$?

1. $w_1 = 1, \quad w_2 = 1$ (jednaka važnost)
1. $w_1 = 1, \quad w_2 = 1000$ (cijena je važnija jer se češće mijenja)
1. $w_1 = 1000, \quad w_2 = 1$ (zakonski propis je drastično važniji)
1. $w_1 = 0, \quad w_2 = 1$ (zakon se podrazumijeva pa ga ne treba stavljati u funkciju cilja)

7. Slučaj: Gradska čistoća ima cilj prikupiti 50 tona otpada. Funkcija cilja je definirana kao $\min (5 \cdot d^- + 1 \cdot d^+)$. Što ova funkcija govori o preferencijama uprave?

1. Upravi je pet puta gori ishod prikupiti manje otpada nego što su planirali, nego prikupiti više.
1. Upravi je pet puta gori ishod prikupiti više otpada, jer to stvara trošak deponiranja.
1. Uprava želi točno 50 tona i svako odstupanje jednako kažnjava, brojevi su samo radi skaliranja.
1. Težine nemaju utjecaj ako je cilj nedostižan.

8. Slučaj: Rješavali smo problem s dva cilja: Dobit (cilj 100k) i Rizik (cilj 10%). Postavili smo težine tako da je Dobit dominantna ($w_{dobit}=100, w_{rizik}=1$). Rezultat modela pokazuje da je $d_{dobit}^- = 0$, ali je $d_{rizik}^+ = 5\%$. Kako interpretiramo rezultat?

1. Model je neispravan jer nije zadovoljio oba cilja.
1. Zbog visoke težine na dobiti, model je “žrtvovao” cilj rizika kako bi u potpunosti ispunio prioritetniji cilj dobiti.
1. Težine su bile premale da bi utjecale na rješenje.
1. Rješenje je neefikasno jer sigurno postoji rješenje s manjim rizikom i istom dobiti.

9. Slučaj: U funkciji cilja $\min (w_A d_A^- + w_B d_B^-)$, postavili smo $w_A = 0.6$ i $w_B = 0.4$. Koja tvrdnja najbolje opisuje odnos ciljeva?

1. Cilj A će sigurno biti zadovoljen prije cilja B.
1. Jedinica odstupanja od cilja A “boli” (kažnjava se) 50% više nego jedinica odstupanja od cilja B ($0.6/0.4 = 1.5$).
1. Zbroj težina mora biti 1, inače solver neće raditi ispravno.
1. Model će ignorirati cilj B dok se cilj A ne ispuni u potpunosti (leksički pristup).

10. Slučaj: Želimo da broj radnih sati tima bude u rasponu između 160 i 180 sati mjesečno. Kako to modeliramo težinskim ciljnim programiranjem?

1. Postavimo dva cilja: $Cilj_1 = 160$ i $Cilj_2 = 180$. U funkciji cilja minimiziramo $d_1^-$ (manjak od donje granice) i $d_2^+$ (višak od gornje granice).
1. Postavimo jedan cilj na sredinu (170) i minimiziramo oba odstupanja.
1. Postavimo cilj na 180 i minimiziramo samo $d^-$.
1. To se ne može riješiti ciljnim programiranjem, moramo koristiti isključivo tvrda ograničenja.

11. Slučaj: Imamo dva investicijska portfelja s ciljem maksimizacije dobiti i minimizacije rizika. Portfelj A: Dobit = 50, Rizik = 5. Portfelj B: Dobit = 60, Rizik = 5. Koji je odnos između A i B?

1. A i B su oba Pareto efikasna rješenja.
1. A dominira B (A je bolji).
1. B dominira A (jer nudi veću dobit za isti rizik).
1. Ne možemo ih usporediti bez informacija o težinama.

12. Slučaj: Promatramo grafikon Pareto granice gdje je os X “Trošak” (minimizacija), a os Y “Kvaliteta” (maksimizacija). Gdje se u odnosu na Pareto granicu nalaze rješenja koja su “dominirana” (neučinkovita)?

1. Iznad/Lijevo od linije granice.
1. Točno na liniji granice.
1. Ispod/Desno od linije granice (imaju veći trošak za istu kvalitetu, ili manju kvalitetu za isti trošak).
1. U ishodištu koordinatnog sustava.

13. Slučaj: Što predstavlja “idealna točka” (Utopia point) u višeciljnom programiranju?

1. Rješenje koje zadovoljava sve menadžerske želje u praksi.
1. Teoretska točka sastavljena od najboljih individualnih vrijednosti svakog cilja zasebno, koja je u konfliktnim problemima obično nedostižna.
1. Točka sjecišta svih tvrdih ograničenja.
1. Rješenje gdje su vrijednosti svih funkcija cilja jednake nuli.

14. Slučaj: Imamo dva konfliktna cilja: Minimizirati emisiju CO2 i Minimizirati cijenu vozila. Ako se krećemo po Pareto granici i odabiremo vozila sa sve manjom emisijom CO2, što se mora dogoditi s cijenom (prema definiciji Pareto efikasnosti)?

1. Cijena se mora smanjiti.
1. Cijena se mora povećati (to je cijena “trade-offa”).
1. Cijena ostaje ista.
1. Cijena se ponaša nasumično.

15. Slučaj: Rješavanjem binarnog problema dobili smo skup od 5 diskretnih Pareto optimalnih rješenja. Ako menadžer odabere rješenje koje nije jedno od tih 5 rješenja, što to implicira?

1. Da je menadžer pronašao inovativno rješenje koje solver nije vidio.
1. Da je odabrano rješenje neefikasno (postoji neko od onih 5 koje je bolje po barem jednom kriteriju bez pogoršanja drugog) ili je nedopustivo.
1. Da je problem bio loše postavljen u startu.
1. Da su težine u solveru bile krivo postavljene.

16. Slučaj: U problemu izbora projekata imamo ciljeve: (1) Neto sadašnja vrijednost (NPV) - red veličine 1.000.000 €, i (2) Broj novih radnih mjesta - red veličine 10. Koristimo funkciju maksimizacije: $\max (0.5 \cdot NPV + 0.5 \cdot RadnaMjesta)$ bez normalizacije. Što će se dogoditi?

1. Model će jednako tretirati oba cilja zbog istih težina.
1. Model će gotovo potpuno ignorirati broj radnih mjesta jer NPV brojčano dominira funkcijom cilja.
1. Model će ignorirati NPV jer je prevelik broj za solver.
1. Solver će javiti grešku zbog različitih mjernih jedinica.

17. Slučaj: Kod binarnog problema (npr. odabir lokacije skladišta), Pareto granica nije glatka linija nego skup točaka. Postupno mijenjamo težinu troška $w$ od 0 do 1. Što očekujemo da će se dogoditi s rješenjem (varijablama odluke)?

1. Rješenje će se kontinuirano i polako mijenjati (malo po malo).
1. Rješenje će biti konstantno za određeni raspon težina, a zatim naglo “skočiti” na drugu kombinaciju lokacija.
1. Uvijek ćemo dobiti isto rješenje bez obzira na težine.
1. Dobit ćemo rješenje koje je kombinacija “pola skladišta A” i “pola skladišta B”.

18. Slučaj: Funkcija cilja je $\max (0.7 \cdot \text{Zadovoljstvo} - 0.3 \cdot \text{Cijena})$. Rezultat solvera za funkciju cilja je negativan broj (npr. -200). Što to znači?

1. Rješenje nije optimalno i treba ga odbaciti.
1. Tvrtka posluje s gubitkom i model sugerira gašenje.
1. To je matematički ispravan optimum; negativan predznak je posljedica toga što komponenta cijene (koju oduzimamo i koja je možda velik broj) brojčano nadmašuje komponentu zadovoljstva.
1. Treba promijeniti smjer optimizacije u min kako bismo dobili pozitivan broj.

19. Slučaj: Rješavamo transportni problem s dva cilja: Minimizirati Vrijeme i Minimizirati Trošak. Postavili smo $w_{vrijeme}=1$ i $w_{trosak}=0$ (ekstremni scenarij). Kakvo rješenje očekujemo?

1. Najjeftinije moguće rješenje, bez obzira na vrijeme.
1. Najbrže moguće rješenje, bez obzira na to koliko košta (npr. sve šaljemo avionom).
1. Balansirano rješenje negdje u sredini.
1. Rješenje koje minimizira oboje istovremeno.

20. Slučaj: Zašto u višeciljnom programiranju često koristimo normalizaciju podataka (skaliranje) prije primjene težina?

1. Da bismo sve brojeve pretvorili u cjelobrojne vrijednosti radi bržeg računanja.
1. Da bismo osigurali da varijable $d^+$ i $d^-$ budu pozitivne.
1. Da bismo sveli ciljeve na usporedivu skalu (npr. sve na raspon 0-1) i time omogućili da težine stvarno odražavaju važnost, a ne da ovise o mjernim jedinicama (milijuni vs. jedinice).
1. Normalizacija u višeciljnom programiranju zapravo nije potrebna i treba je izbjegavati.

Literatura

Anderson, D. R., Sweeney, D. J., Williams, T. A., Camm, J. D., & Cochran, J. J. (2012). Quantitative Methods for Business. Cengage Learning.

Broz, D., Vanzetti, N., Corsano, G., & Montagna, J. M. (2019). Goal programming application for the decision support in the daily production planning of sawmills. Forest Policy and Economics, 102, 29-40.

Dave, A. (2015). Goal programming applications in agricultural management. International Research Journal of Engineering and Technology (IRJET), 2(6), 883-887.

Foued, B. A., & Sameh, M. (2001). Application of goal programming in a multi-objective reservoir operation model in Tunisia. European Journal of Operational Research, 133(2), 352-361.

Ignizio, J. P. (1980). An introduction to goal programming with applications in urban systems. Computers, Environment and Urban Systems, 5(1-2), 15-33.

Karpak, B., Kumcu, E., & Kasuganti, R. (1999). An application of visual interactive goal programming: a case in vendor selection decisions. Journal of Multi‐Criteria Decision Analysis, 8(2), 93-105.

Lin, T. W., & O’Leary, D. E. (1993). Goal programming applications in financial management. Advances in mathematical programming and financial planning, 3(1), 211-30.

Price, W. L., & Piskor, W. G. (1972). The application of goal programming to manpower planning. INFOR: information systems and operational research, 10(3), 221-231.

Prišenk, J., Turk, J., Rozman, Č., Borec, A., Zrakić, M., & Pažek, K. (2014). Advantages of combining linear programming and weighted goal programming for agriculture application. Operational Research, 14(2), 253-260.

San Cristóbal, J. R. (2012). A goal programming model for environmental policy analysis: Application to Spain. Energy Policy, 43, 303-307.

Sen, N., & Nandi, M. (2012). Goal programming, its application in management sectors–special attention into plantation management: a review. International journal of scientific and research publications, 2(9), 1-6.

Sundaram, R. M. (1978). An application of goal programming technique in metal cutting. The International Journal Of Production Research, 16(5), 375-382.

Tamiz, M., Jones, D. F., & El-Darzi, E. (1995). A review of goal programming and its applications. Annals of operations Research, 58(1), 39-53.

Tamiz, M., Jones, D., & Romero, C. (1998). Goal programming for decision making: An overview of the current state-of-the-art. European Journal of operational research, 111(3), 569-581.

Tanino, T., Tanaka, T., & Inuiguchi, M. (Eds.). (2013). Multi-objective programming and goal programming: theory and applications (Vol. 21). Springer Science & Business Media.

Ključ rješenja

b) $d^- = 20, d^+ = 0$ (Manjak od 20 u odnosu na cilj 500).
c) $\min (d^+)$ (Minimiziramo samo prekoračenje/višak).
a) Minimiziramo $d^-$ (Jer želimo izbjeći situaciju da imamo manje od 10 radnika).
b) Rješenje je neinterpretabilno u smislu “koliko smo iznad ili ispod cilja” (istovremeno si i ispod i iznad), a u dobro postavljenom GP modelu i s razumnom funkcijom cilja optimalno rješenje u praksi neće imati oba > 0.
c) $\text{Prihod} + d^- - d^+ = 200000$ (Standardni zapis ograničenja cilja).
c) $w_1 = 1000, w_2 = 1$ (Strogo ograničenje mora imati znatno veću “kaznu”).
a) Upravi je pet puta gori ishod prikupiti manje otpada (Veća težina na $d^-$).
b) Model je “žrtvovao” cilj rizika radi prioriteta dobiti.
b) Jedinica odstupanja od A kažnjava se 50% više nego od B.
a) Postavimo dva cilja i minimiziramo $d_1^-$ (manjak od 160) i $d_2^+$ (višak od 180).
c) B dominira A (Bolji profit za isti rizik).
c) Ispod/Desno od linije granice (Lošija rješenja).
b) Teoretska točka najboljih individualnih vrijednosti (Obično nedostižna).
b) Cijena se mora povećati (To je cijena “trade-offa”).
b) Odabrano rješenje je neefikasno ili nedopustivo.
b) Model će ignorirati broj radnih mjesta jer NPV dominira skalom.
b) Rješenje će biti konstantno pa naglo “skočiti” (Step function).
c) To je ispravan optimum; trošak brojčano dominira.
b) Najbrže moguće rješenje, bez obzira na trošak.
c) Da bismo sveli ciljeve na usporedivu skalu i dali težinama pravi smisao.

Ciljno i višeciljno programiranje

Katarina Kostelić

Uvod

Napomena o širem kontekstu

Opći zapis modela u linearnom programiranju

Ciljno programiranje

Strukturiranje modela

Varijable odstupanja \(d_i^+\) i \(d_i^-\)

Ograničenja temeljem ciljne vrijednosti

Funkcija cilja

Primjena

Primjer

Od teksta do matematičkog modela

Strukturiranje problema:

Težinski pristup u ciljnom programiranju

Primjer

Višeciljno programiranje

Koncept rješenja: zašto nema “jednog najboljeg”?

1. Idealna točka (Utopia Point)

2. Pareto optimalnost (Efikasna rješenja)

Primjena

Primjer

Strukturiranje problema

Pareto efikasnost za dobit i rizik

Težinski pristup u višeciljnom programiranju

Primjer

Primjeri - kombinacija s predznanjem

Višeciljno programiranje + mrežni modeli

Višeciljno programiranje + problem pridruživanja

Zadaci za vježbu

Slučaj 1

Slučaj 2

Slučaj 3

Slučaj 4

Slučaj 5

Pitanja za ponavljanje

Literatura

Ključ rješenja