Linearno programiranje

Linearno programiranje (LP, ili linearna optimizacija) je matematička metodologija za modeliranje i rešavanje problema nalaženja maksimuma ili minimuma linearne funkcije, pod uslovima iskazanim kao linerane jednačine ili nejednačine. Termin „programiranje“ je ovde sinonim za planiranje, odnosno određivanje optimalnog (najboljeg) plana. To znači određivanje vrednosti promenljivih takvih da daju optimalnu vrednost funkcije cilja, pri tom zadovoljavajući uslove (ograničenja).

Linearno programiranje je specijalan slučaj matematičkog programiranja (optimizacije), gde su funkcija cilja i ograničenja linearni.

Primer problema linearnog programiranja sa četiri promenljive (skraćenica p.o. znači - pri ograničenjima):

${\begin{aligned}&{\text{max}}&&f(\mathbf {x} )=x_{1}+3x_{2}+5x_{3}+2x_{4}\\&{\text{p.o.}}&&2x_{1}+3x_{3}\leq 234\\&&&5x_{2}+4x_{4}\leq 180\\&&&x_{1}+x_{2}+x_{2}\leq 300\\&&&x_{1}\geq 0,\ x_{2}\geq 0,\ x_{3}\geq 0\ x_{4}\geq 0\end{aligned}}$

Ovakvim matematičkim modelima se mogu predstaviti problemi alokacije resursa, planiranja kretanja vozila, razni problemi proizvodnje u industriji, problemi u ekonomiji itd. Primenom lineranog programiranja se mogu rešavati svi praktični problemi koji mogu da se iskažu matematičkim modelom linearnog programiranja.

Istorija

Problem linearnog programiranja je formulisao sovjetski matematičar Leonid Kantorovič 1939. godine. Prvi modeli su korišćeni u drvnoj proizvodnji, a tokom Drugog svetskog rata Kantorovič je radio za vojsku na optimizaciji vojnih operacija. Metod rešavanja problema nije bio javno poznat, sve do 1947. kada je Džordž B. Dancig objavio simpleks algoritam.

Rešenja problema

Skup svih tačaka u n-dimenzionalnom prostoru koje zadovoljavaju ograničenja problema se naziva dopustivim skupom, ili skupom dopustivih rešenja. Tačka iz ovog skupa za koju je vrednost funkcije cilja optimalna (najbolja), odnosno maksimalna ili minimalna, se naziva optimalno rešenje. Sve tačke izvan dopustivog skupa su nedopustiva rešenja. Postoji više mogućih slučajeva postojanja rešenja u odnosu na to kakva su ograničenja:

• Problem ima jedinstveno optimalno rešenje
• Problem ima višestruko optimalno rešenje (beskonačno mnogo optmalnih rešenja)
• Problem nema optimalno rešenje (otvoren je, rast funkcije cilja nije ograničen)
• Problem uošte nema rešenje (ograničenja su nekonzistentna)

Oblici problema linearnog programiranja

U opštem slučaju problem linearnog programiranja može biti iskazan u obliku čija su ograničenja jednačine ili nejednačine, sa zadatkom maksimizacije ili minimizacije funkcije cilja. Algoritmi koji rešavaju ove probleme (pre svega Simpleks) zahtevaju da problem ima određen, specijalan oblik, da bi mogao biti rešavan. Postoje sledeća četiri oblika problema linearnog programiranja:

• opšti
• simetrični
• standardni
• kanonski (uslovno, jer je ovo u suštini interni oblik Simpleks algoritma)

Opšti oblik

Opšti oblik problema linearnog programiranja podrazumeva zadatak maksimizacije ili minimizacije funkcije cilja pri ograničenjima iskazanim kao linearne jednačine ili nejednačine i dodatnim skupom prirodnih ograničenja da vrednosti promenljivih ne mogu biti negativne.

${\begin{aligned}&{\text{min}}\mid {\text{max}}&&f(\mathbf {x} )=c_{1}x_{1}+c_{2}x_{2}+...+c_{n}x_{n}\\&{\text{p.o.}}&&a_{11}x_{1}+a_{12}x_{2}+...+a_{1n}x_{n}\lesseqqgtr b_{1}\\&&&a_{21}x_{1}+a_{22}x_{2}+...+a_{2n}x_{n}\lesseqqgtr b_{2}\\&&&\vdots \\&&&a_{m1}x_{1}+a_{m2}x_{2}+...+a_{mn}x_{n}\lesseqqgtr b_{m}\\&&&x_{1}\geq 0,\ x_{2}\geq 0,\ ...,\ x_{n}\geq 0\end{aligned}}$

Ili iskazan u sažetijem obliku:

${\begin{aligned}&{\text{min}}\mid {\text{max}}&&f(\mathbf {x} )=\sum _{i=1}^{n}c_{i}x_{i}\\&{\text{p.o.}}&&\sum _{j=1}^{n}a_{ij}x_{j}\lesseqqgtr b_{i},\ i=1,2,...,m\\&&&x_{j}\geq 0,\ j=1,2,...,n\end{aligned}}$

Simetrični oblik

Problem iskazan u simetričnom obliku ima sva ograničenja kao nejednakosti istog tipa (sva imaju znak $\leq$ ili $\geq$). Takođe, ako je zadatak maksimizacija funkcije cilja, ograničenja moraju da budu tipa $\leq$, a ako je zadatak minimizacija, ograničenja moraju da budu tipa $\geq$.

