Čo je lineárne programovanie?

Lineárne programovanie je matematická metóda pre zistenie optimálnej hodnoty lineárnej funkcie na množine riešení sústavy lineárnych rovníc a nerovníc.(Toma 2008) Sústava pozostáva z lineárnych obmedzení a účelovej funkcie. Účelová funkcia definuje veličinu, ktorá sa má optimalizovať, a cieľom lineárneho programovania je nájsť hodnoty premenných, ktoré maximalizujú alebo minimalizujú účelovú funkciu. Vzťahy v reálnom svete môžu byť mimoriadne komplikované, na zobrazenie takýchto vzťahov však možno použiť lineárne programovanie, čím sa uľahčí ich analýza.

Využitie

Lineárne programovanie sa využíva v rôznych odvetviach, pretože mnohé praktické problémy v operačnom výskume možno vyjadriť ako problémy lineárneho programovania. Lineárne programovanie bolo vo veľkej miere využívané vo formovaní mikroekonómie a v súčasnosti sa využíva v riadení spoločností, ako je plánovanie, výroba alebo doprava. Aj keď sa problémy v spoločnotiach neustále menia, väčšina spoločností by chcela maximalizovať zisky a minimalizovať náklady s obmedzenými zdrojmi. (Brilliant.org, n.d.) Preto mnohé problémy sú vhodné charakterizovať ako problémy lineárneho programovania. (Thie and Keough 2008) V prvom rade tieto problémy ale musia spĺňať všetky z nasledujúcich podmienok:

Grafická metóda

Štandardná forma lineárneho programovania pozostáva z rozhodovacích premenných, účelovej funkcie a ohraničení.
Funkcia \(f(x) = ax_1 + bx_2\) je účelová funkcia, ktorá má byť optimalizovaná (maximalizovaná alebo minimalizovaná). (Brilliant.org, n.d.)
Ohraničenia sú obmedzenia, ktoré sú pridelené na rozhodovacie premenné s cieľom obmedziť ich hodnotu \(cx_1 + dx_2 \leq e\), \(fx_1 + gx_2 \leq h\)
Rozhodovacie premenné musia byť taktiež ohraničené ako nezáporné. \(x_1 \geq 0, x_2 \geq 0\)

Ak náš problém obsahuje iba dve rozhodovacie premenné, jednoduchým spôsobom riešenia je grafická metóda.
Máme daný výrobný problém:

Vo firme sa vyrábajú dva druhy stolov. Zisk z predaja jednotlivých druhov stolov sú 120€ za prvý druh a 100€ za druhý druh. Mesačná výroba je ohraničená množstvom dreva 500 m2 a počtom potrebných kovových tyčí 1200 kusov, pričom všetky ostatné surovinové zdroje sú k diskozícii v dostatočnom množstne. Pretože sa vo firme pracuje len na jednu zmenu, možno rátať len s množstvom 1500 pracovných hodín, ktoré sú k dispozícii počas jedného mesiaca. Na výrobu prvého druhu stola je nutné použiť 2 m2 dreva a 2 kusy kovových tyčí a na výrobu druhého druhu stola je nutné použiť 1 m2 dreva a 3 kusy kovových tyčí. Čas nevyhnutný na zhotovenie jedného kusu stola prvého druhu je 3 hodiny a druhého 4 hodiny. Firma potrebuje stanoviť taký mesačný plán, aby dosiahla pri daných výrobných a odbytových podmienkach maximálny zisk z predaja vyrobených stolov.

Na vyriešenie tohto problému si najprv musíme zostaviť naše ne/rovnice:

Kde \(x_1\) predstavuje stôl prvého druhu a \(x_2\) stôl druhého druhu. Prvá rovnica ohraničenia hovorí o obmedzení dreva, druhá tyčí a tretia času.

Teraz potrebujeme tieto nerovnice naniesť do grafu, aby sme videli kde sa nachádza množina prípustných riešení.

Mnohouholník predstavuje možné hodnoty premenných, ktoré spĺňajú všetky obmedzenia. Aby metóda lineárneho programovania fungovala, mal by to byť konvexný polytop-zovšeobecnenie mnohouholníka alebo mnohostenu v ľubovoľnerozmernom priestore (v 2 dimenziách konvexný mnohouholník; v 3 dimenziách konvexný mnohosten atď.). (Brilliant.org, n.d.).
Z nerovníc vieme určiť okrajové body mnohouholníka určujúceho množinu prípustných riešení:

Po dosadení okrajových bodov do účelovej funkcie dostaneme:

Bod \(f(x) = 120x_1 + 100x_2\)
\(A= (0,0)\) \(f(A)=0\)
\(B=(250,0)\) \(f(B)=30000\)
\(C=(100,300)\) \(f(C)=42000\)
\(D=(0,375)\) \(f(D)=37500\)

