Optimalizace (matematika)

Optimalizace (v matematice , informatice a operačním výzkumu ) je úkolem najít extrém (minimum nebo maximum) účelové funkce v nějaké oblasti konečnorozměrného vektorového prostoru , omezeného množinou lineárních a/nebo ne lineární rovnosti a/nebo nerovnosti .

Teorie a metody řešení optimalizačního problému jsou studovány matematickým programováním .

Matematické programování  je odvětví matematiky, které rozvíjí teorii, numerické metody pro řešení vícerozměrných problémů s omezeními. [jeden]

Prohlášení o optimalizačním problému

V procesu návrhu je úkol obvykle nastaven na určení nejlepší v jistém smyslu struktury nebo hodnot parametrů objektu . Takový problém se nazývá optimalizační problém. Pokud je optimalizace spojena s výpočtem optimálních hodnot parametrů pro danou strukturu objektu, pak se nazývá parametrická optimalizace . Problémem výběru optimální struktury je strukturální optimalizace .

Tímto způsobem je formulován standardní matematický optimalizační problém. Mezi prvky χ, které tvoří množiny X, najděte prvek χ * , který poskytuje minimální hodnotu f(χ * ) dané funkce f(χ). Pro správné zadání optimalizačního problému je nutné nastavit:

1. Přípustná množina  je množina ;
2. Objektivní funkce  - mapování ;
3. Vyhledávací kritérium (max nebo min).

Pak vyřešit problém znamená jeden z:

1. Ukaž to .
2. Ukažte, že účelová funkce není níže omezena.
3. Najít .
4. Pokud , tak najděte .

Pokud minimalizovaná funkce není konvexní , pak se často omezují na hledání lokálních minim a maxim: bodů takových, že všude v některém z jejich sousedství je minimum a maximum.

Pokud je množina přípustná , pak se takový problém nazývá nepodmíněný optimalizační problém , v opačném případě podmíněný optimalizační problém .

Klasifikace optimalizačních metod

Obecný zápis optimalizačních problémů definuje širokou škálu jejich tříd. Volba metody (efektivita jejího řešení) závisí na třídě problému. Klasifikace problémů je určena: účelovou funkcí a přípustnou oblastí (danou systémem nerovností a rovností nebo složitějším algoritmem). [2]

Optimalizační metody jsou klasifikovány podle optimalizačních úloh:

• Lokální metody: konvergují k nějakému lokálnímu extrému účelové funkce. V případě unimodální účelové funkce je tento extrém jedinečný a bude globálním maximem/minimem.
• Globální metody: zabývají se víceextrémními objektivními funkcemi. Při globálním vyhledávání je hlavním úkolem identifikovat trendy v globálním chování účelové funkce.

V současnosti existující metody vyhledávání lze rozdělit do tří velkých skupin:

1. deterministický;
2. náhodný (stochastický);
3. kombinovaný.

Podle kritéria dimenze proveditelného souboru se optimalizační metody dělí na jednorozměrné optimalizační metody a vícerozměrné optimalizační metody .

Podle tvaru účelové funkce a přípustné množiny lze optimalizační problémy a metody jejich řešení rozdělit do následujících tříd:

• Optimalizační problémy, kde účelová funkce a omezení jsou lineární funkce, jsou řešeny metodami tzv. lineárního programování .
• Jinak se člověk zabývá problémem nelineárního programování a aplikuje vhodné metody. Na druhé straně se od nich liší dva konkrétní úkoly:
  • jestliže a  jsou konvexní funkce, pak se takový problém nazývá konvexní programovací problém ;
  • if , pak máme co do činění s celočíselným (diskrétním) programovacím problémem .

Podle požadavků na hladkost a přítomnost parciálních derivací v účelové funkci je lze dále rozdělit na:

• přímé metody, které vyžadují pouze výpočet účelové funkce v aproximačních bodech;
• metody prvního řádu : vyžadují výpočet prvních parciálních derivací funkce;
• metody druhého řádu: vyžadují výpočet druhých parciálních derivací, tj. Hessián účelové funkce.

Kromě toho jsou optimalizační metody rozděleny do následujících skupin:

• analytické metody (např. metoda Lagrangeových multiplikátorů a podmínky Karush - Kuhn - Tucker );
• numerické metody ;
• grafické metody .

V závislosti na povaze množiny X jsou problémy matematického programování klasifikovány jako:

• problémy diskrétního programování (nebo kombinatorická optimalizace ) - pokud je X konečné nebo spočetné ;
• problémy programování celých čísel  - pokud X je podmnožinou množiny celých čísel;
• problémy nelineárního programování, pokud omezení nebo účelová funkce obsahují nelineární funkce a X je podmnožinou konečněrozměrného vektorového prostoru .
• Pokud všechna omezení a účelová funkce obsahují pouze lineární funkce, pak se jedná o problém lineárního programování.

Kromě toho jsou odvětvími matematického programování parametrické programování , dynamické programování a stochastické programování .

Matematické programování se používá při řešení optimalizačních problémů v operačním výzkumu .

