Optimointi (matematiikka)

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 25.9.2021 tarkistetusta versiosta . tarkastukset vaativat 4 muokkausta .

Optimointi ( matematiikassa , tietojenkäsittelytieteessä ja operaatiotutkimuksessa ) on tehtävä löytää objektiivifunktion ääriarvo (minimi tai maksimi) äärellisulotteisen vektoriavaruuden jollakin alueella , jota rajoittaa joukko lineaarisia ja/tai ei- lineaariset yhtäläisyydet ja/tai epäyhtälöt .

Teoriaa ja menetelmiä optimointitehtävän ratkaisemiseksi tutkitaan matemaattisen ohjelmoinnin avulla .

Matemaattinen ohjelmointi on matematiikan haara, joka kehittää teoriaa, numeerisia menetelmiä moniulotteisten ongelmien ratkaisemiseen rajoituksin. [yksi]

Optimointiongelman lausunto

Suunnitteluprosessissa tehtävänä on yleensä määrittää kohteen parametrien paras tietyssä mielessä rakenne tai arvot. Tällaista ongelmaa kutsutaan optimointiongelmaksi. Jos optimointi liittyy optimaalisten parametriarvojen laskemiseen tietylle objektirakenteelle, sitä kutsutaan parametrioptimoinniksi . Optimaalisen rakenteen valinnan ongelmana on rakenteiden optimointi .

Standardi matemaattinen optimointitehtävä on muotoiltu tällä tavalla. Etsi joukot X muodostavien alkioiden χ joukosta alkio χ * , joka antaa annetun funktion f(χ) minimiarvon f(χ * ). Optimointiongelman esittämiseksi oikein on tarpeen asettaa:

Hyväksytty joukko on sarja ; ${\mathbb {X}}=\{{\vec {x}}|\;g_{i}({\vec {x}})\leq 0,\;i=1,\ldots ,m\}\ osajoukko {\mathbb {R}}^{n}$
Objektiivifunktio - kartoitus ; $f:\;{\mathbb {X}}\to {\mathbb {R}}$
Hakuehto (max tai min).

Sitten ongelman ratkaiseminen tarkoittaa jotakin seuraavista: $f(x)\to \min _{({\vec {x}}\in {\mathrm {X}}}}$

Näytä se . ${\mathbb {X}}=\varnothing$
Osoita, että tavoitefunktio ei ole rajoitettu alla. $f({\vec {x)))$
Etsi . ${\vec {x}}^{*}\in {\mathbb {X}}:\;f({\vec {x}}^{*})=\min _{({\vec {x}} \in {\mathbb {X}}}}f({\vec {x}})$
Jos , niin etsi . $\n olemassa {\vec {x}}^{*}$ $\inf _{({\vec {x}}\in {\mathbb {X}}}}f({\vec {x}})$

Jos minimoitava funktio ei ole kupera , niin he usein rajoittuvat paikallisten minimien ja maksimien löytämiseen: pisteitä sellaisiin, että kaikkialla joissain lähiöissään minimiin ja maksimiin. $x_{0}$ $f(x)\geq f(x_{0})$ $f(x)\leq f(x_{0})$

Jos joukko on sallittu , niin tällaista ongelmaa kutsutaan ehdottomaksi optimointitehtäväksi , muuten ehdollisen optimointiongelmaksi . ${\mathbb {X}}={\mathbb {R}}^{n}$

Optimointimenetelmien luokittelu

Optimointiongelmien yleinen merkintätapa määrittelee laajan valikoiman niiden luokkia. Menetelmän valinta (sen ratkaisun tehokkuus) riippuu ongelman luokasta. Tehtävien luokittelun määräävät: tavoitefunktio ja sallittu alue (epäyhtälö- ja yhtäläisyysjärjestelmällä tai monimutkaisemmalla algoritmilla). [2]

Optimointimenetelmät luokitellaan optimointitehtävien mukaan:

Paikalliset menetelmät: suppenevat johonkin tavoitefunktion paikalliseen ääripäähän. Unimodaalisen tavoitefunktion tapauksessa tämä ääriarvo on ainutlaatuinen ja se on globaali maksimi/minimi.
Globaalit menetelmät: käsittele multi-extremaalisia tavoitefunktioita. Globaalissa haussa päätehtävänä on tunnistaa tavoitefunktion globaalin käyttäytymisen trendit.

