Lineáris algebrai alapok Will 2010. június 16.
Vektorterek, mátrixok, lineáris egyenletrendszerek. A lineáris programozási feladat, szimplex algoritmus.
Vektorterek Jellemzés: Vektorok tulajdonságai •
Két vektor egyenl®, ha hosszuk és irányuk egyenl®,
•
Vektorok összeadása kommutatív és asszociatív (kivonás is de niált m¶velet),
•
Skalárral szorzás (λ
∈ R : λa)
asszociatív (skalár tagokra), kommutatív, disztributív (skalárokra,
vektorokra),
•
két vektor párhuzamos (kollineáris,
k),
•
két vektor egysíkú (koplanáris), ha elhelyezhet®k egy síkban.
ha egy egyenesre illeszthet®ek,
Tétel: Síkbeli tétel {a, b, c egysíkúak, a ∦ b} ⇒ ∃!α, β ∈ R : c = αa + β b Tétel: Térbeli tétel
{a, b, c, v|a, b, c
páronként nem egysíkúak}
⇒ ∃!α, β, γ ∈ R : v = αa + β b + γ c
De níció: Lineáris összefüggés Legyenek
a1 , . . . , ak
térvektorok, és
•
lineárisan összefügg®ek, ha
•
lineárisan függetlenek, ha
λ 1 , . . . , λ k ∈ R.
a
Pk
i=1 λi i
Pk
a
i=1 λi i
= 0,
és
Ekkor:
∃λi 6= 0
= 0 ⇔ ∀λi = 0
Ezek a de níciók tetsz®leges számtest feletti tetsz®leges vektorterekre kib®víthet®ek.
De níció: Skaláris szorzat def. ab ⇐⇒ |a||b| cos γ(a, b) Tulajdonságai:
•
ab = ba
•
ab = 0 ⇔ a ⊥ b
•
vektorosan nem asszociatív(!), de skalárisan igen ((
•
disztributív a vektorösszeadásra nézve ( (
ab)c 6= a(bc), de λ(ab) = (λa)b = a(λb))
a b + c) = ab + ac) 1
i j k legyenek páronként mer®leges egységvektorok, amelyek jobbrendu, v vektorok olyanok, hogy u = α1 i + α2 j + α3 k, v = β1 i + β2 j + β3 k. Ekkor:
Következménye a tulajdonságoknak: , , szert alkotnak. Legyenek
•
uv = α1 β1 + α2 β2 + α3 β3
•
u, v 6= 0: cos γ(u, v) =
2β 2 +α3 β3 √ √α1 β2 1 +α = 2 2 2 2 2
α1 α2 α3 ·
β1 β2 β3
uv uv
| || |
De níció: Számtest Egy
•
A
számhalmaz a (+, ·) binér m¶veletekkel test, ha:
+ kommutatív, asszociatív, minden elemnek van inverze, amivel a nullelemet adják ki (0),
• ·
kommutatív, asszociatív, minden elemnek van inverze, amivel az egységelemet adják ki (1),
• ∀x, y ∈ A : xy = 0 ⇔ x = y = 0, • ·
az +-ra nézve disztributív (x(y
De níció: Vektortér Legyen adott
V 6= ∅, T
számtest;
+ z) = xy + xz ).
a, b, . . . ∈ V , α, β, . . . ∈ T . Ekkor V
vektortér
T
felett
⊕,
m¶veletekkel,
ha: I
• ⊕:V ×V →V • ∀a, b ∈ V : a ⊕ b = b ⊕ a
• ∀a, b, c ∈ V : (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c) • ∃0 ∈ V : ∀a ∈ V : 0 ⊕ a = a
• ∀a ∈ V : ∃(−a) ∈ V : (−a) ⊕ a = 0 II
• :T ×V →V • λ, µ ∈ T, a ∈ V : (λµ) a = λ (µ a)
• λ, µ ∈ T, a ∈ V : (λ + µ) a = λ a ⊕ µ a
• λ ∈ T, a, b ∈ V : λ (a ⊕ b) = λ a ⊕ λ b • ∃1 ∈ T : ∀a ∈ V : 1 a = a
Jelölés: ezentúl
⊕ := +
és
:= ·
Tétel: Vektortestekre: a nullelem, az egységelem és az inverz egyértelm¶, és a skalár-vektor szorzás kommutatív (λ
· a = a · λ).
Tétel:
λ ∈ T, a ∈ V : λ · a = 0 ⇔ λ = 0 ∨ a = 0
De níció: Lineáris kombináció Pk Lináris kombináció: i i=1 λi aP Triviális lineáris kombináció:
a
k i=1 0 i
=0
Tétel: Asszociativitás tétele és 1 ≤ i ≤ k : ai ∈ V :
k ∈ Z, k ≥ 1
k X
ai tetsz®leges zárójelezése
= (. . . ((a1 + a2 ) + a3 ) + . . .) + ak
i=1 2
Tétel: Kivonás a, b ∈ V ⇒ ∃!x ∈ V : a + x = b De níció: Bázis Legyen e1 , . . . , en ∈ V . Ekkor: def. 1 ≤ i ≤ n : ei bázis ⇐⇒ ∀j 6= k : ej
lineárisan független
ek -tól és ∀a ∈ V
el®állítható
ei -k valamely lineáris
kombinációjaként.
Tétel: Egységbázis T := R; +, ·
, ahol az
a szokásos (komponensenkénti),
i-edik
elem az 1. Állítás:
V := Rn , ahol n ∈ Z+ . 0 .. . ei := 1 .. . 0
Ekkor legyen
1 ≤ i ≤ n:
ei -k bázist alkotnak V -ben.
Tétel: Bázistranszformáció P 1 ≤ i ≤ n : ei bázis V -ben és a ∈ V : a = nj=1 αj ej . Ekkor tetsz®leges i-re: e1 , . . . , ei−1 , a, ei+1 , . . . , en
Legyen bázis
V -ben ⇔ αi 6= 0.
De níció: Lineáris függés vektortért®l P Legyen ∅ = 6 A ⊆ V . Ekkor v ∈ V lineárisan függ A-tól, ha: ∃a1 , . . . , ak ∈ A, ∃α1 , . . . , αk ∈ T : v = ki=1 αi ai . De níció: Altér W
altere
Jelölése:
V -nek, ha W ⊆ V W 5V.
és
W
vektortér
T
test felett a
+|W , ·|W
m¶veletekre nézve.
Tétel: 6 W ⊆V 1. ∅ = 1. ∅ = 6 W ⊆V 2. ∀a, b ∈ W : a + b ∈ W ⇔ W 5V ⇔ 2. ∀λ, µ ∈ T, ∀a, b ∈ W : λa + µb ∈ W 3. ∀λ ∈ T, ∀a ∈ W : λa ∈ W
De níció:
∅= 6 A ⊆ V : W (A) := {v|v ∈ V, v
lineárisan függ
A-tól}.
Tétel: W (A) 5 V
Tétel: W1 , W2 5 V ⇒ W1 ∩ W2 5 V
De níció: Generálás Legyen
∅= 6 A⊆V.
• hAi:
az
A-t
Ekkor:
tartalmazó alterek metszete (A által generált altér),
• A = {a1 , . . . , ak } ⇒ hAi = ha1 , . . . , ak i
3
hAi = W (A)
• G
generátor rendszer
• B
bázis
•
Legyen
V -ben,
ha
B
W1 , W2 5 V .
V -ben,
ha
hGi = V
egy linárisan független generátorrendszer Ekkor:
hW1 , W2 i = hW1 ∪ W2 i
De níció: Dimenzió def.
dimT V ⇐⇒ V
V -ben minden bázis azonos számosságú). Ekvivalens megfogalmazások: V -ben a maximális lineárisan független vektorok száma dimT V , V -ben a minimális generátorrendszer elemszáma dimT V egy tetsz®leges bázisának elemszáma (tudjuk, hogy
De níció: Vektorrendszer rangja def. ρ(a1 , . . . , an ) ⇐⇒ dimT ha1 , . . . , an i De níció: Véges dimenziós vektortér V
véges dimenziós, ha létezik véges elemszámú generátorrendszere.
Tétel: 1. kicserélési tétel Legyen
V
egy véges dimenziós vektortér, ebben
a1 , . . . , ak lineárisan független vektorok, b1 , . . . , bl pedig egy
generátorrendszer. Ekkor: i) ii)
∃j ∈ {1, . . . , m} : bj , a2 , . . . , ak k ≤ m(L
lineárisan függetlenek
számosássága legfeljebb
G
számossága)
Tétel: 2. kicserélési tétel Legyen
V
egy véges,
n
dimenziós vektortér, ebben
a1 , . . . , ak
lineárisan független vektorok,
egy generátorrendszer. Ekkor: i) ii)
s ≥ 0 : ∃j1 , . . . , js ∈ {1, . . . , m} : a1 , . . . , ak , bj1 , . . . , bjs
bázis
V -ben
m=n
iii)
∀
iv)
|L| = n ⇒ L
lineáris független vektorrendszer kiegészíthet® bázissá bázis
Mátrixok De níció: Mátrix A
egy
n × m-es
mátrix
T
felett (A
∈ T n×m ),
• A : {1, . . . , n} × {1, . . . , m} → T ,
ha:
jelölje:
(i, j) 7→ aij =: i [A]j =: [A]ij
• ∀1 ≤ i ≤ n, 1 ≤ j ≤ m : aij ∈ T Reprezentálása:
A=
a11
. . . a1m
. . .
..
.
. . .
an1 . . . anm
De níció: Vektorm¶veletek λ egy szám, a, b két vektor, amelyeknek koordinátái rendre αi , βi számok. Ekkor:
Legyen
4
b1 , . . . , bl
pedig
•
α1 . . .
β1
def. ⇐⇒ ∀1 ≤ i ≤ n : αi = βi
. . .
=
αn
βn
•
α1 . . .
β1
. . .
αn + βn
βn
αn
α1 + β1
def. =
. . .
+
•
α1
λα1
def. =
. . .
λ·
αn
. . .
λαn
De níció: Mátrixm¶veletek Legyen
A, B ∈ T n×m , λ ∈ T .
Ekkor:
•
a11 + b11
def. A+B =
. . .
. . . a1m + b1m ..
. . .
.
an1 + bn1 . . . anm + bnm • def. λA =
λa11 . . .
. . . λa1m ..
.
. . .
λan1 . . . λanm
De níció: Sor-oszlop szorzás
A ∈ T n×m , x, b ∈ T n . Ekkor: a11 . . . a1m x1 b1 def. .. .. def. . .. . Ax = b ⇐⇒ ... · . = . ⇐⇒ ∀1 ≤ i ≤ n : bi = ai1 x1 + . . . + aim xm . . an1 . . . anm xn bn
Legyen
De níció: Mátrixszorzás Legyen
A ∈ T n×m , B ∈ T m×k .
Ekkor:
def.
∀1 ≤ i ≤ n, 1 ≤ j ≤ k : i [AB]j =
m X l=1
k 6= n ⇒ ∃AB ∈ T n×k , @BA k = n ⇒ ∃AB ∈ T n×n , ∃BA ∈ T m×m n = m = k ⇒ ∃AB, BA ∈ T n×n , AB 6= BA (Weierstrass-delta) De níció: Kronecker-szimbólum
def.
δij = i [In ]j =
1 0
, ha
, ha
i=j i 6= j
5
i [A]ll [B]j
De níció: Egységmátrix In
1
0
... 0
. . .
0 ... = .. . 0 ...
def.
..
.
0
∈ T n×n 0 1
Tétel: A mátrixszorzás asszociatív és disztributív
A ∈ T n1 ×m1 , B ∈ T m2 ×k2 , C ∈ T k3 ×l3 mátrixok. Ekkor: ∃(AB)C ⇔ m1 = m2 ∧ k2 = k3 ⇔ ∃A(BC), továbbá: (AB)C = A(BC) ∃A(B + C) ⇔ m1 = m2 = k3 ∧ k2 = l3 ⇔ ∃AB + AC , továbbá: A(B + C) = AB + AC Legyenek
De níció: Mátrix hatványozása Legyen
A ∈ T n×n .
Ekkor:
• A1 := A • k > 1 : Ak := Ak−1 · A
De níció: Mátrix transzponáltja
A ∈ T n×m . Ekkor A transzponáltja: 3 AT = i [AT ]j := j [A]i
Legyen
T m×n
De níció: Mátrix adjungáltja
A ∈ Cn×m . Ekkor A adjungáltja: 3 A∗ = i [A∗ ]j := j [A]i
Legyen
Cm×n
Tétel:
A ∈ T n×m , B ∈ T m×k ⇒ (AB)T = B T AT A ∈ Cn×m , B ∈ Cm×k ⇒ (AB)∗ = B ∗ A∗
De níció: Speciális mátrixok Legyen
A ∈ T n×n
(vagyis négyzetes). Ekkor
1 ≤ i ≤ n : aii = αi ∈ T
A:
•
diagonális:
•
fels®/alsó bidiagonális: a f®átló feletti/alatti átlóban is vannak elemek
•
tridiagonális: a f®tátló feletti és alatti átlóban is vannak elemek
•
fels®/alsó háromszög:
•
szimmetrikus:
•
antiszimmetrikus:
•
ortogonális:
•
projektor:
A2 = A
•
nilpotens:
∃k ∈ Z+ : Ak = 0
•
invertálható:
•
normális:
és
∀1 ≤ i, j ≤ n : i 6= j : aij = 0
∀1 ≤ i, j ≤ n : i ≶ j : aij = 0
AT = A AT = −A
AT A = In = AAT
∃A−1 : A · A−1 = I = A−1 · A
(esetleg csak jobb vagy balinverz)
A∗ A = AA∗ 6
A∗ A = In = AA∗
•
unitér:
•
önadjungált:
Tétel: LU A∈
T n×n
A∗ = A
felbontás
⇒ ∃L ∈ T n×n
alsó-,
U ∈ T n×n
fels® háromszög mátrix, hogy:
A = LU
De níció: Mátrixok partícionálása Pl.:
A=
, ahol
A ∈ T n×m ,
A11 A12 A13 A21 A22 A23
a partíciók tetsz®leges (megfelel®,
n × m-ben
elfér®, nem feltétlenül azonos, de egymással
kompatibilis) dimenziójúak.
De níció: Rang Oszloprang: Sorrang:
ρo (A) ⇐⇒ dimT ha1 , . . . , am i, def.
def.
ρs (A) ⇐⇒ ρo
Igazolható:
vagyis
A
lineárisan független oszlopainak számossága.
(AT ) def.
ρs (A) = ρo (A) ⇐⇒ ρ(A)
Tétel:
C ∈ T n×m , D ∈ T m×k ⇒ ρ(CD) ≤ ρ(C)
De níció: Rangtartó átalakítások ∀1 ≤ i, j ≤ n : ρ(a1 , . . . , ai , . . . , aj , . . . , an ) = ρ(a1 , . . . , aj , . . . , ai , . . . , an )
•
csere:
•
beszorzás:
•
kombináció:
∀1 ≤ i ≤ n, λ 6= 0 : ρ(a1 , . . . , ai , . . . , an ) = ρ(a1 , . . . , λai , . . . , an ) ∀1 ≤ i, j ≤ n, i 6= j, λ 6= 0 : ρ(a1 , . . . , ai , . . . , an ) = ρ(a1 , . . . , ai + λaj , . . . , an )
Tétel: Inverzek létezése Legyen
A ∈ T n×m .
Ekkor:
i)
A-nak
van jobbinverzve
ii)
A-nak
van balinverzve
iii)
⇔ ρs (A) = n
⇔ ρo (A) = m
∃A−1 ⇔ n = m = ρ(A)
(teljes sorrangú) (teljes oszloprangú)
(négyzetes és teljes rangú)
Tétel: Inverzek készítése Ha
A
nem négyzetes, akkor ha
alakra hozható. Vagyis léteznek
ρ(A) ≥ 1, S, P
akkor véges sok rangtartó átalakítással
invertálható mátrixok, amikre:
e SAP = A
De níció: Általánosított inverz Legyen
A ∈ Cn×n .
Ekkor
i)
AXA = A,
akkor
ii)
XAX = X
és i), akkor
iii)
(AX)∗ = AX ,
X
∃!X ∈ Cn×n :
ún. általánosított inverz
X
ún. re exív általánosított inverz
és i)-ii), akkor
X
ún. normált re exív általánosított inverz
7
e= A
Ir 0 0 0
∈ T n×m
iv)
(XA)∗ = XA,
és i)-ii)-iii), akkor
X
ún. pszeudó-inverz
Az inverzek készítése módszert el®ször alkalmazva nem négyzetes mátrixra is megkaphatóak az általánosított inverzek.
De níció: Mátrixok determinánsa Legyen
A ∈ T n×n .
Ekkor legyen
def.
|A| ⇐⇒ det(A) : A 7→ α ∈ T
Speciálisan:
def.
• n = 1 : A = [a11 ] : |A| = det(A) = a11 a11 a12 def. • n=2:A= : |A| = det(A) = a11 a22 − a12 a21 a21 a22 •
(Sarrus-szabály)
a11 a12 a13 a11 a12 n = 3 : A = a21 a22 a23 a21 a22 = a11 a22 a33 + a12 a23 a31 + a13 a21 a32 − (a13 a22 a31 + a11 a23 a32 + a31 a32 a33 a31 a32 a12 a21 a33 ) Általános esetben:
i1 , i2 , . . . , in az 1, 2, . . . , n számok egy permutációja. Azt mondjuk, hogy (iµ , iν ) inverzióban iµ > iν , µ < ν . Legyen I(i1 , . . . , in ) az i1 , . . . , in permutációban lév® inveriók száma. Ekkor: def. X det(A) = (−1)I(i1 ,...,in ) a1i1 a2i2 · · · akik · · · anin
Legyen
i1 ,...,in
Tétel: Determinánsokra vonatkozó tételek Legyen
A ∈ T n×n ,
ekkor:
• |0| = 0 • ∃1 ≤ k ≤ n : ∀1 ≤ j ≤ n : akj = 0 ⇒ det(A) = 0
(ha van nulla sor, akkor a determináns
• |AT | = |A| • A-ban
két sort cserélve
e = −1|A| det(A)
• A-ban
egy sort beszorozva
lesz
e = λ|A| λ ∈ T -vel: det(A)
lesz
• |λA| = λn |A| • |A + B| = 6 |A| + |B| • |AB| = |A||B| • ρ(A) < n ⇒ |A| = 0 • ρ(A) = n ⇒ |A| = 6 0
(ez egyben újabb feltétel az inverz létezésére!)
• ρ(A) = r ≥ 1 : ∃|r × r| = 6 0
részmátrix, és
∀|(r + 1) × (r + 1)| = 0
Tétel: Vandermonde-determináns ∀n ≥ 2 :
1 a1 a21 . . . an−1 1 1 a2 a2 . . . an−1 2 2 .. .. . . .. . . . . . . . 1 an a2 . . . an−1 n n 8
Y ai − aj = 1≤i,j≤n
0)
van, ha
Tétel: Kifejtési tétel i.
sor szerinti:
|A| =
n X
aij Aij
j=1
j.
oszlop szerinti:
|A| =
n X
aij Aij
i=1 , ahol
Aij
szorozzuk
az adott el®jeles aldetermináns (kiszámítjuk
(−1)i+j -vel
i.
sor,
j.
oszlop nélküli mátrix determinánsát és
(sakktábla-szabály)).
Tétel: Ferde kifejtési tétel Ha az adott sor/oszlop elemeit egy másik sorhoz/oszlophoz tartozó el®jeles aldeterminánssal szorozzuk és adjuk össze, akkor az eredmény mindig
0
lesz:
0 = (k 6= i)
n X
aij Akj = (k 6= j)
j=1
n X
aij Aik
i=1
Lineáris egyenletrendszerek De níció: Lineáris egyenletrendszer (LER) Informálisan:
n
db egyenlet és
a11 x1 a21 x1
m
darab ismeretlen.
+ a12 x2 + a22 x2
. . .
. . .
+ . . . + a1m xm + . . . + a2m xm ..
= b1 = b2
. . .
.
. . .
an1 x1 + an2 x2 + . . . + anm xm = bn
⇔ Ax = b
De níció: Elemi bázistranszformációs algoritmus Egy adott bázisról, adott vektorokkal térjünk át új bázisra, és közben változtassuk a keresett vektort is. Ekkor, ha új bázishoz jutunk, akkor megkapunk egy megoldást is.
De níció: LER általánosítása Legyen
A ∈ T n×m , B ∈ T n×k , X ∈ T m×k .
Ekkor
AX = B
egyenlet átírható
De níció: Cramer-szabály A ∈ T n×n , det(A) 6= 0, b ∈ T n ⇒ ∃!x ∈ T n : Ax = b, és ∀1 ≤ j ≤ n : xj = De níció: Homogén LER
Ax = 0
ún. homogén LER. Ha
i)
Ax = 0
ii)
|A| = 0
A ∈ T n×n ,
iii)
ρ(A) < n
iv)
∃A-nak
legalább két oszlopa, ami lineárisan összefügg
9
darab LER-ré.
a1 ,...,b,...,an ]) a1 ,...,aj ,...,an ])
det([ det([
akkor a következ®k ekvivalensek:
homogén LER-nek létezik nem triviális megoldása
k
A lineáris programozási feladat De níciók: a, x1 , x2 ∈ Rn , a 6= 0, β ∈ R,. Ekkor:
Legyen
H := {x|aT x = β}
•
hipersík:
•
féltér:
•
poliéder: véges sok féltér metszete
•
szakasz:
•
konvex halmaz:
•
támaszsík:
•
F := {x|aT x Q β} [x1 , x2 ] := {x|x = λx1 + (1 − λ)x2 , 0 ≤ λ ≤ 1}
S
S ⊆ Rn
konvex halmaz
⇐⇒ ∀x1 , x2 ∈ S : [x1 , x2 ] ⊆ S def.
konvex halmaz támaszsíkja
extremális pont:
S
H := {x|aT x = β},
zárt konvex halmaz.
x ∈ S
ha
H ∩ S 6= ∅
extremális pont, ha
∃H
és
∀y ∈ S : aT y ≤ β
támaszsíkja
S -nek,
amire:
H ∩ S = {x} •
hipersíkok lineáris függetlensége: két hipersík lineárisan független, ha az ®ket meghatározó vektorok lineárisan függetlenek
•
határoló hipersík: egy poliéder határoló hipersíkjai, azok a hipersíkok, amelyeket a poliédert el®állító félterek vektorai határoznak meg
•
szomszédes extremális pontok: két extremális pont szomszédos, ha létezik határoló hipersík, amely mindkett®t tartalmazza
•
Minkowski összeg:
•
végtelen irány:
P
A, B ⊆ Rn ,
ekkor
A + B := {x|x = a + b, a ∈ A, b ∈ B}
poliéder végtelen iránya
v, ha ∀x ∈ P, ∀λ ≥ 0 : x + λv ∈ P
Tétel: •
A hipersík konvex halmaz
•
Minden féltér konvex halmaz
•
Legyen
•
Minden poliéder konvex halmaz
I
egy indexhalmaz,
∀i ∈ I : Si
legyen konvex halmaz. Ekkor
∩i∈I Si
Tétel: 3 ekvivalens állítás i) ii) iii)
y
a
P
poliéder extremális pontja
@y1 , y2 ∈ P, y1 6= y2 , 0 < λ < 1 : y = λy1 + (1 − λ)y2 y
rajta van a
P
poliéder
n
darab lineárisan független határoló hipersíkján
10
is konvex halmaz
De níció: Lineáris programozási feladat (LP-feladat) Informálisan: lineáris feltételek és egy lineáris célfüggvény összessége.
Legyen
A ∈ Rm×n , b ∈ Rm , c ∈ Rn
adottak. Keressük
rendszerben:
∈ Rn
vektort (ún. döntési vektort) az alábbi
max cT x Ax = b x≥0
Általában feltesszük, hogy
Az
x
ρ(A) = m
(azaz
A
teljes sorrangú).
De níció: LP megoldása x ∈ Rn vektor Ax = b
•
megoldása az LP-nek, ha
•
megengedett megoldása az LP-nek, ha
•
optimális megoldás az LP-nek, ha megengedett megoldás, és
Ax = b, x ≥ 0 ∀y
megengedett megoldásra:
cT y ≤ cT x
De níció: Vektor tartója x ∈ Rn vektor tartója azon indexek halmaza, melyekre xi 6= 0 Jelölése: supp(x) = {i|xi 6= 0}
Egy
De níció: LP bázismegoldása Az LP egy x megoldása bázismegoldás, ha az {aj |j ∈ supp(x)} egy lineárisan független vektorrendszer. Megengedett bázismegoldás, ha megengedett és bázismegoldás is.
Tétel: Minden bázis esetén a hozzátartozó bázismegoldás egyértelm¶. De ez fordítva nem igaz: egy bázismegoldáshoz több bázis is tartozhat. Degenerált LP: ha van olyan bázismegoldás, amit több bázis is meghatároz. Megjegyzés: a gyakorlatban ha
b-t valóban folytonos eloszlás szerint véletlenül választjuk, akkor 0 valószín¶séggel
lesz degenerált a feladat. A degenerált feladatokat a numerikus hibák miatt is kerüljük.
De níció: Megengedett bázis Egy bázis megengedett, ha a hozzá tartozó bázismegoldás megengedett. (azaz
xB = B −1 b ≥ 0)
Tétel:
K := {x ∈ Rn : Ax = b, x ≥ 0}, I := ∪x∈K supp(x) ⇒ ∃y ∈ K : supp(y) = I
Tétel: K 6= ∅ ⇒
az extremális pontok megegyeznek a megengedett bázismegoldásokkal. Azaz ha
extremális pont
⇔
x bázismegoldás.
Tétel:
b B e két bázis, melyek bázismegoldásai x b, x e, B, xb, xe szomszédos extremális pontok.
Legyen Ekkor
és
Szimplex algoritmus De níció: Szimplex algoritmus Legyen
B
egy megengedett induló bázis. Ekkor:
11
x ∈ K , akkor x
e = r − 1, ahol r az A rangja. xb 6= xe, továbbá |Bb ∩ B|
1. Határozzuk meg a redukált árakat: 2.
∃B -n
kívül változó, hogy
3. Legyen
l
p>0
a javító oszlop. Ha
p = c − cTB B −1 A
GOTO 3, ha nem, akkor STOP: optimális megoldásban vagyunk
al ≤ 0
STOP: nem korlátos a célfüggvény (végtelen irány), ha
∃i : ali > 0,
akkor hányados szabállyal keressük meg a csere sorát (k ) 4. Végezzük el a báziscserét (k változó kilép a bázisból,
l
belép) GOTO 1
Tétel: Ha az LP nem degenerált, akkor a szimplex algoritmus véges sok lépésben megáll.
Degeneráció kezelése: 1. Minimálindex szabály: mindig a minimális index¶ javítóoszlop választása 2. Lexikogra kus szimplex: javítóoszlopot tetsz®legesen, sort lexikogra kusan választunk (normálás után) 3. LP perturbálása: a perturbált LP-t megoldjuk, majd azzal a bázissal megoldjuk az eredeti feladatot
Induló bázis el®állítása: x u A I Ax ≤ b x, b ≥ 0
I.
⇔
Ax + I u = b x, b, u ≥ 0
b
Ekvivalens feladatok. A bázis megengedett, a bázismegoldás: II. Ennek az ún. segédfeladatnak a megengedett megoldásának
P ⇔ u = u ≥ 0 ⇒ i ui ≥ 0). megoldásának
0,
tehát
min
P
ui
u
III. Ha a segédfeladatnak van megoldása (
x = 0, u = b
x része része az eredeti feladat megengedett
célfüggvénnyel oldjuk meg a feladatot (ez korlátos, mert
=
b, x
=
0),
és a célfüggvénye korlátos, akkor a szimplex
algoritmus egy optimális megoldást ad. Két eset lehetséges: a) b)
min ui > 0
ekkor az eredeti feladatnak nincs megoldása
min ui = 0 ekkor is el®fordulhat, hogy bizonyos változók bentmaradnak a bázisban. Ezt bázistranszformációval megoldjuk. Ha nem tudjuk kivinni, akkor redundáns feltétel (elhagyható 0-sor)
De níció: Kétfázisú szimplex algoritmus 1) Megengedett bázis keresése (megoldjuk a segédfeladatot). Ha a célfüggvény > 0, akkor STOP: nincs megengedett megoldás. Ha a célfüggvény = 0, akkor GOTO 2 2) A megtalált megengedett bázisból indulva keressünk optimumot
Tétel: Trichotómia tétel Minden LP az alábbi három osztály valamelyikébe tartozik: i)
@
megengedett megoldása
ii)
∃
optimális megoldása (a célfüggvénye korlátos)
iii)
∃
megengedett megoldása, de a célfüggvény nem korlátos
12
De níció: Újrainvertálás A numerikus hibák az iteráció el®rehaladtával egyre inkább el®kerülnek. Ezért egyszer¶en nem engedjük meg, hogy az algoritmus túl sok transzformációs mátrixot tároljon (transzformációs mátrix: amivel a kiinduló mátrixot balról szorozva megkapjuk az iterált mátrixot). Ismerjük a bázisban lév® elemeket: segítségükkel számoljuk ki újra a bázis inverzét, és így csökkenthet®ek a numerikus hibák. Megjegyzés: a gyakorlatban ezt
∼ 50
lépésenként célszer¶ elvégezni.
13
