Grafičko rješavanje linearnog programa

Grafičko rješavanje koristi se prvenstveno za dublje razumijevanje osnovnih principa LP-a. Primjenjivo je samo na probleme s dvije varijable odluke, ali omogućuje vizualizaciju ograničenja i funkcije cilja u ravnini. Ova metoda je posebno korisna jer pomaže razviti intuitivno razumjevanje osnovnih koncepata poput optimalnih rješenja, područja izvedivih rješenja i različitih tipova ograničenja.

Kako funkcionira grafičko rješavanje linearnog programa?

Grafičko rješavanje koristi dvodimenzionalnu geometriju za pronalaženje optimalnog rješenja problema linearne optimizacije. Postupak uključuje sljedeće korake:


  • Definiranje problema:

    • Funkcija cilja izražava što se optimizira (maksimizira ili minimizira). Na primjer:

    \[Z=c_1x_1+c_2x_2\]

    • Ograničenja su zapisana skupom linearnih nejednadžbi ili jednadžbi koje definiraju dopustivo područje. Na primjer:

    \[a_1x_1+a_2x_2≤b_1\]

    \[a_3x_1+a_4x_2≤b_2\]

    \[x_1,x_2≥0\]


  • Crtanje ograničenja:

    • Svako ograničenje se grafički prikazuje kao pravac u koordinatnom sustavu. Taj pravac odgovara jednadžbi dobivenoj iz ograničenja kada se znak nejednakosti (\(\leq\), \(\geq\)) zamijeni jednakosti (\(=\)).
    • Taj pravac dijeli ravninu na dva dijela: jedan dio predstavlja vrijednosti koje zadovoljavaju ograničenje, dok drugi dio predstavlja vrijednosti koje ne zadovoljavaju ograničenje.
    • Na primjer, \(x_1+2x_2≤8\) bi se prikazalo kao pravac \(x_1+2x_2=8\), a područje ispod pravca (ispod, zato jer je \(≤\)) predstavlja dio dopustivog skupa koji zadovoljava ograničenje.


  • Određivanje područja izvedivih rješenja:

    • Područje izvedivih rješenja je zajednički dio (presjek) svih poluravnina koje zadovoljavaju sva ograničenja.
    • Poluravnine se definiraju linearnih nejednadžbama, a presjek tih poluravnina geometrijski tvori područje mogućih kombinacija varijabli \(x_1\) i \(x_2\) koje su u skladu sa svim ograničenjima.
    • Ovo područje je uvijek konveksni poligon, što znači da svaka točka unutar poligona i svaka linija između bilo koje dvije točke unutar poligona također pripadaju tom području. Ta karakteristika je važna u linearnom programiranju jer osigurava da će optimalno rješenje uvijek biti na rubu, odnosno u jednom od vrhova poligona.
    • Područje izvedivih rješenja uključuje sve moguće vrijednosti \(x_1\) i \(x_2\) koje zadovoljavaju ograničenja i u kojima se funkcija cilja može optimizirati.


  • Crtanje funkcije cilja:

    • Funkcija cilja može poprimiti različite vrijednosti i crta se kao skup paralelnih pravaca u koordinatnom sustavu. Svaki pravac funkcije cilja predstavlja određenu vrijednost funkcije cilja, tj. određenu vrijednost \(Z\).
    • Na primjer, za \(Z=3x_1+2x_2\), pravac može prikazivati različite vrijednosti funkcije cilja, dok je nagib definiran koeficijentima uz \(x_1\) i \(x_2\). Na primjer, svaki pravac funkcije cilja definira određenu razinu \(Z\), kao što su \(Z=5\) (za \(x_1=1\) i \(x_2=1\)), \(Z=7\) (za \(x_1=1\) i \(x_2=2\)), \(Z=10\) (za \(x_1=2\) i \(x_2=2\)), itd. Ovi pravci su međusobno paralelni jer nagib svakog od njih ostaje konstantan. Konkretnije, nagib pravaca funkcije cilja određen je omjerom koeficijenata uz varijable, tj. \(-\frac{3}{2}\) (odnos koeficijenta \(x_1\) i \(x_2\) u ovom primjeru, a općenitije: \(- \frac{\text{koeficijent uz } x_1}{\text{koeficijent uz } x_2}\))


  • Pronalaženje optimalnog rješenja:

    • Optimalno rješenje linearnog programa uvijek se nalazi na rubu dopustivog područja, odnosno na jednom od vrhova poligona koji definira zajednički presjek svih ograničenja.
    • U slučaju maksimizacije, funkcija cilja se pomiče prema vanjskoj granici (gore i desno) područja izvedivih rješenja dok ne dodirne posljednju točku koja je unutar tog područja.
    • Za minimizaciju, proces je obrnut: funkcija cilja se pomiče prema unutrašnjosti dopustivog područja (dolje i desno) dok ne dotakne krajnji vrh.
    • Pomicanje funkcije cilja može se vizualizirati kroz paralelne pravce funkcije cilja koji se kreću u smjeru veće (ili manje) vrijednosti \(Z\). Važno je naglasiti da optimalno rješenje mora biti na jednom od vrhova jer je funkcija cilja linearna, a dopustivo područje je konveksno. Na konveksnom poligonu ekstremne vrijednosti funkcije cilja uvijek se nalaze na vrhovima.
    • Praktično, to znači da ispitujemo vrijednosti funkcije cilja u svakom vrhu poligona.
    • Na primjer, ako je funkcija cilja \(Z = 3x_1 + 2x_2\), a područje izvedivih rješenja je poligon s vrhovima \((x_1, x_2) = (0,0)\), \((10,0)\), \((6,6)\), i \((0,8)\), tada bismo izračunali \(Z\) za svaki vrh i odabrali najvišu vrijednost \(Z\) (za maksimizaciju) ili najnižu (za minimizaciju).


  • Provjera rješenja:

    • Kada su sve vrijednosti funkcije cilja u vrhovima poligona izračunate, one se uspoređuju kako bismo odredili optimalnu vrijednost.
    • Ako je problem maksimizacije, odabiremo vrh s najvećom vrijednosti funkcije cilja. Ako je problem minimizacije, odabiremo vrh s najmanjom vrijednosti funkcije cilja.
    • Provjera rješenja također pomaže u identifikaciji više mogućih optimalnih rješenja ako funkcija cilja postiže istu vrijednost u više od jedne točke (npr. kad se optimalna vrijednost nalazi na cijeloj dužini nekog ruba poligona).
    • Provjera omogućuje i uvide u to kako se funkcija cilja ponaša unutar granica dopustivog područja i jesmo li ispravno definirali geometriju problema.


