Penerapan Matching pada Graf untuk Pendistribusian Pupuk Bersubsidi dengan Metode Hungarian
Eva Wahyu Listyawati 1 , Siti Amiroch 2 , Novita Eka Chandra 3
1 Universitas Islam Darul ‘ulum, evawahyulistyawati@gmail.com
2 Universitas Islam Darul ‘ulum Lamongan, siti.amiroch@unisda.ac.id
3 Universitas Islam Darul ‘ulum Lamongan, novitaeka@unisda.ac.id
Abstract.  Increasing  yields,  demanding  each  farmer  to  improve  the  quality  of agriculture, which in turn is expected to increase profits. The purpose of this paper is to determine the allocation of subsidized fertilizer distribution by the distributor of PT. Anak Gresik Raya Kencana and looking for the maximum number of subsidized fertilizer  needs  distributed  in  Lamongan  district  each  year  so  that  there  is  no scarcity  and  HET  (Highest  Retail  Price)  does  not  increase  by  applying  the hungarian  method.  In  this  case,  the  problem  is  expressed  as  a  bipartite  graph, especially a complete weighted bipartite graph that applies the concept of matching, which  is  a  perfect  matching  search  with  maximum  weight  using  the  Hungarian method. Matching is said to be perfect if it has fulfilled all the sets of vertices X and Y.  Obtained  the  results  of  the  allocation  of  subsidized  fertilizer  distribution  by  the distributor  of  PT.  Anak  Gresik  Raya  Kencana  is  Deket  sub-district  requiring  1220 tons  of  SP-36,  Glagah  sub-district  requires  3208  tons  of  Urea,  Karangbinangun sub-district requires 483 tons of Organic, mantup sub-district requires 2079 tons of ZA,  middle  district  needs  2233  tons  of  NPK  and  fertilizer  distribution  problems subsidized  in  Lamongan  district  can  be  completed  with  the  maximum  amount  of subsidized fertilizer needs distributed as many as 9223 tons every year
Keywords: Matching on the Graph, Subsidized Fertilizer, Hungarian Method.
Abstrak. Semakin  meningkatnya  hasil  panen,  menuntut  setiap  petani  untuk meningkatkan  kualitas  pertaniannya  yang  pada  akhirnya  diharapkan  dapat meningkatkan  keuntungan.  Tujuan  penulisan  ini  untuk  menentukan  alokasi pendistribusian  pupuk  bersubsidi  oleh  distributor  PT.  Anak  Gresik  Raya  Kencana dan  mencari  jumlah  maksimum  kebutuhan  pupuk  bersubsidi  yang  didistribusi  di Kabupaten  Lamongan  tiap  tahunnya  sehingga  tidak  terjadi  kelangkaan  dan  HET (Harga  Eceran  Tertinggi)  tidak  mengalami  kenaikan  dengan  menerapkan  metode hungarian. Dalam hal ini, permasalahan dinyatakan sebagai graf bipartit khususnya graf  bipartit  lengkap  berbobot  yang  menerapkan  konsep matching, yaitu  pencarian perfect matching dengan  bobot  maksimum  menggunakan  metode  Hungarian. Matching dikatakan sempurna jika telah memenuhi semua himpunan simpul X dan Y. Diperoleh  hasil  alokasi  pendistribusian  pupuk  bersubsidi  oleh  distributor  PT.  Anak Gresik Raya Kencana adalah kecamatan Deket membutuhkan SP-36 sebanyak 1220 ton,  Kecamatan  Glagah  membutuhkan  Urea  sebanyak  3208  ton,  Kecamatan Karangbinangun  membutuhkan  Organik  sebanyak  483  ton,  Kecamatan  Mantup membutuhkan  ZA  sebanyak  2079  ton,  Kecamatan  Kalitengah  membutuhkan  NPK sebanyak  2233  ton  dan  masalah  pendistribusian  pupuk  bersubsidi  di  Kabupaten Lamongan  dapat  diselesaikan  dengan  jumlah  maksimum  kebutuhan  pupuk bersubsidi yang didistribusikan sebanyak 9223 ton tiap tahun.
Kata Kunci: Matching pada Graf, Pupuk Bersubsidi, Metode Hungarian.

