Diszkrét Matematika. Galambos Gábor SZTE-JGYPK

Diszkrét Matematika.

Galambos Gábor SZTE-JGYPK 2013-2014 Diszkrét Matematika

1

Tematika • Számelmélet: oszthatóság, euklideszi algoritmus, prímfelbontás, kongruenciák, prímszámok. • Kódolás elmélet: az RSA algoritmus és annak matematikai alapjai. • Lineáris algebra: vektor fogalma, műveletek vektorokkal, vektortér, bázis, véges dimenziós vektortér, koordináták, Sajátérték, sajátvektor. • Gráfelmélet: páros gráfok, magyar módszer, hozzárendelési feladat, szállítási feladat.

Diszkrét Matematika

2

1. Számelmélet A számelmélet első kérdéseit Pitagórasz tette fel, és a természetes számok egymáshoz való viszonyával foglalkozott. (Oszthatóság, prímszámok, maradékos osztás, stb.) Különböző részterületei alakultak ki: • Elemi számelmélet (oszthatóság, prímek, maradékos osztás) • Analitikus számelmélet (a vizsgálati módszer a függvénytan) • Algebrai számelmélet (algebrai számok) • Kombinatórikus számelmélet (tökéletes számok) • Prímszámelmélet (prímszámok eloszlása, tulajdonságaik) • Geometriai számelmélet (Nagy Fermat tétel) • Számításelméleti számelmélet (prímteszt, prímfaktorizáció, kriptográfia) Diszkrét Matematika

3

Oszthatóság Az oszthatóság azzal foglalkozik, hogy egy egész szám osztható-e egy másik egész számmal. A da azt jelenti, hogy létezik olyan k egész szám, amelyre teljesül, hogy a = kd. Ha da, akkor d az a szám osztója és az a szám a d szám többszöröse (többese). Általában csak pozitív egészekkel foglalkozunk, de az oszthatóság kiterjeszthető a negatív számokra is, hiszen ha d osztója a-nak, akkor –d is osztója a-nak az egész számok halmazán belül. Bármely a szám osztható 1-gyel és a-val. Ezeket triviális osztóknak nevezzük. A nem triviális osztókat tényezőknek vagy faktoroknak nevezzük. Diszkrét Matematika

4

Tétel 1.1.: Ha ab és ac, akkor ab+c Biz. Ha ab, akkor b = ka. Ha ac, akkor c = la. Ezért b + c = ka + la = (k + l) a Így a osztója (b + c)-nek is.

Vegyük észre, hogy a tétel állítása visszafele nem igaz. Azaz abból, hogy ab+c, abból nem következik, hogy ab és ac. Egy egyszerű ellenpélda: 28 és 8 = 3 + 5. Világos, hogy 2∤3 és 2∤5. Viszont igaz az alábbi tétel

Tétel 1.2.: Tegyük fel, hogy Diszkrét ab+cMatematika és ab. Ekkor ac.

6

Biz. Mivel ab+c és ab , ezért b+c = ka és b = la, ahol k > l. Ezért ka = b+c = la + c. Ezért (k – l)a = c. Amiből azonnal következik, hogy ac


6

Vizsgáljuk meg a következő példát: Legyen n = 5. • Lesznek olyan számok, amelyek többszörösei 5-nek, vagy másképpen fogalmazva 0-át adnak maradékul: ilyenek 10, 15, 20, … • Lesznek olyan számok, amelyek 5-tel osztva 1-et adnak maradékul: ilyenek 6, 11, 16, 21, … • Lesznek olyan számok, amelyek 5-tel osztva 2-t adnak maradékul: ilyenek 7, 12, 17, 22, … • Lesznek olyan számok, amelyek 5-tel osztva 3-at adnak maradékul: ilyenek 8, 13, 18, 23, … • Lesznek olyan számok, amelyek 5-tel osztva 4-et adnak maradékul: ilyenek 9, 14, 19, 24, …


7

Általában azt mondhatjuk, hogyha n egy természetes szám, akkor a természetes számokat különböző osztályokba sorolhatjuk aszerint, hogy az n-nel való osztás után a maradék értéke mennyi lesz. Ezeket az osztályokat maradékosztályoknak vagy más néven ekvivalencia osztályoknak nevezzük. Ha n természetes szám, akkor az n-hez tartozó maradékosztályok száma is n. Tétel 1.3. (Maradékos osztás tétele): Legyenek a és n pozitív egész számok. Ekkor egyértelműen léteznek olyan q és r egész számok, amelyekre 0 ≤ r < n, és a = qn + r.


8

A fenti kongruencia relációról belátható, hogy ekvivalencia reláció: azaz reflexív, szimmetrikus, tranzitív.

Legyen n = 3

2 1 0

0 1 2 3 4 5 6 Diszkrét Matematika

9


10

Prímszámok Ha egy a számnak csak a triviális osztói léteznek, akkor az a számot prímszámnak nevezzük. Ha az a nem prím, akkor a-t összetett számnak nevezzük. Prímszámok: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 53,… Összetett számok: 18 = 2⋅3.3, azaz 318 és 218.


11

Tétel 1.4. Végtelen sok prímszám létezik. Biz.


12

Tétel 1.6.: Ha p prím és a, b egész számok, amelyekre teljesül, hogy pab, akkor pa vagy pb.


13

Közös osztó és legnagyobb közös osztó Ha a d szám egyaránt osztója az a és b egész számoknak, akkor d-t az a és b számok közös osztójának nevezzük. Legyen a = 30 és b = 72. Mivel a osztói a 1, 2, 3, 5, 6, 10, 15, 30 és b osztói 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, ezért a és b közös osztói a 2, 3 és a 6. Ha a és b legalább egyike 0-tól különböző egész, akkor a és b közös osztói közül a legnagyobbat az a és b számok legnagyobb közös osztójának nevezzük. Jelölése lnko(a,b). Legyen a = 30 és b = 72. Ekkor lnko(30,72) = 6. Diszkrét Matematika

14

Az lnko tulajdonágai: • • • • •

lnko(0, 0) =0, lnko(0, a) = | a | , 1 ≤ lnko(a, b) ≤ min(| a |, | b |), lnko(a,b) = lnko(b, a) lnko(a, ka) = | a |

Tétel 1.5.: Ha az a és b egészekre da és db, akkor d lnko(a,b) Azt láttuk, hogy ha a = 30 és b = 72, a és b közös osztói a 1, 2, 3 és a 6, és 1|6, 2|6 és 3|6.


15

Azt mondjuk, hogy az a és b egész számok relatív prímek, ha lnko(a,b) = 1. Azt mondjuk, hogy az n1, n2, …, nk egész számok páronként relatív prímek, ha lnko(ni,nj) = 1 minden i ≠ j párra.


16


17

Az euklideszi algoritmus Az euklideszi algoritmus a következő rekurziós tételen alapul: Tétel 1.8.: Legyen a tetszőleges, nem negatív, és b tetszőleges pozitív egész szám. Ekkor lnko(a,b) = lnko(b, a mod b). Biz. A bizonyításban egyrészt megmutatjuk azt, hogy lnko(a,b) | lnko(b, a mod b). Másrészt azt is bebizonyítjuk, hogy lnko(b, a mod b) | lnko(a,b). Ebből azonnal következik, hogy lnko(a,b) = lnko(b, a mod b). Diszkrét Matematika

18

Példa: Legyen a = 360 és b = 126. Ekkor a tétel szerint lnko(360,126) = lnko(126, 108). Alkalmazzuk ismét a tételt: lnko(126,108) = lnko(108,18). Most a tétel ismételt alkalmazásával azt kapjuk, hogy lnko(108, 18) = lnko(18,0). Ezért a legnagyobb közös osztó: 18.


19

2. Lineáris algebra A hétköznapi tér – az elemi geometria két(három)dimenziós tere – két különböző pontja, az A és B pont közti szakasznak kétféle módon adhatunk irányítást. Az jelöli azt az irányított egyenes szakaszt, amelynek kezdőpontja az A és végpontja a B. Az irányított egyenes szakaszok közé soroljuk az szimbólummal jelölt elfajult szakaszt is, amelynek kezdőpontja és végpontja is az A pont. Az vektort nullvektornak nevezzük. B B

