Seminar Nasional matematıka

Seminar Nasional mATEmATıKA

VOL. 11 TH. 2016

ISSN 1907-3909

UNIVERSITAS KATOLIK PARAHYANGAN PARAHYANGAN CATHOLIC UNIVERSITY

FAKULTAS TEKNOLOGI INFORMASI DAN SAINS FACULTY OF INFORMATION TECHNOLOGY AND SCIENCE Jalan Ciumbuleuit 94, Bandung 40141, Indonesia

Seminar Nasional mATEmATıKA VOL. 11 TH. 2016

ISSN 1907-3909

REVIEWERS Dr. J. Dharma Lesmono

Benny Yong, MSi

Dr. Ferry Jaya Permana, ASAI

Farah Kristiani, MSi

Iwan Sugiarto, MSi

Livia Owen, MSi

Agus Sukmana, MSc

Maria Anestasia, MSi

Erwinna Chendra, MSi

Liem Chin, MSi

Taufik Limansyah, SSi, MT

Alamat Redaksi: Jurusan Matematika, FTIS - UNPAR Gedung 9, Lantai 1 Jl. Ciumbuleuit No. 94, Bandung - 40141

KATA PENGANTAR Puji syukur kami panjatkan ke hadirat Tuhan Yang Maha Esa atas terselenggaranya Seminar Nasional Matematika UNPAR 2016. Seminar ini merupakan kegiatan rutin tahunan yang diselenggarakan oleh Jurusan Matematika, Universitas Katolik Parahyangan, yang dimulai sejak tahun 2005 dan tahun ini merupakan tahun ke-12 penyelenggaraannya. Seminar Nasional Matematika UNPAR ini merupakan wadah pertemuan ilmiah antara matematikawan, guru, peneliti, dan praktisi yang tidak hanya terbatas di bidang matematika saja, melainkan juga penerapannya dalam berbagai bidang ilmu, antara lain dunia medis, ekonomi, lingkungan hidup, gejala alam dan penanganan risiko. Seminar tahun ini mengambil tema “PERANAN MATEMATIKA DALAM PENGELOLAAN RISIKO”. Pemilihan tema ini dilatarbelakangi oleh perkembangan yang cukup pesat dari penerapan matematika di industri keuangan termasuk di dalam pengelolaan risiko suatu perusahaan. Melalui seminar ini diharapkan para peserta dapat saling berbagi pengetahuan dan informasi terbaru sehingga berdampak pada kesiapan yang lebih baik dari Indonesia dalam menghadapi tantangan ini.

Seminar kali ini mengundang tiga orang pembicara dari kalangan akademisi dan praktisi yang akan berbagi pengalaman, gagasan, dan pikiran. Pada sesi pararel, akan dipresentasikan 59 makalah yang merupakan hasil karya dosen, peneliti, dan mahasiswa dari berbagai instansi di tanah air.

Kami atas nama panitia Seminar Nasional Matematika UNPAR 2016 mengucapkan terima kasih atas partisipasinya, semoga bermanfaat bagi semua pihak.

Bandung, September 2016 Ketua Panitia

Dr. J. Dharma Lesmono

i

DAFTAR ISI Kata Pengantar Daftar Isi

...i ...iii-ix

ALJABAR DAN ANALISIS PRIMITIF FUNGSI TERINTEGRAL HENSTOCK-STIELTJES BERNILAI DI RUANG HILBERT Made Benny Prasetya Wiranata dan Ch. Rini Indrati – UGM

...AA 1-8

IDENTITAS BILANGAN FIBONACI DAN BILANGAN LUCAS PADA Z6 Sri Gemawati, Musraini M., Asli Sirait, dan Muslim – Universitas Riau

...AA 9-16

BATAS ATAS PADA NORM-TAK HINGGA DARI INVERS MATRIKS NEKRASOV Euis Hartini – Universitas Padjadjaran

...AA 17-22

PEMBANGKIT SEMIGRUP DAN GRUP Aloysius Joakim Fernandez – Universitas Katolik Widya Mandira

...AA 23-28

STATISTIKA MEMBANGUN APLIKASI STATISTIK DENGAN R SHINY GUI Zulhanif – Universitas Padjadjaran

...ST 1-7

ANALISIS METODE PENGUMPULAN DATA PRODUKTIVITAS BAWANG MERAH DAN CABAI BESAR Anita Theresia – BPS

...ST 8-16

BAYESIAN SPATIAL AUTOREGRESSIVE (BSAR) DALAM MENAKSIR ANGKA PREVALENSI DEMAM BERDARAH (DB) DI KOTA BANDUNG I Gede Nyoman Mindra Jaya, Zulhanif, dan Bertho Tantular – Universitas Padjadjaran …ST 17-24 ESTIMASI REGRESI SEMIPARAMETRIK DENGAN RESPON HILANG MENGGUNAKAN ESTIMATOR TERBOBOT SKOR KECENDERUNGAN Nur Salam – Universitas Lambung Mangkurat

iii

...ST 25-32

