LINEARNO PROGRAMIRANJE: ČEMU SLUŽI, MODELI, OGRANIČENJA, APLIKACIJE - MATEMATIKA - 2026

Linearnog programiranja je matematička metoda koje se koriste za optimizaciju (povećala ili se smanjila je to prikladno), čija funkcija varijable ograničeni, što god je funkcija i ograničenja su varijable ovisne o linearno.

Općenito, funkcija za optimizaciju modelira praktičnu situaciju, poput profita proizvođača čiji su ulozi, rad ili strojevi ograničeni.

Slika 1. Linearno programiranje široko se koristi za optimizaciju dobiti. Izvor: Piqsels.

Jedan od najjednostavnijih slučajeva je linearna funkcija koju treba maksimizirati, što ovisi samo o dvije varijable, koje se nazivaju varijablama odluke. Može biti u obliku:

Z = k ₁ x + k ₂ y

Sa konstantom k ₁ i k ₂. Ova je funkcija poznata kao ciljna funkcija. Naravno, postoje situacije koje za proučavanje trebaju više od dvije varijable, koje su složenije:

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +….

A ograničenja su također matematički modelirana sustavom jednadžbi ili nejednakosti, jednako linearnim u x i y.

Skup rješenja u ovom sustavu naziva se izvedivim rješenjima ili izvedivim točkama. A među izvedivim točkama postoji barem jedna, koja optimizira ciljnu funkciju.

Linearno programiranje neovisno su razvili američki fizičar i matematičar George Dantzig (1914-2005) i ruski matematičar i ekonomist Leonid Kantorovich (1912-1986), ubrzo nakon Drugog svjetskog rata.

Metoda rješavanja problema poznata kao jednostavna metoda je razmišljanje Dantziga koji je radio za američko ratno zrakoplovstvo, Berkeley University i Sveučilište Stanford.

Slika 2. Matematičari George Dantzig (lijevo) i Leonid Kantorovich (desno). Izvor: F. Zapata.

Modeli linearnog programiranja

Elementi potrebni za uspostavu linearnog modela programiranja, pogodnog za praktičnu situaciju, jesu:

-Ciljna funkcija

- varijable preciznosti

-Restrictions

U ciljnoj funkciji definirate ono što želite postići. Na primjer, pretpostavimo da želite maksimizirati dobit od proizvodnje određenih proizvoda. Tada se uspostavlja funkcija "dobit", prema cijeni po kojoj se proizvodi prodaju.

Matematički se ova funkcija može izraziti skraćeno pomoću notacije zbrajanja:

Z = ∑k _i x _i

U ovoj jednadžbi k _i su koeficijenti, a x _i su varijable odluke.

Varijable odluke su elementi sustava čija je kontrola imala, a njihove vrijednosti su realni pozitivni brojevi. U predloženom primjeru, varijable odlučivanja su količina svakog proizvoda koji se proizvodi kako bi se postigla maksimalna dobit.

Konačno, imamo ograničenja, koja su linearne jednadžbe ili nejednakosti u smislu varijabli odluke. Oni opisuju ograničenja problema koja su poznata i mogu biti, na primjer, količine sirovina dostupnih u proizvodnji.

Vrste ograničenja

Možete imati broj M ograničenja, počevši od j = 1 do j = M. Matematički su ograničenja tri vrste:

1. A _j = ∑ a _ij. x _i
2. B _j ≥ ∑ b _ij. x _i
3. C _j ≤ ∑ c _ij. x _i

Prvo ograničenje je tipa linearne jednadžbe i znači da se mora poštovati vrijednost A _j, koja je poznata.

Dva preostala ograničenja linearne su nejednakosti, a to znači da se poznate vrijednosti B _j i C _j mogu poštovati ili premašiti, kada se simbol koji se pojavljuje ≥ (veći ili jednak) ili poštuje ili ne premašuje, ako je simbol ≤ (manje ili jednako).

Primjer modela

Polja primjene vrlo su raznolika, u rasponu od poslovne administracije do prehrane, ali kako bi se razumjela metoda, u nastavku se predlaže jednostavan model praktične situacije s dvije varijable.

Lokalna slastičarnica poznata je po dva specijaliteta: crni šumski kolač i žrtveni kolač.