Kde vidíme, že bod \(C=(100,300)\) má vo funkcií najväčšiu funkčnú hodnotu a bude teda optimálnym riešením maximalizačnej úlohy.
Vieme sa na to pozrieť aj cez vykreslenie účelovej funkcie. Vykreslíme \(120x_1 + 100x_2 = 0\) a túto funkciu budeme postupne “posúvať” doprava cez množinu prípustných riešení. Posledný dotykový bod pred opustením zisteného mnohouholníka je bod optimálneho riešenia.(Thie and Keough 2008)

Riešením tejto úlohy by teda bolo: Pri daných výrobných a odbytových podmienkach by firma získala maximálny zisk z predaja výrobou 100ks stolov prvého druhu a 300 ks druhého druhu.

Táto metóda riešenia je ale vhodná len pre problémy obsahujúce iba dve rozhodujúce premenné. Pri troch už by sme museli ísť do 3D a pri viacerých by bol už tento spôsob nepoužiteľný.

Simplexová metóda

Náš zadaný problém sa síce dá riešiť aj graficky, dá sa riešiť aj simplexovou metódou. Táto metóda je primárne využiteľná pri problémoch nevhodných na grafické riešenie, ale dá sa využiť aj tu.

Riešenie simplexovou metódou pozostáva z nasledujúcich krokov:

1. Prevod nerovníc na tvar rovníc
2. Dosadenie umelých premenných
3. Vytvorenie tabuľky
4. Nájdenie pivotových premenných
5. Vytvorenie novej tabuľky
6. Skontrolovanie optimálneho riešenia

Rovnicový tvar a umelé premenné

Naše rovnice, ktoré pôvodne vyzerali takto:

\(f(x) = 120x_1 + 100x_2\)
\(2x_1 + 1x_2 \leq 500\)
\(2x_1 + 3x_2 \leq 1200\)
\(3x_1 + 4x_2 \leq 1500\)
\(x_1,x_2 \geq 0\)
Prepíšeme do tvaru, ktorý bude obsahovať umelé premenné. Pre každé ohraničenie bude pridaná jedna a tak ich pretransformujeme na rovnice. V našom prípade sú nerovnice v tvare \(\leq\) a teda ak z nich chceme vytvoriť rovnice, musíme pridať nejakú premennú \(+s_i\). V prípade, že by boli nerovnice v tvare \(\geq\), museli by sme premennou niečo odčítať \(-s_i\) (\(s_i\geq0\)).
Nový tvar rovníc bude vyzerať takto:
\(max\) \(z = 120x_1 + 100x_2 + 0s_1 + 0s_2 + 0 s_3\)
\(2x_1 + 1x_2 + 1s_1 + 0s_2 + 0 s_3 = 500\)
\(2x_1 + 3x_2 + 0s_1 + 1s_2 + 0 s_3 = 1200\)
\(3x_1 + 4x_2 + 0s_1 + 0s_2 + 1 s_3 = 1500\)
\(x_1,x_2,s_1,s_2,s_3 \geq 0\)

Vytvorenie tabuľky

Simplexová tabuľka sa používa na vykonávanie riadkových operácii a zároveň aj na skontrolovanie optimálneho riešenia.
Prvý riadok tabuľky hovorí, ktorú premennú daný stĺpec predstavuje. Nasledujúce dva riadky obsahujú koeficienty z rovníc ohraničenia a posledný riadok obsahuje koeficienty účelovej funkcie.
Tabuľka teda vyzerá takto:

x1 x2 s1 s2 s3 b
2 1 1 0 0 500
2 3 0 1 0 1200
3 4 0 0 1 1500
120 100 0 0 0

Keď máme vytvorenú tabuľku, môžeme hneď skontrolovať, či už náhodou neobsahuje optimálne riešenie. Optimálne riešenie hľadáme podľa posledného riadku. Ak máme maximalizačný problém, všetky hodnoty v ňom musia byť menšie/rovné nule, ak je problém minimalizačný, musia byť väčšie/rovné nule. Ako ale môžeme vidieť, máme tam dve hodnoty väčšie ako nula, musíme teda pokračovať ďalším krokom. (Brezina and Pekár 2018)

Pivotová premenná

Pivotová premenná sa používa pri riadkových operáciach na určenie, ktorá premenná sa stane jednotkovou hodnotou. Pivotovú premennú nájdeme podľa posledného riadku. Pri predpoklade, že naše riešenie ešte nie je optimálne, vyberieme najväčšiu hodnotu v poslednom riadku a jedna z hodnôt v jej stĺpci sa stane pivotovou premennou. Číslo v stĺpci b predelíme číslom v stĺpci s potenciálnym pivotom. Toto číslo nazveme indikátorom a vyberieme riadok, v ktorom má indikátor najmenšiu hodnotu.

Najväčšiu hodnotu v poslednom riadku máme 120 v stĺpci \(x_1\) a najmenší indikátor je v prvom riadku:
x1 x2 s1 s2 s3 b indikator
2 1 1 0 0 500 500/2 = 250
2 3 0 1 0 1200 1200/2 = 600
3 4 0 0 1 1500 1500/3 = 500
120 100 0 0 0

