KRISTALOGRAFI BIDANG DATAR BATIK CAP

Prosiding SNMPM Universitas Sebelas Maret 2013

Volume 2

KRISTALOGRAFI BIDANG DATAR BATIK CAP Kartono1), R.Heri Sulistyo Utomo2), Priyo Sidik S3) 1) , 2) Jurusan Matematika FMIPA UNDIP 3) Jurusan Informatika FMIPA UNDIP Jl. Prof. H.Soedarto, SH Tembalang Semarang, e-mail: [email protected] Abstrak Pembuatan kain batik cap yang beragam corak memerlukan banyak cap, sehingga modal awal yang dibutuhkannya cukup besar. Di lain fihak, kain batik cap mendapat persaingan yang keras dari tekstil printing bermotif batik di pasaran, Kedua hal inilah yang memicu semakin tertekannya produksi kain batik cap, sehingga diperlukan suatu inovasi dalam pembuatannya untuk menekan biaya produksinya. Penelitian ini menjawab permasalahan tersebut dengan melakukan inovasi desain motif dan metode pengecapannya, yang dengan satu cap dapat dihasilkan beragam corak. Inovasi ini didasarkan pada teori grup simetri dan kristalografi dua dimensi, sehingga kain batik cap yang dihasilkan ini merupakan grup kristalografi dua dimensi. Metode pengecapan ini mampu menghasilkan beragram corak sebanyak 13 kain batik cap dari satu cap saja, sehingga cap ini disebut ajaib (magic). Hasil penelitian ini bermanfaat dalam mendukung program penguatan sistem inovasi daerah dalam mengembangkan potensi unggulan daerah, dan pembelajaran matematika yang kreatif, inovatif dan produktif. Kata Kunci: batik cap, cap ajaib, motif, corak, kristalografi, simetri

PENDAHULUAN Penguatan sistem inovasi daerah dalam mengembangkan potensi unggulan daerah digalakkan oleh pemerintah, termasuk pemerintah Kota Surakarta dengan unggulan batik. Perkembangan batik diawali dengan adanya batik tulis, yang kemudian diikuti dengan batik cap. Perkembangan batik pada masa sekarang cukup menggembirakan, permintaan batik tulis maupun batik cap cukup tinggi, walaupun kebutuhan pasar batik sekarang sebagian sudah dipenuhi dengan tekstil bermotif batik, bahkan telah dibanjiri produk import. Batik cap membutuhkan modal awal yang cukup mahal karena bergantung pada harga tembaga sebagai bahan utama pembuatan capnya. Untuk membuat batik cap yang beragam motif maka diperlukan banyak cap, sementara harga satu cap relatif lebih mahal dari harga canting. Harga cap pada kondisi sekarang dengan ukuran 20 cm X 20 cm berkisar Rp. 750.000,hingga Rp. 1.250.000,-/motif tergantung kerumitan motifnya. Selain proses pelukisan motif batik yang menggunakan cap, proses selanjutnya dilakukan dengan cara yang hampir sama seperti saat membuat batik tulis, misalnya dari proses pewarnaannya yang harus berulang-ulang untuk mendapatkan warna yang diinginkan, atau dari proses nglorodnya. Pembuatan batik cap membutuhkan ketelitian yang tinggi. Kualitas batik cap sering dilihat dari kehalusannya yaitu presisi peletakan cap di sekujur bidang kain, tidak ada garis sambungan yang meleset atau semuanya pas. Tukang cap harus memastikan agar menyambungnya pas, sehingga tidak ada garis-garis yang menebal atau malamnya menggumpal di kain. Celakanya, ketidaksempurnaan ini seringkali baru terlihat setelah proses pewarnaan. Batik cap pun membutuhkan satu feeling dalam pengerjaannya. Hanya dengan komitmen untuk Makalah Pendamping: Matematika 1

105

Volume 2


mendapatkan yang terbaiklah, tercipta karya batik cap yang berkualitas. Bentuk gambar/desain motif pada batik cap selalu ada pengulangan yang jelas, sehingga gambar nampak berulang dengan bentuk yang sama, dengan ukuran garis motif relatif lebih besar dibandingkan dengan batik tulis. Pengembangan desain motif batik cap, yang dari satu cap dapat menghasilkan beragam corak, merupakan permasalahan yang

diselesaikan dalam penelitian ini. Permasalahan ini

diselesaikan dengan menerapkan konsep grup simetri dan kristalografi berdimensi dua untuk menghasilkan motif dan juga cap ajaib (magic stamp). Cap ini disebut ajaib (magic) karena dengan satu cap yang didesain berdasarkan motif tersebut dapat menghasilkan beragam corak batik cap melalui inovasi metode pengecapannya, yang didasarkan pada generator dalam grup simetri (translasi, refleksi, rotasi, dan glide-refleksi). Seperti yang telah diuraikan dalam latar belakang, para pengrajin batik cap menghadapi kendala mahalnya harga sebuah cap, padahal satu cap biasanya hanya menghasilkan satu corak batik cap, sedangkan harga jualnya lebih murah daripada batik tulis. Dalam kondisi seperti ini maka sangat perlu dan urgen untuk mengembangkan desain motif dalam cap, yang dapat menghasilkan banyak corak, artinya, dari satu desain motif dalam cap dapat menghasilkan lebih dari satu corak batik cap. Pengembangan motif yang demikian akan dapat memperkecil modal awal dan memberikan banyak pilihan corak batik bagi konsumen, sehingga akan meningkatkan daya saing batik cap. Hal inilah yang merupakan fokus tujuan penelitian ini dilaksanakan. Penelitian ini diharapkan dapat berkontribusi secara nyata dalam pengembangan ilmu pengetahuan, teknologi dan seni (Kategori Penelitian I) yakni mengembangkan penerapan teori grup simetri dan konsep kristalografi berdimensi dua untuk mendesain motif batik cap. Disisi lain, pelaksanaan penelitian ini dimaksudkan dapat berkontribusi dalam pemecahan masalah pembangunan dengan meningkatkan daya saing kain batik cap dan mendukung pengembangan cluster unggulan potensi daerah, sekaligus meningkatkan kemampuan masyarakat (pengrajin/ produsen) dalam menerapkan teori tepat guna (Kategori Penelitian II). Dari sudut pandang pengembangan kelembangaan (Kategori Penelitian III), penelitian ini dimaksudkan untuk memperkuat Jurusan Matematika Fakultas Sains dan Matematika (FSM) Universitas Diponegoro Semarang, khususnya Laboratorium Matematika Terapan (Bengkel Desain Motif Simetris) dapat bermitra dengan fihak UMKM dalam rangka mengembangkan industri kreatif. Metode pengecapan yang ditemukan dapat dimanfaatkan dalam pengembangan pembelajaran matematika (grup simetri dan kristalografi) secara kreatif, inovatif dan produktif. Penelitian ini dilakukan atas dorongan untuk dapat menciptakan (mengembangkan) motif batik cap dan inovasi produk derivatifnya, dengan menerapkan teori grup simetri dan kristalografi berdimensi dua dalam mendesain motifnya. Metode pengecapan motif dasar pada selembar kain melalui formulasi-formulasi matematis menghasilkan banyak corak. Pengecapan ini dilakukan tanpa adanya tumpang tindih yang satu dengan yang lain, dan secara berulang-

106

Makalah Pendamping: Matematika 1


Volume 2

ulang menurut komposisi yang cocok dari rotasi, translasi dan refleksi. Hasil pengecapan yang berdasarkan operasi rotasi, translasi atau refleksi dan komposisinya berasosiasi dengan sebuah grup simetri.(Durbin, 1985). Salah satu aplikasi grup simetri yang sangat menarik adalah dikenal sebagai kristalografi berdimensi dua maupun tiga. Permasalahan tentang mengisi secara penuh suatu bidang datar dengan poligon yang kongruen tanpa tumpang tindih kecuali pada sisi-sisinya merupakan permasalahan yang dapat diselesaikan dengan teori kristalografi berdimensi dua. Poligon-poligon kongruen yang mengisi penuh suatu bidang datar dengan mengoperasikan gerakan (translasi, rotasi, refleksi atau glide-refleksi) dari satu poligon tersebut dikenal dengan poligon fondamental. Hasil pengisian yang diperoleh berasosiasi dengan grup simetri dari gambar yang dibentuk oleh sisi-sisi dari semua poligon tersebut. Hal ini merupakan fakta yang mengaitkan antara teori grup dan kristalografi berdimensi dua, sehingga dinamakan grup kristalografi berdimensi dua (Durbin, 1985). Sekarang pandang bidang datar (kain mori) akan dipenuhi oleh poligon-poligon yang berbentuk bujur sangkar yang memuat sebuah motif dasar yang tidak saling tumpang tindih kecuali pada sisi-sisinya saling adjacent. Dengan menggerakkan poligon ini sesuai dengan komposisi generator-generator rotasi, refleksi, translasi maupun refleksi-glide yang cocok akan diperoleh suatu corak hasil pengecapan. Dengan memulai pada poligon dasar dan secara periodik

menggerakkan poligon dasar

menurut generator yang dipilih maka keseluruhan

bidang datar (kain mori) akan terpenuhi oleh poligon-poligon dasar sehingga corak baru dapat diperoleh. Pengembangan motif batik cap yang didasarkan pada teori grup simetri, juga telah digunakan untuk mengembangkan desain motif batik simetris. Pada tahun 1999-2000, Kartono dkk pernah melakukan penelitian dengan judul ”Grup simetri untuk pengembangan desain motif batik simetris” . Pengembangan desain motif batik simetris dengan menerapkan konsep teori grup simetri dan periodesasi telah berhasil dari satu buah desain motif dasar dapat menghasilkan 14 corak. (Kartono et al, 2000). Keempatbelas corak tersebut dihasilkan dengan menggunakan bermacam-macam bentuk poligon

seperti bujur sangkar, persegi panjang,

segitiga siku-siku, segitiga sama kaki, segitiga sama sisi bahkan segitiga dengan sudut-sudut yang ditentukan sesuai dengan keinginan, sedangkan dalam pembuatan motif batik cap ini hanya menggunakan poligon yang berbentuk bujur sangkar saja. Kartono dkk (2011) menerapkan teori yang sama untuk menguak pola (motif) geometris crop circle yang muncul di Berbah Sleman Daerah Istemewa Yogyakarta. Penelitian ini menghasilkan motif lingkaran sebagai motif dasar, dan ternyata bentuk crop circle tersebut dihasilkan melalui operasi translasi, rotasi, maupun glide-refleksi dari motif dasar lingkaran. Penelitian itu berhasil menemukan pola geometrisnya yang tersusun dari 12 lingkaran utama, 2 lingkaran lain di luarnya dengan 11 titik pusat lingkaran (Kartono et al, 2011).


107

Volume 2


Pada awal tahun 2012, teori yang sama dipakai untuk mengembangkan pemanfaatan limbah kayu sebagai bahan pembuat ukiran bergerak berbasis transformasi

oleh Nurhilaliah

dan Ulfia Azmi dengan Kartono sebagai pembimbing, dalam rangka mengikuti Indonesian Science Project Olympiad (ISPO) 2012. Dari penelitian-penelitian ini dapat disimpulkan bahwa, motif yang dihasilkan dapat dikategorikan ke dalam bentuk karya seni generatif. Dari sudut pandang seni generatif, selalu dapat dihubungkan dengan keindahan yang selalu melekat pada karya seni itu. Penelitianpenelitian ini semakin meyakinkan peneliti, bahwa motif dalam karpet maupun hiasan dinding bordir yang dihasilkan juga mengandung unsur keindahan sebagai karya seni generatif. Pada tahun 2012, Kartono dkk melaksanakan penelitian

Riset

Unggulan Daerah

(RUD) Balitbang Provinsi Jawa Tengah tahun 2012 dengan judul ”Pemberdayaan Ekonomi Lokal melalui Pengembangan Inovasi Jenis Produk Bordir di Kabupaten Kudus”(Kartono et al, 2012). Inovasi jenis produk yang dimaksud adalah karpet dan hiasan dinding bordir. Pembuatan desain motif dasarnya juga berbasis pada teori grup simetri dan kristalografi berdimensi dua. Dari penelitian-penelitian ini dapat disimpulkan bahwa, baik desain motif batik simetris, crop circle, ukiran kayu bergerak, maupun bordir tersebut dapat dikategorikan ke dalam bentuk karya seni generatif, yang dapat dihubungkan dengan keindahan yang selalu melekat pada karya seni itu. Unsur keindahan merupakan salah satu bagian penting dalam usaha pengembangan industri kreatif.

METODE PENELITIAN Jenis Penelitian Penelitian ini merupakan penelitian eksperimental . Waktu dan Tempat Penelitian Jangka waktu penelitian ini selama sembilan bulan di Bengkel Desain Motif Simetris Laboratorium Matematika Terapan, Laboratorium Komputasi Jurusan Matematika FMIPA UNDIP, dan bekerjasama dengan Batik Adityan Laweyan Surakarta. Target/Subjek Penelitian Target penelitian iniadalah penemuan atau inovasi desain motif dalam cap dan formulasi matematis pengecapannya, sehingga dari satu motif dalam cap tersebut dapat menghasilkan banyak corak batik. Wujud hasil penelitian ini adalah cap ajaib (magic stamp), prototipe kain batik cap yang siap diproduksi massal. Prosedur 1. Membuat poligon dasar (poligon fondamental) berbentuk persegi ukuran 12 cm x 12 cm pada kertas gambar.

108



Volume 2

2. Mendesain motif dasar dengan mempertimbangkan nilai keindahannya dan generatorgenerator pada teori grup simetri yang dipakai. Pada tahapan ini, telah dipilih satu desain motif yang akan dibuatkan capnya. 3. Melakukan simulasi penataan motif. 4. Motif dasar ini kemudian discan, dan diperbaiki di studio gambar milik pengrajin batik di Laweyan Surakarta. Perbaikan ini dilakukan untuk mendapatkan motif yang akurat dan mencoba beberapa kombinasi warna. Hasil perbaikan inilah yang menjadi motif yang dipakai untuk membuat cap, dan pemesanan cetakan/ cap ajaib (magic stamp) dengan motif yang terpilih. 5. Membuat formulasi pergerakan/pergeseran poligon dasar ini berdasarkan kombinasi generator pada grup simetri (rotasi, refleksi, translasi maupun refleksi-glide) dan periodesasinya. Formulasi ini dibuat

berdasarkan kombinasi yang diinginkan dan

kemudian dipilih formula yang menghasilkan corak hasil penyusunan yang indah. Formulasi inilah yang kemudian dinamakan formula metode penataan motif dasar simetris yang ditemukan itu. 6. Dengan menerapkan formula yang dipilih ini dan konsep periodesasi maka keseluruhan poligon dasar akan terpenuhi oleh motif dasar tersebut. Dari sinilah keindahan dari hasil penataan motif dasar simetris yang ditentukan itu akan dinilai. 7. Melakukan simulasi komputer dan

pengecapan berdasarkan formulasi gerakan

pengecapan yang telah diperoleh pada langkah (5). Hasil pengecapan ini akan menghasilkan corak-corak batik cap dari satu motif tersebut. Formulasi matematis yang disimulasikan ini yang akan dipakai sebagai aturan gerakan pengecapan/ pembuatan kain batik cap oleh pengrajin. Sampai pada penulisan laporan kemajuan ini, pembuatan cap masih dilakukan, sehingga pembuatan kain batiknya belum dilaksanakan.

HASIL PENELITIAN DAN PEMBAHASAN Hasil Penelitian Penelitian ini berhasil membuat cap ajaib bermotif dengan tema Crop Circle dan 13 corak kain batik cap (Lampiran.1) berdasarkan teori grup symetri dan kristalografi berdimensi dua. Ketigabelas corak kain batik cap yang berhasil dibuat ini merupakan penerapan dari 13 buah formulasi matematis gerakan pengecapan yang berhasil dirumuskan pada penelitian ini. Inilah keunggulan dari hasil penelitian ini, dari satu cap dapat diciptakan beragam corak kain batik cap, sehingga wajar kalau cap ini disebut cap ajaib (magic stamp). Pembahasan Formulasi pengecapan yang berhasil dirumuskan dalam penelitian ini dapat menghasilkan 13 corak kain batik cap, yang variasi coraknya tidak sebanyak jika dibandingkan dengan desain batik simetris (Kartono et al, 2000). Hal ini dikarenakan polygon bermotif dasar


109

Volume 2


yang digunakan dalam desain motif batik cap ini hanyalah berbentuk persegi tidak seperti pada desain batik simetris yang menggunakan polygon persegi, persegi panjang, maupun segitiga. Tema motif dasar pada cap (polygon persegi) yang dibuat terinspirasi oleh adanya kemunculan crop circle di Berbah Sleman pada tahun 2011 (Kartono et al, 2011). Motif dasar pada cap didesain terdiri dari lingkaran-lingkaran dengan beragam koordinat pusat dan jarijarinya. Bidang datar (selembar kain mori) diisi penuh oleh polygon-poligon kongruen (cap bermotif dasar) melalui pengoperasian generator gerakan (translasi, refleksi, rotasi, atau gliderefleksi), sehingga menghasilkan suatu corak batik cap. Dengan memulai pada polygon fundamental dan mengulanginya secara berulang-ulang menurut gerakan yang diperintahkan oleh generator gerakan maka keseluruhan bidang datar (selembar kain mori) dapat terisi penuh. Menurut Durbin (1985), corak batik cap yang dihasilkan ini merupakan grup simetri dari gambar yang dibentuk oleh sisi-sisi semua polygon (cap bermotif dasar) dan ketigabelas corak batik cap yang dihasilkan ini merupakan kristalografi berdimensi dua. Kain batik cap ini dapat dipandang sebagai sebuah obyek estetika berpola yang memiliki tata aturan penggambaran pseudo-algoritmik yang dapat diperlakukan sebagai bentuk seni generatif yang memiliki kegunaan memberikan inspirasi kepada peradaban umat manusia, khususnya dalam bidang perkembangan seni generatif itu sendiri. Seni generatif pada batik cap ini, selalu dapat dihubungkan dengan keindahan yang selalu melekat pada karya seni itu, yaitu berbagai bentuk keselarasan (harmoni) dari berbagai cara pengecapan secara berulang tersebut. Jadi sangat masuk akal kalau kain batik cap tersebut dikategorikan dalam suatu karya seni rupa generatif karena pola tersebut merupakan pola iteratif (berulang) yang digenerateoleh motif dasar. Ciri khas corak kain batik cap ini adalah pola iteratif yang terbentuk selalu mengawetkan keterhubungan (konektifitas). Dalam proses pembuatan kain batik cap ini, pengrajin mengeluh kesulitan dalam melakukan pengecapan yang dapat mengawetkan keterhubungan tersebut. Ketigabelas corak kain batik cap yang dihasilkan oleh pengrajin ini masih memperlihatkan adanya sambungan yang tidak sempurna, walaupun dalam pengerjaannya telah dilakukan dengan sabar dan penuh konsentrasi. Kesulitan lainnya adalah membuat seragam ketebalan tekstur kurvanya, namun ketidaksempurnaan inilah yang akan menjadi pembeda dengan produk tekstil bermotif batik (batik printing/ sablon). Jelaslah bahwa pola berulang (iteratif) dari motif dasar yang membentuk beragram corak akan menghasilkan bentuk fraktal sebagaimana pola berulang aritmatik sederhana dapat menghasilkan pola chaos. Seiring dengan perkembangan teknologi komputasi, sebagaimana dapat diterapkan untuk melihat pola aritmatika sederhana yang menghasilkan chaos dapat pula diterapkan untuk melihat pola geometri sederhana (motif dasar) yang menghasilkan fraktal. Upaya melihat fenomena fraktal pada corak batik cap yang dihasilkan ini akan memperluas pula khazanah dan peluang apresiasi yang lebih baik pada produk ini.

110



Volume 2

Penerapan teori grup simetri dan kristalografi berdimensi dua pada pembuatan motif dan kain batik cap ini juga dapat dipakai sebagai alat edukasi secara kreatif, inovatif, dan produktif dalam mempelajari transformasi geometris bidang, atau teori grup simetri dan kristalografi berdimensi dua. Titik atau bentuk obyek di bidang datar yang

biasanya

ditransformasikan dengan generator translasi, rotasi, refleksi, atau glide-refleksi diganti dengan motif batik. Pembelajaran matematika secara kreatif seperti ini akan sangat menyenangkan karena disamping belajar, peserta didik akan tahu manfaat nyata dari proses pembelajaran. Sambil bermain, juga belajar tentang transformasi bidang. bisa digunakan sebagai sarana permainan kreatifitas seperti bermain puzzle. Karena sistem kerja pengecapan yang berulangulang ini seperti menggunakan puzzle maka pembelajarannya lebih menyenangkan dan tidak membosankan. Sifat inovatif dalam pembelajaran ini terlihat pada motif batik cap yang didesain dengan melakukan inovasi dari satu motif dapat menghasilkan beragam corak. Pembelajaran ini juga bersifat produktif karena hasil proses pembelajaran ini tidak berhenti di atas kertas tetapi betul-betul diterapkan dan menghasilkan produk nyata. Proses pembelajaran seperti inilah yang diharapkan mampu melahirkan teknoprenuer, seperti yang diinginkan oleh Kurikulum SMA 2013. Diskusi dengan para pengrajin batik cap di Laweyan Surakarta menyarankan bahwa hasil penelitian ini masih perlu penyempurnaan produk dan perencanaan produksi yang cermat agar dapat menekan biaya produksi. Inovasi motif batik cap perlu dilakukan secara berkelanjutan dalam rangka pengembangan keanekaragaman motif karya seni generatif. Upayaupaya inilah yang harus selalu dilakukan sebagai langkah nyata dalam memberdayakan ekonomi lokal, mengembangkan potensi unggulan daerah dalam rangka

meningkatkan

kesejahteraan masyarakat.

SIMPULAN DAN SARAN Simpulan Penerapan teori grup simetri dan kristalografi berdimensi dua, khususnya transformasi geometris bidang datar (motif dasar bertema Crop Circle) dapat menghasilkan motif simetris batik cap dan beragam coraknya melalui pengecapan yang berulang. Penelitian ini berhasil membuat 13 formula pengecapan berulang yang menghasilkan 13 corak kain batik cap, Keseluruhan proses pembuatan kain batik cap ini merupakan media edukasi yang kreatif, inovatif dan produktif. Hasil

penelitian

dapat

diimplikasikan

untuk

mendukung

pengembangan

keanekaragaman motif maupun metode pengecapan batik cap, dan potensi unggulan daerah, yang diharapkan dapat menciptakan lapangan kerja baru sehingga dapat mendukung upaya mempercepat pengentasan kemiskinan dan meningkatkan kesejahteraan masyarakat. Pelibatan


111

Volume 2


pengrajin dalam keseluruhan proses penelitian ini semakin memperkaya pengetahuan dan keahliannya dalam menghasilkan produk kain batik cap.

Saran Prototip kain batik cap yang dihasilkan pada penelitian ini (dibukukan dalam product knowledge booklet) dapat ditindaklanjuti sebagai peningkatan daya saing dan perluasan pangsa pasar produk kain batik cap dalam rangka pemberdayaan ekonomi lokal. Peningkatan keahlian pengrajin dalam pengembangan moif, yang berbasis pada perkembangan ilmu pengetahuan, teknologi dan seni ini dapat menjadi inspirator dalam upaya mengembangkan teknoprenerteknoprener baru di industri kreatif batik cap atau merevitalisasi UMKM inovatif, yang merupakan salah satu pilar utama dalam pengembangan SIDa (Sistem Inovasi Daerah).

DAFTAR PUSTAKA 1. Durbin, J.R,

(1985), Modern Algebra : an Introduction, Second Edition, New

York:John Willey & Sons 2. Kartono, R. Heri Soelistyo Utomo, Harjito, (2000), Grup Simetri untuk Pengembangan Desain Motif Batik Simetris, Laporan penelitian dosen muda dengan nomor: 015/P2IPT/DM/VI/1999. 3. Kartono, Priyono, Budi Warsito, (2011), Menguak Misteri Crop Circle di Indonesia, Yogyakarta: Graha Ilmu, pp.41-53 4. Kartono, R.Heri Soelistyo Utomo, (2012),Pemberdayaan Ekonomi Lokal melalui Pengembangan Inovasi Jenis Produk Bordir di Kabupaten Kudus, Laporan

RUD

Balitbang Provinsi Jawa Tengah 5. Nurhilaliah, Ulfia Azmi, Kartono (Pembimbing), (2012), Pemanfaatan Limbah Kayu Sebagai Bahan Pembuatan Ukiran Bergerak Berbasis Transformasi

, Artikel Ilmiah

ISPO 2012

UCAPAN TERIMA KASIH Artikel ini merupakan sebagian dari hasil penelitian Hibah Bersaing Desentralisasi DIKTI tahun 2013, oleh karena itulah penulis mengucapkan terima kasih atas kesempatan penelitian yang diberikan. Ucapan terima kasih juga disampaikan kepada Batik Adityan Laweyan Surakarta yang telah bekerjasama dengan baik untuk menyelesaikan proses pembuatan cap dan kain batiknya.

112



Volume 2

LAMPIRAN: 10 CORAK KAIN BATIK CAP CROP CIRCLE


113

Volume 2

114




Volume 2

Eksistensi dan Karakterisasi Kontrol Optimal Vaksinasi Model Epidemi S I R dengan Laju Insidensi Jenuh yang Termodifikasi Rubono Setiawan Prodi Pendidikan Matematika Jurusan P.MIPA, F.KIP, Universitas Sebelas Maret Gedung D Lantai 3 Komplek Gedung F.KIP Kampus Kentingan Jalan Ir.Sutami No.36 A Kentingan Surakarta e-mail : [email protected] Abstrak Dalam paper ini digunakan model epidemi S I R ( Susceptible Invected Recovered) dasar ( Kermack & Mc. Kendrick ) dengan laju insidensi jenuh termodifikasi dan dengan beberapa asumsi tambahan lain. Strategi vaksinasi optimal dilakukan untuk meminimalkan jumlah individu pada kelompok individu rentan dan terinfeksi untuk kemudian memaksimalkan jumlah individu pada kelompok sembuh. Permasalahan optimasi yang dibentuk adalah meminimalkan fungsional tujuan yang memuat variabel kontrol, serta sistem persamaan diferensial yang dalam hal ini adalah model S I R sebagai kendala dalam permasalahan optimasi tersebut. Hamiltonian disusun berdasarkan Lagrangian dari permasalahan optimasi dan digunakan untuk membuktikan eksistensi serta menentukan kontrol yang optimal dari permasalahan optimasi. Kriteria minimum Pontryagin digunakan sebagai alat utama untuk menentukan kontrol yang optimal dan sistem yang optimal. Kata Kunci : Kontrol Optimal, Model S I R , Vaksinasi Optimal, Hamiltonian, Pontryagin