U njegovoj pripremi trebaju jaja i šećer. Za crnu šumu potrebno vam je 9 jaja i 500 g šećera, dok je za žrtvenik potrebno 8 jaja i 800 g šećera. Odgovarajuće prodajne cijene su 8 i 10 USD.

Problem je: koliko kolača svake vrste mora pekara napraviti da poveća svoj profit, znajući da ima 10 kilograma šećera i 144 jaja?

Varijable odluke

Varijable odluke su "x" i "y", koje uzimaju stvarne vrijednosti:

-x: broj crnih šumskih kolača

-y: kolači žrtvenoga tipa.

ograničenja

Ograničenja su data činjenicom da je broj kolača pozitivna količina i da postoje ograničene količine sirovina za njihovu pripremu.

Stoga, u matematičkom obliku, ta ograničenja imaju oblik:

1. x ≥ 0
2. i ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8y ≤ 10

Ograničenja 1 i 2 predstavljaju uvjet nenegativnosti prethodno izložene, a sve podignute nejednakosti linearne su. U ograničenjima 3 i 4 su vrijednosti koje ne smiju biti prekoračene: 144 jaja i 10 kg šećera.

Ciljna funkcija

Konačno, ciljna funkcija je dobit koja se dobije proizvodnjom „x“ količine crnih šumskih kolača plus „y“ količine žrtvenika. Gradi se množenjem cijene s količinom napravljenih kolača i zbrajanjem za svaku vrstu. To je linearna funkcija koju ćemo nazvati G (x, y):

G = 8x + 10y

Metode rješenja

Različite metodologije rješenja uključuju grafičke metode, algoritam simpleksa i metodu unutarnje točke.

- Grafička ili geometrijska metoda

Kada imate problem s dvije varijable poput onog u prethodnom odjeljku, ograničenja određuju poligonalno područje u ravnini xy, koje se naziva izvedivo područje ili područje održivosti.

Slika 3. Izvodljivo područje u kojem se nalazi rješenje problema optimizacije. Izvor: Wikimedia Commons.

To je područje izgrađeno pomoću restrikcijskih linija, koje su crte dobivene iz nejednakosti ograničenja, radeći samo sa znakom jednakosti.

U slučaju pekare koja želi optimizirati dobit, ograničenja su:

1. x = 0
2. y = 0
3. 9x + 8y = 144
4. 0,5 x + 0,8y = 10

Sve točke u regiji zatvorene tim linijama moguća su rješenja, pa ih ima beskonačno mnogo. Osim u slučaju kada se pokaže da je izvedivo područje prazno, u tom slučaju postavljeni problem nema rješenja.

Srećom, za problem s slastičarima izvediva regija nije prazna, imamo je u nastavku.

Slika 4. Izvodljivo područje problema slastičarstva. Linija s dobitkom 0 prelazi izvorište. Izvor: F. Zapata s Geogebrom.

Optimalno rješenje, ako postoji, nalazi se uz pomoć ciljne funkcije. Na primjer, pri pokušaju pronalaska maksimalne dobiti G imamo sljedeći redak, koji se naziva izoprofitna linija:

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

Ovom linijom dobivamo sve parove (x, y) koji daju dan dobitak G, tako da postoji obitelj linija prema vrijednosti G, ali svi s istim nagibom -k ₁ / k ₂, tako da su paralelne linije.

Optimalno rješenje

Sada se može pokazati da je optimalno rješenje linearnog problema uvijek ekstremna točka ili vrhunca izvedivog područja. Tako:

Ako linija najbliža izvoru ima čitav segment zajednički s izvedivom regijom, onda se kaže da postoje beskonačna rješenja. Do ovog slučaja dolazi ako je nagib linije za izuzeće profita jednak onome od ostalih linija koje ograničavaju regiju.

Za naše slastičarstvo, kandidati su vrhovi A, B i C.

- Dantzigova jednostavna metoda

Grafička ili geometrijska metoda primjenjiva je za dvije varijable. Međutim, složenije je kada postoje tri varijable i nemoguće ju je koristiti za veći broj varijabli.

Kad se bave problemima s više od dvije varijable, koristi se simpleks metoda koja se sastoji od niza algoritama za optimizaciju ciljnih funkcija. Za izračun se često koriste matrice i jednostavna aritmetika.