Ovde je dat simetrični oblik u matričnoj formi, gde su koeficijenti funkcije cilja, skup promenljivih i slobodni članovi ograničenja dati kao vektori, a koeficijenti nejednačina ograničenja su dati kao matrica.

Simetrični oblik u matričnoj formi

Varjanta maksimizacije	Varjanta minimizacije	Značenje oznaka
${\begin{aligned}&{\text{max}}&&f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{p.o.}}&&A\mathbf {x} \leq \mathbf {b} \\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}$	${\begin{aligned}&{\text{min}}&&f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{p.o.}}&&A\mathbf {x} \geq \mathbf {b} \\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}$	$\mathbf {x} ={\begin{bmatrix}x_{1}\\\vdots \\x_{n}\end{bmatrix}},\mathbf {c} ={\begin{bmatrix}c_{1}\\\vdots \\c_{n}\end{bmatrix}},\mathbf {b} ={\begin{bmatrix}b_{1}\\\vdots \\b_{m}\end{bmatrix}},A={\begin{bmatrix}a_{11}&\cdots &a_{1n}\\\vdots &\ddots &\vdots \\a_{m1}&\cdots &a_{mn}\end{bmatrix}}$

Standardni oblik

Problem uskazan u standardnom obliku može da bude problem maksimizacije ili minimizacije, a sva ograničenja moraju da budu jednakosti. Osim ovog uslova skup ograničenja mora da zadovolji još neke uslove:

• Jednačine ograničenja treba da budu linearno nezavisne

Ako nisu, to znači da dve ili više jednačina iz skupa iskazuju isto ograničenje, i duplikati se mogu eliminisati iz problema.

• Broj ograničenja treba da bude manji od broja promenljivih

Ako je ispunjen prvi uslov, a broj promenljivih i jednačina je isti, tada problem ima samo jedno dopustivo rešenje, odnosno dopustiva oblast će se sastojati od samo jedne tačke. A ako je, uz ispunjenje prvog uslova, broj jednačina veći od broja promenljivih, onda problem neće imati rešenja, odnosno biće preograničen.

• Svi slobodni članovi jednačina ograničenja treba da budu nenegativni

Ovi dodatni uslovi se mogu sažeti u sledećem (n - broj promenljivih, m - broj ograničenja):

$\mathrm {rang} A=m<n$

$\mathbf {b} \geq \mathbf {0}$

Standardni oblik u matričnoj formi

${\begin{aligned}&{\text{min}}\mid {\text{max}}&&f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{p.o.}}&&A\mathbf {x} =\mathbf {b} \\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}$

Prevođenje iz opšteg u simetrični i standardni oblik

Modeli praktičnih problema su izvorno najčešće u simetričnom obliku ili u opštem, ali sa samo jednim tipom nejednakosti (i sa jednakostima, naravno). Praktični problemi skoro nikad nisu izvorno u standardnom obliku. Modeli u jednom obliku se mogu prevoditi u ekvivalentne modele u nekom drugom obliku. Za prevođenje se mogu koristiti više različitih tehnika, čijim korišćenjem se bilo koji model u opštem, simetričnom ili standardnom obliku, može prevesti u neki od druga dva.

Promena zadatka problema (maks. ili min.)

U slučaju da nam više odgovara suprotan problem od datog (maks. u odnosu na min. i obratno), sve što treba da se uradi je da se funkcija cilja pomnoži sa -1, odnosno da se vektor koeficijenata pomnoži sa -1.

${\text{max}}\ \ f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} \ \ \rightarrow \ \ {\text{min}}\ \ f(\mathbf {x} )=(-\mathbf {c} )^{\mathrm {T} }\mathbf {x}$

Promena tipa nejednakosti

Model u opštem obliku čija su sva ograničenja nejednakosti, se može prevesti u simetrični oblik tako što se sva ograničenja koja ne odgovaraju zadatku (maks. ili min.) množe sa -1, čime se obrće znak nejednakosti.

${\begin{aligned}&{\text{max}}&&f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} &&&&{\text{max}}&&f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} &&&&{\text{max}}&&f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{p.o.}}&&{\begin{matrix}A_{l}\mathbf {x} \leq \mathbf {b} _{l}\\A_{g}\mathbf {x} \geq \mathbf {b} _{g}\end{matrix}}&&\rightarrow &&{\text{p.o.}}&&{\begin{matrix}A_{l}\mathbf {x} \leq \mathbf {b} _{l}\\-A_{g}\mathbf {x} \leq -\mathbf {b} _{g}\end{matrix}}&&\rightarrow &&{\text{p.o.}}&&{\begin{bmatrix}A_{l}\\-A_{g}\end{bmatrix}}\mathbf {x} \leq {\begin{bmatrix}\mathbf {b} _{l}\\-\mathbf {b} _{g}\end{bmatrix}}\\&&&\mathbf {x} \geq \mathbf {0} &&&&&&\mathbf {x} \geq \mathbf {0} &&&&&&\mathbf {x} \geq \mathbf {0} \\\end{aligned}}$

Prevođenje nejednačina u jednačine

