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
Abstract. An interval matrix A = A, A with given and is the set of all matrices such that . 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 is the eigenvalue and eigenvector of each A ∈ A. Universal eigenvector with can be found by solving twosided systems of linear equations over max-plus algebra. Keywords: Interval matrices, max-plus algebra, possible eigenvector, universal eigenvector.
⎛ a11 a12 ⎛ x1(k) ⎞ ⎜ ⎟ ⎜ x ( k ) ⎜ a21 a22 ⎜ 2 ⎟ n x(k) = ⎜ ∈ Rmax , A = ⎜ ⎟ M M M ⎜ ⎟ ⎜ ⎜a a ⎜ x (k) ⎟ ⎝ n1 2n ⎝ n ⎠
1. PENDAHULUAN Aljabar max-plus yang dinotasikan dengan Rmax = ( Rε ,⊕,⊗) merupakan salah satu struktur dalam aljabar yaitu semifield komutatif idempoten [1]. Rε merupakan himpunan bilangan riil R dengan ε = −∞ , sedangkan operasi ⊕ dan ⊗ berturut-turut menyatakan maksimal dan penjumlahan normal bilangan riil, yang didefinisikan sebagai berikut [5]: ∀ a, b ∈ Rε a ⊕ b = max{a, b} a ⊗b = a + b
Suatu skalar λ ∈ Rε dan vektor n x ≠ ε ∈ Rmax berturut-turut dinamakan nilai eigen dan vektor eigen matriks n× n A ∈ Rmax jika A ⊗ x = λ ⊗ x . Jika A adalah matriks dari digraph G ( A) yang terhubung kuat, maka A mempunyai nilai eigen yang tunggal λ ( A) yaitu ⎧ w( ρ ) ⎫ ; ρ adalah cycle dari G ( A)⎬ ⎩ w( ρ ) ⎭
λ ( A) = max⎨
Di mana untuk cycle ρ = {i1 , i2 , L, ik } w( ρ ) = ai1i2 ⊗ ai2i3 ⊗ L ⊗ aik i1 bobotnya dan panjang lintasannya l ( ρ ) = k [1]. Selanjutnya, jika setiap entri matriks digandakan dengan − λ ( A) , maka diperoleh suatu matriks B dengan . Sehingga, terdapat matriks 2 n Γ( B) = B ⊕ B ⊕ ... ⊕ B 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
Suatu sistem persamaan xi (k +1) = max{ai1 + x1(k),ai2 + x2 (k),L, ain + xn (k)} i = 1,2, L , n ; k = 0,1,2, L ; xi (k ), a ij ∈ Rε
dalam aljabar max-plus dapat dinotasikan dengan xi (k +1) = (ai1 ⊗ x1(k)) ⊕(ai2 ⊗ x2(k)) ⊕L⊕(ain ⊗ xn (k))
= ⊕ (a ij ⊗ x j (k ) ) n
j =1
L a1n ⎞ ⎟ L a2n ⎟ n×n ∈ Rmax O M ⎟ ⎟ L ann ⎟⎠
; k = 0,1,2, L
yang akhirnya dapat digabungkan secara kompak dengan penulisan x ( k + 1) = A ⊗ x (k ) di mana 1
[2]. Selanjutnya, semua vektor eigen matriks B dan dapat 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 ALJABAR MAX-PLUS
ATAS
Matriks interval merupakan matriks yang elemen-elemen di dalamnya berupa interval tertutup dengan satu matriks batas bawah dan satu matriks batas atas sebagai penyusunnya. A = (a ij ) Diberikan matriks dan n× n A = (a ij ) ∈ Rmax sedemikian sehingga
a ij ≤ a ij dengan i, j = 1,2, L , 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 2.1 Diberikan suatu matriks interval ⎡ 2,10 5,14 ⎤ = A, A = ⎢ ⎥ di − 3,0 ⎦ ⎣ 0, 7 ⎡2 5 ⎤ ⎡10 14⎤ A=⎢ dan A = ⎢ ⎥ ⎥. ⎣0 − 3⎦ ⎣7 0⎦ Semua matriks A = (aij ) dengan
mana
2 ≤ a11 ≤ 10 0 ≤ a 21 ≤ 7 5 ≤ a12 ≤ 14 − 3 ≤ a 22 ≤ 0 adalah termasuk di dalam matriks interval A = A, A .
Definisi operasi penjumlahan dan pergandaan matriks interval atas aljabar 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 , didefinisikan n = {1,2,...,n}dan m = {1,2,...,m}. Elemen-elemen dari matriks M n×m ( Rmax ) dengan baris dan kolom , 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 didefinisikan dengan = ( a , a ) ij ⊕ ( b , b ) ij [A ⊕ 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 , a ) ij [ β ⊗ 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 ) j =1
ij
⊗ ( b , b ) ij
{
= max j∈l {a ij + b jk }, max j∈l a ij + b jk
}
3. NILAI DAN VEKTOR EIGEN YANG MUNGKIN DARI MATRIKS INTERVAL
Diasumsikan bahwa semua matriks adalah matriks dari digraph berbobot yang terhubung kuat dengan semua entri n×n penyusun matriks A, A ∈ Rmax adalah berhingga, dan oleh kerenanya masingmasing A ∈ A mempunyai nilai eigen yang tunggal . 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 3.1 Suatu skalar adalah nilai eigen yang mungkin dari suatu matriks interval A jika 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 . Karena A adalah matriks dari digraph berbobot yang terhubung kuat, maka ⎧ w( ρ ) ⎫ ; ρ adalah cycle dari G( A)⎬ λ ( A) = max⎨ ⎩ w( ρ ) ⎭
Karena untuk setiap matriks A ∈ A mempunyai cycle yang sama, akan tetapi mempunyai bobot berbeda, yaitu w( ρ ) ≤ w( ρ ) ≤ w( ρ ) dengan cycle di dalam digraph ρ = cycle di dalam digraph G ( A) cycle di dalam digraph maka diperoleh ⎧⎪ w( ρ ) ⎫⎪ ⎧ w( ρ ) ⎫ ⎧ w( ρ ) ⎫ max⎨ ⎬ ≤ max⎨ ⎬ ⎬ ≤ max⎨ ⎪⎩ l ( ρ ) ⎪⎭ ⎩ l (ρ ) ⎭ ⎩ l(ρ ) ⎭ λ ( A) ≤ λ ( A) ≤ λ ( A) Hal ini menunjukkan bahwa .
Diketahui . Akan dibuktikan adalah nilai eigen yang mungkin dari matriks A, yang artinya adalah nilai eigen dari sedikitnya satu . Diambil matriks A dari digraph yang terhubung kuat dengan nilai eigen Matriks interval mempunyai • nilai eigen matriks batas bawah, yaitu • nilai eigen matriks batas atas , yaitu Akan ditunjukkan bahwa matriks . Jika , 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 ρ = cycle di dalam digraph G ( A) cycle di dalam digraph Hal ini menunjukkan bahwa , dengan kata lain adalah nilai eigen dari sedikitnya satu matriks A ∈ A. ■ n Suatu vektor x ∈ Rmax adalah vektor eigen yang mungkin dari suatu matriks interval A jika terdapat A ∈ A sedemikian sehingga A ⊗ x = λ ( A) ⊗ x [2]. Selanjutnya, untuk menentukan matriks yang mempunyai vektor eigen n x ∈ Rmax ini dilakukan dengan cara meningkatkan matriks batas bawah dalam setiap koordinat sedemikian rupa sehingga tidak melebihi matriks batas atas , tetapi untuk setiap koordinat dari A ⊗ x dipastikan nilainya sekurang-kurangnya λ ( x) ⊗ xi yang dapat dirumuskan dengan a * ij = min a ij , λ ( x) + xi − x j .
{
}
Sehingga untuk menguji apakah suatu vektor yang diberikan adalah vektor eigen
dari suatu matriks interval A, dapat dilakukan dengan menggunakan algoritma
”possible eigenvector” sebagai berikut :
Input : suatu matriks interval A, dan sebuah vektor . 1. Begin y := A ⊗ x 2. If y − x adalah suatu vektor konstan then adalah suatu vektor eigen yang mungkin dari A, STOP 3. 4. else begin λ ( x) := max i {y i − xi }; * for all i, j : a ij = min a ij , λ ( x) + xi − x j ; 5.
{
}
if ( A ⊗ x) − x adalah suatu vektor konstan 6. 7. then adalah suatu vektor eigen yang mungkin dari ; STOP 8. else bukan vektor eigen yang mungkin dari ; STOP 9. end 10. end. *
4. NILAI DAN VEKTOR EIGEN UNIVERSAL DARI MATRIKS INTERVAL
Diasumsikan bahwa semua matriks
adalah matriks dari digraph berbobot yang n×n terhubung kuat dengan semua entri penyusun matriks A, A ∈ Rmax adalah berhingga, dan oleh kerenanya masing-masing A ∈ A mempunyai nilai eigen yang tunggal . Suatu skalar dinamakan nilai eigen universal dari suatu matriks interval A, jika skalar tersebut adalah nilai eigen dari setiap A ∈ A [2]. Teorema 4.1 Suatu matriks interval A mempunyai suatu nilai eigen universal jika dan hanya jika λ ( A) = λ ( A) . Bukti :
Diketahui suatu interval mempunyai suatu nilai eigen universal , maka adalah nilai eigen dari setiap A ∈ A. Karena A, A ∈ A, maka dan . Sehingga,
Diketahui . Misalkan , akan ditunjukkan bahwa adalah nilai eigen universal dari A, yang berarti adalah nilai eigen dari setiap A ∈ A. Ambil sebarang matriks , dengan cycle di dalam digraph ρ = cycle di dalam digraph G ( A) cycle di dalam digraph maka . Karena cycle-cycle dari matriks A, A, dan A sama, maka
w(ρ ) l (ρ )
≤
w( ρ ) w( ρ ) ≤ l (ρ ) l(ρ )
Akibatnya ⎧⎪ w(ρ ) ⎫⎪ ⎧ w( ρ ) ⎫ ⎧ w( ρ ) ⎫ max⎨ ⎬ ⎬ ≤ max⎨ ⎬ ≤ max⎨ ⎪⎩ l ( ρ ) ⎪⎭ ⎩ l(ρ ) ⎭ ⎩ l (ρ ) ⎭ λ ( A) ≤ λ ≤ λ ( A) Dengan kata lain, . Karena diketahui bahwa , maka . Hal ini berarti bahwa matriks interval tersebut mempunyai suatu nilai eigen universal . ■
Selanjutnya, dalam pembahasan vektor eigen universal dibatasi hanya pada kasusdan 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 4.2 Apabila suatu matriks interval mempunyai dan {u1 , u 2 ,..., u m } adalah himpunan vektor eigen fundamental dari A , maka terdapat vektor eigen universal dari jika dan hanya jika sistem dua sisi C⊗ y = D⊗ y dengan C i = A ⊗ u i dan Di = u i untuk semua i = 1,2,..., m mempunyai penyelesaian. Bukti :
Diketahui suatu matriks interval dengan dan misalkan adalah himpunan vektor eigen fundamental dari . Akan dibuktikan sistem dua sisi mempunyai penyelesaian. Misalkan vektor eigen universal dari adalah , maka untuk setiap berlaku . Karena vektor eigen universal merupakan kombinasi linier atas aljabar max-plus dari himpunan m vektor eigen fundamental matriks , maka n
x = ⊕ ( yi ⊗ ui ) i =1
Sehingga, untuk dengan λ ( A) = 0 , berlaku m
m
i =1
i =1
A ⊗ ⊕ ( yi ⊗ ui ) = ⊕ ( yi ⊗ ui )
⊕ (( A ⊗ u ) ⊗ y ) = ⊕ (u m
m
i
i =1
m
i
i =1
m
i
⊗ yi )
⊕ (Ci ⊗ yi ) = ⊕ ( Di ⊗ yi ) i =1
i =1
C⊗ y = D⊗ y Jadi, adalah penyelesaian dari .
Diketahui suatu matriks interval dengan dan misalkan adalah himpunan vektor eigen fundamental dari . n Akan dibuktikan terdapat x ∈ Rmax suatu vektor eigen universal dari . Misalkan adalah penyelesaian dari sistem persamaan dua-sisi , sehingga,
Terlihat bahwa dengan λ ( A) = 0 , adalah vektor eigen matriks . Karena adalah vektor eigen matriks batas A dan A , maka adalah vektor eigen semua matriks A ∈ A, yang berarti adalah vektor eigen universal dari . ■
Contoh 4.1 Diberikan matriks interval ⎡ 0, 0 ⎢ = ⎢ − 3, − 2 ⎢⎣ − 4 , − 1
− 1, 0 − 1, − 1 0, 0
− 2, 1 ⎤ ⎥ 0, 0 ⎥ − 4 , − 1 ⎥⎦
di mana λ ( A) = λ ( A) = 0 .
Himpunan vektor eigen fundamental dari matriks yaitu {(0,−3,−3), (−1,0,0)}. ⎡ 0 1⎤ ⎢ ⎥ Dibentuk matriks dengan , yaitu C = ⎢ − 2 0 ⎥ dan matriks dengan , yaitu D = ⎢⎣ − 1 0 ⎥⎦
⎡ 0 − 1⎤ ⎢− 3 0 ⎥ ⎢ ⎥. ⎢⎣ − 3 0 ⎥⎦
⎡ 0 − 1⎤ ⎡ 0 1⎤ ⎢− 2 0⎥ ⊗ y = ⎢− 3 0 ⎥ ⊗ y Salah satu penyelesaian system persamaan dua-sisi ⎢ adalah ⎢ ⎥ ⎥ ⎣⎢ − 3 0 ⎦⎥ ⎣⎢ − 1 0 ⎥⎦
⎡ 0⎤ y = ⎢ ⎥, ⎣− 1⎦ ⎛ ⎜ x = ⎜0 ⊗ ⎜ ⎝
sehingga
⎡ 0⎤⎞ ⎛ ⎢ − 3⎥ ⎟ ⊕ ⎜ − 1 ⊗ ⎢ ⎥⎟ ⎜ ⎢⎣ − 3 ⎥⎦ ⎟⎠ ⎜⎝
vektor
eigen
universal
dari
matriks
adalah
⎡ − 1⎤ ⎞ ⎡ 0 ⎤ ⎢ 0 ⎥ ⎟ = ⎢ − 1⎥ ⎢ ⎥⎟ ⎢ ⎥ ⎢⎣ 0 ⎥⎦ ⎟⎠ ⎢⎣ − 1⎥⎦
5. PENYELESAIAN SISTEM PERSAMAAN DUA-SISI Sistem persamaan linier dua-sisi atas aljabar max-plus yang berbentuk (3.4.1) dengan C ≥ D ............(5.1) n menotasikan himpunan indeks baris {1,2,...,n} dan m himpunan indeks kolom dari matriks dan . Lemma 5.1 Jika terdapat baris i sedemikian sehingga cij > d ij untuk setiap j , maka sistem tidak mempunyai solusi. Bukti : Misalkan vektor adalah solusi dari (5.1) dan pemaksimal dalam sisi ruas kiri dan sisi ruas kanan dari baris masing-masing diperoleh pada kolom ke dan , yaitu cij + y j = max k {cik + y k } dan d il + y l = max k {d ik + y k } dengan i ∈ n, dan j ∈ m .
Maka akan berlaku cij + y j ≥ cil + y l > d il + y l . Hasil kontradiksi dengan adalah . Sehingga terbukti bahwa sistem dengan tidak mempunyai solusi. ■
solusi
dari
Akibat 5.1 Jika sistem berbentuk (5.1) mempunyai penyelesaian, maka untuk setiap baris terdapat suatu indeks sedemikian sehingga berlaku . Bukti : Misalkan vektor adalah solusi dari (5.1). Akan dibuktikan bahwa untuk setiap baris terdapat suatu indeks sedemikian sehingga berlaku . Misalkan pemaksimal dalam sisi ruas kiri dan sisi ruas kanan dari baris masing-masing diperoleh pada kolom ke dan , yaitu cil + y l = max k {cik + y k } dan d ij + y j = max k {d ik + y k } dengan i ∈ n, dan j ∈ m . Sehingga akan berlaku . Dilain pihak, cij + y j ≤ cil + y l , maka cij + y j ≤ d ij + y j .
Karena , yang berarti memenuhi cij ≥ d ij untuk semua i ∈ n, dan j ∈ m , maka , dengan kata lain, . ■ Indeks pada akibat diatas, dinamakan indeks kritis untuk baris . Dalam pembahasan selanjutnya, K i menotasikan himpunan indeks kritis untuk baris . Lemma 5.2 Untuk setiap penyelesaian pada (5.1) terdapat indeks kritis pemaksimal untuk setiap baris . Bukti : Andaikan adalah penyelesaian pada (5.1), dan elemen pemaksimal baris pada dan 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 dari baris pada diperoleh cik + y k = cik + y j + cij − d ik . Karena cik ≥ d ik , maka berlaku cik + y k ≥ cij + y j . Akibatnya, apabila cik − d ik > 0 , maka cik + y k > cij + y j . Sehingga terjadi kontradiksi, karena indeks j bukan pemaksimal baris pada . Oleh karena itu, indeks adalah indeks kritis pemaksimal untuk baris pada . ■ Oleh karena itu, untuk mencari penyelesaian sistem persamaan dua-sisi (5.1) penting untuk memilih elemen pemaksimal yang sesuai dengan indeks kritis untuk setiap baris pada . Teorema 5.1 Suatu sistem (5.1) mempunyai penyelesaian jika dan hanya jika setiap tidak kosong, terdapat fungsi j : n → m sehingga j (i ) ∈ K i untuk semua i ∈ n dan untuk setiap subset {i1 , i2 ,..., ik } dari n , sedemikian sehingga j (i1 ), j (i2 ),..., j (ik ) saling berbeda,diperoleh pertidaksamaan (5.2): ci j (i ) + ci j (i ) + ... + ci j (i ) ≥ ci j (i ) + ci j (i ) + ... + ci j (i ) 1
1
Bukti :
Misalkan adalah solusi dari
2
2
k
k
1
2
2
3
k
1
Ambil sebarang subset {i1 , i2 ,..., ik } ⊆ n . Dengan lemma 5.2, yang menyatakan bahwa setiap baris terdapat indeks kritis pemaksimal , 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 suatu indeks kolom kritis sedemikian sehingga memenuhi pertidaksamaan 5.2. Dinotasikan j (n) = { j (i ); i ∈ n} sebagai himpunan indeks kolom dari kolom terpilih di dalam kolom , dan dibangun suatu submatriks yang dibuat dari kolom . Jumlah baris dengan indeks kolom terpilih di dalam kolom , dinotasikan dengan p ( j ) . Selanjutnya, ditinjau permasalahan untuk pemilihan pasangan indeks sebagai berikut : Memaksimalkan : Z = ∑i∈n ∑j∈ j (n) c'ij xij ∑ j∈ j ( n) xij = 1 untuk semua i ∈ n
∑
i∈n
xij = p( j ) untuk semua j ∈ j (n) xij ≥ 0 untuk semua dan
Akan ditunjukkan bahwa salah satu penyelesaian optimal bulat yang mungkin adalah xij (i ) = 1 untuk dan xij = 0 untuk yang lainnya. Andaikan bahwa 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 , maka terdapat baris i2 ∈ n sedemikian sehingga j = j (i2 ) dan xi2 j (i2 ) = 0 . Karena kapasitas baris adalah 1, maka terdapat indeks kolom j = j (i3 ) untuk beberapa baris sedemikian sehingga xi2 j (i3 ) = 1 , dan , dan seterusnya. Dengan cara ini, diperoleh suatu cycle indeks baris sedemikian sehingga xil j (il ) = 0 dan untuk semua dengan . Didefinisikan solusi baru dengan x' il j (il ) = 1 dan untuk semua dengan , dan xij = 0 untuk semua pasangan indeks lainnya. Kemudian, karena memenuhi pertidaksamaan (5.2), nilai ∑i∈n ∑ j∈ j (n) 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 dan untuk yang lainnya. Sekarang, dibentuk dual dari masalah diatas sebagai berikut : Meminimalkan: Z d = ∑i∈n ui + ∑j∈ j (n) p( j)v j u i + v j ≥ c'ij untuk semua , dan . Definisikan vektor yang dinyatakan sebagai berikut : ⎧− ∞ ; untuk j ∉ j (n) yj = ⎨ ⎩− v j ; untuk j ∈ j (n)
adalah suatu solusi optimal dari (5.1). Karena pada setiap baris dapat dipilih suatu indeks kolom kritis , maka diperoleh cij (i ) + y j (i ) = d ij (i ) + y j (i ) Selanjutnya akan ditunjukkan bahwa untuk semua kolom lain , memenuhi cil + y l ≤ cij (i ) + y j (i ) . Untuk l ∉ j (n) pertidaksamaan ini trivial, dan untuk kolom-kolom dari 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) − v j (i) = cij(i) + y j (i) Dari sini terlihat bahwa vektor mempunyai indeks kritis pemaksimal untuk setiap baris yaitu j (i ) . Sehingga vektor adalah penyelesaian dari persamaan (5.1). ■ Contoh 5.1 ⎡1 2 4 8 ⎤ ⎡0 1 4 5 ⎤ ⎢ ⎥ ⎢ ⎥ Diberikan matriks C = ⎢6 3 9 4⎥ dan D = ⎢2 3 9 2⎥ ⎢⎣7 3 8 0⎥⎦ ⎢⎣7 3 7 0⎥⎦ Akan dicari penyelesaian sistem persamaan dua-sisi . Matriks 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 submatriks 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 : Kendala : x11 + x12 = 1 x 21 + x 22 = 1 x31 + x32 = 1 x11 + x 21 + x31 = 1 xij ≥ 0 untuk semua dan Kemudian, dibentuk permasalahan dual dari masalah pemilihan indeks diatas sebagai berikut :
Meminimalkan : Z d = u1 + u2 + u3 + v1 + 2v2 Kendala : Vektor y yang dinyatakan dengan adalah u1 + v1 ≥ 1 u 2 + v2 ≥ 9 penyelesaian dari sistem persamaan dua-sisi u1 + v 2 ≥ 4 u 3 + v1 ≥ 7 diatas. u 2 + v1 ≥ 6 u3 + v2 ≥ 8 Nilai u i dan yang memenuhi : u1 + v1 ≥ 1 u 2 + v2 = 9 u1 + v 2 = 4 u 3 + v1 = 7 u 2 + v1 ≥ 6 u3 + v2 ≥ 8 adalah solusi dari permasalahan dual diatas. Dengan mengambil nilai , maka dapat diperoleh salah satu kemungkinan solusi dari permasalahan diatas yaitu u1 = 3, u 2 = 8, u 3 = 7, v1 = 0, v 2 = 1 . ⎡ 0 ⎤ ⎢− ∞ ⎥ ⎥ Sehingga diperoleh salah satu penyelesaian dari sistem dua-sisi diatas yaitu y = ⎢ ⎢ −1 ⎥ ⎥ ⎢ ⎣− ∞ ⎦
6. PENUTUP Berdasarkan uraian mengenai nilai dan vektor eigen matriks interval atas aljabar maxplus 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 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 dapat dicari dengan menyelesaikan suatu sistem persamaan dua-sisi. 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, Katarina, (2003), Eigenvectors of Interval Matrices over Max-Plus Algebra, Slovakia. [ 3 ] Chiao, Kuo-Ping, (1999), Inclusion Monotonic Property of Courant-Fischer Minimax Characterization on Interval Eigenproblems for Symmetric Interval Matrices. Alethia University. [ 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.