Způsob nalezení extrému je zcela určen třídou problému. Než však získáte matematický model, musíte provést 4 fáze modelování:

• Stanovení hranic optimalizačního systému
  • Vyřadíme ta spojení optimalizačního objektu s vnějším světem, která nemohou výrazně ovlivnit výsledek optimalizace, nebo přesněji ta, bez kterých je řešení zjednodušeno.
• Volba regulovaných veličin
  • „Zmrazíme“ hodnoty některých proměnných (nespravované proměnné). Ostatní jsou ponecháni na převzetí jakýchkoli hodnot z oblasti přípustných rozhodnutí (řízené proměnné)
• Definování omezení u řízených proměnných
  • … (rovnosti a/nebo nerovnosti)
• Volba numerického optimalizačního kritéria (např. ukazatel výkonu )
  • Vytvořte účelovou funkci

Historie

Problémy lineárního programování byly prvními podrobně studovanými problémy hledání extrému funkcí v přítomnosti omezení , jako jsou nerovnosti . V roce 1820 Fourier a poté v roce 1947 George Dantzig navrhli metodu řízeného počítání sousedních vrcholů ve směru rostoucí účelové funkce  - simplexovou metodu , která se stala hlavní při řešení problémů lineárního programování.

Přítomnost termínu „programování“ v názvu disciplíny se vysvětluje skutečností, že první studie a první aplikace úloh lineární optimalizace byly v oblasti ekonomie, protože v angličtině slovo „programming“ znamená plánování , kreslení plány nebo programy. Je zcela přirozené, že terminologie odráží úzký vztah, který existuje mezi matematickou formulací problému a jeho ekonomickou interpretací (studium optimálního ekonomického programu). Termín „ lineární programování “ navrhl J. Danzig v roce 1949 ke studiu teoretických a algoritmických problémů souvisejících s optimalizací lineárních funkcí s lineárními omezeními.

Proto název „matematické programování“ je dán tím, že cílem řešení problémů je zvolit optimální program akcí.

Identifikace třídy extrémních problémů definovaných lineárním funkcionálem na množině definované lineárními omezeními by měla být připsána 30. letům 20. století. Jedním z prvních, kdo studoval problémy lineárního programování v obecné formě, byli: John von Neumann  , matematik a fyzik, který dokázal hlavní větu o maticových hrách a studoval ekonomický model , který nese jeho jméno, a L. V. Kantorovich  , sovětský akademik, Nobel Vítěz ceny (1975), který formuloval řadu problémů lineárního programování a v roce 1939 navrhl metodu jejich řešení ( metodu řešení faktorů ), která se mírně liší od simplexové metody.

V roce 1931 maďarský matematik B. Egervari uvažoval o matematické formulaci a vyřešil problém lineárního programování zvaný „problém výběru“, metoda řešení se nazývala „ maďarská metoda “.

L. V. Kantorovich a M. K. Gavurin vyvinuli v roce 1949 metodu potenciálů , která se používá při řešení dopravních problémů . V dalších dílech L. V. Kantoroviče, V. S. Němčinova , V. V. Novožilova , A. L. Lurieho , A. Brudna , A. G. Aganbegyana , D. B. Yudina , E. G. Golshteina a dalších matematici a ekonomové dále rozvinuli jak lineární, tak nelineární aplikaci jeho metod lineárního programování a nelineární teorie. ke studiu různých ekonomických problémů.

Metodám lineárního programování se věnuje mnoho prací zahraničních vědců. V roce 1941 stanovil F. L. Hitchcock dopravní výzvu . Základní metoda pro řešení úloh lineárního programování, simplexová metoda  , byla publikována v roce 1949 J. Dantzigem. Metody lineárního a nelineárního programování byly dále rozvíjeny v pracích G. Kuhna , A. Tuckera , Gasse (Saul I. Gass), Charnese (A. Charnes), Bealeho ( EM Beale) a dalších.

Souběžně s rozvojem lineárního programování byla velká pozornost věnována problémům nelineárního programování , ve kterých jsou nelineární buď účelová funkce , omezení, nebo obojí. V roce 1951 vyšla práce G. Kuhna a A. Tuckera , ve které byly dány nutné a dostatečné podmínky optimality pro řešení problémů nelineárního programování. Tato práce vytvořila základ pro další výzkum v této oblasti.

Od roku 1955 bylo publikováno mnoho prací věnovaných kvadratickému programování (práce Beala, Barankina a R. Dorfmana , Franka (M. Frank) a F. Wolfa , G. Markowitze aj.). Práce Dennise (JB Dennis), Rosena (JB Rosen) a Zontendijka (G. Zontendijk) vyvinuly gradientové metody pro řešení problémů nelineárního programování.

V současné době byly pro efektivní aplikaci metod matematického programování a řešení problémů na počítačích vyvinuty algebraické modelovací jazyky , jejichž představiteli jsou AMPL a LINGO .

Viz také

• Vícecílová optimalizace
• Matematická analýza
• Skalární hodnocení

Poznámky

