Optimering (matematik)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 25 september 2021; kontroller kräver 4 redigeringar .

Optimering (inom matematik , datavetenskap och operationsforskning ) är uppgiften att hitta ett extremum (minimum eller maximum) av en objektiv funktion i någon region av ett ändligt dimensionellt vektorrum , begränsat av en uppsättning linjära och/eller icke- linjära jämlikheter och/eller ojämlikheter .

Teorin och metoderna för att lösa ett optimeringsproblem studeras genom matematisk programmering .

Matematisk programmering är en gren av matematiken som utvecklar teori, numeriska metoder för att lösa flerdimensionella problem med begränsningar. [ett]

Uttalande av optimeringsproblemet

I designprocessen är uppgiften vanligtvis inställd på att bestämma den bästa, i viss mening, strukturen eller värdena för objektparametrar . Ett sådant problem kallas ett optimeringsproblem. Om optimering är associerad med beräkningen av optimala parametervärden för en given objektstruktur, kallas det parametrisk optimering . Problemet med att välja den optimala strukturen är strukturell optimering .

Det vanliga matematiska optimeringsproblemet är formulerat på detta sätt. Bland elementen χ som bildar mängderna X, hitta ett element χ * som ger minimivärdet f(χ * ) för den givna funktionen f(χ). För att korrekt posera optimeringsproblemet är det nödvändigt att ställa in:

Den tillåtna mängden är uppsättningen ; ${\mathbb {X}}=\{{\vec {x}}|\;g_{i}({\vec {x}})\leq 0,\;i=1,\ldots ,m\}\ delmängd {\mathbb {R}}^{n}$
Objektiv funktionsmapping ; $f:\;{\mathbb {X}}\to {\mathbb {R}}$
Sökkriterium (max eller min).

Lös sedan problemet innebär något av: $f(x)\till \min _{({\vec {x}}\in {\mathrm {X}}}}$

Visa det . ${\mathbb {X}}=\varnothing$
Visa att målfunktionen inte är begränsad nedan. $f({\vec {x)))$
Hitta . ${\vec {x}}^{*}\in {\mathbb {X}}:\;f({\vec {x}}^{*})=\min _{({\vec {x}} \in {\mathbb {X}}}}f({\vec {x}})$
Om , sedan hitta . $\nfinns {\vec {x}}^{*}$ $\inf _{({\vec {x}}\in {\mathbb {X}}}}f({\vec {x}})$

Om funktionen som minimeras inte är konvex , begränsar de sig ofta till att hitta lokala minima och maxima: punkter som överallt i vissa av deras grannskap för ett minimum och ett maximum. $x_{0}$ $f(x)\geq f(x_{0})$ $f(x)\leq f(x_{0})$

Om uppsättningen är tillåten kallas ett sådant problem ett ovillkorligt optimeringsproblem , annars ett villkorligt optimeringsproblem . ${\mathbb {X}}={\mathbb {R}}^{n}$

Klassificering av optimeringsmetoder

Den allmänna notationen av optimeringsproblem definierar en stor mängd olika klasser. Valet av metod (effektiviteten av dess lösning) beror på problemets klass. Klassificeringen av problem bestäms av: den objektiva funktionen och det tillåtna området (givet av ett system av ojämlikheter och jämlikheter eller en mer komplex algoritm). [2]

Optimeringsmetoder klassificeras enligt optimeringsuppgifter:

Lokala metoder: konvergera till något lokalt extremum av den objektiva funktionen. I fallet med en unimodal objektiv funktion är detta extremum unikt och kommer att vara det globala maximum/minimum.
Globala metoder: hantera multiextrema objektiva funktioner. I den globala sökningen är huvuduppgiften att identifiera trender i den objektiva funktionens globala beteende.

För närvarande befintliga sökmetoder kan delas in i tre stora grupper:

deterministisk;
slumpmässig (stokastisk);
kombinerad.

Enligt kriteriet för dimensionen av den genomförbara uppsättningen delas optimeringsmetoder in i endimensionella optimeringsmetoder och flerdimensionella optimeringsmetoder .

Genom formen av den objektiva funktionen och den tillåtna uppsättningen kan optimeringsproblem och metoder för deras lösning delas in i följande klasser:

