Kode Matkul : 221

SKS : 3 SKS
Waktu : 150 menit
Pertemuan Ke- Pokok Bahasan
1 Pengertian Teknik Riset Operasional
2 Program Linier
3 Metode Transportasi
4 Penyelesaian Optimal
5 Masalah Penugasan
6 Metode Pengendalian Persedian
7 Review Materi pertemuan 1 s/d 6
8 UTS
Pertemuan Ke- Pokok Bahasan
9 Presentasi Kelompok
10 Presentasi Kelompok
11 Presentasi Kelompok
12 Presentasi Kelompok
13 Presentasi Kelompok
14 Presentasi Kelompok
15 Presentasi Kelompok
16 UAS
 Chapter 15:
Masalah Penugasan
 Definisi Masalah Penugasan

1. Masalah penugasan (assignment problems)

merupakan kasus yang berhubungan dengan
pemrograman linier.
2. Pendelegasian sejumlah tugas (assignment) kepada
sejumlah penerima tugas (assignee) dalam basis
satu-satu.
3. tujuan yang ingin dicapai dalam menyelesaikan
masalah ini adalah berusaha untuk menjadwalkan
setiap assignee pada suatu assignment sedemikian
rupa sehingga kerugian yang ditimbulkan minimal
atau keuntungan yang didapatkan maksimal
 Masalah Penugasan

Ada 3 macam permasalahan dalam permasalahan

penugasan (Assignment Problem) yaitu:

1. Masalah Minimisasi
2. Jumlah Tugas Tidak Sama Dengan Jumlah
Karyawan
3. Masalah Maksimisasi
Salah satu teknik pemecahan masalah penugasan,
adalah metode Hungarian yang dikembangkan oleh D.
Konig 1916. Penerapan metode Hungarian ini memiliki
asumsi antara lain:

1. Sumber-sumber (skill) dari karyawan harus = tugas

yang akan dikerjakan
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).
Masalah ini dapat dijelaskan dengan mudah dalam
bentuk matriks segi empat, dimana baris-barisnya
menunjukkan sumber-sumber dan kolom-kolomnya
menunjukkan tugas-tugas.

8
 Masalah Penugasan

1. Masalah Minimisasi

Masalah yang berhubungan dengan optimalisasi berbagai

kemampuan (skill) dari personalia untuk berbagai macam
tugas yang akan dikerjakan dalam operasi perusahaan.
Berbagai macam skill di sini berkaitan dengan
kontraprestasi (imbalan jasa, berupa upah atau gaji) yang
akan dibayarkan kepada karyawan. Sedangkan berbagai
macam tugas adalah tugas-tugas yang telah dilimpahkan
kepada karyawan sesuai dengan skill yang dimilikinya.
 Masalah Penugasan

◼
 Masalah Penugasan

2. Tugas < Karyawan

Jika dalam masalah penugasan terdapat tugas <
karyawan, maka harus ditambahkan “Dummy Job” pada
kolom seperti contoh pada Tabel 2.21., sebagai berikut:
 Masalah Penugasan

3. Masalah Maksimalisasi
Dalam pembahasan masalah maskimisasi dengan
menggunakan metode Hungarian, maka Fungsi Tujuan
disebut dengan Indeks Produktivitas yang dapat diukur
melalui efektivitas pelaksanaan tugas oleh karyawan
secara individual.
 Masalah Penugasan

Langkah-langkah untuk menyelesaikan permasalahan

maksimisasi adalah sebagai berikut:
1. Merubah matriks profit menjadi Matrix Opportunity
Cost dengan cara mencari Profit Maximum, kemudian
mengurangkan dengan elemen angka yang sebaris
2. Menarik garis vertikal atau horizontal untuk
menghubungkan angka-angka nol.
3. Test Optimal, jika belum optimal, maka ulangi poin 1.
 Metode Hungaria
Assignment
1 2 … n
Assignee

1 …
2 …
… … … … …
n …
 Ekspresi model penugasan secara matematika adalah:
Dengan asumsi bahwa m = n sehingga,
0, jk pekerjaan ke-i tdk ditugaskan pada mesin ke-j