PERBANDINGAN METODE ROBUST MELALUI LEAST MEDIAN SQUARE DAN M-ESTIMATOR DALAM MENENTUKAN MODEL WAKTU KELANGSUNGAN HIDUP (SURVIVAL TIME) Soemartini dan Enny Supartini – Universitas Padjadjaran

…ST 33-40

DESAIN SPLIT-BALLOT MTMM UNTUK EVALUASI KUALITAS INSTRUMEN PENGUKURAN Achmad Bachrudin – Universitas Padjadjaran

…ST 41-48

SPARSE MULTINOMIAL LOGISTIC REGRESSION (Studi Kasus Data Kredit Macet di Bank Nasional “N”) M. Fajar Jamiat – Skadron Pendidikan 201 Lanud Sulaiman TNI AU Nusar Hajarisman – Universitas Negeri Islam Bandung Anna Chadidjah – Universitas Padjadjaran

...ST 49-56

ANALISIS KETERTINGGALAN DAERAH DI INDONESIA MENGGUNAKAN REGRESI LOGISTIK BINER Titi Purwandari dan Yuyun Hidayat – Universitas Padjadjaran

…ST 57-62

PENDEKATAN TRUNCATED REGRESSION PADA TINGKAT PENGANGGURAN TERBUKA PEREMPUAN Defi Yusti Faidah, Resa Septiani Pontoh, dan Bertho Tantular – Universitas Padjadjaran

…ST 63-68

ANALISIS VARIANS MULTIVARIATE UNTUK DATA LONGITUDINAL DENGAN PENGUKURAN DATA DILAKUKAN SECARA BERURUT BERDASARKAN WAKTU (REPEATED MEASURE) Enny Supartini dan Soemartini – Universitas Padjadjaran ...ST 69-76 APLIKASI ALGORITMA BOOSTING DALAM REGRESI LOGISTIK Zulhanif – Universitas Padjadjaran …ST 77-81 PENYESUAIAN BAGAN KENDALI ATRIBUT KHUSUSNYA GRAFIK c DENGAN PENDEKATAN EKSPANSI CORNISH-FISHER Irmina Veronika Uskono – Universitas Katolik Widya Mandira ...ST 82-85

MATEMATIKA PENDIDIKAN MENINGKATKAN AKTIVITAS BELAJAR MAHASISWA MELALUI TEKNIK MIND MAP PADA MATA KULIAH MATEMATIKA DISKRIT Ririn Widiyasari – Universitas Muhammadiyah Jakarta ...MP 1-8

iv

PENGEMBANGAN PEMBELAJARAN MATEMATIKA DENGAN PENDEKATAN METAKOGNITIF UNTUK MENINGKATKAN KEMAMPUAN BERPIKIR LOGIS DAN SIKAP POSITIF SISWA SMP Kms. Muhammad Amin Fauzi, Sri Lestari Manurung, dan Arnah Ritonga – Universitas Negeri Medan ...MP 9-17 PENGEMBANGAN BAHAN AJAR MATEMATIK BERBASIS INKUIRI BERBANTUAN MULTI MEDIA UNTUK MENINGKATKAN KEMAMPUAN BERPIKIR KRITIS SISWA SMA SE-PROVINSI SUMATERA UTARA Waminton Rajagukguk, Kms. Muhammad Amin Fauzi, dan Yasifati Hia – Universitas Negeri Medan ...MP 18-25 ANALISIS KESULITAN MAHASISWA DALAM MENYELESAIKAN SOAL KEMAMPUAN ABSTRAKSI MATEMATIS PADA MATA KULIAH STATISTIKA MATEMATIKA Andri Suryana – Universitas Indraprasta PGRI Jakarta ...MP 26-34 PENGEMBANGAN SOAL TIPE PISA DENGAN KONTEKS BATU AKIK Rika Octalisa, Ratu Ilma, dan Somakim – Universitas Sriwijaya ...MP 35-43 FAKTOR PENYEBAB KESALAHAN YANG DILAKUKAN MAHASISWA DALAM MENYELESAIKAN SOAL KEMAMPUAN PEMECAHAN MASALAH MATEMATIS PADA MATA KULIAH TEORI PELUANG Georgina Maria Tinungki – Universitas Hasanuddin

...MP 44-51

PENGEMBANGAN SOAL HOT UNTUK SISWA SMP Indah Sari Kastriandana – Universitas Sriwijaya

...MP 52-58

PEMBELAJARAN MATEMATIKA ANAK BERKEBUTUHAN KHUSUS DI SEKOLAH INKLUSI Chatarina Febryanti dan Ari Irawan – Universitas Indraprasta PGRI Jakarta

...MP 59-64

ALAT PERAGA IRISAN KERUCUT Eyus Sudihartinih dan Tia Purniati – Universitas Pendidikan Indonesia

...MP 65-70

PERBEDAAN PENGARUH BENTUK TES FORMATIF TERHADAP HASIL BELAJAR MATEMATIKA DITINJAU DARI TINGKAT KREATIVITAS SISWA Lasia Agustina – Universitas Indraprasta PGRI

