Primjeri riješenih zadataka - Operacijska istraživanja

Tvrtka želi nabaviti nove računalne uređaje za svojih 100 zaposlenika. Postoje dvije opcije: osobna računala i laptopi. Cijena osobnog računala je 1600 eura, dok je cijena laptopa 2000 eura. Ukupan budžet za nabavu je 180,000 eura.

Od 100 zaposlenika:

30% inzistira na korištenju osobnog računala.
Najmanje 25% i najviše 50% preferira laptope.
Ostali zaposlenici se nisu izjasnili o svojim preferencijama.

Koliko računala i laptopa tvrtka treba kupiti za svoje zaposlenike uz budžet koji ima na raspolaganju i poštivanje preferencija zaposlenika?

Struktura problema:

Varijable odluke

x: Broj osobnih računala koje tvrtka planira kupiti.

y: Broj laptopa koje tvrtka planira kupiti.

Funkcija cilja:

$min (2000x + 1600y)$

Ograničenja:

Ograničenje budžeta: $2000x + 1600y \le 180,000$

Ograničenje za osobna računala (30% od 100 zaposlenika = 30 zaposlenika): $x \le 30$

Ograničenje za laptope (25% od 100 zaposlenika = 25 zaposlenika, 50% od 100 zaposlenika = 50 zaposlenika): $25 \leq y \leq 50$ Ukupan broj uređaja: $x + y = 100$

U ovom slučaju koristi se paket lpSolveAPI (Konis, Schwendinger, and Hornik 2023).

if(!require(lpSolveAPI)) install.packages("lpSolveAPI")

## Loading required package: lpSolveAPI

library(lpSolveAPI)

# Inicijalizacija modela
model <- make.lp(0, 2)

# Postavljanje funkcije cilja
set.objfn(model, c(2000, 1600))

# Dodavanje ograničenja
add.constraint(model, c(2000, 1600), "<=", 180000)
add.constraint(model, c(1, 0), ">=", 30)
add.constraint(model, c(0, 1), ">=", 25)
add.constraint(model, c(0, 1), "<=", 50)
add.constraint(model, c(1, 1), "=", 100)

# Postavljanje naziva varijabli
colnam <- c("x", "y")
rownam <- c("Ograničenje budžeta", "Ograničenje za osobna računala", "Ograničenje za laptope (donja granica)", 
         "Ograničenje za laptope (gornja granica)", "Ukupan broj uređaja")
dimnames(model) <- list(rownam, colnam)

lp.control(model, sense="min")

## $anti.degen
## [1] "fixedvars" "stalling" 
## 
## $basis.crash
## [1] "none"
## 
## $bb.depthlimit
## [1] -50
## 
## $bb.floorfirst
## [1] "automatic"
## 
## $bb.rule
## [1] "pseudononint" "greedy"       "dynamic"      "rcostfixing" 
## 
## $break.at.first
## [1] FALSE
## 
## $break.at.value
## [1] -1e+30
## 
## $epsilon
##       epsb       epsd      epsel     epsint epsperturb   epspivot 
##      1e-10      1e-09      1e-12      1e-07      1e-05      2e-07 
## 
## $improve
## [1] "dualfeas" "thetagap"
## 
## $infinite
## [1] 1e+30
## 
## $maxpivot
## [1] 250
## 
## $mip.gap
## absolute relative 
##    1e-11    1e-11 
## 
## $negrange
## [1] -1e+06
## 
## $obj.in.basis
## [1] TRUE
## 
## $pivoting
## [1] "devex"    "adaptive"
## 
## $presolve
## [1] "none"
## 
## $scalelimit
## [1] 5
## 
## $scaling
## [1] "geometric"   "equilibrate" "integers"   
## 
## $sense
## [1] "minimize"
## 
## $simplextype
## [1] "dual"   "primal"
## 
## $timeout
## [1] 0
## 
## $verbose
## [1] "neutral"

solve(model)

## [1] 0

# Ispis optimalnog rješenja
cat("Optimalno rješenje:\n")

## Optimalno rješenje:

cat("Broj osobnih računala (x):", get.variables(model)[1], "\n")

## Broj osobnih računala (x): 50

cat("Broj laptopa (y):", get.variables(model)[2], "\n")

## Broj laptopa (y): 50

cat("Ukupni trošak:", get.objective(model), "eura\n")

## Ukupni trošak: 180000 eura

U skladu s optimalnim rješenjem, tvrtka bi trebala nabaviti točno 50 osobnih računala i 50 laptopa za svoje zaposlenike kako bi zadovoljila sve postavljene zahtjeve i ograničenja te istovremeno minimizirala ukupne troškove. Kroz ovu optimizaciju, ukupni trošak za tvrtku iznosi 180,000 eura. Korištenje linearnog programiranja omogućilo je tvrtki da zadovolji potrebe svojih zaposlenika za novim računalima uz minimalne troškove, dok je istovremeno uzela u obzir sve postavljene zahtjeve i ograničenja.

S obzirom da je u pitanju problem sa samo dvije varijable, moguća je vizualizacija, odnosno grafički prikaz.

#Grafički prikaz površine dopustivih rješenja
# Postavke grafa
plot(0, 0, xlim=c(0, 100), ylim=c(0, 100), type="n", 
    xlab="Broj osobnih računala (x)", ylab="Broj laptopa (y)", main="Prostor dopustivih rješenja")
polygon(c(30, 30, 50, 70), c(25, 50, 50, 25), col=rgb(0.8,0.8,0.8), border=NA)
budget <- function(x) (180000 - 2000*x) / 1600
curve(budget, from=0, to=100, col="blue", lty=2, add=TRUE)
abline(v=30, col="orange", lty=2)
abline(h=25, col="green", lty=2)
abline(h=50, col="green", lty=2)
sum100 <- function(x) 100 - x
curve(sum100, from=0, to=100, col="purple", lty=2, add=TRUE)
optimal_cost = 2000*get.variables(model)[1] + 1600*get.variables(model)[2]
goal <- function(x) (optimal_cost - 2000*x) / 1600
curve(goal, from=0, to=100, add=TRUE, col="red", lty=3, lwd=2)
points(get.variables(model)[1], get.variables(model)[2], pch=19, col="red")

Slučaj: Proizvodnja super-legura

Problem alokacije resursa

Tvrtka “MetalMix” želi kreirati super-leguru kombinirajući pet različitih metala: Bakar (Cu), Cink (Zn), Nikl (Ni), Krom (Cr) i Mangan (Mn). Super-legura je metalna legura koja se ističe izvanrednim mehaničkim svojstvima, posebno na visokim temperaturama. Super-legure se često koriste u zrakoplovstvu, nuklearnim reaktorima i industrijskim turbinama zbog svoje izdržljivosti na visokim temperaturama, korozivnoj otpornosti i visokoj čvrstoći. Cijene i dostupnost ovih metala su sljedeće:

Bakar košta 6$/kg i dostupan je u količini od 500 kg.
Cink je cijenjen na 5$/kg s dostupnošću od 600 kg.
Nikal stoji 10$/kg s raspoloživom količinom od 300 kg.
Krom košta 8$/kg s dostupnih 400 kg.
Mangan ima cijenu od 7$/kg i dostupan je u količini od 250 kg.

Super-legure su važne zbog svojih izvanrednih mehaničkih svojstava, osobito na visokim temperaturama, te se često koriste u različitim industrijskim aplikacijama.

“MetalMix” će prodavati super-leguru po cijeni od $20 po kg. Da bi super-legura bila kvalitetna, mora udovoljavati sljedećim specifikacijama:

Bakra mora biti barem 25% od ukupne mase.
Cinka ne smije biti više od 30% ukupne mase.
Nikla mora biti najmanje 10% i najviše 20% ukupne mase.
Kroma i Mangana zajedno ne smije biti više od 25% ukupne mase.

Koliko super-legure i u kojoj kombinaciji sastojaka MetalMix treba proizvesti uz dana ograničenja, kako bi maksimizirao svoj profit?

Struktura problema

Neka su varijable odluke:

$x_1$ = masa Bakra (Cu) u kg

$x_2$ = masa Cinka (Zn) u kg

$x_3$ = masa Nikla (Ni) u kg

$x_4$ = masa Kroma (Cr) u kg

$x_5$ = masa Mangana (Mn) u kg

Funkcija cilja:

$max(20(x_1+x_2+x_3+x_4+x_5 )-6x_1-5x_2-10x_3-8x_4-7x_5)$

Ograničenja:

$x_1 ≥ 0.25(x_1+ x_2+ x_3+ x_4+ x_5 )$

$x_2 ≤ 0.30(x_1+ x_2+ x_3+ x_4+ x_5 )$

$x_3 ≥ 0.10(x_1+ x_2+ x_3+ x_4+ x_5 )$

$x_3 ≤ 0.20(x_1+ x_2+ x_3+ x_4+ x_5 )$

$x_4 + x_5 ≤ 0.25(x_1+ x_2+ x_3+ x_4+ x_5 )$

$x_1 ≤ 500$

$x_2 ≤ 600$

$x_3 ≤ 300$

$x_4 ≤ 400$

$x_5 ≤ 250$

$x_1,…,x_5 ≥ 0$

Ograničenja treba prilagoditi kako bi se mogli kreirati matrica A i vektor b.

Za prvo ograničenje vrijedi:

$x_1 - 0.25(x_1+ x_2+ x_3+ x_4+ x_5 ) ≥ 0$

pa je to:

$0.75x-1 -0.25x_2-0.25x_3-0.25x_4-0.25x_5$

Stoga će koeficijenti zapisani u prvi redak matrice A glasiti:

$0.75, -0,25, -0,25, -0,25, -0,25$.

Na isti način potrebno je prilagoditi sljedeća četiri ograničenja, kod kojih se u trenutnom zapisu varijable odluke pojavljuju s desne strane nejednadžbe.

Sad ćemo koristiti paket lpSolve (Berkelaar and al 2023).

if(!require(lpSolve)) install.packages("lpSolve")

## Loading required package: lpSolve

library(lpSolve)

# Ciljna funkcija
f.obj <- c(14,15,10,12,13)

# Matrica ograničenja
f.con <- matrix(c(0.75, -0.25, -0.25, -0.25, -0.25,
              -0.3, 0.7, -0.3, -0.3, -0.3,
              -0.1, -0.1, 0.9, -0.1, -0.1,
              -0.2, -0.2, 0.8, -0.2, -0.2,
              -0.25, -0.25, -0.25, 0.75, 0.75,
              1, 0, 0, 0, 0,
              0, 1, 0, 0, 0,
              0, 0, 1, 0, 0, 
              0, 0, 0, 1, 0,
              0, 0, 0, 0, 1),
            nrow = 10, byrow = TRUE)

# Vektor slobodnih članova
f.dir <- c(">=", "<=", ">=", "<=", "<=", "<=", "<=", "<=", "<=", "<=")

f.rhs <- c(0,0,0,0,0, 500, 600, 300, 400, 250)

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

# Ispis rješenja
print(solution)

## Success: the objective function is 23583.33

solution$solution

## [1] 500.0000 533.3333 300.0000 194.4444 250.0000

solution$duals

##  [1]  0.00000 31.66667  0.00000  0.00000 28.66667 30.66667  0.00000 26.66667
##  [9]  0.00000  1.00000  0.00000  0.00000  0.00000  0.00000  0.00000

Iz dobivenog rješenja, optimalna količina svakog metala koju “MetalMix” treba koristiti u super-leguri je sljedeća: - Bakar (Cu): 500 kg - Cink (Zn): 533.33 kg - Nikl (Ni): 300 kg - Krom (Cr): 194.44 kg - Mangan (Mn): 250 kg

To znači da će tvrtka koristiti svu dostupnu količinu bakra, nikla i mangana kako bi proizvela optimalnu količinu legure. Cink i krom će biti iskorišteni ispod maksimalno dostupne količine kako bi udovoljili postavljenim specifikacijama.

Uzevši u obzir cijene metala i cijenu po kojoj će super-legura biti prodavana, funkcija cilja (maksimalni profit) je 23,583.33 dolara. To znači da “MetalMix”, koristeći optimalnu kombinaciju metala, može ostvariti profit od 23,583.33 dolara.

Dualne vrijednosti pružaju informacije o tome koliko bi se profit promijenio kad bi se promijenilo neko od ograničenja. Na primjer, dualna vrijednost za cink je 31.67 dlara, što sugerira da bi profit mogao porasti za 31.67 dolara za svaku jedinicu povećanja u ograničenju cinka, pod uvjetom da ostala ograničenja ostanu ista. Naravno, to ima smisla koristiti samo ako je trošak nabavke cinka manji od 31.67 dolara. Vrijednost od $28.67 za mangan sugerira da bi dodatni kilogram mangana mogao povećati profit za taj iznos, na sličan način kao kod cinka.

Nadalje, dualna vrijednost od $30.66 za krom ukazuje na sličan potencijalni porast profita za svaku dodatnu jedinicu dostupnog kroma.

Ostale dualne vrijednosti koje su jednake nuli ukazuju na to da promjena tih specifičnih ograničenja ne bi imala izravan utjecaj na maksimalni profit. S obzirom na to da se radi o resursima koji nisu u potpunosti utrošeni, dodatna nabavka tih resursa može samo rezultirati većim zalihama (koje također nose trošak, iako nije uzet u obzir u ovom primjeru).

Stoga, dualne vrijednosti pružaju ključne informacije o osjetljivosti rješenja na promjene u ograničenjima i mogu pomoći tvrtki da donese strateške odluke o nabavi dodatnih resursa ili prilagodbi proizvodnog procesa.

Slučaj: Proizvodnja PVC stolarije

Problem alokacije resursa

PVC stolarija postala je iznimno popularna zbog svoje energetske učinkovitosti, dugovječnosti i otpornosti na različite vremenske uvjete. Tvrtke koje se bave proizvodnjom PVC stolarije često se suočavaju s izazovima optimizacije proizvodnje kako bi maksimizirale dobit uz postojeće resurse i ograničenja. “Svjetli gradovi” je jedna od takvih tvrtki koja teži najboljem iskorištavanju svojih resursa. Tvrtka “Svjetli gradovi” proizvodi pet različitih vrsta PVC stolarije: prozore, vrata, klizne stijenke, balkonska vrata i krovne prozore. Donji su podaci vezani uz svaki proizvod i odnose se na mjesečnu razinu, redom:

Proizvod:Prozori, Vrata, Klizne stijenke, Balkonska vrata, Krovni prozori,
Cijena prodaje ($/jedinica): 100, 150, 200, 250, 300
Trošak proizvodnje ($/jedinica):5, 80, 120, 150, 200
Vrijeme proizvodnje (h/jedinica): 2, 3, 4, 5, 6
Potreban Materijal (kg): 5, 6, 8, 10, 12
Maksimalna proizvodnja: 300, 200, 150, 100, 50

Tvrtka “PVC Pro” tjedno raspolaže s 4000 radnih sati, ima na raspolaganju 5000 kg PVC materijala i može skladištiti do 1000 jedinica proizvoda. Kolika količina kojeg proizvoda treba biti proizvedena kako bi se maksimizirala dobit?

Proizvod <- c("Prozori", "Vrata", "Klizne stijenke", "Balkonska vrata", "Krovni prozori") 
Cijena_prodaje <- c(100, 150, 200, 250, 300)
Trosak_proizvodnje <- c(5, 80, 120, 150, 200)
Vrijeme_proizvodnje <-  c(2, 3, 4, 5, 6)
Potreban_materijal <- c(5, 6, 8, 10, 12)
Maksimalna_proizvodnja <- c(300, 200, 150, 100, 50)
Podaci <- cbind(Proizvod, Cijena_prodaje, Trosak_proizvodnje, Vrijeme_proizvodnje, Potreban_materijal, Maksimalna_proizvodnja)
Podaci <- as.table(Podaci)
Podaci

##   Proizvod        Cijena_prodaje Trosak_proizvodnje Vrijeme_proizvodnje
## A Prozori         100            5                  2                  
## B Vrata           150            80                 3                  
## C Klizne stijenke 200            120                4                  
## D Balkonska vrata 250            150                5                  
## E Krovni prozori  300            200                6                  
##   Potreban_materijal Maksimalna_proizvodnja
## A 5                  300                   
## B 6                  200                   
## C 8                  150                   
## D 10                 100                   
## E 12                 50

Nakon preglednijeg zapisa podataka, sastavljamo strukturu problema.

Struktura problema

Neka su varijable odluke:

$x_1$= broj proizvedenih prozora

$x_2$= broj proizvedenih vrata

$x_3$= broj proizvedenih kliznih stijenki

$x_4$= broj proizvedenih balkonskih vrata

$x_5$= broj proizvedenih krovnih prozora

Funkcija cilja:

$max (95x_1+ 70x_2+ 80x_3+ 100x_4+ 100x_5)$

Ograničenja:

$2x_1+ 3x_2+ 4x_3+ 5x_4+ 6x_5≤ 4000$ (Vremensko ograničenje)

$x_1+ x_2+ x_3+ x_4+ x_5≤ 1000$ (Skladišno ograničenje)

$5x_1+ 6x_2+ 8x_3+ 10x_4+ 12x_5≤ 5000$ (Ograničenje PVC materijala)

$x_1≤ 300$ (Maksimalna proizvodnja prozora)

$x_2≤ 200$ (Maksimalna proizvodnja vrata)

$x_3≤ 150$ (Maksimalna proizvodnja kliznih stijenki)

$x_4≤ 100$ (Maksimalna proizvodnja balkonskih vrata)

$x_5≤ 50$ (Maksimalna proizvodnja krovnih prozora)

$x_1,x_2,x_3,x_4,x_5≥ 0$

if(!require(lpSolveAPI)) install.packages("lpSolveAPI")
library(lpSolveAPI)

# Kreiranje novog linearnog programa s 5 varijabli (x1, x2, x3, x4, x5)
model <- make.lp(0, 5)

# Postavljanje funkcije cilja
set.objfn(model, c(95, 70, 80, 100, 100))

# Postavite smjer optimizacije na maksimizaciju
#set.direction(model, "max")

# Dodavanje ograničenja

add.constraint(model, c(2, 3, 4, 5, 6), "<=", 4000)
add.constraint(model, c(1, 1, 1, 1, 1), "<=", 1000)
add.constraint(model, c(5, 6, 8, 10, 12), "<=", 5000)
add.constraint(model, c(1, 0, 0, 0, 0), "<=", 300) 
add.constraint(model, c(0, 1, 0, 0, 0), "<=", 200)
add.constraint(model, c(0, 0, 1, 0, 0), "<=", 150)
add.constraint(model, c(0, 0, 0, 1, 0), "<=", 100)
add.constraint(model, c(0, 0, 0, 0, 1), "<=", 50)

