Optimizare (matematică)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 25 septembrie 2021; verificările necesită 4 modificări .

Optimizarea (în matematică , informatică și cercetare operațională ) este sarcina de a găsi un extremum (minim sau maxim) al unei funcții obiectiv într-o regiune a unui spațiu vectorial cu dimensiuni finite , limitată de un set de linii liniare și/sau non- egalități și/sau inegalități liniare .

Teoria și metodele de rezolvare a unei probleme de optimizare sunt studiate prin programare matematică .

Programarea matematică este o ramură a matematicii care dezvoltă teoria, metode numerice pentru rezolvarea problemelor multidimensionale cu constrângeri. [unu]

Enunțul problemei de optimizare

În procesul de proiectare , sarcina este de obicei stabilită pentru a determina cele mai bune, într-un sens, structura sau valorile parametrilor obiectului . O astfel de problemă se numește problemă de optimizare. Dacă optimizarea este asociată cu calcularea valorilor optime ale parametrilor pentru o anumită structură a obiectului, atunci se numește optimizare parametrică . Problema alegerii structurii optime este optimizarea structurală .

Problema standard de optimizare matematică este formulată în acest fel. Dintre elementele χ care formează mulțimile X, găsiți un element χ * care furnizează valoarea minimă f(χ * ) a funcției date f(χ). Pentru a pune corect problema de optimizare, este necesar să setați:

Setul admis este setul ; ${\mathbb {X}}=\{{\vec {x}}|\;g_{i}({\vec {x}})\leq 0,\;i=1,\ldots ,m\}\ submult {\mathbb {R}}^{n}$
Funcția obiectivă - cartografiere ; $f:\;{\mathbb {X}}\la {\mathbb {R}}$
Criteriul de căutare (max sau min).

Atunci rezolvarea problemei înseamnă una dintre: $f(x)\la \min _{({\vec {x}}\in {\mathrm {X}}}}$

Arată că . ${\mathbb {X}}=\varnimic$
Arătați că funcția obiectiv nu este mărginită mai jos. $f({\vec {x)))$
Găsiți . ${\vec {x}}^{*}\in {\mathbb {X}}:\;f({\vec {x}}^{*})=\min _{({\vec {x}} \in {\mathbb {X}}}}f({\vec {x}})$
Dacă , atunci găsiți . $\nexistă {\vec {x}}^{*}$ $\inf _{({\vec {x}}\in {\mathbb {X}}}}f({\vec {x}})$

Dacă funcția minimizată nu este convexă , atunci ei se limitează adesea la a găsi minime și maxime locale: puncte astfel încât peste tot în unele dintre cartierele lor pentru un minim și pentru un maxim. $x_{0}$ $f(x)\geq f(x_{0})$ $f(x)\leq f(x_{0})$

Dacă mulțimea este admisibilă , atunci o astfel de problemă se numește o problemă de optimizare necondiționată , în caz contrar, o problemă de optimizare condiționată . ${\mathbb {X}}={\mathbb {R}}^{n}$

Clasificarea metodelor de optimizare

Notarea generală a problemelor de optimizare definește o mare varietate de clase ale acestora. Alegerea metodei (eficiența soluției sale) depinde de clasa problemei. Clasificarea problemelor este determinată de: funcția obiectiv și aria admisibilă (dată de un sistem de inegalități și egalități sau un algoritm mai complex). [2]

Metodele de optimizare sunt clasificate în funcție de sarcinile de optimizare:

Metode locale: converg către un extremum local al funcției obiectiv. În cazul unei funcții obiectiv unimodale, acest extremum este unic și va fi maximul/minimul global.
Metode globale: se ocupă de funcții obiective multi-extreme. În căutarea globală, sarcina principală este identificarea tendințelor în comportamentul global al funcției obiective.

Metodele de căutare existente în prezent pot fi împărțite în trei grupuri mari:

determinat;
aleatoriu (stochastic);
combinate.

În funcție de criteriul dimensiunii mulțimii fezabile, metodele de optimizare sunt împărțite în metode de optimizare unidimensională și metode de optimizare multidimensională .

După forma funcției obiectiv și a mulțimii admisibile, problemele de optimizare și metodele de rezolvare a acestora pot fi împărțite în următoarele clase:

