Optimalizácia vám pomáha nájsť najlepší výsledok, ktorý prináša zisk, znižuje náklady alebo nastavuje parameter, ktorý spôsobuje zlyhania obchodných procesov.
Tento proces sa nazýva aj matematické programovanie. Rieši problém určenia rozdelenia obmedzených zdrojov potrebných na dosiahnutie cieľa stanoveného vedúcim optimalizačného problému. Zo všetkých možných možností je žiaduce nájsť tú, ktorá maximalizuje (alebo znižuje) kontrolný parameter, napríklad zisk alebo náklady. Optimalizačné modely sa tiež nazývajú normatívne alebo normatívne, pretože sa snažia nájsť realizovateľnú stratégiu pre podnikanie.
História vývoja
Lineárne programovanie (LP) pracuje s triedou optimalizačných problémov, kde sú všetky obmedzenia lineárne.
Predstavujeme stručnú históriu vývoja LP:
- V roku 1762 Lagrange vyriešil jednoduché optimalizačné problémy s obmedzeniami rovnosti.
- V roku 1820 sa Gauss rozhodollineárny systém rovníc využívajúci elimináciu.
- V roku 1866 Wilhelm Jordan zdokonalil metódu hľadania chýb najmenších štvorcov ako vhodného kritéria. Toto sa teraz nazýva Gauss-Jordanova metóda.
- Digitálny počítač sa objavil v roku 1945.
- Danzig vynašiel simplexové metódy v roku 1947.
- V roku 1968 predstavili Fiacco a McCormick metódu Inside Point.
- V roku 1984 použil Karmarkar metódu interiéru na riešenie lineárnych programov a pridal k tomu svoju inovatívnu analýzu.
LP sa ukázalo ako mimoriadne výkonný nástroj na modelovanie problémov v reálnom svete aj ako široko používaná matematická teória. Mnohé zaujímavé optimalizačné problémy sú však nelineárne.
Čo robiť v tomto prípade? Štúdium takýchto problémov zahŕňa pestrú zmes lineárnej algebry, mnohorozmerného počtu, numerickej analýzy a výpočtových metód. Vedci vyvíjajú výpočtové algoritmy vrátane metód vnútorných bodov pre lineárne programovanie, geometriu, analýzu konvexných množín a funkcií a štúdium špeciálne štruktúrovaných problémov, ako je kvadratické programovanie.
Nelineárna optimalizácia poskytuje základné pochopenie matematickej analýzy a je široko používaná v rôznych oblastiach, ako je inžinierstvo, regresná analýza, manažment zdrojov, geofyzikálny prieskum a ekonómia.
Klasifikácia problémov s optimalizáciou
Dôležitý krokProces optimalizácie je klasifikácia modelov, pretože ich algoritmy riešenia sú prispôsobené konkrétnemu typu.
1. Problémy s diskrétnou a kontinuálnou optimalizáciou. Niektoré modely majú zmysel iba vtedy, ak premenné nadobúdajú hodnoty z diskrétnej podmnožiny celých čísel. Iné obsahujú údaje, ktoré môžu nadobudnúť akúkoľvek skutočnú hodnotu. Zvyčajne sa dajú ľahšie vyriešiť. Vylepšenia algoritmov v kombinácii s pokrokom vo výpočtovej technológii dramaticky zvýšili veľkosť a zložitosť problému optimalizácie lineárneho programovania.
2. Neobmedzená a obmedzená optimalizácia. Ďalším dôležitým rozdielom sú úlohy, kde neexistujú žiadne obmedzenia na premenné. Môže siahať od jednoduchých odhadov až po systémy rovnosti a nerovností, ktoré modelujú zložité vzťahy medzi údajmi. Takéto optimalizačné problémy možno ďalej klasifikovať podľa povahy funkcií (lineárne a nelineárne, konvexné a hladké, diferencovateľné a nediferencovateľné).
3. Úlohy realizovateľnosti. Ich cieľom je nájsť premenné hodnoty, ktoré spĺňajú obmedzenia modelu bez konkrétneho cieľa optimalizácie.
4. Komplementárne úlohy. Sú široko používané v technológiách a ekonomike. Cieľom je nájsť riešenie, ktoré spĺňa podmienky komplementarity. V praxi sa úlohy s niekoľkými cieľmi často preformulujú na úlohy s jedným cieľom.
5. Deterministická verzus stochastická optimalizácia. Deterministická optimalizácia predpokladá, že údaje prezadania sú úplne presné. V mnohých aktuálnych otázkach však nemôžu byť známe z mnohých dôvodov.
Prvý sa týka jednoduchej chyby merania. Druhý dôvod je zásadnejší. Spočíva v tom, že niektoré údaje predstavujú informácie o budúcnosti, napríklad dopyt po produkte alebo cena na budúce časové obdobie. Pri optimalizácii za podmienok stochastickej optimalizácie je do modelu zahrnutá neistota.
Hlavné komponenty
Cieľová funkcia je tá, ktorá sa má minimalizovať alebo maximalizovať. Väčšina typov optimalizačných problémov má jednu cieľovú funkciu. Ak nie, často sa dajú preformulovať tak, aby fungovali.
Dve výnimky z tohto pravidla:
1. Úloha zacielenia na vyhľadávanie. Vo väčšine obchodných aplikácií chce manažér dosiahnuť konkrétny cieľ a zároveň uspokojiť modelové obmedzenia. Používateľ nechce niečo zvlášť optimalizovať, preto nemá zmysel definovať objektívnu funkciu. Tento typ sa bežne označuje ako problém s uspokojením.
2. Veľa objektívnych funkcií. Používateľ by často chcel optimalizovať niekoľko rôznych cieľov naraz. Zvyčajne sú nekompatibilné. Premenné, ktoré sa optimalizujú pre jeden cieľ, nemusia byť pre iné najlepšie.
Typy komponentov:
- Kontrolovaný vstup je súbor rozhodovacích premenných, ktoré ovplyvňujú hodnotu cieľovej funkcie. Vo výrobnej úlohe môžu premenné zahŕňať distribúciu rôznych dostupných zdrojov alebo potrebnej prácekaždá akcia.
- Obmedzenia sú vzťahy medzi rozhodovacími premennými a parametrami. Pri produkčnom probléme nemá zmysel tráviť veľa času akoukoľvek aktivitou, preto obmedzte všetky „dočasné“premenné.
- Možné a optimálne riešenia. Hodnota rozhodnutia pre premenné, pri ktorej sú splnené všetky obmedzenia, sa nazýva splniteľné. Väčšina algoritmov ho najskôr nájde a potom sa ho pokúsi vylepšiť. Nakoniec menia premenné, aby prešli z jedného možného riešenia na druhé. Tento proces sa opakuje, kým cieľová funkcia nedosiahne maximum alebo minimum. Tento výsledok sa nazýva optimálne riešenie.
Algoritmy optimalizačných problémov vyvinuté pre nasledujúce matematické programy sú široko používané:
- Konvexné.
- Oddeliteľné.
- Kvadratické.
- Geometrické.
Google Linear Solvers
Lineárna optimalizácia alebo programovanie je názov daný výpočtovému procesu optimálneho riešenia problému. Je modelovaný ako súbor lineárnych vzťahov, ktoré vznikajú v mnohých vedeckých a inžinierskych disciplínach.
Google ponúka tri spôsoby riešenia problémov lineárnej optimalizácie:
- Glop open source knižnica.
- Doplnok Linear Optimization pre Tabuľky Google.
- Služba lineárnej optimalizácie v skripte Google Apps.
Glop je zabudovaný do Googlulineárny riešič. Je dostupný v open source. K Glop sa môžete dostať cez OR-Tools lineárny riešič obalov, čo je obal pre Glop.
Modul lineárnej optimalizácie pre Tabuľky Google vám umožňuje vykonať lineárne vyjadrenie problému optimalizácie zadaním údajov do tabuľky.
Kvadratické programovanie
Platforma Premium Solver využíva rozšírenú LP/Quadratic verziu metódy Simplex s limitmi spracovania problémov LP a QP až do 2000 rozhodovacích premenných.
SQP Riešiteľ pre rozsiahle problémy využíva modernú implementáciu metódy aktívnej množiny s riedkym riešením problémov kvadratického programovania (QP). Motor XPRESS Solver využíva prirodzené rozšírenie metódy „Interior Point“alebo Newton Barrier na riešenie problémov QP.
MOSEK Solver používa vložené metódy „Inside Point“a automatické duálne metódy. Toto je obzvlášť účinné pre voľne spojené problémy QP. Môže tiež vyriešiť problémy so škálovým kvadratickým obmedzením (QCP) a druhým rádovým kužeľovým programovaním (SOCP).
Viacoperačné výpočty
Pomerne úspešne sa používajú s využitím funkcií balíka Microsoft Office, napríklad pri riešení problémov s optimalizáciou v Exceli.
V tabuľke vyššie sú symboly:
- K1 – K6 – zákazníci, ktorí potrebujú dodať tovar.
- S1 - S6 sú potenciálne výrobné závody, ktoré by sa na to dali postaviť. Dá sa vytvoriť1, 2, 3, 4, 5 alebo všetkých 6 miest.
Pre každé zariadenie uvedené v stĺpci I sú fixné náklady (Fix).
Ak sa poloha nič nezmení, nebude sa počítať. Potom nebudú žiadne fixné náklady.
Identifikujte potenciálne miesta, aby ste získali najnižšie náklady.
V týchto podmienkach je miesto buď stanovené, alebo nie. Tieto dva stavy sú: „PRAVDA – NEPRAVDA“alebo „1 – 0“. Existuje šesť stavov pre šesť miest, napríklad 000001 je nastavené iba na šieste, 111111 je nastavené na všetky.
V systéme binárnych čísel existuje presne 63 rôznych možností od 000001 (1) do 111111 (63).
L2-L64 by teraz malo znieť {=VIACNÁSOBNÁ PREVÁDZKA (K1)}, toto sú výsledky všetkých alternatívnych riešení. Potom je minimálna hodnota=Min (L) a zodpovedajúca alternatíva je INDEX (K).
Programovanie celých čísel CPLEX
Niekedy lineárny vzťah nestačí na to, aby sme sa dostali k jadru obchodného problému. To platí najmä vtedy, keď rozhodnutia zahŕňajú diskrétne voľby, ako napríklad, či otvoriť alebo neotvoriť sklad na určitom mieste. V týchto situáciách sa musí použiť celočíselné programovanie.
Ak problém zahŕňa diskrétne aj spojité voľby, ide o zmiešaný celočíselný program. Môže mať lineárne, konvexné kvadratické problémy a rovnaké obmedzenia druhého rádu.
Celočíselné programy sú oveľa zložitejšie ako lineárne programy, ale majú dôležité obchodné aplikácie. softvérSoftvér CPLEX využíva zložité matematické metódy na riešenie celočíselných problémov. Jeho metódy zahŕňajú systematické hľadanie možných kombinácií diskrétnych premenných pomocou lineárnych alebo kvadratických softvérových relaxácií na výpočet hraníc hodnoty optimálneho riešenia.
Na výpočet obmedzení tiež používajú LP a iné metódy riešenia problémov s optimalizáciou.
Štandardný riešiteľ Microsoft Excel
Táto technológia využíva základnú implementáciu hlavnej metódy Simplex na riešenie problémov s LP. Je obmedzený na 200 premenných. "Premium Solver" používa vylepšenú primárnu simplexovú metódu s obojstrannými hranicami premenných. Platforma Premium Solver využíva rozšírenú verziu LP/Quadratic Simplex Solver na riešenie optimalizačného problému s až 2000 rozhodovacími premennými.
Rozsiahly LP pre platformu Premium Solver využíva najmodernejšiu implementáciu jednoduchej a dvojitej simplexovej metódy, ktorá využíva vzácnosť v modeli LP na úsporu času a pamäte, pokročilé stratégie aktualizácie a refaktoring matíc, viacnásobné a čiastočné oceňovanie a rotácie a na prekonanie degenerácie. Tento motor je dostupný v troch verziách (schopný spracovať až 8 000, 32 000 alebo neobmedzené množstvo premenných a limitov).
MOSEK Solver obsahuje primárny a duálny simplex, metódu, ktorá tiež využíva vzácnosť a využíva pokročilé stratégie na aktualizáciu matíc a „refaktorizáciu“. Rieši problémy neobmedzenej veľkosti, boltestované na problémoch lineárneho programovania s miliónmi rozhodovacích premenných.
Príklad krok za krokom v EXCEL
Ak chcete definovať model problému optimalizácie v Exceli, vykonajte nasledujúce kroky:
- Usporiadajte údaje o probléme do tabuľky v logickej forme.
- Vyberte bunku na uloženie každej premennej.
- Vytvorte v bunke vzorec na výpočet cieľového matematického modelu optimalizačného problému.
- Vytvorte vzorce na výpočet ľavej strany každého obmedzenia.
- Pomocou dialógov v Exceli povedzte Riešiteľovi o rozhodovacích premenných, cieľoch, obmedzeniach a požadovaných hraniciach týchto parametrov.
- Spustite "Solver" a nájdite optimálne riešenie.
- Vytvorte excelový hárok.
- Usporiadajte údaje pre problém v Exceli, kde sa vypočíta vzorec pre účelovú funkciu a obmedzenie.
V tabuľke vyššie sú bunky B4, C4, D4 a E4 vyhradené na reprezentáciu rozhodovacích premenných X 1, X 2, X 3 a X 4. Príklady rozhodnutí:
- Model produktového mixu (zisk 450 USD, 1 150 USD, 800 USD a 400 USD na produkt) bol zadaný do buniek B5, C5, D5 a E5. To umožňuje vypočítať cieľ v F5=B5B4 + C5C4 + D5D4 + E5E4 alebo F5:=SUMPRODUCT (B5: E5, B4: E4).
- V B8 zadajte množstvo zdrojov potrebných na výrobu každého typu produktu.
- Vzorec pre F8:=SUMPRODUCT(B8:E8, $B$4:$E$4).
- Skopírujte totovzorec v F9. Znaky dolára v $B$4:$E$4 označujú, že tento rozsah buniek zostáva konštantný.
- V G8 zadajte dostupné množstvo zdrojov každého typu, zodpovedajúce hodnotám obmedzení vpravo. To vám umožní vyjadriť ich takto: F11<=G8: G11.
- Toto zodpovedá štyrom limitom F8<=G8, F9 <=G9, F10 <=G10 a F11=0
Oblasti praktického použitia metódy
Lineárna optimalizácia má mnoho praktických aplikácií ako príklad optimalizačného problému:
Spoločnosť môže vyrobiť niekoľko produktov so známou maržou príspevku. Výroba jednotky každej položky vyžaduje známe množstvo obmedzených zdrojov. Úlohou je vytvoriť výrobný program, ktorý určí, koľko z každého produktu by sa malo vyrobiť tak, aby bol zisk spoločnosti maximalizovaný bez porušenia obmedzení zdrojov.
Problémy s miešaním sú riešením problémov s optimalizáciou, ktoré súvisia s kombinovaním prísad do konečného produktu. Príkladom toho je problém stravovania, ktorý študoval George Danzig v roku 1947. Uvádza sa množstvo surovín, ako je ovos, bravčové mäso a slnečnicový olej, spolu s ich nutričným obsahom, ako sú bielkoviny, tuk, vitamín A, a ich cena za kilogram. Výzvou je namiešať jeden alebo viacero konečných produktov zo surovín pri najnižších možných nákladoch pri rešpektovaní minimálnych a maximálnych limitov pre ich nutričnú hodnotu.
Klasickou aplikáciou problému lineárnej optimalizácie je určenie smerovania pre potrebyprevádzky v telekomunikačných alebo dopravných sieťach. Zároveň musia byť toky smerované cez sieť takým spôsobom, aby boli splnené všetky požiadavky na prevádzku bez porušenia podmienok šírky pásma.
V matematickej teórii možno lineárnu optimalizáciu použiť na výpočet optimálnych stratégií v hrách s nulovým súčtom pre dvoch ľudí. V tomto prípade sa vypočíta rozdelenie pravdepodobnosti pre každého účastníka, čo je koeficient náhodného miešania jeho stratégií.
Žiadny úspešný obchodný proces na svete nie je možný bez optimalizácie. Existuje veľa optimalizačných algoritmov. Niektoré metódy sú vhodné len pre určité typy problémov. Je dôležité vedieť rozpoznať ich vlastnosti a vybrať vhodnú metódu riešenia.