Ako je potrebano da problem bude u standardnom obliku, sve nejednačine iz skupa ograničenja moraju se prevesti u ekvivalentne jednačine. Ovo se postiže tako što se u problem ubacuju nove promenljive, koje se zovu izravnjavajuće, i to po jedna u svaku nejednačinu.

• U nejednačine tipa „manje-jednako“ dodaje se izravnjavajuća promenljiva sa koeficijentom 1.

$a_{j1}x_{1}+a_{j2}+...+a_{jn}x_{n}\leq b_{j}\ \ \rightarrow \ \ a_{j1}x_{1}+a_{j2}+...+a_{jn}x_{n}+s_{j}=b_{j}$

• U nejednačine tipa „veće-jednako“ dodaje se izravnjavajuća promenljiva sa koeficijentom -1.

$a_{j1}x_{1}+a_{j2}+...+a_{jn}x_{n}\geq b_{j}\ \ \rightarrow \ \ a_{j1}x_{1}+a_{j2}+...+a_{jn}x_{n}-s_{j}=b_{j}$

Izravnjavajuće promenljive se ne dodaju u funkciju cilja, odnosno može se smatrati da u funkciji cilja imaju koeficijente 0. Posle prevođenja problem će imati onoliko dodatnih promenljivih koliko je bilo nejednačina u skupu ograničenja. Rezultujući problem u standardnom obliku je ekvivalentan početnom problemu u smislu da će se njegovim rešavanjem dobiti optimalno rešenje početnog problema, pri tom se u rešenju vrednosti dodatnih izravnjavajućih promenljivih mogu ignorisati.

${\begin{aligned}&{\text{max}}&&f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} &&&&{\text{max}}&&f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} &&&&{\text{max}}&&f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{p.o.}}&&{\begin{matrix}A_{l}\mathbf {x} \leq \mathbf {b} _{l}\\A_{g}\mathbf {x} \geq \mathbf {b} _{g}\\A_{e}\mathbf {x} =\mathbf {b} _{e}\end{matrix}}&&\rightarrow &&{\text{p.o.}}&&{\begin{matrix}A_{l}\mathbf {x} +\mathbf {s} _{l}=\mathbf {b} _{l}\\A_{g}\mathbf {x} -\mathbf {s} _{g}=\mathbf {b} _{g}\\A_{e}\mathbf {x} =\mathbf {b} _{e}\end{matrix}}&&\rightarrow &&{\text{p.o.}}&&{\begin{bmatrix}A_{l}&I&0\\A_{g}&0&-I\\A_{e}&0&0\end{bmatrix}}{\begin{bmatrix}\mathbf {x} \\\mathbf {s} _{l}\\\mathbf {s} _{g}\end{bmatrix}}={\begin{bmatrix}\mathbf {b} _{l}\\\mathbf {b} _{g}\\\mathbf {b} _{e}\end{bmatrix}}\\&&&\mathbf {x} \geq \mathbf {0} &&&&&&\mathbf {x} \geq \mathbf {0} &&&&&&\mathbf {x} \geq \mathbf {0} \\&&&&&&&&&\mathbf {s} \geq \mathbf {0} &&&&&&\mathbf {s} \geq \mathbf {0} \\\end{aligned}}$

Prevođenje jednačina u nejednačine

Jednačine se mogu prevesti u nejednačine na više načina:

• Operacija obrnuta dodavanju izravnjavajuće promenljive

Iz jednačine se može eliminisati promenljiva koje nema u funkciji cilja, a ni u ostalim ograničenjima, čiji koeficijent u jednačini je pozitivan i koja je ogrančena da bude nenegativna. Tada jednačina prelazi u nejednačinu tipa ”manje-jednako”. Ako je promenljiva ima negativan koeficijent, onda se dobija jednačina ”veće-jednako”. U slučaju da je promenljiva ograničena da bude nepozitivna, onda se pravila za znak koeficijenta okreću.

${\begin{aligned}&a_{i1}x_{1}+a_{i2}x_{2}+a_{i3}x_{3}+a_{is1}s_{1}=b_{i},(s_{1}\geq 0)&&\rightarrow &&a_{i1}x_{1}+a_{i2}x_{2}+a_{i3}x_{3}\leq b_{i}\\&a_{i1}x_{1}+a_{i2}x_{2}+a_{i3}x_{3}-a_{is1}s_{1}=b_{i},(s_{1}\geq 0)&&\rightarrow &&a_{i1}x_{1}+a_{i2}x_{2}+a_{i3}x_{3}\geq b_{i}\\&a_{i1}x_{1}+a_{i2}x_{2}+a_{i3}x_{3}+a_{is1}s_{1}=b_{i},(s_{1}\leq 0)&&\rightarrow &&a_{i1}x_{1}+a_{i2}x_{2}+a_{i3}x_{3}\geq b_{i}\\&a_{i1}x_{1}+a_{i2}x_{2}+a_{i3}x_{3}-a_{is1}s_{1}=b_{i},(s_{1}\leq 0)&&\rightarrow &&a_{i1}x_{1}+a_{i2}x_{2}+a_{i3}x_{3}\leq b_{i}\\\end{aligned}}$

• Zamena jedne jednačine sa dve nejednačine

