MASALAH PENUGASAN (ASSIGNMENT PROBLEM)

Salah satu metode yang digunakan untuk Penugasan adalah Metode Hungarian.
Pada Metode Hungarian, jumlah sumber-sumber yang ditugaskan harus sama
persis dengan jumlah tugas yang akan diselesaikan. Setiap sumber harus
ditugaskan hanya untuk satu tugas. Jadi, masalah penugasan akan mencakup
sejumlah n sumber yang mempunyai n tugas, sehingga ada n! (n faktorial)
kemungkinan. Masalah ini dapat dijelaskan dengan mudah dalam bentuk matriks
segi empat, dimana baris-barisnya menunjukkan sumber-sumber dan kolomkolomnya
menunjukkan tugas-tugas.
1. Masalah Minimisasi
Contoh:
Sebuah perusahaan kecil mempunyai 4 pekerjaan yang berbeda untuk diselesaikan
oleh 4 karyawan. Biaya penugasan seorang karyawan untuk pekerjaan yang
berbeda adalah berbeda karena sifat pekerjaan berbeda-beda. Setiap karyawan
mempunyai tingkat ketrampilan, pengalaman kerja dan latar belakang pendidikan
serta latihan yang berbeda pula. Sehingga biaya penyelesaian pekerjaan yang
sama oleh para karyawan yang berlainan juga berbeda. Tabel biaya sebagai
berikut:

PEKERJAAN

pekerjaan/KARIAWAN	I	II	III	IV
RAIHAN	Rp 150	Rp 200	Rp 180	Rp 220
HAMDAN	Rp 140	Rp 160	Rp 210	Rp 170
HASAN	Rp 250	Rp 200	Rp 230	Rp 200
DZAKWAN	Rp 170	Rp 180	Rp 180	Rp 160

Masalahnya adalah bagaimana menugaskan keempat karyawan untuk
menyelesaikan keempat pekerjaan agar total biaya pekerjaan minimum.
Langkah-langkah:
1. Menyusun tabel biaya seperti tabel di atas.
2. Melakukan pengurangan baris, dengan cara:
a. memilih biaya terkecil setiap baris
b. kurangkan semua biaya dengan biaya terkecil setiap baris
Sehingga menghasilkan reduced cost matrix /matrik biaya yang telah dikurangi.

PEKERJAAN

pekerjaan/karyawan	I	II	III	IV
RAIHAN	(150-150)=0	(200-150)=50	(180-150)= 30	(220-150)= 70
HAMDAN	(140-140)= 0	(160-140)= 20	(210-140)=70	(170-140)= 30
HASAN	(250-200)= 50	(200-200)= 0	(230-200)= 30	(200-200)= 0
DZAKWAN	(170-160)= 10	(180-160)= 200	(180-160)= 20	(160-160)= 0

3. Melakukan pengurangan kolom
Berdasarkan hasil tabel langkah 2, pilih biaya terkecil setiap kolom untuk
mengurangi seluruh biaya dalam kolom-kolom tersebut. Pada contoh di atas hanya
dilakukan pada kolom III karena semua kolom lainnya telah mempunyai elemen
yang bernilai nol (0). Jika langkah kedua telah menghasilkan paling sedikit satu
nilai nol pada setiap kolom, maka langkah ketiga dapat dihilangkan. Berikut
matrix total opportunity cost, dimana setiap baris dan kolom terdapat paling
sedikit satu nilai nol.

Tabel total opportunity cost matrix

pekerjaan/karyawan	I	II	III	IV
RAIHAN	0	50	(30-20)=10	70
HAMDAN	0	20	(70-20)=50	30
HASAN	50	0	(30-20)=10	0
DZAKWAN	10	20	(20-20)=0	0

4. Membentuk penugasan optimum
Prosedur praktis untuk melakukan test optimalisasi adalah dengan menarik
sejumlah minimum garis horisontal dan/ atau vertikal untuk meliputi seluruh
elemen bernilai nol dalam total opportunity cost matrix. Jika jumlah garis sama
dengan jumlah baris/ kolom maka penugasan telah optimal. Jika tidak maka harus
direvisi.

Tabel total opportunity cost matrix

pekerjaan/karyawan	I	II	III	IV
RAIHAN	0	50	10	70
HAMDAN	0	20	50	30
HASAN	50	0	10	0
DZAKWAN	10	20	0	0

