Linearno programiranje · 1. deo

Linearno programiranje 1 - Uvod u linearno programiranje (LP)

Linearno programiranje 1 – uvod: poslastičar u pekari i 3D prikaz dopustive oblasti

U ovom tekstu se bavimo linearnim programiranjem (LP), odnosno definicijom, kratkom istorijom i osnovnim pojmovima LP. Pre nego što počnemo, bitno je napomenuti da “programiranje” u ovom slučaju treba shvatiti kao “planiranje” ili “optimizacija”, te da nema nikakve veze sa terminom “programiranje” koji se koristi u računarstvu i odnosi na razvoj softera.

Šta ćemo pokriti u Linearno programiranje 1?

U ovom tekstu osvrnućemo se na sledeće celine:

Definicija linearnog programiranja (LP)
Kratka istorija linearnog programiranja (LP)
Primer linearnog programiranja (LP) u praksi
Osnovni pojmovi linearnog programiranja (LP)

U narednom tekstu, Linearno programiranje 2, pokrićemo takođe i: Simpleks metodu (Simpleks algoritam) i geometrijsku metodu linearnog programiranja.

Definicija linearnog programiranja (LP)

Linearno programiranje (LP), odnosno linearna optimizacija je matematička metodologija za modeliranje i rešavanje problema nalaženja maksimuma ili minimuma linearne funkcije, sa određenim ograničenjima tj. pod uslovima iskazanim kao linearne jednačine ili nejednačine. Prosto rečeno, imamo neki cilj, operišemo sa nekim ograničenjima i želimo naći optimalno rešenje u datom kontekstu. Cilj je iskazan kao minimum ili maksimum linearne funkcije, a ograničenja su iskazana kao linearne jednačine ili nejednačine.

Zamislimo da imam pekaru koja proizvodi tri proizvoda. Svaki ima svoju cenu i za svaki je potreban određeni rad, vreme u pećnici i sastojci. Ja pod tim ograničenjima želim da zaradim najviše moguće novca i pokušavam da isplaniram koliko kojih proizvoda je idealno da proizvedem. Ovo je savršen problem za linearno programiranje, a u praksi je linearno programiranje kao matematička metodologija izuzetno primenjivo, na primer u trgovini i ekonomiji, industriji, logistici, vojnim naukama i inženjerstvu.

Tri glavne karakteristike linearnog programiranja su proporcionalnost, aditivnost i konačnost.

Proporcionalnost znači da nema eksponencijalnog rasta ili efekta zakrivljenosti. Promena u vrednosti ulaznih veličina stvara direktno proporcionalan uticaj na izlazni rezultat. Duplo više brašna znači duplo više proizvoda.

Aditivnost podrazumeva da je ukupan efekat aktivnosti jednak prostom zbiru pojedinačnih efekata – ne postoje interakcije ili sinergije među promenljivima. Primera radi, ukupno vreme se prosto sabira, jedno pravljenje proizvoda ne ubrzava drugo.

Konačnost znači da model predstavlja konačan (ograničen) broj promenljivih odlučivanja i konačan broj ograničenja. Sistem uvek raspolaže konačnim i određenim brojem resursa (brašna, pećnica, radnika itd.) i konačnim i određenim brojem promenljivih odlučivanja (u ovom slučaju proizvoda).

Kratka istorija linearnog programiranja

Vremenska linija razvoja linearnog programiranja: Fourier 1820-te, Kantorovich i Leontief 1930-te, Dantzig i von Neumann 1940-te

Začeci rešavanja linearnih nejednačina sežu sve do 1820-tih godina i francuskog matematičara i fizičara Žozefa Furijea (Joseph Fourier). Tokom kasnih tridesetih godina dvadesetog veka, sovjetski matematičar Leonid Kantorovič (Леонид Канторович) i rusko-američki ekonomista Vasilij Leontiljev (Василий Леóнтьев) su se pojedinačno dublje bavili praktičnim aspektima linearnog programiranja: Kontorovič se fokusirao na proizvodnju, a Leontijev na ekonomiju.