Optimeringsproblem där målfunktionen och begränsningarna är linjära funktioner löses med så kallade linjära programmeringsmetoder . $f({\vec {x)))$ $g_{i}({\vec {x))),\;i=1,\ldots ,m$
Annars hanterar man ett icke-linjärt programmeringsproblem och tillämpar lämpliga metoder. I sin tur skiljer sig två särskilda uppgifter från dem:
- om och är konvexa funktioner, så kallas ett sådant problem ett konvext programmeringsproblem ; $f({\vec {x)))$ $g_{i}({\vec {x))),\;i=1,\ldots ,m$
- om , då har vi att göra med ett heltals (diskret) programmeringsproblem . ${\mathbb {X}}\subset {\mathbb {Z}}$

Enligt kraven på jämnhet och närvaron av partiella derivat i den objektiva funktionen kan de också delas in i:

direkta metoder som endast kräver beräkning av den objektiva funktionen vid approximationspunkter;
första ordningens metoder : kräver beräkning av de första partiella derivatorna av en funktion;
andra ordningens metoder: kräver beräkning av andra partiella derivator, det vill säga hessian för den objektiva funktionen.

Dessutom är optimeringsmetoder indelade i följande grupper:

analytiska metoder (till exempel metoden för Lagrange-multiplikatorer och förhållandena för Karush - Kuhn - Tucker );
numeriska metoder ;
grafiska metoder .

Beroende på typen av uppsättning X , klassificeras matematiska programmeringsproblem som:

diskreta programmeringsproblem (eller kombinatorisk optimering ) - om X är ändligt eller räknebart ;
heltalsprogrammeringsproblem - om X är en delmängd av uppsättningen heltal ;
icke-linjära programmeringsproblem om begränsningarna eller objektivfunktionen innehåller icke-linjära funktioner och X är en delmängd av ett ändligt dimensionellt vektorrum .
Om alla restriktioner och objektivfunktionen endast innehåller linjära funktioner, är detta ett linjärt programmeringsproblem.

Dessutom är grenar av matematisk programmering parametrisk programmering , dynamisk programmering och stokastisk programmering .

Matematisk programmering används för att lösa optimeringsproblem inom operationsforskning .

Metoden för att hitta extremumet bestäms helt av problemets klass. Men innan du får en matematisk modell måste du utföra fyra steg av modellering:

Bestämma gränserna för optimeringssystemet
- Vi förkastar de kopplingar mellan optimeringsobjektet och omvärlden som inte i hög grad kan påverka optimeringsresultatet, eller, mer exakt, de utan vilka lösningen är förenklad
Val av kontrollerade variabler
- Vi "fryser" värdena för vissa variabler (ohanterade variabler). Andra får ta eventuella värden från området för tillåtna beslut (kontrollerade variabler)
Definiera begränsningar för kontrollerade variabler
- … (jämlikheter och/eller ojämlikheter)
Val av numeriskt optimeringskriterium (t.ex. prestandaindikator )
- Skapa en objektiv funktion

Historik

Linjära programmeringsproblem var de första studerade i detalj problem med att hitta ytterligheten av funktioner i närvaro av begränsningar såsom ojämlikheter . 1820 föreslog Fourier och sedan 1947 George Dantzig en metod för riktad uppräkning av angränsande hörn i riktning mot ökande objektiv funktion - simplexmetoden , som blev den främsta för att lösa linjära programmeringsproblem.

Närvaron av termen "programmering" i disciplinens namn förklaras av det faktum att de första studierna och de första tillämpningarna av linjära optimeringsproblem var inom ekonomiområdet, eftersom ordet "programmering" på engelska betyder planering , ritning upp planer eller program. Det är ganska naturligt att terminologin speglar det nära samband som finns mellan den matematiska formuleringen av problemet och dess ekonomiska tolkning (studie av det optimala ekonomiska programmet). Termen " linjär programmering " föreslogs av J. Danzig 1949 för att studera teoretiska och algoritmiska problem relaterade till optimering av linjära funktioner under linjära begränsningar.

Därför beror namnet "matematisk programmering" på att målet med att lösa problem är att välja det optimala handlingsprogrammet.