Tällä hetkellä olemassa olevat hakutavat voidaan jakaa kolmeen suureen ryhmään:

deterministinen;
satunnainen (stokastinen);
yhdistetty.

Toteutettavan joukon ulottuvuuden kriteerin mukaan optimointimenetelmät jaetaan yksiulotteisiin optimointimenetelmiin ja moniulotteisiin optimointimenetelmiin .

Tavoitefunktion ja hyväksyttävän joukon muodon mukaan optimointiongelmat ja menetelmät niiden ratkaisemiseksi voidaan jakaa seuraaviin luokkiin:

Optimointiongelmat, joissa tavoitefunktio ja rajoitteet ovat lineaarisia funktioita, ratkaistaan ns. lineaarisilla ohjelmointimenetelmillä . $f({\vec {x)))$ $g_{i}({\vec {x))),\;i=1,\ldots ,m$
Muussa tapauksessa käsitellään epälineaarista ohjelmointiongelmaa ja sovelletaan asianmukaisia menetelmiä. Niistä puolestaan erotetaan kaksi erityistehtävää:
- jos ja ovat konveksia funktioita, niin tällaista ongelmaa kutsutaan konveksiksi ohjelmointitehtäväksi ; $f({\vec {x)))$ $g_{i}({\vec {x))),\;i=1,\ldots ,m$
- jos , niin kyseessä on kokonaisluku (diskreetti) ohjelmointiongelma . ${\mathbb {X}}\subset {\mathbb {Z}}$

Tasaisuuden ja tavoitefunktion osittaisten johdannaisten läsnäolon vaatimusten mukaan ne voidaan jakaa myös:

suorat menetelmät, jotka edellyttävät vain tavoitefunktion laskemista approksimaatiopisteissä;
ensimmäisen asteen menetelmät : vaativat funktion ensimmäisten osittaisten derivaattojen laskemista;
toisen asteen menetelmät: vaativat toisen osittaisen derivaatan eli tavoitefunktion Hessenin laskemisen.

Lisäksi optimointimenetelmät on jaettu seuraaviin ryhmiin:

analyyttiset menetelmät (esimerkiksi Lagrange-kertoimien menetelmä ja Karush - Kuhn - Tucker -ehdot );
numeeriset menetelmät ;
graafiset menetelmät .

Joukon X luonteesta riippuen matemaattiset ohjelmointiongelmat luokitellaan seuraavasti:

diskreetit ohjelmointiongelmat (tai kombinatorinen optimointi ) - jos X on äärellinen tai laskettava ;
kokonaislukuohjelmointiongelmat - jos X on kokonaislukujoukon osajoukko ;
epälineaariset ohjelmointiongelmat, jos rajoitteet tai tavoitefunktio sisältävät epälineaarisia funktioita ja X on äärellisulotteisen vektoriavaruuden osajoukko .
Jos kaikki rajoitteet ja tavoitefunktio sisältävät vain lineaarisia funktioita, tämä on lineaarinen ohjelmointiongelma.

Lisäksi matemaattisen ohjelmoinnin osa-alueita ovat parametrinen ohjelmointi , dynaaminen ohjelmointi ja stokastinen ohjelmointi .

Matemaattista ohjelmointia käytetään operaatiotutkimuksen optimointiongelmien ratkaisemisessa .

Ekstreemin löytämismenetelmä määräytyy täysin ongelman luokan mukaan. Mutta ennen kuin saat matemaattisen mallin, sinun on suoritettava 4 mallinnuksen vaihetta:

Optimointijärjestelmän rajojen määrittäminen
- Hylätään ne optimointiobjektin yhteydet ulkomaailmaan, jotka eivät voi suuresti vaikuttaa optimointitulokseen, tai tarkemmin sanottuna ne, joita ilman ratkaisu yksinkertaistuu
Ohjattujen muuttujien valinta
- "Jäädytämme" joidenkin muuttujien arvot (hallitsemattomat muuttujat). Muut saavat ottaa mitkä tahansa arvot hyväksyttävien päätösten alueelta (hallitut muuttujat)
Ohjattujen muuttujien rajoitusten määrittäminen
- … (yhtä- ja/tai eriarvoisuudet)
Numeerisen optimointiehdon valinta (esim. suoritusindikaattori )
- Luo tavoitefunktio