1. primjer

Za početak ćemo koristiti najjednostavniji primjer iz prethodne lekcije. Radi se o proizvodnji stolova i stolica, za koje znamo profit i potrebno vrijeme izrade.

\(x_1\) predstavlja broj proizvedenih stolova, a \(x_2\) broj proizvedenih stolica. \(c_1=40\), \(c_2=50\) predstavljaju profit u eurima po proizvodu. Ograničenja su \(a_1=2\), \(a_2=1\), \(b_1=300\), što znači da proizvodnja zahtijeva dva sata rada za izradu jednog stola i jedan sat rada za izradu stolice, uz ukupno 300 sati dostupnih sati rada koji se mogu rasporediti na izradu stolova i stolica. Funkcija cilja postaje:

\(max\ 40x_1+50x_2\)

uz ograničenja:

\(2x_1+x_2≤300\)

\(x_1≥0\)

\(x_2≥0\)


Sad ćemo to grafički prikazati.

U koordinatni sustav ucrtali smo prvi pravac koji predstavlja ograničenje ukupnog vremena rada dostupnog za proizvodnju stolova i stolica. Ograničenje \(2x_1+x_2≤300\) znači da ukupno vrijeme koje se troši na izradu stolova i stolica ne smije premašiti 300 sati. Pravac \(2x_1+x_2=300\) označili smo plavom bojom i osjenčali područje ispod pravca (područje izvedivih ili dopuštenih rješenja, \(2x_1+x_2≤300\)) svijetlo sivom bojom.