A A

A Diszkrét Matematika

22

Az irányított egyenes szakaszok osztályokra (csoportokra) oszthatók oly módon, hogy a különböző osztályoknak nem lesz közös eleme: Azt mondjuk, hogy az és szakaszok egy osztályba esnek, ha az AD és CD szakaszok felezési pontjai egybeesnek. (Az egy osztályba eső szakaszok párhuzamosak és egyenlő hosszúak.) Az egy osztályba eső elemek összességét nevezzük vektornak. B F1≡ F2 A

D

C

A vektorok jelölése: a, a, . Azt, hogy az irányított egyenes szakasz az a vektorhoz tartozik Diszkrét Matematika-val jelöljük 23

Ha az irányított egyenes szakasz az a vektorral jelölt osztályba tartozik, akkor -t az a egy reprezentánsának nevezzük. Azt mondjuk, hogy az és irányított szakaszok relációban vannak egymással, ha ők ugyanannak az a vektornak a reprezentánsai. (Vagy ami ezzel megegyezik: az AD és BC szakaszok felezési pontjai egybeesnek.) Jelölése:

Egy osztályozást ekvivalencia relációnak nevezünk, ha igazak a következők: reflexív: tranzitív: szimmetrikus: Diszkrét Matematika

24

Tétel: A fenti osztályozás a vektorok között ekvivalencia relációt határoz meg. Biz. Legyen , és az a vektor három reprezentánsa. Ekkor be kell látnunk, hogy a definíció három tulajdonsága (reflexív, tranzitív és szimmetrikus) teljesül a reprezentánsokra. Az osztályozás Reflexív, hiszen szakasz felezési pontja egybeesik az szakasz felezési pontjával. Tranzitív, mert, ha akkor AB párhuzamos DC-vel és így ABDC paralelogrammát alkot. Hasonlóan -ből következik, hogy CD párhuzamos EF-fel. Ezért AB párhuzamos EF-fel, amiből következik, hogy ABFE paralelogramma. Ennek átlói mindig felezik egymást. A szimmetrikusság abból következik, hogy ha AB párhuzamos CDvel, akkor CD is párhuzamos AB-vel. Diszkrét Matematika

25

Tétel: Ha megadunk a síkban egy P pontot, akkor minden vektornak van olyan reprezentánsa, amelynek kezdőpontja P, azaz van olyan Q pont, hogy . Következmény: Egy vektor a síkban mindig szabadon eltolható önmagával párhuzamosan úgy, hogy kezdőpontja egy megadott pontba kerüljön. Az a vektor hosszán bármely reprezentánsának hosszát értjük, és |a|val jelöljük. Az a vektor irányán az összes olyan vektor irányát értjük, amelynek reprezentánsai párhuzamosak az a reprezentánsaival. Ha az a és b vektorok iránya azonos, akkor a jelölés: a ∥ b. A nullvektor – definíció szerint – párhuzamos minden vektorral.


26

Két vektor azonos irányítású, ha reprezentánsaik párhuzamosak, és úgy hozhatók fedésbe, hogy kiindulási és végpontjaik egybeesnek. Az azonos irányítású vektorok jelölése: a⇈b. A nullvektor – definíció szerint – minden vektorral azonos irányítású. Ha két vektor párhuzamos, de nem azonos irányítású, akkor jelölése: a ⇅ b. Két vektort kollineárisnak (egy egyenesbe esőnek) nevezünk, ha irányaik megegyeznek. Tétel: Két vektor akkor és csak akkor egyenlő (ekvivalens), ha reprezentánsaik hossza, iránya és irányítása megegyezik.


27

Az a és b nem egy egyenesbe eső vektorok szögén értjük azt a belső szöget, amely teszőlegesen választott és irányított egyenes szakaszok esetén a PAB háromszög P csúcsánál van. A B P Ha a vektorok egy egyenesbe esnek és egyik sem nullvektor, ha a ⇈ b , akkor a bezárt szög 0º, ha a ⇅ b, akkor a bezárt szög 180º A nullvektor bármely vektorral 0º-os szöget zár be. Diszkrét Matematika

28

Műveletek vektorokkal: Összeadás Vektorok összege: Az

és

vektorok összegén értjük

azt a vektort, amelynek reprezentánsa az

2. Szabály: „paralelogramma” szabály

1. Szabály: „vektorfűzés”

B

A

irányított szakasz.

C

B

A

C B


29

Műveleti azonosságok 1. Az összeadás nem vezet ki a vektorok halmazából. (Az összeadás eredménye vektor.) 2. Az összeadás kommutatív művelet: a+b=b+a A bizonyítás egyszerűen következik a definícióból. 3. A vektorok halmazában létezik a nullvektor, amely az a + x = a vektoregyenlet megoldásaként áll elő: x = 0. a+0=a. 4. A vektorok halmazában létezik az ellentett (inverz) elem, amely az a + x = 0 vektoregyenlet megoldásaként áll elő: x = – a . a + (– a) = 0 . A (– a) inverz vektor nagysága és iránya megegyezik az a vektor irányával és nagyságával, de irányítása ellentétes. Diszkrét Matematika

30

Műveletek vektorokkal: Kivonás Használjuk az inverz elem definícióját a kivonás értelmezéséhez: b – a = b + (–a) b

C

B a

b + (–a) A b

Két vektor különbségén azt a vektort értjük, amelynek hossza a közös kiinduló pontból felmért vektorok végpontjai közötti távolság, iránya a két végpont által meghatározott irány és irányítása a kivonandóból a kisebbítendő felé mutat. Diszkrét Matematika

31

Összegvektorra vonatkozó háromszög egyenlőtlenség: |a + b| ≤ |a| + |b|. Különbségvektorra vonatkozó háromszög egyenlőtlenség: |a – b| ≤ | |a| – |b| |. Paralelgramma azonosság: egy paralelogramma átlói hosszának négyzetösszege egyenlő az oldalak hosszainak négyzetösszegének kétszeresével: |a + b|2+ |a – b|2 = 2|a|2 + 2|b|2.


32

Műveletek vektorokkal: Skalárral való szorzás Ha λ valós szám, akkor az a vektor λ skalárral történő szorzatán azt a λa vektort értjük, amelyre | λa | = | λ |·| a | λa || a

Így a λ skalárral való szorzás | λ |-szoros nyújtás, ha λ > 1, | λ |arányú zsugorítás, ha 1 > λ > 0, és ha λ < 0, akkor a megfelelő szabályhoz járul egy kezdőpontra történő tükrözés.


33

Műveleti azonosságok Legyen V a vektorok halmaza. Ekkor minden λ,ν ∊ ℝ és a, b ∊ V esetén: λ(ν a) = (λν )a (λ + ν )a = λ a + ν a λ(a + b) = λ a + λ b Példa: legyen λ = 2. b

a

b b

a

a+b a+b

Emlékeztetőül: párhuzamos szelők tétele! Diszkrét Matematika

34

Műveletek vektorokkal: Vektorok skaláris szorzata Az a és b nemnulla vektorok skaláris szorzatán a a b = | a | | b | cos γ számot értjük, ahol γ az a és b vektor által bezárt szög. A nullvektor és egy másik tetszőleges vektor skaláris szorzata 0. Fontos: a vektorok skaláris szorzata egy szám! Azt mondjuk, hogy a művelet „kivezet” a vektorok halmazából. Geometriai értelmezés: b γ

·

a

| b | cos γ Diszkrét Matematika

35

