perusratkaisua

Perusratkaisu on keskeinen käsite lineaarisessa ohjelmoinnissa. Se tarkoittaa ratkaisua, joka saadaan asettamalla kaikki ei-valitun eli ei-basiskappaleiden muuttujat nolliksi ja ratkaisemalla jäljelle jäävät m muuttujaa. Tehtävä voidaan kirjoittaa standardimuodossa Ax = b, x ≥ 0, missä A on m×n ja rank(A) = m. Valitsemalla joukon B indeksejä, jonka koolla on m, muodostetaan A_B ja ratkaistaan x_B = A_B^{-1} b, samalla kun x_N = 0, missä N = {1,...,n} \ B. Tällöin ratkaisu on perusratkaisu. Se on perus siksi, että se määräytyy vain valitun muuttujaryhmän perusteella.

Perusratkaisu on toteuttamiskelpoinen (basic feasible solution, BFS) silloin, kun x_B ≥ 0. BFS:t vastaavat feasible-alueen ääripisteitä, eli reuna- tai kulmapisteitä. Toisin sanoen jokainen toteuttamiskelpoinen perusratkaisu on optimaalisen alueen jokin ääripiste, jolloin optimointia voidaan lähestyä siirtymällä näiden pisteiden välillä. Yleensä lineaarinen ohjelmointi etenee käymällä läpi BFS:ää käyttämällä yksinkertaismenetelmää (simplex), joka pyrkii parantamaan arvoa siirryttäessä yhdestä BFS:stä toiseen.

Degeneraatio esiintyy, kun jotkin perusmuuttujista ovat nollia. Tällöin samaa pistettä voidaan edustaa useammalla BFS:llä ja optimoitu arvo voi olla sama useammalla kehyksellä, mikä voi vaikuttaa konvergenssiaikaan. Perusratkaisun käsite on kuitenkin peruslineraalisen ohjelmoinnin perustyökalu: se yhdistää lineaarisen järjestelmän ratkaisut ääripisteisiin ja mahdollistaa tehokkaan optimoinnin.

See also: lineaarinen ohjelmointi, käyrän reuna, extreme point, simplex-menetelmä, degeneraatio.