1. PENDAHULUAN Pembelajaran tentang dinamika penyakit menular merupakan bagian yang sangat penting dalam bidang matematika epidemiologi. Dengan mengerti lebih dalam tentang karakteristik dari penyebaran penyakit menular dalam suatu kelompok, daerah, masyarakat atau bahkan suatu negara, maka dapat ditemukan cara cara yang lebih baik dan sesuai untuk menekan penyebaran penyakit tertentu tersebut. Cara yang umum dikenal adalah dengan program vaksinasi yang sesuai dan program proteksi atau karantina. Model

penyebaran

penyakit

telah

banyak

dipelajari

oleh

banyak

penulis

1 , 2 , 3 , 5 , 6 . Cukup banyak diantaranya yang tertarik menggunakan bentuk laju insidensi jenuh dalam formulasi modelnya, seperti

6 , 5 , 3 . Bentuk laju insidensi jenuh

dapat digolongkan menjadi bentuk laju insidensi nonlinear. Salah satu kelebihan dari bentuk laju insidensi ini adalah adanya faktor jenuh yang ditentukan berdasarkan pengendalian epidemi. Pengendalian epidemi yang dimaksud adalah berdasarkan ukuran pencegahan yang sesuai terhadap penyakit atau pembawa ( vektor ) penyakit yang bersangkutan. Dalam hal ini pencegahan ataupun pengendalian dapat dilakukan oleh dan atau terhadap individu dalam kelompok individu rentan penyakit ataupun yang telah terjangkit penyakit. Bila hanya ada satu ukuran pencegahan misalnya dilakukan oleh individu rentan penyakit maka digunakan bentuk insidensi jenuh dengan satu faktor insidensi jenuh yang menunjukkan ukuran ukuran pencegahan atau

tindakan-tindakan prefentif yang sesuai dari individu sehat yang rentan

terkena penyakit , seperti yang telah digunakan dan dibahas oleh Zhang, dkk., 6 dan Setiawan,


115

Volume 2

Prosiding SNMPM Universitas Sebelas Maret 2013 𝑆𝐼

R., 5 yaitu berbentuk 𝛽 1+𝛼 𝑆. Kemudian juga terdapat bentuk laju insidensi yang lain yaitu 1

𝑆𝐼

𝛽 1+𝛼 𝐼, dalam bentuk insidensi ini menunjukkan bahwa jumlah kontak infektif antara individu 2

rentan dan individu terinfeksi dapat mengalami jenuh pada level infeksi yang tinggi karena tingkat kepadatan individu yang tinggi dalam kelompok terinfeksi atau karena ukuran ukuran proteksi yang dilakukan oleh kelompok individu rentan penyakit. Dalam paper ini akan digunakan bentuk insidensi jenuh yang dimodifikasi yang berbentuk

𝛽𝑆 𝑡 𝐼 𝑡 . 1+𝛼 1 𝑆 𝑡 +𝛼 2 𝐼(𝑡)

Dalam laju

insidensi tersebut memuat dua faktor insidensi jenuh yang tentunya mengakomodasi ukuran ukuran tindakan pencegahan, proteksi dan kejenuhan yang terjadi karena tingkat kepadatan penduduk yang tinggi. Model dasar yang digunakan pada makalah ini nantinya adalah model S I R ( Susceptible Invected Recovered ) dasar dengan beberapa asumsi- asumsi tambahan. Kemudian akan dibentuk suatu permasalahan optimasi yang melibatkan model berbentuk sistem persamaan diferensial sebagai kendala dari fungsi kontrol opimal vaksinasi yang merupakan fungsi tujuan ( biaya) dari permasalahan kontrol optimal tersebut. Dalam hal untuk menjabarkan permasalahan tersebut maka makalah ini ditulis dalam beberapa bab yang dimulai dengan materi pendukung tentang kontrol optimal sistem dinamik kontinu, fungsi biaya sebagai fungsi kontrol optimal vaksinasi. Kemudian dilajutkan dengan bab hasil dan pembahasan yang berisi tentang eksistensi kontrol optimal dan karakterisasi dari kontol optimal tersebut.

2.

METODE PENELITIAN

Metode penelitian untuk mendapatkan hasil dalam makalah ini adalah metode literatur dengan mengkaji makalah-makalah yang membahas penggunaan teori kontrol optimal pada model penyebaran penyakit. Model dasar yang digunakan adalah model S I R yang digunakan oleh Laarabi, dkk. 3 . Penelitian pengembangan dilakukan dengan menggunakan model yang menggunakan angka kematian yang berbeda pada tiap subkelas populasi.

3.

MATERI DAN TEORI PENDUKUNG

3.1. Bentuk Permasalahan Optimasi Kontol Optimal Sistem Dinamik Kontinu Tanpa mengurangi keumuman, akan dijelaskan bentuk umum permasalahan optimasi sistem dinamik kontinu untuk masalah minimasi fungsional kontrol. Misalkan diketahui 𝑥 adalah keadaan (state) dari sistem dinamik kontinu bersyarat awal 𝑥0 dan dengan input kontrol u sedemkian sehingga 𝑥 = 𝑓 𝑥, 𝑢 ,

𝑥 0 = 𝑥0 ,

𝑢 𝑡 ∈ 𝒰,

𝑡 ∈ 0, 𝑇

(3.1.1)

dengan 𝒰 adalah himpunan kontrol admissible, T adalah waktu final / akhir dari sistem. Dalam hal ini kontrol 𝑢 ∈ 𝒰 haruslah dipilih untuk semua 𝑡 ∈ 0, 𝑇 untuk meminimalkan fungsional 116



tujuan J

Volume 2

yang didefinisikan berdasarkan permasalahan nyata dalam aplikasi dan dapat

diabstraksikan sebagai 𝑇

𝐽=Ψ 𝑥 𝑇

+

𝐿 𝑥 𝑡 , 𝑥(𝑡) 𝑑𝑡

(3.1.2)

0

dengan L adalah Lagrangian. Kemudian kendala dalam sistem dinamik dapat digabung dengan Lagrangian L untuk mendapatkan vektor pengali Langrange 𝜆 yang sesuai dan nilainya berubah terhadap waktu, dimana masing – masing anggota 𝜆 disebut sebagai keadaan bersama (costate) dari sistem. Pengertian – pengertian tersebut sebagai dasar untuk mengkontruksi HamiltonianH yang didefinisikan untuk setiap 𝑡 ∈ 0, 𝑇 sebagai 𝐻 𝜆 𝑡 , 𝑥 𝑡 , 𝑢 𝑡 , 𝑡 = 𝐿 𝑥 𝑡 , 𝑢(𝑡) + 𝜆𝑇 𝑓 𝑥 𝑡 , 𝑢(𝑡)

(3.1.3)

dengan 𝜆𝑇 adalah transpose dari 𝜆. Selanjutnya Hamiltonian tersebut memengang peranan yang sangat penting untuk membuktikan eksistensi adanya kontrol yang optimal dan menentukannya dengan menggunakan prinsip minimum Pontryagin yang akan dijelaskan pada subbab selanjutnya.

3.2. Permasalahan Optimasi Kontrol Optimal Model Penyebaran Penyakit Dalam masalah penyebaran penyakit, hal yang pasti ingin diminimumkan adalah jumlah individu rentan dan individu terinfeksi penyakit sehingga jumlah individu sembuh dapat dimaksimumkan. Dalam usaha untuk mengendalikan penyebaran penyakit tersebut, salah satu cara yang umum dilakukan adalah vaksinasi, yaitu vaksinasi terhadap individu rentan ( pasif ) dan atau individu terinfeksi penyakit ( aktif ). Vaksinasi tersebut dapat diasosiasikan dengan suatu variabel kontrol u dan ditambahkan ke dalam model penyebaran penyakit yang bersangkutan. Dalam hal membentuk permasalahan optimasi kontrol optimal, jumlah individu rentan dan terinfeksi yang dikalikan dengan angka penyeimbang yang sesuai serta ditambah dengan fungsi biaya yang dibutuhkan dalam kegiatan vaksinasi akan diformulasikan menjadi fungsional tujuan yang akan diminimumkan, sedangkan model penyebaran penyakit yang berbentuk sistem persamaan diferensial nonlinear yang memuat variabel kontrol akan menjadi kendala ( constraint ) dalam permasalahan optimasi kontrol optimal tersebut.

3.3. Prinsip Minimum Pontryagin Prinsip-prinsip minimum Pontryagin diturunkan dari aslinya yaitu prinsip- prinsip maksimum Pontryagin. Prinsip tersebut ( baik maksimum maupun minimum) digunakan dalam teori kontrol optimal untuk menentukan kemungkinan kontrol terbaik untuk sistem dinamik yang telah ditentukan, dari keadaan satu ke keadaan yang lain, lebih khusus lagi apabila munculnya kendala-kendala untuk keadaan atau input kontrolnya. Prinsip tersebut pertama kali Makalah Pendamping: Matematika 1

117

Volume 2


diperkenalkan pada tahun 1956 oleh matematikawan Rusia Lev Semenovic Pontryagin dan murid-muridnya V.G. Boltyanskii, R.V. Gamkrelidze, 7 .Prinsip tersebut mempunyai bentuk khusus persamaan Euler dan Lagrange dari kalkulus variasi. Inti dari prinsip tersebut mengatakan bahwa Hamiltonian H yang dibentuk dari permasalahan optimasi ( dalam hal ini tanpa mengurangi keumuman diambil kasus untuk minimasi) kontrol optimal haruslah diminimumkan atas U, yaitu himpunan admissible control. Jika 𝑢∗ ∈ 𝑈 adalah kontrol yang optimal dari permasalahan optimasi, maka prinsip minimum Pontryagin mengatakan 𝐻 𝑥 ∗ 𝑡 , 𝑢∗ 𝑡 , 𝜆∗ 𝑡 , 𝑡 ≤ 𝐻 𝑥 ∗ 𝑡 , 𝑢(𝑡), 𝜆∗ 𝑡 , 𝑡 , ∀𝑢 ∈ 𝑈, 𝑡 ∈ 𝑡0 , 𝑡𝑒𝑛𝑑 , dengan 𝑥 ∗ ∈ 𝐶 1 𝑡0 , 𝑡𝑒𝑛𝑑

(3.3.1)

adalah trayektori keadaan (state) yang optimal, sedangkan 𝜆∗ ∈

𝐵𝑉 𝑡0 , 𝑡𝑒𝑛𝑑 ( Fungsi bervariasi terbatas pada 𝑡0 , 𝑡𝑒𝑛𝑑 ) adalah trayektori costate yang optimal. Kemudian prinsip tersebut juga diturunkan untuk kondisi khusus dari Hamiltonian, yaitu apabila waktu akhir 𝑡𝑒𝑛𝑑 ditentukan dan Hamiltonian tidak bergantung secara eksplisit terhadap waktu ( kondisi ekuilibrium terhadap waktu ,

𝜕𝐻 𝜕𝑡

𝐻 𝑥 ∗ 𝑡 , 𝑢∗ 𝑡 , 𝜆∗ 𝑡

≡ 0 ), maka prinsip minimum Pontryagin – nya adalah

≡ konstan,

(3.3.2)

dan kemudian jika waktu akhir tidak ada maka 𝐻 𝑥 ∗ 𝑡 , 𝑢∗ 𝑡 , 𝜆∗ 𝑡

≡ 0.

(3.3.3)

Selanjutnya akan dijelaskan syarat perlu untuk masalah minimasi kontrol optimal berdasar prinsip minimum Pontryagin. Berdasarkan bentuk formal dari permasalahan minimasi kontrol optimal (3.1.2) dengan kendala (3.1.1), maka prinsip minimum Pontryagin mengatakan bahwa trayektori keadaan (state) optimal 𝑥 ∗ , kontrol optimal 𝑢∗ dan vektor pengali Lagrange 𝜆∗ yang sesuai haruslah meminimalkan Hamiltonian H sedemikian sehingga i.

𝐻 𝑥 ∗ 𝑡 , 𝑢∗ 𝑡 , 𝜆∗ 𝑡 , 𝑡 ≤ 𝐻 𝑥 ∗ 𝑡 , 𝑢(𝑡), 𝜆∗ 𝑡 , 𝑡 , ∀𝑢 ∈ 𝑈, 𝑡 ∈ 𝑡0 , 𝑡𝑒𝑛𝑑

dan haruslah

memenuhi kondisi ii. Ψ𝑇 𝑥 𝑇

+ 𝐻 𝑇 = 0, dengan Ψ𝑇 𝑥 𝑇

=

𝜕Ψ 𝑥 𝜕𝑇 𝑥=𝑥 𝑇

,

sebagai tambahan persamaan keadaan bersama ( costate ) iii.

−𝜆𝑇 𝑡 = 𝐻𝑥 𝑥 ∗ 𝑡 , 𝑢∗ 𝑡 , 𝜆∗ 𝑡 , 𝑡 = 𝜆𝑇 𝑡 𝑓𝑥 𝑥 ∗ 𝑡 , 𝑢∗ 𝑡

+ 𝐿𝑥 𝑥 ∗ 𝑡 , 𝑢 ∗ 𝑡

harus

juga dipenuhi, dengan 𝐻𝑥 𝑥 ∗ , 𝑢∗ , 𝜆∗ = 𝐿𝑥 𝑥 ∗ , 𝑢 ∗ =

118

𝜕𝐻 𝜕𝑥1

𝜕𝐿 𝜕𝑥1

… 𝑥=𝑥 ∗ ,𝑢=𝑢 ∗ ,𝜆=𝜆 ∗

… 𝑥=𝑥 ∗ ,𝑢=𝑢 ∗

𝜕𝐿 𝜕𝑥𝑛

𝜕𝐻 𝜕𝑥𝑛

𝑥=𝑥 ∗ ,𝑢=𝑢 ∗ ,𝜆=𝜆 ∗

𝑥=𝑥 ∗ ,𝑢=𝑢 ∗



𝜕𝑓1 𝜕𝑥1 ∗

𝑓𝑥 𝑥 , 𝑢

∗

=

𝑥=𝑥 ∗ ,𝑢=𝑢 ∗

⋮ 𝜕𝑓𝑛 𝜕𝑥1

𝜕𝑓1 𝜕𝑥𝑛

… ⋱

𝑥=𝑥 ∗ ,𝑢=𝑢 ∗

Volume 2

𝑥=𝑥 ∗ ,𝑢=𝑢 ∗

⋮

𝜕𝑓𝑛 … 𝜕𝑥𝑛

𝑥=𝑥 ∗ ,𝑢=𝑢 ∗ 𝜕𝐻

Jika waktu akhir / final 𝑥(𝑇) tidak diketahui nilainya secara pasti ( 𝜕𝑡 ≠ 0) maka haruslah berlaku iv.

𝜆𝑇 𝑇 = Ψ𝑥 𝑥 𝑇 .

Keempat kondisi di atas merupakan syarat perlu untuk adanya kontrol optimal, tetapi syarat ke empat hanya digunakan ketika sistem tidak memiliki 𝑥 𝑇 . Jika 𝑥 𝑇 nilainya diketahui pasti (fixed) maka kondisi ke empat bukanlah kondisi perlu untuk adanya kontrol optimal.

4. HASIL DAN PEMBAHASAN 4.1. Formulasi Model SIR dengan Laju Insidensi Jenuh Termodifikasi Dalam subbab ini akan diformulasikan model SIR dengan beberapa asumsi tambahan baru, dinama berdasarkan modelSIR tersebut akan dianalisa eksistensi dan karakterisasi kontrol optimal tindakan vaksinasi. Model SIR yang digunakan adalah model SIR berdasarkan model SIR yang ditulis oleh Laarabi, dkk. 3 , tetapi dengan modifikasi pada angka kematian alami pada tiap kelas. Jika model SIR dalam 3 digunakan laju kematian alami yang pasti sama pada tiap kelas, maka pada model di paper ini digunakan laju kematian alami yang memungkinkan berbeda pada tiap kelas individu. Model SIR tersebut menggunakan laju insidensi jenuh yang menggunakan dua faktor insidensi jenuh. Berikut ini model SIR selengkapnya yang disajikan dalam sistem persamaan diferensial autonomos

𝑆 =𝐴− 𝐼=

𝛽𝑆𝐼 − 𝜇1 𝑆 1 + 𝛼1 𝑆 + 𝛼2 𝐼

𝛽𝑆𝐼 − 𝛿 + 𝜇2 + 𝛾 𝐼 1 + 𝛼1 𝑆 + 𝛼2 𝐼

(4.1.1)

𝑅 = 𝛾𝐼 − 𝜇3 𝑅 𝑁 =𝑆+𝐼+𝑅 dengan syarat awal 𝑆 0 = 𝑆0 ≥ 0, 𝐼 0 = 𝐼0 ≥ 0, 𝑅 0 = 𝑅0 ≥ 0. Dalam model SIR tersebut di atas konstanta A adalah angka masukan (recruitment) populasi, 𝛽 adalah angka kontak (transmisi), 𝜇1 , 𝜇2 , 𝜇3 masing – masing adalah angka kematian alami individu pada kelas rentan (S), kelas terinfeksi (I) dan kelas sembuh (R), sedangkan 𝛿 adalah angka kematian akibat pengaruh penyakit, kemudian yang terakhir adalah konstanta 𝛾 adalah angka kesembuhan dari individu – individu yang terinfeksi. Makalah Pendamping: Matematika 1

119

Volume 2


4.2. Formulasi Model dengan Kontol Optimal Vaksinasi Teknik kontrol optimal adalah cara yang banyak digunakan dalam hal mengembangkan strategi untuk mengontrol berbagai jenis penyakit. Salah satu strategi tersebut adalah strategi vaksinasi yang optimal. Tujuan utama dari strategi tersebut adalah untuk mengurangi jumlah individu rentan dan individu terinfeksi penyakit serta meningkatkan jumlah individu yang sembuh. Guna merumuskan permasalahan kontrol optimal maka akan dibutuhkan variabel kontrol 𝑢 𝑡 ∈ 𝑈𝑘𝑜𝑛𝑡𝑟𝑜𝑙 yang merupakan persentase dari individu – individu yang telah tervaksinasi per satuan waktu. Kemudian 𝑈𝑘𝑜𝑛𝑡𝑟𝑜𝑙 didefinisikan dalam bentuk himpunan admissible control ( lihat 1 ) sebagai berikut : 𝑈𝑘𝑜𝑛𝑡𝑟𝑜𝑙 = 𝑢 𝑢 𝑡 terukur, 0 ≤ 𝑢 𝑡 ≤ 𝑢𝑚𝑎𝑥 < ∞, 𝑡 ∈ 0, 𝑡𝑒𝑛𝑑

(4.2.1)

Dalam tulisan ini diasumsikan adanya penyederhanaan pada variable kontrol yaitu 0 ≤ 𝑢(𝑡) ≤ 𝑢𝑚𝑎𝑥 7 . Hal tersebut menurut Laarabi, dkk. 3 . Dikarenakan tidak mungkin untuk melakukan vaksinasi untuk semua individu yang masuk kelas rentan penyakit dalam satu waktu. Kemudian arti fisik dari variabel kontrol dalam masalah ini adalah jika jumlah individu rentan dan terinfeksi mencapai level yang redah, maka jumlah individu sembuh akan meningkat. Berdasarkan uraian tersebut di atas maka tujuan dari permasalahan optimasi yang akan dibentuk adalah menimalkan jumlah individu rentan dan terinfeksi untuk meningkatkan jumlah individu sembuh. Setelah menentukan formulasi model SIR di atas, maka selanjutnya akan ditentukan permasalahan optimasi dengan melibatkan model SIR dengan laju insidensi jenuh sebagai kendala dan kontrol optimal vaksinasi sebagai fungsi tujuan untuk meminimalkan jumlah individu terinfeksi dan juga individu rentan yang kemudian memaksimalkan jumlah individu sembuh, yang dalam hal ini individu yang tervaksinasi akan langsung masuk ke dalam kelas sembuh. Kontrol optimal yang digunakan dalam paper ini menggunakan kontrol optimal yang digunakan oleh Laarabi, dkk. 3 . Berikut permasalahan optimasi selengkapnya.

Meminimalkan 𝑡 𝑒𝑛𝑑

𝐽 𝑢 = 0

1 𝐴1 𝑆 𝑡 + 𝐴2 𝐼 𝑡 + 𝜏𝑢2 𝑡 𝑑𝑡 2

(4.2.2)

dengan kendala

𝑆(𝑡) = 𝐴 − 𝜇1 + 𝑢 𝑡 𝑆(𝑡) −

120

𝛽𝑆 𝑡 𝐼(𝑡) 1 + 𝛼1 𝑆(𝑡) + 𝛼2 𝐼(𝑡)



𝐼(𝑡) =

Volume 2

𝛽𝑆 𝑡 𝐼(𝑡) − 𝛿 + 𝜇2 + 𝛾 𝐼(𝑡) 1 + 𝛼1 𝑆(𝑡) + 𝛼2 𝐼(𝑡)

(4.2.3)

𝑅(𝑡) = 𝛾𝐼 𝑡 − 𝜇3 𝑅 𝑡 + 𝑢 𝑡 𝑆(𝑡) dan dengan syarat awal 𝑆 0 = 𝑆0 ≥ 0, 𝐼 0 = 𝐼0 ≥ 0, 𝑅 0 = 𝑅0 ≥ 0. Dalam Persamaan fungsi tujuan (4.2.2) suku 𝑆(𝑡) dan 𝐼 𝑡 merepresentasikan hasil capaian 𝑆(𝑡) dan 𝐼(𝑡) yang ingin dikurangi, kemudian konstanta – konstanta positif

𝐴1 dan 𝐴2 masing – masing

dimaksudkan untuk menjaga keseimbangan besar 𝑆(𝑡) dan 𝐼 𝑡 . Dalam banyak kontrol optimal yang terjadi membutuhkan biaya, tetapi dalam hal ini kita tidak mempunyai data yang cukup untuk menentukan biaya secara pasti yang berhubungan dengan kontrol vaksinasi, oleh karena itu dalam tulisan ini difokuskan dalam hal penggunaan “ biaya relatif ” (relative cost) untuk kontrol. Dalam Persamaan (4.2.1) digunakan suku kuadrat

1 𝜏𝑢2 , 2

dimana konstanta 𝜏 adalah

angka beban yang berkaitan dengan kontrol 𝑢(𝑡) dan dalam hal ini kontrol kuadrat mencerminkan tingkat keparahan efek samping dari vaksinasi (Joshi, 2 , dalam Laarabi, dkk. 3 .)

4.3. Eksistensi Penyelesaian Dalam subbab ini akan dianalisa eksistensi penyelesaian dari Sistem (4.2.3). Pertama, Sistem (4.2.3) akan ditulis dalam sistem nonlinear dengan koefisien terbatas adalah : 𝜙𝑡 = 𝐵𝜙 + 𝐹 𝜙 𝑅(𝑡) 𝑇 ;

dengan 𝜙 = 𝑆 𝑡 𝐼 𝑡

𝐵=

(4.3.1)

− 𝜇1 + 𝑢 𝑡 0 𝑢 𝑡

0 − 𝛿 + 𝜇2 + 𝛾 𝛾

0 0 , −𝜇3

𝛽𝑆 𝑡 𝐼(𝑡) 1 + 𝛼1 𝑆(𝑡) + 𝛼2 𝐼(𝑡) 𝛽𝑆 𝑡 𝐼(𝑡) 1 + 𝛼1 𝑆(𝑡) + 𝛼2 𝐼(𝑡) 0

𝐴− 𝐹 𝜙 =

dan 𝜙𝑡 adalah turunan dari 𝜙 terhadap waktu t . Kemudian dibentuk operator D dengan definisi sebagai berikut 𝐷 𝜙 = 𝐵𝜙 + 𝐹 𝜙 Diambil sebarang 𝜙1 dan 𝜙2 anggota himpunan penyelesaian dari Sistem kemudian

𝐹 𝜙1 − 𝐹 𝜙2

= 2𝛽 = 2𝛽

𝑆2 𝐼2 1 + 𝛼1 𝑆1 + 𝛼2 𝐼1 − 𝑆1 𝐼1 1 + 𝛼1 𝑆2 + 𝛼2 𝐼2 1 + 𝛼1 𝑆1 + 𝛼2 𝐼1 1 + 𝛼1 𝑆2 + 𝛼2 𝐼2

𝑆2 𝐼2 1 + 𝛼1 𝑆1 + 𝛼2 𝐼1 − 𝑆1 𝐼1 1 + 𝛼1 𝑆2 + 𝛼2 𝐼2 1 + 𝛼1 𝑆1 + 𝛼2 𝐼1 1 + 𝛼1 𝑆2 + 𝛼2 𝐼2


121

Volume 2


≤ 2𝛽 𝑆2 𝐼2 1 + 𝛼1 𝑆1 + 𝛼2 𝐼1 − 𝑆1 𝐼1 1 + 𝛼1 𝑆2 + 𝛼2 𝐼2 ≤ 2𝛽 𝑆2 𝐼2 + 𝛼1 𝑆1 𝑆2 𝐼2 + 𝛼2 𝐼1 𝑆2 𝐼2 − 𝑆1 𝐼1 − 𝛼1 𝑆2 𝑆1 𝐼1 − 𝑆1 𝐼1 𝛼2 𝐼2 ≤ 2𝛽 𝛼1 𝑆1 𝑆2 𝐼2 − 𝐼1 + 𝛼2 𝐼1 𝐼2 𝑆2 − 𝑆1 + 𝑆2 𝐼2 − 𝑆1 𝐼1 ≤ 2𝛽 𝛼1 𝑆1 𝑆2 𝐼2 − 𝐼1 + 𝛼2 𝐼1 𝐼2 𝑆2 − 𝑆1 + 𝑆2 𝐼2 − 𝐼1 + 𝐼1 𝑆2 − 𝑆1 ≤ 2𝛽 𝛼1 𝑆1 𝑆2 𝐼2 − 𝐼1 + 𝛼2 𝐼1 𝐼2 𝑆2 − 𝑆1 + 𝑆2 𝐼2 − 𝐼1 + 𝐼1 𝑆2 − 𝑆1

