(sihifunktsioon kasvab tõkestamatult) Gaussi meetodil arvutatakse lahendi uus esitus, mille baaslahend on lubatav. Uues baaslahendis on sihifunktsiooni väärtus suurem kui eelmise esituse baaslahendis. Kui uue maatriksi sihifunktsiooni reas ei ole enam negatiivseid elemente, on maksimum leitud; kui on, tehakse järgmine samm Duaalne simpleksmeetod Reeglid 1. Kui leidub vähemalt üks negatiivne vabaliige, alustatakse duaalse simpleksmeetodiga 2. Juhtreaks valitakse kõige negatiivsema vabaliikmega rida. Näide Juhtreaks saab teine rida Juhtelemendiks valitakse negatiivne element sellest reast Kui negatiivseid elemente ei ole, on üles-anne vastuoluline Hinnang selle rea negatiivsele elemendile saadakse sihifunktsiooni rea elemendi jagamisel hinnatava elemendiga Duaalne ülesanne Igale LP ülesandele saab seada vastavusse temaga duaalse LP ülesande Duaalse ülesande lahend iseloomustab
simpleksmeetodit. Erinevalt harilikust simpleksmeetodist tuleb duaalse simpleksmeetodi korral valida simplekstabelist esmalt välja juhtrida, ja seejärel juhtveerg ning viia siis läbi tabeli ridade teisendus. Kui simplekstabel ei ole lubatav, siis peab vähemalt üks bk 0. Juhtrida uuele simplekstabelile üleminekuks valitakse selliste ridade seast, kus bk 0. Duaalse simpleksmeetodi samm. Kui selliseid ridu on rohkem kui üks, siis kasutatakse üht kahest reeglist: 1) juhtreaks valitakse alati esimene rida, kus bk 0; 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 |
1 0 1/4 - 1/4 0 2 reas ei esine negatiivseid elemen 0 1 1/4 3/4 0 3 0 0 - 1/2 - 1/2 1 1 Z 17 x1 2 x2 3 Alustatakse teisendusi reast, kus vabaliikme ja esimese positiivse kordaja suhe on kõige väiksem. Siin juhtreaks on 1. rida. Teostatakse simleksteisendused: Juhtrea elemendid jagatakse juhtelemendiga. Saadud uue rea abil teisendatakse ülejäänud juhtveeru elemendid nullideks, mille tulemusena saadakse uus baasilahend, milles sihifunktsiooni väärtus on suurem, kui eelmises baasilahendis. n optimaalne, kui sihifunktsiooni ne negatiivseid elemente. z 2 x1 3x2 max x2
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. Juhtelement asub juhtrea ja juhtveeru ristumiskohal. 5. Uue tabeli väärtuste arvutamine ehk uue lubatava lahendi leidmine toimub simpleksteisendustega, mille aluseks on Gauss-Jordani elimineerimisvõte. Selleks: * kõik juhtrea elemendid jagatakse juhtelemendiga, mille tulemusena uues tabelis juhtelement saab väärtuseks +1 ;
on mittenegatiivsed Baasmuutujad- muutujad, mis on baastabelis ühikveergude kohal Vabad muutujad-ülejäänud muutujad, mis ei asu ühikveergude kohal. Põhireeglid simpleksteisendusteks: 1) Juhtveeru valik. Valitakse veerg, kus 0-nda rea kordaja on negativne ja soovitatavalt absoluutväärtuselt suurim. 2) Arvutatakse juhtveeru kõikide positiivsete elementide aij alusel suhe bi/aij (i=1,2..m) 3) Valitakse juhtrida. Juhtreaks on rida, kus suhe bi/aij on väikseim. 4) Juhtelement, mis ümbiritsetakse rõngakesega. 5) Juhtteisendused. Juhtveerg tuleb teisendada ühikveeruks, juhtlement võrdub veerus 1ga, ülejäänud elemendid on 0id. Lahendi stabiilsuse analüüs ehk teeme kindalsk, millistes piirides võib muuta esialgse sihifunktsiooni kordajaid cj (millistes piirides nad vüivad muutuda), et leitud optimaalne lahend oleks ka uue sihifunktsiooni kordajaga ülesande optimaalseks lahendiks.
13. Duaalne simpleksmeetod, kitsenduste vastuolulisus Simpleksmeetodit saab kasutada vaid, kui b0, Kui vähemalt üks parem pool on väikse 0st, tuleb ülesanne lahedada duaalse simpleksmeetodiga. Tavalise simpleksmeetodi kirjelduses tuleb asendada sõnad "rida" ja "veerg", "positiivne" ja "negatiivne", "minimaalne" ja "maksimaalne". I krit: Baasist viiakse välja see negatiivne muutuja, millel on suurim absoluutväärtus. Vastavat rida nimetatakse juhtreaks. Sihifunktsioonile vastavat muutujat x0 ei viida kunagi baasist välja. Optimaalsuse krit on täidetud kui kõik baasimuutujad peale x0 on mittenegatiivsed ja kehtib tavalise simpleksmeetodi optimaalsuse krit (0nda rea kordajad on mitteneg). II krit: Tähistame need veerud, kus juhtrea elemendid on rangelt negatiivsed. Leiame maksimaalse !!"# !"# !"!#!$% !!"# !" !"!#!!"
annaabi.ee 