Problemele de optimizare în care funcția obiectiv și constrângerile sunt funcții liniare sunt rezolvate prin așa-numitele metode de programare liniară . $f({\vec {x)))$ $g_{i}({\vec {x))),\;i=1,\ldots ,m$
În caz contrar, se tratează o problemă de programare neliniară și se aplică metodele adecvate. La rândul lor, două sarcini particulare se disting de acestea:
- dacă și sunt funcții convexe, atunci o astfel de problemă se numește problemă de programare convexă ; $f({\vec {x)))$ $g_{i}({\vec {x))),\;i=1,\ldots ,m$
- dacă , atunci avem de-a face cu o problemă de programare cu numere întregi (discrete) . ${\mathbb {X}}\subset {\mathbb {Z}}$

În conformitate cu cerințele pentru netezime și prezența derivatelor parțiale în funcția obiectiv, acestea pot fi, de asemenea, împărțite în:

metode directe care necesită doar calculul funcției obiectiv la puncte de aproximare;
metode de ordinul întâi : necesită calculul primelor derivate parțiale ale unei funcții;
metode de ordinul doi: necesită calculul derivatelor parțiale secunde, adică Hessianul funcției obiectiv.

În plus, metodele de optimizare sunt împărțite în următoarele grupuri:

metode analitice (de exemplu, metoda multiplicatorilor Lagrange și condițiile Karush - Kuhn - Tucker );
metode numerice ;
metode grafice .

În funcție de natura mulțimii X , problemele de programare matematică sunt clasificate astfel:

probleme de programare discretă (sau optimizare combinatorie ) - dacă X este finit sau numărabil ;
probleme de programare cu numere întregi - dacă X este o submulțime a mulțimii de numere întregi;
probleme de programare neliniară dacă constrângerile sau funcția obiectiv conțin funcții neliniare și X este o submulțime a unui spațiu vectorial cu dimensiuni finite .
Dacă toate constrângerile și funcția obiectiv conțin numai funcții liniare, atunci aceasta este o problemă de programare liniară.

În plus, ramurile programării matematice sunt programarea parametrică , programarea dinamică și programarea stocastică .

Programarea matematică este utilizată în rezolvarea problemelor de optimizare în cercetarea operațională .

Metoda de găsire a extremului este complet determinată de clasa problemei. Dar înainte de a obține un model matematic, trebuie să efectuați 4 etape de modelare:

Determinarea limitelor sistemului de optimizare
- Renunțăm la acele conexiuni ale obiectului de optimizare cu lumea exterioară care nu pot afecta foarte mult rezultatul optimizării sau, mai exact, cele fără de care soluția este simplificată
Alegerea variabilelor controlate
- „Înghețăm” valorile unor variabile (variabile negestionate). Alții sunt lăsați să ia orice valori din zona deciziilor admisibile (variabile controlate)
Definirea constrângerilor asupra variabilelor controlate
- … (egalități și/sau inegalități)
Alegerea criteriului de optimizare numerică (de exemplu , indicator de performanță )
- Creați o funcție obiectivă

Istorie

Problemele de programare liniară au fost primele studiate în detaliu probleme de găsire a extremului de funcții în prezența unor constrângeri precum inegalitățile . În 1820, Fourier și apoi în 1947 George Dantzig au propus o metodă de enumerare direcționată a vârfurilor adiacente în direcția creșterii funcției obiectiv - metoda simplex , care a devenit principala în rezolvarea problemelor de programare liniară.

Prezența termenului „programare” în denumirea disciplinei se explică prin faptul că primele studii și primele aplicații ale problemelor de optimizare liniară au fost în domeniul economiei, întrucât în engleză cuvântul „programare” înseamnă planificare , desen. planuri sau programe. Este destul de firesc ca terminologia să reflecte relația strânsă care există între formularea matematică a problemei și interpretarea ei economică (studiul programului economic optim). Termenul de „ programare liniară ” a fost propus de J. Danzig în 1949 pentru a studia problemele teoretice și algoritmice legate de optimizarea funcțiilor liniare sub constrângeri liniare.

Prin urmare, denumirea de „programare matematică” se datorează faptului că scopul rezolvării problemelor este alegerea programului optim de acțiuni.

