Optimizimi matematikor

Grafiku i një sipërfaqeje të dhënë nga $z=f(x,y)=-(x^{2}+y^{2})+4$. Maksimumi global në $(x,y,z)=(0,0,4)$ tregohet me një pikë blu.

Optimizimi matematikor ( optimizimi i shkruar në mënyrë alternative) ose programimi matematik është zgjedhja e një elementi më të mirë, në lidhje me disa kritere, nga një grup alternativash nën shqyrtim. Në përgjithësi ndahet në dy nënfusha: optimizim diskret dhe optimizim i vazhdueshëm . Problemet e optimizimit lindin në të gjitha disiplinat sasiore që nga shkenca kompjuterike dhe inxhinieria deri te kërkimi operacional dhe ekonomia, dhe zhvillimi i metodave të zgjidhjes ka qenë me interes në matematikë për shekuj me radhë.

Në qasjen më të përgjithshme, një problem optimizimi konsiston në maksimizimin ose minimizimin e një funksioni real duke zgjedhur sistematikisht vlerat hyrëse nga brenda një bashkësie të lejuar dhe duke llogaritur vlerën e funksionit. Përgjithësimi i teorisë dhe teknikave të optimizimit në formulime të tjera përbën një fushë të madhe të matematikës së zbatuar . Në përgjithësi, optimizimi përfshin gjetjen e vlerave "më të mira nën shqyrtim" të disa funksioneve objektive, të dhënë një domeni (ose hyrje) të përcaktuar, duke përfshirë një shumëllojshmëri të llojeve të ndryshme të funksioneve objektive dhe llojeve të ndryshme të fushave.

Problemet e optimizimit

Problemet e optimizimit mund të ndahen në dy kategori, në varësi të faktit nëse ndryshoret janë të vazhdueshme ose diskrete :

• Një problem optimizimi me ndryshore diskrete njihet si një optimizim diskret, në të cilin një objekt si një numër i plotë, permutacion ose graf duhet të gjendet nga një grup i numërueshëm .
• Një problem me ndryshore të vazhdueshme njihet si një optimizim i vazhdueshëm, në të cilin duhet të gjendet një vlerë optimale nga një funksion i vazhdueshëm . Ato mund të përfshijnë probleme të kufizuara dhe probleme multimodale.

Një problem optimizimi mund të paraqitet në mënyrën e mëposhtme:

Jepet: një funksion $f:A\to \mathbb {R}$ nga ndonjë bashkësi $A$ te numrat realë

Kërkohet: një element $x_{0}\in A$ i tillë që $f({\boldsymbol {x}}_{0})\leq f({\boldsymbol {x}})$ për të gjitha $x\in A$ ("minimizimi") ose i tillë që $f({\boldsymbol {x}}_{0})\geq f({\boldsymbol {x}})$ për të gjitha $x\in A$ (" maksimizimi").

Një formulim i tillë quhet një problem optimizimi ose një problem programimi matematikor (një term që nuk lidhet drejtpërdrejt me programimin kompjuterik, por ende përdoret për shembull në programimin linear). Shumë probleme të botës reale dhe teorike mund të modelohen në këtë kuadër të përgjithshëm.

$f(\mathbf {x} _{0})\geq f(\mathbf {x} )\Leftrightarrow -f(\mathbf {x} _{0})\leq -f(\mathbf {x} ),$

mjafton të zgjidhen vetëm probleme minimizimi. Sidoqoftë, perspektiva e kundërt e shqyrtimit vetëm të problemeve të maksimizimit do të ishte gjithashtu e vlefshme.

Problemet e formuluara duke përdorur këtë teknikë në fushat e fizikës mund t'i referohen teknikës si minimizim i energjisë, duke folur për vlerën e funksionit $f$ që përfaqëson energjinë e sistemit që modelohet . Në mësimin makinerik, është gjithmonë e nevojshme të vlerësohet vazhdimisht cilësia e një modeli të dhënash duke përdorur një funksion kostoje ku një minimum nënkupton një grup parametrash ndoshta optimale me një gabim optimal (më të ulët).