Zatim smo dodali pravac \(x_2=0\), koji predstavlja uvjet da broj proizvedenih stolica ne može biti negativan, odnosno granicu područja \(x_2≥0\). Ovaj pravac je obojen zelenom bojom, a područje iznad pravca dodatno smo osjenčali sivom bojom. Područje preklapanja površina ovih dvaju ograničenja može se uočiti kao tamnija površina na grafu.

Nakon toga, nacrtali smo pravac \(x_1=0\), koji osigurava da broj proizvedenih stolova ne može biti negativan. Taj pravac je obojen narančasto, a područje (\(x_1≥0\)) desno od pravca osjenčano je sivom bojom.

U ovom slučaju imamo samo tri ograničenja i ona kreiraju površinu mogućih ili izvedivih rješenja. Bilo koja točka unutar ograničene površine (najtamnija nijansa u obliku trokuta, u ovom slučaju) predstavlja izvedivo rješenje. Ali nas ne zanima bilo koje izvedivo rješenje, zanima nas ono za koje funkcija cilja poprima najveću vrijednost. Funkcija cilja je dana kao maksimizacija \(40x_1+50x_2\) i možemo lako uočiti da će vrijednost biti veća za veće vrijednosti \(x_1\) i \(x_2\). pravo veće vrijednosti \(x_1\) i \(x_2\) očekujemo naći na rubnim dijelovima označene površine, preciznije za točke na vrhovima lika kreiranog ograničenjima. S obzirom na to, ispitujemo vrijednosti funkcije cilja u tim točkama.

Dakle, dodajemo funkcije cilja \(Z=40x_1+50x_2\), odnosno, pripadajuće pravce koji prolaze vrhovima lika (poligona), koje prikazuju kako se profit mijenja ovisno o kombinaciji proizvedenih stolova i stolica. Pravci funkcije cilja crtani su tamnocrvenom bojom i prikazuju konstantne razine profita u promatranim točkama. Kako se pravci pomiču prema desno-gore, tako se povećava i vrijednost funkcije cilja.

Točke vrhova poligona smo označili crvenim točkama i dodali oznake s pripadajućim koordinatama i vrijednostima funkcije cilja u svakom vrhu. Tako smo identificirali optimalnu točku u kojoj funkcija cilja poprima najveću vrijednost.

Točka x1 x2 Z
Vrh 1 0 0 0
Vrh 2 150 0 6000
Vrh 3 0 300 15000

Najveći profit postiže se u točki \(x_1=0\), \(x_2=300\), gdje je funkcija cilja \(Z=15000\). To znači da bismo trebali proizvesti 0 stolova i 300 stolica kako bismo ostvarili najveći mogući profit (15000 €) uz zadanih 300 sati rada.

Ovaj rezultat jasno pokazuje da je profit najveći ako se svi dostupni resursi usmjere na proizvodnju stolica. To zapravo sugerira strategiju proizvodne specijalizacije, gdje se umjesto diversifikacije proizvodnje (stolova i stolica), fokusiramo isključivo na proizvodnju proizvoda koji donosi najveći profit u odnosu na uložene resurse. Ako interpretiramo šire, ovo također ukazuje na važnost razumijevanja relativne profitabilnosti proizvoda unutar dostupnih resursa. Budući da stolice zahtijevaju manje resursa po jedinici i donose veći profit po jedinici radnog vremena, njihova proizvodnja je ekonomski isplativija u danim uvjetima.

Pitanja za razmišljanje:

  1. Što bi se dogodilo s optimalnim rješenjem kada bi maksimalno dostupno vrijeme rada poraslo s 300 na 400 sati? Kako biste to grafički prikazali?

  2. Što ako stolovi donose 60 € profita, a stolice 50 €? Kako biste prilagodili funkciju cilja i kako bi se to odrazilo na optimalno rješenje?

  3. Pretpostavimo da proizvodnja stolova zahtijeva minimalno 50 komada zbog ugovora s klijentom. Kako biste to uključili u model i kako bi to utjecalo na rješenje?

  4. Što se događa s dopustivim područjem ako se doda novo ograničenje \(x_1 + x_2 ≤ 100\)?

  5. Može li postojati više optimalnih rješenja za ovu funkciju cilja? Ako da, pod kojim uvjetima?



2. Primjer

