Simpleksmeetod Maksimumi tunnus: sihifunktsiooni reas ei ole negatiivseid elemente Juhtelemendi valiku reeglid: 1.juhtveeruks valitakse sihifunktsiooni reas kõige negatiivsema elemendiga veerg 2. hinnang veeru positiivsele elemendile saadakse vabaliikme jagamisel hinnatava elemendiga 1.juhtelemendiks valitakse juhtveeru see positiivne element, mille hinnang on kõige väiksem 2.kui juhtveerus ei ole positiivseid elemente, sihifunktsioonil ei ole nendel tingimustel maksimumi (sihifunktsioon kasvab tõkestamatult) Gaussi meetodil arvutatakse lahendi uus esitus, mille baaslahend on lubatav. Uues baaslahendis on
.. ... ... ... ... ... ... ... ... ... ... m. rida am1 am2 ... amn 0 0 ... 1 0 bm 1. Optimaalsuse kontroll: kui sihifunktsiooni reas tundmatute kordajate hulgas esineb kasvõi üksainus negatiivne arv (-cj 0), siis pole lahend optimaalne; kui kõik tundmatute kordajad on mittenegatiivsed (-cj 0), siis on jõutud optimaalse lahendini ja simpleksmeetodi rakendamine on lõppenud. 2. Juhtveeru valimine. Juhtveeruks valida veerg, milles sihifunktsiooni kordaja on negatiivne. Kui selliseid veerge on mitu, siis juhtveeruks valitakse see veerg, milles sihifunktsiooni kordaja on väikseim negatiivne arv. 3. Juhtrea valimine. Juhtrea kindlaksmääramiseks jagatakse tingimustesüsteemi vabaliikmed bi väljavalitud juhtveeru positiivsete nullist erinevate kordajatega aij ja saadud jagatistest valitakse väikseim, millele vastav rida osutubki juhtreaks 4. Juhtelemendi leidmine
2) juhtreaks valitakse alati rida, kus bk 0 ning selajuures on | bk | suurim sellistest vabaliikmetest (kui sellisid on rohkem kui üks, siis nende seast esimene). Kui juhtreaks on valtud k. rida, siis toimub juhtelemendi akl valimine sellest reast järgmise reegli kohaselt: cl cj min | akl | akj 0 | akj | Duaalse simpleksmeetodi samm (2). Seega tuleb juhtveeruks valida juhtreas negatiivsete elementidega veergude hulgast see, mille puhul tabeli esimese rea elemendi jagatis juhtrea samas veerus paikneva elemendiga on absoluutväärtuselt vähim. Duaalse simpleksmeetodi kasutamisel säilib pärast iga sammu tabeli duaalne lubatavus, negatiivne element bk aga asendub elemendiga bk 0. Sihifunktsiooni väärtus küll kahaneb igal sammul monotoonselt, kuid see on loomulik, sest lähenemine optimaalsele lahendile toimub väljapoolt
39. Kuidas saab leida duaalse ülesande optimaalse lahendi ilma duaalset ülesannet vahetult lahendamata, kui esialgne ülesanne on lahendatud simpleksmeetodiga? Viime baasist välja muutuja, mis omab esialgses baasilahendis absoluutväärtuselt suurimat negatiivset väärtust. Saame juhtrea. Otsime juhtveergu leides esimese rea märgitud elementide ja vastavate juhtrea elementide suhted, kus veerg, mis vastab maksimaalsele suhtele, valime juhtveeruks. Seejärel teisendused algses simplekstabelis niikaua kuni on täidetud opitmaalsuse tunnus. Tuleb saada vabaliikmete veergu ja sihifunktsioonile vastavasse kordajate ritta mittenegatiivsed arvud (va. Vabaliige b0).
II krit: Tähistame need veerud, kus juhtrea elemendid on rangelt negatiivsed. Leiame maksimaalse !!"# !"# !"!#!$% !!"# !" !"!#!!" nullinda rea ja juhtrea elementide suhte tähistatud veergudes. =max !!!"#$%&% ; !!!"#$%&% ; ... . Maksimumile vastav veerg võetakse juhtveeruks ja seal olev muutuja tuuakse baasi. Juhtelement on alati negatiivne. Vastuolulisuse krit: Kõik juhtrea elemendid on mittenegatiivsed 14. Duaalülesande koostamine Duaalülesanne koostatakse tavalise LP ülesande põhjal. Sihifunkts kordajad võrduvad lähteülesande paremate pooltega, duaalülesande paremad pooled sihifunkts kordajatega. Kitsenduste maatriks transponeeritakse read lähevad veergudeks. Lühidalt öeldes keeratakse ülesannet 900. Klassikalises
-2 3 4 -5 -2 3 2 - 5 + (-2) -2 -5 0 1 0 4 2 -3 0 4 1 -3 0 4 1 -3 = 2 = 2 = -1 - 2 0 5 -1 -2 0 5 -1 - 2 0 5 9 -4 -8 0 9 -4 -4 0 + 4 9 12 0 - 12 (kolmandast veerust (va lim e kolmandat veergu ( arendame kolmanda saab ette tuua "2" ) juhtveeruks; o lg u juhtelemen - veeru jrgi) ÷2 diks "1"; nullitame kõik elemendid veerus, peale juhtelementi) -2 -5 1 -2 -5 1 2+3 = 2 1 ( -1) -1 - 2 5 = -2 3 - 1 - 2 5 = 9 12 - 12 3 4 -4 (teisest reast saab ette tuua "-1" ) -2 -5 1 + II 2 0 -1 - 9
-1 -2 0 5 -1 -2 0 5 -1 -2 0 5 9 -4 -8 0 9 -4 -4 0 + 4 9 12 0 -12 ( kolmandast veerust (va lim e kolmandat veergu ( arendame kolmanda saab ette tuua "2" ) juhtveeruks; o lg u juhtelemen - veeru jrgi ) ÷2 diks "1" ; nullitame kõik elemendid veerus, peale juhtelementi ) -2 -5 1 -2 -5 1 2 +3 = 2 1 ( -1) -1 -2 5 = -2 3 -1 -2 5 = 9 12 -12 3 4 -4
annaabi.ee 
