perusratkaisuihin

Perusratkaisuihin (basic solutions) on käsite, jota käytetään erityisesti lineaarialgebrassa ja optimoinnissa. Seuraamalla matriisijärjestelmän Ax = b ja oletuksella, että A on mitoitettu m×n ja rank(A) = m, perusratkaisu saadaan valitsemalla m sarakkeesta A muodostamaan perussuure, asettamalla loput n−m muuttujat nolliksi ja ratkaisemalla x_B = A_B^{-1} b. Siis valitaan joukko B, jossa A_B on invertible, ja x_N = 0 kaikille N, joiden indeksit eivät kuulu B:hen. Jos sekä x_B että kaikkien ratkaistujen koordinaattien oltava ei-negatiivisia, perusratkaisu on myös perusjohdonmukainen ratkaisu (basic feasible solution).

Perusratkaisut liittyvät erityisesti lineaariohjelmointiin. Standardimuodossa minimi- tai maksimoimisessa c^T x s.t. Ax = b, x ≥ 0, ideaalialueen luvut koostuvat neliöistä, joiden kannalta perusratkaisujen ja niiden ei-negatiivisten rajoitteiden avulla muodostuu polyedr(i)in kulmapisteitä. Tämä tarkoittaa, että kaikki koettavissa olevat ratkaisut voidaan esittää johtopäätöksinä perusratkaisuista tai perusratkaisujen neutraalimuodoista. Vertexit, eli kulmapisteet, vastavat BFS:ää (basic feasible solutions).

Käytännössä perusratkaisuihin liittyy myös degeneroituminen. Sama ratkaisu voi tulla useammasta kuin yhdestä valinnasta B, mikä voi aiheuttaa saman ratkaisun saamisen useilla perussarjoilla. Rank(A) < m -tilanteita voidaan käyttää, mutta ne eivät tuota ei-infiniti- tai ei-olemassaolevan perusratkaisun tilanteita ilman lisäehtoja.

Käyttökohteita ovat lineaariset järjestelmät, operaatioanalyysi, verkko- ja resurssien optimointi sekä muut sovellukset, joissa ongelma on linear, ja jossa on tarve saada kulmapisteitä ja rakenteellista ymmärrystä ratkaisujen muodostumisesta. See also: basic solution, basic feasible solution, degeneracy.