ALJABAR MAX-PLUS DAN PENERAPANNYA
M. Andy Rudhito
Program Studi Pendidikan Matematika FKIP Universitas Sanata Dharma Yogyakarta 2016
ii
PRAKATA Aljabar max-plus merupakan suatu struktur aljabar di mana himpunan semua bilangan real R {} dilengkapi dengan operasi max (maksimum) dan plus (penjumlahan). Aljabar ini berawal tahun 70an, tetapi baru berkembang dengan pesat sekitar tahun 90an. Permasalahan-permasalahan dalam jaringan (teori graf) yang terutama terkait dengan masalah sinkronisasi dapat dimodelkan dan diselesaikan dengan baik dengan aljabar max-plus. Permasalahan di atas yang dengan menggunakan matematika biasa berupa model matematika yang nonlinear, dengan menggunakan aljabar max-plus ini dapat berupa model yang linear dalam operasinya. Buku ini disajikan dalam beberapa bab dengan sistematika sebagai berikut. Bab 1 pendahuluan dan motivasi yang berisi masalah-masalah yang dapat dimodelkan dan diselesaikan dengan menggunakan aljabar max-plus, di antaranya adalah masalah sistem jaringan kereta api, sistem produksi sederhana, penjadwalan dalam jaringan proyek dan jaringan antrian. Bab 2 membahas konsep-konsep dasar aljabar max-plus yang meliputi matriks dan struktur aljabarnya. Bab 3 membahas tentang sistem persamaan linear max-plus, yang meliputi sistem input output dan sistem iteratif. Sistem persamaan linear max-plus ini akan digunakan sebagai dasar pemodelan masalah dengan menggunakan aljabar max-plus. Selanjutnya dibahas beberapa penerapan dari sistem persamaan linear max-plus. Bab 4 membahas tentang nilai eigen matriks atas aljabar max-plus. Nilai eigen ini sangat terkait dengan permasalahan yang terkait dengan sifat-sifat periodik dinamika jaringan. Dibahas pula beberapa penerapan dari konsep nilai dan vektor eigen maxplus ini terkait sifat periodik sistem. Bab 5 membahas varian lain aljabar max-plus, yakni aljabar min-plus dan aljabar max-min beserta penerapannya. Pembahasan dalam buku ini agak mengalami kesulitan kalau tidak dibantu aspek komputasinya dengan menggunakan komputer. Dalam tiap babnya akan diberikan aspek komputasinya dengan menggunakan bahasa MATLAB.
iii
Pada kesempatan ini penulis mengucapkan terimakasih kepada kolega dosen di Universitas Sanata Dharma yang telah memberikan dukungan positip. Jurusan Matematika FMIPA UGM, khusus dosen-dosen kuliah dan pembimbing tugas akhir selama penulis menempuh S2 dan S3. Para dosen dan mahasiswa dari berbagai perguruan tinggi di Indonesia yang telah mendiskusikan topik ini dalam berbagai kesempatan seminar dan perjumpaan-perjumpaan baik online maupun offline. Mahasiswa bimbingan skripsi saya, Regina Wahyudyah Sonata Ayu, yang telah bekerja keras menyelesaikan skripsi topik aljabar max-plus, di mana hasilnya juga merupakan bagian dari susunan buku ini. Akhirnya semoga buku ini bermanfaat dan dapat digunakan dalam kehidupan sehari-hari, maupun dikembangkan sebagai kajian ilmu matematika
Yogyakarta, Pebruari 2016
Penulis (e-mail:
[email protected])
iv
DAFTAR ISI
PRAKATA ...................................................................................................
iii
DAFTAR ISI ................................................................................................
iv
BAB 1 PENDAHULUAN ............................................................................
1
1.1
Sistem Jaringan Kereta Api ......................................................
1
1.2
Sistem Produksi Sederhana ......................................................
4
1.3
Penjadwalan Jaringan Proyek ...................................................
7
1.4
Jaringan Antrian........................................................................
9
BAB 2 ALJABAR MAX-PLUS DAN MATRIKS .......................................
12
2.1
Aljabar Max-Plus ......................................................................
12
2.2
Matriks atas Aljabar Max-Plus .................................................
15
2.3
Semimodul atas Aljabar Max-Plus ...........................................
23
BAB 3 SISTEM PERSAMAAN LINEAR MAX-PLUS DAN PENERAPANNYA ................................................................. 3.1
28
Sistem Persamaan Linear Input-Output (SPLIO) Max-Plus .................................................................................. .
28
3.2
Penerapan pada Sistem Produksi Sederhana .............................
37
3.3
Eksistensi dan Ketunggalan SPLIO Max-Plus ..........................
58
3.4
Penerapan pada Masalah Ramp-Handling Pesawat .................
75
3.5
Aljabar Matriks dan Teori Graf .................................................
83
3.6
Sistem Persamaan Linear Iteratif (SPLI) Max-Plus ..................
93
3.7
Penerapan pada Penjadwalan Proyek ........................................
98
BAB 4 NILAI, VEKTOR EIGEN MAX-PLUS DAN PENERAPANNYA... 111 4.1
Nilai Eigen dan Vektor Eigen Max-Plus ................................... 111
4.2
Penerapan pada Penjadwalan Kereta .......................................... 119
4.3
Penerapan Analis Model Antrian ................................................ 123
BAB 5 ALJABAR MIN-PLUS DAN ALJABAR MAX-MIN SERTA PENERAPANNYA .............................................................................. 128 5.1
Aljabar Min-Plus ........................................................................ 128 v
5.2
Penerapan Aljabar Min-Plus pada Masalah Lintasan Terpendek ................................................................................... 132
5.3
Aljabar Max-Min ........................................................................ 140
5.4
Penerapan Aljabar Max-Min pada Masalah Kapasitas Maksimum ................................................................................. 145
DAFTAR PUSTAKA ..................................................................................... 148 INDEKS ........................................................................................................... 151
vi
BAB I PENDAHULUAN
Dalam kehidupan sehari-hari terdapat beberapa masalah yang dapat dimodelkan secara matematis dengan sistem dinamika, misalnya sistem produksi perakitan, sistem jaringan telekomunikasi, sistem pemrosesan paralel pada komputer, sistem jaringan kereta, dan sebagainya. Dalam bab ini akan diberikan masalah-masalah dalam sistem jaringan kereta api, sistem produksi sederhana, penjadwalan dalam jaringan kerja dan jaringan antrian yang dapat dimodelkan dengan menggunakan aljabar max-plus.
1.1 Sistem Jaringan Kereta Api Diperhatikan suatu sistem jaringan kereta sederhana yang disajikan dalam Gambar 1.1.1 berikut: 5
3
2
3
Gambar 1.1.1 Jaringan Kereta Api Sederhana
Misalkan di suatu kota terdapat dua stasiun kereta S1 dan S 2 yang dihubungkan dengan suatu jaringan rel kereta seperti pada Gambar 1.1.1 di atas, dengan dua kereta untuk tiap stasiun. Misalkan pada waktu keberangkatan pertama empat kereta tersebut melakukan perjalanan sebagai berikut. Kereta pertama berangkat dari stasiun S1 , mengantar dan menjemput penumpang di pinggiran kota dan kembali ke S1 . Kereta kedua berangkat dari stasiun S1 , mengantar dan menjemput penumpang di tengah kota dan menuju ke stasiun S 2 . Kereta ketiga berangkat dari stasiun S 2 , mengantar dan menjemput penumpang di tengah kota dan menuju ke stasiun S1 . Kereta keempat berangkat dari stasiun S 2 , mengantar dan menjemput
1
2
penumpang di pinggiran kota dan kembali ke S1 . Pada waktu keberangkatan kedua perjalanan kereta sebagai berikut. Kereta pertama dan keempat kembali melakukan perjalanan seperti pada waktu perjalanan sebelumnya. Kereta kedua berangkat dari stasiun S 2 , mengantar dan menjemput penumpang di tengah kota dan menuju ke stasiun S1 . Kereta ketiga berangkat dari stasiun S1 , mengantar dan menjemput penumpang di tengah kota dan menuju ke stasiun S 2 . Pada waktu keberangkatan ketiga perjalanan kereta seperti pada waktu perjalanan pertama, demikian seterusnya. Dengan demikian jaringan rel kereta ini dapt dipandang terdiri dari satu lingkar dalam ( S1 S 2 S1 ) dan dua lingkar luar ( S1 S1 dan
S 2 S 2 ). Kereta mencapai stasiun lain (atau yang sama) setelah suatu waktu tertentu, yang disebut sebagai waktu perjalanan, seperti yang ditunjukkan pada Gambar 1.1.1 di atas. Keberangkatan kereta di suatu stasiun harus menunggu kedatangan kereta yang lain sehingga penumpang mempunyai kesempatan berganti kereta untuk menuju tempat yang diinginkan. Waktu untuk menunggu kereta lain dan penumpang berganti kereta ini telah diperhitungkan dalam waktu perjalanan. Stasiun di pinggiran kota tidak dipertimbangkan karena tidak mempunyai peranan yang penting dalam pemodelan. Misalkan tidak ada jadwal keberangkatan kereta dan kereta langsung berangkat setelah penumpang berganti kereta pada suatu stasiun. Didefinisikan :
xi (k+1) : waktu keberangkatan ke-k + 1 pada stasiun Si untuk i = 1, 2 . Jika proses keberangkatan dan kedatangan suatu kereta berkesinambungan, maka didapat: x1 (k+1) = max (2 + x1 (k), 5 + x2 (k)),
(1.1.1) x2 (k+1) = max (3 + x1 (k), 3 + x2 (k) ),
untuk k = 0, 1, 2, ... . Jika operasi max dinotasikan dengan , operasi penjumlahan dinotasikan dengan , maka persamaan (1.1.1) dapat dituliskan sebagai berikut: x1 (k+1) = ( x1 (k) 2) ( x2 (k) 5),
3
(1.1.2) x2 (k+1) = ( x1 (k) 3) ( x2 (k) 3).
Jika persamaan (1.1.2) di atas dituliskan dalam persamaan matriks, dengan cara yang serupa pada aljabar matriks biasa, di mana operasi penjumlahan diganti operasi maksimum dan operasi perkalian diganti dengan operasi penjumlahan, maka diperoleh persamaan matriks berikut: [
𝑥1 (𝑘 + 1) ]= 𝑥2 (𝑘 + 1)
𝑥1 (𝑘) 2 5 3 3 [𝑥2 (𝑘)]
(1.1.3)
Persamaan (1.1.3) di atas secara ringkas dapat juga dituliskan sebagai x(k+1) = A x(k)
(1.1.4)
2 5 dengan x(k) = [ x1 (k), x2 (k)] T dan A = . 3 3
Dalam prakteknya jaringan rel kereta beroperasi berdasarkan jadwal keberangkatan. Jadwal keberangkatan terdiri dari waktu keberangkatan kereta dari semua stasiun. Hal ini berarti bahwa sebuah kereta tidak dapat meninggalkan stasiun sebelum waktu jadwal keberangkatannya, meskipun kereta yang ditunggunya telah datang. Didefinisikan:
d i (k + 1) : jadwal keberangkatan ke-(k+1) pada stasiun Si untuk i = 1, 2 . Kemudian didapat xi (k+1) untuk i = 1, 2 sebagai berikut: x1 (k+1) = max ( x1 (k) + 2, x2 (k) + 5, d1 (k + 1)),
(1.1.5) x2 (k+1) = max ( x1 (k) + 3, x2 (k) + 3, d 2 (k + 1)),
untuk k = 0, 1, 2, ... . Jika operasi max dinotasikan dengan , operasi penjumlahan dinotasikan dengan , maka, persamaan (1.1.5) atas dapat dituliskan sebagai berikut: x1 (k+1) = ( x1 (k) 2) ( x1 (k) 5) d1 (k + 1),
(1.1.6) x2 (k+1) = ( x1 (k) 3) ( x2 (k) 3) d 2 (k + 1),
4
untuk k = 0, 1, 2, ... . Jika persamaan (1.1.6) dituliskan dalam persamaan matriks akan diperoleh persamaan matriks berikut
d1( k 1) 2 5 x(k+1) = x(k) d ( k 1) 2 3 3
(1.1.7)
untuk k = 0, 1, 2, ... , dengan x(k) = [ x1 (k), x2 (k)] T . Persamaan matriks (1.1.7) di atas dapat juga dituliskan dalam persamaan berikut: x(k+1) = A x(k) d(k + 1)
(1.1.8)
2 5 untuk k = 0, 1, 2, ... , dengan x(k) = [ x1 (k), x2 (k)] T, A = dan d(k + 1) = 3 3
[ d1 (k + 1), d 2 (k + 1)]T . Pada bab-bab selanjutnya akan dibahas bagaimana cara menentukan keberangkatan awal kereta sehingga waktu keberangkatan selanjutnya akan periodik untuk periode waktu tertentu. 1.2 Sistem Produksi Sederhana Diperhatikan suatu sistem produksi sederhana (Schutter, 1996) yang disajikan dalam Gambar 1.2.1 berikut: d1 = 5
u(k)
t1 = 2
t3 = 1 d3 = 3 t5 = 0 d2 = 6
y(k)
t4 = 0
t2 = 0
Gambar 1.2.1 Sistem Produksi Sederhana
Sistem ini terdiri dari 3 unit pemrosesan P1 , P2 , P3 . Bahan baku dimasukkan ke P1 dan P2 , diproses dan dikirimkan ke P3 . Waktu pemrosesan untuk P1 , P2 dan P3
berturut-turut adalah d1 = 5, d 2 = 6 dan d3 = 3 satuan waktu. Diasumsikan
5
bahwa bahan baku memerlukan t1 = 2 satuan waktu untuk dapat masuk dari input ke P1 dan memerlukan t3 = 1 satuan waktu dari produk yang telah diselesaikan di P1 untuk sampai di P3 , sedangkan waktu transportasi yang lain diabaikan. Pada
input sistem dan antara unit pemrosesan terdapat penyangga (buffer), yang berturut-turut disebut penyangga input dan penyangga internal, dengan kapasitas yang cukup besar untuk menjamin tidak ada penyangga yang meluap (overflow). Suatu unit pemrosesan hanya dapat mulai bekerja untuk suatu produk baru jika ia telah menyelesaikan pemrosesan produk sebelumnya. Diasumsikan bahwa setiap unit pemrosesan mulai bekerja segera setelah bahan tersedia. Didefinisikan: i)
u(k+1) : waktu saat bahan baku dimasukkan ke sistem untuk pemrosesan ke-(k+1),
ii)
xi (k) : waktu saat unit pemrosesan ke-i mulai bekerja untuk pemrosesan ke-k,
iii) y(k) : waktu saat produk ke-k yang diselesaikan meninggalkan sistem. Waktu saat P1 mulai bekerja untuk pemrosesan ke-(k+1) dapat ditentukan sebagai berikut. Jika bahan mentah dimasukkan ke sistem untuk pemrosesan ke-(k+1), maka bahan mentah ini tersedia pada input unit pemrosesan P1 pada waktu t = u(k+1) + 2. Akan tetapi P1 hanya dapat mulai bekerja pada sejumlah bahan baku baru segera setelah menyelesaikan pemrosesan sebelumnya, yaitu sejumlah bahan baku untuk pemrosesan ke-k. Karena waktu pemrosesan pada P1 adalah d1 = 5 satuan waktu, maka produk setengah-jadi ke-k akan meninggalkan P1 pada
saat t = x1 (k) + 5. Hal ini dapat dituliskan dengan: x1 (k+1) = max (u(k+1) + 2, x1 (k) + 5) untuk k = 1, 2, 3, ... .
Dengan alasan yang sama untuk P2 , P3 dan waktu saat produk ke-k yang diselesaikan meninggalkan sistem, diperoleh: x2 (k+1) = max (u(k+1) + 0, x2 (k) + 6)
x3 (k+1) = max ( x1 (k+1) + 5 + 1, x2 (k+1) + 6 + 0, x3 (k) + 3)
6
= max (max (u(k+1) + 2, x1 (k) + 5) + 6, max (u(k+1) + 0, x2 (k) + 6) + 6, x3 (k) + 3) = max (u(k+1) + 2 + 6, x1 (k+1) + 5 + 6, u(k+1) + 0 + 6, x2 (k) + 6 + 6,
x3 (k) + 3) = max ( x1 (k) + 11, x2 (k) + 12, x3 (k) + 3, u(k+1) + 8) y(k) = x3 (k) + 3 + 0 untuk k = 1, 2, 3, ... . Jika operasi max dinotasikan dengan , operasi penjumlahan dinotasikan dengan , maka persamaan-persamaan dalam model sistem produksi sederhana di atas dapat dituliskan dalam persamaan-persamaan berikut: x1 (k+1) = 5 x1 (k) 2 u(k+1)
x2 (k+1) = 6 x2 (k) u(k+1)
x3 (k+1) = 11 x1 (k) 12 x2 (k) 3 x3 (k) 8 u(k+1) y(k) = 3 x3 (k) . Dalam hal urutan pengoperasian (jika tanda kurung tidak dituliskan), operasi mempunyai prioritas yang lebih tinggi dari pada operasi . Jika dituliskan dalam persamaan matriks dapat diperoleh persamaan matriks berikut 5 x(k+1) = 6 x(k) 11 12 3
y(k) =
2 0 u(k+1) 8
3 x(k)
(1.2.1)
untuk k = 1, 2, 3, ... , dengan x(k) = [ x1 (k), x2 (k), x3 (k)] T. Hasil di atas dapat juga dituliskan dengan x(k+1) = A x(k) B u(k+1) (1.2.2) y(k) = C x(k)
7
untuk k = 1, 2, 3, ... , dengan x(k) = [ x1 (k), x2 (k), x3 (k)] T, keadaan awal
x(0) = x0 ,
5 2 A = 6 , B = 0 dan C = 3 . Dalam 11 12 8 3
Schutter (1996), sistem (1.2.2) di atas disebut Sistem Kejadian Diskrit (SKD) linear max-plus waktu-invariant atau secara singkat disebut sistem linear maxplus waktu-invariant (SLMI). Pada bab-bab berikutnya akan dibahas input-output dan sifat periodik sisstem produksi sederhana di atas.
1.3 Penjadwalan Jaringan Proyek Dalam Riset Operasi kita sudah mengenal masalah penjadwalan proyek, dengan beberapa metode penyelesaiannya, di antaranya adalah metode CPM (Critical Path Method). Masalah penjadwalan yang biasa dibahas meliputi penentuan saat-mulai paling awal setiap titik pada jaringan, waktu minimal penyelesaian proyek, saat penyelesaian paling lambat setiap titik pada jaringan, waktu mengambang setiap titik pada jaringan dan penentuan lintasan kritis. Suatu proyek mendefinisikan satu kombinasi kegiatan-kegiatan yang saling berkaitan yang harus dilakukan dalam urutan tertentu sebelum keseluruhan tugas dapat diselesaikan. Kegiatan-kegiatan ini saling berkaitan dalam satu urutan kegiatan yang logis dalam arti bahwa beberapa kegiatan tidak dapat dimulai sampai kegiatan-kegiatan lainnya diselesaikan (Taha, 1996). Pemodelan dinamika jaringan proyek dan analisis lintasan kritis diawali dengan menentukan saatmulai paling awal (earliest start time) untuk setiap aktifitas yang berasal dari titik i. Dengan mengadopsi teknik perhitungan maju (forward) seperti pada PERTCPM dapat dilakukan suatu pemodelan jaringan proyek dengan menggunakan operasi max dan plus. Misalkan xie = saat-mulai paling awal yang berasal dari titik i. Diperhatikan jaringan proyek seperti yang diberikan pada Gambar 1.3.1 (Taha, 1996, pp. 81) berikut, di mana bobot busur berarah antara dua titik j dan i yaitu
8
Aij menyatakan waktu aktifitas dalam jaringan. Diasumsikan bahwa aktifitas jaringan dimulai pada titik 1 pada saat waktu sama dengan nol, yaitu x1e = 0. Selanjutnya dengan teknik perhitungan maju PERT-CPM diperoleh
5 2 3
3
6
1 3 2
5
7
2 2
6
3 4
7
2
Gambar 1.3.1 Jaringan Proyek
x2e = 2 + x1e x3e = 3 + x2e
x4e = max(2 + x2e , 3 + x3e ) x5e = max(2 + x3e , 0 + x4e ) x6e = max(3 + x4e , 7 + x5e ) x7e = max(2 + x4e , 5 + x5e , 6 + x6e )
Jika pada persamaan-persamaan di atas operasi max dinotasikan dengan , operasi penjumlahan dinotasikan dengan , diperoleh
x2e = 2 x1e x3e = 3 x2e
x4e = 2 x2e 3 x3e x5e = 2 x3e 0 x4e ) x6e = 3 x4e 7 x5e )
x7e = 2 x4e 5 x5e 6 x6e
9
Jika dituliskan dalam persamaan matriks dapat diperoleh persamaan matriks berikut
xe = A xe be
di mana xe = [ x1e , x2e , ... , xne ]T , be = [0, , ... , ]T dan 2 3 A =
2 3 . 2 0 3 7 2 5 6
1.4 Jaringan Antrian Diperhatikan suatu jaringan antrian seri tertutup (closed tandem) dengan n pelayan-tunggal (Krivulin, 1995). Adapun asumsi-asumsi dasar dalam jaringan ini adalah sebagai berikut: 1. Kapasitas penyangga antrian takhingga. 2. Antrian bekerja dengan prinsip First-In First-Out (FIFO). 3. Perpindahan pelanggan dari suatu antrian ke antrian berikutnya tidak memerlukan waktu. 4. Pelanggan harus melewati antrian dari awal sampai akhir secara berturutan untuk menerima layanan setiap pelayan. Satu siklus layanan jaringan adalah proses dari masuknya pelanggan ke penyangga pelayan ke-1 hingga meninggalkan pelayan ke-n. Setelah penyelesaian layanan pada pelayan ke-n, pelanggan kembali ke antrian pertama untuk suatu siklus baru layanan jaringan. Pada saat awal pengamatan, semua pelayan tidak memberi layanan, di mana penyangga pada pelayan ke-i memuat sebanyak 1 pelanggan untuk setiap i = 1, 2, ..., n. Gambar 1.4.1 berikut (Krivulin, 1996) memberikan keadaan awal jaringan antrian seri tertutup yang dimaksud, dengan pelanggan yang dinyatakan dengan ””. Jaringan antrian seri tertutup dapat dijumpai dalam sistem pabrik perakitan, seperti perakitan mobil maupun barang-barang elektronik. Pelanggan
10
dalam sistem ini adalah palet sedangkan pelayanan adalah mesin perakit. Palet yang dimaksud adalah semacam meja atau tempat di mana komponen-komponen atau barang setengah-jadi ditempatkan dan bergerak mengunjungi mesin-mesin perakit. Mula-mula sebuah palet ke-1 masuk ke penyangga mesin ke-1, kemudian masuk mesin ke-1 dan palet ke-2 masuk ke penyangga mesin ke-1. Di mesin ke-1 ini komponen-komponen diletakkan dan dipersiapkan untuk dirakit di mesin berikutnya. Selanjutnya palet ke-1 masuk ke penyangga mesin ke-2 dan palet ke-2 masuk ke mesin ke-1. Demikian seterusnya untuk n palet yang tersedia, sehingga tercapai keadaan seperti pada Gambar 1.4.1 di bawah, di mana tercapai keadaan awal pengamatan. Setelah perakitan selesai dikerjakan di mesin ke-n, barang hasil rakitan akan meninggalkan jaringan, sementara palet yang membawa akan menuju kembali ke penyangga mesin ke-1, untuk memulai suatu siklus baru layanan jaringan, demikian seterusnya.
1
2
n
Gambar 1.4.1 Jaringan Antrian Seri Tertutup
Misalkan ai (k) = saat kedatangan pelanggan ke-k pada pelayan ke-i,
di (k) = saat keberangkatan pelanggan ke-k dari pelayan ke-i, ti = waktu layanan pada pelayan ke-i. untuk k = 1, 2, ... dan i = 1, 2, ..., n. Selanjutnya dinamika antrian pada pelayan ke- i , seperti yang telah dibahas dalam (Krivulin, 1995), dapat dinyatakan dengan
di (k) = max( ti + ai (k), ti + di (k 1))
(1.4.1)
d n (k 1) jika i 1 ai (k) = d i 1 (k 1) jika i 2 ,...,n
(1.4.2)
Jika operasi max dinotasikan dengan , operasi penjumlahan dinotasikan dengan , maka persamaan (1.4.1) dapat dituliskan sebagai berikut
di (k) = ti ai (k) ti di (k1)
(1.4.3)
11
Misalkan d(k) = [ d1 (k) , d 2 (k), ... , d n (k)]T, a(k) = [ a1 (k) , a2 (k), ... , an (k)]T dan t1 . Persamaan (1.4.3) dan (1.4.2) di atas dapat dituliskan T = t n
menjadi d(k) = T a(k) T d(k 1).
(1.4.4)
a(k) = G d(k1),
(1.4.5)
0 0 . dengan matriks G = 0
Dengan mensubstitusikan persamaan (1.4.5) ke persamaan (1.4.4) dapat diperoleh persamaan d(k) = T G d(k1) T d(k 1) = T (G E) d(k 1) atau d(k) = A d(k 1)
(1.4.6)
t1 t1 t t 2 2 . Persamaan (1.4.6) di atas dengan A = T (G E) = tn 1 tn 1 tn tn merupakan model dinamika jaringan antrian tersebut. Pada bab berikutnya akan dibahas suatu penentuan saat keberangkatan awal tercepat pelanggan agar antar saat keberangkatan pelanggan pada setiap pelayanan dapat berlangsung secara periodik dengan besar periode tertentu. Pemodelan masalah-masalah di atas dengan pendekatan menggunakan operasi max dan plus ini dapat memberikan suatu cara yang lebih padu dan menyatu serta persamaan yang dihasilkan analog dengan hasil-hasil pada teori sistem yang konvensional (Krivulin, 2000).
BAB 2 ALJABAR MAX-PLUS DAN MATRIKS
Dalam bab ini dibahas beberapa konsep-konsep dasar yang akan digunakan untuk membahas bab-bab berikutnya. Pembahasan meliputi aspek struktur aljabar secara umum, sifat-sifat struktur aljabar tersebut, contoh-contoh, dan komputasinya. Secara lebih khususnya akan dibahas aljabar max-plus, matriks atas aljabar max-plus, semimodul atas aljabar max-plus dan kaitan antara matriks atas aljabar max-plus dan teori graf. Hal ini dikarenakan banyak konsep-konsep aljabar max-plus yang karena asal-usul dan penerapannya terkait dengan masalah jaringan dalam teori graf. 2.1 Aljabar Max-Plus Dalam bab sebelumnya telah diberikan beberapa contoh pemodelan dengan semesta pembicaraan himpunan semua bilangan real R, dengan menggunakan operasi maximum yang disingkat dengan max, yang dinotasikan dengan , dan operasi penjumlahan (atau plus) yang dinotasikan dengan . Dalam subbab ini dibahas aljabar max-plus dan sifat-sifatnya Pembahasan diawali dengan meninjau suatu struktur aljabar yang lebih umum. Definisi 2.1.1 Suatu semiring (S, +, ) adalah suatu himpunan tak kosong S yang dilengkapi dengan dua operasi biner + dan , yang memenuhi aksioma berikut: i) ( S, + ) adalah semigrup komutatif dengan elemen netral 0, yaitu a, b, c S : (a + b) + c = a + (b + c) , a+b = b+a, a+ 0 = a. ii) (S, ) adalah semigrup dengan elemen satuan 1, yaitu a, b, c S : (a b) c = a (b c) , a1 = 1a = a,
12
13
iii)
elemen netral 0 merupakan elemen penyerap terhadap operasi , yaitu a S :
a 0 = 0 a = 0.
iv) Operasi distributif terhadap + , yaitu a, b, c S : (a + b) c = (a c) + (b c) , a ( b + c ) = (a b) + (a c) . Contoh 2.1.2 Diberikan R : = R { } dengan R adalah himpunan semua bilangan real dan
: = . Pada R didefinisikan operasi berikut: a, b R ,
a b : = max(a, b) dan a b : = a + b.
Misalkan 2 1 : = max(2, 1) = 2 ; 3 4 : = 3 + 4 = 1. ( R , , ) merupakan semiring dengan elemen netral = dan elemen satuan e = 0, karena untuk setiap a, b, c R berlaku: i) a b = max(a, b) = max(b, a) = b a, (a b) c = max(max(a, b), c) = max(a, b, c) = max(a, max(b, c)) = a (b c), a = max(a, ) = a. ii) (a b) c = (a + b) + c = a + (b + c) = a (b c) , a e = a + 0 = a = 0 + a = e a, iii) a = a + () = = () + a = a . iv) (a b) c = max(a, b) + c = max(a + c, b + c) = (a c) (b c), a (b c) = a + max(b, c) = max(a + b, a + c) = (a b) (a c). Definisi 2.1.3 Suatu semiring (S, +, ) dikatakan komutatif jika operasi bersifat komutatif, yaitu a, b S : a b = b a. Definisi 2.1.4 Suatu semiring (S, +, ) dikatakan idempoten jika operasi + bersifat idempoten, yaitu a S : a + a = a.
14
Dalam Baccelli, et.al.(2001) istilah semiring idempoten disebut dioid. Contoh 2.1.5 Semiring ( R , , ) merupakan semiring komutatif yang sekaligus idempoten, karena untuk setiap a, b R berlaku a b = a + b = b + a = b a dan a a = max(a, a) = a. Definisi 2.1.6 Suatu semiring komutatif (S, +, ) disebut semifield jika setiap elemen tak netralnya mempunyai invers terhadap operasi , yaitu a S \{0} a1 S, a a1 = 1. Contoh 2.1.7 Semiring komutatif ( R , , ) merupakan semifield, karena untuk setiap a R terdapat a sehingga berlaku a (a) = a + (a) = 0. Dari Contoh 2.1.5 dan 2.1.7 di atas terlihat bahwa ( R , , ) merupakan semifield idempoten. Struktur aljabar R max : = ( R , , ) disebut aljabar maxplus, yang selanjutnya cukup dituliskan dengan R max . Elemen-elemen R max akan disebut juga skalar. Dalam hal urutan pengoperasian (jika tanda kurung tidak dituliskan), operasi mempunyai prioritas yang lebih tinggi daripada operasi . Pangkat k N {0} dengan N adalah himpunan semua bilangan asli, dari elemen x R dalam aljabar max-plus dinotasikan dengan x sebagai berikut: Didefinisikan pula
0
k
x : = 0 dan x : = x x 0
k 1
k
didefinisikan
, untuk k = 1, 2, ... .
k
: = 0 dan : = , untuk k = 1, 2, ... . k
Diperhatikan bahwa x = x x x x x = kx, dengan operasi x = k
perkalian pada bilangan real.
k
Pangkat aljabar max-plus mempunyai prioritas
tertinggi dibandingkan operasi dan dalam hal urutan pengoperasian.
15
2.2 Matriks atas Aljabar Max-Plus Operasi dan pada R max di atas dapat diperluas untuk operasi-operasi n matriks dalam R m max seperti dalam definisi berikut.
Definisi 2.2.1 n Diberikan R m max : = { A = ( Aij ) Aij R max , i = 1, 2, ..., m dan j = 1, 2, ..., n }. n i) Diketahui R max , A, B R m max . Didefinisikan
A adalah matriks yang unsur ke-ij-nya: ( A)ij = Aij
untuk i = 1, 2, ..., m dan j = 1, 2, ..., n
dan A B adalah matriks yang unsur ke-ij-nya: (A B)ij = Aij Bij
untuk i = 1, 2, ..., m dan j = 1, 2, ..., n.
p p n ii) Diketahui A R m max , B R max . Didefinisikan
A B adalah matriks yang unsur ke-ij-nya: (A B)ij =
p
Aik Bkj k 1
untuk i = 1, 2, ..., m dan j = 1, 2, ..., n.
Contoh 2.2.2 6 46 40 4 6 4 10 0 40 i) 4 1 = 4 1 4 = 4 1 4 = 5 . 0,5 2 4 0,5 4 2 4 0,5 4 2 4,5 2
1 2 ii) 3
0 5 1 0 2 5 1 7 = 1 3 7 =
max 1, 0 max 2, - 5 max , 1 max - 3, 7 =
1 2 1 7 .
1 1 0 8 iii) 6 0 3 2 2 4
1 0 6 8 2 1 1 0 0 8 4 = 3 6 2 2 1 3 0 2 4
16
max , 6, 6 max 0, 0, 12 = = max , 9, 0 max , 3, 6
6 12 9 6 .
Definisi 2.2.3 n Matriks A, B R m max dikatakan sama jika Aij = Bij untuk setiap i dan j.
Operasi dan untuk matriks di atas mempunyai sifat-sifat berikut: Teorema 2.2.4 Pernyataan-pernyataan berikut berlaku untuk sebarang skalar dan , dan sebarang matriks A , B dan C asalkan operasi yang dimaksud terdefinisi. i)
(A B) C = A (B C)
ii)
AB=BA
iii)
(A B) C = A (B C)
iv)
A (B C) = (A B ) (A C)
v)
(A B) C = (A C ) (A C)
vi)
A=A
vii) ( A) = ( ) A viii) (A B ) = ( A ) B = A ( B) ix)
( ) A = ( A) ( A)
x)
(A B) = ( A) ( B)
xi)
A A = A.
Bukti: Akan dibuktikan untuk iii) dan iv) sedangkan bukti yang lain langsung mengikuti definisi operasi dan sifat-sifat operasi pada R max . p pr rn iii): Diambil sebarang matriks A R m max , B R max , C R max .
Unsur ke-ij matriks (A B) C adalah
matriks A (B C) adalah
r
l 1
p Aik Bkl Clj , unsur ke-ij k 1
r Bkl C lj . A ik k 1 l 1 p
17
r
Karena
l 1
p Aik Bkl Clj = k 1
r
p
Aik Bkl Clj = l 1 k 1
r Bkl C lj maka (A B) C = A (B C). A ik k 1 l 1 p
p p n iv): Diambil sebarang A R m max , B, C R max . Unsur ke-ij matriks A (B C)
p
adalah
Aik ( Bkj C kj ) , unsur ke-ij matriks k 1
(A B) (A C) adalah
p Aik Bkj k 1
p Aik C kj . Karena k 1
p Aik Bkj k 1
p Aik C kj , maka A (B C) = (A B) (A C). k 1
p
Aik ( Bkj C kj ) k 1
=
■
Berikut diperhatikan dua buah matriks khusus.
0 jika i j n Didefinisikan matriks E R n . max dengan ( E)ij : = jika i j n Didefinisikan matriks R m max dengan: ( )ij :=
untuk setiap i dan j .
Contoh 2.2.5 n ( R n max , , ) merupakan semiring idempoten dengan elemen netral adalah
matriks dan elemen satuan adalah matriks E. Matriks E di atas disebut juga matriks identitas max-plus, sedangkan matriks
disebut matriks nol max-plus. ( R
nn max
, , ) bukan semiring komutatif,
0 0 1 0 karena terdapat matriks A = dan B = dengan A B = 1 1 0 1 0 1 = 1 2 , B A =
0 1 0 2 1 = . Jadi A B B A .
18
Pangkat k N {0} dengan N adalah himpunan semua bilangan asli, dari matriks A R nxn max dalam aljabar max-plus didefinisikan dengan: 0
k
A = En dan A = A A
k 1
untuk k = 1, 2, ... .
2
Unsur ke-st matriks A adalah n
( As , i i 1
2
( A ) st =
1
Ai1 , t ) = max ( As , i1 + Ai1 , t ). 1 i1 n
1
3
Unsur ke-st matriks A adalah 3
( A ) st =
n
n
i2 1
i1 1
( As , i2 ( ( Ai2 , i1 Ai1 , t ))) =
n
(
i2 1
n
( As , i i 1
2
Ai2 , i1 Ai1 , t ))
1
= max ( As , i2 + Ai2 , i1 + Ai1 , t ). 1 i1 , i2 n
k
Secara umum, unsur ke-st matriks A adalah n
n
k
( A ) st =
ik 1 1
( As , ik 1 ... ( ( Ai2 , i1 Ai1 , t ))) = i1 1
n
( As , i i 1
k 1
n
...
i2 1
Ai2 , i1 Ai1 , t ))
1
=
max
1 i1 , i2 ,ik 1 n
( As , ik 1 + ... + Ai2 , i1 + Ai1 , t ).
Diperhatikan bahwa untuk sebarang skalar R max dan A R nxn unsur ke-st max k
matriks ( A) adalah k
( ( A) ) st =
max
1 i1 , i2 ,ik 1 n
(( As , ik 1 )+ ... + ( Ai2 , i1 ) +( Ai1 , t )).
= ( )+( k
k
max
1 i1 , i2 ,ik 1 n
( As , ik 1 + ... + Ai2 , i1 + Ai1 , t ))
= ( A )st untuk k = 1, 2, ... . k
Jadi untuk sebarang skalar R max dan A R nxn max berlaku bahwa k
( A) = A untuk k = 1, 2, ... . k
k
(2.1.1)
19
Untuk sebarang A R nxn max didefinisikan trace(A) : =
n
A i 1
.
ii
Contoh 2.2.6 1 3 2 Diberikan A = 2 4 . 0
A
A
2
3
=
1 3 2 1 3 2 2 5 7 A A = 2 4 2 4 = 4 6 . 0 0 2 4
=A A
2
1 3 2 2 5 7 = 2 4 4 6 = 0 2 4
3
Trace(A) =
3 7 9 6 8 . 4 6
Aii = max(1, 2, ) = 2, trace( A ) = 2
i 1
3
dan trace( A ) =
3
A i 1
3 ii
3
A i 1
2 ii
= max(2, 4, 4) = 4
= max(3, 6, 6) = 6.
Untuk memudahkan perhitungan dalam perhitungan matriks, terutama perkalian dan perpangkatan matriks atas aljabar max-plus, berikut diberikan list program MATLAB untuk menghitung dua operasi matriks tersebut. % % % % %
Program Matlab Perkalian Max-plus Matriks A dan B Oleh: M. Andy Rudhito FKIP Universitas Sanata Dharma input: A = matriks max-plus Amxn B = matriks nxp output: Hasil kali max-plus A dan B
function hasilkali = maxkali disp(' ') % Memasukkan matriks yang dikalikan A = input(' Masukkan matriks A(mxn) = disp(' ') B = input(' Masukkan matriks B(nxp) = disp(' ') [m, n]= size(A); [k, r]=size(B); if n == k for i = 1:m for j = 1: r AB(i, j) = -Inf; for p = 1: n
'); ');
20
AB(i, j) = max(AB(i, j) , A(i, p) + B(p, j)); end; end; end; % Menampilkan hasil kali disp(' HASIL PERHITUNGAN :') disp(' ===================') disp(' Matriks A = '),disp(A) disp(' Matriks B = '),disp(B) disp(' Hasil kali max-plus matriks A dan B adalah'),disp(AB) % Peringatan tidak dapat dikalikan else disp(' Ordo tidak sesuai, matriks tidak dapat dikalikan '); end;
Gambar 2.2.1 List Program MATLAB Perkalian Matriks Max-Plus
Berikut diberikan contoh entri matriks dan hasil eksekusi programnya. Contoh 2.2.7 » maxkali Masukkan matriks A(mxn) = [1 0 -2 -Inf 3 4 12 -Inf -1 0; -Inf 2 3 0 -Inf 5 -6 11 20 -7;-3 1 -Inf 1 2 -3 0 0 1 0; 2 7 -1 -2 0 1 1 -Inf 0 4;-Inf 0 -Inf 6 6 7 10 -11 -5 1; -1 0 1 -Inf -Inf 0 0 -Inf 0 7;4 4 -2 -2 -Inf 9 -6 -8 0 0; -Inf -Inf 0 -Inf -Inf -Inf -Inf -Inf -Inf -Inf] Masukkan matriks B(nxp) = [-Inf 0 -Inf 1 -4 0 -Inf; 4 -1 -Inf 2 4 -Inf 0;1 0 -Inf 0 -7 8 10;-Inf 11 -Inf 13 -Inf -Inf 1; -2 1 -Inf 1 6 -2 -3;-Inf -Inf -Inf -Inf -Inf -Inf -1; 0 -1 -Inf 1 -2 2 0;0 0 -Inf 20 16 -2 1;1 0 -Inf -2 2 -Inf 3; -Inf -Inf -Inf -Inf 7 4 1] HASIL PERHITUNGAN : =================== Matriks A = 1 0 -2 -Inf -Inf 2 3 0 -3 1 -Inf 1 2 7 -1 -2 -Inf 0 -Inf 6 -1 0 1 -Inf 4 4 -2 -2 -Inf -Inf 0 -Inf
3 -Inf 2 0 6 -Inf -Inf -Inf
4 5 -3 1 7 0 9 -Inf
12 -6 0 1 10 0 -6 -Inf
Matriks -Inf 0 4 -1 1 0 -Inf 11
-4 4 -7 -Inf
0 -Inf 8 -Inf
-Inf 0 10 1
B = -Inf -Inf -Inf -Inf
1 2 0 13
-Inf 11 0 -Inf -11 -Inf -8 -Inf
-1 20 1 0 -5 0 0 -Inf
0 -7 0 4 1 7 0 -Inf
21
-2 -Inf 0 0 1 -Inf
1 -Inf -1 0 0 -Inf
-Inf -Inf -Inf -Inf -Inf -Inf
1 -Inf 1 20 -2 -Inf
6 -Inf -2 16 2 7
-2 -Inf 2 -2 -Inf 4
-3 -1 0 1 3 1
Hasil kali max-plus matriks A dan B adalah 12 11 -Inf 13 10 14 12 21 20 -Inf 31 27 11 23 5 12 -Inf 20 16 4 4 11 9 -Inf 11 11 8 9 10 17 -Inf 19 12 12 10 4 1 -Inf 2 14 11 11 8 9 -Inf 12 8 6 8 1 0 -Inf 0 -7 8 10
% % % % %
Program Matlab Menghitung PANGKAT MAX-PLUS Matriks Oleh: M. Andy Rudhito FKIP Universitas Sanata Dharma input: A = matriks max-plus Anxn k = pangkat tertinggi output A pangkat max-plus 1 s/d k
function kuadrat = pkmax % Memasukkan matriks dan pangkat tertinggi disp(' ') disp(' PANGKAT MAX-PLUS MATRIKS') disp(' -------------------------') disp(' ') A = input(' Masukkan matriks A = '); disp(' ') k = input(' Hitung sampai pangkat ke- '); disp(' HASIL PERHITUNGAN :') disp(' ===================') disp(' Matriks A = '), disp(A) [m, n]= size(A); if m==n D = A; for r = 1 : k-1 r+1; for i = 1: m for j = 1: n C(i, j) = -Inf; for p = 1: n C(i, j) = max(C(i, j) , A(i, p) + D(p, j)); end; end; end; D = C; % Menampilkan hasil perhitungan disp(' Matriks A pangkat max-plus'), disp(r+1), disp(C) end; else
22
% Peringatan kalau matriksnya tidak bujur sangkar disp(' Matriks A tidak bujur sangkar, pangkat tidak didefinisikan' ) end;
Gambar 2.2.2 List Program MATLAB Perpangkatan Matriks Max-Plus
Berikut diberikan contoh entri matriks dan hasil eksekusi programnya. Contoh 2.2.8 » maxpk PANGKAT MAX-PLUS MATRIKS -----------------------Masukkan matriks A = [1 0 -2 -Inf 3 -Inf -1 0; -Inf 2 3 0 -Inf 5 -6 -7;-3 1 -Inf 1 2 0 1 0; -1 -2 0 1 1 -Inf 0 4; -Inf 0 -Inf 7 10 -11 -5 1;-1 0 1 0 0 -Inf 0 7;4 4 -2 -2 -Inf 9 0 0; -Inf -Inf 0 -Inf -Inf -Inf -Inf -Inf ] Hitung sampai pangkat keHASIL PERHITUNGAN : =================== Matriks A = 1 0 -2 -Inf 3 -Inf 2 3 0 -Inf -3 1 -Inf 1 2 -1 -2 0 1 1 -Inf 0 -Inf 7 10 -1 0 1 0 0 4 4 -2 -2 -Inf -Inf -Inf 0 -Inf -Inf Matriks A pangkat max-plus 2 3 4 5 4 6 4 8 -3
3 5 5 4 10 4 9 1
3 6 4 4 7 7 10 -Inf
10 5 9 8 17 7 9 1
13 5 12 11 20 10 9 2
4
-Inf 5 0 -Inf -11 -Inf 9 -Inf
-1 -6 1 0 -5 0 0 -Inf
0 -7 0 4 1 7 0 -Inf
8 7 10 9 5 9 9 0
0 5 1 1 7 2 9 1
4 12 7 5 11 4 16 0
9 14 10 10 16
10 7 10 9 17
15 14 17 16 21
Matriks A pangkat max-plus 3 9 9 9 8 16
13 9 12 11 20
10 12 11 10 17
20 12 19 18 27
23 15 22 21 30
23
8 13 5
10 13 5
10 16 4
17 16 9
20 19 12
11 18 10
9 11 1
16 16 7
19 16 19 18 26 18 20 10
20 14 19 18 27 17 18 10
24 21 23 22 31 21 25 17
Matriks A pangkat max-plus 4 19 13 18 17 26 16 17 9
23 15 22 21 30 20 19 12
20 15 19 18 27 17 19 11
30 22 29 28 37 27 26 19
33 25 32 31 40 30 29 22
2.3 Semimodul atas Aljabar Max-Plus Bagian ini akan membahas struktur aljabar yang melandasi pembahasan konsep vektor dalam aljabar max-plus. Di samping itu juga akan dibahas konsep urutan dalam vektor di mana di dalamnya dibahas konsep lebih besar dan lebih kecil. Definisi 2.3.1 Diberikan semiring komutatif (S, +, ) dengan elemen netral 0 dan elemen identitas 1. Semimodul M atas S adalah semigrup komutatif (M, + ) bersama operasi perkalian skalar : S M M , yang dituliskan dengan ( , x) x, yang memenuhi aksioma berikut: , S dan x, y M berlaku: i)
(x + y) = x + y,
ii)
( + ) x = x + x,
iii)
( x) = ( ) x,
iv)
1 x = x,
v)
0x=0.
Elemen dalam semimodul disebut vektor. Contoh 2.3.2 Diberikan R nmax := { x = [ x1 , x2 , ... , xn ]T | xi R max , i = 1, 2, ... , n}.
24
Untuk setiap x, y R nmax dan untuk setiap R max didefinisikan operasi dengan x y = [ x1 y1 , x2 y2 , ... , xn yn ]T dan operasi perkalian skalar dengan
x = x = [ x1 , x2 , ... , xn ]T. 1 Perhatikan bahwa R nmax dapat dipandang sebagai R nmax . Dengan memperhatikan
Teorema 2.2.4 i) dan ii) terlihat bahwa ( R nmax , ) merupakan semigrup komutatif dengan elemen netral
= [, , ..., ]T. Kemudian dengan memperhatikan
Teorema 2.2.4 x), ix), dan vii), R nmax merupakan semimodul atas R max . Diberikan vektor-vektor x1 , x 2 , ..., xn di dalam semimodul M dan skalarskalar 1 , 2 , ..., n di dalam semiring komutatif S. Didefinisikan kombinasi linear dari vektor-vektor x1 , x 2 , ..., xn adalah suatu bentuk aljabar 1 x1 +
2 x 2 + ... + n xn . Definisi 2.3.3 (Wohlgemuth, 1990) Relasi “ ” pada himpunan P disebut urutan parsial pada P jika untuk semua x, y, z P berlaku: i) Sifat refleksif, yaitu: x x . ii) Sifat antisimetris, yaitu: jika x y dan y x, maka x = y . iii) Sifat transitif, yaitu: jika x y dan y z, maka x z . Elemen x dan y dikatakan komparabel (comparable) jika x y atau y x . Jika x y akan dituliskan juga dengan y x. Jika x y dan x y akan dituliskan juga dengan x y. Definisi 2.3.4 (Wohlgemuth, 1990) Urutan parsial “ ” pada himpunan P disebut urutan total pada P jika setiap dua elemen dalam P komparabel.
25
Teorema 2.3.5 Jika (S, + ) semigrup komutatif idempoten maka relasi “ ” yang didefinisikan pada S dengan x y x + y = y merupakan urutan parsial pada S. Bukti: Diambil sebarang x, y, z S. i) Karena berlaku sifat idempoten maka x + x = x x x . ii) Jika x y dan y x maka x + y = y dan y + x = x. Karena berlaku sifat komutatif maka x = y. iii) Jika x y dan y z maka x + y = y dan y + z = z. Dari sini karena berlaku sifat asosiatif maka x + z = x + (y + z) = (x + y) + z = y + z = z. Dengan demikian x z.
■
Akibat 2.3.6 Relasi “ m ” yang didefinisikan pada R max dengan x m y x y = y merupakan urutan parsial pada R max . Lebih lanjut relasi ini merupakan urutan total pada R max . Bukti: Karena
( R , ) merupakan semigrup komutatif idempoten, maka
menurut Teorema 2.3.5 relasi “ m ” yang didefinisikan pada R max di atas merupakan urutan parsial pada R max . Selanjutnya diambil x , y R max maka berlaku x y = max (x, y) = x atau x y = max (x, y) = y. Akibat 2.3.7 n Relasi “ m ” yang didefinisikan pada R m max dengan
A
m B
A B = B Aij Bij = Bij Aij m Bij
n untuk setiap i dan j, merupakan urutan parsial pada R m max .
■
26
n Bukti: Dengan menggunakan Teorema 2.2.4 i), ii) dan xi) nampak ( R m max , )
merupakan semigrup komutatif idempoten, sehingga menurut Teorema 2.3.5 n relasi “ m ” yang didefinisikan pada R m max di atas merupakan urutan parsial.
■
Akibat 2.3.8 Relasi “ m ” yang didefinisikan pada R nmax dengan x
m
y x y = y xi m yi
untuk setiap i , merupakan relasi urutan parsial pada R nmax . Bukti: Karena ( R nmax , ) merupakan semigrup komutatif idempoten, maka relasi “ m ” yang didefinisikan pada R nmax merupakan urutan parsial pada R nmax .
■
n Relasi “ m ” yang didefinisikan pada R m max di atas bukan merupakan urutan
0 1 2 1 total, karena terdapat matriks A = dan B = dengan 1 2 1 0 0 1 2 1 2 2 AB= = , sehingga A B B dan A B A. 1 2 1 0 2 2 Demikian juga relasi “ m ” yang didefinisikan pada R nmax di atas bukan merupakan urutan total, karena terdapat vektor x = [1, 2, 3]T dan y = [2, 0, -1]T dengan x y = [1, 2, 3]T [2, 0, -1]T = [2, 2, 3]T . Dengan demikian x y y dan x y x. Teorema 2.3.9 n n Diberikan matriks A R m max . Jika x, y R max dengan x
(A x)
m
(A y).
Bukti: Diambil sebarang x, y R nmax dengan x x y = y A (x y) = A y
m
y, maka
m
y, maka
27
(A x) (A y) = A y (A x)
m
(A y).
■
Hasil pada Teorema 2.3.9 di atas akan digunakan dalam pembahasan penyelesaian sistem persamaan linear max-plus melalui subpenyelesaian terbesarnya.
BAB 3 SISTEM PERSAMAAN LINEAR MAX-PLUS DAN PENERAPANNYA
Dalam bab ini dibahas sistem persamaan linear (SPL) max-plus yang merupakan salah satu alat untuk pemodelan masalah real dengan pendekatan aljabar max-plus. Secara umum ada dua bentuk SPL max-plus, yaitu SPL max-plus inputoutput dan SPL max-plus iteratif. Akan dibahas eksistensi dan ketunggalan penyelesaian SPL max-plus dan juga beberapa contoh penerapannya. 3.1 Sistem Persamaan Linear Input-Output (SPLIO) Max-Plus Sistem persamaan linear max-plus input-output max-plus mempunyai m n n m bentuk umum A x = b di mana A R max , x R max dan b R max . SPL ini tidak
selalu mempunyai penyelesaian. Sebagai contoh: Contoh 3.1.1
2 3 x1 6 Diberikan sistem persamaan linear = . 4 5 x 2 7 Sistem di atas ekuivalen dengan
2 x1 3 x 2 6 4 x1 5 x 2 7
atau
2 ( 2 x1 3 x 2 ) 2 6 4 ( 4 x1 5 x 2 ) 4 7
atau
x1 1 x 2 4 x1 1 x 2 3 max( x1 ,1 x 2 ) 4 atau . max( x1 ,1 x 2 ) 3 Karena 4 3 maka tidak ada x1 , x2 yang memenuhi sistem persamaan di atas. Untuk itu masalah penyelesaian A x = b dapat diperlemah dengan mendefinisikan konsep subpenyelesaian berikut.
28
29
Definisi 3.1.2 m n m n Diberikan A R max dan b R max . Vektor x R max disebut suatu
subpenyelesaian sistem persamaan linear A x = b jika vektor x tersebut memenuhi A x
m
b.
Subpenyelesaian A x = b selalu ada, karena untuk = [, , ... , ]T selalu berlaku:
A=
m
b.
Definisi 3.1.3 Suatu subpenyelesaian xˆ dari sistem A x = b disebut subpenyelesaian terbesar sistem A x = b jika x m xˆ untuk setiap subpenyelesaian x dari sistem A x = b. Sebagai suatu usaha untuk menyelesaikan sistem persamaan ini, berikut dibahas suatu hasil mengenai subpenyelesaian terbesar. Teorema 3.1.4 Diberikan A R max dengan unsur-unsur setiap kolomnya tidak semuanya sama m n
dengan dan b R m . Subpenyelesaian terbesar A x = b ada dan diberikan oleh
xˆ dengan ˆx j = max ( bi + Aij ) i
untuk setiap i = 1, 2, ... , m dan j = 1, 2, ... , n. Bukti: Perhatikan bahwa:
(Ax
m
A11 x1 A12 x 2 A1n x n m b1 A x A x A x b 21 1 22 2 2n n m 2 b) Am1 x1 Am 2 x 2 Amn x n m bm
30
( Aij x j ) m bi , i j ( Aij x j m bi , i , j ) ( Aij + x j bi , i , j ) Karena unsur setiap kolom matriks A tidak semuanya sama dengan , maka untuk setiap j selalu ada i sehingga Aij yang berarti Aij ada. Mengingat untuk setiap a Rmax berlaku a = dan a = a maka koefisien-koefisien Aij = tidak akan berpengaruh pada nilai A x. Sehingga berlaku: ( Aij + x j bi , i , j ) ( Aij + x j bi , i , j dengan Aij ) ( x j bi Aij , i , j dengan Aij ) ( x j min ( bi Aij ), j dengan Aij ) i
( x j max ( bi + Aij ), j ). i
Jadi subpenyelesaian sistem A x = b di atas adalah setiap vektor x yang komponen-komponennya memenuhi x j max ( bi + Aij ), j . i
Jika vektor xˆ = [ xˆ 1 , xˆ 2 , ... , xˆ n ]T didefinisikan dengan ˆx j = max ( bi + Aij ) i
untuk setiap j = 1, 2, ... , n maka diperoleh: ( ˆx j = max ( bi + Aij ), j ) ( ˆx j = min ( bi Aij ), j dengan Aij ) i
i
( ˆx j bi Aij , i , j dengan Aij )
( Aij ˆx j ) m bi , i ( A xˆ j
m
b ).
Jadi vektor xˆ tersebut merupakan subpenyelesaian sistem A x = b. Karena x j max ( bi + Aij ) = ˆx j , j , maka x j ˆx j , j . Akibatnya x m xˆ . i
Jadi vektor xˆ tersebut merupakan subpenyelesaian terbesar sistem A x = b.
■
31
Dengan demikian, suatu cara untuk menyelesaikan sistem persamaan A x = b, pertama-tama dihitung dahulu subpenyelesaian terbesarnya, kemudian diperiksa
subpenyelesaian terbesar itu memenuhi sistem persamaan atau tidak.
Untuk mempermudah penghitungan subpenyelesaian terbesar A x = b, diperhatikan bahwa:
(bi Ai1 ) max ( Ai1 bi ) ˆx1 max i i ˆx max ( b A ) max ( Ai 2 bi ) i i 2 2 = i i xˆ = = (bi Ain ) max ( Ain bi ) ˆx n max i i
A11 ( b1 ) A21 ( b2 ) Am1 ( bm ) A ( b ) A ( b ) A ( b ) 12 1 22 2 m2 m = = AT ( b). A1n ( b1 ) A2 n ( b2 ) Amn ( bm ) Jadi untuk menentukan subpenyelesaian terbesar A x = b, pertama-tama dapat dilakukan dengan menghitung: xˆ = AT ( b). Dalam Teorema 3.1.4 di atas, karena diasumsikan bahwa komponen setiap kolom matriks A tidak semuanya sama dengan , maka subpenyelesaian terbesar
xˆ R n . Contoh 3.1.5 Akan ditentukan penyelesaian terbesar sistem persamaan berikut, dengan terlebih dulu menentukan subpenyelesaian terbesarnya.
1 2 11 3 x1 = 7 . x2 0 10 10
1 3 0 Pertama-tama dihitung: A ( b) = 2 10 T
11 7 = 10 . 0 10
10 Akibatnya subpenyelesaian terbesar sistem persamaan di atas adalah . 0
32
1 2 10 Karena 3 = 0 0 10
11 7 , maka 10
10 0 merupakan penyelesaian sistem di
atas. Contoh 3.1.6 Akan ditentukan penyelesaian terbesar sistem persamaan berikut, dengan terlebih dulu menentukan subpenyelesaian terbesarnya.
2 3 x1 6 4 5 x = 7 . 2
2 4 6 3 Pertama-tama dihitung: AT (b)= = . Akibatnya 3 5 7 2 3 subpenyelesaian terbesar sistem persamaan di atas adalah . 2 2 3 3 5 6 3 Karena = maka bukan merupakan penyelesaian 4 5 2 7 7 2 sistem. Catatan: Jika sistem persamaan linear max-plus A x = b mempunyai subpenyelesaian terbesar yang bukan merupakan penyelesaian, maka sistem persamaan linear max-plus tersebut tidak mempunyai penyelesaian. Hal ini dapat ditunjukkan sebagai berikut. Andaikan x adalah penyelesaian sistem persamaan linear max-plus A x = b, yang berarti (A x )i = bi untuk setiap i = 1, 2, ..., m. Misalkan sistem persamaan linear max-plus A x = b mempunyai subpenyelesaian terbesar xˆ yang bukan merupakan penyelesaian, yang berarti terdapat i {1, 2, ..., m} sehingga (A xˆ )i bi . Karena x juga merupakan subpenyelesaian, maka
x
m
xˆ . Akibatnya menurut Teorema 2.3.9 berlaku (A x )
m
(A xˆ ), yang
berarti (A x )i (A xˆ )i untuk setiap i = 1, 2, ..., m. Hal ini berakibat terdapat i {1, 2, ..., m} sehingga (A x )i (A xˆ )i bi , yang kontradiksi dengan pengandaian di atas.
33
Teorema 3.1.7 (Zimmermann, 2006) Andaikan xˆ adalah subpenyelesaian terbesar sistem A x = b. Vektor x merupakan subpenyelesaian sistem A x = b jika dan hanya jika x
m xˆ .
Bukti: () Jelas menurut definisi subpenyelesaian terbesar. () Andaikan x
m xˆ . Mengingat operasi pada matriks konsisten terhadap
urutan “ m ” dan xˆ adalah subpenyelesaian terbesar sistem A x = b, maka berlaku A x m A x m b. Jadi A x m b yang berarti x merupakan subpenyelesaian sistem A x = b.
■
Teorema 3.1.8 (Zimmermann, 2006) Sistem A x = b mempunyai penyelesaian jika dan hanya jika A xˆ m b , di mana vektor xˆ adalah subpenyelesaian terbesar dari sistem A x = b. Bukti ( ) Andaikan A xˆ
m b . Mengingat xˆ adalah subpenyelesaian terbesar
sistem A x = b, maka berlaku A xˆ dan A xˆ
m b. Mengingat berlaku A xˆ m b
m b, maka A xˆ = b, sehingga xˆ merupakan peyelesaian A x =
b. Jadi A x = b mempunyai penyelesaian. () Andaikan A x = b mempunyai penyelesaian, yaitu vektor y, maka A y = b atau A y m b dan A y m b. Nampak bahwa y merupakan subpenyelesaian sistem A x = b. Mengingat xˆ adalah subpenyelesaian terbesar sistem A x = b, maka berlaku y m xˆ . Mengingat operasi pada matriks konsisten terhadap urutan “ m ”, maka A xˆ m A y m b. Jadi A xˆ m b. ■ Akibat 3.1.9 (Schutter and Boom, 2000) n Diberikan A R m max dengan unsur-unsur setiap kolomnya tidak semuanya sama
dengan , dan b Rm . Jika xˆ adalah subpenyelesaian terbesar sistem persamaan linear max-plus A x = b maka untuk setiap indeks j {1, 2, ... , n} terdapat suatu indeks i(j) {1, 2, ..., m} sedemikian hingga Ai( j ), j xˆ j bi( j ) .
34
Bukti: Karena xˆ adalah subpenyelesaian terbesar sistem A x = b, maka menurut Teorema 3.1.4 ˆx j = min ( bi Aij ) untuk setiap j = 1, 2, ..., n dengan Aij . Hal i
ini berarti juga untuk setiap indeks j {1, 2, ... , n} terdapat suatu indeks i(j) {1, 2, ... , m} sedemikian hingga xˆ j bi( j ) Ai( j ), j atau Ai( j ), j xˆ j bi( j ) . Definisi 3.1.10 Diberikan x = [ x1 , x2 , ..., xn ]T R n . Didefinisikan x
= maks xi untuk i = 1, 2, i
..., n. Diberikan masalah optimisasi yang berkaitan dengan sistem persamaan linear max-plus A x = b berikut: n Diberikan A R m max dengan komponen setiap kolomnya tidak semuanya sama
dengan dan b R m . Akan ditentukan suatu vektor x R n yang meminimalkan b A x . Karena komponen setiap kolom matriks A di atas tidak semuanya sama dengan dan
x R n , maka (A x) R m . Akibatnya b A x merupakan hasil operasi
pengurangan vektor dalam R m . Berikut teorema yang memberikan penyelesaian masalah optimisasi di atas. Teorema 3.1.11 (Schutter and Boom, 2000) n Diberikan A R m max dengan komponen setiap kolomnya tidak semuanya sama
dengan dan b R m . Vektor x # = xˆ
δ dengan xˆ subpenyelesaian terbesar 2
sistem A x= b dan = b A xˆ , merupakan vektor yang meminimalkan
b A x . Selanjutnya b A x #
=
δ . 2
Bukti : Misalkan xˆ subpenyelesaian terbesar sistem A x = b.
35
i) Jika xˆ merupakan penyelesaian sistem A x = b, maka b A xˆ
= maks i
bi ( A xˆ ) i = 0. Akibatnya xˆ meminimalkan b A x . ii) Jika xˆ bukan merupakan penyelesaian sistem A x = b, maka b A xˆ
maks bi ( A xˆ ) i = 0. Karena A xˆ i
m
=
b, maka maks bi ( A xˆ ) i = i
maks bi ( A xˆ ) i . Himpunan indeks i yaitu {1, 2, ..., m}dapat dipartisi menjadi i
tiga himpunan bagian I, J dan K sedemikian hingga:
bi (A xˆ )i = 0
untuk semua i I
bi (A xˆ )i =
untuk semua i J
bi (A xˆ )i = i
untuk semua i K, dengan 0 i 1.
Karena xˆ adalah subpenyelesaian terbesar sistem A x = b maka menurut Akibat 3.1.9 untuk setiap indeks j {1, 2, ... , n} terdapat suatu indeks i(j) {1, 2, ... , m} sedemikian hingga Ai( j ), j xˆ j bi( j ) . Akibatnya I tidak kosong. Karena xˆ bukan merupakan penyelesaian sistem A x = b, maka terdapat suatu indeks i sehingga
maks bi ( A xˆ ) i = . Akibatnya himpunan J juga tidak kosong. Sementara i
himpunan K dapat kosong atau tidak kosong. Menurut Teorema 2.3.9 untuk setiap x yang memenuhi x m xˆ berlaku (A x)
m
(A xˆ ), yang berakibat maks bi ( A xˆ ) i maks bi ( A x) i untuk
setiap x
i
m
i
xˆ . Dengan memperhatikan Teorema 2.2.4 vi) dan viii) diperoleh
bahwa untuk sebarang Rmax berlaku (A xˆ ) = A ( xˆ ). Jika
0, maka xˆ
( xˆ ),
yang berakibat maks bi ( A ( xˆ 0 ))i maks i
i
bi ( A xˆ ) i untuk suatu skalar positip 0 Rmax . Untuk itu didefinisikan x() := xˆ , dengan Rmax, 0. Karena bi (A x() )i = bi (A ( xˆ ) )i = bi ((A xˆ )i ), maka diperoleh
36
bi (A x() )i = i Karena I dan J tidak kosong dan
b A x( )
i
max , 0 2 2
jika i K.
max , 0
yang mempunyai
δ δ δ . Jadi x # = x( ) = xˆ merupakan vektor yang 2 2 2
b A x .
meminimumkan
jika i J
0 i 1 untuk semua i K, maka
= max bi ( A x ( )) i =
nilai minimum untuk =
jika i I
Selanjutnya
diperoleh
b A x#
=
δ = . 2
Kemudian akan ditunjukkan bahwa tidak ada vektor x yang memenuhi
b A x
δ n . Misalkan terdapat vektor ~ x R sedemikian hingga 2 δ b ( A ~x ) . 2
(3.1.1)
ˆ subpenyelesaian ˆ + ). Karena x Didefinisikan = ~x xˆ . Maka A ~ x =A(x terbesar sistem A x = b maka menurut Akibat 3.1.9 untuk setiap j {1, 2, ..., n}, terdapat suatu indeks i(j) sedemikian hingga A xˆ b . Karena ( A ~x ) i( j ), j
= max Ai( j ), j xˆ j j j
j
i( j )
i( j )
Ai( j ), j xˆ j j , maka diperoleh ( A ~x ) i( j )
bi( j ) j . Karena ketaksamaan (3.1.1) maka j
δ 2
(3.1.2)
untuk setiap j {1, 2, ..., n}. Karena xˆ merupakan subpenyelesaian terbesar sistem A x = b, maka terdapat ˆ )i = bi . suatu indeks i {1, 2, ..., m} sehingga bi (A xˆ )i = atau (A x
ˆ 2 Ain x ˆ 1 Ai 2 x ˆ )i = Ai1 x ˆn, Karena (A x ˆ 2 , , Ain x ˆ n ), = max( Ai1 xˆ 1 , Ai 2 x
Aij xˆ j bi , untuk setiap j {1, 2, ..., n}.
maka (3.2.3)
37
Akibatnya (A ~x )i = max Aij xˆ j j max bi j bi + max j . j
j
Karena ketaksamaan (3.1.2), maka bi + max j bi + j
j
δ δ = bi . 2 2
δ Jadi terdapat suatu indeks i {1, 2, ..., m} sedemikian hingga (A ~x )i bi 2 δ atau bi (A ~x )i . Hal ini berakibat bahwa b ( A ~x ) 2 δ bertentangan dengan pemisalan bahwa b ( A ~x ) . 2
δ , yang 2
■
3.2 Penerapan pada Sistem Linear Max-Plus Waktu-Invarian dan Sistem Produksi Sederhana Pada subbab 1.2 telah diintrodusir mengenai model sistem produksi sederhana, seperti pada persamaan (1.2.3). Dari ilustrasi dan contoh-contoh pada Bab 1. Pendahuluan nampak bahwa sistem-sistem yang dibahas merupakan Sistem Kejadian Diskrit (SKD) yang mempunyai waktu aktifitas dan barisan kejadian yang deterministik. Matriks dalam persamaan sistemnya merupakan matriks konstan, yaitu tidak tergantung pada parameter k, sehingga sistemnya merupakan sistem waktu-invariant. Sistem seperti dalam contoh di atas merupakan suatu contoh sistem linear max-plus waktu-invariant seperti yang diberikan dalam definisi berikut. Definisi 3.2.1 (Sistem Linear Max-Plus Waktu-Invariant (SLMI), Schutter, 1996) Sistem Linear Max-Plus Waktu-Invariant adalah SKD yang dapat dinyatakan dengan persamaan berikut: x(k+1) = A x(k) B u(k+1) (3.2.1) y(k) = C x(k) n nm untuk k = 1, 2, 3, ... , dengan kondisi awal x(0) = 𝒙0 , A R n max , B R max , n C R lmax .
38
Vektor x(k) R nmax menyatakan keadaan (state), u(k) R mmax adalah vektor input, dan y(k) R lmax adalah vektor output sistem saat waktu ke-k. SLMI seperti dalam definisi di atas secara singkat akan dituliskan dengan SLMI (A, B, C) dan dituliskan dengan SLMI (A, B, C, 𝒙0 ) jika kondisi awal x(0) = 𝒙0 diberikan. SLMI dengan satu input dan satu output akan disebut SLMI satu input satu output (SISO). Sedangkan SLMI dengan lebih dari satu input dan lebih dari satu output akan disebut SLMI multi input multi output (MIMO). Dalam buku ini, SLMI yang dibahas dibatasi pada SLMI SISO. Secara khusus SLMI SISO mempunyai persamaan berikut: x(k+1) = A x(k) B u(k + 1) (3.2.2) y(k) = C x(k) n n 1n untuk k = 1, 2, 3, ... , kondisi awal x(0) = 𝒙0 , A R n max , B R max , C R max .
Vektor x(k) R nmax menyatakan keadaan, skalar u(k) R max menyatakan input, skalar y(k) R max menyatakan output sistem untuk saat waktu ke-k. Selanjutnya SLMI yang dimaksud adalah SLMI SISO dan kadang-kadang hanya disebut “sistem” apabila konteksnya sudah jelas. Sistem Produksi Sederhana dalam subbab 1.2 merupakan contoh SLMI SISO. Dalam situasi tertentu ada suatu SLMI yang keadaannya tidak dipengaruhi kedatangan input, yang disebut SLMI autonomous, seperti diberikan dalam definisi berikut. Definisi 3.2.2 (SLMI Autonomous) SLMI autonomous adalah SLMI yang mempunyai persamaan berikut: x(k+1) = A x(k) (3.2.3) y(k) = C x(k) untuk k = 1, 2, 3, ... , dengan kondisi awal x(0) = 𝒙0 n C R 1max .
, A R nmaxn , B R nmax ,
39
Secara singkat SLMI autonomous seperti dalam definisi di atas dituliskan dengan SLMI (A, C, 𝒙0 ) dengan 𝒙0 . Interpertasi SLMI autonomous dalam sistem produksi sederhana adalah bahwa keadaan awal sistem, buffer input dan beberapa buffer internal tidak kosong (𝒙0 ), kemudian bahan baku dimasukkan pada sistem dengan laju tertentu sedemikan hingga buffer input tidak pernah kosong. Jadi mesin-mesin sudah bekerja pada kondisi awal, dan untuk berikutnya tidak perlu menunggu kedatangan input, karena input sudah selalu tersedia. Selanjutnya dibahas analisis dan beberapa masalah input-output SLMI. Jika kondisi awal dan suatu barisan input diberikan untuk suatu SLMI (A, B, C, 𝒙0 ), maka secara rekursif dapat ditentukan suatu barisan vektor keadaan sistem dan barisan output sistem. Contoh 3.2.3 Diperhatikan sistem produksi sederhana dalam subbab 1.2. Misalkan kondisi awal sistem x(0) = [0, 1, ]T , yang berarti unit pemrosesan P1 dan P2 berturut-turut memulai aktifitasnya saat waktu 0 dan 1 sementara unit pemrosesan P3 masih kosong dan harus menunggu datangnya input dari P1 dan P2 . Bahan mentah dimasukkan sistem saat waktu 0, 9, 12, 24 dan seterusnya, yang berarti diberikan barisan input u(1) = 0, u(2) = 9, u(3) = 12, u(4) = 24, dan seterusnya, dengan u(k) u(k+1) untuk setiap k = 1, 2, 3, ... . Secara rekursif dapat ditentukan barisan vektor keadaan berikut 5 0 2 x(1) = A x(0) B u(1) = 6 1 0 0 = 11 12 3 8 10 x(2) = A x(1) B u(2) = 13 19
11 11 9 = 13 , 17 19
16 x(3) = A x(2) B u(3) = 19 25
14 16 12 = 19 , 20 25
5 7 13
2 5 0 = 7 8 13
40
21 x(4) = A x(3) B u(4) = 25 31
26 26 24 = 25 , dan seterusnya . 32 32
Kemudian diperoleh barisan output sistem sebagai berikut: y(1) = 16, y(2) = 22, y(3) = 28, y(4) = 35, dan seterusnya, yang berarti produk akan meninggalkan sistem saat waktu 16, 22, 28, 35 dan seterusnya.. Untuk SLMI autonomous (A, C, 𝒙0 ) dengan 𝒙0 , jika kondisi awal diberikan, maka secara rekursif juga dapat ditentukan barisan keadaan sistem dan barisan output sistem yang bersesuaian dengan kondisi awal tersebut. Secara umum sifat input-output SLMI (A, B, C, 𝒙0 ) diberikan dalam teorema berikut. Teorema 3.2.5 (Input-Output SLMI (A, B, C, 𝒙0 )) Diberikan suatu bilangan bulat positip p. Jika vektor output y = [y(1), y(2), ... , y(p)]T dan vektor input u = [u(1), u(2), ... , u(p)]T pada SLMI (A, B, C, x0 ) , maka y = K 𝒙0 H u dengan CB CA 2 C A CB dan H = C A B K= p p 1 p 2 B C A B C A C A
. C B
Bukti: Jika diberikan kondisi awal x(0) = 𝒙0 dan barisan input u ( k )k 0 , dengan induksi matematik akan dibuktikan berlaku k
x(k) = ( A x(0) ) (
k
( i 1
A
k i
B u(i) ) untuk k = 1, 2, 3, ... . (3.2.4) 0
Diperhatikan bahwa x(1) = A x(0) B u(1) = A x(0) A B u(1) 1
= ( A x(0) ) (
1
( i 1
A
1i
B u(i) ).
41
Jadi (3.2.4) benar untuk k = 1. n
Misalkan benar untuk k = n : x(n) = ( A x(0) ) (
n
( i 1
A
n i
B u(i) ),
maka x(n +1) = A x(n) B u(n +1) n
( i 1
n
= A (( A x(0) ) ( = (( A
n 1
= (( A
n 1
x(0) ) (
x(0) ) (
A
n
( A i 1 n 1
( A i 1
n i
( n 1) i
( n 1) i
B u(i) ) ) B u(n +1)
B u(i) ) ) B u(n +1) B u(i) ) ) B u(n +1).
Jadi (3.2.4) benar untuk k = n +1. Akibatnya diperoleh k
y(k) = (C A x(0)) (
k
C i 1
A
k i
B u(i) )
(3.2.5)
untuk k = 1, 2, 3, ... . Diberikan suatu bilangan bulat positip p. Jika didefinisikan y = [y(1), y(2), ... , y(p)]T dan u = [u(1), u(2), ... , y(p)]T maka dari persamaan (3.2.2) diperoleh: y(1) = C A x(0) C B u(1) 2
y(2) = C A x(0) C A B u(1) C B u(2)
p
y(p) = C A x(0) C A
p 1
B u(1) C A
. . . C B u(p). atau dalam persamaan matriks dapat dituliskan sebagai y (1) C A y (2) C A 2 = x(0) p y ( p ) C A
p 2
B u(2)
42
CB C A B CB p 1 p 2 B CA B C A
u (1) u (2) C B u ( p )
y = K x(0) H u
atau
(3.2.6)
dengan CB CA C A 2 C A B CB dan H = K= p p 1 p 2 B C A B C A C A
. C B
■
Dalam sistem produksi, Teorema 3.2.5 berarti bahwa jika diketahui kondisi awal sistem dan barisan waktu saat bahan mentah dimasukkan ke sistem, maka dapat ditentukan barisan waktu saat produk selesai diproses dan meninggalkan sistem. Contoh 3.2.6 Diperhatikan sistem produksi sederhana dalam subbab 1.2. Didefinisikan y = [y(1), y(2), y(3), y(4)]T. Jika diberikan x(0) = [0, 1, ]T dan u = [0, 9, 12, 24 ]T, maka diperoleh y = K x(0) H u dengan 14 19 K= 24 29
6 21 9 dan H = 27 12 33 15
15
11 16 11 . 21 16 11 27 21 16 11
Diperhatikan bahwa 16 11 16 22 20 22 y = K x(0) H u = = . 28 25 28 33 35 35
Hal ini berarti bahwa jika kondisi awal x(0) = [0, 1, ]T dan bahan baku dimasukkan ke dalam sistem pada saat waktu u(1) = 0, u(2) = 9, u(3) = 12, u(4) = 15, maka
43
produk selesai dan akan meninggalkan sistem pada saat waktu y(1) = 16, y(2) = 22, y(3) = 28, y(4) = 34. Hasil pada contoh ini sesuai dengan Contoh 3.2.3 di atas. Secara khusus untuk SLMI (A, B, C, ) diperoleh sifat input-otputnya dalam akibat berikut. Akibat 3.2.7 (Input-Output SLMI (A, B, C, )) Diberikan suatu bilangan bulat positip p. Jika vektor output y = [y(1), y(2), ... , y(p)]T dan vektor input u = [u(1), u(2), ... , u(p)]T pada SLMI (A, B, C, ) , maka y= Hu dengan CB C A B CB H = p 1 p 2 B CA B C A
. C B
Bukti: Seperti bukti Teorema 3.2.3, dengan mengambil 𝒙0 = .
■
Dalam sistem produksi, SLMI (A, B, C, ) berarti bahwa keadaan awal sistem, semua penyangga dalam keadaan kosong dan tidak ada unit pemrosesan yang memuat bahan mentah atau produk setengah-jadi. Contoh 3.2.8 Diperhatikan sistem produksi sederhana dalam subbab 1.2. Didefinisikan y = [y(1), y(2), y(3), y(4)]T. Jika diberikan x(0) = , dan u = [0, 9, 12, 15 ]T,
diperoleh y = H u dengan
11 16 11 . H= 21 16 11 27 21 16 11
maka
44
11 0 16 11 9 Diperhatikan bahwa y = H u = = 21 16 11 12 27 21 16 11 15
11 20 . 25 30
Hal ini berarti bahwa jika keadaan awal sistem semua penyangga dalam keadaan kosong dan tidak ada unit pemrosesan yang memuat bahan mentah atau produk setengah-jadi dan bahan baku dimasukkan ke dalam sistem pada saat waktu u(1) = 0, u(2) = 9, u(3) = 12, u(4) = 15, maka produk selesai dan akan meninggalkan sistem pada saat waktu y(1) = 11, y(2) = 20, y(3) = 25, y(4) = 30. Teorema 3.2.9 (Input-Output SLMI Autonomous) Diberikan suatu bilangan bulat positip p. Jika vektor output y = [y(1), y(2), ... , y(p)]T pada SLMI Autonomous (A, C, 𝒙0 ) dengan 𝒙0 , maka y = K x(0) dengan CA C A 2 . K = p C A
Bukti: Dengan kondisi awal x(0) = 𝒙0
, dengan induksi matematik akan
k
dibuktikan bahwa x(k) = A x(0), untuk k = 1, 2, 3, ... .
(3.2.7)
1
Diperhatikan bahwa x(1) = A x(0) = A x(0). Jadi (3.2.4) benar untuk k = 1. n
Misalkan (3.2.4) benar untuk k = n yaitu x(n) = A x(0), maka n
x(n + 1) = A x(n) = A ( A x(0)) = A
n 1
x(0). Jadi (3.2.4) benar
untuk k = n + 1. Akibatnya diperoleh k
y(k) = C A x(0),
untuk k = 1, 2, 3, ... , sehingga
45
y (1) C A y (2) C A 2 = x(0) untuk suatu bilangan bulat positip p. p y ( p ) C A
■
Diperhatikan dua barisan input u1 = u1 (k )k 0 dan u2 = u 2 (k )k 0 . Misalkan
y1 = y1 (k )k 1 adalah barisan output yang bersesuaian dengan barisan
input u1 (dengan kondisi awal x1,0 ) dan y2 = y 2 ( k )k 1 adalah barisan output yang bersesuaian dengan barisan input u2 (dengan kondisi awal x2,0 ) serta , R max . Dengan menggunakan persamaan (3.2.3) dan sifat-sifat pada Teorema 2.2.4, maka dengan barisan input u1 u2 = u1 (k ) u 2 (k )k 0 (dengan kondisi awal x0 = x1,0 x2,0 ) untuk SLMI (A, B, C, x0 )) diperoleh K ( x1,0 x2,0 ) H ( u1 u2 ) = (K x1,0 ) (K x2,0 ) (H u1 ) (H u2 ) = (K x1,0 H u1 ) (K x2,0 H u2 ) = (K x1,0 H u1 ) (K x2,0 H u2 ) = y1 y2 . Jadi jika barisan input u1 dan u2 berturut-turut akan memberikan barisan output y1 dan y2 , maka barisan input u1 u2 akan memberikan barisan output
y1 y2 . Hal ini merupakan suatu alasan bahwa sistem (3.2.1) disebut sistem linear max-plus. Berikut dibahas masalah input paling lambat pada SLMI (A, B, C, x0 ). Masalah input paling lambat pada SLMI (A, B, C, x0 ) adalah sebagai berikut: Diberikan
suatu bilangan bulat positip p. Diketahui vektor output
y = [y(1), y(2), ... , y(p)]T. Misalkan vektor u = [u(1), u(2), ... , u(p)]T adalah vektor input. Permasalahannya adalah menentukan vektor input u terbesar
46
(waktu paling lambat) sehingga memenuhi K x0 H u
m
y, dengan
K dan H seperti dalam Teorema 3.2.9. Dalam sistem produksi, masalah ini mempunyai interpretasi sebagai berikut. Misalkan diketahui vektor y adalah vektor waktu paling lambat agar produk harus meninggalkan sistem. Permasalahannya adalah menentukan vektor u yaitu vektor waktu paling lambat saat bahan baku harus dimasukkan ke dalam sistem. Terlebih dahulu diperhatikan untuk SLMI (A, B, C,
). Penyelesaian
masalah input paling lambat pada SLMI (A, B, C, ) dengan C B diberikan dalam teorema berikut. Teorema 3.2.10 Penyelesaian masalah input paling lambat pada SLMI (A, B, C, ˆ = [uˆ (1), uˆ (2), , uˆ ( p)]T dengan C B diberikan oleh u
) dengan uˆ (k ) =
max ( y(i) H i , k ) , untuk k = 1, 2, ..., p. 1i p
Bukti: Karena K = , maka K H u = H u . Akibatnya masalah input paling lambat pada SLMI (A, B, C, ) menjadi masalah menentukan vektor input u terbesar (waktu paling lambat) yang memenuhi H u
m
y. Masalah ini
merupakan masalah menentukan subpenyelesaian terbesar sistem persamaan linear max-plus H u = y. Karena C B , maka komponen setiap kolom matriks H tidak semuanya sama dengan . Menurut Teorema 3.1.4 subpenyelesaian terbesar ˆ = sistem persamaan linear max-plus H u = y diberikan oleh vektor u
[uˆ (1), uˆ (2), , uˆ ( p)]T dengan uˆ (k ) = max ( y(i) H i , k ) , k = 1, 2, ...., p. 1i p
■
Contoh 3.2.11 Diperhatikan sistem produksi sederhana dalam subbab 1.2 Misalkan diinginkan penyelesaian produk sebelum saat y(1) = 17, y(2) = 19, y(3) = 24, y(4) = 27, dengan
47
waktu pemasukkan bahan baku ke dalam sistem yang selambat mungkin. Misalkan y = [y(1), y(2), y(3), y(4)]T dan u = [u(1), u(2), u(3), u(4)]T. Masalah ini diselesaikan dengan cara menentukan subpenyelesaian terbesar sistem persamaan linear maxplus 11 u(1) 16 11 u( 2) = H u = y, yaitu 21 16 11 u( 3) 27 21 16 11 u( 4)
17 19 . 25 27
Terlebih dulu diperhatikan bahwa 11 16 21 27 17 11 16 21 19 = ˆ = H T ( y) = u 11 16 24 11 27
0 6 . 11 16
Jadi subpenyelesaian terbesar sistem persamaan linear max-plus H u = y di atas
ˆ = [0, 6, 11, 16]T. Hal ini berarti bahwa bahan baku harus adalah vektor u dimasukkan ke sistem pada saat waktu uˆ (1) = 0, uˆ (2) = 6, uˆ (3) = 11, uˆ (4) = 16.
ˆ ini, diperoleh waktu output sistem adalah ˆy = H u ˆ = Dengan waktu input u [11, 17, 22, 27]T yaitu ˆy (1) = 11, ˆy (2) = 17, ˆy (3) = 22, ˆy (4) = 27. Pembahasan
penyelesaian
masalah
input
paling
lambat
pada
SLMI (A, B, C, ) di atas dapat sedikit diperluas untuk SLMI (A, B, C, x0 ) dengan x0 , seperti diberikan dalam teorema berikut.
Teorema 3.2.12 Diberikan SLMI (A, B, C, x0 ) dengan C B . Jika K x0
m
y , maka
penyelesaian masalah input paling lambat pada SLMI (A, B, C, x0 ) diberikan oleh ˆ = [uˆ (1), uˆ (2), , uˆ ( p)]T dengan uˆ (k ) = max ( y(i) H i , k ) , k = 1, 2, ..., p. u 1i p
Bukti: Karena K x0 m y, maka K x0 H u = y H u = y. Selanjutnya bukti seperti pada bukti Teorema 3.2.10 di atas.
■
48
Berikut dibahas masalah minimisasi simpangan maksimum output pada SLMI (A, B, C, x0 ). Masalah minimisasi simpangan maksimum output pada SLMI (A, B, C, x0 ) adalah sebagai berikut. Diberikan
suatu bilangan bulat positip p. Diketahui
vektor output
y = [y(1), y(2), ... , y(p)]T. Misalkan vektor u = [u(1), u(2), ... , u(p)]T adalah vektor input. Permasalahannya adalah menentukan vektor input u sehingga
max ( y ( K x 0 H u)) i minimal dengan K dan H seperti dalam Teorema i
3.2.5. Interpretasi masalah ini dalam sistem produksi adalah sebagai berikut. Misalkan
dimiliki bahan-bahan mentah yang tidak tahan lama. Kemudian
diinginkan meminimalkan simpangan maksimal antara waktu penyelesaian yang diinginkan dengan waktu penyelesaian yang sesungguhnya. Terlebih dahulu diperhatikan untuk SLMI (A, B, C,
). Penyelesaian
masalah minimisasi simpangan maksimum output pada SLMI (A, B, C, ) dengan C B diberikan dalam teorema berikut. Teorema 3.2.13 Penyelesaian
masalah
minimisasi
simpangan
maksimum
output
pada
δ ~ = u ˆ , dengan SLMI(A, B, C, ) dengan C B diberikan oleh vektor u 2 ˆ )i . ˆ subpenyelesaian terbesar sistem H u = y dan = max ( y H u u i
Bukti: Karena K =
, maka K H u = H u. Akibatnya masalah
minimisasi simpangan maksimum output ini menjadi menentukan vektor input u sedemikian hingga max ( y H u) i minimal. Masalah ini merupakan masalah i
optimisasi yang berkaitan dengan sistem persamaan linear max-plus H u = y, seperti pada pembahasan subbab 3.1 di atas. Karena C B , maka komponen setiap kolom matriks H tidak semuanya sama dengan .. Menurut Teorema 3.1.11
49
δ ~ untuk masalah di atas diberikan oleh u ~ = u ˆ , dengan suatu penyelesaian u 2
= max ( y H uˆ ) i
ˆ merupakan subpenyelesaian terbesar sistem dan u
i
H u = y.
■
Contoh 3.2.14 Diperhatikan sistem produksi sederhana dalam subbab 1.2. Misalkan diinginkan penyelesaian produk saat y(1) = 17, y(2) = 19, y(3) = 24, y(4) = 27 dengan meminimalkan simpangan maksimum antara waktu yang diberikan dengan waktu sesungguhnya. Misalkan y = [y(1), y(2), y(3), y(4)]T dan u = [u(1), u(2), u(3), u(4)]T
ˆ = [0, 6, 11, 16]T dengan ˆy = H u ˆ = Dari Contoh 3.2.11 diperoleh bahwa u [11, 17, 22, 27]T . Diperhatikan bahwa simpangan terbesar antara waktu output y yang diberikan dengan waktu output sesungguhnya ˆy adalah
= y ˆy
= max ( y i H uˆ ) i = max(6, 2, 2, 0) = 6. 1i 4
Kemudian waktu input yang meminimalkan simpangan maksimum antara waktu output yang diinginkan dengan waktu output sesungguhnya ˆy adalah
δ ~ ˆ 3 = [0, 6, 11, 16]T 3 = [3, 9, 14, 19]T. = u u = uˆ 2 Untuk wakatu input ~ u ini diperoleh waktu output berikut: ~y = H ~ u = [14, 20, 25, 30]T. Simpangan terbesar antara waktu penyelesaian (waktu output) yang diinginkan dan waktu penyelesaian sesungguhnya ( ~y ) adalah
max ( y i H ~u ) i = max (3, 1, 1, 3) = 3 = i
6 δ = . 2 2
Pembahasan penyelesaian masalah minimisasi simpangan maksimum output pada SLMI (A, B, C,
) di atas juga dapat sedikit diperluas untuk
SLMI(A, B, C, x0 ) dengan x0 , seperti diberikan dalam teorema berikut.
50
Teorema 3.2.15 Diberikan SLMI (A, B, C, x0 ) dengan C B . Jika K x0
m
y maka
penyelesaian masalah minimisasi simpangan output pada SLMI (A, B, C, x0 ) ~ = u ˆ , dengan u ˆ merupakan subpenyelesaian terbesar diberikan oleh u 2
sistem H u = y dan = max ( y H uˆ ) i . i
Bukti: Karena K x0
m
y, maka K x0 H u = y H u = y. Selanjutnya
bukti seperti pada bukti Teorema 3.2.13 di atas.
■
Untuk memudahkan perhitungan dalam perhitungan dalam sistem di atas, berikut diberikan list program MATLAB untuk perhitungan masalah-masalah di atas. % Program Matlab Menghitung INPUT-OUTPUT Sistem Linear Max-Plus Waktu-Invariant % Oleh: M. Andy Rudhito FKIP Universitas Sanata Dharma % input: A = matriks max-plus Anxn % B = matriks nx1 % C = matriks 1xn % x0 = kondisi awal % u = barisan input % output: x(k) = barisan keadaan sistem % y(k) = barisan output sistem function io_SLMI = maxio % Memasukkan input disp(' ') disp(' INPUT-OUTPUT SLMI(A, B, C, x0) ') disp(' --------------------------------') disp(' ') A = input(' Masukkan matriks A(nxn) = '); disp(' ') B = input(' Masukkan matriks B(nx1) = '); disp(' ') C = input(' Masukkan matriks C(1xn) = '); disp(' ') x0 = input(' Masukkan kondisi awal x0(nx1) = '); disp(' ') u = input(' Masukkan barisan input sp kej ke-k u(kx1) = disp(' ') q = length(u); [a1, a2] = size(A); L = zeros(a1,q);
');
51
M = zeros(1,q); L(:,1)= x0; % Menghitung x(1) = Ax(0) + Bu(1) [x01, x02] = size(x0); for i = 1 : a1 for j = 1 : x02 Ax0(i, j) = -Inf; for p = 1: a2 Ax0(i, j) = max(Ax0(i, j) , A(i, p) + x0(p, j)); end; end; end; x = max(Ax0, B+u(1)); % Menghitung y(1) = Cx(1) [c1, c2] = size(C); [x1, x2] = size(x); for i = 1 : c1 for j = 1 : x2 Cx(i, j) = -Inf; for p = 1: c2 Cx(i, j) = max(Cx(i, j) , C(i, p) + x(p, j)); end; end; end; L(:,2)= x; M(1,1)= Cx; % Menghitung x(k+1) = Ax(k) + Bu(k+1) dan Menghitung y(k) = Cx(k) utk k=1,2,...,p % Menghitung x(k+1) = Ax(k) + Bu(k+1) [a1, a2] = size(A); [x1, x2] = size(x); for r = 1 : q-1; for i = 1 : a1 for j = 1 : x2 Ax(i, j) = -Inf; for p = 1: a2 Ax(i, j) = max(Ax(i, j) , A(i, p) + x(p, j)); end; end; end; x = max(Ax, B+u(r+1)); % Menghitung y(k) = Cx(k) [c1, c2] = size(C); [x1, x2] = size(x); for i = 1 : c1 for j = 1 : x2 Cx(i, j) = -Inf; for p = 1: c2 Cx(i, j) = max(Cx(i, j) , C(i, p) + x(p, j)); end; end; end;
52
L(:,r+2)= x; M(1,r+1)= Cx; end; % Menampilkan hasil perhitungan disp(' HASIL PERHITUNGAN :') disp(' ===================') disp(' Matriks A = '),disp(A) disp(' Matriks B = '),disp(B) disp(' Matriks C = '),disp(C) disp(' Kondisi awal x0 = '),disp(x0) disp(' Barisan input u = '),disp(u') disp(' Barisan vektor keadaan sistem x(k) utk k = 0,1, 2, ... : '), disp(L) disp(' Barisan output sistem y(k) utk k = 1, 2, ... : '), disp(M)
Gambar 3.2.1 List Program MATLAB Input-Output SLMI % Program Matlab Menghitung INPUT-OUTPUT SLMI(A, C, x0) AUTONOMOUS % Oleh: M. Andy Rudhito FKIP Universitas Sanata Dharma % input: A = matriks max-plus Anxn % C = matriks max-plus C1xn % x0 = kondisi awal % k = hitung sampai k % Output: Barisan keadaan sampai kejadian ke-k % Barisan output sistem sampai kejadian ke-k function io_SLMI_autonomous = maxioauto % Memasukkan input program disp(' ') disp(' INPUT-OUTPUT SLMI (A, C, x0) AUTONOMOUS') disp(' -----------------------------------------') disp(' ') A = input(' Masukkan matriks A(nxn) = '); disp(' ') C = input(' Masukkan matriks C(1xn) = '); disp(' ') x0 = input(' Masukkan kondisi awal x0(nx1) = '); disp(' ') q = input(' Hitung sampai kejadian ke = '); disp(' ') [a1, a2] = size(A); L = zeros(a1,q); L(:,1)= x0; % Menghitung x(k+1) = Ax(k) x1=x0; [x01, x02] = size(x0); for r = 1 : q; for i = 1 : a1 for j = 1 : x02 Ax0(i, j) = -Inf; for p = 1: a2
53
Ax0(i, j) = max(Ax0(i, j) , A(i, p) + x1(p, j)); end; end; end; L(:,r+1)= Ax0; x1=Ax0; end; % Menghitung output y = C*x(k) [c1, c2]= size(C); [l1, l2]=size(L); for i = 1:c1 for j = 1: l2 y(i, j) = -Inf; for p = 1: c2 y(i, j) = max(y(i, j) , C(i, p) + L(p, j)); end; end; end; % Menampilkan output program disp(' HASIL PERHITUNGAN :') disp(' ===================') disp(' Matriks A = '),disp(A) disp(' Matriks C = '),disp(C) disp(' Kondisi awal x0 = '),disp(x0) disp(' Barisan vektor keadaan sistem utk k = 0, 1, 2, ... : '), disp(L) disp(' Barisan output sistem utk k = 1, 2, ... : '), disp(y)
Gambar 3.2.2 List Program MATLAB Input-Output SLMI Autonomous % Program Matlab Menghitung BARISAN KEADAAN x(k) SLMI AUTONOMOUS tanpa output % Oleh: M. Andy Rudhito FKIP Universitas Sanata Dharma % input: A = matriks max-plus Anxn % x0 = kondisi awal % k = hitung sampai k % Output: Barisan keadaan sampai kejadian ke-k function keadaan_SLMI_autonomous = maxauto % Memasukkan input program disp(' ') disp(' BARISAN KEADAAN x(k) SLMI AUTONOMOUS tanpa output') disp(' -------------------------------------------------') disp(' ') A = input(' Masukkan matriks A(nxn) = '); disp(' ') x0 = input(' Masukkan kondisi awal x0(nx1) = '); disp(' ') q = input(' Hitung sampai kejadian ke = '); disp(' ') [a1, a2] = size(A); L = zeros(a1,q);
54
L(:,1)= x0; % Menghitung x(k+1) = Ax(k) x1=x0; [x01, x02] = size(x0); for r = 1 : q; for i = 1 : a1 for j = 1 : x02 Ax0(i, j) = -Inf; for p = 1: a2 Ax0(i, j) = max(Ax0(i, j) , A(i, p) + x1(p, j)); end; end; end; L(:,r+1)= Ax0; x1=Ax0; end; % Menampilkan output program disp(' HASIL PERHITUNGAN :') disp(' ===================') disp(' Matriks A = '),disp(A) disp(' Kondisi awal x0 = '),disp(x0) disp(' Barisan vektor keadaan sistem utk k= 0, 1, 2, ... : '), disp(L)
Gambar 3.2.3 List Program MATLAB Input-Output SLMIA Tanpa Output % Program Matlab Menghitung OPTIMISASI INPUT-OUTPUT Sistem Linear Max-Plus Waktu-Invariant % Oleh: M. Andy Rudhito FKIP Universitas Sanata Dharma % input: A = matriks max-plus Anxn % B = matriks nx1 % C = matriks 1xn % x0 = kondisi awal % y = barisan output % output:u_topi = barisan input paling lambat % y_topi = barisan outpout untuk u_topi % u_tilde = barisan input minimum simpangan % y_tilde = barisan output untuk u_tilde function opt_input_output = optio % Memasukkan input disp(' ') disp(' OPTIMISASI INPUT-OUTPUT Sistem Linear Max-Plus Waktu-Invariant') disp(' ---------------------------------------------------') disp(' ') A = input(' Masukkan matriks A = '); disp(' ') B = input(' Masukkan matriks B = '); disp(' ') C = input(' Masukkan matriks C = '); disp(' ')
55
x0 = input(' disp(' y = input(' '); disp('
Masukkan kondisi awal x0 = '); ') Masukkan barisan output (dalam vektor kolom) y = ')
q = length(y); % Menghitung C*B = CB [c1, c2] = size(C); [b1, b2] = size(B); for i = 1 : c1 for j = 1 : b2 CB(i, j) = -Inf; for p = 1: c2 CB(i, j) = max(CB(i, j) , C(i, p) + B(p, j)); end; end; end; % Menghitung C*A = CA [c1, c2] = size(C); [a1, a2] = size(A); for i = 1:c1 for j = 1: a2 CA(i, j) = -Inf; for p = 1: c2 CA(i, j) = max(CA(i, j) , C(i, p) + A(p, j)); end; end; end; L = zeros(q,a2); L(1,:)= CA; % Menghitung (C*A)*B [ca1, ca2] = size(CA); [b1, b2] = size(B); for i = 1:ca1 for j = 1: b2 CAB(i, j) = -Inf; for p = 1: ca2 CAB(i, j) = max(CAB(i, j) , CA(i, p) + B(p, j)); end; end; end; % Menghitung A^k = Ak [a1, a2]= size(A); D = A; for r = 1 : q-1 r+1; for i = 1 : a1 for j = 1 : a2 Ak(i, j) = -Inf; for p = 1: a2
56
Ak(i, j) = max(Ak(i, j) , A(i, p) + D(p, j)); end; end; end; % Menghitung C*A^k = CAk [c1, c2] = size(C); [ak1, ak2] = size(Ak); for i = 1 : c1 for j = 1: ak2 CAk(i, j) = -Inf; for p = 1: c2 CAk(i, j) = max(CAk(i, j) , C(i, p) + Ak(p, j)); end; end; end; L(r+1,:)=CAk; % Menghitung CAkB [cak1, cak2] = size(CAk); [b1, b2] = size(B); for i = 1:cak1 for j = 1: b2 CAkB(i, j) = -Inf; for p = 1: cak2 CAkB(i, j) = max(CAkB(i, j) , CAk(i, p) + B(p, j)); end; end; end; % Menyusun matriks H for i = 1 : q for j = 1 : q if i < j H(i,j) = -Inf; end; if i == j H(i,j) = CB; end; if (i-j) ==1 H(i,j)= CAB; end; if (i-j) == r+1 H(i,j)= CAkB; end; if (i-j) > q H(i,j)=[]; end; end; end; D = Ak; end; % Menghitung K*x0 [l1, l2] = size(L);
57
[x01, x02] = size(x0); for i = 1 : l1 for j = 1 : x02 Kx0(i, j) = -Inf; for p = 1: l2 Kx0(i, j) = max(Kx0(i, j) , L(i, p) + x0(p, j)); end; end; end; if max(Kx0 - y)<=0 % Menghitung input paling lambat u1 (H*(-y)) Ht=H'; my = -y; [ht1, ht2] = size(Ht); [my1, my2] = size(my); for i = 1 : ht1 for j = 1 : my2 Htmy(i, j) = -Inf; for p = 1: ht2 Htmy(i, j) = max(Htmy(i, j) , Ht(i, p) + my(p, j)); end; end; end; u_topi = -Htmy; % Mengitung H*u_topi [h1, h2] = size(H); [utp1, utp2] = size(u_topi); for i = 1 : h1 for j = 1 : utp2 Hutp(i, j) = -Inf; for p = 1: h2 Hutp(i, j) = max(Hutp(i, j) , H(i, p) + u_topi(p, j)); end; end; end; Hutp; % Menghitung barisan output y untuk u_topi y_topi = max(Kx0, Hutp); % Menghitung input minimum simpangan delta = max(abs(y - y_topi)); u_tilde = u_topi + delta/2; % Mengitung H*u_tilde [h1, h2] = size(H); [utd1, utd2] = size(u_tilde); for i = 1 : h1 for j = 1 : utd2 Hutd(i, j) = -Inf; for p = 1: h2
58
Hutd(i, j) = max(Hutd(i, j) , H(i, p) + u_tilde(p, j)); end; end; end; Hutd; % Menampilkan hasil perhitungan disp(' HASIL PERHITUNGAN :') disp(' ===================') disp('Matriks A = '),disp(A) disp('Matriks B = '),disp(B) disp('Matriks C = '),disp(C) disp('Kondisi awal x0 = '),disp(x0) disp('Barisan output y = '),disp(y) disp('Barisan input paling lambat u_topi = '), disp((u_topi)') disp('Barisan output y untuk u_topi = '), disp((y_topi)') disp('Barisan input minimum simpangan u_tilde = '), disp((u_tilde)') disp('Barisan output y untuk u_tilde = '), disp((Hutd)') else disp('Input Minimum Simpangan tidak dapat dikerjakan (Kx0 > y)') end;
Gambar 3.2.4 List Program MATLAB Optimisasi Input-Output SLMI
3.3 Eksistensi dan Ketunggalan SPLIO Max-Plus Pada pembahasan sebelumnya telah dibahas mengenai sub-penyelesaian terbesar dari sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃. Pada bagian ini akan dibahas mengenai eksistensi dan ketunggalan penyelesaian sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃. n Diberikan matriks A R m max dengan elemen-elemen pada setiap kolomnya
tidak semuanya sama dengan 𝜀 dan b R m . Sub-penyelesaian terbesar merupakan calon penyelesaian sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃 yakni vektor 𝒙∗ dengan max(−𝑏𝑖 + 𝑎𝑖1 ) max(𝑎𝑖1 − 𝑏𝑖 ) 𝑖 𝑖 −𝑥 ∗1 ∗ (−𝑏 ) (𝑎𝑖2 − 𝑏𝑖 ) max + 𝑎 max −𝑥 𝑖 𝑖2 2 −𝒙∗ = [ = 𝑖 ]= 𝑖 ⋮ ⋮ ⋮ −𝑥 ∗ 𝑛 (−𝑏 ) (𝑎 max + 𝑎 max 𝑖 𝑖𝑛 ] 𝑖𝑛 − 𝑏𝑖 )] [ 𝑖 [ 𝑖 max{𝑎11 − 𝑏1 , 𝑎21 − 𝑏2 , … , 𝑎𝑚1 − 𝑏𝑚 } max{𝑎12 − 𝑏1 , 𝑎22 − 𝑏2 , … , 𝑎𝑚2 − 𝑏𝑚 } =[ ] ⋮ max{𝑎1𝑛 − 𝑏1 , 𝑎2𝑛 − 𝑏2 , … , 𝑎𝑚𝑛 − 𝑏𝑚 } Selanjutnya didefinisikan matriks ‘discrepancy’ dinotasikan dengan 𝐷𝐴,𝑏 di mana
59
𝐷𝐴,𝑏
𝑎11 − 𝑏1 𝑎 − 𝑏2 = [ 21 ⋮ 𝑎𝑚1 − 𝑏𝑚
𝑎12 − 𝑏1 𝑎22 − 𝑏2 ⋮ 𝑎𝑚2 − 𝑏𝑚
… 𝑎1𝑛 − 𝑏1 … 𝑎2𝑛 − 𝑏2 ] ⋮ ⋱ … 𝑎𝑚𝑛 − 𝑏𝑚
Catatan bahwa setiap −𝑥 ∗𝑗 dapat ditentukan dengan mengambil nilai maksimum dari setiap kolom 𝐷𝐴,𝑏 . Untuk memprediksi banyaknya penyelesaian persamaan 𝐴 ⨂ 𝒙 = 𝒃, maka selanjutnya didefinisikan matriks 𝑅𝐴,𝑏 yang merupakan reduksi matriks 𝐷𝐴,𝑏 sebagai berikut 𝑅𝐴,𝑏 = [𝑟𝑖𝑗 ] di mana 𝑟𝑖𝑗 = {
1 0
jika 𝑑𝑖𝑗 = maksimum kolom 𝑗 . untuk yang lainnya
Di bawah ini akan diberikan contoh-contoh penyelesaian sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃. Contoh 3.3.1 Akan ditentukan penyelesaian sistem 𝐴 ⨂ 𝒙 = 𝒃 , dengan 12 1 6 11 𝑥1 4 1 2 𝐴=[ ], 𝒙 = [𝑥2 ], dan 𝒃 = [ 5 ]. 8 −1 0 8 𝑥3 10 5 12 13 Berdasarkan matriks 𝐴 dan vektor 𝒃 diperoleh matriks 𝐷𝐴,𝑏
1 − 12 6 − 12 11 − 12 −11 4−5 1−5 2−5 =[ ] = [ −1 0 8−8 −1 − 8 0−8 −3 10 − 13 5 − 13 12 − 13
𝑅𝐴,𝑏
0 = [0 1 0
0 1 0 0
−6 −4 −9 −8
−1 −3] −8 −1
1 0]. 0 1
Perhatikan bahwa terdapat elemen bernilai 1 pada tiap baris matriks 𝑅𝐴,𝑏 . Karena pada tiap kolom matriks 𝑅𝐴,𝑏 pasti terdapat elemen bernilai 1, maka sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃 pada contoh ini hanya memiliki satu penyelesaian. Elemenelemen dari vektor penyelesaian dapat ditentukan dengan mengambil nilai maksimum dari tiap kolom 𝐷𝐴,𝑏 , yakni: −𝑥′1 = max{−11, −1,0, −3} = 0
60
−𝑥′2 = max{−6, −4, −9, −8} = −4 −𝑥′3 = max{−1, −3, −8, −1} = −1 Dengan demikian, 𝒙∗ = [0, 4, 1]𝑇 merupakan calon penyelesaian sekaligus menjadi satu-satunya penyelesaian dari sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃. Hal ini ditunjukkan sebagai berikut 1 6 1 𝐴 ⨂ 𝒙∗ = [ 4 8 −1 10 5
max{1,10,12} 12 11 0 max{4,5,3} 2 ] ⨂ [4] = [ ] = [ 5 ] = 𝒃. 0 8 max{8,3,1} 1 12 13 max{10,9,13}
Contoh 3.3.2 Akan ditentukan penyelesaian sistem 𝐴 ⨂ 𝒙 = 𝒃 , dengan 𝑥1 2 1 3 4 𝐴 = [0 𝜀 6], 𝒙 = [𝑥2 ], dan 𝒃 = [3]. 𝑥3 4 0 2 5 Berdasarkan matriks 𝐴 dan vektor 𝒃 diperoleh matriks 2−4 𝐷𝐴,𝑏 = [0 − 3 4−5 0 1 𝑅𝐴,𝑏 = [0 0 1 0
1−4 𝜀−3 0−5 0 1]. 0
3−4 −2 6 − 3] = [−3 2−5 −1
−3 −1 𝜀 3] −5 −3
Perhatikan bahwa terdapat elemen bernilai 1 pada tiap baris matriks 𝑅𝐴,𝑏 . Hal ini berarti bahwa sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃 pada contoh ini juga hanya memiliki satu penyelesaian yakni 𝒙∗ = [0, 4, 1]𝑇 . Hal ini ditunjukkan sebagai berikut 2 𝐴 ⨂ 𝒙∗ = [0 4
1 𝜀 0
max{3,4,0} 3 1 4 ⨂ = [ max{1, 𝜀, 3} ] = ] [ ] [ 3] = 𝒃 . 6 3 2 −3 5 max{5,3, −1}
Contoh 3.3.1 dan 3.3.2 di atas merupakan contoh sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃 yang memiliki penyelesaian tunggal baik untuk kasus 𝑚 > 𝑛 maupun 𝑚 = 𝑛. Berikut ini akan diberikan contoh-contoh sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃 yang tidak memiliki penyelesaian baik untuk kasus 𝑚 > 𝑛, 𝑚 = 𝑛 maupun kasus 𝑚 < 𝑛.
61
Contoh 3.3.3 Akan ditentukan penyelesaian sistem 𝐴 ⨂ 𝒙 = 𝒃 dengan 1 14 6 11 𝑥1 4 1 2 𝐴=[ ], 𝒙 = [𝑥2 ] dan 𝒃 = [ 6 ]. 8 8 −1 0 𝑥3 13 10 5 12 Berdasarkan matriks 𝐴 dan vektor 𝒃 diperoleh matriks 𝐷𝐴,𝑏
−13 = [ −2 0 −3
−8 −5 −9 −8
−3 0 0 −4] dan 𝑅 = [0 1 𝐴,𝑏 −8 1 0 0 0 −1
0 0]. 0 1
Berdasarkan matriks 𝐷𝐴,𝑏 diperoleh 𝒙∗ = [0, 5, 1]𝑇 . Namun demikian, dari matriks 𝑅𝐴,𝑏 di atas terlihat bahwa terdapat baris yang tidak memiliki nilai maksimum yakni baris pertama atau dengan kata lain semua elemen dalam baris pertama bernilai 0. Hal ini mengisyaratkan bahwa sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃 tidak memiliki penyelesaian. Hal ini diperkuat melalui perhitungan berikut: 1 4 𝐴 ⨂ 𝒙∗ = [ 8 10
max{1,11,12} 12 14 6 11 0 max{4,6,3} 1 2 ] ⨂ [5] = [ ] = [ 6 ] ≤ [ 6 ] = 𝒃. 8 8 −1 0 max{8,4,1} 1 13 13 5 12 max{10,10,13}
Dengan demikian, 𝒙∗ hanya merupakan sub-penyelesaian terbesar dan bukan merupakan penyelesaian sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃. Contoh 3.3.4 Akan ditentukan penyelesaian sistem 𝐴 ⨂ 𝒙 = 𝒃, dengan 𝑥1 2 1 3 8 𝑥 𝐴 = [0 𝜀 6], 𝒙 = [ 2 ], dan 𝒃 = [3]. 𝑥3 4 0 2 5 Berdasarkan matriks 𝐴 dan vektor 𝒃 diperoleh matriks 𝐷𝐴,𝑏
−6 = [−3 −1
−7 𝜀 −5
0 −5 3 ] dan 𝑅𝐴,𝑏 = [0 1 −3
0 0 1
0 1]. 0
62
Berdasarkan matriks 𝐷𝐴,𝑏 diperoleh 𝒙∗ = [1, 5, −3]𝑇 . Namun demikian, dari matriks 𝑅𝐴,𝑏 di atas terlihat bahwa semua elemen dalam baris pertama bernilai 0. Hal ini mengisyaratkan bahwa sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃 dalam contoh ini tidak memiliki penyelesaian. Hal ini juga diperkuat melalui perhitungan berikut: 2 𝐴 ⨂ 𝒙 = [0 4 ∗
max{3,6,0} 3 1 6 8 6] ⨂ [ 5 ] = [ max{1, 𝜀, 3} ] = [3] ≤ [3] = 𝒃 . 2 −3 5 5 max{5,5, −1}
1 𝜀 0
Dengan demikian, 𝒙∗ hanya merupakan sub-penyelesaian terbesar dan bukan merupakan penyelesaian sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃. Contoh 3.3.5 Akan ditentukan penyelesaian sistem 𝐴 ⨂ 𝒙 = 𝒃, dengan 𝑥1 1 0 3 1 𝐴=[ ], 𝒙 = [𝑥2 ], dan 𝒃 = [ ] . 𝜀 4 2 6 𝑥3 Berdasarkan matriks 𝐴 dan vektor 𝒃 diperoleh matriks 𝐷𝐴,𝑏 = [
0 𝜀
−1 −2
2 1 1 ] dan 𝑅𝐴,𝑏 = [ −4 0 0
1 ]. 0
Berdasarkan matriks 𝐷𝐴,𝑏 diperoleh 𝒙∗ = [0, 1, −2]𝑇 . Serupa dengan dua contoh sebelumnya, sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃 dalam contoh ini juga tidak memiliki penyelesaian karena semua elemen pada baris kedua matriks 𝑅𝐴,𝑏 -nya bernilai 0. Hal ini ditunjukkan juga melalui perhitungan berikut: 1 𝐴⨂𝒙 =[ 𝜀 ∗
0 4
0 max{1,1,1} 3 1 1 ]⨂[ 1 ] = [ ]=[ ]≤[ ]=𝒃 max{𝜀, 5,0} 2 5 6 −2
Jadi, sistem persamaan linear tersebut hanya memiliki sub-penyelesaian terbesar namun tidak mempunyai penyelesaian. Selanjutnya akan diberikan contoh-contoh sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃 yang memiliki takhingga banyak penyelesaian baik untuk kasus 𝑚 > 𝑛, 𝑚 = 𝑛 maupun kasus 𝑚 < 𝑛. Contoh 3.3.6 Akan ditentukan penyelesaian sistem 𝐴 ⨂ 𝒙 = 𝒃 dengan
63
1 14 6 11 𝑥1 4 1 2 𝐴=[ ], 𝒙 = [𝑥2 ], dan 𝒃 = [ 5 ]. 3 8 −1 0 𝑥3 15 10 5 12 Berdasarkan matriks 𝐴 dan vektor 𝒃 diperoleh matriks 𝐷𝐴,𝑏
−13 −8 −4 = [ −1 −4 5 −5 −10
−3 0 −3] dan 𝑅 = [0 𝐴,𝑏 −3 1 −3 0
0 1 1 0
1 1]. 1 1
Berdasarkan matriks 𝐷𝐴,𝑏 diperoleh 𝒙∗ = [−5, 4, 3]𝑇 . Selanjutnya diperoleh max{−4,10,14} 1 14 6 11 −5 max{−1,5,5} 4 1 2 𝐴 ⨂ 𝒙∗ = [ ]⨂[ 4 ] = [ ]=[5]=𝒃, 3 8 −1 0 max{3,3,3} 3 15 10 5 12 max{5,9,15} yang berarti 𝒙∗ merupakan penyelesaian dari 𝐴 ⨂ 𝒙 = 𝒃. Akan tetapi, pada baris kedua dan ketiga matriks 𝑅𝐴,𝑏 terdapat lebih dari satu nilai maksimum atau dengan kata lain terdapat lebih dari satu elemen bernilai 1 pada kedua baris tersebut. Hal ini mengisyaratkan bahwa sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃 memiliki takhingga banyak penyelesaian. Selain itu, berdasarkan Teorema 3.1.4 diperoleh bahwa elemen-elemen dari 𝒙∗ merupakan batas atas. Karena itu, elemen-elemen vektor penyelesaian 𝒙 dalam contoh ini harus mememenuhi 𝑥1 ≤ −5, 𝑥2 ≤ 4 dan 𝑥3 ≤ 3. Pada baris pertama dan keempat matriks 𝑅𝐴,𝑏 nampak bahwa nilai maksimum terdapat pada kolom ke-3 karena itu 𝑥3 = 3. Pada baris kedua nilai maksimum terdapat pada kolom ke-2 dan ke-3 maka terdapat dua kemungkinan yakni 𝑥2 = 4 atau 𝑥3 = 3. Bila nilai 𝑥3 diubah maka akan mempengaruhi persamaan baris pertama dan keempat. Karena itu, selama 𝑥2 ≤ 4 maka persamaan pertama dan keempat akan selalu terpenuhi. Demikian halnya dengan memilih 𝑥1 ≤ −5 maka persamaan baris akan selalu terpenuhi. Jadi, semua vektor 𝒙 yang berbentuk 𝒙 = [𝑎, 𝑏, 3]𝑇 dengan 𝑎 ≤ −5 dan 𝑏 ≤ 4 juga memenuhi sistem persamaan. Jadi, sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃 dalam contoh ini memiliki takhingga banyak penyelesaian.
64
Contoh 3.3.7 Akan ditentukan penyelesaian sistem 𝐴 ⨂ 𝒙 = 𝒃 , dengan 𝑥1 2 −1 3 4 𝐴 = [0 𝜀 6], 𝒙 = [𝑥2 ], dan 𝒃 = [3]. 𝑥3 4 0 4 5 Berdasarkan matriks 𝐴 dan vektor 𝒃 diperoleh matriks −2 𝐷𝐴,𝑏 = [−3 −1
−5 𝜀 −5
0 −1 3 ] dan 𝑅𝐴,𝑏 = [0 1 −1
1 0 1
0 1] . 0
Berdasarkan matriks 𝐷𝐴,𝑏 diperoleh 𝒙∗ = [1, 5, −3]𝑇 . Selanjutnya diperoleh 2 𝐴 ⨂ 𝒙 = [0 4 ∗
−1 𝜀 0
max{3,4,0} 3 1 4 6] ⨂ [ 5 ] = [max{1, 𝜀, 3}] = [3] = 𝒃 . 4 −3 5 max{5,5,1}
Nampak bahwa 𝒙∗ merupakan penyelesaian dari sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃 . Akan tetapi, dapat diperiksa bahwa semua 𝒙 yang memenuhi bentuk 𝒙 = [𝑎, 5, −3]𝑇 dengan 𝑎 ≤ 1 juga memenuhi sistem persamaan di atas. Jadi, sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃 dalam contoh ini memiliki takhingga banyak penyelesaian. Contoh 3.3.8 Akan ditentukan penyelesaian sistem 𝐴 ⨂ 𝒙 = 𝒃 , dengan 𝑥1 2 2 1 4 𝐴=[ ], 𝒙 = [𝑥2 ], dan 𝒃 = [ ] . 6 4 7 8 𝑥3 Berdasarkan matriks 𝐴 dan vektor 𝒃 diperoleh matriks 𝐷𝐴,𝑏 = [
−2 −2
−2 1
−3 1 ] dan 𝑅𝐴,𝑏 = [ 2 1
0 1
0 ]. 1
Berdasarkan matriks 𝐷𝐴,𝑏 diperoleh 𝒙∗ = [2, −1, −2]𝑇 . Selanjutnya ditunjukkan bahwa 𝒙∗ juga merupakan penyelesaian dari sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃 yakni: 2 4
𝐴 ⨂ 𝒙∗ = [
0 2
2 max{4, −1, −1} 1 4 ] ⨂ [−1] = [ ] = [ ] = 𝒃. max{6,1,1} 6 3 −2
65
Namun demikian, dapat diperiksa bahwa semua 𝒙 yang berbentuk 𝒙 = [2, 𝑎, 𝑏]𝑇 dengan 𝑎 ≤ −1 dan 𝑏 ≤ −2 juga memenuhi sistem persamaan di atas. Jadi, sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃 pada contoh ini juga memiliki takhingga banyak penyelesaian. Matriks 𝐷𝐴,𝑏 dan 𝑅𝐴,𝑏 berperan dalam menentukan perilaku sistem persamaan ⨂ 𝒙 = 𝒃 . Berikut ini diberikan teorema mengenai ada atau tidak adanya (eksistensi) penyelesaian 𝐴 ⨂ 𝒙 = 𝒃. Teorema 3.3.9 n Diberikan sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃 di mana A R m max dengan elemen-elemen
pada setiap kolomnya tidak semuanya sama dengan 𝜀 dan b R m . 1. Jika terdapat baris nol pada matriks 𝑅𝐴,𝑏 maka sistem tidak mempunyai penyelesaian. 2. Jika terdapat paling tidak satu elemen 1 pada tiap baris 𝑅𝐴,𝑏 , maka 𝒙∗ adalah penyelesaian dari sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃. Bukti: 1. Misalkan baris nol pada matriks 𝑅𝐴,𝑏 adalah baris ke 𝑘 dan andaikan 𝒙∗ merupakan penyelesaian dari sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃, maka −𝑥 ∗𝑗 ≥ max(−𝑏𝑖 + 𝑎𝑖𝑗 ) > −𝑏𝑘 + 𝑎𝑘𝑗 𝑖
Akibatnya, −𝑥 ∗𝑗 > −𝑏𝑘 + 𝑎𝑘𝑗 ⇔ 𝑎𝑘𝑗 + 𝑥 ∗𝑗 < 𝑏𝑘 , ∀𝑗. Dengan demikian, 𝒙∗ tidak memenuhi persamaan ke- 𝑘. Hal ini bertentangan dengan 𝒙∗ adalah penyelesaian dari sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃. Jadi, 𝒙∗ bukan merupakan penyelesaian dari sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃 atau sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃 tidak mempunyai penyelesaian. 2. Akan dibuktikan kontraposisinya. Andaikan 𝒙∗
bukan merupakan
penyelesaian dari sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃. BerdasarkanTeorema 3.1.4 diperoleh
66
−𝑥 ∗𝑗 ≥ −𝑏𝑘 + 𝑎𝑘𝑗 , ∀𝑘, 𝑗 Akibatnya, max(𝑎𝑘𝑗 + 𝑥 ∗𝑗 ) ≤ 𝑏𝑘 𝑗
Jika 𝒙∗ bukan merupakan penyelesaian dari 𝐴 ⨂ 𝒙 = 𝒃, maka terdapat 𝑘 sedemikian sehingga max(𝑎𝑘𝑗 + 𝑥 ∗𝑗 ) < 𝑏𝑘 𝑗
Hal ini ekuivalen dengan −𝑥 ∗𝑗 > −𝑏𝑘 + 𝑎𝑘𝑗 , ∀𝑗 Karena −𝑥 ∗𝑗 = max(−𝑏𝑙 + 𝑎𝑙𝑗 ) untuk beberapa 𝑙, maka tidak ada elemen dalam baris 𝑘 dari 𝑅𝐴,𝑏 yang bernilai 1.
∎
Teorema 3.3.9 di atas digunakan untuk menentukan eksistensi penyelesaian sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃. Namun demikian, eksistensi ini belum menjelaskan kapan penyelesaiannya tunggal dan kapan penyelesaiannya taktunggal. Karena itu, untuk menentukan ketunggalan sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃 diberikan definisi berikut. Definisi 3.3.10 Elemen bernilai 1 pada suatu baris 𝑅𝐴,𝑏 dinamakan elemen peubah tetap jika 1. Elemen tersebut merupakan satu-satunya elemen bernilai 1 pada baris tersebut (lone-one), atau 2. Elemen tersebut berada pada kolom yang sama dengan lone-one. Elemen-elemen bernilai 1 lainnya dinamakan elemen-elemen slack. Tabel 3.3.1 berikut ini akan menunjukkan elemen peubah tetap dari setiap contoh yang telah diberikan sebelumnya. Elemen yang dilingkari merupakan elemen peubah tetap. Pada Contoh 3.3.1, semua elemen bernilai 1 merupakan peubah tetap. Persamaan baris pertama menetapkan elemen 𝑥3 = 1, persamaan baris kedua menetapkan elemen 𝑥2 = 4, dan persamaan baris ketiga menetapkan elemen
67
𝑥1 = 0. Ketika sampai pada persamaan keempat, semua elemen 𝒙 sudah ditentukan. Setiap elemen yang sudah dipilih tidak dapat diubah karena bila diubah akan menimbulkan pertidaksamaan pada salah satu dari ketiga baris sebelumnya. Tabel 3.3.1 Daftar Elemen Peubah Tetap pada Contoh
Tidak Mempunyai
Mempunyai Satu
Mempunyai Takhingga
Penyelesaian
Penyelesaian
Banyak Penyelesaian
Contoh 3.3.3 𝑅𝐴,𝑏
0 = [0 1 0
0 1 0 0
Contoh 3.3.1 0 0] 0 1
𝑅𝐴,𝑏
0 = [0 1 0
0 1 0 0
Contoh 3.3.6 1 0] 0 1
Contoh 3.3.4 0 𝑅𝐴,𝑏 = [0 1 1 0
0 0 0 1] 1 0 1 0
0 1 1 0
1 1] 1 1
Contoh 3.3.7
Contoh 3.3.5 𝑅𝐴,𝑏 = [
𝑅𝐴,𝑏
0 = [0 1 0
1 ] 0
Contoh 3.3.2 0 𝑅𝐴,𝑏 = [0 1
1 0 0 1] 0 0
0 𝑅𝐴,𝑏 = [0 1
1 0 0 1] 1 0
Contoh 3.3.8 𝑅𝐴,𝑏 = [
1 1
0 1
0 ] 1
Pada Contoh 3.3.2, semua elemen bernilai 1 juga merupakan peubah tetap. Persamaan baris pertama menetapkan elemen 𝑥2 = 3, persamaan baris kedua menetapkan elemen 𝑥3 = −3, dan persamaan baris ketiga menetapkan elemen 𝑥1 = 1. Pada Contoh 3.3.6, terdapat elemen slack pada 𝑅𝐴,𝑏 . Persamaan baris pertama menetapkan elemen 𝑥3 = 3. Pada persamaan baris kedua, terdapat dua kemungkinan untuk memenuhi persamaan yakni 𝑥2 = 4 atau 𝑥3 = 3. Akan tetapi, nilai 𝑥3 sudah ditetapkan sebelumnya yakni sama dengan 3. Jadi, asalkan 𝑥2 ≤ 4 maka persamaan baris diatasnya tidak akan berubah. Dengan cara yang sama, pada persamaan baris ketiga, asalkan 𝑥1 ≤ −5 maka persamaan baris diatasnya tidak akan berubah. Sedangkan, pada persamaan baris keempat, elemen penyelesaiannya sudah ditetapkan oleh persamaan baris pertama. Dengan demikian, dengan
68
menetapkan 𝑥3 = 3 dan asalkan 𝑥1 ≤ −5 serta 𝑥2 ≤ 4, maka persamaan baris akan selalu benar. Berikut ini diberikan teorema untuk menunjukkan bila mana persamaan 𝐴 ⨂ 𝒙 = 𝒃 memiliki penyelesaian tunggal dan bilamana penyelesaiannya taktunggal. Teorema 3.3.11 n Diberikan sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃 di mana A R m max dengan elemen-elemen
pada setiap kolomnya tidak semuanya sama dengan 𝜀 dan b R m serta penyelesaian persamaan 𝐴 ⨂ 𝒙 = 𝒃 ada. 1. Jika tiap baris 𝑅𝐴,𝑏 memiliki lone one, maka penyelesaian sistem persamaan tunggal. 2. Jika terdapat elemen-elemen slack pada 𝑅𝐴,𝑏 , maka sistem memiliki takhingga banyak penyelesaian. Bukti: 1. Jika terdapat lone one pada tiap baris 𝑅𝐴,𝑏 , maka terdapat satu elemen peubah tetap pada tiap baris 𝑅𝐴,𝑏 . Hal ini berarti bahwa tidak akan ada elemen-elemen slack. Dengan demikian, semua elemen 𝒙 tetap dan penyelesaian sistem persamaan tunggal. 2. Misalkan 𝑟𝑖𝑗 adalah salah satu elemen slack pada 𝑅𝐴,𝑏 dan 𝒙∗ merupakan penyelesaian dari 𝐴 ⨂ 𝒙 = 𝒃. Karena 𝑟𝑖𝑗 tidak tetap, maka tidak terdapat elemen peubah tetap pada kolom ke 𝑗 dari 𝑅𝐴,𝑏 . Jadi, persamaan dapat dipenuhi tanpa menggunakan elemen 𝑥 ∗𝑗 . Dengan demikian, meskipun nilai 𝑥 ∗𝑗 menunjukkan nilai maksimum yang mungkin untuk elemen ini, setiap nilai yang lebih kecil atau sama dengan 𝑥 ∗𝑗 tidak akan mempengaruhi eksistensi persamaan baris yang telah ditetapkan.
∎
Sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃 dalam Contoh 3.3.1 dan 3.3.2 memiliki penyelesaian tunggal karena pada tiap baris matriks 𝑅𝐴,𝑏 -nya memiliki lone one. Sedangkan sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃 dalam Contoh 3.3.6, 3.3.7 dan 3.3.8
69
memiliki takhingga banyak penyelesaian karena terdapat elemen slack pada matriks 𝑅𝐴,𝑏 -nya. Akibat 3.3.12 n Diberikan persamaan matriks 𝐴 ⨂ 𝒙 = 𝒃 di mana A R m max dengan elemen-
elemen pada setiap kolomnya tidak semuanya sama dengan 𝜀 dan b R m serta 𝑚 < 𝑛. Jika penyelesaian persamaan 𝐴 ⨂ 𝒙 = 𝒃 ada maka sistem memiliki takhingga banyak penyelesaian. Bukti: Penyelesaian sistem persamaan 𝐴 ⨂ 𝒙 = 𝒃 ada maka tidak terdapat baris nol pada matriks 𝑅𝐴,𝑏 . Andaikan penyelesaian sistem tunggal maka terdapat lone one pada tiap baris 𝑅𝐴,𝑏 . Sementara itu, 𝑚 < 𝑛 berarti banyaknya persamaan lebih sedikit daripada banyaknya variabel. Karena itu, pastilah terdapat slack pada matriks 𝑅𝐴,𝑏 . Hal ini bertentangan dengan penyelesaian sistem tunggal. Jadi, haruslah sistem memliki takhingga banyaknya penyelesaian.
∎
Pembahasan pada bagian di atas masih terbatas pada sistem persamaan n 𝐴 ⨂ 𝒙 = 𝒃 dengan A R m max dengan elemen-elemen pada setiap kolomnya tidak
semuanya sama dengan 𝜀 dan b R m . Berikut ini diberikan penyelesaian sistem persamaan untuk kasus-kasus lain. Andaikan terdapat 𝑗 ∈ {1,2, … , 𝑛} sedemikian sehingga 𝑎𝑖𝑗 = 𝜀 untuk setiap 𝑖 ∈ {1,2, … , 𝑚} dan b R m maka berlaku hal-hal berikut 1. Jika elemen-elemen pada setiap baris matriks 𝐴 tidak semuanya sama dengan 𝜀 maka 𝑥𝑗 = 𝑎 untuk sebarang 𝑎 ∈ 𝐑 max . Hal ini berangkat dari fakta bahwa elemen netral 𝜀 merupakan elemen penyerap terhadap operasi ⨂. 2. Jika terdapat baris pada matriks 𝐴 dengan semua elemennya sama dengan 𝜀 maka sistem tidak memiliki penyelesaian. Hal ini ditunjukkan sebagai berikut. Andaikan baris tersebut adalah baris ke- 𝑘. Persamaan ke- 𝑘 berbentuk (𝐴 ⨂ 𝒙 )𝑘 = max{𝜀 + 𝑥1 , 𝜀 + 𝑥2 + ⋯ + 𝜀 + 𝑥𝑛 } = 𝑏𝑘 . 𝑗
70
Mengingat untuk setiap 𝑥 ∈ ℝmax berlaku 𝑥 ⨂ 𝜀 = 𝜀 ⨂ 𝑥 = 𝜀 + 𝑥 = 𝜀 maka (𝐴 ⨂ 𝒙 )𝑘 ≠ 𝑏𝑘 . Dengan kata lain, persamaan baris ke-𝑘 tidak terpenuhi. Jadi, sistem tidak memiliki penyelesaian. Berikut diberikan contoh-contoh untuk mengilustrasikan dua hal di atas. Contoh 3.3.13 Diberikan sistem persamaan linear 𝑥1 𝜀 1 2 [ ] ⨂ [𝑥 ] = [ ]. 𝜀 0 2 1 Sistem persamaan ini ekuivalen dengan 𝜀 ⨂ 𝑥1 ⨁ 1 ⨂ 𝑥2 = 2 𝜀 ⨁ 1 ⨂ 𝑥2 = 2 max(𝜀, 1 + 𝑥2 ) = 2 { atau { atau { atau 𝜀 ⨂ 𝑥1 ⨁ 0 ⨂ 𝑥2 = 1 𝜀 ⨁ 0 ⨂ 𝑥2 = 1 max(𝜀, 0 + 𝑥2 ) = 1 1 + 𝑥2 = 2 { sehingga diperoleh 𝑥2 = 1. 0 + 𝑥2 = 1 Jadi, semua vektor 𝒙 yang berbentuk 𝒙 = [𝑎, 1]𝑇 merupakan penyelesaian sistem di atas. Contoh 3.3.14 Diberikan sistem persamaan linear 𝑥1 𝜀 1 2 [ ] ⨂ [𝑥 ] = [ ]. 𝜀 𝜀 2 1 Sistem persamaan ini ekuivalen dengan 𝜀 ⨂ 𝑥1 ⨁ 1 ⨂ 𝑥2 = 2 𝜀 ⨁ 1 ⨂ 𝑥2 = 2 𝜀 ⨁ 1 ⨂ 𝑥2 = 2 { atau { atau { 𝜀 ⨂ 𝑥1 ⨁ 𝜀 ⨂ 𝑥2 = 1 𝜀 ⨁𝜀 =1 𝜀 =1 Karena 𝜀 ≠ 1 maka persamaan baris kedua tidak terpenuhi. Jadi, sistem persamaan di atas tidak memiliki penyelesaian. Selanjutnya, andaikan terdapat 𝑗 ∈ {1,2, … , 𝑛} sedemikian sehingga 𝑎𝑖𝑗 = 𝜀 untuk setiap 𝑖 ∈ {1,2, … , 𝑚} dan terdapat 𝑘 ∈ {1,2, … , 𝑚} sedemikian sehingga 𝑏𝑘 = 𝜀 maka berlaku hal-hal berikut 1. Jika elemen-elemen pada baris ke- 𝑘 matriks 𝐴 tidak semuanya sama dengan 𝜀 maka sistem tidak memiliki penyelesaian. Hal ini ditunjukkan sebagai berikut. Karena elemen-elemen pada baris ke- 𝑘 tidak semuanya sama dengan 𝜀 maka terdapat 𝑙 ∈ {1,2, … , 𝑛} sedemikian sehingga 𝑎𝑘𝑙 ≠ 𝜀. Agar
71
persamaan ke- 𝑘 terpenuhi maka haruslah 𝑥𝑙 = 𝜀. Namun demikian, karena terdapat 𝑝 ∈ {1,2, … , 𝑚} sedemikian sehingga 𝑏𝑝 ≠ 𝜀 maka persamaan ke- 𝑝 tidak terpenuhi. Jadi, sistem tidak memiliki penyelesaian. 2. Jika elemen-elemen pada baris ke- 𝑘 matriks 𝐴 semuanya sama dengan 𝜀 maka 𝑥𝑗 = 𝑏 untuk sebarang 𝑏 ∈ ℝmax . Hal ini berangkat dari fakta bahwa elemen netral 𝜀 merupakan elemen penyerap terhadap operasi ⨂. Berikut diberikan contoh-contoh untuk mengilustrasikan dua hal di atas. Contoh 3.3.15 Diberikan sistem persamaan linear 𝑥1 𝜀 1 2 [ ] ⨂ [𝑥 ] = [ ]. 𝜀 0 𝜀 2 Sistem persamaan ini ekuivalen dengan 𝜀 ⨂ 𝑥1 ⨁ 1 ⨂ 𝑥2 = 2 𝜀 ⨁ 1 ⨂ 𝑥2 = 2 max(𝜀, 1 + 𝑥2 ) = 2 { atau { atau { 𝜀 ⨂ 𝑥1 ⨁ 0 ⨂ 𝑥2 = 𝜀 𝜀 ⨁ 0 ⨂ 𝑥2 = 𝜀 max(𝜀, 0 + 𝑥2 ) = 𝜀 Agar persamaan baris kedua terpenuhi maka haruslah 𝑥2 = 𝜀. Namun demikian, jika 𝑥2 = 𝜀 maka persamaan baris pertama tidak terpenuhi sebab 1 + 𝜀 = 𝜀 ≠ 2. Jadi, sistem di atas tidak memiliki penyelesaian. Contoh 3.3.16 Diberikan sistem persamaan linear 𝑥1 𝜀 1 2 [ ] ⨂ [𝑥 ] = [ ]. 𝜀 𝜀 𝜀 2 Sistem persamaan ini ekuivalen dengan 𝜀 ⨂ 𝑥1 ⨁ 1 ⨂ 𝑥2 = 2 𝜀 ⨁ 1 ⨂ 𝑥2 = 2 { atau { atau 1 ⨂ 𝑥2 = 2 atau 𝑥2 = 1. 𝜀 ⨂ 𝑥1 ⨁ 𝜀 ⨂ 𝑥2 = 𝜀 𝜀 ⨁𝜀 =𝜀 Jadi, semua vektor 𝒙 yang berbentuk 𝒙 = [𝑎, 1]𝑇 merupakan penyelesaian sistem di atas. Kasus selanjutnya adalah andaikan elemen-elemen pada setiap kolom matriks 𝐴 tidak semuanya sama dengan 𝜀 dan terdapat 𝑘 ∈ {1,2, … , 𝑚} sedemikian sehingga 𝑏𝑘 = 𝜀. Jika 𝑎𝑘𝑗 ≠ 𝜀 maka 𝑥𝑗 = 𝜀. Hal ini ditunjukkan sebagai berikut. Persamaan ke- 𝑘 berbentuk 𝑎𝑘𝑗 + 𝑥𝑗 = 𝜀. Karena 𝑎𝑘𝑗 ≠ 𝜀 maka haruslah 𝑥𝑗 = 𝜀.
72
Contoh 3.3.17 Diberikan sistem persamaan linear 𝑥1 𝜀 6 8 [ ] ⨂ [𝑥 ] = [ ]. 4 𝜀 𝜀 2 Sistem persamaan ini ekuivalen dengan 𝜀 ⨂ 𝑥1 ⨁ 6 ⨂ 𝑥2 = 8 𝜀 ⨁ 6 ⨂ 𝑥2 = 8 { atau { . 4 ⨂ 𝑥1 ⨁ 𝜀 ⨂ 𝑥2 = 𝜀 4 ⨂ 𝑥1 ⨁ 𝜀 = 𝜀 Agar persamaan baris kedua terpenuhi maka haruslah 𝑥1 = 𝜀. Akibatnya, 𝑥2 = 2. Jadi, 𝒙 = [𝜀, 2]𝑇 merupakan penyelesaian sistem di atas. Bila sistem memuat banyak persamaan, dalam hal ini ukuran matriks sangat besar maka perhitungan manual dirasa kurang efektif untuk menentukan penyelesaian sistem persamaan linear 𝐴 ⨂ 𝒙 = 𝒃. Untuk itu, perlu dibuat program komputer untuk memudahkan perhitungan. Bahasa program yang akan digunakan adalah bahasa pemograman komputer MATLAB. Program ini akan menampilkan penyelesaian sistem persamaan linear. List program secara lengkap diberikan dalam Gambar berikut. % % % % %
Program Matlab Penyelesaian Sistem Persamaan Linear Ax = b Oleh: M. Andy Rudhito & Regina FKIP Universitas Sanata Dharma Input: A = matriks max-plus Amxn b = vektor mx1 Output: Menampilkan penyelesaian sistem
function x = solsislinmax % Memasukkan matriks A dan b A = input('Masukkan matriks A(mxn) = '); disp(' ') b = input('Masukkan matriks b(mx1) = '); disp(' ') [m,n]= size (A); [p,q]= size (b); if m == p & q == 1 A1=zeros(1,n); for j = 1:n if A(:,j)== -inf A1(j)=0; else A1(j)=1; end; end; Sum1 = sum(A1); b1=zeros(m,1); for i = 1:m
73
if b(i)== -inf b1(i)=0; else b1(i)=1; end; end; c = zeros(m,1); for i = 1:m if R(i,:)== 0 c(i)= 0; else c(i)= 1; end end; Sum3 = sum(c); if Sum3 < m x = '{}'; else x = xc; end %Menampilkan Penyelesaian Sistem disp('Matriks A = '),disp(A) disp('Matriks b = '),disp(b) disp('Matriks D = '),disp(D) disp('Matriks R = '),disp(R) disp('Penyelesaian sistem adalah '), disp('x = ') disp(x) else disp('Elemen-elemen tiap kolom matriks A tidak semuanya -inf dan elemen-elemen matriks b semuanya berhingga') end; % Peringatan sistem persamaan tidak dapat diselesaikan else disp('Ordo matriks A dan b tidak sesuai') end;
Gambar 3.3.1. List Program MATLAB untuk Menyelesaikan SPLIO Max-Plus
Berikut ini diberikan hasil eksekusi untuk beberapa contoh soal yang telah diberikan pada bagian sebelumnya. Perhitungan MATLAB untuk Contoh 3.3.1: Masukkan matriks A(mxn) = [1 6 11; 4 1 2; 8 -1 0; 10 5 12] Masukkan matriks b(mx1) = [12; 5; 8; 13] Matriks A = 1 6 11 4 1 2 8 -1 0 10 5 12
74
Matriks b = 12 5 8 13 Matriks D = -11 -6 -1 -4 0 -9 -3 -8 Matriks R = 0 0 0 1 1 0 0 0
-1 -3 -8 -1 1 0 0 1
Penyelesaian sistem adalah x = 0 4 1
Perhitungan MATLAB untuk Contoh 3.3.3: Masukkan matriks A(mxn) = [1 6 11; 4 1 2; 8 -1 0; 10 5 12] Masukkan matriks b(mx1) = [14; 6; 8; 13] Matriks A = 1 6 11 4 1 2 8 -1 0 10 5 12 Matriks b = 14 6 8 13 Matriks D = -13 -8 -3 -2 -5 -4 0 -9 -8 -3 -8 -1 Matriks R = 0 0 0 0 1 0 1 0 0 0 0 1 Penyelesaian sistem adalah x = {}
75
Perhitungan MATLAB untuk Contoh 3.3.8: Masukkan matriks A(mxn) = [1 6 11;4 1 2;8 -1 0;10 5 12] Masukkan matriks b(mx1) = [14;5;3;15] Matriks A = 1 6 4 1 8 -1 10 5
11 2 0 12
Matriks b = 14 5 3 15 Matriks D = -13 -8 -1 -4 5 -4 -5 -10
-3 -3 -3 -3
Matriks R = 0 0 0 1 1 1 0 0
1 1 1 1
Penyelesaian sistem adalah x = -5 4
3.4 Penerapan SPLIO Max-Plus pada Masalah Ramp-Handling Pesawat Ramp handling merupakan kegiatan penanganan pesawat yang dilakukan di ramp area atau apron yakni suatu pelataran yang ada di bandara, saat jeda waktu antara pesawat block-on (yakni saat ganjalan pesawat dipasang dan pesawat dalam posisi berhenti) hingga pesawat block-off (yakni saat ganjalan dilepas dan pesawat bersiap menuju landasan pacu). Waktu antara pesawat block-on dan pesawat blockoff ini dikenal dengan istilah ground time. Keberlangsungan kegiatan ramp handling berada dalam pengawasan dari satuan unit khusus yang dikenal dengan istilah ramp dispatcher. Setiap petugas ramp dispatcher bertanggung jawab untuk mengawasi dan mengkoordinasi segala aktivitas ramp berkaitan dengan
76
keberangkatan ataupun kedatangan pesawat. Secara umum, aktivitas-aktivitas yang dilakukan dalam ramp handling adalah sebagai berikut 1. Maintenance
merupakan
kegiatan pemeriksaan/pemeliharaan
kondisi
pesawat, termasuk kebersihan tempat duduk dan pantry. 2. Fueling/Refueling merupakan kegiatan pengisian bahan bakar pesawat. 3. Loading/Unloading berkaitan pelaksanaan bongkar muat barang/bagasi. 4. Aircraft Cleaning berkaitan dengan kegiatan membersihkan kabin pesawat dan kamar kecil. 5. Catering berkaitan dengan penyediaan konsumsi bagi para penumpang selama penerbangan. Menurut Suwarno (2001), penanganan pesawat di bandara dibedakan atas dua cara yakni turnaround arrangement dan transit arrangement. Turnaround arrangement adalah penanganan bagi pesawat yang mendarat di kota tujuan akhir (destination) sedangkan transit arrangement adalah penanganan bagi pesawat yang mendarat di kota persinggahan atau transit. Penanganan pesawat ini dilakukan pada tempo waktu yang sudah ditentukan yakni sesuai dengan ground time agar sesuai dengan jadwal penerbangan (departure time). Lebih lanjut, Suwarno (2001) menambahkan penanganan pesawat di bandara udara, baik turnaround arrangement maupun transit arrangement menganut sistem yang sama. Perbedaannya terletak pada lama waktu penanganannya. Penanganan transit arrangement biasanya lebih pendek dibanding turnaround arrangement. Hal ini disebabkan karena pada transit arrangement terdapat perbedaan dalam halhal tertentu, yaitu: 1. Kabin tidak dibersihkan seluruhnya. 2. Awak pesawat (crew) biasanya tidak diganti. 3. Penumpang transit tidak turun ke ruang transit. 4. Kadangkala konsumsi untuk penumpang sudah tersedia di dalam pesawat, kecuali jika ada penambahan penumpang pada saat-saat terakhir. Prosedur penanganan pesawat di bandara udara antara satu jenis pesawat dengan jenis pesawat yang lain tidak sama. Hal ini tergantung tipe pesawat, kondisi
77
pesawat, jarak yang akan ditempuh pesawat, serta banyaknya penumpang. Namun, secara umum lama ground time untuk keperluan turnaround arrangement adalah 40 menit sampai 1 jam sedangkan untuk transit arrangement memerlukan minimal 25 menit untuk penerbangan domestik dan sekitar 1 jam untuk penerbangan internasional (Bazargan, 2004). Berdasarkan penjelasan di atas nampak bahwa kegiatan ramp handling merupakan salah satu masalah sinkronisasi
dalam SKD. Dalam masalah
sinkronisasi, kejadian-kejadian (events) terjadi secara simultan dan harus selesai pada batas waktu yang ditentukan (deadline). Rangkaian kegiatan ramp handling dilakukan secara simultan dan harus selesai pada waktu yang ditentukan sehingga ketepatan jadwal tercapai. Misalkan di suatu bandara terdapat tiga pesawat yakni pesawat A, B dan C telah tiba di gate-nya masing-masing. Pesawat-pesawat tersebut membutuhkan penanganan sebelum penerbangan berikutnya. Penanganan yang dibutuhkan berupa refueling, maintenance, food service dan luggage service. Masing-masing pesawat membutuhkan waktu yang berbeda untuk refueling dan food service (terkait dengan jarak tempuh penerbangan selanjutnya), maintenance (tergantung apakah ada masalah dalam penerbangan selanjutnya atau tergantung pada usia pesawat terbang tersebut), dan luggage service (berkaitan dengan jarak tempuh dan banyaknya penumpang). Ketiga pesawat tersebut akan ditangani sekaligus dengan asumsi bahwa tim yang bertugas memadai dan peralatan yang dibutuhkan pun memadai. Berikut ini diberikan matriks yang berisi waktu yang diperlukan untuk penanganan pesawat per kegiatan penanganan (waktu kegiatan dalam menit). 𝑅
𝑀
𝐹
𝐿
25 10 35
15
Gate 1
15 45 15
20
Gate 2
[25 15 20
15]
Gate 3
78
Contoh 3.4.1 Ketiga pesawat memiliki ground time berturut-turut 𝑔𝑎 = 45, 𝑔𝑏 = 50, 𝑔𝑐 = 55 menit. Akan dicari waktu mulai paling lambat untuk kegiatan 𝑅, 𝑀, 𝐹, dan 𝐿 sedemikian sehingga kegiatan terakhir sudah selesai pada waktu keberangkatan pesawat. Masalah ini dapat diformulasikan dalam bentuk sistem persamaan aljabar max-plus sebagai berikut. 25 10 [15 45 25 15
𝑡1 45 35 15 𝑡2 15 20] ⨂ [𝑡 ] = [50]. 3 55 20 15 𝑡 4
Dalam hal ini kita akan mencari vektor 𝒕. Hasil eksekusi program MATLAB untuk sistem ini diberikan sebagai berikut. Masukkan matriks A(mxn) = [25 10 35 15;15 45 15 20;25 15 20 15] Masukkan matriks b(mx1) = [45;50;55] Matriks A = 25 10 15 45 25 15
35 15 20
15 20 15
Matriks D = -20 -35 -35 -5 -30 -40
-10 -35 -35
-30 -30 -40
Matriks R = 1 0 0 1 0 0
1 0 0
1 1 0
Matriks b = 45 50 55
Penyelesaian sistem adalah t = {}
Berdasarkan matriks 𝑅 dan Teorema 3.3.9 maka sistem tidak memiliki penyelesaian. Vektor 𝒕∗ = [20, 5, 10, 30]𝑇 bukan merupakan penyelesaian sebab
79
25 10 [15 45 25 15
20 45 45 35 15 5 15 20] ⨂ [10] = [50] ≠ [50] 45 55 20 15 30
Meskipun 𝒕∗ bukan merupakan penyelesaian yang tepat untuk sistem persamaan di atas, bukan berarti pesawat akan mengalami delay. Akan tetapi, tidak terpenuhinya persamaan ketiga disebabkan karena penanganan pesawat di gate 3 selesai lebih awal. Penyelesaian seperti ini disebut penyelesaian tak ideal. Contoh 3.4.2 Bagian Departure Control memutuskan untuk menjadwal ulang waktu lepas landas (take-off) dari ketiga pesawat karena pesawat di gate 1 dan 2 membutuhkan waktu penanganan yang lebih panjang. Ground time ketiga pesawat secara berturut-turut dalam 𝑔𝑎 = 50, 𝑔𝑏 = 55, 𝑔𝑐 = 45 menit. Sistem persamaaannya berbentuk 25 10 [15 45 25 15
𝑡1 50 35 15 𝑡2 15 20] ⨂ [𝑡 ] = [55]. 3 45 20 15 𝑡 4
Hasil eksekusi program MATLAB untuk sistem ini diberikan sebagai berikut Masukkan matriks A(mxn) = [25 10 35 15;15 45 15 20;25 15 20 15] Masukkan matriks b(mx1) = [50;55;45] Matriks A = 25 10 15 45 25 15
35 15 20
15 20 15
-15 -40 -25
-35 -35 -30
Matriks b = 50 55 45 Matriks D = -25 -40 -40 -10 -20 -30
80
Matriks R = 0 0 1 0 0 1 0 0 1 0 0 1 Penyelesaian sistem adalah t = 20 10 15 30
Berdasarkan matriks 𝑅 dan berdasarkan Teorema 3.3.11 maka sistem memiliki takhingga banyak penyelesaian dan 𝒕 merupakan salah satu penyelesaian sistem. Semua vektot 𝒕 yang berbentuk 𝒕 = [𝑎, 10, 15, 𝑏]𝑇 dengan 𝑎 ≤ 20 dan 𝑏 ≤ 30 juga merupakan penyelesaian sistem. Dalam hal ini, waktu mulai paling lambat untuk kegiatan perawatan dan layanan makanan sudah pasti dan tidak dapat diubah. Sedangkan waktu mulai untuk kegiatan pengisian bahan bakar dan layanan bagasi bisa lebih awal tanpa mempengaruhi penyelesaian. Kehadiran lebih dari satu elemen 1 pada baris ketiga matriks 𝑅 mengindikasi bahwa kegiatan pengisisan bahan bakar dan layanan bagasi selesai dalam waktu bersamaan. Contoh-contoh yang diberikan di atas mengikuti contoh dalam Andersen (2002). Penanganan pesawat hanya dibatasi pada empat kegiatan yakni pengisian bahan bakar, perawatan, layanan makanan, dan layanan bagasi. Berikut diberikan contoh rangkaian kegiatan ramp handling secara lebih rinci. Contoh 3.4.3 Terdapat tiga pesawat yakni pesawat model 767-200, 767-200ER dan 767-300 yang tiba di gatenya masing-masing dan memerlukan penanganan turnaround sebelum penerbangan selanjutnya. Lama ground time ketiga pesawat secara berturut-turut 𝑔𝑎 = 40, 𝑔𝑏 = 40, 𝑔𝑐 = 45 menit. Akan dicari waktu mulai paling lambat untuk setiap kegiatan penanganan sedemikian sehingga kegiatan terakhir sudah selesai pada waktu keberangkatan pesawat. Diasumsikan bahwa tim bertugas dalam kegiatan penanganan memadai. Tabel kegiatan ramp handling ketiga pesawat diberikan sebagai berikut.
81
Tabel 3.4.1 Kegiatan Ramp Handling 3 Pesawat
No
1 2 3 4 5 6 7 8
Nama Kegiatan
Unloading & loading bulk compartment Fuel airplane Service toilet Service potable water Service galleys Service cabin Loading AFT compartment Loading FWD compartment
Waktu yang Diperlukan Pesawat 767200 (menit)
Waktu yang Diperlukan Pesawat 767200ER (menit)
Waktu yang Diperlukan Pesawat 767-300 (menit)
26
31
36
18 12 7 21 13,5
30 12 7 21 18,5
18 12 10 26 14,5
10
10
14
12
6
16
Berdasarkan tabel di atas, dapat dibentuk sistem persamaaan 𝐴 ⨂ 𝒕 = 𝒃 sebagai berikut
26 18 [31 30 36 18
12 7 12 7 12 10
21 13,5 10 21 18,5 10 26 14,5 14
𝑡1 𝑡2 𝑡3 12 40 𝑡 6 ] ⨂ 𝑡4 = [40]. 5 16 45 𝑡6 𝑡7 [𝑡8 ]
Penyelesaian sistem ini dapat dicari dengan menggunakan program yang telah dibuat sebelumnya dengan sedikit modifikasi. Hasil eksekusi program diberikan sebagai berikut: Masukkan matriks A(mxn) = [26 18 12 7 21 13.5 10 12;31 30 12 7 21 18.5 10 6;36 18 12 10 26 14.5 14 16] Masukkan matriks b(mx1) = [40;40;45] Matriks A =
82
26.0000 18.0000 10.0000 12.0000 31.0000 30.0000 10.0000 6.0000 36.0000 18.0000 14.0000 16.0000
12.0000
7.0000
21.0000
13.5000
12.0000
7.0000
21.0000
18.5000
12.0000
10.0000
26.0000
14.5000
Matriks b = 40 40 45 Matriks D = -14.0000 -22.0000 30.0000 -28.0000 -9.0000 -10.0000 30.0000 -34.0000 -9.0000 -27.0000 31.0000 -29.0000 Matriks R = 0 0 1 1 1 0
1 1 0
-28.0000
-33.0000
-19.0000
-26.5000
-
-28.0000
-33.0000
-19.0000
-21.5000
-
-33.0000
-35.0000
-19.0000
-30.5000
-
1 1 0
1 1 1
0 1 0
1 1 0
1 0 0
Penyelesaian sistem adalah t = 9.0000 10.0000 28.0000 33.0000 19.0000 21.5000 30.0000 28.0000
Kolom-kolom matrks 𝐴 menyatakan jenis kegiatan ramp handling berturut dari nomor 1 sampai 9. Dalam hal ini, akan ditentukan waktu mulai paling lambat untuk setiap jenis kegiatan. Berdasarkan matriks 𝑅 dan berdasarkan Teorema 3.3.11 maka sistem memiliki takhingga banyak penyelesaian dan t merupakan salah satu penyelesaian sistem persamaan 𝐴 ⨂ 𝒕 = 𝒃 di atas. Karena tidak terdapat elemen peubah tetap pada matriks 𝑅 maka semua elemen vektor 𝒕 berupa variabel bebas. Semua vektor 𝒕 yang berbentuk 𝒕 = [𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔, ℎ]𝑇 dengan 𝑎 ≤ 9, 𝑏 ≤ 10, 𝑐 ≤ 28, 𝑑 ≤ 33, 𝑒 ≤ 19, 𝑓 ≤ 21,5, 𝑔 ≤ 30, dan ℎ ≤ 28 juga merupakan penyelesaian sistem. Kehadiran lebih dari satu elemen 1 pada tiap baris matriks 𝑅 mengindikasi bahwa kegiatan yang bersesuaian dengan kolom di mana elemen-
83
elemen bernilai 1 itu ada selesai dalam waktu bersamaan. Namun demikian, karena kegiatan loading dilakukan setelah kegiatan unloading selesai maka dipilih 𝑔 = 30 dan ℎ = 28. Penyelesaian sistem menjadi 𝒕 = [𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 30,28]𝑇 3.5 Matriks atas Aljabar Max-Plus dan Teori Graf Dalam subbab ini diberikan pengantar singkat teori graf, dan interpretasi beberapa operasi dan konsep dasar aljabar max-plus dalam teori graf. Konsep ini akan menjadi dasar pembahasan pada sistem persamaan linear iteratif max-plus, nilai eigen max-plus dan vektor eigen max-plus. Suatu graf didefinisikan sebagai suatu pasangan (V, E) dengan V adalah suatu himpunan berhingga tak kosong yang anggotanya disebut titik (vertices) dan E adalah suatu himpunan pasangan (takterurut) titik-titik. Anggota E disebut rusuk (edges). Suatu graf berarah didefinisikan sebagai suatu pasangan (V, A) dengan V adalah suatu himpunan titik-titik dan A adalah suatu himpunan pasangan terurut titik-titik. Anggota A disebut busur (arc). Untuk busur (v, w) A, v disebut titik awal busur dan w disebut titik akhir busur. Suatu loop adalah busur (v, v) A. Jika suatu graf disajikan dalam gambar, titik digambarkan sebagai noktah yang diberi label dengan nama titik yang diwakilinya. Rusuk digambarkan sebagai kurva atau ruas garis yang menghubungkan noktah-noktah yang bersesuaian pada rusuk atau loop. Busur digambarkan sebagai kurva atau ruas garis berarah yang menghubungkan noktah-noktah yang bersesuaian dengan titik awal dan titik akhir busur, dengan tanda panah pada ujungnya yang menandakan arah busur. Contoh 3.5.1 Diperhatikan graf berarah yang direpresentasikan dalam Gambar 3.5.1 di bawah ini yang direpresantasikan graf berarah G1 = ( V1 , A1 ), dengan V1 = {1, 2, 3} dan
A1 = {(1, 1 ), (1, 2), ( 2, 1), ( 2, 3 ), ( 3, 1), ( 3, 3)}.
84
1
2
3
Gambar 3.5.1 Graf Berarah Contoh 3.5.1
Diberikan G = (V, A) adalah graf berarah dengan V = {1, 2, , ... , n }. Suatu lintasan dalam G adalah suatu barisan berhingga busur ( i1 , i2 ), ( i2 , i3 ), ... , ( il 1 , il ) dengan ( ik , ik 1 ) A untuk suatu l N dan k = 1, 2, ... , l 1 (Wilson, 1972). Lintasan ini direpresentasikan dengan i1 i2 ... il . Titik i1 disebut titik awal lintasan dan titik il disebut titik akhir lintasan. Untuk suatu lintasan , panjang lintasan didefinisikan sebagai banyak busur yang menyusun dan dinotasikan dengan l . Suatu lintasan disebut sirkuit jika titik awal dan titik akhirnya sama. Sirkuit elementer adalah sirkuit yang titik-titiknya muncul tidak lebih dari sekali, kecuali titik awal yang muncul tepat dua kali. 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. Contoh 3.5.2 Diperhatikan graf berarah dalam Contoh 3.5.1. Barisan busur (2, 1), (1, 1), (1, 2), (2, 3) merupakan suatu lintasan dalam G1 yang dapat direpresentasikan dengan 2
85
1 1 2 3. Busur ini mempunyai panjang 4 karena tersusun atas 4 busur. Lintasan 2 1 2 3 1 2 merupakan suatu sirkuit dengan panjang 5. Lintasan 1 2 3 1 merupakan suatu sirkuit elementer dengan panjang 3. Diperhatikan bahwa untuk setiap titik yang berbeda dalam graf berarah tersebut selalu terdapat suatu lintasan, sehingga graf berarah tersebut terhubung kuat. 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), dinotasikan dengan w(j, i). Dalam penyajiannya dengan gambar untuk graf berarah berbobot, busur diberi label dengan bobotnya. Dari pengertian graf berbobot ini, setiap matriks n A R n max bersesuaian dengan suatu graf berarah berbobot seperti diberikan dalam
definisi berikut. Definisi 3.5.3 (Graf Bobot (Precedence Graph), Schutter, 1996) n Diberikan A R n max . Graf bobot dari A adalah graf berarah berbobot G(A) =
(V, A) dengan V = {1, 2, ... , n} dan A = {(j, i) | w(i, j) = Aij }. Contoh 3.5.4 Diberikan
1 3 2 A = 2 4 . 0
Graf bobot dari A adalah graf berarah berbobot G(A) = (V, A) dengan V = {1, 2, 3} dan A = {(1, 1), (2, 1), (3, 1), (2, 2), (3, 2), (2, 3)} yang disajikan dalam Gambar 3.5.2 di bawah ini. Perhatikan sebaliknya bahwa untuk setiap graf berarah berbobot n G = (V, A) selalu dapat didefinisikan suatu matriks A R n max dengan
w( j ,i ) jika ( j ,i ) A Aij = jika ( j ,i ) A . Matriks A seperti ini disebut matriks bobot dari graf G(A). Jelas bahwa graf berarah berbobot tersebut merupakan graf bobot dari A. Terlihat bahwa graf berarah
86
berbobot dalam Gambar 3.5.2 di bawah ini bersesuaian dengan matriks A yang diberikan dalam Contoh 3.5.4. 3 1
2
1
4 -2
2
0
3 Gambar 3.5.2 Graf Berarah Berbobot Contoh 3.5.4
Diberikan graf berarah berbobot G = (V, A) dengan V = {1, 2, ... , n}. Bobot suatu lintasan = i1 i2 ... il didefinisikan sebagai jumlahan bobot busurbusur yang menyusun . Bobot lintasan dinotasikan dengan w . Untuk matriks n A R n max , bobot suatu lintasan lintasan = i1 i2 ... il dalam graf bobot
G(A) adalah
w =
Ai2 , i1 + Ai3 , i2 + ... + Ail , il 1 . Bobot rata-rata lintasan ,
dinotasikan dengan , didefinisikan sebagai
1 (dengan operasi pembagian l w
dan perkalian pada bilangan real). Contoh 3.5.5 Diperhatikan graf bobot G(A) dalam Contoh 3.5.4. Panjang suatu lintasan
= 2 3 2 1 1 adalah l = 4 . Bobot lintasan adalah w = w(3, 2) + w(2, 3) + w(1, 2) + w(1, 1)
= A32 + A23 + A12 + A11 = 0 + 4 + 3 + 1 = 8. Bobot rata-rata lintasan adalah =
1 1 w = ( 8 ) = 2. l 4
87
Berikut diberikan suatu interpertasi dalam teori graf untuk pangkat k matriks n n A R nxn max dalam aljabar max-plus. Diberikan A R max . Jika k N , maka unsur
k
ke-st dari matriks A adalah k
( A ) st = =
max
( As , ik 1 + ... + Ai2 , i1 + Ai1 , t )
max
( Ai1 , t + Ai2 , i1 + ... + As , ik 1 )
1 i1 , i2 ,ik 1 n
1 i1 , i2 ,ik 1 n
untuk setiap s, t. Karena ( Ai1 , t + Ai2 , i1 + ... + As , ik 1 ) adalah bobot lintasan dengan panjang k dengan t sebagai titik awal dan s sebagai titik akhirnya dalam G(A), maka k
( A ) st adalah bobot maksimum semua lintasan dalam G(A) dengan panjang k, dengan t sebagai titik awal dan s sebagai titik akhirnya. Jika tidak ada lintasan dengan panjang k dari t ke s, maka bobot maksimum didefinisikan sama dengan . Contoh 3.5.6 Diambil matriks A dalam Contoh 3.5.4. Bobot maksimum semua lintasan dalam G(A) dengan panjang k untuk setiap pasangan titik awal dan titik akhir lintasan k
dapat ditentukan dari unsur-unsur matriks A . Misalkan diperhatikan untuk k = 2, 3, 4 berikut: A
2
1 5 7 1 7 9 1 9 11 3 4 = 4 6 , A = 6 8 dan A = 8 8 . 2 4 4 6 6 8 2
Misalkan diperhatikan bahwa ( A )12 = 5 yang berarti bobot maksimum semua lintasan dalam G(A) dengan panjang 2, dengan 2 sebagai titik awal dan 1 sebagai titik akhirnya adalah 5. Hal ini karena ( A )12 = max(1+3, 3+2, 2+0) = max (3+1, 2
3+2, 0+(2)) = max(4, 5, 2). Situasi ini sesuai dalam G(A), dimana ada 3 lintasan dengan panjang 2, dengan 2 sebagai titik awal dan 1 sebagai titik akhirnya, yaitu: 2 1 1, 2 2 1 dan 2 3 1 yang berturut turut mempunyai bobot 4, 5 dan 2. Unsur ( A )31 = yang berarti tidak ada lintasan dengan panjang 3, dengan 3
4
1 sebagai titik awal dan 3 sebagai titik akhirnya. Karena ( A )33 = 8, hal ini berarti bobot maksimum semua sirkuit dalam G(A) dengan panjang 4, dengan 3 sebagai
88
titik awal dan titik akhirnya adalah 8, yang bersesuaian dengan sirkuit 3 2 3 2 3. Sekarang diperhatikan bobot rata-rata maksimum sirkuit elementer, dengan n maksimum diambil atas semua sirkuit elementer dalam graf. Diberikan A R n max
dengan graf bobotnya G (A) = (V, E ). Bobot maksimum dari semua sirkuit dengan panjang k dengan titik i sebagai titik awal dan titik akhir dalam G(A) dituliskan k
sebagai ( A ) ii . Maksimum dari bobot maksimum semua sirkuit dengan panjang k dengan titik i sebagai titik awal dan titik akhir dalam G(A) atas seluruh titik i n
adalah
(A
k
i 1
adalah
k
) ii yang dapat dituliskan sebagai trace ( A ) dan rata-ratanya
k 1 trace ( A ) . Kemudian diambil maksimum atas sirkuit dengan panjang k
k n, yaitu atas semua sirkuit elementer, diperoleh suatu rumus untuk bobot ratarata maksimum sirkuit elementer dalam G(A) (dinotasikan dengan max(A)), sebagai berikut: n
max(A) =
1 ( k 1 k
k
trace ( A ) ).
Suatu sirkuit dalam graf G disebut sirkuit kritis jika bobot rata-ratanya sama dengan bobot rata-rata maksimum sirkuit elementer dalam G. Suatu graf yang terdiri dari semua sirkuit kritis dari graf G disebut graf kritis dari G dan dinotasikan dengan Gc. Contoh 3.5.7
2 3 1 Diberikan A = 1 1 . Graf bobot G(A) dinyatakan dalam Gambar 3.5.3. 2 1 Akan ditentukan max(A), bobot rata-rata maksimum sirkuit elementer dalam G(A)
di atas. Diperhatikan bahwa: A
2
4 4 2 5 7 5 3 = 2 4 2 dan A = 5 5 3 . 3 3 2 4 6 4
89
1 2
1
1
3
2
2
1
3
1 Gambar 3.5.3 Graf Bobot Contoh 3.5.7 3
max(A) =
1 ( k 1
1 1 1 1 k trace ( A ) ) = max( (1), (4), (5) ) = (4) = 2. k 2 3 2 1
Sirkuit kritis dalam G(A) di atas adalah sirkuit 1 2 1 dan 2 1 2, sehingga graf kritis Gc(A) dapat disajikan dalam Gambar 3.5.4 berikut. 1
1
3
2
Gambar 3.5.4 Graf Kritis Contoh 3.5.7
Teorema 3.5.8 (Baccelli, et.al., 2001) Diberikan A R nxn max . Jika semua sirkuit dalam G(A) mempunyai bobot takpositif, maka
p n , A
p
m
E A ... A
n 1
.
Bukti: Karena banyak titik dalam G(A) adalah n maka semua lintasan dengan panjang p n tersusun dari k sirkuit dengan jumlah panjang seluruh sirkuit kurang dari p dan
90
satu lintasan dengan panjang kurang dari n. Hal ini berarti untuk setiap p n dan p
untuk setiap s, t {1, 2, ..., n}, , terdapat r {1, 2, ..., n} sehingga ( A )st = l
( A )st +
k
( A
mi
)ri , ri dengan 0 l n1, 1 mi n , 1 ri n dan k = 1, 2, 3,
i
... . Karena semua sirkuit mempunyai bobot nonpositif maka untuk setiap p n dan untuk setiap s, t {1, 2, ..., n} berlaku Akibatnya
A
p
m
p
A ... A
n 1
Karena untuk setiap A R nxn max berlaku E A A
p
m
l
( A )st ( A )st dengan 0 l n1. , p n.
m A, maka
E A ... A
n 1
, p n.
■
Berdasarkan Teorema 3.5.8 di atas didefinisikan operasi bintang () untuk matriks berikut ini. Definisi 3.5.9 nxn Diberikan A R max dengan semua sirkuit dalam G(A) berbobot takpositif.
Didefinisikan dan
n
A* : = E A ... A A
n 1
...
A+ : = A A*.
Berikut diberikan definisi untuk istilah lain matriks yang sirkuit dalam G(A) mempunyai bobot takpositif dan negatif. Istilah ini akan digunakan dalam masalah penyelesaian sistem persamaan linear iteratif max-plus pada pembahasan subbab berikutnya. Definisi 3.5.10 n n Suatu matriks A R max dikatakan semi-definit jika semua sirkuit dalam G(A)
mempunyai bobot takpositif dan dikatakan definit jika semua sirkuit dalam G(A) mempunyai bobot negatif.
91
Berikut ini list program MATLAB untuk menghitung matriks A+ dan A* . % % % %
Program Matlab Menghitung A+ dan A* Oleh: M. Andy Rudhito FKIP Universitas Sanata Dharma input: A = matriks batas bawah dan atas max-plus Anxn output: Matriks A+ dan A*
A1 = input(' Masukkan matriks Anxn = '); A1 [m, n]= size(A1); % Menghitung A pangkat dan A+ G1=A1; A1_plus = A1; for s=1:100 s+1; for i = 1: m for j = 1: n F1(i, j) = -Inf; for p = 1: n F1(i, j) = max( F1(i, j) , A1(i, p) + G1(p, j) ); end; end; end; G1 = F1; F1; A1_plus = max(A1_plus, F1); end; disp(' Matriks A+ '), disp(A1_plus) % Menghitung matriks E dan A* for i = 1 : n for j = 1 : n if i ~= j E(i,j) = -Inf; end; end; end; A1_star= max(E, A1_plus); disp(' Matriks A* '), disp(A1_star)
Gambar 3.5.5 List Program MATLAB untuk Menghitung Matriks A+ dan A*.
Berikut diberikan beberapa contoh matriks dan hasil perhitunganya dengan program di atas. Contoh 3.5.11. Diperhatikan matriks A seperti pada Contoh 3.5.7 di atas. Hasil perhitungan sebagai berikut, dengan mengambil pangkat tertinggi 100. Masukkan matriks Anxn = [-2 3 1; 1 1 -Inf;-Inf 2 1]
92
A1 = -2 1 -Inf
3 1 2
1 -Inf 1
Matriks A+ 201 203 201 201 201 199 200 202 200 Matriks A* 201 203 201 201 201 199 200 202 200
Nampak bahwa hasil perhitungan akan membesar dan tidak akan konvergen. Hal ini nampak juga sesuai dengan G(A) di mana terdapat sirkuit dengan bobot positif.
Contoh 3.5.12. Dari G(A) pada Contoh 3.5.7 jika sedikit dimodifikasi bobot busurnya, sedemikian hingga semua bobot sirkuitnya berbobot nonnegatif dan diperoleh matriks bobot A
2 3 1 A = 1 1 . 2 1
berikut,
Dengan program di atas diperoleh hasil perhitungan berikut. Masukkan matriks Anxn = [-2 -3 1;1 0 -Inf;-Inf -2 0] A1 = -2 1 -Inf
-3 0 -2
1 -Inf 0
Matriks A+ 0 -1 1 0 -1 -2
1 2 0
Matriks A* 0 -1 1 0 -1 -2
1 2 0
93
Nampak bahwa dengan perhitungan sampai pangkat sampai ke-100, matriks tidak membesar melainkan konvergen. Contoh 3.5.13. 5 Diberikan matriks A = 9 10 6 7 8
. Nampak bahwa graf bobot matrik tersebut
tidak memuat sirkuit atau semua sirkuitnya berbobot , sehingga matriks tersebut juga merupakan matriks definit. Dengan program di atas diperoleh hasil perhitungan berikut. Masukkan matriks Anxn = [-Inf -Inf -Inf -Inf;5 -Inf -Inf -Inf; 9 10 -Inf -Inf; 6 7 8 -Inf] A1 = -Inf 5 9 6
-Inf -Inf 10 7
-Inf -Inf -Inf 8
-Inf -Inf -Inf -Inf
Matriks A+ -Inf -Inf -Inf 5 -Inf -Inf 15 10 -Inf 23 18 8
-Inf -Inf -Inf -Inf
Matriks A* 0 -Inf -Inf 5 0 -Inf 15 10 0 23 18 8
-Inf -Inf -Inf 0
Nampak bahwa dengan perhitungan sampai pangkat sampai ke-100, matriks tidak membesar melainkan konvergen. 3.6 Sistem Persamaan Linear Iteratif (SPLI) Max-Plus Sistem persamaan linear iteratif (SPLI) Max-Plus mempunyai bentuk umum n nxn x = A x b , dengan x, b R max dan A R max . Untuk sistem tersebut, dengan
subsitusi berulang diperoleh:
94
2
x = A (A x b ) b = A x A b b
substitusi ke-1 :
2
= A x (A E) b. 3
2
n
n 1
substitusi ke-2 :
x = A x ( A A E) b.
substitusi ke-n :
x = A x ( A
... A E) b.
n
Dengan demikian jika A* : = E A ... A A
n 1
... ada, maka x =
A* b merupakan penyelesaian sistem di atas. Hal ini karena A (A* b) b = (E A A*) b = A* b. Dari uraian di atas dan menurut Teorema 3.5.8 diperoleh teorema berikut. Teorema 3.6.1 (Baccelli, dkk., 2001) Jika A semi-definit, maka x* = A* b merupakan suatu penyelesaian sistem persamaan linear iteratif max-plus x = A x b. Lebih lanjut jika A definit, maka sistem persamaan linear tersebut mempunyai penyelesaian tunggal. Bukti: Dari uraian di atas nampak bahwa x* = A* b merupakan penyelesaian sistem. Andaikan A definit. Dari proses substitusi di atas pada substitusi ke-n diperoleh n
x = A x ( A n
= (A
n 1
... A E) b
n 1
x)(
( A
k
b)).
i 0
Dengan mengambil k diperoleh lim (( n
n
A
n 1
x)(
( A
k
b)))
i 0
n
= lim (( A n
n
= lim (( A n
n 1
x ) lim ( n
( A
n
b))
i 0
n 1
x ) lim
k
( A i 0
k
) b.
95
Mengingat A definit, yaitu semua sirkuitnya berbobot negatif, maka jika n maka A
n
n ij
lim (( n
, sehingga lim (( A n
n
A
n 1
x ) lim n
( A
k
x ) = . Jadi selanjutnya diperoleh
) b = A* b. Dengan demikan x* = A*
i 0
b merupakan penyelesaian tunggal sistem di atas.
■
Selanjutnya SPLI Max-Plus yang dibahas dengan matriks koefisien yang definit. Berikut diberikan list program MATLAB untuk menyelesaikan SPLI MaxPlus . % % % %
Program Matlab Menyelesaikan pers iterative x=Ax+b Oleh: M. Andy Rudhito FKIP Universitas Sanata Dharma input: A1 = matriks Anxn, B = matriks b kolom nx1 output: Penyelesaian minimal sistem x=A*b
A1 = input(‘ Masukkan matriks Anxn = ‘); B1 = input(‘ Masukkan matriks Bnx1 = ‘); A1 B1 [m, n]= size(A1); [k, r]= size(B1); % Menghitung A pangkat dan A+ G1=A1; A1_plus = A1; for s=1:n-1 s+1; for i = 1: m for j = 1: n F1(i, j) = -Inf; for p = 1: n F1(i, j) = max( F1(i, j) , A1(i, p) + G1(p, j) ); end; end; end; G1 = F1; F1 ; A1_plus = max(A1_plus, F1) ; end; disp(‘ Matriks A_plus ‘), disp(A1_plus); % Menghitung matriks E dan A* for i = 1 : n for j = 1 : n if i ~= j E(i,j) = -Inf; end; end;
96
end; A1_star= max(E, A1_plus); % Menampilkan hasil A pangkat disp(‘ Matriks A_star ‘), disp(A1_star); % Menghitung A_star kali B for i = 1:m for j = 1: r A1_starB1(i, j) = -Inf; for p = 1: n A1_starB1(i, j) = max(A1_starB1(i, j) , A1_star(i, p) + B1(p, j)); end; end; end; % Menampilkan hasil kali disp(‘ Penyelesaian minimal x’),disp(A1_starB1)
Gambar 3.6.1 List Program MATLAB Penyelesaian SPLI Max-Plus
Contoh 3.6.2 Berikut diberikan contoh hasil perhitungan penyelesaian SPLI Max-Plus dengan matriks A definit dan b yang dientrikan berikut ini. Masukkan matriks Masukkan matriks
Amxn = Bnx1 =
A1 = -3 -1 -Inf
1 -2 0
1 -Inf -1
B1 = -1 0 2 Matriks A_plus 0 1 1 -1 0 0 -1 0 0 Matriks A_star 0 1 1 -1 0 0
[-3 1 1;-1 -2 -Inf;-Inf 0 -1] [-1;0;2]
97
-1
0
0
Penyelesaian minimal x 3 2 2
Contoh 3.6.3 Berikut diberikan contoh hasil perhitungan penyelesaian SPLI Max-Plus dengan matriks A definit di mana graf bobotnya tidak memuat sirkuit. dan b yang dientrikan berikut ini. Masukkan matriks Anxn = [-Inf -Inf -Inf -Inf;5 -Inf -Inf -Inf; 9 10 -Inf -Inf; 6 7 8 -Inf] Masukkan matriks Bnx1 = [0;-1;1;-Inf] A1 = -Inf 5 9 6
-Inf -Inf 10 7
-Inf -Inf -Inf 8
-Inf -Inf -Inf -Inf
B1 = 0 -1 1 -Inf Matriks A_plus -Inf 5 15 23
-Inf -Inf 10 18
-Inf -Inf -Inf 8
-Inf -Inf -Inf -Inf
Matriks A_star 0 5 15 23
-Inf 0 10 18
-Inf -Inf 0 8
-Inf -Inf -Inf 0
Penyelesaian minimal x 0 5 15 23
98
3.7 Penerapan SPLI Max-Plus pada Penjadwalan Proyek Dalam subbab 1.1 telah diberikan gambaran pemodelan masalah penjadwalan dengan pendekatan aljabar max-plus. Dalam subbab ini akan dibahas lebih lanjut penerapan aljabar max-plus untuk pemodelan dinamika jaringan proyek (project network) dengan waktu aktifitas tegas dan masalah penjadwalan di dalamnya. Masalah penjadwalan meliputi penentuan saat-mulai paling awal setiap titik pada jaringan, waktu minimal penyelesaian proyek, saat penyelesaian paling lambat setiap titik pada jaringan, waktu mengambang setiap titik pada jaringan dan penentuan lintasan kritis. Suatu proyek mendefinisikan satu kombinasi kegiatan-kegiatan yang saling berkaitan yang harus dilakukan dalam urutan tertentu sebelum keseluruhan tugas dapat diselesaikan. Kegiatan-kegiatan ini saling berkaitan dalam satu urutan kegiatan yang logis dalam arti bahwa beberapa kegiatan tidak dapat dimulai sampai kegiatan-kegiatan lainnya diselesaikan (Taha, 1996). Hubungan ketergantungan dan urutan di antara kegiatan-kegiatan dalam proyek dapat dinyatakan dalam suatu graf berarah yang disebut juga dengan graf berarah aktifitas (activity digraph) (Chartrand & Oellermann, 1993). Aturan-aturan pengembangkan diagram panah (graf berarah di atas) dapat dilihat pada (Taha, 1996). Jaringan Proyek secara matematis dapat dinyatakan dalam definisi berikut. Definisi 3.7.1 (Chanas & Zielinski, 2001) Suatu jaringan proyek S adalah suatu graf berarah berbobot terhubung kuat taksiklik S = (V, A), dengan V = {1, 2, , ..., n} yang memenuhi: jika (i, j) A, maka i < j. Dalam jaringan proyek ini, busur menyatakan suatu aktifitas, sedangkan bobot busur menyatakan waktu aktifitas, sehingga bobot dalam jaringan selalu positip. Selanjutnya dilakukan pemodelan dan analisis lintasan kritis. Pembahasan diawali dengan menentukan saat-mulai paling awal (earliest start time) untuk setiap aktifitas yang berasal dari titik i. Pembahasan dilakukan dengan mengadopsi teknik perhitungan maju (forward) seperti pada PERT-CPM, dengan menggunakan pendekatan aljabar-max-plus. Jaringan proyek seperti di atas sering juga disebut
99
jaringan PERT (PERT network), yaitu suatu graf berarah yang digunakan untuk menyatakan interaksi antara kegiatan-kegiatan individual dalam suatu proyek komplek keseluruhan. Busur bersesuaian dengan aktifitas dan titik–titik akhirnya dipilih sedemikian hingga memenuhi kendala urutan di mana aktifitas dapat dilakukan (Busacker & Saaty, 1965). e
Misalkan ESi = xi menyatakan saat-mulai paling awal yang berasal dari titik i ,
waktu aktifitas dari titik j ke titik i jika ( j , i ) A . Aij = jika ( j , i ) A ( ) Dalam pembahasan ini diasumsikan bahwa aktifitas jaringan dimulai pada titik 1 e pada saat waktu sama dengan nol, yaitu x1 = 0, sehingga dapat dituliskan
jika i 1 0 xie = max ( A x e ) jika i 1 . j 1 j n ij Dengan menggunakan notasi aljabar max-plus persamaan di atas dapat dituliskan menjadi xie =
jika i 1
0
1 j n
( Aij x ) jika i 1 . e j
(3.7.1)
Selanjutnya diperoleh hasil dalam Teorema 3.7.2 berikut. Teorema 3.7.2 Jika suatu jaringan proyek dengan n titik, maka vektor saat-mulai paling awal yang berasal dari titik i pada jaringan tersebut diberikan oleh xe = (E A ... A n 1 ) be di mana A adalah matriks bobot dari graf berarah berbobot jaringan tersebut dan vektor be = [0, , ... , ]T. Lebih lanjut, waktu minimal penyelesaian proyek adalah
xne . Bukti: Misalkan A adalah matriks bobot graf S , yaitu graf berarah berbobot e e e jaringan tersebut, xe = [ x1 , x2 , ... , xn ]T dan be = [0, , ... , ]T, persamaan (3.7.1)
dapat dituliskan ke dalam suatu sistem persamaan linear iteratif max-plus berikut xe = A xe be
(3.7.2)
100
Mengingat jaringan proyek merupakan graf berarah taksiklik, maka tidak terdapat sirkuit, sehingga semua sirkuit dalam jaringan mempunyai bobot takpositif, yang berarti matriks A definit. Dengan demikian menurut Teorema 3.6.1, xe = A* be
(3.7.3)
merupakan penyelesaian tunggal sistem (3.7.2) di atas. Mengingat jumlah titik dalam jaringan proyek ini adalah n, maka panjang lintasan terpanjang jaringan tidak akan melebihi n 1. Dengan demikian dalam hal ini persamaan (3.7.3) dapat ditulis xe = A* be = (E A ... A n 1 ) be
menjadi
yang merupakan vektor saat-mulai paling awal yang berasal dari titik i. Perhatikan bahwa ( A* ) n1 merupakan bobot maksimum lintasan dari titik awal e hingga titik akhir proyek, sehingga xn merupakan waktu minimal penyelesaian
proyek.
■
Dari pemodelan dinamika jaringan proyek di atas nampak bahwa dengan pendekatan aljabar max-plus dapat diperoleh suatu model yang padu dan menyatu dalam suatu sistem persamaan linear max-plus iteratif. Selanjutnya dibahas penentuan saat-penyelesaian paling lambat (latest completion time) untuk semua kegiatan yang datang ke titik i. Pembahasan dilakukan dengan mengadopsi teknik perhitungan mundur (backward) seperti pada PERT-CPM, dengan menggunakan pendekatan aljabar-max-plus, sehingga diperoleh Teorema 3.7.3 berikut. Teorema 3.7.3 Jika suatu jaringan proyek dengan waktu aktifitas tegas mempunyai n titik, maka vektor saat-penyelesaian paling lambat untuk semua kegiatan yang datang ke titik i diberikan oleh xl = ( (AT )* bl ) di mana A adalah matriks bobot dari graf berarah berbobot jaringan tersebut dan vektor bl = [, , ... , xn ]T. e
l Bukti: Misalkan LCi = xi menyatakan saat-penyelesaian paling lambat untuk
semua kegiatan yang datang ke titik i,
101
waktu aktifitas dari titik i ke titik j jika ( j,i) A . Bij = jika ( j, i) A ( ) l e Diasumsikan bahwa xn = xn , kemudian dapat dituliskan
xne jika i n x = . ( Bij x lj ) jika i n 1min jn l i
(3.7.4)
Dengan menggunakan notasi aljabar max-plus persamaan (3.7.4) ekivalen dengan e jika i n xn x = . l max ( Bij x j ) jika i n 1 j n
l i
(3.7.5)
Perhatikan bahwa matriks B = AT, dengan A matriks bobot graf berarah berbobot jaringan tersebut. Misalkan z = [ z1 , z2 , ... , zn ]T = xl = [ x1l , x2l , ... ,
T
xnl ]
dan
bl = [, , ... , xn ]T, persamaan (3.7.5) dapat dituliskan menjadi e
z = AT z bl .
(3.7.6)
yang, menurut Teorema 3.6.1, penyelesaiannya adalah z = (AT )* bl . Dengan demikian diperoleh vektor saat paling lambat adalah xl = z.
■
Seperti halnya yang telah dikenal dalam Riset Operasi, berikut dibahas mengenai mengenai waktu senggang atau waktu mengambang. Ada dua jenis waktu mengambang yang biasa dibicarakan, yaitu waktu mengambang total (total float time) dan waktu mengambang bebas (free float time). Sebelumnya didefinisikan saat-mulai paling lambat (latest start (LS) time) dan saat-penyelesaian paling cepat (earliest completion (EC) time) untuk setiap aktifitas (i, j) dalam jaringan dengan LSij = LC j A ji dan ECij = ESi + A ji .
Waktu mengambang total adalah besarnya tenggang waktu yang masih dimungkinkan untuk terjadi keterlambatan selesainya aktifitas tersebut, tanpa mempengaruhi waktu minimal penyelesaian proyek. Secara matematis waktu mengambang total untuk aktifitas (i, j) A, yang dilambangkan dengan TFij didefinisikan sebagai selisih antara waktu maksimum yang tersedia untuk melakukan aktifitas tersebut dengan waktu aktifitasnya, yaitu
102
e TFij = ( LC j ESi ) A ji = ( x lj xi ) A ji .
Jika dituliskan dalam bentuk matriks akan diperoleh matriks waktu mengambang TF = LJ EI AT
total
dengan LJ adalah matriks dengan semua kolomnya adalah vektor xl dan EI adalah matriks dengan semua barisnya adalah vektor baris (xe)T. Waktu mengambang bebas adalah besarnya tenggang waktu yang masih dimungkinkan
pada
suatu
aktifitas
untuk
dilakukan
penundaan
tanpa
mempengaruhi saat dimulainya aktifitas berikutnya. Secara matematis waktu mengambang bebas untuk aktifitas (i, j) A, yang dilambangkan dengan FFij , dengan mengasumsikan semua kegiatan dimulai sedini mungkin, didefinisikan sebagai kelebihan waktu yang tersedia di sepanjang aktifitasnya, yaitu e FFij = ( ES j ESi ) A ji = ( x ej xi ) A ji .
Jika dituliskan dalam bentuk matriks akan diperoleh matriks waktu ambang FF = EJ EI AT dengan EJ adalah matriks dengan semua kolomnya adalah vektor xe dan EI adalah matriks dengan semua barisnya adalah vektor baris (xe)T. Selanjutnya diperhatikan aktifitas (i, j) A dengan waktu mengambang totalnya TFij = 0, hal ini berarti waktu maksimum yang tersedia untuk melakukan aktifitas tersebut sama dengan waktu aktifitasnya. Dengan kata lain tidak ada waktu senggang antara saat-mulai paling cepat dan saat-mulai paling lambat penyelesaian aktifitas tersebut. Aktifitas seperti ini dikatakan sebagai aktifitas kritis seperti diberikan dalam Definisi 3.7.4 berikut. Misalkan P adalah himpunan semua lintasan di dalam S dari titik 1 ke titik n. Definisi 3.7.4 (Chanas & Zielinski, 2001) Suatu aktifitas (i, j) A dalam jaringan proyek S disebut aktifitas kritis jika TFij = 0. Definisi 3.7.5 (Chanas & Zielinski, 2001) Suatu lintasan p P dalam jaringan proyek S disebut lintasan kritis jika semua aktifitas yang terletak dalam p merupakan aktifitas kritis.
103
Dari Definisi 3.7.4 dan 3.7.5 di atas dapat diperoleh Teorema 3.7.6 berikut (Chanas & Zielinski, 2001). Teorema 3.7.6 Suatu lintasan p P merupakan lintasan kritis jika dan hanya jika e p mempunyai bobot maksimum, yaitu sama dengan xn .
Bukti: ( ) Akan dibuktikan kontraposisinya. Jika bobot suatu lintasan pP tidak maksimum, maka ada lintasan selain p, yaitu p P yang bobotnya lebih besar dari bobot lintasan p. Hal ini berakibat terdapat suatu aktifitas (i, j) p, sedemikian hingga TFij 0, yang berarti tidak semua aktifitas pada lintasan p merupakan aktifitas kritis. Jadi menurut Definisi 3.7.5, lintasan p tersebut bukan merupakan lintasan kritis. () Akan dibuktikan kontraposisinya. Jika lintasan p P bukan merupakan lintasan kritis, maka menurut Definisi 3.7.5, ada suatu aktifitas (i, j) p, sedemikian hingga TFij 0. Hal ini berarti waktu maksimum yang tersedia untuk melakukan aktifitas tersebut lebih besar dari pada waktu aktifitasnya, yang berarti bobot lintasan p tersebut bukan merupakan lintasan maksimum.
■
Berikut diberikan contoh suatu jaringan proyek dan perhitungannya. Contoh 3.7.8 Perhatikan jaringan proyek seperti yang diberikan pada Gambar 3.7.1 (Taha, 1996, pp. 81) : 5 2 3
6
1 3 2
5
7
3
2 2
6
3 4
Gambar 3.7.1 Jaringan Proyek
2
7
104
Matriks bobot graf berarah berbobot pada jaringan proyek di atas adalah matriks
2 3 A =
2 3 2 0 3 7 2 5
. 6
Dengan menggunakan bantuan program yang disusun dengan menggunakan MATLAB, yang list programnya pada Gambar 3.7.2 di bawah ini, dengan input matriks A di atas, diperoleh output program sebagai berikut.
0 2 0 3 A* = 6 2 6 2 13 9 19 15
0 3 3 10 16
0 7 13
7 13
6
, xe =
0 0 2 4 3 3 l 6 dan x = 6 . Hasil perhitungan 6 6 13 13 19 19
selengkapnya seperti dalam Tabel 3.7.1 berikut. Tabel 3.7.1 Tabel Waktu Hasil Analisis Lintasan Kritis Contoh 3.7.8 No 1 2 3 4 5 6 7 8 9 10 11
(i, j) (1, 2) (1, 3) (2, 4) (3, 4) (3, 5) (4, 5) (4, 6) (4, 7) (5, 6) (5, 7) (6, 7)
Aji 2 3 2 3 2 0 3 2 7 5 6
ESi 0 0 2 3 3 6 6 6 6 6 13
ECij 2 3 4 6 5 6 9 8 13 11 19
LSij 2 0 4 3 4 6 10 17 6 14 13
LCj 4 3 6 6 6 6 13 19 13 19 19
TFij 2 0 2 0 1 0 4 11 0 8 0
FFij 0 0 2 0 1 0 4 11 0 8 0
Dari hasil di atas diperoleh lintasan kritis: (1, 3), (3, 4), (4, 5), (5, 6), (6, 7). Hasil yang diperoleh di atas sesuai dengan hasil yang diperoleh dalam Taha (1996).
105
% Program Matlab Menghitung saat-mulai paling awal, saat-mulai paling lambat dan waktu mengambang dengan menggunakan aljabar max-plus % Oleh: M. Andy Rudhito FKIP Universitas Sanata Dharma % input: A = matriks max-plus Anxn, (matriks yang bersesuaian dengan graf proyek) % output: Tabel meliputi saat-mulai paling awal, saat-mulai paling lambat, waktu mengambang, dan waktu aktifitas kritis. % Memasukkan matriks yang bersesuaian: A = input(' Masukkan matriks A = '); disp(' HASIL PERHITUNGAN :') disp(' ===================') disp(' Matriks A = '),disp(A) [m, n]= size(A); %MENGHITUNG MAJU % Menghitung A pangkat dan A+ G=A; A_plus = A; for s=1:n-1 s+1; for i = 1: m for j = 1: n F(i, j) = -Inf; for p = 1: n F(i, j) = max( F(i, j) , A(i, p) + G(p, j) ); end; end; end; G = F; A_plus = max(A_plus, F); end; % Menghitung matriks E dan A* for i = 1 : n for j = 1 : n if i ~= j E(i,j) = -Inf; end; end; end; A_star= max(E, A_plus) % Membuat matriks B for i = 1 : n for j = 1 : 1 if i ~= 1 B(i,j) = -Inf; else B(i,j)=0; end; end; end;
106
% Menghitung vektor saat-mulai paling awal ESi = A_star kali B [k, r]= size(B); for i = 1:m for j = 1: r A_starB(i, j) = -Inf; for p = 1: n A_starB(i, j) = max(A_starB(i, j) , A_star(i, p) + B(p, j)); end; end; end; ESi=A_starB % Membuat matriks saat-mulai paling awal MESi for i = 1:n for j = 1:n if A(i,j)~=-Inf MESi(i,j)= ESi(j,1); else MESi(i,j)=-Inf; end end end % Membuat matriks saat-mulai paling awal MESj for i = 1:n for j = 1:n if A(i,j)~=-Inf MESj(i,j)= ESi(i,1); else MESj(i,j)=-Inf; end end end % Membuat matriks saat penyelesaian paling cepat MECij for i = 1:n for j = 1:n MEC(i,j)= MESi(i,j)+A(i,j); end end %MENGHITUNG MUNDUR % Menghitung A2 pangkat dan A2+ A2=A'; G2=A2; A2_plus = A2; for s=1:n-1 s+1; for i = 1: m for j = 1: n F2(i, j) = -Inf; for p = 1: n F2(i, j) = max( F2(i, j) , A2(i, p) + G2(p, j) ); end;
107
end; end; G2 = F2; A2_plus = max(A2_plus, F2); end; % Menghitung matriks E2 dan A2* for i = 1 : n for j = 1 : n if i ~= j E2(i,j) = -Inf; end; end; end; A2_star= max(E2, A2_plus); % Membuat matriks B2 for i = 1 : n for j = 1 : 1 if i ~= n B2(i,j)= -Inf; else B2(i,j) = -A_starB(n,1); end; end; end; [k, r]= size(B2); % Menghitung vektor saat penyelesaian paling lambat LCj = A2_star kali B2 for i = 1:m for j = 1: r A2_starB2(i, j) = -Inf; for p = 1: n A2_starB2(i, j) = max(A2_starB2(i, j) , A2_star(i, p) + B2(p, j)); end; end; end; LCj = -A2_starB2 % Membuat matriks saat penyelesaian paling lambat MLCj for i = 1:n for j = 1:n if A(i,j)~=-Inf MLCj(i,j)= LCj(i,1); else MLCj(i,j)=-Inf; end end end % Membuat matriks saat penyelesaian paling lambat MLCi for i = 1:n for j = 1:n if A(i,j)~=-Inf
108
MLCi(i,j)= LCj(j,1); else MLCi(i,j)=-Inf; end end end % Membuat matriks saat penyelesaian paling lambat MLS for i = 1:n for j = 1:n if MLCj(i,j)~=-Inf MLS(i,j)= MLCj(i,j)-A(i,j); else MLS(i,j)=-Inf; end end end %Membuat Matriks utk Menghitung ESj-ESi (MESji)dan LCj-LCi (MLCji) MESji=MESj-MESi; MLCji=MLCj-MLCi; % Menampilkan Tabel WAKTU MENGAMBANG ta0 =zeros(n*n, 9); ta1 =zeros(n*n, 9); ta2 =zeros(n*n, 9); ta3 =zeros(n*n, 9); ta4 =zeros(n*n, 9); ta5 =zeros(n*n, 9); ta6 =zeros(n*n, 9); ta7 =zeros(n*n, 9); ta8 =zeros(n*n, 9); Ck0=zeros(n); for i=1:n for j=1:n Ek0(i,j)=j; Fk0(i,j)=i; end; end; Tk0=(Ek0(1:n*n))'; Tk1=(Fk0(1:n*n))'; Tk2=(A(1:n*n))'; Tk3=(MESi(1:n*n))'; Tk4=(MESj(1:n*n))'; Tk5=(MLCi(1:n*n))'; Tk6=(MLCj(1:n*n))'; Tk7=(MESji(1:n*n))'; Tk8=(MLCji(1:n*n))'; ta0(:,1)= Tk0; ta1(:,2)= Tk1; ta2(:,3)= Tk2; ta3(:,4)= Tk3; ta4(:,5)= Tk4; ta5(:,6)= Tk5; ta6(:,7)= Tk6; ta7(:,8)= Tk7;
109
ta8(:,9)= Tk8; ta=ta0+ta1+ta2+ta3+ta4+ta5+ta6+ta7+ta8; for k=n*n:-1:1 if ta(k,3)==-Inf ta(k,:)=[]; end end %MENGHITUNG WAKTU MENGAMBANG % Membuat vektor waktu mengambang total titik VSi VSi=(LCj)-(ESi); % Membuat Matriks Slack Total aktifitas MTF for i = 1:n for j = 1:n if MLS(i,j)~=-Inf MTF(i,j)= MLS(i,j)-MESi(i,j); else MTF(i,j)=-Inf; end end end % Membuat waktu mengambang bebas MFF for i = 1:n for j = 1:n if A(i,j)~=-Inf MFF(i,j)= MESj(i,j)- MESi(i,j)-A(i,j); else MFF(i,j)=-Inf; end end end % Menampilkan Tabel WAKTU MENGAMBANG tab0 =zeros(n*n, 9); tab1 =zeros(n*n, 9); tab2 =zeros(n*n, 9); tab3 =zeros(n*n, 9); tab4 =zeros(n*n, 9); tab5 =zeros(n*n, 9); tab6 =zeros(n*n, 9); tab7 =zeros(n*n, 9); tab8 =zeros(n*n, 9); C0=zeros(n); for i=1:n for j=1:n E0(i,j)=j; F0(i,j)=i; end; end; T0=(E0(1:n*n))'; T1=(F0(1:n*n))'; T2=(A(1:n*n))'; T3=(MESi(1:n*n))'; T4=(MEC(1:n*n))'; T5=(MLS(1:n*n))';
110
T6=(MLCj(1:n*n))'; T7=(MTF(1:n*n))'; T8=(MFF(1:n*n))'; tab0(:,1)= T0; tab1(:,2)= T1; tab2(:,3)= T2; tab3(:,4)= T3; tab4(:,5)= T4; tab5(:,6)= T5; tab6(:,7)= T6; tab7(:,8)= T7; tab8(:,9)= T8; tab=tab0+tab1+tab2+tab3+tab4+tab5+tab6+tab7+tab8; disp('TABEL WAKTU AKTIFITAS DAN WAKTU MENGAMBANG:') for k=n*n:-1:1 if tab(k,3)==-Inf tab(k,:)=[]; end end tab1=tab; disp(' i j Aji ESi ECij LSij LCj TFij FFij '),disp(tab1); %Menentukan Aktifitas Kritis [kta, ktb]=size(tab1); for k=kta:-1:1 if tab1(k,8)~=0 tab1(k,:)=[]; end end disp(' AKTIFITAS KRITIS :') disp(' i j Aji ESi '),disp(tab1);
ECij
LSij
LCj
TFij
Gambar 3.7.2 List Program MATLAB Menentukan Lintasan Kritis
FFij
BAB 4 NILAI EIGEN DAN VEKTOR MAX-PLUS SERTA PENERAPANNYA
Dalam bab ini dibahas nilai eigen dan vektor eigen max-plus yang merupakan salah satu alat untuk menganalisa sifat periodik pemodelan masalah real dengan pendekatan aljabar max-plus. Akan dibahas eksistensi dan ketunggalan nilai eigen max-plus dan juga beberapa contoh penerapannya. 4.1 Nilai Eigen dan Vektor Eigen Max-Plus Terlebih dulu akan dibahas kembali konsep aljabar max-plus dan graf, terutama yang terkait dengan pembahasan nilai eigen dan vektor eigen max-plus. Berikut didefinisikan suatu matriks yang graf bobotnya terhubung kuat. Definisi 4.1.1 (Irredusibilitas, Schutter,1996) Suatu matriks A R nxn max dikatakan irredusibel jika graf bobotnya terhubung kuat. Teorema berikut memberikan syarat perlu dan cukup matriks irredusibel. Teorema 4.1.2 2
Matriks A R nxn ... A max irredusibel jika dan hanya jika (A A
n 1
) ij
untuk setiap i, j dengan i j. Bukti: () Jika A irredusibel maka G(A) = (V, A) dengan V = {1, 2, , ... , n} terhubung kuat, yaitu untuk setiap i, j V , i j , terdapat suatu lintasan dari i ke j . Hal ini berarti untuk setiap i, j V, i j terdapat k dengan 1 k n1 sehingga k
2
( A ) ij . Akibatnya (A A ... A
n 1
) ij untuk setiap i, j dengan
i j. 2
() Jika (A A ... A
n 1
) ij untuk setiap i, j dengan i j, maka k
terdapat k dengan 1 k n1 sehingga ( A ) ij . Hal ini berarti dalam graf bobot G(A) = (V, A) dengan V = {1, 2, , ... , n}, untuk setiap i, j V , i j
111
112
terdapat suatu lintasan dari i ke j. Akibatnya G(A) terhubung kuat, yang berarti bahwa A irredusibel.
■
Contoh 4.1.3 Diperhatikan matriks A dalam Contoh 3.5.7. Matriks A tersebut irredusibel, karena A A
2
2 3 1 = 1 1 2 1
4 4 2 2 4 2 = 3 3 2
4 4 2 2 4 2 , berarti (A A 2 ) ij 3 3 2
untuk setiap i j. Dalam graf pada Gambar 3.5.3 terlihat bahwa untuk sebarang dua titik yang berbeda i dan j dalam G(A) terdapat suatu lintasan dari i ke j. Sedangkan matriks A dalam Contoh 3.5.4 tidak irredusibel, karena A A
2
1 3 2 1 5 7 = 2 4 4 6 = 0 2 4
1 5 7 4 6 , di mana (A A 2 ) = . 21 2 4
Dalam graf pada Gambar 3.5.2 terlihat bahwa dalam G(A)-nya tidak ada lintasan dari titik 1 ke titik 2. Berikut dibahas konsep nilai eigen dan vektor eigen suatu matriks dalam aljabar max-plus. Definisi 4.1.4 (Nilai eigen dan vektor eigen max-plus, Schutter,1996) n Diberikan A R n max . Skalar Rmax disebut nilai eigen max-plus matriks A
jika terdapat suatu vektor v R nmax dengan v εn1 sehingga A v = v. Vektor v tersebut disebut vektor eigen max-plus matriks A yang bersesuaian dengan . Berikut diberikan teorema yang memberikan eksistensi nilai eigen aljabar maxn plus untuk setiap A R n max .
Teorema 4.1.5 n Diberikan A R n max . Skalar max(A), yaitu bobot rata-rata maksimum sirkuit
elementer dalam G(A), merupakan suatu nilai eigen max-plus matriks A.
113
Bukti: Didefinisikan matriks B = max(A) A, maka n
max(B) =
1 ( k 1 k
k
trace ( B )
)
n
=
1 ( k 1 k
k
trace ((max ( A) A) )
)
n
=
1 ( k 1 k
k
k
trace ((max ( A)) A )
)
n
=
1 k k ( ((max ( A)) ) trace ( A ) ) k 1 k
n
=
(max ( A)) max ( A)) k 1
n
=
(0) = 0. k 1
Akibatnya G(B) tidak mempunyai sirkuit dengan bobot positif. Menurut Teorema 3.5.8 dapat diperoleh B* = E B ... B
n 1
2
n
dan B = B B ... B .
Karena max(B) = 0, maka terdapat k N (= himpunan semua bilangan asli) , k n k
dan suatu s {1, 2, ..., n} sehingga ( B ) ss = 0. Akibatnya komponen ke-s dari
B.s ( kolom ke-s matriks B ) adalah ( B ) ss = 0 yang berarti bahwa B.s n1. k
Di sisi lain menurut Definisi 3.5.9 B = B B * dan B * = E B . Karena (E)ss = 0, maka B.s = B.s* . Akibatnya
B.s = B B.s* = B.s*
atau ( max(A) A)
B.s* = B.s* atau A B.s* = max(A) B.s* . Jadi max(A) merupakan suatu nilai eigen aljabar max-plus matriks A dan B.s* merupakan vektor eigen aljabar maxplus matriks A yang bersesuaian dengan max(A).
■
Karena definisi matriks B = max(A) A, maka sirkuit kritis 0 dalam G(A) juga merupakan sirkuit kritis dalam G(B). Dari bukti Teorema 4.1.5 di atas, jika titik i menyusun busur dalam sirkuit kritis 0 , maka kolom ke-i matriks B * merupakan vektor eigen yang bersesuaian dengan nilai eigen max(A). Kolom ke-i
114
matriks B* di atas, yang merupakan vektor-vektor eigen max-plus matriks A yang bersesuaian dengan nilai eigen max(A), disebut vektor eigen max-plus fundamental yang bersesuaian dengan nilai eigen max-plus max(A). Dapat ditunjukkan bahwa kombinasi linear max-plus vektor-vektor eigen max-plus fundamental matriks A juga merupakan vektor eigen max-plus yang bersesuaian dengan max(A). Contoh 4.1.6 Diperhatikan matriks A dalam Contoh 3.5.7 dengan max(A) = 2. Dibentuk matriks 2 3 1 B = max(A) A = 2 1 1 = 2 1
B
2
0 2 0 = 2 0 2 , 1 1 2
B = E B B *
4 1 1 1 1 . Kemudian dihitung 0 1 2
0 1 1 = 1 0 2 . Karena sirkuit 1 0 0
1 2 1 merupakan sirkuit kritis dalam G(A) maka kolom pertama dan kedua matriks B* merupakan vektor eigen yang bersesuian dengan nilai eigen 2 3 1 0 2 0 max(A) = 2, yaitu bahwa = 1 = 2 1 dan 1 1 1 2 1 1 1 1 2 3 1 1 3 1 1 0 = 2 = 2 2 1 0 2
1 0 . 0
Berikut diberikan suatu teorema yang memberikan syarat perlu nilai eigen aljabar max-plus suatu matriks. Teorema 4.1.7 n Diberikan A R n max . Jika skalar R, merupakan nilai eigen aljabar max-plus
matriks A, maka merupakan bobot rata-rata suatu sirkuit dalam G(A).
115
Bukti: Misalkan adalah nilai eigen max-plus matriks A maka untuk setiap i {1, 2, ... , n} berlaku ( A x)i = xi dengan x
n 1. Akibatnya terdapat
suatu indeks i1 , i2 sehingga Ai1 , i2 xi2 = x i1 dengan x i1 . Karena dan x i1 maka xi2 dan Ai1 , i2 . Karena xi2 maka terdapat suatu indeks i3
sedemikian hingga Ai2 , i3 xi3 = xi2 . Karena dan xi2 maka xi3 dan Ai2 , i3 . Demikian seterusnya dengan cara yang sama di atas, akan diperoleh suatu barisan { i j } sehingga dan Ai j 1 ,
ij
Ai j 1, i j xi j = λ xi j 1 , dengan xi j
, j = 1, 2, 3, ... . Karena banyak titik dalam G(A) berhingga, maka
terdapat suatu j dan l sehingga i j = il . Akibatnya diperoleh suatu sirkuit , katakan adalah ( il , im ), ..., ( il 2 , il 1 ), ( il 1 , il ). Selanjutnya diperoleh ( Ail , il 1 xil 1 ) ... ( Aim , il xil ) = ( xil ) . . . ( xim ) . Karena operasi “” dalam Rmax bersifat komutatif, maka diperoleh ( Ail , il 1 . . . Aim , il ) ( xil 1 . . . xim xil ) = xim ) atau
( Ail , il 1 + . . . + Aim , il ) =
ml 1
atau =
ml 1
( xil xil 1 . . .
1 ( Ai , i + . . . m l 1 l l 1
+ Aim , il ). Hal ini berarti merupakan bobot rata-rata sirkuit .
■
n Dari Teorema 4.1.5 dan 4.1.7 dapat disimpulkan bahwa untuk A R n max ,
max(A) merupakan nilai eigen aljabar max-plus maksimum matriks A. Berikut diberikan lemma yang menyatakan bahwa untuk matriks irredusibel semua komponen vektor eigen max-plusnya berupa bilangan real. Lemma 4.1.8 berikut juga akan digunakan untuk membuktikan Teorema 4.1.9. Lemma 4.1.8 n Jika matriks irredusibel A R n max mempunyai nilai eigen aljabar max-plus
dengan x vektor eigen aljabar max-plus yang bersesuaian dengan , maka xi untuk setiap i {1, 2, ..., n}.
116
Bukti: Misalkan terdapat dengan tunggal s {1, 2, ..., n} sehingga xs = . Akibatnya (A x ) s = xs = atau As , i xi = untuk setiap i {1, 2, ..., n}. Karena xi untuk setiap i s, maka As , i = . Hal ini berarti tidak ada busur dari setiap titik i s ke titik s. Akibatnya G(A) tidak terhubung kuat atau A tidak irredusibel. Jika terdapat lebih dari satu komponen yang sama dengan , bukti seperti di atas sehingga akan diperoleh kesimpulan A tidak irredusibel.
■
Matriks irredusibel mempunyai nilai eigen aljabar max-plus tunggal seperti diberikan dalam teorema berikut. Teorema 4.1.9 n Jika matriks A R n max irredusibel, maka A mempunyai nilai eigen aljabar max-
plus tunggal. Bukti:. Eksistensi nilai eigen aljabar max-plus matriks A telah diberikan dalam Teorema 4.1.5 Misalkan adalah sebarang nilai eigen aljabar max-plus matriks A dengan x adalah vektor eigen aljabar max-plus yang bersesuaian dengan . Karena A irredusibel maka menurut Lemma 4.1.8, xi untuk setiap i {1, 2, ..., n}. Diambil sebarang sirkuit , misalkan sirkuit adalah ( i1 , i2 ), ( i2 , i3 ) , ... , ( i p , i1 ) dalam G(A). Karena adalah nilai eigen aljabar max-plus matriks A, maka Ai2 ,
i1
xi1 λ xi2 ,
Ai p ,
i p 1
Ai1 ,
xi p 1 λ xi p ,
ip
xi p λ xi1 .
Dari bukti Teorema 4.1.7, didapat bahwa lebih besar atau sama dengan rata-rata bobot , untuk setiap sirkuit dalam G(A). Jadi = max(A), yang berarti nilai eigen aljabar max-plus matriks A tunggal.
■
Berikut diberikan list program MATLAB untuk menghitung nilai eigen dan vektor eigen max-plus.
117
% Program Matlab Menghitung NILAI EIGEN MAX-PLUS Maksimum dan VEKTOR EIGEN % yang bersesuaian untuk suatu Matriks max-plus A % Oleh: M. Andy Rudhito FKIP Universitas Sanata Dharma % input: matriks max-plus Anxn % output: irredusibel/ tak irredusibel matriks A % nilai eigen max-plus maximum % vektor eigen yang bersesuaian function hasilkali = eigmax disp(' ') disp(' NILAI EIGEN DAN VEKTOR EIGEN MAX-PLUS MATRIKS') disp(' ----------------------------------------------') disp(' ') A = input(' Matriks yang dihitung A = '); disp(' ') disp(' HASIL PERHITUNGAN :') disp(' ===================') disp(' Matriks A = '), disp(A) % Menghitung A pangkat , trace/pangkat dan nilai eigen maksimum [m, n]= size(A); if m==n if n==2 for i = 1: n for j=1: n if i==j A(i,j) = 0; end; end; end; A0 = min(A); A00 = min(A0); if A00 == -Inf disp(' Matriks A TIDAK IRREDUSIBEL') else disp(' Matriks A IRREDUSIBEL') end; end; trace = max(diag(A)); D=A; for r=1:n-1 r+1; for i = 1: m for j = 1: n C(i, j) = -Inf; for p = 1: n C(i, j) = max( C(i, j) , A(i, p) + D(p, j) ); end; end; end; A_plus = max(D, C); D=C; trace_perpk(r) = max(diag(D)./(r+1)); lambmax = max(trace_perpk);
118
end; lambmaxmat = max(trace, lambmax); for r=1:n-2 r+1; for i = 1: m for j = 1: n C(i, j) = -Inf; for p = 1: n C(i, j) = max( C(i, j) , A(i, p) + D(p, j) ); end; end; end; A_plus1 = max(D, C); D=C; end; if n>2 for i = 1 : n for j = 1 : n if i==j A_plus1(i,j) = 0; end; end; end; A0_plus1 = min(A_plus1); A00_plus1 = min(A0_plus1); if A00_plus1 == -Inf disp(' Matriks A TIDAK IRREDUSIBEL') else disp(' Matriks A IRREDUSIBEL') end; end; disp('NILAI EIGEN max-plus maksimum matriks A =’),disp(lambmaxmat) % Menghitung matriks normal B, B pangkat dan B+ B = A-lambmaxmat; disp(' ') G=B; for s=1:n-1 s+1; for i = 1: m for j = 1: n F(i, j) = -Inf; for p = 1: n F(i, j) = max( F(i, j) , B(i, p) + G(p, j) ); end; end; end; B_plus = max(G, F); G = F; end; % Menghitung matriks E dan B* for i = 1 : n for j = 1 : n if i ~= j
119
E(i,j) = -Inf; end; end; end; B_star= max(E, B_plus); % Menentukan vektor eigen yang bersesuaian disp(' VEKTOR EIGEN max-plus yang bersesuaian =') x= diag(B_plus); for t = 1 : n if x(t)>=0 VE = B_star(:,t); disp(VE) end; end; % Perhatian jika yang diinputkan bukan matriks nxn else disp(' ') disp(' P E R H A T I A N ! ! !') disp('BUKAN matriks bujursangkar, nilai eigen tidak didefinisikan') end;
Gambar 4.1.1 List Program MATLAB untuk nilai dan vektor eigen max-plus.
Dengan menggunakan program di atas dapat ditentukan nilai eigen maksimum dan vektor eigen yang bersesuaian untuk matriks seperti dalam contoh berikut. Contoh 4.1.10 2 3 1 Untuk matriks A = 1 1 dapat diperoleh bahwa vektor eigen 2 1
maksimumnya max(A) = 2 dengan vektor-vektor eigen max-plus fundamentalnya adalah v1 = [0, 1, 1]T dan v2 = [1, 0, 0]T . 4.2 Penerapan pada Penjadwalan Kereta Dibahas kembali sistem (1.1.8) pada Bab 1 di depan. Diberikan waktu keberangkatan perjalanan awal dari dua stasiun x(0) = [0, 0]T. Secara rekursif akan diperoleh barisan vektor x(k) (waktu keberangkatan perjalanan ke-k dari dua stasiun) berikut
120
0 x(0) = , x(1) = 0
5 3 , x(2) =
8 8 , x(3) =
13 11 , x(4) =
16 16 , ... .
Diperhatikan barisan vektor di atas, parameter k pada vektor x(k) menyatakan banyak perjalanan (kejadian) yang telah diberangkatkan (dimulai) oleh suatu stasiun (titik). Pada kondisi awal, yaitu untuk k = 0, dianggap sebagai kejadian ke0. Misalkan saat waktu 12, setelah kondisi awal, titik 1 telah menjadi aktif (memulai suatu kejadian) sebanyak dua kali, yaitu pada waktu 5 dan 8. Sementara pada waktu yang sama, setelah kondisi awal, titik 2 telah menjadi aktif sebanyak tiga kali, yaitu pada waktu 3, 8 dan 11. Selanjutnya diperhatikan sistem jaringan kereta sederhana dalam sistem (1.1.8), untuk kasus tidak ada jadwal keberangkatan. Secara rekursif barisan vektor keadaan sistem dapat ditentukan dengan x(1) = A x(0), x(2) = A x(1), x(3) = A x(2), ... . Jika diberikan waktu keberangkatan perjalanan awal (perjalanan ke-0) dari dua 2 stasiun adalah x(0) = , yaitu kereta berangkat dari stasiun S1 saat waktu 2 0
untuk dan saat waktu 0 dari stasiun S 2 , maka barisan waktu keberangkatan dari 5 2 10 13 dua stasiun adalah: x(0) = , x(1) = , x(2) = , x(3) = , 5 0 8 13 18 x(4) = , x(5) = 16
21 21 , ... .
Hal ini berarti untuk perjalanan ke-1, kereta berangkat dari stasiun S1 saat waktu 5 untuk dan saat waktu 5 dari stasiun S 2 , untuk perjalan ke-2, kereta berangkat dari stasiun S1 saat waktu 10 untuk dan saat waktu 8 dari stasiun S 2 dan seterusnya. Selanjutnya dibahas sifat periodik SLMI autonomous berdasarkan pengertian nilai eigen dan vektor eigen aljabar max-plus. Sebelumnya didefinisikan pengertian sifat periodik suatu SLMI.
121
Definisi 4.2.1 Suatu SLMI (A, B, C, x0 ) dikatakan periodik dengan periode , jika x(k) = k
x(0), untuk k = 1, 2, 3, ... . Teorema 4.2.2 Diberikan SLMI autonomous (A, C, x0
)) dengan A matriks irredusibel yang
mempunyai nilai eigen aljabar max-plus . Jika x0 = x(0), merupakan vektor k
eigen aljabar max-plus yang bersesuaian dengan maka x(k) = x(0), k
untuk k = 1, 2, 3, ... . Selanjutnya y(k) = C x(0), untuk k = 1, 2, 3, ... .
Bukti: Untuk kondisi awal x0 yang merupakan vektor eigen yang bersesuaian dengan , dengan induksi matematik akan dibuktikan bahwa k
x(k) = x(0),
untuk k = 1, 2, 3, ... .
(4.2.1)
1
Diperhatikan bahwa x(1) = A x(0) = x(0) = x(0). Jadi (4.2.1) benar n
untuk k = 1. Misalkan (4.2.1) benar untuk k = n yaitu x(n) = x(0), maka n
n
n
x(n +1) = A x(n) = A ( x(0)) = (A x(0)) = ( x(0)) =
n 1
x(0). Jadi (4.2.1) benar untuk k = n + 1.
Selanjutnya diperoleh k
y(k) = C x(0),
untuk k = 1, 2, 3, ... .
■
Dengan kata lain teorema di atas mengatakan bahwa setelah kondisi awal kejadian berikutnya muncul secara secara periodik dengan periode .
Kembali diperhatikan sistem jaringan kereta sederhana dalam subbab 1.1, 2 5 untuk kasus tidak ada jadwal keberangkatan. Matriks A = merupakan 3 3
matriks irredusibel karena A12 , A21 . Dengan cara seperti yang dibahas dalam
122
subbab 4.1 di atas dapat ditentukan bahwa matriks A tersebut mempunyai nilai eigen tunggal = 4 dengan vektor eigen yang bersesuaian adalah [0, 1]T dan [1, 0]T. Dengan mengambil x0 = [1, 0]T maka diperoleh barisan vektor keadaan sistem sebagai berikut: 1 x(0) = , x(1) = 0
5 4 , x(2) =
9 8 , x(3) =
13 12 , x(4) =
17 16 , x(5) =
21 20 , ... .
Terlihat bahwa x(1) = 4 x(0), x(2) = 4 x(1), x(3) = 4 x(2) dan seterusnya. Hal ini berarti dengan mengambil waktu keberangkatan awal [1, 0]T, waktu antar keberangkatan dalam setiap stasiun adalah 4 satuan waktu. Dengan demikian waktu keberangkatan menjadi sangat teratur, yang mana setiap 4 satuan waktu kereta akan berangkat dari setiap stasiun. Hasil dalam Teorema 4.2.2 di atas, dalam Sistem Jaringan Kereta dapat dipergunakan sebagai pertimbangan dalam penyusunan jadwal keberangkatan kereta dengan waktu antar keberangkatan yang tetap. Berikut dibahas penerapan teorema di atas untuk Sistem Jaringan Kereta Sederhana untuk kasus dengan jadwal keberangkatan. Dalam pembahasan subbab 1.1 untuk kasus dengan jadwal keberangkatan, telah diperoleh sistem x(k+1) = A x(k) d(k + 1) untuk k = 0, 1, 2, ... , 2 5 2 dengan x(k) = [ x1 (k), x2 (k)] T R 2max , A = R 2max , 3 3
d(k + 1) = [ d1 (k + 1), d 2 (k + 1)]T R 2max ,
xi (k+1): waktu keberangkatan ke-k+1 pada stasiun Si untuk i = 1, 2 , dan di (k + 1): jadwal keberangkatan ke-(k+1) pada stasiun Si untuk i = 1, 2 . Jika diinginkan suatu jadwal keberangkatan dengan waktu antar keberangkatan yang tetap, misalkan T satuan waktu, maka jadwal keberangkatan ke-k pada stasiun Si untuk i = 1, 2 adalah d(k) = d(0) T
k
untuk k = 1, 2, 3, ...,
dengan d(0) adalah jadwal keberangkatan awal. Misalkan pada keberangkatan kek kereta berangkat dengan jadwal keberangkatan k, maka waktu keberangkatan
123
ke-k + 1 pada stasiun Si untuk i = 1, 2 adalah x(k+1) = A d(k) d(k + 1). Agar kereta dapat berangkat sesuai jadwal, maka waktu keberangkatan kereta harus sama dengan jadwal keberangkatan kereta yaitu x(k+1) = d(k + 1) untuk k = 0, 1, 2, 3, ... . Hal ini dipenuhi bila A d(k)
m
d(k + 1) untuk k = 0, 1, 2, 3, ... .
Dalam subbab 2.3 telah dibahas bahwa nilai eigen suatu matriks irredusibel A merupakan bobot rata-rata maksimum sirkuit elementer dalam G(A). Dalam sistem jaringan kereta di atas yang merupakan nilai eigen aljabar max-plus matriks A diinterpretasikan sebagai rata-rata waktu antar kedatangan kereta dalam lingkar yang memerlukan waktu perjalanan terbesar, yaitu lingkar dalam. Jika x0 vektor eigen aljabar max-plus yang bersesuaian dengan di ambil sebagai d(0), maka merupakan waktu antar keberangkatan minimum agar kereta dapat berangkat sesuai jadwal. Jika jadwal keberangkatan yang disusun dengan mengambil T = , maka jadwal ini tidak memperbolehkan adanya keterlambatan kedatangan kereta. Dalam penyusunan jadwal keberangkatan, keterlambatan kereta dapat diperbolehkan untuk suatu selang waktu tertentu dengan mengambil T yang lebih besar dari . Misalkan diambil T = 5, maka keterlambatan kereta yang diperbolehkan maksimum sebesar T = 5 4 = 1 satuan waktu. 4.3 Penerapan Analis Model Antrian Dalam subab 1.4 telah dibahas pemodelan jaringan antrian seri tertutup. Diperhatikan kembali jaringan antrian seri tertutup dengan banyak pelayan dan banyak pelanggan masing-masing adalah n = 5. Misalkan waktu layanan pada pelayan ke-i = 1, 2, 3, 4, 5 berturut-turut t1 = 3, t 2 = 4, t3 = 6, t4 = 7 dan t5 = 5, 3 4 maka diperoleh A =
3 4 6 6 . 7 7 5 5
Misalkan diambil saat keberangkatan awal pelanggan d(0) = [0, 0, ..., 0]T , maka saat keberangkatan pelanggan untuk k = 1, 2, 3, ... adalah
124
d1 (1) 3 d (1) 4 2 d3 (1) = d 4 (1) d5 (1)
4 6
6 7
7 5
3 0 3 0 4 0 = 6 , 0 7 5 0 5
d1 (3) 3 d (3) 4 2 d 3 (3) = d 4 (3) d 5 (3)
4 6
6 7
7 5
3 5 15 6 12 10 = 18 dan seterusnya. 9 21 5 7 19
d1 (2) 3 d ( 2) 4 2 d 3 (2) = d 4 (2) d 5 (2)
4 6
6 7
7 5
3 3 8 4 8 6 = 12 . 7 14 5 5 12
Saat keberangkatan pelanggan d(k) sampai k = 15, seperti dalam tabel berikut. Tabel 4.3.1. Perhitungan Saat Keberangkatan Pelanggan k d1 d2 d3 d4 d5
0 0 0 0 0 0
1 3 4 6 7 5
2 8 8 12 14 12
3 15 12 18 21 19
4 22 19 24 28 26
5 29 26 30 35 33
6 36 33 36 42 40
7 43 40 42 49 47
8 50 47 48 56 54
9 57 54 54 63 61
10 64 61 60 70 68
11 71 68 67 77 75
12 78 75 74 84 82
13 85 82 81 91 89
14 92 89 88 98 96
15 99 96 95 105 103
Dari Tabel 4.3.1 di atas, dengan saat keberangkatan awal pelanggan d(0) = [0, 0, ..., 0]T, nampak bahwa antar saat keberangkatan pelanggan pada setiap pelayanan tidak seluruhnya periodik. Selanjutnya akan dibahas suatu upaya penjadwalan saat keberangkatan awal pelanggan d(0) agar saat keberangkatan selanjutnya periodik dengan periode tertentu. Sebelumnya akan dibahas cara lain untuk menyatakan persamaan rekursif model dinamika jaringan antrian (1.4.6) melalui vektor saat keberangkatan awal pelanggan d(0). Dengan menggunakan induksi matematis dapat ditunjukkan bahwa
k
d(k) = A d(k 1) = A d(0) , k = 1, 2, ... .
(4.3.1)
1
Untuk k = 1 berlaku d(1) = A d(0) = A d(0). Andaikan benar untuk k = n 1, yaitu d(n 1) = A Untuk k = n , d(n) = A d(n 1) = A ( A untuk k = n.
( n 1)
( n 1)
d(0). n
d(0)) = A d(0). Jadi benar
125
Saat keberangkatan pelanggan d(k) dikatakan perodik dengan periode sebesar jika d(k) = d(k 1) untuk setiap k = 1, 2, ... . Dengan demikan agar d(k) dikatakan perodik dengan periode sebesar haruslah dipenuhi d(k) = A d(k 1) = d(k 1) untuk setiap k = 1, 2, ... . Hal ini berarti merupakan suatu nilai eigen max-plus matriks A dan d(k 1) merupakan vektor eigen yang bersesuaian dengan . Mengingat berlaku untuk setiap k = 1, 2, ... , maka juga berlaku untuk k = 1. Jadi agar saat keberangkatan pelanggan perodik dengan periode sebesar , maka d(0), yaitu saat keberangkatan awal pelanggan, haruslah merupakan suatu vektor eigen yang bersesuaian dengan
. Mengingat graf bobot matriks A pada model jaringan antrian di atas terhubung kuat maka matriks A irredusibel. Kemudian menurut Teorema 4.1.9, matriks A mempunyai nilai eigen max-plus tunggal, yaitu max(A), dengan vektor eigen fundamental v di mana vi untuk setiap i {1, 2, ..., n}. Situasi ini sesuai dengan keadaan nyata, di mana saat keberangkatan awal berhingga. Selanjutnya agar realistis, saat keberangkatan awal pelanggan haruslah tak negatif. Untuk itu perlu dilakukan modifikasi terhadap vektor eigen fundamental v sedemikian hingga semua komponennya tak negatif . Dibentuk vektor v* = v , dengan = min (vi ) , untuk i = 1, 2, ..., n. i
Dengan kombinasi linear max-plus di atas akan diperoleh bahwa komponenkomponen vi* semuanya tak negatif dan paling sedikit satu komponennya bernilai nol. Sementara vektor v* juga merupakan vektor eigen yang bersesuaian dengan
max(A). Jika diambil saat keberangkatan awal pelanggan d(0) = v* , maka v* merupakan saat keberangkatan awal tercepat pelanggan, agar saat keberangkatan pelanggan periodik sejak saat keberangkatan awal pelanggan. Mengingat vektor v* merupakan vektor eigen yang bersesuaian dengan max(A), maka A v* =
126
max ( A) v*. Dari persamaan (4.3.1) dengan menggunakan induksi matematis dapat ditunjukkan bahwa d(k) = (max ( A)) v*, k
untuk k = 1, 2, ... .
(4.3.2)
Untuk k = 1 berlaku d(1) = A v* = max ( A) v* = (max ( A)) v*. 1
Andaikan benar untuk k = n 1, yaitu d(n 1) = (max ( A)) Untuk k = n , d(n) = A d(n 1) = A ( (max ( A)) ( (max ( A))
( n 1)
A v* = ( (max ( A))
( n 1)
( n 1)
( n 1)
v* .
v* =
max ( A) v* = ( (max ( A))
n 1
v*.
Jadi benar untuk k = n. Dari Persamaan (4.3.2) di atas nampak bahwa v* adalah saat keberangkatan awal tercepat pelanggan, sehingga saat keberangkatan pelanggan pada jaringan periodik dengan periode sebesar max ( A) . Selanjutnya dapat ditentukan bahwa nilai eigen max-plus tunggal matriks A adalah max ( A) = 7 dengan vektor eigen max-plus fundamental yang bersesuaian dengan max ( A) adalah v = [6, 9, 10, 0, 2]T. Selanjutnya diperoleh = min (vi ) = 10, untuk i = 1, 2, ..., n, sehingga saat keberangkatan i
awal tercepat pelanggan adalah d(0) = v* = 10 v = [4, 1, 0, 10, 8]T. Selanjutnya dengan saat keberangkatan awal tersebut, saat keberangkatan pelanggan untuk k = 1, 2, 3, ... adalah d1 (1) 3 d (1) 4 2 d3 (1) = d 4 (1) d5 (1)
4 6
6 7
7 5
3 4 11 4 1 1 8 0 = 7 = 7 0 , 10 17 10 8 5 8 15
4 d1 (2) 18 1 d (2) 15 2 2 d 3 (2) = 14 = 7 0 , 10 d 4 (2) 24 8 d 5 (2) 22
d1 (3) 25 4 d (3) 22 1 2 3 d 3 (3) = 21 = 7 0 dan seterusnya. d 4 (3) 31 10 d 5 (3) 29 8
Saat keberangkatan pelanggan d(k) sampai k = 15, seperti dalam tabel berikut
127
Tabel 4.3.2 Perhitungan Saat Keberangkatan Periodik k d1 d2 d3 d4 d5
0 4 1 0 10 8
1 11 8 7 17 15
2 18 15 14 24 22
3 25 22 21 31 29
4 32 29 28 38 36
5 39 36 35 45 43
6 46 43 42 52 50
7 53 50 49 59 57
8 60 57 56 66 64
9 67 64 63 73 71
10 74 71 70 80 78
11 81 78 77 87 85
12 88 85 84 94 92
13 95 92 91 101 99
14 102 99 98 108 106
15 109 106 105 115 113
Nampak bahwa saat awal keberangkatan tercepat pelanggan adalah vektor d(0) = [4, 1, 0, 10, 8]T, sehingga saat keberangkatan pelanggan pada setiap pelayanan dalam jaringan antrian tersebut periodik dengan periode sebesar 7.
BAB 5 ALJABAR MIN-PLUS DAN ALJABAR MAX-MIN SERTA PENERAPANNYA
Bab ini membahas beberapa varian lain dari aljabar max-plus. Jika operasi maximum pada aljabar max-plus diganti dengan operasi minimum, maka akan diperoleh aljabar max-min. Jika operasi plus dalam aljabar max-plus diganti dengan dengan minimum, maka akan diperoleh aljabar max-min. Beberapa penyesuaian dilakukan terkait perubahan operasi tersebut. Diberikan juga penerapannya khususnya terkait dengan masalah jaringan. 5.1
Aljabar Min-Plus Secara umum aljabar min-plus analog dengan aljabar min-plus, atau dapat
dikatakan kedua struktur aljabarnya isomorfis. Dalam pembahasan berikut hanya akan ditampilkan beberapa hal yang berbeda, baik dari segi konsep maupun penafsirannya. Diberikan R := R { } dengan R adalah himpunan semua bilangan real dan : = . Pada R didefinisikan operasi berikut: a b := min(a, b) dan a b : = a b untuk setiap a, b R . Dapat ditunjukkan bahwa (R, , ) merupakan semiring idempoten komutatif dengan elemen netral 0 = 0 dan elemen satuan = +. Kemudian (R , , ) disebut dengan aljabar min-plus, yang selanjutnya cukup dituliskan dengan Rmin. Relasi “ m ” didefinisikan pada R dengan x m y x y = x. Dalam masalah lintasan terpendek, Aij adalah bilangan real nonnegatif dan merupakan bobot busur (j, i), yaitu waktu tempuh untuk melalui busur (j, i). k
n Diberikan A R n adalah min . Jika k = 0, 1, 2, 3, ..., maka unsur ke-st dari matriks A
k
( A ) st = =
min
( As , ik 1 + ... + Ai2 , i1 + Ai1 , t )
min
( Ai1 , t + Ai2 , i1 + ... + As , ik 1 ),
1i1 , i2 ,ik 1 n
1i1 , i2 ,ik 1 n
128
129
untuk setiap s, t. Karena ( Ai1 , t + Ai2 , i1 + ... + As , ik 1 ), adalah bobot lintasan, dengan panjang k dengan t sebagai titik awal dan s sebagai titik akhirnya dalam G(A), yang dalam hal ini adalah total waktu tempuh lintasan dengan t sebagai titik awal dan s k
sebagai titik akhirnya, maka ( A ) st adalah waktu tempuh minimum, dari semua lintasan dalam G(A) dengan panjang k, dengan t sebagai titik awal dan s sebagai titik akhirnya. Jika tidak ada lintasan dengan panjang k dari t ke s, maka kapasitas bobot maksimum didefinisikan sama dengan . n Suatu matriks A R n min dikatakan semi-definit jika semua sirkuit dalam
G(A) mempunyai bobot taknegatif dan dikatakan definit jika semua sirkuit dalam G(A) mempunyai bobot positif. Teorema berikut memberikan hasil seperti dalam aljabar max-plus dalam versi aljabar min-plus. Teorema 5.1.1 (versi Min-Plus dari Max-Plus dalam Baccelli, et.al., 2001) n Diberikan A R n min . Jika semua sirkuit dalam G(A) mempunyai bobot taknegatif,
atau dengan kata lain A adalah semi-definit, maka p n, E A ... A
n 1
m
A
p
Bukti: Mengingat banyak titik dalam G(A) adalah n maka semua lintasan dengan panjang p n tersusun dari k sirkuit dengan jumlah panjang seluruh sirkuit kurang dari p dan satu lintasan dengan panjang kurang dari n. Hal ini berarti untuk setiap p n dan untuk setiap s, t {1, 2, ..., n}, terdapat r {1, 2, ..., n} sehingga p
l
( A ) st = ( A ) st +
k
(A
mi
) ri , ri dengan 0 l n1 , 1 mi n , 1 ri n dan
i
k = 1, 2, 3, ... . Mengingat semua sirkuit mempunyai bobot taknegatif maka untuk l
p
setiap p n dan untuk setiap s, t {1, 2, ..., n} berlaku ( A ) st ( A ) st dengan 0 l n1. Akibatnya A ... A
n 1
m
n Mengingat untuk setiap A R n min berlaku A
E A ... A
n 1
p
A , p n.
m E A, maka
m
A
p
■
130
Berdasarkan Teorema 5.1.1 di atas didefinisikan operasi bintang (*) berikut. n * Definisi 5.1.2 Diberikan matriks semi-definit A R n min . Didefinisikan A : = E
A ... A
n
A
n 1
... .
Mengingat Teorema 5.1.1 di atas diperoleh bahwa A* : = E A ... A
n 1
.
Berikut diberikan teorema yang memberikan eksistensi dan ketunggalan penyelesaian sistem persamaan linear iteratif min-plus x = A x b. Teorema berikut merupakan versi min-plus, yang analog dengan versi max-plus (Baccelli, et.al., 2001 atau Heidergott, et.al., 2005). Teorema 5.1.3 Jika A semi-definit, maka x* = A* b merupakan suatu penyelesaian sistem persamaan linear iteratif min-plus x = A x b. Lebih lanjut jika A definit, maka sistem persamaan linear tersebut mempunyai penyelesaian tunggal. Bukti: Mengingat A semi-definit maka A* ada. Perhatikan bahwa A (A* b) b = (E A A*) b = A* b. Jadi x* = A* b merupakan suatu penyelesaian sistem persamaan linear iteratif min-plus x = A x b. Selanjutnya andaikan A definit dan x adalah penyelesaian sistem x = A x b. Substitusikan x ke ruas kanan diperoleh: x = b A [(A x) b] = b (A b) ( A x) . 2
Dengan pengulangan cara di atas diperoleh x = b (A b) ( A b) ( A x) 2
= b (A b) … ( A k 1
=
( A l 1
k
3
k 1
b) ( A x). k
b) ( A x) k
131
Untuk k diperoleh lim
k 1
( A
k
𝑘→∞ l 1
k 1
= lim
A
k
𝑘→∞ l 1
b) ( A x) k
b lim ( A x). k
𝑘→∞
Mengingat A semi-definit, yaitu bahwa semua sirkuit dalam G(A) mempunyai bobot k
positif, maka lim A = 𝑘→∞
, sehingga diperoleh
merupakan penyelesaian tunggal.
x = A* b . Jadi x = A* b
■
0 3 3 6 1 3 5 Contoh 5.1.4 Diberikan A = [4 2 0] , b = [0]. Dapat diperoleh A* = [0 0 0], 0 3 0 2 0 𝜀 2 3 * * sehingga x = A b = [0] merupakan suatu penyelesaian sistem persamaan linear 2 iteratif min-plus x = A x b. Perhitungan di atas diperoleh dengan Program MATLAB dengan list program berikut. % % % %
Program Matlab Menyelesaikan pers iterative SPL min-plus x=Ax+b Oleh: M. Andy Rudhito Pmat FKIP USD input: A = matriks koefisien Anxn, B = matriks konstanta nx1 output: Interval matriks x=A*b
A1 = input(’ Masukkan matriks Amxn = ’); B1 = input(’ Masukkan matriks Bnx1 = ’); A1 B1 [m, n]= size(A1); [k, r]= size(B1); % Menghitung A pangkat dan A+ G1=A1; A1_plus = A1; for s=1:n-1 s+1; for i = 1: m for j = 1: n F1(i, j) = Inf; for p = 1: n F1(i, j) = min( F1(i, j) , A1(i, p) + G1(p, j) ); end; end; end;
132
G1 = F1; F1; A1_plus = min(A1_plus, F1); end; disp(’ Matriks A_plus ’), disp(A1_plus); % Menghitung matriks E dan A* for i = 1 : n for j = 1 : n if i ~= j E(i,j) = Inf; end; end; end; A1_star= min(E, A1_plus); % Menampilkan hasil A pangkat disp(’ Matriks A_star ’), disp(A1_star); % Menghitung A_star kali B for i = 1:m for j = 1: r A1_starB1(i, j) = Inf; for p = 1: n A1_starB1(i, j) = min(A1_starB1(i, j) , A1_star(i, p) + B1(p, j)); end; end; end; % Menampilkan hasil kali disp(’ Penyelesaian minimal x’),disp(A1_starB1)
Gambar 5.1.1 List Program MATLAB untuk Menyelesaikan SPL Min-Plus
5.2
Penerapan Aljabar Min-Plus pada 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. Pembahasan dengan mengikuti alur dan konsep yang analog dengan masalah penjadwalan seperti pada subbab 3.7. Definisi 5.2.1 Suatu jaringan lintasan searah S adalah suatu graf berarah berbobot terhubung kuat taksiklik S = (V, A), dengan V = {1, 2, , ... , n} yang memenuhi kondisi: jika (i, j) A, maka i < j.
133
Dalam jaringan lintasan searah 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 saat-mulai paling awal (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 saat-mulai paling awal titik i dapat dilalui,
waktu temp uh dari titik j ke titik i jika ( j,i ) A jika ( j, i) A. ( )
Aij =
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 0
jika i 1
xie = e min ( Aij x j ) jika i 1.
1 j n
Dengan menggunakan notasi aljabar min-plus persamaan di atas dapat dituliskan menjadi jika i 1 0 e x = ( Aij x j ) jika i 1. 1 j n e i
(5.2.1)
Selanjutnya diperoleh hasil dalam Teorema 5.2.2 berikut. Teorema 5.2.2 Diberikan suatu jaringan lintasan searah dengan n titik dan A adalah matriks bobot graf berarah berbobot jaringan tersebut. Vektor saat-mulai paling awal titik i dapat dilalui diberikan oleh xe = (E A ... A
n1
) be
di mana be = [0, , ... , ]T. Lebih lanjut xne merupakan waktu minimal untuk melintasi jaringan.
134
Bukti: Misalkan A adalah matriks bobot jaringan tersebut, xe = [ x1e , x2e , ... , xne ]T dan be = [0, , ... , ]T, persamaan (5.2.1) dapat dituliskan ke dalam suatu sistem persamaan linear min-plus berikut xe = A xe be .
(5.2.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
(5.2.3)
merupakan penyelesaian sistem (5.2.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 (5.2.3) dapat ditulis menjadi xe = A* be = (E A ... A
n 1
) be
yang merupakan vektor waktu-mulai paling cepat setiap titik i dapat dilalui. Perhatikan bahwa ( A* ) n1 merupakan bobot minimum lintasan dari titik awal hingga titik akhir jaringan, sehingga xne merupakan waktu tempuh minimal untuk melintasi jaringan.
■
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, sehingga diperoleh Teorema 5.2.3 berikut. Teorema 5.2.3 Diberikan suatu jaringan lintasan searah dengan n titik dan A adalah matriks bobot graf berarah berbobot jaringan tersebut. Vektor saat-penyelesaian paling lambat titik diberikan oleh xl = ( (AT )* bl ) di mana bl = [, , ... , xne ]T.
135
Bukti: Misalkan
xil = saat-penyelesaian paling lambat 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 xil
e jika i n xn = l max ( Bij x j ) jika i 1. 1 j n
(5.2.4)
Dengan menggunakan notasi aljabar min-plus persamaan (5.2.4) ekivalen dengan
xil
e jika i n xn = min ( B x lj ) jika i 1. 1 j n ij
(5.2.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.2.5) dapat dituliskan menjadi
z = AT z bl .
(5.2.6)
yang penyelesaiannya adalah z = (AT )* bl . Jadi diperoleh vektor saat-penyelesaian paling lambat adalah xl = z.
■
Dari hasil pada Teorema 5.2.2 dan Teorema 5.2.3 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 xie = xil . Berikut diberikan beberapa definisi dari hasil di atas. Definisi 5.2.4 Suatu jalan (i, j) A dalam jaringan lintasan searah S disebut jalan terpendek jika xie = xil dan x ej = xlj .
136
Definisi 5.2.5 Suatu lintasan p P dalam jaringan lintasan searah S disebut lintasan terpendek jika semua jalan yang terletak dalam p merupakan jalan terpendek. Dari Definisi 5.2.4 dan 5.2.5 di atas dan uraian sebelumnya, dapat diperoleh Teorema 5.2.6 berikut. Teorema 5.2.6 Suatu lintasan p P merupakan lintasan terpendek jika dan hanya p jika mempunyai bobot minimum, yaitu sama dengan xne . Bukti: () Akan dibuktikan kontraposisinya. Jika lintasan pP mempunyai bobot tidak minimum, maka ada (i, j) p sedemikian hingga xie xil atau
x ej xlj .
Hal ini berarti ada jalan (i, j) p yang bukan merupakan jalan terpendek. Jadi menurut Definisi 5.2.5 lintasan p bukan merupakan lintasan terpendek. () Akan dibuktikan kontraposisinya. Jika lintasan p P bukan lintasan terpendek, maka menurut Definisi 5.2.5, terdapat jalan (i, j) p yang bukan merupakan jalan terpendek, yaitu di mana xie xil atau x ej xlj . Hal ini berakibat ada lintasan selain p, yaitu p P yang bobotnya lebih kecil dari bobot lintasan p. Jadi bobot ■
lintasan p tidak mempunyai bobot minimum.
Berikut diberikan contoh suatu jaringan lintasan searah dan perhitungannya. Contoh 5.2.8 Perhatikan jaringan lintasan searah seperti yang diberikan pada Gambar 5.2.1 berikut : 5 2 3
3
6
1 3 2
5
7
2 2
6
3 4
7
Gambar 5.2.1 Contoh Jaringan lintasan searah
7
137
Matriks bobot graf berarah berbobot pada jaringan proyek di atas adalah matriks A di bawah ini. Dengan menggunakan program yang disusun dengan menggunakan MATLAB, di mana list programnya dapat dilihat pada Gambar 5.2.2 di bawah ini, dengan input matriks A berikut, diperoleh output program sebagai berikut.
2 3 A =
2 3 2 0 3 7 7 5
A* = 6
0 2 3 4 4 7 9
0 0 2 3 0 2 2 0 0
xe = 5 6 3 7 0
7 7 5 5 6 0
0 2 3 l 4 x = 4 7 9
0 2 2 4 4 3 9
. Dari hasil di atas, waktu tempuh minimal untuk melintasi lintasan adalah 9 dan lintasan terpendek yang diperoleh adalah lintasan : (1, 2), (2, 4), (4, 5), (5, 7). % Program Matlab Menentukan Lintasan Terpendek % Oleh: M. Andy Rudhito FKIP Universitas Sanata Dharma % input: A = matriks max-plus Anxn, (matriks yang bersesuaian dengan graf jaringan) % output: saat-mulai paling awal, saat-mulai paling lambat. % Memasukkan matriks yang bersesuaian: A = input(' Masukkan matriks A = '); disp(' HASIL PERHITUNGAN :') disp(' ===================') disp(' Matriks A = '),disp(A) [m, n]= size(A); %MENGHITUNG MAJU % Menghitung A pangkat dan A+ G=A; A_plus = A; for s=1:n-1 s+1; for i = 1: m for j = 1: n F(i, j) = Inf; for p = 1: n F(i, j) = min( F(i, j) , A(i, p) + G(p, j) ); end; end;
138
end; G = F; A_plus = min(A_plus, F); end; % Menghitung matriks E dan A* for i = 1 : n for j = 1 : n if i ~= j E(i,j) = Inf; end; end; end; A_star= min(E, A_plus) % Membuat matriks B for i = 1 : n for j = 1 : 1 if i ~= 1 B(i,j) = Inf; else B(i,j)=0; end; end; end; % Menghitung vektor saat-mulai paling awal ESi = A_star kali B [k, r]= size(B); for i = 1:m for j = 1: r A_starB(i, j) = Inf; for p = 1: n A_starB(i, j) A_star(i, p) + B(p, j)); end; end; end; ESi=A_starB
=
min(A_starB(i,
% Membuat Matriks saat-mulai paling awal MESi for i = 1:n for j = 1:n if A(i,j)~=Inf MESi(i,j)= ESi(j,1); else MESi(i,j)=Inf; end end end % Membuat Matriks saat-mulai paling awal MESj for i = 1:n for j = 1:n if A(i,j)~=Inf MESj(i,j)= ESi(i,1); else
j)
,
139
MESj(i,j)=Inf; end end end % Membuat matriks saat penyelesaian paling cepat MECij for i = 1:n for j = 1:n MEC(i,j)= MESi(i,j)+A(i,j); end end %MENGHITUNG MUNDUR % Menghitung A2 pangkat dan A2+ A2=A'; G2=A2; A2_plus = A2; for s=1:n-1 s+1; for i = 1: m for j = 1: n F2(i, j) = Inf; for p = 1: n F2(i, j) = min( F2(i, j) , A2(i, p) + G2(p, j) ); end; end; end; G2 = F2; A2_plus = min(A2_plus, F2); end; % Menghitung matriks E2 dan A2* for i = 1 : n for j = 1 : n if i ~= j E2(i,j) = Inf; end; end; end; A2_star= min(E2, A2_plus); % Membuat matriks B2 for i = 1 : n for j = 1 : 1 if i ~= n B2(i,j)= Inf; else B2(i,j) = -A_starB(n,1); end; end; end; [k, r]= size(B2); % Menghitung vektor saat penyelesaian paling lambat LCj = A2_star kali B2
140
for i = 1:m for j = 1: r A2_starB2(i, j) = Inf; for p = 1: n A2_starB2(i, j) = min(A2_starB2(i, j) , A2_star(i, p) + B2(p, j)); end; end; end; LCj = -A2_starB2
Gambar 5.2.2 List Program MATLAB untuk Menentukan Lintasan Terpendek
5.3
Aljabar Max-Min Secara umum aljabar max-min juga analog dengan aljabar max-plus, atau
dapat dikatakan kedua struktur aljabarnya isomorfis. Seperti dalam pembahsan aljabar min-plus, dalam pembahasan berikut hanya akan ditampilkan beberapa hal yang berbeda, baik dari segi konsep maupun penafsirannya. Aljabar max-min, yaitu himpunan semua bilangan real Rdilengkapi dengan operasi max (maksimum) dan min (minimum), telah dapat digunakan dengan baik untuk memodelkan dan menganalisis masalah lintasan kapasitas maksimum (Gondran dan Minoux, 2008). Diberikan R := R { } dengan R adalah himpunan semua bilangan real nonnegatif dan : = +. Pada R didefinisikan operasi berikut: a,b R , a b := max(a, b) dan a b : = min(a, b). Dapat ditunjukkan bahwa ( R , , ) merupakan semiring idempoten komutatif dengan elemen netral 0 = 0 dan elemen satuan = +. Kemudian ( R , , ) disebut dengan aljabar max-min, yang selanjutnya cukup dituliskan dengan R . Dalam masalah lintasan kapasitas maksimum, Aij adalah bilangan real nonnegatif dan merupakan kapasitas busur (j, i), yaitu aliran maksimum yang dapat melalui busur (j, i). Diberikan A R nn . Jika k = 0, 1, 2, 3, ..., maka unsur ke-st k
k
dari matriks A adalah ( A ) st =
max
1 i1 , i2 ,ik 1 n
(min( As , ik 1 , ... , Ai2 , i1 , Ai , t )) 1
141
=
max
1 i1 , i2 ,ik 1 n
(min( Ai1 , t , Ai2 , i1 , ... , As , ik 1 )) , untuk
setiap s, t. Karena min( Ai1 , t , Ai2 , i1 , ... , As , ik 1 ) adalah kapasitas lintasan dengan panjang k dengan t sebagai titik awal dan s sebagai titik akhirnya dalam G(A), maka k
( A ) st adalah kapasitas maksimum semua lintasan dalam G(A) dengan panjang k,
dengan t sebagai titik awal dan s sebagai titik akhirnya. Jika tidak ada lintasan dengan panjang k dari t ke s, maka kapasitas bobot maksimum didefinisikan sama dengan 0. Agak berbeda dengan aljabar max-plus dan aljabar min-plus di mana ada konsep semi-definit dan definit, dalam aljabar max-min teorema berikut berlaku untuk sembarang matriks persegi dalam aljabar max-min. Teorema 5.3.1 Diberikan A R nn . p n , A
p
m
E A ... A . n
Bukti: Karena banyak titik dalam G(A) adalah n maka semua lintasan dengan panjang p n tersusun setidaknya oleh sebuah sirkuit, sehingga kapasitas maksimum sirkuit tersebut lebih kecil atau sama dengan kapasitas maksimum lintasan yang panjangnya kurang dari n. Akibatnya A p n. Karena untuk setiap A R n n berlaku A A ... A
n 1
, p n.
p
m
A ... A
m E A, maka
A
p
n 1
m
,
E
∎
Berdasarkan Teorema 5.3.1 di atas didefinisikan operasi bintang (*) berikut. Definisi 5.3.2 Diberikan A R nn . Didefinisikan A* : = E A ... A A
n 1
n
... . Mengingat Teorema 5.3.1 diperoleh bahwa A* : = E A ... A
n 1
.
Berdasarkan penjelasan tentang kapasitas dan pangkat matriks di atas, berikut diberikan suatu hasil mengenai kapasitas maksimum lintasan dalam suatu jaringan.
142
Teorema 5.3.3 Jika A R n n adalah matriks bobot suatu graf berarah berbobot, di mana bobot Aij merupakan kapasitas busur (j, i), yaitu aliran maksimum yang dapat melalui busur (j, i), maka unsur ( A* )ij merupakan kapasitas maksimum lintasan dengan ujung titik j dan pangkal titik i. Bukti: Jika A R nn , maka seperti pada penjelasan di atas, diperoleh bahwa k
( A ) st adalah kapasitas maksimum semua lintasan dalam G(A) dengan panjang k,
dengan t sebagai titik awal dan s sebagai titik akhirnya. Mengingat A* = E A ... A
n
A
n 1
... dapat disimpukan bahwa unsur ( A* )ij merupakan
kapasitas maksimum lintasan dengan ujung titik j dan pangkal titik i .
■
Berikut list program MATLAB untuk menghitung A* max-min. % Program Matlab untuk menghitung A* max-min % Oleh: M. Andy Rudhito FKIP Universitas Sanata Dharma % input: A = matriks persegi atas max-min % output: Matriks A* A1 = input(' Masukkan matriks Anxn = '); [m, n]= size(A1); % Menghitung A pangkat dan A+ G1=A1; A1_plus = A1; for s=1:n-1 s+1; for i = 1: n for j = 1: n F1(i, j) = -Inf; for p = 1: n F1(i, j) = max( F1(i, j) , min(A1(i, p), G1(p, j))); end; end; end; G1 = F1; A1_plus = max(A1_plus, F1); end; disp(' Matriks A_plus '), disp(A1_plus); % Menghitung matriks E dan A* for i = 1 : n for j = 1 : n
143
if i == j E(i,j) = Inf; end; end; end; A1_star= max(E, A1_plus) % Menampilkan hasil A* disp(' Matriks A_star '), disp(A1_star);
Gambar 5.3.1 List Program MATLAB untuk Menghitung A* max-min
Berikut diberikan teorema yang memberikan eksistensi dan ketunggalan penyelesaian sistem persamaan linear iteratif max-min x = A x b. Teorema 5.3.4 Diberikan A R nn dan b R n . Vektor x* = A* b merupakan penyelesaian tunggal sistem persamaan linear iteratif max-min x = A x b. Bukti: Perhatikan bahwa berlaku A (A* b) b = (E A A*) b = A* b. Jadi x* = A* b merupakan suatu penyelesaian sistem persamaan linear iteratif x = A x b.
max-min
Selanjutnya andaikan x adalah penyelesaian sistem x = A x b. Substitusikan x ke ruas kanan diperoleh: x = b A [(A x) b] = b (A b) ( A x) . 2
Dengan pengulangan cara di atas diperoleh x = b (A b) ( A b) ( A x) 2
3
= b (A b) … ( A k 1
=
( A
k
k 1
b) ( A x) k
b) ( A x). k
l 1
Untuk k diperoleh lim
k 1
( A
k
𝑘→∞ l 1
k 1
= lim
A
𝑘→∞ l 1
k
b) ( A x) k
b lim ( A x). k
𝑘→∞
144
Mengingat sifat operasi maximum dan minimum lim A 𝑘→∞
k
m
A* , sehingga
* * diperoleh x = A b . Jadi x = A b merupakan penyelesaian tunggal.
■
1 1 3 5 𝜀 5 5 * Contoh 5.3.5 Diberikan A = [4 2 0] , b = [0]. Dapat diperoleh A = [4 𝜀 0], 2 0 𝜀 2 4 𝜀 𝜀 2 sehingga x* = A* b = [2] merupakan suatu penyelesaian sistem persamaan linear 2 iteratif max-min x = A x b. Perhitungan di atas diperoleh dengan Program MATLAB dengan list program seperti Gambar berikut. % Program Matlab Menyelesaikan Sistem Pers Linear Iterative Max-Min x=Ax+b % Oleh: M. Andy Rudhito FKIP Universitas Sanata Dharma % Input: A = matriks atas aljabar max-min Anxn, b = Vektor nx1 % Output: Matriks x=A*b % Memasukkan matriks A dan vektor b A1 = input(' Masukkan matriks Anxn = '); B1 = input(' Masukkan matriks bnx1 = '); [m, n]= size(A1); [k, r]= size(B1); % Menghitung A pangkat dan A+ G1=A1; A1_plus = A1; for s=1:n-1 s+1; for i = 1: n for j = 1: n F1(i, j) = -Inf; for p = 1: n F1(i, j) = max( F1(i, j) , min(A1(i, p), G1(p, j))); end; end; end; G1 = F1; A1_plus = max(A1_plus, F1); end; disp(' Matriks A_plus '), disp(A1_plus); % Menghitung matriks E dan A* for i = 1 : n for j = 1 : n if i == j E(i,j) = Inf; end; end; end;
145
A1_star= max(E, A1_plus) % Menampilkan hasil A pangkat disp(' Matriks A_star '), disp(A1_star); % Menghitung A_star kali B for i = 1:m for j = 1: r A1_starB1(i, j) = -Inf; for p = 1: n A1_starB1(i, j) = max(A1_starB1(i, j) , min(A1_star(i, p), B1(p, j))); end; end; end; % Menampilkan hasil kali disp(' Penyelesaian minimal x'), disp(A1_starB1)
Gambar 5.3.2 List Program MATLAB untuk SPL Max-Min
5.4
Penerapan Aljabar Max-Min pada Masalah Kapasitas Maksimum Dalam pembahasan subbab di atas, diketahui bahwa unsur ( A* )ij
merupakan kapasitas maksimum lintasan dengan ujung titik j dan pangkal titik i, dengan A adalah matriks bobot pada graf berarah berbobot yang terkait. Dari hasil ini kemudian dapat ditentukan lintasan dengan kapasitas maksimum yang berawal dari titik 1 dan berakhir di titik n dalam suatu jaringan lintasan searah seperti dalam Definisi 5.2.1, dengan bobot busurnya berupa kapasitas busur, yaitu aliran maksimum yang dapat melalui busur tersebut. Selanjutnya lintasan yang dimaksud adalah lintasan yang berawal dari titik 1 dan berakhir di titik n. Dari Teorema 5.3.3 diperoleh bahwa ( A* )n 1 merupakan kapasitas maksimum lintasan dengan titik awal 1 dan titik akhir n. Kapasitas maksimum lintasan dengan titik awal 1 dan titik akhir n seperti ini selanjutnya disebut kapasitas maksimum jaringan. Selanjutnya didefinisikan busur kapasitas maksimum dan lintasan kapasitas maksimum. Definisi 5.4.1. Suatu busur (j, i) dalam jaringan lintasan searah dengan n titik merupakan busur kapasitas maksimum jika kapasitasnya tidak kurang dari kapasitas maksimum jaringan .
146
Definisi 5.4.2. Suatu lintasan disebut lintasan kapasitas maksimum jika seluruhnya terdiri dari busur kapasitas maksimum. Dari definisi di atas dan hasil sebelumnya dapat diperoleh hasil pada teorema berikut. Teorema 5.4.3. Diberikan jaringan lintasan searah dengan n titik dan matriks bobotnya A R n n . Suatu busur (j, i) dalam jaringan merupakan busur kapasitas maksimum jika dan hanya jika Aij ( A* )n 1 0. Bukti. Menurut Definisi 5.4.1 di atas, suatu busur (j, i) merupakan busur kapasitas maksimum jika hanya jika kapasitasnya tidak kurang dari kapasitas maksimum jaringan. Dari Teorema 5.3.3 diperoleh bahwa ( A* )n 1 merupakan disebut kapasitas maksimum jaringan. Dengan demikian suatu busur (j, i) dalam jaringan merupakan busur kapasitas maksimum jika dan hanya jika Aij ( A* )n 1 0.
■
Contoh 5.4.4 Diberikan suatu jaringan berkapasitas seperti pada Gambar 5.4.1 di bawah ini. 5 2 6
3
5
1 5 7
5
7
2 4
6
6
3 4
7
2
Gambar 5.4.1. Suatu Jaringan Lintasan Searah Berkapasitas Real
Matriks bobot graf berarah berbobot pada jaringan berkapasitas di atas adalah matriks A di bawah ini. Dengan menggunakan program MATLAB untuk menyelesaikan SPL Max-Min dengan list programnya seperti pada Gambar 5.3.2
147
di atas, dengan input matriks A tersebut, diperoleh output program matriks A* sebagai berikut.
0 7 6 A = 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 5 0 0 0 0 , A* = 0 2 5 0 0 0 0 0 3 7 0 0 0 0 2 5 6 0
7 6 5 5 5 5
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 5 0 0 0 . 4 5 5 0 0 4 5 5 7 0 4 5 5 6 6
sehingga diperoleh ( A* ) 71 = 5. Selanjutnya diperoleh
5 2 1 * A ( A ) 71 = 5 5 5 5
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 1 0 5 5 5 5 . 5 3 0 5 5 5 5 5 2 2 5 5 5 5 3 0 1 5
Dari matriks A ( A* ) 71 nampak bahwa busur kapasitas maksimum adalah (1,2), (1,3), (3,4), (4,5), (5,6) dan (6,7), sehingga lintasan 134567 merupakan lintasan kapasitas real maksimum. Untuk lintasan mulai busur (1, 2) tidak membentuk lintasan kapasitas real maksimum karena (2, 4) bukan merupakan busur kapasitas maksimum.
DAFTAR PUSTAKA
Andersen, Maria H. 2002. Max-Plus Algebra: Properties and Applications. Master of Science in Mathematics’ Thesis. Department of Mathematics University of Wyoming. Laramie, WY. Bazargan, Massoud. 2004. Airline Operations and Scheduling. Asghate Publishing Company. Burlington. Baccelli, F., Cohen, G., Olsder, G.J. and Quadrat, J.P. 2001. Synchronization and Linearity. John Wiley & Sons. New York. Boom, T.J.J., Schutter, B. D. and Verdult, V. 2003. Identification of Stochastic Max-plus-linear Systems.
Proceedings of the 2003 European Control
Conference (ECC'03), Cambridge, UK. Paper 104. pp. 6 – 11. Busacker, R. G. and Saaty, T. L. 1965. Finite Graphs and Networks: An Introduction with Applications. McGraw-Hill Book Company. New York. Butkovič, Peter. 2010. Max Linear System: Theory and Algorithm. Springer. New York. Chanas, S. and Zielinski, P. 2001. Critical Path Analysis in the Network with Fuzzy Activity Times. Fuzzy Sets and Systems. 122. pp. 195 –204. Chartrand, G. and Oellermann, O. R. 1993. Applied and Algorithmic Graph Theory. McGraw-Hill, Inc. New York. Farlow, Kasie G. 2009. Max-Plus Algebra. Master’s Thesis Virginia Polytechnic Institute and State University. Blacksburg, VA. Gondran, M and Minoux, M. 2008. Graph, Dioids and Semirings. Springer. New York. Heidergott, B., Olsder, J. G and Woude, J. 2005. Max Plus at Work. Princeton University Press. Princeton. Krivulin, N.K. 1995. A Max-Algebra Approach to Modeling and Simulation of Tandem Queueing Systems. Mathematical and Computer Modelling, 22. pp. 25-31.
148
149
Krivulin, N.K. 1996. The Max-Plus Algebra Approach in Modelling of Queueing Networks. Proc. Summer Computer Simulation Conf. Portland, OR, SCS. pp. 485-490. Krivulin, N.K. 2000. Algebraic Modelling and Performance Evaluation of Acyclic Fork-Join Queueing Networks. Advances in Stochastic Simulation Methods, Statistics for Industry and Technology. Birkhäuser. Boston. Krivulin, N.K. 2001. Evaluation of Bounds on Service Cycle Times in Acyclic Fork-Join Queueing Networks. International Journal of Computing Anticipatory Systems. 9. pp. 94-109. Rudhito, M. A. 2003. Sistem Linear Max-Plus Waktu Invariant. Tesis. Program Pascasarjana Universitas Gadjah Mada. Yogyakarta. Rudhito, M. A. 2004. Penerapan Sistem Persamaan Linear Max-Plus x = Axb pada Masalah Penjadwalan. Jurnal Ilmiah Bidang Matematika, Informatika dan Terapannya. Math – Info (4). pp. 14 – 19. Rudhito, M. A. 2011. Aljabar Max-Plus Bilangan Kabur dan Penerapannya pada Masalah Penjadwalan dan Jaringan Antrian Kabur. Disertasi Program Pascasarjana Universitas Gadjah Mada. Yogyakarta. Schutter, B. De. 1996. Max-Algebraic System Theory for Discrete Event Systems. PhD Thesis. Department of Electrical Engineering Katholieke Universiteit Leuven. Leuven. Schutter, B. D. and Boom, T. 2000. ”Model Predictive Control for Max-plus-linear Discrete-event Systems: Extended Report & Addendum”. Technical report bds: 99-10a. Faculty of Information Technology and System. Delft University of Technology. Delft. Skalna, I., Rao, R. M. V. and Pownuk, A. 2007. Systems of Fuzzy Equations in Structural Mechanics. The University of Texas at El Paso Department of Mathematical Sciences Research Reports Series No. 2007-01. Soltoni, A.and Haji, R. 2007. A Project Scheduling Method Based on Fuzzy Theory. Journal of Industrial and Systems Engineering. 1. pp 70 – 80. 149
150
Susilo, F. 2006. Himpunan dan Logika Kabur serta Aplikasinya. Edisi kedua. Graha Ilmu. Yogyakarta Suwarno, FX Widadi A. 2001. Tata Operasi Darat. PT Gramedia Widiasarana Indonesia. Jakarta. Taha, Hamdi A. 1996. Riset Operasi. Jilid 2 (terjemahan). Binarupa Aksara. Jakarta. Wahyudyah, Regina. 2015. Sistem Persamaan Linear Max-Plus dan Aplikasinya dalam Masalah Ramp-Handling Pesawat. Skripsi. Program Studi Pendidikan Universitas Sanata Dharma. Yogyakarta. Wilson, Robin J. 1972. Introduction to Graph Theory. Oliver & Beyond. Edinburgh. Wohlgemuth, A. 1990. Introduction to Proof in Abstract Mathematics. Saunders College Publishing. Philadelphia. Zimmermann, K. 2006. Interval Linear Systems and Optimization Problems over Max-plus Algebras. Linear Optimization Problem with Inexact Data. Springer Science+Business Media, Inc. New York.
151
INDEKS
aktifitas, 7, 8, 98 aktifitas kritis, 102, 103 aljabar max-min, 128, 140, 145 aljabar max-plus, 1, 12, 15, 23 aljabar min-plus, 123, 132, 133 antrian seri tertutup, 9, 10, 123 bahan baku, 4, 39, 42 block-off, 75 block-on, 75 bobot, 7, 85, 86 bobot lintasan, 86, 87, 103, 129 bobot negatif, 90, 95, bobot positif, 92, 113, 129 bobot rata-rata lintasan, 86, bobot rata-rata maksimum, 88, 112, 123 bobot taknegatif, 129 bobot takpositif, 89, 90, 100, 134 buffer, 5, 39, busur, 7, 83, 84, 98, 133, 145, 146 busur kapasitas maksimum, 145, 146 closed tandem, 9 critical path method, 7 definit, 90, 94, 100, 129 delay, 79 dioid, 14 earliest start time, 7, 98, 133 eksistensi penyelesaian SPLIO, 65 elemen invers, 14 elemen netral, 13, 17, 128 elemen penyerap, 13 elemen satuan, 12, 17, 128, 140 elemen slack, 66 first-in-first-out, 9 forward, 7, 98, 133 graf, 83 graf berarah, 83, graf berarah aktifitas, 98 graf bobot, 85 graf kritis, 88 graf siklik, 84 graf taksiklik, 84 ground time, 75 idempoten, 13, input-output SLMI, 40 input-output SLMI autonomous, 44 irredusibel, 111
jadwal keberangkatan, 2, 3, 122 jadwal penerbangan, 76 jalan, 133 jalan terpendek, 135, 136 jaringan antrian, 9, 123 jaringan kereta api, 1 jaringan lintasan searah, 132, 135 jaringan proyek,7, 98, kapasitas busur, 140, 145 kapasitas maksimum, 140, 145 kesamaan matriks, 16 ketunggalan penyelesaian SPLIO, 66 kombinasi linear, 24 komparabel, 25 kondisi awal, 38 lintasan, 84 lintasan kapasitas maksimum, 147 lintasan kritis, 102 lintasan terpendek, 136 lone-one, 66 loop, 83 masalah input paling lambat, 45 masalah lintasan terpendek, 128, 132 masalah optimisasi SPL, 34 minimisasi simpangan maksimum, 47 MATLAB I-O SLMI autonomous, 53 MATLAB input-output SLMI, 52 MATLAB lintasan terpendek, 140 MATLAB operasi bintang max-min, 145 MATLAB operasi bintang max-plus, 93 MATLAB pangkat matriks, 22 MATLAB SPLI max-plus, 96 MATLAB SPLI min-plus, 132 MATLAB perkalian matriks, 20 MATLAB SPLI max-min, 145 MATLAB SPLIO max-plus, 73 MATLAB lintasan kritis, 110 MATLAB nilai dan vektor eigen, 119 matriks atas aljabar max-plus, 15 matriks bobot, 85 matriks identitas max-plus, 17 matriks nol max-plus, 17 nilai eigen max-plus, 113 operasi bintang, 90 operasi max, 3 operasi min, 128
152
operasi penjumlahan, 3 overflow, 5 palet, 9 pangkat matriks, 18 penjadwalan proyek, 7, 98 penyangga, 5 penyelesaian paling cepat, 101 penyelesaian tak ideal, 79 perhitungan maju, 7 persimpangan, 133 peubah tetap, 66 ramp dispatcher, 75 ramp-handling, 75 rusuk, 83 saat keberangkatan, 10 saat keberangkatan periodik, 127 saat kedatangan, 10 saat-mulai paling awal, 7 saat-mulai paling lambat, 101 saat-penyelesaian paling cepat, 98 saat-penyelesaian paling lambat, 100 semi-definit, 90 semifield, 14 semigrup, 12 semigrup komutatif, 12 semimodul, 23 semiring, 12 semiring komutatif, 13 sifat antisimetris, 24 sifat refleksif, 24
sifat transitif, 24 siklus layanan jaringan, 9 sirkuit, 84 sirkuit kritis, 88 sistem kejadian diskrit (SKD), 6 SLMI, 6 SLMI autonomous, 38 SLMI MIMO, 38 SLMI periodik, 122 SLMI satu input satu output (SISO), 38 sistem persamaan linear (SPL), 28 SPL input-output (SPLIO) max-plus, 28 SPL Iteratif (SPLI) max-plus, 93 SPL Iteratif min-plus, 131 sistem produksi sederhana, 4, 37 subpenyelesaian, 29 subpenyelesaian terbesar, 29 teori graf, 83 terhubung kuat, 84 titik, 83 trace, 19 transit arrangement, 76 turnaround arrangement, 76 urutan parsial, 24 urutan pengoperasian, 6 urutan total, 24 vektor, 24 vektor eigen max-plus fundamental, 114 vektor eigen max-plus, 112, 114 waktu mengambang, 101
