Optimering (matematik)

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 25. september 2021; checks kræver 4 redigeringer .

Optimering (i matematik , datalogi og operationsforskning ) er opgaven med at finde et ekstremum (minimum eller maksimum) af en objektiv funktion i et område af et endeligt-dimensionelt vektorrum , begrænset af et sæt lineære og/eller ikke- lineære ligheder og/eller uligheder .

Teorien og metoderne til løsning af et optimeringsproblem studeres ved matematisk programmering .

Matematisk programmering  er en gren af ​​matematikken, der udvikler teori, numeriske metoder til løsning af multidimensionelle problemer med begrænsninger. [en]

Udtalelse af optimeringsproblemet

I designprocessen er opgaven normalt sat til at bestemme den bedste, i en vis forstand, struktur eller værdier af objektparametre . Et sådant problem kaldes et optimeringsproblem. Hvis optimering er forbundet med beregningen af ​​optimale parameterværdier for en given objektstruktur, så kaldes det parametrisk optimering . Problemet med at vælge den optimale struktur er strukturel optimering .

Standard matematisk optimeringsproblemet er formuleret på denne måde. Blandt de elementer χ, der danner mængderne X, skal du finde et element χ * , der giver minimumværdien f(χ * ) af den givne funktion f(χ). For at kunne udgøre optimeringsproblemet korrekt, er det nødvendigt at indstille:

  1. Det tilladte sæt  er sættet ;
  2. Objektiv funktion  -mapping ;
  3. Søgekriterium (max eller min).

Løs derefter problemet betyder en af:

  1. Vis det .
  2. Vis, at den objektive funktion ikke er afgrænset nedenfor.
  3. Find .
  4. Hvis , så find .

Hvis funktionen, der minimeres, ikke er konveks , så begrænser de sig ofte til at finde lokale minima og maksima: punkter sådan, at overalt i nogle af deres kvarterer for et minimum og for et maksimum.

Hvis sættet er tilladt , kaldes et sådant problem et ubetinget optimeringsproblem , ellers et betinget optimeringsproblem .

Klassificering af optimeringsmetoder

Den generelle notation af optimeringsproblemer definerer en bred vifte af deres klasser. Valget af metode (effektiviteten af ​​dens løsning) afhænger af problemets klasse. Klassificeringen af ​​problemer bestemmes af: den objektive funktion og det tilladte område (givet af et system af uligheder og ligheder eller en mere kompleks algoritme). [2]

Optimeringsmetoder er klassificeret efter optimeringsopgaver:

I øjeblikket eksisterende søgemetoder kan opdeles i tre store grupper:

  1. deterministisk;
  2. tilfældig (stokastisk);
  3. kombineret.

I henhold til kriteriet for dimensionen af ​​det mulige sæt er optimeringsmetoder opdelt i endimensionelle optimeringsmetoder og flerdimensionelle optimeringsmetoder .

I form af den objektive funktion og det tilladte sæt kan optimeringsproblemer og metoder til deres løsning opdeles i følgende klasser:

I henhold til kravene til glathed og tilstedeværelsen af ​​partielle derivater i den objektive funktion kan de også opdeles i:

Derudover er optimeringsmetoder opdelt i følgende grupper:

Afhængigt af arten af ​​sættet X klassificeres matematiske programmeringsproblemer som:

Derudover er grene af matematisk programmering parametrisk programmering , dynamisk programmering og stokastisk programmering .

Matematisk programmering bruges til at løse optimeringsproblemer i operationsforskning .

Metoden til at finde ekstremum er fuldstændig bestemt af problemets klasse. Men før du får en matematisk model, skal du udføre 4 modelleringstrin:

Historie

Lineære programmeringsproblemer var de første undersøgte detaljerede problemer med at finde det yderste af funktioner i nærvær af begrænsninger såsom uligheder . I 1820 foreslog Fourier og derefter i 1947 George Dantzig en metode til rettet opregning af tilstødende hjørner i retning af stigende objektiv funktion  - simplexmetoden , som blev den vigtigste til løsning af lineære programmeringsproblemer.

