2y1+y2+y4-y6=105 w=2000y1+1500y2+1200y3+600y4->min w'=-2000y1-1500y2-1200y3-600y4->max võrratussüsteemi lahend, y1+y2+y3-y5+y7=90 2y1+y2+y4-y6+y8=105 sihifunkts. w=2000y1+1500y2+1200y3+600y4+My7+My8->min w'=-2000y1-1500y2-1200y3-600y4-My7-My8->max w+2000y1+1500y2+1200y3+600y4+My7+My8=0 juhtveerg y1 y2 y3 y4 y5 y6 1 1 1 0 -1 0 2 1 0 1 0 -1 2000 1500 1200 600 00 -28000 -18500 -8800 -9400 10000 10000
2y1+y2+y4-y6=105 w=2000y1+1500y2+1200y3+600y4->min w'=-2000y1-1500y2-1200y3-600y4->max võrratussüsteemi lahend, y1+y2+y3-y5+y7=90 2y1+y2+y4-y6+y8=105 sihifunkts. w=2000y1+1500y2+1200y3+600y4+My7+My8->min w'=-2000y1-1500y2-1200y3-600y4-My7-My8->max w+2000y1+1500y2+1200y3+600y4+My7+My8=0 juhtveerg y1 y2 y3 y4 y5 y6 1 1 1 0 -1 0 2 1 0 1 0 -1 2000 1500 1200 600 00 -28000 -18500 -8800 -9400 10000 10000
maxcT x : Ax b, x 0. Lubatavate lahendite hulk on kirjapandav kujul R x : Ax b, x 0 . Duaalne simpleksmeetod. Kui aga simplekstabel ei ole lubatav, kuid on duaalselt lubatav, siis tuleb optimaalse lahendi leidmiseks kasutada duaalset 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 |
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
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 muutujate väärtuste komplekti, mis annavad Z-ile suurima (vähima) väärtuse,
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. Tuleb teha järgmist: 1)lisada optimaalse baasitabeli sihifunktsiooni reas k-ndas veerus seisvale arvule suurus –ek
N: z= 2x1+3x2àmax à x0-2x1-3x2=0 · Igale järgmisele reale (kitsendustele) liidetakse simpleksmuutuja ning pannakse võrduma algse b-ga. N: x1+x24 à x1+x2+x3=4 · Saadakse baasimuutujad N: Antud näites x0=0, x3=4, x1=x2=0 Simpleksmeetodiga LP ülesande lahendamine käib kahe kriteeriumi järgi. 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.
annaabi.ee 