Vegyük észre, hogy párhuzamos vektorok a skaláris szorzatra nézve úgy viselkednek, mint a valós számok. Ilyenkor a két vektor hossza (| a | és | b |) adja a számok abszolút értékét, és a számok előjelét a két vektor iránytásának viszonya szolgáltatja. Ez következik abból a tényből is, hogy cos 0º = 1 és cos 180 º = – 1. Mivel a vektorok skaláris szorzata ennek a műveletnek a kiterjesztése nem kollineáris vektorokra, ezért a nem egy egyenesbe eső vektorokra úgy végezzük el a skaláris szorzást, hogy az egyik vektort „rávetítjük” a másik vektorra, és ezutás alkalmazzuk a „klasszikus” – számokra már ismert – szorzás műveletét. Mivel a2 = a · a = | a |2 , ezért Következmény: a · a > 0, ha a ≠ 0, és a · a = 0 akkor és csak akkor, ha a = 0. (A skalár szorzat pozitív definit.) Diszkrét Matematika

36

Tétel: Ha a és b két egy síkban fekvő nemnulla vektor, akkor a két vektor akkor és csak akkor merőleges egymásra, ha skaláris szorzatuk 0. Biz. 1. Tegyük fel, hogy a két vektor merőleges egymásra. Ekkor a két vektor által közbezárt szög 90º. Mivel cos 90º = 0, ezért a b = | a | | b | cos γ = | a | | b | · 0 = 0. 2. Tegyük fel, hogy a b = 0. Azt tudjuk, hogy a b = | a | | b | cos γ és | a | ≠ 0 és | b | ≠ 0. Egy szorzás csak akkor lehet 0, ha valamelyik tényezője 0, ezért a b = 0 csak akkor állhat, ha cos γ = 0. Ebből pedig következik, hogy γ = 90º + k π, ami azt jelenti, hogy a és b merőleges egymásra. Diszkrét Matematika

37

Műveleti azonosságok Tétel: a vektorok skaláris szorzata kommutatív művelet: ab=ba. Tétel: a vektorok skaláris szorzata nem asszociatív művelet: ( a b ) c ≠ a ( b c ). Biz. A bal oldal egy c-vel párhuzamos vektort ad, a jobb oldal pedig egy a-val párhuzamosat. Tétel:a vektorok skaláris szorzatára igazak a következő azonosságok: λ( a b ) = (λ a ) b = a (λ b ). Biz. Használjuk ki a kommutativitást és a definíciót! Diszkrét Matematika

38

Tétel: a vektorok skaláris szorzata disztributív művelet: a( b + c ) = a b + a c. Biz. Geometriai bizonyítást adunk. Tegyük fel, hogy a = λ e, ahol e egységnyi hosszú. Ekkor b+c b cos α = e b

c

c cos β = e c

b e e( b + c )

Ebből következik, hogy e( b + c ) = e b + e c. A skalárral való szorzás szabályai miatt λ e ( b + c ) = λ e b + λ e c . Mivel a = λe, ezért a( b + c ) = a b + a c. Diszkrét Matematika

39

Műveletek vektorokkal: Vektorok vektoriális szorzata Legyenek a és b nemnulla vektorok, és jelöljük a közbezárt szöget γval. A két vektor vektoriális szorzatán azt az a x b vektort értjük, amelynek nagysága = | a | | b | sin γ iránya merőleges az a és b vektorok által meghatározott síkra írányítása olyan, hogy a, b és a x b ebben a sorrendben jobbsodrású rendszert alkot. A nullvektor és egy másik tetszőleges vektor vektoriális szorzata 0. Tétel: Ha a és b egyike sem nullvektor, akkor a x b hossza az a és b által kifeszített paralelogramma területe. b γ

m = | b | sin γ a Diszkrét Matematika

T = | a | | b | sin γ 40

c=axb ·· a

b


41

Műveleti azonosságok Tétel: a vektorok vektoriális szorzata antikommutatív művelet: axb=–bxa. Biz. A tétel állítása azonnal következik a ”jobbsodrás” előírásából. Tétel: a vektorok vektoriális szorzata megtartja a lineáris kombinációt: (λa + µ b) x c = λ (a x c ) + µ (b x c ) . Tétel: a vektorok vektoriális szorzata mindkét oldalra disztributív művelet: (a +b) x c = (a x b) + (b x c) a x ( b + c ) = (a x b) + (a x c) Diszkrét Matematika

42

Tétel: Ha a és b két egy síkban fekvő nemnulla vektor, akkor a két vektor akkor és csak akkor párhuzamos egymással, ha vektoriális szorzatuk 0. Biz. 1. Tegyük fel, hogy a két vektor párhuzamos. Ekkor a két vektor által közbezárt szög 0º. Mivel sin 0º = 0, ezért a x b = | a | | b | sin γ = | a | | b | · 0 = 0. 2. Tegyük fel, hogy a x b = 0. Azt tudjuk, hogy a x b = | a | | b | sin γ és | a | ≠ 0 és | b | ≠ 0. Egy szorzás csak akkor lehet 0, ha valamelyik tényezője 0, ezért a x b = 0 csak akkor állhat, ha sin γ = 0. Ebből pedig következik, hogy γ = 180º + k π, ami azt jelenti, hogy a és b párhuzamos. Diszkrét Matematika

43

Műveletek vektorokkal: Vektorok vegyes szorzata Az a, b, c vektorok vegyes szorzatán az ( a b c )= a ·(b x c ) számot értjük. Tétel: Az a, b, c vektorok vegyes szorzata akkor és csak akkor 0, ha a három vektor egy síkban van. Tétel: Az a, b, c vektorok vegyes szorzata az a, b és c által kifeszített paralelepipedon térfogata. Tétel: Az a, b, c vektorok vegyes szorzataira igazak a következő állítások: ( a b c ) = (b c a) = (c a b) = – ( c b a ) = – ( b a c ) = – ( a c b )


44

Vektorok megadása koordinátákkal Tétel: Ha a és b párhuzamos, akkor létezik olyan α konstans, amelyre b = αa. Tétel: Ha adott a síkban a és b nem kollineáris vektor, akkor a sík bármely c vektora felbontható az a és b vektorokkal párhuzamos összetevőkre. Azaz léteznek olyan egyértelműen meghatározható α, β ∊ℝ konstansok, amelyekre c=αa+βb Biz. 1. Felbonthatóság: Legyen adva a három vektor: a, b, c. Húzzunk c végpontjain át párhuzamosokat az a ill. b vektorokkal. Az a és b vektorral párhuzamos egyenesek biztosan metszik egymást. Legyen ez a pont M. Diszkrét Matematika 45

M αa A


βb B

46

2. Egyértelműség. Tegyük fel, hogy létezik két felbontás: c = α1 a + β1 b c = α2 a + β2 b 0 = ( α1 – α2 ) a + ( β1 – β2 ) b Mivel a és b nem párhuzamosak, ezért konstansszorosaik sem párhuzamosak. Két – nem kollineáris – vektor konstansszorosának összege csak akkor lehet a 0 vektor, ha együtthatóik 0-val egyenlők. Ezért α1 = α2 és β1 = β2 , ami ellentmondás. Diszkrét Matematika

47

A c = α a + β b előállításban azt mondjuk, hogy a c vektor az a és b vektorok lineáris kombinációja. (A definíció független a dimenziótól, tehát több vektort is feksorolhatunk a jobb oldalon.) Legyen a1, a2, …, an a (kétdimenziós) tér n különböző osztályába tartozó vektor. Azt mondjuk, hogy a vektorok egy rendszere lineárisan független, ha a rendszer egyetlen vektora sem fejezhető ki a többi lineáris kombinációjával. Tétel: Ha a és b nem kollineáris (nem párhuzamos) vektor, akkor a két vektor lineárisan független. Biz. Triviális.


48

Következmény: A kétdimenziós térben van két lineárisan független vektor. Tétel: A kétdimenziós térben nincs három olyan vektor, amely lineárisan független lenne. Biz. A tétel állítása azonnal következik a felbontási tételből A maximális számú lineárisan független vektort bázisnak nevezzük. Következmény: a kétdimenziós térben két nem kollineáris vektor bázist alkot. Legyen a és b két olyan vektor, amely bázist alkot a kétdimenziós térben. A c = α a + β b előállításban az α és β együtthatókat a c vektor a, b bázisra vonatkozó koordinátájának nevezzük. Diszkrét Matematika