Historia

Lineaariset ohjelmointiongelmat olivat ensimmäisiä yksityiskohtaisesti tutkittuja ongelmia funktioiden ääripään löytämisessä rajoitteiden , kuten epäyhtälöiden , esiintyessä . Vuonna 1820 Fourier ja sitten vuonna 1947 George Dantzig ehdottivat menetelmää vierekkäisten pisteiden ohjaamiseksi numeroimiseksi kohdefunktion lisäämisen suuntaan - simpleksimenetelmää , josta tuli tärkein lineaarisen ohjelmoinnin ongelmien ratkaisemisessa.

Termin "ohjelmointi" esiintyminen tieteenalan nimessä selittyy sillä, että ensimmäiset tutkimukset ja lineaarisen optimointiongelmien ensimmäiset sovellukset olivat taloustieteen alalla, koska englanniksi sana "ohjelmointi" tarkoittaa suunnittelua , piirtämistä. laatia suunnitelmia tai ohjelmia. On aivan luonnollista, että terminologia heijastaa läheistä suhdetta, joka vallitsee ongelman matemaattisen muotoilun ja sen taloudellisen tulkinnan (optimaalisen taloudellisen ohjelman tutkimus) välillä. Termin " lineaarinen ohjelmointi " ehdotti J. Danzig vuonna 1949 tutkiakseen teoreettisia ja algoritmisia ongelmia, jotka liittyvät lineaaristen funktioiden optimointiin lineaaristen rajoitusten alaisina.

Siksi nimi "matemaattinen ohjelmointi" johtuu siitä, että ongelmien ratkaisemisen tavoitteena on valita optimaalinen toimintaohjelma.

Lineaarifunktion määrittelemän äärimmäisten ongelmien luokan tunnistaminen lineaaristen rajoitusten määrittämässä joukossa tulisi lukea 1930-luvulta. Yksi ensimmäisistä, jotka tutkivat lineaarisen ohjelmoinnin ongelmia yleisessä muodossa, olivat: John von Neumann , matemaatikko ja fyysikko, joka todisti matriisipelien päälauseen ja tutki nimeään kantavaa talousmallia, ja L. V. Kantorovich , Neuvostoliiton akateemikko, Nobel Palkinnon voittaja (1975), joka muotoili joukon lineaarisia ohjelmointiongelmia ja ehdotti vuonna 1939 menetelmää niiden ratkaisemiseksi ( menetelmä tekijöiden ratkaisemiseksi ), joka eroaa hieman simpleksimenetelmästä.

Vuonna 1931 unkarilainen matemaatikko B. Egervari harkitsi matemaattista muotoilua ja ratkaisi lineaarisen ohjelmointitehtävän, jota kutsutaan "valintatehtäväksi", ratkaisumenetelmää kutsuttiin " Unkarin menetelmäksi ".

L. V. Kantorovich ja M. K. Gavurin kehittivät vuonna 1949 potentiaalien menetelmän , jota käytetään kuljetusongelmien ratkaisemisessa . L. V. Kantorovichin, V. S. Nemchinovin , V. V. Novozhilovin , A. L. Lurien , A. Brudnon , A. G. Aganbegyanin , D. B. Yudinin , E. G. Golshteinin ja muiden matemaatikot ja taloustieteilijät kehittivät edelleen matemaatikot ja taloustieteilijät kehittävät edelleen sekä sen lineaaristen ohjelmointimenetelmien että epälineaaristen menetelmien teoriaa. erilaisten taloudellisten ongelmien tutkimiseen.

Monet ulkomaisten tutkijoiden teokset on omistettu lineaarisen ohjelmoinnin menetelmille. Vuonna 1941 F. L. Hitchcock asetti kuljetushaasteen . Lineaarisen ohjelmointiongelmien ratkaisemisen perusmenetelmä, simpleksimenetelmä , julkaisi vuonna 1949 J. Dantzig. Lineaarisen ja epälineaarisen ohjelmoinnin menetelmiä kehitettiin edelleen G. Kuhnin , A. Tuckerin , Gassin (Saul I. Gass), Charnesin (A. Charnes), Bealen (EM Beale) ja muiden teoksissa.