...MP 71-76

v

REPRESENTASI VISUAL PENYELESAIAN SOAL CERITA PECAHAN SISWA SMP Kristoforus Djawa Djong – Universitas Katolik Widya Mandira, Mahasiswa Pasca Unesa

...MP 77-82

PENGARUH PENDEKATAN RECIPROCAL TEACHING TERHADAP KEMAMPUAN BERPIKIR KREATIF MATEMATIKA SISWA Ulfah Hernaeny dan Febrina Lia Dahlia – Universitas Indraprasta PGRI Jakarta ...MP 83-88 PENGARUH GAYA BELAJAR TERHADAP KEMAMPUAN PEMAHAMAN MATEMATIKA Seruni dan Nurul Hikmah – Universitas Indraprasta PGRI

...MP 89-95

PENERAPAN ASESMEN KINERJA MELALUI “PBM” UNTUK MENINGKATKAN KEMAMPUAN BERPIKIR KRITIS, KREATIF MATEMATIK Erik Santoso – Universitas Majalengka

...MP 96-102

PENERAPAN MODEL PEMBELAJARAN TREFFINGER DALAM MENINGKATKAN KEMAMPUAN BERPIKIR KREATIF Roida Eva Flora Siagian – Universitas Indraprasta PGRI Jakarta

...MP 103-109

PENGEMBANGAN BAHAN AJAR BERBASIS PROBLEM BASED LEARNING UNTUK SISWA SMP Asri Nurdayani, Darmawijoyo, dan Somakim – Universitas Sriwijaya

...MP 110-116

ANALISIS PENGARUH SIKAP MAHASISWA PADA MATA KULIAH MATEMATIKA EKONOMI DAN BISNIS TERHADAP PRESTASI BELAJAR Herlina – Universitas Bunda Mulia ...MP 117-121 PENGARUH PENGUASAAN TEKNOLOGI INFORMASI DAN KOMUNIKASI DAN DISIPLIN KERJA TERHADAP PRODUKTIVITAS KERJA GURU Yuan Andinny dan Indah Lestari – Universitas Indraprasta PGRI ...MP 122-130

vi

MATEMATIKA TERAPAN ANALISIS PENGARUH TINGKAT PENGANGGURAN TERBUKA DAN ANGKA MELEK HURUF TERHADAP TINGKAT KEMISKINAN MENGGUNAKAN MODEL FIXED EFFECT (Studi Kasus Wilayah Kabupaten Propinsi Jawa Barat) Ani Andriyati dan Rini Rakhmawati – Universitas Pakuan ...MT 1-8 PENYEBARAN PENYAKIT DEMAM BERDARAH DI SURABAYA MENGGUNAKAN METODE K-MEANS Suzyanna, Purbandini, Indah Werdiningsih, dan Miswanto – Universitas Airlangga Surabaya

...MT 9-16

ENKRIPSI DAN DEKRIPSI TEXT.TXT MENGGUNAKAN KRIPTOSISTEM ELLIPTIC CURVE CRYPTOSYSTEM (ECC) Akik Hidayat, Mira Suryani, dan Akmal – Universitas Padjadjaran

...MT 17-26

PREMI ASURANSI JIWA DWIGUNA LAST SURVIVOR DENGAN DISTRIBUSI PARETO Hasriati, Ihda Hasbiyati, dan T. P. Nababan – Universitas Riau

…MT 27-36

ANALISA PERILAKU KONSUMEN DALAM MENENTUKAN STRATEGI PEMASARAN MENGGUNAKAN CONFIGURAL FREQUENCY ANALYSIS Resa Septiani Pontoh, Defi Yusti Faidah, dan Bertho Tantular – Universitas Padjadjaran

…MT 37-42

MODEL OPTIMASI VAKSINASI Jonner Nainggolan – Universitas Cenderawasih Jayapura

...MT 43-48

PEMANFAATAN FUNGSI MODIFIKASI WEIL PAIRING PADA SKEMA PROXY SIGNATURE Annisa Dini Handayani – Sekolah Tinggi Sandi Negara

...MT 49-54

KONTROL OPTIMUM PADA POPULASI TUMOR DAN WAKTU PENGOBATAN BERDASARKAN MODEL RADIOVIROTHERAPY Embay Rohaeti dan Susi Susanti – Universitas Pakuan

...MT 55-61

INVERS MATRIKS VANDERMONDE Handi Koswara dan Iwan Sugiarto – Universitas Katolik Parahyangan

...MT 62-70

vii

MAHASISWA DISTRIBUSI BETA-PARETO Adrianus Rambe, Siti Nurrohmah, dan Ida Fithriani – Universitas Indonesia

…MS 1-8

PERSAMAAN DIFUSI PADA ZOOPLANKTON Rahmat Al Kafi, Sri Mardiyati, dan Maulana Malik – Universitas Indonesia

…MS 9-16

DISTRIBUSI RAYLEIGH Fitria Andaryani, Siti Nurrohmah, dan Ida Fithriani – Universitas Indonesia