U eri digitalizacije, Tvrtka “Terijum” se okreće budućnosti tehnološki potkovanih poslovnih prostora, gdje Internet stvari (IoT) igra ključnu ulogu u redefiniranju načina na koji interakcija i operativna efikasnost oblikuju radno okruženje. Svjesni potencijala koji IoT nosi, od automatizacije do optimizacije resursa, Terijum nastoji uskladiti svoj radni prostor s vizijom visoko povezanog i inteligentnog ureda. S inicijativom da se premoste tradicionalni pristupi upravljanja uredom, integracijom pametnih tehnologija ciljaju na znatne uštede u vremenu i financijama, dok istovremeno postavljaju temelje za održiv i ekološki osviješten radni prostor. U ovom procesu modernizacije, ključan je pažljivo promišljen proračun koji omogućuje da svaka investicija u IoT rješenja donese mjerljive benefite i dugoročno pozitivno utječe na operativnu efikasnost i troškove. Terijum se stoga usmjerava na strateški pristup koji će osigurati da svaki euro uložen u modernizaciju bude korak prema inovativnom i naprednom poslovanju.

Tvrtka “Terijum” poduzima korake ka modernizaciji svog uredskog prostora implementacijom različitih IoT rješenja s ciljem povećanja učinkovitosti i smanjenja operativnih troškova. S obzirom na ograničenja proračuna, ključno je strateški rasporediti dostupna sredstva kako bi se maksimizirale očekivane godišnje uštede.

Tvrtka razmatra investicije u dva glavna područja IoT rješenja:

  • Senzore za osvjetljenje koji se automatski prilagođavaju svjetlosnim uvjetima, donoseći tjedne uštede od 0,5 EUR za svaki uloženi euro.
  • Uređaje za kontrolu klime koji optimiziraju temperaturu prema broju ljudi u prostoriji, s očekivanom tjednom uštedom od 0,6 EUR za svaki uloženi euro.

Proračun namijenjen za ovu investiciju iznosi 70.000 EUR, a potrebno je uzeti u obzir minimalna i maksimalna ograničenja ulaganja za svaku tehnologiju. Tablica ispod prikazuje očekivane uštede po uloženom euru, kao i minimalna i maksimalna ulaganja za svako područje:

IoT rješenje Uštede (po uloženom EURu) Min. ulaganje (EUR) Maks. ulaganje (EUR)
Senzori za osvjetljenje 0.5 10000 40000
Uređaji za kontrolu klime 0.6 15000 35000

Terijum treba odlučiti kako najučinkovitije alocirati svoj proračun među navedenim IoT rješenjima kako bi postigao najveće moguće tjedne uštede unutar postavljenih financijskih ograničenja.

Varijable odluke:

  • Količina novca uloženog u IoT senzore za osvjetljenje koji se automatski prilagođavaju svjetlosnim uvjetima - \(x_1\) u EUR.
  • Količina novca uloženog u IoT uređaje za kontrolu klime koji optimiziraju temperaturu prema broju ljudi u prostoriji - \(x_2\) u EUR.

Funkcija cilja (maksimizacija ušteda): \(Z = 0.5 \cdot x_1 + 0.6 \cdot x_2\)

Ograničenja:

  • Ukupan proračun za IoT implementaciju je 100000 EUR: \(x_1 + x_2 \leq 70000\).
  • Minimalna investicija u senzore za osvjetljenje je 10000 EUR: \(x_1 \geq 10000\).
  • Minimalna investicija u uređaje za kontrolu klime je 15000 EUR: \(x_2 \geq 15000\).
  • Maksimalna investicija u senzore za osvjetljenje je 40000 EUR: \(x_1 \leq 40000\).
  • Maksimalna investicija u uređaje za kontrolu klime je 35000 EUR: \(x_2 \leq 35000\).


Cijeli grafički prikaz smješten je u prvi kvadrant. Na taj način ujedno su predstavljene granice vrijednosti varijabli \(x_1\) (količina novca uloženog u IoT senzore) i \(x_2\) (količina novca uloženog u IoT uređaje za kontrolu klime), to jest \(x_1, x_2 \geq 0\).

