am1 am 2 amn xn bm cn võime lineaarse planeerimise ülesande kirjutada maatrikskujul 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;
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. Mida näitavad simpleksmeetodi puhul lisamuutujate optimaalsed väärtused? See näitab ülejääki 17. Millised on duaalse simpleksmeetdi puhul juhtveeru ja juhtrea valiku reeglid? Juhtrida - Kõige väikseima absoluutväärtusega negatiivne vabaliige Juhtveerg - juhtrea elemendi ja sihifunksiooni elemendi maksimaalne jagatis, ainult kus juhtrea element on negatiivne 18. Mis on optimaalsuse tunnus duaalse simpleksmeetodi kasutamise korral?
Kui x* ei ole ühene, siis on vähemalt 2 hulga Q tippu optimaalsed lahendid. Sellel teoreemil põhineb teine graafilise lahendamise meetod. x1, x2, ..., xs on hulga Q tipud. Teoreem 2 järgi, saab teisendada: z=(c,x)=1(cx1)+...+ s(cxs) 1(cxk)+...+ s(cxk)=(1+...+s)cxk=1*cxk=cxk. xk on selline tipp, milles cx saavutab miinimumi. Iga xQ, (c,x)(c,xk). Tipp xk on ühene optimaalne lahend. 10. Simpleksmeetodi kirjeldus (krit I ja II põhjendus, tõkestamatus) Simpleksmeetodil lahendatakse LP ülesannet järgmiselt: · Nullindale reale lisatakse x0, millest lahutatakse algse z-muutujad ning pannakse see võrduma 0ga. 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
Karamell g 6 9 mitte rohkem kui 18 kg Pähkel g - 9 vähemalt 4,5 kg Kasumit planeeritakse saada šokolaadi Juku valmistamisest 13 senti ja Miku tootmisest 18 senti. Kui palju erinevat sorti šokolaade tuleb firmal valmistada, et maksimeerida kasum? 1. Koostada lineaarse planeerimise ülesanne. 2. Lahendada ülesanne kasutades sobivat simpleksmeetodi algoritmi (klassikaline simpleksmeetod, M-meetod või duaalne simpleksmeetod). 3. Kirjutada välja primaarne lahend ja anda tundmatute optimaalsetele väärtustele majanduslik tõlgendus. 1. Koostada lineaarse planeerimise ülesanne. x1 juku valmistamine x2 miku valmistamine
neerimise ülesanne. kitsendused sihifunktsioon nete segu M1 tootmine sool 12x1+6x2<=24000 kasum ainete segu M2 tootmine pipar 6x1+9x2<=18000 F=15x1+12x2->max tsilli 3x2>=4500 x1,x2>=0 asutades sobivat simpleksmeetodi algoritmi eetod, M-meetod või duaalne simpleksmeetod). max-kanooniline kuju lisan fiktiivse tundmatu x6 12x1+6x2+x3<=24000 12x1+6x2+x3<=24000 6x1+9x2+x4<=18000 6x1+9x2+x4<=18000 3x2-x5>=4500 3x2-x5+x6>=4500 x1...x5>=0 x1...x6>=0
2. rida a21 a22 ... a2n 0 1 ... 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
neerimise ülesanne. kitsendused sihifunktsioon nete segu M1 tootmine sool 12x1+6x2<=24000 kasum ainete segu M2 tootmine pipar 6x1+9x2<=18000 F=15x1+12x2->max tsilli 3x2>=4500 x1,x2>=0 asutades sobivat simpleksmeetodi algoritmi eetod, M-meetod või duaalne simpleksmeetod). max-kanooniline kuju lisan fiktiivse tundmatu x6 12x1+6x2+x3<=24000 12x1+6x2+x3<=24000 6x1+9x2+x4<=18000 6x1+9x2+x4<=18000 3x2-x5>=4500 3x2-x5+x6>=4500 x1...x5>=0 x1...x6>=0
annaabi.ee 