...MS 17-24

PEMILIHAN PORTOFOLIO YANG OPTIMAL DENGAN MENGGUNAKAN METODE ANT COLONY OPTIMIZATION Joseph Martua Nababan dan Liem Chin – Universitas Katolik Parahyangan

...MS 25-32

PENERAPAN ALGORITMA BEE COLONY UNTUK MENYELESAIKAN TRAVELING SALESMAN PROBLEM Refy Kusumah dan J. Dharma Lesmono – Universitas Katolik Parahyangan

...MS 33-40

PEMODELAN PERHITUNGAN PREMI ASURANSI JIWA DWIGUNA UNIT LINK DENGAN GARANSI Bernika Setiawan dan Ferry Jaya Permana – Universitas Katolik Parahyangan

...MS 41-48

PENENTUAN HARGA OPSI SAHAM KARYAWAN (OSK) MODEL HULL-WHITE DENGAN METODE BINO-TRINOMIAL (BTT) Natasha Magdalena dan Erwinna Chendra – Universitas Katolik Parahyangan

...MS 49-58

EKSISTENSI BIONOMIK EQUILOBRIUM PADA MODEL INTERAKSI INDUSTRIALISASI BIOMASSA DAN HEWAN LINDUNG Ganjar, E. Hertini, dan A. K. Supriatna – Universitas Padjadjaran ...MS 59-67 IMPLEMENTASI MODEL HYBRID ARIMA-ANN MENGGUNAKAN FILTER MOVING AVERAGE PADA PERAMALAN NILAI TUKAR DOLAR AS TERHADAP RUPIAH Dian Nurhayati, Bevina D. Handari, dan Fevi Novkaniza – Universitas Indonesia …MS 68-76

viii

MODEL PENYEBARAN PENYAKIT SARS DENGAN PENGARUH VAKSINASI Putri Efelin, Benny Yong, dan Livia Owen – Universitas Katolik Parahyangan

...MS 77-85

STABLE AGE DISTRIBUTION PADA MODEL BACK-CROSSING PERSILANGAN TERNAK LOKAL DAN TERNAK EKSOTIS A. U. Raihan, A. K. Supriatna, dan N. Anggriani – Universitas Padjadjaran

...MS 86-92

MODEL PERSEDIAAN P(R,T) MULTI ITEM DENGAN DISTRIBUSI PERMINTAAN UMUM Handi Koswara dan J. Dharma Lesmono – Universitas Katolik Parahyangan

...MS 93-99

DISTRIBUSI EXPONENTIATED EXPONENTIAL Ridho Okta Pawarestu, Siti Nurrohmah, dan Ida Fithriani – Universitas Indonesia

...MS 100-106

PENENTUAN JARAK MINIMUM DALAM SUATU JARINGAN DENGAN ALGORITMA PRIM DAN PEMROGRAMAN BILANGAN BINER Robby Hardiwinata dan J. Dharma Lesmono – Universitas Katolik Parahyangan

…MS 107-113

ALGORITMA SWEEP DAN ELITE ANT SYSTEM UNTUK MENYELESAIKAN MULTIPLE TRAVELING SALESMAN PROBLEM (MTSP) Karina, Gatot F. Hertono, dan Bevina D. Handari – Universitas Indonesia

…MS 114-119

PENAKSIRAN PARAMETER SKALA DARI DISTRIBUSI NAKAGAMI MENGGUNAKAN METODE BAYES Siti Nur Noviyani Witayati, Ida Fithriani, dan Siti Nurrohmah – Universitas Indonesia

...MS 120-127

ix

PENENTUAN JARAK MINIMUM DALAM SUATU JARINGAN DENGAN ALGORITMA PRIM DAN PEMROGRAMAN BILANGAN BINER Robby Hardiwinata1 dan J. Dharma Lesmono2 1,2

Jurusan Matematika Universitas Katolik Parahyangan email : [email protected], [email protected]

Abstrak. Penelitian Operasional yang dimulai sejak revolusi industri merupakan bagian dari aplikasi matematika untuk memecahkan masalah optimasi. Pemrograman Linear merupakan salah satu model Penelitian Operasional yang berkembang dan dapat digunakan untuk menganalisis suatu jaringan seperti jaringan transportasi, listrik, air dan telekomunikasi. Dalam makalah ini akan dibahas Algoritma Prim dan Pemrograman Bilangan Biner, yang berkaitan dengan Pemrograman Linear, untuk mencari suatu jaringan atau pohon rentang minimum pada masalah pendistribusian listrik di Rumania. Pohon Rentang Minimum merupakan variasi dari persoalan pencarian jarak terpendek. Pada pohon rentang minimum akan ditentukan sisi-sisi yang menghubungkan masing-masing simpul yang ada pada jaringan sehingga diperoleh panjang sisi total yang minimum. Baik Algorimta Prim ataupun Pemrograman Bilangan Biner menghasilkan pohon rentang minimum yang sama tetapi terdapat perbedaan dalam waktu pencarian solusi dengan menggunakan Matlab. Algoritma Prim membutuhkan waktu lebih cepat yakni selama 0,002393 detik sedangkan Pemrograman Bilangan Biner selama 0,013275 detik. Hal ini terjadi karena langah-langkah pencarian solusi optimal dari Algoritma Prim relatif lebih sederhana dibandingkan Pemrograman Bilangan Biner. . Kata kunci : Pohon rentang minimum, Algoritma Prim, Pemrograman Bilangan Biner.