Zatim smo nacrtali pravac koji predstavlja ograničenje proračuna: \(x_1+x_2=70,000\). To je pravac obojan plavom bojom, koji dijeli ravninu na dva područja: područje izvedivih ili dopuštenih rješenja, obojano svijetlo plavom bojom (\(x_1+x_2≤70,000\), ispod pravca), i područje neizvedivih rješenja (iznad pravca).

Sljedeći korak je dodavanje pravca koji predstavlja minimalno ulaganje u senzore, \(x_1 = 10000\) i taj je pravac označen zelenom bojom. Površina \(x_1 \geq 10000\) definirana ovim ograničenjem obojana je svijetlo zelenom bojom (desno od pravca).

Nakon toga, dodali smo pravac koji predstavlja minimalno ulaganje u uređaje za kontrolu klime, \(x_2 = 15000\), obojan narančasto. Područje iznad ovog pravca, \(x_2 \geq 15000\), označava je svijetlo narančastom bojom.

Potom crtamo pravac koji predstavlja maksimalno ulaganje u senzore, \(x_1 = 40000\), ljubičastom bojom. Površina pod tim pravcem, \(x_1 \leq 40000\), osjenčana je kako bi se vizualiziralo područje ograničenja.

Slijedi ograničenje maksimalnog ulaganja u uređaje za kontrolu klime, \(x_2 = 35000\), obojano crvenom bojom. Vezana površina, \(x_2 \leq 35000\), osjenčana je svijetlo crvenom bojom.

U presjeku površina svih ovih ograničenja nalazi se područje mogućih ili izvedivih rješenja, naznačeno sivom bojom. Bilo koja od točaka unutar ove površine može biti rješenje - ali nas zanima ono rješenje u kojoj funkcija cija, \(0.5x_1+0.6x_2\) poprima najveće vrijednosti. Najveće vrijednosti će poprimiti u točkama koje se nalaze na rubu označene površine, odnosno u vrhovima koje ovaj poligon čini. Dakle, sljedeći je korak ispitati vrijednosti koje funkcija cilja poprima u vrhovima. Identificirani su vrhovi:

Točka x1 x2
Vrh 1 10000 15000
Vrh 2 40000 15000
Vrh 3 40000 30000
Vrh 4 35000 35000
Vrh 5 10000 35000

Nacrtano je 5 pravaca funkcije cilja \(0.5x_1+0.6x_2\), koji prolaze kroz točke vrhova. Ovi pravci prikazuju kako se vrijednost funkcije cilja mijenja dok se pomičemo unutar dozvoljenog područja. Svaki od tih pravaca obojen je tamnocrvenom bojom, a kako se vrijednost funkcije cilja povećava, pravci se pomiču prema gore i desno.

Nakon što su pravci funkcije cilja nacrtani, fokusiramo se na ključne točke presjeka i izračunavamo vrijednost funkcije cilja u svakoj od utvrđenih točaka:

Točka x1 x2 Z
Vrh 1 10000 15000 14000
Vrh 2 40000 15000 29000
Vrh 3 40000 30000 38000
Vrh 4 35000 35000 38500
Vrh 5 10000 35000 26000

Uočavamo da funkcija cilja poprima najveću vrijednost za \(x_1 = 35000\) i \(x_2 = 35000\) i iznosi \(38500\). Dakle, to će biti rješenje promatranog problema. Temeljem toga, možemo preporučiti tvrtci Terijum da svoj proračun podjednako alocira na senzore za osvjetljenje i uređaje za kontrolu klime, pri čemu će ostvariti najveće moguće uštede uz dana financijska ograničenja. Preciznije, tjedne uštede će iznositi 38500 €.

Pitanja za razmišljanje:

  1. Što bi se dogodilo s optimalnim rješenjem kada bi ukupni budžet porastao na 100000 EUR? Kako biste to prikazali grafički?

  2. Ako bi senzori za osvjetljenje postali skuplji za implementaciju i donijeli manju uštedu od 0,4 EUR po uloženom euru, kako bi to utjecalo na optimalno ulaganje?

  3. Što ako je postojalo dodatno ograničenje da ulaganje u senzore za osvjetljenje mora biti najmanje 45000 EUR? Kako biste to dodali modelu i kako bi to utjecalo na optimalno rješenje?

  4. Može li se dogoditi da budžet ostane neiskorišten? Ako da, pod kojim uvjetima?

  5. Kako biste preporučili alokaciju sredstava ako je cilj minimizirati inicijalne troškove, a ne maksimizirati uštede?