# Postavljanje imena varijabli
rownames <- c("Vremensko ograničenje", "Skladišno ograničenje", "Ograničenje PVC materijala", "Maksimalna proizvodnja prozora", "Maksimalna proizvodnja vrata", "Maksimalna proizvodnja kliznih stijenki", "Maksimalna proizvodnja balkonskih vrata", "Maksimalna proizvodnja krovnih prozora")
colnames <- c("Prozori", "Vrata", "Klizne stijenke", "Balkonska vrata", "Krovni prozori")
dimnames(model) <- list(rownames, colnames)


lp.control(model, sense="max", simplextype =c("primal", "dual"))

## $anti.degen
## [1] "fixedvars" "stalling" 
## 
## $basis.crash
## [1] "none"
## 
## $bb.depthlimit
## [1] -50
## 
## $bb.floorfirst
## [1] "automatic"
## 
## $bb.rule
## [1] "pseudononint" "greedy"       "dynamic"      "rcostfixing" 
## 
## $break.at.first
## [1] FALSE
## 
## $break.at.value
## [1] 1e+30
## 
## $epsilon
##       epsb       epsd      epsel     epsint epsperturb   epspivot 
##      1e-10      1e-09      1e-12      1e-07      1e-05      2e-07 
## 
## $improve
## [1] "dualfeas" "thetagap"
## 
## $infinite
## [1] 1e+30
## 
## $maxpivot
## [1] 250
## 
## $mip.gap
## absolute relative 
##    1e-11    1e-11 
## 
## $negrange
## [1] -1e+06
## 
## $obj.in.basis
## [1] TRUE
## 
## $pivoting
## [1] "devex"    "adaptive"
## 
## $presolve
## [1] "none"
## 
## $scalelimit
## [1] 5
## 
## $scaling
## [1] "geometric"   "equilibrate" "integers"   
## 
## $sense
## [1] "maximize"
## 
## $simplextype
## [1] "primal" "dual"  
## 
## $timeout
## [1] 0
## 
## $verbose
## [1] "neutral"

model

## Model name: 
##                                                  Prozori            Vrata  Klizne stijenke  Balkonska vrata   Krovni prozori          
## Maximize                                              95               70               80              100              100          
## Vremensko ograničenje                                  2                3                4                5                6  <=  4000
## Skladišno ograničenje                                  1                1                1                1                1  <=  1000
## Ograničenje PVC materijala                             5                6                8               10               12  <=  5000
## Maksimalna proizvodnja prozora                         1                0                0                0                0  <=   300
## Maksimalna proizvodnja vrata                           0                1                0                0                0  <=   200
## Maksimalna proizvodnja kliznih stijenki                0                0                1                0                0  <=   150
## Maksimalna proizvodnja balkonskih vrata                0                0                0                1                0  <=   100
## Maksimalna proizvodnja krovnih prozora                 0                0                0                0                1  <=    50
## Kind                                                 Std              Std              Std              Std              Std          
## Type                                                Real             Real             Real             Real             Real          
## Upper                                                Inf              Inf              Inf              Inf              Inf          
## Lower                                                  0                0                0                0                0

# Rješavanje modela
solution <- solve(model)
solution

## [1] 0

# Prikaz rješenja
cat("Vrijednost funkcije cilja (maksimalna dobit):", get.objective(model), "\n")

## Vrijednost funkcije cilja (maksimalna dobit): 65333.33

cat("Optimalna proizvodnja za svaki proizvod:\n")

## Optimalna proizvodnja za svaki proizvod:

get.variables(model)

## [1] 300.000000 200.000000 150.000000 100.000000   8.333333

Da bi se maksimizirala dobit, tvrtka treba proizvesti 300 prozora, 200 vrata, 150 kliznih stijenki, 100 balkonskih vrata i otprilike 8 krovnih prozora mjesečno. Uz ovu optimalnu strategiju proizvodnje, “Svjetli gradovi” će postići maksimalnu dobit od 65,333.33 dolara. Ovaj iznos predstavlja razliku između prodajne cijene i troška proizvodnje za svaku jedinicu svakog proizvoda, pomnoženu s optimalnom količinom proizvedenih jedinica. S obzirom da se radi o mjesečnoj proizvodnji, rješenje od 8.33 krovnih prozora nije problematično, jer podrazumijeva da će proizvodnja 9. krovnog prozora započeti u jednom mjesecu i nastaviti se u sljedećem.

U nastavku ćemo se pozabaviti funkcijom cilja i prikazom rezultata.

# Dohvati osjetljivost dualnih vrijednosti
duals <- get.dual.solution(model)

# Dohvati osjetljivost cijena sjenki
shadows <- get.sensitivity.rhs(model)

options(scipen = 23.5)


# Kreirajte data frame za osjetljivost ograničenja
sensitivity_constraints <- data.frame(
  Constraint = c("Vremensko ograničenje", "Skladišno ograničenje", "Ograničenje PVC materijala", "Maksimalna proizvodnja prozora", "Maksimalna proizvodnja vrata", "Maksimalna proizvodnja kliznih stijenki", "Maksimalna proizvodnja balkonskih vrata", "Maksimalna proizvodnja krovnih prozora"),
  ShadowPrice = formatC(shadows[[1]][c(1:8)], format = "f", digits = 3),
  Lower_bound = formatC(shadows[[2]][c(1:8)], format = "f", digits = 3),
  Upper_bound = formatC(shadows[[3]][c(1:8)], format = "f", digits = 3)
)


# Dohvati osjetljivost objektivne funkcije
obj_sensitivity <- get.sensitivity.obj(model)

# Kreirajte data frame za osjetljivost koeficijenata ciljne funkcije
sensitivity_obj <- data.frame(
  Variable = c("Prozori", "Vrata", "Klizne stijenke", "Balkonska vrata", "Krovni prozori"), 
  ObjectiveCoef = formatC(get.variables(model), format = "f", digits = 3),
  LowerLimit = formatC(obj_sensitivity[[1]], format = "f", digits = 3),
  UpperLimit = formatC(obj_sensitivity[[2]], format = "f", digits = 3)
)


#install.packages("knitr")
library(knitr)

kable(sensitivity_constraints, caption = "Osjetljivost ograničenja")

Osjetljivost ograničenja
Constraint	ShadowPrice	Lower_bound	Upper_bound
Vremensko ograničenje	0.000	-1000000000000000019924668064446.000	1000000000000000019924668064446.000
Skladišno ograničenje	0.000	-1000000000000000019924668064446.000	1000000000000000019924668064446.000
Ograničenje PVC materijala	8.333	4900.000	5500.000
Maksimalna proizvodnja prozora	53.333	200.000	320.000
Maksimalna proizvodnja vrata	20.000	116.667	216.667
Maksimalna proizvodnja kliznih stijenki	13.333	87.500	162.500
Maksimalna proizvodnja balkonskih vrata	16.667	50.000	110.000
Maksimalna proizvodnja krovnih prozora	0.000	-1000000000000000019924668064446.000	1000000000000000019924668064446.000

kable(sensitivity_obj, caption = "Osjetljivost koeficijenata funkcije cilja")

Osjetljivost koeficijenata funkcije cilja
Variable	ObjectiveCoef	LowerLimit	UpperLimit
Prozori	300.000	41.667	1000000000000000019924668064446.000
Vrata	200.000	50.000	1000000000000000019924668064446.000
Klizne stijenke	150.000	66.667	1000000000000000019924668064446.000
Balkonska vrata	100.000	83.333	1000000000000000019924668064446.000
Krovni prozori	8.333	0.000	120.000

on.exit(options(scipen = 0))

Uz prozore je koeficijent u funkciji cilja 300, uz dopušteno smanjenje na 41.67 i neograničeno povećanje. Na sličan način se iščitavaju i ostale vrijednosti u drugoj tablici.

U prvoj tablici prikazane su sjene cijena te dopuštene donje i gornje granice desnih strana ograničenja. Na primjer, maksimalna proizvodnja prozora ima sjenu cijena 53.33. To znači da bi se funkcija cilja povećala za 53.33 za jedinično povećanje tog resursa. To ima smisla koristiti samo ukoliko je povezani trošak promjene tog ograničenja manji od 53.33. Granice ograničenja u kojima ta sjena cijena vrijedi je od 200 do 320 komada.

Ogranicenje PVC materijala ima sjenu cijena 8.333, što znači da bi se za dodatni kilogram dostupnog materijala funkcija cilja povećala za 8.333. Ukoliko je moguće nabaviti dodatne količine tog materijala za trošak manji od 8.33, tada se to isplati napraviti. Ipak, treba imati na umu da to pokriva 500 kg materijala (do gornje granice od 5500 kg). Nakon toga, treba kreirati novi model i utvrditi parametre.

Ovo rješenje pruža “Svjetlim gradovima” jasan plan kako najbolje rasporediti resurse s ciljem maksimizacije dobiti. Sa znanjem o ovim optimalnim količinama, tvrtka može bolje planirati svoje operativne aktivnosti, od alokacije radnih sati do nabave materijala. Osim toga, razumijevanje dualnih vrijednosti omogućuje im da prepoznaju ključna ograničenja koja imaju najveći utjecaj na njihovu dobit i prilagode svoje strategije sukladno tome.

Slučaj: Izbor medija za oglašavanje

Problem alokacije resursa

Zamislite da radite za agenciju Theatre of joy d.o.o.Upravo Vam se javio novi klijent, poduzeće AZBC kojem je potreban savjet o odabiru i alokaciji sredstava za promociju putem medija pri dizajnu promotivne kampanje. U Agenciji promocija već ste prikupili sljedeće podatke: doseg potencijalnih klijenata (broj klijenata koji će vidjeti oglas), trošak po oglasu, maksimalni broj puta angažmana medija (dostupnost medija) te rejting kvalitete izloženosti za 5 medija.

Dostupni oglašivači prema dosegu, trošku, mogućem broju oglasa i kvaliteti izloženosti su sljedeći:

Dnevna TV postaja Pula, DTV za 1 minutu ima doseg od 1000 klijenata, trošak od 1500€, mogućnost 15 oglasa i kvalitetu izloženosti od 65.
Večernja TV postaja Pula, VTV za 30 sekundi ima doseg od 2000 klijenata, trošak od 3000€, mogućnost 10 oglasa i kvalitetu izloženosti od 90.
Dnevne novine Glas Pule, DNGP s cijelom stranicom imaju doseg od 1500 klijenata, trošak od 400€, mogućnost 25 oglasa i kvalitetu izloženosti od 40.
Nedjeljni magazin s pola stranice u boji ima doseg od 2500 klijenata, trošak od 1000€, mogućnost 4 oglasa i kvalitetu izloženosti od 60.
Radio postaja Pulala u 8:00 ili 17:00 h za 30 sekundi ima doseg od 300 klijenata, trošak od 100€, mogućnost 30 oglasa i kvalitetu izloženosti od 20.

Što ćete preporučiti poduzeću AZBC ako im je kriterij maksimizirati kvalitetu izloženosti, uz budžet od 30 000 € i uvjete da mora biti bar 10 televizijskih oglasa uz maksimalni utrošak od 18000€ i ukupni doseg od bar 50 000 potencijalnih klijenata?

Struktura problema

Varijable odluke:

Dnevna TV (1 min) postaja Pula = $DTV$

Večernja TV (30 sek), postaja Pula = $VTV$

Dnevne novine (cijela stranica) – Glas Pule = $DNGP$

Nedjeljni magazin (1/2 stranice u boji) = $NM$

Radio, u 8.00 ili 17.00 h, 30 sek, postaja Pulala = $R$

Funkcija cilja:

$Max (65DTV + 90VTV + 40DNGP + 60NM + 2R)$ (maksimizacija s obzirom na kvalitetu izloženosti)

Ograničenja:

$DTV≤ 15$

$VTV≤ 10$

$DNGP≤ 25$

$NM≤ 4$

$R ≤ 30$

$1500DTV + 3000VTV + 400DNGP + 1000NM + 100R≤ 30000$

$DTV +VTV≥ 10$

$1500DTV + 3000VTV≤18000$

$1000DTV + 2000VTV + 1500DNGP + 2500NM + 300R≥ 50000$

if(!require(lpSolve)) install.packages("lpSolve")
library(lpSolve)

# Definiranje funkcije cilja
f.obj <- c(65, 90, 40, 60, 20)

# Matrica ograničenja
f.con <- matrix(c(1, 0, 0, 0, 0, # Ograničenje za DTV
              0, 1, 0, 0, 0, # Ograničenje za VTV
              0, 0, 1, 0, 0, # Ograničenje za DNGP
              0, 0, 0, 1, 0, # Ograničenje za NM
              0, 0, 0, 0, 1, # Ograničenje za R
              1500, 3000, 400, 1000, 100, # Ograničenje troška
              1, 1, 0, 0, 0, # Ograničenje broja TV oglasa
              1500, 3000, 0, 0, 0, # Ograničenje troška za TV
              1000, 2000, 1500, 2500, 300), # Ograničenje doseg
           nrow=9, byrow=TRUE)

# Vektor desne strane ograničenja
f.dir <- c("<=", "<=", "<=", "<=", "<=", "<=", ">=", "<=", ">=")
f.rhs <- c(15, 10, 25, 4, 30, 30000, 10, 18000, 50000)

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

# Ispis rješenja
print(solution)

## Success: the objective function is 2370

solution$solution

## [1] 10  0 25  2 30

solution$duals

##  [1]   0.00   0.00  16.00   0.00  14.00   0.06 -25.00   0.00   0.00   0.00
## [11] -65.00   0.00   0.00   0.00

Na temelju dobivenog rješenja, optimalna alokacija sredstava je:

Kupiti 10 oglasa od Dnevne TV postaje Pula (DTV).
Ne kupiti niti jedan oglas od Večernje TV postaje Pula (VTV).
Kupiti 25 oglasa od Dnevnih novina Glas Pule (DNGP).
Kupiti 2 oglasa od Nedjeljnog magazina.
Kupiti 30 oglasa od Radio postaje Pulala.

Funkcija cilja (kvaliteta izloženosti) je maksimizirana na vrijednosti 2370. To znači da, s obzirom na odabrane oglase i njihove kvalitete izloženosti, poduzeće AZBC može postići maksimalnu kvalitetu izloženosti od 2370.

Dualne vrijednosti predstavljaju osjetljivost funkcije cilja prema promjeni u ograničenjima. Na primjer, dualna vrijednost 16.00 za ograničenje DNGP-a znači da će funkcija cilja porasti za 16 jedinica ako se to ograničenje poveća za jednu jedinicu.

Odabirom optimalne alokacije sredstava, poduzeće AZBC može maksimizirati izloženost klijenta dok ostaje unutar zadanih ograničenja. Investiranje u DTV, DNGP, Nedjeljni magazin, i Radio postaju Pulala omogućuje poduzeću da postigne željeni doseg uz optimalne troškove.

Izbjegavanje kupnje oglasa od VTV može biti rezultat visokih troškova u usporedbi s kvalitetom izloženosti ili drugih ograničenja. S druge strane, odluka o kupnji 25 oglasa od DNGP može biti rezultat njihovih troškova i dosega.

Konačno, poduzeće bi trebalo pažljivo pratiti rezultate ove kampanje kako bi u budućnosti moglo prilagoditi svoju strategiju temeljem stvarnih povratnih informacija. Osim toga, razumijevanje dualnih vrijednosti može poduzeću pomoći u budućim pregovorima s medijima ili prilikom preispitivanja svojeg budžeta za marketing.

Slučaj: Kupovina ili proizvodnja

Problem alokacije resursa

Kalkulator d.d. namjerava proizvoditi dvije vrste kalkulatora, i to: 1) za financijere (naziva „Financijski menadžer”) i 2) za inženjere (naziva „Inženjer”). Kalkulatori se sastoje od tri komponente: kućišta, elektronike i maske. Kućišta su jednaka za oba kalkulatora, dok se ostali dijelovi razlikuju. Menadžeri Kalkulatora d.d. moraju donijeti odluku hoće li navedene dijelove proizvoditi ili kupovati. Temeljem istraživanja tržišta, utvrđeno je da postoji potražnja za 3000 kalkulatora iz serije FM, te 2000 iz serije I. Proizvodni kapaciteti su limitirani s 200 sati rada, te maksimalno 50 sati prekovremenog rada (pri čemu prekovremeni rad stoji 9€ po satu).

Trošak proizvodnje i kupovine za svaku komponentu je kako slijedi: - Kućište košta 0,5€ za proizvodnju i 0,6€ za kupovinu, uz vrijeme proizvodnje od 1 minute. - Elektronika za “Financijski menadžer” košta 3,75€ za proizvodnju, 4€ za kupovinu, s vremenom proizvodnje od 3 minute. - Elektronika za “Inženjer” iznosi 3,3€ za proizvodnju, 3,9€ za kupovinu, uz 2,5 minute za proizvodnju. - Maska za “Financijski menadžer” košta 0,6€ za proizvodnju, 0,65€ za kupovinu, i traje 1 minutu za proizvodnju. - Maska za “Inženjer” iznosi 0,75€ za proizvodnju, 0,78€ za kupovinu, s vremenom proizvodnje od 1,5 minute.

Struktura problema

Varijable odluke - količine

Proizvedene jedinice: $B, EFM, EI, MFM, MI$

Kupljene jedinice: $BK, EFMK, EIK, MFMK, MIK$

$PH$ – sati prekovremenog

Funkcija cilja:

$min (0.5B + 0.6BK + 3.75EFM + 4EFMK + 3.3EI +3.9EIK + 0.6MFM + 0.65MFMK + 0.75MI + 0.78MIK + 9PH)$

Ograničenja:

$B + BK = 5000$

$EFM + EFMK = 3000$

$EI + EIK = 2000$

$MFM + MFMK = 3000$

$MI + MIK = 2000$

$PH \le 50$

$B + 3EFM+2.5EI+MFM+1.5MI ≤12000+60PH$

ili $B + 3EFM+2.5EI+MFM+1.5MI-60PH≤12000$

if(!require(lpSolve)) install.packages("lpSolve")
library(lpSolve)

# Definiranje funkcije cilja
f.obj <- c(0.5, 0.6, 3.75, 4, 3.3, 3.9, 0.6, 0.65, 0.75, 0.78, 9)

# Matrica ograničenja
f.con <- matrix(c(1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, # Ograničenje za kućište
              0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, # Ograničenje za Elektronika FM
              0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, # Ograničenje za Elektronika I
              0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, # Ograničenje za Maska FM
              0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, # Ograničenje za Maska I
              0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, # Ograničenje za PH
              1, 0, 3, 0, 2.5, 0, 1, 0, 0, 0, -60), # Ograničenje za rad
           nrow=7, byrow=TRUE)

# Vektor desne strane ograničenja
f.dir <- c("=", "=", "=", "=", "=", "<=", "<=")
f.rhs <- c(5000, 3000, 2000, 3000, 2000, 50, 12000)

# Rješavanje problema
solution <- lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens = TRUE)

# Ispis rješenja
print(solution)

## Success: the objective function is 24383.33

solution$solution

##  [1] 5000.0000    0.0000  666.6667 2333.3333 2000.0000    0.0000    0.0000
##  [8] 3000.0000 2000.0000    0.0000    0.0000

solution$duals