Ove dve nejadnačine će imati iste koeficijente i slobodne članove kao početna jednačina, ali sa obrnutim znakovima nejednakosti. Pošto znakovi nejednakosti uključuju i mogućnost jednakosti (”manje-jednako” i ”veće-jednako”), a suprotni su, to znači da se te dve nejednačine mogu svesti na jednu jednačinu.

${\begin{aligned}&a_{i1}x_{1}+a_{i2}x_{2}+a_{i3}x_{3}=b_{i}&&\rightarrow &&a_{i1}x_{1}+a_{i2}x_{2}+a_{i3}x_{3}\leq b_{i}\\&&&&&a_{i1}x_{1}+a_{i2}x_{2}+a_{i3}x_{3}\geq b_{i}\\\end{aligned}}$

Eliminisanje promenljivih neograničenih po znaku

Problem može da bude formulisan tako da neke promenljive nisu ograničene po znaku (mogu biti i pozitivne i negativne). U ovom slučaju može se napraviti smena. Neku promenljivu $x_{j}$ možemo zameniti razlikom dve promenljive $x_{j}^{+}-x_{j}^{-}$ na svim mestima u problemu gde se pojavljuje. Sada ove dve nove promenljive mogu da budu ograničene da budu nenegativne, jer njihova razlika može da bude i pozitivna i negativna, kao originalna promenljiva.

Kanonski oblik

Kanoski oblik problema linearnog programiranja je skoro specijalan slučaj standardnog oblika (skoro, jer ima jedno proširenje u odnosu na opšti oblik problema LP). Ovaj oblik je zapravo interni oblik problema Simpleks algoritma. Problem u kanonskom obliku osim što zadovoljava uslove standardnog oblika, takođe ima i sledeće dodatne uslove. Ako problem ima $n$ promenljivih i $m$ ograničenja, on je u kanonskom ako zadovoljava sledeće uslove:

• Zadatak problema je maksimizacija funkcije cilja.
• U skupu promenljivih postoji podskup od m promenljivih, takvih da se u svakom ograničenju nalazi po jedna promenljiva iz tog podskupa (i ni u jednom drugom ograničenju), i to sa koeficijenom 1.
• Tih m promenljivih iz podskupa u funkciji cilja imaju koeficijent 0.
• Svi slobodni članovi ograničenja su nenegativni.

Takođe ima i jedno proširenje u odnosu na opšti oblik, a to je da funkcija cilja može da sadrži slobodan član.

Razvijeno	Matrično
${\begin{aligned}&{\text{max}}&&f(\mathbf {x} )=c_{1}x_{1}+...+c_{n-m}x_{n-m}+F_{0}\\&{\text{p.o.}}&&a_{11}x_{1}+a_{12}x_{2}+...+a_{1(n-m)}x_{n-m}+x_{n-m+1}=b_{1}\\&&&a_{21}x_{1}+a_{22}x_{2}+...+a_{2(n-m)}x_{n-m}+x_{n-m+2}=b_{2}\\&&&\vdots \\&&&a_{m1}x_{1}+a_{m2}x_{2}+...+a_{m(n-m)}x_{n-m}+x_{n}=b_{m}\\&&&x_{i}\geq 0,\ i=1,...,n\\\end{aligned}}$	${\begin{aligned}&{\text{max}}&&f(\mathbf {x} )=\mathbf {c} _{n}^{\mathrm {T} }\mathbf {x} _{n}+F_{0}\\&{\text{p.o.}}&&{\begin{bmatrix}A_{n}&I\end{bmatrix}}{\begin{bmatrix}\mathbf {x} _{n}\\\mathbf {x} _{b}\end{bmatrix}}=\mathbf {b} \\&&&\mathbf {x} _{n}\geq \mathbf {0} \\&&&\mathbf {x} _{b}\geq \mathbf {0} \\\end{aligned}}$

Bazne promenljive i bazna dopustiva rešenja

Ako imamo problem u standardnom obliku, sa matricom ograničenja $A_{m\times n},(m<n)$, od svih promenljivih možemo da izaberemo nekih m promenljivih, takvih da, ako ostale promenljive izjednačimo sa nulom sistem jednačina ograničenja može da se jednistveno reši po izabranih m promenljivih. Poznato je da, da bi sistem jednačina bio rešiv, matrica koeficijenata promenljivih mora da bude invertibilna, odnosno da ima determinantu različitu od 0. Ovih m promenljivih koje zadovoljavaju uslov se nazivaju bazne promenljive, skup baznih promenljivih se naziva baza, a kvadratna matrica koeficijenata baznih promenljivih se naziva matrica baze.

${\begin{aligned}&{\begin{bmatrix}A_{n}&A_{b}\end{bmatrix}}{\begin{bmatrix}\mathbf {x} _{n}\\\mathbf {x} _{b}\end{bmatrix}}=\mathbf {b} &&\rightarrow &&{\begin{bmatrix}A_{n}&A_{b}\end{bmatrix}}{\begin{bmatrix}\mathbf {0} \\\mathbf {x} _{b}\end{bmatrix}}=\mathbf {b} &&\rightarrow &&A_{b}\mathbf {x} _{b}=\mathbf {b} &&\rightarrow &&\mathbf {x} _{b}=A_{b}^{-1}\mathbf {b} \\\end{aligned}}$