≤ 2𝛽 𝛼1 +

𝐴 𝜇1

𝐴 𝜇1

2

𝐼2 − 𝐼1 + 𝛼2

𝑆2 − 𝑆1

𝐴 𝜇1

2

𝑆2 − 𝑆1 +

𝐴 𝜇1

𝐼2 − 𝐼1

∗∗

≤ 𝑀 𝑆2 − 𝑆1 + 𝐼2 − 𝐼1 dengan 𝑀 = 2𝛽max 𝛼1

𝐴 2 𝜇1

(∗)

+

𝐴 𝜇1

, 𝛼2

(4.3.2) 𝐴 2 𝜇1

+

𝐴 𝜇1

.

Dalam pertidaksamaan (4.3.2), berdasarkan (*) apabila dicari penyelesaian untuk dinamika S sebelum dikurangi dengan suku insidensi dan penyelesaian tersebut diambil untuk 𝑡 → ∞ maka akan diperoleh kesimpulan bahwa jumlah individu S terbatas pada individu I juga pasti tidak akan lebih dari

𝐴 . 𝜇1

𝐴 , 𝜇1

lebih lanjut jumlah

Berdasarkan Pertidaksamaan (4.3.2) akan

didapatkan hubungan : 𝐷 𝜙1 − 𝐷 𝜙2 dengan

𝐾 = max 𝑀, 𝐵

< ∞.

≤ 𝐾 𝜙1 − 𝜙2

(4.3.3)

Berdasarkan Pertidaksamaan (4.3.3) D adalah kontinu

Lipschitz seragam, lebih lanjut ditambah dengan definisi dari kontrol 𝑢(𝑡) serta pembatasan pada 𝑆 𝑡 , 𝐼 𝑡 , 𝑅 𝑡 ≥ 0, maka dapat kita simpulkan bahwa penyelesaian dari Sistem (4.3.1) ada.

4.4. Eksistensi Kontrol yang Optimal Setelah memuktikan eksistensi penyelesaian dari Sistem (4.3.2), selanjutnya akan dibuktikan eksistensi dari kontrol optimal. Sebelumnya akan ditentukan terlebih dahulu Lagrangian dan Hamiltonian dari permasalahan optimasi (4.2.2) – (4.2.3). Langrangian dari permasalahan optimasi tersebut adalah 1 𝐿 𝑆, 𝐼, 𝑢 = 𝐴1 𝑆 𝑡 + 𝐴2 𝐼 𝑡 + 𝜏𝑢2 𝑡 2

122

(4.4.1)



Volume 2

Selanjutnya untuk mencari nilai minimum dari Lagrangian (4.4.1) maka dibentuklah Hamiltonian H untuk permasalahan kontrol optimal. Hamiltonial dari permasalahan optimasi (4.2.2) – (4.2.3) adalah 𝐻 𝑥 𝑡 ,𝑢 𝑡 ,𝜆 𝑡 ,𝑡 = 𝑓 𝑥 𝑡 ,𝑢 𝑡 ,𝑡 + 𝜆 𝑡 𝑔 𝑥 𝑡 ,𝑢 𝑡 ,𝑡

(4.4.2)

dengan 𝑓 𝑡, 𝑥 𝑡 , 𝑢(𝑡) adalah integran fungsi tujuan, 𝜆(𝑡) adjoint dan 𝑔 𝑡, 𝑥 𝑡 , 𝑢 𝑡

adalah

ruas kanan dari sistem persamaan diferensial biasa yang sebagai model S I R. Bentuk (4.4.2) apabila disesuaikan dengan model yang telah terformulasikan maka dapat ditulis sebagai 𝐻 𝑆, 𝐼, 𝑅, 𝑢, 𝜆1 , 𝜆2 , 𝜆3 , 𝑡 = 𝐿 𝑆, 𝐼, 𝑢 + 𝜆1

𝑑𝑆(𝑡) 𝑑𝐼(𝑡) 𝑑𝑅(𝑡) + 𝜆2 + 𝜆3 𝑑𝑡 𝑑𝑡 𝑑𝑡

(4.4.3)

dalam hal ini 𝜆1 , 𝜆2 dan 𝜆3 adalah fungsi-fungsi adjoint yang sesuai. Untuk penjaminan adanya kontrol optimal dari permasalahan optimasi (4.2.2) – (4.2.3), akan dijelaskan lewat teorema berikut : Teorema 4.4.1.Terdapat suatu kontrol optimal 𝑢∗ 𝑡 sedemikian sehingga 𝐽 𝑢∗ 𝑡

= 𝑚𝑖𝑛 𝐽 𝑢(𝑡) 𝑢∈𝑈

dengan kendala Sistem (4.2.3) dengan syarat awal.

Bukti :

Variabel kontrol dan variabel keadaan (state variable) dari sistem semuanya bernilai tak negatif. Kemudian suku 𝑢(𝑡) pada fungsional fungsi tujuan bersifat konvek yang merupakan syarat perlu untuk masalah minimasi. Berdasarkan definisi dari ruang kontrol sendiri maka ruang kontrol (4.2.1) juga konvek dan tertutup. Karena sistem optimal (4.2.3) terbatas maka juga memenuhi sifat kekompakan yang diperlukan untuk eksistensi kontrol yang optimal. Selain itu 1

integran dalam fungsional (4.2.2) , 𝐴1 𝑆 𝑡 + 𝐴2 𝐼 𝑡 + 2 𝜏𝑢2 𝑡 juga konveks pada suku kontrol 𝑢(𝑡). Kemudian dapat dengan dibuktikan bahwa terdapat konstanta 𝜌 > 1, bilangan positif 𝜔1 dan 𝜔2 sedemikian sehingga 𝐽 𝑢(𝑡) ≥ 𝜔2 + 𝜔1 𝑢

2

𝜌

2.

Berdasarkan uraian tersebut dapat disimpulkan bahwa terdapat kontrol optimal untuk permasalahan optimasi (4.2.2) – (4.2.3).

4.5.

Q.E.D.

Karakterisasi dan Penentuan Kontrol yang Optimal

Eksistensi adanya kontrol yang optimal dari permasalahan optimasi (4.2.2) – (4.2.3) telah dibuktikan

pada subbab sebelumnya, kemudian untuk menentukan kontrol yang optimal


123

Volume 2


tersebut akan digunakan prinsip minimum Pontryagin 𝑥 ∗ 𝑡 , 𝑢∗ 𝑡

pada Hamiltonian (4.4.2). Jika

adalah solusi optimal dari permasalahan optimasi kontrol optimal, maka terdapat yang memenuhi persamaan –

fungsi vektor nontrivial 𝜆 𝑡 = 𝜆1 𝑡 , 𝜆2 𝑡 , … , 𝜆𝑛 𝑡 𝑡 persamaan berikut :

𝑥′ 𝑡 =

𝜕𝐻 𝑥 ∗ 𝑡 , 𝑢∗ 𝑡 , 𝜆 𝑡 , 𝑡 𝜕𝜆

4.5.1

𝜕𝐻 𝑥 ∗ 𝑡 , 𝑢∗ 𝑡 , 𝜆 𝑡 , 𝑡 𝜕𝑢 ∗ ∗ 𝜕𝐻 𝑥 𝑡 , 𝑢 𝑡 , 𝜆 𝑡 , 𝑡 𝜆′ 𝑡 = − 𝜕𝑥 0=

4.5.2 (4.5.3)

Berdasarkan sifat dari ruang kontrol 𝑢∗ 𝑡 = 0, 𝑢∗ 𝑡 ∈ 0, 𝑢𝑚𝑎𝑥 𝑢∗ 𝑡 = 𝑢𝑚𝑎𝑥 ,

𝜕𝐻 <0 𝜕𝑢 𝜕𝐻 , jika =0 𝜕𝑢 𝜕𝐻 jika >0 𝜕𝑢 jika

4.5.4 dan hasil dalam Persamaan (4.5.2) maka 𝑢∗ 𝑡 ∈ 0, 𝑢𝑚𝑎𝑥 . Teorema 4.5.1.Jika 𝑆 ∗ 𝑡 , 𝐼 ∗ 𝑡 dan 𝑅 ∗ (𝑡) adalah keadaan optimal yang berhubungan dengan variabel kontrol yang optimal 𝑢∗ 𝑡 dari permasalahan optimasi (4.2.2) – (4.2.3),

maka

terdapat variabel adjoint ( pengali Lagrange) 𝜆1 , 𝜆2 dan 𝜆3 yang sesuai dan memenuhi 𝑑𝜆1 𝑡 = −𝐴1 + 𝜆1 𝑡 𝜇1 + 𝑢 𝑡 + 𝜌1 − 𝜆2 𝑡 𝜌1 − 𝜆3 𝑡 𝑢 𝑡 , 𝑑𝑡 𝑑𝜆2 = −𝐴2 + 𝜆1 𝑡 𝜌2 − 𝜆2 𝑡 𝜌2 − 𝛿 + 𝜇2 + 𝛾 − 𝜆3 𝑡 𝛾, 𝑑𝑡 𝑑𝜆3 𝑡 = 𝜆3 𝑡 𝜇3 , 𝑑𝑡 dengan 𝜌1 =

𝛽𝐼 1 + 𝛼2 𝐼 , 1 + 𝛼1 𝑆 + 𝛼2 𝐼 2

𝜌2 =

𝛽𝑆 1 + 𝛼2 𝑆 1 + 𝛼1 𝑆 + 𝛼2 𝐼

2

,

dan kondisi transversal 𝜆𝑖 𝑡𝑒𝑛𝑑 = 0,

𝑖 = 1,2,3.

Lebih lanjut, kontrol optimal 𝑢∗ 𝑡 yang diberikan untuk

124



𝑢∗ 𝑡 = 𝑚𝑎𝑥 𝑚𝑖𝑛

Volume 2

𝜆1 𝑡 − 𝜆3 𝑆 ∗ 𝑡 , 𝑢𝑚𝑎𝑥 , 0 . 𝜏

Bukti Akan digunakan persamaan Hamiltonian (4.4.3) untuk membuktikan persamaan – persamaan adjoint dan kondisi transversal. Jika diambil 𝑆 𝑡 = 𝑆 ∗ 𝑡 , 𝐼 𝑡 = 𝐼 ∗ 𝑡 , 𝑅 𝑡 = 𝑅 ∗ 𝑡 dan kemudian melakukan diferensiasi terhadap Hamiltonian H terhadap S, I dan R, serta berdasarkan syarat perlu ( syarat iii ) untuk prinsip minimum Pontryagin maka akan didapat 𝑑𝜆1 𝑡 𝜕𝐻 =− = −𝐴1 + 𝜆1 𝑡 𝜇1 + 𝑢 𝑡 + 𝜌1 − 𝜆2 𝑡 𝜌1 − 𝜆3 𝑡 𝑢 𝑡 𝑑𝑡 𝜕𝑆 𝑑𝜆2 𝑡 𝜕𝐻 =− = −𝐴2 + 𝜆1 𝑡 𝜌2 − 𝜆2 𝑡 𝜌2 − 𝛿 + 𝜇2 + 𝛾 − 𝜆3 𝑡 𝛾 𝑑𝑡 𝜕𝐼 𝑑𝜆3 𝑡 𝜕𝐻 =− = 𝜆3 𝑡 𝜇3 𝑑𝑡 𝜕𝑅 dengan 𝜌1 =

𝛽𝐼 1 + 𝛼2 𝐼 , 1 + 𝛼1 𝑆 + 𝛼2 𝐼 2

𝜌2 =

𝛽𝑆 1 + 𝛼2 𝑆 1 + 𝛼1 𝑆 + 𝛼2 𝐼

2

Selanjutnya dengan menggunakan kondisi optimal untuk Hamiltonian, maka akan didapat hubungan 𝜕𝐻 =0 𝜕𝑢 𝜕𝐻 ⇔ = 𝜏𝑢∗ 𝑡 − 𝜆1 𝑡 𝑆 ∗ + 𝜆3 𝑡 𝑆 ∗ 𝑡 = 0, 𝜕𝑢

di 𝑢 = 𝑢∗ 𝑡 ,

dan dihasilkan 𝑢∗ 𝑡 =

𝜆1 𝑡 − 𝜆3 𝑆 ∗ 𝑡 . 𝜏

Kemudian jika menggunakan sifat dari ruang kontrol, akan didapatkan hubungan 𝜆1 𝑡 − 𝜆3 𝑆 ∗ 𝑡 ≤0 𝜏 𝜆1 𝑡 − 𝜆3 𝑆 ∗ 𝑡 𝜆1 𝑡 − 𝜆3 𝑆 ∗ 𝑡 𝑢∗ 𝑡 = , jika 0 < < 𝑢𝑚𝑎𝑥 𝜏 𝜏 𝜆1 𝑡 − 𝜆3 𝑆 ∗ 𝑡 𝑢∗ 𝑡 = 𝑢𝑚𝑎𝑥 , jika >0 𝜏 𝑢∗ 𝑡 = 0,

jika

Jadi, kontrol yang optimal dari permasalahan optimasi (4.2.2) – (4.2.3) dapat dikarakterisasi sebagai


125

Volume 2


𝑢∗ 𝑡 = 𝑚𝑎𝑥 𝑚𝑖𝑛

𝜆1 𝑡 − 𝜆3 𝑆 ∗ 𝑡 , 𝑢𝑚𝑎𝑥 , 0 . 𝜏 Q.E.D.

Suatu sistem yang optimal dari permasalahan optimasi kontrol otpimal terdiri atas keadaan dari sistem ( state sytem ) yang berpasangan dengan adjoint dari sistem ( vektor pengali Lagrange ) dengan kondisi awal dan kondisi transversal bersama beserta karakterisasi dari kontrol optimal tersebut. Berdasarkan karakterisasi dari kontrol optimal yang telah dijelaskan dalam Teorema (4.5.1) maka didapat sistem optimal dari permasalahan optimasi (4.2.2) – (4.2.3) 𝑆 ∗ = 𝐴 − 𝜇1 + 𝑢∗ 𝑆 ∗ −

𝛽𝑆 ∗ 𝐼 ∗ 1 + 𝛼1 𝑆 ∗ + 𝛼2 𝐼 ∗

𝛽𝑆 ∗ 𝐼 ∗ 𝐼 = − 𝛿 + 𝜇2 + 𝛾 𝐼 ∗ 1 + 𝛼1 𝑆 ∗ + 𝛼2 𝐼 ∗ ∗

𝑅 ∗ = 𝛾𝐼 ∗ − 𝜇3 𝑅 ∗ + 𝑢∗ 𝑆 ∗ 𝜆1 = −𝐴1 + 𝜆1 𝜇1 + 𝑢∗ + 𝜆2 = −𝐴2 + 𝜆1

𝛽𝐼 ∗ 1 + 𝛼2 𝐼 ∗ 1 + 𝛼1 𝑆 ∗ + 𝛼2 𝐼 ∗

𝛽𝑆 ∗ 1 + 𝛼2 𝑆 ∗ 1 + 𝛼1 𝑆 ∗ + 𝛼2 𝐼 ∗

− 𝜆2 2

2

− 𝜆2

𝛽𝐼 ∗ 1 + 𝛼2 𝐼 ∗ 1 + 𝛼1 𝑆 ∗ + 𝛼2 𝐼 ∗

𝛽𝑆 ∗ 1 + 𝛼2 𝑆 ∗ 1 + 𝛼1 𝑆 ∗ + 𝛼2 𝐼 ∗

2

2

− 𝜆3 𝑢 ∗

− 𝛿 + 𝜇2 + 𝛾

− 𝜆3 𝛾

𝜆3 = 𝜆3 𝜇3 4.5.5

5.

PENUTUP

Berdasarkan uraian dan penjelasan pada bab hasil dan pembahasan dapat diambil kesimpulan terdapat suatu kontrol optimal untuk permasalahan optimasi (4.2.2) – (4.2.3) menentukannya digunakan prinsip-prinsip minimum Pontryagin

dan untuk

pada Hamiltonian

yang

terbentuk. Dengan ditemukannya kontrol optimal tersebut, maka juga ditemukan keadaan sistem persamaan diferensial ( model S I R ) dan vektor pengali Langrange yang sesuai untuk terpenuhinya fungsi tujuan yang minimum yaitu meminimumkan jumlah individu rentan dan terifeksi sehingga otomatis akan memaksimumkan jumlah individu yang sembuh, selain itu juga meminimukan biaya ( cost ) relatif dari tindakan vaksinasi, sehingga pada akhirnya akan ditemukan sistem yang optimal dari permasalahan optimasi (4.2.2) – (4.2.3) yaitu Sistem (4.5.5)

6.DAFTAR PUSTAKA 1 Chachuat, B., Optimal Control Lecture 17-18 : Problem Formulation, Department of Chemical Engineering, McMaster University, (2009)., diakses pada 12 september 2013. 2

Joshi, H.R., “ Optimal Control of An HIV Immunology Model “, Optim. Control Appl. Methods, 23, pp. 199 – 213, (2002).

126



Volume 2

3 Laarabi, H.,Labriji, E.H.,Rachik, M.,Kaddar, A.,”Optimal Control of An Epidemic Model with A Saturated Incidence Rate”, Nonlinear Analysis : Modelling and Control, Vol.17, No.4, pp. 448 – 459, (2012). 4

Luenberger, D.G., Optimization by Vector Space Methods, John Wiley and Sons, Inc., USA, (1969)

5

Setiawan, R., Widodo, Aryati, L.,” Stability Analysis of Delayed S I R Epidemic Model With Saturated Incidence”, Presented on International Conference on Algebra (ICA) UGM Yogyakarta,Yogyakarta, Indonesia, (2010).

6

Zhang, J-Z. ; Jin,Z. ; Liu, Q –X. ; dan Zhang, Z-Y., Analysis of a Delayed SIR Model with Nonlinear Incidence , Discrete Dynamics in Nature and Society, Hindawi Publishing Corporation , Vol. 2008, Article ID 636153, (2008).

7 -------, Pontryagin’s Minimum Principle, Wikipedia the free encyclopedia, diakses di http://en.wikipedia.org/wiki/Pontryagin’s_minimum_principle 29 September 2013.


127

Volume 2


ANALISIS KAPASITAS MAKSIMUM LINTASAN DENGAN PENDEKATAN ALJABAR MAX-MIN M. Andy Rudhito1) 1) Program Studi Pendidikan Matematika FKIP Universitas Sanata Dharma Kampus III USD Paingan Maguwoharjo Yogyakarta, e-mail: [email protected] Abstract Artikel ini membahas suatu metode analisis kapasitas maksimum lintasan dalam suatu jaringan dengan menggunakan pendekatan aljabar max-min. Pembahasan merupakan hasil kajian teoritis yang didasarkan literatur dan suatu perhitungan menggunakan program MATLAB. Hasil pembahasan menunjukkan bahwa jaringan yang memuat kapasitas, dapat dimodelkan sebagai graf berarah terbobot, di mana bobotnya adalah kapasitas dalam jaringan. Graf berarah terbobot di atas dapat dinyatakan dalam matriks atas aljabar maxmin. Dengan menggunakan operasi perpangkatan max-min untuk matriks di atas, dapat ditentukan kapasitas maksimum lintasan antara dua buah titik dalam jaringan. Selanjutnya diberikan program MATLAB untuk menghitung perpangkatan matriks atas aljabar maxmin yang dapat digunakan untuk membantu menentukan kapasitas maksimum lintasan dalam jaringan tersebut.. Keywords:aljabar max-min, matriks, lintasan, kapasitas maksimum.

PENDAHULUAN Aljabar max-plus (himpunan R{}, dengan R adalah himpunan semua bilangan real, yang dilengkapi dengan operasi maximum dan penjumlahan) telah digunakan untuk memodelkan dan menganalisis sistem produksi sederhana, dengan fokus analisa pada masalah input-output sistem (Baccelli et.al, 2001 dan Rudhito, 2003). Pemodelan dan analisis sifat-sifat suatu jaringan antrian juga telah dilakukan dengan pendekatan aljabar max-plus, seperti dalam Krivulin (2000) dan Rudhito (2011). Penerapan aljabar max-plus pada masalah analisis lintasan kritis juga telah dibahas dalam Rudhito (2010). Pemodelan dan analisa suatu jaringan dengan pendekatan aljabar max-plus ini dapat memberikan hasil analitis dan lebih mudah pada komputasinya. Selain aljabar max-plus, dalam Baccelli et.al. (2001), Gondran and Minoux (2008) dan John and George (2010) telah disinggung beberapa varian aljabar yang serupa dengan aljabar max-plus, seperti aljabar min-plus (dengan operasi minimum dan penjumlahan) dan aljabar max-min (dengan operasi maximum dan minimum). Diberikan pula dalam referensi di atas, beberapa gambaran singkat mengenai ilustrasi penerapannya yang terkait dengan masalahmasalah dalam teori graf, seperti masalah lintasan terpendek dan masalah kapasitas maksimum suatu lintasan dalam jaringan. Seperti halnya dalam aljabar max-plus, dengan pendekatan aljabar yang serupa diharapkan masalah-masalah yang terkait dapat dimodelkan dan perhitungan-perhitungan masalah-masalah yang terkait dapat dilakukan secara lebih analitis. Makalah ini akan membahas analisis penentuan kapasitas maksimum suatu lintasan dalam jaringan dengan menggunakan pendekatan aljabar max-min. Untuk memudahkan dalam 128



Volume 2

perhitungan numeriknya, akan disusun pula suatu program komputer dengan menggunakan MATLAB. Dari hasil pembahasan makalah ini diharapkan sebagai langkah awal untuk ke masalah berikutnya yang lebih kompleks, seperti menentukan aliran (flow) maksimum dalam suatu jaringan.

ALJABAR MAX-MIN DAN MATRIKS Dalam bagian ini dibahas konsep-konsep dasar aljabar max-min dan matriks atas aljabar max-min. Pembahasan lebih lengkap dapat dilihat pada Rudhito (20011), Rudhito (2013a) dan Rudhito (2013b). 



Diberikan R  := R {} dengan R adalah himpunan semua bilangan real nonnegatip dan  : = +. Pada R  didefinisikan operasi berikut: a,b  R  , ab := max(a, b) dana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 hal urutan pengoperasian (jika tanda kurang tidak dituliskan), operasimempunyai prioritas yang lebih tinggi dari pada operasi. Karena ( R  , ) merupakan semigrup komutatif idempoten, maka relasi“  m ” yang didefinisikan pada R  denganx  m yxy = y merupakan urutan parsial pada R  .Lebih lanjut relasi ini merupakan urutan total pada R  . Karena R  merupakan semiring idempoten, maka operasi  dan konsisten terhadap urutan  m , yaitu a, b, c  R  , jika a  m b , maka ac

 m bc, dan ac  m b c. Aljabar max-min R  tidak memuat pembagi nol yaitu  x, y  R  berlaku: jika x y = min(x, y) = 0,maka x =0atau y = 0. Operasi  dan  pada R  dapat diperluas untuk operasi-operasi matriks dalam R m n : = {A = (Aij)Aij R  , untuk i = 1, 2, ..., m dan j = 1, 2, ..., n}. Untuk  R  , dan A, B R  m n didefinisikan A, dengan (A)ij = Aij dan AB, dengan (AB)ij = AijBij untuk i

= 1, 2, ..., m dan j = 1, 2, ..., n. Untuk

A R m p , B R  p n didefinisikan AB, dengan

p

(AB)ij =

Aik  Bkj . Matriks A, B R  k 1

 m n



dikatakan samajikaAij = Bijuntuk setiapidanj.

Didefinisikan matriks matriks O R m n , di mana (O)ij := 0, untuk setiap i dan j, dan matriks

 , jika i  j . Dapat ditunjukkan bahwa ( R  nn , , ) 0 , jika i  j 

E  R  nn , di mana (E )ij := 

merupakan semiring idempoten dengan elemen netral matriks O dan elemen satuan matriks E.


129

Volume 2


Sedangkan R m n merupakan semimodul atas R  . Pangkat k darimatriks A R  nn dalam 0

k

aljabar max-plus didefinisikan dengan: A = En dan A = A A

k 1

untuk k = 1, 2, ... .

Contoh 1.

 1 2  0 5    =  3 1 7

i) 

1  0 2  5   1 3  7  =  

max 1, 0 max 2, 5  max  , 1 max 3, 7  =  

1 5  7 .  

 1  1 0 8    = 1    0  6  8  2 1 1  0  0  8  4  6 0 ii)         3 2  2 4     3  6  2  2  1  3  0  2  4  

 max 1, 0, 2 max 1, 0, 4 = max  , 3, 2 max 1, 0, 2

= 

 2 4  3 2 .  

ANALISIS KAPASITAS MAKSIMUM LINTASAN Konsep-konsep dalam aljabar max-plus sangat terkait dengan konsep-konsep dalam teori graf. Untuk itu dalam bagian ini akan diawali dengan meninjau kembali beberapa konsep dalam teori graf. Suatu graf berarah G didefinisikan sebagai suatu pasangan G = (V, A) dengan V adalah suatu himpunan berhingga tak kosong yang anggotanya disebut titik dan A adalah suatu himpunan pasangan terurut titik-titik. Anggota A disebut busur. Suatu lintasan dalam graf berarah G adalah suatu barisan berhingga busur (i1, i2), (i2, i3), ... , (il1, il) dengan (ik, ik+1)  A untuk suatu l N(= himpunan semua bilangan asli) dank = 1, 2, ..., l  1. Suatu lintasan disebut sirkuit jika titik awal dan titik akhirnya sama. Diberikan graf berarah G = (V, A) dengan V = {1, 2, ... ,p}. Graf berarah G dikatakan berbobot jika setiap busur (j, i)  A dikawankan dengan suatu bilangan real Aij. Bilangan real Aij disebut bobot busur (j, i), dilambangkan dengan w(j, i). Graf preseden dari matriks denganV = {1, 2, ... ,n} dan