##  [1]  0.58333333  4.00000000  3.50833333  0.65000000  0.75000000  0.00000000
##  [7] -0.08333333  0.00000000  0.01666667  0.00000000  0.00000000  0.00000000
## [13]  0.39166667  0.03333333  0.00000000  0.00000000  0.03000000  4.00000000

Rješenje ukazuje na sljedeće:

5000 kućišta će biti proizvedeno, dok se nijedno kućište neće kupiti.
666.67 komada elektronike za “Financijski menadžer” će biti proizvedeno, dok će 2333.33 komada biti kupljeno.
Sva elektronika (2000 komada) za “Inženjer” će biti proizvedena, a nijedna se neće kupiti.
Sve maske za “Financijski menadžer” (3000 komada) će biti proizvedene.
Sve maske za “Inženjer” (2000 komada) će biti proizvedene.

Dualne vrijednosti ukazuju na cijenu koja se pridaje svakom ograničenju. Ako je dualna vrijednost pozitivna, to znači da povećanje tog ograničenja za jednu jedinicu rezultira povećanjem funkcije cilja za tu dualnu vrijednost. U tom kontekstu, ograničenje rada ima sjenu cijena -0.083. To znači da bi se funkcija cilja smanjila za 0.083 ako bi dodatni sat rada bio na raspolaganju. Taj dodatni sat rada omogućio bi uštedu na način da se određeni broj komponenti ne bi kupio nego proizvodio (što je jeftinija opcija).

Ako su nam poznate osnovne ekonomske pretpostavke poslovanja, u ovom slučaju mogu se dobiti i dublji uvidi. Naime, optimalna strategija je proizvesti svih 5000 kućišta. To znači da tvrtka može iskoristiti svoje proizvodne resurse da minimizira troškove, umjesto da plaća dodatni iznos za kupovinu.

Nadalje, ako tvrtka proizvodi određenu količinu elektronike za FM, velika količina se kupuje. To ukazuje na to da su kapaciteti proizvodnje ograničeni u odnosu na postojeću potražnju.

Također, pozitivne dualne vrijednosti ukazuju na ograničenja koja su ključna za rješenje. Primjerice, vrijednost od 4€ za elektroniku za kalkulator FM ukazuje da povećanje proizvodnih kapaciteta za tu komponentu može donijeti znatne uštede.

Dakle, ima smisla predložiti da bi Kalkulator d.d. trebao uložiti u proširenje proizvodnih kapaciteta ili poboljšanje proizvodne učinkovitosti za komponente koje imaju visoke dualne vrijednosti kako bi dodatno smanjili troškove i optimizirali svoju proizvodnu strategiju.

Slučaj: Financiranje budućnosti: alternativni izvori financiranja

Problem alokacije resursa

Tvrtka “HeavenFound” stoji na prekretnici svog poslovnog putovanja. Kako bi podržali rast i pokrili operativne troškove, menadžeri su odlučili razmotriti različite alternativne izvore financiranja. No, svaki izvor financiranja dolazi s vlastitim skupom uvjeta i troškova. Neki izvori financiranja, poput “venture capital” investicija, zahtijevaju da tvrtka odredi određeni postotak vlasničkog udjela, dok drugi izvori, poput mikrokredita, mogu nuditi povoljnije kamatne stope. Ključno je da “Finans Alternativa” nađe ravnotežu između dobivanja potrebnih sredstava i zadržavanja većinskog udjela u tvrtki. Odlučili su da za potrebe prikupljanja sredstava ne žele ustupiti više od 30% udjela u tvrtci. Također, bitno je proučiti i maksimalne količine sredstava koje svaki izvor može ponuditi. Tvrtki je potrebno točno 1 000 000 dolara kako bi ostvarili planirani poslovni rast. Žele prikupiti sredstva uz minimalne troškove. Postoji nekoliko izvora financiranja za koje su definirane maksimalne količine sredstava, godišnje kamatne stope i postoci vlasničkog udjela. Crowdfunding: Maksimalna količina sredstava dostupna putem crowdfundinga je 200,000 dolara s godišnjom kamatnom stopom od 5%. Vlasnički udjel za ovu opciju financiranja je 0%. Venture Capital (Kapital rizičnih investitora): Putem Venture Capital-a može se dobiti do 500,000 dolara s godišnjom kamatnom stopom od 8%. U zamjenu za ovo financiranje, kapital rizičnih investitora će zahtijevati 20% vlasničkog udjela. Mikrokrediti: Maksimalni iznos koji se može dobiti putem mikrokredita je 150,000 dolara uz godišnju kamatnu stopu od 3%. Vlasnički udjel za ovu opciju financiranja je 0%. Poslovni Anđeli: Poslovni anđeli mogu ponuditi do 250,000 dolara s godišnjom kamatnom stopom od 7%. U zamjenu za financiranje, poslovni anđeli će zahtijevati 15% vlasničkog udjela. Obveznice: Kroz izdavanje obveznica može se prikupiti do 400,000 dolara s godišnjom kamatnom stopom od 4%. Vlasnički udjel za ovu opciju financiranja je 0%.

Struktura problema

Varijable:

$CF$ - Količina sredstava dobivena putem Crowdfundinga

$VC$ - Količina sredstava dobivena putem Venture Capital-a

$MK$ - Količina sredstava dobivena putem Mikrokredita

$PA$ - Količina sredstava dobivena putem Poslovnih Anđela

$OB$ - Količina sredstava dobivena putem Obveznica

Funkcija cilja:

$min (0.05CF + 0.08VC + 0.03MK + 0.07PA + 0.04OB)$

Ograničenja:

$CF + VC + MK + PA + OB = 1,000,000$ (ukupno sredstava)

$0.20VC + 0.15PA ≤ 300,000$ (ukupni vlasnički udjel ne smije biti više od 30% od 1,000,000)

$CF ≤ 200,000$ (maksimalna količina sredstava putem Crowdfundinga)

$VC ≤ 500,000$ (maksimalna količina sredstava putem Venture Capital-a)

$MK ≤ 150,000$ (maksimalna količina sredstava putem Mikrokredita)

$PA ≤ 250,000$ (maksimalna količina sredstava putem Poslovnih Anđela)

$OB ≤ 400,000$ (maksimalna količina sredstava putem Obveznica)

if(!require(lpSolve)) install.packages("lpSolve")
library(lpSolve)

# Koeficijenti funkcije cilja
f.obj <- c(0.05, 0.08, 0.03, 0.07, 0.04)

# Matrica koeficijenata ograničenja
f.con <- matrix(c(1, 1, 1, 1, 1,  
              0, 0.20, 0, 0.15, 0,
              1, 0, 0, 0, 0,
              0, 1, 0, 0, 0, 
              0, 0, 1, 0, 0,
              0, 0, 0, 1, 0, 
              0, 0, 0, 0, 1),  
            nrow=7, byrow=TRUE)

# Vektor desne strane ograničenja
f.rhs <- c(1000000, 300000, 200000, 500000, 150000, 250000, 400000)

# Vektor koji opisuje vrstu ograničenja 
f.dir <- c("=", "<=", "<=", "<=", "<=", "<=", "<=")

# Rješavanje linearne optimizacije
solution <- lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens = TRUE)

# Ispis rješenja
print(solution)

## Success: the objective function is 48000

print("Rješenje")

## [1] "Rješenje"

solution$solution

## [1] 200000      0 150000 250000 400000

print("Rješenje duala")

## [1] "Rješenje duala"

solution$duals

##  [1]  0.07  0.00 -0.02  0.00 -0.04  0.00 -0.03  0.00  0.01  0.00  0.00  0.00

Temeljem optimizacijskog modela koji se koristi za minimiziranje troškova financiranja, tvrtka “HeavenFound” bi trebala donijeti sljedeće odluke o financiranju:

Prikupiti 200,000 dolara putem Crowdfundinga. Budući da Crowdfunding ne zahtijeva davanje vlasničkog udjela i ima relativno nisku kamatnu stopu, ovo je atraktivna opcija.
Ne uzimati sredstva iz Venture Capital-a. Iako ova opcija nudi velike iznose, također zahtijeva značajan vlasnički udjel, što može biti problematično za tvrtku koja želi zadržati kontrolu.
Prikupiti maksimalnih 150,000 dolara putem Mikrokredita. S obzirom na nisku kamatnu stopu i bez potrebe za davanjem vlasničkog udjela, ova opcija je također povoljna.
Prikupiti 250,000 dolara od Poslovnih Anđela. Iako ova opcija zahtijeva ustupanje vlasničkog udjela, kamatna stopa je relativno povoljna, a količina sredstava koju nude je značajna.
Prikupiti 400,000 dolara izdavanjem Obveznica. Ova opcija pruža pristojan iznos sredstava s umjerenom kamatnom stopom, a bez potrebe za davanjem vlasničkog udjela.

Rješenje duala nam daje informaciju o tome kako promjena desne strane ograničenja utječe na vrijednost funkcije cilja. Pozitivna vrijednost duala sugerira koji su izvori financiranja ključni za smanjenje ukupnih troškova financiranja. Na primjer, pozitivna sjena cjena za Crowdfunding i Poslovne Anđele sugerira da bi dodatna sredstva iz ovih izvora mogla biti povoljna za tvrtku.

Dakle, rješenje ukazuje na to da “HeavenFound” treba razmotriti kombinaciju Crowdfundinga, Mikrokredita, Poslovnih Anđela i Obveznica kako bi prikupila potrebna sredstva. Važno je napomenuti da, prema ovom rješenju, tvrtka neće ustupiti više od 15% svog vlasničkog udjela, čime se osigurava da zadrže kontrolu nad većinskim udjelom. Ovo je ključno za očuvanje strateškog smjera i vizije tvrtke. Minimiziranjem troškova financiranja, tvrtka je postavila temelje za održiv rast i uspjeh, dok istodobno štiti interese svojih osnivača i dioničara.

Slučaj: Transformacija obiteljske kuće u apartmane za odmor

Cjelobrojno programiranje

Ivan je nedavno naslijedio prostranu kuću od $300 𝑚^2$ koja je smještena u atraktivnoj turističkoj zoni i odlučio je prenamijeniti kuću u apartmane za odmor.

Pri odabiru veličina i broja apartmana, Ivan mora razmisliti ne samo o mogućem prihodu već i o drugim faktorima poput održavanja, upravljanja, strateškog pozicioniranja na tržištu te fleksibilnosti smještaja. Na primjer, dok veliki apartmani mogu generirati više prihoda, također mogu zahtijevati više resursa za održavanje. Odlučiti se za pravu kombinaciju apartmana može značiti razliku između uspješne i poražavajuće sezone.

Svjestan je raznolikih potreba turista, pa razmatra različite veličine apartmana:

Mali apartmani (za dvije osobe) su površine $25 m^2$ i mogu mu donijeti godišnji prihod od 5.000 € po apartmanu. No, Ivan ne želi više od 6 takvih apartmana.
Srednji apartmani (za četiri osobe) zauzimaju površinu od $50 m^2$ s potencijalnim godišnjim prihodom od 9.000 € svaki. Ivan želi barem dva takva apartmana radi veće fleksibilnosti smještaja.
Veliki apartmani (za 6 osoba) zauzimaju $75 m^2$ i mogu generirati 12.000 € godišnjeg prihoda svaki. Međutim, Ivan želi imati najviše 3 takva apartmana.

Kada uzme u obzir sve čimbenike, uključujući održavanje, upravljanje, pozicioniranje na tržištu i fleksibilnost, Ivan je odlučio da ukupno ne želi više od 10 apartmana u kući. Ova odluka će mu pomoći da pronađe optimalnu kombinaciju apartmana koja će mu donijeti najbolje rezultate.

Struktura problema:

Varijable odluke:

$x1$ = broj malih apartmana

$x2$ = broj srednjih apartmana

$x3$ = broj velikih apartmana

Funkcija cilja (maksimizacija godišnjeg prihoda):

$Max (5000x1+9000x2+12000x3)$

Ograničenja:

Ograničenje prostora: $25x1+50x2+75x3≤300$

Ograničenje za broj malih apartmana: $x1≤6$

Ograničenje za broj srednjih apartmana: $x2≥2$

Ograničenje ukupnog broja apartmana: $x1+x2+x3≤10$

Ograničenje za broj velikih apartmana: $x3≤3$

Sva tri broja apartmana moraju biti veći ili jednaki nuli: $x1,x2,x3≥0$

Nije moguće odabrati dio apartmana, broj apartmana mora biti cijeli broj: $x1,x2,x3∈Z$

Ovo je slučaj cjelobrojnog programiranja, jer varijable odluke mogu poprimiti isključivo cjelobrojne vrijednosti. Dok se ostatak strukture problema kreira na isti način, pri rješavanju će biti potrebno podesiti uvjet cjelobrojnosti. To će se učiniti definiranjem parametra all.int = TRUE u funkciji lp().

if(!require(lpSolve)) install.packages("lpSolve")
library(lpSolve)

# Definiranje koeficijenata funkcije cilja
f.obj <- c(5000, 9000, 12000)

# Matrica ograničenja (koeficijenti ograničenja)
f.con <- matrix(c(25, 50, 75,
              1, 0, 0,
              0, 1, 0,
              1, 1, 1,
              0, 0, 1), 
            nrow=5, byrow=TRUE)

# Vrste ograničenja
f.dir <- c("<=", "<=", ">=", "<=", "<=")

# Desna strana ograničenja
f.rhs <- c(300, 6, 2, 10, 3)

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

# Ispis rješenja
print(solution)

## Success: the objective function is 57000

print("Rješenje")

## [1] "Rješenje"

solution$solution

## [1] 6 3 0

print("Rješenje duala")

## [1] "Rješenje duala"

solution$duals

## [1]   180   500     0     0     0     0     0 -1500

Ivanov optimalni plan za maksimizaciju godišnjeg prihoda od apartmana jest da kuću preuredi u ukupno 9 apartmana, 6 malih apartmana, 3 srednja apartmana i niti jedan veliki apartman. Ovom kombinacijom apartmana, Ivan će ostvariti maksimalni godišnji prihod od 57.000 €.

Rješenje duala pruža dodatne informacije o cijenama sjena za svako ograničenje. Pozitivna vrijednost cijene sjena ukazuje na povećanje ukupnog prihoda ako se određeno ograničenje poveća za jednu jedinicu. Na primjer, cijena sjena od 180 € za prvo ograničenje znači da bi Ivan mogao očekivati dodatni prihod od 180 € godišnje ako bi imao dodatnih 1 m^2 prostora za apartmane. Ipak, treba imati na umu da apartmani iziskuju više od 1 m^2 površine i da se radi o cjelobrojnim vrijednostima koje broj apartmana može poprimiti.

Sljedeća sjena cijena odnosi se na ograničenje od 6 malih apartmana. Ako bi se ograničenje malih apartmana povećalo na 8, tada bi se funkcija cilja povećala za 1000 eura. U ovom slučaju, to se može lako direktno provjeriti. Dva mala apartmana mogla bi zamijeniti jedan srednji apartman. Jedan srednji apartman pridonosi 9000 eura funkciji cilja, dok dva mala doprinose 2*5000=10000 eura. Razlika među tim prihodima očituje se u sjeni cjena, 500 eura za dodatni mali apartman (odnosno 1000 eura za dva mala apartmana).

Slučaj: Optimizacija angažmana i produktivnosti zaposlenika kroz inicijative

Problem alokacije resursa/binarne varijable odluke

Angažman zaposlenika često je ključni faktor koji određuje produktivnost, efikasnost i opću atmosferu u organizaciji. Prepoznavši važnost ovog aspekta, menadžment tvrtke razmatra ulaganje u različite inicijative kako bi povećao angažman zaposlenika, što će posljedično povećati i njihovu produktivnost. Sljedeće inicijative su predložene:

Timski izleti i team-building aktivnosti: Proučavanja su pokazala da takve aktivnosti mogu poboljšati timsku suradnju, povjerenje među kolegama i osjećaj pripadnosti organizaciji, s potencijalnim povećanjem produktivnosti za 6%.
Sustav nagrađivanja: Pružanjem dodatnih poticaja, tvrtka može potaknuti zaposlenike da daju svoj maksimum, potencijalno povećavajući produktivnost za 8%.
Povratne informacije i mentoring: Kvalitetan sustav povratnih informacija i mentorstva može značajno pomoći zaposlenicima u njihovom profesionalnom razvoju, s mogućim povećanjem produktivnosti za 10%.
Bolja oprema: Investiranje u modernu i visoko-kvalitetnu opremu može smanjiti tehničke prepreke s kojima se zaposlenici susreću, što može rezultirati povećanjem produktivnosti za 7%.
Kontinuirano obrazovanje: Pružanjem mogućnosti za stalno učenje i razvoj, tvrtka može osigurati da su njezini zaposlenici uvijek ažurirani s najnovijim trendovima i tehnikama u industriji, što može pridonijeti povećanju produktivnosti za 9%.

S obzirom na ograničeni budžet od 150,000 USD, tvrtka mora pažljivo razmotriti koje će inicijative implementirati kako bi postigla najveći mogući ROI.

Struktura problema

Varijable odluke:

$x_1,x_2,x_3,x_4,x_5$ - Oznake koje predstavljaju odluku o tome hoće li se određena inicijativa implementirati (1 ako da, 0 ako ne).

Funkcija cilja (maksimizacija produktivnosti):

$max(0.06x_1+ 0.08x_2+ 0.10x_3+ 0.07x_4+ 0.09x_5)$

Ograničenja:

Ukupni budžet za implementaciju inicijativa ne smije premašiti 150,000 USD: $40000x_1+ 20000x_2+ 30000x_3+ 50000x_4+ 25000x_5≤ 150,000$.

Tvrtka želi implementirati barem dvije inicijative kako bi postigla širu promjenu: $x_1+ x_2+ x_3+ x_4+ x_5≥ 2$

$x_1, ..., x_5 = binary$

if(!require(lpSolve)) install.packages("lpSolve")
library(lpSolve)

# Ciljna funkcija 
cvec <- c(0.06, 0.08, 0.1, 0.07, 0.09)

# Matrica ograničenja
Amat <- matrix(c(40000, 20000, 30000, 50000, 25000,
                 1, 1, 1, 1, 1),
               nrow = 2, byrow = TRUE)
dir <- c("<=", ">=")

# Vektor slobodnih članova
bvec <- c(150000, 2)

# Rješavanje problema
solution <- lp("max", cvec, Amat, dir, bvec, all.bin = TRUE)

# Ispis rješenja
solution

## Success: the objective function is 0.34

solution$solution

## [1] 0 1 1 1 1

Rješenje problema ukazuje na optimalan izbor inicijativa koje će tvrtka provesti kako bi maksimizirala angažman zaposlenika unutar ograničenog budžeta. Na temelju rješenja, funkcija cilja dostiže maksimalnu vrijednost od 0.34, što sugerira da će produktivnost zaposlenika potencijalno porasti za 34% ako tvrtka implementira odabrane inicijative.