Teda našou pivotovou premennou sa stane hodnota 2 v prvom riadku stĺpca \(x_1\).

Vytvorenie novej tabuľky

Nová tabuľka poslúži na identifikovanie nového potenciálne optimálneho riešenia. Pivotová premenná bola určená v predošlom kroku a teraz podľa nej vieme vykonať riadkové operácie, po ktorých zostane tabuľka ekvivalentná k pôvodnej.
Pivotovú premennú musíme previesť na jednotku, čo znamená, že celý riadok vydelíme hodnotou pivota.
x1 x2 s1 s2 s3 b
1 0.5 0.5 0 0 250
2 3.0 0.0 1 0 1200
3 4.0 0.0 0 1 1500
120 100.0 0.0 0 0 0
Teraz (ako pri maticových riadkových operáciách), chceme “vynulovať” hodnoty v tom istom stĺpci ako je jednotková premenná. Odpočítame dvojnásobok prvého riadku od druhého. Odpočítame trojnásobok prvého riadku od tretieho atď.
x1 x2 s1 s2 s3 b
1 0.5 0.5 0 0 250
0 2.0 -1.0 1 0 700
0 2.5 -1.5 0 1 750
0 40.0 -60.0 0 0
Teraz môžme opäť skontrolovať, či už máme k dispozícii optimálne riešenie. Pri našom maximalizačnom probléme očakávame v poslednom riadku hodnoty menšie/rovné nule a máme tam hodnotu 40, preto musíme pokračovať.
Najväčšia hdnota v poslednom riadku je práve týchto 40, a preto naša nová pivotová premenná bude v príslušnom stĺpci. Zopakujeme postup a zistíme, že nová pivotová premenná je v stĺpci \(x_2\) v treťom riadku
x1 x2 s1 s2 s3 b indikator
1 0.5 0.5 0 0 250 250/0.5 = 500
0 2.0 -1.0 1 0 700 700/2 = 350
0 2.5 -1.5 0 1 750 750/2.5 = 300
0 40.0 -60.0 0 0
Postup pokračuje rovnako ako v prvej iterácii.
x1 x2 s1 s2 s3 b
1 0 0.8 0 -0.2 100
0 0 0.2 1 -0.8 100
0 1 -0.6 0 0.4 300
0 0 -36.0 0 -16.0

Teraz keď sa pozrieme na posledný riadok tabuľky, už by sme mali mať optimálne riešenie.
Optimálne rišenie v tabuľke nájdeme identifikovaním bázových a nebázových premenných. Bázová premenná je tá, ktorá má v stĺpci jednu hodnotu 1 a ostatné 0. Ak premenná tieto kritériá nespĺňa, je nebázová.
Pre nebázové premenné platí, že optimálne riešenie pre túto premennú je nula. Ak je premenná bázová, jej optimálne riešenie sa nachádza v riadku s jednotkou, v stĺpci b.
V našom prípade sú bázové premenné \(x_1\) a \(x_2\) (to sme aj očakávali, pretože \(s_1\), \(s_2\) a \(s_3\) boli umelo pridané) a premenné \(s_{1,2,3}\) sú nebázové. Prislúchajúce hodnoty bázových premenných sú \(x_1=100\) a \(x_2=300\) a to predstavuje naše optimálne riešenie. Po dosadení do účelovej funkcie: \(f(x_1,x_2)=42000\).
Našli sme rovnaké riešenie aj simplexovou metódou.
Výhodou simplexovej metódy je využiteľnosť pri viac ako dvoch premenných a pomerne jednoduchá možnosť použitia aj na počítači (napr. Excel).

Záver

Lineárne programovanie je veľmi dôležitým odvetvím aplikovanej matematiky, ktoré dokáže riešiť rôzne druhy optimalizačných problémov. Riešenie optimalizačných problémov lineárnym programovaním je jednoduchým prostriedkom ponúkajúcim spoločnostiam/priemyslu spraviť to najviac priaznivé rozhodnutie v danej situácii. Jeho najväčšou výhodou ako optimalizačnej metódy je, že vždy nájde optimálne riešenie, ak nejaké existuje.

Literatúra

Brezina, Ivan, and Juraj Pekár. 2018. “Úvod Do Operačného Výskumu I.” Vydavateľstvo Letra Edu.
Brilliant.org. n.d. “Linear Programming.” https://brilliant.org/wiki/linear-programming/.
Thie, Paul R., and Gerard E. Keough. 2008. An Introduction to Linear Programming and Game Theory. John Wiley & Sons, Inc.
Toma, Vladimír. 2008. Základy Lineárneho Programovania. Knižničné a edičné centrum FMFI UK. https://zona.fmph.uniba.sk/fileadmin/fmfi/sluzby/elektronicke_studijne_materialy/ip_uk/Zaklady_linerne_programovanie.pdf.