BAB I PENDAHULUAN
1.1 Latar belakang
Peranan matematika dalam menyelesaikan masalah
di dunia nyata sudah tidak di ragukan lagi.
Dengan matematika diharapkan
akan diperoleh solusi
akhir yang tepat, valid dan dapat diterima secara ilmiah.
Salah satu bidang ilmu yang dikembangkan dalam
mendapatkan solusi yang optimum adalah
Riset Operasi. Riset
operasi adalah sebuah
kajian dalam menetapkan tugas-tugas pada berbagai fasilitas
dengan korespondensi satu-ke-satu 1 secara
optimal. Sebagai contoh,
permasalahannya mungkin berupa
menentukan penugasan terbaik
atas pekerja dengan
pekerjaannya, pemain olah raga
dengan posisinya dilapangan,
peralatan dengan lokasi konstruksi, dan sebagainya. (Anton, Rorrer. 2004: 152) Salah satu metode yang berkaitan dengan
masalah tersebut adalah Hungaria.
Metode
Hungaria adalah salah
satu algoritma yang
digunakan untuk menyelesaikan
persoalan masalah assignment
(masalah penugasan). versi awalnya,
yang dikenal dengan
Hungaria Metod (Metode Hungaria) yang
di ditemukan dan dipublikasikan
oleh Harold Kuhn pada tahun 1955. Oleh karen itu, algoritma ini kemudian dikenal juga dengan
nama Algoritma Kuhn – Munkers.
Algoritma yang dikembangkan oleh Kuhn ini
berdasarkan pada hasil kerja dua orang
matematikawan asal hungaria
lainnya, yaitu Denes
Konig dan Jeno Egervary. Keberhasilan
Kuhn menggabungkan dua
buah penemuan matematis dari Jeno Egervary menjadi satu bagian
merupakan hal utama menginspirasikan lahirnya
Metode Hungaria. Untuk
dapat menerapkan Metode
Hungaria, Matriks Biayanya
harus berbentuk Bujur
sangkar dan entri-entri
pada matriks biaya
harus merupakan bilangan bulat. Selain itu, setiap sumber
harus ditugaskan hanya untuk satu tugas.
Metode
Hungaria, yang merupakan
metode lima langkah untuk
menerapkan sebuah matriks
biaya dengan entri-entri
tak negatif yang mengandung
sebuah Masalah Penugasan
yang seluruhnya terdiri
dari entri-entri nol.
(Anton, Rorrer.
2004) Masalah penugasan
(Assignment Problems)
merupakan masalah terbesar dalam teori pengambilan keputusan yang
penyelesaiannya cukup kompleks. Salah satu
algoritma yang disarankan untuk digunakan dalam menyelesaikan persoalan ini
adalah algoritma brute
force, di mana
dalam algoritma ini
seluruh kemungkinan solusi
diperhitungkan sebagai kandidat
solusi. Tentu saja
hal ini sangat
menggunakan resource (sumber
daya) yang besar
dan penyelesaian ini menjadi
optimal.
Metode
ini akan penulis
aplikasiakan pada Badan
Pengelola Keuangan Daerah (BPKD) Kabupaten Malang dengan Masalah
Penugasan, dimana masalah yang ingin
dipecahkan adalah mencari
solusi terbaik minimum terhadap
Pajak Galian Golongan C. (Munir,
Renaldi. 2005 : 86).
Untuk
memudahkan persoalan, Tujuannya adalah menugaskan Jenis-jenis galian
golongan C tersebut
ke pajak (satu
jenis galian golongan
C per pajak) dengan biaya total terendah, Misalkan situasi
penugasan mjenis galian golongan C ke npajak. Jenis galian golongan i C (=1, 2, …, m) ketika ditugaskan ke pajak j
(=1, 2, …, n) memerlukan biaya ij C .
Tujuannya adalah menugaskan Jenis-jenis galian golongan
C tersebut ke
pajak (satu jenis
galian golongan C
per pajak) dengan biaya total terendah. Seperti dalam
tabel dibawah ini: Tabel 1. Bentuk
Masalah Penugasan Tujuan
1 2 … n 1 C11
C12 … C1n Sumber 2 C 21
C22 … C2n :
: : : m Cm1
Cm2 … Cmn Perumusan masalah ini dapat
dipandang sebagai kasuskhusus dari model transportasi.
Di sini jenis
galian golongan C
mewakili ”sumber” dan
pajak mewakili ”tujuan”.
Penawaran yang tersedia disetiapsumber adalah 1;yaitu, a =1 untuk
semua i.Demikian pula, permintaan yang diperlukan disetiaptujuan adalah 1;yaitu, j b =1 untuk
semua j. Biaya ”transportasi” (penugasan)
Jenis galian golongan C i ke pajak jadalah ij C . Jika sebuah Jenis galian golongan C
tidak bisa di tugaskan ke pajak tertentu,
nilai c ij yang bersangkutan disamakan
dengan M, biaya yang sangat tinggi. Tabel diatas
memberikan represensi umum dari model penugasan
ini. (Taha, 2006 : 226).
Pajak
merupakan salah satu
kontributor terbesar dari
APBN (Anggaran Pendapatan
Belanja Negara) di
Indonesia, yang mana
perannya sangat berpengaruh
besar terhadap kelangsungan
pembangunan bangsa ini. Dengan diberlakukannya sistem
Otonomi Daerah (OTODA),
biaya pajak dapat
berbeda antar daerah
karena masing-masing daerah
berhak menentukan biaya/pungutan pajak.
Adapun pajak
yang dikelola di
Daerah Tingkat II
(Kabupaten/Kota Madya) antara
lain: Pajak Hotel
dan Restoran, Pajak Hiburan, Pajak
Galian golongan C, Pajak
Penerangan Jalan, Pajak Pengambilan dan Pengolahan Bahan Galian
Golongan C, serta
Pajak Pemanfaatan Air
Bawah Tanah dan
Air Permukaan. Dari
setiap pemungutan pajak
yang dilakukan, maka
akan memberikan pendapatan yang
besar pula sebanding dengan besarnya pajak yang di
kelola. Pajak Galian
Golongan C merupakn
salah satu kontribusi
terhadap APBD (Anggaran
Pendapatan Belanja Daerah), dan menduduki urutan yang keenam dari keseluruhan pendapatan
pemerintah kabupaten Malang, meskipun pajak Galian
Golongan C bukan
satu-satunya pajak, namun
dapat memberikan pemasukan yang besar di tingkat kabupaten.
Seperti halnya di Kabupaten Malang, Berdasarkan hal
inilah penulis mengangkat
masalah “ Analisis Matematika Metode Hungaria Pada Masalah
Penugasan ” pada kantor Badan Pengelola
Keuangan Daerah (BPKD) Kabupaten Malang.
1.2
Rumusan Masalah Berdasarkan latar
belakang diatas, maka
permasalahan dirumuskan sebagai berikut: 1.
Bagaimana Analisis Matematika
Metode Hungaria dalam menentukan solusi yang optimal? 2.
Bagaimana Implementasi Metode
Hungaria bila diterapkan
pada pajak galian golongan C? 1.3
Batasan Masalah Permasalahan yang
ditulis pada skripsi
ini dibatasi pada perhitungan Metode Hungaria yang dilakukan dengan
menggunakan model penugasan dengan mengambil
objek Pajak galian golongan C agar tidak menimbulkan permasalahan yang baru yaitu pajak jenis reklame dan
besarnya pajak dengan Metode Hungaria pada
Masalah Penugasan.Dengan besar
pendapatan daerah Kabupaten Malang tahun 2007-2008.
1.4
Tujuan Penelitian Berdasarkan
latar belakang serta
rumusan masalah tersebut,
maka penelitian ini bertujuan
untuk : 1. Diperoleh
rumusanAnalisis Matematika Metode
Hungaria dalam menentukan solusi yang optimal.
2.
mengimplementasi Metode Hungaria
bila diterapkan pada
pajak galian golongan C.
1.5
Metode Penelitian 1.5. 1
Pendekatan dan Jenis Penelitian Jenis penelitian ini merupakan penelitian
lapangan atau studi kasus pada Badan
Pengelola Keuangan Daerah (BPKD) Kabupaten Malang Tahun 2007-2008 yang bertujuan untuk mengumpulkan data atau
informasi dengan bantuan materi Analisis
Metode Hungaria yang di Aplikasikan pada Masalah penugasan.
BAB II KAJIAN PUSTAKA 2.1
Pengertian Metode Hungarian Metode Hungarian
(Hungarian Method) adalah
salah satu dari
beberapa teknik-teknik pemecahan
yang tersedia untuk
masalah-masalah penugasan.
Metode
Hungarian mula-mula dikembangkan
oleh seorang ahli
matematika berkebangsaan Hungaria
yang bernama D. Konig dalam tahun 1916.
Untuk dapat menerapkan Metode Hungarian,
jumlah sumber-sumber yang ditugaskan
harus sama persis dengan jumlah tujuan yang akan diselesaikan. Selain itu,
setiap sumber harus
ditugaskan hanya untuk
satu tujuan. Jadi,
masalah penugasan akan mencakup
sejumlah nsumber yang mempunyai ntujuan (Taha, 1996: 225-227).
Teorema:
Jika sebuah bilangan
ditambahkan pada atau
dikurangkan pada seluruh entri
dari sebuah baris atau
kolom dalam sebuah
matriks biaya, maka
penugasan optimal untuk
matriks biaya yang dihasilkan adalah
juga penugasan optimal
untuk matriks biaya semula.
Untuk
melihat mengapa berlaku
teorema ini, andaikan bilangan lima ditambahkan pada
tiap entri pada
baris kedua dalam
matriks biaya tertentu.
Karena
setiap penugasan mengandung
tepat satu entri dari
baris kedua, dengan sendirinya
biaya tiap penugasan
pada matriks baru
adalah tepat 5
kali lebih banyak
dibanding dengan biaya
penugasan terkait pada
matriks semula. Maka, 7
penugasan-penugasan yang
saling terkait akan
tetap dengan urutannya
semula dalam kaitannya
dengan biaya, sehingga
penugasan optimal untuk
matriks manapun akan
berhubungan dengan penugasan
optimal untuk matriks
lainnya.
Argumen serupa akan berlaku jika sebuah
bilangan ditambahkan kekolom tertentu di
dalam sebuah matriks biaya, atau
jika proses pengurangan
lebih disukai dari pada
proses penambahan.
Berikut
ini akan diperkenalkan
Metode Hungaria (Hungaria
method).
Yang merupakan prosedur lima langkah untuk
menerapkan teorema di atas pada sebuah matriks
biaya tertentu dan
menghasilkan matriks entri-entri
tak negatif yang mengandung sebuah penugasan yang
seluruhnya terdiri dari entri-entri nol.
0 komentar:
Posting Komentar