Samanaikaisesti lineaarisen ohjelmoinnin kehittämisen kanssa kiinnitettiin paljon huomiota epälineaariseen ohjelmointiongelmiin , joissa joko tavoitefunktio tai rajoitteet tai molemmat ovat epälineaarisia. Vuonna 1951 julkaistiin G. Kuhnin ja A. Tuckerin teos , jossa annettiin tarvittavat ja riittävät optimaalisuusehdot epälineaaristen ohjelmointiongelmien ratkaisemiseksi. Tämä työ muodosti perustan myöhemmälle tutkimukselle tällä alalla.

Vuodesta 1955 lähtien on julkaistu monia kvadraattiseen ohjelmointiin omistettuja teoksia (Bealin, Barankinin ja R. Dorfmanin , Frankin (M. Frank) ja F. Wolfin , G. Markowitzin teoksia jne.). Dennisin (JB Dennis), Rosenin (JB Rosen) ja Zontendijkin (G. Zontendijk) työt kehittivät gradienttimenetelmiä epälineaaristen ohjelmointiongelmien ratkaisemiseksi.

Tällä hetkellä matemaattisten ohjelmointimenetelmien tehokasta soveltamista ja ongelmien ratkaisemista varten tietokoneissa on kehitetty algebrallisia mallinnuskieliä , joiden edustajia ovat AMPL ja LINGO .

Katso myös

Muistiinpanot

↑ Lähde: Altai Regional Universal Scientific Library. V. Ya. Shishkova (AKUNB) Arkistoitu 5. maaliskuuta 2022 Wayback Machinessa . Optimointimenetelmät: Proc. korvaus. Brazovskaja N.V.; Altain osavaltion tekninen yliopisto I. I. Polzunova, [Etäisyyskeskus. koulutus].-Barnaul: Publishing House of AltSTU, 2000, 120 s. - UDC / LBC 22.183.4 B871
↑ Optimaalisen vaihtoehdon löytäminen: Tietokone laajentaa mahdollisuuksia . - M .: Nauka, 1989. - S. 14 . — ISBN 5-02-006737-7 .

Kirjallisuus

Abakarov A. Sh., Sushkov Yu. A. Tilastollinen tutkimus yhdestä globaalista optimointialgoritmista . - FORA:n julkaisut, 2004.
Akulich I. L. Matemaattinen ohjelmointi esimerkeissä ja tehtävissä: Proc. opiskelijatalouden tuki. asiantuntija. yliopistot. - M . : Korkeakoulu, 1986.
Gill F., Murray W., Wright M. Käytännön optimointi. Per. englannista. - M .: Mir, 1985.
Girsanov IV Luennot ääriongelmien matemaattisesta teoriasta. - M .; Izhevsk : Tutkimuskeskus "säännöllinen ja kaoottinen dynamiikka", 2003. - 118 s. — ISBN 5-93972-272-5 .
Zhiglyavsky A. A., Zhilinkas A. G. Menetelmät globaalin ääripään etsimiseen. - M .: Nauka, Fizmatlit , 1991.
Karmanov VG Matemaattinen ohjelmointi. - Publishing House of Phys.-Math. Kirjallisuus, 2004.
Korn G., Korn T. Matematiikan käsikirja tutkijoille ja insinööreille. - M .: Nauka, 1970. - S. 575-576.
Korshunov Yu. M., Korshunov Yu. M. Kybernetiikan matemaattiset perusteet. - M .: Energoatomizdat , 1972.
Lotov A. V. , Pospelova I. I. Luentomuistiinpanot monikriteerien optimoinnin teoriasta ja menetelmistä. Arkistoitu 21. tammikuuta 2022 Wayback Machinessa ratkaisu M., 2005. 127 s.
Maksimov Yu. A., Filippovskaya EA Algoritmit epälineaaristen ohjelmointiongelmien ratkaisemiseen. - M .: MEPhI, 1982.
Maksimov Yu. A. Lineaariset ja diskreetit ohjelmointialgoritmit. - M .: MEPhI, 1980.
Plotnikov A.D. Matemaattinen ohjelmointi = pikakurssi. - 2006. - S. 171. - ISBN 985-475-186-4 .
Rastrigin L. A. Tilastolliset hakumenetelmät. - M. , 1968.
Sergeev Ya. D., Kvasov D. E. Diagonaaliset globaalin optimoinnin menetelmät Arkistoitu 26. lokakuuta 2017 Wayback Machinessa . — M.: FIZMATLIT, 2008. 341s.
Hemdy A. Taha. Johdatus operaatiotutkimukseen = Operations Research: An Introduction. - 8. painos - M .: Williams , 2007. - S. 912. - ISBN 0-13-032374-8 .
Kini RL, Raifa H. Päätöksenteko useilla kriteereillä: mieltymykset ja korvaukset. - M . : Radio ja viestintä, 1981. - 560 s.
Zukhovitsky S. I. , Avdeeva L. I. Lineaarinen ja kupera ohjelmointi. - 2. painos, tarkistettu. ja muita .. - M . : Kustantaja "Nauka", 1967.
Minaev Yu. N. Taloudellisten ja matemaattisten optimointimallien vakaus. - M . : Tilastot, 1980.
Moiseev NN Numeeriset menetelmät optimaalisten järjestelmien teoriassa . - M .: Nauka, 1971. - 424 s.
Moiseev NN Optimaalisten järjestelmien teorian elementit . - M .: Nauka, 1975. - 528 s.
Moiseev NN , Ivanilov Yu.P. , Stolyarova EM Optimointimenetelmät . - M .: Nauka, 1978. - 352 s.

