Cjelobrojno i mješovito programiranje (IP, BIP, MILP)
Katarina Kostelić
Uvod
Do sada smo se u svijetu operacijskih istraživanja kretali u domeni kontinuiranosti. Kada smo rješavali probleme linearnog programiranja, pretpostavljali smo da su naši resursi djeljivi do u beskonačnost. Voda teče kroz cijevi, struja kroz žice, novac se dijeli na cente. Ako je optimalno rješenje bilo proizvesti \(333.33\) jedinice nekog proizvoda, matematički model je bio zadovoljan.
Međutim, u stvarnosti smo ponekad suočeni s odlukama koje iziskuju diskretne vrijednosti:
- Ne možete kupiti 0.7 servera.
- Ne možete zaposliti 2.5 programera.
- Ne možete izgraditi pola mosta.
- Varijabla je ili
TRUE(1) iliFALSE(0); feature je ili implementiran ili nije.
Prirodna reakcija je: “Pa dobro, jednostavno ćemo zaokružiti rezultat na najbliži cijeli broj.” U svijetu optimizacije, zaokruživanje je jedna od najopasnijih zamki. Jednostavno zaokruživanje rezultata dobivenog linearnim programiranjem može dovesti do dva velika problema:
- Nedopustivost: Zaokruživanje može prekršiti stroga ograničenja (npr. prekoračenje budžeta ili kapaciteta skladišta).
- Suboptimalnost: Čak i ako je rješenje dopustivo, ono često nije najbolje moguće. Optimalno cjelobrojno rješenje može biti udaljeno od zaokruženog LP rješenja.
Stoga nam je potreban robustniji matematički okvir koji uvažava diskretnu prirodu stvarnosti (Gomory, 2009).
Ovdje ulazimo u domenu cjelobrojnog programiranja (Integer Programming - IP). Iako se matematički čini kao mala promjena (samo dodajemo uvjet \(x \in \mathbb{Z}\)), ova restrikcija drastično mijenja prirodu problema. Pretvara “lako rješive” probleme u kombinatorijske izazove gdje jednostavno zaokruživanje rezultata može dovesti do nedopustivih rješenja.
Istovremeno, kako naši modeli postaju složeniji, tablice i matrice (poput onih \(20 \times 20\)) postaju nečitljive za ljudsko oko. Zbog toga, moramo razviti vještinu vizualizacije. Npr., gledajući u matricu susjedstva, teško ćemo uočiti “usko grlo” ili izolirani klaster; gledajući u graf, to vidimo u djeliću sekunde.
Cjelobrojno programiranje (IP)
Cjelobrojno programiranje (Integer Programming - IP, često nazivano i Pure Integer Programming) odnosi se na optimizacijske modele u kojima sve varijable odluke moraju poprimiti cjelobrojne vrijednosti.
Matematička definicija
Model je identičan standardnom LP-u, uz jedan ključni dodatak:
\[ \begin{aligned} \max (\text{ili } \min) \quad & Z = c_1x_1 + c_2x_2 + \dots + c_nx_n \\ \text{uz ograničenja:} \quad & a_{11}x_1 + \dots + a_{1n}x_n \le b_1 \\ & \dots \\ & x_i \ge 0 \\ & \mathbf{x_i \in \mathbb{Z}} \quad (\text{Varijable su cijeli brojevi}) \end{aligned} \]
Do sada smo rješavali linearno programiranje (LP). Tamo su sve varijable kontinuirane, pa je dopušteno područje konveksni poligon/poliedar, a algoritmi poput Simplexa ili interior-point metoda mogu “kliziti po rubovima” tog poliedra i relativno brzo pronaći optimum.
Kod cjelobrojnog programiranja (IP) model izgleda gotovo isto:
funkcija cilja je linearna,
ograničenja su linearne jednadžbe/nejednadžbe,
ali dodajemo uvjet tipa: \(x_i∈Z\)
LP relaksacija
Standardni trik je:
Zanemarimo cjelobrojnost i privremeno dopustimo da su varijable kontinuirane – dobivamo tzv. LP relaksaciju.
riješimo LP relaksaciju (Simplexom ili nekim LP solverom) – to rješenje je gornja/donja granica (bound) za IP problem:
kod maksimizacije: LP optimum \(\geq\) IP optimum,
kod minimizacije: LP optimum \(\leq\) IP optimum.
Ako se dogodi da je LP rješenje već cjelobrojno, završili smo – to je ujedno i IP optimum. Ako LP rješenje nije cjelobrojno, moramo dodatno “pretraživati” prostor rješenja.
Zašto ne možemo koristiti samo Simplex?
Kod LP-a Simplex koristi činjenicu da je dopustivo područje konveksno. Kod IP-a dopuštene su samo rešetkaste točke (integer grid) unutar tog poligona:
geometrijski: LP “vidi” cijelu površinu (kontinuum),
IP dopušta samo diskretne točke na mreži.
Simplex može naći najbolju kontinuirnu točku, ali ona u pravilu ima decimalne koordinate. Da dođemo do najboljeg cjelobrojnog rješenja, moramo enumerirati (barem implicitno) dio tih rešetkastih točaka, a to je kombinatorijski teže.
Kako solver stvarno radi: branch-and-bound / branch-and-cut (intuicija)
Moderni IP/MILP solveri (uključujući one “iza” funkcije
lp() iz lpSolve-a kad zadamo
all.int = TRUE ili binary.vec=...) koriste varijante:
branch-and-bound
branch-and-cut (branch-and-bound + dodatne rezne ravnine).
Ukratko, ova ideja funkcionira na sljedeći način (Balas i Padberg, 1972; Dantzig, 1963/2016; Schrijver, 1986; Nemhauser i Wolsey, 1988; Wolsey, 1998; Bertsimas i Weismantel, 2005; Conforti i sur., 2014):
Riješimo LP relaksaciju.
Ako je rezultat necjelobrojan, “granamo” problem (dodamo ograničenja, npr. \(x_1\leq4\) i \(x_1\geq5\)) i dobivamo dva manja potproblema.
Za svaki potproblem opet rješavamo LP relaksaciju:
ako je rješenje cjelobrojno → kandidat za optimum,
ako je necjelobrojno, ali je već gore/dolje od nekog boljeg cjelobrojnog rješenja → odbacujemo taj potproblem (bound).
Ponavljamo dok sve grane ne budu pokrivene ili odbačene.
Usporedba LP (linearno programiranje), IP (cjelobrojno programiranje), BIP (birnarno programiranje) i MILP (mješovito programiranje)
| Model | Tip varijabli | Prostor dopustivih rješenja | Tipičan postupak rješavanja | Napomena o težini problema |
|---|---|---|---|---|
| LP | Sve varijable kontinuirane | Konveksan politop (poligon / politop) | Simplex, dual simplex, interior-point metode | Polinomski rješiv, vrlo skalabilan |
| IP (čisti) | Sve varijable cjelobrojne | Diskretna rešetka točaka u LP politopu | LP relaksacija + branch-and-bound, branch-and-cut, heuristike | NP-težak; vrijeme rješavanja osjetljivo na broj dimenzija |
| BIP | Sve varijable binarne (0/1) | Podskupni problemi, logički uvjeti | Specijalizirani B&B/B&C, presjek s pseudo-bool. formulacijama | NP-težak, ali često vrlo strukturiran (set cover, lokacija,…) |
| MILP | Dio varijabli cjelobrojan/ binaran, dio kontinuiran | Mješoviti (diskretni + kontinuirani) politop | Isto kao IP: B&B/B&C nad LP relaksacijama, uz heuristike i rezove | Generalno NP-težak; najčešći praktični industrijski model |
Napomene vezane uz kratice i pojmove u tablici:
- LP relaksacija znači da privremeno ignoriramo uvjet cjelobrojnosti i rješavamo problem kao običan LP s kontinuiranim varijablama.
- Branch-and-bound (B&B) je postupak u kojem rješavamo LP relaksaciju, a zatim problem “granamo” dodavanjem dodatnih ograničenja te odbacujemo one grane koje ne mogu dati bolje cjelobrojno rješenje od već pronađenih.
- Branch-and-cut (B&C) je proširenje B&B metode u kojem uz grananje dodajemo i rezne ravnine (dodatna linearna ograničenja) koja “režu” nedopušteni dio relaksiranog prostora i ubrzavaju traženje cjelobrojnih rješenja.
- Heuristike su pametna “pravila palca” i aproksimacijski algoritmi koji ne daju nužno optimalno rješenje, ali često brzo pronađu jako dobro rješenje i pomažu solveru da brže dođe do optimuma.
Primjena
Ovo se koristi kada brojimo fizičke ili nedjeljive entitete, npr.:
- Broj kamiona u voznom parku,
- broj proizvedenih zrakoplova,
- broj paleta u skladištu,
- broj tokena…
Čisti IP najčešće se pojavljuje u:
proizvodno–logističkim problemima (cutting stock, lot-sizing),
raspoređivanju (timetabling, crew scheduling),
raznim kombinatorijskim problemima gdje su sve varijable tipa “koliko komada”.
Kod čistog cjelobrojnog programiranja zgodno je krenuti od klasične industrijske priče o rezanju materijala. U tzv. cutting-stock problemu moramo iz standardnih koluta papira, limova ili drvenih greda izrezati zadane duljine tako da se otpad minimizira. Svaki uzorak rezanja modelira se kao cjelobrojna varijabla – koliko puta taj uzorak koristimo – a ograničenja osiguravaju da je tražena količina svake duljine zadovoljena. Gilmore i Gomory (1961) su to još 1960-ih formalizirali kao (veliki) cjelobrojni linearni program i otvorili cijelo područje za rješavanje takvih problema u praksi. Danas isti tip formulacije koriste papirnice, čeličane ili proizvođači kabela.
Osim rezanja materijala, cjelobrojno programiranje pojavljuje se i u puno „digitalnijim“ rasporedima. Jedan tipičan primjer je raspored instrukcija u procesoru. Wilken, Liu i Heffernan (2000) modeliraju instruction scheduling kao cjelobrojni problem u kojem svaka instrukcija iz programa dobije svoju poziciju u vremenskoj liniji procesora. Varijable odlučuju u kojem ciklusu se koja instrukcija izvršava (cijeli brojevi), a ograničenja osiguravaju da se ne krše podatkovne ovisnosti i da se u svakom taktu ne koristi više funkcijskih jedinica nego što ih procesor stvarno ima. Cilj je minimizirati ukupno vrijeme izvršavanja (ili duljinu pipelinea), ali se sve ključne odluke svode na diskretan izbor u kojem slotu će ova instrukcija završiti, što prirodno vodi do cjelobrojnog modela.
Vrlo slična ideja javlja se kod rasporeda smjena i posada u javnom prijevozu. Ryan i Foster (1981) pokazuju kako se raspored vožnji autobusa i posada može formulirati kao cjelobrojni model u kojem varijable biraju koje dionice posla (duty pieces) čine jednu smjenu, uz gomilu praktičnih ograničenja: maksimalno trajanje smjene, pauze, početak i kraj u istom depo-u, pokrivenost svih planiranih linija itd. Klasične mrežne metode poput PERT-a i CPM-a tu nisu dovoljne: one jako dobro opisuju redoslijed aktivnosti i kritični put kroz projekt, ali ne odgovaraju na pitanje „tko to točno radi i u kojoj kombinaciji?“. Drugim riječima, PERT/CPM modeliraju vrijeme i ovisnosti u mreži, ali ne rješavaju dodjelu diskretnih resursa (npr. konkretnog vozača ili autobusa) na te aktivnosti. Upravo taj sloj – slaganje cjelovitih smjena od diskretnih komadića rasporeda – rješava se cjelobrojnim programiranjem.
U obrazovnom kontekstu, cjelobrojno programiranje se vrlo uspješno koristi za raspored nastave i ispita. Klasičan primjer je rad Martin (2004), koji opisuje kako je College of Business na Ohio Universityju prešao s ručnog planiranja na model temeljen na cjelobrojnom programiranju kako bi odredili termine, dvorane i dodjele kolegija na nositelje. Model istovremeno uvažava kapacitete učionica, preklapanja nastavnika, ograničenja studijskih programa i preferencije (npr. da se određeni kolegiji ne drže prekasno ili prerano), a rješenje se generira automatski jednom kada su svi podaci uneseni. Rezultat je znatno manji broj konflikata u rasporedu, bolja iskorištenost učionica i puno manje vremena koje administracija troši na ručne izmjene.
Primjer: Optimizacija u igri Factorio
Factorio je popularna simulacijska igra u kojoj igrač gradi i održava automatizirane tvornice. Srž igre je balansiranje ulaznih sirovina (željezo, bakar) kako bi se proizveli složeni proizvodi (“Znanstveni paketi” ili Science Packs) koji se koriste za istraživanje novih tehnologija.
Vi ste glavni inženjer svoje baze. Imate ograničeni dotok sirovina iz svojih rudnika i talionica. Vaš cilj je maksimizirati proizvodnju “znanosti” kako biste što prije lansirali raketu.
Fokusiramo se na rani dio igre (Early Game) i proizvodnju dva ključna paketa:
- Automation Science Pack
- Logistic Science Pack
Tehnološki recepti (pojednostavljeni):
Da biste proizveli 1 jedinicu znanosti, potrebni su vam sljedeći resursi (u pločama):
| Proizvod | Željezne ploče (Iron Plates) | Bakrene ploče (Copper Plates) | Vrijeme proizvodnje (s) |
|---|---|---|---|
| Automation Science Pack (\(x_1\)) | 2 | 1 | 5 |
| Logistic Science Pack (\(x_2\)) | 6 | 1.5 | 6 |
(Napomena: Logistic Science Pack je složeniji jer traži pokretne trake i insertere, što troši puno više željeza.)
Ograničenja sustava (resursi):
Vaša trenutna infrastruktura talionica (Smelting Array) može isporučiti:
- Željezo: Maksimalno 600 ploča u minuti.
- Bakar: Maksimalno 200 ploča u minuti.
- Također, imate ograničen broj Assembling Machine 1 (tvornica) na raspolaganju zbog ograničenog prostora i struje. Ukupno vrijeme rada svih strojeva ne smije prelaziti 3000 sekundi u minuti (ovo ekvivalentno znači da imate na raspolaganju 50 strojeva, jer svaki radi 60 sekundi u minuti).
Cilj:
Maksimizirati ukupnu količinu proizvedenih paketa znanosti u minuti (\(Z = x_1 + x_2\)), ali uz uvjet da Logistic Science Pack mora činiti barem 30% ukupne proizvodnje jer je nužna za napredak.
Struktura problema
Varijable odluke:
- \(x_1\) = količina Automation Science Pack (paketa/min)
- \(x_2\) = količina Logistic Science Pack (paketa/min)
Funkcija cilja: \[ \max (x_1 + x_2) \]
Ograničenja:
- Ograničenje željeza:
Svaka ASP troši 2, svaka LSP 6. Dostupno 600. \[ 2x_1 + 6x_2 \le 600 \]
- Ograničenje bakra:
Svaka ASP troši 1, svaka LSP 1.5. Dostupno 200. \[ 1x_1 + 1.5x_2 \le 200 \]
- Ograničenje Kapaciteta strojeva:
Da bismo proizveli \(x_1\) paketa u minuti, a jedan traje 5 sekundi, trebamo \(5x_1\) sekundi strojnog vremena. \[ 5x_1 + 6x_2 \le 3000 \]
- Ograničenje balansa (Mix):
LSP mora biti barem 30% ukupne proizvodnje. \[ x_2 \ge 0.3(x_1 + x_2) \Rightarrow x_2 \ge 0.3x_1 + 0.3x_2 \Rightarrow 0.7x_2 - 0.3x_1 \ge 0 \] Ili ljepše zapisano: \[ -0.3x_1 + 0.7x_2 \ge 0 \] 5. Uvjet cjelobrojnosti (kreiramo jedinice paketa) \[x_1,x_2 = int\]
- Uvjet nenegativnosti \[x_1,x_2 \geq0\]
library(lpSolve)## Warning: package 'lpSolve' was built under R version 4.4.2obj <- c(1, 1)
constr <- matrix(c(
2, 6,
1, 1.5,
5, 6,
-0.3, 0.7),
nrow = 4, byrow = TRUE)
rhs <- c(600, 200, 3000, 0)
constr_dir <- c("<=", "<=", "<=", ">=")
solution <- lp(
direction = "max",
objective.in = obj,
const.mat = constr,
const.dir = constr_dir,
const.rhs = rhs,
all.int = TRUE
)
# Ispis
cat("Optimalna proizvodnja:\n",
paste("ASP (x1):", solution$solution[1], "/ min\n"),
paste("LSP (x2):", solution$solution[2], "/ min\n"),
paste("Ukupno paketa:", solution$objval, "/ min\n"))## Optimalna proizvodnja:
## ASP (x1): 119 / min
## LSP (x2): 54 / min
## Ukupno paketa: 173 / minzeljezo <- 2 * solution$solution[1] + 6 * solution$solution[2]
bakar <- 1 * solution$solution[1] + 1.5 * solution$solution[2]
cat("\nIskorištenost resursa:\n",
paste("Željezo:", zeljezo, "/ 600\n"),
paste("Bakar: ", bakar, "/ 200\n"))##
## Iskorištenost resursa:
## Željezo: 562 / 600
## Bakar: 200 / 200Rješenje modela daje nam sliku stanja naše tvornice:
- Usko grlo (bottleneck)
Pogledom na iskorištenost resursa, vidimo da je bakar potpuno iskorišten (200/200). U jeziku operacijskih istraživanja, ovo ograničenje je aktivno, odnosno vezujuće. S druge strane, imamo višak (slack) željeza od 38 jedinica.
Praktični savjet: Da biste povećali ukupnu proizvodnju, morate izgraditi nove rudnike bakra. Dodavanje novih talionica željeza u ovom trenutku ne bi imalo nikakvog efekta.
- Proizvodni miks
Algoritam je predložio proizvodnju 119 crvenih (\(x_1\)) i 54 zelena paketa (\(x_2\)).
- Udio zelenih paketa je \(54 / 173 \approx 31.2\%\).
- Ovo je vrlo blizu minimalno zahtijevanih 30%. Zašto? Zato što je Automation Science Pack (crveni) “jeftiniji” u pogledu bakra (troši 1 ploču, dok LSP/zeleni troši 1.5). Budući da nam nedostaje bakra, a želimo maksimizirati ukupan broj paketa, algoritam “štedi” bakar na zelenim paketima (proizvodi ih tek toliko da zadovolji uvjet) kako bi mogao proizvesti što više crvenih.
U ovom primjeru koristili smo uvjet \(x_1,
x_2 \in \mathbb{Z}\) (all.int = TRUE). Zašto je to
važno?
- Priroda problema: U igrama poput Factorija, kao i u stvarnoj logistici paketa, proizvodi su diskretne jedinice. Ne možete isporučiti 0.7 znanstvenog paketa; on je ili na traci ili nije.
- Da smo koristili obično linearno programiranje (pretpostavka kontinuiranih varijabli), rezultat bi mogao biti npr. \(x_1 = 121.74\) i \(x_2 = 52.17\).
- Ako bismo te brojeve jednostavno zaokružili prema dolje (na 121 i 52), možda bismo prekršili uvjet minimalnog udjela od 30%.
- Ako bismo zaokružili prema gore (na 122 i 53), prekršili bismo ograničenje dostupnog bakra.
- Cjelobrojno programiranje nam daje rješenje koje je garantirano provedivo unutar strogih ograničenja resursa i pravila sustava, eliminirajući potrebu za nagađanjem kod zaokruživanja.
Budući da naš problem ima samo dvije varijable odluke (\(x_1\) i \(x_2\)), možemo ga vizualizirati u 2D koordinatnom sustavu.
- X-os: Količina Automation Science Pack (\(x_1\))
- Y-os: Količina Logistic Science Pack (\(x_2\))
Na grafu ćemo prikazati:
- Pravce ograničenja: Svako ograničenje (željezo, bakar, strojevi, miks) dijeli ravninu na “dopušteni” i “nedopušteni” dio.
- Dopustivo područje (Feasible Region): Sivi poligon koji predstavlja sve kombinacije (\(x_1, x_2\)) koje zadovoljavaju sva ograničenja.
- Točku optimuma: Crvena točka koja predstavlja naše rješenje.
- Pravac funkcije cilja (izoprofitni pravac): Isprekidana linija koja nam pokazuje smjer maksimizacije.
Grafički prikaz nam otkriva nekoliko važnih informacija koje se ne vide samo iz brojeva:
- Geometrija dopustivog područja (siva zona):
Vidimo da je sivo područje omeđeno s tri linije: dolje pravcem za mix (zelena), gore desno pravcem za bakar (narančasta) i iznad, još pravcem za željezo (plava).
- Zašto je bakar usko grlo?
Pogledajte optimalnu točku (crvena točka). Ona se nalazi točno na narančastoj liniji (bakar). To vizualno potvrđuje da nas ta linija “zaustavlja” da idemo dalje gore-desno (prema većem profitu).
- Višak željeza (slack):
Optimalna točka je ispod plave linije (željezo). Udaljenost od crvene točke do plave linije vertikalno predstavlja neiskorišteni kapacitet željeza.
- Cjelobrojno vs. kontinuirano:
Iako je sivo područje kontinuirano, cjelobrojno programiranje (IP) zapravo “vidi” samo mrežu točkica s cjelobrojnim koordinatama (grid) unutar tog sivog područja. Algoritam traži onu točkicu koja daje najveći Z (što više desno i gore), a da je i dalje unutar granica.
Na linku je primjer Factorio kalkulatora, pa se možete poigrati i sami sastaviti i riješiti slučaj.
Binarno programiranje (BIP)
Binarno programiranje (Binary Integer Programming - BIP) je poseban slučaj cjelobrojnog programiranja gdje su varijable ograničene na samo dvije vrijednosti: 0 ili 1.
Dok opće cjelobrojno programiranje odgovara na pitanje “Koliko?”, binarno programiranje odgovara na logička pitanja “Da ili Ne?”.
Matematička definicija
\[ x_i \in \{0, 1\} \] * \(x_i = 1\) \(\implies\) akcija je odabrana (npr. projekt je prihvaćen, tvornica je izgrađena). * \(x_i = 0\) \(\implies\) akcija je odbijena.
Primjena
Binarno programiranje nam omogućuje modeliranje složenih logičkih uvjeta koji su nemogući u običnom LP-u:
- Međusobna isključivost: odabir projekta A ili projekta B, ali ne oba (\(x_A + x_B \le 1\)).
- Uvjetovanost: ako gradimo skladište (A), moramo izgraditi i cestu (B) (\(x_A \le x_B\)).
- Set Covering / Packing: problemi pokrivanja tržišta, raspored smjena, odabir lokacija za odašiljače.
U strojnom učenju, binarno programiranje se koristi za vrlo “čistu” formalizaciju problema odabira značajki (features). U radu Bertolazzi i sur. (2016) istražuje se kako binarni IP modeli mogu preuzeti ulogu selekcije featurea umjesto heuristika poput stepwise metoda ili “filter” pristupa. Svaka potencijalna značajka predstavlja se binarnom varijablom koja poprima vrijednost 1 ako je značajka odabrana u model i 0 ako je isključena. Funkcija cilja tipično balansira prediktivnu točnost i kompleksnost (broj odabranih značajki), a ograničenja kontroliraju stvari poput maksimalnog broja featurea ili međusobnih isključenja zbog kolinearnosti. Autori dodatno razvijaju proširenja modela i random algoritam rješavanja, pokazujući da je moguće dobiti vrlo konkurentne skupove značajki s eksplicitno modeliranim trade-offom između kvalitete i jednostavnosti modela. Slična ideja javlja se i u radu Wan i sur. (2016), gdje je selekcija značajki formulirana kroz modificirani binarno kodirani ant colony algoritam: iako je središnji algoritam metaheuristika, sama struktura rješenja je binarni vektor (uzima/ne uzima feature), pa je svaka mravlja putanja zapravo kandidat rješenja jednog binarnog programskog problema. Rezultat je opet eksplicitna diskretna odluka o tome koji se skup senzora ili varijabli isplati zadržati kako bi se smanjila dimenzionalnost, a zadržala (ili poboljšala) točnost klasifikatora.
U domeni planiranja rada i smjena, binarno programiranje prirodno zapisuje raspored ljudi na vremenske slotove. Khalil i Modibbo (2021) koriste binarno “goal programming” (ciljno programiranje - to će biti pokriveno u sljedećoj lekciji) za rješavanje problema rasporeda medicinskih sestara u bolnici. Svaka potencijalna dodjela “sestra/tehničar i – smjena j” modelira se binarnom varijablom koja označava radi li ta sestra/tehničar u toj smjeni ili ne. Cilj nije jedinstven, nego višekriterijski: treba istovremeno zadovoljiti minimalnu pokrivenost odjela, ravnomjerno raspodijeliti radne sate, poštovati preferencije osoblja i ograničenja iz radnog prava (maksimalan broj noćnih smjena, minimalan odmor i sl.). Binarni model ovdje služi kao čvrsta jezgra – sve te politike i “mekani” ciljevi pretvaraju se u linearne ciljeve i ograničenja nad 0–1 varijablama, a rješenje je konkretan raspored tko točno radi koju smjenu. Ovo je također lijep kontrast prema “klasičnom” PERT/CPM pristupu rasporedu, gdje računamo kritični put i trajanja aktivnosti, ali ne možemo direktno odlučiti koja konkretna osoba radi koju aktivnost – upravo za taj sloj dodjele resursa koristimo binarno/cjelobrojno programiranje.
Druga vrlo tipična primjena binarnog programiranja su problemske situacije lociranja i postavljanja infrastrukture. Wong i sur. (2006) modeliraju smještaj baznih stanica u zatvorenim, indoor bežičnim sustavima pomoću binarnih varijabli koje označavaju hoćemo li na konkretnu lokaciju-kandidata postaviti baznu stanicu ili ne. Cilj je pokriti cijeli prostor signalom uz minimalan broj stanica ili minimalan trošak, uz ograničenja vezanih uz jačinu signala, interferenciju i geometriju prostora. Svaka dodatna poslovna ili tehnička politika – poput maksimalnog broja stanica, ograničenja po etažama, minimalne kvalitete signala u “kritičnim” zonama – izražava se linearno u tim 0–1 varijablama. Dobiveni BIP model daje vrlo konkretan raspored: koje lokacije aktivirati, a koje ostaviti praznima, uz jasnu interpretaciju za inženjere mreža.
Primjer s međusobnom isključivosti
Vi ste novoimenovani CTO (Chief Technology Officer) startupa koji razvija novu SaaS platformu. Morate odabrati tehnologije koje će činiti vaš “Tech Stack”. Svaka tehnologija nosi određene bodove “produktivnosti” (bazirano na iskustvu tima i brzini razvoja), ali i mjesečni trošak (licence, hosting, održavanje).
Vaš ukupni mjesečni budžet za infrastrukturu i licence je 200 €.
Na raspolaganju su sljedeće opcije, podijeljene po kategorijama:
| ID | Tehnologija | Kategorija | Produktivnost (Bodovi) | Trošak (€/mj) |
|---|---|---|---|---|
| 1 | React | Frontend | 90 | 0 |
| 2 | Angular | Frontend | 85 | 0 |
| 3 | Vue.js | Frontend | 80 | 0 |
| 4 | Node.js | Backend | 85 | 20 |
| 5 | Django (Python) | Backend | 90 | 30 |
| 6 | Go (Golang) | Backend | 95 | 50 |
| 7 | PostgreSQL | Baza | 88 | 40 |
| 8 | MongoDB | Baza | 82 | 40 |
| 9 | Redis | Cache (Add-on) | 70 | 30 |
| 10 | Elasticsearch | Search (Add-on) | 85 | 60 |
Cilj je maksimizirati ukupne bodove produktivnosti odabirom optimalnog skupa tehnologija.
Pritom postoje stroga arhitekturalna pravila:
- Morate odabrati točno jedan Frontend framework, točno jedan Backend jezik i točno jednu Bazu podataka.
- Ukupni trošak ne smije prelaziti 200 €.
- Međusobna isključivost (The “Legacy” Conflict): Vaš tim je utvrdio da Angular (\(x_2\)) i Django (\(x_5\)) zajedno stvaraju probleme u deployment pipelineu zbog specifičnih internih biblioteka. Ne smijete odabrati oboje (možete odabrati jedno, drugo ili nijedno, ali ne oboje).
- Ako želite koristiti naprednu tražilicu Elasticsearch (\(x_{10}\)), arhitektura mora biti brza i skalabilna, stoga to zahtijeva da backend bude Go (\(x_6\)). Ako nemate Go, ne možete imati ni Elasticsearch (obrnuto ne vrijedi: možete imati Go bez Elasticsearcha).
Struktura problema
Varijable odluke:
Neka je \(x_i\) binarna varijabla:
\[ x_i \in \{0, 1\}, \quad i = 1 \dots 10 \] * \(x_i = 1\) ako odaberemo tehnologiju \(i\). * \(x_i = 0\) inače.
Funkcija cilja:
\[ \max \sum (\text{produktivnost}_i \cdot x_i) \]
Ograničenja:
- Odabir frontenda (točno jedan):
\[ x_1 + x_2 + x_3 = 1 \]
- Odabir backenda (točno jedan):
\[ x_4 + x_5 + x_6 = 1 \]
- Odabir baze (točno jedna):
\[ x_7 + x_8 = 1 \]
- Budžet:
\[ \sum (\text{Trošak}_i \cdot x_i) \le 200 \]
- Isključivost (Angular vs Django):
\[ x_2 + x_5 \le 1 \]
- Ovisnost (Elasticsearch treba Go):
Ako je \(x_{10}=1\), onda \(x_6\) mora biti 1.
\[ x_{10} \le x_6 \quad \Rightarrow \quad x_{10} - x_6 \le 0 \]
library(lpSolve)
# Podaci
tehnologije <- c("React", "Angular", "Vue",
"Node.js", "Django", "Go",
"PostgreSQL", "MongoDB",
"Redis", "Elasticsearch")
# Funkcija cilja
obj <- c(90, 85, 80,
85, 90, 95,
88, 82,
70, 85)
# Matrica ograničenja
constr <- matrix(c(
1, 1, 1, 0, 0, 0, 0, 0, 0, 0, # 1. Frontend (React, Angular, Vue) = 1
0, 0, 0, 1, 1, 1, 0, 0, 0, 0, # 2. Backend (Node, Django, Go) = 1
0, 0, 0, 0, 0, 0, 1, 1, 0, 0, # 3. Baza (Postgres, Mongo) = 1
0, 0, 0, 20, 30, 50, 40, 40, 30, 60, # 4. Budžet (svi troškovi) <= 200
0, 1, 0, 0, 1, 0, 0, 0, 0, 0, # 5. Isključivost: Angular(2) + Django(5) <= 1
0, 0, 0, 0, 0, -1, 0, 0, 0, 1 # 6. Ovisnost: Elastic(10) <= Go(6) -> Elastic - Go <= 0
),
nrow = 6, byrow = TRUE)
# Smjerovi ograničenja
constr_dir <- c("=", "=", "=", "<=", "<=", "<=")
rhs <- c(1, 1, 1, 200, 1, 0)
solution <- lp(
direction = "max",
objective.in = obj,
const.mat = constr,
const.dir = constr_dir,
const.rhs = rhs,
all.bin = TRUE # Ključan argument! Sve varijable su 0 ili 1
)
# Priprema za ispis
tehnologije <- c("React", "Angular", "Vue",
"Node.js", "Django", "Go",
"PostgreSQL", "MongoDB",
"Redis", "Elasticsearch")
trosak <- constr[4,]
selected_indices <- which(solution$solution == 1)
odabrano <- data.frame(
Tehnologija = tehnologije[selected_indices],
Bodovi = obj[selected_indices],
Trosak = trosak[selected_indices]
)
print(odabrano)## Tehnologija Bodovi Trosak
## 1 React 90 0
## 2 Go 95 50
## 3 PostgreSQL 88 40
## 4 Redis 70 30
## 5 Elasticsearch 85 60cat("\nUkupna produktivnost:", solution$objval,
"\nUkupni trošak:", sum(odabrano$Trosak), "€ / 200 €")##
## Ukupna produktivnost: 428
## Ukupni trošak: 180 € / 200 €Algoritam je odabrao sljedeću kombinaciju kao optimalnu: React + Go + PostgreSQL + Redis + Elasticsearch.
Zašto baš ova kombinacija?
- Frontend (React):
Odabran je React jer ima najveću produktivnost (90) u svojoj kategoriji, a cijena mu je 0 €, isto kao i konkurentima.
- Backend (Go):
Ovo je najzanimljiviji dio. Go je najskuplji backend (50 €) u usporedbi s Node.js (20 €) i Djangom (30 €).
- Da smo gledali samo cijenu, Node.js bi bio favorit.
- Međutim, odabran je Go zbog Elasticsearcha. Elasticsearch donosi ogromnih 85 bodova, ali zahtijeva Go (6. ograničenje).
- Kombinacija
Go + Elasticsearchkošta 110 € i donosi \(95 + 85 = 180\) bodova. - Bilo koja druga kombinacija (npr. Django + Redis) ne bi mogla doseći tu razinu bodova unutar preostalog budžeta. Model je “žrtvovao” skuplji backend da bi “otključao” moćni add-on.
- Baza (PostgreSQL):
Cijena PostgreSQL-a i MongoDB-a je ista (40 €), ali PostgreSQL nosi više bodova (88 vs 82). Algoritam je jednostavno uzeo bolji omjer cijene i kvalitete.
- Add-ons (Redis i Elasticsearch):
Budžet je dopustio odabir oba dodatna alata.
- Trošak do sada: Go (50) + Postgres (40) + Elastic (60) = 150 €.
- Preostalo je 50 €.
- Redis košta 30 €. Imamo novca, donosi 70 bodova. Uzimamo ga.
- Zadovoljena ograničenja:
- Budžet: potrošeno 180 €, ostalo 20 €. Za tih 20 € ne možemo kupiti ništa što bi poboljšalo sustav (npr. ne možemo zamijeniti React za nešto bolje jer nema boljeg, a backend ne možemo mijenjati jer nam treba Go).
- Konflikt: Angular i Django nisu odabrani, tako da sukoba nema.
- Ovisnost: Elasticsearch je odabran, ali je odabran i Go, tako da je uvjet zadovoljen.
Primjer s uvjetima
Vi ste CISO (Chief Information Security Officer) u fintech kompaniji. Uprava vam je odobrila budžet od 25000 € za implementaciju novih sigurnosnih kontrola kako biste prošli nadolazeću ISO 27001 reviziju.
Vaš tim je identificirao 6 ključnih sigurnosnih alata/mjera. Svaka mjera donosi određeno smanjenje rizika (bodovi; što više, to bolje) i ima svoju cijenu implementacije.
Dostupne sigurnosne kontrole:
| ID (\(x_i\)) | Sigurnosna kontrola | Cijena (€) | Smanjenje rizika (Bodovi) |
|---|---|---|---|
| 1 | Next-Gen Firewall (NGFW) | 8000 | 90 |
| 2 | SIEM sustav (Logovi i monitoring) | 12000 | 95 |
| 3 | VPN Gateway (Udaljeni pristup) | 4000 | 50 |
| 4 | MFA (Multi-Factor Auth) | 3000 | 80 |
| 5 | Endpoint Protection (EDR) | 6000 | 85 |
| 6 | DLP (Data Loss Prevention) | 7000 | 60 |
Cilj je odabrati skup kontrola koji maksimizira ukupno smanjenje rizika, poštujući budžet i tehničke ovisnosti.
Ovo je onaj dio gdje problem postaje zanimljiv i “težak”. Sigurnost funkcionira u slojevima:
Uvjetovana nužnost (IF A THEN B): Ako implementiramo VPN Gateway (\(x_3\)) kako bismo omogućili rad od kuće, sigurnosna politika strogo zahtijeva da moramo implementirati i MFA (\(x_4\)) radi provjere identiteta. (VPN bez MFA je sigurnosna rupa. Dakle: Ako uzmemo VPN, moramo uzeti i MFA. Ako ne uzmemo VPN, MFA možemo uzeti, a i ne moramo.)
Tehnička ovisnost (uvjet): SIEM sustav (\(x_2\)) je beskoristan ako nemamo kvalitetne logove s mrežne razine. Stoga, SIEM možemo kupiti samo ako kupimo i NGFW (\(x_1\)). (Ne možemo imati SIEM bez Firewalla).
Resursni konflikt (međusobna isključivost): Zbog ograničenja na agentima koji se vrte na računalima zaposlenika, ne možemo istovremeno vrtjeti i EDR (\(x_5\)) i DLP (\(x_6\)) jer ruše performanse sustava. Moramo odabrati najviše jedan od ta dva.
Struktura problema
Varijable odluke: \[ x_i \in \{0, 1\}, \quad i = 1 \dots 6 \]
Funkcija cilja: \[ \max (90x_1 + 95x_2 + 50x_3 + 80x_4 + 85x_5 + 60x_6) \]
Ograničenja:
Budžet: \[ 8x_1 + 12x_2 + 4x_3 + 3x_4 + 6x_5 + 7x_6 \le 25 \quad (\text{u tisućama}) \]
Uvjetovana nužnost (VPN \(\implies\) MFA):
Logika: Ako je \(x_3=1\), onda \(x_4\) mora biti 1.
(Tablica istinitosti: \(1 \to 1\) (OK), \(0 \to 0\) (OK), \(0 \to 1\) (OK), \(1 \to 0\) (NIJE OK)).
Matematički zapis: \[ x_3 \le x_4 \quad \Rightarrow \quad x_3 - x_4 \le 0 \]
- Ovisnost (SIEM zahtijeva NGFW):
Logika: Ako je \(x_2=1\), onda \(x_1\) mora biti 1. (Isto kao gore, SIEM je “dijete”, NGFW je “roditelj”). \[ x_2 \le x_1 \quad \Rightarrow \quad x_2 - x_1 \le 0 \]
- Konflikt (EDR vs DLP):
Suma mora biti 0 ili 1, ne smije biti 2. \[ x_5 + x_6 \le 1 \]
library(lpSolve)
# Imena radi lakšeg praćenja
items <- c("NGFW", "SIEM", "VPN", "MFA", "EDR", "DLP")
# Funkcija cilja (Smanjenje rizika)
risk_points <- c(90, 95, 50, 80, 85, 60)
# Troškovi (u tisućama)
costs <- c(8, 12, 4, 3, 6, 7)
# Matrica ograničenja
constr <- matrix(c(
8, 12, 4, 3, 6, 7, # 1. Budžet: 8x1 + 12x2 + 4x3 + 3x4 + 6x5 + 7x6 <= 25
0, 0, 1, -1, 0, 0, # 2. VPN(3) => MFA(4) -> x3 - x4 <= 0
-1, 1, 0, 0, 0, 0, # 3. SIEM(2) => NGFW(1) -> x2 - x1 <= 0
0, 0, 0, 0, 1, 1 # 4. Konflikt: EDR(5) + DLP(6) <= 1
), nrow = 4, byrow = TRUE)
# Desna strana i smjerovi
rhs <- c(25, 0, 0, 1)
constr_dir <- c("<=", "<=", "<=", "<=")
solution <- lp(
direction = "max",
objective.in = risk_points,
const.mat = constr,
const.dir = constr_dir,
const.rhs = rhs,
all.bin = TRUE
)
selected <- which(solution$solution == 1)
df_result <- data.frame(
Kontrola = items[selected],
Cijena = costs[selected],
Bodovi = risk_points[selected])
print(df_result)## Kontrola Cijena Bodovi
## 1 NGFW 8 90
## 2 VPN 4 50
## 3 MFA 3 80
## 4 EDR 6 85cat("\nUkupno smanjenje rizika:", solution$objval,
"\nPotrošeni budžet:", sum(df_result$Cijena), "000 € / 25 000 €")##
## Ukupno smanjenje rizika: 305
## Potrošeni budžet: 21 000 € / 25 000 €Algoritam je odabrao kombinaciju: NGFW + VPN + MFA + EDR. Ukupni bodovi: 305. Potrošeno: 21000 €.
Zašto je ovo optimalno i što možemo naučiti iz ovog rezultata?
- Zamka “najboljeg alata” (SIEM)
SIEM ima pojedinačno najviše bodova (95 bodova). Intuitivno, mnogi bi ga odmah kupili.
- Ali, SIEM košta 12000 €.
- Zbog ovisnosti, on zahtijeva NGFW (8000 €).
- Dakle, odluka “kupimo SIEM” zapravo košta 20000 € (80% budžeta!).
- To nam ostavlja samo 5000 € za sve ostalo. Za taj novac bismo mogli kupiti samo MFA (3000 €).
- Scenarij sa SIEM-om: NGFW + SIEM + MFA = \(90 + 95 + 80 = \mathbf{265}\) bodova.
- Optimalni scenarij: \(\mathbf{305}\) bodova. Algoritam je ispravno zaključio da je SIEM preskup za ono što nudi kada se uračunaju ovisnosti.
- Uvjetna povezanost VPN-a i MFA
VPN sam po sebi nosi malo bodova (50) i košta 4000 €. MFA je jeftin (3000 €) i nosi puno bodova (80).
Zbog ograničenja \(VPN \implies MFA\), kupnja ove dvije stavke zajedno košta 7000 € i donosi 130 bodova. To je izvrstan omjer “cijene i performansi” (ROI), pa ih je algoritam uvrstio.
- Konflikt: EDR vs. DLP
Morali smo birati između EDR-a i DLP-a.
- EDR: 6000 € za 85 bodova.
- DLP: 7000 € za 60 bodova.
EDR je jeftiniji i efikasniji.
- Neiskorišteni budžet (Slack)
Ostalo nam je 4000 €. Zašto nismo potrošili i to?
- Jedina preostala opcija koju nismo kupili je DLP (7000 €) - preskupo.
- SIEM (12000 €) - preskupo.
- Ne možemo kupiti “pola DLP-a” jer je ovo binarno programiranje.
- Ovaj neiskorišteni budžet je dokaz diskretne prirode problema – ponekad jednostavno ne možete iskoristiti sve, do zadnjeg centa.
Primjer - Set Covering
Vaša tvrtka razvila je uspješnu FinTech aplikaciju koja je trenutno dostupna u EU. Imate stabilne prihode i spremni ste za globalno širenje.
Međutim, svako novo tržište je “skupo”. FinTech je strogo regulirana industrija. Ulazak u novu zemlju znači:
- Pravni trošak: Angažman lokalnih odvjetnika za usklađivanje s financijskim zakonima.
- Tehnički trošak: Prilagodba formata valuta, poreznih izvještaja i jezika aplikacije.
- Compliance trošak: Usklađivanje s lokalnim verzijama GDPR-a (npr. LGPD u Brazilu, CCPA u Kaliforniji).
Uprava je postavila 5 strateških ciljeva (zahtjeva) koje morate ispuniti u idućem kvartalu. Vaš zadatak je odabrati kombinaciju tržišta koja ispunjava sve te ciljeve uz minimalni ukupni trošak ulaska.
Analizirali ste 5 potencijalnih regija za širenje.
| ID (\(x_j\)) | Tržište | Trošak ulaska (€) | Karakteristike (Koga pokriva?) |
|---|---|---|---|
| 1 | SAD (Sjeverna Amerika) | 150000 | • Govornici engleskog • Visoka kupovna moć • Stroga regulativa |
| 2 | Brazil (LATAM) | 60000 | • Tržište u razvoju (High Growth) • Velika baza korisnika |
| 3 | UK (Post-Brexit) | 90000 | • Govornici engleskog • Visoka kupovna moć • Europska vremenska zona |
| 4 | Singapur (APAC Hub) | 110000 | • Azijsko tržište • Govornici engleskog • Stroga regulativa |
| 5 | Indija | 70000 | • Azijsko tržište • Tržište u razvoju (High Growth) • Velika baza korisnika |
Moramo odabrati podskup tržišta tako da je zadovoljen svaki od sljedećih 5 uvjeta (minimalno jednom):
- Engleski jezik: moramo ući na barem jedno tržište gdje je primarni jezik engleski (radi lakšeg customer supporta).
- Kandidati: SAD, UK, Singapur.
- Azijska prisutnost: moramo imati barem jedno uporište u Aziji radi 24h pokrivenosti podrške.
- Kandidati: Singapur, Indija.
- Tržište u razvoju (High Growth): investitori traže brzi rast broja korisnika, što nude tržišta u razvoju.
- Kandidati: Brazil, Indija.
- Visoka kupovna moć (High ARPU): trebamo tržište s visokim prihodom po korisniku.
- Kandidati: SAD, UK.
- Regulatorni “Sandbox”: trebamo barem jedno tržište s vrlo strogom regulativom (izvan EU) kako bismo testirali naš novi compliance algoritam.
- Kandidati: SAD, Singapur.
Struktura problema
Ovo je klasičan problem minimizacije gdje su ograničenja tipa “veće ili jednako 1” (\(\ge 1\)).
Varijable odluke: \[ x_j \in \{0, 1\}, \quad j = 1 \dots 5 \quad (\text{1 ako ulazimo na tržište, 0 inače}) \]
Funkcija cilja (minimizacija troška): \[ \min (150x_1 + 60x_2 + 90x_3 + 110x_4 + 70x_5) \]
Ograničenja (pokrivanje ciljeva):
- Engleski: (SAD ili UK ili Singapur \(\ge 1\)) \[ x_1 + x_3 + x_4 \ge 1 \]
- Azija: (Singapur ili Indija \(\ge 1\)) \[ x_4 + x_5 \ge 1 \]
- Rast: (Brazil ili Indija \(\ge 1\)) \[ x_2 + x_5 \ge 1 \]
- Kupovna moć: (SAD ili UK \(\ge 1\)) \[ x_1 + x_3 \ge 1 \]
- Regulativa: (SAD ili Singapur \(\ge 1\)) \[ x_1 + x_4 \ge 1 \]
library(lpSolve)
# Troškovi ulaska (u tisućama)
costs <- c(150, 60, 90, 110, 70)
constr <- matrix(c(
# SAD, Bra, UK, Sin, Ind
1, 0, 1, 1, 0, # 1. Engleski
0, 0, 0, 1, 1, # 2. Azija
0, 1, 0, 0, 1, # 3. Rast (Growth)
1, 0, 1, 0, 0, # 4. Kupovna moć
1, 0, 0, 1, 0 # 5. Regulativa
), nrow = 5, byrow = TRUE)
rhs <- rep(1, 5) # Sva ograničenja su ">= 1" (Set Covering)
constr_dir <- rep(">=", 5)
solution <- lp(
direction = "min",
objective.in = costs,
const.mat = constr,
const.dir = constr_dir,
const.rhs = rhs,
all.bin = TRUE
)
# Imena ciljeva za lakše snalaženje
goals <- c("Engleski jezik", "Azijska prisutnost", "Rast (Growth)",
"Visoka kupovna moć", "Stroga regulativa")
# Imena tržišta
markets <- c("SAD", "Brazil", "UK", "Singapur", "Indija")
selected_idx <- which(solution$solution == 1)
df_result <- data.frame(
Trziste = markets[selected_idx],
Trosak = costs[selected_idx]
)
print(df_result)## Trziste Trosak
## 1 SAD 150
## 2 Indija 70cat("\nUkupni trošak ekspanzije:", solution$objval, "000 € \n")##
## Ukupni trošak ekspanzije: 220 000 €for(i in 1:5) {
# Koji od ODABRANIH tržišta pokrivaju cilj 'i'?
covering_markets <- markets[which(constr[i, ] == 1 & solution$solution == 1)]
cat(paste0(goals[i], ": Pokriveno s -> ", paste(covering_markets, collapse=", "),
"\n"))
}## Engleski jezik: Pokriveno s -> SAD
## Azijska prisutnost: Pokriveno s -> Indija
## Rast (Growth): Pokriveno s -> Indija
## Visoka kupovna moć: Pokriveno s -> SAD
## Stroga regulativa: Pokriveno s -> SADPokretanjem koda dobivamo optimalno rješenje koje predlaže ulazak na dva tržišta: SAD i Indija. Ukupni trošak ove strategije iznosi 220000 eura.
Ovaj rezultat je na prvi pogled možda iznenađujući jer je SAD pojedinačno najskuplja opcija s cijenom od 150000 eura. Ljudska intuicija često nas navodi da izbjegavamo najskuplje stavke i pokušamo kombinirati jeftinije opcije poput Brazila ili UK-a. Međutim, algoritam nam otkriva snagu efikasnosti pokrivanja. SAD, iako skup, jednim potezom rješava tri ključna problema: pokriva zahtjev za engleskim jezikom, osigurava tržište s visokom kupovnom moći i zadovoljava uvjet stroge regulative.
Kada SAD-u pridružimo Indiju, koja je relativno povoljna s cijenom od 70 000 eura, ona popunjava preostale praznine: osigurava prisutnost u Aziji i pokriva zahtjev za tržištem u razvoju.
Usporedimo li to s alternativom bez SAD-a, morali bismo odabrati UK za kupovnu moć, Singapur za regulativu i Indiju za rast, što bi ukupno koštalo 270 000 eura. Dakle, kombinacija jedne skupe i jedne jeftine opcije u ovom je slučaju znatno isplativija od kombinacije triju srednje skupih opcija. Ovo je klasičan primjer kako set covering problemi ne traže najjeftinije pojedinačne komponente, već najefikasnije kombinacije koje zadovoljavaju sve uvjete.
Mješovito cjelobrojno programiranje (MILP)
U stvarnosti, sustavi su rijetko potpuno diskretni ili potpuno kontinuirani. Najčešće su hibridni. Tu nastupa MILP (Mixed Integer Linear Programming) – najfleksibilniji i najčešće korišten oblik optimizacije u praksi.
U MILP modelima, neke varijable moraju biti cijeli brojevi (ili binarne), dok druge mogu biti kontinuirane.
Matematička definicija
\[ \begin{aligned} \text{Neke } x_i \in \mathbb{Z} \quad &(\text{npr. broj strojeva}) \\ \text{Neke } x_j \in \mathbb{R} \quad &(\text{npr. količina struje, vrijeme, tekućina}) \end{aligned} \]
Primjena
Zamislite pokretanje proizvodnje.
- Morate donijeti binarnu odluku: Pokrenuti stroj ili ne? (Fiksni trošak, \(y \in \{0,1\}\)).
- Ako je stroj pokrenut, morate odlučiti koliko proizvesti? (Varijabilni trošak, kontinuirana varijabla \(x \ge 0\)).
Ovaj tip modeliranja omogućuje nam rješavanje kompleksnih problema poput dizajna opskrbnih lanaca, gdje odlučujemo gdje otvoriti skladišta (binarno), a zatim koliko robe slati iz njih (kontinuirano).
Talebi i sur. (2025) i povezuju teoriju izbora potrošača s konkretnim odlukama o cijenama tako da integriraju diskretne choice modele temeljene na Random Regret Minimization s MILP modelom za optimizaciju prihoda. Cijene proizvoda tretiraju se kao varijable odluke, kapaciteti kao ograničenja, a diskretni izbor kupaca modelira se preko cjelobrojnih varijabli koje povezuju „koju opciju tko bira“ s ukupnom potražnjom i prihodima. Time pokazuju tipičnu situaciju u kojoj čisti LP (s kontinuiranom potražnjom) nije dovoljan, jer se odluke kupaca događaju u diskretnim izborima među tarifama ili proizvodima, pa RRM-DCM + MILP daje realističniji i finije kontroliran model cjenovne politike.
Benati i Rizzi (2007) formuliraju izbor portfelja s ograničenjem na Value-at-Risk (VaR) kao mješoviti cjelobrojni linearni program. Klasični Markowitzov model s varijancom može se zapisati kvadratno, ali čim se u model uvede VaR (koji je po prirodi parcijalno linearan i uključuje scenarije) te logiku tipa maksimalan broj pozicija u portfelju ili minimalne/ maksimalne udjele, prirodno se pojavljuju binarne i cjelobrojne varijable. U njihovoj formulaciji, kontinuirane varijable predstavljaju udjele kapitala u pojedinim imovinama, dok binarne varijable odlučuju hoće li se neki instrument uopće uključiti, a dodatne linearizacije omogućuju da se VaR pojavi u funkciji cilja ili ograničenjima kao linearni izraz. To je vrlo čist i „knjiški“ primjer kako MILP ulazi u financijsko odlučivanje kada kombiniraš kvantitativni rizik i diskretne investicijske odluke.
Mashayekh i suradnici (2017) koriste MILP za istovremenu optimizaciju portfelja distribuiranih izvora energije (DER), njihove veličine i lokacije u multi-energetskim mikromrežama. Kontinuirane varijable opisuju tokove energije (struja, toplina, plin), dok binarne varijable odlučuju hoće li se pojedini tip izvora (npr. kogeneracija, baterije, fotonapon) uopće instalirati na određenoj lokaciji. Model mora istodobno poštovati energetske bilance, kapacitete i međusobna tehnološka ograničenja, pa je tipičan MILP: kombinira diskretne investicijske odluke s kontinuiranim operativnim tokovima.
Mikolajková, Saxén i Pettersson (2018) formuliraju opskrbu lokalnog tržišta plinom kao MILP problem u kojem se odlučuje koliko plina povući iz različitih izvora i kako ga transportirati kroz mrežu do potrošača. Ovdje su protoci plina kontinuirani, ali postoji niz diskretnih odluka: aktivacija pojedinih dobavnih tokova, izbor konfiguracije kompresora, ili prebacivanje između različitih ugovora i tarifnih struktura. Upravo taj miks „tekućih“ tokova i diskretnih tehničkih/komercijalnih opcija čini problem klasičnim MILP-om.
Sangaiah i suradnici (2020) na sličan način tretiraju LNG lanac opskrbe: planiranje nabave, transporta, skladištenja i distribucije formulirano je kao robusni MILP. Binarne varijable biraju koje rute i koje terminale koristiti, kontinuirane varijable opisuju količine LNG-a, a robusna formulacija uzima u obzir neizvjesnosti u potražnji i cijenama. Pant i sur. (2018) šire taj pogled na cjelokupnu višerazinsku, „closed-loop“ opskrbnu mrežu, gdje se uz tokove materijala modeliraju i povrati/recikliranje – opet kombinacija diskretnih odluka o otvaranju čvorova i kontinuiranih tokova kroz mrežu.
da Silva i suradnici (2006) prikazuju agregatno planiranje proizvodnje kao problem višekriterijskog MILP-a, uz interaktivni sustav podrške odlučivanju. U njihovom modelu kontinuirane varijable predstavljaju proizvodne količine, zalihe i tokove, dok binarne varijable odlučuju o aktivaciji pojedinih planova ili scenarija (npr. prekovremeni rad, podugovaranje, otvaranje dodatnih kapaciteta). Kroz višekriterijsku formulaciju istovremeno se balansiraju troškovi, razina usluge i stabilnost plana, a interaktivni DSS omogućuje menadžerima da mijenjaju težine kriterija i vide kako se mijenja optimalno rješenje.
Askari-Nasab i suradnici (2011) koriste MILP za raspoređivanje proizvodnje u otvorenim kopovima (open-pit mine scheduling). Svaki blok rude može se iskopati ili ne (binarna varijabla), pri čemu postoje složena prostorna i tehnološka ograničenja – ne može se iskopati blok na dnu dok nisu maknuti oni iznad njega, rudnik mora zadovoljavati kapacitete opreme, kvalitetu smjese, ograničenja na godišnju proizvodnju itd. U ovom kontekstu MILP spaja geometriju ležišta (prethodnosni odnosi između blokova) s višegodišnjim planiranjem volumena i kvalitete proizvodnje, što čini problem odličnim primjerom kako diskretne i kontinuirane odluke moraju biti zajedno optimirane.
Mješovito cjelobrojno programiranje možemo shvatiti kao prirodno proširenje klasičnog linearnog programiranja, čistog cjelobrojnog programiranja i mrežnih modela. S LP-a preuzima linearnu strukturu i efikasne relaksacije, s IP-a diskretne odluke (koliko strojeva, projekata, ljudi…), a s mrežnih modela tokove, rute i strukturu čvorova i lukova. Zahvaljujući binarnim i cjelobrojnim varijablama, te Big-M i sličnim konstrukcijama, MILP nam omogućuje da u iste modele ugradimo logičke uvjete, fiksne troškove, kapacitete i hijerarhijske odluke. Zbog te kombinacije ono pokriva gotovo čitav spektar realističnih optimizacijskih problema – od čisto kontinuiranih LP-zadataka, preko diskretnih IP-modela, do vrlo kompleksnih mrežnih i lančanih sustava u kojima se istovremeno donose strateške, taktičke i operativne odluke.
Primjer
Proširujemo prethodni problem globalne ekspanzije za fintech aplikaciju. U prethodnom koraku odlučili smo koja tržišta strateški moramo otvoriti kako bismo zadovoljili uvjete investitora. No, stvarni život je složeniji. Nije dovoljno samo “otvoriti” tržište; moramo alocirati resurse kako bismo na tom tržištu ostvarili profit.
Suočeni ste s problemom mješovitog cjelobrojnog programiranja (MILP). Morate istovremeno donijeti tri vrste odluka:
Strateške (binarne): Na koja tržišta ući?
Operativne (cjelobrojne): Koliko servera i zaposlenika alocirati svakom otvorenom tržištu?
Financijske (kontinuirane): Koliko novca uložiti u marketing na svakom tržištu?
Vaš cilj je maksimizirati ukupni godišnji profit tvrtke.
- Ekonomski podaci po tržištima
Analitičari su za svako od 5 potencijalnih tržišta procijenili fiksne troškove ulaska, očekivani “bazni” prihod (prihod koji dolazi samim prisustvom na tržištu zbog organskog rasta) te efikasnost marketinga (ROI).
| Tržište | Fiksni trošak ulaska | Bazni godišnji prihod | Marketing ROI (Povrat na 1€) |
|---|---|---|---|
| SAD | 150 | 400 | 5.0 |
| Brazil | 60 | 150 | 3.0 |
| UK | 90 | 250 | 4.0 |
| Singapur | 110 | 200 | 3.5 |
| Indija | 70 | 100 | 2.5 |
Napomena za Marketing ROI: Faktor 5 znači da za svakih 1000 € uloženih u marketing, generirate 5000 € prihoda.
- Strateška ograničenja (Set Covering)
Kao i u prethodnoj fazi, odabrani skup tržišta mora zadovoljiti strateške ciljeve investitora. Morate odabrati kombinaciju tržišta koja osigurava prisutnost u sljedećim kategorijama (minimalno jedno tržište po kategoriji):
- Engleski jezik: SAD, UK, Singapur.
- Azijska prisutnost: Singapur, Indija.
- Rast (Growth): Brazil, Indija.
- Visoka kupovna moć: SAD, UK.
- Stroga regulativa: SAD, Singapur.
- Operativna pravila i troškovi
Ako odlučite ući na tržište (\(x_j=1\)), morate uspostaviti infrastrukturu prema sljedećim pravilima:
- Najam jednog servera košta 2000 € godišnje.
- Jedan zaposlenik korisničke podrške košta 30000 € godišnje (bruto 2).
- Ako uđete na tržište, morate zakupiti minimalno 2 servera kako bi usluga bila stabilna.
- Na svaka 2 servera (koji impliciraju određeni volumen prometa), morate zaposliti barem 1 djelatnika podrške.
- Ne možete alocirati servere, ljude ili marketinški budžet na tržište na koje niste ušli.
- Globalna ograničenja resursa
Tvrtka ima ograničene resurse na razini cijele grupe:
- Ukupno na raspolaganju imate maksimalno 30 servera visoke performanse za globalno širenje.
- Ukupan iznos za marketing na svim tržištima ne smije prelaziti 500000 €.
- Zbog smanjenja efikasnosti oglasa pri velikom volumenu, ne smijete uložiti više od 200000 € u marketing na jednom pojedinačnom tržištu.
Imamo tri vrste odluka koje moramo donijeti istovremeno. Prvo, binarne odluke o ulasku na tržište. Ako uđemo na tržište, plaćamo fiksni trošak ulaska (pravni i tehnički setup). Drugo, cjelobrojne odluke o infrastrukturi i ljudima. Za svako odabrano tržište moramo zakupiti određeni broj servera ovisno o očekivanom prometu, te zaposliti djelatnike korisničke podrške. Treće, kontinuirane odluke o budžetu. Za svako tržište moramo odrediti iznos marketinškog budžeta. Što više uložimo, očekujemo veći prihod, ali uz opadajući povrat investicije.
Definiramo 4 skupa varijabli za svako od 5 tržišta (ukupno 20 varijabli). \(x_j\) je binarna varijabla (1 ako ulazimo, 0 inače). \(s_j\) je cjelobrojna varijabla koja predstavlja broj servera. \(e_j\) je cjelobrojna varijabla koja predstavlja broj zaposlenih u podršci. \(m_j\) je kontinuirana varijabla koja predstavlja marketinški budžet (u tisućama eura).
Model uključuje sljedeća ograničenja. Prvo, strateška pokrivenost (iz prethodnog primjera). Moramo zadovoljiti uvjete jezika, regije i regulative. Drugo, logička povezanost (Big M metoda). Ne možemo alocirati servere, ljude ili marketing na tržište na koje nismo ušli. Ako je \(x_j = 0\), onda i \(s_j\), \(e_j\) i \(m_j\) moraju biti 0. Treće, operativni minimumi. Ako uđemo na tržište (\(x_j = 1\)), moramo imati minimalno 2 servera da bi usluga radila. Četvrto, omjer podrške. Na svaka 2 servera (koji impliciraju određeni broj korisnika), moramo zaposliti barem 1 djelatnika podrške. Peto, globalni resursi. Ukupno na raspolaganju imamo 30 servera i 500000 eura za marketing.
Ekonomski parametri su sljedeći: Svaki server košta 2000 € godišnje. Svaki zaposlenik košta 30000 € godišnje. Prihod se modelira kao funkcija: \(\text{Profit=(Bazni Prihod+Prihod od Marketinga)−(Fiksni Trošak+Trošak Servera+Trošak Osoblja+Ulog u Marketing)}\), gdje je: \(\text{Prihod od Marketinga=Ulog×ROI}\). Neka tržišta poput SAD-a imaju visoku bazu i visok povrat na marketing, dok druga imaju manji.
Struktura problema - raspisano
Budući da ovaj model sadrži čak 20 varijabli različitih tipova, zapisivanje pomoću suma (\(\sum\)) može sakriti stvarnu složenost problema. Kako bismo točno razumjeli što se događa (i kako ćemo kasnije slagati matricu u R-u), raspisat ćemo model u potpunosti.
- Definiranje varijabli
Naš vektor rješenja imat će 20 elemenata. Poredani su po tipu, a unutar tipa po tržištima (SAD, Brazil, UK, Singapur, Indija):
Binarne varijable (ulazak na tržište):
- \(x_1\) = SAD
- \(x_2\) = Brazil
- \(x_3\) = UK
- \(x_4\) = Singapur
- \(x_5\) = Indija
Cjelobrojne varijable (broj servera):
- \(s_1\) = Serveri (SAD)
- \(s_2\) = Serveri (Brazil)
- \(s_3\) = Serveri (UK)
- \(s_4\) = Serveri (Singapur)
- \(s_5\) = Serveri (Indija)
Cjelobrojne varijable (broj zaposlenika):
- \(e_1\) = Zaposlenici (SAD)
- \(e_2\) = Zaposlenici (Brazil)
- \(e_3\) = Zaposlenici (UK)
- \(e_4\) = Zaposlenici (Singapur)
- \(e_5\) = Zaposlenici (Indija)
Kontinuirane varijable (budžet za marketing u ’000 €):
\(m_1\) = Marketing (SAD)
\(m_2\) = Marketing (Brazil)
\(m_3\) = Marketing (UK)
\(m_4\) = Marketing (Singapur)
\(m_5\) = Marketing (Indija)
Funkcija cilja (maksimizacija Profita)
Tražimo \(\max Z\). Koeficijenti uz varijable predstavljaju neto doprinos profitu.
Uz \(x\) (Ulazak): Bazni prihod minus fiksni trošak.
- SAD: \(400 - 150 = 250\)
- Brazil: \(150 - 60 = 90\)
- UK: \(250 - 90 = 160\)
- Singapur: \(200 - 110 = 90\)
- Indija: \(100 - 70 = 30\)
Uz \(s\) (Serveri): Trošak je -2 po serveru.
Uz \(e\) (Zaposlenici): Trošak je -30 po zaposleniku.
Uz \(m\) (Marketing): Prihod od ROI minus uloženo (ROI - 1).
- SAD: \(5.0 - 1 = 4.0\)
- Brazil: \(3.0 - 1 = 2.0\)
- UK: \(4.0 - 1 = 3.0\)
- Singapur: \(3.5 - 1 = 2.5\)
- Indija: \(2.5 - 1 = 1.5\)
Cjelovita funkcija:
\[ \begin{aligned} \max \quad & (250x_1 + 90x_2 + 160x_3 + 90x_4 + 30x_5 \\ & - 2s_1 - 2s_2 - 2s_3 - 2s_4 - 2s_5 \\ & - 30e_1 - 30e_2 - 30e_3 - 30e_4 - 30e_5 \\ & + 4m_1 + 2m_2 + 3m_3 + 2.5m_4 + 1.5m_5) \end{aligned} \]
- Ograničenja
A) Strateška pokrivenost (Set Covering)
Ovo su ista ograničenja kao u binarnom problemu, tiču se samo varijabli \(x\).
- Engleski: \(x_1 + x_3 + x_4 \ge 1\)
- Azija: \(x_4 + x_5 \ge 1\)
- Rast: \(x_2 + x_5 \ge 1\)
- Kupovna moć: \(x_1 + x_3 \ge 1\)
- Regulativa: \(x_1 + x_4 \ge 1\)
B) Logička povezanost (Big M metoda)
Ovdje povezujemo odluke. Ako nismo ušli na tržište (\(x=0\)), ne smijemo trošiti resurse.
Big M metoda je tehnika kojom povezujemo binarnu varijablu (0/1) s količinskom varijablom, koristeći proizvoljno veliki broj \(M\) kao “prekidač” u ograničenju oblika \(\text{resurs} \leq M \cdot x\).
Primjenjuje se kako bi se matematički osiguralo da varijabla resursa (npr. broj servera) mora biti nula ako je binarna odluka \(x=0\) (nismo ušli na tržište), dok u suprotnom (\(x=1\)) dozvoljava korištenje resursa sve do gornjeg limita \(M\).
M treba biti “dovoljno velik”, ali što je moguće manji. M mora biti gornja granica koju varijabla ikada može doseći u realnom scenariju. Ako je M premali, model će pogrešno “odrezati” valjana rješenja.
Koristimo je u situacijama kada je trošenje nekog resursa ili budžeta logički moguće isključivo ako je prethodno donesena pozitivna strateška odluka o pokretanju projekta.
Matematički oblik:
\(\text{Resurs} \le M \cdot x \implies \text{Resurs} - M \cdot x \le 0\).
Za tržište 1 (SAD):
- Serveri (SAD): \(s_1 - 100x_1 \le 0\)
- Marketing (SAD): \(m_1 - 200x_1 \le 0\)
(Ponavlja se za ostala 4 tržišta…)
Napomena: Npr., imamo globalno ograničenje budžeta od 500000 €. Također, imamo lokalno ograničenje od 200000 € po zemlji. Logički, varijabla marketinga za jednu zemlju (\(m_j\)) nikada ne može biti veća od 200. Dakle, savršen M za marketing je 200. Ako bismo stavili \(M=100\), model bi nam zabranio da uložimo 150, iako je to dopušteno. Ako stavimo nepotrebno ogroman broj (npr. \(10^9\)), događaju se dvije loše stvari: (1) Računala ne računaju s beskonačnom preciznošću. U računalnoj aritmetici, ako zbrajate ogroman broj i vrlo mali broj, ovaj manji se može “izgubiti” (zaokružiti) zbog greške u decimalnom zarezu. To može dovesti do toga da solver misli da je uvjet zadovoljen kad nije, ili obrnuto. (2) Solver prvo rješava problem kao da varijable nisu cijeli brojevi (to se zove LP relaksacija), a tek onda traži cjelobrojna rješenja. Ako je M ogroman, to početno “opušteno” rješenje je jako daleko od stvarnosti, pa solveru treba puno više vremena da suzi prostor pretrage i nađe cjelobrojno rješenje.
C) Operativni minimumi
Ako uđemo (\(x=1\)), moramo imati barem 2 servera. Ako ne uđemo (\(x=0\)), serveri su 0.
Matematički oblik: \(s \ge 2x \implies s - 2x \ge 0\).
Za tržište 1 (SAD):
- Min. infrastruktura (SAD): \(s_1 - 2x_1 \ge 0\)
(Ponavlja se za ostala 4 tržišta…)
(Napomena: Ovo osigurava da ako je \(x_1=1\), onda \(s_1 \ge 2\). Ako je \(x_1=0\), onda \(s_1 \ge 0\), što je već zadano, ali gornje Big M ograničenje će prisiliti \(s_1=0\).)
D) Omjer podrške
Zaposlenici moraju biti barem polovica broja servera (\(e \ge 0.5s\)).
Matematički oblik: \(2e \ge s \implies 2e - s \ge 0\).
Za tržište 1 (SAD):
- Podrška (SAD): \(2e_1 - s_1 \ge 0\)
(Ponavlja se za ostala 4 tržišta…)
E) Globalna ograničenja
Odnose se na sumu resursa na razini cijele tvrtke.
- Max servera: \(s_1 + s_2 + s_3 + s_4 + s_5 \le 30\)
- Max marketing budžet: \(m_1 + m_2 + m_3 + m_4 + m_5 \le 500\)
Struktura problema - sažeti zapis
Indeksi: \(j = 1, \dots, 5\) (1=SAD, 2=Brazil, 3=UK, 4=Singapur, 5=Indija)
Varijable odluke:
Modeliramo četiri skupa varijabli za svako tržište:
- Strateške (Binarna): \(x_j \in \{0, 1\}\)
- 1 ako ulazimo na tržište \(j\), 0 inače.
- Infrastrukturne (Cjelobrojna): \(s_j \in \mathbb{Z}, s_j \ge 0\)
- Broj zakupljenih servera na tržištu \(j\).
- Kadrovske (Cjelobrojna): \(e_j \in \mathbb{Z}, e_j \ge 0\)
- Broj zaposlenika podrške na tržištu \(j\).
- Financijske (Kontinuirana): \(m_j \ge 0\)
- Uloženi marketinški budžet na tržištu \(j\) (u tisućama €).
Funkcija cilja (Maksimizacija profita):
Cilj je maksimizirati razliku između ukupnih prihoda i ukupnih troškova.
\[ \max \big( \sum_{j=1}^{5} \left[ (\text{Bazni}_j \cdot x_j) + (\text{ROI}_j \cdot m_j) - (\text{Fiksni}_j \cdot x_j) - (2 \cdot s_j) - (30 \cdot e_j) - (1 \cdot m_j) \right] \big) \]
Pojednostavljeno (grupiranjem uz varijable):
\[ \max \big(\sum_{j=1}^{5} \left[ (\text{Bazni}_j - \text{Fiksni}_j)x_j - 2s_j - 30e_j + (\text{ROI}_j - 1)m_j \right]\big) \]
Ograničenja:
- Strateška pokrivenost (Set Covering):
- Engleski: \(x_1 + x_3 + x_4 \ge 1\)
- Azija: \(x_4 + x_5 \ge 1\)
- Rast: \(x_2 + x_5 \ge 1\)
- Kupovna moć: \(x_1 + x_3 \ge 1\)
- Regulativa: \(x_1 + x_4 \ge 1\)
Logička povezanost (Big M metoda):
Osigurava da su resursi 0 ako ne uđemo na tržište.
- Serveri: \(s_j \le 100 \cdot x_j\) (gdje je 100 dovoljno veliki broj M)
- Osoblje: \(e_j \le 100 \cdot x_j\)
- Marketing: \(m_j \le 200 \cdot x_j\) (ujedno limitira max marketing po zemlji na 200k)
Operativni minimumi:
Ako je tržište otvoreno, mora imati minimalnu infrastrukturu.
- \(s_j \ge 2 \cdot x_j\)
Omjer podrške:
Broj zaposlenih mora biti barem polovica broja servera.
- \(e_j \ge 0.5 \cdot s_j \implies 2e_j - s_j \ge 0\)
- Globalna ograničenja resursa:
- Ukupno servera: \(\sum s_j \le 30\)
- Ukupni marketing: \(\sum m_j \le 500\) (tisuća €)
library(lpSolve)
# 1. Fiksni troškovi ulaska (iz prošlog primjera)
fixed_entry_cost <- c(150, 60, 90, 110, 70)
# 2. Ekonomski potencijal
base_revenue <- c(400, 150, 250, 200, 100) # Prihod samim ulaskom
marketing_roi <- c(5.0, 3.0, 4.0, 3.5, 2.5) # Povrat na 1€ marketinga
# 3. Troškovi resursa
cost_per_server <- 2 # tisuće eura
cost_per_employee <- 30 # tisuće eura
# Varijable su poredane:
# 1-5: x (Binarno, Ulaz)
# 6-10: s (Integer, Serveri)
# 11-15: e (Integer, Zaposlenici)
# 16-20: m (Continuous, Marketing)
# Funkcija cilja (Maksimizacija Profita)
# Profit = Prihod - Troškovi
# Max: (BaseRev * x) + (ROI * m) - (Fixed * x) - (S_cost * s) - (E_cost * e) - (1 * m)
# Grupiramo uz varijable:
# Coeff za x: BaseRev - Fixed
# Coeff za s: -S_cost
# Coeff za e: -E_cost
# Coeff za m: ROI - 1
obj_x <- base_revenue - fixed_entry_cost
obj_s <- rep(-cost_per_server, 5)
obj_e <- rep(-cost_per_employee, 5)
obj_m <- marketing_roi - 1
objective <- c(obj_x, obj_s, obj_e, obj_m)Jedan od ciljeva ovog materijala je da vidite korak po korak kako kreiramo matricu ograničenja kad imamo jako puno ograničenja. U ovakvoj situaciji, praktičnije je upisivati dio po dio ograničenja, umjesto ručnog upisa glomazne matrice. Zato ćemo:
- prvo složiti podmatricu za strateška ograničenja (set covering),
- zatim ju proširiti nulama za ostale varijable,
- na kraju dodati Big-M, minimalne resurse i globalna ograničenja.
# Inicijalizacija matrica za ograničenja (zadajemo praznu matricu/vektore, pa popunjavamo)
con_matrix <- matrix(0, nrow = 0, ncol = 20)
con_rhs <- c()
con_dir <- c()
# 1. STRATEŠKA OGRANIČENJA (Set Covering iz prošlog primjera)
# Odnose se samo na x (prvih 5 varijabli)
sc_matrix <- matrix(c(
1, 0, 1, 1, 0, # Engleski
0, 0, 0, 1, 1, # Azija
0, 1, 0, 0, 1, # Rast
1, 0, 1, 0, 0, # Kupovna moć
1, 0, 0, 1, 0 # Regulativa
), nrow = 5, byrow = TRUE)
sc_matrix## [,1] [,2] [,3] [,4] [,5]
## [1,] 1 0 1 1 0
## [2,] 0 0 0 1 1
## [3,] 0 1 0 0 1
## [4,] 1 0 1 0 0
## [5,] 1 0 0 1 0# Proširujemo nulama za s, e, m
sc_full <- cbind(sc_matrix, matrix(0, 5, 15)) # spajanje po stupcima (proširujemo/ popunjavamo matricu u desno s nulama za varijable koje ovdje nisu uključene)
sc_full## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14]
## [1,] 1 0 1 1 0 0 0 0 0 0 0 0 0 0
## [2,] 0 0 0 1 1 0 0 0 0 0 0 0 0 0
## [3,] 0 1 0 0 1 0 0 0 0 0 0 0 0 0
## [4,] 1 0 1 0 0 0 0 0 0 0 0 0 0 0
## [5,] 1 0 0 1 0 0 0 0 0 0 0 0 0 0
## [,15] [,16] [,17] [,18] [,19] [,20]
## [1,] 0 0 0 0 0 0
## [2,] 0 0 0 0 0 0
## [3,] 0 0 0 0 0 0
## [4,] 0 0 0 0 0 0
## [5,] 0 0 0 0 0 0con_matrix <- rbind(con_matrix, sc_full) # spajanje po retcima
con_matrix ## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14]
## [1,] 1 0 1 1 0 0 0 0 0 0 0 0 0 0
## [2,] 0 0 0 1 1 0 0 0 0 0 0 0 0 0
## [3,] 0 1 0 0 1 0 0 0 0 0 0 0 0 0
## [4,] 1 0 1 0 0 0 0 0 0 0 0 0 0 0
## [5,] 1 0 0 1 0 0 0 0 0 0 0 0 0 0
## [,15] [,16] [,17] [,18] [,19] [,20]
## [1,] 0 0 0 0 0 0
## [2,] 0 0 0 0 0 0
## [3,] 0 0 0 0 0 0
## [4,] 0 0 0 0 0 0
## [5,] 0 0 0 0 0 0con_rhs <- c(con_rhs, rep(1, 5))
con_rhs## [1] 1 1 1 1 1con_dir <- c(con_dir, rep(">=", 5))
con_dir## [1] ">=" ">=" ">=" ">=" ">="# 2. LOGIČKA POVEZANOST (Big M)
# Ako x=0, onda s=0. => s <= M*x => s - M*x <= 0
# Ako x=0, onda m=0. => m <= M*x => m - M*x <= 0
M_serv <- 100
M_mark <- 200 # Max marketing budget po zemlji
for(i in 1:5) {
# Za servere
row <- numeric(20)
row[5 + i] <- 1 # s_i
row[i] <- -M_serv # -100 * x_i
con_matrix <- rbind(con_matrix, row)
con_rhs <- c(con_rhs, 0)
con_dir <- c(con_dir, "<=")
# Za marketing
row <- numeric(20)
row[15 + i] <- 1 # m_i
row[i] <- -M_mark # -200 * x_i
con_matrix <- rbind(con_matrix, row)
con_rhs <- c(con_rhs, 0)
con_dir <- c(con_dir, "<=")
}
con_matrix## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14]
## 1 0 1 1 0 0 0 0 0 0 0 0 0 0
## 0 0 0 1 1 0 0 0 0 0 0 0 0 0
## 0 1 0 0 1 0 0 0 0 0 0 0 0 0
## 1 0 1 0 0 0 0 0 0 0 0 0 0 0
## 1 0 0 1 0 0 0 0 0 0 0 0 0 0
## row -100 0 0 0 0 1 0 0 0 0 0 0 0 0
## row -200 0 0 0 0 0 0 0 0 0 0 0 0 0
## row 0 -100 0 0 0 0 1 0 0 0 0 0 0 0
## row 0 -200 0 0 0 0 0 0 0 0 0 0 0 0
## row 0 0 -100 0 0 0 0 1 0 0 0 0 0 0
## row 0 0 -200 0 0 0 0 0 0 0 0 0 0 0
## row 0 0 0 -100 0 0 0 0 1 0 0 0 0 0
## row 0 0 0 -200 0 0 0 0 0 0 0 0 0 0
## row 0 0 0 0 -100 0 0 0 0 1 0 0 0 0
## row 0 0 0 0 -200 0 0 0 0 0 0 0 0 0
## [,15] [,16] [,17] [,18] [,19] [,20]
## 0 0 0 0 0 0
## 0 0 0 0 0 0
## 0 0 0 0 0 0
## 0 0 0 0 0 0
## 0 0 0 0 0 0
## row 0 0 0 0 0 0
## row 0 1 0 0 0 0
## row 0 0 0 0 0 0
## row 0 0 1 0 0 0
## row 0 0 0 0 0 0
## row 0 0 0 1 0 0
## row 0 0 0 0 0 0
## row 0 0 0 0 1 0
## row 0 0 0 0 0 0
## row 0 0 0 0 0 1con_rhs## [1] 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0con_dir## [1] ">=" ">=" ">=" ">=" ">=" "<=" "<=" "<=" "<=" "<=" "<=" "<=" "<=" "<=" "<="# 3. OPERATIVNI MINIMUMI
# Ako x=1, s >= 2. => s >= 2x => s - 2x >= 0
for(i in 1:5) {
row <- numeric(20)
row[5 + i] <- 1 # s_i
row[i] <- -2 # -2 * x_i
con_matrix <- rbind(con_matrix, row)
con_rhs <- c(con_rhs, 0)
con_dir <- c(con_dir, ">=")
}
con_matrix## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14]
## 1 0 1 1 0 0 0 0 0 0 0 0 0 0
## 0 0 0 1 1 0 0 0 0 0 0 0 0 0
## 0 1 0 0 1 0 0 0 0 0 0 0 0 0
## 1 0 1 0 0 0 0 0 0 0 0 0 0 0
## 1 0 0 1 0 0 0 0 0 0 0 0 0 0
## row -100 0 0 0 0 1 0 0 0 0 0 0 0 0
## row -200 0 0 0 0 0 0 0 0 0 0 0 0 0
## row 0 -100 0 0 0 0 1 0 0 0 0 0 0 0
## row 0 -200 0 0 0 0 0 0 0 0 0 0 0 0
## row 0 0 -100 0 0 0 0 1 0 0 0 0 0 0
## row 0 0 -200 0 0 0 0 0 0 0 0 0 0 0
## row 0 0 0 -100 0 0 0 0 1 0 0 0 0 0
## row 0 0 0 -200 0 0 0 0 0 0 0 0 0 0
## row 0 0 0 0 -100 0 0 0 0 1 0 0 0 0
## row 0 0 0 0 -200 0 0 0 0 0 0 0 0 0
## row -2 0 0 0 0 1 0 0 0 0 0 0 0 0
## row 0 -2 0 0 0 0 1 0 0 0 0 0 0 0
## row 0 0 -2 0 0 0 0 1 0 0 0 0 0 0
## row 0 0 0 -2 0 0 0 0 1 0 0 0 0 0
## row 0 0 0 0 -2 0 0 0 0 1 0 0 0 0
## [,15] [,16] [,17] [,18] [,19] [,20]
## 0 0 0 0 0 0
## 0 0 0 0 0 0
## 0 0 0 0 0 0
## 0 0 0 0 0 0
## 0 0 0 0 0 0
## row 0 0 0 0 0 0
## row 0 1 0 0 0 0
## row 0 0 0 0 0 0
## row 0 0 1 0 0 0
## row 0 0 0 0 0 0
## row 0 0 0 1 0 0
## row 0 0 0 0 0 0
## row 0 0 0 0 1 0
## row 0 0 0 0 0 0
## row 0 0 0 0 0 1
## row 0 0 0 0 0 0
## row 0 0 0 0 0 0
## row 0 0 0 0 0 0
## row 0 0 0 0 0 0
## row 0 0 0 0 0 0con_rhs## [1] 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0con_dir## [1] ">=" ">=" ">=" ">=" ">=" "<=" "<=" "<=" "<=" "<=" "<=" "<=" "<=" "<=" "<="
## [16] ">=" ">=" ">=" ">=" ">="# 4. OMJER PODRŠKE
# Zaposlenici >= 0.5 * Serveri => 2 * e >= s => 2e - s >= 0
for(i in 1:5) {
row <- numeric(20)
row[10 + i] <- 2 # 2 * e_i
row[5 + i] <- -1 # -1 * s_i
con_matrix <- rbind(con_matrix, row)
con_rhs <- c(con_rhs, 0)
con_dir <- c(con_dir, ">=")
}
con_matrix## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14]
## 1 0 1 1 0 0 0 0 0 0 0 0 0 0
## 0 0 0 1 1 0 0 0 0 0 0 0 0 0
## 0 1 0 0 1 0 0 0 0 0 0 0 0 0
## 1 0 1 0 0 0 0 0 0 0 0 0 0 0
## 1 0 0 1 0 0 0 0 0 0 0 0 0 0
## row -100 0 0 0 0 1 0 0 0 0 0 0 0 0
## row -200 0 0 0 0 0 0 0 0 0 0 0 0 0
## row 0 -100 0 0 0 0 1 0 0 0 0 0 0 0
## row 0 -200 0 0 0 0 0 0 0 0 0 0 0 0
## row 0 0 -100 0 0 0 0 1 0 0 0 0 0 0
## row 0 0 -200 0 0 0 0 0 0 0 0 0 0 0
## row 0 0 0 -100 0 0 0 0 1 0 0 0 0 0
## row 0 0 0 -200 0 0 0 0 0 0 0 0 0 0
## row 0 0 0 0 -100 0 0 0 0 1 0 0 0 0
## row 0 0 0 0 -200 0 0 0 0 0 0 0 0 0
## row -2 0 0 0 0 1 0 0 0 0 0 0 0 0
## row 0 -2 0 0 0 0 1 0 0 0 0 0 0 0
## row 0 0 -2 0 0 0 0 1 0 0 0 0 0 0
## row 0 0 0 -2 0 0 0 0 1 0 0 0 0 0
## row 0 0 0 0 -2 0 0 0 0 1 0 0 0 0
## row 0 0 0 0 0 -1 0 0 0 0 2 0 0 0
## row 0 0 0 0 0 0 -1 0 0 0 0 2 0 0
## row 0 0 0 0 0 0 0 -1 0 0 0 0 2 0
## row 0 0 0 0 0 0 0 0 -1 0 0 0 0 2
## row 0 0 0 0 0 0 0 0 0 -1 0 0 0 0
## [,15] [,16] [,17] [,18] [,19] [,20]
## 0 0 0 0 0 0
## 0 0 0 0 0 0
## 0 0 0 0 0 0
## 0 0 0 0 0 0
## 0 0 0 0 0 0
## row 0 0 0 0 0 0
## row 0 1 0 0 0 0
## row 0 0 0 0 0 0
## row 0 0 1 0 0 0
## row 0 0 0 0 0 0
## row 0 0 0 1 0 0
## row 0 0 0 0 0 0
## row 0 0 0 0 1 0
## row 0 0 0 0 0 0
## row 0 0 0 0 0 1
## row 0 0 0 0 0 0
## row 0 0 0 0 0 0
## row 0 0 0 0 0 0
## row 0 0 0 0 0 0
## row 0 0 0 0 0 0
## row 0 0 0 0 0 0
## row 0 0 0 0 0 0
## row 0 0 0 0 0 0
## row 0 0 0 0 0 0
## row 2 0 0 0 0 0con_rhs## [1] 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0con_dir## [1] ">=" ">=" ">=" ">=" ">=" "<=" "<=" "<=" "<=" "<=" "<=" "<=" "<=" "<=" "<="
## [16] ">=" ">=" ">=" ">=" ">=" ">=" ">=" ">=" ">=" ">="# 5. GLOBALNA OGRANIČENJA
# Ukupno servera <= 30
row_serv <- numeric(20)
row_serv[6:10] <- 1
con_matrix <- rbind(con_matrix, row_serv)
con_rhs <- c(con_rhs, 30)
con_dir <- c(con_dir, "<=")
con_matrix## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13]
## 1 0 1 1 0 0 0 0 0 0 0 0 0
## 0 0 0 1 1 0 0 0 0 0 0 0 0
## 0 1 0 0 1 0 0 0 0 0 0 0 0
## 1 0 1 0 0 0 0 0 0 0 0 0 0
## 1 0 0 1 0 0 0 0 0 0 0 0 0
## row -100 0 0 0 0 1 0 0 0 0 0 0 0
## row -200 0 0 0 0 0 0 0 0 0 0 0 0
## row 0 -100 0 0 0 0 1 0 0 0 0 0 0
## row 0 -200 0 0 0 0 0 0 0 0 0 0 0
## row 0 0 -100 0 0 0 0 1 0 0 0 0 0
## row 0 0 -200 0 0 0 0 0 0 0 0 0 0
## row 0 0 0 -100 0 0 0 0 1 0 0 0 0
## row 0 0 0 -200 0 0 0 0 0 0 0 0 0
## row 0 0 0 0 -100 0 0 0 0 1 0 0 0
## row 0 0 0 0 -200 0 0 0 0 0 0 0 0
## row -2 0 0 0 0 1 0 0 0 0 0 0 0
## row 0 -2 0 0 0 0 1 0 0 0 0 0 0
## row 0 0 -2 0 0 0 0 1 0 0 0 0 0
## row 0 0 0 -2 0 0 0 0 1 0 0 0 0
## row 0 0 0 0 -2 0 0 0 0 1 0 0 0
## row 0 0 0 0 0 -1 0 0 0 0 2 0 0
## row 0 0 0 0 0 0 -1 0 0 0 0 2 0
## row 0 0 0 0 0 0 0 -1 0 0 0 0 2
## row 0 0 0 0 0 0 0 0 -1 0 0 0 0
## row 0 0 0 0 0 0 0 0 0 -1 0 0 0
## row_serv 0 0 0 0 0 1 1 1 1 1 0 0 0
## [,14] [,15] [,16] [,17] [,18] [,19] [,20]
## 0 0 0 0 0 0 0
## 0 0 0 0 0 0 0
## 0 0 0 0 0 0 0
## 0 0 0 0 0 0 0
## 0 0 0 0 0 0 0
## row 0 0 0 0 0 0 0
## row 0 0 1 0 0 0 0
## row 0 0 0 0 0 0 0
## row 0 0 0 1 0 0 0
## row 0 0 0 0 0 0 0
## row 0 0 0 0 1 0 0
## row 0 0 0 0 0 0 0
## row 0 0 0 0 0 1 0
## row 0 0 0 0 0 0 0
## row 0 0 0 0 0 0 1
## row 0 0 0 0 0 0 0
## row 0 0 0 0 0 0 0
## row 0 0 0 0 0 0 0
## row 0 0 0 0 0 0 0
## row 0 0 0 0 0 0 0
## row 0 0 0 0 0 0 0
## row 0 0 0 0 0 0 0
## row 0 0 0 0 0 0 0
## row 2 0 0 0 0 0 0
## row 0 2 0 0 0 0 0
## row_serv 0 0 0 0 0 0 0con_rhs## [1] 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
## [26] 30con_dir## [1] ">=" ">=" ">=" ">=" ">=" "<=" "<=" "<=" "<=" "<=" "<=" "<=" "<=" "<=" "<="
## [16] ">=" ">=" ">=" ">=" ">=" ">=" ">=" ">=" ">=" ">=" "<="# Ukupni marketing <= 500
row_mark <- numeric(20)
row_mark[16:20] <- 1
con_matrix <- rbind(con_matrix, row_mark)
con_rhs <- c(con_rhs, 500)
con_dir <- c(con_dir, "<=")
con_matrix## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13]
## 1 0 1 1 0 0 0 0 0 0 0 0 0
## 0 0 0 1 1 0 0 0 0 0 0 0 0
## 0 1 0 0 1 0 0 0 0 0 0 0 0
## 1 0 1 0 0 0 0 0 0 0 0 0 0
## 1 0 0 1 0 0 0 0 0 0 0 0 0
## row -100 0 0 0 0 1 0 0 0 0 0 0 0
## row -200 0 0 0 0 0 0 0 0 0 0 0 0
## row 0 -100 0 0 0 0 1 0 0 0 0 0 0
## row 0 -200 0 0 0 0 0 0 0 0 0 0 0
## row 0 0 -100 0 0 0 0 1 0 0 0 0 0
## row 0 0 -200 0 0 0 0 0 0 0 0 0 0
## row 0 0 0 -100 0 0 0 0 1 0 0 0 0
## row 0 0 0 -200 0 0 0 0 0 0 0 0 0
## row 0 0 0 0 -100 0 0 0 0 1 0 0 0
## row 0 0 0 0 -200 0 0 0 0 0 0 0 0
## row -2 0 0 0 0 1 0 0 0 0 0 0 0
## row 0 -2 0 0 0 0 1 0 0 0 0 0 0
## row 0 0 -2 0 0 0 0 1 0 0 0 0 0
## row 0 0 0 -2 0 0 0 0 1 0 0 0 0
## row 0 0 0 0 -2 0 0 0 0 1 0 0 0
## row 0 0 0 0 0 -1 0 0 0 0 2 0 0
## row 0 0 0 0 0 0 -1 0 0 0 0 2 0
## row 0 0 0 0 0 0 0 -1 0 0 0 0 2
## row 0 0 0 0 0 0 0 0 -1 0 0 0 0
## row 0 0 0 0 0 0 0 0 0 -1 0 0 0
## row_serv 0 0 0 0 0 1 1 1 1 1 0 0 0
## row_mark 0 0 0 0 0 0 0 0 0 0 0 0 0
## [,14] [,15] [,16] [,17] [,18] [,19] [,20]
## 0 0 0 0 0 0 0
## 0 0 0 0 0 0 0
## 0 0 0 0 0 0 0
## 0 0 0 0 0 0 0
## 0 0 0 0 0 0 0
## row 0 0 0 0 0 0 0
## row 0 0 1 0 0 0 0
## row 0 0 0 0 0 0 0
## row 0 0 0 1 0 0 0
## row 0 0 0 0 0 0 0
## row 0 0 0 0 1 0 0
## row 0 0 0 0 0 0 0
## row 0 0 0 0 0 1 0
## row 0 0 0 0 0 0 0
## row 0 0 0 0 0 0 1
## row 0 0 0 0 0 0 0
## row 0 0 0 0 0 0 0
## row 0 0 0 0 0 0 0
## row 0 0 0 0 0 0 0
## row 0 0 0 0 0 0 0
## row 0 0 0 0 0 0 0
## row 0 0 0 0 0 0 0
## row 0 0 0 0 0 0 0
## row 2 0 0 0 0 0 0
## row 0 2 0 0 0 0 0
## row_serv 0 0 0 0 0 0 0
## row_mark 0 0 1 1 1 1 1con_rhs## [1] 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
## [20] 0 0 0 0 0 0 30 500con_dir## [1] ">=" ">=" ">=" ">=" ">=" "<=" "<=" "<=" "<=" "<=" "<=" "<=" "<=" "<=" "<="
## [16] ">=" ">=" ">=" ">=" ">=" ">=" ">=" ">=" ">=" ">=" "<=" "<="# RJEŠAVANJE (MILP)
# Definiramo tipove varijabli
# 1-5 (x): Binary
# 6-10 (s): Integer
# 11-15 (e): Integer
# 16-20 (m): Continuous (default)
solution <- lp(
direction = "max",
objective.in = objective,
const.mat = con_matrix,
const.dir = con_dir,
const.rhs = con_rhs,
binary.vec = 1:5, # Prvih 5 su binarne
int.vec = 6:15 # Idućih 10 su integer (serveri i ljudi)
)
markets <- c("SAD", "Brazil", "UK", "Singapur", "Indija")
vars <- solution$solution
df_res <- data.frame(
Trziste = markets,
Ulazak = vars[1:5],
Serveri = vars[6:10],
Zaposlenici = vars[11:15],
Marketing = round(vars[16:20], 1)
)
df_res## Trziste Ulazak Serveri Zaposlenici Marketing
## 1 SAD 1 2 1 200
## 2 Brazil 1 2 1 0
## 3 UK 1 2 1 200
## 4 Singapur 1 2 1 100
## 5 Indija 0 0 0 0# Filtriramo samo odabrana tržišta
df_final <- df_res[df_res$Ulazak == 1, ]
df_final## Trziste Ulazak Serveri Zaposlenici Marketing
## 1 SAD 1 2 1 200
## 2 Brazil 1 2 1 0
## 3 UK 1 2 1 200
## 4 Singapur 1 2 1 100cat("\nUkupni ostvareni profit:", round(solution$objval, 2), "tisuća €",
"\nUkupno servera:", sum(df_final$Serveri), "/ 30",
"\nUkupno marketinga:", sum(df_final$Marketing), "/ 500")##
## Ukupni ostvareni profit: 2104 tisuća €
## Ukupno servera: 8 / 30
## Ukupno marketinga: 500 / 500Rezultati ovog mješovitog modela (MILP) pružaju nam uvid u to kako optimizacijski algoritam donosi odluke kada su resursi ograničeni, a ciljevi višeslojni.
Ukupni ostvareni profit iznosi 2104000 €.
Analizirajmo odluke po slojevima:
Strateška razina (Tko je upao, a tko ispao?) Algoritam je odlučio ući na tržišta: SAD, Brazil, UK i Singapur. Tržište Indija je izbačeno. Iako je Indija jeftina za ulazak (70k), ona nije bila nužna za zadovoljenje strateških ciljeva (Set Covering) jer su Singapur (za Aziju) i Brazil (za Rast) već pokrili te uvjete. Budući da Indija ima najniži ROI (2.5) i najniži bazni prihod, algoritam je procijenio da se ne isplati trošiti fiksne troškove ulaska na nju.
Financijska razina (Gdje je otišao novac?) Ovo je najzanimljiviji dio. Imali smo globalni budžet od 500k za marketing. Algoritam je slijedio veličinu ROI-a:
SAD (ROI 5.0): Dobio je maksimalnih 200k. (Najveći povrat).
UK (ROI 4.0): Dobio je maksimalnih 200k. (Drugi najveći povrat).
Singapur (ROI 3.5): Dobio je preostalih 100k.
Brazil (ROI 3.0): Dobio je 0 €.
Indija (ROI 2.5): Nije ni odabrana.
Iako smo ušli u Brazil (jer smo morali zbog uvjeta “Rasta”), algoritam tamo nije uložio ni eura u marketing jer je “potrošio” sav novac na profitabilnija tržišta (SAD, UK, Singapur). Ovo je realistična situacija gdje “Cash Cow” tržišta financiraju širenje na strateški bitna, ali manje profitabilna tržišta.
- Operativna razina (Infrastruktura) Na svim odabranim tržištima, broj servera je točno 2, a broj zaposlenika 1. Zašto minimum? U našoj funkciji cilja, serveri i ljudi su definirani isključivo kao trošak. Nismo postavili ograničenje koje kaže “ako uložiš 200k u marketing, moraš imati 10 servera”. Zbog toga je model, u težnji da maksimizira profit, srezao operativne troškove na zakonski minimum definiran ograničenjima.
Usko grlo ovog poslovanja nije infrastruktura (iskorišteno samo 8/30 servera), već marketinški budžet (iskorišteno 500/500). Da imamo više novca za marketing, profit bi rastao investiranjem u Singapur i Brazil.
Sigurno ste uočili da smo dobili različite rezultate ulaska u odnosu na prvotno razmatran problem (binarno programiranje). Promjena rezultata nije greška, već izravna posljedica promjene cilja (funkcije cilja).
Zašto se to dogodilo:
- Razlika u filozofiji modela
Model 1 (Set Covering): Minimizacija troška
Pitanje: “Koji je najjeftiniji način da zadovoljim uvjete?”
Logika: Model je gledao samo cijenu ulaska. SAD (150k) i Indija (70k) su zajedno koštali 220k. To je bila najjeftinija kombinacija koja pokriva sve kvačice. Profit, prihodi i ROI nisu postojali kao podatak. Indija je pobijedila jer je jeftina.
Model 2 (MILP): Maksimizacija profita
Pitanje: “Gdje mogu najviše zaraditi?”
Logika: Model sada gleda neto vrijednost (Prihod - Trošak). Više nije bitno samo koliko tržište košta, već koliko vraća natrag.
- Zašto su UK i Singapur odjednom “upali”?
U prvom modelu UK i Singapur su bili “preskupi” (90k i 110k) u odnosu na Indiju i Brazil. Ali u drugom modelu:
UK ima ROI od 4 i Bazni prihod od 250k. Iako košta 90k da se uđe, on generira ogroman profit. Model ga želi jer je to “tvornica novca”.
Singapur ima ROI od 3.5. Model ga želi jer se svaki uloženi euro višestruko vraća.
- Zašto je Indija “ispala”?
Ovo je najzanimljiviji dio. Pratite “domino efekt” odluka:
Model je zbog profita želio ući u Singapur (visok prihod, dobar ROI).
Jednom kad smo ušli u Singapur, uvjet “Azijska prisutnost” je zadovoljen!
Indija nam više ne treba za “Aziju”. Sada nam Indija treba samo za uvjet “Rast” (Growth).
Tu se natječe s Brazilom.
Indija: Bazni prihod 100, ROI 2.5.
Brazil: Bazni prihod 150, ROI 3.
Budući da Brazil donosi više novca od Indije, a Singapur već pokriva Aziju, model bira Brazil umjesto Indije kako bi zadovoljio uvjet “rasta”.
Sažetak vrsta varijabli u R-u (lpSolve)
Kada koristimo lpSolve paket u R-u, kontroliramo ove
tipove pomoću specifičnih argumenata:
- Standardni LP:
all.int = FALSE(zadano),all.bin = FALSE(zadano). - Cjelobrojno (IP):
all.int = TRUE. - Binarno (BIP):
all.bin = TRUE. - Mješovito (MILP): Koristimo argumente
int.vecilibinary.vecgdje navodimo točne indekse (redne brojeve) varijabli koje moraju biti cjelobrojne ili binarne, dok ostale ostaju kontinuirane.
Zadaci za samostalnu vježbu
Slučaj 1
Vi ste voditelj infrastrukture u Cloud kompaniji. Dobili ste budžet od 100000 € za hitno proširenje kapaciteta vašeg data centra kako biste podržali nove AI modele. Imate na raspolaganju samo 42 “U” (Rack Units) slobodnog prostora u serverskom ormaru i limitirano napajanje od 10000 W (Watta) na toj liniji.
Dobavljač nudi tri vrste servera. Vaš cilj je maksimizirati ukupnu procesorsku snagu (mjerenu u Benchmark bodovima) odabirom optimalne kombinacije servera.
Podaci o opremi:
| Tip Servera (\(x_i\)) | Cijena (€) | Visina (U) | Potrošnja (W) | Performanse (Bodovi) |
|---|---|---|---|---|
| Tip A (High-Density) | 5000 | 1 | 400 | 120 |
| Tip B (Standard) | 8000 | 2 | 600 | 200 |
| Tip C (GPU Monster) | 15000 | 4 | 1.200 | 550 |
Postavite model cjelobrojnog programiranja kako biste odredili koliko servera tipa A, B i C treba kupiti.
Slučaj 2
Pokrećete “zelenu” dostavnu službu u centru Zagreba. Morate formirati vozni park kupovinom električnih vozila. Imate početni kapital od 60000 €. Vaše skladište ima ograničen prostor za parkiranje/punjenje od 50 m². Također, imate na raspolaganju 4 mehaničara za održavanje, a svako vozilo zahtijeva određeni broj sati održavanja tjedno (ukupno imate 160 sati održavanja na raspolaganju).
Svaki tip vozila ima drugačiji kapacitet dostave (prosječan broj paketa koje može dostaviti dnevno).
Podaci o vozilima:
| Vozilo (\(x_i\)) | Cijena (€) | Potreban prostor (m²) | Održavanje (h/tjedno) | Kapacitet (paketa/dan) |
|---|---|---|---|---|
| E-Romobil | 800 | 1 | 2 | 20 |
| Cargo E-Bicikl | 2.500 | 3 | 5 | 50 |
| Mali E-Kombi | 12000 | 12 | 10 | 180 |
Odredite koliko kojih vozila kupiti kako biste maksimizirali ukupni dnevni kapacitet dostave (broj paketa), poštujući ograničenja budžeta, parkinga i radnih sati mehaničara.
Slučaj 3
Mala ste tvrtka koja proizvodi pametne IoT uređaje. Zbog globalne nestašice čipova, ne možete naručiti nove komponente, već morate iskoristiti zalihe koje imate u skladištu kako biste proizveli i prodali što više prije kraja kvartala.
Na skladištu imate:
- 200 mikrokontrolera (ESP32 čipova)
- 350 senzora temperature
- 150 Wi-Fi modula (pojačanih)
- 500 baterijskih jedinica
Proizvodite tri modela uređaja, a svaki se prodaje po različitoj cijeni (Profit):
Sastavnica proizvoda:
| Komponenta | Basic Model (\(x_1\)) | Pro Model (\(x_2\)) | Industrial Model (\(x_3\)) | Dostupno |
|---|---|---|---|---|
| Mikrokontroleri | 1 | 1 | 2 | 200 |
| Senzori | 1 | 2 | 4 | 350 |
| Wi-Fi moduli | 0 | 1 | 1 | 150 |
| Baterije | 2 | 2 | 4 | 500 |
| Profit po komadu (€) | 20 | 45 | 90 |
Odredite plan proizvodnje (koliko komada Basic, Pro i Industrial modela proizvesti) kako biste maksimizirali ukupni profit, a da pritom ne potrošite više komponenti nego što ih imate na zalihi.
Slučaj 4
Vi ste Product Manager koji planira sadržaj iduće velike verzije (v2.0) vaše mobilne aplikacije. Imate listu željenih funkcionalnosti (“Feature Requests”) koje su tražili korisnici. Svaka funkcionalnost ima procijenjenu vrijednost za korisnika (User Value Points) i procijenjeni trošak razvoja u satima (Dev Hours).
Vaš tim ima fiksni kapacitet od 300 radnih sati za ovaj ciklus. Cilj je odabrati skup funkcionalnosti koji maksimizira ukupnu vrijednost za korisnika.
Podaci o funkcionalnostima:
| ID | Funkcionalnost (\(x_i\)) | Vrijednost (Bodovi) | Trošak (Sati) |
|---|---|---|---|
| 1 | Dark mode | 40 | 20 |
| 2 | Video pozivi | 90 | 120 |
| 3 | AI Chatbot | 70 | 80 |
| 4 | Integracija s kalendarom | 30 | 40 |
| 5 | Napredna analitika | 50 | 60 |
| 6 | Offline mode | 60 | 50 |
Logička ograničenja:
- Ovisnost: Funkcionalnost Napredna Analitika (5) tehnički ovisi o Integraciji s Kalendarom (4) jer koristi njegove podatke. Ako odaberete Analitiku, morate odabrati i Kalendar. (\(x_5 \le x_4\))
- Konflikt: Vaš tim za UI ne može istovremeno raditi na Dark Modu (1) i Video Pozivima (2) jer oboje zahtijevaju potpunu promjenu dizajna sučelja. Možete odabrati najviše jedno od to dvoje. (\(x_1 + x_2 \le 1\))
Maksimizirajte vrijednost odabirom značajki uz poštivanje budžeta sati i logičkih uvjeta.
Slučaj 5
Vaša tvrtka pruža uslugu streaminga igara (Cloud Gaming) gdje je niska latencija presudna. Želite postaviti “Edge” servere u nekoliko strateških gradova kako biste pokrili što više korisnika s latencijom manjom od 20ms. Imate budžet za izgradnju točno 2 nova servera.
Identificirali ste 4 potencijalne lokacije za izgradnju servera. Svaka lokacija pokriva određeni skup regija (gradova).
Potencijalne lokacije i pokrivene regije:
| ID | Lokacija Servera (\(x_i\)) | Trošak izgradnje | Pokriva Regije (Korisnike) |
|---|---|---|---|
| 1 | Lokacija A (Sjever) | 1 jedinica | Regija 1 (50k), Regija 2 (30k) |
| 2 | Lokacija B (Centar) | 1 jedinica | Regija 2 (30k), Regija 3 (40k) |
| 3 | Lokacija C (Jug) | 1 jedinica | Regija 3 (40k), Regija 4 (60k) |
| 4 | Lokacija D (Zapad) | 1 jedinica | Regija 1 (50k), Regija 5 (20k) |
Napomena: Ako je regija pokrivena s više servera, broj korisnika se broji samo jednom (ne zbraja se dvaput).
Ovo je malo složeniji problem. Kako biste ga modelirali?
Trebaju vam binarne varijable za lokacije (\(x_i\)) i binarne varijable za pokrivene regije (\(y_j\)).
Cilj je maksimizirati sumu korisnika u pokrivenim regijama (\(\sum \text{Korisnici}_j \cdot y_j\)).
Ograničenje: Regija \(j\) je pokrivena (\(y_j=1\)) samo ako je izgrađen barem jedan server koji je “vidi”.
(Npr. za Regiju 2: \(y_2 \le x_1 + x_2\)).
Pronađite optimalne 2 lokacije.
Slučaj 6
Nakon spajanja dviju tvrtki, vaš IT odjel ima previše redundantnih softverskih licenci. Troškovi su preveliki i želite odabrati samo jedan alat za svaku kategoriju poslovanja kako biste standardizirali procese.
Imate tri kategorije alata:
- Komunikacija (Chat/Video)
- Pohrana (Cloud storage)
- Upravljanje projektima (Project management)
Dostupni paketi (vendor bundles):
Neki proizvođači nude pakete koji pokrivaju više kategorija, dok su drugi specijalizirani.
| ID | Alat/Paket (\(x_i\)) | Cijena (€/god) | Komunikacija? | Pohrana? | Projekti? |
|---|---|---|---|---|---|
| 1 | Vendor “Micro” (365) | 20000 | DA | DA | NE |
| 2 | Vendor “Goo” (Work) | 18000 | DA | DA | NE |
| 3 | Vendor “Slack” | 10000 | DA | NE | NE |
| 4 | Vendor “Box” | 8000 | NE | DA | NE |
| 5 | Vendor “Jira” | 12000 | NE | NE | DA |
| 6 | Vendor “Base” | 15000 | DA | NE | DA |
Minimizirajte ukupni trošak licenci uz sljedeća ograničenja:
- Pokrivenost: Svaka kategorija (Komunikacija, Pohrana, Projekti) mora biti pokrivena barem jednim alatom.
- Vendor Lock-in (Ovisnost): Ako odaberete Vendor “Jira” (\(x_5\)), menadžment inzistira da za komunikaciju morate koristiti Vendor “Slack” (\(x_3\)) jer imaju najbolju integraciju. (\(x_5 \le x_3\)).
- Isključivost (Single Ecosystem): Ne smijete odabrati i Vendor “Micro” (\(x_1\)) i Vendor “Goo” (\(x_2\)) jer bi to zbunilo korisnike (dva različita cloud diska). (\(x_1 + x_2 \le 1\)).
Slučaj 7
Vodite infrastrukturu za veliku web trgovinu. Promet (opterećenje) varira tijekom dana u tri smjene:
- Jutro (00-08h): Nisko opterećenje (potrebno 200 vCPU).
- Dan (08-16h): Visoko opterećenje (potrebno 500 vCPU).
- Večer (16-24h): Srednje opterećenje (potrebno 350 vCPU).
Imate dvije opcije za zakup računalne snage na AWS-u:
- Reserved Instances (RI): Kupuju se unaprijed na ugovor od 24 sata.
- Jedna instanca daje 10 vCPU.
- Cijena: 20 € / 24h (fiksno, bez obzira koristite li je ili ne).
- Ovo je cjelobrojna varijabla (kupujete cijele instance).
- On-Demand (Spot): Plaća se po satu, samo za ono što vam fali.
- Cijena: 0.15 € / vCPU / sat.
- Ovo je kontinuirana varijabla (možete zakazati točno onoliko snage koliko fali).
Odredite: 1. Broj Reserved instanci (\(R \in \mathbb{Z}\)) koje ćete kupiti za cijeli dan. 2. Količinu On-Demand vCPU-a (\(d_1, d_2, d_3 \in \mathbb{R}\)) koju ćete dokupiti za svaku smjenu.
Cilj je minimizirati ukupni dnevni trošak, uz uvjet da je potražnja u svakoj smjeni zadovoljena.
(Hint: Reserved instance su dostupne u svim smjenama. On-Demand plaćate posebno za svaku smjenu, pazeći na trajanje smjene od 8 sati).
Slučaj 8
Projektirate privatnu optičku mrežu koja povezuje Glavni Data Centar (Izvor) s tri regionalna ureda (Odredišta A, B, C). Svaki ured ima potražnju za podacima (Traffic Demand in Gbps):
- Ured A: 10 Gbps
- Ured B: 15 Gbps
- Ured C: 8 Gbps
Možete unajmiti optičke vodove (linkove) između određenih točaka. Svaki vod ima:
- Fiksni trošak instalacije: Plaća se jednokratno ako odlučite koristiti taj vod (Binarna odluka).
- Varijabilni trošak: Cijena po prenesenom Gbps (Kontinuirana varijabla).
- Maksimalni kapacitet: 20 Gbps po vodu.
Mogući vodovi:
- DC \(\to\) Ured A (Fiksno: 1000€, Var: 5€/Gbps)
- DC \(\to\) Ured B (Fiksno: 1200€, Var: 4€/Gbps)
- Ured A \(\to\) Ured B (Fiksno: 500€, Var: 2€/Gbps) - Poprečna veza
- Ured B \(\to\) Ured C (Fiksno: 600€, Var: 3€/Gbps) - Poprečna veza
- DC \(\to\) Ured C (Fiksno: 1500€, Var: 6€/Gbps)
Odlučite koje vodove aktivirati (\(x_{ij} \in \{0,1\}\)) i koliko prometa usmjeriti kroz njih (\(f_{ij} \ge 0\)) kako biste zadovoljili potražnju svih ureda uz minimalni trošak.
(Hint: Koristite Big M metodu za povezivanje toka i binarne odluke: \(f_{ij} \le M \cdot x_{ij}\), gdje je \(M\) kapacitet voda).
Slučaj 9
Vaš data centar napaja se iz tri izvora: Solarne elektrane, Javne mreže (Grid) i Diesel generatora. Trenutna potrošnja servera je 800 kW.
Morate odlučiti kako pokriti tu potrošnju u idućih sat vremena uz minimalni trošak, poštujući tehnička ograničenja generatora.
Izvori energije:
- Solarna energija: Besplatna, ali trenutno dostupno maksimalno 200 kW. (Sve što je dostupno možemo iskoristiti).
- Javna mreža (Grid):
- Cijena: 0.20 € / kWh.
- Limit: Trafostanica dopušta maksimalno 500 kW iz mreže.
- Ovo je kontinuirana varijabla.
- Diesel generator:
- Da bi se upalio, postoji fiksni trošak pokretanja i zagrijavanja od 50 € (Binarna odluka \(y \in \{0,1\}\)).
- Ako radi, troši gorivo po cijeni od 0.35 € / kWh (Kontinuirana varijabla \(g\)).
- Tehničko ograničenje (Semi-continuous): Ako je generator upaljen, ne smije raditi ispod 30% kapaciteta radi zdravlja motora, niti iznad 100%.
- Kapacitet generatora: 1000 kW (Dakle, ako radi, mora proizvoditi između 300 kW i 1000 kW).
Trebate li upaliti generator? Koliko struje povući iz mreže, a koliko iz generatora?
(Hint: Ovdje imate dva ograničenja za generator povezana s binarnom varijablom \(y\): \(g \ge 300 \cdot y\) i \(g \le 1000 \cdot y\)).
Korištena literatura
Anderson, D. R., Sweeney, D. J., Williams, T. A., Camm, J. D., & Cochran, J. J. (2012). Quantitative Methods for Business. Cengage Learning.
Askari-Nasab, H., Pourrahimian, Y., Ben-Awuah, E., & Kalantari, S. (2011). Mixed integer linear programming formulations for open pit production scheduling. Journal of Mining Science, 47(3), 338-359.
Balas, E., & Padberg, M. W. (1972). On the set-covering problem. Operations Research, 20(6), 1152-1161.
Benati, S., & Rizzi, R. (2007). A mixed integer linear programming formulation of the optimal mean/value-at-risk portfolio problem. European Journal of Operational Research, 176(1), 423-434.
Bertolazzi, P., Felici, G., Festa, P., Fiscon, G., & Weitschek, E. (2016). Integer programming models for feature selection: New extensions and a randomized solution algorithm. European Journal of Operational Research, 250(2), 389-399.
Bertsimas, D., & Weismantel, R. (2005). Optimization over Integers. Athena Scientific.
Conforti, M., Cornuéjols, G., & Zambelli, G. (2014). Integer Programming. Springer. https://link.springer.com/book/10.1007/978-3-319-11008-0
da Silva, C. G., Figueira, J., Lisboa, J., & Barman, S. (2006). An interactive decision support system for an aggregate production planning model based on multiple criteria mixed integer linear programming. Omega, 34(2), 167-177.
Dantzig, G. B. (2016). Linear programming and extensions. https://www.rand.org/content/dam/rand/pubs/reports/2007/R366part1.pdf
Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations research, 9(6), 849-859. https://www.researchgate.net/publication/266478800_A_Linear_Programming_Approach_to_the_Cutting_Stock_Problem_I
Gomory, R. E. (2009). Outline of an algorithm for integer solutions to linear programs and an algorithm for the mixed integer problem. In 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art (pp. 77-103). Berlin, Heidelberg: Springer Berlin Heidelberg.
Khalil, S., & Modibbo, U. M. (2021, March). Multiobjective optimization for hospital nurses scheduling problem using binary goal programming. In Virtual International Conference on Soft Computing, Optimization Theory and Applications (pp. 255-270). Singapore: Springer Nature Singapore.
Martin, C. H. (2004). Ohio university’s college of business uses integer programming to schedule classes. Interfaces, 34(6), 460-465.
Mashayekh, S., Stadler, M., Cardoso, G., & Heleno, M. (2017). A mixed integer linear programming approach for optimal DER portfolio, sizing, and placement in multi-energy microgrids. Applied Energy, 187, 154-168.
Mikolajková, M., Saxén, H., & Pettersson, F. (2018). Mixed integer linear programming optimization of gas supply to a local market. Industrial & Engineering Chemistry Research, 57(17), 5951-5965.
Nemhauser, G. L., & Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley. https://onlinelibrary.wiley.com/doi/book/10.1002/9781118627372
Pant, K., Singh, A. R., Pandey, U., & Purohit, R. (2018). A multi echelon mixed integer linear programming model of a close loop supply chain network design. Materials today: proceedings, 5(2), 4838-4846.
Ryan, D. M., & Foster, B. A. (1981). An integer programming approach to scheduling. Computer scheduling of public transport urban passenger vehicle and crew scheduling, 269-280.
Sangaiah, A. K., Tirkolaee, E. B., Goli, A., & Dehnavi-Arani, S. (2020). Robust optimization and mixed-integer linear programming model for LNG supply chain planning problem. Soft computing, 24(11), 7885-7905.
Schrijver, A. (1986). Theory of Linear and Integer Programming. John Wiley & Sons. promathmedia.wordpress.com/wp-content/uploads/2013/10/alexander_schrijver_theory_of_linear_and_integerbookfi-org.pdf
Talebi, A., Haeri Boroujeni, S. P., & Razi, A. (2025). Integrating random regret minimization-based discrete choice models with mixed integer linear programming for revenue optimization. Iran Journal of Computer Science, 8(1), 21-35.
Wan, Y., Wang, M., Ye, Z., & Lai, X. (2016). A feature selection method based on modified binary coded ant colony optimization algorithm. Applied Soft Computing, 49, 248-258.
Wilken, K., Liu, J., & Heffernan, M. (2000). Optimal instruction scheduling using integer programming. Acm sigplan notices, 35(5), 121-133.
Wolsey, L. A. (1998). Integer Programming. Wiley.
Wong, J. K. L., Mason, A. J., Neve, M. J., & Sowerby, K. W. (2006). Base station placement in indoor wireless systems using binary integer programming. IEE Proceedings-Communications, 153(5), 771-778.
Ključ odgovora
- b (Fizička nedjeljivost resursa)
- c (Rizik nedopustivosti rješenja - prekršaj ograničenja)
- c (Nenegativni cijeli brojevi)
- b (Problem pakiranja/Bin packing - diskretni entiteti)
- b (Prostor rješenja nije konveksan, već diskretna rešetka)
- b (Suma mora biti 0 ili 1, ali ne 2)
- c (Ako je A=1, B mora biti 1. Ako je A=0, B može biti bilo što)
- b (Definicija Set Covering ograničenja)
- a (Fiksni trošak se množi s binarnom varijablom)
- c (Točno k-od-n je suma jednakosti)
- a (Big M metoda: povezivanje binarne i kontinuirane varijable)
- b (Numerička stabilnost i brzina konvergencije)
- c (Semi-continuous varijabla: mora biti 0 ili u intervalu [L, M])
- d (Sadrži i cjelobrojne, i kontinuirane, i binarne varijable)
- b (Fiksni trošak vezan uz binarnu odluku + varijabilni trošak vezan uz količinu)