## FARABI Jurnal Matematika dan Pendidikan Matematika

## Analisis Penyelesaian Masalah Penugasan Pada Algoritma Matching Graf Bipartit Dan Metode Hungarian
Fajrul Hasnan Sani 1 , Sawaluddin 2
1,2 Program Studi Matematika, FMIPA, Universitas Sumatera Utara, Medan-Indonesia 20155 Email: 1 fajrul.hasnan@gmail.com, 2 sawal@usu.ac.id

## ABSTRAK
Dalam  dunia  industri  dapat  dilihat  bahwa  untuk  menempatkan  karyawan  dalam  menyelesaikan permasalah  tertentu  pada  bidang-bidang  tertentu  diperlukan  penerapan  dari  masalah  penugasan (Assignment  Problem)  agar  diperoleh  hasil  yang  optimal.  Masalah  penugasan  sendiri  merupakan masalah  untuk  memasangkan  tepat  satu  untuk  pekerja  ke  pekerjaan  yang  lain.  Dalam  hal  ini penerapan proses penyelesaian dapat dilakukan menggunakan algoritma matching graf bipartit dan metode  hungarian.  Sehingga  kedua  metode  ini  mempunyai  hubungan  dalam  sebuah  aplikasi masalah penugasan di mana hasil dari kasus penerapan masalah penugasan memiliki solusi optimal yang sama yaitu bernilai 604.
Kata kunci: Graf Bipartit, Masalah Penugasan, Matching, Metode Hungarian, Optimal

## ABSTRACT
In  the  industrial  world,  it  can  be  seen  that  to  place  employees  in  solving  certain  problems  in certain  fields,  it  is  necessary  to  apply  the  assignment  problem  in  order  to obtain  optimal  results. The  assignment  problem  itself  is  a  problem  to  match  exactly  one  worker  to  another  job.  In  this case,  the  application  of  the  solution  process  can  be  done  using  the  bipartit  graph  matching algorithm  and  the  Hungarian  method.  So  that  these  two  methods  have  a  relationship  in  an assignment problem application where the results of the assignment problem application case have the same optimal solution, which is worth 604.
Keywords: Assignment Problem, Bipartit Graph, Hungarian Method, Matching, Optimal

## A. Pendahuluan
Dalam i dunia i bisnis  dan  industri, manajemen i selalu  mengahadapi  pada  masalah yang berkaitan dengan penugasan i optimal i dari i pabrikan ataupun personel yang berbeda dengan tingkat i efisiensi i yang berbeda i dan untuk tugas yang i berbeda-beda.  Untuk  itu  sangat  penting rasanya masalah penugasan ( assignment problem )  dalam  dunia  bisnis  agar  hasil  yang diperoleh  tiap  perusahan  memiliki  hasil  atau kualitas  yang  optimal.  Hal  ini  sangat  penting dalam  penempatan  karyawan  agar  para  pekerja dapat  memanfaatkan  sumber  daya  manusianya sebaik-baiknya  dengan  menempatkannya  pada pekerjaan yang tepat dan berdampak keuntungan  pada  perusahaan.  Penemapatan
karyawan  yang  tidak  sesuai  akan  membuat pemborosan  terhadap  waktu  ataupun  biaya produksi,  sehingga  hal  ini  tidak  mendapatkan hasil  optimal.  Penempatan  awal  task-task  ke dalam  prosessor-prosessor,  di  mana  biaya  dari suatu  tugas  merupakan  fungsi  dari  total  waktu eksekusi  dan  total  waktu  komunikasi  untuk mendapatkan  tugas  yang  optimal  yaitu,  tugas yang diminimalkan fungsi dua biaya Venkateswaran (1993).
Dalam  hal  ini,  bentuk  penyelesaian masalah  penugasan  dapat  dibagi  dalam  dua buah  metode  yaitu, matching graf  bipartit  dan metode  hungarian.  Graf i digunakan i untuk i mengidentifikasi objek i diskrit i untuk memvisualisasikan  masalah  yang  terjadi  agar
dapat  mudah  di  pahami.  Sering  kali  graf digunakan  dalam  kehidupan  sehari-hari  pada sebuah  bentuk  pemodelan  karena  penggunaan graf dapat diselesaikan dengan lebih sederhana. Secara umum graf G didefiniskan oleh sepasang himpunan ( V,E ) yang terdiri dari dua himpunan berhingga V dan E .  Himpunan V adalah himpunan  tak  kosong  dari  simpul-simpul ( vertices atau node ),  himpunan E adalah himpunan  sisi  ( edges atau arsc )  yang menghubungkan  sepasang  simpul  tersebut Harary F, (1969).
Karena  bentuk  penyelesaian  masalah penugasan juga terdapat pada metode hungarian yang  juga  merupakan  sebuah  penyelesaian algoritma  kombinasional  untuk  optimasi,  di mana  metode  hungarian  adalah  komplekistas algoritma  yang  polinomial.  Salah  satu  cara untuk  menyelesaikan  permasalahan  metode hungarian  dengan  membangkitkan  baris  dan kolom  dari  matriks  sampai  nol  unik  muncul  di setiap  baris  dan  kolom  yang  dipilih  sebagai alokasinya. Hal ini bertujuan untuk menetapkan pekerja dengan pekerjaan agar alokasi penugasan  memperoleh  nilai  yang  paling optimal.
Dari  hal  ini  dapat  dilihat  bahwa  kedua metode  yang  saling  lepas  tersebut  memilik kesamaan  penggunaan  dalam  contoh  kasus masalah  penugasan  sehingga  sangat  menarik rasanya  untuk  dicari  apakah  kedua  metode memang  saling  berhubungan.  Dalam  konteks penelitian  ini  merujuk  pada  perosalan  masalah penugasan tak seimbang.