## 1  Pendahuluan
Kabupaten  Lamongan  merupakan  kabupaten  di  wilayah  Jawa  Timur  yang memiliki luas wilayah 181.280 Ha. Lahan di kabupaten ini didominasi oleh sektor pertanian  dan  mayoritas  penduduk  berprofesi  sebagai  petani.  Sebanyak  12 kecamatan memiliki potensi pertanian terbesar di kabupaten Lamongan [1]. Lebih lanjut,  [2]  mengatakan  sektor  pertanian  di  kabupaten  Lamongan  perlu  mendapat perhatian lebih guna meningkatkan nilai tukar petani yang cenderung menurun.
Selain  itu,  dalam  sektor  pertanian  kabupaten  Lamongan,  pupuk  merupakan salah satu unsur yang sangat berpengaruh terhadap hasil panen, khususnya pupuk bersubsidi. Pupuk bersubsidi didapatkan dari gudang penyedia pupuk yang ada di daerah  tersebut.  Di  sisi  lain,  ketersediaan  pupuk  di  gudang  harus  sesuai  dengan jumlah  kebutuhan  petani  agar  tidak  terjadi  penimbunan  atau  kekurangan  akan ketersediaan pupuk tersebut.
Untuk  mengatasi  hal  tersebut  diperlukan  suatu  metode  hungarian  dengan mencari perfect  matching dengan  bobot  maksimal.  Metode  Hungarian  adalah metode  penugasan  yang  berkaitan  dengan  keinginan  perusahaan  dalam mendapatkan  alokasi  tugas  yang  optimal.  Pada  dasarnya  pencarian perfect matching dengan  bobot  maksimal  dapat  dilakukan  dengan  mendaftar  semua perfect matching yang  berbeda  dan  menghitung  jumlah  bobot  dari  setiap perfect matching yang diperoleh.
Penelitian  sebelumnya  dilakukan  oleh  [3],  menyimpulkan  bahwa  dengan menggunakan  metode  Hungarian  terdapat  efisiensi  waktu  dalam  menyelesaikan masalah  penugasan.  Dalam  hal  penentuan  matching,  [4]  mengatakan  bahwa matching  tersebut  merupakan  perfect  matching  dengan  kardinalitas  dan  jumlah bobot  sisi  yang  maksimum  pada  graf  bipartit  berbobot.  Lebih  lanjut,  metode Hungarian dapat membantu perusahaan atau institusi dalam mengambil keputusan. Pada  penelitian  ini  akan  dibahas  metode  hungarian  untuk  menyelesaikan matching pada  graf  bipartit  lengkap  berbobot  dengan  masalah  yang  akan dipecahkan adalah mencari solusi pendistribusian pupuk.

## 2 Metode Penelitian
Penelitian tentang penerapan metode Hungarian  dalam penyelesaian matching pada  graf  untuk  pendistribusian  pupuk  bersubsidi  di  Kabupaten  Lamongan merupakan penelitian yang bersifat studi literatur dengan mempelajari materi yang berkaitan  dengan  buku,  jurnal  dan  karya  ilmiah  lainnya.  Penelitian  ini  dimulai dengan pengumpulan data dan data yang digunakan adalah data sekunder tentang laporan pendistribusian dan kebutuhan pupuk bersubsidi di Kabupaten Lamongan yang  diperoleh  dari  Dinas  Pertanian  Kabupaten  Lamongan.  Tahap  selanjutnya yaitu menentukan variabel X (mewakili kecamatan di Kabupaten Lamongan) dan Y (jenis  pupuk  bersubsidi).  Dimana  variabel X terdiri  dari adalah  Kecamatan Deket; adalah  Kecamatan  Glagah; adalah  Kecamatan  Karangbinangun; adalah  Kecamatan  Mantup;  dan adalah  Kecamatan  Kalitengah.  Sedangkan variabel Y terdiri  dari adalah  pupuk  Urea; adalah  pupuk  SP-36; adalah pupuk  ZA; adalah  pupuk  NPK;  dan adalah  pupuk  Organik.  Selanjutnya, membentuk  matriks  dari  data  pendistribusian  pupuk  tersebut  dan  tahap  terakhir adalah melakukan perhitungan dengan metode Hungarian.

## 3 Hasil dan Pembahasan
Penelitian  tentang  alokasi  pendistribusian  pupuk  bersubsidi  dapat  dilakukan dengan menentukan variabel X dan variabel Y dari suatu data, membentuk sebuah matriks  kemudian mengolah matriks  tersebut  dengan metode Hungarian. Berikut bentuk matriksnya sebagai berikut :
Setelah  matriks  terbentu,  dilakukan  pelabelan  simpul  ℓ  dan  dibentuk equality subgraph . Diperoleh feasible  labelling yang  diilustrasikan  pada  matriks berikut:
Sehingga diperoleh pelabelan simpul  :
dan digambarkan menjadi
Gambar 1. Equality Subgraph
Selanjutnya, dipilih sebarang matching M