A  R  nn adalahgraf berarah berbobot G(A) = (V, A) A = {(j, i) | w(i, j) = Aij 0}. Sebaliknya untuk setiap graf

n berarah berbobot G = (V, A) selalu dapat didefinisikan suatu matriks A  R n max dengan Aij =

 w( j, i) , jika ( j, i )  A , yang disebut matriks bobot graf G.  jika ( j, i )  A .  ,

Dalam masalah lintasan kapasitas maksimum, untuk suatu

graf berarah berbobot

dengan matriks bobotnya A R  n n , Aijadalah bilangan real nonnegatif dan merupakan kapasitasbusur (j, i), yaitu aliran maksimum yang dapat melalui busur (j, i). Diberikan A k

R  nn . Jika k = 0, 1, 2, 3, ..., maka unsur ke-st dari matriks A adalah

130



k

( A  ) st = =

max

1i1 , i2 ,ik 1 n

max

1 i1 , i2 ,i k 1  n

Volume 2

(min( As , ik 1 , ... , Ai2 , i1 , Ai1 , t )) (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 k

sebagai titik awal dan s sebagai titik akhirnya dalam G(A), maka ( A  ) st adalah kapasitas maksimumsemua 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. Teorema 1. DiberikanA R  n n . 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 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

A

p

 m A ...  A n1 , p n. Karena untuk setiap A R  m E A ...  A n1 ,

pn.

 nn



berlaku A  m EA, maka

∎

Berdasarkan Teorema 1 di atas didefinisikan operasi bintang (*) berikut. n

Definisi 1. DiberikanA R  nn . DidefinisikanA* : = E A ...  A   A Mengingat Teorema 1 diperoleh bahwa A* : =

n 1

E A ...  A

... .

n 1

. Berdasarkan

penjelasan tentang kapasitas dan pangkat matriks di atas dapat disimpukan bahwa unsur (A*)ij merupakan kapasitas maksimum lintasan dengan ujung titik j dan pangkal titik i . Dari uraian di atas diperoleh Teorema 2 berikut, dengan bukti seperti pada uraian di atas. Teorema 2. Jika A R  n n merupakan matriks bobot suatu graf berarah berbobot, makaunsur (A*)ij merupakan kapasitas maksimum lintasan dengan ujung titikj dan pangkal titik i . Contoh 2. Diberikan suatu jaringan berkapasitas seperti pada Gambar 1 di bawah ini. 5 2 5

6

1 5 7

5

7

3

6

2 4

6

3 4

7

2

Gambar 1. Suatu Jaringan Berkapasitas Makalah Pendamping: Matematika 1

131

Volume 2


Matriks bobot graf berarah berbobot pada jaringan berkapasitas di atas adalah matriks A di bawah ini. Dengan menggunakan program yang disusun dengan menggunakan MATLAB seperti pada list program terlampir, 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  

Dari matriks A* nampak bahwa kapasitas maksimum lintasan dengan titik awal titik ke-j nampak dalam unsur-unsur kolom ke-j matriks A*. Tabel berikut memberikan daftar lintasan dan kapasitas maksimumnya dengan titik awal titik 1. Untuk titik awal yang lain dapat dilakukan dengan cara yang sama. Tabel 1. Kapasitas Maksimum Lintasan dari Titik 1 Titik Akhir

Lintasan

Kapasitas Maksimum

2

12

7

3

13

6

4

134

5

5

1345

5

6

13456

5

7

134567

5

PENUTUP Dari hasil pembahasan dapat disimpulkan bahwajaringan yang memuat kapasitas, dapat dimodelkan sebagai graf berarah terbobot, di mana bobotnya adalah kapasitas dalam jaringan. Graf berarah terbobot di atas dapat dinyatakan dalam matriks atas aljabar max-min. Dengan menggunakan operasi perpangkatan max-min untuk matriks di atas, dapat ditentukan kapasitas maksimum lintasan antara dua buah titik dalam jaringan. Dapat pula disusun suatu program MATLAB untuk menghitung perpangkatan matriks atas aljabar max-min yang dapat digunakan untuk membantu menentukan kapasitas maksimum lintasan dalam jaringan tersebut. Hasil pembahasan makalah ini diharapkan dapat dikembangkan untuk masalah yang lebih kompleks, seperti menentukan aliran (flow) maksimum dalam suatu jaringan, dengan terlebih dahulu menentukan lintasan dengan kapasitas maksimal secara otomatis.

DAFTAR PUSTAKA 132



Volume 2

Baccelli, F., Cohen, G., Olsder, G.J. and Quadrat, J.P. 2001. Synchronization and Linearity. New York: John Wiley & Sons. John S. Baras and George Theodorakopoulos. 2010. Path Problems in Networks. Synthesis Lectures on Communication Networks. Morgan & Claypool Publishers. Gondran, M and Minoux, M. 2008. Graph, Dioids and Semirings. New York: Springer. Krivulin, N.K., Algebraic Modelling and Performance Evaluation of Acyclic Fork-Join Queueing Networks. Advances in Stochastic Simulation Methods, Statistics for Industry and Technology. Birkhauser, Boston, 63-81, 2000 Rudhito MA, 2003, Sistem Linear Max-Plus Waktu-Invariant, Tesis: Program Pascasarjana Universitas Gadjah Mada, Yogyakarta Rudhito MA, Wahyuni S, Suparwanto A, dan Susilo F. 2010.Analisis Lintasan Kritis Jaringan Proyek dengan Pendekatan Aljabar Max-Plus. Jurnal Matematika Vol 12 No. 3. pp. 128133 Rudhito, Andy. 2011. Aljabar Max-Plus Bilangan Kabur dan Penerapannya pada Masalah Penjadwalan dan Jaringan Antrian Kabur. Disertasi: Program Pascasarjana Universitas Gadjah Mada. Yogyakarta. Rudhito, Andy. 2013a. Aljabar Max-Min Interval. Prosiding Seminar Nasional Penelitian, Pendidikan , dan Penerapan MIPA, tanggal 18 Mei 2013, FMIPA Universitas Negeri Yogyakarta: M-97 – M-102. Rudhito, Andy. 2013b. Matriks atas Aljabar Max-Min Interval. Prosiding Seminar Nasional Sains dan Pendidikan Sains dan Matematika, tanggal 15 Juni 2013, FSM Universitas Kristen Satya Wacana, Salatiga: 115-121.

LAMPIRAN: List Program MATLAB untuk Menghitung A* % Program Matlab untuk menghitung A* max-min % 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); Makalah Pendamping: Matematika 1

133

Volume 2


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= max(E, A1_plus) % Menampilkan hasil A* disp(' Matriks A_star '), disp(A1_star);

134



Volume 2

BILANGAN CLIQUE GRAF NON COMMUTING DARI GRUP DIHEDRAL Muflihatun Nafisah1), Abdussakir2) 1) Jurusan Matematika UIN Maulana Malik Ibrahim Malang Jl. Sumbersari Gg. 3A 230 Malang, e-mail: [email protected] 2) Jurusan Matematika UIN Maulana Malik Ibrahim Malang Perum OMA View EF 01, Malang, e-mail: [email protected] Abstrak. Misalkan 𝐺 grup tidak komutatif. Graf non commuting Γ𝐺 dari 𝐺 didefinisikan sebagai graf yang himpunan titiknya bukan anggota center dari 𝐺 dan dua titik saling terhubung jika dan hanya jika tidak komutatif. Dari graf sederhana yang didapatkan dari graf non commuting Γ𝐺 , orde terbesar subgraf komplit dari graf Γ𝐺 dinamakan dengan bilangan clique𝜔 Γ𝐺 . Pada makalah ini akan ditentukan bilangan cliquegraf non commuting pada grup dihedral 𝐷2𝑛 . Metode yang digunakan adalah kajian pustaka. Sedangkan analisis yang dilakukan adalah dengan melihat pola berdasarkan beberapa contoh yang selanjutnya dinyatakan sebagai teorema. Berdasarkan penelitian ini, diperoleh hasil bahwa bilangan cliquegraf non commuting dari grup dihedral 𝐷2𝑛 untuk 𝑛 bilangan asli ganjil, dengan 𝑛 ≥ 3 adalah 𝜔 Γ𝐷2𝑛 = 𝑛 + 1 dan bilangan cliquegraf non commuting pada grup dihedral 𝐷2𝑛 untuk 𝑛 bilangan asli genap, dengan 𝑛 ≥ 3 adalah 𝑛+2 𝜔 Γ𝐷2𝑛 = 2 Kata kunci:bilangan clique, graf non commuting, grup dihedral.

PENDAHULUAN Graf𝐺 adalah pasangan himpunan (𝑉, 𝐸) dengan 𝑉 adalah himpunan tidak kosong dan berhingga dari objek-objek yang disebut sebagai titik dan 𝐸 adalah himpunan (mungkin kosong) pasangan tak berurutan dari titik-titik berbeda di 𝑉 yang disebut sebagai sisi. Banyak unsur di 𝑉 disebut orde dari 𝐺 dan dilambangkan dengan 𝑝(𝐺), dan banyak unsur di 𝐸 disebur ukuran dari 𝐺 dan dilambangkan dengan 𝑞(𝐺) (Chartrand dan Lesniak, 1986). Jika dimisalkan Γ merupakan graf sederhana, ukuran maksimum dari subgraf komplit dari graf Γdisebut bilangan clique dari Γ yang dinotasikan dengan ω(Γ)(Abdollahi, dkk.. 2010). Beberapa penelitian mengenai bilangan clique suatu graf yang sudah dilakukan antara lain, Vahidi dan Talebi (2010) membahas tentang bilangan bebas, bilangan clique dan bilangan cover minimum dari graf commuting dari grup. Abdollahi, dkk. (2010) meneliti tentang bilangan clique dari graf non commuting dari suatu grup. Chelvam, dkk. (2011) meneliti tentang bilangan kromatik dan bilangan clique pada graf komuting yang diperoleh dari grup dihedral. Perkembangan teori graf juga membahas tentang graf yang dibangun dari grup. Seperti halnya yang dilakukan oleh Vahidi dan Talebi (2010) yang meneliti mengenai graf commuting dari grup, perkembangan selanjutnya yaitu misalkan 𝐺 grup tidak komutatif dan 𝑍(𝐺) adalah center dari 𝐺. Graf non commuting Γ𝐺 adalah draf yang memiliki himpunan titik 𝐺\𝑍(𝐺) dan


135

Volume 2


dua titik 𝑥, 𝑦 ∈ 𝐺\𝑍(𝐺) akan terhubung langsung di Γ𝐺 jika 𝑥𝑦 ≠ 𝑦𝑥 ∈ 𝐺 (Abdollahi, dkk. (2006) dan Abdollahi, dkk. (2010)). Berdasarkan uraian di atas, meskipun Abdollahi, dkk. (2010), telah meneliti tentang bilangan clique dari graf non commuting dari suatu grup, tetapi pada penelitian itu tidak dilakukan pada grup dihedral, sehingga pada penelitian ini akan dikaji bilangan clique graf non commuting dari grup dihedral.

TINJAUAN PUSTAKA 2.1 Graf Graf𝐺 adalah pasangan himpunan (𝑉, 𝐸) dengan 𝑉 adalah himpunan tidak kosong dan berhingga dari objek-objek yang disebut sebagai titik dan 𝐸 adalah himpunan (mungkin kosong) pasangan tak berurutan dari titik-titik berbeda di 𝑉 yang disebut sebagai sisi. Banyak unsur di 𝑉 disebur orde dari 𝐺 dan dilambangkan dengan 𝑝(𝐺), dan banyak unsur di 𝐸 disebur ukuran dari 𝐺 dan dilambangkan dengan 𝑞(𝐺) (Chartrand dan Lesniak, 1986).

2.2 Grup Dihedral Grup adalah suatu struktur aljabar yang dinyatakan sebagai (𝐺,∗) dengan 𝐺 himpunan tidak kosong dan ∗ operasi biner di 𝐺 yang memenuhi sifat-sifat berikut: a.

𝑎 ∗ 𝑏 ∗ 𝑐 = 𝑎 ∗ (𝑏 ∗ 𝑐), untuk semua 𝑎, 𝑏, 𝑐 ∈ 𝐺 (sifat assosiatif).

b. Ada suatu elemen 𝑒 di 𝐺 sehingga 𝑎 ∗ 𝑒 = 𝑒 ∗ 𝑎 = 𝑎, untuk semua 𝑎 ∈ 𝐺 (𝑒 disebut dentitas di 𝐺). c. Untuk setiap 𝑎 ∈ 𝐺 ada suatu elemen 𝑎−1 ∈ 𝐺sehingga 𝑎 ∗ 𝑎−1 = 𝑎−1 ∗ 𝑎 = 𝑒 (𝑎−1 disebut invers dari 𝑎). Sebagai tambahan, grup(𝐺,∗) disebut abelian (grup komutatif) jika 𝑎 ∗ 𝑏 = 𝑏 ∗ 𝑎 untuk semua 𝑎, 𝑏 ∈ 𝐺 (Raisinghania dan Aggarwal, 1980:31). Grup dihedral adalah grup dari himpunan simetri-simetri dari segi- 𝑛 beraturan, dinotasikan 𝐷2𝑛 untuk setiap 𝑛 bilangan bulat positif dan 𝑛 ≥ 3. Dalam buku lain ada yang menuliskan grup dihedral dengan 𝐷𝑛 . Operasi biner di 𝐷2𝑛 adalah operasi fungsi komposisi yang bersifat assosiatif. Berikut ini beberapa notasi dan beberapa kaidah yang dapat menyederhanakan perhitungan selanjutnya yaitu (Dummit dan Foote, 1991): a. 1, 𝑟, 𝑟 2 , … , 𝑟 𝑛−1 b. |𝑠| = 2 c. 𝑠 ≠ 𝑟 𝑖 untuk semua 𝑖 d. 𝑠𝑟 𝑖 ≠ 𝑠𝑟 𝑗

untuk

semua

0 ≤ 𝑖, 𝑗 ≤ 𝑛 − 1

dengan

𝑖 ≠ 𝑗.

Jadi

𝐷2𝑛 = {1, 𝑟, 𝑟 2 , … , 𝑟 𝑛−1 , 𝑠, 𝑠𝑟, 𝑠𝑟 2 , … , 𝑠𝑟 𝑛−1 } yaitu setiap elemen dapat dituliskan secara tunggal dalam bentuk 𝑠 𝑘 𝑟 𝑖 untuk 𝑘 = 0 atau 𝑘 = 1 dan 0 ≤ 𝑖 ≤ 𝑛 − 1. e. 𝑠𝑟 = 𝑟 −1 𝑠 136



f.

Volume 2

𝑠𝑟 𝑖 = 𝑟 −𝑖 𝑠, untuk semua 0 ≤ 𝑖 ≤ 𝑛.

2.3 Graf Non Commuting Misalkan 𝐺 grup tidak komutatif dan 𝑍(𝐺) adalah center dari 𝐺. Graf non commuting Γ𝐺 adalah draf yang memiliki himpunan titik 𝐺\𝑍(𝐺) dan dua titik 𝑥, 𝑦 ∈ 𝐺\𝑍(𝐺) akan terhubung langsung di Γ𝐺 jika 𝑥𝑦 ≠ 𝑦𝑥 ∈ 𝐺 (Abdollahi, dkk.. 2006). Atau graf non commuting dari 𝐺 didefinisikan sebagai graf yang himpunan titiknya adalah bukan anggota center dari 𝐺 dan dua titik saling terhubung jika dan hanya jika tidak komutatif (Abdollahi, dkk.. 2010). Misalkan pada 𝐷6 diperoleh 𝑍 𝐷6 = {1}, sehingga graf noncommuting dari grup 𝐷6 memiliki himpunan titik-titik Γ𝐷6 = {𝑟, 𝑟 2 , 𝑠, 𝑠𝑟, 𝑠𝑟 2 }. Kemudian hasil di atas digambarkan ke dalam bentuk graf non commuting sebagai berikut:

Gambar 2.1. Graf Non Commuting pada Grup 𝑫𝟔 2.4 Bilangan Clique Misal Γ merupakan graf sederhana, ukuran maksimum dari subgraf komplit dari graf Γdisebut bilangan clique dari Γ yang dinotasikan dengan ω(Γ)(Abdollahi, dkk.. 2010).

METODE PENELITIAN Penelitian ini merupakan penelitian pustaka (library research), yang dimulai dengan mengkaji topik berdasarkan bahan-bahan pustaka berupa buku, artikel, atau jurnal. Penelitian selanjutnya dilakukan dengan mengkaji contoh-contoh khusus (induktif) untuk menemukan suatu generalisasi yang dibuktikan secara deduktif. Adapun langkah-langkah penelitian ini secara garis besar sebagai berikut: a. Menentukan graf non commuting dari grup dihedral 𝐷2𝑛 dengan 𝑛 = 3,4,5,6,7,8. b. Menetukan cliquegraf non commuting dari grup dihedral 𝐷2𝑛 dengan 𝑛 = 3,4,5,6,7,8. c. Menelaah pola bilangan cliquegraf non commuting pada grup dihedral 𝐷2𝑛 dengan 𝑛 = 3,4,5,6,7,8 yang sudah ditemukan. d. Membuat konjektur berdasarkan pola yang sudah ditemukan. e. Merumuskan konjektur sebagai suatu teorema dan melengkapi dengan bukti secara deduktif. Makalah Pendamping: Matematika 1

137

Volume 2


HASIL Elemen-elemen dari grup dihedral 𝐷6 adalah {1, 𝑟, 𝑟 2 , 𝑠, 𝑠𝑟, 𝑠𝑟 2 }. Adapun hasil operasi komposisi pada setiap elemen grup dihedral 𝐷6 dalam bentuk tabel Cayley sebagai berikut: Tabel 1. Tabel Cayley 𝑫𝟔

Dengan daerah warna kuning merupakan unsur-unsur yang tidak komutatif pada grup dihedral 𝐷6 . Sehingga unsur-unsur yang tidak komutatif pada grup dihedral 𝐷6 sebagai berikut: 𝑟∘𝑠 ≠𝑠∘𝑟

𝑟2∘𝑠 ≠𝑠∘𝑟2

𝑠 ∘ 𝑠𝑟 ≠ 𝑠𝑟 ∘ 𝑠

𝑟 ∘ 𝑠𝑟 ≠ 𝑠𝑟 ∘ 𝑟

𝑟 2 ∘ 𝑠𝑟 ≠ 𝑠𝑟 ∘ 𝑟 2

𝑠 ∘ 𝑠𝑟 2 ≠ 𝑠𝑟 2 ∘ 𝑠

𝑟 ∘ 𝑠𝑟 2 ≠ 𝑠𝑟 2 ∘ 𝑟

𝑟 2 ∘ 𝑠𝑟 2 ≠ 𝑠𝑟 2 ∘ 𝑟 2

𝑠𝑟 ∘ 𝑠𝑟 2 ≠ 𝑠𝑟 2 ∘ 𝑠𝑟

Dengan menghilangkan center dari grup 𝐷6 yaitu 𝑍 𝐷6 = {1}, sehingga graf noncommuting dari grup 𝐷6 memiliki himpunan titik-titik Γ𝐷6 = {𝑟, 𝑟 2 , 𝑠, 𝑠𝑟, 𝑠𝑟 2 }. Kemudian hasil di atas digambarkan ke dalam bentuk graf non commuting sebagai berikut:

Gambar 4.2. Graf Non Commuting pada Grup 𝑫𝟔 Dengan melihat gambar di atas, maka dapat ditentukan cliqueΓ𝐷6 sebagai berikut:

138



Volume 2

Gambar 4.3. clique 𝚪𝑫𝟔 Sehingga didapatkan cliqueΓ𝐷6 merupakan graf 𝐾4 dengan himpunan titik-titiknya adalah {𝑟, 𝑠, 𝑠𝑟, 𝑠𝑟 2 }. Dengan demikian bilangan clique graf non commuting grup dihedral 𝐷6 𝜔 Γ𝐷6

= 4.

Berdasarkan pengamatan dengan langkah-langkah yang sama seperti di atas, ditemukan pola untuk bilangan cliqueΓ𝐷2𝑛 dengan 𝑛 = 4,5,6,7,8 sebagai berikut: Tabel 2. Pola Bilangan Clique Graf Non Commuting Grup D2n No.

Graf Non Commuting

Bilangan Clique Graf NonCommuting

1.

Graf noncommuting grup 𝐷6

𝜔(Γ𝐷6 ) = 4

2.


𝜔(Γ𝐷8 ) = 3

3.


𝜔(Γ𝐷10 ) = 6

4.


𝜔(Γ𝐷12 ) = 4

5.


𝜔(Γ𝐷14 ) = 8

6

Graf noncommuting grup𝐷16

𝜔(Γ𝐷16 ) = 5

Dengan demikian,diperoleh pola yang dapat dinyatakan sebagai teorema sebagai berikut:

Teorema 1: Misalkan 𝐷2𝑛 adalah grup dihedral dengan order 2𝑛 dengan 𝑛 bilangan asli dan 𝑛 ≥ 3. Bilangan clique Γ𝐷2𝑛 dengan 𝑛 ganjil diperoleh: 𝜔 Γ𝐷2𝑛 = 𝑛 + 1 sedangkan untuk 𝑛 genap diperoleh: 𝜔 Γ𝐷2𝑛 =

𝑛+2 2

Bukti: Diketahui grup dihedral 𝐷2𝑛 = {1, 𝑟, 𝑟 2 , ⋯ , 𝑟 𝑛−1 , 𝑠, 𝑠𝑟, 𝑠𝑟 2 , ⋯ , 𝑠𝑟 𝑛−1 }. Diperoleh bahwa 𝑍(𝐷2𝑛 ) = 1 untuk 𝑛 ganjil. Dengan demikian himpunan titik dari graf non commutingΓ𝐷2𝑛 = Makalah Pendamping: Matematika 1

139

Volume 2


𝑟, 𝑟 2 , ⋯ , 𝑟 𝑛−1 , 𝑠, 𝑠𝑟, 𝑠𝑟 2 , ⋯ , 𝑠𝑟 𝑛−1 . Karena 𝑟 𝑖 ∘ 𝑟 𝑗 = 𝑟 𝑗 ∘ 𝑟 𝑖 , untuk semua 1 ≤ 𝑖, 𝑗 ≤ 𝑛 − 1 dengan 𝑖 ≠ 𝑗 maka titik-titik ini tidak terhubung langsung di Γ𝐷2𝑛 . Dan karena 𝑛 ganjil, maka 𝑠 ∘ 𝑟 𝑖 ≠ 𝑟 𝑖 ∘ 𝑠, 𝑖 = 1,2, … , 𝑛 − 1, yang berarti bahwa 𝑠 dan 𝑟 𝑖 saling terhubung langsung di Γ𝐷2𝑛 . Demikian juga karena 𝑛 ganjil, maka 𝑠𝑟 𝑖 ∘ 𝑠𝑟 𝑗 ≠ 𝑠𝑟 𝑗 ∘ 𝑠𝑟 𝑖 , 𝑗 = 0,1,2, ⋯ , 𝑛 − 1 dan 𝑖 = 0,1,2, ⋯ , 𝑛 − 1, dengan 𝑖 ≠ 𝑗 yang berarti 𝑠𝑟 𝑖 dan 𝑠𝑟 𝑗 saling terhubung langsung di Γ𝐷2𝑛 . Sehingga terdapat salah satu himpunan titik-titik yang membentuk clique graf non commuting grup 𝐷2𝑛 dengan 𝑛 ganjil sebagai berikut: Γ𝐷2∙𝑛 : {𝑟, 𝑠, 𝑠𝑟, 𝑠𝑟 2 , 𝑠𝑟 3 , ⋯ , 𝑠𝑟 𝑛−1 } 11𝑛 − 1 Sehingga bilangan clique graf non commuting grup 𝐷2𝑛 dengan 𝑛 ganjil adalah 1 + 1 + 𝑛 − 1 = 𝑛 + 1. 𝑛

Sementara itu, untuk 𝑛 genap diperoleh bahwa 𝑍(𝐷2𝑛 ) = 1, 𝑟 2 . Dengan demikian himpunan 𝑛

𝑛

titik dari graf non commutingΓ𝐷2𝑛 = 𝑟, 𝑟 2 , ⋯ , 𝑟 2 −1 , 𝑟 2 +1 , ⋯ , 𝑟 𝑛−1 , 𝑠, 𝑠𝑟, 𝑠𝑟 2 , ⋯ , 𝑠𝑟 𝑛−1 . Karena 𝑟 𝑖 ∘ 𝑟 𝑗 = 𝑟 𝑗 ∘ 𝑟 𝑖 , untuk semua 1 ≤ 𝑖, 𝑗 ≤ 𝑛 − 1, dengan 𝑖 ≠ 𝑗 maka titik-titik ini tidak terhubung langsung di Γ𝐷2𝑛 . Dan karena 𝑛 genap, maka 𝑠 ∘ 𝑟 𝑖 ≠ 𝑟 𝑖 ∘ 𝑠, 𝑖 = 1,2, … , 𝑛 − 1 dan 𝑛

𝑖 ≠ 2 , yang berarti bahwa 𝑠 dan 𝑟 𝑖 saling terhubung langsung di Γ𝐷2𝑛 . Demikian juga karena 𝑛 genap, maka 𝑠𝑟 𝑖 ∘ 𝑠𝑟 𝑗 ≠ 𝑠𝑟 𝑗 ∘ 𝑠𝑟 𝑖 , 𝑗 = 0,1,2, … , 𝑛 − 1 dan 𝑖 = 0,1,2, … , 𝑛 − 1, dengan 𝑖 ≠ 𝑗 𝑛