## B. Metode Penelitian

## 1. Graf Matching
Matching merupakan  permasalahan  yang memasangkan  pasangan  tepat  satu  pada  setiap elemen dalam sebuah himpunan dengan elemen yang lainnya. Matching M merupakan himpunan  sisi  sedemikian  rupa  sehingga  kedua sisi M tidak  bertemu  di  titik  yang  sama. Banyaknya matching yang  ada  pada  suatu  graf disebut  kardinalitas  matching,  dan  disimbolkan dengan | M | Kocay dan Kreher (2005).
Matching i maksimum adalah matching yang mempunyai i jumlah bobot sisi i yang maksimum. M disebut i matching maksimum i jika G tidak memuat matching M’ yang lain dengan | M’ |≥| M | Bondy dan Murty, (1976).
Matching sempurna  apabila matching pada graf  melibatkan  semua  titik  pada  graf G Chartrand dan Oellermann (1993).
1. Sampul Saturated sebuah  simpul  yang beririsan ( incident ) dengan i sisi (garis) matching M Gondran i dan Minoux (1984).
2.  Simpul  unsaturated sebuah  simpul  yang tidak i beririsan i ( incident )  dengan i sisi  (garis) matching M Gondran dan Minoux (1984).
1.  Lintasan  alternating sebuah i lintasan i pada i graf  yang i sisi-sisinya  bergantian i antara i matching dan  bukan matching .  Gondran i dan Minoux (1984).
Gambar 1 . Lintasan Alternating
2.  Lintasan  augmenting sebuah i lintasan  pada graf  yang  simpul i awal i dan  simpul  akhirnya merupakan simpul unsaturated .
Gambar 2 . Lintasan Augmenting
2. Masalah Penugasan
Masalah i penugasan  adalah i masalah  yang spesifik yang diturunkan dari linear programming (Program Linear) dengan pengaturan  untuk i menyajikan i masalah  yang harus dipecahkan. Dalam i Linear Programming (LP),  terdapat i 3  elemen  utama i yaitu i variabel i keputusan, fungsi tujuan dan fungsi kendala.
Dalam hal ini permasalahan dapat diselesaikan  dengan  masalah  penugasan  adalah masalah  maksimum  dan  minimal  dengan sebuah  asumsi  bahwa m  =  n ,  sehingga  akan terdapat n ! ( n factorial)  penuguasan  dalam permasalahan  karena  berpasangan  satu-satu Munkres (1957).
Adapun  asumsi-asumi  dalam  masalah penugasan yang harus dipenuhi sebagai berikut:
1. Jumlah  pekerja  dan  pekerjaan  haruslah sama jika tidak maka harus ditambahkan dengan variabel dummy . 2. Suatu pekerja hanya ditugaskan kedalam satu pekerjaan saja.
3. Ada  biaya C ij yang  dihubungkan  oleh pekerja i ( i = 1 , 2 , 3 , … , m ) 4. Menentukan  bagaimana  mengerjakan seluruh penugasan untuk meminimalkan  dan maksimum.
Pada  pemecahan  masalah  penugasan  selalu dikaitkan  dengan  tabel  ataupun  matriks,  pada
umumnya  baris  berisikan  pekerja  yang  ingin ditetapkan  dan  kolom  terdiri  dari  pekerjaan yang  ingin  ditetapkan  Hillier  dan  Gerald (1990).
Model  dari  masalah  penugasan  pada  dapat ditulis  secara  matematis  sebagai  berikut  Hillier (2008). Di mana fungsi tujuannya ialah
𝑍 =   ∑ ∑ 𝐶 𝑖𝑗 𝑥 𝑖𝑗 𝑚 𝑗=1 𝑛 𝑖=1
𝑍 =   𝐶 11 𝑥 11 +   𝐶 22 𝑥 22 + ⋯ +   𝐶 𝑛𝑚 𝑥 𝑛𝑚 Dengan kendala sebagai berikut.
∑ 𝑥 𝑖𝑗 𝑛 𝑖=1 = 0 atau 1
Di mana untuk i = ( 1 , 2 , 3 , …. , n ) ∑ 𝑥 𝑖𝑗 𝑚 𝑖=1 = 0 atau 1
Di mana untuk j = ( 1 , 2 , 3 , …. , m ) Dengan x ij sebagai berikut.