5. Melakukan revisi tabel
a. Untuk merevisi total opportunity cost, pilih angka terkecil yang tidak
terliput (dilewati) garis. (pada contoh di atas = 10)
b. Kurangkan angka yang tidak dilewati garis dengan angka terkecil (10)
c. Tambahkan angka yang terdapat pada persilangan garis dengan angka
terkecil (10) yaitu (50) pada Hasan dan (10) pada Dzakwan.
d. Kembali ke langkah 4
Revised matrix:

Tabel total opportunity cost matrix

pekerjaan/karyawan	I	II	III	IV
RAIHAN	0	40	0	60
HAMDAN	0	10	40	20
HASAN	60	0	10	0
DZAKWAN	20	20	0	0

Tabel PENUGASAN

PENUGASAN	BIAYA
RAIHAN III	Rp 180
HAMDAN I	Rp 140
HASAN II	Rp 200
DZAKWAN IV	Rp 160
JUMLAH IV	Rp 680

2. Jumlah Pekerjaan Tidak Sama Dengan Jumlah Karyawan
Bila jumlah pekerjaan lebih besar dari jumlah karyawan, maka harus ditambahkan
karyawan semu (dummy worker). Biaya semu sama dengan nol karena tidak akan
terjadi biaya bila suatu pekerjaan ditugaskan ke karyawan semu. Bila jumlah
karyawan lebih banyak daripada pekerjaan, maka ditambahkan pekerjaan semu
(dummy job). Sebagai contoh, bila jumlah pekerjaan lebih besar dari jumlah
karyawan dapat dilihat pada tabel berikut:

DUMMY JOB

pekerjaan/karyawan	I	II	III	IV
RAIHAN	Rp.150	Rp.200	Rp.180	Rp.220
HAMDAN	Rp.140	Rp.160	Rp.210	Rp.170
HASAN	Rp.250	Rp.200	Rp.230	Rp.200
DZAKWAN	Rp.170	Rp.180	Rp.180	Rp.160
DUMMY JOB	Rp.0	Rp.0	Rp.0	Rp.0

DUALITAS

Dalam sebuah pemodelan Pemrograman Linear, terdapat dua konsep yang saling
berlawanan. Konsep yang pertama kita sebut Primal dan yang kedua Dual.Bentuk
Dual adalah kebalikan dari bentuk Primal. Hubungan Primal dan Dual sebagai
berikut:
Masalah Primal (atau Dual) Masalah Dual (atau Primal)
Koefisien fungsi tujuan ……………… Nilai kanan fungsi batasan
Maksimumkan Z (atau Y) …………... Minimumkan Y (atau Z)
Batasan i …………………………….. Variabel yi (atau xi)
Bentuk …………………………….. yi 0
Bentuk = …………………………….. yi dihilangkan
Variabel Xj ………………………….. Batasan j
Xj 0 ………………………………... Bentuk
Xj 0 dihilangkan …………………... Bentuk =
Contoh 1:
Primal
Minimumkan Z = 5X1 + 2X2 + X3
Fungsi batasan: 1) 2X1 + 3X2 + X3 20
2) 6X1 + 8X2 + 5X3 30
3) 7X1 + X2 + 3X3 40
X1 , X2 , X3 0
Dual
Maksimumkan Y= 20 y1 + 30 y2 + 40 y3
Fungsi batasan: 1) 2y1 + 6y2 + 7y3 5
2) 3y1 + 8y2 + y3 2
3) y1 + 5y2 + 3y3 1

Contoh 2 :
Primal
Minimumkan Z = 2X1 + X2
Fungsi batasan: 1) X1 + 5X2 10
2) X1 + 3X2 6
3) 2X1 + 2X2 8
X1, X2 0
Dual
Maksimumkan Y = 10 y1 + 6y2 + 8y3
Fungsi batasan : 1) y1 + y2 + 2y3 2
2) 5y1 + 3y2 + 2y3 1
y1, y2 0
Contoh 3:
Primal
Maksimumkan Z = X1 + 3X2 – 2X3
Fungsi batasan: 1) 4X1 + 8X2 + 6X3 = 25
2) 7X1 + 5X2 + 9X3 = 30
X1, X2, X3 0
Dual
Minimumkan Y= 25y1 + 30y2
Fungsi batasan: 1) 4y1 + 7y2 1
2) 8y1 + 5y2 3
3) 6y1 + 9y2 -2