Graafiliselt on lahent tõkestamata juhul, kui mistahes lubatavat lahendit on võimalik parandada (ehk lõpmatus). 13. Milline seos on lineaarse planeerimise ülesande optimaalsete lahendite ja lubatavate baasilahendite vahel? Optimaalsed lahendid lineaarse planeerimise ülesande puhul on lubatavad baasilahendid kanoonilisel kujul (simpleksmeetidiga) 14. Millised on simpleksmeetdi puhul juhtveeru ja juhtrea valiku reeglid? Juhtveerg - sihifunksiooni kõige suurema absoluutväärtusega negatiivne arv Juhtrida - vabaliikmete ja juhtveeru elemendi minimaalne jagatis min(Va / Je) 15. Milline on simplekstabeli optimaalsuse tunnus? kui simplekstabelis sihifunktsioonile vastavas kordajate reas puuduvad negatiivsed kordajad, siis vastav baaslahend on optimaalne ja vabaliige sihifunktsioonile vastavas kordajate reas annab sihifunktsiooni optimaalse väärtuse 16
ü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. 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:
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 lubatavat hulka, ja nimelt sealt, kus sihifunktsiooni väärtus on suurem tema väärtusest lubatavate lahendite hulgas.
lubatavate baaslahendite hulgast valitakse välja tipp, milles sihifunktsiooni väärtus on suurim kui lähtetipus, vastav baaslahend ongi optimaalne lahend 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).
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 I : x1 x2 4 II : x2 2 x0 I grad
"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 !!"# !"# !"!#!$% !!"# !" !"!#!!" 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.
+ 4(-1) 2 5 1 = 4 - 6 1 Lihtsustamisel on soovitav kasutada järgmist algoritmi. 1. Valida determinandis juhtrida või veerg( soovitavalt selline, milles leidub element 1 või -1 ja mille ülejäänud elemendid oleks võimalikult väikesed; 2. valida juhtreast või veerust juhtelement, mille abil teisendatakse kõik ülejäänud juhtrea või veeru elemendid nullideks( kasutades omadusi 7 ja 8); 3. arendada determinant, kasutades teoreemi. Märkus: Kui determinandis ei esine arve 1 või -1, siis kasutatakse eelteisendust, mille tulemusena saadakse sobivad arvud. Näide: -3 7 -1 4 - 1 12 0 6 - 1 12 6 - 1 12 2 5 -9 2 7 1 - 19 0 3
stabiilsust- millistes piirides võivad LPÜ andmed muutuda, et lahendi optimaalsus säiliks. Põhireeglid simpleksteisendusteks 1. Juhtveeru valik (0-nda rea kordaja on negatiivne ja absoluutväärtuselt suurim) bi 2. Arvutatakse juhtveeru kõikide positiivsete elementide aij alusel suhe aij 3. Valitakse juhtrida (rida, kus suhe on kõige väiksem ↑) 4. Juhtveeru ja juhtrea lõikepunktis on juhtelement, ümbritsetakse rõngakesega 5. Tehakse juhtteisendusi. Eesmärgiks teisendada juhtveerg ühikveeruks, sealjuures juhtelemen võrdub ühikveerus 1-ga. Selleks jagatakse juhtrida läbi juhtelemendiga ning seejärel teisendatakse juhtveerg ühikveeruks (juhelement =1, ülejäänud 0). Lahendi analüüs: Kas leidub ka teisi optimaalseid lahendeid. Kui on mitu baaasilahendile vastavate
2 5 1 4 -6 1 + 4(-1) = Lihtsustamisel on soovitav kasutada järgmist algoritmi. 1. Valida determinandis juhtrida või veerg( soovitavalt selline, milles leidub element 1 või -1 ja mille ülejäänud elemendid oleks võimalikult väikesed; 2. valida juhtreast või veerust juhtelement, mille abil teisendatakse kõik ülejäänud juhtrea või veeru elemendid nullideks( kasutades omadusi 7 ja 8); 3. arendada determinant, kasutades teoreemi. Märkus: Kui determinandis ei esine arve 1 või -1, siis kasutatakse eelteisendust, mille tulemusena saadakse sobivad arvud. Näide: - 3 7 -1 4 - 1 12 0 6 5 -9 2 7 1 - 19 0 3 - 1 12 6 - 1 12 2 2 5 1 2 2 5 1 2 1 - 19 3 1 - 19 1
+ 4(-1) 2 5 1 = 4 -6 1 Lihtsustamisel on soovitav kasutada järgmist algoritmi. 1. Valida determinandis juhtrida või veerg( soovitavalt selline, milles leidub element 1 või -1 ja mille ülejäänud elemendid oleks võimalikult väikesed; 2. valida juhtreast või veerust juhtelement, mille abil teisendatakse kõik ülejäänud juhtrea või veeru elemendid nullideks( kasutades omadusi 7 ja 8); 3. arendada determinant, kasutades teoreemi. Märkus: Kui determinandis ei esine arve 1 või -1, siis kasutatakse eelteisendust, mille tulemusena saadakse sobivad arvud. Näide: -3 7 -1 4 -1 12 0 6 -1 12 6 5 -9 2 7 1 -19 0 3
17. Valida maatriksis A juhtrida või veerg (soovitavalt selline, milles leidub element ,,1" või ,,-1" ja mille ülejäänud elemendid on absoluutväärtuse poolest võimalikult väikesed); 18. Valida juhtreast või veerust juhtelement (soovitavalt 1 või -1; kui sellist elementi maatriksis ei ole , võib selle sinna teisendada kasutades omadusi 4 ja 6); 19. Teisendada omaduste 4 ja 6 abil juhtrea või -veeru kõik elemendid peale juhtelemendi nullideks; 20. Arendada determinant kasutades omadust 10 (determinandi arendusteoreem); 21. Kui arendamisel tekib teist või kolmandat järku maatriksi determinant, siis võib selle välja arvutada mittearendadaes determinanti, suuremat järku maatriksi determinandi arvutamisel korratakse algoritmi.
Valida maatriksis A juhtrida või veerg (soovitavalt selline, milles leidub element ,,1" või ,,-1" ja mille ülejäänud elemendid on absoluutväärtuse poolest võimalikult väikesed); 2. Valida juhtreast või veerust juhtelement (soovitavalt 1 või -1; kui sellist elementi maatriksis ei ole , võib selle sinna teisendada kasutades omadusi 4 ja 6); 3. Teisendada omaduste 4 ja 6 abil juhtrea või -veeru kõik elemendid peale juhtelemendi nullideks; 4. Arendada determinant kasutades omadust 10 (determinandi arendusteoreem); 5. Kui arendamisel tekib teist või kolmandat järku maatriksi determinant, siis võib selle välja arvutada mittearendadaes determinanti, suuremat järku maatriksi determinandi arvutamisel korratakse algoritmi.
annaabi.ee 