Degtyarev Yu. I. Optimointimenetelmät. - M . : Neuvostoliiton radio, 1980. - 272 s.
Rekleitis G., Reyvindran A., Ragsdel K. Optimointi suunnittelussa. - M . : Mir, 1986. - 400 s.
Romanovsky IV Algoritmit äärimmäisten ongelmien ratkaisemiseen. - M .: Nauka, 1977. - 352 s. - 16 000 kappaletta.
Umnov A.E. , Umnov E.A. Matemaattisen ohjelmoinnin parametriset ongelmat arkistoitu 9. heinäkuuta 2021 Wayback Machinessa (pdf)
Khokhlyuk VI Rinnakkaislukujen optimointialgoritmit. Arkistoitu 18. tammikuuta 2021 Wayback Machine Course -luennoilla. Novosibirsk , 2007.
Khokhlyuk V. I. Diskreetit optimointimenetelmät. Arkistoitu 18. tammikuuta 2021 Wayback Machinessa NSU, 2013. 154 s.

Linkit

Polyak B.P. Matemaattisen ohjelmoinnin historia Neuvostoliitossa: ilmiön analyysi // 14. Baikal-kouluseminaarin "Optimointimenetelmät ja niiden sovellukset" julkaisut. - 2008. - T. 1 . - S. 2-20 .

Sanakirjat ja tietosanakirjat	Suuri tanskalainen Iso venäläinen Britannica (verkossa)
Bibliografisissa luetteloissa	BNF : 11932649z GND : 4043664-0 J9U : 987007538691105171 LCCN : sh85107312 NKC : ph122672

Optimointimenetelmät _
Yksiulotteinen	kultaisen leikkauksen menetelmä Dikotomia Paraabeli menetelmä Verkkohaku Yhtenäinen lohkohakumenetelmä Fibonaccin menetelmä Kolminkertainen haku Piyavsky menetelmä Vahva menetelmä
Nolla järjestys	Gaussin menetelmä Nelder-Meadin menetelmä Hook-Jeeves -menetelmä Rosenbrockin menetelmä Powellin menetelmä
Ensimmäinen tilaus	gradienttilasku Zeutendijkin menetelmä Koordinaattilasku Konjugaattigradienttimenetelmä Kvasi-Newtonilaiset menetelmät Levenberg-Marquardt-algoritmi
toinen tilaus	Newtonin menetelmä Newton-Raphsonin menetelmä Broyden-Fletcher-Goldfarb-Shanno-algoritmi (BFGS)
Stokastinen	Monte Carlon menetelmä Simuloitu hehkutus Evoluutioalgoritmit differentiaalinen evoluutio Ant algoritmi Hiukkasparvimenetelmä Mehiläisyhdyskunnan algoritmi Satunnainen kävelymenetelmä
Lineaariset ohjelmointimenetelmät _	Yksinkertainen menetelmä Gomorin algoritmi Ellipsoidi menetelmä Potentiaalinen menetelmä
Epälineaariset ohjelmointimenetelmät	Jaksottainen neliöllinen ohjelmointi