3. Primjer

Zamislimo situaciju u kojoj se bavimo proizvodnjom dvije vrsta majica: majica s kratkim rukavima (\(x\)) i majica s dugim rukavima (\(y\)). Svaka od ovih majica ima različite zahtjeve za materijalima, a naš je cilj maksimizirati profit. Profit za svaku proizvedenu majicu s kratkim rukavima iznosi 10 €, dok je profit za majicu s dugim rukavima 15 €. Funkcija cilja, koju pokušavamo maksimizirati, stoga glasi:

\[max\ 10x+15y\]

gdje \(x\) predstavlja broj proizvedenih majica s kratkim rukavima, a \(y\) broj majica s dugim rukavima. Ova funkcija cilja nam govori koliko ćemo zaraditi, ovisno o kombinaciji proizvedenih majica obje vrste.

Međutim, naša proizvodnja nije neograničena jer smo suočeni s ograničenjima resursa, odnosno količinom materijala koje imamo na raspolaganju za proizvodnju u ovom mjesecu. Svaki tip majice zahtijeva određenu količinu različitih materijala: konac, pamučni materijal, saten i čipku. Ta ograničenja su važna jer određuju izvedive kombinacije \(x\) i \(y\) koje možemo proizvesti.

Prvo ograničenje odnosi se na dostupnu količinu konca. Za svaku majicu s kratkim rukavima potrebno je 0.75 metara konca, dok je za majicu s dugim rukavima potrebno 1 metar konca. Ukupno raspolažemo s 7000 metara konca. Ovo ograničenje možemo zapisati kao:

\[0.75x+1y≤7000\]

Drugo ograničenje vezano je uz pamučni materijal. Majice s kratkim rukavima troše 0.45 \(m^2\) pamučnog materijala, dok majice s dugim rukavima troše 0.85 \(m^2\) pamučnog materijala. Ukupno na raspolaganju imamo 5500 \(m^2\) pamučnog materijala. Ovo ograničenje glasi:

\[0.45x+0.85y≤5500\]

Treće ograničenje odnosi se na saten, gdje svaka majica s kratkim rukavima zahtijeva 0.95 \(m^2\) satena, dok majica s dugim rukavima zahtijeva 0.65 \(m^2\) satena. Ukupna raspoloživa količina satena iznosi 6100 \(m^2\). Ovo ograničenje zapisujemo kao:

\[0.95x+0.65y≤6100\]

Četvrto ograničenje tiče se čipke, koju svaka majica s kratkim rukavima troši u količini od 0.25 m, dok majica s dugim rukavima troši 0.2 m čipke. Ukupno raspoloživo imamo 1700 m čipke. Ovo ograničenje glasi:

\[0.25x+0.2y≤1700\]

Uz ova četiri ograničenja, postavljamo i osnovne uvjete da proizvodnja ne može biti negativna, odnosno da \(x≥0\) i \(y≥0\).

Naš zadatak je sada grafički prikazati ova ograničenja i definirati područje mogućih, izvedivih rješenja. To područje predstavlja presjek svih površina definiranih gore navedenim nejednadžbama. Bilo koja kombinacija \(x\) i \(y\) unutar tog područja zadovoljava sva ograničenja i može se smatrati izvedivim rješenjem. Međutim, nas zanima optimalno rješenje, odnosno ona kombinacija \(x\) i \(y\) koja maksimizira funkciju cilja \(10x+15y\).


Prvo ćemo grafički prikazati svaki od pravaca koji predstavljaju gornje granice pojedinih ograničenja. Površine ispod svakog pravca predstavljaju područja koja zadovoljavaju ta ograničenja. Zatim ćemo označiti područje preklapanja svih tih površina, koje čini dozvoljeno područje rješenja. Na kraju, usmjerit ćemo pažnju na vrhove tog poligona dozvoljenih rješenja jer optimalno rješenje mora biti u jednoj od tih točaka. Izračunavanjem vrijednosti funkcije cilja za svaki vrh, odabrat ćemo onu kombinaciju \(x\) i \(y\) koja daje maksimalan profit.