Rešavanjem sistema jednačina dobijenog na ovaj način dobijaju se vrednosti baznih promenljivih. Tako dobijene vrednosti baznih promenljivih sa dodatim nulama kao vrednostima ostalih (nebaznih) promenljivih čine jedno dopustivo rešenje problema, jer ono sigurno zadovoljava ograničenja. Ovako dobijeno dopustivo rešenje se naziva bazno dopustivo rešenje. Problem ima onoliko baznih dopustivih rešenja, koliko matrica koeficijenata ograničenja ima kvadratnih invertibilnih podmatrica veličine m.

Ako vektor koeficijenata baznih promenljivih u funkciji cilja označimo sa $\mathbf {c} _{b}$, tada će vrednost funkcije cilja za dato bazno dopustivo rešenje biti jednaka $\mathbf {c} _{b}^{\mathrm {T} }\mathbf {x} _{b}$, odnosno $\mathbf {c} _{b}^{\mathrm {T} }A_{b}^{-1}\mathbf {b}$.

Ako problem ima jedinstveno optimalno rešenje, tada će jedno od baznih dopustivih rešenja biti to optimalno rešenje, a ako sistem ima beskonačno mnogo optimalnih rešenja, tada će više od jednog baznog dopustivog rešenja imati optimalnu vrednost funkcije cilja. Ako se otkriju sve invertibilne podmatrice veličine m, i preko njih generišu sva bazna dopustiva rešenja, ona rešenja koja daju najbolju vrednost funkcije cilja jesu optimalna rešenja problema. Naravno, ovaj način rešavanja problema linearnog programiranja je jako neefkasan, jer podrazumeva probanje svih mogućnosti.

Bazna dopustiva rešenja u kanonskm obliku

Ako imamo problem u kanonskom obliku možemo direktno pročitati jedno bazno dopustivo rešenje, bez rešavanja sistem jednačina. Matrica koeficijenata već ima jasno vidljivu invertibilnu podmatricu (jediničnu matricu za m promenljivih) i ako nebaznim promenljivama dodelimo vrednost 0, odmah vidimo da su rešenja sistema jednačina zapravo slobodni članovi jednačina.

${\begin{bmatrix}\mathbf {x} _{n}\\\mathbf {x} _{b}\end{bmatrix}}={\begin{bmatrix}\mathbf {0} \\\mathbf {b} \end{bmatrix}}$

Svođenje standardnog oblika na kanonski

Metode linearne algebre

Ako imamo problem u standardnom obliku, i poznata nam je jedna baza, tada možemo problem da svedemo na kanonski oblik u odnosu na tu bazu, ali pod uslovom da slobodni članovi ograničenja rezultujućeg kanonskog oblika budu nenegativni.

Prevođenje ograničenja

Ako promenljive u ograničenjima grupišemo u bazne i nebazne, možemo metodama linearne algebre (inverzija matrice ili Gaus-Žordanova redukcija) da transformišemo sistem jednačina tako da matrica baze $A_{b}$ postane jedinična matrica (što zahteva kanonski oblik). Matrica nebaznih promenljivih $A_{n}$ tada postaje matrica $A_{b}^{-1}A_{n}$, dok vektor $\mathbf {b}$ postaje $A_{b}^{-1}\mathbf {b}$.

${\begin{aligned}&{\begin{bmatrix}A_{n}&A_{b}&\mathbf {b} \end{bmatrix}}&&\rightarrow &&{\begin{bmatrix}A_{n}^{*}&I&\mathbf {b} ^{*}\end{bmatrix}}&&\Leftrightarrow &&{\begin{bmatrix}A_{b}^{-1}A_{n}&I&A_{b}^{-1}\mathbf {b} \end{bmatrix}}\\\end{aligned}}$

Pošto kanonski oblik postavlja uslov da slobodni članovi budu nenegativni, operacija prevođenja u kanonski oblik u odnosnu na datu bazu će uspeti ako je $A_{b}^{-1}\mathbf {b} \geq \mathbf {0}$. Dakle ako je ovaj uslov zadovoljen možemo nastaviti sa prevođenjem.

Prevođenje funkcije cilja

Da bi ceo problem bio u kanonskom obliku, moramo da eliminišemo bazne promenljive iz funkcije cilja. Funkciji cilja možemo da dodamo slobodni član nekog od ograničenja, a oduzmemo od nje linearnu funkciju koja čini to ograničenje. Pošto između leve i desne strane ograničenja stoji jednakost, ova operacija ne menja funkciju cilja i problem pretvara u ekvivalentan problem u drugačijoj formi. Da bi eliminisali neku od baznih promenljivih iz funkcije cilja treba da pomnožimo ograničenje u kome se ona nalazi sa njenim koeficijentom u funkciji cilja i onda sa takvom jednačinom uradimo navedenu operaciju (pri tom ne menjamo samo ograničenje). Ovu operaciju možemo da uradimo sa svakim ograničenjem koje sadrži baznu promenljivu koja postoji u funkciji cilja, i time eliminišemo sve bazne promenljive iz funkcije cilja. Kao posledica funkcija cilja će sada sadržati i slobodan član. Ovaj slobodan član je zapravo vrednost funkcije cilja polaznog problema u odnosu na datu bazu.

