Linearno Programiranje

Piše: Harun Kuč dipl. ing. el.

U organizovanju raznih privrednih aktivnosti u različitim područjima, linearno programiranje ima različitu primjenu, što zavisi od vrste preduzeća, karaktera proizvodnje, ili predmeta istraživanja. Linearnim programiranjem rješavaju se problemi u kojima se postavljaju zahtjevi određivanja maksimalne ili minimalne vrijednosti jedne veličine pri unaprijed datim, odnosno poznatim ograničavajućim uslovima. Pretpostavimo, da raspolažemo ograničenim količinama različitih vrsta sredstava (proizvodni, skladišni, transportni kapaciteti, energija, novčana sredstva, investiciona sredstva, kreditne mogućnosti i tako dalje) koja možemo koristiti na različite načine, to jest za ostvarenje većeg broja mogućih aktivnosti, u cilju postizanja određenog ekonomskog efekta. Treba odabrati takvu kombinaciju mogućih aktivnosti koja će u okviru raspoloživih sredstava, a vodeći računa o konkretnim uslovima poslovanja (tehnološki uslovi, tržišni uslovi, ugovorne i druge obaveze, itd.) osigurati maksimalni mogući ekonomski efekt (na primjer, maksimalni dohodak). Takvom ćemo kombinacijom aktivnosti raspoloživa ograničena sredstva iskoristiti na optimalan način. U ovom tipu problema radi se, dakle, o tome da raspoloživa sredstva možemo koristiti na različite načine pa tražimo takav način koji će nam omogućiti da postignemo maksimalno mogući ekonomski efekt. Pored ovog tipa problema često postoje različite mogućnosti da se neki određeni ekonomski cilj ostvari. Svaka od tih mogućnosti iziskuje različite troškove, pa treba odabrati takvu mogućnost koja će iziskivati najmanje moguće troškove. Naravno, u ovom slučaju se radi o problemu minimuma. Sada ćemo na tipičnim primjerima problema maksimuma i minimuma pokazati kako se svi elementi relevantni za rješenje određenog praktičnog problema na matematički način formulišu u obliku linearnog programa. Za rješavanje ovakvih tipova problema koristićemo se ugrađenim alatom za analizu rezultata pod imenom Solver u proračunskoj tablici Excel, te paralelno, specijalizovanim softverima Mathematica 3.0 i Scientific Work Place 3.0. Naravno, da ovakav pristup iz postojećeg seta alata za analizu rezultata u Excelu daje prednost alatu SOLVER nad ostalim alatima kao što su: DATA TABLE (kojim se vrši analiza rezultata promjenom vrijednosti jednog ili dvaju ulaznih podataka), SCENARIO MANAGER (kojim se vrši analiza rezultata promjenom vrijednosti više ulaznih podataka), i GOAL SEEK (kojim se postiže tačno određeni rezultat promjenom jednog ulaznog podatka). Pomoću Solvera za određeni model se može pronaći ne samo određeno rješenje već i optimalno ili najbolje rješenje. Za potpuno iskorištenje mogućnosti alata Solver važno je u modelu dobro razumjeti međusobnu zavisnost između ulaznih podataka i formula.

Modeli koji se rješavaju pomoću Solvera imaju sljedeće karakteristike:  model mora imati samo jedno rješenje, na primjer, maksimizirati dobit ili minimizirati troškove,  model mora u sebi imati neka ograničenja koja se izražavaju pomoću jednakosti ili nejednakosti,  model mora imati ulazne vrijednosti koje su direktno ili indirektno kod izračunavanja povezane i s ograničenjima i s konačnim ciljem. Sa matematičkog stanovišta u osnovi se svi modeli mogu podijeliti na linearne i nelinearne modele. Mi ćemo se ovdje baviti rješavanjem linearnih modela kod kojih je odnos između ulaznih podataka i rezultata linearan, što znači da povećanje ulaznih vrijednosti proporcionalno povećava rezultat. Grafički, linearni model odgovara pravoj liniji koja je u odnosu na x osu postavljena pod nekim uglom. Napominjemo, da se kod nelinearnih modela koje takođe može obrađivati alat za analizu rezultata Solver, povećanjem ulaznih vrijednosti ne povećava proporcionalno i rezultat. Na jednostavnom primjeru se vidi kako se postavlja problem linearnog programiranja. Pretpostavimo da preduzeće proizvodi dva proizvoda, A i B, koji u procesu proizvodnje prolaze kroz dva različita pogona. Na slici 1. su dati podaci koji pokazuju potrebno vrijeme u časovima za proizvodnju jedinice proizvoda A i B, kao i ukupan fond časova pojedinih pogona u određenom periodu (dan, nedjelja, mjesec). Drugim riječima, za proizvodnju jedne jedinice proizvoda A utrošen je jedan čas u prvom i 5 časova u drugom pogonu. Za proizvodnju jedne jedinice proizvoda B utrošeno je tri časa u prvom, odnosno dva časa u drugom pogonu. Pored toga raspoloživi fond časova prvog i drugog pogona iznosi 18, odnosno 25 časova. U posljednjem redu dat je dohodak po jedinici proizvoda, koji za proizvod A iznosi 5 a za proizvod B, 6 novčanih jedinica.

