Matematikal na optimisasyon

Mula sa Wikipediang Tagalog, ang malayang ensiklopedya
Tumalon sa: nabigasyon, hanapin
Grapo ng paraboloid na ibinigay ng f(x,y) = -(x²+y²)+4. Ang global na maksimum sa (0,0,4) ay tinutukoy ng isang pulang tuldok.

Sa matematika, agham komputasyonal, o agham ng pangangasiwa, ang matematikal na optimisasyon o matemetikal na pagpoprograma, o optimisasyon ay tumutukoy sa pagpili ng pinakamahusay na elemento mula sa isang hanay ng mga magagamit na alternatibo. Sa pinakasimpleng kaso, ang problemang optimisasyon ay binubuo ng pag-ma-maksima o pag-mi-minima ng isang real na punsiyon sa pamamagitan ng sistematikong pagpili ng mga halagang input sa loob ng isang pinapayagang hanay at kukwentahin ang halaga ng punsiyon. Ang paglalahat ng teoriyang optimisasyon at mga paraan sa ibang mga pormulasyon ay binubuo ng isang malaking sakop ng nilalapat na matematika. Sa mas pangkalahatan, ang optimisasyon ay binubuo ng paghahanap ng "pinakamahusay na magagamit" na mga halaga ng isang obhektibong punisyon sa isang ibinigay na inilarawang sakop(domain) kabilang ang iba't ibang mga uri ng obhektibong punsiyon at iba't ibang mga uri ng sakop.

Mga problemang optimisasyon[baguhin | baguhin ang batayan]

Ang isang problemang optimisasyon ay maaaring ilarawan sa sumusunod na paraan

Ibinigay: ang isang punsiyon na f : A R mula sa isang hanay na A sa mga real na bilang
Hinanap: ang isang elementong x0 sa A sa gayong ang f(x0) ≤ f(x) para sa lahat ng x sa A ("minimisasyon") o sa paraang ang f(x0) ≥ f(x) para sa lahat ng x sa A ("maksimisasyon").

Ang gayong pormulasyon ay tinatawag na optimisasyong problema o matematikal na pagpoprogramang problema. Maraming mga praktikal at teoretikal na problema ay maaaring imodelo sa pangkalahatang balangkas na ito. Ang mga problemang pinormula gamit ang paraang ito sa mga larangan ng pisika at bisyon ng kompyuter ay maaaring tumukoy sa paraang gaya ng enerhiyang minimisasyon na tumutukoy sa halaga ng punsiyong f bilang kumakatawan sa enerhiya ng sistemang minomodelo. Sa karaniwan, ang A ay isang pang-ilalim na hanay ng espasyong Euclidean na Rn, na kalimitang tinutukoy ng isang hanay ng mga pagtatakda, mga ekwalidad at inekwalidad na kailangang sapatan ng mga kasapi ng A. Ang sakop na A ng f ay tinatawag na espasyo ng paghahanap o hanay ng pagpipilian samantalang ang mga elemento ng A ay tinatawag na mga kandidatong solusyon o mga magagawang solusyon(feasible solutions). Ang punsiyong f ay tinatawag na obhektibong punsiyon, halagang punsiyon(cost function/minimization), utilidad na punsiyon(utilitiy function/maximization) sa ilang mga larangan, enerhiyang punsiyon o enerhiyang punsiyonal. Ang isang magagawang solusyon na nag-mi-minima(o nag-mamaksima kung ito ang layunin) ng obhektibong punsiyon ay tinatawag na solusyong optimal. Sa konbensiyon, ang pamantayang anyo ng isang problemang optimisasyon ay isinasaad sa mga termino ng minimisasyon. Sa pangkalahatan, malibang ang parehong obhektibong punsiyon at ang magagawang rehiyon ay konbeks sa isang problemang minimisasyon, maaaring mayroon ilang mga lokal na minima kung saan ang isang lokal na minimum na x* ay inilalarawan bilang isang punto kung saan may umiiral na isang δ > 0 upang para sa lahat ng x sa gayong ang

ang ekspresyong

ay totoo. Ang ibig sabihin nito, sa isang rehiyon sa palibot ng x*, ang lahat ng mga halaga ng punsiyon ay mas mataas o katumbas ng halaga sa puntong iyon. Ang lokal na maksima ay inilalarawan sa parehong paraan. Ang isang malaking bilang ng mga algoritmo sa paglutas ng mga hindi konbeks na problema kabilang ang karamihan ng mabibiling mga tagalutas(solvers) ay walang kakayahan na magtangi sa pagitan ng isang lokal na optimal na mga solusyon at tiyak na mga optimal na solusyon at tinatrato ang mga lokal na optimal na solusyon bilang mga aktuwal na solusyon sa orihinal na problema. Ang sangay ng nilalapat na matematika at numerikal na analisis na umuukol sa pagbuo ng deterministikong mga algoritmo na may kakayahan sa paggagarantiya ng pagtatagpo(convergence) sa may hangganang panahon sa aktuwal na optimal na solusyon ng isang hindi-konbeks na problema ay tinatawag na global na optimisasyon.

Notasyon[baguhin | baguhin ang batayan]

Ang mga problemang optimisasyon ay kalimitang inihahayag ng espesyal na notasyon. Ang mga sumusunod ang ilang mga halimbawa.

Minimum at maksimum na halaga ng isang punsiyon[baguhin | baguhin ang batayan]

Ituring ang sumusunod na notasyon:

Ito ay tumutukoy sa minimum na halaga ng obhektibong punsiyong x2 kapag pipili ng x mula sa hanay ng mga real na bilang . Ang minimum na halaga sa kasong ito ay , na umiiral sa .

Katulad nito, ang notasyong

ay humihingi ng maksimum na halaga ng obhektibong punsiyong 2x kung saan ang x ay maaaring anumang real na bilang. Sa kasong ito, walang gayong maksimum dahil ang obhektibong punsiyon ay hindi tinatakdaan kaya ang sagot ay inpinidad o "hindi matukoy".

Optimal na mga argumentong input[baguhin | baguhin ang batayan]

Pangunahing lathalain: Arg max

Ituring ang sumusunod na notasyon:

o ang katumbas na

Ito ay kumakatawan sa halaga o mga halaga ng argumentong x sa interbal na na nagmi-minima ng obhektibong punsiyong x2 + 1 (ang aktuwal na minimum na halaga ng punsiyong iyon ay hindi ang hinihingi ng problema). Sa kasong ito, ang sagot ay x = -1, dahil ang x = 0 ay hindi magagawa(infeasible) na ang ibig sabihin ay kabilang sa magagawang hanay. Sa katulad na paraan.

ang katumbas na

ay kumakatawan sa pares na na nag-mamaksima ng halaga ng obhektibong punsiyong na may dinagdaga ng pagtatakdang ang x ay nasa interbal na (muli, ang aktuwal na halagang maksimum ng ekspresyon ay hindi mahalaga). Sa kasong ito, ang mga solusyon ang pares ng anyong (5, 2kπ) at (−5,(2k+1)π) kung saan ang k ay sumasaklaw sa ibabaw ng lahat ng mga intedyer. Ang arg min at arg max ay minsang isinulat na argmin at argmax at tumatayo para sa argument of the minimum at argument of the maximum.