lubatava hulga mingis tipus ● Kui lineaarplaneerimise ülesandel leidub optimaalne lahend, siis vähemalt üks neist paikneb lubatava hulga mingis tipus. ● Lineaarplaneerimise ülesande iga lokaalselt optimaalne lahend on ka globaalselt optimaalne 11. Millal on lineaarse planeerimise ülesande optimaalne lahend ühene, millal leiduvad alternatiivsed lahendid? Kuidas seda hinnata graafilise lahendusmeetodi puhul, kuidas simpleksmeetodiga lahendades? Graafiliselt on ühene siis, kui parim nivoojoon omab lubatava hulgaga ainult ühte ühist punkti; Graafiliselt on mitmene siis, kui parim nivoojoon omab aga lubatava hulgaga rohkem kui ühe ühise punkti, siis on olemas ka alternatiivsed optimaalsed lahendid Simpleksmeetodiga on mitmene siis, kui peale Gaussi teisenduste sooritamist süsteemi maatriksi ridade arv (ehk süsteemi lineaarselt sõltumatute võrrandite arv) on väiksem muutujate arvust.
(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 valitakse kõige negatiivsema vabaliikmega rida. Näide Juhtreaks saab teine rida Juhtelemendiks valitakse negatiivne element sellest reast Kui negatiivseid elemente ei ole, on üles-anne vastuoluline Hinnang selle rea negatiivsele elemendile saadakse sihifunktsiooni rea elemendi jagamisel hinnatava elemendiga Duaalne ülesanne Igale LP ülesandele saab seada vastavusse temaga duaalse LP ülesande Duaalse ülesande lahend iseloomustab
c) uurida optimaalse lahendi stabiilsust, kui muutub I tootmisressurss b1 d) kirjutada välja duaalne lahend ja tõlgendada saadud lahendit. 5. Koostada esialgse ülesandega duaalne ülesanne. 6. Lahendada duaalne ülesanne M-meetodiga. Kirjutada välja lahend ja anda tundmatute optimaalsetele väärtustele majanduslik tõlgend 7. Lahendada duaalne ülesanne duaalse simpleksmeetodiga. Kirjutada välja lahend ja anda tundmatute optimaalsetele väärtustele majanduslik tõlgend 1. Püstitada lineaarse planeerimise ülesanne põhikujul: a) Tundmatud x1= teraviljakülvik TV1 x2= teraviljakülvik TV2 b) Kitsendused MAX-põhikuju MAX-kanooniline kuju
1 kg-s söödas S2 on toitaineid K, L ja M vastavalt 1; 3 ja 1 ühikut. Kui palju erinevaid söötasid peab ratsiooni koostamiseks kasutama, et toitainete vajadused saaksid rahuldatud minimaalsete kuludega, kui on teada, et 1 kg sööta S1 maksab 3 € ja 1 kg sööta S2 2 €. 1. Koostada lineaarse planeerimise ülesanne. a. tundmatud b. kitsendused c. sihifunktsioon 2. Lahendada ülesanne duaalse simpleksmeetodiga. 3. Lahendada ülesanne M-meetodil. 4. Kirjutada välja primaarne lahend ja anda tundmatute optimaalsetele väärtustele majanduslik tõlgendus. 1. Koostada lineaarse planeerimise ülesanne. a. tundmatud x1 sööt S1 x2 sööt S2 b. kitsendused K 2x1 + 1x2 >= 14 - x3 + Mx6
olemasolevaid mänguasjade liike. X1 tähendab mängujäneste kogust; neid saab kõige kasumlikum toota koguses 70 tükki. X2 tähendab siilide kogust ja neid on kõige parim toota 189 tükki. X3 on mängukarude kogus ning neid on kõige mõttekam toota 13 tükki (12,5 ümardatud). X4 on rebaste kogus ja neid on parim toota 170 tükki (169,5 ümardatud). 3. Abitundmatute väärtuste analüüs. Kui me lahendaksime seda ülesannet tavaliselt simpleksmeetodiga, siis peaksid esinema ka abitundmatud, mis tähendaksid ressursside ülejääki. Lahendatud Exceliga tabelist on näha, et materjalid puuvillariie, täitematerjal, karusnahk ja plüüs on kasutatud kuni ülemise piiranguni. See tähendab, et ülejääke ei ole ja neli viiendiku abitundmatuid on kõik nullid. Niiti juhul on aga määratud ülejääk, sest et see ei olnud kasutatud lõpuni (801,7m 980-st). Ülejäägi väärtus on siis 980-801,7=178,3 m. Siis abitundmatu x5 väärtus on 178,3.
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. 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
38. Milline seos on lineaarplaneerimise ülesande optimaalsete lahendite ja lubatavate baaslahendite vahel? 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.
1 0 -1 1 1 -1 0 0 200 100 1000 500 w' -142000 w' 142000 ressursside fiktiivne kogumaksumus 142000 7. Lahendada duaalne ülesanne duaalse simpleksmeetodiga. Kirjutada välja lahend ja anda tundmatute optimaalsetele väärtustele majanduslik tõlgend y1+y2+y3>=90 2y1+y2+y4>=105 y1...y4>=0 w=2000y1+1500y2+1200y3+600y4->min duaalne ülesanne tuleb läbi korrutada -1 tuleb lisada abitundmatu, et saa -y1-y2-y3<=-90 -y1-y2-y3+y5=-90
1 0 -1 1 1 -1 0 0 200 100 1000 500 w' -142000 w' 142000 ressursside fiktiivne kogumaksumus 142000 7. Lahendada duaalne ülesanne duaalse simpleksmeetodiga. Kirjutada välja lahend ja anda tundmatute optimaalsetele väärtustele majanduslik tõlgend y1+y2+y3>=90 2y1+y2+y4>=105 y1...y4>=0 w=2000y1+1500y2+1200y3+600y4->min duaalne ülesanne tuleb läbi korrutada -1 tuleb lisada abitundmatu, et saa -y1-y2-y3<=-90 -y1-y2-y3+y5=-90
annaabi.ee 