Varijable odluke pokazuju sljedeći rezultat: [1] 0 1 1 1 1. To znači: - Timski izleti i team-building aktivnosti neće biti implementirani. - Sustav nagrađivanja će biti implementiran. - Povratne informacije i mentoring će biti implementirani. - Bolja oprema će biti nabavljena. - Kontinuirano obrazovanje će biti poticano.

Ovaj odabir sugerira da je model optimizacije prepoznao veću vrijednost u direktnim poticajima za zaposlenike, povratnim informacijama, boljoj opremi i kontinuiranom obrazovanju u odnosu na team-building aktivnosti. Kada se ove inicijative implementiraju, očekuje se da će zaposlenici biti motiviraniji, bolje opremljeni i bolje informirani, što će sve pridonijeti većoj produktivnosti.

U usporedbi s timskim izletima, ostale četiri inicijative nude direktnije koristi za zaposlenike i njihovu svakodnevnu produktivnost. Ako tvrtka uspije uspješno implementirati ove inicijative, može očekivati pozitivan utjecaj na uspjeh poslovanja kroz veću produktivnost i zadovoljstvo zaposlenika.

Slučaj: dostava proizvoda

Transportni problem

Poduzeće želi riješiti problem dostave proizvoda iz tri proizvodna pogona u četiri distribucijska centra. Proizvodni kapaciteti prikazani su tablicom i odnose se na tromjesečni period.

Postrojenje	Tromj. proizvodni kapacitet (kom)
Osijek	4000
Rijeka	6000
Zagreb	3000
Ukupno	13000

Poduzeće distribuira proizvode kroz četiri regionalna distribucijska centra, a tromjesečna procjena potražnje prikazana je tablicom:

Tromjesečna potražnja distribucijskih centara

Distribucijski centar	Tromj. potražnja (kom)
Varaždin	5000
Slavonski Brod	5000
Split	2000
Pula	1000
Ukupno	13000

Jedinični troškovi prijevoza (trošak prijevoza po komadu proizvoda)

	Varaždin	Slavonski Brod	Split	Pula
Osijek	3	2	6	7
Rijeka	5	6	3	3
Zagreb	2	5	5	4

Dakle, iz opisanog slučaja, uočava se da je potrebno riješiti problem dostave na način da se utvrde količine koje je potrebno prevesti iz postrojenja do distribucijskih centara, na način da potražnja bude zadovoljena, a troškovi prijevoza minimalni.

Na početku rješavanja ovakvih problema, korisno je započeti skicom problema, to jest crtanjem grafa.

if(!require(igraph)) install.packages("igraph")

## Loading required package: igraph

## 
## Attaching package: 'igraph'

## The following objects are masked from 'package:stats':
## 
##     decompose, spectrum

## The following object is masked from 'package:base':
## 
##     union

library(igraph)

# Definiranje čvorova i veza
nodes <- c("Osijek", "Rijeka", "Zagreb", "Varaždin", "SlavonskiBrod", "Split", "Pula")
edges <- c(
  "Osijek", "Varaždin", "Osijek", "SlavonskiBrod", "Osijek", "Split", "Osijek", "Pula", 
  "Rijeka", "Varaždin", "Rijeka", "SlavonskiBrod", "Rijeka", "Split", "Rijeka", "Pula", 
  "Zagreb", "Varaždin", "Zagreb", "SlavonskiBrod", "Zagreb", "Split", "Zagreb", "Pula"
)

# Trošak transporta
weights <- c(3, 2, 6, 7, 5, 6, 3, 3, 2, 5, 5, 4)

# Kreiranje grafa
g <- graph_from_data_frame(data.frame(from=edges[seq(1, length(edges), 2)], to=edges[seq(2, length(edges), 2)]), directed=FALSE)
E(g)$weight <- weights

# Postavljanje atributa za čvorove
V(g)$type <- ifelse(V(g)$name %in% c("Osijek", "Rijeka", "Zagreb"), "postrojenje", "centar")
V(g)$color <- ifelse(V(g)$type == "postrojenje", "blue", "red")
V(g)$size <- ifelse(V(g)$type == "postrojenje", 25, 15)
V(g)$label.color <- "black"
V(g)$label.dist <- 4

# Kreiranje prilagođenog layouta
layout_matrix_rotated <- matrix(0, nrow=length(nodes), ncol=2)
layout_matrix_rotated[V(g)$type == "postrojenje", ] <- cbind(1, c(1, 2.5, 4))
layout_matrix_rotated[V(g)$type == "centar", ] <- cbind(2, c(1, 2, 3, 4))

# Vizualizacija grafa
plot(g, 
    layout=layout_matrix_rotated,
    edge.label=E(g)$weight,
    edge.arrow.size=1,
    edge.label.cex = 0.7,
    main="Transportni Problem")

Rješavanje problema linearnim programiranjem zahtijeva određivanje broja komada proizvoda za slanje s obzirom na m polazišta i n odredišta. Varijable odluke uobičajeno označava se x-om. U ovom slučaju, varijable odluke predstavljaju poslane količine iz svakog postrojenja u svaki od distribucijskih centara. Iako će neke od varijabli odluka poprimiti vrijednost nula (po određenoj ruti neće biti prevezenih proizvoda), potrebno je predvidjeti mogućnost prevoženja proizvoda svakom rutom. Također, Kako bi se olakšalo označavanje varijabli odluke, uvriježeno se koristi $x_ij$, pri čemu indeks $i$ označava ishodišni čvor (Osijek=1, Rijeka=2, Zagreb=3), a indeks $j$ odredišne čvorove (Varaždin=1, Slavonski Brod=2, Split=3, Pula=4). U ovom se slučaju, kraće to može zapisati:

$x_ij$=broj poslanih jedinica proizvoda;$i=1,…, m; j=1,…, n$;

Funkcija cilja odnosi se na minimizaciju troška. Stoga, funkcija cilja mora sadržavati varijable odluke uz pripadajući trošak po jedinici proizvoda koji se tom rutom prevozi. Kao pomoćna radnja koja olakšava zapis, može se koristiti razlaganje troškova prema polazišnim čvorovima:

Transportni trošak iz Osijeka=$3x_11+2x_12+6x_13+7x_14$

Transportni trošak iz Rijeke=$5x_21+6x_22+3x_23+3x_24$

Transportni trošak iz Zagreba=$2x_31+5x_32+5x_33+4x_34$

Kako bi zapisali funkciju cilja, navedene je troškove potrebno objediniti:

$min(⁡3x_11+2x_12+6x_13+7x_14+ 5x_21+6x_22+3x_23+3x_24+2x_31+5x_32+5x_33+4x_34)$

Ograničenja se odnose na ograničenje ponude i ograničenje potražnje. Ponuda je ograničena dostupnom količinom, odnosno proizvedenim proizvodima. Iz perspektive ponude, može biti isporučena dostupna količina ili manje. Potražnja je uvjetovana potraživanom količinom, što znači da će pri ograničenju postojati jednakost.

Struktura problema:

Varijable odluke:

$x_{ij}$=broj poslanih jedinica proizvoda;$i=1,…, m; j=1,…, n$;

Funkcija cilja:

$min(⁡3x_{11}+2x_{12}+6x_{13}+7x_{14}+ 5x_{21}+6x_{22}+3x_{23}+3x_{24}+2x_{31}+5x_{32}+5x_{33}+4x_{34})$

Ograničenja ponude:

$x_{11} + x_{12} + x_{13} + x_{14} \leq 4000$

$x_{21} + x_{22} + x_{23} + x_{24} \leq 6000$

$x_{31} + x_{32} + x_{33} + x_{34} \leq 3000$

Ograničenja potražnje:

$x_{11} + x_{21} + x_{31} = 5000$

$x_{12} + x_{22} + x_{32} = 5000$

$x_{13} + x_{23} + x_{33} = 2000$

$x_{14} + x_{24} + x_{34} = 1000$

$x_{ij} \geq 0$

if(!require(lpSolve)) install.packages("lpSolve")
library(lpSolve)

# Definiranje koeficijenata ciljne funkcije (trošak transporta)
f.obj <- c(3, 2, 6, 7, 5, 6, 3, 3, 2, 5, 5, 4)

# Matrica ograničenja
f.con <- matrix(c(1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
              0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0,
              0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1,
              1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
              0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0,
              0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0,
              0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1),
            nrow=7, byrow=TRUE)

# Definiranje smjera ograničenja (<= ili =)
f.dir <- c("<=", "<=", "<=", "=", "=", "=", "=")

# Desna strana ograničenja (ponuda i potražnja)
f.rhs <- c(4000, 6000, 3000, 5000, 5000, 2000, 1000)

# Rješavanje problema
solution <- lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens = TRUE)

# Ispis rješenja
solution

## Success: the objective function is 39000

solution$solution

##  [1]    0 4000    0    0 2000 1000 2000 1000 3000    0    0    0

solution$duals

##  [1] -4  0 -3  5  6  3  3  2  0  7  8  0  0  0  0  0  2  5  4

Rješenje pokazuje optimalnu distribuciju proizvoda iz pogona prema distribucijskim centrima kako bi se minimizirali ukupni troškovi prijevoza. Ukupni trošak dostave proizvoda iznosi 39000 jedinica.

Distribucija:

Iz pogona u Osijeku, 4000 proizvoda bit će poslano u distribucijski centar u Slavonskom Brodu.
Iz pogona u Rijeci, 2000 proizvoda će biti poslano u Varaždin, 1000 u Slavonski Brod i 2000 u Split te 1000 u Pulu.
Iz pogona u Zagrebu, 3000 proizvoda će biti poslano u Varaždin.

Sjene cijena (ili dualne vrijednosti) daju informacije o tome koliko bi se funkcija cilja promijenila kad bi se desnoj strani pripadajućeg ograničenja dodala jedinica. Na primjer, veća ograničenja ponude Osijeka i Zagreba mogla bi smanjiti vrijednost funkcije cilje. Naime, iz tih lokacija je jeftinije prevesti proizvode do nekih distribucijskih centara.

Optimalna distribucija proizvoda omogućava poduzeću da zadovolji potražnju distribucijskih centara uz minimalne troškove. Uzimajući u obzir sjene cijena, poduzeće može prepoznati mogućnosti za dodatne uštede optimizacijom kapaciteta proizvodnje i rješavanjem uskih grla u distribucijskom lancu. Ova informacija može biti dragocjena pri donošenju odluka o budućim investicijama i strateškom planiranju.

Slučaj: Odabir rute

Problem najkraćeg puta

Menadžer poduzeća mora svaki dan putovati od svog ureda do podružnice. Potrebno je utvrditi rutu kojom menadžer može najkraćim putem stići od svog ureda do podružnice na čvoru 7. Moguće rute od njegovog ureda (1) do podružnice (7) predstavljene su slikom. Težine prikazane na lukovima označavaju udaljenosti između dva čvora, izražene u kilometrima.

if(!require(igraph)) install.packages("igraph")
library(igraph)

# Stvaranje grafa s lukovima i težinama
g <- graph(edges=c(1,2, 1,3, 2,3, 2,4, 4,2, 2,6, 3,5, 3,4, 4,3, 4,5, 5,4, 4,6, 5,7, 6,7),
         directed=TRUE)

E(g)$weight <- c(17, 22, 4, 4, 4, 15, 11, 3, 3, 1, 1, 3, 5, 6)

# Prilagođeni layout
layout_custom <- matrix(c(-3,1,  -2,2.5,  -2,0,  0,1,  1,0,  1,2.5,  3,1), ncol=2, byrow=TRUE)

# Prikaz grafa
plot(g, 
    layout=layout_custom, 
    edge.label=E(g)$weight, 
    edge.arrow.size=0.5, 
    vertex.color="lightblue", 
    vertex.size=30, 
    edge.curved=0.2,
    main="Ruta menadžera")

Struktura problema

Varijable odluke predstavljaju svi lukovi prikazani na grafu, a težine pripisane lukovima postaju koeficijenti koji množe varijable odluke u funkciji cilja. S obzirom da se želi utvrditi najkraći put, funkcija cilja je minimizacija sume tih umnožaka.

Ključ razvoja modela najkraće rute leži u razumijevanju posrednih čvorova (zapravo se promatrati kao transportni problem s posrednim čvorovima, uz iznimku prevezenih količina). Važno je ne izgubiti menadžera u mreži. Situacija se može promatrati tako da čvor 1 predstavlja polazište, čvorovi 2, 3, 4, 5 i 6 su posredni čvorovi, a čvor 7 je odredišni čvor. Osim toga, potrebno je predvidjeti da putem bridova x_12 i x_13 u mrežu ulazi 1 menadžer. Također, iz mreže izlazi 1 menadžer, a to može učiniti putem bridova x_67 i x_57.

Varijable odluke:

čvorovi $x_{ij}$

Funkcija cilja:

$min (17x_{12} + 22x_{13} + 4x_{23} + 4x_{24} + 4x_{42} + 15x_{26} + 11x_{35} + 3x_{34} + 3x_{43} + x_{45} + x_{54} + 3x_{46} + 5x_{57} + 6x_{67})$

Ograničenja:

$x_{12} + x_{13} = 1$ Ograničenje ulaska 1 menadžera u mrežu

$-x_{12} - x_{42} + x_{23} + x_{24} + x_{26} = 0$ ograničenje posrednog čvora 2

$-x_{13} - x_{23} - x_{43} + x_{34} + x_{35} = 0$ ograničenje posrednog čvora 3

$-x_{24} - x_{34} - x_{54} + x_{42} + x_{43} + x_{45} + x_{46} = 0$ ograničenje posrednog čvora 4

$-x_{35} - x_{45} + x_{54} + x_{57} = 0$ ograničenje posrednog čvora 5

$-x_{26} - x_{46} + x_{67} = 0$ ograničenje posrednog čvora 6

$x_{67} + x_{57} = 1$ Ograničenje izlaska 1 menadžera iz mreže

$x_{ij} \geq 0$, za sve i i j

Za promjenu, koristit ćemo paket linprog (Henningsen 2022).

if(!require(linprog)) install.packages("linprog")

## Loading required package: linprog

library(linprog)

# Koeficijenti funkcije cilja
cvec <- c(17, 22, 4, 4, 4, 15, 11, 3, 3, 1, 1, 3, 5, 6)

# Matrica koeficijenata za ograničenja
#      x_12  x_13  x_23  x_24  x_42  x_26  x_35  x_34  x_43  x_45  x_54  x_46  x_57  x_67

Amat <- matrix(c(
  1,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, # Ograničenje ulaska 1 menadžera u mrežu
 -1,  0,  1,  1, -1,  1,  0,  0,  0,  0,  0,  0,  0,  0, # Ograničenje posrednog čvora 2
  0, -1, -1,  0,  0,  0,  1,  1, -1,  0,  0,  0,  0,  0, # Ograničenje posrednog čvora 3
  0,  0,  0, -1,  1,  0,  0, -1,  1,  1, -1,  1,  0,  0, # Ograničenje posrednog čvora 4
  0,  0,  0,  0,  0,  0, -1,  0,  0, -1,  1,  0,  1,  0, # Ograničenje posrednog čvora 5
  0,  0,  0,  0,  0, -1,  0,  0,  0,  0,  0, -1,  0,  1, # Ograničenje posrednog čvora 6
  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  1),  # Ograničenje izlaska 1 menadžera iz mreže, 
 ncol = 14, byrow = TRUE)

# Vektor s desne strane jednadžbi
bvec <- c(1, 0, 0, 0, 0, 0, 1)

# Rješenje LP modela
result <- lp("min", cvec, Amat, "=", bvec, all.bin = TRUE)

result

## Success: the objective function is 27

lukovi <- c("x_12",  "x_13",  "x_23",  "x_24",  "x_42",  "x_26",  "x_35",  "x_34",  "x_43",  "x_45",  "x_54",  "x_46",  "x_57",  "x_67")
rez <- cbind(lukovi, result$solution)
rez<- as.table(rez)
rez

##   lukovi  
## A x_12   1
## B x_13   0
## C x_23   0
## D x_24   1
## E x_42   0
## F x_26   0
## G x_35   0
## H x_34   0
## I x_43   0
## J x_45   1
## K x_54   0
## L x_46   0
## M x_57   1
## N x_67   0

Alternativno, može se koristiti paket igraph (Csárdi et al. 2023), s kojim je prethodno kreiran grafički prikaz.

if(!require(igraph)) install.packages("igraph")
library(igraph)

#najkraći put između čvorova, koristimo ranije kreirani graf
shortest_path <- shortest_paths(g, from=1, to=7, output="both")

# Prikaz najkraćeg puta
shortest_path$vpath[[1]]

## + 5/7 vertices, from 1054a40:
## [1] 1 2 4 5 7

shortest_path$epath[[1]]

## + 4/14 edges from 1054a40:
## [1] 1->2 2->4 4->5 5->7

f.cilja = 

# Označavanje najkraćeg puta crvenom bojom
E(g)$color <- "black"
for (edge in shortest_path$epath[[1]]) {
  E(g)[edge]$color <- "red"
}


# Prikaz grafa sa označenim najkraćim putem (crveno) 
plot(g, edge.color=E(g)$color, edge.width=2, edge.label=E(g)$weight, 
    vertex.size=25, vertex.label.dist=1.5, layout=layout_custom, 
    main="Ruta menadžera", edge.arrow.size=0.5)

Rješenje pokazuje optimalnu rutu kojom menadžer treba putovati da bi od svog ureda (čvor 1) stigao do podružnice (čvor 7) na najkraći mogući način. Na temelju rješenja, menadžer bi trebao slijediti ovu rutu:

Od ureda (čvor 1) do čvora 2 preko luka A ($x_{12}$).
Zatim, od čvora 2 do čvora 4 preko luka D ($x_{24}$).
Dalje, od čvora 4 do čvora 5 preko luka J ($x_{45}$).
Napokon, od čvora 5 do podružnice (čvor 7) preko luka M ($x_{57}$).

Ukupna udaljenost ove rute iznosi 27 kilometara, što je najkraća moguća ruta.

Odabirom najkraće rute, menadžer ne samo da štedi vrijeme putovanja, već i smanjuje troškove povezane s putovanjima, kao što su troškovi goriva ili troškovi održavanja vozila. Uz to, manje vremena provedenog u putovanju znači da menadžer ima više vremena za obavljanje poslovnih aktivnosti, što može doprinijeti boljoj produktivnosti i učinkovitosti. Osim toga, redovito korištenje najkraće rute može rezultirati boljom predvidljivošću dolazaka i odlazaka, što može biti korisno za planiranje sastanaka i drugih obaveza.

Slučaj: Ljetne gužve u Istri

Problem maksimalnog protoka

Kao primjer problema maksimalnog toka, analizira se primjer ljetnih gužvi na ulazu u Pulu. Prema izvješću Hrvatskih autocesta, na izlazu s Istarskog Ipsilona Pula-sjever je u kolovozu 2021. godine prošlo 1590536 automobila. To je približno 51308 automobila dnevno. Razmatra se situacija u kojoj je izlaz Pula-sjever nedostupan jer je donji dio ceste zatvoren (npr. zbog radova na cesti ili zbog prometne nesreće) te automobili moraju koristiti izlaz Vodnjan-jug (Slika).