Veliki preokret se dešava tokom Drugog svetskog rata, kada linearno programiranje postaje alat za brojne izazove u ratovanju, poput kompleksnih problema transporta i logistike, raspoređivanja resursa, položaja radara i alokacije resursa. Preko primene u ratu, linearno programiranje dolazi u žižu naučne javnosti. Kantorovič je kasnije, 1970-ih, sa holandsko-američkim matematičarem i ekonomistom Kopmansom (Tjalling Koopmans) podelio Nobelovu nagradu za ekonomiju (upravo za rad zasnovan na linearnom programiranju).

Sredinom 1940-ih, Džordž Dancig (George Dantzig) nadalje razvija opštu formulaciju linearnog programiranja za primenu u vojnom zaduhoplovstvu SAD, te razvija i jednu on najpozntihijih metoda linearnog programiranja: simpleks algoritam. Mađrasko-američki matematičar i fizičar, fon Nojmen (John von Neumann), inače poznat po postavljanju matematičkih okvira kvantne fizike i razvoju teorije igara, zajedno sa Dancigom u ovom periodu razvija i teoriju dualnosti linearnog programiranja.

Linearno programiranje se i danas, osamdeset godina nakon Danciga i svog prvobitnog procvata, aktivno koristi u operacionim istraživanjima. Ipak, moja dobra prijateljica je u pravu kada (pomalo kroz šalu) kaže da je tu već izmišljeno sve što je moglo da se izmisli. Fokus današnjih istraživanja zato treba usmeriti ka drugim pravcima optimizacije - poput nelinearnog, stohastičkog i fazi programiranja, kao i heuristikama i metaheuristikama - o čemu će takođe biti reči na Pametnim odlukama.

Primer linearnog programiranja u praksi

Imamo cilj, proizvode, resurse i ograničenja - tabele sa ciljem, resursima, ograničenjima i podacima o proizvodima

Zamisli da smo u Beogradu otvorii finu francusku poslastičarnicu Le Petit Monet. Naš cilj je jednostavan: što veća dnevna zarada od prodaje kolača. Međutim, kao i u svakom biznisu, susrećemo se sa ograničenjima: vreme poslatičara je ograničeno, peć ne može raditi neprestano, a količina specijalnog brašna koje uvozimo je takođe limitirana.

Da bismo doneli najbolju odluku i maksimizirali zaradu, koristimo upravo linearno programiranje u nekoliko koraka.

1. Definisnje promenljivih (proizvodi)

U ponudi imamo tri vrste poslastica:

x₁ – Voćni tart
x₂ – Ekler
x₃ – Krem brule

2. Funkcija cilja (maksimizacija zarade)

Naš cilj je maksimizovati ukupnu zaradu Z. Pošto voćni tart donosi 12, ekler 8, a krem brule 6 eura po komadu, cilja će da glasi:

\max Z = 12x_1 + 8x_2 + 6x_3

3. Ograničenja (limitirani resursi)

Svakog dana radimo sa sledećim ograničenjima:

Radno vreme poslatičara: Poslastičar radi 8 sati dnevno (480 minuta).
- Priprema voćnog tarta traje 10 min, eklera 20 min, a krem brulea 5 min.
- Ograničenje: $10x_1 + 20x_2 + 5x_3 \le 480$
Kapacitet peći: Peć može raditi ukupno 360 minuta dnevno.
- Pečenje voćnog tarta traje 15 min, eklera 5 min, a krem brulea 10 min.
- Ograničenje: $15x_1 + 5x_2 + 10x_3 \le 360$
Zalihe specijalnog brašna: Na raspolaganju je 4.000 grama brašna dnevno.
- Za voćni tart je potrebno 200 g, za ekler 100 g, a za krem brule 50 g.
- Ograničenje: $200x_1 + 100x_2 + 50x_3 \le 4000$

3.2 Zdravorazumsko ograničenje

Ne treba zaboraviti ni poslednje ograničenje, tj. nenegativnost. Ne možemo proizvesti negativan broj proizvoda.