Identifieringen av en klass av extrema problem definierade av en linjär funktional på en uppsättning definierad av linjära begränsningar bör hänföras till 1930-talet. En av de första som studerade linjära programmeringsproblem i allmän form var: John von Neumann , en matematiker och fysiker som bevisade huvudsatsen om matrisspel och studerade den ekonomiska modell som bär hans namn, och L. V. Kantorovich , en sovjetisk akademiker, Nobel Pristagare (1975), som formulerade ett antal linjära programmeringsproblem och föreslog 1939 en metod för att lösa dem ( metoden för att lösa faktorer ), som skiljer sig något från simplexmetoden.

År 1931 övervägde den ungerske matematikern B. Egervari en matematisk formulering och löste ett linjärt programmeringsproblem som kallas "valproblemet", lösningsmetoden kallades för den " ungerska metoden ".

L. V. Kantorovich och M. K. Gavurin utvecklade metoden för potentialer 1949 , som används för att lösa transportproblem . I efterföljande verk av L. V. Kantorovich, V. S. Nemchinov , V. V. Novozhilov , A. L. Lurie , A. Brudno , A. G. Aganbegyan , D. B. Yudin , E. G. Golshtein och andra vidareutvecklade matematiker och ekonomer både den linjära programmeringsmetoden och den onlinebaserade tillämpningen av dess matematiska och onlinebaserade programmering. till studiet av olika ekonomiska problem.

Många verk av utländska forskare ägnas åt metoderna för linjär programmering. 1941 satte F. L. Hitchcock transportutmaningen . Den grundläggande metoden för att lösa linjära programmeringsproblem, simplexmetoden , publicerades 1949 av J. Dantzig. Metoderna för linjär och icke-linjär programmering utvecklades vidare i verk av G. Kuhn , A. Tucker , Gass (Saul I. Gass), Charnes (A. Charnes), Beale (EM Beale) och andra.

Samtidigt med utvecklingen av linjär programmering ägnades mycket uppmärksamhet åt icke-linjära programmeringsproblem , där antingen den objektiva funktionen , eller begränsningarna, eller båda är icke-linjära. År 1951 publicerades G. Kuhns och A. Tuckers arbete , där nödvändiga och tillräckliga optimalitetsvillkor för att lösa olinjära programmeringsproblem gavs. Detta arbete låg till grund för efterföljande forskning inom området.

Sedan 1955 har många verk som ägnas åt kvadratisk programmering publicerats (verk av Beal, Barankin och R. Dorfman , Frank (M. Frank) och F. Wolf , G. Markowitz , etc.). Verken av Dennis (JB Dennis), Rosen (JB Rosen) och Zontendijk (G. Zontendijk) utvecklade gradientmetoder för att lösa icke-linjära programmeringsproblem.

För närvarande, för effektiv tillämpning av matematiska programmeringsmetoder och för att lösa problem på datorer, har algebraiska modelleringsspråk utvecklats , vars representanter är AMPL och LINGO .

Se även

Anteckningar

↑ Källa: Altai Regional Universal Scientific Library. V. Ya. Shishkova (AKUNB) Arkiverad 5 mars 2022 på Wayback Machine . Optimeringsmetoder: Proc. ersättning. Brazovskaya N.V.; Altai State Technical University I. I. Polzunova, [Center of Distance. utbildning].-Barnaul: Publishing House of AltSTU, 2000, 120 sid. - UDC / LBC 22.183.4 B871
↑ Hitta det optimala: Datorn utökar möjligheter . - M . : Nauka, 1989. - S. 14 . — ISBN 5-02-006737-7 .

Litteratur

