Optimalizácia SIMPLEX metódou

Simplexová optimalizačná metóda

Simplex algoritmus, alebo Simplexová metóda, je veľmi rozšírený spôsob riešenia úloh lineárneho programovania.

Ako to funguje?

Aby sme mohli aplikovať Simplex na vyriešenie problému, musí byť tento problém zadaný v štandardnom tvare, teda:

V časti Lineárne programovanie sme opísali, ako z ohraničení v tvare nerovnosti vznikne konvexná množina prípustných riešení, ktorú sme označili M. Pre viacrozmerné problémy lineárneho programovania vytvárajú ohraničenia tzv. konvexný mnohosten:

Obr. 1 - príklad konvexného mnohostena

Bod x = (x_i, ... , x_n) je vrcholom mnohostena práve vtedy a len vtedy, ak prvky stĺpcových vektorov A_i ( A_i je podmnožina množiny všetkých ohraničení), ktorým prislúcha vektor nenulových vstupov x (x_i ≠ 0), sú lineárne nezávislé. Vrcholy mnohostena teda predstavujú najmenšie možné priesečníky ohraničení. Takýto vrchol nazývame zlučiteľné bázické riešenie.

Možno dokázať, že ak hodnota účelovej funkcie J problému lineárneho programovania v štandardnom tvare nadobúda maximum v množine prípustných riešení M, nadobúda ho v aspoň jednom vrchole mnohostena (množiny M).

Optimálne riešenie problému sa teda musí nachádzať na jednom z vrcholov, čo znamená, že pri hľadaní tohto riešenia hľadáme jedno z konečného počtu možných riešení. Počet riešení teda nie je nekonečný, no napriek tomu je pre bežné optimalizačné problémy veľmi veľký.

Dá sa tiež dokázať, že ak vo vrchole x množiny M nenadobúda účelová funkcia maximum, t.j. ak x nie je optimálnym riešením, musí tento bod ležať na takej hrane mnohostena, po ktorej keď sa posúvame smerom od bodu x, hodnota účelovej funkcie sa buď zvyšuje, alebo nemení.

Ak je táto spojnica nekonečná, jedná sa o neohraničený problém.
Ak je spojnica ukončená nejakým vrcholom y, tak platí že f(y) ≥ f(x).

Simplexová metóda využíva práve tieto poznatky. Prvým krokom pri riešení úlohy lineárneho programovania simplexovou metódou je nájsť nejaký počiatočný vrchol množiny prípustných riešení – zlučiteľné bázické riešenie, ktoré označíme x₀ .
Bod x₀ je prvkom viacerých spojníc. Treba vybrať takú spojnicu, na ktorej bude hodnota účelovej funkcie väčšia alebo rovná x₀ . Táto spojnica končí vo vrchole, ktorý označíme x₁. V prípade, že hodnota f(x₁) nie je optimálna, znova hľadáme spojnicu, na ktorej je hodnota vyššia, a jej druhým vrcholom je x₂ . Ak je problém ohraničený, týmto postupom sa dopracujeme k optimálnemu riešeniu.

Obr. 2 - ilustrácia Simplex algoritmu