Tilstedeværelsen af ​​udtrykket "programmering" i disciplinens navn forklares ved, at de første undersøgelser og de første anvendelser af lineære optimeringsproblemer var inden for økonomi, da ordet "programmering" på engelsk betyder planlægning , tegning op planer eller programmer. Det er helt naturligt, at terminologien afspejler den tætte sammenhæng, der er mellem den matematiske formulering af problemet og dens økonomiske fortolkning (undersøgelse af det optimale økonomiske program). Udtrykket " lineær programmering " blev foreslået af J. Danzig i 1949 for at studere teoretiske og algoritmiske problemer relateret til optimering af lineære funktioner under lineære begrænsninger.

Derfor skyldes navnet "matematisk programmering", at målet med at løse problemer er at vælge det optimale handlingsprogram.

Identifikationen af ​​en klasse af ekstreme problemer defineret af en lineær funktional på et sæt defineret af lineære begrænsninger bør tilskrives 1930'erne. En af de første til at studere lineære programmeringsproblemer i generel form var: John von Neumann  , en matematiker og fysiker, der beviste hovedsætningen om matrixspil og studerede den økonomiske model , der bærer hans navn, og L. V. Kantorovich  , en sovjetisk akademiker, Nobel Prisvinder (1975), som formulerede en række lineære programmeringsproblemer og foreslog i 1939 en metode til at løse dem ( metoden til at opløse faktorer ), som adskiller sig lidt fra simpleksmetoden.

I 1931 overvejede den ungarske matematiker B. Egervari en matematisk formulering og løste et lineært programmeringsproblem kaldet "valgproblemet", løsningsmetoden blev kaldt den " ungarske metode ".

L. V. Kantorovich og M. K. Gavurin udviklede metoden for potentialer i 1949 , som bruges til at løse transportproblemer . I efterfølgende værker af L. V. Kantorovich, V. S. Nemchinov , V. V. Novozhilov , A. L. Lurie , A. Brudno , A. G. Aganbegyan , D. B. Yudin , E. G. Golshtein og andre videreudviklede matematikere og økonomer både den matematiske programmeringsmetode og dens online-anvendelse. til undersøgelse af forskellige økonomiske problemer.

Mange udenlandske videnskabsmænds værker er viet til metoderne til lineær programmering. I 1941 satte F. L. Hitchcock transportudfordringen . Den grundlæggende metode til løsning af lineære programmeringsproblemer, simplex-metoden  , blev udgivet i 1949 af J. Dantzig. Metoderne til lineær og ikke-lineær programmering blev videreudviklet i værker af G. Kuhn , A. Tucker , Gass (Saul I. Gass), Charnes (A. Charnes), Beale (EM Beale) og andre.

Samtidig med udviklingen af ​​lineær programmering blev der lagt stor vægt på ikke-lineære programmeringsproblemer , hvor enten den objektive funktion eller begrænsninger eller begge er ikke-lineære. I 1951 blev arbejdet af G. Kuhn og A. Tucker udgivet , hvor nødvendige og tilstrækkelige optimalitetsbetingelser for at løse ikke-lineære programmeringsproblemer blev givet. Dette arbejde dannede grundlag for efterfølgende forskning på området.

Siden 1955 er mange værker afsat til kvadratisk programmering blevet udgivet (værker af Beal, Barankin og R. Dorfman , Frank (M. Frank) og F. Wolf , G. Markowitz , etc.). Værkerne af Dennis (JB Dennis), Rosen (JB Rosen) og Zontendijk (G. Zontendijk) udviklede gradientmetoder til løsning af ikke-lineære programmeringsproblemer.

På nuværende tidspunkt er der udviklet algebraiske modelleringssprog til effektiv anvendelse af matematiske programmeringsmetoder og løsning af problemer på computere , repræsentanter for dem er AMPL og LINGO .

Se også

Noter

  1. ↑ Kilde: Altai Regional Universal Scientific Library. V. Ya. Shishkova (AKUNB) Arkiveret 5. marts 2022 på Wayback Machine . Optimeringsmetoder: Proc. godtgørelse. Brazovskaya N.V.; Altai State Technical University I. I. Polzunova, [Afstandscenter. uddannelse].-Barnaul: Publishing House of AltSTU, 2000, 120 s. - UDC / LBC 22.183.4 B871
  2. ↑ At finde det optimale: Computeren udvider muligheder . - M . : Nauka, 1989. - S.  14 . — ISBN 5-02-006737-7 .

Litteratur

Links

  Gå til Wikidata-elementet  Ordbøger og encyklopædier
I bibliografiske kataloger