dan jumlah dari 𝑖 dan 𝑗 bukan merupakan kelipatan dari 2 , yang berarti 𝑠𝑟 𝑖 dan 𝑠𝑟 𝑗 saling terhubung langsung di Γ𝐷2𝑛 . Maka salah satu himpunan titik-titik yang membentuk clique graf non commuting grup 𝐷2𝑛 dengan 𝑛 genap sebagai berikut: Γ𝐷2∙𝑛 : {𝑟, 𝑠, 𝑠𝑟, 𝑠𝑟 2 , ⋯ , 𝑠𝑟 (

11

𝑛 −2 ) 2

}

𝑛−2 2

Sehingga bilangan clique graf non commuting grup 𝐷2𝑛 dengan 𝑛 ganjil adalah 1 + 1 +

𝑛−2 2

=

𝑛+2 . 2

KESIMPULAN Berdasarkan hasil penelitian kali ini, diperoleh bahwa bilangan cliquegraf non commuting dari grup dihedral 𝐷2𝑛 untuk 𝑛 bilangan asli ganjil, dengan 𝑛 ≥ 3 adalah 𝜔 Γ𝐷2𝑛 = 𝑛 + 1

140



Volume 2

dan bilangan cliquegraf non commuting dari grup dihedral 𝐷2𝑛 untuk 𝑛 bilangan asli genap, dengan 𝑛 ≥ 3 adalah 𝜔 Γ𝐷2𝑛 =

𝑛+2 2

SARAN Penelitian selanjutnya disarankan untuk meneliti spektrum adjacency, spektrum laplace, spektrum singles laplace, atau spektrum detour dari graf non commuting dari grup dihedral 𝐷2𝑛 . DAFTAR PUSTAKA Abdollahi, A., Akbari, S., dan Maimani, H.R.. (2006). Non-commuting Graph of a Group. Journal of Algebra, Vol 298 Hal: 468-492. Abdollahi, A., Azad, A., Hassanabadi, A.M., dan Zarrin, M.. (2010). On the Clique Numbers of Non-commuting Graphs of Certain Groups. Algebra Colloquium, Vol 17 Hal: 611-620. Chartrand, G. dan Lesniak, L.. (1986). Graph and Digraph 2ndEdition. California: Wadsworth Inc. Chelvam, Tamizh, T., Selvakumar, K., dan Raja, S.. (2011). Commuting Graph on Dihegral Group. The Journal of Mathematics and Computer Science. Vol 2, No 2, Hal: 402-406. Dummit, D.S. Dan Foote, R.M.. (1991). Abstract Algebra. New Jersey: Prentice Hall, Inc. Raisinghania, M.D., dan Aggarwal, R.S.. 1980. Modern Algebra. New Delhi: S. Chand & Com[any LTD. Vahidi, J., dan Taalebi, A.A.. (2010). The Commuting Graphs on Group 𝐷2𝑛 and 𝑄𝑛 . Journal Mathematics and Computer Science. Vol 1, No 2, Hal: 123-127.


141

Volume 2


DIGRAF EKSENTRIK DARI GRAF MATAHARI Sri Kuntari, Tri Atmojo Kusmayadi dan Nugroho Arif Sudibyo Jurusan Matematika FMIPA UNS Jl. Ir. Sutami 36A Surakarta e-mail: [email protected],[email protected], [email protected]

Abstrak Suatu graf G mempunyai himpunan vertex berhingga V(G) dan himpunan edge E(G). Eksentrisitas vertexu dalam graf Gmerupakan jarak maksimum dari vertexu ke sebarang vertex yang lain di G, dinotasikan e(u). Sedangkan jarak dari vertex u ke vertexv di Gdidefinisikan sebagai adalah panjang dari pathterpendek dari vertex u ke v dan dinotasikan d(u,v). Vertex vdisebut vertex eksentrik dari u jika d(u,v)  e(u). Digraf eksentrik dari graf G adalah suatu graf G’ dengan V(G’)= V(G), dan terdapat suatu arc (edge berarah) yang menghubungkan vertexu ke vdenganvvertex eksentrik dari u. Dalam makalah ini diselidiki digraf eksentrik pada graf matahari. Kata kunci: eksentrisitas, digraf eksentrik, graf matahari.

PENDAHULUAN Pengertian dan notasi yang berkaitan dalam makalah ini diambil dari Chartrand dan Lesniak [2] serta Harris et al. [4]. Diketahui graf G dengan himpunan vertex V(G) dan himpunan edge E(G). Jarak dua vertexu dan v dalam G, dinotasikan dengan d(u,v), merupakan panjang path terpendek dari vertexu ke vertex v. Jika tidak ada path yang menghubungkan kedua vertex, d(u,v) =. Eksentrisitas dari vertex u dalam graf G didefinisikan sebagai jarak maksimum dari vertex u ke sembarang vertex lainnya dalam G. Eksentrisitas vertex u dinotasikan sebagai e(u) dengan e(u) = max{d(u,v)vV(G)}. Sedangkan vertex v merupakan vertex eksentrik dari vertex u jika d(u,v)  e(u). Digraf eksentik dari graf G yaitu ED(G) adalah graf yang mempunyai himpunan vertex yang sama dengan G, V(ED(G)) = V(G) dan terdapat arc (edge berarah) yang menghubungkan setiap vertex dalam G ke vertex eksentriknya. Suatu arc dalam digraf D dikatakan arc simetri jika arc tersebut menghubungkan vertex

u dan v, demikian juga

sebaliknya. Boland dan Miller [1] memberi saran untuk menemukan digraf eksentrik dari kelaskelas graf. Berkaitan dengan ini, diantaranya telah ditemukan digraf eksentrik dari graf (n,t)kite oleh Kusmayadi dkk. [7]. Huilgol et al. [5] mengkarakterisasi graf G dengan

ED(G) = G.

Kemudian pada tahun 2012 Huilgol [6] mengadakan survey terhadap hasi-hasil yang berkaitan dengan digraph eksentrik dan menyatakan masalah-masalah yang belum ada solusinya. Sebagai contoh masalah tersebut adalah sifat-sifat dari suatu graf yang berkaitan dengan digraph eksentrik.

142



Volume 2

HASIL DAN PEMBAHASAN Graf matahariSnn3 adalah graf yang dibentuk dari cycleCn dengan cara menambahkan sebuah vertex berderajat satu (pendant) pada setiap vertex di Cn. Definisi ini diambil dariWallis [8]. Gambar 1 merupakan contoh dari graf matahari S3dan S4. v1

v2

v1

u1 u2 u3 v2

v3

u1

u2

u4

u3

v4

v3

Gambar 1. Graf matahari S3(kiri) dan S4 (kanan) Langkah-langkah dalam menentukan digraf eksentrik dari suatu graf ada tiga. Pertama adalah menentukan jarak dari vertex u ke vertex v dalam graf G yang merupakan panjang lintasan terpendek dari vertex u ke vertex v. Tetapi d(u,v) = , jika tidak ada lintasan yang menghubungkan kedua vertex tersebut. Dalam menentukan jarak dari vertex u ke sembarang vertex v dalam graf G digunakan algoritma Breadth First Search (BFS) Moore yang mengacu dari Chartrand and Oellermann [3] yaitu 1. diambil salah satu vertex dalam graf G, misal u dan dilabeli 0 yang menyatakan jarak u ke dirinya sendiri, sedangkan semua vertex u dilabeli , 2. semua vertex berlabel  yang adjacent dengan u dilabeli 1, 3. semua vertex berlabel  yang adjacent dengan vertex berlabel 1 dilabeli 2, dan seterusnya sampai vertex yang dimaksud misal v berjarak hingga. Label setiap vertex menyatakan jarak dari vertex u. Kedua menentukan vertex eksentrik dari vertex u, dinotasikan dengan e(u), yaitu vertex dalam graf G yang memiliki jarak maksimum dari u. Vertex vadalah suatu vertex eksentrik dari u jika d(u,v)  e(u). Ketiga, menghubungkan vertex u dangan vertex eksentriknya dengan suatu arcd diperoleh digraph eksentrik dari graf yang diberikan. Diberikan graf matahariSnn3 dengan himpunan vertexV(Gn)={u1, u2, …, un, v1, v2, …, vn} dan himpunan edgeE(Sn)={ui ui+1(mod n), uivi,i=1, 2, …, n}. Lema berikut merupakan dasar untuk mengetahui besarnya eksentrisitas dari setiap vertex dalam graf matahari.


143

Volume 2


Lema 1.Diberikan graf matahariSnn3maka eksentrisitas dari vertex vi adalah eksentrisitas vertex uiadalah

𝑛 2

𝑛 2

+2 sedangkan

+1, i=1, 2, …, n.

Bukti. Menggunakan algoritma Breadth First Search (BFS) Moore, dapat dicari jarak setiap vertex ke setiap vertex dalam graf matahari Sn. Untuk graf matahari, masalah mencari jarak antar vertex dapat dibedakan menjadi dua yaitu untuk n ganjil dan n genap.

1. Untuk n ganjil Tabel berikutmenyajikan jarak setiap vertex ke setiap vertex dalam Sn untuk n ganjil.

Tabel 1.Jarak dari Setiap Vertex ke Setiap Vertex dalam Graf Matahari M n untuk n Ganjil Vertex

u1



u n 1

u n 1

2

2

0



n 1 2

n 1 2

n 1 2



0

1

n 1 2



1

un

1



v1

1

u1





un

v1



v n 1

v n 1

2

2

n 1 2

n 1 2



vn

1

1

2



n 1 2

n 1 2



1

2



n 1 2

0



n 1 2

n 1 2



2

1



n 1 2

n 1 2

n 1 2



0

3



n 1 2

n 1 2



1



n 1 2

n 1 2



3

0



n3 2

n3 2



n 1 2



1

2



n 1 2

n3 2



0

2



n3 2

n 1 2



1

1



n 1 2

n3 2



2

0



n 1 2

2



n 1 2

n 1 2



1

1



n3 2

n 1 2



0



u n 1 2

u n 1 2









v n 1 2

v n 1 2





vn

2. Untuk n genap Tabel berikut menyajikan jarak setiap vertex ke setiap vertex dalam Sn untuk n genap

144



Volume 2

Tabel 2.Jarak dari Setiap Vertex ke Setiap Vertex dalam Graf Matahari M n untuk n Genap Vertex

u1





un

un

v1



vn

2



vn

2

0



n 2



1

1



n2 2



2

n 2



0



n2 2

n2 2



1



n 2

un

1



n2 2



0

2



n 2



1

v1

1



n2 2



2

0



n4 2



3

n4 2



1



n 2

n4 2



0



n2 2

2



n 2



1

3



n2 2



0

u1





un 2









vn 2





vn

Dari Tabel 1 dan Tabel 2 diperoleh eksentrisitas dari vertex vi adalah eksentrisitas vertex uiadalah

𝑛 2

𝑛 2

+2 sedangkan

+1, i=1, 2, …, n.∎

Untuk graf S3 dalam Gambar 1 dan menggunakan tabel jarak

pada Tabel 1 diperoleh

eksentrisitas dari vertex𝑢𝑖 sebesar tiga dan eksentrisitas dari vertex𝑣𝑖 sebesar dua dengan

i=

1, 2, 3. Sedangkan untuk graf S4 dalam Gambar 1 dan menggunakan tabel jarak pada Tabel 2 diperoleh eksentrisitas dari vertex𝑢𝑖 sebesar 4 dan eksentrisitas dari vertex𝑣𝑖 sebesar 3 dengan i = 1, 2, 3, 4. Lema berikut ini digunakan untuk menentukan vertex eksentrik dari setiap vertex dalam graf matahari. Lema 2. Diberikan graf matahariSn, n3 maka vertex eksentrik dari 𝑢𝑖 , 𝑣𝑖 adalah 𝑣𝑛 +𝑖 𝑚𝑜𝑑 2

𝑣𝑛 +𝑖+2 𝑚𝑜𝑑 2

𝑛

𝑛

dan

untuk n ganjil, sedangkan untuk n genap, vertex eksentrik dari 𝑢𝑖 , 𝑣𝑖 adalah

𝑣𝑛 +2𝑖 𝑚𝑜𝑑 𝑛 . 2


145

Volume 2


Bukti. Vertex eksentrik dari suatu vertex dalam graf matahari Sn, dapat dicari menggunakan Lema 1. ∎ Menggunakan Lema 2, vertex eksentrik dari setiap vertex dalam graf matahari S3 dan 𝑆4 dapat dilihat pada Tabel 3.

Tabel 3. Vertex dan vertex eksentrik dari graf matahari S3 dan S4 Graf S3

Graf S4

vertex

Vertex eksentrik

vertex

Vertex eksentrik

𝑢1 , 𝑣1

𝑣2 dan 𝑣3

𝑢1 , 𝑣1

𝑣3

𝑢2 , 𝑣2

𝑣3 dan 𝑣1

𝑢2 , 𝑣2

𝑣4

𝑢3 , 𝑣3

𝑣1 dan 𝑣2

𝑢3 , 𝑣3

𝑣1

𝑢4 , 𝑣4

𝑣2

Selanjutnya diberikan teorema tentang digraf eksentrik dari graf matahari.

Teorema 3. Diberikan graf matahariSn, n3 maka maka digraf eksentrik dari graf matahari adalah 1. digraf G yang mempunyai V(G)=V(Sn) dan mempunyai arc𝑣𝑖 𝑣𝑗 dan 𝑢𝑖 𝑣𝑗 dengan 𝑗 = 𝑛 +𝑖 2

𝑚𝑜𝑑 𝑛, 𝑗 =

𝑛 +𝑖+2 2

𝑚𝑜𝑑 𝑛 dan 𝑖 = 1, 𝑛 untuk n ganjil,

2. digraf G yang mempunyai V(G)=V(Sn) dan mempunyai arc𝑣𝑖 𝑣𝑗 dan 𝑢𝑖 𝑣𝑗 dengan 𝑗 = 𝑛 +2𝑖 2

𝑚𝑜𝑑 𝑛 dan 𝑖 = 1, 𝑛 untuk n genap.

Bukti. Dari Tabel 1, setiap vertex dihubungkan dengan vertex eksentriknya terbentuk arc. Arc yang simetrik adalah 𝑣𝑖 𝑣𝑗 dengan 𝑗 = simetrik adalah 𝑢𝑖 𝑣𝑗 dengan 𝑗 =

𝑛 +𝑖 2 𝑛 +𝑖 2

𝑚𝑜𝑑 𝑛, 𝑗 = 𝑚𝑜𝑑 𝑛, 𝑗 =

𝑛 +𝑖+2 2 𝑛 +𝑖+2 2

𝑚𝑜𝑑 𝑛 dan 𝑖 = 1, 𝑛 .Arc yang tidak

𝑚𝑜𝑑 𝑛 dan 𝑖 = 1, 𝑛 .

Selanjutnya diperoleh digraf eksentrik dari graf matahari Sn, n  3 untuk n ganjil adalah suatu digraf G yang mempunyai V(G)=V(Sn) dan mempunyai arc𝑣𝑖 𝑣𝑗 dan 𝑢𝑖 𝑣𝑗 𝑛 +𝑖 2

𝑚𝑜𝑑 𝑛, 𝑗 =

𝑛 +𝑖+2 2

dengan 𝑗 =


Sedangkan dari Tabel 2 dapat dibentuk arc dengan menghubungkan setiap vertex dengan vertex eksentriknya. Arc yang simetrik adalah 𝑣𝑖 𝑣𝑗 dengan 𝑗 = tidak simetrik adalah 𝑢𝑖 𝑣𝑗 dengan 𝑗 =

146

𝑛 +2𝑖 2

𝑛 +2𝑖 2

𝑚𝑜𝑑 𝑛 dan 𝑖 = 1, 𝑛 .Arc yang




Volume 2

Selanjutnya diperoleh digraf eksentrik dari graf matahari Sn, n  3 untuk n genapadalah suatu digraf G yang mempunyai V(G)=V(Sn) dan mempunyai arc𝑣𝑖 𝑣𝑗 dan 𝑢𝑖 𝑣𝑗 dengan 𝑗 = 𝑛 +2𝑖 2

𝑚𝑜𝑑 𝑛 dan 𝑖 = 1, 𝑛 . ∎

Digraf eksentrik dari graf matahari S3 dan S4 disajikan dalam Gambar 2. u3 v1

u2

u3

v2

v3

u4

v1

v2

v3

v4

u1

u1

u2

Gambar 2. Digraf eksentrik dari graf matahari S3 (kiri) dan S4 (kanan) PENUTUP Penelitian ini dapat dikembangkan sesuai saran dari Boland dan Miller [1] untuk kelaskelas graf yang lain yang belum ditemukan digraph eksentriknya. Demikian juga penelitian dapat dikembangkan mengikuti masalah yang diungkapkan oleh Huilgol [6].

UCAPAN TERIMA KASIH Tim Peneliti mengucapkan terima kasih kepada Universitas Sebelas Maret atas didanainya penelitian ini dalam hibah riset fundamental tahun anggaran 2013.

DAFTAR PUSTAKA [1] Boland, J. and M. Miller. 2001. The Eccentric Digraph of a Digraph, Proceeding of AWOCA’01, Lembang-Bandung, Indonesia. [2] Chartrand, G. And L. Lesniak, 1996,

Graphs and Digraphs 3rd ed., Chapman and

Hall/RCR, New York. [3] Chartrand, G. and O. R. Oellermann. 1993. Applied and AlGorithmic Graph Theory, International Series in Pure and Applied Mathematics, McGraw-Hill Inc, California. [4] Harris, J. M., J. L. Hirst and M. J. Mossinghoff, 2000, Combinatorics and Graph Theory 2nd ed.. Springer, New York. Makalah Pendamping: Matematika 1

147

Volume 2


[5] Huilgol, M. I., S.A. Ulla S. and Sunilchandra A.R., 2011, On Eccentric Digraphs of Graphs, Applied Mathematics 2, pp:705-710. [6] Huilgol, M.I., 2012, A Survey on Eccentric graph of a (Di)Graph, J. Math. Comput. Sci 2 no 4, pp:1144-1160. [7] Kusmayadi, T. A., Nugroho, A. S. and S. Kuntari, 2013, Eccentric Digraph of

(n, t)-

kiteGraph, Far East Journal of Mathematical Sciences, volume 74 nomer 2, pp 369-378. [8] Wallis W.D., 2001, Magic Graph, Birkhauser, Boston, Basel, Berlin.

148



Volume 2

PEMBERIAN NOMOR VERTEX PADA JARINGAN GRAF MATAHARI𝑺𝒏 Dimas Ari Kurniawan Perdana dan Tri Atmojo Kusmayadi Jurusan Matematika FMIPA UNS Jl. Ir. Sutami 36A Surakarta e-mail: [email protected],[email protected] Abstrak Minimum spanning tree padasuatu jaringan komunikasi menggunakan edge untuk menghubungkan setiap vertexdalam lintasan yang bertujuan untuk menghasilkan jaringan komunikasi yang efektif dan efisien. Jaringan komunikasi yang efektif dan efisien adalah jaringan dengan rute terpendek yang dapat memberikan hasil yang maksimal dengan biaya minimal. Misal G = (V;E) adalah jaringan komunikasi. Jarak adalah panjang lintasan terpendek dari vertex u ke v dalam G, dinotasikan dengan d(u, v). Eksentrisitas dari vertex u adalah jarak terjauh dari vertex u ke vertex lain, dinotasikan dengan e(u). Dalam paper ini, akan diberikan penomoran vertexberdasarkan besar eksentrisitas tiap vertex pada jaringan komunikasi yang berbentuk graf matahari 𝑆𝑛 .

Kata Kunci: minimum spanning tree, graf matahari, eksentrisitas, jarak

PENDAHULUAN

Di dalam suatu bentuk jaringan komunikasi, baik jaringan dengan kabel (wired) ataupun tanpa kabel (wireless) yang menggunakan edge untuk menghubungkan setiap vertex pada suatu jaringan bertujuan untuk menghasilkan jaringan komunikasi yang efektif dan efisien. Menurut Kamalesh dan Srivatsa [3], tujuan dari bentuk jaringan komunikasi adalah untuk memberikan hasil yang maksimal dengan biaya yang minimal. Dalam hal ini, posisi dan urutan dari tiap vertex, banyaknya edge dan panjang tiap edge dalam menyalurkan data di dalam jaringan sangat berpengaruh dalam mencapai hasil yang maksimal. Salah satu cara untuk membentuk jaringan komunikasi yang efektif dan efisien adalah dengan memberi nomor pada setiap vertexdengan menentukan bentuk minumum spanning treedarijaringan komunikasi tersebut. Dalam pemberian nomor tiap vertex terlebih dahulu ditentukan jarak dan eksentrisitas setiap vertex pada lintasan graf. Ketika vertex diberi nomor secara sistematik, spanning tree yang dihasilkan akan mengalami perubahan bentuk yang relatif lebih kecil (minimum) dan akan menghasilkan jaringan spanning tree yang efisien. Minimum spanning treeyang efisien adalah spanning tree dari suatu jaringan yang melalui semua vertex yang ada dengan jarak paling minimum. Dalam perkembangannya telah banyak penelitianterkait efisiensi jaringan melalui bentuk minimum spanning tree. Kamalesh dan Srivatsa [3] dalam penelitiannya memberikan solusi bentuk efisien jaringan komputer yang berbentuk graf tripartit menggunakan bentuk minimum spanning tree dengan memberikan nomor pada tiap vertex berdasarkan jarak dan eksentrisitas tiap vertex. Selanjutnya dalam paper ini, penulis tertarik untuk membahas penyelesaian masalah pemberian nomor vertex dariminimum spanning tree pada jaringan graf matahari𝑆𝑛 .


149

Volume 2


HASIL PENELITIAN DAN PEMBAHASAN Berikut ini diberikan beberapa definisi mengenai spanning tree, minimum spanning tree, dan graf matahari 𝑆𝑛 yang diambil dari Boland dan Miller [1], Chartrand dan Oellermann [3], dan Wallis [4] Definisi 1.MisalkanGadalah graf terhubung.Spanning tree dari G adalah spanning subgrafT dari G jika T adalah sebuah tree dan T memuat semua vertex dari G. Definisi 2. Misalkan G adalah graf terhubung berbobot. Spanning tree dimana total bobot edgenya paling kecil disebut minimum spanning tree dari G. Definisi 3. Graf matahari dinotasikan dengan 𝑆𝑛 , untuk n ≥ 3, adalah graf yang dibentuk dari cycle dengan cara menambahkan sebuah vertex berderajat 1 (pendant) pada setiap vertex di cycle Cn. Dalam mencari bentuk spanning tree digunakan metode Breadth-First Search (BFS). BFS adalah metode untuk mencari spanning tree dengan cara memproses semua vertex pada level yang diberikan sebelum menuju ke level berikutnya. Definisi 4. Jarak dari vertex u ke v di G adalah panjang lintasan terpendek dari vertex u ke v, dinotasikan dengan d(u, v). Jika tidak ada lintasan yang menghubungkan vertex u dan v, maka d(u,v) = 1. Selanjutnya untuk menyelesaikan masalah lintasan terpendek dalam graf G, digunakan algoritma BFS (Breadth First Search) Moore. Chartrand dan Oelermann [2] menyebutkan langkah-langkah dalam algoritma BFS Moore adalah sebagai berikut. 1. Diambil salah satu vertex, misal u, dan dilabeli 0 yang menyatakan jarak dari u ke dirinya sendiri, sedangkan semua vertex selain u dilabeli 1. 2. Semua vertex berlabel 1 yang adjacent dengan u dilabeli 1. 3. Semua vertex berlabel 1 yang adjacent dengan vertex berlabel 1 dilabeli 2 dan demikian seterusnya sampai vertex yang dimaksud, misal v, sudah berlabel hingga ∞. Definisi 5. Eksentrisitas (eccentricity) vertex u, dinotasikan e(u), dalam graf G adalah jarak terjauh (lintasan terpendek maksimum) dari vertex u ke setiap vertex di G, dapat dituliskan 𝑒 𝑢 = max⁡ {𝑑(𝑢, 𝑣) 𝑣 ∈ 𝑉(𝐺)}. Algoritma Kamalesh-Srivatsa Dalam menentukan jaringan yang efektif dan efisien dilakukan pemberian nomor vertex secara matematis. Menurut Kamalesh dan Srivatsa [4], langkah-langkah dalam pemberian nomor vertex adalah sebagai berikut, 1) mengkonstruksikan suatu jaringan graf, 2) memberikan label pada tiap vertex menggunakan simbol {𝑣1 , 𝑣2 , … , 𝑣𝑛 }, 3) menentukan minimum spanning tree dari suatu jaringan graf, 4) menentukan eksentrisitas e(v) dari minimum spanning tree T,

150



Volume 2

5) memberikan nomor vertex pada jaringan berdasarkan nilai eksentrisitas secara terurut. Vertex yang memiliki nilai eksentrisitas terkecil maka diberikan nomor terkecil. Jika terdapat vertex yang memiliki nilai eksentrisitas sama maka dilihat jarak vertex tersebut terhadap vertex awal. Vertex dengan d(vi, vawal) lebih kecil diberikan nomor vertex lebih kecil. Jika terdapat vertex dengan d(vi, vawal) sama maka vertex dengan indek lebih kecil diberikan penomoran vertex lebih kecil. Pemberian nomor vertex pada jaringan graf matahari𝑆𝑛 dilakukan dalam beberapa tahap. Sebelumnya diasumsikan bahwa bobot setiap edge adalah sama.

Langkah pertama mengkonstruksikan jaringan graf matahari𝑆𝑛 seperti Gambar 1.

Gambar 1. Graf Matahari 𝑆𝑛 tanpa label Selanjutnya jaringan graf matahari𝑆𝑛 diberikan label vertex dengan himpunan vertexnya V = {𝑣1 , 𝑣2 , … , 𝑣𝑛 , 𝑢1 , 𝑢2 , … , 𝑢𝑛 }

v1 v2

u1v3 u2u3

v4

u4

vn-2

u5

v5

un-2 un-1 unvn-1

vn vn

Gambar 2. Graf Matahari 𝑆𝑛 dengan label

Minimum Spanning Tree Graf Matahari 𝑺′𝒏 Jaringan graf matahari yang sudah diberi label kemudian ditentukan bentuk minimum spanning treenya. Minimum spanning tree dapat ditentukan dengan menggunakan algoritma BFS sehingga diperoleh minimum spanning tree graf matahari𝑆𝑛′ seperti pada Gambar 3.