49

A vektornak azt a reprezentánsát, amelynek kezdőpontját a Descartes-féle koordinátarendszer origójában van rögzítve, helyvektornak nevezzük. Egy helyvektort meghatározza végpontjának helyzete. Tétel: A Descardes koordinátarendszerben a koordinátatengelyek irányába mutató egységnyi hosszúságú helyvektorok bázist alkotnak. e1 = (1,0) e2 = (0,1)

a = 4 e1 + 2 e2

3 2 1

a 1 2 3 4

a = (4, 2) Diszkrét Matematika

50

Figyeljük meg, hogy egy vektor koordinátái függenek a bázistól: a = (2,0) b = (0,2)

a' = (1,0) b' = (0,1) 3 2 1

c 1 2 3 4

c=2a+1b

c = 4 a' + 2 b'

c = (2, 1)

c = (4, 2)

Következmény: egy adott bázis esetén egy síkbeli vektor megadható két koordinátájának segítségével: c = (c1, c2). Diszkrét Matematika

51

Műveletek koordinátákkal adott vektorokkal Legyen az a és b két síkbeli (kétdimenziós) vektor adott a koordinátáival:

Két síkbeli vektor összegén azt a c vektort értjük, amelynek koordinátái a két összeadandó koordinátáinak összegével egyenlők:

Könnyű ellenőrizni, hogy a műveleti azonosságok érvényben maradnak. Diszkrét Matematika

52

4 3 2 1

b a 1 2 3 4 5


53

Ha λ valós szám (λ ∈ ℝ), akkor az a vektor λ skalárral történő szorzatán azt a λa vektort értjük, amelyre

tehát a konstanssal megszorozzuk a vektor minden koordinátáját.

λ = 1,5

4 3 2 1

a 1 2 3 4 5


54

Két síkbeli vektor különbségén azt a c vektort értjük, amelynek koordinátái a kivonandó és a kisebbítendő koordinátáinak különbségével egyenlők:

4 3 2 1 -b a

b

1 2 3 4 5


55

Tétel: A koordinátákkal adott a és b vektorok skaláris szorzatán a

számot értjük, azaz a skalárszorzat értéke a szorzótényezők megfelelő koordinátáinak szorzatösszegével egyenlő. Biz. Itt geometriai bizonyításnak nincs helye, mert az eredmény skalár. Legyen a kétdimenziós tér bázisa az e1 és e2 – koordinátatengelyek irányába mutató – két egységvektor:

Ekkor a = a1 e1 + a2 e2 és b = b1 e1 + b2 e2 . Diszkrét Matematika

56

Számítsuk ki a skalárszorzat értékét úgy, hogy közben használjuk a skalárszorzat műveleti azonosságait: a b = (a1 e1 + a2 e2 ) (b1 e1 + b2 e2 ) = = a1 b1 e1 e1 + a1 b2 e1 e2 + a2 b1 e2 e1 + a2 b2 e2 e2 Használjuk ki, hogy egymásra merőleges, egységnyi hosszú vektorok alkotják a bázist: e1 e1 = e2 e2 = 1, és e1 e2 = e2 e1 = 0. Ezért a b = a1 b1 e1 e1 + a2 b2 e2 e2 = a1 b1 + a2 b2, amit bizonyítani akartunk. Mivel a vektoriális szorzat kivezet a síkból,ezért ennek kordinátákkal történő kiszámítása előtt foglalkoznunk kell a háromdimenziós tér vektoraival. Diszkrét Matematika

57

Síkban, koordinátákkal adott vektor hossza: Ha a vektor koordinátákkal van adva, akkor a vektor hosszát megkaphatjuk, ha képletet használjuk. Ekkor ugyanis:

Példa: Legyen a = (3, 4). Ekkor


58

Vektorok a háromdimenziós térben Mivel a vektorok korábbi definíciójában sehol sem használtuk ki azt, hogy egy irányított szakasznak a síkban kell lenni, ezért a három dimenziós térben minden korábbi definíció érvényben marad. Két vektor egymáshoz való viszonya is változatlan lesz a térben, mert ha a két vektor reprezentánsait közös kezdőpontba toljuk el, akkor a két vektor mindig egyértelműen meghatároz egy síkot, és ezért a síkbeli definíciók itt is érvényben maradnak. (lásd két vektor szöge). Ennek az a következménye, hogy az összes művelet, amelyet a vektorokra definiáltunk, érvényben marad, hiszen ezekben maximum két vektor szerepel. A kérdés az, hogy meg lehet-e adni koordinátákkal egy háromdimenziós vektort, és lehet-e általánosítani a két-dimenziós eredményeket? Diszkrét Matematika 59

Háromdimenziós vektorok megadása koordinátákkal Tétel: Ha a és b párhuzamos, akkor létezik olyan α konstans, amelyre b = αa. Tétel: Ha adottak a térben a, b és c nem egy síkbba eső vektorok, akkor a tér bármely d vektora felbontható az a, b és c vektorokkal párhuzamos összetevőkre. Azaz léteznek olyan egyértelműen meghatározható α, β, γ ∊ℝ konstansok, amelyekre d=αa+βb+γc Biz. Legyen adva a három nem egy síkba eső vektor, és vegyünk fel egy negyedik vektort is. a-t, b-t és d-t toljuk el közös kezdőpontba (K), és d végpontján jelöljük D-vel, és húzzunk egy a D-n átmenő és a c vektorral párhuzamos egyenest. Diszkrét Matematika

60

Ez az egyenes döfi az a és b által meghatározott síkot egy T pontban. A KT irányított szakasz meghatároz egy f vektort , amely az a és b vektorokkal egy síkban van. Ezért a síkbeli vektorok felbontási tétele miatt léteznek olyan α, β ∊ℝ konstansok, amelyekre f=αa+βb. A TD által meghatározott c’ vektor párhuzamos a c vektorral, ezért c’ = γ c. Az f, c’ és a d vektorok egy síkban vannak, ezért rájuk ismét alkalmazható a síkbeli vektorokra vonatkozó felbontási tétel: d = f + c’ = α a + β b + γ c. Az egyértelműség bizonyítása megegyezik a kétdimenziós esettel. Diszkrét Matematika

61

d = f + c’ = α a + β b + γ c c’ = γ c a

D d

b

d c b K βb

T a f f =α a + β b

αa Diszkrét Matematika

62

Tétel: Ha a, b és c nem egy síkba eső vektorok, akkor a három vektor lineárisan független. Biz. Triviális. Következmény: A háromdimenziós térben van három lineárisan független vektor. Tétel: A háromdimenziós térben nincs négy olyan vektor, amely lineárisan független lenne. Biz. A tétel állítása azonnal következik a felbontási tételből


63

A maximális számú lineárisan független vektort bázisnak nevezzük. Következmény: a háromdimenziós térben három nem egy síkba eső vektor bázist alkot. Legyen a, b és c három olyan vektor, amely bázist alkot a háromdimenziós térben. A d = α a + β b + γ c előállításban az α, β és γ együtthatókat a d vektor a, b, c bázisra vonatkozó koordinátájának nevezzük. Tétel: A Descardes koordinátarendszerben a koordinátatengelyek irányába mutató egységnyi hosszúságú helyvektorok bázist alkotnak. e1 = (1, 0, 0)

e2 = (0, 1, 0) Diszkrét Matematika

e3 = (0, 0, 1) 64

Az e1, e2, e3 vektorokból álló bázis ortonormált rendszernek hívjuk. (Az elnevezés magyarázata: ortogonális = merőleges egymásra, normált = egységnyi hosszú.) Koordinátákkal adott háromdimenziós vektorokra a kétdimenziós vektoroknál megadott definíciók kiterjeszthetők. Legyen az a és b két térbeli (háromdimenziós) vektor adott a koordinátáival:


65