1. PENDAHULUAN Penelitian Operasional yang dimulai sejak revolusi industri merupakan bagian dari aplikasi matematika untuk memecahkan masalah optimasi. Penelitian Operasional sering dikaitkan secara eksklusif dengan penggunaan teknik-teknik matematika untuk memodelkan dan menganalisis masalah-masalah pengambilan keputusan. Disamping teknik-teknik itu, masalah pengambilan keputusan juga mencakup faktor-faktor penting lainnya yang tidak dapat diterjemahkan secara langsung ke dalam model-model matematika. Faktor-faktor itu adalah adanya unsur manusia di dalam setiap pengambilan keputusan.[4] Keberhasilan suatu teknik pada Penelitian Operasional diukur dari penggunaan teknik tersebut sebagai suatu alat pengambil keputusan untuk solusi yang optimal. Sejak diperkenalkan pada akhir tahun 1940, Pemrograman Linear telah terbukti sebagai salah satu alat Penelitian Operasional yang paling efektif. Pemrograman Linear merupakan model dari Penelitian Operasional yang dapat digunakan untuk menganalisis suatu jaringan seperti jaringan transportasi, listrik, air ataupun jaringan telekomunikasi yang sering kita jumpai sehari-hari.[3] Makalah ini akan membahas mengenai aplikasi dari Pemrograman Linear, dalam hal ini adalah Algoritma Prim dan Pemrograman Bilangan Biner untuk pohon rentang minimum pada masalah pendistribusian listrik di Rumania.

MS - 107

2. LANDASAN TEORI 2.1 Teori Graf Graf didefinisikan sebagai: G = (V,E), dimana V merupakan himpunan tidak kosong dari setiap simpul pada himpunan {v1, v2,…,vn} dan E adalah himpunan sisi yang menghubungkan sepasang simpul di himpunan { e1, e2,…, en}. Beberapa terminologi dasar dalam graf yang perlu diketahui adalah sebagai berikut: 1. Graf berbobot adalah graf yang setiap sisinya diberi sebuah bobot. 2. Bertetangga artinya dua buah simpul pada graf tidak berarah jika keduanya terhubung dengan sebuah sisi. Dapat dikatakan, jika v1 dan v2 bertetangga, maka haruslah terdapat sisi (v1, v2). 3. Bersisian artinya untuk sebarang sisi e = (v1, v2), sisi e dikatakan bersisian dengan titik v1 dan titik v2. 4. Siklus artinya lintasan yang simpul awal dan simpul akhirnya sama. 5. Pohon adalah graf terhubung dengan n - 1 sisi dan n simpul. 2.2 Pohon Rentang Minimum Jika G adalah graf berbobot, maka bobot dari pohon rentang T dari G didefinisikan sebagai jumlah bobot pada semua sisi di T. Pohon rentang yang berbeda memiliki bobot yang berbeda pula. Di antara semua pohon rentang di G, pohon yang memiliki bobot paling minimum dinamakan pohon rentang minimum. Persoalan pohon rentang minimum menyangkut pemilihan seperangkat penghubung yang menghubungkan semua simpul dalam suatu jaringan sedemikian rupa sehingga menghasilkan jumlah panjang yang minimum dari semua penghubung terpilih.[5] 2.3 Pemrograman Linear Pemrograman Linear merupakan suatu model umum yang dapat digunakan dalam pemecahan masalah pengalokasian sumber-sumber yang terbatas secara optimal. Masalah tersebut timbul apabila seseorang diharuskan untuk memilih atau menentukan tingkat setiap kegiatan yang akan dilakukannya, dimana masing-masing kegiatan membutuhkan sumber yang sama sedangkan jumlahnya terbatas.[4] Terdapat tiga komponen dasar di dalam model Pemrograman Linear yaitu:  Variabel keputusan yang ingin ditentukan model.  Kendala-kendala yang harus dipenuhi oleh solusi dari model tersebut.  Tujuan yang ingin dioptimalkan (maksimasi atau minimasi). Secara umum model Pemrograman Linear diformulasikan sebagai berikut: Fungsi Objektif: Maks / Min Z = ∑𝑛𝑗=1 𝐶 jXj dengan kendala: ∑𝑛𝑗=1 𝑎ijXj ≤ bi, i = 1,2,…,m Xj ≥ 0, j = 1,2,..,n Z : nilai dari fungsi objektif Xj : tingkat aktifitas ke-j Cj : koefisien di Z yang menyatakan jumlah penggunaan tingkat aktifitas ke-j aij : jumlah sumber daya ke-i yang digunakan tiap unit aktifitas ke-j bi : jumlah sumber daya ke-i yang tersedia untuk dialokasikan

