Analiza osjetljivosti
Katarina Kostelić
Analiza osjetljivosti u linearnom programiranju
Do čitanja ove teme, već ste savladali strukturu linearnog programa i sastavljanje iste temeljem opisa slučaja. Osim toga, naučili ste grafičko rješavanje linearnog programa. Potom ste savladali simplex metodu.
Sljedeći je korak naučiti što je dualni program pridružen primalnom programu, zašto postoji i zašto je koristan za menadžersko odlučivanje i analizu osjetljivosti.
Primalni program \(\rightarrow\) Što odlučiti?
Dualni program \(\rightarrow\) Koliko vrijede resursi koji nam omogućuju tu odluku?
Analiza osjetljivosti \(\rightarrow\) Kako se optimum mijenja ako promijenimo resurse ili tržišne parametre?
Napomena: Pojam analiza osjetljivosti u literaturi se koristi šire – od lokalne post-optimalne analize LP-a (što radimo ovdje), pa sve do globalnih/stohastičkih analiza nesigurnosti u kompleksnim modelima. U ovoj jedinici ostajemo u okviru linearnog programiranja i fokusiramo se na post-optimalnu analizu zasnovanu na dualnosti i simplex tablici.
Intro:
Razvoj analize osjetljivosti usko je povezan s razvojem samog linearnog programiranja (LP) i Simplex algoritma. Važne etape razvoja:
- Rane 1940-e: Postavljanje temelja LP-a:
- Problem alokacije resursa postojao je i prije, ali formalne metode rješavanja bile su ograničene. Tijekom Drugog svjetskog rata, potreba za optimizacijom logistike i vojnih operacija potaknula je istraživanja. George B. Dantzig radio je na metodama planiranja za američko ratno zrakoplovstvo.
- Relevantni izvori za kontekst i Dantzigov rani rad: Dantzig (1963) - Uvodna poglavlja; Lenstra et al. (1991).
- 1947: Izum simplex algoritma:
- George B. Dantzig razvija Simplex algoritam. Ovo je bio ključni trenutak. Simplex ne samo da je omogućio pronalaženje optimalnog rješenja za LP probleme, već je njegova konačna tablica inherentno sadržavala informacije potrebne za analizu osjetljivosti.
- Već u ranim fazama razvoja Simplexa, Dantzig i suradnici uočili su da Z-red (redak funkcije cilja) u optimalnoj tablici sadrži informacije o tome kako bi se vrijednost cilja promijenila ako bi se nebazna varijabla nasilno uvela u rješenje (što je temelj za smanjene troškove).
- Primarni izvor za Simplex algoritam i interpretaciju tablice: Dantzig (1963).
- Kasne 1940-e - Rane 1950-e: Razvoj teorije
dualnosti:
- John von Neumann (kroz rad na teoriji igara), Albert W. Tucker, Harold W. Kuhn, David Gale i drugi formaliziraju teoriju dualnosti u linearnom programiranju.
- Ovo je bilo presudno za analizu osjetljivosti jer je dalo ekonomsku interpretaciju brojevima u Simplex tablici. Dualne varijable su prepoznate kao sjene cijena (marginalne vrijednosti) ograničenih resursa. Teorem o jakoj dualnosti (\(Z^*=W^*\)) postao je temelj razumijevanja.
- Postalo je jasno da Z-redak u optimalnoj tablici (ispod početnih slack varijabli) izravno daje optimalne vrijednosti dualnih varijabli (sjene cijena).
- Izvori za matematičke temelje dualnosti: Kuhn & Tucker (1956); Integracija dualnosti s LP i ekonomska interpretacija: Dantzig (1963), Gass (2003), Hadley (1962).
- 1950-e: Rane primjene i potreba za “što-ako”
analizom:
- Kako se LP počeo primjenjivati (npr. u naftnoj industriji, planiranju proizvodnje), korisnici su brzo shvatili da ulazni podaci (cijene, dostupnost resursa) nisu fiksni. Postalo je ključno razumjeti koliko je optimalno rješenje osjetljivo na promjene tih podataka.
- Počinje se razvijati “post-optimalna analiza” – metode za određivanje dopuštenih raspona (allowable ranges) za koeficijente funkcije cilja (\(c_j\)) i desne strane ograničenja (\(b_i\)) unutar kojih trenutna optimalna baza (skup varijabli u rješenju) ostaje optimalna.
- Izvori koji opisuju rane primjene i motivaciju za post-optimalnu analizu: Gass (2003) - Poglavlja o primjenama; Lenstra et al. (1991).
- 1950-e i 1960-e: Uloga računala i formalizacija:
- Pojavom i razvojem računala, rješavanje većih LP problema i izračunavanje analiza osjetljivosti postaje praktično izvedivo.
- Matematički temelji analize osjetljivosti, oslanjajući se na inverznu matricu baze (\(B^{-1}\)), postaju standardni dio udžbenika iz operacijskih istraživanja i linearnog programiranja. Razvijaju se pravila poput “100% pravila” za simultane promjene.
- Klasični udžbenici koji su formalizirali metode analize osjetljivosti: Gass (2003 - rane verzije iz 1958.), Hadley (1962), Dantzig (1963).
- 1970-e do danas: Integracija u softvere (solvere):
- Komercijalni i akademski softverski paketi za LP (kao što su MPSX, LINDO, kasnije CPLEX, Gurobi, pa čak i Excel Solver) počinju standardno uključivati izvještaje o analizi osjetljivosti kao dio izlaza.
- Korisnici više ne moraju ručno interpretirati simpleks tablicu; softver izravno daje sjene cijena, smanjene troškove i dopuštene raspone. Fokus se prebacuje s izračuna na interpretaciju i primjenu rezultata analize osjetljivosti u donošenju menadžerskih odluka.
- Kontekstualni izvori (iako ne pokrivaju direktno povijest softvera, kasnija izdanja udžbenika odražavaju ovu promjenu): Gass (2003 - 5. izdanje); Schrijver (1986) - spominje računalne aspekte; INFORMS resursi (za opći kontekst).
Ukratko, analiza osjetljivosti nije “izmišljena” kao zasebna tehnika, već je prirodno izrasla iz strukture Simplex algoritma i teorije dualnosti, potaknuta praktičnom potrebom za razumijevanjem robusnosti optimalnih rješenja u svijetu koji se stalno mijenja. (Dantzig, 1963; Gass, 2003).
Moderna analiza osjetljivosti (engl. sensitivity analysis, SA) u linearnom programiranju (LP) značajno je oblikovana napretkom računalne tehnologije i softvera. Ključne karakteristike uključuju:
- Dominacija softverskih rješavača (Solvera):
- Izračun SA (sjene cijena, smanjeni troškovi, dopušteni rasponi) potpuno je automatiziran u moćnim komercijalnim (npr. CPLEX, Gurobi) i open-source (npr. GLPK, HiGHS) solverima.
- Ručna interpretacija simpleks tablica za SA više nije praktična za stvarne probleme (Vanderbei, 2020).
- Integracija u sustave:
- LP i SA su često ugrađeni kao moduli unutar većih poslovnih sustava (ERP, SCM), alata za modeliranje (GAMS, AMPL) i programskih knjižnica (Python, R, Julia), čineći optimizaciju i analizu dostupnijima (Hillier & Lieberman, 2021).
- Pomak fokusa na interpretaciju i primjenu:
- Budući da softver obavlja izračune, naglasak je na ispravnom tumačenju SA izvještaja i njihovoj primjeni za podršku menadžerskom odlučivanju (“što-ako” scenariji, identifikacija uskih grla) (Winston & Goldberg, 2004).
- Napredne tehnike za neizvjesnost:
- Standardna SA je lokalna i često promatra promjenu jednog parametra.
Za realističnije modeliranje neizvjesnosti, koriste se naprednije metode
poput:
- Stohastičkog programiranja (modeliranje vjerojatnosnih ishoda) (Birge & Louveaux, 2011).
- Robusne optimizacije (traženje rješenja otpornog na najgore scenarije) (Ben-Tal et al., 2009).
- Standardna SA je lokalna i često promatra promjenu jednog parametra.
Za realističnije modeliranje neizvjesnosti, koriste se naprednije metode
poput:
- Algoritamski razvoj:
- Uz Simplex metodu, metode unutarnje točke postale su standardne, često brže za vrlo velike probleme i prirodno daju primalna i dualna rješenja potrebna za SA (Vanderbei, 2020).
Ukratko, dok su teorijski temelji ostali isti, moderna praksa analize osjetljivosti oslanja se na sofisticirane računalne alate i fokus je preusmjeren na ispravno tumačenje SA izvještaja. I mi ćemo pristupiti na taj način. No, da bismo mogli razumjeti zašto se neki pokazatelj tumači na točno određeni način, moramo steći dublje razumijevanje što stoji iza izračunatih brojki. Krenimo redom - prvo upoznajemo dualni program koji je pridružen primalnom programu.
Primalni i dualni program
Primalni program
Pretpostavimo linearni program u obliku maksimizacije. Koristimo standardni zapis i prepoznajemo da se radi o strukturi problema koju smo već ranije savladali. U ovom kontekstu, pridodajemo joj još jedno značenje, tj. naziv: primalni program.
Maksimizacija
\[ Z = c_1 x_1 + c_2 x_2 + \dots + c_n x_n \]
uz ograničenja
\[ a_{11} x_1 + a_{12} x_2 + \dots + a_{1n} x_n \le b_1 \] \[ a_{21} x_1 + a_{22} x_2 + \dots + a_{2n} x_n \le b_2 \] \[ \vdots \] \[ a_{m1} x_1 + a_{m2} x_2 + \dots + a_{mn} x_n \le b_m \]
i ne-negativnost odluka
\[ x_j \ge 0 \quad \text{za } j = 1,\dots,n. \]
Interpretacija:
- \(x_j\): varijabla odluke (npr. koliko proizvoditi proizvoda \(j\))
- \(c_j\): doprinos cilju po jedinici (npr. koliko raste prihod po jedinici \(x_j\) )
- \(b_i\): dostupna količina resursa tipa \(i\) (npr. sati rada, kg sirovine)
- \(a_{ij}\): koliko resursa \(i\) troši jedna jedinica aktivnosti/proizvoda \(j\)
Drugim riječima:
Primalni program odgovara na pitanje: Kako alocirati ograničene resurse (\(b_i\)) na različite aktivnosti (\(x_j\)) da bismo ostvarili što veći ukupni rezultat (\(Z\))?
Dualni program
Ta fotografija korisnika Nepoznat autor: licenca CC BY-NC-ND
Svakom primalnom programu, pridružen je pripadajući dualni problem.
Pravila prelaska iz primalnog u dualni program
Ako je primalni problem (koji zovemo kanonski primal) oblika:
- Funkcija cilja: maksimizacija
- Sva ograničenja: tipa \(\le\)
- Sve varijable: \(x_j \ge 0\)
…onda je njegov dual oblika:
- Cilj: minimizacija
- Sva ograničenja: tipa \(\ge\)
- Varijable duala: \(y_i \ge 0\)
Točnije, dualni program glasi:
Minimizacija \[ W = b_1 y_1 + b_2 y_2 + \dots + b_m y_m \]
uz ograničenja \[ a_{11} y_1 + a_{21} y_2 + \dots + a_{m1} y_m \ge c_1 \] \[ a_{12} y_1 + a_{22} y_2 + \dots + a_{m2} y_m \ge c_2 \] \[ \vdots \] \[ a_{1n} y_1 + a_{2n} y_2 + \dots + a_{mn} y_m \ge c_n \]
i uvjet
\[ y_i \ge 0 \quad \text{za } i = 1,\dots,m. \]
Strukturna pravila
- Broj ograničenja u primalu (\(m\)) = Broj varijabli u dualu (\(m\)). (Svakom primalnom ograničenju \(i\) odgovara dualna varijabla \(y_i\)).
- Broj varijabli u primalu (\(n\)) = Broj ograničenja u dualu (\(n\)). (Svakoj primalnoj varijabli \(x_j\) odgovara dualno ograničenje \(j\)).
- Matrica koeficijenata se transponira:
- Koeficijenti \(a_{ij}\) koji u primalu čine \(i\)-to ograničenje (redak), u dualu čine koeficijente uz \(y_i\) varijable u različitim ograničenjima.
- Koeficijenti \(a_{ij}\) koji u primalu čine \(j\)-tu varijablu (stupac), u dualu čine \(j\)-to ograničenje (redak).
- Vektori \(c\) (primalni cilj) i
\(b\) (primalna desna strana) mijenjaju
mjesta:
- \(b_i\) iz primala postaju koeficijenti cilja u dualu.
- \(c_j\) iz primala postaju desna strana ograničenja u dualu.
Intuicija: kako čitamo primalni i dualni program
Primalni program (proizvodni pogled)
Kroz primalni program, pitamo se, npr.:
Koliko kojeg proizvoda proizvodimo da zaradimo najviše, s resursima koje imamo?
- \(x_j\): koliko radimo
proizvoda/aktivnosti \(j\)
- cilj: maksimizirati (npr.) profit
Profitabilnost je normalna i poželjna. To nije problem. Problem bi bio da model “nađe rupu” gdje može povećavati cilj bez dodatne potrošnje ograničenih resursa. Primal je taj koji sadrži ograničenja tipa “ovoga imamo samo toliko” i ta ograničenja sama po sebi sprečavaju besmisleni rast funkcije cilja. Dual nije tu da “zabrani” profitabilne proizvode nego da procijeni vrijednost resursa kroz sjenu cijena.
Lijeva strana dualnog ograničenja za proizvod \(j\),
\[ a_{1j} y_1 + a_{2j} y_2 + \dots + a_{mj} y_m, \]
predstavlja vrijednost resursa koji se troše da se napravi 1 jedinica tog proizvoda \(j\).
Desna strana, \(c_j\), je doprinos cilju (npr. profit po jedinici proizvoda \(j\)).
Uvjet
\[ a_{1j} y_1 + a_{2j} y_2 + \dots + a_{mj} y_m \ge c_j \]
osigurava da niti jedna varijabla odluke (npr. jedinica proizvoda) ne može “pobjeći” iz sustava i proizvesti više rezultata nego što smo mu priznali kroz vrijednost resursa. Zašto je to važno? Zato što inače ukupna vrijednost resursa iz duala,
\[ W = \sum_{i=1}^m b_i\, y_i,\]
ne bi bila valjana gornja granica rezultata koji primal može ostvariti. Drugim riječima: dualno ograničenje garantira da je \(W\) doista “najniža poštena gornja granica” za maksimizirani rezultat primala.
Dualni program (vrijednosni / cjenovni pogled)
Kroz dualni program, pitamo se, npr.:
Koja je minimalna “poštena” vrijednost (\(W\)) svih naših resursa?
Da bismo to odredili, svakom resursu \(i\) (kojeg imamo u količini \(b_i\)) dodjeljujemo “cijenu u sjeni” ili sjenu cijena, odnosno dualnu varijablu \(y_i\).
Iako je ovo vjerojatno jasno, vrijedi napomenuti da ovo činimo tek po utvrđivanju optimalnog rezultata. Drugim riječima, prethodna tvrdnja je matematički točna tek u optimumu. Do tada je \(y_i\) samo “kandidat” za tu cijenu. Prava sjena cijena će biti \(y_i^*\), odnosno optimalna vrijednost dualne varijable. Zašto je ovo važno? Temeljem sjene cijena izvodimo ozbiljne zaključke i preporuke, koji vrijede samo za optimalno rješenje, ne za bilo kakav proizvoljan \(y\).
- u tom kontekstu, \(y_i\) predstavlja graničnu vrijednost jedne dodatne jedinice resursa \(i\). Također, vodite računa da ovdje govorimo o vrijednosti, a ne trošku - dakle, za sad možemo zamisliti da se radi o pripisanoj internoj vrijednosti resursima - to neće biti objektivna, općevažeća mjera koju možemo izravno izmjeriti kroz npr. trošak resursa ili sl. te vrijedi samo za pojedini program uz dane parametre.
- drugim riječima, kao granična vrijednost, \(y_i\) nam govori za koliko bi se naš maksimalni rezultat (\(Z\)) povećao kada bismo imali na raspolaganju još jednu jedinicu resursa \(i\). Zato se \(y_i\) naziva “sjena u cijeni”, sjena cijena (engl. shadow price) ili oportunitetni trošak resursa.
Funkcija cilja duala: \[ W = b_1 y_1 + \dots + b_m y_m \]
- predstavlja ukupnu imputiranu (procijenjenu) vrijednost svih resursa koje tvrtka posjeduje. Ako resurs \(i\) vrijedi \(y_i\) po jedinici, a imamo ga \(b_i\) jedinica, ukupna vrijednost je njihov umnožak. Zbrajamo po svim resursima.
Dual želi minimizirati tu ukupnu vrijednost. Zašto? Tražimo najniži mogući skup cijena (\(y_i\)) koji je još uvijek “racionalan” ili “održiv” – tj. koji zadovoljava dualna ograničenja. Želimo pronaći najnižu ukupnu vrijednost naših resursa (\(W\)) koja je i dalje u skladu s rezultatom koji ti resursi mogu generirati. Odnosno, želimo da \(W\) bude gornja granica za bilo koji rezultat koji možemo ostvariti proizvodnjom u primalu.
Dualna ograničenja
Pogledajmo jedno dualno ograničenje, npr. prvo (koje odgovara primalnoj varijabli \(x_1\), tj. proizvodu 1): \[ a_{11} y_1 + a_{21} y_2 + \dots + a_{m1} y_m \ge c_1 \]
Interpretacija:
- Desna strana (\(c_1\)): Ovo je rezultat koji ostvarujemo generiranjem jedne jedinice \(x_1\).
- Lijeva strana (\(a_{11} y_1 +
\dots\)): Ovo je imputirana vrijednost (ili
oportunitetni trošak) resursa potrebnih za generiranje te jedne
jedinice, npr. proizvoda 1.
- Za 1 kom proizvoda 1 treba nam:
- \(a_{11}\) jedinica resursa 1 (koji vrijedi \(y_1\) po jedinici)
- \(a_{21}\) jedinica resursa 2 (koji vrijedi \(y_2\) po jedinici)
- …
- \(a_{m1}\) jedinica resursa \(m\) (koji vrijedi \(y_m\) po jedinici)
- Ukupna vrijednost resursa utrošenih u proizvod 1 je upravo zbroj na lijevoj strani.
- Za 1 kom proizvoda 1 treba nam:
To ograničenje kaže:
Imputirana vrijednost resursa utrošenih u proizvod 1 mora biti barem jednaka rezultatu koji taj proizvod donosi.
Zašto to mora vrijediti?
Zamislimo da nije tako. Pretpostavimo da za proizvod 1 vrijedi suprotno: \[ (\text{Vrijednost resursa}) < (\text{Profit}) \] \[ (a_{11} y_1 + \dots + a_{m1} y_m) < c_1 \]
Recimo da resursi koje trošimo vrijede ukupno najviše 5€, ali proizvod koji od njih nastaje donosi profit od 8€.
To bi značilo da naš sustav “cijena” (\(y_i\)) nije dobar – podcijenili smo vrijednost naših resursa. Ako je to istina, proizvod 1 je “čaroban”: stvara vrijednost (profit) ni iz čega (iz resursa koji vrijede manje). Što bi napravio racionalan menadžer? Proizvodio bi beskonačno mnogo tog proizvoda, jer svaka nova jedinica “pretvara” resurse vrijedne 5 € u profit od 8 €. Znači +3 € čiste razlike po komadu, opet i opet. To implicira da bi optimalna vrijednost ciljne funkcije u primalu otišla u beskonačno (neograničeno velika dobit). Racionalna tvrtka bi u tom slučaju trebala proizvoditi beskonačno mnogo proizvoda 1 (ako je moguće), što bi značilo da primalni problem nema konačno rješenje (kažemo da je neograničen).
Dualni program, postavljanjem uvjeta \(\ge\), osigurava ekonomsku ravnotežu. Cijene resursa (\(y_i\)) moraju biti postavljene dovoljno visoko da opravdaju (pokriju) profitabilnost svake pojedine aktivnosti (proizvoda) koja te resurse koristi.
U optimalnom rješenju:
- Ako je za proizvod \(j\) trošak resursa veći od profita (\(A^T y > c_j\)), taj se proizvod ne isplati proizvoditi. Optimalna odluka bit će \(x_j = 0\).
- Ako se proizvod \(j\) isplati proizvoditi (\(x_j > 0\)), tada u optimumu mora vrijediti jednakost: trošak resursa je točno jednak profitu (\(A^T y = c_j\)). Sav profit se “prelio” u vrijednost resursa koje taj proizvod troši. (Ovo je poznato kao uvjet komplementarnosti). Obratite pozornost na to da ovdje govorimo o vrijednosti resursa, a ne njihovom trošku.
Veza između primala i duala
Slaba dualnost (Weak Duality)
Za bilo koje dopušteno rješenje primala \(x\) i bilo koje dopušteno rješenje duala \(y\) vrijedi:
\[ Z(x) \le W(y) \]
(Uz pretpostavku da je primal MAX problem, a dual MIN problem)
ili
\[c^⊤x≤b^⊤y\]
Tumačenje (Ekonomski smisao):
Bilo koji ostvarivi rezultat (vrijednost \(Z(x)\) iz dopuštenog rješenja primala) nikada ne može premašiti bilo koju dopuštenu procjenu vrijednosti resursa (vrijednost \(W(y)\) iz dopuštenog rješenja duala).
Svako dopušteno rješenje duala (svaka \(W(y)\)) daje nam gornju granicu za optimalnu vrijednost primala (\(Z^*\)).
Praktična uporaba:
Ovo je “provjera realnosti”.
Ako netko tvrdi da može ostvariti profit od 10.000 € (potencijalni \(Z(x)\)), a vi pronađete samo jedno dopušteno rješenje duala (jednu konzistentnu procjenu resursa) s vrijednošću \(W(y) = \text{9.500 €}\), znate da je profit od 10.000 € nemoguć.
Zašto? Jer slaba dualnost kaže da svaki \(Z(x)\) mora biti manji ili jednak svakom \(W(y)\). Budući da smo našli \(W(y)\) od 9.500 €, optimalni profit \(Z^*\) mora biti \(\le 9.500 €\).
Jaka dualnost (Strong Duality)
Ako primal ima (konačno) optimalno rješenje \(x^*\), tada i dual ima (konačno) optimalno rješenje \(y^*\), i vrijedi:
\[ Z^* = W^* \]
ili
\[ Z(x^*) = W(y^*) \] - gdje \(^*\) koristimo kao oznaku uz varijable \(x\) i \(y\) koje označavaju onu njihovu vrijednost koja je optimalna i za koju funkcije \(Z(x)\) i \(W(x)\) poprimaju optimalnu (najveću moguću) vrijednost, tj. \(Z^*\) ili \(W^*\);
odnosno, isto to možemo zapisati i kao:
\[c^⊤x=b^⊤y\]
Tumačenje (Ekonomski smisao):
Na optimumu, stvari se savršeno poklapaju.
Optimalna vrijednost primala (Maksimalni mogući rezultat) = Optimalna vrijednost duala (Minimalna “fer” ili “ravnotežna” vrijednost resursa)
Jaz između ostvarivog rezultata i procijenjene vrijednosti resursa (tzv. “duality gap”) na optimumu nestaje i jednak je nuli.
Posljedica: potvrda optimalnosti
Ovo je najvažnija praktična posljedica dualnosti.
Ako imate kandidata za optimalno rješenje primala (\(x'\)) i kandidata za optimalno rješenje duala (\(y'\)), i možete pokazati da su obje točke dopuštene I da je \(Z(x') = W(y')\), dokazali ste da su oba rješenja optimalna.
Ne trebate tražiti dalje. Pronalazak para dopuštenih rješenja s jednakom vrijednosti funkcije cilja certifikat je da ste pronašli optimum.
Univerzalnost dualnosti: Pravila za bilo koji oblik primala
Svaki problem linearnog programiranja (primal) ima točno jedan njemu pridružen dualni problem.
Pravila za formuliranje duala su sistematična i mehanička. Ona vrijede bez obzira na to je li funkcija cilja maksimizacija ili minimizacija, te bez obzira kakva su ograničenja (\(\le\), \(\ge\) ili \(=\)).
Odnos primal-dual je “zrcalni” ili simetričan. Najlakše ga je pamtiti kroz tablicu korespondencije.
Kako formulirati dual za “mješoviti” primal
Recimo da formuliramo dual polazeći od primala koji je MAX problem (ako je primal MIN, dual će biti MAX, i pravila se čitaju simetrično).
Osnovni princip:
- Svako ograničenje u primalu odgovara jednoj varijabli u dualu.
- Svaka varijabla u primalu odgovara jednom ograničenju u dualu.
Ova tablica pokriva sve slučajeve:
| Primal (Problem MAKSIMIZACIJE) | \(\longleftrightarrow\) | Dual (Problem MINIMIZACIJE) |
|---|---|---|
| Funkcija cilja (Max) | \(\longleftrightarrow\) | Funkcija cilja (Min) |
| Koeficijenti cilja (\(c_j\)) | \(\longleftrightarrow\) | Desne strane ograničenja |
| Desne strane ograničenja (\(b_i\)) | \(\longleftrightarrow\) | Koeficijenti cilja |
| \(i\)-to ograničenje tipa \(\le\) | \(\longleftrightarrow\) | \(i\)-ta varijabla \(y_i \ge 0\) (nenegativna) |
| \(i\)-to ograničenje tipa \(\ge\) | \(\longleftrightarrow\) | \(i\)-ta varijabla \(y_i \le 0\) (nepozitivna) |
| \(i\)-to ograničenje tipa \(=\) | \(\longleftrightarrow\) | \(i\)-ta varijabla \(y_i\) (slobodna) |
| \(j\)-ta varijabla \(x_j \ge 0\) | \(\longleftrightarrow\) | \(j\)-to ograničenje tipa \(\ge\) |
| \(j\)-ta varijabla \(x_j \le 0\) | \(\longleftrightarrow\) | \(j\)-to ograničenje tipa \(\le\) |
| \(j\)-ta varijabla \(x_j\) (slobodna) | \(\longleftrightarrow\) | \(j\)-to ograničenje tipa \(=\) |
- Što ako je funkcija cilja primala MINIMIZACIJA?
Dualni problem će biti problem MAKSIMIZACIJE.
Sva pravila iz gornje tablice vrijede, samo ih čitate “s desna na lijevo”.
- Ako primal (MIN) ima ograničenje \(\ge\) (što je “standardno” za minimizaciju), dualna varijabla (MAX) bit će \(\ge 0\).
- Ako primal (MIN) ima ograničenje \(\le\), dualna varijabla (MAX) bit će \(\le 0\).
- Ako primal (MIN) ima ograničenje \(=\), dualna varijabla (MAX) bit će slobodna.
- Što ako su ograničenja mješovita (npr. \(\ge\) i \(\le\))?
To uopće nije problem. Pravila primjenjujete pojedinačno, za svako ograničenje.
Primjer:
Recimo da imate primal (MAX) s dva ograničenja:
- Ograničenje 1: … \(\le b_1\)
- Ograničenje 2: … \(\ge b_2\)
Kada budete formulirali dual (MIN), on će imati dvije dualne varijable, \(y_1\) i \(y_2\):
- Zbog ograničenja 1 (tipa \(\le\)), njegova dualna varijabla bit će: \(y_1 \ge 0\).
- Zbog ograničenja 2 (tipa \(\ge\)), njegova dualna varijabla bit će: \(y_2 \le 0\).
Proces je potpuno mehanički. Nije važno koliko je primalni problem “neuredan” ili mješovit; dualni problem se uvijek može konstruirati slijedeći ova simetrična pravila.
Primjeri kreiranja dualnog programa
Ovdje ćemo koristiti prvih 5 primjera iz lekcije Uvod u linearno programiranje - strukturiranje problema
1. primjer
Primalni program:
Funkcija cilja
\[max\ 40x_1 + 50x_2\]
Ograničenja
\[x_2 \leq 8\]
\[x_1 \leq 24\]
\[x_1 + x_2 \leq 28\]
\[x_1 \geq 0\]
\[x_2 \geq 0\]
Dualni program:
Funkcija cilja
\[min\ W = 8y_1 + 24y_2 + 28y_3\]
Ograničenja
\[y_2 + y_3 \geq 40 \quad (\text{za } x_1)\] \[y_1 + y_3 \geq 50 \quad (\text{za } x_2)\] \[y_1, y_2, y_3 \geq 0\]
Objašnjenje: Primal je MAX, sve \(\le\), sve \(x_j \ge 0\). Ovo je “standardni” oblik. Dual je MIN, sve \(\ge\), sve \(y_i \ge 0\).
Na ovom primjeru ćemo i dokazati da rješenje primalnog programa mora
biti jednako rješenju dualnog programa, koristeći paket
linprog.
> library(linprog)
>
> cvec <- c(40, 50) # vektor koeficijenata uz varijable odluke u funkciji cilja
> Amat <- matrix(c(0, 1,
+ 1, 0,
+ 1, 1),
+ ncol = 2, byrow = TRUE) # matrica koeficijenata uz varijable odluke na desnoj strani ograničenja
> dir <- rep("<=", 3) # vektor smjera ograničenja
> b <- c(8, 24, 28) # vektor desne strane ograničenja
>
> rjesenje1 <- solveLP(cvec = cvec, bvec = b, Amat = Amat, maximum = TRUE, const.dir = dir,
+ solve.dual = TRUE)> library(linprog)
>
> cvec <- c(8, 24, 28) # vektor koeficijenata uz varijable odluke u funkciji cilja
> Amat <- matrix(c(0, 1, 1,
+ 1, 0, 1),
+ ncol = 3, byrow = TRUE) # matrica koeficijenata uz varijable odluke na desnoj strani ograničenja
> dir <- rep(">=", 2) # vektor smjera ograničenja
> b <- c(40, 50) # vektor desne strane ograničenja
>
> rjesenje2 <- solveLP(cvec = cvec, bvec = b, Amat = Amat, maximum = FALSE, const.dir = dir,
+ solve.dual = TRUE)Nakon pokretanja oba rješenja, izlaz nam omogućuje izravnu usporedbu.
Uočavamo da je optimalna vrijednost primala (rjesenje1)
Objective function (Maximum): 1200, što je točno jednako
optimalnoj vrijednosti duala (rjesenje2) koja iznosi
Objective function (Minimum): 1200. Ovime je i praktično
potvrđen Teorem o jakoj dualnosti (\(Z^∗=W^∗\)).
> rjesenje1##
##
## Results of Linear Programming / Linear Optimization
##
## Objective function (Maximum): 1200
##
## Iterations in phase 1: 0
## Iterations in phase 2: 3
## Solution
## opt
## 1 20
## 2 8
##
## Basic Variables
## opt
## 1 20
## 2 8
## S 2 4
##
## Constraints
## actual dir bvec free dual dual.reg dual.p
## 1 8 <= 8 0 10 4 10
## 2 20 <= 24 4 0 4 0
## 3 28 <= 28 0 40 20 40
##
## All Variables (including slack variables)
## opt cvec min.c max.c marg marg.reg
## 1 20 40 0 50 NA NA
## 2 8 50 40 Inf NA NA
## S 1 0 0 -Inf 10 -10 4
## S 2 4 0 -10 40 0 NA
## S 3 0 0 -Inf 40 -40 20> rjesenje2##
##
## Results of Linear Programming / Linear Optimization
##
## Objective function (Minimum): 1200
##
## Iterations in phase 1: 2
## Iterations in phase 2: 0
## Solution
## opt
## 1 10
## 2 0
## 3 40
##
## Basic Variables
## opt
## 1 10
## 3 40
##
## Constraints
## actual dir bvec free dual dual.reg dual.p
## 1 40 >= 40 0 20 10 20
## 2 50 >= 50 0 8 Inf 8
##
## All Variables (including slack variables)
## opt cvec min.c max.c marg marg.reg
## 1 10 8 -12 28 NA NA
## 2 0 24 99 77 4 40
## 3 40 28 -48 32 NA NA
## S 1 0 0 -20 Inf 20 10
## S 2 0 0 -8 Inf 8 Inf2. primjer
Primalni program:
Funkcija cilja:
\[
\text{Max } 90x_1 + 100x_2 \quad \text{(maksimizacija profita)}
\]
Ograničenja:
\[
\begin{aligned}
0.7x_1 + x_2 &\leq 630 \quad \text{(priprema materijala)} \\
0.5x_1 + 0.8x_2 &\leq 600 \quad \text{(izrada kućišta)} \\
x_1 + 0.6x_2 &\leq 708 \quad \text{(izrada elektroničkih
dijelova)} \\
0.1x_1 + 0.25x_2 &\leq 135 \quad \text{(izrada maske)} \\
x_1, x_2 &\geq 0 \quad \text{(uvjet ne-negativnosti)}
\end{aligned}
\]
Dualni program:
Funkcija cilja:
\[ \text{Min } W = 630y_1 + 600y_2 + 708y_3 + 135y_4 \]
Ograničenja:
\[ \begin{aligned} 0.7y_1 + 0.5y_2 + y_3 + 0.1y_4 &\geq 90 \quad (\text{za } x_1) \\ y_1 + 0.8y_2 + 0.6y_3 + 0.25y_4 &\geq 100 \quad (\text{za } x_2) \\ y_1, y_2, y_3, y_4 &\geq 0 \end{aligned} \]
Objašnjenje: Identična logika kao u primjeru 1. Četiri primalna ograničenja postaju četiri dualne varijable. Dvije primalne varijable postaju dva dualna ograničenja.
3. primjer
Primalni program:
Funkcija cilja (maksimizacija dobiti po hektaru):
\(Z = 3200x_1 + 500x_2 + 700x_3 + 1000x_4\)
Ograničenja:
\(x_1 + x_2 + x_3 + x_4 = 100\) (ukupna dostupna površina je 100 hektara)
\(x_3 \geq 20\) (minimalna površina za kukuruz zbog ugovora s kooperativama)
\(x_4 \leq 40\) (maksimalna površina za soju zbog rotacije usjeva)
\(x_3 - x_2 \geq 10\) (barem 10 hektara više kukuruza nego pšenice)
\(x_2 \leq 35\) (ograničenje za pšenicu zbog opreme i resursa)
\(x_1 \leq 45\) (maksimalna površina za šparoge zbog dostupnosti sjemena)
\(x_1, x_2, x_3, x_4 \geq 0\) (površine zasađene svakom kulturom moraju biti ne-negativne)
Dualni program:
Funkcija cilja:
\[ \text{Min } W = 100y_1 + 20y_2 + 40y_3 + 10y_4 + 35y_5 + 45y_6 \]
Ograničenja:
\[ \begin{aligned} y_1 + y_6 &\geq 3200 \quad (\text{za } x_1) \\ y_1 - y_4 + y_5 &\geq 500 \quad (\text{za } x_2) \\ y_1 + y_2 + y_4 &\geq 700 \quad (\text{za } x_3) \\ y_1 + y_3 &\geq 1000 \quad (\text{za } x_4) \end{aligned} \]
Ograničenja za dualne varijable:
- \(y_1\) je slobodna (neograničena) (jer je primalno ograničenje 1 tipa \(=\))
- \(y_2 \le 0\) (jer je primalno ograničenje 2 tipa \(\ge\))
- \(y_3 \ge 0\) (jer je primalno ograničenje 3 tipa \(\le\))
- \(y_4 \le 0\) (jer je primalno ograničenje 4 tipa \(\ge\))
- \(y_5 \ge 0\) (jer je primalno ograničenje 5 tipa \(\le\))
- \(y_6 \ge 0\) (jer je primalno ograničenje 6 tipa \(\le\))
Objašnjenje: Ovo je mješoviti primjer. Svako primalno ograničenje (\(=, \ge, \le\)) diktira predznak svoje dualne varijable. Budući da su sve primalne varijable \(x_j \ge 0\), sva dualna ograničenja su tipa \(\ge\).
4. primjer
Primalni program:
Funkcija cilja:
\[ \text{Min } 8x_1 + 3x_2 \]
Ograničenja:
\[ \begin{aligned} 50x_1 + 100x_2 &\leq 1200000 \\ 0.1 \cdot 50 \cdot x_1 + 0.04 \cdot 100 \cdot x_2 &\geq 60000 \\ x_2 &\geq \frac{300000}{100} \\ x_1, x_2 &\geq 0 \end{aligned} \]
Dualni program:
Funkcija cilja:
\[ \text{Max } W = 1200000y_1 + 60000y_2 + 3000y_3 \]
Ograničenja:
\[ \begin{aligned} 50y_1 + 5y_2 &\leq 8 \quad (\text{za } x_1) \\ 100y_1 + 4y_2 + y_3 &\leq 3 \quad (\text{za } x_2) \end{aligned} \]
Ograničenja za dualne varijable:
- \(y_1 \le 0\) (jer je primalni (MIN) problem imao ograničenje 1 tipa \(\le\))
- \(y_2 \ge 0\) (jer je primalni (MIN) problem imao ograničenje 2 tipa \(\ge\))
- \(y_3 \ge 0\) (jer je primalni (MIN) problem imao ograničenje 3 tipa \(\ge\))
Objašnjenje: Ovdje je primal MINIMIZACIJA. Stoga je dual MAKSIMIZACIJA. Pravila se simetrično primjenjuju. Primalne varijable \(x_j \ge 0\) sada impliciraju dualna ograničenja tipa \(\le\).
5. primjer
Primalni program:
Funkcija cilja:
\[\text{max } 65x + 76y + 75z + 68w\]
Ograničenja:
- Trošak oglašavanja:
\[9x + 8y + 10z + 11w \leq 7200\]
- Radni sati prodajnih predstavnika:
\[3x + 3y + 4z \leq 2000\]
- Ukupna proizvodnja:
\[x + y + z + w \leq 800\]
- Minimalna isporuka za maloprodajne dućane:
\[z \geq 100\]
Uvjet ne-negativnosti:
\[x, y, z, w \geq 0\]
Dualni program:
Funkcija cilja:
\[ \text{Min } W = 7200y_1 + 2000y_2 + 800y_3 + 100y_4 \]
Ograničenja:
\[ \begin{aligned} 9y_1 + 3y_2 + y_3 &\geq 65 \quad (\text{za } x) \\ 8y_1 + 3y_2 + y_3 &\geq 76 \quad (\text{za } y) \\ 10y_1 + 4y_2 + y_3 + y_4 &\geq 75 \quad (\text{za } z) \\ 11y_1 + y_3 &\geq 68 \quad (\text{za } w) \end{aligned} \]
Ograničenja za dualne varijable:
- \(y_1 \ge 0\) (zbog primalnog ograničenja 1 tipa \(\le\))
- \(y_2 \ge 0\) (zbog primalnog ograničenja 2 tipa \(\le\))
- \(y_3 \ge 0\) (zbog primalnog ograničenja 3 tipa \(\le\))
- \(y_4 \le 0\) (zbog primalnog ograničenja 4 tipa \(\ge\))
Objašnjenje: Klasičan mješoviti problem. Primal je MAX, pa je dual MIN. Primalne varijable \(x_j \ge 0\) daju dualna ograničenja \(\ge\). Mješovita primalna ograničenja (\(\le\) i \(\ge\)) daju mješovite predznake dualnih varijabli (\(y_1, y_2, y_3 \ge 0\), ali \(y_4 \le 0\)).
Analiza osjetljivosti
Nakon što smo pronašli optimalno rješenje \(x^*\) i \(Z^*\), posao rijetko kada staje. U stvarnom svijetu, uvjeti se mijenjaju. Cijene sirovina rastu, dostupnost radne snage se smanjuje, potražnja za proizvodom varira.
Analiza osjetljivosti (ili post-optimalna analiza) je vrsta “što-ako” (engl. What-if) analize. Ona nam odgovara na ključna menadžerska pitanja:
Simbolična ilustracija
- Koliko je naše optimalno rješenje robusno (otporno) na promjene?
- Koliko se neki ulazni podatak (cijena, resurs) može promijeniti prije nego što se naša optimalna strategija (npr. “proizvodi A i B, ali ne C”) mora promijeniti?
- Koja ograničenja su nam stvarna “uska grla” i koliko bi vrijedilo platiti da ih se oslobodimo?
Dualni program je temelj za jedan od najvažnijih dijelova analize osjetljivosti.
Uloga duala: analiza desnih strana ograničenja (RHS)
Ovo je najelegantnija i najvažnija primjena dualnosti.
Optimalno rješenje dualnog problema, \(y^*\), daje nam točno ekonomsko tumačenje vrijednosti svakog resursa.
Sjene cijena (Shadow Prices)
Dualni program predstavlja matematičku osnovu utvrđivanja sjena cijena.
Optimalne vrijednosti dualnih varijabli (\(y_1^*, y_2^*, ... y_m^*\)) nazivaju se sjene cijena (ili marginalne vrijednosti resursa).
\(^*\) u izrazu \(y_1^*, y_2^*, ... y_m^*\) označava da se radi o optimalnom rezultatu. Npr. \(y_1\) može imati više vrijednosti koje su kandidati za optimum, ali kad dosegne optimum, onda ga označimo s \(y_1^*\).
Dakle, oznaka \(^*\) ukazuje na to da je varijabla (ili funkcija) poprimila optimalnu vrijednost. Često se koristi ovakva skraćena notacija da ne moramo svaki put tekstualno naglašavati na to da se radi o optimalnoj vrijednosti.
Ta fotografija korisnika Nepoznat autor: licenca CC BY-NC-ND
Definicija: Sjena cijena \(y_i^*\) za \(i\)-to ograničenje (resurs) nam govori za koliko će se točno povećati optimalna vrijednost funkcije cilja (\(Z^*\)) ako se desna strana (\(b_i\))-tog ograničenja poveća za jednu jedinicu.
Za bilo koji dopušteni \(x\) (primal) i \(y\) (dual):
\(c^⊤x≤y^⊤b\) \(\leftarrow \rightarrow\) Rezultat koji se može ostvariti ≤ Vrijednost resursa po cijenama \(y\)
Zato pokušavamo naći NAJMANJU moguću “fer procjenu” vrijednosti resursa: to je, u suštini, dual.
Tumačenje sjene cijena:
- Recimo da je primal problem maksimizacije (npr. profit), a ograničenje 1 su “sati rada” (\(... \le 1000\) sati).
- Riješimo problem i dobijemo, npr. \(Z^*= 50000\) €.
- Riješimo dual i dobijemo, npr. \(y_1^* = 30\) €.
- Tumačenje: Ako bismo povećali dostupne sate rada s 1000 na 1001 (\(b_1\) se povećao za 1), naš ukupni maksimalni profit (\(Z^*\)) bi porastao na \(50030\) €.
- Preporuka odluke: Sjena cijene od 30 € nam govori da se isplati platiti do 30 € za svaki dodatni sat rada. Ako možemo dobiti prekovremeni sat za 25 €, trebali bismo to učiniti. Ako prekovremeni sat košta više od 30 €, ne bismo.
Dopušteni raspon za \(b_i\)
- (engl. allowable increase)
- (engl. allowable decrease)
- ili (engl. allowable range)
Upozorenje: sjena cijene ne vrijedi zauvijek.
- Sjena cijene (\(y_i^*\)) vrijedi samo unutar određenog dopuštenog raspona (Allowable Increase / Allowable Decrease) za \(b_i\).
- Tumačenje: Softver nam kaže da sjena cijena \(y_1^* = 30 €\) vrijedi dok god su sati rada (npr.) između 950 i 1100.
- Ako povećamo sate rada na 1200 (izvan dopuštenog raspona), sjena cijene od 30 € više ne vrijedi. Zašto? Zato što se vjerojatno promijenilo “usko grlo”. Možda nam sada sati rada više nisu problem, nego su sirovine postale problem, ili nešto treće.
- Promjena \(b_i\) izvan dopuštenog raspona mijenja optimalnu bazu (set varijabli koje su u rješenju) i time mijenja i cijene u sjeni.
Vezujuća i nevezujuća ograničenja
(engl. Binding vs. Non-binding)
- Vezujuće ograničenje (Binding):
Ograničenje koje je u optimumu ispunjeno kao jednakost (npr. ako smo
potrošili svih 1000 sati rada).
- Njegova sjena cijene (\(y_i^*\)) je pozitivna (\(> 0\)). Vrijedilo bi imati više ovog resursa.
- Nevezujuće ograničenje (Non-binding):
Ograničenje koje u optimumu nije u potpunosti iskorišteno (npr.
ako smo imali 500kg sirovine, a potrošili 480kg).
- Njegova sjena cijene (\(y_i^*\)) je uvijek nula (\(= 0\)).
- Tumačenje: Imamo viška ovog resursa. Nabavka još tog resursa nam neće povećati rezultat (\(Z^*\)) nimalo, jer ga već imamo dovoljno (imamo i neiskorišteni višak).
Analiza koeficijenata \(c_j\) za varijable koje JESU u rješenju (\(x_j > 0\))
Osim analize resursa (\(b_i\)) pomoću duala, analizom osjetljivosti razmatramo i koeficijente funkcije cilja (\(c_j\)).
- Pitanje: Npr. imamo optimalno rješenje koje kaže “proizvodi 100 komada stola (\(x_1\))”. Stol (\(x_1\)) donosi profit \(c_1 = 50 €\). Koliko se taj profit može promijeniti (pasti ili porasti) prije nego što nam se promijeni optimalna odluka (npr. prije nego što postane isplativije proizvoditi stolice umjesto stolova)?
- Koncept: Dopušteni raspon za \(c_j\) (Allowable Range for Objective Coefficients).
- Tumačenje: Softver nam daje raspon (npr. od \(45\) € do \(65\) €).
- To znači: Dok god je profit koji se generira proizvodnjom stola unutar tog raspona, optimalna strategija (baza) ostaje ista (i dalje proizvodimo 100 stolova).
- Vrijednost ukupnog profita \(Z^*\) će se, naravno, promijeniti, ali optimalni plan se ne mijenja.
- Ako profit padne na \(40\) € (izvan raspona), optimalni plan se mijenja (npr. možda će biti optimalno proizvoditi 0 stolova).
Analiza koeficijenata \(c_j\) za varijable koje NISU u rješenju (\(x_j = 0\))
- Pitanje: Naše optimalno rješenje kaže “ne proizvodi proizvod C” (\(x_C = 0\)). Trenutni profit za C je \(c_C = 20 €\). Koliko bi taj profit morao porasti da bi nam se isplatilo početi proizvoditi C?
- Koncept: Smanjeni trošak (Reduced Cost).
- Tumačenje: Smanjeni trošak (npr. \(-5 €\)) nam govori koliko bi se \(c_C\) morao poboljšati (povećati) da bi
varijabla \(x_C\) ušla u rješenje.
- Ako je smanjeni trošak \(-5 €\), to znači da profit \(c_C\) mora porasti za \(5 €\) (s \(20 €\) na \(25 €\)) prije nego što \(x_C\) uopće postane kandidat za proizvodnju.
- Drugi način tumačenja: Ako na silu odlučimo proizvesti jedan komad \(x_C\) (iako je optimalno 0), naš ukupni profit \(Z^*\) će se smanjiti za \(5 €\).
Matematičke osnove analize osjetljivosti
Sva analiza osjetljivosti (sjene cijena, dopušteni rasponi za \(c_j\) i \(b_i\), smanjeni trošak) izvlači se iz finalne simpleks tablice (ili, preciznije, iz matrice \(B^{-1}\), inverza optimalne bazične matrice).
Podsjetimo se ključnih elemenata iz simpleks metode:
- \(B\) = Matrica baze (sastavljena od stupaca primalnih varijabli koje su u rješenju, \(x_B\))
- \(B^{-1}\) = Inverz matrice baze. Ovo je “sveti gral” analize osjetljivosti.
- \(b\) = Vektor desne strane (resursi)
- \(c_B\) = Vektor koeficijenata cilja za bazične varijable
U finalnoj, optimalnoj simpleks tablici vrijedi:
Optimalno rješenje (RHS): \(x_B = B^{-1} b\)
Sjene cijena (Dualne varijable): \(y^T = c_B^T B^{-1}\)
Red \(z_j - c_j\) (Reduced Costs): \(z_j - c_j = c_B^T B^{-1} A_j - c_j\) (gdje je \(A_j\) \(j\)-ti stupac originalne matrice \(A\))
Sve dok su dva uvjeta zadovoljena, naše rješenje je optimalno:
- Uvjet dopustivosti (Feasibility): \(x_B \ge 0\) (Sve vrijednosti u RHS stupcu su nenegativne)
- Uvjet optimalnosti (Optimality): \(z_j - c_j \ge 0\) (Svi koeficijenti u redu \(z-c\) su nenegativni, za MAX problem)
Analiza osjetljivosti nije ništa drugo nego postavljanje pitanja: “Koliko možemo promijeniti \(b_i\) ili \(c_j\) prije nego što jedno od ova dva uvjeta bude narušeno?”
U prošloj lekciji, Simplex metoda, riješili smo 1. primjer i dobili:
| BV | x₁ | x₂ | s₁ | s₂ | s₃ | RHS |
|---|---|---|---|---|---|---|
| x₂ | 0 | 1 | 1 | 0 | 0 | 8 |
| s₂ | 0 | 0 | 1 | 1 | -1 | 4 |
| x₁ | 1 | 0 | -1 | 0 | 1 | 20 |
| Z | 0 | 0 | 10 | 0 | 40 | 1200 |
Ova tablica nam daje sve odgovore odjednom:
- Optimalno rješenje (RHS stupac):
- Bazične varijable (BV) su \(x_2, s_2, x_1\).
- Njihove vrijednosti su: \(x_2 = 8\), \(s_2 = 4\), \(x_1 = 20\).
- Nebazične varijable su \(s_1=0\) i \(s_3=0\).
- Optimalna vrijednost funkcije cilja je \(Z = 1200\).
- Sjene cijena (Z-redak):
- Koeficijenti u Z-retku ispod početnih slack varijabli (\(s_1, s_2, s_3\)) su točno sjene cijena za odgovarajuća ograničenja.
- Koeficijent za \(s_1\) (Ograničenje \(C_1: x_2 \le 8\)) je 10. \(\implies y_1^* = 10\).
- Koeficijent za \(s_2\) (Ograničenje \(C_2: x_1 \le 24\)) je 0. \(\implies y_2^* = 0\).
- Koeficijent za \(s_3\) (Ograničenje \(C_3: x_1+x_2 \le 28\)) je 40. \(\implies y_3^* = 40\).
- Ovo savršeno odgovara algebarskom rezultatu (koji ćemo izvesti ispod) da je \(Z^* = W^* = 40b_3 + 10b_1\). Simpleks tablica nam izravno daje te koeficijente.
Matematika iza ovoga oslanja se na matričnu algebru.
Početni problem (u matričnom obliku):
Dodavanjem slack varijabli \(s_1, s_2, s_3\) dobivamo:
\[ \begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \\ s_1 \\ s_2 \\ s_3 \end{pmatrix} = \begin{pmatrix} 8 \\ 24 \\ 28 \end{pmatrix} \]
Bazna matrica (B)
Ovo je matrica sastavljena od originalnih stupaca varijabli koje su na kraju u bazi (BV).
Naše bazne varijable (BV) su \(x_2, s_2, x_1\). Njihovi originalni stupci su:
\[ \text{Stupac } x_2: \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}, \quad \text{Stupac } s_2: \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}, \quad \text{Stupac } x_1: \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix} \] Dakle, bazna matrica \(B\) (pazeći na redoslijed \(x_2, s_2, x_1\) iz tablice) je:
\[ B = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix} \]
Inverzna bazna matrica (\(B^{-1}\))
Ključni “trik” simpleksa je da se inverzna matrica \(B^{-1}\) automatski pojavljuje u konačnoj tablici. Ona se nalazi u stupcima koji su na početku činili jediničnu matricu (tj. u stupcima naših slack varijabli \(s_1, s_2, s_3\)).
Gledajući stupce \(s_1, s_2, s_3\) u gornjoj tablici:
Podsjetnik: Dvije metode za izračun inverza matrice (\(B^{-1}\))
Metoda 1: Gaussova eliminacija
Standardni postupak za izračun inverza je korištenje Gaussove eliminacije na proširenoj matrici \([B | I]\) dok ne dobijemo oblik \([I | B^{-1}]\).
Postavimo proširenu matricu \([B | I]\): \[ [ \begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 \end{array} ] \]
Koristimo operacije na recima:
- \(R_3 = R_3 - R_1\) \[ [ \begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & -1 & 0 & 1 \end{array} ] \]
- \(R_2 = R_2 - R_3\) \[ [ \begin{array}{ccc|ccc} 1 & 0 & 0 & \boldsymbol{1} & \boldsymbol{0} & \boldsymbol{0} \\ 0 & 1 & 0 & \boldsymbol{1} & \boldsymbol{1} & \boldsymbol{-1} \\ 0 & 0 & 1 & \boldsymbol{-1} & \boldsymbol{0} & \boldsymbol{1} \end{array} ] \]
Dobili smo oblik \([I | B^{-1}]\): \[ B^{-1} = \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & -1 \\ -1 & 0 & 1 \end{pmatrix} \]
Metoda 2: Formula pomoću adjunktne matrice
Klasična formula za inverz matrice \(B\) glasi: \[ B^{-1} = \frac{1}{\det(B)} \cdot \text{adj}(B) \]
Determinanta \(\det(B)\): (Razvoj po prvom retku) \[ \det(B) = 1 \cdot \det\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = 1 \]
Matrica kofaktora \(C\):
Kofaktor \(C_{ij}\) dobiva se brisanjem \(i\)-tog retka i \(j\)-tog stupca te množenjem determinante preostale \(2 \times 2\) matrice s \((-1)^{i+j}\).
- \(C_{11} = + \det\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = 1\)
- \(C_{12} = - \det\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} = -(0 - 1) = 1\)
- \(C_{13} = + \det\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} = (0 - 1) = -1\)
- \(C_{21} = - \det\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix} = 0\)
- \(C_{22} = + \det\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} = (1 - 0) = 1\)
- \(C_{23} = - \det\begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix} = 0\)
- \(C_{31} = + \det\begin{pmatrix} 0 & 0 \\ 1 & 1 \end{pmatrix} = 0\)
- \(C_{32} = - \det\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = -(1 - 0) = -1\)
- \(C_{33} = + \det\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = (1 - 0) = 1\) \[ C = \begin{pmatrix} 1 & 1 & -1 \\ 0 & 1 & 0 \\ 0 & -1 & 1 \end{pmatrix} \]
Adjunktna matrica \(\text{adj}(B) = C^T\): Adjunktna matrica je jednostavno transponirana matrica kofaktora (\(C^T\)): \[ \text{adj}(B) = \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & -1 \\ -1 & 0 & 1 \end{pmatrix} \]
Finalni izračun \(B^{-1}\): \[ B^{-1} = \frac{1}{1} \cdot \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & -1 \\ -1 & 0 & 1 \end{pmatrix} \] \[ B^{-1} = \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & -1 \\ -1 & 0 & 1 \end{pmatrix} \]
Obje metode daju isti rezultat. Kad pokrenemo naradbe
lp() i solveLP() iz lpSolve i
linprog, one ovaj izračun rade automatski. Inverzna matrica
\(B^{-1}\) se uvijek nalazi u
optimalnoj simplex tablici, i to točno u onim stupcima koji su na
početku problema bili jedinična matrica (stupci naših slack varijabli
\(s_1, s_2, s_3\)).
\[ B^{-1} = \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & -1 \\ -1 & 0 & 1 \end{pmatrix} \]
(Prvi red \(B^{-1}\) je red \(x_2\) u tablici, drugi je red \(s_2\), treći je red \(x_1\), tj. stupci uz slack varijable u optimalnoj tablici zapravo \(B^{−1}\) zapisano po redovima bazičnih varijabli)
Zašto je \(B^{-1}\) ključ analize osjetljivosti?
Zato što se zapravo pomoću nje računa sve u optimalnom rješenju:
Optimalni RHS: (Finalni RHS) = \(B^{-1} \cdot\) (Početni RHS) \[ \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & -1 \\ -1 & 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} 8 \\ 24 \\ 28 \end{pmatrix} = \begin{pmatrix} (1 \cdot 8) + (0 \cdot 24) + (0 \cdot 28) \\ (1 \cdot 8) + (1 \cdot 24) + (-1 \cdot 28) \\ (-1 \cdot 8) + (0 \cdot 24) + (1 \cdot 28) \end{pmatrix} = \begin{pmatrix} 8 \\ 4 \\ 20 \end{pmatrix} \] Ovo točno odgovara RHS stupcu (\(x_2=8, s_2=4, x_1=20\)).
Sjene cijena (\(y^*\)): sjene cijena su vektor \(y^{*T} = c_B^T \cdot B^{-1}\)
- Koeficijenti cilja (\(c_B^T\)) za \(x_2, s_2, x_1\) su \(\begin{pmatrix} 50 & 0 & 40 \end{pmatrix}\). \[ y^{*T} = \begin{pmatrix} 50 & 0 & 40 \end{pmatrix} \cdot \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & -1 \\ -1 & 0 & 1 \end{pmatrix} \] \[ y^{*T} = \begin{pmatrix} (50 \cdot 1 + 0 \cdot 1 + 40 \cdot -1) & (50 \cdot 0 + 0 \cdot 1 + 40 \cdot 0) & (50 \cdot 0 + 0 \cdot -1 + 40 \cdot 1) \end{pmatrix} \] \[ y^{*T} = \begin{pmatrix} 10 & 0 & 40 \end{pmatrix} \] Ovo točno odgovara Z-retku (10, 0, 40).
Zaključak:
Matematičke osnove koje smo prikazali putem matrične algebre te one koje ćemo izvesti algebrom u idućoj sekciji i rezultati simpleks tablice samo su različiti pogledi na istu stvar. Inverzna matrica \(B^{-1}\) je osnova koja nam daje i optimalno rješenje i sjene cijena. No, priča tu ne staje. Upravo se \(B^{-1}\) koristi za izračunavanje svih dopuštenih raspona u analizi osjetljivosti, a to je ono na što ćemo se fokusirati u nastavku.
Ponovo se vraćamo na 1. primjer, koristimo drugi pristup.
Funkcija cilja \[ \max Z = 40x_1 + 50x_2 \] Ograničenja \[ \begin{aligned} (C_1): \quad x_2 &\le 8 \\ (C_2): \quad x_1 &\le 24 \\ (C_3): \quad x_1 + x_2 &\le 28 \\ x_1, x_2 &\ge 0 \end{aligned} \]
Optimalno rješenje je:
- \(x_1^* = 20\)
- \(x_2^* = 8\)
- \(Z^* = 40(20) + 50(8) = 1200\)
Sada provjerimo koja su ograničenja “aktivna”, tj. vezujuća:
- \((C_1): \quad x_2 \le 8 \implies 8 \le 8\). Vezujuće.
- \((C_2): \quad x_1 \le 24 \implies 20 \le 24\). Nevezujuće. (Imamo 4 jedinice “viška” ili slacka).
- \((C_3): \quad x_1 + x_2 \le 28 \implies 20 + 8 \le 28\). Vezujuće.
Optimalno rješenje (\(x_1^*=20, x_2^*=8\)) je “točka” koja se nalazi na sjecištu dvaju vezujućih ograničenja:
- \(x_2 = 8\)
- \(x_1 + x_2 = 28\)
Matematički, cijela analiza osjetljivosti svodi se na pitanje: “Koliko možemo promijeniti ulazne podatke (npr. \(c_1=40\) ili \(b_1=8\)) prije nego što se optimalna točka pomakne na neko drugo sjecište?”
Sjena cijene nam govori koliko \(Z^*\) raste ako povećamo desnu stranu (\(b_i\)) za 1. Pogledajmo zašto.
Naša optimalna točka \((x_1, x_2)\) definirana je sustavom jednadžbi:
\[ \begin{aligned} x_1 + x_2 &= b_3 \quad (\text{gdje je } b_3=28) \\ x_2 &= b_1 \quad (\text{gdje je } b_1=8) \end{aligned} \]
Rješenje ovog sustava je:
- \(x_2^* = b_1\)
- \(x_1^* = b_3 - x_2^* = b_3 - b_1\)
Sada ubacimo ovo općenito rješenje u funkciju cilja \(Z\):
\[ Z = 40x_1 + 50x_2 = 40(b_3 - b_1) + 50(b_1) \] \[ Z = 40b_3 - 40b_1 + 50b_1 \] \[ Z^* = 40b_3 + 10b_1 \]
Ova jednadžba je srž analize osjetljivosti za desnu stranu (RHS). Ona nam točno govori kako optimalni \(Z^*\) ovisi o \(b_1\) i \(b_3\).
Što ako povećamo \(b_1\) (limit za \(x_2\)) s 8 na 9?
- \(Z_{novi}^* = 40(28) + 10(9) = 1120 + 90 = 1210\).
- Promjena \(Z^* = 1210 - 1200 = 10\).
- Sjena cijene za \(b_1\) je 10.
Što ako povećamo \(b_3\) (limit za \(x_1+x_2\)) s 28 na 29?
- \(Z_{novi}^* = 40(29) + 10(8) = 1160 + 80 = 1240\).
- Promjena \(Z^* = 1240 - 1200 = 40\).
- Sjena cijene za \(b_3\) je 40.
Što ako povećamo \(b_2\) (limit za \(x_1\)) s 24 na 25?
- Naša jednadžba \(Z^* = 40b_3 + 10b_1\) uopće ne sadrži \(b_2\).
- Promjena \(Z^* = 0\).
- Sjena cijene za \(b_2\) je 0. (To je \(y_2^*\) iz R ispisa, što je i logično jer je ograničenje nevezujuće).
Dopušteni raspon \(b_i\) (Resursi)
Kada mijenjamo desnu stranu (resurse), npr. \(b_i\), mi ne utječemo na red \(z-c\). Cijene \(c_j\) su iste, pa uvjet optimalnosti ostaje zadovoljen.
Međutim, utječemo na uvjet dopustivosti.
Ako se \(b_i\) promijeni za \(\Delta_i\), novi vektor resursa je \(b_{novi} = b + \Delta_i \cdot e_i\) (gdje je \(e_i\) vektor s 1 na \(i\)-tom mjestu i 0 inače).
Novo rješenje (RHS stupac) postaje:
\[ x_{B, novi} = B^{-1} \cdot b_{novi} = B^{-1} \cdot (b + \Delta_i \cdot e_i) \] \[ x_{B, novi} = (B^{-1} b) + \Delta_i \cdot (B^{-1} e_i) \]
Prepoznajemo dijelove:
- \(B^{-1} b = x_B^*\) (naše staro optimalno rješenje)
- \(B^{-1} e_i = \text{i-ti stupac matrice } B^{-1}\) (Ovaj stupac se u simpleks tablici nalazi točno na mjestu gdje je originalno bila slack varijabla \(s_i\) za to ograničenje!)
Dakle, formula je:
\[ (\text{Novi RHS}) = (\text{Stari RHS}) + \Delta_i \cdot (\text{Stupac od } s_i \text{ u finalnoj tablici}) \]
Da bi rješenje ostalo dopušteno, moramo zadržati \(x_{B, novi} \ge 0\).
\[ x_B^* + \Delta_i \cdot (\text{stupac } s_i) \ge 0 \]
Ovo je sustav nejednadžbi. Rješavajući ga za \(\Delta_i\), dobivamo:
- Dopušteno smanjenje (Allowable Decrease): Najveća negativna \(\Delta_i\) koja još zadovoljava nejednadžbe.
- Dopušteno povećanje (Allowable Increase): Najveća pozitivna \(\Delta_i\) koja još zadovoljava nejednadžbe.
Sjena cijene \(y_i^*\) vrijedi točno unutar tog raspona za \(\Delta_i\).
Ovdje nastavljamo s 1. Primjerom i daljnjim prikazom analize osjetljivosti.
Sada se pitamo: Dokad vrijede ove sjene cijene?
One vrijede sve dok je naša “baza” (skup vezujućih ograničenja \(C_1\) i \(C_3\)) optimalna. Baza ostaje optimalna sve dok:
Sva naša rješenja \(x_1^*, x_2^*\) ostaju \(\ge 0\).
Nijedno novo ograničenje ne postane vezujuće.
Naše općenito rješenje je:
- \(x_1^* = b_3 - b_1\)
- \(x_2^* = b_1\)
- Slack od \(C_2\): \(s_2^* = b_2 - x_1^* = b_2 - (b_3 - b_1) = b_2 - b_3 + b_1\)
Svi \(x_1^*, x_2^*, s_2^*\) moraju biti \(\ge 0\).
Analizirajmo promjenu \(b_1\) (trenutno = 8):
(Držimo \(b_2=24, b_3=28\) fiksnima)
- \(x_1^* = 28 - b_1 \ge 0 \implies \boldsymbol{b_1 \le 28}\) (Dopušteno povećanje: \(28 - 8 = 20\))
- \(x_2^* = b_1 \ge 0 \implies \boldsymbol{b_1 \ge 0}\)
- \(s_2^* = 24 - 28 + b_1 \ge 0 \implies -4 + b_1 \ge 0 \implies \boldsymbol{b_1 \ge 4}\) (Dopušteno smanjenje: \(8 - 4 = 4\))
Kombinirajući najstrože uvjete, dobivamo da \(b_1\) mora biti u rasponu \([4, 28]\).
Analizirajmo promjenu \(b_3\) (trenutno = 28):
(Držimo \(b_1=8, b_2=24\) fiksnima)
- \(x_1^* = b_3 - 8 \ge 0 \implies \boldsymbol{b_3 \ge 8}\) (Dopušteno smanjenje: \(28 - 8 = 20\))
- \(x_2^* = 8 \ge 0\) (Uvijek vrijedi)
- \(s_2^* = 24 - b_3 + 8 \ge 0 \implies 32 - b_3 \ge 0 \implies \boldsymbol{b_3 \le 32}\) (Dopušteno povećanje: \(32 - 28 = 4\))
Kombinirajući uvjete, dobivamo da \(b_3\) mora biti u rasponu \([8, 32]\).
Dopušteni raspon \(c_j\) (koeficijenti cilja)
Kada mijenjamo koeficijent cilja \(c_j\), mi ne utječemo na RHS stupac. Rješenje \(x_B = B^{-1} b\) ostaje isto, pa uvjet dopustivosti nije narušen.
Međutim, utječemo na uvjet optimalnosti (red \(z_j - c_j\)).
Slučaj 1: \(x_j\) je nebazična varijabla (\(x_j = 0\) u rješenju)
Ovo je jednostavno. Promjena \(c_j\) utječe samo na \(z_j - c_j\) za tu jednu varijablu.
Stari uvjet: \(z_j - c_j \ge 0\).
Novi uvjet: \(z_j - (c_j + \Delta_j) \ge 0\).
To znači: \(\Delta_j \le (z_j - c_j)\).
Tumačenje: Dopušteno povećanje je točno jednako Smanjenom trošku (Reduced Cost). Ako je smanjeni trošak 5, možemo povećati \(c_j\) za 5 (npr. s 20€ na 25€) prije nego varijabla uđe u rješenje. Dopušteno smanjenje je \(\infty\).
Slučaj 2: \(x_j\) je bazična varijabla (\(x_j > 0\) u rješenju)
Ovo je kompliciranije. Promjena \(c_j\) mijenja vektor \(c_B\). Budući da se \(c_B\) koristi za izračun cijelog \(z-c\) reda (\(z_k - c_k = c_B^T B^{-1} A_k - c_k\)), promjena \(c_j\) utječe na svaku nebazičnu varijablu \(k\).
Ako se \(c_j\) (koji je \(i\)-ti član \(c_B\)) promijeni za \(\Delta_j\), novi \(z-c\) red postaje: \[ (z_k - c_k)_{novi} = (c_B + \Delta_j \cdot e_i)^T B^{-1} A_k - c_k \] \[ (z_k - c_k)_{novi} = (c_B^T B^{-1} A_k - c_k) + \Delta_j \cdot (e_i^T B^{-1} A_k) \] \[ (z_k - c_k)_{novi} = (z_k - c_k)_{stari} + \Delta_j \cdot \bar{a}_{ik} \]
(gdje je \(\bar{a}_{ik}\) koeficijent u \(i\)-tom redu i \(k\)-tom stupcu finalne simpleks tablice)
Moramo zadržati uvjet optimalnosti \((z_k - c_k)_{novi} \ge 0\) za sve nebazične varijable \(k\).
\[ (z_k - c_k)_{stari} + \Delta_j \cdot \bar{a}_{ik} \ge 0 \]
Rješavajući ovaj sustav nejednadžbi (po jednu za svaku nebazičnu varijablu) za \(\Delta_j\), dobivamo:
- Dopušteno smanjenje: Najveća negativna \(\Delta_j\) koja zadovoljava sve nejednadžbe.
- Dopušteno povećanje: Najveća pozitivna \(\Delta_j\) koja zadovoljava sve nejednadžbe.
Unutar tog raspona, optimalna baza (strategija) ostaje ista.
Ponovo ćemo navedeno prikazati na 1. Primjeru.
Ovdje se pitamo: Koliko možemo mijenjati \(c_1=40\) ili \(c_2=50\) a da točka \((20, 8)\) i dalje bude optimalna?
Grafički, ovo je pitanje o nagibu funkcije cilja.
Funkcija cilja \(Z = c_1 x_1 + c_2 x_2\) ima izo-profitnu liniju \(x_2 = -\frac{c_1}{c_2} x_1 + \frac{Z}{c_2}\). \(\text{Nagib} = -\frac{c_1}{c_2}\)
Naša vezujuća ograničenja imaju nagibe:
\(x_1 + x_2 = 28 \implies x_2 = -1 \cdot x_1 + 28\). \(\text{Nagib} = -1\)
\(x_2 = 8\). \(\text{Nagib} = 0\) (horizontalna linija)
Da bi točka \((20, 8)\) bila optimalna, nagib funkcije cilja mora biti između nagiba ograničenja koja ga tvore.
\[ \text{Nagib}(C_3) \le \text{Nagib}(Z) \le \text{Nagib}(C_1) \] \[ -1 \le -\frac{c_1}{c_2} \le 0 \]
Analizirajmo promjenu \(c_1\) (trenutno = 40):
(Držimo \(c_2=50\) fiksnim)
\[ -1 \le -\frac{c_1}{50} \le 0 \]
Pomnožimo sve s \(-50\) (i okrenimo znakove nejednakosti):
\[ (-1) \cdot (-50) \ge (-\frac{c_1}{50}) \cdot (-50) \ge (0) \cdot (-50) \] \[ \boldsymbol{50 \ge c_1 \ge 0} \]
Raspon za \(c_1\) je \([0, 50]\).
Analizirajmo promjenu \(c_2\) (trenutno = 50):
(Držimo \(c_1=40\) fiksnim)
\[ -1 \le -\frac{40}{c_2} \le 0 \]
Prvo, riješimo desnu stranu (pretpostavljamo \(c_2 > 0\)):
\[ -\frac{40}{c_2} \le 0 \implies \frac{40}{c_2} \ge 0 \implies \text{Uvijek vrijedi} \]
Sada riješimo lijevu stranu:
\[ -1 \le -\frac{40}{c_2} \implies 1 \ge \frac{40}{c_2} \]
Pomnožimo s \(c_2\):
\[ \boldsymbol{c_2 \ge 40} \]
Raspon za \(c_2\) je \([40, \infty)\).
Vizualna interpretacija analize osjetljivosti
Matematika simpleksa je moćna, ali grafički pristup daje najbolju intuiciju. Koristimo standardni 2D problem iz 1. Primjera.
Vizualizacija dopuštenog raspona za \(c_j\) (Profit)
Što je Z? Funkcija cilja \(Z=40x_1+50x_2\) je linija (izoprofitna linija). Njen nagib je \(−\frac{c_1}{c_2}=−\frac{40}{50}=−0.8\).
Što je optimum? To je vrh (\(B\)) na sjecištu vezujućih ograničenja \(x_2=8\) (nagib 0) i \(x_1+x_2=28\) (nagib -1).
Što je dopušteni raspon? To je raspon unutar kojeg nagib funkcije cilja \(−\frac{c_1}{c_2}\) ostaje između nagiba vezujućih ograničenja (između -1 i 0).
Na gornjoj slici:
Optimalno rješenje (B): Trenutna linija profita (crna) ima nagib (-0.8) koji je “između” nagiba ograničenja \(C1\) (nagib 0) i \(C3\) (nagib -1).
Dopušteno smanjenje (crvena linija): Ako smanjimo \(c_1\) (profit Servera A), nagib raste prema 0. Sve dok je nagib manji od 0, točka B je optimalna. U granici, kada \(c_1=0\), nagib je 0 i svaka točka na liniji između (0, 8) i (20, 8) je optimalna.
Dopušteno povećanje (plava linija): Ako povećamo \(c_1\), nagib pada prema -1. U granici, kada \(c_1=50\), nagib je -1 (paralelan s C3). Tada je svaka točka na liniji između (20, 8) i (24, 4) optimalna.
Dopušteni raspon za \(c_1\) je [0, 50], što drži nagib profita između nagiba dva ograničenja koja definiraju optimalnu točku.
Funkcija cilja se rotira u ružičasto naznačenoj površini, ali uvijek prolazi točkom optimuma.
Vizualizacija dopuštenog raspona za \(b_i\) (Resursi)
Što je \(b_i\)? To je desna strana ograničenja (npr. \(x_2≤8\)). Ona definira položaj linije ograničenja.
Što je promjena \(b_i\)? Promjena \(b_i\) paralelno pomiče liniju ograničenja.
Što je sjena cijene? To je stopa po kojoj \(Z^∗\) raste kako pomičemo vezujuće ograničenje “prema van”.
Na gornjim slikama:
Graf A (Vezujuće ograničenje): Pomičemo \(b_3\) (liniju \(x_1+x_2\)).
Kada \(b_3\) poraste (plava linija), dopušteno područje se širi, a optimalna točka “klizi” od B prema B’ (\(x_1=24,x_2=8\)). Profit (\(Z^∗\)) raste. Sjena cijene je pozitivna (točno 40 €).
Kada \(b_3\) padne (crvena linija), područje se smanjuje, optimum klizi ulijevo. Profit pada.
Dopušteni raspon za \(b_3\) je [8, 32]. Izvan tog raspona, optimalna točka “udara” u drugo ograničenje (npr. \(x_1≤24\) postaje vezujuće kod B’) i sjena cijene se mijenja.
Graf B (Nevezujuće ograničenje): Pomičemo \(b_2\) (liniju \(x_1≤24\)).
Ograničenje C2 je nevezujuće. Imamo 4 jedinice “lufta” (slack).
Kada \(b_2\) poraste (plava linija), dopušteno područje se širi, ali optimalna točka (B) se ne miče. Ona je i dalje definirana sjecištem C1 i C3.
Profit (\(Z^∗\)) se ne mijenja. Sjena cijene je 0.
Tek ako smanjimo \(b^2\) za više od 4 jedinice (crvena linija), on će “udariti” u optimalno rješenje i postati vezujuć.
Dodatne vizualizacije analize osjetljivosti za druge probleme s dvije varijable koje rješavate možete isprobati u Interaktivnoj web aplikaciji za linearno programiranje s dvije varijable
Sažetak tumačenja
- iliti što gledamo u rješenju:
| Što analiziramo? | Ključni pojam | Gdje ga nalazimo? | Što nam govori? |
|---|---|---|---|
| Resurse / Ograničenja (\(b_i\)) | Sjena cijene (Shadow Price) | Vrijednost dualne varijable (\(y_i^*\)) | Koliko \(Z^*\) raste ako \(b_i\) poraste za 1. (Vrijedi samo za vezujuća ograničenja). |
| Resurse / Ograničenja (\(b_i\)) | Dopušteni Raspon (Allowable Range) | Raspon za \(b_i\) | Unutar kojeg raspona za \(b_i\) vrijedi ta sjena cijene. |
| Profit / Trošak (\(c_j\)) (za \(x_j > 0\)) | Dopušteni Raspon (Allowable Range) | Raspon za \(c_j\) | Unutar kojeg raspona \(c_j\) može varirati, a da strategija (baza) ostane ista. |
| Profit / Trošak (\(c_j\)) (za \(x_j = 0\)) | Smanjeni Trošak (Reduced Cost) | Vrijednost u simplex tablici | Koliko se \(c_j\) mora poboljšati (ili kolika je “kazna”) da bi \(x_j\) ušao u rješenje. |
Smjernice za tumačenje:
(općenito, prilagodite vlastitim primjerima)
Izvor: Ta
fotografija korisnika Nepoznat autor: licenca CC BY-NC-ND
Intervali za koeficijente funkcije cilja predstavljaju raspon vrijednosti unutar kojeg koeficijent može varirati bez promjene optimalnog rješenja, uz pretpostavku da ostale vrijednosti ostanu nepromijenjene.
Promjene desnih strana ograničenja predstavljaju raspon vrijednosti unutar kojeg desna strana može varirati bez promjene sjene cijena, uz pretpostavku da ostale vrijednosti ostanu nepromijenjene.
Ako je dopustivo povećanje ili smanjenje Inf ili -Inf, to znači da koeficijent ili ograničenje može varirati u tom smjeru bez utjecaja na optimalno rješenje, odnosno sjenu cijena.
Dodatne ili dopunske varijable označavaju razliku između iskorištenih i dostupnih resursa (ograničenja).
Sjene cijena (shadow prices) predstavljaju promjenu u vrijednosti funkcije cilja za jediničnu promjenu desne strane odgovarajućeg ograničenja.
Napomena o izračunu dopustivih povećanja desne strane ograničenja u
linprog i lpSolve paketima:
- Dopustiva povećanja izračunavaju se iterativnim postupkom s točnošću do 0.001.
- Postupak koristi kombinaciju ekspanzijske faze i binarnog pretraživanja za pronalazak graničnih vrijednosti.
- Preciznost izračuna može varirati ovisno o složenosti problema i
numeričkim karakteristikama rješavača
linprog.
U početku, korištenje Interaktivne web aplikacije za linearno programiranje može pomoći.
Primjeri rješavanja u R-u i interpretacije analize osjetljivosti
Nastavljamo s primjerima za koje smo ranije zadali primalni i dualni program.
1. primjer
Simbolična ilustracija
Izvor: DALL-E
Funkcija cilja
\[max\ 40x_1 + 50x_2\]
Ograničenja
\[x_2 \leq 8\]
\[x_1 \leq 24\]
\[x_1 + x_2 \leq 28\]
\[x_1 \geq 0\]
\[x_2 \geq 0\]
- prvi način, koristeći paket
linprog
> library(linprog)
>
> cvec <- c(40, 50) # vektor koeficijenata uz varijable odluke u funkciji cilja
> Amat <- matrix(c(0, 1,
+ 1, 0,
+ 1, 1),
+ ncol = 2, byrow = TRUE) # matrica koeficijenata uz varijable odluke na desnoj strani ograničenja
> dir <- rep("<=", 3) # vektor smjera ograničenja
> b <- c(8, 24, 28) # vektor desne strane ograničenja
>
> rjesenje1 <- solveLP(cvec = cvec, bvec = b, Amat = Amat, maximum = TRUE, const.dir = dir,
+ solve.dual = TRUE)
> rjesenje1##
##
## Results of Linear Programming / Linear Optimization
##
## Objective function (Maximum): 1200
##
## Iterations in phase 1: 0
## Iterations in phase 2: 3
## Solution
## opt
## 1 20
## 2 8
##
## Basic Variables
## opt
## 1 20
## 2 8
## S 2 4
##
## Constraints
## actual dir bvec free dual dual.reg dual.p
## 1 8 <= 8 0 10 4 10
## 2 20 <= 24 4 0 4 0
## 3 28 <= 28 0 40 20 40
##
## All Variables (including slack variables)
## opt cvec min.c max.c marg marg.reg
## 1 20 40 0 50 NA NA
## 2 8 50 40 Inf NA NA
## S 1 0 0 -Inf 10 -10 4
## S 2 4 0 -10 40 0 NA
## S 3 0 0 -Inf 40 -40 20- drugi način, koristeći paket
lpSolve
> library(lpSolve)
>
> cvec <- c(40, 50) # vektor koeficijenata uz varijable odluke u funkciji cilja
> Amat <- matrix(c(0, 1,
+ 1, 0,
+ 1, 1),
+ ncol = 2, byrow = TRUE) # matrica koeficijenata uz varijable odluke na desnoj strani ograničenja
> dir <- rep("<=", 3) # vektor smjera ograničenja
> b <- c(8, 24, 28) # vektor desne strane ograničenja
>
> rjesenje2 <- lp(direction = "max", objective.in = cvec, const.mat = Amat, const.dir = dir, const.rhs = b,
+ compute.sens=1)
> rjesenje2## Success: the objective function is 1200> rjesenje2$solution## [1] 20 8> rjesenje2$sens.coef.from## [1] 0 40> rjesenje2$sens.coef.to## [1] 5e+01 1e+30> rjesenje2$duals## [1] 10 0 40 0 0> rjesenje2$duals.from## [1] 4e+00 -1e+30 8e+00 -1e+30 -1e+30> rjesenje2$duals.to## [1] 2.8e+01 1.0e+30 3.2e+01 1.0e+30 1.0e+30Prvo primjećujemo da linprog i solveLP()
daju pregledniji sažetak rješenja nego lpSolve i
lp(). Svaki od ovih paketa, odnosno funkcija, ima svoje
prednosti i nedostatke, pa ćemo ih koristiti u kombinaciji. Ovdje ćemo
napraviti kratku digresiju kako bismo se detaljnije upoznali s
karakteristikama tih paketa.
Paket linprog
Paket linprog koristi Simplex algoritam za rješavanje
problema linearnog programiranja. Simplex algoritam, koji je razvio
George Dantzig 1947. godine, je iterativna metoda koja efikasno
pronalazi optimalno rješenje pomičući se od jednog vrha dopustivog
područja do drugog, sve dok ne pronađe optimum. Ovaj paket je relativno
jednostavan i direktan u svojoj implementaciji Simplex metode, ali je
zbog toga i sporiji.
Prednosti:
- Jednostavnost: direktna implementacija Simplex algoritma, što ga čini prikladnim za edukativne svrhe.
- Detaljnost: pruža detaljnije uvide u rezultate, osobito po pitanju analize osjetljivosti.
- Transparentnost: omogućuje bolje razumijevanje procesa rješavanja linearnog programa.
Ograničenja paketa linprog:
- Brzina: nije optimiziran za brzinu i može biti značajno sporiji od drugih paketa poput lpSolve.
- Dvofazni postupak: ako rješenje x=0 nije izvedivo, primjenjuje se dvofazni postupak, što može usporiti rješavanje.
- Numerička preciznost: zbog zaokruživanja, mogu se pojaviti male numeričke greške koje utječu na rezultat.
- Umjetna ograničenja: male numeričke greške mogu dovesti do stvaranja umjetnih ograničenja u problemu.
- Ograničena testiranost: funkcija nije opsežno testirana i možda neće riješiti sve izvedive probleme.
- Potencijalno netočni rezultati: u nekim slučajevima može dovesti do pogrešnih rezultata.
- Ograničenja jednakosti: nisu implementirana ograničenja jednakosti.
- Ograničena veličina problema: može imati poteškoća s vrlo velikim problemima.
- Nedostatak naprednih tehnika: ne uključuje napredne tehnike (kao npr. presolve rutine).
- Ograničena robusnost: može biti manje pouzdan za složenije ili numerički zahtjevne probleme.
Upotreba:
- Koristan kada je potrebna detaljna analiza osjetljivosti.
- Preporučljivo je verificirati rezultate korištenjem drugih softvera, posebno za složenije probleme.
- Pogodno za manje do srednje velike probleme linearnog programiranja.
Više detalja dostupno je na linku: https://cran.r-project.org/web/packages/linprog/linprog.pdf
Paket lpSolve
Paket lpSolve je svestraniji alat koji primarno koristi
revidirani Simplex algoritam, ali uključuje i dodatne napredne tehnike
te je optimiziran za brzinu.
Prednosti:
- Revidirana Simplex metoda: poboljšana verzija originalnog Simplex algoritma koja je računski efikasnija.
- Presolve rutina: pokušava pojednostaviti problem prije primjene glavnog algoritma.
- Višestruko određivanje cijena: koristi različite strategije za odabir varijabli koje ulaze u bazu.
- Skaliranje: opcije za skaliranje problema radi poboljšanja numeričke stabilnosti.
- Basis Crash: heuristike za brzo pronalaženje dobre početne baze kod problema s mnogo varijabli. Zbog svoje svestranosti i robusnosti, lpSolve je prikladan za širok spektar problema linearnog programiranja, uključujući i složenije slučajeve.
Ograničenja paketa lpSolve:
- Numerička stabilnost: kao i mnogi solveri linearnog programiranja, lpSolve može imati problema s numeričkom stabilnošću za loše uvjetovane ili vrlo velike probleme.
- Skaliranje: za neke probleme, potrebno je pravilno skaliranje ulaznih podataka kako bi se dobili točni rezultati.
- Ograničenja veličine: iako može riješiti velike probleme, performanse mogu značajno opasti za vrlo velike probleme s mnogo varijabli i ograničenja.
- Preciznost: za neke probleme, osobito one s vrlo malim ili vrlo velikim koeficijentima, preciznost rješenja može biti ograničena.
- Ograničenja u analizi osjetljivosti: analiza osjetljivosti uz lpSolve je manje detaljna u usporedbi s nekim drugim paketima ili komercijalnim solverima.
- Rješavanje degeneriranih problema: kao i mnogi solveri koji koriste Simplex metodu, lpSolve može imati poteškoća s visoko degeneriranim problemima.
Više detalja dostupno je na linku: https://cran.r-project.org/web/packages/lpSolve/lpSolve.pdf
Oba paketa koriste implementacije Simplex algoritma, ali zbog razlika u specifičnim implementacijama i dodatnim značajkama, mogu se pojaviti razlike u performansama ili čak u konačnim rezultatima, posebno kod numerički zahtjevnih problema.
Iščitavanje
Dijagnostika
Status rješenja primalnog programa (lpSolve): Uspješno pronađeno rješenje.
Status rješenja primalnog programa (linprog): Uspješno pronađeno rješenje.
Status rješenja dualnog programa (lpSolve): Uspješno pronađeno rješenje.
Status rješenja dualnog programa (linprog): Uspješno pronađeno rješenje.
Vrijednost funkcije cilja (lpSolve): 1200
Vrijednost funkcije cilja (linprog): 1200
Vrijednosti varijabli odluka:
- Broj sati dnevno koje Server A provede u radu: lpSolve =20, linprog =20
- Broj sati dnevno koje Server B provede u radu: lpSolve =8, linprog =8
Vrijednosti sjena cijena:
- Maksimalno vrijeme rada Servera B: lpSolve =10, linprog =10
- Maksimalno vrijeme rada Servera A: lpSolve =0, linprog =0
- Kombinirani rad Servera A i B: lpSolve =40, linprog =40
Validacija rezultata korištenjem dva različita paketa:
- Rezultati dobiveni korištenjem dva paketa (lpSolve i linprog) se podudaraju.
Analiza osjetljivosti: - Interval dopustivih promjena za koeficijente funkcije cilja
(temeljem rezultata dobivenih korištenjem paketa linprog):
Broj sati dnevno koje Server A provede u radu:
- dopustivo smanjenje na: 0,
- dopustivo povećanje na: 50 (zadana vrijednost koeficijenta: 40)
Broj sati dnevno koje Server B provede u radu:
- dopustivo smanjenje na: 40,
- dopustivo povećanje na: Inf (zadana vrijednost koeficijenta: 50)
Interval dopustivih promjena za desne strane ograničenja
(temeljem rezultata dobivenih korištenjem paketa linprog):
Maksimalno vrijeme rada Servera B:
- dopustivo smanjenje za: 4,
- dopustivo povećanje za: 20 (zadano ograničenje: 8 trenutno iskorišteno: 8)
Maksimalno vrijeme rada Servera A:
- dopustivo smanjenje za: 4,
- dopustivo povećanje za: Inf (zadano ograničenje: 24, trenutno iskorišteno: 20)
Kombinirani rad Servera A i B:
- dopustivo smanjenje za: 20,
- dopustivo povećanje za: 3.999878 (zadano ograničenje: 28, trenutno iskorišteno: 28)
Dodatne/dopunske varijable (slack/surplus)
(temeljem rezultata dobivenih korištenjem paketa linprog):
Maksimalno vrijeme rada Servera B: 0
Maksimalno vrijeme rada Servera A: 4
Kombinirani rad Servera A i B: 0
Sjene cijena (shadow prices)
(temeljem rezultata dobivenih korištenjem paketa linprog):
- Maksimalno vrijeme rada Servera B: 10
- Maksimalno vrijeme rada Servera A: 0
- Kombinirani rad Servera A i B: 40
Izvještavanje o rješenju i analizi osjetljivosti
Traži se optimalna strategija korištenja Servera A i Servera B kako bi se maksimizirala ukupna vrijednost (profit), uz identificiranje prilika za poboljšanje sustava.
Cilj problema
Cilj je bio maksimizirati dnevnu vrijednost (profit) koju generiraju dva servera, pri čemu:
- Server A donosi 40 €/sat
- Server B donosi 50 €/sat
Ograničeni smo s tri resursa:
- Server B može raditi najviše 8 sati dnevno.
- Server A može raditi najviše 24 sata dnevno.
- Kombinirani rad oba servera ne smije prijeći 28 sati dnevno.
Optimalno rješenje
Optimalna strategija koja donosi maksimalnu dnevnu vrijednost od 1200 € je:
- Koristiti Server A: 20 sati
- Koristiti Server B: 8 sati
Analiza resursa: Gdje su “uska grla”?
Analiza osjetljivosti otkriva stvarno stanje naših resursa:
Potpuno iskorištena (Vezujuća) ograničenja:
- Maksimalno vrijeme rada Servera B: Iskoristili smo svih 8 od 8 dostupnih sati. (Slack = 0)
- Kombinirani rad (A+B): Iskoristili smo svih 28 od 28 dostupnih sati. (Slack = 0)
- OVO SU NAŠA DVA “USKA GRLA”.
Neiskorištena (Nevezujuća) ograničenja:
- Maksimalno vrijeme rada Servera A: Imamo 4 sata viška kapaciteta (iskorišteno 20 od 24 dostupna sata).
- OVO TRENUTNO NIJE PROBLEM.
Ključne preporuke koje proizlaze iz analize osjetljivosti
(Ovdje leži najveća vrijednost analize.)
Sjene cijena (Shadow Prices) nam govore koliko točno vrijedi svaki dodatni sat posve iskorištenih resursa (“uskih grla”):
Prioritet #1: Povećanje “Kombiniranog rada”
- Sjena cijene = 40 €
- Za svaki 1 sat kojim uspijemo povećati limit kombiniranog rada (npr. s 28 na 29 sati), naš ukupni profit raste za 40 €.
- Ova vrijednost vrijedi samo za idućih ~4 sata povećanja (prema “dopustivo povećanje za: 3.999”). Nakon toga, vjerojatno nailazimo na novo usko grlo.
- Preporuka: Istražiti što definira limit od 28 sati (npr. hlađenje, napajanje) i je li ga moguće povoljno povećati, jer je to naš najvrijedniji resurs.
Prioritet #2: Povećanje rada Servera B
- Sjena cijene = 10 €
- Za svaki 1 sat kojim uspijemo povećati individualni limit Servera B (npr. s 8 na 9 sati), naš ukupni profit raste za 10 €.
- Preporuka: Ovo je također vrijedno, ali manje isplativo od rješavanja “kombiniranog” limita.
Ulaganje u Server A je nepotrebno
- Sjena cijene = 0 €
- Budući da imamo 4 sata viška kapaciteta za Server A, ulaganje u povećanje njegovog limita (iznad 24 sata) ne donosi nikakav dodatni profit (0 €).
Stabilnost optimalnog plana
Analiza pokazuje koliko su naši profiti (koeficijenti cilja) osjetljivi na promjene:
Server A (Profit = 40 €): Plan (20h za A, 8h za B) ostaje optimalan sve dok je profit Servera A u rasponu od [0 € do 50 €]. Naš plan je izuzetno stabilan na promjene cijene Servera A.
Server B (Profit = 50 €): Plan ostaje optimalan sve dok je profit Servera B u rasponu od [40 € do Beskonačno].
Zanimljivo je da, čak i ako profit Servera B postane ekstremno visok, i dalje je optimalno koristiti ga samo 8 sati, jer smo fizički ograničeni njegovim limitom (Ograničenje 1) i kombiniranim limitom (Ograničenje 3).
Zaključak: Imamo robustan plan. Da bismo zaradili više od 1200 €, fokus mora biti na rješavanju “uskih grla”, primarno na povećanju limita “kombiniranog rada” (vrijednost 40 €/sat).
Dualne vrijednosti (sjene cijene) pretvaraju rezultat LP-a u akcijske preporuke: pokazuju koje je ograničenje stvarno “skupe” prirode i gdje “prisila” košta profit. To je srž veze između dualnosti i analize osjetljivosti: primal kaže “koliko čega raditi”, dual kaže “što vrijedi mijenjati u sustavu i kolika je cijena toga**.
2. primjer
Simbolična ilustracija
Izvor: DALL-E
Funkcija cilja:
\[
\text{Max } 90x_1 + 100x_2 \quad \text{(maksimizacija profita)}
\]
Ograničenja:
\[0.7x_1 + x_2 \leq 630 \quad \text{(priprema
materijala)}\] \[0.5x_1 + 0.8x_2 \leq
600 \quad \text{(izrada kućišta)}\] \[x_1 + 0.6x_2 \leq 708 \quad \text{(izrada
elektroničkih dijelova)}\] \[0.1x_1 +
0.25x_2 \leq 135 \quad \text{(izrada maske)}\] \[x_1, x_2 \geq 0 \quad \text{(uvjet
ne-negativnosti)}\]
> library(linprog)
>
> cvec <- c(90, 100) # vektor koeficijenata uz varijable odluke u funkciji cilja
> Amat <- matrix(c(0.7, 1,
+ 0.5, 0.8,
+ 1, 0.6,
+ 0.1, 0.25),
+ ncol = 2, byrow = TRUE) # matrica koeficijenata uz varijable odluke na desnoj strani ograničenja
> dir <- rep("<=", 4) # vektor smjera ograničenja
> b <- c(630, 600, 708, 135) # vektor desne strane ograničenja
>
> rjesenje1 <- solveLP(cvec = cvec, bvec = b, Amat = Amat, maximum = TRUE, const.dir = dir,
+ solve.dual = TRUE)
> rjesenje1##
##
## Results of Linear Programming / Linear Optimization
##
## Objective function (Maximum): 74379.3
##
## Iterations in phase 1: 0
## Iterations in phase 2: 2
## Solution
## opt
## 1 568.966
## 2 231.724
##
## Basic Variables
## opt
## 1 568.9655
## 2 231.7241
## S 2 130.1379
## S 4 20.1724
##
## Constraints
## actual dir bvec free dual dual.reg dual.p
## 1 630.000 <= 630 0.0000 79.3103 134.4000 79.3103
## 2 469.862 <= 600 130.1379 0.0000 130.1379 0.0000
## 3 708.000 <= 708 0.0000 34.4828 156.0000 34.4828
## 4 114.828 <= 135 20.1724 0.0000 20.1724 0.0000
##
## All Variables (including slack variables)
## opt cvec min.c max.c marg marg.reg
## 1 568.9655 90 70.000 166.6667 NA NA
## 2 231.7241 100 54.000 128.5714 NA NA
## S 1 0.0000 0 -Inf 79.3103 -79.3103 134.4
## S 2 130.1379 0 -333.333 92.0000 0.0000 NA
## S 3 0.0000 0 -Inf 34.4828 -34.4828 156.0
## S 4 20.1724 0 -266.667 242.1053 0.0000 NA- drugi način, koristeći paket
lpSolve
> library(lpSolve)
>
>
> cvec <- c(90, 100) # vektor koeficijenata uz varijable odluke u funkciji cilja
> Amat <- matrix(c(0.7, 1,
+ 0.5, 0.8,
+ 1, 0.6,
+ 0.1, 0.25),
+ ncol = 2, byrow = TRUE) # matrica koeficijenata uz varijable odluke na desnoj strani ograničenja
> dir <- rep("<=", 4) # vektor smjera ograničenja
> b <- c(630, 600, 708, 135) # vektor desne strane ograničenja
>
> rjesenje2 <- lp(direction = "max", objective.in = cvec, const.mat = Amat, const.dir = dir, const.rhs = b,
+ compute.sens=1)
> rjesenje2## Success: the objective function is 74379.31> rjesenje2$solution## [1] 568.9655 231.7241> rjesenje2$sens.coef.from## [1] 70 54> rjesenje2$sens.coef.to## [1] 166.6667 128.5714> rjesenje2$duals## [1] 79.31034 0.00000 34.48276 0.00000 0.00000 0.00000> rjesenje2$duals.from## [1] 4.956e+02 -1.000e+30 5.520e+02 -1.000e+30 -1.000e+30 -1.000e+30> rjesenje2$duals.to## [1] 6.915789e+02 1.000000e+30 9.000000e+02 1.000000e+30 1.000000e+30
## [6] 1.000000e+30Iščitavanje
Dijagnostika
Status rješenja primalnog programa (lpSolve): Uspješno pronađeno rješenje.
Status rješenja primalnog programa (linprog): Uspješno pronađeno rješenje.
Status rješenja dualnog programa (lpSolve): Uspješno pronađeno rješenje.
Status rješenja dualnog programa (linprog): Uspješno pronađeno rješenje.
Vrijednost funkcije cilja (lpSolve): 74379.31
Vrijednost funkcije cilja (linprog): 74379.31
Vrijednosti varijabli odluka:
- Tablet srednje kvalitete: lpSolve =568.9655, linprog =568.9655
- Tablet visoke kvalitete: lpSolve =231.7241, linprog =231.7241
Vrijednosti sjena cijena:
- Odjel pripreme materijala: lpSolve =79.31034, linprog =79.31034
- Odjel izrade kućišta: lpSolve =0, linprog =0
- Odjel izrade elektroničkih dijelova: lpSolve =34.48276, linprog =34.48276
- Odjel izrade maski: lpSolve =0, linprog =0
Validacija rezultata korištenjem dva različita paketa:
- Rezultati dobiveni korištenjem dva paketa (lpSolve i linprog) se podudaraju.
Analiza osjetljivosti:
Interval dopustivih promjena za koeficijente funkcije cilja (temeljem rezultata dobivenih korištenjem paketa linprog):
Tablet srednje kvalitete:
- dopustivo smanjenje na: 70,
- dopustivo povećanje na: 166.6667 (zadana vrijednost koeficijenta: 90)
Tablet visoke kvalitete:
- dopustivo smanjenje na: 54,
- dopustivo povećanje na: 128.5714 (zadana vrijednost koeficijenta: 100)
Interval dopustivih promjena za desne strane ograničenja (temeljem rezultata dobivenih korištenjem paketa linprog):
Odjel pripreme materijala:
- dopustivo smanjenje za: 134.4,
- dopustivo povećanje za: 61.57871 (zadano ograničenje: 630 trenutno iskorišteno: 630)
Odjel izrade kućišta:
- dopustivo smanjenje za: 130.1379,
- dopustivo povećanje za: Inf (zadano ograničenje: 600 trenutno iskorišteno: 469.8621)
Odjel izrade elektroničkih dijelova:
- dopustivo smanjenje za: 156,
- dopustivo povećanje za: 191.9996 (zadano ograničenje: 708 trenutno iskorišteno: 708)
Odjel izrade maski:
- dopustivo smanjenje za: 20.17241,
- dopustivo povećanje za: Inf (zadano ograničenje: 135 trenutno iskorišteno: 114.8276)
Dodatne/dopunske varijable (slack/surplus) (temeljem rezultata dobivenih korištenjem paketa linprog):
Odjel pripreme materijala: 0
Odjel izrade kućišta: 130.1379
Odjel izrade elektroničkih dijelova: 0
Odjel izrade maski: 20.17241
Sjene cijena (shadow prices) (temeljem rezultata dobivenih korištenjem paketa linprog):
Odjel pripreme materijala: 79.31034
Odjel izrade kućišta: 0
Odjel izrade elektroničkih dijelova: 34.48276
Odjel izrade maski: 0
Izvještavanje o rješenju i analizi osjetljivosti
Traži se optimalna strategija mjesečne proizvodnje tableta srednje i visoke kvalitete kako bi se maksimizirao ukupni profit, uz identificiranje prilika za poboljšanje proizvodnog procesa.
Cilj problema
Cilj je bio maksimizirati mjesečni profit od proizvodnje dva modela tableta:
- Tablet srednje kvalitete (\(x_1\)) donosi 90 €/kom
- Tablet visoke kvalitete (\(x_2\)) donosi 100 €/kom
Proizvodnja je ograničena s četiri resursa (odjela):
- Priprema materijala: limit od 630 jedinica (npr. radnih sati)
- Izrada kućišta: limit od 600 jedinica
- Izrada elektroničkih dijelova: limit od 708 jedinica
- Izrada maske: limit od 135 jedinica
Optimalno rješenje
Optimalna strategija koja donosi maksimalni mjesečni profit od 74,379.31 € je:
- Proizvesti ~569 komada Tableta srednje kvalitete (\(x_1\))
- Proizvesti ~232 komada Tableta visoke kvalitete (\(x_2\))
(Precizne vrijednosti: \(x_1 = 568.97\) i \(x_2 = 231.72\))
Analiza resursa: Gdje su “uska grla”?
Analiza osjetljivosti otkriva stvarno stanje naših resursa:
- Potpuno iskorištena (Vezujuća) ograničenja:
- Odjel pripreme materijala: Iskoristili smo svih 630 od 630 dostupnih jedinica. (Slack = 0)
- Odjel izrade elektroničkih dijelova: Iskoristili smo svih 708 od 708 dostupnih jedinica. (Slack = 0)
- OVO SU NAŠA DVA “USKA GRLA”.
- Neiskorištena (Nevezujuća) ograničenja:
- Odjel izrade kućišta: Imamo ~130 jedinica viška kapaciteta (iskorišteno ~470 od 600).
- Odjel izrade maski: Imamo ~20 jedinica viška kapaciteta (iskorišteno ~115 od 135).
- OVI ODJELI TRENUTNO NISU PROBLEM.
Preporuke koje proizlaze iz analize osjetljivosti
Sjene cijena (Shadow Prices) nam govore koliko točno vrijedi svaka dodatna jedinica (npr. radni sat) naših “uskih grla”:
- Prioritet #1: Poboljšanje “Odjela pripreme materijala”
- Sjena cijene = 79.31 €
- Tumačenje: Za svaku 1 dodatnu jedinicu kapaciteta u ovom odjelu (npr. s 630 na 631), naš ukupni profit raste za 79.31 €.
- Oprez: Ova vrijednost vrijedi samo za idućih ~61.6 jedinica povećanja (prema “dopustivom povećanju za: 61.57” - tj. marginalna vrijednost od 79.31 € vrijedi samo unutar tog raspona).
- Preporuka: Ovo je naš daleko najvrjedniji resurs. Prioritet treba biti ulaganje u povećanje kapaciteta ovog odjela (npr. dodatna smjena, nabavka bržeg stroja), sve dok je cijena tog povećanja manja od 79.31 € po jedinici.
- Prioritet #2: Poboljšanje “Odjela izrade elektroničkih dijelova”
- Sjena cijene = 34.48 €
- Tumačenje: Za svaku 1 dodatnu jedinicu kapaciteta u ovom odjelu (s 708 na 709), naš ukupni profit raste za 34.48 €.
- Oprez: Ovo vrijedi za idućih ~192 jedinice povećanja.
- Preporuka: Ovo je također vrlo vrijedno ulaganje, ali tek nakon što se iscrpe mogućnosti u pripremi materijala.
- Ulaganje u “Izradu kućišta” i “Izradu maski” je
nepotrebno
- Sjena cijene = 0 €
- Tumačenje: Budući da imamo viška kapaciteta u oba odjela (130 i 20 jedinica), ulaganje u njihovo daljnje povećanje ne donosi nikakav dodatni profit (0 €).
Stabilnost optimalnog plana
Analiza pokazuje koliko su naši prodajni profiti osjetljivi na promjene:
Tablet srednje kvalitete (Profit = 90 €): Naš plan proizvodnje (~569, ~232) ostaje optimalan sve dok je profit ovog tableta u rasponu od [70 € do 166.67 €]. Plan je vrlo stabilan.
Tablet visoke kvalitete (Profit = 100 €): Plan ostaje optimalan sve dok je profit ovog tableta u rasponu od [54 € do 128.57 €].
Zaključak: Imamo robustan i stabilan plan proizvodnje. Da bismo zaradili više od 74,379 €, sav menadžerski fokus mora biti na rješavanju “uskih grla”, prvenstveno na povećanju kapaciteta Odjela pripreme materijala, gdje svaka dodatna jedinica resursa vrijedi 79.31 €.
3. primjer
Simbolična ilustracija
Izvor: DALL-E
Funkcija cilja (maksimizacija dobiti po hektaru):
\(Z = 3200x_1 + 500x_2 + 700x_3 + 1000x_4\)
Ograničenja:
\(x_1 + x_2 + x_3 + x_4 = 100\) (ukupna dostupna površina je 100 hektara)
\(x_3 \geq 20\) (minimalna površina za kukuruz zbog ugovora s kooperativama)
\(x_4 \leq 40\) (maksimalna površina za soju zbog rotacije usjeva)
\(x_3 - x_2 \geq 10\) (barem 10 hektara više kukuruza nego pšenice)
\(x_2 \leq 35\) (ograničenje za pšenicu zbog opreme i resursa)
\(x_1 \leq 45\) (maksimalna površina za šparoge zbog dostupnosti sjemena)
\(x_1, x_2, x_3, x_4 \geq 0\) (površine zasađene svakom kulturom moraju biti ne-negativne)
> library(linprog)
>
> cvec <- c(3200, 500, 700, 1000) # vektor koeficijenata uz varijable odluke u funkciji cilja
> Amat <- matrix(c(1, 1, 1, 1,
+ 0, 0, 1, 0,
+ 0, 0, 0, 1,
+ 0, -1, 1, 0,
+ 0, 1, 0, 0,
+ 1, 0, 0, 0),
+ ncol = 4, byrow = TRUE) # matrica koeficijenata uz varijable odluke na desnoj strani ograničenja
> dir <- c("=", ">=", "<=", ">=", "<=", "<=") # vektor smjera ograničenja
> b <- c(100, 20, 40, 10, 35, 45) # vektor desne strane ograničenja
>
> rjesenje1 <- solveLP(cvec = cvec, bvec = b, Amat = Amat, maximum = TRUE, const.dir = dir,
+ solve.dual = TRUE)
> rjesenje1Error in while (min(Tab[nCon + 1, 1:(nVar + nCon)]) < -zero & iter2 < : missing value where TRUE/FALSE needed
- ovdje uočavamo ograničenje
solveLP- ne podržava izračun rješenja za modele u kojima se pojavljuje ograničenje s jednakosti. No, to nije neočekivano, jer kad smo se bavili simplex algoritmima, vidjeli smo da osnovna simplex metoda ne podržava takva ograničenja. Zbog toga je potrebno posegnuti za naprednijim inačicama rješavanja. Unutarlinprogpaketa i funkcijesolveLP, postoji mogućnost podešavanja argumenta funkcijelpSolve=TRUE. Isprobajmo.
> library(linprog)
>
> cvec <- c(3200, 500, 700, 1000) # vektor koeficijenata uz varijable odluke u funkciji cilja
> Amat <- matrix(c(1, 1, 1, 1,
+ 0, 0, 1, 0,
+ 0, 0, 0, 1,
+ 0, -1, 1, 0,
+ 0, 1, 0, 0,
+ 1, 0, 0, 0),
+ ncol = 4, byrow = TRUE) # matrica koeficijenata uz varijable odluke na desnoj strani ograničenja
> dir <- c("=", ">=", "<=", ">=", "<=", "<=") # vektor smjera ograničenja
> b <- c(100, 20, 40, 10, 35, 45) # vektor desne strane ograničenja
>
> rjesenje1 <- solveLP(cvec = cvec, bvec = b, Amat = Amat, maximum = TRUE, const.dir = dir,
+ lpSolve = TRUE,
+ solve.dual = FALSE)
> rjesenje1##
##
## Results of Linear Programming / Linear Optimization
## (using lpSolve)
##
## Objective function (Maximum): 193000
##
## Solution
## opt
## 1 45
## 2 0
## 3 20
## 4 35
##
## Constraints
## actual dir bvec free
## 1 100 = 100 0
## 2 20 >= 20 0
## 3 35 <= 40 5
## 4 20 >= 10 10
## 5 0 <= 35 35
## 6 45 <= 45 0Rješenje je dobiveno, ali je izlaz nešto sažetiji nego ranije.
- drugi način, koristeći paket
lpSolve
> library(lpSolve)
>
> cvec <- c(3200, 500, 700, 1000) # vektor koeficijenata uz varijable odluke u funkciji cilja
> Amat <- matrix(c(1, 1, 1, 1,
+ 0, 0, 1, 0,
+ 0, 0, 0, 1,
+ 0, -1, 1, 0,
+ 0, 1, 0, 0,
+ 1, 0, 0, 0),
+ ncol = 4, byrow = TRUE) # matrica koeficijenata uz varijable odluke na desnoj strani ograničenja
> dir <- c("=", ">=", "<=", ">=", "<=", "<=") # vektor smjera ograničenja
> b <- c(100, 20, 40, 10, 35, 45) # vektor desne strane ograničenja
>
> rjesenje2 <- lp(direction = "max", objective.in = cvec, const.mat = Amat, const.dir = dir, const.rhs = b,
+ compute.sens=1)
> rjesenje2## Success: the objective function is 193000> rjesenje2$solution## [1] 45 0 20 35> rjesenje2$sens.coef.from## [1] 1e+03 -1e+30 -1e+30 7e+02> rjesenje2$sens.coef.to## [1] 1.0e+30 1.0e+03 1.0e+03 3.2e+03> rjesenje2$duals## [1] 1000 -300 0 0 0 2200 0 -500 0 0> rjesenje2$duals.from## [1] 6.5e+01 1.5e+01 -1.0e+30 -1.0e+30 -1.0e+30 4.0e+01 -1.0e+30 -5.0e+00
## [9] -1.0e+30 -1.0e+30> rjesenje2$duals.to## [1] 1.05e+02 5.50e+01 1.00e+30 1.00e+30 1.00e+30 8.00e+01 1.00e+30 1.00e+01
## [9] 1.00e+30 1.00e+30Iščitavanje
Dijagnostika
Status rješenja primalnog programa (
lpSolve): Uspješno pronađeno rješenje.
Status rješenja primalnog programa (
linproguzlpSolve = TRUE): Uspješno pronađeno rješenje.Status rješenja dualnog programa (
lpSolve): Uspješno pronađeno rješenje (dualni podaci dostupni krozrjesenje2$duals).
Status rješenja dualnog programa (
linproguzlpSolve = TRUE): Dual nije računan automatski (solve.dual = FALSE), no primalno rješenje i ciljana vrijednost se podudaraju slpSolve.Vrijednost funkcije cilja (lpSolve): 193000
Vrijednost funkcije cilja (linprog, uz lpSolve=TRUE): 193000
Vrijednosti varijabli odluka:
- Šparoge (\(x_1\)): lpSolve = 45
- Pšenica (\(x_2\)): lpSolve = 0
- Kukuruz (\(x_3\)): lpSolve = 20
- Soja (\(x_4\)): lpSolve = 35
Validacija rezultata korištenjem dva različita paketa:
linprog(slpSolve=TRUE) ilpSolvedaju istu optimalnu vrijednost cilja (193000) i identične vrijednosti varijabli odluka.
Dodatne/dopunske varijable (slack/surplus) - izračunate ručno:
Za \(\le\) ograničenja taj višak
zovemo slack.
Za \(\ge\) ograničenja taj višak zovemo
surplus.
Ako je slack/surplus = 0 → ograničenje je vezujuće
(binding).
Ako je slack/surplus > 0 → ograničenje je nevezujuće
(non-binding).
U našem problemu ograničenja su:
\(x_1 + x_2 + x_3 + x_4 = 100\)
- U rješenju: \(45 + 0 + 20 + 35 =
100\).
- Slack/surplus = 0 → vezujuće.
\(x_3 \ge 20\)
- U rješenju: \(x_3 = 20\).
- Surplus = \(20 - 20 = 0\) → vezujuće.
\(x_4 \le 40\)
- U rješenju: \(x_4 = 35\).
- Slack = \(40 - 35 = 5\) → nevezujuće (imamo još “lufta” od 5 ha).
\(x_3 - x_2 \ge 10\)
- U rješenju: \(20 - 0 = 20\).
- Surplus = \(20 - 10 = 10\) → nevezujuće (uvjet je zadovoljen “s rezervom”).
\(x_2 \le 35\)
- U rješenju: \(x_2 = 0\).
- Slack = \(35 - 0 = 35\) → nevezujuće (ovo ograničenje nam ništa ne diktira jer ionako nismo sadili pšenicu).
\(x_1 \le 45\)
- U rješenju: \(x_1 = 45\).
- Slack = \(45 - 45 = 0\) → vezujuće.
Sažetak statusa ograničenja:
Vezujuća (presudna, “usko grlo”):
- ukupna površina (\(=100\))
- minimalno kukuruza (\(\ge
20\))
- maksimalno šparoga (\(\le 45\))
- ukupna površina (\(=100\))
Nevezujuća (trenutno nisu problem):
- maksimalno soje (\(\le 40\), slack
5)
- odnos kukuruza i pšenice (\(\ge
10\), višak 10)
- maksimalno pšenice (\(\le 35\), slack 35)
- maksimalno soje (\(\le 40\), slack
5)
Dodatne/dopunske varijable (slack/surplus) - sažetak:
- \(x_1 + x_2 + x_3 + x_4 = 100\):
Slack = 0 → vezujuće
- \(x_3 \ge 20\): Surplus = \(20-20=0\) → vezujuće
- \(x_4 \le 40\): Slack = \(40-35=5\) →
nevezujuće
- \(x_3 - x_2 \ge 10\): Surplus =
\((20-0)-10=10\) →
nevezujuće
- \(x_2 \le 35\): Slack = \(35-0=35\) →
nevezujuće
- \(x_1 \le 45\): Slack = \(45-45=0\) → vezujuće
(Napomena: Uočite nesklad između sjene cijene i Slack/Surplusa za min. kukuruza. Vidi idući odjeljak.)
Analiza osjetljivosti:
- Interval dopustivih promjena za koeficijente funkcije cilja
(temeljem rezultata dobivenih korištenjem paketa lpSolve):
Šparuge:
- dopušteno smanjenje do: 1000 €/ha
- dopušteno povećanje do: praktički beskonačno (
1e+30) (zadana vrijednost koeficijenta: 3200)
- dopušteno smanjenje do: 1000 €/ha
Pšenica:
- dopušteno smanjenje: \(-\infty\)
(praktički
-1e+30)
- dopušteno povećanje do: 1000 €/ha (zadana vrijednost koeficijenta: 500)
- dopušteno smanjenje: \(-\infty\)
(praktički
Kukuruz:
- dopušteno smanjenje: \(-\infty\)
- dopušteno povećanje do: 1000 €/ha (zadana vrijednost koeficijenta: 700)
- dopušteno smanjenje: \(-\infty\)
Soja:
- dopušteno smanjenje do: 700 €/ha
- dopušteno povećanje do: 3200 €/ha (zadana vrijednost koeficijenta: 1000)
- dopušteno smanjenje do: 700 €/ha
Sjene cijena (shadow prices)
(temeljem rezultata dobivenih korištenjem paketa lpSolve):
- ukupna dostupna površina (100 ha): 1000
- minimalna površina za kukuruz (\(\ge
20\)): -300
- maksimalna površina za soju (\(\le
40\)): 0
- uvjet \(x_3 - x_2 \ge 10\): 0
- ograničenje za pšenicu (\(\le
35\)): 0
- maksimalna površina za šparoge (\(\le 45\)): 2200
- ukupna dostupna površina (100 ha): 1000
Napomena - pri iščitavanju:
> rjesenje2$duals## [1] 1000 -300 0 0 0 2200 0 -500 0 0Naš model ima:
- \(m = 6\) ograničenja
- \(n = 4\) varijable odluke
lpSolve vraća vektor duals duljine \(m + n = 6 + 4 = 10\). To je spoj dvije
stvari:
Prvih 6 brojeva = sjene cijene za svih 6 ograničenja, po redu kojim su zadana u modelu,
zadnja 4 broja = smanjeni troškovi (reduced costs) za 4 varijable odluke \(x1,x2,x3,x4\), tim redom.
Smanjeni troškovi (Zadnja \(n=4\) broja, za 4 varijable):
- (\(x_1\)) Smanjeni trošak za Šparoge: \(0\) €
- (\(x_2\)) Smanjeni trošak za Pšenicu: \(-500\) €
- (\(x_3\)) Smanjeni trošak za Kukuruz: \(0\) €
- (\(x_4\)) Smanjeni trošak za Soju: \(0\) €
Ovo je prvi put u našim primjerima da vidimo smanjeni trošak koji nije nula.
Što je to? Smanjeni trošak (ili oportunitetni trošak) je relevantan samo za varijable koje su 0 u optimalnom rješenju. U našem slučaju, to je Pšenica (\(x_2 = 0\)).
Zašto je 0 za druge? Za varijable koje su veće od 0 u rješenju (Šparoge, Kukuruz, Soja), smanjeni trošak je po definiciji uvijek 0. One su već profitabilne i nalaze se u optimalnoj bazi.
Tumačenje smanjenog troška od -500 € za Pšenicu (\(x_2\)):
Imamo dva (ekvivalentna) načina tumačenja ove vrijednosti:
Tumačenje kao “kazna”: Vrijednost od -500 € nam govori da je Pšenica jako neprofitabilna u ovom miksu. Ako bismo na silu odlučili posaditi 1 hektar pšenice (i time žrtvovali resurse s drugih, profitabilnijih kultura), naš ukupni profit (\(Z^*\)) bi pao za 500 €.
Tumačenje kao “potrebno poboljšanje”: Koliko bi profit pšenice trebao porasti da bi uopće postala kandidat za sadnju (da bi \(x_2\) postao \(> 0\))?
- Trenutni profit (\(c_2\)): 500 €/ha
- Smanjeni trošak: -500 €/ha
- Potreban porast profita = Apsolutna vrijednost smanjenog troška = 500 €/ha
- Zaključak: Profit pšenice morao bi porasti s 500 € na 1000 € (\(500 + 500\)) prije nego što bi se isplatilo posaditi je. Ovo je logično, jer bi tada postala jednako profitabilna kao Soja (koja donosi 1000 € i koja je “zauzela” mjesto u rješenju).
Izvještavanje o rješenju i analizi osjetljivosti
Traži se optimalna strategija sjetve (šparoge, pšenica, kukuruz, soja) kako bi se maksimizirala ukupna dobit, uz poštivanje agronomskih, ugovornih i resursnih ograničenja.
Cilj problema
Cilj je maksimizirati dobit sa 100 hektara zemlje, gdje kulture donose:
- Šparoge (\(x_1\)): 3200 €/ha
- Pšenica (\(x_2\)): 500 €/ha
- Kukuruz (\(x_3\)): 700 €/ha
- Soja (\(x_4\)): 1000 €/ha
Ograničeni smo nizom uvjeta, uključujući ugovorni minimum za kukuruz, agronomska ograničenja za soju i pšenicu, te limit dostupnosti sjemena za šparoge.
Optimalno rješenje
Optimalna strategija sjetve koja donosi maksimalnu dobit od 193.000 € je:
- Posaditi 45 ha Šparoga (\(x_1\))
- Ne saditi Pšenicu (\(x_2 = 0\) ha)
- Posaditi 20 ha Kukuruza (\(x_3\))
- Posaditi 35 ha Soje (\(x_4\))
Analiza resursa: Gdje su “uska grla”?
Analiza osjetljivosti (sjene cijena) otkriva koja su naša stvarna ograničenja:
- Kritična (Vezujuća) ograničenja (sjena cijene \(\neq 0\)):
- Maksimalna površina za šparuge (Limit: 45 ha): Iskoristili smo sav dostupan limit.
- Ukupna dostupna površina (Limit: 100 ha): Iskoristili smo svih 100 hektara.
- Minimalna površina za kukuruz (Limit: 20 ha): Sadimo 20 ha (na granici uvjeta).
- Nekritična (Nevezujuća) ograničenja (sjena cijene = 0):
- Maksimalna površina za soju (Limit: 40 ha): Nije problem (imamo 5 ha viška).
- Maksimalna površina za pšenicu (Limit: 35 ha): Nije problem (imamo 35 ha viška).
- Odnos Kukuruz vs Pšenica (>=10 ha): Ograničenje je zadovoljeno s viškom od 10 ha (\(20-0=20\)), nije kritično za profit.
Ključne preporuke koje proizlaze iz analize osjetljivosti
Sjene cijena nam govore koliko točno vrijedi (ili košta) promjena svakog vezujućeg ograničenja za 1 hektar:
- Prioritet #1: Povećati limit za šparuge
- Sjena cijene = 2200 €
- Tumačenje: Za svaki 1 dodatni hektar za koji možemo osigurati sjeme šparoga (povećanje limita s 45 na 46 ha), naša ukupna dobit raste za 2200 €.
- Preporuka: Ovo je daleko najprofitabilnija akcija. Sav napor treba usmjeriti na nabavku dodatnog sjemena ili resursa za šparoge.
- Prioritet #2: Povećati ukupnu površinu zemlje
- Sjena cijene = 1000 €
- Tumačenje: Za svaki 1 dodatni hektar zemlje koji možemo unajmiti ili kupiti (povećanje sa 100 na 101 ha), naša ukupna dobit raste za 1000 €.
- Preporuka: Ako je cijena dodatnog hektara manja od 1000 €, to je isplativo ulaganje (nakon što se iscrpi mogućnost sa šparogama).
- Problematično ograničenje: Ugovor za kukuruz
- Sjena cijene = -300 €
- Tumačenje: Minus je ključan. Budući da je ograničenje “veće ili jednako” (\(\ge 20\)), ovo znači: za svaki 1 hektar za koji povećamo ugovornu obvezu (npr. s 20 na 21 ha), naš ukupni profit PADA za 300 €.
- Preporuka: Ovaj ugovor nas košta profita. Trebali bismo pregovarati sa zadrugom o smanjenju obvezne sadnje kukuruza. Svaki hektar manje obveze donio bi nam 300 € (jer bismo taj hektar preusmjerili na profitabilniju soju ili šparoge).
Stabilnost optimalnog plana
- Šparoge (Profit = 3200 €): Plan je stabilan. Profit može pasti sve do 1000 €/ha, a šparoge će i dalje biti optimalan izbor (jer su i dalje profitabilnije od soje).
- Soja (Profit = 1000 €): Osjetljivija. Ako profit soje padne ispod 700 €/ha (manje od kukuruza), plan bi se promijenio. Ako poraste iznad 3200 €/ha, postala bi profitabilnija od šparoga.
- Pšenica (Profit = 500 €): Pšenica je trenutno potpuno izbačena. Njezin smanjeni trošak je -500 €, a dopušteno povećanje profita je do 1000 €. To znači da bi profit pšenice morao porasti s 500 € na 1000 € (koliko donosi soja) da bi postala konkurentna za ulazak u rješenje.
Zaključak: Imamo jasan plan (45 ha šparoga, 0 ha pšenice, 20 ha kukuruza, 35 ha soje) za maksimalnu dobit od 193000 €. Da bi se dobit povećala, fokus mora biti na: 1) Nabavci više sjemena za šparoge (vrijedi 2200 €/ha), 2) Povećanju ukupne zemlje (vrijedi 1000 €/ha), i 3) Smanjenju ugovorne obveze za kukuruz (košta nas 300 €/ha).
4. primjer
(4.1. iz Uvoda u linearno programiranje - strukturiranje problema )
Simbolična ilustracija
Izvor: DALL-E
Funkcija cilja:
\[ \text{Min } 8x_1 + 3x_2 \]
Ograničenja:
\[
\begin{aligned}
50x_1 + 100x_2 &\leq 1200000 \\
0.1 \cdot 50 \cdot x_1 + 0.04 \cdot 100 \cdot x_2 &\geq 60000 \\
x_2 &\geq \frac{300000}{100} \\
x_1, x_2 &\geq 0
\end{aligned}
\]
> library(linprog)
>
> cvec <- c(8, 3) # vektor koeficijenata uz varijable odluke u funkciji cilja
> Amat <- matrix(c(50, 100,
+ 0.1*50, 0.04*100,
+ 0, 1),
+ ncol = 2, byrow = TRUE) # matrica koeficijenata uz varijable odluke na desnoj strani ograničenja
> dir <- c( "<=", ">=", ">=") # vektor smjera ograničenja
> b <- c(1200000, 60000, 300000/100) # vektor desne strane ograničenja
>
> rjesenje1 <- solveLP(cvec = cvec, bvec = b, Amat = Amat, maximum = FALSE, const.dir = dir,
+ solve.dual = TRUE)
> rjesenje1##
##
## Results of Linear Programming / Linear Optimization
##
## Objective function (Minimum): 62000
##
## Iterations in phase 1: 2
## Iterations in phase 2: 1
## Solution
## opt
## 1 4000
## 2 10000
##
## Basic Variables
## opt
## 1 4000
## 2 10000
## S 3 7000
##
## Constraints
## actual dir bvec free dual dual.reg dual.p
## 1 1200000 <= 1200000 0 0.0566667 420000 0.0566667
## 2 60000 >= 60000 0 2.1666667 42000 2.1666667
## 3 10000 >= 3000 7000 0.0000000 7000 0.0000000
##
## All Variables (including slack variables)
## opt cvec min.c max.c marg marg.reg
## 1 4000 8 -12.2500000 NA NA NA
## 2 10000 3 NA 6.4 NA NA
## S 1 0 0 -0.0566667 Inf 0.0566667 420000
## S 2 0 0 -2.1666667 Inf 2.1666667 42000
## S 3 7000 0 NA 3.4 0.0000000 NARješenje je dobiveno, ali je izlaz nešto sažetiji nego ranije.
- drugi način, koristeći paket
lpSolve
> library(lpSolve)
>
> cvec <- c(8, 3) # vektor koeficijenata uz varijable odluke u funkciji cilja
> Amat <- matrix(c(50, 100,
+ 0.1*50, 0.04*100,
+ 0, 1),
+ ncol = 2, byrow = TRUE) # matrica koeficijenata uz varijable odluke na desnoj strani ograničenja
> dir <- c( "<=", ">=", ">=") # vektor smjera ograničenja
> b <- c(1200000, 60000, 300000/100) # vektor desne strane ograničenja
>
> rjesenje2 <- lp(direction = "min", objective.in = cvec, const.mat = Amat, const.dir = dir, const.rhs = b,
+ compute.sens=1)
> rjesenje2## Success: the objective function is 62000> rjesenje2$solution## [1] 4000 10000> rjesenje2$sens.coef.from## [1] 3.75e+00 -1.00e+30> rjesenje2$sens.coef.to## [1] 1.0e+30 6.4e+00> rjesenje2$duals## [1] -0.05666667 2.16666667 0.00000000 0.00000000 0.00000000> rjesenje2$duals.from## [1] 7.8e+05 4.8e+04 -1.0e+30 -1.0e+30 -1.0e+30> rjesenje2$duals.to## [1] 1.50e+06 1.02e+05 1.00e+30 1.00e+30 1.00e+30Iščitavanje
Dijagnostika - Status rješenja primalnog programa (lpSolve): Uspješno pronađeno rješenje. - Status rješenja primalnog programa (linprog): Uspješno pronađeno rješenje.
Status rješenja dualnog programa (lpSolve): Uspješno pronađeno rješenje.
Status rješenja dualnog programa (linprog): Uspješno pronađeno rješenje.
Vrijednost funkcije cilja (lpSolve): 62000
Vrijednost funkcije cilja (linprog): 62000
Vrijednosti varijabli odluka: - Udjeli u dioničkom fondu: lpSolve =4000, linprog =4000 - Udjeli u novčanom fondu: lpSolve =10000, linprog =10000
Vrijednosti sjena cijena: - Dostupni budžet: lpSolve =-0.05666667, linprog =0.05666667 - Minimalni željeni prinos: lpSolve =2.166667, linprog =2.166667 - Minimalno ulaganje u novčani fond: lpSolve =0, linprog =0
Validacija rezultata korištenjem dva različita paketa: - Rezultati dobiveni korištenjem dva paketa (lpSolve i linprog) se podudaraju.
Analiza osjetljivosti: - Interval dopustivih promjena za koeficijente funkcije cilja (temeljem rezultata dobivenih korištenjem paketa linprog): - Udjeli u dioničkom fondu: - dopustivo smanjenje na: -12.25, - dopustivo povećanje na: NA (zadana vrijednost koeficijenta: 8) - Udjeli u novčanom fondu: - dopustivo smanjenje na: NA, - dopustivo povećanje na: 6.4 (zadana vrijednost koeficijenta: 3)
Interval dopustivih promjena za desne strane ograničenja (temeljem rezultata dobivenih korištenjem paketa linprog):
Dostupni budžet:
- dopustivo smanjenje za: 420000,
- dopustivo povećanje za: 3e+05 (zadano ograničenje: 1200000 trenutno iskorišteno: 1200000)
Minimalni željeni prinos:
- dopustivo smanjenje za: 42000,
- dopustivo povećanje za: 60000 (zadano ograničenje: 60000 trenutno iskorišteno: 60000)
Minimalno ulaganje u novčani fond:
- dopustivo smanjenje za: 7000,
- dopustivo povećanje za: Inf (zadano ograničenje: 3000 trenutno iskorišteno: 10000)
Dodatne/dopunske varijable (slack/surplus) (temeljem rezultata dobivenih korištenjem paketa linprog):
Dostupni budžet: 0
Minimalni željeni prinos: 0
Minimalno ulaganje u novčani fond: 7000
Sjene cijena (shadow prices) (temeljem rezultata dobivenih korištenjem paketa linprog):
Dostupni budžet: 0.05666667
Minimalni željeni prinos: 2.166667
Minimalno ulaganje u novčani fond: 0
Izvještavanje o rješenju i analizi osjetljivosti
Traži se optimalna strategija ulaganja u dionički i novčani fond kako bi se minimalizirao ukupni rizik, uz zadovoljavanje zadanog minimalnog prinosa i poštivanje limita budžeta.
Cilj problema
Cilj je bio minimalizirati rizik (vrijednost \(Z\)) ulaganja, pri čemu:
- Ulaganje u Dionički fond (\(x_1\)) nosi 8 jedinica rizika.
- Ulaganje u Novčani fond (\(x_2\)) nosi 3 jedinice rizika.
Ograničeni smo s tri uvjeta:
- Dostupni budžet: Ukupno ulaganje mora biti \(\le 1.200.000 €\).
- Minimalni prinos: Očekivani prinos mora biti \(\ge 60.000 €\).
- Minimalno ulaganje: Barem 3.000 udjela mora biti u novčanom fondu (\(x_2 \ge 3000\)).
Optimalno rješenje
Optimalna strategija koja donosi minimalni rizik od 62.000 jedinica je:
- Kupiti 4.000 udjela Dioničkog fonda (\(x_1\))
- Kupiti 10.000 udjela Novčanog fonda (\(x_2\))
Analiza resursa: Gdje su “uska grla”?
Analiza osjetljivosti otkriva koja ograničenja diktiraju naše rješenje:
- Potpuno iskorištena (Vezujuća) ograničenja:
- Dostupni budžet: Iskoristili smo svih 1.200.000 € budžeta. (Slack = 0)
- Minimalni željeni prinos: Ostvarili smo točno 60.000 € traženog prinosa. (Surplus = 0)
- OVO SU NAŠA DVA “USKA GRLA”.
- Neiskorištena (Nevezujuća) ograničenja:
- Minimalno ulaganje u novčani fond: Naš plan (10.000 udjela) je 7.000 udjela IZNAD traženog minimuma (3.000). (Surplus = 7.000)
- OVO TRENUTNO NIJE PROBLEM.
Ključne preporuke koje proizlaze iz analize osjetljivosti
Budući da je ovo problem minimizacije, sjene cijena nam govore koliko nas “košta” svako ograničenje, tj. za koliko raste rizik ako postrožimo uvjete.
- Prioritet #1: Analiza minimalnog prinosa
- Sjena cijene = 2.167
- Tumačenje: Za svaki 1 € dodatnog prinosa koji zahtijevamo (npr. podizanje cilja s 60.000 € na 60.001 €), naš ukupni rizik (cilj) RASTE za 2.167 jedinica.
- Preporuka: Ovo je “cijena rizika” koju plaćamo za traženi prinos. Ako je menadžment voljan smanjiti traženi prinos (npr. na 59.999 €), ukupni rizik portfelja bi pao za 2.167 jedinica.
- Oprez: Ova cijena vrijedi dok je traženi prinos u rasponu od [18.000 €, 120.000 €].
- Prioritet #2: Analiza budžeta
- Sjena cijene = 0.0567 (koristeći
linprogvrijednost;lpSolvepredznak -0.0567 je tehnički točniji) - Tumačenje (koristeći
lpSolvepredznak -0.0567): Za svaki 1 € dodatnog budžeta koji osiguramo (povećanje s 1.2M na 1.2M+1), naš minimalni rizik PADA (zbog predznaka \(-\)) za 0.0567 jedinica. - Preporuka: Povećanje budžeta nam omogućuje da postignemo isti prinos uz neznatno manji rizik, ali je utjecaj vrlo malen u usporedbi s promjenom ciljanog prinosa.
- Oprez: Vrijedi dok je budžet u rasponu od [780.000 €, 1.500.000 €].
- Sjena cijene = 0.0567 (koristeći
- Minimalno ulaganje u novčani fond je nebitno
- Sjena cijene = 0 €
- Tumačenje: Budući da naš optimalni plan (10.000) ionako daleko premašuje minimum (3.000), promjena tog minimuma (npr. podizanje na 5.000) nema nikakav utjecaj (0) na optimalni rizik.
Stabilnost optimalnog plana
Analiza pokazuje koliko su procijenjeni rizici (koeficijenti cilja) osjetljivi na promjene:
- Novčani fond (Rizik = 3): Naš plan (4.000, 10.000) ostaje optimalan
sve dok je rizik novčanog fonda u rasponu [\(-\infty\), 6.4].
- Upozorenje: Ako stvarni rizik novčanog fonda poraste iznad 6.4 jedinice, naš trenutni plan prestaje biti optimalan.
- Dionički fond (Rizik = 8): Plan ostaje optimalan sve dok je rizik
dioničkog fonda u rasponu [-12.25, \(\infty\)].
- Tumačenje: Plan je izuzetno robustan na promjene rizika dioničkog fonda.
Zaključak: Imamo stabilan plan (4.000 udjela \(x_1\), 10.000 udjela \(x_2\)) koji daje minimalni rizik od 62.000. Ključni faktor koji “košta” rizik je zahtjev za minimalnim prinosom (svaki euro prinosa “košta” 2.167 jedinica rizika). Plan je osjetljiv jedino na neočekivano povećanje rizika novčanog fonda.
5. primjer
Simbolična ilustracija
Izvor: DALL-E
Funkcija cilja:
\[\text{max } 65x + 76y + 75z + 68w\]
Ograničenja:
- Trošak oglašavanja:
\[9x + 8y + 10z + 11w \leq 7200\]
- Radni sati prodajnih predstavnika:
\[3x + 3y + 4z \leq 2000\]
- Ukupna proizvodnja:
\[x + y + z + w \leq 800\]
- Minimalna isporuka za maloprodajne dućane:
\[z \geq 100\]
Uvjet ne-negativnosti:
\[x, y, z, w \geq 0\]
> library(linprog)
>
> cvec <- c(65, 76, 75, 68) # vektor koeficijenata uz varijable odluke u funkciji cilja
> Amat <- matrix(c(9, 8,10, 11,
+ 3, 3, 4, 0,
+ 1, 1, 1, 1,
+ 0, 0, 1, 0),
+ ncol = 4, byrow = TRUE) # matrica koeficijenata uz varijable odluke na desnoj strani ograničenja
> dir <- c(rep("<=", 3), ">=") # vektor smjera ograničenja
> b <- c(7200, 2000, 800, 100) # vektor desne strane ograničenja
>
> rjesenje1 <- solveLP(cvec = cvec, bvec = b, Amat = Amat, maximum = TRUE, const.dir = dir,
+ solve.dual = TRUE)
> rjesenje1##
##
## Results of Linear Programming / Linear Optimization
##
## Objective function (Maximum): 59366.7
##
## Iterations in phase 1: 1
## Iterations in phase 2: 2
## Solution
## opt
## 1 0.000
## 2 533.333
## 3 100.000
## 4 166.667
##
## Basic Variables
## opt
## 2 533.333
## 3 100.000
## 4 166.667
## S 1 100.000
##
## Constraints
## actual dir bvec free dual dual.reg dual.p
## 1 7100 <= 7200 100 0.00000 100.0000 0.00000
## 2 2000 <= 2000 0 2.66667 100.0000 2.66667
## 3 800 <= 800 0 68.00000 166.6667 68.00000
## 4 100 >= 100 0 3.66667 33.3333 3.66667
##
## All Variables (including slack variables)
## opt cvec min.c max.c marg marg.reg
## 1 0.000 65 -Inf 76.00000 -11.00000 100.0000
## 2 533.333 76 73.25000 Inf NA NA
## 3 100.000 75 -Inf 78.66667 NA NA
## 4 166.667 68 0.00000 76.00000 NA NA
## S 1 100.000 0 -1.22222 6.18182 0.00000 NA
## S 2 0.000 0 -Inf 2.66667 -2.66667 100.0000
## S 3 0.000 0 -Inf 68.00000 -68.00000 166.6667
## S 4 0.000 0 -Inf 3.66667 -3.66667 33.3333- drugi način, koristeći paket
lpSolve
> library(lpSolve)
>
> cvec <- c(65, 76, 75, 68) # vektor koeficijenata uz varijable odluke u funkciji cilja
> Amat <- matrix(c(9, 8, 10, 11,
+ 3, 3, 4, 0,
+ 1, 1, 1, 1,
+ 0, 0, 1, 0),
+ ncol = 4, byrow = TRUE) # matrica koeficijenata uz varijable odluke na desnoj strani ograničenja
> dir <- c(rep("<=", 3), ">=") # vektor smjera ograničenja
> b <- c(7200, 2000, 800, 100) # vektor desne strane ograničenja
>
> rjesenje2 <- lp(direction = "max", objective.in = cvec, const.mat = Amat, const.dir = dir, const.rhs = b,
+ compute.sens=1)
> rjesenje2## Success: the objective function is 59366.67> rjesenje2$solution## [1] 0.0000 533.3333 100.0000 166.6667> rjesenje2$sens.coef.from## [1] -1.000e+30 7.325e+01 -1.000e+30 0.000e+00> rjesenje2$sens.coef.to## [1] 7.600000e+01 1.000000e+30 7.866667e+01 7.600000e+01> rjesenje2$duals## [1] 0.000000 2.666667 68.000000 -3.666667 -11.000000 0.000000 0.000000
## [8] 0.000000> rjesenje2$duals.from## [1] -1.000000e+30 1.900000e+03 6.333333e+02 0.000000e+00 -1.000000e+30
## [6] -1.000000e+30 -1.000000e+30 -1.000000e+30> rjesenje2$duals.to## [1] 1.000000e+30 2.500000e+03 8.090909e+02 1.333333e+02 1.000000e+02
## [6] 1.000000e+30 1.000000e+30 1.000000e+30Iščitavanje
Dijagnostika
Status rješenja primalnog programa (lpSolve): Uspješno pronađeno rješenje.
Status rješenja primalnog programa (linprog): Uspješno pronađeno rješenje.
Vrijednost funkcije cilja (lpSolve): 59366.67
Vrijednost funkcije cilja (linprog): 59366.7
Vrijednosti varijabli odluka:
- Proizvod ‘x’: lpSolve = 0.00
- Proizvod ‘y’: lpSolve = 533.33
- Proizvod ‘z’: lpSolve = 100.00
- Proizvod ‘w’: lpSolve = 166.67
Vrijednosti sjena cijena (iz
lpSolve):
- Trošak oglašavanja: 0.00
- Radni sati prod. predstavnika: 2.666667
- Ukupna proizvodnja: 68.00
- Minimalna isporuka za maloprodaju: -3.666667
Validacija rezultata korištenjem dva različita paketa:
- Rezultati dobiveni korištenjem oba pristupa se podudaraju.
Analiza osjetljivosti:
- Interval dopustivih promjena za koeficijente funkcije cilja
(temeljem rezultata dobivenih korištenjem oba paketa):
Proizvod ‘x’:
- dopustivo smanjenje na: -\(\infty\),
- dopustivo povećanje na: 76.00 (zadana vrijednost koeficijenta: 65)
Proizvod ‘y’:
- dopustivo smanjenje na: 73.25,
- dopustivo povećanje na: \(\infty\) (zadana vrijednost koeficijenta: 76)
Proizvod ‘z’:
- dopustivo smanjenje na: -\(\infty\),
- dopustivo povećanje na: 78.67 (zadana vrijednost koeficijenta: 75)
Proizvod ‘w’:
- dopustivo smanjenje na: 0.00,
- dopustivo povećanje na: 76.00 (zadana vrijednost koeficijenta: 68)
Smanjeni trošak (Reduced Cost) za varijable izvan rješenja:
Proizvod ‘x’: -11.0 (Profit od 65€ je za 11€ previše nizak da bi ušao u rješenje. Morao bi porasti na 76€).
Interval dopustivih promjena za desne strane ograničenja
(temeljem rezultata dobivenih korištenjem paketa lpSolve):
- Trošak oglašavanja:
- dopustivo smanjenje na: 7100.00 (tj. za 100),
- dopustivo povećanje na: \(\infty\) (zadano ograničenje: 7200)
- Radni sati prod. predstavnika:
- dopustivo smanjenje na: 1900.00,
- dopustivo povećanje na: 2500.00 (zadano ograničenje: 2000)
- Ukupna proizvodnja:
- dopustivo smanjenje na: 633.33,
- dopustivo povećanje na: 809.09 (zadano ograničenje: 800)
- Minimalna isporuka za maloprodaju:
- dopustivo smanjenje na: 0.00,
- dopustivo povećanje na: 133.33 (zadano ograničenje: 100)
- Dodatne/dopunske varijable (slack/surplus)
(temeljem rezultata dobivenih korištenjem paketa linprog):
Trošak oglašavanja: 100
Radni sati prod. predstavnika: 0
Ukupna proizvodnja: 0
Minimalna isporuka za maloprodaju: 0
Sjene cijena (shadow prices)
(temeljem rezultata dobivenih korištenjem paketa lpSolve):
- Trošak oglašavanja: 0.00
- Radni sati prod. predstavnika: 2.666667
- Ukupna proizvodnja: 68.00
- Minimalna isporuka za maloprodaju: -3.666667
Izvještavanje o rješenju i analizi osjetljivosti
Traži se optimalna strategija proizvodnje za četiri proizvoda (x, y, z, w) kako bi se maksimizirao ukupni profit, uz poštivanje ograničenja budžeta, radnih sati, ukupne proizvodnje i minimalne ugovorne isporuke.
Cilj problema
Cilj je maksimizirati profit (\(Z\)) od četiri proizvoda, koji donose:
- Proizvod X: 65 €/kom
- Proizvod Y: 76 €/kom
- Proizvod Z: 75 €/kom
- Proizvod W: 68 €/kom
Ograničeni smo s četiri resursa:
- Trošak oglašavanja: limit od 7200 €
- Radni sati predstavnika: limit od 2000 sati
- Ukupna proizvodnja: limit od 800 komada
- Minimalna isporuka (za Z): \(\ge\) 100 komada
Optimalno rješenje
Optimalna strategija koja donosi maksimalni profit od 59,366.67 € je:
- Ne proizvoditi Proizvod X (0 komada)
- Proizvesti ~533 komada Proizvoda Y
- Proizvesti 100 komada Proizvoda Z
- Proizvesti ~167 komada Proizvoda W
(Precizne vrijednosti: \(x=0, y=533.33, z=100, w=166.67\))
Analiza resursa: Gdje su “uska grla”?
Analiza osjetljivosti otkriva stvarno stanje naših resursa:
- Potpuno iskorištena (Vezujuća) ograničenja:
- Radni sati predstavnika: Iskoristili smo svih 2000 od 2000 dostupnih sati. (Slack = 0)
- Ukupna proizvodnja: Dosegli smo limit od 800 od 800 komada. (Slack = 0)
- Minimalna isporuka za maloprodaju: Proizveli smo točno 100 od 100 obveznih komada. (Surplus = 0)
- OVO SU NAŠA TRI “USKA GRLA”.
- Neiskorištena (Nevezujuća) ograničenja:
- Trošak oglašavanja: Imamo 100 € viška budžeta (iskorišteno 7100 od 7200).
- OVO TRENUTNO NIJE PROBLEM.
Ključne preporuke koje proizlaze iz analize osjetljivosti
Sjene cijena (Shadow Prices) nam govore koliko točno vrijedi (ili košta) svako ograničenje:
- Prioritet #1: Povećati “Ukupnu proizvodnju”
- Sjena cijene = 68.00 €
- Tumačenje: Za svaki 1 dodatni komad koji možemo proizvesti (povećanje limita s 800 na 801), naš ukupni profit raste za 68.00 €.
- Oprez: Ovo vrijedi samo dok limit ne poraste na ~809 komada.
- Preporuka: Ovo je naš najvrjedniji resurs. Prioritet treba biti ulaganje u povećanje ukupnog kapaciteta proizvodnje.
- Prioritet #2: Povećati “Radne sate predstavnika”
- Sjena cijene = 2.67 €
- Tumačenje: Za svaki 1 dodatni radni sat (s 2000 na 2001), naš ukupni profit raste za 2.67 €.
- Preporuka: Ako možemo dobiti prekovremeni sat za manje od 2.67 €, isplati se. Ovo vrijedi u rasponu od 1900 do 2500 sati.
- Problematično ograničenje: Minimalna isporuka (Z)
- Sjena cijene = -3.67 €
- Tumačenje: Negativna cijena za \(\ge\) ograničenje znači da nas ono košta. Za svaki 1 komad za koji povećamo obvezu (sa 100 na 101), naš ukupni profit PADA za 3.67 €.
- Preporuka: Pregovarati o smanjenju ove ugovorne obveze. Svaki komad manje obveze (na 99) donio bi nam 3.67 € profita.
- Ulaganje u “Oglašavanje” je nepotrebno
- Sjena cijene = 0 €
- Tumačenje: Budući da imamo 100 € viška budžeta, dodatno ulaganje u oglašavanje ne donosi nikakav dodatni profit (0 €).
Stabilnost optimalnog plana
- Proizvod X (Profit = 65 €): Ne proizvodimo ga. Njegov smanjeni trošak (Reduced Cost) je 11 €. To znači da bi mu profit trebao porasti s 65 € na 76 € (tj. za 11 €) prije nego što uopće postane isplativo proizvesti ga.
- Proizvod Y (Profit = 76 €): Ovo je naš “najprofitabilniji” proizvod u miksu. Njegov profit može pasti na 73.25 € prije nego se plan promijeni.
- Proizvod W (Profit = 68 €): Zanimljivo, profit ovog proizvoda može pasti na 0 €, a on bi i dalje ostao u planu proizvodnje.
Zaključak: Imamo jasan plan (0, ~533, 100, ~167) za maksimalni profit od 59,367 €. Da bi se dobit povećala, fokus mora biti na: 1) Povećanju ukupnog proizvodnog kapaciteta (vrijedi 68 €/kom), 2) Povećanju radnih sati (vrijedi 2.67 €/sat), i 3) Smanjenju ugovorne obveze za Proizvod Z (košta nas 3.67 €/kom).
Literatura
Ben-Tal, A., El Ghaoui, L., & Nemirovski, A. (2009). Robust
Optimization. Princeton University Press.
Birge, J. R., & Louveaux, F. (2011). Introduction to Stochastic Programming (2nd ed.). Springer.
Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press.
Gass, S. I. (2003). Linear Programming: Methods and Applications (5th ed.). Dover Publications. (Prvo izdanje 1958.)
Hadley, G. (1962). Linear Programming. Addison-Wesley.
Hillier, F. S., & Lieberman, G. J. (2021). Introduction to Operations Research (11th ed.). McGraw-Hill.
Kuhn, H. W., & Tucker, A. W. (Eds.). (1956). Linear Inequalities and Related Systems. Annals of Mathematics Studies, No. 38. Princeton University Press.
Lenstra, J. K., Rinnooy Kan, A. H. G., & Schrijver, A. (Eds.). (1991). History of Mathematical Programming: A Collection of Personal Reminiscences. North-Holland.
Schrijver, A. (1986). Theory of Linear and Integer Programming. Wiley.
Vanderbei, R. J. (2020). Linear Programming: Foundations and Extensions (5th ed.). Springer.
Winston, W. L., & Goldberg, J. B. (2004). Operations Research: Applications and Algorithms (4th ed.). Brooks/Cole.