NILAI DAN VEKTOR EIGEN MATRIKS INTERVAL ATAS ALJABAR MAX-PLUS Dwi Suci Maharani1 dan Suryoto2 Jurusan Matematika FMIPA Universitas Diponegoro Jln. Prof. H. Soedarto, S.H., Tembalang, Semarang
1, 2
n× n
Abstract. An interval matrix A = A, A with given A, A ∈ R max and A ≤ A is the set of all matrices A such that A ≤ A ≤ A . Eigenvalue and eigenvector of A ∈ A is called possible eigenvalue and eigenvector of an interval matrix A. With the definitions eigenvalue and interval matrix over max-plus algebra, can be developed a algorithm “possible eigenvector” to test whether a given vector x is a possible eigenvector of that interval matrix. Whereas universal eigenvalue and eigenvector of an matrix A is the eigenvalue and eigenvector of each A ∈ A. Universal eigenvector with λ = 0 can be found by solving two-sided systems of linear equations over max-plus algebra.
Keywords: Interval matrices, max-plus algebra, possible eigenvector, universal eigenvector.
1. PENDAHULUAN Aljabar max-plus yang dinotasikan dengan Rmax = ( Rε ,⊕,⊗) merupakan salah satu struktur dalam aljabar yaitu semifield komutatif idempoten [1], dengan Rε merupakan himpunan semua bilangan riil R dengan ε = −∞ , sedangkan operasi berturut-turut menyatakan ⊕ dan ⊗ maksimal dan penjumlahan normal bilangan riil, yang didefinisikan sebagai berikut [5]: ∀ a, b ∈ Rε a ⊕ b = max{a, b} a ⊗b = a +b Suatu sistem persamaan xi (k +1) = max{ai1 + x1(k),ai2 + x2(k),, ain + xn (k)} i = 1,2, , n ; k = 0,1,2, ; xi ( k ), aij ∈ Rε dalam aljabar max-plus dapat dinotasikan dengan xi (k +1) = (ai1 ⊗x1(k)) ⊕(ai2 ⊗x2(k)) ⊕⊕(ain ⊗xn(k)) n
= ⊕ (a ij ⊗ x j ( k ) )
; k = 0,1,2,
j =1
yang akhirnya dapat digabungkan secara kompak dengan penulisan x( k + 1) = A ⊗ x( k ) di mana
x1(k) a11 a12 x2 (k) n a a ∈ Rmax , A = 21 22 x(k) = x (k) a a n n1 2n
a1n a2n n×n ∈ Rmax ann
Suatu skalar λ ∈ Rε dan vektor n berturut-turut dinamakan x ≠ ε ∈ Rmax nilai eigen dan vektor eigen matriks n× n jika A ⊗ x = λ ⊗ x . Jika A A ∈ Rmax adalah matriks dari digraph G ( A) yang terhubung kuat, maka A mempunyai nilai eigen yang tunggal λ ( A) yaitu w( ρ ) ; ρ adalah cycle dari G ( A) λ ( A) = max ρ w ( ) Di mana untuk cycle ρ = {i1 , i 2 , , i k }
bobotnya
w( ρ ) = a i1i2 ⊗ ai2i3 ⊗ ⊗ aik i1
dan panjang lintasannya l ( ρ ) = k [1]. Selanjutnya, jika setiap entri n× n matriks A ∈ Rmax digandakan dengan − λ ( A) , maka diperoleh suatu matriks B dengan λ ( B ) = 0 . Sehingga, terdapat matriks Γ( B) = B ⊕ B 2 ⊕ ... ⊕ B n yang mempunyai beberapa entri diagonal utamanya sama dengan 0. Kolom-kolom yang memuat entri tersebut disebut vektor eigen-vektor eigen fundamental dari matriks B dan A [2]. Selanjutnya, semua vektor eigen matriks B dan A dapat 1
Jurnal Matematika Vol. 12, No.1, April 2009:1-10
dinyatakan sebagai kombinasi linier atas aljabar max-plus dari himpunan m vektor eigen fundamental (m < n) yang diperoleh. Bila matriks A diatas adalah matriks
interval
A = A, A
dengan
n× n A, A ∈ Rmax dan A ≤ A yang berarti setiap entri-entri yang bersesuaian berlaku a ij ≤ a ij . Dengan mengasumsikan bahwa digraph dari semua matriks A ∈ A adalah terhubung kuat dengan entri-entrinya berhingga, dan oleh kerenanya masingmasing A ∈ A mempunyai nilai eigen yang tunggal λ (A) , berikut akan dibahas mengenai nilai dan vektor eigen yang mungkin maupun nilai dan vektor eigen universal dari matriks interval A atas aljabar max-plus.
2. MATRIKS INTERVAL ATAS ALJABAR MAX-PLUS Matriks interval merupakan matriks yang elemen-elemen di dalamnya berupa interval tertutup dengan satu matriks batas bawah dan satu matriks batas atas sebagai penyusunnya. Diberikan matriks dan A = (a ij ) n× n A = (a ij ) ∈ Rmax
sedemikian
sehingga
a ij ≤ a ij dengan i, j = 1,2, , n . Matriks interval atas aljabar max-plus berordo n didefinisikan dengan A = A, A = A = (aij ) aij ≤ aij ≤ aij ; i, j = 1,2,...,n [6]
{
}
Contoh 1 Diberikan suatu matriks interval 2,10 5,14 A = A, A = di mana − 3,0 0, 7 2 5 10 14 A= dan A = . 0 − 3 7 0 Semua matriks A = (a ij ) dengan adalah termasuk di dalam matriks interval A = A, A .
Definisi operasi penjumlahan dan pergandaan matriks interval atas aljabar 2
max-plus, sama halnya definisi operasi penjumlahan dan pergandaan pada matriks atas aljabar max-plus. Hanya saja pada matriks interval mengikuti definisi operasi max dan plus pada suatu interval yaitu a, b ⊗ c, d = a + c, b + d [3]
a, b ⊕ c, d = max(a, c), max(b, d ) [3] dengan a, b, c, d ∈ Rε . Pembahasan operasi matriks interval atas aljabar max-plus, analog dengan definisi operasi matriks interval pada [4]. Dimisalkan M n×m ( Rmax ) adalah himpunan semua matriks interval atas aljabar maxplus berordo n × m . Untuk n, m ∈ N , didefinisikan n = {1,2,...,n}dan m = {1,2,...,m}. Elemen-elemen dari matriks A = A, A ∈ M n×m ( Rmax ) dengan baris i
dan kolom j , dinotasikan dengan (a, a ) ij atau dapat disajikan dengan [A]ij, untuk i ∈ n, dan j ∈ j (n) . a. Misalkan matriks A, B ∈ M n×m ( Rmax ) , penjumlahan matriks A ⊕ B, didefinisikan dengan [A ⊕ B]ij = ( a , a ) ij ⊕ ( b , b ) ij
= max(a ij , b ij ), max(a ij , b ij ) b. Misalkan A ∈ M n×m ( Rmax ) dan β ∈ Rε , pergandaan skalar β dengan matriks A yaitu β ⊗ A, didefinisikan dengan [ β ⊗ A]ij = β ⊗ ( a , a ) ij
= a ij + β , a ij + β c. Misalkan matriks A ∈ M n×l ( Rmax ) dan B ∈ M l×m ( Rmax ) , perkalian matriks A ⊗ B, didefinisikan dengan [A ⊗ B]ik =
l
⊕ (a , a )
ij
⊗ ( b , b ) ij
j =1
{
= max j∈l {a ij + b jk }, max j∈l a ij + b jk 2 ≤ a11 ≤ 10 5 ≤ a12 ≤ 14
0 ≤ a 21 ≤ 7 − 3 ≤ a 22 ≤ 0
}
Dwi Suci Maharani dan Suryoto (Nilai dan Vektor Eigen Matriks Interval Atas Aljabar Max-Plus)
3. NILAI DAN VEKTOR EIGEN YANG MUNGKIN DARI MATRIKS INTERVAL Diasumsikan bahwa semua matriks
A ∈ A = A, A adalah matriks dari digraph berbobot yang terhubung kuat dengan n× n semua entri penyusun matriks A, A ∈ Rmax adalah berhingga, dan oleh kerenanya masing-masing A ∈ A mempunyai nilai eigen yang tunggal λ ( A) . Suatu skalar λ dinamakan nilai eigen yang mungkin dari suatu matriks interval A, jika skalar tersebut adalah nilai eigen dari sedikitnya satu A ∈ A [2]. Teorema 1 Suatu skalar λ adalah nilai eigen yang mungkin dari suatu matriks interval A jika
Hal
A ∈ A = A, A . Karena A adalah matriks dari digraph berbobot yang terhubung kuat, maka w( ρ ) ; ρ adalah cycle dari G( A) K ρ w ( )
λ ( A) = max
arena untuk setiap matriks A ∈A mempunyai cycle yang sama, akan tetapi mempunyai bobot berbeda, yaitu w( ρ ) ≤ w( ρ ) ≤ w( ρ ) dengan ρ = cycle di dalam digraph G ( A)
ρ = cycle di dalam digraph G ( A) ρ = cycle di dalam digraph G ( A) maka diperoleh w(ρ ) w( ρ ) w(ρ ) max ≤ max ≤ max l (ρ ) l (ρ ) l(ρ) λ ( A) ≤ λ ( A) ≤ λ ( A)
menunjukkan
bahwa
λ ∈ λ ( A), λ ( A) . (⇐)
λ ∈ λ ( A), λ ( A) .
Diketahui
Akan
dibuktikan λ adalah nilai eigen yang mungkin dari matriks A, yang artinya λ adalah nilai eigen dari sedikitnya satu A ∈ A. Diambil matriks A dari digraph yang terhubung kuat dengan nilai eigen w( ρ ) w( ρ )
λ ( A) = max
Matriks interval A = A, A mempunyai • nilai eigen matriks batas bawah A , yaitu w( ρ ) l ( ρ )
λ ( A) = max
dan hanya jika λ ∈ λ ( A), λ ( A) . Bukti : (⇒) Diketahui λ adalah nilai eigen yang mungkin dari suatu matriks interval A. Sehingga, λ adalah nilai eigen dari sedikitnya satu A ∈ A. Misalkan λ adalah nilai eigen dari suatu matriks
ini
• nilai eigen matriks batas atas A , yaitu w( ρ ) λ ( A) = max l(ρ ) Akan ditunjukkan bahwa matriks
A ∈ A = A, A . Jika
λ ( A) ∈ λ ( A), λ ( A) ,
ini
berarti
bahwa λ ( A) ≤ λ ( A) ≤ λ ( A) Sehingga berlaku w(ρ ) w(ρ ) w( ρ ) max ≤ max ≤ max l ( ρ ) l(ρ) l(ρ) Karena cycle-cycle dari matriks A, A, dan A sama, maka berlaku w( ρ ) ≤ w( ρ ) ≤ w( ρ ) dengan ρ = cycle di dalam digraph G ( A)
ρ = cycle di dalam digraph G ( A)
ρ = cycle di dalam digraph G ( A) Hal ini menunjukkan bahwa A ∈ A = A, A , dengan kata lain λ ( A)
adalah nilai eigen dari sedikitnya satu matriks A ∈ A. ■ 3
Jurnal Matematika Vol. 12, No.1, April 2009:1-10
Input : suatu matriks interval A, dan sebuah vektor x . 1. Begin y := A ⊗ x If y − x adalah suatu vektor konstan 2. 3. then x adalah suatu vektor eigen yang mungkin dari A, STOP 4. else begin λ ( x) := max i {y i − xi };
5.
{
}
for all i, j : a * ij = min a ij , λ ( x) + xi − x j ; *
6. if ( A ⊗ x) − x adalah suatu vektor konstan 7. then x adalah suatu vektor eigen yang mungkin dari A ; STOP else x bukan vektor eigen yang mungkin dari A; STOP 8. 9. end 10. end. n adalah vektor Suatu vektor x ∈ Rmax eigen yang mungkin dari suatu matriks interval A jika terdapat A ∈ A sedemikian sehingga A ⊗ x = λ ( A) ⊗ x [2]. Selanjutnya, untuk menentukan matriks A yang mempunyai vektor eigen n x ∈ Rmax ini dilakukan dengan cara meningkatkan matriks batas bawah A dalam setiap koordinat sedemikian rupa sehingga tidak melebihi matriks batas atas dari A , tetapi untuk setiap koordinat A ⊗ x dipastikan nilainya sekurangλ ( x) ⊗ xi yang dapat kurangnya dirumuskan dengan a * ij = min a ij , λ ( x ) + xi − x j . Sehingga untuk menguji apakah suatu vektor x yang diberikan adalah vektor eigen dari suatu matriks interval A, dapat dilakukan dengan menggunakan algoritma ”possible eigenvector” sebagai berikut :
masing-masing A ∈ A mempunyai nilai eigen yang tunggal λ ( A) . Suatu skalar λ dinamakan nilai eigen universal dari suatu matriks interval A, jika skalar tersebut adalah nilai eigen dari setiap A ∈ A [2].
4. NILAI DAN VEKTOR EIGEN UNIVERSAL DARI MATRIKS INTERVAL Diasumsikan bahwa semua matriks
(⇐)
{
}
A ∈ A = A, A adalah matriks dari digraph berbobot yang terhubung kuat dengan n× n semua entri penyusun matriks A, A ∈ Rmax adalah berhingga, dan oleh kerenanya
4
Teorema 2 Suatu matriks interval A mempunyai suatu nilai eigen universal jika dan hanya jika λ ( A) = λ ( A) .
Bukti : (⇒) Diketahui suatu interval A mempunyai suatu nilai eigen universal λ , maka λ adalah nilai eigen dari setiap A ∈ A. Karena A, A ∈ A, maka λ ( A) = λ dan
λ ( A) = λ . Sehingga, λ ( A) = λ ( A)
Diketahui λ ( A) = λ ( A) . Misalkan akan λ ( A) = λ ( A) = λ , ditunjukkan bahwa λ adalah nilai eigen universal dari A, yang berarti λ adalah nilai eigen dari setiap A ∈ A. Ambil sebarang matriks dengan
A ∈ A = A, A ,
Dwi Suci Maharani dan Suryoto (Nilai dan Vektor Eigen Matriks Interval Atas Aljabar Max-Plus)
ρ = cycle di dalam digraph G ( A) ρ = cycle di dalam digraph G ( A)
ρ = cycle di dalam digraph G ( A) maka w( ρ ) ≤ w( ρ ) ≤ w( ρ ) . Karena cycle-cycle dari matriks A, A, dan A sama, maka w(ρ ) w( ρ ) w( ρ ) ≤ ≤ l (ρ ) l (ρ ) l ( ρ ) Akibatnya w( ρ ) w(ρ ) w(ρ ) max ≤ max ≤ max l (ρ ) l (ρ ) l(ρ)
λ ( A) ≤ λ ≤ λ ( A) Dengan kata lain, λ ∈ λ ( A), λ ( A) . Karena diketahui bahwa
λ ( A) = λ ( A) ,
maka λ = λ ( A) = λ ( A) . Hal ini berarti bahwa matriks interval A tersebut mempunyai suatu nilai eigen universal λ . ■ Selanjutnya, dalam pembahasan vektor eigen universal dibatasi hanya pada kasus λ ( A) = λ ( A) dan matriks interval yang diberikan mempunyai suatu nilai eigen universal sama dengan 0. Vektor eigen universal merupakan kombinasi linier atas aljabar max-plus dari himpunan vektor eigen fundamental matriks A maupun A . Teorema 3 Apabila suatu matriks interval A mempunyai λ ( A) = λ ( A) = 0 dan {u1 , u 2 ,..., u m } adalah himpunan vektor eigen fundamental dari A , maka terdapat vektor eigen universal dari A jika dan hanya jika sistem dua sisi C⊗ y = D⊗ y
dengan C i = A ⊗ u i dan Di = u i untuk semua mempunyai i = 1,2,..., m penyelesaian.
Bukti : (⇒) Diketahui suatu matriks interval A dengan dan misalkan λ ( A) = λ ( A) = 0 {u1 , u 2 ,..., u m } adalah himpunan vektor eigen fundamental dari A . Akan dibuktikan sistem dua sisi C ⊗ y = D ⊗ y mempunyai penyelesaian. Misalkan vektor eigen universal dari A n adalah x ∈ Rmax , maka untuk setiap A ∈ A berlaku A ⊗ x = λ ( A) ⊗ x . Karena vektor eigen universal merupakan kombinasi linier atas aljabar max-plus dari himpunan m vektor eigen fundamental matriks A , maka n
x = ⊕ ( yi ⊗ ui ) i =1
Sehingga, untuk A ∈ A dengan λ ( A) = 0 , berlaku m
m
A ⊗ ⊕ ( yi ⊗ ui ) = ⊕ ( y i ⊗ ui ) i =1
i =1
m
m
⊕ (( A ⊗ u ) ⊗ y ) = ⊕ (u i
i
i =1
i
⊗ yi )
i =1
m
m
⊕ (Ci ⊗ yi ) = ⊕ ( Di ⊗ yi ) i =1
i =1
C⊗ y = D⊗ y
y1 y Jadi, y = 2 adalah penyelesaian dari ym C ⊗ y = D⊗ y. (⇐) Diketahui suatu matriks interval A dengan λ ( A) = λ ( A) = 0 dan misalkan {u1 , u 2 ,..., u m } adalah himpunan vektor eigen fundamental dari A . n Akan dibuktikan terdapat x ∈ Rmax suatu vektor eigen universal dari A.
5
Jurnal Matematika Vol. 12, No.1, April 2009:1-10
y1 y Misalkan y = 2 adalah penyelesaian ym dari sistem persamaan dua-sisi C ⊗ y = D ⊗ y , sehingga, m i =1
i =1
m
m
⊕ (( A ⊗ u ) ⊗ y ) = ⊕ (u i
i
i =1
i
⊗ yi )
i =1
m
m
A ⊗ ⊕ ( yi ⊗ ui ) = ⊕ ( y i ⊗ ui ) i =1
i =1
bahwa
dengan
λ ( A) = 0 ,
n
x = ⊕ ( yi ⊗ ui )
adalah
vektor
matriks A . Karena x adalah vektor eigen matriks batas A dan A , maka x adalah vektor eigen semua matriks A ∈ A, yang berarti x adalah vektor eigen universal dari A. ■ Contoh 2 Diberikan matriks interval 0, 0
− 1, 0
− 4, − 1
− 1, − 1 0, 0
A = − 3, − 2
− 2, 1 0, 0 − 4, − 1
di mana λ ( A) = λ ( A) = 0 . Himpunan vektor eigen fundamental dari matriks A yaitu {(0,−3,−3), (−1,0,0)}. Dibentuk matriks C dengan C i = A ⊗ u i , 0 1
yaitu C = − 2 0 dan matriks D dengan − 1 0
0 − 1 Di = u i , yaitu D = − 3 0 . − 3 0
Salah satu penyelesaian system persamaan dua-sisi
6
0 − 3 ⊕ − 1 ⊗ − 3
− 1 0 0 = − 1 0 − 1
5. PENYELESAIAN SISTEM PERSAMAAN DUA-SISI Sistem persamaan linier dua-sisi atas aljabar max-plus yang berbentuk C ⊗ y = D ⊗ y dengan C ≥ D (1) n menotasikan himpunan indeks baris {1,2,...,n} dan m himpunan indeks kolom {1,2,..., m} dari matriks C dan D .
eigen
i =1
x = 0 ⊗
m
⊕ (Ci ⊗ yi ) = ⊕ ( Di ⊗ yi )
Terlihat
0 adalah y = , sehingga vektor eigen − 1 universal dari matriks A adalah
0 1 0 − 1 − 2 0 ⊗ y = − 3 0 ⊗ y − 1 0 − 3 0
Lemma 4 Jika terdapat baris i sedemikian sehingga cij > d ij untuk setiap j , maka sistem tidak mempunyai solusi. Bukti : Misalkan vektor y adalah solusi dari (1) dan pemaksimal dalam sisi ruas kiri dan sisi ruas kanan dari baris i masing-masing diperoleh pada kolom ke j dan l , yaitu dan cij + y j = max k {cik + y k }
d il + y l = max k {d ik + y k } i ∈ n, dan j ∈ m . Maka akan cij + y j ≥ cil + y l > d il + y l .
dengan berlaku
Hasil cil + yl > d il + yl kontradiksi dengan adalah solusi dari y C ⊗ y = D ⊗ y . Sehingga terbukti bahwa sistem C ⊗ y = D ⊗ y dengan C ≥ D tidak mempunyai solusi. ■ Akibat Jika sistem berbentuk (1) mempunyai penyelesaian, maka untuk setiap baris i terdapat suatu indeks j sedemikian sehingga berlaku cij = d ij . Bukti : Misalkan vektor y adalah solusi dari (1).
Dwi Suci Maharani dan Suryoto (Nilai dan Vektor Eigen Matriks Interval Atas Aljabar Max-Plus)
Akan dibuktikan bahwa untuk setiap baris i terdapat suatu indeks j sedemikian sehingga berlaku cij = d ij . Misalkan pemaksimal dalam sisi ruas kiri dan sisi ruas kanan dari baris i masingmasing diperoleh pada kolom ke l dan j , yaitu dan cil + y l = max k {cik + y k } dengan d ij + y j = max k {d ik + y k } i ∈ n, dan j ∈ m . Sehingga akan berlaku cil + y l = d ij + y j .
Dilain pihak,
cij + y j ≤ cil + y l ,
maka
cij + y j ≤ d ij + y j .
Karena C ≥ D , yang berarti memenuhi cij ≥ d ij untuk semua i ∈ n, dan j ∈ m , maka cij + y j = d ij + y j , dengan kata lain, cij = d ij . ■
Indeks j pada akibat diatas, dinamakan indeks kritis untuk baris i . Dalam pembahasan selanjutnya, K i menotasikan himpunan indeks kritis untuk baris i . Lemma 5 Untuk setiap penyelesaian y pada (1) terdapat indeks kritis pemaksimal untuk setiap baris i . Bukti : Andaikan y adalah penyelesaian pada (1), dan elemen pemaksimal baris i pada C ⊗ y dan D ⊗ y berturut-turut adalah cij + y j dan d ik + y k .
Hal ini berarti cij + y j = d ik + y k , oleh karena itu y k = y j + cij − d ik . Maka untuk elemen ke k dari baris i pada C⊗y diperoleh cik + y k = cik + y j + cij − d ik . Karena cik ≥ d ik , cik + y k ≥ cij + y j . Akibatnya, apabila cik + y k > cij + y j .
maka
berlaku
cik − d ik > 0 , maka
Sehingga terjadi kontradiksi, karena indeks j bukan pemaksimal baris i pada C ⊗ y . Oleh karena itu, indeks k adalah indeks kritis pemaksimal untuk baris i pada C ⊗ y . ■ Oleh karena itu, untuk mencari penyelesaian sistem persamaan dua-sisi (1) penting untuk memilih elemen pemaksimal yang sesuai dengan indeks kritis untuk setiap baris pada C ⊗ y . Teorema 6 Suatu sistem (1) mempunyai penyelesaian jika dan hanya jika setiap K i tidak kosong, terdapat fungsi j : n → m sehingga j (i ) ∈ K i untuk semua i ∈ n dan untuk dari n , setiap subset {i1 , i2 ,..., ik } sedemikian sehingga j (i1 ), j (i2 ),..., j (ik ) saling berbeda,diperoleh pertidaksamaan ci1 j (i1 ) + ci2 j (i2 ) + ... + cik j (ik ) ≥ ci1 j (i2 ) + ci2 j (i3 ) + ... + cik j (i1 )
(2) Bukti : (⇒) Misalkan y adalah solusi dari C⊗ y = D⊗ y Ambil sebarang subset {i1 , i2 ,..., ik } ⊆ n . Dengan lemma 5, yang menyatakan bahwa setiap baris i terdapat indeks kritis pemaksimal C ⊗ y , maka dinotasikan satu indeks untuk setiap baris oleh j (il ), l = 1,2,..., k dan andaikan bahwa indeks kolom yang terpilih satu sama lain berbeda, maka diperoleh cil j (il ) + y j (ik ) ≥ cil j (il +1 ) + y j (il +1 )
untuk semua l = 1,2,..., k dengan k + 1 = 1 . Apabila pertidaksamaan tersebut dijumlahkan, maka diperoleh ci1 j (i1 ) + ci2 j (i2 ) + ... + cik j (ik ) ≥ ci1 j (i2 ) + ci2 j (i3 ) + ... + cik j (i1 )
( ⇐) Andaikan bahwa ada kemungkinan untuk memilih setiap baris i suatu indeks kolom kritis j (i ) sedemikian sehingga memenuhi pertidaksamaan (2). Kemudian dinotasikan
7
Jurnal Matematika Vol. 12, No.1, April 2009:1-10
j ( n) = { j (i ); i ∈ n} sebagai himpunan indeks kolom dari kolom terpilih di dalam kolom j , dan dibangun C ' suatu submatriks C yang dibuat dari kolom j (n) . Jumlah baris dengan indeks kolom terpilih di dalam kolom j , dinotasikan dengan p ( j ) . Selanjutnya, ditinjau permasalahan untuk pemilihan pasangan indeks sebagai berikut :
j∈ j ( n ) i∈n
xij = 1 untuk semua i ∈ n
Akan ditunjukkan bahwa salah satu penyelesaian optimal bulat yang mungkin adalah xij (i ) = 1 untuk i ∈ n dan xij = 0 untuk yang lainnya. Andaikan bahwa X adalah solusi optimal dan xi1 j = 1 untuk beberapa i1 ∈ n dan j ∉ j (i1 ) . Karena kapasitas baris i1 adalah 1, maka xi1 j (i1 ) = 0 . Selanjutnya, karena j ∈ j (n) , maka terdapat baris i 2 ∈ n sedemikian sehingga j = j (i2 ) dan xi2 j (i2 ) = 0 . Karena kapasitas baris i 2 adalah 1, maka terdapat indeks kolom j = j (i3 ) untuk beberapa baris i3
,
dan
xi3 j (i3 ) = 0 , dan seterusnya. Dengan cara ini, diperoleh suatu cycle indeks baris {i1 , i2 ,..., ik } sedemikian sehingga
xil j (il ) = 0 dan xil j (il +1 ) = 1 untuk semua l = 1,2,..., k dengan k + 1 = 1 . Didefinisikan solusi baru X ' dengan x'il j (il ) = 1 dan x'il j ( il +1 ) = 0 untuk semua l = 1,2,..., k dengan k + 1 = 1 , dan xij = 0 untuk semua pasangan indeks lainnya. Kemudian, karena memenuhi C' pertidaksamaan (2), nilai
8
c' ij x' ij > ∑i∈n ∑ j∈ j ( n) c' ij xij ,
sehinggga diperoleh solusi permasalahan diatas dengan xij = 1 jika hanya jika j = j (i ) untuk i ∈ n dan xij = 0 untuk yang lainnya.
Sekarang, dibentuk dual dari masalah diatas sebagai berikut :
j ∈ j ( n) .
xij ≥ 0 untuk semua i ∈ n dan j ∈ j (n)
sehingga xi2 j (i3 ) = 1
j∈ j ( n)
u i + v j ≥ c' ij untuk semua i ∈ n , dan
xij = p ( j ) untuk semua j ∈ j (n)
sedemikian
i∈n
Meminimalkan: Z d = ∑i∈n ui + ∑j∈ j (n) p( j)v j
Memaksimalkan : Z = ∑i∈n ∑j∈ j ( n) c'ij xij
∑ ∑
∑ ∑
Definisikan vektor y yang dinyatakan sebagai berikut : − ∞ ; untuk j ∉ j (n) yj = − v j ; untuk j ∈ j (n) adalah suatu solusi optimal dari (1). Karena pada setiap baris i dapat dipilih suatu indeks kolom kritis j (i ) , maka diperoleh cij (i ) + y j (i ) = d ij (i ) + y j (i ) Selanjutnya akan ditunjukkan bahwa untuk semua kolom lain l , memenuhi cil + y l ≤ cij (i ) + y j (i ) . Untuk l ∉ j ( n) pertidaksamaan ini trivial, dan untuk kolom-kolom dari j ( n) maka cij = c'ij . Karena pemilihan entri-entri
(i, j (i ) ) bersesuaian dengan elemen tak nol dari solusi permasalahan diatas, maka berlaku u i = cij (i ) − v j (i ) , dan untuk semua entri yang lain vl ≥ cil − u i [7]. Sehingga diperoleh cil + yl = cil − vl ≤ cil − cil + ui = cij(i) − vj (i) = cij(i) + y j(i) Dari sini terlihat bahwa vektor y mempunyai indeks kritis pemaksimal untuk setiap baris i yaitu j (i ) . Sehingga vektor y adalah penyelesaian dari persamaan (1). ■
Dwi Suci Maharani dan Suryoto (Nilai dan Vektor Eigen Matriks Interval Atas Aljabar Max-Plus)
Contoh 3
1 2 4 8 Diberikan matriks C = 6 3 9 4 dan 7 3 8 0 0 1 4 5 D = 2 3 9 2 . 7 3 7 0 Akan dicari penyelesaian sistem persamaan dua-sisi C ⊗ y = D ⊗ y . Matriks C mempunyai entri-entri kritis yang ditandai sebagai berikut : 1 2 4ˆ 8 C = 6 3ˆ 9ˆ 4 7ˆ 3ˆ 8 0ˆ Selanjutnya, dipilih entri-entri c13 , c 23 , c31 yang memenuhi (5.2). Dibentuk sumatriks C dari kolom-kolom terpilih yaitu 1 4 C ' = 6 9 7 8 Kapasitas setiap baris adalah 1, kapasitas kolom ke-1 adalah 1, dan kapasitas kolom ke-2 adalah 2. Sehingga, diperoleh permasalahan pemilihan indeks sebagai berikut : Memaksimalkan : Z = ∑i∈n ∑ j∈ j ( n) c'ij xij Kendala : x11 + x12 = 1 x 21 + x 22 = 1 x31 + x32 = 1 x11 + x 21 + x31 = 1 x12 + x 22 + x32 = 2 xij ≥ 0 untuk semua i ∈ n dan j ∈ j (n) Kemudian, dibentuk permasalahan dual dari masalah pemilihan indeks diatas sebagai berikut : Meminimalkan : Z d = u1 + u 2 + u3 + v1 + 2v2
Kendala : u1 + v1 ≥ 1 u1 + v 2 ≥ 4 u 2 + v1 ≥ 6 Vektor y − ∞ yj = − v j
u 2 + v2 ≥ 9 u 3 + v1 ≥ 7
u3 + v2 ≥ 8
yang dinyatakan ; untuk j ∉ j (n) ; untuk j ∈ j (n)
dengan adalah
penyelesaian dari sistem persamaan duasisi diatas. Nilai u i dan v j yang memenuhi : u1 + v1 ≥ 1 u1 + v 2 = 4 u 2 + v1 ≥ 6
u 2 + v2 = 9 u 3 + v1 = 7 u3 + v2 ≥ 8 adalah solusi dari permasalahan dual diatas. Dengan mengambil nilai v2 = 1 , maka dapat diperoleh salah satu kemungkinan solusi dari permasalahan diatas yaitu u1 = 3, u 2 = 8, u 3 = 7, v1 = 0, v 2 = 1 . Sehingga diperoleh salah satu penyelesaian 0 − ∞ dari sistem dua-sisi diatas yaitu y = −1 − ∞ 6. PENUTUP Berdasarkan uraian mengenai nilai dan vektor eigen matriks interval atas aljabar max-plus diatas dapat diperoleh beberapa hal sebagai berikut : a. Nilai eigen yang mungkin dari suatu matrik interval A berada pada interval tertutup nilai eigen matriks batasnya. b. Algoritma “possible eigenvector” dapat digunakan untuk menguji suatu vektor x sebagai vektor eigen yang mungkin dari suatu matrik interval A. c. Matriks interval A mempunyai nilai eigen universal apabila nilai eigen matriks batasnya sama. d. Vektor eigen universal matriks interval A dengan λ = 0 dapat dicari dengan menyelesaikan suatu sistem persamaan dua-sisi.
9
Jurnal Matematika Vol. 12, No.1, April 2009:1-10
Selanjutnya, dapat dikembangkan suatu metode bagaimana mencari vektor eigen universal matriks interval yang bersesuaian dengan nilai eigen universal λ ≠ 0 . 7. DAFTAR PUSTAKA [ 1 ] Baccelli, Francois., dkk. (1992), Synchronization and Linearity, An Algebra for Discrete Event Systems. Wiley, Chichester. [ 2 ] Cechlarova, K. (2003), Eigenvectors of Interval Matrices over Max-Plus Algebra, Slovakia. [ 3 ] Chiao, Kuo-Ping. (1999), Inclusion Monotonic Property of CourantFischer Minimax Characterization on Interval Eigenproblems for Symmetric Interval Matrices. Alethia University.
10
[ 4 ] Gioia, Federica dan Carlo N. Lauro. (2006), Principal Component Analysis on Interval Data, Universita degli Studi di Napoli, 21(2) : 3 – 5. [ 5 ] Heidergott, Bernd. (1998), Max Plus Algebra and Queues, Vrije Universiteit, Amsterdam. [ 6 ] Kandasamy, W. B. Vasantha. (2006), Fuzzy Interval Matrices, Neutrosophic Interval Matrices and Their Aplications, Florentin Smarandache, Phoenix, Arizona. [ 7 ] Supranto, Johanes. (2006), Riset Operasi untuk Pengambilan Keputusan, UIP, Yogyakarta.