Zakonisht, $A$ është një nëngrup i hapësirës Euklidiane $\mathbb {R} ^{n}$, shpesh të specifikuara nga një bashkësi kufizimesh, barazish ose pabarazish që anëtarët e $A$ duhet të plotësojnë. Fusha $A$ e $f$ quhet hapësira e kërkimit ose bashkësia e zgjedhjes, ndërsa elementët e $A$ quhen zgjidhje kandidate ose zgjidhje të realizueshme .

Funksioni $f$ quhet, në mënyra të ndryshme, një funksion objektiv, një funksion humbjeje ose funksion kostoje (minimizimi), një funksion i dobishëm, ose, në fusha të caktuara, një funksion energjie ose funksional energjie . Një zgjidhje e realizueshme që minimizon (ose maksimizon, nëse ky është qëllimi) funksionin objektiv quhet zgjidhje optimale .

Një minimum lokal ${\boldsymbol {x}}*$ përcaktohet si një element për të cilin ekziston ndonjë $\delta >0$ e tillë që

$\forall \mathbf {x} \in A\;{\text{ku}}\;\left\Vert \mathbf {x} -\mathbf {x} ^{\ast }\right\Vert \leq \delta ,\,$

vlen shprehja $f({\boldsymbol {x}}*)\leq f({\boldsymbol {x}})$ ;

Shënimi

Problemet e optimizimit shpesh shprehen me shënime të veçanta. Ketu jane disa shembuj:

Vlera minimale dhe maksimale e një funksioni

Merrni parasysh shënimin e mëposhtëm:

$\min _{x\in \mathbb {R} }\;\left(x^{2}+1\right)$

Kjo shënon vlerën minimale të funksionit objektiv $x^{2}+1$, duke zgjedhur $x$ nga bashkësia e numrave realë $\mathbb {R}$. Vlera minimale në këtë rast është 1, që arrihet për $x=0$.

Në mënyrë të ngjashme, shënimi

$\max _{x\in \mathbb {R} }\;2x$

kërkon vlerën maksimale të funksionit objektiv $2x$, ku $x$ mund të jetë çdo numër real. Në këtë rast, nuk ka një maksimum të tillë pasi funksioni objektiv është i pakufizuar, kështu që përgjigja është " pafundësi " ose "e papërcaktuar".

Argumentet e hyrjes optimale

Merrni parasysh shënimin e mëposhtëm:

${\underset {x\in (-\infty ,-1]}{\operatorname {arg\,min} }}\;x^{2}+1,$

ose në mënyrë të njëvlershme

${\underset {x}{\operatorname {arg\,min} }}\;x^{2}+1,\;{\text{subject to:}}\;x\in (-\infty ,-1].$

Kjo përfaqëson vlerën (ose vlerat) e argumentit $x$ në intervalin $(-\infty ,-1]$ që minimizon (ose minimizon) funksionin objektiv $x^{2}+1$ (vlera minimale aktuale e atij funksioni nuk është ajo që kërkon problemi ). Në këtë rast, përgjigja është $x=-1$, pasi $x=0$ është e pa realizueshme, domethënë nuk i përket grupit të realizueshëm .

Në mënyrë të ngjashme,

${\underset {x\in [-5,5],\;y\in \mathbb {R} }{\operatorname {arg\,max} }}\;x\cos y,$

ose në mënyrë ekuivalente

${\underset {x,\;y}{\operatorname {arg\,max} }}\;x\cos y,\;{\text{subject to:}}\;x\in [-5,5],\;y\in \mathbb {R} ,$

përfaqëson çiftin (ose çiftet) $\{x,y\}$ që maksimizon (ose maksimizojnë) vlerën e funksionit objektiv $x\cos y$, me kufizimin e shtuar që $x$ shtrihet në intervalin $[-5,5]$ (përsëri, maksimumi aktual vlera e shprehjes nuk ka rëndësi). Në këtë rast, zgjidhjet janë çiftet e formës $\{5,2k\pi \}$ dhe $\{-5,(2k+1)\pi \}$, ku $k$ varion mbi të gjithë numrat e plotë .