matematinis programavimas

matemãtinis programãvimas, optimizãvimas, matematikos ir informatikos šaka, tirianti uždavinius, susijusius su funkcijų ekstremumų nustatymu aibėse, nusakytose lygybių ir (arba) nelygybių sistemomis. Matematinio programavimo uždaviniai iškyla sprendžiant gamybos planavimo ir valdymo, projektavimo, perspektyvinio planavimo uždavinius. Bendrasis matematinio programavimo uždavinys formuluojamas taip: rasti skaliarinės funkcijos f₀(x) ekstremumą (minimumą ar maksimumą) su sąlygomis f_j(x) ≤ 0, j = 1, 2, ..., m; x∈Q; (∗) čia Q – vektorinės erdvės aibė, f_j(x) – ribinės funkcijos. Funkcija f₀(x) vadinama tikslo funkcija, aibė Ω = {x∈Q|f_j(x) ≤ 0, j = 1, ..., m} – leidžiamąja aibe (planų aibe), ekstremumo taškas x* – optimaliu tašku (planu). Ekstremumų savybes ir skaitinius sprendimo metodus lemia funkcijų f_j(x) ir aibės Q savybės. Tiesinis programavimas tiria uždavinius, kurių funkcijos f_j(x) yra tiesinės, o aibę Q sudaro n‑matės euklidinės erdvės Rⁿ vektoriai su neneigiamomis koordinatėmis ($Q={\text{R}}_{\text{+}}^n$). Matematinio programavimo šaka, tirianti uždavinius, kuriuose leidžiamąją aibę Ω sudaro vektoriai, o jų visos koordinatės ar dalis koordinačių yra sveikieji skaičiai, vadinama sveikaskaičiu programavimu. Iškilasis programavimas tiria iškilosios funkcijos minimizavimo uždavinius, kurių ribinės funkcijos f_j(x) ir aibė Q yra iškilosios. Atvejį, kai tikslo funkcija yra kvadratinė, o ribinės funkcijos tiesinės, tiria kvadratinis programavimas. Bendrasis kvadratinio programavimo uždavinys: minimizuoti funkciją $f_0(x)=\frac{1}{2}(x,\mathit{Cx})-(b,x)$, kai Ax ≤ c; čia C – simetrinė, pusiau teigiamai apibrėžta ((x, Cx) ≥ 0 kiekvienam x) n × n matrica, A – m × n matrica, x ir b – n‑mačiai vektoriai, c – m‑matis vektorius (paprastaisiais skliaustais pažymėtos skaliarinės vektorių sandaugos). Iškilojo programavimo uždavinio ekstremumo būtinas sąlygas nusako Kuhno ir Tuckerio teorema. Tegu funkcijos f_j(x) yra iškilosios ir aibė Ω tenkina Slaterio sąlygą, t. y. egzistuoja bent vienas aibės Ω taškas, kuriame visos (*) nelygybės yra griežtos. Vektorius x* yra sprendinys tada ir tik tada, kai egzistuoja toks vektorius u*, kuris su x* sudaro Lagrange’o funkcijos $F(x,y)=f_0(x)+\sum _{j=1}^m{u}_j{f}_j(x)$ balno tašką, t. y. tenkina nelygybes F(x*, u) ≤ F(x*, u*) ≤ F(x, u*) kiekvienam x ∈Q ir u ≥ 0.

Paprasčiausias skaitinis iškilojo programavimo metodas yra leidžiamųjų krypčių metodas. Juo pagal formulę x^k + 1 = x^k + t_ke^k sudaroma vektorių x* seka, artėjanti į x*; vektorius e^k parenkamas taip, kad esant pakankamai mažoms skaliaro t_k ≥ 0 reikšmėms vektorius x^k + 1 priklausytų aibei Ω, o tikslo funkcija mažėtų. Kai funkcijos f_j(x), j = 1, ..., m ir aibė Q yra bet kokios, matematinio programavimo uždavinius tiria netiesinis programavimas. Jo uždaviniams būdingi lokalieji ekstremumai, kurie apskaičiuojami iškilojo programavimo metodais. Kai ribojimų funkcijos f_j(x), j = 1, ..., m priklauso nuo parametro, kartais galima nustatyti tas parametro kitimo sritis, kuriose matematinio programavimo uždavinio sprendinys yra pastovus. Tokius uždavinius tiria parametrinis programavimas. Stochastinis programavimas tiria matematinio programavimo uždavinį, kurio funkcijos f_j(x) yra atsitiktiniai dydžiai. Matematinio programavimo uždavinį galima nagrinėti taikant daugiažingsnį sprendimą – nuosekliai nustatant kiekvieną ekstremumo taško koordinatę. Šį sprendimo metodą tiria dinaminis programavimas.

Pirmasis matematinio programavimo uždavinį, kaip nustatyti sąlyginį ekstremumą, kai (*) nelygybės yra lygybės, suformulavo ir išsprendė J. L. de Lagrange’as. Matematinis programavimas susiformavo 20 a. 5–7 dešimtmetyje. Svarbūs Georgeʼo Bernardo Dantzigo, Herberto Elio Scarfo, Saulo Irvingo Gasso, Ralpho Tyrrello Rockefellerio, Philipo Starro Wolfo, Leonido Chačiano (visi Jungtinės Amerikos Valstijos), Judino Golšteino, Nikolajaus Šoro, Davido Judino, L. Kantorovičiaus, Jurijaus Nesterovo (visi SSRS), Narendros Krishnos Karmarkaro (Indija) matematinio programavimo darbai.