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 Duaalne simpleksmeetod Reeglid 1. Kui leidub vähemalt üks negatiivne vabaliige, alustatakse duaalse simpleksmeetodiga 2. Juhtreaks...
Kui palju erinevat tüüpi teraviljakülvikuid peab firma tootma, et saada nende valmistamisest maksimaalset kasum kui teraviljakülviku TV1 tootmine annab kasumit 90 eurot ja teraviljakülviku TV2 tootmine 120 eurot? 1. Püstitada lineaarse planeerimise ülesanne põhikujul: a) tundmatud b) kitsendused c) sihifunktsioon 2. Koostada algsimplekstabel ülesande lahendamiseks simpleksmeetodil. 3. Lahendada ülesanne simpleksmeetodil. 4. Optimaalse lahendi analüüs: a) leida primaarne lahend ning anda tundmatute optimaalsetele väärtustele majanduslik tõlg b) uurida optimaalse lahendi stabiilsust, kui muutub teise toote kasum c2 c) uurida optimaalse lahendi stabiilsust, kui muutub I tootmisressurss b1 d) kirjutada välja duaalne lahend ja tõlgendada saadud lahendit.
ühe toote M1 tootmiskulu on 50 € ja toodet müüakse hinnaga 100 € tükk ja ühe toote M2 tootmiskulu on 60 € ja müüakse hinnaga 80 € tükk. 1. Püstitada lineaarse planeerimise ülesanne põhikujul: a) tundmatud b) kitsendused c) sihifunktsioon 2. Koostada esialgse ülesandega duaalne ülesanne. 3. Koostada algsimplekstabel ülesande lahendamiseks simpleksmeetodil. 4. Lahendada ülesanne simpleksmeetodil. 5. Analüüsida optimaalset lahendit: a) leida primaarne lahend ning anda tundmatute optimaalsetele väärtustele majanduslik tõlgendus; b) leida duaalne lahend ning anda tundmatute optimaalsetele väärtustele majanduslik tõlgendus; c) uurida optimaalse lahendi stabiilsust, kui muutub esimese toote kasum c 1; d) uurida optimaalse lahendi stabiilsust, kui muutub III tootmisressurss b 3. 1
materjal x1+x2<=1500 nõudlus x1<=1200 x1 +2X2 <= 2000 x2<=600 X1+X2 <= 1500 teneg.nõue x1>=0,x2>=0 X1 <= 1200 X2<=600 c) sihifunktsioon F = 90x1 + 105x2 -> max F=90X1+105X2->MAX x1, x2 >= 0 2. Koostada algsimplekstabel ülesande lahendamiseks simpleksmeetodil. x1 x2 x3 x4 x5 x6 bi 1 2 1 0 0 0 2000 1 1 0 1 0 0 1500 1 0 0 0 1 0 1200 0 1 0 0 0 1 600
materjal x1+x2<=1500 nõudlus x1<=1200 x1 +2X2 <= 2000 x2<=600 X1+X2 <= 1500 teneg.nõue x1>=0,x2>=0 X1 <= 1200 X2<=600 c) sihifunktsioon F = 90x1 + 105x2 -> max F=90X1+105X2->MAX x1, x2 >= 0 2. Koostada algsimplekstabel ülesande lahendamiseks simpleksmeetodil. x1 x2 x3 x4 x5 x6 bi 1 2 1 0 0 0 2000 1 1 0 1 0 0 1500 1 0 0 0 1 0 1200 0 1 0 0 0 1 600
tundmatud omada igasuguseid väärtusi (ka negatiivseid). Iga ülesanne duaalsete ülesannete paarist kujutab formaalselt endast iseseisvat ülesannet ja teda on võimalik lahendada teisest paari kuuluvast ülesandest sõltumatult. Kuid leides ühele ülesandele duaalsete ülesannete paarist optimaalse lahendi, on see hõlpsasti väljaloetav ka teisele samasse paari kuuluvale ülesandele. Et leida duaalse ülesande lahendit, lahendatakse esialgne ülesanne nt. simpleksmeetodil. Kui esialgsele ülesandele üldse on leitav optimaalne lahend, siis mingi lõpliku arvu sammude tulemusena saadakse lõppsimplekstabel, kust on leitavad ka duaalse ülesande optimaalsed lahendid (asuvad sihifunktsiooni reas abitundmatute veergudes). Kui tegemist on nn. tootmisplaani leidmise ülesandega (kasumi maksimeerimine piiratud ressursside tingimustes), siis duaalse ülesande tundmatute yi väärtused väljendavad täiendavat kasumit, mida oleks võimalik saada, kui i-ndat ressurssi
sirged tõusuga c 2 • optimaalse lahendi leidmine LPÜ graafilisel lahendamisel 1. lahend puudub, kui lubatav piirkond on tühi (vasturääkivad kitsendused, lubatavate lahendite piirkond on tõkestamata) 2. Alternatiivne lahend- mitu erinnevat muutujate väärtuste kombinatsiooni, mis annavad Z-ile optimaalse väärtuse 3. Lõpmata palju lahendeid SIMPLEKSMEETOD Kui kanoonilisel kujul antud ülesanne sisaldab n tundmatut ja m võrrandit, siis simpleksmeetodil leitud lahendis võivad nullist erineda mitte rohkem kui m (kitsenduste arv) tundmatu väärtust, mida nimetatakse lahendielementideks. Simplekstabelit nimetatakse baasitabeliks, kui tabeli elementide aij (kitsenduste kordajad) osas on vähemalt m erinevat ühikveergu ning nendes veergudes sihifunktsiooni reas on nullid. Ühikveerus erineb nullist vaid üks element, mis võrdub 1-ga. Muutujad, mis on
Piima on kohvikus 80 liitrit, espressot saab teha kuni 60 liitrit. CoffeLatte hind on kohvikus 15 raha, Cappuccino hind 10 raha. Mida näitavad kanoonilise kuju lisamuutujad antud ülesandes? Vali üks: a. CoffeeLatte ülejääki ja Cappuccino ülejääki b. Piima ja espresso puudujääki c. piima ülejääki ja espresso ülejääki d. CoffeeLatte puudujääki ja Cappuccino puudujääki e. Raha ülejääki Tagasiside Kanooniline kuju on vajalik vaid simpleksmeetodil ülesannete lahendamisel! Õige vastus on: piima ülejääki ja espresso ülejääki . Küsimus 2 Väär 0,00 punkti 1,00-st Küsimuse tekst Kas antud ülesandel on alternatiivseid lahendeid? x1 x2 x3 x4 VL SF 0 0 0 2 100 1k 1 2 0 -4 22 2k 0 -0,5 1 1 12 Vali üks: a. Ei, sest tabelis leidub negatiivseid arve b. Ei, sest ülesandel puuduvad lahendid c
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 Simpleksmeetodiga LP ülesande lahendamine käib kahe kriteeriumi järgi.
annaabi.ee 