151

Volume 2


v1

v1

u1

u1

u2 u3 v2 v3

u2 u4

u5

u3 v2

v3

u4

v4 v5 un-1un

u5 v4

un-2 (a)

vn-2

vn-1vn

un-1

v5

unv(b) n-1

Gambar 3. Minimum spanning tree 𝑆𝑛′ dari jaringan graf matahari 𝑆𝑛 (a) untuk n ganjil n ≥ 3 dan (b) untuk n genap n ≥ 4.

vn

Dari minimum spanning tree yang sudah diperoleh, selanjutnya dicari nilai eksentrisitasnya. Nilai eksetrisitas setiap vertex diperoleh dengan mencari lintasan terpendek maksimum. Dalam mencari lintasan terpendek dari vertex ke setiap vertex dalam 𝑆𝑛′ digunakan algoritma BFS Moore. Eksentrisitas dari Graf Matahari 𝑺′𝒏 Misal 𝑆𝑛′ adalah bentuk miminum spanning tree dari graf matahari yang diperoleh dengan algoritma BFS, dimana label vertex diberikan seperti pada Gambar 2, maka eksentrisitas dari minimum spanning tree graf matahari 𝑆𝑛′ untuk n ganjil n> 3 adalah

𝑒 𝑢𝑖 =

𝑛+𝑖 2 𝑛+1 +𝑖 2

,

𝑖 = 1, 3, … , 𝑛,

,

𝑖 = 2, 4, … , 𝑛 − 1,

,

𝑗 = 1, 3, … , 𝑛,

,

𝑗 = 2, 4, … , 𝑛 − 1.

(1)

dan

𝑒 𝑣𝑗 =

𝑛+2 +𝑗 2 𝑛+3 +𝑗 2

(2)

Sedangkan eksentrisitas dari minimum spanning tree graf matahari 𝑆𝑛′ untuk n genap, n> 4 adalah,

152



𝑒 𝑢𝑖 =

Volume 2

𝑛 +1 , 𝑖=1 2 𝑛+2 +𝑖 , 𝑖 = 2, 4, … , 𝑛 − 2 2 𝑖−1 +𝑛 . 𝑖 = 3, 5, … , 𝑛 − 1 2 𝑛 . 𝑖=𝑛,

(3)

𝑛+4 , 𝑗=1 2 𝑛+4 +𝑗 , 𝑗 = 2, 4, … , 𝑛 − 2 2 𝑛+1 +𝑗 . 𝑗 = 3, 5, … , 𝑛 − 1 2 𝑛+1 . 𝑗=𝑛.

(4)

dan

𝑒 𝑣𝑗 =

Penomoran vertex pada Graf Matahari 𝑺′𝒏 Setelah ditentukan eksentrisitas dari bentuk minimum spanning tree graf matahari 𝑆𝑛′ , selanjutnya diberikan nomor vertex pada jaringan berdasarkan nilai eksentrisitas secara terurut. Vertex yang memiliki nilai eksentrisitas terkecil maka diberikan nomor terkecil. Misal 𝑆𝑛′ merupakan bentuk minimum spanning tree dari graf matahari 𝑆𝑛 , maka urutan penomoran vertex dari minimum spanning tree graf matahari𝑆𝑛′ dapat dinotasikan dengan λ(𝑆𝑛′ ) Teorema 1. Misal 𝑆𝑛′ merupakan bentuk minimum spanning tree dari graf matahari dengan n ganjil n ≥ 3, maka λ(𝑆𝑛′ ) nya adalah 1 , 𝜆 𝑢𝑖 = 2𝑖 − 1 , 2𝑖 − 2 ,

𝑖=1 𝑖 = 2, 4, … , 𝑛 − 1 𝑖 = 3, 5, … , 𝑛,

dan 𝜆 𝑣𝑗

2 = 2𝑗 + 1 2𝑗

, , ,

𝑗=1 𝑗 = 2, 4, … , 𝑛 − 1 𝑗 = 3, 5, … , 𝑛.

Bukti. Penomoran vertex dari setiap vertex pada minimum spanning tree graf matahari 𝑆𝑛′ untuk n ganjil n> 3, diperoleh dari urutan nilai eksentrisitas setiap vertex. Jika nilai eksentrisitas vertex kecil maka diberi nomor urut kecil, semakin besar nilai eksentrisitas vertex maka semakin besar pula nomor urut vertex tersebut. Berdasarkan eksentrisitasdari minimum spanning tree graf matahari𝑆𝑛′ dengan n ganjil n> 3 pada persamaan (1),maka didapatkan urutan penomoran vertex untuk setiap vertex 𝑢𝑖 adalah 1 untuk i = 1, dan 2i -1 untuk setiap 𝑖 = 2, 4, … , 𝑛 − 1, serta 2i – 2 untuk setiap 𝑖 = 3, 5, … , 𝑛, sehingga urutan penomoran vertex dari eksentrisitas vertex ui, λ(ui) Makalah Pendamping: Matematika 1

153

Volume 2


adalah 1 untuk i = 1, dan 2i -1 untuk setiap 𝑖 = 2, 4, … , 𝑛 − 1, serta 2i – 2 untuk setiap 𝑖 = 3, 5, … , 𝑛. Demikian juga urutan penomoran vertex untuk vertex vj,berdasarkan eksentrisitas pada persamaan (2), didapatkan urutan penomoran vertex untuk setiap vertex vjadalah 2 untuk j = 1, dan 2j + 1 untuk setiap 𝑗 = 2, 4, … , 𝑛 − 1, serta 2j untuk setiap 𝑖 = 3, 5, … , 𝑛, sehingga urutan penomoran vertex dari eksentrisitas vertex vj, λ(vj) adalah 2 untuk j = 1, dan 2j + 1 untuk 

setiap 𝑗 = 2, 4, … , 𝑛 − 1, serta 2j untuk setiap 𝑖 = 3, 5, … , 𝑛.

Teorema 2. Misal 𝑆𝑛′ merupakan bentuk minimum spanning tree graf matahari dengan n genap n ≥ 4, maka λ(𝑆𝑛′ ) nya adalah

𝜆 𝑢𝑖

1 , 𝑖=1 2𝑖 , 𝑖 = 2, 4, … , 𝑛 − 2 = 2𝑖 − 4 , 𝑖 = 3, 5, … , 𝑛 − 1 2𝑖 − 2 , 𝑖 = 𝑛 ,

𝜆 𝑣𝑗

3 2𝑗 + 3 = 2𝑗 − 1 2𝑗

dan , 𝑗=1 , 𝑗 = 2, 4, … , 𝑛 − 2 , 𝑗 = 3, 5, … , 𝑛 − 1 , 𝑗 = 𝑛.

Bukti. Penomoran vertex dari setiap vertex pada minimum spanning tree graf matahari 𝑆𝑛′ untuk n genap n ≥ 4, diperoleh dari urutan nilai eksentrisitas setiap vertex. Jika nilai eksentrisitas vertex kecil maka diberi nomor urut kecil, semakin besar nilai eksentrisitas vertex maka semakin besar pula nomor urut vertex tersebut. Berdasarkan eksentrisitasdari minimum spanning tree graf matahari𝑆𝑛′ dengan n genap n> 4 pada persamaan (3), maka didapatkan urutan penomoran vertex untuk setiap vertex 𝑢𝑖 adalah 1 untuk i = 1, dan 2i untuk setiap 𝑖 = 2, 4, … , 𝑛 − 2, lalu 2i – 4 untuk setiap 𝑖 = 3, 5, … , 𝑛 − 1, serta 2i -2 untuk 𝑖 = 𝑛, sehingga urutan penomoran vertex dari eksentrisitas vertex ui, λ(ui) adalah 1 untuk i = 1, dan 2i untuk setiap 𝑖 = 2, 4, … , 𝑛 − 2, lalu 2i – 4 untuk setiap 𝑖 = 3, 5, … , 𝑛 − 1, serta 2i – 2 untuk 𝑖 = 𝑛. Demikian juga urutan penomoran vertex untuk vertex vjberdasarkan eksentrisitas pada persamaan (4), didapatkan urutan penomoran vertex untuk setiap vertex vjadalah 3 untuk j = 1, dan 2j + 3untuk setiap 𝑗 = 2, 4, … , 𝑛 − 2, lalu 2j – 1 untuk setiap 𝑗 = 3, 5, … , 𝑛 − 1, serta 2j untuk 𝑗 = 𝑛, sehingga urutan penomoran vertex dari eksentrisitas vertex vj, λ(vj) adalah 3 untuk j = 1, dan 2j + 3untuk setiap 𝑗 = 2, 4, … , 𝑛 − 2, lalu 2j – 1 untuk setiap 𝑗 = 3, 5, … , 𝑛 − 1, serta 2j untuk 𝑗 = 𝑛.



SIMPULAN DAN SARAN Berdasarkan

pembahasan

dapat

diambil

kesimpulan

bahwa

pemberian

nomorvertexdapat diterapkan untuk berbagai jaringan yang mempunyai karakteristik sama 154



Volume 2

sepertikelas - kelas dalamjaringan graf matahari 𝑆𝑛 dengan himpunan vertex V = {𝑣1 , 𝑣2 , … , 𝑣𝑛 , 𝑢1 , 𝑢2 , … , 𝑢𝑛 },diperoleh pemberian nomor vertex untuk jaringan graf matahari 𝑆𝑛′ dengan n ganjil, n ≥ 3seperti pada Teorema 1. dan untuk jaringan graf matahari 𝑆𝑛′ dengan n genap, n ≥ 4seperti pada Teorema 2.

DAFTAR PUSTAKA [1]

Boland, J. and Miller, M. (2001). The eccentric digraph of a digraph. Proceeding of AWOCA'01. Lembang-Bandung. Indonesia.

[2]

Chartrand, G. and O. R. Oellermann. (1993). Applied and Algorithmic Graph Theory. McGraw Hill Inc., New York.

[3]

Kamalesh, V. N. and S. K, Srivatsa. (2009). Node numbering in topological structure of interconnection network. Indian Journal of Science and Technology. 2 no. 11, 37 – 40.

[4]

Wallis, W. D. (2001). Magic Graphs. Birkhauser. Boston.


155

Volume 2


SPEKTRUM ADJACENCY GRAF NON COMMUTING DARI GRUP DIHEDRAL (𝑫𝟐𝒏 ) Rivatul Ridho Elvierayani1), Abdussakir, M.Si2) 1) Jurusan Matematika UIN Maulana Malik Ibrahim Malang Jl. Sumbersari Gg.3B 158 Malang, e-mail: [email protected] 2) Jurusan Matematika UIN Maulana Malik Ibrahim Malang Perum OMA View EF 01 Malang,e-mail: [email protected] Abstrak Graf dapat dinyatakan dalam bentuk matriks, misalnya matriks adjacency. Ketika graf sudah dinyatakan dalam bentuk matriks, maka dapat didekati secara aljabar linier untuk mencari nilai eigen dan vektor eigennya. Matriks baru yang memuat semua nilai eigen pada baris pertama dan banyaknya vektor eigen yang besesuaian pada baris kedua disebut spektrum. Spektrum yang diperoleh dari matriks A(G) disebut spektrum adjacency. Kajian mengenai grup dalam aljabar abstrak membawa pada konsep baru dalam teori graf yang disebut graf noncommuting. Pada artikel ini ditentukan spektrum adjacency graf non commuting pada grup dihedral (𝐷2𝑛 ) dengan n adalahbilangan asli diperoleh spektrum adjacency nya: 𝑠𝑝𝑒𝑐 𝛤𝐷2𝑛 =

𝑛−1 + 2

𝑛−1 𝑛+

𝑛−1 2

2

0

1 ≥ 3 danganjil 𝑛−2

spec (𝛤𝐷2𝑛 )=

2

+

5𝑛 2 −12𝑛+4 4

1

−1

𝑛−1 − 2

𝑛−1 𝑛+

𝑛−2 𝑛−1

0

−2

𝑛−2

3𝑛−6

2

2

𝑛−2 2

−

𝑛−1 2

2

∀𝑛

1

5𝑛 2 −12𝑛+4 4

∀𝑛 ≥ 6 dangenap

1

Kata Kunci:Graf, matriks adjacency, nilai eigen, vektor eigen, spektrum, grup dihedral, graf non commuting.

PENDAHULUAN Graf Gadalah pasangan (V(G),E(G)) dengan V(G) adalah himpunan tidak kosong dan berhingga dari objek-objek yang disebut titik, dan E(G) adalah himpunan (mungkin kosong) pasangan tak berurutan dari titik-titik berbeda di V(G) yang disebut sisi. Banyaknya unsur di V(G) disebut order dari G dan dilambangkan dengan n(G), dan banyaknya unsur di E(G) disebut ukuran dari G dan dilambangkan dengan m(G) (Chartrand & Lesniak, 1996). Sisi e=(u, v) dikatakan menghubungkan titik u dan v. Jika e=(u, v) adalah sisi di graf G, maka u dan v disebut terhubung langsung(adjacent),v dan e serta u dan e disebut terkaitlangsung (incident), dan titik u dan v disebut ujung dari e. Dua sisi berbeda e1 dan e2 disebut terhubung langsung (adjacent), jika terkait langsung pada satu titik yang sama, sisi e = (u, v) akan ditulis e = uv (Chartrand & Lesniak, 1996). Misalkan G graf dengan order 𝑛 𝑛 ≥ 1 dan ukuran q serta himpunan titik V(G) = {v1, v2, …, vn}.Matriks keterhubungan titik (matriks Adjacency) dari graf G, dinotasikan dengan A(G), adalah matriks (n n). Dengan kata lain,matriks adjacencydapat ditulisA(G) = [aij], 1 i, jp, dengan 𝑎𝑖𝑗 = 1 jika 𝑣𝑖 𝑣𝑗 ∈ 𝐸(𝐺) dan 𝑣𝑖 𝑣𝑗 𝐸(𝐺). Matriks adjacency suatu graf G adalah matriks simetri dengan unsur 0 dan 1 dan memuat nilai 0 pada diagonal utamanya (Chartrand & Lesniak, 1996). 156



Volume 2

Jika A adalah matriks 𝑛 × 𝑛, maka vektor tak nol 𝑥 di dalam 𝑅 𝑛 dinamakan vektor eigen (eigenvector) dari A jika 𝐴𝑥 adalah kelipatan skalar dari 𝑥, yakni 𝐴𝑥 = 𝜆𝑥 untuk skalar 𝜆. Skalar 𝜆 dinamakan nilai eigen (eigenvalue) dari 𝐴 dan 𝑥 dikatakan vektor eigen yang bersesuaian dengan 𝜆. Karena matriks adjacency adalah matriks simetri dan real sehingga eigenvalue i, i = 1, 2, 3, …, p nonnegatif real numbers dan dapat ditulisan dengan 12 p= 0. If 𝜇𝑖1 ≥ 𝜇𝑖2 ≥ ⋯ ≥ 𝜇𝑖𝑔 adalah nilai eigen yang berbeda, maka spektrum dari A(G) dapat dituliskan dengan: 𝜇𝑖 𝜇𝑖 …𝜇𝑖 spec (G) = 𝑚1 𝑚2 …𝑚𝑔 𝑔 1 2 𝑚𝑔 melambangkan multiplisitas nilai eigen 𝜇𝑖𝑗 (Yin, 2008). m1 + m2 + … + mg = p (Ayyaswamy & Balachandran, 2010).

Multiplisitas dari 𝜇𝑖𝑗 sebagai akar persamaan karakteristik dari

det(𝜇𝑖𝑗 𝐼 − 𝐴(𝐺)) = 0 sama dengan dimensi ruang vektor eigen yang bersesuaian dengan 𝜇𝑖𝑗 (Bigg, 1974). Sebuah sistem aljabar (G,*) dengan G bukan himpunan ∅ dan satu operasi biner * dikatakan sebagai grup jika memenuhi postulat: (i)

Operasi * memenuhi hukum assosiatif 𝑎 ∗ 𝑏 ∗ 𝑐 = 𝑎 ∗ 𝑏 ∗ 𝑐 … . . ∀𝑎, 𝑏, 𝑐 ∈ 𝐺

(ii) Setiap elemen G mempunyai identitas terhadap operasi *, misal e adalah identitas di G 𝑒 ∗ 𝑎 = 𝑎 ∗ 𝑒 = 𝑎 … . ∀𝑎 ∈ 𝐺 (iii) Setiap elemen G mempunyai invers terhadap operasi * 𝑎−1 ∗ 𝑎 = 𝑎 ∗ 𝑎−1 = 𝑒, dimana e adalah ∈ 𝐺(Raisinghania dan Aggarwal, 1980). Jika (𝐺,∗) adalah grup dan 𝑎 ∗ 𝑏 = 𝑏 ∗ 𝑎, ∀𝑎, 𝑏 ∈ 𝐺, maka G dikatakan grup abelian atau grup komutatif. Grup dihedral adalah grup dari himpunan simetri-simetri dari segi-n beraturan, dinotasikan 𝐷2𝑛 , untuk setiap n bilangan bulat positif dan𝑛 ≥ 3. Dalam buku lain ada yang menuliskan grup dihedral dengan 𝐷𝑛 (Dummit dan Foote, 1991). Karena grup dihedral akan digunakan secara ektensif, maka perlu beberapa notasi dan beberapa hitungan yang dapat menyederhanakan perhitungan selanjutnya dan membantu mengamati 𝐷2𝑛 sebagai grup abstrak, yaitu: (1) 1, r, r 2 , . . ., r n 1 (2) s  2 , (3) s  r i untuk semua i. (4) untuk semua 0 ≤ 𝑖, 𝑗 ≤ 𝑛 − 1 dengan 𝑖 ≠ 𝑗. Jadi 𝐷2𝑛 = 1, 𝑟, 𝑟 2 , … , 𝑟 𝑛−1 , 𝑠, 𝑠𝑟 2 , … , 𝑠𝑟 𝑛−1 yaitu setiap elemen dapat dituliskan secara tunggal dalam bentuk s k r i untuk k = 0 atau 1 dan 0 ≤ 𝑖 ≤ 𝑛 − 1. Makalah Pendamping: Matematika 1

157

Volume 2


1 (5) sr  r s .

(6) sr i  r i s , untuk semua 0 ≤ 𝑖 ≤ 𝑛 (Dummit dan Foote, 1991). Misal G grup, center dari grup G, dituliskan 𝑍(𝐺) sebagai berikut: 𝑍(𝐺) = 𝑧 ∈ 𝐺 ∶ 𝑧𝑥 = 𝑥𝑧, ∀𝑥 ∈ 𝐺 Jadi jika 𝑍(𝐺) adalah himpunan anggota G yang komutatif terhadap semua anggota 𝑍(𝐺). Misal G grup non abelian dan Z(G) adalah center dari G. Graf non commutingΓG adalah sebuah graf yang mana titik-titiknya merupakan himpunan dari 𝐺\𝑍(𝐺) dan dua titik x dan y terhubung langsung jika dan hanya jika 𝑥𝑦 ≠ 𝑦𝑥(Abdollahi, A, 2006, Journal of Algebra). 𝛤𝐺 adalah sebuah graf yang titiknya adalah bukan elemen-elemen center dari sebuah graf G, titik-titik dari 𝛤𝐺 adalah G\Z(G) merupakan pengambilan atau penghapusan elemen center pada graf G. Beberapa penelitian lain mengenai spektrum suatu graf sudah pernah dilakukan. Shuhua Yin (2006) meneliti spektrum Adjacency dan spektrum Laplace pada graf Gl yang diperoleh dari graf komplit Kl dengan menambahkan pohon isomorfik berakar untuk masing-masing titik di Kl. Abdussakir, dkk (2009) meneliti spektrum adjacency pada graf komplit (Kn), graf star (Sn), graf bipartisi komplit (Km,n), dan graf lintasan (Pn). Ayyaswamy & Balachandran (2010) meneliti spektrum Detour pada beberapa graf yang meliputi graf K(n, n), graf Korona G dan K1, graf perkalian Kartesius G dengan K2, graf perkalian leksikografik G dengan K2, dan perluasan dobel kover dari graf beraturan. Abdussakir, dkk (2012) meneliti spektrum Adjacency, Laplace, Singless Laplace, dan Detour graf multipartisi komplit K(𝛼1 , 𝛼2 , 𝛼3 , … , 𝛼𝑛 ). Dalam penelitian mengenai graf commuting dan non commuting, Abdollahi, dkk (2006&2010) meneliti tentang grup finite pada dua grup yang non abelian dan bilangan clique. Abdussakir, dkk (2013) meneliti tentang spektrum graf commuting suatu grup. Berdasarkan uraian di atas, belum ada yang mengkaji mengenai spektrum graf non commuting sehingga peneliti bermaksud untuk mengkaji spektrum adjacency graf non commuting dari grup dihedral (𝐷2𝑛 ). METODE PENELITIAN Dalam penulisan artikel ini, peneliti menggunakan metode studi literatur, adapun langkah-langkah peneliti diantaranya: 1. Membuat tabel cayle dengan operasi komposisi (∘) pada grup dihedral 𝐷2𝑛 . 2. Menentukan himpunan titik-titik graf non commuting dari grup dihedral 𝐷2𝑛 dari tabel cayle. 3. Menggambar graf non commuting dari grup dihedral 𝐷2𝑛 . 4. Menentukan matriks adjacency dari graf non commuting dari grup dihedral 𝐷2𝑛 . 5. Mencari nilai eigen (eigenvalue) dari matriks adjacency graf non commuting grup dihedral 𝐷2𝑛 .

158



Volume 2

6. Mencari multiplisitas setiap nilai eigen dari matriks adjacency graf non commuting grup dihedral 𝐷2𝑛 . 7. Mencari spektrum adjacency dari grup dihedral 𝐷2𝑛 . 8. Mencari pola dan dirumuskan menjadi suatu lemma dan teorema serta dibuktikan kebenarannya secara umum.

HASIL PENELITIAN DAN PEMBAHASAN Pada pembahasan ini, grup dihedral yang digunakan adalah𝐷6 , 𝐷8 , 𝐷10 , … , 𝐷2𝑛 . Pembahasan yang disajikan dalam bentuk contoh selanjutnya dijadikan sebuah teorema dan disertai bukti. Dihedral 𝐷6 dibangun dari elemen-elemen {1, 𝑟, 𝑟 2 , 𝑠, 𝑠𝑟, 𝑠𝑟 2 }, hasil operasi komposisi pada setiap elemen grup dihedral berbentuk tabel Cayley yang menunjukkan unsur-unsur yang tidak komutatif pada 𝐷6 sebagai berikut: Tabel 1. Tabel Cayley D6 °

1

r

r2

s

Sr

sr2

1

1

r

r2

s

Sr

sr2

r

r

r2

1

sr2

S

sr

r

2

r

2

1

r

sr

sr

2

s

s

s

sr

sr2

1

R

r2

sr

sr

sr2

s

r2

1

r

sr2

sr2

s

sr

r

r2

1

Dari tabel 1, diperoleh center 𝐷6 atau 𝑍 𝐷6 yaitu {1} yang ditunjukkan pada tabel dengan warna hitam, dan elemen-elemen pada D6 yang tidak komutatif ditunjukkan pada tabel dengan warna abu-abu. Sehingga graf non kommuting dari grup 𝐷6 memiliki himpunan titiktitiknya ΓD 6 = {𝑟, 𝑟 2 , 𝑠, 𝑠𝑟, 𝑠𝑟 2 }. Dari hasil tersebut akan digambarkan ke dalam bentuk graf non commuting sebagai berikut:

Gambar 1. Graf non D6 Graf non commuting grup 𝐷6 diatas menghasilkan matriks adjacency sebagai berikut:


159

Volume 2


𝐴 ΓD 6

𝑟 𝑟2 = 𝑠 𝑠𝑟 𝑠𝑟 2

𝑟 0 0 1 1 1

𝑟2 0 0 1 1 1

𝑠 1 1 0 1 1

𝑠𝑟 1 1 1 0 1

𝑠𝑟 2 1 1 1 1 0

Setelah mendapatkan bentuk matriks Adjacency maka akan dicari nilai eigen dan vektor eigen dari matriks tersebut dengan cara mengolah persamaan de𝑡 𝐴 ΓD 6 −  𝐼 =0. Dengan mereduksi matriks menggunakan metode Gaussian Elimination yang ada pada software Maple 12, maka akan diperoleh:

Karena det 𝐴 ΓD 6 −  𝐼 adalah hasil perkalian semua unsur diagonal utama matriks segitiga atas berikut, maka diperoleh polinomial karakteristiknya yaitu: det 𝐴 ΓD 6 −  𝐼 = (1)(𝜆) 1 + 𝜆

2

6 + 2𝜆 − 𝜆2

2

6 + 2𝜆 − 𝜆2 = 0

karena det 𝐴 ΓD 6 −  𝐼 =0, maka det 𝐴 ΓD 6 −  𝐼 = (1)(𝜆) 1 + 𝜆 dan diperoleh nilai eigennya 𝜆1 = 1 + 7,

𝜆2 = 0, 𝜆3 = −1, 𝜆4 = 1 − 7 ,

Selanjutnya akan ditentukan basis untuk ruang vektor eigen, basis merupakan baris nol pada matriks. Untuk semua 𝜆 yang diperoleh subtitusikan kedalam det 𝐴 ΓD 6 −  𝐼 =0 dengan metode gauss Jordan dalam software Maple 12 akan diperoleh 𝜆1 = 1 + 7 multiplisitas nilai eigennya 1, 𝜆2 = 0 multiplisitas nilai eigennya 1, 𝜆3 = −1 multiplisitas nilai eigennya 2, 𝜆4 = 1 − 7 multiplisitas nilai eigennya 1. Sehingga diperoleh spektrum adjacency graf non commuting dari 𝐷6 adalah: 𝑠𝑝𝑒𝑐(Γ𝐷6 ) = 1 + 7 1 Dengan cara yang sama akan diperoleh 𝑠𝑝𝑒𝑐 Γ𝐷8 =

0 −1 1 − 7 1 2 1 4 0 1 3

−2 ; 2

𝑠𝑝𝑒𝑐(Γ𝐷10 ) = 2 + 2 6 0 −1 2 − 2 6 ; 1 3 4 1 spec ΓD 12 = 2 + 2 7 1