Slika 1. Postavlja se pitanje kako odrediti program proizvodnje tako da dohodak preduzeća bude maksimalan pri datim ograničavajućim uslovima. Ako sa x označimo broj jedinica proizvoda A, a s y broj jedinica proizvoda B, tada je dohodak od proizvoda A, 5*x, a od proizvoda B, 6*y, što ukupno daje: f = 5x+6y gdje f označava ukupan dohodak. Jednačinu f = 5x+6y nazivamo funkcijom kriterijuma ili funkcijom cilja. Na sličan način se formulišu i ostale relacije koje se tiču tehničkotehnoloških uslova proizvodnje, odnosno ograničavajući uslovi proizvodnje po pojedinim pogonima. Ovaj se problem sada može formulisati na sljedeći način: Odrediti program proizvodnje preduzeća tako da dohodak bude maksimalan, to jest: (max) f =5x+6y pri ograničavajućim uslovima:

x  3  y  18 5  x  2  y  25 x  0, y  0

Ovim je postavljen problem linearnog programiranja. Rješenje problema (x,y) daje odgovor na pitanje koliko treba proizvoditi jedinica proizvoda A, a koliko jedinica B da bi se ostvario maksimalan dohodak. Sada ćemo krenuti u potrazi za rješenjem ovog problema posredstvom ugrađenog alata za analizu rezultata Solvera. Postupak korištenja ovog alata opisan je u nastavku u nekoliko dijelova. Sadržaj polja ćelija B1:B5 odgovara proizvoljnim, inicijalnim vrijednostima. Takođe je lako uočljivo kako se poziva alat za analizu rezultata, Solver (prema slici 2.). U ćeliji B5 je upisana funkcija cilja (max) f =5x+6y.

Slika 2. U prvom dijelu se Solveru naznačuje u kojoj ćeliji se nalazi funkcija cilja (slika 3.) koja se upisuje u okvir dijaloga Solver Parameters kada je tačka unosa u okviru Set Target Cell. Vidimo da je upisana apsolutna adresa ćelije $B$5. Takođe je označena priroda funkcije cilja, što u našem primjeru odgovara maksimumu funkcije, pa je uključena opcija Max.

Slika 3. U drugom dijelu treba naznačiti kojim će ćelijama Solver mijenjati vrijednosti, dok ne postigne vrijednost, navedenu u prethodnom koraku.

Na slici 4. vidimo, da će ćelijama $B$1 i $B$2 Solver mijenjati vrijednost na putu do cilja.

Slika 4. U trećem dijelu postupka (slika 5.) se naznačuju ograničenja ćelija: U okviru dijaloga Solver Parameters treba aktivirati gumb Add. Nakon pojave dijaloga Add Constraint tačka unosa je okviru Cell Reference. U ovaj okvir treba upisati ograničenje pri traženju rezultata.

Slika 5. Nakon upisanih ograničenja pojavljuje se okvir dijaloga Solver Parameters kao na slici 6.

Slika 6. Sada je potrebno aktivirati gumb Solve da pokrene traženje rezultata. Ako je Excel pronašao traženu vrijednost pod navedenim ograničenjima, upisati će u tablicu nove vrijednosti. Istovremeno će se pojaviti okvir dijaloga Solver Results u kojem se nalazi obavještenje je li pronađeno rješenje (slika 7.). Vidimo da rješenje x =3, y =5 ukazuje na to

da preduzeće, pod datim uslovima , treba da proizvodi 3 jedinice proizvoda A i 5 jedinica proizvoda B da bi ostvarilo maksimalni dohodak. (max) f =5*3+6*5=45.