Nenegativnost: Ne možemo napraviti negativan broj kolača: $x_1, x_2, x_3 \ge 0$

4. Matematička postavka

Kada sve iznad uzmemo u obzir, ostaje samo da iskažemo ovaj problem. Postoje četiri oblika iskazivanja linearnog problema: opšti, simetrični, standardni i kanonski. U ovom slučaju izabraćemo opšti:

\begin{aligned} \max Z ={}& 12x_1 + 8x_2 + 6x_3\\ \text{p.o. }& 10x_1 + 20x_2 + 5x_3 \le 480\\ & 15x_1 + 5x_2 + 10x_3 \le 360\\ & 200x_1 + 100x_2 + 50x_3 \le 4000\\ & x_1, x_2, x_3 \ge 0 \end{aligned}

Osnovni pojmovi u linearnom programiranju (LP)

Dobro je upoznati se sa sledećim osnovnim konceptima, odnosno pojmovima linearnog programiranja (LP).

Linearne funkcije (linear functions): Matematičke funkcije u kojima su promenljive na prvi stepen, a čiji je grafik uvek prava linija.

Primer iz pekare: Funkcija zarade $Z = 12x_1 + 8x_2 + 6x_3$ je linearna jer svaki dodati voćni tart uvek povećava zaradu za tačno 12 eur, bez obzira na to koliko smo ih do sada napravili.

Promenljive odlučivanja (decision variables): Nepoznate veličine koje su pod našom direktnom kontrolom i čije vrednosti izračunavamo da bismo doneli najbolju odluku.

Primer iz pekare:
- $x_1$ = broj voćnih tartova koje ćemo ispeći danas
- $x_2$ = broj eklera koje ćemo ispeći danas
- $x_3$ = broj krem brulea koje ćemo ispeći danas

Ograničenja (constraints): Matematičke nejednačine ili jednakosti koje predstavljaju granice naših resursa (vreme, materijal, budžet).

Primer iz pekare:
- Vreme poslastičara: $10x_1 + 20x_2 + 5x_3 \le 480$ (priprema ne sme preći 480 minuta radnog vremena)
- Kapacitet peći: $15x_1 + 5x_2 + 10x_3 \le 360$ (peć ne može raditi duže od 360 minuta)
- Zalihe brašna: $200x_1 + 100x_2 + 50x_3 \le 4000$ (imamo samo 4.000 g specijalnog brašna)
- Nenegativnost: $x_1, x_2, x_3 \ge 0$ (ne možemo ispeći negativan broj kolača)

Funkcija cilja (objective function): Glavna matematička funkcija čiju maksimalnu ili minimalnu vrednost želimo da postignemo.

Primer iz pekare: $\max Z = 12x_1 + 8x_2 + 6x_3$ — želimo da pronađemo takve vrednosti za $x_1, x_2, x_3$ koji daju najveću ukupnu dnevnu zaradu od prodaje kolača.

Dopustiva oblast (feasible region): Geometrijska oblast (skup svih mogućih kombinacija) koja istovremeno zadovoljava sva zadata ograničenja u modelu.

Primer iz pekare: Sve moguće kombinacije pečenja kolača koje fizički možemo da postignemo u jednom danu. Na primer, kombinacija od 10 tartova, 10 eklera i 10 krem brulea nalazi se unutar dopustive oblasti jer troši manje brašna i vremena nego što imamo na raspolaganju.

Dopustivo rešenje (feasible solution): Bilo koja pojedinačna kombinacija vrednosti promenljivih koja se nalazi unutar dopustive oblasti (odnosno rešenje koje ne krši nijedno pravilo).

Primer iz pekare: Odluka da ispečemo 5 voćnih tartova, 5 eklera i 10 krem brulea. Ovo je izvodljivo (dopustivo) rešenje jer imamo dovoljno brašna, vremena poslastičara i kapaciteta peći, ali ne mora značiti da nam donosi i najvišu moguću zaradu.