3. ALGORITMA PRIM 3.1 Algoritma Prim Konsep pohon merupakan konsep penting karena konsep ini mampu mendukung penerapan graf dalam berbagai bidang ilmu. Aplikasi yang menggunakan konsep Pohon diantaranya adalah pembangunan jalan dan rel kereta api, pembuatan jaringan komputer, pencarian jalur untuk MS - 108

penjual keliling, dan sebagainya. Salah satu metode untuk mencari pohon rentang minimum dalam masalah jaringan yang ditemukan oleh Robert C. Prim. Algoritma Prim membentuk pohon rentang minimum dengan langkah per langkah. Pada setiap langkah kita mengambil sisi graf G yang memiliki jarak minimum namun yang terhubung dengan pohon rentang T yang telah terbentuk.[2] Misalkan G adalah graf berlabel dengan n simpul dan T adalah pohon rentang minimum yang akan dibentuk (mula-mula kosong). Langkah-langkah Algoritma Prim adalah sebagai berikut:[5]  Inisialisasi: Mula-mula T adalah graf kosong  Ambil sembarang v ϵ V (G). Masukkan v ke dalam V (T).  V (G) = V (G) - v.  Untuk itu pilih i = 1, 2, …, n - 1: (1) Pilihlah sisi e ∈ E(G) dan e ∉ E(T) dengan syarat: (a) e berhubungan dengan satu simpul di T. (b) mempunyai bobot (jarak) terkecil dibandingkan dengan semua sisi yang berhubungan dengan tiap simpul dalam T. Misalkan w adalah simpul ujung e yang tidak berada dalam T. (2) Tambahkan e ke E(T) dan w ke V (T) (3) V (G) = V (G) - w 3.2 Menentukan Jarak Minimum dengan Algoritma Prim Akan dicari pohon rentang minimum dengan menggunakan Algoritma Prim untuk graf G pada Gambar 1.

Gambar 1. Graf G Solusi permasalahan gambar 1 sebagai berikut:  Misalkan G adalah graf mula-mula seperti yang tampak pada gambar di atas dan T adalah pohon rentang minimum yang akan dibuat.  Tentukan simpul awal pertama (bebas), misalkan simpul A. V (T) = {A} dan E(T) = {}  Pilih jarak minimal suatu simpul yang terhubung dengan simpul A. Simpul B memiliki jarak 3 terhadap simpul A, simpul C memiliki jarak 7 dari simpul A, sehingga simpul B dipilih karena memiliki jarak minimal dari simpul A dibandingkan dari simpul B. Pemilihan simpul B akan menghasilkan sisi A - B. V (T) = {A, B} dan E(T) ={AB}.  Pilih jarak minimal suatu simpul yang terhubung dengan simpul A atau simpul . Simpul C dan D masing-masing memiliki jarak 7 dan 6 dari simpul A, sedangkan simpul B terhubung dengan simpul D yang berjarak 5. Sehingga dipilih simpul B yang terhubung dengan simpul D yang menghasilkan sisi A - B - D. V (T) = {A, B,D} dan E(T) ={AB, BD}.  Pilih jarak minimal suatu simpul yang terhubung dengan simpul A atau simpul D. Simpul C berjarak 7 dari simpul A dan berjarak 8 dari simpul D, sehingga dipilih sisi A-C, yang akhirnya menghasilkan sisi A - B - D, A - C. V (T) = {A, B, D, C} dan E(T) ={AB, BD, AC}. Karena masing-masing simpul telah terhubung dan tidak ada siklus maka diperoleh pohon rentang minimum yaitu sisi A-B, B-D, dan A-C. MS - 109

4. PEMROGRAMAN BILANGAN BINER 4.1 Pemrograman Bilangan Biner Pemrograman Bilangan Biner merupakan hal khusus dari Pemrograman Bilangan Bulat dan Pemrograman Linear, dimana solusi dari variabel-variabel keputusan dari suatu permasalahan haruslah bernilai nol atau satu. Secara umum, Pemrograman Linear terdiri dari tiga unsur utama yaitu variabel keputusan, fungsi objektif dan fungsi kendala. Dalam Pemrograman Bilangan Bulat semua variabel haruslah berupa bilangan bulat. Bentuk umum dari Pemrograman Bilangan Bulat dan Pemrograman Bilangan Biner adalah sebagai berikut:[1] Fungsi Objektif: Maks/Min Z = ∑𝑛𝑗=1 𝐶 jXj , Kendala:

Fungsi Objektif:

Kendala:

∑𝑛𝑗=1 𝑎ijXj ≤ bi, i = 1,2,…,m Xj ≥ 0, j = 1,2,..,n Xj ∈ ℤ Maks/Min Z = ∑𝑛𝑗=1 𝐶 jXj , ∑𝑛𝑗=1 𝑎ijXj ≤ bi, i = 1,2,…,m Xj = 0 atau Xj = 1