Abakarov A. Sh., Sushkov Yu. A. Statistisk studie av en global optimeringsalgoritm . - FORA:s handlingar, 2004.
Akulich I. L. Matematisk programmering i exempel och uppgifter: Proc. bidrag för studenters ekonomi. specialist. universitet. - M . : Högre skola, 1986.
Gill F., Murray W., Wright M. Praktisk optimering. Per. från engelska. — M .: Mir, 1985.
Girsanov IV Föreläsningar om matematisk teori för extrema problem. - M .; Izhevsk : Forskningscentrum "Regular and Chaotic Dynamics", 2003. - 118 sid. — ISBN 5-93972-272-5 .
Zhiglyavsky A. A., Zhilinkas A. G. Metoder för att söka efter ett globalt extremum. — M .: Nauka, Fizmatlit , 1991.
Karmanov VG Matematisk programmering. - Publishing House of Phys.-Math. Litteratur, 2004.
Korn G., Korn T. Handbok i matematik för vetenskapsmän och ingenjörer. - M . : Nauka, 1970. - S. 575-576.
Korshunov Yu. M., Korshunov Yu. M. Matematiska grunder för cybernetik. — M .: Energoatomizdat , 1972.
Lotov A. V. , Pospelova I. I. Föreläsningsanteckningar om teori och metoder för multikriterieoptimering. Arkiverad 21 januari 2022 på Wayback Machine lösning M., 2005. 127 sid.
Maksimov Yu. A., Filippovskaya EA Algoritmer för att lösa olinjära programmeringsproblem. — M .: MEPhI, 1982.
Maksimov Yu. A. Linjära och diskreta programmeringsalgoritmer. — M .: MEPhI, 1980.
Plotnikov A.D. Matematisk programmering = expresskurs. - 2006. - S. 171. - ISBN 985-475-186-4 .
Rastrigin L. A. Statistiska metoder för sökning. - M. , 1968.
Sergeev Ya. D., Kvasov D. E. Diagonala metoder för global optimering Arkiverad 26 oktober 2017 på Wayback Machine . — M.: FIZMATLIT, 2008. 341s.
Hemdy A. Taha. Introduktion till Operations Research = Operations Research: An Introduction. - 8:e uppl. - M .: Williams , 2007. - S. 912. - ISBN 0-13-032374-8 .
Kini RL, Raifa H. Beslutsfattande enligt flera kriterier: preferenser och substitutioner. - M . : Radio och kommunikation, 1981. - 560 sid.
Zukhovitsky S. I. , Avdeeva L. I. Linjär och konvex programmering. - 2:a uppl., reviderad. och ytterligare .. - M . : Förlag "Nauka", 1967.
Minaev Yu. N. Stabilitet av ekonomiska och matematiska optimeringsmodeller. - M . : Statistik, 1980.
Moiseev NN Numeriska metoder i teorin om optimala system . - M. : Nauka, 1971. - 424 sid.
Moiseev NN Element i teorin om optimala system . — M .: Nauka, 1975. — 528 sid.
Moiseev NN , Ivanilov Yu. P. , Stolyarova EM Optimeringsmetoder . - M. : Nauka, 1978. - 352 sid.

Degtyarev Yu. I. Metoder för optimering. - M . : Sovjetisk radio, 1980. - 272 sid.
Rekleitis G., Reyvindran A., Ragsdel K. Optimering inom teknik. — M .: Mir, 1986. — 400 sid.
Romanovsky IV Algoritmer för att lösa extrema problem. — M .: Nauka, 1977. — 352 sid. - 16 000 exemplar.
Umnov A.E. , Umnov E.A. Parametriska problem i matematisk programmering Arkiverad 9 juli 2021 på Wayback Machine (pdf)
Khokhlyuk VI Parallella heltalsoptimeringsalgoritmer. Arkiverad 18 januari 2021 på Wayback Machine Course of föreläsningar. Novosibirsk , 2007.
Khokhlyuk V. I. Diskreta optimeringsmetoder. Arkiverad 18 januari 2021 på Wayback Machine NSU, 2013. 154 sid.

Länkar

Polyak B.P. Historia om matematisk programmering i Sovjetunionen: analys av fenomenet // Proceedings of the 14th Baikal school-seminar "Optimization methods and their applications". - 2008. - T. 1 . - S. 2-20 .

Ordböcker och uppslagsverk	Stor dansk Stor ryss Britannica (online)
I bibliografiska kataloger	BNF : 11932649z GND : 4043664-0 J9U : 987007538691105171 LCCN : sh85107312 NKC : ph122672