Identificarea unei clase de probleme extreme definite de o funcțională liniară pe o mulțime definită de constrângeri liniare ar trebui să fie atribuită anilor 1930. Unul dintre primii care a studiat problemele de programare liniară într-o formă generală au fost: John von Neumann , un matematician și fizician care a demonstrat teorema principală a jocurilor matrice și a studiat modelul economic care îi poartă numele, și L. V. Kantorovich , un academician sovietic, Nobel Nobel . Câștigător al premiului (1975), care a formulat o serie de probleme de programare liniară și a propus în 1939 o metodă de rezolvare a acestora ( metoda de rezolvare a factorilor ), care diferă ușor de metoda simplex.

În 1931, matematicianul maghiar B. Egervari a luat în considerare o formulare matematică și a rezolvat o problemă de programare liniară numită „problema alegerii”, metoda soluției fiind numită „ metoda maghiară ”.

L. V. Kantorovich și M. K. Gavurin au dezvoltat metoda potențialelor în 1949 , care este folosită în rezolvarea problemelor de transport . În lucrările ulterioare ale lui L. V. Kantorovich, V. S. Nemchinov , V. V. Novozhilov , A. L. Lurie , A. Brudno , A. G. Aganbegyan , D. B. Yudin , E. G. Golshtein și alți matematicieni și economiști și-au dezvoltat în continuare atât metoda matematică, cât și aplicarea tematică neliniară a matematicii liniare. la studiul diferitelor probleme economice.

Multe lucrări ale oamenilor de știință străini sunt dedicate metodelor de programare liniară. În 1941, F. L. Hitchcock a stabilit provocarea transportului . Metoda de bază pentru rezolvarea problemelor de programare liniară, metoda simplex , a fost publicată în 1949 de J. Dantzig. Metodele de programare liniară și neliniară au fost dezvoltate în continuare în lucrările lui G. Kuhn , A. Tucker , Gass (Saul I. Gass), Charnes (A. Charnes), Beale (EM Beale) și alții.

Concomitent cu dezvoltarea programării liniare, s-a acordat multă atenție problemelor de programare neliniară , în care fie funcția obiectiv , fie constrângerile, fie ambele sunt neliniare. În 1951, a fost publicată lucrarea lui G. Kuhn și A. Tucker , în care au fost date condiții de optimitate necesare și suficiente pentru rezolvarea problemelor de programare neliniară. Această lucrare a stat la baza cercetărilor ulterioare în acest domeniu.

Din 1955, au fost publicate multe lucrări dedicate programării pătratice (lucrări de Beal, Barankin și R. Dorfman , Frank (M. Frank) și F. Wolf , G. Markowitz , etc.). Lucrările lui Dennis (JB Dennis), Rosen (JB Rosen) și Zontendijk (G. Zontendijk) au dezvoltat metode de gradient pentru rezolvarea problemelor de programare neliniară.

În prezent, pentru aplicarea eficientă a metodelor de programare matematică și rezolvarea problemelor pe computere, au fost dezvoltate limbaje de modelare algebrică , reprezentanți ai cărora sunt AMPL și LINGO .

Vezi și

Note

↑ Sursa: Biblioteca Științifică Universală Regională Altai. V. Ya. Shishkova (AKUNB) Arhivat pe 5 martie 2022 la Wayback Machine . Metode de optimizare: Proc. indemnizatie. Brazovskaya N.V.; Universitatea Tehnică de Stat din Altai I. I. Polzunova, [Centrul distanței. instruire].-Barnaul: Editura AltSTU, 2000, 120 p. - UDC / LBC 22.183.4 B871
↑ Găsirea optimului: computerul extinde posibilitățile . - M . : Nauka, 1989. - S. 14 . — ISBN 5-02-006737-7 .

Literatură