## 3. Algoritma  Matching  Maksimum  untuk Graf Bipartit
Berikut merupakan langkah-langkah
penyelesaian algoritma matching graf. Chartrand dan Oellerman (1993):
1. Langkah  pertama  adalah  pelabelan  simpul ℓ . 1a. ∀𝑣  ∈ V 1 , misal ℓ = 𝑚𝑎𝑥 𝑢 ∈ 𝑉 2 𝑤(𝑣, 𝑢) . 1b. ∀𝑢  ∈ V 2 , misal ℓ = 0.
1c. 𝐻 ℓ adalah  subgraf  perentang  dari 𝐺 ℓ dengan himpunan sisi 𝐸 ℓ . 1d. Misal 𝐺 ℓ adalah graf dasar dari 𝐻 ℓ . 2. Pilih sembarang matching M di 𝐺 ℓ . 3. Jika pada 𝐺 ℓ terdapat matching maksimum, apakah 𝐺 ℓ merupakan matching sempurna.
Matching sempurna tersebut adalah matching maksimum  di 𝐺′ ℓ .  Jika matching maksimum di 𝐺 ℓ bukan merupakan matching sempurna,  maka  harus  disusun pohon alternating  T yang  berakar  disimpul unsaturated untuk  menentukan  pelabelan simpul ℓ′ .  Selanjutnya  ini  langkah-langkah untuk menentukan  pelabelan simpul ℓ′ . 3a. Pada  setiap  simpul  di V 1 merupakan simpul saturated di M ,  maka M adalah matching maksimum  di G dan  proses berhenti. Jika tidak maka lanjutkan. 3b. Seandainya x
adalah simpul unsaturated di V 1 .
3c. Buatlah pohon alternating dari M yang berakar i pada x .  Jika i pada  lintasan augmenting-P terdapat  di 𝐺 ℓ ,  maka ganti M dengan M' untuk matching baru.  Jika  tidak  terdapat  lintasan augmenting  P ,  dan T adalah  pohon alternating dari M dengan  akar x yang tidak  dapat  diperluas i lagi  di 𝐺 ℓ ,  maka pelabelan  simpul ℓ diganti  dengan sebuah i pelabelan  simpul ℓ′ ,  dengan sifat  bahwa M dan T termuat  di  graf dasar 𝐺 ℓ dari 𝐻 ℓ . 4. Menghitung pelabelan simpul ℓ ′ . Misalkan 𝑚 ℓ =  minimal  { ℓ(𝑣) + ℓ(𝑢) − 𝑤(𝑣, 𝑢)|𝑣 ∈ V 1 ∩ V ( T ) dan 𝑢  ∈ V 2 − V ( T )}. 4a. ℓ ( x ) − 𝑚 ℓ untuk 𝑣  ∈ V 1 ∩ V ( T ) 4b. ℓ ( x ) + 𝑚 ℓ untuk 𝑢  ∈ V 2 ∩ V ( T ) 4c. ℓ ( 𝑣 ) untuk yang lainnya.
5. Jika  pada  pelabelan  simpul ℓ′ belum  ada yang  memuat  semua  simpul  di V 1 ,  maka harus diulang ke langkah 3.3.
4. Metode Hungarian Metode hungarian i berguna untuk menentukan  penugasan i pekerja  ke i pekerjaan tertentu i secara i satu i persatu i ( one  by  one ) Ndururu,  Waruwu,    Yanny  (2017).  Dalam menyelesaikan  persoalan  metode  hungarian untuk menyelesaikan masalah penugasan:
1. Identifikasi i dan  penyederhanaan i masalah dalam bentuk matriks.
2. Tentukan  nilai  maksimum  dari  setiap baris, kemudian nilai terbesar dikurangkan dengan setiap entri baris.
3. Periksa i setiap  kolom  dan  baris  telah terdapat  nilai  nol.  Jika  sudah,  maka lanjutkan.  Jika  setiap  baris  dan  kolomnya belum  terdapat  nilai  nol  maka  nilai  yang tidak  memiliki  elemen  nol  dikurangkan i dengan nilai yang terkecil.
4. Tarik  garis i melalui  baris i dan  kolom dengan  nilai  nol,  pertama-tama  pilih  baris dan  kolom  dengan  angka  nol  paling banyak i untuk i mendapatkan  jumlah i baris seminimal i mungkin.  Jika  jumlah  baris sudah  sama  dengan  jumlah  baris  dan kolom matriks, tabel tersebut i optimal. Jika tidak, lanjutkan ke langkah 6. Langkah ini disebut memeriksa optimalitas ketika garis cakupan i kurang i dari n –  baris  dan  ( n – kolom).
5. Kurangi i semua  nilai  yang  tidak i tercakup oleh nilai i yang i lebih kecil dan tambahkan
nilai  pada  perpotongan  garis  dengan  nilai yang lebih kecil.
6. Jika  semua  baris  dan  kolom  dengan  nilai nol dicakup oleh baris, tabelnya optimal.