U sledećoj formulaciji ove operacije $\mathbf {x} _{b}$ je vektor baznih promenljivih, a $\mathbf {x} _{n}$ je vektor nebaznih promenljivih. Koeficijenti nebaznih promenljivih su dati matricom $A_{n}^{*}$, a slobodni članovi vektorom $\mathbf {b} ^{*}$.

${\begin{aligned}&f(\mathbf {x} )=\mathbf {c} _{n}^{\mathrm {T} }\mathbf {x} _{n}+\mathbf {c} _{b}^{\mathrm {T} }\mathbf {x} _{b}&&\rightarrow &&f(\mathbf {x} )=(\mathbf {c} _{n}^{\mathrm {T} }-\mathbf {c} _{b}^{\mathrm {T} }A_{n}^{*})\mathbf {x} _{n}+\mathbf {c} _{b}^{\mathrm {T} }\mathbf {b} ^{*}\\\end{aligned}}$

Rezultat kompletne operacije svođenja u matričnoj formi

${\begin{aligned}&{\text{max}}&&f(\mathbf {x} )=\mathbf {c} _{n}^{\mathrm {T} }\mathbf {x} _{n}+\mathbf {c} _{b}^{\mathrm {T} }\mathbf {x} _{b}&&&&{\text{max}}&&f(\mathbf {x} )=(\mathbf {c} _{n}^{\mathrm {T} }-\mathbf {c} _{b}^{\mathrm {T} }A_{b}^{-1}A_{n})\mathbf {x} _{n}+\mathbf {c} _{b}^{\mathrm {T} }A_{b}^{-1}\mathbf {b} \\&{\text{p.o.}}&&{\begin{bmatrix}A_{n}&A_{b}\end{bmatrix}}{\begin{bmatrix}\mathbf {x} _{n}\\\mathbf {x} _{b}\end{bmatrix}}=\mathbf {b} &&\rightarrow &&{\text{p.o.}}&&{\begin{bmatrix}A_{b}^{-1}A_{n}&I\end{bmatrix}}{\begin{bmatrix}\mathbf {x} _{n}\\\mathbf {x} _{b}\end{bmatrix}}=A_{b}^{-1}\mathbf {b} \\&&&\mathbf {x} _{b}\geq \mathbf {0} &&&&&&\mathbf {x} _{b}\geq \mathbf {0} \\&&&\mathbf {x} _{n}\geq \mathbf {0} &&&&&&\mathbf {x} _{n}\geq \mathbf {0} \\\end{aligned}}$

Ove dve operacije (transformisanje ograničenja i funkcije cilja) mogu da se rade i unakrsno. Može se formirati proširena matrica celog problema, koja će se satojati od proširene matrice sistema ograničenja, sa dodatnim redom koji predstavlja funkciju cilja, s tim što će poslednji element tog reda biti negativni slobodni član funkcije cilja, jer operacija kojom eliminišemo promenljive iz funkcije cilja nije elementarna matrična transformacija redova. Ali ako se pridržavamo pravila matričnih transformacija, na mestu slobodnog člana dobićemo njegovu suprotnu vrednost.

${\begin{aligned}&{\begin{bmatrix}\mathbf {c} _{n}^{\mathrm {T} }&\mathbf {c} _{b}^{\mathrm {T} }&\mathbf {0} \\A_{n}&A_{b}&\mathbf {b} \\\end{bmatrix}}&&{\overset {\mathrm {e.t.r.} }{\rightarrow }}&&{\begin{bmatrix}{\mathbf {c} _{n}^{*}}^{\mathrm {T} }&0&-f\\A_{n}^{*}&I&\mathbf {b} ^{*}\end{bmatrix}}&&\Leftrightarrow &&{\begin{bmatrix}\mathbf {c} _{n}^{\mathrm {T} }-\mathbf {c} _{b}^{\mathrm {T} }A_{b}^{-1}A_{n}&0&-\mathbf {c} _{b}^{\mathrm {T} }A_{b}^{-1}\mathbf {b} \\A_{b}^{-1}A_{n}&I&A_{b}^{-1}\mathbf {b} \end{bmatrix}}\end{aligned}}$

Ako obratimo pažnju na uslov $A_{b}^{-1}\mathbf {b} \geq \mathbf {0}$, onda je najefikasnije prvo izračunati slobodne članove, pa ako zadovoljavaju uslov, izračunati ostatak matrice.

Ovaj postupak dobijanja kanonskog oblika podrazumeva nalaženje neke baze preko koje se problem može prevesti u kanonski oblik, što moeže biti prilično zahtevno. Sledeća metoda to zaobilazi.

Metoda veštačkih promenljivih

Ova metoda se još naziva i metodom velikog M. Ako standardnim transformacijama sistema jednačina ne možemo lako da dobijemo kanonski oblik sistema ograničenja onda ćemo u svaku jednačinu koja odskače od kanonskog oblika dodati po jednu dodatnu promenljivu. Ove nove promenljive zovemo veštačke (i obično označavamo sa v) jer ne postoje u originalnom problemu. Zato ćemo u funkciji cilja veštačkim promenljivama dodeliti koeficijente $-\mathrm {M}$, gde je M neki mnogo veliki pozitivan broj (veći od bilo kog broja pri poređenju). Ovim osiguravamo da će, zbog zadatka maksimizacije, algoritam za rešavanje sigurno ovim promenljivama dodeliti vrednost 0, čime se ova izmena orgiginalnog problema poništava.