Abakarov A. Sh., Sushkov Yu. A. Studiu statistic al unui algoritm global de optimizare . - Proceedings of FORA, 2004.
Akulich I. L. Programare matematică în exemple și sarcini: Proc. indemnizație pentru economia studenților. specialist. universități. - M . : Liceu, 1986.
Gill F., Murray W., Wright M. Optimizare practică. Pe. din engleza. — M .: Mir, 1985.
Girsanov IV Prelegeri despre teoria matematică a problemelor extreme. - M .; Izhevsk : Centrul de cercetare „Dinamica regulată și haotică”, 2003. - 118 p. — ISBN 5-93972-272-5 .
Zhiglyavsky A. A., Zhilinkas A. G. Metode de căutare a unui extremum global. — M .: Nauka, Fizmatlit , 1991.
Karmanov VG Programare matematică. - Editura Fiz.-Math. Literatură, 2004.
Korn G., Korn T. Manual de matematică pentru oameni de știință și ingineri. - M . : Nauka, 1970. - S. 575-576.
Korshunov Yu. M., Korshunov Yu. M. Fundamentele matematice ale ciberneticii. — M .: Energoatomizdat , 1972.
Lotov A. V. , Pospelova I. I. Note de curs despre teoria și metodele optimizării multicriteriale. Arhivat pe 21 ianuarie 2022 la Wayback Machine aşezare M., 2005. 127 p.
Maksimov Yu. A., Filippovskaya EA Algoritmi pentru rezolvarea problemelor de programare neliniară. — M .: MEPhI, 1982.
Maksimov Yu. A. Algoritmi de programare liniară și discretă. — M .: MEPhI, 1980.
Plotnikov A.D. Programare matematică = curs expres. - 2006. - S. 171. - ISBN 985-475-186-4 .
Rastrigin L. A. Metode statistice de căutare. - M. , 1968.
Sergeev Ya. D., Kvasov D. E. Metode diagonale de optimizare globală Arhivat 26 octombrie 2017 la Wayback Machine . — M.: FIZMATLIT, 2008. 341s.
Hemdy A. Taha. Introduction to Operations Research = Operations Research: An Introduction. - Ed. a 8-a. - M .: Williams , 2007. - S. 912. - ISBN 0-13-032374-8 .
Kini RL, Raifa H. Luarea deciziilor pe criterii multiple: preferințe și substituții. - M . : Radio şi comunicare, 1981. - 560 p.
Zukhovitsky S. I. , Avdeeva L. I. Programare liniară și convexă. - Ed. a II-a, revizuită. și suplimentar .. - M . : Editura „Nauka”, 1967.
Minaev Yu. N. Stabilitatea modelelor de optimizare economică și matematică. - M .: Statistică, 1980.
Moiseev NN Metode numerice în teoria sistemelor optime . - M. : Nauka, 1971. - 424 p.
Moiseev NN Elemente ale teoriei sistemelor optime . — M .: Nauka, 1975. — 528 p.
Moiseev NN , Ivanilov Yu. P. , Stolyarova EM Optimization methods . - M. : Nauka, 1978. - 352 p.

Degtyarev Yu. I. Metode de optimizare. - M . : Radio sovietică, 1980. - 272 p.
Rekleitis G., Reyvindran A., Ragsdel K. Optimization in engineering. - M . : Mir, 1986. - 400 p.
Romanovsky IV Algoritmi pentru rezolvarea problemelor extreme. — M .: Nauka, 1977. — 352 p. - 16.000 de exemplare.
Umnov A.E. , Umnov E.A. Probleme parametrice în programarea matematică Arhivat 9 iulie 2021 la Wayback Machine (pdf)
Khokhlyuk VI Algoritmi de optimizare a numărului întreg paralel. Arhivat 18 ianuarie 2021 la cursul Wayback Machine de prelegeri. Novosibirsk , 2007.
Khokhlyuk V. I. Metode discrete de optimizare. Arhivat pe 18 ianuarie 2021 la Wayback Machine NSU, 2013. 154 p.

Link -uri

Polyak B.P. Istoria programării matematice în URSS: analiza fenomenului // Lucrările celui de-al XIV-lea seminar-școală Baikal „Metode de optimizare și aplicații ale acestora”. - 2008. - T. 1 . - S. 2-20 .

Dicționare și enciclopedii	mare danez Rusă mare Britannica (online)
În cataloagele bibliografice	BNF : 11932649z GND : 4043664-0 J9U : 987007538691105171 LCCN : sh85107312 NKC : ph122672

