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 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
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
.. 0 0 b2 ... ... ... ... ... ... ... ... ... ... ... 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
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 II 1 0 1 I: KONTROLL:
• Baasitabeli optimaalsuse kontrollimine ja simpleksteisendused optimaalse simplekstabeli leidmiseks • Optimaalse simplekstabeli analüüs. 5 Selgub, kas on alternatiivseid lahendeid, saab leida DÜ lahendeid, saab uurida lahendi 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
täidetud eeldused ei primaarse ega ka duaalse simpleksmeetodi rakendamise jaoks. Sel korral rakendatakse algul üht neist meetoditest lihtsustatud kujul, teisel etapil aga teist meetodit eespool kirjeldatud kujul. Kui näiteks rakendada algul duaalset simpleksmeetodit, siis võib pärast juhtrea valimist valida juhtelemendiks esimese negatiivse elemendi juhtreast. Kui aga rakendada algul primaarset simpleksmeetodit, siis võib pärast juhtveeru valimist valida juhtelemendiks selle rea esimese positiivse elemendi. Näide Leida muutujate x1 , x2 , x3 mittenegatiivsed väärtused, mis rahuldavad võrratusesüsteemi x1 x2 x3 1, x1 3 x2 x3 2, x1 2 x2 4 x3 2 mis muudavad maksimaalseks funktsiooni z x1 3x2 4 x3 . Näide (2) Lahendus Korrutame teise ja kolmanda võrratuse arvuga 1:
Baastabel on lubatav kui kõik elemendid b1(vabaliimed) on mittenegatiivsed. Lubatav baastabel on optimaalne, kui baastundamtutele vastavad elemendid sihifukntsiooni reas on 0-d ja ülejäänud selle rea elemendid (-cj) 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.
I krit: Baasi tuuakse muutuja mille ees on 0-ndas reas kõige negatiivsem kordaja see on juhtveerg. ! N: x0-2x1-3x2=0 - -3x2 on 0nda rea 2. veerg. Sellest veerust tuleb leida =min !!!"#$%&% ; !!!"#$%&% ; ... - leitakse iga rea b ja vastava x-kordaja jagatis, millest väikseim ongi ning antud rea, kus see arv asub baasimuutuja viiakse baasist välja, selle asemele tuleb antud juhtveeru element. NB! arvutatakse kordajate absoluutväärtustega. II krit: (on juba tegelikult seletatud eelpool) Baasist viiakse välja see muutuja, mille korral =min. I krit pole kohustuslik, II krit on! Optimaalsuse kriteerium on täidetud kui 0nda rea kõik elemendid on 0. Tehtud arvutuste kontrollimiseks tuleb antud lahendus panna 0. süsteemi. Tõkestamatuse kriteerium: kõik juhtveeru elemendid on 0. 11. Kunstliku baasi meetod, M valimine
annaabi.ee 