## Gambar 2. Matching M
Matching  M pada  Gambar  2  bukan matching sempurna,  pilih  sebarang yang unsaturated di M. Didapatkan simpul , sehingga didefinisikan
dan . Simpul yang adjancent dengan simpul di S adalah , maka .  Karena ,  maka  pilih .  Diperoleh , karena matched di matching M dengan dan ,  maka  akan  dibentuk  lintasan M-alternating dengan menambahkan dan .
Gambar 3. (a)  Lintasan M-alternating berawal dari simpul  ; (b) Lintasan M- alternating berawal dari simpul  ; (c) Lintasan M-alternating berawal dari simpul dan dan .  Karena , maka hitung . Diperoleh pada ( ). Kurangi elemen pada label dengan  1160  dan  tambahkan  elemen-elemen  label dengan 1160.
Diperoleh pelabelan simpul   : = (1160, 0, 0, 1160, 0) = (1325, 2003, 1668, 2079, 2347)
Gambar 4. Equality Subgraph dan Matching M , dan .Karena ,  maka  pilih . ,  karena unmatched di matching  M, maka  terdapat P yang  merupakan  lintasan M- augmenting , yaitu :
Gambar 5. Lintasan M-augmenting
Selanjutnya, mengubah M dengan , sehingga
Matching bukan matching sempurna,  maka  pilih  sebarang yang unsaturated di .  Diperoleh  simpul sehingga  didefinisikan dan . Gambar 6. Equality Subgraph dan Matching , dan .  Karena ,  maka  pilih .  Diperoleh ,  karena matched di matching
, maka bentuk lintasan
M-alternating dengan menambahkan dan .  Lintasan M- alternating yang dibentuk sama dengan Lintasan M-alternating pada Gambar 3.
, dan .  Karena ,  maka hitung . Diperoleh
pada ( ). Pelabelan simpul baru = (1310, 0, 0, 1160, 0) = (1220, 1898, 1563, 2079, 2242)
Gambar 7. Equality Subgraph dan Matching , dan .  Karena , maka  pilih . .  Karena unmatched pada matching , maka  bentuk  lintasan M-augmenting , yaitu  :
.
Gambar 8. Lintasan M-augmenting
Ganti dengan ,
Matching bukan matching sempurna
Ulangi  langkah  di  atas  hingga  26  langkah  sampai  diperoleh matching sempurna, yaitu :
Dengan  begitu,  diperoleh  nilai  solusi  optimal  dengan  menjumlahkan  semua  nilai feasible labelling pada equality subgraph , yaitu :
Jadi  pendistribusian  pupuk  bersubsidi  pada  5  kecamatan  di  Lamongan  sebagai berikut :
Gambar 9. Matching sebagai solusi masalah  pendistribusian pupuk bersubsidi
Berdasarkan hasil matching pada Gambar 9, maka alokasi pendistribusian pupuk bersubsidi  yang  sebaiknya  dilakukan  oleh  distributor  PT.  Anak  Gresik  Raya Kencana adalah:
a. Kecamatan  Deket  ( )  membutuhkan  pupuk  bersubsidi  SP-36  ( ) dengan jumlah pupuk yang dibutuhkan sebanyak 1220 ton.
b. Kecamatan  Glagah  ( )  membutuhkan  pupuk  bersubsidi  Urea  ( ) dengan jumlah pupuk yang dibutuhkan sebanyak 3208 ton.
c. Kecamatan  Karangbinangun  ( )  membutuhkan  pupuk  bersubsidi Organik ( ) dengan jumlah pupuk yang dibutuhkan sebanyak 483 ton.
d. Kecamatan Mantup ( ) membutuhkan pupuk bersubsidi ZA ( ) dengan jumlah pupuk yang dibutuhkan sebanyak 2079 ton.
e. Kecamatan  Kalitengah  ( )  membutuhkan  pupuk  bersubsidi  NPK  ( ) dengan jumlah pupuk yang dibutuhkan sebanyak 2233 ton.

## 4  Kesimpulan
Dari hasil dan pembahasan yang dilakukan, disimpulkan bahwa dengan metode Hungarian,  masalah  pendistribusian  pupuk  bersubsidi  di  Kabupaten  Lamongan dapat  diselesaikan  dengan  jumlah  maksimum  kebutuhan  pupuk  bersubsidi  yang didistribusikan sebanyak 9223 ton tiap tahun.

## 5  Daftar Pustaka
[1] A.  Rohmatullah,  D.  Rahmalia,  and  M.  S.  Pradana,  “Klasterisasi  Data Pertanian di Kabupaten Lamongan Menggunakan Algoritma K-Means Dan
Fuzzy C Means,” J. Ilm. Teknosains , vol. 5, no. 2, pp. 86–93, 2019.
[2] M.  S.  Pradana,  D.  Rahmalia,  and  E.  D.  A.  Prahastini,  “Peramalan  Nilai Tukar Petani Kabupaten Lamongan dengan Arima,” J. Mat. , vol. 10, no. 2, pp. 91–104, 2020.
[3] D.  Harini,  “Optimasi  Penugasan  Menggunakan  Metode  Hungarian,” INTENSIF J. Ilm. Penelit. dan Penerapan Teknol. Sist. Inf. , vol. 1, no. 2, pp. 68–74, 2017.
[4] M.  Abrori  and  R.  Wahyuningsih,  “Penentuan  Matching  Maksimum  Pada Graf Bipartit Berbobot Menggunakan Metode Hungarian,” J. Ilm. Tek. Ind. , vol. 11, no. 1, pp. 9–21, 2012.