Simplex metoda započinje odabirom izvedivog rješenja i provjerom je li optimalno. Ako jeste, problem smo već riješili, ali ako nije, nastavljamo prema rješenju bližem optimizaciji. Ako rješenje postoji, algoritam ga pronalazi u nekoliko pokušaja.

Prijave

Linearno i nelinearno programiranje primjenjuju se na mnogim poljima kako bi se donijele najbolje odluke u smislu smanjenja troškova i povećanja profita, koji nisu uvijek novčani, jer se mogu mjeriti vremenom, na primjer, ako želite smanjiti vrijeme potrebno izvršiti niz operacija.

Evo nekoliko polja:

-U marketingu se koristi za pronalaženje najbolje kombinacije medija (društvene mreže, televizija, tisak i drugi) za oglašavanje određenog proizvoda.

-Za dodjeljivanje odgovarajućih zadataka osoblju tvrtke ili tvornice ili raspoređivanje istih.

- U odabiru najhranjivije hrane i uz najnižu cijenu u stočarstvu i peradi.

Riješene vježbe

- Vježba 1

Grafički riješiti model linearnog programiranja podignut u prethodnim odjeljcima.

Riješenje

Potrebno je graficirati skup vrijednosti utvrđenih sustavom ograničenja navedenim u problemu:

1. x ≥ 0
2. i ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8y ≤ 10

Područje dano nejednakostima 1 i 2 odgovara prvom kvadrantu kartezijanske ravnine. Što se tiče nejednakosti 3 i 4, započet ćemo pronalaženjem restriktivnih linija:

9x + 8y = 144

0,5 x + 0,8y = 10 → 5x + 8y = 100

Izvodljivo područje je četverokutnik čiji su vrhovi točke A, B, C i D.

Minimalna dobit je 0, stoga je linija 8x + 10y = 0 donja granica, a izoprofitne linije imaju nagib -8/10 = - 0,8.

Ova se vrijednost razlikuje od padina drugih restriktivnih linija i budući da je izvedivo područje ograničeno, jedinstveno rješenje postoji.

Slika 5. Grafičko rješenje vježbe 1, koje prikazuje izvedivo područje i točku C rješenja na jednoj od vrhova navedenog područja. Izvor: F. Zapata.

Ovo rješenje odgovara liniji nagiba -0,8 koja prolazi kroz bilo koju od točaka A, B ili C, čije su koordinate:

A (11; 5.625)

B (0; 12,5)

C (16, 0)

Optimalno rješenje

Izračunavamo vrijednost G za svaku od ovih točaka:

- (11; 5.625): G _A = 8 x 11 + 10 x 5.625 = 144.25

- (0; 12,5): G _B = 8 x 0 + 10 x 12,5 = 125

- (16, 0): G _C = 8 x 16 + 10 x 0 = 128

Najveću dobit ostvaruje proizvodnja 11 crnih šumskih kolača i 5.625 kolača sa žrtvinama. Ovo se rješenje slaže s onim koje je pronađeno u softveru.

- Vježba 2

Provjerite rezultat prethodne vježbe pomoću Solver funkcije dostupne u većini proračunskih tablica, kao što su Excel ili LibreOffice Calc, koji uključuju algoritam Simplex za optimizaciju u linearnom programiranju.

Riješenje

Slika 6. Detalj otopine iz vježbe 1 kroz proračunsku tablicu Libre Office Calc. Izvor: F. Zapata.

Slika 7. Detaljno rješenje iz vježbe 1 kroz proračunsku tablicu Libre Office Calc. Izvor: F. Zapata.

Reference

1. Sjajan. Linearno programiranje. Oporavak od: briljan.org.
2. Eppen, G. 2000. Operativna istraživanja u administrativnoj znanosti. 5.. Izdanje. Dvorana Prentice.
3. Haeussler, E. 1992. Matematika za menadžment i ekonomiju. 2.. Izdanje. Grupo Uredništvo Iberoamericana.
4. Hiru.eus. Linearno programiranje. Oporavak od: hiru.eus.
5. Wikipedia. Linearno programiranje. Oporavak od: es. wikipedia.org.