## C. Hasil dan Pembahasan

## 1. Pengolahan Data
Data  dalam  kasus  yang  sesuai  dengan masalah  penugasan  diambil  pada  jurnal  yang berjudul A  New  Approach  To  Solve  An Unbalanced  Assignment  Problem .  Kore  B.  G (2012).
Tabel 1 . Data Masalah Penugasan Karyawan di Perushasan
Di  mana  himpunan V 1 ={ x 1 , x 2 , x 3 , x 4 , x 5 } menyatakan  pekerja  dan  himpunan V 2 ={ y 1 , y 2 , y 3 , y 4 , y 5 , y 6 } menyatakan pekerjaan.
2. Algoritma Matching Graf Bipartit
Dalam
melakukan pengerjaan
pelakasanaan  masalah  penugasan  maka  harus dibuat  terlebih  dahulu  variabelnya.  Dalam  hal ini  sudah  ditentukan  bahwa V 1 ={ x 1 , x 2 , x 3 , x 4 , x 5 }  dan V 2 ={ y 1 , y 2 , y 3 , y 4 , y 5 , y 6 }  data  masalah penugasan.
Gambar  3 .  Graf  Bipartit  Berbobot G Pada Masalah Penugasan
1. Langkah  pertama  adalah  pelebelan  simpul
ℓ . y 1 y 2 y 3 y 4 y 5 y 6
𝑥 1 𝑥 2 𝑥 3 𝑥 4 𝑥 5 [ 80 140 80 100 56 98 48 64 94 126 170 100 56 80 120 100 70 64 99 100 100 104 80 90 64 90 90 60 60 70 ]
1a. ∀𝑥  ∈ V 1 , misal ℓ = 𝑚𝑎𝑥 𝑦 ∈ 𝑉 2 𝑤(𝑥, 𝑦) Sehingga diperoleh nilai ℓ (𝑥) =
(140, 170, 120, 104, 90) 1b. ∀𝑦  ∈ V 2 , misal ℓ = 0 Sehingga nilai pelebelan ℓ (𝑦) = (0,0,0,0,0,0) 1c. 𝐻 ℓ adalah  subgraf  perentang  dari 𝐺 ℓ dengan himpunan sisi 𝐸 ℓ 1d. Misal 𝐺 ℓ adalah graf dasar dari 𝐻 ℓ .
Gambar 4 . Equality Subgraf di 𝐺 ℓ
2. Pilih sembarang matching M di 𝐺 ℓ Misalkan  dipilih matching  M . M 0  = ( x 2 , y 5 ), ( x 3 , y 3 ), ( x 4 , y 4 ), ( x 5 , y 2 )
Gambar 5 . Graf Matching M 0 di 𝐺 ℓ
3. Diperoleh matching maksimum di 𝐺 ℓ bukan matching sempurna. sehingga akan disusun pohon alternating  T yang  berakar  di  titik unsaturated menentukan  pelabelan  simpul
ℓ′ .
3a. Terdapat  simpul V 1 merupakan  sebuah simpul unsaturated di M ,  maka lanjutkan.
3b. Misal x simpul unsaturated di V 1 , maka terdapat x 1 adalah  sebuah  simpul unsaturated sebagai simpul awal. 3c. Susun sebuah pohon alternating dari M yang berawal pada x 1 . Diperoleh pohon
alternating  T di  mana  V(T)  =  { x 1 , y 2 , x 5 },  dari  hal  ini  tidak  ditemukannya lintasan augmenting dan pohon alternating  T dari M yang  berawal x 1 tidak  dapat  diperluas  lagi  di 𝐺 ℓ . Sehingga  pelebelan  simpul ℓ diganti menjadi pelebelan simpul baru ℓ′ .
4. Menghitung pelabelan simpul baru ℓ ′ 𝑚 ℓ =  minimal  { ℓ(𝑥) + ℓ(𝑦) − 𝑤(𝑥, 𝑦)|x ∈ V 1 ∩ V ( T )  dan 𝑦  ∈ V 2 − V ( T )}  sehingga berlaku ℓ ′ 4a. ℓ ( x ) − 𝑚 ℓ untuk 𝑥  ∈ V 1 ∩ V ( T ) 4b. ℓ ( x ) + 𝑚 ℓ untuk 𝑦  ∈ V 2 ∩ V ( T ) 4c. ℓ ( 𝑥 ) untuk yang lainnya Anggota  himpunan  untuk 𝑥  ∈ V 1 ∩ V ( T ) ialah { x 1 , x 5 } dan anggota himpunan 𝑦  ∈ V 2 ∩ V ( T ) ialah { y 1 , y 3 , y 4 , y 5 , y 6 }. Di mana S = V 1 ∩ V ( T )  Untuk  perhitugan  nilai 𝑚 ℓ = 𝑚𝑖𝑛 𝑥∈𝑆,𝑦∉𝑇 ℓ(𝑥) + ℓ(𝑦) − 𝑤(𝑥, 𝑦) adalah sebagai berikut.
𝑚 ℓ = ℓ(𝑥 1 ) + ℓ(𝑦 1 ) − 𝑤(𝑥 1 , 𝑦 1 ) = 140 + 0 − 80 = 60 𝑚 ℓ = ℓ(𝑥 1 ) + ℓ(𝑦 3 ) − 𝑤(𝑥 1 , 𝑦 3 ) = 140 + 0 − 80 = 60 𝑚 ℓ = ℓ(𝑥 1 ) + ℓ(𝑦 4 ) − 𝑤(𝑥 1 , 𝑦 4 ) = 140 + 0 − 100 = 40 𝑚 ℓ = ℓ(𝑥 1 ) + ℓ(𝑦 5 ) − 𝑤(𝑥 1 , 𝑦 5 ) = 140 + 0 − 56 = 84 𝑚 ℓ = ℓ(𝑥 1 ) + ℓ(𝑦 6 ) − 𝑤(𝑥 1 , 𝑦 6 ) = 140 + 0 − 98 = 42 𝑚 ℓ = ℓ(𝑥 5 ) + ℓ(𝑦 1 ) − 𝑤(𝑥 5 , 𝑦 1 ) = 90 + 0 − 64 = 24 𝑚 ℓ = ℓ(𝑥 5 ) + ℓ( 𝑦 4 ) − 𝑤(𝑥 5 , 𝑦 4 ) = 90 + 0 − 60 = 20 𝑚 ℓ = ℓ(𝑥 5 ) + ℓ( 𝑦 5 ) − 𝑤(𝑥 5 , 𝑦 5 ) = 90 + 0 − 60 = 30 𝑚 ℓ = ℓ(𝑥 5 ) + ℓ( 𝑦 6 ) − 𝑤(𝑥 5 , 𝑦 6 ) = 𝟗𝟎 + 𝟎 − 𝟕𝟎 = 𝟐𝟎
Sehingga diperoleh nilai dari 𝑚 ℓ = 20 diperoleh  dari sisi  ( x 5 , y 6 )  nilai  pelebelan ℓ ′ ialah sebagai berikut.
Gambar 6 . Matching M 0 dan Sisi 𝑚 ℓ
Karena  pada  pelebelan  simpul ℓ ′ belum memuat  simpul ℓ semua  simpul  di ℓ maka kembali ke langkah 3c.
3.c Susun  sebuah  pohon alternating dari M yang  berawal  pada x 1 .  Diperoleh  sebuah pohon alternating T di mana V ( T ) = { x 1 , y 2 , x 5, y 6 },  dapat  ditemukan  sebuah  lintasan augmenting-M yaitu P 0 =  {( x 1 , y 2 ),  ( x 5 , y 2 ),
( x 5, y 6 )}.  Sehingga  lintasana  augmenting P 0 dapat digunakan dalam pembentukan matching yang baru.
Gambar 7 . Lintasan Augmenting - M
M 1 = M 0 ⨂ P 0 M 1 = {( x 2 , y 5 ), ( x 3 , y 3 ), ( x 4 , y 4 ), ( x 5 , y 2 )} ⨂ {( x 1 , y 2 ),
( x 5 , y 2 ), ( x 5 , y 6 )} M 1 = {( x 1 , y 2 ), ( x 2 , y 5 ), ( x 3 , y 3 ), ( x 4 , y 4 ), ( x 5 , y 6 )}
Gambar 8 . Matching Maksimum M 1
Simpul V 1 ,  sudah  merupakan  sebuah  simpul yang saturated ,  ini  berarti  sebuah  proses penyelesaian telah berhenti. Sehingga hasil dari graf matching tersebut  merupakan  sebuah penyelesaian  dari  masalah  penugasan  ini  bisa juga disebut sebagai matching sempurna.
Z=w ( x 1 , y 2 )  + w ( x 2 , y 5 )  + w ( x 3 , y 3 )  + w ( x 4 , y 4 )  + w ( x 5 , y 6 )
Z = 140 + 170 + 120 + 120 + 104 + 70
Z = 604 Dengan penempatan karyawannya pada
masalah penugasan ialah sebagai berikut
Pekerja x 1 mengerjakaan pekerjaan pada y 2
Pekerja x 2 mengerjakaan pekerjaan pada y 5 Pekerja x 3 mengerjakaan pekerjaan pada y 3 Pekerja x 4 mengerjakaan pekerjaan pada y 4 Pekerja x 5 mengerjakaan pekerjaan pada y 6
Gambar 9 . Solusi Penempatan Karyawan