Pretpostavlja se da automobili žele stići u Pulu ili u neku od turističkih destinacija na jugu Istre. Utvrđene su mogućnosti preusmjeravanja prometa (niže generirana slika), a težine na lukovima predstavljaju maksimalni kapacitet automobila koji u minuti može proći određenom dionicom puta.

Ako bi tijekom gužve pristizalo 500 automobila u minuti, je li moguće kreirati takvo preusmjeravanje da ne dolazi do zastoja u prometu? Koliko automobila može izaći iz mreže u jednoj minuti?

#if(!require(sf, ggplot2, ggmap, ggraph, igraph)) install.packages(c("sf", "ggplot2", "ggmap", "ggraph", "igraph"))

library(sf)

## Linking to GEOS 3.11.2, GDAL 3.7.2, PROJ 9.3.0; sf_use_s2() is TRUE

library(ggplot2)
library(ggmap)

## ℹ Google's Terms of Service: <https://mapsplatform.google.com>
## ℹ Please cite ggmap if you use it! Use `citation("ggmap")` for details.

library(ggraph)
library(igraph)

Za nastavak će vam trebati Google Maps API ključ, kako biste mogli dohvatiti odgovarajuću mapu.

Pribavljanje Google Maps API ključa:

Posjetite Google Cloud Console.
Napravite novi projekt ili odaberite postojeći.
U izborniku s lijeve strane odaberite “Biblioteka”, potražite “Maps JavaScript API” i omogućite ga.
Nakon što omogućite API, idite na izbornik “Vjerodajnice” kako biste stvorili novi API ključ.
Slijedite upute za stvaranje ključa.

## ℹ <https://maps.googleapis.com/maps/api/staticmap?center=44.92,13.875&zoom=12&size=640x640&scale=2&maptype=roadmap&key=xxx-zTjU>

#register_google(key = "Vaš Google Maps API ključ")
istra_map <- get_googlemap(center = c(lon= 13.875, lat = 44.92), maptype = "roadmap", zoom = 12)

## ℹ <https://maps.googleapis.com/maps/api/staticmap?center=44.92,13.875&zoom=12&size=640x640&scale=2&maptype=roadmap&key=xxx-zTjU>

ggmap(istra_map)

edges <- data.frame(
  from = c(1, 1, 1, 2, 2, 3, 3, 4, 5,  6, 6,  7, 8, 9, 10),
  to =   c(2, 3, 6, 4, 7, 2, 5, 5, 10, 5, 10, 8, 9, 11, 11),
  weight = c(141, 55, 134, 680, 880, 127, 187, 410, 638, 130, 570, 1091, 200, 94, 214)
)

g <- graph_from_data_frame(edges, directed = TRUE)

layout_coords <- layout_nicely(g)

edges_df <- get.data.frame(g, what = "edges")

# Pretvorimo layout_coords u data frame
layout_df <- as.data.frame(layout_coords)
colnames(layout_df) <- c("x", "y")

# Dodajemo koordinate
vertices_df <- data.frame(
  name = c(1:11),
  x = c(13.872522, 13.856774, 13.853459, 13.804559, 13.851631, 13.868820, 13.954344, 13.905709, 13.889106, 13.846062, 13.864071),
  y = c(44.951202, 44.963265, 44.946469, 44.926220, 44.928099, 44.930904, 44.956833, 44.915968, 44.892654, 44.890473, 44.880731)
)

edges_df$x <- vertices_df$x[match(edges_df$from, vertices_df$name)]
edges_df$y <- vertices_df$y[match(edges_df$from, vertices_df$name)]
edges_df$xend <- vertices_df$x[match(edges_df$to, vertices_df$name)]
edges_df$yend <- vertices_df$y[match(edges_df$to, vertices_df$name)]
edges_df$mid_x <- (edges_df$x + edges_df$xend) / 2
edges_df$mid_y <- (edges_df$y + edges_df$yend) / 2


# Crtamo
ggmap(istra_map) +
  geom_segment(data = edges_df, aes(x = x, y = y, xend = xend, yend = yend), 
            arrow = arrow(type = "closed", length = unit(0.1, "inches")), 
            alpha = 0.5, linewidth = 1) +
  geom_point(data = vertices_df, aes(x = x, y = y), size = 3, color = "red") +
  geom_text(data = vertices_df, aes(x = x, y = y, label = name), 
         check_overlap = TRUE, size = 2.5) +   
  geom_text(data = edges_df, aes(x = mid_x, y = mid_y, label = weight), 
           check_overlap = TRUE, vjust=0.5, hjust=0.5, size = 2.5) +  
  # Dodajemo luk koji ulazi u čvor 1 s težinom 500
  geom_segment(aes(x = 13.88, y = 44.99, 
             xend = vertices_df$x[vertices_df$name == "1"], 
             yend = vertices_df$y[vertices_df$name == "1"]), 
          arrow = arrow(type = "closed", length = unit(0.1, "inches")), 
          alpha = 0.5, linewidth = 1, color = "blue") + 
  geom_text(aes(x = 13.88, y = 44.99, label = "500"), 
         check_overlap = TRUE, vjust=-0.5, hjust=1.5, size = 2.5, color = "blue") +
  # Dodajemo luk koji izlazi iz čvora 11 bez naznačene težine
  geom_segment(aes(x = vertices_df$x[vertices_df$name == "11"], 
               y = vertices_df$y[vertices_df$name == "11"], 
               xend = 13.86, yend = 44.86), 
            arrow = arrow(type = "closed", length = unit(0.1, "inches")), 
            alpha = 0.5, linewidth = 1, color = "green") + 
  theme_minimal()

Po pitanju problema maksimalnog toka mreže, podrazumijeva se da će ono što u mrežu uđe, iz nje i izaći. O tome se može razmišljati na način da se svi čvorovi mreže tretiraju kao posredni čvorovi. Pritom osobitu pozornost treba posvetiti prvom i posljednjem čvoru. Naime, radi jednostavnosti, u ovakve se mreže često dodaje dodatni luk ($⁡x_{11,1}$) koji simbolizira navedenu pravilnost, a to je luk koji spaja posljednji čvor s prvim.

Nadalje, težine zapisane na lukovima ove mreže predstavljaju kapacitet, odnosno količinu automobila koja prolazi pojedinim lukom.

Struktura problema:

Varijabble odluke:

čvorovi $x_{ij}$

Funkcija cilja:

$\max x_{11,1}$

Ograničenja:

$-x_{11,1} + x_{12} + x_{13} + x_{16} = 0$

$-x_{12} - x_{13} + x_{24} + x_{27} = 0$

$-x_{13} + x_{32} + x_{35} = 0$

$-x_{24} + x_{45} = 0$

$-x_{35} - x_{45} - x_{65} + x_{5,10} = 0$

$-x_{16} + x_{65} + x_{6,10} = 0$

$-x_{27} + x_{78} = 0$

$-x_{78} + x_{89} = 0$

$-x_{89} + x_{9,11} = 0$

$-x_{5,10} - x_{6,10} + x_{10,11} = 0$

$-x_{10,11} - x_{9,11} + x_{11,1} = 0$

$x_{12} \leq 141$

$x_{13} \leq 55$

$x_{16} \leq 134$

$x_{24} \leq 680$

$x_{27} \leq 880$

$x_{32} \leq 127$

$x_{35} \leq 187$

$x_{45} \leq 410$

$x_{5,10} \leq 638$

$x_{6,5} \leq 130$

$x_{6,10} \leq 570$

$x_{7,8} \leq 1091$

$x_{8,9} \leq 200$

$x_{9,10} \leq 214$

$x_{10,11} \leq 94$

$x_{ij} \geq 0$

#Redoslijed varijabli: 
#x11,1, x12, x13, x16, x24, x27, x32, x35, x45, x5,10, x65, x6,10, x78, x89, x9,11, x10,11