Problem proširen veštačkim promenljivama u slučaju da svaka jednačina ima po jednu (što ne mora da bude), izgleda ovako:

${\begin{aligned}&{\text{max}}&&f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} -{\text{M}}\sum _{i=1}^{m}v_{i}\\&{\text{p.o.}}&&A\mathbf {x} +\mathbf {v} =\mathbf {b} \\&&&\mathbf {x} \geq \mathbf {0} ,\mathbf {v} \geq \mathbf {0} \end{aligned}}$

Da bi problem bio u kanonskom obliku, moramo da elimišemo veštačke promenljive iz funkcije cilja, što možemo da uradimo množenjem svake jednačine koja sadrži veštačku promenljivu sa M i dodavanjem dobijene jednačine funkciji cilja (uz istovremeno oduzimanje slobodnih članova). Tada će funkcija cilja dobiti sledeći oblik. (množenje matrice transponovanim vektorom jedinica sleva daje vrstu suma kolona te matrice)

$f(\mathbf {x} )=(\mathbf {c} ^{\mathrm {T} }+\mathrm {M} \cdot \mathbf {1} ^{\mathrm {T} }A)\mathbf {x} -\mathrm {M} \sum _{i=1}^{m}b_{i}$

Ovo jeste kanonski oblik funkcije cilja i zajedno sa ograničenjima, ceo problem je sada u kanonskom obliku. Bazno rešenje ovakvog kanonskog oblika predstavljaju slobodni članovi kao vrednosti veštačkih promenljivih i nule kao vrednosti nebaznih, što su sve promenljive iz originalnog problema, a takvo rešenje je za originalni problem nedopustivo. Ali Simpleks algoritam može da pođe od ovakvog kanonskog oblika, i uspešno dobije optimalno rešenje originalnog problema (iako ovako modifikovani problem nije ekvivalentan originalnom).

Dualnost

Raznim transformacijama funkcije cilja i ograničenja problemi linearnog programiranja se mogu prevesti u ekvivalentne probleme, ali u drugačijoj formi. Svakom problemu linearnog programiranja osim bezbroj ekvivalentnih problema, može se na određen način pridružiti i, takozvani, dualni problem. U terminilogiji teorije dualnosti početni problem se naziva primal. Primal i dual nisu ekvivalentni problemi, ali su srodni i vezani.

Broj promenljivih duala je jednak broju ograničenja primala, dok je broj ograničenja duala jednak broju promenljivih primala. Vektor koeficijenata funkcije cilja duala je jednak vektoru slobodnih članova ograničenja primala, dok je vektor slobodnih članova duala jednak vektoru koeficijenata u funkciji cilja primala. Matrica koeficijenata ograničenja duala je jednaka transponovanoj matrici primala. I na posletku zadatak dualnog problema je suprotan zadatku primala.

Takođe postoji odnos između između tipova ograničenja i ograničenosti promenljivih u primalu i dualu. Taj odnos je najbolje opisati u tabeli.

Primal	Dual
${\text{max}}\ f(\mathbf {x} )$	${\text{min}}\ \phi (\mathbf {y} )$
i - to ograničenje	i - ta promenljiva
tipa $\leq$	$y_{i}\geq 0$
tipa $\geq$	$y_{i}\leq 0$
tipa $=$	$y_{i}$ neograničena po znaku
j - ta promanljiva	j - to ograničenje
$x_{j}\geq 0$	tipa $\geq$
$x_{j}\leq 0$	tipa $\leq$
$x_{j}$ neograničena po znaku	tipa $=$

Dual problema u simetričnom obliku

${\begin{aligned}&{\text{max}}&&f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} &&&&{\text{min}}&&\phi (\mathbf {y} )=\mathbf {b} ^{\mathrm {T} }\mathbf {y} \\&{\text{p.o.}}&&A\mathbf {x} \leq \mathbf {b} &&\Leftrightarrow &&{\text{p.o.}}&&A^{\mathrm {T} }\mathbf {y} \geq \mathbf {c} \\&&&\mathbf {x} \geq \mathbf {0} &&&&&&\mathbf {y} \geq \mathbf {0} \\\end{aligned}}$

Praktična vrednost teorije dualnosti je ta da se može desiti da dualni problem bude takav da će ga algortimi za rešavanje rešiti brže, odnosno u manjem broju koraka, nego primal. Pri tom se algoritam kreće kroz rešenja koja su nedopustiva za primal, ali završava na rešenju koje je dopustivo i za primal i za dual, što je optimalno rešenje oba problema.

Teorija dualnosti

Teorija dualnosti izučava matemačka svojstva odnosa primalnog i dualnog problema.

Podrazumevjući da primal predstavlja problem maksimizacije funkcije $f(\mathbf {x} )$, a dual problem minimizacije funkcije $\phi (\mathbf {y} )$, oni su povezani sledećim svojstvima:

• Ako je x bilo koje dopustivo rešenje primala, a y bilo koje dopustivo rešenje duala, tada je $f(\mathbf {x} )\leq \phi (\mathbf {y} )$. Ovo se naziva svojstvo slabe dualnosti.
• Ako je x dopustivo rešenje primala koje nije optimalno i $f(\mathbf {x} )=\phi (\mathbf {y} )$, tada y nije dopustivo rešenje duala.
• Ako su x i y dopustiva rešenja primala i duala, i važi da je $f(\mathbf {x} )=\phi (\mathbf {y} )$, tada su tačke x i y optimalna rešenja primala i duala. Ovo svojstvo važi i u suprotnom smeru.
• Primal ima optimalno rešenje, ako i samo ako dual ima optimalno rešenje, pri čemu su njihove vrednosti jednake.
• Ako je funkcija cilja primala neograničena odozgo (otvoren problem), tada je dopustiva oblast duala prazna (ograničenja će biti nekozistentna). A ako je dual neograničen odozdo, tada je dopustiva oblast primala prazna.

Dakle, ako su dopustive oblasti primala i duala neprazne, oba problema imaju optimalno rešenje.

Algoritmi za rešavanje problema LP

Algortmi promene baze

Simpleks algoritam

Simpleks algoritam, koji je razvio Džordž Dancig 1947., rešava probleme linearnog programiranja tako što počinje od jednog baznog dopustivog rešenja (temena dopustive oblasti, koja je oblika višedimenzinalnog poliedra), i generiše niz novih baznih rešenja takvih da je svako sledeće bolje o prethodnog, dok ne stigne do optimalnog rešenja.

Iako u najgorem slučaju Simpleks algoritam ima eksponencijalnu složenost, u praksi je prilično efikasan, a pokazalo se da ”nasumične” probleme rešava podjednako efikaso kao i praktične.

Criss-cross algoritam

Kao i Simpleks, i ovaj algoritam se kreće između baznih rešenja. Ali criss-cross algoritam ne mora da zadrži dopustivost baza, već može da ode i na nedopustiav bazna rešenja. Oavj algoritam je kao i Simpleks, eksponencijane složenosti u najgorem slučaju.

Serangov algoritam

Kao i drugi algortimi promene baze, Serangov algoritam se kreće preko temena, ali dok se simpleks kreće samo s jedne na drugu susednu bazu, ovaj algoritam može da promeni više od jedne promenljive u bazi i ode na neko nesusedno teme, i ne kreće se samo duž ivica. Počev od trenutnog temena, algoritam uzima nasumičan vektor koji poboljšava funkciju cilja bez kršenja susednih ograničenja, zatim se kreće duž tog vektora dok ne naiđe na ograničenje. Onda agoritam projektuje ovaj vektor na ograničenje i kreće se duž proekcije dok se ne naiđe na noo ograničenje. Postupak projekcije i kretanja se ponavlja dok se ne stigne u teme. Tada se opet uzima nasumičan vektor, i tako do pronalaženja optimanog temena. I ovaj algortiam je eksponencijalan i najgorem sučaju, ali u praksi je bolji u odnosu na Simpleks.

Algoritmi koji se kreću kroz unutrašnjost

Ovi algoritmi ostaju u unutrašnjosti dopustive oblasti, a tokom kretanja se iterativno, asimptotski približavaju optimalnom temenu do zadate udaljenosti. Onda se nekom drugom metodom može preći na najbliže teme i doći do tačnog rešenja.

Hačijanov agortam je prvi algoritam za rešavanje LP problema koji ima polinomijalnu složenost u najgorem slučaju. Ali je Simpleks i dalje bio efikasniji osim u specijalno napravljenim slučajevima. Kasnije je Karmarkar razvio algoritam boljih polinomijalnih performansi.

Trenutno je mišljenje da je efikasnost dobrih implementacija algoritama baziranih na Simpleksu i algoritama unitrašnjosti slična za rutinske priemene linearnog programiranja. Ali za određene tipove problema jedna vrsta algoritma može biti bolja od druge (nekada mnogo bolja).

Vidi još

• Simpleks algoritam
• Dinamičko programiranje
• Transportni problem
• Optimizacija (matematika)
• Operaciona istraživanja

Literatura

• Dantzig, G.B.: Maximization of a linear function of variables subject to linear inequalities, 1947. Objavljen na pp. 339–347 u Koopmans T.C. (ed.):Activity Analysis of Production and Allocation, New York-London 1951 (Wiley & Chapman-Hall)
• S. Krčevinac, M. Čangalović, V. Kovačević-Vujčić, M. Martić, M. Vujošević: Operaciona istraživanja 1, 3. izdanje, Beograd (Fakultet organizacionih nauka). 2009. ISBN 978-86-7680-200-5.
• Nash, S.G., Sofer A.: "Linear and Nonlinear Programming", McGraw Hill. 1996. ISBN 007046.0655. ISBN 978-0070460652.
• Gass, S.I.: "Linear Programming: Methods and Applications". . Courier Dover Publications. 1985. ISBN 9780486432847. 
• Dantzig, G.B.: "Linear programming and extensions", . . Princeton University Press. 1998. ISBN 9780691059136. 
• Frederick, S.,H.,Lieberman, G.J. "Introduction to Operations Research, 6th edition, McGraw Hill, 1995
• Gondzio, Jacek; Terlaky, Tamás (1996). „3 A computational view of interior point methods”. Ur.: J. E. Beasley. Advances in linear and integer programming. Oxford Lecture Series in Mathematics and its Applications. 4. New York: Oxford University Press. str. 103—144. MR 1438311. Postscript file at website of Gondzio and at McMaster University website of Terlaky.