1. ↑ Zdroj: Altai Regional Universal Scientific Library. V. Ya. Shishkova (AKUNB) Archivováno 5. března 2022 na Wayback Machine . Metody optimalizace: Proc. příspěvek. Brazovskaya N.V.; Altajská státní technická univerzita I. I. Polzunova, [Centrum dálky. školení].-Barnaul: Nakladatelství AltSTU, 2000, 120 s. - UDC / LBC 22.183.4 B871
2. ↑ Hledání optima: Počítač rozšiřuje možnosti . - M .: Nauka, 1989. - S.  14 . — ISBN 5-02-006737-7 .

Literatura

• Abakarov A. Sh., Sushkov Yu. A. Statistická studie jednoho globálního optimalizačního algoritmu . - Sborník FORA, 2004.
• Akulich I. L. Matematické programování v příkladech a úlohách: Proc. příspěvek na studentské hospodářství. specialista. vysoké školy. - M .: Vyšší škola, 1986.
• Gill F., Murray W., Wright M. Praktická optimalizace. Za. z angličtiny. — M .: Mir, 1985.
• Girsanov IV Přednášky o matematické teorii extrémních problémů. - M .; Iževsk : Výzkumné centrum "Regular and Chaotic Dynamics", 2003. - 118 s. — ISBN 5-93972-272-5 .
• Zhiglyavsky A. A., Zhilinkas A. G. Metody hledání globálního extrému. — M .: Nauka, Fizmatlit , 1991.
• Karmanov VG Matematické programování. - Fyzikálně-matematické nakladatelství. Literatura, 2004.
• Korn G., Korn T. Příručka matematiky pro vědce a inženýry. - M .: Nauka, 1970. - S. 575-576.
• Korshunov Yu.M., Korshunov Yu.M. Matematické základy kybernetiky. — M .: Energoatomizdat , 1972.
• Lotov A. V. , Pospelová I. I. Přednáškové poznámky k teorii a metodám multikriteriální optimalizace. Archivováno 21. ledna 2022 na Wayback Machine vyrovnání M., 2005. 127 s.
• Maksimov Yu. A., Filippovskaya EA Algoritmy pro řešení problémů nelineárního programování. — M. : MEPhI, 1982.
• Maksimov Yu.A. Lineární a diskrétní programovací algoritmy. — M. : MEPhI, 1980.
• Plotnikov A.D. Matematické programování = expresní kurz. - 2006. - S. 171. - ISBN 985-475-186-4 .
• Rastrigin L. A. Statistické metody vyhledávání. - M. , 1968.
• Sergeev Ya. D., Kvasov D. E. Diagonální metody globální optimalizace Archivováno 26. října 2017 na Wayback Machine . — M.: FIZMATLIT, 2008. 341s.
• Hemdy A. Taha. Úvod do operačního výzkumu = Operační výzkum: Úvod. - 8. vyd. - M .: Williams , 2007. - S. 912. - ISBN 0-13-032374-8 .
• Kini RL, Raifa H. Rozhodování podle více kritérií: preference a substituce. - M . : Rozhlas a komunikace, 1981. - 560 s.
• Zukhovitsky S. I. , Avdeeva L. I. Lineární a konvexní programování. - 2. vyd., přepracováno. a další .. - M . : Nakladatelství "Nauka", 1967.
• Minaev Yu. N. Stabilita ekonomických a matematických optimalizačních modelů. - M .: Statistika, 1980.
• Moiseev NN Numerické metody v teorii optimálních systémů . - M. : Nauka, 1971. - 424 s.
• Moiseev NN Základy teorie optimálních systémů . — M .: Nauka, 1975. — 528 s.
• Moiseev NN , Ivanilov Yu.P. , Stolyarova EM Optimalizační metody . - M. : Nauka, 1978. - 352 s.

• Degtyarev Yu I. Metody optimalizace. - M . : Sovětský rozhlas, 1980. - 272 s.
• Rekleitis G., Reyvindran A., Ragsdel K. Optimalizace ve strojírenství. - M .: Mir, 1986. - 400 s.
• Romanovský IV Algoritmy pro řešení extrémních problémů. — M .: Nauka, 1977. — 352 s. - 16 000 výtisků.
• Umnov A.E. , Úmnov E.A. Parametrické problémy v matematickém programování archivovány 9. července 2021 na Wayback Machine (pdf)
• Khokhlyuk VI Paralelní celočíselné optimalizační algoritmy. Archivováno 18. ledna 2021 napřednáškách Wayback Machine Course. Novosibirsk , 2007.
• Khokhlyuk V. I. Diskrétní optimalizační metody. Archivováno 18. ledna 2021 na Wayback Machine NSU, ​​2013. 154 s.

Odkazy

• Polyak B.P. Historie matematického programování v SSSR: analýza fenoménu  // Sborník ze 14. semináře Bajkalské školy „Optimalizační metody a jejich aplikace“. - 2008. - T. 1 . - S. 2-20 .

Slovníky a encyklopedie	Velká dánština Velký Rus Britannica (online)
V bibliografických katalozích	BNF : 11932649z GND : 4043664-0 J9U : 987007538691105171 LCCN : sh85107312 NKC : ph122672