Lineáris tér: olyan halmaz, amelyben értelmezve van:
- összeadás és a skalárral való szorzás és ez a halmaz zárt erre a két műveletre nézve,
- az összeadás és a skaláris szorzás a halmaza zárt halma, mindkettő kommunitatív, komponens, asszociatív, disztributív
- minden elemnek van ellentetje
- minden a-ra igaz, hogy szorozva 1-gyel önmagát adja
Zárt halmaz: természetes szám zárt az összeadásra nézve, mert ha 2 elemét összeadom, akkor természetes számot kapok
Lineáris tér altere: - a lineáris tér olyan részhalmaza, amely maga is lineáris teret alkot – a lineáris tér alterének nevezzük, azaz ez a halmaz-altér is zárt az összeadásra-skaláris szorzásra, valamint igazak rá a műveleti tulajdonságok is pl. 3 komponensű vektorok altere
- az összes olyan 3 komponensű vektor, melynek 3 komponense 0
Lineáris függetlenség és összefüggés: 0 vektor hogyan állítható elő tetszőleges vektor lineáris kombinációjából?
1. Állítsuk elő 0 vektort a (121), (3-10), (215) vektorok lineáris kombinációjából – szorozva mindegyik 0-val = (000)
2. Ha tetszőleges számú lamda1xa1+lambd2xa2+….lambdanxan=0 vektoregyenlet mindig megoldható, ennek egy triviális megoldása, ha lambda1=lambda2=…lambdan=a
3. Az a1,a2,……an vektorrendszer lineárisan független, ha a 0 vektor csak triviális módon állítható elő ezek lineáris kombinációjaként
4. Az a1,a2,…….an vektorrendszer lineárisan összefüggő, ha a 0 vektor nem csak triviális módon lehet előállítani a vektorok lineáris kombinációjaként.
Kis a1=(300) a2=(0-24) a3=(005) a 0 vektor előállítása a1,a2,a3 lineáris kombinációjaként
lambdaa1+lambda2a2+lambda3a3=0
Tehát a1,a2,a3 lineárisan független, csak triviális megoldása van az egyenletrendszernek.
Tétel:
5. Az a1,a2,….an vektorrendszer összefüggő, ha a vektorok között 0 vektor van
6. Ha a vektorok között vannak egyenlőek pl.: a1=(121) a2=(121)
7. Ha a b vektor előállítható a1,a2,…an vektorrendszer lineáris kombinációjaként, akkor a1,a2,…….an b vektor lineárisan összefüggő
8. Ha a1,a2,…..an vektorrendszer lineárisan összefüggő, akkor van a vektorok között olyan, ami előáll a többi lineáris kombinációjaként
9. Ha a1,a2,…an lineárisan független, akkor a vektorrendszer bármely nem üres részhalmaza is lineárisan független
Vektorrendszer rangja:
D. Az a1,a2,…an vektorrendszer rangja r, ha a vektorok közül legfeljebb r db lineárisan független vektort lehet kiválasztani
Megjegyzés: bármely r+1 db kiválasztott vektor lineárisan összefüggő
Tétel:
1. Az a1,a2,…an vektorrendszerhez olyan vektort csatolunk, amely előáll ezek lineáris kombinációjaként, akkor a vektorrendszer rangja nem változik
2. Ha az a1,a2,…an vektorrendszerből olyan vektort veszünk el, amely előáll ezek lineáris kombinációjaként, akkor a vektorrendszer rangja nem változik.
3. Az a1,a2,…an vektorrendszer rangja r, akkor a vektorrendszer bármely vektora előállítható a vektorrendszerből kiválasztott r számú független vektor lineáris kombinációjaként
Generátor rendszer:
L3=3 komponensű vektorok halmaza – keresünk 1 olyan vektorhalmazt, amellyel L 3 bármely vektora előállítható
D.: Az a1,a2,…an generátor rendszere az L lineáris térnek, ha L bármely vektora előállítható ezek lineáris kombinációjaként
Bázis:
D.: Az L lineáris tér lineárisan független vektorból álló generátor rendszerét L bázisnak hívjuk
Megjegyzés: az a1,a2,…an bázisát alkotja L-nek, akkor L bármely vektora egyértelműen állítható elő ezek lineáris kombinációjaként pl. L3-nak bázis egy triviális /legegyszerűbb/ bázisa az egységvektorokból előállítható
Mátrix rangja:
- a mátrix sorvektor rendszerének és oszlopvektor rendszerének rangja megegyezik
- a sorvektor rendszerének és oszlopvektor rendszernek közös rangjával egyenlő
- A nxm mátrix rangja = a lineárisan független oszlopvektorok db szám rang A<=m
- Minden nem zérus mátrixhoz egyértelműen hozzárendelhető egy természetes szám – ez a mátrix rangja
- Nxm típusú mátrix rangja nem lehet nagyobb sem sorai, sem oszlopai számánál
- Zérusmátrix rangja 0 – ha egy mátrix rangja 0, akkor abból következik, hogy a mátrix zérusmátrix.
- D. ha az (n+n) kvadratikus (ugyanannyi oszlop/sor) mátrix rangja n, akkor a mátrixot regulárisnak (nem szimulárisnak) mondjuk – ekkor a sorai, ill. oszlopai lineárisan függetlenek
- Ha az (nxn) kvadratikus mátrix rangja kisebb, mint n, akkor a mátrix szimuláris – ekkor a mátrix sorai-oszlopai lineárisan összefüggőek
Mátrix lineáris kombinációja: ha az A1,A2,……An azonos típusú mátrixokat rendre megszorozzuk a k1,k2,…….kn számokkal és a szorzatokat összeadjuk, akkor az így kapott k1A1+k2A2+…+knAn=L mátrixot az adott mátrix lineáris kombinációjának nevezzük+*9/
Mátrix jobboldali inverze: Az A*x=E mátrixegyenlet minden x mátrix megoldását, ha létezik az A mátrix jobboldali inverzének nevezzük
Az A mátrixnak akkor van jobboldali inverze, ha sorai lineárisan függetlenek.
Mátrix baloldali inverze: az Y*A=E mátrixegyenlet minden Y mátrix megoldását, ha létezik az A mátrix baloldali inverzének nevezzük
Az A mátrixnak akkor van baloldali inverze, ha oszlopai lineárisan függetlenek.
Mátrixok fajtái:
1. Zérusmátrix: minden eleme 0
2. Diagonálmátrix: az olyan négyzetes mátrix, melynek csak a bal felső sarokból a jobb alsó sarokba húzott átlójában – főátlóban – van 0-tól különböző eleme
3. Egységmátrix: Melynek főátlójában minden eleme 1-gyel egyenlő
Egységvektor: azokat az oszlopkat, melyeknek eleme 0, a többi zérus
4. Összegező vektor: az az oszlop- vagy sormátrix, melynek minden eleme 1
5. Permutáló mátrix: az a négyzetes mátrix, mely az egységmátrixból az oszlopok vagy sorok más sorrendű leírásával – permutálásával – kapható – a permutáló mátrix minden sora és oszlopa egy-egy 1-est tartalmaz, a többi eleme 0.
6. Háromszögmátrix: az olyan négyzetes mátrix, melynek főátlója alatt vagy fölött csupa 0 elem áll.
7. Komplex mátrix: ha elemei között komplex számok is előfordulnak
8. Kontinuánsmátrix: olyan négyzetes mátrix, mely csak a főátlóban és a főátlóval párhuzamos két szomszédos átlóban tartalmaz zérustól különböző elemeket
Az nxn-es kvadratikus mátrixnak akkor és csak akkor van bal-, ill. jobboldali inverze, ha sorai és oszlopai lineárisan függetlenek – ekkor bal- és jobboldali inverze megegyezik. A*A-1=E , A-1*A=E
Elemi bázistranszformáció = BTR: egy adott bázisból egy más bázisra térünk át egyetlen vektor kicserélésével, s vizsgáljuk, hogy hogyan változik a vektorok koordinátája a BTR során
Tétel: c azon vektorok helyére vihető be a bázisba, amelyeknél a c vektor előállításában az együtthatója nem 0
Lépései:
- generátor elemnek vesszük a reciprokát
- generátor elem sorában az elemeket osszuk a generátor elemmel
- generátor elem oszlopában osztunk a generátor elem x-1-gyel
- a többi elemre az un. téglalapszabályt alkalmazzuk
- téglalapszabály:
b c
h i – i generátor elem
b-(hxc/i) – az új érték
megjegyzés:
1. ha a generáló elem sorában 0 van, akkor a 0 oszlopa változatlan marad.
2. Ha a generáló elem oszlopában 0 van, akkor a 0 sora másolható
3. Amelyik sorból egyszer már választottam generáló elemet, azt többen nem választhatom
Kompatibilitás vizsgálat:
D. a c vektor kompatíbilis a b1,b2,b3,……..bn vektorrendszerben, ha c vektor előállítható a b1,b2,……..bn vektorok lineáris kombinációjaként
1. határozzuk meg, hogy c1,c2 vektorok kompatibilisek-e a b1,b2,b3 vektorrendszerrel
2. c1 vektor előállításához szükséges e1 vektor is, azaz b1,b2,b3 lineáris kombinációjaként nem lehet előállítani, ezért c1 nem kompatíbilis b1,b2,b3 vektorrendszerrel
3. egyenletrendszer megoldása elemi bázistranszformációval
4. vizsgáljuk meg, hogy a1 vektor hogyan állítható elő b1,b2,b3 vektorok lineáris kombinációjaként
5. az egyenletrendszer megoldásának leolvasása a végtábla segítségével
Szabadságfok: az egyenletrendszer szabadságfoka a szabad ismeretlenek számával egyenlő
Megjegyzés: az együttható mátrix rangja a kötött ismeretlenek számával egyezik meg
Általános megoldás: a bázisba bevitt x ismeretlen = a b vektor oszlopában lévő értékből a sorában lévő, a bázisba be nem vitt x értékek szorzatával
Bázismegoldás: szabad ismeretleneket 0-nak választjuk
Partikuláris megoldás: megadott x1,x2,..xn értékek behelyettesítése az általános megoldás képleteibe
Tétel:
1. Az egyenletrendszernek nincs megoldása, ha b oszlopvektor nem állítható elő az együttható mátrix oszlopainak lineáris kombinációjaként
1. Ha van megoldása és az együttható mátrix oszlopai lineárisan függetlenek, akkor egyértelmű megoldása van
2. Ha van megoldás és az együttható mátrix oszlopvektorai lineárisan összefüggőek, akkor végtelen sok megoldás van
Konvex halmaz: bármely 2 pontját összekötő szakasz pontjai eleme a halmaznak
Konvex halmaz belső pontja: ha van a pontnak olyan epszilon sugarú környezete, melynek minden pontja eleme a halmaznak
Határpont: bármely epszilon sugarú környezetében van halmazbeli és nem halmazbeli pont
Csúszpont – extremális pont: nincs a halmaznak olyan szakasza, amelynek ez felezőpontja lenne
Zárt a halmaz: Ha a halmazhoz a határpontok is hozzátartoznak
Korlátos a halmaz: ha van olyan hosszúságú szakasz, amely már nem fér bele a halmazba
Konvex poliéder-sokszög: - zárt: határpontok hozzátartoznak
- korlátos, véges sok extremális csúcspontja van, konvex
Origo próba: (0,0) pontokat behelyettesítem az egyenletbe, ha a kapott eredmény megfelel az egyenletnek, akkor L a lehetséges megoldások halmaza
Megjegyzések:
1 Az azonos célértéket adó pontok egy egyenesen helyezkednek el
2. A különböző célértéket adó egyenesek egymással párhuzamosak
3. A célérték maximuma egy extramális pontban van
Lineáris egyenlőtlenségrendszer:
Megoldás lépései:
1. meghatározzuk a lehetséges megoldások halmazát
2. L-en / L halmazban / kerestük azt a pontot, amelynél a célfüggvény max értéket vesz fel – ezt a megoldást optimális megoldásnak nevezzük
3. Ha az együtthatók azonosak két egyenesnél az egyenesek párhuzamosak lesznek
4. Párhuzamos egyenesek: ha x1,x2 értékei megegyeznek
5. Ha 0 az adott egyenlet eredménye egy pontot helyettesítek be
Z1max: a célfüggvény nem korlátos a lehetséges megoldások halmazán, s nincs optimális megoldása – végtelen
Optimális megoldás: a kiválasztott szakaszok bármely pontja
- a szakasz pontjainak koordinátái a végpontok konvex lineáris kombinációja
Minimum érték: az optimális megoldást adó pontok az egyik egyenesen helyezkednek el
Maximum érték: egy c kezdőpontú félegyenes az e3 egyenesen
Lineáris programozási LP feladat:
1. Az LP feladat optimális megoldása valamelyik bázismegoldás
2. Az LP feladat bázismegoldásai extremális pontok
Megoldási lépések:
1. Generátor elem választása – mely csak pozitív szám lehet, mert ekkor a b vektor oszlopában lévő elem pozitív marad
2. Kis zmax, -z min generátor elemet csak nem negatív célelem felett választhatok
3. Szűk keresztmetszet mellett kell a generáló elemet választani – szűk keresztmetszet: ha több generálóelemünk volna, akkor megvizsgálom, hogy az adott generálóelem sorában lévő b értéket, ha elosztom a leendő generáló elemmel, melyik ad kisebb értéket
4. Ajánlatos a legnagyobb célelem felett generáló elemet választani
5. Ha a célelemek csak negatívak vége az eljárásnak, bázismegoldás leolvasása, s akkor ez egyben ez az optimális megoldás is
6. Ha van pozitív célelem, de csak negatív elemek vannak felett, csak pozitív generáló elemet választhatok
- nem tudok generáló elemet választani – ekkor a célfüggvény nem korlátos a lehetséges megoldások halmazán
7. Ha van pozitív célelem és van felette pozitív elem – szűk keresztmetszet mellett választunk generáló elemet – végrehajtjuk az elemi bázistranszformációt
8. Az LP feladatnak akkor van optimális megoldása, ha az utolsó oszlopban nincs negatív és az utolsó sorban nincs pozitív elem
Alternatív optimum: -ot kapunk, ha a célértékek között van 0 és a többi célérték negatív és a 0 felett van pozitív elem – ekkor a 0 felett választhatok generáló elemet, ezzel az elemi BTR-rel a célérték nem változik – mindkét bázismegoldás optimális
Módosított normál feladat: - ot akkor kapunk, ha a feltételrendszer soraiban <=, vagy = relációjelek vannak – ekkor az egyenlőség soraiban fiktív u^ eltérésváltozókat vezetünk be
- lehetséges megoldást akkor kaphatunk, ha fiktív eltérésváltozók értéke 0, azaz ki tudtuk őket vinni a bázisból
- a megoldás során másodlagos célfüggvényt vezettünk be z^ sorok összegével
- lehetséges bázismegoldásnál a z^ felveszi a maximumát, a táblázat pedig a – z célértéke 0-t /ha ez teljesül, z összes céleleme is 0/
- ha van lehetséges bázismegoldás, akkor az nem feltétlenül optimális is egyben – ekkor az elsődleges célfüggvény optimalizálásával folytatjuk az eljárást
- vége az eljárásnak, ha – z ^ célelemei nem pozitívak és a célérték pozitív
- nincs a feladatnak még lehetséges megoldása sem, ha a feltételrendszer ellentmondást tartalmaz
Dualitás: minden általános maximalizáló – primál – feladatnak van egy minimalizáló – duál – feladat párja
Duál feladat felírása:
1. >= sorának együtthatóit ellentétes előjellel kell figyelembe venni
2. az = sorához tartozó y változóra nem kell előjelkikötés
3. duál: y1,y2>=0
Dualitás tétel: ha a primál vagy a duál feladatok közül valamelyiknek van lehetséges megoldása és véges optimuma, akkor a másiknak is van lehetséges megoldása és véges optimuma; s ez a két optimum érték megegyezik
Tétel: 1. Ha mind a duálnak, mind a primálnak van lehetséges megoldása, akkor f(x) <= g(y)
Primál célfv. Duál célfv.
A primál célfv. értéke mindig <=
2. Ha a primál feladat nem korlátos /felülről/ a lehetséges megoldások halmazán, akkor a duálnak még lehetséges megoldása sincs