Untuk mencari solusi dari Pemrograman Bilangan Bulat dapat digunakan metode simpleks dengan melakukan pembulatan pada solusi optimalnya, sedangkan untuk Pemrograman Bilangan Biner, metode yang sering digunakan adalah metode branch and bound.[1] 4.2 Metode Branch and Bound Pencarian solusi optimal dari suatu masalah dengan metode branch and bound melibatkan tiga buah proses yaitu bounding, fathoming, dan branching. Pada tahap bounding dibangun semua cabang pohon yang mungkin menuju solusi. Dalam permasalahan pencarian rute terpendek pada setiap langkah terdapat 2 kemungkinan yang dapat diambil, yaitu 0 jika pilihan tidak diambil atau 1 jika pilihan tersebut diambil. Sehingga total langkah yang bisa diambil sebanyak 2n, dimana n merupakan jumlah simpul. Proses kedua adalah fathoming yang merupakan tahap pendugaan. Pada tahap ini akan dilakukan evaluasi terhadap masing-masing hasil pada tahap branching secara sistematis. Tahap ini merupakan tahap iterasi, sehingga bisa saja diperoleh solusi sementara. Iterasi dilakukan sampai solusi optimum ditemukan. Proses ketiga yaitu branching akan menentukan simpul mana yang dapat dilakukan percabangan dan simpul mana yang tidak dapat dilakukan percabangan dengan menggunakan syarat batas dari kendala.[4] 4.3 Penyelesaian Model Linear dengan Pemrograman Bilangan Biner Contoh berikut merupakan permasalahan alokasi biaya (dalam $) pada perusahaan Star Oil. Dengan memperhatikan kondisi keuangan, perusahaan ingin menentukan pilihan terhadap 4 jenis investasi yang ada. Investasi pertama, kedua, ketiga dan keempat masing-masing akan memberikan hasil sebesar 16.000, 22.000, 12.000, dan 8.000. Biaya yang harus dikeluarkan perusahaan untuk investasi pertama, kedua, ketiga dan keempat masing-masing adalah sebesar 5.000, 7.000, investasi 4.000 dan 3.000. Besarnya dana yang dimiliki perusahaan untuk

MS - 110

membiayai keempat investasi tersebut adalah 14.000. Perusahaan ingin menentukan investasi mana yang sebaiknya dipilih dengan mempertimbangkan kesediaan dana. [4] Masalah di atas dapat dimodelkan ke dalam Pemrograman Bilangan Biner sebagai berikut: Maks Z = 16X1 + 22X2 + 12X3 + 8X4 (dalam ribuan) dengan kendala 5X1 + 7X2 + 4X3 + 3X4 ≤ 14 Xj = 0 atau Xj = 1 j =1,2,3,4 Berdasarkan konsep dari branching, fathoming, dan bounding diperoleh solusi optimal sebesar 42 (Z = 42) dengan X1 = 0 dan X2 = X3 = X4 = 1, sehingga dapat disimpulkan bahwa perusahaan harus mengambil pilihan investasi kedua, ketiga, dan keempat.

5. MENENTUKAN JARAK MINIMUM DENGAN ALGORITMA PRIM DAN PEMROGRAMAN BILANGAN BINER 5.1 Menentukan Jarak Minimum dengan Algoritma Prim Pemerintah Rumania menginginkan akses distribusi jaringan listrik yang ada di wilayah tertentu melakukan penghematan. Perusahaan terkemuka yang bergerak di bidang kelistrikan di negara tersebut mencoba memenuhi permintaan pemerintah. Perusahaan tersebut membuat sebuah perencanaan baru dengan mencoba mengurangi jaringan yang terhubung tanpa mengganggu kegiatan masyarakat di daerah yang terkait.[1]. Jaringan yang terbentuk diberikan seperti gambar di bawah ini:

Gambar 2. Representasi dari peta Rumania (Matlab) Misal tersebut diberikan X1 = jarak Arad - Zerind , X2 = jarak Arad - Timisoara, X3 = jarak Zerind - Oradea, X4 = jarak Timisoara - Lugoj, X5 = jarak Orade - Sibiru, X6 = jarak Lugoj Mehadea, X7 = jarak Mehadea - Dobreta, X8 = jarak Dobreta - Rimmicu, X9 = jarak Rimmicu Sibiru, X10 = jarak Rimmicu - Craiova, X11 = jarak Rimmicu - Pitesti, X12 = jarak Craiova Pitesti, X13 = jarak Sibiru - Fragaras, X14 = jarak Pitesti - Bucharest, X15 = jarak Fragaras Bucharest , X16 = jarak Arad - Sibiru. Masing-masing panjang jaraknya yakni: X1 = 75km, X2 = 118km, X3 = 71km, X4 = 111km, X5 = 151km, X6 = 70km, X7 = 75km, X8 = 120km, X9 = 80km, X10 = 146km, X11 = 97km, X12 = 138km, X13 = 99km, X14 = 101km, X15 = 211km, X16 = 140km.

MS - 111