0 −2 2 − 2 7 ; 6 2 1

spec ΓD 14 = 3 + 51 1

0 −1 3 − 51 ; 5 6 1

160



spec ΓD 16 = 3 + 57 1 dan

Volume 2

0 −2 3 − 57 9 3 1

spec ΓD 20 = 4 + 4 6 0 −2 4 − 4 6 1 12 4 1 Dari percobaan yang dilakukan oleh peneliti, didapatkan beberapa lemma dan teorema diantaranya: Lemma 1: Misalkan Γ𝐷2𝑛 adalah graf non commuting dari grup dihedral𝐷2𝑛 dengan n ganjil, maka polinomial karakteristik matriks adjacency 𝐴 Γ𝐷2𝑛 adalah: 𝑝 𝜆 = 1 𝜆

𝑛

1+𝜆

𝑛−1

−𝜆 + 𝑛 − 1 𝜆 + 𝑛 𝑛 − 1

Bukti: Diketahui grup dihedral 𝐷2𝑛 = {1, r, r2, …, rn-1, s, sr, sr2, …, srn-1}. Diperoleh bahwa Z(𝐷2𝑛 ) = {1}untuk n ganjil. Dengan demikian graf non commuting 𝐷2𝑛 mempunyai himpunan titik { r, r2, …, rn-1, s, sr, sr2, …, srn-1}. Karena n ganjil, maka 𝑠𝑟 𝑖 ≠ 𝑟 𝑖 𝑠, 𝑖 = 1, 2, … , 𝑛 − 1, artinya s dan 𝑟 𝑖 saling terhubung langsung di graf non commuting 𝐷2𝑛 . Demikian juga, karena n ganjil, maka 𝑠𝑟 𝑖 𝑠𝑟 𝑗 ≠ 𝑠𝑟 𝑗 𝑠𝑟 𝑖 , j=1, 2,..., n-1 dan 𝑖 = 1, 2, … , 𝑛 − 1, dengan 𝑖 ≠ 𝑗, yang berarti 𝑠𝑟 𝑖 dan 𝑠𝑟 𝑗 saling terhubung langsung di graf non commuting maka diperoleh matriks keterhubungan titik: 𝑟 2 ⋯ 𝑟 𝑛−1 𝑠 𝑠𝑟 𝑠𝑟 2 ⋯ 𝑠𝑟 𝑛−1

𝑟 𝑟 𝑟2 ⋮ 𝐴 ΓD 2𝑛

𝑟 𝑛−1 = 𝑠 𝑠𝑟 𝑠𝑟 2 ⋮ 𝑠𝑟 𝑛−1

0 0 ⋮ 0 1 1 1 ⋮ 1

0 0 ⋮ 0 1 1 1 ⋮ 1

… … ⋱ ⋯ ⋯ ⋯ ⋯ ⋯

0 0 ⋮ 0 1 1 1 ⋮ 1

1 1 ⋮ 1 0 1 1 ⋮ 1

1 1 ⋮ 1 1 0 1 ⋮ 1

1 1 ⋮ 1 1 1 0 ⋮ 1

⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋱ ⋯

1 1 ⋮ 1 1 1 1 ⋮ 0

Setelah mendapatkan bentuk matriks adjacency maka akan dicari nilai eigen dan vektor eigen dari matriks tersebut dengan menyelesaikan persamaan de𝑡 𝐴 ΓD 2n − 𝑟 𝑟 𝑟2 ⋮ de𝑡 𝐴 ΓD 2n

𝑟 𝑛−1 − 𝐼 = 𝑠 𝑠𝑟 𝑠𝑟 2 ⋮ 𝑛−1 𝑠𝑟

−𝜆 0 ⋮ 0 1 1 1 ⋮ 1

𝑟2 ⋯ 0 −𝜆 ⋱ 0 1 1 1 ⋮ 1

… … ⋱ ⋯ ⋯ ⋯ ⋯ ⋯

 𝐼 =0

𝑟 𝑛−1

𝑠

𝑠𝑟 𝑠𝑟 2 ⋯ 𝑠𝑟 𝑛−1

0 0 ⋮ −𝜆 1 1 1 ⋮ 1

1 1 ⋮ 1 −𝜆 1 1 ⋮ 1

1 1 ⋮ 1 1 −𝜆 1 ⋮ 1

1 1 ⋮ 1 1 1 −𝜆 ⋮ 1

⋯ 1 ⋯ 1 ⋯ ⋮ ⋯ 1 ⋯ 1 ⋯ 1 ⋯ 1 ⋱ ⋮ ⋯ −𝜆

Diperoleh matriks segitiga atas dari 𝐴 ΓD 2𝑛 − λI sebagai berikut: Makalah Pendamping: Matematika 1

161

Volume 2


𝑟 2 ⋯ 𝑟 𝑛−1

𝑟 𝑟 𝑟2 ⋮ 𝑟 𝑛−1 𝑠 𝑠𝑟 𝑠𝑟 2 ⋮ 𝑠𝑟 𝑛−1

1 0 0 0 0 0 0 ⋮ 0

1 𝜆 0 0 0 0 0 ⋮ 0

… … ⋱ ⋯ ⋯ ⋯ ⋯

1 𝜆 𝜆 𝜆 0 0 0 ⋮ 0

⋯

𝑠

𝑠𝑟 2

𝑠𝑟

−𝜆 1 − 𝜆2 ⋮ (𝑛 − 2) − 𝜆2 1+𝜆 0 0 ⋮ 0

1 1+𝜆 ⋮ (𝑛 − 2) + 𝜆 −𝜆 − 1 1+𝜆 0 ⋮ 0

𝑠𝑟 𝑛−1

⋯

1 1+𝜆 ⋮ (𝑛 − 2) + 𝜆 0 −𝜆 − 1 1+𝜆 ⋮ 1

⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋱ ⋱ ⋯

1 1+𝜆 ⋮ (𝑛 − 2) + 𝜆 0 0 0 −𝜆 − 1 −𝜆 + 𝑛 − 1 𝜆 + 𝑛 𝑛 − 1

Polinomial karakteristik dari 𝐴 ΓD 2𝑛 − λI adalah det 𝐴 ΓD 2𝑛 − λI , merupakan hasil perkalian semua unsur diagonal utama matriks segitiga atas tersebut, sehingga diperoleh: 𝑝 𝜆 = 1 𝜆

𝑛

1+𝜆

𝑛−1

−𝜆 + 𝑛 − 1 𝜆 + 𝑛 𝑛 − 1

Teorema 1: Spektrum Γ𝐷2𝑛 dengan n ganjil diperoleh: spec (𝛤𝐷2𝑛 )=

𝑛−1 2

+

𝑛−1 2 2

𝑛−1 𝑛+ 1

0

−1

𝑛−1 2

−

𝑛−1 𝑛+

𝑛−2 𝑛−1

𝑛−1 2 2

1

Bukti: Dari lemma 1, diperoleh bahwa 𝑝 𝜆 = 1 𝜆

𝑛

1+𝜆

𝑛−1

−𝜆 + 𝑛 − 1 𝜆 + 𝑛 𝑛 − 1

Sehingga diperoleh nilai eigen 𝜆1 =

𝑛−1 + 2

𝑛−1 𝑛+

𝜆4 =

𝑛−1 2

𝑛−1 − 2

2

, 𝜆2 = 0,

𝑛−1 𝑛+

𝜆3 = −1,

𝑛−1 2

2

Selanjutnya akan ditentukan multiplisitas dari setiap nilai eigen. Karena multiplisitas itu sama dengan basis ruang vektor eigen yang besesuaian dengan i, i = 1, 2, 3, 4 dan basis merupakan baris nol pada matriks, subtitusikan i ke 𝐴(ΓD 2n ) − 𝑖 𝐼 dan dengan mereduksi matriks menggunakan meode Gauss Jordan akan diperoleh matriks eselon baris tereduksi. Dengan melihat basis pada matriks tersebut diperoleh: untuk 𝜆1 =

𝑛−1 2

+

𝑛−1 𝑛+

𝑛−1 2 2

setelah dieliminasi ke 𝐴(ΓD 2n ) − 1 𝐼, diperoleh matriks

eselon baris dengan 1 baris yang nol. Jadi untuk 𝜆1 =

𝑛−1 2

+

𝑛−1 𝑛+

𝑛−1 2 2

memiliki

multiplisitas sebanyak 1. Untuk 𝜆2 = 0 setelah dieliminasi ke 𝐴(ΓD 2n ) − 2 𝐼, diperoleh matriks eselon baris dengan n – 2 baris yang nol. Jadi untuk 𝜆2 = 0 memiliki multiplisitas sebanyak n – 2. Untuk 𝜆3 = −1 setelah dieliminasi ke 𝐴(ΓD 2n ) − 3 𝐼, diperoleh matriks eselon baris dengan 162



Volume 2

n – 1 baris yang nol. Jadi untuk 𝜆3 = −1 memiliki multiplisitas sebanyak n – 1. Untuk 𝜆4 =

𝑛−1 2

−

𝑛−1 𝑛+

𝑛−1 2 2

setelah dieliminasi ke 𝐴(ΓD 2n ) − 4 𝐼, diperoleh matriks

eselon baris denga 1 baris yang nol. Jadi untuk 𝜆4 =

𝑛−1 2

+

𝑛−1 𝑛+

𝑛−1 2 2

memiliki

multiplisitas sebanyak 1. Sehingga diperoleh: spec (𝛤𝐷2𝑛 )=

𝑛−1 2

+

𝑛−1 2 2

𝑛−1 𝑛+

0

1

𝑛−1 2

−1

−

𝑛−1 𝑛+

𝑛−2 𝑛−1

𝑛−1 2 2

1

Lemma 2: Misalkan Γ𝐷2𝑛 graf non commuting dari grup dihedral𝐷2𝑛 dengan n genap dan 𝑛 ≥ 6, maka polinomial karakteristik matriks adjacency 𝐴 Γ𝐷2𝑛 adalah: p(𝜆)= 1 𝜆 𝑛2 − 2𝑛

𝑛−2

−1

𝑛 −2 2

𝜆 −𝑛 1 . 2𝑛−4

−2𝜆 − 𝜆2

2𝑛 2 −4𝑛

𝑛 −4 2

2𝑛 − 4 𝜆 +

− 𝑛−2 (𝑛+2) 𝜆− 𝑛−4 𝜆 2 +𝜆 3 𝑛 +𝜆 2

Bukti: Diketahui grup dihedral 𝐷2𝑛 = {1, r, r2, …, rn-1, s, sr, sr2, …, srn-1}. Diperoleh bahwa 𝑛

Z(𝐷2𝑛 ) = {1, 𝑟 2 }untuk n ganjil. Dengan demikian graf non commuting 𝐷2𝑛 mempunyai 𝑛

𝑛

himpunan titik {r, r2, …, rn-1, s, sr, sr2, 𝑠𝑟 2 , 𝑠𝑟 2 +1 , …, 𝑠𝑟 𝑛−2 , srn-1}. Jumlah himpunan titiknya adalah 2𝑛 − 2 dari grup dihedral 𝐷2𝑛 . Karena n genap, maka 𝑠𝑟 𝑖 ≠ 𝑟 𝑖 𝑠, 𝑖 = 1, 2, … , 𝑛 − 1, artinya s dan 𝑟 𝑖 saling terhubung langsung di graf non commuting 𝐷2𝑛 .Demikian juga, karena n genap, maka 𝑠𝑟 𝑖 𝑠𝑟 𝑗 ≠ 𝑠𝑟 𝑗 𝑠𝑟 𝑖 , j=1, 2,..., n-1 dan 𝑖 = 1, 2, … , 𝑛 − 1, dengan 𝑖 ≠ 𝑗, yang berarti 𝑛

𝑠𝑟 𝑖 dan 𝑠𝑟 𝑗 saling terhubung langsung di graf non commuting D2𝑛 kecualijika 𝑠𝑟 𝑖 𝑠𝑟 𝑗 = 𝑟 2 yang berarti 𝑠𝑟 𝑖 dan 𝑠𝑟 𝑗 tidak saling terhubung langsung di graf non commuting D2𝑛 maka diperoleh matriks keterhubungan titik:

𝐴 ΓD 2𝑛

𝑟 𝑟2 ⋯ 𝑟 0 𝑟2 0 ⋮ ⋮ 𝑟 𝑛−1 0 𝑠 1 𝑠𝑟 1 𝑠𝑟 2 1 ⋮ = 𝑛 ⋮ 𝑠𝑟 2 −1 1 𝑛 𝑠𝑟 2 1 𝑛 𝑠𝑟 2 +1 1 ⋮ ⋮ 𝑛−2 1 𝑠𝑟 𝑠𝑟 𝑛−1 1

𝑟 𝑛−1 𝑠 0 0 ⋮ 0 1 1 1 ⋮ 1 1 1 ⋮ 1 1


… … ⋱ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯

0 0 ⋮ 0 1 1 1 ⋮ 1 1 1 ⋮ 1 1

𝑛

𝑛

𝑛

𝑠𝑟 𝑠𝑟 2 ⋯ 𝑠𝑟 2 −1 𝑠𝑟 2 𝑠𝑟 2 +1 ⋯ 𝑠𝑟 𝑛−2 𝑠𝑟 𝑛−1 1 1 1 1 1 1 ⋮ ⋮ ⋮ 1 1 1 0 1 1 1 0 1 1 1 0 ⋮ ⋮ ⋱ 1 1 1 0 1 1 1 0 1 ⋱ ⋱ ⋱ 1 1 1 1 1 1

⋯ 1 1 1 ⋯ 1 1 1 ⋯ ⋮ ⋮ ⋮ ⋯ 1 1 1 ⋯ 1 0 1 ⋯ 1 1 0 ⋱ 1 1 1 ⋱ ⋮ ⋮ ⋮ ⋱ 0 1 1 ⋱ 1 0 1 ⋱ 1 1 0 ⋮ ⋱ ⋱ ⋱ ⋱ 1 1 1 ⋱ 0 1 1

⋯ 1 1 ⋯ 1 1 ⋯ ⋮ ⋮ ⋯ 1 1 ⋯ 1 1 ⋱ 1 1 ⋱ 0 1 ⋮ ⋯ ⋱ ⋱ 1 0 ⋱ 1 1 ⋱ 1 1 ⋱ ⋮ ⋮ ⋯ 0 1 ⋯ 1 0 163

Volume 2


Setelah mendapatkan bentuk matriks adjacency maka akan dicari nilai eigen dan vektor eigen dari matriks tersebut dengan menyelesaikan persamaan de𝑡 𝐴 ΓD 2n − 𝑟2 ⋯

𝑟

de𝑡 𝐴 ΓD 2n − 𝑟 𝑟2 ⋮

−𝜆 0 ⋮ 0 1 1 1 ⋮ 1 1 1 ⋮ 1 1

𝑟 𝑛−1 𝑠 𝑠𝑟 𝑠𝑟 2 ⋮ 𝑛

𝑠𝑟 2 −1 𝑛

𝑠𝑟 2 𝑛

𝑠𝑟 2 +1 ⋮ 𝑛−2 𝑠𝑟 𝑠𝑟 𝑛−1

𝑟 𝑛−1 𝑠

𝑠𝑟

𝑠𝑟 2

𝑛

𝑛

 𝐼 =0:

𝑛

𝑠𝑟 2 −1 𝑠𝑟 2 𝑠𝑟 2 +1 ⋯

⋯

𝑠𝑟 𝑛−2 𝑠𝑟 𝑛−1

𝐼 =

0 −𝜆 ⋮ 0 1 1 1 ⋮ 1 1 1 ⋮ 1 1

… 0 … 0 ⋱ ⋮ ⋯ −𝜆 ⋯ 1 ⋯ 1 ⋯ 1 ⋯ ⋮ ⋯ 1 ⋯ 1 ⋯ 1 ⋯ ⋮ ⋯ 1 ⋯ 1

1 1 ⋮ 1 −𝜆 1 1 ⋮ 1 0 1 ⋱ 1 1

1 1 ⋮ 1 1 −𝜆 1 ⋮ 1 1 0 ⋱ 1 1

1 1 ⋮ 1 1 1 −𝜆 ⋱ 1 1 1 ⋱ 1 1

⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋱ ⋱ ⋱ ⋱ ⋱ ⋮ ⋱ ⋱

1 1 ⋮ 1 1 1 1 ⋮ −𝜆 1 1 ⋱ 1 0

1 1 ⋮ 1 0 1 1 ⋮ 1 −𝜆 1 ⋱ 1 1

1 1 ⋮ 1 1 0 1 ⋮ 1 1 −𝜆 ⋱ 1 1

⋯ 1 ⋯ 1 ⋯ ⋮ ⋯ 1 ⋯ 1 ⋱ 1 ⋱ 0 ⋮ ⋯ ⋱ 1 ⋱ 1 ⋱ 1 ⋱ ⋮ ⋯ −𝜆 ⋯ 1

1 1 ⋮ 1 1 1 1 ⋱ 0 1 1 ⋮ 1 −𝜆

Diperoleh matriks segitiga atas dari 𝐴 ΓD 2𝑛 − λI sebagai berikut: 𝒓𝟐 ⋯

𝒓 𝒓 𝒓𝟐 ⋮ 𝒓𝒏−𝟏 𝒔 𝒔𝒓 𝒔𝒓𝟐 ⋮ 𝒏

1 0 ⋮ 0 0 0 0 ⋮ 0 0 0 ⋮ 0

1 𝜆 ⋮ 0 0 0 0 ⋮ 0 0 0 ⋮ 0

… … ⋱ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯

1 𝜆 ⋮ 𝜆 0 0 0 ⋮ 0 0 0 ⋮ 0

𝒔𝒓𝟐−𝟏 𝒏 𝒔𝒓𝟐 𝒏 𝒔𝒓𝟐+𝟏 ⋮ 𝒔𝒓𝒏−𝟐 𝒔𝒓𝒏−𝟏 0 0 ⋯ 0

𝒓𝒏−𝟏

𝒔

𝒔𝒓𝟐

𝒔𝒓

𝒏

⋯ 𝒔𝒓𝟐−𝟏

𝒏

𝒏

𝒔𝒓𝟐 𝒔𝒓𝟐+𝟏

𝒔𝒓𝒏−𝟐

⋯

−𝜆 1 − 𝜆2 ⋮ 𝑛 − 3 − 𝜆2 𝜆 0 0 ⋮ 0 0 0 ⋱ 0

1 1 + 𝜆2 ⋮ 𝑛 − 3 + 𝜆2 0 −1 0 ⋮ 0 0 0 ⋱ 0

1 1 + 𝜆2 ⋮ 𝑛 − 3 + 𝜆2 0 0 −1 ⋱ 0 0 0 ⋮ 0

⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋱ ⋱ ⋯ ⋱ ⋱ ⋮ 0

1 1 + 𝜆2 ⋮ 𝑛 − 3 + 𝜆2 0 0 0 ⋮ −1 0 0 ⋱ 0

0 1 ⋮ 𝑛−3 −𝜆 2+𝜆 2+𝜆 ⋮ 2+𝜆 −2𝜆 − 𝜆2 0 ⋱ 0

1 1 + 𝜆2 ⋮ 𝑛 − 3 + 𝜆2 0 −𝜆 − 1 0 ⋮ 0 2𝜆 + 𝜆2 −2𝜆 − 𝜆2 ⋱ 0

⋯ ⋯ ⋯ ⋯ ⋯ ⋱ ⋱ ⋮ ⋱ ⋱ ⋱ ⋱ ⋯

1 1 + 𝜆2 ⋮ 𝑛 − 3 + 𝜆2 0 0 0 −𝜆 − 1 0 0 0 ⋱ 2𝑛 − 4 𝜆 + 𝑛2 − 2𝑛

0

0

0

0

0

0

0

⋯

0

𝒔𝒓𝒏−𝟏

1 . 2𝑛 − 4

1 1 + 𝜆2 ⋮ 𝑛 − 3 + 𝜆2 0 0 0 ⋱ −𝜆 − 1 0 0 ⋮ − 𝑛 − 2 𝜆 − 𝜆2 𝜆 −𝑛 2𝑛2 − 4𝑛 − 𝑛 − 2 (𝑛 + 2) 𝜆 − 𝑛 − 4 𝜆2 + 𝜆3 𝑛 2

+𝜆

Polinomial karakteristik dari 𝐴 ΓD 2𝑛 − λI adalah det 𝐴 ΓD 2𝑛 − λI , merupakan hasil perkalian semua unsur diagonal utama matriks segitiga atas tersebut, sehingga diperoleh: p(𝜆)= 1 𝜆 𝑛2 − 2𝑛

𝑛−2

−1

𝑛 −2 2

−2𝜆 − 𝜆2

𝑛 −4 2

2𝑛 − 4 𝜆 +

𝜆 −𝑛 2𝑛 2 −4𝑛 − 𝑛−2 𝑛+2 𝜆− 𝑛−4 𝜆 2 +𝜆 3 1 . 𝑛 2𝑛−4 +𝜆 2

Teorema 2: Spektrum D2n dengan n genap dan 𝑛 ≥ 6 diperoleh: Specc (𝛤𝐷2𝑛 )=

𝑛−2 2

+

5𝑛 2 −12𝑛+4 4

1

0

−2

𝑛−2 2

3𝑛−6 2

𝑛−2 2

−

5𝑛 2 −12𝑛+4 4

1

Bukti: Dari lemma 2, diperoleh bahwa

164



p(𝜆)= 1 𝜆 𝑛2 − 2𝑛

𝑛−2

𝑛 −2 2

−1

−2𝜆 − 𝜆2

𝑛 −4 2

Volume 2

2𝑛 − 4 𝜆 +

𝜆 −𝑛 2𝑛 2 −4𝑛 − 𝑛−2 𝑛+2 𝜆− 𝑛−4 𝜆 2 +𝜆 3 1 . 𝑛 2𝑛−4 +𝜆 2

Sehingga diperoleh nilai eigen 𝜆1 =

𝑛−2 5𝑛2 − 12𝑛 + 4 + , 𝜆2 = 0, 2 4

𝜆3 = −2,

𝑛−2 5𝑛2 − 12𝑛 + 4 − 2 4

𝜆4 =

Selanjutnya akan ditentukan multiplisitas dari setiap nilai eigen. Karena multiplisitas itu sama dengan basis ruang vektor eigen yang besesuaian dengan i, i = 1, 2, 3, 4 dan basis merupakan baris nol pada matriks, subtitusikan i ke 𝐴(ΓD 2n ) − 𝑖 𝐼 dan dengan mereduksi matriks menggunakan meode Gauss Jordan akan diperoleh matriks eselon baris kita tereduksi. Dengan melihat basis pada matriks tereduksi tersebut diperoleh: untuk 𝜆1 =

𝑛−2 2

5𝑛 2 −12𝑛+4 4

+

setelah dieliminasi ke 𝐴(ΓD 2n ) − 1 𝐼, diperoleh matriks eselon

baris dengan 1 baris nol. Jadi untuk 𝜆1 =

𝑛−2 2

+

5𝑛 2 −12𝑛+4 4

memiliki multiplisitas sebanyak 1.

Untuk 𝜆2 = 0 setelah dieliminasi ke 𝐴(ΓD 2n ) − 2 𝐼, diperoleh matriks eselon baris dengan 𝑛−2 baris 2

nol. Jadi untuk 𝜆2 = 0 memiliki multiplisitas sebanyak

𝑛−2 . 2

dieliminasi ke 𝐴(ΓD 2n ) − 3 𝐼, diperoleh matriks eselon baris dengan 𝜆3 = −2 memiliki multiplisitas sebanyak Untuk 𝜆4 =

𝑛−2 2

5𝑛 2 −12𝑛+4 4

−

Untuk 𝜆3 = −2 setelah

3𝑛−6 baris 2

nol. Jadi untuk

3𝑛−6 . 2

setelah dieliminasi ke 𝐴(ΓD 2n ) − 4 𝐼, kita temukan diperoleh

matriks eselon baris denga 1 baris nol. Jadi untuk 𝜆4 =

𝑛 −2 2

−

5𝑛 2 −12𝑛+4 4

memiliki

multiplisitas sebanyak 1. Sehingga diperoleh: Specc (𝛤𝐷2𝑛 )=

𝑛−2 2

+

5𝑛 2 −12𝑛+4 4

1

0

−2

𝑛−2 2

3𝑛−6 2

𝑛−2 2

−

5𝑛 2 −12𝑛+4 4

1

KESIMPULAN DAN SARAN Berdasarkan pembahasan dapat disimpulkan bahwa spektrum Adjacency graf non commuting pada grup dihedral (𝐷2𝑛 ) dengan n adalahbilangan asli ganjil diperoleh spektrum Adjacency nya:


165

Volume 2


𝑠𝑝𝑒𝑐𝑐 𝛤𝐷2𝑛 𝑛−1 + = 2

𝑛−1 𝑛+

𝑛−1 2

2

0

1

−1

𝑛−1 − 2

𝑛−2 𝑛−1

𝑛−1 𝑛+

𝑛−1 2

2

∀𝑛

1

≥ 3 danganjil Specc (𝛤𝐷2𝑛 )=

𝑛−2 2

+

5𝑛 2 −12𝑛+4 4

1

0

−2

𝑛−2 2

3𝑛−6 2

𝑛−2 2

−

5𝑛 2 −12𝑛+4 4

∀ 𝑛 ≥ 6 dangenap

1

