..xn), mis rahuldab kitsenduste süsteemi. Kui kõik kitsenduste süsteemi lahendid on mittenegatiivsed, siis on tegemist lubatava lahendiga ehk plaaniga. Niisugust lubatavate lahendite hulka, mille korral Z on max või min nimetatakse optimaalseks lahendiks ehk optim plaaniks. DUAALÜLESANDED LPÜ teisendamine max-kanoonilisele kujule 1) Kui Z nõutakse miinimumi, siis seda saab esitada max nõudele Min z=max (z´= -z)=-c1x1-c2x2.. 2) Kui kitsendused on esitatud võrratustena, tuleb sisse tuua täiendavad muutujat (abimuutujad, ülejäägi näitajad) 3) Kui mõne muutuja kohta pole esitatud mittenegatiivsuse nõuet, siis seda võib defineerida kahe mittenegatiivse muutuja vahena x2=x2´-x2´´ x2 ≥0, x2´´≥0 LPÜ-ga duaalne ülesanne max-põhikujul LPÜ duaalne ülesanne 1. Esialgse ül igale kitsenduele seame vastavusse duaalse ül tundmatud: y1, y2,..,ym 2
valikust kasutatakse lineaarset planeerimist, ruutplaneerimist, dünaamilist planeerimist, stohhastilist planeerimist jne. Lineaarne planeerimisülesanne. Lineaarne planeerimisülesanne koosneb kolmest põhiosast: 1. Sihifunktsioon, mis lineaarse funktsiooni abil kirjeldab püstitatud eesmärki e. optimaalsuse kriteeriumit, näiteks maksimaalse kasumi saamine, minimaalsed tootmiskulud, maksimaalne kogutoodang rahalises väljenduses, minimaalne omahind jne. f(x) = c1x1 + c2x2 + . . . + cnxn ( max ), kus xk k-nda toote maht, ck k-nda tooteühiku realiseerimisest saadav kasum; 2. Kitsenduste süsteem, mis lineaasete võrrandite või võrratuste abil kirjeldab tootmist piiravaid tingimusi, näiteks piiratud ressursimahud, turupiirangud, minimaalselt vajalikud toodangumahud jne. a11 x1 + a12 x 2 + ... + a1n x n b1 a x + a x + ... + a x b
valikust kasutatakse lineaarset planeerimist, ruutplaneerimist, dünaamilist planeerimist, stohhastilist planeerimist jne. Lineaarne planeerimisülesanne. Lineaarne planeerimisülesanne koosneb kolmest põhiosast: 1. Sihifunktsioon, mis lineaarse funktsiooni abil kirjeldab püstitatud eesmärki e. optimaalsuse kriteeriumit, näiteks maksimaalse kasumi saamine, minimaalsed tootmiskulud, maksimaalne kogutoodang rahalises väljenduses, minimaalne omahind jne. f(x) = c1x1 + c2x2 + . . . + cnxn ( max ), kus xk k-nda toote maht, ck k-nda tooteühiku realiseerimisest saadav kasum; 2. Kitsenduste süsteem, mis lineaasete võrrandite või võrratuste abil kirjeldab tootmist piiravaid tingimusi, näiteks piiratud ressursimahud, turupiirangud, minimaalselt vajalikud toodangumahud jne. a11 x1 + a12 x 2 +... + a1n x n b1 a x + a x +... + a x b
o. kas maksimaalse või minimaalse) väärtuse. Ülesandel on optimaalne lahend siis, kui lubatavate lahendite piirkond sisaldab vähemalt ühte punkti ja sihifunktsiooni muutumise suunas on lahendite piirkond tõkestatud. Samakõrgusjooned- punktide hulk tasandil, millede koordinaadid annavad sihifunktsioonile ühe ja sama väärtuse. Sihifunktsiooni väärtustele z = K (K – const.) vastavaks samakõrgusjooneks on tasandi need punktid, mis rahuldavad seost c0 + c1x1 + c2x2 = K. Sihifunktsiooni erinevate väärtuste K (K = K1 , K2 ,…) korral saame seega samakõrgusjoonteks paralleelsed sirged. Ülesande lahendamisel piisab aga ühe samakõrgusjoone väljajoonistamisest ning seejärel määratakse suund, kuhupoole seda sirget iseendaga paralleelselt nihutades (s.o. tegelikult uusi samakõrgusjooni joonistades) sihifunktsiooni väärtus kasvab (maksimumi leidmise korral) või kahaneb (miinimumi leidmise korral). Lubatavate lahendite
Iga cij näitab vastava lao kauba veo maksumust vastavasse kauplusesse. Ülesandeks on koostada selline vedude plaan, et summaarne vedude maksumus zàmin. x11 vedu I ladu II kauplus. Jne z= x11+4x12+2x13+3x21+5x22+x23 à min x11+x12+x13 =5 ... (vastavad read liidad = a, vastavaad veerud liida = b) xij 0 8. LP ülesande püstitus (kanoonilise kuju teisendamine standardseks ja vastupidi) Standardne kuju: z=c1x1 + ... + cnxn à max a11x1 + ... + a1nxn b1 ... am1x1 + ... + amnxn bm x0 Kasutades vektoreid c, b, x ja m*n-maatriksit A kirjutame ülesande vektorkujul: z = (c,x) à max Ax b, x0. Kanooniline kuju: z=(c,x) àmin Ax = b x0 Standardse ülesande teisendamisel kanooniliseks, lisandub igale reale üks mittenegatiivne muutuja, et
hulka { f0, f1, f2, ... , f15 } · Klass K0 - nulli säilitavate loogikafunktsioonide klass. K0 ={ fi(x1 ,x2 ,..... ,xn ) | fi(0,0,...,0 ) = 0} { f0, f1, f2, f3, f4, f5, f6, f7 } K0 · Klass K1 - ühte säilitavate loogikafunktsioonide klass. K1 ={ fi(x1 ,x2 ,..... ,xn ) | fi(1,1,....,1 ) = 1} { f1, f3, f5, f7, f9, f11, f13, f15 } K1 · Klass Klin - lineaarsete loogikafunktsioonide klass. Klin ={ fi(x1 ,x2 ,..... ,xn ) | fi(x1 ,x2 ,..... ,xn )= c0 c1x1 c2x2 .... cnxn }, kus ci {0,1} Seega iga lineaarse funktsiooni jaoks eksisteerib selline kahendvektor {c0 ,c1, c2, ...., cn }, et funktsioon on esitatav definitsioonis toodud lineaarpolünoomina. Kõikvõimalikest n-argumendi loogikafunktsioonidest on lineaarseid funktsioone 2n+1 . { f0, f3, f5, f6, f9, f10, f12, f15 } Klin · Klass Kd - iseendaga duaalsete funktsioonide klass Kaks loogikafunktsioonid fi(x1 ,x2 ,..... ,xn ) ja fj(x1 ,x2 ,..... ,xn ) on omavahel duaalsed, kui fi(x1 ,x2 ,.
hulka { f0, f1, f2, ... , f15 } Klass K0 - nulli säilitavate loogikafunktsioonide klass. K0 ={ fi(x1 ,x2 ,..... ,xn ) | fi(0,0,...,0 ) = 0} { f0, f1, f2, f3, f4, f5, f6, f7 } K0 Klass K1 - ühte säilitavate loogikafunktsioonide klass. K1 ={ fi(x1 ,x2 ,..... ,xn ) | fi(1,1,....,1 ) = 1} { f1, f3, f5, f7, f9, f11, f13, f15 } K1 Klass Klin - lineaarsete loogikafunktsioonide klass. Klin ={ fi(x1 ,x2 ,..... ,xn ) | fi(x1 ,x2 ,..... ,xn )= c0 c1x1 c2x2 .... cnxn }, kus ci {0,1} Seega iga lineaarse funktsiooni jaoks eksisteerib selline kahendvektor {c0 ,c1, c2, ...., cn }, et funktsioon on esitatav definitsioonis toodud lineaarpolünoomina. Kõikvõimalikest n-argumendi loogikafunktsioonidest on lineaarseid funktsioone 2n+1 . { f0, f3, f5, f6, f9, f10, f12, f15 } Klin Klass Kd - iseendaga duaalsete funktsioonide klass Kaks loogikafunktsioonid fi(x1 ,x2 ,..... ,xn ) ja fj(x1 ,x2 ,....
annaabi.ee 