## 3. Metode Hungarian
Pada  data  kasus  permasalahan  masalah penugasan yang ditampilkan terdapat 6
pekerjaan dan 5 pekerja maka harus ditmabahkan dengan variabel dummy .
Tabel  2. Masalah  Penugasan  Karyawan
Dengan Dummy Langkah-langkah dalam menyelesaikan
masalah  penugasan  metode  Hungarian  sebagai berikut.
1. Mengidentifikasi dan penyederhanaan masalah dalam bentuk matriks penugasan.
[ 80 140 80 100 56 98 48 64 94 126 170 100 56 80 120 100 70 64 99 100 100 104 80 90 64 90 90 60 60 70 0 0 0 0 0 0 ] 2. Menentukan i nilai terbesar i dari setiap i baris dan  kolom,  kemudian i mengurangkan  nilai i terbesar dengan setiap nilai dalam baris.
[ 80 𝟏𝟒𝟎 80 100 56 98 48 64 94 126 𝟏𝟕𝟎 100 56 80 𝟏𝟐𝟎 100 70 64 99 100 100 𝟏𝟎𝟒 80 90 64 𝟗𝟎 𝟗𝟎 60 60 70 0 0 0 0 0 0 ]
3. Mengkonfirmasi  apakah  setiap  kolom  telah mempunyai nilai nol.
[ 60 𝟎 60 40 84 42 122 106 76 44 𝟎 70 60 40 𝟎 20 50 56 5 4 4 𝟎 24 14 26 𝟎 𝟎 30 30 20 𝟎 𝟎 𝟎 𝟎 𝟎 𝟎 ]
Karena  nilai  pada  matriks  telah  memiliki nilai nol maka akan ditarik garis.
4. Menarik i garis i pada i baris atau  kolom yang mempunyai i nilai i nol  dengan  cara  memilih baris atau kolom yang memiliki nol.
[ 60 𝟎 60 40 84 42 122 106 76 44 𝟎 70 60 40 𝟎 20 50 56 5 4 4 𝟎 24 14 26 𝟎 𝟎 30 30 𝟐𝟎 𝟎 𝟎 𝟎 𝟎 𝟎 𝟎 ] Dari  matriks  diatas  banyaknya  garis  tidak sama dengan jumlah baris dan kolom maka dilanjukan ke Langkah berikutnya.
5. Nilai  pada  setiap  baris  dan  kolom  yang belum  memiliki  nilai  nol  dikurangkan dengan  nilai  terkecil.  Pada  matriks  berikut ini nilai terkecilnya terdapat pada angka 20.
[ 60 𝟎 60 40 84 42 122 106 76 44 𝟎 70 60 40 𝟎 20 50 56 5 4 4 𝟎 24 14 26 𝟎 𝟎 30 30 𝟐𝟎 𝟎 𝟎 𝟎 𝟎 𝟎 𝟎 ]
Nilai  terkecilnya  dikurangkan  untuk  setiap nilai yang tidak digaris dan pada perpotongan  garis  tersebut  ditambahkan dengan nilai terkecil yaitu 20.
[ 40 𝟎 60 20 64 22 122 126 96 44 𝟎 70 40 40 𝟎 0 30 36 5 24 24 𝟎 24 14 6 𝟎 𝟎 10 10 𝟎 𝟎 𝟐𝟎 𝟐𝟎 𝟎 𝟎 𝟎 ]
Sehingga jumlah garis dan jumlah banyaknya  baris  dan  kolom  pada  matriks sudah sama.
6. Jika  jumlah  baris  dan  kolom  sudah  sama dengan  banyak  garis,  maka  matriks  sudah optimal.
[ 40 𝟎 60 20 64 22 122 126 96 44 𝟎 70 40 40 𝟎 0 30 36 5 24 24 𝟎 24 14 6 0 0 10 10 𝟎 𝟎 20 20 0 0 0 ]
Sehingga  nilai  optimal  dari  permasalahan penugasan  tersebut  ialah  yang  memiliki nilai nol bertulis tebal.
Pada  matriks  tersebut  maka  diperoleh  nilai optimalnya  pada  nilai  matriks  pada  baris dan kolom yang dilingkarin
[ 80 140 80 100 56 98 48 64 94 126 170 100 56 80 120 100 70 64 99 100 100 104 80 90 64 90 90 60 60 70 0 0 0 0 0 0 ]
Dari tabel matriks tersebut diperoleh bahwa nilai optimal maksimumnya  ialah Z = x 2 + x 5 + x 3 + x 4 + x 6 + x 1 Z = 140 + 170 + 120 + 104 + 70 + 0 Z = 604
Sehingga  nilai  pada  masalah  penugasan memiliki  optimal  maksimumnya  ialah  604. Penempatan yang lebih jelas dari pekerja ke pekerjaan dilihat pada table ini.
Tabel  3. Alokasi  Solusi  Optimal  Dengan Metode Hungarian Pekerja Pekerjaan Bobot x 1 y 2 140 x 2 Y 5 170 x 3 y 3 120 x 4 y 4 104 x 5 y 6 70 Dummy y 1 0
Total 604
Dengan  penempatan  pekerjanya  pada  masalah penugasan ialah sebagai berikut Pekerja x 1 mengerjakaan pekerjaan pada y 2 Pekerja x 2 mengerjakaan pekerjaan pada y 5 Pekerja x 3 mengerjakaan pekerjaan pada y 3 Pekerja x 4 mengerjakaan pekerjaan pada y 4 Pekerja x 5 mengerjakaan pekerjaan pada y 6
Untuk  variabel Dummy dapat  dialokasikan  ke pada  variabel    pekerjaan y 1 , y 4 , y 5 dan y 6 . Dikarenakan pekerja x 2 mengerjakaan pekerjaan pada y 5 ,  pekerja x 4 mengerjakaan  pekerjaan pada y 4 dan  pekerja x 5 mengerjakaan  pekerjaan pada y 6 sehingga  variabel Dummy dapat  pada pekerjaan y 1
Berdasarkan pengerjaan yang dilakukan maka  diperoleh  hasil  bahwa  kedua  metode memiliki  hasil  maksimum  yang  optimal.  Hasil optimal  pada  pengerjaan  tersebut  memliki  nilai yang  sama  yaitu  604. Untuk  kedua  metode tersebut  bisa  digunakan  kedalam  sebuah permasalahan penugasan, karena dari hasil yang diperoleh  keduanya  mempunyai  hasil  yang sesuai  dari  kedua  metode  ini.  Sehingga  dapat dikatakan  bahwa  masalah  penugasan  dapat diselesaikan  pada  algoritma matching graf  dan metode hungarian.

