Lineāras programmēšanas metodes

Funkciju sauc par mērķa funkciju, konstantes par mērķa funkcijām vai vērtības koeficientiem, vienādojumu sistēmu (2) par nosacījumu sistēmu, konstantes par nosacījumu sistēmas koeficientiem, konstantes par nosacījumu sistēmas brīvajiem locekļiem, nevienādojumus (3) par nenegatīvības nosacījumus.

Biežāk izmanto matricveida formu uzdevuma nostādnei. Tāpēc ierakstīsim šādus vektorus un matricas:

Izmantojot šos apzīmējumus, formulas (1) – (3) var pierakstīt šādi:

Apskatīto formu sauc par kanonisko formu. Vispārējā gadījumā var izmantot vispārīgo formu, kur: 1) nepieciešams maksimizēt vai minimizēt mērķa funkciju (1); 2) sistēmā (2) vienādības vietā var būt nevienādības zīmes <, >, , ; 3) katram mainīgajam uzdotas robežas , tādejādi .

Lineāras programmēšanas uzdevums var būt pierakstīts (5) formā: atrast vektoru x ar nenegatīvām komponentēm, kurš

Sadalām A matricu divās matricās B un N: A = (B N), kur B ir kvadrātiskā nesingulārā matrica, N ir (m(n¬ – m)) matrica. Sadalīsim arī vektoru x divos vektoros xB un xN dimensijās m un n m : x = , x = ( xB , xN ). Tagad mēs varam pierakstīt sistēmu (7) šādi:

Tas ļauj mums pierakstīt sistēmas (7) atrisinājumu šādā veidā:

Ja , tad vektoru sauc par bāzes plānu, komponentes par bāzes komponentēm, komponentes par nebāzes komponentēm. Tālāk – matricas A kolonnas, kuras pieder B, par bāzes kolonnām, bet kuras pieder N, par nebāzes kolonnām.