Xij =
1, jk pekerjaan ke-i ditugaskan pada mesin ke-j
n n
Minimukan z = ∑ ∑ cij xij
i=1j=1
dengan batasan:
n
∑ xij = 1 , i = 1, 2, … , n
j=1
n
∑ xij = 1 , j = 1, 2, … , n
i=1
xij = 0 atau 1
 Langkah-langkah penyelesaian:
1. Utk setiap baris ke-i, i = 1,2, … , n lakukan
c’ij = cij – min (cij) untuk setiap j = 1,2, … ,n
2. Utk setiap kolom ke-j, j= 1,2, … ,n lakukan
c’ij = cij – min (cij) untuk setiap i = 1,2, … ,n
3. Pastikan setiap baris dan kolom telah memuat paling
sedikit satu angka nol. Jika suatu baris memuat
hanya satu angka nol beri tanda kotak, jika tidak
lanjutkan baris berikutnya. Sedangkan pada kolom
yang memuat angka nol yang baru diberi tanda
kotak, jika memuat angka nol lain beri tanda silang.
Dengan cara yang sama kerjakan juga untuk
kolomnya.
4. Dari langkah 3 dan 4 akan diperoleh kondisi:
• Semua baris telah memuat tanda kotak, alokasi
optimal telah diperoleh pada tanda kotak tersebut.
• Ada beberapa baris yang tidak memuat tanda
kotak tetapi masih memuat angka nol yang tidak
disilang, yang dilakukan: coba beberapa alternatif
alokasi angka nol yang tersisa (yang tidak
disilang), pilih yang memberikan total biaya
minimum.
• Ada beberapa baris tidak memuat tanda kotak
tetapi angka nol yang ada telah disilang, sehingga
yang dilakukan:
a. Tariklah garis pada semua baris dan kolom
yang mengandung angka nol dengan jumlah
garis minimum, sehingga tidak terdapat lagi nol
pada matriks yang bersangkutan.
b. Tentukan diantara angka-angka yang tidak ikut
tergaris, satu angka terkecil kemudian
kurangkan sebesar harga angka ini kepada
semua angka yang tidak tergaris.
c. Tambahkan sebesar angka tersebut (pada
langkah b) kepada semua angka yang terletak
pada perpotongan dua garis.
d. Alokasikan pekerjaan pada angka-angka nol
tersebut.
e. Jika solusi optimum belum juga ditemukan,
ulangi lagi langkah a s/d d.
 Contoh:
Sebuah kontraktor memiliki 5 buah proyek yang
ditawarkan 5 sub-kontraktor. Biaya yang diajukan oleh
masing-masing sub-kontraktor untuk setiap proyek (dalam juta
Rp) diberikan matriks dibawah ini:
PROYEK
1 2 3 4 5
A 10 4 6 10 12

B 11 7 7 9 14
KARYAWAN

C 13 8 12 14 15

D 14 16 13 17 17

E 19 11 17 20 19
 MODEL LP
MIN 10A1+4A2+6A3+10A4+12A5+11B1+7B2+7B3+9B4+14B5+
13C1+8C2+12C3+14C4+15C5+14D1+16D2+13D3+17D4+17D5+
19E1+11E2+17E3+20E4+19E5

DENGAN BATASAN :
1). A1+A2+A3+A4+A5  1 , 6). A1+B1+C1+D1+E1 = 1,
2) B1+B2+B3+B4+B5  1 , 7) A2+B2+C2+D2+E2 = 1
3).C1+C2+C3+C4+C5  1, 8). A3+B3+C3+D3+E3 = 1,
4) D1+D2+D3+D4+D5  1 9) A4+B4+C4+D4+E4 = 1
5) E1+E2+E3+E4+E5  1 10). A5+B5+C5+D5+E5 = 1

Semua variabel non negatif

 LANGKAH PENYELESAIAN DENGAN LINDO

1. Ketikan model Lp dari masalah Penugasan pada

Command Window
2. Klik menu Solve
3. Klik Report Window
Maka akan terlihat tampilan seperti berikut ini:
Sintak model LP
Hasil /output laporan
 KESIMPULAN :

Dari hasil perhitungan LINDO pada tampilan 2 diperoleh

penyelesaian optimal sbb:

Penugasan : karyawan A → proyek 3

karyawan B → proyek 4
karyawan C → proyek 5
karyawan D → proyek 1
karyawan E → proyek 2
Dengan biaya minimal sebesar $55/jam