PROSIDING
ISBN : 978 – 979 – 16353 – 9 – 4
A-5 SISTEM PERSAMAAN LINEAR MIN-PLUS DAN PENERAPANNYA PADA MASALAH LINTASAN TERPENDEK M. Andy Rudhito1 1
Program Studi Pendidikan Matematika FKIP Universitas Sanata Dharma Kampus III USD Paingan Maguwoharjo Yogyakarta 1 e-mail:
[email protected]
Abstrak Artikel ini membahas tentang sistem persamaan linear min-plus dan penerapannya pada masalah lintasan terpendek. Pembahasan merupakan hasil kajian teoritis yang didasarkan literatur dan suatu perhitungan menggunakan program MATLAB. Hasil pembahasan menunjukkan bahwa jaringan dengan bobot waktu tempuh dapat dimodelkan sebagai graf berarah terbobot yang dapat dinyatakan dengan matriks atas aljabar min-plus. Penentuan waktu tempuh minimal dapat dilakukan melaui operasi star pada matriks bobot jaringannya. Lintasan terpendek dapat ditentukan dengan memodifikasi metode PERT-CPM pada analisis lintasan kritis pada jaringan proyek. Dengan memodelkan waktu tempuh perjalanan pada jaringan ke dalam suatu sistem persamaan (SPL) linear iteratif min-plus. Dari penyelesaian SPL min-plus ini, dapat ditentukan waktu awal paling cepat dan waktu paling akhir, untuk masing-masing titik. Titik-titik dengan waktu awal paling cepat dan waktu paling akhir yang sama akan membentuk lintasan terpendek pada jaringan. Kata kunci: Aljabar Min-Plus, Sistem Persamaan Linear, Lintasan Terpendek.
A. PENDAHULUAN Aljabar max-plus (himpunan R {}, dengan R adalah himpunan semua bilangan real, yang dilengkapi dengan operasi maximum dan penjumlahan) telah digunakan untuk memodelkan dan menganalisis sistem produksi sederhana, dengan fokus analisa pada masalah input-output sistem (Baccelli et.al, 2001 dan Rudhito, 2003). Pemodelan dan analisis sifat-sifat suatu jaringan antrian juga telah dilakukan dengan pendekatan aljabar max-plus, seperti dalam Krivulin (2000) dan Rudhito (2011). Penerapan aljabar max-plus pada masalah analisis lintasan kritis juga telah dibahas dalam Rudhito (2010). Pemodelan dan analisa suatu jaringan dengan pendekatan aljabar max-plus ini dapat memberikan hasil analitis dan lebih mudah pada komputasinya. Selain aljabar max-plus, dalam Baccelli et.al. (2001), Gondran and Minoux (2008) dan John and George (2010) telah disinggung beberapa varian aljabar yang serupa dengan aljabar max-plus, seperti aljabar min-plus (dengan operasi minimum dan penjumlahan) dan aljabar max-min (dengan operasi maximum dan minimum). Diberikan pula dalam referensi di atas, beberapa gambaran singkat mengenai ilustrasi penerapannya yang terkait dengan masalah-masalah dalam teori graf, seperti masalah lintasan terpendek dan masalah kapasitas maksimum suatu lintasan dalam jaringan. Seperti halnya dalam aljabar max-plus, dengan pendekatan aljabar yang serupa diharapkan masalah-masalah yang terkait dapat dimodelkan dan perhitungan-perhitungan masalah-masalah yang terkait dapat dilakukan secara lebih analitis. Makalah ini akan membahas tentang sistem persamaan linear iteratif min-plus dan penerapannya pada masalah penentuan lintasan terpendek pada suatu jaringan graf berarah berbobot. Pembahasan sistem persamaan linear iteratif min-plus akan dilakukan dengan membandingkan hasil yang telah diperoleh pada eksistensi dan ketunggalan penyelesaian sistem persamaan linear max-plus (Baccelli et.al, 2001 dan Rudhito, 2011). Sedangkan pembahasan pada masalah penentuan lintasan terpendek akan dilakukan dengan membandingkan hasil pada Makalah dipresentasikan dalam Seminar Nasional Matematika dan Pendidikan Matematika dengan tema ” Penguatan Peran Matematika dan Pendidikan Matematika untuk Indonesia yang Lebih Baik" pada tanggal 9 November 2013 di Jurusan Pendidikan Matematika FMIPA UNY
PROSIDING
ISBN : 978 – 979 – 16353 – 9 – 4
analisis lintasan kritis jaringan proyek dengan pendekatan aljabar max-plus (Rudhito, dkk. 2010) Untuk memudahkan dalam perhitungan numeriknya, akan disusun pula suatu program komputer dengan menggunakan MATLAB. Dari hasil pembahasan makalah ini diharapkan sebagai langkah awal untuk ke masalah berikutnya yang lebih kompleks, seperti menentukan aliran (flow) maksimum dalam suatu jaringan. B. PEMBAHASAN Pada bagian awal akan dibahas konsep-konsep dasar aljabar min-plus dan matriks atas aljabar min-plus, serta konsep dasar dalam teori graf yang terkait. Aljabar min-plus ini mempunyai struktur yang isomorfis dengan aljabar max-plus (Gondran and Minoux, 2008, Baccelli et.al, 2001). Diberikan R := R { } dengan : = +. Pada R didefinisikan operasi berikut: a,b R, a b := min(a, b) dan a b : = a b. Dapat ditunjukkan bahwa (R, , ) merupakan semiring komutatif idempoten dengan elemen netral = + dan elemen satuan e = 0. Lebih lanjut (R, , ) merupakan semifield, yaitu bahwa (R, , ) merupakan semiring komutatif di mana untuk setiap a R terdapat a sehingga berlaku a (a) = 0. Kemudian (R , , ) disebut dengan aljabar min-plus, yang selanjutnya cukup dituliskan dengan Rmin. Relasi “ m ” yang didefinisikan pada Rmin sebagai berikut x m y jika x y = y, merupakan urutan parsial pada Rmin. Lebih lanjut relasi ini merupakan urutan total 0
k
pada Rmin. Pangkat k elemen x R dilambangkan dengan x didefinisikan dengan x := 0, k
x := x x
k 1
k
0
. Didefinisikan pula : = 0 , untuk k = 1, 2, ... ε : = . n Operasi dan pada Rmin dapat diperluas untuk operasi-operasi matriks dalam R m min , di
n m n mana R m min : = {A = (Aij)Aij Rmin, untuk i = 1, 2, ..., m dan j = 1, 2, ..., n}. Untuk A, B R max p p n didefinisikan A B, dengan (A B)ij = Aij Bij . Untuk matriks A R m min , B R min
p
didefinisikan A B, dengan (A B)ij =
A
ik
n Bkj . Didefinisikan pula matriks E R n min ,
k 1
0 , jika i j n dan matriks R m min , ( )ij := untuk setiap i dan j . Pangkat k ε , jika i j
dengan (E )ij :=
0
k
n matriks A R n = En dan A = A A min didefinisikan dengan A
k 1
untuk k = 1, 2, ... .
Suatu graf berarah G didefinisikan sebagai suatu pasangan G = (V, A) dengan V adalah suatu himpunan berhingga tak kosong yang anggotanya disebut titik dan A adalah suatu himpunan pasangan terurut titik-titik di V. Anggota A disebut busur. Suatu lintasan dalam graf berarah G adalah suatu barisan berhingga busur (i1, i2), (i2, i3), ... , (il1, il) dengan (ik, ik+1) A untuk suatu l N , di mana N = himpunan semua bilangan asli, dan k = 1, 2, ... , l 1. Lintasan di atas dapat direpresentasikan dengan i1 i2 ... il. Titik i1 disebut titik awal lintasan dan titik il disebut titik akhir lintasan. Panjang suatu lintasan didefinisikan sebagai banyak busur yang menyusun lintasan tersebut. Suatu lintasan disebut sirkuit jika titik awal dan titik akhirnya sama. Suatu graf berarah G = (V, A) dengan V = {1, 2, , ... , n} dikatakan terhubung kuat jika untuk setiap i, j V, i j , terdapat suatu lintasan dari i ke j. Suatu graf yang memuat sirkuit disebut graf siklik, sedangkan suatu graf yang tidak memuat sirkuit disebut graf taksiklik. Diberikan graf berarah G = (V, A) dengan V = {1, 2, ... , p}. Graf berarah G dikatakan berbobot jika setiap busur ( j, i ) A dikawankan dengan suatu bilangan real Aij. Bilangan real Aij disebut bobot busur (j, i ), dilambangkan dengan w( j, i ). Bobot suatu lintasan didefinisikan sebagai jumlahan bobot busur-busur yang menyusun lintasan tersebut. Lintasan terpendek
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 9 November 2013
MA-30
PROSIDING
ISBN : 978 – 979 – 16353 – 9 – 4
n didefinisikan sebagai lintasan dengan bobot minimum. Graf preseden dari matriks A R nmax
adalah graf berarah berbobot G(A) = (V, A) dengan V = {1, 2, ... , n}, A = {( j, i ) | w( i, j ) = Aij , i, j }. Sebaliknya untuk setiap graf berarah berbobot G = (V, A) selalu dapat didefinisikan w( j, i) , jika ( j, i) A n suatu matriks A R n , yang disebut matriks bobot graf min dengan Aij = jika ( j, i) A . , k
n G. Dalam kaitannya dengan teori graf, untuk A R n ) st min dan k N, unsur matriks ( A merupakan bobot minimum semua lintasan dalam G(A) dengan panjang k, dengan t sebagai titik awal dan s sebagai titik akhirnya. n Suatu matriks A R n min dikatakan semi-definit jika semua sirkuit dalam G(A) mempunyai bobot takpositif dan dikatakan definit jika semua sirkuit dalam G(A) mempunyai bobot negatif. n Diberikan A R n min . Dengan cara yang analog dengan kasus di aljabar max-plus (Baccelli et.al,
2001), dapat ditunjukkan bahwa jika A semi-definit, maka p n, A A
n 1
A
p
m
E A ... *
n . Selanjutnya untuk matriks semi-definit A R n min , dapat didefinisikan A : = E A ...
n
A
n 1
... . Didefinisikan R nmin := { x = [ x1, x2, ... , xn]T | xi Rmin, i = 1, 2, ... , n}.
Untuk setiap x, y R nmin dan Rmin berturut-turut didefinisikan operasi penjumlahan dan operasi perkalian skalar sebagai berikut : x y = [x1 y1, x2 y2, ... , xn yn]T dan x = 1 x = [ x1, x2, ... , xn ]T. Perhatikan bahwa R nmin dapat dipandang sebagai R nmin . Dapat ditunjukkan bahwa R nmax merupakan semimodul atas semified Rmin. Unsur-unsur dalam R nmax disebut vektor atas Rmin. Eksistensi dan ketunggalan penyelesaian sistem persamaan linear iterarif min-plus analog dengan hasil pada eksistensi dan ketunggalan sistem persamaan linear iteratif max-plus seperti n n yang dibahas dalam Baccelli et.al (2001). Diberikan A R n min dan b R min . Jika A semi-definit, maka vektor x* = A* b merupakan suatu penyelesaian sistem x = A x b. Lebih lanjut jika A definit, maka sistem tersebut mempunyai penyelesaian tunggal. Selanjutnya dibahas masalah lintasan terpendek. Pembahasan diawali dengan meninjau beberapa pengertian dasar, dilanjutkan dengan memberikan pemodelan dan analisa dengan pendekatan aljabar min-plus dan memberikan contoh perhitungannya. Definisi 1 Suatu jaringan lintasan searah S adalah suatu graf berarah berbobot terhubung kuat taksiklik = (V, A), dengan V = {1, 2, , ... , n} yang memenuhi: jika (i, j) A, maka i < j.
S
Dalam jaringan proyek ini, titik menyatakan persimpangan, busur menyatakan suatu jalan, sedangkan bobot busur menyatakan waktu tempuh, sehingga bobot dalam jaringan selalu positip. Selanjutnya dilakukan pemodelan dan analisis lintasan terpendek, yaitu lintasan dengan waktu tempuh minimum. Pembahasan diawali dengan menentukan waktu awal paling cepat (earliest start time) untuk setiap persimpangan titik i dapat dilalui. Pembahasan dilakukan dengan mengadopsi dan memodifikasi teknik perhitungan maju (forward) seperti pada PERT-CPM, dengan menggunakan pendekatan aljabar-min-plus. Misalkan xie = menyatakan waktu awal paling cepat titik i dapat dilalui, waktu tempuh dari titik j ke titik i , jika ( j,i ) A Aij = jika ( j, i) A. ( ),
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 9 November 2013
MA-31
PROSIDING
ISBN : 978 – 979 – 16353 – 9 – 4
Dalam pembahasan ini diasumsikan bahwa perjalanan dalam jaringan dimulai pada titik 1 pada saat waktu tempuh sama dengan nol, yaitu x1e = 0, diasumsikan pula tidak ada waktu singgah di persimpangan, sehingga dapat dituliskan jika i 1 0, xie = min ( A x e ) , jika i 1. j 1 j n ij Dengan menggunakan notasi aljabar min-plus persamaan di atas dapat dituliskan menjadi jika i 1 0, e xie = (1) ( Aij x j ) , jika i 1. 1 j n Misalkan A adalah matriks yang bersesuaian dengan graf berarah berbobot jaringan tersebut, xe = [ x1e , x2e , ... , xne ]T dan be = [0, , ... , ]T, persamaan (1) dapat dituliskan ke dalam suatu sistem persamaan linear min-plus berikut xe = A xe be (2) Karena jaringan lintasan searah merupakan graf berarah taksiklik, maka tidak terdapat sirkuit, sehingga semua sirkuit dalam jaringan mempunyai bobot takpositif. Dengan demikian xe = A* be (3) merupakan penyelesaian sistem (2) di atas. Karena jumlah titik dalam jaringan proyek ini adalah n, maka panjang lintasan terpanjangnya tidak akan melebihi n 1. Dengan demikian dalam hal ini persamaan (3) dapat ditulis menjadi n 1 xe = A* be = (E A ... A ) be yang merupakan vektor waktu paling awal setiap titik i dapat dilalui. Perhatikan bahwa (A*)n1 merupakan bobot minimum lintasan dari titik awal hingga titik akhir proyek, sehingga xne merupakan waktu tempuh minimal untuk melintasi jaringan.
Dari pembahasan di atas dapat disimpulkan dalam Teorema 1 berikut. Teorema 1 Diberikan suatu jaringan lintasan searah dengan n titik dan A adalah matriks bobot graf berarah berbobot jaringan tersebut. Vektor waktu awal paling cepat titik i dilalui diberikan oleh n 1 xe = (E A ... A ) be di mana be = [0, , ... , ]T. Lebih lanjut xne merupakan waktu tercepat untuk melintasi jaringan. Bukti: (lihat uraian di atas) . ■ Selanjutnya setelah diketahui waktu tercepat untuk melintasi jaringan ( xne ) akan ditentukan lintasan mana yang dilalui. Pembahasan dilakukan dengan mengadopsi dan memodifikasi teknik perhitungan mundur (backward) seperti pada PERT-CPM, dengan menggunakan pendekatan aljabar-min-plus. Misalkan xil = waktu paling akhir perjalanan meninggalkan titik i, waktu temp uh dari titik i ke titik j , jika ( j,i) A Bij = jika ( j, i) A. ( ),
Diasumsikan bahwa xnl = xne , kemudian dapat dituliskan xne , jika i n x = l max( Bij x j ) , jika i 1. 1 j n l i
(4) Dengan menggunakan notasi aljabar min-plus persamaan (4) ekivalen dengan
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 9 November 2013
MA-32
PROSIDING
ISBN : 978 – 979 – 16353 – 9 – 4
xne , jika i n x = l min ( B x j ) , jika i 1. 1 j n ij l i
(5) Perhatikan bahwa matriks B = AT, dengan A adalah matriks bobot graf berarah berbobot jaringan tersebut. Misalkan z = [z1, z2, ... , zn]T = xl = [ x1l , x2l , ... , xnl ]T dan bl = [, , ... , xne ]T, persamaan (5) dapat dituliskan menjadi z = AT z bl . (6) yang penyelesaiannya adalah z = (AT )* bl . Dengan demikian diperoleh vektor waktu paling akhir perjalanan adalah xl = z. Dari pembahasan di atas dapat disimpulkan dalam Teorema 2 berikut. Teorema 2 Diberikan suatu jaringan lintasan searah dengan n titik dan A adalah matriks bobot graf berarah berbobot jaringan tersebut. Vektor waktu paling akhir perjalanan diberikan oleh xl = ( (AT )* bl ) di mana bl = [, , ... , xne ]T. ■
Bukti: (lihat uraian di atas) .
Dari hasil pada Teorema 1 dan Teorema 2 di atas, dapat ditentukan lintasan terpendek pada jaringan lintasan searah. Mengingat waktu singgah pada persimpangan adalah nol, dan telah diketahui bahwa xne merupakan waktu tercepat untuk melintasi jaringan, maka persimpangan yang dilalui lintasan terpendek yang dicari adalah titik-titik i di mana xil = xie . Berikut diberikan contoh suatu jaringan lintasan searah dan perhitungannya. Contoh 1 Perhatikan jaringan lintasan searah seperti yang diberikan pada Gambar 1 berikut : 5 2 3
5
7
3
6
1 3 2
2 2
6
3 4
7
7
Gambar 1 Contoh Jaringan lintasan searah Matriks bobot graf berarah berbobot pada jaringan proyek di atas adalah matriks A di bawah ini. Dengan menggunakan program yang disusun dengan menggunakan MATLAB dengan input matriks A berikut, diperoleh output program sebagai berikut.
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 9 November 2013
MA-33
PROSIDING
2 3 A =
2
ISBN : 978 – 979 – 16353 – 9 – 4
3 2
0 3 7
7 5
6
, A* =
0 2 3 4 4 7 9
0 2 2 5 7
0 3 2 6 7
0 0 3 5
0 7 5
0 6
, xe = 0
0 2 3 l 4 dan x = 4 7 9
0 2 2 4 . 4 3 9
Dari hasil di atas nampak bahwa waktu tempuh minimal untuk melintasi lintasan adalah 9 dan lintasan terpendek yang diperoleh adalah lintasan : (1, 2), (2, 4), (4, 5), (6, 7). C. SIMPULAN Dari hasil pembahasan dapat disimpulkan bahwa jaringan lintasan searah dengan bobot waktu tempuh dapat dimodelkan sebagai graf berarah terbobot yang dapat dinyatakan dengan matriks atas aljabar min-plus. Penentuan waktu tempuh minimal dapat dilakukan melaui operasi star (*) pada matriks bobot jaringannya. Lintasan terpendek dapat ditentukan melalui penentuan waktu awal paling cepat untuk melewati titik dan waktu paling akhir meninggalkan titik, untuk masing-masing titik pada jaringan. Hal ini dapat dilakukan terlebih dahulu memodelkan waktu tempuh perjalanan pada jaringan ke dalam suatu sistem persamaan (SPL) linear iteratif min-plus. Selanjutnya menyelesaikan SPL min-plus dapat ditentukan waktu awal paling cepat dan waktu paling akhir tersebut. Titik-titik dengan waktu awal paling cepat dan waktu paling akhir yang sama akan membentuk lintasan terpendek pada jaringan. Lebih lanjut dapat dilakukan penelitian mengenai kelebihan dan kelemahan metode di atas dibandingan dengan metode-metode lintasan terpendek yang telah ada, analisis algoritma dan pendekatan aljabar min-plus untuk masalah-masalah yang terkait dengan lintasan terpendek lebih lanjut. D. DAFTAR PUSTAKA Baccelli, F., Cohen, G., Olsder, G.J. and Quadrat, J.P. 2001. Synchronization and Linearity. New York: John Wiley & Sons. John S. Baras and George Theodorakopoulos. 2010. Path Problems in Networks. Synthesis Lectures on Communication Networks. Morgan & Claypool Publishers. Gondran, M and Minoux, M. 2008. Graph, Dioids and Semirings. New York: Springer. Krivulin, N.K., Algebraic Modelling and Performance Evaluation of Acyclic Fork-Join Queueing Networks. Advances in Stochastic Simulation Methods, Statistics for Industry and Technology. Birkhauser, Boston, 63-81, 2000 Rudhito MA, 2003, Sistem Linear Max-Plus Waktu-Invariant, Tesis: Program Pascasarjana Universitas Gadjah Mada, Yogyakarta Rudhito MA, Wahyuni S, Suparwanto A, dan Susilo F. 2010. Analisis Lintasan Kritis Jaringan Proyek dengan Pendekatan Aljabar Max-Plus. Jurnal Matematika Vol 12 No. 3. pp. 128-133 Rudhito, Andy. 2011. Aljabar Max-Plus Bilangan Kabur dan Penerapannya pada Masalah Penjadwalan dan Jaringan Antrian Kabur. Disertasi: Program Pascasarjana Universitas Gadjah Mada. Yogyakarta.
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 9 November 2013
MA-34
