Lineāras programmēšanas uzdevumi
Kopīga lineārās programmēšanas uzdevuma forma ir šādā:
Atrast nezināmos mainīgos , kuri maksimizē funkciju
(1)
un apmierina nosacījumus:
(2)
, i = 1, 2, …, n. (3)
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:
(5)
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 .
Modificētās simpleksa metodes ideja
Lineāras programmēšanas uzdevums var būt pierakstīts (5) formā: atrast vektoru x ar nenegatīvām komponentēm, kurš
(6)
(7)
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ā:
(8)
Ja = 0, tad
(9)
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.
Pieņemsim, ka mums ir kaut kāds bāzes plāns x. Mēs gribam uzlabot šo plānu vai pierādīt, ka šis plāns ir optimāls. Šim mērķim sadalam izmaksas vektoru c (kā iepriekš vektoru x) divos apakšvektoros: c = ( cB , cN ). Tad, izmantojot formulu (8), mērķa funkcijas vērtība būs pierakstīta šādi:
Parasti šo izteiksmi pārraksta formā, kura satur šādus apzīmējumus: :
(10)
Pašlaik mums ir pārveidots uzdevums: atrast nenegatīvu vektoru , kurš maksimizē funkciju (10) un apmierina nosacījumus:
(11)
Uzmanīgi apskatīsim mērķa funkciju (10). Ja = 0, tad Kas būs, ja mēs palielināsim nebāzes vektora komponentes? Izteiksmes (10) loceklis
ir vektoru un reizinājums:
Ja rindas i-tais elements ir negatīvs, tad nebāzes elementa palielinājums (no sākuma nulles vērtības) palielina mērķa funkciju. Tādejādi mēs iegūstam šādu optimālu kritēriju:
Plāna optimalitātes kritērijs: tekošais plāns ir optimāls, ja vektors nesatur negatīvus elementus.
Atzīmēsim, ka sauc par relatīvu novērtējumu vektoru.
Tagad mēs varam noformulēt simpleksa metodes ideju: balstoties un relatīvu novērtējumu vektoru, mēs secīgi uzlabojam plānus, kamēr tas ir iespējams. Pie tam katrā reizē mēs ievadam vienu nebāzes mainīgo bāzē, un izvadam vienu bāzes mainīgo no bāzes.
Modificētās simpleksa metodes soļi
Aprakstīsim tipisko soli. Mums ir dota tekoša bāze ar bāzes matricu B un nebāzes matricu N. Inversā matrica arī ir uzdota.
1. solis. Aprēķināt vektorus
. (12)
2. solis. Aprēķināt relatīvu novērtējumu vektoru :
. (13)
Ja visi relatīvie novērtējumi nav negatīvi ( ), tad algoritms savu darbu noslēdz. Pretējā gadījumā seko 3. solis.
3. solis. Kolonnas izvēle, kura ir ievadīta bāzē. Starp negatīvām vērtībām jāizvēlas vismazāko, lai tā vērtība būtu ar numuru p. Tas nozīmē, ka kolonna jāievada bāzē.
4. solis. Pārrēķināt kolonnu , kura ir ievadīta bāzē:
. (14)
5. solis. Kolonnas izvēle, kura ir izvadīta no bāzes. Apskatam vektora pozitīvās komponentes. Ja tādu komponentu nav, algoritms savu darbu noslēdz. Citā gadījumā no pozitīvām komponentēm ir jāizvēlās to, kuras attiecība ir minimālā:
. (15)
Pieņemsim, ka tā ir komponente ar numuru q. Jāizdzēš kolonnu no bāzes.
6. solis. Pārrēķināt bāzi pēc formulam:
, (16)
, (17)
, (18)
, (19)
(20)