Rezultati će nam omogućiti da donesemo odluku o optimalnoj alokaciji materijala za proizvodnju majica kako bismo ostvarili maksimalnu zaradu uz ograničene resurse.

Grafički prikaz smještamo u prvi kvadrant, gdje os \(x\) predstavlja broj proizvedenih majica kratkih rukava, a os \(y\) broj proizvedenih majica dugih rukava. Na taj način osigurano je i poštivanje ograničenja \(x, y \geq 0\), iako ih nismo zasebno iscrtavali. Svako ograničenje prikazali smo kao pravac u ovom sustavu.

Prvo smo nacrtali pravac \(0.75x+1y=7000\), koji predstavlja gornju granicu za potrošnju konca. Područje ispod ovog pravca, odnosno \(0.75x+1y \leq 7000\), obojano je svijetlo plavom bojom, što predstavlja sve moguće kombinacije \(x\) i \(y\) koje ne premašuju dostupnu količinu konca.

Zatim smo dodali ograničenje za pamučni materijal, \(0.45x+0.85y=5500\). Taj pravac označili smo zelenom bojom, a područje ispod njega, odnosno \(0.45x+0.85y \leq 5500\) dodatno osjenčali svijetlo zelenom bojom, što pokazuje dopuštene kombinacije s obzirom na količinu pamučnog materijala.

Treće ograničenje odnosi se na saten, \(0.95x+0.65y=6100\). Taj pravac nacrtali smo narančastom bojom, a područje ispod njega, odnosno \(0.95x+0.65y \leq 6100\), osjenčali svijetlo narančastom bojom, označavajući sve izvedive kombinacije koje ne premašuju dostupnu količinu satena.

Četvrto ograničenje, \(0.25x+0.2y=1700\), prikazali smo ljubičastom bojom. Površina ispod ovog pravca koja se odnosi na \(0.25x+0.2y \leq 1700\), osjenčana je svijetlo ljubičastom bojom, što označava područje izvedivih rješenja s obzirom na količinu čipke.

Presjek svih osjenčanih površina definira područje izvedivih rješenja. Ovaj poligon pokazuje sve moguće kombinacije \(x\) i \(y\) koje zadovoljavaju sva ograničenja. Svaka točka unutar ovog poligona predstavlja izvedivo rješenje problema, dok su točke na rubovima ključne jer upravo tamo funkcija cilja postiže svoje ekstremne vrijednosti.

Kako bismo vizualizirali kako se profit mijenja, dodali smo pravce funkcije cilja \(Z=10x+15y\). Ovi pravci crtani su tamnocrvenom bojom i pokazuju različite razine profita za određene kombinacije \(x\) i \(y\). Pomicanjem pravaca prema gore i desno postiže se veća vrijednost funkcije cilja.

Identificirali smo vrhove poligona koji čine izvedivo područje. Ti vrhovi su vrlo važni jer optimalno rješenje problema mora biti u jednoj od tih točaka. Izračunali smo vrijednosti funkcije cilja za svaki od vrhova:

Točka x y Z
Vrh 1 0 0 0
Vrh 2 6421.05 0 64210.53
Vrh 3 4181.82 3272.73 90909.09
Vrh 4 3000 4750 101250
Vrh 5 2400 5200 102000
Vrh 6 0 6470.59 97058.82

Uočili smo da funkcija cilja postiže maksimalnu vrijednost u točki \(x=2400\), \(y=5200\), gdje je \(Z=102000\). Drugim riječima, s obzirom na dostupne resurse, optimalna proizvodnja bila 2400 majica s kratkim rukavima i 5200 majica s dugim rukavima, pri čemu bismo ostvarili maksimalan profit od 102000 €.

