tiesinis programavimas

tiesnis programãvimas, optimizacijos uždavinių sprendimo teorija, algoritmai ir kai kurie bendrieji taikymai. Matematinio tiesinio programavimo uždavinys – rasti tokį aibės A elementą, kuriame tiesinė tikslo funkcija f įgyja minimalią reikšmę. Leistinoji sritis A yra daugiasienis, apibrėžiamas tiesinėmis lygybėmis ir (arba) nelygybėmis. Kai f(x) = $\sum _{i=1}^n$ c_ix_i ir vektorių x = (x₁,…, x_n) aibė A nusakoma sąryšiais $\sum _{i=1}^n$ a_ijx_i = b_j, j = 1,…, m, x_i ≥ 0, i = 1,…, n, yra standartinis tiesinio programavimo uždavinys. Kitokia matematinė forma užrašytus tiesinių funkcijų optimizavimo, esant tiesiniams ribojimams, uždavinius (pvz., maksimizavimo su nelygybiniais ribojimais) galima užrašyti ekvivalenčia standartine forma. Esant papildomiems ribojimams ar prielaidoms apibrėžiamos tiesinio programavimo uždavinių specialios klasės, pvz., tokie tiesinio programavimo uždaviniai, kuriems ieškomi sprendiniai reiškiami sveikaisiais skaičiais (leistinosios srities apibrėžimas papildomas sprendinio sveikaskaitiškumo reikalavimu), vadinami sveikaskaičio tiesinio programavimo uždaviniais. Svarbi tiesinio programavimo uždavinių klasė – transporto uždaviniai, t. y. matematiškai suformuluoti pervežimų optimizacijos uždaviniai, jiems būdingi specialūs ribojimai. Naudojantis ribojimų specifika, buvo sukurti tokių uždavinių sprendimo algoritmai, kur kas efektyvesni už bendruosius tiesinio programavimo algoritmus. Pastarieji yra dviejų tipų: simpleksiniai ir vidinio taško.

Istorija

Pirmąjį simpleksinio tipo algoritmą dar 1939 sukūrė L. Kantorovičius jo suformuluotam gamybos planavimo uždaviniui (matematine forma tai buvo tiesinio programavimo uždavinys) spręsti. Atskirai tokio tipo algoritmą 1947 paskelbė Georgeʼas Bernardas Danzigas (Jungtinės Amerikos Valstijos ). Tuo metu Jungtinėse Amerikos Valstijose buvo sukurti pirmieji kompiuteriai, ir tiesinio programavimo uždaviniai buvo vieni pirmųjų kompiuteriais išspręstų uždavinių. Nors pagal struktūrą tiesinio programavimo uždaviniai yra paprasčiausi, o jiems spręsti skirtas simplekso algoritmas praktiškai plačiai taikomas, algoritmų sudėtingumo teorijos požiūriu simplekso algoritmas nėra geras, t. y. teoriškai sprendimui reikia vis daugiau laiko labai greitai kintant n ir m. Teoriškai geresnį vidinio taško algoritmą, pavadintą elipsoidų algoritmu, 1979 sukūrė Leonidas Chačianas (SSRS). Elipsoidų algoritmas, nors teoriškai ir geresnis už simplekso, praktiškai pastarajam nebuvo lygiavertis. Vidinio taško algoritmai labai aktyviai plėtojami ir taikomi pradedant Narendros Krishnos Karmarkaro (Indija) 1984 darbu, kuriame buvo paskelbtas ne tik teoriškai, bet ir praktiškai efektyvus, vadinamas projektyvusis, algoritmas. Simplekso algoritmo idėją populiariai galima paaiškinti kaip šokinėjimą, pradedamą vienoje iš leistinosios srities viršūnių, po to peršokant į kaimyninę, kurioje tikslo funkcijos reikšmė geresnė; algoritmas grindžiamas tuo faktu, kad ieškomasis sprendinys yra viena iš leistinosios srities viršūnių. Vidinio taško algoritmai generuoja trajektoriją, kuri prasideda leistinosios srities vidiniame taške ir srities viduje iteratyviai tęsiama link sprendinio. 21 a. pradžioje yra sukurta daug tiesinio programavimo kompiuterinių programų, tiek laisvai platinamų, tiek ir komercinių; sėkmingai sprendžiami uždaviniai, kurių kintamųjų skaičius siekia milijonus, o ribojimų skaičius dešimtis tūkstančių. Pažyminėtina tiesinio programavimo teorijos reikšmė ekonomikai (Nobelio ekonomikos premija 1975 L. Kantorovičiui ir T. Ch. Koopmansu už tiesinio programavimo metodų taikymą ekonomikos moksle).

2277

-simplekso metodas