Penerapan Algoritma Prim dengan bantuan Matlab untuk masalah di atas menghasilkan gambar sebagai berikut:

Gambar 3. Pohon Rentang Minimum dengan Algoritma Prim Dari hasil di Gambar 3 diperoleh bahwa perusahaan listrik tersebut dapat memangkas total jarak pada permasalahan pendistribusian listrik pada daerah yang dituju sebesar 648 km (dari 1803 km menjadi 1155 km). 5.2 Menentukan Jarak Minimum dengan Pemrograman Bilangan Biner Dalam subbab ini akan dibahas aplikasi dari Pemrograman Bilangan Biner untuk menyelesaikan masalah pemdistribusian listrik di Rumania seperti pada subbab 5.1. Pada gambar 2 terdapat 4 bagian ruang yang terbentuk yaitu daerah I,II,III, dan IV. Pemrograman Bilangan Biner bertujuan mereduksi jumlah sisi pada masing-masing bagian ruang tersebut yang akan berakibat pada reduksi total jarak. Permasalahan di atas dapat dimodelkan menjadi: Min Z = 75X1 + 118X2 + 71X3 + 111X4 + 151X5 + 70X6 + 75X7 + 120X8 + 80X9 + 146X10 + 97X11 + 138X12 + 99X13 + 101X14 + 211X15 + 140X16 dengan kendala X1 + X3 + X5 + X16 ≤ 3 X2 + X4 + X6 + X7 + X8 + X9 + X16 ≤ 6 X10 + X11 + X12 ≤ 2 X9 + X11 + X13 + X14 + X15 ≤ 4 Xj = 0 atau Xj = 1 j =1,2,…,16 Dengan bantuan Matlab diperoleh gambar seperti di bawah ini:

Gambar 4. Pohon Rentang Minimum dengan Pemrograman Bilangan Biner Terlihat bahwa Pemrograman Bilangan Biner menghasilkan pohon rentang minimum yang sama dengan Algoritma Prim, sehingga diperoleh total jarak yang sama yakni 1155 km. Tetapi terdapat perbedaan di dalam waktu pencarian solusi optimal dengan menggunakan Matlab. MS - 112

Algoritma Prim membutuhkan waktu selama 0,002393 detik untuk memperoleh solusi optimal sedangkan Pemrograman Bilangan Biner memerlukan waktu selama 0,013275 detik. Hal ini disebabkan langkah-langkan pencarian solusi pada Algoritma Prim relatif lebih sederhana dibandingkan Pemrograman Bilangan Biner.

6. KESIMPULAN Dari pembahasan pada makalah ini, diperoleh beberapa kesimpulan sebagai berikut: 1. Pemrograman Bilangan Biner dapat digunakan untuk menyelesaikan masalah Pemrograman Linear untuk kasus pendistribusian listrik di Rumania. 2. Algoritma Prim dapat menghasilkan jarak minimum (1155 km) pada jaringan pendistribusian listrik di Rumania dengan waktu pencarian solusi optimal selama 0,002393 detik dengan bantuan Matlab. 3. Pemrograman Bilangan Biner dapat menghasilkan jarak minimum (1155 km) pada jaringan pendistribusian listrik di Rumania. Waktu yang dibutuhkan untuk memperoleh solusi optimal dengan bantuan Matlab adalah 0,013275 detik. Algoritma Prim dan Pemrograman Bilangan Biner efektif untuk menyelesaikan permasalahan jaringan dengan hasil akhir berupa pohon rentang minimum. Dalam kasus jaringan listrik atau jaringan lainnya kedua metode ini dapat digunakan sebagai salah satu perencanaan yang baik karena dapat mereduksi biaya. Algoritma Prim maupun Pemrograman Bilangan Biner dapat menjadi rujukan bagi organisasi/perusahaan dalam hal pemetaan sebuah jaringan yang akan dibangun/dibentuk.

DAFTAR PUSTAKA [1]. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., and Stein, Clifford. (2009). An Introduction to Algorithms, MIT Press and McGraw-Hill, Massachusetts. [2]. Prim, R.C. (1957). Shortest connection networks and some generalisations, Bell System Technical Journal vol. 36, pp 1389-1401. [3]. Arogundade, O.T., Sobowale, B., Akinwale, A.T. (2011). Prim Algorithm Approach to Improving Local Acces Network in Rural Areas, International Journal of Computer Theory and Engineering 11, vol.3, pp 413-417. [4]. Taha, Hamdy A. (2011). Operations Research An Introduction, Ninth Edition, Pearson International, London. [5]. Siang, Jong Jek. (2014). Riset Operasi dalam pendekatan Algoritmis, edisi kedua, Penerbit ANDI, Yogyakarta.

MS - 113

I SSN 1907 - 3909

9 771907 390914

Alamat Redaksi: Jurusan Matematika, FTIS - UNPAR Gedung 9, Lantai 1 Jl. Ciumbuleuit No. 94, Bandung - 40141

PROSIDING SEMINAR NASIONAL MATEMATIKA 2016