Ova analiza jasno pokazuje kako učinkovito raspodijeliti resurse kako bismo maksimizirali profit. Rezultati sugeriraju da je u danim uvjetima proizvodnja usmjerena prema većoj količini majica s dugim rukavima isplativija zbog njihovog većeg doprinosa ukupnom profitu. Ova strategija omogućava optimalno korištenje dostupnih resursa i maksimizaciju zarade, što je ključno za dugoročno planiranje proizvodnje i upravljanje resursima.

Pitanja za razmišljanje:

  1. Što bi se dogodilo kada bi dostupna količina čipke bila povećana na 2500 m? Kako bi se to odrazilo na dopustivo područje?

  2. Što ako su majice s kratkim rukavima postale manje profitabilne i sada donose samo 7 € po komadu? Kako bi se promjena u funkciji cilja odrazila na rješenje?

  3. Ako bi minimalni broj proizvedenih majica s kratkim rukavima morao biti 1000 zbog ugovora, kako biste prilagodili model i kako bi se promjena odrazila na rješenje?

  4. Može li se dogoditi da optimalno rješenje uključuje proizvodnju samo jedne vrste majica (kratkih ili dugih rukava)? Ako da, pod kojim uvjetima?

  5. Pretpostavite da se maksimalno raspoloživo vrijeme za sve resurse smanjuje za 20%. Kako biste to implementirali u model i kako bi se to odrazilo na rješenje?

Rezime

Grafičko rješavanje linearnog programa (LP) predstavlja jednostavan, vizualno intuitivan pristup razumijevanju osnovnih koncepata optimizacije. Omogućava prikaz ograničenja i funkcije cilja u dvodimenzionalnom prostoru i pomaže nam razumjeti ključne elemente LP-a, kao što je način na koji ograničenja oblikuju područja izvedivih rješenja.

Proces grafičkog rješavanja započinje definiranjem funkcije cilja i ograničenja. Funkcija cilja izražava što se optimizira, dok ograničenja predstavljaju linearne nejednadžbe (ili rjeđe, jednadžbe) koje definiraju resurse ili druge uvjete problema. Svako ograničenje grafički se prikazuje kao pravac, a područje ispod ili iznad pravca (ovisno o smjeru nejednadžbe) predstavlja dozvoljene vrijednosti varijabli odluke. Presjek svih dopuštenih područja definira izvedivo područje, obično u obliku poligona.

Funkcija cilja se vizualizira pomoću paralelnih pravaca koji prikazuju različite razine optimizacije, pri čemu se optimalno rješenje pronalazi pomicanjem funkcije cilja prema vanjskoj granici izvedivog područja. Specifičnost grafičkog rješavanja je da se optimalno rješenje uvijek nalazi u jednom od vrhova poligona koje označava područje izvedivih rješenja. Zbog toga se za svaki vrh izračunava vrijednost funkcije cilja, a najveća (ili najmanja, ovisno o cilju) vrijednost daje optimalno rješenje.

U prikazanim primjerima grafički smo analizirali i rješavali linearne programe različitih složenosti. Vizualizacijom ograničenja i funkcije cilja jasno su prikazani odnosi između varijabli odluke i utjecaj svakog ograničenja na prostor mogućih rješenja. Identificirali smo optimalne kombinacije odluka i interpretirali ih u kontekstu problema. Grafički pristup ne samo da je pružio rješenje problema već je i omogućio dublje razumijevanje odnosa između varijabli, ograničenja i funkcije cilja.

Primjeri koji su ovdje korišteni namjerno su jednostavni i idealizirani kako bi ilustrirali osnovne principe LP-a na razumljiv način. U stvarnim situacijama problemi linearnog programiranja često uključuju više varijabli odluke i kompleksnija ograničenja, zbog čega grafički pristup postaje nepraktičan. Međutim, ovakvi jednostavni primjeri omogućuju čvrste temelje za razumijevanje LP-a, što je preduvjet za primjenu naprednijih metoda poput simpleks algoritma ili korištenja softverskih alata za rješavanje složenih problema.

Pri kreiranju grafičkih prikaza mogu nam pomoći različiti alati, kao na primjer R i paket ggplot2, ali i postojeće aplikacije namijenjene grafičkom prikazu rješavanja linearnog programa, kao na primjer:

Interaktivna web aplikacija za linearno programiranje s dvije varijable

Linear programming grapher

PHPSimplex