Két térbeli vektor összegén azt a c vektort értjük, amelynek koordinátái a két összeadandó koordinátáinak összegével egyenlők:

Ha λ valós szám (λ ∈ ℝ), akkor az a vektor λ skalárral történő szorzatán azt a λa vektort értjük, amelyre

tehát a konstanssal megszorozzuk a vektor minden koordinátáját. Diszkrét Matematika

66

Két térbeli vektor különbségén azt a c vektort értjük, amelynek koordinátái a kivonandó és a kisebbítendő koordinátáinak különbségével egyenlők:

A koordinátákkal adott a és b vektorok skaláris szorzatán a

számot értjük, azaz a skalárszorzat értéke a szorzótényezők megfelelő koordinátáinak szorzatösszegével egyenlő.


67

Tétel: A koordinátákkal adott a és b vektorok vektoriális szorzatán az

vektort értjük. Biz. Jelöljük most a koordinátatengelyek irányába mutató – bázist alkotó – egységvektorokat rendre i, j, k-val. a x b = (a1 i + a2 j + a3 k) x (b1 i + b2 j + b3 k) = = a1 b1(i x i ) + a1 b1(i x j ) + a1 b3(i x k ) + a2 b1(j x i ) + a2 b2(j x j ) + a2 b3(j x k ) + a3 b1(k x i ) + a3 b2(k x j ) + a3 b3(k x k ). Diszkrét Matematika

68

Használjuk ki, hogy (i x i ) = (j x j ) = (k x k ) = 0, mert párhuzamos vektorok vektoriális szorzata 0. Vegyük észre, hogy a definíció miatt (i x j ) = k , (j x k ) = i , (k x i ) = j , és az antikommutativitás miatt (i x k ) = – j, (j x i ) = – k, (k x j ) = – i Ezért a x b = a1 b2 k – a1 b3 j – a2 b1 k + a2 b3 i + a3 b1 j – a3 b2 i = (a2 b3 – a3 b2) i + (a3 b1 – a1 b3) j + (a1 b2 – a2 b1) k.


69

Koordinátákkal adott háromdimenziós vektorok esetén a vegyes szorzat kiszámítható a definíció alkalmazásával: ( a b c )= a ·(b x c ) ( a b c ) = a ·(b x c ) = (a1 i + a2 j + a3 k) · [(b2 c3 – b3 c2) i + (b3 c1 – b1 c3) j + (b1 c2 – b2 c1) k] = = a1 (b2 c3 – b3 c2) i + a2 (b3 c1 – b1 c3) j + a3 (b1 c2 – b2 c1) k

A 3 x 3-as elrendezéseket harmadrendű determinánsnak nevezzük. Diszkrét Matematika

70

Térbeli vektorok hossza: Ha a vektor koordinátákkal van adva, akkor a vektor hosszát megkaphatjuk, ha képletet használjuk. Ekkor ugyanis:

Példa: Legyen a = (3, 4, 5). Ekkor


71

Határozzuk meg az y és z értékeket úgy, hogy az a = 2i + yj + k és a b = 3i -6j +zk vektorok párhuzamosak legyenek egymással! Használjuk a párhuzamosság feltételét, és a vektorok vektoriális szorzatának koordinátás alakját:

Mivel egy vektor akkor 0, ha minden koordinátája 0, ezért – 12 – 3y = 0-ból kapjuk, hogy y = – 4. Hasonlóan, 3 – 2z = 0-ból kapjuk, hogy z = 3/2. Ha y és z értékét behelyettesítjük az első koordináta helyébe, akkor azonosságot kapunk. Diszkrét Matematika

72

Mivel egyenlő y értéke, ha azt akarjuk, hogy az a = (4, -7, 2) vektor merőleges legyen b = (5, y, 4)-re? Használjuk a merőlegesség feltételét, és a vektorok skaláris szorzatának koordinátás alakját:

Az a kérdés, hogy a skaláris szorzat milyen y értékre egyenlő 0-val? 28 – 7y = 0-ból következik, hogy y = 4. Ezért a (4, -7, 2) vektorra a (5, 4, 4) vektor merőleges.


73

Bizonyítsuk be, hogy ha egy tetraéder két szemközti élpárja merőleges egymásra, akkor a harmadik élpár is merőleges. Feltételek: a ⊥ c – b c⊥b–a Biz.dó: b⊥c–a a

b c-a

b-a

c

Megoldás: a feltételekből adódik, hogy a ( c – b ) = 0 és c-b c ( b – a ) = 0. Ezért ac – ab = 0 és cb – ca = 0. cb – ab = 0, és így b( c – a ) = 0 Diszkrét Matematika

⇒

b⊥c–a 74

Bizonyítsuk be, hogy az A(1,0,7), B(-1,-1,2), C(2,-2,2) és D(0,1,9) pontok egysíkúak (komplanárisak). Azt kell belátni, hogy a D A

O B

vektorok egy síkban vannak.

C

Az ábrából kiolvasható, hogy

Ezért a

vektorok koordinátái kiszámíthatók: Diszkrét Matematika

75

Ez a három vektor akkor van egy síkban, ha a koordinátáikból alkotott harmadrendű determináns értéke = 0. (Vegyük figyelembe a vegyesszorzat geometriai értelmezését.)


76

Vektorfogalom általánosítása Láttuk azt, hogy a kétdimenziós ill. a háromdimenziós térben a tér egyes pontjait reprezentáló vektorok egy számpárral, ill. egy számháromassal jellemezhetők. A vektorok között műveleteket definiáltunk, amelyek közül néhány eredménye vektor (összeadás, skalárral való szorzás) volt, másoké skaláris mennyiség (skaláris szorzás). Terjesszük ki a vektor fogalmát : Egy n-dimenziós vektoron egy a = (a1, a2, …, an) = (ai)n rendezett szám n-est értünk. (A definícióban most nincs jelentősége annak, hogy a vektort sorvektor vagy oszlopvektor formájában adjuk meg, de a későbbi tanulmányok során a két fogalmat meg kell különböztetni egymástól) Diszkrét Matematika

77

Definiáljunk két műveletet – a vektorok összeadását és a skalárral való szorzást – úgy, hogy az n = 2 ill. n =3 speciális esetekre a már korábban definiált műveleteket kapjuk. Az a = (a1, a2, …, an) = (ai)n, b = (b1, b2, …, bn) = (bi)n két ndimenziós vektor összegén azt a c = (c1, c2, …, cn) = (ci)n vektort értjük, amelynek koordinátái a két összeadandó koordinátáinak összegével egyenlők: c = a + b = (a1 + b1, a2 + b2, …, an + bn ) = (ai + bi )n Ha λ valós szám (λ ∈ ℝ), akkor az a n-dimenziós vektor λ skalárral történő szorzatán azt a λa vektort értjük, amelyre

tehát a konstanssal megszorozzuk a vektor minden koordinátáját. Diszkrét Matematika

78

Könnyű belátni, hogy ha λ, µ ∈ ℝ és a = (ai)n, b = (bi)n , akkor az így definiált műveletekre érvényesek az alábbi azonosságok: (1)

λ(a + b) = λ a + λ b

(2)

(λ + µ) a = λ a + µ a

(3)

(λ µ) a = λ(µ a)

(4)

1a = a

Az n-dimenziós térben két vektor – a és b – egyenlő, ha megfelelő koordinátái megegyeznek, azaz ai = bi, i = 1,2,…,n.


79

Definiáljuk a következő speciális vektorokat az n-dimenziós vektorok halmazában: 1 = (1, 1, …, 1) = (1)n 0 = (0, 0, …, 0) = (0)n

egységvektor nullvektor i. egységvektor

Tétel: Érvényesek a következő állítások: (1) 0a= 0 (2) (– 1) a = – a (3) λ0 = 0 (4) λa= 0 ⇒ (λ = 0 ∨ a = 0) (5) λ a = λ b ⇔ (λ = 0 ∨ a = b) (6) λ a = µ a ⇒ (λ = µ ∨ a = 0) Diszkrét Matematika

80