Berbagai macam spektrum dapat diperoleh dari suatu matriks, sehingga disarankan bagi pembaca untuk mencari rumus spektrum yang lain dari grup dihedral (𝐷2𝑛 ). DAFTAR PUSTAKA Abdollahi, A., Akbari, S., & Maimani, H. 2006. Non-commuting Graph of a Group. Journal Of Algebra, vol 298 pp: 468-492. Abdussakir, Ikawati, DSE, and Sari, FKN.. 2012. Spektrum Adjacensy, Spektrum Laplace, Spektrum Signless-Laplace, dan Spektrum Detour Graf Multipatisi Komplit. Malang: UIN Maliki Malang Ayyaswamy, S.K. and Balachandran, S.. 2010. On Detour Spectra of Some Graph. International Journal of Computational and Mathematical Sciences, vol 4 pp:250-252. Biggs, Norman. 1974. Algebraic Graph Theory. Cambride: Cambride University Press. Biyikoglu, T., Leydold, J., & Stadler, P. F. 2007. Laplacian Eigenvectors of Graphs. Berlin: Springer. Chartrand, G., & Lesniak, L. 1996. Graph and Digraph Third Edition. Calfornia: Wadsworth Inc. Raisinghania, M.D., Aggarwal, R. S.. 1980. Modern Algebra. New delhi: S. Chand & Company Ltd. Yin, S.. 2008. Investigation os Spectrum of the Adjacency and Laplacian Matrixx of Graph Gl. WSEAS TRANSACTION on SYSTEM, vol 7 pp: 362-372.

166



Volume 2

OPTIMASI HASIL PANEN PADI MENGGUNAKAN SINGULAR VALUE DECOMPOSITION (SVD) DANANT COLONY OPTIMIZATION (ACO) Vina Puspita Dewi 1), Hanna Arini Parhusip 2), Lilik Linawati 3) 1) Mahasiswa Program Studi Matematika FSM UKSW 2), 3) Dosen Program Studi Matematika FSM UKSW Fakultas Sains dan Matematika, Universitas Kristen Satya Wacana Jl. Diponegoro 52-60 Salatiga 50711 E-mail: [email protected]), [email protected]), [email protected]) Abstrak Hasil panen padi di Kota Surakarta pada tahun 1992-2012 akan ditentukan periode tanam yang optimal. Untuk mendapatkan periode tanam yang optimal maka perlu menyusun fungsi tujuan. Fungsi tujuan yang dipilih adalah berbentuk kuadratik yang parameterparameternya ditentukan menggunakan Singular Value Decomposition (SVD). Ant Colony Optimization (ACO) ACO merupakan algoritma optimasi yang menggunakan perilaku semut. ACO menghasilkan periode III (September – Desember) sebagai periode yang optimal. Hasil gabah per hektar yang diperoleh adalah 43.8 ton Kata Kunci:Ant Colony Optimization (ACO), Singuler Value Decomposition (SVD)

PENDAHULUAN Kajian optimasi hasil panen padi di kota Surakarta berdasarkan data BPS Surakarta untuk mencari periode tanam optimal (maksimal) pernah dilakukan menggunakan pemrograman kuadratik. Ada tiga periode tanam dalam satu tahun yaitu periode I (Januari-April), periode II (Mei-Agustus), dan periode III (September-Desember). Kajian didasarkan pada data hasil panen padi tahun 1992-2012. Analisis dilakukan untuk setiap periode tanam, sehingga pada masingmasing periode tanam dibuat fungsi tujuan yang berbentuk kuadratik. Parameter-parameter fungsi tujuan ditentukan menggunakan metode kuadrat terkecil dan diperoleh periode tanam yang optimal (maksimal) adalah periode tanam III. Jadi hampir setiap tahun periode yang optimal adalah pada periode III (Dewi, dkk, 2013). Terdapat beberapa metode optimasi non linear modern diantaranya Simulated Annealing, algoritma genetik, Ant colony optimization (ACO), dan Particle Swarm Optimization (PSO). Pada penelitian ini akan digunakan ACO untuk menentukan periode tanam optimal dan diharapkan akan memberikan hasil yang sama dengan hasil penelitian menggunakan pemrograman kuadratik. ACO dibuat berdasarkan perilaku kooperatif dari koloni semut di alam yang dapat menemukan lintasan terpendek dari sarang semut ke suatu sumber makanan. Metode ini dikembangkan oleh Dorigo pada awal 1990-an (Rao, 2009). Untuk fungsi tujuan disusun menggunakan Singuler Value Decomposition (SDV) dan diharapkan nilai error

terhadap

parameter-parameter fungsi tujuan yang diperoleh lebih kecil. Penelitian mengenai Ant Colony Optimiation (ACO) sudah pernah dilakukan oleh beberapa peneliti diantaranya untuk menyelesaikan permasalahan penjadwalan mesin pararel (Chang, dkk, 2008), menyelesaikan permasalahan job shop dengan menggunakan ACO (Seo Makalah Pendamping: Matematika 1

167

Volume 2


&Kim, 2008), dan untuk mengoptimalkan reduksi warna pada sirup stevioside (Parhusip & Martono, 2012).

DASAR TEORI Ant Colony Optimization (ACO) Menurut Rao (2009) ACO dapat dijelaskan dengan menampilkan masalah optimasi dalam grafik multilayer sebagaimana ditunjukkan pada Gambar 1 dengan banyaknya variabel sama dengan banyaknya layer. Sedangkan banyaknya titik/node pada tiap layer sama dengan banyaknya titik diskrit yang diijinkan berkaitan dengan variabel keputusan. rumah

Layer 1(x1)

x11

x12

x13

x14

x15

Layer 2 (x2)

x21

x22

x23

x24

x25

Layer 3 (x3)

x31

x32

x33

x34

x35

Layer 4 (x4)

x41

x42

x43

x44

x45

Tujuan (makanan)

168



Volume 2

Gambar 1. Grafik multilayer untuk Ant Colony Optimization (ACO) 𝑥𝑖 = variabel ke-i.

i=1,2,...,n

𝑥𝑖𝑗 = lintasan pada node ke-i dan posisi ke-j.

j=1,2,...,m

Berikut ini model cara semut berjalan dari rumah/sarang menuju ke node tujuan dan kembali lagi ke rumah/ sarangnya: 1. Sifat Perilaku Semut dalam Perjalanan Menuju Tujuan Seekor semut berjalan dari titik awal yaitu rumah menuju ke layer pertama sampai ke layer terakhir dan akan berhenti sampai ke node tujuan (makanan). Semut ke-k pada lokasi node i untuk menuju posisi ke-j sebagai posisi selanjutnya menggunakan jejak feromon  ij pada probabilitas 𝛼 𝜏 𝑖𝑗

(𝑘) 𝜌𝑖𝑗

𝛼 (𝑘) 𝜏 𝑖𝑗 𝑗 ∈𝑁 𝑖

= 0

(𝑘)

, jika𝑗 ∈ 𝑁𝑖 , jika𝑗 ∉

(1)

(𝑘) 𝑁𝑖

dimana  menyatakan derajat kepentingan dari feromon dan

(𝑘)

𝑁𝑖

himpunan node-node pada persekitaran semut ke-k pada posisi i,

menyatakan

kecuali node

predesesor ( yaitu node terakhir yang dikunjungi sebelum i). Hal ini akan menjaga semut ke-k kembali ke node yang sama. 2. Lintasan Kembali dan Memperbaharui Feromon Sebelum ke node rumah (arah mundur), semut ke-kmenyimpan  (k ) feromon pada lintasan yang telah dikunjungi. Nilai feromon  ij pada lintasan (i,j) diperbarui dengan 𝜏𝑖𝑗 ← 𝜏𝑖𝑗 + ∆𝜏 (𝑘)

(2)

Karena ada peningkatan pada feromon , probabilitas lintasan tersebut akan dipilih semut lain juga akan semakin meningkat. 3. Penguapan Jejak Feromon Ketika seekor semut ke-kbergerak ke node berikutnya, feromon yang dapat dinyatakan sebagai 𝜏𝑖𝑗 ← 1 − 𝜌 𝜏𝑖𝑗 ; ∀ 𝑖, 𝑗 𝜖𝐴

(3)

dimana 𝜌  (0,1] adalah laju penguapan (yang dikenal juga sebagai faktor penurunan feromon) dan A menyatakan segmen atau lintasan yang dilalui oleh semut ke-k dari rumah ke tujuan. Penurunan intensitas feromon menyebabkan eksplorasi pada lintasan yang berbeda-beda selama proses pencarian. Hal ini menyebabkan adanya eliminasi dari pemilihan lintasan yang buruk sehingga jejak feromon dapat menghasilkan nilai


169

Volume 2


yang maksimum.Suatu iterasi dikatakan lengkap jika meliputi pergerakan semut, penguapan feromon dan penyimpanan feromon. Setelah semua semut ke-k kembali ke titik sarang (rumah) , informasi feromon diperbaharui berdasarkan hubungan 𝑁 (k) 𝑘=1 ∆𝜏𝑖𝑗

𝜏𝑖𝑗 = 1 − 𝜌 𝜏𝑖𝑗 +

(4)

dimana  ij adalah banyaknya feromon yang disimpan pada lintasan ij oleh semut ke(k )

k. Tujuan feromon diperbaharui adalah untuk meningkatkan nilai feromon yang berkaitan dengan baik atau tidaknya lintasan. Feromon disimpan pada lintasan ij terbaik dalam bentuk 𝑄

∆𝜏𝑖𝑗 (k) = 𝐿

(5)

𝑘

dimana Q menyatakan suatu konstan dan Lk adalah panjang lintasan yang dilalui oleh semut ke-k (seperti dari 1 kota ke kota lain). Persamaan (5) dapat diimplementasikan sebagai (𝑘)

∆𝜏𝑖𝑗 =

𝜍𝑓 𝑡𝑒𝑟𝑏𝑎𝑖𝑘 𝑓 𝑡𝑒𝑟𝑏𝑢𝑟𝑢𝑘

; jika 𝑖, 𝑗 ∈ perjalanan global terbaik

0;

untuk yang lain

(6)

fterbaik= nilai terbaik fungsi tujuan fterburuk= nilai terburuk fungsi tujuan



= parameter yang digunakan untuk mengkontrol pembaharuan feromon

Fungsi Tujuan ACO Menggunakan Singular Value Decomposition (SVD) Pada penelitian ini digunakan fungsi tujuan kuadratik dengan parameter-parameternya dicari menggunakan Singuler Value Decomposition (SDV). Parameter-parameter fungsi tujuan yang akan dicari adalah 𝑆𝑖 = 𝛼1 𝑥𝑖2 + 𝛼2 𝑦𝑖2 + 𝛼3 𝑥𝑖 𝑦𝑖 + 𝛼4 𝑥𝑖 + 𝛼5 𝑦𝑖 + 𝛼6

(7)

Persamaan (7) dalam bentuk matriks dapat ditulis: 𝐴𝑣𝛼 = 𝑆

(8)

dimana 𝑥12 2 A= 𝑥2 ⋮ 𝑥𝑛2

𝑦12 𝑦22 ⋮ 𝑦𝑛2

𝑥1 𝑦1 𝑥2 𝑦2 ⋮ 𝑥𝑛 𝑦𝑛

𝑥1 𝑥2 ⋮ 𝑥𝑛

𝑦1 𝑦2 ⋮ 𝑦𝑛

1 1 ⋮ 1

(8a)

𝑣𝛼 = 𝛼1 𝛼2 𝛼3 𝛼4 𝛼5 𝛼6 xi = data ke- i variabel 1 y i = data ke- i variabel 2

𝑆 = S i = data ke- i variabel 3 170

i = 1,2,...,n; n= banyaknya data Makalah Pendamping: Matematika 1


𝛼𝑗 = parameter fungsi tujuan

Volume 2

j = 1,2,...,6 𝐴 = 𝑈𝛴𝑉 𝑇

(9) nxm

Menurut Watkins (1991) pada persamaan (9) jika matriks Aϵ R 𝑇

mempunyai rankr,

maka terdapat matriks dengan kolom-kolom dari nilai eigen 𝐴𝐴 U ϵ R , Σ adalah matriks nxn

diagonal dari akar nilai eigen 𝐴𝐴𝑇 Σ ϵ Rnxm, dan V adalah matriks dengan kolom-kolom dari vektor eigen 𝐴𝐴𝑇 V ϵ Rmxm. Dari persamaan (8) dan (9) diperoleh: 𝑈𝛴𝑉 𝑇 𝑣𝛼 = 𝑆 atau 𝛴𝑉 𝑇 𝑣𝛼 = 𝑈 𝑇 𝑆

(10)

Misal 𝑐 = 𝑈 𝑇 𝑆 dan 𝑦 = 𝑉 𝑇 𝑣𝛼 , maka 𝛴𝑦 = 𝑐 sehingga 𝑦 = 𝛴 𝑇 𝑐 Persamaan (8) diselesaikan dengan: 𝑣𝛼 = 𝑉𝑦

(11)

Untuk error : Error= E =

𝑆𝑝𝑒𝑛𝑑𝑒𝑘𝑎𝑡𝑎𝑛 −𝑆𝑑𝑎𝑡𝑎 𝑆𝑑𝑎𝑡𝑎

. 100%

Selain itu dengan menghitung Conditional Number: κ 𝐴 ≡

𝐴−1

𝐴 jika 𝐴 nonsinguler ∞jika 𝐴 singuler

Menurut Anderson, dkk, (1999) jika Conditional Number dibawah 67108864 maka errorinvers dinyatakan baik. Sebaliknya dikatakan tidak baik (ill condition) Setelah mendapatkan fungsi tujuan, agar fungsi tujuan menjadi tidak berkendala maka perlu disusun fungsi Lagrange untuk menyelesaikannya dengan ACO yaitu m        L( x ,  )  f ( x )   i g i ( x ) untuk x  C dan   0

(12)

i 1

Kondisi Karush Kuhn Tucker (KKT) pada persamaan (13) dapat digunakan untuk menemukan



titik kritis dengan menyelesaikan sistem persamaan yang diperoleh dari L  0 . Artinya   mencari pemaksimal x * dan parameter optimal  * yang memenuhi (1).𝜆∗𝑖 ≥ 0



(2). 𝜆∗𝑖 g i ( x*)  0 untuk i = 1,2,…,m. (13) m     f ( x *)  (3).  i * g i ( x*)  0 i 1

Fungsi tujuan mempunyai titik pemaksimal jika bersifat concave (cekung). Menurut Perresini, dkk, (1998) ada beberapa cara untuk menunjukkan fungsi tujuan yang diperoleh concave:


171

Volume 2


1. Jika matriks Hessian fungsi tujuan negative semi definite (setiap nilai eigen ≤ 0) maka 𝑥 ∗ merupakan pemaksimal. 2. Sebuah fungsi 𝑓(𝑥 ) adalah cembung pada sebuah selang  (berhingga atau tak berhingga). Jika untuk setiap dua titik 𝑥 dan𝑦 didalam  dimana 𝑥 dan𝑦 ϵ Rndan untuk semua 0 ≤ 𝜆 ≤ 1berlaku 𝑓 𝜆𝑥 + 1 − 𝜆 𝑦 ≤ 𝜆𝑓 𝑥 + 1 − 𝜆 𝑓(𝑦)

(14)

Jika pernyataan diatas berlaku dengan tanda pertidaksamaan yang terbalik, maka𝑓(𝑥 ) adalah cekung .

METODE PENELITIAN Tahap 1. Penelitian ini didasarkan pada data sekunder yang diperoleh dari BPS kota Surakarta untuk data hasil panen padi tahun 1992-2012. Tahap 2. Data hasil panen padi akan dioptimalkan dengan menggunakan algoritma ACO, dengan parameter fungsi tujuan ditentukan dengan menggunakan SVD. Tahap 3. Menyusun dan menyelesaikan model a. Menyusun fungsi tujuan dengan menggunakan SVD b. Menyusun fungsi Lagrange seperti persamaan (12). c. Mengoptimalkan fungsi Lagrange sesuai dengan algoritma ACO. Tahap 4. Menganalisis hasil dan pembahasan Tahap 5. Membuat kesimpulan.

HASIL PENELITIAN DAN PEMBAHASAN Penyusunan fungsi tujuan dengan menggunakan SVD menghasilkan fungsi tujuan untuk masing-masing periode tanam sebagai berikut: 𝑆𝐼 = 0.8362𝑥 2 − 0.0282 − 0.4457𝑥𝑦 − 0.681𝑥 + 0.4676𝑦 + 0.8401

(15)

𝑆𝐼𝐼 = −0.2253𝑥 2 − 3.1680𝑦 2 + 4.6619𝑥𝑦 − 2.9688𝑥 + 2.5897𝑦 + 0.3584

(16)

𝑆𝐼𝐼𝐼 = 1.1955𝑥 2 + 0.7538𝑦 2 − 0.1339𝑥𝑦 − 1.6698𝑥 − 0.6658𝑦 − 1.3404

(17)

Pada Gambar 1 disajikan data aktual yang dibandingkan dengan data pendekatan untuk setiap periode tanam. Nilai error dari parameter setiap fungsi tujuan menggunakan metode kuadrat terkecil maupun dengan SVD diperlihatkan pada Tabel 1.

172



Volume 2

1 1

1

hasil pendekatan

hasil pendekatan

hasil pendekatan

0.95

0.9

0.95

0.9 0.85

0.85

fungsi tujuan

fungsi tujuan

fungsi tujuan

0.8

0.9

0.7

0.6

0.8 0.75 0.7 0.65

0.8 0.5

0.6

0.75

0.4

0

5

10

15

20

25

0

5

10

15

20

25

0.55

0

indeks

indeks

Periode I

5

10

15

20

25

indeks

Periode II

Periode III

Gambar 2. Grafik hasil panen padi menurut data aktual dan hasil pendekatan fungsi kuadratik pada setiap periode tanam. Tabel 1.Nilai error berdasarkan metode kuadrat terkecil dan SVD serta nilai Conditional Number. Metode yang digunakan Kuadrat terkecil Error Conditional number

Periode I

Periode II

Periode III

9.4%

13.8342%

18.5405%

SVD

7.27%

11.89%

8.43%

Kuadrat terkecil

23568

37013

22201

SVD

162.86

221.188

160.35

Metode SVD memberikan nilai error dan Conditional Number yang lebih kecil jika dibandingkan dengan metode kuadrat terkecil. Begitu juga dengan Conditional Number yang diperoleh. Hal ini dapat disimpulkan bahwa parameter-parameter fungsi tujuan yang diperoleh menggunakan SVD lebih baik jika dibandingkan dengan metode kuadrat terkecil. Perlu dibuat persamaan Lagrange seperti persamaan (12) dengan kendala yaitu 𝑥 ≤𝑥𝑚𝑎𝑘𝑠 dan 𝑦 ≤ 𝑥. Sehingga persamaan (15) sampai (17) menjadi: 𝐿 𝑥 , 𝜆 = 0.8362𝑥 2 − 0.0282𝑦 2 − 0.4457𝑥𝑦 − 0.681𝑥 + 0.4676𝑦 + 0.8401 + 𝜆1 𝑥 − 1 + 𝜆2 𝑦 − 𝑥 − 𝜆3 𝑥 − 𝜆4 𝑦

(18)

𝐿 𝑥 , 𝜆 = −0.2253𝑥 2 − 3.1680𝑦 2 + 4.6619𝑥𝑦 − 2.9688𝑥 + 2.5897𝑦 + 0.3584 + 𝜆1 𝑥 − 1 + 𝜆2 (𝑦 − 𝑥) − 𝜆3 𝑥 − 𝜆4 𝑦

(19)

𝐿 𝑥 , 𝜆 = 1.1955𝑥 2 + 0.7538𝑦 2 − 0.1339𝑥𝑦 − 1.6698𝑥 − 0.6658𝑦 − 1.3404 + 𝜆1 𝑥 − 1 + 𝜆2 (𝑦 − 𝑥) − 𝜆3 𝑥 − 𝜆4 𝑦

(20)

Masing-masing fungsi tujuan diselesaikan berdasarkan algoritma ACO, dan diperoleh penyelesaian seperti pada Tabel 2.


173

Volume 2


Tabel 2.Penyelesaian optimal berdasarkan ACO untuk ketiga periode tanam. Periode I

Periode II

Periode III

*

0.7434

0.7160

0.8087

y*

0.6759

0.6662

0.5663

S*

0.453

0.4396

0.5262

𝜆1

0.62

0.0770

0.3434

𝜆2

0.4832

0.9032

0.6415

𝜆3

0.1436

0.2022

0.8831

𝜆4

0.1831

0.0134

0.2934

x

Tabel 3. Kondisi KKT untuk setiap periode tanam. Periode I

Periode II

Periode III

Kondisi I

Terpenuhi

Terpenuhi

Terpenuhi

Kondisi II

-0.1591

-0.0219

-0.0657

-0.0326

-0.045

-0.1555

-0.1068

-0.1448

-0.7142

-0.1225

-0.0089

-0.1662

0.3845

-1.3547

-0.5233

0.6007

1.5464

-1.1220

-0.4157

-0.4088

-0.2920

-0.1001

-0.0536

-0.3256

-0.8502

-1.3627

-1.3275

-0.7984

-0.8009

-1.0664

Kondisi III

Kondisi KKT pada Tabel 3 tidak terpenuhi sehingga 𝑥 ∗ bukan merupakan pemaksimal dan parameter 𝜆∗tidak optimal. Selain itu dengan mencari niai eigen dari matriks Hessian fungsi Lagrange. Diperoleh nilai eigen untuk setiap periode tanam yaitu: 

Periode I: [-1.47; -1.01; 0; 0; 1.14; 2.95]



Periode II: [-9.24; -0.65; 0; 0; 0.29; 2.81]



Periode III: [-0.98; -0.48; 0; 0; 2.27; 4.61]

Dari ketiga periode tanam diatas nilai eigen untuk masing-masing periode tanam tidak ada yang bersifat negative semi definite, sehingga 𝑥 ∗ bukan merupakan pemaksimal. Cara selanjutnya yaitu menguji persamaan (14), dari Gambar 3 dapat disimpulkan bahwa untuk setiap periode tidak terlihat secara signifikan bersifat convex atau concave.

174



Volume 2

-1.34

0.5 0.86

ruas kiri ruas kanan


0.85


-1.36 -1.38

0.84

0.45 -1.4

0.83

-1.42

0.82

-1.44

0.81

0.4

0.8

-1.46

0.79

-1.48

0.78

1

2

3

4

5

6

7

8

9

0.35

10

1

2

3

4

Periode I

5

6

7

8

9

10

-1.5

1

2

3

4

5

Periode II

6

7

8

9

10

Periode III

Gambar 3. Fungsi tujuan convex atau concave.

Tabel 4.Penyelesaian optimal untuk ketiga periode tanam dalam bentuk data berdimensi.

Luas Tanam

Metode yang digunakan

Periode I

Periode II

Periode III

Pemrograman Kuadratik

132.9505

54.6966

120.4908

ACO

118.944

109.55

142.33


120.4864

105.2448

76.1586

ACO

98

103.9

63.99


61.7237

55.8306

60.4087

ACO

29.18

34.31

43.8

Akhir (ha) Luas Panen (ha) Hasil gabah (ton)

Dapat dijelaskan dari Tabel 4 bahwa periode tanam yang optimal adalah periode III, dimana hasil gabah yang didapat dalam satu hektar sawah adalah 43.8 ton. Pada penelitian yang pernah dilakukan menggunakan pemrograman kuadratik periode optimal adalah periode III. Secara informal (dari data) periode III merupakan periode yang maksimal hampir di setiap tahunnya. Pada dasarnya ACO tidak baik karena

 L  0 tidak terpenuhi, untuk itu

menggunakan fungsi tujuan seperti persamaan (18) sampai (20) diselesaikan dengan pemrograman kuadratik menurut dewi,dkk, (2013). Hasil untuk pemrograman kuadratik diperoleh pada Tabel 5.

Tabel 5. Penyelesaian fungsi tujuan SVD dengan pemrograman kuadratik Periode I

Periode II

Periode III

Luas Tanam Akhir

47.12

41.922

127.8992

Luas Panen

42.7025

95.2068

57.2006

Hasil gabah

35.8976

56.6334

59.2967


175

Volume 2


Menggunakan pemrograman kuadratik diperoleh hasil yang lebih optimal dibandingkan dengan ACO. Hasil optimasinya juga menunjukkan periode III merupakan periode optimal.

SIMPULAN DAN SARAN Analisis hasil panen padi berdasarkan ACO yang parameternya ditentukan menggunakan SVD memberikan hasil bahwa periode III merupakan periode optimal. Hal ini mendukung hasil penelitian pada data yang sama dengan analisis menggunakan pemrograman kuadratik dan parameter ditentukan berdasarkan metode kuadrat terkecil bahwa periode III merupakan periode optimal. Menggunakan fungsi tujuan yang diperoleh dari SVD dan mengoptimasi dengan pemrograman kuadratik periode III merupakan periode yang optimal. Hasil ACO jika dibandingkan dengan pemrograman kuadratik lebih optimal pemrograman kuadratik.

DAFTAR PUSTAKA Anderson, E. dkk.(1999). LAPACK User's Guide Third Edition, SIAM, Philadelphia. (http://www.netlib.org/lapack/lug/lapack_lug.html) Chang, P.T. dkk. (2008). Ant colony optimization system for a multi-quantitative and qualitative objective job-shop parallel-machine-scheduling problem. International Journal of Production Research,Vol. 46, No. 20, 15 October 2008, 5719–5759. Dewi, V.P. Parhusip, H.A. & Linawati, L. (2013). Analisis hasil panen padi menggunakan pemodelan kuadratik. Prosiding (dalam proses), Seminar Nasional Matematika VII yang diselenggarakan oleh jurusan Matematika FMIPA dan Prodi Pendidikan Matematika Program Pasca Sarjana UNNES tanggal 26 Oktober 2013.Semarang: Universitas Negeri Semarang. Parhusip, H.A. &Martono, Y.(2012). Optimization Of Colour Reduction For Producing Stevioside Syrup Using Ant Colony Algorithm Of Logistic Function, proceeding of The Fifth International Symposium on Computational Science,ISSN:2252-7761,Vol1, pp91101, GMU. Peressini, A.L. Sullivan, F.E. & Uhl, J. (1998). The Mathematics of Nonlinear Programing, Springer Verlag, New York,Inc. Rao, S.S. (2009). Engineering Optimization, Theory and Practice, John Wiley & Sons, Inc., Hoboken, New Jersey. Seo, M. & Kim, D. (2010). Ant colony optimisation with parameterised search space for the job shop scheduling problem. International Journal of Production Research.Vol. 48, No. 4, 15 February 2010, 1143–1154 Watkins, D.S. (1991). Fundamentals of Matrix Computations, John Wiley & Sons, New York.

176


KRISTALOGRAFI BIDANG DATAR BATIK CAP

Recommend Documents