Slika 7. Aktiviranjem gumba OK, vrijednosti će biti upisane u tablicu. Ako se odabere opcija Restore Original Values i nakon toga aktivira se gumb OK, nove vrijednosti zamijeniti će se starima. Na slici 6. je lako uočljivo na koji način se mogu vršiti izmjene u ograničenjima ili brisanje istih, ako je to potrebno. Na slici 7. uočavamo da pronađene vrijednosti koje zadovoljavaju postavljene uslove možemo postaviti u Scenario Manager. Klikom na gumb Save Scenario… pojavit će se okvir Save Scenario, kao na slici 8. Potrebno je aktivirati gumb OK. Rezultate dobijene pomoću Solvera i postavljene u scenarij možemo ponovo postaviti u model ako se izvede naredba Tools, Scenario… U okviru dijaloga Scenario Manager možemo pronaći ime scenarija kao na slici 9.

Slika 8. Treba naglasiti da se uslovi rada alata za analizu rezultata Solver, mogu promijeniti u okviru dijaloga Solver Parameters aktiviranjem gumba Options kao na slici 10.

Slika 10.

Sada ćemo isti primjer linearnog programiranja uraditi u programima Mathematica 3.0 i Scientific Work Place 3.0.  Mathematica 3.0



Scientific Work Place 3.0

Ograničavajući uslovi mogu biti postavljeni mnogo šire, tako da obuhvate elemente u vezi sa tržištem, snabdijevanjem, uvozom, izvozom, planskim zadacima, i tako dalje. Tada problem postaje mnogo složeniji. Pretpostavimo da pored ograničenja u pogledu tehničko-tehnoloških uslova proizvodnje posmatramo još dva, i to: ograničenja u pogledu realizacije i izvoza. Neka su ta ograničenja izražena sljedećim relacijama:

7x  4 y  28  realizacija  x  2 y  2  izvoz Sa dodatnim uslovima, prvobitno posmatran problem može se formulisati:

(max)f  5x  6y pri ograničavajućim uslovima:

x  3 y  18 5 x  2 y  25 7 x  4 y  28  x  2y  2 x  0, y  0 U ovom primjeru proširenje ograničavajućih uslova nije dovelo do promjene rješenja. Primjera radi, u programu Mathematica 3.0 uz promijenjene uslove, sada imamo:

Još jedan primjer maksimuma Fabrika automobila izrađuje tri vrste vozila u tri bazična pogona. Tehničko-tehnološki uslovi proizvodnje, kao i dobit po jedinici ( 1 jedinica =1000 vozila), dati su sljedećom tabelom na slici.

Problem se može izraziti na sljedeći način:

(max) f  15 x  20 y  25 z 2 x  2 y  z  100 y  2 z  95 3 x  y  90 x  0 , y  0 , z  0 Na isti način kao u prethodnom primjeru, dolazimo do rješenja koje odgovara maksimumu funkcije f. Vrijednosti u polju ćelija B1:B7 su inicijalne, proizvoljne početne vrijednosti koje nam pomažu da postavimao model.

Slika 11. Na slici 12. su data rješenja koja odgovaraju maksimumu ukupne dobiti.

Slika 12. Prema uslovima zadatka, optimalno rješenje kazuje da fabrika automobila treba da proizvodi godišnje 26250 lakih vozila, 47500 kamioneta da bi ostvarila maksimalnu dobit u visini od 1581,25 miliona novčanih jedinica.

Zamjenom vrijednosti iz optimalnog rješenja u sistem ograničavajućih uslova, dolazimo do zaključka da su kapaciteti prvog i drugog pogona u potpunosti iskorišteni, a da kapaciteti trećeg pogona nisu iskorišteni za 11,25 %. Do istog rješenja u programu Mathematica 3.0 dolazimo na sljedeći način:

Za sve ovo, potreban je "samo sekund". U programu Scientific Work Place 3.0 do rješenja dolazimo:

Primjer problema minimuma Matematička formulacija odgovarajućeg linearnog programa, za koji treba pronaći minimum funkcije cilja glasi: (min) f  100 x  150 0 , 3 x  0 ,1 y  1 0 ,2 x  0 ,4 y  2 0 ,1 x  0 , 4 y  1 , 6 0 , 1 x  0 , 15 x  0 , y  0

y