Optimeringsmetoder _
En-dimensionell	gyllene snittmetoden Dikotomi Parabolmetoden Rutnätssökning Enhetlig blocksökningsmetod Fibonacci-metoden Ternär sökning Piyavsky-metoden Strongin metod
Noll ordning	Gauss metod Nelder-Mead metod Hook-Jeeves metod Rosenbrock-metoden Powell metod
Första beställning	lutning nedstigning Zeutendijk-metoden Koordinera nedstigning Konjugerad gradientmetod Kvasi-newtonska metoder Levenberg-Marquardts algoritm
andra beställning	Newtons metod Newton-Raphson-metoden Broyden-Fletcher-Goldfarb-Shanno-algoritm (BFGS)
Stokastisk	Monte Carlo metoden Simulerad glödgning Evolutionära algoritmer differentiell evolution Myralgoritm Partikelsvärmmetod Algoritm för bikoloni Random walk-metod
Linjära programmeringsmetoder _	Enkel metod Gomoris algoritm Ellipsoid metod Potentiell metod
Icke -linjära programmeringsmetoder	Sekventiell kvadratisk programmering

ekonomisk vetenskap
Ekonomisk teori Politisk ekonomi Tillämpad ekonomi
Metodik	Ekonomiska modeller Ekonomiska system matematisk ekonomi Ekonometri Experimentell ekonomi Computational Economics Mikrofundament för makroekonomi
Mikroekonomi	budget satt Lön indifferenskurva Intertemporalt val Osäkerhet Riskhantering Avkastning allmänna nyttigheter Verktyg Förväntat Begränsande Konsumtionsteori Vinst Procent Jämvikt Allmän Distribution Ransonering Resurs sällsynthet Hyra Marknadsföra Tillgång och efterfrågan Pris Marknadsstruktur Konkurrens monopol Perfekt Monopol dubbelsidigt Monopsony Oligopol Oligopsoni Råvaruunderskott Marknadsfiasko Teori om företaget Pris yttre påverkan Elasticitet inkomsteffekt substitutionseffekt skaleffekt Pareto effektivitet Kostar Alternativ Implicit Ej återbetalningsbar offentlig Begränsa Medium Transaktionell Kostnadsnyttoanalys överskott Social Choice
Makroekonomi	Arbetslöshet Valuta Pengar Demand Mening Utsläpp Pengar-kreditpolicy Deflation Inflation Hyperinflation Keynesianskt kors Phillipskurva En kris Den stora depressionen Modell AD-AS Modell IS-LM Bedömd hårdhet " Allmän teori " av Keynes förväntningar Adaptiv Rationell Köpkraftsparitet Betalningssaldo Ränta Lågkonjunktur tillväxtteori Sparande Nationalräkenskapssystemet Samlad efterfrågan Stagflation skattepolitik centralbank Cykelteori Krympflation Effektiv efterfrågan DSGE NAIRU Modeller Mätning av nationalinkomst och produktion Investeringar Prisnivå _ Supply shock Efterfrågan chock
matematisk ekonomi	Operationsforskning Ekonometri Beslutsteori Spel teori Mekanism design Input-output-modellen finansiell matematik
Tillämpad ekonomi	Välfärd Ekonomisk geografi Städer Ekonomisk demografi pengar teori kunskap Utbildning Hälsa Ekonomisk historia Internationellt och världen allmänhetens val Miljö ekologisk ekonomi Branschorganisation Ekonomisk politik Utveckling Regional Religioner Familjer socioekonomi ekonomisk sociologi Arbetskraft offentlig sektor ekonomisk planering Ekonomisk analys av juridik Naturresurser Jordbruk (engelska) Ekonomisk statistik Finansiell
Skolor ( historia ) av ekonomiskt tänkande	Ekonomisk tanke i det antika östern Antikens ekonomiska tanke österrikisk Bloomington buddhist Harvard georgism institutionalism historisk Catheder-socialism Keynesianism Neokeynesianism ( Neoklassisk- Keynesian syntes ) Post-keynesianism Teori om monetär cirkulation Ny klassisk konstitutionell Malthusianism Manchester marginalism marxistisk nymarxistisk _ Ekonomisk mainstream Merkantilism världssystemteori Monetarism nyklassisk Lausanne oortodox Ny institutionell Ny klassiker Real Business Cycle Theory beteendemässiga Ekonomi på utbudssidan Salamanca Stockholm Fysiokrati Chartalism Modern monetär teori Chicago evolutionär Ekologisk Medeltidens ekonomiska tankegång anarkist Mutualism Icke-jämvikt Socialist Termoekonomi Feminist
se även	Mesoekonomi Klassificering av ekonomisk litteratur JEL De viktigaste publikationerna inom ekonomiområdet