INVERS TERGENERALISASI MATRIKS ATAS ALJABAR MAXPLUS Musthofa Jurusan Pendidikan Matematika FMIPA UNY
[email protected] Abstrak Jika A matriks atas lapangan, maka pasti terdapat dengan tunggal suatu matriks B yang memenuhi sifat ABA = A. Matriks B yang memenuhi sifat ini disebut invers tergeneralisasi matriks A. Dalam aljabar maxplus, tidak ada jaminan bahwa setiap matriks memiliki invers tergeneralisasi. Jika A mempunyai invers tergeneralisasi, maka A dikatakan reguler. Dalam makalah ini akan dibahas bagaimana menentukan suatu matriks A atas aljabar maxplus regular atau tidak. Kata kunci: Matriks, invers tergeneralisasi, aljabar maxplus, reguler
A. PENDAHULUAN Aljabar maxplus memiliki peranan yang sangat banyak dalam menyelesaikan persoalan di beberapa bidang seperti teori graf, kombinatorika, teori sistem, teori antrian dan proses stokastik. Hal ini telah dibahas dalam beberapa buku dan jurnal seperti Bacelli,et.al (2001), Heidergott, (1999), Fleming, (2004), Menguy, et.al (2000). Sebagai contoh yang sederhana, misal suatu kegiatan dimodelkan dalam graf aktivitas sebagai berikut:
Bobot garis berarah dari titik i ke titik j menyatakan waktu tersingkat yang diperlukan untuk memulai kegiatan pada titik i sampai memulai kegiatan pada titik j,dalam bentuk matriks dinyatakan sebagai Aji. Jika tidak ada garis yang menghubungkan titik i dengan titik j, maka Aji = -∞. Kegiatan pada titik j , baru dapat dimulai jika seluruh kegiatan yang mendahului titik j sudah selesai. Dalam gambar di atas, kegiatan pada titik 4 baru dapat dimulai jika seluruh kegiatan pada titik 2 dan 5 sudah selesai. Jika xj menyatakan waktu tercepat dapat dimulainya kegiatan pada titik j, maka xj dapat dinyatakan sebagai x j = maks( Aji + xi ) . Terlihat bahwa masalah ini melibatkan dua i =1,2,..,6
operasi yaitu maksimum ( maks) dan penjumlahan (+), yang merupakan operasi dalam aljabar maxplus. Dalam aljabar linear, sudah dikenal konsep invers tergeneralisasi suatu matriks atas lapangan. Yaitu, jika A matriks atas lapangan, maka pasti terdapat invers tergeneralisasi matriks A, namakan B, sehingga ABA = A. Untuk itu dalam makalah ini akan dibahas tentang matriks atas aljabar maxplus, khususnya tentang invers tergeneralisasi dari matriks atas aljabar maxplus. Jika A sebarang matriks atas aljabar maxplus, maka belum tentu A mempunyai invers tergeneralisasi. Dalam makalah ini
akan dibahas syarat matriks A
mempunyai invers tergeneralisasi dan sekaligus menentukan invers tergeneralisasi dari matriks A atas aljabar maxplus.
B. PEMBAHASAN 1. Aljabar Maxplus
Aljabar maxplus adalah himpunan R ∪ {-∞}, dengan R himpunan semua bilangan real yang dilengkapi dengan operasi
maksimum, dinotasikan dengan ⊕ dan operasi
penjumlahan, yang dinotasikan dengan ⊗ . Selanjutnya ( R ∪ {-∞}, ⊕, ⊗ ) dinotasikan dengan Rmax dan {-∞} dinotasikan dengan ε. Elemen
ε merupakan elemen netral terhadap
operasi ⊕ dan 0 merupakan elemen identitas terhadap operasi ⊗. Struktur aljabar dari Rmax adalah semifield, yaitu : 1. ( R ∪ {-∞}, ⊕ ) merupakan semigrup komutatif dengan elemen netral {-∞}
2. (R ∪ {-∞}, ⊗ ) merupakan grup komutatif dengan elemen identitas 0 3. Operasi ⊕ dan ⊗ bersifat distributif 4. Elemen netral bersifat menyerap terhadap operasi ⊗ , yaitu ∀ a ∈ Rmax , ε ⊗ a = a ⊗ ε =ε 2. Matriks atas Rmax
Dalam aljabar linear, jika F field, maka dapat dibentuk suatu matriks berukuran m × n dengan entri –entrinya adalah elemen –elemen F. Hal yang serupa dapat dikerjakan pada Rmax , yaitu dapat dibentuk matriks A berukuran m × n dengan entri-entrinya elemen Rmax. Operasi ⊕ dan ⊗ pada matriks atas aljabar maxplus didefinisikan sebagai berikut: (1) ( A ⊕ B)ij = Aij ⊕ Bij (2) ( A ⊗ B )ij = ⊕( Aik ⊗ Bkj ) k
Contoh : ⎡1 2 ⎤ ⎡ -2 7 ⎤ Jika A = ⎢ dan B = ⎢ ⎥ ⎥ , maka ⎣ -2 3 ⎦ ⎣1 -3⎦ ⎡1 2 ⎤ ⎡ -2 7 ⎤ ⎡1 ⊕ -2 2 ⊕ 7 ⎤ ⎡1 7 ⎤ A⊕ B = ⎢ ⎥⊕⎢ ⎥=⎢ ⎥=⎢ ⎥ dan ⎣ -2 3 ⎦ ⎣1 -3 ⎦ ⎣ -2 ⊕ 1 3 ⊕ −3⎦ ⎣1 3 ⎦ ⎡{1+(-2)} ⊕ {2 + 1} {1+7} ⊕ {2 + (−3)} ⎤ ⎡3 8 ⎤ A⊗ B = ⎢ ⎥=⎢ ⎥ ⎣{-2+(-2)} ⊕ {3 + 1} {-2+7} ⊕ {3 + (−3)}⎦ ⎣ 4 5⎦ Jika ( Rmax)n
× n
menyatakan himpunan semua matriks dengan entri-entrinya elemen Rmax, ,
⎧0, jika i = j maka matriks E dengan ( E )ij = ⎨ dan matriks ⎩ε , jika i ≠ j
ε dengan (ε)ij = ε,∀
berturut– turut merupakan matriks identitas dan matriks nol. Jadi , (1) ( E ⊗ A ) = (A ⊗ E ) = A untuk setiap A ∈( Rmax)n × n ; (2) (ε ⊕ A ) = (A ⊕ ε ) = A, untuk setiap A ∈ ( Rmax)n × n.
i, j
Perlu diperhatikan bahwa ( Rmax)n × n bukan merupakan semifield, tetapi merupakan semiring, sebab terhadap operasi ⊗ ( Rmax)n × n tidak komutatif dan tidak setiap A ∈ ( Rmax)n × n mempunyai invers .
3. Pemetaan Residuated Pada R
max
dapat dilengkapkan suatu relasi urutan ≤ , yaitu a ≤ b ⇔ a ⊕ b = b.
Sehingga (Rmax , ≤ ) merupakan poset ( himpunan terurut parsial ).
Definisi 1. Suatu pemetaan f pada himpunan teurut parsial dikatakan isoton jika x ≤ y ⇒ f(x) ≤ f(y) Contoh 1. f : Rmax → Rmax dengan f(x) = x ⊗ 5 merupakan pemetaan isoton, yaitu untuk setiap x, y ∈ Rmax berlaku x ≤ y ⇒ f(x) = x ⊗ 5 = x + 5 ≤ y + 5 = y ⊗ 5 = f(y)
Definisi 2. Suatu pemetaan isoton f : D → E dengan D dan E masing-masing himpunan terurut parsial dikatakan pemetaan residuated jika untuk setiap b ∈ E, maka { x / f(x) ≤ b} mempunyai elemen maximal, dinotasikan dengan f#(b).Pemetaan isoton f#: E → D disebut residual dari f. Contoh 2. Pada contoh 1 di atas, f merupakan pemetaan residuated , sebab untuk setiap y ∈ Rmax, {x/f(x) = x ⊗ 5 ≤ y }mempunyai elemen maximal, yaitu x = f#(y) = y-5. Hubungan antara f dan f# seperti yang dibahas dalam bacilli, et.al (2001) adalah sebagai berikut: f ο f# ≤ I f# ο f ≥ I Selanjutnya residual dari f#(b)
(1a) ( 1b)
digunakan untuk menentukan ada tidaknya solusi dari
persamaan f(x) = b, dinyatakan dalam teorema sebagai berikut:
Teorema 3. Jika f : D → E pemetaan residuated, maka persamaan f(x) = b mempunyai solusi jika dan hanya jika f ( f#(b)) = b. Bukti :
( ⇐) Diketahui f(f# (b)) = b, maka persamaan f(x) = b mempunyai solusi, yaitu x = f# (b) (⇒ ) Diketahui f(x) = b mempunyai solusi, misalkan x1 . Diperoleh f(x1) = b. Karena f# (b) adalah elemen maksimal dalam { x/ f(x) ≤ b}, maka x1 ≤ f# (b). Karena f isoton maka f(x1) ≤ f( f# (b)). Menurut (1a) f f# (b) ≤ b, akibatnya b = f(x1) ≤ f f# (b) ≤ b, yaitu f(f# (b)) = b.
4. Penyelesaian Persamaan Ax = b dalam Aljabar Maxplus ⎡ A11 ( x1 ) ⊕ A12 ( x2 ) ⊕ ... ⊕ A1n ( xn ) ⎤ ⎢ A ( x ) ⊕ A ( x ) ⊕ ... ⊕ A ( x ) ⎥ 22 2 2n n ⎥ . Jika A ∈ ( Rmax)n × n dan x ∈ Rnmax , maka Ax = ⎢ 21 1 ⎢.................................................. ⎥ ⎢ ⎥ ⎢⎣ An1 ( x1 ) ⊕ An 2 ( x2 ) ⊕ ... ⊕ Ann ( xn ) ⎥⎦
⎡ A1 j ( x j ) ⎤ ⎢ ⎥ n A2 j ( x j ) ⎥ ⎢ Dibentuk f j ( x j ) = ⎢ Ax = ⊕ f j (x j ) , maka j =1 ............ ⎥ ⎢ ⎥ ⎢⎣ Anj ( x j ) ⎥⎦
(2)
Untuk setiap j, jika x jh ≤ x jk ⇒ f j ( x jh ) ≤ f j ( x jk ) .Sehingga A merupakan pemetaan isoton. Selain itu untuk setiap j,
{ x j / f j ( x j ) ≤ b } mempunyai elemen maksimal, yaitu
x j = min {b1 – A1j, b2 – A2j, …, bn – Anj }. Jadi A merupakan pemetaan residuated. Dengan kata lain. A dapat dipandang sebagai suatu pemetaan residuated dari Rnmax ke Rnmax . Berdasarkan uraian ini, yaitu karena x j = min {b1 – A1j, b2 – A2j, …, bn – Anj }, maka residual dari A adalah [ A# (b)] j = min(b j − Aij ) . 1≤i ≤ n
Sehingga untuk menentukan solusi persamaan Ax = b, seperti pada pembahasan pada teorema 3, dapat dilakukan dengan mengecek apakah A ( A#(b)) = b. Hal ini dinyatakan dalam teorema di bawah ini. Teorema 4. Jika A ∈ ( Rmax)n × n , dan b ∈ Rnmax , maka persamaan Ax = b mempunyai solusi
jika dan hanya jika A(A#(b))= b. Bukti : (⇐)
Diketahui A(A# (b)) = b. Jadi persamaan Ax = b mempunyai penyelesaian , yaitu x = A#(b) (⇒ ) Misalkan persamaan Ax = b mempunyai solusi x•. diperoleh A x• = b, sehingga A x• ≤ b. Karena A#( b) merupakan elemen maksimal dalam { x/ Ax ≤ b ) maka x• ≤ A# (b). Diperoleh A x• ≤ A ( A# (b )) ⇔
b = A x• ≤ A ( A\b) ………(*)
Selanjutnya menurut (1a) A (A\b) ≤ b………………...(**) Dari (*) dan (**) diperoleh A ( A# (b)) = b.
5. Invers Tergeneralisasi Matriks atas Aljabar Maxplus
Salah satu tujuan mencari invers tergeneralisasi matriks atas lapangan , seperti dalam Penrose, (1954) adalah untuk menentukan solusi sistem persamaan linear AXB = C. Berikut ini definisi invers tergeneralisasi matriks atas aljabar maxplus, seperti definisi yang ditulis oleh Blyumin dan Goland, (2001). Definisi 5.
Jika A ∈ ( Rmax)n
, maka matriks B ∈ ( Rmax)
× m
m ×n
dikatakan invers
tergeneralisasi dari matriks A( atau g-invers dari A) jika ABA=A. Untuk menentukan ada tidaknya matriks B yang memenuhi ABA = A, ekuivalen dengan menentukan ada atau tidaknya solusi persamaan AXA = A dengan A ∈ ( Rmax )n × m . Elemen ke-ij pada AXA adalah
m
n
[ AXA]ij = ⊕[⊕( Aik + X kl + Alj )] . Sehingga diperoleh k =1 l =1
persamaan m
n
⊕[⊕( Aik + X kl + Alj )] = Aij
(3)
fij ( X kl ) = Aik + X kl + Alj
(4)
k =1 l =1
Jika untuk setiap k,l dibentuk
maka persamaan (3) menjadi n
m
⊕ ⊕ fij ( X kl ) = Aij i =1 j =1
(5)
Elemen maksimal dalam { X kl / fij ( X kl ) ≤ Aij } adalah n
{
}
m
X kl• = min min Aij − ( Aik + Alj ) i =1
j =1
Selanjutnya akan dibahas syarat suatu matriks
A ∈ ( Rmax)n
(6) × m
mempunyai invers
tergeneralisasi yang disajikan dalam teorema berikut: Teorema 6. Matriks A ∈ ( Rmax)n × m mempunyai invers tergeneralisasi jika dan hanya jika
elemen maksimal dalam { X / AXA ≤ A } merupakan solusi persamaan AXA = A. Bukti : (⇐ ) Jika X# = max { X / AXA ≤ A } merupakan solusi persamaan AXA = A, maka jelas A mempunyai invers tergeneralisasi, yaitu matriks X#. (⇒ ) Jika A mempunyai invers tergeneralisasi, maka terdapat matriks X1 sedemikian sehingga AX1A = A. Jika X# = max { X / AXA ≤ A }, maka X1 ≤ X#, sehingga AX1A ≤ AX#A. Akibatnya A = AX1A ≤ AX#A ≤ A. Jadi diperoleh AX#A = A, dengan X# = max { X / AXA ≤ A }. Selanjutnya jika A ∈ A ∈ ( Rmax)n
× m
mempunyai invers tergeneralisasi, maka A
dikatakan regular, jika tidak maka A dikatakan nonreguler. Jika A regular, maka invers tergeneralisasi dari A belum tentu tunggal. Contoh : ⎡ 2 3⎤ Akan ditentukan invers tergeneralisasi dari matriks A = ⎢ ⎥. ⎣1 2 ⎦ Menurut persamaan (6), diperoleh: 2
{
2
X 11# = min min Aij − Ai1 − A1 j i =1
j =1
}
= min {( A11 − A11 − A11 );( A12 − A11 − A12 ); ( A21 − A21 − A11 ); ( A22 − A21 − A12 )}
= min { (2-2-2); ( 3-2-3);(1-1-2);(2-1-3)} = min { -2; -2; -2; -2} = -2.
2
{
2
X 12# = min min Aij − Ai1 − A2 j i =1
j =1
}
= min {( A11 − A11 − A21 );( A12 − A11 − A22 ); ( A21 − A21 − A21 ); ( A22 − A21 − A22 )}
= min { (2-2-1);(3-2-2);(1-1-1);(2-1-2)} = min { -1; 0; -1; -1 } = -1 2
{
2
X 21# = min min Aij − Ai 2 − A1 j i =1
j =1
}
= min {( A11 − A12 − A11 );( A12 − A12 − A12 ); ( A21 − A22 − A11 ); ( A22 − A22 − A12 )}
= min { (2-3-2);(3-3-3);(1-2-2);(2-2-3)} = min { -3; -3; -3; -3 } = -3 2
{
2
X 22# = min min Aij − Ai 2 − A2 j i =1
j =1
}
= min {( A11 − A12 − A21 ); ( A12 − A12 − A22 );( A21 − A22 − A21 );( A22 − A22 − A22 )}
= min { (2-3-1);(3-3-2);(1-2-1);(2-2-2)} = min { -2; -2; -2; -2 } = -2 ⎡-2 -1 ⎤ # Diperoleh X # = ⎢ ⎥ . Selanjutnya dicek apakah AX A = A. -3 -2 ⎣ ⎦ ⎡ 2 3⎤ ⎡-2 -1 ⎤ ⎡ 2 3⎤ ⎡ 0 1 ⎤ ⎡ 2 3⎤ ⎡ 2 3⎤ AX # A = ⎢ ⎥⎢ ⎥= ⎢ ⎥ = A. ⎥⎢ ⎥⎢ ⎥= ⎢ ⎣1 2 ⎦ ⎣-3 -2 ⎦ ⎣1 2 ⎦ ⎣ -1 0 ⎦ ⎣1 2 ⎦ ⎣1 2 ⎦ ⎡ 2 3⎤ ⎡ -2 -1 ⎤ Jadi matriks A = ⎢ regular, dengan invers tergeneralisasinya adalah X # = ⎢ ⎥ ⎥. ⎣1 2 ⎦ ⎣ -3 -2 ⎦ ⎡ -3 -1 ⎤ Dapat dicek juga bahwa X 1 = ⎢ ⎥ juga memenuhi AX1A=A, yaitu ⎣ -3 -2 ⎦ ⎡ 2 3⎤ ⎡-3 -1 ⎤ ⎡ 2 3⎤ ⎡ 0 1 ⎤ ⎡ 2 3⎤ ⎡ 2 3⎤ AX 1 A = ⎢ ⎥⎢ ⎥⎢ ⎥=⎢ ⎥⎢ ⎥=⎢ ⎥=A ⎣1 2 ⎦ ⎣-3 -2 ⎦ ⎣1 2 ⎦ ⎣ -1 0⎦ ⎣1 2 ⎦ ⎣1 2 ⎦
C. KESIMPULAN DAN SARAN
Jika A ∈ (Rmax)n
× m
, maka untuk menentukan invers tergeneralisasi dari matriks A
dilakukan dengan menentukan matriks X# yang entri ke- kl - nya adalah n
{
m
X kl# = m in m in Aij − ( Aik + Alj ) i =1
j =1
}.
Jika matriks X# memenuhi AX#A=A, maka A mempunyai invers tergeneralsasi atau A dikatakan regular. Jika X# tidak memenuhi AX#A=A, maka pasti A tidak mempunyai invers tergeneralisasi, atau A nonreguler. Jika A regular, maka invers tergeneralisasi dari matriks A belum tentu tunggal. Sehingga dapat dilakukan penelitian lebih lanjut tentang syarat ketunggalan suatu matriks atas aljabar maxplus mempunyai invers tergeneralisasi yang tunggal .
D. Referensi
Bacelli, F.et.al. 2001. Synchronization and Linearity.New York: John Wiley & Sons Blyumin,S.L, Goland,J.S.2002. One-sided Complements and Solution of the equation of axb=c in semiring. IJJMS29:28 hal:254-458.Hindawi Publishing Corp Cohen,G.et.al.1997. Linear Projector in The max- plus Algebra. 5th IEEE Mediterranean Conference on Control and Systems. Paphos Cyprus, 21-23 July 1997 Flemming,W.H,
2004.
Max-Plus
Stochastic
Processes.
Applied
Mathemamatic
Optimization.New York : Springer-Verlag Heidergot, B. 2000. A Characterization of (max,+) -linear queueing system.Queueing System.2359(2000) 237-262. Menguy, E. 2000. A fist Step Towards Adaptive Control for Linear System in Max Algebra. Discrete Event Dynamic System: Theory and Application. Boston: KluwerAcademic Publisher. Penrose,R.1954.
A generalized Inverse for Matrices. Mathematical Proceedings of The
Cambridge Philoshopical Society.