## D. Kesimpulan dan Saran
1. Kesimpulan :
1. Berdasarkan  penelitian,  data  pada masalah  penugasan  menghasilkan  nilai optimal  yang  sama  yaitu  604.  Oleh karenanya, masalah penugasan ( Assigment  Problem )  bisa  diselesaikan pada  algoritma matching graf  bipartit dan metode hungarian.
2. Matching graf  bipartit  dan  metode Hungarian mempunyai hubungan dalam penyelesaiaan persoalan masalah penugasan  sehingga  salah  satu  hal tersebut dapat digunakan dalam mencari nilai optimal untuk pemecahan permasalahan masalah penugasan.

## E. Daftar Pustaka
Bondy,  J.A  dan  Murty,  U.S.R.  1976. Graph Theory  with  Applications. Mac Millan Press: New York.
Chartrand,    Gary    dan    Oellermann,    Ortrud. 1993. Applied    and    Algoritmic Graph  Theory. Mc Graw Hill
International Edition: New York.
Gondran  M,  and  Minoux,  M.  1984. Linear Algebra in Dioids: A Survey of Recent Results. In Algebraic and Combinatorial Methods in Operations Research ,  Vol  95  of  North-Hollad Math. Study,.
North-Holland,
Amsterdam.
Harary  F,  1969 Graph  Teori. Addison-Wesley Publish Company Inc, London.
Hillier,  Fridrick  S  and  Gerald  J.  Lieberman. 1990. Introduction  To  Operations Research,  Fifth  Edition ,  McGraw-
Hill, Inc., USA
Hillier,  S.  F.    J.  G.  Lieberman.  2008. Introduction  To  Operations  Research (Edition  9) .  New  York:  Mc  Graw- Hill, Inc.
Kocay,  William  dan  Kreher,  Donald.  2005. Graph    Theory    and    Optimization. Chapman  Hall / CRC.
Kore.  G,.  2012. A  New  Approach  To  Solve  An Unbalanced  Assignment  Problem .
International  Journal  of  Physics  and Mathematical Sciences. Vol 2 (1)
Munkres, J. 1957. Algorithms for the Assignment and Transportation
Problems .  Journal  of  the  Society  for
Industrial  and  Applied  Mathematics,
5(1):32-38.
Ndururu, E., Waruwu, F. T.,  Yanny, A. 2017. Alokasi  Pekerja  pada  Suatu  Proyek dengan  metode  Hungarian  (Studi Kasus: PT Ira  Widya Utama Medan) . KOMIK (Konferensi Nasional Teknologi  Informasi  dan  Komputer), Vol 1 (1). Venkateswaran, R., Obranivic, Z., Raghavendra, C.S., 1993. Cooperative Genetic for Optimization  Problem  in  Distributed Computer  System .  Technical  report
TR-EECS-93-018.  School  of  EECS.
Washington State University.