Metode de optimizare
Unidimensional	metoda secțiunii de aur Dihotomie Metoda parabolelor Căutare în grilă Metoda de căutare uniformă a blocurilor Metoda Fibonacci Căutare ternară metoda Piyavsky Metoda Strongin
Comanda zero	metoda Gauss Metoda Nelder-Mead Metoda Hook-Jeeves metoda Rosenbrock metoda Powell
Prima comanda	coborâre în gradient Metoda Zeutendijk Coordonarea coborârii Metoda gradientului conjugat Metode cvasi-newtoniene Algoritmul Levenberg-Marquardt
a doua comanda	metoda lui Newton Metoda Newton-Raphson Algoritmul Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastic	Metoda Monte Carlo Recoacere simulată Algoritmi evolutivi evolutie diferentiala Algoritmul furnicilor Metoda roiului de particule Algoritmul coloniilor de albine Metoda de mers aleatoriu
Metode de programare liniară	Metoda simplex algoritmul lui Gomori Metoda elipsoidă Metoda potențială
Metode de programare neliniară	Programare secvenţială pătratică

stiinta economica
Teoria economică Economie politică Economie aplicată
Metodologie	Modele economice Sisteme economice economie matematică Econometrie Economia experimentală Computational Economics Microfundamente ale macroeconomiei
Microeconomie	buget stabilit Salariu curba de indiferență Alegerea intertemporale Incertitudine Aversiunii față de risc Rata de rentabilitate bunuri publice Utilitate Așteptat Limitare Teoria consumului Profit La sută Echilibru General Distributie Raționalizarea Raritatea resurselor Chirie Piaţă Cerere și ofertă Preț Structura pieței Competiție monopol Perfect Monopol cu două fețe Monopson Oligopol Oligopsoniul Deficitul de mărfuri Fiasco pe piață Teoria firmei Preț externalia Elasticitate efectul de venit efect de substitutie efect de scară Eficiența Pareto Cheltuieli Alternativă Implicit Nerambursabile Public Limită Mediu Tranzacțional Analiza cost-beneficiu surplus Alegere socială
Macroeconomie	Şomaj Valută Bani Cerere Propoziție Emisia Politica bani-credit Deflaţie Inflația Hiperinflația cruce keynesiană curba Phillips O criză Marea Depresiune Model AD-AS Model IS-LM Duritate nominală „ Teoria generală ” de Keynes așteptări Adaptiv Raţional Paritatea puterii de cumpărare Sold de plată Rata dobânzii Recesiune teoria cresterii Economisire Sistemul de Conturi Nationale Cererea agregată Stagflația politica fiscala Banca centrala Teoria ciclului Contracție Cerere efectivă DSGE NAIRU Modele Măsurarea venitului și producției naționale Investiții Nivelul prețului Soc de aprovizionare Socul cererii
economie matematică	Cercetare operațională Econometrie Teoria deciziei Teoria jocului Proiectarea mecanismului Modelul de intrare-ieșire matematica financiara
Economie aplicată	Bunăstare Geografie economică Orase Demografie economică teoria banilor Cunoştinţe educaţie Sănătate Istoria economică Internațional și mondial alegere publică Mediu inconjurator economie ecologică Organizarea industriei Politică economică Dezvoltare Regional Religiile Familiile socioeconomic sociologie economică Muncă sector public planificarea economică Analiza economică a dreptului Resurse naturale Agricultura (engleză) Statistici economice financiar
Școli ( istorie ) de gândire economică	Gândirea economică a Orientului Antic Gândirea economică a Antichității austriac Bloomington budist Harvard Georgiaismul instituţionalism istoric Cateder-socialism keynesianismul Neo- keynesianism ( sinteză neoclasic-keynesiană ) Post-keynesianismul Teoria circulației monetare Nou clasic constituţional malthusianism Manchester marginalism marxist neo- marxist Mainstream economic Mercantilism teoria sistemelor lumii Monetarismul neoclasic Lausanne neortodox Nou instituțional Nou clasic Teoria reală a ciclului de afaceri comportamental Economia pe partea ofertei Salamanca Stockholm Fiziocrația Chartalism Teoria monetară modernă Chicago evolutiv Ecologic Gândirea economică a Evului Mediu Anarhist Mutualismul non-echilibru Socialist Termoeconomie Feminist
Vezi si	Mezoeconomie Clasificarea literaturii economice JEL Cele mai importante publicații din domeniul economiei