Az n-dimenziós tér vektorainak egy halmazát lineárisan függetlennek nevezzük, ha egyik vektor sem írható fel a többiek lineáris kombinációjaként. Tétel: ha a vektoroknak egy halmaza lineárisan független, akkor a nullvektor csak triviálisan – csupa 0 együtthatóval – állítható elő a vektorok lineáris kombinációjával. Azt a minimális számú lineárisan független vektort, amelynek lineáris kombinációjaként bármely n-dimenziós vektor előállítható, bázisnak nevezzük. Tétel: n – 1 darab vektor nem elegendő ahhoz, hogy minden ndimenziós vektor előállítsunk ezek lineáris kombinációjaként. Tétel: az n darab egységvektor az n-dimenziós vektorok halmazában lineárisan független. Diszkrét Matematika

81

Hozzárendelési feladat Adott n számú dolgozó és n különböző munka. A dolgozók a munkákat különböző költségekkel végzik el. Osszuk szét a dolgozók között a munkákat úgy, hogy minden dolgozó pontosan egy munkát kapjon, és a munkavégzés költsége minimális legyen! n

A dolgozók száma

cij

A j. munka elvégzésének költsége, ha azt az i. dolgozó hajtja végre. (1 ≤ i,j ≤ n) 1, ha az i. dolgozó végzi a j. munkát

xij 0, különben 83

A matematikai modell

i = 1, 2, …, n j = 1, 2, …, n 1 ≤ i ≤ n, 1 ≤ j ≤ n

84

Megoldható a feladat? A megoldást mindig egy olyan n n-es bináris mátrix szolgáltatja, amelynek minden sorában és minden oszlopában egy – és csak egy – 1-es van. Példa: 4 4-es esetben legyen a költségmátrix Egy lehetséges megoldás:

85

Következmény-1: Egy hozzárendelési feladatnak (HF) mindig van lehetséges megoldása. Következmény-2: Egy HF lehetséges megoldásainak halmaza csak ntől függ, a költségmátrix értékétől a a lehetséges megoldások halmaza független. Következmény-3: Egy HF-nak n! különböző lehetséges megoldása van. Következmény-4: Különböző célfüggvényű (de azonos n-hez tartozó) HF-hoz tartozó lehetséges megoldások halmaza megegyezik. Ezért a HF-t meghatározza a C = {cij} költségmátrix. Jelölése: H(C). Következmény-5: Egy HF optimális megoldását mindig meghatározhatjuk, ha végigpróbáljuk az összes lehetséges megoldást, és kiválasztjuk azt, amelyhez a minimális célfüggvényérték tartozik. 86

A Cn m és Dn m mátrixokat ekvivalensnek mondunk, ha léteznek olyan α1, α2, …, αn, és β1, β2, …, β m konstansok, amelyekre cij = dij + αi + βj minden 1 ≤ i ≤ n, 1 ≤ j ≤ n értékre. Jelölése: C ~ D. Tétel (Mátrixok ekvivalenciája): Ha C és D n n-es költségmátrixok, és C ~ D, akkor H(C) és H(D) optimális megoldásai megegyeznek. Biz. Legyen zC és zD a két célfüggvény, és legyen megoldás.

egy tetszőleges

Megmutatjuk, hogy létezik egy olyan γ konstans, amelyre

87

1

1

γ 88

Egy mátrix 0 elemeinek egy rendszerét független 0 rendszernek nevezzük, ha a mátrix minden sora és minden oszlopa legfeljebb egy elemet tartalmaz a rendszerből. (Elemeit 0*-gal jelöljük.) Tekintsük azt az eljárást, amely előállít egy olyan C(0), C(1), …, C(k) mátrixsorozatot (k ≤ n), amelyre teljesül, hogy (1) C ~ C(0) (2) C(t) ~ C(t+1), t = 0, 1, 2, …, k-1 (3) C(t) ≥ 0,

t = 0, 1, 2, …, k

(4) C(k) –ban ki van jelölve egy n elemű független 0 rendszer.

89

Tétel: Tegyük fel, hogy van egy ilyen mátrixsorozatunk. Legyen egy olyan n n-es mátrix, amelyre teljesül, hogy

Ekkor

optimális megoldása H(C)-nek.

Biz. lehetséges megoldás (4) miatt. optimális megoldása H(C(k))-nak, mert zk( ) = 0, és (3) miatt, és bármely X lehetséges megoldásra zk(X ) ≥ 0. •

(1) és (2) valamint az ekvivalencia tranzitivitása miatt C ~ C(k). optimális megoldása H(C)-nek is. 90

Magyar módszer Jelölje || 0* || a kijelölt független 0 rendszer elemeinek a számát. Előkészítő rész (Egy független 0 rendszer előállítása): Vonjuk ki a sorminimumokat a sorokból Vonjuk ki az oszlopminimumokat az oszlopokból. Így megkapunk egy C(0) mátrixot. Jelöljünk ki C(0)-ban egy független 0 rendszert. Egy mátrix egy elemét szabad elemnek nevezzük, ha nincs jellel ellátva, és sem a sora sem az oszlopa nincs lekötve.

91

r=0

||0*|| = n

i

VÉGE

Kössük le a 0* oszlopait Van szabad 0 elem? Jelöljük meg '-vel a szabad 0-t 0' sora tartalmaz 0*-t? 0' sorát kössük le, 0* oszlopát oldjuk fel r=r+1

A szabad elemek minimumát levonjuk a szabad elemekből, és hozzáadjuk a kétszeresen kötött elemekhez. Láncképzés:0’oszlopában 0*, 0* sorában 0’. (Jel.: L) C(r+1) elemei: Jelölések nélküli C(r) megjelölése *-gal, ha -

és

-

és 92

Példa: Oldjuk meg a következő hozzárendelési feladatot!

93

Jelöljük ki a független 0 rendszert oszlopfolytonosan: * * * * Kössük le a 0*-k oszlopait!

+ + + + * * * * 94

Keressünk sorfolytonosan szabad 0-t! Ez a c35 elem lesz. Mivel a harmadik sor tartalmaz 0* elemet, ezért a c35 elemet ellátjuk '-vel, a sort lekötjük, a sorában levő 0* oszlopát pedig feloldjuk: + + + + * ' + * * '

*

' + +

Most a c41 lesz az első szabad 0, a negyedik sort lekötjük és a negyedik oszlopot kell feloldani. Keresve szabad 0-t azt kapjuk, hogy a c14 lesz az első szabad 0, az első sort le kell kötni és a harmadik oszlopot kell feloldani. 95

Szabad 0-t keresve most azt látjuk, hogy nincs ilyen elem. Mivel a független 0 rendszerünk csak 4 elemet tartalmaz, ezért – az ekvivalencia tétel felhasználásával – „gyártani” kell szabad 0-t: A szabad elemek minimuma most 1. + + + + * '

+

* * '

*

' + +

Vonjuk le az 1-t a szabad elemekből, és adjuk hozzá a kétszer kötött elemekhez: 96

Most már ismét kereshetünk szabad 0-t. Ez a c21 elem lesz. Ennek sora tartalmaz 0* elemet, ezért a c21 elemet ellátjuk '-vel, a sorát lekötjük, és a harmadik oszlopot feloldjuk: + * ' + '

*

+

* '

*

' + +

Ismét szabad 0-t keresve, c51 lesz az első szabad 0, de a sora nem tartalmaz 0* elemet, ezért a láncképzés indul be: 97

C

(0)

2  0 =  0*   0'  ' 0

4 0* 0' 1   0* 0 0 1  1 0 1 0' 3 0 0* 2   0 0 2 1

+ + + +

Most törölve a jelöléseket, és ”*”-gal ellátva a láncon kívüli 0* elemeket, valamint ”*”-gal ellátva a láncon belüli 0' elemeket, megkapjuk a a C(1) mátrixot.

98

C (1)

2  0 = 0  0  * 0

4 0* 0 1   0* 0 0 1  1 0 1 0* 3 0 0* 2   0 0 2 1

