Optimizazio (matematika)

Matematikan, estatistiketan, zientzia enpirikoetan, ekonomian edo konputazioaren zientzian, optimizazioa (edo hoberenatzea) helburuko funtzio bat maximizatu edo minimizatu egiten duten ebazkizunen azterketa eta ebazpena da (irizpideren bati dagokionez). Ikerketa operatiboa matematikaren eremuetako bat da, eta haren oinarrietan optimizazioak funtzionatzen du.^[1]

Hoberenatze-ebazkizun bat: f(x) funtzioa maximizatzen duen x balioa x₀ da. Funtzioaren maximoa f(x₀) da.

Optimizazioaren teoria eta beste formulazio batzuetarako teknikak orokortzeak matematika aplikatuen eremu handia hartzen du. Orohar, optimizazioan sartzen da funtzio objektiboren baten "balio onenak" aurkitzea, domeinu jakin batean, xede-funtzio mota eta domeinu-mota desberdinak barne.

Optimizazioa optimizatzeko ekintza eta efektuari dagokio. Oro har, zerbait ahalik eta modu eraginkorrenean egiteko edo ebazteko gaitasunari egiten dio erreferentzia, eta, kasurik onenean, ahalik eta baliabide gutxien erabiliz.

Hobeneratzeak aplikazio zabalak ditu: ekonomian, etekinak (helburuko funtzioa) maximizatzeko burutu beharreko ekoizpena (aldagaia) zein den; motore baten errendimendua (helburuko funtzioa) maximizatzeko erantsi beharreko erregaiaren ezaugarri kuantitatibo bat (aldagaia) zehaztea; erreakzio kimiko batek behar duen tenperatura (helburuko aldagaia) minimizatzeko, osagai baten kopurua (aldagaia) zenbat izan behar den.

"Optimizazioa, Programazio lineala" liburuaren azaleko marrazkia (UEU, 1995). Hainbat herritatik pasa behar dela baldintza gisa jarrita ibilbide "optimo" bat bilatzea ohiko ariketa bat izaten da jakintza-arlo honetan. Elena Lazkanoren marrazkian Euskal Herriko hiriburu guztiak bisitatzeko ibilbide bat agertzen da^[2].

Optimizazioen problemak

Emanda funtzio bat: ${\displaystyle f:A\rightarrow \mathbb {R} }$ , ${\displaystyle x_{0}\in A}$ balioa bilatu behar da helburuko funtzioa maximizatzeko, hots ${\displaystyle f(x_{0})\geq f(x)}$ egiten duena ${\displaystyle x\in A}$ balio guztietarako; edota minimizatzeko, hots ${\displaystyle f(x_{0})\leq f(x)}$ egiten duena ${\displaystyle x\in A}$ balio guztietarako. Ohikoa da, aldi berean, ${\displaystyle x\,}$ aldagaiak har ditzakeen ${\displaystyle A\,}$ multzoko balioei buruz murrizketak ezartzea.

Formulazio horri optimizazio problema edo programazio matematikoaren problema deitzen zaio (konputagailuen programazioarekin zuzenean lotuta ez dagoen baina oraindik erabiltzen den termino bat, programazio linealean adibidez - ikus Historia atala). Problema teoriko eta mundu errealeko asko eskema orokor honen bidez molda daitezke. Teknika hau fisika eta ordenagailu bidezko ikusmenaren eremuetan erabiliz formulatutako problemak dira teknika energiaren minimizazio gisa, modelatzen ari den sistemaren energia adierazten duen f funtzioaren balioaz ari garela.

Normalean, ${\displaystyle A\,}$ ${\displaystyle R^{n}}$ espazio euklidearraren azpimultzoren bat izaten da, askotan ${\displaystyle A\,}$-ko elementuek bete behar dituzten murrizketa, murrizketa edo desberdintasunen multzo batek mugatzen duena.${\displaystyle f}$-ren ${\displaystyle A\,}$ domeinuari bilaketa espazioa edo aukeraketa multzoa esaten zaio, eta ${\displaystyle A\,}$-ren elementuei, berriz, erantzun hautagaiak edo erantzun egingarriak.

${\displaystyle f}$ funtzioari, era askotara, funtzio objektiboa, kostu-funtzioa (minimizazioa), erabilgarritasun-funtzioa (maximizazioa), eta beste arlo batzuetan, energia-funtzioa edo energia funtzionala esaten zaio. Funtzio objektiboa minimizatzen (edo maximizatzen, helburua hori bada) duen soluzio egingarri bati soluzio optimoa deitzen zaio.

