Versionen fra 27. dec. 2012, 18:42 redigér ZéroBot (diskussion \| bidrag) 74.014 edits m r2.7.1) (Robot tilføjer hu:Matematikai optimalizálás ← Gå til forrige forskel		Versionen fra 28. jan. 2013, 20:10 redigér fjern redigering Hanshuttel (diskussion \| bidrag) 53 edits No edit summary Gå til næste forskel →
Linje 1: {{wikify}} '''Optimering''' er en [[matematik\|matematisk]] [[Videnskabelig metode\|metode]] til bestemmelse af den optimale løsning på en særlig type af problemer. Det kunne eksempelvis dreje sig om at minimere materialeforbruget ved produktion af en beholder: Hvis målet er at fremstille en metaldåse i form af en hul [[Cylinder (geometri)\|cylinder]] med given vægtykkelse, kan man for fastholdt volumen spørge sig hvorledes dåsen skal dimensioneres for at gøre metalforbruget mindst muligt. En fysisk overvejelse viser at det gælder om at minimere dåsens overfladeareal, og ved optimering indses at målet nås når dåsens højde er lig dåsens diameter, dvs. når dåsens form er så tæt på [[kugle]]ns som muligt. == ~~Matematisk~~Generel ~~grundlag~~formulering == Et optimeringsproblem kan være et ''minimeringsproblem'' eller et ''maksimeringsproblem''. I begge tilfælde handler problemet om at bestemme ekstremumspunkter af en funktion <math>f : S \rightarrow \mathbb{R}</math>, hvor <math>S</math> er en mængde. Ofte kaldes denne funktion for en ''omkostningsfunktion''. I matematikken refererer ordet optimering til studiet af problemer hvor man søger at minimere eller maksimere en [[funktion (matematik)\|funktion]]. Det matematiske grundlag for optimering er [[differentialregning]]. Den generelle formulering af et minimeringsproblem er: Bestem en <math>x \in S</math> således at det for alle <math>y \in S</math> gælder at <math>f(y) \geq f(x)</math>. Et sådant <math>x</math> kaldes da et ''minimum'' for <math>f</math>. Hvis funktionen er defineret på en delmængde af de [[reelle tal]] og antager reelle værdier, kan opgaven formuleres på følgende måde: Givet en funktion <math>f: A \rightarrow \mathbf{R}</math> hvor <math>A \subset \mathbf{R}</math> søges et minimumspunkt eller et maksimumspunkt, dvs. et tal <math>x_0 \in A</math> som opfylder at <math>f(x) \geq f(x_0)</math> henholdsvis <math>f(x) \leq f(x_0)</math> for alle <math>x \in A</math>. Et sådant punkt <math>x_0</math> kaldes et ekstremumspunkt, og den tilsvarende funktionsværdi <math>f(x_0)</math>, som altså er et minimum eller et maksimum, kaldes et ekstremum. Hvis <math>f(x) \geq f(x_0)</math> henholdsvis <math>f(x) \leq f(x_0)</math> for alle <math>x</math> i funktionens definitionsmængde, siges ekstremumspunktet <math>x_0</math> at være globalt. Den generelle formulering af et maksimeringsproblm er: Bestem en <math>x \in S</math> således at det for alle <math>y \in S</math> gælder at <math>f(y) \leq f(x)</math>. Et sådant <math>x</math> kaldes da et ''maksimum'' for <math>f</math>. Hvis funktionen er kontinuert og defineret på et begrænset og lukket [[interval]], antager funktionen ifølge en af den [[analyse\|matematiske analyses]] centrale sætninger såvel maksimum som minimum i intervallet. == Diskret og kontinuert optimering == Hvis funktionen er differentiabel, og <math>x_0</math> er et lokalt ekstremumspunkt, dvs. der findes et åbent interval indeholdende <math>x_0</math>, så <math>f(x) \geq f(x_0)</math> henholdsvis <math>f(x) \leq f(x_0)</math> for alle <math>x</math> i intervallet, da er funktionens differentialkvotient nul i punktet: <math>f'(x_0) = 0</math>. Det betyder at de mulige ekstremumspunkter for <math>f</math> skal søges blandt de <math>x</math>-værdier som opfylder <math>f'(x) = 0</math>. Et optimeringsproblem kan være ''diskret'' eller ''kontinuert'', alt efter egenskaberne ved <math>f</math> og <math>S</math>. ~~== Noter ==~~ Et eksempel på et kontinuert optimeringsproblem er at minimere materialeforbruget ved produktion af en beholder: Hvis målet er at fremstille en metaldåse i form af en hul [[Cylinder (geometri)\|cylinder]] med given vægtykkelse, kan man for fastholdt volumen spørge sig hvorledes dåsen skal dimensioneres for at gøre metalforbruget mindst muligt. Omkostningsfunktionen er her dåsens metalforbrug, der er en kontinuert funktion af dåsens højde og diameter. Note 1: En sådan formulering kaldes et optimeringsproblem (eng: optimization problem or a mathematical programming problem – dette er omtalt på den engelske wikipedia som “a term not directly related to computer programming, but still in use for example in linear programming – see history below”). Mange praktiske og teoretiske problemer kan modelleres efter denne generelle model. En fysisk overvejelse viser at det gælder om at minimere dåsens overfladeareal, og ved optimering indses at målet nås når dåsens højde er lig dåsens diameter, dvs. når dåsens form er så tæt på [[kugle]]ns som muligt. Note 2: Den engelske wikipedia har en meget stor artikel om definitionsmængden for funktionen f der skal optimeres, se ovenfor. Man anvender betegnelsen A med bemærkningen at A er en mængde – her følger en forklaring på hvad dette betyder. Et eksempel på et diskret optimeringsproblem er, givet et vejnet mellem en samling byer i Danmark og længderne af hver vej mellem hvert par af byer, at bestemme den korteste rute, der besøger hver by præcis én gang. Dette problem er også kendt som [[den handelsrejsendes problem \| Travelling salesman problem]]. ~~Typisk er <math>A</math> en delmængde af det euklidske rum <math>\mathbf{R}^n</math>, ofte beskrevet med nogle restriktioner i form af ligninger eller uligheder som elementerne i A skal opfylde.~~ == Lokale maksima og minima == ~~Elementerne i A kaldes for mulige løsninger (eng: feasible solutions). Funktionen f kaldes en formålsfunktion (eng: objective function), eller en omkostningsfunktion (eng: cost function).~~ Hvis omkostningsfunktionen er defineret på et metrisk rum <math>M</math> med metrik <math>d</math>, dvs. at <math>f: M\rightarrow \mathbf{R}</math, kan man tale om lokale minima og maksima. ~~En mulig løsning er en løsning de minimerer (eller maksimerer, afhængigt af målet) funktionen. En sådan fundet løsning kaldes for en optimal løsning.~~ Et ''lokalt minimum'' for <math>f</math> er et <math>x_0 \in A</math>således at der findes en omegn af diameter <math>\delta</math> hvor det for alle <math>x</math> med <math>d(x,x_0) \leq \delta</math> gælder at <math>f(x) \geq f(x_0)</math>. Et lokalt maksimum defineres tilsvarende; blot skal det her gælde for alle <math>x</math> med <math>d(x,x_0) \leq \delta</math> at <math>f(x) \leq f(x_0)</math>. ~~Definitionsmængden A for f kaldes for søgerummet (eng: search space) og elementerne i A kaldes for mulige løsninger (eng: candidate solutions ).~~ ~~Generelt gælder, at når funktionen f ikke indeholder et entydigt bestemt, lokalt ekstremum i det område hvor en mulig løsning ønskes fundet, kan der opstå problemer:~~ ~~Hvis der eksisterer adskillige lokale minima og maxima, hvor et lokalt minimum ''x'' er defineret som et punkt for hvilket der eksisterer et ''δ > 0'' således at for alle x om hvilke det gælder~~ ~~<math>\\|\mathbf{x}-\mathbf{x}^\\|\leq\delta</math>;~~ ~~vil udtrykket~~ ~~<math> f(\mathbf{x}^) \leq f(\mathbf{x})</math>~~ være sandt, det vil sige, i et område i nærheden af ''x'' vil alle funktionsværdier være større eller lig med værdien i det pågældende punkt. Lokale maxima er defineret på tilsvarende måde. Et stort antal algoritmer som er foreslået til at løse sådanne ikke-entydige optimeringer (eng: non-convex problems ) – og dette inkluderer størstedelen af de kommercielt tilgængelige optimeringsalgoritmer – er ikke i stand til at foretage en skelnen (eng: distinction) mellem lokale optimale løsninger (lokale optima) og løsninger som vitterligt er extreme i det valgte område, dvs. ekstremumspunkter der gælder for hele A. De fleste algoritmer vil opfatte en funden lokalt optimal løsning som om det var en optimal løsning for hele A, dvs. programmet indser ikke at dets løsning ikke er den rigtige. Den gren af anvendt matematik og [[numerisk analyse]] der beskæftiger sig med udvikling af deterministiske algoritmer som er i stand til at garantere konvergens indenfor en endelig tid (dvs. som er i stand til at finde den korrekte løsning, og hvor man er i stand til at give et bud på hvor lang tid programmet skal bruge på det) kaldes for global optimering. == Kildehenvisning ==

Optimering (matematik): Forskelle mellem versioner