Mivel C(1)-ben 5 elemű a független 0 rendszer, ezért az eljárás véget ér. Most már csak az X megoldásmátrix előállítása van hátra:

99

0  0 X =  0 0  1

0 1 0 0  1 0 0 0 0 0 0 1  0 0 1 0  0 0 0 0

Ezért a célfüggvény értéke:

100

Szállítási feladat Adottak feladóhelyek (raktárak), amelyekben azonos árú áll rendelkezésre különböző mennyiségben. Adottak továbbá felvevőhelyek (igények), amelyekben előírt mennyiségekben árúra van szükség. Szállítsuk el a raktárakban levő árút a felvevőhelyekre úgy, hogy a szállítási költségek összege minimális legyen. n

A dolgozók száma

ai

Az i. raktárban lévő árumennyiség. (i = 1,2,…,n)

m

Az igények száma

cij

Egységnyi anyagmennyiség szállítási költsége az i. raktárból a j. felvevőhelyre. (1 ≤ i ≤ n, 1 ≤ j ≤ m) Az i. raktárból a j. felvevőhelyre szállítandó árumenynyiség. (1 ≤ i ≤ n, 1 ≤ j ≤ m)

xij

101

A matematikai modell

i = 1, 2, …, n j = 1, 2, …, m 1 ≤ i ≤ n, 1 ≤ j ≤ m

102

Megoldható a feladat? Tétel (Egyensúlyi feltétel): A szállítási feadatnak akkor és csak akkor létezik optimális megoldása, ha és

A korábbiakból látható, hogy egy szállítási feladatot meghatározza az a és b vektor, valamint a C költségmátrix. Jelöljük az így meghatározott szállítási feladatot S(a, b, C)-vel. Tétel: Ha a C és D mátrixok ekvivalensek, akkor az S(a, b, C) és S(a, b, D) feladatok optimális megoldásai megegyeznek. A következőkben feltételezzük, hogy az a, b, C elemei egész számok. 103

Tekintsük a következő eljárást (Ford-Fulkerson, 1956): Előállítunk egy olyan mátrixsorozatot, amelyre (1) C ~ C(0) (2) C(t) ~ C(t+1), t = 0, 1, 2, …, k-1 (3) C(t) ≥ 0,

t = 0, 1, 2, …, k

(4) X(t) ≥ 0, és X(t) egész, t = 0, 1, 2, …, k (5) Ha 0 ≤ t ≤ k, akkor (6) Bármely 1 ≤ i ≤ n, 1 ≤ j ≤ m, 1 ≤ t ≤ k indexháromasra következik, hogy (7) Ha

akkor

-ból

bármely 0 ≤ t < k.

(8) ∆k = 0. 104

Tétel: A bemutatott eljárás feltételeit kielégítő mátrixsorozat esetén X(k) optimális megoldása az S(a, b, C) szállítási feladatnak. Biz: ∆t definíciója miatt, és a (4), (5), (8) feltételek teljesülése miatt ahol Lk az S(a, b, C(k)) szállítási feladat lehetséges megoldásainak a halmaza. Ha zk az S(a, b, C(k)) célfüggvénye, akkor (6) miatt

.

(3) miatt bármely lehetséges megoldásra zk(X) ≥ 0, ezért X(k) optimális megoldása S(a, b, C(k))-nak. (1), (2) és az ekvivalencia tranzitivitása miatt C ~ C(k). Ezért X(k) optimális megoldása S(a, b, C)-nek is. 105

Hogyan lehet az (1) – (8) feltételeket kielégítő mátrixpár-sorozatot előállítani? Ford – Fulkerson (1956): A hozzárendelési feladatra kidolgozott gondolatmenet alapján megalkotta a magyar módszert a szállítási feladat megoldására. Előkészítő rész: C(0)-ban 0 elemek előállítása sorminimumok és oszlopminimumok segítségével. X(0) előállítása (mohó algoritmus segítségével)

106

r=0

Paraméterek kiszámítása ∆r = 0

i

VÉGE

Van szabad 0 elem?

Ekvivalencia lépés

i. sorban Jelöljük meg '-vel a szabad 0-t Láncképzés kössük le az i. sort. ha és és az s. oszlop le van kötve, akkor oldjuk fel az s. oszlopot, és jelöljük *-gal.

r=r+1

107

Paraméterek kiszámítása:

Ekvivalencia-lépés: A szabad elemek minimumát levonjuk a szabad elemekből, és hozzáadjuk a kétszeresen kötött elemekhez. Láncképzés: 0’ oszlopában 0*, 0* sorában 0’ választása.

108

Példa: Oldjuk Meg a következő S(a,b, C) szállítási feladatot!

Először az előkészítő részben – a sorminimumok és az oszlopminimumok segítségével – kiszámítjuk C(0)-t: X (0)

0 3 0 0 0   =  0 0 2 0 2 2 1 0 0 0  

Most C(0) alapján megkonstruáljuk az X(0) mátrixot: 109

Mivel az iterációs részben mindig mátrixpárral dolgozunk, ezért a továbbiakban ezeket adjuk meg. + + + + 0 3 0 0 0   (0) X =  0 0 2 0 2 2 1 0 0 0   Következik a paraméterek kiszámítása: Ezért az oszloplekötésekkel folytatódik az eljárás. Ehhez ki kell számolnunk a a szükségletek és a szállítandó mennyiségek eltéréseit a

képlet alapján. Kapjuk δ1 = δ2 = δ3 = δ5 = 0, ezért ezeket az oszlopokat lekötjük. 110

Most – az algoritmus szerint – sorfolytonosan keresünk szabad 0-t. Az első szabad 0 elem . Megvizsgálva X(0) első sorára a készlet és a szállítandó mennyiségek eltérését, kapjuk, hogy azaz X(0) első sorára teljesül a szállítás. Ellátjuk vesszővel a elemet, lekötjük a sorát, a sorában megvizsgáljuk az elemeket. Azt látjuk, hogy és C(0) második oszlopa le van kötve. Ezért ezt az oszlopot feloldjuk, és a elemet *-gal látjuk el: + + + *

'

+

+ X (0)

0 3 0 0 0   =  0 0 2 0 2 2 1 0 0 0   111

Több ilyen elem nincs az első sorban. Ezért ismét szabad 0-t keresünk. Az első szabad elem lesz. Kiszámolva a különbséget kapjuk, hogy következik:

-t vesszővel kell ellátni, és a láncképzési lépés

+ + + * '

'

+ +

X ( 0)

0 3 0 0 0   =  0 0 2 0 2 2 1 0 0 0  

Most X(0) és a lánc alapján elkészítjük X(1)-t. Ehhez ki kell számítanunk Θ értékét. Ehhez először ρ értékét határozzuk meg, amely a láncba tartozó 0*-knak megfelelő x értékek minimuma. Most egyetlen ilyen elem van, ezért ρ = 3. 112

Másrészt venni kell a lánc kezdő elemének sorindexét, és az X(0)-ban ehhez a sorhoz tartozó lehetséges növekményt: Ezután még venni kell a lánc befejező elemének oszlopindexét (ez 4), és meg kell határozni az oszlopeltérést: Ezért Állítsuk elő a (C(1), X(1)) mátrix-párt: + + +

+ X (1)

0 2 0 1 0   =  0 0 2 0 2 2 2 0 0 0  

Mivel ∆1 = 1, ezért ismét oszloplekötésekkel folytatódik az eljárás. δ1= δ2= δ3= δ5= 0, ezért az indexeknek megfelelő oszlopokat lekötjük. 113

Sorfolytonosan az első szabad 0 elem. Mivel ezért -et ellátjuk vesszővel, a sorát lekötjük, majd a C (1) második oszlopát feloldjuk, és -et ellátjuk *-gal. + + + *

'

+

+ X ( 1)

*

'

+

0 2 0 1 0   =  0 0 2 0 2 2 2 0 0 0  