Hitzarmen bidez, optimizazio-problema baten formatu estandarra minimizazioari dagokionez deklaratuta dago. Oro har, funtzio objektiboa eta eskualde egingarria minimizazio-problema batean ganbilak izan ezean, minimo lokal batzuk egon daitezke, non x* minimo lokal bat definitzen den puntu gisa, zeinarentzat ${\displaystyle \delta }$ > 0 bat dagoen, non x

${\displaystyle ||x-x^{*}||\leq \delta }$.

Honako expreso hau egiazkoa da:

${\displaystyle f(x^{*})\leq f(x)}$

hau da, hau da, x* inguruko eskualderen batean, funtzioaren balio guztiak puntu horretako balioa baino handiagoak edo berdinak dira. Maximo lokala antzera definitzen da.

Problema ez-ganbilak ebazteko proposatutako algoritmo ugari – komertzialki eskuragarri dauden konpontzaile gehienak barne – ez dira gai irtenbide lokal optimoen eta soluzio optimo zorrotzen arteko bereizketa egiteko, eta lehenak jatorrizko arazoaren egungo soluzio gisa tratatzen dituzte. Matematika aplikatuaren eta zenbakizko analisiaren adarrari optimizazio globala esaten zaio. Algoritmo deterministen garapenaz arduratzen da, eta algoritmo horiek gai dira konbergentzia denbora finituan bermatzeko problema ez-ganbil baten benetako soluzio optimoari.

Notazioa

Optimizazio-problemak askotan notazio berezi batekin adierazten dira. Hona hemen adibide batzuk.

Funtzio baten maximo eta minimoen balioak

Kontsidera dezagun notazio hau:

${\displaystyle \min(x^{2}+1)}$ non ${\displaystyle x\in \mathbb {R} }$

Honek ${\displaystyle x^{2}+1}$ funtzioaren minimoaren balioa adierazten du, x-a zenbaki errealen multzotik hautatzen denean, ${\displaystyle \mathbb {R} }$. Kasu honetan balio minimoa 1 da eta ${\displaystyle x=0}$ rako gertatzen da. Modu berean, ondoko notazioa:

${\displaystyle \max 2x}$ non ${\displaystyle x\in \mathbb {R} }$

2x helburu-funtzioaren gehieneko balioa adierazten du, eta x zenbaki erreala da. Kasu honetan, ez dago maximorik, beraz, ez dago balio optimo mugaturik.

Historia

Pierre de Fermat eta Joseph Louis Lagrangek kalkuluan oinarritutako formulak aurkitu zituzten balio optimoak identifikatzeko, eta Isaac Newtonek eta Carl Friedrich Gaussek metodo iteratiboak proposatu zituzten optimoa hurbiltzeko. Historikoki, optimizazio problema batzuei erreferentzia egiteko programazio lineal terminoa George B. Dantzig-i zor zaio, nahiz eta teoriaren zati handi bat Leonid Kantorovichek 1939an sartua izan. Dantzig-ek 1947an argitaratu zuen Sinplex Algoritmoa delakoa, eta John von Neumannek urte berean garatu zuen dualitasunaren teoria.

Testuinguru horretan, programazio terminoa ez da ordenagailuen programazioari buruzkoa. Izan ere, terminoa Estatu Batuetako armadak entrenamenduaren eta planifikazio logistikoaren proposamena aipatzean erabili zuen programatik dator, horixe izan baitzen Dantzigek garai hartan aztertu zuen problema.

Hona hemen optimizazio matematikoaren arloko beste ikertzaile garrantzitsu batzuk:

• Richard Bellman
• Ronald A. Howard
• Narendra Karmarkar
• William Karush
• Leonid Khachiyan
• Joseph Louis Lagrange
• László Lovász

Erreferentziak

1. Wis.), Symposium on Nonlinear Programming (1st : 1970 : Madison,. (2014). Nonlinear Programming : Proceedings of a Symposium Conducted by the Mathematics Research Center, the University of Wisconsin, Madison, May 4-6, 1970. Academic Press/Elsevier Science ISBN 978-1-4832-7246-7. PMC 898422240. (Noiz kontsultatua: 2022-12-21).
2. Fernandez Gonzalez, Victoria; Jauregi, Ana Zelaia. (1995). Optimizazioa. Programazio lineala. UEU ISBN 978-84-86967-65-9. (Noiz kontsultatua: 2022-04-22).

Ikus, gainera

• Victoria Fernández
• Ana Zelaia

Kanpo estekak

• Datuak: Q141495
• Multimedia: Optimization / Q141495