taloustiede
Talousteoria Poliittinen talous Soveltava taloustiede
Metodologia	Talousmallit Talousjärjestelmät matemaattinen taloustiede Ekonometria Kokeellinen taloustiede Laskennallinen taloustiede Makrotalouden mikroperustat
Mikrotaloustiede	budjetti asetettu Palkka välinpitämättömyyskäyrä Intertemporaalinen valinta Epävarmuus Riskien välttäminen Tuottoprosentti julkishyödykkeet Apuohjelma Odotettu Rajoittava Kulutusteoria Voitto Prosentti Tasapaino Kenraali Jakelu Säännöstely Resurssien harvinaisuus Vuokrata Markkinoida Tarjonta ja kysyntä Hinta Markkinoiden rakenne Kilpailu monopoli Täydellinen Monopoli kaksipuolinen Monopsonia Oligopoli Oligopsony Hyödykevaje Markkinafiasko Yrityksen teoria Hinta ulkoista Elastisuus tulovaikutus korvausvaikutus mittakaavaefekti Pareto-tehokkuus Kustannukset Vaihtoehtoinen Implisiittinen Ei palauteta Julkinen Raja Keskikokoinen Transaktio Kustannus-hyötyanalyysi ylijäämä Sosiaalinen valinta
Makrotaloustiede	Työttömyys Valuutta Raha Kysyntä Tuomita Päästö Raha-luottopolitiikka Deflaatio Inflaatio Hyperinflaatio Keynesiläinen risti Phillipsin käyrä Kriisi Suuri lama Malli AD-AS Malli IS-LM Nimelliskovuus Keynesin " Yleinen teoria ". odotuksia Mukautuva Rationaalista Ostovoimapariteetti Maksusaldo Korko Lama kasvuteoria Tallentaa Kansantalouden tilinpitojärjestelmä Kokonaiskysyntä Stagflaatio veropolitiikka keskuspankki Kierrosteoria Kutistuminen Tehokas kysyntä DSGE NAIRU Mallit Kansantulon ja tuotannon mittaaminen Sijoitukset Hintataso _ Supply shokki Kysyntäshokki
matemaattinen taloustiede	Toimintatutkimus Ekonometria Päätösteoria Peliteoria Mekanismin suunnittelu Input-output malli talousmatematiikka
Soveltava taloustiede	Hyvinvointi Talousmaantiede kaupungit Talousdemografia rahan teoria tietoa koulutus Terveys Taloushistoria Kansainvälinen ja maailma julkinen valinta Ympäristö ekologinen taloustiede Toimialan organisaatio Talouspolitiikka Kehitys Alueellinen Uskonnot Perheet sosioekonomiikka taloussosiologia Työvoimaa julkisen sektorin taloudellinen suunnittelu Lain taloudellinen analyysi Luonnonvarat Maatalous (englanniksi) Taloustilastot Talous
Taloudellisen ajattelun koulut ( historia ) .	Muinaisen idän taloudellinen ajatus Antiikin taloudellinen ajatus itävaltalainen Bloomington buddhalainen Harvard Georgiaisuus institutionalismia historiallinen Katedri-sosialismi Keynesiläisyys Uuskeynesiläisyys ( uusklassis- keynesilainen synteesi ) Postkeynesiläisyys Rahakierron teoria Uusi klassista perustuslaillinen Malthusianismi Manchester marginalismia marxilainen Uusmarxilainen _ Taloudellinen valtavirta Merkantilismi maailmanjärjestelmäteoria Monetarismi uusklassinen Lausanne epätavallinen Uusi instituutio Uusi klassikko Todellinen liiketoimintasykliteoria käyttäytymiseen Tarjontapuolen taloustiede Salamanca Tukholma Fysiokratia Chartalismi Nykyaikainen rahateoria Chicago evoluutionaalinen Ekologinen Keskiajan taloudellinen ajatus Anarkisti Mutualismi Ei-tasapaino sosialisti Lämpötalous Feministi
Katso myös	Mesoekonomiikka Taloudellisen kirjallisuuden luokitus JEL Tärkeimmät taloustieteen julkaisut