Ekstremne tačke / temena (extreme points / vertices): Ugaone tačke dopustive oblasti. Fundamentalna teorema LP: Ako optimalno rešenje postoji, ono se sigurno nalazi u bar jednoj ekstremnoj tački.

Primer iz pekare: Teme u kom trošimo tačno 100% radnog vremena poslastičara i 100% kapaciteta peći do krajnjih granica. Najpametniji plan proizvodnje će se uvek kriti u nekom od ovih „uglova” izvodljivog spektra.

Optimalno rešenje (optimal solution): Ono dopustivo rešenje koje daje najbolju moguću (maksimalnu ili minimalnu) vrednost funkcije cilja.

Primer iz pekare: Tačan plan proizvodnje (npr. tačan broj $x_1, x_2, x_3$ ) koji poslastičaru daje jasnu instrukciju: „Danas ispeci tačno N tartova, M eklera i K krem brulea. To će maksimalno iskoristiti naše resurse i doneti najveću moguću dnevnu zaradu u evrima.”

Oblici problema linearnog programiranja

1. Opšti oblik (General form)

Opšti oblik problema linearnog programiranja nema nikakva posebna ograničenja na vrstu nejednakosti ili predznak promenljivih. Funkcija cilja može tražiti maksimizaciju ili minimizaciju, ograničenja mogu sadržati mešavinu relacija (≤, ≥, =), a promenljive mogu biti nenegativne, nepozitivne ili neograničene po znaku.

Funkcija cilja: $\max Z = \sum_{j=1}^{n} c_j x_j$ ili $\min Z = \sum_{j=1}^{n} c_j x_j$
Ograničenja: $\sum_{j=1}^{n} a_{ij} x_j \; \{\le, =, \ge\} \; b_i$ za $i = 1, 2, \dots, m$
Uslovi za promenljive: $x_j \ge 0,\; x_j \le 0$ ili $x_j$ neograničenog znaka

2. Simetrični oblik (Symmetric form)

Simetrični oblik ima uniformne relacije nejednakosti u svim ograničenjima, pri čemu su sve promenljive striktno nenegativne:

Kada se traži maksimizacija, sva ograničenja su tipa ≤ (manje ili jednako).
Kada se traži minimizacija, sva ograničenja su tipa ≥ (veće ili jednako).
Primer za maksimizaciju:

\begin{aligned} \max Z ={}& c_1x_1 + c_2x_2 + \dots + c_nx_n\\ \text{p.o. }& 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\\ & x_1, x_2, \dots, x_n \ge 0 \end{aligned}

3. Standardni oblik (Standard form)

Standardni oblik karakterišu isključivo striktne jednakosti = u svim glavnim ograničenjima, dok su sve promenljive nenegativne ( $x_j \ge 0$ ), a slobodni članovi desne strane su nenegativni ( $b_i \ge 0$ ). Svaki LP problem u simetričnom ili opštem obliku može se prevesti u standardni oblik uvođenjem izravnavajućih (dopunskih / slack) promenljivih.

Matrični zapis:

\begin{aligned} \max\quad & Z = \mathbf{c}^{T}\mathbf{x}\\ \text{p.o.}\quad & \mathbf{A}\mathbf{x} = \mathbf{b}\\ & \mathbf{x} \ge \mathbf{0},\quad \mathbf{b} \ge \mathbf{0} \end{aligned}

4. Kanonski oblik (Canonical form)

Kanonski oblik je specijalan, uslovni oblik standardnog problema linearnog programiranja koji služi kao interni oblik i polazna osnova za primenu Simpleks algoritma.

U ovom obliku, sistem jednačina je rešen po baznim promenljivima — matrica sistema sadrži identifikovanu jediničnu podmatricu (bazne promenljive $\mathbf{x}_B$ ), gde se svaka bazna promenljiva pojavljuje sa koeficijentom 1 u tačno jednoj jednačini i sa koeficijentom 0 u svim ostalim jednačinama i funkciji cilja.

Ovaj oblik direktno daje uvid u početno dopustivo bazno rešenje (gde je $\mathbf{x}_B = \mathbf{b}$ ).