Több elemet nem lehet ellátni *-gal ebben a sorban, ezért sorfolytonosan 0-t keresünk. Sorfolytonosan az első szabad elem. Mivel ezért -et ellátjuk vesszővel, a sorát lekötjük, majd a C (1) első oszlopát feloldjuk, és -et ellátjuk *-gal. Mivel nincs szabad 0, ezért az ekvivalencia lépéssel folytatjuk az eljárást. 114

+ + + *

'

+

+ X (1)

*

'

+

0 2 0 1 0   =  0 0 2 0 2 2 2 0 0 0  

Kössük le a sorokat és az oszlopokat. A szabad elemek minimuma 1, ezt kivonjuk a hozzáadjuk a kétszer kötött elemekhez: + + + + * ' 0 +  (1) X = 0 2 * ' + 

szabad elemekből és 2 0 1 0  0 2 0 2 2 0 0 0  115

Ismét szabad 0-t keresve, lesz az első szabad 0. ezért az eljárás a láncképzéssel folytatódik. Lássuk el vel. + + + + * ' 0 2 0 +  ( 1 ) ' X = 0 0 2 2 2 0 * ' + 

Mivel -et vessző1 0  0 2 0 0 

A C(1) negyedik oszlopában nincs 0*, ezért a lánc elfajuló, csak egyetlen elemet tartalmaz. Számoljuk ki most is először Θ-t. és ezért Θ = 1. Így a lánc alapján az X(1) mátrixnak csak a (2,4) indexű eleme változik meg.

116

X (2)

0 2 0 1 0   =  0 0 2 1 2 2 2 0 0 0  

Képezzük most ∆2 –t. Azt kapjuk, hogy ∆2 = 0, ezért az eljárás véget ér. A feladat optimális megoldásához tartozó célfüggvényérték: X ( 2)

0 2 0 1 0   =  0 0 2 1 2 2 2 0 0 0  

117

A potenciálok módszere Tekintsük a következő szállítási feladatot: K1

5

K2

4

20

3

K3

8

70

3

Igény (b)

F3

F2

F1 8

90

40

4

10

3

6

20

4

7 40

Készlet (a)

F4 40

80 70

8 30

50

40

200

Keressünk egy kiinduló megoldást a mohó algoritmussal! Így az összes költség: 8·70 + 4 ·20 + 3 ·40 + 6 ·20 + 4 ·10 + 3 ·40 = 1040 Az összesen n + m -1 = 6 helyre allokáltunk szállítást. 118

Vezessük be segédváltozóként az ui és a vj potenciálokat, úgy, hogy a költségmátrixban szereplő a lekötött elemekre cij = ui+vj legyen. Írjuk ezeket a lekötött elemek oszlopa elé ill. sora fölé. A potenciálok közül egyet szabadon választhatunk meg. Legyen u2 = 0. v3 = 6

v4 = 5

v1 = 4

v2 = 3

u1 = -2

5

8

4

3

50

u2 = 0

4

3

6

4

u3 = 4

8

3

7

8

80 70

Igény (b)

90

40

30

40

Készlet (a)

200

Számítsuk ki a nem lekötött relációkra a cij – (ui+vj) különbségeket: 119

c11 – (u1+v1) = 5 – (-2 + 4) = 3 c12 – (u1+v2) = 8 – (-2 + 3) = 7 c32 – (u3+v2) = 3 – (4 + 3) = -4 c33 – (u3+v3) = 7 – (4 + 6) = -3 c24 – (u2+v4) = 4 – (0 + 5) = -1 c34 – (u3+v4) = 8 – (4 + 5) = -1

előjele előjele előjele előjele előjele előjele

+ + – – – –

Vizsgáljuk meg ezek után, hogy a nem lekötött relációk esetén hogyan alakul a cij – (ui+vj) különbség. Ha ez 0, ez azt jelenti, hogy annak relációnak a lekötése nem változtatna a költségeken. Ha ez a különbség pozitív, akkor ennek a relációnak a bevonása növelné a költségeket. Ha negatív, akkor ennek a relációnak a bevonása csökkentené a költségeket. 120

Miután több negatív különbséget is kaptunk, a program, vagyis a költség csökkenthető, ha a negatív előjelű relációk közül lekötünk. A legnegatívabb a T3→F2 viszonylat adódott, ennek lekötése csökkentené leginkább a költségeket. Ha ezt a viszonylatot lekötjük egy x mennyiséggel, akkor ez hiányozni fog az előbbi lekötések közül. Vagyis át kell rendeznünk a korábbi elosztási rendet egy kör mentén. x értékét úgy kell megválasztani, hogy ezáltal egy addig kötött elemhez 0 mennyiség kerüljön, és így a kötöttsége megszűnjön. Pl. x = 40-t választva a T2→F2 reláció kötöttsége megszűnik.

121

v3 = 6

v4 = 5

v1 = 4

v2 = 3

u1 = -2

5

8

4

10

3

u2 = 0

4

2060+x

3 400-x

6

20

4

u3 = 4

8

30-x 70

3

7

Igény (b)

90

40 +x 40

Készlet (a)

40

50 80 70

8 30

40

200

Az új program költsége: 4 · 60 + 8 · 30 + 3 · 40 + 4 · 10 + 6 · 20 + 3 · 40 = 880. Tekintsük most az új helyzetet, és jelöljük be az új kötött relációkat.

122

Nézzük a további javítás lehetőségét: c11 – (u1 + v1) = 5 – (0 + 2) = 3 c12 – (u1 + v2) = 8 – (0 – 3) = 11 c23 – (u2 + v3) = 3 – (2 - 3) = 4 c33 – (u3 + v3) = 7 – (6 + 4) = -3 c24 – (u2 + v4) = 4 – (2 + 3) = -1 c34 – (u3 + v4) = 8 – (6 + 3) = -1

az előjel az előjel az előjel az előjel az előjel az előjel

+ + + – – –

A program ugyan jobb lett, mint korábban, a szállítási költség kevesebb, de mivel még vannak negatív különbségek, ezért tovább javítható. Most a legnagyobb javítást a T3→F3 reláció bevonása ígéri, ezért – a korábbi elvekhez hasonlóan – növeljük meg ezt a relációt egy x mennyiséggel. 123

v3 = 6

v4 = 5

v1 = 4

v2 = 3

u1 = -2

5

8

4

10

3

u2 = 0

4

60+x

3

6

20-x

4

80

u3 = 4

8

30-x

3

7

+x

8

70

Igény (b)

90

40 40

30

40

40

Készlet (a) 50

200

Most x = 20 a helyes választás ahhoz, hogy egy lekötött pozíción 0-t kaphassunk.

124

v3 = 6

v1 = 4

v2 = 3

u1 = -2

5

8

4

u2 = 0

4

80

3

6

u3 = 4

8

10

3

Igény (b)

90

40

10 20

7

40

30

v4 = 5 3

Készlet (a)

40

50

4

80

8

70 40

200

Az új program költsége: 4 · 80 + 8 · 10 + 3 · 40 + 4 · 10 + 7 · 20 + 3 · 40 = 820. Számítsuk ki ismét az új potenciálokat:

125

v3 = 7

v1 = 8

v2 = 3

u1 = -3

5

8

4

u2 = -4

4

80

3

6

u3 = 0

8

10

3

Igény (b)

90

40

20

7

40

c11 – (u1+v1) = 5 – (-3 + 8) = 0 c12 – (u1+v2) = 8 – (-3 + 3) = 8 c22 – (u2+v2) = 3 – (-4 + 3) = 1 c23 – (u2+v3) = 6 – (-4 + 7) = 3 c24 – (u2+v4) = 4 – (-4 + 6) = 2 c34 – (u3+v4) = 8 – (0 + 6) = 2

10

30 előjele előjele előjele előjele előjele előjele

v4 = 6 3

40

Készlet (a) 50

4

80

8

70 40

200

+ + + + + +

Mivel minden le nem kötött potenciál értéke pozitív, ezért a megoldásunk tovább nem javítható. 126

Diszkrét Matematika. Galambos Gábor SZTE-JGYPK

Recommend Documents