f.obj <- c(1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

# Matrica ograničenja (ovisno o redoslijedu varijabli koje ste koristili, ovo možda treba prilagoditi)
f.con <- matrix(c(
  -1,  1,  1,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, #-x_11,1+x_12+x_13+x_16=0 
   0, -1, -1,  0,  1,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, #-x_12-x_13+x_24+x_27=0 
   0,  0, -1,  0,  0,  0,  1,  1,  0,  0,  0,  0,  0,  0,  0,  0, #-x_13+x_32+x_35=0 
   0,  0,  0,  0, -1,  0,  0,  0,  1,  0,  0,  0,  0,  0,  0,  0, #-x_24+x_45=0 
   0,  0,  0,  0,  0,  0,  0, -1, -1,  1, -1,  0,  0,  0,  0,  0, #-x_35-x_45-x_65+x_5,10=0 
   0,  0,  0, -1,  0,  0,  0,  0,  0,  0,  1,  1,  0,  0,  0,  0, #-x_16+x_65+x_6,10=0 
   0,  0,  0,  0,  0, -1,  0,  0,  0,  0,  0,  0,  1,  0,  0,  0, #-x_27+x_78=0
   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, -1,  1,  0,  0, #-x_78+x_89=0 
   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, -1,  1,  0, #-x_89+x_9,11=0
   0,  0,  0,  0,  0,  0,  0,  0,  0, -1,  0, -1,  0,  0,  0,  1, #-x_5,10-x_6,10+x_10,11=0 
   1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, -1, -1, #-x_10,11-x_9,11+x_11,1=0 
   0,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, # x_12≤141
   0,  0,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, #x_13≤55 
   0,  0,  0,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, #x_16≤134 
   0,  0,  0,  0,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, #x_24≤680 
   0,  0,  0,  0,  0,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, #x_27≤880
   0,  0,  0,  0,  0,  0,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0, #x_32≤127 
   0,  0,  0,  0,  0,  0,  0,  1,  0,  0,  0,  0,  0,  0,  0,  0, #x_35≤187 
   0,  0,  0,  0,  0,  0,  0,  0,  1,  0,  0,  0,  0,  0,  0,  0, #x_45≤410 
   0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  0,  0,  0,  0,  0,  0, #x_5,10≤638 
   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  0,  0,  0,  0,  0, #x_6,5≤130 
   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  0,  0,  0,  0, #x_6,10≤570 
   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  0,  0,  0, #x_7,8≤1091 
   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  0,  0, #x_8,9≤200
   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  0, #x_9,11≤214 
   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1), #x_10,11≤94
  nrow=26, byrow=TRUE)
 
f.rhs <- c(rep(0, 11), 141, 55, 134, 680, 880, 127, 187, 410, 638, 130, 570, 1091, 200, 214, 94)

f.dir <- c(rep("==", 11), rep("<=", 15))

# Rješenje 
result <- lp("max", f.obj, f.con, f.dir, f.rhs, all.bin = FALSE)
result

## Success: the objective function is 290

result$solution

##  [1] 290 141  55  94   0 196  55   0   0   0   0  94 196 196 196  94

lukovi <- c("x11,1", "x12", "x13", "x16", "x24", "x27", "x32", "x35", "x45", "x5,10", "x65", "x6,10", "x78", "x89", "x9,11", "x10,11")
rez <- cbind(lukovi, result$solution)
rez

##       lukovi        
##  [1,] "x11,1"  "290"
##  [2,] "x12"    "141"
##  [3,] "x13"    "55" 
##  [4,] "x16"    "94" 
##  [5,] "x24"    "0"  
##  [6,] "x27"    "196"
##  [7,] "x32"    "55" 
##  [8,] "x35"    "0"  
##  [9,] "x45"    "0"  
## [10,] "x5,10"  "0"  
## [11,] "x65"    "0"  
## [12,] "x6,10"  "94" 
## [13,] "x78"    "196"
## [14,] "x89"    "196"
## [15,] "x9,11"  "196"
## [16,] "x10,11" "94"

S obzirom da je graf već definiran, alternativno možemo koristiti igraph za rješavanje.

library(igraph)

# graf je već ranije definiran, ali ovdje moramo dodati još jedan luk, od posljednjeg do prvog čvora, iz istog razloga kao ranije
cvorovi <- data.frame(c(1,2,3,4,5,6,7,8,9,10,11))
edges <- data.frame(
  from = c(1, 1, 1, 2, 2, 3, 3, 4, 5,  6, 6,  7, 8, 9, 10, 11),
  to =   c(2, 3, 6, 4, 7, 2, 5, 5, 10, 5, 10, 8, 9, 11, 11, 1),
  weight = c(141, 55, 134, 680, 880, 127, 187, 410, 638, 130, 570, 1091, 200, 214, 94, 500))

g <- graph_from_data_frame(edges, directed = TRUE, vertices = cvorovi)

max_flow_value <- max_flow(g, source = V(g)[1], target = V(g)[11], capacity = edges$weight)

max_flow_value$value

## [1] 290

lukovi2 <- c("x12", "x13", "x16", "x24", "x27", "x32", "x35", "x45", "x5,10", "x65", "x6,10", "x78", "x89", "x9,11", "x10,11", "x11,1")
rez.pom <- max_flow_value$flow
rez.pom[length(rez.pom)] <-max_flow_value$value
rez2 <- cbind(lukovi2, rez.pom)
rez2

##       lukovi2  rez.pom
##  [1,] "x12"    "141"  
##  [2,] "x13"    "55"   
##  [3,] "x16"    "94"   
##  [4,] "x24"    "0"    
##  [5,] "x27"    "196"  
##  [6,] "x32"    "55"   
##  [7,] "x35"    "0"    
##  [8,] "x45"    "0"    
##  [9,] "x5,10"  "55"   
## [10,] "x65"    "55"   
## [11,] "x6,10"  "39"   
## [12,] "x78"    "196"  
## [13,] "x89"    "196"  
## [14,] "x9,11"  "196"  
## [15,] "x10,11" "94"   
## [16,] "x11,1"  "290"

plot.igraph(g, edge.label = max_flow_value$flow, layout=layout_as_tree)

Funkcija max_flow() u paketu igraph za R koristi Push-relabel algoritam za pronalaženje maksimalnog protoka u mreži. Push-relabel algoritam (metoda etiketiranja) je poznat po svojoj efikasnosti i često se koristi za rješavanje problema maksimalnog protoka. Algoritam djeluje tako što “gura” protok kroz mrežu dok se ne postigne stanje u kojem više nije moguće “gurati” protok.

Prema rješenju, ciljna funkcija je 290, što znači da maksimalno 290 automobila može izaći iz mreže svake minute. Varijable odluke pokazuju kako se automobili distribuiraju kroz mrežu. Tokovi pokazuju da se 141 automobila preusmjerava na “x12”, 55 na “x13” i 94 na “x16”. Izlaz iz mreže je omogućen kroz “x9,11” s maksimalnim tokom od 196 automobila i “x10,11” s tokom od 94 automobila, što ukupno iznosi 290 automobila.

Iz ovog rješenja možemo zaključiti da, unatoč preusmjeravanju prometa zbog zatvaranja izlaza Pula-sjever, mreža može efikasno “progurati” 290 automobila u minuti. Međutim, ako tijekom gužve pristigne 500 automobila u minuti, mreža će se suočiti s preopterećenjem od 210 automobila svake minute. Ekonomske implikacije ovog preopterećenja uključuju moguće zastoje, povećano vrijeme putovanja, veće troškove goriva i potencijalno smanjenje turističkih prihoda ako turisti odustanu od posjeta zbog gužve. Upravljanje ovim prometnim izazovima bitno je za održavanje ekonomske isplativosti regije tijekom ljetnih mjeseci.

Slucaj: Dodjela radnih zadataka

Problem pridruživanja

Zaposleni ste kao manager proizvodnje tvrtke Tab d.o.o. Pred Vama je novi izazov: rasporediti tri radne aktivnosti na tri dostupna radnika. Promatramo projektni tim koji radi na osmišljavanju novog tableta. Projektni tim čine Ivan, Maja i Luka. Aktivnosti koje je potrebno provesti su osmišljavanje dizajna maske, osmišljavanje kućišta i odabir elektroničkih dijelova za tablet. Uvjet je da svaka osoba može dobiti samo po jednu aktivnost, a cilj je da ukupno vrijeme za izvršenje aktivnosti bude što manje. Iz odjela ljudskih resursa, dobili ste izviješće o produktivnosti zaposlenika izraženu u vremenu (radnim danima).

Ivan je u prosjeku proveo 10 dana osmišljavajući dizajn maske, 15 dana osmišljavajući kućišta i 9 dana odabirući komponente, prema izvješćima odjela za ljudske resurse.
Maja je u prosjeku za osmišljavanje dizajna maske utrošila 9 dana, za osmišljavanje kućišta 18 dana, te za odabir komponenti 5 dana, temeljem podataka odjela za ljudske resurse.
Luka je u prosjeku osmišljavanje dizajna maske završio za 6 dana, osmišljavanje kućišta za 14 dana, dok je za odabir komponenti potrošio 3 dana, prema informacijama odjela za ljudske resurse.

Ovdje se radi o problemu pridruživanja, pri čemu menadžer (tj. Vi) trebate pridružiti svakom zaposleniku točno jedan zadatak na način da utrošeno vrijeme za provedbu svih aktivnosti bude minimalno.

Početna vizualizacija:

cvorovi <- data.frame(c("Ivan", "Maja", "Luka", "Dizajn maske", "Osmišljavanje kućišta", "Odabir komponenti"))
edges <- data.frame(
  from = c("Ivan","Ivan","Ivan","Maja","Maja","Maja","Luka","Luka","Luka"),
  to =   c("Dizajn maske", "Osmišljavanje kućišta", "Odabir komponenti","Dizajn maske", "Osmišljavanje kućišta", "Odabir komponenti","Dizajn maske", "Osmišljavanje kućišta", "Odabir komponenti"),
  weight = c(10,15,9,9,18,5,6,14,3))

g <- graph_from_data_frame(edges, directed = FALSE, vertices = cvorovi)


plot.igraph(g, edge.label = edges$weight, 
         layout = layout_as_tree(g, root = match(c("Ivan", "Maja", "Luka"), V(g)$name)),
         vertex.label.dist = 2,
         edge.label.dist = 2,
         edge.label.cex = 0.7,
         vertex.label.cex = 0.7,
         edge.curved = 0.1)

Ograničenja vezana uz zaposlenike funkcioniraju na sličan način kao ograničenja vezana za ponudu, u smislu da svatko od njih ima kapacitet za preuzimanje do jednog radnog zadatka.Ograničenja vezana uz radne zadatke slična su ograničenjima potražnje u ranijim zadacima, pri čemu svaki zadatak mora biti dodijeljen nekom od zaposlenika.

Varijable odluke predstavljaju dodjeljivanje određenog zadatka (1, 2 ili 3) pojedinom zaposleniku (1, 2 ili 3). Varijable odluke su binarne te mogu poprimiti vrijednost 1 (ako je zadatak dodijeljen) ili 0 (ako zadatak nije dodijeljen).

Struktura problema

Varijable odluke: $x_{ij}$

Funkcija cilja: $\Min 10x_{11}+15x_{12}+9x_{13}+9x_{21}+18x_{22}+5x_{23}+6x_{31}+14x_{32}+3x_{33}$

Ograničenja:

$x_{11}+x_{12}+x_{13}≤1$ #Ivan

$x_{21}+x_{22}+x_{23}≤1$ #Maja

$x_{31}+x_{32}+x_{33}≤1$ #Luka

$x_{11}+x_{21}+x_{31}=1$ #Dizajn maske

$x_{12}+x_{22}+x_{32}=1$ #Dizajn kućišta

$x_{13}+x_{23}+x_{33}=1$ #Odabir komponenti

library(lpSolve)

f.obj <- c(10, 15, 9, 9, 18, 5, 6, 14, 3)

f.con <- matrix(c(1, 0, 0, 1, 0, 0, 1, 0, 0,
              0, 1, 0, 0, 1, 0, 0, 1, 0,
              0, 0, 1, 0, 0, 1, 0, 0, 1,
              1, 1, 1, 0, 0, 0, 0, 0, 0,
              0, 0, 0, 1, 1, 1, 0, 0, 0,
              0, 0, 0, 0, 0, 0, 1, 1, 1), 
           nrow=6, byrow=TRUE)

f.dir <- c("<=", "<=", "<=", "==", "==", "==")

f.rhs <- c(1, 1, 1, 1, 1, 1)

result <- lp("min", f.obj, f.con, f.dir, f.rhs, all.bin = TRUE)

result

## Success: the objective function is 26

result$solution

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

Koristeći lpSolve (i dalje), ovaj se problem može riješiti i na drugačiji način:

library(lpSolve)
vrijeme <- matrix(c(10,15,9,9,18,5,6,14,3), nrow = 3, byrow = TRUE)
pridruzivanje<-lp.assign(vrijeme)
pridruzivanje$solution

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

pridruzivanje$solution*vrijeme

##      [,1] [,2] [,3]
## [1,]    0   15    0
## [2,]    0    0    5
## [3,]    6    0    0

sum(pridruzivanje$solution*vrijeme)

## [1] 26

Ivan treba raditi na osmišljavanju kućišta, a za to će mu trabati 15 dana. Maja će raditi na odabiru elektroničkih dijelova za tablet i tu aktivnost dovršiti kroz5 dana. Luki dodjeljujete osmišljavanje dizajna maske, za što će mu trebati 6 dana. Sve će aktivnosti biti dovršene u roku od 26 dana. Dakle, ne samo da ste efikasno rasporedili zadatke, već ste također osigurali da se projekt dovrši što je brže moguće s obzirom na raspoložive resurse.

Ekonomski gledano, optimalno raspoređivanje zadataka ključno je za smanjenje troškova i povećanje produktivnosti. U ovom slučaju, to je postignuto na način da su zadaci raspodijeljeni na temelju individualnih sposobnosti i iskustava zaposlenika. Tako je ukupno vrijeme za izvršenje svih zadataka minimalno. Osim toga, brže dovršavanje projekta može rezultirati ranijim plasiranjem proizvoda na tržište, čime se može ostvariti konkurentska prednost. Dodatno, smanjenjem vremena potrebnog za završetak projekta, smanjuju se i ukupni operativni troškovi tvrtke, što može dovesti do povećanja profitabilnosti.

Slučaj: Organizacija znanstvene konferencije

Utvrđivanje kritičnog puta/ raspored

Pripreme za znanstvenu konferenciju su kompleksan proces koji uključuje niz različitih koraka, svaki s vlastitim vremenskim okvirom. Upravljanje svim tim zadacima, osiguravanje koordinacije među članovima tima i osiguranje pravovremene izvedbe ključni su za uspješnu organizaciju konferencije. Generički plan i raspored kojim ćemo se ovdje baviti mogu poslužiti kao početna točka, ali svaka konferencija će imati svoje jedinstvene zahtjeve i izazov.

U prvom koraku, potrebno je definirati aktivnosti i vrijeme izvršenja. U sljedećem koraku, kreiramo dataframe temeljem poznatih podataka, koji se radi dupliranja neće sad navoditi.

# Kreiranje dataframea s podacima
konferencija <- cbind(
  c(seq(1,30)), 
  c("Odluka o organizaciji konferencije", "Formiranje organizacijskog odbora", "Izbor Predsjednika organizacijskog odbora",
   "Uspostava kanala komunikacije", "Odabir mjesta i datuma te provjera dostupnosti", "Definiranje formata radova", 
  "Postavljanje recenzentskog postupka", "Izrada financijskog proračuna", "Definiranje iznosa kotizacije", 
  "Utvrđivanje važnih datuma", "Kontaktiranje pozvanih izlagača", "Objava informacija o uplati kotizacije", 
  "Izrada i slanje poziva za sudjelovanje", "Promocija konferencije online", "Uspostava registracijskog obrasca", 
  "Proces recenzije radova", "Praćenje financijskog stanja", "Dostava ponuda za uplatu kotizacije", 
  "Priprema za traženje sredstava od Ministarstva", "Kontaktiranje sponzora konferencije","Ugovaranje s donatorima/sponzorima", 
  "Organizacija smještaja za keynote govornike", "Izrada programa konferencije", "Priprema i tisak sažetaka", 
  "Organizacija događanja tijekom konferencije", "Izrada promidžbenih materijala", "Priprema i potpisivanje certifikata", 
  "Finalne pripreme za dan konferencije", "Koordinacija volontera", "Evaluacija konferencije i izrada izvješća"),
  c(15, 7, 14, 10, 20, 7, 10, 15, 7, 5, 20, 7, 10, 15, 10, 60, 120, 5, 20, 20, 15, 20, 15, 40, 30, 20, 10, 7, 10, 15),
  c(10, 5, 10, 7, 15, 5, 7, 12, 4, 3, 12, 6, 7, 12, 7, 50, 100, 3, 15, 17, 9, 13, 11, 30, 23, 16,  7, 5, 8, 13),
  c(5, 3, 2, 5, 10, 3, 5, 8, 3, 1, 10, 3, 5, 7, 5, 45, 90, 1, 10, 10, 7, 10, 7, 25, 20, 10, 5, 3, 5, 7),
  c(NA, "1", "2", 
   "3", "1,3","1,3",
   "6","1,3,4,5","8",
   "1,5,7,8","5,8,10","9",
   "4,5,6,7,10,11,12","4,12","4,12",
   "7,13,15","8","8,12,13",
   "8","8, 10","20",
   "5,11","4,5,6,7,9,10,11,16,21","23",
   "1,22,23","23","23",
   "23,24,25,26","25,28","17,25,27,28,29"))

colnames(konferencija) <- c("Redni broj", "Aktivnost", "Pesimisticno trajanje", "Ocekivano trajanje", "Optimisticno trajanje", "Neposredni prethodnici")

#Pregledni ispis podataka koji su nam trenutno potrebni
konf <- as.table(konferencija[,c(1,2,4,6)])
konf

##    Redni broj Aktivnost                                      Ocekivano trajanje
## A  1          Odluka o organizaciji konferencije             10                
## B  2          Formiranje organizacijskog odbora              5                 
## C  3          Izbor Predsjednika organizacijskog odbora      10                
## D  4          Uspostava kanala komunikacije                  7                 
## E  5          Odabir mjesta i datuma te provjera dostupnosti 15                
## F  6          Definiranje formata radova                     5                 
## G  7          Postavljanje recenzentskog postupka            7                 
## H  8          Izrada financijskog proračuna                  12                
## I  9          Definiranje iznosa kotizacije                  4                 
## J  10         Utvrđivanje važnih datuma                      3                 
## K  11         Kontaktiranje pozvanih izlagača                12                
## L  12         Objava informacija o uplati kotizacije         6                 
## M  13         Izrada i slanje poziva za sudjelovanje         7                 
## N  14         Promocija konferencije online                  12                
## O  15         Uspostava registracijskog obrasca              7                 
## P  16         Proces recenzije radova                        50                
## Q  17         Praćenje financijskog stanja                   100               
## R  18         Dostava ponuda za uplatu kotizacije            3                 
## S  19         Priprema za traženje sredstava od Ministarstva 15                
## T  20         Kontaktiranje sponzora konferencije            17                
## U  21         Ugovaranje s donatorima/sponzorima             9                 
## V  22         Organizacija smještaja za keynote govornike    13                
## W  23         Izrada programa konferencije                   11                
## X  24         Priprema i tisak sažetaka                      30                
## Y  25         Organizacija događanja tijekom konferencije    23                
## Z  26         Izrada promidžbenih materijala                 16                
## A1 27         Priprema i potpisivanje certifikata            7                 
## B1 28         Finalne pripreme za dan konferencije           5                 
## C1 29         Koordinacija volontera                         8                 
## D1 30         Evaluacija konferencije i izrada izvješća      13                
##    Neposredni prethodnici
## A                        
## B  1                     
## C  2                     
## D  3                     
## E  1,3                   
## F  1,3                   
## G  6                     
## H  1,3,4,5               
## I  8                     
## J  1,5,7,8               
## K  5,8,10                
## L  9                     
## M  4,5,6,7,10,11,12      
## N  4,12                  
## O  4,12                  
## P  7,13,15               
## Q  8                     
## R  8,12,13               
## S  8                     
## T  8, 10                 
## U  20                    
## V  5,11                  
## W  4,5,6,7,9,10,11,16,21 
## X  23                    
## Y  1,22,23               
## Z  23                    
## A1 23                    
## B1 23,24,25,26           
## C1 25,28                 
## D1 17,25,27,28,29

#spremanje konferencija_df kao podatkovni okvir 
konferencija_df<-as.data.frame(konferencija)

konferencija_df sadrži sve potrebne podatke.

Najčešće se započinje sa sličnim zapisom uvezenim iz csv ili excel datoteke. No, za daljnju analizu potrebno je izvršiti prilagodbu podataka. U nastavku će se koristiti paketi igraph (Csárdi et al. 2023), criticalpath (Rosa, Santos, and Marques 2021) i critpath (Kucharski 2023). Svaki od tih paketa pri analizi iziskuje malu prilagodbu podataka.

Neposredni_prethodnici_list <- konferencija_df$`Neposredni prethodnici`
Neposredni_prethodnici_list <- lapply(Neposredni_prethodnici_list, function(x) {
  if (is.na(x)) {
   return(NULL)
  } else {
   return(as.integer(unlist(strsplit(as.character(x), ","))))
  }
})

# Kreiranje dataframea s bridovima
edges_df <- data.frame(from = integer(), to = integer())

for(i in 1:30) {
  aktivnost <- konferencija_df$`Redni broj`[i]
  prethodnici <- Neposredni_prethodnici_list[[i]]
  
  if (!is.null(prethodnici)) {  # Provjeravamo da prethodnici nisu NULL
   for(j in prethodnici) {
     edges_df <- rbind(edges_df, data.frame(from = prethodnici, to = aktivnost))
   }
  }
}

edges_df <- unique(edges_df)

if(!require(igraph)) install.packages("igraph")
library(igraph)

g <- graph_from_data_frame(edges_df, directed=TRUE, vertices=konferencija_df)

plot(g, 
    vertex.size=15, 
    #vertex.label=g$v, 
    #vertex.label.cex=0.7, 
    edge.arrow.size=0.5, 
    layout=layout_with_kk)

if(!require(criticalpath)) install.packages("criticalpath")

## Loading required package: criticalpath

library(criticalpath)

konferencija_df$`Redni broj` <- as.integer(konferencija_df$`Redni broj`)
konferencija_df$`Ocekivano trajanje` <- as.integer(konferencija_df$`Ocekivano trajanje`)
edges_df$from <- as.integer(edges_df$from)
edges_df$to <- as.integer(edges_df$to)

# Kreiranje taskova i njihovih zavisnosti
raspored <- sch_new() %>%
  sch_add_activities(
   id = konferencija_df$`Redni broj`,
   name = konferencija_df$Aktivnost,
   duration = konferencija_df$`Ocekivano trajanje`
  ) %>%
  sch_add_relations(
   from = edges_df$from,
   to = edges_df$to
  ) %>%
  sch_plan()

print("Ukupno trajanje:")

## [1] "Ukupno trajanje:"

sch_duration(raspored)

## [1] 191

#Uređivanje prikaza rješenja
aktivnosti <- sch_activities(raspored)
prikaz <- as.table(cbind(aktivnosti$id, aktivnosti$name, aktivnosti$duration, aktivnosti$critical, aktivnosti$free_float, 
                   aktivnosti$early_start, aktivnosti$early_finish, aktivnosti$late_start, aktivnosti$late_finish))
colnames(prikaz) <- c("ID", "Aktivnost", "Trajanje", "Kritična aktivnost", "Free Float", 
                 "Najraniji početak", "Najraniji završetak", "Najkasniji početak", "Najkasniji završetak")
prikaz

##    ID Aktivnost                                      Trajanje
## A  1  Odluka o organizaciji konferencije             10      
## B  2  Formiranje organizacijskog odbora              5       
## C  3  Izbor Predsjednika organizacijskog odbora      10      
## D  4  Uspostava kanala komunikacije                  7       
## E  5  Odabir mjesta i datuma te provjera dostupnosti 15      
## F  6  Definiranje formata radova                     5       
## G  7  Postavljanje recenzentskog postupka            7       
## H  8  Izrada financijskog proračuna                  12      
## I  9  Definiranje iznosa kotizacije                  4       
## J  10 Utvrđivanje važnih datuma                      3       
## K  11 Kontaktiranje pozvanih izlagača                12      
## L  12 Objava informacija o uplati kotizacije         6       
## M  13 Izrada i slanje poziva za sudjelovanje         7       
## N  14 Promocija konferencije online                  12      
## O  15 Uspostava registracijskog obrasca              7       
## P  16 Proces recenzije radova                        50      
## Q  17 Praćenje financijskog stanja                   100     
## R  18 Dostava ponuda za uplatu kotizacije            3       
## S  19 Priprema za traženje sredstava od Ministarstva 15      
## T  20 Kontaktiranje sponzora konferencije            17      
## U  21 Ugovaranje s donatorima/sponzorima             9       
## V  22 Organizacija smještaja za keynote govornike    13      
## W  23 Izrada programa konferencije                   11      
## X  24 Priprema i tisak sažetaka                      30      
## Y  25 Organizacija događanja tijekom konferencije    23      
## Z  26 Izrada promidžbenih materijala                 16      
## A1 27 Priprema i potpisivanje certifikata            7       
## B1 28 Finalne pripreme za dan konferencije           5       
## C1 29 Koordinacija volontera                         8       
## D1 30 Evaluacija konferencije i izrada izvješća      13      
##    Kritična aktivnost Free Float Najraniji početak Najraniji završetak
## A  TRUE               0          0                 10                 
## B  TRUE               0          10                15                 
## C  TRUE               0          15                25                 
## D  FALSE              8          25                32                 
## E  TRUE               0          25                40                 
## F  FALSE              0          25                30                 
## G  FALSE              15         30                37                 
## H  TRUE               0          40                52                 
## I  FALSE              0          52                56                 
## J  TRUE               0          52                55                 
## K  TRUE               0          55                67                 
## L  FALSE              0          56                62                 
## M  TRUE               0          67                74                 
## N  FALSE              117        62                74                 
## O  FALSE              5          62                69                 
## P  TRUE               0          74                124                
## Q  FALSE              26         52                152                
## R  FALSE              114        74                77                 
## S  FALSE              124        52                67                 
## T  FALSE              0          55                72                 
## U  FALSE              43         72                81                 
## V  FALSE              55         67                80                 
## W  TRUE               0          124               135                
## X  TRUE               0          135               165                
## Y  FALSE              7          135               158                
## Z  FALSE              14         135               151                
## A1 FALSE              36         135               142                
## B1 TRUE               0          165               170                
## C1 TRUE               0          170               178                
## D1 TRUE               0          178               191                
##    Najkasniji početak Najkasniji završetak
## A  0                  10                  
## B  10                 15                  
## C  15                 25                  
## D  33                 40                  
## E  25                 40                  
## F  40                 45                  
## G  45                 52                  
## H  40                 52                  
## I  57                 61                  
## J  52                 55                  
## K  55                 67                  
## L  61                 67                  
## M  67                 74                  
## N  179                191                 
## O  67                 74                  
## P  74                 124                 
## Q  78                 178                 
## R  188                191                 
## S  176                191                 
## T  98                 115                 
## U  115                124                 
## V  129                142                 
## W  124                135                 
## X  135                165                 
## Y  142                165                 
## Z  149                165                 
## A1 171                178                 
## B1 165                170                 
## C1 170                178                 
## D1 178                191

#Uređivanje prikaza rješenja
krit_akt<- sch_critical_activities(raspored)
krit_ak<- cbind(krit_akt$id, krit_akt$name, krit_akt$duration)
krit_ak <- as.table(krit_ak)
colnames(krit_ak) <- c("ID", "Aktivnost", "Trajanje")
krit_ak

##   ID Aktivnost                                      Trajanje
## A 1  Odluka o organizaciji konferencije             10      
## B 2  Formiranje organizacijskog odbora              5       
## C 3  Izbor Predsjednika organizacijskog odbora      10      
## D 5  Odabir mjesta i datuma te provjera dostupnosti 15      
## E 8  Izrada financijskog proračuna                  12      
## F 10 Utvrđivanje važnih datuma                      3       
## G 11 Kontaktiranje pozvanih izlagača                12      
## H 13 Izrada i slanje poziva za sudjelovanje         7       
## I 16 Proces recenzije radova                        50      
## J 23 Izrada programa konferencije                   11      
## K 24 Priprema i tisak sažetaka                      30      
## L 28 Finalne pripreme za dan konferencije           5       
## M 29 Koordinacija volontera                         8       
## N 30 Evaluacija konferencije i izrada izvješća      13

plot(sch_xy_gantt_matrix(raspored))

Ukupno trajanje projekta organizacije konferencije iznosi 191 dana. Kritični put je niz aktivnosti koje direktno utječu na ukupno trajanje projekta, odnosno bilo kakvo kašnjenje tih aktivnosti rezultirat će produženjem ukupnog trajanja projekta. Aktivnosti na kritičnom putu uključuju “Odluku o organizaciji konferencije”, “Formiranje organizacijskog odbora”, “Izbor Predsjednika organizacijskog odbora”, “Odabir mjesta i datuma te provjera dostupnosti”, “Izradu financijskog proračuna”, “Utvrđivanje važnih datuma”, “Kontaktiranje pozvanih izlagača”, “Izradu i slanje poziva za sudjelovanje”, “Proces recenzije radova”, “Izradu programa konferencije”, “Pripremu i tisak sažetaka”, “Finalne pripreme za dan konferencije”, “Koordinaciju volontera” i “Evaluaciju konferencije i izradu izvješća”.

Vrijednost “slack” (slobodno vrijeme) ukazuje na to koliko vremena određena aktivnost može kasniti a da se ukupno trajanje projekta ne produži. Na primjer, “Uspostava kanala komunikacije” ima slack od 8 dana, što znači da ova aktivnost može kasniti do 8 dana a da to ne utječe na ukupno trajanje projekta. Aktivnosti na kritičnom putu imaju nula dana slacka, što znači da ne smiju kasniti ako se želi održati procijenjeno ukupno trajanje organizacije konferencije.

Osim toga, najraniji i najkasniji početak i završetak svake aktivnosti ukazuje na vremenski okvir unutar kojeg aktivnost može početi i završiti bez utjecaja na ukupno trajanje projekta. Na primjer, “Uspostava registracijskog obrasca” može početi između 62. i 67. dana, a završiti između 69. i 74. dana.

Za uspješno upravljanje ovim projektom, ključno je pažljivo pratiti aktivnosti na kritičnom putu i osigurati da one ne kasne kako bi se projekt uspješno završio unutar predviđenog vremenskog okvira.

Organizacija znanstvene konferencije je značajan pothvat koji ima direktne ekonomske implikacije. Kritični put, koji predstavlja niz aktivnosti direktno utječe na ukupno trajanje projekta i osnova je za daljnje iizračune ekonomske efikasnosti.

Ako se aktivnosti na kritičnom putu ne izvršavaju prema planu, mogući su dodatni troškovi. Na primjer, kašnjenje u odabiru mjesta može rezultirati višim cijenama najma ili čak nedostupnošću željenog prostora, što može povećati ukupne troškove. Osim toga, kašnjenje u procesu recenzije radova ili izradi programa može rezultirati smanjenim interesom sudionika, što bi moglo dovesti do smanjenja prihoda od kotizacija.

Vrijednost “slack” za određene aktivnosti pruža određenu fleksibilnost u upravljanju resursima. Aktivnosti s višim slackom mogu se prilagoditi bez utjecaja na ukupno trajanje, što omogućava bolju alokaciju resursa prema prioritetima i potrebama.

Konačno, precizno definirani vremenski okviri za početak i završetak svake aktivnosti omogućuju bolje planiranje i koordinaciju, što može rezultirati smanjenjem troškova.

Ukupno gledano, pažljivo upravljanje i praćenje kritičnog puta te iskorištavanje fleksibilnosti pružene vrijednostima “slack” ključni su za minimiziranje troškova i optimizaciju ekonomske učinkovitosti organizacije konferencije. Uz to, pravovremena izvedba značajno povećava reputaciju i povjerenje sudionika, što može imati dugoročne ekonomske koristi za organizatore.

U nastavku se prikazuje rješavanje koristeći još jedan paket.

if(!require(critpath)) install.packages("critpath")

## Loading required package: critpath

library(critpath)

#potrebno je pripremiti podatke za korištenje naredbi iz ovog paketa
#na kraju se dodaje još jedan čvor kako bi se moglo prikazati trajanje 30. aktivnosti
Start_node <- edges_df$from
Start_node[length(Start_node) + 1] <- 30
End_node <- edges_df$to
End_node[length(End_node) + 1] <- 31
Activity <- edges_df$from
Activity[length(Activity) + 1] <- 30
Duration <- numeric(length(Activity))

for (i in 1:length(Activity)) {
  match_index <- which(Activity[i] == konferencija_df$`Redni broj`)
  if (length(match_index) == 1) {
   Duration[i] <- konferencija_df$`Ocekivano trajanje`[match_index]
  }
}

data_konf <- cbind(Start_node, End_node, Activity, Duration)
colnames(data_konf) <- c("Start_node", "End_node", "Activity", "Duration")
data_konf <- as.data.frame(data_konf)

critical<-solve_pathAOA(data_konf, deterministic=TRUE)

## Completion time:  191

name <- critical$schedule$Name
time <- critical$schedule$Time
ESij <- critical$schedule$ESij
LSij <- critical$schedule$LSij
EFij <- critical$schedule$EFij
LFij <- critical$schedule$LFij
Crit <- critical$schedule$Crit
TSij <- critical$schedule$TSij

rez_crit <- as.data.frame(cbind(name, time, ESij, LSij, EFij, LFij, Crit, TSij))
rez_crity <- subset(rez_crit, Crit == "*")
colnames(rez_crity) <- c("Name", "Time", "ESij", "LSij", "EFij", "LFij", "Crit", "TSij")
rez_crity

##    Name Time ESij LSij EFij LFij Crit TSij
## 1     1   10    0    0   10   10    *    0
## 7     2    5   10   10   15   15    *    0
## 9     3   10   15   15   25   25    *    0
## 17    5   15   25   25   40   40    *    0
## 31    8   12   40   40   52   52    *    0
## 39   10    3   52   52   55   55    *    0
## 43   11   12   55   55   67   67    *    0
## 50   13    7   67   67   74   74    *    0
## 53   16   50   74   74  124  124    *    0
## 58   23   11  124  124  135  135    *    0
## 63   24   30  135  135  165  165    *    0
## 69   28    5  165  165  170  170    *    0
## 71   29    8  170  170  178  178    *    0
## 72   30   13  178  178  191  191    *    0

rez_crit <- as.data.frame(cbind(name, time, ESij, LSij, EFij, LFij, Crit, TSij))
rez_not_crit <- subset(rez_crit, Crit != "*")
colnames(rez_not_crit) <- c("Name", "Time", "ESij", "LSij", "EFij", "LFij", "Crit", "TSij")
rez_not_crit

##    Name Time ESij LSij EFij LFij Crit TSij
## 2     1   10    0   15   10   25        15
## 3     1   10    0   30   10   40        30
## 4     1   10    0   30   10   40        30
## 5     1   10    0   42   10   52        42
## 6     1   10    0  132   10  142       132
## 8     3   10   15   23   25   33         8
## 10    3   10   15   30   25   40        15
## 11    3   10   15   30   25   40        15
## 12    4    7   25   33   32   40         8
## 13    4    7   25   60   32   67        35
## 14    4    7   25  184   32  191       159
## 15    4    7   25   60   32   67        35
## 16    4    7   25  117   32  124        92
## 18    5   15   25   37   40   52        12
## 19    5   15   25   40   40   55        15
## 20    5   15   25   52   40   67        27
## 21    5   15   25  114   40  129        89
## 22    5   15   25  109   40  124        84
## 23    6    5   25   40   30   45        15
## 24    6    5   25   62   30   67        37
## 25    6    5   25  119   30  124        94
## 26    7    7   30   45   37   52        15
## 27    7    7   30   60   37   67        30
## 28    7    7   30   67   37   74        37
## 29    7    7   30  117   37  124        87
## 30    8   12   40   45   52   57         5
## 32    8   12   40   43   52   55         3
## 33    8   12   40   66   52   78        26
## 34    8   12   40  179   52  191       139
## 35    8   12   40  179   52  191       139
## 36    8   12   40   86   52   98        46
## 37    9    4   52   57   56   61         5
## 38    9    4   52  120   56  124        68
## 40   10    3   52   64   55   67        12
## 41   10    3   52   95   55   98        43
## 42   10    3   52  121   55  124        69
## 44   11   12   55  117   67  129        62
## 45   11   12   55  112   67  124        57
## 46   12    6   56   61   62   67         5
## 47   12    6   56  185   62  191       129
## 48   12    6   56   61   62   67         5
## 49   12    6   56  185   62  191       129
## 51   13    7   67  184   74  191       117
## 52   15    7   62   67   69   74         5
## 54   17  100   52   78  152  178        26
## 55   20   17   55   98   72  115        43
## 56   21    9   72  115   81  124        43
## 57   22   13   67  129   80  142        62
## 59   23   11  124  131  135  142         7
## 60   23   11  124  138  135  149        14
## 61   23   11  124  160  135  171        36
## 62   23   11  124  154  135  165        30
## 64   25   23  135  142  158  165         7
## 65   25   23  135  147  158  170        12
## 66   25   23  135  155  158  178        20
## 67   26   16  135  149  151  165        14
## 68   27    7  135  171  142  178        36
## 70   28    5  165  173  170  178         8

plot_graphAOA(data_konf)

## Warning: The `x` argument of `as_tibble.matrix()` must have unique column names if
## `.name_repair` is omitted as of tibble 2.0.0.
## ℹ Using compatibility `.name_repair`.
## ℹ The deprecated feature was likely used in the DiagrammeR package.
##   Please report the issue at
##   <https://github.com/rich-iannone/DiagrammeR/issues>.
## This warning is displayed once every 8 hours.
## Call `lifecycle::last_lifecycle_warnings()` to see where this warning was
## generated.

plot_graphAOA(data_konf, solved = critical)

Jedan dio inicijalno zapisanih podataka nije još iskorišten. Radi se o optimističnoj i pesimističnoj procjeni trajanja vremena završetka. Ako bismo i te podatke htjeli uzeti u obzir, trebamo koristiti stohastičku verziju. Zapravo se radi o PERT/CPM metodi, koja uzima u obzir neizvjesnost.

if(!require(critpath)) install.packages("critpath")
library(critpath)

head(data_konf)

##   Start_node End_node Activity Duration
## 1          1        2        1       10
## 2          2        3        2        5
## 3          3        4        3       10
## 4          1        5        1       10
## 5          3        5        3       10
## 6          1        6        1       10

#dodavanje podataka o optimističnom i pesimističnom vremenu
Optimistic <-numeric(length(data_konf$Activity))
Pesimistic <-numeric(length(data_konf$Activity))

for (i in 1:length(Activity)) {
  match_index <- which(Activity[i] == konferencija_df$`Redni broj`)
  if (length(match_index) == 1) {
   Optimistic[i] <- konferencija_df$`Optimisticno trajanje`[match_index]
  }
}

for (i in 1:length(Activity)) {
  match_index <- which(Activity[i] == konferencija_df$`Redni broj`)
  if (length(match_index) == 1) {
   Pesimistic[i] <- konferencija_df$`Pesimisticno trajanje`[match_index]
  }
}

#kreiranje novog df-a s odgovarajućim poretkom varijabli
data_konf2 <- cbind(from=data_konf$Start_node, to=data_konf$End_node,
               label=data_konf$Activity, opt_time= Optimistic, 
               likely_time=data_konf$Duration, pes_time=Pesimistic)
data_konf2 <- as.data.frame(data_konf2)
str(data_konf2)

## 'data.frame':    72 obs. of  6 variables:
##  $ from       : chr  "1" "2" "3" "1" ...
##  $ to         : chr  "2" "3" "4" "5" ...
##  $ label      : chr  "1" "2" "3" "1" ...
##  $ opt_time   : chr  "5" "3" "2" "5" ...
##  $ likely_time: chr  "10" "5" "10" "10" ...
##  $ pes_time   : chr  "15" "7" "14" "15" ...

data_konf2 <- sapply(data_konf2, function(x) as.numeric(x))
data_konf2 <- as.data.frame(data_konf2)
str(data_konf2)

## 'data.frame':    72 obs. of  6 variables:
##  $ from       : num  1 2 3 1 3 1 3 6 1 3 ...
##  $ to         : num  2 3 4 5 5 6 6 7 8 8 ...
##  $ label      : num  1 2 3 1 3 1 3 6 1 3 ...
##  $ opt_time   : num  5 3 2 5 2 5 2 3 5 2 ...
##  $ likely_time: num  10 5 10 10 10 10 10 5 10 10 ...
##  $ pes_time   : num  15 7 14 15 14 15 14 7 15 14 ...

critp_stohastic<-solve_pathAOA(data_konf2, deterministic=FALSE)

## Expected compl. time distribution: N( 192.1667 , 2.867442 )

critp_stohastic$ComplTi

## [1] 192.1667

critp_stohastic$SDevTi

## [1] 2.867442

critp_stohastic$CritAct

## [1] "5"  "10" "11" "23" "28"

head(critp_stohastic$schedule, 10)

##    Name      Time       Var ESij         LSij     EFij      LFij         TSij
## 1     1 10.000000 2.7777778    0 1.776357e-15 10.00000  10.00000 1.776357e-15
## 2     1 10.000000 2.7777778    0 1.433333e+01 10.00000  24.33333 1.433333e+01
## 3     1 10.000000 2.7777778    0 2.900000e+01 10.00000  39.00000 2.900000e+01
## 4     1 10.000000 2.7777778    0 2.933333e+01 10.00000  39.33333 2.933333e+01
## 5     1 10.000000 2.7777778    0 4.116667e+01 10.00000  51.16667 4.116667e+01
## 6     1 10.000000 2.7777778    0 1.333333e+02 10.00000 143.33333 1.333333e+02
## 7     2  5.000000 0.4444444   10 1.000000e+01 15.00000  15.00000 1.776357e-15
## 8     3  9.333333 4.0000000   15 2.283333e+01 24.33333  32.16667 7.833333e+00
## 9     3  9.333333 4.0000000   15 1.500000e+01 24.33333  24.33333 1.776357e-15
## 10    3  9.333333 4.0000000   15 2.966667e+01 24.33333  39.00000 1.466667e+01
##    Crit
## 1      
## 2      
## 3      
## 4      
## 5      
## 6      
## 7      
## 8      
## 9      
## 10

plot_graphAOA(data_konf2, solved=critp_stohastic)

PERT/CPM metoda je razvijena kako bi pružila menadžerima sredstva za procjenu vjerojatnosti dovršetka projekta unutar određenog vremenskog okvira, te omogućila identifikaciju kritičnih aktivnosti koje mogu utjecati na to trajanje. U kontekstu organizacije konferencije, ekonomske implikacije su mnogostruke.

Korištenjem PERT/CPM metode za raspored organizacije konferencije, dobili smo nekoliko ključnih rezultata. Prvo, kritične aktivnosti su 5, 10, 11, 23 i 28 i one direktno utječu na trajanje cijelog projekta. Ako bilo koja od ovih aktivnosti kasni, cijeli projekt će kasniti. Osim toga, bilo kakvo kašnjenje u tim aktivnostima može rezultirati dodatnim troškovima, poput penala za kasno bukiranje mjesta održavanja ili izgubljenih prihoda zbog manje registracija.

Očekivano trajanje: 192.17 dana. Ovo predstavlja procjenu koliko dana će potrajati da se organizacija konferencije završi, uzimajući u obzir sve aktivnosti i njihova očekivane trajanja. Ako se projekt ne završi unutar tog vremenskog okvira, mogući su dodatni troškovi. Na primjer, kašnjenje može dovesti do potrebe za dodatnim radnim satima ili angažiranjem dodatnih resursa kako bi se posao završio na vrijeme. S druge strane, ako se projekt završi prije očekivanog trajanja, može rezultirati smanjenjem ukupnih troškova, kao što su smanjeni troškovi za ljudske resurse ili najam prostora. Ukupno gledano, precizna procjena trajanja projekta i prepoznavanje kritičnih aktivnosti pružaju temelj za ekonomsku optimizaciju. Pravilnim raspoređivanjem resursa i pravovremenim izvršavanjem kritičnih aktivnosti, organizatori mogu minimizirati troškove i maksimizirati prihod od konferencije.

Standardna devijacija: 2.87 dana. Očekivano trajanje uz standardnu devijaciju stvara pretpostavku za daljnje ispitivanje vjerojatnosti trajanja projekta do određenog roka. Pritom se pretpostavlja normalna distribucija vjerojatnosti, naznačena i u rješenju, N(192.1667 , 2.867442). Distibuciju vjerojatnosti trajanja projekta možemo i grafički prikazati.

ocekivano_trajanje <- 192.1667
standardna_devijacija <- 2.867442

#funkcija dnorm vraća gustoću funkcije vjerojatnosti za dane parametre
#ostatak naredbi odnosi se na grafički prikaz
curve(dnorm(x, ocekivano_trajanje, sd=standardna_devijacija), 
     from = ocekivano_trajanje - 4*standardna_devijacija, 
     to = ocekivano_trajanje + 4*standardna_devijacija, 
     xlab = "x", 
     ylab = "Gustoća vjerojatnosti",
     main = "Normalna distribucija N(192.1667, 2.867442)")

grid()

Ovdje možemo iskoristiti i Empirijsko pravilo za dodatne uvide. Sjetite se, Empirijsko pravilo vrijedi za normalnu distribuciju i tumači se pomoću površina pod krivuljom vezanih uz intervale odstupanja 1, 2 i 3 standardne devijacije od prosjeka. Pa se tako unutar intervala od jedne standardne devijacije od prosjeka (prosjek +/- 1 sd) nalazi približno 68.28% podataka. Unutar intervala od dvije standardne devijacije od prosjeka (prosjek +/- 2 sd) nalazi 95.44% podataka. Unutar intervala od tri standardne devijacije od prosjeka nalazi se približno 99.7% podataka.

ocekivano_trajanje <- 192.1667
standardna_devijacija <- 2.867442

# Grafički prikaz osnovne distribucije
curve(dnorm(x, mean=ocekivano_trajanje, sd=standardna_devijacija), 
     from = ocekivano_trajanje - 4*standardna_devijacija, 
     to = ocekivano_trajanje + 4*standardna_devijacija, 
     xlab = "x", 
     ylab = "Gustoća vjerojatnosti",
     main = "Normalna distribucija s označenim standardnim devijacijama")

# Dodajemo površine
for (i in 1:3) {
  x_vals <- seq(ocekivano_trajanje - i*standardna_devijacija, ocekivano_trajanje + i*standardna_devijacija, length.out = 100)
  y_vals <- dnorm(x_vals, mean=ocekivano_trajanje, sd=standardna_devijacija)
  polygon(c(ocekivano_trajanje - i*standardna_devijacija, x_vals, ocekivano_trajanje + i*standardna_devijacija),
        c(0, y_vals, 0),
        col = rgb(0.8, 0.8, 0.8, 0.2 / i), border = NA)
}

# Ponovno crtamo osnovnu krivulju da bude iznad površina
curve(dnorm(x, mean=ocekivano_trajanje, sd=standardna_devijacija), 
     from = ocekivano_trajanje - 4*standardna_devijacija, 
     to = ocekivano_trajanje + 4*standardna_devijacija, 
     add = TRUE)

grid()

Najtamnija nijansa sive boje na grafu odnosi se na interval odstupanja jedne standardne devijacije od prosjeka. Ako bismo pokušaj organizacije konferencije s ovim parametrima ponavljali u beskonačnost, u približno 68% slučajeva vrijeme izvršenja bilo bi između 189.2993 i 195.0341 dana. To možemo promatrati i iz druge perspektive, postoji vjerojatnost od približno 68% da će organizacija konferencije trajati između 189.2993 i 195.0341 dana. Sukladno tome, može se zaključiti da postoji približno 95.44% vjerojatnost da će organizacija konferencije trajati između 186.4318 i 197.9016 dana. Naposlijetku, gotovo je sigurno (99.7%) da će organizacija konferencije biti provedena u intervalu od 183.5644 i 200.769 dana.

Da bismo utvrdili vjerojatnost da će organizacija konferencije biti završena, npr. točno u 195 dana i 200 dana, koristimo normalnu distribuciju s očekivanim trajanjem i standardnom devijacijom.

vjerojatnost_200_dana <- pnorm(195, mean=ocekivano_trajanje, sd=standardna_devijacija)
vjerojatnost_300_dana <- pnorm(200, mean=ocekivano_trajanje, sd=standardna_devijacija)

cat("Vjerojatnost da će organizacija konferencije biti gotova u 195 dana je", vjerojatnost_200_dana*100, "%.")

## Vjerojatnost da će organizacija konferencije biti gotova u 195 dana je 83.84465 %.

cat(" Vjerojatnost da će organizacija konferencije biti gotova u 200 dana je", vjerojatnost_300_dana*100, "%.")

##  Vjerojatnost da će organizacija konferencije biti gotova u 200 dana je 99.68506 %.

Možete još samostalno istražiti primjenu LESS metode, koja je također podržana u paketu critpath.

Slučaj: Optimizacija raspodjele usluga distribuirane mreže

Alokacija resursa/elementi problema pridruživanja/aspekti rasporeda

Ovo je problem maksimizacije dobiti s elementima problema pridruživanja, elementima problema raspodjele ili paketiranja (Bin Packing Problem) s višestrukim ograničenjima i aspektima rasporeda (Scheduling Problem). Spada u nešto naprednije problemske slučajeve (ali ne i teške).

U digitalnom svijetu, distribuirane mreže igraju ključnu ulogu u osiguravanju brze i pouzdane komunikacije između različitih točaka. Tvrtka X je na čelu ove industrije, upravljajući s mrežom koja koristi čvorove ili servere kako bi pružala niz usluga svojim klijentima. Uz široku paletu usluga kao što su pohrana podataka, računalna snaga, mrežno povezivanje, analitika podataka i sigurnost i zaštita, tvrtka se suočava s izazovom optimizacije raspodjele ovih usluga među svojim čvorovima.

Svaka usluga ima svoju specifičnu cijenu i trošak, a svaka se razlikuje i po potražnji i pragovima performansi. Izazov je u tome kako maksimizirati dobit pružanjem ovih usluga, uzimajući u obzir različite faktore i ograničenja. Na primjer, dok usluga pohrane podataka osigurava da podaci ostanu dostupni čak i ako jedan čvor padne, usluga računalne snage omogućava klijentima pristup računalnoj snazi za obradu podataka. Svaki čvor može podržati najviše četiri usluge, a tvrtka ima 5 čvorova.

Usluga 1 - Pohrana podataka: Ova usluga omogućuje klijentima da pohranjuju, dohvaćaju i upravljaju svojim podacima unutar distribuirane mreže. Pohrana podataka je otporna na kvarove, što znači da čak i ako jedan čvor padne, podaci ostaju dostupni.
Usluga 2 - Računalna snaga (Compute): Klijentima se pruža pristup računalnoj snazi za obradu podataka, vođenje aplikacija i drugih računalnih operacija.
Usluga 3 - Mrežno povezivanje: Ova usluga omogućuje klijentima povezivanje svojih resursa i aplikacija s distribuiranom mrežom, nudeći visoku propusnost i nisku latenciju.
Usluga 4 - Analitika podataka: Pruža klijentima mogućnost analize svojih podataka unutar distribuirane mreže, koristeći alate za obradu velikih podataka i strojno učenje.
Usluga 5 - Sigurnost i zaštita: Ova usluga štiti podatke i aplikacije klijenta unutar distribuirane mreže, pružajući sigurnosne značajke kao što su firewall, detekcija prijetnji i enkripcija.

Poznati su sljedeći parametri vezani uz navedene usluge: - Usluga 1: Cijena = $150, Trošak = $50, Maksimalna potražnja = 80, Maksimum performansi= 40 - Usluga 2: Cijena = $100, Trošak = $40, Maksimalna potražnja = 100, Maksimum performansi= 50 - Usluga 3: Cijena = $200, Trošak = $70, Maksimalna potražnja = 70, Maksimum performansi= 35 - Usluga 4: Cijena = $80, Trošak = $30, Maksimalna potražnja = 110, Maksimum performansi= 55 - Usluga 5: Cijena = $180, Trošak = $60, Maksimalna potražnja = 90, Maksimum performansi= 45

Ograničenje redundancije osigurava otpornost i pouzdanost distribuirane mreže. U praksi, ako jedna usluga na čvoru iz nekog razloga postane nedostupna (npr. zbog kvara na čvoru), druga usluga može preuzeti njezinu funkcionalnost i osigurati kontinuitet usluge. Stoga svaki čvor mora pružati barem dvije različite usluge kako bi se osigurala redundancija i pouzdanost.

U distribuiranim mrežama, neke usluge mogu koristiti slične resurse ili su inače tehnički nespojive kad se izvode na istom čvoru. U ovom konkretnom slučaju, usluga pohrane podataka (Usluga 1) i usluga mrežnog povezivanja (Usluga 3) ne mogu koegzistirati na istom čvoru zbog potencijalnih sukoba u resursima. To može biti rezultat, na primjer, konkurencije za pristup mrežnim komponentama ili posebnih tehničkih specifikacija. Stoga, ako se na čvoru pruža usluga pohrane podataka, usluga mrežnog povezivanja ne može se pružiti na tom istom čvoru i obrnuto.

Optimizacija je ključna kako bi se osiguralo da svaka usluga ne samo da zadovoljava potrebe klijenata, već i da je ekonomski isplativa za tvrtku. Kroz linearno programiranje, tvrtka X može identificirati najbolji način raspodjele usluga kako bi maksimizirala svoju dobit. Pritom mora uzeti u obzir ograničenja kapaciteta za svaki čvor, ograničenja potražnje za svaku uslugu, uvjet da svaka usluga mora biti raspoređena, ograničenja performansi te ograničenja redundancije i preklapanja.

Struktura problema

Za ovu svrhu, možemo koristiti matricu odluke. Svaki element matrice xijxij označava da li čvor i pruža uslugu j ili ne. Dakle, ako čvor i pruža uslugu j, x_ij=1, inače x_ij=0. Tako će biti ukupno 5x5=25 varijabli odluke jer imamo 5 čvorova i 5 različitih usluga.

Varijable odluke:

$x_{ij}$ gdje broj čvorova $i = 1,...,5$ i broj usluga $j = 1,...,5$

Funkcija cilja (maksimizacija dobiti):

$Z = (150-50)(x_{11}+x_{21}+x_{31}+x_{41}+x_{51}) +$ $(100-40)(x_{12}+x_{22}+x_{32}+x_{42}+x_{52}) +$ $(200-70)(x_{13}+x_{23}+x_{33}+x_{43}+x_{53}) +$ $(80-30)(x_{14}+x_{24}+x_{34}+x_{44}+x_{54}) +$ $(180-60)(x_{15}+x_{25}+x_{35}+x_{45}+x_{55})$

Ograničenja:

Kapacitetska ograničenja za svaki čvor:

$x_{11}+x_{12}+x_{13}+x_{14}+x_{15} \leq 4$

$x_{21}+x_{22}+x_{23}+x_{24}+x_{25} \leq 4$

$x_{31}+x_{32}+x_{33}+x_{34}+x_{35} \leq 4$

$x_{41}+x_{42}+x_{43}+x_{44}+x_{45} \leq 4$

$x_{51}+x_{52}+x_{53}+x_{54}+x_{55} \leq 4$

Ograničenje potražnje za svaku uslugu:

$x_{11}+x_{21}+x_{31}+x_{41}+x_{51} \leq 80$

$x_{12}+x_{22}+x_{32}+x_{42}+x_{52} \leq 100$

$x_{13}+x_{23}+x_{33}+x_{43}+x_{53} \leq 70$

$x_{14}+x_{24}+x_{34}+x_{44}+x_{54} \leq 110$

$x_{15}+x_{25}+x_{35}+x_{45}+x_{55} \leq 90$

Svaka usluga mora biti raspoređena na barem jednom čvoru:

$x_{11}+x_{21}+x_{31}+x_{41}+x_{51} > 0$

$x_{12}+x_{22}+x_{32}+x_{42}+x_{52} > 0$

$x_{13}+x_{23}+x_{33}+x_{43}+x_{53} > 0$

$x_{14}+x_{24}+x_{34}+x_{44}+x_{54} > 0$

$x_{15}+x_{25}+x_{35}+x_{45}+x_{55} > 0$

Ograničenje redundancije (svaki čvor mora pružiti najmanje dvije različite usluge):

$x_{11}+x_{12}+x_{13}+x_{14}+x_{15} \geq 2$

$x_{21}+x_{22}+x_{23}+x_{24}+x_{25} \geq 2$

$x_{31}+x_{32}+x_{33}+x_{34}+x_{35} \geq 2$

$x_{41}+x_{42}+x_{43}+x_{44}+x_{45} \geq 2$

$x_{51}+x_{52}+x_{53}+x_{54}+x_{55} \geq 2$

Ograničenja performansi:

$x_{11}+x_{21}+x_{31}+x_{41}+x_{51} \leq 40$

$x_{12}+x_{22}+x_{32}+x_{42}+x_{52} \leq 50$

$x_{13}+x_{23}+x_{33}+x_{43}+x_{53} \leq 35$

$x_{14}+x_{24}+x_{34}+x_{44}+x_{54} \leq 55$

$x_{15}+x_{25}+x_{35}+x_{45}+x_{55} \leq 45$

Uzimajući u obzir moguće preklapanje mreže (ako se na čvoru pruža usluga 1, onda se ne može pružiti usluga 3):

$x_{11}+x_{13} \leq 1$

$x_{21}+x_{23} \leq 1$

$x_{31}+x_{33} \leq 1$

$x_{41}+x_{43} \leq 1$

$x_{51}+x_{53} \leq 1$

Ne može biti dodijeljen dio usluge dijelu čvora:

$x_{ij}=int$

if(!require(lpSolve)) install.packages("lpSolve")
library(lpSolve)

# Definiranje koeficijenata funkcije cilja
f.obj <- c(100, 60, 130, 50, 120, 100, 60, 130, 50, 120, 100, 60, 130, 50, 120, 100, 60, 130, 50, 120, 100, 60, 130, 50, 120)

# Matrica ograničenja
f.con <- matrix(c(# Kapacitetska ograničenja za čvorove
  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,
  0, 0, 0, 0, 0, 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, 0, 0, 0, 0, 0, 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, 0, 0, 0, 0, 0, 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, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1,

  # Ograničenja potražnje za usluge
  1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0,
  0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0,
  0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0,
  0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0,
  0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1,

  # Svaka usluga mora biti raspoređena na barem jednom čvoru
  1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0,
  0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0,
  0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0,
  0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0,
  0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1,

  # Ograničenje redundancije 
  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,
  0, 0, 0, 0, 0, 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, 0, 0, 0, 0, 0, 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, 0, 0, 0, 0, 0, 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, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1,
  
  #ograničenje performansi
  1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0,
  0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0,
  0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0,
  0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0,
  0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1,
  
  #ograničenje preklapanja
  1, 0, 1, 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, 1, 0, 1, 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, 1, 0, 1, 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, 1, 0, 1, 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, 1, 0, 1, 0, 0), 
            nrow=30, byrow=TRUE)

# Vektor desnih strana ograničenja
f.dir <- c("<=", "<=", "<=", "<=", "<=", "<=", "<=", "<=", "<=", "<=", 
         "<=", "<=", "<=", "<=", "<=", ">=", ">=", ">=", ">=", ">=", 
         ">=", ">=", ">=", ">=", ">=", "<=", "<=", "<=", "<=", "<=")
f.rhs <- c(4, 4, 4, 4, 4, 80, 100, 70, 110, 90, 40, 50, 35, 55, 45, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1)

# Rješavanje LP problema
solution <- lp("max", f.obj, f.con, f.dir, f.rhs, all.int = TRUE)

# Prikaz rezultata
print(solution)

## Success: the objective function is 2130

solution$solution

##  [1] 0 0 1 0 3 0 2 1 0 1 1 0 0 0 3 1 0 0 0 3 0 0 1 2 1

library(ggplot2)
library(lattice)

rjesenje <- matrix(solution$solution, nrow = 5, byrow = TRUE)

#1. graf
levelplot(rjesenje, 
        main="Rješenje vizualizirano kao mrežna tablica",
        xlab="Usluga", ylab="Čvor", 
        scales=list(x=list(rot=0)))

#2. graf
df <- as.data.frame(as.table(rjesenje))

ggplot(df, aes(Var1, Var2)) + 
  geom_tile(aes(fill = Freq), color = "white") +
  scale_fill_gradient(low = "white", high = "blue") +
  theme_minimal() +
  labs(title = "Rješenje vizualizirano kao toplinska karta", x = "Čvor", y = "Usluga")

#3. graf
profit_values <- c(100, 60, 130, 50, 120)
profits_per_node <- rowSums(rjesenje * profit_values)

barplot(profits_per_node, main="Dobit po čvoru", xlab="Čvor", ylab="Dobit", col="lightblue", border="black")

Rješenje dano kroz varijable odluke predstavlja raspodjelu usluga po čvorovima u distribuiranoj mreži tvrtke X. Na osnovu rješenja, možemo zaključiti sljedeće:

Na prvom čvoru pruža se treća usluga (Mrežno povezivanje).
Na drugom čvoru pružaju se pete (Sigurnost i zaštita) i druge usluge (Računalna snaga).
Na trećem čvoru pružaju se druge (Računalna snaga) i četvrte usluge (Analitika podataka), uz dodatnu petu uslugu (Sigurnost i zaštita).
Na četvrtom čvoru pružaju se treća (Mrežno povezivanje) i peta usluga (Sigurnost i zaštita).
Na petom čvoru pružaju se druge (Računalna snaga) i četvrte usluge (Analitika podataka), uz dodatnu prvom uslugom (Pohrana podataka).

Ovaj raspored je optimiziran da osigura maksimalnu dobit za tvrtku uz poštivanje svih navedenih ograničenja. Ukupna dobit tvrtke iznosi 2130 dolara uzimajući u obzir cijene i troškove svake usluge. Optimizacijom raspodjele usluga, tvrtka osigurava najveći mogući povrat na svoje ulaganje u mrežnu infrastrukturu.

Osim ekonomskih koristi, rješenje osigurava da svaki čvor pruža barem dvije različite usluge, čime se osigurava kontinuitet usluge u slučaju kvara na čvoru. Sukob između usluge pohrane podataka i mrežnog povezivanja je riješen tako da se te dvije usluge ne pružaju na istom čvoru, osiguravajući stabilnost mreže i kvalitetu usluge.

Ovim rješenjem tvrtka X ne samo da maksimizira svoj profit, već i osigurava visoku kvalitetu usluge svojim klijentima kroz optimiziranu raspodjelu resursa, dok istovremeno smanjuje rizik od prekida usluge.

Korištena literatura:

Berkelaar, Michel, and et al. 2023. “lpSolve: Interface to ’Lp_solve’ v. 5.5 to Solve Linear/Integer Programs.” https://CRAN.R-project.org/package=lpSolve.

Csárdi, Gábor, Tamás Nepusz, Vincent Traag, Szabolcs Horvát, Fabio Zanini, Daniel Noom, Kirill Müller, Maëlle Salmon, and Chan Zuckerberg. 2023. “Igraph: Network Analysis and Visualization.” https://CRAN.R-project.org/package=igraph.

Garbett, Shawn P, Jeremy Stephens, and Kirill Simonov. 2023. “Yaml: Methods to Convert R Data to YAML and Back.” https://CRAN.R-project.org/package=yaml.

Henningsen, Arne. 2022. “Linprog: Linear Programming / Optimization.” https://CRAN.R-project.org/package=linprog.

Kahle, David, Hadley Wickham, Scott Jackson, and Mikko Korpela. 2023. “Ggmap: Spatial Visualization with Ggplot2.” https://CRAN.R-project.org/package=ggmap.

Konis, Kjell, Florian Schwendinger, and Kurt Hornik. 2023. “lpSolveAPI: R Interface to ’Lp_solve’ Version 5.5.2.0.” https://CRAN.R-project.org/package=lpSolveAPI.

Kucharski, Adam. 2023. “Critpath: Setting the Critical Path in Project Management.” https://cran.r-project.org/web/packages/critpath/index.html.

Pebesma, Edzer. 2023. “Sf: Simple Features for R.” https://CRAN.R-project.org/package=sf.

Pedersen, Thomas Lin. 2022. “Ggraph: An Implementation of Grammar of Graphics for Graphs and Networks.” https://cran.r-project.org/web/packages/ggraph/index.html.

R Core Team, R. Developement Core. 2010. “R: A Language and Environment for Statistical Computing.” (No Title).

Rosa, Rubens Jose, Marcos dos Santos, and Thiago Marques. 2021. “Criticalpath-R Package Implementation of Critical Path.”

Sarkar, Deepayan. 2023. “Lattice: Trellis Graphics for R.” https://CRAN.R-project.org/package=lattice.

Wickham, Hadley, Winston Chang, Lionel Henry, Thomas Lin Pedersen, Kohske Takahashi, Claus Wilke, Kara Woo, Hiroaki Yutani, and Dewey Dunnington. 2023. “Ggplot2: Create Elegant Data Visualisations Using the Grammar of Graphics. R Package Version 3.4.4.” Stata Software Package: College Station, TX, USA, October.

Xie, Yihui, and et al. 2023. “Knitr: A General-Purpose Package for Dynamic Report Generation in R.” https://CRAN.R-project.org/package=knitr.

Primjeri riješenih zadataka - Operacijska istraživanja

Katarina Kostelić

ak. god. 2023./24.

Slučaj: Nabavka opreme

Problem alokacije resursa

Struktura problema:

Slučaj: Proizvodnja super-legura

Problem alokacije resursa

Struktura problema

Slučaj: Proizvodnja PVC stolarije

Problem alokacije resursa

Struktura problema

Slučaj: Izbor medija za oglašavanje

Problem alokacije resursa

Struktura problema

Slučaj: Kupovina ili proizvodnja

Problem alokacije resursa

Struktura problema

Slučaj: Financiranje budućnosti: alternativni izvori financiranja

Problem alokacije resursa

Struktura problema

Slučaj: Transformacija obiteljske kuće u apartmane za odmor

Cjelobrojno programiranje

Struktura problema:

Slučaj: Optimizacija angažmana i produktivnosti zaposlenika kroz inicijative

Problem alokacije resursa/binarne varijable odluke

Struktura problema

Slučaj: dostava proizvoda

Transportni problem

Struktura problema:

Slučaj: Odabir rute

Problem najkraćeg puta

Struktura problema

Slučaj: Ljetne gužve u Istri

Problem maksimalnog protoka

Struktura problema:

Slucaj: Dodjela radnih zadataka

Problem pridruživanja

Struktura problema

Slučaj: Organizacija znanstvene konferencije

Utvrđivanje kritičnog puta/ raspored

Slučaj: Optimizacija raspodjele usluga distribuirane mreže

Alokacija resursa/elementi problema pridruživanja/aspekti rasporeda

Struktura problema